COMPRESSIONS, CONVEX GEOMETRY AND THE FREIMAN–BILU THEOREM

Brian Green, Terence Tao

Type: Article

Publication Date: 2006-05-15

Citations: 48

DOI: https://doi.org/10.1093/qmath/hal009

Abstract

We note a link between combinatorial results of Bollobás and Leader concerning sumsets in the grid, the Brunn–Minkowski theorem and a result of Freiman and Bilu concerning the structure of sets A ⊆ ℤ with small doubling. Our main result is the following. If ε > 0 and if A is a finite non-empty subset of a torsion-free abelian group with |A + A| ≤ K|A|, then A may be covered by eKO(1) progressions of dimension ⌊ log 2 K + ε ⌋ and size at most |A|.

Locations

The Quarterly Journal of Mathematics - View
arXiv (Cornell University) - View - PDF
The Quarterly Journal of Mathematics - View
arXiv (Cornell University) - View - PDF

Similar Works

Action	Title	Year	Authors
+	Compressions, convex geometry and the Freiman-Bilu theorem	2005	Ben Green Terence Tao
+	Set addition in boxes and the Freiman-Bilu theorem	2005	Ben Green
+	Freiman's Theorem in an arbitrary abelian group	2005	Ben Green Imre Z. Ruzsa
+ PDF Chat	On the structure of sets of large doubling	2011	Allison Lewko Mark Lewko
+ PDF	Structure in Sets with Logarithmic Doubling	2011	Tom Sanders
+	Small doubling in groups with moderate torsion	2020	Vsevolod F. Lev
+	Small doubling in groups with moderate torsion	2020	Vsevolod F. Lev
+	Sets in $\mathbb{Z}^k$ with doubling $2^k+\delta$ are near convex progressions	2020	Peter van Hintum Hunter Spink Marius Tiba
+ PDF Chat	SETS WITH SMALL SUMSET AND RECTIFICATION	2006	Ben Green Imre Z. Ruzsa
+ PDF	A NOTE ON THE FREIMAN AND BALOG–SZEMERÉDI–GOWERS THEOREMS IN FINITE FIELDS	2009	Benjamin Green Terence Tao
+	Sets in $\mathbb{Z}^k$ with doubling $2^k+δ$ are near convex progressions	2020	Peter van Hintum Hunter Spink Marius Tiba
+	On sets with small sumset in the circle	2017	Pablo Candela Anne de Roton
+	SETS WITH SMALL SUMSET AND RECTIFICATION	2006	Ben Green Imre Z. Ruzsa
+	Sets with small sumset and rectification	2004	Ben Green Imre Z. Ruzsa
+ PDF	On the Bogolyubov–Ruzsa lemma	2012	Tom Sanders
+	A note on the Freiman and Balog-Szemeredi-Gowers theorems in finite fields	2007	Ben Green Terence Tao
+	On the Structure of Sets of Large Doubling	2010	Allison Lewko Mark Lewko
+	Coset Progressions and Bohr Sets	2019	Matthew Tointon
+	Small doubling in cyclic groups	2020	Vsevolod F. Lev
+	On the Structure of Sets of Large Doubling	2010	Allison Lewko Mark Lewko

Works That Cite This (48)

Action	Title	Year	Authors
+	On Rogers-Shephard type inequalities for the lattice point enumerator	2021	David Alonso–Gutiérrez Eduardo Lucas Jesús Yepes Nicolás
+ PDF	EXPANDING POLYNOMIALS ON SETS WITH FEW PRODUCTS	2019	Cosmin Pohoata
+	Quantitative bounds for Gowers uniformity of the Möbius and von Mangoldt functions	2021	Terence Tao Joni Teräväinen
+	Brunn-Minkowski type inequalities for the lattice point enumerator	2019	David Iglesias Jesús Yepes Nicolás Artem Zvavitch
+	FROM HARMONIC ANALYSIS TO ARITHMETIC COMBINATORICS	2007	Izabella Łaba
+ PDF Chat	Properties of two-dimensional sets with small sumset	2009	David J. Grynkiewicz Oriol Serra
+	Brunn-Minkowski type inequalities for the lattice point enumerator	2020	David Iglesias Jesús Yepes Nicolás Artem Zvavitch
+	Sums of finite subsets in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" id="d1e19" altimg="si6.gif"><mml:msup><mml:mrow><mml:mi mathvariant="double-struck">R</mml:mi></mml:mrow><mml:mrow><mml:mi>d</mml:mi></mml:mrow></mml:msup></mml:math>	2019	Mario Huicochea
+ PDF	An Analytic Approach to Cardinalities of Sumsets	2022	Dávid Matolcsi Imre Z. Ruzsa George Shakan Dmitrii Zhelezov
+ PDF	On a Characterization of Lattice Cubes via Discrete Isoperimetric Inequalities	2023	David Iglesias Eduardo Lucas

Works Cited by This (18)

Action	Title	Year	Authors
+	Long arithmetic progressions in sumsets: Thresholds and bounds	2005	Endre Szemerédi Van Vu
+ PDF	On the size of $k$-fold sum and product sets of integers	2003	Jean Bourgain Mei-Chu Chang
+	Sum of sets in several dimensions	1994	Imre Z. Ruzsa
+	An Application of Graph Theory to Additive Number Theory	1985	Noga Alon P. Erdős
+	Generalized arithmetical progressions and sumsets	1994	Imre Z. Ruzsa
+ PDF	The Brunn-Minkowski inequality	2002	Richard J. Gardner
+	Sums in the grid	1996	Béla Bollobás Imre Leader
+	Finite field models in additive combinatorics	2005	Ben Green
+	Long arithmetic progressions in sum-sets and the number x-sum-free sets	2005	Endre Szemerédi Van H. Vu
+ PDF	Finite and infinite arithmetic progressions in sumsets	2006	Endre Szemerédi Van H. Vu