imported>The big parsley: /* Breuillard–Green–Tao theorem */

2025-02-01T14:37:25Z

Breuillard–Green–Tao theorem

New page

{{Short description|Mathematical subject}}
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 J. Green|Ben Green]] explains arithmetic combinatorics in his review of "Additive Combinatorics" by [[Terence Tao|Tao]] and [[Van H. Vu|Vu]].<ref>{{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}}</ref>

==Important results==
===Szemerédi's theorem===
{{main|Szemerédi's theorem}}
[[Szemerédi's theorem]] is a result in arithmetic combinatorics concerning [[arithmetic progression]]s in subsets of the integers. In 1936, [[Paul Erdős|Erdős]] and [[Pál Turán|Turán]] conjectured<ref name="erdos turan">{{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}}.</ref> 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===
{{main|Green–Tao theorem}}
The [[Green–Tao theorem]], proved by [[Ben J. Green|Ben Green]] and [[Terence Tao]] in 2004,<ref>{{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 }}.</ref> states that the sequence of [[prime number]]s contains arbitrarily long [[arithmetic progression]]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 2006, Terence Tao and [[Tamar Ziegler]] extended the result to cover polynomial progressions.<ref>{{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 }}.</ref> More precisely, given any [[integer-valued polynomial]]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]], [[Ben J. Green|Ben Green]], and [[Terence Tao]] in 2011,<ref>{{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 }}.</ref> gives a complete classification of [[approximate group|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]]
:<math>A+A := \{x+y: x,y \in A\},</math>

the difference set
:<math>A-A := \{x-y: x,y \in A\},</math>

and the product set
:<math>A\cdot A := \{xy: x,y \in A\}</math>

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, [[group (mathematics)|groups]], [[ring (mathematics)|rings]] and [[field (mathematics)|fields]].<ref>{{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 }}</ref>

==See also==
{{div col|colwidth=20em}}
*[[Additive number theory]]
*[[Additive combinatorics]]
*[[Approximate group]]
*[[Corners theorem]]
*[[Ergodic Ramsey theory]]
*[[Problems involving arithmetic progressions]]
*[[Schnirelmann density]]
*[[Shapley–Folkman lemma]]
*[[Sidon set]]
*[[Sum-free set]]
*[[Restricted sumset]]
*[[Sum-product phenomenon]]
{{div col end}}

==Notes==
{{Reflist}}

==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}}

==Further reading==
*[https://www.math.ucla.edu/~tao/254a.1.03w/ Some Highlights of Arithmetic Combinatorics], resources by [[Terence Tao]]
*[http://math.stanford.edu/~ksound/Notes.pdf Additive Combinatorics: Winter 2007], K Soundararajan
*[http://lucatrevisan.wordpress.com/2009/04/17/earliest-connections-of-additive-combinatorics-and-computer-science/ Earliest Connections of Additive Combinatorics and Computer Science], Luca Trevisan

{{Number theory}}

[[Category:Additive number theory]]
[[Category:Sumsets]]
[[Category:Harmonic analysis]]
[[Category:Ergodic theory]]
[[Category:Additive combinatorics]]

Arithmetic combinatorics - Revision history

imported>The big parsley: /* Breuillard–Green–Tao theorem */