Erdős conjecture on arithmetic progressions

<h2 id="history">History</h2>
In 1936, Erdős and Turán made the weaker conjecture that any set of integers with positive <a href="/facts/Natural_density/WtMTUmMJ">natural density</a> contains infinitely many 3 term arithmetic progressions.<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a> This was proven by <a href="/facts/Klaus_Roth/exBd7vDU">Klaus Roth</a> in 1952, and generalized to arbitrarily long arithmetic progressions by <a href="/facts/Szemer%25C3%25A9di/bE2Ezgbl">Szemerédi</a> in 1975 in what is now known as <a href="/facts/Szemer%25C3%25A9di%2527s_theorem/6fjvXcEx">Szemerédi's theorem</a>. 
In a 1976 talk titled "To the memory of my lifelong friend and collaborator Paul Turán," <a href="/facts/Paul_Erd%25C5%2591s/63LoUTe1">Paul Erdős</a> offered a prize of US$3000 for a proof of this conjecture.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> As of 2008 the problem is worth US$5000.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>

<h2 id="progress-and-related-results">Progress and related results</h2>
See also: <a href="/facts/Szemer%25C3%25A9di%2527s_theorem/6fjvXcEx">Szemerédi's theorem § Quantitative bounds</a>, <a href="/facts/Roth%2527s_theorem_on_arithmetic_progressions/f0Xd6Pr9">Roth's theorem on arithmetic progressions § Improving bounds</a>, and <a href="/facts/Salem%25E2%2580%2593Spencer_set/aWogz0JA">Salem–Spencer set § Size</a>

Unsolved problem in mathematics:
Does every large set of natural numbers contain arbitrarily long arithmetic progressions?
<a href="/facts/List_of_unsolved_problems_in_mathematics/RroxGPpP">(more unsolved problems in mathematics)</a>

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 <a href="/facts/Green%25E2%2580%2593Tao_theorem/kGTx52Vp">Green–Tao theorem</a> on arithmetic progressions is a special case of the conjecture.
The <a href="/facts/Szemer%25C3%25A9di%2527s_theorem/6fjvXcEx">weaker claim</a> that A must contain infinitely many arithmetic progressions of length 3 is a consequence of an improved bound in <a href="/facts/Roth%2527s_theorem_on_arithmetic_progressions/f0Xd6Pr9">Roth's theorem</a>. A 2016 paper by <a href="/facts/Thomas_Bloom/Btv4quGS">Bloom</a><a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> proved that if 
 
 
 
 A
 ⊂
 {
 1
 ,
 .
 .
 ,
 N
 }
 
 
 {\displaystyle A\subset \{1,..,N\}}
 
 contains no non-trivial three-term arithmetic progressions then 
 
 
 
 
 |
 
 A
 
 |
 
 ≪
 N
 (
 log
 ⁡
 
 log
 ⁡
 
 N
 
 
 )
 
 /
 
 log
 ⁡
 
 N
 
 
 
 {\displaystyle |A|\ll N(\log {\log {N}})/\log {N}}
 
.
In 2020 a preprint by Bloom and Sisask<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> improved the bound to 
 
 
 
 
 |
 
 A
 
 |
 
 ≪
 N
 
 /
 
 (
 log
 ⁡
 
 N
 
 
 )
 
 1
 +
 c
 
 
 
 
 {\displaystyle |A|\ll N/(\log {N})^{1+c}}
 
 for some absolute constant 
 
 
 
 c
 >
 0
 
 
 {\displaystyle c>0}
 
 .
In 2023 a new bound of 
 
 
 
 exp
 ⁡
 (
 −
 c
 (
 log
 ⁡
 N
 
 )
 
 1
 
 /
 
 12
 
 
 )
 N
 
 
 {\displaystyle \exp(-c(\log N)^{1/12})N}
 
<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a><a class="footnote-ref" id="fnref:7" href="#fn:7">7</a><a class="footnote-ref" id="fnref:8" href="#fn:8">8</a> was found by computer scientists Kelley and Meka, with an exposition given in more familiar mathematical language by <a href="/facts/Thomas_Bloom/Btv4quGS">Bloom</a> and Sisask,<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a><a class="footnote-ref" id="fnref:10" href="#fn:10">10</a> who have since improved the exponent of the Kelly-Meka bound to 
 
 
 
 β
 =
 1
 
 /
 
 9
 
 
 {\displaystyle \beta =1/9}
 
, and conjectured 
 
 
 
 β
 =
 5
 
 /
 
 41
 
 
 {\displaystyle \beta =5/41}
 
, in a preprint.<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a>

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Problems_involving_arithmetic_progressions/k8FohnnP">Problems involving arithmetic progressions</a></li>
<li><a href="/facts/List_of_sums_of_reciprocals/B2eAx0vL">List of sums of reciprocals</a></li>
<li><a href="/facts/List_of_conjectures_by_Paul_Erd%25C5%2591s/bpBChe3o">List of conjectures by Paul Erdős</a></li>
<li><a href="/facts/M%25C3%25BCntz%25E2%2580%2593Sz%25C3%25A1sz_theorem/u9vCYFcg">Müntz–Szász theorem</a></li></ul>

<ul><li>P. Erdős: <a href="http://www.renyi.hu/~p_erdos/1973-24.pdf">Résultats et problèmes en théorie de nombres</a>, Séminaire Delange-Pisot-Poitou (14e année: 1972/1973), Théorie des nombres, Fasc 2., Exp. No. 24, pp. 7,</li>
<li>P. Erdős and P. Turán, On some sequences of integers, J. London Math. Soc. 11 (1936), 261–264.</li>
<li>P. Erdős: Problems in number theory and combinatorics, Proc. Sixth Manitoba Conf. on Num. Math., Congress Numer. XVIII(1977), 35–58.</li>
<li>P. Erdős: On the combinatorial problems which I would most like to see solved, Combinatorica, 1(1981), 28. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF02579174">10.1007/BF02579174</a></li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="https://mathoverflow.net/q/132648">The Erdős–Turán conjecture or the Erdős conjecture?</a> on MathOverflow</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">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. <a href="/wiki/Paul_Erd%C5%91s" target="_blank">/wiki/Paul_Erd%C5%91s</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">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 <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">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 <a href="/wiki/The_Mathematical_Coloring_Book" target="_blank">/wiki/The_Mathematical_Coloring_Book</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">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. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Bloom, Thomas F.; Sisask, Olof (2020). "Breaking the logarithmic barrier in Roth's theorem on arithmetic progressions". arXiv:2007.03528 [math.NT]. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Kelley, Zander; Meka, Raghu (2023-11-06). "Strong Bounds for 3-Progressions". 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS). IEEE. pp. 933–973. arXiv:2302.05537. doi:10.1109/FOCS57990.2023.00059. ISBN 979-8-3503-1894-4. <a href="979-8-3503-1894-4" target="_blank">979-8-3503-1894-4</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Kelley, Zander; Meka, Raghu (2023-02-10). "Strong Bounds for 3-Progressions". arXiv:2302.05537 [math.NT]. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Sloman, Leila (2023-03-21). "Surprise Computer Science Proof Stuns Mathematicians". Quanta Magazine. <a href="https://www.quantamagazine.org/surprise-computer-science-proof-stuns-mathematicians-20230321/" target="_blank">https://www.quantamagazine.org/surprise-computer-science-proof-stuns-mathematicians-20230321/</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Bloom, Thomas F.; Sisask, Olof (2023-12-31). "The Kelley–Meka bounds for sets free of three-term arithmetic progressions". Essential Number Theory. 2 (1): 15–44. arXiv:2302.07211. doi:10.2140/ent.2023.2.15. ISSN 2834-4634. <a href="https://msp.org/ent/2023/2-1/p02.xhtml" target="_blank">https://msp.org/ent/2023/2-1/p02.xhtml</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Bloom, Thomas F.; Sisask, Olof (2023-02-14). "The Kelley–Meka bounds for sets free of three-term arithmetic progressions". Essential Number Theory. 2: 15–44. arXiv:2302.07211. doi:10.2140/ent.2023.2.15. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Bloom, Thomas F.; Sisask, Olof (2023-09-05). "An improvement to the Kelley-Meka bounds on three-term arithmetic progressions". arXiv:2309.02353 [math.NT]. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
</ol>

Erdős conjecture on arithmetic progressions open-in-new

Erdős conjecture on arithmetic progressions