Binary Trees and Sum of Two Squares

技术摘要：二叉树与两数平方和

问题陈述
本文探讨了两个著名的有理数二叉树——Stern–Brocot 树与 Calkin–Wilf 树之间的结构关系。此外，通过利用这些树中的连分数理论和基于矩阵的路径表示，本文旨在为费马关于两数平方和的定理（特别是针对形式为 $4k+1$ 的素数）提供一种新的解释。

方法论
作者构建了一个基于矩阵二叉树的统一框架。该树从 $2 \times 2$ 单位矩阵开始生成，其中“右”（R）移动对应于右乘 $\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$，“左”（L）移动对应于右乘 $\begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}$。

• 恢复已知树： 通过将此结构中的每个矩阵右乘列向量 $\begin{pmatrix} 1 \\ 1 \end{pmatrix}$（列求和），可以恢复出 Stern–Brocot 树。通过左乘行向量 $\begin{pmatrix} 1 & 1 \end{pmatrix}$（行求和），可以恢复出 Calkin–Wilf 树。
• 连分数联系： 本文建立了连分数 $[q_0; q_1, q_2, \dots]$ 的渐近分数与该矩阵树中路径之间的直接映射。路径 $W$ 由对应于部分商（partial quotients）的移动序列定义（$q_0$ 次 R 移动，$q_1$ 次 L 移动，依此类推）。定理 1 证明，由该路径生成的矩阵包含其分数的渐近分数 $A_n/B_n$ 及其前项。
• 两数平方和证明： 为了证明形式为 $p \equiv 1 \pmod 4$ 的素数是两数平方和，作者利用了 Brillhart 的方法，该方法涉及 $p/x_0$ 的连分数，其中 $x_0^2 \equiv -1 \pmod p$。作者指出，该连分数是回文的，且具有偶数项。作者并未使用连分数（continuants），而是构造了一个镜像该回文结构的矩阵树特定路径 $W$。通过将该路径分解为矩阵 $M$ 及其转置 $M^T$，并分析所得的矩阵乘积，他们推导出了平方和恒等式。

核心结果

1. 树的统一： 本文证明了 Stern–Brocot 树和 Calkin–Wilf 树并非截然不同的实体，而是通过简单的线性运算（列求和或行求和）从同一个底层的矩阵二叉树中衍生出来的。
2. 路径-渐近分数对应关系： 定理 1 提供了一个严谨的公式，将由连分数系数定义的路径矩阵乘积与该分数的渐近分数联系起来。
3. 费马定理的构造性证明： 本文提出了任何素数 $p = 4k+1$ 都可以写成 $p = x^2 + y^2$ 的证明。该证明依赖于 $p/x_0$ 连分数的对称回文性质。
4. 平方数的显式识别： 一个重要的结果是能够显式识别出使得 $p = x^2 + y^2$ 成立的整数 $x$ 和 $y$。定理 5 指出，如果分数 $x/y$ 对应于 Stern–Brocot 树中的路径 $M^T$（其中 $M$ 是由回文连分数路径的前半部分导出的），那么 $p = x^2 + y^2$。类似的结论也适用于使用路径 $M$ 的 Calkin–Wilf 树。

意义与主张
本文声称为 Brillhart 关于费马两数平方和定理的证明提供了一种新的解释。作者不再仅仅依赖于连分数的代数性质，而是利用了矩阵二叉树中路径的几何与结构特性。其主要意义在于通过树的路径结构，显式地构造出求和为 $p$ 的两个平方数。这项工作将连分数理论与基于矩阵生成的有理树无缝结合，为这些数学对象提供了一个统一的视角，并在连分数、二叉树与数论恒等式之间建立了一种具体的算法联系。