Enumerating permutation polynomials II: k-cycles with minimal degree

We consider the function mkðqÞ that counts the number of cycle permutations of a finite field Fq of fixed length k such that their permutation polynomial has the smallest possible degree. We prove the upper-bound mkðqÞpðk 1Þ!ðqðq 1ÞÞ=k for charðFqÞ4eðk3Þ=e and the lower-bound mkðqÞXjðkÞðqðq 1ÞÞ=k for q 1 ðmod kÞ: This is done by establishing a connection with the Fq-solutions of a system of equationsAk defined over Z: As example, we give complete formulas for mkðqÞ when k 4; 5 and partial formulas for k 6: Finally, we analyze the Galois structure of the algebraic set Ak: r 2003 Elsevier Inc. All rights reserved. 1