5.1　和集的最小规模与 e-变换Minimal size of sum sets and the e-transform

讲解（如何自证引理 5.2）. 把每个论断拆开看就一目了然。

1. (5.1) 为何成立. 取 \(A^{(e)}=A\cup(B+e)\) 与 \(B^{(e)}=B\cap(A-e)\) 中的元素相加。\(B^{(e)}\subseteq B\)，而 \(A^{(e)}\) 拆成两块：\(A\) 这块加上 \(B^{(e)}\) 当然落在 \(A+B\) 里；\(B+e\) 这块加上 \(B^{(e)}\subseteq A-e\) 这块，得到的元素形如 \((b+e)+b'\)，其中 \(b'\in A-e\) 即 \(b'+e\in A\)，于是 \((b+e)+b'=b+(b'+e)\in B+A=A+B\)。两块都落在 \(A+B\) 内，故 (5.1) 成立。
2. (5.2) 为何成立. 这是 (5.3) 取 \(E=Z\) 的特例：此时 \((E-e)\setminus E\) 与 \(E\setminus(E-e)\) 都是空集，于是 (5.3) 退化为 \(|A^{(e)}|+|B^{(e)}|=|A|+|B|\)。直观上：从 \(B\) 里拿走 \(B\setminus(A-e)\) 这些元素（数目记为 \(t\)），\(B^{(e)}\) 比 \(B\) 少 \(t\) 个；这 \(t\) 个元素平移 \(e\) 后并入 \(A\)，且它们原先不在 \(A\) 里（这正是“不在 \(A-e\)”的含义），所以 \(A^{(e)}\) 比 \(A\) 恰好多 \(t\) 个。一减一加，总数不变。
3. (5.4) 与等号. 上一条说明 \(|A^{(e)}|=|A|+t\)、\(|B^{(e)}|=|B|-t\)，其中 \(t=|B\setminus(A-e)|\ge0\)，立得 \(|A^{(e)}|\ge|A|\) 且 \(|B^{(e)}|\le|B|\)。两式取等号都等价于 \(t=0\)，即 \(B\setminus(A-e)=\varnothing\)，亦即 \(B\subseteq A-e\)，亦即 \(B+e\subseteq A\)。

♦

证明. 取 \(e:=\max(A)-\min(B)\)；则我们看到 \(B^{(e)}\) 是单点集 \(\{\min(B)\}\)，因此由 (5.2) 有 \(|A^{(e)}|=|A|+|B|-1\)，从而 \(|A^{(e)}+B^{(e)}|=|A|+|B|-1\)。结论随即由 (5.1) 得到。♦

讲解（为什么 \(B^{(e)}\) 恰好缩成一个点）. 取 \(e=\max(A)-\min(B)\)。要算 \(B^{(e)}=B\cap(A-e)\)，就要看 \(B\) 里哪些 \(b\) 满足 \(b\in A-e\)，即 \(b+e\in A\)。

1. 取 \(b=\min(B)\)：\(b+e=\min(B)+\max(A)-\min(B)=\max(A)\in A\)。所以 \(\min(B)\in B^{(e)}\)。
2. 取任何更大的 \(b>\min(B)\)：则 \(b+e>\min(B)+e=\max(A)\)，即 \(b+e\) 超过了 \(A\) 的最大元，必不在 \(A\) 内，故这个 \(b\notin B^{(e)}\)。
3. 于是 \(B^{(e)}=\{\min(B)\}\)，只剩一个元素。由 (5.2)，\(|A^{(e)}|=|A|+|B|-1\)。而 \(A^{(e)}+B^{(e)}=A^{(e)}+\{\min(B)\}\) 只是把 \(A^{(e)}\) 整体平移，故 \(|A^{(e)}+B^{(e)}|=|A^{(e)}|=|A|+|B|-1\)。再用 (5.1) 即 \(|A+B|\ge|A|+|B|-1\)。

证明. 我们对 \(|B|\) 的大小作归纳；于是假设结论对所有更小的集合 \(B\) 已经证明（\(|B|=1\) 的情形是平凡的）。假设我们能找到一个元素 \(e\in A-B\)，使得 \(B\) 的 e-变换 \(B^{(e)}\) 严格小于 \(B\)。那么由归纳假设有 \(|A^{(e)}+B^{(e)}|\ge\min(|A^{(e)}|+|B^{(e)}|-1,\ p)\)，结论便由 (5.1) 和 (5.2) 得到。

因此我们可以假设 \(B\) 的任何 e-变换都不严格小于 \(B\)。利用引理 5.2（即 (5.4) 的等号情形），这意味着对所有 \(e\in A-B\) 都有 \(B+e\subseteq A\)，于是 \[A-B+B\subseteq A.\] 利用命题 2.2，我们由此得知 \(B\) 包含在 \(\mathbb{Z}_p\) 的某子群 \(G\) 的一个陪集之内，而 \(A\) 是 \(G\) 的若干陪集之并。但由于 \(p\) 是素数，可用的子群 \(G\) 只有平凡群 \(\{0\}\) 与整个群 \(\mathbb{Z}_p\)。无论哪种情形，Cauchy–Davenport 不等式都易于验证。♦

讲解（这条归纳的逻辑骨架）.

1. 归纳基础. \(|B|=1\) 时，\(B=\{b\}\)，\(A+B\) 只是 \(A\) 平移 \(b\)，故 \(|A+B|=|A|=|A|+|B|-1\)。✓
2. 能缩则缩. 若存在某个 \(e\) 让 \(B^{(e)}\) 真正变小，就把问题换成 \((A^{(e)},B^{(e)})\)。因为 \(|B^{(e)}|<|B|\)，归纳假设可用；又因为 (5.2) 总规模不变、(5.1) 和集不增，所证下界对原来的 \(A+B\) 同样成立。
3. 缩不动的情形. 若所有 \(e\) 都让 \(B^{(e)}=B\)（缩不动），由 (5.4) 等号知 \(B+e\subseteq A\) 对每个 \(e\in A-B\) 成立，合起来就是 \(A-B+B\subseteq A\)。这是一个很强的“自我封闭”条件，命题 2.2 把它翻译为：\(B\) 困在一个子群 \(G\) 的单个陪集里。
4. 素数收尾. \(\mathbb{Z}_p\) 里只有 \(G=\{0\}\) 或 \(G=\mathbb{Z}_p\)。若 \(G=\{0\}\)，则 \(B\) 是单点，回到基础情形；若 \(G=\mathbb{Z}_p\)，则 \(A=\mathbb{Z}_p\)，于是 \(A+B=\mathbb{Z}_p\)，\(|A+B|=p\)，下界中的 \(\min(\cdot,p)\) 由 \(p\) 这一支给出。✓

证明. 我们使用一个三重归纳。首先，我们对 \(|A+B|\) 向上归纳，即假设结论对所有 \(|A+B|\) 值更小的对 \(A,B\) 已成立。其次，固定 \(|A+B|\)，对 \(|A|+|B|\)（它被 \(2|A+B|\) 从上方界住）向下归纳，假设结论对更大的 \(|A|+|B|\) 值成立。最后，固定 \(|A+B|\) 与 \(|A|+|B|\)，对 \(|B|\) 向上归纳，假设结论对更小的 \(|B|\) 值成立。这一相当复杂的归纳，是被我们在这个（出人意料地精细的）论证中对 \(A\) 与 \(B\) 所用的不同约化方式所迫使的。

令 \(G:=\mathrm{Sym}_1(A+B)\)。若 \(G\) 不是平凡群 \(\{0\}\)，则我们可以从 \(Z\) 过渡到商群 \(Z/G\)，把 \(A,B\) 换成 \((A+G)/G\) 与 \((B+G)/G\)，从而减小 \(|A+B|\)，结论便由第一重归纳假设得到。因此我们可取 \(\mathrm{Sym}_1(A+B)=\{0\}\)。此时我们的任务化为证明 \(|A+B|\ge|A|+|B|-1\)。

假设对所有 \(e\in A-B\) 都有 \(B^{(e)}=B\)。那么如前所述有 \(A-B+B\subseteq A\)，于是由命题 2.2，\(B\) 含于某群 \(H\) 的一个陪集，\(A\) 是 \(H\) 的若干陪集之并。于是 \(\mathrm{Sym}_1(A+B)\) 包含 \(H\)，从而 \(H=\{0\}\)，这就推出 \(|B|=1\)，结论易于验证。

剩下要考虑的情形是：至少存在一个 \(e\in A-B\) 使 \(B^{(e)}\) 严格小于 \(B\)。在所有这样的 \(e\) 中，我们选取使 \(|B^{(e)}|\) 最大的那个。必要时把 \(B\)（及 \(B^{(e)}\)）平移 \(e\)，可将 \(e\) 规范化为 \(e=0\)；于是 \(A^{(0)}=A\cup B\)，\(B^{(0)}=A\cap B\)。由 (5.3) 注意到 \(|A^{(0)}+B^{(0)}|\le|A+B|\)，\(|A^{(0)}|+|B^{(0)}|=|A|+|B|\)，且 \(|B^{(0)}|<|B|\)。于是由归纳假设有 \[|A^{(0)}+B^{(0)}|\ge|A^{(0)}+H|+|B^{(0)}+H|-|H|, \tag{5.5}\] 其中 \(H:=\mathrm{Sym}_1(A^{(0)}+B^{(0)})\)。令 \(C:=(A\cap B)+H\)。由 \(H\) 以及 \(A^{(0)},B^{(0)}\) 的定义，我们看到 \(A+C\) 与 \(B+C\) 含于 \(A^{(0)}+B^{(0)}\)，从而含于 \(A+B\)。故我们可以把 \(A,B\) 换成 \(A\cup C,B\cup C\) 而不影响 \(A+B\) 或 \(\mathrm{Sym}(A+B)\)。因此可设 \(C\) 同时含于 \(A\ 与\ B\)——否则 \(|A+C|+|B+C|\) 将超过 \(|A|+|B|\)，结论便由第二重归纳假设得到。特别地，我们看到 \(A\cap B=C\) 是 \(H\) 的非零个陪集之并。

假设 \(A^{(0)}+B^{(0)}\) 等于 \(A+B\)；则 \(H=\mathrm{Sym}(A+B)=\{0\}\)，结论由 (5.5) 与 (5.3) 得到。因此可设 \(A^{(0)}+B^{(0)}\) 严格小于 \(A+B\)。

令 \(A'\) 记那些 \(a\in A\)，使得存在 \(b\in B\) 满足 \(a+b\in A^{(0)}+B^{(0)}\) 的补——更准确地，使 \(a+b\notin A^{(0)}+B^{(0)}\) 的 \(a\)。由前一假设，\(A'\) 非空；又注意对所有 \(a\in A'\)，\(a\)（从而 \(a+H\)）与 \(C=B^{(0)}\) 不相交。设 \(b\) 使 \(a+b\notin A^{(0)}+B^{(0)}\)：则 \(a+b+H\) 与 \(A^{(0)}+B^{(0)}\) 不相交（由 \(H\) 的定义）；由于 \(b\in A^{(0)}\)，我们推得 \(a+H\) 与 \(A\cap B\) 不相交。又有 \(((a+H)\cap A)+b\) 与 \(A^{(0)}+B^{(0)}\) 不相交且含于 \(A+B\)；于是 \[|A+B|\ge|A^{(0)}+B^{(0)}|+|(a+H)\cap A|.\] 由于 \(A\cap B\) 与 \(a+H\) 不相交，有 \[\begin{aligned}|A^{(0)}+H|&\ge|A^{(0)}|+|(A^{(0)}+H\setminus A^{(0)})\cap(a+H)|\\&=|A^{(0)}|+|H|-|(a+H)\cap A|-|(a+H)\cap B|,\end{aligned}\] 从而由 (5.5) 与 (5.3) \[|A+B|\ge|A|+|B|-|(a+H)\cap B|.\] 于是除非对所有 \(a\in A'\) 都有 \(|(a+H)\cap B|>1\)，否则我们就已完成证明；下面假设这一情况成立。

对每个 \(a\in A'\)，令 \(A_a:=(a+H)\cap A\)，\(B_a:=(a+H)\cap B\)。假设我们能找到 \(a,a'\in A'\) 使得 \(A_{a'}-B_{a'}+B_a\subseteq A_a\)。那么我们能找到 \(e\in A_a-B_a\subseteq H\) 使 \(B_{a'}+e\subseteq A_a\)。这表明 \(B\) 不含于 \(A-e\)，从而 \(B^{(e)}\) 严格小于 \(B\)，并且它既含 \(B^{(0)}=C\)，又含非空集合 \(B_{a'}\cap(A_a-e)\)（后者位于 \(a+H\) 中，因而与 \(C\) 不相交），故 \(B^{(e)}\) 严格大于 \(B^{(0)}\)。这与 \(|B^{(0)}|\) 的最大性矛盾。因此必有 \(A_{a'}-B_{a'}+B_a\subseteq A_a\) 对所有 \(a,a'\in A'\) 成立。这尤其推出 \(|A_a|=|A_{a'}|\) 对所有 \(a,a'\in A'\) 成立，由命题 2.2，这意味着各 \(B_a\) 都含于某固定群 \(K\) 的一个陪集，而各 \(A_a\) 是 \(K\) 的若干陪集之并（特别地 \(K\) 是 \(H\) 的子群）。由于我们假设了 \(|B_a|>1\) 对所有 \(a\in A'\) 成立，故 \(|K|>1\)。又因为对每个 \(a\)，\(A_a+B\) 是 \(K\) 的陪集之并，而 \(A^{(0)}+B^{(0)}\) 是 \(H\)（从而也是 \(K\)）的陪集之并，我们推得 \(A+B\) 是 \(K\) 的陪集之并。但这与假设 \(\mathrm{Sym}_1(A+B)=\{0\}\) 矛盾，证毕。♦

证明. 我们只证明第三条蕴含第五条；其余各条类似或平凡，留作习题。由 Kneser 定理有 \[\tfrac32|A|>|A+B|\ge|A|+|B|-|\mathrm{Sym}_1(A+B)|\ge 2|A|-|\mathrm{Sym}_1(A+B)|;\] 因此若令 \(G:=\mathrm{Sym}_1(A+B)\)，则 \(|G|>|A|/2\)。由于 \(|A+B|<\tfrac32|A|\) 且 \(A+B\) 是其对称群 \(G\) 的陪集之并，我们看到 \(A+B\) 等于 \(G\) 中至多两个陪集之并，且 \(|G|<\tfrac32|A|\)。

先假设 \(A+B\) 是 \(G\) 的两个陪集之并。则 \(\tfrac32|B|\ge\tfrac32|A|>|A+B|=2|G|\)，这推出 \(A\) 与 \(B\) 都不能含于 \(G\) 的单个陪集。但这再次与 Kneser 定理矛盾。因此 \(A+B\) 是 \(G\) 的单个陪集，这推出 \(A\) 也含于 \(G\) 的一个陪集，结论得证。♦

证明. 对 \(N=0\) 结论易于验证，故归纳地假设 \(N\ge1\) 且结论已对所有更小的 \(N\) 证明。特别地，由这个归纳假设我们已有 \[|(A+B)\cap[1,n]|\ge\alpha n\quad\text{对所有}\ 0\le n1\) 且结论已对所有更小的 \(B\) 证明。不失一般性，可取 \(A\subseteq[0,N]\) 与 \(B\subseteq[0,N]\)，因为 \(A,B\) 中多出来的元素显然无害。

鉴于引理 5.2 与归纳假设，只需找到一个整数 \(e\in A\subseteq A-B\)，使得 \(|B^{(e)}|<|B|\) 且 \[|A^{(e)}\cap[1,n]|+|B^{(e)}\cap[1,n]|\ge\alpha n\quad\text{对所有}\ 1\le n\le N. \tag{5.7}\] 注意约束 \(e\in A\) 将保证 \(A^{(e)}\) 与 \(B^{(e)}\) 都含 \(0\)。

情形一：\(B\) 不含于 \(A\)。 此时我们可以简单地取 \(e=0\in A\)，因为 \(B_0=A\cap B\) 将严格小于 \(B\)，并且由 (5.3) 与 (5.6) 有 \[|A_0\cap[1,n]|+|B_0\cap[1,n]|=|A\cap[1,n]|+|B\cap[1,n]|\ge\alpha n,\] 正是所需。

情形二（较难）：\(B\) 含于 \(A\)。 此时取 \[e:=\min\{a\in A: a+B\subseteq A\}.\] 注意右边的集合非空，因为 \(A\) 的最大元显然属于它。我们有 \(e\in A\)；由假设，\(e\) 为正，且由构造有 \[(A\cap[0,e))+B\subseteq A. \tag{5.8}\] 又由引理 5.2，\(B^{(e)}\) 严格小于 \(B\)。于是剩下要证明 (5.7)。由 (5.3)（并注意 \(B\setminus(A-e)\) 与 \([-e+1,0]\) 不相交）有 \[\begin{aligned}|A^{(e)}\cap[1,n]|+|B^{(e)}\cap[1,n]|&=|A\cap[1,n]|+|B\cap[1,n]|-|(B\setminus(A-e))\cap[n-e+1,n]|\\&\ge|A\cap[1,n]|+|B\cap[1,n-e]|.\end{aligned}\] 若 \(B\cap[n-e+1,n]\) 为空，则结论 (5.7) 即由 (5.6) 得到，故可设 \(B\cap[n-e+1,n]\) 非空。设 \(b\) 为 \(B\cap[n-e+1,n]\) 中的最小元，则 \(b\in B\subseteq A\)，又由 \(e\in A\subseteq[0,N]\) 知 \(n-b\le e-1♦

证明.“当”的部分是显然的，故我们证明“仅当”的部分。令 \(e:=\max(A)-\min(B)\)。由引理 5.3 的证明，我们必有 \[A+B=A^{(e)}+B^{(e)}=(A\cup(B+e))+\min(B)=(A+\min(B))\cup(B+\max(A)).\] 现令 \(\min(B)+v\) 为 \(B\) 中仅次于 \(\min(B)\) 的第二小元素；则 \(v>0\)，且对任意 \(a\in A\setminus\{\max(A)\}\) 有 \[\begin{aligned}a+\min(B)+v&\in A+B=(A+\min(B))\cup(B+\max(A))\\&=(A+\min(B))\cup((B\setminus\{\min(B)\})+\max(A)).\end{aligned}\] 注意由于 \(a<\max(A)\) 且 \(\min(B)+v\) 是 \(B\setminus\{\min(B)\}\) 的最小值，\(a+\min(B)+v\) 不可能落在 \((B\setminus\{\min(B)\})+\max(A)\) 中。我们由此推得 \[a+v\in A\quad\text{对所有}\ a\in A\setminus\{\max(A)\}.\] 由此易见 \(A\) 是步长为 \(v\) 的等差级数。特别地，\(\max(A)-v\) 是 \(A\) 中仅次于 \(\max(A)\) 的第二大值；改用前面的论证，我们看到 \(B\) 也是步长为 \(v\) 的等差级数，证毕。♦

证明.“当”的部分容易，故证“仅当”。我们首先在 \(A\) 是等差级数 \(\{a,a+v,\dots,a+nv\}\)（\(n\ge1\)）的情形下证明此断言。由 Cauchy–Davenport， \[\begin{aligned}|B|+n&=|A|+|B|-1=|A+B|\\&=|\{a,a+v,\dots,a+(n-1)v\}+\{0,v\}+B|\\&\ge|B+\{0,v\}|+n-1,\end{aligned}\] 从而（再次由 Cauchy–Davenport）有 \(|B+\{0,v\}|=|B|+1\)。于是 \(B\) 与 \(B+v\) 至多相差一个元素，这推出 \(B\) 是步长为 \(v\) 的等差级数（见习题 3.2.7）。由对称性，当 \(A\) 与 \(B\) 的角色互换时同样成立。

现在我们用一个对偶技巧来证明如下变体：若和集 \(A+B\) 是一个真等差级数，且 \(|A+B|=|A|+|B|-1\)，则 \(A\) 与 \(B\) 也是等差级数，且三者步长相同。为此，令 \(C:=-(\mathbb{Z}_p\setminus(A+B))\)。则 \(C\) 也是与 \(A+B\) 同步长的等差级数，基数 \(|C|=p-|A+B|=p+1-|A|-|B|\ge2\)。又注意 \(C+B\subseteq-(\mathbb{Z}_p\setminus A)\)，因为若 \(-A\) 中某元素 \(-a\) 落在 \(C+B\) 里，则 \(C\) 会与 \(-a-B\subset-(A+B)\) 相交，矛盾。于是 \(|C+B|\le p-|A|=|C|+|B|-1\)，从而由 Cauchy–Davenport 有 \(|C+B|=|C|+|B|-1\)。既然 \(C\) 是长度至少为 \(2\) 的等差级数，由前述讨论知 \(B\) 也是，且与 \(C\) 同步长。对 \(A\) 同理。

综上，我们已在 \(A,B,A+B\) 三者之一为等差级数的情形下证明了 Vosper 定理。现在处理一般情形。我们对 \(B\) 的大小作归纳。若 \(|B|=2\)，则 \(B\) 已是等差级数，结论已证。现设 \(|B|>2\) 且结论已对更小的 \(B\) 证明。

先假设我们能找到 \(e\in A-B\)，使 \(B\) 的 e-变换 \(B^{(e)}\) 的大小满足 \(1<|B^{(e)}|<|B|\)。由假设 \(|A+B|=|A|+|B|-1\)，结合 (5.1)、(5.2) 与 Cauchy–Davenport 不等式，我们看到必有 \(A^{(e)}+B^{(e)}=A+B\) 且 \[|A^{(e)}+B^{(e)}|=|A^{(e)}|+|B^{(e)}|-1.\] 利用归纳假设，我们由此得知 \(A^{(e)}\) 与 \(B^{(e)}\) 是同步长 \(v\) 的等差级数，从而 \(A+B=A^{(e)}+B^{(e)}\) 也是等差级数，结论便由前述讨论得到。

剩下唯一的情形是：对所有 \(e\in A-B\) 都有 \(|B^{(e)}|=1\) 或 \(|B^{(e)}|=|B|\)。但若 \(E\subseteq A-B\) 记所有满足 \(|B^{(e)}|=|B|\) 的 \(e\)，则由引理 5.2 有 \(B+E\subseteq A\)，从而由 Cauchy–Davenport 有 \(|E|\le|A|-|B|+1\)。又由 Cauchy–Davenport 有 \(|A-B|\ge|A|+|B|-1\)，于是我们看到至少有 \(2|B|-2\) 个 \(e\) 满足 \(|B^{(e)}|=1\)。由于 \(B^{(e)}\) 是 \(B\) 的单点子集，由鸽巢原理我们看到存在 \(e,e'\in A-B\) 与 \(b\in B\) 使得 \(B^{(e)}=B^{(e')}=\{b\}\)。由假设 \(|A+B|=|A|+|B|-1\)，结合 (5.1)、(5.2) 我们看到 \[A+B=A^{(e)}+b=A^{(e')}+b,\] 从而 \[A\cup(B+e)=A\cup(B+e').\] 由于 \(A\) 仅在 \(b+e\) 处与 \(B+e\) 相交，仅在 \(b+e'\) 处与 \(B+e'\) 相交，我们由此看到 \(B+e\) 与 \(B+e'\) 至多相差一个元素。但这迫使 \(B\) 成为一个等差级数（步长为 \(e-e'\)），结论得证。♦

证明. 我们把 \(2A\) 按其在 \(\mathbb{Z}_N\) 中的像分块（利用引理 5.3 以及观察 \(\sum_{x\in\varphi_N(A)}\mu_x=|A|\)）： \[\begin{aligned} |2A|&=\sum_{x\in\varphi_N(2A)}\big|2A\cap\varphi_N^{-1}(\{x\})\big|\\ &\ge\sum_{x\in\varphi_N(2A)}\ \sup_{\substack{y,z\in\varphi_N(A)\\ y+z=x}}\Big(\big|A\cap\varphi_N^{-1}(\{y\})\big|+\big|A\cap\varphi_N^{-1}(\{z\})\big|-1\Big)\\ &\ge\sum_{x\in\varphi_N(2A)}\ \sup_{\substack{y,z\in\varphi_N(A)\\ y+z=x}}\big(\mu_y+\mu_z\big)-|\varphi_N(2A)|. \end{aligned}\] 对 \(x\in\varphi_N(A)\) 这部分，分解 \(x=0+x\) 给出 \(\mu_0+\mu_x\)；对 \(x\in\varphi_N(2A)\setminus\varphi_N(A)\) 这部分，则有 \(\sup\ge m+m=2m\)。于是 \[\begin{aligned} |2A|&\ge\sum_{x\in\varphi_N(A)}(\mu_0+\mu_x)+\sum_{x\in\varphi_N(2A)\setminus\varphi_N(A)}2m-|\varphi_N(2A)|\\ &=\mu_0|\varphi_N(A)|+|A|+(|\varphi_N(2A)|-|\varphi_N(A)|)2m-|\varphi_N(2A)|, \end{aligned}\] 正是所需（这里用到 \(2\varphi_N(A)=\varphi_N(2A)\)）。♦

证明. 我们采用 [233] 中的论证。平移 \(A\) 后可设 \(\min(A)=0\)。又可设集合 \(A\) 没有大于 \(1\) 的公因子 \(d\)，否则可用 \(\tfrac1d\cdot A\) 替换 \(A\)。我们假设 \(|A|\ge3\)，因为 \(|A|=1,2\) 的情形可直接验证。

记 \(N:=\max(A)\)，于是 \(A\subseteq[0,N]\) 且 \(0,N\in A\)。只需证明 \(N\le|2A|-|A|\)。反设 \(N>|2A|-|A|\)。现在我们运用引理 5.10。注意此时 \(\mu_0=2\)（因 \(\varphi_N(0)=\varphi_N(N)=0\)，故 \(0\) 处至少压着 \(0\) 与 \(N\) 两个元素）且 \(m=1\)，于是 \[|2A|\ge|A|+|2\varphi_N(A)|. \tag{5.9}\] 由于我们假设 \(N>|2A|-|A|\)，我们推得 \[|2\varphi_N(A)|
注意 \(\varphi_N(A)\) 含 \(0\)，但不可能整个落在 \(H\) 之内，否则意味着 \(A\) 有公因子 \(h\)，与假设矛盾。因此我们知道 \(\varphi_N(A)\) 至少含 \(H\) 的两个陪集，等价地 \(|\varphi_h(A)|\ge2\)。

现在我们再次运用引理 5.10，但把 \(N\) 换成 \(h\)。由 (5.11)，若 \(x+H\subseteq\mathbb{Z}_N\) 是 \(H\) 的任意非平凡陪集，则 \(H\cup(x+H)\) 与 \(\varphi_N(A)\) 相交于至少 \(2|H|-k\) 个点；由于 \(\varphi_N(0)=\varphi_N(N)=0\in H\cup(x+H)\)，这推出 \(\varphi_N^{-1}(H\cup(x+H))=\varphi_h^{-1}(\{0,x\bmod h\})\) 与 \(A\) 相交于至少 \(2|H|-k+1\) 个点。换言之 \[\mu_0+m\ge2|H|-k+1.\] 类似的论证给出 \[m\ge|H|-k.\] 但由于 \(H\) 是 \(2\varphi_N(A)\) 的对称群，我们看到 \(2\varphi_h(A)\) 具有平凡的对称群；进而由 (5.10) 知 \(|2\varphi_h(A)|♦