The number of permutation polynomials of a given degree over a finite field (Q1867460): Difference between revisions

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 \textit{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 \textit{S. Konyagin} and \textit{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.