丢番图逼近

有理数与实数的距离

无论何种丢番图逼近问题, 都需要定义“距离”。对于实数的有理逼近，要考虑的是有理数 ${\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的任何有理数都更接近π（依欧氏距离），可见密率的精确性。

丢番图逼近理论的基础之一是刘维尔的一个关于代数数逼近的定理：

定理：设无理数${\displaystyle \alpha }$ 是一个整系数${\displaystyle n}$ 次多项式的根，则存在常数${\displaystyle A>0}$ ，使得对任意两整数 ${\displaystyle p,q>0}$  恒有

${\displaystyle \left|\alpha -{\frac {p}{q}}\right|>{\frac {A}{q^{n}}}}$ 

刘维尔定理可用于构造超越数。在这之前，数学家们已利用连分数导出关于平方根与其它二次无理数的许多逼近性质。这个结果后来由Axel Thue等人改进，并导致Roth定理：对于代数数${\displaystyle \alpha }$ ，将刘维尔定理中的指数由其次数${\displaystyle n}$ 缩至任意的${\displaystyle 2+\epsilon }$ （其中${\displaystyle \epsilon >0}$ ）。之后Schmidt又将此结果推广到一致逼近。这些命题的证明颇为困难，而且不能得到${\displaystyle A}$ 的确切数值，在应用上有所缺憾。

另一个主题是模1的均匀分布理论。取一实数序列 ${\displaystyle a_{1},a_{2},\ldots }$  并考虑其真分数部分；或抽象地说，将其看作 ${\displaystyle \mathbb {R} /\mathbb {Z} }$ ，即拓扑学中所说的一维圆环 ${\displaystyle \mathbb {S} ^{1}}$ 上的数列。对圆环上的任一段区间，我们研究有限集 ${\displaystyle \{a_{n}:n\leq N\}}$  中有多大比例落在该区间内，并考虑这个比例与区间长度之间的关系。一个序列均匀分布意味着当 ${\displaystyle N\rightarrow +\infty }$  时，此比例收敛于我们所“期望”的值。赫尔曼·外尔证明了一个基本结论：均匀分布等价于该序列元素的指数和有上界。这表明丢番图逼近与指数和相消的一般问题密切相关，而后者在解析数论的误差项估计中无处不在。

在Roth定理以后，丢番图逼近论的主要进展与超越理论相关。均匀分布关乎分布的不规则性，因而带有组合学的本性。丢番图逼近论中仍有陈述简单却悬而未解的问题，例如李特尔伍德猜想：对任意两个实数 ${\displaystyle \alpha ,\beta }$ ,

${\displaystyle \liminf _{n\to \infty }\ n\,\Vert n\alpha \Vert \,\Vert n\beta \Vert =0}$ 

其中${\displaystyle \Vert \,\Vert }$ 表示到最近整数的距离。

• Lang, S. Introduction to Diophantine Approximations New Expanded Edition. Springer-Verlag. 1995.   引文格式1维护：冗余文本 (link)