Available in electronic format
Available in print format		 Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(e) ISSN 0002-9947(p)
Previous issue | Table of contents | Next issue
Articles in press | Recently posted articles | Most recent issue | All issues
Previous Article | Next Article
     

Permutation binomials over finite fields

Author(s): Ariane M. Masuda; Michael E. Zieve
Journal: Trans. Amer. Math. Soc. 361 (2009), 4169-4180.
MSC (2000): Primary 11T06
Posted: March 17, 2009
Retrieve article in: PDF

Abstract | References | Similar articles | Additional information

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:

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.
F. Brioschi, Des substitutions de la forme $ \Theta(r)\equiv \varepsilon (r^{n-2}+ar^{(n-3)/2})$ pour un nombre $ n$ premier de lettres, Math. Ann. 2 1870, 467-470. (= Opere Matematiche, v. 5, 193-197) MR 1509672

3.
F. Brioschi, Sur les fonctions de sept lettres, C. R. Acad. Sci. Paris 95 1882, 665-669. (= Opere Matematiche, v. 5, 31-39)

4.
L. Carlitz, Some theorems on permutation polynomials, Bull. Amer. Math. Soc. 68 1962, 120-122. MR 0141655 (25:5052)

5.
L. Carlitz and C. Wells, The number of solutions of a special system of equations in a finite field, Acta Arith. 12 1966-1967, 77-84. MR 0204417 (34:4259)

6.
L. E. 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-1897, 65-120. MR 1502214

7.
V. G. Drinfel'd and S. G. Vlăduţ, The number of points of an algebraic curve, Funktsional. Anal. i Prilozhen. 17 1983, 68-69. (= Funct. Anal. Appl. 17 1983, 53-54) MR 0695100 (85b:14028)

8.
S. El Baghdadi, Sur un problème de L. Carlitz, Acta Arith. 69 1995, 39-50. MR 1310841 (95m:11140)

9.
H. Halberstam and H.-E. Richert, Sieve Methods, Academic Press, London, 1974. MR 0424730 (54:12689)

10.
Ch. Hermite, Sur les fonctions de sept lettres, C. R. Acad. Sci. Paris 57 1863, 750-757.

11.
Y. Ihara, Some remarks on the number of rational points of algebraic curves over finite fields, J. Fac. Sci. Univ. Tokyo 28, 1981, 721-724. MR 0656048 (84c:14016)

12.
N. M. Korobov, An estimate of the sum of the Legendre symbols, Dokl. Akad. Nauk SSSR 196 1971, 764-767. (= Soviet Math. Dokl. 12 1971, 241-245) MR 0274455 (43:220)

13.
Y. Laigle-Chapuy, Permutation polynomials and applications to coding theory, Finite Fields Appl. 13 2007, 58-70. MR 2284666 (2008c:94027)

14.
Y. I. Manin, What is the maximum number of points on a curve over $ \mathbb{F}_2$?, J. Fac. Sci. Univ. Tokyo 28 1981, 715-720. MR 0656047 (84c:14015)

15.
A. Masuda, D. Panario, and Q. Wang, The number of permutation binomials over $ {\mathbb{F}}_{4p+1}$ where $ p$ and $ 4p+1$ are primes, Electron. J. Combin. 13 2006, R65.

MR 2240771 (2007c:11138)

16.
A. M. Masuda and M. E. Zieve, Nonexistence of permutation binomials of certain shapes, Electron. J. Combin. 14 2007, N12. MR 2320592 (2008c:11162)

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'kin, Estimation of the sum of the Legendre symbols of polynomials of even degree, Mat. Zametki 14 1973, 73-81. (= Math. Notes 14 1973, 597-602) MR 0332794 (48:11120)

19.
D. A. Mit'kin, Existence of rational points on a hyperelliptic curves over a finite prime field, Vestnik Moskov. Univ. Ser. I Mat. Meh. 30 1975, 86-90. (= Moscow Univ. Math. Bull. 30 1975, 124-127) MR 0401644 (53:5471)

20.
H. Niederreiter and K. H. Robinson, Complete mappings of finite fields, J. Austral. Math. Soc. (Series A) 33 1982, 197-212. MR 0668442 (83j:12015)

21.
J. B. Rosser and L. Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 1962, 64-94. MR 0137689 (25:1139)

22.
J.-P. 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, 397-402. (= Œuvres [128]) MR 0703906 (85b:14027)

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, in: Analytic Number Theory, Proc. Sympos. Pure Math. 24, 285-302, Amer. Math. Soc., Providence, 1973. MR 0332793 (48:11119)

25.
H. Stichtenoth, Algebraic Function Fields and Codes, Springer-Verlag, Berlin, 1993. MR 1251961 (94k:14016)

26.
K.-O. Stöhr and J. F. Voloch, Weierstrass points and curves over finite fields, Proc. London Math. Soc. (3) 52 1986, 1-19. MR 0812443 (87b:14010)

27.
T. J. Tucker and M. E. Zieve, Permutation polynomials, curves without points, and Latin squares, preprint, 2000.

28.
G. Turnwald, Permutation polynomials of binomial type, in: Contributions to General Algebra 6, 281-286, Hölder-Pichler-Tempsky, Vienna, 1988. MR 1078048 (92e:11141)

29.
J. F. Voloch, On the number of values taken by a polynomial over a finite field, Acta Arith. 52 1989, 197-201. MR 1005605 (90j:11138)

30.
D. Wan, Permutation polynomials over finite fields, Acta Math. Sinica (N.S.) 3 1987, 1-5. MR 0915843 (89b:11100)

31.
D. Wan, Permutation binomials over finite fields, Acta Math. Sinica (N.S.) 10 1994, 30-35. MR 1268257 (94m:11145)

32.
D. Wan and R. Lidl, Permutation polynomials of the form $ x^rf(x^{(q-1)/d})$ and their group structure, Monatsh. Math. 112 1991, 149-163. MR 1126814 (92g:11119)

33.
A. 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, Hermann, Paris, 1948. MR 0027151 (10:262c)

34.
U. Zannier, Polynomials modulo $ p$ whose values are squares (elementary improvements on some consequences of Weil's bounds), Enseign. Math. (2) 44 1998, 95-102. MR 1643282 (99j:11072)

Similar Articles:

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 11T06

Retrieve articles in all Journals with MSC (2000): 11T06

Additional Information:

Ariane M. Masuda
Affiliation: School of Mathematics and Statistics, Carleton University, 1125 Colonel By Drive, Ottawa, Ontario, Canada K1S 5B6
Address at time of publication: Department of Mathematics and Statistics, University of Ottawa, 585 King Edward Avenue, Ottawa, Ontario, Canada K1N 6N5
Email: amasuda@uottawa.ca

Michael E. Zieve
Affiliation: Center for Communications Research, 805 Bunn Drive, Princeton, New Jersey 08540
Email: zieve@math.rutgers.edu

DOI: 10.1090/S0002-9947-09-04578-4
PII: S 0002-9947(09)04578-4
Keywords: Permutation polynomial, finite field, Weil bound
Received by editor(s): February 2, 2007
Received by editor(s) in revised form: July 19, 2007
Posted: March 17, 2009
Additional Notes: The authors thank Jeff VanderKam and Daqing Wan for valuable conversations, and Igor Shparlinski for suggesting the use of the Brun-Titchmarsh theorem in Section 4.
Copyright of article: Copyright 2009, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.

  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2009, American Mathematical Society
Privacy Statement 		Search the AMSPowered by Google