A polynomial whose pairwise sums are all distinct (a polynomial Sidon set): does one exist? (Erdős #324)
Statement
Does there exist a polynomial $f(x)\in\mathbb{Z}[x]$ such that all the sums $f(a)+f(b)$ with $0\leq a<b$ (nonnegative integers) are distinct? Equivalently, is there a polynomial $f$ for which the image $\{f(n):n\geq 0\}$ is a Sidon set — a set all of whose pairwise sums are distinct?
Acceptance. FULLY RESOLVES (existence direction): a specific polynomial $f\in\mathbb{Z}[x]$ together with a proof that the sums $f(a)+f(b)$, $0\leq a<b$, are pairwise distinct (equivalently that the associated equal-pair-sum equation has only trivial solutions) — machine-checkable proof preferred. FULLY RESOLVES (nonexistence direction): a proof that no polynomial $f\in\mathbb{Z}[x]$ has this property. ADVANCES: (a) settle the degree-$5$ monomial case — prove $f(x)=x^5$ is a Sidon set (i.e. $x^5+y^5=z^5+w^5$ has only trivial nonnegative solutions), or exhibit an explicit collision refuting it; (b) extend the collision-free verified range for $x^5$ (or another explicit candidate) to a new record $N$, supplying the search code and a certificate that no nontrivial equal pair-sum occurs below $N$; (c) prove a new nonexistence result for a degree beyond those already excluded — e.g. that no general polynomial of some degree $d\geq 4$ works (Dubickas-Novikas handled general degree $3$; $x^4$ is excluded only as a monomial) — with proof; (d) construct, in the style of Ruzsa, an explicit polynomial-image Sidon set of a new degree, with proof. Deliver the polynomial plus proof, the nonexistence proof, or the collision-search code plus certified range / found collision.
Background
Posed by Erdős and Graham [ErGr80, p.53], who called it 'very annoying.' Low degrees are ruled out: a quadratic $f$ cannot work (an easy check), $x^4$ classically cannot, and Dubickas and Novikas [DuNo21] proved that no cubic $f$ works. Degree $5$ is the first plausible case — Erdős and Graham suggest $f(x)=x^5$ 'should work,' and the Lander-Parkin-Selfridge conjecture would imply $x^n$ is a Sidon set for every $n\geq 5$. Ruzsa [Ru01b] proved there exist $c\in[0,1]$ and $n_0\geq 1$ such that $\{n^5+\lfloor cn^4\rfloor:n\geq n_0\}$ is a Sidon set — a degree-$5$ polynomial-image Sidon set, though not of the pure form $x^5$. Discussed as problems C9, D1, F30 in Guy's collection [Gu04]. This is distinct from the venue's many additive Sidon-set problems (e.g. Erdős #30, #41, #44, #329): here the set must be the image of a single integer polynomial. Listed as open on erdosproblems.com/324 (fetched 2026-07-21, status 'open', tagged 'number theory | powers | sidon sets'). No prize is recorded. Attacker's tool: for a candidate $f$ such as $x^5$, the Sidon property is finitely falsifiable — search for a collision $f(a)+f(b)=f(c)+f(d)$ with all arguments $\leq N$ (for $x^5$ this is an equal-sums-of-two-fifth-powers Diophantine search), which either produces a counterexample or extends the collision-free verified range; the existence proof for $x^5$ reduces to bounding solutions of $x^5+y^5=z^5+w^5$.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #324 (T. F. Bloom) | website |
| REF-02 | Sidon sequence (definition and background) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.