Erdős Problem #966

Erdős problem #966 · erdosproblems.com/966

Let $k,r\geq 2$ . Does there exist a set $A\subseteq \mathbb{N}$ that contains no non-trivial arithmetic progression of length $k+1$ , yet in any $r$ -colouring of $A$ there must exist a monochromatic non-trivial arithmetic progression of length $k$ ? Answered in the affirmative.

Result: Proved(see note)
Status: Resolved
AI contribution: AI-discovered
Method: Construction
Field: Additive Combinatorics, Ramsey Theory
Posed by: Paul Erdős
Year posed: 1975
Years open: 51y
Solved: 2026-02-25
Model: Aristotle
Vendor: Harmonic
Collaborators: —
Verification: Lean-verified
Publication: Announced
Significance: 10 / 100
Disclosed cost: —
Wikipedia: No dedicated article

What was actually shown

Erdős reported in 1975 that Spencer had shown existence but gave no reference; no proof was on record before the AI solution

What the AI did

Aristotle produced the construction and its proof and formalized the result; erdosproblems.com marks the problem PROVED with the proof verified in Lean.

Verification

erdosproblems.com marks the problem PROVED (LEAN): solved in the affirmative with the proof verified in Lean.

Source

Problem recorderdosproblems.com/966

Erdős Problem #966

What was actually shown

What the AI did

Verification

Source

Discussion