Arithmetic combinatorics
   HOME

TheInfoList



OR:

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