Arithmetic combinatorics

From Wikipedia, the free encyclopedia
  (Redirected from Additive combinatorics)
Jump to: navigation, search

In mathematics, arithmetic combinatorics is a field in the intersection of number theory, combinatorics, ergodic theory and harmonic analysis.

Scope[edit]

Arithmetic combinatorics is about combinatorial estimates associated with arithmetic operations (addition, subtraction, multiplication, and division). Additive combinatorics is the special case when only the operations of addition and subtraction are involved.

Arithmetic combinatorics is explained in Green's review of "Additive Combinatorics" by Tao and Vu.

Important results[edit]

Szemerédi's theorem[edit]

Main article: Szemerédi's theorem

Szemerédi's theorem is a result in arithmetic combinatorics concerning arithmetic progressions in subsets of the integers. In 1936, Erdős and Turán conjectured[1] that every set of integers A with positive natural density contains a k term arithmetic progression for every k. This conjecture, which became Szemerédi's theorem, generalizes the statement of van der Waerden's theorem.

Green-Tao theorem and extensions[edit]

Main article: Green-Tao theorem

The Green–Tao theorem, proved by Ben Green and Terence Tao in 2004,[2] states that the sequence of prime numbers contains arbitrarily long arithmetic progressions. In other words there exist arithmetic progressions of primes, with k terms, where k can be any natural number. The proof is an extension of Szemerédi's theorem.

In 2006, Terence Tao and Tamar Ziegler extended the result to cover polynomial progressions.[3] More precisely, given any integer-valued polynomials P1,..., Pk in one unknown m all with constant term 0, there are infinitely many integers x, m such that x + P1(m), ..., x + Pk(m) are simultaneously prime. The special case when the polynomials are m, 2m, ..., km implies the previous result that there are length k arithmetic progressions of primes.

Example[edit]

If A is a set of N integers, how large or small can the sumset

A+A := \{x+y: x,y \in A\},

the difference set

A-A := \{x-y: x,y \in A\},

and the product set

A\cdot A := \{xy: x,y \in A\}

be, and how are the sizes of these sets related? (Not to be confused: the terms difference set and product set can have other meanings.)

Extensions[edit]

The sets being studied may also be subsets of algebraic structures other than the integers, for example, groups, rings and fields.[4]

See also[edit]

Notes[edit]

  1. ^ Erdős, Paul; Turán, Paul (1936). "On some sequences of integers" (PDF). Journal of the London Mathematical Society 11 (4): 261–264. doi:10.1112/jlms/s1-11.4.261. MR 1574918. .
  2. ^ Green, Ben; Tao, Terence (2008). "The primes contain arbitrarily long arithmetic progressions". Annals of Mathematics 167 (2): 481–547. arXiv:math.NT/0404188. doi:10.4007/annals.2008.167.481. MR 2415379. .
  3. ^ Tao, Terence; Ziegler, Tamar (2008). "The primes contain arbitrarily long polynomial progressions". Acta Mathematica 201 (2): 213–305. arXiv:math.NT/0610050. doi:10.1007/s11511-008-0032-5. MR 2461509. .
  4. ^ Bourgain, Jean; Katz, Nets; Tao, Terence (2004). "A sum-product estimate in finite fields, and applications". Geometric and Functional Analysis 14 (1): 27–57. doi:10.1007/s00039-004-0451-1. MR 2053599. 

References[edit]

Further reading[edit]