A tree that holds every triple

There are infinitely many right triangles with whole-numbered sides, and the usual way to produce them is a formula with two free parameters that has to be handed a condition — take $m$ and $n$ coprime and of opposite parity — before it stops repeating itself. Here is the same collection with no condition at all.

Every entry in that tree is a right triangle: $3^2 + 4^2 = 5^2$ at the root, $20^2 + 21^2 = 29^2$ two steps along the middle, $119^2 + 120^2 = 169^2$ one step further. Every entry is primitive — its three sides share no common factor. No entry appears twice. And the three matrices doing the work are the same three at every node, applied without any inspection of the numbers they are applied to.

The three matrices #

Write a triple as a column of three numbers. Then the children of $(a, b, c)$ are the three columns obtained by multiplying it by

$$\begin{pmatrix} 1 & -2 & 2 \\ 2 & -1 & 2 \\ 2 & -2 & 3 \end{pmatrix},\quad \begin{pmatrix} 1 & 2 & 2 \\ 2 & 1 & 2 \\ 2 & 2 & 3 \end{pmatrix},\quad \begin{pmatrix} -1 & 2 & 2 \\ -2 & 1 & 2 \\ -2 & 2 & 3 \end{pmatrix}.$$

Applied to $(3, 4, 5)$ they give $(5, 12, 13)$, $(21, 20, 29)$ and $(15, 8, 17)$. Applied to those they give nine more. The arithmetic is three multiplications and two additions per entry, and it never divides by anything.

That the matrices preserve the Pythagorean condition is a calculation anybody can do once and never repeat: each of the three satisfies $M^{\mathsf T} J M = J$ where $J$ is the diagonal matrix $\operatorname{diag}(1, 1, -1)$, which says exactly that $a^2 + b^2 - c^2$ is unchanged. A matrix that preserves that quantity carries triples to triples, and integer entries keep the results whole. What none of this explains is the interesting half: why nothing is missed and nothing is repeated.

Why the tree is complete, and why it does not repeat #

The argument runs downward rather than upward, and it is the reason this construction is due to Berggren in 1934 and rediscovered by Barning and by Hall thirty years later: descent is what makes it work.

Every primitive triple other than $(3, 4, 5)$ has exactly one of the three matrices whose inverse sends it to a smaller primitive triple. The inverses are integer matrices too, so the reduced triple is whole; a short check on the signs shows that exactly one of the three reductions lands in the positive octant, and that reduction strictly decreases the hypotenuse. So from any primitive triple, following the arrows backwards gives a sequence with strictly falling hypotenuses, and a falling sequence of positive whole numbers cannot go on forever. It stops, and the only place it can stop is at the one triple with no parent, which is $(3, 4, 5)$.

Completeness and uniqueness are the same statement read in the two directions. Every triple has a path down to the root, so every triple is somewhere in the tree; that path is forced at every step, so it is the only path, and no triple is in the tree twice.

This is worth holding against the parametrisation, which reaches the same set by a different route. Rational points on the circle give every triple as $(m^2 - n^2,\, 2mn,\, m^2 + n^2)$, and the pair $(m, n)$ has to be coprime and of opposite parity or the same triple arrives repeatedly and in non-primitive dress. The condition is a filter applied after the fact. The tree has no filter: its output is primitive because its input was, and the property is carried rather than tested.

The check the figure runs #

A claim of the form every one of them, exactly once is exactly the kind that a picture cannot make and a computation can. So the figure grows the tree until the hypotenuse passes two hundred, collects what it finds, and compares that collection with the one produced by an exhaustive search over $m$ and $n$ in the parametrisation. Both find 32 triples, and they are the same 32.

That is not bookkeeping. The two procedures share nothing: one multiplies matrices and never divides, the other loops over pairs of integers and rejects those with a common factor or the same parity. Agreement between them is evidence for the claim in a way that a hand-checked list of the first dozen is not, and the check is the same shape as the one that counts triangulations by drawing every one of them.

The middle branch, and the triangles that are nearly isosceles #

The three matrices are not interchangeable, and the difference between them is visible in the drawn tree. Follow the middle matrix repeatedly from the root and the triples are

$$(3, 4, 5),\quad (21, 20, 29),\quad (119, 120, 169),\quad (697, 696, 985),\ \dots$$

whose legs differ by exactly one. These are the nearly isosceles right triangles, and the hypotenuses satisfy a two-term recurrence: $6 \times 5 - 1 = 29$ and $6 \times 29 - 5 = 169$, and the pattern continues, each hypotenuse six times the previous one minus the one before that. The same recurrence generates the solutions of Pell’s equation $x^2 - 2y^2 = \pm 1$, which is not a coincidence: a right triangle with legs one apart is a near-solution of $2y^2 = x^2$, and the best rational approximations to $\sqrt{2}$ are what such a triangle is made of.

Follow the first matrix instead and the triples become long and thin — $(3,4,5)$, $(5,12,13)$, $(7,24,25)$ — with the legs in ratio approaching zero. The third matrix goes the other way. So the tree is not merely a list; it sorts the family by shape, and the three matrices are three directions to travel in.

The cousin construction #

A tree in which every object of some kind appears exactly once, built by a fixed rule with no test for lowest terms, should look familiar. The Stern–Brocot tree does the same thing for fractions: take mediants of neighbours, never cancel anything, and every positive rational turns up once, already reduced.

The resemblance is closer than an analogy. Both trees are built from matrices of determinant one — unimodular matrices — acting on a set the matrices preserve, and in both cases the reason nothing needs cancelling is that a unimodular matrix cannot introduce a common factor. If two entries of the output shared a factor, the inverse matrix, which is also integral, would carry that factor back into the input. The input was primitive, so they do not.

That is the whole of it, and it is the sort of argument this collection is built around: a property is maintained by a structural fact about the operation rather than restored by an inspection after the fact. The same reasoning is what makes the Euclidean algorithm terminate in lowest terms without ever looking for a common factor.

Two things every entry in the tree satisfies #

The tree produces triples and the descent explains why it produces all of them. It is worth asking what the entries have in common besides the defining equation, because the answers are checkable against the drawn nodes and they explain a pattern a reader will already have half-noticed in the numbers.

Sixty divides the product of the three sides. Look at the root: $3 \cdot 4 \cdot 5 = 60$. The next generation gives $5 \cdot 12 \cdot 13 = 780$, and $20 \cdot 21 \cdot 29 = 12180$, and $8 \cdot 15 \cdot 17 = 2040$ — each a multiple of sixty. It holds at every node forever, and the reason is three separate congruence facts stacked together.

A square is $0$ or $1$ modulo three, so if neither leg were divisible by three the two squares would add to two, which no square is; hence one leg is a multiple of three. Modulo eight, an odd square is $1$ and an even square is $0$ or $4$, and running the cases shows the even leg must be a multiple of four. And squares modulo five are $0$, $1$ or $4$; if none of the three sides were divisible by five the equation would fail in every remaining combination, so one of the three is a multiple of five. The three factors are distinct primes’ worth of divisibility, so their product divides the product of the sides.

And every one of these triangles has a whole-number inradius. The radius of the inscribed circle of a right triangle is half of $a + b - c$, and for a primitive triple that quantity is even — the legs have opposite parity and the hypotenuse is odd, so an odd sum minus an odd number is even. The root gives $(3 + 4 - 5)/2 = 1$; the middle child gives $(20 + 21 - 29)/2 = 6$; the others give $2$ and $3$. In the parametrisation the radius is exactly $n(m-n)$, so the inradius is a product of the two parameters’ difference and the smaller one — a fact that is invisible in the tree and immediate in the formula.

Both properties are worth noticing for what they say about the two descriptions. The tree cannot see either of them. Nothing in the three matrices refers to three, four, five or to an inscribed circle, and a reader who only had the tree would find the divisibility by inspecting outputs and would have no route to a proof. The parametrisation, which the tree was introduced to improve on, hands both facts over in a line each — because $m$ and $n$ are exactly the quantities the arithmetic is about.

That is the honest limit of the substitution this essay makes. A generative description names which objects exist and in what order; an analytic description names what they are made of. The tree wins on enumeration and loses on arithmetic, and neither wins outright.

What a tree buys that a formula does not #

The parametrisation is shorter to write down, so it is fair to ask what the tree is for.

It supplies a distance. Every triple has a generation number — the number of steps from $(3, 4, 5)$ — and that is a genuine measure of complication that the parametrisation does not offer. The 32 primitive triples with hypotenuse below two hundred occupy the first four generations.

It supplies a canonical route. Given a triple, the descent produces a unique word in three letters, and that word is a name for the triple. Two triples are equal exactly when their words are, which makes equality decidable by a procedure rather than by a search.

It makes the family generable in order. Breadth-first from the root produces triples in an order that never revisits, so a program that wants the first thousand primitive triples has no bookkeeping to do at all. A loop over the parametrisation must maintain a set of what it has already emitted, or accept duplicates.

And it makes structure visible. The near-isosceles family being one branch is a fact about the tree; in the parametrisation it is the condition $m - n = 1$, which is true and says nothing about where those pairs sit relative to the others.

Where it needs a condition, and where it fails #

Three things are quietly assumed above.

The tree is about primitive triples only. $(6, 8, 10)$ is a Pythagorean triple and is nowhere in the tree, because it is $2 \times (3, 4, 5)$. Every non-primitive triple is a whole multiple of exactly one primitive one, so the complete list of triples is the tree crossed with the positive integers — which is a fine description and is not what the tree itself provides.

The order of the legs matters. $(5, 12, 13)$ and $(12, 5, 13)$ are the same triangle and different columns, and the matrices distinguish them. The convention here is the one the picture uses: the drawn labels put the smaller leg first, while the arithmetic keeps whichever order the matrices produce. Getting that wrong makes the tree appear to repeat itself.

The choice of matrices is not unique. Berggren’s three are the standard ones, but other triples of matrices generate the same tree with the branches permuted, and there are genuinely different ternary trees on the same set — Price’s family of them was described in 2008. So the tree is a slight overstatement; what is canonical is that a tree of this shape exists, not which one.

How many there are, and where pi comes from #

The tree makes it easy to ask how many primitive triples have a hypotenuse below some bound, and the answer is one of the better surprises in the subject.

Below two hundred there are 32 of them, which the figure above establishes twice over. Below two thousand there are 319, and below twenty thousand, 3,186. Those numbers are very close to the bound divided by $2\pi$: the count of primitive triples with hypotenuse at most $N$ is asymptotically $N / (2\pi)$, and at $N = 20{,}000$ that estimate gives 3,183 against the 3,186 there are.

A constant defined by circles has no business in a count of integer triangles, and the route by which it arrives is the parametrisation rather than the tree. Each primitive triple is a rational point on the unit circle, the rational points with denominator at most $N$ are distributed along the circumference with a density controlled by the totient function, and the circumference is where the $2\pi$ enters. The tree gives the objects; the circle gives their number.

That is a fair illustration of what having two descriptions is worth. The tree answers which and the parametrisation answers how many, and neither answers the other’s question comfortably — the same division of labour turns up wherever a set has both a generative and an analytic description.

What the picture cannot show #

The tree is infinite and the drawing has thirteen nodes. Three generations were chosen because the fourth has twenty-seven entries and the numbers in it run to five digits, which is a picture of a data structure rather than of an idea.

More seriously, the drawing cannot show the property it is about. Exactly once is a statement about all of the infinitely many entries, and no finite portion of the tree can exhibit it — a repeat could occur at any depth without contradicting anything visible. What the picture offers is the shape of the claim and a check on it up to a stated bound; the argument that closes the gap is the descent, which is three lines of prose and no picture at all.

Nor does the tree show why $(3, 4, 5)$ is the root. It looks like a choice and it is not: it is the unique primitive triple whose three reductions all leave the positive octant, and finding that out means doing the arithmetic rather than looking.

Where this came from #

Berggren published the construction in 1934 in Swedish, in a journal that nobody outside Scandinavia read, and it disappeared. Barning found it again in 1963 in a Dutch report, and Hall in 1970 in the Mathematical Gazette; both are usually credited, and the tree is now generally called the Barning–Hall tree, or the Berggren tree by those keeping score.

What is striking about the three discoveries is that each was looking for something different. Berggren was studying the group generated by the matrices, Barning was after an algorithm, and Hall wanted a pedagogical device for a schools journal. The object is the same one and the three papers argue about it in three registers, which is a decent illustration of the fact that a good mathematical object does not know what it is for.

The underlying group turns out to be a familiar one. The three matrices generate a free product of three copies of the two-element group, sitting inside the integer orthogonal group of the form $x^2 + y^2 - z^2$; the ternary tree is the Cayley graph of that free product, and the uniqueness of the descent is freeness. That reading explains the shape of the answer, though it arrived long after the answer did.

The ladder from here #

Below this: the dissection that proves the theorem, the converse that turns three lengths into a right angle, and the parametrisation this tree replaces. Sideways: the mediant tree and the continued fraction of the square root of two, which is what the middle branch is made of. Above: the same question with the exponent changed, where the tree, the parametrisation and the triples themselves all vanish — there are no whole-numbered solutions at all beyond the second power, which is Fermat, and the machinery that finally settled it has nothing in common with anything here.

A rule that carries its own condition #

The lasting point is the one about primitivity. The parametrisation produces triples and then asks whether each is primitive; the tree produces primitive triples and never asks. The difference between those two is the difference between a filter and an invariant, and an invariant is worth a great deal more: it composes, it survives being iterated, and it turns a test that must be applied at every step into a fact established once.

The same distinction runs through this collection. An alternating sum that no deformation can change, a parity that no legal move can flip and a quantity conserved in expectation are all the same move: find the thing the operation leaves alone, and the questions that were going to require checking answer themselves.