Binary Trees and Sum of Two Squares

Hongshen Chua · 2026

Read Binary Trees and Sum of Two Squares by Hongshen Chua (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-24931.txt.

Introduction

Hongshen Chua explores two famous binary trees of rational numbers and uses them to reread a classic theorem. The Stern Brocot tree grows by taking mediants of neighbouring fractions. The Calkin Wilf tree grows by giving each fraction two children built from its parts. The trees look alike, and Backhouse and Ferreira explained why: one matrix based binary tree generates both. Chua develops that construction in detail. Continued fractions enter next, since their convergents appear as paths through the matrix tree.

The payoff is number theoretic. Brillhart once gave a short proof of Fermat's theorem that certain primes are sums of two squares, using continued fractions. The path based viewpoint offers a new interpretation of that proof. Walking the tree replaces the older fraction manipulations. Chua presents the material as an integrated tour: two trees, one matrix construction, continued fractions, and a fresh route through a three century old result.

Catalog record

CREATORHongshen Chua
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE9 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.24931

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Binary Trees and Sum of Two Squares Hongshen Chua Abstract 1 Introduction When it comes to binary trees of rational numbers, there are two that stand out in particular, namely the Stern–Brocot tree (Figure 1 ) and the Calkin–Wilf tree (Figure 2 ). Both trees start with the number 1 at the 0 -th level. The (i+1) -th level of the Stern-Brocot tree is generated from two adjacent terms, a_{1}/b_{1} and a_{2}/b_{2} , on the i -th level by computing their mediant, (a_{1}+a_{2})/(b_{1}+b_{2}) . In contrast, to construct the Calkin–Wilf tree, we take a vertex a/b at the i -th level, then set its left child as a/(a+b) and its right child as (a+b)/b . {forest} Figure 1: Stern–Brocot tree {forest} Figure 2: Calkin–Wilf tree Both trees appear quite similar, so it is perhaps unsurprising that they are closely related. In fact, Backhouse and Ferreira [ 1 ] described a remarkable matrix-based binary tree that naturally generates both the Stern–Brocot and Calkin–Wilf trees. We will explore this construction in more detail in Section 2 . The matrix binary tree also integrates seamlessly with the theory of continued fractions. The convergents of a continued fraction can be derived from a matrix similar to the one we use to generate our tree. Consequently, these convergents can be represented as paths through the matrix binary tree. This will be the focus of Section 3 . Finally, Brillhart wrote a brief note [ 2 ] presenting a proof of Fermat’s famous theorem on the sum of two squares. The main idea of his method relies on continued fractions. Our path-based approach offers a new interpretation of his proof, which we will present in Section 4 . 2 Binary Trees First, we construct a matrix binary tree that underlies both the Stern–Brocot and Calkin–Wilf trees. Starting with the 2\times 2 identity matrix, a right ( R ) and a left ( L ) move correspond to post-multiplication by the matrices \begin{pmatrix}1&1\\ 0&1\end{pmatrix} and \begin{pmatrix}1&0\\ 1&1\end{pmatrix} , respectively. Alternatively, an R -move can be thought of as adding the left column to the right column, while an L -move involves adding the right column to the left column. By repeatedly applying these moves, we can construct the matrix binary tree shown in Figure 3 . {forest} Figure 3: Matrix binary tree From the matrix binary tree, we can easily recover the Stern–Brocot and Calkin–Wilf trees. By post-multiplying each matrix by \begin{pmatrix}1\\ 1\end{pmatrix} , which is equivalent to adding the columns together, we obtain the Stern–Brocot tree (Figure 1 ). On the other hand, if we pre-multiply each matrix by \begin{pmatrix}1&1\end{pmatrix} , which corresponds to adding the rows together, we get the Calkin–Wilf tree (Figure 2 ). 3 Continued Fraction Let [q_{0};q_{1},q_{2},\ldots] represent the continued fraction \displaystyle q_{0}+\cfrac{1}{q_{1}+\cfrac{1}{q_{2}+\ddots}}. The n -th convergent A_{n}/B_{n} of a continued fraction is the fraction obtained by truncating the continued fraction at q_{n} , i.e., A_{n}/B_{n}=[q_{0};q_{1},q_{2},\ldots,q_{n}] . These convergents are related by the following linear recurrences: \displaystyle A_{n}=q_{n}A_{n-1}+A_{n-2}\quad\text{ and }\quad B_{n}=q_{n}B_{n-1}+B_{n-2}, with the initial values A_{-1}=1 , A_{0}=q_{0} , B_{-1}=0 , and B_{0}=1 . The matrix binary tree provides a powerful representation of the convergents. Given a continued fraction [q_{0};q_{1},q_{2},\ldots] , we define a path W through the tree by starting with q_{0} R -moves, followed by q_{1} L -moves, and so on, alternating the direction after each term. By an abuse of notation, we write R=\begin{pmatrix}1&1\\ 0&1\end{pmatrix} , L=\begin{pmatrix}1&0\\ 1&1\end{pmatrix} , and the matrix corresponding to the path W as R^{q_{0}}L^{q_{1}}\ldots . This path produces the convergents, as demonstrated in the next theorem. Theorem 1 . Let A_{n}/B_{n} be the n -th convergent of a continued fraction [q_{0};q_{1},q_{2},\ldots] . If a path W_{n}=R^{q_{0}}L^{q_{1}}\ldots ends with an R -move, then \displaystyle W_{n}=\begin{pmatrix}A_{n-1}&A_{n}\\ B_{n-1}&B_{n}\end{pmatrix}. Otherwise, if W_{n} ends with an L -move, then \displaystyle W_{n}=\begin{pmatrix}A_{n}&A_{n-1}\\ B_{n}&B_{n-1}\end{pmatrix}. Proof. A quick calculation shows that consecutive R or L moves have a simple matrix representation of \displaystyle R^{q}=\begin{pmatrix}1&q\\ 0&1\end{pmatrix}\quad\text{ and }\quad L^{q}=\begin{pmatrix}1&0\\ q&1\end{pmatrix}. We proceed by induction. For the base case of n=0 , we have \displaystyle W_{0}=R^{q_{0}}=\begin{pmatrix}1&q_{0}\\ 0&1\end{pmatrix}=\begin{pmatrix}A_{-1}&A_{0}\\ B_{-1}&B_{0}\end{pmatrix}. Next, it is simple to verify that \displaystyle A_{1}=q_{1}A_{0}+A_{-1}=q_{0}q_{1}+1\quad\text{ and }\quad B_{1}=q_{1}B_{0}+B_{-1}=1. Hence, for the case n=1 , we compute \displaystyle R^{q_{0}}L^{q_{1}}=\begin{pmatrix}1&q_{0}\\ 0&1\end{pmatrix}\begin{pmatrix}1&0\\ q_{1}&1\end{pmatrix}=\begin{pmatrix}q_{0}q_{1}+1&q_{0}\\ q_{1}&1\end{pmatrix}=\begin{pmatrix}A_{1}&A_{0}\\ B_{1}&B_{0}\end{pmatrix}. This completes the base cases for n=0 and n=1 . Now, suppose the result holds for all n\leq N for some N\geq 1 . We prove it for n=N+1 . If W_{N+1} ends with an R -move, then W_{N} must have ended with an L -move. By the inductive hypothesis, we get \displaystyle W_{N+1}=\begin{pmatrix}A_{N}&A_{N-1}\\ B_{N}&B_{N-1}\end{pmatrix}\begin{pmatrix}1&q_{N+1}\\ 0&1\end{pmatrix}=\begin{pmatrix}A_{N}&q_{N+1}A_{N}+A_{N-1}\\ B_{N}&q_{N+1}B_{N}+B_{N-1}\end{pmatrix}. Using the recurrence relation for convergents, the last matrix simplifies to \displaystyle W_{N+1} \displaystyle=\begin{pmatrix}A_{N}&A_{N+1}\\ B_{N}&B_{N+1}\end{pmatrix}. On the other hand, if W_{N+1} ends with an L -move, then W_{N} must have ended with an R -move, so \displaystyle W_{N+1}=\begin{pmatrix}A_{N-1}&A_{N}\\ B_{N-1}&B_{N}\end{pmatrix}\begin{pmatrix}1&0\\ q_{N+1}&1\end{pmatrix}=\begin{pmatrix}q_{N+1}A_{N}+A_{N-1}&A_{N}\\ q_{N+1}B_{N}+B_{N-1}&B_{N}\end{pmatrix}. Again, the recurrence relation for convergents yields \displaystyle W_{N+1}=\begin{pmatrix}A_{N+1}&A_{N}\\ B_{N+1}&B_{N}\end{pmatrix}. This completes the induction step, and hence the proof. ∎ 4 Sum of Two Squares In a letter to Mersenne, Fermat stated that any prime p of the form 4k+1 can be written as a sum of two squares [ 4 ] . However, like many of his conjectures, Fermat did not provide a proof for this result. The first complete proof was given by Euler, using the method of infinite descent, a technique, rather fittingly, invented by Fermat. Our approach is inspired by Brillhart’s excellent note [ 2 ] on this subject. First, we find a solution x_{0} to the congruence x^{2}\equiv-1\pmod{p} , where 0<x_{0}<p/2 . Such a solution always exists as -1 is a quadratic residue modulo p . Specifically, (-1\mid p)=(-1)^{(p-1)/2}=1 , where (\cdot\mid p) denotes the Legendre symbol modulo p . Once we have chosen our x_{0} , a result from Perron states that the continued fraction of p/x_{0} has a particularly neat structure. Lemma 2 ( [ 6 ] ) . The continued fraction of p/x_{0} has an even number of terms and is palindromic, i.e., \displaystyle p/x_{0}=[q_{0},q_{1},\ldots,q_{n},q_{n},\ldots,q_{1},q_{0}]. So far, our proof follows Brillhart’s approach, but this is the point where we diverge. Rather than working with continuants, consider the path \displaystyle W=R^{q_{0}}L^{q_{1}}\ldots S^{q_{n}}S^{q_{n}}\ldots R^{q_{1}}L^{q_{0}}, where S is either R or L , depending on whether n is odd or even. Since the path W ends with an L -move, Theorem 1 tells us that \displaystyle W=\begin{pmatrix}p&*\\ x_{0}&*\end{pmatrix}. On the other hand, let M=R^{q_{0}-1}L^{q_{1}}\ldots S^{q_{n}}=\begin{pmatrix}a&b\\ c&d\end{pmatrix} , where a , b , c , and d are integers. Since R=L^{T} , we have W=RMM^{T}L . The middle term MM^{T} evaluates to \displaystyle MM^{T} \displaystyle=\begin{pmatrix}a&b\\ c&d\end{pmatrix}\begin{pmatrix}a&c\\ b&d\end{pmatrix}=\begin{pmatrix}a^{2}+b^{2}&ac+bd\\ ac+bd&c^{2}+d^{2}\end{pmatrix}. Therefore, we have \displaystyle RMM^{T}L=\begin{pmatrix}1&1\\ 0&1\end{pmatrix}\begin{pmatrix}a^{2}+b^{2}&ac+bd\\ ac+bd&c^{2}+d^{2}\end{pmatrix}\begin{pmatrix}1&0\\ 1&1\end{pmatrix}, which simplifies to \displaystyle W=\begin{pmatrix}(a+c)^{2}+(b+d)^{2}&(a+c)c+(b+d)d\\ (a+c)c+(b+d)d&c^{2}+d^{2}\end{pmatrix}. Comparing both expressions for W yields \displaystyle p=(a+c)^{2}+(b+d)^{2}. Thus, we conclude the following theorem. Theorem 3 . If a prime p has the form 4k+1 , then p is a sum of two squares. Remark 4 . We also have the relation x_{0}=(a+c)c+(b+d)d . An advantage of this method is that we can explicitly identify the two squares that make up the sum. The numbers (a+c) and (b+d) correspond to the path M^{T} applied to the matrix \begin{pmatrix}1\\ 1\end{pmatrix} . Hence, we can state the following theorem. Theorem 5 . If the fraction x/y corresponds to

Read the complete text