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.

Solution 1:

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.

Solution 2:

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.

Solution 3:

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$