塞邁雷迪-特羅特定理

塞邁雷迪－特羅特定理為組合幾何的定理，其斷言給定歐氏平面上任意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} 時，此上界比塞邁雷迪－特羅特上界更優。

若限定點集為笛卡兒積，則其證明以下更佳的上界：證\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）研究了點集和直線集皆為笛卡兒積的情況（不論在實域或任意域），給出該情況下重合數的上界。此上界有時優於上列其他上界。

參考資料