兩名數學家已經證明了一個長期存在的猜想，這是在平面上尋找最差堆積形狀的道路上邁開的一步。

圖源：Nico Roper / Quanta Magazine

作者：Gregory Barber《量子雜志》特約撰稿人 2024-6-28

譯者：zzllrr小樂（數學科普公眾號）2024-6-29

幾個世紀以來，數學家們一直猜測六邊形瓷磚是鋪滿平面的最佳方式。這意味著，如果你想將大面積瓷磚細分為相同尺寸的瓷磚，并使得每個瓷磚的周長最小，那么沒有比六邊形更佳的形狀。1999年，匹茲堡大學的托馬斯·黑爾斯（Thomas Hales）終于證明了這一點 https://arxiv.org/abs/math/9906042 。六邊形比正方形、三角形或任何其他替代品都要好。

但是許多形狀不能在不留縫隙的情況下密鋪。例如，圓形顯然不能。一個六邊形的圓形堆積，擺弄最佳陣型之后，將覆蓋近90.69%的平面。

圖源：Mark Belan / Quanta Magazine

在1920年代，數學家們開始思考：堆積最差的形狀是什么？換句話說，什么形狀會留下最大的縫隙，即使你以最優(yōu)的方式堆積它？Hales和他以前的研究生Koundinya Vajjha（瓦杰哈，現在是英特爾的工程師）的一篇新論文 https://arxiv.org/abs/2405.04331 標志著這類形狀搜索的重大突破。

定義一個最差的形狀需要一些規(guī)則。很容易想出包含孔洞或向內凹陷的任意差的形狀，例如這些鏤空的正方形：

這些差的形狀在數學上并不是那么有趣，因為通過使邊緣變得更薄，可以很容易地想出一個形狀，迫使任意大部分面積成為空的。但是，如果你加上形狀是凸（convex ）的要求——這意味著如果你選擇形狀中的任意兩個點，連接它們的線段將包含在形狀中——那么像這樣的空心形狀是被禁止的，事情就會變得更加有趣。

數學家對具有一個附加約束的形狀感興趣：中心對稱性。在不要求中心對稱性的情況下，已知最差的形狀是正七邊形（覆蓋平面：約89.27%），盡管數學家遠不能證明它是最差的。Hales和Vajjha研究了一個更受限制、因而更簡單的問題：什么是最差的既是凸形又是中心對稱的堆積形狀？

在中心對稱形狀中，例如一個八邊形（左圖），從中心到邊緣畫出的線與其在中心點上的反射的長度相同。而對于一個七邊形（右圖），這個結論是不成立的。

數學家最初認為它是一個圓。然后，在1934年，一位名叫卡爾·萊因哈特（Karl Reinhardt，1895 - 1941，請勿與另一個同時代同國同名文學家混淆，zzllrr小樂譯注）的德國數學家發(fā)現了更差的形狀：一個邊緣圓潤的八邊形。當使用雙曲線繪制角中的這些弧線時，總覆蓋率約為90.24%。這與圓的90.69%相比差異很小，但在數學上至關重要。

萊因哈特無法證明他的圓角八邊形是最差的形狀。其他人也做不到。“我一直認為萊因哈特可能是對的，但這個理論并不是為了解決這個問題，”微軟研究院的數學家亨利·科恩（Henry Cohn）說，他以在更高維度上堆積球體的工作而聞名。“我們能看到證明嗎？可能在我有生之年都不會。”

這樣的一個證明還沒有到來。但Hales和Vajjha五月的論文證明了一個關鍵的中間猜想。

比起在六邊形上的成果，Hales更為出名的是，他在1990年代后期證明了約翰內斯·開普勒（Johannes Kepler，1571 - 1630）在17世紀關于在三維空間中堆積球體的最佳方法的猜想（有時被稱為橙子堆疊問題，因為它喚起了市場上成堆的水果）。但由于它依賴于計算機計算，因此在證明首次發(fā)表后，他花了數年時間才說服數學界相信其有效性。

2007年，在越南休假期間，Hales在證明開普勒的猜想時，將注意力從最優(yōu)的堆積轉向最差的堆積。但進展緩慢。

最差的情形尚未到來

最差堆積問題要求其最大堆積密度是所有堆積形狀中的堆積密度值最小的形狀。這些類型的約束問題屬于一類稱為最小最大值問題（minimax problems ），這些問題本質上是棘手的。處理它們的標準方法是通過一組稱為變分法（calculus of variations）的技術。萊因哈特將其用于他的堆積問題，試圖證明圓角八邊形的最優(yōu)性。圓角點用雙曲線描摹，雙曲線在不弄亂堆積的情況下盡可能多地減少面積。這意味著預期的解不僅涉及曲線，還涉及曲線和直邊的混合。

Hales試圖從萊因哈特離開的地方繼續(xù)，但他很快意識到變分法不足以解決問題。他觀察到，核心問題是，雖然這些技術有助于找到最適合一組所需參數的最優(yōu)曲線，但他正在尋找的解并不完全是曲線。如果解像萊因哈特所猜想的那樣，它將是一個更復雜的結構，將曲線和直邊混合在一起。

幾十年前，Thomas Hales因證明最優(yōu)堆積而聞名。現在他把注意力轉向了最差的情形。

圖源：Joe Appel

2017年，經過十年的斷斷續(xù)續(xù)的工作，Hales發(fā)表了一份預印本 https://arxiv.org/abs/1703.01352 ，為證明提供了某種藍圖。他建議使用一種稱為最優(yōu)控制論（optimal control theory）的數學分支，他認為這種分支更適合探索大轉彎的結構。對于其他數學家來說，一個難以解決的問題突然變得可行了。“這種創(chuàng)造力給我留下了深刻的印象，”Cohn說。“但另一方面，我想，要真正實現它需要做很多工作。”

在Hales提出他的藍圖后不久，Vajjha來到匹茲堡時感到有些迷茫，就像許多學生在研究生院的早期一樣。他希望研究形式化的方法——用于驗證軟件和硬件的技術——并參加了鎮(zhèn)上的各種講座，以尋找合適的問題。在其中一次講座中，他了解到尋找最優(yōu)的最差堆積，他發(fā)現這個問題的欺騙性技巧很有趣。那天晚些時候，當他發(fā)現Hales的預印本時，他更感興趣，該預印本提出了一種全新的方法來解決這個問題。

兩人在接下來的一周見面了。“我告訴他，‘如果這很容易，你為什么不去做呢？'”Vajjha回憶道。Hales回答說，他們可能會在大約六個月內一起解決這個問題。Vajjha同意了。“事情從來都不是那么容易的，”他最近說。

為了證明圓角八邊形是堆積最差的形狀，Hales和Vajjha實際上不得不排除所有其他可能的形狀。即使有中心對稱和凸性等約束條件，他們也在盯著一個具有無限潛在答案的問題，其中許多表現出奇怪的行為，使它們看起來是可行的解，而實際上它們是無效的。例如，有一些候選形狀會在直線和曲線之間無限次地翻轉，稱為“顫動”解（chattering solution）。這聽起來可能很矛盾，但這樣的形狀可能比圓形更好。它們甚至比萊因哈特的圓角八邊形更好嗎？

Hales對開普勒猜想的大量證明使用了一種計算機輔助方法，該方法涉及用蠻力排除幾乎無窮無盡的可能堆積。它被認為是開創(chuàng)性的——而且在當時有點爭議，因為審稿人發(fā)現這些程序很難驗證。Hales希望使用類似的方法來找到最壞的形狀，但潛在的“顫動”解是一個障礙。“如果事情無限多次切換，那么在計算機上做到這一點并不容易，”Hales說。

要消除這些結構和其他晦澀難懂的結構，就需要找到創(chuàng)造性的方法來排除它們。他們試圖通過引入新的對稱約束來簡化問題，然后回到原來的問題。“就像在物理學中一樣，數學中有這樣的想法，如果你有對稱性，就有守恒定律，”Hales說。這些法則可能有助于排除一些結構。

Koundinya Vajjha現在是英特爾的一名工程師，他花了數年時間證明圓角八邊形是最差的堆積形狀。

圖源：Vihasi Jani

盡管如此，新的可能性不斷出現。“我知道這個問題很難解決，但你總是有更多的結構可以解開，”Vajjha說。“總是只有六個月的時間。”五年過去了，他遲遲沒有拿到學位。他打算結婚并搬到西海岸。“我們永遠不知道這個問題什么時候會反擊，并在下一個世紀內得不到解決。留下一個不完整的證名的想法是痛苦的，但他只是鞭長莫及了。他于2022年8月畢業(yè)，曾在一家AI初創(chuàng)公司短暫工作，然后在英特爾正式做驗證CPU的工作，回到了他預期的研究領域。

第二年春天，Vajjha回到匹茲堡參加他的畢業(yè)典禮。他和Hales感嘆說，他們設法詳細說明了許多新的想法和方法，但沒有產生一個堅實的定理。一周后，Hales意識到：他們幾乎證明了庫爾特·馬勒（Kurt Mahler，1903 - 1988）在1946年提出的相關猜想，庫爾特·馬勒是一位獨立于萊因哈特工作的數學家。“我一直對馬勒有點不屑一顧，因為他和萊因哈特在做同樣的事情，只是幾年后做，”Hales說。但是馬勒通過將問題分解為兩個步驟做出了重要的觀察。他的第一個猜想是，答案是一個光滑的多邊形，直邊和角用雙曲線弧接。他的第二個猜想與萊因哈特的相同——圓角八邊形是最差的形狀。兩人還沒有完全達到馬勒的第一步，但Hales意識到他們已經很接近了。他懇求Vajjha花一個月的時間考慮一下。

那個月來來去去，兩人開始交換電子郵件——揭示更多的結構并駁回它們，承認更多的懷疑和疲憊。一個月延長到一年。然后，最后，Hales給Vajjha發(fā)了一條信息。馬勒的第一個猜想，“又回到了地平線上。我很確定我已經證明了這一點。”

他們對馬勒的第一個猜想的證明 - 六年，而不是六個月 - 是對該主題的260頁探索，詳細介紹了一系列令人眼花繚亂的候選結構，并使用了比Hales最初想象的更廣泛的理論。這項工作尚未經過同行評審，但包括Cohn和加州大學戴維斯分校數學家格雷格·庫珀伯格（Greg Kuperberg）在內的數學家對這項工作進行了非正式審查，他們表示，鑒于Hales對復雜證明的謹慎聲譽，他們對結果充滿信心。

然而，Kuperberg補充說，“他們并沒有真正越過終點線。有時，即使理論得到發(fā)展并取得了中間步驟，問題也會持續(xù)數十年。畢竟，Hales對開普勒猜想的證明依賴于匈牙利數學家拉斯洛·費耶斯·托特（László Fejes Tóth，1915 - 2005）在50年前發(fā)展的方法。“也許所有的想法都已經到位，可以完成萊因哈特的工作。也許不是，”Hales說。“我們把這當成一個問號。”

參考資料

https://www.quantamagazine.org/why-is-this-shape-so-terrible-to-pack-20240628/

https://arxiv.org/abs/math/9906042

https://arxiv.org/abs/2405.04331

https://arxiv.org/abs/1703.01352

·開放 · 友好 · 多元 · 普適 · 守拙·

讓數學

更加

易學易練

易教易研

易賞易玩

易見易得

易傳易及

歡迎評論、點贊、在看、在聽

收藏、分享、轉載、投稿

查看原始文章出處

點擊zzllrr小樂

公眾號主頁

右上角

數學科普不迷路！