Freiman's theorem

In mathematics, Freiman's theorem is a combinatorial result in number theory. It in a sense accounts for the approximate structure of sets of integers which 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.

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

References

* Melvyn B. Nathanson, Additive Number Theory: Inverse Problems and Geometry of Sumsets volume 165 of GTM. Springer, 1996. Zbl 0859.11003.

Number Theory