Enumerating permutation polynomials. II: \(k\)-cycles with minimal degree. (Q1418184)

Every permutation \(\sigma\) on the elements of the finite field \(\mathbb F_q\) (\(q>2\)) is uniquely represented by a polynomial \(f_\sigma\in\mathbb F_q[x]\) of degree \(\partial(f_\sigma)\leq q-2\). A lower bound for \(\partial(f_\sigma)\) is given by the number of the fixed points of \(\sigma\) (\(\sigma\not=\text{id}\)). In [Finite Fields Appl. 8, 531--547 (2002; Zbl 1029.11068)], the authors considered the problem of enumerating conjugated permutations on \(\mathbb F_q\) whose corresponding polynomials are of degree \(<q-2\). In this sequel, they turn particularly their attention to permutation polynomials with minimal degree. Let \(m_{[k]}(q)\) denote the number of \(k\)-cycles \(\sigma\) on \(\mathbb F_q\) for which \(\partial(f_\sigma)=q-k\), or equivalently, \(\sum_{c\in\mathbb F_q} c^i(c-\sigma(c))=0\) for \(i=1,\ldots,k-2\). The authors give the upper bound \[ m_{[k]}(q)\leq\frac{(k-1)!}{k}\;q(q-1) \] if \(\text{ char}(\mathbb F_q)>e^{(k-3)/e}\) and the lower bound \[ m_{[k]}(q)\geq\frac{\varphi(k)}{k}\;q(q-1) \] for \(q\equiv1\bmod k\) where \(\varphi\) denotes the Euler totient function. Their proof is based on the relation of \(m_{[k]}(q)\) to the number of solutions in \(\mathbb F_q^{k-2}\) of a system of equations defined over \(\mathbb Z\). The paper concludes with the computation of \(m_{[4]}(q)\) and \(m_{[5]}(q)\) (and \(m_{[6]}(q)\) in parts) by means of computer algebra.