テレンス・タオが、60 年前のもう一つの幾何学の問題に取り組みます。周期的タイル分割問題における新たなブレークスルー

テレンス・タオ氏が研究してきた周期的モザイク化問題に新たな進歩がありました。

9月18日、Terence TaoとRachel Greenfeldはプレプリント論文「翻訳モノタイリングの決定不能性」をarXivにアップロードしました。

論文アドレス: https://arxiv.org/abs/2309.09504

この論文の主な結論は、グリッドの次元が無制限である場合、グリッドの有限サブセットがそのグリッドの周期サブセットをタイルできるかどうかを判断する問題は決定不可能であるということです。

この問題は次元 1 と 2 の両方で決定可能であることに注意してください。

タオ氏は、記事で紹介されたコンポーネントのほとんどが人気ゲームに似ているのは少し奇妙だと述べた。

ドミノ、数独、コンピュータ ゲームのテトリス、さらには子供向けのゲームであるフィズ バズに類似したタイル ゲームもあります。

なぜ数学の問題を勉強するにはこれほど多くのゲームが必要なのでしょうか?テレンス・タオもそれを説明できなかった。

並進単純テッセレーションの決定不可能性

この論文は二人が書いた前回の論文の続編です。リンク 周期的テッセレーション問題

前回の論文では、高次元グリッドの並進単一タイル分割を構築した。

(したがって、単純なテッセレーションは有限集合です)、非周期的です(このテッセレーションを周期的なテッセレーションに「固定」する方法はなく、インデックスの有限サブグループに関して周期的になります)。

これは、そのような非周期的なタイリングモノマーは存在しないと主張した Stein、Grunbaum-Shephard、および Lagarias-Wang の周期的なタイリングの予想を反証するものです。

(「ハット タイリング」は、回転、反射、および平行移動が可能な最近発見された非周期的等角投影タイリング、または新しい「ゴースト タイリング」です。上記のタイリングは、反射が必要ないことを除いて、ハット タイリングに似ています)。

テレンス・タオとレイチェル・グリーンフェルドがこの推測を思いついた理由の一つは、数学者ハオ・ワンの観察でした。

彼は、周期的モザイク予想が正しい場合、平行移動モザイク問題はアルゴリズム的に決定可能であることを発見した。

には、次元と有限部分集合 が与えられると、有限時間内にをモザイク化できるかどうかを判定できるチューリングマシン があります。

周期的なテッセレーションが存在する場合、コンピューター検索を通じて見つけることができるためです。

テッセレーションがまったくない場合、コンパクト性定理は、分離した変換ではカバーできない有限のサブセットがいくつかあることを示しています。これは、コンピューター検索によっても発見できます。

周期的モザイク化予想は、これらが唯一の 2 つのケースであると主張し、したがって決定可能になります。

一方、Wang の議論は不可逆的である。周期的タイリング予想の失敗は、周期的タイリングの存在に依存しないタイリングを決定する他のアルゴリズムの存在を排除しないため、自動的に並進単純タイリング問題の決定不能性を意味するわけではない。

(たとえば、新しく発見されたハット テッセレーションとゴースト テッセレーションがあっても、有理係数を持つ多角形の等角単純テッセレーション問題が、反射の有無にかかわらず決定可能かどうかは未解決の問題のままです。

この論文の主な結果は、この疑問に答えています（ただし、1 つの注意点があります）。

定理1

次元、周期的サブセット、有限サブセットが与えられた場合、有限時間内に変換テッセレーションが存在するかどうかを判断できるアルゴリズムは存在しません。

すべての周期性を使用するのではなく、そのサブセットを使用する必要があることに注意することが重要です。これは主にこのアプローチの技術的な制限によるもので、追加の努力と創造性によって排除できる可能性があります。

さらに、Tao と Rachel Greenfeld は、 のとき、周期的タイリング予想は Bhattacharya によって確立されているため、この場合、問題は決定可能であると指摘しています。

テッセレーション問題が任意の固定値に対して決定可能かどうかは未解決のままです(上記の結果では、次元は固定されておらず、入力の一部であることに注意してください)。

アルゴリズムの決定不能性と論理的な決定不能性 (論理的独立性とも呼ばれる) の間のよく知られた関係により、この定理は、(原理的には明確に記述可能な)次元の周期的部分集合、 、およびの有限部分集合が存在し、ZFC 集合論では変換によるテッセレーションが検証または反証できないことも意味します (もちろん理論が一貫していると仮定した場合)。

このアプローチの結果として、ここでは「ほぼ 2 次元」のグループを代用することもできます。ここで、は有限アーベル群です (これは入力の一部となり、次元 を置き換えます)。

次に、証明のいくつかの主要なアイデアについて説明します。

問題が決定不可能であることを証明する一般的な方法は、決定不可能であることがわかっている他の問題を元の問題に「エンコード」することです。これにより、元の問題を決定できるアルゴリズムであれば、埋め込まれた問題も決定できるようになります。

したがって、Wangのテッセレーション問題を単一のテッセレーション問題としてエンコードします。

問題2（王のテッセレーション問題）

有限の Wang タイリング セット(各エッジに有限のパレットからいくつかの色が割り当てられた単位正方形) が与えられた場合、隣接するタイリングの共通エッジが同じ色になるように、平行移動によって標準格子を使用して平面をタイリングすることは可能ですか?

バーガーはかつて、この問題は決定不可能であるという有名な結果を与えました。

バーガー、ロバート、<ドミノ問題の決定不可能性>

この問題を高次元の並進単一テッセレーション問題に組み込むには、いくつかの中間問題を通過する必要があります。

まず、Wang のテッセレーション問題を、ドミノ問題と呼ばれる類似の問題に簡単に埋め込むことができます。

問題3（ドミノ問題）

隣接する単位正方形のペアである水平（または垂直）ドミノまたはの有限集合が与えられ、それぞれに有限集合からの点が点在している場合、標準の格子タイリングの各単位正方形に点を割り当てて、タイリング内のすべての水平（または垂直）正方形のペアが または からのドミノを使用するようにすることは可能ですか？

実際には、各 Wang テッセレーションを個別の「ドット」として挿入し、水平または垂直に隣接し、エッジの色が同じWangテッセレーションのペアとしてドミノのセットを定義するだけです。

次に、ドミノ問題を数独問題に埋め込みます。

質問4（数独問題）

列幅、数値セット、関数セット、および「初期条件」 （ここでは詳しく説明しません）が与えられた場合、 「数独ボード」の各セルに数値を割り当てて、任意の傾きと切片に対して、線に沿った数値が 内にある（および初期条件 に従う）ようにすることは可能ですか？

この論文の最も斬新な部分は、ドミノ問題が実際に数独問題に組み込むことができるという証明です。

数独問題を単一のテッセレーション問題に埋め込む方法は、前回の論文で修正した方法から派生したものです。

これらの論文では、数独問題のバージョンも紹介され、さまざまな問題 (数独を含む) を単一のテッセレーション問題として「エンコード」するために使用できる「テッセレーション言語」も作成されました。

ドミノ問題を数独問題としてエンコードするには、ドミノ関数を取得する必要があります。

(ドミノのセットに関連付けられたいくつかのドミノ制約に従う)、そしてこれを使用して数独関数を構築します(ドミノのセットに関連付けられたいくつかの数独制約に従う)。逆に、数独パズルのルールに従うすべての数独関数は、何らかの方法でドミノ関数から派生する必要があります。

これがどのように行われるかはすぐには分かりませんが、テレンス・タオとレイチェル・グリーンフェルドは、エマニュエル・ジャンデルの助けを借りて、アンデラとルイスのアイデアの一部を採用し、ある種の階層を使用して 1 つの問題を別の問題にエンコードしました。

ここでは階層構造について説明します（ドミノ問題は 2 次元であるため、2 つの異なる素数が必要です）。

次に、数式で数独関数を構築することにより、ある種の埋め込みが反映されます。

ここで、 は2つの異なる大きな素数（例えば、 、 ）であり、 は の分割数を表し、

の展開における最後のゼロでない数は:

（ 、そして）。

の場合、（１）の最初の成分は次のようになる。

最終コンポーネントの典型的な例を以下に示します。

興味深いことに、なぜかここの装飾は基本的に子供のゲーム「フィズバズ」のルールに従っています。