サムネイル|4×4の格子点の3つのordinary line。 シルヴェスター–ガライの定理（シルヴェスター–ガライのていり、）は、幾何学において、平面上の有限個の点のうち、ちょうど2点のみを通るまたはすべての点を通る直線が存在する事を示す定理。1893年にこの問題を提起したジェームス・ジョセフ・シルヴェスターと、1944年に最初の証明を発表したティボル・ガライに因んで命名された。
平面上の有限個の点のうち、ちょうど2点のみを通る直線は正規直線 (ordinary line)、ガライ直線と呼ばれる。シルヴェスター–ガライの定理を別の方法で表現すると、平面上の有限個の点であって少なくとも1つの点が他の2点と共線でなければ、その有限個の点の集合は正規直線を持つ、となる。より強い定理によれば（非共線的な）有限個の点の集合には、点の個数に比例する数個の正規直線が存在する。正規直線を発見するアルゴリズムの時間計算量は、点の集合に対してである。
歴史 シルヴェスター–ガライの定理は、 によって提起された。シルヴェスターが、上の三次曲線の9つの変曲点は9点と12直線の（）を成すという代数幾何学の問題に触発されたことを、 は示唆している。シルヴェスター–ガライの定理はこの9つの変曲点がすべて実座標を持つことは不可能であることを示している。
は、シルヴェスター–ガライの定理の短い証明を発見したと主張したが、発表する時点ですでに、証明が不完全であることが指摘されていた。 は、定理の射影幾何学的な双対を示すことで、正確で強力な定理を得た。 は、メルヒオールの証明に気づかぬまま、定理を予想として述べ、 その後にティボル・ガライや他の数学者が証明した; .。
1951年の評論で、エルデシュは「ガライの定理」の名を使用した。1954年には、の評論で「シルヴェスター–ガライの定理」という名称が使われた。
同値な定理 正規直線の存在問題は、ユークリッド平面の代わりに射影平面で考えることで、正規直線の双対となる点の問題としても考えることができる。射影平面は通常のユークリッド平面上の点に「無限遠」を付加することで構築される。ただし、無限遠点によって正規直線を持たない点の集合が作られるわけではない。射影平面上の任意の有限個の点が、同様の点と直線の接続関係のパターンを持つユークリッド点の集合に変換されるためである。ユークリッド平面または射影平面のどちらかに存在する交点と直線のパターンは、もう一方の平面にも存在する。にもかかわらず、射影的な観点によって点と直線の配置を簡単に述べることができる。特に、を使用することができることが重要である。この双対性の下、上の正規直線の存在は、有限個の直線の非自明なにおける、 の存在に置き換えることができる。ここで直線の配置が自明であるとはすべての直線が共点であることで、非自明であるとはある ordinary point がちょうど2直線に属する状態を示す。 サムネイル|長菱形十二面体。赤い平行四辺形状の面は5直線の ordinary point に一致する。シルヴェスター–ガライの定理と同値な定理は、すべてのゾーン多面体上が少なくとも1つ以上の平行四辺形を持つことを示す。 直線の配置はゾーン多面体（と呼ばれる直線の有限集合のミンコフスキー和から成る多面体）と近い組合せ的構造を持つ。この関係において、ゾーン多面体の対面の組は、射影平面上の直線の交点と各 generator に対応する。対面の組の個数は、交点の数の2倍である。
例えば、長菱形十二面体は5本の generator を持つゾーン多面体で、六角形の対面の組が2つ、平行四辺形の対面の組が4つ存在する。5本の直線の配置の対応において、3直線の組の2つが交差し、六角形の対面に対応する。また、残りの直線は ordinary point で交差し、平行四辺形の対面の組に対応する。ゾーン多面体の観点から、シルヴェスター-ガライの定理を言い換えると、すべてのゾーン多面体は1つ以上の平行四辺形を持つ、となる。より強力には、平面上の点の集合が少なくとも個の正規直線を持つとき、 本の generator を持つゾーン多面体は少なくとも個の平行四辺形の面を持つことが保証される。
証明 シルヴェスター-ガライの定理はさまざな方法で証明されてきた。ガライの1944年の証明は、ユークリッド幾何学と射影幾何学を交互に切り替えて、点を傾きが0に近い正規直線に変換するというものである（詳しくはを参照されたい）。1941年のメルヒオールの証明では、射影幾何学の双対性を用いて、問題を直線の配置に置き換え、オイラーの多面体公式を使った。の証明は、0でない最小の距離にある点を繋ぐ直線は正規直線になることを背理法によって示した。またスタインバーグ () の先行の証明に続いてコクセターは、ガライとケリーの証明に現れた傾きと距離という計量の概念を不必要とする代わりに、の公理を使った定理のみを使用して証明した。
ケリーの証明 次はによる証明である。 はケリーの証明を、数多の証明の中で"simply the best"であると述べている。
を共線でない点の有限集合とする。少なくともの2点を含む直線を、連結直線 (connecting line) という。の有限性より、の要素には点と連結直線の距離が最小となるような点が存在する必要がある。ケリーはこのときの連結直線 が正規であることを背理法によって証明した。
を正規直線でないと仮定する。は少なくともに属する3点以上を通る必要がある。これら共線点のうち2つ以上は、へのの直交射影に関して同じ側にある。この2点をと定義する。ただし、はこの順で並んでいるとする。をを通る連結直線、をのへの直交射影とすれば、が相似かつであることより、はより短い。
しかし、これはの定義に矛盾する。これはが正規でないとした仮定が偽であることを意味する。よって題意は示された。
メルヒオールの証明 1941年（エルデシュの問題発表とガライの証明の前）、メルヒオールは、射影平面上の非自明な直線の配置は、3つ以上の ordinary point を持つことを示した。双対性より、非自明な点の集合は3つ以上の正規直線を持つことを意味する。
メルヒオールは、射影平面に任意のグラフについて、オイラー標数でなければならないことに気づいた。ここで、はそれぞれ、グラフの頂点、辺、面の個数。射影平面上の非自明な直線の配置は、面は3辺以上で囲まれ、辺は2面で囲まれるようなグラフを定義する。そのため、ことで不等式を得る。この不等式によって、オイラー標数からを取り除くことよりが証明できる。しかしもし、配置上のすべての頂点が3つ以上の直線の交点であるならば辺の総数は以上であるが、これは不等式に矛盾する。したがって、いくつかの頂点は2直線のみの交点でなければならず、メルヒオールの慎重な分析が示すように、3個以上の ordinary な頂点が少なくとも不等式を満たす必要がある。
の指摘のように、ordinary な頂点の存在に関する議論は、1944年にノーマン・スティーンロッドによっても与えられた。スティーンロッドは正規直線の問題の双対を明示的に応用した; スティーンロッドの証明は に要約されている。。
メルヒオールの不等式 同様の議論で、メルヒオールはより一般的な結果を証明することができた。任意のにおいて、を本の直線で作られる点の個数として、次の式が成立する。。
同値な表現として次の形でも表すことができる。
公理数学 はケリーの証明のユークリッド距離の使用は不必要に強力で、"like using a sledge hammer to crack an almond"（アーモンドを砕くために大型ハンマーを使うようなものだ）と述べた。 代わりにコクセターはにおいて証明を行った; .。コクセターの証明は1944年のスタインバーグによって与えられた証明の変種である; . 。最小の公理集合を見つける問題には逆数学の定理を証明する必要がある。詳細はこの問題に関する研究のを参照。
シルヴェスター-ガライの定理の通常の主張はにおいては有効でない。構成的数学の公理によって拒否される排中律の弱いものであるLPOを意味するためである。にもかかわらず、構成的解析学の公理の範囲のシルヴェスター-ガライの定理の定理は定式化が可能で、構成的解析学の公理の下でケリーの証明を有効となるように適用することができる。
正規直線の求め方 正規直線の存在のケリーの証明では、2点を通る直線と点の距離が最小となるような組を見つける事で正規直線を見つけることができる。 はこの方法で力まかせ探索を用いて正規直線を捜索する時間計算量はであることを報告した。 しかし、はで発見するアルゴリズムを開発した。これは、点集合の中の3点からなる三角形で最小のものを探すことの副産物であった。同じ論文で、（メルヒオールとスティーンロッドの証明を用いて）双対の配置において ordinary point を見つける方法が同様の時間であることが示された。 は（ケリーの証明を必要とせず）で1本の正規直線を発見する方法を初めて開発した。同じ時間ではあるもののより単純なアルゴリズムが によって述べられている。
のアルゴリズムはコクセターの証明をもとにしている。次の手順で示される。
与えられた点集合の凸包の頂点から点を選ぶ。 と他の凸包の頂点を通る直線をとする。 他の点をと成す角をもとに並べ替え、同じ角のものをグループ化する。 グループに分けたとき孤立している点が存在すれば、その点とを通る直線が正規直線である。 連続する2つのグループごとに、一方のグループ内のと最も近い点と、もう一方のグループのと最も遠い点を通る直線を作る。また、2つのグループを入れ替えて同様に別の直線を作る。 このようにしてできた直線の集合のそれぞれの直線に対して、の交点を取る。 この交点ととが一番近いようなが正規直線となる。
4つ目のステップで見つかった場合は構成的な証明、7つ目のステップで見つかったものは背理法によって正規であるといえる。もし7つ目の段階で見つかったが正規直線でなければ、上の点の1つと を通る直線が正規直線として存在するが、これは4つ目の段階で発見されるべきものである。
正規直線の個数 サムネイル|より少ない正規直線を持つ有名な例。 シルヴェスター-ガライの定理は点の配置について正規直線の存在は述べているが、正規直線の個数については述べていない。をつの共線でない点の集合の正規直線の最小の個数とする。メルヒオールの証明ではが示された。 はが増えるとは無限大へ発散していくと考えた。 はを証明して、予想が正しいことを示した。 はを予想した。これは現在ディラック–モツキン予想 () と呼ばれている（詳細はを参照）。 は を証明している。 サムネイル|Böröczkyの10点と5本の正規直線の配置の例。 ディラックの予想した下限は漸近的には最もよいもので、4より大きい偶数には対応する上限がある。Károly Böröczky による上限に達した構成は、射影平面上の正角形の頂点と頂点の組で決定される方向の無限遠点個（延べ個）から成る。正角形の点から2点を選ぶ組は個あるが、つのみの方向が定まる。この配置では個の正規直線が存在し、頂点とそれに隣り合う2頂点と共線な無限遠点を結ぶ直線になる。実射影平面の任意の有限の配置として、この構成を正規直線の数を変えずにすべての点が有限点となるように変換することができる.。
奇数において、ディラックの予想の下限に一致する例は2つしか知られていない。1つはの考案した正三角形の頂点、重心 、辺の中点の7点から成る構成である。この7点は正規直線を3つのみ持つ。3つの正規直線を単一の直線に置き換えるはユークリッド平面上では実現しないが、として知られる有限の射影空間を形成する。この接続関係のために、ケリー-モーザーの例は としても呼ばれる.。他の例にマッキー () の考案した 、1辺を共有する2つの正五角形の頂点と、共有辺の中点と4つの無限遠点の延べ13点から成る配置がある。これは6つの正規直線を持つ。Böröczky の構成を修正すれば、奇数個の点で個の正規直線を持つ配置が導かれれる。
はが7である場合を除き、が成立することを証明した。漸近的には、証明された上限のである。 の場合、ケリー-モーザーの例が反例となって除外される。しかし、Csima–Sawyerの境界がにおいても有効だったならば、が主張されただろう。
似た結果にがある。これは少数の点の直線の数と一本の直線上の点の個数が対応することを述べている。
ベン・グリーンとテレンス・タオは、十分大きい点の集合に対して（適当にを選択したときとなるようにして）正規直線の数は確かに少なくともとなること示した。更に、 が奇数ならば、正規直線の数はある定数が存在して少なくともとなる。したがって、Böröczky による構成は最良であったことが判明した。正規直線の個数の最小化は、グリーンとタオが十分大きい場合について証明した、3点を通る直線の個数の最大化問題である Orchard-planting problemにも深く関係している。ordinary point を探すような双対の状態において、擬似直線の配置の ordinary point の最小を考えることができる。この場合においては、Csima-Sawyerのの下限は有効であるが、グリーンとタオの漸近的な境界が有効であるかは知られていない。
連結直線の数 ポール・エルデシュの気づきのように、シルヴェスター-ガライの定理は共線でない点の集合について少なくともつの異なる直線が決定できることを意味する。 この結果はとして知られる。基本的な場合としては、の場合が自明である。値の大きいについては、（残りの点がすべて共線とならないように注意して）1本の正規直線とその直線上の2点のうち1点を削除して、点の場合を点の場合から演繹できる。よって、定理は数学的帰納法から示すことができる。ニアペンシル () と呼ばれる個の共線点と、それらと共線でないある1点から成る配置が下限の例となる。
一般化 シルヴェスター-ガライの定理は、ユークリッド平面平面上の色付きの点の集合や、代数的または距離空間によって定義される点と直線の系に一般化できる。より一般にはこれら定理のバリエーションは、正規直線を持たない点の集合を避けるため、有限集合に対するものとなっている。
色付きの点 色付きの点におけるシルヴェスター-ガライの定理は、1960年代中期にロナルド・グラハムが提起し、が広めた。 2つの色に分けられた（すべてが同一直線上にはない）有限の点の集合について、2つ以上のすべて同色の点を通る直線が存在するかどうかを考える。集合と集合族の言葉では、（すべてが同一直線上にはない）有限の点の共線部分集合の族はを持つことはできないと表現できる。証明はによって成されたが、公表はされなかった。最初に証明を公表したのはであるこの変種における歴史については を参照。。
非実座標 代替文=A 3 by 3 grid of points, with 8 straight lines through triples of points and four more curves through triples of points on the broken diagonals of the grid|サムネイル|。2点を通る直線は3つ目の点を通る。 シルヴェスター-ガライの定理は、この配置はユークリッド平面では実現できないが、では実現できることを示す。 ユークリッド平面または射影平面が実数の組、すなわち座標を用いて定義できるように（ユークリッド平面は直交座標系、射影平面は）、 点と直線の系の抽象的な類似物は、他の数体系と座標を用いて定義できる。シルヴェスター-ガライの定理は有限体上でこのように定義された幾何学では適用できない。つまりのような有限幾何学において、すべての点の集合の正規直線は存在しない。
また、シルヴェスター-ガライの定理は複素数や四元数の組の座標を持つ幾何学においても直接は成立しないが、より複雑な類似物であれば成立する。例えば、には、9つの点（三次曲線の変曲点）の配置であるがある。ヘッセ配置において正規直線は存在しない。このような配置は、として知られ、ユークリッド平面上では成立しえない。 シルヴェスター-ガライの定理の他の方法で述べると、シルヴェスター-ガライ配置が共線性を保ちつつユークリッド平面に埋め込まれるとき、配置内の点は常に一本の直線上にある、となる。したがってヘッセ配置の例は、シルヴェスター-ガライの定理がでは偽であることを示している。一方で、 はシルヴェスター-ガライの定理の複素数への類似物として、を複素射影平面に埋め込んだ時、すべての点は2次元部分空間上になければならないことを示した。つまり、 アフィン包を全体空間とする3次元複素空間上の点の集合は必ず1つの正規直線を持たなければならない。実際には正規直線の個数は点の個数に比例する。同様に、 はを四元数で定義される空間に埋め込むとき、それらの点は必ず3次元部分空間上になければならないことを示した。
マトロイド ユークリッド平面上の点の任意の集合とそれらを繋ぐ直線は、階数3のの成分と平面に抽象化される。実数でない数体系で定義される幾何学の点と直線はマトロイドを成すが、必ずしも有向マトロイドである必要はない。この状況において、の正規直線の個数の下限の結果は、有向マトロイドへ一般化できる。個の要素を持つ階数3の有向マトロイドは、2点を通る直線を少なくとも個持つ。あるいは、より少数の2点を通る直線の持つ階数3のマトロイドは無向である必要がある.。 2点のみを通る直線がないようなマトロイドはと呼ばれる。関連して、7点と3つの正規直線を持つケリー-モーザー配置は、におけるを構成する。
距離幾何学 シルヴェスター-ガライの定理の他の一般化において、によって任意の距離空間へ予想が行われ、によって解決された。この一般化では、距離空間上の3点が三角不等式の等号を満たすとき共線であると定義され、直線は、既に直線上にある2点と共線である点の全体の集合であると定義された。ChvátalとChenによる一般化によればすべての有限距離空間には、すべての点を含むような直線かただ2点のみを通る直線が存在することが示された; ; 。
脚注
出典
外部リンク
Proof presentation by Terence Tao at the 2013 Minerva Lectures 複素版Sylvester-Gallaiの定理と超平面配置の対数的ベクトル場の分裂型 - 阿部 拓郎