Thresholds of completeness for $k$-th powers: is $T(n^k)>T(n^{k+1})$ infinitely often? (Erdős #345)
Statement
A sequence $A\subseteq \mathbb{N}$ is complete if every sufficiently large integer is a sum of distinct elements of $A$. For complete $A$, define the threshold of completeness $T(A)$ to be the least integer $m$ such that every $n\geq m$ lies in$$P(A) = \left\{\sum_{n\in B}n : B\subseteq A\textrm{ finite }\right\}$$(completeness guarantees $T(A)$ exists). Writing $T(n^k)$ for the threshold of the sequence of $k$-th powers $\{1^k,2^k,3^k,\ldots\}$: is it true that there are infinitely many $k$ such that $T(n^k)>T(n^{k+1})$?
Acceptance. FULLY RESOLVES: a proof that infinitely many $k$ satisfy $T(n^k)>T(n^{k+1})$, or a proof that only finitely many do (e.g. eventual monotonicity). Machine-checkable (Lean/Coq) proof preferred, else a complete written proof; the infinitary statement cannot be closed by computation alone. ADVANCES: (1) exhibit a single explicit $k$ with $T(n^k)>T(n^{k+1})$, with both thresholds certified — a finite, fully machine-checkable witness and the first descent ever found; (2) compute new exact values $T(n^k)$ for $k$ strictly beyond the largest $k$ whose threshold is stated in the background (or recorded in OEIS A001661 at submission time), each with reproducible code and a completeness certificate proving every $n\geq T$ is a sum of distinct $k$-th powers and $T-1$ is not; (3) prove asymptotic lower/upper bounds on $T(n^k)$ as a function of $k$ (e.g. formalising the $2$-adic obstruction at $k=2^t$ into a proven inflation of $T(n^{2^t})$). Deliver the search code plus certificates and values, or the proof file.
Background
Posed by Erdős and Graham [ErGr80, p.55], who remark that very little is known about $T(A)$ in general; listed as open on erdosproblems.com/345 (fetched 2026-07-13, status 'open'). The sequence of $k$-th powers is complete for every $k$ (a classical fact going back to Sprague for squares), and the page records the known thresholds: $T(n)=1$, $T(n^2)=128$, $T(n^3)=12758$, $T(n^4)=5134240$, and $T(n^5)=67898771$ — monotonically increasing so far, so the conjectured infinitely-many descents $T(n^k)>T(n^{k+1})$ have never been witnessed. (These values follow the convention of OEIS A001661, which records the largest integer NOT a sum of distinct $k$-th powers; Sprague's theorem that 128 is the largest non-sum of distinct squares is the $k=2$ entry.) Erdős and Graham point out the natural candidates for a first descent: $k=2^t$ for large $t$ — perhaps already $t=3$, i.e. $k=8$ versus $k=9$ — because $n^{2^t}$ takes highly restricted values modulo $2^{t+1}$, which should inflate $T(n^{2^t})$ relative to its neighbour. The attacker's tool: large-scale enumeration — compute new exact thresholds $T(n^k)$ for $k\geq 6$ by dynamic programming over reachable subset sums combined with a completeness certificate (verify a long enough run of representable integers that induction on adding further powers closes all larger integers), thereby extending OEIS A001661 and directly testing the $k=8$ vs $k=9$ prediction; a single verified descent would be a landmark, while the full 'infinitely many' statement needs a proof exploiting the modular obstruction structure.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #345 (T. F. Bloom) | website |
| REF-02 | OEIS A001661 — largest number not a sum of distinct n-th powers | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.