🔢 mathematics

Binary Trees and Sum of Two Squares

This paper introduces a matrix-based binary tree unifying the Stern–Brocot and Calkin–Wilf trees, explores its connection to continued fractions, and utilizes this framework to provide a path-based representation of Brillhart's proof for the sum of two squares.

Original authors: Hongshen Chua

Published 2026-06-25

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Hongshen Chua

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a magical family tree, but instead of people, every branch holds a fraction (a number like 1/2 or 3/4). For a long time, mathematicians knew about two famous versions of this tree: the Stern–Brocot tree and the Calkin–Wilf tree. They look very similar, like twins, but they grow their branches using slightly different rules.

This paper introduces a "master tree" that sits underneath both of them, acting like a common ancestor. It also uses this tree to solve a very old, famous puzzle about numbers: Can every prime number that is one more than a multiple of 4 (like 5, 13, 17) be written as the sum of two perfect squares? (For example, $5 = 1^2 + 2^2$ ).

Here is the story of the paper, broken down into simple steps:

1. The Master Tree: A Game of Matrix Moves

Instead of just writing down fractions, the author builds a tree using 2x2 grids of numbers (called matrices).

The Starting Point: You begin with a blank slate (the identity matrix).
The Moves: To grow the tree, you can only make two types of moves:
- The "Right" Move (R): You take the left column of numbers and add it to the right column.
- The "Left" Move (L): You take the right column and add it to the left column.
The Result: By repeating these moves, you create a giant family tree of grids.

The Magic Connection:
If you take any grid in this tree and perform a simple "summing" trick on it, you instantly get the Stern–Brocot tree. If you perform a slightly different "summing" trick (swapping rows and columns), you get the Calkin–Wilf tree. So, this one "Matrix Tree" is the secret engine that powers both famous trees.

2. The Map: Reading Continued Fractions

Mathematicians often write complex numbers as "continued fractions" (a fancy way of writing a number as a chain of additions and divisions, like $1 + \frac{1}{2 + \frac{1}{3...}}$ ).

The paper shows that these continued fractions are actually maps or instructions for walking through the Matrix Tree.

If your map says "go Right 3 times, then Left 2 times," you follow that path on the tree.
The paper proves that the grid you land on at the end of your walk contains the exact answer (the "convergent") for that fraction. It's like a treasure hunt where the path you take reveals the treasure at the end.

3. Solving the "Sum of Two Squares" Puzzle

The final part of the paper tackles Fermat's famous theorem: Any prime number that is 1 more than a multiple of 4 can be split into two squares.

Here is how the author solves it using their tree:

The Setup: Take a prime number (like 13). Find a special number related to it (called $x_0$ ) that helps set up a specific fraction.
The Mirror Trick: When you turn this fraction into a continued fraction map, something magical happens: the map is symmetrical (a palindrome). It looks like a reflection in a mirror (e.g., Right, Left, Right, Right, Left, Right).
The Walk: You walk this symmetrical path on the Matrix Tree. Because the path is symmetrical, the math works out so that the final grid you land on has a very special property.
The Reveal: When you look at the numbers in that final grid, the prime number (13) appears as the sum of two squares hidden inside the math.
- The author shows that the two numbers you need to square are actually the result of a specific path on the tree.
- In our example, the path reveals that $13 = 2^2 + 3^2$ .

The Big Takeaway

The paper doesn't just prove that these numbers can be written as sums of squares; it gives you a recipe to find exactly which squares they are.

The Analogy: Think of the Matrix Tree as a giant, magical labyrinth. The "Sum of Two Squares" problem is a locked door. The author discovered that if you follow a specific, symmetrical path through the labyrinth (based on the properties of the prime number), the door opens, and the two numbers you need to unlock the secret are waiting for you right there on the floor.

In short, the paper connects three seemingly different things—tree structures, fraction maps, and number puzzles—by showing they are all different views of the same underlying mathematical machine.

Technical Summary: Binary Trees and Sum of Two Squares

Problem Statement
The paper addresses the structural relationship between two prominent binary trees of rational numbers: the Stern–Brocot tree and the Calkin–Wilf tree. Furthermore, it seeks to provide a new interpretation of Fermat's theorem on the sum of two squares (specifically for primes of the form $4k+1$ ) by leveraging the theory of continued fractions and matrix-based path representations within these trees.

Methodology
The authors construct a unifying framework based on a matrix binary tree. This tree is generated starting from the $2 \times 2$ identity matrix, where a "Right" (R) move corresponds to post-multiplication by $\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$ and a "Left" (L) move corresponds to post-multiplication by $\begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}$ .

Recovering Known Trees: The Stern–Brocot tree is recovered by post-multiplying each matrix in this structure by the column vector $\begin{pmatrix} 1 \\ 1 \end{pmatrix}$ (summing columns). The Calkin–Wilf tree is recovered by pre-multiplying by the row vector $\begin{pmatrix} 1 & 1 \end{pmatrix}$ (summing rows).
Continued Fraction Connection: The paper establishes a direct mapping between the convergents of a continued fraction $[q_0; q_1, q_2, \dots]$ and paths through this matrix tree. A path $W$ is defined by a sequence of moves corresponding to the partial quotients ( $q_0$ R-moves, $q_1$ L-moves, etc.). Theorem 1 proves that the matrix resulting from such a path contains the convergents $A_n/B_n$ and their predecessors in its entries.
Sum of Two Squares Proof: To prove that a prime $p \equiv 1 \pmod 4$ is a sum of two squares, the authors utilize Brillhart's approach involving the continued fraction of $p/x_0$ , where $x_0^2 \equiv -1 \pmod p$ . They note that this continued fraction is palindromic with an even number of terms. Instead of using continuants, the authors construct a specific path $W$ in the matrix tree that mirrors this palindromic structure. By decomposing this path into a matrix $M$ and its transpose $M^T$ , and analyzing the resulting matrix product, they derive the sum of squares identity.

Key Results

Unification of Trees: The paper demonstrates that the Stern–Brocot and Calkin–Wilf trees are not distinct entities but are derived from a single underlying matrix binary tree through simple linear operations (column or row summation).
Path-Convergent Correspondence: Theorem 1 provides a rigorous formula linking the matrix product of a path defined by continued fraction coefficients to the convergents of that fraction.
Constructive Proof of Fermat's Theorem: The paper presents a proof that any prime $p = 4k+1$ can be written as $p = x^2 + y^2$ . The proof relies on the palindromic nature of the continued fraction of $p/x_0$ .
Explicit Identification of Squares: A significant result is the ability to explicitly identify the integers $x$ and $y$ such that $p = x^2 + y^2$ . Theorem 5 states that if a fraction $x/y$ corresponds to the path $M^T$ in the Stern–Brocot tree (where $M$ is derived from the first half of the palindromic continued fraction path), then $p = x^2 + y^2$ . A similar result holds for the Calkin–Wilf tree using path $M$ .

Significance and Claims
The paper claims to offer a new interpretation of Brillhart's proof of Fermat's theorem on the sum of two squares. Rather than relying solely on the algebraic properties of continuants, the authors utilize the geometric and structural properties of paths through the matrix binary tree. The primary significance lies in the explicit construction of the two squares summing to $p$ via the tree's path structure, providing a concrete algorithmic link between continued fractions, binary trees, and number-theoretic identities. The work integrates the theory of continued fractions seamlessly with the matrix-based generation of rational trees, offering a unified perspective on these mathematical objects.

1. The Master Tree: A Game of Matrix Moves

2. The Map: Reading Continued Fractions

3. Solving the "Sum of Two Squares" Puzzle

The Big Takeaway

Technical Summary: Binary Trees and Sum of Two Squares

More like this