シルヴェスター–ガライの定理

ウィキペディア

シルヴェスター–ガライの定理

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/03/13 15:24 UTC 版)

この項目「シルヴェスター–ガライの定理」は翻訳されたばかりのものです。不自然あるいは曖昧な表現などが含まれる可能性があり、このままでは読みづらいかもしれません。（原文：Sylvester-Gallai theorem oldid=1226528235） 修正、加筆に協力し、現在の表現をより自然な表現にして下さる方を求めています。ノートページや履歴も参照してください。（2024年9月）

4×4の格子点の3つのordinary line。

シルヴェスター–ガライの定理（シルヴェスター–ガライのていり^[1]、英: Sylvester–Gallai theorem）は、幾何学において、平面上の有限個の点のうち、ちょうど2点のみを通るまたはすべての点を通る直線が存在する事を示す定理^[2][3]。1893年にこの問題を提起したジェームス・ジョセフ・シルヴェスターと、1944年に最初の証明を発表したティボル・ガライに因んで命名された。

平面上の有限個の点のうち、ちょうど2点のみを通る直線は ordinary line^{[訳語疑問点]} と呼ばれる。シルヴェスタ–ガライの定理を別の方法で表現すると、平面上の有限個の点であって少なくとも1つの点が他の2点と共線でなければ、その有限個の点の集合は ordinary line を持つ、となる。より強い定理によれば、（すべての点が一直線上にある、ということがない）有限個の点の集合には、線型数以上の ordinary line が存在する。ordinary line を発見するアルゴリズムの時間計算量は、n点の集合に対してO(n log n)である。

歴史

シルヴェスタ–ガライの定理は、J. J. Sylvester (1893) によって提起された。 Kelly (1986) は、シルヴェスターは複素射影平面（英語版）上の三次曲線の9つの変曲点が、9点と12直線の配置（英語版）（ヘッセ配置（英語版））を成すという代数幾何学の問題に触発されたことを示唆している。シルヴェスター–ガライの定理はこの9つの変曲点がすべて実座標を持つことは不可能であることを示している^[4]。

H. J. Woodall (1893a, 1893b) は、シルヴェスター–ガライの定理の短い証明を発見したと主張したが、発表する時点ですでに、証明が不完全であることが指摘されていた。Eberhard Melchior (1941) は、定理の射影幾何学的な双対を示すことで、正確で強力な定理を得た。Paul Erdős (1943) は、メルヒオールの証明に気づかぬまま^[5]、定理を予想として述べ、 その後にティボル・ガライや他の数学者が証明した^[6]。

1951年の評論では、エルデシュは「ガライの定理」の名を使用した^[7]。1954年には、レナード・ブルーメンタール（英語版）の評論で「シルヴェスター–ガライの定理」という名称が使われた^[8]。

同値な定理

ordinary line の存在問題は、ユークリッド平面の代わりに射影平面RP²で考えることで、ordinary line の双対となる点の問題としても考えることができる。射影平面は通常のユークリッド平面上の点に"無限遠"を付加することで構築される。しかし、無限遠に付加された点は、ordinary line を持たない点の集合を作るのに役立つわけではない。射影平面上の任意の有限個の点が、点と直線の接続関係の同様の組み合わせパターンを持つユークリッド点の集合に変換されるためである。したがって、ユークリッド平面と射影平面のどちらかに存在する交点と直線のパターンは、もう一方の平面にも存在する。にもかかわらず、射影的な観点によって点と直線の配置を簡単に述べることができる。特に、射影幾何学の双対性（英語版）を使用することができることが重要である。この双対性の下、ordinary line の存在は、非自明な配置 (Arrangement of lines) の有限個の直線上の、RP²上の有限個の点（ordinary point^{[訳語疑問点]}）の存在に置き換えることができる。ここで直線の配置が自明であるとは、すべての直線が共点であることで、非自明であるとは、ある ordinary point がちょうど2直線に属する状態を示す^[5]。

長菱形十二面体。赤い平行四辺形状の面は5線の配置のordinary pointsに一致する。シルヴェスター–ガライの定理と同意な定理は、すべてのゾーン多面体上が少なくとも1つ以上の平行四辺形を持つことを示す。

直線の配置はゾーン多面体（generator^{[訳語疑問点]}と呼ばれる直線の有限集合のミンコフスキー和から成る多面体）と近い組み合わせ的構造を持つ。この関係において、ゾーン多面体の対面の組は、射影平面上の直線の配置の交点と各 generator に対応する。対面の組の個数は、交点の数の2倍である。

例えば、長菱形十二面体は5本の generator を持つゾーン多面体で、六角形の対面の組が2つ、平行四辺形の対面の組が4つ存在する。5本の直線の配置の対応において、3直線の組の2つが交差し、六角形の対面に対応する。また、残りの直線は ordinary point で交差し、平行四辺形の対面の組に対応する。ゾーン多面体の観点から、シルヴェスター-ガライの定理を言い換えると、すべてのゾーン多面体は1つ以上の）平行四辺形を持つ、となる。より強力には、平面上のn点の集合は少なくともt₂ (n)個の ordinary lines を持ち、 n本の generator を持つゾーン多面体は少なくとも2t₂ (n)個の平行四辺形の面を持つことが保証される^[9]。

証明

シルヴェスター-ガライの定理はさまざなな方法で証明されてきた。ガライの1944年の証明は、ユークリッド幾何学と射影幾何学を交互に切り替えて、点を傾きが0に近い ordinary line に変換するというものである（詳しくはBorwein & Moser (1990)を参照されたい）。1941年のメルヒオールの証明では、射影幾何学の双対性を用いて、問題を直線の配置に置き換え、オイラーの多面体公式を使った。リロイ・ミルトン・ケリー（英語版）の証明は、0でない最小の距離にある点を繋ぐ直線は ordinary になることを背理法によって示した。またスタインバーグ（Steinberg）の早期の証明に続いて、コクセターは、傾きの計量と、ガライとケリーの証明に現れた距離の概念を不必要とする代わりに、順序幾何学（英語版）の公理を使った定理のみを使用して証明した。

ケリーの証明

次はリロイ・ミルトン・ケリー（英語版）による証明である。Aigner & Ziegler (2018) はケリーの証明を、数多の証明の中で"simply the best"であると述べている^[10]。

Sを共線でない点の有限集合とする。少なくともSの2点を含む直線を、connecting line と定義する。Sの有限性より、Sの要素には点と connecting line の距離が最小となるような点Pが存在する必要がある。ケリーはこのときの connecting line l が ordinary であることを背理法によって証明した^[10]。

lを ordinary でないと仮定しよう。lは少なくともSに属する3点以上を通る必要がある。これら共線点のうち2つ以上は、lへのPの直交射影P'に関して同じ側にある。この2点をB, Cと定義する。ただし、C, B, P'はこの順で並んでいるとする。mをCPを通る connecting line、B'をBのmへの直交射影とすれば、△PP'C, △BB'Cが相似かつ|△PP'C| > |△BB'C|であることより、BB'はPP'より短い^[10]。

しかし、これはP, lの定義に矛盾する。これはlが ordinary でないとした仮定が偽であることを意味する。よって題意は示された^[10]。

メルヒオールの証明

1941年（エルデシュの問題発表とガライの証明の前）、メルヒオールは、射影平面上の非自明な直線の配置は、3つ以上の ordinary point を持つことを示した。双対性より、非自明な点の集合は3つ以上の ordinary line を持つことを意味する^[11]。

メルヒオールは、射影平面に埋め込まれた（英語版）任意のグラフについて、オイラー標数V - E + Fは1でなければならないことに気づいた。ここで、V, E, Fはそれぞれ、グラフの頂点、辺、面の個数。射影平面上の非自明な直線の配置は、面は3辺以上で囲まれ、辺は2面で囲まれるようなグラフを定義する。そのため、二重に数える（英語版）ことで不等式F ≦ 2E/3を得る。この不等式によって、オイラー標数からFを取り除くことよりE ≦ 3V - 3が証明できる。しかしもし、配置上のすべての頂点が3以上の直線の交点であるならば、辺の総数は3V以上であるが、これは不等式に矛盾する。したがって、いくつかの頂点は2直線のみの交点でなければならず、メルヒオールの慎重な分析が示すように、3個以上の ordinary vertice が少なくとも不等式E ≦ 3V - 3を満たす必要がある^[11]。

Aigner & Ziegler (2018) の指摘のように、ordinary vertex の存在に関する議論は、1944年、ノーマン・スティーンロッド（英語版）によって与えられた。スティーンロッドは ordinary line の問題の双対を明示的に応用した^[12]。

メルヒオールの不等式

同様の議論で、メルヒオールはより一般的な結果を証明することができた。任意のk ≧ 2において、t_kをk本の直線で作られる点の個数として、次の式が成立する。^[11]。

${\displaystyle \displaystyle \sum _{k\geq 2}(k-3)t_{k}\leq -3.}$

${\displaystyle n/2}$

Böröczkyの10点と5本の ordinary linesの配置の例。

ディラックの予想した下限は漸近的には最もよいもので、4超過の偶数nの上限t₂(n) ≦ n/2と対応する。Károly Böröczkyによる上限を達成した構築は、射影平面上の正m角形の頂点と頂点の組で決定される方向の無限遠点m個（延べn = 2m個）から構築される。これらの点の組はm(m - 1)/2個あるが、m個のみの方向を決定する。この配置ではm個の ordinary line を持ち、頂点vとそれに隣り合う2頂点と共線な無限遠点を結ぶ点になる。実射影平面の任意の有限の配置のように、この構成は ordinary line の数を変えずにすべての点が有限点となるように帰ることができる^[17]。

奇数nにおいて、ディラックの予想の下限t₂(n) = n - 1/2に一致する例は2つしか知られていない。1つはKelly & Moser (1958)の考案した正三角形の頂点、重心 、辺の中点の7点から成る構成である。この7点は ordinary line を3つのみ持つ。3つの ordinary line を持つ点と直線の配置（英語版）はユークリッド平面上では単一の直線に置き換えることはできないが、ファノ平面（英語版）として知られる有限の射影空間を構成する。この接続関係のために、ケリー-モザーの例は non-Fano configuration としても呼ばれる^[18]。他の例にマッキー（McKee）の考案した^[17] 、1辺を共有する2つの正五角形の頂点と、共有辺の中点と4つの無限遠点の延べ13点から成る配置がある。これは6つの ordinary line を持つ。Böröczky の構成を修正すれば、奇数n個の点で${\displaystyle 3\lfloor {\frac {n}{4}}\rfloor }$

ヘッセ配置（英語版）。２点を通る直線は3つ目の点を通る。 シルヴェスター-ガライの定理は、この配置はユークリッド平面では実現できないが、複素射影平面（英語版）では実現できることを示す。

ユークリッド平面または射影平面が実数の組、座標を用いて定義できるように（ユークリッド平面は直交座標系、射影平面は同次座標系（英語版））、 点と直線の系の抽象的な類似物は、数と座標を用いて定義できる。シルヴェスター-ガライの定理は有限体上でこのように定義された幾何学では適応できない。つまりファノ平面（英語版）のような有限幾何学において、すべての点の集合の ordinary line は存在しない^[10]。

また、シルヴェスター-ガライの定理は複素数や四元数の組の座標を持つ幾何学においても直接は成立しないが、より複雑な類似物であれば成立する。例えば、複素射影平面（英語版）には、9つの点（三次曲線の変曲点）の配置であるヘッセ配置（英語版）がある。この配置における ordinary line は存在しない。このような配置は、シルヴェスター-ガライ配置（英語版）として知られ、ユークリッド平面上では成立することはない。 シルヴェスター-ガライの定理の他の方法で述べると、シルヴェスター-ガライ配置が共線性を保ちつつユークリッド平面に埋め込まれるとき、配置内の点は常に一本の直線上にある、となる。したがってヘッセ配置の例は、複素射影平面（英語版）では偽であることが分かる。 しかし、Kelly (1986)はシルヴェスター-ガライの定理の複素数への類似物として、 シルヴェスター-ガライ配置（英語版）を複素射影平面に埋め込んだ時、すべての点は2次元部分空間上になければならないことを示した。つまり、 アフィン包が全体の空間であるような3次元複素空間上の点の集合は必ず1つの ordinary line を持ち、また ordinary line の線型数を持たなければならない^[24]。同様に、Elkies, Pretorius & Swanepoel (2006) はシルヴェスター-ガライ配置（英語版）四元数で定義される空間に埋め込むとき、それらの点は必ず3次元部分空間上になければならないことを示した。

マトロイド

ユークリッド平面上の点の任意の集合とそれらを繋ぐ直線は、ランク3の有向マトロイド（英語版）の成分と平面に抽象化される。実数でない数の体系で定義される幾何学の点と直線はマトロイドを成すが、必ずしも有向マトロイドを成すわけではない。この状況において、Kelly & Moser (1958)の ordinary line の個数の下限の結果は、有向マトロイドへ一般化できる。ランク3のn成分の有向マトロイドは、3n/7個の、2点を通る直線を持つ。あるいは、より少数の2点を通る直線の持つランク3のマトロイドは無向である必要がある^[25]。 2点のみを通る直線がないようなマトロイドはシルヴェスターマトロイド（英語版）と呼ばれる。関連して、7点と3つの ordinary line を持つケリー-モザー配置は、GF(4)表現可能マトロイド（英語版）における禁止マイナー（英語版）を構成する^[18]。

距離幾何学

シルヴェスター-ガライの定理の他の一般化において、Chvátal (2004)によって任意の距離空間へ予想が行われChen (2006)によって解決された。この一般化では、距離空間上の3点が三角不等式の等号を満たすとき共線であると定義され、直線は、既に直線上にある2点と共線である点の全体の集合であると定義された。ChvátalとChenによる一般化はすべての有限距離空間は、すべての点を含むような直線かただ2点のみを通る直線を持つことを示した^[26]。

脚注

1. ^ 『新訂版　数学用語 英和辞典: 和英索引付き』近代科学社、2020年12月2日。ISBN 978-4-7649-0624-2。https://www.google.co.jp/books/edition/%E6%96%B0%E8%A8%82%E7%89%88_%E6%95%B0%E5%AD%A6%E7%94%A8%E8%AA%9E_%E8%8B%B1%E5%92%8C%E8%BE%9E%E5%85%B8/SHMNEAAAQBAJ。 
2. ^ Chvátal, Vašek『ポール・エルデス：離散数学の魅力: 伝説の講義』近代科学社、2023年8月25日。ISBN 978-4-7649-0662-4。https://www.google.co.jp/books/edition/%E3%83%9D%E3%83%BC%E3%83%AB_%E3%82%A8%E3%83%AB%E3%83%87%E3%82%B9_%E9%9B%A2%E6%95%A3%E6%95%B0%E5%AD%A6%E3%81%AE/yd3QEAAAQBAJ。 
3. ^ 『ボロバシュ 数学の技法』丸善出版、2022年。ISBN 978-4-621-30731-1。 
4. ^ Elkies, Pretorius & Swanepoel (2006).
5. ^ ^{a b} Borwein & Moser (1990).
6. ^ Steinberg et al. (1944); Erdős (1982).
7. ^ MR0041447
8. ^ MR0056941
9. ^ Shephard (1968).
10. ^ ^{a b c d e} Aigner & Ziegler (2018).
11. ^ ^{a b c} Melchior (1941).
12. ^ Aigner & Ziegler (2018, p. 92); Steenrod's proof was briefly summarized in Steinberg et al. (1944).
13. ^ Aigner & Ziegler (2018); Pambuccian (2009).
14. ^ Coxeter (1948); Pambuccian (2009).
15. ^ Mandelkern (2016).
16. ^ Mukhopadhyay & Greene (2012).
17. ^ ^{a b} Crowe & McKee (1968).
18. ^ ^{a b} Geelen, Gerards & Kapoor (2000).
19. ^ ^{a b} Pach & Sharir (2009)
20. ^ Beck (1983).
21. ^ Green & Tao (2013).
22. ^ Lenchner (2008).
23. ^ For the history of this variation of the problem, see also Grünbaum (1999)
24. ^ Basit et al. (2019).
25. ^ Björner et al. (1993).
26. ^ Chvátal (2004); Chen (2006); Pambuccian (2009)

出典

• Aigner, Martin; Ziegler, Günter M. (2018), “Chapter 11. Lines in the plane and decomposition of graphs”, Proofs from THE BOOK (6th ed.), Springer, Theorem 1, pp. 77–78, doi:10.1007/978-3-662-57265-8_11, ISBN 978-3-662-57265-8 
• Basit, Abdul; Dvir, Zeev; Saraf, Shubhangi; Wolf, Charles (2019), “On the number of ordinary lines determined by sets in complex space”, Discrete & Computational Geometry 61 (4): 778–808, arXiv:1611.08740, doi:10.1007/s00454-018-0039-4, MR3943495 
• Beck, József (1983), “On the lattice property of the plane and some problems of Dirac, Motzkin, and Erdős in combinatorial geometry”, Combinatorica 3 (3–4): 281–297, doi:10.1007/BF02579184, MR0729781 
• Björner, Anders; Las Vergnas, Michel; Sturmfels, Bernd; White, Neil; Ziegler, Günter M. (1993), Oriented matroids, Encyclopedia of Mathematics and its Applications, 46, Cambridge: Cambridge University Press, p. 273, ISBN 0-521-41836-4, MR1226888, https://archive.org/details/orientedmatroids0000unse/page/273 
• Borwein, P.; Moser, W. O. J. (1990), “A survey of Sylvester's problem and its generalizations”, Aequationes Mathematicae 40 (1): 111–135, doi:10.1007/BF02112289, MR1069788 
• Brass, Peter; Moser, William; Pach, János (2005), Research problems in discrete geometry, Berlin: Springer, ISBN 0-387-23815-8 
• de Bruijn, N. G.; Erdős, P. (1948), “A combinatioral [sic] problem”, Indagationes Mathematicae 10: 421–423, MR0028289, http://www.renyi.hu/~p_erdos/1948-01.pdf 
• Chakerian, G. D. (1970), “Sylvester's problem on collinear points and a relative”, American Mathematical Monthly 77 (2): 164–167, doi:10.2307/2317330, JSTOR 2317330, MR258659, https://jstor.org/stable/2317330 
• Chen, Xiaomin (2006), “The Sylvester–Chvátal theorem”, Discrete & Computational Geometry 35 (2): 193–199, doi:10.1007/s00454-005-1216-9, MR2195050 
• Chvátal, Vašek (2004), “Sylvester–Gallai theorem and metric betweenness”, Discrete & Computational Geometry 31 (2): 175–195, doi:10.1007/s00454-003-0795-6, MR2060634 
• Coxeter, H. S. M. (1948), “A problem of collinear points”, American Mathematical Monthly 55 (1): 26–28, doi:10.2307/2305324, JSTOR 2305324, MR24137, https://jstor.org/stable/2305324 
• Coxeter, H. S. M. (1969), “12.3 Sylvester's problem of collinear points”, Introduction to Geometry (2nd ed.), New York: John Wiley & Sons, pp. 181–182, ISBN 0-471-50458-0 
• Crowe, D. W.; McKee, T. A. (1968), “Sylvester's problem on collinear points”, Mathematics Magazine 41 (1): 30–34, doi:10.2307/2687957, JSTOR 2687957, MR0235452, https://jstor.org/stable/2687957 
• Csima, J.; Sawyer, E. (1993), “There exist ${\displaystyle 6n/13}$