## 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:  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 vertices 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 vertices 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.
```