Erdős conjecture on arithmetic progressions explained
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
\{a,a{+}c,a{+}2c,\ldots,a{+}kc\}\subsetA
.
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. A 2016 paper by Bloom[4] proved that if
contains no non-trivial three-term arithmetic progressions then
|A|\llN(log{log{N}})/log{N}
.
In 2020 a preprint by Bloom and Sisask[5] improved the bound to
for some absolute constant
.
In 2023 a new bound of
[6] [7] [8] was found by computers scientist Kelley an Meka and shortly after an exposition in more familiar mathematical terms was given by
Bloom and Sisask
[9] [10] who have since also improved the exponent of the Kelly-Meka bound to
(and conjectured
) in a preprint.
[11] See also
References
- 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.
External links
Notes and References
- .
- 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.
- 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 . 1405.5800 . 10.1112/jlms/jdw010 . 3509957 . 27536138.
- Bloom . Thomas F. . Sisask . Olof . 2020 . Breaking the logarithmic barrier in Roth's theorem on arithmetic progressions . math.NT . 2007.03528.
- Kelley . Zander . Meka . Raghu . 2023-11-06 . Strong Bounds for 3-Progressions . 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)-Conference Proceedings . IEEE . 933–973 . 10.1109/FOCS57990.2023.00059 . 979-8-3503-1894-4. 2302.05537 .
- 2302.05537 . math.NT . Zander . Kelley . Raghu . Meka . Strong Bounds for 3-Progressions . 2023-02-10.
- Web site: Sloman . Leila . 2023-03-21 . Surprise Computer Science Proof Stuns Mathematicians . Quanta Magazine . en.
- Bloom . Thomas F. . Sisask . Olof . 2023-12-31 . The Kelley–Meka bounds for sets free of three-term arithmetic progressions . Essential Number Theory . en . 2 . 1 . 15–44 . 10.2140/ent.2023.2.15 . 2834-4634. 2302.07211 .
- 2302.07211 . math.NT . Thomas F. . Bloom . Olof . Sisask . The Kelley--Meka bounds for sets free of three-term arithmetic progressions . 2023-02-14.
- 2309.02353 . math.NT . Thomas F. . Bloom . Olof . Sisask . An improvement to the Kelley-Meka bounds on three-term arithmetic progressions . 2023-09-05.