Permutation binomials over finite fields

Masuda, Ariane; Zieve, Michael

doi:10.1090/S0002-9947-09-04578-4

Permutation binomials over finite fields
HTML articles powered by AMS MathViewer

by Ariane M. Masuda and Michael E. Zieve PDF

Trans. Amer. Math. Soc. 361 (2009), 4169-4180 Request permission

Abstract:

We prove that if $x^m + ax^n$ permutes the prime field $\mathbb {F}_p$, where $m>n>0$ and $a\in \mathbb {F}_p^*$, then $\gcd (m-n,p-1) > \sqrt {p}-1$. Conversely, we prove that if $q\ge 4$ and $m>n>0$ are fixed and satisfy $\gcd (m-n,q-1) > 2q(\log \log q)/\log q$, then there exist permutation binomials over $\mathbb {F}_q$ of the form $x^m + ax^n$ if and only if $\gcd (m,n,q-1) = 1$.

References

E. Betti, Sopra la risolubilità per radicali delle equazioni algebriche irriduttibili di grado primo, Ann. Sci. Mat. Fis. 2 1851, 5–19. (= Opere Matematiche, v. 1, 17–27)
Franc Brioschi, Des substitutions de la forme $\theta (r)\equiv \varepsilon \left ({r^{n-2} + ar^{\tfrac {{n-3}}{2}}}\right )$ pour un nombre $n$ premier de lettres, Math. Ann. 2 (1870), no. 3, 467–470 (French). MR 1509672, DOI 10.1007/BF01448238
F. Brioschi, Sur les fonctions de sept lettres, C. R. Acad. Sci. Paris 95 1882, 665–669. (= Opere Matematiche, v. 5, 31–39)
L. Carlitz, Some theorems on permutation polynomials, Bull. Amer. Math. Soc. 68 (1962), 120–122. MR 141655, DOI 10.1090/S0002-9904-1962-10750-2
L. Carlitz and Charles Wells, The number of solutions of a special system of equations in a finite field, Acta Arith 12 (1966/1967), 77–84. MR 0204417, DOI 10.4064/aa-12-1-77-84
Leonard Eugene Dickson, The analytic representation of substitutions on a power of a prime number of letters with a discussion of the linear group, Ann. of Math. 11 (1896/97), no. 1-6, 65–120. MR 1502214, DOI 10.2307/1967217
S. G. Vlèduts and V. G. Drinfel′d, The number of points of an algebraic curve, Funktsional. Anal. i Prilozhen. 17 (1983), no. 1, 68–69 (Russian). MR 695100
Saïd El Baghdadi, Sur un problème de L. Carlitz, Acta Arith. 69 (1995), no. 1, 39–50 (French). MR 1310841, DOI 10.4064/aa-69-1-39-50
H. Halberstam and H.-E. Richert, Sieve methods, London Mathematical Society Monographs, No. 4, Academic Press [Harcourt Brace Jovanovich, Publishers], London-New York, 1974. MR 0424730
Ch. Hermite, Sur les fonctions de sept lettres, C. R. Acad. Sci. Paris 57 1863, 750–757.
Yasutaka Ihara, Some remarks on the number of rational points of algebraic curves over finite fields, J. Fac. Sci. Univ. Tokyo Sect. IA Math. 28 (1981), no. 3, 721–724 (1982). MR 656048
N. M. Korobov, An estimate of the sum of the Legendre symbols, Dokl. Akad. Nauk SSSR 196 (1971), 764–767 (Russian). MR 0274455
Yann Laigle-Chapuy, Permutation polynomials and applications to coding theory, Finite Fields Appl. 13 (2007), no. 1, 58–70. MR 2284666, DOI 10.1016/j.ffa.2005.08.003
Yu. I. Manin, What is the maximum number of points on a curve over $\textbf {F}_{2}$?, J. Fac. Sci. Univ. Tokyo Sect. IA Math. 28 (1981), no. 3, 715–720 (1982). MR 656047
A. Masuda, D. Panario, and Q. Wang, The number of permutation binomials over $\Bbb F_{4p+1}$ where $p$ and $4p+1$ are primes, Electron. J. Combin. 13 (2006), no. 1, Research Paper 65, 15. MR 2240771, DOI 10.37236/1091
Ariane M. Masuda and Michael E. Zieve, Nonexistence of permutation binomials of certain shapes, Electron. J. Combin. 14 (2007), no. 1, Note 12, 5. MR 2320592
É. Mathieu, Mémoire sur l’étude des fonctions de plusieurs quantités, sur la manière de les former et sur les substitutions qui les laissent invariables, J. Math. Pures Appl. (2) 6 1861, 241–323.
D. A. Mit′kin, Estimation of the sum of the Legendre symbols of polynomials of even degree, Mat. Zametki 14 (1973), 73–81 (Russian). MR 332794
D. A. Mit′kin, Existence of rational points on a hyperelliptic curve over a finite prime field, Vestnik Moskov. Univ. Ser. I Mat. Meh. 30 (1975), no. 6, 86–90 (Russian, with English summary). MR 0401644
Harald Niederreiter and Karl H. Robinson, Complete mappings of finite fields, J. Austral. Math. Soc. Ser. A 33 (1982), no. 2, 197–212. MR 668442, DOI 10.1017/S1446788700018346
J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64–94. MR 137689
Jean-Pierre Serre, Sur le nombre des points rationnels d’une courbe algébrique sur un corps fini, C. R. Acad. Sci. Paris Sér. I Math. 296 (1983), no. 9, 397–402 (French, with English summary). MR 703906
J.-P. Serre, Rational points on curves over finite fields, unpublished lecture notes by F. Q. Gouvêa, Harvard University, 1985.
H. M. Stark, On the Riemann hypothesis in hyperelliptic function fields, Analytic number theory (Proc. Sympos. Pure Math., Vol. XXIV, St. Louis Univ., St. Louis, Mo., 1972) Amer. Math. Soc., Providence, R.I., 1973, pp. 285–302. MR 0332793
Henning Stichtenoth, Algebraic function fields and codes, Universitext, Springer-Verlag, Berlin, 1993. MR 1251961
Karl-Otto Stöhr and José Felipe Voloch, Weierstrass points and curves over finite fields, Proc. London Math. Soc. (3) 52 (1986), no. 1, 1–19. MR 812443, DOI 10.1112/plms/s3-52.1.1
T. J. Tucker and M. E. Zieve, Permutation polynomials, curves without points, and Latin squares, preprint, 2000.
Gerhard Turnwald, Permutation polynomials of binomial type, Contributions to general algebra, 6, Hölder-Pichler-Tempsky, Vienna, 1988, pp. 281–286. MR 1078048
J. F. Voloch, On the number of values taken by a polynomial over a finite field, Acta Arith. 52 (1989), no. 2, 197–201. MR 1005605, DOI 10.4064/aa-52-2-197-201
Da Qing Wan, Permutation polynomials over finite fields, Acta Math. Sinica (N.S.) 3 (1987), no. 1, 1–5. MR 915843, DOI 10.1007/BF02564938
Da Qing Wan, Permutation binomials over finite fields, Acta Math. Sinica (N.S.) 10 (1994), no. Special Issue, 30–35. MR 1268257
Da Qing Wan and Rudolf Lidl, Permutation polynomials of the form $x^rf(x^{(q-1)/d})$ and their group structure, Monatsh. Math. 112 (1991), no. 2, 149–163. MR 1126814, DOI 10.1007/BF01525801
André Weil, Sur les courbes algébriques et les variétés qui s’en déduisent, Publ. Inst. Math. Univ. Strasbourg, vol. 7, Hermann & Cie, Paris, 1948 (French). MR 0027151
Umberto Zannier, Polynomials modulo $p$ whose values are squares (elementary improvements on some consequences of Weil’s bounds), Enseign. Math. (2) 44 (1998), no. 1-2, 95–102. MR 1643282