On the few products, many sums problem

Brendan Murphy; Misha Rudnev; Ilya Shkredov; Yuri Shteinikov

doi:10.5802/jtnb.1095

Brendan Murphy ¹ ; Misha Rudnev ² ; Ilya Shkredov ^3,^4,⁵ ; Yuri Shteinikov ⁶

¹ Heilbronn Institute for Mathematical Research School of Mathematics, University Walk Bristol BS8 1TW, UK
² School of Mathematics University Walk Bristol BS8 1TW, UK
³ IITP RAS Bolshoy Karetny per. 19 127994 Moscow, Russia
⁴ MIPT Institutskii per. 9 141701 Dolgoprudnii, Russia
⁵ Steklov Mathematical Institute Gubkina 8 119991 Moscow, Russia
⁶ SRISA Nahimovsky prosp. 36, building 1 117218 Moscow, Russia

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

Résumé
Abstract

Nous prouvons de nouvelles estimations quantitatives pour les propriétés additives des ensembles finis à doublement multiplicatif petit $| A A | \leq 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} {| A A |}^{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}^{\times}$ d’ordre $O (\sqrt{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 $Ω (\sqrt{p})$ .

We prove new quantitative estimates on additive properties of finite sets $A$ with small multiplicative doubling $| A A | \leq 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} {| A A |}^{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}^{\times}$ , whose order is $O (\sqrt{p})$ . We adapt the above energy bound to larger subgroups and obtain new bounds on gaps between elements in cosets of subgroups of order $Ω (\sqrt{p})$ .

Reçu le : 2018-04-23
Révisé le : 2019-09-04
Accepté le : 2019-09-27
Publié le : 2020-05-06

MR Numdam Zbl

DOI : 10.5802/jtnb.1095

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

Affiliations des auteurs :

Brendan Murphy ¹ ; Misha Rudnev ² ; Ilya Shkredov ^{3, 4, 5} ; Yuri Shteinikov ⁶

¹ Heilbronn Institute for Mathematical Research School of Mathematics, University Walk Bristol BS8 1TW, UK
² School of Mathematics University Walk Bristol BS8 1TW, UK
³ IITP RAS Bolshoy Karetny per. 19 127994 Moscow, Russia
⁴ MIPT Institutskii per. 9 141701 Dolgoprudnii, Russia
⁵ Steklov Mathematical Institute Gubkina 8 119991 Moscow, Russia
⁶ SRISA Nahimovsky prosp. 36, building 1 117218 Moscow, Russia

Licence :

CC-BY-ND 4.0

Droits d'auteur : Les auteurs conservent leurs droits

@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, Tome 31 (2019) no. 3, pp. 573-602. doi : 10.5802/jtnb.1095. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.1095/

Bibliographie
Cité par

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

[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 | DOI | MR | Zbl

[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

[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 | DOI | MR | Zbl

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

[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 | DOI | MR | Zbl

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

[8] 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

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

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

[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 | DOI | MR | Zbl

[12] 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

[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

[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 | Zbl

[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

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

[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 | Zbl

[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.) | Zbl

[20] 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

[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

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

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

[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 | DOI | MR | Zbl

[26] 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

[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.) | Zbl

[28] 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

[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 | DOI | MR | Zbl

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

[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 | Zbl

[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 | Zbl

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

[34] 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

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

[36] 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

[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 | Zbl

[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 | Zbl

[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

[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 | DOI | MR | Zbl

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

[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 | DOI | Zbl

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

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

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

Cité par Sources :