安德烈·塞迈雷迪

获奖原因

安德烈·塞迈雷迪是组合数论的巨匠。1975 年他证明了著名的塞迈雷迪定理：整数中任何具有正上密度的子集都包含任意长的算术级数。他还提出”塞迈雷迪正则引理”，成为图论与极值组合学的核心工具。2012 年阿贝尔奖表彰其对”离散数学与理论计算机科学的贡献”。

问题来龙去脉

塞迈雷迪定理回答了一个源于厄尔丢斯（Erdős）与图兰（Turán）的问题：若从整数中”密度足够大”地选取一个子集，它是否必然藏有任意长的等差数列？

设 $A\subset \mathbb{N}$，其上密度定义为 $\bar d(A)=\limsup_{N\to\infty}\frac{|A\cap\{1,\dots,N\}|}{N}.$ 塞迈雷迪定理（1975）：若 $\bar d(A)>0$，则对任意 $k\ge 3$，存在 $k$ 项算术级数 $\{a,a+d,\dots,a+(k-1)d\}\subset A$（$d>0$）。

特例 $k=3$ 由 Roth（1953）用”圆法+能量增量”证明；塞迈雷迪把证明推广到任意 $k$，用的是一条被后世称为 正则引理（regularity lemma）的组合利器。该引理说：任意足够大的图都可被分割成近乎”随机”的块（正则对），使得图的结构近似由这些块的密度矩阵决定。借助这一”粗略结构 + 拟随机”的二分，他得以在密度子集中找到长算术级数。正则引理本身后来成为图极限、极值组合与理论计算机科学（如加性组合、性质测试）的基石。

定理的第二种、更具概念冲击力的证明来自 H. Furstenberg（1977）：他用遍历论重述问题——通过”Furstenberg 对应原理”，把密度子集上的算术级数存在性，转化为保测动力系统中”多点回复”的存在性（Furstenberg 多重递归定理）。即 $\text{正密度子集含 }k\text{-项 AP} \iff \text{遍历系统的多点回复}.$ 这一对应不仅给出新证明，更开创了”遍历 Ramsey 理论”，把组合数论与动力系统永久连在一起；其后的 Host–Kra 理论与 Green–Tao 定理（素数含任意长算术级数）都沿此脉络推进。

塞迈雷迪定理的意义在于它给出了”结构强制出现”的定量门槛：只要密度不为零，规律（长算术级数）就不可避免。这与素数分布、随机性、加性组合中的”准随机性”概念深度交织，并直接启发了陶哲轩与格林关于素数 AP 的工作。阿贝尔奖对塞迈雷迪的授予，正是对”从密度到结构”这一组合学根本原理的致敬。

相关链接

阿贝尔奖 组合数学数论序列与级数