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.[1]
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[2] 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.
In 2006, Terence Tao and Tamar Ziegler extended the result to cover polynomial progressions.[4] More precisely, given any integer-valued polynomialsP1,..., Pk in one unknown m all with constant term 0, there are infinitely many integers x, m such that x + P1(m), ..., x + Pk(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.
^Green, Ben (July 2009). "Book Reviews: Additive combinatorics, by Terence C. Tao and Van H. Vu" (PDF). Bulletin of the American Mathematical Society. 46 (3): 489–497. doi:10.1090/s0273-0979-09-01231-2.
Additive Combinatorics and Theoretical Computer Science 2016-03-04 at the Wayback Machine, Luca Trevisan, SIGACT News, June 2009
Bibak, Khodakhast (2013). "Additive combinatorics with a view towards computer science and cryptography". In Borwein, Jonathan M.; Shparlinski, Igor E.; Zudilin, Wadim (eds.). Number Theory and Related Fields: In Memory of Alf van der Poorten. Vol. 43. New York: Springer Proceedings in Mathematics & Statistics. pp. 99–128. arXiv:1108.3790. doi:10.1007/978-1-4614-6642-0_4. ISBN978-1-4614-6642-0. S2CID 14979158.
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, AMS Notices March 2001
Mann, Henry (1976). Addition Theorems: The Addition Theorems of Group Theory and Number Theory (Corrected reprint of 1965 Wiley ed.). Huntington, New York: Robert E. Krieger Publishing Company. ISBN0-88275-418-1.
Nathanson, Melvyn B. (1996). Additive Number Theory: Inverse Problems and the Geometry of Sumsets. Graduate Texts in Mathematics. Vol. 165. New York: Springer-Verlag. ISBN0-387-94655-1. MR 1477155.
Further readingedit
Some Highlights of Arithmetic Combinatorics, resources by Terence Tao
Additive Combinatorics: Winter 2007, K Soundararajan
Earliest Connections of Additive Combinatorics and Computer Science, Luca Trevisan
December 20, 2023
arithmetic, combinatorics, mathematics, arithmetic, combinatorics, field, intersection, number, theory, combinatorics, ergodic, theory, harmonic, analysis, contents, scope, important, results, szemerédi, theorem, green, theorem, extensions, breuillard, green, . In mathematics arithmetic combinatorics is a field in the intersection of number theory combinatorics ergodic theory and harmonic analysis Contents 1 Scope 2 Important results 2 1 Szemeredi s theorem 2 2 Green Tao theorem and extensions 2 3 Breuillard Green Tao theorem 3 Example 4 Extensions 5 See also 6 Notes 7 References 8 Further readingScope editArithmetic 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 1 Important results editSzemeredi s theorem edit Main article Szemeredi s theorem Szemeredi s theorem is a result in arithmetic combinatorics concerning arithmetic progressions in subsets of the integers In 1936 Erdos and Turan conjectured 2 that every set of integers A with positive natural density contains a k term arithmetic progression for every k This conjecture which became Szemeredi s theorem generalizes the statement of van der Waerden s theorem Green Tao theorem and extensions edit Main article Green Tao theorem The Green Tao theorem proved by Ben Green and Terence Tao in 2004 3 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 Szemeredi s theorem In 2006 Terence Tao and Tamar Ziegler extended the result to cover polynomial progressions 4 More precisely given any integer valued polynomials P1 Pk in one unknown m all with constant term 0 there are infinitely many integers x m such that x P1 m x Pk 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 edit The Breuillard Green Tao theorem proved by Emmanuel Breuillard Ben Green and Terence Tao in 2011 5 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 editIf A is a set of N integers how large or small can the sumset A A x y x y A displaystyle A A x y x y in A nbsp the difference set A A x y x y A displaystyle A A x y x y in A nbsp and the product set A A x y x y A displaystyle A cdot A xy x y in A nbsp 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 editThe sets being studied may also be subsets of algebraic structures other than the integers for example groups rings and fields 6 See also editAdditive number theory Approximate group Corners theorem Ergodic Ramsey theory Problems involving arithmetic progressions Schnirelmann density Shapley Folkman lemma Sidon set Sum free set Sum product problemNotes edit Green Ben July 2009 Book Reviews Additive combinatorics by Terence C Tao and Van H Vu PDF Bulletin of the American Mathematical Society 46 3 489 497 doi 10 1090 s0273 0979 09 01231 2 Erdos Paul Turan Paul 1936 On some sequences of integers PDF Journal of the London Mathematical Society 11 4 261 264 doi 10 1112 jlms s1 11 4 261 MR 1574918 Green Ben Tao Terence 2008 The primes contain arbitrarily long arithmetic progressions Annals of Mathematics 167 2 481 547 arXiv math NT 0404188 doi 10 4007 annals 2008 167 481 MR 2415379 S2CID 1883951 Tao Terence Ziegler Tamar 2008 The primes contain arbitrarily long polynomial progressions Acta Mathematica 201 2 213 305 arXiv math 0610050 doi 10 1007 s11511 008 0032 5 MR 2461509 S2CID 119138411 Breuillard Emmanuel Green Ben Tao Terence 2012 The structure of approximate groups Publications Mathematiques de l IHES 116 115 221 arXiv 1110 5008 doi 10 1007 s10240 012 0043 9 MR 3090256 S2CID 119603959 Bourgain Jean Katz Nets Tao Terence 2004 A sum product estimate in finite fields and applications Geometric and Functional Analysis 14 1 27 57 arXiv math 0301343 doi 10 1007 s00039 004 0451 1 MR 2053599 S2CID 14097626 References editLaba Izabella 2008 From harmonic analysis to arithmetic combinatorics Bull Amer Math Soc 45 1 77 115 doi 10 1090 S0273 0979 07 01189 5 Additive Combinatorics and Theoretical Computer Science Archived 2016 03 04 at the Wayback Machine Luca Trevisan SIGACT News June 2009 Bibak Khodakhast 2013 Additive combinatorics with a view towards computer science and cryptography In Borwein Jonathan M Shparlinski Igor E Zudilin Wadim eds Number Theory and Related Fields In Memory of Alf van der Poorten Vol 43 New York Springer Proceedings in Mathematics amp Statistics pp 99 128 arXiv 1108 3790 doi 10 1007 978 1 4614 6642 0 4 ISBN 978 1 4614 6642 0 S2CID 14979158 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 AMS Notices March 2001 Tao Terence Vu Van H 2006 Additive combinatorics Cambridge Studies in Advanced Mathematics Vol 105 Cambridge Cambridge University Press ISBN 0 521 85386 9 MR 2289012 Zbl 1127 11002 Granville Andrew Nathanson Melvyn B Solymosi Jozsef eds 2007 Additive Combinatorics CRM Proceedings amp Lecture Notes Vol 43 American Mathematical Society ISBN 978 0 8218 4351 2 Zbl 1124 11003 Mann Henry 1976 Addition Theorems The Addition Theorems of Group Theory and Number Theory Corrected reprint of 1965 Wiley ed Huntington New York Robert E Krieger Publishing Company ISBN 0 88275 418 1 Nathanson Melvyn B 1996 Additive Number Theory the Classical Bases Graduate Texts in Mathematics Vol 164 New York Springer Verlag ISBN 0 387 94656 X MR 1395371 Nathanson Melvyn B 1996 Additive Number Theory Inverse Problems and the Geometry of Sumsets Graduate Texts in Mathematics Vol 165 New York Springer Verlag ISBN 0 387 94655 1 MR 1477155 Further reading editSome Highlights of Arithmetic Combinatorics resources by Terence Tao Additive Combinatorics Winter 2007 K Soundararajan Earliest Connections of Additive Combinatorics and Computer Science Luca Trevisan Retrieved from https en wikipedia org w index php title Arithmetic combinatorics amp oldid 1174356901, wikipedia, wiki, book, books, library,
