1. I want to argue that permutation polynomials of GF(q) with polynomial degree <= q*(1-1/ln(q)) are likely to be rare. So prize them when you find them. All functions mapping GF(q) into itself are polynomials of degree<q. There are q^q such functions. Assume nonrigorously that the q! ones which happen to be permutations (bijective maps) are randomly distributed within all functions. Since q! = q^q * exp(-q) = q^(q-q/lnq) approximately (crude Stirling formula) we see that the number of perm-polys living within the polys of degree<q-q/lnq, is expected to be <1. Of course, this probability model is largely bunk, e.g. A*x+B is a permutation-polynomial if A is nonzero, with degree=1. And Dickson found a parameterized family of degree-5 ones when q=+-2 (mod 5): x * (x^4 + B*x^2 + B^2/5) (and compose with linears ad libitum). Also x^k (for k odd) is a perm-poly if q-1 is not divisible by k. But still, presumably there must be some shred of validity to this, in which case there are not terribly many low-degree permutation polynomials in the sense that almost all of them have degrees>q*(1-1/lnq), which is nearly as high as degrees can get. ======== 2. I want to argue, again nonrigorously, that it is likely that Dickson's degree-5 guys (if & when they exist) and linears, suffice to generate all, or anyhow at least half, of all perm-polys via composition. Because: John D. Dixon: The probability of generating the symmetric group, Math. Zeitschrift 110,3 (1969) 199-205 http://link.springer.com/article/10.1007%2FBF01110210 John D. Dixon: The probability of generating the symmetric group, Electronic J. Combinatorics 12 (2005), #R56, pp. 1-5. showed (and the 2nd paper finds the asymptotic expansion of the probability; the first gave merely a quite weak lower bound) that 2 random elements of S[n] will generate the entire group, or its half-size subgroup (the even perms only) with probability-->1 when n-->infinity. So if we regard the Dickson degree-5 polynomials as "random enough" then the Dixon theorem would indicate they should generate everything. Then you'd get examples of most odd degrees easily for large q, but even (and unusual odd) degrees not so easily. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)