Representations as sums of $k$ many $k$-th powers: can the count exceed $n^c$ infinitely often? (Erdős #322)
Statement
Fix $k\geq 3$ and let $A=\{1^k,2^k,3^k,\ldots\}$ be the set of $k$-th powers. Let $1_A^{(k)}(n)$ denote the number of representations of $n$ as a sum of $k$ many $k$-th powers. What is the order of growth of $1_A^{(k)}(n)$? In particular, does there exist a constant $c>0$ and infinitely many $n$ such that $$1_A^{(k)}(n)>n^{c}?$$
Acceptance. FULLY RESOLVES: a proof (machine-checkable Lean/Coq preferred, else a complete written proof) that for a given $k\geq 4$ there is $c>0$ with $1_A^{(k)}(n)>n^{c}$ for infinitely many $n$ (disproving Hypothesis $K$ for that $k$, as Mahler did for $k=3$), OR a proof that no such $c$ exists for some $k\geq 4$ (Hypothesis $K$ holds there); establishing the true order of growth of $1_A^{(k)}(n)$ for any single $k\geq 4$ resolves the headline for that $k$. ADVANCES: (a) improve Mahler's exponent for $k=3$ — prove $1_A^{(3)}(n)\gg n^{c}$ for infinitely many $n$ with $c$ strictly larger than the best published constant (which is Mahler's $1/12$), via proof or an explicit reproducible family; (b) prove Hypothesis $K^*$ $\bigl(\sum_{n\leq N}1_A^{(k)}(n)^2\ll_\epsilon N^{1+\epsilon}\bigr)$ for some $k$, or any nontrivial improvement over the trivial second-moment bound, with proof; (c) computationally exhibit, for $k=3$ or $k=4$, integers $n$ with certified representation count $1_A^{(k)}(n)$ exceeding the current record multiplicity, supplying the search code and the fully factored representations. Deliver the proof, the improved-exponent family plus proof, or the record-search code plus certified high-multiplicity representations.
Background
This is the failure-of-Hypothesis-$K$ question from Waring's problem. Hardy and Littlewood's Hypothesis $K$ asserted $1_A^{(k)}(n)\leq n^{o(1)}$; Mahler [Ma36] disproved it for $k=3$ by constructing infinitely many $n$ with $1_A^{(3)}(n)\gg n^{1/12}$ (where $A$ is the cubes). Whether Hypothesis $K$ fails for every $k\geq 4$ is unknown — Erdős believed it does. Independently Erdős [Er36] and Chowla proved that for all $k\geq 3$ there are infinitely many $n$ with $1_A^{(k)}(n)\gg n^{c/\log\log n}$ for some $c>0$ depending on $k$ (unbounded, but still $n^{o(1)}$). Hardy and Littlewood's weaker Hypothesis $K^*$, that $\sum_{n\leq N}1_A^{(k)}(n)^2\ll_\epsilon N^{1+\epsilon}$, remains open; Erdős and Graham call it 'probably true but no doubt very deep' while noting it 'would suffice for most applications'. In [Er65b] Erdős claims an unpublished proof that $\limsup_n 1_B^{(k)}(n)=\infty$ whenever $B$ is the set of $k$-th powers of a positive-density set. Discussed as problem D4 in Guy's collection [Gu04]. From [Er65b] and [ErGr80]. Related OEIS A025456, A025418. Note this is about the representation count of a single $n$ (Hypothesis $K$), distinct from the venue's density questions on how many integers are representable (Erdős #323, #325). Listed as open on erdosproblems.com/322 (fetched 2026-07-21, status 'open', tagged 'number theory | powers'). No prize is recorded. Attacker's tool: direct computation of $1_A^{(3)}(n)$ to hunt record-multiplicity $n$ that extend Mahler's $n^{1/12}$ construction, plus mean-square / circle-method estimates toward Hypothesis $K^*$.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #322 (T. F. Bloom) | website |
| REF-02 | OEIS A025456 — number of representations of n as a sum of cubes (per erdosproblems.com/322) | website |
| REF-03 | OEIS A025418 — related representation-count sequence for sums of powers (per erdosproblems.com/322) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.