On the few products, many sums problem
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 |AA|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|A|10

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

E(A)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| M |A| 8/5 .

Ces bornes, avec M=1, s’appliquent également aux sous-groupes multiplicatifs de 𝔽 p × d’ordre O(p). 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 Ω(p).

We prove new quantitative estimates on additive properties of finite sets A with small multiplicative doubling |AA|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|A|10,

over the reals, “redistributing” the exponents in the textbook Elekes sum-product inequality and the new best known additive energy bound E(A) M |A| 49/20 , which aligns, in a sense to be discussed, with the best known sum set bound |A+A| M |A| 8/5 .

These bounds, with M=1, also apply to multiplicative subgroups of 𝔽 p × , whose order is O(p). We adapt the above energy bound to larger subgroups and obtain new bounds on gaps between elements in cosets of subgroups of order Ω(p).

Reçu le :
Révisé le :
Accepté le :
Publié le :
DOI : https://doi.org/10.5802/jtnb.1095
Classification : 11B13,  11B50,  11B75
Mots clés : Sum–product phenomenon, multiplicative subgroups, additive energy
@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},
     language = {en},
     url = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.1095/}
}
Brendan Murphy; Misha Rudnev; Ilya Shkredov; Yuri Shteinikov. On the few products, many sums problem. Journal de Théorie des Nombres de Bordeaux, Tome 31 (2019) no. 3, pp. 573-602. doi : 10.5802/jtnb.1095. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.1095/

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

[2] 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 | Article | MR 2051619 | Zbl 1034.05003

[3] 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 1232.11003

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

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

[6] 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 | Article | MR 3479546 | Zbl 1371.11003

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

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

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

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

[11] 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 | Article | MR 3526419 | Zbl 1407.11043

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

[13] 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 1123.11027

[14] 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 3488800 | Zbl 1366.11054

[15] 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 3628494

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

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

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

[19] 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.)

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

[21] 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 1113.11037

[22] 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 | Article | MR 3935815 | Zbl 1429.11027

[23] 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 | Article | MR 3691216 | Zbl 1370.11022

[24] Francesco Pappalardi On the order of finitely generated subgroups of * (modp) and divisors of p-1, J. Number Theory, Volume 57 (1996) no. 2, pp. 207-222 | Article | MR 2257550 | Zbl 0847.11049

[25] 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 | Article | MR 3474329 | Zbl 1412.11018

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

[27] 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.)

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

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

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

[31] 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 2904042 | Zbl 1313.11032

[32] 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 3284125 | Zbl 1382.11017

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

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

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

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

[37] 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 3598750 | Zbl 06727035

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

[39] 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 07013435

[40] 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 | Article | MR 3438516 | Zbl 1358.11094

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

[42] 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 | Zbl 1192.05017

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

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

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