Fourier analysis and expanding phenomena in finite fields

Hart, Derrick; Li, Liangpan; Shen, Chun-Yen

doi:10.1090/S0002-9939-2012-11338-3

Fourier analysis and expanding phenomena in finite fields
HTML articles powered by AMS MathViewer

by Derrick Hart, Liangpan Li and Chun-Yen Shen

Proc. Amer. Math. Soc. 141 (2013), 461-473

DOI: https://doi.org/10.1090/S0002-9939-2012-11338-3

Published electronically: June 19, 2012

PDF | Request permission

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 $A$ is a subset of a prime field $\mathbb F_p$ of size less than $p^{1/2}$ it is shown that $|\{a^2+b:a,b \in A\}|\geq C_1 |A|^{147/146}$ and $|\{\frac {b+1}{a}:a,b \in A\}|\geq C_2 |A|^{110/109}$, where $|\cdot |$ denotes the cardinality of a set and $C_1$ and $C_2$ are absolute constants.

References

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, DOI 10.1142/S1793042105000108
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, DOI 10.1017/S0305004108001230
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, DOI 10.1007/s00039-004-0451-1
J. Cilleruelo, Combinatorial problems in finite fields and Sidon sets, arXiv:1003.3576, 2010. Combinatorica, to appear.
E. Croot, Private communication, 2009.
György Elekes, On the number of sums and products, Acta Arith. 81 (1997), no. 4, 365–367. MR 1472816, DOI 10.4064/aa-81-4-365-367
György Elekes, Melvyn B. Nathanson, and Imre Z. Ruzsa, Convexity and sumsets, J. Number Theory 83 (2000), no. 2, 194–201. MR 1772612, DOI 10.1006/jnth.1999.2386
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
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, DOI 10.1023/A:1009709908223
M. Z. Garaev, An explicit sum-product estimate in $\Bbb F_p$, Int. Math. Res. Not. IMRN 11 (2007), Art. ID rnm035, 11. MR 2344270
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, DOI 10.1090/S0002-9939-08-09386-6
Moubariz Z. Garaev and Chun-Yen Shen, On the size of the set $A(A+1)$, Math. Z. 265 (2010), no. 1, 125–132. MR 2606952, DOI 10.1007/s00209-009-0504-0
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, DOI 10.1090/crmp/043/15
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, DOI 10.1093/imrn/rnm007
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
Liangpan Li, Slightly improved sum-product estimates in fields of prime order, Acta Arith. 147 (2011), no. 2, 153–160. MR 2771659, DOI 10.4064/aa147-2-4
Liangpan Li and Jian Shen, A sum-division estimate of reals, Proc. Amer. Math. Soc. 138 (2010), no. 1, 101–104. MR 2550173, DOI 10.1090/S0002-9939-2010-10431-8
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
Melvyn B. Nathanson, On sums and products of integers, Proc. Amer. Math. Soc. 125 (1997), no. 1, 9–16. MR 1343715, DOI 10.1090/S0002-9939-97-03510-7
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, DOI 10.1006/ffta.2001.0334
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, DOI 10.1007/3-540-33700-8_{1}1
M. Rudnev, An improved sum-product inequality in fields of prime order, arXiv:1011.2738, 2010. IMRN, to appear.
C.-Y. Shen, Algebraic methods in sum-product phenomena, Israel J. Math. 188 (2012), no. 1.
Chun-Yen Shen, An extension of Bourgain and Garaev’s sum-product estimates, Acta Arith. 135 (2008), no. 4, 351–356. MR 2465717, DOI 10.4064/aa135-4-4
Chun-Yen Shen, On the sum product estimates and two variables expanders, Publ. Mat. 54 (2010), no. 1, 149–157. MR 2603593, DOI 10.5565/PUBLMAT_{5}4110_{0}8
József Solymosi, On the number of sums and products, Bull. London Math. Soc. 37 (2005), no. 4, 491–494. MR 2143727, DOI 10.1112/S0024609305004261
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, DOI 10.1007/978-3-540-85221-6_{1}7
József Solymosi, Bounding multiplicative energy by the sumset, Adv. Math. 222 (2009), no. 2, 402–408. MR 2538014, DOI 10.1016/j.aim.2009.04.006
Terence Tao and Van Vu, Additive combinatorics, Cambridge Studies in Advanced Mathematics, vol. 105, Cambridge University Press, Cambridge, 2006. MR 2289012, DOI 10.1017/CBO9780511755149
L. A. Vinh, The solvability of norm, bilinear and quadratic equations over finite fields via spectra of graphs, arXiv:0904.0441, 2009.
Van H. Vu, Sum-product estimates via directed expanders, Math. Res. Lett. 15 (2008), no. 2, 375–388. MR 2385648, DOI 10.4310/MRL.2008.v15.n2.a14