# zbMATH — the first resource for mathematics

Permutation binomials over finite fields. (English) Zbl 1239.11139
Summary: 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\geq 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$$.

##### MSC:
 11T06 Polynomials over finite fields
##### Keywords:
permutation polynomial; finite field; Weil bound
Full Text:
##### References:
 [1] 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) [2] Franc Brioschi, Des substitutions de la forme \?(\?)\equiv \?(\?$$^{n}$$$$^{-}$$²+\?\?^\tfrac\?-32) pour un nombre \? premier de lettres, Math. Ann. 2 (1870), no. 3, 467 – 470 (French). · doi:10.1007/BF01448238 · doi.org [3] F. Brioschi, Sur les fonctions de sept lettres, C. R. Acad. Sci. Paris 95 1882, 665-669. (= Opere Matematiche, v. 5, 31-39) · JFM 14.0098.01 [4] L. Carlitz, Some theorems on permutation polynomials, Bull. Amer. Math. Soc. 68 (1962), 120 – 122. · Zbl 0217.33003 [5] 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. · Zbl 0147.04003 [6] 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. · JFM 28.0135.03 · doi:10.2307/1967217 · doi.org [7] S. G. Vlèduts and V. G. Drinfel$$^{\prime}$$d, The number of points of an algebraic curve, Funktsional. Anal. i Prilozhen. 17 (1983), no. 1, 68 – 69 (Russian). [8] Saïd El Baghdadi, Sur un problème de L. Carlitz, Acta Arith. 69 (1995), no. 1, 39 – 50 (French). · Zbl 0812.11068 [9] H. Halberstam and H.-E. Richert, Sieve methods, Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], London-New York, 1974. London Mathematical Society Monographs, No. 4. · Zbl 0298.10026 [10] Ch. Hermite, Sur les fonctions de sept lettres, C. R. Acad. Sci. Paris 57 1863, 750-757. [11] 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). · Zbl 0509.14019 [12] N. M. Korobov, An estimate of the sum of the Legendre symbols, Dokl. Akad. Nauk SSSR 196 (1971), 764 – 767 (Russian). [13] Yann Laigle-Chapuy, Permutation polynomials and applications to coding theory, Finite Fields Appl. 13 (2007), no. 1, 58 – 70. · Zbl 1107.11048 · doi:10.1016/j.ffa.2005.08.003 · doi.org [14] Yu. I. Manin, What is the maximum number of points on a curve over \?$$_{2}$$?, J. Fac. Sci. Univ. Tokyo Sect. IA Math. 28 (1981), no. 3, 715 – 720 (1982). · Zbl 0527.14021 [15] A. Masuda, D. Panario, and Q. Wang, The number of permutation binomials over \?_4\?+1 where \? and 4\?+1 are primes, Electron. J. Combin. 13 (2006), no. 1, Research Paper 65, 15. · Zbl 1121.11077 [16] Ariane M. Masuda and Michael E. Zieve, Nonexistence of permutation binomials of certain shapes, Electron. J. Combin. 14 (2007), no. 1, Note 12, 5. · Zbl 1162.11396 [17] É. 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. [18] D. A. Mit$$^{\prime}$$kin, Estimation of the sum of the Legendre symbols of polynomials of even degree, Mat. Zametki 14 (1973), 73 – 81 (Russian). [19] D. A. Mit$$^{\prime}$$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). [20] Harald Niederreiter and Karl H. Robinson, Complete mappings of finite fields, J. Austral. Math. Soc. Ser. A 33 (1982), no. 2, 197 – 212. · Zbl 0495.12018 [21] J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64 – 94. · Zbl 0122.05001 [22] 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). · Zbl 0538.14015 [23] J.-P. Serre, Rational points on curves over finite fields, unpublished lecture notes by F. Q. Gouvêa, Harvard University, 1985. [24] 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. [25] Henning Stichtenoth, Algebraic function fields and codes, Universitext, Springer-Verlag, Berlin, 1993. · Zbl 0816.14011 [26] 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. · Zbl 0593.14020 · doi:10.1112/plms/s3-52.1.1 · doi.org [27] T. J. Tucker and M. E. Zieve, Permutation polynomials, curves without points, and Latin squares, preprint, 2000. [28] Gerhard Turnwald, Permutation polynomials of binomial type, Contributions to general algebra, 6, Hölder-Pichler-Tempsky, Vienna, 1988, pp. 281 – 286. · Zbl 0699.12029 [29] J. F. Voloch, On the number of values taken by a polynomial over a finite field, Acta Arith. 52 (1989), no. 2, 197 – 201. · Zbl 0693.12014 [30] Da Qing Wan, Permutation polynomials over finite fields, Acta Math. Sinica (N.S.) 3 (1987), no. 1, 1 – 5. · Zbl 0636.12011 · doi:10.1007/BF02564938 · doi.org [31] Da Qing Wan, Permutation binomials over finite fields, Acta Math. Sinica (N.S.) 10 (1994), no. Special Issue, 30 – 35. · Zbl 0817.11056 [32] Da Qing Wan and Rudolf Lidl, Permutation polynomials of the form \?^\?\?(\?^(\?-1)/\?) and their group structure, Monatsh. Math. 112 (1991), no. 2, 149 – 163. · Zbl 0737.11040 · doi:10.1007/BF01525801 · doi.org [33] André Weil, Sur les courbes algébriques et les variétés qui s’en déduisent, Actualités Sci. Ind., no. 1041 = Publ. Inst. Math. Univ. Strasbourg 7 (1945), Hermann et Cie., Paris, 1948 (French). · Zbl 0036.16001 [34] Umberto Zannier, Polynomials modulo \? whose values are squares (elementary improvements on some consequences of Weil’s bounds), Enseign. Math. (2) 44 (1998), no. 1-2, 95 – 102. · Zbl 1064.11501
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.