Arithmetic progressions from a divergent reciprocal sum

← All digests

Family 159 · Combinatorics
Importance 5/5 · Provisional editorial rating
Sources consulted 2026-10-11

1. The question

The positive integers contain many evenly spaced patterns, such as $7,12,17,22$. How sparse can a set of integers be while still being forced to contain arbitrarily long arithmetic progressions?

Positive density is enough by Szemerédi’s theorem. Erdős proposed a much weaker hypothesis: perhaps it suffices that the reciprocals of the set’s elements have divergent sum. Such a set may have density zero. The primes are the most familiar example of that distinction.

The manuscript in family 159 claims Erdős’s reciprocal-sum conjecture for every progression length. It does so through a finite quantitative theorem: sets avoiding a fixed progression must be sparse enough that their reciprocal contributions, collected over successively doubled intervals, form a convergent series.

The decisive advance is therefore a particular rate of sparsity, not merely the qualitative statement that progression-free sets have density tending to zero.

2. Background and essential definitions

A nonconstant $k$-term arithmetic progression is

$$a,\ a+d,\ a+2d,\ldots,\ a+(k-1)d, \qquad d\ge1.$$

The positive step excludes the uninformative repetition of one number. Write $[N]=\{1,\ldots,N\}$, and let $r_k(N)$ be the largest size of a subset of $[N]$ containing no such progression.

The density of $A\subseteq[N]$ is $\alpha=|A|/N$. Szemerédi’s theorem says that for fixed $k$,

$$\frac{r_k(N)}{N}\longrightarrow0 \quad\text{as }N\longrightarrow\infty.$$

It does not, in this qualitative form, specify the speed of convergence. A density of $1/\log\log N$, for example, tends to zero very slowly.

For an infinite set $A\subseteq\mathbb N$, its reciprocal sum is $\sum_{a\in A}1/a$. The full harmonic series diverges, while the sum over powers of two converges. This criterion accounts for where elements lie as well as how many exist: an element near $2^m$ contributes roughly $2^{-m}$.

What the quantitative terminology means

A stretched exponential in $\log N$ has the form

$$\exp\bigl(-c(\log N)^\varepsilon\bigr), \qquad c,\varepsilon>0.$$

For any fixed positive $\varepsilon$, this decays faster than every negative fixed power of $\log N$. The source’s equivalent density threshold makes $\log N$ polynomially bounded in $\log(1/\alpha)$; that is the sense in which its interval threshold is quasipolynomial in inverse density. Constants and exponents may depend on $k$.

3. Development history and previous partial results

Van der Waerden’s 1927 theorem established that every finite coloring of the integers has monochromatic progressions of every finite length. A density theorem is different: it forces a progression inside a particular set rather than somewhere in a partition.

Erdős and Turán initiated the extremal density problem in 1936. Roth proved the three-term positive-density case in 1953. Szemerédi’s 1975 theorem treated every fixed length, following his earlier four-term result. Furstenberg later connected the phenomenon to recurrence in dynamical systems.

Quantitative work asks how small $r_k(N)$ must be. In the three-term case, density-increment arguments and Fourier analysis gradually improved logarithmic savings. Bloom and Sisask crossed the threshold needed to deduce the three-term reciprocal-sum conjecture. Kelley and Meka then obtained a stretched-exponential saving in $\log N$, with subsequent improvements to its exponent.

Longer progressions require higher-order structure. Gowers introduced uniformity norms that detect it, and inverse theorems explain what a large such norm means. Leng, Sah and Sawhney obtained improved bounds for all fixed lengths, using a quantitative inverse theorem. The general savings described in M1 involve a power of $\log\log N$ in an exponential, rather than the power of $\log N$ in the new claim.

That change is crucial for summing over doubled intervals. Strong bounds for three terms do not automatically handle four or more terms, and a powerful inverse theorem alone does not control all the losses incurred when its structured regions are repeatedly refined.

4. What the new manuscripts claim

M1’s Theorem 1.1 states that for every fixed integer $k\ge3$, there are positive constants $C_k,c_k,\varepsilon_k$ such that every $N\ge2$ satisfies

$$r_k(N)\le C_kN\exp\bigl(-c_k(\log N)^{\varepsilon_k}\bigr).$$

An equivalent formulation gives a constant $A_k\ge1$ such that an $\alpha$-dense subset of $[N]$ contains a progression whenever

$$\log N\ge A_k\bigl(2+\log(1/\alpha)\bigr)^{A_k}.$$

The source does not optimize these exponents or assert useful uniform dependence on growing $k$.

Corollary 1.2 states that every $A\subseteq\mathbb N$ with divergent reciprocal sum contains nonconstant arithmetic progressions of every finite length. The manuscript also gives stronger weighted divergence criteria. In particular, for each fixed $B\ge0$, divergence of

$$\sum_{a\in A}\frac{(\log(2+a))^B}{a}$$

already forces progressions of every finite length. This is a stronger sufficient condition because the enlarged weights may diverge for some sets whose ordinary reciprocal sum converges.

The source recovers progressions in positive-relative-density subsets of the primes as a consequence of its quantitative bound. That does not make the earlier Green–Tao theorem historically redundant; it is a new route within the claimed result.

5. Why the advance matters

Importance: 5/5. The reciprocal-sum conjecture is a central sparsity question in additive combinatorics. The claimed theorem would resolve it for every finite length and supply a quantitative strengthening well beyond qualitative density.

The connection between finite estimates and infinite sets is particularly instructive. Knowing that an avoidance density tends to zero does not ensure that its contributions across scales are summable. The manuscript claims enough decay to close precisely that gap.

Its significance is also methodological. Many additive-combinatorial arguments locate a structured region with increased density; the difficult part is retaining enough size and manageable complexity to repeat the argument. The proposed treatment of those accumulated costs would have interest beyond the final reciprocal-sum statement.

6. The main idea

Why the finite bound settles the infinite question

Suppose $A$ has no $k$-term progression. Partition the positive integers into intervals $[2^m,2^{m+1})$. Translation identifies each interval with one of length $2^m$, so its intersection with $A$ has at most $r_k(2^m)$ elements. Therefore

$$\sum_{a\in A\cap[2^m,2^{m+1})}\frac1a \le\frac{r_k(2^m)}{2^m} \le C_k e^{-c_k(m\log2)^{\varepsilon_k}}.$$

The last expression is summable over $m$. For sufficiently large $m$, it is smaller than $m^{-2}$, whose series converges. Hence a progression-free set has finite reciprocal sum, giving the desired contrapositive. This is an explanation of the manuscript’s stated deduction, rather than the difficult finite theorem itself.

Increase density without losing the ambient space too quickly

The finite argument follows a density-increment strategy. A set with too few progressions cannot behave randomly in all relevant tests. Higher-order Fourier analysis detects structure, and one finds a smaller region where the set has noticeably greater relative density.

A multiplicative increase can happen only about $\log(1/\alpha)$ times before density would exceed one. But this only helps if the regions do not shrink catastrophically at each stage. Both their dimensions and the precision of their defining constraints must be controlled.

The source uses triangular polynomial cells. These are regions described by successive polynomial conditions: later conditions may depend on integer data selected by earlier ones. The triangular order keeps track of this dependence rather than discarding it each time a new region is chosen.

Think of a sequence of increasingly precise filters on integers. If a later filter refers to an earlier rounded value, even a tiny uncontrolled change in that value can alter all subsequent tests. The manuscript retains those integer values exactly while managing the allowed widths of the surrounding constraints.

Control different levels in the right order

The claimed increment theorem bounds new precision at one level using higher levels, without feeding the current precision back into itself. Because the number of levels depends only on the fixed progression length, descending through them yields polynomial control over the whole iteration.

Higher-order inverse theorems supply correlations with nilsequences, structured sequences generalizing polynomial phases. Sampling and comparison arguments convert these correlations into a positive density increment. A separate return argument expresses that increment back in the original cell while preserving its existing equations.

This separation matters: finding an increment in a convenient temporary coordinate system is insufficient if translating it back destroys the quantitative gain. The paper’s long technical development is devoted to preserving the necessary control through those changes of description.

7. Scope, limitations, and open questions

The theorem fixes $k$ first. It does not provide a sharp joint estimate when progression length grows with $N$, and it does not claim an improved best exponent specifically for three terms.

The bound is not a fixed power saving $r_k(N)=O(N^{1-c})$. Classical constructions of large three-term-progression-free sets rule out that kind of universal bound even for $k=3$. A stretched exponential in $\log N$ occupies a different scale.

The divergence criterion is sufficient, not necessary. A set with convergent reciprocal sum can still contain arbitrarily long progressions, for instance by including widely separated finite intervals of increasing lengths. The theorem does not classify all sets containing such patterns.

Natural quantitative questions remain about the best possible exponent, its dependence on $k$, and how closely upper bounds can approach known constructions. These are finer issues than the all-length divergence conclusion.

8. Sources and further reading

M1’s Theorem 1.1 gives the finite bound and Corollary 1.2 the reciprocal-sum consequence. Sections 1.2–1.3 describe the historical estimates and the precision problem; Section 10 completes the iteration, and Section 11 develops weighted consequences.

The primary papers linked in Section 3 trace the progression from Roth and Szemerédi to recent quantitative work. Wikipedia’s Szemerédi’s theorem is optional background; all parameters needed for the claims above have been defined here.

Source manuscripts

• M1. OpenAI, Quasipolynomial Bounds for Arithmetic Progressions (September 23, 2026).

Sources consulted on 11 October 2026 at repository revision fd4aeeb. Download the manuscript citations.