- 高次元の球充填問題で、Boaz Klartagが1947年のClaude Ambrose Rogers以来最大級の効率改善を含む短い草稿を4月にオンライン公開した
- 新しい方法は任意の格子から出発してより大きな楕円体を作り、その後Rogersの手順で高密度の球充填を構成するもので、しばらく脇に追いやられていた幾何学的アプローチを復活させた
- Klartagの構成では、次元 d において既存の多くの結果より約 d 倍多くの球を充填でき、100次元では約100倍、100万次元では約100万倍に相当する
- 2023年の非格子的な記録以後に強まっていた無秩序な充填の可能性をめぐる議論とは対照的に、今回の結果は高次元の最適充填で秩序と対称性が依然として有力でありうることを示している
- 暗号学や通信への応用において球充填問題は重要だが、今回の結果がただちに応用されるわけではなく、凸幾何学と格子理論を再び結びつける契機になりうる
高次元球充填における大きな前進
- 球充填問題とは、球を高次元空間の中にできるだけ効率よく詰める方法を見つける問題である
- この問題は何世紀にもわたり数学者を惹きつけてきており、暗号学や長距離通信にも重要な応用可能性がある
- 17世紀初頭、Johannes Keplerは3次元の球を食料品店のオレンジのように積み上げると空間の約**74%**を満たせることを示し、それが最適だと予想した
- この予想が証明されたのは、ほぼ400年後のことだった
- より高い次元では、8次元と24次元を除いて最適解はまだ分かっていない
- 数学者たちは長年にわたりより良い充填を探してきたが、改善は小さくまれだった
- Boaz Klartagは4月に公開した短い草稿で従来記録を大きく上回り、一部の研究者はこの結果が最適に近い可能性があると見ている
格子から楕円体へとつながる古いアイデア
- 1905年、Hermann Minkowskiは**格子(lattice)**によって球充填を考える方法を打ち立てた
- 空間に繰り返し現れる点配置を作り、各点のまわりに球を描く方法である
- 特定の次元で最適な球充填を見つける問題は、点が最も効率よく配置された格子を見つける問題に置き換わる
- 2次元では六角格子が最適である
- 1947年、Claude Ambrose Rogersは別の視点を提示した
- 最適ではない任意の格子からでも出発できる
- 各点に球を描く代わりに、ある点のまわりに楕円体を描き、その表面が格子の別の点に触れても越えないようにする
- この楕円体を出発点として高密度の球充填を作るアルゴリズムを示した
- Rogersの方法の利点は、出発格子が特別に効率的である必要がない点にある
- 適切な楕円体さえ選べば、効率的な球充填を作ることができる
- しかし楕円体は球より扱いが難しい
- 球は半径ひとつで定まるが、楕円体は長さの異なる複数の軸で定まる
- 次元が高くなるほど、伸ばせる方向と取りうる形状は急激に増える
- 数学者たちは結局Minkowski流の格子アプローチへ戻り、格子理論により集中するようになって、Rogersの幾何学的アプローチからは離れていった
- この戦略でも高次元球充填は改善されたが、その多くはRogersの充填より小幅な改善にとどまった
凸幾何学の研究者が復活させたRogersのアプローチ
- KlartagはWeizmann Institute of Scienceの数学者で、主に**凸幾何学(convex geometry)**を研究している
- 凸図形とは、内側にへこんだ部分を持たない図形のことである
- 高次元ではさまざまな対称性を含み、Klartagはこうした図形を強力な数学的道具とみなしている
- 彼は格子と球充填に関心を持っていたが、その分野を深く学ぶ時間はなかった
- 昨年11月に主要プロジェクトを終えた後、予定が空いた彼は、Tel Aviv UniversityのBarak Weissに新しい分野を学ぶためのメンタリングを依頼した
- WeissはKlartagと数人が一緒に文献を読む小さなセミナーを始めた
- KlartagはMinkowskiとRogersの球充填法を詳しく読んだ
- Rogersが楕円体を球充填へ変換する方法を読んだ後、Klartagは数学者たちがなぜその方法を放棄したのか疑問に思った
- 楕円体は凸図形なので、Klartagにはそれを操作する洗練された方法があった
- Rogersが用いた出発楕円体は直感的ではあるが非効率だと判断した
- もしより大きな体積の楕円体を作れれば、Rogers本来の手順によって新たな充填記録を打ち立てられるはずだった
ランダムな成長でより大きな楕円体を作る
- Klartagは、各軸に沿って楕円体の境界をランダムな過程で伸ばしたり縮めたりする、自身になじみのある方法から出発した
- 境界が十分に拡張されて格子の新しい点に触れると、その方向での成長を止める
- その点が楕円体の内部に入らないようにするためである
- 他の方向では、別の点に触れるまで膨らみ続ける
- この過程で楕円体は、ぎくしゃくと止まり動きながら周囲の空間を徐々に探索していく
- 時間がたつと、平均的には楕円体の体積は増加する
- Klartagの中心的な問いは、この体積増加がRogersの直感的な楕円体を上回るのに十分かどうかだった
- ランダム過程は実行のたびに異なる楕円体を生み出すため、Klartagは取りうる楕円体体積の範囲を評価した
- 当初は、Rogersの楕円体より十分に大きい単一の楕円体を見つけられなかった
- ランダム成長過程の細部を調整した後、1〜2週間で、ときには新記録を打ち立てるほど大きな楕円体が現れることを証明した
約d倍の改善が持つ数学的意味
- Klartagの証明は検証されており、新しい出発楕円体を球充填に変換すると、Rogersの1947年の論文以来最大級の効率改善をもたらす
- 与えられた次元 d において、Klartagの方法は既存の多くの結果より約 d 倍多くの球を充填できる
- 100次元空間ではおよそ100倍多くの球を充填できる
- 100万次元空間ではおよそ100万倍多くの球を充填できる
- Klartagは球充填分野を数か月学び、証明を数週間で書き上げたうえで、中心的問題のひとつを大きく前進させた
- 彼の凸幾何学の経験は、ふつうは別分野として扱われる手法を球充填問題に適用するうえで直接役立った
- Gil Kalaiはこの結果を「本当に驚くべきブレークスルー」と評価し、数学者たちをほぼ100年にわたって興奮させてきた問題に関わる成果だとみている
秩序と無秩序をめぐる論争
- Klartagの結果は、高次元の最適充填の性質をめぐる論争を再燃させた
- しばらくの間、数学者たちは高い対称性を持つ格子ベースの充填が球を最も高密度に並べる最善の方法だと考えていた
- 2023年には、繰り返し格子にきれいに依存しない充填が発見され、Klartag以前の記録となった
- 一部の数学者はこれを、最適球充填の探索にはより多くの無秩序が必要だという証拠とみなした
- Klartagの研究は、再び秩序と対称性が有力でありうるという考えを後押ししている
- 球充填がどれほど高密度になりうるかは、なお議論の最中にある
- 一部の数学者はKlartagの充填が最適に非常に近いとみている
- 別の数学者たちは、なお改善の余地があるとみている
- University of Illinois, ChicagoのMarcus Michelenは、現時点で何を信じるべきか分からず、あらゆる可能性が開かれていると述べている
すぐの応用より大きな分野横断のつながり
- 球充填問題の答えは、暗号学と通信への応用可能性があるため重要である
- Hebrew Universityの情報理論研究者Or Ordentlichは、この問題はエンジニアにとって大きい一方で進展が少なかったため、今回の結果は興奮を呼ぶと述べている
- ただし、Klartagの結果がそうした応用にすぐ役立つわけではない
- Klartagは、自身の研究が、Rogersの時代のように凸幾何学と格子理論がより強く結びついていたやり方へ戻るきっかけになることを望んでいる
- 彼は、凸体に関する現在の理解が球充填を超えて格子問題にも役立つ可能性があるとみている
- Klartagの目標は、二つの分野が今より分断されないようにすることである
1件のコメント
Hacker Newsのコメント
両親に自分の仕事が本物の職業だと説明するだけでも難しいのに、「はみ出して内側に入り込んだ部分のない図形だけを研究している」と説明するのは、想像するだけでさらに難しい
選択肢は実質3つしかない。相手が理解できる言葉で短く説明すると、仕事が簡単そうに見えて「これでどうやってお金をもらうんだ？」と思われる
相手が理解できる言葉で、何をしていてなぜ重要なのかを説明すると、長くなりすぎて退屈になり、聞いたことを後悔される
あるいは、相手が知らない専門用語で短く説明して、退屈だけれど感心させることもできる。悪い選択肢の中ではこれが最善
自分の事業が何なのか、一般の人にも少しは理解してもらえる説明の仕方をまだ見つけられていない。どれもあまりに難解で、日常生活から何段階も離れている
必ずしも複雑というより、平均的な人が慣れ親しんだことのない細部が多すぎて、日常的なたとえもほとんどない
凸図形のほうはよくわからない
細かすぎるように見える話し方には、人を遠ざける毒性が生まれることがある
「XYZをやろうとしているけれど難しすぎて苛立たしい。そこで簡単な推測をしてみる。この問題をこんなふうに粗く考えるのは扱いやすいからで、ABCを知っているのでABCを作る。そしてそれを使うと、これまで試したものよりうまくいくところに近づいてワクワクする」といった観点で説明すればいい
非技術者には、感情のこもった説明でも十分伝わる。彼らは感情的に考えることにより慣れているかもしれず、私たちは仕事の論理や、ときには数学に深く浸っている。だから説明に感情を戻す必要がある
家族にそう説明したら、ついてきて実際に理解してくれた
記事では「100次元空間では彼の方法が、およそ100倍多くの球を詰め込み、100万次元空間ではおよそ100万倍多く詰め込む」とあったが、高次元空間がどれほど奇妙かを示すよい例だと思う
頭のいい人たちが100次元の箱に100次元のオレンジをできるだけ多く入れようとしたとき、これまでは空間の1%も埋められず、何十年探してももう1個入れる場所を見つけられなかった、という意味に見える
単位超立方体に囲まれた単位 n-球を考えると、n が大きくなるほど球の占める割合は消えていく。付け加えると、奇妙なことにこの関係は単調ではなく、n=6 で最大になる
n=100 では単位100-球の体積はおよそ 10^-40 で、この超立方体の中に2つ目の球を入れられないのは当然だ。だから充填の改善で得られる利得がそれほど大きくなり得ること自体は驚きではない
4次元を可視化できると言う人は多いが、実際にできる人はまだ見たことがない。数学者も多く含まれるが、そう主張するのはたいてい数学者ではない
この Math Overflow の投稿にあるアニメーション[0]が好きなのだが、それはほとんどの人が考えない隠れた複雑さが多いからだ。そのアニメーションは実は錯視であり、私たちは「幻覚」を見ている。上の図が立方体を平面に射影している？ 実はそれは立方体ではない。すでに立方体を2次元に射影したものだ。技術的には3次元だが、3つ目の次元は空間次元ではなく時間次元だ。これ自体が次元の抽象化を学ぶうえでよい教訓になる
だから私たちは回転する立方体を幻覚し、平面上の射影を見たうえで、それを歪んでいない正方形ではなく奥行きのあるものとしてさらに幻覚する。これだけでもかなり奇妙だ
実は私たちは2次元の想像も苦手だ。ほとんどの人は2次元を可視化できると主張し、その主張はたいてい反論されない
Flatland[1]を読んだことがないなら、誰にでも勧めたい。多くの人が誤読している。普通は1次元下げた比喩として読み、3次元存在である私たちが2次元存在に対応し、4次元存在は、Flatlander にとって3次元存在が戸惑わせるのと同じくらい私たちを戸惑わせるのだ、と理解する。それは正しいが、そこには罠がある。私たちは2次元の理解はとても簡単だと思っている。だが今頭の中に描いているものは間違っていると断言する。正直、本も完全に正確ではない
本当に Flatlander の立場になってみる必要がある。本の中ではなく、実際の Flatlander の立場だ。正方形の Flatlander になって三角形を見ると想像したら、何が見えるだろうか。おそらく線を思い浮かべるだろうが、それは間違いだ。厚みを与えており、3つ目の次元を入れてしまっている。もう一度やってみて、さらに奥行きを加えながら実際の Flatland を想像しようと自分に課してみれば、できないことが分かる
代わりに私たちは、3次元の中に埋め込まれた2次元空間を可視化し、推論できる。揚げ足取りだと言われるかもしれないが、そうでないなら、これ[2,3]を4次元超立方体の表現ではなく4次元超立方体そのものだと言っても、まったく問題ないはずだ
これを理解すると、非常に高い次元を理解するうえで大きな助けになると思う。次元を1つ増やしたり減らしたりしたものを正確に可視化することの途方もない難しさに向き合えば、はるかに高い次元を推論するときに自分を欺く可能性が減る
Feynman が言ったように、第一原理は自分を欺かないことであり、最も欺きやすい相手はまさに自分自身だ
[0] https://math.stackexchange.com/a/2286226
[1] http://www.geom.uiuc.edu/~banchoff/Flatland/
[2] [https://en.wikipedia.org/wiki/Tesseract#/media/File:8-cell-s...](https://en.wikipedia.org/wiki/Tesseract#/media/File:8-cell-simple.gif)
[3] Carl Sagan が超立方体の3次元射影、つまり影を手に持って説明するよい動画だ。何を見せようとしても、2次元の中に埋め込まれるしかない。6:20 から持ち上げる https://www.youtube.com/watch?v=UnURElCzGc0
興味深い。より良い圧縮アルゴリズムを作ろうとして、1か月ほど球充填のアプローチを使ってみた
ベクトルが大量にあり、それらはクラスタリングでまとめられていたのだが、理論的なアプローチは一様なデータでしかうまく機能せず、現実世界のデータにはあまり合わないという結論になった
たとえばデータに高次構造があるが、局所的には一様だとしよう。これはよくあることで、ノイズを生む過程によって生じる。中心点を計算して保存すれば、元データより一様で、数も多くないので、いずれにせよ大きな問題にはならない
各ベクトルは中心点インデックスとベクトルのオフセットとして保存する。このとき AoS ではなく SoA だ。インデックスは好みのエントロピー系の整数方式で圧縮でき、順序を保持する必要がなければさらにうまくできるかもしれない
オフセットは仮定上、今やおおむね一様なので、文献にある好みの球戦略を使える
もちろん、実際のユースケースがあまりに異質で、一般的な手法が有効でないなら別だが
数学者は、最初の博士号取得から数年後に、自分の分野と同じではないものの隣接分野で2つ目の博士レベルの学位を取れるべきだと感じる
多くの研究者はポスドク期やその後に、隣接分野へ再訓練したり研究上の関心を追加したりする。その時点からは、単に研究である
ただし現代の学界環境でそれをやろうとすると、簡単ではないだろう
特に数学の異なる分野を結びつけることは、非常に強力になり得る
少なくともドイツでは、かなり説明されたものに近い
与えられた次元 d について、Klartag は従来の大半の結果より d 倍多くの球を詰められるという
つまり100次元ではおよそ100倍、100万次元ではおよそ100万倍多くの球を詰めるということで、数字としては途方もなく聞こえる。さまざまな通信システムで、帯域幅が数桁増えたり消費電力が減ったりするという意味なのだろうか？
したがって、自然に高次元である対象にしか役立たない。デジタルな対象には自然な次元、つまりバイト長がないので、小さい次元を選べる
https://en.m.wikipedia.org/wiki/Sphere_packing
Klartag は訓練上の背景としては球充填の専門家ではないが、彼は周辺で指折りの問題解決者の一人である
今年初めには Hyperplane Conjecture を解決し、KLS Conjecture、Mahler Conjecture、凸体に関する中心極限定理のような凸性理論関連の問題の進展に貢献してきた
彼の学生 Eldan による Stochastic Localization の研究も、対数凹サンプリングアルゴリズムで核心的であることが証明されており、これは KLS Conjecture と関連し、ICM でも講演された
また凸幾何で使う道具、特に一部の調和解析の道具は、球充填の研究にもかなり有用である
だから「予想外」とは言いにくい
Klartag が凸図形は過小評価された数学的道具だと見ていることに同意する。数学者ではないが、凸包アルゴリズムがまったく予想しないところで問題を解くのを見たことがある
例えば画像の自動パレット分解の論文のようなところで凸包アルゴリズムを使うとは、思いもしなかっただろう
https://www.rose-hulman.edu/class/cs/csse451/Papers/DILvGRB....
初歩的な質問だが、最適な球充填は正則格子と相関があるのだろうか？ 2次元と3次元ではそうではないのか？ だとすれば n 次元にも拡張されるのだろうか？
これは2017年に Maryna Viazovska が証明し、2本目の論文には共同研究者たちも加わった。 https://doi.org/10.4007/annals.2017.185.3.7 https://doi.org/10.4007/annals.2017.185.3.8
これも参考になる: https://www.ams.org/journals/notices/201702/rnoti-p102.pdf
他の次元では未解決問題であり、一般に真である可能性は低そうだ。ある次元では、知られている最も密な非正則充填が、知られている最も密な正則充填よりも高密度である
ただし、すべて FCC 格子と同じ密度を持つ。こうした充填は、FCC の水平層を互いに対して水平方向にずらすことで作れる
高次元では、最も密な充填は常に非格子であるという予想がある。そのような空間には十分な対称性がないという理由からである
今日これに先立って、ネアンデルタール人が脂肪をレンダリングしていたという投稿があった
人類学者たちは、土器の発明以前にも煮沸が可能だったことを知らなかった、という話が出ていて、科学教師たちは授業で実演することがあるので、その可能性を知っていたという話もあった
最後には、ブドウ糖を研究していた人が積分の台形公式を再発見したように、異なる分野で同じものが再発見されることがある、という流れだった
これも、別領域の専門知識が役に立つもう一つの例だ
サバイバル状況で使う方法を見せているYouTube動画を一つ見るだけで十分だ。似たものはたくさんあるはず: https://www.youtube.com/shorts/0zun_UxO2vU
文脈を知らないのは確かだが、そんな驚くべき主張に出典がないなら筋が通らない。「笑いのテスト」にも通らない