×

zbMATH — the first resource for mathematics

Enumerating permutation polynomials. II: \(k\)-cycles with minimal degree. (English) Zbl 1035.11062
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.

MSC:
11T06 Polynomials over finite fields
Software:
Maple
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Das, P., The number of permutation polynomials of a given degree over a finite field, Finite fields appl., 8, 4, 478-490, (2002) · Zbl 1029.11066
[2] J. Harris, Algebraic Geometry, A First Course, Graduate Texts in Mathematics, Vol. 133, Springer, Berlin, 1992. · Zbl 0779.14001
[3] Konyagin, S.; Pappalardi, F., Enumerating permutation polynomials over finite fields by degree, Finite fields appl., 8, 4, 548-553, (2002) · Zbl 1029.11067
[4] Levine, J.; Brawley, J.V., Some cryptographic applications of permutation polynomials, Cryptologia, 1, 1, 76-92, (1977)
[5] 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
[6] 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
[7] Lidl, R.; Müller, W.B., A note on polynomials and functions in cryptography, Ars combin., 17A, 223-229, (1984) · Zbl 0539.94018
[8] R. Lidl, H. Niederreiter, Finite Fields, Encyclopedia of Mathematics Applications, Vol. 20, Addison-Wesley, Reading, MA, 1983. · Zbl 0554.12010
[9] Malvenuto, C.; Pappalardi, F., Enumerating permutation polynomials I: permutations with non-maximal degree, Finite fields appl., 8, 4, 531-547, (2002) · Zbl 1029.11068
[10] Maple V Release 5.1 (1999), Waterloo Maple Inc. · Zbl 1066.65500
[11] G.L. Mullen, Permutation polynomials over finite fields, Finite Fields, Coding Theory, and Advances in Communications and Computing, Las Vegas, NV, 1991, Lecture Notes in Pure and Applied Mathematics, Vol. 141, Dekker, New York, 1993, pp. 131-151.
[12] Wells, C., The degrees of permutation polynomials over finite fields, J. combin. theory, 7, 49-55, (1969) · Zbl 0165.36701
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.