Freiman's theorem

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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

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.[1]

A simple instructive case is the following. We always have

|A + A| \ge 2|A|-1

with equality precisely when A is an arithmetic progression.

This result is due to Gregory Freiman (1964,1966).[2] Much interest in it, and applications, stemmed from a new proof by Imre Z. Ruzsa (1994).

See also[edit]


  1. ^ Nathanson (1996) p.251
  2. ^ Nathanson (1996) p.252

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