Erdős 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\)? 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\). This was formalized in Lean by van Doorn using Aristotle.