Problem 331

Let $A,B\subseteq \mathbb{N}$ such that for all large $N$

\lvert A\cap \{1,\ldots,N\}\rvert \gg N^{1/2}

and

\lvert B\cap \{1,\ldots,N\}\rvert \gg N^{1/2}.

Is it true that there are infinitely many solutions to $a_1-a_2=b_1-b_2\neq 0$ with $a_1,a_2\in A$ and $b_1,b_2\in B$ ?

Source: erdosproblems.com/331

Number theory
Additive combinatorics

Wiki page

Status

SolvedDisproved

An accepted solution exists. The statement is false.

DISPROVED (LEAN), the site's label: the answer is no, by the binary-digit counterexample that the site credits to Ruzsa, recorded on its claim page (Ruzsa, 2024) with the site's acceptance as its evidence, and that Erdős and Freud had published in 1984 (J. Number Theory 18, 99--109, refereed) without crediting Ruzsa, recorded on its own claim page (Erdős and Freud, 1984); the label's Lean mark refers to van Doorn's Lean formalization of the counterexample, posted in the site's discussion thread in January 2026 and linked by the catalog, listed on the Ruzsa page as a formalization link (third-party Lean, so no formalized evidence).

Problem 331

Status

Proof claims

Discussion