9にまつわるある数学（証明編）

前回の記事で紹介した「点の個数・直線の個数が最小の3-配置は9個の点と9本の直線からなる」という主張の証明を書きます。なお3-配置などの用語の定義については適宜前回の記事を参照してください。

まずどんな3-配置においても、そこに現れる点の個数と直線の個数は同じです。これは次のようにすれば分かります。まず3-配置に現れる点と直線に対し、「点 A が直線 a の上に載っている」を満たすような点 A と直線 a のペアを (A, a) のように書いて全て書き出します。ペアの一覧の中に各点はちょうど3回ずつ現れるはずなので、書き出したペアの個数は （点の個数）× 3 個あるはずです。一方でペアの一覧の中に各直線はちょうど3回ずつ現れるはずなので、書き出したペアの個数は（直線の個数）× 3 個あるはずです。ペアの個数が計算方法によって変わるなんてことは起こらないので、（点の個数）× 3 =（ペアの個数）=（直線の個数）× 3 となっている必要があります。従って点の個数と直線の個数は等しくなければなりません。なお、これと同じ議論は1-配置でも2-配置でも、より一般に n-配置（ n は 1 以上の整数）でもできるので、n-配置に現れる点の個数と直線の個数は必ず同じになります。

それでは具体的な議論に移りましょう。まず3-配置には直線が少なくとも1本含まれています。

3-配置の定義からこの直線の上にはちょうど3個の点を置く必要があります（これらの点を A, B, C とします）。

これらの3点のそれぞれについて、今ある直線以外にあと2本ずつその点を通る直線を置く必要があります。

ここまでで置いた直線の本数を数えてみると、ちょうど7本あります。従って、3-配置には直線が7本以上含まれなくてはなりません。上で議論したことと合わせると、3-配置には点も7個以上含まれなくてはなりません。

従って、「点の個数・直線の個数が最小の3-配置は9個の点と9本の直線からなる」ということを示すためには次の3つのことを示せば良いです：

  • 9個の点と9本の直線からなる3-配置は存在する

  • 7個の点と7本の直線からなる3-配置は存在しない

  • 8個の点と8本の直線からなる3-配置は存在しない

「9個の点と9本の直線からなる3-配置は存在する」については前回の記事で構成方法を説明したので、この記事では残りのふたつを順番に示していきましょう。

7個の点と7本の直線からなる3-配置は存在しない

（射影変換および実射影平面を知っている人は「余談」を見てください。）

7個の点と7本の直線からなる3-配置を作ろうとしてみます。上で描いた「3個の点と7本の直線からなる図」を思い出しましょう。

この図を念頭に置いて、図の真ん中の点 B と B から左上・右上に伸びる2本の直線だけを取り出した図を描いてみます。

この2本の直線にはそれぞれあと2個ずつ、合計4つの A と C 以外の点が乗っている必要があります（それぞれ D, E と F, G とします）。この4つの点 D, E, F, G と B との位置関係は、必要なら回転させたり点の名前の変更を行うことで次の3通りのいずれかだとみなせます：

ここで2本の直線の開き具合の違いは無視しています（開き具合が違っても今後の議論に支障は出ない）。さてまず左の位置関係について考えてみましょう。 A, B, C, D, E, F, G はちょうど7個なのでの、3-配置に現れる点はこれで全てです。ここで A から伸びる直線 AC 以外の2直線について考えましょう。これらの2本の直線は B も C も通ることができません（もし B, C のいずれかを通ってしまうとその直線は直線 AC に一致してしまう）。従ってこれらの2直線はどちらも D, E, F, G のうち2つ以上の点を通ります。 C から伸びる直線 AC 以外の2直線についても同様なので、 A または C から伸びる直線 AC 以外の4直線はどれも D, E, F, G のうち2つ以上の点を通ります。一方で D, E, F, G のうち2つ以上の点を通る直線は直線 DE, DF, DG, EF, EG, FG の6本です。

直線 DE, DF, DG, EF, EG, FG の中で直線 DE と直線 FG はすでに B を通っているので A も C も通りません（もし A か C を通ってしまうと直線 AC と一致してしまう）。従って D, E, F, G のうち2つ以上の点を通る直線であって A か C を通りうる直線は直線 DF, DG, EF, EG の4本しかありません。先ほど得た「 A または C から伸びる直線 AC 以外の4直線はどれも D, E, F, G のうち2つ以上の点を通る」という結果と合わせると、次が分かります：A または C から伸びる直線 AC 以外の4直線は直線 DF, DG, EF, EG である。従って特に直線 DF, DG, EF, EG はどれもこの3-配置の一部に含まれる必要があります。

ここまでの議論から、直線 DF, DG, EF, EG のうちちょうど2本が A を、残りの2本が C を通るということが分かります。よって A, C はこれらの直線の交点でなくてはなりません。少し考えると A, C は特に DF と EG の交点であるか DG と EF の交点であるかのどちらかでなくてはならないことも分かります。ひとまず DG と EF の交点を A 、 DF と EG の交点を C として図を描いてみます（ A と C を逆にしても以下の議論は同様にできるのでそちらは省略する）。

さてここまでの議論は A, B, C が一直線上に並んでいるという仮定から出発していたのでした。しかしこの図ではそうなっていません。これはこの図がたまたま上手くいかなかったというわけでなく、このような D, E, F, G と B の位置関係から始めて図を作ると（ D, E, F, G の場所をこの図のような位置関係を保ったままズラしてみたとしても） A, B, C が一直線上に並ぶことはありません。このことは次のようにして分かります。 A, B, C が一直線上に並ぶということはつまり C が直線 AB 上にあるということです。

図の作り方を考えてみると、このような D, E, F, G と B の位置関係から始めると点 A は常に次の緑で塗られた領域の内側に含まれることが分かります。このとき直線 AB も緑で塗られた領域に含まれるので、 C もこの緑で塗られた領域の内側にある必要があります。

しかし、図の作り方を考えてみると C は緑の領域の外側にしか存在できないことが分かります。従って A, B, C は一直線上に並ぶことはありません。これは A, B, C が一直線上に並んでいるという仮定から考察を始めていたことに矛盾します。

他の2通りの位置関係においても同様に議論を行い同様の図を描くことで同様の矛盾が生じることが分かります。

従って7個の点と7本の直線からなる3-配置は存在しません。

8個の点と8本の直線からなる3-配置は存在しない

8個の点と8本の直線からなる3-配置を作ろうとしてみます。「3個の点と7本の直線からなる図」を思い出します。

8個の点と8本の直線からなる3-配置を作ろうとするなら、あともう1本直線を置く必要があります。この新しい直線は、直線 AB と平行であるか直線 AB と交わるかの大きく2通りの置き方があります。

「新しい直線」が直線 AB と平行な場合

まずこの「新しい直線」が直線 AB と平行な場合を考察します。直線 AB と「新しい直線」だけを取り出して図を描いてみます。

この2本の直線の上に乗っている点はそれぞれ3個ずつあるので、合計6個の点がこれらの直線の上に乗っています（それぞれ A, B, C 、 D, E, F とします）。

「3個の点と7本の直線からなる図」を思い出すと、 A, B, C のいずれかを通る直線は直線 AB 以外にちょうど6本あります。この6本の直線はそれぞれ A, B, C のうちちょうど1個の点を通りまた D, E, F のうち1個以下の点しか通ることができません（ A, B, C のうち2個以上の点を通ると直線 AB に一致してしまうし、 D, E, F のうち2個以上の点を通ると直線 DE に一致してしまう）。従ってA, B, C のいずれかを通る直線 AB 以外の6本の直線はそれぞれ A, B, C, D, E, F 以外の点を1個以上通らなくてはなりません。

ここでこの3-配置に含まれる点が全部で8個だったことを思い出すと、この3-配置には直線 AB, DE に乗っていない点がちょうど2個含まれます。これらを G, H と呼ぶことにします。すると、A, B, C のいずれかを通る直線 AB 以外の6本の直線はそれぞれ G, H のうち1個以上の点を通らなくてはなりません。一方で3-配置の定義から G, H のいずれかを通る直線は6本以下です。従って G, H のいずれかを通る直線はちょうど6本で、それらは全て A, B, C のいずれか1個のみを通ります。特に直線 GH はこの3-配置には含まれません（ G を通る直線も H を通る直線もちょうど3本ずつなので、直線 GH がこの3-配置に含まれたとすると G, H のいずれかを通る直線が合計5本になってしまう）。

ここまでのことをまとめると、次のようになります： G, H のいずれかを通る直線はちょうど6本で、それらは全て A, B, C のうちちょうど1個のみを通り、G, H のうちちょうど1個のみを通る。3-配置の定義からこれらの6本の直線はそれぞれちょうど3点ずつを通る必要があるので、 D, E, F のうちちょうど1個のみを通ることも分かります。

このまとめをさらに書き換えると、 G, H のそれぞれから出る3つの直線は全て直線 AB, DE の両方と交わることおよびそれらの交点は A, B, C, D, E, F のいずれかであること、そして直線 GH は配置に含まれないということが分かったことになります。

さて、 G と直線 AB, DE との位置関係は、必要なら回転させることで次の2通りのいずれかだとみなせます：

G から出る3つの直線は全て直線 AB, DE の両方と交わるので、 G から出る3つの直線と AB, DE との交わり方は次のようになっています。

G から出る3つの直線と直線 AB, DE との交点は A, B, C, D, E, F のいずれかでした。つまり、 A, B, C, D, E, F は次のいずれかの黒い点の位置に置く必要があります。

ここではじめに描いた2本の直線の絵に戻りましょう。

この2本の直線の上にはそれぞれ3個ずつの点 A, B, C 、 D, E, F が乗っているのでした。必要なら点の名前を変更することで、それらは次のような順番に並んでいるとみなせます。

A, B, C、D, E, F の順番がこの図と一致する、あるいは回転することによってこの図と一致するように先ほどの図の黒い点の位置に A, B, C, D, E, F を配置するやり方は次で全てです：

この4つの図を観察すると、実は G を通る3つの直線の組の候補は直線 AF, BE, CD の組もしくは直線 AD, BE, CF の組しかないことが分かります。

ここまで G について議論しましたが H についても同様の議論ができるので、 G, H のそれぞれを通る3つの直線の組の候補は直線 AF, BE, CD の組もしくは直線 AD, BE, CF の組しかありません。ここで G と H は異なる点なので、結局この両方の組が配置に含まれなくてはなりません。特に直線 BE はこの配置に含まれていて、 G と H の両方を通っています。次は直線 AF, BE, CD が G を、直線 AD, BE, CF が H を通る場合の図です（ G と H を逆にしてもこの後の議論は変わらない）。

さて直線 BE が G と H の両方を通っているので直線 BE は直線 GH と一致します。しかし直線 GH はこの3-配置に含まれていないはずなので、これは矛盾です。

従って「「新しい直線」が直線 AB と平行な場合」には8個の点と8本の直線からなる3-配置を作ることはできません。

「新しい直線」が直線 AB と交わる場合

（射影変換および実射影平面を知っている人は「余談」を見てください。）

それではもうひとつの可能性である、「新しい直線」が直線 AB と交わる場合を考えましょう。次のような図を描きます（ここで2本の直線の開き具合が違っていてもこの後の議論は同じなので、この図を使って考察して問題ありません）。

「3個の点と7本の直線からなる図」を思い出すと、 A, B, C にはすでにそれぞれちょうど3本の直線が通ってしまっているので、「新しい直線」は A, B, C のいずれも通ることはありません。また直線 AB 上には A, B, C 以外の点を置くことはできないので、直線 AB と「新しい直線」の交点には点を配置できないということが分かります。従って直線 AB と「新しい直線」の上に乗っている点はそれぞれ3個ずつで、合計6個の点がこれらの直線の上に乗っています。これらの点をそれぞれ A, B, C 、 D, E, F として、これらの直線に乗っていない残り2つの点を G, H とすることにします。すると「平行な場合」での議論と同様にして、 G, H のそれぞれから出る3つの直線は全て直線 AB, DE の両方と交わることおよびそれらの交点は A, B, C, D, E, F のいずれかであること、そして直線 GH は配置に含まれないということが分かります。今回の場合特に G, H のそれぞれから出る3つの直線は全て直線 AB, DE の交点を通らないということも分かります。

G と直線 AB, DE との位置関係は、必要なら回転させることで次の図のようになっているとみなせます。

G から出る3つの直線は全て直線 AB, DE の両方と交わりかつ直線 AB, DE の交点を通らないので、 G を通る直線は次の3つのタイプのいずれかになっています：①直線 AB, DE の交点から上に伸びる直線と右に伸びる直線に交わる直線、②直線 AB, DE の交点から上に伸びる直線と左に伸びる直線に交わる直線、③直線 AB, DE の交点から下に伸びる直線と右に伸びる直線に交わる直線。

G を通る3つの直線と直線 AB, DE との交わり方の組は、必要なら回転させたり鏡写しにすることで次の6通りのいずれかだとみなせます：①①①、①①②、①②②、①②③、②②②、②②③。

G から出る3つの直線と直線 AB, DE との交点は A, B, C, D, E, F のいずれかだったので、 A, B, C, D, E, F は次のいずれかの黒い点の位置に置く必要があります。

この6通りの図を観察すると、まず A, B, C, D, E, F と直線 AB, DE の交点との位置関係が、必要なら回転させたり鏡写しにしたり点の名前を変更することで、次の3通りのいずれかになっていることが分かります：

A, B, C、D, E, F の順番がこの図と一致する、あるいは回転することによってこの図と一致するように先ほどの図の黒い点の位置に A, B, C, D, E, F を配置するやり方は次で全てです（左の図については4通り、真ん中の図については2通り、右の図については4通り）：

これらの図を観察すると、左・真ん中・右の図で表されていた3通りの位置関係のいずれについても、これらの図に現れる G を通る3つの直線の組は直線 AF, BE, CD の組もしくは直線 AD, BE, CF の組の2通りしかないことが分かります。従って3通りのどの位置関係においても G を通る3つの直線の組の候補は直線 AF, BE, CD の組もしくは直線 AD, BE, CF の組しかないことが分かります。

ここまで G について議論しましたが H についても同様の議論ができるので、 G, H のそれぞれを通る3つの直線の組の候補は直線 AF, BE, CD の組もしくは直線 AD, BE, CF の組しかありません。ここで G と H は異なる点なので、結局この両方の組がこの3-配置に含まれなくてはなりません。特に直線 BE はこの3-配置に含まれていて、 G と H の両方を通っています。直線 BE は G と H の両方を通っているので直線 GH と一致しており、従って直線 GH はこの3-配置に含まれています。しかし直線 GH はこの3-配置に含まれていないはずだったので、これは矛盾です。

従って「「新しい直線」が直線 AB と交わる場合」にも8個の点と8本の直線からなる3-配置を作ることはできません。

よって、8個の点と8本の直線からなる3-配置が存在しないことが分かり、最終的に点の個数・直線の個数が最小の3-配置は9個の点と9本の直線からなるということが分かりました。

余談

射影変換および実射影平面を知っている人向けの注意

普通の平面上での3-配置は、実射影平面から無限遠直線を除いた部分を平面と同一視した後各直線を無限遠直線の部分まで適切に延長することによって、そのまま実射影平面上の3-配置だと思うことができます。射影変換によって共点・共線関係は変わらないので実射影平面上の3-配置を射影変換で写したものはやはり実射影平面上の3-配置になります。このことを用いて考える構図を簡単にすることができます。

7個の点と7本の直線からなる3-配置が存在しないことの証明は次のようにすれば楽に行うことができます。7個の点と7本の直線からなる3-配置を作ろうとしてみます。まず「3個の点と7本の直線からなる図」を描きます。

この図について、直線 AB を無限遠直線に写すような射影変換を適用します*1。この射影変換によって A, B, C は無限遠直線上の点に写され、 A, B, C のいずれかを通る直線 AB 以外の残り2本ずつの直線は射影平面から無限遠直線を除いた部分で見るとそれぞれ平行な2直線のペアに写されます。さらに異なるペアに含まれる直線は無限遠直線上で異なる点と交わっているので、異なるペアに含まれる直線どうしは射影平面から無限遠直線を除いた部分で交わります。無限遠直線上にはすでに3点を置いているので射影平面から無限遠直線を除いた部分に残りの4点を置かなくてはなりません。従ってこの3-配置を射影平面から無限遠直線を除いた部分に制限したものは、平面上の4点と平行な2直線の3ペアの配置であって異なるペアに含まれる直線同士は平行ではないかつ各点を通る直線がちょうど3本になっているものでなくてはなりません。なので平面上でこのような配置を作ることを目標にして図を描いてみます。平面上に平行な2直線を2ペア置いた図を描くと次のようになります。

これらの2ペアは4点で交わります。この後置くことができる直線は平行な2直線1ペアしかないので、この図に現れている交点にしか点を置くことができません（直線が3本以上通りうる場所はこの図ですでに直線が2本以上通っている場所しかない）。一方で配置しようとしている点はちょうど4個あるので、この図に表れている交点全てに点を置かなくてはなりません（これらの点を D, E, F, G とします）。

各点にちょうど3本の直線が通るためには、残りの2直線は直線 DG と直線 EF でなくてはなりません。

しかし、直線 DG と直線 EF は平面上で交わってしまうので、平行にはなりません。これらは平行な2直線のペアになっているはずなのでこれは矛盾です。

8個の点と8本の直線からなる3-配置が存在しないことの証明についても、「新しい直線」が直線 AB と交わる場合の議論をほとんど省略することができます。「新しい直線」が直線 AB と交わる場合について次のような図を考えましょう（ここで2つの直線の開き具合の違いはこの後の議論に影響しません）。

「3個の点と7本の直線からなる図」を思い出すと、 A, B, C にはすでにそれぞれちょうど3本の直線が通ってしまっているので、「新しい直線」は A, B, C のいずれも通ることはありません。また直線 AB 上には A, B, C 以外の点を置くことはできないので、直線 AB と「新しい直線」の交点には点を配置できないということが分かります。従って直線 AB と「新しい直線」の上に乗っている点はそれぞれ3個ずつで、合計6個の点がこれらの直線の上に乗っています（次の図はそのような配置の例です）。

ここで直線 AB と「新しい直線」との交点を無限遠直線上に写し、3-配置に含まれる点を無限遠直線上に写さないような射影変換を行う*2と、直線 AB と「新しい直線」は射影平面から無限遠直線を除いた部分では平行な2直線に写るため、「新しい直線」が直線 AB と平行な場合に議論を帰着することができます。

「n-配置」という用語について

本稿での n-配置は [Grünbaum] で（ユークリッド平面で考えた場合の）geometric n-configuration と呼ばれているものに相当します。「配置」という日本語は "configuration" という英語の（執筆者による勝手な）訳で、この訳が本当にふさわしいかどうかは分かりません（ [HC] ではコンフィギュラチオンと呼ばれているが、これはおそらくドイツ語 "Konfiguration" の音写）。なお同じく「配置」と訳される語に "arrangement" （例えば "hyperplane arrangement" という用語の訳として「超平面配置」が用いられている）がありますが、 "configuration" と "arrangement" には若干のニュアンスの違いがあるようで、その訳し分けをした方が良いかもしれない……。

参考文献

配置について

[Grünbaum] Branko Grünbaum, Configurations of Points and Lines. Graduate Studies in Mathematics 103. American Mathematical Society, Providence, RI, 2009. ISBN: 978-0-8218-4308-6. URL

配置についての本。今回の記事は主にこの本の1.1〜1.3節と2.0〜2.1節を参考に書きました。今回の記事での「9個の点と9本の直線からなる3-配置」の図は p.6 の Figure 1.1.6 を参考にしました。また「7個の点と7本の直線からなる3-配置が存在しないこと」の証明は p.63 で紹介されているSchröterの議論を、「8個の点と8本の直線からなる3-配置が存在しないこと」の証明は pp.62〜63 の議論を参考にしつつ考えました。

[HC] D. ヒルベルト, S. コーン゠フォッセン（著）, 芹沢 正三（訳）, 直観幾何学, 新装版. みすず書房. 2019.（初版は1966年）ISBN: 978-4-622-08828-8. URL

（David Hilbert, Stefan Cohn-Vossen, Anschauliche Geometrie. Grundlehren der mathematischen Wissenschaften 37. Springer-Verlag Berlin, Heidelberg, 1932. ISBN: 978-3-662-35855-9. URL の和訳）

図を描くなどの「直観的」な議論によって色々な幾何学を紹介する本。3章の射影幾何についての章が配置（この本では「コンフィギュラチオン」と呼ばれている）の考察に充てられていて、特に15〜17節で7〜9個の点と7〜9本の直線からなる3-配置が扱われています。配置について日本語で読める本はもしかするとこの本しかないかも……？ただ翻訳がちょっと読みにくい（数十年前の訳なので仕方ないが……）し議論も射影幾何に寄っているので、配置について勉強するなら [Grünbaum] の方が良さげな感じがします。

射影変換について

[西山] 西山 享, 射影幾何学の考え方. 数学のかんどころ 19. 共立出版, 2013. ISBN: 978-4-320-11061-8. URL

射影幾何についての本。特に3章・4章で実射影平面や射影変換の性質が紹介されています。

*1:実射影平面上の任意の2直線 l, m について、 l を m に写すような射影変換はいつでも存在する（ [西山] p.95 の定理 3.14）。

*2:3-配置に含まれる点は有限個なので、直線 AB と「新しい直線」との交点を通り3-配置に含まれるどの点も通らないような実射影平面上の直線が存在する。この直線を無限遠直線に写すような射影変換はここで要求している性質を満たす射影変換になっている。

9にまつわるある数学

9は、いろいろな性質を持つ、楽しくて、すごい数。たくさんの可能性があるんだ。あ、これは数学の話なんだけど……
（夕霧綴理、104期 OPENING！Fes×LIVEでのMCにて*1）

点と直線をいくつか用意して、それらを平面上に配置することを考えます。ただし点同士をぴったり重ねて置いたり、直線同士をぴったり重ねて置いたりはしないことにします。

1個の点と1本の直線を平面上に配置するやり方は大きく分けて2通りあります：点が直線の上に乗っているか、そうでないかの2通りです。あるいは同じことですが、直線が点を通っているか、そうでないかの2通りです。

右の図の点に注目すると、点はちょうど1本の直線の上に乗っています。直線に注目すると、直線はちょうど1個の点を通っています。このように、どの点もちょうど1本の直線の上に乗っていて、どの直線もちょうど1個の点を通っているような点と直線の配置のことを1-配置（1-configuration）と呼ぶことにします。1個の点と1本の直線からなる1-配置は1-配置の中でも点の個数・直線の個数が最小のものになっています。

この1-配置の定義をまねて、どの点もちょうど2本の直線の上に乗っていて、どの直線もちょうど2個の点を通っているような点と直線の配置のことを2-配置（2-configuration）と呼ぶことにしましょう。とりあえず定義はしてみましたが、2-配置はそもそも存在するでしょうか？

紙に描いたりして考えてみると、例えば次のような2-配置があることが分かります。

これは3個の点と3本の直線からなる2-配置です。実はこの3個の点と3本の直線からなる2-配置は2-配置の中でも点の個数・直線の個数が最小のものになっています。これは次のように考えると分かります。

まず2-配置には直線が少なくとも1本は含まれています。2-配置を作りたいなら、この直線の上にはちょうど2個の点を置く必要があります。

2-配置では今配置した2点はちょうど2本の直線の上に乗っていなくてはならないので、それぞれの点を通る直線をさらに1本ずつ置く必要があります。

従って、まず2-配置には3本以上の直線が含まれなくてはならないことが分かります。配置しようとしている2直線を試しに点線で表してみました。これらの直線もちょうど2個の点を通る必要があるので、少なくともさらにあと1個点を置く必要があります。従って、2-配置には3個以上の点が含まれなくてはならないことも分かります。まとめると、2-配置には3個以上の点と3本以上の直線が含まれなくてはなりません。

1-配置、2-配置と来れば次は3-配置です。3-配置（3-configuration）とはどの点もちょうど3本の直線の上に乗っていて、どの直線もちょうど3個の点を通っているような点と直線の配置のことです。3-配置は存在するでしょうか、そしてもし存在するなら点の個数や直線の個数が最小の3-配置は何個の点・何本の直線を含んだ配置になるのでしょうか？

実は3-配置は存在します。次の図は点の個数・直線の個数がどちらも最小になっている3-配置の一例を描いたものです。

つまり、次のことが知られています：点の個数・直線の個数が最小の3-配置は9個の点と9本の直線からなる。

（なお、図の上や左下や右下の部分を見るとこの配置において直線は9個の点以外の場所でも交わっていることが分かります。3-配置は点と直線の配置ですが、直線同士が交わっているところ全てに点を置かなくてはならないという決まりは無いので、直線を置いた時にそれらがたまたま勝手に交わってしまっても問題ありません。）

同様にして4-配置、5-配置、……とさらに考えていくことも可能です。点の個数・直線の個数が最小の4-配置は18個の点と18本の直線からなることが知られています*2。5-配置については、点の個数・直線の個数が最小の5-配置は25〜48個の点と25〜48本の直線からなるものであるということまでは分かっているようです*3が、それ以上はまだ分かっておらず未解決のようです*4。

以上、9にまつわる数学のご紹介でした。

構成方法

流石に紹介だけだと不親切すぎると思ったので「点の個数・直線の個数が最小の3-配置は9個の点と9本の直線からなる」ということの証明を書きます。書こうと思ったのですが証明がかなり長くなってしまったので、ここでは「9個の点と9本の直線からなる3-配置の構成方法」だけ述べて残りの部分は次回の記事で証明することにします。

上で紹介した図から9個の点と9本の直線からなる3-配置が存在することは明らかだろうと思うかもしれませんが、あの図を作った人（私）がずるをしていて、実は図がフェイクだという可能性もあります。というわけで本当に作れることを示すために、9個の点と9本の直線からなる3-配置の具体的な作り方の例を紹介します。

まず3個の点（A, B, C）と3本の直線を配置して正三角形 ABC を作ります。

AE:EB = BF:FC = CD:DA を満たすように、正三角形 ABC の辺上に点 D, E, F を置きます。

D, E, F から2点ずつ選んで直線で結ぶと、 D, E, F の置き方から再び正三角形 DEF を描くことができます。

次に点 G, H の位置を決めます。これはすこしトリッキーです。まず直線 AE と直線 AF に注目します。

直線 AE と直線 AF の間の傾きであって A を通る直線（図では点線で表されている）を描き、その直線と直線 DE および直線 EF との交点をそれぞれ G', H' とします。

上で描いた点線の角度をすこしずつ変えていくと、 G' と H' の位置も変わります。点線を AE の方から AF の方へと少しずつ傾けていくと、 EG' の長さはだんだん大きくなり、逆に FH' の長さはだんだん小さくなります。従って、（ EG' の長さ）-（ FH' の長さ）を計算すると、これはだんだん大きくなります（より正確には、点線の傾きを AE の方から AF の方へと連続的に変化させると（ EG' の長さ）-（ FH' の長さ）の値が連続的に増加する）。

もし点線がちょうど AE と重なっていたら EG' の長さは 0 で FH' の長さは 0 より大きいので、（ EG' の長さ）-（ FH' の長さ）は 0 より小さいです。もし点線がちょうど AF と重なっていたら、 EG' の長さは 0 より大きく FH' の長さは 0 なので、（ EG' の長さ）-（ FH' の長さ）は 0 より大きいです。（ EG' の長さ）-（ FH' の長さ）はだんだん大きくなる（連続的に増加する）ということでしたから、どこかで（ EG' の長さ）-（ FH' の長さ）=0 となるはずです（中間値の定理を使っている！）。そのような点線の傾きを見つけて、そのときの G' と H' を正式に G と H とします。このとき G, H の置き方から A は直線 GH 上に乗っています。

G と H の置き方から DG : GE = EH : HF となっています。ここでさらに DG : GE = EH : HF = FI : ID を満たすように I を置きます。

E, I と F, I を直線で結びます。このとき、三角形 ABC が正三角形であることおよび AE:EB = BF:FC = CD: DA であることおよび DG : GE = EH : HF = FI : ID であることから図に描かれた点 A, B, C, D, E, F, G, H, I と直線の配置は 120 度・240 度回転してもぴったり重なるような対称性を持っています。 A が直線 GH 上に乗っていることおよびこの対称性から、 B は直線 HI 上に、 C は直線 IG 上に乗っていることが分かります。

これらのことを踏まえつつ図を見ると、この図の配置が9個の点と9本の直線からなる3-配置になっていることが確認できます。このようにして9個の点と9本の直線からなる3-配置は実際に作ることができます。

余談

9個の点と9本の直線からなる3-配置にはある意味で「本質的に異なる配置」になっているものがここで紹介したものの他に2種類、合計3種類あります*5。この意味でも9には「たくさんの可能性がある」わけですね。

参考文献

文献の詳しい説明は次回の記事に書きます。

[Grünbaum] Branko Grünbaum, Configurations of Points and Lines. Graduate Studies in Mathematics 103. American Mathematical Society, Providence, RI, 2009. ISBN: 978-0-8218-4308-6. URL

[HC] D. ヒルベルト, S. コーン゠フォッセン（著）, 芹沢 正三（訳）, 直観幾何学, 新装版. みすず書房. 2019.（初版は1966年）ISBN: 978-4-622-08828-8. URL

（David Hilbert, Stefan Cohn-Vossen, Anschauliche Geometrie. Grundlehren der mathematischen Wissenschaften 37. Springer-Verlag Berlin, Heidelberg, 1932. ISBN: 978-3-662-35855-9. URL の和訳）

*1:104期 OPENING！Fes×LIVEのアーカイブの46:40〜49:02のやりとりでの発言。引用した発言は47:26〜47:52の部分。

*2: [Grünbaum] p.162 の Theorem 3.2.3 と Theorem 3.2.4。なおこの結果は [Grünbaum] の出版時点（2009年）ではまだ未出版だったJ. BokowskiとL. Scheweによる結果であり、比較的最近の結果です。

*3: [Grünbaum] p.235 に"The smallest 5-configuration discovered so far is the (48_5) configuration, found by L. Berman [...]"、 p.237 に"[...] the result mentioned in the proof of Theorem 3.2.1 to the effect that any topological (n_5) configuration must satisfy n \geq 25."と書かれている。

*4: [Grünbaum] p.237 には"There has been no investigation of 5-configurations---topological or geometric---till very recently, and no systematic approaches have been developed so far."と書かれています。

*5: [Grünbaum] pp.70〜72（特に Figure 2.2.1）および [HC] pp.111〜118。

閉曲面版の「四色定理」

この記事は組合せ論 Advent Calendar 2024 8日目の記事です。

adventar.org

四色定理という定理があります。これはKenneth AppelとWolfgang Hakenによって1976年に示された*1定理で、その主張はグラフの言葉で書けば次の通りです：任意の平面グラフは 4-彩色可能であり、また 3-彩色不可能な平面グラフが存在する。

なお後半の「 3-彩色不可能な平面グラフが存在する」という主張は簡単に具体的な構成ができるので、AppelとHakenが実際に示した非自明な部分は前半の「任意の平面グラフは 4-彩色可能である」という主張です。

定理に出てきた用語の説明をします。（本稿における）平面グラフとは、平面（ \mathbb{R}^2 ）上の有限個の点の集合 V と V の異なる2点を結ぶ線であって自分自身と交わらないもの*2をいくつか集めてできた集合 E の組 (V, E) であって、

  • V のどの異なる2つの要素 v_1, v_2 についても、2点 v_1 と v_2 を結ぶような E の要素は高々1つしかない
  • E のどの要素 e についても、 e は端以外では V の要素を通らない
  • E のどの異なる2つの要素 e_1, e_2 についても、 e_1 と e_2 は端以外では交わらない

ようなもののことです。 V の要素は頂点、 E の要素は辺と呼ばれます。 V の異なる2つの要素 v_1, v_2 について v_1, v_2 を結ぶような E の要素が存在する時、 v_1, v_2 は辺で繋がっているなどと表現します。

平面グラフ (V, E) が n-彩色可能とは、 n 色の色だけを用いて V の要素を次を満たすように塗り分けることができるということです*3： V のどの異なる二つの要素 v_1, v_2 についても、 v_1 と v_2 が辺で繋がっているならば v_1 に塗られた色と v_2 に塗られた色は異なっている。

これらの定義を踏まえてもう一度定理の主張を眺めてみましょう：任意の平面グラフは 4-彩色可能であり、また 3-彩色不可能な平面グラフが存在する。なお 3-彩色可能ならば 4-彩色可能ですから、「任意の平面グラフは 3-彩色可能である」というより強い主張が成り立っている可能性もあります。しかし定理の後半部分で述べられているように 3-彩色不可能な平面グラフは存在するので 4-彩色可能の 4 の部分は最良の値になっています。

さて、平面グラフの構造はグラフの入っている空間である平面の空間構造に制約を受けています（特に、辺同士が交わってはいけないという条件は強い条件です）。そこで、この空間を取り替えるというということも考えてみたくなります。例えば球面はどうでしょうか？上の定義で「平面」と書いているところを「球面」に置き換えることで「球面グラフ」のような概念を定義することができます。「球面グラフ」の彩色可能性はどうなっているでしょうか？

ここで彩色可能性の定義では頂点がどう繋がっているかのみが問題になっていることに注目しましょう。2つのグラフについて、その頂点や辺の配置が違っていても頂点のつながり方がある意味で同じであれば、「彩色可能性」のみを問題にする場合にはそれらのグラフは等価だと思って良いでしょう。そこで、頂点のつながり方がある意味で同じグラフのことを同型なグラフと呼ぶことにしましょう（というかむしろ、このような「つながり方」の情報の方をグラフと呼んで、これまで考えた「平面グラフ」「球面グラフ」なるものはそのような抽象的なグラフを平面や球面上で実現したものだという見方をする方が一般的です）。きちんと定義を書けば、2つのグラフ (V_1, E_1) と (V_2, E_2) が同型であるとは、 V_1 のどの2点 a, b についても、 a, b が (V_1, E_1) において辺で繋がっていることと f(a), f(b) が (V_2, E_2) において辺で繋がっていることが同値になっているような V_1 から V_2 へのある全単射 f が存在することです。この定義のもとで、次のことが成り立つことが知られています：任意の平面グラフに対してそれと同型な球面グラフが存在し、逆に任意の球面グラフに対してそれと同型な平面グラフが存在する。従って、四色定理は次の主張と同値です：任意の球面グラフは 4-彩色可能であり、また 3-彩色不可能な球面グラフが存在する。

球面は閉曲面と呼ばれるものの1つです。閉曲面とはコンパクトな2次元多様体のことです。連結な閉曲面は同相写像による分類が知られており、種数 p （p \geq 0 ）の向き付け可能な閉曲面 S_p と種数が q （ q \geq 1 ）の向き付け不可能な閉曲面 N_q で全ての同相類が尽くされています（球面は S_0 と同相です）。「球面グラフ」と同様に「 S_p グラフ」や「 N_q グラフ」のような概念を定義することができます*4。「 S_p グラフ」や「 N_q グラフ」の彩色可能性はどうなっているでしょうか？

実は S_0 以外の任意の閉曲面 S_p および N_q についても「四色定理」の類似物が証明されています。具体的には次のことが成り立ちます： S_0 と N_2 以外の閉曲面 S について、任意の S グラフは \lfloor\frac{7+\sqrt{49-24e(S)}}{2}\rfloor-彩色可能であり、また \lfloor\frac{7+\sqrt{49-24e(S)}}{2}\rfloor - 1-彩色不可能な S グラフが存在する（ここで \lfloor x \rfloor は n \leq x \lt n+1 を満たす整数 n のこととし、 e(S) は S のオイラー標数、つまり e(S_p) = 2 - 2p, e(N_q) = 2 - q とします）。なお N_2 についてはこの式とは値がズレていて、任意の N_2 グラフは 6-彩色可能であることおよび 5-彩色不可能な N_2 グラフが存在することが分かっています。

この主張はGerhard RingelやJ. W. T. Youngsをはじめとした様々な人の多大な努力による結果の集合体で、最終的な証明は1968年に完了しました*5。四色定理と合わせれば、全ての閉曲面について「四色定理」の類似物が証明されているということになります。

ここで球面以外の閉曲面版の「四色定理」の証明（1968年）が平面・球面に対する四色定理の証明（1976年）よりも早いことに驚くかもしれません（一般の閉曲面の方が平面・球面よりも空間構造はなんとなく複雑なような気がするのに）。結果的に出来上がった証明を眺めると球面の場合とそれ以外とでは困難な部分が異なっていて、これが証明年が前後しているように見える理由のひとつだと思われます。平面・球面グラフの場合には上で述べたように 3-彩色不可能な平面・球面グラフを構成することは簡単で、任意の平面・球面グラフが 4-彩色可能であるという前半部分を示すのが非常に難しいようです（ 5-彩色可能であることまでなら簡単に示せる）。球面と N_2 以外の閉曲面においては逆に任意の S グラフが\lfloor\frac{7+\sqrt{49-24e(S)}}{2}\rfloor-彩色可能であるという前半部分は簡単に示すことができて、\lfloor\frac{7+\sqrt{49-24e(S)}}{2}\rfloor- 1-彩色不可能な S グラフが存在するという後半部分を全ての閉曲面 S について示すという部分が非常に難しいようです*6。なお、定理が示されていない段階では真の値がいくつなのか不明なので、実際にどこが解決に向けての困難になっているのかは当時は不透明だっただろうと想像されます。

球面以外の閉曲面版の「四色定理」の証明はRingelの"Map Color Theorem"という本[Ringel]にまとめられています。頂点が n 個でどの2つの頂点も繋がっているような（閉曲面に実現する前の）グラフは完全グラフと呼ばれ K_n で表されるのですが、定理の証明を「 K_n が実現できるような S_p であって p が最小のもの」および「 K_n が実現できるような N_q であって q が最小のもの」を決定するという問題に帰着することができるので、この問題をひたすら解いていくというのが方針です。このような最小の p および q のことはそれぞれ K_n の向き付け可能種数および向き付け不可能種数と呼ばれています。その決定は n に関する細かい場合分けを伴った議論が必要で、かなり手間がかかっているようです。

さて、この記事は組合せ論 Advent Calendar 2024 8日目の記事である、と冒頭に書きました。 8 といえば……そう、種数 2 の向き付け可能な閉曲面 S_2 です。

種数 2 の向き付け可能な閉曲面 a.k.a. 横たわった 8

\lfloor\frac{7+\sqrt{49-24e(S)}}{2}\rfloor の S に S_2 を代入してみましょう。 e(S_2) = -2 ですから、\lfloor\frac{7+\sqrt{49-24e(S_2)}}{2}\rfloor = \lfloor\frac{7+\sqrt{97}}{2}\rfloor であり、 \frac{7+\sqrt{97}}{2} は \frac{16}{2} = 8 と \frac{17}{2} = 8.5 の間の実数なので、\lfloor\frac{7+\sqrt{49-24e(S_2)}}{2}\rfloor = 8 です。つまり、 8 の形をした閉曲面上に実現できるグラフについて「八色定理」が成り立っています（覚えやすい！）。

参考文献

[Ringel] Gerhard Ringel, Map Color Theorem. Die Grundlehren der mathematischen Wissenschaften 209. Springer-Verlag Berlin, Heidelberg, 1974. ISBN: 978-3-642-65761-0. URL

今回紹介した球面以外の閉曲面版の「四色定理」の証明が載っている本。主に序文・1章・4章・5章を参照しました。

[RSST] Neil Robertson, Daniel Sanders, Paul Seymour, Robin Thomas, The four-colour theorem. J. Comb. Theory, Ser. B 70, No. 1, 2-44 (1997). URL

四色定理の簡略化された証明が載っている論文。Appel, Hakenと方針は同じだがそれよりも楽な証明になっているらしい。

[中小] 中本 敦浩, 小関 健太, 曲面上のグラフ理論. SGCライブラリ 172. サイエンス社, 2021. ISBN: 978-4-7819-1530-2. URL

平面や閉曲面上に実現されるグラフについて書かれている本。3.3節に K_n の向き付け可能種数および向き付け不可能種数の話が、5.3節に閉曲面版の「四色定理」に関する話が載っています。

*1:証明年は[RSST]に基づいた。ただし[RSST]のp.3には"We began by trying to read the A&H proof, but very soon gave this up."と書かれており、本当にこの証明が合っているのかには疑問が残っているかもしれない。[RSST]にはAppel, Hakenと同じ方針だが簡略化された証明が書かれている。

*2:[0, 1] から \mathbb{R}^2 への連続単射 f であって f(0), f(1) が V の異なる2つの要素であるようなもののこと。

*3:ここで頂点に n 色の色を用いて塗るという行為は数学的には V から \{1, 2, ..., n\} への写像 c を与えるということだと思っても良い。

*4:この呼び方は本稿のみでの呼び方。

*5:証明年は[Ringel]に基づいた。[Ringel]の序文と1章にはどのように証明が進んでいったかが書かれている。

*6: N_2 については個別の議論が必要だが、そこまで長い証明ではない。