Permutation group theory and permutation polynomials

This article is a very interesting and well written survey of some results about permutation polynomials over finite fields and how results about primitive permutation groups have been used in the theory. Recall that a polynomial over a finite field \(k\) is called a permutation polynomial if \(f(x)\) is a bijective function on \(k\). A polynomial over the finite field \(k\) is called an exceptional polynomial if it is bijective over infinitely many extensions of \(k\) (or equivalently a sufficiently large extension compared to the degree). There are other equivalent definitions over finite fields which extend the concept appropriately for infinite fields. Such polynomials have been studied for over century. The author points out that these properties can be translated to properties in a corresponding group and gives the corresponding group theoretic statement. This is done as follows: let \(f \in k[x]\) be separable (i.e. have nonzero derivative) of degree \(n\). Then \(k(x)/k(f)\) is a separable degree \(n\) extension of fields. Let \(A\) be the Galois group of the Galois closure \(L\). Then \(A\) is called the arithmetic monodromy group of \(f\). Let \(k'\) be the algebraic closure of \(k\) in \(L\) and let \(G\) be the normal subgroup of \(A\) which acts trivially on \(k'\). Then \(G\) is called the geometric monodromy of \(f\) and \(A/G\) is isomorphic to the Galois group of \(k'/k\). If \(H\) is the subgroup of \(A\) acting trivially on \(k(x)\), then \(A\) acts faithfully and transitively on the cosets of \(H\). Let \(\Omega\) denote this \(A\)-set. The property that \(f\) is a polynomial implies that \(A=HI\) where \(I\) is the inertia group of a point over \(\infty\) (also the fact that \(k(x)\) has genus zero has a group theoretic interpretation as well which we will not go into here). Exceptionality also has a group theoretic interpretation which is not so natural from a group theoretic point of view. The interpretation is that \(A\) and \(G\) have no common orbits on \(\Omega \times \Omega\) other than the diagonal (with the appropriate definition of exceptionality this is valid over any field). In particular, if \(A/G\) is cyclic (always true over finite fields), exceptionality is equivalent to saying that every element in the coset \(xG\) has a unique fixed point on \(\Omega\), where \(xG\) is a generator for \(A/G\). The author then goes on to discuss various families of exceptional polynomials. He mentions the cyclic polynomials (those equivalent to \(x^r\)) and Dickson polynomials. If \(f\) is a composition of polynomials over \(k\), then \(f\) is a permutation polynomial or exceptional polynomial if and only if each term is (this is not true for exceptional polynomials over infinite fields). So one reduces to the case when \(f\) is indecomposable over \(k\) or equivalently \(A\) is primitive on \(\Omega\). The Aschbacher-O'Nan-Scott theorem [see \textit{M. Aschbacher} and \textit{L. Scott}, Maximal subgroups of finite groups, J. Algebra 92, 44-80 (1985; Zbl 0549.20011)] shows that the structure of primitive permutation groups is quite restricted and many properties of them can be reduced to questions about finite simple groups. Using the classification of finite simple groups, one can then deduce many results about primitive permutation groups. The strategy of using group theory to obtain some interesting results about exceptional polynomials was used successfully more than thirty years ago -- see \textit{M. Fried} [On a conjecture of Schur, Mich. Math. J. 17, 41-55 (1970; Zbl 0169.37702) and Arithmetical properties of value sets of polynomials, Acta Arith. 15, 91-115 (1969; Zbl 0182.07502)] and \textit{S. Cohen} [The distribution of polynomials over finite fields, Acta Arith. 17, 255-271 (1970; Zbl 0209.36001)]. Of course, the classification of finite simple groups was not available then. This strategy was also employed by \textit{M. Fried, R. Guralnick} and \textit{J. Saxl} [Isr. J. Math. 82, 157-225 (1993; Zbl 0855.11036)] to determine the possible group theoretic configurations that arise for exceptional indecomposable polynomials. In particular, it was proved that any indecomposable exceptional polynomial \(f\) over a finite field \(k\) of characteristic \(p\) not \(2\) or \(3\) either has degree \(p^a\), or (up to a linear change of variables) is \(x^r\), with \(r\) a prime and \((r,|k|-1)\) or a Dickson polynomial of prime degree \(r\) with \((r,|k|^2-1)\). In recent work, Guralnick and Saxl have proved the same theorem for indecomposable exceptional polynomials over an arbitrary field (where the arithmetic condition on \(r\) has to be modified slightly). In characteristic \(p\) with \(p=2\) or \(3\), the same is true except that there are additional families of polynomials associated with \(G=PSL(2,p^a)\) for \(1 <a\), \(a\) odd and \(A\) the full automorphism group of \(G\). The degrees of these polynomials are \(p^a(p^a-1)/2\). It is not too difficult to deduce the existence of polynomials corresponding to these groups since \(A\) acts naturally on projective space over the field of \(p^a\) elements (if \(p=3\), one has to view this group acting on projective space over the field of size \(p^{2a}\)). It is more difficult to actually produce the corresponding polynomials. \textit{P. Müller} [in Finite fields: theory, applications, and algorithms (Las Vegas, NV, 1993), Contemp. Math. 168, 245-249 (1994; Zbl 0818.11047)] was the first to write down some explicit polynomials for the first case in characteristic \(2\) (of degree \(28\)). Also, in characteristic 2, \textit{S. D. Cohen} and \textit{R. W. Matthews} [A class of exceptional polynomials, Trans. Am. Math. Soc. 345, 897-909 (1994; Zbl 0812.11070)] and in characteristic 3 \textit{H. W. Lenstra jun.} and \textit{M. Zieve} [A family of exceptional polynomials in characteristic three, Finite fields and applications (Glasgow, 1995), London Math. Soc. Lecture Note Ser. 233, 209-218 (1996; Zbl 0871.11087)] wrote down some very interesting families of polynomials for all possible values of \(a\) and proved that they corresponded to these group theoretic configurations. In fact, in two recent papers by Guralnick-Zieve (Polynomials with monodromy \(PSL(2,q)\), preprint) and Guralnick-Rosenberg-Zieve (A new family of exceptional polynomials in characteristic \(2\), preprint), all such polynomials have been classified. Most of them are variations of the earlier ones (and are geometrically equivalent to the known examples). However, there is one totally new family in characteristic \(2\) (which cannot occur over the field of \(2\) elements). This leaves the exceptional polynomials whose degree \(n\) is a power of the characteristic \(p\). The result of Fried, Guralnick and Saxl showed that the corresponding group \(A\) is an affine group -- i.e. it has a normal elementary abelian subgroup \(N\) of order \(n\) and \(A=HN\) (semidirect product). There are two families of such exceptional polynomials known and are discussed in this article. In the first case \(H \cap G\) is cyclic and in the second case, \(H \cap G\) is dihedral. If \(n=p\), then all exceptional polynomials are easy to determine. In general, the problem seems quite difficult. Polynomials in the first family (called sublinear) are easy to construct because the groups embed in \(PGL(2)\) and so act naturally on projective space. The second family discussed in the final section of the paper was constructed by \textit{R. Guralnick} and \textit{P. Müller} [J. Algebra 194, 429-454 (1997; Zbl 0911.11049)]. These are of degree \(p^{2a}\) with \(p\) odd. With these examples at hand, one can classify all exceptional polynomials of degree \(p^2\). For the entire collection see [Zbl 0939.00025].

Recommendations

Cited in

(24)

This page was built for publication: Permutation group theory and permutation polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4495682)