5.2　向量空间中的和集Sum sets in vector spaces

证明. 我们对 \(d\) 作归纳。若 \(d=1\)，结论由定理 5.5 给出（一维 Freiman 型不等式）。故设 \(d\ge 2\) 且结论对 \(d-1\) 已成立。现在固定 \(d\)，再对 \(|A|\) 作归纳。当 \(|A|=1\) 时结论平凡成立（空洞地真），故设 \(|A|\ge 2\) 且结论对更小的集合 \(A\) 已成立。

取 \(a\in A\) 为 \(A\) 的任意一个极点；即 \(a\) 是 \(A\) 的凸包上的一个顶点。令 \(A':=A\setminus\{a\}\)。我们分两种情形。

情形一：\(\operatorname{rank}(A')\ge d\)。 则由（对 \(|A|\) 的）归纳假设， \[|A'+A'|\ge (d+1)|A'|-\frac{d(d+1)}{2}.\] 由于 \(a\) 落在 \(A'\) 的凸包之外且 \(\operatorname{rank}(A')\ge d\)，必定存在（用贪心算法）\(A'\) 的至少 \(d\) 个极点 \(x_1,\dots,x_d\)，它们从 \(a\) “可见”，意思是连接 \(a\) 到 \(x_1,\dots,x_d\) 的线段都落在 \(A'\) 的凸包之外。特别地，我们看到 \(d+1\) 个点 \[a,\ \frac{a+x_1}{2},\ \dots,\ \frac{a+x_d}{2}\] 落在 \(A'\) 的凸包之外，从而尤其落在 \(\tfrac12\cdot(A'+A')\) 之外。把它放大 \(2\) 倍，便看到 \(a+a,\ a+x_1,\ \dots,\ a+x_d\) 都与 \(A'+A'\) 不相交。于是 \[|A+A|\ge (d+1)+|A'+A'|\ge (d+1)|A|-\frac{d(d+1)}{2},\] 从而闭合了归纳。

情形二：\(\operatorname{rank}(A')< d\)。 则 \(A'\) 被包含在一个 \(d-1\) 维仿射空间 \(W\) 中。因为 \(\operatorname{rank}(A)\ge d\)，所以 \(a\notin W\)。这意味着 \(2a\)、\(a+W\)、\(2W\) 两两不相交；从而 \(a+a\)、\(a+A'\)、\(A'+A'\) 两两不相交；于是 \[|A+A|\ge 1+(|A|-1)+|A'+A'|.\] 但因为 \(\operatorname{rank}(A)\ge d\)，我们有 \(\operatorname{rank}(A')=\operatorname{rank}(A\setminus\{a\})\ge d-1\)，故由（对 \(d\) 的）归纳， \[|A'+A'|\ge d|A'|-\frac{d(d-1)}{2}=d|A|-\frac{d(d+1)}{2},\] 结论再次由归纳得出。♦

证明. 不失一般性可取 \(V=\mathbb{R}^n\)。由 Hahn–Banach 定理，存在线性泛函 \(\varphi:V\to\mathbb{R}\) 使得对所有 \(x\in(A\cup B)\setminus 0\) 都有 \(\varphi(x)>0\)（这是因为 \(0\) 是凸包顶点，可用一张支撑超平面把 \(0\) 之外的点全推到正侧）。我们要证明 \(A+B\) 的每个元素 \(x\) 都落在 \(C\) 的张成中。对 \(\varphi(x)\) 的取值（在 \(\varphi\) 于 \(A\cup B\) 上取到的有限个值中，按从小到大的次序）作归纳。若 \(\varphi(x)=0\)，则 \(x=0\)，无需证明。现设 \(\varphi(x)>0\) 且结论对更小的 \(\varphi(x)\) 值已成立。

若 \(x\in A'+B'\)，则可写 \(x=a+b\)，其中 \(a\in A'\)、\(b\in B'\)。但由于 \(\varphi(x)=\varphi(a)+\varphi(b)\) 且 \(\varphi(a),\varphi(b)>0\)，我们看到 \(\varphi(a),\varphi(b)\) 都严格小于 \(\varphi(x)\)，结论由归纳得出（\(a,b\) 各自落在 \(C\) 的张成中）。剩下唯一的情形是 \(\varphi(x)>0\) 且 \(x\notin A'+B'\)。但既然 \(x\in A+B\)，这就推出 \(x\in C\)（即 \(x\) 落在 \(A'\cup B'\) 里却不在 \(A'+B'\) 里），证毕。♦

证明. 设 \(A,B\) 如 \(S(d,n,t)\) 定义中所取；注意 \(A,B\) 至少含两个元素。由于 \(A,B\) 有限，可找到一个在 \(A\cup B\) 上单射的线性泛函 \(\varphi:V\to\mathbb{R}\)（事实上随机取一个 \(\varphi\) 即可）。由单射性，存在唯一的 \(a_0\in A\) 在 \(A\) 上极小化 \(\varphi\)，即对所有 \(a\in A\setminus a_0\) 有 \(\varphi(a)>\varphi(a_0)\)。类似地有 \(b_0\in B\) 在 \(B\) 上极小化 \(\varphi\)。必要时平移 \(A,B\)，可设 \(a_0=b_0=0\)。于是 \(A,B\) 现在都含 \(0\)，若定义 \(A':=A\setminus\{0\}\)、\(B':=B\setminus\{0\}\)，则 \(\varphi\) 在 \(A'\) 与 \(B'\) 上严格为正。特别地 \(\varphi\) 在 \(A'+B'\) 上严格为正，从而 \(A'+B'\) 不含 \(0\)。

由引理 5.14（此时 \(0\) 确为 \(A\cup B\) 的凸包顶点）， \[|(A'\cup B')\setminus(A'+B')|\ge d,\] 从而（由于 \(0\) 在 \(A+B\) 中但不在 \(A'\)、\(B'\) 或 \(A'+B'\) 中） \[|A+B|\ge |A'+B'|+d+1.\]

设 \(c+W\) 表示 \(A'+B'\) 的仿射张成，其中 \(c\in V\)，\(W\) 是 \(V\) 的线性子空间。若我们知道 \(\operatorname{rank}(A'+B')=\dim(W)\ge d\)，便可断定 \(|A'+B'|\ge S(d,n-1,t)\)，于是（结合上式）便得第一项，证毕。故可设 \(\dim(W)\le d-1\)。于是任取 \(a_1\in A'\)、\(b_1\in B'\)，则有 \(A'\subseteq a_1+W\)、\(B'\subseteq b_1+W\)。从而 \(A'+B'\) 被包含在 \(W,a_1,b_1\) 的张成中。由假设（\(\operatorname{rank}(A+B)\ge d\) 而 \(\dim W\le d-1\)），这意味着 \(a_1,b_1\) 中至少有一个落在 \(W\) 之外。

下面依据 \(a_1,b_1\) 相对 \(W\) 的位置分几种情形。

情形一：\(a_1,b_1\) 模 \(W\) 线性无关。 则 \(A=\{0\}\cup A'\) 落在 \(\{0,a_1\}+W\) 中，从而与落在 \(\{b_1,a_1+b_1\}+W\) 中的 \(A'+B'\) 不相交；于是 \[|A+B|\ge |A'+B'|+|A|\ge |A'+B'|+n.\] 另一方面 \(\operatorname{rank}(A'+B')\ge \operatorname{rank}(A+B)-1\ge d-1\)，这给出 \(|A'+B'|\ge S(d-1,n-1,t)\)。本情形结论（第二项）成立。

情形二：\(a_1,b_1\) 模 \(W\) 线性相关，且 \(b_1\notin W\)。 则 \(A\subseteq a_1+W\) 与 \(A'+B'\subseteq a_1+b_1+W\) 不相交，而 \(0\) 既与 \(A'\) 不相交（按定义），也与 \(A'+B'\) 不相交（前述）。于是 \[|A+B|\ge 1+|A'|+|A'+B'|\ge n+|A'+B'|.\] 另一方面，由于 \(A'+B'\) 被包含在 \(W\) 与 \(b_1\) 的张成中，\(\operatorname{rank}(A'+B')=\dim(W)\ge \operatorname{rank}(A+B)-1\ge d-1\)，故 \(|A'+B'|\ge S(d-1,n-1,t)\)。结论（第二项）再次成立。

情形三（剩余）：\(b_1\in W\)。 由前面的讨论，这迫使 \(a_1\notin W\)。则 \(A'+B'\) 与 \(B\) 不相交，于是 \[|A+B|\ge |B|+|A'+B'|\ge (n-t)+|A'+B'|.\] 但由于 \(\operatorname{rank}(A'+B')\ge \operatorname{rank}(A+B)-1\ge d-1\)，我们有 \(|A'+B'|\ge S(d-1,n-1,t-1)\)，结论（第三项）再次成立。♦

证明. 当 \(d=0\)、\(n=1\) 或 \(r\ge n-1\)（即 \(d\) 退化或区间退化）等情形可由 (5.12) 直接验证，故可限于 \(d\ge 1\)、\(n\ge 2\)、\(t\le n-2\)。我们对正量 \(n+d+t\) 作归纳，归纳地假设结论对所有更小的 \(n+d+t\) 已成立。于是把命题 5.15 的三项分别用归纳假设展开：

第一项： \[S(d,n-1,t)+d+1\ge \sum_{n-d-1\le r\le n-1} r-\sum_{1\le s\le t}\min(s,d)+d+1=\sum_{n-d\le r\le n} r-\sum_{1\le s\le t}\min(s,d),\] 这里用到把求和下端从 \(n-d-1\) 抬到 \(n-d\)、上端从 \(n-1\) 抬到 \(n\)，恰好补进一个 \(d+1\)。

第二项： \[S(d-1,n-1,t)+n\ge \sum_{n-d\le r\le n-1} r-\sum_{1\le s\le t}\min(s,d-1)+n\ge \sum_{n-d\le r\le n} r-\sum_{1\le s\le t}\min(s,d),\] 这里用到 \(\min(s,d-1)\le\min(s,d)\)。

第三项： \[S(d-1,n-1,t-1)+n-t\ge \sum_{n-d\le r\le n-1} r-\sum_{1\le s\le t-1}\min(s,d-1)+n-t\ge \sum_{n-d\le r\le n} r-\sum_{1\le s\le t}\min(s,d),\] 这里用到恒等式 \(\sum_{1\le s\le t}\min(s,d)=\sum_{1\le s\le t-1}\min(s,d-1)+t\)。

三项都不小于目标右端，故结论由命题 5.15 得出。♦

证明. 在推论 5.16 中取 \(n:=|A|\)、\(t:=|A|-|B|\)，并利用平凡界 \(\min(s,d)\le d\)（故 \(\sum_{1\le s\le t}\min(s,d)\le dt\)）。注意 \[\sum_{n-d\le r\le n} r=(d+1)n-\frac{d(d+1)}{2},\] （这是 \(d+1\) 个连续整数之和），故 \[|A+B|\ge (d+1)n-\frac{d(d+1)}{2}-dt=n+d(n-t)-\frac{d(d+1)}{2}.\] 代入 \(n-t=|B|\) 即得所欲。♦

证明. 我们对余维 \(r\) 作归纳。

\(r=1\)。 不失一般性可取 \(V\) 为欧氏空间 \(\mathbb{R}^d\)。令 \(v_1\) 为 \(A\) 中使量 \(\operatorname{dist}(v_1,W)\) 最大的元素；则容易看出 \(1\)-平行体 \(P=0+I\cdot v_1\) 满足所需性质（这里利用 \(A\) 的对称性，把 \(P\) 的两个角点 \(\pm v_1\) 都放进 \(A\)）。

\(r\ge 2\)，且结论对所有更小的 \(r\) 已成立。 把 \(W\) 放进一个 \(d-1\) 维超平面 \(H\subset V\) 中，\(H\) 把 \(V\) 分成超平面 \(H\) 与两个开半空间 \(H_-,H_+\)。由鸽巢原理，三个集合 \(A\cap H\)、\(A\cap H_-\)、\(A\cap H_+\) 中有一个的基数至少是 \(|A|/3\)。

先设 \(|A\cap H|\ge |A|/3\)。则对（把 \(V\) 换成 \(H\)、\(d\) 换成 \(d-1\) 的）归纳假设应用，可找到一个角点落在 \(A\cap H\subseteq H\) 内、中心为 \(0\) 的 \(r-1\)-平行体 \(P\subset H\subset V\)，使得 \[|A\cap(P+W)|\ge |(A\cap H)\cap(P+W)|\ge (9K)^{-2^{\,r-2}+1}\,|A|/3\ge (9K)^{-2^{\,r-1}+1}\,|A|.\] 结论随之得出，只需给 \(P\) 添加一个哑向量 \(v_r=0\) 把它补成 \(r\)-平行体。

不失一般性，剩下要考虑 \(|A\cap H_+|\ge |A|/3\) 的情形。由于 \(|2(A\cap H_+)|\le |2A|\le K|A|\)，我们得到 \(\sigma[A\cap H_+]\le 3K\)。由练习 2.3.14，可得一个关于某中心 \(a=x/2\) 对称的子集 \(F\)（即 \(F=x-F\)），满足 \(|F|\ge |A|/9K\) 且 \(\sigma[F]\le 9K^2\)。由于 \(F\) 整个含于半空间 \(H_+\)，其对称中心 \(a\in H_+\)，特别地 \(a\notin W\)。现令 \(W'\) 为由 \(W\) 与 \(a\) 张成的 \(d-r+1\) 维线性空间，并对（把 \(A\) 换成 \(F-a\)、\(K\) 换成 \(9K^2\)、\(W\) 换成 \(W'\)、\(r\) 换成 \(r-1\) 的）归纳假设应用。这让我们找到一个中心为 \(a\)、角点落在 \(F\) 内的 \(r-1\)-平行体 \(P'=a+I\cdot v_1+\cdots+I\cdot v_{r-1}\)，使得 \[|F\cap(P'+W')|\ge (81K^2)^{-2^{\,r-2}+1}\,|F|\ge (9K)^{-2^{\,r-1}+1}\,|A|.\]

现在令 \(P\) 为 \(r\)-平行体 \(I\cdot a+I\cdot v_1+\cdots+I\cdot v_{r-1}\)；由于 \(F\) 与 \(-F\) 都含于 \(A\)（\(A\) 对称），我们看到 \(P\) 的角点都落在 \(A\) 内，且 \(P\) 当然以原点为中心。要完成证明，我们需要证明 \[|A\cap(P+W)|\ge |F\cap(P'+W')|.\]

为证此，我们用一个滑动论证，利用 \(A\) 与 \(F\) 的对称性。把 \(W'=W'_{>0}\cup W'_{\le 0}\) 拆开，其中 \(W'_{>0}\) 是 \(W'\) 中以 \(W\) 为边界、含 \(a\) 的开半空间，\(W'_{\le 0}\) 是 \(W'\) 中以 \(W\) 为边界、不含 \(a\) 的闭半空间。则 \[\begin{aligned}|F\cap(P'+W')|&=|F\cap(P'+W'_{>0})|+|F\cap(P'+W'_{\le 0})|\\&=|(F-2a)\cap(P'+W'_{>0}-2a)|+|F\cap(P'+W'_{\le 0})|\\&=|(-F)\cap(P'+W'_{>0}-2a)|+|F\cap(P'+W'_{\le 0})|\\&=\bigl|[(-F)\cap(P'+W'_{>0}-2a)]\cup[F\cap(P'+W'_{\le 0})]\bigr|,\end{aligned}\] 这里用到 \(F\) 关于 \(a\) 对称（故 \(F-2a=-F\)），以及 \(F\) 与 \(-F\) 不相交（一个落在 \(H_+\)，另一个落在 \(H_-\)）。于是只需证明集合 \(-F\cap(P'+W'_{>0}-2a)\) 与 \(F\cap(P'+W'_{\le 0})\) 都落在 \(A\cap(P+W)\) 中。它们落在 \(A\) 中是显然的，因为 \(A\) 同时含 \(F\) 与 \(-F\)。又注意到 \((P'+W'_{>0}-2a)\subseteq -(P'+W'_{\le 0})\)，因为 \(P'\) 关于 \(a\) 对称。于是只剩证明 \(F\cap(P'+W'_{\le 0})\subseteq P+W\)。但由于 \(F=2a-F\) 落在 \(H_+\)，\(P'\) 的角点落在 \(F\) 内，而 \(W\) 落在 \(H\) 中，我们看到 \(F\) 与 \(P'+W\) 都落在 \(H\) 与 \(2a+H\) 之间的薄板里。从而 \(F\cap(P'+W'_{\le 0})\) 落在集合 \(P-\{ta:0\le t\le 2\}+W=P+W\) 中，结论得证。♦

证明. 由练习 2.3.14，可取对称子集，使其 \(\sigma[F]\le K^2\)。然后对它应用引理 5.18，取 \(W=\{0\}\)、\(r=d\) 即可。♦