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

8.4　单元分解与相异距离问题Cell decompositions and the distinct distances problem

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

本节目标给定平面（或 \(d\) 维空间）里的 \(n\) 个点，它们两两之间能拼出多少个互不相同的距离？这就是 Erdős 在 1946 年提出的相异距离问题。点摆得越“规整”，重复的距离越多、不同距离就越少。本节要为“不同距离的个数”证明下界：平面上 Székely 的 \(\Omega(n^{4/5})\)（用第 8 章前几节的交叉数与 Szemerédi–Trotter 工具），以及高维“均匀分布”情形下用单元分解（把空间切成许多小块）得到的下界。核心套路始终是：对同一个量做双重计数，一边给上界、一边给下界，再夹出结论。

问题的提法

给定有限点集 \(P\subset\mathbb{R}^d\)，记 \[g(P):=\bigl|\{\,|x-y| : x,y\in P\,\}\bigr|\] 为 \(P\) 中元素之间相异距离的个数。定义 \[g_d(n)=\min_{P\subset\mathbb{R}^d,\,|P|=n} g(P).\] 著名的 Erdős 相异距离问题（distinct distances problem，1946 年提出，见 [83]）要求对每个固定的 \(d\)，确定 \(g_d(n)\) 关于 \(n\) 的正确增长速率；即使 \(d=2\)，这个问题至今仍然悬而未决。（显然 \(g_1(n)=n-1\)。）

为什么 \(g_1(n)=n-1\)直线上取 \(n\) 个点，把它们从小到大排成 \(x_1<x_2<\dots<x_n\)。最小的非零距离至少有 \(x_2-x_1\)，最大的距离是 \(x_n-x_1\)。要让不同距离尽量少，取等差排列 \(1,2,\dots,n\)：此时所有距离恰好是 \(1,2,\dots,n-1\)，共 \(n-1\) 个，且无法更少（任意两点中最远的一对就贡献了一个最大距离，最近的贡献最小距离，配合鸽笼可证下界）。所以 \(g_1(n)=n-1\)。

考虑等差数列盒子 \(P=[1,n^{1/d}]^d\)，容易看出 \(g_d(n)=O\!\left(d\,n^{2/d}\right)\)。Erdős 与许多其他研究者猜测 \(g_d(n)\) 接近这个上界；特别地，猜测对任意 \(\varepsilon>0\) 有 \[g_d(n)=\Omega_{\varepsilon,d}\!\left(n^{2/d-\varepsilon}\right).\]

规整的格子里 很多对点共享 同一个距离， 所以相异距离 的个数很少。 \(P=[1,n^{1/d}]^d\)（此处 \(d=2\)）
把 \(n\) 个点摆成边长约 \(n^{1/d}\) 的整点盒子，距离平方都是不超过 \(d\cdot n^{2/d}\) 的整数（且只有 \(O(d\,n^{2/d})\) 种），于是相异距离至多 \(O(d\,n^{2/d})\) 个——这就是上界。难的是反方向：证明任何摆法都至少有多少个相异距离。

建立下界 \(g_d(n)=\Omega_d(n^{1/d})\) 是相当容易的：见习题 8.4.2。对 \(d=2\) 的情形有一系列改进，分别来自 Moser [252]、Chung [57]、Chung–Szemerédi–Trotter [60]、Székely [342]、Solymosi–Tóth [328]、Tardos [353] 以及 Katz 与 Tardos [197]。目前最好的界是 \(g_2(n)=\Omega(n^{0.8635})\) [197]，它在 [328] 的方法基础上结合了巧妙的熵论证。这里我们将给出 Székely 得到的一个稍弱的界；这个论证是上面所提到的全部后续改进的基石。

定理 8.17 [342] 我们有 \[g_2(n)=\Omega\!\left(n^{4/5}\right).\]

定理 8.17 的证明：等腰三角形的双重计数

关键定义（等腰三角形 / 窄）设 \(P\) 是 \(\mathbb{R}^2\) 中的 \(n\) 个点。把等腰三角形定义为 \(P\) 中三个不同点构成的三元组 \((p,q,q')\)，满足 \(|p-q|=|p-q'|\)。若以 \(p\) 为圆心、从 \(q\) 到 \(q'\) 的那段圆弧上不含 \(P\) 的其他点，就称这个等腰三角形是窄的（narrow）。称点对 \((q,q')\) 为这个等腰三角形的底（base），称 \(p\) 为顶（apex）。对任意 \(k\ge 1\)，若一个点对 \((q,q')\) 是至少 \(k\) 个窄等腰三角形的底，就称它是 \(k\)-富（\(k\)-rich）的；否则称它 \(k\)-贫（\(k\)-poor）。
顶 \(p\) \(q\) \(q'\) 这段弧上没有 P 的其他点 ⇒ 窄 \(|p-q|=|p-q'|\)
等腰三角形：两条腰 \(|p-q|=|p-q'|\) 等长，故 \(q,q'\) 同在以 \(p\) 为圆心的某个圆上。“窄”表示 \(q,q'\) 在这个圆上是相邻的（它们之间的弧上没夹别的点）。

设 \(N\) 为窄等腰三角形 \((p,q,q')\) 的个数。我们将对 \(N\) 施行一个双重计数论证。先从下界开始。\(p\) 有 \(|P|\) 种选择。固定 \(p\) 后，其余 \(|P|-1\) 个点落在以 \(p\) 为圆心的至多 \(g_2(|P|)\) 个圆上。设 \(\mathcal{C}\) 为这些圆的集合，则容易验证：以 \(p\) 为顶的窄等腰三角形的个数为 \[\sum_{C\in\mathcal{C}:\,|C\cap P|\ge 2} 2\,|C\cap P|.\] 由于 \(\sum_{C\in\mathcal{C}}|C\cap P|=|P|-1\)，上式可写为 \(2|P|-O(g_2(P))\)。对所有 \(p\) 求和，便得 \[N\ge 2|P|^2-O\!\left(|P|\,g_2(|P|)\right).\]

把这个下界算清楚固定顶 \(p\)。围绕 \(p\)，把其余各点按到 \(p\) 的距离分组——每一组就落在一个圆上。设某个圆 \(C\) 上有 \(m=|C\cap P|\ge2\) 个点，把它们沿圆周排成一圈。
  1. 窄等腰三角形的底 \((q,q')\) 必须是圆周上相邻的两点（中间不夹别的点）。沿圆周一圈，相邻点对恰好 \(m\) 个。
  2. 把底视为有序 \((q,q')\)（两种顺序各算一次），故该圆贡献 \(2m\) 个有序窄等腰三角形，即 \(2|C\cap P|\)。
  3. 对 \(p\) 周围所有圆求和：\(\sum_{C:\,|C\cap P|\ge2}2|C\cap P|=2\sum_C|C\cap P|-2\!\!\sum_{C:\,|C\cap P|=1}\!\!1\)。第一项 \(=2(|P|-1)=2|P|-2\)；第二项是“只含一个点的圆”的个数，而圆总数不超过 \(g_2(P)\)，故为 \(O(g_2(P))\)。合起来 \(=2|P|-O(g_2(P))\)。
  4. 顶 \(p\) 共 \(|P|\) 个，相加得 \(N\ge \sum_p\bigl(2|P|-O(g_2(P))\bigr)=2|P|^2-O(|P|\,g_2(|P|))\)。
直觉：相异距离少（\(g_2\) 小）就意味着每个 \(p\) 周围的圆少，于是每个圆上挤的点多、相邻对多、窄等腰三角形多 —— \(N\) 的下界与“\(g_2\) 小”直接挂钩，这正是反证的杠杆。
\(p\) 同一圆上相邻的 两点 → 一个窄 等腰三角形（绿弧）。 相异距离越少， 同心圆越少， 每圈点越密。
固定顶 \(p\)，所有其他点按到 \(p\) 的距离分布在至多 \(g_2(|P|)\) 个同心圆上。每个圆上相邻的一对点给出一个窄等腰三角形。

现在我们来求上界。令 \(k\ge1\) 为稍后选定的参数，并把 \(N\) 拆为 \(N=N_{\text{rich}}+N_{\text{poor}}\)，其中 \(N_{\text{rich}}\)（相应地 \(N_{\text{poor}}\)）是底为 \(k\)-富（相应地 \(k\)-贫）的窄等腰三角形的个数。注意：若 \((p,q,q')\) 是底为 \(k\)-富的等腰三角形，则 \(q,q'\) 的垂直平分线 \(l\) 既经过 \(p\)，也至少包含 \(P\) 中的 \(k\) 个点。反过来，对固定的 \(l\) 与 \(p\)，使 \((p,q,q')\) 为窄等腰三角形、且以 \(l\) 为垂直平分线的点对 \((q,q')\) 至多有 \(4g_2(|P|)\) 个；这可以这样看出：把 \(P\setminus\{p\}\) 覆盖进至多 \(g_2(|P|)\) 个圆，每个圆至多贡献四个这样的三角形。应用习题 8.2.5，我们得到 \[N_{\text{rich}}=O\!\left(g_2(|P|)\left(\frac{|P|^2}{k^2}+|P|\log|P|\right)\right).\]

为什么富底牵出“富线”
  1. \((q,q')\) 是底，意味着每个对应的顶 \(p\) 都满足 \(|p-q|=|p-q'|\)，即 \(p\) 到 \(q,q'\) 等距。到两点等距的点恰好构成线段 \(qq'\) 的垂直平分线 \(l\)。
  2. 底 \((q,q')\) 是 \(k\)-富，就是说它至少是 \(k\) 个窄等腰三角形的底，于是至少有 \(k\) 个不同的顶 \(p\in P\) 落在同一条线 \(l\) 上 —— 即 \(l\) 是一条“含 \(P\) 中 \(\ge k\) 个点”的富线。
  3. 习题 8.2.5（来自 Szemerédi–Trotter 关联定理）给出富线数量的上界：含 \(\ge k\) 个点的直线至多 \(O(|P|^2/k^3+|P|/k)\) 条。把它与“每条线、每个点至多 \(4g_2\) 个底”相乘累加，便得到上面的 \(N_{\text{rich}}\) 估计。
关键直觉：把“等腰”翻译成“顶在垂直平分线上”，就把几何问题接回了第 8.2 节已经解决的点线关联问题。
\(q\) \(q'\) 垂直平分线 \(l\) 每个顶 \(p\) 都在 \(l\) 上 \(\ge k\) 个 ⇒ \(l\) 是富线
底 \((q,q')\) 固定，所有以它为底的等腰三角形的顶都落在垂直平分线 \(l\) 上。底越富（顶越多），线 \(l\) 上的 \(P\)-点就越多。

至于贫三角形，考虑一个重图画（multi-graph drawing）\(G\)：以 \(P\) 为顶点，以那些底为 \(k\)-贫的窄等腰三角形 \((p,q,q')\) 所对应的圆弧为边。这个图有 \(|P|\) 个顶点、\(N_{\text{poor}}\) 条边，且边的重数至多为 \(k\)。于是由习题 8.1.5 有 \[N_{\text{poor}}=O\!\left(k|P|+k^{1/3}|P|^{2/3}\,\mathrm{cross}(G)^{1/3}\right).\] 另一方面，由于 \(G\) 的这个画法被包含在至多 \(|P|\,g_2(|P|)\) 个圆内（每个圆心 \(p\in P\) 至多贡献 \(g_2(|P|)\) 个圆），而任意两个圆至多相交于两点，我们看出 \(\mathrm{cross}(G)\le 2\bigl(|P|\,g_2(|P|)\bigr)^2\)；于是 \[N_{\text{poor}}=O\!\left(k|P|+k^{1/3}|P|^{4/3}\,g_2(|P|)^{2/3}\right).\]

交叉数登场（习题 8.1.5）窄等腰三角形 \((p,q,q')\) 的“弧”\(\,q\!\to\!q'\,\)（以 \(p\) 为圆心）天然是平面上一条曲线，把它当作连接 \(q,q'\) 的一条边，就得到一张画在平面上的（重）图 \(G\)。
  1. 边的重数 \(\le k\)：同一对端点 \((q,q')\) 之间的平行边，对应以它为底的不同窄等腰三角形；因为这里只收“\(k\)-贫”的底，故每对端点的边数 \(<k\)。
  2. 交叉数 \(\mathrm{cross}(G)\)：两条弧相交，必是它们所在的两个圆相交。圆共有 \(\le|P|g_2\) 个，两两至多交于 \(2\) 点，故 \(\mathrm{cross}(G)\le 2(|P|g_2)^2\)。
  3. 把这两条代入第 8.1 节的重图交叉数引理（习题 8.1.5），就把边数 \(N_{\text{poor}}\) 用 \(g_2\) 框住了。

把 \(N_{\text{poor}}\) 与 \(N_{\text{rich}}\) 的上界同 \(N\) 的下界合并，我们得到 \[\tfrac12|P|^2\le O\!\left(|P|g_2(|P|)\right)+O\!\left(g_2(|P|)\left(\frac{|P|^2}{k^2}+|P|\log|P|\right)\right)+O\!\left(k|P|+k^{1/3}|P|^{4/3}g_2(|P|)^{2/3}\right).\] 我们通过取 \(k:=c|P|^{2/5}\)（\(c>0\) 为某个小常数）来优化它，随后一些初等代数便给出所需的 \(g_2(|P|)=\Omega(|P|^{4/5})\)。♦

为什么取 \(k\sim|P|^{2/5}\)、为什么落在 \(4/5\)把左边的主项 \(\tfrac12|P|^2\) 与右边各项对抗。反设 \(g_2:=g_2(|P|)\) 较小，看哪一项先“撑不住”。
  1. 富项里有 \(g_2\cdot|P|^2/k^2\)，它随 \(k\) 增大而变小；贫项里有 \(k^{1/3}|P|^{4/3}g_2^{2/3}\)，随 \(k\) 增大而变大。最优的 \(k\) 让这两股力量平衡。
  2. 令 \(g_2|P|^2/k^2 \sim k^{1/3}|P|^{4/3}g_2^{2/3}\) 并代入“若结论 \(g_2\sim|P|^{4/5}\) 成立”自洽，可定出 \(k\sim|P|^{2/5}\)。
  3. 代回主不等式 \(|P|^2\lesssim(\text{含 }g_2\text{ 的项})\)，解出 \(g_2\gtrsim|P|^{4/5}\)。指数 \(4/5\) 正是这场上下界拉锯的平衡点。

上述论证可以推广到比欧氏度量更一般的许多度量上；见 [130]。然而，要想突破 \(n^{4/5}\)，似乎就需要用到欧氏几何更精细的算术结构。非常粗略地说，[328]、[353]、[197] 的结果通过分析“给定顶 \(p\)、底为 \(k\)-富的所有窄等腰三角形 \((p,q,q')\) 的垂直平分线”来推进；注意这些平分线在如下意义下是 \(k\)-富的：它们各自至少包含 \(P\) 中的 \(k\) 个点。围绕 \(p\) 采用极坐标，可以用 \(q\) 与 \(q'\) 的角度之和来参数化这些平分线。然后便能利用关于部分和集（partial sum sets）的一些界，得到“过 \(p\) 的 \(k\)-富直线条数”的非平凡下界，再与习题 8.2.5 结合，从而改进定理 8.17；见 [328]。[353]、[197] 中更进一步的细化也类似进行，但采用了一个稍弱的“窄等腰三角形”概念，允许连接 \(q\) 与 \(q'\) 的圆弧上含有 \(O(1)\) 个 \(P\) 的其他点。这就提供了若干额外的部分和集，进而对“过 \(p\) 的 \(k\)-富直线条数”给出略好的下界。

高维与均匀分布：单元分解

在高维情形 \(d>2\) 中，已知的结果要少得多。不过，如果对这些点施加某种均匀分布的假设，倒是有一些合理的结果。设 \(Q_d\) 为 \(\mathbb{R}^d\) 中以原点为中心的标准单位立方体。我们称有限集 \(P\subset\mathbb{R}^d\) 是齐性的（homogeneous），若 \(P\subset|P|^{1/d}\cdot Q\)，并且对所有 \(x\in\mathbb{R}^d\) 都有 \(|P\cap(x+Q)|=O_d(1)\)。一个齐性集的好例子可以这样得到：从等差盒子 \([1,|P|^{1/d}]^d\) 出发，把其中每个元素任意地平移一个有界的位移量。

齐性集的两个条件，直白地说
  1. 装得下：\(P\subset|P|^{1/d}\cdot Q\) —— 全部 \(n=|P|\) 个点装进一个边长约 \(n^{1/d}\) 的大立方体里。
  2. 不扎堆：把一个单位立方体 \(x+Q\) 平移到任何位置，里面最多只有 \(O_d(1)\)（即与 \(n\) 无关的常数个）点。也就是点既不太挤、（配合条件 1 的“装得下”）整体上又大致铺满 —— 平均每个单位体积有常数个点。
所以“齐性”= 点近似均匀地散布，像被轻轻扰动过的格子，而不是聚成一团或排在一条低维子空间里。
齐性：轻扰动的格子（均匀） 非齐性：扎堆（被禁止）
左：齐性集，点均匀铺开，任一单位方块里点数有界。右：扎堆的点集不是齐性的，违反“不扎堆”条件。

Erdős 原始问题的一个弱化版本，是问一个齐性集中相异距离的个数。齐性集之所以有趣，至少有两个原因。第一，距离问题目前已知的最佳上界都是齐性的。第二，齐性集在分析学中扮演重要角色（例见 [189]）。在本节中我们证明：

定理 8.18 [326] 设 \(P\subset\mathbb{R}^d\) 为齐性集。则 \[g_d(P)=\Omega_d\!\left(|P|^{\,\frac{2}{d}-\frac{1}{d^2}}\right).\]

应当把它与（齐性的）格子例子 \(P=[1,|P|^{1/d}]^d\) 作对比，后者给出 \(g_d(P)=O_d(|P|^{2/d})\)。与定理 8.17 一样，证明从对窄等腰三角形的双重计数论证开始。然而，交叉数以及 Szemerédi–Trotter 型结果在高维中不可用，于是人们改用一种更灵活的技术——单元分解（cell decomposition）。给定一个庞大而复杂的关联系统 \(S\)，我们试图把它打碎成许多小块，使每一块只含少量关联。完成分解之后，一个（往往很巧妙的）关于某个恰当定义的对象的双重计数论证，就会给出相当有效的界。

证明. 我们当然可以假设 \(|P|\ge2\)。由假设，\(P\) 包含于立方体 \(|P|^{1/d}\cdot Q\) 中。令 \(1\le r<|P|^{1/d}\) 为稍后选定的整数。用平行于坐标轴的超平面，我们可以把 \[|P|^{1/d}\cdot Q=C_1\cup\cdots\cup C_{r^d}\] 分割成 \(r^d\) 个小立方体，其中每个 \(C_i\) 是边长为 \(|P|^{1/d}/r\) 的立方体；这些立方体的边界点任意地归入分割中的某一个立方体。我们把这些立方体 \(C_i\) 称为单元（cells）。

对每个 \(p\in P\)，集合 \(P\setminus\{p\}\) 包含于以 \(p\) 为球心的至多 \(g_d(P)\) 个球面之并中。我们用 \(\mathcal{S}_p\) 记这组球面的集合。对每个球面 \(S\in\mathcal{S}_p\)，用 \(\mathcal{C}_S\) 记所有“与 \(S\) 相交且至少含 \(P\) 中一个点”的单元 \(C_i\)；由初等几何可知 \(|\mathcal{C}_S|=O_d(r^{d-1})\)。

现在我们对如下的量施行双重计数论证： \[N:=\bigl|\{(p,S,C,q,q'):p\in P;\,S\in\mathcal{S}_p;\,C\in\mathcal{C}_S;\,q,q'\in P\cap S\cap C;\,q\neq q'\}\bigr|;\] 通俗地说，\(N\) 计数 \(P\) 中那些“底上两点落在同一个单元里”的等腰三角形（参看定理 8.17 的证明）。我们先求上界。注意可选的单元 \(C\) 有 \(r^d\) 个。一个单元的边长为 \(|P|^{1/d}/r>1\)，故由齐性，它含 \(O_d(|P|/r^d)\) 个 \(P\) 中的点。于是可与 \(C\) 相配的点对 \(q,q'\) 有 \(O_d\!\bigl((|P|/r^d)^2\bigr)\) 个。对每个这样的点对，注意 \(p\) 必须落在平分 \(q,q'\) 的超平面上（因为 \(q,q'\) 同在以 \(p\) 为球心的球面上）。再由齐性，这个超平面至多含 \(P\) 的 \(O(|P|^{(d-1)/d})\) 个元素。最后，一旦 \(p,q,q'\) 固定，\(S\) 就完全确定了。把这些合在一起，得到上界 \[N\le r^d\cdot O_d\!\left((|P|/r^d)^2\right)\cdot O\!\left(|P|^{(d-1)/d}\right)=O_d\!\left(|P|^{3-\frac1d}\,r^{-d}\right).\tag{8.6}\]

现在我们求下界。注意到显式公式 \[N=\sum_{p\in P}\sum_{S\in\mathcal{S}_p}\sum_{C\in\mathcal{C}_S}\Bigl(|P\cap S\cap C|^2-|P\cap S\cap C|\Bigr).\] 由 Cauchy–Schwarz 不等式有 \[\sum_{C\in\mathcal{C}_S}|P\cap S\cap C|^2\ge\frac{|P\cap S|^2}{|\mathcal{C}_S|}\] 以及 \[\sum_{S\in\mathcal{S}_p}|P\cap S|^2\ge\frac{(|P|-1)^2}{g_d(P)},\] 从而 \[N\ge\sum_{p\in P}\frac{(|P|-1)^2}{g_d(P)\,|\mathcal{C}_S|}-(|P|-1).\] 由于 \(|\mathcal{C}_S|=O_d(r^{d-1})\)，我们得出 \[N\ge\Omega_d\!\left(\frac{|P|^3}{g_d(P)\,r^{d-1}}-|P|^2\right).\] 把它与 (8.6) 合并并整理，便得出 \[g_d(P)=\Omega_d\!\left(\frac{|P|^3}{r^{d-1}\bigl(|P|^{3-\frac1d}r^{-d}+|P|^2\bigr)}\right).\] 我们通过选取 \(r\) 为最接近 \(|P|^{\,\frac1d-\frac1{d^2}}\) 的整数来优化它，结论随之成立。♦

两次 Cauchy–Schwarz 在干什么下界的诀窍是“把点尽量摊匀时 \(N\) 反而最小”，于是反向用 Cauchy–Schwarz 拿到下界。
  1. 第一次（对单元）：\(\sum_C |P\cap S\cap C|^2\ge (\sum_C|P\cap S\cap C|)^2/|\mathcal{C}_S|=|P\cap S|^2/|\mathcal{C}_S|\)。即“一个球面上的点分散到 \(|\mathcal{C}_S|\) 个单元里，平方和最小也有这么大”。
  2. 第二次（对球面）：\(\sum_S|P\cap S|^2\ge(\sum_S|P\cap S|)^2/|\mathcal{S}_p|=(|P|-1)^2/g_d(P)\)，因为 \(p\) 周围球面数 \(|\mathcal{S}_p|\le g_d(P)\)，而这些球面共盖住 \(|P|-1\) 个点。
  3. 这一步把“相异距离少”（\(g_d\) 小）直接变成“\(N\) 大”的下界，与上界 (8.6) 一夹，就压出 \(g_d\) 的下界。
参数 \(r\) 的最优选择把下界分母里两项对抗。分母 \(=r^{d-1}|P|^{3-1/d}r^{-d}+r^{d-1}|P|^2=|P|^{3-1/d}r^{-1}+|P|^2 r^{d-1}\)。
  1. 第一项随 \(r\) 增大而减小，第二项随 \(r\) 增大而增大。令二者相等：\(|P|^{3-1/d}r^{-1}=|P|^2 r^{d-1}\)，即 \(r^d=|P|^{1-1/d}\)，故 \(r=|P|^{\frac1d-\frac1{d^2}}\)。
  2. 代回得分母 \(\sim|P|^{2+(d-1)^2/d^2}\)，于是 \(g_d\sim|P|^{3}/|P|^{2+(d-1)^2/d^2}=|P|^{1-(d-1)^2/d^2}\)。
  3. 而 \(1-\dfrac{(d-1)^2}{d^2}=\dfrac{d^2-(d-1)^2}{d^2}=\dfrac{2d-1}{d^2}=\dfrac2d-\dfrac1{d^2}\)，正是定理 8.18 的指数。
\(p\) 大立方体 边长 ~\(|P|^{1/d}\) 切成 \(r^d\) 个单元， 每个边长 \(|P|^{1/d}/r\) 一个球面 \(S\) 只穿过 \(O_d(r^{d-1})\) 个单元
单元分解：把容纳所有点的大立方体均匀切成 \(r^d\) 个小立方体（单元）。以 \(p\) 为球心的一个球面只会“掠过”其中 \(O_d(r^{d-1})\) 个单元——这就把全局的复杂关联拆成了每块少量关联，便于双重计数。

一般高维情形与更精细的分解

对 \(d\ge3\) 且一般的（非齐性的）点集，长期以来人们所知甚少，因为基于 Szemerédi–Trotter 定理的方法无法推广到大于 \(2\) 的维数。Clarkson、Edelsbrunner、Guibas、Sharir 与 Welzl [63] 证明了 \(g_3(n)=\Omega(n^{1/2})\)。2002 年，Aronov、Pach、Sharir 与 Tardos [14] 证明了对任意 \(\varepsilon>0\) 有 \(g_3(n)=\Omega(n^{77/141-\varepsilon})\)。更一般地，他们证明了对任意 \(d\ge3\) 有 \[g_d(n)=\Omega_{d,\varepsilon}\!\left(n^{1/(d-90/77)-\varepsilon}\right).\] 与此前的界 \(n^{1/d}\) 相比，这个结果对较小的 \(d\) 给出了非平凡的改进。另一方面，当 \(d\to\infty\) 时，指数 \(1/(d-90/77)-\varepsilon\) 收敛到 \(1/d\)，而非所猜测的 \(2/d\)。

最近，Solymosi 与 Vu [327] 设法证明了：指数 \(2/d\) 在最高阶意义下是最优的，即它不能被任何 \((2-\varepsilon+o_{d\to\infty}(1))/d\)（\(\varepsilon>0\) 为正常数）所取代。更确切地说，他们证明了对所有 \(d\ge4\) 有 \[g_d(n)=\Omega_d\!\left(n^{\frac2d-\frac{2}{d(d+2)}}\right),\] 并且 \(g_3(n)=\Omega(n^{0.5643})\)。

这个结果以及前面 Aronov 等人的界，都是用分解方法结合其他论证证明的。与齐性的情形不同，这里所用的分解更为精巧，它最早由 Chazelle 与 Friedman [52] 发展出来（另见 [245]），其动机来自计算机科学中的几何检索问题。让我们以简要讨论这个结果来结束本节。

进行检索的主要技术之一是分治（divide-and-conquer）。在许多问题中，情形如下：给定 \(\mathbb{R}^d\) 中一组超平面 \(B\)（余维为 \(1\)），人们希望把 \(\mathbb{R}^d\) 分割成不太多的若干部分，使每一部分只与少量超平面相交。

定义 8.19 称一个超平面 \(H\) 强相交（strongly intersects）于集合 \(P\)，若 \(H\cap P\) 非空，并且 \(P\) 在 \(H\) 的两侧都有点。
为什么要“强”相交普通的“相交”只要求 \(H\) 碰到 \(P\) 里的点；但若 \(P\) 整块落在 \(H\) 的一侧，\(H\) 只是擦着边、并没有把 \(P\) 真正切开。“强相交”要求两侧都有点，才算 \(H\) 实质地分割了 \(P\)。这个拓扑条件用来排除一些极端情形——例如所有超平面都通过同一个点（此时它们能同时“碰到”很多区域，却没真正切开各区域）。
\(H\) 强相交：两侧都有点 ✓ \(H\) 点都在一侧：非强相交 ✗
左：超平面 \(H\) 两侧都有 \(P\) 的点，是强相交（真正切开 \(P\)）。右：\(P\) 全在一侧，不算强相交。
引理 8.20 设 \(B\) 是 \(\mathbb{R}^d\) 中 \(k\) 个超平面构成的集合。对任意 \(1\le r\le k\)，可以把 \(\mathbb{R}^d\) 分割成 \(r\) 个集合 \(P_1,\dots,P_r\)，使得对每个 \(1\le i\le r\)，强相交于 \(P_i\) 的超平面只有 \(O(k/r^{1/d})\) 个。

界 \(O(k/r^{1/d})\) 是最优的；\(O\) 中隐藏的常数依赖于 \(d\)，但不依赖于 \(r\)。还可以保证这些集合 \(P_i\) 是广义单纯形（generalized simplices）。强相交实际上指的是与内部相交（见 [245]）。现在让我们考虑稍微复杂一点的情形：除了 \(B\) 之外，我们还有一个由 \(n\) 个点构成的集合 \(A\)。我们可以额外要求每一部分含有不太多的点。

引理 8.21 设 \(A\) 是 \(n\) 个点构成的集合，\(B\) 是 \(\mathbb{R}^d\) 中 \(k\) 个超平面构成的集合。对任意 \(1\le r\le k\)，可以把 \(\mathbb{R}^d\) 分割成 \(r\) 个集合 \(P_1,\dots,P_r\)，使得对每个 \(1\le i\le r\)，有 \(|P_i\cap A|\le 2n/r\)，并且 \(P_i\) 强相交于 \(O(k/r^{1/d})\) 个超平面。

引理 8.21 并不局限于超平面。若把一族超平面替换为满足某些拓扑条件的一族曲面，它仍然成立。特别地，若把超平面替换为（满维的）球面，引理依然成立（见 [245] 第 6.5 节）。作为引理 8.21 的类比，我们得到下面的引理，它正是 [327] 中所实际使用的。

定义 8.22 称一个球面 \(S\) 强相交于集合 \(P\)，若 \(S\cap P\) 非空，并且 \(P\) 在 \(S\) 的两侧（球内与球外）都有点。
引理 8.23 设 \(A\) 是 \(n\) 个点构成的集合，\(B\) 是 \(\mathbb{R}^d\) 中 \(k\) 个球面构成的集合。对任意 \(1\le r\le k\)，可以把 \(\mathbb{R}^d\) 分割成 \(r\) 个集合 \(P_1,\dots,P_r\)，使得对每个 \(1\le i\le r\)，有 \(|P_i\cap A|=O(n/r)\)，并且强相交于 \(P_i\) 的球面只有 \(O(k/r^{1/d})\) 个。
\(P_i\) 绿虚线：把空间切成 \(r\) 块；红线/曲线：超平面或球面（共 \(k\) 个）
分解引理的图景：把 \(\mathbb{R}^d\) 切成 \(r\) 块，使每块只被 \(O(k/r^{1/d})\) 个超平面（或球面）强相交，且每块只含 \(O(n/r)\) 个 \(A\)-点。这就把“\(k\) 个曲面、\(n\) 个点”的大问题降为 \(r\) 个小问题。

如果能有上述引理在有限域上的类比，那将非常理想。问题的最简单形式是：给定有限平面上一组直线（或简单曲线），我们希望把平面分割成少数几部分，使每一部分只与少量直线相交。这里主要的障碍在于：人们需要为“强相交”这一拓扑条件找到一个恰当的替代物。这个条件原本是用来排除一些极端情形的，例如所有超平面都通过同一个点的情形。

习题

习题 8.4.1 设 \(A\) 为非空的有限实数集合。证明 \(\bigl|k\bigl((A-A)^{\wedge2}\bigr)\bigr|\ge g_k(|A|^2)\)，其中 \(X^{\wedge2}:=\{x^2:x\in X\}\) 是 \(X\) 中元素平方所成的集合，而 \(kX:=X+\cdots+X\) 是 \(X\) 的 \(k\)-重和集。因此，Erdős 距离问题上的进展与和–积型问题上的进展相联系；关于这一想法的进一步发展见 [43]。
习题 8.4.2 [83] 设 \(x_1,\dots,x_d\) 为 \(\mathbb{R}^d\) 中处于一般位置的 \(d\) 个点。证明：若 \(x\in\mathbb{R}^d\)，则这 \(d\) 个距离 \(|x-x_1|,\dots,|x-x_d|\) 在至多 \(O_d(1)\) 的重数意义下确定 \(x\)。利用这一点证明对所有 \(n\) 有 \(g_d(n)=\Omega_d(n^{1/d})\)。（注意：许多点落在某个低维空间中的退化情形可以用归纳论证来处理。）
习题 8.4.3 [326]（三维中的富直线） 设 \(P\) 为 \(\mathbb{R}^3\) 中的齐性集。证明：对所有 \(k\ge2\) 有 \[\sum_{l:\,|l\cap P|\ge k}|l\cap P|=O\!\left(|P|^2/k^3\right).\]
习题 8.4.4 [326] 设 \(A\) 为 \(\mathbb{R}^3\) 中基数为 \(n\) 的齐性集，\(\mathcal{P}\) 为 \(D\) 个两两不平行的平面构成的集合。则存在一个平面 \(P\in\mathcal{P}\)……（原文至此截断。）

返回 全书目录