in: D. E. Dobbs, M. Fontana, S.-E. Kabbaj (eds.), Advances in Commutative Ring Theory (Fes III Conf. 1997) Lecture Notes in Pure and Appl. Mathematics 205, Dekker 1999, pp 323–336.

POLYNOMIAL FUNCTIONS

ON

FI NITE COMMUTATIVE RI NGS

Sophie Frisch

Abstract. ‡ Every function on a finite residue class ring D/I of a Dedekind domain D is induced by an integer-valued polynomial on D that preserves congruences mod I if and only if I is a power of a prime ideal. If R is a finite commutative local ring with maximal ideal P of nilpotency N satisfying for all a, b ∈ R, if ab ∈ P^{n} then a ∈ P^{k}, b ∈ P^{j} with k + j ≥ min(n, N), we determine the number of functions (as well as the number of permutations) on R arising from polynomials in R[x]. For a finite commutative local ring whose maximal ideal is of nilpotency 2, we also determine the structure of the semigroup of functions and of the group of permutations induced on R by polynomials in R[x].

Introduction

Let R be a finite commutative ring with identity. Every polynomial f ∈R[x] defines a function on R by substitution of the variable. Not every function φ: R → R is induced by a polynomial in R[x], however, unless R is a finite field. (Indeed, if the function with φ(0) = 0 and φ(r) = 1 for r ∈ R \ {0} is represented by f ∈ R[x], then f(x) = a_{1}x + … + a_{n}x^{n} and for every non-zero r ∈ R we have 1 = f(r) = (a_{1} + … + a_{n}r^{n−1})r, which shows r to be invertible.)

This prompts the question how many functions on R are representable by polynomials in R[x]; and also, in the case that R = D/I is a residue class ring of a domain D with quotient field K, whether every function on R might be induced by a polynomial in K[x]? We will address these questions in sections 2 and 1, respectively.

‡ 1991 Math. Subj. Classification: Primary 13M10, 13B25; Secondary 11C08, 13F05, 11T06.

polynomial functions on finite rings

Other related problems are to characterize the functions on R arising from polynomials in R[x] by intrinsic properties of these functions (such as preservation of certain relations), and to determine the structure of the semigroup of polynomial functions on R and that of the group of polynomial permutations of R. In section 4, we will answer the second question in the special case that R is a local ring whose maximal ideal is of nilpotency 2.

Apart from that, the only result I am aware of is Nöbauer’s expression of the group of polynomial permutations on ℤ_{p^{n}} as a wreath product G≀S_{p}, with G a rather inscrutable subgroup (characterized by conditions on the coefficients of the representing polynomials) of the group of polynomial permutations on ℤ_{p^{n−1}} [11]. (There is a wealth of literature on the functions induced by polynomials on finite fields, some of it concerning the structure of the subgroup of S_{q} generated by special polynomials, see e.g. [8] and its references. Methods from the theory of finite fields do not help much with finite rings, however, except when the rings are algebras over a finite field, see [2].)

A characterization of polynomial functions by preservation of relations has been given for R = ℤ_{n} by Kempner [6]. For finite commutative rings in general there is the criterion of Spira [17] that a function is representable by a polynomial if and only if all the iterated divided differences that can be formed by subsets of the arguments and the respective values are in R.

In what follows, all rings are assumed to be commutative with identity, the natural numbers are written as ℕ = {1, 2, 3, …}, and the non-negative integers as ℕ_{0} = {0, 1, 2, …}.

1. Functions induced on residue class rings by integer-valued polynomials

In this section we give the answer, for Dedekind rings, to a question asked by Narkiewicz in his “Polynomial Mappings” book [9]. For R = ℤ, the ‘if’ direction has been shown (for several variables, cf. the corollary) by Skolem [16], the ‘only if’ direction by Rédei and Szele [12, 13].

If D is a domain with quotient field K, a polynomial f ∈ K[x] is called integer-valued on D if f(d) ∈ D for all d ∈ D. We write Int(D) for the set of all integer-valued polynomials on D. If I is an ideal of a domain D, we say that a polynomial f ∈ Int(D) induces a function φ: D/I → D/I if φ(d + I) = f(d) + I is well defined, i.e., if c ≡ d mod I implies f(c) ≡ f(d) mod I.

Theorem 1. Let R be a Dedekind domain and I an ideal of R of finite index. Every function φ: R/I → R/I is induced by a polynomial f ∈ Int(R) if and only if I is a power of a prime ideal of R.

Proof. The case of a finite field or of I = R = P^{0} is trivial, so we consider R infinite and I ≠ R. Let P be a prime ideal with I ⊆ P. Assume that the characteristic function of {0} on R/I is induced by a polynomial f ∈ Int(R), then f(r) ≡ 1 mod I for r ∈ I and f(r) ≡ 0 mod I for r ∉ I. We show that I must be a power of P. Suppose otherwise, then P^{n} ⊈ I for all n ∈ ℕ. Let c ∈ R and g ∈ R[x] such that f(x) = g(x)/c, and n = v_{P} (c).

Since g is in R[x], the function r ↦ g(r) on R preserves congruences mod every ideal of R, in particular mod P^{n+1}. It follows that r ≡ s mod P^{n+1} implies f(r) ≡ f(s) mod P. Now consider an element r ∈ P^{n+1}\I. On one hand, f(r) ∉ P, since f(r) ≡ f(0) mod P and f(0) ≡ 1 mod I; on the other hand, since r ∉ I, we have f(r) ∈ I ⊆ P, a contradiction.

To show that every function on R/P^{n} (P a prime ideal of finite index) is induced by a polynomial in Int(R), it suffices to show this for the charcteristic function of {0} on the residue class ring. For this, we need only construct a polynomial f ∈ Int(R) satisfying f(r) ∈ P for r ∉ P^{n} and f(r) ∉ P for r ∈ P^{n}; an appropriate power f̃(x) = f(x)^{m} will then satisfy f̃(r) ∈ P^{n} for r ∉ P^{n} and f̃(r) ≡ 1 mod P^{n} for r ∈ P^{n}.

Let a_{1}, …, a_{q^{n}−1} ∈ R be a system of representatives of the residue classes of P^{n} other than P^{n} itself, and let a_{0} ∈ P^{n−1} \ P^{n}. Put h(x) = ∏_{k=0}^{q^{n}−1}(x − a_{k}) and α = ∑_{j=1}^{n} [\frac{q^{n}}{q^{j}} ] = \frac{q^{n}−1}{q−1} , then for all r ∈ P^{n} we have v_{P} (h(r)) = α − 1, while v_{P} (h(r)) ≥ α for all r ∈ R \ P^{n}.

Now let Q = {Q ∈ Spec(R) | Q ≠ P; ∃k a_{k} ∈ Q} and for Q ∈ Q define m_{Q} = max{m ∈ ℕ | ∃k a_{k} ∈ Q^{m}}. Pick c ∈ R such that c ∉ P and c ∈ Q^{m_{Q}+1} for all Q ∈ Q, and set b_{k} = c^{−1}a_{k} and g(x) = ∏_{k=0}^{q^{n}−1}(x − b_{k}).

We now set f(x) = g(x)/g(0) and claim that f ∈ Int(R) and that for all r ∈ R, f(r) ∈ P if and only if r ∉ P^{n}. To verify this, we check that for all Q ∈ Spec(R) and all r ∈ R, v_{Q}(g(r)) ≥ v_{Q}(g(0)) and that v_{P} (g(r)) > v_{P} (g(0)) for r ∈ R \ P^{n}, while v_{P} (g(r)) = v_{P} (g(0)) for r ∈ P^{n}.

First consider those Q ∈ Spec(R) with v_{Q}(c) > 0. We have v_{Q}(b_{k}) < 0 for all k and therefore v_{Q}(g(r)) = ∑_{k=0}^{q^{n}−1} v_{Q}(b_{k}) = v_{Q}(g(0)) for all r ∈ R.

Now consider a Q ∈ Spec(R) with v_{Q}(c) = 0 and Q ≠ P, then v_{Q}(b_{k}) = 0 for all k, and for all r ∈ R we have v_{Q}(g(r)) ≥ 0 = v_{Q}(g(0)).

Concerning P, we observe that v_{P} (r − b_{k}) = v_{P} (c^{−1}(cr − a_{k})) = v_{P} (cr − a_{k}), such that v_{P} (g(r)) = v_{P} (h(cr)). Since v_{P} (cr) = v_{P} (r), this implies v_{P} (g(r)) ≥ α for r ∈ R \ P^{n} and v_{P} (g(r)) = α − 1 for r ∈ P^{n}. □

If K is the quotient field of a domain D and I an ideal of D, we say that f ∈ K[x_{1}, …, x_{m}] induces a function φ: (D/I)^{m} → D/I if φ(d_{1} + I, …, d_{m} + I) = f(d_{1}, …, d_{m}) + I makes sense, i.e., if f(d_{1}, …, d_{m}) ∈ D for all (d_{1}, …, d_{m}) ∈ D^{m} and f(d′_{1}, …, d′_{m}) ≡ f(d_{1}, …, d_{m}) mod I whenever d′_{i} ≡ d_{i} mod I for 1 ≤ i ≤ m.

Corollary. If R is a Dedekind domain, P a maximal ideal of finite index and n ∈ ℕ then every function f: (R/P^{n})^{m} → R/P^{n} is induced by a polynomial f ∈ K[x_{1}, …, x_{m}] (K being the quotient field of R).

Proof. It suffices to have a polynomial f ∈ K[x_{1}, …, x_{m}] that induces the characteristic function of (0, 0, …, 0) mod P^{n}. As R/P is a field, there exists a g ∈ R[x_{1}, …, x_{m}] such that g(r_{1}, …, r_{m}) ≡ 1 mod P if r_{i} ∈ P for 1 ≤ i ≤ m and g(r_{1}, …, r_{m}) ≡ 0 mod P otherwise. By the Theorem, there exists h ∈ Int(R) such that h(r) ∈ P if r ∈ P^{n} and h(r) ∉ P otherwise. Now f(x_{1}, …, x_{m}) = g(h(x_{1}), …, h(x_{m})) satisfies f(r_{1}, …, r_{m}) ∉ P iff r_{i} ∈ P^{n} for 1 ≤ i ≤ m, and a suitable power of g(x) = f(x)^{k} finally satisfies g(r_{1}, …, r_{m}) ≡ 1 mod P^{n} if r_{i} ∈ P^{n} for 1 ≤ i ≤ m and g(r_{1}, …, r_{m}) ≡ 0 mod P^{n} otherwise, as required. □

Note that the theorem and its proof still hold if we replace Dedekind ring by Krull ring, prime ideal by height 1 prime ideal, and restrict I to ideals with div(I) ≠ R.

2. The number formulas

For a commutative finite ring R, let us denote by F(R) the set (or semigroup with respect to composition) of functions on R induced by polynomials in R[x], and by P(R) the subset (or group) of those polynomial functions on R that are permutations.

When considering the functions induced on a finite commutative ring R by polynomials in R[x], we can restrict ourselves to local rings, since every finite commutative ring is a direct sum of local rings, and addition and multiplication (and therefore evaluation of polynomials in R[x]) are performed in each component independently.

For residue class rings of the integers, we know

|F(ℤ_{p^{n}})| = p^{∑_{k=1}^{n}β_{p}(k)} and |P(ℤ_{p^{n}})| = p!p^{p}(p − 1)^{p}p^{∑_{k=3}^{n}β_{p}(k)},

where p is a prime and β_{p}(k) is the minimal m ∈ ℕ such that p^{k} | m! (in other words, the minimal m ∈ ℕ such that α_{p}(m) ≥ k, with α_{p}(m) = ∑_{j≥1} [\frac{m}{p^{j}} ]).

The most lucid proof, in my opinion, of these two formulas is that by Keller and Olson [5], to whom the second one is due. Kempner’s earlier proof [6] of the formula for |F(ℤ_{p^{n}})| is rather more involved. Singmaster [15] and Wiesenbauer [18] gave proofs for R = ℤ_{m} which do not use reduction to the local ring case. Brawley and Mullen [3] generalized the formulas to Galois rings (rings of the form ℤ[x]/(p^{n}, f), where p is prime and f ∈ ℤ[x] is irreducible over ℤ_{p}, see [7]) and Nečaev [10] to finite commutative local principal ideal rings.

We will give a proof along the lines of Keller and Olson of a generalization of the formulas to a class of local rings (the suitable rings defined below) that properly contains the rings considered by Brawley, Mullen and Nečaev.

Definition. Let R be a finite commutative local ring R with maximal ideal P and N ∈ ℕ minimal with P^{N} = (0). We call R “suitable”, if for all a, b ∈ R and all n ∈ ℕ,

ab ∈ P^{n} ⟹ a ∈ P^{k} and b ∈ P^{j} with k + j ≥ min(N, n).

Note that every finite local ring R with maximal ideal P such that P^{2} = (0) is suitable, as well as every finite local ring whose maximal ideal is principal.

We may think of this property as inducing a valuation-like mapping v: R→H_{N}, by v(r) = k if r ∈ P^{k} \ P^{k+1} and v(0) = ∞, where (H_{N}, +) results from the non-negative integers by identifying all numbers greater or equal N; it is the semigroup with elements {0, 1, …, N − 1, N = ∞} and i + j = min(i + j, N), where the operations on the right are just the usual ones on non-negative integers.

Definition. If R is a finite local ring and P its maximal ideal, for n ≥ 0, let

α(n) = α_{(R,P)}(n) = ∑_{j≥1} [\frac{n}{[R: P^{j}]}]

and let β(n) = β_{(R,P)}(n) be the minimal m ∈ ℕ such that α_{(R,P)}(m) ≥ n. (If R and P are understood, we suppress the subscript (R, P) of α and β.)

Remark. Note that α_{(R,P)}(n) is finite if and only if n < |R|; we will never use α_{(R,P)} outside that range. Also note that, since [R/P^{k} : P^{j}/P^{k}] = [R : P^{j}] for j ≤ k, we have α_{(R,P)}(n) = α_{(R/P^{k},P/P^{k})}(n) in the range where both values are finite, that is for n < [R: P^{k}].

Theorem 2. Let R be a suitable finite local ring with maximal ideal P, q = [R:P], and N ∈ ℕ minimal, such that P^{N} = (0). Then

|F(R)| = ∏_{j=0}^{β(N)−1}[R: P^{N−α(j)}],

where α(n) = ∑_{j≥1} [\frac{n}{[R:P^{j}]}] and β(n) is the minimal m ∈ ℕ such that α(m) ≥ n. Also, for N > 1,

|P(R)| = \frac{q! (q − 1)^{q}}{q^{2q}} |F(R)| .

If [P^{k−1} : P^{k}] = q for 1 ≤ k ≤ N, the formulas simplify to

|F(R)| = q^{∑_{k=1}^{N}β_{q}(k)} and |P(R)| = q!q^{q}(q − 1)^{q} q^{∑_{k=3}^{N}β_{q}(k)},

where α_{q}(m) = ∑_{j≥1} [\frac{m}{q^{j}} ] and β_{q}(k) is the minimal m ∈ ℕ such that α_{q}(m) ≥ k.

We will prove the expression for |F(R)| at the end of the next section, and that for |P(R)| at the end of section 4.

3. A canonical form for the polynomial repesenting a function.

Definition. Let R be a commutative finite local ring with maximal ideal P of nilpotency N. We call a sequence (a_{k})_{k=0}^{∞} of elements in R a P -sequence, if for 0 ≤ n ≤ N

a_{k} − a_{j} ∈ P^{n} ⟺ [R: P^{n}] | k − j;

and if (a_{k}) is a P -sequence, we call the polynomials

⟨x⟩_{0} = 1  and  ⟨x⟩_{n} = (x − a_{0}) … (x − a_{n−1}) for n > 0

the “falling factorials” constructed from the sequence (a_{k}).

A P -sequence (a_{k}) for R is easy to construct inductively: Let a_{0}, …, a_{[R:P]−1} be a complete set of residues mod P with a_{0} = 0. Once a_{k} has been defined for k < [R: P^{n−1}] (while n ≤ N), define a_{k} for [R: P^{n−1}] ≤ k < [R: P^{n}] as follows: let b_{0} = 0, b_{1}, …, b_{[P^{n−1}:P^{n}]−1} be a complete set of residues of P^{n−1} mod P^{n}; then, for k = j[R : P^{n−1}] + r with 0 ≤ r < [R : P^{n−1}] and 1 ≤ j < [P^{n−1} : P^{n}], let a_{k} = b_{j} + a_{r}. After a_{0}, …, a_{|R|−1} have been defined (necessarily a complete enumeration of the elements of R), continue the sequence |R|-periodically.

In the following Lemma, we use the convention that P^{∞} = (0).

Lemma. Let R be a suitable finite local ring with maximal ideal P of nilpotency N, and ⟨x⟩_{n} the falling factorial of degree n constructed from a P -sequence (a_{k}). Then for all n ∈ ℕ_{0},

∀r ∈ R ⟨r⟩_{n} ∈ P^{α(n)}  and  if α(n) < N then ⟨a_{n}⟩_{n} ∉ P^{α(n)+1}.

Proof. If n ≥ |R| (equivalent to α(n) = ∞) then, since a_{0}, …, a_{|R|−1} enumerate all elements of R, ⟨r⟩_{n} = 0 for all r.

If n < |R| then α(n) = ∑_{k=1}^{N} [\frac{n}{[R:P^{k}]}], while ⟨r⟩_{n} ∈ P^{e}, where e =

∑_{k=1}^{N−1} k |{j | 0 ≤ j < n; r − a_{j} ∈ P^{k} \ P^{k+1}}| + N |{j | 0 ≤ j < n; r − a_{j} ∈ P^{N}}|

= ∑_{k=1}^{N} |{j | 0 ≤ j < n; r − a_{j} ∈ P^{k}}|

and (by definition of suitable) ⟨r⟩_{n} is in no higher power of P if e < N.

From the definition of P -sequence, we see that |{j | 0 ≤ j < n; r − a_{j} ∈ P^{k}}| is either [\frac{n}{[R:P^{k}]}] or [\frac{n}{[R:P^{k}]}] + 1 and the +1 doesn’t occur for r = a_{n}. □

Proposition 1. Let R be a suitable finite local ring with maximal ideal P of nilpotency N, (a_{k}) a P -sequence for R, ⟨x⟩_{k} the falling factorial of degree k constructed from it and let 0 ≤ n ≤ N.

A polynomial f ∈ R[x] induces the zero-function on R/P^{n} if and only if

f(x) = ∑_{j≥0} c_{j}⟨x⟩_{j}  with  c_{j} ∈ P^{n−α(j)} for 0 ≤ j < β(n).

Proof. As ⟨x⟩_{j} maps R into P^{α(j)}, the “if” direction is evident. To show “only if”, assume that f(x) = ∑_{j≥0} c_{j}⟨x⟩_{j} maps R into P^{n}. We show c_{j} ∈ P^{n−α(j)} for 0 ≤ j < β(n) by induction on j. (There is no condition on the coefficients for j ≥ β(n), since ⟨x⟩_{j} already maps R into P^{n} for those j.)

For j = 0, we have c_{0} = f(a_{0}) ∈ P^{n}. Now assume c_{i} ∈ P^{n−α(i)} for i < j and consider f(a_{j}). Since ⟨x⟩_{i} maps R into P^{α(i)} and ⟨a_{j}⟩_{k} = 0 for k > j, we have f(a_{j}) ≡ c_{j}⟨a_{j}⟩_{j} mod P^{n}. Also, ⟨a_{j}⟩_{j} is in no higher power of P than P^{α(j)}. Therefore f(a_{j}) ∈ P^{n} implies c_{j} ∈ P^{n−α(j)}. □

Corollary 1. In the situation of the Proposition, for 0 ≤ j < β(n), let C_{j} be a complete set of residues mod P^{n−α(j)}. Then every function on R/P^{n} arising from a polynomial in R[x] arises from a unique polynomial of the form

f(x) = ∑_{j=0}^{β(n)−1} c_{j}⟨x⟩_{j}  with  c_{j} ∈ C_{j}.

For R = ℤ_{p^{n}}, other canonical forms for the functions representable by polynomials have been given by Dueball [4], Aizenberg, Semion and Tsitkin [1] and Rosenberg [14] (the latter for polynomials in several variables).

Corollary 2. In the situation of the Proposition, if n > 0 then for every function induced on the residue classes of P^{n−1} by a polynomial in R[x], there are exactly

∏_{j=0}^{β(n)−1}[P^{n−α(j)−1} : P^{n−α(j)}]

different polynomial functions on the residue classes of P^{n} that reduce to the given function mod P^{n−1}. If [P^{k−1} :P^{k}] = q for 1 ≤ k ≤ N then the expression simplifies to q^{β_{q}(n)}, where β_{q}(n) is the minimal m ∈ ℕ such that α_{q}(m) = ∑_{j≥1} [\frac{n}{q^{j}} ] ≥ n.

Proof of the formula for |F(R)| in Theorem 2: That |F(R)|=∏_{j=0}^{β(N)−1}[R:P^{N−α(j)}] follows immediately from Corollary 1 with n = N. In the special case that [P^{k−1} : P^{k}] = q for 1 ≤ k ≤ N, writing s_{k} for the number of different functions on R/P^{k} arising from polynomials in R[x], we see from Corollary 2 that q^{β_{q}(k)}s_{k−1} = s_{k}. Therefore q^{∑_{k=1}^{N} β(k)} = s_{N} = |F(R)| in that case. □

4. The group P(R/P^{2})

We want to determine the structure of the group P(R/P^{2}) with respect to composition of functions, R being a suitable finite local ring as above. To simplify notation, we consider the group P(R), where R is a finite local ring with maximal ideal P of nilpotency N = 2.

Some notational conventions: We write the group of invertible elements of a monoid M as M^{∗}. If M is a monoid and H a monoid acting on a set S then the wreath product M ≀H is the monoid defined on the set H × M^{S} by the operation

(h, (m_{s})_{s∈S})(g, (l_{s})_{s∈S}) = (hg, (m_{g(s)}l_{s})_{s∈S}).

If M acts on a set T then the standard action of M ≀H on S × T is

(h, (m_{s})_{s∈S})(x, y) = (h(x), m_{x}(y)).

Note that an element (h, (m_{s})_{s∈S}) is in (M ≀H)^{∗} if and only if h∈H^{∗} and m_{s} ∈M^{∗} for all s ∈ S, and that therefore (M ≀H)^{∗} ≃ M^{∗}≀H^{∗}.

If D is a commutative ring and M a D-module, we write 𝔸_{D}(M) for the semigroup with respect to compostion of transformations of M of the form x ↦ ax + b with a ∈ D and b ∈ M. We have |𝔸_{D}(M)| = |D/Ann(M) × M|.

Proposition 2. Let R be a finite local ring with maximal ideal P of nilpotency 2 and q = [R:P]. Denote by Q^{Q} the semigroup of functions from a set of q elements to itself. Then

F(R) ≃ 𝔸_{R/P} (P)≀Q^{Q}  and  P(R) ≃ 𝔸_{R/P}^{∗} (P)≀S_{q},

and in particular,

|F(R)| = q^{q} |R|^{q}  and  |P(R)| = q! (q − 1)^{q} |P |^{q}.

Proof. Fix a system of representatives Q of R mod P. We identify R with Q × P by r ↦ (s, t) with s ∈ Q, t ∈ P, such that r = s + t. Let f ∈ R[x]. We have

f(r) = f(s + t) = f(s) + f′(s)t,

since this holds mod P^{2} by Taylor’s Theorem and P^{2} = (0) in R. Now let φ(s) be the representative in Q of f(s) + P, then

f(s + t) = φ(s) + (f(s) − φ(s)) + f′(s)t,

with φ(s) ∈ Q and f(s) − φ(s) ∈ P. We regard f′(s) as being in R/P. (As it gets multiplied by t ∈ P, only its residue class mod P matters).

If we associate to f ∈ R[x] the functions φ_{f}: Q → Q and ψ_{f}: Q → 𝔸_{R/P} (P), where

• φ_{f}(s) is the representative in Q of f(s) + P

• ψ_{f}(s) is the transformation x ↦ a_{f}(s)x + b_{f}(s) on P, where • a_{f}(s) ∈ R/P is f′(s) mod P,

• b_{f}(s) = f(s) − φ(s) ∈ P then φ_{f} and ψ_{f} completely determine the function induced by f on R.

Moreover, the function defined on Q × P by φ ∈ Q^{Q}, a ∈ (R/P)^{Q} and b ∈ P^{Q} via (s, t) ↦ φ(s) + a(s)t + b(s) determines φ, a and b uniquely, such that for f, g ∈ R[x] inducing the same function on R we have φ_{g} = φ_{f} and ψ_{g} = ψ_{f}. Therefore f ↦ (φ_{f}, ψ_{f}) depends only on the function induced by f ∈ R[x] on R and defines a homomorphism from F(R) to 𝔸_{R/P} (P)≀Q^{Q}, which takes the action of F(R) on R (identified with Q × P) to the standard action of A≀Q^{Q} arising from the obvious actions of A on P and of Q^{Q} on Q. We have already seen that this homomorphism is injective.

To check surjectivity, we show that every triple of functions φ: Q → Q, b: Q → P and a: Q → R/P actually occurs as φ_{f}, a_{f} and b_{f} for some f ∈ R[x].

Every pair of functions on R/P arises as f mod P and f′ mod P for some polynomial f ∈ R[x], because R/P is a finite field. This takes care of φ_{f} and a_{f}. Since the characteristic function of every residue class of P is induced by a polynomial in R[x] (just take a sufficiently high power of a polynomial representing it mod P), we can adjust f to take prescribed values on the s ∈ Q, by adding a P - linear combination of these characteristic functions. This produces a prescribed b_{f} without disturbing the values of f and f′ mod P, since we only add a polynomial in P [x].

If we restrict to polynomials representing permutations or, equivalently, to polynomials for which φ_{f} is a permutation of Q and a_{f}(s) ≠ 0 + P for all s ∈ Q, we get an isomorphism of P(R) and 𝔸_{R/P}^{∗} (P)≀S_{q}, which takes the action of P(R) on R (identified with Q × P) to the standard action of the wreath product on Q × P arising from the obvious actions of 𝔸_{R/P}^{∗} on P and of the symmetric group S_{q} on Q. □

Remark. We may simplify the expression for P(R) by noting that 𝔸_{R/P} (P) is isomorphic to the semi-direct product ((R/P)^{∗}, ·)⋉(P, +) with (R/P)^{∗} acting on (P, +) through the scalar mulutiplication of the R/P -vectorspace structure on P.

Proof of the formula for |P(R)| in Theorem 2: For n ≤ N, let s_{n} denote the number of functions on the residue classes of P^{n} induced by polynomials in R[x] and t_{n} the number of them that are permutations.

If n ≥ 2, a polynomial induces a permutation mod P^{n} if and only if it induces a permutation mod P and its derivative is nowhere zero mod P, cf. [7]. In particular, if n > 2, a polynomial induces a permutation mod P^{n} if and only if it induces one mod P^{n−1}. Together with the fact that every class of polynomial functions mod P^{n} reducing to the same function mod P^{n−1} contains the same number of elements (Corollary 2 of Proposition 1), this implies that \frac{t_{n}}{t_{n−1}} = \frac{s_{n}}{s_{n−1}} for all n > 2, and therefore t_{n} = \frac{t_{2}}{s_{2}} s_{n} for all n ≥ 2.

From Proposition 2 applied to R/P^{2} we get t_{2} = q!(q − 1)^{q}[P : P^{2}]^{q} and s_{2} = q^{q}[R: P^{2}]^{q} and the formula for |P(R)| follows. □

references

[1] N. Aizenberg, I. Semion, and A. Tsitkin, Polynomial representations of logical functions, Automatic Control and Computer Sciences (transl. of Automatika i Vychislitel’naya Tekhnika, Acad. Nauk Latv. SSR (Riga)), 5 (1971), pp. 5–11 (orig. 6–13).

[2] D. A. Ashlock, Permutation polynomials of Abelian group rings over finite fields, J. Pure Appl. Algebra, 86 (1993), pp. 1–5.

[3] J. V. Brawley and G. L. Mullen, Functions and polynomials over Galois rings, J. Number Theory, 41 (1992), pp. 156–166.

[4] F. Dueball, Bestimmung von Polynomen aus ihren Werten mod p^{n}, Math. Nachr., 3 (1949/50), pp. 71–76.

[5] G. Keller and F. Olson, Counting polynomial functions (mod p^{n}), Duke Math. J., 35 (1968), pp. 835–838.

[6] A. J. Kempner, Polynomials and their residue systems, Trans. Amer. Math. Soc., 22 (1921), pp. 240–266, 267–288.

[7] B. R. McDonald, Finite Rings with Identity, Dekker, 1974.

[8] G. L. Mullen and H. Niederreiter, The structure of a group of permutation polynomials, J. Austral. Math. Soc. Ser. A, 38 (1985), pp. 164–170.

[9] W. Narkiewicz, Polynomial Mappings, vol. 1600 of Lecture Notes in Mathematics, Springer, 1995.

[10] A. Nechaev, Polynomial transformations of finite commutative local rings of principal ideals, Math. Notes, 27 (1980), pp. 425–432. transl. from Mat. Zametki 27 (1980) 885-897, 989.

[11] W. Nöbauer, Gruppen von Restpolynomidealrestklassen nach Primzahlpotenzen, Monatsh. Math., 59 (1955), pp. 194–202.

[12] L. Rédei and T. Szele, Algebraisch-zahlentheoretische Betrachtungen über Ringe I, Acta Math. (Uppsala), 79 (1947), pp. 291–320.

[13] , Algebraisch-zahlentheoretische Betrachtungen über Ringe II, Acta Math. (Uppsala), 82 (1950), pp. 209–241.

[14] I. G. Rosenberg, Polynomial functions over finite rings, Glas. Mat., 10 (1975), pp. 25–33.

[15] D. Singmaster, On polynomial functions (mod m), J. Number Theory, 6 (1974), pp. 345–352.

[16] Th. Skolem, Einige Sätze über Polynome, Avh. Norske Vid. Akad. Oslo, I. Mat.-Naturv. Kl., 4 (1940), pp. 1–16.

[17] R. Spira, Polynomial interpolation over commutative rings, Amer. Math. Monthly, 75 (1968), pp. 638–640.

[18] J. Wiesenbauer, On polynomial functions over residue class rings of ℤ, in Contributions to general algebra 2 (Proc. of Conf. in Klagenfurt 1982), Hölder-Pichler-Tempsky, Teubner, 1983, pp. 395–398.

Institut für Mathematik C / Technische Universität Graz / Steyrergasse 30 / A-8010 Graz / Austria

e-mail: frisch@blah.math.tu-graz.ac.at