Full classification of permutation rational functions and complete rational functions of degree three over finite fields

Designs, Codes and Cryptography - Tập 88 - Trang 867-886 - 2020
Andrea Ferraguti1, Giacomo Micheli2
1Max Planck Institute for Mathematics, Bonn, Germany
2Mathematical Institute, University of Oxford, Oxford, UK

Tóm tắt

Let q be a prime power, $$\mathbb {F}_q$$ be the finite field of order q and $$\mathbb {F}_q(x)$$ be the field of rational functions over $$\mathbb {F}_q$$. In this paper we classify and count all rational functions $$\varphi \in \mathbb {F}_q(x)$$ of degree 3 that induce a permutation of $$\mathbb {P}^1(\mathbb {F}_q)$$. As a consequence of our classification, we can show that there is no complete permutation rational function of degree 3 unless $$3\mid q$$ and $$\varphi $$ is a polynomial.

Tài liệu tham khảo

Amadio Guidi F., Lindqvist S., Micheli G.: Full orbit sequences in affine spaces via fractional jumps and pseudorandom number generation. Math. Comput. 88, 2005–2025 (2018). Bartoli D., Giulietti M., Zini G.: On monomial complete permutation polynomials. Finite Fields Appl. 41, 132–158 (2016). Bartoli D., Giulietti M., Quoos L., Zini G.: Complete permutation polynomials from exceptional polynomials. J. Number Theory 176, 46–66 (2017). Bosma W., Cannon J., Playoust C.: The Magma algebra system. I. The user language. Computational algebra and number theory (London, 1993). J. Symb. Comput. 24(3–4), 235–265 (1997). Cannon J.J., Holt D.F.: The transitive permutation groups of degree 32. Exp. Math. 17(3), 307–314 (2008). Charpin P., Kyureghyan G.M.: On a class of permutation polynomials over \({\mathbb{F}}_{2^{n}}\). In: Sequences and Their Applications—SETA 2008, vol. 5203 of Lecture Notes in Comput. Sci., pp. 368–376. Springer, Berlin (2008). Charpin P., Kyureghyan G.: When does \(G(x)+\gamma {\rm Tr}(H(x))\) permute \({\mathbb{F}}_{p^n}\)? Finite Fields Appl. 15(5), 615–632 (2009). Cohen S.D.: Permutation group theory and permutation polynomials. In: Algebras and Combinatorics (Hong Kong, 1997), pp. 133–146 (1999) Fan X.: Permutation polynomials of degree 8 over finite fields of odd characteristic. Bull. Aust. Math. Soc., pp. 1–16 (2019). Fan X.: Permutation polynomials of degree over finite fields of characteristic 2. https://arxiv.org/abs/1903.10309 (2019). Gao S., Panario D.: Tests and constructions of irreducible polynomials over finite fields. In: Foundations of Computational Mathematics, pp. 346–361. Springer, New York (1997). Galois K.C.: Groups of cubics and quartics. https://kconrad.math.uconn.edu/blurbs/. Guidi F.A., Micheli, G.: Fractional jumps: complete characterisation and an explicit infinite family. arXiv:1805.11658 (2018). Guralnick R.M., Müller P., Saxl J.: The Rational Function Analogue of a Question of Schur and Exceptionality of Permutation Representations, vol. 773. American Mathematical Society, Providence, RI (2003). Guralnick R.M., Tucker T.J., Zieve M.E.: Exceptional covers and bijections on rational points. In: International Mathematics Research Notices (2007). Hulpke A.: Constructing transitive permutation groups. J. Symb. Comput. 39(1), 1–30 (2005). Konyagin S., Pappalardi F.: Enumerating permutation polynomials over finite fields by degree. Finite Fields Appl. 8(4), 548–553 (2002). Konyagin S., Pappalardi F.: Enumerating permutation polynomials over finite fields by degree II. Finite Fields Appl. 12(1), 26–37 (2006). Kosters M.: A short proof of a chebotarev density theorem for function fields. Math. Commun. 22(2), 227–233 (2017). Laigle-Chapuy Y.: Permutation polynomials and applications to coding theory. Finite Fields Appl. 13(1), 58–70 (2007). Lidl R., Niederreiter H.: Finite fields, vol. 20. Cambridge University Press, Cambridge (1997). Masuda A., Panario D., Wang Q.: The number of permutation binomials over \(f_{4p+ 1}\) where \( p \) and \(4 p+ 1\) are primes. Electron J. Comb. 13(1), 65 (2006). Mullen G.L., Panario D.: Handbook of Finite Fields. CRC Press, Boca Raton (2013). Mullen G.L., Shparlinski I.: Open problems and conjectures in finite fields. In: London Mathematical Society Lecture Note Series, pp. 243–268 (1996). Rivest R.L.: Permutation polynomials modulo 2w. Finite Fields Appl. 7(2), 287–292 (2001). Shparlinski I.E.: A deterministic test for permutation polynomials. Comput. Complex. 2(2), 129–132 (1992). Stichtenoth H.: Algebraic function fields and codes, vol. 254. Springer, New York (2009). Sun J., Takeshita O.Y.: Interleavers for turbo codes using permutation polynomials over integer rings. IEEE Trans. Inf. Theory 51(1), 101–119 (2005). Xu X., Li C., Zeng X., Helleseth T.: Constructions of complete permutation polynomials. Des. Codes Cryptogr. 86(12), 2869–2892 (2018).