Erdős Problem #156

Erdős Problem 156: a checked attempt

GPT_6_Astra_Ultra

25 September 2026

Statement and scope

Does every interval $[1,N]\cap\mathbb Z$ contain a maximal, under inclusion, Sidon set of size $O(N^{1/3})$? Source: https://www.erdosproblems.com/156. We prove an exact blocking characterization and the lower bound \[ 2N\le |A|^3+|A| \] for every maximal Sidon set. These are necessary conditions and an exact finite test; the requested uniform upper construction remains unresolved.

Exactly what blocks an additional element

Let $A$ be Sidon and $x\notin A$. The new unordered sums after adjoining $x$ are $2x$ and $x+a$ for $a\in A$. They are mutually distinct: $x+a=x+b$ forces $a=b$, and $2x=x+a$ would force $x=a$. Thus $A\cup\{x\}$ fails to be Sidon exactly when a new sum equals an old sum, that is, when \[ 2x=b+c\quad\text{or}\quad x+a=b+c \qquad(a,b,c\in A). \tag{1} \] Consequently maximality in $[1,N]$ is equivalent to covering every integer outside $A$ in that interval by $(A+A)/2$ or $A+A-A$. The half-sum set contributes only its integer points.

Counting only genuinely new blocked points

Put $m=|A|$. A midpoint outside $A$ can only come from a pair $b<c$, giving at most $\binom m2$ such points. For a fixed negative summand $a$, there are $\binom{m+1}{2}$ unordered choices of $(b,c)$. Exactly $m$ of these pairs contain $a$, and all those give $b+c-a\in A$. Therefore the number of possible blocked points outside $A$ of the second form is at most \[ m\left(\binom{m+1}{2}-m\right)=\frac{m^2(m-1)}2. \] Counting repeated blocked points more than once only increases this upper bound. Hence a maximal set must satisfy \[ N\le m+\binom m2+\frac{m^2(m-1)}2 =\frac{m^3+m}{2}. \tag{2} \] In particular $m\ge(2N)^{1/3}(1-o(1))$ as $N\to\infty$; indeed $2$ forces $m\to\infty$ and then $m^3+m=m^3(1+o(1))$.

A finite construction and its limitation

Starting with the empty set, repeatedly adjoin any point not blocked by $1$. The process preserves the Sidon property and terminates at a maximal set because the interval is finite. It can be implemented by maintaining the old sum set and checking both sorts of new sums, rather than testing only the three-term-progression obstruction. This procedure guarantees existence of a maximal set, but $2$ is a lower bound and cannot be used to claim the produced set has size $O(N^{1/3})$. Distinct positive differences only give the much weaker universal upper bound $m=O(\sqrt N)$.

Correction and remaining gap

For example, the earlier GPT-Pro-5.2 draft claimed $\{1,4,6\}$ was maximal in $[1,10]$. It is not: adjoining $10$ adds the sums $11,14,16,20$, all distinct from one another and from the old sums $2,5,7,8,10,12$. Thus its numerical maximality table is not accepted. The blocking characterization is retained with the missing comparison among new sums supplied, and the count is sharpened by discarding representations that merely return a point of $A$. The unresolved task is to arrange a Sidon set whose blocked points cover the whole interval efficiently enough to attain the cubic scale with an absolute constant.

Completion rate estimate: 20%.

Erdos problem #156

1) FORMAL RESTATEMENT

A Sidon set $A\subseteq\{1,2,\dots,N\}$ is maximal (with respect to inclusion) if there is no $x\in\{1,\dots,N\}\setminus A$ such that $A\cup\{x\}$ is still Sidon. The question asks whether there always exists a maximal Sidon set of size $O(N^{1/3})$.

2) QUICK LITERATURE/CONTEXT CHECK

The problem file states that it is easy to show a greedy construction produces a maximal Sidon set of size $\gg N^{1/3}$, and (as stated in the file) Ruzsa proved existence of maximal Sidon sets of size $\ll (N\log N)^{1/3}$. I do not use those results as black boxes below; I re-prove the $\Omega(N^{1/3})$ lower bound for maximality.

3) ATTACK PLAN

A maximal Sidon set $A$ blocks every $x\notin A$ by forcing a sum-collision if $x$ were added. Those collisions imply that every $x$ lies in a structured set built from $A$ such as $A+A-A$ or $(A+A)/2$. Counting the size of these structured sets gives a lower bound on $|A|$.

4) WORK

Lemma 156.1 (maximality forces a covering by $A$, $(A+A)/2$, and $A+A-A$).

Let $A\subseteq\{1,\dots,N\}$ be Sidon and maximal. Then every $x\in\{1,\dots,N\}$ satisfies at least one of: \[ \text{(i) }x\in A,\qquad \text{(ii) }2x\in A+A,\qquad \text{(iii) }x\in A+A-A. \] Equivalently, \[ \{1,\dots,N\}\subseteq A\ \cup\ \tfrac12(A+A)\ \cup\ $A+A-A$. \]

Proof. Fix $x\in\{1,\dots,N\}\setminus A$. By maximality, $A\cup\{x\}$ is not Sidon, so among the new unordered sums created by adding $x$ there is a collision with an old sum. The new sums are of two forms:

1. $x+x=2x$,
2. $x+a$ for $a\in A$.

A collision means either:

1. (a) $2x = a+b$ for some $a,b\in A$ (possibly $a=b$). Then $2x\in A+A$, i.e. $x\in\tfrac12(A+A)$.
2. (b) $x+a = b+c$ for some $a,b,c\in A$. Rearranging gives $x=b+c-a\in A+A-A$.

Thus every $x\notin A$ lies in $\tfrac12(A+A)$ or in $A+A-A$, establishing the containment. $\square$

Lemma 156.2 (a crude but explicit lower bound $|A|=\Omega(N^{1/3})$ for maximal Sidon sets).

Let $A\subseteq\{1,\dots,N\}$ be maximal Sidon and let $m=|A|$. Then \[ N \le m + m^2 + m^3, \] and hence for all $N\ge 1$, \[ |A|\ge \left(N/3\right)^{1/3}. \]

Proof. From Lemma 156.1, \[ N\le |A| + |\tfrac12(A+A)| + |A+A-A|. \] Trivially $|\tfrac12(A+A)|\le |A+A|\le m^2$. Also $|A+A-A|\le m^3$ because it is the image of $A^3$ under $(b,c,a)\mapsto b+c-a$. Thus $N\le m + m^2 + m^3 \le 3m^3$ for $m\ge 1$, which implies $m\ge (N/3)^{1/3}$. $\square$

FAST REALITY CHECK (computed small cases).

I brute-forced the minimum size of a maximal Sidon set in $\{1,\dots,N\}$ for $N\le 40$. Let $m_{\min}(N)$ be this minimum. For selected values: \[ \begin{array}{c|c|l} N & m_{\min}(N) & \text{example maximal Sidon set}\\\hline 10 & 3 & \{1,4,6\}\\ 20 & 4 & \{1,4,10,12\}\\ 30 & 5 & \{1,4,10,12,30\}\\ 40 & 5 & \{1,4,10,12,30\} \end{array} \] The full sequence for $2\le N\le 40$ is: \[ 2,2,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5. \] (Starting at $N=2$.) This is compatible with growth slower than $N^{1/3}$ in this tiny range, but not decisive.

5) VERIFICATION

• Lemma 156.1: enumerates exactly the new sums created by adding $x$ and uses maximality to force a collision.
• Lemma 156.2: uses only cardinality bounds $|A+A|\le m^2$ and $|A+A-A|\le m^3$.
• Computation: checked by exhaustive backtracking over Sidon subsets and testing maximality by attempted extensions.

6) FINAL

UNRESOLVED

1. (i) Strongest fully proved partial result obtained here. Any maximal Sidon set $A\subseteq\{1,\dots,N\}$ has size $|A|\ge (N/3)^{1/3}$ (Lemma 156.2).

2. (ii) Exact first gap. Either (a) construct, for every $N$, a maximal Sidon set of size $\le C N^{1/3}$ with an absolute constant $C$, or (b) prove that every maximal Sidon set has size $\omega(N^{1/3})$.

3. (iii) Top 3 next moves (concrete targets).
   1. Sharpen Lemma 156.2 by bounding $|A+A-A|$ substantially below $m^3$ for Sidon sets (Sidon structure should reduce collisions).
   2. Try explicit constructions built from "blocks" that are Sidon internally but whose cross-block sums are arranged to enforce maximality.
   3. Extend brute computations to $N\approx 100$ to guess whether $m_{\min}(N)$ behaves like $c N^{1/3}$.

4. (iv) Minimal counterexample structure (if $O(N^{1/3})$ is false). A counterexample would be a sequence $N\to\infty$ such that every maximal Sidon set in $\{1,\dots,N\}$ has size at least $N^{1/3}\,g(N)$ with $g(N)\to\infty$. By Lemma 156.1, this would force the covering $A\cup \tfrac12(A+A)\cup(A+A-A)$ to be "inefficient" unless $|A|$ is larger than $N^{1/3}$ by a diverging factor.