Erdős conjecture on arithmetic progressions
Erdős' conjecture on arithmetic progressions, often referred to as the Erdős–Turán conjecture, is a conjecture in arithmetic combinatorics (not to be confused with the Erdős–Turán conjecture on additive bases). It states that if the sum of the reciprocals of the members of a set A of positive integers diverges, then A contains arbitrarily long arithmetic progressions.
Formally, the conjecture states that if A is a large set in the sense that
[math]\displaystyle{ \sum_{n\in A} \frac{1}{n} \ =\ \infty, }[/math]
then A contains arithmetic progressions of any given length, meaning that for every positive integer k there are an integer a and a non-zero integer c such that [math]\displaystyle{ \{a,a{+}c,a{+}2c,\ldots,a{+}kc\}\subset A }[/math].
History
In 1936, Erdős and Turán made the weaker conjecture that any set of integers with positive natural density contains infinitely many 3 term arithmetic progressions.[1] This was proven by Klaus Roth in 1952, and generalized to arbitrarily long arithmetic progressions by Szemerédi in 1975 in what is now known as Szemerédi's theorem.
In a 1976 talk titled "To the memory of my lifelong friend and collaborator Paul Turán," Paul Erdős offered a prize of US$3000 for a proof of this conjecture.[2] As of 2008 the problem is worth US$5000.[3]
 |
Unsolved problem in mathematics: Does every large set of natural numbers contain arbitrarily long arithmetic progressions? (more unsolved problems in mathematics)
|
Erdős' conjecture on arithmetic progressions can be viewed as a stronger version of Szemerédi's theorem. Because the sum of the reciprocals of the primes diverges, the Green–Tao theorem on arithmetic progressions is a special case of the conjecture.
The weaker claim that A must contain infinitely many arithmetic progressions of length 3 is a consequence of an improved bound in Roth's theorem. A 2016 paper by Bloom[4] proved that if [math]\displaystyle{ A\subset \{1,..,N\} }[/math] contains no non-trivial three-term arithmetic progressions then [math]\displaystyle{ |A|\ll N(\log{\log{N}})/\log{N} }[/math].
In 2020 a preprint by Bloom and Sisask[5] improved the bound to [math]\displaystyle{ |A|\ll N/(\log{N})^{1+c} }[/math] for some absolute constant [math]\displaystyle{ c\gt 0 }[/math] .
In 2023 a preprint by Kelley and Meka gave a new bound of [math]\displaystyle{ 2^{-O((\log N)^c)} \cdot N }[/math][6][7] and four days later Bloom and Sisask simplified the result and with a little improvement to [math]\displaystyle{ |A| \leq \exp(-c(\log N)^{1/11})N }[/math].[8]
See also
- Problems involving arithmetic progressions
- List of sums of reciprocals
- List of conjectures by Paul Erdős
- Müntz–Szász theorem
References
- ↑ Erdős, Paul; Turán, Paul (1936), "On some sequences of integers", Journal of the London Mathematical Society 11 (4): 261–264, doi:10.1112/jlms/s1-11.4.261, http://www.renyi.hu/~p_erdos/1936-05.pdf.
- ↑ Problems in number theory and Combinatorics, in Proceedings of the Sixth Manitoba Conference on Numerical Mathematics (Univ. Manitoba, Winnipeg, Man., 1976), Congress. Numer. XVIII, 35–58, Utilitas Math., Winnipeg, Man., 1977
- ↑ p. 354, Soifer, Alexander (2008); The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators; New York: Springer. ISBN 978-0-387-74640-1
- ↑ Bloom, Thomas F. (2016). "A quantitative improvement for Roth's theorem on arithmetic progressions". Journal of the London Mathematical Society. Second Series 93 (3): 643–663. doi:10.1112/jlms/jdw010.
- ↑ Bloom, Thomas F.; Sisask, Olof (2020). Breaking the logarithmic barrier in Roth's theorem on arithmetic progressions.
- ↑ Kelley, Zander; Meka, Raghu (2023-02-10). "Strong Bounds for 3-Progressions". arXiv:2302.05537 [math.NT].
- ↑ Sloman, Leila (2023-03-21). "Surprise Computer Science Proof Stuns Mathematicians" (in en). https://www.quantamagazine.org/surprise-computer-science-proof-stuns-mathematicians-20230321/.
- ↑ Bloom, Thomas F.; Sisask, Olof (2023-02-14). "The Kelley--Meka bounds for sets free of three-term arithmetic progressions". arXiv:2302.07211 [math.NT].
- P. Erdős: Résultats et problèmes en théorie de nombres, Séminaire Delange-Pisot-Poitou (14e année: 1972/1973), Théorie des nombres, Fasc 2., Exp. No. 24, pp. 7,
- P. Erdős and P. Turán, On some sequences of integers, J. London Math. Soc. 11 (1936), 261–264.
- P. Erdős: Problems in number theory and combinatorics, Proc. Sixth Manitoba Conf. on Num. Math., Congress Numer. XVIII(1977), 35–58.
- P. Erdős: On the combinatorial problems which I would most like to see solved, Combinatorica, 1(1981), 28. doi:10.1007/BF02579174
External links
- The Erdős–Turán conjecture or the Erdős conjecture? on MathOverflow
 |  |
