動機
平方根的連分數常常從某處開始重複。例如,二的平方根中重複出現的數字二是精確的算術事實,而不是從很長的小數展開中推測出來的數值規律。我們希望給出一個證明,既解釋為甚麼會出現重複,也解釋為甚麼一個重複的連分數必然表示二次無理數。
這裏有兩種不同的機制。一個重複的塊是一個整係數分式線性變換,它的不動點滿足一個二次方程。反方向上,二次無理數具有整數根式座標,但這些座標起初並沒有界。我們先證明它的共軛完全商會進入某個區間;只有這樣,座標才落在一個有限集合中。保持這一順序,可以避免作出「無窮連分數由遞推生成,所以必然最終重複」這種缺乏依據的斷言。
本文使用漸近分數與完全商公式。這裏的數都是實數。連分數是簡單連分數:首項是整數,之後每個數字都是正整數。全文所說的取整判定都是精確的,而不是浮點捨入。
定義
定義 11.2.1
(完全商與簡約二次無理數)
對於無理數 ,令 ,,。則對 有 。如果連分數的數字從某個下標起開始重複,則稱它最終週期;如果從下標零起就重複,則稱它純週期。
實二次無理數是某個二次整係數多項式的無理根。它的另一個根稱為共軛,記作 。當 且 時,稱該二次無理數是簡約的。共軛保持有理數不變,並把其二次域中的正平方根映為負平方根。
定理
定理 11.2.2
(最終週期性刻劃實二次無理數)
一個無理實數的簡單連分數最終週期,當且僅當它是二次的。重複可以透過某個完全商的重複來精確檢測;對於二次無理數,還可以透過某個整數根式狀態的重複來檢測。
定理 11.2.3
(簡約給出有限且可逆的狀態系統)
每個二次無理數從某個下標起,其完全商都是簡約的。一個二次無理數的簡單連分數是純週期的,當且僅當它是簡約的。對於表示
這裏 為正的非平方整數。每個簡約狀態都滿足 及 。完全商映射在固定 的簡約整數狀態這一有限集合上是一個置換。
證明思路
週期塊給出二次不動點
證明
(塊矩陣的不動點)
運算 的矩陣是 ,行列式為 。始於首項之後的週期只使用正數字。設其乘積為 。它的左下角元素 為正:長度為一的塊顯然如此,而再乘以一個由正數字構成的矩陣,所需元素的正性得以保持。因此,處於週期起點的完全商 滿足
重複尾部的相等性來自無窮簡單連分數的唯一性。原來的 是 的分式線性表達式,其係數為整數、行列式為 ,這是在前面接上有限前綴得到的。這樣的變換及其逆變換都保持有理性。因此 是無理數,上面所示的多項式次數為二,而 屬於同一個二次域,是二次的。如果重複從零開始,則先轉到後面的某個完全商;這樣就不必對初始數字的正負號作任何假設。
把每個二次無理數寫成整數根式座標
證明
(整數根式遞推)
設 是整係數方程且 。其判別式 為正且非平方;否則它的根就不會是實無理數。根據所取的根,二次公式把 寫成 ,其中 ,或 。兩種情形下 都整除 。開始時允許 為負。
對下一個完全商做有理化,得到精確的遞推式
整除性假設使 成為整數:模 有 。同一個顯式等式也給出新的整除條件。它的分子非零,因為 不是平方數。於是遞推在整數座標中持續進行,但僅憑這一觀察還不能說明狀態集合是有限的。
共軛最終必須變為負數
證明
(後期的共軛落在 內)
令 ;共軛給出 。沒有任何 是有理數。一旦在某個下標 處有 ,則由於 ,下一個 嚴格位於 與零之間。這個區間隨後被保持。
反之,假設對所有 , 都保持為正。下一項為正迫使 ,再下一項為正又迫使 。因此 在每個下標處都與 有相同的簡單連分數數字 。於是 與 會有完全相同的無窮多個數字,從而必須相等,這與二次共軛矛盾。
為完整起見,這裏用到的唯一性並不依賴小數展開。一個有限的正數字前綴把尾部 映入一個區間,其端點是該前綴的漸近分數與尾部取一時的值。行列式恆等式顯示該區間長度至多為 ,其中 是最後一個漸近分數的分母。這些分母無界增長,因為它們的遞推是在前一個分母的正整數倍上再加上一項。因此,共享所有前綴的兩個數之間的距離為零。這一論證同樣適用於被設想具有所有這些正尾部的共軛。
證明透視
有限性在週期性論證中的位置
整數座標給出一個離散集合,但還不是有界集合。共軛為負使狀態成為簡約狀態。簡約狀態所滿足的不等式再對兩個整數座標加以界定。最後,一個重複的狀態給出完全相同的後續狀態,因為下一個數字恰好是所表示的數的精確取整。每一步都提供了前一步所沒有的條件;僅憑離散性無法確立重複。
簡約座標有界,因而最終重複
證明
(簡約座標有界)
對於簡約狀態 與 ,差 為正,所以 。不等式 與 給出 以及 。此外 。因此,即使還沒有施加整除性或其餘不等式 ,可能的整數對 也只有有限多個。
由前面的共軛論證,所有足夠靠後的狀態都是簡約的。因此其中有兩個狀態具有相同的數對。遞推(包括其中的取整判定)是確定性的,所以它們此後的狀態與數字永遠重複。這就證明了二次無理數蘊含最終週期,並且無需估計簡約從何時開始。
為甚麼簡約的起點沒有非週期前綴
證明
(簡約狀態的一個置換)
對固定的 ,考慮所有滿足所述整除條件及兩個簡約不等式的整數狀態。我們已經證明這個有限集合被映入自身。它還具有唯一的簡約前驅。
事實上,若 是簡約的且其共軛為 ,則其前一個完全商必為 ,其共軛為 。要求 ,便確定了
端點不是整數,因為 是無理數。這個 還給出 及 。該前驅屬於同一個整數狀態集合:取 及 。則 是正整數,直接有理化得 ,且 整除 。它的簡約不等式已經內置於 的選取之中。唯一性來自同一個共軛區間。因此該映射是有限集合上的置換,所以每個簡約的起始狀態從其第一步起就是週期的。
反之,純週期無理數的首項為正:否則,其重複的首項會在更靠後的下標處違背正性。因此它大於一。它的完全商序列與共軛序列都是週期的,而後者最終落在 中。週期性把這一區間條件帶回到初始共軛。這就證明了純週期性的判別準則。
精確證書,以及有限界沒有保證甚麼
在簡約狀態中, 為正。因此,要判斷 是否大於整數 ,只需比較正平方根 與整數 。若後者為負,比較立即確定;若後者非負,則比較 與它的平方。由於 不是平方數,不會出現相等。這使取整判斷完全建立在整數運算上,無需把某個足夠精確的小數當作證書的一部分。
因此,驗證一個聲稱的週期,可以列出其中的整數對,逐項核對遞推和取整不等式,並展示回到第一個整數對。固定 後,狀態的表示唯一:兩個 相等,會迫使有理部分和無理係數分別相等,從而兩個整數對相同。若返回之前的各對互異,所列狀態週期便具有最小長度。若數字存在更短週期,無窮展開的唯一性又會給出相同的完全商,因而迫使狀態更早返回。
令 。上述有界矩形最多包含 個整數對,所以它給出每個簡約週期長度的上界,儘管許多候選對不滿足整除或簡約不等式。這個界沒有控制任意初始完全商進入簡約狀態之前需要多少步,也沒有證明算法關於 的二進制長度是多項式時間的:與 成比例的界,對於該輸入長度可能是指數級的。證明給出了精確終止和可核驗的週期,同時保留了與更精細計算估計之間的區別。
例題詳解
例題 11.2.4
(二的平方根有前綴,但一加上它則是簡約的)
從 及 開始。下一個狀態是 ,表示 。它的數字是二,而遞推又回到同一個狀態。於是 。它的共軛 小於 ,所以最初的平方根不是簡約的,其連分數也不是純週期的。相反, 的共軛 位於 中,並且 等於 。區別在於起始完全商,而不在於某處是否存在週期。
例題 11.2.5
(十三的平方根的精確五步週期)
從 開始。相繼的整數狀態及其數字為
例如,第一次更新用到 ;最後一次用到 與 。每次取整都來自 ,以及所示的整數分子與分母。回到起點之前的五個狀態兩兩不同。因此 ,且這個完全商循環的長度為五。僅僅觀察到小數中出現五個重複的塊,並不能提供這些精確的狀態相等關係。
例題 11.2.6
(由週期塊還原無理數)
對於 ,塊矩陣為 。它的不動點方程是 ,所以正根為 。它的值位於一與二之間,而它的共軛 位於 與零之間。簡約準則確認所取的根具有純週期;負根不可能是一個正的完全商。下一個完全商是 ,其數字為二,再下一個完全商又是 。僅有二次方程還不夠,還必須配合區間資訊來選出所要的根。
常見錯誤
反例模式
確定性的遞推不一定是週期的
整數上的遞推 是確定性的,卻永不重複。在證明簡約不等式之前,整數根式遞推同樣在一個無限集合上取值。有限狀態這一步既需要整數性,也需要有界性。四捨五入後的數值狀態又是另一回事:表面上的數值回歸並不能證明兩個二次無理數相等。
常見錯誤
(二次無理數不一定是純週期的)
二次無理數不一定以純週期開始, 就說明了這一點:它的首項 不重複,因為共軛 小於 ,所以 不是簡約的。要到後面的完全商,即 ,週期才開始。
常見錯誤
(有理數輸入不是週期的例子)
有理數在這個算法下會終止;它們另一種以有限的末項表示的寫法,並不使它們成為無理週期的例子。
常見錯誤
(共軛不保持不等式)
證明利用共軛來界定狀態,而不是斷言共軛保持不等式。共軛可以改變正負號與大小順序:,但它的共軛 是負數。所以每個共軛遞推與區間都單獨做了檢驗。
快速檢查
快速檢查
(對於 ,每個滿足 及 的整數對是否都必須出現在平方根的循環中?)
把矩形中整數對的個數,與上面算出的循環長度比較。
解答 · 答案
不必。整除性、簡約不等式以及屬於該特定軌道,都會施加進一步的限制。矩形包含 、 的 個整數對,但 的循環只用到其中五個。例如 位於矩形內,可是 。這個矩形只是候選狀態的一個有限上界,而不是對單個週期的分類。
練習
快速檢查
(從 出發,計算 的完全商狀態,直到第一次回歸。指出哪一個起始完全商是簡約的。)
用 代入 及 。
解答 · 答案
由於 ,下一個狀態是 ,數字為一。再下一個是 ,數字為二,它回到 。因此 。它的第一個完全商 的共軛 位於 中,所以是簡約的。初始共軛 不在該區間內。
快速檢查
(利用矩陣方程求出 所表示的正無理數。驗證它的兩個簡約不等式及其兩個精確數字。)
計算 ,再解不動點方程。
解答 · 答案
矩陣乘積為 ,給出 。正根為 ,其共軛 位於 中。它的整數部分為二。下一個完全商 的整數部分為一,再下一個完全商回到 。這就驗證了精確的週期與根的選取。
快速檢查
(設 。求 所滿足的二次方程。解釋為甚麼 是最終週期的而不是純週期的。)
把 代入 。
解答 · 答案
方程 經倒數代換後變為 。正根為 ,位於零與一之間。它的連分數以零開頭,此後每個數字都是一。它不可能是純週期的,因為重複其初始的零會使零出現在後面的數字之中。它也不是簡約的,因為它小於一。
快速檢查
(解釋為甚麼在一個正的二次尾部前面接上任何有限的容許簡單連分數前綴,所得的無理數仍屬於同一個二次域。說明為甚麼對這樣的尾部,分式線性變換的分母不會為零。)
把前綴寫成分式線性映射,其矩陣的行列式為 。
解答 · 答案
一個前綴給出 ,其係數為整數、行列式為 ,所以它的值位於該尾部所在的二次域中。若該值是有理數 ,則方程 要麼使 成為有理數,要麼迫使兩個係數都為零;後者與行列式非零矛盾。分母在無理數 處不可能為零,因為那將給出一個非平凡的有理線性方程; 同樣被行列式排除。因此所接上的值是一個次數為二的域中的無理元素,所以是二次的。
相關筆記
Pell 方程的單元在丟番圖(Diophantine)的背景下使用與週期性相關的遞推。本定理確立了精確的最終週期性與純週期性;它沒有給出最小週期長度的精確界,沒有證明完整的 Hurwitz 逼近定理,也沒有分類所有二次範數。