Vtyjkyuk

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)$?

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=8implies 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)$.

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(beginarray[ccc]11 & 2 & 2 \ 2 & 1 & 2 \ 2 & 2 & 3endarrayright)^-1.left(beginarray[c]1165\ 52\173endarrayright) = left(beginarray[ccc]11 & 2 & -2 \ 2 & 1 & -2 \ -2 & -2 & 3endarrayright).left(beginarray[c]1165\ 52\173endarrayright) = left(beginarray[c] 0-77 \ 36\85endarrayright) $$

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.

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.