丟番圖逼近

丢番图分析（英語：Diophantine approximation）是数论的一个分支。最经典的丢番图逼近主要用於有理数逼近实数，亦即实数的有理逼近相关问题。其中有理数一般用分数形式表达，且一律要求分子为整数，分母为正整数，通常要求是既约分数。

丢番图逼近的名称源于古希腊数学家丢番图。这是因为有理逼近可以归结为求不等式整数解的问题，而求方程整数解的问题一般称为丢番图方程（或不定方程），故而得名。事实上，丢番图逼近与不定方程的研究确有颇多相关。

丢番图逼近的首要问题是寻求实数的最佳（有理）丢番图逼近，简称最佳逼近。具体来说，对于一个实数 $\alpha$ ，希望找到一个“最优”的有理数 $p/q$ 作为 $\alpha$ 的近似，使在分母不超过 $q$ 的所有有理数中， $p/q$ 与 $\alpha$ 的距离最小。这里的“距离”可以是欧氏距离，即两数之差的绝对值；也可以用 $|q\alpha -p|$ 等方式度量。满足此类要求的有理数 $p/q$ 称为实数 $\alpha$ 的一个最佳逼近。关于如何寻找实数的最佳逼近及相关论题，已于18世纪随着连分数理论的发展得到基本解决。

其后，该领域的主要注意力转向对有理逼近的误差进行估计、度量，以给出尽可能精确的上下界（一般用分母的函数表示）。作为分母的函数, 这种上下界的阶与 $\alpha$ 的性质密切相关。当 $\alpha$ 分别为有理数、代数数、超越数时，其最佳逼近误差下界的阶是不同的。基于这种思想，刘维尔在1844年建立了有关代数数逼近的一个基本结论，并由此具体地构造出了一个超越数（参见刘维尔数），证明了它的超越性。这在人类历史上尚属首次。由此可见，丢番图逼近与数论的另一分支——超越数论紧密相关。

除了上述最经典的单个实数的有理逼近问题，该领域还包括多个实数的联立逼近，非齐次逼近，实数的代数数逼近，一致分布（均匀分布）等方面。甚至连p进数上的丢番图逼近也有颇多研究。

实数的最佳丢番图逼近

有理数与实数的距离

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

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

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

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

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

此时不要求 $p,q$ 互素。

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

问题的提法

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

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

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

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

|\alpha -p/q|<|\alpha -p'/q'|

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

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

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

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

结论

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

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

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

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]

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

第二类最佳逼近

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

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

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

第一类最佳逼近

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

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

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

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

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

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

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

例子

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

[2;1,2,1,1,4,1,1,6,1,1,8,1,\ldots \;]

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

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

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

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……，其连分数表达式为

[3;7,15,1,292,1,1,1,2,1,3,1,14,\ldots ]

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

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

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

[1;1,1,2,1,3,14\ldots ]>[1,1,1]=3/2>113/106

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

刘维尔定理与Roth定理

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

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

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

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

均匀分布

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