Finite Fields Appl. 1 (1995) 437–439

WHEN ARE WEAK

PERMUTATION POLYNOMIALS STRONG?

Sophie Frisch

Abstract. For a commutative finite ring with identity R, the two definitions of permutation polynomial in several indeterminates over R coincide if and only if R is a direct sum of finite fields. Amer. Math. Soc. 1991 Mathematics Subject Classification: 11T06, 13M10; Secondary: 13B25.

All rings considered are commutative and finite, and ring always means ring with identity. A polynomial f ∈ R[x] is said to be a permutation polynomial (abbreviated PP) if the function it defines on R through substitution, r ↦ f(r), is a permutation. This notion has been generalized to polynomials in several indeterminates in two different ways. We will characterize the rings for which the two coincide. (For quotient rings of the integers this has been done by Kaiser and Nöbauer [1].)

We write the cartesian product of n copies of a set S as S^{<n>}, to avoid confusion with the power S^{n}, if S happens to be an ideal. An m-tuple of polynomials (f_{0}, f_{1}, …, f_{m−1}) in n indeterminates over R induces a function (r_{0}, …, r_{n−1}) ↦ (f_{0}(r_{0}, …, r_{n−1}), …, f_{m−1}(r_{0}, …, r_{n−1})), which we denote by the same name, (f_{0}, f_{1}, …, f_{m−1}): R^{<n>} → R^{<m>}.

Definition. Let f be a polynomial in n indeterminates with coefficients in R. f is a strong PP if there exist polynomials f_{1},…,f_{n−1} in n indeterminates over R, such that the function (f, f_{1}, …, f_{n−1}): R^{<n>} → R^{<n>} is a permutation.

f is a weak PP if for every r in R the cardinality of the inverse image of r under f: R^{<n>} → R is |R|^{n−1}.

Clearly, strong PP implies weak PP. It is easy to see that f is a weak PP if and only if there exist functions g_{i}: R^{<n>} → R (not necessarily representable by polynomials), such that (f, g_{1}, …, g_{n−1}) permutes R^{<n>} (cf. [2, p120]).

Permutation Polynomials

If F is a finite field, it is well known that every function γ: F^{<n>} → F is represented by a polynomial with coefficients in F, namely by g(x_{1}, …, x_{n}) = ∑_{(c_{1},..,c_{n})∈F^{<n>}} γ(c_{1}, …, c_{n}) ∏_{i=1}^{n}(1 − (x_{i} − c_{i})^{|F |−1}); therefore every weak PP over a finite field is a strong PP [3, p369].

Lemma 1. Let n ∈ ℕ. A finite direct sum of finite commutative rings has the property “every weak PP over R in n indeterminates is strong” if and only if every summand has it.

Proof. If R = R_{1} × … × R_{k}, there is a natural isomorphism of R[X] (X a set of indeterminates) to R_{1}[X] × … × R_{k}[X], sending f to [f^{(1)}, …, f^{(k)}], where f^{(i)} results from f by projection of the coefficients onto R_{i}. Since addition and multiplication (and therefore evaluation of polynomials) in a direct sum of rings are defined componentwise, we may identify a vector r̄ ∈ R^{<n>} with the k-tuple of its components [r̄^{(1)}, …, r̄^{(k)}], r̄^{(i)} ∈ R_{i}^{<n>}, and f ∈ R[x_{1}, …, x_{n}] with [f^{(1)}, …, f^{(k)}], and the function f: R^{<n>} → R will correspond to the k-tuple of functions f^{(i)}: R_{i}^{<n>} → R_{i} acting independently on the components of R^{<n>}: f(r̄) = [f^{(1)}(r̄^{(1)}), …, f^{(k)}(r̄^{(k)})]. Therefore f is a weak [strong] PP over R if and only if each f^{(i)} is a weak [strong] PP over R_{i}. Indeed, if f is a weak PP, then |f^{−1}({r_{1}} × R_{2} × … × R_{k})| = |R|^{n−1} |R_{2}| … |R_{k}|. On the other hand f^{−1}({r_{1}} × R_{2} × … × R_{k}) = f^{(1)}^{−1}(r_{1}) × R_{2}^{<n>} × … × R_{k}^{<n>}, so |f^{(1)}^{−1}(r_{1})| = |R_{1}|^{n−1}. The remaining implications are even more straightforward. The statement of the Lemma now follows. (Note that every weak PP over R_{i}, f^{(i)} ∈ R_{i}[x_{1}, …, x_{n}], can be completed to a system [f^{(1)}, …, f^{(k)}] of weak PPs on the components of R by setting f^{(j)} = x_{1}, i ≠ j.) □

For a commutative ring R, Rad(R) denotes the intersection of all maximal ideals in R.

Lemma 2. Let R be a commutative finite ring with Rad(R) ≠ (0). If Rad(R) is generated as an ideal by n elements, then there exists a weak PP over R in n + 1 indeterminates that is not strong.

Proof. Suppose (0) ≠ Rad(R) = Q and let h(y) = y(∏_{p∈Q}(y − p))c, with c a multiple of [R : M] − 1 for every maximal ideal M of R; then h(p) = 0 for all p ∈ Q and h(r) ≡ r mod Q for all r ∈ R. If Q = q_{1}R + … + q_{n}R, let g(x_{1}, …, x_{n}) = q_{1}x_{1} + … + q_{n}x_{n}. Then g(R^{<n>}) = Q and for every p ∈ Q |g^{−1}(p)| = |ker(g)| = |R|^{n} / |Q|. Set f(x_{1}, …, x_{n}, y) = g(x_{1}, …, x_{n}) + h(y); we show that f is a weak but not a strong PP.

First note that f(r_{1}, …, r_{n}, s) ≡ s mod Q for all r_{1}, …, r_{n}, s ∈ R. We have |f^{−1}(r)| = |R|^{n} for every r ∈ R, because there are |Q| choices for s in r + Q and for each such s there are |R|^{n} / |Q| choices for (r_{1}, …, r_{n}) such that g(r_{1}, …, r_{n}) = r − h(s); so f is a weak PP. Suppose f is a strong PP, i.e. there exist f_{1}, …, f_{n} ∈ R[x_{1}, …, x_{n}, y], such that (f, f_{1}, …, f_{n}) permutes R^{<n+1>}. W.l.o.g. we assume the constant terms of f_{1}, …, f_{n} to be 0 (adding a constant does not affect bijectivity). Then |(f, f_{1}, …, f_{n})^{−1}({0} × Q^{<n>})| = |Q|^{n}. In contradiction to this there exists a set S ⊆ (f, f_{1}, …, f_{n})^{−1}({0} × Q^{<n>}) with |S| > |Q|^{n}, namely S = f^{−1}(0)∩Q^{<n+1>}. By hypothesis Q ≠ (0), but (being the radical) Q is nilpotent, so Q^{2} ≠ Q. Let g̃ be g restricted to arguments in Q, then g̃(Q^{<n>}) ⊆ Q^{2}, so |g̃(Q^{<n>})| < |Q| and |ker(g̃)| = |Q|^{n} / |g̃(Q^{<n>})| > |Q|^{n−1}. Therefore |f^{−1}(0) ∩ Q^{<n+1>}| = |ker(g̃)| · |Q| > |Q|^{n}. □

Theorem. If R is a commutative finite ring, then every weak PP over R is a strong PP if and only if R is a direct sum of finite fields.

Proof. By Lemma 1 and the remark preceding it, every weak PP over a finite direct sum of finite fields is strong. Conversely, if R is a finite commutative ring such that every weak PP over R is strong, then Lemma 2 implies Rad(R) = (0). But for a commutative finite ring R “Rad(R) = (0)” and “R is a direct sum of finite fields” are equivalent: This is an easy consequence of the fact that every commutative finite ring is a direct sum of local rings; cf. [4, p95]. □

References

1. H. K. Kaiser and W. Nöbauer, Permutation polynomials in several variables over residue class rings. J. Austral. Math. Soc. (Ser. A) 43 (1987), 171–175.

2. H. Lausch and W. Nöbauer, “Algebra of Polynomials,”

North-Holland, Amsterdam, 1973.

3. R. Lidl and H. Niederreiter, “Finite Fields,” Addison-Wesley,

Reading, MA, 1983.

4. B. R. McDonald, “Finite Rings with Identity,” Dekker, New York, 1974.

Institut für Mathematik (C), Technische Universität Graz, Kopernikusgasse 24, A-8010 Graz, Austria

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