Background
I've been working a lot recently with the sums of squares (I have a previous post about finding the Exhaustive List of the Sums of Four-Squares). This work has been for some research and also for Project Euler. However, I came across an interesting result: If $n$ is even and $a^2 + b^2 + c^2 = n^2$, then $a,b,$ and $c$ are also even.To kind of tip-toe around the issue, we know that there is at least one solution $a,b,c$ such that this is true: $a=n, b=c=0$. Others may and do exist, but we won't fret too much right now about what they are. All we need to know is that there is at least one solution. Since all natural numbers are either even or odd, we have four possibilities: all $a,b,c$ are odd, two are odd and one is even, one is odd and two are even, or all three are even.
We can easily rule out the case for which one is odd and three are odd. Because we know $n$ is even, $n^2$ must also be even. However, there are an odd number of odds on the other side (remember an odd squared is still odd), which means the entire other side is odd. And, since an odd cannot equal an even, we have a contradiction. However, in order to eliminate the case where two are odd, we must do a little more work.
Assume, without loss of generality, that $a$ and $b$ are odd and $c$ is even and we will prove a contradiction. Let $d,e,f,g\in\mathbb{N}$ be such that $$\begin{array}{c} a = 2d + 1 \\ b = 2e + 1 \\ c = 2f \\ n = 2g \end{array} $$ We know that. $$n^2 = (2g)^2 = 4g^2$$ And we know that $$\begin{array}{r l} n^2 &= a^2 + b^2 + c^2 \\ &= (2d+1)^2 + (2e+1)^2 + (2f)^2 \\ & = 4d^2 + 4d + 1 + 4e^2 + 4e + 1 + 4f^2 \\ &= 4(d^2 + d + e^2 + e + f^2) + 2 \end{array}$$ Putting the two together: $$4g^2 = 4(d^2 + d + e^2 + e + f^2) + 2$$ Clearly, the left hand side is a multiple of $4$, however, the righthand side is not. Therefore, these two cannot be equal and we cannot have two odd squares to sum. We won't try to eliminate the last possibility (that all three be even) because we know that at least one solution exists and it has to fall into one of those categories.
Now, this probably doesn't seem like that interesting of a result. And honestly speaking, it's really not particularly interesting. However, we can generalizes this:
Theorem
Proof
For $k=1$, this simplifies to the above proof and $k=0$ is trivial. As such, we have base cases and we will proceed by induction. So, we assume that if $2^{k-1}\vert n$ for some $k\in \mathbb{N}$ and $a^2 + b^2 + c^2 = n^2$, then $2^{k-1}\vert a,b,c$. Now assume that $2^k\vert n$ and that $a^2 + b^2 + c^2 = n^2$. We know that there exists $m$ such that $n=2^km$. We also can show that $$n = 2^km = 2^{k-1}(2m)$$ which means that $2^{k-1}\vert n$. And, since $a^2 + b^2 + c^2 = n^2$ by our induction hypothesis, we can conclude that $2^{k-1}\vert a,b,c$. This implies there exists $i,j,l\in \mathbb{N}$ such that $$\begin{array}{c} a = 2^{k-1}i \\ b = 2^{k-1}j \\ c = 2^{k-1}l \\ \end{array}$$ We can now classify $a,b,c$ based on the respective parity of $i,j,l$ (because again, $i,j,l$ must either be even or odd). We, again, have four possibilities: all three are odd, two are odd and one is even, one is odd and two are even, and all three are even.Case 1
Assume that all three are odd. Therefore, there exists $i_0, j_0, l_0$ such that $$\begin{array}{c} i = 2i_0 + 1 \\ j = 2j_0 + 1 \\ l = 2l_0 + 1 \end{array}$$ and furthermore $$\begin{array}{c} a = 2^{k-1}(2i_0 + 1) = 2^ki_0 + 2^{k-1} \\ b = 2^{k-1}(2j_0 + 1) = 2^kj_0 + 2^{k-1} \\ c = 2^{k-1}(2l_0 + 1) = 2^kl_0 + 2^{k-1} \\ \end{array}$$ Consider $$\begin{array}{r l} n^2 &= a^2 + b^2 + c^2 \\ & = (2^ki_0 + 2^{k-1})^2 + (2^kj_0 + 2^{k-1})^2 + (2^kl_0 + 2^{k-1})^2 \\ &= 2^{2k}(i_0^2+i_0+j_0^2+j_0+l_0^2+l_0) + 3(2^{2k-2}) \\ \end{array}$$ Note that this is not divisible by $2^{2k}$ because of the last term. On the contrary, note that $$n^2 = (2^km)^2 = 2^{2k}m^2$$ and therefore $2^{2k}\vert n^2$; a contradiction. Therefore, all three cannot be odd.Case 2
Assume that two are odd and one is even. Therefore there exists $i_0,j_0, l_0$ such that $$\begin{array}{c} i = 2i_0 + 1 \\ j = 2j_0 + 1 \\ l = 2l_0 \end{array}$$ As before, we can substitute and write $a,b,c$ in terms of $i_0, j_0,l_0$ and as a result $n^2$ in terms of $i_0, j_0,l_0$. $$n^2 = 2^{2k}(i_0^2+i_0+j_0^2+j_0+l_0^2) + 2(2^{2k-2})$$ Note that this is not divisible by $2^{2k}$ because of the last term only having a factor of $2^{2k-1}$. But again, because know that $2^{2k}\vert n^2$ we have a contradiction. Therefore, two cannot be odd.Case 3
Assume that one is odd and two are even. Therefore there exists $i_0,j_0, l_0$ such that $$\begin{array}{c} i = 2i_0 + 1 \\ j = 2j_0 \\ l = 2l_0 \end{array}$$ Once again, we can substitute and write $n^2$ in terms of $i_0, j_0,l_0$. $$n^2 = 2^{2k}(i_0^2+i_0+j_0^2+l_0^2) + 2^{2k-2}$$ Note that this is not divisible by $2^{2k}$ because of the last term. And again, because know that $2^{2k}\vert n^2$ we have a contradiction. Therefore, one cannot be odd.Case 4
That only leaves the option that all three are even. Since $i,j,k$ are even, and we have $i_0,j_0, l_0$ such that $$\begin{array}{c} i = 2i_0 \\ j = 2j_0 \\ l = 2l_0 \end{array}$$ we can now write $$\begin{array}{c} a = 2^{k-1}(2i_0) = 2^ki_0 \\ b = 2^{k-1}(2j_0) = 2^kj_0 \\ c = 2^{k-1}(2l_0) = 2^kl_0 \\ \end{array}$$ and we have shown that $2^k\vert a,b,c$!Implications
What does this mean, though? It means that if we want to find the three integers whose squares sum to $n^2$(such as lattice points on a sphere), then we can omit multiples of two from our search and work with smaller numbers. This saves a great deal of computing time.For instance, if we know that $2^k\vert n$ and we want to find $a,b,c$ such that $n^2 = a^2+b^2+c^2$, we can really just search for $d,e,f$ such that $m^2=d^2+e^2+f^2$ ($n = 2^km$). We jump back to the original problem by multiplying by $2^{2k}$ on both sides: $$\begin{array}{r l} m^2 & = d^2 + e^2 + f^2\\ 2^{2k}m^2 & = 2^{2k}(d^2 + e^2 + f^2) \\ (2^km)^2&= 2^{2k}d^2 + 2^{2k}e^2 + 2^{2k}f^2 \\ n^2 & = (2^kd)^2 + (2^ke)^2 + (2^kf)^2\\ n^2 & = a^2 + b^2 + c^2 \end{array} $$ Where clearly $d,e,f$ is the respective result of the division of $a,b,c$ by $2^k$.
This is really clever, man.
ReplyDelete