2026-08-29 · article Erdős problemsunsolved problemscombinatorics

The Erdős conjecture on arithmetic progressions — the records 3.0085385 for k=3 and 4.4397535 for k=4 are each a single machine-checked theorem

Leanmachine-checked (Lean 4 + mathlib, standard axioms only, no sorryAx, no native_decide; theorem names given) paperproved, not yet machine-checked computationchecked on this machine, within the range stated; not a claim made to the outside knowna restatement, a known theorem, or a check of the literature

There is a conjecture Erdős put $5,000 on in his lifetime.

The Erdős arithmetic progression conjecture: for a set A of positive integers, if Σ_a∈A 1/a = ∞ then A contains arbitrarily long arithmetic progressions.

"A set dense enough for its sum of reciprocals to diverge cannot avoid arbitrarily long arithmetic progressions." The sum of the reciprocals of the primes diverges, so if this is right then the primes contain arbitrarily long arithmetic progressions (this special case was proved separately by Green–Tao in 2004).

This conjecture translates into a single sequence of numbers.

This is Erdős problem #169. And —

Erdős asked two things: to estimate f(k), and whether lim f(k)/log W(k) = ∞ (W(k) the van der Waerden number). For the latter, f(k)/log W(k) ≥ 1/2 is trivial, and no constant above 1/2 is known.

The known lower bounds come in three layers: Berlekamp's (log 2/2)·k of 1968, Gerver's (1−o(1))·k log k of 1977, and Walker's 2025 records for individual k. This article is about moving the third layer.

The wall is at "logarithmic exponent 1"

Why is only k=3 settled while k=4 and above are open? It comes down to one place.

Write the density of the part of a k-AP-free set in [N, 2N) as δ_k(N) = r_k(N)/N (r_k being the maximum size); then the sum of reciprocals is bounded by

Put the known upper bound rk(N) ≪ N/(log N)θ in here and δ_k(2^j) ≈ j^−θ, so —

Σ j^−θ converges only when θ > 1.
Proving the conjecture for k is the same as raising the logarithmic exponent θ above 1.

Every known result lines up on this single line.

As long as c < 1, the upper bound for k≥5 is weaker than any polylogarithm (exp(−(log log N)^c) against exp(−c·log log N)). It is not even on the θ scale.

And for k=4, Green–Tao write in their own paper that "this is the limit of our method". The limit of the method and the position of the wall coincide exactly at k=4.

The lower bound side — sets that have actually been built

Walker 2025's reduction — the search space becomes finite-dimensional

Kempner sets alone are enough. That is, with only sets of the form "fix a base b and a digit set S, and take the integers all of whose base-b digits lie in S", one can reach f(k) − ε for any k and ε.

An ocean of infinite sets becomes a search over pairs (b, S). All the work in this article sits on top of this theorem.

* But "enough" is a statement about the limit; it does not say that a finite b will get there. This is a place where "enough" is easily reread as "enough in practice" (the type of leap where a shortened word is re-expanded).

Raising the upper bound is out of reach. We went over to the lower bound side — actually building sets. Two tools were needed, and both could be written.

The second is the crux. Not "we searched up to 10⁶ and found no arithmetic progression" but "there is none", said by a finite computation.

Once a tool exists, check it against a known answer first

A peer-reviewed record from 2025, reproduced independently. The numbers from here on can be trusted.

* The difference in the last digits of 5 and 6 (1.2×10⁻⁸) is lattice interpolation error, not an improvement.

Only the greedy one failed to land. The other five differ in their mechanism and in the breadth of their search space, and yet return the same set. Walker searched the same place with 8,679 core-hours of C++ and calls it "an influential local maximum".

What is at that point — the Szekeres set (1962)

The band on top has the shape of a Cantor set. The same pattern at every scale — this matters later. The curve below is the partial sum of the reciprocals, and 4,000 terms in, it is still 0.019 short. Reaching this value by enumeration is effectively impossible, and there is no way but solving the functional equation — which is why the tools of §03 were needed.

Generalising as far as a Bellman equation

A Kempner set has the form "the same (b, S) at every digit". It ought to be allowed to vary digit by digit, and further, branch by branch.

A sufficient condition for this family to be 3-AP-free is "at each node F is 3-AP-free in ℤ/cℤ". The sum of reciprocals is linear in F, so maximisation becomes an optimality equation.

The lower bound sought is 1 + U*(1). What matters is that iterating from U=0, the value at every stage is a correct lower bound. The n-th iterate corresponds to "a tree of depth n" = a finite 3-AP-free set, so stopping partway does not make it a lie.

At x = 1 and at x = 0.5 alike, the optimal policy was the same, (c=3, F={0,1}). Even given the freedom to change the structure at each level, Szekeres keeps being chosen.

For k=3 the record lay outside the family. k=4 is different.

The sufficient condition goes through in the same form as k=3

Suppose V has a 4-AP with common difference D > 0. Writing v_i = f_i + c·u_i uniquely, mod c the f_i form an arithmetic progression with common difference D mod c.
If D ≡ 0 (mod c), the f_i are all the same f and the u_i are a 4-AP inside V^(f). → down to the lower level (induction).
If D ≢ 0, then (f₁,f₂,f₃,f₄) is a non-constant 4-AP in ℤ/cℤ with every term in F.

Hence "at each node F contains no non-constant 4-AP in ℤ/cℤ" is a sufficient condition. ∎

The record set is inside the family — the starting point is already at the record

We checked over all 55×54 pairs whether Walker's S contains a non-constant 4-AP in ℤ/55ℤ. It does not.

So the policy of using (55, S) at every level lies in this family, and the family's optimum is confirmed to be at least 4.4397534. The only question is whether it is strictly exceeded.

Measure the necessary condition for improvement first

The Bellman value rises only when the best (c,F) changes with x.

The sign does not change. Walker dominates for all x — a bad sign. But c = 11, a set of just 6 digits, gives 4.4217475, only 0.018 short of the record. That a small base comes this close is itself the shape in which mixing might help.

Write the prediction before measuring

The result of running it — nothing moves

For every base from 4 to 70, build the best F against the current U exactly by integer programming and add it to the candidate pool (column generation). Even after adding 92 candidates, the value stays at 4.439753373.

A stronger form — prove that it is a fixed point

Value iteration was the long way round. If T(U_W) = U_W for the Bellman operator T, then U_W is a fixed point = the family's optimum (T is a monotone contraction, so the fixed point is unique). So take one step from U_W and see whether any F exceeds it.

This part had to be done carefully. At c=55 Walker's own S is feasible, so the maximum is necessarily at least U_W. That is, "whether it is exceeded" is decided at a single knife-edge point. A provisional solution is no answer. We took the time and made the integer program prove optimality.

Optimality was proved at every x for c = 55. The largest excess is −8.482×10⁻¹³.
The negative value is within numerical error; in substance it is exactly zero — Walker's policy is precisely a fixed point.

Why nothing moves — base 55 was special

The number of elements of a Kempner set K(F,c) grows as N^{log|F|/log c}. We will call this exponent the dimension. For each base we found the largest F with no non-constant 4-AP in ℤ/cℤ by integer programming and computed the dimension.

Examining c from 4 to 157, the dimension of 55 was the largest. And the top three are 11, 55 = 5×11 and 121 = 11². The base 11 is special in this problem. That Walker found 55 with 8,679 core-hours was no accident.

But the dimension does not settle it by itself. At c=22, with the same |F| = 10, the sum of reciprocals splits into 3.135 and 4.420. The position of F — whether it contains small digits — matters strongly.

The "nothing moves" of this section is a conclusion within the family of Kempner sets — the family that chooses a base c and a digit set F at each level. Within it, Walker's set is a fixed point. Outside it, things move: truncate Walker's set and attach Behrend-type blocks, and the record is strictly exceeded. See "The record for k=4 has moved too" at the end of §07.

Nothing gets within 0.00055 of the k=3 record. We measure what that 0.00055 is.

The sum of reciprocals is dominated by the small numbers

Two thirds of it is in the first 4. So what matters is not "how large a number can be taken" but "how many small numbers can be taken".

A denser set is, on the contrary, worse

The densest 3-AP-free sets are the Behrend sets (1946, density N^{−c√(log N)}). Asymptotically denser than any Cantor type. The construction is "restrict each digit of an n-digit base-d number to below d/2 and fix the sum of the squares of the digits" — the points lie on a sphere, and a sphere is convex, so no three of them form an arithmetic progression.

The Behrend type is overwhelmingly worse. The best is 0.890, not even a third of Szekeres.
Being asymptotically dense and being able to take small numbers are different things. A Behrend set can take only 2 elements in the range 25.

Then what is optimal on a finite interval?

We solved exactly, by integer programming, for the 3-AP-free subset of [1, M] with the largest sum of reciprocals. Only the M for which optimality could be proved are listed (truncated values are not used).

For M ≤ 52, Szekeres is exactly optimal. The integer program returns the very set from 1962.
At M = 53 it loses for the first time (pinned down by bisecting in steps of 1). The gap is 0.0013298 — already larger than the 0.00055 gap to the record.

How it loses is telling too.

The first 8 are exactly the same. They part at the ninth, where Szekeres takes 28 and the optimum takes 30. And the optimum uses the interval right up to 53 (its end), packing in one more element. Szekeres does not use up the end — because the self-similar structure is cut off there.

That advantage becomes a trap when the horizon is extended (exact)

The optimal set A at M = 53 beats Szekeres by +0.0013298. So if you continue optimally from that A, does the advantage survive? We fixed the head, optimised [54, H] exactly by integer programming, and compared the two starting points.

* Optimality was proved in all four optimisations (not truncated).

The +0.0013 advantage at 53 turns into a −0.0347 debt at horizon 128.
And in [54, 80], nothing at all can be added from either head — which is why Szekeres itself jumps from 41 all the way to 82.

Taking early is a trap. A local improvement becomes a global cost — "the price of self-similarity", proved in a moving form, as a single number.
(The optimal continuation of [54,128] from the Szekeres head coincides exactly with Szekeres's own continuation. That is proved too.)

Local surgery moves nothing anywhere (exact)

We checked the reverse direction too. With the future fixed to Szekeres, can the middle be rebuilt? Taking Szekeres ∩ [1, 6561] (256 elements) as the base, we freed an interval entirely — removing the Szekeres elements in it as well, and choosing from scratch — and optimised exactly.

The gaps in Szekeres are not laziness; they are completely blocked. Fix what comes before and after to Szekeres and nothing can be added to the empty bands; free a whole block and Szekeres itself comes back.

Combined with the trap of taking early (above), this can be said — Szekeres is locally inoperable. Whatever finite window you touch, as long as the outside is Szekeres, Szekeres is optimal.
Therefore the record set (3.00849) does not differ from Szekeres at some finite place; it must differ globally, in the whole way of continuing from some scale onwards.

Szekeres still wins because it can splice on a tail

Splicing a distant tail T = {c·v : v ∈ V, v ≥ 1} onto a finite head H ⊆ [1, M] gives a 3-AP-free set if c > 2M (two from the head and one from the tail is impossible since t = 2h₂−h₁ ≤ 2M < c ≤ min T; one from the head and two from the tail gives 2t₁−t₂ = c(2v₁−v₂), which if non-zero has absolute value at least c and so is not in the head, and if zero is not a positive element; the form that straddles the head, t₁+t₂ = 2h, contradicts c > 2M; and three from the tail is covered by the tail being 3-AP-free itself).

But this tail adds almost nothing. The contribution is Σ 1/(c·v) = 3.007939/c, which for c = 161 (M = 80) is 0.0187.

Separate and you are safe, but you lose exactly as much of the sum as you separate. Szekeres is strong because it is thinly mixed at every scale — the tail slips into the gaps of the head and does not need to be separated.

The price of separating is what this section measures.
Almost all of the record's excess 0.00055 is generated beyond the scale 2^24.4, where the tail of Behrend-type blocks becomes denser than the tail of the self-similar continuation (§08). What the finite-interval computations of this section show is the part before that — at low scales the self-similar continuation is inoperable.

Up to here the work was re-measuring known things. Only this section is a new lower bound. For k=3 and for k=4 alike, that the set contains no progression and that it exceeds the record is one theorem in Lean. Read it together with "The limits of this section" at the end.

LeanShiori959.erdos169_lower_record_939 — the 84-step set contains no 3-AP and its reciprocal sum exceeds 3.0085385 (and so the 1984 record 3.00849). Wróblewski's Lemmas 1 and 2 are written out and machine-checked as well; nothing is borrowed from outside.

What was changed

Wróblewski's construction is made of two parts. A head (the Szekeres set cut at 21 523 361, sum of reciprocals 3.0042100) and a sequence of blocks spliced on after it. The splicing — placing three translated copies of a block T after a set Z — is guaranteed as it stands by his lemma.

Neither the splicing nor the head was changed. Only the sequence of blocks was replaced.

Here B(p,q,r) is a Behrend-type block: choose digits from p possibilities, lay them out in base 2p−1, and fix the sum of the quadratic form of the digits at r.

Why that increases it

The number of elements of a block B(p,·,·) grows as N^(log p / log(2p−1)) against its width N. This exponent — the dimension — rises with p.

Wróblewski fixed p = 6. A parameter chosen on a 1983 computer (an ODRA 1305) had stayed in place for 42 years.

Since the sum of reciprocals is dominated by the small numbers, at low scales a block with a small base pays better. But the further the scale grows, the more a block of higher dimension — that is, with larger p — pays.
Grow the base along with the scale. That alone moved the record.

This has the same shape as the picture in §02, "the wall is at the logarithmic exponent". On the lower-bound side too, what does the work is the exponent.

How exact is it

Floating point is never gone through.

The value at 84 steps is 3.0085385221. Truncation only pushes the lower bound down, so this value is a lower bound as it stands. Lean guarantees the digits up to 3.0085385; the 10-digit value itself lies on the side of exact integer arithmetic.

* We also confirmed that an independently written floating-point implementation (a centred-moment expansion) agrees with the per-step contributions to within 10⁻⁹.

The limits of this section

• Nothing is said about the upper bound. That f(3) is finite is already known, and this work only improves one "set that can actually be built" within that
• Whether it works is decided not by comparing dimensions at a fixed scale but by how the tails decay. The same shape works for k=4 ("The record for k=4 has moved too" below). It has not been applied to k ≥ 5
• No optimality is claimed for the choice of steps (Bellman). The room left inside this frame is roughly 5×10⁻⁶ by a coarse estimate

The record for k=4 has moved too

In §05 we proved that Walker's set is a fixed point within the family of Kempner sets. Outside that family, it moves. The idea is the same as in §07: cut the self-similar continuation partway and switch to Behrend-type blocks. What Wróblewski did to the Szekeres set for k=3, we did to Walker's set for k=4.

Why the blocks can be attached — one lemma

When a block is attached, the trouble is a k-AP with one point in the lower window and k−1 points in the upper one. Tao pointed out this gap in the forum thread for this problem (September 2025) and closed it by a probabilistic thinning, which is useless for a numerical lower bound. The following lemma closes the same gap without loss.

Lemma (k ≥ 4). If the head is k-AP-free, each block is (k−1)-AP-free, and the least element of each block exceeds twice the largest element of everything before it (the doubling rule), then the union is k-AP-free. There is no condition on the lengths of the windows.

The proof is a one-page case analysis (an adjacent pair straddling the boundary between head and block forces the difference to be at least the width of the gap, and the second term then falls outside the head). For k=4 the blocks need only be 3-AP-free — so Wróblewski's blocks from §07 serve as they are. For k=3 the condition reduces to Wróblewski's own doubling rule a > max(2z, z+t). The lemma is proved in Lean 4 (Shiori1109.lemma2_four; no sorry, standard axioms only).

Why it beats the record — how the tails decay

The tail of a Kempner set above scale z decays like z^−β (β = 0.240 for Walker's set). The tail of Behrend-type blocks decays only like exp(−c√log z). The latter is eventually denser, so cutting far enough out and switching gives, for every k and every k-AP-free Kempner set K, f(k) > H(K) strictly. Walker's Theorem 2.1 says f(k) is the supremum over Kempner sets; that supremum is not attained by any Kempner set. For k=3 this argument is exactly Wróblewski's 1984 construction (Szekeres cut at 2.15×10⁷, Behrend attached).

Comparing dimensions at a fixed scale makes it look as if this cannot work for k=4; the error is in that way of looking. The dimension of a Behrend-type block grows with p (0.897 at p = 400) and passes Walker's 0.7597. But the head for k=4 is better than the head for k=3 (Szekeres, β = 0.369), so the switching scale is pushed out from 10⁷ to 10³⁰. The head is so good that the machinery comes in late — which is why the gain appears only in the 8th digit.

How rigorous — the same level as k=3

That the set itself is 4-AP-free and that its reciprocal sum exceeds 4.439753474215620 are theorems in Lean 4 (Shiori1112.setA4_apfree_and_lower; the form that exceeds the record 4.439753369254541 is setA4_apfree_and_beats_walker; no sorry, no native_decide, standard axioms only). Lean This is stated separately on purpose. Two things remain outside Lean: the value of the reciprocal sum of Walker's set itself, and that the head equals the truncation of Walker's set.

The stage table (38 rows, all integers), the scripts, and the complete Lean verification environment (a tar.gz of the k=3 distribution with the 19 k=4 files on top) are in the certificates. The table's internal consistency, and the fact that it beats the record, can be checked with the standard library alone; the main theorem about the set itself, in Lean.

The limits of this section

• The gain is in the 8th digit. Moving anything above the 7th digit needs a digit set S beyond Walker's search (b ≤ 88 unconditionally, b ≤ 200 with pruning). On the tail side only the 9th and 10th digits are left
• No optimality is claimed for the stage-selection policy (Bellman). The estimates used to choose stages are floating point, but they do not bear on the correctness of the lower bound
• The Lean lower bound for the head could not reach the required precision with truncated leaves (the k=3 method): tens of millions of leaves, an estimated 30 hours. Instead the four-term expansion 1/(1+u) ≥ 1−u+u²−u³ was proved via a recurrence for the moments and used in the leaves: depth 1, 13,545 leaves, loss 9.9×10⁻¹¹. It went through because the method was changed, not because the problem was light

Where the open items that have moved now stand is collected in What remains. Only what is open at present is listed here.

Open at present

Sources and reproduction

Apart from §07, there is no new mathematics in this article. The theorems used, and the framework of Wróblewski's construction, are published. There are only two places where we can write "this may not be written down anywhere", and both carry a proviso.

This problem came up in the random draw.

Six searches of differing mechanism returning the same value is strong evidence that the point really is the maximum. But that confidence holds only inside the conditions imposed. Outside those conditions sits a record from 42 years ago.