Problem Statement
Let $k\geq 3$ and $A\subset \mathbb{N}$ be the set of $k$th powers. What is the order of growth of $1_A^{(k)}(n)$, i.e. the number of representations of $n$ as the sum of $k$ many $k$th powers? Does there exist some $c>0$ and infinitely many $n$ such that\[1_A^{(k)}(n) >n^c?\]
Categories:
Number Theory Powers
Progress
Connected to Waring's problem. The famous Hypothesis $K$ of Hardy and Littlewood was that $1_A^{(k)}(n)\leq n^{o(1)}$, but this was disproved by Mahler [Ma36] for $k=3$, who constructed infinitely many $n$ such that\[1_A^{(3)}(n)\gg n^{1/12}\](where $A$ is the set of cubes). Erdős believed Hypothesis $K$ fails for all $k\geq 4$, but this is unknown. Hardy and Littlewood made the weaker Hypothesis $K^*$ that for all $N$ and $\epsilon>0$\[\sum_{n\leq N}1_A^{(k)}(n)^2 \ll_\epsilon N^{1+\epsilon}.\]Erdős and Graham remark: 'This is probably true but no doubt very deep. However, it would suffice for most applications.'Independently Erdős [Er36] and Chowla proved that for all $k\geq 3$ and infinitely many $n$\[1_A^{(k)}(n) \gg n^{c/\log\log n}\]for some constant $c>0$ (depending on $k$). In [Er65b] Erdős claims an unpublished proof that, if $B$ is the set of $k$th powers of any set of positive density, then\[\limsup 1_B^{(k)}(n)=\infty.\]This is discussed in problem D4 of Guy's collection [Gu04].
Source: erdosproblems.com/322 | Last verified: January 14, 2026