希爾伯特第十個問題- Robinson cover

破解希爾伯特第十個問題——她的畢生夢想與關鍵角色

破解希爾伯特第十個問題——她的畢生夢想與關鍵角色

破解希爾伯特第十個問題——她的畢生夢想與關鍵角色

「茱莉亞·羅賓遜 (Julia Robinson) 的名字絕不能被排除於希爾伯特第十個問題之外。」最終解決了希爾伯特這個大哉問的俄國數學家馬季亞謝維奇 (Yuri Matiyasevich),於 1992 年特別發表一篇回顧的文章,開頭第一句便如此宣告羅賓遜的重要性。

什麼是希爾伯特第十個問題?

1900 年,大數學家希爾伯特 (David Hilbert) 在第二屆國際數學家大會上提出 23 道最重要的數學問題,其中第十個問題是:

是否存在一種演算法,可以判定任一個係數均為整數的多項方程式有整數解?

例如:3x2 – 2xy – y2z -7 = 0 有整數解 x=1, y=2, z=-2

但 x2 + y2 + 1 = 0 就沒有整數解。

丟番圖方程式

係數均為整數的多項方程式又叫「丟番圖方程式」,名字源自三世紀時對此有相當研究的希臘數學家亞歷山大城的丟番圖 (Diophantus of Alexandria)。很多我們熟悉的問題都是丟番圖方程式,例如:「雞兔同籠,共有18 隻腳,請問有幾種雞兔組合?」這個問題就相當於 2x + 4y = 18 有幾組正整數解。還有畢氏定理: a2 + b2 = c2 也是有整數解的丟番圖方程式。

有些丟番圖方程式我們可以確定有沒有整數解,例如雞兔同籠問題如果全部的腳是奇數,顯然就不存在整數解,但有些就不是那麼容易判斷了,例如費馬最後定理。費馬於 1637 年在丟番圖的《算術》拉丁文譯本的一頁邊緣空白處寫下:

「一個立方數不可能是兩個立方數之和,一個四次方數不可能是兩個四次方數之和;概括的說,任何指數大於2的數,都不可能是兩個同樣指數之數的和。我已經發現這個命題的美妙證明,只是邊緣太窄寫不下。」

也就是說:整數n大於2時,an + bn = cn 沒有正整數解。

然而,在他之後沒有人能加以證明,包括歐拉、高斯在內的大數學家也只證明在某些特例下成立(例如 n = 3 及 n = 5),令人不禁懷疑費馬是否真的找到證明,因此只能視之為猜想。直到 1994 年,英國數學家懷爾斯 (Andrew John Wiles) 才終於成功證明,讓這則猜想正身為定理。 還有許多丟番圖方程式也是看似簡易,卻仍無法確定有沒有整數解,所以希爾伯特在二十世紀之始將它列入最重要的數學問題之一。近半世紀後,這也成為茱莉亞·羅賓遜魂牽夢縈,立誓窮盡一生也要完成的終極目標。

羅賓遜的成長歷程

羅賓遜 (Julia Robinson) 幼年因病休學。圖片來源:courtesy of Neil Reid

羅賓遜本性鮑曼 (Bowman),1919 年出生於美國密蘇里州,兩歲時母親過世後,父親隨即再娶。她 9 歲時隨家人搬到聖地牙哥,卻得了猩紅熱,接著又因感染而產生風濕熱,以致休學兩年,其中一年還因住院療養,與家人分離,只有護士陪伴。儘管如此,她很快就趕上學業,高中成為全校唯一先修數學與物理的女學生,而且 16 歲就進入聖地牙哥州立大學就讀數學系。

大二時,羅賓遜的父親因生意失敗自殺,她仍繼續苦讀,大四轉到加州大學柏克萊分校,與授課的數學教授陷入愛河,1941 年念碩一時就與他結婚。由於過去的經歷,她一直期待生兒育女,有個完整的家庭。無奈幼時罹病傷及身體,在一次流產後,醫生告知她不能再懷孕,成為她最大的遺憾。

她於 1948 年拿到數學博士後,在一家智庫公司找到工作,沒幾年她就回到柏克萊,但限於當時的規定,不能與丈夫同在數學系任教,她只剩在統計系教微積分的機會,而且沒有自己的辦公室,只能擠在先生那裏。儘管工作與收入都不穩定,她仍甘之如飴,持續鑽研她畢業後就一頭埋進去的希爾伯特第十個問題。

兩種進攻策略

羅賓遜的博士論文是關於指數函數的判定問題,因此她選擇從 a = bc 這種特定形式的丟番圖方程式著手,例如當 c = 2,那麼顯然只有 a 是平方數時,才有整數解。她雖然未能找出通則,但至少證明在某種前提下,a = bc 有整數解。

她在 1950 年的國際數學家大會上發表論文,在場的另一位美國數學家戴維斯 (Martin Davis) 才告訴她自己也在研究希爾伯特第十個問題,不過他採取的是完全不同的策略。由於當時已經證明存在有些「遞迴可列舉集合」(註一),無法判定某一自然數是否屬於該集合,因此只要證明丟番圖方程式的解和遞迴可列舉集合有對等關係,就代表有些丟番圖方程式無法判定,從而證明希爾伯特第十個問題的答案是否定的。

戴維斯 (Martin Davis)。圖片來源:Wikipedia

戴維斯當場好心勸告羅賓遜,說她的方法恐怕只會離目標越來越遠。但羅賓遜仍按既定策略繼續埋首研究。她每年生日總是會許下「有一天會得知希爾伯特第十個問題的答案」這個願望。她甚至不在乎率先抵達終點線的是不是自己,「我覺得如果不知道答案,我會死不瞑目。」她如此向身為數學科普作家的姊姊表達內心的渴望。

兩種策略合一

1960 年,她收到戴維斯的來信,說他後來和普特南 (Hilary Putnam) 合作,最近才發現如果質數序列包含任意長的等差數列,那麼羅賓遜的方法便可用來證明遞迴可列舉集合一定是丟番圖方程式的解,反之,丟番圖方程式的解也一定是遞迴可列舉集合。

普特南 (Hilary Putnam)。圖片來源:Wikipedia

羅賓遜很快回信,表達對於他們的成果十分驚喜,但她發現他們的證明可以再加以簡化,不需要質數序列的假設就能成立。如此一來,只要「羅賓遜猜想」——也就是她十年前所設定的那個前提——能夠證明為真,希爾伯特第十個問題也就解決了。

羅賓遜和戴維斯、普特南三人繼續研究,卻始終無法跨越這關鍵的最後一步,他們都不知道遠在地球的另一邊,蘇聯鐵幕內有位青年也在研究希爾伯特第十個問題,而他將後來居上,尋獲這個聖杯。

同時在蘇聯那邊……

馬季亞謝維奇自小展露數學天分,曾贏得蘇聯境內的數學奧林匹亞競賽冠軍。1965 年他大二時,數學老師建議他試試希爾伯特第十個問題,他問老師應該先研讀那些材料,老師告訴他:「美國數學家是有寫了幾篇關於希爾伯特第十個問題的論文,不過你不用讀這些東西。」「為什麼?」「因為他們到現在都沒有成功,表示他們的方法很可能不恰當。」

馬季亞謝維奇 (Yuri Matiyasevich)。圖片來源:Wikipedia

於是馬季亞謝維奇根據老師的建議,採取完全不同的途徑,但幾次以為有所進展卻又發現證明有誤。到了 1968 年,他終於去找羅賓遜等人的論文來讀,才發現他們的方法相當值得研究,於是他組織研討會,邀請數學家來參加,但才沒幾次就只剩下他一個人。他於 1969 年畢業後,繼續攻讀博士,決定不要再浪費時間在這上面。

沒想到這年秋季的某一天,他的同事就興沖沖地叫他趕快去圖書館,剛出版的美國數學期刊裏頭有一篇羅賓遜新發表的論文。但馬季亞謝維奇心意已決,他不想再去了解希爾伯特第十個問題的進展。

怎料命運之神再度來敲門,或者按照馬季亞謝維奇自己的話:「數學天堂裡的某個地方,一定有個數學之神或女神,不肯讓我錯過茱莉亞·羅賓遜的新論文。」由於他過去的經歷,儼然已是這個問題的專家,因此蘇聯一家數學雜誌把羅賓遜這篇論文寄給他,要求他發表評論。他還是逃不開希爾伯特第十個問題。

希爾伯特第十個問題終於解決

羅賓遜的新論文只有 5 頁,把問題簡化到 a = 2c這個更為簡潔的丟番圖方程式,為「羅賓遜猜想」的證明提供一個新思路。馬季亞謝維奇立刻想到他之前研究希爾伯特第十個問題時,有個產生費波那契數 的丟番圖方程式與這有異曲同工之妙。於是他循著羅賓遜這個思路,重新投入研究,結果在 1970 年 1 月就成功證明羅賓遜猜想。高懸 70 年的希爾伯特第十個問題終於拍板定案:並沒有可以判定任一丟番圖方程式是否有整數解的演算法。

羅賓遜得知這個消息後十分興奮,她寫信給馬季亞謝維奇:「這真是令我特別欣喜,想到我最初提出這個猜想時,你只是個小小孩,而我只能等,等你長大。」他們兩人從此互相書信往返,繼續在希爾伯特第十個問題上合作。咦,這問題不是已經解決了嗎?是沒錯,但數學家仍想知道某些特定的丟番圖方程式是否有解(註二)?或者能否把無法判定的丟番圖方程式範圍縮小?

羅賓遜終獲肯定

Julia Robinson 攝於 1975 年。圖片來源:Wikipedia

1973 年,羅賓遜的先生退休,但柏克萊仍沒給她全職的教職。直到 1975 年,羅賓遜成為第一位獲選為美國國家科學院院士的女性,她才終於獲得柏克萊的正式聘書。1982 年,她又成為第一位女性,擔任美國數學學會的主席。

雖然獲得諸多殊榮,不過羅賓遜在她姐姐為她寫的傳記中表示:

「與其被記得是這個或那個的第一位女性,我寧願像一位數學家那樣,純粹因為我證明的理論與解決的問題而被記得。」 1985 年,羅賓遜因白血病不治過世,享年 65 歲。如果真有數學天堂,她一定在上面吧。

註:

一、遞迴計算是指下一個數是用前面的數算出來的,例如費波那契數 (Fibonacci number) 從 1、1 開始,之後每個數字都是由前兩個數字相加產生:1、1、2、3、5、8、13、……,以此類推。費波那契數就屬於遞迴可列舉集合。

二、例如 2019 年有個相當引起注目的數學新聞:

42 = (–80,538,738,812,075,974)3 + 80,435,758,145,817,5153 + 12,602,123,297,335,6313

n = a3 + b3 +c3 就是一種丟番圖方程式,自 1955 年以來,數學家一直試圖找 n 等於不同數字時,是否有整數解。直到 2019 年 8 月,已經知道 100 以下的數字哪些可以表示成三個數字的立方和,那些不行,唯獨剩下 42 還不知道。因此,當九月發現這個解答後,還蠻轟動的,尤其對於科幻迷而言,42 可是個特別的數字,它是生命、宇宙與一切的最終答案!

參考資料:

  1. My Collaboration with JULIA ROBINSON (pdmi.ras.ru)
  2. Foreword to “Hilbert’s tenth problem” by Yuri MATIYASEVICH (pdmi.ras.ru)
  3. How Julia Robinson helped define the limits of mathematical knowledge | Science News
  4. Wikipedia 相關條目
  5. 數學家接連破解超過六十年未知的丟番圖方程式: 33和42的三立方和問題 – UniMath (google.com)

更多文章

© 2021 張瑞棋