ケラーの予想

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

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

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

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

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

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

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

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

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

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

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

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

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

その後、デブロニら (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]

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

ケラーの予想はミンコフスキーの予想の変形で、立方体の中心が格子を形成するという条件が緩和されている。1936 年にフルトヴェングラーが行った 2 番目の関連予想では、立方体がタイリングを形成するという条件が緩和されている。フルトヴェングラーは、空間のk重被覆を形成する格子点を中心とした立方体のシステム (つまり、空間内の点のうち測度が 0 の部分集合を除くすべてが、ちょうど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]