# Growth of $n=n(k)$ for which there's a non-trivial solution to $x_1^k+\cdots+x_n^k=y^k$?

Walter Hayman just asked me the following question. What, if anything, is known about the growth of the function $n(k)$, where $k\geq1$ is an integer, and $n=n(k)\geq2$ is the smallest integer for which there is a non-trivial solution in positive integers to $$x_1^k+x_2^k+\cdots+x_n^k=y^k.$$

Walter observed that an upper bound for $n(k)$ is $G(k)$ [EDIT: this should probably say $G(k)+1$], the "big $G$" function used as standard notation in discussions of Waring's Problem. Explicitly, $G(k)$ is the smallest $m$ such that every sufficiently large integer is the sum of at most $m$ $k$th powers; the trick of course is then to choose a sufficiently large $k$th power [EDIT: and then subtract 1.]. Hence $n(k)$ grows at most as fast as $G(k)$, and a fair bit is known about the growth of $G(k)$ (again see the Wikipedia page); for example $G(k)=O(k\log(k))$. We deduce that $n(k)$ is at most $O(k\log(k))$. The question is whether it is possible to do any better.

I would imagine that lower bounds are hopeless -- it was a lot of work to prove that $n(k)\geq3$ for all $k\geq3$, and I am not sure that mathematics is ready to rule out the possibility that there are arbitrarily large integers $k$ such that there are solutions to $a^k+b^k+c^k=d^k$ in positive integers (i.e. that $n(k)\geq4$ for all sufficiently large $k$). But it did not seem unreasonable to hope that there were better upper bounds than the naive approach going via $G(k)$, so I told him I'd ask here.

-
I asked about lower bounds at mathoverflow.net/questions/64649/… –  Boris Bukh Mar 16 '12 at 16:45
I don't see why $G(k)$ is an upper bound for $n(k).$ Since every large $k$-th power is already a $k$-th power, I think they are irrelevant to the value of $G(k).$ –  Will Jagy Mar 18 '12 at 20:08
$3^3 + 4^3 + 5^3 = 6^3, \; \; \; 1^3 + 6^3 + 8^3 = 9^3, \; \; 3^3 + 10^3 + 18^3 = 19^3, \; \; 7^3 + 14^3 + 17^3 = 20^3$ –  Will Jagy Mar 18 '12 at 21:02
Will -- you're right. I guess you can use not $N^k$ but $N^k-1$ in the $G(k)$ result, giving $n(k)\leq G(k)+1$ which is still good enough for what follows. Thanks. I'll fix it. –  Kevin Buzzard Mar 19 '12 at 10:26
@Will, isn't D1 more to the point than D7? We have (thanks to Noam Elkies) 3 4th powers that sum to a 4th power, and (thanks to Lander and Parkin) 4 5th powers that sum to a 5th power. Guy says that for $k\ge6$ there is no known sum of $k$ $k$th powers giving a $k$th power. –  Gerry Myerson Mar 29 '12 at 23:09