# Which integers are the areas of squares with vertices in the 3d integer lattice?

For which integers $n$ does there exist a square of area $n$ with vertices in the 3d integer lattice $\mathbb{Z}^3$?

A sufficient condition is that $n$ is a square or the sum of two squares, and I have verified that the condition is also necessary when $n < 10^5$.

Edit: This question was posed by James Tanton on Twitter. I thought it was very interesting, so I took the liberty of posting it here.

Edit 2: I have extended the search to $n < 10^6$ without finding any counterexamples.

-
A related result: Richard Parris proved that if a cube has all of its vertices in $\mathbb{Z}^3$ then the edge length is an integer. jstor.org/pss/10.4169/college.math.j.42.2.118 – Dave Radcliffe Jul 30 '11 at 3:58
Errr... sorry, that looked different in my head. :( – anon Jul 30 '11 at 4:03
Does this appear in the Online Encyclopedia of Integer Sequences? – Michael Hardy Jul 30 '11 at 15:59
The sequence appears to agree with oeis.org/A001481, numbers that are the sum of two nonnegative squares. – Dave Radcliffe Jul 30 '11 at 16:10
@Dave R: Actually, Richard Parris' result is a corollary of this result. Translating one of the vertices to the origin, we have three mutually perpendicular vectors, $\vec{u}$, $\vec{v}$, and $\vec{w}$, in $\mathbb{Z}^3$, each of length $\sqrt{s}$ where $s=m^2+n^2$. Now we can rotate $\vec{u}$, $\vec{v}$, and $\vec{u}\times\vec{v}$ to $(m,n,0)$,$(-n,m,0)$, and $(0,0,s)$ by a unitary matrix with rational entries. That same matrix takes $\vec{w}$ to $(0,0,\sqrt{s})$. Since the entries in the matrix are rational and $\vec{w}$ is in $\mathbb{Z}^3$, $\sqrt{s}$ must be rational, hence an integer. – robjohn Aug 2 '11 at 17:48

Translate one of the vertices to the origin, then the two adjacent vertices of the square are $(x,y,z)$ and $(u,v,w)$ where $x^2 + y^2 + z^2 = u^2 + v^2 + w^2 = s$ and $xu + yv + zw = 0$, and the area of the square is $s$. Now consider \begin{align} (xw-uz)^2 + (yw-vz)^2 &=x^2w^2 - 2xwuz + u^2z^2 + y^2w^2 - 2ywvz + v^2z^2\\ &=(x^2 + y^2)w^2 + (u^2 +v^2)z^2 - 2(xu+yv)wz\\ &=(x^2 + y^2)w^2 + (u^2 +v^2)z^2 + 2(zw)wz\\ &=(x^2 + y^2 + z^2)w^2 + (u^2 +v^2+w^2)z^2\\ &=s(w^2+z^2) \end{align} Since a number is a sum of two squares if and only if each prime factor of that number that is equal to $3\pmod{4}$ occurs with even exponent, all prime factors of $(xw-uz)^2 + (yw-vz)^2$ and $w^2+z^2$ equal to $3\pmod{4}$ occur with even exponent, thus each prime factor of $s$ equal to $3\pmod{4}$ must also occur with even exponent. Therefore, $s$ is a sum of two squares.

-
Nice. Of course, when you write "sum of squares" you mean "sum of two squares". – Gerry Myerson Aug 2 '11 at 7:09
@Gerry Myerson: yes, and it is now so noted in the answer. Thanks. – robjohn Aug 2 '11 at 7:12
+1 Very nice, indeed! Did you know of this identity in advance? Looks like it might have made an appearance when you play with the proof leading to the formula relating the length of the cross product of two vectors to their lengths and their inner product. – Jyrki Lahtonen Aug 2 '11 at 7:44
@Jyrki Lahtonen: No, I did not know it before. I was canceling the third coordinate with $(x,y,z)w-(u,v,w)z=(xw-uz,yw-vz,0)$ and realized that the square of the length of the left side was $(w^2+z^2)s$ and the square of the length of the right side was $(xw-uz)^2+(yw-vz)^2$. – robjohn Aug 2 '11 at 7:52
Simpler than I thought. Thanks. – Jyrki Lahtonen Aug 2 '11 at 8:00

This is equivalent to integers $\{x_i, y_i, z_i\}$ for $i = 0, 1, 2, 3$ satisfying:

$(x_i - x_{i+1})^2 + (y_i - y_{i+1})^2 + (z_i - z_{i+1})^2 = A$ (the area)

$(x_i - x_{i+1})(x_{i+1} - x_{i+2}) + (y_i - y_{i+1})(y_{i+1} - y_{i+2}) + (z_i - z_{i+1})(z_{i+1} - z_{i+2}) = 0$

(taking $i+1$ and $i+2$ mod 4)

So because a non-negative integer is the sum of three squares of integers if and only if it is not of the form $4^m(8 n + 7)$, a necessary condition is that the area A is not of that form. Your conditions satisfy this, as they require odd primes of odd multiplicity to be $\equiv 1 \bmod 4$, so that the area (according to your conditions) must be of the form $4^m(4 n + 1)$.

But the three squares condition doesn't in itself rule out primes $\equiv 3 \bmod 4$ occuring to odd multiplicity, and if you try larger values perhaps some examples of this will turn up.

Edit: I just had another thought - The area would be of the form $4^m(8 n + 3)$ if and only if all the differences $x_i - x_{i+1}$, $y_i - y_{i+1}$, etc were odd. But in that case, the "orthogonality" conditions would not be satisfied, because the LHS would be the sum of three odd integers and hence odd and non-zero. So in summary, the area must be of the form $4^m(8 n + 1)$

However, that still leaves a loophole to evade your conditions: A non-negative integer is the sum of the squares of two integers if and only if it contains no prime $\equiv 3 \bmod 4$ to odd multiplicity. (Of course a square is a special case of this, with one of the two integers zero.) But the $8 n + 1$ area condition above doesn't exclude an even number of primes $\equiv 3 \bmod 4$ each occurring to odd multiplicity, which would preclude a sum of two squares form.

-
Does this appear in the Online Encyclopedia of Integer Sequences? – Michael Hardy Jul 30 '11 at 15:58
You only need six variables and three equations to describe this problem (place one of the vertices of the square at the origin; then the two adjacent vertices determine the last one). – Qiaochu Yuan Jul 30 '11 at 17:07

With Qiaochu's observation, one can find a general parametric solution to this problem, starting from:

$a^2 + b^2 + c^2 = d^2 + e^2 + F^2$

$a d + b e + c F = 0$

Start by forgetting about integers for now, and dividing both equations by $c^2$, and considering $a, b, d, e, F$ as rational. In other words, in effect take $c = 1$.

Then plugging $- F = a d + b e$ into the first gives a result equivalent to:

$(a^2 + 1) d^2 + 2 a b d e + (b^2 + 1) e^2 = a^2 + b^2 + 1$

Multiplying throughout by $a^2 + 1$, this can be expressed in the form:

$((a^2 + 1) d + a b e)^2 = (a^2 + 1 - e^2) (a^2 + b^2 + 1)$

Letting:

$(a^2 + 1) d + a b e = (a^2 + b^2 + 1) f$

this becomes:

$a^2 + 1 - e^2 = (a^2 + b^2 + 1) f^2$

or equivalently:

$(a^2 + 1) (1 - f^2) = e^2 + (b f)^2$

It isn't hard to prove that this implies the existence of rational $g, h$ with:

$1 - f^2 = g^2 + h^2$

whence by composition:

$e^2 + (b f)^2 = (a g + h)^2 + (a h - g)^2$

This in turn implies the existence of rational $u, v$ with:

$u^2 + v^2 = 1$

such that again by composition:

$e = u (a g + h) + v (a h - g)$

$b f = v (a g + h) - u (a h - g)$

Now $f^2 + g^2 + h^2 = 1$ has general solution:

$f = \frac{p^2 + q^2 - 1}{p^2 + q^2 + 1}$

$g = \frac{2 p}{p^2 + q^2 + 1}$

$h = \frac{2 q}{p^2 + q^2 + 1}$

and $u^2 + v^2 = 1$ of course has general solution:

$u = \frac{r^2 - 1}{r^2 + 1}$

$v = \frac{2 r}{r^2 + 1}$

So plugging these two solutions into the preceding equations for $e$ and $b f$ expresses $b$ and $e$ in terms of $a, p, q, r$.

Also plugging these two solutions, and $b$ and $e$ just obtained, into the equation (near the start) where $f$ was introduced, expresses $d$ in terms of $a, p, q, r$.

Finally, $F$ follows from $- F = a d + b e$.

Then simply homogenize to obtain equations giving all integer solutions.

I later realized that the above, although correct, is suboptimal.

Solving $a^2 _+ b^2 + 1 = d^2 + e^2 + (a d - b e)^2$, as we did, by expressing $b, d, e$ in terms of $a$ and parameters should require only 2 parameters instead of our 3.

This mystery can be resolved by observing that $u^2 + v^2 (= 1)$ can be absorbed by composition into $g^2 + h^2$. So with a pair of new parameters $G, H$, with $1 - f^2 = G^2 + H^2$ we can conclude:

$e = a G + H$

$b f = a H - G$

and $b, d, e, F$ can each now be expressed in terms of $a, G, H$

-