Arithmetic progressions and divergent reciprocal sums

Source and verification

This article explains family 159 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Progression-free sets and reciprocal sums

A $k$-term arithmetic progression is a sequence $a,a+d,\dots ,a+(k-1)d$ with positive integer common difference $d$. Let $r_k(N)$ be the largest size of a subset of $\{1,\dots ,N\}$ containing no such progression. For fixed $k$, the qualitative assertion $r_k(N)=o(N)$ says that positive density eventually forces a progression.

The manuscript claims a much stronger quantitative estimate.

Manuscript claim

For every fixed integer $k\ge 3$, there are positive constants $c_k,C_k,{\epsilon }_k$ such that, for all sufficiently large $N$,

$$\frac{r_k(N)}{N}\le C_k{e}^{-c_k(\log N{)}^{{\epsilon }_k}}.$$

Consequently, every set of positive integers whose reciprocal sum diverges contains arithmetic progressions of every finite length. (OpenAI, 2026)

The constants depend on $k$; no useful uniform dependence or optimized exponent for three-term progressions is asserted here. An equivalent way to express the scale is that a set of density $\alpha$ must contain a progression once $\log N$ exceeds a fixed power, depending on $k$, of $2+\log (1/\alpha )$.

🏷️ The reciprocal-sum deduction

The consequence has a short proof that isolates the strength of the estimate. Suppose $A\subset \mathbb{N}$ contains no $k$-term progression. In a dyadic interval $[2^m,2^{m+1})$, every reciprocal is at most $2^{-m}$, while the number of elements of $A$ is at most $r_k(2^{m+1})$. Thus, after adjusting constants,

$$\sum _{a\in A\cap [2^m,2^{m+1})}\frac{1}{a}\le C\exp (-c{m}^{{\epsilon }_k}).$$

The series on the right converges. For example, the substitution $u=x^{{\epsilon }_k}$ in its integral comparison leaves an exponentially decaying integrand times a fixed power of $u$. Summing over $m$ proves ${\sum }_{a\in A}1/a<\infty$.

The same argument allows a factor $(\log (2+a){)}^B$ in the numerator for every fixed $B\ge 0$: on the $m$th interval this adds only a polynomial factor in $m$. Qualitative density decay alone would not justify either conclusion. A bound such as $|A\cap [1,N]|=o(N)$ gives no summable rate across dyadic scales.

🏷️ Density increments and the size budget

A density-increment argument starts with a progression-free set of density $\alpha$ and locates a structured region on which its relative density is larger. If each successful step increases density by a fixed factor, only $O(\log (1/\alpha ))$ steps are possible before the density exceeds one.

The decisive issue is how much the underlying region shrinks. A proof can establish a density increment at every step and still obtain a very weak theorem if each new region is too small. To reach the displayed bound, the total loss in logarithmic size must be bounded by a fixed power of $\log (1/\alpha )$.

The manuscript works with polynomial cells, regions cut out by polynomial phase constraints. These are organized into blocks with different weights. Later blocks can depend on earlier blocks, so the cells have a triangular dependency structure. Their widths are small enough to give unique local coordinate choices.

Each block has a precision parameter, measuring the logarithm of the reciprocal width. A central estimate bounds the precision required at one weight using the parameters at higher weights, without feeding the same or lower weight back into itself. Since the maximum weight is fixed by $k$, descending induction controls the total precision by a fixed power. This triangular bookkeeping prevents an uncontrolled cascade of repeated exponentiation.

🏷️ Fresh coordinates and return to the old cell

An inverse theorem detects structure when progression counts differ substantially from their random-model values. In this argument, the detected structure is represented using polynomial sequences on compact spaces with a finite hierarchy of commutators, often called nilsequences. Their detailed geometry is an input to the proof architecture rather than a prerequisite developed in these notes.

Merely applying an inverse theorem does not produce the desired bound. It can introduce new coordinates whose complexity grows with the existing system. The manuscript instead seeks a density gain in fresh coordinates with estimates that do not deteriorate with the ambient number of coordinates. It then returns to a region satisfying the old constraints.

That return is essential. A gain on an unrelated region would not support iteration within the original progression-free set. Positive comparison shifts and degree-lowering arguments preserve the earlier conditions, while neighborhood estimates retain the incoming radius instead of restarting from an uncontrolled smaller scale.

The quantitative conclusion therefore depends on three components together: detection of structure, a useful density gain, and a return mechanism whose accumulated size loss remains polynomial in the logarithmic density parameter. The first component alone is not the claimed quasipolynomial theorem.

🏷️ Key steps and proof outlines

Why the bookkeeping has to be triangular

The difficult quantitative issue is that finding a denser structured piece may add coordinates and demand finer precision. If the next precision were an arbitrary polynomial of the previous precision, iterating for $O(\log (1/\alpha ))$ rounds could destroy the claimed bound. The manuscript’s “Iteration” section instead separates a fixed number $D$ of weights. Here $\alpha$ is the initial density, $d_i$ is the number of coordinates of weight $i$, and a width log measures the logarithm of the reciprocal tolerance for those coordinates. The number $D$ depends on the progression length, not on $\alpha$ or the eventual numerical tolerances. (OpenAI, 2026)

Structural invariant

A preparation cut at weight $i$ can export new coordinates only to lower weights. The increase at weight $i$ therefore depends on the incoming dimensions strictly above $i$, rather than recursively on its own enlarged dimension.

The proof makes this concrete. During one preparation round, define

$$H_D=d_D,H_i=d_i+H_{i+1}^2(i<D).$$

A cut lowers the current value-space dimension by one. At level $i$, at most $H_i$ cuts can occur, and each exports at most $H_i$ coordinates to the next lower level. Thus its total export is at most $H_i^2$. Restarting a probabilistic test does not reset that value space, so restarts cannot manufacture additional cuts. If the newly introduced absolute tuple has at most $d_0$ coordinates, the output satisfies

$$d_i^{\mathrm{out}}\le d_i+d_0+H_{i+1}^2,H_{D+1}=0.$$

Start at the top weight and descend. Over $T$ rounds the top dimension grows at most linearly in $T$; the next dimension accumulates a polynomial in that top bound; and so on through the fixed $D$ levels. Every dimension consequently remains polynomial in the common budget parameter and $T$. A fixed depth of triangular dependencies is crucial here.

Width losses must avoid their own current width

Let $q_j$ be the incoming width log at weight $j$. The source schedules precision from weight $D$ downward, after higher-weight requests are already fixed. Some auxiliary requests may depend on $q_j$. The stronger fact needed for iteration is that the added width loss does not:

$$Q_j^{\mathrm{out}}\le q_j+P_j(p,d_{\ast },q_{>j}).$$

Here $p$ is the common accuracy budget, $d_{\ast }$ bounds all structural dimensions, $q_{>j}$ denotes higher-weight width logs, and $P_j$ is a fixed polynomial. Its independence of $q_j$ prevents self-amplification. This is a statement about logarithms: a tolerance may itself be exponentially small in a polynomial while its bookkeeping remains affordable.

Proof outline. Record the losses from preparation cuts, ascent back to the original coordinates, and root compression separately. Each has polynomial logarithmic cost in the already scheduled higher-weight requests. Descending substitution combines them into $P_j$. For a proposed $T$-round run, define envelopes

$$\begin{array}{rl}{V}_D& =Q_D(0)+T{P}_D(p,d_{\ast }),\\ V_j& =Q_j(0)+T{P}_j(p,d_{\ast },V_{>j}).\end{array}$$

Descending induction gives $Q_j(t)\le V_j$ at every round $t\le T$. Starting with no coordinates and trivial widths makes all envelopes polynomial in $p$ when $T=O_k(1+p)$. The root slice losses also have polynomial logarithmic cost, so summing them over all rounds preserves this scale. This is the quantitative role of the manuscript’s return-to-old-constraints machinery: new coordinates cannot erase the cost of satisfying old constraints.

Closing the density increment

The source takes $p=C(2+\log (1/\alpha ))$ and starts its certified target at $a_0=\alpha /2$. Each successful round multiplies that target by at least $1+{\eta }_k$, where ${\eta }_k>0$ depends only on the progression length. Reserve

$$T=\lceil \frac{\log (2/\alpha )}{\log (1+{\eta }_k)}\rceil +1.$$

The forecasts above guarantee sufficient room for every possible round if $\log N\ge C_k(2+\log (1/\alpha ){)}^{A_k}$. Yet $T$ successful increments would force a target at least one. The certificate then contradicts the pointwise bound $f{B}^{-}\le B^{+}$, where $f$ is the indicator and $B^{-},B^{+}$ are the lower and upper cell weights used by the source. The alternative is that an earlier progression-producing step has already ended the iteration.

Taking the contrapositive and solving for $\alpha$ gives the stated stretched-exponential density bound. Its reciprocal-sum consequence then needs no additional structural theorem: on the dyadic interval $[2^m,2^{m+1})$, the reciprocal contribution is bounded by a constant times $e^{-c{m}^{{\epsilon }_k}}$, a summable sequence. The new ingredient is therefore the controlled iteration, with the final summation an elementary consequence. These are selected proof interfaces from the manuscript, not an independent verification of its full structural apparatus.

See Also

• Van der Waerden growth gives lower bounds for the interval length needed to force a monochromatic progression, complementing the present upper-bound mechanism.
• Finite sums and products concerns simultaneous additive and multiplicative configurations, with a different recurrence argument.

🏷️ Manuscripts and verification scope

• Quasipolynomial Bounds for Arithmetic Progressions — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The selected statement is the reciprocal-sum consequence. The quantitative progression-free bound is outside that selected statement. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026. Quasipolynomial Bounds for Arithmetic Progressions.