2. 重合几何

另一个与和积问题相关的数学领域是重合几何. 点集 $\mathcal{P}$ 和线集 $\mathcal{L}$ 之间的 “重合关系” 定义为$$I(\mathcal{P},\mathcal{L})=|\{(p,\ell )\in \mathcal{P}\times \mathcal{L}:p\in \ell \}|$$$n$ 个点和 $n$ 条线之间发生重合的次数最大是多少? 一个简单的上界是 $|\mathcal{P}||\mathcal{L}|$. 事实上, 注意到每一对点最多由一条线确定, 基于此我们可以获得更好的上界: $$\begin{array}{rl}|\mathcal{P}{|}^2& \ge \#\left\{\left(p,p^{\prime },\ell \right)\in \mathcal{P}\times \mathcal{P}\times \mathcal{L}:p{p}^{\prime }\in \ell ,p\ne p^{\prime }\right\}\\ & \ge \sum _{\ell \in \mathcal{L}}|\mathcal{P}\cup \ell |(|\mathcal{P}\cup \ell |-1)\\ & \ge \frac{I(\mathcal{P},\mathcal{L}{)}^2}{|\mathcal{L}|}-I(\mathcal{P},\mathcal{L})\end{array}$$最后一个不等号来自 Cauchy-Schwarz 不等式. 因此, 我们得到 $I(\mathcal{P},\mathcal{L})\le |\mathcal{P}||\mathcal{L}{|}^{1/2}+|\mathcal{L}|$. 由点和线的对偶性, 我们也有 $I(\mathcal{P},\mathcal{L})\le |\mathcal{L}||\mathcal{P}{|}^{1/2}+|\mathcal{P}|$. 这些不等式告诉我们 $n$ 点和 $n$ 线的发生重合次数为 $O\left(n^{3/2}\right)$ . 在第一章中我们已经知道 $\mathrm{ex}\left(n,C_4\right)=\Theta \left(n^{3/2}\right)$, 这与我们的预期是相符的 (我们可以将点和线看作是二部图) . 回想一下, 第一章中的构造来自有限域, 并且上界是紧的. 但是, 在实际平面中, $n^{3/2}$ 并不紧, 我们将在下一个定理中看到.

定理 2.1 (Szemerédi-Trotter 1983). 对于任意 ${\mathbb{R}}^2$ 上的点集 $\mathcal{P}$ 和线集 $\mathcal{L}$ , $$I(\mathcal{P},\mathcal{L})=O\left(|\mathcal{P}{|}^{2/3}|\mathcal{L}{|}^{2/3}+|\mathcal{P}|+|\mathcal{L}|\right)$$

推论 2.2. 对于 ${\mathbb{R}}^2$ 上 $n$ 个点和 $n$ 条线, 重合的次数为 $O\left(n^{4/3}\right)$.

例 2.3. 下面我们给出一个示例, 用于说明推论 2.2 的上界是紧的. 令 $\mathcal{P}=[k]\times \left[2k^2\right]$ 和 $\mathcal{L}=\{y=mx+b$ : $m\in [k],b\in \left[k^2\right]\}$. 则 $\mathcal{L}$ 中的每一条线都包含 $\mathcal{P}$ 中 $k$ 个顶点, 所以 $I=k^4=\Theta \left(n^{4/3}\right)$.

定理 2.1.

我们首先去掉 $\mathcal{L}$ 中所有最多包含 $\mathcal{P}$ 中一个点的线. 可以看到, 这些线最多能够造成 $|\mathcal{L}|$ 次重合.

现在我们可以假设 $\mathcal{L}$ 中的每一条线至少包含 $\mathcal{P}$ 中的两个点. 我们构造一个图 $G$ 如下: 首先, 顶点为 $\mathcal{P}$ 中的所有点. 对于 $\mathcal{L}$ 中的每条线, 我们在位于该线上的 $\mathcal{P}$ 的相邻点之间分配一条边. 见图 ??.

(...) 图 $G$ 的构造

因为一条经过 $k$ 个顶点的线最多有 $k-1\ge k/2$ 条边, 所以我们有不等式 $|E|\ge I(\mathcal{P},\mathcal{L})/2$. 我们假设 $I(\mathcal{L},\mathcal{P})\ge 8|\mathcal{P}|$ 成立 (否则有 $I(\mathcal{P},\mathcal{L})\lesssim |\mathcal{P}|$ ) , 根据定理 1.1 有$$\mathrm{cr}(G)\gtrsim \frac{|E{|}^3}{|V{|}^2}\ge \frac{I(\mathcal{P},\mathcal{L}{)}^3}{|\mathcal{P}{|}^2}$$此外, 因为每两条线最多相交于一个点, 所以 $\mathrm{cr}(G)\le |\mathcal{L}{|}^2$. 我们整理得到 $I(\mathcal{P},\mathcal{L})\lesssim |P{|}^{2/3}|L{|}^{2/3}$. 因此我们得到 $I(\mathcal{P},\mathcal{L})\lesssim |\mathcal{P}{|}^{2/3}|\mathcal{L}{|}^{2/3}+|\mathcal{P}|+|\mathcal{L}|$. 两个线性的部分分别是考虑到开始时去掉的线和假设 $I(\mathcal{L},\mathcal{P})\ge 8|\mathcal{P}|$.

$\square$

当我们在定理 1.1 的证明中应用欧拉公式时, 我们使用了实平面的拓扑性质. 现在我们将展示一个关于和积问题如何与重合几何相关联的例子.

定理 2.4 (Elekes 1997). 如果 $A\subset \mathbb{R}$, 则 $|A+A||A\cdot A|\gtrsim |A{|}^{5/2}$

推论 2.5. 如果 $A\subset \mathbb{R}$, 则 $\max \{|A+A|,|A\cdot A|\}\gtrsim |A{|}^{5/4}$

定理 2.4 的证明. 令 $\mathcal{P}=\{(x,y):x\in A+A,y\in A\cdot A\}$ 和 $\mathcal{L}=\left\{y=a\left(x-a^{\prime }\right):a,a^{\prime }\in A\right\}$. 考虑 $\mathcal{L}$ 中的任一条线 $y=a\left(x-a^{\prime }\right)$ , 对于所有 $b\in A$, $\left(a^{\prime }+b,ab\right)\in \mathcal{P}$ 都在这条线上, 所以 $\mathcal{L}$ 中的每一条线都包含 $|A|$ 次重合. 根据 $\mathcal{P}$ 和 $\mathcal{L}$ 的定义, 我们有$$|\mathcal{P}|=|A+A||A\cdot A|,|\mathcal{L}|=|A{|}^2$$回顾定理 2.1, 我们得到$$\begin{array}{rl}|A{|}^3\le I(\mathcal{P},\mathcal{L})& \le |\mathcal{P}{|}^{3/2}|\mathcal{L}{|}^{3/2}+|\mathcal{P}|+|\mathcal{L}|\\ & \lesssim |A+A{|}^{3/2}|A\cdot A{|}^{3/2}|A{|}^{4/3}\end{array}$$整理后即得到我们想要的不等式.

$\square$