Freiman's theorem
From Wikipedia, the free encyclopedia
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.
This result is due to G. A. Freiman (1966). Much interest in it, and applications, stemmed from a new proof by Imre Ruzsa.
[edit] References
- Nathanson, Melvyn B. (1996). Additive Number Theory: Inverse Problems and Geometry of Sumsets, Graduate Texts in Mathematics 165. Springer. Zbl 0859.11003.
This article incorporates material from Freiman's theorem on PlanetMath, which is licensed under the GFDL.
