A Theory of Permutation Polynomials Using Compositional Attractors Citation Ashlock, Daniel Abram (1990) A Theory of Permutation Polynomials Using Compositional Attractors. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/24QB-M779. https://resolver.caltech.edu/CaltechETD:etd-06022006-085847 Abstract In this work I will develop a theory of permutation polynomials with coefficients over finite commutative rings. The general situation will be that we have a finite ring R and a ring S, both with 1, with S commutative, and with a scalar multiplication of elements of R by elements of S, so that for each r in R 1 S •r = r and with the scalar multiplication being R bilinear. When all these conditions hold, I will call R an S-algebra. A permutation polynomial will be a polynomial of S[x] with the property that the function r |→ f(r) is a bijection, or permutation, of R. Item Type: Thesis (Dissertation (Ph.D.)) Subject Keywords: Mathematics Degree Grantor: California Institute of Technology Division: Physics, Mathematics and Astronomy Major Option: Mathematics Thesis Availability: Public (worldwide access) Research Advisor(s): Wales, David B. (advisor) Wilson, Richard M. (co-advisor) Thesis Committee: Wilson, Richard M. (chair) Aschbacher, Michael Ramakrishnan, Dinakar Wales, David B. Luxemburg, W. A. J. Defense Date: 7 May 1990 Non-Caltech Author Email: dashlock (AT) uoguelph.ca Record Number: CaltechETD:etd-06022006-085847 Persistent URL: https://resolver.caltech.edu/CaltechETD:etd-06022006-085847 DOI: 10.7907/24QB-M779 Default Usage Policy: No commercial reproduction, distribution, display or performance rights in this work are provided. ID Code: 2397 Collection: CaltechTHESIS Deposited By: Imported from ETD-db Deposited On: 02 Jun 2006 Last Modified: 14 Jan 2022 01:13 Thesis Files Preview PDF (Ashlock_da_1990.pdf) - Final Version See Usage Policy. 4MB Repository Staff Only: item control page

A Theory of Permutation Polynomials Using Compositiond Attractors Thesis by Daniel Abram Ashlock In Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy California Institute of Technology Pasadena, California 1990 (Submitted May 7 , 1990) @ 1990 Daniel Abram Ashlock All rights Reserved Acknowledgments W a r m thanks go t o my friend and colleague Jack Lutz who accidentally shoved me toward this thesis with his question, "Aren't the first two congruent t o the third mod two?" Thanks go t o James Cummings who read this work in its early stages and with whom I had many stimulating discussions. I must credit Heeralal Janwa with providing me with many useful references. My committee deserves thanks for their investment of time, both in sitting on my committee and in training me in mathematics. I want especially t o thank Michael Aschbacher, who read the work in progress and corrected my many blunders in group theory, Dinakar Ramakrishnan, who suggested many topics for future application of my work, and Richard Wilson, my advisor, who has supervised my work for the last four years and has taught me much delightful and beautiful comhinatorics. I must also thank my wife, Wendy, who has been substantially inconvenienced by my graduate studies and nonetheless provided love and support, and my father, Peter Dunning Ashlock, who died while I was working on this thesis. More than any other person he trained me in t h e philosophy and methods of science and gave me my direction through life. iv Table of Contents .. Copyright 11 Acknowledgments ... 111 Table of Contents iv List of Tables vi List of Examples vii Introduction and Summary Chapter I. Definitions and Basic Results. $0. Introduction and Summary. 1 Equivalence Results. $2. Lifting and Decomposition Lemmas. $3. Properties of Compositional Attractors. 11. Results for Finite Fields and t h e Integers. $0. Introduction and Summary. $1. Compositional Attractors of GF(pn)[x]. $2. T h e Order of Finite Permutation Polynomial Groups with Finite Field Coefficents. $3. Compositional Attractors of Z[x]. 111. T h e Groups PPZn(Zn) and PPZn(Zmim). $0. Introduction and Summary. $ 1 Singmaster's Result. 52. A Basis for t h e Ideal 1 2 . $3. T h e Group PPZn(Zn). $4. Computation of t h e Ideal I zmim zn ' $5. Membership and Enumeration of the Group IV. Applications and Topics for Future Work. $0. Introduction and Summary. 1 T h e Permutation Polynomials of t h e p-adic Integers. $2. Permutation Polynomials of Abelian Group Algebras over Finite Fields. 93. Questions for Further Study. Appendices A Explicit Examples of Polynomial Groups. T h e Group Sym(GF(5)) Realized as Polynomials. T h e Stabilizer of 0 in PP(Z9) B Tables of special functions. C Certain Permutation Polynomial Groups. List of Tables Table 3.1, Values of ~ ( n ) 41 Table 3.2, Order of PPm(Zn) 71 The Symmetric Group on GF(5) as Cycle and Polynomials 80 Values of r ( n ) 83 Values for em(n) 84 List of Examples Example 1.1, Permutation Polynomials of a Finite Field 7 Example 1.2, A Homomorphism of Polynomial Groups 15 Example 2.1, Compositional Attractors of a Subfield 20 Example 2.2, Compositional Attractors for Matrices over G F ( q ) 20 Lemma 2.1, T h e Compositional Attractor of a Polynomial Modular Algebra 20 Example 2.3, An Irreducible of Z ,[XIt h a t Factors Modulo p P 33 Example 2.4, A Family of Compositional Attractors of Z[x] 34 Example 3.1, Generators for fI2, II2* 43 Example 3.2, Computation of a Least Degree Common Multiple 58 Example 4.1, T h e GF(2)-Permutation Polynmials of GF(2)[C3] 76 Appendix A, Example 4.2, T h e number of GF(3)-Permutation Polynomials of GF(3)[C6] 77 T h e GF(5)-permutation polynomials of GF(5) as cycles and polynomials of least possible degree 80 Introduction and Summary In this work I will develop a theory of permutation polynomials with coefficents over finite commutative rings. T h e general situation will be that we have a finite ring R and a ring S, both with 1, with S commutative, and with a scalar multiplication of elements of R by elements of S, so that for each r in R ls.r multiplication being R bilinear. algebra. = r and with the scalar When all these conditions hold, I will call R an S- A permutation polynomial will be a polynomial of S[x] with the property that t h e function r + f f r ) is a bijection, or permutation, of R. Presented here, as far a s I know for the first time, is t h e idea t h a t compositional attractors are integral t o t h e study of permutation polynomials. A compositional attractor is an ideal I in a polynomial ring S[x] with t h e added property t h a t There are several reasons that compositional attractors are important. First of all, a compositional attractor of Six] is exactly a n ideal comprised of the polynomials t h a t are zero everywhere on some S-algebra, i.e., it is the kernal of the representation of S[x] as a ring of functions over R. This means t h a t they capture the equivalence relation associating polynomials t h a t give the same permutation. Such a ideal, zero everywhere on an S-algebra, is called the compositional attractor associated with an S-algebra. Second, polynomial composition modulo an ideal forms a monoid if and only if that ideal is a compositional attractor. One consequence of this is t h a t the polynomials with the identity polynomial f(x) = x in their composition sequence modulo a compositional attractor form a group under composition. Third, two S-algebras with the same associated compositional attractors in S[x] necessarily have identical permutation polynomials in S[x]. Since it is often easier to compute a compositional attractor associated with an algebra than t o compute the permutation polynomials directly, this gives a powerful tool for locating and enumerating the permutation polynomials of certain S-algebras. Fourth, if J < -I S[x] is a compositional attractor, then S[x]/J is an S-algebra with associated compositional attractor J. This fact gives a canonical domain in which t o perform computations. This fact, while quite easy t o prove, is of great utility in classifying the permutation polynomial groups when S is taken t o be a finite field. In addition, taken together with t h e third point, this fourth fact has a wonderful consequence. In a rather nice paper, "Polynomials Over a Ring T h a t Permute the Matrices Over T h a t Ring,"[lO] Brawley spends not inconsequential effort doing matrix arithmetic t o prove a theorem t h a t characterizes scalar permutation polynomials of matrices. I t turns o u t t h a t in specific instances a n alternate p r w f is possible in which one first computes t h e associated compositional attractor for the matrix ring and then does t h e computations in the corresponding canonical algebra, which is commutative. This thesis is presented in four chapters. T h e first chapter develops, in abstract, the properties of compositional attractors mentioned above, along with a few other straightforward properties. T h e set of compositional attractors of a polynomial ring is, for example, closed under intersection and multiplication of ideals. T h e second chapter focuses on the cases when S is a finite field or the integers. In the first section I classify the compositional attractors of Fix] for any finite field F. In the second section I compute the size of the permutation polynomial groups t h a t arise modulo these compositional attractors. T h e work in the second section is essentially a generalization, with new terminology, of a paper, "Permutations with Coefficients in a Subfield,"[S] by L. Carlitz and D. R. Hayes, which treats t h e case where R is a field and S is a subfield R. In the third section I give a few useful lemmas about the compositional attractors of Z[x] and present an example. T h e third chapter explores the situation when S is the integers or the integers modulo n and R is taken t o be either the integers modulo n o r matrices over t h e integers modulo n. In t h e first section I present a new proof, based on t h e difference operator Af(x) = f(x+l)-f(x) of Singmaster's forrnnla[4] for the number of polynomial functions from H, t o itself. In the second section I give a new proof, also with the difference operator, of Niven and Warren's[G] basis theorem for the compositional attractor in Z,[x] associated with 2,. In t h e third section I count the 2,-permutation polynomials of Z,, give the isomorphism type of t h e group for cube-free integers n, and give some information about t h e isomorphism type of the group for all n. In t h e fourth section I compute a basis for the compositional attractor of Z,[x] associated with t h e matrices over 2, and use the basis t o count the number of Z,polynomial functions from Zmim t o itself. In the fifth section I reprove Brawtey's[lO] characterization of Zn-permutation polynomials of t h e matrices over Z, and g o on t o enumerate t h e group of such polynomials for each n. In t h e fourth chapter I skip lightly over easy consequences of t h e material developed i n t h e first three chapters and give topics for future research. In Section one I compute exactly t h e membership of t h e p-adic permutation polynomials of t h e p-adic integers. I n Section two I compute t h e compositional attractors of F[x] associated with F[G] and count t h e groups of F-permutation polynomials of FIG] where F is a finite field, G is an abelian group, and F[G] is t h e group algebra of F over G. As one might expect, t h e case where t h e characteristic of F divides t h e order of G is t h e hard one, but not too hard. In Section three I define multivariate compositionat attractors and give a list of topics for future consideration. I more o r less stumbled into this thesis topic accidentally. In t h e summer of 1986 I was trying t o find some algebraic structure in t h e rules for generating cellular automata. T h i s is a relatively futile pursuit, but in t h e process I discovered a number of properties of functions from Zn t o 2,. I also reproduced Singmaster's results from[4]. A t this point Heeralal J a n w a arrived a t Caltech for a two-year stint. While I was trying t o explain t o him what I was working on he said, 'This sounds very much like permutation polynomials." T h i s gave m e a n application for t h e material I had developed on functions over 2,. particular, t h e difference operator Akf(x) = f(x+k)-f(x) In leads t o nice slick proofs of some known results, contained in t h e first two sections of Chapter three. I spent a great deal of computer time computing t h e membership and structure of groups of permutation polynomials over 2,. In t h e end I had t h e membership, size, and some structural information about t h e groups in question, but not enough material for a thesis. My advisor, Richard Wilson, suggested t h a t I generalize t o the matrix case Now the matrix case is severely resistant t o computer scans. T h e problem of computing a least degree monic polynomial zero everywhere o n two-by-two matrices over Z4 is about the limit of what you can d o on a personal computer unless you prove some theorems. In addition, many of the nice proofs in t h e non-matrix case depend heavily on the commutativity of Z,. Carlitz, Levine, and others [S], A t this point I uncovered the material by Brawley, [lo], [ll]. Their theorems were often theorems that would be true if matrices commuted. In other words, they would have two, essentially identical, theorems for commutative and noncommutative rings with substantially different proofs. At this point, inspired by [9], I decided t o leave t h e matrix case alone and t o try computing permutation polynomials over finite commutative rings. T h e first step in this process was computing the ideal of polynomials zero everywhere on the ring. I used a computer t o find this ideal for a large number of examples, particularly for group algebras over finite fields, which are easy t o implement on a computer. At this point I noticed t h a t many different algebras can have the same zeroing ideals and, more importantly, t h a t when they do, they also have t h e same permutation polynomials. I set o u t t o prove this and in the process was forced into considering t h e notion of compositional attractors. After a few months in which I roughed o u t the material presented in Chapter two, I realized t h a t compositional attractors solved my problem with the matrix case. The theory of compositional attractors gave me a way t o construct a commutative algebra with the exact same compositional attractor and hence permutation polynomials as any given noncommutative algebra. current form. Developing this idea put the thesis in more or less its 1Definitions and Basic Results $0 Introduction and Summary. Throughout this chapter S will be a commutative ring with 1, and R will be a finite Salgebra with 1. By 1: I will denote the set ( f ( x ) c ~ [ ~: ]VrcR, f(r) = 0). T h a t 1: is an ideal of S[X] is elementary; I sometimes call it t h e S-zeroing ideal of R. F(R, R ) denotes the set of functions from R t o itself, which I will treat as both a monoid under functional composition and an algebra under the usual extension of the addition and mnltiplication on R and scalar multiplication by S. I denote by 6; : S[X] -r F(R, R ) t h e evaluation map; i.e., f(x) b (r b f(r)). an algebra homomorphism. T h e kernel of r: f(x)c1:). As an algebra homomorphism c: Note t h a t E: is both a monoid and as a monoid homomorphism is has kernel .:I {x+f(x) : I will denote by FS(R), the S-polynomial functions on R, the image of r:, which is both a submonoid and subalgehra of F(R, R). I will denote by PPS(R), the S-permutation polynomials on R, the subset of Fs(R) t h a t are invertible (bijective) members of the monoid FS(R). PPS(R) is a submonoid of Fs(R) but is not a subalgebra of Fs(R). Notice that Notice also that the choice of invertible elements makes PPS(R) a group under composition. Finally, if U is a ring of functions call a n ideal I of U a compositional attractor if for all f c I and for all g c U , we have f o g c I, where o denotes functional composition. As motivation for these definitions, I would like t o give an overview of the use I will p u t them t o and illustrate it with a basic example. problem is t o compute the membership of 1: Having fixed R and S, the first and produce, if possible, a nice set of generators for it. Once we have ;1 it is easy t o enumerate FS(R) and t o find, as a side effect, its structure as an S-module. Using results from this chapter, I can often go on t o compute the membership of PPS(R) and subsequently enumerate PPS(R). Finally, where possible, I will determine the isomorphism type of the group PPs(R). For example, if we choose R = GF(q), the field with q elements, and choose S = R , then we see immediately from the theory of finite fields, t h a t Example 1.1. (i) 12 = <xq-x>, (ii) /FS(R)I = qq, (iii) F,(R) can he given the structure of a q-dimensional vector space over S, (iv) / P P ~ ( R ) I= q! (v) PPs(R) G Sym(R), the group of all permutations of R. These particular results, while both easy and elementary, are central t o the theory of permutation polynomials over a finite commutative ring. T h e theory of Jacobson radicals tells us t h a t a finite commutative ring modulo its radical is a direct product of finite fields. In this section we observe t h a t for any finite S-algebra R, we may find a commutative S-algebra R', so t h a t PPS(R) G P P ~ ( R ' ) and t h a t a direct product decomposition of S often induces a direct product decomposition of PPS(R). Taken together these results make the above example broadly applicable. O n t h e other hand, when R has a nontrivial Jacobson radical, many interesting things happen t h a t prevent t h e permutation polynomial groups in question from being merely direct products of symmetric groups. In this instance the utility of t h e above results follow from the observation t h a t the natural homomorphism of R modulo its Jacobson radical o n t o a n S-algebra with semisimple ring structure induces a group homomorphism of the corresponding permutation polynomial groups. '$1 Equivalence Results. In this section I will prove several lemmas t h a t allow me t o export calculation done for one choice of R and S t o others. Lemma 1.1. For a polynomial f(x) E S[x], let f(")(x) denote composition of f(x) with itself n times. Then: (i) PPs(R) = {f(x)ef: : 3 n f(")(x) E x (mod IR , o r equivalently s)> (ii) P P S ( R ) Z {f(x) E s[x]/I: : 3 n P")(x) E x), as a group under composition mod 1.: Proof: Suppose for f(x)rS[x] t h a t 3 n h n ) ( x ) E x (mod I:). Then since c: homomorphism, it follows t h a t t h e n-fold composition of f(x)c: function on R. This requires f(x)r: {f(x)cf: : 3n f(")(x) z x (mod I:)). is a monoid with itself is t h e identity itself t o be a bijective function; hence P P S ( R ) 1 Suppose instead t h a t f(x)c: E PPs(R). Then since f(x)c$ is a bijection of a finite set, we see t h a t for some n t h e n-fold composition of f(x)c: with itself is t h e identity function. X+I$ hence x is among t h e preimages of P")(x) under c: 1 This shows t h a t P P S ( R ) E {f(x)e: T h e identity function in F,(R) is clearly : 3 n P")(x) and we see f(n) (x) E x (mod x (mod I:)). To see t h a t (ii) is a restatement of (i), notice t h a t c: T h u s we have (i). has kernel 1: as a ring homomorphism. 0 Lemma 1.2. Suppose for R, R', both S-algebras, we have t h a t E PP,(R'). Proof: From Lemma 1.1 (ii) we see 12 = 1 2 . Then P P S ( R ) I P P ~ ( R )z {f(x) c s [ x ~ / I: ~3n f(")(x) Since 12 = 1 5 , we see I = x 1. {f(x) c S [ X I / I ~ : 3n f(")(x) i x) = { ~ ( x )E S[XJ/I$ : 3n f(")(x) ,x}, and applying Lemma 1.1 (ii) again we see I {f(x) E S [ X I / I ~: 3n f(")(x) hence PP,(R) E PP,(R'). = x) 2 P P ~ ( R / ) ; 0 T h e next result is somewhat more substantial and completes the tools t o make good on my boast in Section 0 t o reduce the problem of computing arbitrary finite S-algebras t o the commutative case. Theorem 1.1. Let R be an S-algebra, let J be a compositional attractor of Six], and let T = S[X]/I:. Then (i) 1; is a compositional attractor of S[x]. (ii) A = S[x]/J is an S-algebra with 12 = J . (iii) PPS(R) E PPS(T). Proof: Let f(x)eIg and let g(x) ES[X]. By definition feg is the zero function on R. Since c g = 0 o (gc;) = 0. This means (fog) E ker(c2) viewed as an algebra homomorphism; hence (fog) E 12, and is a monoid homomorphism, it follows that (fog)€: we see t h a t = (fc2)o(grg) 12 is a compositional attractor. Notice that the scalar multiplication of S on A is induced by the scalar multiplication of S on S[x]. definition of Now suppose f(x) E 12. Then Vg(x)+J e S[x]/J; we see from the 12 that f(g(x)+J) = 0. If we expand f(g(x)+J), we see that this implies t h a t f(g(x)) e J . Specialize g(x) t o x and note f(x) c J ; hence 12 C J. Now, recalling the definition of compositional attractor, we see for f(x) c J and any g(x) E S[x], that f(g(x)) e J ; hence f(g(x)+J) = 0 in A, and thus 3 C 1;. Combining the two previous inclusions, we see 1; = J. Finally, set J = I;, so A = T Then (ii) tells us t h a t 1; = .:I Then by Lemma 1.2 we see t h a t PPs(R) S PPs(T). Notice t h a t while my primary reason for proving this theorem is t o allow calculations for a noncommutative R t o take place in the commutative domain s[x]/I;, this theorem potentially allows me t o use other special properties of S[x] besides commutativity. Additionally, part (iii) makes it meaningful t o speak of the permutation polynomials t h a t arise modulo a compositional attractor, a s in Lemma 1.1. I will conclude this section with the following corollary, which ilustrates the breadth of Theorem 1.1. Corollary 1.1. An ideal J of S[x] is a compositional attractor iff there exists R, an Salgebra, so t h a t J = I;. Proof: (*) Set R = S[x]/J and apply Theorem 1 (ii). (+)Theorem 1 (i). 92 Lifting and Decomposition Lemmas. In this section I will give a lemma that allows the computation of the permutation polynomials of R from the permutation polynomials of R modulo its Jacobson Radical. For R with nontrivial direct product decomposition, I will give a sufficient condition to induce a direct product decomposition of PPS(R). Lemma 1.3 (Lifting Lemma). R/J. Let J be a nontrivial nilpotent ideal of R and set A = Then for f(x) e S[X] we have that f(x)rz e PPS(R) iff f(x)r$ E PPs(A) and for each aeA, for each element j E J\(O), j.f'(a) has the same degree of nilpotency as j. Proof: First I claim that for any f(x)~S[x],f(x)c; is a function that preserves equivalence classes (mod I) for any ideal I of R. T o see this, let P E R ,~ E and I compute f(r+j)-f(r) = j.i'(x)+j2.$f"(x)+.. . E I. With this claim we can now prove the lemma. (j) Since f(x)r: PPS(A). is 1:l on R, the claim forces f(x)r$ t o be 1:l on A; hence f ( x ) r $ E Suppose there exist j E J\{O), a c A so that j.f'(a) has a higher degee of = r+J. Set o = f(r+j)-f(r) = j.f'(r). nilpotency than j. Well, then a f(x)#PPS(R/<o>). Since f(x)c! is 1:1 on R, the claim forces f(x)rR'<s"' Then t o be 1:1, a contradiction, and the right implication is finished. (e) Suppose for r, s E R that f(r) = f(s). Then from the claim we see that r = s (mod J). From this we see there exists some j E J so that s = r+j. So f(r)-f(r+j) which a simple computation shows is equivalent t o the statement, Since, by hypothesis, j.f'(r) has the same degree of nilpotency as j, it follows that j.i'(r) + -(j2.$i"( r)+...) , = 0, unless j=0. From this we see that r = s; hence f(x)c: c PPS(R). Lemma 1.4. (Decomposition Lemma). Suppose that R = R1@R2 is a direct product decomposition of R. Then (i) If I :and 1: are relatively prime ideals in S[x], then R R PPs(R1) R (ii) 1: = In: I PPs(R1) @ PPs(R2), 2, and R (iii) both (i) and (ii) may be applied inductively t o arbitrary finite direct products. Proof: (i) Since I: R R and 1: are relatively prime, we see that the Chinese Remainder Theorem gives us an S-algebra isomorphism 2 ;-+ s [ x ] / I ~ . R R A: S[X]/I @ S[x]/I R Notice that ( x + I ,: R x+I s 2 ) ~ = x+1$; hence the characterization of permutation polynomials given in Lemma 1.1 (ii) and the fact that the polynomial composition involved is a combination of addition and multiplication of the sort preserved by A, tell us t h a t X is a bijection of PP,(Rx) C3 PPs(R2) = PPs(R) t h a t preserves the group operation. (ii) Clearly a polynomial in S[x] is zero everywhere on R when and only when it is zero everywhere on R1 and R2. (iii) Follows by induction. $3 Properties of Compositional Attractors. Compositional attractors are central t o the study of permutation polynomials over finite rings. As we saw in Section 1 many different S-algebras can have the same permutation polynomials exactly a s they share the same S-zeroing ideal. In this section I will develop a few properties of compositional attractors. Notice t h a t any ideal of S injected in the natural fashion into SIX] is a compositional attractor of S[x], with the corresponding group of permutation polynomials, as in Lemma 1.1, being the trivial group {x). Such a compositionql attractor is called trivial; all others are called nontrivial. As we saw in the comments subsequent t o Theorem 1, each compositional attractor I of SIX] has a permutation polynomial group attached to it, acting on the elements of S[x]/I. I will introduce the shorthand Gs(I) := PPs(S[x]/I) for this group. Lemma 1.5. Suppose t h a t I, J are compositional attractors of S[x]. Then IflJ and I.J, their intersection and product, are also compositional attractors. Proof: Elementary calculation. Lemma 1.6. Suppose t h a t I is a compositional attractor of S[x] and t h a t n : S + T is a ring homomorphism with i : S[x] -r T[x] being the natural extension of rr t o polynomials. Then i i is a compositional attractor of T. Proof: Polynomial composition is a combination of multiplication and addition of ring elements by one another o r by powers of t h e variable, all operations preserved by iT, hence r preserves composition of polynomials. O Lemma 1.6 raises t h e natural question: Is there any connection between t h e groups of permutation polynomials GS(I) and G T ( 1 7 ) ? T h e answer is yes, as demonstrated in t h e following lemma, which implies the existence of a functor from t h e category of Salgebras t o t h e catgory of groups. Lemma 1.7. Let S, T , x , ii, be as above and set R = S[x]/I and A = T[x]/ITi. Then there is a well-defined m a p p: Fs(R) - FT(A) induced by iit h a t agrees with T s o as t o make f ( x ) ~ r $ = f ( x ) ~ ; and ~ which has t h e additional property t h a t w = pl ~ ~ ( is1 a) group homomorphism of G,(I) with G,(A). Proof: A Since I is a compositional attractor, Theorom 1 (ii) tells us t h a t ker(c2)ii = ker(cT). This is sufficient t o show t h a t p exists. Since p agrees with ?i and 7 preserves polynomial composition, we see t h a t p is a monoid homomorphism of FS(R) into FT(A). A monoid homomorphism necessarily induces a group homomorphism on t h e groups of invertible elements; hence w exists a s specified. Example 1.2. Let S = Z 2, T = Zp, and let r be t h e natural m a p with kernel < p > . P - z2 I52 If we take I , then Lemma 1.7 tells us there is a group homomorphism u : P P Z p2 z2 PPZp(Zp) given by f(x)+lZP p2 (Z 2 ) - + f(x)+IZzP . In plainer language, a polynomial over Z P t h a t permutes Z 2 , is (mod p) a polynomial over Zp t h a t permutes Zp. P P Results for Finite Fields and the Integers. §O Introduction and Summary. In this chapter I will discuss results where the coefficient ring is the integers. I refer t o such compositional attractors and permutation polynomials as scalar. In some cases I will give generalizations of results when such generalization is without cost. For example, the results o n prime finite fields, which I require for the integer case, can be done for all finite fields just as easily. Every finite ring with 1 clearly forms a 2-algebra and hence has scalar polynomial functions and scalar permutation polynomials. In Section 1 I will give a classification of all compositional attractors of GF(pn)[x], p prime, as well as several examples of attractors tied t o specific GF(pn)-atgebras. In Section 2 I will use the classification of compositional attractors t o give a complete list of orders of permutation polynomial groups with coefficients in GF(pn). In Section 3 I will address the question of compositional attractors of Z[x] in terms of compositional attractors of Z .[XI. P $1 Compositional Attractors of GF(P")[x]. In this section F = GF(pn), and let q = pn. Since F[x] is a principal ideal domain the search for compositional attractors in F[x] is reduced t o the problem of finding polynomials f(x) with the property f(x) I f(g(x)) for at1 g(x) rF[x]. This property has modest application t o factorization theory. One question of interest, for example, is to determine when a composition of irreducible polynomials is itself irreducible. As we will see this section tells us t h a t there are many instances when t h e composition of irreducibles is not irreducible. Theorem 2.1. A polynomial f(x)&F[x] generates a compositional attractor iff it is a ( product of least common multiples of polynomials of the form x '*- x). Proof: (e) Notice t h a t if Q = G F ( ~ ~ then ) , (xqk- x) generates ;1: hence by Lemma 1.5 all polynomials of t h e given form generate compositional attractors, as intersecting ideals is equivalent t o taking the least common multiple of their generators, and multiplying ideals is the same as multiplying their generators. (+) Let I = <c(x)> be a compositional attractor of F[x], set A = F[x]/I, and suppose t h a t f(x)&F[x] is irreducible so that f"(x) is the minimal polynomial of some a & A . Recall t h a t F[x] is a unique factorization domain. I claim t h a t for any irreducible g(x)&F[x] with degree dividing the degree of f(x), there exists aome P r A so t h a t gn(x) is t h e minimal polynomial of 8. To see this, notice t h a t if J = J(A) is the Jacobson radical of A, then A/J is a direct product of finite fields of characteristic p. Since f"(a) = 0, it follows t h a t f ( a ) r J. Now, since f(x) is irreducible it must be the minimal polynomial of an element of one component of the direct product; if not, f(x) would be the product of the minimal polynomials of elements in two different components and hence would not he irreducible. Let F he the component of the direct product A / J in which an element for which f(x) is t h e minimal polynomial lies. Then for any irreducible g(x) with degree dividing the degree of f(x), we know from the theory of finite fields that there is some y + J 6 F for which g(x) is the minimal polynomial. A quick calculation shows t h a t the set g ( y + J ) is all of J. Since f(o) has nilpotency n, it therefore follows t h a t for some choice of jcJ, g(y+j) haa nilpotency n ; hence P = y + j has minimal polynomial gn(x). Since I = ,:I it follows t h a t the minimal polynomials of all elements of A divide c(x). k Recalling t h a t xq - x is the product of all irreducibles of degree dividing k, once each, we see t h a t the claim shows t h a t c(x) must have the specified form, as the irreducibles of smaller degree in the divisor lattice occur, as divisors of c(x), a t least as often as those of larger degree, and as irreducibles of the same degree are forced t o occur the same number of times. Corollary 2.1. Suppose fix) generates a compositional attractor of F[x]. Then the following hold: (i) All irreducible divisors of f(x) having t h e same degree have the same multiplicity. (ii) If f(x) has a n irreducible divisor of degree d and multiplicity m, then all irreducible divisors of f(x) having a degree dividing d have a multiplicity equaling o r surpassing m. Proof: Elementary computations show this t o be simply a restatement of the preceding theorem. T h e following corollaries demonstrate a use for Theorem 2.1 outside the domain of permutation polynomials. Corollary 2.2. Suppose t h a t f(x)cF[x] is an irreducihle of prime degree r. Then if g(x)cF[x] is a polynomial of degree less than r, there must exist another irreducible h(x)cF[x] of degree q so t h a t f(x) I h(g(x)). Proof: (xqr- x) generates a compositionai attractor. Its divisors a r e exactly the irreducibles of degree r and 1. From Theorem 2.1 we see t h a t this means (x qr - x) ( ( g ( ~ ) ~g(x)). ~ Since g(x) has degree less than r, the composition of g(x) with one of the linear factors of (xqr- x) cannot produce a multiple of f(x); hence the composition of g(x) with some h(x) of degree r must have done so. C! One conclusion this corollary leads t o is t h a t for any irreducible of degree n, for each prime r > n , we find t h a t there exists at least one irreducible h(x) of degree r so t h a t h(g(x)) is not irreducible. Corollary 2.3. Suppose f(x) is an irreducible of F[x] of degree n. Then there exists some g(x) # x of degree less than n so t h a t f(x) I f(g(x)). Proof: For any g(x) # x, Theorem 2.1 implies xq-x I (&x)) 9 -g(x). If we set h(x) = '4 w,then Theorem 2.1 implies t h a t there exists g(x) so t h a t h(x) 1 h(g(x)). Since f(x) h(x).f(x) I h(g(x)).f(g(x)), we may conclude t h a t f(x) I f(g(x)). From this we see that f(x)lf(a.f(x)+g(x)); hence we may take g(x) t o have degree less than t h a t of f(x), without loss. Now I will give examples of compositional attractors tied t o various F-algebras. The first is taken from [9] and is the basic compositional attractor from which t h e others are built. k Example 2.1. If Q = G F ( ~ then ~ ) <xq - x > = IQ F. My second example is taken from [ l l ] . Example 2.2. If R = Fmxm then we see 1; = <ITm ( xq L- x)>. L = l For my third example, which is m y own and hence is stated as a lemma, I will use a t y p e of F-algebra fundamental t o t h e analysis of those permutation polynomial groups associated with compositional attractors of F[x]. Lemma 2.1. Suppose t h a t f(x) = fl(x)e1.f2(x)e2.....fk(x)ek is a factorization of f(x) E F[x] into powers of distinct irreducibtes. Then if A = F[x]/<f(x)> we see t h a t Proof: Notice t h a t since t h e various fi(x)'s a r e relatively prime t o one another, t h e Chinese Remainder Theorem tells us t h a t From this we can see t h a t the generator of 1: A. generators of the I; must be a common multiple of the i = 1...m, where Ai = F[x]/<Fi(x) multiple of all these generators is in ,I: A. remains t o show t h a t 1; ei >. Since the least common it follows t h a t it must be the generator. It is generated by To see this, apply Theorem 2.1. t h e coset of x, t h a t has Certainly there exists a n element in Ai; it is in fact as its minimal polynomial. generator t o divide the actual generator. This forces the putative It is easy t o see t h a t the Jacobson radical J(Ai) of Ai has generator fi(x); hence the maximum degree of nilpotency of a n element of J ( A i ) is ei. Since A i / J ( A i ) E G F ( q deg(fi(x)) ) we see t h a t all minimal polynomials of elements of Ai are powers of irreducibles of degree dividing the degree of fi(x). From the maximal degree of nilpotency argument, we see t h a t the power of an irreducible in a minimal polynomial need not exceed ei; hence the actual generator divides the putative generator, forcing them t o be one and t h e same. O $2 T h e Order of Finite Permutation Polynomial Groups with Finite Field Coefficients. In this section F = GF(pn), and let q = pn. At this point I a m ready t o tackle the problem of enumerating the permutation polynomial group associated with each compositional attractor of F[x]. Lemma 1.2 makes this equivalent t o computing the order of every finite group of permutation polynomials with coefficients in F. T h e first step is t o solve the problem for F-algebras t h a t are direct products of finite fields. At this point I would like t o recall the Artin-Wedderburn structure theorem for Rings. Theorem (Artin-Wedderburn). For a ring R t h e maximal nilpotent ideal J ( R ) of the ring is called its Jacobson Radical. T h e factor ring R / J ( R ) is a semisimple ring. In the case we are dealing with, R both finite and commutative, R / J ( R ) is the direct product of finite fields. T h e second step is t o employ Lemma 1.3 t o lift this result t o all F-algebras of the form F[x]/ <f(x)>, a t which point t h e title of the section is satisfied. Unlike other permutation polynomial groups, enumeration of the permutation polynomials of a finite F-algebra comprising a direct product of finite field is best done by computing t h e isomorphism type of the group. This process is a simple modification of work presented in [9]. Lemma 2.2(i) is entirely as presented in [9] except for a change of terminology, and is included for completeness and consistency. Lemma 2.2. Let Q = G F ( ~ ~ )Then . (i) PPF(Q) is the centralizer in PPQ(Q) of the Frobenius automorphism a: x (ii) P P F ( Q ) acts on all suhfields of Q containing F. xq. (iii) PPF(Q) acts on the sets Qd = { q t Q : q has a minimal polynomial of degree d). (iv) P P F ( Q ) is the internal direct product of its representation on the Qd's. Proof: (i) Suppose that f ( x ) + l z t PPF(Q). Then (f(x))' = (xfixi>g = xfiq~q.i = ~ f ~ x ~f(xq), " = SO all members of P P F ( Q ) centralize o. On the other hand, suppose t h a t f ( X ) + l z centralizes r. Since 12 = <xqk- x > . there is some unique representative, take it t o be f(x), with degree<qk of f(x)+12. Then f(x)' we set y = xq, we see t h a t this equality can be reformulated as g(y) = = f(xq). If k 9 -1 C (fi-fiu)yi = i=l 0 for all y in Q. Since g(y) has degree less than qk, it follows t h a t fi = fiu for all i, placing f(x) squarely in PPF(Q). (ii) This follows directly from the fact t h a t all subfields of Q contain F. (iii) This follows directly from the fact t h a t the partition of Q into the Qd's is induced by the subsets of Q t h a t are subfields containing F. (iv) Let Gd be the representation of P P F ( Q ) on Qg. (iii). Notice t h a t t h e characteristic function x Qd' d This notion is well defined by k, is in FF(Q). To see this, simply t a k e f(x) t o be xqk- x divided by each irreducible of degree d in F[xJ. Since d E k, f(x) F[x]. T h e resulting function is zero off Qd and equal t o the product of all elements of Q-Qd on Qd; hence x 9 d is a scalar multiple of f(x). Since f(x) E F[x], this scalar is in F; hence f(x)<Z = xQd. Once we have x.(1 -,yQd)+f(x).xQ xQddF[x] d we see that for f(x)+1:cPPF(Q), g(x) = is exactly the Qd-component of the permutation associated with f(x) on Qd and identity off Qd. Therefore, each element of P P F ( Q ) has unique internal decomposition into a product of elements from each Gd, giving the specified internal direct product. 0 T h e following lemma also appears with different language in [9]. As we will see subsequently, it has application t o all F-algebras t h a t are direct products of finite fields, not just extension fields. Lemma 2.3. Let Gd be the representation of PPs(Q) on Qd = {q&Q : q has minimal polynomial of degree d). Then Gd S Cd wr Sn(d), where ~ ( d )is t h e number of irreducibles of degree d in F[x], and wr denotes the wreath product. Proof: Since we know t h a t PPq(Q) contains all permutations of Q , we see from Lemma 2.2 t h a t G d is t h e centralizer in Sym(Qd) of t h e Frobenius automorphism a: x xq. From the theory of finite fields, we know t h a t t h e action of t h e Frobinius automorphism on Qd is the cyclic permutation of the x(d) sets of d roots of each irreducible of degree d in F[x]. T h e centalizer then clearly contains each individual cyclic action induced by a on t h e roota of some irreducible of degree d. A simple calculation shows t h a t any permutation centralizing u must normalize the group generated by these cycles; hence G d has a normal subgroup N comprising the direct product of a ( d ) cyclic groups of order d. Note t h a t Gd must contain a n y permutations t h a t swap sets of roots in a fashion consistent with t h e cyclic actions of u upon them. A simple calculation shows that these together with the members of N comprise all permutations t h a t commute with u. If (al a2 . . . ad) and ( b l b2 . .. hd) are respectively the cyclic actions on t w o sets of roots, then (al bl)(a2 b2) . . . (ad hd) is an involution in Gd. Clearly, the set of ail such involutious generates a symmetric group on the sets of roots of irreducibles t h a t form an S r(d)- complement t o N in G d r making Gd the semidirect product of N by S Notice that ~(d)' t h e stabilizer of a set of roots in this symmetric action centralizes those roots; hence Gd is a wreath product as specified in 131, page 33. O Theorem 2.2. Let A be an F-algebra that is a direct product of finite fields Then: (i) P P F ( A ) CZ Cd wr d l ki and where ~ ( d denotes ) the number of irreducibles of degree d over F. Proof: (i) Let Ad = { ~ E A : a has an irreducible minimal polynomial of degree d). Notice k. t h a t PPF(A) must act o n sets of the form A d n G F ( q '); hence the action of P P F ( A ) is completely determined by its action on t h e Ad's. G F ( ~ ~), ~we~ see ( t~h a~t as ) in 2.2(iv), By examining the finite field F = xAd E FF(A) and t h a t PPF(A) is therefore a direct product of its repreaentations on the Ad's. i claim further t h a t t h e action of PPF(A) o n Ad is completely determined by its action on any Qd = A,n k. G F ( q ') where d / ki. To see this, notice t h a t all such intersections a r e simply t h e set of all elements in t h e field extension G F ( ~ ~of ) F t h a t had minimal polynomials of degree d over F. Clearly, a polynomial permutes the set product of several such sets iff it permutes some one of them; hence the claim is true. With the claim we see, however, that the representation of PPF(A) on Ad is isomorphic t o the representation of P P ~ ( G F ( ~ * )on ) Qd, as in Lemma 2.3; hence the components of the direct product of (i) above have the specified form. (ii) T h e enumeration follows directly from the isomorphism type of t h e group. Corollary 2.4. Suppose t h a t f(x) E F[x] is a square free with irreducible divisors fl(x), f2(x), ..., fm(x) of degree dl, d2, ..., dm, and set A = F[x]/f(x). Then II (i) PPF(A) 2 C, wr s 1 some d i and n (ii) I P P ~ ( A = )~ sF's).*(s)! 5 1 some di di (iii) 1; = < L . C . M ( X ~ - x ) > . Proof: (i) Notice t h a t the Chinese Remainder Theorem tells us t h a t Apply Theorem 2.2 and we have (i). (ii) Follows from (i) by elementary counting. (iii) Note t h a t t h e putative generator of 1; is t h e least common multiple of the minimal polynomials of all elements of A. Since all members of 1: are common multiples of all minimal polynomials of elements of A, this suffices t o make it t h e generator of .1: 0 With Corollary 2.4 in hand, we are ready t o compute t h e order of PPF(A), where A is Fix] modulo any polynomial. T o d o this we will employ the lifting Lemma 1.3 from Chapter 1. Theorem 2.3. Suppose t h a t f(x) = fl(x)e1.f2(x)e2 . a factorization of f(x) .,. .fm(x)em ts into powers of distinct irreducibles of degree dl, d2, ..., dm, respectively, and let rd = max{ei : d deg(fi(x))). Then if A = F[x]/<f(x)>, S = {s : s divides some di}, T = { t e S : r t > l ) we have Prwf: As I will demonstrate, the three factors in the formula above are, respectively, the number of polynomial permutations of A modulo its Jacobson Radical, the number of Fpolynomial functions on A t h a t are also permutations of A modulo its Jacobson radical, and the fraction of those functions that are actually permutations of A. T o see t h a t the first two factors are correct is easy. If J ( A ) is t h e Jacobson Radical of A and s(x) = fl(x).f2(x). ... .fm(x), we see first t h a t J ( A ) = <s(x)>; hence A / J ( A ) ie isomorphic to an algebra of t h e form described in Corollary 2.4, and we have t h e first factor. If we t a k e t(x) t o be the product of all irreducibles in Fix] with degrees in S, then we see from Lemma 2.1 t h a t I = < t ( x ) > . All the F-polynomial functions on A that give permutations of A / J ( A ) are then of the form f(x)+t(x).r(x), f ( x ) + ~ ~ / : ( ~ t) P P ~ ( A / J ( A ) ) , (*I for some polynomial r(x) and further all such functions have a unique representative modulo t h e generator, g(x), of 1: (which, recall, is ket(r$)). A quick calculation shows t h a t t h e exponent of q in the second term is exactly degree(g)-degree(t) and hence gives t h a t maximum degree of I, so the second term is correct as there are q possible choices for each coefficient of r. T h e third term follows from the Chinese Remainder Theorem and the lifting lemma. Indeed, lemma 1.3 tells us t h a t a polynomial permutes A iff it permutes A/J(A), and t h a t the evaluation of its formal derivative a t any point cannot, by multiplication, increase the degree of nilpotency of any element of J(A). convince one t h a t J ( A ) = <t(x)>. A moment's thought will From this we see t h a t the second condition of the lifting lemma is equivalent t o the formal derivative a t each point being divisible by no irreducible whose degree is in T . Apply this t o (*) and we see t h a t for each a ( x ) ~ A we , want f)(a)+t(a).r'(a)+tl(a)r(a) to be divisible by no irreducible of degree d for which rd > 1. Notice that Corollary 1 implies that t(x) is a compositional attractor; hence t ( a ) is divisible by all such and the condition we wish t o satisfy is exactly f ( a ) + t l ( a ) . r ( a ) f b(a) simultaneously for all irreducibles h(x) with degrees in T. However, this is equivalent to insisting t h a t f)(x)+tl(x).r(x) not be a multiple of h(x). From t h e factorization of t(x), t h e product rule for derivatives makes it obvious t h a t t'ix) is relatively prime t o h(x) a n d the condition becomes t h a t r(x) not assume some one value modulo h(x). means t h a t exactly the fraction This ) of all polynomials modulo h(x) are ( I - * deg(h(x)) acceptable. Since the various irreducihles with degrees in T are all relatively prime. the Chinese Remainder Theorem tells us t h a t t h e fraction of polynomials acceptable modulo all possible irreducibles is simply the product of the fraction acceptable modulo each irreducible; hence t h e third term is correct. O Corollary 2.5. T h e formula given in Theorem 2.3 may be simplified t o Proof: Routine computation. $3Compositional Attractors of Z[x]. In this section we will develop some information about compositional attractors of the integers, setting the stage for Chapter three. Throughout the section p will he a prime, , n will be a positive integer, and Z will denote the ring Z / i p n > . Lemma 1.4 implies P t h a t the compositional attractors of Z[x] are built o u t of the compositional attractors of Z ,[XI for various integers n and primes p. Recall that Z ,[XI ( m > l ) is not a C F D or P P PID; hence the computations in this section will be both messy and farther from the main stream. I can't just say Ufrorn the theory of finite fields we see..." anymore. I will begin the section with a useful lemma that quantifies in some sense the degree t o which Zpm[x] fails t o be a PID. Lemma 2.4. Suppose t h a t I is an ideal of Z ,[XI, p prime so that t h e factor module F = P Z ,[x]/I is finite. Then P I = <fl(x), pe2.f2(x), ..., pek.fk(x)>, so t h a t (i) 0 = e l < e 2 < . . . < e k = m , (ii) = fk(x) ! fk-l(x) I ... I fl(x), (iii) each fi(x) is monic, and (iv) t h e generating set with its kth element deleted is a basis for I. Proof: Let G = {gl(x), g2(x), ...) be any generating set of I ordered so t h a t t h e p-part of the generators is nondecreasing and all possible p-parts of members of I are represented. Let G i = {geG : g has p-part pi}. Now for t w o polynomials with t h e same p-part, a greatest degree common divisor is a linear combination of those t w o polynomials with t h e coefficients being monic polynomials; simply compute t h e gcd of their primitive parts (mod p ) t o obtain such coefficients. From this we deduce t h a t there exists some g;(x) with p-part pi t h a t is a common divisor of all elements of Gi (mod pi+'). Thus {g;(x) : i = 1, ..., m) is a generating set of G. For G(x), q ( x ) , i<j, we compute a replacement for q ( x ) so t h a t the primitive part of the replacement for q ( x ) is a divisor of the primitive part of &(x). This is done by .. computing t h e quantity gcd(pJ-'&(x), g;(x)) as a linear combination with monic coefficients exactly as in the previous paragraph, and using this gcd as the replacement. From this we see some finite number of operations reduces the generating set t o a new set {gi*(x) : i = l , ..., m) which has the divisibility property on primitive parts of generators t h a t we want for (ii). In addition the reduction step did not change the pp a r t of the ith generator. Since F is finite we see t h a t the generator with the largest ppart is exactly gm*(x) = pm. Since F is finite we see that G contains primitive polynomials, hence gl*(x) is primitive. Next we must transform the generating set {gi*} into a generating set {gi(x)} so as t o make each %(x) a power of p times a monic polynomial, all without destroying the divisibility property. Certainly pm = g,*(x) is already gi(x) ( t h e transformation of g m f ( x ) is t o leave it alone). Suppose t h a t t h e leading coefficient of gi* does not have p-part pi. Then it is a multiple of the p-part of &+l(x), and as deg(gi+l) 5 deg(gi*(x)), we may subtract a multiple of gi+l(x) and obtain a replacement for gi"(x) with leading coefficent t h a t has p-part pi. Having done this we may then multiply by a well chosen unit (mod pm) and obtain &(x) with leading coefficient exactly i = 1, ..., m. Inductively, we obtain t h e desired gi(x), Since the reduction simply made each &(x) some combination of {gj* : j>i) we see t h a t the divisibility property is preserved. A t this point we must eliminate redundant members of the generating set. primitive part of &(x) divides the primitive part of &i+l(x), then g,+'(x) If the is a multiple of gi(x); throw it out. Let fi(x) be the i f h survivor of this elimination process on the gi(x). A t this point we see t h a t we have satisfied (i)-(iii). It remains t o prove (iv). e. Let hi(x) = p '.ii(x) and assume t h a t the generating set is not a basis. Then for some 1 < j 5 k, hj(x) is a linear combination of the other generators. Let (high degree) r(x) = C c i ( x ) . h i ( x ) , and 1 <J S(X) = C c i ( x ) . h i ( x ) , (high content) 1>J such t h a t h,(x) = r(x)+s(x). Notice t h a t fj(x) divides hi(x). By the divisibility property it also divides r(x); hence it must divide s(x). Also by the divisibility property, the ppart of s(x) is a proper multiple of the p-part of h j ( x ) This means that pC.hj(x) divides s(x) for some integer c 1 1. Let A be the companion matrix of hhl(x) over pm. Now, notice that A satisfies r(x). This means t h a t h,(A) = s(A). On t h e other hand, A is not a r w t of h,(x), so we have t h a t s(A) is a proper multiple of gi(kj), a contradiction, so the given generating set is minimal, and we are done. One consequence of this lemma is a statement about the form of compositional attractors over Z Corollary 2.6. P"' Suppose t h a t J is a compositional attractor of Z ,,[XI. Then J has a P basis {fl(x), pF2.f2(x). ...r ~ ~ ~ . f ~ ( x ) l ~ so t h a t (i) 0 = el<e2<...<ek=m, (ii) 1 = fk(x) / fk-l(x) I .. . I fi(x), all generate compositional attractors (mod p) (iii) and each fi(x) is monic. Proof: If we apply Lemma 2.4 to J , we obtain all of the above except the claim that each of the fi(x) is a compositional attractor. Let g ( x ) ~ Z.[xi have invertible leading coefficient. P Since J is a compositional attractor itself, we see for each i that By considering t h e powers of p and using t h e basis and divisibility properties, we see t h a t cj(x) = 0 for j < i. T h u s we see t h a t so fi(g(x)) cj(x).fj(x) (mod p), and fi(x) is a compositional attractor (mod p). 0 Corollary 2.6 tells us a form t h a t all compositional attractors of Z .[XI must have. P T h e next step is t o further tighten o u r understanding of which parameters of the form actually yield a compositional attractor. Lemma 2.5. Let J be a compositional attractor of Z ,,[XI, "t P A/(p), and take (f(x)) = I Then if A = Z .[x]/J, P let B = '. ZP 3 = (f,(x), pe2.f2(x), ..., pek.fk(x)) is a basis of t h e sort described in Lemma 2.4 and ~ ~ ( isx an ) irreducible power divisor of f(x), then rk(x) divides each fi(x), i < k , (mod p). Proof: Since B is a Zp-algebra, it follows t h a t f(x) is t h e least comman multiple of the minimal polynomials of all elements of B. If kk(x) divides f(x), then there is a n element o+(p) E B which has minimal polynomial g(x) divisible by L k (x). If rK(x), and hence e. g(x), fails t o divide some fi(x) (mod p), then p '.fi(a) f 0 (mod pn). This, however, violates a property bestowed on J by Theorem 1.1 (ii), giving a contradiction. I3 At this point I want t o highlight an obnoxious feature of arithmetic in Z ,[XI. If a P polynomial in Z ,[XI is congruent t o a polynomial t h a t can be factored (mod p), it need P not be itself reducible when n > l . Example 2.3. An irreducible polynomial of Z .[XI t h a t factors modulo p. P (i) p=2, n=2, f(x) = x2+2, f(0) = 2, f(1) = 3, f(2) = 2, f(3) = 3; hence f(x) is irreducible in Z4[x], yet f(x) (mod 2). X.X This situation is not irretrievable, however, as shown by the following lemma. Lemma 2.6. If f(x) E Z .[XI is irreducible, then it is congruent modulo p t o a power of P an irreducible element of Zp[x]. Proof: If f(x) is not congruent t o a power of an irreducible (modulo p) then is has a factorization, f(x) = a(x).b(x) (mod p) into relatively prime factors; this follows from t h e prime factor theorem for UFDs. In order t o prove the Lemma I will now construct a factorization for a n y f(x) over Z P . not congruent t o a power of a prime (mod p). Suppose t h a t a(x), b(x) E. Z .[XI are relatively prime modulo p so t h a t P f(x) = a(x).b(x)+p.q(x). Examine the product with undetermined coefficients c!(x): J (a(x)+p .c:(x)+p2.c:(x)+p 3 .cl(c)+ 3 ...), .~.).(~(x)+P.c~(x)+P~.c~(x)+~~.c~(x) which when expanded becomes a(x).b(x) + p.(ci(x).b(x)+c:(x).a(x)) + p2.(c:(x).c:(x)+c:(x).a(x)+c?(x).b(x)) + p 3 . ( c ~ ( x ) . c ~ ( x ) + c ~ ( x ) ~ c ~ ( x ) + c ~ ( x ) ~ a ( x ) + c ~ ( x ) ~ b.... (x))+ T h e fact t h a t a(x) and b(x) are relatively prime (mod p) allows us t o apply the Euclidean algorithm and obtain values for <(x) and cA(x), u p t o congruence (mod p ) , so, examining t h e above expression, we see t h a t we may obtain any possible value for the product (mod pi) without disturbing its value (mod pi-f). W e may in particular choose the coefficents so as t o obtain f(x) from the product, hence the lemma is true. 0 I want t o conclude this section with an example of compositional attractors of Z[x]. T h e entire thrust of Chapter 3 is t o develop t w o examples of compositional attractors of Z, those associated with Zn and with the mxm matrices over Zn. Example 2.4 . Suppose t h a t f(x)+(p) is the generator of a compositional attractor of Zp[x]. Then is certainly a compositional attractor of Z[x]. T o see this simply note t h a t f(g(x)) = r(x).f(x)+p.a(x) by hypothesis, which yields the identity f(g(x))k = (r(x).f(x)+p.a(x))k = k r(~)~f(x)~p~-~a(x)~~"', m=O and apply the identity t o each basis element. Example 2.4 is in fact simply an application of Lemma 1.5 t o the compositional attractor generated by f(x) and p. IChapterI T h e Groups P P Z n ( Z n ) and PPZn(Zmim). $0 Introduction and Summary. In Section 1, I will give a new proof of David Singmaster's result[4], t h a t there are exactly functions from Zn t o itself t h a t can be represented as polynomials in Zn[x], which is shorter t h a n t h e original and matches t h e notation used in t h e rest of this paper. Section 2, I will give a new form of t h e computation of a basis of 1"' Z' In In Section 3 I will compute exactly which polynomials over Zn a r e permutation polynomials, and I will give t h e size of PPZn(Zn). In addition, I will give some information about t h e isomorphism t y p e of PPZ,(Zn), establishing t h e isomorphism type exactly for n = 1, 2. In Section 4 zn I will compute a basis for t h e compositional attractor IZmxm. n compute t h e membership and order of t h e group P P Z (Znmxm). n In Section 5 I will A tool I have found t h a t leads t o shorter proof about polynomials (mod n) is the difference operator A, defined on any ring of polynomials over a commutative ring with 1, t o be For a n original treatment of t h e difference operator, see [I]. introduction t o A is in [2]. A more modern I will call a polynomial f(x)eZ[x] n-ish if it is a member of I.Z; Such polynomials are t h e preimages under t h e natural homomorphism ~ : Z [ x ] - r Z ~ (of x ]t h e residue polynomials of Zn. Residue polynomials of a ring a r e those polynomials having all elements of the ring ar, their roots (51. Throughout this chapter I will use falling factorial notation, In order to avoid confusion with the use of parentheses in standard exponents, a n exponent will denote a falling factorial only if it is completely enclosed in parentheses. T h e falling factorials a r e preferable t o the powers of x as a basis for t h e polynomials in some situations because of identities like t h e following [2]. First, and using (3.1) for a polynomial f(x) = .a + alx(') + ... + amx(m), it follows t h a t $1Singmasters Result. In this section I will re-prove D. Singmaster's 1974 result [4] t h a t the number of functions from Zn t o itself t h a t can be represented as polynomials is I later use this result t o compute IPP(Zn)I. Proposition 3.1. If f(x)cZ[x] is n-ish of degree k, then divides the content of f(x). Proof: T h e content of a polynomial is defined t o be the greatest common divisor of its coefficients when the polynomial is written with respect t o the standard basis, the powers of x. Notice t h a t the gcd of the coefficients does not change if t h e polynomial is rewritten in the descending factorial basis. Assume then t h a t f(x) is n-ish of degree k and that I t is trivial to ~ e teh a t A preserves n-ishness, so n divides Amf(0), which means by (3.2) t h a t n / a,m!. From this, we see t h a t )* 1 a,. Each m is less than o r equal t o k, so - I (n,m!) ---"-- for each rn; hence (n,k!) -...! II a,- for each m. As a result A divides the (n,k!) n (n,k!) content of f(x). A polynomial p(x)&Z[X] induces the function f, where f(x mod n) = p(x) mod n from Zn t o itself. This notion is well defined because members of Z[X] preserve congruence (mod n). Theorem 3.1. (D. Singmaster, 1974). T h e number of functions from Zn t o itself that can be represented as polynomials is Proof: To prove the formula I will produce a system of representatives for the equivalence classes of polynomials in Z[X]t h a t induce the same function over Zn and then compute its size. I claim t h a t t h e polynomials of the form -.&.- lk) a r e n-ish. For any integer a, alk) (n,k!lx is a product of k consecutive integers. An elementary result of number theory is t h a t k! divides the product of k consecutive integers so we see t h a t k!lalk) and hence n 1 lk) for each integer a. This proves t h e claim. oa From t h e claim one can see t h a t if a polynomial induces a function on Zn, then that same function is induced by a polynomial a. + alx + ... + a,lx"-l with its coefficients in t h e range 0 5 ak < 1One simply subtracts proper integral multiples of n-ish (n,k!). polynomials supplied by the claim, starting with those of highest degree and working down. Since we are bringing the coefficients into the correct range in descending degree order, the later corrections will not disrupt the earlier ones. Further, since n-ish polynomiale induce t h e zero function, subtracting multiples of them does not affect the function induced. Now let f(x) and g(x) be polynomials with their coefficients in the range specified above, and let p(x) = f(x) - g(x). Then if d = deg(p), one sees t h a t the leading coefficient of p(x) is strictly bounded in absolute value by -2(n,d!). This means t h a t -A(n,d!) 1 cont(p). Applying Proposition 3.1 we see t h a t p(x) is not n-ish. This means t h a t the set of all polynomials with coefficients in the specified range form the desired system of representatives. coefficient yields the desired formula. Counting the number of choices for each $2 A Basis for t h e Ideal I z n Z' Throughout this section I will use t h e notation I, for I Zn Z. I will s t a r t with a n interesting property of ~ ( n ) defined , t o be t h e least k for which n/k!; i.e., n(n) = min{k : n / k!), after which I will produce a slightly different version of t h e Niven and Warren (61 basis for t h e residue polynomials of Zn, which basis is also a minimal generating set for I,. ) necessary t o produce this basis, and it is also Information about t h e function ~ ( n is useful for t h e calculations in Section three. Some form of ~ ( n appears ) in 141, [5], and [6]. In [5] Kempner refers t o K as p, and m y definition and use a r e closer t o his than t o a n y other. I d o not use t h e symbol p s o as t o avoid confusion with t h e Mobius function, which pops up repeatedly in t h e generalization of this work t o t h e matrix case. In [6] Niven and Warren refer t o a closely related function t(k), which is in some sense a n inverse of ~ ( n for ) prime powers. In [4] Singmaster uses t h e notation n(m) in place of ~ ( n and ) then drops t h e argument and merely refers to t h e function as n. A quick pencil-and-paper method of computing ~ ( n for ) prime powers and a number ) on page 243 of [5]. As I will show below, of valuable special cases of ~ ( n appears ) all n. knowing t h e value of ~ ( n a) t prime powers rapidly gives one t h e value of ~ ( n for Proposition 3.2. For n (A. J. Kempner 1921) > 2, ~ ( n = ) m a x { ~ ( q ): q a prime power divisor of n). Proof: Assume t h a t n 2 2, and let d = max{n(q) : q a prime power divisor of n}. Then for each prime power divisor q of n, q / d ! and hence n/d!. On the other hand since for some divisor q of n, ~ ( q = ) d, it follows that x(n)>d, so ~ ( n = ) d. Notice t h a t ~ ( 1 )= 0 and that n(p) = p for p prime. Table 3.1 gives some provocative values of ~ ( n ) . Table 3.1 Values of n(n) n 32 n(n) 8 n ~(n) 8192 16 64 8 16384 16 128 8 32768 16 256 10 65536 18 512 12 1024 12 2048 14 4096 16 Now, instead of a basis for the Ideal of residue polynomials in Zn[x], as in [6], I will produce a basis for t h e ideal In in 21x1, which is a preimage under the natural map from Z[x] t o Z,[x] of Niven and Warren's basis. My proof produces the basis immediately for all n instead of producing it first for prime powers and then constructing a basis for general n from t h e prime power bases. Define: Theorem 3.2. Let In denote t h e ideal of n-ish polynomials in Z[x]. Then and further. this basis is minimal. = ( : k i n In t h e proof of Theorem 3.1, we saw t h a t each nk) generator of J n was n-ish; hence J n C I n . Let f(x) be a member of In with degree m, say. Let J, If k is t h e largest member of An less than m, then --&..- = - This is because the (n,m!) (n,k!)' members of An a r e exactly all those integers a for which a! contains a divisor of n that (a-l)! does not. Now, proposition 1 says t h a t 1 I cont(f). As a (n,m!) / cont(f), s o (n,k!) result there is a multiple of ~ . x ( of ~degree ) m with the same leading coefficient a s (n,k!) f(x). Subtracting this multiple gives us a new member f ( x ) of In having lower degree t h a n f(x) but congruent t o f(x) (mod J n ) . By induction on degree, it fottows t h a t ail members of In a r e congruent (mod J n ) t o 0 o r zeroth degree members of In, which are exactly t h e multiples of n. Since n = -.A- (O) is a generator of J n , it follows t h a t (n,~!)'" I n C J n , and all t h a t remains is t o show t h a t t h e basis is minimal. Notice t h a t t h e form of t h e generators given in Theorem 3.2 has a very nice property. T h e contents of t h e various generators and their primitive parts a r e both totally and strictly ordered by divisibility, with the two orderings running in opposite directions. S t a r t by ordering An = {kl > k2 > ... > kn} and let gi(x) = 1 . x (n,ki) (ki) . Assume t h e generating set is not a basis. Then for some j c A n , gj is a linear combination of the other generators. Let r(x) = C c i ( x ) . g i ( x ) , and C'J such that gj(x) = r(x)+s(x). Notice that x (k,) divides g,(x). By the divisibility property above, it also divides r(x): hence it must divide s(x). Also by the divisibility property, the content of s(x) is a proper multiple of the content of gj(x). This means that c.gj(xj divides s(x) for some integer c > 2. Now, notice that kj is a root of r(x). This means that gj(k,) = s(k,). On the other hand, kj is not a root of gj(x), so we have that s(kj) is a proper multiple of g,(k,), a contradiction, so the given generating set is minimal, and we are done. 0 Example 3.1. Generators for I12. 1128. (I12)The divisors of 12 are 1, 2, 3, 4, 6, 12. Consulting Table 3.1 we find that ~ ( d for ) each of these divisors is 0, 2, 3, 4, 3, and 4, respectively, so An = { O , 2, 3, 4). Applying Theorem 3.2, we get that 112 = (12, 6 ~ ' 2~ ~) '~x~( ~) ) )~, and hence that Z[x]/I12 2 Z12 x ZI2 x Z6 x Z2, M an abelian group. (Il2*) T h e divisors of 128 are 1, 2, 4, 8, 16, 32, 64, and 128. Consulting Table 3.1 we ) each of these divisors is 0, 2, 4, 4, 6, 8, 8, and 8, respectively, so An = find that ~ ( d for {0, 2, 4, 6, 8). Applying Theorem 3.2 we get that '128 = ( 128, 6 4 ~ ( ~1)6,x ( ~ ) , x")), and hence that Z[x]/IlZ8 E Z128 x ZlZ8 x Z64 x Z 6 4 ~ Z 1 6x Z16 x Z8 x Z8, M an abelian group. 53 T h e group PPZ,(Zn). In t h e name of legibility, I will refer t o PPZ,(Z,) and I will continue t o use t h e notation Infor 1"' Z' as PP(Z,) throughout this section. T h e first step in computing PP(Z,) is t o reduce the problem of finding t h e isomorphism type and generators for general n to t h e same problem for prime powers. I will then produce a surjective homomorphism . r : P P ( Z .)-+PP(Z and establish a necessary and sufficient condition for a P P polynomial over Z t o be a permutation polynomial. P Henceforth when I refer t o a permutation polynomial I will actually mean t h e equivalence class of all permutation polynomials t h a t induce t h e same permutation. Recall t h a t t h e residue polynomials of Zn[x] a r e those members of Zn[x] having each element of Zn as roots; they induce t h e zero function. T h e equivalence class of a given permutation polynomial f(x) over Zn is thus t h e set of sums of f(x) with a n y residue polynomial 151. This convention simplifies matters substantially, as it allows us t o treat composition of polynomials as t h e composition of t h e permutations they induce. Lemma 3.1. If n =q1.q2. ... .qm is a factorization of n into powers of distinct primes, then Proof: Let n: Zn[x] -+ Theorem. Zqi[x] be t h e ring isomorphism given by t h e Chinese Remainder Suppose t h a t (gl, g2, ..., g,) is an m-tuple of permutation polynomials in ~ z ~ ~ [ xThen ] . by applying the Chinese Remainder Theorem pointwise t o the functions induced on the Zails by the gi's, we get a 1:l function on 2,. the function induced on Z, by the preimage of (gl, gZ, ..., g,) This function is, however. under n. Now suppose Then the natural projection of this t h a t f(x)rZ,[x] induces a 1:l function on 2,. function onto the product of functions on the Z 's must yield 1:l functions, or we have "i a contradiction of the Chinese Remainder Theorem; hence the polynomial components of f i must be permutation polynomials. This shows t h a t PP(Z,)n = npp(Zai). It remains t o show t h a t a preserves group structure. Recall t h a t our group operation is composition of polynomials. A polynomial composition is a string of ring additions and multiplications, nothing more, a n d both these operations are preserved by i, a ring isomorphism. It follows that n preserves our group operation, and hence t h a t T restricted t o PP(Z,) is a group homomorphism. Since i is an isomorphism of finite rings, it preserves t h e size of a set and hence is a group isomorphism when restricted t o PP(Z,). T h e next lemma is trivial but has great utility. Lemma 3.2. , If rn 5 n and f(x)€PP(Z ,), then f(x) acts on the congruence classes of Z modulo P P t h e ideal generated by pm. Proof: Routine. Lemma 3.3. Fix n 2 2. Let n: Z[X]/I be the natural map. Then the map p that n P induces on PP(Z ,) is a group homomorphism o n t o PP(Z P P P" + Z[X]/I Proof: Since I C I the natural map n exists. Let f c P P ( Z ,,). W e know t h a t i induces pn- p P a 1:l function on Z Lemma 3.2 tells us t h a t f induces a well-defined function on P"' Z as well, and it is easy to see t h a t this function must also be 1:l. Since k e r ( r ) = P I we know t h a t the function induced by f on Z is equal t o the function induced by P P This means that i n induces a 1:l function on Z and hence t h a t fn on Z P P ., tmage(p) C P P ( Z .-I). P Since 5 is a ring homomorphism it preserves addition and multiplication. From this we see t h a t it must preserve polynomial composition, which is just a combination of additions and multiplications. This means t h a t p preserves polynomial composition, and hence is a group homomorphism, as specified. U T h e next lemma is a special case of Lemma 1.3. I give a difference theoretic proof, more in t h e spirit of this chapter, rather than refer t o Lemma 1.3. Lemma 3.4. Let n 2 2. Then f(x) c Z[x] induces a permutation o n Z P" iff f ( x ) has no roots (mod p), and f(x) induces a permutation on Zp,,-l. To prove this lemma, I need t o define t h e q-difference operator and make a claim about it. T h e q-difference operator Aq, which has the same domain as A, is defined by I claim t h a t if n is 2 o r more, then for f(x) in Z .[XI we have t h a t A n - l f ( ~ ) = P P pn-l.f'(x) (mod pn). A routine calculation shows this t o be so. Now, t h e proof of Lemma 3.4. Suppose t h a t f(x) induces a permutation on Z Lemma 3.2 tells us t h a t if P"' a ~ b + p n " then f ( a ) r f ( b ) (mod pn-I). Since t h e function induced by f(x) is injective, it (J) is a nonzero multiple of pn-l. Since f(b)- f(a) = ( A n_lf)(a) we P see t h a t A n_lf(x) is everywhere nonzero. By t h e claim this is equivalent to f'(x) having P no roots (mod p). As in t h e proof of Lemma 3.3, t h e fact t h a t f induces a 1:l function follows t h a t f(b)-f(a) on Z P . is sufficient for it t o induce a 1:l function on Z P ( e )Suppose t h a t f(x) induces a permutation on Z (mod p). Since f induces a 1:l function on Z function on each equivalence class of Z P" and t h a t f'(x) has n o roots P it suffices t o show t h a t f induces a 1:l P (mod p"'). Let A = {a, a+pn-I, ..., a + ( p - l)pn-'1 be one such equivalence class. Since f'(x) has n o roots (mod p), t h e claim tells us t h a t A n-lf(x) has no roots (mod P pn). On t h e other hand, t w o applications of t h e claim show us t h a t n-lf(x) = 0 P (mod $). F r o m this we can deduce t h a t for h, b+pn'l~ A, f(b)-f(b+pn-l) = k.pn-l for some kfO (mod p ) t h a t doesn't depend on t h e choice of b. This in t u r n shows t h a t f induces a 1:l function on A since A {f(a), f(a)+k.pn", ..., f(a)+(p-l).k.pn'lf, which a r e all distinct values (mod pn), as k is simply generating t h e additive group of Zp. 0 Corollary 3.1. Let f(x) E Z[x]. If f(x)+I E P PP(Z P then f(x)+l . E P P P ( Z .) for all n > 2 . P Proof: If f(x)+I is a permutation polynomial, it follows that it induces a 1:1 function on P A simple computation shows t h a t a pn-l-ish polynomial has a p-ish derivative; Z P hence for n>2, ( f ( ~ ) + ~ ( x ) )=' ?(x) (mod p) for any pn-l-ish polynomial g. By Lemma 3.4, fJ(x) has no roots (mod p) and hence neither does (f+g)'. Since g(x) is a residue polynomial over Zpn-l, it follows that f(x)+g(x) still induces a 1:l function on Z n-l, so P by Lemma 3.4, f(x)+g(x) is a permutation polynomial over Z for any pn-l-ish P" polynomial g(x). 0 Notice t h a t the corollary says for f E Z[x] and n > 2 if f(x)+I f(x)+I ,is in P P ( ZP), P . is in PP(Z ) then P P for any m>n. With t h e aid of Lemma 3.4 and Corollary 3.1 it is now possible t o prove that p is a surjective group homomorphism. Lemma 3.5. p : PP(Zp,) -+ PP(Z is surjective. P Prwf: First deal with the case 1123. Let f(x)+I be a permutation polynomial in P PP(Z and let g(x) = f(x)+I ,. Then by Corollary 3.1, g ( x ) € P P ( Z ,). From the P P P definition of p we see that g(x)p = f(x); hence p is surjective. Now take t h e case n=2. If we take some f(x)+Ip .s PP(Zp) a n d let g(x) = xfP).(l+f'(x))+f(x)+l 2, P I claim t h a t g(x) is a preimage of f(x) under p. A routine calculation with the product rule from [2] shows that g ' ( x ) ~ p - l (mod p); hence g1 has no roots (mod p). From (3.2) and the fact t h a t A preserves p-ishness, it follows t h a t x(") is p-ish. From this it follows t h a t g(x) = f(x) (mod p) and hence t h a t g(x) induces a 1:l function on Z since f P does. This means that g(x) satisfies the conditions of Lemma 3.4 and we may deduce t h a t g ( x ) t P P ( Z 2). O n the other hand, since x(') is a n element of Ip, it follows that g p P = f, from the definition of p. 0 Now we have the tools t o obtain results on the isomorphism type of P P ( Z ,). The P main task of this section is producing the isomorphism type and generators of ker(p). For n > 3 it turns o u t t h a t ker(p) is an elementary abelian p-group. A t the end of the I section I will give a formula for P P ( Z ), P I. As we saw in Example 1.1 all permutations of Zp a r e induced by polynomials in Zp[x]. This follows directly from the fact t h a t all functions from Zp t o Zp can be realized as members of Zp[x]. Another way to see this is the following remark. Remark 3.1 Let F be the finite field of order q. Then for each nonzero a&F,the polynomial f,(xj ~+xa~~~-~ 4 = is a permutation polynomial inducing the transposition (0a ) on F. As a kr2 varies through all of F, this gives us a set of transpositions t h a t generate Sym(F). In particular, this means PP(Zp) = Sp, t h e symmetric group on p letters. Now I want t o produce the kernel of p in the case where p : P P ( Z 2) + PP(Zp). It P turns o u t that t h e kernal of p is isomorphic to the direct product, p times, of the group of affine functions over Zp, {ax+b : a, b E Zp, a # 0). Lemma 3.6. If p: P P ( Z 2 ) + PP(Zp) then lker(p)l = [p.(p-1)] '. P Proof: T h e definition of p shows t h a t the elements of ker(p) are of the form x+f(x), where f(x) is pish. Theorem 3.2 tells us t h a t Ip has a minimal generating set {p, x fpf } and that I hk5 a minimal generating set {p2, p.x('), x ( ~ ~ ) ] From . this we can see that a P set of representatives for ker(p) is the set of all permutation polynomials over Z of the P form with the degrees and coefficients of r and s in the range 0 t o p-1. Now (+) clearly induces a 1:l function on Zp, t h e identity. By Lemma 3.4 we need only compute how many choices of r and s give (*) a rootless derivative (mod p). If we compute t h e derivative of ( t ) , we get s'(x)~~(~)+s(~)~[x(~)]'+p.r'(x)+~. Removing those terms t h a t are p-ish, we see t h a t ( t ) is a permutation polynomial if s(x).[x(P)]' + 1 # 0. A simple calculation shows t h a t [x'~)]' ZE (-1) (mod p), s o we need only have t h a t s(x) # 1 (mod p ) for all x. A trivial counting argument shows t h a t there a r e (p-1)' such functions on Zp. Since all functions from Zp t o Zp a r e induced by polynomials in Zp[x] of degree less t h a n p, we see t h a t there a r e (p-1) P choices for s. T h e choice of r is completely free among t h e p P polynomials t h a t can be substituted for r in ( t ) ; hence there a r e (p-1) P . p P permutation polynomials in ker(p). 0 Lemma 3.7. , T h e characteristic function , Y ( ~of ) t h e ideal ( p ) generated by p in Z is a polynomial P function. Proof: Notice t h a t ( p ) is exactly t h e set of nonunits of Z T h e n for each u&U, f(u) = 0. P"' Let U be t h e units of Z P , and f(x) = (x - u). u&U If a is a nonunit, then f(a) is t h e product of all the elements of U. This means t h a t t h e value o f f is a constant unit y on all of (p). Simply setting xCp)(x) = y - l f ( ~ )gives us t h e characteristic function of ( p ) as a polynomial. 0 Theorem 3.3. Let H be t h e group of affine functions from Zp t o Zp. Then PP(Z 2) Z H wr Sp. P Proof: Claim 1 : Let ( a . x + b ) c H. Then L: (a.x+h) /-t ~ ( ~ , ( x ) . ( a . xb+. p ) + ( l - ~ ( ~ ) ( x ) ) . x is an injective group homomorphism of H into P P ( Z 2) t h a t moves (p) and fixes P Zp-(p). Proof: By Lemma 3.7, (a.x+b)L is a polynomial. Routine computation then proves the claim. Now, conjugating HL by ( x + a ) gives us a copy of H t h a t moves a + ( p ) and fixes This yields p copies of H t h a t move mutually disjoint subsets of Z 2; P hence we have a p-fold direct product of H inside ker(p), call it K. By Lemma 3.6, order the rest of Zp. considerations force K t o be all of ker(p). Now, I will produce a complement t o K in PP(Z 2) t h a t is isomorphic t o PP(Zp). P Let R = {O, 1, . .., p-1) be a set of coset representatives for Z (mod p). P Claim 2 : For a E PP(Zp) there is some a * E P P ( Z 2), so t h a t P R such that a8 = b, we have ( a + ~ . ~ ) a= * b+c.p. = a and for a, b E Proof: Let a be a n y preimage of 8 under p and transform a into a * as follows. W e know - a ( a ) = al(a).cp where we saw in t h e proof of Lemma 3.4 t h a t ul(x).p is constant (mod p2) on a+(p). This means t h a t a(a+c.p) = b + k.p + cp.al(a). In t h a t a(a+c.p) claim 1 we showed there was a permutation t h a t fixed all points not in b+(p) and which had the property t h a t (b + k.p + cp.al(a)) (h+cp). Apply this permutation t o a and repeat the process for each member of R. T h e permutation you obtain in t h e end has t h e properties specified for a * . Using t h e claim it is easy t o see t h a t the set {a* : Z?cPP(Zp)} is a copy of PP(Zp) inside PP(Z *) that has trivial intersection with K; thus PP(Z *) is the semidirect P P product of K by PP(Zp). It remains t o show that the copy of PP(Zp) acts on K in the fashion necessary for a wreath product. T o see this, let Ha be a copy of H acting on a + ( p ) and let it E PP(Zp) take a t o b. Then H,"* = H,, by a simple computation, which is exactly what we need (31. Since PP(Zp) Z Sp, we have PP(Z 2) Z H wr Sp. 0 P Lemma 3.8. For n 2 3 , ker(p) = {x + f(x) : i(x) E I P Proof: Certainly ker(p) C {x + f(x) : f(x) E 1 Let f(x) E I A simple computation P P shows that f'(x) is p-ish; hence ( f ( x ) + x ) ' z l (mod p). Since f(x)+x induces identity on Z P Lemma 3.4 tells us that f(x)+x is a permutation polynomial. Lemma 3.9. Let n>3. Then ker(p) is an elementary abeiian p-group of order u(n) where v gives the size of a set of representative of I P mod I P"' Proof: , be the natural map. Notice t h a t the additive group G of I P P is abelian and t h a t for each frG, p.f = 0; hence G is an elementary abelian p-group. Let d [ x ] -r Z[x]/I Let 8: G -r ker(p) be defined by f@ t-, f(x)+x. I claim t h a t 6 is an isomorphism. By Lemma 3.8 8 is a bijection of G with ker(p), so I need only check that 8 preserves the group operation. Let f , g E G, with f(x) = zfi.xi. Then (fe)o(ge) = c fi.(x+g(x)Y + g(x) + X, = f'(x).g(x) + f(x) + g(x) + x, = f(x) + g(x) + x, (recall f ( x ) is p-ish) = (f+g)e. T h e fact that ff is an isomorphism gives ker(p) t h e desired size. 0 Corollary 3.2. Let n > 3 and let {qi(x) : L E I ) be the image under r of of t h e minimal generating set of I given in Theorem 2, with the generator of highest degree removed if its image P under n is 0. Then forms a minimal set of generators for ker(p). Proof: {xkqi(x) : i E I of I P O<k<p } is clearly a minimal generating set for the additive group and 0 is an isomorphism. 0 Lemma 3.10. For the function u, defined in Lemma 3.9, u(n) = p Kipn' for each n>3. Proof: B y looking a t representatives of I P mod I P"' we see that the following recursion holds: Check t h a t 4 8 ) = 4 and K ( ~ =~ 3) p for all odd p. Then the recursion telescopes, giving t h e desired formula. Theorem 3.4. O Size of P P ( Z ,). P (i) IPP(Zp)/ = p!. n- 1 C kbk) (iii) for n > 3 IPP(Z P,)I = p!.[p.(p-1)) P . pk=3 Proof: (i) follows from a remark. (ii) follows from (i) and Lemma 3.6. (iii) follows from (ii) and Lemma 3.10. zmy $4 Computation of the ideal 1 zn ' 2 zm;m zmxm In this section I will abbreviate 1 and 1 by the more wieldy notation I?. zn with the meaning of the abbreviation being implied by context. A basis for one of these ideals differs from the other only by the addition o r subtraction of pn. polynomial in Zn[x] m-matrix n-ish if it is a member of the ideal . :1 I will call a My goal in this chapter is t o create a basis for I 5 n d as a consequence, compute the number of scalar P polynomial functions from Zmim t o itself. For the case n prime, see[ll], and refer also t o Example 2.2. T h e first step is t o reduce the problem for general n t o prime powers, which is done exactly the way you would think. Lemma 3.11. Suppose that n = plel .p2eZ. ... .pkek is rs factorization of n into powers of distinct primes. Then Proof: Follows from the Chinese Remainder Theorem decomposition & Zmxm ei zm;m i=l and Lemma 1.4 (ii). Recall[ll] t h a t for p prime, ;1 = m 1 (11(xP - x)), o r r = l if we let A' = {f(x) E Zp[x] : f(x) an irreducible of degree L ) , then These characterizations both come from noting t h a t every polynomial of degree rn has a companion matrix in Zmxm, and taking the least common multiple of all such P . polynomials t o obtain a generator for I F . It is possible t o extend a weakened version of this technique t o Z P and t o obtain generators for I m P"' Lemma 3.12. Im is exactly the ideal of polynomials having each polynomial, of degree P" m or less, congruent modulo p t o a power of an irreducible of Zp[x], as a divisor. Proof: Lemma 2.6 says t h a t being divisible by any polynomial of degree 5 m is equivalent t o the putative condition for membership in I m It is easy t o see t h a t being divisible by P"' any polynomial in Z .[XI of degree m o r less is equivalent t o being divisible by all monic P polynomials of degree exactly m. Now let f(x)&Z , be a monic polynomial of degree m P and let A be the companion matrix of f(x). T h e ones t h a t appear above the diagonal of A ensure t h a t A satisfies no polynomial relation of degree less than m. By applying the division algorithm we see t h a t this forces each member of 1% t o be divisible by f(x). On P the other hand, polynomials divisible by all polynomiais of degree 5 m are certainly satisfied by each mxm matrix over Z P"' 0 Lemma 3.12 reduces the problem of finding 1% t o one of computing least common P multiples in Z , [XI. Unfortunately the usual definition of the leirst common multiple P with its intimations of uniqueness doesn't apply here. As it turns o u t we may be satisfied with least degree common multiples. First notice t h a t the problem may (must) be done separately, one irreducible at a time. I will follow the rough outlines of the technique used t o compute In in the first two sections of this chapter. Lemma 3.13. If f(x) I L ( x ) (mod ~ p) for an irreducible L ( x ) E Z ~ [ X of] degree d, then the degree of a monic common multiple of all members of Z congruent t o f(x) mod p P" equals or exceeds and t h e proof constructs a common multiple attaining t h e bound. Proof: This formula should be reminiscent of t h e one for the power of a prime dividing a factorial. When d = l it is exactly a comparison based on that formula. Now notice t h a t the degree of f(x) is exactly d.k. Each polynomial in Z , congruent t o f(x) (mod p) P differs from each other such polynomial by a multiple of p (by definition). Generalizing this one sees t h a t exactly the fraction of these polynomiais differs from f(x) by a multiple of p'. This is because each of the deg(f) coefficents, those other than the first, must all differ from t h e corresponding coefficient of f(x) by a multiple of pJ. This is the key t o constructing a polynomial t h a t attains t h e bound. Simply multiply sets of polynomials congruent t o f(x) (mod p) that complete equivalence classes (mod p), (mod p2), ... as often aa possible. This ensures t h a t you will arrive a t a set of polynomials so t h a t as many as possible differ from each possible divisor by t h e highest possible power of p. One then sees this process gives the stated bound. 0 Example 3.2 Z3-Jx] . Compute a least degree common multiple g(x) of all monic polynomials in congruent t o x2+x+1 (mod 2). T h e set of all such polynomials is of the form D = {x2+(2k+1)x+(2m+l) : O < k,m 515). Lemma 3.13 tells us t h a t we should be able t o d o the job with an 8 t h degree polynomial. It should be the product of four members of D t h a t sweep o u t an equivalence class (mod 4). So take With Lemma 3.13 in hand we can compute the degree of a least degree of a monic mmatrix pn-ish polynomial. Corollary 3.3. Let ~ ( d denote ) the number of irreducibles of degree d in Zp[x]. Then is exactly t h e least degree of a monic m-matrix p"-ish polynomial. Proof: Lemma 3.12 tells us t h a t we want every polynomial of degree 5 m congruent (mod p) t o a power of a n irreducible of Zp[x] as a divisor of our putative m-matrix pn-ish polynomial. This polynomial would then be t h e product, over t h e set of possible irreducibles, of least degree common multiples of all monic polynomials congruent (mod p) t o t h e highest power of the irreducible of degree not exceeding m. T h e sum and n(d) cover t h e set of possible irreducibles, and by Lemma 3.13, ~ ( d , is the degree of the required least degree common multiple; hence the stated degree is correct. 0 In the case of Z,, the factorial function handily captured the maximal degree of n- ishness one could expect from a polynomial. For the matrix case we need an analogous function. Corollary 3.4. Let p prime then if g f x ) is monic of degree d, then it is a t best, in the sense of division, m-matrix %,(d)-ish. Proof: T h e Chinese Remainder Theorem allows us t o find polynomiats simultaneously congruent t o a n y choice of polynomials modulo the assorted prime divisors of a given integer. T h e powers of the primes in the above formula are, by Corollary 3.3, exactly t h e best one could hope for, given the degree of the polynomial, hence the corollary is true. A t this point I want t o extend K,(~") t o nonprime powers. Recalling Proposition 3.2, it is no surprise t h a t I will lake n,(p Corollary 3.5 s,(n); k k ) : p a prime powet divisor of m (3.4) If g(x) is monic and rn-matrix n-ish, then its degree equals or exceeds further, a g(x) with degree exactly n,(n) can always be found. Proof: T h a t this degree is necessary follows from the definition of ~ ~ ( a n d ) Corollary 3.3. T h a t it is sufficient follows from the Chinese Remainder Theorem. T h a t the polynomial desired exists is a consequence of the constructive nature of Coroilary 3.3. 0 Corollary 3.6. ~ ~ ( =n ~) ( n ) . Proof: Routine computation. 0 A t this point I want t o take a detour off t h e road Leading t o t h e computation of generators for I m and take time o u t t o perform t h e obvious generalization of P" Singmaster's result from Section 1. Lemma 3.14. If q(x) is m-matrix n-ish of degree d, then n divides t h e content (a, a d d ) ) of d x ) . Proof: Suppose t h a t t h e lemma fails for some q(x). Then from (3.4) we deduce t h a t for . e = max{i : d > ~ , ( ~ ~ ) }Now . if some prime power divisor pk of n t h a t d < ~ , ( ~ ~ )Let for each such prime it was true t h a t pk-e divided t h e content of q(x), then t h e lemma would hold, s o assume without loss t h a t pk'e fails t o divide t h e content of q(x). Then for some j < k-e, we see t h a t q(x) = pj .s(x), where s(x) has some coefficient t h a t is Iterating t h e reduction of s(x) by appropriate members of ,:I the P generators given in Corollary 2.6, and multiplying by well-chosen powers of x, we may invertible (mod p"). produce a new polynomial H(x) s o t h a t pJ.8(x) is still m-matric pk-ish of degree less than o r equal to d , but t h e leading coefficient of H(x) is invertible modulo pk. By multiplying by a n appropriate unit of Z and reducing mod pk, we find t h a t we have a new P polynomial pJ.s*(x) t h a t is monic, m-matrix pk-ish, and of degree d o r less. From this we deduce t h a t q(x) must be m-matrix pk-j-ish, but since j < k-e, we have a contradiction of Corollary 3.3. D Theorem 3.5 The number of scalar polynomial functions from Zm:m t o itself is Proof: Corollary 3.5 and Lemma 3.14 imply that we may construct polynomials of degree d of the form sd(x) = (n. %m(d)) .fd(~) 1. with fd monic so t h a t the set S = sd(x) : d = l . 2, 3, ... { IS a generating set of IF. If we suppose t h a t this is not so, then there exists some f(x) that is m-matrix n-ish that has a nontrivial remainder r(x) when reduced modulo (S). This remainder must necessarily violate Lemma 3.14; hence no such f(x) exists. T h e set of nontrivial remainders modulo (S) is then a set of representatives of the distinct Zn-polynomial functions of Zmim. These nontrivial remainders can be taken t o he polynomials with n This together with the fact that (n* %m(d))' ODm(nm(n)) is a multiple of n shows the formula t o be correct. t h e coefficient of xd in the range O < c < W e a r e now ready t o produce a basis for IF. This will be done in a manner analogous to Theorem 3.2. First we need t o define A: and let q,(x; = {nm(d) : d ( n), k) denote some monic m-matrix $,(k)-ish see from Corollaries 3.3 a n d 3 . 4 t h a t such polynomials exist. Theorem 3.6 polynomial of degree k. We is a basis for :1 in Z[x]. Proof: Let J m n k) : kch!,)'. -- ( (n, ~ m ( k ).qm(x; ) ensures C ' ,that ?, ' J Then the choice of the scalar factor I T . Let f(x) be an element of :1 and assume by way of contradiction that f(x) / J g . If the degree and content of f(x) simultaneously exceed those of one of the generators of J F , we may take the remainder of f(x) divided by that generator, obtaining a member of I T that fails t o exceed the degree and content. Since the contents of the generators are ordered by divisibility in the reverse order of degree of the generators, we may in fact obtain a member of I t from f(x), simulaneously exceeding or equaling the degree and content of no generator of J?. This resulting polynomial = I T . It remains to show that the would, however, contradict Lemma 3.14, hence J: generating set is minimal. From Lemma 3.13 and the Chinese Remainder Theorem we see that we may assume without logs of generality that for kl, k2 E AT, kl<k2 order A& = {kl>k2>...>kC) generators. If t h e generating set given is not a basis, then for some i, gi(x) must be a and set gi(x) = qm(x; kl) I qm(x; kZ). Now n .q,(x; (ny $m(ki)) linear combination with polynomial coefficients of the others. Let ki), the various so that gi(x) = r(x)+s(x). Since the contents of the generators are ordered by n divides s(x) and (n. 3m(ki)) Likewise, since the primitive parts of the generators divide one another it divisibility in the reverse of their degrees, it follows t h a t hence r(x). follows t h a t q(x; ki) divides r(x). Since gi(x) is a scalar multiple of q(x; ki), we may conclude t h a t q(x; ki) divides s(x). Finally, since A: captures exactly t h e point when t h e content of an m-matrix n-ish polynomial must change to compensate for its degree, the divisibility ordering of the contents of the assorted generators is strict. From this we may deduce t h a t t h e content of s(x) is a proper multiple of the content of gi(x). T h u s for some constant C > 2 , there are a(x) and b(x) so t h a t 6i(x) = n q(x; ki+l)+C q(x; ki).b(x). (n. 3m(ki)) (n, %(ki)) (*) Now since the degree of q(x; ki+l) is strictly greater than q(x; ki), it follows t h a t the companion matrix A of q(x; kitl) satisfies q(x; ki+l) but not q(x; ki). Specialize (+) a t A, expand gi(x) and see t h a t we obtain the identity, Since integral matrices have integral determinants and the left side of the above expression is not zero, this is impossible; hence gI(x) is not a linear combination of the other generators. El 55. Membership and Enumeration of the Group PPZn(ZmEm). In this section I will apply the techniques and tools of the first t w o chapters to delineating and enumerating the Zn-permutation polynomials of the matrices over hn. In [8] 3. V. Brawley computes the order of P P m ( G F ( q ) ) and hence by specialization, PPm(Zp). T h e only material on the isomorphism type of PPm(Zp), of which I a m aware, appears in [8] and [S], and no attempt is made t o compute the structure of the group. As part of the proof of his formula for the order of PP,(GF(q)), Brawley gives an effective but tedious construction for members of the group; i.e., he can produce the polynomial associated with a given permutation of matrices if one exists, and I see no way of improving his technique. arbitrary polynomials. No test for membership in PPm(Zp) exists for In fact, the problem of determining membership other than by direct testing is the subject of ongoing research in the case m = l (see [i], Chapter 7). I wilt denote by pn the group homomorphism from P P m ( Z .) P induced by t h e (mod p) homomorphism as described in Lemma 1.7. t o PPm(Z P As always the Chinese Remainder Theorem allows us t o restrict our investigation of P P m ( Z n ) t o Z P" in t h e following fashion. If n = 91.42. ... .qr is a factorization of n into powers of distinct primes, then the Chinese Remainder Theorem implies I will continue t o use the notation I F for the ideal of m-matrix n-ish polynomials in Z[x] or Zn[x]. By a(n) I will denote the number of irreducible polynomials of degree n in I I T h e computation of P P m ( Z ,) breaks into three parts: n = l , n=2, and 1123. T h e P case n = l is done by Brawley in [lo] but is also a consequence of Example 2.2 and Corollary 2.5. For completeness I will restate Brawley's result here. Now, for the remaining cases we will need t o ascertain what t h e specialization of the lifting lemma is in t h e matrix case. This lemma is a consequence of Theorem 3, page 98, of [lo]. My proof is much simpler than the one given in [lo] as it avoids tensor products and ugly matrix arithmetic. This is a result of applying Theorem 1.1. Lemma 3.15 A polynomial f(x)&PPm(Z .) iff f(x)&PP,(Z P P (mod p) on ZmGm. and f ( x ) is root-free Proof: Set A = Z .[x]/Im P P"' and B = Z n-l[x]/t P P Then Theorem 1.1 tells us that f(x)&PPm(Zpn) iff f(x)&PPZ (A) and f(x)€PP,(Z P" iff f ( x ) c P P Z problem is reduced to finding when a member P P Z (B), so the pn-l P pn-l (B) lifts t o a member of - PEl, we see t h a t B is A modulo the nilpotent ideal J = P P Z "(A). Now since I m C I P I p F l taken modulo P" Im P"' This means t h a t we may apply Lemma 1.3. T h e question then becomes, when can ft(x), by multiplication, increase the degree of nilpotency of some element of A? I claim t h a t this happens exactly when f ( x ) is divisible (mod p) by any irreducible in 9, the set of all irreducibles of degree 1, 2, ..., m. Notice that nilpotent elements of A are exactly the cosets of polynomials simultaneously divisible (mod p) by all members of 3. t h a t t h e generators of I;, P k By examining t h e definition of K,(~"), it is easy t o see > 2 are in fact divisible (mod p ) by the square of each irreducible in 9; hence there exist elements of A whose degree of nilpotency can be increased by multiplicatiou by any polynomial congruent (mod p ) t o a multiple of a member of 3. By the same token, multiplication by a polynomial congruent (mod p) t o a multiple of a member of 9 is the only muftiplication capable of increasing the nilpotency of a member of .I; hence f'(x) must simply avoid having divisors (mod p ) in 9. T h e fact that minimal polynomials of matrices in Zmim are exactly products of members of 9 means t h a t this condition on f ( x ) is exactly equivalent t o being root-free on Zmbm. 0 With the correct version of the iifting lemma in hand, we have a test for membership in PPm(Z .). P W e may now proceed t o the enumeration for 1122. Theorem 3.7. T h e homomorphism pn is surjective, and the size of ker(pn) is given by (n=2) Set q = [y]+1, then IKer(p2)I = P 2p.(pm-1)/(,l) m (I -$)r(d), d=q and Proof: In the course of this proof I will compute the number of preimages under p , of an arbitrary element a ( x ) of P P m ( Z T h a t the number of preimages is independent of P the choice of t h e element suffices t o show t h a t p, is surjective. Let L(x) be the generator of I F given in Example 2.2. Recall t h a t p, is the restriction t o permutation given in Lemma 1.7. In polynomials of the natural map K : Zpn[x]/Ip", * Zpn-l[~]/I P the case (n=2) this means t h a t preimages of u(x) are all of the form with r(x) and s(x) having degree less than the degree of L(x) and coefficients in the range 0 5 c <p. This follows from the fact, given by Theorem 3.6 and routine computation, t h a t 2 Im, = ( L ( x ) ~ ,p.L(x), P ), P as ideals of Z[x]. W h a t remains then is t o compute how many choices of r(x) and s(x) actually yield a permutation polynomial under t h e auspices of Lemma 3.15. This amounts t o checking when a!+(x)' is root-free on Zm:m, or equivalently, when a:(x)' has no irreducible divisors of degree 1, 2, ..., m. Computing the derivative, we obtain Any multiple of p is m-matrix p-ish as is L(x) by construction; hence the terms involving p and L(x) are zero everywhere on Zmim. W h a t we need then is for the remaining terms t o be everywhere nonzero. T h u s a(x)'+r(x).ll(x) must have no irreducible divisors of degree < m. This, however, is a type of computation we have done before, in the proof of Theorem 2.3. There are p deg(L(x)) candidates for r(x) and, since ~ ' ( x )is constructively root-free on Zmim, r(x) must avoid a single value modulo each irreducible of degree 5 m t h a t can divide al(x). Happily, a f ( x ) cannot have irreducible divisors (mod p) of degree 5 [TI. Since L(x) is divisible by the square of such irreducibles and since a ( x ) is forced by Theorem 1.1 and Lemma 1.1 t o be a Zp-permutation polynomial of A = Zp[x]/(L(x)), we see Lemma 1.3 and the existence of the nilpotent ideal of A generated by t h e coset of the maximal square-free divisor of L(x) force o f ( x ) t o be root-free modulo such irreducibles. leaves us with the irreducibles of degree [:]+I This o r more. T h e Chinese Ftemainder Theorem tells us t h a t t h e constraints satisfied for each irreducible are independent; thus the fraction of viable candidates is the product of viable candidates modulo each irreducible. So of the possible choices for r(x), exactly t h e fraction of t h e possible choices allow t h e satisfaction of Lemma 3.15. There are also p Deg(L(x)) choices for s(x) all of which allow the satisfaction of Lemma 3.15; hence the total number of preimages of a ( x ) under p2 is Recall t h a t L(x) = n m k (XP - X), k=l SO Deg(L(x)) = p.- pk-l Plugging this into (+) gives t h e stated result for n=2. p-1 ' Now we turn t o the case 023. Notice, as in Lemma 3.10 for nl, t h a t the formula given in 3.8 for lker(pn)l is exactly the size of a set of representatives of :I modulo I P P or, in other words, exactly Iker(?f)I. This means t h a t every possible preimage of a Z P permutation polynomial of Z "',","? under t must be a Z ,-permutation polynomial of P Zmxm for each n>3. By Lemma 3.15 this is equivalent t o all possible preimages having P" ' a root-free formal derivative on Zmim, which, by an application of Lemma 3.15 with n=2, must he so. T h u s all preimages of permutation polynomials under t are in fact permutation polynomials themselves, and the formula given for n > 3 is correct. Cl Corollary 3.7. Let f(x)eZ[x]. If f(x)+Im P" E PPm(Zpn), 1122, then f(x)+(Ipmk) E P P m ( Z k ) for all k = 1, 2, .... P Proof: This is simply a restatement of a portion of the final paragraph of the preceding proof. Now I will wrap u p t h e chapter by bringing together the assorted information on the size of PPm(Zp.). previous one. Notice t h a t each of the formulas given below simply build on the Corollary 3.8 If q = [Y]+l, then the size of PP,(Z (i) fl ,) is Im/21 k"'k)x(k)!.n k= 1 (ii) P ((pk-l).(pk.f[m/kl-2) k=l fi k.(Im/kl-21 k= 1 P2~."m-1)fi"',fI and k=q (iii) fi k.(Im/kI-Z) k=1 k=1 P k=3 Proof: Follows from (3.6), (3.7), and (3.8). 0 In order t o give a sense of concreteness t o the above formulas, I will give, on the following page, the actual numbers involved for small values of the parameters. Appendix B contains the values of the special functions used. See also Appendix C. Table 3.2 Order of PP,(Z,). pE$Gi-] Applications and Topics for Future Work. $0 Introduction and Summary. This chapter is a potpourri of results related t o t h e main results of my thesis and a few applications of results, particularly Lemma 1.2. In Section 1 I will compute the permutation polynomials of the p-adic integers with p-adic coefficients. In Section 2 %I will compute t h e compositional attractors associated with t h e group algebras of finite fields over finite abelian groups. In Section 3 I will define multidimensional compositional attractors and give a list of topics for additional consideration. $1 T h e Permutation Polynomials of the p-adic Integers. In this section Zp will denote the p-adic integers and Z / n will denote the integers modulo n. T h e p-adic integers are the set of all series {ak : k > l ) so t h a t ak E Z / p k , and (4.1) ak+,Eak (mod pk). They are given the structure of a ring by {ak}+{bk} = {ak+bk), and Denote by nm the natural projection homomorphism from Zp t o Z I P m given by {ak) Let n z be the extension of nm t o polynomials. a,. With these definitions we may characterize the p-adic permutation polynomials of the p-adic integers. Theorem 4.1. Let s = 2 / p 2 , R = Zp. Then f ( x ) t P P R ( R ) iff f(x)n; c PPS(S). Proof: (a)Suppose t h a t f(x) c PPR(R). Then the function r t, f(r) is 1:1 on R and hence s t, f(x)z;(s) is 1:l o n S = Rnz (e) Suppose t h a t f(x)n; T h u s f(x)n; t PPS(S). c PPS(S). Then Corollary 3.1 says t h a t f(x)a;c PPRnm(Rnm) for all m 2 2. Assume then by way of contradiction t h a t for r, s c R, r # s but t h a t f(r) = f(s). Since r # s, there is some m so t h a t V 1 2 m, m,# sn,, but for each such 1, f(r)n, = f(s)n,, which contradicts the information yielded by Corollary 3.1. 0 I = r, so g(x) has the specified form when k = 0. Consider the case k>O. Notice t h a t if H is a subgroup of G, then F[H] is a subalgebra of R. From this we may deduce t h a t lF['"l F C - IF ~ . (4.3) From this we may deduce t h a t g(x) is in fact a multiple of f(x), as a P generates a subgroup of G of order s; hence R has a snbalgebra of the type treated in the case k=O, whose F-zeroing polynomials are generated by f(x). From the theory of finite fields we know t h a t each irreducible divisor of f(x) ha4 multiplicity 1, so from Corollary 2.1 we deduce t h a t g(x) is in fact a power of f(x). Finally, a computation shows t h a t 1.0 fails k t o satisfy f(x)P -1 ; hence f(x)' k I g(x). O Corollary 4.1. Let G = C n l x C n 2 x Cn, be a direct product decomposition of a finite abelian group into cyclic groups of order nl, n2, ..., ne, let ni = si.pki where p 1 si, let ri be the order of q mod si, and set R = F[G]. Then Proof: Notice t h a t R is the direct product of Cnl, Cn2, ..., Cnc, apply T h w r e m 4.2 t o each component of t h e direct product, and apply Lemma 1.4 (iii), recalling t h a t in F[x] the generator of the intersection of ideals is t h e least common multiple of t h e generators of the ideals. Corollary 4.2. Assume the hypotheses of Corollary 4.1 and let kl = k2 = ... = k, = 0. Then (i) PPF(R) n Cs s 1 some ri ST(,), and n (ii) I P P ~ ( R )= / s"(s).n(s)! s / some r.I Proof: Lemma 1.2 then says that Use Corollary 4.1 t o obtain 1:. Corollary 2.4 may be applied t o obtain the formulas given. Corollary 4.3. Assume the hypotheses of Corollary 4.1, let S be the set of all divisors of any ri, let T be those members of S dividing an ri for which ki>O, and let d, = maxi:' : s 1 ri}. Then Proof: Use Corollary 4.1 t o compute 1; , and use Lemma 1.2 t o allow you t o apply Theorem 2.3. Example 4.1. Let F = GF(2), G = C3, the cyclic group of order 3, and set R = F[G]. Then Theorem 4.2 says that IF = <x4-x>, and Corollary 4.2 says that PPF(R) C2x C2, the Klein-4 group. In fact, PPF(R) = {x, x + l , x2, and x2+l}. Exampie 4.2 . Let F = GF(3). G = Cb.and set R = FIG]. Then Theorem 4.2 says that F - < x 9 - x 3 >, and Corollary 4.3 says that /PPF(R)I = 1296 = 64 . $3 Questions for further study. Multivariate Compositional Attractors. A question I a m asked virtually every time I mention compositional attractors is "What happens when you use more variables?" My answer typically has been that things get messy, s o I haven't checked. T h e question, however, is a good one and in this section I will extend t h e definition of compositional attractors t o multivariable polynomial rings. A multivariate compositional attractor of t h e polynomial ring S[xl, x2, ..., xn] is an ideal I with t h e additional property t h a t for f c I and for gl, gZ, ..., g, we have t h a t f(gl, g2, ...1 gn) E 1. Compositional Attractors of the Integers. Something on my wish list is a classification of t h e compositional attractors of Z[x]. T h e techniques used to compute t h e compositional attractors for matrices over Z, generalize t o Zn algebras t h a t have t h e property t h a t every possible monic polynomial, u p t o some fixed degree, is a least degree monie polynomial satisfied by some member of t h e algebra. Algebras t h a t d o not have this property exist. To see this, notice t h a t Corollary 2.6 suggests a means of constructing them. Lacking some additional insight, I d o not at present have t h e tools to classify such compositional attractors. Public Key Cryptosystems. T h e second topic I would like t o study is t h e computational complexity of decomposing long period permutation polynomials into short period permutation polynomials. If the computational complexity of this process is high then the material from the first three sections of Chapter 3 may be used t o construct a public key cryptosystem. O n e would design the permutation polynomial separately mod each p, p2, p3, etc. dividing n t o obtain a long period permutation without any short cycles in its cycle decomposition. Locally, that is modulo each pk , one would invert the polynomial and then compose t h e inverses to obtain the secret decoding key. In conjunction with this it would be nice t o see if the number of nonzero coefficients of a permutation polynomial of Zn can be controlled "locally." For permutation polynomials over finite fields locating permutation polynomials with few nonzero coefficients is difficult[?]. Compositional Attractors of Nonabelian Group Rings. O n e of the nice things about t h e theory of compositional attractors presented herein is t h a t it lets computations o n nonabelian algebras take place in equivalent abelian settings. It would be nice, then, t o be able t o find which compositional attractors go with the various nonabelian group algebras. Factorization Theorems. O n e of the consequences of t h e material presented in Chapter 2 is a iarge number of global factorization properties of composed polynomials over finite fields. nice t o see if any additional juice could be squeezed o u t of this. It would be Explicit Examples of Polynomial Groups The Group Sym(GF(5)) Realized as Polynomials. Permutation Polynomial Permutation Polynomial 0 X (3 4) x3+2x2 t 3 x (2 3) X (2 4) 4x3+4x2+3x ( 1 2) x3+3x2+3x ( 1 3) 4x3+x2+3x ( 1 4) 4x3 (0 1) x3+x2+2x+1 (0 2) 4x3+3x2+2x+2 (0 3) 4x3+2x2+2x+3 (0 4) x3+4x2+2x+4 ( 1 2)(3 4) zx3 (1 3)(2 4) 3x3 ( 1 4)(2 3) 4x (0 1 x 3 4) 2x3+3x2+4x+1 (0 1)(2 3) 2x3+x2+x+1 (0 1)(2 4) 4x+1 (0 2)(3 4) 4x+2 (0 2)(1 3) 3x3+4x2+4x+2 (0 2)(1 4) 3x3+3x2+x+2 (0 3)(2 4) 3x3+x2+4x+3 (0 3 x 1 2) 4x+3 (0 3)(1 4) 3x3+2x2+x+3 (0 4)(2 3) 2x3+4x2+x+4 (0 4)(1 2) 2x3+2x2+4x+4 (0 4)(1 3) 4x+4 (2 3 4) 3x3+4x2+4x (2 4 3) 3x3+2x2+x ( 1 2 3) 3x3+3x2+x (1 2 4) 2x3+4x2+x (1 3 2) 3x3+x2+4x ( 1 3 4) 2x3+2x2+4x (1 4 2 ) 2x3+3x2+4x (1 43) 2x3+x2tx (0 12) 3x3+2x2+x+1 (0 1 3 ) zx3+1 (0 1 4 ) 3x3+x2t4x+1 (0 2 1) 3x3 t 2 (0 2 3) 2x3+3x2+4x+2 (0 2 4) 2x3+x2+x+2 (0 3 1) 2x"4x2+x+3 (0 3 2) 2x3+2x2+4x+3 (0 3 4) 3x3+3 (0 4 1) 3x3+4x2+4x+4 (04 2) 2x3+4 (0 4 3) 3x3+3x2+x+4 3 Permutation Permutation Polynomial (0 1)(2 3 4) (0 1)(2 4 3) 4x3+3x2+2x+ 1 (0 1 2)(3 4) (0 1 3 x 2 4) x3+4x2+2x+1 ( 0 14)(2 3) (0 2 1)(3 4) 4x3+2x2+2x+2 (0 2)(1 3 4) (0 2 4 x 1 3) x3+2x2+3x+2 (0 2)(1 4 3) (0 2 3 x 1 4) x3+3x2+3x+2 (0 3 1 x 2 4) (0 3 4)(1 2) 4x3+3x2+2x+3 (0 3)(1 2 4) (0 3 2 x 1 4) x3+2x2+3x+3 (0 3)(1 4 2) (0 4 1)(2 3) 4x3+4x2+3x+4 (0 4 3)(1 2) (0 4 x 1 2 3) 4x3+2x2+2x+4 (0 4 2)(1 3) ( 0 4 x 1 3 2) 4x3+4 ( 1 2 3 4) ( 1 2 4 3) 2x (1342) ( 1 3 2 4) 4x3+2x2+2x (1 4 3 2) (1 4 2 3) 4x3+3x2+2x (0 1 2 3) (0 1 2 4) ~ 3 + 1 (0 1 3 2) (0 1 3 4) x3+3x2+3x+1 (0 14 2) (0 1 4 3) (0 2 3 1) (0 2 4 1) (0 2 3 4) (0 2 4 3) (0 2 1 3) (0 2 1 4) (0 3 2 1) (0 3 4 1) (0 3 4 2) (0 3 2 4) (0 3 1 2) (0 3 1 4) (0 4 2 1) (0 4 3 1) (0 4 3 2) (0 4 2 3) (0 4 12) (0 4 1 3) Permutation Polynomial Permutation Polynomial (0 1 2 3 4) x+l (0 1 2 4 3) 3x3+4x2+4x+1 (0 1 3 4 2) 2x3+4x2+x+1 (0 1 3 2 4) 3x3+3x2+x+1 (0 1 4 3 2) 3x3+1 (0 1 4 2 3) 2x3+2x2+4x+1 (0 2 3 4 1) 3x3+x2+4x+2 (0 2 4 3 1) 2x3+2x2+4x+2 (0 2 1 3 4) 3x3+2x2+x+2 (0 2 4 1 3) x+2 (0 2 1 4 3) 2x3+4xZ+x+2 (0 2 3 1 4) 2 ~ ~ + 2 (0 3 4 2 1) 3x3+3x2+x+3 (0 3 2 4 1) 2x3+3 (0 3 4 1 2) 2x3+x2+x+3 (0 3 1 2 4) 2x3+3x2+4x+3 (0 3 1 4 2) x+3 (0 3 2 1 4) 3x3+4x2+4x+3 (0 4 3 2 1) x+4 (0 4 2 3 1) 3x3+2x2+x+4 (0 4 3 1 2) 3x3+x2+4x+4 (0 4 1 2 3) 3x3+4 (0 4 1 3 2) 2x3+3x2+4x+4 (0 4 2 1 3) 2x3+x2+x+4 The Stabilizer of 0 in PP(Z9). Permutation Polynomial Permutation Polynomial identity X ( 1 7) x5+x4+2x3+2x2+x (2 8) x5+2x4+2x3+4x2+x (5 8) x5+2x4+2x3+x2+4x (1 4) x5+x4+2x3+5x2+4x (2 5) x5+2x4+2x3+7x2+7x (4 7) x5+x4+2x3+8x2+7x (3 6) x5+x3+8x ( 1 4)(5 8) 2x5+x3+x ( 1 7)(2 5) 2x5+x3+3x2+x (2 8 x 4 7) 2x5+x3+6x2+x (1 7)(3 6) 2x5+x4+2x2+2x (2 8)(3 6) 2x5+2x4+4x2+2x (1 7)(2 8) h5+x 3+4x (4 7)(5 8) 2x5+x3+3x2+4x ( 1 4)(2 5) 2x5+x3+6x2+4x (3 6)(5 8) zx5+2x4+x2+5x (1 4)(3 6) 2x5+x4+sx2+5x (2 5 x 4 7) 2x5+x3+7x (1 4)(2 8) 2x5+x3+3x2+7x (1 7)(5 8) 2x5+x3+6x2+7x (2 5)(3 6) 2x5+2x4+7x2+8x (3 6)(4 7) 2x5+x4+8x2+8x (1 2)(4 5)(7 8) x3+x ( 1 4)(3 6)(5 8) zX3+zx ( 1 0 1 2 5)(3 6) 2x3+3x2+2x (2 8)(3 6)(4 7 ) (1 8)(2 7)(4 5) ( 1 5)(2 4)(7 8) (3 6)(4 7)(5 8) ( 1 8)(2 4)(5 7) Permutation Polynomial Permutation Polynomial (1 7 4)(2 5)(3 6) 2x5+ 2x4+x2+2x (2 5 8)(3 6)(4 7) 2x5+x4+5x2+2x ( 1 4 7)(3 6)(5 8) 2x5+2x4+7x2+2x ( 1 4)(2 8 5)(3 6) 2x5+x4+8x2+2x (2 8 5)(3 6)(4 7) 2x5+x4+2x2+5x (14 7)(2 5)(3 6) 2x5+2x4+4x2+5x (1 7 4)(2 8)(3 6) 2x5+2x4+7x2+5x ( 1 7)(2 5 8)(3 6) 2x5+x4+8x2+5x (1 4 7)(2 8)(3 6) 2x5+2x4+x2+8x ( 1 4)(2 5 8)(3 6) 2x5+x4+2x2+8x (1 7 4)(3 6)(5 8) 2x5+2x4+4x2+8x (1 7)(2 8 5)(3 6) 2x5+x4+5x2+8x (14 7)(2 5 8) 3x2+x (1 7 4)(2 8 5) 6xZ+x (1 4 7)(2 8 5) 4x (1 7 4)(2 5 8) 7x (1 4 7)(2 8 5)(3 6) x5+x3+2x (1 7 4)(2 5 8)(3 6) x5+x3+5x ( 1 4 7)(2 5 8)(3 6) x5+x3+3x2+8x ( 1 7 4)(2 8 5)(3 6) x5+x3+6x2+8x ( 1 5 4 8)(2 7) x5+2x4+x2+x ( 1 5 7 8)(2 4) x5+x4+2x2+x (1 8 4 2)(5 7) x5+2x4+4x2+x ( 1 8 4 5)(2 7) x5+x4+5x2+x (1 2 4 5)(7 8) x5+2x4+7x2+x ( 1 2)(4 8 7 5) x5+x4+8x2+x ( 1 8 7 5)(2 4) x5+2x4+x2+4x (1 8 7 2)(4 5) x5+x4+2x2+4x (1 2 7 8)(4 5) x5+2x4+4x2+4x ( 1 2 4 8)(5 7) x5+x4+5x2+4x (1 5 7 2)(4 8) x5+2x4+7x2+4x (1 5)(2 7 8 4) x5+x4+8x2+4x ( 1 2)(4 5 7 8) x5+2x4+x2+7x ( 1 2 7 5)(4 8) x5+x4+2x2+7x (1 5)(2 4 8 7) x5+2x4+4X2+7x (1 5 4 2)(7 8) x5+x4+5x2+7x (1 8)(2 7 5 4) x5+2x4+7x2+7x ( 1 8)(2 4 5 7) x5+x4+8x2+7x (1 8 7 5)(2 4)(3 6) 2x5+2x4+x3+x2+2x ( 1 8 7 2)(3 6)(4 5) 2x5+x4+x3+2x2+2x (1 2 7 8)(3 6)(4 5) 2x5+2x4+x3+4x2+2x (1 2 4 8)(3 6)(5 7) 2x5+x4+x3+5x2+2x (1 5 7 2)(3 6)(4 8) ~ X ~ + Z X ~ + X ~ + ~ X ~ + (Z1X5)(2 ( 1 2)(3 6)(4 5 7 8) 2x5+2x4+x3+x2+5x (1 5)(2 4 8 7)(3 6) 2x5+2x4+ x3+ 4x2+ 5x (1 5 4 2)(3 6)(7 8) 2x5+x4+x3+ (1 8)(2 7 5 4)(3 6) 2xS+2x4+x3+7x2+5x ( 1 8)(2 4 5 7)(3 6) 2x5+x4+x3+8x2+5x (1 5 4 8)(2 7)(3 6) 2x5+2x4+x3+x2+8x ( 1 5 7 8)(2 4)(3 6) 2x5+x4+x3+2x2+8x (1 8 4 2)(3 6)(5 7) h5+2x4+x3+4x2+8x (1 8 4 5)(2 7)(3 6) 2x5+x4+x3+5x2+8x (1 2 4 5)(3 6)(7 8) 2x5+2x4+x3+7x2+8x (1 2)(3 6)(4 8 7 5) 2x5+x4+x3+8x2+8x 7 8 4)(3 6) 2x5+x4+x3+8x2+2x ( 1 2 7 5)(3 6)(4 8) h5+x4+x3+2x2+5x 5x2+5x Permutation Polynomial Permutation Polynomial (157842) 2x5+2x3+x (157248) x3+3x2+x (187245) 2x5+2x3+3x2+x (184275) x3+6x2+x (127548) 2x5+2x3+6x2+x (187542) x3+3x2+4x (124578) x3+6x2+4x (124875) 2x5+2x3+7x (127845) x3+3x2+7x (154278) 2x5+2x3+3x2+7x (154872) x3+6x2+7x (184572) 2x5+2x3+6x2+7x (1 2 4 8 7 5)(3 6) 2X ( 1 5 4 2 7 8)(3 6) 3x2+2x (1 8 7 5 4 2)(3 6) x5+2x3+3x2+2x (1 8 4 5 7 2)(3 6) 6x2+2x (1 2 4 5 7 8)(3 6) x5+2x3+6x2+2x ( 1 5 7 8 4 2)(3 6) 5x (1 8 7 2 4 5)(3 6) 3x2+5x ( 1 2 7 8 4 5)(3 6) x5+2x3+3x2+5x ( 1 2 7 5 4 8)(3 6) (1 5 4 8 7 2)(3 6) x5+2x3+6x2+5x ( 1 5 7 2 4 8)(3 6) ( 1 8 4 2 7 5)(3 6) x5+2x3+6x2+8x / Appendix B1 Tables of special functions. The function x(d) is used to denote the number of irreducibles of degree d in GF(q). There is a well known formula for ~ ( d ) , where ~ ( k is ) the Mbbius function. A table of values for small values is given below. Table 3.1 gives several values for ~ ( n ) the , least degree of an n-ish rnonic polynomial in Z[x]. Below, values are given for nm(n), the least degree of an m-matrix n-ish polynomial. / Appendix C ] Certain Permutation Polynomial Groups In this appendix I want t o include some information about particular groups of permutation polynomials t h a t I have uncovered. Since t h e members of PPZ,(Z,) are polynomials of Zn, they preserve equivalence classes mod each divisor of n. If n = pk is a prime power, this means t h a t they live inside a group isomorphic t o Sp wr S p wr . . . w r Sp, t h e k-fold wreath product of t h e symmetric group on p letters. This pins down t h e structure of G = PPZ8(Z8). Theorem 3.4 says t h a t t h e size of G is 128, exactly the size of Z2 wr Z2 wr Z2, which itself contains a copy of G. Table 3.2 tells us t h a t PPZ(Z2) has size four. Pencil-and-paper examination of its action on t h e matrices reveals t h a t it has t h e structure of a Klein 4 group. was known t o Brawley[8]. This fact [ Referencences 1 [I] G. Boole, A Treatise on the Calculus of Finite Differences, Macmillan and co., London, 1872. [2] K. Miller, An Introduction t o the Calculus of Finite Differences and Difference Equasions, Dover Books, New York, 1960. [3] M. Aschbacher, Finite Group Theory, Cambridge University Press, Cambridge, 1986. [4] D. Singmaster, On Polynomial Functions (mod m), Journal of Number Theory 6 (1974), 345-352. [5] A. J. Kempner, Polynomials and their Residue Systems, Transactions of the American Mathematical Society 22 (1925), 240-266, 267-288. [6] I. Wiven and L. J. Warren, A Generalization of Fermat's Theorem, Proceedings of the American Mathematical Society 8(1957), 306-313. [7] R. Lidl and H. Niederreiter, Finite Fields, Ency. of Mathematics 20, Cambridge University Press, Cambridge, 1984. [8] J. V. Brawley, T h e Number of Polynomial Functions t h a t Permute the Matrices Over a Finite Field, Journal of Combinatorial Theory(A) 21 (1976), 147-153. 19) L. Carlitz and D. R. Hayes, Permutations with Coefficients in a Subfield, Acta Arithmetica XXI (1972), 131-135. [ l o ] J . V. Brawley, Polynomials Over a Ring T h a t Permute the Matrices Over T h a t Ring, Journal of Algebra. 38 (1976), 93-99. [ l l ] J . V. Brawley, L. Carlitz, and Jack Levine, Scalar Polynomial Functions on the nxn Matrices over a Finite Field, Linear Algebra and its Applications 10, (1975) 199-217. 1121 Hans Lausch, Winfried B. Mtlller, und Wilfried Nebauer, iiber die Struktur einer durch Dicksonpolynome dargestellten Permutationsgruppe des Restklassenringes modulo n, J. Reine Agnew Math. 261 : (1973) 88-99. [13] Wilfried Niibauer, o b e r Permutationspolynorne und Permutationsfunktionen fiir Primzahlpotenzen, Monatsh. f. Math. (Vienna) 69 : (1965) 230-238.