從不定方程到數字的宿命——Thue的偉大定理

經過最近半個月的持續努力 , 我終於完成瞭在高中時的一大願望 .

我來賣個萌

不要打我qwq , 雖然這個標題看上去非常的民科 . 但內容卻涉及到貨真價實的二十世紀的數學 !


讓我們從好多個小故事開始介紹我們的旅程 , 當然 , 不定方程也叫丟番圖方程 , 就是強調隻研究這種方程的整數解 , 比如真 · 小學二年級學過的 :

【一群小朋友排隊放學 , 三人一行多兩個 , 五人一行多三個 , 請問一共有多少個小朋友呢 ? 】

這個問題轉化成數學的語言 , 就是 n 個小朋友 , n=3a+2=5b+3 , 已知 n,a,b 都是正整數 , 求 n 的可能值 .

非常簡單 , 註意到 n-8=3(a-2)=5(b-1) , n-8 就是 3,5 的倍數 , 也就是說 n-8 必須是它們公倍數 15 的倍數 , 於是 n=15k+8 , 小朋友的個數可能是 8,23,38,53cdots .

可能你還在因解決瞭這個簡單的問題在心裡偷笑 : 哼哼 , 列出方程一看 , 就是一次的嘛 , 次數這麼低 , 怎麼能難得住號稱天才 ( 琪露諾 ) 的我呢 ? ( 大霧 ) 當然沒有這麼簡單 , 請看 :

【請找出所有邊長為正整數的直角三角形】

你的內心想法 : 我小學一年級就學過瞭 , 勾股方程的所有本原 ( 就是互質 ) 的解可以寫成 (x^2-y^2)^2+(2xy)^2=(x^2+y^2)^2 , 隻要乘一個正整數 , 就可以自然得到所有解瞭 , cyb醬怎麼連這麼簡單的題目都不會 , 好笨啊 .

【請找出所有含 60^circ 角的整數邊長三角形】

這也難不倒你 , 知乎上還真有人問過這個問題 , 回答說先利用餘弦定理 , a^2-ab+b^2=c^2 所以還是二次的不定方程 , 經過奇奇怪怪的操作可以證明本原解是 a=-m^2-2mn+3n^2 , b=-m^2+2mn+3n^2 , c=m^2+3n^2 , 和勾股問題類似 , 所有的解還是它們的倍數 , 不過這次不一定是整數倍瞭 , 但經過簡單的討論還是可以算出來 !

上面三個問題有一個共同點 , 就是最後所有的整數解都可以用簡單的式子表示出來 , 數學傢們發現 , 變量很少的二次的不定方程 , 解起來都特別簡單 , 又例如著名的Pell方程 :

【小明和小紅每個人都有一些糖果 , 它們都有正方形的盤子 , 可以將自己的糖果整整齊齊擺成正方形 ( 也就是個完全平方數 ) , 小紅對小明說 , 我的糖果比你的兩倍還多一顆 , 請問分別可能是多少糖果 ? 】

a1b3e0104a1034e74e5fa31c932faaf4簡單的例子 , 猜猜看糖都是什麼口味的

當然 , 我們可以將問題轉化成 x^2-2y^2=1 , 它的所有解和 3+2sqrt 2 關系密切 , 且看下面這個對應 : 原方程的所有解是 (3,2),(17,12),(99,70)cdots , 而 (3+2sqrt2)^2=17+12sqrt2 , (3+2sqrt2)^3=99+70sqrt2 還有更高次的冪 , 原因是什麼 , 學過的讀者自然明白 , 沒學過的讀者也不是一兩句話能說明白的 .

姑且就從這裡看出 , 原方程可能有很大的解 . 比如 , 小明可能有 723573111879672^2 顆糖而小紅有 1023286908188737^2 顆糖 , 這非常過分 , 因為小紅的糖總質量加起來可能比太陽的質量還要大 .

另外還有幾個很著名的問題 , 比如小明和小紅仍然用正方形的盤子 , 但是現在已知他們的糖加起來是某個數——比如 2333333449 顆糖 , 那麼怎麼求分別有多少顆呢 ? 這就和費馬平方和問題密切相關 . 實際上用一定的算法不難得知 , 兩人的糖隻可能分別是 15480^245757^2 顆 , 因為總糖數是模 41 的素數 . 剛才見到和太陽差不多重量的糖 , 現在少得隻能填滿一個房間的糖甚至無法引起你的註意 .

但是 ! 時代變瞭 !

【小明和小紅都用立方體的盒子裝糖 , 小紅還是對小明說 , 我的糖果比你的兩倍還多一顆 , 請問分別可能是多少糖果 ? 】

這個問題的味道全然變瞭 ! 看起來隻是次數高瞭一次變成瞭 x^3-2y^3=1 , 但是數學傢們見到都會覺得頭疼 ! 因為我們不再有確定形式的公式可以輕易得到這種方程的所有解瞭 ! 這個時候 , 一位在黑暗中像燈塔一般發出醒目光芒的數學傢站瞭出來 , 他叫Thue , 他說 :

我雖然不能告訴你小明和小紅有多少顆糖 , 但是我知道存在這樣一個數 N_0 , 他們的糖不會超過這個數 . 換句話說 , 就是有一個無形的天花板 , 他們的糖再怎麼堆起來 , 也不會高過這個天花板 .

你問Thue , 這個天花板有多高呢 ? 他卻回答到 : 鬼才知道有多高 , 我隻告訴你天花板是存在的 , 至於求出這個高度 , 就不要來找我瞭 .

這果然是純數學傢2333 , 告訴瞭我們一個看起來沒有用卻不平凡的事實 .

故事還沒有結束 , 剛才這部分還有後話 , 其實小紅在騙小明 , 因為嚴格細致而復雜的推導可以得出 , 並不存在這樣兩個正整數滿足那個方程 . 但這並不違反Thue的結果 , 他隻是說萬一他們真的有糖 , 不會超過這麼多 , 甚至不能保證這個方程到底有解還是沒有 . 這個定理簡直無用至極瞭 !

但這個定理的一大意義在於 , 暗示我們很可能不像二次的方程那樣 , 能找到一條萬能的表達式 , 代入不同的整數可以得到取之不盡的解 , 也不能像 (3+2sqrt2)^m 那樣遞推得算出越來越大的解 . 很有可能 , 三次或者更高次的方程就是數字的盡頭 , 山窮水盡 .

實際上 , ax^3-by^3=c 這種形狀的方程隻有有限組解 , 甚至 , ax^n-by^n=c 在確定瞭其中的常數 a,b,c,n(nge3) 後 , 也隻有有限多組解 . ( 為瞭閱讀的連續性 , 作者可以跳過下面這個復雜的定理 )

歡迎回來 !

實際上 , 這其中暗示瞭更多的秘密 : 比如我們考慮一類數字 , 不妨起個名字 , 叫做 2,3,5,7 形數 , 其包含的素因子隻有 2,3,5,7 四種 , 比如 12,35,49,210 就是這樣的數字 , 但是 11,33,38 就不是 , 因為他們有 2,3,5,7 以外的素因子 . Thue告訴我們 : 隨著數的逐漸增大 , 相鄰兩個這種數間的距離會變得越來越稀疏 , 到最後 , 每個 2,3,5,7 形數都是孤零零的 . 這就是這種數的宿命瞭 .

沒有什麼是永恒的 , 除瞭 …… 孤獨 !

比如假設兩個 2,3,5,7 形數的差是 c , 那麼 2^{a_1}3^{a_2}5^{a_3}7^{a_4}-2^{b_1}3^{b_2}5^{b_3}7^{b_4}=c , 我們可以證明這種方程的解數是有限的 , 證明很簡單 , 因為每個 a_i,b_i 除以 3 都有個餘數 , 無非是 0,1,2 , 減掉這個餘數後 , a_i,b_i 們將變成 3 的倍數 . 每個指數都是 3 的倍數 , 意味著這個數是一個完全立方數 , 因為餘數隻有三種可能 , 2,3,5,7 的這些餘數次冪的乘積也隻有有限種組合 , 到頭來 , 變成瞭一個 ax^3-by^3=c 形狀的方程 , 而系數組合隻有有限種 , 根據我們前面提到的結果 , 終究隻有有限組解 .

這意味著 , 對每個 c , 隻有有限多組 2,3,5,7 形數的差是 c , 當超過瞭這些解中最大的那個 , 兩個這樣的數的差就再也不可能是 c 瞭 , 當 c=1,2,3,cdots,N 的解都用完瞭 , 以後就再也不會有瞭 , 換而言之 , 再往後兩個 2,3,5,7 形數的差必須大於 N . 隨著小的解快速消耗 , 故人各在天一方 , 相望落落如晨星 .

數字的宿命就是這樣 , 即使我們考慮的是 2,3,5,7,cdots,97 形數 , 也就是說我們考慮所有素因子都小於 100 的數 , 它們終究還是逃脫不瞭孤獨的宿命 , 因為【有限】的耐心和品性 , 永遠無法和【無限】相比 , 那種永遠也到不瞭盡頭的無力感 , 超出瞭我們所有文字的想象力 . 但是卻沒有超出數學的想象力 , 隻有數學才能精確地刻畫無限 .

那麼故事看起來到這裡就結束瞭 , 是這樣嗎 ? 其實正相反 , 才剛剛開始 . 現在我們知道解的數量是有限的 , 但是怎麼求出來呢 ? 最簡單的方法就是同餘 ! 比如以 2,3,5 形數作為例子吧 ! 我們隻解最簡單的 c=1 作為例子 , 讓讀者真實地感受解決這種問題的傳統方法是怎樣的 , 當然這並不是文章的核心內容 , 讀者可以斟酌閱讀 .

兩個這種數差為 1 , 表示這兩個數是互質的 , 否則它們的差應該整除它們公共的因子 , 就不可能是 1 瞭 . 所以我們考慮的情況隻有下面六種 ( 每個絕對值表示可以交換被減數和減數兩者的順序 ) : |2^x3^y-5^z|,|2^x5^y-3^z|,|3^x5^y-2^z| . 我們先猜一些解 : 2-1,6-5,5-4,25-24 ; 3-2,4-3,9-8,10-9,81-80 ; 16-15 看起來就止於此瞭 , 但還是看起來非常多 ! 怎麼討論才能盡量簡單呢 ? 並沒有什麼好辦法 , 最有效的就是不斷嘗試適合的數來同餘 .

你看 , 上面這麼一個簡單的差為 1 情況 , 我們來回推導瞭好多行 , 也就是說 , 傳統方法必須要辛苦驗證所有情況 , 不能有絲毫的差錯 . 不過實際上僅僅對於差 1 這種極特殊的情況 , 著名的Zsigmondy定理和Stormer定理也能推出很強悍的結果 , 限於篇幅 , 我們就不介紹它們瞭 , 留給讀者自行瞭解 .

經過數學傢的努力 , 這種方程最有效的結果叫Baker定理 , 他的功勞在於給出瞭一個便於計算的上界 , Thue隻告訴你這個界存在 , 而Baker給算瞭出來 . 不過不愧是數學傢 , 這個界雖然能算 , 但是大的可怕 , 隨便代入幾個小數字就是至少 10^{100} 這種量級的 , 無論如何 , 人們借助於這個界 , 還是給出瞭求這種方程的解的有效方法 , 例如著名的 lattice basis reduction類的方法和LLL算法 , 同樣本文也不作具體介紹 .

介紹完這些不定方程 , 我們回到Thue的定理 , 我們將會給出一個初等書寫的證明 , 這也是這篇文章的核心 , 半個月來的努力也就是為瞭將過程完全理順 .

首先我們對這個方程做一些變形 : ax^3-by^3=c , 其中 a,b,c 都是正整數 .

因為 y=0 的情況很好驗證 , 所以我們考慮 yneq0 , 左右就可以除以 ay^3 , 這樣方程化為 (x/y)^3-b/a=c/(ay^3) , 雖然我們感興趣的是正整數解 , 但是很有用的技巧是在實數范圍內因式分解 : z^3-t^3=(z-t)(z^2+zt+t^2) , 我們這時候代入 z=x/y,t=xi=sqrt[3]{b/a}>0 , 於是問題化為 (x/y-xi)((x/y)^2+(x/y)xi+xi^2)=c/(ay^3) .

做一點簡單的放縮 , z^2+zt+t^2gefrac34t^2 , 因此 |x/y-xi|le4c/(3axi^2y^3)=C/y^3 , 其中 C 是隻與 a,b,c 有關的常數 , 因此我們的目標集中在這個不等式 |x/y-xi|le C/y^3 , 下面就是本文的主角 :

代數實數就是一個實的代數數 , 什麼是代數數後面會講 . 在這之前 , 我們知道 xi 是一個三次方根 , d=3 , 比如在這個定理中代入 varepsilon=1/3 , 隻要 q>C^6 那麼 1/q ^{1+d/2+varepsilon}<C/q^3 , 也就是說 , q>C^6 的解隻有有限個 . 當然讀者不難發現 0<q<C^6 的解也隻有有限個 ( 為什麼 ? ) , 也就是方程隻有有限個解 .

從上面的介紹來看我們有瞭切身的體會 , Thue定理是一個重大的突破 . 因為這個具有跨時代意義的定理 , 可以看作繼Pell方程 ( 和二次連分數 , 周期連分數 ) 的研究之後 , 第一個對一大類方程作出定性分析的結果 . 不僅如此 , 為解決問題Thue所提出的解決方案具有很大的啟發性 , 這一系想法的精細化直接帶來瞭後面Roth , Baker等人的結果 , 說是現代丟番圖逼近論的起源也不為過 .

在學數學競賽的時候 , 我也曾思考過有沒有辦法能證明代數數不能被有理數很好地逼近 , 曾獨立推導出劉維爾trivial的估計 , 而後再無進展 , 後來聽說瞭這一系列的結論 , 從此對丟番圖逼近論也產生瞭濃厚的興趣 , 競賽時期的一大夢想就是看懂Roth定理至少是Thue定理的證明 . 但是當時自己太菜瞭 , 無法理解Roth的結果 , 而Thue的原始論文是德語的 , 看不懂qwq . 直到最近我才找到瞭參考文獻[1] , 這份Lecture notes是我見到的第一個詳盡介紹Thue定理的文章 , 半個月後 , 於是有瞭這篇知乎文章 .


終於 , 我們要來介紹這個定理瞭 , 接下來全程硬核 :

長文警告 ( 進度條警告 ) :我們需要的前置知識隻有下面這些 , 換而言之 , 一個非常優秀 ( 瞭解一點點超綱知識 ) 的高中生或者一個學過高等數學的大學生就能完全理解這個證明 .作者的工作就是將原文的工作轉化成這種內容 , 加以整理 . 如果讀者隻是對於前面科普的內容感興趣 , 而不希望閱讀具體的證明內容 , 那麼走到這裡 , 也算是一個完滿的旅程瞭 .

再次提示讀者 , 這真的是一個非常非常長的證明 , 請做好心理準備 . 過程中雖穿插瞭七個引理 , 不過我們都給瞭詳盡的證明 .

text{Readme.} 在給出證明的想法之前 , 要先知道 , 因為解決方案復雜到超乎想象 , 我們可能事先用字母待定很多系數 , 直到後面需要 , 發現這些系數應該滿足某些條件的時候 , 再將他們具體確定下來 . 這是在很多證明中常見的技術 , 比起一開始就提出莫名其妙的系數更容易讓人理解和信服 ,希望讀者能習慣這一點 .


證明的想法大概是這樣的 : 首先我們假設有無窮多個這種逼近 , 不妨稱為【優秀的逼近】. 我們先隨便取其中的兩個 p/qneq r/s , 並且假設 qle s . 看似兩個沒什麼關系的分數 , 但是 , 我們要有一種感覺 : 我們借助它們的定義 , 可以從中得到點什麼更精細的結論 .

我們記 Delta=|p/q-xi|-|r/s-xi| 再記分母的冪次 mu=1+d/2+varepsilon 然後試圖放縮得到一個上界一個下界 : 1/qsle|p/q-r/s|le|Delta| 以及 |Delta|<1/q^mu+1/s^mule 2/q^mu

結合兩式 , 立刻得到 q,s 之間的關系 s>q^{mu-1}/2 . 這表明瞭兩個優秀的逼近的分母其實不是同一個量級的 , 這一個特點我們稱之為 gap principle , 或許翻譯作【隔閡原則】比較合適 .

接下來就是Thue的想法中很核心的構造 . 如果我們能整兩個次數不超過 n 的整系數多項式 P_n(X),Q_n(X) 使得 P_n(X)-xi Q_n(X)X=xi 處有非常多重的零點 , 因為 xip/q 非常接近 , 照理來說 , 多重零點的多項式代入附近的值 X=p/q 結果也會很小 ( 讀者可以想象在十重零點的 y=x^{10} 中代入 x=0.01 的場景 ) , 我們遂有理由認為有理數 p_n/q_n=P_n(p/q)/Q_n(p/q) 也是 xi 比較好的逼近 .

同時運用一些技術手段 , 將兩個多項式的系數都弄得很小 , 這樣新產生的分數 p_n/q_n 不會有很大的分子分母 , 這能保證它們也是不錯的逼近 . 這樣就可以從一個優秀的逼近衍生出一系列的逼近 , 而且因為多項式的次數可以調節 , 這意味著分子分母的量級可以調節 , 我們或許可試圖取一合適的 n , 將 p_n/q_n 推進gap裡 , 根據前面的隔閡原則 , q_ns 足夠接近時產生矛盾 , 這逼迫 p_n/q_n=r/s .

於是我們隻剩下最後一步 , 就是證明它們不相等 , 產生一個矛盾 . 這最後一步看起來容易 , 卻是極其精巧的 ( 甚至在Roth定理前數學傢們也是卡在這裡 ).

不過其實我們真正在證明的時候 , 並不會完全采取這個思路 , 而是更高層面的 ,用這種思想來推出矛盾 , 例如 : 實際進行表達式估計的時候 , 不一定直接使用隔閡原則 , 但隔閡原則會暗示我們這裡應該能推出一個 < 或者 > 方向的不等式 , 我們可能會嘗試其他的方法來得到它 , 像一張藏寶圖 .

這一系列看似華麗的操作將問題先分而後治 , 然而 , Thue定理始終隻是一個定性分析的結果 : 萬一好的逼近隻有一個 , 我們怎麼也沒法推出矛盾 , 如果不巧這個好的逼近分子分母都很大呢 ? 我們暫時是沒有辦法對它的界進行有效估計的 . 實際上 , 在Thue之後的Siegel , Gelfond和Dyson乃至最後Roth不斷將 1+d/2 改進為更小的數 2sqrt d,sqrt{2d} 乃至 2 , 這個定性的框框還是沒有跳出 , 無論是將估計更精細化 , 增加變元的數量還是提高零點的階數 , 都依賴於最初足夠量並且足夠好的【優秀的逼近】的存在性來推矛盾 . 用這方面的術語 , 這種方法也稱【非實效性方法】( 其中的ineffectivity不可避 ) .

嘛但是不管怎麼說定性結果也是結果瞭 , 因此我們方才不會把這種方法叫做【無效方法】喵 .

在上面思想的指導下 , 我們把證明分成三部分 :

上面這三個步驟顯然比起我們最初的想法已經成熟瞭不少 , 分別較具體地給出瞭實施方案 , 其重要性不言而喻 , 但真正的研究進程和我們這樣草率介紹的思路顯然是完全不同的 . 很多情況下 , 思路會隨著精確的符號和數值計算的確立而向前延展 , 讀者可以自己體會下面我們的證明中哪些技術是隨著計算而提出的 .

另外 , 我們基本將所有需要歸納法和技巧的過程全部寫成瞭引理 , 如果讀者覺得某個引理是顯然的或者熟知的 , 可以考慮跳過它的證明 . 因為證明的一大部分版面由這些獨立的 ( 不需要上下文的 ) 引理構成 , 每次見到都去閱讀證明會影響思維連貫性 , 讀者可以選擇現在就閱讀自己需要的證明 . 然後正式開始時在心中默認它們都是對的 .


squaretext{Proof.} 首先我們開始第一步 , 這一步漫長而艱辛 .

我們需要一個整系數的 F_n(X,Y)=P_n(X)-YQ_n(X) , 其中 P_n,Q_n 的次數不超過 n , 而且我們希望 X=xiF_n(X,xi)m 階零點 . 關於零點的階數有下面很重要的引理 :

squaretext{Proof.} 使用歸納法 , 根據因式定理 , 對於 m=1 的情形 , f(x_0)=0 所以 f(X) 有因子 (X-x_0) . 假設在某 m 時成立 , 那麼 f'(X) 可以寫作 (X-x_0)^mr(X) , 同時 f(X) 可作 (X-x_0)^ms(X) 求導得 (X-x_0)^{m}s'(X)+m(X-x_0)^{m-1}s(X) 這應當等於 f'(X)=(X-x_0)^mr(X) , 這表明 s(X)=(X-x_0)(r(X)-s'(X))/m , 於是 f(X)(X-x_0) 因子至少是 m+1 重的 blacksquare

這個有用的引理可以幫助我們利用導數判斷是否是高階零點 , 為瞭方便 , 我們引入一個記號 D_j=frac1{j!}frac{partial^j}{partial X^j} : 表示對 Xj 階導數後除以 j 的階乘 , 關於這個記號有一個顯然的性質 : 對整系數多項式 P(X) 來說 D_jP(X) 還是整系數的 . 這一點隻要研究一個單項式 D_j(aX^k)=ak(k-1)cdots (k-j+1)X^{k-j}/j! , 而這個系數剛好可以寫成組合數 abinom kjX^{k-j} ( 記號 binom kj=text C_k^j ) , 因為組合數是整數 , 於是結論得證 .

現在我們對 F_n(X,xi)=P_n(X)-xi Q_n(X) 求導看看 , 是 m 階零點這要求 D_jF_n(X,xi) 代入 X=xi 等於 0j=0,1,cdots ,m-1 時成立 . 但是含有 xi 到底是怎樣一回事呢 ? 我們需要對代數數做一點簡單的刻畫 .

我們知道的事僅限於 xi 是一個 d 次有理系數多項式的根 , 除法除掉首項系數後 , 我們不妨設 xi^d=c_{d,0}+c_{d,1}xi+cdots+c_{d,d-1}xi^{d-1} 成立 , 其中 c_{d,s} 都是有理數 . 也就是 xi^d 可以用 1,xi,cdots,xi^{d-1} 的有理數倍表示出來 , 自然會問 xi^{d+1},xi^{d+2},cdots 這樣更高的次數能不能有類似的表示呢 ?

答案是肯定的 , 我們甚至可以對這些系數給出一個好的界 :

squaretext{Proof.} 當然是使用歸納法啦 ! 先解決 r=0,1,cdots,d 的情形 , 顯然取 b 是所有 c_{d,s} 的公倍數 , 這樣 b^rc_{r,s} 是整數的問題解決瞭 , 同時再取 B_11+max_{0le sle d-1}|c_{d,s}| , 於是界的問題也解決瞭 .

接下來假設在某 rge d 的時候成立 , 那麼 r+1 時 , xi^{r+1} 可以寫作 xicdotxi^r=c_{r,0}xi+c_{r,1}xi^2+cdots+c_{r,d-1}xi^d , 再將 xi^d 用我們的奠基拆成 1,cdots,xi^{d-1} 的線性組合 . 於是系數變為瞭 c_{r,d-1}c_{d,0} ( 常數項 ) 和 c_{r,s-1}+c_{r,d-1}c_{d,s} ( xi^s 項系數 , s>0 ) 顯然乘積中一個的分母是 b^r 的因子 , 另一個是 b 的因子 , 遂為整數 . 而看成求和一個不超過 B_1^r 另一個不超過 B_1^rcdot max_{0le sle d-1}|c_{d,s}| , 遂得其界 blacksquare

有瞭這個引理作為工具 , D_jF_n(X,xi)=D_jP_n(X)-xi D_jQ_n(X) , 首先我們知道 j=0,cdots,m-1 時它們仍然是整系數多項式 , 代入 X=xi 時 , 將 xi^r(rge d) 全部寫成 1,cdots,xi^{d-1} 的有理線性組合 , 具體一點 , 設 P_n=sum_{j=0}^n x_j X^j , Q_n=sum_{j=0}^n y_jX^j 並且求導代入展開 ( 我們設它們的次數都不超過 n ) .

簡單化簡得到 xi^l 前的系數是 sum_{s=j}^n(x_sbinom sj c_{s-j,l}+y_sbinom sjc_{s-j+1,l}) . 也就是說 , 每一個 j 相當於給出瞭一個 x_s,y_s 們的有理系數的線性方程組 . 註意到 , 根據引理 , 用 b^{n+1} 來左乘每一個方程組 , 可以將系數全都變成整的 , 利用我們熟悉的求和式 binom s0+binom s1+cdots+binom ss=2^s 我們知道 , binom sjle 2^s 成立 , 結合 sle n 以及 c_{s-j,l},c_{s-j+1,l} 絕對值不超過 B_1^{n+1} , 於是 :

我們現在得到瞭 dm 條 ( 別忘瞭每個導數限制帶來的是 d 條方程 ) 整系數的方程 , 這些方程是關於 2n+2 個系數 x_0,cdots,x_n,y_0,cdots,y_n 的 , 而且每個方程的參數不超過 2^nb^{n+1}B_1^{n+1}le B_2^n , 其中 B_2=(2bB_1)^2 , 因為 b,B_1 隻與 xi 有關 , 故 B_2 也是隻與 xi 有關的常數 .

真正的魔法是下面這個引理 :

squaretext{Proof.} 證明其實非常初等 , 設 T=[(NA)^{M/(N-M)}] 這裡方括號表示取整 , 現在我們考慮一系列 N 元組 : x=(x_1,cdots,x_N) , 讓每個 x_i 取遍 0,1,cdots,T , 於是一共有 (T+1)^N 個 . 將它們代入那些線性函數 f_j(x)=sum_{i=1}^n a_{ij}x_i 中去 ( 將其看作一個關於 N 元組 x 的函數 ) , 於是每一個輸入 x 可以自然對應到一個 M 元組 y=(f_1(x),cdots,f_M(x)) 作為輸出 .

如果我們設 S_{j,+} 表示 a_{1,j},cdots,a_{N,j} 中所有非負數的求和 , 用 S_{j,-} 表示其中非正數的求和 . 那麼 S_{j,+}-S_{j,-} 就得到瞭它們的絕對值之和 , 因為正的被加瞭負的被減瞭 . 而且因為每一者絕對值不超過 A 因此 S_{j,+}-S_{j,-}le NA . 更有意義的是 , 不難證明 S_{j,-}Tle f_j(x)le S_{j,+}T , 因為每個正 a_{i,j} 最大湊上 T 相乘 , 最小就是讓正的 a_{i,j} 全部乘 0 , 負的剛好反過來 .

於是每個 f_j 的值域不過是 S_{j,+}T-S_{j,-}T+1le NAT+1 個正整數 , 因此 y 的取值至多隻有 (NAT+1)^M 種可能 . 因為 (T+1)^N>(NAT+1)^M 成立 ( 由 T+1>(NA)^{M/(N-M)} 變形不難得到 ) , 表明輸入數量多於輸出數量 , 這根據抽屜原理必然有兩個不同的輸入 x,x' 對應同一個輸出 . 將它們做差 , 令 t_i=x_i-x_i' , 我們就得到瞭一個絕對值不超過 T ( x_i,x_i' 的絕對值本身就不超過 T ) 的不是全零的解 blacksquare

立刻將這個引理應用到我們的問題中去 , 我們有 N=2n+2 個未知數 , M=dm 個方程 , 系數絕對值不超過 A=B_2^n , 於是存在不全為零的整數 x_0,cdots,x_n,y_0,cdots,y_n 解 , 其絕對值不超過 K=((2n+2)B_2^n)^{dm/(2n+2-dm)} .

這個數看起來非常復雜 , 我們過一會兒再來處理它 .


終於 , 我們來到瞭第二部分 . 很真切地 , 前一個部分中我們體會到為瞭處理過程中的每一個細節 , 我們要付出多大的努力 .

還是如一開始那樣 , 我們記分母的冪次 mu=1+d/2+varepsilon , 並且取兩個優秀的逼近 p/qneq r/s,0<q<s 且滿足 |xi-p/q|le1/q^mu|xi-r/s|le 1/s^mu . 為瞭方便 , 我們後面也時常用 u=p/q 以及 v=r/s 代表這兩個分數 .

更進一步的 , 我們希望給出 |D_jF_n(u,v)| 的上界 , 以備不時隻需 . 因為零點至少有 m 階 , 我們寫 F_n(X,xi)=(X-xi)^mR_n(X) 這樣一來 F_n(X,Y)=F_n(X,xi)-(Y-xi)Q_n(X) 寫開就有 F_n(X,Y)=(X-xi)^mR_n(X)-(Y-xi)Q_n(X) .

現在對其使用 D_j , 不難驗證 , 一個多項式如果在 xi 處有 m 階零點 , 求一次導數後零點至少還會有 m-1 階 , 進一步可歸納到求 j 階導數的情形 , 這正是我們需要的 : D_jF_n=(X-xi)^{m-j}R_{n,j}(X)-(Y-xi)D_jQ_n(X) , 其中 R_{n,j} 是一系列多項式 .

不要忘記在前一部分我們已然證明 Q_n 的各系數絕對值不會超過 K , 今後為瞭行文方便 , 對多項式 P(X) , 我們用記號 |P| 表示 P 的各項系數絕對值的最大值 . 由前文 , |Q|le K , 由前文 , 作用 D_j 會讓系數乘上組合數 binom kj ( 還記得證明系數是整數那裡講過 ) 並且 binom kj<2^k , 由於 Q 次數不超過 n , 於是 |D_j Q_n|<2^nK , 類似的 , 同批出現的 |D_jP_n|<2^nK 也成立 , 我們首先根據定義 D_jF_n(X,xi)=D_jP_n(X)-xi D_jQ_n(X) , 於是善用絕對值不等式 , |D_jF_n(X,xi)|<|D_jP|+|xi|cdot|D_jQ| , 也就有 |D_jF_n(X,xi)|<2^nK+|xi|cdot2^nK=(1+|xi|)2^nK . 現在是時候處理 |R_{n,j}| 瞭 . 這時候 , 我們需要一種以除代乘的思想 ( 其實簡單來說就是在形式冪級數環裡研究問題 ) .

squaretext{Proof.} 首先我們證明 xi^{-m}(1+X/xi+cdots+(X/xi)^{n-1})^m=S(X)+X^nU(X) , 其中 U(X) 是多項式 , 將 X/xi 看作一個整體 z , 於是隻要證明 (1+z+cdots+z^{n-1})^m 等於binom {m-1}{m-1}+binom m{m-1}z+cdots+binom{n+m-2}{m-1}z^{n-1} 加上 z^n 乘上一個多項式 . 證明隻需使用歸納法 , m=1 時系數全 1 構成瞭顯然的奠基 . 而由 binom {m-1}{m-1}+binom m{m-1}+cdots+binom {m+k-1}{m-1}=binom{m+k}m ( 為什麼此恒等式成立 ? 此恒等式成立後有什麼用 ? 提示 : 可以對 k 歸納 ) 可以直接由 m 推出 m+1 的情形 .

根據這個結論 , (-1)^m(X-xi)^mS(X) 就是 (-1)^m(X-xi)^m(xi^{-m}(1+X/xi+cdots+(X/xi)^{n-1})^m-X^nU) , 化簡得 (1-(X/xi)^n)^m+X^nV(X)=1+X^nW(X) , 於是 (-1)^mF(X)S(X)=R(X)(1+X^nW(X))blacksquare

現在我們可以通過乘一個多項式 , 復原其中一個因子的系數 . 雖然會帶來一個討厭的餘項 , 但是並不會影響我們研究 |R_{n,j}| 的值 . 對於次數不超過 n 的多項式 A,B , |AB|le(n+1)|A||B| 是顯而易見的 . 因為 AB 的每一個系數都是至多 n+1A,B 系數的乘積求和 , 然後根據絕對值不等式容易得到需要的結果 .

現在這兩個工具直接給出瞭 |R_{n,j}| 的一個上界 : (n+1)|D_jF_n(X,xi)|cdot|S(X)| . 後者仍然是用傳統的技術 : binom{n+m-2}{m-1}<2^{n+m-2} , 於是非常粗獷地 , 我們可以放到 |S|<(2max{1,|1/xi|})^{2n} , 因為這仍然可以寫成一個僅與 xi 有關的常數的冪次 . 總而言之 |R_{n,j}|le(n+1)2^n(1+|xi|)(2max{1,|1/xi|})^{2n}K . 那麼前面我們求出復雜的 K=((2n+2)B_2^n)^{dm/(2n+2-dm)} 是不是也有希望變得更簡單一些呢 ?

這時應該考慮將 m 取成一些可愛的數值 . 我們先設 ( 後面我會解釋這裡的 1/2 的來源 ) lambdain(0,1/2),m=(2n+2)(1-lambda)/d , 這樣指數可寫作 (1-lambda)/lambda , 如果我們事先固定 lambda 要求其隻與 varepsilon ( varepsilon 是題目裡的一個字母 , 還記得嗎 ? ) 有關 , 那麼我們就存在隻與 xi,varepsilon 有關 ( 也就是說題目中的常數確定下來後它們就固定瞭 ) 的常數 B_3,B_4 : 放縮 (2n+2)B_2^nle(4B_2)^n , 於是可以寫 Kle left((4B_2)^{lambda/(1-lambda)}right)^n=B_3^n , 再令 B_4=32B_3(1+|xi|)max{1,|1/xi|}^2 , 於是 |R_{n,j}(X)|,|D_jQ_n(X)| 都不超過 B_4^n , 這是一個很好的界 .

現在精確地估計 |D_jF_n(u.v)||(u-xi)^{m-j}R_{n,j}(u)-(v-xi)D_jQ_n(u)| , 這時候前面的結論起瞭作用 , 次數不超過 nF(X)|F(X)|le(n+1)|F|max{1,X}^n , 由此得到 |R_{n,j}(u)|,|D_jQ_n(u)|le(n+1)B_4^nmax{1,u}^n . 實際上因為 u,v 都與 xi 足夠接近 , 容易證明 |u-xi|<q^{-mu},|v-xi|<s^{-mu} |u|,|v|le1+|xi| . 於是設 B_5=2(1+|xi|)B_4 當然也僅僅與 xi,varepsilon 有關 , 因為 , 因此 |D_jF_n(u,v)|le (q^{-mu(m-j)}+s^{-mu})B_5^n 成立 , 第二部分就此完成 .


接下來是第三部分 , 首先咱簡單研究 |D_jF_n(u,v)| 的下界 , 企圖構造矛盾 . 因為 D_jF_n(X,Y) 是整系數的 , 因此代入 p/q,r/s 兩個有理數後分母是 q^{n-j}s 的因子 . 於是要麼 |D_jF_n(u,v)|ge1/(q^{n-j}s) , 要麼就是 0 .

假設很不幸 , 真的有很多 0 , 有多少呢 ? 假設 j=0,1,cdots h-1 這個值都是 0 ( 註意一下當然還有極端的 h=0 也就是一個 0 也沒有以及 h=infty 也就是怎麼求導都是 0 ) . 按照定義 , 約去 j! 就是說現在咱有 v=P_n^{(j)}(u)/Q_n^{(j)}(u) , 其中上面的 (j) 表示求導 j 次 .

這就明示 P_n^{(j)}(u)Q_n^{(i)}(u)-Q_n^{(j)}(u)P_n^{(i)}(u)=0 , i,j 是小於 h 的自然數 . 先定義其中一個特殊情形 : W=P_nQ_n'-Q_nP_n' . 這個特殊情形有一個重要的應用由下面的引理給出 ( 其實熟悉分析的同學應該知道這叫做多項式 P,Q 的Wronskian行列式 ) :

squaretext{Proof.} 這次要用到多次求導的關鍵性引理Leibnitz法則 : 也就是 (AB)^{(j)}=sum_{i=0}^jbinom jiA^{(j-i)}B^{(i)} , 證明和二項式定理的證明是類似的 , 就是使用歸納法 , 我們就將細節留給讀者 .

將這個法則運用在 P_nQ_n'Q_nP_n' 上 , 得到 W^{(j)}(u)=sum_{i=0}^jbinom ji(P_n^{(j-i)}Q_n^{(i+1)}-Q_n^{(j-i)}P_n^{(i+1)})=0i+1,j-ile j+1le h-1 時成立 , 於是結論得證 blacksquare

我們知道 , 如果看成多項式意義下 W(X)equiv0 , 這恒等於 0 的直接推論是 P_n,Q_n 兩個多項式線性相關 . 對於不熟悉Wronskian行列式的讀者我們這裡補充一個證明 : P_nQ_n'-Q_nP_n'=Q_n^2cdot(P_n/Q_n)' , 如果恒等於 0 , 要麼 Q_n=0 , 這表明 Q_n=0P_n , 是線性的 ; 要麼 P_n/Q_n 是常數 ( 否則求導不會是 0 ) 也就是存在 c 使得 P_n=cQ_n .

下面我們首先證明 P_n,Q_n 看成多項式不是線性相關的 , 否則我們會按照下面的方式推出矛盾 :

因為 F_n(X,xi)=P_n(X)-xi Q_n(X) , 如果 P_n,Q_n 線性相關 , 它將變成 P_n,Q_n 中非零者的常數倍 . 共同地 , 它們有 xim 階因子 , 同時它們都還是整系數的 , 這裡就需要我們對代數數有另外一個基本認知 :

squaretext{Proof.} 如果 g(X) 不是 f(X) 的倍數 , 那麼我們存在有理系數的多項式 h_0(X)r(X) , 其中 r(X) 的次數低於 f 的次數 , 使得 g(X)=f(X)h_0(X)+r(X) . 這一性質也叫做多項式的帶餘除法 , 證明是如下 :

假設某 r_1(X) 是使得上帶餘除法式中 r 取到最低次數的有理系數多項式之一 , 但是超過瞭 f 的次數 , 設有理系數的 h_1(X) 使得 g=fh_1+r_1 . 假設 f 的首項是 f_dX^d , f_dneq0 , r 的首項是 r_nX^n , nge d,r_nneq 0 . 這時候 , 我們有恒等式 g=(h_1+(r_n/f_d)X^{n-d})f+(r_1-(r_n/f_d)X^{n-d}f) , 可是 (r_1-(r_n/f_d)X^{n-d}f) 將首項 r_nX^n 消掉瞭 , 這與我們前面假設的 r_1 的最低次數相矛盾 , 不難驗證新多項式的系數也是有理的 .

當然 , 表達式 g=fcdot0+g 意味著 r 的存在性得以保障 ( 用大白話說 , 萬一沒有任何有理系數的多項式 r,h_0 符合上面的式子 , 那麼我們的證明從【一個既有式】推出次數更低的也變成瞭莫須有的 )

現在 , 在 g(X)=f(X)h_0(X)+r(X) 中代入 X=xi , 這樣一來 g(X)=f(X)=0 這推出 r(xi)=0 , 但是 r 的次數比起 f 要低 , 如果 r 非零 , 這將與我們題目中的假設 f 是次數最低的非零多項式之一矛盾 , 這脅迫 r(X) 恒等於 0 , 但這又與開始假設的不是倍數相矛盾 , 因此結論得證 blacksquare

要註意 : 這個次數最低的多項式 f(X) 隻能有 1 階的 xi 零點 , 否則如果階數超過 1 , 那麼對 f 求導 , 其導函數 f' 也至少有一階 xi 零點 ( 這件事我們在 R_{n,j} 那裡講過 ) , 而 f 不可能是常數 , 這表明存在比 f 次數更低的非零 f' 擁有 xi 作為零點且有理系數而矛盾 .

利用這個引理 , 我們可以不妨假定我們第一個部分中討論的 xi 滿足的 l(x)=xi^d-(c_{d,0}+c_{d,1}xi+cdots+c_{d,d-1}xi^{d-1}) 是次數最低的 . 這樣由我們的引理 , P_n,Q_nmxi 的因子給他們帶來瞭一個整整 md 次的有理系數多項式因子 : 每次提取出一個有理系數的 l(x) 因子後將其除掉 , 商隻會少一階 xi 的零點 ( 我們證明瞭次數最低的 l 隻能包含 xi1 階零點 ) , 同時保持是有理系數的 ( 多項式的除法過程隻涉及加減乘除 , 不會產生無理系數 ) , 於是這一過程能一直進行下去 .

這樣一來 , F_n(X,xi) 至少是 md 次的多項式 ( 因為非零而且有一個 md 次的多項式因子 ) , 而 md=(2n+2)(1-lambda) , 我們一開始要求 lambdain(0,1/2) ( 讀者可以翻回前面看看 ) 就是這個用意 , 這樣使得 md>n+1 而矛盾 .

終於 , 這表明 P_n,Q_n 不是線性相關的 , W(X) 不是恒 0 的 ( 還記得這能推出前者 ) . 也就是說 (X-u)^{h-1}W 的因子 ( 這是引理五和引理一的共同推論 , 後者提供瞭一系列導數為零 ) 當然 W=P_nQ_n'-Q_nP_n' 是整系數的 , 而 (X-p/q)^{h-1} 是因子將推出 q^{h-1} 整除 W 的首項系數 :

這不是顯然的 , 我們指出下面的引理 :

squaremathrm{Proof.} 設整系數多項式 h(X) 分解為 h(X)=f(X)g(X) , 不妨設 f(X),g(X) 都是有理多項式 , 可能非整系數 . 設 f(X)=f_0(X)/k_f 其中 k_ff(X) 各系數既約分母的最小公倍數, 這樣 f_0(X) 整系數 , 這也就是通分的過程 . 類似的, 設 g(x)=g_0(X)/k_g , 若 k_f=k_g=1 結論已然成立 , 下考慮如果至少一者大於 1 的情形 , 不妨就設 k_f>1 .

那麼 k_f 必然存在一個素因子 p , 而恒等式 k_fk_gh(X)=f_0(X)g_0(X) 成立 , 因 k_fp 的倍數 , 故 p 整除 f_0(X)g_0(X) 的每一個系數 . 不妨設出所有整系數 : f_0(X)=a_mX^m+cdots+a_0 , g_0(X)=b_nX^n+cdots+b_0 , 我們證明要麼諸 a_i 都是 p 的倍數要麼諸 b_i 都是 p 的倍數 , 這樣就可以提出因子 p 消去分母 k_fk_g 中的一個素因子 , 這操作一直進行下去終可以將 k_fk_g 變成 1 .

若不成立 , 假設 s 為使得 a_s 不是 p 倍數的最大的下標 , 類似 t 為使得 b_t 不是 p 倍數的最大的下標, 考慮乘積中 x^{s+t} 的系數 :

該系數是一系列 a_ib_j 的和 , 其中 i,j 取遍一切使得 i+j=s+t 的下標 , 按照 p 整除 f_0(X)g_0(X) 的每個系數知道它是 p 的倍數 , 除開 a_sb_t 唯一一項 ( 兩個非素數 p 倍數的數乘積也不是其倍數 ) , 要麼 ile s 要麼 jle t ( 為什麼 ? ) , 因為 s,t 之最大性 , 其餘 a_ib_j 者均是 p 的倍數唯 a_sb_t 不是 , 這導致最後求和亦不是 p 的倍數, 矛盾 blacksquare

在這一工具的幫助下 , W(X) 可以在整系數內因式分解 , 說明 (qX-p)^{h-1} 整除 W(X) ( 因為可以不斷勻出素因子將所有分母的 q 化解掉 ) , 因此 q^{h-1} 整除 W(X) 的首項系數 , 這表示 |W(X)|ge q^{h-1} , 但是另一方面根據絕對值不等式 |W|le|P_n(X)Q_n'(X)|+|Q_n(X)P_n'(X)| , 運用我們前面關於乘積的 : 次數不超過 n 的多項式 A,B , |AB|le(n+1)|A||B| . 還有第二部分辛苦得到的 |D_jP_n|,|D_jQ_n|<2^nKle(2B_3)^n ( 包括 j=0 也就是不求導和這裡需要的 j=1 ) .

於是 |W|le 2(n+1)(2B_3)^{2n}le(16B_3)^n=B_6^n , 仍然 , 我們的 B_6 隻與 varepsilon,xi 有關 . 所以 , 我們推出 q^{h-1}le B_6^n , 取對數就是 hle1+nln B_6/ln q . 完事具備 , 開始放縮 !


最開始 , 我們把證明分成三個部分 , 實則還有最後的隱藏部分 , 就是利用這些不等式綜合推出矛盾 , 請看我們最後的表演吧 !

這裡總結瞭我們前面文章辛苦得到的所有本部分需要的結果 . 現在我們取 j=h , 很明顯我們希望 (q^{-mu(m-h)}+s^{-mu})B_5^n<1/(q^{n-h}s) , 這樣就能導出反例來 . 我們決定最後變量的順序是 lambda,q,s,tau,n , 這些是自變量 , 其他常數是可以由它們和題目給定的 xi,varepsilon 確定的 .

首先左邊還是有點復雜 , 如果我們要求 m 是滿足 sge q^m 還有 s<q^{m+tau} , 那麼 q^{-mu(m-h)}+s^{-mu}le 2q^{-mu(m-h)} 成立 . 現在我們希望 2B_5^nq^{n-h-mu(m-h)}s<1 , 於是希望 2B_5^nq^{n-h-mu(m-h)+m+tau}<1 . 取對數得到 mu (m-h)+h-n-m-tau>(ln 2+nln B_5)/ln q . 代入 hle1+nln B_6/ln q , 我們希望 (mu-1)m-n>mu(1+nln B_6/ln q)+tau+(ln 2+nln B_5)/ln q . 因為 m>2n(1-lambda)/d , 將 mu 的表達式代入第一個 mu , 如果我們記 delta=(d/2+varepsilon)cdot2(1-lambda)/d-1 , 現在我們希望 delta n>mu(1+nln B_6/ln q)+tau+(ln 2+nln B_5)/ln q .

因為 B_5,B_6,mu 在題目中的常數和 lambda ( 但是後文我們會先將 lambda 依據 xi,varepsilon 確定下來 , 繼而也就可以看成隻和題目中的常數有關瞭 ) 確定下來後 , 它們就固定瞭 , 如果 q 足夠大 , 大到可以使得 (mu(1+ln B_6)+ln2+ln B_5)/(ln q)<delta/2 , 我們希望成立有 delta n/2>tau , 而優秀逼近被假設是無窮多的 , 所以總能找到分母足夠大的 ( 為什麼 ) 以至滿足這個條件 .

最後我們希望 delta=(1+2varepsilon/d)(1-lambda)-1>0 , 這可以取 lambda 足夠接近 0 的有理數而得到 , 這樣就有想要多大就有多大的 n 使得 m=(2n+2)(1-lambda)/d 是整數 ( 為什麼總能約去 (1-lambda)/d 的分母呢 ? ) , 然後就可以按照上一段確定 q . 最後隻需選取足夠大的優秀逼近 s 使之不小於 q^m , 再選取 tau 使得 q^{m+tau}>s . 於是總存在足夠大的整數 n 使得 delta n/2>tau blacksquare

終於經過我們漫長的努力 , 終於解決瞭Thue定理 !

发表回复

相关推荐

三國志戰略版“五虎槍”

由於戰功顯示更新後很少更新,補兩張戰報:①五虎打蜀國:五虎打經典關關張:紅度基本一樣,但是五虎還是略勝一籌,且五虎戰法...

· 1分钟前

狂野徐锦江,演三级片走红,如今一幅画150万不愿卖,自砸5000万建艺术中心,原来你是这样的鳌拜!

▲杨善深作品一个人的心里山山水水越多,越容易对一草一木动情,也越无情——奇崛的个性总会有自己参不透的时候。”

· 3分钟前

手機短信婚禮邀請函 手機婚禮請柬

結婚邀請是婚前準備之一,至於這邀請方式,現在有電子版和手寫版紙質請柬,後者就不多說啦,電子版的話,短信啦,微信啦,等...

· 3分钟前

人民黃河期刊

《人民黃河》是月刊,創刊於1949年,是由水利部主管、黃河水利委員會主辦的水利科技專業學術刊物,自1992年起連續6次入選全國...

· 8分钟前

不看後悔系列:韓劇《浪漫的體質》

為什麼寫韓劇,嗯,答主是學韓語的,又是個文案,所以韓劇真的是再適合不過瞭。但是,這不是我今天寫這篇文的原因。《慶餘年...

· 9分钟前