コンピューター検索は、90年前の数学の問題を解決するのに役立ちました

ケラーの仮説をコンピューターが理解できるグラフ検索言語に翻訳することにより、研究者たちはついにスペースをタイルで覆うという問題を解決しました。

数学者のチームがついにケラーの仮説を理解しましたが、それだけではありません。代わりに、彼らはコンピューターのフリート全体をトレーニングし、それを解決しました。



90年前にOtt-HeinrichKellerによって提唱されたKellerの仮説は、同じタイルでスペースをカバーするタスクに関連しています。彼女は、2次元の正方形のタイルで2次元の空間を舗装する場合、少なくとも2つは部分的にではなく、側面に完全に接触する必要があると主張しています。この仮説は、どの次元でも同じ予測を行います。つまり、12次元の空間を12次元の「正方形」で埋める場合、少なくとも2つは共通のエッジを持っている必要があります。



何年もの間、数学者はこの仮説をめぐって争い、ある次元ではその真実を証明し、他の次元では偽を証明しました。そして去年の秋までに、問題は7次元空間についてのみ未解決のままでした。



しかし、新しいコンピューター生成の証拠もその問題を解決しました。昨年10月に発表されたこの証明は、数学の最もエキサイティングな質問に答えるための、人間の天才と純粋な計算能力の組み合わせの最新の例の1つです。



新しい作品の作者、ジョシュアBreukensikスタンフォードの、マリンHijulとジョン・マッキーカーネギーメロン大学の、そしてデビッド・ナルバエスロチェスター工科大学のは、40台のコンピュータを使用してこの問題を解決しました。わずか30分で、マシンは単音節の答えを出しました。はい、7つの次元で、仮説は正しいです。そして、私たちは信仰についてこの結論を下す必要さえありません。



答えに添付されているのは、その真実を説明する長い証拠です。証明は人間が理解するには長すぎますが、別のコンピュータプログラムがそれを検証できます。



言い換えれば、ケラーの仮説を証明するためにコンピューターが何をしたのか正確にわからなくても、少なくともコンピューターが正しくそれを行ったことを確認することができます。

神秘的な7次元

ケラーの推測が二次元で真実であることは容易に理解できます。一枚の紙を取り、隙間や重なりのない等しい正方形でそれを覆うようにしてください。すぐに、少なくとも2つの正方形の辺が同じである場合にのみこれを実行できることがわかります。手元にキューブがある場合は、仮説が3次元に当てはまることを簡単に確認できます。 1930年、ケラーは、この関係がすべてのディメンションとそれに対応するタイルで機能することを提案しました。



初期の結果はケラーの予測を裏付けました。 1940年、オスカー・ペロンは、1から6までの測定で仮説が正しいことを証明しました。しかし、50年以上後、新世代の数学者がこの仮説に対する最初の反例を見つけました。1992年、ジェフリー・ラガリアスとピーター・ショア仮説が10次元では機能しないことを証明しました。





ケラーの仮説は、任意の次元のスペースを埋めるとき、少なくとも2つのタイルが完全に側面に接触する必要があると予測しています。

二次元空間を埋めるとき、多くのタイルは共通の側面（青い線）を持っています。

3D空間を埋めるとき、多くのキューブには共通の面（青）があります。



ある次元で仮説が失敗した場合、それがすべての上位の仮説に当てはまるわけではないことを示すのは簡単です。したがって、LagariasとShorの作業の後、7次元、8次元、および9次元の問題を解決することだけが残っています。 2002年に、マッキーはケラーの仮説が次元8（したがって9）について誤っていることを証明しました。



7番目の次元のみが開いたままでした。これは、この仮説が正しい最大の次元か、仮説が正しくない最小の次元のいずれかでした。



「そこで何が起こっているのか正確には誰も知りません」とキユルは言いました。

点を結びます

数学者は数十年の間この問題に苦しんでいましたが、彼らの方法は徐々に変化しました。ペロンは鉛筆と紙だけを使用して最初の6次元に取り組みましたが、1990年代までに、研究者はケラーの仮説を完全に異なる形式に変換する方法を理解しました。コンピューターを使用してそれを解決できるようにしました。



ケラーの推測の元の定式化は、滑らかな連続空間に関するものです。このようなスペースでは、無限の数のタイルを配置する方法が無限にあります。しかし、コンピューターは、無限の数のオプションで問題を解決するのが得意ではありません。それらに対処するには、離散的で有限のオブジェクトが必要です。





カーネギーメロン大学のマリンヒジュール



1990年に、KereszteliKorradiとSandorShaboは、適切な個別のオブジェクトを考案しました。彼らは、ケラーの仮説と同等の質問をこのオブジェクトについて尋ねることができることを示しました。そして、これらのオブジェクトに関連する何かを証明すると、ケラー仮説が証明されます。これにより、無限大の問題が、複数の数値を使用するより複雑でない算術問題になりました。



仕組みは次のとおりです。



ケラーの仮説を2次元で理解したいとします。 CorradiとChabotは、ケラーグラフと呼ばれる構造の構築を使用して、この方法を考案しました。



まず、テーブルに16個のダイスがあり、それらすべてに2つのドットがある上端があると想像してください（2つのドットは2次元空間を示し、なぜ16個のキューブがあるのか​​-少し後で説明します）。すべてのキューブは同じ方法で回転するため、2つのポイントはすべての人にとって同じ位置に配置されます。各ドットを、赤、緑、白、または黒の4色のいずれかで着色します。



1つのキューブ上のポイントは場所を変更しません-それらの1つはx座標を示し、もう1つは-yを示します。キューブに色を付けたら、2つの条件が満たされた場合に、キューブのペアの間に線またはエッジを描画し始めます。キューブのペアの同じ場所にあるポイントの色が異なり、他のポイントでは異なるペアになっており、赤と緑はペアまたは黒と見なされます。白で。





2次元のケラーグラフ。それぞれが他のすべてに接続されている4つのキューブのサブセットを見つけると、2次元空間のケラー仮説を反証します。ただし、そのようなサブセットはなく、仮説は正しいです。

以下は、グラフにない4つのダイスの完全にマージされたクリークの例です。



つまり、たとえば、一方のキューブに2つの赤いドットがあり、もう一方のキューブに2つの黒いドットがある場合、それらはエッジで接続されていません。同じ位置にあるポイントの色は異なりますが、ペアリングの要件を満たしていません。 1つのキューブに赤と黒のドットがあり、もう1つのキューブに2つの緑のドットがある場合、一方の位置ではペアの色（赤と緑）があり、もう一方のキューブでは単純に異なる（黒と緑）ため、エッジで接続されます。



2つのポイントを4つの色で着色する方法は16あります（つまり、16個のキューブがあります）。これらの16の可能性をすべて目の前に配置します。要件を満たすキューブのすべてのペアを接続します。スキームに4つのキューブがあり、それぞれが他の3つのキューブと組み合わされていますか？



このように完全に接続されたキューブのサブセットは、クリークと呼ばれます。あなたがそれを見つけることができれば、あなたは二次元でケラー仮説を反証するでしょう。しかし、あなたはできません-それは単に存在しません。そして、そのような4つの立方体のクリークがないということは、ケラーの仮説が2つの次元に当てはまることを意味します。



これらのキューブは、文字通りケラーの仮説と同じタイルではありませんが、各キューブがタイルを表していると想定できます。ポイントに割り当てられた色を、キューブを空間に配置する座標と見なします。また、エッジの存在は、2つのキューブが相互にどのように配置されているかを示しています。



キューブの色が同じである場合、それらは等間隔のタイルを表します。共通の色と色のペアがない場合（一方は黒と白、もう一方は緑と赤）、部分的に重なり合っているタイルを示します。これは、スペースを埋めることができません。 2つのキューブに1セットの一致する色と1セットの同じ色（1つは赤黒、もう1つは緑黒）がある場合、それらは共通の側面を持つタイルを表します。



最後に、そして最も重要なのは、ペアの色のセットと異なる色のセットがある場合、つまりエッジで接続されている場合、キューブは互いに接触しているがわずかにシフトしているタイルを表します。そのため、エッジは完全には一致しません。 ..。私たちが研究する必要があるのはこの状態です。エッジで接続されたキューブは、共通の側面を持たない隣接するタイルを示します。これは、ケラーの仮説に反論するために必要な配置です。



「彼らは触れるべきですが、完全ではありません」とキユルは言いました。





同じ色-同じ配置。

異なる色、ペアなし-オーバーラップ。

2つのペアの色と同じペアが共通の側面です。

2つのペアの色と2つの異なる-側面による部分的な接触。

スケーリング

30年前、CorradiとShaboは、数学者が同様の手順を使用して、実験のパラメーターを微調整しながら、ケラーの仮説を任意の次元で処理できることを証明しました。ケラーの仮説を3次元で証明するために、エッジに3つのポイントがあり、場合によっては3つの色のペアを持つ216個のキューブを使用できます（ただし、ここにはある程度の柔軟性があります）。次に、上記と同じ条件に従って、互いに完全に接続された8つのキューブ（2 ³）を探す必要があります。



一般に、ケラーの推測をn次元で証明するには、n点の立方体を使用し、その中からサイズ^2nのクリークを見つけようとする必要があります。それは一種のスーパータイル（2 ⁿからなる）を表していると見なすことができます。より小さなタイル）n次元空間全体をカバーすることができます。



このスーパータイル（共通の側面を持つタイルがない）を見つけた場合は、そのコピーを使用して、共通の側面のないタイルでスペース全体を覆うことができます。これにより、ケラーの仮説が反証されます。



「成功すれば、スペース全体を転送でカバーできます。共通のタイル面のないブロックは床全体に広がります」と現在ミシガン大学にいるラガリアスは言いました。



マッキーは8次元でケラーの仮説に反論し、256キューブのクリークを見つけた（2 ⁸）ので、7次元での仮説を処理し続け、128キューブのクリークを見つけた（2 ⁷）。このクリークを見つけることは、7次元でケラーの仮説を反証します。それが存在しないことを証明し、仮説が真実であることを証明します。



残念ながら、128個のキューブのクリークを見つけることは特に難しい作業です。以前の研究では、研究者は、次元8と10は、ある意味で、作業が容易な低次元の空間に「分解」できるという事実を利用していました。そして、ここではこれは機能しませんでした。



「7は素数であり、それをより小さな次数の次元に分解することはできないため、7番目の次元は不便です」とLagarias氏は述べています。「したがって、これらのグラフの本格的な組み合わせに対処する以外に方法はありませんでした。」



128キューブのクリークを見つけることは、支援を受けていない脳にとっては難しい場合がありますが、これらは、特に少しの助けを借りて、コンピューターが答えるのが得意な種類の質問です。

論理の言語

クリックの検索をコンピューターが処理できるタスクに変えるには、提案ロジックの観点からそれを定式化する必要があります。これは、一連の制限を含む論理的な推論です。



3人が友達とのパーティーを計画しているとしましょう。ゲストリストを作成しようとしていますが、利害の衝突があります。Alexeiを招待するか、Kolyaを除外するとします。友達の1人が、Kolya、Vlad、またはその両方を招待したいと考えています。別の友人は、AlexeiまたはVladのどちらにも電話をかけたくありません。このような制限がある場合、3つすべてを満たすゲストリストを作成することは可能ですか？



コンピュータサイエンスの用語では、この問題は受容性の問題と呼ばれます。これは、提案式に条件を記述することで解決できます。この場合、次のようになります。A、K、およびBは、潜在的なゲストを示します：（A OR NOT K）AND（K OR B）AND（NOT A OR NOT B）。



コンピュータは、各変数に0または1を代入​​して計算します。0は変数「false」またはoffの値であり、1は「true」またはonです。 Aの代わりに0を使用すると、Alexeiは招待されなかった、1は招待されたと言います。この単純な式では、0と1は（ゲストリストを作成することによって）さまざまな方法で置き換えることができ、それらを繰り返した後、すべてのコンピューターがすべての利益を満たすことは不可能であると結論付ける可能性があります。ただし、この場合、すべての人を満足させるために1と0を置き換えるには、A = 1、K = 1、B = 0（AlexeyとKolyaを招待）とA = 0、K = 0、B = 1（1つのVladを招待）の2つの方法があります。 ）。



このようなステートメントを解決するコンピュータープログラムはSATソルバーと呼ばれ、SATはsatisfiabilityの略です。変数のすべての組み合わせを調べて、単音節の答えを出します-はい、式の要件を満たす方法があります、またはいいえ、そうではありません。





カーネギーメロン大学のジョン・マッキーは



「あなたはちょうどあなたがすべての変数に真と偽の値を割り当てることができるかどうかを確認するために探しているので、全体の式が真であり、そうならば、それは満足のいくものであること、およびでない場合は、何も、」言わなかったトーマス・ヘイルズのピッツバーグ大学。



128個の立方体のクリークを見つけるという問題も同様の問題です。また、提案式として書き直して、SATソルバーに渡すこともできます。それぞれ7つのドットと6つの可能な色を持つたくさんのキューブから始めます。特定のルールに従って128個のキューブが相互に接続されるようにドットに色を付けることは可能ですか？言い換えれば、クリックが表示されるように色を割り当てることは可能ですか？



クリックされた質問の提案式は非常に長く、39,000の変数が含まれています。それぞれに0または1の2つの値のいずれかを割り当てることができます。その結果、値を配置するための可能なオプションの数、または色を割り当てる方法は、^{2,39,000でした}。これは非常に多いです。



ケラー仮説に関する質問への答えを7次元で見つけるには、コンピューターはこれらすべての組み合わせをチェックする必要があります-そしてそれらをすべて除外するか（つまり、サイズ128のクリークが存在せず、7次元のケラー仮説が正しいことを意味します）、少なくとも1つの実用的なオプションになります（ケラーの仮説を反証します）。



「すべての可能性を単純に繰り返すと、324桁の数字に出くわします」とマッキーは言いました。世界最速のコンピューターは、すべての可能性を通り抜けて、時間の終わりまで実行されます。



しかし、新しい作品の作者は、コンピューターがすべての可能性をチェックせずに明確な答えを出す方法を理解しました。これの鍵は効率です。

隠れた効率

マッキーは、彼の観点から、プロジェクトが実際に機能し始めた日のことを思い出します。彼はカーネギーメロン大学の彼のオフィスの黒板の前に立って、2人の共著者、HijulとBreikensikと問題について話し合っていました。そのとき、Hijulは、妥当な時間で検索を完了することができるように検索を構成する方法を提案しました。



「その日、私のオフィスで働いていた本当の人間の天才がいました」とマッキーは言いました。 -NBAファイナルでウェイングレツキーやレブロンジェームスを見ているようなものでした。私はそれの記憶だけからグースバンプを持っています。」



特定のケラーグラフの検索をさまざまな方法で調整できます。テーブルにたくさんのキューブがあり、ケラー伯爵のルールに従って、そのうちの128個を解決しようとしていると想像してください。 12を正しく選択したが、次の12を追加する方法がわからないとします。この時点で、この機能していない12の構成を含む128のダイスの構成を破棄できます。



「最初の5つの割り当てが一致しないことがわかっている場合は、他の変数を探す必要はありません。これにより、通常、検索フィールドが大幅に削減されます」と、現在MITにいるShore氏は述べています。



別のタイプの効率は対称性に関連しています。対称オブジェクトは多少同じです。アイデンティティにより、オブジェクト全体を理解し、オブジェクトの一部のみを調査できます。人の顔の半分を見ると、オブジェクトを完全に復元できます。



同様に、ケラーグラフの場合は角を切ることができます。テーブルにキューブを並べようとしているともう一度想像してみてください。テーブルの中央から始めて、左側に手を置いたとしましょう。あなたは4つのダイスを配置し、行き止まりになります。これで、1つの開始の組み合わせと、それに基づくすべての組み合わせが削除されました。ただし、この最初の組み合わせのミラーリングを除外することはできます。つまり、同じ方法で右側にのみ配置した場合に得られるキューブの構成です。



「対称性を巧みに考慮した満足のいく問題を解決する方法を思いついた場合、タスクは大幅に簡素化されました」とヘイルズ氏は述べています。



4人の同僚は、この検索の効率を新しい方法で利用しました。特に、数学者は以前はほとんど手作業で処理していたのに対し、対称的なケースの検討を自動化しました。



その結果、サイズ128のクリークの検索が大幅に改善され、^239,000の構成をチェックする代わりに、プログラムで約10億（^2,30）をチェックするだけで済みました。これにより、ある朝のタスクに永遠にかかる可能性のある検索が行われました。最後に、わずか30分の計算の後、彼らは答えを受け取りました。



「コンピューターはノーと言ったので、仮説が機能することはわかっています」とヒユルは言いました。 128個のキューブをすべて互いにマージするように色付けすることは不可能であるため、7番目の次元に対するケラーの仮説が確認されます。スペースをカバーするタイルの配置では、必然的に少なくとも1対の完全に接触するエッジが存在します。



コンピューターは単音節の答えだけではありませんでした。彼は、この結論を裏付ける長い200GBの証明を添付しました。



証明は、コンピューターによって検証された変数のすべてのセットの単なる計算ではありません。これは、必要なクリークが存在できないことを証明する論理的な議論です。研究者たちは、議論の論理をたどることによって正式な証拠をテストするプログラムに証拠を送り、それを検証しました。



「すべてのオプションを調べただけでなく、何も見つかりませんでした。私たちはすべての選択肢を検討し、そのようなものが存在しないという証拠を書き留めることができました」とマッキーは言いました。「私たちは不満の証拠を書き留めることができました。」