シルヴェスター–ガライの定理のソースを表示

{{翻訳直後|1=[[w:en:Sylvester-Gallai theorem|Sylvester-Gallai theorem]] oldid=1226528235|date=2024年9月}}
[[ファイル:Ordinary_lines.svg|サムネイル|4×4の格子点の3つのordinary line。]]
'''シルヴェスター–ガライの定理'''（シルヴェスター–ガライのていり<ref>{{Cite book |title=新訂版　数学用語 英和辞典: 和英索引付き |url=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|publisher=近代科学社 |date=2020-12-02 |isbn=978-4-7649-0624-2 |language=ja}}</ref>、{{Lang-en-short|Sylvester–Gallai theorem}}）は、[[幾何学]]において、[[平面]]上の[[有限集合|有限]]個の点のうち、ちょうど2点のみを通るまたはすべての点を通る[[直線]]が存在する事を示す定理<ref>{{Cite book |title=ポール・エルデス：離散数学の魅力: 伝説の講義 |url=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|publisher=近代科学社 |date=2023-08-25 |isbn=978-4-7649-0662-4 |language=ja |first=Vašek |last=Chvátal}}</ref><ref>{{Cite book|和書 |title=ボロバシュ 数学の技法 |url= |year=2022 |publisher=丸善出版 |isbn=978-4-621-30731-1}}</ref>。1893年にこの問題を提起した[[ジェームス・ジョセフ・シルベスター|ジェームス・ジョセフ・シルヴェスター]]と、1944年に最初の証明を発表した[[ティボル・ガライ]]に因んで命名された。

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

== 歴史 ==
シルヴェスタ–ガライの定理は、{{harvs|txt|authorlink=ジェームス・ジョセフ・シルベスター|year=1893|last=Sylvester|first=J. J.}} によって提起された。{{harvs|txt|year=1986|authorlink=レロイ・ミルトン・ケリー|last=Kelly}} は、シルヴェスターは{{仮リンク|複素射影平面|en|Complex projective plane}}上の[[三次曲線]]の9つの[[変曲点]]が、9点と12直線の{{仮リンク|点と直線の配置|en|Configuration (geometry)|label=配置}}（{{仮リンク|ヘッセ配置|en|Hesse configuration}}）を成すという[[代数幾何学]]の問題に触発されたことを示唆している。シルヴェスター–ガライの定理はこの9つの変曲点がすべて実座標を持つことは不可能であることを示している{{Sfnp|Elkies|Pretorius|Swanepoel|2006}}。

{{harvs|txt|author-link=ハーバート・ウッドール|year=1893a|year2=1893b|author=H. J. Woodall}} は、シルヴェスター–ガライの定理の短い証明を発見したと主張したが、発表する時点ですでに、証明が不完全であることが指摘されていた。{{harvs|txt|authorlink=エベラール・メルヒオール|year=1941|last=Melchior|first=Eberhard}} は、定理の射影幾何学的な[[射影幾何学の双対性|双対]]を示すことで、正確で強力な定理を得た。{{harvs|txt|authorlink=ポール・エルデシュ|year=1943|last=Erdős|first=Paul}} は、メルヒオールの証明に気づかぬまま{{Sfnp|Borwein|Moser|1990}}、定理を予想として述べ、 その後に[[ティボル・ガライ]]や他の数学者が証明した<ref name="stein44">{{Harvtxt|Steinberg|Buck|Grünwald|Steenrod|1944}}; {{Harvtxt|Erdős|1982}}.</ref>。

1951年の評論では、エルデシュは「ガライの定理」の名を使用した<ref>{{MathSciNet|0041447}}</ref>。1954年には、{{仮リンク|レナード・ブルーメンタール|en|Leonard Blumenthal}}の評論で「シルヴェスター–ガライの定理」という名称が使われた<ref>{{MathSciNet|0056941}}</ref>。

== 同値な定理 ==
ordinary line の存在問題は、[[平面|ユークリッド平面]]の代わりに[[射影平面]]{{Math|RP{{sup|2}}}}で考えることで、ordinary line の双対となる点の問題としても考えることができる。射影平面は通常のユークリッド平面上の点に"[[無限遠]]"を付加することで構築される。しかし、無限遠に付加された点は、ordinary line を持たない点の集合を作るのに役立つわけではない。射影平面上の任意の有限個の点が、点と直線の[[接続関係 (射影幾何学)|接続関係]]の同様の組み合わせパターンを持つユークリッド点の集合に変換されるためである。したがって、ユークリッド平面と射影平面のどちらかに存在する交点と直線のパターンは、もう一方の平面にも存在する。にもかかわらず、射影的な観点によって点と直線の配置を簡単に述べることができる。特に、{{仮リンク|射影幾何学の双対性|en|Duality (projective geometry)}}を使用することができることが重要である。この双対性の下、ordinary line の存在は、非自明な配置{{Enlink|Arrangement of lines}}の有限個の直線上の、{{Math|RP{{sup|2}}}}上の有限個の点（{{訳語疑問点範囲|ordinary point|date=2024年9月}}）の存在に置き換えることができる。ここで直線の配置が自明であるとは、すべての直線が[[共点]]であることで、非自明であるとは、ある ordinary point がちょうど2直線に属する状態を示す{{Sfnp|Borwein|Moser|1990}}。
[[ファイル:Rhombo-hexagonal_dodecahedron.png|サムネイル|[[長菱形十二面体]]。赤い平行四辺形状の面は5線の配置のordinary pointsに一致する。シルヴェスター–ガライの定理と同意な定理は、すべてのゾーン多面体上が少なくとも1つ以上の平行四辺形を持つことを示す。]]
直線の配置は[[ゾーン多面体]]（{{訳語疑問点範囲|generator|date=2024年9月}}と呼ばれる直線の有限集合の[[ミンコフスキー和]]から成る多面体）と近い組み合わせ的構造を持つ。この関係において、ゾーン多面体の対面の組は、射影平面上の直線の配置の交点と各 generator に対応する。対面の組の個数は、交点の数の2倍である。

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

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

=== ケリーの証明 ===
次は{{仮リンク|リロイ・ミルトン・ケリー|en|Leroy Milton Kelly}}による証明である。{{Harvtxt|Aigner|Ziegler|2018}} はケリーの証明を、数多の証明の中で"simply the best"であると述べている{{Sfnp|Aigner|Ziegler|2018}}。

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

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

しかし、これは{{Mvar|P, l}}の定義に矛盾する。これは{{Mvar|l}}が ordinary でないとした仮定が偽であることを意味する。よって題意は示された{{Sfnp|Aigner|Ziegler|2018}}。

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

メルヒオールは、射影平面に{{仮リンク|グラフ埋め込み|en|Graph embedding|label=埋め込まれた}}任意のグラフについて、[[オイラー標数]]{{Math|''V'' - ''E'' + ''F''}}は1でなければならないことに気づいた。ここで、{{Mvar|V, E, F}}はそれぞれ、グラフの頂点、辺、面の個数。射影平面上の非自明な直線の配置は、面は3辺以上で囲まれ、辺は2面で囲まれるようなグラフを定義する。そのため、{{仮リンク|二通りに数える論法|en|Double counting (proof technique)|label=二重に数える}}ことで不等式{{Math|''F'' ≦ {{sfrac|2''E''|3}}}}を得る。この不等式によって、オイラー標数から{{Mvar|F}}を取り除くことより{{Math|''E'' ≦ 3''V'' - 3}}が証明できる。しかしもし、配置上のすべての頂点が3以上の直線の交点であるならば、辺の総数は{{Math|3''V''}}以上であるが、これは不等式に矛盾する。したがって、いくつかの頂点は2直線のみの交点でなければならず、メルヒオールの慎重な分析が示すように、3個以上の ordinary vertice が少なくとも不等式{{Math|''E'' ≦ 3''V'' - 3}}を満たす必要がある{{Sfnp|Melchior|1941}}。 

{{Harvtxt|Aigner|Ziegler|2018}} の指摘のように、ordinary vertex の存在に関する議論は、1944年、{{仮リンク|ノーマン・スティーンロッド|en|Norman Steenrod}}によって与えられた。スティーンロッドは ordinary line の問題の双対を明示的に応用した<ref>{{Harvtxt|Aigner|Ziegler|2018|p=92}}; Steenrod's proof was briefly summarized in {{Harvtxt|Steinberg|Buck|Grünwald|Steenrod|1944}}.</ref>。

==== メルヒオールの不等式 ====
同様の議論で、メルヒオールはより一般的な結果を証明することができた。任意の{{Math|''k'' ≧ 2}}において、{{Mvar|t{{sub|k}}}}を{{Mvar|k}}本の直線で作られる点の個数として、次の式が成立する。{{Sfnp|Melchior|1941}}。

: <math>\displaystyle \sum_{k\geq2} (k-3) t_k \leq -3.</math>

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

: <math>\displaystyle t_2 \geqslant 3 + \sum_{k\geq4} (k-3) t_k.</math>

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

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

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

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

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

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

== ordinary lineの個数 ==
[[ファイル:Few-ordinary-lines.svg|サムネイル|<math>n/2</math>より少ない ordinary lineを持つ有名な例。]]
シルヴェスター-ガライの定理は点の配置について ordinary line の存在は述べているが、ordinary line の個数については述べていない。{{Math|''t''{{sub|2}}(''n'')}}を{{Mvar|n}}つの共線でない点の集合のordinary lineの最小の個数とする。メルヒオールの証明では{{Math|''t''{{sub|2}}(''n'') ≧ 3}}が示された。{{harvs|txt|author2-link=ポール・エルデシュ|last2=Erdős|last1=de Bruijn|author1-link=ニコラース・ホーヴァート・ド・ブラウン|year=1948}} は{{Mvar|n}}が増えるにつれて{{Math|''t''{{sub|2}}(''n'')}}は無限大へ発散していくと考えた。{{harvs|txt|authorlink=セオドア・モツキン|last=Motzkin|first=Theodore|year=1951}} は{{Math|''t''{{sub|2}}(''n'') ≧ {{sqrt|''n''}}}}を証明して、予想が正しいことを示した。  {{harvs|txt|authorlink=ガブリエル・アンドリュ・ディラック|first=Gabriel|last=Dirac|year=1951}} は<math>t_2(n)\ge\lfloor \frac{n}{2}\rfloor</math>を予想した。これは現在'''ディラック–モツキン予想'''（Dirac–Motzkin conjecture）と呼ばれている（詳細は{{Harvtxt|Brass|Moser|Pach|2005|p=304}}を参照）。 {{Harvtxt|Kelly|Moser|1958}} は {{Math|''t''{{sub|2}}(''n'') ≧{{sfrac|3''n''|7}}}}を証明している。
[[ファイル:Boroczky-config-even.svg|サムネイル|Böröczkyの10点と5本の ordinary linesの配置の例。]]
ディラックの予想した下限は漸近的には最もよいもので、4超過の[[偶数]]{{Mvar|n}}の上限{{Math|''t''{{sub|2}}(''n'') ≦ {{sfrac|''n''|2}}}}と対応する。[[Károly Böröczky]]による上限を達成した構築は、[[射影平面]]上の[[正多角形|正{{Mvar|m}}角形]]の頂点と頂点の組で決定される方向の[[無限遠点]]{{Mvar|m}}個（延べ{{Math|1=''n'' = 2''m''}}個）から構築される。これらの点の組は{{Math|{{sfrac|''m''(''m'' - 1)|2}}}}個あるが、{{Mvar|m}}個のみの方向を決定する。この配置では{{Mvar|m}}個の ordinary line を持ち、頂点{{Mvar|v}}とそれに隣り合う2頂点と共線な無限遠点を結ぶ点になる。実射影平面の任意の有限の配置のように、この構成は ordinary line の数を変えずにすべての点が有限点となるように帰ることができる<ref name="CM68">{{Harvtxt|Crowe|McKee|1968}}.</ref>。

[[奇数]]{{Mvar|n}}において、ディラックの予想の下限{{Math|''t''{{sub|2}}(''n'') {{=}} {{sfrac|''n'' - 1|2}}}}に一致する例は2つしか知られていない。1つは{{Harvtxt|Kelly|Moser|1958}}の考案した正三角形の頂点、[[重心]] 、辺の中点の7点から成る構成である。この7点は ordinary line を3つのみ持つ。3つの ordinary line を持つ{{仮リンク|点と直線の配置|en|Configuration (geometry)}}はユークリッド平面上では単一の直線に置き換えることはできないが、{{仮リンク|ファノ平面|en|Fano plane}}として知られる有限の[[射影空間]]を構成する。この接続関係のために、ケリー-モザーの例は non-Fano configuration としても呼ばれる<ref name="ggk00">{{Harvtxt|Geelen|Gerards|Kapoor|2000}}.</ref>。他の例にマッキー（McKee）の考案した<ref name="CM68" /> 、1辺を共有する2つの正五角形の頂点と、共有辺の中点と4つの無限遠点の延べ13点から成る配置がある。これは6つの ordinary line を持つ。Böröczky の構成を修正すれば、奇数n個の点で<math>3\lfloor \frac{n}{4}\rfloor</math>個の ordinary line を持つ配置が導かれれる<ref name="ps09">{{Harvtxt|Pach|Sharir|2009}}</ref>。

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

似た結果に{{仮リンク|ベックの定理 (幾何学)|en|Beck's theorem (geometry)|label=ベックの定理}}がある。これは少数の点の直線の数と一本の直線上の点の数が対応されることを延べている{{Sfnp|Beck|1983}}。

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

== connecting lineの数 ==
[[ポール・エルデシュ]]の気づきのように、シルヴェスター-ガライの定理は共線でない{{Mvar|n}}点の集合について少なくとも{{Mvar|n}}つの異なる直線が決定できることを意味する。 この結果は{{仮リンク|ド・ブルイン-エルデシュの定理 (接続幾何学)|en|De Bruijn–Erdős theorem (incidence geometry)|label=ド・ブルイン-エルデシュの定理}}として知られる。基本的な場合としては、{{Math|''n'' {{=}} 3}}の場合が自明である。値の大きい{{Mvar|3}}については、 （残りの点がすべて共線とならないように注意して）1本の ordinary line とその直線上の2点のうち1点を削除して、{{Mvar|n}}点を{{Math|''n'' - 1}}点に減らすことができる。よって、定理は[[数学的帰納法]]から示すことができる。ニアペンシル（near-pencil）と呼ばれる{{Math|''n'' - 1}}個の共線点と、それらと共線でないある1点から成る配置が下限の例となる<ref name="ps09" />。

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

=== 色付きの点 ===
色付きの点におけるシルヴェスター-ガライの定理は、1960年代中期に[[ロナルド・グラハム]]が提起し、{{仮リンク|ドナルド・ニューマン|en|Donald J. Newman}}が広めた。 2つの色に分けられた（すべてが同一直線上にはない）有限の点の集合について、2つ以上のすべて同色の点を通る直線が存在するかどうかを考える。  集合と[[集合族]]の言葉では、（すべてが同一直線上にはない）有限の点の共線部分集合の族は{{仮リンク|性質B|en|Property B}}を持つことはできない、と表現できる。証明は{{仮リンク|セオドア・モツキン|en|Theodore Motzkin}}によって発表されたが、公表はされなかった。最初に証明を公表したのは{{Harvtxt|Chakerian|1970}}である<ref>For the history of this variation of the problem, see also {{Harvtxt|Grünbaum|1999}}</ref>。

=== 非実座標 ===
[[ファイル:Hesse_configuration.svg|代替文=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|サムネイル|{{仮リンク|ヘッセ配置|en|Hesse configuration}}。２点を通る直線は3つ目の点を通る。 シルヴェスター-ガライの定理は、この配置はユークリッド平面では実現できないが、{{仮リンク|複素射影平面|en|Complex projective plane}}では実現できることを示す。]]
[[平面|ユークリッド平面]]または[[射影平面]]が[[実数]]の組、座標を用いて定義できるように（ユークリッド平面は[[直交座標系]]、射影平面は{{仮リンク|同次座標系|en|Homogeneous coordinates}}）、 点と直線の系の抽象的な類似物は、数と座標を用いて定義できる。シルヴェスター-ガライの定理は[[有限体]]上でこのように定義された幾何学では適応できない。つまり{{仮リンク|ファノ平面|en|Fano plane}}のような[[有限幾何学]]において、すべての点の集合の ordinary line は存在しない{{Sfnp|Aigner|Ziegler|2018}}。

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

=== マトロイド ===
ユークリッド平面上の点の任意の集合とそれらを繋ぐ直線は、ランク3の{{仮リンク|有向マトロイド|en|Oriented matroid}}の成分と平面に抽象化される。実数でない数の体系で定義される幾何学の点と直線は[[マトロイド]]を成すが、必ずしも有向マトロイドを成すわけではない。この状況において、{{Harvtxt|Kelly|Moser|1958}}の ordinary line の個数の下限の結果は、有向マトロイドへ一般化できる。ランク3の{{Mvar|n}}成分の有向マトロイドは、{{Math|{{sfrac|3''n''|7}}}}個の、2点を通る直線を持つ。あるいは、より少数の2点を通る直線の持つランク3のマトロイドは無向である必要がある<ref>{{Harvtxt|Björner|Las Vergnas|Sturmfels|White|1993}}.</ref>。 2点のみを通る直線がないようなマトロイドは{{仮リンク|シルヴェスターマトロイド|en|Sylvester matroid}}と呼ばれる。関連して、7点と3つの ordinary line を持つケリー-モザー配置は、{{仮リンク|ロタの予想|en|Rota's conjecture|label=GF(4)表現可能マトロイド}}における{{仮リンク|マテロイドマイナー|en|Matroid minor|label=禁止マイナー}}を構成する<ref name="ggk00" />。

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

== 脚注 ==
{{Reflist}}

== 出典 ==
{{Refbegin|30em}}
*{{citation|title=Proofs from THE BOOK|last1=Aigner|first1=Martin|author1-link=マーティン・アイグナー|last2=Ziegler|first2=Günter M.|author2-link=ギュンター・ツィーグラー|year=2018|edition=6th|publisher=Springer|at=Theorem 1, pp. 77–78|chapter=Chapter 11. Lines in the plane and decomposition of graphs|isbn=978-3-662-57265-8|doi=10.1007/978-3-662-57265-8_11|title-link=Proofs from THE BOOK}}
*{{citation|title=On the number of ordinary lines determined by sets in complex space|last1=Basit|first1=Abdul|last2=Dvir|first2=Zeev|last3=Saraf|first3=Shubhangi|last4=Wolf|first4=Charles|year=2019|journal=[[Discrete & Computational Geometry]]|volume=61|issue=4|pages=778–808|arxiv=1611.08740|doi=10.1007/s00454-018-0039-4|mr=3943495|s2cid=125616042}}
*{{citation|title=On the lattice property of the plane and some problems of Dirac, Motzkin, and Erdős in combinatorial geometry|last=Beck|first=József|author-link=József Beck|year=1983|journal=[[Combinatorica]]|volume=3|issue=3–4|pages=281–297|doi=10.1007/BF02579184|mr=0729781|s2cid=31011939}}
*{{citation|title=Oriented matroids|last1=Björner|first1=Anders|author1-link=Anders Björner|last2=Las Vergnas|first2=Michel|author2-link=Michel Las Vergnas|last3=Sturmfels|first3=Bernd|author3-link=Bernd Sturmfels|last4=White|first4=Neil|last5=Ziegler|first5=Günter M.|author5-link=Günter M. Ziegler|year=1993|url=https://archive.org/details/orientedmatroids0000unse/page/273|publisher=Cambridge University Press|series=Encyclopedia of Mathematics and its Applications|volume=46|page=[https://archive.org/details/orientedmatroids0000unse/page/273 273]|location=Cambridge|isbn=0-521-41836-4|mr=1226888}}
*{{citation|title=A survey of Sylvester's problem and its generalizations|last1=Borwein|first1=P.|author1-link=Peter Borwein|last2=Moser|first2=W. O. J.|year=1990|journal=[[Aequationes Mathematicae]]|volume=40|issue=1|pages=111–135|doi=10.1007/BF02112289|mr=1069788|s2cid=122052678}}
* {{Citation|title=Research problems in discrete geometry|last1=Brass|first1=Peter|last2=Moser|first2=William|last3=Pach|first3=János|authorlink3=János Pach|year=2005|publisher=Springer|location=Berlin|isbn=0-387-23815-8}}
*{{citation|title=A combinatioral &#91;sic&#93; problem|last1=de Bruijn|first1=N. G.|author1-link=ニコラース・ホーヴァート・ド・ブラウン|last2=Erdős|first2=P.|author2-link=Paul Erdős|year=1948|url=http://www.renyi.hu/~p_erdos/1948-01.pdf|journal=[[Indagationes Mathematicae]]|volume=10|pages=421–423|mr=0028289}}
*{{citation|title=Sylvester's problem on collinear points and a relative|last=Chakerian|first=G. D.|year=1970|journal=[[American Mathematical Monthly]]|volume=77|issue=2|pages=164–167|doi=10.2307/2317330|jstor=2317330|mr=258659}}
*{{citation|title=The Sylvester–Chvátal theorem|last=Chen|first=Xiaomin|year=2006|journal=[[Discrete & Computational Geometry]]|volume=35|issue=2|pages=193–199|doi=10.1007/s00454-005-1216-9|mr=2195050|doi-access=free}}
*{{citation|title=Sylvester–Gallai theorem and metric betweenness|last=Chvátal|first=Vašek|author-link=Václav Chvátal|year=2004|journal=[[Discrete & Computational Geometry]]|volume=31|issue=2|pages=175–195|doi=10.1007/s00454-003-0795-6|mr=2060634|doi-access=free}}
*{{citation|title=A problem of collinear points|last=Coxeter|first=H. S. M.|author-link=Harold Scott MacDonald Coxeter|year=1948|journal=American Mathematical Monthly|volume=55|issue=1|pages=26–28|doi=10.2307/2305324|jstor=2305324|mr=24137}}
*{{citation|title=Introduction to Geometry|last=Coxeter|first=H. S. M.|author-link=Harold Scott MacDonald Coxeter|year=1969|edition=2nd|publisher=John Wiley & Sons|pages=181–182|contribution=12.3 Sylvester's problem of collinear points|location=New York|isbn=0-471-50458-0}}
*{{citation|title=Sylvester's problem on collinear points|last1=Crowe|first1=D. W.|last2=McKee|first2=T. A.|year=1968|journal=[[Mathematics Magazine]]|volume=41|issue=1|pages=30–34|doi=10.2307/2687957|jstor=2687957|mr=0235452}}
*{{citation|title=There exist <math>6n/13</math> ordinary points|last1=Csima|first1=J.|last2=Sawyer|first2=E.|year=1993|journal=[[Discrete & Computational Geometry]]|volume=9|pages=187–202|doi=10.1007/BF02189318|mr=1194036|doi-access=free}}
*{{citation|title=Collinearity properties of sets of points|last=Dirac|first=G.|author-link=Gabriel Andrew Dirac|year=1951|journal=[[Quarterly Journal of Mathematics]]|volume=2|pages=221–227|doi=10.1093/qmath/2.1.221|bibcode=1951QJMat...2..221D|mr=0043485}}
*{{citation|title=Topologically sweeping an arrangement|last1=Edelsbrunner|first1=Herbert|author1-link=Herbert Edelsbrunner|last2=Guibas|first2=Leonidas J.|author2-link=Leonidas J. Guibas|year=1989|journal=[[Journal of Computer and System Sciences]]|volume=38|issue=1|pages=165–194|doi=10.1016/0022-0000(89)90038-X|mr=990055|doi-access=free}}
*{{citation|title=Sylvester–Gallai theorems for complex numbers and quaternions|last1=Elkies|first1=Noam|author1-link=Noam Elkies|last2=Pretorius|first2=Lou M.|last3=Swanepoel|first3=Konrad J.|year=2006|journal=[[Discrete & Computational Geometry]]|volume=35|issue=3|pages=361–373|arxiv=math/0403023|doi=10.1007/s00454-005-1226-7|mr=2202107|s2cid=1647360}}
*{{citation|title=Problem 4065|last=Erdős|first=P.|author-link=Paul Erdős|year=1943|journal=[[American Mathematical Monthly]]|volume=50|issue=1|pages=65–66|doi=10.2307/2304011|jstor=2304011|department=Problems for solution: 4065–4069}}
*{{citation|title=Personal reminiscences and remarks on the mathematical work of Tibor Gallai|last=Erdős|first=P.|author-link=Paul Erdős|year=1982|url=http://www.math-inst.hu/~p_erdos/1982-22.pdf|journal=[[Combinatorica]]|volume=2|issue=3|pages=207–212|doi=10.1007/BF02579228|mr=0698647|s2cid=1135308}}
*{{citation|title=The excluded minors for GF(4)-representable matroids|last1=Geelen|first1=J. F.|author1-link=Jim Geelen|last2=Gerards|first2=A. M. H.|last3=Kapoor|first3=A.|year=2000|url=http://www.math.uwaterloo.ca/~jfgeelen/Publications/gf4.pdf|archive-url=https://web.archive.org/web/20100924110912/http://www.math.uwaterloo.ca/~jfgeelen/publications/gf4.pdf|archive-date=2010-09-24|journal=[[Journal of Combinatorial Theory]]|series=Series B|volume=79|issue=2|pages=247–299|doi=10.1006/jctb.2000.1963|mr=1769191|url-status=dead}}
*{{citation|title=On sets defining few ordinary lines|last1=Green|first1=Ben|author1-link=ベン・グリーン|last2=Tao|first2=Terence|author2-link=テレンス・タオ|year=2013|journal=Discrete & Computational Geometry|volume=50|issue=2|pages=409–468|arxiv=1208.4714|doi=10.1007/s00454-013-9518-9|mr=3090525|s2cid=15813230}}
*{{citation|title=Monochromatic intersection points in families of colored lines|last=Grünbaum|first=Branko|author-link=ブランコ・グレンバウム|year=1999|url=https://sites.math.washington.edu/~grunbaum/BG229.pdf|journal=[[Geombinatorics]]|volume=9|issue=1|pages=3–9|mr=1698297}}
*{{citation|title=A resolution of the Sylvester–Gallai problem of J. P. Serre|last=Kelly|first=L. M.|author-link=リロイ・ミルトン・ケリー|year=1986|journal=[[Discrete and Computational Geometry]]|volume=1|issue=2|pages=101–104|doi=10.1007/BF02187687|mr=0834051|doi-access=free}}
*{{citation|title=On the number of ordinary lines determined by <math>n</math> points|last1=Kelly|first1=L. M.|author1-link=リロイ・ミルトン・ケリー|last2=Moser|first2=W. O. J.|year=1958|journal=[[Canadian Journal of Mathematics]]|volume=10|pages=210–219|doi=10.4153/CJM-1958-024-6|mr=0097014|s2cid=123865536|doi-access=free}}
*{{cite thesis|last=Lenchner|first=Jonathan|date=2008|title=Sylvester-Gallai results and other contributions to combinatorial and computational geometry|url=https://dl.acm.org/doi/book/10.5555/1467469|type=Ph.D. Thesis|chapter=|publisher=|docket=|oclc=|access-date=}}
*{{citation|title=A constructive version of the Sylvester–Gallai theorem|last=Mandelkern|first=Mark|year=2016|journal=[[Acta Mathematica Hungarica]]|volume=150|pages=121–130|arxiv=2402.03662|doi=10.1007/s10474-016-0624-z|mr=3542040|s2cid=124023963}}
*{{citation|title=Über Vielseite der Projektive Ebene|last=Melchior|first=E.|author-link=Eberhard Melchior|year=1941|journal=[[Deutsche Mathematik]]|volume=5|pages=461–475}}
*{{citation|title=The lines and planes connecting the points of a finite set|last=Motzkin|first=Th.|author-link=セオドア・モツキン|year=1951|journal=[[Transactions of the American Mathematical Society]]|volume=70|issue=3|pages=451–464|doi=10.2307/1990609|jstor=1990609|mr=0041447|doi-access=free}}
*{{citation|title=On the ordinary line problem in computational geometry|last1=Mukhopadhyay|first1=A.|last2=Agrawal|first2=A.|last3=Hosabettu|first3=R. M.|year=1997|journal=Nordic Journal of Computing|volume=4|issue=4|pages=330–341|mr=1607014}}
*{{citation|title=The ordinary line problem revisited|last1=Mukhopadhyay|first1=Asish|last2=Greene|first2=Eugene|year=2012|journal=[[Computational Geometry (journal)|Computational Geometry: Theory and Applications]]|volume=45|issue=3|pages=127–130|doi=10.1016/j.comgeo.2011.10.003|mr=2853475|doi-access=free}}
*{{citation|title=Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures|last1=Pach|first1=János|author1-link=János Pach|last2=Sharir|first2=Micha|author2-link=Micha Sharir|year=2009|publisher=[[American Mathematical Society]]|series=Mathematical Surveys and Monographs|volume=152|pages=1–12|contribution=Chapter 1. Sylvester–Gallai Problem: The Beginnings of Combinatorial Geometry}}
*{{citation|title=A reverse analysis of the Sylvester–Gallai theorem|last=Pambuccian|first=Victor|year=2009|url=http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.ndjfl/1257862037|journal=[[Notre Dame Journal of Formal Logic]]|volume=50|issue=3|pages=245–260|doi=10.1215/00294527-2009-010|mr=2572973|doi-access=free}}
*{{citation|title=Twenty problems on convex polyhedra, part I|last=Shephard|first=G. C.|author-link=ジェフリー・コリン・シェパード|year=1968|journal=The Mathematical Gazette|volume=52|issue=380|pages=136–156|doi=10.2307/3612678|jstor=3612678|mr=231278|s2cid=250442107}}
*{{citation|title=Three point collinearity (solution to problem 4065)|last1=Steinberg|first1=R.|last2=Buck|first2=R. C.|last3=Grünwald|first3=T.|author3-link=Tibor Gallai|last4=Steenrod|first4=N. E.|author4-link=Norman Steenrod|year=1944|journal=[[American Mathematical Monthly]]|volume=51|issue=3|pages=169–171|doi=10.2307/2303021|jstor=2303021}}
*{{citation|title=Mathematical question 11851|last=Sylvester|first=J. J.|author-link=ジェームス・ジョセフ・シルベスター|year=1893|journal=The Educational Times|volume=46|issue=383|pages=156}}
*{{citation|title=Mathematical question 11851 answered|last=Woodall|first=H. J.|author-link=H. J. Woodall|year=1893a|journal=The Educational Times|volume=46|issue=385|page=231}}
*{{citation|title=Mathematical question 11851 answered|last=Woodall|first=H. J.|author-link=H. J. Woodall|year=1893b|url=https://books.google.com/books?id=qtUGAAAAYAAJ&q=%2211851%22+woodall&pg=PA98|journal=Mathematical Questions and Solutions from the Educational Times|volume=59|page=98}}
{{Refend}}

== 外部リンク ==

* {{Citation|title=A discrete geometrical gem|last=Malkevitch, Joseph|year=2003|url=http://e-math.ams.org/featurecolumn/archive/sylvester1.html|archive-url=https://web.archive.org/web/20061010192721/http://e-math.ams.org/featurecolumn/archive/sylvester1.html|archive-date=2006-10-10|journal=AMS Feature Column|publisher=[[American Mathematical Society]]}}
* {{MathWorld|title=Ordinary Line}}
* [https://www.youtube.com/watch?v=6mG9HG4lfgI&t=12m16s Proof presentation] by [[テレンス・タオ|Terence Tao]] at the 2013 Minerva Lectures
* [https://repository.kulib.kyoto-u.ac.jp/dspace/bitstream/2433/279907/1/2022-12.pdf 複素版Sylvester-Gallaiの定理と超平面配置の対数的ベクトル場の分裂型] - 阿部 拓郎
{{DEFAULTSORT:しるうえすたあからいのていり}}
[[Category:証明を含む記事]]
[[Category:マトロイド理論]]
[[Category:幾何学の定理]]
[[Category:数学のエポニム]]
[[Category:数学に関する記事]]