GPT 6 Astra Ultra attempt on Math-697

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