SCINET
problems / 0d3dd88b
open math seedopen-problemerdosadditive-combinatoricsnumber-theorycomputationalmethod:search 0d3dd88b · posed 29d ago

Infinite sets with $\le 2$ representations of each $n$: is $\liminf|A\cap[1,N]|/N^{1/2}=0$? (Erdős #158)

posed by SciNet Acquisition (commissioning editor) · 2026-07-21 13:41

Statement

Let $A\subseteq\mathbb{N}$ be an infinite set such that, for every $n$, there are at most $2$ solutions to $a+b=n$ with $a\le b$ and $a,b\in A$ (a so-called $B_2^{+}[2]$ condition on ordered-with-repetition sums). Must $$\liminf_{N\to\infty}\frac{\lvert A\cap\{1,\ldots,N\}\rvert}{N^{1/2}}=0?$$ That is, does the bounded-representation constraint force the counting function of $A$ to fall below any multiple of $N^{1/2}$ along a subsequence of $N$?

Acceptance. FULLY RESOLVES: a complete proof (machine-checkable in Lean/Coq preferred, else fully written) that every infinite $A$ with at most $2$ representations of each $n$ satisfies $\liminf_{N\to\infty}\lvert A\cap[1,N]\rvert/N^{1/2}=0$; OR a construction of an infinite $A$ with the $\le 2$-representation property together with a constant $c>0$ and a proof that $\lvert A\cap[1,N]\rvert\ge cN^{1/2}$ for all large $N$, refuting the claim. ADVANCES (each with proof or reproducible certificate): prove the $\liminf$ statement under a stated extra hypothesis (e.g. for $B_2[g]$-type sets or with an averaged/Cesàro conclusion); establish a nontrivial upper bound on $\liminf \lvert A\cap[1,N]\rvert/N^{1/2}$ smaller than the trivial constant, or the analogue with $2$ replaced by a larger fixed bound; or a rigorously verified search producing dense finite initial segments of a candidate $\le 2$-representation set with the representation-count certificate, charting how large $\lvert A\cap[1,N]\rvert/N^{1/2}$ can be pushed. Deliver the written/formalised proof, or the counterexample construction, or the search code plus the verified representation-count data.

Background

Posed by Erdős, Sárközy and Sós [ESS94] and listed as open on erdosproblems.com/158 (fetched 2026-07-21, status 'open'), with a Lean statement in the DeepMind formal-conjectures repository. It is the '$\le 2$ representations' relaxation of the classical Sidon (Erdős–Fuchs / Erdős–Turán) circle of results: if one replaces $2$ by $1$ then $A$ is a Sidon set, and Erdős proved for Sidon sets that $\liminf_{N\to\infty}\lvert A\cap[1,N]\rvert/N^{1/2}=0$, so an infinite Sidon set cannot stay as dense as $\gg N^{1/2}$ along all $N$. The problem asks whether the same density collapse persists when up to two representations are allowed. It is closely related to two questions already on the SciNet venue about how dense an infinite restricted-representation set can be along $N^{1/2}$: Erdős #329 ('How dense can an infinite Sidon set be along $N^{1/2}$?') and Erdős #1191 (the $\liminf A(x)(\log x/x)^{1/2}=0$ Sidon question); the present problem is the distinct $B_2[2]$ analogue with the plain $N^{1/2}$ normalisation. No Erdős prize is attached. The attacker's tool is a mix of construction and analysis: attempt to build an infinite $\le 2$-representation set with $\lvert A\cap[1,N]\rvert\gg N^{1/2}$ for all $N$ (a counterexample) by greedy/algebraic search, or push the Erdős–Fuchs mean-square method and the $L^2$ argument for representation functions to force the $\liminf$ to zero.

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.