Enumerating permutation polynomials over finite fields by degree (Q1867467): 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 authors deal with the problem of enumerating such permutation polynomials having degree \(<q-2\). This is equivalent to counting the permutations \(\sigma\) of \(\mathbb F_q\) for which \(\sum_{c\in\mathbb F_q} c\sigma(c)=0\). Let \(N\) denote the number of permutations of \(\mathbb F_q\) satisfying this condition. By inclusion exclusion, \[ N=\sum_{S\subseteq\mathbb F_q} (-1)^{q-|S|}n_S \] where \(n_S\) is the number of mappings \(f\colon\mathbb F_q\to S\) with \(\sum_{c\in S} cf(c)=0\). Using an expression for \(n_S\) in terms of exponential sums, the authors then show that \[ |N-(q-1)!|\leq\sqrt{2e/\pi}q^{q/2}. \] A similar estimate for a prime \(q\) was determined, using a different method, by \textit{P. Das} [Finite Fields Appl. 8, 478--490 (2002; Zbl 1029.11066)].