Enumerating permutation polynomials. I: Permutations with non-maximal degree (Q1867466)

Every permutation \(\sigma\) on the elements of \(\mathbb F_q\) (\(q>2\)) is uniquely represented by a polynomial \(f_\sigma\in\mathbb F_q[x]\) of degree \(\leq q-2\). A lower bound for the degree of \(f_\sigma\) is given by the number of fixed points of \(\sigma\) (\(\sigma\not=\text{id}\)). The authors deal with the problem of enumerating conjugated permutations of \(\mathbb F_q\) whose corresponding polynomials are of degree \(<q-2\). This restriction is equivalent to \(\sum_{c\in\mathbb F_q} c\sigma(c)=0\). Let \(N_{\mathcal C}(q)\) denote the number of permutations of \(\mathbb F_q\) which are of cycle type \({\mathcal C}=[l_1,\ldots,l_k]\) (\(l_i>1\)) and satisfy this condition. The determination of \(N_{\mathcal C}(q)\) amounts to counting the number of roots with pairwise distinct coordinates of a homogeneous quadratic polynomial in \(l_1+\ldots+l_k\) variables. Extending studies by \textit{C. Wells} [J. Comb. Theory 7, 49--55 (1969; Zbl 0165.36701)], the authors prove formulas for \(N_{\mathcal C}(q)\) with \({\mathcal C}=[4],[2,2],[5]\). (Already while considering the latter type, the limits of the approach become obvious.) Furthermore, they give a recursive relation for \(N_{[2,2,\ldots,2]}(q)\) in case of even \(q\). In Section 5, the authors discuss their method for arbitrary cycle types. The resulting Proposition 5.1 states that the probability that a permutation of cycle type \(\mathcal C\) corresponds to a polynomial of degree \(<q-2\) does not depend on \(\mathcal C\) asymptotically and estimates it at \(1/q+O(1/q^2)\). This is contrary to the fact \(N_{[2]}(q)=0\) for all \(q\).