塞迈雷迪-特罗特定理

塞迈雷迪－特罗特定理为组合几何的定理，其断言给定欧氏平面上任意$n$个点和$m$条直线，至多发生

$$O \left ( n^{\frac{2}{3}} m^{\frac{2}{3}} + n + m \right )$$

次重合（incidence，即二元组$(p, \ell)$，其中$p$为一点，$\ell$为直线，且$p$在$\ell$上）。

此上界已经是最优的上界了，唯一的改进只可能出现在大O符号中隐藏的常数倍数。

考虑隐藏常数的话，保奇·亚诺什、拉多什·拉多伊契奇（Radoš Radoičić）、陶尔多什·加博尔、托特·盖萨四人给出上界$2.5n^{2/3} m^{2/3} + n + m$。此后，由于交叉数不等式的常数得到改进，塞迈雷迪－特罗特定理的常数也相应得到改进。截至2019年末，最优的常数是$2.44$。另一方面，保奇和托特证明，若将上式的常数$2.5$换成$0.42$，则不再为重合数的上界。

定理也有以下等价形式：若给定$n$个点和整数$k\ge 2$，则经过至少$k$个点的直线数至多为

$$O \left( \frac{n^2}{k^3} + \frac{n}{k} \right ).$$

定理得名自塞迈雷迪·安德烈和威廉·特罗特，其最先的证明较复杂，用到称为“胞分解”（cell decomposition）的组合技巧。其后，塞凯利·拉兹洛（Székely László）利用图的交叉数不等式，给出更简单的证明，详见下文。

塞迈雷迪－特罗特定理可推导出若干其他定理，例如重合几何的贝克定理和算术组合学的艾狄胥－塞迈雷迪和积定理。

## 第一形式的证明

先考虑仅经过至多两点的直线。该些直线产生的重合数至多为$2m$。于是现在仅需考虑余下的直线，而该些直线每条经过至少三点。

若一条直线上恰有$k$个点，则该些点将直线截断成$k-1$条线段（不计首尾仅得一端点的射线）。由于假设$k\ge 3$（已无须考虑仅经过至多两点的直线），有$k-1 \ge k/2$，即每条直线截成的线段数至少为其上点数之半。对所有直线求和，可知该些线段的总数$e$亦至少为总重合数之半，从而只需证明

$$e = O \left ( n^{\frac{2}{3}} m^{\frac{2}{3}} + n + m \right).$$

以该$n$点为顶点，并以该$e$条线段为边建图。每条线段皆为$m$条直线中某一条的部分，且每两条直线交于至多一点，故图的交叉数至多为$m(m-1)/2$。再由交叉数不等式知，或者有$e \le 7.5 n$，或者有$m(m-1)/2 \ge e^3/33.75 n^2$。两者皆推出$e \le 3.24(nm)^{2/3} + 7.5n$，从而得到上界

$$e = O \left ( n^{\frac{2}{3}} m^{\frac{2}{3}} + n + m \right ).$$

## 第二形式的证明

因为过两点至多只有一条直线，且$k \ge 2$，所以经过至少$k$个点的直线至多只有$n(n-1)/2$条。若$k$很小（$k$小于某个绝对常数$C$），则此上界$n(n-1)/2$已足以证明定理的第二形式。于是，以下仅需考虑$k$较大的情况（$k\ge C$）。

设经过至少$k$个点的直线恰有$m$条直线，则其上至少有$mk$次重合，故由定理的第一形式，得

$$mk = O \left ( n^{\frac{2}{3}} m^{\frac{2}{3}} + n + m \right ),$$

所以$mk = O( n^{2/3} m^{2/3} )$、$mk = O(n)$、$mk = O(m)$三式至少有一式成立。第三式不可能，因为已设$k$为大，所以必有前两者之一。但经初等运算可知，前两者皆推出$m = O( n^2 / k^3 + n/k )$。

## 取到上界的例子

若不考虑上界隐含的常数，则塞迈雷迪－特罗特定理的上界已是最优。使重合数达到上界的例子如下：对任意正整数$N\in \mathbb{N}$，考虑整数格点集

$$P = \left \{ (a, b) \in \mathbb{Z}^2 \ : \ 1 \leq a \leq N; 1 \leq b \leq 2N^2 \right \},$$

和一族直线

$$L = \left \{ (x, mx + b) \ : \ m, b \in \mathbb{Z}; 1 \leq m \leq N; 1 \leq b \leq N^2 \right \}.$$

于是，有$|P| = 2N^3$个点和$|L| = N^3$条直线。由于每条直线都通过$N$点（每个$x \in \{1, \cdots, N\}$)对应一点），总重合数为$N^4$，已达上界$O(N^4+N^3+N^3) = O(N^4)$。

## 高维推广

潘卡杰·阿加尔瓦尔及鲍里斯·阿洛诺夫发现定理的高维推广：给定$d$维空间$\mathbb{R}^d$的$n$点（记其集合为$S$）和$m$个（$d-1$维）超平面（记其集合为$H$），则$S$和$H$之间的重合数有上界

$$O \left (m^{\frac{2}{3}}n^{\frac{d}{3}}+n^{d-1} \right ).$$

也可以等价写成：$H$中通过至少$k$个点的超平面数目至多为

$$O\left( \frac{n^d}{k^3} + \frac{n^{d-1}}{k} \right ).$$

赫伯特·埃德斯布伦内给出了渐近最优的构造，从而上述上界亦不能再改进。

绍利莫希·约瑟夫和陶哲轩考虑点和高维代数簇的情况，并在其满足“某些拟直线（pseudo-line）类公设”的情况下，得到近乎最优的重合数上界。其证明运用到多项式火腿三文治定理。

## 复二维平面

实域$\mathbb{R}$上的塞迈雷迪－特罗特定理有若干证明依赖欧几里得空间的拓扑，所以不能直接推广到其他域上，塞迈雷迪和特罗特的原证明、多项式分割法、交叉数法皆属此类，其不能适用于复域上的平面$\mathbb{C}^2$。

托特·乔鲍（Tóth Csaba）将塞迈雷迪和特罗特的原证明推广到$\mathbb{C}^2$。乔书亚·扎尔（Joshua Zahl）利用另一个方法，也独立地证明此结论。然而，其所得的上界的隐含常数与实域的情况有异：托特证明了该常数可取为$10^{60}$，而扎尔的证明并无给出具体的常数。

若限定点集为笛卡儿积，则绍利莫希·约瑟夫和陶尔多什·加博尔更简单地证明了塞迈雷迪－特罗特上界仍成立。

## 有限域上

在一般域$\mathbb{F}$上，塞迈雷迪－特罗特上界不一定成立。例如：取有限域$\mathbb{F}_p$的二维平面上全部$p^2$个点的集合$\mathcal{P} = \mathbb{F}_p\times \mathbb{F}_p$，又取全部$p^2$条直线的集合$\mathcal{L}$，则每条直线经过$p$个点，故有$p^3$次重合。另一方面，塞迈雷迪－特罗特上界仅为$O\left((p^2)^{2/3} (p^2)^{2/3} + p^2\right) = O(p^{8/3})$。此例子说明平凡上界$mn$已为最优。

让·布尔甘、内茨·卡茨、陶哲轩三人证明，除此例子外，平凡上界可以改进。

有限域上的重合数大致分为两类：

- 点数与直线数有一者“远大于”域的特征。
- 两者与域的特征相比皆“不太大”。

### 点集或直线集大的情况

设$q$为奇质数幂。黎英荣（Lê Anh Vinh）证明，$\mathbb{F}_q^2$上$n$点与$m$条直线的重合数至多为

$$\frac{nm}{q} + \sqrt{qnm}.$$

且上式并无隐含常数。

### 点集及直线集皆不大的情况

设$\mathbb{F}$为域，且其特征为$p\neq 2$。苏菲·史蒂文斯（Sophie Stevens）和弗兰克·德齐乌（Frank de Zeeuw）证明，若$m^{-2}n^{13} \leq p^{15}$（$p=0$时无需此条件），则$\mathbb{F}^2$上$n$点和$m$条直线的重合数至多为

$$O\left(m^{\frac{11}{15}}n^{\frac{11}{15}}\right).$$

$m^{7/8} < n < m^{8/7}$时，此上界比塞迈雷迪－特罗特上界更优。

若限定点集为笛卡儿积，则其证明以下更佳的上界：证$\mathcal{P} = A\times B \subseteq \mathbb{F}^2$为有限点集，其中$|A|\leq |B|$，又设$\mathcal{L}$为平面上有限条直线的集合。假设$|A||B|^2 \leq |\mathcal{L}|^3$，而若特征为正就再加上条件$|A||\mathcal{L}|\leq p^2$，则$\mathcal{P}$和$\mathcal{L}$组成的重合数至多为

$$O\left(|A|^{\frac34}|B|^{\frac12} |\mathcal{L}|^\frac34 + |\mathcal{L}| \right).$$

此上界为最优。由于平面有点线对偶，也可以将上述定理中，点和线的角色互换，得到对偶版本，适用于直线集为笛卡儿积、点集任意的情况。

米沙·鲁德涅夫（Misha Rudnev）和伊利亚·什克列多夫（Ilya D. Shkredov）研究了点集和直线集皆为笛卡儿积的情况（不论在实域或任意域），给出该情况下重合数的上界。此上界有时优于上列其他上界。