空間を塗り分けるには何色必要か？典型的な「ものさし」なら2d色で足りる
平らな平面上のすべての点に、それぞれ色をつけるとしよう。ルールは一つ。ちょうど1単位離れた2点は、決して同じ色にしてはならない。うまくいく最小の色数はいくつだろうか。
これがハドウィガー・ネルソン問題である。1950年にさかのぼり、著者らの言葉を借りれば、離散幾何学で最も有名な未解決問題の一つだ。長いあいだ、答えは4から7の間にあることが知られていた。最近のブレークスルーによって下限は5に引き上げられた。厳密な答えは今もわかっていない。
ものさしを変える
距離は普通のものさしで測る必要はない。数学者は長さを測るさまざまな方法、すなわちノルムを定義している。それぞれのノルムは「単位球」、つまり中心からの距離が1以下の点の集合によって表される。通常の距離では丸い球だが、ほかのノルムでは、中心について対称な任意の凸形状になりうる。
平面上のどのノルムについても、この塗り分けパズルの答えは4から7の間にある。d次元では、どのノルムでも答えは高々dの指数関数程度だ。そして、通常のユークリッド距離を含む多くの自然なノルムでは、少なくとも指数関数的でもある。つまり、次元が上がるにつれて色の数が爆発的に増える。
この爆発は一般的な法則なのだろうか。ノガ・アロン(Noga Alon、プリンストン大学およびテルアビブ大学)、マティヤ・ブツィッチ(Matija Bucić、ウィーン大学)、ジェームズ・デイヴィス(James Davies、ライプツィヒ大学)は、典型的なノルムに目を向けた。ノルムを「ランダムに」選ぶ自然な方法はないので、彼らは位相的な概念を使う。例外が無視できる集合(「やせた集合」、meagre set)をなすとき、その性質は典型的なノルムで成り立つという。アロン、ブツィッチ、リサ・ザウアーマン(Lisa Sauermann)による以前の研究は、典型的なノルムでは高々2ᵈ色で足りることを示し、それが真の値にどれほど近いのかを問うていた。
指数関数ではなく線形
答えは、まったく近くない、というものだった。新しい論文は次のことを証明している。
- d次元空間の典型的なノルムでは、2d色で常に足りる。
- これは最良である。あるノルムの開集合では少なくとも2d色が必要となる。したがって、ちょうど2d色を必要とするノルムがある。
10次元では、典型的なノルムは高々20色で済むが、通常の距離では指数関数的に増える数の色が必要になる。著者らによれば、任意の次元dにおいて「狭義凸」なノルムについて塗り分け数が厳密に決定されたのも、これが初めてだという。
下限の証明には巧妙な罠が使われる。2d個の点で、互いにちょうど1単位ずつ離れているが、2点aとbだけは0.5単位離れている、という配置を見つける。そこに、配置全体をaについて点対称に写した像を加える。色が2d未満だと、bとその鏡像はどちらもaと同じ色にならざるをえない。しかしこの2点はちょうど1単位離れている。矛盾だ。安定性に関する補題により、この配置はノルムを少し変えても生き残ることが示される。
高次元の「孤独なランナー」
上限の証明では、各点をうまく選んだ射影がどこに落ちるかに応じて、幅1/(2d)の帯ごとに色を塗る。これを成り立たせるには、著者らが有名な孤独なランナー予想(lonely runner conjecture)の高次元・行列版と呼ぶ重要な要素が必要になる。
sup over x of minᵢ ‖aᵢ · x − bᵢ‖ ≥ k / (2n)
ここで‖t‖はtから最も近い整数までの距離であり、k次元のn本のベクトルaᵢのうち任意のk本が線形独立であるとする。この主張は、「視線の遮蔽」(view obstruction)に関するI・J・シェーンバーグ(I. J. Schoenberg)の1978年の予想も解決する。これは、無限遠へのあらゆる視線を遮るには周期的に並んだ板がどれほど厚くなければならないかを問うもので、著者らはこの分野で最も古典的な未解決問題の一つと呼んでいる。あわせて、ヘンツェ(Henze)とマリキオシス(Malikiosis)による関連する予想も解決する。
謝辞に登場する機械
著者らははっきりと書いている。「ChatGPT 6 Proは、長い議論の末に、定理1の証明に必要だった最後の要素、すなわち補題7の証明を私たちに提供した」。その議論の中で、彼らは帰納法のアイデアや全体の戦略を含む自分たちの観察を共有していた。「下限の議論もChatGPT 6 Proの助けを借りて見つけられた」。
疑問は残っている。厳密な値2dが証明されたのはノルムのある開集合においてであり、すべての典型的なノルムについてではない。また通常のユークリッド距離については、著者らはあらゆる次元で2dより真に多い色が必要だと予想している。これは2、4、7、8次元および9次元以上ではすでに知られているが、3、5、6次元ではまだ未解決だ。