ケラーの予想

超立方体によるタイリングに関する幾何学問題

幾何学において、ケラー予想とは、 $n$ 次元ユークリッド空間を同一の超立方体で敷き詰める場合、必ず $($ $n$ $-1)$ 次元面全体を共有する2つの超立方体が存在するという予想である。例えば、平面を同一の正方形で敷き詰める場合、図に示すように、2つの正方形は必ず辺全体を共有する。

この予想はオット＝ハインリヒ・ケラー（1930）によって提唱され、彼の名にちなんで命名されました。ラガリアスとショア（1992）による画期的な発見により、この予想は10次元以上では偽であることが示され、その後の改良を経て、現在では7次元以下の空間では真、それ以上の次元では偽であることが分かっています。これらの結果の証明は、現在ケラーグラフとして知られる特定のグラフのクリーク数を用いて問題を再構成したものです。

関連するミンコフスキー格子立方体タイリング予想は、同一の立方体による空間のタイリングにおいて、立方体の中心が格子を形成するという追加の特性を持つ場合、いくつかの立方体は必ず面と面が合うというものである。これは1942年にジェルジ・ハヨシュによって証明された。

Szabó (1993)、Shor (2004)、Zong (2005) は、ケラーの予想と関連する問題に関する研究の概要を示しています。

声明

ユークリッド空間のタイル張り、あるいはタイリングは、直感的には、空間全体を重なり合うことなく覆う部分集合の族です。より正式には、タイルと呼ばれる閉集合の族は、それらの和が空間全体であり、族内の2つの異なる集合がすべて互いに素な内部構造を持つ場合、タイリングを形成します。すべてのタイルが同じ形状（互いに合同）である場合、タイリングは単面体であると言われます。ケラー予想は、すべてのタイルが空間と同じ次元の超立方体である単面体タイリングに関するものです。Szabó (1986) が問題を定式化しているように、立方体タイリングは合同な超立方体によるタイリングであり、タイルはすべて回転なしで互いに並進移動すること、または同等に、すべての辺が空間の座標軸と平行であることがさらに要求されます合同な立方体によるすべてのタイリングがこの性質を持つわけではない。例えば、三次元空間は、互いに任意の角度でねじれた二次元立方体シートによってタイリングされることがある。ショア（2004）は、同じ問題を定式化するにあたり、合同な超立方体による空間のタイリングをすべて考察し、立方体が軸平行であるという仮定は一般性を損なうことなく追加できると、証明なしに述べている。

n $次元超立方体は、$ $n$ $- 1$ 次元の $2 n$ 面を持ち、それら自体も超立方体である。例えば、正方形は4辺を持ち、3次元立方体は6つの正方形面を持つ。立方体タイリング（上記のいずれかの方法で定義）において、2つのタイルが面と面を接する場合、それらのタイルの両方の面となる( $n$ $- 1$ )次元超立方体が存在する。ケラー予想とは、すべての立方体タイリングには、このように面と面を接するタイルのペアが少なくとも1組存在するというものである。^[1]

ケラーが提唱したこの予想の元のバージョンは、より強い主張をしていた。すなわち、すべての立方体のタイル張りには、面と面が交わる立方体の列が存在する、というものである。この問題のバージョンは、より一般的に研究されている定式化と同じ次元において真か偽かを判定する。^[2] この予想において、タイル張りの立方体がすべて互いに合同であることは必須である。なぜなら、異なるサイズの立方体を許容するならば、ピタゴラスのタイル張りは2次元において反例となるからである。

前述の予想は、タイル張りにおける全ての立方体が他の立方体と面を合わせて接することを必要としない。平面上の合同な正方形によるタイル張りは、全ての正方形が他の正方形と辺を合わせて接するというより強い性質を持つが、高次元の超立方体タイル張りにおいては、一部のタイルが他のタイルと面を合わせて接しない可能性がある。例えば、三次元においては、直角柱を3組垂直に並べたテトラスティックス構造を用いて、ウィア・フェラン構造と組み合わせ的に等価な立方体タイル張りを構築することができる。この構造では、立方体の4分の1（どの柱にも属さないもの）が他の12個の立方体に囲まれているが、どの立方体も面を合わせて接していない。^[3]

群論的再定式化

ケラー予想は、ペロン（1940a, 1940b）によって、最大6次元まで真であることが示されました。十分に高い次元におけるケラー予想の反証は、一連の還元を経て進展し、タイル張りの幾何学の問題から群論の問題へ、そしてそこからグラフ理論の問題へと変化しました。^[1]

Hajós (1949) は、ケラーの予想をアーベル群の因数分解という観点から初めて再定式化しました。彼は、予想の反例がある場合、それは整数の辺の長さと整数の頂点位置を持つ立方体の周期的なタイリングであると想定できることを示し、したがって、予想を研究するには、この特別な形式のタイリングを検討すれば十分であることを示しています。この場合、タイリングを保存する変換を法とした整数変換のグループはアーベル群を形成し、このグループの特定の要素はタイルの位置に対応します。Hajós は、アーベル群の部分集合の族 $A i$ が因数分解であると定義し、グループの各要素は、各 $a$ $i$ $がA$ $i$ に属している、和 $a 0 + a 1 + ...$ として一意に表現されます。この定義により、ハヨスが再定式化した予想は、アーベル群の因数分解において、最初の集合 $A$ $0 は$ 任意であるが、後続の集合 $A$ $i$ $はそれぞれA$ iの何らかの元 $g$ $i$ $に対して{0,$ $g$ $i$ $, 2$ $g$ $i$ $,$ $3$ $g$ $i$ $, ..., (|$ $A$ $i$ $| - 1)$ $g$ $i$ $} という$ 特別な形式をとる場合、少なくとも 1 つの元 $|$ $A$ $i$ $|$ $g$ $i は$ $A$ $0$ $-$ $A$ $0$ ( $A$ $0$ とそれ自身の差集合)に属さなければならない、というものである。 ^[1]

サボー (1986) は、この予想の反例となる任意のタイリングは、さらに特殊な形をとると仮定できることを示した。すなわち、立方体の辺の長さが2のべき乗で、頂点座標が整数であり、タイリングは各座標方向において立方体の辺の長さの2倍の周期で周期的である。この幾何学的簡略化に基づいて、サボーはハヨスの群論的定式化も簡略化し、 $q$ $i$ $= 2$ となる位数4の巡回群の直和であるアーベル群を考慮すれば十分であることを示した。

ケラーグラフ

Corrádi & Szabó (1990) は、Szabó の結果を、のちにKeller グラフとして知られるようになった、あるグラフ族における大きなクリークの存在に関する条件として再定式化しました。より正確には、 $n$ 次元の Keller グラフの頂点は4 $n$ $個の$ 要素 $($ $m$ $1$ $、...、$ $m$ $n$ $)$ で、各 $m$ は 0、1、2、または 3 です。2 つの頂点は、少なくとも 2 つの座標が異なり、少なくとも 1 つの座標がちょうど 2 だけ異なる場合に、辺で結ばれます。Corrádi と Szabó は、このグラフの最大クリークのサイズは最大でも $2$ $n$ であり、このサイズのクリークが存在する場合、Keller の予想は誤りであることを示しました。このようなクリークが与えられた場合、その中心の座標が 4 を法としてとったときにクリークの頂点となるような、辺が 2 の立方体で空間を覆うことができます。クリークの任意の2つの頂点の座標が2ずつ異なるという条件は、これらの頂点に対応する立方体が重なり合わないことを意味する。頂点の座標が2ずつ異なるという条件は、これらの立方体が面と面を合わせることができないことを意味する。クリークの大きさが2nであるという条件は $、$ $タイル$ 張りの任意の周期内の立方体の総体積がその周期自体と同じであることを意味する。これらの立方体が重なり合わないという事実と合わせて、このように配置された立方体は面と面を合わせることなく空間をタイル張りすることを意味する。^[4]

ラガリアスとショア (1992) は、 10次元のケラーグラフにおいてサイズ 2 ^10のクリークを発見することで、ケラー予想を反証した。このクリークは10次元において非対面タイリングにつながり、そのコピーを（各座標方向に半単位ずつずらして）積み重ねることで、任意の高次元において非対面タイリングを生成できる。同様に、マッキー (2002) は8次元のケラーグラフにおいてサイズ 2 ⁸のクリークを発見し、同様に8次元において非対面タイリングにつながり、さらに積み重ねることで9次元においても非対面タイリングにつながった。

その後、Debroni et al. (2011) は、7次元のケラーグラフの最大クリークサイズが124であることを示した。これは2^ ⁷ = 128より小さいため、グラフ理論版のケラー予想は7次元で成り立つ。しかし、立方体タイリングからグラフ理論への翻訳は問題の次元を変える可能性があるため、この結果は7次元における幾何学版のケラー予想を確定させるものではない。最終的に、2019年に200ギガバイトのコンピュータ支援証明がケラーグラフを用いて、この予想が7次元で成り立つことを証明した。 ^[5]したがって、ケラーが提起した問題は解決されたとみなすことができる。つまり、この予想は7次元以下では真であるが、7次元を超える場合は偽である。^[6]

2次元、3次元、4次元、5次元、6次元のケラーグラフにおける最大クリークの大きさは、それぞれ2、5次元、12次元、28次元、60次元である。4次元、5次元、6次元のケラーグラフは、クリーク発見アルゴリズムのベンチマークとして頻繁に使用される「DIMACSチャレンジグラフ」のセットに含まれている。^[7]

注釈

^ abc Szabó (1993); Shor (2004); Zong (2005)
^ Łysakowska and Przesławski (2011, 2012).
^ Conway、Burgiel、Goodman-Strauss（2008年）。
^ Corrádi & Szabó (1990).
^ Brakensiekら（2020年）。
^ ハートネット (2020).
^ Johnson & Trick (1996); Debroni et al. (2011)、「ケラーグラフは、DIMACSクリークチャレンジのクリーク問題のベンチマークセットに含まれており、クリークアルゴリズムにとって特に難しいようです。」
^ Szabó (1993).
^ サボー (1982).
^ Grünbaum & Shephard (1980).

参考文献

Brakensiek, Joshua; Heule, Marijn ; Mackey, John; Narváez, David (2020)、「ケラー予想の解決」、Peltier, Nicolas; Sofronie-Stokkermans, Viorica (編)、『自動推論：第10回国際合同会議、IJCAR 2020、パリ、フランス、2020年7月1日～4日、議事録、パートI、Lecture Notes in Computer Science、vol. 12166、Springer、pp. 48～ 65、arXiv : 1910.03740、doi : 10.1007/978-3-030-51074-9_4、ISBN 978-3-030-51073-2、S2CID 203951899
ジョン・H・コンウェイ、ハイディ・バーギエル、チャイム・グッドマン＝ストラウス（2008年）「アイルランドのバブルを理解する」『物事の対称性』、マサチューセッツ州ウェルズリー：AKピーターズ、351ページ、ISBN 978-1-56881-220-5、MR 2410150
Corrádi, K.; Szabó, S. (1990)、「ケラー予想に対する組合せ論的アプローチ」、Periodica Mathematica Hungarica. Journal of the János Bolyai Mathematical Society、21 (2): 95– 100、doi :10.1007/BF01946848、MR 1070948、S2CID 121453908。
デブロニ、ジェニファー、エブレン、ジョン・D、ラングストン、マイケル・A、ショア、ピーター、ミルボルド、ウェンディ、ウィーラプラゲ、ディネシュ (2011)、「ケラー最大クリーク問題の完全解決」(PDF)、第22回ACM-SIAM離散アルゴリズムシンポジウム論文集、pp. 129– 135、doi :10.1137/1.9781611973082.11、hdl : 1721.1/81184、ISBN 978-0-89871-993-2、S2CID 15797721。
Dutour Sikirić, Mathieu; Itoh, Yoshiaki; Poyarkov, Alexei (2007)、「Cube packings, second moment and holes」、European Journal of Combinatorics、28 (3): 715– 725、arXiv : math/0509100、doi :10.1016/j.ejc.2006.01.008、MR 2300752、S2CID 15876010。
Grünbaum, Branko ; Shephard, GC (1980)、「同型タイルによるタイリング」、米国数学会報、3 (3): 951– 973、doi : 10.1090/S0273-0979-1980-14827-2、MR 0585178。
Hajós, G. (1949)、「Sur la factorisation des groupes abéliens」、Československá Akademie Věd. Časopis Pro Pěstování Matematiky、74 : 157–162、MR 0045727。
ハートネット、ケビン（2020年8月19日）「コンピュータ検索が90年来の数学の問題を解決」Quanta Magazine。
Iosevich, Alex; Pedersen, Steen (1998)、「単位立方体のスペクトル特性とタイリング特性」、International Mathematics Research Notices、1998 (16): 819– 828、arXiv : math/0104093、doi : 10.1155/S1073792898000506、MR 1643694、S2CID 14232561。
ジョンソン、デイビッド・S. ;トリック、マイケル・A. (1996)、「クリーク、カラーリング、および満足度：第2回DIMACS実装チャレンジ、ワークショップ、1993年10月11日～13日、ボストン、マサチューセッツ州、米国：アメリカ数学会、ISBN 0-8218-6609-5特に43ページ、114ページ、147ページ、156ページ、161～163ページを参照してください。このチャレンジセットに含まれるケラーグラフに関するさまざまな計算結果が説明されています
ケラー、O. -H. (1930)、「Über die lückenlose Erfüllung des Raumes mit Würfeln」、Journal für die reine und angewandte Mathematik (ドイツ語)、1930 (163): 231–248、doi :10.1515/crll.1930.163.231、JFM 56.1120.01、S2CID 199547028。
ラガリアス、ジェフリー・Ｃ．リード、ジェームス A. Wang、Yang (2000)、「-cube の指数関数の正規直交基底」、Duke Mathematical Journal、103 (1): 25–37、CiteSeerX 10.1.1.207.4194、doi :10.1215/S0012-7094-00-10312-2、MR 1758237 $n$ 。
ラガリアス, ジェフリー・C. ;ショア, ピーター・W. (1992)、「ケラーの立方体タイリング予想は高次元では誤りである」アメリカ数学会報、新シリーズ、27 (2): 279– 283、arXiv : math/9210222、Bibcode :1992math.....10222L、doi :10.1090/S0273-0979-1992-00318-X、MR 1155280、S2CID 6390600。
Lagarias, JC ; Shor, PW (1994)、「キューブタイリングと非線形コード」、離散および計算幾何学、11 (4): 359– 391、doi : 10.1007/BF02574014、MR 1273224 $\mathbb {R}^{n}$ 。
Łysakowska, Magdalena; Przesławski, Krzysztof (2011)「低次元における立方体タイリングの構造と拡張不可能な立方体システムについて」European Journal of Combinatorics、32 (8): 1417– 1427、doi : 10.1016/j.ejc.2011.07.003。
Łysakowska, Magdalena; Przesławski, Krzysztof (2012)、「立方体タイリングにおける列の存在に関するケラーの予想」、Advances in Geometry、12 (2): 329– 352、arXiv : 0809.1960、doi :10.1515/advgeom.2011.055、MR 2911153、S2CID 14016886 $\mathbb {R}^{n}$
マッキー、ジョン（2002）、「面共有のない8次元立方体タイリング」、離散幾何学と計算幾何学、28（2）：275-279、doi：10.1007/s00454-002-2801-9、MR 1920144。
Perron, Oskar (1940a)、「Über lückenlose Ausfüllung des -Dimensionen Raumes durch kongruente Würfel」、Mathematische Zeitschrift、46 : 1–26、doi : 10.1007/BF01181421、MR 0003041、S2CID 186236462 $n$ 。
Perron, Oskar (1940b)、「Über lückenlose Ausfüllung des -Dimensionen Raumes durch kongruente Würfel. II」、Mathematische Zeitschrift、46 : 161–180、doi : 10.1007/BF01181436、MR 0006068、S2CID 123877436 $n$ 。
ロビンソン、ラファエル・M. (1979)、「単位立方体による次元空間の多重タイリング」、Mathematische Zeitschrift、166 (3): 225– 264、doi : 10.1007/BF01214145、MR 0526466、S2CID 123242152 $n$ 。
ショア、ピーター（2004）、ミンコフスキーとケラーの立方体タイリング予想、IAP数学講義シリーズの講義ノート。
Szabó, Sándor (1982)、「面を共有しない立方体による複数のタイリング」(PDF)、Aequationes Mathematicae、25 (1): 83–89、doi :10.1007/BF02189600、MR 0716380、S2CID 122364522。
Szabó, Sándor (1986)、「ケラー予想の還元」、ハンガリカ数学定期刊行物。 János Bolyai Mathematical Society のジャーナル、17 (4): 265–277、doi :10.1007/BF01848388、MR 0866636、S2CID 120163301。
Szabó, Sándor (1993)、「幾何学への代数の貢献としての立方体タイリング」、Beiträge zur Algebra und Geometrie、34 (1): 63–75、MR 1239279。
宗, 川明 (2005)、「単位立方体についてわかっていること」アメリカ数学会報、新シリーズ、42 (2): 181– 211、doi : 10.1090/S0273-0979-05-01050-5、MR 2133310。

[general-1] Szabó (1993); Shor (2004); Zong (2005)

[2] Łysakowska and Przesławski (2011, 2012).

[FOOTNOTEConwayBurgielGoodman-Strauss2008-3] Conway、Burgiel、Goodman-Strauss（2008年）。

[FOOTNOTECorrádiSzabó1990-4] Corrádi & Szabó (1990).

[FOOTNOTEBrakensiekHeuleMackeyNarváez2020-5] Brakensiekら（2020年）。

[FOOTNOTEHartnett2020-6] ハートネット (2020).

[7] Johnson & Trick (1996); Debroni et al. (2011)、「ケラーグラフは、DIMACSクリークチャレンジのクリーク問題のベンチマークセットに含まれており、クリークアルゴリズムにとって特に難しいようです。」

[FOOTNOTESzabó1993-8] Szabó (1993).

[FOOTNOTESzabó1982-9] サボー (1982).

[FOOTNOTEGrünbaumShephard1980-10] Grünbaum & Shephard (1980).