Sets with Small Sumset and Rectification

By Ben Joseph Green, Imre Z. Ruzsa. 2004

73 citations recorded by the source corpus.

We study the extent to which sets A ⊆ Z/NZ, N prime, resemble sets of integers from the additive point of view (‘up to Freiman isomorphism’). We give a direct proof of a result of Freiman, namely that if |A + A| ⩽ K|A| and |A| < c(K)N, then A is Freiman isomorphic to a set of integers. Because we avoid appealing to Freiman's structure theorem, we obtain a reasonable bound: we can take c(K)⩾ (32K)−12K2 . As a byproduct of our argument we obtain a sharpening of the second author's result on sets with small sumset in torsion groups. For example, if A ⊆ F2n , and if |A + A| ⩽ K|A|, then A is contained in a coset of a subspace of size no more than K222K2−2|A| . 2000 Mathematics Subject Classification 11B75.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/7790b451f61b69d93f61c9843f66aaea8d4ffb67

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Discrete Mathematics and Combinatorics

In Geometry and Topology

Citations in the corpus

A Probabilistic Technique for Finding Almost-Periods of Convolutions (2010, unknown): “progress was made on this question by �Luczak and Schoen [�LuS], who also noted that work of Green and Ruzsa [ GR2 ] implies that one can always find an x ∈ A + A with 1A ∗ 1A(x) max 1, |A|/(log2 p) 1/2+o(1) . The results of this paper can be used”
The structure theory of set addition revisited (2012, background): “A refined covering argument of Green and Ruzsa [GR06] gives the best known result following from covering techniques, while the best known upper bound by any argument is due to Schoen [Sch11] who showed that the group generated by A has size at most r 1`op1q|A|.”
Freiman's theorem in an arbitrary abelian group (2005, background): “We will also draw on results from [8], and for these reasons this paper is far from self-contained.”
On the Bogolyubov–Ruzsa lemma (2010, methodology): “The above lemma is particularly useful for controlling the order of relative polynomial growth through the next result, an idea which was introduced by Green and Ruzsa in [GR06].”