Locality in sumsets

EUROCOMB’23

Peter van Hintum Peter Keevash

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-079

PDF
Abstract
Motivated by the Polynomial Freiman-Ruzsa (PFR) Conjecture, we develop a theory of locality in sumsets, with several applications to John-type approximation and stability of sets with small doubling. One highlight shows that if $A \subset \mathbb{Z}$ with $|A+A| \le (1-ε) 2^d |A|$ is non-degenerate then $A$ is covered by $O(2^d)$ translates of a $d$-dimensional generalised arithmetic progression ($d$-GAP) $P$ with $|P| \le O_{d,ε}(|A|)$; thus we obtain one of the polynomial bounds required by PFR, under the non-degeneracy assumption that $A$ is not efficiently covered by $O_{d,ε}(1)$ translates of a $(d-1)$-GAP. We also prove a stability result showing for any $ε,α>0$ that if $A \subset \mathbb{Z}$ with $|A+A| \le (2-ε)2^d|A|$ is non-degenerate then some $A‘ \subset A$ with $|A‘|>(1-α)|A|$ is efficiently covered by either a $(d+1)$-GAP or $O_{α}(1)$ translates of a $d$-GAP. This `dimension-free‘ bound for approximate covering makes for a surprising contrast with exact covering, where the required number of translates not only grows with $d$, but does so exponentially. Another highlight shows that if $A \subset \mathbb{Z}$ is non-degenerate with $|A+A| \le (2^d + \ell)|A|$ and $\ell \le 0.1 \cdot 2^d$ then $A$ is covered by $\ell+1$ translates of a $d$-GAP $P$ with $|P| \le O_d(|A|)$; this is tight, in that $\ell+1$ cannot be replaced by any smaller number. The above results also hold for $A \subset \mathbb{R}^d$, replacing GAPs by a suitable common generalisation of GAPs and convex bodies, which we call generalised convex progressions. In this setting the non-degeneracy condition holds automatically, so we obtain essentially optimal bounds with no additional assumption on $A$. Here we show that if $A\subset\mathbb{R}^k$ satisfies $|\frac{A+A}{2}|\leq (1+\delta)|A|$ with $\delta\in(0,1)$, then $\exists A‘\subset A$ with $|A‘|\geq (1-\delta)|A|$ so that $|\operatorname{co}(A‘)|\leq O_{k,1-\delta}(|A|)$. This is a dimensionally independent sharp stability result for the Brunn-Minkowski inequality for equal sets, which hints towards a possible analogue for the Prékopa-Leindler inequality. These results are all deduced from a unifying theory, in which we introduce a new intrinsic structural approximation of any set, which we call the `additive hull‘, and develop its theory via a refinement of Freiman‘s theorem with additional separation properties. A further application that will be published separately is a proof of Ruzsa‘s Discrete Brunn-Minkowski Conjecture \cite{Ruzsaconjecture}.

Pages:
568–578
References

Ben Barber, Joshua Erde, Peter Keevash, and Alexander Roberts. Isoperimetric stability in lattices. Forthcoming in the Proceedings of the American Mathematical Society, 2023+.
https://doi.org/10.1090/proc/16439

Yuri Bilu. The (α + 2β)-inequality on a torus. Journal of the London Mathematical Society, 57(3):513-528, 1998.
https://doi.org/10.1112/S0024610798006024

Yuri Bilu. Structure of sets with small sumset. Astérisque, 258(xi):77-108, 1999.

Pablo Candela and Anne De Roton. On sets with small sumset in the circle. The Quarterly Journal of Mathematics, 70(1):49-69, 2019.
https://doi.org/10.1093/qmath/hay034

Pablo Candela, Diego González-Sánchez, and David Joseph Grynkiewicz. A step towards the 3k − 4 conjecture in Z/pZ and an application to m-sum-free sets. Acta Mathematica Universitatis Comenianae, 88(3):521-525, 2019.

Mei-Chu Chang. A polynomial bound in Freiman's theorem. Duke mathematical journal, 113(3):399-419, 2002.
https://doi.org/10.1215/S0012-7094-02-11331-3

Michael Christ. Near equality in the Brunn-Minkowski inequality. arXiv preprint arXiv:1207.5062, 2012.

Michael Christ. Near equality in the two-dimensional Brunn-Minkowski inequality. arXiv preprint arXiv:1206.1965, 2012.

Pablo Candela, Oriol Serra, and Christoph Spiegel. A step beyond Freiman's theorem for set addition modulo a prime. Journal de Théorie des Nombres de Bordeaux, 32(1):275-289, 2020.
https://doi.org/10.5802/jtnb.1122

Sean Eberhard, Ben Green, and Freddie Manners. Sets of integers with no large sum-free subset. Annals of Mathematics, pages 621-652, 2014.
https://doi.org/10.4007/annals.2014.180.2.5

Alessio Figalli and David Jerison. Quantitative stability for sumsets in Rn. Journal of the European Mathematical Society, 17(5):1079-1106, 2015.
https://doi.org/10.4171/JEMS/527

Alessio Figalli and David Jerison. Quantitative stability for the Brunn-Minkowski inequality. Advances in Mathematics, 314:1-47, 2017.
https://doi.org/10.1016/j.aim.2016.12.018

Alessio Figalli and David Jerison. A sharp Freiman type estimate for semisums in two and three dimensional euclidean spaces. Annales Scientifiques de l'École Normale Supérieure, 54(4):235-257, 2021.
https://doi.org/10.24033/asens.2458

Alessio Figalli, Francesco Maggi, and Aldo Pratelli. A refined Brunn-Minkowski inequality for convex sets. In Annales de l'Institut Henri Poincaré C, Analyse non linéaire, volume 26, pages 2511-2519. Elsevier, 2009.
https://doi.org/10.1016/j.anihpc.2009.07.004

Alessio Figalli, Francesco Maggi, and Aldo Pratelli. A mass transportation approach to quantitative isoperimetric inequalities. Inventiones mathematicae, 182(1):167-211, 2010.
https://doi.org/10.1007/s00222-010-0261-z

Gregory Freiman. The addition of finite sets. i. Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika, (6):202-213, 1959.

Ben Green and Imre Ruzsa. Sets with small sumset and rectification. Bulletin of the London Mathematical Society, 38(1):43-52, 2006.
https://doi.org/10.1112/S0024609305018102

Ben Green. The polynomial Freıman-Ruzsa conjecture. Terence Tao's blog, 2007.

Ben Green and Terence Tao. Compressions, convex geometry and the Freiman-Bilu theorem. Quarterly Journal of Mathematics, 57(4):495-504, 2006.
https://doi.org/10.1093/qmath/hal009

Peter van Hintum and Peter Keevash. Locality in sumsets. arXiv preprint arXiv:2304.01189, 2023.
https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-079

Peter van Hintum and Peter Keevash. The sharp doubling threshold for approximate convexity. arXiv preprint arXiv:2304.01176, 2023.

Peter van Hintum, Peter Keevash, and Marius Tiba. On Ruzsa's discrete Brunn-Minkowski conjecture. Manuscript, 2023.

Peter van Hintum, Hunter Spink, and Marius Tiba. Sharp stability of Brunn-Minkowski for homothetic regions. Journal of the European Mathematical Society, 24(12):4207-4223, 2022.
https://doi.org/10.4171/JEMS/1185

Peter van Hintum, Hunter Spink, and Marius Tiba. Sets in Zk with doubling 2k + δ are near convex progressions. Advances in Mathematics, 413:108830, 2023.
https://doi.org/10.1016/j.aim.2022.108830

Peter van Hintum, Hunter Spink, and Marius Tiba. Sharp l1 inequalities for sup-convolution. Forthcoming in Discrete Analysis, 2023+.

Peter van Hintum, Hunter Spink, and Marius Tiba. Sharp quantitative stability of the planar Brunn-Minkowski inequality. Forthcoming in Journal of the European Mathematical Society, 2023+.

Renling Jin. Freiman's inverse problem with small doubling property. Advances in Mathematics, 216(2):711-752, 2007.
https://doi.org/10.1016/j.aim.2007.06.002

Peter Keevash. Hypergraph turan problems. Surveys in combinatorics, 392:83-140, 2011.
https://doi.org/10.1017/CBO9781139004114.004

Shachar Lovett and Oded Regev. A counterexample to a strong variant of the polynomial Freiman-Ruzsa conjecture in euclidean space. Discrete Analysis, 8:379-388, 2017.
https://doi.org/10.19086/da.1640

Vsevolod F Lev and Oriol Serra. Towards 3n − 4 in groups of prime order. arXiv preprint arXiv:2302.08465, 2023.

Francesco Maggi. Some methods for studying stability in isoperimetric type problems. Bulletin of the American Mathematical Society, 45(3):367-408, 2008.
https://doi.org/10.1090/S0273-0979-08-01206-8

DA Moskvin, Gregory Freiman, and Aleksandr Aleksandrovich Yudin. Structure theory of set addition and local limit theorems for independent lattice random variables. Theory of Probability & Its Applications, 19(1):53-64, 1974.
https://doi.org/10.1137/1119005

Imre Ruzsa. Generalized arithmetical progressions and sumsets. Acta Mathematica Hungarica, 8(4):1-6, 1994.
https://doi.org/10.1007/BF01876039

Imre Ruzsa. An analog of Freiman's theorem in groups. Astérisque, 258(199):323-326, 1999.

Imre Ruzsa. Sumsets and structure. Combinatorial number theory and additive group theory, pages 87-210, 2009.

Tom Sanders. Appendix to 'Roth's theorem on progressions revisited' by J. Bourgain. Journal d'Analyse Mathématique, 1(104):193-206, 2008.
https://doi.org/10.1007/s11854-008-0021-9

Tom Sanders. On the Bogolyubov-Ruzsa lemma. Analysis & PDE, 5(3):627-655, 2012.
https://doi.org/10.2140/apde.2012.5.627

Tomasz Schoen. Near optimal bounds in Freiman's theorem. Duke Mathematical Journal, 158(1):1-12, 2011.
https://doi.org/10.1215/00127094-1276283

Terence Tao. An inverse theorem for an inequality of Kneser. Proceedings of the Steklov Institute of Mathematics, 303(1):193-219, 2018.
https://doi.org/10.1134/S0081543818080163

Terence Tao and Van Vu. Additive combinatorics, volume 105. Cambridge University Press, 2006.

Terence Tao and Van Vu. John-type theorems for generalized arithmetic progressions and iterated sumsets. Advances in Mathematics, 219(2):428-449, 2008.
https://doi.org/10.1016/j.aim.2008.05.002

Metrics

0

Views

0

PDF views

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Copyright © 2023 Peter van Hintum, Peter Keevash

PDF