Erdős conjecture on arithmetic progressions: Difference between revisions
m Undid revision 885206410 by 138.119.57.87 (talk) |
→Progress and related results: replace Bloom citation with the published version |
||
| Line 19: | Line 19: | ||
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. |
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. |
||
Even the [[Szemerédi's theorem#Quantitative bounds|weaker claim]] that ''A'' must contain at least one arithmetic progression of length 3 is open. The strongest related result is due to Bloom.<ref>{{cite |
Even the [[Szemerédi's theorem#Quantitative bounds|weaker claim]] that ''A'' must contain at least one arithmetic progression of length 3 is open. The strongest related result 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}}</ref> |
||
==See also== |
==See also== |
||
Revision as of 05:45, 10 June 2019
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
then A contains arithmetic progressions of any given length. (Sets satisfying the hypothesis are called large sets.)
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.
Even the weaker claim that A must contain at least one arithmetic progression of length 3 is open. The strongest related result is due to Bloom.[4]
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. (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.
- 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