gpt pro 5.2 attempt on Math-698

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