mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

arithmetic Arithmetic is an elementary branch of mathematics that deals with numerical operations like addition, subtraction, multiplication, and division. In a wider sense, it also includes exponentiation, extraction of roots, and taking logarithms. ...

combinatorics is a field in the intersection of

number theory Number theory is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic functions. Number theorists study prime numbers as well as the properties of mathematical objects constructed from integers (for example ...

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

ergodic theory Ergodic theory is a branch of mathematics that studies statistical properties of deterministic dynamical systems; it is the study of ergodicity. In this context, "statistical properties" refers to properties which are expressed through the behav ...

and

harmonic analysis Harmonic analysis is a branch of mathematics concerned with investigating the connections between a function and its representation in frequency. The frequency representation is found by using the Fourier transform for functions on unbounded do ...

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 The Tao or Dao is the natural way of the universe, primarily as conceived in East Asian philosophy and religion. This seeing of life cannot be grasped as a concept. Rather, it is seen through actual living experience of one's everyday being. T ...

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

is a result in arithmetic combinatorics concerning

arithmetic progression An arithmetic progression or arithmetic sequence is a sequence of numbers such that the difference from any succeeding term to its preceding term remains constant throughout the sequence. The constant difference is called common difference of that ...

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

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 Van der Waerden's theorem is a theorem in the branch of mathematics called Ramsey theory. Van der Waerden's theorem states that for any given positive integers ''r'' and ''k'', there is some number ''N'' such that if the integers are colored, eac ...

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 (mathematics), 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 ...

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 polynomial In mathematics, an integer-valued polynomial (also known as a numerical polynomial) P(t) is a polynomial whose value P(n) is an integer for every integer ''n''. Every polynomial with integer coefficients is integer-valued, but the converse is not tr ...

s ''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 In geometric group theory, Gromov's theorem on groups of polynomial growth, first proved by Mikhail Gromov, characterizes finitely generated groups of ''polynomial'' growth, as those groups which have nilpotent subgroups of finite index. Statemen ...

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 cardinality, size k of a group (mathematics), group G of order of a group, order v such that every non-identity element, identity element of G can be expressed as a product d_1d_2^ o ...

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 Fields may refer to: Music *Fields (band), an indie rock band formed in 2006 * Fields (progressive rock band), a progressive rock band formed in 1971 * ''Fields'' (album), an LP by Swedish-based indie rock band Junip (2010) * "Fields", a song by ...

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 * * * * *