跳转到内容

塞迈雷迪-特罗特定理

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

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

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