Additive combinatorics is an area of
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 ...
in
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 ...
. One major area of study in additive combinatorics are ''inverse problems'': given the size of the
sumset is small, what can we say about the structures of and ? In the case of the integers, the classical
Freiman's theorem provides a partial answer to this question in terms of
multi-dimensional arithmetic progressions.
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
In additive number theory and additive combinatorics, combinatorics, a restricted sumset has the form
:S=\,
where A_1,\ldots,A_n are finite empty set, nonempty subsets of a field (mathematics), field ''F'' and P(x_1,\ldots,x_n) is a polynomial ...
(for a
restricted sumset) 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 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 ...
,
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 and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
,
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-algebraic and polynomial methods.
History of additive combinatorics
Although additive combinatorics is a fairly new branch of combinatorics (the term ''additive combinatorics'' was coined by
Terence Tao and
Van H. Vu in their 2006 book of the same name), a much older problem, the
Cauchy–Davenport theorem, is one of the most fundamental results in this field.
Cauchy–Davenport theorem
Suppose that ' and ' are finite subsets of the
cyclic group
In abstract algebra, a cyclic group or monogenous group is a Group (mathematics), group, denoted C_n (also frequently \Z_n or Z_n, not to be confused with the commutative ring of P-adic number, -adic numbers), that is Generating set of a group, ge ...
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. 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 ' and ' 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 ' and ' to be
:
The -fold sumset of the set with itself is denoted by
:
which must not be confused with
:
Doubling constant
Let ' be a subset of an abelian group. The doubling constant measures how big the sum set
is compared to its original size . We define the doubling constant of to be
:
Ruzsa distance
Let ' and ' be two subsets of an abelian group. We define the Ruzsa distance between these two sets to be the quantity
:
The
Ruzsa triangle inequality asserts that the Ruzsa distance obeys the triangle inequality:
:
However, since cannot be zero, the Ruzsa distance is not actually a
metric
Metric or metrical may refer to:
Measuring
* Metric system, an internationally adopted decimal system of measurement
* An adjective indicating relation to measurement in general, or a noun describing a specific type of measurement
Mathematics
...
.
See also
*
Arithmetic combinatorics
*
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 semigro ...
References
Citations
* Tao, T., & Vu, V. (2006). ''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