|
Fourier analysis and expanding phenomena in finite fields
Authors:
Derrick Hart, Liangpan Li and Chun-Yen Shen
Journal:
Proc. Amer. Math. Soc. 141 (2013), 461-473
MSC (2010):
Primary 11B75
Posted:
June 19, 2012
Full-text PDF
Abstract |
References |
Similar Articles |
Additional Information
Abstract: In this paper we study set expansion in finite fields. Fourier analytic proofs are given for several results recently obtained by other authors using spectral graph theory. In addition, several generalizations of these results are given. In the case that is a subset of a prime field of size less than it is shown that and , where denotes the cardinality of a set and and are absolute constants.
- 1.
J.
Bourgain, More on the sum-product phenomenon in prime fields and
its applications, Int. J. Number Theory 1 (2005),
no. 1, 1–32. MR 2172328
(2006g:11041), http://dx.doi.org/10.1142/S1793042105000108
- 2.
J.
Bourgain and M.
Z. Garaev, On a variant of sum-product estimates and explicit
exponential sum bounds in prime fields, Math. Proc. Cambridge Philos.
Soc. 146 (2009), no. 1, 1–21. MR 2461864
(2009k:11019), http://dx.doi.org/10.1017/S0305004108001230
- 3.
J.
Bourgain, N.
Katz, and T.
Tao, A sum-product 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/s00039-004-0451-1
- 4.
J. Cilleruelo, Combinatorial problems in finite fields and Sidon sets, arXiv:1003.3576, 2010. Combinatorica, to appear.
- 5.
E. Croot, Private communication, 2009.
- 6.
György
Elekes, On the number of sums and products, Acta Arith.
81 (1997), no. 4, 365–367. MR 1472816
(98h:11026)
- 7.
György
Elekes, Melvyn
B. Nathanson, and Imre
Z. Ruzsa, Convexity and sumsets, J. Number Theory
83 (2000), no. 2, 194–201. MR 1772612
(2001e:11020), http://dx.doi.org/10.1006/jnth.1999.2386
- 8.
P.
Erdős and E.
Szemerédi, On sums and products of integers, Studies in
pure mathematics, Birkhäuser, Basel, 1983, pp. 213–218. MR 820223
(86m:11011)
- 9.
Kevin
Ford, Sums and products from a finite set of real numbers,
Ramanujan J. 2 (1998), no. 1-2, 59–66. Paul
Erdős (1913–1996). MR 1642873
(99i:11014), http://dx.doi.org/10.1023/A:1009709908223
- 10.
M.
Z. Garaev, An explicit sum-product estimate in
𝔽_{𝕡}, Int. Math. Res. Not. IMRN 11
(2007), Art. ID rnm035, 11. MR 2344270
(2008g:11038)
- 11.
M.
Z. Garaev, The sum-product estimate for large
subsets of prime fields, Proc. Amer. Math.
Soc. 136 (2008), no. 8, 2735–2739. MR 2399035
(2009e:11043), http://dx.doi.org/10.1090/S0002-9939-08-09386-6
- 12.
Moubariz
Z. Garaev and Chun-Yen
Shen, On the size of the set 𝐴(𝐴+1), Math. Z.
265 (2010), no. 1, 125–132. MR 2606952
(2011b:11022), http://dx.doi.org/10.1007/s00209-009-0504-0
- 13.
A.
A. Glibichuk and S.
V. Konyagin, Additive properties of product sets in fields of prime
order, Additive combinatorics, CRM Proc. Lecture Notes, vol. 43,
Amer. Math. Soc., Providence, RI, 2007, pp. 279–286. MR 2359478
(2009a:11054)
- 14.
Derrick
Hart, Alex
Iosevich, and Jozsef
Solymosi, Sum-product estimates in finite fields via Kloosterman
sums, Int. Math. Res. Not. IMRN 5 (2007), Art. ID
rnm007, 14. MR
2341599 (2008i:11037), http://dx.doi.org/10.1093/imrn/rnm007
- 15.
Nicholas
M. Katz, Sommes exponentielles, Astérisque,
vol. 79, Société Mathématique de France, Paris,
1980 (French). Course taught at the University of Paris, Orsay, Fall 1979;
With a preface by Luc Illusie; Notes written by Gérard Laumon; With
an English summary. MR 617009
(82m:10059)
- 16.
Liangpan
Li, Slightly improved sum-product estimates in fields of prime
order, Acta Arith. 147 (2011), no. 2,
153–160. MR 2771659
(2012b:11016), http://dx.doi.org/10.4064/aa147-2-4
- 17.
Liangpan
Li and Jian
Shen, A sum-division estimate of
reals, Proc. Amer. Math. Soc.
138 (2010), no. 1,
101–104. MR 2550173
(2010m:11033), http://dx.doi.org/10.1090/S0002-9939-09-10052-7
- 18.
Rudolf
Lidl and Harald
Niederreiter, Finite fields, 2nd ed., Encyclopedia of
Mathematics and its Applications, vol. 20, Cambridge University Press,
Cambridge, 1997. With a foreword by P. M. Cohn. MR 1429394
(97i:11115)
- 19.
Melvyn
B. Nathanson, On sums and products of
integers, Proc. Amer. Math. Soc.
125 (1997), no. 1,
9–16. MR
1343715 (97c:11010), http://dx.doi.org/10.1090/S0002-9939-97-03510-7
- 20.
Harald
Niederreiter and Arne
Winterhof, Incomplete character sums and polynomial interpolation
of the discrete logarithm, Finite Fields Appl. 8
(2002), no. 2, 184–192. MR 1894512
(2003a:11155), http://dx.doi.org/10.1006/ffta.2001.0334
- 21.
Pavel
Pudlák, On explicit Ramsey graphs and estimates of the
number of sums and products, Topics in discrete mathematics,
Algorithms Combin., vol. 26, Springer, Berlin, 2006,
pp. 169–175. MR 2249270
(2007h:05107), http://dx.doi.org/10.1007/3-540-33700-8_11
- 22.
M. Rudnev, An improved sum-product inequality in fields of prime order, arXiv:1011.2738, 2010. IMRN, to appear.
- 23.
C.-Y. Shen, Algebraic methods in sum-product phenomena, Israel J. Math. 188 (2012), no. 1.
- 24.
Chun-Yen
Shen, An extension of Bourgain and Garaev’s sum-product
estimates, Acta Arith. 135 (2008), no. 4,
351–356. MR 2465717
(2009i:11028), http://dx.doi.org/10.4064/aa135-4-4
- 25.
Chun-Yen
Shen, On the sum product estimates and two variables
expanders, Publ. Mat. 54 (2010), no. 1,
149–157. MR 2603593
(2011b:11023), http://dx.doi.org/10.5565/PUBLMAT_54110_08
- 26.
József
Solymosi, On the number of sums and products, Bull. London
Math. Soc. 37 (2005), no. 4, 491–494. MR 2143727
(2006c:11021), http://dx.doi.org/10.1112/S0024609305004261
- 27.
József
Solymosi, Incidences and the spectra of graphs, Building
bridges, Bolyai Soc. Math. Stud., vol. 19, Springer, Berlin, 2008,
pp. 499–513. MR 2484652
(2010e:05189), http://dx.doi.org/10.1007/978-3-540-85221-6_17
- 28.
József
Solymosi, Bounding multiplicative energy by the sumset, Adv.
Math. 222 (2009), no. 2, 402–408. MR 2538014
(2010h:11014), http://dx.doi.org/10.1016/j.aim.2009.04.006
- 29.
Terence
Tao and Van
Vu, Additive combinatorics, Cambridge Studies in Advanced
Mathematics, vol. 105, Cambridge University Press, Cambridge, 2006. MR 2289012
(2008a:11002)
- 30.
L. A. Vinh, The solvability of norm, bilinear and quadratic equations over finite fields via spectra of graphs, arXiv:0904.0441, 2009.
- 31.
Van
H. Vu, Sum-product estimates via directed expanders, Math.
Res. Lett. 15 (2008), no. 2, 375–388. MR 2385648
(2009e:11023)
- 1.
- J. Bourgain, More on the sum-product phenomenon in prime fields and its applications, Int. J. Number Theory 1 (2005), 1-32. MR 2172328 (2006g:11041)
- 2.
- J. Bourgain, M. Garaev, On a variant of sum-product estimates and explicit exponential sum bounds in prime fields, Math. Proc. Cambridge Philos. Soc. 146 (2009), 1-21. MR 2461864 (2009k:11019)
- 3.
- J. Bourgain, N. Katz, T. Tao, A sum-product estimate in finite fields, and applications, Geom. Funct. Anal. 14 (2004), 27-57. MR 2053599 (2005d:11028)
- 4.
- J. Cilleruelo, Combinatorial problems in finite fields and Sidon sets, arXiv:1003.3576, 2010. Combinatorica, to appear.
- 5.
- E. Croot, Private communication, 2009.
- 6.
- Gy. Elekes, On the number of sums and products, Acta Arith. 81 (1997), 365-367. MR 1472816 (98h:11026)
- 7.
- Gy. Elekes, M. B. Nathanson, I. Z. Ruzsa, Convexity and sumsets, J. Number Theory 83 (2000), 194-201. MR 1772612 (2001e:11020)
- 8.
- P. Erdős, E. Szemerédi, On sums and products of integers, Studies in Pure Mathematics, pages 213-218, Birkhäuser, Basel, 1983. MR 820223 (86m:11011)
- 9.
- K. Ford, Sums and products from a finite set of real numbers, Ramanujan J. 2 (1998), 59-66. MR 1642873 (99i:11014)
- 10.
- M. Garaev, An explicit sum-product estimate in
, Int. Math. Res. Notices 11 (2007), Art. ID rnm035. MR 2344270 (2008g:11038)
- 11.
- M. Garaev, The sum-product estimate for large subsets of prime fields, Proc. Amer. Math. Soc. 136 (2008), 2735-2739. MR 2399035 (2009e:11043)
- 12.
- M. Garaev, C.-Y. Shen, On the size of the set A(A+1), Math. Z. 265 (2010), 125-132. MR 2606952 (2011b:11022)
- 13.
- A. Glibichuk, S. Konyagin. Additive properties of product sets in fields of prime order, CRM Proc. Lecture Notes, 43, Additive combinatorics, 279-286, Amer. Math. Soc., Providence, RI, 2007. MR 2359478 (2009a:11054)
- 14.
- D. Hart, A. Iosevich, J. Solymosi, Sum-product estimates in finite fields via Kloosterman sums, Int. Math. Res. Notices 5 (2007), Art. ID rmn007. MR 2341599 (2008i:11037)
- 15.
- N. M. Katz, Sommes exponentielles, Astérisque 79, Société Mathématique de France, Paris, 1980. MR 617009 (82m:10059)
- 16.
- L. Li, Slightly improved sum-product estimates in fields of prime order, Acta. Arith. 147 (2011), 153-160. MR 2771659
- 17.
- L. Li, J. Shen, A sum-division estimate of reals, Proc. Amer. Math. Soc. 138 (2010), 101-104. MR 2550173 (2010m:11033)
- 18.
- R. Lidl, H. Niederreiter, Finite Fields, second edition, Cambridge University Press, 1997. MR 1429394 (97i:11115)
- 19.
- M. B. Nathanson, On sums and products of integers, Proc. Amer. Math. Soc. 125 (1997), 9-16. MR 1343715 (97c:11010)
- 20.
- H. Niederreiter, Incomplete character sums and polynomial interpolation of the discrete logarithm, Finite Fields Appl. 8 (2002), 184-192. MR 1894512 (2003a:11155)
- 21.
- P. Pudlák, On explicit Ramsey graphs and estimates of the number of sums and products, Topics in discrete mathematics, 169-175, Algorithms Combin., 26, Springer, Berlin, 2006. MR 2249270 (2007h:05107)
- 22.
- M. Rudnev, An improved sum-product inequality in fields of prime order, arXiv:1011.2738, 2010. IMRN, to appear.
- 23.
- C.-Y. Shen, Algebraic methods in sum-product phenomena, Israel J. Math. 188 (2012), no. 1.
- 24.
- C.-Y. Shen, An extension of Bourgain and Garaev's sum-product estimates, Acta Arith. 135 (2008), 351-356. MR 2465717 (2009i:11028)
- 25.
- C.-Y. Shen, On the sum product estimates and two variables expanders, Publ. Math. 54 (2010), 149-157. MR 2603593 (2011b:11023)
- 26.
- J. Solymosi, On the number of sums and products, Bull. London Math. Soc. 37 (2005), 491-494. MR 2143727 (2006c:11021)
- 27.
- J. Solymosi, Incidences and the spectra of graphs, Building Bridges, 499-513, Bolyai Soc. Math. Stud., 19, Springer, Berlin, 2008. MR 2484652 (2010e:05189)
- 28.
- J. Solymosi, Bounding multiplicative energy by the sumset, Adv. Math. 222 (2009), 402-408. MR 2538014 (2010h:11014)
- 29.
- T. Tao, V. Vu, Additive Combinatorics, Cambridge University Press, 2006. MR 2289012 (2008a:11002)
- 30.
- L. A. Vinh, The solvability of norm, bilinear and quadratic equations over finite fields via spectra of graphs, arXiv:0904.0441, 2009.
- 31.
- V. Vu, Sum-product estimates via directed expanders, Math. Res. Lett. 15 (2008), 375-388. MR 2385648 (2009e:11023)
Similar Articles
Retrieve articles in Proceedings of the American Mathematical Society
with MSC (2010):
11B75
Retrieve articles in all journals
with MSC (2010):
11B75
Additional Information
Derrick Hart
Affiliation:
Department of Mathematics, Rutgers University, Piscataway, New Jersey 08854
Email:
dnhart@math.rutgers.edu
Liangpan Li
Affiliation:
Department of Mathematics, Shanghai Jiao Tong University, Shanghai 200240, People’s Republic of China – and – Department of Mathematical Sciences, Loughborough University, Leicestershire LE11 3TU, United Kingdom
Email:
liliangpan@gmail.com
Chun-Yen Shen
Affiliation:
Department of Mathematics and Statistics, McMaster University, Hamilton, Ontario L8S 4K1, Canada
Address at time of publication:
Department of Mathematics, Michigan State University, East Lansing, Michigan 48824
Email:
shenc@umail.iu.edu
DOI:
http://dx.doi.org/10.1090/S0002-9939-2012-11338-3
PII:
S 0002-9939(2012)11338-3
Keywords:
Sums,
products,
expanding maps,
character sums
Received by editor(s):
April 10, 2011
Received by editor(s) in revised form:
July 4, 2011
Posted:
June 19, 2012
Communicated by:
Matthew A. Papanikolas
Article copyright:
© Copyright 2012 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.
|