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)$?
On
You can use the matrix transformations found here:
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) $$
On
The ternary rooted tree of Pythagorean triples never made sense to me and has no order that can be sensed just by looking at it. What makes more sense is a pattern of sets within the subset of triples where $GCD(A,B,C)$ is an odd square. This subset includes all primitives. Here is a sample:
$$\begin{array}{c|c|c|c|c|c|c|} n & Triple_1 & Triple_2 & Triple_3 & Triple_4 & Triple_5 & Triple_6 \\ \hline Set_1 & 3,4,5 & 5,12,13& 7,24,25& 9,40,41& 11,60,61 & 13,84,85 \\ \hline Set_2 & 15,8,17 & 21,20,29 &27,36,45 &33,56,65 & 39,80,89 & 45,108,117 \\ \hline Set_3 & 35,12,37 & 45,28,53 &55,48,73 &65,72,97 & 75,100,125 & 85,132,157 \\ \hline Set_{4} &63,16,65 &77,36,85 &91,60,109 &105,88,137 &119,120,169 & 133,156,205 \\ \hline Set_{5} &99,20,101 &117,44,125 &135,72,153 &153,104,185 &171,140,221 & 189,180,261 \\ \hline Set_{6} &143,24,145 &165,52,173 &187,84,205 &209,120,241 &231,160,281 & 253,204,325 \\ \hline \end{array}$$
The formula that generates these triples may be used to find successor or predecessor simply by increasing or decreasing the values of $n$ or $k$.
$$A=(2n-1)^2+2(2n-1)k \qquad B=2(2n-1)k+2k^2\qquad C=(2n-1)^2+2(2n-1)k+2k^2 $$
On
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.
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)$.