查看“︁塞邁雷迪-特羅特定理”︁的源代码

{{Eastern name order|匈牙利语|匈牙利人名}}

'''塞邁雷迪－特羅特定理'''為[[組合幾何]]的定理，其斷言給定[[歐幾里得空間|歐氏平面]]上任意<math>n</math>個[[點]]和<math>m</math>條[[直線]]，至多發生

:<math>O \left ( n^{\frac{2}{3}} m^{\frac{2}{3}} + n + m \right )</math>

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

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

考慮隱藏常數的話，{{le|保奇·亞諾什|János Pach}}<!--依[[WP:外語譯音表/匈牙利語]]暫譯-->、拉多什·拉多伊契奇（Radoš Radoičić）<!--似乎是波黑人，依[[WP:外語譯音表/塞爾維亞語]]暫譯-->、{{le|陶爾多什·加博爾|Gábor Tardos}}、{{le|托特·蓋薩|Géza Tóth}}<!--依[[匈牙利人名]]Tóth和[[蓋薩大公]]的先例-->四人<ref>{{cite journal | last1=Pach | first1=János  |first2=Radoš|last2= Radoičić |last3=Tardos | first3=Gábor | last4=Tóth | first4=Géza |year=2006 | title=Improving the Crossing Lemma by Finding More Crossings in Sparse Graphs | journal=Discrete & Computational Geometry| volume = 36 | issue = 4 | pages = 527–552 | doi=10.1007/s00454-006-1264-9| doi-access=free |language=en}}</ref>給出上界<math> 2.5n^{2/3} m^{2/3} + n + m</math>。此後，由於[[交叉數不等式]]的常數得到改進，塞邁雷迪－特羅特定理的常數也相應得到改進。截至2019年末，最優的常數是<math>2.44</math>。<ref>{{Cite journal|last=Ackerman|first=Eyal|date=December 2019|title=On topological graphs with at most four crossings per edge|url=http://dx.doi.org/10.1016/j.comgeo.2019.101574|journal=Computational Geometry|volume=85|pages=101574|doi=10.1016/j.comgeo.2019.101574|issn=0925-7721 |language = en}}</ref> 另一方面，保奇和托特證明，若將上式的常數<math>2.5</math>換成<math>0.42</math>，則不再為重合數的上界。<ref>{{cite journal|last1=Pach|first1=János|last2=Tóth|first2=Géza|year=1997|title=Graphs drawn with few crossings per edge|url=https://archive.org/details/sim_combinatorica_1997_17_3/page/427|journal=Combinatorica|volume=17|issue=3|pages=427–439|doi=10.1007/BF01215922 |language = en}}</ref>

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

:<math>O \left( \frac{n^2}{k^3} + \frac{n}{k} \right ).</math>

定理得名自[[塞邁雷迪·安德烈]]和{{le|威廉·特羅特|William T. Trotter}}，其最先的證明較複雜，用到稱為「胞分解」（cell decomposition）的組合技巧。<ref name="Szemerédi">{{cite journal|last1=Szemerédi|first1=Endre|last2=Trotter|first2=William T.|year=1983|title=Extremal problems in discrete geometry|journal=Combinatorica|volume=3|issue=3–4|pages=381–392|doi=10.1007/BF02579194|mr=0729791|authorlink1=塞邁雷迪·安德烈 |language = en}}</ref><ref>{{cite journal|last1=Szemerédi|first1=Endre|last2=Trotter|first2=William T.|year=1983|title=A Combinatorial Distinction Between the Euclidean and Projective Planes|url=http://people.math.gatech.edu/~trotter/papers/37.pdf|journal=European Journal of Combinatorics|volume=4|issue=4|pages=385–394|doi=10.1016/S0195-6698(83)80036-5|authorlink1=塞邁雷迪·安德烈|doi-access=free|language=en|access-date=2021-07-16|archive-date=2021-07-29|archive-url=https://web.archive.org/web/20210729225413/https://people.math.gatech.edu/~trotter/papers/37.pdf|dead-url=no}}</ref>其後，塞凱利·拉茲洛（Székely László）利用[[圖 (數學)|圖]]的[[交叉數不等式]]，給出更簡單的證明，<ref name="Székely">{{cite journal| last=Székely | first=László A. | year=1997 | title=Crossing numbers and hard Erdős problems in discrete geometry | journal=Combinatorics, Probability and Computing | volume=6 | issue=3 | pages=353–358 | doi=10.1017/S0963548397002976 | mr=1464571 | language = en}}</ref> 詳見下文。

塞邁雷迪－特羅特定理可推導出若干其他定理，例如[[重合幾何]]的{{le|貝克定理|Beck's theorem (geometry)}}和{{le|算術組合學|Arithmetic combinatorics}}的{{le|艾狄胥－塞邁雷迪和積定理|Erdős–Szemerédi theorem}}。

== 第一形式的證明 ==
先考慮僅經過至多兩點的直線。該些直線產生的重合數至多為<math>2m</math>。於是現在僅需考慮餘下的直線，而該些直線每條經過至少三點。

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

:<math>e = O \left ( n^{\frac{2}{3}} m^{\frac{2}{3}} + n + m \right).</math>

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

:<math>e = O \left ( n^{\frac{2}{3}} m^{\frac{2}{3}} + n + m \right ).</math>

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

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

:<math>mk = O \left ( n^{\frac{2}{3}} m^{\frac{2}{3}} + n + m \right ),</math>

所以<math>mk = O( n^{2/3} m^{2/3} )</math>、<math>mk = O(n)</math>、<math>mk = O(m)</math>三式至少有一式成立。第三式不可能，因為已設<math>k</math>為大，所以必有前兩者之一。但經初等運算可知，前兩者皆推出<math>m = O( n^2 / k^3 + n/k )</math>。

== 取到上界的例子 ==
若不考慮上界隱含的常數，則塞邁雷迪－特羅特定理的上界已是最優。使重合數達到上界的例子如下：對任意正整數<math>N\in \mathbb{N}</math>，考慮整數[[格子|格點]]集

:<math>P = \left \{ (a, b) \in \mathbb{Z}^2 \ : \ 1 \leq a \leq N; 1 \leq b \leq 2N^2 \right \},</math>

和一族直線

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

於是，有<math>|P| = 2N^3</math>個點和<math>|L| = N^3</math>條直線。由於每條直線都通過<math>N</math>點（每個<math>x \in \{1, \cdots, N\}</math>)對應一點），總重合數為<math>N^4</math>，已達上界<math>O(N^4+N^3+N^3) = O(N^4)</math>。<ref>{{Cite web|url=http://terrytao.wordpress.com/tag/szemeredi-trotter-theorem|author=Terence Tao|title=An incidence theorem in higher dimensions|author-link=陶哲軒|date=2011-03-17|accessdate=2021-07-22|language = en|archiveurl = https://web.archive.org/web/20210719030859/https://terrytao.wordpress.com/tag/szemeredi-trotter-theorem/ | archivedate = 2021-07-19}}</ref>

== 高維推廣 ==
{{le|潘卡傑·阿加爾瓦爾|Pankaj K. Agarwal}}<!--遵循[[潘卡基·阿德瓦尼]]和[[OYO酒店]]中利特施·阿加瓦爾的先例-->及{{le|鮑里斯·阿洛諾夫|Boris Aronov}}<!--遵循[[錢藏凶機]]中麥可·阿洛諾夫的先例-->發現定理的高維推廣：<ref>{{cite journal|last1=Agarwal|first1=Pankaj|last2=Aronov|first2=Boris|title=Counting facets and incidences|year=1992|journal=Discrete & Computational Geometry|volume=7|issue=1|pages=359–369|doi=10.1007/BF02187848|doi-access=free|language = en}}</ref>給定<math>d</math>維空間<math>\mathbb{R}^d</math>的<math>n</math>點（記其集合為<math>S</math>）和<math>m</math>個（<math>d-1</math>維）超平面（記其集合為<math>H</math>），則<math>S</math>和<math>H</math>之間的重合數有上界

:<math>O \left (m^{\frac{2}{3}}n^{\frac{d}{3}}+n^{d-1} \right ).</math>

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

:<math>O\left( \frac{n^d}{k^3} + \frac{n^{d-1}}{k} \right ).</math>

{{le|赫伯特·埃德斯布倫內|Herbert Edelsbrunner}}<!--依[[WP: 外語譯音表/德語]]暫譯-->給出了漸近最優的構造，從而上述上界亦不能再改進。<ref>{{cite book|title=Algorithms in Combinatorial Geometry|url=https://archive.org/details/algorithmsincomb00edel|last=Edelsbrunner|first=Herbert|publisher=Springer-Verlag|year=1987|chapter=6.5 Lower bounds for many cells|isbn=978-3-540-13722-1|language = en}}</ref>

{{le|紹利莫希·約瑟夫|József Solymosi}}<!--依[[WP:外語譯音表/匈牙利語]]暫譯-->和[[陶哲軒]]考慮點和高維[[代數簇]]的情況，並在其滿足「某些擬直線（pseudo-line）類公設」的情況下，得到近乎最優的重合數上界。其證明運用到{{le|多項式火腿三文治定理|Polynomial Ham Sandwich Theorem}}。<ref>{{Cite journal|last1=Solymosi|first1=József |last2=Tao|first2=Terence|author2-link=陶哲軒|title=An incidence theorem in higher dimensions|date=September 2012|journal=Discrete & Computational Geometry| issue=2|pages=255–280| volume=48| doi=10.1007/s00454-012-9420-x|arxiv=1103.2926|mr=2946447|language = en}}</ref>

==複二維平面== 
實域<math>\mathbb{R}</math>上的塞邁雷迪－特羅特定理有若干證明依賴[[歐幾里得空間]]的[[拓撲]]，所以不能直接推廣到其他[[域 (數學)|域]]上，塞邁雷迪和特羅特的原證明、多項式分割法、交叉數法皆屬此類，其不能適用於複域上的平面<math>\mathbb{C}^2</math>。

托特·喬鮑（Tóth Csaba）<!--WP:外語譯音表/匈牙利語-->將塞邁雷迪和特羅特的原證明推廣到<math>\mathbb{C}^2</math>。<ref>{{cite journal|last=Tóth|first=Csaba D.|year=2015|title=The Szemerédi-Trotter Theorem in the Complex Plane|journal=Combinatorica|volume=35|issue=1|pages=95&ndash;126|arxiv=math/0305283|doi=10.1007/s00493-014-2686-2 |language = en}}</ref>喬書亞·扎爾（Joshua Zahl）<!--依[[WP:外語譯音表/英語]]暫譯-->利用另一個方法，也獨立地證明此結論。<ref>{{cite journal|last=Zahl|first=Joshua|year=2015|title=A Szemerédi-Trotter Type Theorem in ℝ4|journal=Discrete & Computational Geometry|volume=54|issue=3|pages=513&ndash;572|arxiv=1203.4600|doi=10.1007/s00454-015-9717-7|language = en}}</ref>然而，其所得的上界的隱含常數與實域的情況有異：托特證明了該常數可取為<math>10^{60}</math>，而扎爾的證明並無給出具體的常數。

若限定點集為[[笛卡兒積]]，則{{le|紹利莫希·約瑟夫|József Solymosi}}和{{le|陶爾多什·加博爾|Gábor Tardos}}更簡單地證明了塞邁雷迪－特羅特上界仍成立。<ref>{{Cite journal|last=Solymosi|first=Jozsef|last2=Tardos|first2=Gabor|date=2007|title=On the number of k-rich transformations|url=http://dx.doi.org/10.1145/1247069.1247111|journal=Proceedings of the twenty-third annual symposium on Computational geometry  - SCG '07|location=New York, New York, USA|publisher=ACM Press|doi=10.1145/1247069.1247111|isbn=978-1-59593-705-6 | language = en}}</ref>

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

[[讓·布爾甘]]、{{le|內茨·卡茨|Nets Katz}}<!--依[[WP:外語譯音表/英語]]暫譯-->、[[陶哲軒]]三人<ref>{{Cite journal|last=Bourgain|first=Jean|last2=Katz|first2=Nets|last3=Tao|first3=Terence|date=2004-02-01|title=A sum-product estimate in finite fields, and applications|url=http://dx.doi.org/10.1007/s00039-004-0451-1|journal=Geometric And Functional Analysis|volume=14|issue=1|pages=27–57|doi=10.1007/s00039-004-0451-1|issn=1016-443X |language = en}}</ref>證明，除此例子外，平凡上界可以改進。

有限域上的重合數大致分為兩類：
#點數與直線數有一者「遠大於」域的[[特徵 (代數)|特徵]]；
#兩者與域的[[特徵 (代數)|特徵]]相比皆「不太大」。

=== 點集或直線集大的情況 ===
設<math>q</math>為奇[[質數]]冪。黎英榮（Lê Anh Vinh）<!--用http://www.vanlangsj.org/hanviet/ 暫譯--><ref>{{Cite journal|last=Vinh|first=Le Anh|date=November 2011|title=The Szemerédi–Trotter type theorem and the sum-product estimate in finite fields|url=http://dx.doi.org/10.1016/j.ejc.2011.06.008|journal=European Journal of Combinatorics|volume=32|issue=8|pages=1177–1181|doi=10.1016/j.ejc.2011.06.008|issn=0195-6698| language = en}}</ref>證明，<math>\mathbb{F}_q^2</math>上<math>n</math>點與<math>m</math>條直線的重合數至多為

<math>\frac{nm}{q} + \sqrt{qnm}.</math>

且上式並無隱含常數。

=== 點集及直線集皆不大的情況 ===
設<math>\mathbb{F}</math>為域，且其[[特徵 (代數)|特徵]]為<math>p\neq 2</math>。蘇菲·史蒂文斯（Sophie Stevens）和弗蘭克·德齊烏（Frank de Zeeuw）<ref>{{Cite journal|last=Stevens|first=Sophie|last2=de Zeeuw|first2=Frank|date=2017-08-03|title=An improved point-line incidence bound over arbitrary fields|url=http://dx.doi.org/10.1112/blms.12077|journal=Bulletin of the London Mathematical Society|volume=49|issue=5|pages=842–858|doi=10.1112/blms.12077|issn=0024-6093|language = en}}</ref>證明，若<math>m^{-2}n^{13} \leq p^{15}</math>（<math>p=0</math>時無需此條件），則<math>\mathbb{F}^2</math>上<math>n</math>點和<math>m</math>條直線的重合數至多為

<math>O\left(m^{\frac{11}{15}}n^{\frac{11}{15}}\right).</math>

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

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

<math>O\left(|A|^{\frac34}|B|^{\frac12} |\mathcal{L}|^\frac34 + |\mathcal{L}|
\right).</math>

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

米沙·魯德涅夫（Misha Rudnev）<!--遵循[[列夫·魯德涅夫]]的先例-->和伊利亞·什克列多夫（Ilya D. Shkredov）<!--Шкредов按[[WP: 外語譯音表/俄語]]暫譯-->研究了點集和直線集皆為笛卡兒積的情況（不論在實域或任意域），<ref>{{Cite web|last1=Rudnev|first1=Misha|last2=Shkredov|first2=Ilya D.|title=On the growth rate in SL_2(F_p), the affine group and sum-product type implications|url=https://arxiv.org/abs/1812.01671|url-status=no|website=arxiv|language=en|access-date=2021-07-16|archive-date=2021-07-13|archive-url=https://web.archive.org/web/20210713070041/https://arxiv.org/abs/1812.01671}}</ref>給出該情況下重合數的上界。此上界有時優於上列其他上界。

== 參考資料 ==
{{reflist}}

{{DEFAULTSORT:Szemeredi-Trotter theorem}}
[[Category:平面幾何]]
[[Category:离散数学定理]]
[[Category:组合数学]]
[[Category:重合幾何]]