跳转到内容

塞邁雷迪-特羅特定理

维基百科,自由的百科全书

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

次重合(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) (英语).