Erdős Problem #870

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

Let $k\geq 3$ and $A$ be an additive basis of order $k$ . Does there exist a constant $c=c(k)>0$ such that if $r(n)\geq c\log n$ for all large $n$ (where $r(n)$ counts representations of $n$ as a sum of at most $k$ elements of $A$ ) then $A$ must contain a minimal basis of order $k$ ? The claimed answer is no, for every $k\geq 3$ .

Result: Disproved(see note)
Status: Candidate (review pending)
AI contribution: AI-discovered
Method: Construction
Field: Number Theory, Additive Bases
Posed by: Paul Erdős, Melvyn Nathanson
Year posed: 1979
Years open: 47y
Solved: 2026-05-02
Model: GPT-5.4 Pro, GPT-5.5 Pro
Vendor: OpenAI
Collaborators: David Turturean
Verification: Unreviewed
Publication: Announced
Significance: 10 / 100
Disclosed cost: —
Wikipedia: No dedicated article

What was actually shown

A total refutation is claimed for all k>=3, building on the Larsen-Larsen resolution of problem #868; erdosproblems.com still lists the problem open

What the AI did

The proof was developed via an automated multi-turn scaffold that iteratively queried GPT-5.4 Pro and GPT-5.5 Pro over roughly forty turns, with constructions inspired by the Larsen-Larsen order-2 basis; the author later reworked the k=3 case after community concerns and verified the write-up himself and with GPT-5.5 Pro.

Verification

Verification so far is by the author and by GPT-5.5 model runs he links; a Lean formalization attempt is blocked because the underlying Larsen-Larsen probabilistic construction resists autoformalization. No independent human review.

Sources

erdosproblems.com/870

Write-up

Erdős Problem #870

What was actually shown

What the AI did

Verification

Sources

Discussion