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

Updated Oct 8

Problem 158

claims/: The 1 claim page of Problem 158, one per claimant's result; the problem's standing derives from them.

Statement. Let $A\subset \mathbb{N}$ be an infinite set such that, for any $n$ , there are most $2$ solutions to $a+b=n$ with $a\leq b$ . Must

\liminf_{N\to\infty}\frac{\lvert A\cap \{1,\ldots,N\}\rvert}{N^{1/2}}=0?

Status. Open, in the site's label. The accepted partial claim Erdős's theorem for Sidon sets answers the question yes for sets with at most one representation of each integer, as the site's remark records; no claim covers sets in which some integer has two. No proof claim on the site, no release item and no other claimed resolution names the problem.

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

Formalization. Statement in formal-conjectures.

Current assessment

The site's formulation reads "there are most [sic] $2$ solutions", omitting "at"; the question concerns the intended "at most" reading. It asks about one fixed infinite set with at most two unordered representations of each integer, counting a diagonal once. A counterexample needs $A(N)\ge c\sqrt N$ for some $c>0$ and every sufficiently large $N$ , not just along a subsequence. The site labels the problem open (2026-09-10), in agreement with the fixed- $g$ liminf conjecture stated in Pliego's manuscript, arXiv:2405.04154v1 (7 May 2024), p. 2, equation (1.4). Erdős's theorem that every infinite Sidon set has $\liminf A(N)/N^{1/2}=0$ , the case of one representation, is the accepted partial claim named under Status; the sources below give further partial and adjacent results, not a resolution.

No proof or disproof of the exact question had been published or announced. The 2026 greedy-computation announcement is Zeraoulia's note, and the recent papers of O'Bryant and Táfula have the different hypotheses described under Known Results. Robin Riblet's author page lists Existence of infinite $B_h[g]$ -sets with large density as forthcoming, with no manuscript, theorem statement or venue, so its scope is unknown.

Progress

The Current assessment above records the known progress.

Known Results

For infinite lower growth, a public benchmark is Cilleruelo's infinite Sidon construction: $A(x)=x^{\sqrt2-1+o(1)}$ (Theorem 1.2, p. 2 of arXiv:1209.0326v2, 15 May 2013; published in Advances in Mathematics 255 (2014)). Its convention includes the diagonal (p. 1), so this same set is also $B_2[2]$ . Pliego's Theorem 1.1 and Corollary 1.2 (arXiv:2405.04154v1, pp. 2–3) give $A(x)\gg x^{g/(2g+1)}$ for each fixed $g\ge2$ , together with a three-summand representation property. At $g=2$ this is $x^{2/5}$ , improving the logarithmic factor in that general- $g$ construction line but not the Sidon-subclass exponent. Pliego's result is a preprint theorem; it had no publication or independent-acceptance record. Neither a lower bound with exponent below $1/2$ nor letting $g$ grow establishes positive square-root lower density for fixed multiplicity two.

For the limit superior, Cilleruelo and Trujillo construct an infinite $B_2[2]$ sequence with $\limsup_{x\to\infty}A(x)/\sqrt x=\sqrt{3/2}$ (Theorem 1, p. 2 of the four-page manuscript; published in Israel Journal of Mathematics 126 (2001)). Their introduction explicitly separates this from the unknown liminf question. For finite sets, Cilleruelo's historical bound is $F(N,2)\le\sqrt{6N}+1$ , where $F(N,2)$ maximizes the size of a $B_2[2]$ subset of $[1,N]$ (Theorem 1, p. 1 of the three-page manuscript; published in 2000). This historical finite estimate was superseded by Yu (Theorems 1.1–1.2, p. 2 of the 2008 paper) and Habsieger and Plagne (Theorem 1, pp. 1–2 of arXiv:1609.02771v3, 9 November 2016). These are historical examples, not an exhaustive account or a claim to the latest finite bound. Further work includes White (2024), whose quantitative bounds this page does not summarize. The finite estimates quoted here and the limsup construction neither force nor refute a positive liminf for one infinite set.

Recent density obstructions use different hypotheses. O'Bryant's Theorem 1 (arXiv:2606.28651v3, 26 July 2026, pp. 1–2) concerns a bounded number of representations of each positive difference, a condition not supplied by the $B_2[2]$ sum bound. Táfula's Theorems 1.1–1.2 (arXiv:2607.20753v1, 22 July 2026, pp. 1–2) concern ordered tuples of pairwise distinct elements and zero-sum linear forms; the general-form result also assumes gap bounds. The published article, accepted 17 July and published 29 July 2026, retains these distinctions. These theorems do not settle the ordinary sum-multiplicity question here.

Finally, Zeraoulia's note (1 February 2026, pp. 1–3, especially Table 1) reports the first 2,000 terms of the greedy $B_2[2]$ sequence, ending at $7{,}445{,}662$ . It presents a possible counterexample candidate and finite data, not a proof that its normalized counting function stays bounded away from zero. No independent reproduction of the computation is recorded.

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 (116)

Graph