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.

Pythagorean triples

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

72109833