Erdős Conjecture on Arithmetic Progressions

Erdős \$3000 Conjecture on Arithmetic Progressions

OpenAI's claim

Progression-free density and reciprocal sums: For each fixed length $k\ge3$, the claimed progression-free density decays as $\exp(-c_k(\log N)^{\varepsilon_k})$ up to a fixed factor. This quantitative estimate is used to deduce arbitrarily long progressions from a divergent reciprocal sum.

Mathematical statement of the claimed result

Mathematical claim 1.

For each fixed integer $k\ge3$, let $r_k(N)$ denote maximal cardinality among subsets of $\{1,\ldots,N\}$ containing no arithmetic progression $a,a+d,\ldots,a+(k-1)d$ with $d\ne0$. The claim gives constants $C_k,c_k,\epsilon_k>0$ with \[r_k(N)\le C_kN\exp\{-c_k(\log N)^{\epsilon_k}\}\quad(N\ge2).\] Its divergent-reciprocal-sums corollary asserts \[A\subset\mathbb N,\ \sum_{a\in A}a^{-1}=\infty\quad\Longrightarrow\quad A\text{ contains a nonconstant progression of every finite length}.\] This concerns sets of distinct positive integers. It does not settle a separate finite-field progression clause.

Outline of the argument

Progression-free density and reciprocal sums: Density increments take place inside triangular polynomial cells rather than repeatedly discarding inherited structure. Integer coordinate blocks and exact substitution retain old constraints when new ones are added. A hierarchy of precision costs bounds the total logarithmic length loss by a polynomial in the logarithmic density parameter, enabling the quasipolynomial estimate and the reciprocal-sum consequence.

Formal verification

Family 159 describes Lean coverage for the divergent-reciprocal-sum progression consequence; the quantitative progression-free density bound is not selected.

Progression-free density and reciprocal sums: The manuscript links ErdosReciprocal.lean.

The documented selection does not cover the entire manuscript assertion relevant here.

This site has not run the Lean development. These links describe OpenAI’s selected formal statements and should be read with their stated scope.

Status caveat

OpenAI reports that an internal model produced the manuscripts. Their arguments have not been independently verified as proofs by this site. Any portion outside the documented formal scope may contain mistakes, and the catalogue label reports the announced mathematical claim.

Sources

• OpenAI, Quasipolynomial Bounds for Arithmetic Progressions, 2026-09-23; citation key OAI:Quasipolynomial-Bounds-for-Arithmetic-Progressions-September-23-2026. PDF (GitHub); PDF (direct); Manuscript page and citation; Latest version; Statement source: ap:main; Statement source: ap:reciprocal.
• Family 159: Lean scope.
• Comparator ErdosReciprocal.json.
• Comparator ErdosReciprocal.lean.
• Family 159: Reasoning summary.
• OpenAI catalogue entry.

Erdős Conjecture on Arithmetic Progressions

OpenAI's claim

Progression-free density and reciprocal sums: For each fixed length $k\ge3$, the claimed progression-free density decays as $\exp(-c_k(\log N)^{\varepsilon_k})$ up to a fixed factor. This quantitative estimate is used to deduce arbitrarily long progressions from a divergent reciprocal sum.

Mathematical statement of the claimed result

Mathematical claim 1.

For each fixed integer $k\ge3$, let $r_k(N)$ denote maximal cardinality among subsets of $\{1,\ldots,N\}$ containing no arithmetic progression $a,a+d,\ldots,a+(k-1)d$ with $d\ne0$. The claim gives constants $C_k,c_k,\epsilon_k>0$ with \[r_k(N)\le C_kN\exp\{-c_k(\log N)^{\epsilon_k}\}\quad(N\ge2).\] Its divergent-reciprocal-sums corollary asserts \[A\subset\mathbb N,\ \sum_{a\in A}a^{-1}=\infty\quad\Longrightarrow\quad A\text{ contains a nonconstant progression of every finite length}.\] This concerns sets of distinct positive integers. It does not settle a separate finite-field progression clause.

Outline of the argument

Progression-free density and reciprocal sums: Density increments take place inside triangular polynomial cells rather than repeatedly discarding inherited structure. Integer coordinate blocks and exact substitution retain old constraints when new ones are added. A hierarchy of precision costs bounds the total logarithmic length loss by a polynomial in the logarithmic density parameter, enabling the quasipolynomial estimate and the reciprocal-sum consequence.

Formal verification

Family 159 describes Lean coverage for the divergent-reciprocal-sum progression consequence; the quantitative progression-free density bound is not selected.

Progression-free density and reciprocal sums: The manuscript links ErdosReciprocal.lean.

The documented selection does not cover the entire manuscript assertion relevant here.

This site has not run the Lean development. These links describe OpenAI’s selected formal statements and should be read with their stated scope.

Status caveat

OpenAI reports that an internal model produced the manuscripts. Their arguments have not been independently verified as proofs by this site. Any portion outside the documented formal scope may contain mistakes, and the catalogue label reports the announced mathematical claim.

Sources

• OpenAI, Quasipolynomial Bounds for Arithmetic Progressions, 2026-09-23; citation key OAI:Quasipolynomial-Bounds-for-Arithmetic-Progressions-September-23-2026. PDF (GitHub); PDF (direct); Manuscript page and citation; Latest version; Statement source: ap:main; Statement source: ap:reciprocal.
• Family 159: Lean scope.
• Comparator ErdosReciprocal.json.
• Comparator ErdosReciprocal.lean.
• Family 159: Reasoning summary.
• OpenAI catalogue entry.

Erdős \$3000 Conjecture on Arithmetic Progressions

Definitions and mathematical statement

For $A\subseteq{\mathbb{Z}}_{>0}$, divergence of its reciprocal sum means $\sum_{a\in A}1/a=\infty$. A nonconstant arithmetic progression of length $k$ is $a,a+d,\ldots,a+(k-1)d$ with integers $a,d\ge1$. The question is whether \[ \sum_{a\in A}\frac1a=\infty\quad\Longrightarrow\quad \forall k\ge1\ \exists a,d\ge1:\ \{a+jd:0\le j<k\}\subseteq A. \] Positive density is not assumed, and the common difference can depend on the requested length.

Formulation and concept references: [S1].

Short English statement

Does divergence of a set's reciprocal sum force it to contain arithmetic progressions of every finite length?

Research attempt

Current frontier and scope.

The reciprocal-sum question is much stronger than a positive-density progression theorem: the density of a set with divergent reciprocal sum may tend to zero. The supplied entry associates the problem with Green's historical article. [S1] The exact target used here is the displayed catalogue statement; the quantitative input used below is the separate theorem of Bloom--Sisask. For length three, Bloom--Sisask's Theorem 1 gives $r_3(N)\leq N\exp(-c(\log N)^{1/9})$, which is strong enough to make the reciprocal sum of any three-term-progression-free set finite. [E1] This does not supply the same quantitative conclusion for every fixed progression length. The frontier check on 27 September 2026 did not yield a verified resolution of the full all-length statement. The deductions below are independent of any purported solution claim.

Attack map.

A density-increment approach must produce a summable sequence of density upper bounds across scales, not merely densities tending to zero. A counterexample approach might glue large finite progression-free sets at separated scales; the difficulty is preventing progressions that cross between blocks. A compactness argument based only on finite examples would not control their reciprocal mass. Here the gluing route can be made exact, producing an equivalence between the original fixed-length problem and a specific numerical series, together with a canonical computable counterexample if that series diverges.

Attempt I: separate blocks so that no three-term progression crosses.

Fix $k\geq3$. Write \[ r_k(N)=\max_{\substack{B\subseteq\{1,\ldots,N\}\\ B\text{ has no nonconstant }k\text{-term progression}}}|B|, \qquad a_j=\frac{r_k(4^j)}{4^j}\quad(j\geq0). \] For each $j$, choose a largest $k$-term-progression-free set $B_j\subseteq[1,4^j]\cap{\mathbb{Z}}$. Define \begin{equation}\label{wsref-0-31-38-35-37-3a-67-6c-75-69-6e-67} A_k=\bigcup_{j\geq0}(2\cdot4^j+B_j),\qquad I_j=[2\cdot4^j+1,3\cdot4^j]\cap{\mathbb{Z}}. \end{equation} The intervals $I_j$ are disjoint. The separation is chosen so that no nonconstant three-term progression in their union can meet two different intervals.

To prove the latter assertion, suppose $x<y<z$ and $x+z=2y$, with $z\in I_j$ the highest occupied block. If $y$ lies in an earlier block, then $y\leq3\cdot4^{j-1}$ and \[ z=2y-x\leq6\cdot4^{j-1}-1<2\cdot4^j+1, \] a contradiction. If $y\in I_j$ but $x$ lies earlier, then \[ z=2y-x\geq4\cdot4^j+2-3\cdot4^{j-1}>3\cdot4^j, \] again a contradiction. For $j=0$ there is no earlier block. Thus all three terms lie in one interval.

Every consecutive triple of a $k$-term progression is a three-term progression. Overlapping consecutive triples force all $k$ terms into the same block. Such a progression cannot occur in $A_k$, since its translate back into $B_j$ is forbidden. This proves that $A_k$ is $k$-term-progression-free even when the individual $B_j$ contain many shorter progressions. Assuming they are three-term-free would have unnecessarily weakened the construction.

Attempt II: an exact summability equivalence.

Every member of $2\cdot4^j+B_j$ is at most $3\cdot4^j$. Consequently \begin{equation}\label{wsref-0-31-38-35-37-3a-6c-6f-77-65-72} \sum_{a\in A_k}\frac1a \geq\frac13\sum_{j\geq0}\frac{|B_j|}{4^j} =\frac13\sum_{j\geq0}a_j. \end{equation} Conversely, for any $k$-term-progression-free $A\subseteq{\mathbb{Z}}_{>0}$, partition the positive integers into $[4^j,4^{j+1})$. There are at most $r_k(4^{j+1})$ members of $A$ in this interval, and each has reciprocal at most $4^{-j}$. Therefore \begin{equation}\label{wsref-0-31-38-35-37-3a-75-70-70-65-72} \sum_{a\in A}\frac1a\leq4\sum_{j\geq1}a_j. \end{equation} Both statements use nonnegative series, so no conditionally convergent rearrangement is involved.

Lacunary extremal-series lemma. For every fixed integer $k\geq3$, the following are equivalent: \[ \begin{gathered} \text{every $k$-term-progression-free subset of ${\mathbb{Z}}_{>0}$}\\ \text{has finite reciprocal sum}\\[2pt] \Longleftrightarrow\quad \sum_{j\geq0}\frac{r_k(4^j)}{4^j}<\infty. \end{gathered} \] Proof. Convergence implies the first assertion by (1857:upper). Divergence produces the explicit counterexample (1857:gluing) by (1857:lower). $\square$

It follows that the entire conjecture in the original entry is equivalent to convergence of this series for every fixed $k\geq3$. Lengths one and two cause no exception: a set with divergent reciprocal sum is infinite. This is more than a one-directional sufficient density estimate, but no assertion is made that the series has now been evaluated for general $k$.

The same proof gives a quantitative finite form. Put \[ W_k(N)=\max_{\substack{A\subseteq[1,N]\cap{\mathbb{Z}}\\A\text{ $k$-term-free}}} \sum_{a\in A}\frac1a. \] For every $J\geq0$, \begin{equation}\label{wsref-0-31-38-35-37-3a-66-69-6e-69-74-65} \frac13\sum_{j=0}^{J}a_j \leq W_k(3\cdot4^J) \leq4\sum_{j=1}^{J+1}a_j. \end{equation} The lower bound uses the first $J+1$ blocks in (1857:gluing); the upper bound is the same interval partition, stopped before $4^{J+1}$. Thus convergence would in fact give a uniform reciprocal-sum bound depending only on $k$, although the original statement does not ask for an explicit bound or a rate.

Attempt III: make a hypothetical counterexample computable.

Choose $B_j$ canonically: enumerate all subsets of $[1,4^j]$, test all candidate progressions, maximize cardinality, and use lexicographic order to break ties. This is an astronomically slow but terminating finite procedure. Membership of an integer $n$ in $A_k$ is decidable: find whether it belongs to one of the disjoint intervals $I_j$, and, if so, perform that finite search and test $n-2\cdot4^j\in B_j$.

Therefore, if the conjecture is false at some fixed length $k$, it has a computable counterexample of the specific form (1857:gluing). No effectiveness assumption has been appended to the original problem: the conclusion follows from the extremal series equivalence. The unknown point is not the algorithm's termination, but whether its output set has divergent reciprocal sum. Computing larger finite portions cannot decide that infinite-series question without a new uniform argument.

A nonconstructive choice of different near-extremizers at every scale is likewise not an obstacle here. The separation lemma permits all scales to be used simultaneously. The missing arithmetic information is entirely in their attainable relative sizes $a_j$.

Testing the reduction against known estimates.

The length-three theorem cited above yields \[ a_j\leq\exp(-c'(j\log4)^{1/9}) \] after adjusting constants and omitting finitely many initial terms. This series converges, for example by comparison with the integral of $\exp(-c''x^{1/9})$. Hence the three-term case follows rigorously from the extremal-series lemma. [E1] No comparable all-$k$ summable estimate has been proved in this attempt.

For general $k$, a bound $r_k(N)\ll_k N/(\log N)^{1+\delta_k}$ with any $\delta_k>0$ would suffice. In contrast, $r_k(N)=o(N)$ gives only $a_j\to0$, which does not imply $\sum a_j<\infty$. Even an upper bound of order $1/j$ for $a_j$ would not prove convergence. These observations describe what particular estimates can or cannot establish; they do not assert that the actual extremal sequence equals $1/j$ or that a counterexample has been found.

The harmonic weights are essential to the calculation: translation to $[2\cdot4^j+1,3\cdot4^j]$ keeps the reciprocal mass comparable to $|B_j|/4^j$. Moving blocks arbitrarily far out would eliminate crossing progressions but could destroy all the reciprocal divergence.

Stress test.

The gluing proof is checked for the worst placement of the smaller terms, not merely for progressions with one term in each of three successive blocks. It handles two terms in the largest block and one term in any earlier block, and also one term in the largest block. Only nonconstant progressions are considered, exactly as required. The overlapping-triple argument is what extends the construction from length three to every $k\geq3$.

The companion script exhaustively computes small extremizers for $k=3,4$ and $N\leq16$, forms the corresponding initial blocks, and checks the absence of cross-block three-term progressions and of $k$-term progressions in their union. Reciprocal sums and both sides of the finite inequalities are checked with exact rational arithmetic. This verifies examples and endpoints; the all-scale proof is supplied above, rather than inferred from the finite search.

The exact search, with lexicographic tie-breaking, gives the following initial extremizers used in the finite gluing check: \[ \begin{array}{c|r|r|l} k&N&r_k(N)&B\\\hline 3&1&1&\{1\}\\ 3&4&3&\{1,2,4\}\\ 3&16&8&\{1,2,4,5,10,11,13,14\}\\ 4&1&1&\{1\}\\ 4&4&3&\{1,2,3\}\\ 4&16&10&\{1,2,3,5,6,8,9,10,15,16\}\\ \end{array} \] The last column records actual subsets, not just a numerical upper bound; maximality in this finite range is certified by exhaustive search.

Outcome.

Outcome: Conditional reduction.

The fixed-length reciprocal-sum assertion is exactly equivalent to summability of $r_k(4^j)/4^j$, with a canonical computable counterexample if the series diverges. The construction also gives uniform finite harmonic-mass inequalities and recovers the length-three case from an established quantitative theorem. For arbitrary $k$, neither convergence nor divergence of the required series has been established. These reductions are not claimed to be new to the literature, and no complete solution of the original all-length problem is claimed.

Sources

• S1 B. Green, Arithmetic progressions at the Journal of the LMS, Journal of the London Mathematical Society $2026$. https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/jlms.70483. Catalogue formulation source.
• E1 Thomas F. Bloom and Olof Sisask. An improvement to the Kelley--Meka bounds on three-term arithmetic progressions, arXiv:2309.02353v1, 5 September 2023. Theorem 1: $r_3(N)\leq N\exp(-c(\log N)^{1/9})$. Used as a sufficient summable bound, not as an all-length theorem. https://arxiv.org/html/2309.02353v1. Consulted 27 September 2026 for the indicated result or scope.