Arbitrarily large number of representations

Question

For a positive integer $k$ let $\gamma_k(n)$ be the number of representations of $n$ as a sum of strictly increasing perfect $k^{\text{th}}$ powers. For example $\gamma_k(2)=0$ for any $k$. Now is the following true?

For any $x\in \mathbb{R}^\ast_+$ there's an integer $N$ such that for all $n\ge N$ $$\dfrac{\max_{1\le i\le n}\;\gamma_k(i)}{n}>x$$

Motivation : This is motivated from an easier problem : Let $\gamma^{\ast}_k(n)$ be number of representations of $n$ as sum of distinct $k^{\text{th}}$ powers, where order doesn't matter. Then $\exists \; n$ such that $$\gamma_k^{\ast}(n)>nx$$ for any positive real $x$. Can someone shed some light on this conjecture of mine? I have tried to check as much as possible,and I have found no way out of it. Thanks for all help.

Answer 1

Yes, the statement is true.

For any positive integer $m$ there are $2^m$ subsets of $\{1^k,2^k,\ldots,m^k\}$. Each subset has sum bounded by $m^{k+1}$, so by the pigeonhole principle $$ \max_{1\leq i\leq m^{k+1}} \gamma_k(i)\geq \frac{2^m}{m^{k+1}}. $$ This shows that $$ \frac{\max_{1\leq i\leq n}\gamma_k(i)}{n}\geq \frac{2^{\lfloor\sqrt[k+1]{n}\rfloor}}{\lceil\sqrt[k+1]{n}\rceil^{k+1} n}, $$ which goes to $\infty$ as $n\to\infty$.

Answer 2

Let $\gamma_{k,s}(n)$ be the number of representations of $n$ as a sum of $s$ distinct $k$-th powers. Clearly $\gamma_k(n)\geq \gamma_{k,s}(n)$ for all $s$. By standard results on Waring's problem, $\gamma_{k,s}(n)\gg n^{s/k-1}$ holds when $s$ is sufficiently large in terms of $k$ (e.g. $s>2^k$), for $n$ sufficiently large in terms of $s$ and $k$. It follows that $\max_{1\leq i\leq n}\gamma_k(i)$ grows faster than any polynomial of $n$ as even the individual terms (with the exception of a bounded number of terms depending on the polynomial) have this property.