尋找 x³+y³+z³ = 33 的整數解很無聊嗎？
先警告一下︰因為隨便寫所以不太有條理。下面提到的 MRDP 定理我還未看完證明，但為了寫這文章我總算了解證明的方向（我一直以為很難所以沒讀，現在看來似乎不算太難）。
上星期除了圓周率日外還有這宗新聞︰
Kayue
簡單來說，$x^3+y^3+z^3=33$ 這條方程式找到整數解，三個整數分別是︰
- 8,866,128,975,287,528
- −8,778,405,442,862,239
- −2,736,111,468,807,040
本來 33 是最小未能找到整數解的數字（不包括所有「除以 9 後餘數是 4 或 5」的數字，原因見上面連結），現在這個數字變成 ——「生命、宇宙以及任何事情的終極答案」—— 42。
這條方程式—— $x^3+y^3+z^3=k$ ——有甚麼特別嗎？也沒有很特別，不過除了非常容易證明的「除以 9 後餘數是 4 或 5」的數字外，數學界暫時未能證明其他數字不能寫成三個立方數之和，這自然令數學家想知道︰到底是否對於其他數字 $k$，上述方程式都有解？無論答案為何，數學家都想知道原因。
但在未找到證明之前，我們還是可以逐個數字試一下，今次 Andrew Booker 的新發現不僅在於找到答案，還包括改進了演算法的效率——按我有限的理解，給出特定上限 B，過往是搜尋到 $|x|, |y|, |z|$（絕對值）都在 B 以下的答案，Booker 的方法則能（在接近線性時間內）找到$|x|, |y|, |z|$最小者在 B 以下的答案。
像 $x^3+y^3+z^3=k$ 這類（係數為整數的）多項式尋找整數解的問題，稱為丟番圖方程（Diophantine equations）。$x^2+y^2=z^2$ 這個丟番圖方程相信大部分人都不會陌生，能夠滿足此方程的整數解，稱為畢氏三數組——命名源自畢氏定理——而且有無限多個。
（順帶一提，如果你把 0 到 7825 之間的所有整數分成紅色或藍色，無論你如何分配，總會存在一個相同顏色的畢氏三數組。）
有些丟番圖方程只有所謂的平凡解（trivial solution），此處指答案包含 0 的解，例如著名的費馬最後定理告訴我們，$x^3+y^3=z^3$ 只有平凡解（而且不僅是三次方，三次以上的同樣如此）。有些甚至完全沒有解，例如對於任何正整數$k$，$x^2+y^2+k=0$ 都沒有整數解（因為平方數最少是 0）。
希爾伯特第十問題（Hilbert’s 10th problem）問的是︰我們能否找到一套判斷哪些丟番圖方程有解、哪些沒有解的演算法？
Martin Davis、 Yuri Matiyasevich、Hilary Putnam（對，正是這位 Putnam）及 Julia Robinson 的研究，證明了希爾伯特第十問題無解，換言之，沒有讓數學家一勞永逸去判斷丟番圖方程有沒有解的演算法。（其實四人證明的MRDP定理有更多精彩內容，但本文略過。）
假如這套演算法存在，數學家也許沒那麼熱衷於尋找 $x^3+y^3+z^3=33$ 的解，反正不少人有興趣的是這方程有沒有整數解，而非確實答案（當然答案如此龐大仍是個有趣的發現）。
現在我們的確尚未知道 $x^3+y^3+z^3=42$ 到底有沒有整數解，而且可能永遠也不會知道。萬一這條丟番圖方程沒有整數解，但又沒有人能夠證明它沒有整數解的話，即使用電腦不斷搜尋更大的數字（然後找不到答案），我們也無辦法確定到底是「問題沒有答案」抑或只是「我們未找到答案」，畢竟答案可能遠遠超出人類以至電腦能夠計算的範圍。相反，如果找到答案的話，我們倒能夠肯定「問題存在解答」。
「特定丟番圖方程有解」在一階算術中可寫成只有一個無限制量詞（unbounded quantifier）而且那是存在量詞（existential quantifier）∃的公式，邏輯學中稱為$\Sigma_1$公式；而其否定句則等價於只有一個無限制全稱量詞（unbounded universal quantifier）「$\forall$」的公式，又叫$\Pi_1$公式。
一些數學命題如哥德巴哈猜想（Goldbach conjecture）——所有大於4的偶數都可寫成兩個質數之和——可寫成$\Pi_1$公式，假如這類命題不成立，理論上（即不考慮數字太大的問題）只靠計算就可以找到反例推翻；假如成立的話，倒是沒辦法透過計算證明。這就像玩一個有無限次機會的抽獎遊戲，只要抽中一次你就能確定這遊戲真的有獎，但一直抽不中的話你無法因此斷言遊戲是個騙局。
哥德爾不完備定理告訴我們，（粗略地說）任何包含一定算術內容而且一致的形式系統——例如皮亞諾算術（Peano Arithmetic）——之中均存在一個無法證明又無法否證的$\Pi_1$公式。我們亦可利用MRDP定理得出類似結果，找到一個無解的丟番圖方程，但這個形式系統無法證明此事（與此同時，如果你交出任何整數$n$給這個系統，它都能夠證明$n$不是該丟番圖方程的解）。
那麼，$x^3+y^3+z^3=42$ 會不會是（比方說在皮亞諾算術中）「無法證明無解」的丟番圖方程？我認為不太可能，畢竟這類方程往往需要要刻意構造出來而頗為複雜，要是如此簡單，肯定會比它有非常大的整數解更難以置信。
對 MRDP 定理有興趣的可以看這兩篇︰
另外手頭上有本在序言書室買的二手書，Martin Davis（MRDP 的 D）寫的 Computability and Unsolvability，書中第二個附錄就是講解 MRDP 定理。
（原刊於Medium）
