Tao–Vu · 加性组合学 · 第 12 章 和集中的长等差数列
12.6 进一步的应用Further applications
本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。
文本说明：所提供的原文 PDF 只包含本节开头部分（节标题、引言段落，以及一条引理的开头——它引入了记号 \(\mathbb{Z}_n^\times\) 后即被截断）。下文忠实翻译这部分现有原文，并围绕它把所需的背景概念（推论 12.13、互素剩余类 \(\mathbb{Z}_n^\times\)）讲清楚；凡涉及原文之外的具体定理陈述，本页不予杜撰。
本节目标第 12 章前面已经反复证明了一类核心结论：只要一个数集足够“稠密”，它的和集里就一定藏着一条很长的真等差数列。本节（12.6）要做的，是把这件“抽象工具”拿去解决几个具体的小问题——也就是“进一步的应用”。开头先准备一个关于与 \(n\) 互素的剩余类的小引理，作为后续应用的垫脚石。
引言
在本节中，我们给出推论 12.13 的几个简短应用，这些应用取自文献 [380]。关于定理 12.2 的若干应用，我们请读者参阅 [308, 309] 及其中所引的文献。
下面这条简单的引理会很有用。记 \(\mathbb{Z}_n^\times\) 为 \(\mathbb{Z}_n\) 中与 \(n\) 互素的剩余类。
（原文 PDF 在此处中断。以下为本页对上述概念的讲解，帮助理解这一引理的出发点。）
讲解一：被反复使用的工具——推论 12.13 在说什么
回顾·和集与真等差数列
- 给定整数集合 \(A\)，它的 \(h\) 重和集记作 \(hA=\{a_1+a_2+\cdots+a_h: a_i\in A\}\)；最常见的是 \(2A=A+A\)。
- 一条等差数列（arithmetic progression, AP）形如 \(a,\,a+d,\,a+2d,\dots,a+(k-1)d\)，其中 \(d>0\) 称为公差（step），\(k\) 称为长度。
- 称它是真（proper）等差数列，意思是这 \(k\) 个数互不相同——在整数里这是自动满足的，但在 \(\mathbb{Z}_n\)（模 \(n\) 的世界）里就不一定，必须特别声明。
第 12 章一连串定理（其中包括被本节引用的推论 12.13）的共同主题可以一句话概括：
本章主题（直觉版）如果 \(A\) 是区间 \([1,N]\) 里一个足够稠密的集合（元素个数 \(|A|\) 占了 \(N\) 的相当一部分），那么它的和集 \(hA\)（哪怕只是 \(A+A\)）里必定包含一条很长的真等差数列。集合越稠密，保证的等差数列就越长。
这正是“为什么 12.6 节能拿它去做应用”的原因：很多看似与等差数列无关的问题，最后都能归约成“某个和集是否含有长等差数列”。一旦归约成功，直接套用推论 12.13 即可。
例·为什么“稠密 ⇒ 和集有长 AP”不奇怪
取最稠密的情形 \(A=\{1,2,3,\dots,N\}\)（区间本身）。
- 它的和集 \(A+A=\{2,3,\dots,2N\}\)，本身就是一条公差 \(d=1\)、长度 \(2N-1\) 的等差数列。
- 现在把 \(A\) 挖掉一些元素、让它稀疏一点，和集会出现一些“窟窿”，但只要挖得不太狠（\(|A|\) 仍然很大），窟窿填不满整段，总能在和集里找到一条没被窟窿打断的长等差数列。
- 推论 12.13 做的，就是把“挖得不太狠”量化成一个关于 \(|A|\) 与 \(N\) 的精确条件，并给出能保证的等差数列长度。
讲解二：互素剩余类 \(\mathbb{Z}_n^\times\)
引言之后，原文宣布“下面这条简单的引理会很有用”，并立刻引入了记号 \(\mathbb{Z}_n^\times\)。这个对象在数论与加性组合中无处不在，我们把它彻底讲清楚。
定义·模 \(n\) 的剩余类与 \(\mathbb{Z}_n^\times\)
- \(\mathbb{Z}_n=\{0,1,2,\dots,n-1\}\) 是“模 \(n\) 的世界”：所有整数按除以 \(n\) 的余数归类，得到 \(n\) 个剩余类。
- \(\mathbb{Z}_n^\times\) 取出其中那些与 \(n\) 互素（最大公约数为 \(1\)）的剩余类： \[\mathbb{Z}_n^\times=\{\,a\in\mathbb{Z}_n:\gcd(a,n)=1\,\}.\]
- 它的元素个数恰为欧拉函数 \(\varphi(n)\)，即 \(|\mathbb{Z}_n^\times|=\varphi(n)\)。
例·算出 \(\mathbb{Z}_{12}^\times\)
取 \(n=12\)。逐个检查 \(0\) 到 \(11\) 与 \(12\) 是否互素：
- \(\gcd(1,12)=1\) ✔；\(\gcd(5,12)=1\) ✔；\(\gcd(7,12)=1\) ✔；\(\gcd(11,12)=1\) ✔。
- 其余的都与 \(12\) 有公因子：偶数 \(2,4,6,8,10\)（含公因子 \(2\)）、\(3,9\)（含 \(3\)）、\(0\)（\(\gcd(0,12)=12\)）。
- 于是 \(\mathbb{Z}_{12}^\times=\{1,5,7,11\}\)，共 \(4\) 个，正好 \(\varphi(12)=4\)。
为什么数论里偏爱 \(\mathbb{Z}_n^\times\)
\(\mathbb{Z}_n^\times\) 里的元素正是那些模 \(n\) 可逆的剩余类：\(a\in\mathbb{Z}_n^\times\) 当且仅当存在 \(b\) 使 \(ab\equiv 1\pmod n\)。因此在加性组合的应用里，当我们想让“乘以某个数”这一步可以撤销、或想保证某个分布在模 \(n\) 下“铺得均匀”时，就会要求相关的数落在 \(\mathbb{Z}_n^\times\) 中。这正是原文把它单独拎出来、准备写成引理的原因。
例·互素 ⇒ 可逆（取 \(n=12,\ a=5\)）
- \(5\in\mathbb{Z}_{12}^\times\)（已知 \(\gcd(5,12)=1\)）。
- 找 \(5\) 的逆：试 \(5\times 5=25=2\cdot 12+1\equiv 1\pmod{12}\)。
- 所以 \(5^{-1}\equiv 5\pmod{12}\)，“乘以 \(5\)”可以靠“再乘一次 \(5\)”撤销。
- 反观 \(6\notin\mathbb{Z}_{12}^\times\)：\(6\times b\) 永远是偶数，绝不可能 \(\equiv 1\pmod{12}\)，故 \(6\) 不可逆。
讲解三：本节的整体思路（把工具接到应用上）
把前两部分拼起来，就能看清 12.6 节的写作脉络，即便后续具体应用未在本 PDF 中给出，其套路是清楚的：
- 准备引理：先证一条关于 \(\mathbb{Z}_n^\times\) 的小引理（原文“下面这条简单的引理会很有用”所指）。它通常用来保证某些剩余类可以被“调准”到我们想要的位置。
- 归约：把待解决的具体问题，改写成“某个集合的和集是否含有长真等差数列”。
- 套用推论 12.13：只要那个集合足够稠密，工具立刻吐出一条长等差数列。
- 翻译回去：把这条等差数列在原问题语境下的含义读出来，即得结论。
小结本节标题“进一步的应用”意味着：第 12 章辛苦建立的“稠密集的和集含长等差数列”这把工具，到这里开始收获果实。原文给出的开头两步——引用推论 12.13、引入互素剩余类 \(\mathbb{Z}_n^\times\)——正是把工具接到具体问题上的标准接口。理解了 \(\mathbb{Z}_n^\times=\{a:\gcd(a,n)=1\}\)（大小为 \(\varphi(n)\)，元素都模 \(n\) 可逆）这一概念，就握住了打开后续应用的钥匙。
返回 全书目录