zbMATH — the first resource for mathematics

Enumerating permutation polynomials. I: Permutations with non-maximal degree. (English) Zbl 1029.11068
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 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\).

11T06 Polynomials over finite fields
Full Text: DOI
[1] Levine, J.; Brawley, J.V., Some cryptographic applications of permutation polynomials, Cryptologia, 1, 76-92, (1977)
[2] Lidl, R.; Müller, W.B., A note on polynomials and functions in cryptography, Ars combin., 17-A, 223-229, (1984) · Zbl 0539.94018
[3] 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
[4] Lidl, R.; Mullen, G.L., When does a polynomial over a finite field permute the elements of the field? II, Amer. math. monthly, 100, 71-74, (1993) · Zbl 0777.11054
[5] Lidl, R.; Niederreiter, H., Finite fields, encyclopedia of mathematics and its applications, (1983), Addison-Wesley Publishing Company Reading
[6] G. L. Mullen, Permutation polynomials over finite fields, in:Finite fields, coding theory, and advances in communications and computing, Las Vegas, NV, 1991, pp. 131-151, Lecture Notes in Pure and Applied Mathematics, Vol. 141, Dekker, New York, 1993.
[7] Wells, C., The degrees of permutation polynomials over finite fields, J. combin. theory, 7, 49-55, (1969) · Zbl 0165.36701
[8] C. Batut, K. Belabas, D. Bernardi, H. Cohen, and, M. Olivier, GP/PARI Calculator Version 2.0.14, 1989-1999.
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.