丟番圖逼近

丟番圖分析（英語：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$ 時，此比例收斂於我們所「期望值」的值。赫爾曼·外爾證明了一個基本結論：均勻分佈等價於該序列元素的指數和有上界。這表明丟番圖逼近與指數和相消的一般問題密切相關，而後者在解析數論的誤差項估計中無處不在。