On the few products, many sums problem

Murphy, Brendan; Rudnev, Misha; Shkredov, Ilya; Shteinikov, Yuri

Journal de théorie des nombres de Bordeaux, Tome 31 (2019) no. 3, pp. 573-602.

Nous prouvons de nouvelles estimations quantitatives pour les propriétés additives des ensembles finis à doublement multiplicatif petit $\left|AA\right|\le M\left|A\right|$ dans la catégorie des ensembles réels ou complexes $A,$ ainsi que pour les sous-groupes du groupe multiplicatif d’un corps fini premier. Ces améliorations reposent sur de nouveaux lemmes combinatoires qui peuvent présenter un intérêt indépendant.

Dans le cas réel,nos principaux résultats sont l’inégalité

$${|A-A|}^3{\left|AA\right|}^5\gtrsim {\left|A\right|}^{10}$$

qui redistribue les exposants dans l’inégalité somme-produit d’Elekes et la nouvelle borne pour l’énergie additive

$$\mathsf{E}\left(A\right){\lesssim }_M{\left|A\right|}^{49/20},$$

qui améliore les résultats précédemment connus et s’accorde, au sens expliqué dans l’article, avec la meilleure borne connue pour l’ensemble somme $|A+A|{\gtrsim }_M{\left|A\right|}^{8/5}$.

Ces bornes, avec $M=1$, s’appliquent également aux sous-groupes multiplicatifs de ${𝔽}_p^{\times }$ d’ordre $O\left(\sqrt{p}\right)$. Nous adaptons la borne pour l’énergie citée ci-dessus à des sous-groupes plus grands et obtenons de nouvelles bornes pour les écarts entre les éléments dans les classes des sous-groupes d’ordre $\Omega \left(\sqrt{p}\right)$.

We prove new quantitative estimates on additive properties of finite sets $A$ with small multiplicative doubling $\left|AA\right|\le M\left|A\right|$ in the category of real/complex sets as well as multiplicative subgroups in the prime residue field. The improvements are based on new combinatorial lemmata, which may be of independent interest.

Our main results are the inequality

$${|A-A|}^3{\left|AA\right|}^5\gtrsim {\left|A\right|}^{10},$$

over the reals, “redistributing” the exponents in the textbook Elekes sum-product inequality and the new best known additive energy bound $\mathsf{E}\left(A\right){\lesssim }_M{\left|A\right|}^{49/20}$, which aligns, in a sense to be discussed, with the best known sum set bound $|A+A|{\gtrsim }_M{\left|A\right|}^{8/5}$.

These bounds, with $M=1$, also apply to multiplicative subgroups of ${𝔽}_p^{\times }$, whose order is $O\left(\sqrt{p}\right)$. We adapt the above energy bound to larger subgroups and obtain new bounds on gaps between elements in cosets of subgroups of order $\Omega \left(\sqrt{p}\right)$.

Classification : 11B13, 11B50, 11B75
Mots clés : Sum–product phenomenon, multiplicative subgroups, additive energy

[1] Balog, Antal; Wooley, Trevor D. A low-energy decomposition theorem, Q. J. Math, Volume 68 (2017), pp. 207-226 | DOI | MR | Zbl

[2] Bourgain, Jean; Chang, Mei-Chu On the size of k-fold sum and product sets of integers, J. Am. Math. Soc., Volume 17 (2004) no. 2, pp. 473-497 | DOI | MR | Zbl

[3] Bourgain, Jean; Konyagin, Sergeĭ V.; Shparlinski, Igor E. Product sets of rationals, multiplicative translates of subgroups in residue rings and fixed points of the discrete logarithm, Int. Math. Res. Not., Volume 2008 (2008), rnn090, 29 pages | Zbl

[4] Chang, Mei-Chu; Solymosi, József Sum-product theorems and incidence geometry, J. Eur. Math. Soc., Volume 9 (2007) no. 3, pp. 545-560 | DOI | MR | Zbl

[5] Cilleruelo, Javier; Garaev, Moubariz Z. The congruence $x^x=\lambda (modp)$, Proc. Am. Math. Soc., Volume 144 (2016) no. 6, pp. 2411-2418 | DOI | Zbl

[6] Cilleruelo, Javier; Garaev, Moubariz Z. Congruences involving product of intervals and sets with small multiplicative doubling modulo a prime and applications, Math. Proc. Camb. Philos. Soc., Volume 160 (2016) no. 3, pp. 477-494 | DOI | MR | Zbl

[7] Elekes, György On the number of sums and products, Acta Arith., Volume 81 (1997) no. 4, pp. 365-367 | DOI | MR | Zbl

[8] Elekes, György; Nathanson, Melvyn B.; Ruzsa, Imre Z. Convexity and sumsets, J. Number Theory, Volume 83 (2000) no. 2, pp. 194-201 | DOI | MR | Zbl

[9] Elekes, György; Ruzsa, Imre Z. Few sums, many products, Stud. Sci. Math. Hung., Volume 40 (2003) no. 3, pp. 301-308 | MR | Zbl

[10] Erdős, Paul; Szemerédi, Endre On sums and products of integers, Studies in pure mathematics, Birkhäuser, 1983, pp. 213-218 | DOI | Zbl

[11] Granville, Andrew; Solymosi, József Sum-product formulae, Recent trends in combinatorics (The IMA Volumes in Mathematics and its Applications), Volume 159, Springer, 2016, pp. 419-451 | DOI | MR | Zbl

[12] Heath-Brown, David R.; Konyagin, Sergeĭ V. New bounds for Gauss sums derived from $k$th powers, and for Heilbronn’s exponential sum, Q. J. Math, Volume 51 (2000) no. 2, pp. 221-235 | DOI | Zbl

[13] Konyagin, Sergeĭ V. Estimates for trigonometric sums and for Gaussian sums, IV International conference “Modern problems of number theory and its applications”, 2002, pp. 86-114 | Zbl

[14] Konyagin, Sergeĭ V.; Shkredov, Il’ya D. On sum sets of sets, having small product sets, Tr. Mat. Inst. Steklova, Volume 290 (2015), pp. 304-316 | MR | Zbl

[15] Konyagin, Sergeĭ V.; Shkredov, Il’ya D. New results on sum-products in $ℝ$, Proc. Steklov Inst. Math., Volume 294 (2016) no. 78, pp. 87-98 | MR

[16] Konyagin, Sergeĭ V.; Shparlinski, Igor E. Character sums with exponential functions, Cambridge Tracts in Mathematics, 136, Cambridge University Press, 1999 | MR | Zbl

[17] Li, Liangpan On a theorem of Schoen and Shkredov on sumsets of convex sets (2011) (https://arxiv.org/abs/1108.4382)

[18] Li, Liangpan; Roche-Newton, Oliver Convexity and a sum-product type estimate, Acta Arith., Volume 156 (2012) no. 3, pp. 247-255 | MR | Zbl

[19] Macourt, Simon; Shkredov, Il’ya D.; Shparlinski, Igor E. Multiplicative energy of shifted sugroups and bounds on exponential sums with trinomials in finite fields (2017) (https://arxiv.org/abs/1701.06192, to appear in Can. J. Math.)

[20] Malykhin, Yuriĭ V. Bounds for exponential sums over $p^2$, J. Math. Sci., New York, Volume 146 (2007) no. 2, pp. 5686-5696 | DOI | Zbl

[21] Mit’kin, Dmitriĭ Alekseevich Estimation of the total number of total number of the rational points on a set of curves in a simple finite field, Chebyshevskiĭ Sb., Volume 4 (2003) no. 4, pp. 94-102 | Zbl

[22] Murphy, Brendan; Petridis, Giorgis; Roche-Newton, Oliver; Rudnev, Misha; Shkredov, Il’ya D. New results on sum-product type growth over fields, Mathematika, Volume 65 (2019) no. 3, pp. 588-642 | DOI | MR | Zbl

[23] Murphy, Brendan; Roche-Newton, Oliver; Shkredov, Il’ya D. Variations on the sum-product problem II, SIAM J. Discrete Math., Volume 31 (2017) no. 3, pp. 1878-1894 | DOI | MR | Zbl

[24] Pappalardi, Francesco On the order of finitely generated subgroups of ${\mathbb{Q}}^{*}\left(\mathrm{mod}p\right)$ and divisors of $p-1$, J. Number Theory, Volume 57 (1996) no. 2, pp. 207-222 | DOI | MR | Zbl

[25] Roche-Newton, Oliver; Rudnev, Misha; Shkredov, Il’ya D. New sum-product type estimates over finite fields, Adv. Math., Volume 293 (2016), pp. 589-605 | DOI | MR | Zbl

[26] Rudnev, Misha On the number of incidences between planes and points in three dimensions, Combinatorica, Volume 38 (2018) no. 1, pp. 219-254 | DOI | MR | Zbl

[27] Rudnev, Misha; Stevens, Sophie; Shkredov, Il’ya D. On The Energy Variant of the Sum-Product Conjecture (2017) (https://arxiv.org/abs/1607.05053v5, to appear in Rev. Mat. Iberoam.)

[28] Schoen, Tomasz; Shkredov, Il’ya D. On sumsets of convex sets, Comb. Probab. Comput., Volume 20 (2011) no. 5, pp. 793-798 | DOI | MR | Zbl

[29] Schoen, Tomasz; Shkredov, Il’ya D. Additive properties of multiplicative subgroups of ${𝔽}_p$, Q. J. Math, Volume 63 (2012) no. 3, pp. 713-722 | DOI | Zbl

[30] Schoen, Tomasz; Shkredov, Il’ya D. Higher moments of convolutions, J. Number Theory, Volume 133 (2013) no. 5, pp. 1693-1737 | DOI | MR | Zbl

[31] Shkredov, Il’ya D. Some applications of W. Rudin’s inequality to problems of combinatorial number theory, Unif. Distrib. Theory, Volume 6 (2011) no. 2, pp. 95-116 | MR | Zbl

[32] Shkredov, Il’ya D. Some new inequalities in additive combinatorics, Mosc. J. Comb. Number Theory, Volume 3 (2013) no. 3-4, pp. 237-288 | MR | Zbl

[33] Shkredov, Il’ya D. Some new results on higher energies, Tr. Mosk. Mat. O.-va, Volume 74 (2013), pp. 35-73 | Zbl

[34] Shkredov, Il’ya D. On exponential sums over multiplicative subgroups of medium size, Finite Fields Appl., Volume 30 (2014), pp. 72-87 | DOI | MR | Zbl

[35] Shkredov, Il’ya D. On tripling constant of multiplicative subgroups, Integers, Volume 16 (2016), A75, 9 pages | MR | Zbl

[36] Shkredov, Il’ya D. Some remarks on sets with small quotient set, Sb. Math., Volume 208 (2017) no. 12, pp. 1854-1868 | DOI | MR | Zbl

[37] Shkredov, Il’ya D.; Solodkova, E. V.; Vyugin, Ilya V. On the additive energy of Heilbronn’s subgroup, Mat. Zametki, Volume 101 (2017) no. 1, pp. 43-57 | MR | Zbl

[38] Shkredov, Il’ya D.; Vyugin, Ilya V. On additive shifts of multiplicative subgroups, Mat. Sb., Volume 203 (2012) no. 6, pp. 81-100 | MR | Zbl

[39] Shkredov, Il’ya D.; Zhelezov, Dmitrii On additive bases of sets with small product set (2016) (1606.02320v2, to appear in Int. Math. Res. Not.) | Zbl

[40] Shteĭnikov, Yuriĭ N. Estimates of trigonometric sums over subgroups and some of their applications, Mathematical Notes, Volume 98 (2015) no. 4, pp. 667-684 | DOI | MR | Zbl

[41] Solymosi, József Bounding multiplicative energy by the sumset, Adv. Math., Volume 222 (2009) no. 2, pp. 402-408 | DOI | MR | Zbl

[42] Solymosi, József; Tardos, Gábor On the number of $k$-rich transformations, Proceedings of the 23rd annual symposium on computational geometry, SCG’07, ACM Press, 2007, pp. 227-231 | Zbl

[43] Stevens, Sophie; Zeeuw, Frank de An Improved Point-Line Incidence Bound Over Arbitrary Fields (2016) (https://arxiv.org/abs/1609.06284v4)

[44] Szemerédi, Endre; Trotter, William T. Extremal problems in discrete geometry, Combinatorica, Volume 3 (1983), pp. 381-392 | DOI | MR | Zbl

[45] Tao, Terence; Vu, Van H. Additive Combinatorics, Cambridge Studies in Advanced Mathematics, 105, Cambridge University Press, 2006 | MR | Zbl