For every k,r∈ N with k≥2 and r≥2, does there exist a set A⊆ N containing no non-trivial arithmetic progression of length k+1, such that every colouring of A with r colours contains a monochromatic non-trivial arithmetic progression of length k?

Erdős Problem #966 — Arithmetic-progression-free sets forcing monochromatic progressions

For $k,r\geq 2$ , the problem asks whether there is a set $A\subseteq\mathbb{N}$ with no nontrivial progression of length $k+1$ , while every $r$ -colouring of $A$ contains a monochromatic progression of length $k$ . Erdős reported in 1975 that Spencer had shown such a sequence exists, but no proof was supplied.

Known results

Spencer, as reported by Erdős in 1975, allegedly established existence; the reference and proof remain unavailable.

February 2026 claimed solution

A construction based on the Hales–Jewett theorem and a base- $q$ embedding was discussed on February 25, 2026, but the discussion did not verify it. Aristotle, developed by Harmonic, is credited with producing and formalizing a proof, with claimed Lean verification; the official record still lists zero proof claims.

Current status (as of February 2026): Existence was reported by Erdős in 1975, and an affirmative AI-generated construction was claimed in 2026, but no independently verified proof is recorded.

Erdős Problem #966 — Arithmetic-progression-free sets forcing monochromatic progressions

Primary source

Additional references

Progress summary

Solutions 0