Prove: For all $n\geq 1$, $a_{n+1}-a_n<8^ka_n^{\left(1-\frac{1}{k}\right)^3}$.

Question

Set $S=\left\{\left.x^k+y^k+z^k\right|x,y,z\in Z^+\cup \{0\}\right\}$, k is a positive integer, sort elements of $S$ increasingly, that $a_1<a_2<a_3<\text{...}<a_n<\text{...}$.

Prove: For all $n\geq 1$, $a_{n+1}-a_n<8^ka_n^{\left(1-\frac{1}{k}\right)^3}$.

---

And how about the case $S=\left\{\left.x^k+y^k+z^k+w^k\right|x,y,z\in Z^+\cup \{0\}\right\}$

Answer 1

This is false. For the case $n=1$:

$$\begin{align} a_1&=0 \\ (\forall{k})a_2&=1\end{align}$$

$$a_2-a_1=1$$ $$8^ka_1^{(1-\frac{1}{k})^3}=0$$

$$1\not<0$$

Therefore the statement is false.

Answer 2

For $k$ large enough (like $6$ or $7$), multiple representations of integers as sums of three $k$-th powers are rare enough to be negligible, and the number of integer solutions of $x^k + y^k + z^k \leq M$ approximately $\alpha M^{3/k}$ with error bounded by a smaller power of $M$. Consequently $a_n$ is approximately $\beta n^{k/3}$. One would like to say that first differences of $a_n$ are about $\gamma n^{(k/3)-1} \sim \delta {a_n}^{(1 - (3/k))}$, and it is true "on average". Constants $\alpha, \beta,\gamma,\delta$ can be calculated exactly, and depend on $k$ but not $n$.

Conclusion: for large enough $k$, for large $n$, the power of $a_n$ on the right side of the inequality is higher than the threshold for the statement to hold on average. If this extra slack is enough to for the inequality to hold without averaging, it would be for $n \geq N_0(k)$. More care is needed to understand the situation for all $n$, and control over small $k$ is potentially very difficult as is known from Linnik's problem ($k=2$).