In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern 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 ...
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 arithmetic function, integer-valued functions. German mathematician Carl Friedrich Gauss (1777â ...
,
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 appl ...
,
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 Function (mathematics), functions or signals as the Superposition principle, superposition of basic waves, and the study of and generalization of the notions of Fo ...
.
Scope
Arithmetic combinatorics is about combinatorial estimates associated with arithmetic operations (addition, subtraction, multiplication, and division).
Additive combinatorics
Additive combinatorics is an area of combinatorics in mathematics. One major area of study in additive combinatorics are ''inverse problems'': given the size of the sumset ''A'' + ''B'' is small, what can we say about the structures of A ...
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
''Tao'' or ''Dao'' is the natural order of the universe, whose character one's intuition must discern to realize the potential for individual wisdom, as conceived in the context of East Asian philosophy, East Asian religions, or any other phil ...
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''-ter ...
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
ErdĆs, Erdos, or Erdoes is a Hungarian surname.
People with the surname include:
* Ăgnes ErdĆs (born 1950), Hungarian politician
* Brad Erdos (born 1990), Canadian football player
* Ăva ErdĆs (born 1964), Hungarian handball player
* JĂłzse ...
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 de ...
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, ea ...
.
GreenâTao theorem and extensions
The
GreenâTao theorem In number theory, the GreenâTao theorem, proved by Ben Green and Terence Tao in 2004, states that the sequence of prime numbers contains arbitrarily long arithmetic progressions. In other words, for every natural number ''k'', there exist arith ...
, proved by
Ben Green and
Terence Tao
Terence Chi-Shen Tao (; born 17 July 1975) is an Australian-American mathematician. He is a professor of mathematics at the University of California, Los Angeles (UCLA), where he holds the James and Carol Collins chair. His research includes ...
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 ways ...
s contains arbitrarily long
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 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 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''-ter ...
.
In 2006, Terence Tao and
Tamar Ziegler
Tamar Debora Ziegler (; born 1971) is an Israeli mathematician known for her work in ergodic theory, combinatorics and number theory. She holds the Henry and Manya Noskwith Chair of Mathematics at the Einstein Institute of Mathematics at the He ...
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 t ...
s ''P''
1,..., ''P''
''k'' in one unknown ''m'' all with constant term 0, there are infinitely many integers ''x'', ''m'' such that ''x'' + ''P''
1(''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
Emmanuel Breuillard (born 25 June 1977) is a French mathematician. He was the Sadleirian Professor of Pure Mathematics in the
Department of Pure Mathematics and Mathematical Statistics (DPMMS) at the University of Cambridge, and is now Professor ...
,
Ben Green, and
Terence Tao
Terence Chi-Shen Tao (; born 17 July 1975) is an Australian-American mathematician. He is a professor of mathematics at the University of California, Los Angeles (UCLA), where he holds the James and Carol Collins chair. His research includes ...
in 2011, gives a complete classification of approximate groups. This result can be seen as a nonabelian version of
Freiman's theorem
In additive combinatorics, Freiman's theorem is a central result which indicates the approximate structure of sets whose sumset is small. It roughly states that if , A+A, /, A, is small, then A can be contained in a small generalized arithmetic p ...
, 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.
Statement ...
.
Example
If ''A'' is a set of ''N'' integers, how large or small can the
sumset In additive combinatorics, the sumset (also called the Minkowski sum) of two subsets A and B of an abelian group G (written additively) is defined to be the set of all sums of an element from A with an element from B. That is,
:A + B = \.
The n-f ...
:
the difference set
:
and the product set
:
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 ...
and
product set
In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''Ă''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is
: A\tim ...
can have other meanings.)
Extensions
The sets being studied may also be subsets of algebraic structures other than the integers, for example,
groups
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic ide ...
,
rings
Ring may refer to:
* Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry
* To make a sound with a bell, and the sound made by a bell
:(hence) to initiate a telephone connection
Arts, entertainment and media Film and ...
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 b ...
.
See also
*
Additive number theory
Additive number theory is the subfield of number theory concerning the study of subsets of integers and their behavior under addition. More abstractly, the field of additive number theory includes the study of abelian groups and commutative semigr ...
*
Approximate group In mathematics, an approximate group is a subset of a group which behaves like a subgroup "up to a constant error", in a precise quantitative sense (so the term approximate subgroup may be more correct). For example, it is required that the set of ...
*
Corners theorem In arithmetic combinatorics, the corners theorem states that for every \varepsilon>0, for large enough N, any set of at least \varepsilon N^2 points in the N\times N grid \^2 contains a corner, i.e., a triple of points of the form \ with h\ne 0. It ...
*
Ergodic Ramsey theory Ergodic Ramsey theory is a branch of mathematics where problems motivated by additive combinatorics are proven using ergodic theory.
History
Ergodic Ramsey theory arose shortly after Endre Szemerédi's proof that a set of positive upper density ...
*
Problems involving arithmetic progressions
Problems involving arithmetic progressions are of interest in number theory,
combinatorics, and computer science, both from theoretical and applied points of view.
Largest progression-free subsets
Find the cardinality (denoted by ''A'k''(''m' ...
*
Schnirelmann density
In additive number theory, the Schnirelmann density of a sequence of numbers is a way to measure how "dense" the sequence is. It is named after Russian mathematician Lev Schnirelmann, who was the first to study it.Schnirelmann, L.G. (1930).On the ...
*
ShapleyâFolkman lemma
The ShapleyâFolkman lemma is a result in convex geometry that describes the Minkowski addition of sets in a vector space. It is named after mathematicians Lloyd Shapley and Jon Folkman, but was first published by the economist Ros ...
*
Sidon set
*
Sum-free set In additive combinatorics and number theory, a subset ''A'' of an abelian group ''G'' is said to be sum-free if the sumset ''A'' + ''A'' is disjoint from ''A''. In other words, ''A'' is sum-free if the equation a + b = c has no solution with a,b, ...
*
Sum-product problem
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
Terence Chi-Shen Tao (; born 17 July 1975) is an Australian-American mathematician. He is a professor of mathematics at the University of California, Los Angeles (UCLA), where he holds the James and Carol Collins chair. His research includes ...
, AMS Notices March 2001
*
*
*
*
*
Further reading
Some Highlights of Arithmetic Combinatorics resources by
Terence Tao
Terence Chi-Shen Tao (; born 17 July 1975) is an Australian-American mathematician. He is a professor of mathematics at the University of California, Los Angeles (UCLA), where he holds the James and Carol Collins chair. His research includes ...
Additive Combinatorics: Winter 2007 K Soundararajan
Earliest Connections of Additive Combinatorics and Computer Science Luca Trevisan
{{Number theory
Additive number theory
Sumsets
Harmonic analysis
Ergodic theory
Additive combinatorics