Erdős Problem #42

The problem

Let $M\geq 1$ and $N$ be sufficiently large in terms of $M$ . Is it true that for every Sidon set $A\subset \{1,\ldots,N\}$ there is another Sidon set $B\subset \{1,\ldots,N\}$ of size $M$ such that $(A-A)\cap(B-B)=\{0\}$ ?

Statement quoted from erdosproblems.com/42, maintained by Thomas Bloom. Original source: [Er95,p.5]. 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	Humans	Outcome
19 Jan, 2026	AI on its own	Codex, GPT-5.2, GPT-5.2 Pro	—	🟡 Partial result (Lean)
27 Apr, 2026	AI working with humans	GPT-5.5 Pro	Harjas Sandhu	🟢 Full solution

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.

∎