Pythagorean Graphs

Is it possible to fill an infinite square array with distinct
integers such that the sum of the squares of any two adjacent 
numbers is a square?  To illustrate, the following is a 4x4 
array with the desired property

           1836     105     252     735

           1248     100     240     700

            936      75     180     525

            273     560    1344    3920

Every pair of neighboring numbers (horizonally or vertically)
constitutes the legs of a Pythagorean triple.  The hypotenuses
of these triples are as shown below

               1839     273     777

            2220    145     348     1015
  
                1252    260     740

            1560    125     300      875

                 939    195     555

             975     565    1356    3955

                 623     1456    4144

The key to this problem is to recognize that the row and column
conditions are independent.  Thus, for any positive integer N we 
can easily construct a square array of size (N+1)x(N+1) consisting 
of the values 

       A[m,n] = (12/5)^m  (24/7)^n  35^N

              =  2^(2m+3n) 3^(m+n) 5^(N-m) 7^(N-n)

for m,n = 0,1,2,..,N.  These values are all integers and no
two of them have the same number of factors of 5 and 7, so
they are all distinct.

Although this gives a recipe for arbitrarily large arrays, it 
doesn't give an *infinite* array.  R. Mentock provided the
following nice construction of an infinite array.

 For m=3M+a, n=3N+b, define F(m,n) by

      F(m,n) = 6^M * 132^N * f(a,b) 

 where
 
  f(0,0) = 6 * 7
  f(0,1) = 6 * 24 
  f(0,2) = 6 * 143 
  f(1,0) = 8 * 7
  f(1,1) = 8 * 24
  f(1,2) = 8 * 143
  f(2,0) = 15* 7
  f(2,1) = 15* 24
  f(2,2) = 15* 143

 Another, shorter, solution is given by
 
 For m=2M+a, n=2N+b, define F(m,n) by
 
      F(m,n) = 10^M * 76^N * f(a,b) 

 where
 
  f(0,0) = 7 * 17
  f(0,1) = 7 * 144
  f(1,0) = 24 * 17
  f(1,1) = 24 * 144

Both of the above "infinite" solutions actually fill only one
quadrant of the plane.  To completely "tile" the plane with
Pythaogrean legs, Mentock notes that

 Each of the two solutions are actually combinations of two
 sequences, each defined along the axes.  The other points are
 just products of these, i.e., G(m,n) = G(m) * G(n).  Since we 
 have four of them, we start at zero and assign values to the 
 four semi-axes.  G(0,0) is the LCM of all G(0), and that number 
 is propogated through.  Then G(m,n) = G(m) * G(n) like above, 
 and there we go.

A slightly different approach was suggested by Dave Radcliffe,
who wrote

 Given  F(m,n) = 10^M * 76^N * f(a,b) where
 
    f(0,0) = 7 * 17
    f(0,1) = 7 * 144
    f(1,0) = 24 * 17
    f(1,1) = 24 * 144

 For m,n >= 0 define

     G(m,n)       = F(m,n) * 11 * 13
     G(-m-1,n)    = F(m,n) * 11 * 84
     G(-m-1,-n-1) = F(m,n) * 60 * 84
     G(m,-n-1)    = F(m,n) * 60 * 13   

 Since no F(m,n) is divisible by 11 or 13, G is also one-to-one. 

By the way, it's also interesting to see which polyhedra can
have distinct numbers at their verticies such that the sum of
the squares of any two adjacent numbers is a square.  Considering
just the Platonic solids, I think there is no solution for the 
tetrahedron, octahedron, or icosahedron.  Of course there are 
solutions for the cube, such as

               225--------240
               /          /|
              /          / |
            120--------160 |
             |          |  |
             |(540)     | 720
             |          | /
             |          |/
            288--------384

Here the values increase by factors of 4/3, 12/5, and 15/8 in the
three principle directions.  (Presumably it's possible to fill an
infinite 3D orthogonal lattice with distinct numbers in this way.)

This leaves only the dodecahedron.  It turns out that it is possible 
to populate the verticies of a dodecahedron with distinct numbers 
such that the sum of the squares of each pair of adjacent numbers 
is a square.  Here's an example of a "Pythagorean dodecahedron":

           a_______________________b
           /\                     /\
          /  \                   /  \
         /    \f_______q_______g/    \
        /     /        |        \     \
       /    p/         |k        \r    \
      /     /\        / \        /\     \
     /     /   \    /     \    /   \     \
    /     /      \/         \/      \     \
  e/____j/       o|         |l       \h____\c
   \     \        |_________|       /     /
     \     \     /n         m\    /     /
       \     \  /             \ /     /
         \    t\              /s     /
           \     \          /      /
             \     \      /      /
               \     \  /      /
                 \     |i    /
                   \   |   /
                     \ | /
                       d


  a =  155040   f =  649800   k =  802560   p = 2006400
  b =  290700   g = 1438965   l =  601920   q =  180576
  c =  897600   h = 3762000   m =  451440   r =  689700
  d = 1683000   i = 2613600   n =  240768   s =  846450
  e =  177650   j = 1504800   o = 1070080   t =  275880


Another related question, raised by Dave Radcliffe, is whether it
it possible to connect any two positive integers (greater than 4)
by a series of Pythagorean legs.  (As Dave put it, "consider a graph 
G with a vertex for each integer n > [4], and an edge joining 
m and n iff m^2 + n^2 is a square.  Is this graph connected?")
Notice that the numbers 3,4 are a separate graph and don't connect 
to anything else.  But for n > 4 it certainly appears to be true 
that the graph is connected.

If you look at this as a special case of the more general "connection 
criterion" m^2 + n^2 = k*square (where k is a square-free integer
expressible as a sum of two squares), it seems the case k=1 is unique
in giving a connected graph for all the integers (above some number).

In contrast, consider the graph based on m^2 + n^2 = 2*square.  In this
case the naturals split into mutually disjoint graphs, each of which is 
a multiple of the basic connected graph consisting of the numbers

  1, 7, 17, 23, 31, 41, 47, 49, 71, 73, 79, 89, 97, 103, 113, 119, ...

These are exactly the numbers whose prime factors are all congruent
to +1 or -1 modulo 8.  In other words, they are the primes p such that 
2 is a square (mod p).

The graph based on m^2 + n^2 = 5*square splits into mutually disjoint
graphs, each of which is a multiple of

 1, 2, 4, 8, 11, 16, 19, 22, 29, 31, 32, 38, 41, 44, 58, 59, 61, 62, ...

These appear to be exactly the numbers expressible as products of the 
primes 2, 11, 19, 31, 41, 59, 61, 71, 79, 89, 101, ... which I think
are the primes p such that 5 is a square (mod p).

The graph based on m^2 + n^2 = 10*square splits into disjoint graphs
that are each multiples of

  1, 3, 9, 13, 27, 31, 37, 39, 41, 43, 53, 67, 71, 79, 81, 83, ...

Again it appears there are all the products of a particular set of 
primes, in this case the primes 3, 13, 31, 37, 41, etc., and these
look like the primes modulo which 10 is a square.

So, we might be tempted to conclude that the graph of the naturals 
with the connection criterion m^2 + n^2 = k*square splits into disjoint
graphs, each of which is a multiple of a graph consisting of the
numbers expressible as a product of primes p not dividing k and such 
that k is a quadratic residue mod p.  (This explains why the case k=1 
gives just a single totally connected graph.)  However, the case k=13 
seems to behave differently.  It's basic connected set consists of

  1, 8, 12, 18, 27, 34, 51, 53, 79, 86, 92, 96, 103, 116, 122, ...

The set of primes for this case should be 2,3,13,17,23,29,43,etc. but
there seems to be something else going on here.

Return to MathPages Main Menu
Сайт управляется системой uCoz