Problem Statement
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$?
Categories:
Number Theory Additive Combinatorics
Progress
Ruzsa has observed that there is a simple counterexample: take $A$ to be the set of numbers whose binary representation has only non-zero digits in even places, and $B$ similarly but with non-zero digits only in odd places. It is easy to see $A$ and $B$ both grow like $\gg N^{1/2}$ and yet for any $n\geq 1$ there is exactly one solution to $n=a+b$ with $a\in A$ and $b\in B$.Ruzsa suggests that a non-trivial variant of this problem arises if one imposes the stronger condition that\[\lvert A\cap \{1,\ldots,N\}\rvert \sim c_AN^{1/2}\]for some constant $c_A>0$ as $N\to \infty$, and similarly for $B$.
Source: erdosproblems.com/331 | Last verified: January 14, 2026