ケラーの推測

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

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

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

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

ユークリッド空間のテセレーションまたはタイリングは、直感的には、空間全体を重なり合わずに覆う部分集合の族です。より厳密には、タイルと呼ばれる閉集合の族は、それらの和集合が空間全体であり、その族内の任意の異なる2つの集合の内部が互いに素である場合にタイリングを形成します。タイリングは、すべてのタイルが同じ形状（互いに合同）である場合に単面体であると言われます。ケラー予想は、すべてのタイルが空間と同じ次元の超立方体である単面体タイリングに関するものです。サボー（1986）が問題を定式化しているように、立方体タイリングは、合同な超立方体によるタイリングであり、タイルはすべて回転なしで互いに平行移動している必要があり、または同等に、すべての辺が空間の座標軸に平行である必要があります。合同な立方体によるすべてのタイリングがこの性質を持つわけではありません。たとえば、3 次元空間は、互いに任意の角度でねじれた 2 次元の立方体シートでタイリングできます。同じ問題を定式化するにあたり、Shor (2004)は、合同な超立方体による空間のすべてのタイリングを考慮し、立方体が軸に平行であるという仮定を追加しても一般性は失われないと証明なしで述べています。

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

ケラーが述べた予想の元のバージョンは、より強い主張でした。すなわち、すべての立方体タイリングには、面と面が接する立方体の列が存在するというものです。この問題のバージョンは、より一般的に研究されている定式化と同じ次元で真または偽となります。^{[ 2 ]} タイリング内の立方体がすべて互いに合同であることは、予想の必須部分です。なぜなら、大きさが異なる立方体が許容される場合、ピタゴラスタイリングは2次元で反例を形成することになるからです。

述べられている予想では、タイリング内のすべての立方体が他の立方体と面と面を合わせて接する必要があるわけではありません。平面上の合同な正方形によるタイリングでは、すべての正方形が他の正方形と辺と辺を合わせて接するという強い性質がありますが、高次元のハイパーキューブタイリングでは、一部のタイルが他のどのタイルとも面と面を合わせて接しない場合があります。たとえば、3 次元では、3 つの垂直な正方形プリズムのセットによって形成されるテトラスティックス構造を使用して、組み合わせ論的にWeaire–Phelan 構造と等価な立方体タイリングを構築できます。この構造では、立方体の 4 分の 1 (どのプリズムにも含まれていないもの) が、他の 12 個の立方体に囲まれていますが、それらのどれとも面と面を合わせて接していません。^{[ 3 ]}

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

Hajós (1949)は、アーベル群の因数分解の観点からケラーの予想を最初に再定式化した。彼は、予想に対する反例が存在する場合、それは整数辺の長さと整数頂点位置を持つ立方体の周期的なタイル張りであると仮定できることを示した。したがって、予想を研究する際には、この特殊な形式のタイル張りを考慮すれば十分である。この場合、タイル張りを保存する並進を法とする整数並進の群はアーベル群を形成し、この群の特定の要素はタイルの位置に対応する。Hajós は、アーベル群の部分集合の族A _iが因数分解であると定義するのは、群の各要素が和a ₀ + a ₁ + ...として一意の表現を持ち、各a _iがA _iに属する場合である。この定義に基づくと、Hajós の再定式化された予想は、アーベル群が、最初の集合A ₀は任意であるが、後続の各集合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 ]}             

Szabó (1986) は、この予想に対する反例となるタイリングは、さらに特別な形式を持つと仮定できることを示した。すなわち、立方体の辺の長さは2 のべき乗であり、頂点の座標は整数であり、タイリングは各座標方向で立方体の辺の長さの 2 倍の周期を持つ周期的である。この幾何学的単純化に基づいて、彼は Hajós の群論的定式化も単純化し、各q _i = 2の位数 4 の巡回群の直和であるアーベル群を考慮すれば十分であることを示した。  

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

LagariasとShor （1992 ）は、10次元のケラーグラフにサイズ2× ¹⁰のクリークを発見することで、ケラーの予想を否定した。このクリークは10次元で非対面タイリングにつながり、そのコピーを（各座標方向に半単位ずらして）積み重ねることで、任意の高次元で非対面タイリングを生成できる。同様に、Mackey（2002）は8次元のケラーグラフにサイズ2× ⁸のクリークを発見し、同じ方法で8次元および（積み重ねることで）9次元で非対面タイリングにつながる。 

その後、Debroni ら (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 ]}

サボー（1993）が述べているように、ヘルマン・ミンコフスキーはディオファントス近似の問題から立方体タイリング予想の特殊なケースにたどり着いた。ミンコフスキーの定理の帰結の一つは、任意の格子（行列式が1になるように正規化されている）は、原点からのチェビシェフ距離が最大で1である非ゼロ点を含まなければならないということである。チェビシェフ距離が厳密に1より小さい非ゼロ点を含まない格子は臨界格子と呼ばれ、臨界格子の点は立方体タイリングの立方体の中心を形成する。ミンコフスキーは1900年に、立方体タイリングの立方体がこのように格子点を中心とする場合、必ず面と面を接する2つの立方体が含まれると予想した。これが正しいとすれば、（格子の対称性により）タイリング内の各立方体は立方体の列の一部でなければならず、これらの列の断面は、1つ小さい次元の立方体タイリングを形成する。このように推論して、ミンコフスキーは（彼の予想が正しいと仮定すると）すべての臨界格子は、主対角線上に1があり、対角線から1未満の数だけ離れた三角行列として表現できる基底を持つことを示した。ジョルジュ・ハヨーシュは、 1942年にアーベル群の因数分解に関するハヨーシュの定理を用いてミンコフスキーの予想を証明した。これは、彼が後にケラーのより一般的な予想に適用することになる方法と同様の群論的方法である。^{[ 8 ]}

ケラーの予想は、立方体の中心が格子を形成するという条件を緩和したミンコフスキーの予想の変形である。1936年にフルトヴェングラーが立てた2番目の関連する予想は、立方体がタイルを形成するという条件を緩和している。フルトヴェングラーは、空間のk重被覆を形成する格子点を中心とする立方体のシステム（つまり、空間内の点のうち測度ゼロの部分集合を除くすべてがちょうどk個の立方体の内部にある必要がある）は、必ず2つの立方体が面と面を合わせて接することになるのかと問いかけた。フルトヴェングラーの予想は2次元および3次元空間では真であるが、1938年にハヨースが4次元の反例を発見した。ロビンソン（1979）は、反例を許容するkと次元nの組み合わせを特徴づけた。さらに、フルトヴェングラー予想とケラー予想の両方を組み合わせることで、ロビンソンは、ユークリッド平面のk重正方形被覆には、辺同士が接する 2 つの正方形が含まれる必要があることを示した。しかし、k  >  1およびn  >  2のいずれの場合も、共有面を持たない立方体によるn次元空間のk重タイリングが存在する。^{[ 9 ]}

ケラー予想に対する反例が知られるようになると、立方体のタイル張りで必ず存在する共有面の最大次元を求めることが興味深いものとなった。次元nが最大 7 の場合、この最大次元は、これらの小さな次元に対するケラー予想の証明により、ちょうどn  −  1であり、 nが少なくとも 8 の場合、この最大次元は最大でn  −  2である。LagariasとShor (1994)は、最大でn  − √ n /3 であり、10 次元以上ではより強いことを示した。

Iosevich & Pedersen (1998)およびLagarias, Reeds & Wang (2000)は、立方体のタイル張りと立方体上の二乗可積分関数のスペクトル理論との間に密接な関係があることを発見した。

Dutour Sikirić、Itoh & Poyarkov (2007)は、ケラーグラフ内の最大ではあるが最大ではないクリークを使用して、追加の立方体を追加しても拡張できない空間への立方体の充填を研究しています。

1975年、ルートヴィヒ・ダンツァーと、独立してブランコ・グリュンバウムとGCシェパードは、面角が60°と120°の平行六面体による3次元空間のタイル張りを発見した。このタイル張りでは、2つの平行六面体が面を共有しない。^{[ 10 ]}