The number of permutation polynomials of a given degree over a finite field. (English) Zbl 1029.11066

Every permutation on the elements of \(\mathbb F_q\) (\(q>2\)) is uniquely represented by a polynomial over \(\mathbb F_q\) of degree \(\leq q-2\). The author deals with the problem of enumerating such permutation polynomials by their degree.
Let \(N_q(d)\) denote the number of permutation polynomials \(f\in\mathbb F_q[x]\) of degree \(d\) satisfying \(f(0)=0\). Relating \(N_q(d)\) to the number of solutions of a system of linear equations over \(\mathbb F_q\), the author finds an expression for \(N_p(p-2)\) in terms of the permanent of a Vandermonde matrix. Asymptotic bounds then follow from an estimate for the permanent of a complex matrix given by H. Minc [Permanents, Addison-Wesley (1978; Zbl 0401.15005)]. It is shown that \[ |N_p(p-2)-(1-1/p)(p-1)!|\leq\sqrt{(p-1)(1+(p-2)p^{p-1})}/p. \] A similar estimate was determined, using a different method, by S. Konyagin and F. Pappalardi [Finite Fields Appl. 8, 548–553 (2002; Zbl 1029.11067)].
Furthermore, the author indicates how to generalize his result to permutation polynomials of arbitrary degree over prime fields.


11T06 Polynomials over finite fields
Full Text: DOI


[1] S. Konyagin, and, F. Pappalardi, Enumerating permutation polynomials over finite fields by degree, preprint, 2001. · Zbl 1029.11067
[2] Lidl, R.; Mullen, G.L., When does a polynomial over a finite field permute the elements of the field?, Amer. math. monthly, 95, 243-246, (1988) · Zbl 0653.12010
[3] Lidl, R.; Niederreiter, H., Finite fields, (1997), Cambridge University Press Cambridge
[4] Marcus, M.; Minc, H., Permanents, (1978), Addison-Wesley Reading
[5] Mullen, G.L., Permutation polynomials over finite fields, Finite fields, coding theory, and advances in communications and computing, (1993), Marcel Dekker New York, p. 131-151 · Zbl 0808.11069
[6] Shparlinski, I.E., Finite fields: theory and computation, (1999), Kluwer Academic Publishers Dordrecht · Zbl 0967.11052
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.