On asymptotic formulae in some sum–product questions
HTML articles powered by AMS MathViewer
- by I. D. Shkredov
- Trans. Moscow Math. Soc. 2018, 231-281
- DOI: https://doi.org/10.1090/mosc/283
- Published electronically: November 29, 2018
- PDF | Request permission
Abstract:
In this paper we obtain a series of asymptotic formulae in the sum–product phenomena over the prime field $\mathbb {F}_p$. In the proofs we use the usual incidence theorems in $\mathbb {F}_p$, as well as the growth result in $\mathrm {SL}_2 (\mathbb {F}_p)$ due to Helfgott. Here are some of our applications: $\bullet ~$ a new bound for the number of the solutions to the equation $(a_1-a_2) (a_3-a_4) = (a’_1-a’_2) (a’_3-a’_4)$, $a_i, a’_i\in A$, $A$ is an arbitrary subset of $\mathbb {F}_p$, $\bullet ~$ a new effective bound for multilinear exponential sums of Bourgain, $\bullet ~$ an asymptotic analogue of the Balog–Wooley decomposition theorem, $\bullet ~$ growth of $p_1(b) + 1/(a+p_2 (b))$, where $a,b$ runs over two subsets of $\mathbb {F}_p$, $p_1,p_2 \in \mathbb {F}_p [x]$ are two non–constant polynomials, $\bullet ~$ new bounds for some exponential sums with multiplicative and additive characters.References
- Esen Aksoy Yazici, Brendan Murphy, Misha Rudnev, and Ilya Shkredov, Growth estimates in positive characteristic via collisions, Int. Math. Res. Not. IMRN 23 (2017), 7148–7189. MR 3802122, DOI 10.1093/imrn/rnw206
- Antal Balog and Trevor D. Wooley, A low-energy decomposition theorem, Q. J. Math. 68 (2017), no. 1, 207–226. MR 3658289, DOI 10.1093/qmath/haw023
- Bruce C. Berndt, Ronald J. Evans, and Kenneth S. Williams, Gauss and Jacobi sums, Canadian Mathematical Society Series of Monographs and Advanced Texts, John Wiley & Sons, Inc., New York, 1998. A Wiley-Interscience Publication. MR 1625181
- 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, Estimates on exponential sums related to the Diffie-Hellman distributions, Geom. Funct. Anal. 15 (2005), no. 1, 1–34. MR 2140627, DOI 10.1007/s00039-005-0500-4
- Jean Bourgain, Multilinear exponential sums in prime fields under optimal entropy condition on the sources, Geom. Funct. Anal. 18 (2009), no. 5, 1477–1502. MR 2481734, DOI 10.1007/s00039-008-0691-6
- Jean Bourgain, A modular Szemerédi-Trotter theorem for hyperbolas, C. R. Math. Acad. Sci. Paris 350 (2012), no. 17-18, 793–796 (English, with English and French summaries). MR 2989378, DOI 10.1016/j.crma.2012.09.011
- J. Bourgain and M.-C. Chang, Exponential sum estimates over subgroups and almost subgroups of $\Bbb Z_Q^*$, where $Q$ is composite with few prime factors, Geom. Funct. Anal. 16 (2006), no. 2, 327–366. MR 2231466, DOI 10.1007/s00039-006-0558-7
- Jean Bourgain and Alex Gamburd, Uniform expansion bounds for Cayley graphs of $\textrm {SL}_2(\Bbb F_p)$, Ann. of Math. (2) 167 (2008), no. 2, 625–642. MR 2415383, DOI 10.4007/annals.2008.167.625
- 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
- Zh. Burgeĭn and M. Z. Garaev, Sumsets of reciprocals in prime fields and multilinear Kloosterman sums, Izv. Ross. Akad. Nauk Ser. Mat. 78 (2014), no. 4, 19–72 (Russian, with Russian summary); English transl., Izv. Math. 78 (2014), no. 4, 656–707. MR 3288401, DOI 10.1070/im2014v078n04abeh002703
- J. Bourgain, A. A. Glibichuk, and S. V. Konyagin, Estimates for the number of sums and products and for exponential sums in fields of prime order, J. London Math. Soc. (2) 73 (2006), no. 2, 380–398. MR 2225493, DOI 10.1112/S0024610706022721
- 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
- 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
- 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
- M. Z. Garaev, Sums and products of sets and estimates for rational trigonometric sums in fields of prime order, Uspekhi Mat. Nauk 65 (2010), no. 4(394), 5–66 (Russian, with Russian summary); English transl., Russian Math. Surveys 65 (2010), no. 4, 599–658. MR 2759693, DOI 10.1070/RM2010v065n04ABEH004691
- 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
- W. T. Gowers, Quasirandom groups, Combin. Probab. Comput. 17 (2008), no. 3, 363–387. MR 2410393, DOI 10.1017/S0963548307008826
- Larry Guth and Nets Hawk Katz, On the Erdős distinct distances problem in the plane, Ann. of Math. (2) 181 (2015), no. 1, 155–190. MR 3272924, DOI 10.4007/annals.2015.181.1.2
- G. Frobenius, Über Gruppencharaktere, Sitzungsberichte der Königlich Preußischen Akademie der Wissenschaften zu Berlin, 1896, 985–1021.
- Nick Gill, Quasirandom group actions, Forum Math. Sigma 4 (2016), Paper No. e24, 35. MR 3542514, DOI 10.1017/fms.2016.8
- H. A. Helfgott, Growth and generation in $\textrm {SL}_2(\Bbb Z/p\Bbb Z)$, Ann. of Math. (2) 167 (2008), no. 2, 601–623. MR 2415382, DOI 10.4007/annals.2008.167.601
- Roger A. Horn and Charles R. Johnson, Matrix analysis, Cambridge University Press, Cambridge, 1985. MR 832183, DOI 10.1017/CBO9780511810817
- Henryk Iwaniec and Emmanuel Kowalski, Analytic number theory, American Mathematical Society Colloquium Publications, vol. 53, American Mathematical Society, Providence, RI, 2004. MR 2061214, DOI 10.1090/coll/053
- Alex Iosevich, S. Konyagin, M. Rudnev, and V. Ten, Combinatorial complexity of convex sequences, Discrete Comput. Geom. 35 (2006), no. 1, 143–158. MR 2183494, DOI 10.1007/s00454-005-1194-y
- A. Ya. Khinchin, Continued fractions, University of Chicago Press, Chicago, Ill.-London, 1964. MR 0161833
- Sergei Konyagin, $h$-fold sums from a set with few products, Mosc. J. Comb. Number Theory 4 (2014), no. 3, 14–20. MR 3341776
- S. V. Konyagin and I. D. Shkredov, On sum sets of sets having small product set, Proc. Steklov Inst. Math. 290 (2015), no. 1, 288–299. Published in Russian in Tr. Mat. Inst. Steklova 290 (2015), 304–316. MR 3488800, DOI 10.1134/S0081543815060255
- S. V. Konyagin and I. D. Shkredov, New results on sums and products in $\Bbb {R}$, Tr. Mat. Inst. Steklova 294 (2016), no. Sovremennye Problemy Matematiki, Mekhaniki i Matematicheskoĭ Fiziki. II, 87–98 (Russian, with Russian summary). English version published in Proc. Steklov Inst. Math. 294 (2016), no. 1, 78–88. MR 3628494, DOI 10.1134/S0371968516030055
- 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, DOI 10.1017/CBO9780511542930
- Simon Macourt, Incidence results and bounds of trilinear and quadrilinear exponential sums, SIAM J. Discrete Math. 32 (2018), no. 2, 815–825. MR 3782395, DOI 10.1137/17M1147494
- N.G. Moshchevitin, B. Murphy, I.D. Shkredov, Popular products and continued fractions, preprint. arXiv:1808.05845.
- B. Murphy, Upper and lower bounds for rich lines in grids, arXiv:1709.10438v1 [math.CO] 29 Sep 2017.
- Brendan Murphy and Giorgis Petridis, A second wave of expanders in finite fields, Combinatorial and additive number theory. II, Springer Proc. Math. Stat., vol. 220, Springer, Cham, 2017, pp. 215–238. MR 3754906, DOI 10.1007/978-3-319-68032-3_{1}5
- B. Murphy, G. Petridis, Products of Differences over Arbitrary Finite Fields, arXiv:1705.06581v1 [math.CO] 18 May 2017.
- Brendan Murphy and Giorgis Petridis, A point-line incidence identity in finite fields, and applications, Mosc. J. Comb. Number Theory 6 (2016), no. 1, 64–95. MR 3529321
- Oliver Roche-Newton, Misha Rudnev, and Ilya D. Shkredov, New sum-product type estimates over finite fields, Adv. Math. 293 (2016), 589–605. MR 3474329, DOI 10.1016/j.aim.2016.02.019
- B. Murphy, M. Rudnev, I. D. Shkredov, Y.N. Shteinikov, On the few products, many sums problem, arXiv:1712.00410v1 [math.CO] 1 Dec 2017.
- G. Petridis, Collinear triples and quadruples for Cartesian products in $\mathbb {F}_p^2$, arXiv:1610.05620v1 [math.CO] 18 Oct 2016.
- G. Petridis, I.E. Shparlinski, Bounds of trilinear and quadrilinear exponential sums, arXiv:1604.08469v3 [math.NT] 6 Sep 2016.
- László Rédei, Lückenhafte Polynome über endlichen Körpern, Lehrbücher und Monographien aus dem Gebiete der Exakten Wissenschaften, Mathematische Reihe, Band 42, Birkhäuser Verlag, Basel-Stuttgart, 1970 (German). MR 0294297
- Oliver Roche-Newton, Misha Rudnev, and Ilya D. Shkredov, New sum-product type estimates over finite fields, Adv. Math. 293 (2016), 589–605. MR 3474329, DOI 10.1016/j.aim.2016.02.019
- Misha Rudnev, On the number of incidences between points and planes in three dimensions, Combinatorica 38 (2018), no. 1, 219–254. MR 3776354, DOI 10.1007/s00493-016-3329-6
- M. Rudnev, I. D. Shkredov, S. Stevens, On the energy variant of the sum–product conjecture, arXiv:1607.05053.
- Peter Sarnak and Xiao Xi Xue, Bounds for multiplicities of automorphic representations, Duke Math. J. 64 (1991), no. 1, 207–227. MR 1131400, DOI 10.1215/S0012-7094-91-06410-0
- Tomasz Schoen and Ilya D. Shkredov, Higher moments of convolutions, J. Number Theory 133 (2013), no. 5, 1693–1737. MR 3007128, DOI 10.1016/j.jnt.2012.10.010
- Ilya D. Shkredov, Some new inequalities in additive combinatorics, Mosc. J. Comb. Number Theory 3 (2013), no. 3-4, 189–239. MR 3284125
- I. D. Shkredov, Some new results on higher energies, Trans. Moscow Math. Soc. , posted on (2013), 31–63. MR 3235789, DOI 10.1090/s0077-1554-2014-00212-0
- I.D. Shkredov, Some remarks on the Balog–Wooley decomposition theorem and quantities $D^+$, $D^\times$, Proceedings of the Steklov Institute of Mathematics, 298:1 (2017), 74–90.
- I.D. Shkredov, Any small multiplicative subgroup is not a sumset, arXiv:1702.01197v1 [math.NT] 3 Feb 2017.
- I.D. Shkredov, Some remarks on the asymmetric sum–product phenomenon, Moscow J. Combin. Number Theory, (2018), 101–126, dx.doi.org/10.2140/moscow.2018..101; arXiv:1705.09703v1 [math.NT] 26 May 2017.
- Ilya D. Shkredov and Dmitrii Zhelezov, On additive bases of sets with small product set, Int. Math. Res. Not. IMRN 5 (2018), 1585–1599. MR 3800633, DOI 10.1093/imrn/rnw291
- 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
- Sophie Stevens and Frank de Zeeuw, An improved point-line incidence bound over arbitrary fields, Bull. Lond. Math. Soc. 49 (2017), no. 5, 842–858. MR 3742451, DOI 10.1112/blms.12077
- Michio Suzuki, Group theory. I, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 247, Springer-Verlag, Berlin-New York, 1982. Translated from the Japanese by the author. MR 648772
- Tamás Szőnyi, Around Rédei’s theorem, Discrete Math. 208/209 (1999), 557–575. Combinatorics (Assisi, 1996). MR 1725560, DOI 10.1016/S0012-365X(99)00097-7
- 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
- Thang Pham, Michael Tait, Craig Timmons, and Le Anh Vinh, A Szemerédi-Trotter type theorem, sum-product estimates in finite quasifields, and related results, J. Combin. Theory Ser. A 147 (2017), 55–74. MR 3589890, DOI 10.1016/j.jcta.2016.11.003
- Le Anh Vinh, The Szemerédi-Trotter type theorem and the sum-product estimate in finite fields, European J. Combin. 32 (2011), no. 8, 1177–1181. MR 2838005, DOI 10.1016/j.ejc.2011.06.008
- F. de Zeeuw, A short proof of Rudnev’s point–plane incidence bound, arXiv:1612.02719v1 [math.CO] 8 Dec 2016.
Bibliographic Information
- I. D. Shkredov
- Affiliation: Steklov Mathematical Institute, ul. Gubkina, 8, Moscow, Russia, 119991 –and– IITP RAS, Bolshoy Karetny per. 19, Moscow, Russia, 127994 –and– MIPT, Institutskii per. 9, Dolgoprudnii, Russia, 141701
- MR Author ID: 705369
- Email: ilya.shkredov@gmail.com
- Published electronically: November 29, 2018
- Additional Notes: This work was supported by grant Russian Scientific Foundation RSF 14–11–00433.
- © Copyright 2018 American Mathematical Society
- Journal: Trans. Moscow Math. Soc. 2018, 231-281
- MSC (2010): Primary 11B75
- DOI: https://doi.org/10.1090/mosc/283
- MathSciNet review: 3881467