陶哲軒親測(cè)點(diǎn)贊o3-mini：專家級(jí)證明，我收到了一個(gè)完美的答案

十三 2025-03-11 14:12:46 來源：量子位

金磊 發(fā)自 凹非寺

量子位 | 公眾號(hào) QbitAI

剛剛，陶哲軒親測(cè)了一下o3-mini，然后他給出了這樣的結(jié)論：

重建圖論中一個(gè)標(biāo)準(zhǔn)（專家級(jí)）結(jié)果的證明，o3-mini是完全可以hold住的。

陶哲軒要重建的這個(gè)證明，叫做三角形移除引理（triangle removal lemma），由Ruzsa和Szemeredi于1978年提出，是極值圖論中的重要結(jié)果:

對(duì)于任意的η＞0，都存在c>0，使得對(duì)于任意一個(gè)足夠大的有n個(gè)頂點(diǎn)的圖，如果該圖中最多包含cn3個(gè)三角形，那么可以通過移除最多ηn2條邊，使這個(gè)圖變?yōu)闊o三角形的圖。

用另一種表述方式就是，如果一個(gè)有n個(gè)頂點(diǎn)的圖包含o(n3)個(gè)三角形，那么可以通過移除o(n2)條邊來刪除所有的三角形。

然后陶哲軒看罷o3-mini的作答后表示：

在幾秒鐘后，我收到了一個(gè)完美的答案，（o3-mini）正確地解釋了這種蘊(yùn)含關(guān)系。

o3-mini是如何作答的？

首先，我們來看下陶哲軒的Prompt：

Ruzsa和Szemeredi的三角形移除引理斷言，如果一個(gè)具有n個(gè)頂點(diǎn)的圖（n很大）包含o(n3)個(gè)三角形，那么可以通過移除o(n2)條邊使其變?yōu)闊o三角形圖。顯然，這一引理蘊(yùn)含了以下結(jié)論：如果一個(gè)具有n個(gè)頂點(diǎn)的圖是n個(gè)誘導(dǎo)匹配的并集，那么它只包含o(n2)條邊。你知道后者是如何從前者的結(jié)論中推導(dǎo)出來的嗎？

對(duì)于這個(gè)問題，o3-mini的回答是這樣的：

（注：為完整體現(xiàn)內(nèi)容，o3-mini的作答將以英文呈現(xiàn)）

可以看到，o3-mini回答的邏輯還是比較清晰的。

一步一步展開論證，從起始條件（誘導(dǎo)匹配的并集），到構(gòu)建輔助圖，再到建立邊與三角形數(shù)量的聯(lián)系、應(yīng)用引理，最后得出結(jié)論。

緊接著，陶哲軒開始追問了：

謝謝！三角形移除引理的另一個(gè)標(biāo)準(zhǔn)推論是(6,3)定理：如果一個(gè)具有n個(gè)頂點(diǎn)的3-一致超圖不包含(6,3)-配置，即不存在六個(gè)頂點(diǎn)確定至少三個(gè)超邊的情況，那么該超圖只包含o(n2)條超邊。你能解釋一下為什么這也是三角形移除引理的一個(gè)推論嗎？

o3-mini在思考了片刻后，開始作答：

o3-mini對(duì)這個(gè)問題的總結(jié)是：

在一個(gè)不包含任何 “(6,3)-configuration”（即任意六個(gè)頂點(diǎn)不生成三條或更多超邊 ）的3-uniform 超圖中，由于將超邊編碼為輔助圖中的三角形后，輔助圖的三角形結(jié)構(gòu)受超圖條件限制呈現(xiàn) “稀疏” 狀態(tài) ，根據(jù)三角形移除引理可以推斷出，該超圖中的超邊總數(shù)為o(n2)，也就是說這樣的超圖不會(huì)過于稠密。

在此之后，陶哲軒便開始加大難度：

感謝你的大致概述！我有興趣將其擴(kuò)展成一個(gè)更詳細(xì)的證明。我聽說首先考慮超圖是線性的情況會(huì)很有幫助——即任意兩條超邊不會(huì)共享兩個(gè)頂點(diǎn)。你能將你的概述擴(kuò)展成一個(gè)更精確的論證，專門針對(duì)線性情況嗎？

這一次，o3-mini思考的時(shí)間足足是上個(gè)問題的四倍：

這次o3-mini的推理過程，是通過構(gòu)造一個(gè)輔助圖G，將超圖中的每個(gè)超邊對(duì)應(yīng)到輔助圖中的一個(gè)三角形。利用線性性質(zhì)保證這些三角形邊不相交，再通過假設(shè)m=Ω(n2)推出與三角形移除引理相矛盾的結(jié)果，從而證明原假設(shè)錯(cuò)誤，得出超邊數(shù)量的漸近上界 。

陶哲軒再追問：

如何確保圖G不會(huì)產(chǎn)生任何額外的三角形，除了那些直接由超邊生成的三角形之外？

至此，陶哲軒評(píng)價(jià)道：

好的，我認(rèn)為這給出了(6,3)定理在線性情況下的完整證明。

然后繼續(xù)追問o3-mini：

你有什么建議，如何建立一般情況下使用這個(gè)線性的情況？

o3-mini給出了一種“清理”的路數(shù)：

• 清理超圖：通過刪除少量超邊使得到的子超圖H’線性化，“(6,3) 條件” 保證不會(huì)移除過多超邊。
• 應(yīng)用線性情況結(jié)論：為線性超圖H’構(gòu)建輔助圖，每個(gè)超邊對(duì)應(yīng)一個(gè)邊不相交三角形。
• 利用三角形移除引理：過多的邊不相交三角形會(huì)導(dǎo)致與引理矛盾，所以H’有o(n2)個(gè)超邊。
• 推導(dǎo)原始超圖的邊界：因?yàn)镠’保留了H’的幾乎所有超邊，所以原始超圖H’也有o(n2)個(gè)超邊。

陶哲軒認(rèn)為這是一個(gè)不錯(cuò)的策略，并最后提出了一個(gè)問題：

你能不能試著給出一個(gè)更精確的清理步驟的描述，這個(gè)步驟可能會(huì)把一個(gè)一般的(6,3)超圖轉(zhuǎn)換成一個(gè)線性的(6,3)超圖，并對(duì)邊緣進(jìn)行一些控制？

但也有局限性

在陶哲軒六連問之后，除了剛才提到的“完美答案”之外，他還給出了更加客觀中立的評(píng)價(jià)：

我的總體感覺是，至少對(duì)于研究級(jí)的數(shù)學(xué)任務(wù)，當(dāng)前的模型在“僅需用戶提供大致指導(dǎo)即可真正有用”和“只有在用戶提供大量詳細(xì)指導(dǎo)后才有用”之間波動(dòng)，而最強(qiáng)大的模型在前者中的回答比例更高。

它們似乎特別適合那些非常標(biāo)準(zhǔn)的問題，這些問題的答案基本上可以在現(xiàn)有資源（如維基百科或StackOverflow）中找到。

但隨著問題變得越來越冷門，成功率逐漸下降（盡管下降的方式較為平緩），并且需要更多的用戶指導(dǎo)（或更高的計(jì)算資源）才能使LLM的輸出達(dá)到可用的形式。

陶哲軒的這波實(shí)測(cè)也引發(fā)了不少網(wǎng)友的討論。

例如有人質(zhì)疑LLM的推理能力，認(rèn)為它們是隨機(jī)文本生成器，而不是真正的推理模型。他指出LLM的輸出依賴于點(diǎn)贊/踩票信號(hào)，而不是真正的邏輯推理。

陶哲軒與o3-mini完整對(duì)話：
https://chatgpt.com/share/67cf13cf-53dc-800e-a382-e4ece8341a6d

參考鏈接：
https://mathstodon.xyz/@tao/114139145175476223