数论初步 —— Stern-Brocot tree 和 Farey serires

Posted by WildCow on April 4, 2019

写在前面


爱在接吻欲落时





互质


若 $m, n$ 满足 $gcd(n, m) = 1$
那么我们称 $m, n$ 为互质的




Stern-Brocot tree


Stern-Brocot tree (下文简称 SBT)是一种构造满足 $gcd(n, m) = 1$ 的全部非负分数 $m / n$ 的集合的方法
思想很简单
从两个分数 $(\frac{0}{1},\frac{1}{0})$ 开始
然后不断的在两个相邻分数 $(\frac{m}{n},\frac{m’}{n’})$ 中插入 $\frac{m + m’}{n + n’}$
新的分数 $\frac{m + m’}{n + n’}$ 被称为相邻分数 $(\frac{m}{n},\frac{m’}{n’})$ 的中位分数(mediant)
所以在一开始的情形插入后,可以得到
$\frac{0}{1},\frac{1}{1},\frac{1}{0}$
然后就可以再插入两个分数了
$\frac{0}{1}, \frac{1}{2},\frac{1}{1},\frac{2}{1},\frac{1}{0}$
然后就可以再插入四个
$\frac{0}{1}, \frac{1}{3}, \frac{1}{2},\frac{2}{3}, \frac{1}{1}, \frac{3}{2}, \frac{2}{1}, \frac{3}{1}, \frac{1}{0}$
其实你可以把这个分数的序列当作一个二叉树的构造
Alt text
然后是一个很重要的结论:
如果 $m/n$ 和 $m’ / n’$ 是这个构造中任意一个阶段的相邻分数
我们就有 $m’n - mn’ = 1$
归纳法证明:

  • 对于初始状态肯定是正确的($1 \times 1 - 0 \times 0 = 1$)
  • 对于从 $(\frac{m}{n},\frac{m’}{n’})$ ,假设成立 $m’n - mn’ = 1$
    当我们够造出 $\frac{m + m’}{n + n’}$
    我们需要证明
    $(m + m’)n - (n + n’)m = 1$ 和 $(n + n’)m’ - (m + m’)n’ $= 1
    这就。。很显然的吖。。
    把括号拆开,就会发现 $mn$ 和 $m’n’$ 约掉了
    然后就和上面的一样了
    证毕
    接下来是三个推论以及证明




最简分数


在 SBT 中的每个分数都是最简分数
即 $gcd(n, m) = 1$
很容易发现 $m’n - mn’ = 1$ 其实不就是。。。$exgcd$ 么
那就直接证出来了




不重复


上述构造方式不会够造出两个相同的分数
对于 $m / n < m’ / n’$
且所有值为非负的
那小学生都会知道
$m / n < (m + m’) / (n + n’) <m’ / n’$
那就。。和二分一样的意思了




不遗漏


SBT 不会遗漏任何满足条件的分数
反证法证明

  • 假设 $\frac{a}{b}$ 不会被构造得出
    且在某一阶段有
    $\frac{m}{n} < \frac{a}{b} < \frac{m’}{n’}$
    那么我们有
    $\frac{a}{b} - \frac{m}{n} > 0$ 和 $\frac{m’}{n’} - \frac{a}{b} > 0$
    于是就有
    $an - bm \geq 0$ 和 $bm’ - an’ \geq 0$
    于是我们有
    $(m’ + n’)(an - bm) + (m + n)(bm’ - an’) \geq m’ + n’ + m + n$
    括号拆开
    $am’n - bmn’ - amn’ + bm’n \geq m’ + n’ + m + n$
    $a(m’n - mn’) + b(m’n - mn’) >= m’ + n’ + m + n$
    之前有 $m’n - mn’ = 1$
    那就化成了 $a + b \geq m’ + n’ + m + n$
    由于 $m, n, m’, n’$ 每次都会增加
    所以至多 $a + b$ 次操作后一定能够得到 $a / b$
    证毕



一些嘿嘿嘿的东西


显然,我们可以把 SBT 当作一个表示有理数的数系(number system)
我们用字母 $L$,$R$ 表示从 SBT 树根到目标分数行走的路径
这样每个分数都能用一个 $L$、$R$ 构成的字符串唯一表示
不过
为了能够表示分数 $\frac{1}{1}$
我们引进记号 $I$ 表示
我们当然希望能够解决两个问题:

  • 给出字符串,求对应的 $m / n$
    例如 $f(LRRL) = \frac{5}{7}$
    根据 SBT 的构造方法
    如果 $m / n$ 和 $m’ / n’$ 是 SBT 上,位于 $f(S)$ 上一层且是它前面以及后面与之最接近的两个分数(好绕)
    则显然有 $f(S) = (m + m’) / (n + n’)$
    一开始有 $m / n = 0 / 1$ 和 $m’ / n’ = 1 / 0$
    这样当在这棵树往左或者往右移动的时候
    我们就能很方便的用中位分数去代替 $m / n$ 或 $m’ / n’$
    那么我们很容易(?)就能想到用矩阵
    会注意到这个和我们的分数表示是上下相反的
    在接下来的研究中我们会发发现这样倒过来是十分必要的
    这样我们首先有:
    你会发现这其实就是一个单位矩阵
    向左走一步时我们需要用 $n + n’$ 代替 $n$
    用 $m + m’$ 代替 $m$
    这样其实是:
    同样的往右边走就是:
    这样一来,我们把 $L$ 和 $R$ 定义成 $2\times2$ 矩阵,就有:
    这样就有一个很漂亮的一语双关(?)的结论:
    $M(S) = S$
  • 给出 $m/n$ ,求对应的字符串
    在树的结构的基础上
    显然会发现往左走会变小。。。往右走会变大。。
    就和二叉搜索树一样的找就行了
    转移用问题一的方法进行矩阵转移
    这个方法是固定 $m / n$ 的
    还有一个方法是改变 $m / n$ 的
    我们尝试观察 $S$ 和 $RS$ 之间的关系
    即:
    显然可以得出
    $f(S) = (m + m’)/(n + n’)$
    $f(RS) = ((m + n) + (m’ + n’)) / (n + n’)$
    可以得出,$f(RS) = f(S) + 1$
    这就意味着我们可以不用矩阵转移
    即对于当前的 $m/n$
    如果 $m < n$,输出 $L$,$n -= m$
    否则,输出 $R$,$m -= n$
    这样的方法的意义在于,我们可以求得一个无理数的最逼近的分数!




Farey series


我们定义阶为 $N$ 的法里级数Farey series )为介于 $0$ 和 $1$ 之间,分母不超过 $N$ 的所有最简分数的集合,并且是递增排列的
记为 $F_N$
通过 SBT 的构造方法
我们可以很容易得出由 $F_{N - 1}$ 得到 $F_N$
即在 $F_{N - 1}$ 中所有相邻的分母之和为 $N$ 的分数进行构造就好了
因为分子和分母互质
所以由 $F_{N - 1}$ 得到 $F_N$ 我们能获得 $\varphi(N)$ 个新的分数
其中 $\varphi$ 为欧拉函数
(可能会在以后补充一些新的东西)