Arithmetic combinatorics

In mathematics, arithmetic combinatorics is a field in the intersection of number theory, combinatorics, ergodic theory and harmonic analysis.

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 and Vu.{{Cite journal|last=Green|first=Ben|date=July 2009|title=Book Reviews: Additive combinatorics, by Terence C. Tao and Van H. Vu|url=https://www.ams.org/journals/bull/2009-46-03/S0273-0979-09-01231-2/S0273-0979-09-01231-2.pdf|journal=Bulletin of the American Mathematical Society|volume= 46| issue = 3|pages=489–497|doi=10.1090/s0273-0979-09-01231-2|doi-access=free}}

Important results

=Szemerédi's theorem=

Szemerédi's theorem is a result in arithmetic combinatorics concerning arithmetic progressions in subsets of the integers. In 1936, Erdős and Turán conjectured{{cite journal|author-link1=Paul Erdős|first1=Paul|last1=Erdős|author-link2=Pál Turán|first2=Paul|last2=Turán|title=On some sequences of integers|journal=Journal of the London Mathematical Society|volume=11|issue=4|year=1936|pages=261–264|url=http://www.renyi.hu/~p_erdos/1936-05.pdf|mr=1574918|doi=10.1112/jlms/s1-11.4.261}}. that every set of integers A with positive natural density 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.

=Green–Tao theorem and extensions=

The Green–Tao theorem, proved by Ben Green and Terence Tao in 2004,{{cite journal|doi=10.4007/annals.2008.167.481|first1=Ben|last1=Green|author1-link=Ben J. Green|first2=Terence|last2=Tao|author2-link=Terence Tao|arxiv=math.NT/0404188 |title=The primes contain arbitrarily long arithmetic progressions|journal=Annals of Mathematics|volume=167|year=2008|issue=2|pages=481–547|mr=2415379|s2cid=1883951 }}. states that the sequence of prime numbers contains arbitrarily long arithmetic progressions. 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 2006, Terence Tao and Tamar Ziegler extended the result to cover polynomial progressions.{{cite journal|first1=Terence|last1=Tao|author1-link=Terence Tao|first2=Tamar|last2=Ziegler|author2-link=Tamar Ziegler |title=The primes contain arbitrarily long polynomial progressions|journal=Acta Mathematica|volume=201|issue=2|year=2008|pages=213–305 |arxiv=math/0610050 | doi=10.1007/s11511-008-0032-5|mr=2461509|s2cid=119138411 }}. More precisely, given any integer-valued polynomials 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, 2m, ..., 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,{{cite journal|doi=10.1007/s10240-012-0043-9|first1=Emmanuel|last1=Breuillard|author1-link=Emmanuel Breuillard|first2=Ben|last2=Green|author2-link=Ben J. Green|first3=Terence|last3=Tao|author3-link=Terence Tao|title=The structure of approximate groups

|journal=Publications Mathématiques de l'IHÉS|volume=116|year=2012|pages=115–221|mr=3090256|arxiv=1110.5008|s2cid=119603959 }}. 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.

Example

If A is a set of N integers, how large or small can the sumset

: $A+A := \{x+y: x,y \in A\},$

the difference set

: $A-A := \{x-y: x,y \in A\},$

and the product set

: $A\cdot A := \{xy: x,y \in A\}$

be, and how are the sizes of these sets related? (Not to be confused: the terms difference set 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.{{cite journal |title=A sum-product estimate in finite fields, and applications |first1=Jean |last1=Bourgain |first2=Nets |last2=Katz |first3=Terence |last3=Tao |year=2004 |journal=Geometric and Functional Analysis |volume=14 |issue=1 |pages=27–57 |doi=10.1007/s00039-004-0451-1 | mr=2053599|arxiv=math/0301343 |s2cid=14097626 }}

Notes

References

{{cite journal | first= Izabella | last = Łaba | author-link = Izabella Łaba | title=From harmonic analysis to arithmetic combinatorics | journal=Bull. Amer. Math. Soc. | volume=45 | year=2008 | issue=1 | pages=77–115 | doi=10.1090/S0273-0979-07-01189-5 | doi-access=free }}
[http://www.cs.berkeley.edu/~luca/pubs/addcomb-sigact.pdf Additive Combinatorics and Theoretical Computer Science] {{Webarchive|url=https://web.archive.org/web/20160304030143/http://www.cs.berkeley.edu/~luca/pubs/addcomb-sigact.pdf |date=2016-03-04 }}, Luca Trevisan, SIGACT News, June 2009
{{cite book |last=Bibak|first=Khodakhast |editor-last1=Borwein |editor-first1=Jonathan M. |editor-last2=Shparlinski |editor-first2=Igor E. |editor-last3=Zudilin |editor-first3=Wadim |title=Number Theory and Related Fields: In Memory of Alf van der Poorten |publisher= Springer Proceedings in Mathematics & Statistics | volume=43 | location=New York |date=2013 |pages= 99–128|chapter=Additive combinatorics with a view towards computer science and cryptography |doi=10.1007/978-1-4614-6642-0_4 |arxiv=1108.3790 |isbn=978-1-4614-6642-0|s2cid=14979158 }}
[http://people.math.gatech.edu/~ecroot/E2S-01-11.pdf Open problems in additive combinatorics], E Croot, V Lev
[https://www.ams.org/notices/200103/fea-tao.pdf From Rotating Needles to Stability of Waves: Emerging Connections between Combinatorics, Analysis, and PDE], Terence Tao, AMS Notices March 2001
{{cite book | last1=Tao | first1=Terence | author1-link=Terence Tao | last2=Vu | first2=Van H. | author2-link=Van H. Vu | title=Additive combinatorics | series=Cambridge Studies in Advanced Mathematics | volume=105 | location=Cambridge | publisher=Cambridge University Press | year=2006 | isbn=0-521-85386-9 | zbl=1127.11002 | mr=2289012 }}
{{cite book | editor1-first=Andrew | editor1-last=Granville | editor1-link=Andrew Granville | editor2-first=Melvyn B. | editor2-last=Nathanson| editor3-first=József | editor3-last=Solymosi |editor3-link= József Solymosi | title=Additive Combinatorics | series= CRM Proceedings & Lecture Notes | volume=43 | publisher=American Mathematical Society | year=2007 | isbn=978-0-8218-4351-2 | zbl=1124.11003 }}
{{cite book | first=Henry | last=Mann |author-link=Henry Mann

|title=Addition Theorems: The Addition Theorems of Group Theory and Number Theory

|publisher= Robert E. Krieger Publishing Company

|location=Huntington, New York

|year=1976

|edition=Corrected reprint of 1965 Wiley

|isbn=0-88275-418-1

}}

{{cite book | title=Additive Number Theory: the Classical Bases | volume=164 | series=Graduate Texts in Mathematics | first=Melvyn B. | last=Nathanson | publisher=Springer-Verlag | year=1996 | isbn=0-387-94656-X | location=New York | mr=1395371}}
{{cite book | title=Additive Number Theory: Inverse Problems and the Geometry of Sumsets | volume=165 | series=Graduate Texts in Mathematics | first=Melvyn B. | last=Nathanson | publisher=Springer-Verlag | year=1996 | isbn=0-387-94655-1 | location=New York | mr=1477155}}