查看“︁Farey 数列”︁的源代码

[[分类:连分数理论]]
[[分类:数列与级数]]
[[分类:以 Farey 命名]]
{{InfoBox
|name=法里数列
|eng_name=Farey sequence
}}
'''<ins>法里</ins>数列'''('''Farey sequence''')是对正整数 <math>n</math> ，在 0 到 1 之间的全体分母不大于 <math>n</math> 的[[最简分数]]从小到大排列构成的[[数列]]。（有时不要求范围）

== 定义 ==

对正整数 <math>n</math> ，按有理数的最简分数形式，从 <math>\tfrac{0}{1}</math> 到 <math>\tfrac{1}{1}</math> 以从小到大的顺序列出所有分数，则称为第 <math>n</math> 阶的'''<ins>法里</ins>数列'''('''Farey sequence''')。

注：可证明相邻三项之间有关系，且任意相邻两项间的分数都一定有更大的分母，因此同等价定义。

=== 等价定义 ===

记数列 <math>F_0 = \{\tfrac{0}{1}, \tfrac{1}{1}\}</math> ，并有递推关系：给定数列 <math>F_{n-1}, n\geq 1</math> ，将其所有项按原顺序构成新数列，计算其中左右相邻的两项 <math>\tfrac{p}{q}</math> 和 <math>\tfrac{p'}{q'}</math> 的[[中间分数]] <math>\tfrac{p+p'}{q+q'}</math> ，若满足分母 <math>q+q' \leq n</math> 则插入这两项之间，将这样得到的数列记为 <math>F_n, n \geq 1</math> 。则得到的 <math>F_n, n\geq 0</math> 就是第 <math>n</math> 阶的'''<ins>法里</ins>数列'''('''Farey sequence''')。

注：可证明新插入的分数一定是最简分数，因此和第一个定义等价。

== 性质 ==

=== Farey 中项 ===

在任意阶 Farey 数列的连续三项中，中间项总是外侧两项的[[中间分数]]，因此也称两个分数的中间分数为 '''Farey 中项'''。注意这个性质不像等价定义中的中间项一样要求是后插入的，先出现的项也一定是所有项插入后，外侧两项中间分数约分后的形式。

=== 连分数关系 ===

如果表示成[[连分数]]，对于第 <math>q</math> 阶 Farey 数列中的分数 <math>\tfrac{p}{q}</math> ，一定可以表示成 <math>[0; a_1, a_2, \dots, a_n, 1]</math> 和 <math>[0; a_1, a_2, \dots, a_n+1]</math> 两种等价形式，此时其相邻的两项一定恰好是 <math>[0; a_1, a_2, \dots, a_n]</math> 和 <math>[0; a_1, a_2, \dots, a_{n-1}]</math> ，根据大小决定左右。

=== 相邻项关系 ===

相邻两项 <math>\tfrac{p}{q}</math> 和 <math>\tfrac{p'}{q'}</math> ，有 <math>p'q - pq' = 1</math> 。

相邻两项 <math>\tfrac{p}{q}</math> 和 <math>\tfrac{p'}{q'}</math> ，对任意满足 <math>\tfrac{p}{q} < \tfrac{x}{y} < \tfrac{p'}{q'}</math> 的有理数，必有 <math>y \geq q + q'</math> 。

第 <math>n</math> 阶 Farey 数列有相邻两项 <math>\tfrac{p}{q}</math> 和 <math>\tfrac{p'}{q'}</math> ，则必有
<math>\left| \tfrac{p}{q} - \tfrac{p+p'}{q+q'} \right| \leq \tfrac{1}{q(n+1)}</math> 和
<math>\left| \tfrac{p'}{q'} - \tfrac{p+p'}{q+q'} \right| \leq \tfrac{1}{q'(n+1)}</math> 。

=== 渐近性质 ===

相邻项关系表明，对任意实数 <math>\xi</math> ，对任意给定正整数 <math>n</math> ，都存在有理数 <math>\tfrac{h}{k}</math> ， <math>0<k\leq n</math> ，满足 <math>\left| \xi - \tfrac{h}{k} \right| \leq \frac{1}{k(n+1)}</math> 。也就是区间左右端点到中间分数的距离都有满足上式形式的上限，则不是中间分数时候也就总有至少一个满足上式。这表明 Farey 数列和[[最佳有理逼近]]问题有关。

考虑 <math>\left| \xi - \tfrac{h}{k} \right| \leq \frac{1}{k(n+1)} < \tfrac{1}{k^2}</math> ，其中 <math>n</math> 有任意性并且限制 <math>k</math> 的取值，可知对任意无理数 <math>\xi</math> ，都存在无穷多个不同有理数 <math>\tfrac{h}{k}</math> ，满足 <math>\left| \xi - \tfrac{h}{k} \right| < \frac{1}{k^2}</math> 。

对无理数 <math>\xi</math> ，如果其在第 <math>n</math> 阶 Farey 数列的相邻两项 <math>\tfrac{p}{q}</math> 和 <math>\tfrac{p'}{q'}</math> 之间，则以下两式必有至少一个成立：
* <math>\left| \xi - \tfrac{p}{q} \right| < \tfrac{1}{2 q^2}</math> 
* <math>\left| \xi - \tfrac{p'}{q'} \right| < \tfrac{1}{2 q'^2}</math>
这一点可以被表示为三个 [[Ford 圆]]相切，并且覆盖了整个区间。

进一步地，以下三式必有至少一个成立：
* <math>\left| \xi - \tfrac{p}{q} \right| < \tfrac{1}{\sqrt5 q^2}</math> 
* <math>\left| \xi - \tfrac{p'}{q'} \right| < \tfrac{1}{\sqrt5 q'^2}</math> 
* <math>\left| \xi - \tfrac{p+p'}{q+q'} \right| < \tfrac{1}{\sqrt5 (q+q')^2}</math>
这可以进一步导出 [[Hurwitz 定理]]。

因此，对给定无理数，总是可以从任意给定两项之间按 Farey 中项插入的方式插入新的项，并使得结果更加接近该无理数，参考 [[Stern–Brocot 树|Stern–Brocot 树（Farey 树）]]。

=== 逐项关系 ===

第 n 阶 Farey 数列首项是 0 ，第 2 项是 <math>\tfrac{1}{n}</math> 。如果给定连续两项 <math>\tfrac{p}{q},\tfrac{p'}{q'}</math> ，则再下一项满足 <math>\tfrac{ k p' - p }{ k q' - q }, k= \left\lfloor\tfrac{n+q}{q'}\right\rfloor</math> 。