MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 5 down vote accepted

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$.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.