非周期的なタイリング

非周期的タイリングは、任意の大きさの周期的な領域またはパッチを含まないという追加のプロパティを備えた非周期的タイリングです。タイルのコピーが非周期的タイリング のみを形成できる場合、タイルの種類 (またはプロトタイプ)のセットは非周期的です。

ペンローズ・タイリングは非周期的タイリングのよく知られた例である。^{[1] [2]}

2023年3月、デイビッド・スミス、ジョセフ・サミュエル・マイヤーズ、クレイグ・S・カプラン、チャイム・グッドマン＝シュトラウスの4人の研究者は、デイビッド・スミスが発見したタイルが非周期モノタイルであることの証明、すなわち、任意の単一形状の非周期タイルの存在を求める問題であるアインシュタイン問題の解決策を発表しました。 ^[3] 2023年5月、同じ著者らは、同様だがより強い制約を持つキラル非周期モノタイルを発表しました。^[4]

非周期的タイリングは、1982年にダン・シェヒトマン^[5]によって発見され、その後2011年にノーベル賞を受賞した物理的固体である準結晶の数学的モデルとして機能します。 ^[6]しかし、これらの材料の特定の局所構造はまだ十分に理解されていません。

非周期的なタイリングを構築するためのいくつかの方法が知られています。

単位正方形による周期的なタイリングを考えてみましょう (無限のグラフ用紙のように見えます)。次に、1 つの正方形を 2 つの長方形に切ります。この方法で得られたタイリングは非周期的です。つまり、このタイリングを固定したままにする非ゼロのシフトはありません。しかし、明らかにこの例はペンローズ タイリングほど面白くありません。このような退屈な例を除外するために、非周期的なタイリングを、任意の大きさの周期部分を含まないものと定義します。

タイリングの包が非周期的なタイリングのみを含む場合、そのタイリングは非周期的と呼ばれます。タイリングの包には、Tのすべての変換T + xと、 Tの変換で近似できるすべてのタイリングが含まれます。正式には、これはローカルトポロジーの集合の閉包です。^[7]ローカルトポロジー（または対応するメトリック）では、2つのタイリングが原点の周りの半径の球内で一致する場合、それらは -closeです（おそらく、タイリングの1つを 未満の量だけシフトした後）。 ${\displaystyle T\subset \mathbb {R} ^{d}}$${\displaystyle \{T+x\,:\,x\in \mathbb {R} ^{d}\}}$${\displaystyle \epsilon }$${\displaystyle 1/\varepsilon }$${\displaystyle \epsilon }$

上記よりもさらに簡単な例として、次のような直線の1 次元タイリングT を考えてみましょう。... aaaaaabaaaaa ... です。ここで、a は長さ 1 の区間、b は長さ 2 の区間を表します。したがって、タイリングT は、 aの無限個のコピーと、 bの 1 つのコピー(中心は 0 とします) で構成されます。ここで、Tのすべての変換は、どこかに1 つのbがあり、別の場所にsがあるタイリングです。bが中心にあるタイリングのシーケンスは、ローカル トポロジーで、s のみで構成される周期的なタイリングに収束します。したがって、Tは非周期的なタイリングではありません。その包には周期的なタイリング ... aaaaaa ... が含まれているからです。${\displaystyle 1,2,4,\ldots ,2^{n},\ldots }$

適切に動作するタイリング（例えば有限個の局所パターンを持つ置換タイリング）では、タイリングが非周期的かつ反復的（つまり各パッチがタイリング全体で均一な密度で発生する）である場合、それは非周期的である。^[7]

非周期的タイリングが初めて具体的に現れたのは 1961 年で、論理学者Hao Wang がドミノ問題が決定可能かどうか、つまり、与えられた有限の原型集合が平面のタイリングを許容するかどうかを決定するアルゴリズムが存在するかどうかを決定しようとしたときでした。Wang は、平面をタイリングできないタイルセットと、平面を周期的にタイリングできるタイルセットを列挙するアルゴリズムを見つけました。これにより、平面のタイリングを許容するすべての有限の原型集合が周期的なタイリングも許容する場合、そのような決定アルゴリズムが存在することを示しまし た。1964 年、Robert Berger は非周期的な原型集合を見つけ、そこからタイリング問題が実際には決定不可能であることを実証しました。^{[8] [9]} Berger が決定不能性の証明に使用したこの最初の集合には、20,426 個の Wang タイルが必要でした。ベルガーは後にセットを104に減らし、ハンス・ロイクリはその後、わずか40枚のワンタイルで済む非周期セットを発見した。^[10]ワンタイルを基にした6枚の非周期タイルからなるより小さなセットは、1971年にラファエル・M・ロビンソンによって発見された。 ^[11] ロジャー・ペンローズは1973年と1974年にさらに3つのセットを発見し、必要なタイルの数は2枚に減り、ロバート・アマンは1977年にいくつかの新しいセットを発見した。^{[12] 2023年にデビッド・スミス、ジョセフ・サミュエル・マイヤーズ、}クレイグ・S・カプラン、チャイム・グッドマン・シュトラウスによって必要なタイルの数は1枚に減らされた。^{[3] [4] [13]}

非周期的なペンローズタイリングは、非周期的な原型集合だけでなく、置換やカットアンドプロジェクション法によっても生成できます。準結晶の発見後、非周期的なタイリングは物理学者や数学者によって集中的に研究されるようになりました。ペンローズタイリングに対するNG de Bruijnのカットアンドプロジェクション法は、最終的にマイヤー集合の理論の一例であることが判明しました。^{[14] [15]}今日、非周期的なタイリングに関する文献は大量に存在します。^[7]

アインシュタイン（ドイツ語：ein Stein、一つの石）は、単一の形状のみを使用する非周期的なタイルです。そのようなタイルの最初のものは2010年に発見されました -ソコラー・テイラータイルですが、1つのピースに接続されていません。2023年に、「帽子」と呼ばれる形状を使用した接続されたタイルが発見されました。^[16]

非周期的タイリングの構成はいくつか知られています。いくつかの構成は、無限の非周期的タイル集合の族に基づいています。^{[17] [18]}これまでに発見されたタイリングは、主に何らかの非周期的な階層構造を強制することによって、いくつかの方法で構築されています。それにもかかわらず、ドミノ問題の決定不能性により、無限に多くの異なる構築原理が存在する必要があり、実際には、非周期性の証明が不可能な非周期的タイル集合が存在することが保証されます。

しかし、2023年までプロトタイプの有限集合に主に使用されてきた構築原則が3つあります。^[19]

• マッチングルール、
• 置換と拡張のルールと
• カットアンドプロジェクト方式。

いくつかのタイリングでは、そのタイリングを生成するために1つの構成法のみが知られています。他のものは、ペンローズタイリングなど、3つの古典的な方法すべてで構築できます。^[19]

グッドマン＝ストラウスは、置換ルールによって生成され、技術的条件を満たすすべてのタイリングは、マッチングルールによって生成できることを証明した。技術的条件は緩やかで、実際には通常満たされている。タイルは、置換タイリングが兄弟エッジ対エッジとなるような遺伝的エッジのセットを許容する必要がある。^[17]

タイリングでは、原型の合同なコピーがユークリッド平面全体を、重なり合うことなく (境界を除く)、覆われていない部分を残さずに敷き詰める必要があります。したがって、タイリングを形成するタイルの境界は、幾何学的に一致している必要があります。これは、非周期的および周期的タイリングを問わず、すべてのタイリングに当てはまります。場合によっては、これらの幾何学的一致条件だけで、タイル セットを非周期的にすることができます。これは、以下で説明する Robinsion のタイリングの場合などです。

場合によっては、追加のマッチング ルールが必須となります。これには通常、境界を越えて複数のタイルにまたがって一致する必要がある色やマークが含まれます。Wangタイルでは通常、このような追加のルールが必要です。

場合によっては、境界のプロトタイプを変更することで、マッチング ルールを幾何学的マッチング条件に完全に置き換えることも可能です。 ペンローズ タイリング (P1) は、もともと 4 つのプロトタイプといくつかのマッチング ルールで構成されています。4 つのタイルの 1 つは五角形です。この五角形のプロトタイプを、境界に突起とくぼみを追加して 3 つの異なるタイルを作成する 3 つの異なる五角形に置き換えることができます。適切に調整された境界を持つ他の 3 つのプロトタイプと一緒に、基本的に元の 4 つのタイルと同じ非周期的なタイリングを作成する 6 つのプロトタイプのセットが得られますが、6 つのタイルには追加のマッチング ルールは必要なく、幾何学的マッチング条件で十分です。

また、以下の Robinsion のプロファイルには、構造を視覚的に認識しやすくするためのマーキングが装備されていますが、これらのマーキングによって、幾何学的境界を通じてすでに設定されているタイルのマッチング ルールがさらに追加されるわけではないことに注意してください。

現在までに、タイリングが階層構造を持つかどうかを説明する正式な定義は存在しません。しかし、置換タイリングには階層構造があることは明らかであり、Berger、Knuth、Läuchli、Robinson、Ammannのタイリングも同様です。「非周期的タイリング」という用語自体と同様に、「非周期的階層的タイリング」という用語は便利な省略形であり、「階層構造を持つ非周期的タイリングのみを許可するタイルのセット」のような意味になります。

非周期的なタイリングの場合、追加のマッチング ルールが関係しているかどうかに関係なく、マッチング条件によってタイリングに何らかの階層構造が強制され、周期構造が不可能になります。

これらのタイルのセットは、どのようなタイリングでも、特定の階層構造を強制します。(後の多くの例では、この構造は置換タイリング システムとして説明できます。これについては後述します)。このようなタイルのセットによって許可されるタイリングは周期的ではありません。これは、単一の変換では階層構造全体を不変にできないためです。Robinson の 1971 年のタイルを検討してください。

これらのタイルによるタイリングは、正方形の格子の階層構造のみを示すことができます。つまり、オレンジ色の正方形の中心は、より大きなオレンジ色の正方形の角でもあり、この状態が無限に続きます。平行移動は、正方形のサイズよりも小さくなければならないため、このようなタイリングを不変のままにすることはできません。

ロビンソンは、これらのタイルがこの構造を形成しなければならないことを帰納的に証明しています。つまり、タイルはブロックを形成し、それ自体が元のタイルのより大きなバージョンとして組み合わさる必要がある、ということになります。階層構造のみを許容できるタイルのセットを見つけるというこのアイデアは、現在までに知られているほとんどの非周期的なタイルのセットの構築に使用されています。

しかし、このようにして生成されたタイリングは、ユークリッド群の等長変換、例えば並進や回転に至っても一意ではありません。ロビンソンのタイルで構築された平面の完全なタイリングには、最大4つの腕で無限に伸びる断層（廊下とも呼ばれる）がある場合とない場合があり、最大4文字のアルファベットΣに対してΣ ^ωから無限の単語をエンコードできる追加の選択肢があります。 ^[12]まとめると、ユークリッド等長変換によって関連付けられていない、必然的に非周期的な無数の異なるタイリングがロビンソンのタイルから生じます。

置換タイル システムは、非周期的なタイルの豊富なソースを提供します。置換構造を強制的に出現させるタイルのセットは、置換構造を強制すると言われています。たとえば、以下に示す椅子タイルは置換を許可しており、置換タイルの一部が右下に示されています。これらの置換タイルは、上で説明したのとまったく同じように、必然的に非周期的ですが、椅子タイル自体は非周期的ではありません。つまり、幾何学的マッチング条件を満たすマークされていない椅子タイルによる周期的なタイルを簡単に見つけることができます。

しかし、以下に示すタイルは椅子置換構造を強制的に出現させ、それ自体が非周期的である。^[20]

ペンローズタイルと、その後すぐにアンマンが提案したいくつかの異なるタイルセット^{[21] は}、置換タイリング構造を明示的に強制的に出現させることに基づいた最初の例でした。ジョシュア・ソコラー^{[22] [23]} ロジャー・ペンローズ[ ^24] ルートヴィヒ・ダンツァー^[25]およびチャイム・グッドマン＝シュトラウス^[20]は、その後いくつかのセットを発見しました。シャハール・モーゼスは、 1 次元置換システムのすべての積がマッチングルールによって強制できることを示した最初の一般的な構成を示しました。^[18] チャールズ・ラディンは、コンウェイ・ピンホイール置換タイリングシステムを強制するルールを発見しました。 ^[26] 1998 年、グッドマン＝シュトラウスは、いくつかの緩い条件の下で、任意の置換タイリング構造を強制するローカルマッチングルールが見つかる可能性があることを示しました。^[17]

非周期的なタイリングは、高次元構造を低次元空間に投影することによっても得られ、状況によっては、この非周期的な構造を強制するタイルが存在する可能性があり、したがって非周期的である。ペンローズタイルは、この最初の最も有名な例であり、de Bruijnの先駆的な研究で最初に指摘された。^[27]マッチングルールによって強制できるカットタイリングと投影タイリングの完全な（代数的な）特徴付けはまだ行われていないが、多数の必要条件または十分条件が知られている。^[28]

これまでに見つかっている構築法はほんのわずかです。特に、Jarkko Kari は、タイルの行でエンコードされた実数の 2 または 2/3 による乗算に基づく Wang タイルの非周期セットを与えました (エンコードは、Beatty シーケンスの連続する要素の差として作成されたSturmian シーケンスに関連しています)。この非周期性は主に、任意の正の整数nとmに対して 2 ⁿ /3 ^mが 1 に等しくなることはないという事実に依存しています。^{[29]この方法は後に}Goodman-Straussによって採用され、双曲平面で強く非周期的なタイルの集合が得られました。^[30] Shahar Mozesは、よりエキゾチックな設定を含む、非周期的なタイルの集合の代替構築を多数発見しました。たとえば、半単純リー群などです。^{[31] Block と Weinberger は、ホモロジー法を使用して、すべての非}従属多様体に対して非周期的なタイルの集合を構築しました。^{[32]ジョシュア・ソコラールは、}交代条件の観点から非周期性を強制する別の方法も示した。^[33]これにより、通常、置換から得られるものよりもはるかに小さなタイルセットが得られます。

非周期的なタイリングは、1984年に物理学者ダン・シェヒトマンがアルミニウムマンガン合金の相を発見し、明確な五回対称性を持つ鮮明な回折図形を生成したことを発表するまで、数学的な人工物と考えられていました^[5]。したがって、それは二十面体対称性を持つ結晶性物質でなければなりませんでした。1975年にロバート・アマンはすでにペンローズ構成を3次元の二十面体相当物に拡張していました。このような場合、「タイリング」という用語は「空間を埋める」という意味に解釈されます。現在、フォトニックデバイスは異なる層の非周期的なシーケンスとして構築されており、したがって1つの方向では非周期的、他の2つの方向では周期的です。Cd-Teの準結晶構造は、原子が平面の非周期パターンで配置された原子層で構成されているように見えます。このような非周期構造では、エントロピーのエネルギー最小値または最大値が発生することがあります。スタインハートは、グメルトの重なり合う十角形が極限原理の適用を可能にし、非周期的タイリングの数学と準結晶の構造を結びつけることを示した。^[34] ファラデー波は、非周期的パターンの大きなパッチを形成することが観察されている。^{[35]この発見の物理学は、非周期的タイリングと}干渉現象を結びつけることを示唆する不整合構造と周波数への関心を復活させた。 ^[36]

非周期的という用語は、タイリングに関する数学文献でさまざまな意味で使われてきました (また、力学系やグラフ理論などの他の数学分野でも、まったく異なる意味を持ちます)。タイリングに関して、非周期的という用語は非周期的という用語と同義語として使用されることがあります。非周期的タイリングとは、単に、非自明な翻訳によって固定されないタイリングのことです。この用語は、非周期的なプロトタイルの集合によって生成されるタイリングを暗黙的または明示的に説明することもあります。非周期的という用語は、多くの場合、対象構造を漠然と説明するためだけに使用され、物理的な非周期的固体、つまり準結晶、または何らかのグローバルな秩序を持つ非周期的なものを指しています。^[37]

「タイリング」という単語の使用も、その定義が明確であるにもかかわらず、問題があります。たとえば、ペンローズ タイリングは1 つではありません。ペンローズ 菱形には、無限の数のタイリング (局所的に区別できない) が存在します。一般的な解決策は、技術文書では用語を慎重に使用しながらも、非公式な用語が広く使用されていることを認識することです。

• ギリフタイル – イスラムの装飾芸術に使われる5つのタイル
• 非周期的なタイルのセットのリスト
• 準結晶 – 繰り返しパターンのない整然とした化学構造
• ゼリージュ – モザイクタイル装飾リダイレクト先の簡単な説明を表示するページ

• ジオメトリジャンクヤード
• 非周期的なタイリング
• 決して繰り返されない無限のパターン