Tree of primitive Pythagorean triples

Berggrens's tree of primitive Pythagorean triples.

A tree of primitive Pythagorean triples is a mathematical tree in which each node represents a primitive Pythagorean triple and each primitive Pythagorean triple is represented by exactly one node. In two of these trees, Berggren's tree and Price's tree, the root of the tree is the triple Template:Math, and each node has exactly three children, generated from it by linear transformations.

A Pythagorean triple is a set of three positive integers Template:Mvar, Template:Mvar, and Template:Mvar having the property that they can be respectively the two legs and the hypotenuse of a right triangle, thus satisfying the equation $a^2+b^2=c^2$; the triple is said to be primitive if and only if the greatest common divisor of Template:Mvar, Template:Mvar, and Template:Mvar is one. With primitive Pythagorean triples, Template:Mvar, Template:Mvar, and Template:Mvar are also pairwise coprime. The set of all primitive Pythagorean triples has the structure of a rooted tree, specifically a ternary tree, in a natural way. This was first discovered by B. Berggren in 1934.

F. J. M. Barning showed that when any of the three matrices

$\begin{array}{ccc}A=\left[\begin{array}{ccc}1& -2& 2\\ 2& -1& 2\\ 2& -2& 3\end{array}\right]& B=\left[\begin{array}{ccc}1& 2& 2\\ 2& 1& 2\\ 2& 2& 3\end{array}\right]& C=\left[\begin{array}{ccc}-1& 2& 2\\ -2& 1& 2\\ -2& 2& 3\end{array}\right]\end{array}$

is multiplied on the right by a column vector whose components form a Pythagorean triple, then the result is another column vector whose components are a different Pythagorean triple. If the initial triple is primitive, then so is the one that results. Thus each primitive Pythagorean triple has three "children". All primitive Pythagorean triples are descended in this way from the triple Template:Math, and no primitive triple appears more than once. The result may be graphically represented as an infinite ternary tree with Template:Math at the root node (see classic tree at right). This tree also appeared in papers of A. Hall in 1970 and A. R. Kanga in 1990. In 2008 V. E. Firstov showed generally that only three such trichotomy trees exist and give explicitly a tree similar to Berggren's but starting with initial node Template:Math.

Proofs

Presence of exclusively primitive Pythagorean triples

It can be shown inductively that the tree contains primitive Pythagorean triples and nothing else by showing that starting from a primitive Pythagorean triple, such as is present at the initial node with Template:Math, each generated triple is both Pythagorean and primitive.

Preservation of the Pythagorean property

If any of the above matrices, say Template:Mvar, is applied to a triple Template:Math having the Pythagorean property Template:Math to obtain a new triple Template:Math, this new triple is also Pythagorean. This can be seen by writing out each of Template:Mvar, Template:Mvar, and Template:Mvar as the sum of three terms in Template:Mvar, Template:Mvar, and Template:Mvar, squaring each of them, and substituting Template:Math to obtain Template:Math. This holds for Template:Mvar and Template:Mvar as well as for Template:Mvar.

Preservation of primitivity

The matrices Template:Mvar, Template:Mvar, and Template:Mvar are all unimodular—that is, they have only integer entries and their determinants are ±1. Thus their inverses are also unimodular and in particular have only integer entries. So if any one of them, for example Template:Mvar, is applied to a primitive Pythagorean triple Template:Math to obtain another triple Template:Math, we have Template:Math and hence Template:Math. If any prime factor were shared by any two of (and hence all three of) Template:Mvar, Template:Mvar, and Template:Mvar then by this last equation that prime would also divide each of Template:Mvar, Template:Mvar, and Template:Mvar. So if Template:Mvar, Template:Mvar, and Template:Mvar are in fact pairwise coprime, then Template:Mvar, Template:Mvar, and Template:Mvar must be pairwise coprime as well. This holds for Template:Mvar and Template:Mvar as well as for Template:Mvar.

Presence of every primitive Pythagorean triple exactly once

To show that the tree contains every primitive Pythagorean triple, but no more than once, it suffices to show that for any such triple there is exactly one path back through the tree to the starting node Template:Math. This can be seen by applying in turn each of the unimodular inverse matrices Template:Math, Template:Math, and Template:Math to an arbitrary primitive Pythagorean triple Template:Math, noting that by the above reasoning primitivity and the Pythagorean property are retained, and noting that for any triple larger than Template:Math exactly one of the inverse transition matrices yields a new triple with all positive entries (and a smaller hypotenuse). By induction, this new valid triple itself leads to exactly one smaller valid triple, and so forth. By the finiteness of the number of smaller and smaller potential hypotenuses, eventually Template:Math is reached. This proves that Template:Math does in fact occur in the tree, since it can be reached from Template:Math by reversing the steps; and it occurs uniquely because there was only one path from Template:Math to Template:Math.

Properties

The transformation using matrix Template:Mvar, if performed repeatedly from Template:Math, preserves the feature Template:Math; matrix Template:Mvar preserves Template:Math starting from Template:Math; and matrix Template:Mvar preserves the feature Template:Math starting from Template:Math.

A geometric interpretation for this tree involves the excircles present at each node. The three children of any parent triangle “inherit” their inradii from the parent: the parent's excircle radii become the inradii for the next generation.Template:Rp For example, parent Template:Math has excircle radii equal to 2, 3 and 6. These are precisely the inradii of the three children Template:Math, Template:Math and Template:Math respectively.

If either of Template:Mvar or Template:Mvar is applied repeatedly from any Pythagorean triple used as an initial condition, then the dynamics of any of Template:Mvar, Template:Mvar, and Template:Mvar can be expressed as the dynamics of Template:Mvar in

$x_{n+3}-3x_{n+2}+3x_{n+1}-x_n=0$

which is patterned on the matrices' shared characteristic equation

${\lambda }^3-3{\lambda }^2+3\lambda -1=0.$

If Template:Mvar is applied repeatedly, then the dynamics of any of Template:Mvar, Template:Mvar, and Template:Mvar can be expressed as the dynamics of Template:Mvar in

$x_{n+3}-5x_{n+2}-5x_{n+1}+x_n=0,$

which is patterned on the characteristic equation of Template:Mvar.

Moreover, an infinitude of other third-order univariate difference equations can be found by multiplying any of the three matrices together an arbitrary number of times in an arbitrary sequence. For instance, the matrix Template:Math moves one out the tree by two nodes (across, then down) in a single step; the characteristic equation of Template:Mvar provides the pattern for the third-order dynamics of any of Template:Mvar, Template:Mvar, or Template:Mvar in the non-exhaustive tree formed by Template:Mvar.

Alternative methods of generating the tree

Using two parameters

Another approach to the dynamics of this tree relies on the standard formula for generating all primitive Pythagorean triples:

$a=m^2-n^2,$

$b=2mn,$

$c=m^2+n^2,$

with Template:Math and Template:Mvar and Template:Mvar coprime and of opposite parity (i.e., not both odd). Pairs Template:Math can be iterated by pre-multiplying them (expressed as a column vector) by any of

$\begin{array}{ccc}\left[\begin{array}{cc}2& -1\\ 1& 0\end{array}\right],& \left[\begin{array}{cc}2& 1\\ 1& 0\end{array}\right],& \left[\begin{array}{cc}1& 2\\ 0& 1\end{array}\right],\end{array}$

each of which preserves the inequalities, coprimeness, and opposite parity. The resulting ternary tree, starting at Template:Math, contains every such Template:Math pair exactly once, and when converted into Template:Math triples it becomes identical to the tree described above.

Alternatively, start with Template:Math for the root node. Then the matrix multiplications will preserve the inequalities and coprimeness, and both Template:Mvar and Template:Mvar will remain odd. The corresponding primitive Pythagorean triples will have Template:Math, Template:Math, and Template:Math. This tree will produce the same primitive Pythagorean triples, though with Template:Mvar and Template:Mvar switched.

Using one parameter

This approach relies on the standard formula for generating any primitive Pythagorean triple from a half-angle tangent. Specifically one writes Template:Math, where Template:Mvar is the tangent of half of the interior angle that is opposite to the side of length Template:Mvar. The root node of the tree is Template:Math, which is for the primitive Pythagorean triple Template:Math. For any node with value Template:Mvar, its three children are Template:Math, Template:Math, and Template:Math. To find the primitive Pythagorean triple associated with any such value Template:Mvar, compute Template:Math and multiply all three values by the least common multiple of their denominators. (Alternatively, write Template:Math as a fraction in lowest terms and use the formulas from the previous section.) A root node that instead has value Template:Math will give the same tree of primitive Pythagorean triples, though with the values of Template:Mvar and Template:Mvar switched.

A different tree

Price's tree of primitive Pythagorean triples.

Alternatively, one may also use three different matrices found by Price:

$\begin{array}{ccc}{A}^{\prime }=\left[\begin{array}{ccc}2& 1& -1\\ -2& 2& 2\\ -2& 1& 3\end{array}\right],& B^{\prime }=\left[\begin{array}{ccc}2& 1& 1\\ 2& -2& 2\\ 2& -1& 3\end{array}\right],& C^{\prime }=\left[\begin{array}{ccc}2& -1& 1\\ 2& 2& 2\\ 2& 1& 3\end{array}\right].\end{array}$

The three children produced by the set Template:Math and the children produced by the set Template:Math are not the same, but each set separately produces all primitive triples.

For example, using Template:Math as the parent, we get two sets of three children:

$\begin{array}{ccc}& [5,12,13]& \\ A& B& C\\ [45,28,53]& [55,48,73]& [7,24,25]\end{array}\begin{array}{ccc}& [5,12,13]& \\ A^{\prime }& B^{\prime }& C^{\prime }\\ [9,40,41]& [35,12,37]& [11,60,61]\end{array}$

External links

• The Trinary Tree(s) underlying Primitive Pythagorean Triples at cut-the-knot
• Frank R. Bernhart, and H. Lee Price, "Pythagoras' garden, revisited", Australian Senior Mathematics Journal 01/2012; 26(1):29-40.[1]
• Template:MathWorld