Erdős Problem #329

Erdős Problem 329: the upper density of an infinite Sidon set

Statement and scope

This substantially strengthens the earlier GPT-5.2 write-up's $\sqrt2$ upper constant. The bounds and attribution to Erdős--Turán and Krückeberg are recorded at https://www.erdosproblems.com/329. The proof uses the classical Bose--Chowla construction, established below from the standard algebraic facts that finite fields of order $q^2$ exist and their multiplicative groups are cyclic. No novelty is claimed.

A sharp leading constant in the finite upper bound

Fix $1\le u<m$ and consider differences $a_{i+h}-a_i$ for $1\le h\le u$. Their number is $D=um-u(u+1)/2$. Being distinct positive integers, their sum is at least $D(D+1)/2$. On the other hand, telescoping for each $h$ gives \[ \sum_{i=1}^{m-h}(a_{i+h}-a_i) =\sum_{i=m-h+1}^m a_i-\sum_{i=1}^h a_i\le hN. \] Consequently $D^2\le Nu(u+1)$, and \[ m\le\sqrt{N(1+1/u)}+\frac{u+1}{2}. \tag{1} \] Take $u=\lceil N^{1/4}\rceil$ if $m>u$; otherwise the desired estimate is immediate. Since $\sqrt{1+t}\le1+t/2$, $1$ gives \[ m\le\sqrt N+N^{1/4}+O(1). \] Applying this to every initial segment proves the universal limsup upper bound $1$.

Finite Sidon sets of size $q$ in length $q^2-1$

If $b_1+b_2\equiv b_3+b_4\pmod Q$, then \[ (\theta+t_1)(\theta+t_2)=(\theta+t_3)(\theta+t_4). \] The elements $1,\theta$ are linearly independent over $\mathbb F_q$, so $t_1+t_2=t_3+t_4$ and $t_1t_2=t_3t_4$. The two unordered pairs are roots of the same monic quadratic, hence are equal. Thus $B$ is Sidon modulo $Q$. Taking its representatives in $[1,Q]$ gives an integer Sidon set of size $q$.

Extending a finite prefix by a dense distant block

Let $L=Q+M$ and put $F'=F\cup(L+B')$. This is Sidon. Sums of two old points are at most $2M$; mixed sums lie between $L+2$ and $L+Q+M=2L$; sums of two new points are at least $2L+2$. These three ranges are disjoint. Old and new sums are individually unique, and equality of two mixed sums would give an old positive difference equal to a new one, which was excluded.

Iterate this operation, choosing successive primes so large that, for the current $m,M$, $m^2/q\to0$ and $M/q^2\to0$ along the construction. Such choices are possible because primes are unbounded. The increasing union $A$ is infinite and Sidon: every proposed collision would already lie in a finite stage. At the endpoint $N=L+Q=2(q^2-1)+M$ of a stage, \[ |A\cap[1,N]|\ge q-\binom m2,\qquad \frac{|A\cap[1,N]|}{\sqrt N}\ge\frac1{\sqrt2}-o(1). \] Later blocks start beyond $N$, so the finite-prefix argument is consistent. This proves the lower limsup bound $1/\sqrt2$.

Remaining gap

COMPLETION ESTIMATE

1) FORMAL RESTATEMENT

A set $A\subseteq\mathbb N$ is a Sidon set (also called a $B_2[1]$ set) if every integer has at most one representation \[ n=a+b\quad\text{with }a,b\in A\text{ and }a\le b. \] Equivalently, all sums $a+b$ with $a\le b$ are distinct.

The problem asks how large \[ \limsup_{N\to\infty}\frac{|A\cap\{1,\dots,N\}|}{\sqrt{N}} \] can be, over all infinite Sidon sets $A\subseteq\mathbb N$.

2) QUICK LITERATURE/CONTEXT CHECK

I do not add external results. The statement says:

* Erdős constructed a Sidon set with limsup $\ge 1/2$. * Krückeberg constructed one with limsup $\ge 1/\sqrt{2}$. * Erdős--Turán proved the limsup is always $\le 1$.

3) ATTACK PLAN

I do not attempt the full limsup optimization. Instead I prove from scratch the classical easy upper bound for finite Sidon sets in $\{1,\dots,N\}$ using distinct differences. I also compute exact maxima for small $N$ to sanity-check scaling.

4) WORK

PHASE 1: FAST REALITY CHECK (exact maximum Sidon size for small $N$)

By exhaustive search, the maximum size of a Sidon subset of $\{1,\dots,N\}$ for several $N$ is: \[ \begin{array}{c|ccccc} N & 10 & 20 & 30 & 40 & 50\\\hline \max |A| & 4 & 6 & 7 & 8 & 9 \end{array} \] The ratios $(\max|A|)/\sqrt{N}$ for these $N$ are approximately $1.265,1.342,1.278,1.265,1.273$. (These are small-$N$ artifacts; the asymptotic limsup concerns infinite sets.)

Lemma 329.1 (Sidon $\Rightarrow$ distinct positive differences).

Let $A$ be a Sidon set, and let $a_1<a_2<\cdots<a_m$ be distinct elements of $A$. Then all positive differences $a_j-a_i$ with $1\le i<j\le m$ are distinct.

Proof. Suppose for contradiction that $a_j-a_i=a_{j'}-a_{i'}$ with $i<j$ and $i'<j'$ and the ordered pairs $(i,j)\neq(i',j')$. Rearranging gives \[ a_j+a_{i'}=a_{j'}+a_i. \] Because $i<j$ and $i'<j'$, we have $a_i<a_j$ and $a_{i'}<a_{j'}$. Thus $a_i\le a_{i'}$ or $a_{i'}\le a_i$; in either case, the equality above gives two (possibly reordered) representations of the same integer as a sum of two elements of $A$. More formally, consider the two unordered pairs $\{a_j,a_{i'}\}$ and $\{a_{j'},a_i\}$. If they are different, then we have a collision of sums among distinct pairs, contradicting the Sidon property. If they are the same, then $a_j=a_{j'}$ and $a_{i'}=a_i$, which forces $(i,j)=(i',j')$. So no two distinct pairs can yield the same difference. $\square$

Lemma 329.2 (finite Sidon upper bound in $\{1,\dots,N\}$).

Let $S\subseteq\{1,\dots,N\}$ be a Sidon set of size $m$. Then \[ \binom{m}{2} \le N-1, \] and consequently \[ m \le \frac{1+\sqrt{1+8(N-1)}}{2} \le \sqrt{2N}+1. \]

Proof. List $S=\{s_1<\cdots<s_m\}$. By Lemma 329.1, the $\binom{m}{2}$ positive differences $s_j-s_i$ (for $i<j$) are all distinct. Each difference is an integer between $1$ and $N-1$, since $1\le s_i<s_j\le N$. There are only $N-1$ possible values in $\{1,\dots,N-1\}$, so \[ \binom{m}{2}\le N-1. \] Solving the quadratic inequality $m(m-1)/2\le N-1$ gives \[ m\le \frac{1+\sqrt{1+8(N-1)}}{2}. \] Finally $\sqrt{1+8(N-1)}\le \sqrt{8N}$ for $N\ge 1$, giving $m\le \sqrt{2N}+1$. $\square$

5) VERIFICATION

-- Lemma 329.1: the implication "equal differences $\Rightarrow$ equal sums" is correct by rearrangement. The Sidon property applies to sums with $a\le b$; equality of unordered pairs covers this.

-- Lemma 329.2: the difference range is indeed within $[1,N-1]$.

-- Computation: brute-force search over subsets for $N\le 50$.

6) FINAL

UNRESOLVED

(i) Strongest fully proved partial result obtained here.

* A standard finite upper bound: any Sidon subset of $\{1,\dots,N\}$ has size at most $\sqrt{2N}+1$ (Lemma 329.2).

(ii) Exact first gap.

Determine the optimal possible value of $\limsup_{N\to\infty}|A\cap[1,N]|/\sqrt{N}$ over infinite Sidon sets $A$. The lemmas here only reprove an easy universal upper bound with constant $\sqrt{2}$ (on finite initial segments) and do not address the sharp constant in the limsup problem.

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

1. Produce an explicit infinite Sidon construction with a provable limsup constant (at least $1/2$ as stated, ideally approaching $1$). 2. Relate the limsup constant to embeddings of finite Sidon sets into perfect difference sets (as referenced in the statement). 3. Study the extension problem: when can a finite Sidon set in $[1,N]$ be extended to a larger Sidon set without losing the Sidon property?

(iv) What a minimal counterexample would likely look like.

If the true supremum limsup constant were $<1$, then there would exist an $\varepsilon>0$ such that every Sidon set satisfies $|A\cap[1,N]|\le (1-\varepsilon)\sqrt{N}$ infinitely often. A minimal obstruction would likely come from a structural limitation on how often dense finite Sidon sets can occur along an infinite set (e.g. a rigidity preventing them from appearing at infinitely many scales).