Mordell's exponential sum estimate revisited
Author:
J. Bourgain
Journal:
J. Amer. Math. Soc. 18 (2005), 477499
MSC (2000):
Primary 11L07; Secondary 11T23
Published electronically:
January 18, 2005
MathSciNet review:
2137982
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: The aim of this paper is to extend recent work of S. Konyagin and the author on Gauss sum estimates for large degree to the case of `sparse' polynomials. In this context we do obtain a nearly optimal result, improving on the works of Mordell and of Cochrane and Pinner. The result is optimal in terms of providing some power gain under conditions on the exponents in the polynomial that are best possible if we allow arbitrary coefficients. As in earlier work referred to above, our main combinatorial tool is a sumproduct theorem. Here we need a version for product spaces for which the formulation is obviously not as simple as in the case. Again, the method applies more generally to provide nontrivial bounds on (possibly incomplete) exponential sums involving exponential functions. At the end of the paper, some applications of these are given to issues of uniform distribution for power generators in cryptography.
 [B]
J. Bourgain, Estimates on exponential sums related to the DiffieHellman distributions, to appear in GAFA.
 [BC]
J. Bourgain, M.C. Chang, Exponential sum estimates over subgroups and almost subgroups of where is composite with few prime factors, submitted to Geom. Funct. Anal.
 [BGK]
J. Bourgain, A. Glibichuk, S. Konyagin, Estimate for the number of sums and products and for exponential sums in fields of prime order, submitted to J. London Math. Soc.
 [BK]
Jean
Bourgain and S.
V. Konyagin, Estimates for the number of sums and products and for
exponential sums over subgroups in fields of prime order, C. R. Math.
Acad. Sci. Paris 337 (2003), no. 2, 75–80
(English, with English and French summaries). MR 1998834
(2004g:11067), http://dx.doi.org/10.1016/S1631073X(03)002814
 [BKT]
J.
Bourgain, N.
Katz, and T.
Tao, A sumproduct estimate in finite fields, and
applications, Geom. Funct. Anal. 14 (2004),
no. 1, 27–57. MR 2053599
(2005d:11028), http://dx.doi.org/10.1007/s0003900404511
 [CP1]
Todd
Cochrane and Christopher
Pinner, An improved Mordell type bound for
exponential sums, Proc. Amer. Math. Soc.
133 (2005), no. 2,
313–320 (electronic). MR 2093050
(2005h:11179), http://dx.doi.org/10.1090/S0002993904077263
 [CP2]
Todd
Cochrane and Christopher
Pinner, Stepanov’s method applied to binomial exponential
sums, Q. J. Math. 54 (2003), no. 3,
243–255. MR 2013138
(2004k:11136), http://dx.doi.org/10.1093/qjmath/54.3.243
 [FPS]
John
B. Friedlander, Carl
Pomerance, and Igor
E. Shparlinski, Period of the power generator and
small values of Carmichael’s function, Math. Comp. 70 (2001), no. 236, 1591–1605 (electronic). MR 1836921
(2002g:11112), http://dx.doi.org/10.1090/S0025571800012825
 [FS]
John
B. Friedlander and Igor
E. Shparlinski, On the distribution of the power
generator, Math. Comp. 70
(2001), no. 236, 1575–1589
(electronic). MR
1836920 (2002f:11107), http://dx.doi.org/10.1090/S0025571800012837
 [Go]
W.
T. Gowers, A new proof of Szemerédi’s theorem for
arithmetic progressions of length four, Geom. Funct. Anal.
8 (1998), no. 3, 529–551. MR 1631259
(2000d:11019), http://dx.doi.org/10.1007/s000390050065
 [KS]
Sergei
V. Konyagin and Igor
E. Shparlinski, Character sums with exponential functions and their
applications, Cambridge Tracts in Mathematics, vol. 136,
Cambridge University Press, Cambridge, 1999. MR 1725241
(2000h:11089)
 [Mor]
L.J. Mordell, On a sum analogous to a Gauss sum, Quart. J. Math. 3 (1932), 161162.
 [Na]
Melvyn
B. Nathanson, Additive number theory, Graduate Texts in
Mathematics, vol. 164, SpringerVerlag, New York, 1996. The classical
bases. MR
1395371 (97e:11004)
Melvyn
B. Nathanson, Additive number theory, Graduate Texts in
Mathematics, vol. 165, SpringerVerlag, New York, 1996. Inverse
problems and the geometry of sumsets. MR 1477155
(98f:11011)
 [B]
 J. Bourgain, Estimates on exponential sums related to the DiffieHellman distributions, to appear in GAFA.
 [BC]
 J. Bourgain, M.C. Chang, Exponential sum estimates over subgroups and almost subgroups of where is composite with few prime factors, submitted to Geom. Funct. Anal.
 [BGK]
 J. Bourgain, A. Glibichuk, S. Konyagin, Estimate for the number of sums and products and for exponential sums in fields of prime order, submitted to J. London Math. Soc.
 [BK]
 J. Bourgain, S. Konyagin, Estimates for the number of sums and products and for exponential sums over subgroups in fields of prime order, CR Acad. Sci., Paris 337 (2003), no 2, 7580. MR 1998834 (2004g:11067)
 [BKT]
 J. Bourgain, N. Katz, T. Tao, A sumproduct theorem in finite fields and applications, Geom. Funct. Anal. 14 (2004), no. 1, 2757.MR 2053599
 [CP1]
 T. Cochrane, C. Pinner, An improved Mordell type bound for exponential sums, Proc. Amer. Math. Soc. 133 (2005), no. 2, 313320 (electronic).MR 2093050
 [CP2]
 , Stepanov's method applied to binomial exponential sums, Quart. J. Math. 54 (2003), No 3, 243255. MR 2013138 (2004k:11136)
 [FPS]
 J. Friedlander, C. Pomerance, I. Shparlinsky, Period of the power generator and small values of the Carmichael function, Math. Comp. 70 (2001), no. 236, 15911605. MR 1836921 (2002g:11112)
 [FS]
 J. Friedlander, I. Shparlinsky, On the distribution of the power generator, Math. Comp., Vol. 70, No. 236, (2001), 15751589. MR 1836920 (2002f:11107)
 [Go]
 T. Govers, A new proof of Szemerédi's theorem for arithmetic progressions of length 4, GAFA 8 (1998), no. 3, 529551. MR 1631259 (2000d:11019)
 [KS]
 S. Konyagin, I. Shparlinski, Character sums with exponential functions and their applications, Cambridge UP, Cambridge (1999). MR 1725241 (2000h:11089)
 [Mor]
 L.J. Mordell, On a sum analogous to a Gauss sum, Quart. J. Math. 3 (1932), 161162.
 [Na]
 M. Nathanson, Additive Number Theory, SpringerVerlag, NY, 1996.MR 1395371 (97e:11004); MR 1477155 (98f:11011)
Similar Articles
Retrieve articles in Journal of the American Mathematical Society
with MSC (2000):
11L07,
11T23
Retrieve articles in all journals
with MSC (2000):
11L07,
11T23
Additional Information
J. Bourgain
Affiliation:
School of Mathematics, Institute for Advanced Study, Princeton, New Jersey 08540
DOI:
http://dx.doi.org/10.1090/S0894034705004765
PII:
S 08940347(05)004765
Received by editor(s):
July 16, 2004
Published electronically:
January 18, 2005
Article copyright:
© Copyright 2005 American Mathematical Society
