Additive combinatorics is an area of
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 ...
in mathematics. One major area of study in additive combinatorics are ''inverse problems'': given the size of 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 ...
''A'' + ''B'' is small, what can we say about the structures of
and
? In the case of the integers, the classical
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 ...
provides a partial answer to this question in terms of
multi-dimensional arithmetic progression
In mathematics, a generalized arithmetic progression (or multiple arithmetic progression) is a generalization of an arithmetic progression equipped with multiple common differences – whereas an arithmetic progression is generated by a single c ...
s.
Another typical problem is to find a lower bound for
in terms of
and
. This can be viewed as an inverse problem with the given information that
is sufficiently small and the structural conclusion is then of the form that either
or
is the empty set; however, in literature, such problems are sometimes considered to be direct problems as well. Examples of this type include the
Erdős–Heilbronn Conjecture (for a
restricted sumset
In additive number theory and combinatorics, a restricted sumset has the form
:S=\,
where A_1,\ldots,A_n are finite nonempty subsets of a field ''F'' and P(x_1,\ldots,x_n) is a polynomial over ''F''.
If P is a constant non-zero function, f ...
) and the
Cauchy–Davenport Theorem. The methods used for tackling such questions often come from many different fields of mathematics, including
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 ...
,
analysis
Analysis ( : analyses) is the process of breaking a complex topic or substance into smaller parts in order to gain a better understanding of it. The technique has been applied in the study of mathematics and logic since before Aristotle (38 ...
,
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
,
group theory
In abstract algebra, group theory studies the algebraic structures known as group (mathematics), groups.
The concept of a group is central to abstract algebra: other well-known algebraic structures, such as ring (mathematics), rings, field ...
, and
linear algebra
Linear algebra is the branch of mathematics concerning linear equations such as:
:a_1x_1+\cdots +a_nx_n=b,
linear maps such as:
:(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n,
and their representations in vector spaces and through matrices.
...
ic and polynomial methods.
History of additive combinatorics
Although additive combinatorics is a fairly new branch of combinatorics (in fact the term ''additive combinatorics'' was coined 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 ...
and
Van H. Vu in their book in 2000's), an extremely old problem
Cauchy–Davenport theorem is one of the most fundamental results in this field.
Cauchy–Davenport theorem
Suppose that ''A'' and ''B'' are finite subsets of the prime order
cyclic group
In group theory, a branch of abstract algebra in pure mathematics, a cyclic group or monogenous group is a group, denoted C''n'', that is generated by a single element. That is, it is a set of invertible elements with a single associative bina ...
for a prime
, then the following inequality holds.
:
Vosper's theorem
Now we have the inequality for the cardinality of the sum set
, it is natural to ask the inverse problem, namely under what conditions on
and
does the equality hold? Vosper's theorem answers this question. Suppose that
(that is, barring edge cases) and
:
then
and
are arithmetic progressions with the same difference. This illustrates the structures that are often studied in additive combinatorics: the combinatorial structure of
as compared to the algebraic structure of arithmetic progressions.
Plünnecke–Ruzsa inequality
A useful theorem in additive combinatorics is
Plünnecke–Ruzsa inequality In additive combinatorics, the Plünnecke–Ruzsa inequality is an inequality that bounds the size of various sumsets of a set B, given that there is another set A so that A+B is not much larger than A. A slightly weaker version of this inequality w ...
. This theorem gives an upper bound on the cardinality of
in terms of the doubling constant of
. For instance using Plünnecke–Ruzsa inequality, we are able to prove a version of Freiman's Theorem in finite fields.
Basic notions
Operations on sets
Let ''A'' and ''B'' be finite subsets of an abelian group, then the sum set is defined to be
:
For example, we can write
. Similarly we can define the difference set of ''A'' and ''B'' to be
:
Here we provide other useful notations.
:
Not to be confused with
:
Doubling constant
Let ''A'' be a subset of an abelian group. The doubling constant measures how big the sum set
is compared to its original size , ''A'', . We define the doubling constant of ''A'' to be
:
Ruzsa distance
Let ''A'' and ''B'' be two subsets of an abelian group. We define the Ruzsa distance between these two sets to be the quantity
:
Ruzsa triangle inequality In additive combinatorics, the Ruzsa triangle inequality, also known as the Ruzsa difference triangle inequality to differentiate it from some of its variants, bounds the size of the difference of two sets in terms of the sizes of both their differe ...
tells us that the Ruzsa distance obeys the triangle inequality:
:
However, since
cannot be zero, note that the Ruzsa distance is not actually a metric.
References
Citations
* Tao, T., & Vu, V. (2012). ''Additive combinatorics''. Cambridge: Cambridge University Press.
* Green, B. (2009, January 15). Additive Combinatorics Book Review. Retrieved from
https://www.ams.org/journals/bull/2009-46-03/S0273-0979-09-01231-2/S0273-0979-09-01231-2.pdf.
{{reflist, 20em
Mathematical theorems
Combinatorial algorithms