2.8　初等和积估计Elementary sum-product estimates

证明. 我们有 \(|A+x\cdot A|=|A|^{2}\) 当且仅当映射 \((a,b)\mapsto a+xb\) 在 \(A\times A\) 上是单射。这又当且仅当对一切相异的 \((a,b),(c,d)\in A\times A\) 都有 \(a+xb\ne c+xd\)；经过一点代数变形，这等价于断言 \(x\notin Q[A]\)。♦

证明. 由引理 2.50 及假设，我们看出 \(Q[A]\cdot Q[A]\subseteq Q[A]\) 且 \(Q[A]+Q[A]\subseteq Q[A]\)。（理由：若某 \(y\in Q[A]\cdot Q[A]\) 却 \(y\notin Q[A]\)，则 \(|A+y\cdot A|=|A|^2\)；但 \(A+y\cdot A\subseteq A+Q[A]\cdot Q[A]\cdot A\)，于是后者 \(\ge|A|^2\)，与假设矛盾。第二个包含同理。）特别地 \(Q[A]^{\times}\cdot Q[A]^{\times}=Q[A]^{\times}\)。由于 \(Q[A]\) 有限且含 \(0,1\)，由命题 2.7 知 \(Q[A]\) 是一个加法群；类似地，由该命题的乘法版本知 \(Q[A]^{\times}\) 是一个乘法群。结论得证。♦

证明. 我们采用 [41] 中的论证。可设 \(|A|>10K\)（例如），否则结论平凡。考虑 \(A\) 的诸伸缩 \(\{a\cdot A:a\in A\}\)。由于 \(a\in Z^{*}\)，\(a\cdot A\) 与 \(A\) 有相同的基数。特别地有 \[\sum_{x\in A\cdot A}\sum_{a\in A}\mathbf 1_{a\cdot A}(x)=|A|^{2}.\] 由于 \(|A\cdot A|\le K|A|\)，可应用 Cauchy–Schwarz 不等式得 \[\sum_{x\in A\cdot A}\left(\sum_{a\in A}\mathbf 1_{a\cdot A}(x)\right)^{2}\ge \frac{|A|^{3}}{K}.\] 将其重新整理为 \[\sum_{a,b\in A}\big|(a\cdot A)\cap(b\cdot A)\big|\ge \frac{|A|^{3}}{K}.\] 由鸽笼原理，可找到一个 \(b\in A\) 使得 \[\sum_{a\in A}\big|(a\cdot A)\cap(b\cdot A)\big|\ge \frac{|A|^{2}}{K}.\] 固定这个 \(b\)。令 \(A'\) 为一切满足 \(|(a\cdot A)\cap(b\cdot A)|\ge \dfrac{|A|}{2K}\) 的 \(a\in A\) 之集，则 \[\sum_{a\in A'}\big|(a\cdot A)\cap(b\cdot A)\big|\ge \frac{|A|^{2}}{2K},\] 从而 \(|A'|\ge\dfrac{|A|}{2K}\)。必要时把 \(A'\) 缩小一个元素，可设 \(b\in A'\)。

现在回忆 Ruzsa 距离 \(d(A,B):=\log\dfrac{|A-B|}{|A|^{1/2}|B|^{1/2}}\)，并注意当 \(a\) 不是零因子时 \(d(a\cdot A,a\cdot B)=d(A,B)\)。于是 \(d(A,A)\le 2d(A,-A)=2\log K\)，从而 \[d(a\cdot A,a\cdot A)=d(b\cdot A,b\cdot A)=d(A,A)\le 2\log K\quad\text{对一切 }a\in A'.\] 由于 \((a\cdot A)\cap(b\cdot A)\) 是 \(a\cdot A\) 与 \(b\cdot A\) 的一个大子集，可算得 \[d\big(a\cdot A,\,a\cdot A\cap b\cdot A\big),\ d\big(b\cdot A,\,a\cdot A\cap b\cdot A\big)=O(1+\log K),\] 于是由 Ruzsa 三角不等式 \[d(a\cdot A,\,b\cdot A)=O(1+\log K)\quad\text{对一切 }a\in A'.\tag{2.41}\] 对其作伸缩，得到 \[d(a_1a_2\cdot A,\,ba_2\cdot A),\ d(ba_2\cdot A,\,b^{2}\cdot A)=O(1+\log K)\quad\text{对一切 }a_1,a_2\in A',\] 从而再由 Ruzsa 三角不等式 \[d(a_1a_2\cdot A,\,b^{2}\cdot A)=O(1+\log K)\quad\text{对一切 }a_1,a_2\in A'.\tag{2.42}\]

为继续推进，我们需要把 \(A'\) 中的元素“求逆”。对任意 \(a\in A'\)，令 \(\hat a:=\prod_{a'\in A'\setminus\{a\}}a'\in Z^{*}\)。把 (2.41)（其中 \(a\) 换成 \(a_3\)）用 \(a_1a_2\prod_{a'\in A'\setminus\{a_3,b\}}a'\) 作伸缩（\(a_1,a_2,a_3\in A'\)），得到 \[d(a_1a_2\hat b\cdot A,\,a_1a_2\hat a_3\cdot A)=O(1+\log K)\quad\text{对一切 }a_1,a_2,a_3\in A'.\] 另一方面，对 (2.42) 作伸缩有 \[d(a_1a_2\hat b\cdot A,\,b^{2}\hat b\cdot A)=O(1+\log K)\quad\text{对一切 }a_1,a_2,a_3\in A'.\] 应用 Ruzsa 三角不等式，于是 \[d(a_1a_2\hat a_3\cdot A,\,a_1'a_2'\hat a_3'\cdot A)=O(1+\log K)\quad\text{对一切 }a_1,a_2,a_3,a_1',a_2',a_3'\in A',\] 从而 \[\big|a_1a_2\hat a_3\cdot A-a_1'a_2'\hat a_3'\cdot A\big|=O(K^{O(1)})|A|.\] 因此 \[\sum_{x,y\in A'\cdot A'\cdot \hat A'}\big|x\cdot A-y\cdot A\big|=O(K^{O(1)})\,|A|\,|A'\cdot A'\cdot \hat A'|^{2},\] 其中 \(\hat A':=\{\hat a:a\in A'\}\)。但由于 \(|A\cdot A|\le K|A|\) 且 \(|A'|\ge\dfrac{|A|}{2K}-1\)，由和集估计的乘法版本（在由可消去交换幺半群 \(Z^{*}\) 生成的形式乘法群中工作）得 \(|A'\cdot A'\cdot \hat A'|=O(K^{O(1)}|A|)\)。于是 \[\sum_{x,y\in A'\cdot A'\cdot \hat A'}\big|x\cdot A-y\cdot A\big|\le O(K^{O(1)}|A'|^{3}).\] 把左边改写为 \[\sum_{z\in Z}\big|\{(x,y):\exists\,a,b\in A\ \text{使}\ z=xa-yb\}\big|.\] 记 \(\omega:=\prod_{a\in A'}a\)，并注意：每当 \(a_1,a_2,a_3,a_4\in A'\) 时，数 \(\omega(a_1a_2-a_3a_4)\) 至少有 \(|A'|^{2}\) 个形如 \(xa-yb\)（\(x,y\in A'\cdot A'\cdot\hat A'\)，\(a,b\in A'\)，且 \((x,y)\) 互异）的表示，这归功于恒等式 \[\omega(a_1a_2-a_3a_4)=(a_1a_2\hat a)\,a-(a_3a_4\hat b)\,b.\] （因为 \(\hat a\cdot a=\omega\)，故 \((a_1a_2\hat a)a=a_1a_2\omega\)，同理另一项。让 \((a,b)\) 跑遍 \(A'\times A'\)，便得 \(|A'|^2\) 个表示。）于是 \[\big|\omega\cdot(A'\cdot A'-A'\cdot A')\big|=O(K^{O(1)}|A'|),\] 而由于 \(\omega\in Z^{*}\)，结论得证。♦

证明. 我们只证正向蕴含（(i)\(\Rightarrow\)(ii)），容易的反向蕴含留作习题 2.8.2。把 \(C_1K^{C_1}\) 重新记作 \(K\)，于是可设 \(|A+A|\le K|A|\) 且 \(|A\cdot A|\le K|A|\)。可设 \(|A|\ge C_0K^{C_0}\)（\(C_0\) 为某大绝对常数），否则结论平凡。也可毫无困难地把 \(0\) 从 \(A\) 中移除，于是可设 \(A\subseteq F^{*}\)。

应用引理 2.53 与引理 2.54，可找到 \(A\) 的子集 \(A'\)，满足 \(|A'|=\Omega(K^{-O(1)}|A|)\) 且对一切 \(k\ge 1\) 有 \(|(A')^{k}-(A')^{k}|=O(K)^{O(k)}|A'|\)。由推论 2.23 这蕴含 \[|n(A')^{k}-m(A')^{k}|\le O(K)^{O_{k,n,m}(1)}|A'|\quad\text{对一切 }n,k,m\ge 1.\tag{2.43}\] 必要时用一个非零因子对 \(A'\) 作伸缩，可设 \(1\in A'\)（注意定理的假设与结论在此类伸缩下不变）。现在可把 \(0\) 加回到 \(A\) 与 \(A'\) 中而不影响 (2.43)。

现在应用推论 2.52。令 \(D:=(A'-A')\setminus\{0\}\) 与 \(G:=Q[A']=(A'-A')/D\)。利用通分（最低公分母），观察到 \[A'+G\cdot G\cdot A'\subseteq\frac{A'\cdot D\cdot D-(A'-A')\cdot(A'-A')\cdot A'}{D^{2}}\subseteq\frac{4(A')^{3}-4(A')^{3}}{D^{2}}.\] 另一方面，由 (2.43) 有 \(|(4(A')^{3}-4(A')^{3})\cdot D^{2}|=O(K^{O(1)}|A'|)\)，故由推论 2.12 的乘法版本得 \[|A'+G\cdot G\cdot A'|=O(K^{O(1)}|A'|)<|A'|^{2}\] （只要 \(C_0\) 足够大）。类似的论证给出 \(|A'+(G+G)\cdot A'|=O(K^{O(1)}|A'|)<|A'|^{2}\)。应用推论 2.52，便知 \(G\) 实际上是一个域。

现取 \(A'\) 的一个非零元 \(x\)，以及 \(A'\) 的一个元素 \(y\)。则对一切 \(a\in A'\) 有 \((a-y)/x\in Q[A']=G\)，于是 \[A'\subseteq x\cdot G+y.\] 从而 \[x\cdot G+y=A'+x\cdot G\subseteq A'+A'\cdot Q[A'],\] 进而 \[(x\cdot G+y)^{2}\subseteq (A'+A'\cdot Q[A'])^{2}.\] 但与前面一样，用 (2.43) 与推论 2.12 的论证给出 \(|(A'+A'\cdot Q[A'])^{2}|=O(K^{O(1)}|A'|)\le O(K^{O(1)}|G|)\)。直接计算表明，除非 \(y\in x\cdot G\)，否则 \(|(x\cdot G+y)^{2}|\ge|G|^{2}\)。于是（若 \(C_0\) 足够大）可取 \(y\in x\cdot G\)。因为 \(A'\) 含 \(1\)，故得 \(A'\subseteq G\)。

由于 \(|A+A'|\le K|A|=O(K^{O(1)}|A'|)\)，可应用 Ruzsa 覆盖引理（引理 2.14），用 \(O(K^{O(1)})\) 个 \(A'-A'\) 的平移覆盖 \(A\)，从而用 \(O(K^{O(1)})\) 个 \(G\) 的平移覆盖 \(A\)。用此引理的乘法版本（必要时暂时把不可逆的 \(0\) 从 \(A\) 中移走）的类似论证，可用 \(O(K^{C})\) 个 \(G\) 的伸缩覆盖 \(A\)。另一方面，当 \(x\ne 1\) 时有 \(|(G\cdot x)\cap(G+y)|\le 1\)。于是 \(|A\setminus G|=O(K^{O(1)})\)，结论得证。♦

证明. 由习题 2.3.24 的乘法版本，可找到 \(H'\subset H\)，满足 \(|H'|\ge\dfrac{1}{2K}|H|\)，以及 \(h_0\in H'\)，使得对一切 \(h\in H'\) 有 \(|(h\cdot H)\cap(h_0\cdot H)|\ge\dfrac{1}{2K}|H|\)。经伸缩可标准化 \(h_0=1\)。由加法不扩张性质得 \[|2kH|\le L\,|k((h\cdot H)\cap H)|\le L\,|A_h|\quad\text{对一切 }h\in H',\] 其中 \(A_h:=k(h\cdot H)\cap kH\)。由于 \[|kH+A_h|\le|2kH|;\qquad |k(h\cdot H)+A_h|\le|2k(h\cdot H)|=|2kH|,\] 我们得到 Ruzsa 距离估计 \(d(kH,-A_h),\ d(k(h\cdot H),-A_h)\le\log L\)，从而由三角不等式 \[d(kH,\,k(h\cdot H))\le 2\log L.\tag{2.44}\] 现在转而控制某个 \(j\) 的 \(j(H')^{j}\)。首先注意 \[|(H')^{2}|\le|H^{2}|\le K|H|\le 2K^{2}|H'|,\] 故由习题 2.3.10 的乘法类比有 \(|(H')^{2}\cdot(H')^{-1}|=O\!\big(K^{O(1)}|H'|\big)\)。然后可应用习题 1.1.8 的乘法版本，得到一个集合 \(X\subset(H')^{2}\cdot(H')^{-1}\)，其基数 \(|X|=O(K^{O(1)}(1+\log|H|))\)，使得 \((H')^{2}\subset X\cdot H'\)，从而 \((H')^{j}\subset X^{j-1}\cdot H'\)。于是由鸽笼原理可界定 \[|j(H')^{j}|\le|j(X^{j-1}H')|\le|X|^{j(j-1)}\,|x_1\cdot H'+\cdots+x_j\cdot H'|\] 对某 \(x_1,\dots,x_j\in X^{j-1}\) 成立；因此只需证明 \[|x_1\cdot H'+\cdots+x_j\cdot H'|=O_{j}\!\big(L^{O(j^{2})}|kH|\big).\] 由于 \(xH'\) 含于 \(k(xH')\) 的某个平移中，我们有较粗的估计 \[|x_1\cdot H'+\cdots+x_j\cdot H'|\le|jB|,\] 其中 \(B:=k(x_1\cdot H)\cup\cdots\cup k(x_j\cdot H)\)。但诸 \(x_i\) 都是 \(O(j)\) 个来自 \(H'\) 与 \((H')^{-1}\) 的元素之积。反复应用 (2.44) 与三角不等式，得 \[d(k(x_i\cdot H),\,k(x_{i'}\cdot H))\le O(j\log L)\quad\text{对一切 }1\le i,i'\le j,\] 从而 \(d(B,B)\le O(j\log L)+O(\log j)\)。由习题 2.3.10 得 \(|jB|=O_{j}(L^{O(j^{2})}|B|)\)，结论得证。♦

证明. 设 \(\varepsilon'=\varepsilon'(\delta)>0\) 为待定的小数，\(\varepsilon=\varepsilon(\varepsilon',\delta)>0\) 为更小的待定数。反设存在集合 \(A\) 使得 \(E(A,H)\ge p^{-\varepsilon}|A||H|^{2}\)。应用推论 2.36（取 \(L:=p\)，并把其中的 \(\varepsilon\) 换成 \(\varepsilon'\)），可找到（若 \(\varepsilon\) 关于 \(\varepsilon'\) 充分小）\(H\) 的子集 \(H'\)，基数为 \[|H'|=\Omega_{\varepsilon'}\!\big(p^{-\varepsilon'/2}|H|\big),\] 使得对一切 \(k\) 有 \[|kH'|\le|A+kH'|=O_{\varepsilon',k}\!\big(p^{k\varepsilon'/2}|A|\big).\] 由于 \(H\) 是乘法子群，故 \(|H'\cdot H'|\le|H^{2}|=|H|=O_{\varepsilon'}(p^{\varepsilon'/2}|H'|)\)。又因 \(|H|\ge p^{\delta}\)，还可看出（若 \(\varepsilon'\) 关于 \(\delta\) 充分小）对某仅依赖于 \(\delta\) 的 \(A\) 有 \(|H'|^{A}\ge p^{1-\delta/2}\)。于是可应用推论 2.60（把其中的 \(\delta\) 换成 \(\delta/2\)），断定对某依赖于 \(\delta\) 的充分大的 \(k\) 有 \[|kH'|=\Omega_{\varepsilon',\delta}\!\big(p^{\,1-\delta/2-O_{\delta}(\varepsilon')}\big).\] 若 \(\varepsilon'\) 关于 \(\delta\) 充分小，且 \(p\) 充分大，这就给出矛盾。♦