大家都知道陶哲軒得了費爾茲獎，可能也知道他得獎得結果是證明了存在任意長的質數等差數列，即Green-Tao Theorem。不過可能很少有人了解具體的做法。
質數等差數列，比如3，5，7 。更長一點的，比如7，37，67，97，127，157 。如果沒記錯，目前人們知道的最長的質數等差數列也只有26項，所以G-T定理還是很不平凡的結果。
這個證明基本上就是用 圖論 和 組合數學 做的，基於Szemeredi regularity lemma和Szemeredi theorem。Szemeredi本人透過這個定理拿了Abel獎，Gowers用調和分析構造了regularity lemma中常數的界拿了費爾茲獎，Tao推廣了這個定理也拿了費爾茲。難怪我老板說，10年之內regularity lemma將是人人都會用的工具。（特別的，Frieze和Kannan給出了regularity lemma的弱化版本，利用graph limit的理論在理論電腦中套用非常多。）
關於graph limit的最最基本的理論可以參考有哪些指標可以描述兩個圖（graph）的相似度？ - 知乎
G-T定理具體的證明過程大家估計不感興趣，我說一下大概的思路。
Erdos有一個很有名的猜想，是說我有一個自然數的子集A，裏面的元素是 a_1,a_2,\dots ，如果 \sum_{i\geq1}\frac{1}{a_i}=\infty ，那麽A中有任意長的等差數列。這個猜想至今還open，人們甚至不能證明A中有長度為3的等差數列。。G-T定理是這個猜想的特殊情況，因為所有質數倒數和也是無窮的。至於一般情況，誰能證出來這個，估計Fields沒跑了。
Szemeredi證明了弱化版本，所謂Szemeredi Theorem是說，如果A是自然數的稠密子集，那麽A中有任意長的等差數列。所謂稠密是指 \limsup_{N\to\infty}\frac{\vert A\cap[N]\vert}{N}>0 ，其中[N]指的是前N個自然數的集合。註意到質數不滿足這個性質（由質數定理），所以這個定理比G-T定理弱。
他用到的工具就是regularity lemma。
Szemeredi Regularity Lemma描述的是 完全混亂是不可能的 。隨便給一個large graph，我都可以把他分成M份使得每兩份之間非常reguler。Gowers證明了M至少是Tower Function。
透過regularity lemma可以得到graph counting lemma。我這裏以三角形為例，triangle removal lemma說的是如果一個圖中有不是很多的三角形（ \delta n^3 ），我可以透過移除相當相當少的邊（ \varepsilon n^2 ），讓圖中沒有三角形。三部圖中的三角形可以對應長度為3的等差數列，基本上用counting lemma加上一些精細的分析，可以得到Szemeredi Theorem。
G-T定理的核心是證明了relative Szemeredi theorem。因為質數集P在N中sparse，這個定理內容是說如果N的子集S滿足某種性質（初始論文要滿足兩個條件，最新的結果簡化成了一個），A在S中稠密，那麽A中有任意長的等差數列。我們可以取S為一些素因子很少的數的集合，讓質數在裏面稠密。具體的思路就是在sparse的情況下證明圖中的counting lemma。
不過可以看到這個最新的結果仍然far away from Erdos的猜想。。期待大神的突破。
正在外邊吃飯，就不放reference paper了。另外有沒有人知道為啥Tao憑借 Green-Tao Theorm拿了費爾茲但是Green沒有？他18年應該41了，徹底沒希望了。
----------------------------
補充一下 個人理解的 regularity lemma在演算法上的套用部份（根據問題標簽，回答裏還是涉及一下演算法比較好）
1. regularity lemma側重於理論上的套用（證明某些存在性），因為他給出的界是一個Tower Function（就是2的2的2的..的2次方）。這樣即使我們得出的演算法是linear的，其實裏面的常數是一個大到無法想象的數位。
2. regularity lemma中將圖分成幾部份，其中有 \varepsilon 的irregular誤差，如果消去誤差將會得到一個界是Tower的Tower。FK-regularity lemma套用價值更高（界是exp的），但是損失了很多regular的性質。
3. 只對dense graph有意義，因為sparse上的regularity是平凡的。sparse上最近也有一些不平凡的結果，詳情看大神Yufei Zhao的paper。
4. 用regularity lemma的證明大都可以找到一個不用lemma的證明可以得到更好的界（但是很難），比如最近很熱的Hypergraph container。
