×

Permutation polynomials of degree 8 over finite fields of odd characteristic. (English) Zbl 1456.11227

A permutation polynomial (PP) over a finite field \(\mathbb{F}_q\) is a polynomial with coefficients in \(\mathbb{F}_q\) such that the function \(c\mapsto f(c)\) is a permutation of \(\mathbb{F}_q\). Clearly, if \(f(x)\) is a PP, then for any \(a,b\in \mathbb{F}_q^*\) and \(c,d\in \mathbb{F}_q\) the polynomial \(af(bx+c)+d\) is a permutation too. Up to such a linear equivalence, PP of small degree \(d\) have been completely classified in previous works. The first open case is \(d=8\).
It is well known that any PP over \(\mathbb{F}_q\) of relatively small degree with respect to \(q\) (roughly smaller than \(\sqrt[4]{q}\)) is indeed an exceptional polynomial, that is a PP over infinite many extensions \(\mathbb{F}_{q^s}\) of \(\mathbb{F}_q\). Exceptional polynomials have been completely classified if the degree is not a power of the characteristic. Therefore, for polynomials of whose degree is fixed and not a power of the characteristic, only a finite number of fields \(\mathbb{F}_q\) must be investigated in order to obtain the complete classification of PPs (for that degree).
Using a well known connection with algebraic curves, in [D. Bartoli et al., J. Number Theory 176, 46–66 (2017; Zbl 1364.11150)] exceptional polynomials of degree \(8\) over fields of characteristic \(2\) have been completely classified. Thus, to classify PPs of degree \(8\) in even characteristic, it suffices to search for non-exceptional PPs over \(\mathbb{F}_{2^r}\), with \(r\leq 9\).
The authors perform such an exhaustive search using the SageMath software running on a personal computer. In order to facilitate the computation and prune the search space, they use Hermite’s criterion to provide some conditions on the polynomial coefficients. The main result of this paper is that a non-exceptional PP of degree \(8\) over \(\mathbb{F}_{2^r}\) (with \(r > 3\)) exists if and only if \(r\in \{4, 5, 6\}\) and such polynomials are explicitly listed up to linear transformations.

MSC:

11T06 Polynomials over finite fields
11-04 Software, source code, etc. for problems pertaining to number theory

Citations:

Zbl 1364.11150

Software:

SINGULAR; SageMath
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Chahal, J. S. and Ghorpade, S. R., ‘Carlitz-Wan conjecture for permutation polynomials and Weil bound for curves over finite fields’, Finite Fields Appl.54 (2018), 366-375. · Zbl 1407.11136
[2] Cohen, S. D. and Fried, M. D., ‘Lenstra’s proof of the Carlitz-Wan conjecture on exceptional polynomials: an elementary version’, Finite Fields Appl.1(3) (1995), 372-375. · Zbl 0839.11063
[3] Decker, W., Greuel, G.-M., Pfister, G. and Schönemann, H., ‘Singular 4-1-2: A computer algebra system for polynomial computations’, 2019, https://www.singular.uni-kl.de.
[4] Dickson, L. E., ‘The analytic representation of substitutions on a power of a prime number of letters with a discussion of the linear group’, Ann. of Math. (2)11(1-6) (1896-1897), 65-120. · JFM 28.0135.03
[5] Ding, C. and Yuan, J., ‘A family of skew Hadamard difference sets’, J. Combin. Theory Ser. A113(7) (2006), 1526-1535. · Zbl 1106.05016
[6] Fan, X., ‘The Weil bound and non-exceptional permutation polynomials over finite fields’, Preprint, 2018, arXiv:1811.12631.
[7] Fan, X., ‘A classification of permutation polynomials of degree 7 over finite fields’, Finite Fields Appl.59 (2019), 1-21. · Zbl 1444.11238
[8] Fan, X., ‘Permutation polynomials of degree \(8\) over finite fields of characteristic \(2\)’, Preprint, 2019, arXiv:1903.10309.
[9] Fried, M. D., Guralnick, R. and Saxl, J., ‘Schur covers and Carlitz’s conjecture’, Israel J. Math.82(1-3) (1993), 157-225. · Zbl 0855.11063
[10] Hayes, D. R., ‘A geometric approach to permutation polynomials over a finite field’, Duke Math. J.34 (1967), 293-305. · Zbl 0163.05202
[11] Hermite, C., ‘Sur les fonctions de sept lettres’, C. R. Acad. Sci. Paris57 (1863), 750-757.
[12] Hou, X.-D., ‘Permutation polynomials over finite fields — a survey of recent advances’, Finite Fields Appl.32 (2015), 82-119. · Zbl 1325.11128
[13] Kemper, G., ‘The calculation of radical ideals in positive characteristic’, J. Symbolic Comput.34(3) (2002), 229-238. · Zbl 1010.13001
[14] Li, J., Chandler, D. B. and Xiang, Q., ‘Permutation polynomials of degree 6 or 7 over finite fields of characteristic 2’, Finite Fields Appl.16(6) (2010), 406-419. · Zbl 1206.11145
[15] Lidl, R. and Niederreiter, H., Finite Fields, 2nd edn, , 20 (Cambridge University Press, Cambridge, 1997). · Zbl 1139.11053
[16] Mullen, G. L. (ed), Handbook of Finite Fields, (CRC Press, Boca Raton, FL, 2013). · Zbl 1319.11001
[17] The Sage Developers, SageMath, the Sage Mathematics Software System, version 8.6, 2019, https://www.sagemath.org.
[18] von zur Gathen, J., ‘Values of polynomials over finite fields’, Bull. Aust. Math. Soc.43(1) (1991), 141-146. · Zbl 0711.11047
[19] Wan, D. Q., ‘A p-adic lifting lemma and its applications to permutation polynomials’, in: Finite Fields, Coding Theory, and Advances in Communications and Computing (Las Vegas, NV, 1991), , 141 (Dekker, New York, 1993), 209-216. · Zbl 0792.11049
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.