塞邁雷迪-特羅特定理

平面上若干點和直線產生的重合數的上界

塞邁雷迪-特羅特定理組合幾何的定理,其斷言給定歐氏平面上任意直線,至多發生

次重合(incidence,即二元組,其中為一點,為直線,且上)。

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

考慮隱藏常數的話,保奇·亞諾什英语János Pach、拉多什·拉多伊契奇(Radoš Radoičić)、陶爾多什·加博爾英语Gábor Tardos托特·蓋薩英语Géza Tóth四人[1]給出上界。此後,由於交叉數不等式的常數得到改進,塞邁雷迪-特羅特定理的常數也相應得到改進。截至2019年末,最優的常數是[2] 另一方面,保奇和托特證明,若將上式的常數換成,則不再為重合數的上界。[3]

定理也有以下等價形式:若給定個點和整數,則經過至少個點的直線數至多為

定理得名自塞邁雷迪·安德烈威廉·特羅特英语William T. Trotter,其最先的證明較複雜,用到稱為「胞分解」(cell decomposition)的組合技巧。[4][5]其後,塞凱利·拉茲洛(Székely László)利用交叉數不等式,給出更簡單的證明,[6] 詳見下文。

塞邁雷迪-特羅特定理可推導出若干其他定理,例如重合幾何貝克定理英语Beck's theorem (geometry)算術組合學英语Arithmetic combinatorics艾狄胥-塞邁雷迪和積定理英语Erdős–Szemerédi theorem

第一形式的證明

编辑

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

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

 

以該 點為頂點,並以該 條線段為邊建。每條線段皆為 條直線中某一條的部分,且每兩條直線交於至多一點,故圖的交叉數至多為 。再由交叉數不等式知,或者有 ,或者有 。兩者皆推出 ,從而得到上界

 

第二形式的證明

编辑

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

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

 

所以   三式至少有一式成立。第三式不可能,因為已設 為大,所以必有前兩者之一。但經初等運算可知,前兩者皆推出 

取到上界的例子

编辑

若不考慮上界隱含的常數,則塞邁雷迪-特羅特定理的上界已是最優。使重合數達到上界的例子如下:對任意正整數 ,考慮整數格點

 

和一族直線

 

於是,有 個點和 條直線。由於每條直線都通過 點(每個 )對應一點),總重合數為 ,已達上界 [7]

高維推廣

编辑

潘卡傑·阿加爾瓦爾英语Pankaj K. Agarwal鮑里斯·阿洛諾夫英语Boris Aronov發現定理的高維推廣:[8]給定 維空間  點(記其集合為 )和 個( 維)超平面(記其集合為 ),則  之間的重合數有上界

 

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

 

赫伯特·埃德斯布倫內英语Herbert Edelsbrunner給出了漸近最優的構造,從而上述上界亦不能再改進。[9]

紹利莫希·約瑟夫英语József Solymosi陶哲軒考慮點和高維代數簇的情況,並在其滿足「某些擬直線(pseudo-line)類公設」的情況下,得到近乎最優的重合數上界。其證明運用到多項式火腿三文治定理英语Polynomial Ham Sandwich Theorem[10]

複二維平面

编辑

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

托特·喬鮑(Tóth Csaba)將塞邁雷迪和特羅特的原證明推廣到 [11]喬書亞·扎爾(Joshua Zahl)利用另一個方法,也獨立地證明此結論。[12]然而,其所得的上界的隱含常數與實域的情況有異:托特證明了該常數可取為 ,而扎爾的證明並無給出具體的常數。

若限定點集為笛卡兒積,則紹利莫希·約瑟夫英语József Solymosi陶爾多什·加博爾英语Gábor Tardos更簡單地證明了塞邁雷迪-特羅特上界仍成立。[13]

有限域上

编辑

在一般 上,塞邁雷迪-特羅特上界不一定成立。例如:取有限域 的二維平面上全部 個點的集合 ,又取全部 條直線的集合 ,則每條直線經過 個點,故有 次重合。另一方面,塞邁雷迪-特羅特上界僅為 。此例子說明平凡上界 已為最優。

讓·布爾甘內茨·卡茨英语Nets Katz陶哲軒三人[14]證明,除此例子外,平凡上界可以改進。

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

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

點集或直線集大的情況

编辑

 為奇質數冪。黎英榮(Lê Anh Vinh)[15]證明,  點與 條直線的重合數至多為

 

且上式並無隱含常數。

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

编辑

 為域,且其特徵 。蘇菲·史蒂文斯(Sophie Stevens)和弗蘭克·德齊烏(Frank de Zeeuw)[16]證明,若  時無需此條件),則  點和 條直線的重合數至多為

 

 時,此上界比塞邁雷迪-特羅特上界更優。

若限定點集為笛卡兒積,則其證明以下更佳的上界:證 為有限點集,其中 ,又設 為平面上有限條直線的集合。假設 ,而若特徵為正就再加上條件 ,則  組成的重合數至多為

 

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

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

參考資料

编辑
  1. ^ Pach, János; Radoičić, Radoš; Tardos, Gábor; Tóth, Géza. Improving the Crossing Lemma by Finding More Crossings in Sparse Graphs. Discrete & Computational Geometry. 2006, 36 (4): 527–552. doi:10.1007/s00454-006-1264-9  (英语). 
  2. ^ Ackerman, Eyal. On topological graphs with at most four crossings per edge. Computational Geometry. December 2019, 85: 101574. ISSN 0925-7721. doi:10.1016/j.comgeo.2019.101574 (英语). 
  3. ^ Pach, János; Tóth, Géza. Graphs drawn with few crossings per edge. Combinatorica. 1997, 17 (3): 427–439. doi:10.1007/BF01215922 (英语). 
  4. ^ Szemerédi, Endre; Trotter, William T. Extremal problems in discrete geometry. Combinatorica. 1983, 3 (3–4): 381–392. MR 0729791. doi:10.1007/BF02579194 (英语). 
  5. ^ Szemerédi, Endre; Trotter, William T. A Combinatorial Distinction Between the Euclidean and Projective Planes (PDF). European Journal of Combinatorics. 1983, 4 (4): 385–394 [2021-07-16]. doi:10.1016/S0195-6698(83)80036-5 . (原始内容存档 (PDF)于2021-07-29) (英语). 
  6. ^ Székely, László A. Crossing numbers and hard Erdős problems in discrete geometry. Combinatorics, Probability and Computing. 1997, 6 (3): 353–358. MR 1464571. doi:10.1017/S0963548397002976 (英语). 
  7. ^ Terence Tao. An incidence theorem in higher dimensions. 2011-03-17 [2021-07-22]. (原始内容存档于2021-07-19) (英语). 
  8. ^ Agarwal, Pankaj; Aronov, Boris. Counting facets and incidences. Discrete & Computational Geometry. 1992, 7 (1): 359–369. doi:10.1007/BF02187848  (英语). 
  9. ^ Edelsbrunner, Herbert. 6.5 Lower bounds for many cells. Algorithms in Combinatorial Geometry. Springer-Verlag. 1987. ISBN 978-3-540-13722-1 (英语). 
  10. ^ Solymosi, József; Tao, Terence. An incidence theorem in higher dimensions. Discrete & Computational Geometry. September 2012, 48 (2): 255–280. MR 2946447. arXiv:1103.2926 . doi:10.1007/s00454-012-9420-x (英语). 
  11. ^ Tóth, Csaba D. The Szemerédi-Trotter Theorem in the Complex Plane. Combinatorica. 2015, 35 (1): 95–126. arXiv:math/0305283 . doi:10.1007/s00493-014-2686-2 (英语). 
  12. ^ Zahl, Joshua. A Szemerédi-Trotter Type Theorem in ℝ4. Discrete & Computational Geometry. 2015, 54 (3): 513–572. arXiv:1203.4600 . doi:10.1007/s00454-015-9717-7 (英语). 
  13. ^ Solymosi, Jozsef; Tardos, Gabor. On the number of k-rich transformations. Proceedings of the twenty-third annual symposium on Computational geometry - SCG '07 (New York, New York, USA: ACM Press). 2007. ISBN 978-1-59593-705-6. doi:10.1145/1247069.1247111 (英语). 
  14. ^ Bourgain, Jean; Katz, Nets; Tao, Terence. A sum-product estimate in finite fields, and applications. Geometric And Functional Analysis. 2004-02-01, 14 (1): 27–57. ISSN 1016-443X. doi:10.1007/s00039-004-0451-1 (英语). 
  15. ^ Vinh, Le Anh. The Szemerédi–Trotter type theorem and the sum-product estimate in finite fields. European Journal of Combinatorics. November 2011, 32 (8): 1177–1181. ISSN 0195-6698. doi:10.1016/j.ejc.2011.06.008 (英语). 
  16. ^ Stevens, Sophie; de Zeeuw, Frank. An improved point-line incidence bound over arbitrary fields. Bulletin of the London Mathematical Society. 2017-08-03, 49 (5): 842–858. ISSN 0024-6093. doi:10.1112/blms.12077 (英语). 
  17. ^ Rudnev, Misha; Shkredov, Ilya D. On the growth rate in SL_2(F_p), the affine group and sum-product type implications. arxiv. [2021-07-16]. (原始内容存档于2021-07-13) (英语).