在这些猜想上的第一个进展是一系列反例，最终汇集为 Behrend 对不存在长度 3 算术序列的适度稀疏集（对于任意给定的 ε，这个集合在 {1,...,N} 中的密度渐近地大于 N-ε ）的优美构造。这一构造排除了 Erdös-Turán 猜想中最具野心的部分（它猜测多项稀疏集包含大量的序列），而且还排除了很大一类解决这些问题的方法（比如那些基于 Cauchy-Schwarz 或 Hölder 之类不等式的方法）。这些例子虽不能完全解决问题，但它们表明 Erdös-Turán 猜想若成立，将需要一个非平凡的（从而想必是有趣的）证明。

　　下一个主要进展来自于 Roth，他以一种优美的方式运用 Hardy-Littlewood 的圆法[8]及一种新的方法（密度增量论证），确立了 Roth 定理：每一个密度为正的整数集都包含无穷多个长度 3 序列。接下去很自然的就是试图将 Roth 的方法推广到更长的序列。Roth 和许多其他人在这方面花费了好几年的时间，却没能取得完全的成功。困难的起因直到很久之后才由于 Gowers 的工作而得到显现。问题的解决则依靠了 Endré Szemerédi 的惊人才华，他重新回到了纯粹的组合方法上（特别是，把密度增量论证推进到了一个令人瞩目的技术复杂度上），将 Roth 的结果首先推广到长度 4 [9]，然后到任意长度，从而确立了他的著名定理。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，他的数学品位使他试图寻找一种本质上不同的（高度非初等的[10]）证明，他所依据的是组合数论与各态历经理论之间富有远见的类比，这一类比很快被他表述为很有用的 Furstenberg 对应原理。从这个原理[11]人们可以很容易地得出结论：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 定理的一个非常有力及抽象的推广）。这些通过无穷各态历经理论技巧所获得的结果中的许多，人们至今也不知道是否存在“初等”证明，这证实了这种方法的力量。不仅如此，作为这些努力的一个有价值的副产品，人们还获得了对保测体系结构分类的深刻得多的理解。特别是，人们意识到对于许多类型的回归问题，一个任意体系的渐进回归性质几乎完全由该体系的一个特殊因子所控制，这个因子被称为该体系的（最小）特征因子[12]。确定各类回归中这一特征因子的精确性质于是便成为了研究的焦点，因为这将导致有关极限行为的更精确的信息（特别是，它将显示与多重回归有关的某些渐进表达式实际上收敛于一个极限，这在 Furstenberg 的原始论证中是悬而未决的）。Furstenberg 和 Weiss 的反例，及 Conze 和 Lesigne 的结果，逐渐导致一个结论，即这些特征因子应该由一个非常特殊的（代数型的）保测体系，即与幂零群（nilpotent group）相联系的零系统（nilsystem），来描述。这些结论的集大成者是对这些因子给予精确及严格描述的技术上引人注目的 Host 和 Kra 的论文（及随后的 Ziegler 的论文），它在得到其它一些结果的同时解决了刚才提到的渐进多重回归平均的收敛性问题。这些特征因子所扮演的核心角色相当充分地表明了存在于（由零系统所表示的）结构与（由某些技术型的“混合”性质所刻划的）随机性之间的二向性（dichotomy），以及一种深刻的见解，即Szemerédi定理的力量实际上是源于这一二向性。Host-Kra 分析的另一个值得一提的特点是平均概念在“立方体”或“超平行体”中令人瞩目的出现，出于一些原因，它比与算术序列有关的多重回归平均更易于分析。（译者注：1. Hales-Jewett 定理的大致内容是：如果用 m 种颜色来给一个边长为 n 的多维点阵着色，那么只要点阵的维数足够高，就必定存在同色的长度为 n 的行、列、对角线等。2. “dichotomy”在数学与逻辑中通常译为二分法，不过在本文中似以译成“二向性”或“二重性”为佳，因为“二分法”这一译名过于强调两种性质之间的区分而非联系。）