Erdős Problem #741

The problem

Let $A\subseteq \mathbb{N}$ be such that $A+A$ has positive (upper) density. Can one always decompose $A=A_1\sqcup A_2$ such that $A_1+A_1$ and $A_2+A_2$ both have positive (upper) density?

Is there a basis $A$ of order $2$ such that if $A=A_1\sqcup A_2$ then $A_1+A_1$ and $A_2+A_2$ cannot both have bounded gaps?

Statement quoted from erdosproblems.com/741, maintained by Thomas Bloom. Original source: [Er94b,p.263]. Current status there: solved (Lean).

AI contributions

As recorded in Terence Tao's wiki AI contributions to Erdős problems (data as of 30 Jun 2026). 🟢 full, 🟡 partial, ⚪ unverified, 🔴 incorrect.

Date	Kind	AI systems	Outcome
31 Mar, 2026	AI on its own	DeepMind prover agent	🟡 Partial result (Lean) (solution to variant of first part; solution to second part)
31 Mar, 2026	AI on its own	OpenAI internal model	🟡 Partial result (solution to second part)
16 Apr, 2026	AI on its own	DeepMind prover agent	🟢 Full solution (Lean)

Caveats

The wiki's classifications are provisional and are not a benchmark. Many Erdős problems have never had a thorough literature review, so a result that looks new may later turn out to be known; some problems were also stated ambiguously or incorrectly. See the problem page for the full discussion.

∎