塞邁雷迪-特羅特定理

塞邁雷迪－特羅特定理為組合幾何的定理，其斷言給定歐氏平面上任意$n$個點和$m$條直線，至多發生

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

次重合（incidence，即二元組$(p,\ell )$，其中$p$為一點，$\ell$為直線，且$p$在$\ell$上）。

此上界已經是最優的上界了，唯一的改進只可能出現在大O符號中隱藏的常數倍數。

考慮隱藏常數的話，Template:Le、拉多什·拉多伊契奇（Radoš Radoičić）、Template:Le、Template:Le四人給出上界$2.5n^{2/3}{m}^{2/3}+n+m$。此後，由於交叉數不等式的常數得到改進，塞邁雷迪－特羅特定理的常數也相應得到改進。截至2019年末，最優的常數是$2.44$。 另一方面，保奇和托特證明，若將上式的常數$2.5$換成$0.42$，則不再為重合數的上界。

定理也有以下等價形式：若給定$n$個點和整數$k\ge 2$，則經過至少$k$個點的直線數至多為

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

定理得名自塞邁雷迪·安德烈和Template:Le，其最先的證明較複雜，用到稱為「胞分解」（cell decomposition）的組合技巧。其後，塞凱利·拉茲洛（Székely László）利用圖的交叉數不等式，給出更簡單的證明， 詳見下文。

塞邁雷迪－特羅特定理可推導出若干其他定理，例如重合幾何的Template:Le和Template:Le的Template:Le。

第一形式的證明

先考慮僅經過至多兩點的直線。該些直線產生的重合數至多為$2m$。於是現在僅需考慮餘下的直線，而該些直線每條經過至少三點。

若一條直線上恰有$k$個點，則該些點將直線截斷成$k-1$條線段（不計首尾僅得一端點的射線）。由於假設$k\ge 3$（已無須考慮僅經過至多兩點的直線），有$k-1\ge k/2$，即每條直線截成的線段數至少為其上點數之半。對所有直線求和，可知該些線段的總數$e$亦至少為總重合數之半，從而只需證明

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

以該$n$點為頂點，並以該$e$條線段為邊建圖。每條線段皆為$m$條直線中某一條的部分，且每兩條直線交於至多一點，故圖的交叉數至多為$m(m-1)/2$。再由交叉數不等式知，或者有$e\le 7.5n$，或者有$m(m-1)/2\ge e^3/33.75n^2$。兩者皆推出$e\le 3.24(nm{)}^{2/3}+7.5n$，從而得到上界

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

第二形式的證明

因為過兩點至多只有一條直線，且$k\ge 2$，所以經過至少$k$個點的直線至多只有$n(n-1)/2$條。若$k$很小（$k$小於某個絕對常數$C$），則此上界$n(n-1)/2$已足以證明定理的第二形式。於是，以下僅需考慮$k$較大的情況（$k\ge C$）。

設經過至少$k$個點的直線恰有$m$條直線，則其上至少有$mk$次重合，故由定理的第一形式，得

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

所以$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=\{(a,b)\in {\mathbb{Z}}^2:1\le a\le N;1\le b\le 2N^2\},$

和一族直線

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

於是，有$|P|=2N^3$個點和$|L|=N^3$條直線。由於每條直線都通過$N$點（每個$x\in \{1,\cdots ,N\}$)對應一點），總重合數為$N^4$，已達上界$O(N^4+N^3+N^3)=O(N^4)$。

高維推廣

Template:Le及Template:Le發現定理的高維推廣：給定$d$維空間${ℝ}^d$的$n$點（記其集合為$S$）和$m$個（$d-1$維）超平面（記其集合為$H$），則$S$和$H$之間的重合數有上界

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

也可以等價寫成：$H$中通過至少$k$個點的超平面數目至多為

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

Template:Le給出了漸近最優的構造，從而上述上界亦不能再改進。

Template:Le和陶哲軒考慮點和高維代數簇的情況，並在其滿足「某些擬直線（pseudo-line）類公設」的情況下，得到近乎最優的重合數上界。其證明運用到Template:Le。

複二維平面

實域$ℝ$上的塞邁雷迪－特羅特定理有若干證明依賴歐幾里得空間的拓撲，所以不能直接推廣到其他域上，塞邁雷迪和特羅特的原證明、多項式分割法、交叉數法皆屬此類，其不能適用於複域上的平面${ℂ}^2$。

托特·喬鮑（Tóth Csaba）將塞邁雷迪和特羅特的原證明推廣到${ℂ}^2$。喬書亞·扎爾（Joshua Zahl）利用另一個方法，也獨立地證明此結論。然而，其所得的上界的隱含常數與實域的情況有異：托特證明了該常數可取為$10^{60}$，而扎爾的證明並無給出具體的常數。

若限定點集為笛卡兒積，則Template:Le和Template:Le更簡單地證明了塞邁雷迪－特羅特上界仍成立。

有限域上

在一般域$𝔽$上，塞邁雷迪－特羅特上界不一定成立。例如：取有限域${𝔽}_p$的二維平面上全部$p^2$個點的集合$𝒫={𝔽}_p\times {𝔽}_p$，又取全部$p^2$條直線的集合$ℒ$，則每條直線經過$p$個點，故有$p^3$次重合。另一方面，塞邁雷迪－特羅特上界僅為$O((p^2{)}^{2/3}(p^2{)}^{2/3}+p^2)=O(p^{8/3})$。此例子說明平凡上界$mn$已為最優。

讓·布爾甘、Template:Le、陶哲軒三人證明，除此例子外，平凡上界可以改進。

有限域上的重合數大致分為兩類：

1. 點數與直線數有一者「遠大於」域的特徵；
2. 兩者與域的特徵相比皆「不太大」。

點集或直線集大的情況

設$q$為奇質數冪。黎英榮（Lê Anh Vinh）證明，${𝔽}_q^2$上$n$點與$m$條直線的重合數至多為

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

且上式並無隱含常數。

點集及直線集皆不大的情況

設$𝔽$為域，且其特徵為$p\ne 2$。蘇菲·史蒂文斯（Sophie Stevens）和弗蘭克·德齊烏（Frank de Zeeuw）證明，若$m^{-2}{n}^{13}\le p^{15}$（$p=0$時無需此條件），則${𝔽}^2$上$n$點和$m$條直線的重合數至多為

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

$m^{7/8}<n<m^{8/7}$時，此上界比塞邁雷迪－特羅特上界更優。

若限定點集為笛卡兒積，則其證明以下更佳的上界：證$𝒫=A\times B\subseteq {𝔽}^2$為有限點集，其中$|A|\le |B|$，又設$ℒ$為平面上有限條直線的集合。假設$|A||B{|}^2\le |ℒ{|}^3$，而若特徵為正就再加上條件$|A||ℒ|\le p^2$，則$𝒫$和$ℒ$組成的重合數至多為

$O(|A{|}^{\frac{3}{4}}|B{|}^{\frac{1}{2}}|ℒ{|}^{\frac{3}{4}}+|ℒ|).$

此上界為最優。由於平面有Template:Le，也可以將上述定理中，點和線的角色互換，得到對偶版本，適用於直線集為笛卡兒積、點集任意的情況。

米沙·魯德涅夫（Misha Rudnev）和伊利亞·什克列多夫（Ilya D. Shkredov）研究了點集和直線集皆為笛卡兒積的情況（不論在實域或任意域），給出該情況下重合數的上界。此上界有時優於上列其他上界。