Geodesic Diophantine Boxes

```Do there exist rectangular solids with integer edge lengths such
that all three geodesic distances between opposite vertices are also
integers?  Herman Baer noted the three solutions (108,357,368),
about such solutions.  This is an interesting problem - one that you'd
think would have been considered before - but I haven't been able to
find any reference to this particular set of Diophantine equations.
Dave Rusin responded to Baer with some additional solutions, such as
(243984,675500,689613).  I was curious to know how many primitive
solutions exist between the three small examples and this larger one.

To review, the problem is to find a rectangular box with integer
dimensions AxBxC such that all the (locally) geodesic paths on the
surface of the box from one corner to the diagonally opposite corner,
as shown below, have integer lengths. (We exclude the infinitely
many geodesic paths that enter any face more than once.)

___________end
/          /\
/          /  \
/          /    \
B/          /     /
/          /     /
/          /     /
/          /     /
/__________/     /
\          \    /
A\          \  /
\__________\/
start   C

Clearly any geodesic path on the surface must be a straight line on
any given wall, so if we "unfold" the box in various ways and lay all
the sides out flat, the geodesic paths are just the straight lines
connecting opposite corners, as illustrated below (where "s" indicates
the starting corner and e1,e2,e3 are the three basic positions of the
ending corner for the three different ways of unfolding the box.

|  A  |
_  __________e1
|          |
A |          |
_ |__________|_____e2
|          |     |
|          |     |
|          |     |
B |          |     |
|          |     |
|          |     |
|          |     |
_s|__________|_____|____________
|          |                  |
A |          |                  |
_ |__________|__________________|
e3
|    C     |        B         |

From this we see that the three locally geodesic path lengths x,y,z
are related to the edge lengths A,B,C according to the equations

x^2 = (A+B)^2 + C^2

y^2 = (A+C)^2 + B^2

z^2 = (B+C)^2 + A^2

So, the task is to find integers A,B,C,x,y,z that satisfy all three
of these equations simultaneously.  If we re-write these equations in
the form

2ab + D2 = x^2       2ac + D2 = y^2      2bc + D2 = z^2

where D2 is the squared length of the main diagonal of the box (which
we don't require to be a square integer), this Diophantine problem
bears some resemblence to a class of problems considered by Diophantus
himself, namely, to find three numbers such that their products in
pairs increased by a constant are each squares.  In other words,
Diophantus considered the set of simultaneous equations (in rational
numbers)

ab + k = x^2      ac + k = y^2      bc + k = z^2

The case k=1 in particular has been studied extensively, and extended
to sets of four, and even five (rational) numbers whose products in
pairs are 1 less than squares.  This was studied by Euler and many
others.  However, the Diophantine box problem is a bit trickier,
because it asks us to find three integers such that TWICE each pair-
wise product, increased by the sum of of the squares, is a square.
I'm not sure if the classical methods used to solve Diophantus'
original system of equations can be adapted to treat this problem,
but we can say a few things about the integer S = A+B+C that makes
searching for solutions a bit easier.  Obviously each of the
conditions corresponds to a Pythagorean triple which can be
parameterized in the usual way, i.e.,

(ku^2 - kv^2)^2  +  (2kuv)^2   =  (ku^2 + kv^2)^2

where u,v are coprime (one odd, one even).  Now, S = A+B+C is the sum
of the two terms on the left, so essentially the conditions of the
problem require that S for a solution be expressible in the form

(u^2 - v^2)  +  (2uv)

in (at least) three distinct ways.  Equivalently, S must have at least
three distinct representations of the form (u+v)^2 - 2v^2.  Thus, we
are dealing with the number field Q[sqrt(2)], which possesses unique
factorization.  By Fermat's "Christmas theorem" we know that S must be
a product of at least two primes of the form X^2 - 2Y^2, and probably
three.  Also we can see that a primitive solution must not be divisible
by any primes NOT of this form.

At first it may seem surprising that a value of S having only 2 factors
could yield a solution, because S must be expressible in THREE distinct
ways as a sum of two legs of a Pythagorean triple, viz, in the quadratic
form X^2 - 2Y^2.  Thus, we might expect that S must have at least three
prime divisors congruent to +1 or -1 (mod 8).  However, there exist
solutions such as S = (41)(17921) in which S does have just two prime
factors.  This is quite rare - the only other such solution less than
10 million is S = (89)(88001).  The reason such solutions are possible
is that not all of the Pythagorean triples are necessarily primitive,
and, furthermore, the common divisor "k" for any non-primitive triples
must be a divisor of S=pq.  As a result, we can get two of our
representations of S from the usual composition of the quadratic forms
of the two prime factors p,q of S, and then we get the 3rd representation
as p times the minimal representation of q.

In any case, the acceptable S values must be composed entirely of at
least two (and usually three) primes, not necessarily distinct, modulo
which 2 is a quadratic residue, i.e., primes congruent to +-1 modulo
8.  The first few primes of this type are

7   17   23   31   41   47   71   73   79   89   97  103... etc.

Indeed, the three smallest solutions have the S values

833 = (7)(7)(17)       2737 = (7)(17)(23)      3703 = (7)(23)(23)

In general, to find values of S that give primitive solutions we
can examine each integer and immediately exclude any that are not
composed entirely of 2 or more primes congruent to +-1 (mod 8).

Now, if two or all three of the Pythagorean triples are primitive, we
can infer the solution simply by finding two minimal representations
of S in the form  2y^2 - x^2  where 0 < x < y, which can clearly be
found by a 1-dimensional search up to sqrt(S).  Once we have found
these minimal representations, we can take them, two at a time, to
see if they give a valid solution.

For example, the minimal representations of 833 in the form 2y^2 - x^2
are (x,y) = (7,21), (15,23), and (25,27), and these are converted to
(u,v) parameterizations of the respective Pythagorean triples by

u  =  y             v  =  y - x

Taking the 2nd and 3rd minimal forms gives the triples

u    v     u^2 - v^2    2uv
---  ---    ---------  -------
23   8        465       368
27   2        725       108

Recalling that our three triples are of the form (A+B,C), (A+C,B), and
(B+C,A), it's clear that if this is a solution then we must have A=108,
B=368, and C = 465-108 = 725-368 = 357, and we can easily verify that
this is, in fact, a solution.

On the other hand, if our solution involves two (or more) non-primitive
Pythagorean triples, the above method won't work, because the primitive
triples are based on the minimal forms of the entire S, whereas the
non-primitive triples are based on the minimal forms of proper FACTORS
of S.  So, to find such solutions we need to proceed as before, but
now we need to include, in addition to the minimal representations of
S, the representations of the form n(2y^2 - x^2) where n is any proper
divisor of S.  For any divisor n we find the minimal form(s) of S/n,
convert them to (u,v) paramaters as above, and then the resulting
Pythagorean legs are n(u^2 - v^2) and 2nuv.  We can then check these
purported triples in pairs as above to determine if they give three
suitable triples.

A table showing all 79 primitive solutions with S less than 50 million
is presented in

Attachment: Table of Geodesic Boxes

Obviously if (A,B,C) is a solution then so is (kA,kB,kC) for any integer
k, so we've considered only the "primitive" solutions, i.e., those for
which  gcd(A,B,C) = 1.  Now, each primitive solution leads to the three
Pythagorean triples

(A+B)^2 + C^2  =  x^2
(A+C)^2 + B^2  =  y^2
(B+C)^2 + A^2  =  z^2

where x,y,z are the three geodesic path lengths.  Notice in the attached
table that almost all the solutions less than 3 million  have two primitive
Pythagorean triples.  For example, the smallest solution is

S       A       B       C       (prime factors of S)
A+B      C       x             k1      u1      v1
A+C      B       y             k2      u2      v2
B+C      A       z             k3      u3      v3

=  833     108     357     368       (7)(7)(17)
465     368     593             1      23       8
476     357     595           119       2       1
725     108     733             1      27       2

and we note that two of the three Pythagorean triples are primitive, but
one is just the simple 3^2 + 4^2 = 5^2 triple multiplied by 119.  (Oddly
enough, the larger solution found by Rusin by means of elliptic curves
also involved a multiple of the 3^2 + 4^2 = 5^2 triple.)  Most of the
solutions are of this type, i.e., two primitive triples and one non-
primitive triple, but there are also solutions in which only one of the
Pythagorean triples is primitive, such as

1228687  112812  431955  683920       (79)(103)(151)
544767  683920  874367           103      83      40
796732  431955  906293             1     818     487
1115875  112812 1121563            79     119       6

Furthermore, there are even primitive geodesic boxes for which NONE of
the Pythagorean triples is primitive, including

2627639  337824  516260 1773555       (7)(17)(71)(311)
854084 1773555 1968491             7     517     118
2111379  516260 2173579           311      83      10
2289815  337824 2314601            17     368      27

In addition, the table also shows that we have some "ultra-primitive"
geodesic boxes, i.e., primitive geodesic boxes such that all three
Pythagorean triples are also primitive.  The smallest example of
this is

2107609  312040  587340 1208229       (7)(17)(89)(199)
899380 1208229 1506221             1    1165     386
1520269  587340 1629781             1    1255     234
1795569  312040 1822481             1    1345     116

which has the dimensions A=312040, B=587340, C=1208229.  The geodesic
path lengths for this box are given by three primitive Pythagorean
triples as

x = (1069)(1409)        y = (197)(8273)       z = (1822481)

and the sum of the edge lengths is

S  =  A+B+C  =  2107609  =  (7)(17)(89)(199)

There are a total of 8 ultra-primitive geodesic boxes with S less
than 50 million, as shown in the table.

Having found three-dimensional boxes of size AxBxC such that the edge
lengths and all three geodesic path lengths connecting opposite
vertices are integers, it's interesting to consider the analagous
question for 4-dimensional boxes.  First, note that for a 2D box of
size AxB there is essentially just one geodesic distance S along the
surface connecting opposite corners, given by

S^2 = (A+B)^2

In other words, the distance is simply A+B.  For a 3D box of size
AxBxC there are three local geodesic distances, given by

S1^2  =  (A+B)^2 + C^2
S2^2  =  (A+C)^2 + B^2
S3^2  =  (B+C)^2 + A^2

The usual way of seeing this is to simply unfold the box and draw the
straight lines connecting opposite corners, be we could also deduce
this more formally by noting that we're required to go from the point
[0,0,0] to the point [A,B,C] in the minimum linear segments, each of
which is on (at least) one surface of the box.  In other words, every
segment must have at least one of the components at its min or max
limit (0 or A,B,C respectively) for the entire segment.  So the
shortest path must be of the form

[0,0,0]   ->   [A,0,t]   ->   [A,B,C]

Notice that for the first segment the 2nd coordinate is always 0,
whereas for the second segment the 1st coordinate is constantly A,
so both segments are on the surface.  The total length of this path

S   =   sqrt(A^2 + t^2)  +  sqrt(B^2 + (C-t)^2)

Differentiating with respect to t and setting the result to zero, we
find that t = AC/(A+B), which can be substituted back into the above
equation to give the expected result

S^2  =  (A+B)^2 + C^2

Now, for a 4-dimensional box we need to go from [0,0,0,0] to
[A,B,C,D] via the most economical path on the surface.  In this
case the "surface" consists of 8 solid regions in which three of
the coordinates are anywhere between their min and max while the
fourth coordinate is at its min or max.  Again we can visualize
this by "unwrapping" the box, placing two of the faces adjacent
to each other.  For example, if we unfold a face with dimensions
AxCxD into the same 3D space as a face of dimensions BxCxD we have
a solid with overall dimensions (A+B)xCxD, and the shortest path
connecting the two opposite corners has length S given by

S^2   =   (A+B)^2 + C^2 + D^2

Likewise for the other face combinations.  Alternatively, we can
proceed more formally by considering the path

[0,0,0,0]   ->   [A,0,u,v]   ->   [A,B,C,D]

whose total length is

S = sqrt[A^2 + u^2 + v^2]  +  sqrt[B^2 + (C-u)^2 + (D-v)^2]

Here we have two unknown paramaters, so we differentiate with
respect to each of them separately to give the two conditions

dS/du  =  0           dS/dv  =  0

Solving these simultaneous equations for u and v gives

u = AC/(A+B)      v = AD/(A+B)

Substituting these back into the preceeding expression gives the
expected result S^2 = (A+B)^2 + C^2 + D^2.  In general, if the edge
lengths of an n-dimensional rectangular box are E1, E2,..,En then
the lengths of the geodesics connecting opposite vertices on the
surface are of the form

S^2 = (E1+E2)^2 + E3^2 + E4^2 + ... + En^2

for all n(n-1)/2 distinct permutations of the edges.  Thus, for the
case of a 4-dimensional box we have six distinct geodesic lengths

S1^2   =   (A+B)^2 + C^2 + D^2
S2^2   =   (A+C)^2 + B^2 + D^2
S3^2   =   (A+D)^2 + B^2 + C^2
S4^2   =   (B+C)^2 + A^2 + D^2
S5^2   =   (B+D)^2 + A^2 + C^2
S6^2   =   (C+D)^2 + A^2 + B^2

So, the question is whether there exist 4-tuples of integers
A,B,C,D such that all six of these lengths are integers.  It's
interesting that this can be expressed in terms very similar to
the ancient Diophantine problem of finding four numbers whose
six pairwise products increased by a constant n are all squares.
However, in this case we need to consider TWICE the pairwise
products, because we have

S1^2   =   2AB + K
S2^2   =   2AC + K
S4^2   =   2BC + K
S5^2   =   2BD + K
S6^2   =   2CD + K

where K = A^2 + B^2 + C^2 + D^2 is the squared main diagonal.  The
problem involving just the pairwise products (without the factor
of 2) was treated by Euler, but unfortunately the method he used
is not applicable when the factor of 2 is included (because it
relies on being able to set 4 - y^2 to zero with a rational number
y, but this term becomes 8 - y^2 when the factor of 2 is included).
I haven't found any non-trivial integer solutions to this set of
equations.  Does anyone know of any solutions?  Or a proof that
such solutions are impossible?

By the way, just for fun, we might consider the general ways in
which a sum of squares can be defined on a 4-part partition of a
given number S = A+B+C+D.  We have the following possibilities

Number of distinct values
Form                        under permutations of A,B,C,D
-------------------------------   -----------------------------

(A)^2 + (B)^2 + (C)^2 + (D)^2             1
(A+B)^2 + (C)^2 + (D)^2                   6
(A+B+C)^2 + (D)^2                         4
(A+B)^2 + (C+D)^2                         3
(A+B+C+D)^2                               1

Since every number is expressible as a sum of four squares, it's
clear that the first form, which is invariant under permutations,
can be set equal to a square.  Also, the last form is invariant
and is automatically a square.  In addition, it's not hard to find
sets of integers [A,B,C,D] such that all 4 of the permutations
of the 3rd form are squares, as shown by [189,1032,564,952], which
gives
(189+1032+564)^2 + (952)^2 = (2023)^2
(189+1032+952)^2 + (564)^2 = (2245)^2
(189+564+952)^2 + (1032)^2 = (1993)^2
(1032+564+952)^2 + (189)^2 = (2555)^2

(Notice that this solution has S = 189+1032+564+952 = 2737, which
is the 2nd smallest S value for solutions of the 3D box problem.)
In addition, we can find integers A,B,C,D such that all three of the
permutations of the 4th form are squares, as shown by [23,47,55,113],
which gives
(23+47)^2 + (55+113)^2  =  (182)^2
(23+55)^2 + (47+113)^2  =  (178)^2
(23+113)^2 + (47+55)^2  =  (170)^2

So it's easy to find solutions for all of the forms EXCEPT the one
that gives the geodesic lengths of a 4D box, which is clearly the
most stringent because it imposes SIX Diophantine conditions on
four numbers.

Regarding the 3D case, all the solutions for S=A+B+C less than 50
million were given above, including eight "ultra-primitive" solutions.
Only one solution for each S is listed, and I think in most cases it
is the ONLY solution.  The only exception to this for S less than 1
million is S=82943, which actually has two solutions

82943 =  6647 + 33228 + 43068
= 13940 + 31155 + 37848

Multiple representations of other forms seem to be more common.
For example, the number 1666 can be partitioned into four parts
A,B,C,D in 15 distinct ways such that (A+B)^2 + (C+D)^2 is a
square for all the permutations of those four parts (although
only one of them, 137+353+577+599, involves just prime numbers).
```