塞迈雷迪-特罗特定理

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

塞迈雷迪-特罗特定理组合几何的定理,其断言给定欧氏平面上任意直线,至多发生

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