Erdős Problem #340

Erdős Problem 340: growth of the greedy Sidon sequence

Statement and scope

Starting with $a_1=1$, repeatedly choose the least larger integer preserving distinct unordered pair sums, including repeated summands. For the resulting greedy Sidon set $A$, is $|A\cap[1,N]|\gg_\epsilon N^{1/2-\epsilon}$ for every $\epsilon>0$? What can be said about $A-A$?

We prove the classical cubic greedy bound and the sharp leading constant in the general Sidon upper bound. The requested near-square-root growth and general difference-set questions are unresolved here. This repairs the earlier GPT-5.2 attempt's unnecessary summation of local gap bounds, which only gave exponent $1/4$. Source: https://www.erdosproblems.com/340. No novelty is claimed.

Count all rejected values at once

Put $B=A\cap[1,N]$ and $k=|B|$. If $x\in[1,N]\setminus B$, it was rejected when all previously selected elements were smaller than $x$. Adding $x$ cannot cause a collision involving $2x$ and an old sum, because every old summand is smaller than $x$. The sums $x+a$ are mutually distinct, and none equals $2x$. Thus rejection means \[ x+a=b+c \] for some old $a,b,c$, allowing $b=c$. These elements all belong to $B$, so $x\in B+B-B$. Every chosen $x\in B$ also lies there, since $x=x+1-1$. Consequently \[ [1,N]\subset B+B-B,\qquad N\le k\,|B+B|=\frac{k^2(k+1)}2. \tag{1} \] In particular \[ |A\cap[1,N]|\ge(2N)^{1/3}-1. \tag{2} \] The same argument at $N=a_{k+1}-1$ gives $a_{k+1}\le k^2(k+1)/2+1$ directly, without accumulating a new cubic error at every step.

The sequence is infinite: a candidate larger than twice the current maximum has all its new sums above the old sumset, so some admissible next value always exists.

The matching general upper exponent

For any Sidon subset $b_1<\cdots<b_k\le N$, all positive differences are distinct. For $1\le u<k$, the $D=uk-u(u+1)/2$ differences $b_{i+h}-b_i$ with $h\le u$ have total at least $D(D+1)/2$. Telescoping for each $h$ bounds their total by $N u(u+1)/2$. Hence \[ k\le \sqrt{N(1+1/u)}+\frac{u+1}2. \] Taking $u=\lceil N^{1/4}\rceil$ when $k>u$, and treating $k\le u$ directly, yields \[ |A\cap[1,N]|\le\sqrt N+N^{1/4}+O(1). \tag{3} \]

A checked finite difference

Exact generation gives the first fifteen terms \[ 1,2,4,8,13,21,31,45,66,81,97,123,148,182,204. \] Thus $22=204-182$ belongs to $A-A$. This is a finite verified fact. Absence of a difference from any computed prefix would not establish its absence from the infinite sequence, so no such inference is used.

Remaining gap

Bounds $2$--$3$ leave an exponent gap from $1/3$ to $1/2$. Formula $1$ only counts possible forbidden triples and does not show that their values overlap enough to obtain the conjectured denser sequence. The proof also gives no positive-density or completeness theorem for $A-A$.

COMPLETION ESTIMATE

COMPLETION: 40%

Erdős problem #340

1) FORMAL RESTATEMENT.

Define the greedy Sidon sequence $A=\{a_1<a_2<\cdots\}$ by $a_1=1$ and, having chosen $a_1,\dots,a_n$, let $a_{n+1}$ be the smallest integer $>a_n$ such that $\{a_1,\dots,a_n,a_{n+1}\}$ remains a Sidon set, i.e. \[ a_i+a_j=a_k+a_\ell\ (1\le i\le j,\ 1\le k\le \ell)\ \Rightarrow\ \{i,j\}=\{k,\ell\}. \] Let $D:=A-A=\{a-b: a,b\in A\}\subseteq\mathbb{Z}$.

The problem asks:

• Determine the order of magnitude of $|A\cap[1,N]|$ (known bounds $N^{1/3}\le |A\cap[1,N]|\le N^{1/2}$ are stated in the problem).
• Does $D$ contain all integers? It is stated that $22\in D$, and it is not known whether $33\in D$.

2) QUICK LITERATURE/CONTEXT CHECK. We use only the facts explicitly stated above. In particular, we do not assume any deeper theorems about Sidon sets.

3) ATTACK PLAN.

• Prove standard counting bounds for Sidon subsets of $[1,N]$ (upper bound).
• Prove a simple growth bound for the greedy construction (a weak lower bound on $|A\cap[1,N]|$).
• Compute initial terms and difference-set data as a reality check.

4) WORK.

Lemma 340.1 (Sidon implies distinct differences). Let $S=\{s_1<\dots<s_k\}$ be a Sidon set. Then all differences $s_i-s_j$ with $i\ne j$ are distinct.

Proof. Suppose $s_i-s_j=s_{i'}-s_{j'}$ with $i\ne j$ and $i'\ne j'$. Rearranging gives \[ s_i+s_{j'} = s_{i'}+s_j. \] By the Sidon property, the unordered pairs must coincide: $\{i,j'\}=\{i',j\}$. If $i=i'$ then $j=j'$, and if $i=j$ then $s_i=s_j$ contradicting $i\ne j$. Thus the only way is the trivial equality with the same ordered pair, so distinctness holds. $\square$

Proposition 340.2 (a classical counting upper bound). If $S\subseteq\{1,2,\dots,N\}$ is Sidon with $|S|=k$, then \[ k(k-1)\le 2(N-1)\qquad\text{and hence}\qquad k\le \sqrt{2N}+1. \]

Proof. By Lemma 340.1, the $k(k-1)$ nonzero differences $s_i-s_j$ ($i\ne j$) are all distinct integers lying in $\{-(N-1),\dots,-1,1,\dots,N-1\}$, a set of size $2(N-1)$. Therefore $k(k-1)\le 2(N-1)$, implying $k\le \sqrt{2N}+1$. $\square$

Proposition 340.3 (a weak growth bound for the greedy Sidon sequence). Let $A=\{a_n\}$ be the greedy Sidon sequence. Then \[ a_{n+1} \le a_n + n^3+n^2+1\qquad\text{for all }n\ge 1. \] In particular $a_n\le 1+\sum_{j=1}^{n-1}(j^3+j^2+1)=O(n^4)$, so \[ |A\cap[1,N]|\ge c\,N^{1/4}\quad\text{for some constant }c>0\text{ and all large }N. \]

Proof. Fix $n$ and let $S_n:=\{a_i+a_j:1\le i\le j\le n\}$ be the set of existing sums; $|S_n|=n(n+1)/2$ and $S_n\subseteq[2,2a_n]$. A candidate integer $x>a_n$ fails to extend the Sidon property only if at least one of the following holds:

• (i) $2x\in S_n$ (collision of $x+x$ with an old sum), or
• (ii) $x+a_i\in S_n$ for some $1\le i\le n$ (collision of a new sum with an old sum).

Condition (i) forbids at most $|S_n|$ values of $x$ (namely $x=s/2$ for $s\in S_n$ with $s$ even). For (ii), fixing $i$ and $s\in S_n$ gives a forbidden value $x=s-a_i$; thus (ii) forbids at most $n|S_n|$ values of $x$. Therefore the set of forbidden $x$ has size at most \[ |S_n| + n|S_n| \le (n+1)\cdot \frac{n(n+1)}{2} \le n^3+n^2. \] Hence among the $n^3+n^2+1$ integers $a_n+1,\dots,a_n+(n^3+n^2+1)$ there exists some $x$ that is not forbidden, so the greedy choice satisfies $a_{n+1}\le a_n+n^3+n^2+1$. Summing the recurrence gives $a_n=O(n^4)$, which implies $|A\cap[1,N]|=\Omega(N^{1/4})$ by inversion. $\square$

FAST REALITY CHECK (computed initial terms and differences). Using a direct implementation of the greedy definition, the first $20$ terms are \[ 1,2,4,8,13,21,31,45,66,81,97,123,148,182,204,252,290,361,401,475. \] For the difference set $D=A-A$, using the first $200$ terms:

• $22\in D$ (e.g. $204-182=22$), matching the statement.
• Among positive integers $\le 200$, the smallest missing difference is $33$ (i.e. $33\notin (A-A)\cap[1,200]$ for the first $200$ terms).

Also, the counts of $A\cap[1,N]$ for $N\in\{10,100,10^3,10^4,10^5\}$ were: \[ |A\cap[1,10]|=4,\ |A\cap[1,100]|=11,\ |A\cap[1,10^3]|=27,\ |A\cap[1,10^4]|=66,\ |A\cap[1,10^5]|=161. \]

5) VERIFICATION. Proposition 340.2 is a complete argument using only Lemma 340.1 and a pigeonhole count of differences. Proposition 340.3 is a direct forbidden-value count for the greedy extension criterion. The computation is an exact brute-force generation of the greedy sequence for the stated prefix lengths.

6) FINAL.

UNRESOLVED

(i) Strongest fully proved partial result obtained here. We proved a standard Sidon upper bound $|S\cap[1,N]|\le \sqrt{2N}+1$ for any Sidon set (Proposition 340.2) and a weak lower bound for the greedy Sidon sequence $|A\cap[1,N]|=\Omega(N^{1/4})$ (Proposition 340.3). Computationally, $22\in D$ and $33$ does not occur as a difference among the first $200$ terms.

(ii) Exact first gap. The main gap is proving the true order of growth of the greedy Sidon sequence: bridging from the weak $\Omega(N^{1/4})$ bound here to the conjectural/asked ranges (closer to $N^{1/3}$ or $N^{1/2}$), and deciding whether every integer lies in $D$.

(iii) Top 3 next moves (concrete targets).

1. Improve Proposition 340.3 by sharpening the forbidden-value count to $O(n^2)$, which would yield $a_n=O(n^3)$ and hence $|A\cap[1,N]|=\Omega(N^{1/3})$.
2. Prove a structural lemma about the distribution of the new sums $a_{n+1}+a_i$ relative to old sums, to control typical gap sizes in the greedy process.
3. For the difference-set question, compute $D$ to much larger depth and identify the smallest missing difference empirically; then attempt to prove that any missing difference must have a specific residue-class or carry structure.

(iv) Minimal counterexample structure. If $D\ne\mathbb{Z}$, a minimal counterexample would be the smallest positive integer $m$ not in $A-A$. Such an $m$ would force that no two elements of $A$ differ by $m$, imposing a strong spacing constraint on $A$ that should reflect back into the greedy construction in a detectable way (e.g. forbidding a whole translate $A+m$).