丟番圖逼近

维基百科,自由的百科全书
跳转至: 导航搜索

丢番图逼近又名丢番图分析,是数论的一个分支。最经典的丢番图逼近主要研究用有理数逼近实数,亦即实数的有理逼近的相关问题。在本条目中,所出现的有理数一般用分数形式表达,且一律要求分子为整数,分母为正整数,通常要求是既约分数

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

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

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

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

实数的最佳丢番图逼近[编辑]

有理数与实数的距离[编辑]

无论何种丢番图逼近问题,都需要定义“距离”。对于实数的有理逼近,要考虑的是有理数p/q与实数α的距离。对此一般有两种定义方式,其一是非常自然的欧氏距离|\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,我们用“优”一词形容它与给定实数α的距离更接近,这裡的“距离”一般是1.1节给出的两种定义方式中的一种。当α为无理数时,无论按上述哪一种距离,只要分母q足够大,p/q总能与α任意接近。因此,单纯讨论“最优的”(意即与α最接近的)有理数意义不大,还需要对有理数的范围,特别是分母的范围加以限制。这样,给定一个实数α后,就产生了以下三个自然的问题:

  1. 对于哪些有理数p/q,其在分母不超过q的所有有理数中是最优的?
  2. 对于给定的正整数,在分母不超过它的所有有理数中,最优的是哪个?(如果有多个,一般取分母最小者)
  3. 对于一个有理数(通常考虑的是最佳逼近),比它更优的有理数中分母最小的是哪个?

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

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

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

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

\left|q\alpha -p\right| < \left|q^\prime\alpha - p^\prime\right|,

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

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

结论[编辑]

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

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

再设Ck = pk/qkα的k阶渐进分数(即收敛子),Ck,t = pk,t/qk,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}^*. 此时Ck,t总在Ck-1, Ck之间。

第二类最佳逼近[编辑]

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

对于问题2,给定正整数M>1,设qk-1≤M<qk,则在分母不超过M的有理数中,最优的是第k-1个渐近分数Ck-1.

对于问题3,给定一个第二类最佳逼近,它一定是某个渐近分数Ck-1α为半整数时有例外,此时a0+1也第二类最佳逼近,但对结论没有本质影响),那么比它更优的有理数中分母最小的是Ck.

第一类最佳逼近[编辑]

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

  •  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阶的中间分数。这裡还需要特别注意α为有理数时,它的简单连分数展开要取最后一位是1的那个。例如2/3的连分数要写成[0;1,1,1]而不是[0;1,2],故此时[0;1,1]=1/2是2/3的渐近分数。事实上,1/2确实是2/3的第一类最佳逼近。

总结起来,α的第一类最佳逼近恰有三类:

  • 渐近分数C_ka_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}.

其中的355/113正是密率。按上面的结论,由于292为偶数,且

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

故355/113之后的下一个第一类最佳逼近是C4,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定理:將劉維爾定理中的指數n由代數數的次數縮減到任意的2+ε(其中ε>0);之後Schmidt將此推廣到同步逼近。這些證明頗困難,而且不能得到明確的上界,這在應用上是一大缺憾。

均勻分佈[编辑]

另一個主題是模1的均勻分佈理論。取一實數序列a_1, a_2, \ldots並考慮其真分數部份;或者抽象地說是考慮\mathbb{R}/\mathbb{Z},這在拓撲學上是個一維圓環\mathbb{S}^1。對圓環上的任一段區間,我們研究有限集\{a_n : n \leq N \}中有多大比例落在該區間,並考慮此比例與區間長度之關係。「均勻分佈」意味著當N \rightarrow +\infty,此比例將趨近我們「期望」的值。Hermann Weyl證明了這等價於該序列元素的指數和之上界,這表明了丟番圖逼近與指數和相消的一般問題密切相關,後者在解析數論的誤差項估計中無所不在。

其它面向[编辑]

在Roth定理以後,丟番圖逼近的主要進展與超越理論相關。均勻分佈關乎分佈的不規則性,因而帶有組合學的本性。丟番圖逼近中仍有陳述簡單卻懸而未解的問題,例如李特伍德猜想。

文獻[编辑]

  • Lang, S. Introduction to Diophantine Approximations New Expanded Edition. Springer-Verlag. 1995. ISBN 0-387-94456-7.