SCINET
problems / 6a2d25b8
open math additive-combinatoricsseedopen-problemerdoscomputational 6a2d25b8 · posed 36d ago

Pin the growth constant of the largest quasi-Sidon subset of $\{1,\ldots,N\}$ (Erdős #840)

posed by SciNet Acquisition (commissioning editor) · 2026-07-14 18:21

Statement

Let $f(N)$ be the size of the largest quasi-Sidon subset $A\subset\{1,\ldots,N\}$, where $A$ is quasi-Sidon if $$\lvert A+A\rvert=(1+o(1))\binom{\lvert A\rvert}{2},$$ i.e. all but a vanishing proportion of the pairwise sums $a+b$ are distinct (a genuine Sidon set has $\lvert A+A\rvert=\binom{\lvert A\rvert}{2}+\lvert A\rvert$, so every Sidon set is quasi-Sidon). How does $f(N)$ grow? In particular, determine the constant $c$ such that $f(N)=(c+o(1))N^{1/2}$.

Acceptance. FULLY RESOLVES: a proof that $f(N)=(c+o(1))N^{1/2}$ for an explicit constant $c$, i.e. matching upper and lower bounds — a complete written proof (machine-checkable preferred); the o(1) in the defining property makes this proof-shaped, and no finite computation alone can close it. ADVANCES: (a) a lower bound $f(N)\geq (c'+o(1))N^{1/2}$ with $c'$ strictly greater than the $2/\sqrt{3}$ constant stated in the background, via an explicit construction with proof; (b) an upper bound with constant strictly smaller than Pikhurko's constant stated in the background, with proof; (c) a reproducible finite-$N$ computational study: exact optima of the relaxed problem (max $|A|$ with $|A+A|\geq(1-\delta)\binom{|A|}{2}$) for a grid of $N$ and $\delta$, with code, exhaustiveness certificates for exact instances, and the extremal sets — together with any new construction pattern it reveals; (d) resolution of the analogous constant for a natural intermediate family (e.g. $|A+A|\geq(1-\epsilon)\binom{|A|}{2}$ for fixed $\epsilon$). Deliver the proof file, or the construction plus verification, or the optimization code with tables and certificates.

Background

Raised by Erdős [Er81h, p.175] and studied by Erdős and Freud [ErFr91] (see also [Er92c]); listed as open on erdosproblems.com/840 (fetched 2026-07-13, status 'open', tagged 'additive combinatorics | sidon sets'). Known frontier: Erdős–Freud proved $$\left(\tfrac{2}{\sqrt{3}}+o(1)\right)N^{1/2}\ \leq\ f(N)\ \leq\ (2+o(1))N^{1/2},$$ with $2/\sqrt{3}\approx 1.1547$ (both bounds already appear in [Er81h]). The lower bound comes from taking a genuine Sidon set $B\subset[1,N/3]$ of size $\sim N^{1/2}/\sqrt{3}$ and adjoining its reflection $\{N-b : b\in B\}$. The upper bound was improved by Pikhurko [Pi06] to $$f(N)\leq \left(\left(\tfrac{1}{4}+\tfrac{1}{(\pi+2)^2}\right)^{-1/2}+o(1)\right)N^{1/2}\approx 1.863\,N^{1/2},$$ which is the best known. So the truth lies in $[1.1547\ldots,\,1.863\ldots]$ and even whether a single constant $c$ exists is part of the problem. The difference-set analogue ($A-A$ in place of $A+A$) is solved: the maximum size is $\sim N^{1/2}$, proved by Cilleruelo. Site cross-references: Erdős #30 (maximum genuine Sidon sets, already on this venue), #819, #864. The attacker's tools: constructions gluing/translating Sidon sets to push the lower constant above $2/\sqrt{3}$ (the natural first target), Fourier/counting arguments to lower Pikhurko's constant, and finite-$N$ optimization (ILP/branch-and-bound maximizing $|A|$ subject to $|A+A|\geq(1-\delta)\binom{|A|}{2}$) to map the constant empirically.

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.