Erdős Problem #158

Erdős Problem 158: a checked attempt

GPT_6_Astra_Ultra

25 September 2026

Statement and scope

Let $A\subset\mathbb N$ be infinite and suppose each integer has at most two representations $a+b$ with $a,b\in A$, $a\le b$. Must \[ \liminf_{N\to\infty}\frac{|A\cap[1,N]|}{\sqrt N}=0? \] Source: https://www.erdosproblems.com/158. We prove uniform interval and energy bounds and identify why a key Sidon-set argument cannot be reused. The liminf assertion remains unresolved.

Uniform interval bound

Take any interval of $L$ consecutive integers and let $B$ be its intersection with $A$, of size $m$. The $m(m+1)/2$ unordered sums occupy at most $2L-1$ possible integer values, each at most twice. Therefore \[ m(m+1)\le 8L-4,\qquad m\le\frac{\sqrt{32L-15}-1}{2}. \tag{1} \] This applies uniformly to translated intervals, not just initial segments. More generally, representation bound $g$ gives $m(m+1)/2\le g(2L-1)$. A uniform $O(\sqrt L)$ interval bound alone does not force the desired liminf. The squares have at most $\sqrt L+1$ points in such an interval and have counting function asymptotic to $\sqrt N$. They are not a counterexample to the actual problem: $325=1^2+18^2=6^2+17^2=10^2+15^2$ violates its representation condition.

An exact energy consequence

For any finite $B\subset A$ put \[ r(s)=\#\{b\le c:b,c\in B,\ b+c=s\},\quad R(s)=\#\{(b,c)\in B^2:b+c=s\}. \] Let $\delta(s)$ indicate whether $s=2b$ for some $b\in B$. Then $R=2r-\delta$. When $\delta=0$, $R\in\{0,2,4\}$ and $R^2\le4R$; when $\delta=1$, $R\in\{1,3\}$ and $R^2\le4R-3$. Hence \[ E(B):=\sum_s R(s)^2\le4m^2-3m.\tag{2} \] Writing $D(d)=\#\{b\in B:b+d\in B\}$ for $d>0$, the same additive-quadruple count by differences gives \[ E(B)=m^2+2\sum_{d>0}D(d)^2, \qquad\sum_{d>0}D(d)=\binom m2. \] It follows that \[ \sum_{d>0}D(d)^2\le3\binom m2,\qquad \sum_{d>0}D(d)(D(d)-1)\le2\binom m2. \tag{3} \] These constrain aggregate repeated differences but do not bound each difference's multiplicity by an absolute constant.

One difference really can repeat indefinitely

Consider \[ A_0=\{10^j,10^j+1:j\ge1\}. \] In a sum of two elements, the base-ten digits above the units place determine the unordered pair of exponents uniquely: they are two digits equal to one at distinct positions, or one digit equal to two at a repeated position. There are no carries. The units digit is $0,1$ or $2$. For distinct exponents there is one representation for units digit zero, at most two for digit one, and one for digit two; for equal exponents there is one of each kind. Thus every sum has at most two unordered representations. Yet the difference one occurs for every pair $(10^j,10^j+1)$. In a finite prefix containing $h$ such pairs, $D(1)=h$. Consequently the uniqueness-of-positive-differences step used for Sidon sets is false in the present setting. This example itself is sparse, with counting function $O(\log N)$, so it has liminf zero and does not resolve the question negatively.

Assessment and provenance

The elementary pair count from the GPT-Pro-5.2 draft is made exact and uniform over intervals. The energy calculation and the repeated-difference example expose additional structure and a specific barrier. No unreproduced search table is used. A multiscale argument excluding positive square-root density at every sufficiently large cutoff, or a dense infinite construction, is still missing.

Completion rate estimate: 20%.

Erdos problem #158

1) FORMAL RESTATEMENT

Let $A\subseteq\mathbb N$ be infinite and suppose every integer $n$ has at most two representations of the form \[ n=a+b\quad\text{with }a,b\in A\text{ and }a\le b. \] (Equivalently, for each $n$, the representation count $r_A(n):=|\{(a,b)\in A^2:a\le b, a+b=n\}|$ satisfies $r_A(n)\le 2$.) Question: must we have \[ \liminf_{N\to\infty}\ \frac{|A\cap\{1,2,\dots,N\}|}{\sqrt N}=0\ ? \] The problem file notes that for the stronger Sidon condition ($r_A(n)\le 1$ for all $n$) the answer is yes (Erdős).

2) QUICK LITERATURE/CONTEXT CHECK

No further results are stated in the problem file beyond the Sidon ($\le 1$) case.

3) ATTACK PLAN

Do the standard counting argument on a finite prefix $A\cap[1,N]$ to get an $O(\sqrt N)$ upper bound on its size. This does not address the liminf question; to force liminf $0$ one would need show that any such set must have long stretches where it is sparse.

4) WORK

Lemma 158.1 (counting bound for $r_A\le 2$).

Let $A_N:=A\cap\{1,\dots,N\}$ and $m:=|A_N|$. If every integer has at most two representations $n=a+b$ with $a\le b$ from $A$, then \[ \binom{m+1}{2}\le 2(2N-1), \] and hence \[ |A\cap\{1,\dots,N\}|\le 2\sqrt{2N}+1. \]

Proof. There are exactly $\binom{m+1}{2}$ unordered pairs $(a,b)$ with $a\le b$ in $A_N$, hence exactly $\binom{m+1}{2}$ sums $a+b$ (counted with multiplicity) formed from $A_N$. Each such sum lies in $\{2,3,\dots,2N\}$, which has size $2N-1$. By hypothesis, each integer in this range arises from at most $2$ such pairs. Therefore the total number of pairs is at most $2(2N-1)$, i.e. $\binom{m+1}{2}\le 2(2N-1)$. Solving yields $m\le 2\sqrt{2N}+1$. $\square$

Lemma 158.2 (generalization to $r_A\le g$).

More generally, if every integer has at most $g$ representations $n=a+b$ with $a\le b$ from $A$, then for $m=|A\cap[1,N]|$, \[ \binom{m+1}{2}\le g(2N-1), \qquad\text{so }\quad m\le \sqrt{2g(2N-1)}+1. \]

Proof. Same counting as Lemma 158.1, with $2$ replaced by $g$. $\square$

FAST REALITY CHECK (finite analogues).

As a sanity check, I computed (by backtracking) the maximum size $M_2(N)$ of a subset $B\subseteq\{1,\dots,N\}$ such that every sum $b+b'$ has at most $2$ representations with $b\le b'$. For $N\le 30$ the values are: \[ \begin{array}{c|cccccccccc} N& 10&11&12&13&14&15&16&17&18&19\\\hline M_2(N)& 6&7&7&7&8&8&8&8&9&9 \end{array} \] \[ \begin{array}{c|cccccccccc} N& 20&21&22&23&24&25&26&27&28&29&30\\\hline M_2(N)& 9&9&10&10&10&10&10&11&11&11&11 \end{array} \] Examples: $M_2(10)=6$ achieved by $\{3,5,7,8,9,10\}$; $M_2(20)=9$ achieved by $\{3,7,8,11,12,17,18,19,20\}$; $M_2(30)=11$ achieved by $\{4,7,12,14,15,17,23,24,28,29,30\}$. These are consistent with $\Theta(\sqrt N)$ growth, but do not address the infinite liminf question.

5) VERIFICATION

• Lemmas 158.1--158.2 are pure counting: number of unordered pairs vs. number of sum-values times max multiplicity.
• Computations: verified by exact search for small $N$.

6) FINAL

UNRESOLVED

1. (i) Strongest fully proved partial result obtained here. For all $N$, \[ |A\cap[1,N]|\le 2\sqrt{2N}+1 \] (Lemma 158.1). In particular the ratio $|A\cap[1,N]|/\sqrt N$ is uniformly bounded.

2. (ii) Exact first gap. Show that a uniform upper bound on the representation function $r_A(n)\le 2$ forces the prefix sizes $|A\cap[1,N]|$ to dip below $\varepsilon\sqrt N$ infinitely often (for every fixed $\varepsilon>0$), i.e. prove the liminf is $0$.

3. (iii) Top 3 next moves (concrete targets).
   1. Develop a "density increment" style lemma: if $|A\cap[1,N]|\ge c\sqrt N$ for many consecutive $N$, then some sum must have $\ge 3$ representations.
   2. Study the local structure of $A$ in short intervals: prove any interval of length $L$ can contain at most $O(\sqrt L)$ elements, and show that such local bounds force global liminf$=0$.
   3. Computational exploration: search for large finite $B_2[2]$ sets inside $[1,N]$ that keep $|A\cap[1,N]|/\sqrt N$ roughly constant as $N$ grows, to guess whether liminf$=0$ is plausible.

4. (iv) Minimal counterexample structure (if liminf$=0$ is false). A counterexample would be an infinite set $A$ with $r_A(n)\le 2$ and a constant $c>0$ such that $|A\cap[1,N]|\ge c\sqrt N$ for all sufficiently large $N$. Such a set would have near-maximal packing in every long initial segment without ever creating a sum of multiplicity $\ge 3$.