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

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

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

例えば、長菱形十二面体は5本の generator を持つゾーン多面体で、六角形の対面の組が2つ、平行四辺形の対面の組が4つ存在する。5本の直線の配置の対応において、3直線の組の2つが交差し、六角形の対面に対応する。また、残りの直線は ordinary point で交差し、平行四辺形の対面の組に対応する。ゾーン多面体の観点から、シルヴェスター-ガライの定理を言い換えると、すべてのゾーン多面体は1つ以上の）平行四辺形を持つ、となる。より強力には、平面上の $n$ 点の集合は少なくとも $t 2 (n)$ 個の ordinary lines を持ち、 $n$ 本の generator を持つゾーン多面体は少なくとも $2 t 2 (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 ≦ .mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}2E/3$ を得る。この不等式によって、オイラー標数から $F$ を取り除くことより $E ≦ 3 V - 3$ が証明できる。しかしもし、配置上のすべての頂点が3以上の直線の交点であるならば、辺の総数は $3 V$ 以上であるが、これは不等式に矛盾する。したがって、いくつかの頂点は2直線のみの交点でなければならず、メルヒオールの慎重な分析が示すように、3個以上の ordinary vertice が少なくとも不等式 $E ≦ 3 V - 3$ を満たす必要がある^[11]。

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

メルヒオールの不等式

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

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

同値な表現として次の形でも表すことができる。

\displaystyle t_{2}\geqslant 3+\sum _{k\geq 4}(k-3)t_{k}.

公理数学

H. S. M. Coxeter (1948, 1969) はケリーの証明のユークリッド距離の使用は不必要に強力で、"like using a sledge hammer to crack an almond"（アーモンドを砕くために大型ハンマーを使うようなものだ）と述べた。代わりにコクセターは順序幾何学において証明を行った^[13]。コクセターの証明は1944年のスタインバーグによって与えられた証明の変形である^[14]。最小の公理集合を見つける問題は逆数学の定理を証明する必要がある。詳細はこの問題に関する研究のPambuccian (2009)を見よ。

シルヴェスター-ガライの定理の通常の主張は構成幾何学（英語版）においては有効でない。構成幾何学で拒否される排中律の弱いものであるLPO (Limited principle of omniscience) を意味するためである。にもかかわらず、構成解析の公理の範囲のシルヴェスター-ガライの定理の定理は定式化が可能で、ケリーの証明を構成幾何学の公理の下で、有効となるように適用することができる^[15]。

ordinary lineの捜索

ordinary line の存在のケリーの証明では、2点を通る直線と点の距離が最小となるような組を見つける事で ordinary line を見つけることができる。 Mukhopadhyay & Greene (2012)はこの方法で力まかせ探索を用いて ordinary line を捜索する時間計算量は $O (n 3)$ であることを報告した。しかし、Edelsbrunner & Guibas (1989)は $O (n 2)$ で発見するアルゴリズムを開発した。これは、集合の中の3点からなる三角形で最小のものを探すことの副産物であった。彼らの同様の論文にて、（メルヒオールとスティーンロッドの証明を用いて）、双対の配置で ordinary point を見つける方法が同様の時間 $O (n 2)$ であることを示した。 Mukhopadhyay, Agrawal & Hosabettu (1997) は最初に（ケリーの証明を必要としない方法で）1つのordinary lineを発見する時間 $O (n log n)$ の方法を開発した。同じ時間ではあるがより単純なアルゴリズムがMukhopadhyay & Greene (2012)によって述べられている。

Mukhopadhyay & Greene (2012)のアルゴリズムはコクセターの証明をもとにしている。次の手順で示される。

与えられた点の凸包の頂点から点 $p 0$ を選ぶ。
直線 $\ell _{0}$ を、 $p 0$ と他の凸包の頂点を通る直線として構築する。
他の与えられた点を $p 0$ と成す角で並べ替え、同じ角のものをグループ化する。
グループ内のある点が孤立していれば、その点と $p 0$ を通る直線が ordinary である。
それぞれの2つの連続するグループに対して、2直線を、一方のグループ内の $p 0$ と最も近い点と、もう一方の最も近い点を通る直線とする。
このようにしてできた直線の集合内のそれぞれの直線 $\ell _{i}$ に対して、 $\ell _{0}$ と $\ell _{i}$ の交点を取る。
この交点が $p 0$ と一番近いような $\ell _{i}$ が ordinary line となる。

著者らの証明のように、このアルゴリズムで ordinary line を必ず見つけることができる。4つ目のステップで見つかった場合は構成幾何学によるもの、7つ目のステップで見つかったものは背理法によるもので、もし7つ目の段階で見つかったものが ordinary line でなければ、交点らと $p 0$ を通る直線が ordinary line として存在するが、これは4つ目の段階で発見されるべきものである^[16]。

ordinary lineの個数

シルヴェスター-ガライの定理は点の配置について ordinary line の存在は述べているが、ordinary line の個数については述べていない。 $t 2 (n)$ を $n$ つの共線でない点の集合のordinary lineの最小の個数とする。メルヒオールの証明では $t 2 (n) ≧ 3$ が示された。 de Bruijn and Erdős (1948) は $n$ が増えるにつれて $t 2 (n)$ は無限大へ発散していくと考えた。Theodore Motzkin (1951) は $t 2 (n) ≧ \sqrt n$ を証明して、予想が正しいことを示した。 Gabriel Dirac (1951) は $t_{2}(n)\geq \lfloor {\frac {n}{2}}\rfloor$ を予想した。これは現在ディラック–モツキン予想（Dirac–Motzkin conjecture）と呼ばれている（詳細はBrass, Moser & Pach (2005, p. 304)を参照）。 Kelly & Moser (1958) は $t 2 (n) ≧ 3 n / 7$ を証明している。

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

奇数 $n$ において、ディラックの予想の下限 $t 2 (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個の点で $3\lfloor {\frac {n}{4}}\rfloor$ 個の ordinary line を持つ配置が導かれれる^[19]。

Csima & Sawyer (1993) は $n$ が7である場合を除き、 $t_{2}(n)\geq \lceil {\frac {6n}{13}}\rceil$ が成立することを証明した。漸近的には、証明された上限 $n / 2$ の $12/13\approx 92.3\%$ である。 $n = 7$ の場合、ケリー-モザーの例 $t 2 (7) ≦ 3$ が反例となって除外される。しかし、Csima–Sawyerの境界が $n = 7$ においても有効だったならば、 $t 2 (7) ≧ 4$ が主張されただろう。

似た結果にベックの定理（英語版）がある。これは少数の点の直線の数と一本の直線上の点の数が対応されることを延べている^[20]。

ベン・グリーンとテレンス・タオは、十分大きい点の集合に対して（適当に $n 0$ を選択したとき $n > n 0$ となるようにして）、ordinary line の数は確かに少なくとも $n / 2$ となること示した。更に、 $n$ が奇数ならば、ordinary line の数はある定数 $C$ が存在して少なくとも $3 n / 4 - C$ となる。したがって、Böröczky による構成は最良であったことが判明した。ordinary line の個数の最小化は、グリーンとタオが十分大きい場合について証明した、3点を通る直線の個数の最大化問題である Orchard-planting problem (Orchard-planting problem) にも深く関係している^[21]。ordinary point を探すような双対の状態において、擬似直線の配置の ordinary point の最小を考えることができる。この場合においては、Csima-Sawyerの $\lceil {\frac {6n}{13}}\rceil$ の下限は有効であるが^[22]、グリーンとタオの漸近的な境界 $n / 2$ が有効であるかは知られていない。

connecting lineの数

ポール・エルデシュの気づきのように、シルヴェスター-ガライの定理は共線でない $n$ 点の集合について少なくとも $n$ つの異なる直線が決定できることを意味する。この結果はド・ブラウン-エルデシュの定理（英語版）として知られる。基本的な場合としては、 $n = 3$ の場合が自明である。値の大きい $n$ については、（残りの点がすべて共線とならないように注意して）1本の ordinary line とその直線上の2点のうち1点を削除して、 $n$ 点を $n - 1$ 点に減らすことができる。よって、定理は数学的帰納法から示すことができる。ニアペンシル（near-pencil）と呼ばれる $n - 1$ 個の共線点と、それらと共線でないある1点から成る配置が下限の例となる^[19]。

一般化

シルヴェスター-ガライの定理は、ユークリッド平面平面上の色付きの点の集合や、代数的または距離空間的に定義される点と直線の系に一般化できる。より一般にはこれら定理のバリエーションは、ordinary line を持たない点の集合を避けるため、有限集合に対するものとなっている。

色付きの点

色付きの点におけるシルヴェスター-ガライの定理は、1960年代中期にロナルド・グラハムが提起し、ドナルド・ニューマン（英語版）が広めた。 2つの色に分けられた（すべてが同一直線上にはない）有限の点の集合について、2つ以上のすべて同色の点を通る直線が存在するかどうかを考える。集合と集合族の言葉では、（すべてが同一直線上にはない）有限の点の共線部分集合の族は性質B（英語版）を持つことはできない、と表現できる。証明はセオドア・モツキン（英語版）によって発表されたが、公表はされなかった。最初に証明を公表したのはChakerian (1970)である^[23]。

非実座標

ユークリッド平面または射影平面が実数の組、座標を用いて定義できるように（ユークリッド平面は直交座標系、射影平面は同次座標系（英語版））、点と直線の系の抽象的な類似物は、数と座標を用いて定義できる。シルヴェスター-ガライの定理は有限体上でこのように定義された幾何学では適応できない。つまりファノ平面（英語版）のような有限幾何学において、すべての点の集合の 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$ 成分の有向マトロイドは、 $3 n / 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]。