塞迈雷迪-特罗特定理

塞迈雷迪－特罗特定理为组合几何的定理，其断言给定欧氏平面上任意$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\geq 2$，则经过至少$k$个点的直线数至多为

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

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

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

第一形式的证明

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

若一条直线上恰有$k$个点，则该些点将直线截断成$k-1$条线段（不计首尾仅得一端点的射线）。由于假设$k\geq 3$（已无须考虑仅经过至多两点的直线），有$k-1\geq 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\leq 7.5n$，或者有$m(m-1)/2\geq e^{3}/33.75n^{2}$。两者皆推出$e\leq 3.24(nm)^{2/3}+7.5n$，从而得到上界

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

第二形式的证明

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

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

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

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

点集或直线集大的情况

设$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|^{\frac {3}{4}}|B|^{\frac {1}{2}}|{\mathcal {L}}|^{\frac {3}{4}}+|{\mathcal {L}}|\right).$

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

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