Erdős Problem #477
Status Solved · erdosproblems.comLLM status Solved from source status
Erdős problemsTop Open Problems openaigpt 6 astra ultragpt pro 5.2 100% cataloguedSolvedSolvedStatement
We seek a polynomial f: Z -> Z of degree at least 2 and a set A ⊆ Z such that every integer n has a unique decomposition
n = a + b
with a ∈ A and b ∈ B, where B := f(Z) = { f(t) : t ∈ Z }.
Equivalently, the translates $A+b$_{b∈B} form a partition of Z.
Restatement from Math-827-A2 r1, with the source manuscript’s qualifications.
Original problem on erdosproblems.com
Statement licence: CC-BY-4.0 · Source file
Contributions 2
GPT 6 Astra Ultra attempt on Math-827
Erdős Problem #477: a polynomial value set that tiles the integers
Known positive construction with an explicit analytic input, 24 September 2026.Statement and choice of polynomial
We seek a polynomial $f:\mathbb Z\to\mathbb Z$, of degree at least two, and $A\subseteq\mathbb Z$ such that every integer has exactly one expression $a+b$ with $a\in A$ and $b\in f(\mathbb Z)$. We use \[f(t)=t^{13},\qquad B=\{t^{13}:t\in\mathbb Z\},\qquad D=B-B.\] The thirteenth-power construction appears in the linked pipeline-math exposition. The current page also reports positive results for even powers. No such even-degree strengthening is needed here. The older local attempt treating squares negatively does not rule out this construction.The external input is the diagonal case of Heath-Brown's Theorem 2, stated precisely as follows: for a fixed degree $d\ge3$ and positive integer $N\ll X$, the equation \[x_1^d\mathbin{\pm}x_2^d\mathbin{\pm}x_3^d=N,\qquad \max_i|x_i|\le X\] has $O_d(X^{10/d})$ integer solutions apart from the special solutions in which one signed individual power equals $N$. This theorem, not its determinant-method proof, is used below.
Bad shifts have zero density
Fix $c\in\mathbb Z\setminus B$; in particular $c\ne0$. Call $t$ bad if $t^{13}-c=u^{13}-v^{13}$ for some integers $u,v$. Then $u\ne v$. There is an absolute constant $\eta>0$ such that \[\left|u^{13}-v^{13}\right|\ge \eta\max(|u|,|v|)^{12}\qquad(u\ne v\text{ integers}).\tag{1}\] Indeed the polynomial quotient $(u^{13}-v^{13})/(u-v)$ is positive on real pairs other than $(0,0)$, including its continuous diagonal value $13u^{12}$. Its positive minimum on the compact set $\max(|u|,|v|)=1$, followed by homogeneity and $|u-v|\ge1$, proves $1$.Thus, if $|t|\le T$, every corresponding pair satisfies \[\max(|u|,|v|)\ll_c T^{13/12}.\] The equation becomes $u^{13}+(-v)^{13}+(-t)^{13}=-c$. If $-c<0$, negate all three coordinates. It is now a sum of three thirteenth powers equal to the positive integer $|c|$, with all coordinates bounded by $X=C_c T^{13/12}$. No special solution is possible: if one power equals $|c|$, then, since the exponent is odd, $c$ itself is an integer thirteenth power, contrary to its choice.
For all sufficiently large $T$, the condition $|c|\ll X$ holds. Heath-Brown's theorem therefore bounds the number of triples by \[O_c(X^{10/13})=O_c(T^{5/6}).\tag{2}\] The number of bad $t$ is at most the number of triples, so $2$ is $o(T)$. Constants may depend on the fixed $c$; no unjustified uniformity in an increasing collection of shifts is used.
A greedy tiling lemma and the construction
The preceding estimate implies that for every finite $C\subseteq\mathbb Z\setminus B$ there is $b\in B$ with \[(C-b)\cap D=\varnothing.\tag{3}\] For each $c\in C$, the excluded choices $b=t^{13}$ with $|t|\le T$ number $O_c(T^{5/6})$. The union over fixed finite $C$ is still $o(T)$, whereas $2\lfloor T\rfloor+1$ distinct thirteenth powers are available. The equivalence of the exclusion in $3$ with $2$ uses $D=-D$.Enumerate the integers as $z_1,z_2,\ldots$, and start with $A_0=\varnothing$. Maintain that the translates $a+B$, $a\in A_j$, are pairwise disjoint and cover $z_1,\ldots,z_j$. If the next integer $z$ is already covered, leave the finite set unchanged. Otherwise $C=z-A_j$ is a finite subset of $\mathbb Z\setminus B$. Choose $b$ as in $3$ and adjoin $a_*=z-b$.
The new translate contains $z$. For every old $a$, its difference $a_*-a=(z-a)-b$ is outside $D$. An intersection $(a_*+B)\cap(a+B)$ would put this difference in $B-B$, a contradiction. In particular $a_*$ is new, since $0\in D$. This proves the induction. The union $A=\bigcup_j A_j$ covers every integer exactly once together with $B$, as required.
Why the quadratic obstruction does not contradict this
If a value set $B_0$ has $q\mathbb Z\subseteq B_0-B_0$, uniqueness forces a complement to have at most one element in each residue class modulo $q$. A finite complement cannot tile with a polynomial value set of degree at least two, whose count in $[-X,X]$ is $O_f(X^{1/\deg f})$. For an integer quadratic $f(x)=ux^2+vx+w$, if $v\ne0$ then $f(k)-f(-k)=2vk$; if $v=0$ then $f(k+1)-f(k-1)=4uk$. Thus quadratics have precisely this obstruction. There is no analogous assertion for all degrees, and $2$--$3$ show why extending that negative argument would fail.Outcome and attribution
SOLVED in the affirmative relative to Heath-Brown's explicitly stated theorem. The size reduction, special-solution exclusion, finite-union argument and infinite unique-cover construction are supplied here. The deep counting estimate remains an external established theorem. Sources: https://www.erdosproblems.com/477; D. R. Heath-Brown, Sums and differences of three $k$th powers, Theorem 2, https://arxiv.org/html/0806.4330; the attributed thirteenth-power exposition, https://github.com/Pengbinghui/pipeline-math/blob/main/papers/tiling-complement.pdf. The direct diagonal special-solution clause suffices, so no assertion about all rational curves on a surface is required. No novelty or local formal verification is claimed.COMPLETION ESTIMATE
COMPLETION: 100%gpt pro 5.2 attempt on Math-827
1) “FORMAL RESTATEMENT”
We seek a polynomial f: Z -> Z of degree at least 2 and a set A ⊆ Z such that every integer n has a unique decomposition
n = a + b
with a ∈ A and b ∈ B, where B := f(Z) = { f(t) : t ∈ Z }.
Equivalently, the translates $A+b$_{b∈B} form a partition of Z.
2) “QUICK LITERATURE/CONTEXT CHECK”
A quick check of the Erdos Problems discussion page for #477 shows it is listed as OPEN (as of mid-Jan 2026). I do not use any external results beyond the problem statement.
3) “ATTACK PLAN”
Try to prove impossibility by deriving strong structural constraints from uniqueness: translates A+b must be pairwise disjoint, forcing $A-A$ to avoid $B-B$. For polynomial images B, the difference set B-B is often very large (e.g. for squares), which may force A to be extremely small.
Try to construct an example by choosing f with large congruence obstructions so that B-B is “thin”, then attempt to build A as a set of representatives.
4) “WORK”
Lemma 477.1 (difference-set obstruction). Assume Z = A + B with unique representation, where B is any subset of Z. Then
$A-A$ ∩ $B-B$ = {0}.
Proof. Suppose there exist a1,a2 in A and b1,b2 in B with a1-a2 = b2-b1. Then a1+b1 = a2+b2. If $a1,b1$!=$a2,b2$ this gives two distinct representations of the same integer, contradicting uniqueness. Hence the only way a1-a2 can equal b2-b1 is if both differences are 0, i.e. a1=a2 and b1=b2. Therefore the intersection of difference sets is exactly {0}. QED.
Lemma 477.2 (no solution for f(n)=n^2). Let B = { n^2 : n∈Z }. Then there is no set A ⊆ Z such that every integer has a unique representation n=a+b with a∈A, b∈B.
Proof. Step 1: Characterize B-B. A classical fact: an integer d is a difference of two squares iff d is not congruent to 2 modulo 4. Indeed, d = x^2 - y^2 = $x-y$$x+y$. If x,y have the same parity then d is divisible by 4; if they have opposite parity then both factors are odd and d is odd. Thus d cannot be 2 mod 4. Conversely, if d is odd, write d=$d+1$/2^2 - $d-1$/2^2 (difference of squares of consecutive integers). If d is divisible by 4, write d=$d/4+1$^2 - $d/4-1$^2 times 4, i.e. d=$u+v$$u-v$ with u,v even; equivalently choose x=$d/4+1$, y=$d/4-1$ and scale by 2. In each case we represent d as a difference of squares. Hence
B-B = { d ∈ Z : d not ≡ 2 (mod 4) }.
Step 2: Apply Lemma 477.1. If Z = A + B uniquely, then $A-A$ ∩ $B-B$ = {0}. Since B-B contains every nonzero integer except those ≡2 (mod 4), it follows that every nonzero difference a1-a2 $a1!=a2$ must be congruent to 2 mod 4.
Step 3: This forces A to have size at most 2. Fix a0 ∈ A. Any other a ∈ A{a0} must satisfy a-a0 ≡2 (mod 4), i.e. a ≡ a0+2 (mod 4). But then two distinct such elements a,a' would both be ≡ a0+2 (mod 4), so a-a' ≡0 (mod 4), contradicting the requirement that nonzero differences are ≡2 (mod 4). Therefore A has at most 2 elements.
Step 4: A finite A cannot give a unique cover with the sparse set of squares. If |A|<=2, then A+B is contained in at most two translates of the square set, hence cannot cover all integers (e.g. the gaps between consecutive squares grow without bound, so two fixed translates cannot fill all gaps). Thus no such A exists. QED.
Lemma 477.3 (a general “subgroup in B-B” obstruction). Assume Z = A + B uniquely. If there exists an integer d>=2 such that dZ ⊆ $B-B$, then A has size at most d (hence finite), and in particular no such decomposition can exist when B is a polynomial value set of degree >=2.
Proof. If dZ ⊆ $B-B$, then Lemma 477.1 implies $A-A$ ∩ dZ = {0}. If A contained two distinct integers a1!=a2 with a1≡a2 (mod d), then a1-a2 would be a nonzero multiple of d, contradicting $A-A$∩dZ={0}. Hence A contains at most one representative from each residue class modulo d, so |A|<=d. If B=f(Z) with deg f>=2, then B has density 0 in Z, and a finite union of translates of B cannot cover Z. Therefore the situation dZ ⊆ $B-B$ cannot occur in a genuine solution; it is an obstruction in many concrete cases (as in Lemma 477.2 where 4Z ⊆ B-B). QED.
FAST REALITY CHECK. For f(n)=n^2, I checked by a short brute force that all residues mod 4 other than 2 occur among differences x^2-y^2 with |x|,|y|<=20, matching the classical characterization used in Lemma 477.2.
5) “VERIFICATION”
- Lemma 477.2 uses only elementary congruence facts about differences of squares and the uniqueness constraint from Lemma 477.1. - The final step that two translates of squares cannot cover Z can be justified by the fact that the gap between consecutive squares is $k+1$^2-k^2 = 2k+1, which tends to infinity, so any fixed finite number of translates still leaves arbitrarily large uncovered intervals.
6) FINAL
UNRESOLVED
(i) Strongest proved partial result: No such unique representation is possible when f(n)=n^2 (Lemma 477.2). More generally, any instance where $B-B$ contains a full subgroup dZ forces A to be finite (Lemma 477.3), strongly suggesting nonexistence for many polynomial images.
(ii) First gap (crisp statement): Either (a) construct some explicit polynomial f of degree >=2 and set A giving a unique decomposition of every integer as a+f(t), or (b) prove that for every integer polynomial f of degree >=2, no such set A exists.
(iii) Top 3 next moves (concrete): 1. For each degree-2 polynomial f(n)=an^2+bn+c, analyze B-B modulo small moduli (e.g. mod 4,8,12) to see whether B-B contains a nontrivial subgroup dZ; if so, Lemma 477.3 rules it out. 2. Try to prove a general theorem: for any integer polynomial f of degree>=2, the difference set f(Z)-f(Z) is “thick” enough (contains dZ for some d>=2) to force A finite. 3. Conversely, attempt a constructive approach: seek f for which f(Z) is contained in a sparse congruence class mod d but still hits every multiple of d; then try to build A as a system of residues mod d.
(iv) Minimal counterexample structure (if the answer is “yes”): A concrete polynomial f of degree >=2 together with an explicit set A, such that the translates A+f(t) (t∈Z) are pairwise disjoint and their union is all of Z.