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

提供: testwiki
2025年3月13日 (木) 16:24時点におけるimported>Baudanbau20による版 (→connecting lineの数)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
ナビゲーションに移動 検索に移動

テンプレート:翻訳直後

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

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

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

歴史

シルヴェスタ–ガライの定理は、テンプレート:Harvs によって提起された。テンプレート:Harvs は、シルヴェスターはテンプレート:仮リンク上の三次曲線の9つの変曲点が、9点と12直線のテンプレート:仮リンク（テンプレート:仮リンク）を成すという代数幾何学の問題に触発されたことを示唆している。シルヴェスター–ガライの定理はこの9つの変曲点がすべて実座標を持つことは不可能であることを示しているテンプレート:Sfnp。

テンプレート:Harvs は、シルヴェスター–ガライの定理の短い証明を発見したと主張したが、発表する時点ですでに、証明が不完全であることが指摘されていた。テンプレート:Harvs は、定理の射影幾何学的な双対を示すことで、正確で強力な定理を得た。テンプレート:Harvs は、メルヒオールの証明に気づかぬままテンプレート:Sfnp、定理を予想として述べ、 その後にティボル・ガライや他の数学者が証明した[4]。

1951年の評論では、エルデシュは「ガライの定理」の名を使用した[5]。1954年には、テンプレート:仮リンクの評論で「シルヴェスター–ガライの定理」という名称が使われた[6]。

同値な定理

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

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

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

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

証明

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

ケリーの証明

次はテンプレート:仮リンクによる証明である。テンプレート:Harvtxt はケリーの証明を、数多の証明の中で"simply the best"であると述べているテンプレート:Sfnp。

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

テンプレート:Mvarを ordinary でないと仮定しよう。テンプレート:Mvarは少なくともテンプレート:Mvarに属する3点以上を通る必要がある。これら共線点のうち2つ以上は、テンプレート:Mvarへのテンプレート:Mvarの直交射影テンプレート:Mvarに関して同じ側にある。この2点をテンプレート:Mvarと定義する。ただし、テンプレート:Mvarはこの順で並んでいるとする。テンプレート:Mvarをテンプレート:Mvarを通る connecting line、テンプレート:Mvarをテンプレート:Mvarのテンプレート:Mvarへの直交射影とすれば、テンプレート:Mathが相似かつテンプレート:Mathであることより、テンプレート:Mvarはテンプレート:Mvarより短いテンプレート:Sfnp。

しかし、これはテンプレート:Mvarの定義に矛盾する。これはテンプレート:Mvarが ordinary でないとした仮定が偽であることを意味する。よって題意は示されたテンプレート:Sfnp。

メルヒオールの証明

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

メルヒオールは、射影平面にテンプレート:仮リンク任意のグラフについて、オイラー標数テンプレート:Mathは1でなければならないことに気づいた。ここで、テンプレート:Mvarはそれぞれ、グラフの頂点、辺、面の個数。射影平面上の非自明な直線の配置は、面は3辺以上で囲まれ、辺は2面で囲まれるようなグラフを定義する。そのため、テンプレート:仮リンクことで不等式テンプレート:Mathを得る。この不等式によって、オイラー標数からテンプレート:Mvarを取り除くことよりテンプレート:Mathが証明できる。しかしもし、配置上のすべての頂点が3以上の直線の交点であるならば、辺の総数はテンプレート:Math以上であるが、これは不等式に矛盾する。したがって、いくつかの頂点は2直線のみの交点でなければならず、メルヒオールの慎重な分析が示すように、3個以上の ordinary vertice が少なくとも不等式テンプレート:Mathを満たす必要があるテンプレート:Sfnp。

テンプレート:Harvtxt の指摘のように、ordinary vertex の存在に関する議論は、1944年、テンプレート:仮リンクによって与えられた。スティーンロッドは ordinary line の問題の双対を明示的に応用した[7]。

メルヒオールの不等式

同様の議論で、メルヒオールはより一般的な結果を証明することができた。任意のテンプレート:Mathにおいて、テンプレート:Mvarをテンプレート:Mvar本の直線で作られる点の個数として、次の式が成立する。テンプレート:Sfnp。

∑k≥2(k−3)tk≤−3.

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

t2⩾3+∑k≥4(k−3)tk.

公理数学

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

シルヴェスター-ガライの定理の通常の主張はテンプレート:仮リンクにおいては有効でない。構成幾何学で拒否される排中律の弱いものであるLPOテンプレート:Enlinkを意味するためである。にもかかわらず、構成解析の公理の範囲のシルヴェスター-ガライの定理の定理は定式化が可能で、ケリーの証明を構成幾何学の公理の下で、有効となるように適用することができるテンプレート:Sfnp。

ordinary lineの捜索

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

テンプレート:Harvtxtのアルゴリズムはコクセターの証明をもとにしている。次の手順で示される。

  1. 与えられた点の凸包の頂点から点テンプレート:Mathを選ぶ。
  2. 直線ℓ0を、テンプレート:Mathと他の凸包の頂点を通る直線として構築する。
  3. 他の与えられた点をテンプレート:Mathと成す角で並べ替え、同じ角のものをグループ化する。
  4. グループ内のある点が孤立していれば、その点とテンプレート:Mathを通る直線が ordinary である。
  5. それぞれの2つの連続するグループに対して、2直線を、一方のグループ内のテンプレート:Mathと最も近い点と、もう一方の最も近い点を通る直線とする。
  6. このようにしてできた直線の集合内のそれぞれの直線ℓiに対して、ℓ0とℓiの交点を取る。
  7. この交点がテンプレート:Mathと一番近いようなℓiが ordinary line となる。

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

ordinary lineの個数

n/2より少ない ordinary lineを持つ有名な例。

シルヴェスター-ガライの定理は点の配置について ordinary line の存在は述べているが、ordinary line の個数については述べていない。テンプレート:Mathをテンプレート:Mvarつの共線でない点の集合のordinary lineの最小の個数とする。メルヒオールの証明ではテンプレート:Mathが示された。テンプレート:Harvs はテンプレート:Mvarが増えるにつれてテンプレート:Mathは無限大へ発散していくと考えた。テンプレート:Harvs はテンプレート:Mathを証明して、予想が正しいことを示した。 テンプレート:Harvs はt2(n)≥⌊n2⌋を予想した。これは現在ディラック–モツキン予想（Dirac–Motzkin conjecture）と呼ばれている（詳細はテンプレート:Harvtxtを参照）。 テンプレート:Harvtxt は テンプレート:Mathを証明している。

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

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

奇数テンプレート:Mvarにおいて、ディラックの予想の下限テンプレート:Mathに一致する例は2つしか知られていない。1つはテンプレート:Harvtxtの考案した正三角形の頂点、重心 、辺の中点の7点から成る構成である。この7点は ordinary line を3つのみ持つ。3つの ordinary line を持つテンプレート:仮リンクはユークリッド平面上では単一の直線に置き換えることはできないが、テンプレート:仮リンクとして知られる有限の射影空間を構成する。この接続関係のために、ケリー-モザーの例は non-Fano configuration としても呼ばれる[11]。他の例にマッキー（McKee）の考案した[10] 、1辺を共有する2つの正五角形の頂点と、共有辺の中点と4つの無限遠点の延べ13点から成る配置がある。これは6つの ordinary line を持つ。Böröczky の構成を修正すれば、奇数n個の点で3⌊n4⌋個の ordinary line を持つ配置が導かれれる[12]。

テンプレート:Harvtxt はテンプレート:Mvarが7である場合を除き、 t2(n)≥⌈6n13⌉が成立することを証明した。漸近的には、証明された上限テンプレート:Mathの12/13≈92.3%である。 テンプレート:Mathの場合、ケリー-モザーの例テンプレート:Mathが反例となって除外される。しかし、Csima–Sawyerの境界がテンプレート:Mathにおいても有効だったならば、テンプレート:Mathが主張されただろう。

似た結果にテンプレート:仮リンクがある。これは少数の点の直線の数と一本の直線上の点の数が対応されることを延べているテンプレート:Sfnp。

ベン・グリーンとテレンス・タオは、十分大きい点の集合に対して（適当にテンプレート:Mathを選択したときテンプレート:Mathとなるようにして）、ordinary line の数は確かに少なくともテンプレート:Mathとなること示した。更に、 テンプレート:Mvarが奇数ならば、ordinary line の数はある定数テンプレート:Mvarが存在して少なくともテンプレート:Mathとなる。したがって、Böröczky による構成は最良であったことが判明した。ordinary line の個数の最小化は、グリーンとタオが十分大きい場合について証明した、3点を通る直線の個数の最大化問題である Orchard-planting problemテンプレート:Enlinkにも深く関係しているテンプレート:Sfnp。ordinary point を探すような双対の状態において、擬似直線の配置の ordinary point の最小を考えることができる。この場合においては、Csima-Sawyerの⌈6n13⌉の下限は有効であるがテンプレート:Sfnp、グリーンとタオの漸近的な境界テンプレート:Mathが有効であるかは知られていない。

connecting lineの数

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

一般化

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

色付きの点

色付きの点におけるシルヴェスター-ガライの定理は、1960年代中期にロナルド・グラハムが提起し、テンプレート:仮リンクが広めた。 2つの色に分けられた（すべてが同一直線上にはない）有限の点の集合について、2つ以上のすべて同色の点を通る直線が存在するかどうかを考える。 集合と集合族の言葉では、（すべてが同一直線上にはない）有限の点の共線部分集合の族はテンプレート:仮リンクを持つことはできない、と表現できる。証明はテンプレート:仮リンクによって発表されたが、公表はされなかった。最初に証明を公表したのはテンプレート:Harvtxtである[13]。

非実座標

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
テンプレート:仮リンク。２点を通る直線は3つ目の点を通る。 シルヴェスター-ガライの定理は、この配置はユークリッド平面では実現できないが、テンプレート:仮リンクでは実現できることを示す。

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

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

マトロイド

ユークリッド平面上の点の任意の集合とそれらを繋ぐ直線は、ランク3のテンプレート:仮リンクの成分と平面に抽象化される。実数でない数の体系で定義される幾何学の点と直線はマトロイドを成すが、必ずしも有向マトロイドを成すわけではない。この状況において、テンプレート:Harvtxtの ordinary line の個数の下限の結果は、有向マトロイドへ一般化できる。ランク3のテンプレート:Mvar成分の有向マトロイドは、テンプレート:Math個の、2点を通る直線を持つ。あるいは、より少数の2点を通る直線の持つランク3のマトロイドは無向である必要がある[14]。 2点のみを通る直線がないようなマトロイドはテンプレート:仮リンクと呼ばれる。関連して、7点と3つの ordinary line を持つケリー-モザー配置は、テンプレート:仮リンクにおけるテンプレート:仮リンクを構成する[11]。

距離幾何学

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

脚注

テンプレート:Reflist

出典

テンプレート:Refbegin

テンプレート:Refend

外部リンク

  1. ↑ テンプレート:Cite book
  2. ↑ テンプレート:Cite book
  3. ↑ テンプレート:Cite book
  4. ↑ テンプレート:Harvtxt; テンプレート:Harvtxt.
  5. ↑ テンプレート:MathSciNet
  6. ↑ テンプレート:MathSciNet
  7. ↑ テンプレート:Harvtxt; Steenrod's proof was briefly summarized in テンプレート:Harvtxt.
  8. ↑ テンプレート:Harvtxt; テンプレート:Harvtxt.
  9. ↑ テンプレート:Harvtxt; テンプレート:Harvtxt.
  10. ↑ 10.0 10.1 テンプレート:Harvtxt.
  11. ↑ 11.0 11.1 テンプレート:Harvtxt.
  12. ↑ 12.0 12.1 テンプレート:Harvtxt
  13. ↑ For the history of this variation of the problem, see also テンプレート:Harvtxt
  14. ↑ テンプレート:Harvtxt.
  15. ↑ テンプレート:Harvtxt; テンプレート:Harvtxt; テンプレート:Harvtxt
「https://ja.wiki.beta.math.wmflabs.org/w/index.php?title=シルヴェスター–ガライの定理&oldid=13572」から取得