什么是好数学？ (中)2. 个例研究： Szemerédi 定理
现在我们从一般转向特殊， 通过考察 Szemerédi 定理 - 那个声称任何具有正 (上) 密度的整数子集必定包含任意长度算术序列的漂亮而著名的结果 - 的内容及历史来说明上段所述的现象。 这里我将避免所有的技术细节。 [译者注： 1. 整数子集 A 的 “上” 密度， 指的是 lim supN→∞ |A∩[-N,N]|/2N， 其中序列 aN 的上极限 lim supN→∞ aN 定义为 AN=supk≥N ak 的极限。 2. 算术序列 (在后文中有时被简称为序列) 指的是由整数组成的等差序列， 序列中的整数个数称为算术序列的长度。]
这个故事有许多个自然的切入点。 我将从 Ramsey 定理 - 任何有限着色的足够大的完全图必定包含大的单色完全子图 (比如任意六人中必有三人要么彼此相识， 要么彼此陌生， 假定 “相识” 是一个有良好定义的对称关系) - 开始。 这个很容易证明 (无需用到比迭代鸽笼原理更多的东西) 的结果代表了一种新现象的发现， 并且开辟了一系列新的数学结果： Ramsey 型定理。 这些定理中的每一个都是数学上一个新近洞察的观点 “完全无序是不可能的” 的不同表述。 [译者注： 1. 完全图指的是任意两个顶点间都有边相连的图。 2. 鸽笼原理也叫 Dirichlet 抽屉原理， 它最简单的版本指的是将 n>k 件东西放入 k 个容器中， 其中至少有一个容器含有多于一件东西。]
最早的 Ramsey 型定理之一 (事实上比 Ramsey 定理还早了几年) 是 van der Waerden 定理： 给定整数集的一个有限着色， 其中必有一个单色类包含任意长度算术序列。 van der Waerden 的高度递归的证明非常优美， 但有一个缺点， 那就是它给出的出现第一个给定长度算术序列的定量下界弱得出奇。 事实上， 这个下界含有序列长度和着色种数的 Ackermann 函数。 Erdös 和 Turán 所具有的良好数学品位， 以及希望在 (当时还是猜想的) 素数是否包含任意长度算术序列这一问题上获取进展的企图， 使他们对这一定量问题做了进一步的探究[注七]。 他们推进了一些很强的猜想， 其中一个成为了 Szemerédi 定理； 另一个则是一个漂亮 (但尚未证明) 的更强的命题， 它声称任何一个倒数和非绝对可和的正整数集都包含任意长度算术序列。 [译者注： 1. 译文 “定量下界” 所对应的原文是比较笼统的 “quantitative bounds” (即未指明是上界还是下界)。 2. Ackermann 函数 A(m,n) (其中 m、 n 为非负整数) 的递归定义是： A(0,n)=n+1； A(m,0)=A(m-1,1)； A(m,n)=A(m-1,A(m,n-1))， 它的增长速度快于任何初等递归函数 (包括指数函数)。 3. Tao 对 Erdös 和 Turán 所提出的 “更强的命题” 的表述略显冗余， 其中 “非绝对可和” 可简化为 “非可和” 或 “发散” (因为他所讨论的是正整数集)。]
在这些猜想上的第一个进展是一系列反例， 最终汇集为 Behrend 对不存在长度 3 算术序列的适度稀疏集 (对于任意给定的 ε， 这个集合在 {1, ..., N} 中的密度渐近地大于 N-ε) 的优美构造。 这一构造排除了 Erdös-Turán 猜想中最具野心的部分 (它猜测多项稀疏集包含大量的序列)， 而且还排除了很大一类解决这些问题的方法 (比如那些基于 Cauchy-Schwarz 或 Hölder 之类不等式的方法)。 这些例子虽不能完全解决问题， 但它们表明 Erdös-Turán 猜想若成立， 将需要一个非平凡的 (从而想必是有趣的) 证明。
下一个主要进展来自于 Roth， 他以一种优美的方式运用 Hardy-Littlewood 的圆法[注八]及一种新的方法 (密度增量论证)， 确立了 Roth 定理： 每一个密度为正的整数集都包含无穷多个长度 3 序列。 接下去很自然的就是试图将 Roth 的方法推广到更长的序列。 Roth 和许多其他人在这方面花费了好几年的时间， 却没能取得完全的成功。 困难的起因直到很久之后才由于 Gowers 的工作而得到显现。 问题的解决则依靠了 Endré Szemerédi 的惊人才华， 他重新回到了纯粹的组合方法上 (特别是， 把密度增量论证推进到了一个令人瞩目的技术复杂度上)， 将 Roth 的结果首先推广到长度 4[注九]， 然后到任意长度， 从而确立了他的著名定理。 Szemerédi 的证明是一项技术绝活， 它引进了许多新想法和新技巧， 其中最重要的一个是引进了看待极端复杂图的新方法， 即通过有界复杂模型来取近似。 这一结果， 即著名的 Szemerédi 正规性引理 (Szemerédi regularity lemma)， 在很多方面都引人注目。 如上所述， 它给出了有关复杂图结构的全新洞察 (在现代术语中， 这被视为那些图的结构定理和紧致定理)； 它提供了一种将在本故事后面部分变得至关重要的新的证明方法 [能量增量方法 (energy increment method)]； 它还导致了从图论到性质检验到加性组合学的数量多得难以置信的意外应用。 可惜的是， 正规性引理的完整故事太过冗长， 无法在这里加以叙述。 [译者注： 1. 密度增量论证 (density increment argument) 的含义在 下篇 中将有所提及。 2. 性质检验 (property testing) 是图论及组合学中一类相当困难的判定问题。 3. 加性组合学 (additive combinatorics) 是一个旨在研究集合中加性结构的数学分支。]
Szemerédi 的成就无疑是本故事的一个重点， 但它绝不是故事的终结。 Szemerédi 对其定理的证明虽然初等， 却极为复杂、 不易理解。 并且它也没能完全解决启发 Erdös 和 Turán 进行研究的原始问题， 因为这一证明本身在两个关键地方用到了 van der Waerden 定理， 从而无法改进该定理中的定量下界。 接下来是 Furstenberg， 他的数学品位使他试图寻找一种本质上不同的 (高度非初等的[注十]) 证明， 他所依据的是组合数论与各态历经理论之间富有远见的类比， 这一类比很快被他表述为很有用的 Furstenberg 对应原理。 从这个原理[注十一]人们可以很容易地得出结论： Szemerédi 定理等价于保测体系中的多重回归定理， 由此可以很自然地直接运用各态历经理论中的方法， 特别是通过考察这种体系中各种可能的分类及结构分解 (比如各态历经分解)， 来证明这一定理 (现在被称为 Furstenberg 回归定理)。 事实上， Furstenberg 很快建立了 Furstenberg 结构定理， 这一定理把所有保测体系都描述为一个平凡体系的一系列紧致拓展 (compact extension) 的弱混合拓展 (weakly mixing extension)。 在这一定理及几个附加论证 (包括 van der Waerden 论证的一个变种) 的基础上可以确立多重回归定理， 从而给出 Szemerédi 定理的一个新的证明。 同样值得一提的是 Furstenberg 还撰写了有关这一领域及相关课题的优秀著作， 在对这一领域的成长及发展做出重大贡献的同时对基础理论作了系统的形式化。
Furstenberg 与其合作者随后意识到这一新方法所具有的强劲潜力可以用来确立许多类型的回归定理， 后者 (通过对应原理) 又可以产生一些高度非平凡的组合定理。 顺着这一思路， Furstenberg、 Katznelson 及其他人获得了 Szemerédi 定理的许多变种和推广， 比如高维空间的变种， 他们甚至确立了 Hales-Jewett 定理的密度版本 (这是 van der Waerden 定理的一个非常有力及抽象的推广)。 这些通过无穷各态历经理论技巧所获得的结果中的许多， 人们至今也不知道是否存在 “初等” 证明， 这证实了这种方法的力量。 不仅如此， 作为这些努力的一个有价值的副产品， 人们还获得了对保测体系结构分类的深刻得多的理解。 特别是， 人们意识到对于许多类型的回归问题， 一个任意体系的渐进回归性质几乎完全由该体系的一个特殊因子所控制， 这个因子被称为该体系的 (最小) 特征因子[注十二]。 确定各类回归中这一特征因子的精确性质于是便成为了研究的焦点， 因为这将导致有关极限行为的更精确的信息 (特别是， 它将显示与多重回归有关的某些渐进表达式实际上收敛于一个极限， 这在 Furstenberg 的原始论证中是悬而未决的)。 Furstenberg 和 Weiss 的反例， 及 Conze 和 Lesigne 的结果， 逐渐导致一个结论， 即这些特征因子应该由一个非常特殊的 (代数型的) 保测体系， 即与幂零群 (nilpotent group) 相联系的零系统 (nilsystem)， 来描述。 这些结论的集大成者是对这些因子给予精确及严格描述的技术上引人注目的 Host 和 Kra 的论文 (及随后的 Ziegler 的论文)， 它在得到其它一些结果的同时解决了刚才提到的渐进多重回归平均的收敛性问题。 这些特征因子所扮演的核心角色相当充分地表明了存在于 (由零系统所表示的) 结构与 (由某些技术型的 “混合” 性质所刻划的) 随机性之间的二向性 (dichotomy)， 以及一种深刻的见解， 即 Szemerédi 定理的力量实际上是源于这一二向性。 Host-Kra 分析的另一个值得一提的特点是平均概念在 “立方体” 或 “超平行体” 中令人瞩目的出现， 出于一些原因， 它比与算术序列有关的多重回归平均更易于分析。 [译者注： 1. Hales-Jewett 定理的大致内容是： 如果用 m 种颜色来给一个边长为 n 的多维点阵着色， 那么只要点阵的维数足够高， 就必定存在同色的长度为 n 的行、 列、 对角线等。 2. “dichotomy” 在数学与逻辑中通常译为二分法， 不过在本文中似以译成 “二向性” 或 “二重性” 为佳， 因为 “二分法” 这一译名过于强调两种性质之间的区分而非联系。]
>> 接下篇
注释

1. Erdös 也研究了 Ramsey 原始定理中的定量下界， 由此导致的结果中包括了对在组合学中极其重要的概率方法的确立， 不过这本身就是一个很长的故事， 我们没有足够的篇幅在这里讨论。
2. 同样， 圆法的历史也是一段我们无法细述的精彩故事。 不过只要提这样一点就足够了， 那便是用现代语言来说， 这一方法是 “Fourier 分析是解决加性组合学问题的重要工具” 这一现代标准见解的一部分。
3. 在这之后， Roth 很快就将 Szemerédi 的想法与他自己的 Fourier 分析方法组合在一起， 给出了针对长度 4 序列的 Szemerédi 定理的混合证明。
4. 比方说， 某些版本的 Furstenberg 论证严重依赖于选择公理， 尽管将之修改为不依赖选择公理也是可能的。
5. 对拓扑动力系统也存在类似的对应原理将 van der Waerden 定理与多重回归定理等价起来。 这引出了有关拓扑动力学的迷人故事。
6. 这方面的早期例子是 von Neumann 的平均各态历经定理， 在其中移位不变函数 (shift-invariant function) 的因子控制了移位简单平均的极限行为。

什么是好数学？ (下)   与这些各态历经理论的进展相平行， 其他数学家则在寻找用别的方式来理解、 重新证明及改进 Szemerédi 定理。 Ruzsa 和 Szemerédi 取得了一个重要的概念突破， 他们用上面提到的 Szemerédi 正规性引理确立了一些图论中的结果， 包括现在被称为三角消除引理 (triangle removal lemma) 的引理， 其大致内容是说一个包含少数三角形的图中的三角形可以通过删除数目少得令人惊讶的边而消除。 他们随后发现前面提到的 Behrend 例子对这一引理的定量下界给出了某种极限， 特别是它排除了许多类型的初等方法 (因为那些方法通常给出多项式型的下界)， 事实上迄今所知消除引理的所有证明都是通过正规性引理的某些变种。 将这一联系反过来应用， 人们发现其实三角消除引理蕴含了 Roth 关于长度 3 序列的定理。 这一发现首次开启了通过纯图论技巧证明 Szemerédi 型定理的可能性， 从而抛弃了问题中几乎所有的加性结构 (注意各态历经方法仍然保留了这一结构， 以作用在系统上的移位算符的面目而出现； Szemerédi 的原始证明也只是部分是图论的， 因为它在许多不同环节用到了序列的加性结构)。 不过， 一段时间之后人们才意识到图论方法与先于它出现的 Fourier 分析方法在很大程度上局限于检测象三角形或长度 3 序列那样的 “低复杂度” 结构， 检测更长的序列将需要复杂得多的超图理论。 特别是， 这启示了 (由 Frankl 和 Rödl 率先提出的) 一个计划， 意在寻找超图理论中正规性引理的类比， 这将足以产生象 Szemerédi 定理 (及其变种和推广) 那样的推论。 这被证明是一项复杂得令人吃惊的工作， 尤其是要仔细安排这种正规化中参数的等级[注十三]， 使之以正确的顺序相互主导。 事实上， 能够从中推出 Szemerédi 定理的正规性引理及与之相伴的记数引理 (counting lemma) 的最终证明直到最近才出现。 Gowers 的很有教益的反例也是值得一提的， 它表明原始的正规性引理中的定量下界必须至少是塔状指数形式 (tower-exponential)， 从而再次显示这一引理非同寻常的性质 (和力量)。 [译者注： 1. 三角形消除引理中的 “少得令人惊讶” 是相对于三角形的数目而言的， 它指的是用删除 O(n2) 条边来消除 O(n3) 个三角形。 2. 超图 (hypergraph) 是普通图的推广， 在其中边可以连接两个以上的顶点 (类似于多元关系)。]
       自 Roth 之后未曾有实质进展的 Fourier 分析方法最终由 Gowers 做了重新考察。 和其它方法一样， Fourier 分析方法首先确立了整数集中的二向性， 即他们在某种意义上要么是有结构的， 要么是伪随机的。 这里的结构这一概念是由 Roth 提出的： 有结构的集合在中等长度算术序列上有一个密度增量， 但有关伪随机或 “均匀性” 的正确概念却没那么清楚。 Gowers 提出了一个反例 (事实上这一反例与前面提到的 Host 与 Kra 的例子有着密切的关系)， 表明以 Fourier 分析为基础的伪随机概念对于控制长度 4 或更长的序列是不够的， 他随后引进了一个满足需要的不同的均匀性概念 (与 Host 和 Kra 的立方体平均有很密切的关系， 与某些超图正规性的概念也有关系)。 剩下的工作就是为二向性确立一个定量且严格的形式。 这却是一项困难得出人意料的工作 (主要是由于这一方法中 Fourier 变换的效用有限)， 并且在许多方面与 Host-Kra 及 Ziegler 试图将特征因子赋予零系统代数结构的努力相类似。 但是， 通过将 Fourier 分析工具与诸如 Freiman 定理和 Balog-Szemerédi 定理等加性组合学的主要结果， 及一些新的组合与概率方法结合在一起， Gowers 用令人瞩目的高超技巧成功地完成了这一工作， 他并且得到了有关 Szemerédi 定理和 van der Waerden 定理的非常强的定量下界[注十四]。 [译者注： Freiman 定理是一个有关具有小和集的整数集中算术序列性质的定理 (一个整数集 A 的和集 A+A 是由该整数集本身及其中任意两个数的和组成的集合， 小和集则是指 |A+A|<c|A| 的情形， 其中 c 为常数)。]
       总结起来， 人们给出了 Szemerédi 定理的四种平行的证明； 一种是通过直接的组合方法， 一种是通过各态历经理论， 一种是通过超图理论， 还有一种是通过 Fourier 分析及加性组合学。 即便有了这么多的证明， 我们依然觉得有关自己对这一结果的理解还不完全。 比方说， 这些方法中没有一种强到能够检测素数中的序列， 这主要是由于素数序列的稀疏性 (不过， Fourier 方法， 或更确切地说 Hardy-Littlewood-Vinogradov 圆法， 可以用来证明素数中存在无穷多长度 3 序列， 并且在付出很大努力后可以部分地描述长度 4 序列)。 但是通过调和分析中的限制理论 (这是另一个我们将不在这里讨论的引人入胜的故事)， Green 能够将素数 “当成” 稠密来处理， 由此得到了一个有关素数稠密子集的类似于 Roth 定理的结果。 这为相对 Szemerédi 定理 (relative Szemerédi theorem) 开启了可能性， 使人们能检测整数集以外的其它集合， 比如素数， 的稠密子集中的算术序列。 事实上， 一个与相当稀疏的随机集合的稠密子集有关的相对 Roth 定理 (relative Roth theorem) 的原型已经出现在了图论文献中。
            在与 Ben Green 的合作[注十五]中， 我们开始试图将 Gowers 的 Fourier 分析及组合论证方法相对化到诸如稀疏随机集合或伪随机集合的稠密子集这样的情形中。 经过许多努力 (部分地受到超图理论的启示， 它已被很好地用来计算稀疏集合中的结构； 也部分地受到 Green 正规性引理的启示， 它将图论中的 “算术正规性引理” 转用到了加性理论中)， 我们逐渐能够 (在一项尚未发表的工作中) 检测这类集合中的长度 4 序列。 这时候， 我们意识到了我们所用的正规性引理与 Host-kra 有关特征因子的构造之间的相似性。 通过对这些构造的置换[注十六] (特别依赖于立方体平均)， 我们可以确立一个令人满意的相对 Szemerédi 定理， 它依赖于一个特定的转化原理 (transference principle)， 粗略地说， 该原理断言稀疏伪随机集合的稠密子集的行为 “就好比” 它们在初始集合中就是稠密的。 为了将这一定理应用于素数， 我们需要将素数包裹在一个适当的伪随机集合 (或者更确切地说， 伪随机测度) 中。 对我们来说很偶然的是， Goldston 和 Yildirim 最近有关素数隙的突破[注十七][注十八]几乎恰好构造了我们所需要的东西， 使我们最终确立了早年的猜想， 即素数集包含任意长度的算术序列。 [译者注： 1. 这里提到的 Tao 与 Green 合作所得的结果 “素数集包含任意长度的算术序列” 被称为 Green-Tao 定理。 2. 这里提到的 Goldston 和 Yildirim 的工作， 及原文 [注十七] 提到的故事可参阅拙作 孪生素数猜想 及该文末尾的补注。]
         故事到这里仍未结束， 而是继续沿几个方向发展着。 一方面转化原理现在已经有了一些进一步的应用， 比如获得高斯素数中的组团 (constellation) 或有理素数中的多项序列。 另一个很有前途的研究方向是 Fourier 分析、 超图理论及各态历经方法的彼此汇聚， 比如发展图论与超图理论的无穷版本 (它在其它数学领域， 如性质检验， 中也有应用)， 或各态历经理论的有限版本。 第三个方向是使控制各态历经情形下的回归的零系统也能控制算术序列的各种有限平均。 特别是， Green 和我正在积极地计算素数及由零系统 (通过 Vinogradov 方法) 产生的序列之间的关联， 以便确立能够在素数中找到的各种结构的精确渐进形式。 最后， 但并非最不重要的是最初的 Erd&ouml;s-Turán 猜想， 它在所有这些进展之后仍未得到解决， 不过现在 Bourgain 已经取得了一些非常有希望的进展， 这应该能引导出进一步的发展。 [译者注： 1. 高斯素数 (Gaussian prime) 是素数概念在高斯整数集 (即形如 m+ni 的复数组成的集合， 其中 m、 n 均为整数) 中的推广。 2. 有理素数 (rational prime) 是普通素数在高斯整数集中的称谓。]
3. 结论
      如我们在上述个例研究中可以看到的， 好数学的最佳例子不仅满足本文开头所列举的数学品质判据中的一项或多项， 更重要的， 它是一个更宏大的数学故事的一部分， 那个故事的展开将产生许多不同类型的进一步的好数学。 实际上， 人们可以将整个数学领域的历史看成是主要由少数几个这类好故事随时间的演化及相互影响所产生的。 因此我的结论是， 好数学不仅仅是用前面列举的一个或几个 “局部” 品质来衡量的 (尽管那些品质无疑是重要且值得追求与争论的)， 还要依赖于它如何通过继承以前的成果或鼓励后续发展来与其它好数学相匹配这样更 “全局” 的问题。 当然， 如果不凭借后见之利， 要确切地预言什么样的数学会具有这种品质是困难的。 不过实际上似乎存在某种无法定义的感觉， 使我们能感觉到某项数学成果 “触及了什么东西”， 是一个有待进一步探索的更大谜团的一部分。 在我看来， 追求这种对发展潜力的难以言状的保障， 对数学进展来说起码是与前面列举的更具体更显然的数学品质同等重要的。 因此我相信， 好数学并不是单纯的解题、 构筑理论、 对论证进行简化、 强化、 明晰化、 使论证更优美、 更严格， 尽管这些无疑都是很好的目标。 在完成所有这些任务 (及争论一个给定领域中哪一个应该有较高的优先权) 的同时， 我们应该关注我们的结果所可能从属的任何更大的范围， 因为那很可能会对我们的结果、 相应的领域， 乃至整个数学产生最大的长期利益。
4. 鸣谢
      感谢 Laura Kim 阅读并评论本文的早期文稿， 以及 Gil Kalai 的许多深思熟虑的评论与建议。
注释

1.     这一等级看来与 Furstenberg 在其使保测体系 “正规化” 的类似探索中所遇到的一系列拓展有关， 尽管我们现在对其确切关联还了解得很少。
2.     同样值得一提的是 Shelah 有关 van der Waerden 定理的杰出的创造性证明， 它曾经保持着有关这一定理的最佳常数的纪录。
3.    顺便说一下， 我最初被这些问题所吸引是因为它们与另一个重大的数学故事， 我们在此处没有篇幅讨论的 Kakeya 猜想， 之间的联系。 它们与前面提到的有关限制理论的故事之间的关系则是多少有点出人意料的。
4.    出于几个原因， 这里有一点技巧性。 最明显的是各态历经构造本质上是无穷的， 但为了处理素数却必须在有限的情况下使用。 幸运的是， 我曾经尝试过将各态历经方法有限化以便应用于 Szemerédi 定理。 虽然那一尝试在当时并不完全， 但后来发现它足以对我们研究素数提供帮助。
5.    在我们写论文的时候， 我们所采用的构造来自于 Goldston 和 Y?ld?r?m 的一篇文章， 那篇文章曾因为一个与我们工作无关的缺陷而被他们收回， 后来他们通过一些聪明的新想法弥补了缺陷。 这对我们前面提到的一个观点， 即一项数学工作不一定要在所有细节上都绝对正确才能对未来的 (严密) 工作有所助益， 是一种支持。
6.    有关素数隙的故事也是一个我们无法在这里讲述的有趣的故事。

                                                                                                                                        二零零七年三月十一日译于纽约
                                                                                                                                                              http://www.changhai.org/
附录： Alain Connes 的评论
Good Mathematics?
              ... ... 很难评论 Tao 的这篇文章， 第二部分有关 Szemeredi 定理的个例不错且很有趣， 但第一部分有那种艺术家试图通过一系列标准来定义美的痛苦意味。 这种类型的判断是如此主观， 我很真切地感到除了显而易见的傲慢自大外没学到任何东西 ... ... [译者注： Connes 提到的这种 “傲慢自大” Tao 自己也提到了， 并试图予以说明 (本译文 上篇 最后两段)， 但看来 “Resistance is Fertile”。 还是 Hardy 看得比较透彻， 他说： “对一位职业数学家来说， 发觉自己在 writing about mathematics 是一种郁闷的感觉”， Hardy 自己虽然也做了这件 “郁闷” 的事， 但那时他已经 63 岁， 比 Tao 大了一倍。]
Alain Connes 发表于 "Noncommutative Geometry" (2007-02-19)