Erdős' conjecture on arithmetic progressions, often referred to as the Erdős–Turán conjecture, is a
conjecture in
arithmetic combinatorics In mathematics, arithmetic combinatorics is a field in the intersection of number theory, combinatorics, ergodic theory and harmonic analysis.
Scope
Arithmetic combinatorics is about combinatorial estimates associated with arithmetic operations (ad ...
(not to be confused with the
Erdős–Turán conjecture on additive bases
The Erdős–Turán conjecture is an old unsolved problem in additive number theory (not to be confused with Erdős conjecture on arithmetic progressions) posed by Paul Erdős and Pál Turán in 1941.
The question concerns subsets of the natur ...
). 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 progression
An arithmetic progression or arithmetic sequence () is a sequence of numbers such that the difference between the consecutive terms is constant. For instance, the sequence 5, 7, 9, 11, 13, 15, . . . is an arithmetic progression with a common differ ...
s.
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 In number theory, natural density (also referred to as asymptotic density or arithmetic density) is one method to measure how "large" a subset of the set of natural numbers is. It relies chiefly on the probability of encountering members of the de ...
contains infinitely many 3 term arithmetic progressions.
[.] This was proven by
Klaus Roth
Klaus Friedrich Roth (29 October 1925 – 10 November 2015) was a German-born British mathematician who won the Fields Medal for proving Roth's theorem on the Diophantine approximation of algebraic numbers. He was also a winner of the De Mo ...
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 arithmetic combinatorics, Szemerédi's theorem is a result concerning arithmetic progressions in subsets of the integers. In 1936, Erdős and Turán conjectured that every set of integers ''A'' with positive natural density contains a ''k''-ter ...
.
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. As of 2008 the problem is worth US$5000.
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. The former strongest bound in Roth's theorem is due to Bloom.
See also
*
Problems involving arithmetic progressions
Problems involving arithmetic progressions are of interest in number theory,
combinatorics, and computer science, both from theoretical and applied points of view.
Largest progression-free subsets
Find the cardinality (denoted by ''A'k''(''m' ...
*
List of sums of reciprocals
In mathematics and especially number theory, the sum of reciprocals generally is computed for the reciprocals of some or all of the positive integers (counting numbers)—that is, it is generally the sum of unit fractions. If infinitely many n ...
*
List of conjectures by Paul Erdős
The prolific mathematician Paul Erdős and his various collaborators made many famous mathematical conjectures, over a wide field of subjects, and in many cases Erdős offered monetary rewards for solving them.
Unsolved
* The Erdős–Gyárfás co ...
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
The Erdős–Turán conjecture or the Erdős conjecture?on MathOverflow
{{DEFAULTSORT:Erdos conjecture on arithmetic progressions
Combinatorics
Conjectures
Unsolved problems in mathematics