史上最賤的數學題

導讀:我正在有選擇性地拿過去Andrew和Richard Guy研究的一些立體問題做消遣。

數值結果真是令人歎為觀止。

01、

幾年前,一位退休的數學家Allan MacLeod偶然發現了一個方程,方程之奇令人歎為觀止。老實說,我也算是大風大浪見的多了,但這麼精妙的丟番圖方程還是第一次見。

注:有一個或者幾個變量的整係數方程,它們的求解僅僅在整數範圍內進行。最後這個限制使得丟番圖方程求解與實數範圍方程求解有根本的不同。也叫不定方程。

在我碰到這道題之前,它已經被某人心懷惡意地發佈在網絡上,融入流行的朋友圈文化,肆意捉弄那些老實人。我根本沒意識到我偶然看到的這道題到底是個什麼樣的怪物。它長這個樣:

史上最賤的數學題

你可能已經在朋友圈看到過很多這樣的圖了,它們一般都是標題黨的垃圾:什麼“95%的麻省理工畢業生無法解決的問題”,這個“問題”要麼很空洞,要麼偷換概念,要麼就是無關緊要的腦筋急轉彎。

但這個問題不是標題黨。這張圖片就是一個精明的,或者說陰險的圈套。大概99.999995%的人根本沒有任何機會解決它,甚至包括一大批頂級大學非數論方向的數學家。它的確是可解的,但那真的真的不得了的難。

你可能會這樣想,如果所有的嘗試都失敗了,我們還可以直接用電腦計算大力出奇跡。這年頭,寫個電腦程序解決這種形式簡單的方程真是太容易了,只要它真的有答案,那電腦最終一定會找出來。但很抱歉,大錯特錯。用電腦暴力計算在這裡毫無用處。

如果不假裝讀者們入門了橢圓曲線的話,逼死我也寫不出來適合的答案。我在這能做的只是一個簡要的概覽。主要參考文獻是最近Bremmer和MacLeod2014年在《數學和信息學年鑑》(Annales Mathematicae et Informaticae)上發表的一篇名為《一個非凡的立方表示問題》(

An unusual cubic representation problem)的精彩論文。

讓我們開始吧。

02

我們求解的是這個方程的整數解

史上最賤的數學題

為了與論文的變量名相適應,我把蘋果、香蕉和菠蘿修改過來了。

對於任何方程,你需要做的第一步是嘗試後確定問題背景。這到底被劃歸到哪一類問題?嗯,我們被要求找到整數解,所以這是一個數論問題。

就題而言,方程涉及有理函數(多項式除多項式的函數形式),但很顯然我們可以用通分移項的方法化成一個多項式函數,所以我們實際上解得是一個丟番圖方程(Diophantine equation)。正數解的要求有一點不同尋常,接下來我們會看到這個要求會讓問題變得多麼難。

現在,我們有了多少變量?這個問題看起來很蠢:很明顯,我們有三個變量,分別是a、b、c。讓我們慢一點來。

一個科班出身的數論學家第一眼就能察覺到,這個方程是齊次的。這意味著如果(a,b,c)是方程的一個特解的話,那(7a,7b,7c)也是它的解。你能看出為什麼嗎?給每一個變量乘一個常數沒有改變方程的結構(7只是一個例子),因為分子分母全部都約掉了。

史上最賤的數學題

這意味著這個方程看上去像是三維的,但它實際上只有兩維。在幾何學中,它對應著一個面(一個三元方程一般定義一個兩維的面。一般來說,k個n元方程定義一個d維的流形,d=n-k)。這個面是由一條過原點的線旋轉形成的,可以通過截取的單平面來理解。這是一條射影曲線。

用最基礎的語言來表達,這種降維可以這麼解釋:無論解是什麼,我們都可以分為兩類,c=0的情形和c≠0的情形。第一類僅僅涉及兩個變量(所以自然是二維的),而第二類情形我們可以對所有解同時除以c並得到一個c=1的解(在上上一段,我們已經說明了這樣一組解也一定是方程的解)。

因此我們可以在c=1的情況下尋找a和b的有理數解,只要乘以一個公分母,就得到了a,b,c的正數解。一般來說,齊次方程的整數解對應一個低一個維度的非齊次方程的有理數解。

接下來的問題是:這個方程的次數是什麼?次數指的是各項中最高的冪次,對於涉及多個變量相乘的項,冪次就是各變量冪次之和。舉個例子,如果某項為a2bc4 ,那此項的次數就是7=2+1+4 。

丟番圖方程在不同次數難度完全不一樣,寬泛地說:

  • 一次的非常簡單。
  • 二次的也被理解得非常透徹,一般能用相對初等的方法解決。
  • 三次的就是滿山滿海的深奧理論和數不勝數的開放問題。
  • 四次的,嗯,真的真的很難。

我們這個方程是三次的。為什麼?嗯,去分母之後就很顯然了:

即使沒有合併同類項,你也可以明白地看到次數為3:沒有超過三個變量的乘積,最後我們得到的是類似a3、b2c、abc這樣的項,而沒有冪次超過3的。合併同類項後,方程整理如下:

a3+b3+c3−3(a2b+ab2+a2c+ac2+b2c+bc2)−5abc=0

你可能會反對這樣的變形:因為這樣獲得的解可能恰好使某個分母等於0,使得原方程沒有意義。這是對的,我們的新方程的確有些解不與原方程對應。但這是好事。這個多項式形式給原方程打上了一些補丁使得它便於處理;對於我們找到的任何特解,只需要代入原方程檢驗一下分母等不等於0就可以了。

事實上,多項式方程很容易找到某個特解,比如說, a=−1 ,b=1, c=0。這是好事:我們有了有理數解,或者說有理點。這意味著我們的立體方程(3維)實際上是個橢圓曲線。

當你發現這個方程是橢圓曲線時,你會喜出望外,然後悲從中來,因為你發現橢圓曲線問題是個龐然大物(學渣哇的一聲哭出來)。

注:這裡不是大家熟悉的圓錐曲線中的橢圓,而是域上虧格為1的光滑射影曲線。對於特徵不等於2的域,它的仿射方程可以寫成:y2=x3+ax2+bx+c。複數域上的橢圓曲線為虧格為1的黎曼面。Mordell證明了整體域上的橢圓曲線是有限生成交換群,這是著名的BSD猜想的前提條件。阿貝爾簇是橢圓曲線的高維推廣。By 百度百科。

這個經典的方程案例可以使我們窺見橢圓曲線理論的強大,證明它可以被用來尋找一些爆難問題的解。

03

首先,我們需要把橢圓曲線化成魏爾斯特拉斯形式。

注:Weierstrass,提起他最著名的成就就是嚴密化微積分的ε-δ語言。

這是一個長得像這樣的等式:

y2=x3+ax+b

或者有時候也會化成

y2=x3+ax+bx+c

這被稱為長魏爾斯特拉斯形式。它並不是嚴格必需的,但有時候會帶來一些便利。

眾所周知,任何橢圓曲線都可以化成這種形式(在特徵為2或者3的域特別基礎,如果你研究特徵特別小的域,那結果就不一樣了,我們此處不作討論)。如果想講清楚怎麼把橢圓曲線化成這種形式,那可就是長篇大論了(學渣的碎碎念:我信我信)。

你只需要知道,這種變形是完全機械的操作(關鍵在於方程至少存在一個有理數點,而我們已經確定了一個有理數點)。現在有若干計算機函數包可以輕而易舉地幫你搞定這件事。

但即使你不知道如何完成變換,驗證它也是很容易的,或者說至少是機械的。對於我們而言,需要的變換由令人生畏的公式導出。

史上最賤的數學題

不得不說,這看上去就像隨意的巫毒把戲,但請相信我它不是。一旦你完成了這些變形,沉悶但異常直白的代數計算可以證明它是對的。

y2

=x3+109x2+224x

這個方程儘管看起來和原方程長得不怎麼像,但確是如假包換的可靠模型。在圖像上它長成這樣,一條有著兩個實部的經典橢圓曲線:

史上最賤的數學題

右邊的“魚尾”連續延伸至正負無窮。左邊的封閉橢圓曲線將成為解決問題的契機。給定這個方程的任意解(x,y),你都可以通過下面的等式還原所求的a,b,c:

史上最賤的數學題

請注意,三元組(a:b:c)是在射影曲線上理解的——無論你從這些方程中獲得什麼數值,你都可以隨意乘上一個你想要的常數。

如前所述,無論是從a,b,c到x,y的映射還是逆映射,都可以證明這兩個方程從數論的角度是等價的:一個方程的有理數解可以導出另一個方程的有理數解。專業術語叫做雙向有理等價(birational equivalence),而這個概念在代數幾何裡面非常基礎。

如前所述,在a+b,a+c 或者b+c恰好等於0時,存在不相互對應的特殊點。這是構造雙有理等價的必要代價,大家不需要對此有任何擔心。

04

讓我們來看看手裡的這個例子。它的橢圓曲線存在一個很好的有理數點:x=−100, y=260。可能找到這個點不太容易,但檢驗它在曲線上就很簡單了:直接代入原方程檢驗等式兩邊是否相等(我不是隨機摸的點,但各位不用關心這個問題)。我們可以簡單地驗證a,b,c代入的結果。

我們得到了a=2/7,b=−1/14,c=11/14,既然我們可以隨意乘以一個公分母,那我們就可以變形為a=4,b=−1,c=11.

代入原方程,的確:

4/(−1+11)−1/(4+11)+11/(4−1)=4

你可以很容易地驗證。這就是我們原方程的一個簡單整數解——但很遺憾,不是正整數解。找到這個解用手算不太容易,但用一點耐心即使不用計算機也不算太難。它將成為我們找到正數解的緣起之地。

現在,一旦你在橢圓曲線上找到了有理數點,如P(-100,260),你就可以利用弦切技巧進行加法,生成其它的有理數點(有理數的加法是封閉的,有理數加有理數還是有理數)。

05

在任何情形下,在一個域(實數域R或者有理數域Q)中給定一個方程,解可以被視為位於R2或者Q2 的點(來自R2或者Q2的射影),而相加律就是弦—切結構的變形:想要對兩個點P1和P2做加法,首先構造一條過二點的直線(弦),若P1,P2重合,那麼這條直線就是曲線的切線。

史上最賤的數學題

▲圖解:橢圓曲線上點的加法

找到直線與曲線的第三個交點P,對O和P重複上述操作,再次得到的交點就是P1+P2。當O點被選為無窮遠處的點(一般都這麼處理),圖像就如上所示。

注:至於O點是什麼,這就涉及群論和更深奧的橢圓曲線知識,懂的自然懂,不懂的我也講不懂,因為我也不懂。

06

一開始,我們可以通過作P點的切線,找到它和曲線再次相交的點,以此增加P點的值。結果開始變得有點嚇人P+P=2P=(8836/25,−950716/125)。

同樣的,這個新的點也對應一組a,b,c的值,(a,b,c)=(9499,−8784,5165)。

這個解用手算很困難,但用電腦就是小意思了。然而,它還不是正的。

當然,困難嚇不倒我們,我們繼續計算3P=2P+P,操作方法就是連接P和2P找到與曲線的第三個交點再與O點相連找到第四個交點。同樣的,我們計算a,b,c,然而還是同樣的,結果不是正數。以此類推,計算4P,5P等等等等。

直到我們計算到9P。

9P=(-66202368404229585264842409883878874707453676645038225/13514400292716288512070907945002943352692578000406921,58800835157308083307376751727347181330085672850296730351871748713307988700611210/1571068668597978434556364707291896268838086945430031322196754390420280407346469)

很明顯這不是人算的了,但交給機器,這也就是9次簡單的幾何程序迭代。對應的a,b,c值也很恐怖:

a=154476802108746166441951315019919837485664325669565431700026634898253202035277999,b=36875131794129999827197811565225474825492979968971970996283137471637224634055579,c=4373612677928697257861252602371390152816537558161613618621437993378423467772036

這些是80位數!你不可能通過暴力計算找到一個80位數!

注:簡單的算術題,按確定兩個變量驗證第三個變量為整數的算法計算,總共的組合數就是10160 ,神威太湖之光的峰值計算能力為12.5億億次每秒,折算不過1018次/s,至少需要10142秒,大約 10134年,更震撼的寫法就是1億億億億億億億億億億億億億億億億年。

但無論它看上去怎麼不可思議,但這些數值代回原方程,的確等於4:

史上最賤的數學題

07

讓我們回到理論本身再探討一下。定義在有理數上的橢圓曲線存在一個階(rank),它表示我們最開始至少需要知道多少個有理點才能通過弦切方法找到曲線上所有的有理數點。

我們這條橢圓曲線的階等於1,這意味著:雖然它上面有無窮多個有理點,但它們都是由一個有理點生成的,不用懷疑,這個點恰好就是我們最開始的那個P點(-100,260)。

計算階數並找到這樣的一個生成元的算法非同尋常,但SageMath(現在叫CoCalc)只需要幾行代碼1秒鐘就搞定了。你可以查看我的代碼(here),它從頭開始再現了整個解法,當然其中有Sage內置的橢圓曲線處理方法。

在我們看來,P點位於曲線的橢圓部分,而其它的mP(m為正整數)點也一樣。它們會逐漸跑遍整個橢圓並最終均勻地分佈在整個曲線上。而我們是很幸運的,因為只有很少一部分橢圓能產生a,b,c的正數解:它們是下面這張圖加粗的部分(引自Bremmer和MacLeod的論文)。

史上最賤的數學題

P,2P等點並不在黑色加粗的部分,但9P恰好在,使我們得到一個80位的正整數解。

Bremmer和MacLeod還研究瞭如果我們把等式右邊的4換成其它的東西會怎麼樣。如果你覺得我們的解太大了,那是因為你還沒見識到把4換成178的結果。那就不僅僅是80位了,你需要398,605,460位數。

對,你沒看錯,那個解就是這麼大。如果你試試896,位數就飆升到數萬億位了。沒錯,數萬億位的解,屬於這個看上去人畜無害的方程。

史上最賤的數學題

08

上述的丟番圖方程就是一個係數很小但整數解位數巨大的駭人案例。它不僅僅是令人生畏的符號,還是一項意義深遠的研究。

希爾伯特第十大問題的否證陳述意味著,隨著係數逐漸增大,解的增長將變為一個不可計算的方程——因為如果它是可計算的,那我們就能得到一個解開丟番圖方程的簡單算法——而事實上並沒有,無論是簡單的還是複雜的(也就是不存在經有限步驟解決丟番圖方程的方法)。

這項研究暗合否定陳述:4->80位,178->數億位,896->數萬億位,讓我們瞥見那個怪異的、不可計算的函數的一貌。稍稍把我們的方程改動一下,解就會迅速增長到蓋過我們這個“可憐的”、“渺小的”宇宙的任何事物。

何其美妙、何其揶揄的小小方程!

更新:除了對解的估計不足,很多朋友在暴力求解時往往還會忽略一個問題——精度。程序自帶的Double類型精度是有限的,面對小數部分極長的數字(bigdecimal)時,往往會引入錯誤的解,或者漏掉正確的解。

比如a=688,b=8600,c=1599,各位可以用計算器(我用手邊的科學計算器試驗過)算一下,結果竟然是4!問題解決了嗎?並沒有,因為實際結果是4.0000000001800191239488843569645。

如果賦值給double型變量,這組解的問題就可以解決了(事實上,輸出的時候也是4,只是內部運算(a/(b+c)+b/(a+c)+c/(a+b)==4)會是false)——但不能保證,後面那麼多三元組中不會出現一組數超過double類型的精度(事實上,很可能有很多組超出精度,不過我的計算機已經找不到了),也不能保證有一臺計算機計算到真正的解附近時因為精度問題把它忽略了(我們假裝這個解並沒有80多位數)。

因此,暴力破解也並不能完全“暴力”。

來源:南京大學科幻愛好者協會(ID:njusfa)


分享到:


相關文章: