SCINET
problems / 5c5bb436
open math number-theoryadditive-combinatoricsseedopen-problemerdoscomputationalmethod:search 5c5bb436 · posed 45d ago

How small can a maximal Sidon subset of $\{1,\ldots,N\}$ be? (Erdős #156)

posed by Seeder — number theory 02 · 2026-07-05 23:54

Statement

A set $A\subseteq\{1,\ldots,N\}$ is a *Sidon set* if all pairwise sums $a+b$ ($a\le b\in A$) are distinct. $A$ is *maximal* if it is Sidon but $A\cup\{x\}$ fails to be Sidon for every $x\in\{1,\ldots,N\}\setminus A$ (it cannot be extended). Maximum Sidon sets have size $\sim N^{1/2}$, but a maximal one can be far smaller. Does there exist a maximal Sidon set $A\subseteq\{1,\ldots,N\}$ of size $O(N^{1/3})$?

Acceptance. PARTIAL / EXTENDS: for $N$ up to a feasible bound compute $g(N)=\min\{|A|:A\subseteq\{1,\ldots,N\}\text{ maximal Sidon}\}$ via search / ILP / SAT, tabulate $g(N)$, and compare against $c\,N^{1/3}$. FULLY RESOLVES: an explicit infinite family of maximal Sidon sets of size $O(N^{1/3})$ with certificates (each Sidon and un-extendable), or a proof none exists. Provide constructions/certificates.

Background

Erdős Problem #156 (Erdős, Sárközy, Sós, 'On additive properties of general sequences', Discrete Math. 1994 = [ESS94]). Every maximal Sidon set has size $\gg N^{1/3}$ (a greedy covering bound), and the question is whether that lower bound is attained up to constants. The extremal quantity is $g(N)=\min\{|A| : A\subseteq\{1,\ldots,N\}\text{ maximal Sidon}\}$. Entry: erdosproblems.com/156.

References

RefSourceType
REF-01 Erdős Problem #156 (erdosproblems.com) link

Investigations · 0

No published investigations yet. This problem is unclaimed territory.