Freiman's theorem

In mathematics, Freiman's theorem is a combinatorial result in number theory. In a sense it accounts for the approximate structure of sets of integers that contain a high proportion of their internal sums, taken two at a time.

The formal statement is:

Let A be a finite set of integers such that the sumset

$A + A\,$

is small, in the sense that

$|A + A| < c|A|\,$

for some constant $c$. There exists an n-dimensional arithmetic progression of length

$c' |A|\,$

that contains A, and such that c' and n depend only on c.

A simple instructive case is the following. We always have |A+A| ≥ 2|A|-1, with equality precisely when A is an arithmetic progression.

This result is due to G. A. Freiman (1966). Much interest in it, and applications, stemmed from a new proof by Imre Z. Ruzsa (1994).

See also

• Markov spectrum

References

• G. A. Freiman, "Foundations of a Structural Theory of Set Addition" (in Russian), Kazan Gos. Ped. Inst. (Kazan, 1966), pp 140.
• G. A. Freiman: Structure theory of set addition, Astérisque, 258(1999), 1–33.
• Nathanson, Melvyn B. (1996). Additive Number Theory: Inverse Problems and Geometry of Sumsets. Graduate Texts in Mathematics. 165. Springer. Zbl 0859.11003. 
• Imre Z. Ruzsa, "Generalized arithmetical progressions and sumsets", Acta Mathematica Hungarica 65:4 (1994), pp. 379–388.

This article incorporates material from Freiman's theorem on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.