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),
(564,748,1425), and (348,975,2380), and asked for more information
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
              S3^2   =   2AD + 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).

Return to MathPages Main Menu