塞迈雷迪-特罗特定理

匈牙利语人名顺序为先姓后名。此条目中的译名遵从此顺序。

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

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

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

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

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

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

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

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

塞迈雷迪－特罗特定理可推导出若干其他定理，例如重合几何的贝克定理（英语：Beck's theorem (geometry)）和算术组合学（英语：Arithmetic combinatorics）的艾狄胥－塞迈雷迪和积定理（英语：Erdős–Szemerédi theorem）。

第一形式的证明

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

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

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

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

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

第二形式的证明

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

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

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

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

取到上界的例子

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

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

和一族直线

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

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

高维推广

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

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

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

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

赫伯特·埃德斯布伦内（英语：Herbert Edelsbrunner）给出了渐近最优的构造，从而上述上界亦不能再改进。^[9]

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

复二维平面

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

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

若限定点集为笛卡儿积，则绍利莫希·约瑟夫（英语：József Solymosi）和陶尔多什·加博尔（英语：Gábor Tardos）更简单地证明了塞迈雷迪－特罗特上界仍成立。^[13]

有限域上

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

让·布尔甘、内茨·卡茨（英语：Nets Katz）、陶哲轩三人^[14]证明，除此例子外，平凡上界可以改进。

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

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

点集或直线集大的情况

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

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

且上式并无隐含常数。

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

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

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

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

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

${\displaystyle O\left(|A|^{\frac {3}{4}}|B|^{\frac {1}{2}}|{\mathcal {L}}|^{\frac {3}{4}}+|{\mathcal {L}}|\right).}$

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

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