塞邁雷迪-特羅特定理

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

塞邁雷迪－特羅特定理為組合幾何的定理，其斷言給定歐氏平面上任意${\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]給出該情況下重合數的上界。此上界有時優於上列其他上界。