大家都知道陶哲轩得了菲尔兹奖，可能也知道他得奖得结果是证明了存在任意长的素数等差数列，即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。
