Exact additive complement of a degree-$\geq 2$ polynomial image: does one exist? (Erdős #477)
Statement
Is there a polynomial $f:\mathbb{Z}\to\mathbb{Z}$ of degree at least $2$, together with a set $A\subseteq\mathbb{Z}$, such that every integer $n$ has exactly one representation $n=a+b$ with $a\in A$ and $b\in f(\mathbb{Z})=\{f(k):k\in\mathbb{Z}\}$? Equivalently, does the value set $f(\mathbb{Z})$ admit a perfect (exact, tiling) additive complement $A$?
Acceptance. FULLY RESOLVES (proof-shaped): either exhibit an explicit polynomial $f$ of degree $\geq 2$ and a set $A$ with a proof that every $n\in\mathbb{Z}$ has exactly one representation $n=a+b$ ($a\in A$, $b\in f(\mathbb{Z})$); OR prove that no such pair exists for any $f$ of degree $\geq 2$. Machine-checkable (Lean) proofs are preferred, else a complete written proof. Because the degree-$2$ case and the family with $f(\mathbb{Z})-f(\mathbb{Z})\supseteq q\mathbb{Z}$ are already resolved negatively, a resolving contribution must cover the remaining open cases (some polynomial of degree $\geq 3$, or all of them). ADVANCES: a proof of non-existence for a new explicit class of degree-$\geq 3$ polynomials strictly larger than the family recorded in the background (e.g. all cubics, or all $f$ of a stated shape), with proof; or a formal (Lean) verification extending the known degree-$2$ impossibility to a new degree. Deliver the construction, the impossibility proof, or the formal artifact.
Background
A question of Erdős and Graham [ErGr80, p.95], who expected the answer to be negative; listed as open on erdosproblems.com/477 (fetched 2026-07-21, status 'open'). Any such $A$ must be infinite. A neighbouring venue problem, Erdős #33, instead concerns the minimal-density (inexact) additive complement of the squares $k^2$ — the degree-$2$ image — asking only that $A$ plus the squares cover all large integers, not that each integer have exactly one representation. The degree-$2$ case is now settled negatively: no such $A$ exists when $\deg f=2$. A short argument (combining AlphaProof and Adenwalla, in the site comments) shows that for $f(x)=c_2x^2+c_1x+c_0$ one can always find $a,b\in A$ producing two distinct representations of some $n$; the same argument rules out every $f$ for which $f(\mathbb{Z})-f(\mathbb{Z})$ contains all multiples of a fixed $q\geq 1$, such as any $f(x)=g((x-k)^2)+c_1x+c_0$ with $c_1\neq 0$. The general question — degrees $\geq 3$ outside this family — remains open. The problem carries a Sidon-sets tag and is formalized in Lean. No prize. Attacker's tool: extend the difference-set obstruction to higher-degree $f$ (a Lean formalization is available to build on), or, for a candidate $f$, computationally search for an exact complement $A$ up to a large bound and analyse its structure.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #477 (T. F. Bloom) | website |
| REF-02 | Lean formalisation of Erdős #477 (google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.