# How to descend within the “Tree of primitive Pythagorean triples”?

It is well-known that the set of all primitive Pythagorean triples has the structure of an infinite ternary rooted tree.

What is the exact algorithm (i.e., formula, or possibly set of three formulas) by which one can take a given Pythagorean triple $(a,b,c)$ and find the immediately smaller triple in the tree? For example, given $(165,52,173)$, how does one obtain its [unique] “ancestor” triple $(77,36,85)$?

• I've done a writeup on a geometric mechanism of traversing this tree here. The exact formula is $(abs(p-2q),q)\text{ or }(q,abs(p-2q))$, assuming you are able to resolve $(a,b,c)$ to the $p,q$ generating pair. – abiessu Oct 9 '14 at 14:43
• This formula is derived directly from the reverse-direction three-way formula $(p+2q,q), (2p+q,p), (2p-q,p)$. In all these formulas, we have $(a,b,c)=(p^2-q^2,2pq,p^2+q^2)$. – abiessu Oct 9 '14 at 14:51
• Better pay attention to the search for solutions Diofantos equation of the form: $aX^2+bXY+cY^2=jZ^2$ – individ Oct 9 '14 at 17:47

Starting with $(165,52,173)$, we attempt to find the $p,q$ pair which generates this triple, i.e., $p^2-q^2=165,2pq=52,p^2+q^2=173$. Clearly, we have $2q^2=173-165=8\implies q=2$ and thus $p=13$.

The ancestor of this triple arises from $(|p-2q|,q)\text{ or }(q,|p-2q|)$, whichever places $p',q'$ in largest-to-smallest order. In this case, we have $p-2q=9$ and thus the ancestor pair is $(p',q')=(9,2)$ and therefore the ancestor triple is $(p'^2-q'^2,2p'q',p'^2+q'^2)=(77,36,85)$.

• Is it not possible to avoid the sign issue? i.e., Is there no formula which can take any Pythagorean triple of positive integers $(a_n,b_n,c_n)$ and give its “ancestor” triple $(a_{n-1},b_{n-1},c_{n-1})$ with all three elements positive? – Kieren MacMillan Aug 18 '16 at 23:54

You can use the matrix transformations found here:

http://en.wikipedia.org/wiki/Formulas_for_generating_Pythagorean_triples#Pythagorean_triples_by_use_of_matrices_and_linear_transformations

to ascend the tree of triples. To decend, just use the inverse matrices (which look similar except for some signs being flipped). You can try each inverse in turn but, in fact, you only need use any of the three inverses. If it was not the correct one (meaning not the one used to ascend to the current triple), you will get the ancestor triple anyway, only some of the lengths will be negative. So just take the absolute value and you're done.

For example $$\left(\begin{array}[ccc]11 & 2 & 2 \\ 2 & 1 & 2 \\ 2 & 2 & 3\end{array}\right)^{-1}.\left(\begin{array}[c]1165\\ 52\\173\end{array}\right) = \left(\begin{array}[ccc]11 & 2 & -2 \\ 2 & 1 & -2 \\ -2 & -2 & 3\end{array}\right).\left(\begin{array}[c]1165\\ 52\\173\end{array}\right) = \left(\begin{array}[c] 0-77 \\ 36\\85\end{array}\right)$$

• If we start with an [indeterminate] triple $(a,b,c)$, is there a single expression in [polynomials of?] $a,b,c$ that we can use to represent the fundamental $(3,4,5)$? – Kieren MacMillan Oct 12 '14 at 1:23
• Is it not possible to avoid the sign issue? i.e., Is there no formula which can take any Pythagorean triple of positive integers $(a_n,b_n,c_n)$ and give its “ancestor” triple $(a_{n-1},b_{n-1},c_{n-1})$ with all three elements positive? – Kieren MacMillan Aug 18 '16 at 23:55
• @KierenMacMillan A formula would then be: Use the matrix multiply and then take the absolute value. This is what you're asking for unless I'm misunderstanding. – amcalde Aug 19 '16 at 0:14
• @KierenMacMillan: I can't say that I have much experience with such a venture, but it sounds interesting. I'll see what I can come up with. – abiessu Aug 19 '16 at 14:06
• @KierenMacMillan: by the given design of that example, you seem to be saying that although there are numbers supplied as $(a,b,c)$ in a triple, they may not necessarily be a Pythagorean Triple for a given $x,y$, is that right? And following that logic, we would prove that there are no Pythagorean Triples arising from the specified formulas... – abiessu Aug 19 '16 at 14:10

Two Trees of Pythagorean triples are known to exist (Berggren's and Price's), so to answer your question you need to first identify which one you are talking about. Descent/Ascent algorithms for both trees are given the following paper.

Bernhart, F.R. & Price, H.L. Pythagoras’ garden, revisited. Aust. Sr. Math. J. 26, 29–40 (2012). http://files.eric.ed.gov/fulltext/EJ992372.pdf.

• It seems there are at least three trees of Pythagorean triples (cf. McCullough). I'm hoping one of them — or some other one I don't know about — allows a descent without sign changes. – Kieren MacMillan Aug 19 '16 at 1:28
• F.J.M. Barning (1963) rediscovered the same tree Berggren had found in 1934. McCullough didn't know about Berggren, and he refers to that tree as the "Barning tree" so I don't think a third tree can be attributed to McCullough. – KYZYL Aug 20 '16 at 2:45

I am coming to this question a bit late. In the orthogonal group of the quadratic form $x^2+y^2-z^2$ there is a reflection you can use to find the parent of each primitive Pythagorean triple (up to sign, as others have noted, and changing signs to make all coordinates positive is another reflection). See Examples 3.2 and 3.3, and the proof of Corollary 3.4, in https://www.math.uconn.edu/~kconrad/blurbs/linmultialg/descentPythag.pdf. The key reflection $s_{123}$ is defined in equation (3.3) there.

This description using a geometric language (in an orthogonal group that is not the standard orthogonal group of 3-dimensional space) does not rely directly on the parametrization formula for primitive Pythagorean triples.