作者简介：W. T. Gowers是英国皇家学会院士，剑桥大学数学教授，因其将泛函分析与组合数学联系起来的贡献于1998年获菲尔兹奖。
1. 引言 安德烈·塞迈雷迪是数学中组合数学领域的杰出人物，特别是在极值组合论这一子领域做出了重要的贡献。稍后我将解释这些术语的意思，但是这里我们首先来介绍一下关于他非凡数学成就的一些枯燥的事实。他的最著名的成就是，在1975年给出了众所周知的埃尔德什（Paul Erdös）和 Turán提出的一个具有几十年历史的猜想的证明，现在被称为是Szemerédi定理。这个定理不仅是二十世纪数学的重要贡献之一，而且也是当前大量研究的核心所在。他给出的Szemerédi正则引理，是源于Szemerédi定理证明的一个结果，但是也已经逐渐成为极值组合论的一个重要工具。除此之外，他已经发表了200余篇论文，其中很多论文都描述了重要的进展。我将会选择其中一两个问题来讲解，但是我们应该知道的是，它们仅仅是对很多领域的数学思想有深远影响的巨大成就中的一个小的例子。 那么，什么是组合数学呢？一个可能的定义是组合数学是来研究离散结构的。那么什么是离散结构呢？“离散”这个词是跟“连续”对应的：一个结构是连续的，如果你可以从一个部分平滑地移动到另一部分；如果你不得不跳跃，就是离散的。例如，如果你在建立流体流动的模型，那么你研究的数学结构将是连续的，因为你将考虑类似于不同点的速度和压力的一些东西，并且这些是平滑地变化的。相反地，如果你在建立计算机内部东西的模型，那么你将会对 另一个离散结构，也许是组合数学中的一个最重要的结构，是图。它包含一些点，以及连接某些点的线。点称为顶点，线称为边。 你可能会认为图是连续的，因为你可以沿着它的边连续地移动。然而，连续的仅仅是图片，而不是图本身。对一个图，我们所关心的是，顶点中的哪些对是由边连接的，这可以被看作为一个简单的列表。例如，如果一个图由一个正方形的顶点和边构成，我们可以称它的顶点为 2. Szemerédi定理 并不是离散结构的所有研究都被划为组合数学。大部分题目的另一个特征是这些问题都可以以容易理解的方式叙述，至少要比许多其他领域的问题要容易得多。同样，证明经常是初等的，不是像歇洛克·福尔摩斯那样用到整个世界，而是仅仅用到某种数学。当一个数学家描述某个证明是初等的时候，这意味着证明不会用到深层次的概念，或者不依赖于之前建立的某些复杂的结果。但是我们不应该认为这意味着证明是简单的：人们可以以极其复杂的方式将一些初等的元素放在一起，而且有些“初等的”证明在数学中是困难的。相反地，一些很高级的证明，当你花足够的时间去理解它们所依赖的定理时，实际上可能是非常简单的。（当然，也确实存在一些简单的初等证明以及困难的高级证明。） Szemerédi定理是对我刚才所讲内容的一个完美的解释。它有一个吸引人的叙述，并且塞迈雷迪给出的证明既是初等的又是极其困难的。让我以解释定理的内容开始讲起。 为了讲解定理的内容，我需要等差级数（或称为算术级数）的概念。一个等差级数是指一个数的序列，每一项都增加相同的大小（称为公差）。所以序列 阿贝尔委员会关于塞迈雷迪获奖的海报 显然地，最终你是注定要输掉这个比赛的，因为我们可以给出一个既初等又极其简单的证明，如果你要保持足够长的选择，最终你将选择 为了更准确地叙述这个结果，我将需要一点代数的知识，我的意思是希望用两个字母来表示我们开始时的那两个数字。用k表示我们希望避免的级数的长度， 例如，如果你尝试去回避长为 那么怎么去证明呢？这里我不打算去告诉你，我将再次说明从技巧意义上来说那是初等的，并且我将从塞迈雷迪的原始文章中复制一个图表来尝试使你相信这也是困难的。 3. 为什么我们要关心等差级数的寻找呢？ 我在现实生活中并没有看到如下情形的重要性：一个小的整数集合包含一个长为 对这个问题，有很多回答。最显而易见的是，Szemerédi定理叙述的简单与其证明（以及所有随后发现的证明）的困难之间的对比。通常情况下，一个简单的、自然的数学陈述要么有一个简单的证明，要么有一个简单的反例。然而，有些时候人们惊奇地看到：一个形式无误的问题的解决要远比人们的期望困难得多。这些问题中的大部分被证明太难了，以至于没有人相信在与当前完全不同的新思想出现之前它们将能够被解决（ 第二个回答是，Szemerédi定理有很多数学的应用，尽管它没有什么实际的应用。其中非常著名的是Ben Green和陶哲轩的一个定理：你可以发现仅包含素数的任意长的等差级数。这个结果并不是直接源于Szemerédi定理，但是Green和陶哲轩发现了一个极其巧妙的方法将他们的问题转化为一个可以用Szemerédi定理来解决的形式。 然而，如果你坚持要求实际应用的话，那么一切并没有丢失，只要你能够接受非直接的应用而不是直接的应用。数学的一个重要的但不值得充分赞赏的方面是，你要证明的结果往往没有你证明它所用的方法更有意思。这一趋势在组合数学中尤为明显，组合数学中的一些公开问题往往越来越受关注，不是因为我们渴望知道它们的答案，而是因为它们包含了许多更一般的困难，这些困难让我们感觉到我们又真正地回到了数学。当一个这样的问题得到解决时，它的解常常包含新的数学工具的发展，这些新的工具能够在许多其他情况下得到使用。 Szemerédi定理就是这种现象的一个奇妙的解释，正如我们将要看到的。 4. Szemerédi正则引理 到目前为止我还没有讲什么是极值组合论，那么现在让我开始讲。这里有一个极值图论的问题：如果一个图有 Ben Green(左)和陶哲轩著名的数论工作用到了Szemerédi定理 这些问题自然地分为两部分。一部分是去寻找能够避免你希望避免的结构的例子，以这样的方式使得你感兴趣的量能够尽可能的大。另一部分是去证明如果问题中的量达到某个数值，那么你将不能避免你希望避免的结构。埃尔德什的一个深刻的观察，在很多情况下是解决第一部分问题的一个出奇得好的方法，即去随机地选择你的结构。例如，如果你的结构是 埃尔德什的观察诞生了随机图论，现在已经成为组合数学的一个主要的子领域。作为一个结果，组合数学家们不认为随机图是讨厌的、混乱的东西，而认为从许多方面来说都是容易理解的东西。为了更清楚地表达，我不再说随机图论是一个容易的领域：如果你问关于一个随机图的足够详细的问题，那么回答它们需要非常精密的、困难的概率估计。但是随机图在以下方面具有重要意义，随机图（几乎总）是可预言的并且效果良好。 由于这一背景，Szemerédi正则引理应该得到大家理解。在介绍正则引理之前，我们假设图被认为是没有结构的东西。最后，当你介绍一个图时，对每对顶点x和y你需要决定是否用一条边连接它们，并且你的决定没有任何限制。然而塞迈雷迪意识到，一旦你丢掉你对随机性的恐惧，你就可以对完全任意的图给出一个有用的结构描述。 在这里我不能给出这个结果的一个精确的叙述，但是大致的思想是这样的。给定任意一个图，存在一种如下的方式将它的所有顶点划分为一些集合，这些集合的数目比较小：如果你取出连接其中任意两个集合的边，那么它们看起来像是被随机选择的（事实上，尽管这个大致的思想是过于简单的，但是对这些目的它将起作用）。简言之，每个图都是由数目很少的随机图构成的。 这告诉我们，可以使用很小数目的数据来给我们的图一个好的刻画：将顶点划分成引理告诉我们的一些集合，我们只需要粗略地说每对集合之间有多少条边，并且我们知道这些边是以一种看起来随机的方式分配的。这并不能确切地告诉我们这个图是什么样子的，但是更多情形下两个随机图的差别是不重要的，因为它们都是随机的，所以它们都具有你希望一个随机图所具有的性质。 Szemerédi正则引理很快成为，并且现在仍然是极值图论的一个核心的工具，它的间接的影响，如随后的许多变形和推广，仍然非常广泛。 我许诺过要讨论正则引理的一些间接的实际应用。所以让我以一个具有明显实际重要性的人工智能问题开始，然后回到正则引理。没有人可以否认：如果有人可以设计一个能够从经验中学习的计算机程序，那么这个程序将有无数的实际应用。试图去做这件事的人工智能的一个分支称为机器学习。一个被称为 PAC学习的著名的抽象模型是由Leslie Valiant提出的，是研究机器学习的一种好的结构。［字母 PAC代表“probably approximately correct”（概率近似正确）］。这引出了一个被归入一般性能测试的纯数学的问题。粗略地讲，你有一个结构，你希望去证明它要么有某个性质，要么它可能非常类似于一个不具有这个性质的结构。例如，给你一个图，让你去证明它包含一个三角形，或者它跟一个不包含三角形的图只有略微的不同。从机器学习的角度来看，我们感兴趣的是这些通常可以被格外快地处理：程序会执行很小数目的一些简单的测试，然后形成一个可靠的假设（也就是，一个概率近似正确的假设）。允许我们去证明这件事的工具是什么呢？那就是Szemerédi正则引理。 5. 排序 塞迈雷迪也因成为Miklos Ajtai，Janos Komlos和Endre Szemerédi（简称AKS）三人之一而著名。我将论述他们工作的两个最著名的部分，但是我必须强调这只是一个小样本。当我说“最著名”的时候，我的意思是类似于高速公路上的光线：它们非常的昂贵，但是它们也非常的多。 计算机科学中的一个古老的话题是排序算法。给你一个对象的集合，并且它们中的任意两个都是可以比较的，你的任务是用尽可能少的比较来对它们进行排序。为了研究这个问题，你可以想象这是岩石的一个集合，你要按照它们的重量进行排序，做这件事你所需要的是一副天平，它能够告诉你任意给定的两块岩石哪块更重。你每使用一次天平需要支付一美元，并且你希望花费尽可能少的钱。 一个漂亮的论证说明如果你有 的对数大概是 在1945年底，塞迈雷迪仅仅五岁，因此，排序算法这一课题早在塞迈雷迪研究数学之前就已经完全出现了。 让我们回到我们希望按照重量排序的岩石问题，并且将这一游戏做轻微的变化。这一次你将拥有尽可能多的天平，这样你就可以同时进行多次比较。所以你要做的是组织一系列的称重，每次称重中你可以对尽可能多对的岩石称重。一个明显的限制是同一块岩石不能放在不同的天平上，所以在每次称重中每块岩石至多被比较一次。你现在的目标是使用最少的称重次数对岩石进行排序。 因为我们已经知道大概需要 这里我不能完全的描述他们的方法，但是可以给出这一方法的某些想法。假设你以1000块岩石开始，并且将它们分成两组，每组500块。（在这一步，你绝对没有任何比较两块岩石重量的思路。）你要做的事情是将一组中的岩石跟另一组中的岩石进行配对，同时做500次比较，然后将较轻的那些岩石放到标记为 图论既困难又有实际应用 根据埃尔德什的方法，我们可能认为将 如果我们保持将 如果L中的所有岩石都比H中的所有岩石都轻，那么我只需在每一组中重复这一程序，并且大约 关于这个算法的最后一点：我上面所描述的算法是一个随机算法，因为所有的对都是随机对。然而，存在一类非常有用的被称为扩展图的图，它可作为随机图的替代来使用。这里，你可以用扩展图的边来决定如何去给岩石配对，而不是靠投掷硬币的办法，并且这时算法仍然是起作用的。这就是去随机化（derandomization）的一个例子，这是理论计算机科学的一个基本思想，它意味着算法可以以一种完全确定的方式运行。 6. Ramsey数R(3,k) 你所期望的图中的一个三角形是：三个顶点彼此相连。一个独立集是一个顶点的集合，他们彼此没有边相连。这里给出一个简单的论述来证明，一个具有 论述如下。令 现在我们设想来尝试寻找一个大的独立集。我们做这件事的一种方法是去寻找一个顶点的序列 上面的讨论（根据数学研究的标准）是非常简单的，但是确定是否可以改进它被证明是非常困难的。这就是AKS解决的问题：他们证明 为了证明他们的结果，AKS可以比上面讲到的简单论述做得更好。极其粗略地，他们用的是同样的讨论，但是用一种更谨慎的方式处理的。回忆一下基本的想法是选择顶点 现在如果我们在程序的任何一步中，发现了一个顶点，它的邻点数目远小于 上面我所暗示的讨论并不是 AKS给出的原始证明，但是描述起来比较容易。他们早期的讨论也是非常重要的，因为它是称为半随机方法的一个较早的例子，这里我将不再讨论，但是我想说这是另一种具有很多应用的技巧。 7. 结论 一些数学家因为一个或者两个定理而著名，另一些数学家因为巨大的、重要的一些一流结果而著名。偶尔，也会有数学家因为两者而著名。没有Szemerédi定理和Szemerédi正则引理的讨论，塞迈雷迪的工作将不会完整。然而，对塞迈雷迪来说，他的工作远远多于这两个定理，他已经发表了200余篇论文，正如我在开始时提到的，71岁的他并没有任何慢下来的迹象。他应该得到阿贝尔奖，这是极其恰当的。即使我仅仅了解他工作的一些表面情况，我还是希望通过这个小样本描述，至少能够让大家认识到推荐他获奖的一些理由。
