Sum of Squares and Cubes

 (Jit here). There is a famous theorem of Lagrange that says every natural number $n$ is a sum of four non-negative squares (so that $0$ is allowed). Let's try to prove this theorem. The first observation to make is that if $n$ and $m$ are both sum of four squares, then so is their product. You can look at https://en.wikipedia.org/wiki/Euler%27s_four-square_identity for a proof of this. Given this, we just need to show that any prime number $p$ is a sum of four squares. We first consider the case of $p \equiv 1 \pmod 4$. 

If $p \equiv 1 \pmod 4$, then again it is a well known theorem that it can always be written as a sum of two squares. There are many ways to prove this. The simplest proof is probably due to Thue - one first lets $a$ be a positive integer such that $a^2 \equiv -1 \pmod p$ and $1 < a < p$. This is always doable since $p \equiv 1 \pmod 4$ and so $-1$ is a quadratic residue. Now consider all possible residue classes $x+ay$ as $x,y$ range between $0$ and $\lfloor \sqrt{p} \rfloor$. There are $(\lfloor \sqrt{p} \rfloor +1)^2 > p$ many such pairs, and hence in particular there exists two distinct pairs $(x,y)$ and $(x',y')$ such that $x+ay \equiv x' + ay' \pmod p$. We then get $(x-x') \equiv a(y-y') \pmod p$ and squaring, since $a^2 \equiv -1 \pmod p$, we get $(x-x')^2 + (y-y')^2 \equiv 0 \pmod p$. Now since $(x,y)$ and $(x',y')$ are distinct, we know that $(x-x',y-y')$ is not just $(0,0)$. Also, we may bound it to be less than $2p$, and so this sum must be $p$. Thus we get positive integers such that $x^2+y^2 = p$ as desired.

Here is another way to do this. We consider $\mathbb{Z}[i]$, the ring of Gaussian integers given by $\{a+bi \mid a,b \in \mathbb{Z}\}$. The main idea is that there is an Euclidean algorithm in $\mathbb{Z}[i]$. I won't go into details about it, but this implies that we have a Bezout's lemma: given $x$ and $y$ in $\mathbb{Z}[i]$, we can find some $z$ such that $ax+by$ are all multiples of $z$ for any $a,b \in \mathbb{Z}[i]$, and also that $z$ can be written as a linear combination of $x$ and $y$. Accepting this, we first find $a+bi$ such that $p$ doesn't divide both $a$ and $b$, and $N(a+bi) = a^2 + b^2$ is divisible by $p$. We can do this since we can solve the congruence $x^2+y^2 \equiv 0 \pmod p$ non-trivially. Next we consider the $z$ given by Bezout's lemma for $p$ and $a+bi$. This $z$ cannot be an unit (i.e. $\pm 1$ or $\pm i$) since any linear combination of $a+bi$ and $p$ must have norm divisible by $p$. But $N(z)$ divides $N(p) = p^2$, and since it is not a multiple of $p$ (as $a+bi$ is a multiple of $z$), it must be that $N(z) = p$. So if $z  = x+yi$, we get that $x^2+y^2 = p$ as desired.

Now if $p \equiv 3 \pmod 4$, turns out there is no easy way to do it without doing it for all primes $p$. We can make the first argument a little more sophisticated by using Minkowski's theorem. We consider instead the lattice generated by $v_1 = (a,1)$ and $v_2 = (p,0)$. The fundamental parallelogram has volume $p$. Hence if we consider the region $\{(x,y) \in \mathbb{R}^2 \mid x^2 + y^2 < 2p \}$, this has volume larger than $4p$ and so we have a lattice point in it. Writing it as $mv_1 + nv_2$, we get some lattice point of the form $(ma + np, m)$ such that $(ma+np)^2 + m^2 < 2p$. It is easy to check that $(ma+np)^2 + m^2 \equiv 0 \pmod p$, so it must be exactly $p$. 

Ok now let's do four squares. We don't have such an $a$ when $p \equiv 3 \pmod 4$, but instead we can always solve for $x^2+y^2+1 \equiv 0 \pmod p$. There are many ways to see this and it follows from the fact that there are $\frac{p+1}{2}$ many quadratic residues mod $p$.  Accepting this, we let $a$ and $b$ be positive integers such that $p \mid a^2+b^2+1$. We then consider the following vectors in $\mathbb{R}^4$, given by $(p,0,0,0), (0,p,0,0), (a,b,1,0), (-b,a,0,1)$. If we take any of the two vectors, including picking the same vector twice, their dot product is a multiple of $p$. Hence any linear combination of them will have its norm being a multiple of $p$ too. Now it suffices to note that the volume of our lattice is $p^2$, and so if we consider the region $x^2+y^2+z^2+w^2 < 2p$, again we have a lattice point. The norm of this lattice point then writes our prime number as a sum of four squares.

What about sum of cubes? When going to higher powers, all these methods fail because there is no analogue of Euler's sum of four squares identity. So we can't just do it for primes and try to generalize it (it is not clear how to do it for a prime $p$ either). I am going to try to give a proof that some $N$ exists such that all numbers can be written as a sum of N non-negative cubes. 

First, we consider the identity 

$$\sum_{i=1}^{4} \left( (A+m_i)^3 + (A-m_i)^3 \right) = 6A(A^2 + m_1^2 + m_2^2 + m_3^2 + m_4^2).$$

Since every natural number can be written as the sum of four squares, we can write every number of the form $6A(A^2+m)$ using $8$ cubes. We are going to take $A = 8^k$ for some positive integer $k$, and so we are looking at integers of the form $6 \cdot 8^k(8^{2k}+ m)$. Hence we would like to prove that given any sufficiently large positive integer $N$, we can find $a$ and $b$ so that $N - a^3  - b^3$ is divisible by $8^k$. This is not hard to prove since any odd number is congruent to a cube modulo $8^k$ and so with two cubes we can reach every residue. We can also choose them to be divisible by $6 \cdot 8^k$. Hence we get

$$N - a^3 - b^3 = 6 \cdot 8^k n$$

for some $n$ and we win if $n > 8^{2k}$. But we can choose $a,b$ to be less than $8^k$ so as long as $N > 8 \cdot 8^k$ we are safe. There is now a catch - we have to make sure the cubes we have are non-negative, which happens if $A > m_i$ and so we also need to guarantee that $8^k \geq m_i$. 

To do so, we let $k$ be a positive integer such that $8 \cdot 8^{3k} \leq N \leq 8 \cdot 8^{3(k+1)}$. We then choose $i$ so that $N-i^3 \geq 8 \cdot 8^{3k} \geq N - (i+1)^3$. We then have an upper bound of $11 \cdot 8^{3k} \geq N-(i-1)^3 \geq N-i^3$ too. Choosing $i$ or $i-1$ depending on the parity of $N$, we can then find two cubes so that $N - a^3 - b^3$ is between $7 \cdot 8^{3k}$ and $11 \cdot 8^{3k}$, and that it is a multiple of $8^k$. Hence we have

$$N - a^3 - b^3 = 8^k q$$

where $7 \cdot 8^{2k} \leq q \leq 11 \cdot 8^{2k}$. Now set $q = r - 6 \cdot 8^{2k}$, so that $8^{2k}\leq r \leq 5 \cdot 8^{2k}$. We then write $r = s^3 + 6t$, for some positive integer $t$. 

$$N = a^3 + b^3 + 8^k(6 \cdot 8^{2k} + r) = a^3 + b^3 + 8^k(6 \cdot 8^{2k} + s^3 + 6t) = a^3 + b^3 + (2^k s)^3 + 6 \cdot 8^k(8^{2k} + t).$$

Finally it suffices to check that $t \leq 8^{2k}$, but $t \leq \frac{r}{6} \leq \frac{5}{6} 8^{2k}$ as desired.