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.
Return to MathPages Main Menu