Re: [math-fun] Characterizing polys which permute GF(p)
Applied Algebra and Number Theory edited by Gerhard Larcher, Friedrich Pillichshammer, Arne Winterhof, Chaoping Xing Cambridge University Press, 2014 contains a paper "Index Bounds for Value Sets of Polynomials Over Finite Fields" by Gary L. Mullen, Daqing Wan, and Quiang Wang with an extensive bibliography of references, many of them about permutation polynomials. With a reasonably clever search, Google Books will display enough of the paper to allow you to view the bilbiography for that paper. Hilarie
This is a very cool theorem: Supposedly (I don't have access to this paper), [Carlitz1953] proved for any finite field GF(q=p^n), q>2, the whole symmetric group is generated by the power map x->x^(q-2) and the linear polynomials over GF(q). Notice that this map takes any non-zero field element to its inverse, and hence is an involution. Carlitz, L. "Permutations on a finite field". Proc. Amer. Math. Soc. 4 (1953), 538.
We also have a theorem by Fryer (195?): The permutations in GF(p) x->x+1 and x->m*x^(p-2) [i.e., x->m/x] generate the full symmetric group when p=4n+1 and m is a square, or p=4n+3 and m is a non-square. and generate the alternating group when p=4n+1 and m is a nonsquare, or p=4n+3 and m is a square. Fryer, K.D. "Note on permutations in a finite field". AMS 195?
Perm polys can be recognized in polynomial time. Kayal, N. "Recognizing permutation functions in polynomial time.", 2004
Generated only the *alternating* subgroup. Let e(i)(x)=1-(x-i)^(p-1). This poly function e(i) over x maps i->1, everything else to 0. Then r(x)=2*e(0)-e(1)-e(2)+x does a rotation of 0,1,2, leaving the other elements stationary. By construction, r(x) is divisible by (x-1), since r(1)=0. {x,x+1,2*e(0)-e(1)-e(2)+x} generates the *alternating group* (group of even perms), for every odd prime p. By one of Dickson's theorems, r(x) is a Dickson/Chebyshev poly, but I haven't figured out which one yet. BTW, has anyone figured out the intuition behind why the Dickson (perm) polys are the Chebyshev polys ?
participants (2)
-
Henry Baker -
Hilarie Orman