The Trinary Tree(s) underlying Primitive Pythagorean Triples
H. Andres Lönnemo
June 8 2000
==========
FOUNDATION
==========
I've known this a long time:
Let ( a, b, c ) be a Pythagorean Triple
a2 + b2 = c2 a,b,c > 0
Parameterize a,b,c as follows
a = q + m m,n,q > 0
b = q + n
c = q + m + n
Substitute
(q + m)2 + (q + n)2 = (q + m + n)2
Expand, cancel common terms, and take square root to get
q = sqr(2*m*n)
Thus, Pythagorean Triples can be generated by finding m,n
such that 2*m*n is a perfect square.
The following observations are offered without proof:
* If m,n are relatively prime then the Pythagorean
Triple will also be relatively prime. This is
known as a Primitive Pythagorean Triple, or PPT.
* q will always be even.
* In PPTs, either m or n must be even and the other odd
This is also true for a and b.
* q is larger than m or n or both
* q is smaller than m + n
The reverse equations are easily derived:
m = c - b
n = c - a
q = a + b - c
========================
LOOK, THEY COME IN PAIRS
========================
This is the new twist:
Traditionally, q is assumed to be the positive root. However
if you instead choose the negative root, a different Pythagorean
Triple is formed with a or b or both being negative. Discard the
sign(s) and you have a perfectly good Pythagorean Triple.
Thus each valid combination of m and n produce two Triples. Again,
if m and n are relatively prime so will be a, b and c in both Triples.
One of the triples will have all positive terms, and in the other
a or b will be negative. The c's will always have the same sign,
assumed positive without loss of generality.
The odd/even pattern in PPTs will be identical.
The Signed Primitive Pythagorean Triple will be known as the SPPT.
For example:
let m = 25 and n = 8
q = sqr( 2 * 25 * 8 ) = 20
a = q + m = 45 a' = -q + m = 5
b = q + n = 28 b' = -q + n = -12
c = q + m + n = 53 c' = -q + m + n = 13
The PPT is (45,28,53) and the SPPT is (5,-12,13) which
corresponds to a PPT of (5,12,13).
The c' value of the SPPT will always be smaller than the c value
of the PPT.
=================
TREE CONSTRUCTION
=================
The construction of the trinary tree is based on the observation
that PPTs and SPPTs always come in pairs and every valid PPT can
generate three, and only three, SPPTs simply by changing the signs
on a and b.
Start with (3,4,5) as the root node called "P".
Build a table of values:
A B C M N Q Q' A' B' C'
=== === === === === === === === === ===
PPT 3 4 5 1 2 2 -2 -1 0 1 (later)
SPPT -3 4 5 1 8 -4 4 5 12 13 PPT
SPPT 3 -4 5 9 2 -6 6 15 8 17 PPT
SPPT -3 -4 5 9 8 -12 12 21 20 29 PPT
You can now read the three child nodes from the table:
They are (5,12,13), (15,8,17) and (21,20,29) called P1, P2 and P3
respectively.
Repeat the process for each child node to build as large a tree
as you want.
For example:
A B C M N Q Q' A' B' C'
=== === === === === === === === === ===
PPT 5 12 13 1 8 4 -4 -3 4 5 SPPT
SPPT -5 12 13 1 18 -6 6 7 24 25 PPT
SPPT 5 -12 13 25 8 -20 20 45 28 53 PPT
SPPT -5 -12 13 25 18 -30 30 55 48 73 PPT
Notice that the first row points back to the parent PPT when
the sign is removed from the PPT. Also the sign pattern will
tell which branch was taken.
As you build the tree you will notice that the c's are always
increasing as you traverse from the root, that is the list of
PPTs is 'quasi-sorted' in a heap sort sense.
==================================
THE SELF ROOTED NATURE OF THE TREE
==================================
Something funny happens at the apparent parent of (3,4,5) which is (1,0,1).
Since one of the values is zero, there is only one signed variation of
the node instead of the usual three.
A B C M N Q Q' A' B' C'
=== === === === === === === === === ===
~PPT 1 0 1 1 0 0 0 1 0 1 ~PPT
~SPPT -1 0 1 1 2 -2 2 3 4 5 PPT
This tree will lead to all PPTs where a is odd and b is even, similarly
(0,1,1) will lead to all the PPTs where a is even and b is odd.
==========================
CUTTING OUT THE MIDDLE MEN
==========================
Now apply the same technique to a node in general. Once again,
assume a,b,c,m,n,q > 0
A B C M N Q Q' A' B' C'
=== === === === === === === === === ===
PPT a b c m n q -q a0 b0 c0 SPPT
SPPT -a b c m1 n1 q1 -q1 a1 b1 c1 PPT
SPPT a -b c m2 n2 q2 -q2 a2 b2 c2 PPT
SPPT -a -b c m3 n3 q3 -q3 a3 b3 c3 PPT
Processing the first child shows:
m1 = c - b
m2 = c - (-a) = c + a
q1 = (-a) + b - c (always < 0)
a1 = -q1 + m1 = (a - b + c) + (c - b) = a - 2*b + 2*c
b1 = -q1 + n1 = (a - b + c) + (c + a) = 2*a - b + 2*c
c1 = -q1 + m1 + n1 = (a - b + c) + (c - b) + (c + a)
= 2*a - 2*b + 3*c
Putting these equations into matrix form:
(a1 b1 c1) = (a b c)( 1 2 2 ) = (a b c)*T1
( -2 -1 -2 )
( 2 2 3 )
Similar calculations yield:
(a2 b2 c2) = (a b c)( -1 -2 -2 ) = (a b c)*T2
( 2 1 2 )
( 2 2 3 )
(a3 b3 c3) = (a b c)( 1 2 2 ) = (a b c)*T3
( 2 1 2 )
( 2 2 3 )
(a0 b0 c0) = (a b c)( -1 -2 -2 ) = (a b c)*T0
( -2 -1 -2 )
( 2 2 3 )
And this is a remarkable result. It means that any Pythagorean
Triple can generate three new Triples by means of matrix
multiplications with T1, T2 and T3 with larger c's, and can
generate a signed version of a smaller c triple with a matrix
multiplication with T0. If the triple is a PPT the child
nodes will be PPTs and the T0 transform will yield a SPPT
corresponding to the parent.
=================
SPANNING THE PPTS
=================
The trinary tree covers the entire set of PPTs completely and
uniquely. The unique part is inherent from the construction of
the tree. Each node has only one unique SPPT 'mnq-twin' and
thus has only one parent.
The completely part requires a proof by contradiction. Suppose you
have a PPT which is not spanned by the tree. It would still have a
'mnq-twin' SPPT with a smaller c. And the absolute values of those
numbers would form another PPT.
This PPT can't be on the tree either or the original one would be,
and so on. Since the c's are decreasing, and are bounded by zero,
this sequence must terminate in a different 'self-parent' than
(1,0,1) or (0,1,1). Since everything is relatively prime these two
are the only two triples where q = 0, since q = 0 implies m = 0 or
n = 0 (Remember q = sqr(2*m*n)).
================================
MNQ-TWINS IN LINEAR ALGEBRA FORM
================================
T
------------------------------------>
(a b c) -----> (m n q) -----> (m n -q) -----> (a' b' c')
InvP U4 P
InvP = ( 0 -1 1 ) U4 = ( 1 0 0 ) P = ( 1 0 1 )
( -1 0 1 ) ( 0 1 0 ) ( 0 1 1 )
( 1 1 -1 ) ( 0 0 -1 ) ( 1 1 1 )
U4 * U4 = I
T = InvP * U4 * P = ( -1 -2 -2 )
( -2 -1 -2 )
( 2 2 3 )
Note, T * T = I
Proof: T * T = InvP * U4 * P * InvP * U4 * P = InvP * U4 * U4 * P
= InvP * P = I
Thus the T transform will find the 'mnq-twin' of any triple.
========================================
TREE CONSTRUCTION IN LINEAR ALGEBRA FORM
========================================
Parent -------------------------> Child
Signed Variation MNQ-Twin
PPT SPPT PPT
(a b c) -----> ( a' b' c ) -----> ( a" b" c" )
Ui T i = 1,2,3
U1 = ( -1 0 0 ) U2 = ( 1 0 0 ) U3 = ( -1 0 0 )
( 0 1 0 ) ( 0 -1 0 ) ( 0 -1 0 )
( 0 0 1 ) ( 0 0 1 ) ( 0 0 1 )
T1 = U1 * T = ( 1 2 2 )
( -2 -1 -2 )
( 2 2 3 )
T2 and T3 multiply out identically to the results in the previous
section.
================================
EIGENVECTORS AND SELF ROOTEDNESS
================================
The Eigenvectors of T are also interesting.
The characteristic equation of T is
-x3 + x2 + x - 1 = 0
Which yields roots of 1, 1, and -1. Since there is a
double root at one the eigenvectors require two parameters.
A set of corresponding eigenvectors are:
( s1, s2, s1+s2 ) and ( s3, s3, s3 )
Since (1,1,1) can never be a Pythagorean triple when multiplied
by any length (except the trivial zero), it can be discarded.
Applying the Pythagorean constraint to the first family of vectors:
(s1)2 + (s2)2 = (s1 + s2)2
s12 + s22 = s12 + 2*s1*s2 + s22
0 = 2*s1*s2
Therefore s1 = 0 or s2 = 0 or both. Both is again the trivial
solution and can be discarded. That leaves two vectors:
( s1, 0, s1 ) and ( 0, s2, s2 ) which reduce to ( 1, 0, 1 )
and ( 0, 1, 1 ) when relative primeness is introduced.
These are precisely the two self rooted triplets that lead to
all the odd/even/odd and even/odd/odd PPTs respectively.
====================
AN INTERESTING TWIST
====================
Reversing the first two rows of T has the effect of swapping
the odd/even pattern of a and b. This has the effect of
making (1 0 1) the parent of (0 1 1) and vice versa. So instead
of two separate self rooted trees, you get sort of 'Siamese'
trees joined at the head where the tiers alternate between even/odd
and odd/even triples.
The eigenvalues of this matrix are -1, -1, and 1 with
eigenvectors:
( s1, s2, (s1+s2)/2 ) and (1,1,2)
Applying the Pythagorean constraint to these shows no real
solutions possible. Therefore there can be no other
self-rooted trees based on this matrix.
This article has a nice sequel.
- Proof of the formula
- Norm of Gaussian integers
- Gaussian integers
- Divisibilty in Pythagorean Triples
- The Trinary Tree(s) underlying Primitive Pythagorean Triples
- Pythagorean Triples and Perfect Numbers
|Contact| |Front page| |Contents| |Algebra|
Copyright © 1996-2018 Alexander Bogomolny
72106500