Erdős Problem #966

Precise statement

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.

The source statement is reproduced for indexing with attribution. Mathematical correctness requires domain-expert or mechanical review. VibeMath has not independently audited statement fidelity, correctness, priority, or novelty.

What AI did

Aristotle

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

Provider: Harmonic · Prompt public: unknown · Independence: unknown

Verification boundary

lean verified statement audited

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

Correctness: supported · statement fidelity: audited · peer review: none

Timeline

1. 2026-02-25

   erdosproblems.com/966

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

Known method families

construction (source-reported)

Source-reported tools: construction.

Independent: unknown · difference confidence: 0

What remains uncertain

VibeMath has not independently audited the mathematical statement, proof, or novelty claim.

• VibeMath has not independently verified the mathematical claim.
• AI-attempt independence and training-data exposure are unknown unless explicitly documented.
• VibeMath has not independently audited the mathematical statement, proof, or novelty claim.