すべての点をすべての点と結ぶ：最少の交差数、ついに証明

紙に5個の点を置き、すべての組を曲線で結んでみよう。曲線は全部で10本になる。曲線は好きなように曲げてよいが、3つ目の点を通り抜けてはいけない。交差をすべて避けようとしても、うまくいかないはずだ。点が5個なら少なくとも1個、6個なら少なくとも3個、10個なら少なくとも60個の交差が避けられない。

数学者はこうした図を完全グラフKₙ（n個の点があり、どの2点も結ばれているもの）の描画と呼び、どの描画でも到達できる最少の交差数を、その交差数と呼ぶ。チェコのカレル大学のMartin Balkoは、この問題を「位相的グラフ理論で最も有名な問題の一つ」と呼んでいる。

芸術家が数えた交差

1950年代後半、英国の芸術家アンソニー・ヒルは、ちょうど

Z(n) = ¼ ⌊n/2⌋ ⌊(n − 1)/2⌋ ⌊(n − 2)/2⌋ ⌊(n − 3)/2⌋

個の交差をもつKₙの描画を構成した。ここで⌊ ⌋は切り捨てを表す。これより少ない交差の描画は存在しないという予想は、最初にガイによって発表され、のちにハラリーとヒルによって論じられ、エルデシュとガイによって広く知られるようになった。これはハラリー–ヒル予想、あるいはガイの予想として知られている。

この公式の値は急速に大きくなる。

点が4個以下：交差0個
点が5個：1個
点が7個：9個
点が10個：60個
点が14個：315個

部分的な答えが続いた60年

ちょうどZ(n)個の交差をもつ描画は、点がいくつの場合にも存在していた。難しいのは、それより少ない交差の描画が一つもないことを示す部分だった。

60年以上にわたって、それが証明されていたのは特別な種類の描画だけだった。たとえば、すべての点が1本の直線上にあり、各曲線がその直線の片側にとどまる場合や、点が球面上にあり、各曲線が最短経路をとる場合などである。Balko自身も、FulekやKynčlとともに、そうしたクラスの一つを解決していた。2021年までに、コンピューターによって点が14個までは公式が確認された。点の数がきわめて大きい場合について、一般的な結果のうち最良のものが保証していたのは、Z(n)の少なくとも98.5%、その後**98.99%**だった。

証明、そしてより明快な証明

2026年、OpenAIは点がいくつであっても成り立つ証明を発表した。Balkoの論文はそれを「OpenAI Math Release preprint」として挙げ、この定理の功績をそれに帰している。その証明がどのようにして見つかったのかについて、論文は何も述べていない。Balkoの言葉によれば、元の証明は「比較的短い」が、「たどるのがかなり難しい」。彼のプレプリントは、整理された別版を示しており、それは「線形代数とグラフ理論の初歩的な知識しか必要としない」と彼は書いている。別の数学者Gelasio Salazarも、独立した詳しい解説を準備している。

交差の代わりに係数を数える

既知の描画がすでにZ(n)に到達しているので、証明が必要なのは下界だけだ。それには4つの手順を踏む。

奇数の場合だけで十分。 最良の描画は、点を共有する曲線どうしが決して交差しないように描き直せる。そうすると、どの交差にも4個の異なる点が関わることになる。6個の点を1つずつ順に取り除いてみよう。残った5点の図にはどれも少なくとも1個の交差があり、各交差は6通りの削除のうちちょうど2通りで生き残る（その交差に関わる4点のどれかが削除されれば消え、残りの2通りでは生き残る）。したがって、交差の数の2倍は少なくとも6であり、交差は少なくとも3個、つまりZ(6)個ある。同じ数え方が、すべての偶数について成り立つ。
多項式の族。 それぞれの点に固有の数を割り当てる。1つの交差には2本の曲線、つまり4個の点、したがって4つの数が関わる。Balkoは4変数の多項式を使い、nが奇数のとき、その族がちょうど**Z(n)**個の独立な係数をもつように選ぶ。点が7個なら、3 × 3 = 9個である。
交差が少なすぎると余地が残る。 ある交差で多項式が0になることを要求するのは、1つの方程式にあたる。方程式の数が自由な係数の数より少なければ、線形代数により、0でない解が必ず残る。したがって、交差がZ(n)個より少ない描画があれば、そのすべての交差で0になる、0でない多項式が伴うことになる。そのうち次数が最も低いものをとる。
平面が押し返す。 幾何学は、ある古典的な事実を通じて入ってくる。平面上の閉じたループは、別のループを右から左へ横切るのとちょうど同じ回数だけ、左から右へ横切る。重みをうまく選ぶと、ここから多項式の値の二乗の和が得られる。その一部は正に、一部は負に数えられ、合計は0になる。正の項はすべて交差の位置にあり、そこでは多項式が0なので、負の項も0にならなければならない。ループについての事実をもう一度使うと、その多項式はある決まった因子で割り切れることがわかる。割ると、同じ性質をもつ、より次数の低い0でない多項式が得られる。だが次数が最も低いものをとったのだから、これはありえない。

この符号の議論が、Balkoによる主な変更点だ。それは、元の証明にあった「非退化な双線形形式と直交補空間を用いる」議論に取って代わっている。彼はまた、ループについての事実を別の方法で証明し、各点をより直接的に切り離している。

一挙に解決したほかのネットワーク

点を共有する曲線どうしがほかの場所で決して出会わない限り、交差の数の代わりに、少しでも交差する曲線の組の数や、奇数回交差する曲線の組の数を数えても、答えはZ(n)のままである。以前に得られていた帰着と組み合わせると、この定理からはさらに、いくつかの辺を取り除いた完全グラフ、完全グラフのコピーを道に沿って、あるいは偶数長の閉路に沿ってつないだもの、そして拡張シェルピンスキーグラフと呼ばれるフラクタルに似たネットワークの族について、正確な交差数が得られる。

6個の点からなる完全グラフから曲線を1本だけ取り除くと、最少の交差数は3から2に下がる。8個の点なら、18から15に下がる。