Freiman's theorem
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 integer
s 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
. There exists an n-dimensional arithmetic progression
of length
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).
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, Freiman's theorem is a combinatorial result in number theory
Number theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
. In a sense it accounts for the approximate structure of sets of integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s 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
Sumset
In additive combinatorics, the sumset of two subsets A and B of an abelian group G is defined to be the set of all sums of an element from A with an element from B...
is small, in the sense that
for some constant
. There exists an n-dimensional arithmetic progressionGeneralized arithmetic progression
In mathematics, a multiple arithmetic progression, generalized arithmetic progression, or k-dimensional arithmetic progression, is a set of integers constructed as an arithmetic progression is, but allowing several possible differences. So, for example, we start at 17 and may add a multiple of 3 or...
of length
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
Imre Z. Ruzsa
Imre Z. Ruzsa is a Hungarian mathematician specializing in number theory.Ruzsa participated in the International Mathematical Olympiad for Hungary, winning a silver medal in 1969, and two consecutive gold medals with perfect scores in 1970 and 1971. He graduated from the Eötvös Loránd University...
(1994).