Density of sums of $k$-th powers: is $f_{k,k}(x)\gg x^{1-\epsilon}$ and $f_{k,m}(x)\gg x^{m/k}$? (Erdős #323)
Statement
For integers $1\leq m\leq k$, let $f_{k,m}(x)$ denote the number of integers $\leq x$ that can be written as a sum of $m$ many nonnegative $k$-th powers. (i) Is it true that for every $\epsilon>0$, $$f_{k,k}(x)\gg_\epsilon x^{1-\epsilon}?$$ (ii) Is it true that for $m<k$ and all sufficiently large $x$, $$f_{k,m}(x)\gg x^{m/k}?$$
Acceptance. FULLY RESOLVES: a proof (machine-checkable Lean/Coq preferred, else a complete written proof) establishing (i) $f_{k,k}(x)\gg_\epsilon x^{1-\epsilon}$ for all $\epsilon>0$ (for $k\geq 3$) and (ii) $f_{k,m}(x)\gg x^{m/k}$ for all $m<k$ and large $x$, or a disproof of either. ADVANCES: (a) prove that $f_{k,k}(x)=o(x)$ FAILS for some $k\geq 3$ (i.e. $f_{k,k}(x)\gg x$), or conversely prove $f_{k,k}(x)=o(x)$, with proof; (b) prove a power lower bound $f_{k,m}(x)\gg x^{\alpha}$ with $\alpha$ strictly larger than the best exponent stated in the background for the relevant $(k,m)$ (for $m<k$, moving toward $m/k$; the $m=3,k=3$ record is Wooley's $0.917\cdots$, cf. Erdős #325), with proof; (c) prove the exact conjectured exponent for any single new pair $(k,m)$, with proof; (d) rigorously compute $f_{k,m}(x)$ over a large range and report a certified empirical exponent with the sieving code (evidence, not a proof). Deliver the proof, the improved-exponent proof, or the sieving code plus certified counts.
Background
Posed by Erdős and Graham [ErGr80], who called it 'unattackable by the methods at our disposal.' The exponent $m/k$ is the expected order, since there are $\asymp x^{m/k}$ candidate $m$-tuples of $k$-th powers with sum $\leq x$. The case $k=2$ is classical: Landau proved $f_{2,2}(x)\sim cx/\sqrt{\log x}$ for sums of two squares, so $f_{2,2}(x)=o(x)$. For $k>2$ it is not even known whether $f_{k,k}(x)=o(x)$. The $m=3$ special case of (ii) is the sharper venue problem Erdős #325 (which records Wooley's $f_{3,3}(x)\gg x^{0.917\cdots}$); the representation-count analogue (how large a single integer's representation count can be) is Erdős #322. Listed as open on erdosproblems.com/323 (fetched 2026-07-21, status 'open', tagged 'number theory | powers'). No prize is recorded. Attacker's tool: exact computation of $f_{k,m}(x)$ by sieving the $m$-fold sumset of $k$-th powers up to $x$ yields the empirical exponent $\log f_{k,m}(x)/\log x$ and tests the conjectured $m/k$ and $1-\epsilon$ rates; circle-method / Hooley-delta analysis supplies the proof.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #323 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.