Freiman's theorem

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 . There exists an n-dimensional arithmetic progression of length

that contains A, and such that c' and n depend only on c.[1]

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).[2] Much interest in it, and applications, stemmed from a new proof by Imre Z. Ruzsa (1994). Mei-Chu Chang proved new polynomial estimates for the size of arithmetic progressions arising in the theorem in 2002. [3]

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.

See also

References

  1. Nathanson (1996) p.251
  2. Nathanson (1996) p.252
  3. Chang, Mei-Chu (2002). "A polynomial bound in Freiman's theorem". Duke Math. J. 113 (3): 399–419. MR 1909605.

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.