丟番圖逼近

无论何种丢番图逼近问题, 都需要定义“距离”。对于实数的有理逼近，要考虑的是有理数 ${\displaystyle p/q}$ 与实数 ${\displaystyle \alpha }$ 的距离。对此一般有两种定义方式，其一是非常自然的欧氏距离 ${\displaystyle |\alpha -p/q|}$，其二是 ${\displaystyle |q\alpha -p|}$ 第二种定义方式是有理数所独有的，在丢番图逼近的理论和实践中都很常用，不过这样定义的距离并非一个度量。

这两种距离也可看作只由分母 ${\displaystyle q}$ 决定的。此时，上述第二种定义变为

${\displaystyle \min\{p\in \mathbb {Z}$ :|q\alpha -p|\}=||q\alpha ||}

上式右端的记号在丢番图逼近中很常用。沿用此记号，第一种定义变为

${\displaystyle \min\{p\in \mathbb {Z}$ :|\alpha -p/q|\}=||q\alpha ||/q}

此时不要求 ${\displaystyle p,q}$ 互素。

对于实数的最佳逼近问题，依“距离”的定义不同，有第一类和第二类之分，二者的结论有所不同。未加限定时，“最佳逼近”一词一般指的是第一类最佳逼近。

在本节中，对有理数 ${\displaystyle p/q}$，我们用“优”一词形容它与给定实数 ${\displaystyle \alpha }$ 的距离更接近，此处的“距离”一般是按照1.1节给出的两种定义方式之一。当 ${\displaystyle \alpha }$ 为无理数时，无论按上述哪一种距离，只要分母 ${\displaystyle q}$ 足够大，${\displaystyle p/q}$ 总能与 ${\displaystyle \alpha }$ 任意接近。因此，单纯讨论“最优”（意即与 ${\displaystyle \alpha }$ 最接近的）有理数意义不大，还需要对有理数的范围，主要是分母的范围加以限制。这样，给定一个实数 ${\displaystyle \alpha }$ 后，就产生了以下三个自然的问题：

1. 对于哪些有理数 ${\displaystyle p/q}$，其在分母不超过 ${\displaystyle q}$ 的所有有理数中是最优的？
2. 对于给定的正整数，在分母不超过它的所有有理数中，最优的是哪个？（如果有多个，一般取分母最小者）
3. 对于一个有理数（通常考虑的是最佳逼近），比它更优的有理数中分母最小的是哪个？

问题1正是经典丢番图逼近领域的一个核心问题，也是后两个问题的基础；问题2可视作问题1的扩展，从某些角度看它的提法甚至更为自然；问题3则可看作问题2的某种反问题。

丢番图逼近领域的最佳逼近一词，一般就指符合问题1中条件的有理数。两种距离都可以考虑，分别对应两类最佳逼近。具体来说，给定一个实数 ${\displaystyle \alpha }$，称有理数 ${\displaystyle p/q}$ 为 ${\displaystyle \alpha }$ 的第一类最佳逼近，当且仅当对每个与 ${\displaystyle p/q}$ 不同的有理数 ${\displaystyle p'/q'}$，在 ${\displaystyle q'\leq q}$ 时恒有

${\displaystyle |\alpha -p/q|<|\alpha -p'/q'|}$

如果其余条件不变，最后的不等式变为

${\displaystyle \left|q\alpha -p\right|<\left|q^{\prime }\alpha -p^{\prime }\right|}$

则称 ${\displaystyle p/q}$ 为 ${\displaystyle \alpha }$ 的第二类最佳逼近。显然，第二类最佳逼近一定是第一类的，反之则未必。例如对于2/3来说，1/2是第一类最佳逼近，但不是第二类的。

对于问题2, 3，依“距离”的定义不同，也有类似的第一类和第二类之分。问题1解决后，不难得到问题2, 3的结论。事实上，后两个问题中所求的有理数一定是一个最佳逼近。

实数最佳逼近问题与连分数理论有密切联系，后者提供了计算最佳逼近的理论依据和具体算法。下面总假设实数 ${\displaystyle \alpha }$ 的简单连分数表达式为

${\displaystyle \alpha =[a_{0};a_{1},a_{2},\,\ldots ,a_{n}\,\ldots ]}$

再设C_k = p_k/q_k为 ${\displaystyle \alpha }$ 的k阶渐进分数（即收敛子），C_{k, t} = p_{k, t}/q_{k, t}的第t个k阶中间渐近分数（简称中间分数，又名半收敛子，参见连分数#半收敛），其中

${\displaystyle p_{k,t}=tp_{k-1}+p_{k-2},\ q_{k,t}=tq_{k-1}+q_{k-2},\ C_{k,t}=p_{k,t}/q_{k,t}=[a_{0};a_{1},\,\ldots ,a_{k-1},t]}$

习惯上认为中间分数不包括渐近分数，因此，上述记号中一般要求 ${\displaystyle t<a_{k},\ t\in \mathbb {N} ^{*}}$ 此时 ${\displaystyle C_{k,t}}$ 总在 ${\displaystyle C_{k-1}}$ 和 ${\displaystyle C_{k}}$ 之间。

第二类最佳逼近的结论比较简单：实数的第二类最佳逼近恰是它的简单连分数的所有渐近分数。此时需要注意：${\displaystyle \alpha }$ 为有理数时，它的简单连分数展开要取最后一位不是1的那个。例如2/3的连分数要写成[0; 1, 2]而不是[0; 1, 1, 1]，故此时[0; 1, 1]=1/2不是2/3的渐近分数。事实上，1/2确实不是2/3的第二类最佳逼近。另外，此论断有一个平凡的例外：若${\displaystyle a_{k}=1}$，${\displaystyle \alpha }$ 的第0个渐近分数并非第二类最佳逼近。

对于问题2，给定正整数 ${\displaystyle M>1}$，设 ${\displaystyle q_{k-1}\leq M<q_{k}}$，则在分母不超过M的有理数中，最优的是第 ${\displaystyle k-1}$ 个渐近分数 ${\displaystyle C_{k-1}}$

对于问题3，给定一个第二类最佳逼近，它一定是某个渐近分数 ${\displaystyle C_{k-1}}$（${\displaystyle \alpha }$ 为半整数时有例外，此时 ${\displaystyle a_{0}+1}$ 也第二类最佳逼近，但对结论没有本质影响），那么比它更优的有理数中分母最小的是 ${\displaystyle C_{k}}$。

对于第一类最佳逼近，问题要复杂一些。此时渐近分数当然仍是最佳逼近，但某些中间分数亦是。具体来说，

• ${\displaystyle t>a_{k}/2}$时, ${\displaystyle C_{k,t}}$ 是第一类最佳逼近；
• ${\displaystyle t<a_{k}/2}$时, ${\displaystyle C_{k,t}}$ 不是第一类最佳逼近；
• ${\displaystyle t=a_{k}/2\in \mathbb {N} ^{*}}$时，仅考虑连分数的前k项已不足以判断，需要特殊的判定准则。此时，${\displaystyle C_{k,t}}$ 是第一类最佳逼近，当且仅当

${\displaystyle [a_{k+1};a_{k+2},\,\ldots ]>q_{k-1}/q_{k-2}}$

另一方面，第一类最佳逼近一定是渐近分数或中间分数。为使此论断无例外，需补充定义-1阶渐进分数为1/0，这样可以考虑0阶的中间分数。这裡还需要特别注意： ${\displaystyle \alpha }$ 为有理数时，它的简单连分数展开要取最后一位是1的那个。例如2/3的连分数要写成[0;1, 1, 1]而不是[0;1, 2]，故此时[0; 1, 1]=1/2是2/3的渐近分数。事实上，1/2确实是2/3的第一类最佳逼近。

总结起来，${\displaystyle \alpha }$ 的第一类最佳逼近恰有三类：

• 渐近分数 ${\displaystyle C_{k}}$ (${\displaystyle a_{1}=1}$ 时不包含 ${\displaystyle C_{0}}$) ；
• 中间分数 ${\displaystyle C_{k,t},}$其中${\displaystyle t\in \mathbb {N} ^{*},\ a_{k}/2<t<a_{k};}$
• 中间分数 ${\displaystyle C_{k,a_{k}/2},}$其中${\displaystyle a_{k}/2\in \mathbb {N} ^{*},\ [a_{k+1};a_{k+2},\,\ldots ]>q_{k-1}/q_{k-2}}$

问题2, 3的结论与上一小节类似。

考虑自然对数底 e=2.718281828459045235……，其连分数表达式为

${\displaystyle [2;1,2,1,1,4,1,1,6,1,1,8,1,\ldots \;]}$

它的第二类最佳逼近依次是：

${\displaystyle 3,{\frac {8}{3}},{\frac {11}{4}},{\frac {19}{7}},{\frac {87}{32}},\ldots \,}$

它的第一类最佳逼近依次是：

${\displaystyle 3,{\frac {5}{2}},{\frac {8}{3}},{\frac {11}{4}},{\frac {19}{7}},{\frac {30}{11}},{\frac {49}{18}},{\frac {68}{25}},{\frac {87}{32}},{\frac {106}{39}},\ldots \,}$

和渐近分数一样，最佳逼近一般也按分母由小到大排列。

又如圆周率 π=3.145926535897……，其连分数表达式为

${\displaystyle [3;7,15,1,292,1,1,1,2,1,3,1,14,\ldots ]}$

它的前几个渐近分数如下：

${\displaystyle 3,{\frac {22}{7}},{\frac {333}{106}},{\frac {355}{113}},{\frac {103993}{33102}}}$

其中的22/7正是约率，而355/113正是密率。按上面的结论，由于292为偶数，且

${\displaystyle [1;1,1,2,1,3,14\ldots ]>[1,1,1]=3/2>113/106}$

故355/113之后的下一个第一类最佳逼近是${\displaystyle C_{4,292/2}=52163/16604}$。这说明355/113比分母小于16604的任何有理数都更接近π（依欧氏距离），可见密率的精确性。