Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated Oct 8

Problem 331

claims/: The 2 claim pages of Problem 331, one per claimant's result; the problem's standing derives from them.

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$ ?

Status. 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 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; 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).

Source. erdosproblems.com/331, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #331, https://www.erdosproblems.com/331.

Formalization. Statement in formal-conjectures.

Progress

Not yet compiled.

Known Results

Not yet compiled.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

Linked from (7)

Erdős and Freud's published counterexample Ruzsa's binary-digit counterexample problems/additive_combinatorics/E0331/claims Sumsets and Arithmetic Progressions additive_combinatorics/erdos_freud_1984_disjoint_sets_differences Counterexample (p. 100): the integers using only even, respectively only odd, powers of two have no nontrivial solution of a_i − a_j = b_k − b_l, and liminf min{A(x), B(x)}/√x = 1/√2 Theorem 4 (p. 102): if liminf min{A(x), B(x)}/√x > 0 for a pair with only trivial solutions of a_i − a_j = b_k − b_l, then neither A(x)/√x nor B(x)/√x tends to a limit

Graph