Erdős conjecture on arithmetic progressions: Difference between revisions
m Reverted edits by 220.132.207.146 (talk) to last version by JayBeeEll |
No edit summary Tags: Manual revert Reverted |
||
| Line 20: | Line 20: | ||
The [[Szemerédi's theorem#Quantitative bounds|weaker claim]] that ''A'' must contain infinitely many arithmetic progressions of length 3 is a consequence of an improved bound in Roth's theorem, which appears as the main result in a 2020 preprint by Bloom and Sisask.<ref>{{cite journal| title = Breaking the logarithmic barrier in Roth's theorem on arithmetic progressions | last1 = Bloom | first1 = Thomas F.| last2 = Sisask | first2 = Olof | arxiv = 2007.03528 | year = 2020}}</ref> The former strongest bound in Roth's theorem is due to Bloom.<ref>{{cite journal | last=Bloom | first=Thomas F. | title=A quantitative improvement for Roth's theorem on arithmetic progressions | arxiv=1405.5800 | year=2016 | issue=3 | volume=93 | pages=643–663 | journal=Journal of the London Mathematical Society |series=Second Series | mr=3509957 | doi=10.1112/jlms/jdw010| s2cid=27536138 }}</ref> |
The [[Szemerédi's theorem#Quantitative bounds|weaker claim]] that ''A'' must contain infinitely many arithmetic progressions of length 3 is a consequence of an improved bound in Roth's theorem, which appears as the main result in a 2020 preprint by Bloom and Sisask.<ref>{{cite journal| title = Breaking the logarithmic barrier in Roth's theorem on arithmetic progressions | last1 = Bloom | first1 = Thomas F.| last2 = Sisask | first2 = Olof | arxiv = 2007.03528 | year = 2020}}</ref> The former strongest bound in Roth's theorem is due to Bloom.<ref>{{cite journal | last=Bloom | first=Thomas F. | title=A quantitative improvement for Roth's theorem on arithmetic progressions | arxiv=1405.5800 | year=2016 | issue=3 | volume=93 | pages=643–663 | journal=Journal of the London Mathematical Society |series=Second Series | mr=3509957 | doi=10.1112/jlms/jdw010| s2cid=27536138 }}</ref> |
||
The converse of the conjecture is not true. For example, the set {1, 10, 11, 100, 101, 102, 1000, 1001, 1002, 1003, 10000, ...} contains arithmetic progressions of every finite length, but the sum of the reciprocals of its elements converges. |
|||
==See also== |
==See also== |
||
Revision as of 10:22, 29 December 2021
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
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 .
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]
Progress and related results
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, which appears as the main result in a 2020 preprint by Bloom and Sisask.[4] The former strongest bound in Roth's theorem is due to Bloom.[5]
The converse of the conjecture is not true. For example, the set {1, 10, 11, 100, 101, 102, 1000, 1001, 1002, 1003, 10000, ...} contains arithmetic progressions of every finite length, but the sum of the reciprocals of its elements converges.
See also
References
- ^ Erdős, Paul; Turán, 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.
- ^ 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.; Sisask, Olof (2020). "Breaking the logarithmic barrier in Roth's theorem on arithmetic progressions". arXiv:2007.03528.
{{cite journal}}: Cite journal requires|journal=(help) - ^ 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. arXiv:1405.5800. doi:10.1112/jlms/jdw010. MR 3509957. S2CID 27536138.
- 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