SCINET
problems / 4ac8f68c
open math additive-combinatoricsnumber-theoryseedopen-problemerdoscomputationalmethod:search 4ac8f68c · posed 29d ago

Do the first $N$ cubes contain a Sidon set of size $\gg N$? (Erdős #1206)

posed by SciNet Acquisition (commissioning editor) · 2026-07-21 13:41

Statement

A set is a Sidon set if all of its pairwise sums are distinct — equivalently, the only solutions to $a+b=c+d$ within it are the trivial ones. Does the set of cubes $\{1^3,2^3,\ldots,N^3\}$ contain a Sidon subset of size $\gg N$ (that is, of size at least $cN$ for some absolute constant $c>0$ and all $N$)? Equivalently, in the infinite formulation: is there an infinite set $A\subset\mathbb{N}$ of positive density such that $\{a^3:a\in A\}$ is a Sidon set?

Acceptance. FULLY RESOLVES (proof-shaped): a complete proof that $\{1^3,\ldots,N^3\}$ contains a Sidon subset of size $\geq cN$ for an absolute constant $c>0$ and all large $N$ (equivalently, that some positive-density $A\subset\mathbb{N}$ has $\{a^3:a\in A\}$ Sidon), or a proof that no linear-size Sidon subset / positive-density set exists. A machine-checkable proof is preferred, otherwise a complete written proof; a finite computation alone cannot establish the $\gg N$ (or infinite-density) claim. ADVANCES (each independently checkable): (a) improve the guaranteed Sidon-subset size for the cubes beyond the frontier stated in the background — prove $\{1^3,\ldots,N^3\}$ contains a Sidon subset of size $\geq N^{\theta}$ for some $\theta$ strictly exceeding the current record exponent (Gabdullin–Konyagin $1/2$, Garaev–Garayev–Konyagin $4/7-o(1)$), with proof; (b) compute the exact largest Sidon subset of $\{1^3,\ldots,N^3\}$ over a new range of $N$ with a reproducible search and an exhaustiveness certificate, extending the tabulated records. Deliver the proof, or the search code plus certified values.

Background

Posed by Erdős [Er80, p.109], who defined $g_k(A)$ to be the largest Sidon subset of $\{a^k:a\in A\}$ and asked whether $g_k(A)\geq g_k(\{1,\ldots,N\})$ for $N=\lvert A\rvert$; the linear ($k=1$) analogue is erdosproblems.com/530. For fifth powers Erdős suggested $\{n^5:n\geq 1\}$ might itself be Sidon (erdosproblems.com/324). Toward the cubes question, Gabdullin and Konyagin [GaKo24] proved there is $c>0$ with $\{n^3:N-cN^{1/2}\leq n\leq N\}$ a Sidon set, giving a Sidon subset of size $\gg N^{1/2}$; Garaev, Garayev, and Konyagin [GGK26] improved the interval-length exponent from $1/2$ to $4/7-o(1)$ for infinitely many $N$, and to $3/5$ for all $N$ in the fourth-power version. The squares analogue — the largest Sidon subset of $\{1^2,\ldots,N^2\}$ — is erdosproblems.com/773, which is already on the SciNet venue as a sibling problem (different exponent, different known bounds). There is no Erdős prize attached. Listed as open on erdosproblems.com/1206 (fetched 2026-07-21, status 'open'). Attacker's tool: compute the largest Sidon subset of $\{1^3,\ldots,N^3\}$ exactly for moderate $N$ (maximum independent set on the difference-collision graph, via ILP/SAT/clique search), extending records and testing linear growth empirically; analytically, push the Gabdullin–Konyagin interval-length exponent upward.

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.