Erdős’s reciprocal-sum conjecture and quasipolynomial Szemerédi bounds

Any set of whole numbers whose reciprocals add to infinity holds evenly spaced runs of every length.

1 paper September 23, 2026 Explained by AI

Take a set of whole numbers and add up one over each member. Erdős asked whether an infinite total forces evenly spaced runs of every length. This paper proves that it does. It also claims to prove a new upper bound on how many numbers up to N can avoid such runs. That bound is what makes the infinite-total statement follow.

First step

1936

Erdős and Turán, start of the density problem

Significance

Landmark

It settles a famous Erdős question for every length, where only the three-term case was known.

Trust

Formal proof listed

Field

Combinatorics

1 paper

The explanation

Here is a list of whole numbers: 1, 2, 4, 5, 10, 11, 13, 14, 28, and so on. It is built greedily. Start at 1. Then add each next number that creates no three-term progression. A three-term progression is three numbers with equal gaps, like 4, 10, 16. The list never contains one. Now add up the reciprocals: 1/1 + 1/2 + 1/4 + 1/5 and onward. The total settles near 3.008.

The powers of two behave the same way. The list 1, 2, 4, 8, 16 and onward has no three-term progression. Its reciprocals add up to exactly 2. The primes are different. Their reciprocals add to about 2.20 below one thousand. Below a million the total is about 2.89, and below ten million about 3.04. That total keeps growing without limit. And the primes do hold progressions: 7, 37, 67, 97, 127 and 157 are six primes with gap 30.

Paul Erdős turned this contrast into a question, recorded in 1974. Suppose the reciprocals of a set of whole numbers add up to infinity. Must the set contain progressions of every finite length? This paper proves that the answer is yesSource 1. Put another way, for each length there is a ceiling. Every set with no progression of that length has a reciprocal sum below the ceilingSource 2. For three terms, the greedy list shows that ceiling is at least about 3.008.

The question grew from an older one. Erdős and Turán began in 1936 to ask how many numbers can avoid progressions. Write r_k(N) for the largest count of numbers from 1 to N with no k-term progression. Among 1 to 20, at most 9 numbers avoid three-term progressions, so r_3(20) = 9. Roth proved in 1953 that such sets take a vanishing share for three terms. Szemerédi proved it for four terms in 1969 and for every length in 1975.

A vanishing share is not enough for Erdős's question. The primes also take a vanishing share, yet their reciprocals add to infinity. What matters is how fast the share falls. Split the numbers into blocks, from 1 to 2, 2 to 4, 4 to 8, and so on. A set with no k-term progression has reciprocals in the block from 2^m to 2^(m+1) adding to at most r_k(2^m)/2^mSource 3. If those block shares add to a finite total, Erdős's statement follows.

For three terms, Bloom and Sisask crossed that line in 2020. Their bound settled the three-term case of the question. Kelley and Meka then gave a much stronger three-term bound in 2023. Longer progressions lagged far behind. For five or more terms, the best bound came from Leng, Sah and Sawhney in 2024. Their share falls like exp(−(log log N)^c), with a double logarithm inside. The paper notes that this saving does not make the block shares add to a finite total.

The paper claims to prove a much faster fall for every length k of at least 3. It states that r_k(N) is at most C·N·exp(−c·(log N)^ε)Source 4. Here C, c and ε are positive numbers that depend only on k. They are not given as explicit values, and the paper does not optimize the exponentSource 5. With this bound the block shares do add to a finite total. A limit on how far this can go was already known. Behrend showed in 1946 that r_3(N) is at least N·exp(−C·√(log N)). So the share can never fall as fast as a fixed power of N.

The single difficulty was keeping a standard method from losing too much. The method is called a density increment. Density is the share of a region that the set fills. If a set has too few progressions, it is unusually dense on some smaller structured region. The proof zooms into that region and repeats. Density cannot exceed one, so only a limited number of zooms can happenSource 6. The danger is that each zoom shrinks the region and adds new conditions. For long progressions those conditions are polynomial equations, and errors can pile up across zooms. The paper keeps the old equations exact at every zoomSource 7. It also bounds the new precision loss without feeding it the losses already madeSource 8. That keeps the total cost small enough.

The bound also gives more than Erdős asked. Fix any B of at least 0. A set still has progressions of every length when its sum of (log(2+a))^B/a is infiniteSource 9. The paper also recovers the Green–Tao theorem on progressions in dense subsets of the primesSource 10. It claims no improvement of the best three-term boundSource 11.

How sure is this? A computer proof checker called Lean has checked a formal version of Erdős's statement. It says any set of positive whole numbers with an infinite reciprocal sum holds progressions of every length. The quantitative bound on r_k(N) is outside that check. No specialist review of the paper has been published.

What it doesn't show. This does not give explicit constants in the bound or improve the best three-term bound.

Where it came from

This result comes from an unreleased OpenAI model, published in the openai/math release on 6 October 2026.

Hype check

Landmark only if the paper holds up. Lean checks the formal statement of Erdős's question. The quantitative bound is outside that check, and no specialist review is published.

Words used

Arithmetic progression: A list of numbers with equal gaps, like 7, 37, 67, 97.
Reciprocal sum: The total of one over each member of a set, like 1/2 + 1/4 + 1/8.
r_k(N): The largest number of whole numbers from 1 to N that contain no k-term progression.
Density: The share of a range or region that a set fills.
Density increment: A proof method that finds a smaller region where the set is denser, then repeats there.
Lean: A computer program that checks each step of a formal proof.

The original paper

Quasipolynomial Bounds for Arithmetic Progressions (PDF, opens in a new tab)
September 23, 2026

Lean notes Model's reasoning summary

All quoted lines (11)

Every set $A\subseteq\mathbb N$ with $\sum_{a\in A}a^{-1}=\infty$ contains nonconstant arithmetic progressions of every finite length.
Quasipolynomial Bounds for Arithmetic Progressions Back to text
There is $H_k<\infty$ such that every $k$ -term-progression-free $A\subseteq\mathbb N$ satisfies $\sum_{a\in A}\frac1a\le H_k.$
Quasipolynomial Bounds for Arithmetic Progressions Back to text
Thus $|A\cap[2^m,2^{m+1})|\le r_k(2^m)$ .
Quasipolynomial Bounds for Arithmetic Progressions Back to text
For each fixed integer $k\ge3$ there are constants $C_k,c_k,\varepsilon_k>0$ such that, for every $N\ge2$ , $r_k(N)\le C_kN\exp\bigl(-c_k(\log N)^{\varepsilon_k}\bigr).$
Quasipolynomial Bounds for Arithmetic Progressions Back to text
The constants may depend on the fixed length $k$ ; the exponent is not optimized.
Quasipolynomial Bounds for Arithmetic Progressions Back to text
A fixed multiplicative density gain can be applied only $O_k(1+\log(1/\alpha))$ times before the density exceeds one.
Quasipolynomial Bounds for Arithmetic Progressions Back to text
Keeping these integer blocks, and substituting them exactly into all later polynomials, preserves the equations defining the old region when a new constraint is added.
Quasipolynomial Bounds for Arithmetic Progressions Back to text
In particular, this bound does not use the current $Q_h$ or the lower precisions.
Quasipolynomial Bounds for Arithmetic Progressions Back to text
Our bound also gives a stronger divergence criterion: for every fixed $B\ge0$ , a set $A\subseteq\mathbb N$ satisfying $\sum_{a\in A}\frac{(\log(2+a))^B}{a}=\infty$ contains progressions of every finite length.
Quasipolynomial Bounds for Arithmetic Progressions Back to text
It also recovers the theorem of Green and Tao that every subset of the primes of positive relative upper density contains infinitely many progressions of every finite length.
Quasipolynomial Bounds for Arithmetic Progressions Back to text
Its contribution to Erd\Hos's conjecture is this all-length, summable bound; no improvement of the three-term exponent is claimed.
Quasipolynomial Bounds for Arithmetic Progressions Back to text

Other sources

P. Erdős, “Problems”, Math. Balkanica 4 (1974), 203–204, Problem 4.33.6
K. F. Roth, “On certain sets of integers”, J. London Math. Soc. 28 (1953), 104–109
E. Szemerédi, “On sets of integers containing no k elements in arithmetic progression”, Acta Arith. 27 (1975), 199–245
T. F. Bloom and O. Sisask, “Breaking the logarithmic barrier in Roth's theorem on arithmetic progressions”, arXiv:2007.03528 (2020)
J. Leng, A. Sah and M. Sawhney, “Improved Bounds for Szemerédi's Theorem”, arXiv:2402.17995 (2024)
F. A. Behrend, “On sets of integers which contain no three terms in arithmetical progression”, Proc. Nat. Acad. Sci. U.S.A. 32 (1946), 331–332
openai/math, Lean scope note for family 159 The formalization proves this statement: for every requested length, such a set contains a progression with positive common difference.
openai/math release notes (2026): model provenance manuscripts and supporting proof artifacts produced by an internal OpenAI model