8.3　实数集上的和积问题The sum-product problem in R

证明. 令 \[P=\{(a,b)\mid a\in A+A,\ b\in A\cdot A\};\] \(P\) 是平面上的一个点集，其基数为 \(|P|=|A+A|\,|A\cdot A|\)。 考虑形如 \[\{(x,y):y=a(x-b)\}\] 的直线全体 \(L\)，其中 \(a,b\) 取遍 \(A\) 中的元素。显然 \(L\) 含有 \(|A|^2\) 条直线（每选一对 \((a,b)\) 得到一条）。此外，每一条这样的直线至少包含 \(|A|\) 个 \(P\) 中的点，即点 \((b+c,\ ac)\)，其中 \(c\) 取遍 \(A\)。于是 \[I(P,L)\ \ge\ |A|\cdot|A|^2=|A|^3.\] 对其应用 Szemerédi–Trotter 定理，得 \[|A|^3\ \le\ O\!\left((|A+A|\,|A\cdot A|)^{2/3}(|A|^2)^{2/3}+|A+A|\,|A\cdot A|+|A|^2\right),\] 再由初等代数即得结论。♦

证明. 必要时去掉 \(0\)，可设 \(A\) 中所有元素都非零（去掉一个元素不影响量级）。 为了同时从上、下两方控制 \(A/A\) 中各商的重数，我们需要对 \(A/A\) 作一次二进分解。设 \(2\le d\le|A|\) 为某个稍后再选定的 \(2\) 的幂，令 \(D_d\subseteq A/A\) 为 \[D_d:=\Big\{m\in A/A:\ m=a_1/a_2\ \text{恰有介于 }d\text{ 与 }2d\text{ 之间个数的}(a_1,a_2)\in A\times A\ \text{表示}\Big\}.\] 第一段（直线很多）。 令 \(P:=A\times A\)，令 \(L\) 表示所有斜率 \(m\) 落在 \(D_d\) 中、且至少包含 \(P\) 里一个点的直线 \(\{(x,y):y=mx+b\}\)。注意 \(L\) 是有限的，并且 \(P\) 中每一个点 \(p\) 都关联到 \(L\) 中的 \(|D_d|\) 条直线（过 \(p\) 每个允许的斜率各画一条）。于是由推论 8.5（Szemerédi–Trotter 的一个推论，给出在每点关联固定条数直线时点数的上界）得 \[|A|^2=|P|=O\!\left(\frac{|L|}{|D_d|}+\frac{|L|^2}{|D_d|^3}\right);\] 由于 \(|D_d|\le|A/A|\le|A|^2\)，这给出 \(|L|\) 的一个下界： \[|L|=\Omega\!\left(|A|\,|D_d|^{3/2}\right).\tag{8.4}\] 第二段（每条直线在更大的网格上点很多）。 现在令 \(P':=(A+A)\times(A+A)\)。注意若 \(l\in L\)，则 \(l\) 有某个斜率 \(m\in D_d\) 且包含 \(P\) 中一点 \((a_1,a_2)\)。特别地，\(l\cap P'\) 包含集合 \[\{(a_1+a_3,\ a_2+a_4):a_3,a_4\in A;\ a_3/a_4=m\},\] 按 \(D_d\) 的定义，它的基数至少为 \(d\)。因此 \(L\) 中每条直线在 \(P'\) 上至少有 \(d\) 个点；再次用推论 8.5，得 \[|L|=O\!\left(\frac{|P'|}{d}+\frac{|P'|^2}{d^3}\right)=O\!\left(\frac{|P'|^2}{d^3}\right),\] 其中后一个上界成立是因为 \(d\le|A|\) 且 \(|P'|\ge|A|^2\)。将 (8.4) 与 \(|P'|=|A+A|^2\) 代入，经过一些代数运算可得 \[|D_d|=O\!\left(\frac{|A+A|^{8/3}}{|A|^{2/3}\,d^2}\right).\tag{8.5}\] 第三段（加总各层，得第一式）。 特别地，由 \(D_d\) 的定义（每个 \(m\in D_d\) 有约 \(d\) 个表示）， \[\big|\{(a_1,a_2)\in A\times A:\ a_1/a_2\in D_d\}\big|=O\!\left(\frac{|A+A|^{8/3}}{|A|^{2/3}\,d}\right).\] 对所有大于 \(C|A+A|^{8/3}/|A|^{8/3}\) 的 \(2\) 的幂 \(d\) 求和（\(C\) 为某个足够大的绝对常数；几何级数之和由最小项主导），得 \[\Big|\big\{(a_1,a_2)\in A\times A:\ a_1/a_2\in D_d\ \text{对某个}\ d\ge C|A+A|^{8/3}/|A|^{8/3}\big\}\Big|\le\tfrac12|A|^2,\] 从而 \[\Big|\big\{(a_1,a_2)\in A\times A:\ a_1/a_2\in D_d\ \text{对某个}\ d< C|A+A|^{8/3}/|A|^{8/3}\big\}\big|\ge\tfrac12|A|^2.\] 而对如上的 \(d\)，每个 \(m\in D_d\) 至多有 \(O(d)=O(|A+A|^{8/3}/|A|^{8/3})\) 个形如 \(a_1/a_2\) 的表示，于是可得 \[|A/A|=\Omega\!\left(\frac{|A|^2}{\,|A+A|^{8/3}/|A|^{8/3}\,}\right)=\Omega\!\left(\frac{|A|^{14/3}}{|A+A|^{8/3}}\right),\] 这就给出第一个不等式（两边立方即 \(|A+A|^8|A/A|^3=\Omega(|A|^{14})\)）。 第四段（得第二式）。 为证第二个不等式，我们从 (8.5) 观察到 \[\big|\{(a_1,a_2,a_3,a_4)\in A^4:\ a_1/a_2=a_3/a_4\in D_d\}\big|=O\!\left(\frac{|A+A|^{8/3}}{|A|^{2/3}}\right);\] 注意上述论证虽只对 \(d\ge2\) 进行，但此估计对 \(d=1\) 也成立——只需把左边粗略地用 \(|A|^2\) 控制、并用 \(|A+A|\ge|A|\) 从下方控制即可。对介于 \(1\) 与 \(|A|\) 之间的所有 \(2\) 的幂 \(d\) 求和（共约 \(\log|A|\) 项），得 \[\big|\{(a_1,a_2,a_3,a_4)\in A^4:\ a_1/a_2=a_3/a_4\}\big|=O\!\left(\frac{|A+A|^{8/3}}{|A|^{2/3}}\log|A|\right).\] 另一方面，由一个简单的二重计数论证（参见 (2.8)）有 \[\big|\{(a_1,a_2,a_3,a_4)\in A^4:\ a_1/a_2=a_3/a_4\}\big|\ge\frac{|A|^4}{|A\cdot A|},\] 比较上下两式即得结论。♦

证明. 容易归约到 \(A\) 中元素皆为正的情形。令 \[P:=\big((A+A)\cup A\big)\times\big((A+A)\cup A\big);\] 于是 \(P\) 是一个基数为 \(O(|A+A|^2)\) 的点集。我们对 \(P\) 中共线三点组的个数施行二重计数。 上界（一方面）。 推论 8.9 表明，这种三点组的个数为 \(O(|A+A|^2\log|A|)\)。 下界（另一方面）。 标准的 Cauchy–Schwarz 论证（参见 (2.8)）给出 \[\big|\{(a,b,c,d)\in A^4:\ ab=cd\}\big|\ \ge\ \frac{|A|^4}{|A\cdot A|}.\] 我们可设 \(|A\cdot A|\le\tfrac12|A|^2\)（否则结论平凡成立）。这样便可从右边去掉 \(a=d\) 的贡献，得到 \[\big|\{(a,b,c,d)\in A^4:\ ab=cd;\ a\ne d\}\big|=\Omega\!\left(\frac{|A|^4}{|A\cdot A|}\right).\] 对上面集合中任一 \((a,b,c,d)\) 以及任意 \(e,f\in A\)，注意三点 \[(e,f),\quad (e+a,\ f+c),\quad (e+b,\ f+d)\] 构成 \(P\) 中的一个共线三点组。用这种方式得到的三点组个数为 \(\Omega\!\left(\dfrac{|A|^6}{|A\cdot A|}\right)\)。把它与上界相结合，结论即得。♦