本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。
本节目标前面几节里，“和积问题”是在实数 \(\mathbb{R}\) 上讨论的：一个实数有限集 \(A\)，它的和集 \(A+A\) 与积集 \(A\cdot A\) 不可能同时都很小。本节要把这个现象搬到别的数系上去——主要是复数 \(\mathbb{C}\)。难点在于：实数的证明用到了 Szemerédi–Trotter 关联定理，而那条定理的实数证明依赖“交叉数”技巧，到了复数上不再适用。本节展示 Solymosi 的一个巧妙做法：用双重计数（同一个量从两个角度去数）绕开关联定理，直接得到复数版的和积估计，而且这套办法对四元数、矩阵等更多数系也奏效。
和积问题的一个自然推广，是考虑来自 \(\mathbb{R}\) 以外的域与环中的集合。其中一个例子（把 \(\mathbb{R}\) 换成素数 \(p\) 对应的 \(\mathbb{Z}_p\)）已在前面某一章中讨论过。在本节中，我们考虑把 \(\mathbb{R}\) 换成复数的情形。
攻克这个问题的一条途径，是先证明一个复数版的 Szemerédi–Trotter 定理，然后照搬定理 8.14 与定理 8.15 的证明。虽然人们相信 Szemerédi–Trotter 定理的结论对复直线与复点也成立，但证明它并不容易，因为使用交叉数（crossing number）的那套技术不再适用（不过可参看 Tóth [368] 最近的一项宣告）。
在下文中，我们将展示：借助一个巧妙的双重计数论证，可以把 Elekes 的结果推广到复数。事实上，这个论证（归功于 Solymosi [325]）对另外几个数域同样有效（见证明末尾的注记）。
先认清记号
- \(A+B=\{a+b:a\in A,\;b\in B\}\)：所有“一个来自 \(A\)、一个来自 \(B\)”的和组成的集合。
- \(A\cdot Q=\{a q:a\in A,\;q\in Q\}\)：所有这样的积组成的集合。
- \(|X|\)：有限集 \(X\) 的元素个数。
- 记号 \(f=\Omega(g)\) 表示“存在一个与集合大小无关的正常数 \(c\)，使得 \(f\ge c\,g\)”，也就是“\(f\) 至少有 \(g\) 那么大”。本节所有结论都是这种下界。
定理 8.24 [325] 对任意有限非空的复数集合 \(A,B,Q\)，有
\[\tag{8.6}|A+B|\cdot|A\cdot Q|=\Omega\!\left(|A|^{3/2}\,|B|^{1/2}\,|Q|^{1/2}\right).\]
令 \(Q=B=A\)，立即得到
\[|A+A|\cdot|A\cdot A|=\Omega\!\left(|A|^{5/2}\right),\]
以及（由“两个正数之和不小于它们几何平均的两倍”这一基本不等式）
\[|A+A|+|A\cdot A|=\Omega\!\left(|A|^{5/4}\right),\]
因此本定理推广了定理 8.14。
例：两条推论是怎么来的
设 \(X=|A+A|\)，\(Y=|A\cdot A|\)。把 \(Q=B=A\) 代入 \((8.6)\)：右边的 \(|A|^{3/2}|A|^{1/2}|A|^{1/2}=|A|^{5/2}\)，于是
\[XY=\Omega\!\left(|A|^{5/2}\right).\]
再用算术–几何平均不等式 \(X+Y\ge 2\sqrt{XY}\)：
\[X+Y\ge 2\sqrt{XY}=\Omega\!\left(\sqrt{|A|^{5/2}}\right)=\Omega\!\left(|A|^{5/4}\right).\]
这正是“和集与积集不能同时小”的复数版定量陈述：若 \(|A+A|\) 和 \(|A\cdot A|\) 都接近最小值 \(|A|\)，乘积就只有 \(|A|^2\) 量级，与 \(|A|^{5/2}\) 矛盾。
证明的核心想法
这套证明在干什么
我们要去数一种叫“好四元组”\((a,a',b,q)\) 的对象的总数 \(N\)，然后
从两个方向估计 \(N\)：
- 下界：用一个几何事实（一个点最多被 7 个圆盘盖住）说明好四元组很多，得到 \(N\ge\tfrac12|A||B||Q|\)。
- 上界：用“四元组被它的像唯一决定”加上“好”的限制条件，说明好四元组不会太多，得到 \(N\le 784\,\dfrac{|A+B|^2|A\cdot Q|^2}{|A|^2}\)。
同一个 \(N\) 被夹在中间，两头一比，就逼出 \((8.6)\)。这就是“双重计数”。
证明.
我们可以假设 \(|A|\ge 2\) 且 \(0\notin Q\)（否则结论平凡或可平移化归）。由初等代数可知，映射
\[(a,a',b,q)\;\longmapsto\;(a+b,\;a'+b,\;a q,\;a' q)\]
是从 \(A\times A\times B\times Q\) 到 \((A+B)\times(A+B)\times(A\cdot Q)\times(A\cdot Q)\) 的
单射（一对一），只要我们排除对角线 \(a=a'\) 的情形。
仅凭这一观察，只能得到平凡的下界 \(|A+B|\cdot|A\cdot Q|=\Omega\!\left(|A|\,|B|^{1/2}\,|Q|^{1/2}\right)\)。但我们可以做得更好，办法是利用一个直观的观察：若 \(a'\) 离 \(a\) 很近，则 \(a'+b\) 也离 \(a+b\) 很近，且 \(a q\) 离 \(a' q\) 很近。
为什么那个映射是单射
给定像 \((s_1,s_2,p_1,p_2)=(a+b,\,a'+b,\,aq,\,a'q)\)，能不能把 \(a,a',b,q\) 反解出来？
- \(s_1-s_2=(a+b)-(a'+b)=a-a'\)。
- \(p_1-p_2=aq-a'q=(a-a')q\)。
- 因为排除了对角线，\(a-a'\neq 0\)，于是 \(q=\dfrac{p_1-p_2}{s_1-s_2}\) 被唯一确定。
- 有了 \(q\)，由 \(a=p_1/q\) 定出 \(a\)，再由 \(b=s_1-a\) 定出 \(b\)，最后 \(a'=s_2-b\)。
所以四元组被它的像唯一决定——这正是上界论证要反复用到的“可逆性”。
平凡下界为什么是 \(\Omega(|A||B|^{1/2}|Q|^{1/2})\)
单射意味着定义域的大小 \(\le\) 值域里被用到的部分的大小，即
\[|A|(|A|-1)\,|B|\,|Q|\;\le\;|A+B|^2\cdot|A\cdot Q|^2.\]
两边开平方，\(\;|A+B|\cdot|A\cdot Q|\ge\sqrt{|A|(|A|-1)|B||Q|}=\Omega(|A||B|^{1/2}|Q|^{1/2})\)。
这个下界的指数是 \(|A|^1\)，而我们想要的是更强的 \(|A|^{3/2}\)。差距正是靠“最近邻很近”这条额外信息补上的。
最近邻与“好四元组”
更确切地说，对每个 \(a\in A\)，定义它的最近邻 \(a'\) 为 \(A\setminus\{a\}\) 中使距离 \(|a-a'|\) 最小的元素。（若最近邻的候选不止一个，任取其一。）我们把 \((a,a')\) 称为一个相邻对（neighboring pair），于是一共有 \(|A|\) 个相邻对。注意提醒：若 \((a,a')\) 是相邻对，\((a',a)\) 未必也是相邻对。
复数就是复平面上的点。每个 \(a\) 有一个离它最近的 \(a'\)，构成相邻对 \((a,a')\)。共 \(|A|\) 个相邻对。
称四元组 \((a,a',b,q)\) 为好的（good），如果 \((a,a')\) 是相邻对、\(b\in B\)、\(q\in Q\)，并且满足以下两条邻近性条件：
\[\tag{8.7}\bigl|\{u\in A+B:\ |a+b-u|\le|a-a'|\}\bigr|\ \le\ \frac{28\,|A+B|}{|A|},\]
以及
\[\tag{8.8}\bigl|\{v\in A\cdot Q:\ |aq-v|\le|aq-a'q|\}\bigr|\ \le\ \frac{28\,|A\cdot Q|}{|A|}.\]
不正式地说，\((8.7)\) 与 \((8.8)\) 断言：\(a'+b\) 是 \(a+b\) 在 \(A+B\) 中一个相当近的邻居，类似地 \(a'q\) 是 \(aq\) 在 \(A\cdot Q\) 中一个相当近的邻居。我们将对 \(N\)（好四元组的个数）施加双重计数论证。
条件 (8.7) 在说什么
固定 \(a,a',b\)。在和集 \(A+B\) 里，以点 \(a+b\) 为中心、以 \(|a-a'|\) 为半径画一个小圆盘。\((8.7)\) 说：落在这个小圆盘里的 \(A+B\) 元素不超过 \(\dfrac{28|A+B|}{|A|}\) 个——即 \(a+b\) 附近不太拥挤。注意半径 \(|a-a'|\) 很小（因为 \(a'\) 是 \(a\) 的最近邻），所以这是“\(a'+b\) 距 \(a+b\) 只隔着很少几个 \(A+B\) 点”的精确说法。\((8.8)\) 对积集 \(A\cdot Q\) 是同样的意思。
第一步：下界（好四元组很多）
先建立下界。对每个 \(a\in A\)，令
\[D_a:=\{z\in\mathbb{C}:\ |z-a|\le|a'-a|\}\]
为以 \(a\) 为圆心、\(|a'-a|\) 为半径的圆盘。一个简单的几何论证（留作习题 8.5.1）表明：任何一个复数 \(z\) 至多被这些圆盘中的七个所包含。特别地，对任意 \(b\in B\) 有
\[\sum_{a\in A}\bigl|\{u\in A+B:\ |a+b-u|\le|a-a'|\}\bigr|=\sum_{z\in A+B-b}\bigl|\{a\in A:\ z\in D_a\}\bigr|\le 7\,|A+B|,\]
类似地，对任意 \(q\in Q\) 有
\[\sum_{a\in A}\bigl|\{v\in A\cdot Q:\ |aq-v|\le|aq-a'q|\}\bigr|=\sum_{z\in A\cdot Q/q}\bigl|\{a\in A:\ z\in D_a\}\bigr|\le 7\,|A\cdot Q|.\]
这两步求和怎么换序的
看第一条等式。把内层那个计数 \(\{u\in A+B:|a+b-u|\le|a-a'|\}\) 里的 \(u\) 换成 \(z:=u-b\)，则 \(z\in A+B-b\)，而条件
\[|a+b-u|=|a-(u-b)|=|a-z|\le|a-a'|=|a'-a|\]
恰好就是 \(z\in D_a\)。于是
\[\sum_{a\in A}\#\{u:\dots\}=\sum_{a\in A}\#\{z\in A+B-b:z\in D_a\}=\sum_{z\in A+B-b}\#\{a\in A:z\in D_a\}.\]
最后一个等号只是把“先对 \(a\) 后对 \(z\)”改成“先对 \(z\) 后对 \(a\)”地数同一批 \((a,z)\) 配对。由“每个 \(z\) 至多在 7 个 \(D_a\) 里”，内层 \(\le 7\)，而 \(z\) 的取值不超过 \(|A+B|\) 种，故总和 \(\le 7|A+B|\)。第二条等式把 \(v\) 换成 \(z:=v/q\)、用 \(|aq-v|=|q|\,|a-z|\) 同理可得。
习题 8.5.1 的几何事实：若 \(z\) 同时落在 \(D_a\) 与 \(D_{a'}\) 中（\(a,a',z\) 互不相同），则 \(a,a'\) 关于 \(z\) 张成的夹角至少 \(60^\circ\)。绕一圈 \(360^\circ\) 最多塞下 \(6\) 个这样的圆心，故任一点至多被 \(7\) 个圆盘覆盖。
因此，若固定 \(b\) 与 \(q\)，并在 \(A\) 中均匀随机地选取 \(a\)，则对 Markov 不等式的一次简单应用表明：\((a,a',b,q)\) 是好的概率至少为 \(1/2\)。这说明
\[\tag{8.9}N\ \ge\ |B|\,|Q|\,\frac{|A|}{2}.\]
Markov 不等式怎么给出概率 ≥ 1/2
固定 \(b,q\)，在 \(A\) 里随机取 \(a\)（每个概率 \(1/|A|\)）。
- 记随机变量 \(X=\bigl|\{u\in A+B:|a+b-u|\le|a-a'|\}\bigr|\)。它的平均值就是上面那条和式除以 \(|A|\)：
\[\mathbb{E}[X]=\frac{1}{|A|}\sum_{a\in A}X\le\frac{7|A+B|}{|A|}.\]
- Markov 不等式：对非负 \(X\)，\(\Pr\bigl(X\ge 4\,\mathbb{E}[X]\bigr)\le\tfrac14\)。取阈值 \(\dfrac{28|A+B|}{|A|}=4\cdot\dfrac{7|A+B|}{|A|}\ge 4\,\mathbb{E}[X]\)，故条件 \((8.7)\) 失败的概率 \(\le\tfrac14\)。
- 同理条件 \((8.8)\) 失败的概率 \(\le\tfrac14\)。
- 两者至少一个失败的概率 \(\le\tfrac14+\tfrac14=\tfrac12\)，于是两条同时成立（即四元组是好的）的概率 \(\ge\tfrac12\)。
- 对固定 \(b,q\)，好的 \(a\) 至少有 \(\tfrac12|A|\) 个；再对所有 \(b\in B,\,q\in Q\) 求和，便得 \(N\ge|B||Q|\cdot\tfrac{|A|}{2}\)。
第二步：上界（好四元组不会太多）
现在建立上界。回忆前面所述：四元组 \((a,a',b,q)\) 被四元组 \((a+b,\,a'+b,\,aq,\,a'q)\) 唯一决定。其中 \(a+b\) 有 \(|A+B|\) 种选择，\(aq\) 有 \(|A\cdot Q|\) 种选择。对固定的 \(a+b\)，由 \((8.7)\) 可知，\(A+B\) 中比 \(a'+b\) 更靠近、或与之等距于 \(a+b\) 的元素至多有 \(\dfrac{28|A+B|}{|A|}\) 个，因而 \(a'+b\) 的取值至多有 \(\dfrac{28|A+B|}{|A|}\) 种。类似地，\(a'q\) 的取值至多有 \(\dfrac{28|A\cdot Q|}{|A|}\) 种。这给出上界
\[\tag{8.10}N\ \le\ |A+B|\cdot\frac{28|A+B|}{|A|}\cdot|A\cdot Q|\cdot\frac{28|A\cdot Q|}{|A|}.\]
把它与下界结合，即得所要的结论。♦
把两头合起来，凑出指数 3/2
下界 \((8.9)\) 与上界 \((8.10)\) 夹住同一个 \(N\)：
\[|B||Q|\frac{|A|}{2}\ \le\ N\ \le\ 28^2\,\frac{|A+B|^2\,|A\cdot Q|^2}{|A|^2}.\]
两端整理（\(28^2=784\)）：
\[|A+B|^2\,|A\cdot Q|^2\ \ge\ \frac{|A|^3\,|B|\,|Q|}{1568}.\]
开平方：
\[|A+B|\cdot|A\cdot Q|\ \ge\ \frac{1}{\sqrt{1568}}\,|A|^{3/2}\,|B|^{1/2}\,|Q|^{1/2}=\Omega\!\left(|A|^{3/2}|B|^{1/2}|Q|^{1/2}\right).\]
注意指数从平凡下界的 \(|A|^1\) 升到了 \(|A|^{3/2}\)，多出来的半个幂正是“最近邻很近 ⇒ 像也很近 ⇒ \(a'+b,a'q\) 的可能取值很少”这条信息贡献的。
为什么要数“好四元组”而不是全部四元组
若直接数全部四元组（不要求好），上界就只能用“\(a'+b\) 有 \(|A+B|\) 种、\(a'q\) 有 \(|A\cdot Q|\) 种”，得到 \(N\le|A+B|^2|A\cdot Q|^2\)，配上平凡下界 \(N\ge|A|(|A|-1)|B||Q|\)，只能回到弱的 \(|A|^1\) 估计。“好”的限制把 \(a'+b\) 的种数从 \(|A+B|\) 砍到 \(\tfrac{28|A+B|}{|A|}\)（相当于除以 \(|A|\)），正是这次“砍价”让上界更小、从而逼出更强的下界。下界一侧则用几何（7 个圆盘）保证“好”的四元组依然占了一半，没被砍太狠。
注记 8.25
类似的论证对四元数以及其他超复数同样有效。一般地，设 \(T\) 与 \(Q\) 是一组相似变换（similarity transformations），\(A\) 是空间中的一组点，使得：从任一四元组 \(\bigl(t(p_1),\,t(p_2),\,q(p_1),\,q(p_2)\bigr)\) 都能唯一确定出 \(t\in T\)、\(q\in Q\) 与 \(p_1\neq p_2\in A\)，则
\[c\,|A|^{3/2}\,|T|^{1/2}\,|Q|^{1/2}\ \le\ |T(A)|\cdot|Q(A)|,\]
其中常数 \(c\) 只依赖于空间的维数。
注记 8.25 与定理 8.24 的对应
在复数情形里：把“加上 \(b\)”看成平移变换 \(t\)（属于 \(T\)，对应集合 \(B\)），把“乘以 \(q\)”看成放缩–旋转变换 \(q\)（属于 \(Q\)）——它们都是复平面的相似变换。点集就是 \(A\)。于是 \(T(A)=A+B\)、\(Q(A)=A\cdot Q\)，上面的抽象不等式正好退化为定理 8.24。把“相似变换”换成更高维空间里的相似变换，同一证明框架（最近邻 + 圆盘覆盖 + 双重计数）就给出四元数等数系的结果，只是“一点至多被几个球覆盖”的那个常数随维数变化，故 \(c\) 依赖维数。
矩阵上的和积问题
作为本节的结尾，让我们描述 Chang 最近的一项结果，她研究了矩阵的和积问题 [51]。
定理 8.26 存在一个随 \(n\to\infty\) 而趋于无穷的函数 \(\psi(n)\)，使得下述成立。设 \(d\) 为固定整数，\(A\) 为一个由 \(d\times d\) 实矩阵组成的有限集合，且对 \(A\) 中任意两个不同元素 \(M\) 与 \(M'\)，都有 \(\det(M-M')\neq 0\)。则
\[|A+A|+|A\cdot A|\ \ge\ \psi(|A|)\,|A|.\]
定理 8.27 对每个 \(d\)，存在正常数 \(\delta=\delta(d)\)，使得下述成立。设 \(A\) 为一个由 \(d\times d\) 实对称矩阵组成的有限集合。则
\[|A+A|+|A\cdot A|\ \ge\ |A|^{1+\delta}.\]
这两条定理的证明比这里给出的更为复杂，细节请读者参看 [51]。
两条矩阵定理在说什么、有何不同
- 共同点：和集 \(A+A\)（矩阵逐项相加得到的所有矩阵）与积集 \(A\cdot A\)（矩阵相乘得到的所有矩阵）依旧不能同时小。
- 定理 8.26 给出的下界是 \(\psi(|A|)\cdot|A|\)：只比平凡的 \(|A|\) 多出一个慢慢变大的因子 \(\psi\)（增长速度未明说），代价是要求矩阵两两之差可逆（\(\det(M-M')\neq0\)）。
- 定理 8.27 把矩阵限制为对称矩阵，换来更强的多项式型下界 \(|A|^{1+\delta}\)，其中 \(\delta>0\) 只依赖维数 \(d\)。
可见“结构假设越强（对称），能证出的下界越好（指数严格大于 1）”。
矩阵版和积问题：由同一个矩阵集 \(A\) 生成的和集 \(A+A\) 与积集 \(A\cdot A\)，两者大小之和有下界。定理 8.26、8.27 给出不同假设下的不同下界。
习题
习题 8.5.1
沿用定理 8.24 证明中的记号，证明：每个复数至多被七个圆盘 \(D_a\) 所包含。（提示：证明若 \(z\) 同时含于 \(D_a\) 与 \(D_{a'}\) 中，且 \(a,a',z\) 互不相同，则 \(a,a'\) 关于 \(z\) 张成的夹角至少为 \(60^\circ\)。）
习题 8.5.1 的思路
- 设 \(z\in D_a\cap D_{a'}\)，即 \(|z-a|\le|a-(a\text{ 的最近邻})|\) 且 \(|z-a'|\le|a'-(a'\text{ 的最近邻})|\)。由“最近邻是最近的”这一定义，可推出 \(|a-a'|\ge|z-a|\) 且 \(|a-a'|\ge|z-a'|\)（因为 \(a'\) 不比 \(a\) 自己的最近邻更近、反之亦然）。
- 于是在三角形 \(z\,a\,a'\) 中，边 \(aa'\) 是最长边。最长边所对的角（即 \(z\) 处的角 \(\angle a z a'\)）是最大角，故 \(\angle aza'\ge 60^\circ\)（三角形内角和 \(180^\circ\)，最大角不小于平均的 \(60^\circ\)）。
- 把所有“含 \(z\) 的圆盘”对应的圆心 \(a\) 画在 \(z\) 周围：它们两两关于 \(z\) 的夹角都 \(\ge 60^\circ\)。绕 \(z\) 一圈总共 \(360^\circ\)，最多容纳 \(\lfloor 360^\circ/60^\circ\rfloor=6\) 个互成 \(\ge60^\circ\) 的方向。再算上可能恰好有某个圆心 \(a=z\)（此时 \(z\in D_a\) 自动成立）的退化情形，总数至多 \(7\)。
这正是下界论证里“一点至多被 7 个圆盘覆盖”所依据的几何事实。
返回 全书目录