In mathematics,

arithmetic Arithmetic () is an elementary part of mathematics that consists of the study of the properties of the traditional operations on numbers—addition, subtraction, multiplication, division, exponentiation, and extraction of roots. In the 19th c ...

combinatorics is a field in the intersection of

number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Math ...

combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many a ...

ergodic theory Ergodic theory (Greek: ' "work", ' "way") is a branch of mathematics that studies statistical properties of deterministic dynamical systems; it is the study of ergodicity. In this context, statistical properties means properties which are expres ...

and

harmonic analysis Harmonic analysis is a branch of mathematics concerned with the representation of functions or signals as the superposition of basic waves, and the study of and generalization of the notions of Fourier series and Fourier transforms (i.e. an e ...

Scope

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. Ben Green explains arithmetic combinatorics in his review of "Additive Combinatorics" by Tao and Vu.

Important results

Szemerédi's theorem

Szemerédi's theorem In arithmetic combinatorics, Szemerédi's theorem is a result concerning arithmetic progressions in subsets of the integers. In 1936, Erdős and Turán conjectured that every set of integers ''A'' with positive natural density contains a ''k''-t ...

is a result in arithmetic combinatorics concerning

arithmetic progression An arithmetic progression or arithmetic sequence () is a sequence of numbers such that the difference between the consecutive terms is constant. For instance, the sequence 5, 7, 9, 11, 13, 15, . . . is an arithmetic progression with a common differ ...

s in subsets of the integers. In 1936, Erdős and Turán conjectured. that every set of integers ''A'' with positive

natural density In number theory, natural density (also referred to as asymptotic density or arithmetic density) is one method to measure how "large" a subset of the set of natural numbers is. It relies chiefly on the probability of encountering members of the ...

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

The Green–Tao theorem, proved by Ben Green and Terence Tao in 2004, states that the sequence of

prime number A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only way ...

s contains arbitrarily long

s. 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

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

Breuillard–Green–Tao theorem

The Breuillard–Green–Tao theorem, proved by Emmanuel Breuillard, Ben Green, and Terence Tao in 2011, gives a complete classification of approximate groups. This result can be seen as a nonabelian version of Freiman's theorem, and a generalization of Gromov's theorem on groups of polynomial growth.

Example

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

A+A := \,

the difference set :

A-A := \,

and the product set :

A\cdot A := \

be, and how are the sizes of these sets related? (Not to be confused: the terms

difference set In combinatorics, a (v,k,\lambda) difference set is a subset D of size k of a group G of order v such that every nonidentity element of G can be expressed as a product d_1d_2^ of elements of D in exactly \lambda ways. A difference set D is said to ...

and product set can have other meanings.)

Extensions

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

Notes

References

*
Additive Combinatorics and Theoretical Computer Science
Luca Trevisan, SIGACT News, June 2009 *
Open problems in additive combinatorics
E Croot, V Lev
From Rotating Needles to Stability of Waves: Emerging Connections between Combinatorics, Analysis, and PDE
Terence Tao, AMS Notices March 2001 * * * * *