Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
|
   
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)

     

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
MathSciNet review: 2500883
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 and Social Media LinkedIn Facebook Podcasts Twitter YouTube RSS Feeds Blogs Wikipedia