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.
