In mathematics, Freiman's theorem is a combinatorial result in additive 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
is small, in the sense that
for some constant
that contains A, and such that c' and n depend only on c.
A simple instructive case is the following. We always have
with equality precisely when A is an arithmetic progression.
This result is due to Gregory Freiman (1964,1966). Much interest in it, and applications, stemmed from a new proof by Imre Z. Ruzsa (1994).
Green and Ruzsa (2007) generalized the theorem for arbitrary abelian groups: here A can be contained in the sum of a generalized arithmetic progression and a subgroup — the name of such sets is coset-progression.