大家都知道陶哲轩得了菲尔兹奖，可能也知道他得奖得结果是证明了存在任意长的素数等差数列，即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中有任意长的等差数列。这个猜想至今还open，人们甚至不能证明A中有长度为3的等差数列。。G-T定理是这个猜想的特殊情况，因为所有素数倒数和也是无穷的。至于一般情况，谁能证出来这个，估计Fields没跑了。
Szemeredi证明了弱化版本，所谓Szemeredi Theorem是说，如果A是自然数的稠密子集，那么A中有任意长的等差数列。所谓稠密是指 ，其中[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说的是如果一个图中有不是很多的三角形（ ），我可以通过移除相当相当少的边（ ），让图中没有三角形。三部图中的三角形可以对应长度为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了，彻底没希望了。
一个经济学中的应用。去年学一般均衡的时候讲到其中一个小分支，有一个叫价格图（price graph）的概念。大意就是在价格p下，如果一个个体i，他/她把自己的消费中一小部分拿给j能让j的境况严格变好，我们就说i和j是连通的。如果这张图中任意两个个体之间都有一条连通路径，那么它就是强连通的。Baldry和Ghosal证明了，如果一个经济满足一些正则条件，并且在任意价格向量下都是强连通的，这个经济中就存在瓦尔拉斯均衡(2005)。用图论来处理一般均衡问题常常是和经济体的可约性联系在一起的，所谓可约性，就是经济体不能太分裂。如果经济体可以分割成两块，其中一块完全不需要另一块的产品/禀赋，那瓦尔拉斯均衡就不会存在。具体描绘可约性实际上就是在描绘经济体的图。从1957年Rosenblatt引入这个概念开始，我们已经得到了很多种可约性，比如说McKenzie可约性，C可约性，C'可约性等等，Baldry和Ghosal用图论得到的是C可约性和C'可约性下的结果。实际上图论在理论经济学中还有很多其它应用，不过个人觉得这个是特别漂亮和重要的。
参考文献：
Baldry R, Ghosal S. Irreducible economies and strongly connected graphs[J]. Journal of Mathematical Economics, 2005, 41(8): 937-956.
