欢 迎 访 问 卢 昌 海 个 人 主 页

除了自己的无知,
我什么都不懂。

-苏格拉底

 
信 息
 
 
 
已发表作品列表
站长简介 | 常见问题
版权说明 | 电子信箱
 
统 计
 
 
 
自 2008-02-01 以来
本文点击数
17,862
自 2008-02-01 以来
本站点击数
16,015,644
昨日点击数 7,768
今日点击数 1,122

什么是好数学? (中)

- 作者:Terence Tao    译者:卢昌海 -

<< 接上篇

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) 的因子控制了移位简单平均的极限行为。

站长近期发表的作品

本文的讨论期限已过, 如果您仍想讨论本文,
请在每个月前七天的 “读者周” 期间前来讨论。

>> 查阅目前尚在讨论期限内的文章 <<