Farey 数列
| 法里数列 | |
|---|---|
| 术语名称 | 法里数列 |
| 英语名称 | Farey sequence |
法里数列(Farey sequence)是对正整数 [math]\displaystyle{ n }[/math] ，在 0 到 1 之间的全体分母不大于 [math]\displaystyle{ n }[/math] 的最简分数从小到大排列构成的数列。（有时不要求范围）
定义
对正整数 [math]\displaystyle{ n }[/math] ，按有理数的最简分数形式，从 [math]\displaystyle{ \tfrac{0}{1} }[/math] 到 [math]\displaystyle{ \tfrac{1}{1} }[/math] 以从小到大的顺序列出所有分数，则称为第 [math]\displaystyle{ n }[/math] 阶的法里数列(Farey sequence)。
注：可证明相邻三项之间有关系，且任意相邻两项间的分数都一定有更大的分母，因此同等价定义。
等价定义
记数列 [math]\displaystyle{ F_0 = \{\tfrac{0}{1}, \tfrac{1}{1}\} }[/math] ，并有递推关系：给定数列 [math]\displaystyle{ F_{n-1}, n\geq 1 }[/math] ，将其所有项按原顺序构成新数列，计算其中左右相邻的两项 [math]\displaystyle{ \tfrac{p}{q} }[/math] 和 [math]\displaystyle{ \tfrac{p'}{q'} }[/math] 的中间分数 [math]\displaystyle{ \tfrac{p+p'}{q+q'} }[/math] ，若满足分母 [math]\displaystyle{ q+q' \leq n }[/math] 则插入这两项之间，将这样得到的数列记为 [math]\displaystyle{ F_n, n \geq 1 }[/math] 。则得到的 [math]\displaystyle{ F_n, n\geq 0 }[/math] 就是第 [math]\displaystyle{ n }[/math] 阶的法里数列(Farey sequence)。
注：可证明新插入的分数一定是最简分数，因此和第一个定义等价。
性质
Farey 中项
在任意阶 Farey 数列的连续三项中，中间项总是外侧两项的中间分数，因此也称两个分数的中间分数为 Farey 中项。注意这个性质不像等价定义中的中间项一样要求是后插入的，先出现的项也一定是所有项插入后，外侧两项中间分数约分后的形式。
连分数关系
如果表示成连分数，对于第 [math]\displaystyle{ q }[/math] 阶 Farey 数列中的分数 [math]\displaystyle{ \tfrac{p}{q} }[/math] ，一定可以表示成 [math]\displaystyle{ [0; a_1, a_2, \dots, a_n, 1] }[/math] 和 [math]\displaystyle{ [0; a_1, a_2, \dots, a_n+1] }[/math] 两种等价形式，此时其相邻的两项一定恰好是 [math]\displaystyle{ [0; a_1, a_2, \dots, a_n] }[/math] 和 [math]\displaystyle{ [0; a_1, a_2, \dots, a_{n-1}] }[/math] ，根据大小决定左右。
相邻项关系
相邻两项 [math]\displaystyle{ \tfrac{p}{q} }[/math] 和 [math]\displaystyle{ \tfrac{p'}{q'} }[/math] ，有 [math]\displaystyle{ p'q - pq' = 1 }[/math] 。
相邻两项 [math]\displaystyle{ \tfrac{p}{q} }[/math] 和 [math]\displaystyle{ \tfrac{p'}{q'} }[/math] ，对任意满足 [math]\displaystyle{ \tfrac{p}{q} \lt \tfrac{x}{y} \lt \tfrac{p'}{q'} }[/math] 的有理数，必有 [math]\displaystyle{ y \geq q + q' }[/math] 。
第 [math]\displaystyle{ n }[/math] 阶 Farey 数列有相邻两项 [math]\displaystyle{ \tfrac{p}{q} }[/math] 和 [math]\displaystyle{ \tfrac{p'}{q'} }[/math] ，则必有 [math]\displaystyle{ \left| \tfrac{p}{q} - \tfrac{p+p'}{q+q'} \right| \leq \tfrac{1}{q(n+1)} }[/math] 和 [math]\displaystyle{ \left| \tfrac{p'}{q'} - \tfrac{p+p'}{q+q'} \right| \leq \tfrac{1}{q'(n+1)} }[/math] 。
渐近性质
相邻项关系表明，对任意实数 [math]\displaystyle{ \xi }[/math] ，对任意给定正整数 [math]\displaystyle{ n }[/math] ，都存在有理数 [math]\displaystyle{ \tfrac{h}{k} }[/math] ， [math]\displaystyle{ 0\lt k\leq n }[/math] ，满足 [math]\displaystyle{ \left| \xi - \tfrac{h}{k} \right| \leq \frac{1}{k(n+1)} }[/math] 。也就是区间左右端点到中间分数的距离都有满足上式形式的上限，则不是中间分数时候也就总有至少一个满足上式。这表明 Farey 数列和最佳有理逼近问题有关。
考虑 [math]\displaystyle{ \left| \xi - \tfrac{h}{k} \right| \leq \frac{1}{k(n+1)} \lt \tfrac{1}{k^2} }[/math] ，其中 [math]\displaystyle{ n }[/math] 有任意性并且限制 [math]\displaystyle{ k }[/math] 的取值，可知对任意无理数 [math]\displaystyle{ \xi }[/math] ，都存在无穷多个不同有理数 [math]\displaystyle{ \tfrac{h}{k} }[/math] ，满足 [math]\displaystyle{ \left| \xi - \tfrac{h}{k} \right| \lt \frac{1}{k^2} }[/math] 。
对无理数 [math]\displaystyle{ \xi }[/math] ，如果其在第 [math]\displaystyle{ n }[/math] 阶 Farey 数列的相邻两项 [math]\displaystyle{ \tfrac{p}{q} }[/math] 和 [math]\displaystyle{ \tfrac{p'}{q'} }[/math] 之间，则以下两式必有至少一个成立：
- [math]\displaystyle{ \left| \xi - \tfrac{p}{q} \right| \lt \tfrac{1}{2 q^2} }[/math]
- [math]\displaystyle{ \left| \xi - \tfrac{p'}{q'} \right| \lt \tfrac{1}{2 q'^2} }[/math]
这一点可以被表示为三个 Ford 圆相切，并且覆盖了整个区间。
进一步地，以下三式必有至少一个成立：
- [math]\displaystyle{ \left| \xi - \tfrac{p}{q} \right| \lt \tfrac{1}{\sqrt5 q^2} }[/math]
- [math]\displaystyle{ \left| \xi - \tfrac{p'}{q'} \right| \lt \tfrac{1}{\sqrt5 q'^2} }[/math]
- [math]\displaystyle{ \left| \xi - \tfrac{p+p'}{q+q'} \right| \lt \tfrac{1}{\sqrt5 (q+q')^2} }[/math]
这可以进一步导出 Hurwitz 定理。
因此，对给定无理数，总是可以从任意给定两项之间按 Farey 中项插入的方式插入新的项，并使得结果更加接近该无理数，参考 Stern-Brocot 树（Farey 树）。
逐项关系
第 n 阶 Farey 数列首项是 0 ，第 2 项是 [math]\displaystyle{ \tfrac{1}{n} }[/math] 。如果给定连续两项 [math]\displaystyle{ \tfrac{p}{q},\tfrac{p'}{q'} }[/math] ，则再下一项满足 [math]\displaystyle{ \tfrac{ k p' - p }{ k q' - q }, k= \left\lfloor\tfrac{n+q}{q'}\right\rfloor }[/math] 。