Tao–Vu · 加性组合学 · 第 8 章 关联几何

8.2　塞迈雷迪–特罗特定理The Szemerédi–Trotter theorem

本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。

本节目标平面上撒一堆点、画一堆直线，问“点落在线上”这种关联最多能有多少次？显然点越多、线越多，关联就越多；但增长速度有一个出人意料的上限。本节的核心——塞迈雷迪–特罗特定理——给出这个上限，并把它和上一节的“交叉数不等式”串起来；随后用它推出若干关于“富线”“共线三元组”乃至格点凸多边形的漂亮推论。

什么是“关联”

给定一个有限的点集 \(P\) 和一个有限的直线集 \(L\)，一个基本问题是估计 \(P\) 与 \(L\) 之间的关联数（number of incidences） \[ I(P,L):=\bigl|\{(p,l)\in P\times L:\ p\in l\}\bigr|. \] 也就是统计有多少对“(点, 线)”满足该点正好落在该线上。显然，我们可以毫不费力地让 \(I(P,L)\) 小到 \(0\)（把所有线都画在没有点的地方即可），所以有趣的问题是：在 \(|P|\) 与 \(|L|\) 的大小固定时，最大化 \(I(P,L)\) 能达到多少。

例：先把“关联”数清楚 取 \(4\) 个点 \(P=\{A,B,C,D\}\)，其中 \(A,B,C\) 在同一条横线 \(\ell_1\) 上，\(D\) 单独在外。再取两条线：\(\ell_1\)（过 \(A,B,C\)）和 \(\ell_2\)（过 \(C,D\)）。
  1. \(\ell_1\) 上的点：\(A,B,C\)，贡献 \(3\) 个关联对 \((A,\ell_1),(B,\ell_1),(C,\ell_1)\)。
  2. \(\ell_2\) 上的点：\(C,D\)，贡献 \(2\) 个关联对 \((C,\ell_2),(D,\ell_2)\)。
  3. 合计 \(I(P,L)=3+2=5\)。注意 \(C\) 同时落在两条线上，被算了两次——这正是“关联”计的是(点,线)对，而不是点本身。
ℓ₁ ℓ₂ A B C D
关联 = “点落在线上”这件事的次数。这里共有 \(5\) 个关联对；交点 \(C\) 同时属于两条线，被计两次。

当然有一个平凡的界 \(I(P,L)\le |P||L|\)（每个点最多和每条线关联一次）。不费力还能把它进一步改进为 \[ I(P,L)\le \min\bigl(|P|^{1/2}|L|+|P|,\ |L|^{1/2}|P|+|L|\bigr); \tag{8.2}\] 见习题。在文献 [348] 中，塞迈雷迪（Szemerédi）与特罗特（Trotter）证明了下面这个更强的估计，它在相差一个常数因子的意义下是最优的。

(8.2) 是怎么来的（直觉）关键事实只有两条：两点确定至多一条线，两线相交于至多一点。把它们配合柯西–施瓦茨不等式就能挤出 (8.2)。其中 \(|P|^{1/2}|L|\) 这一项已经接近真相，但指数 \(1\)（在 \(|L|\) 上）偏大；塞迈雷迪–特罗特把两边的指数都压到 \(2/3\)，这才是质的飞跃。

主定理

定理 8.3（塞迈雷迪–特罗特定理）设 \(P\) 为有限点集，\(L\) 为有限直线集。则 \[ I(P,L)\le 4|P|^{2/3}|L|^{2/3}+4|P|+|L|. \]
证明. 我们可以删去 \(L\) 中那些不含 \(P\) 中任何点的直线 \(l\)，因为它们对左边毫无贡献。于是不妨假设 \(L\) 中每条直线至少含 \(P\) 中一个点。

现在构造一个图 \(G=G(P,E)\)：它的顶点就是 \(P\) 中的点；两点 \(a,b\) 之间连一条边，当且仅当从 \(a\) 到 \(b\) 的开线段落在 \(L\) 的某条直线上，并且其内部不含 \(P\) 中任何点。换言之，沿着某条直线，把相邻的两个点用边连起来。

我们对边数 \(|E|\) 施行双重计数法。观察：若 \(L\) 中一条直线 \(l\) 含 \(P\) 中 \(k\ge 1\) 个点，则 \(l\) 给 \(E\) 贡献 \(k-1\) 条边（\(k\) 个点排成一串，相邻配对得 \(k-1\) 条）。对所有 \(l\in L\) 求和，得 \[ |E|=I(P,L)-|L|. \] （因为 \(\sum_l k_l = I(P,L)\)，而每条线减去的那个 \(1\) 合计为 \(|L|\)。）

另一方面，图 \(G\) 有一个“天然画法”（tautological drawing）：把 \(P\) 中每个顶点画在它本来的位置，把边 \([a,b]\) 画成从 \(a\) 到 \(b\) 的线段。由于 \(L\) 中任意两条直线至多相交于一点，我们得到交叉数满足 \[ \mathrm{cross}(G)\le |L|^2. \] 对 \(G\) 应用交叉数不等式（上一节的结论：要么 \(|E|\le 4|V|\)，要么 \(\mathrm{cross}(G)\ge |E|^3/(64|V|^2)\)），其中 \(|V|=|P|\)，于是：要么 \(|E|\le 4|P|\)，要么 \[ |L|^2\ge \mathrm{cross}(G)\ge \frac{|E|^3}{64|P|^2}\ \Longrightarrow\ |E|\le 4|P|^{2/3}|L|^{2/3}. \] 因此 \(|E|\le \max\bigl(4|P|,\,4|P|^{2/3}|L|^{2/3}\bigr)\)。结合 \(I(P,L)=|E|+|L|\)，即得所证（\(\max\) 不超过两项之和，故得 \(4|P|^{2/3}|L|^{2/3}+4|P|+|L|\)）。♦

证明骨架（为什么能奏效）核心招式是“同一个量 \(|E|\) 两头夹”：
  1. 下界方向（从关联出发）：把每条富含点的直线拆成相邻点对，边数恰好 \(=I(P,L)-|L|\)。所以关联多 ⇔ 边多。
  2. 上界方向（从平面图出发）：这张图画在平面上，两条直线最多交一次，所以交叉总数 \(\le |L|^2\)，受 \(|L|\) 的强力限制。
  3. 交叉数不等式当桥梁：它说“边一多，交叉必爆炸（\(\sim |E|^3/|P|^2\)）”。把交叉压在 \(|L|^2\) 以内，就反推出 \(|E|\) 不能太大。
  4. 边数被卡住，关联数 \(=|E|+|L|\) 也就被卡住了。
例：定理给出的具体数字 设有 \(|P|=|L|=10^6\)（一百万个点、一百万条线）。 逐次收紧：\(10^{12}\to10^{9}\to4\times10^{8}\)。当 \(|P|=|L|=n\) 时主项为 \(4n^{4/3}\)，远小于平凡的 \(n^2\)。
记号约定 全节用 \(O(\cdot)\) 表示“不超过某常数倍”（上界），用 \(\Omega(\cdot)\) 表示“至少某常数倍”（下界），用 \(\Theta(\cdot)\) 表示两者兼有（同阶）。这些常数与点、线的具体个数无关。
注记 8.4 上面的证明归功于塞凯伊（Székely）[342]；塞迈雷迪与特罗特的原始证明相当不同（见习题 8.4.7，那里给出一个精神上更接近原证的证明）。\(P\) 与 \(L\) 之间的对称性可由射影对偶来解释：若把平面 \(\mathbb{R}^2\) 嵌入 \(\mathbb{R}^3\) 的射影空间，则点对应于 \(\mathbb{R}^3\) 中 \(1\) 维子空间，而直线对应于余维 \(1\) 的子空间。点与线在对偶下互换，这就是为什么定理里 \(|P|\) 与 \(|L|\) 地位完全平等。

由定理推出的推论

现在我们从定理导出若干推论。第一个是直接结论（留作习题），它能让我们估计有多少条直线是“富的”——所谓富，是指它含有给定点集 \(P\) 中许多元素。

推论 8.5（富线）若 \(P\) 是任意有限点集，\(k\ge 2\)，则 \[ \bigl|\{l\text{ 是直线}:\ |l\cap P|\ge k\}\bigr| = O\!\left(\max\Bigl(\frac{|P|^2}{k^3},\ \frac{|P|}{k}\Bigr)\right). \] 对偶地，对任意有限直线集 \(L\)，有 \[ \bigl|\{p\in\mathbb{R}^2:\ |\{l\in L:\ p\in l\}|\ge k\}\bigr| = O\!\left(\max\Bigl(\frac{|L|^2}{k^3},\ \frac{|L|}{k}\Bigr)\right). \]
读懂推论 8.5“至少含 \(k\) 个点的直线”叫 \(k\)-富线。直觉：每条 \(k\)-富线至少吃掉 \(k\) 个关联；若有 \(N_k\) 条这样的线，则它们合计至少 \(kN_k\) 个关联。把它和定理 8.3 的关联上界比较，就能反解出 \(N_k\) 的上界——\(k\) 越大，富线越稀少（分母里 \(k^3\) 衰减极快）。对偶版本把“线富含点”换成“点上挤了许多线”，靠的正是注记 8.4 的点线对称。
例：富线随 \(k\) 迅速变少 取 \(|P|=10^4\)，看主项 \(|P|^2/k^3=10^8/k^3\)：
  1. \(k=10\)：至多约 \(10^8/10^3=10^5\) 条富线。
  2. \(k=100\)：至多约 \(10^8/10^6=10^2\) 条。
  3. \(k=1000\)：至多约 \(10^8/10^9=0.1\)，即几乎不存在含 \(1000\) 点的直线。
\(k\) 翻 \(10\) 倍，富线上限掉 \(1000\) 倍——这就是 \(k^3\) 的威力。
注记 8.6 在典型应用（如下文）中 \(k\le |P|^{1/2}\)，此时 \(\dfrac{|P|^2}{k^3}\) 这一项占主导（因为此时 \(|P|^2/k^3\ge |P|/k\)）。而 \(k>|P|^{1/2}\) 的情形可用较粗的估计 (8.2) 处理。推论后半部分（对偶版）同理。

接下来，我们估计“被一条富线连接的点对”有多少。

推论 8.7（富点对）若 \(P\) 是任意有限点集，\(k\ge 1\)，则 \[ \bigl|\{(p,q)\in P\times P:\ p\neq q;\ k\le |l_{p,q}\cap P|\le 2k\}\bigr| = O\!\left(\max\Bigl(\frac{|P|^2}{k},\ |P|k\Bigr)\right), \] 其中 \(l_{p,q}\) 是连接 \(p,q\) 的唯一直线。特别地，若 \(1\le k\le |P|^{1/2}\)，则 \[ \bigl|\{(p,q)\in P\times P:\ p\neq q;\ k\le |l_{p,q}\cap P|\le |P|^{1/2}\}\bigr| = O\!\left(\frac{|P|^2}{k}\right). \]
证明. 对第一个界：每条满足 \(k\le |l\cap P|\le 2k\) 的直线 \(l\)，其上点数在 \([k,2k]\) 内，故由它产生的有序点对 \((p,q)\)（都取自 \(l\cap P\)）至多 \(O(k^2)\) 对。再由推论 8.5，这类直线的条数为 \(O(|P|^2/k^3)\)（取主项）。于是点对总数 \[ \le O(k^2)\cdot O\!\Bigl(\frac{|P|^2}{k^3}\Bigr)=O\!\Bigl(\frac{|P|^2}{k}\Bigr), \] 此即结论。第二个界由第一个界结合标准的二进分解（dyadic decomposition）论证得到：把区间 \([k,|P|^{1/2}]\) 按 \(k,2k,4k,\dots\) 分成 \(O(\log)\) 段，每段用第一界，求和后主项仍为 \(O(|P|^2/k)\)（几何级数求和被首项控制）。♦
例：把“点对”和“线”对应起来 一条恰含 \(k\) 个点的直线，能产生多少个有序点对 \((p,q)\)（\(p\neq q\)）？答：\(k(k-1)\approx k^2\)。所以“线的条数”乘以“每条线的 \(k^2\) 对”就是点对总数——这正是上面证明里 \(O(k^2)\times O(|P|^2/k^3)\) 的来历。

对上述论证做一个简单修改（留作习题），还能控制那些不在过富直线上的共线三元组：

推论 8.8（共线三元组）设 \(P\) 为有限点集。则满足如下条件的三元组 \((u,v,w)\) 的个数至多为 \(O(|P|^2\log|P|)\)：\(u,v,w\) 是 \(P\) 中三个互异的共线点，且它们所在的直线至多含 \(P\) 中 \(|P|^{1/2}\) 个点。
为什么会冒出 \(\log\)把直线按其上点数 \(k\) 做二进分组 \(k\sim 1,2,4,\dots,|P|^{1/2}\)，共 \(O(\log|P|)\) 组。每组里共线三元组个数 \(\sim k^3\times(\text{该组线数})\sim k^3\cdot |P|^2/k^3=|P|^2\)（与 \(k\) 无关！）。每组都贡献 \(O(|P|^2)\)，组数为 \(O(\log|P|)\)，相乘即 \(O(|P|^2\log|P|)\)。这个 \(\log\) 正是“各尺度均匀贡献再叠加”的产物。

把它特别应用到笛卡儿积 \(P=A\times B\)（\(A,B\) 是实数集，\(|A|=|B|=m\)）：此时 \(|P|=m^2\)，且没有任何直线能与 \(P\) 相交超过 \(|P|^{1/2}=m\) 个点（一条直线在网格 \(A\times B\) 上每个横坐标至多取一点，故至多 \(m\) 点）。由此立得

推论 8.9设 \(A,B\) 为基数 \(m\) 的实数集。则 \(A\times B\) 中至多含 \(O(m^4\log m)\) 个共线三元组。
B A
\(m\times m\) 网格 \(P=A\times B\)（这里 \(m=5\)）。任一直线在每一竖列至多取一点，故至多含 \(m\) 个点；恰好落入推论 8.8 的“至多 \(|P|^{1/2}=m\) 点”条件。

推广到曲线

把塞迈雷迪–特罗特定理从直线推广到更一般的曲线是件容易的事。

定理 8.10（广义塞迈雷迪–特罗特定理）[342]设 \(P\) 为 \(\mathbb{R}^2\) 中有限点集，\(L\) 为 \(\mathbb{R}^2\) 中有限曲线集。假设 \(L\) 中任意两条曲线至多相交于 \(\alpha\) 个点，且 \(P\) 中任意两点至多同时落在 \(\beta\) 条曲线上；则 \[ \bigl|\{(p,l)\in P\times L:\ p\in l\}\bigr| = O\!\left(\alpha^{1/3}\beta^{1/3}|P|^{2/3}|L|^{2/3}+|L|+\beta|P|\right). \]
两个参数 \(\alpha,\beta\) 在管什么原定理里隐含了 \(\alpha=1\)（两直线至多交一点）与 \(\beta=1\)（两点至多被一条直线同穿）。换成曲线后： 把 \(\alpha=\beta=1\) 代入即回到定理 8.3 的主项 \(|P|^{2/3}|L|^{2/3}\)。

作为该定理的一个应用，我们证明 Andrews [13] 的下述著名结果。

定理 8.11设 \(\Gamma\subset\mathbb{R}^2\) 为一个格（例如 \(\Gamma=\mathbb{Z}^2\)）。若 \(C\) 是一个顶点都在 \(\Gamma\) 中的凸 \(n\) 边形，则 \(C\) 的内部含有 \(\Omega(n^3)\) 个格点。
证明. 设 \(\partial C\) 为 \(C\) 的边界，\(\mathcal{F}\) 为把 \(\partial C\) 沿着 \(C\) 内部的每个格点平移所得的（分段线性）曲线之集合。设 \(P\) 为被 \(\mathcal{F}\) 中曲线的并所覆盖的全体格点之集合，\(m\) 为 \(C\) 内部的格点个数。则 \[ |\mathcal{F}|=m,\qquad |P|=\Theta(m)\quad(\text{参见 (3.10)}). \]

我们对 \(P\) 与 \(\mathcal{F}\) 之间的关联数施行双重计数。一方面，广义塞迈雷迪–特罗特定理给出这些关联的上界为 \(O(m^{4/3})\)（把 \(|P|=\Theta(m)\)、\(|\mathcal{F}|=m\) 代入主项 \(|P|^{2/3}|L|^{2/3}=m^{2/3}m^{2/3}=m^{4/3}\)）。另一方面，每一条 \(\partial C\) 的平移恰好通过 \(n\) 个格点（因为原 \(n\) 边形有 \(n\) 个顶点落在格点上，平移后仍是 \(n\) 个），故关联数至少为 \(nm\)。比较两个界： \[ nm \le O(m^{4/3})\ \Longrightarrow\ n=O(m^{1/3})\ \Longrightarrow\ m=\Omega(n^3), \] 即所求。♦

例：n 越大，内部格点必然爆炸式增多 定理说“顶点在格上的凸 \(n\) 边形，内部至少 \(\sim n^3\) 个格点”。
  1. \(n=10\)：内部至少约 \(c\cdot 10^3=1000c\) 个格点。
  2. \(n=20\)：至少约 \(c\cdot 20^3=8000c\) 个——边数翻倍，内部格点至少翻 \(8\) 倍。
  3. 直觉：要想用格点顶点拼出边数很多的凸多边形，每条边的方向（向量）必须各不相同且越来越长，于是多边形被迫“撑得很大”，把大量格点圈进内部。
顶点都落在格点（深蓝）上的凸六边形。Andrews 定理断言：要让顶点数 \(n\) 增大，多边形必须撑大，从而内部圈住 \(\Omega(n^3)\) 个格点。
注记 8.12 上述定理可推广到 \(\mathbb{R}^d\)。对任意固定的 \(d\)，Andrews 证明了：若 \(\mathbb{R}^d\) 中一个凸多胞形的边界上有 \(n\) 个不共面的整点，则其体积为 \(\Omega\bigl(n^{(d+1)/(d-1)}\bigr)\)。然而上面的证明不能推广到更高维。

一个重要的公开问题

一个重要的公开问题是：把塞迈雷迪–特罗特定理推广到其他域上的平面，例如复平面 \(\mathbb{C}^2\) 或有限域平面 \(\mathbb{F}_p^2\)。粗糙的估计 (8.2) 在所有这些情形都成立（它只用到“两点定一线、两线交一点”，对任意域都对），但人们希望改进这个界。在 \(\mathbb{F}_p^2\) 的情形已经证明：对所有 \(\delta>0\) 以及某个依赖 \(\delta\) 的 \(\varepsilon(\delta)>0\)，只要 \(|P|,|L|\le p^{2-\delta}\)，就有 \[ I(P,L)=O_\delta\!\left(\max(|P|,|L|)^{3/2-\varepsilon(\delta)}\right); \] 见 [43]、[44]。该论证的主要原料是和积估计（推论 2.58）与 Balog–Szemerédi–Gowers 定理（定理 2.29）。

为什么换个域就变难定理 8.3 的证明依赖交叉数不等式，而后者本质上用到了实平面的拓扑（“画在平面上、欧拉公式”）。有限域 \(\mathbb{F}_p^2\) 没有这种连续拓扑，于是这条路走不通，必须改用和积估计等纯组合/代数工具——这也解释了关联几何与加性组合学（和积问题）之间的深刻联系，正是本书后续 8.3、8.5 节的主题。

习题

习题 8.2
  1. 8.2.1　仅用基本事实“两个不同的点确定至多一条线”“两条不同的线相交于至多一点”，配合柯西–施瓦茨不等式，证明 (8.2)。注意该论证对任意域都成立，而不止 \(\mathbb{R}\)。在域为 \(\mathbb{F}_p^2\) 的情形，证明当 \(|P|=|L|=p^2\) 或 \(|P|=|L|=p^4\) 时该界可达到最优。
  2. 8.2.2　设给定 \(n,m\ge 1\)。找出一个点集 \(P\) 与直线集 \(L\) 的例子，使得 \(|P|=n\)、\(|L|=m\)，且 \(P,L\) 间的关联数为 \(\Omega(n^{2/3}m^{2/3}+n+m)\)，从而表明塞迈雷迪–特罗特定理在相差常数因子意义下最优。（提示：考虑形如 \(P=[1,a]\times[1,ab]\) 的点集，并取不同的参数 \(a,b\)。）
  3. 8.2.3　证明推论 8.5。
  4. 8.2.4　证明推论 8.8。
  5. 8.2.5　设 \(P\) 为有限点集，\(k\ge 2\)。证明 \[ \bigl|\{(p,l):\ p\in P;\ l\text{ 是直线};\ p\in l;\ |l\cap P|\ge k\}\bigr| = O\!\left(\frac{|P|^2}{k^2}+|P|\log|P|\right). \]
  6. 8.2.6（Beck 定理）[19]　设 \(P\) 为有限点集。证明：要么存在一条直线关联 \(P\) 中 \(\Omega(|P|)\) 个点，要么存在 \(\Omega(|P|^2)\) 条直线，每条都恰好关联 \(P\) 中两个点。
  7. 8.2.7（Sylvester–Gallai 定理）　设 \(P\) 为有限点集，且并非所有点都共线。证明：存在一条直线恰好含 \(P\) 中两个点。（提示：最小化量 \(\mathrm{dist}(p,l)\)，其中 \(l\) 是含两个或更多 \(P\) 中点的直线，\(p\in P\setminus l\)。用初等几何证明该量仅当 \(l\) 恰含 \(P\) 中两点时才取到最小。）
  8. 8.2.8　证明定理 8.10。（提示：用习题 8.1.5。）
  9. 8.2.9　设 \(\gamma\) 为 \(\mathbb{R}^2\) 中一条严格凸曲线。证明对所有 \(R\ge 1\) 及所有格 \(\Gamma\)，有 \(|(R\cdot\gamma)\cap\Gamma|=O_\gamma(R^{2/3})\)。
  10. 8.2.10　设 \(\gamma\) 为 \(\mathbb{R}^2\) 中一条严格凸曲线，\(A\) 为 \(\mathbb{R}^2\) 中有限集。证明 \(\bigl|\{(a,a')\in A\times A:\ a-a'\in\gamma\}\bigr|=O(|A|^{4/3})\)。由此推出 \(\bigl|\{|x-y|:\ x,y\in A\}\bigr|=\Omega(|A|^{2/3})\)。

返回 全书目录