 On the few products, many sums problem
Journal de théorie des nombres de Bordeaux, Volume 31 (2019) no. 3, pp. 573-602.

We prove new quantitative estimates on additive properties of finite sets $A$ with small multiplicative doubling $|AA|\le M|A|$ 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}{|AA|}^{5}\gtrsim {|A|}^{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}{|A|}^{49/20}$, which aligns, in a sense to be discussed, with the best known sum set bound $|A+A|{\gtrsim }_{M}{|A|}^{8/5}$.

These bounds, with $M=1$, also apply to multiplicative subgroups of ${𝔽}_{p}^{×}$, 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)$.

Nous prouvons de nouvelles estimations quantitatives pour les propriétés additives des ensembles finis à doublement multiplicatif petit $|AA|\le M|A|$ 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}{|AA|}^{5}\gtrsim {|A|}^{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}{|A|}^{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}{|A|}^{8/5}$.

Ces bornes, avec $M=1$, s’appliquent également aux sous-groupes multiplicatifs de ${𝔽}_{p}^{×}$ 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)$.

Revised:
Accepted:
Published online:
DOI: 10.5802/jtnb.1095
Classification: 11B13, 11B50, 11B75
Keywords: Sum–product phenomenon, multiplicative subgroups, additive energy
Brendan Murphy 1; Misha Rudnev 2; Ilya Shkredov 3, 4, 5; Yuri Shteinikov 6

1 Heilbronn Institute for Mathematical Research School of Mathematics, University Walk Bristol BS8 1TW, UK
2 School of Mathematics University Walk Bristol BS8 1TW, UK
3 IITP RAS Bolshoy Karetny per. 19 127994 Moscow, Russia
4 MIPT Institutskii per. 9 141701 Dolgoprudnii, Russia
5 Steklov Mathematical Institute Gubkina 8 119991 Moscow, Russia
6 SRISA Nahimovsky prosp. 36, building 1 117218 Moscow, Russia
License: CC-BY-ND 4.0
@article{JTNB_2019__31_3_573_0,
author = {Brendan Murphy and Misha Rudnev and Ilya Shkredov and Yuri Shteinikov},
title = {On the few products, many sums problem},
journal = {Journal de th\'eorie des nombres de Bordeaux},
pages = {573--602},
publisher = {Soci\'et\'e Arithm\'etique de Bordeaux},
volume = {31},
number = {3},
year = {2019},
doi = {10.5802/jtnb.1095},
mrnumber = {4102615},
zbl = {1454.11025},
language = {en},
url = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.1095/}
}
TY  - JOUR
AU  - Brendan Murphy
AU  - Misha Rudnev
AU  - Ilya Shkredov
AU  - Yuri Shteinikov
TI  - On the few products, many sums problem
JO  - Journal de théorie des nombres de Bordeaux
PY  - 2019
SP  - 573
EP  - 602
VL  - 31
IS  - 3
PB  - Société Arithmétique de Bordeaux
UR  - https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.1095/
DO  - 10.5802/jtnb.1095
LA  - en
ID  - JTNB_2019__31_3_573_0
ER  - 
%0 Journal Article
%A Brendan Murphy
%A Misha Rudnev
%A Ilya Shkredov
%A Yuri Shteinikov
%T On the few products, many sums problem
%J Journal de théorie des nombres de Bordeaux
%D 2019
%P 573-602
%V 31
%N 3
%I Société Arithmétique de Bordeaux
%U https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.1095/
%R 10.5802/jtnb.1095
%G en
%F JTNB_2019__31_3_573_0
Brendan Murphy; Misha Rudnev; Ilya Shkredov; Yuri Shteinikov. On the few products, many sums problem. Journal de théorie des nombres de Bordeaux, Volume 31 (2019) no. 3, pp. 573-602. doi : 10.5802/jtnb.1095. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.1095/

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

 Jean Bourgain; Mei-Chu Chang 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

 Jean Bourgain; Sergeĭ V. Konyagin; Igor E. Shparlinski 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

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

 Javier Cilleruelo; Moubariz Z. Garaev The congruence ${x}^{x}=\lambda \phantom{\rule{4.44443pt}{0ex}}\left(mod\phantom{\rule{0.277778em}{0ex}}p\right)$, Proc. Am. Math. Soc., Volume 144 (2016) no. 6, pp. 2411-2418 | DOI | Zbl

 Javier Cilleruelo; Moubariz Z. Garaev 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

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

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

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

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

 Andrew Granville; József Solymosi 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

 David R. Heath-Brown; Sergeĭ V. Konyagin 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

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

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

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

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

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

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

 Simon Macourt; Il’ya D. Shkredov; Igor E. Shparlinski 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.) | Zbl

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

 Dmitriĭ Alekseevich Mit’kin 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

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

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

 Francesco Pappalardi On the order of finitely generated subgroups of ${ℚ}^{*}\left(\mathrm{mod}\phantom{\rule{4pt}{0ex}}p\right)$ and divisors of $p-1$, J. Number Theory, Volume 57 (1996) no. 2, pp. 207-222 | DOI | MR | Zbl

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

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

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

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

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

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

 Il’ya D. Shkredov 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Cited by Sources: