前章の最後で触れたように、タイルホモロジー群を用いてもタイリン グ可能かどうかが判定出来ないタイリング問題は存在する。
1990年、J，H．Conway、 J．C．Lagariasの2人は、タイリング問題の判定 に有効な新たな群を考えた［4］。それがタイルホモトピ一群である。
この章ではタイルホモトピ一群を用いてタイリング可能性を判定する ことを述べる。
3．1 新しい状況設定
タイルホモトピー群について述べる前に、新しく状況を設定しなおす こととする。まずこの章での話を進めていくにあたって、正方格子、格 子点、格子点の隣接、セルといった用語については第1章で述べたもの
と同じ定義とする。
ただし議論を簡単にするため、格子図形については、次のように定義
し直す1。
定義3．1．1第1章ではセルの連結な合併集合を格子図形として定義した が、この章ではさらに次の2っの条件を付け加えた図形を格子図形と定
義する。
i）セルとセルが1点のみで繋がる箇所がない。つまり、境界線に分岐 がない。
ii）図形の境界が連結である。
境界に分岐がなく、境界が連結しているので、境界上のどの点から境 界をたどっても、必ず全ての境界上の辺を通り、もとの点へと戻ること
1このように格子図形の条件を厳しくするのは、論証を簡単にするためだけであって、
原論文［4］では単連結な格子図形を全て扱っている。
第3章 タイルホモトピー群 51 になる。つまり、図3．1のように1点のみでセルとセルがつながっている 部分を含む図形や穴のあいた図形は格子図形には含まないこととする。
一 一一一ロー
［b…ト1一一1一一一田一
図3．！：格子図形に含まれない図形の例
格子図形Rを格子図形Tl，．．．，Tnによってタイリングするとき、 Rを 格子領域、Tl，．．．，Tnをタイルと呼ぶことは第1章における定義と同じで ある。また、タイリング問題についても第1章と同じ定義を用いる。
この新しい状況設定のもとで、タイルホモトピー群について考える際 にさらに必要となる定義について述べる。
定義3．1．2隣接する格子点（隣接点）を結ぶ線分を辺といい、α，b∈Zに
対して、（α，b）と（α，b＋1）とを結ぶものを縦の辺、（α，b）と（α＋1，b）とを
結ぶものを横の辺と呼ぶ。辺の1っの端点を始点、もう片方の端点を終点 と呼ぶことにすると、始点から終点への向きを考慮した辺を考えることが 出来る。このように始点と終点を指定した辺を有向辺と呼ぶ。有向辺eに 対して逆向きの辺をe−1と表す。有向辺の有限列e1，e2，＿，enについて、
（eiの終点）＝（ei＋1の始点）（i＝1，．。．，n−1）を満たすとき、これを（有向）
パスと呼ぶ。e1の始点を（Xo，yo）、 eiの終点を（Ui，yi）として、有向パスを
（XO，yo），（Xl， Y1），＿，（ωn，Yn）と書くこともある。このとき、（XO， Yo）をパ スの始点、（Xn， Yn）をパスの終点という。
また、パスに含まれる辺の個数を、パスの長さという。特別なパスと して、長さが0のパスも考え、このパスを空のパスという。空のパスは一 致する始点と終点のみから成る。
以下、単に辺、パスと書いたときはそれぞれ、有向辺、有向パスのこ とを指すものとする。
定義3．1．3パスpに対して、pの終点から始点へとpを逆順にたどる辺 の列から成るパスをp−1と表す。
第3章 タイルホモトピー群 52
定義3．1．4パスe1，．．．，enに対して、 ei＋1＝ei 1となるi （1 f｛ i≦n−1）
があるとき、このパスを可約なパスといい、可約でないパスのことを既 約なパスという。
定義3．1．5パス＠o，yo），＠1，Yl），＿，（Xn， Yn）があって、＠o，yo）＝＠η，yの
であるとき、パスが閉じている（closedである）という。
定義3．1．6i，」を整数として、パス＠o，yo），（Xl， Y1），＿，（Xn， Yn）が、
（Ci，Zli）≠＠♪防）（0≦i＜ゴ≦n）を満たすとき、パスが単純（simple）で あるという。
定義3．1．7閉じたパス（Xo， Yo），＠1，Yl），．．．，（Xn， Yn）が（［Xi， yi）≠（紛，防）
（1≦i〈」≦n）を満たすとき、このパスを辺の巡回列と考えたものを閉 路という。つまり、閉路にはパスの始点や終点が無いと考える。
定義3．1．8格子図形Rの境界上を反時計回りにたどる閉じたパスは閉路 となる。この閉路を、∂Rと表す。
また、Rの境界の辺のうち、 eを最初の辺として、∂Rを閉じたパスと して考えたものを∂R（e）とする。
さらに格子図形Eの閉路∂Rに含まれる有向辺の集合を、△Rとする。
以上の状況設定を踏まえて、タイルホモトピー群によるタイリング問 題の判定を述べていく。
3．2 自由群について
タイルホモトピー群を導入するにあたって、まず自由群について定義
する。
定義3．2．1rを空でない集合とする。 rの流元aに対しその形式的な逆 元を考え、amlと表す。また、 rの元及びその形式的な逆元を形式的に有
限個並べたものをr上のwordと呼ぶことにする。 wがr上のwordであ
るとき、ωは次のように表される。iv ＝＝aS aS2 …aS
ただし、αi∈r， Ei＝±1であり、α1＝aiとする。
第3章 タイルホモトピー群 53 このときのpを、word wの長さといい、［ω1で表す。つまり上の場合、
1zv 1＝pである。また、特別なwordとして、長さが0のwordを考え、こ れを1と表す。
定義3．22r上のwordについて、 word内の元の並びの中で、元αとそ の形式的な逆元α一1が隣り合うとき、このwordが可約であるという。ま た、可約でないwordを既約であるという。
定義3．2．3r上のwordを横に並べたものはまたr上のwordになる。そ
こで、r上の既約なwordを横に並べるという演算（積）を定義したい（演 算子を・で表す）。つまり、r上の既約なwordω1＝αi1α12…虜とω2＝bSlb§2…bGqに対 して、その積を
ωrω・一・11α；2…・卸・おP b1 わS2…わlq
とする。ただしここで、ω1の最後の元とω2の最初の元について、αガP＝
bS であった場合、この単語は可約である。その場合はαガPと碑を消去 した次のword
aS aS2 … aS 一一，i bS2 … beq
をω1とω2の積とする。この操作を簡約という。
さらに、α詳㍗一1）＝碍であった場合はまだこのwordは可約であるので、
・i1α；2…・麗δ蜜…blq
と簡約することができる。この簡約を繰り返すことで、既約なwordを作 ることができる。時に、すべての元が簡約されることもある。そのとき はω1・ω2＝1と定める。さらに、word wと1との積、1とωとの積はと もにwと定める。
r上の既約なwordの集合をア（F）と表す（ただし、1もf（P）に含める）。
このとき、上で述べた積・はf（r）上の2項演算である。このア（r）が、上 記の演算・に関して群であることを示す。
f（r）の元1と任意の元ωについて、iV・1 ＝1・w＝ωと定めたことか ら、単位元1が存在することは自明である。
補題3．2．4．7 （r）の任意の元w＝α11α蔓2…α身に対して、ω一1＝α∬ P・
とおく。このとき、ω｝1はωの逆元である。
ピ しユ α2 α1
第3章 タイルホモトピー群
証明 ∫（r）の任意の元ω＝α11 a蔓2 ・
いての演算を考えると、
54
・aSpとω一1＝α∬ P・・α5Qατqにつ
zv・w−i@＝ aSiaS2 …aSp ・ap−Ep …a2−C2afEi
一・i α12…・賀・α諸1…・牙Qαfq （簡約の繰り返し）
＝1
である。また、
u．，一i@・ w ＝ ap−Ep ・ ・ 一 a2−E2ai fi ・ aCiiaS2 ・ ・ ・ aS
＝α憂⊂P…α牙 2・α蓬2…α参P （簡約の繰り返し）
＝1
であることより補題が示された。
補題3．2．5r上の既約なwordω1，ω2，ω3について、
（Wl・W2）一ZV3 ＝＝ IVI・（IV2・IV3）
o
が成り立つ。
証明 まず、1ω21＝mとし、ω1・ω2を考える際に簡約される回数をα、
ω2・ω3を考える際に簡約される回数をbとする。この証明内では、いく つかの既約なwordを並べて得られるwordが（簡約なしに）既約であると き、この全体として既約なword列の部分に下線をひいて強調して表すこ
とにする。
i）α＝mのとき
ω1の最後のm個の元からなる部分はω2の逆元であるので、1ω11≧0 となる既約なwordを用いてω1＝ωCω2−1と表される。
また、ω2を最後のb個の元の並びとそれ以外に分けて、ω2＝ω砂と すると、ω3＝v−1w5と表される。したがって、次を得る。
（ω、・ω、）・W、一（（ω1ω、一1）・W，）・（V一 ωS）
＝（ω1）・（v一iw6） （3ユ）
第3章 タイルホモトピー群 55
ここで、ω3が既約なので、ガ1蝿も既約である。
一方、
ω、・（W、・W、）一（ω1ω、一1）・（（ωIV）・＠一1ω1））
一 （wlv−iivS一 ） ・ （wSzvS）
一wlv−i・wS （32）
Wlが既約なので、ωCv−1も既約である。
ここで、
・lv−i1≧1であれば、ω1ガ1，v−1妬が疵約であることから、
ωlv−iw§も既約であり、式（3．1）、式（3．2）は共にωlv−iwlとな る。
●lv 1＝0であれば、（ ，wl）・（v−iwS）＝ωlv−1・妬＝wl・w5で ある。
以上から、（ω1 W2）・ω3＝ω1・（W2・W3）であることが分かる。
ii）b＝mのとき
b＝mのときもi）のときと同様に演算を進めていくことで、容易に
（Wl ω2）．ω3＝ Wl・（W2・ω3）が導かれる。
iii）α＜m， b＜mのとき （1）α＋b≦mのとき
1ω21≧α＋bなので、ω2＝u賜u，1ω61≧0，囮＝α， lvl＝うと表さ れる。このとき、ω1＝ωluHi，ω3 ・・ V−iω5と表すことが出来て、
（wi w2） ny zv3 ＝ （（wlu−i）・（iLwSv））・（v−iw6）
＝（婿ψ）・（v−1妬）
一wlwS・wS （3．3）
であり、一方
U］i （iv2 ・ w3） ＝ （w ， u＋ ） ・ （（iL wSv） ・ （v一 wg））
＝（wlu−i）・（測1妬）
一wl ・wS w5 （3．4）
第3章 タイルホモトピー群 56
となる。
ここで、
・1妬1≧1なら、畷妬妬も既約であり、式（3．3），式（3．4）は共 にωi妬蝿となる。
●1ωS1＝0なら、呵妬・ω§＝婿・喝蝿＝ωi・ω§である。
以上から、（11）1 ・ 11J2）・ω3 ・・ IVI・（ω2・ω3）であることが分かる。
（2）α＋b＞mのとき
1ω21〈α＋bなので、ω2＝＝ zcωv， lwl二α＋b−m＞0，
1iL1＝m−b＞o，1vl＝m一α＞oと表される。このとき、
1uω1；α， 1ωvl；bなので、ω1＝ωiω一iu−i， w3＝v−iω一1wSと 表すことが出来て、
（Wl W2）・W、＝（（・］1w−1zL−i）・（塑））・＠一 W一 ω1）
＝ （ivlv） ・ （v−iiv一 wS）
＝ wl−iv iw6 （3．5）
であり、一方
ω1・（ω、・W、）一（ωiガ1ゼ1）・（（・LωV）・＠一 W一 ω1））
＝ （wlw−iiL−i） ・ （uw5）
一＝ wlwfii・w5 （3．6）
となる。
ここで、
・Iw−i1≧1なら、婿ω一1蝿も既約であり、式（3．5），式（3．6）は 共にωlw−1蝿となる。
●lw−il＝oなら、 wl・ω一1蝿＝・ωlw−1・妬… wl・wSである。
以上から、（ωrω2）・ω3＝ω1・（ω2・ω3）であることが分かる。□
以上により、f（r）は群となることが分かる。
補題3。2．5により結合法則を示したので、3っ以上の既約なwordの積に ついて、演算の順番に関係無くどこから簡約をしても同じ既約なwordが 得られることが分かる。特に、可約なwordも長さ1の既約なwordの積と 考えることで、矛盾なくア（F）の元を表していると考えることができる。
第3章 タイルホモトピー群 57
この群∫（F）を、rで生成される自由群という。以下では、 f（r）の演算子の記号・を省いて表記する。また、．7 （F）の元w， w 1をk個並べて演 算したものをそれぞれωk， w−kと表す。
さらに、r＝｛α1，．．．，αm｝であるときは、 f（r）＝∫（α1，＿，am）とも 書く。
定義3．2．6群Gとその部分集合Sに対して、Gの部分集合
〈S＞ ＝ ｛x：i ・・一xan lxi E S， Ei ＝＝ ±1，nE N｝
を考えると、〈S＞はGの部分群である。この〈S＞を、Sが生成するGの部 分群という2。また、Sを〈S＞の生成系、Sの元を〈S＞の生成元という。
定義3．2．7自由群ア（α1，．．．，am）の元ω1，．．．，ωκについて、 f（α1，．．．，αm）
の部分群N（Wl，…ラWk）を
N（lvi，・・．7wh） ＝ 〈｛xivix−ilx E ．T （ai，．．．，a．），i−1，．一，ん｝〉
と定める。
補題3．2．8自由群ア（α1，．．．，αm）の元ω1，．．．， Wkに対して、 N（Wi，．．． ， Wle）
はf（α1，．．，，αm）の正規部分群である。
証明 まず、rl，＿，r、を婦1，．．．，婦1のいずれかとする。 A （Wi，＿，Wk）
の任意の元（Xirixi1）…（X。r。啄1）と、 f（α1，．．．，αm）の元yに対し、
y（xirixii）…（x．r，x．一i）y−i
一施1・1ωf1〃一1）（ 一1． 一1yx2r2x2 Y）…＠。・。啄1）y−1
＝ （yxirixiiyrmi）（yx2r2x2−iymi）… （y ：，r，x，一iy＋i） （3．7）
となる。式（3．7）の右辺における各括弧の中の式はそれぞれN（IVI7＿，IVk）
の元なので、y（Xirixii）…（鞠r。鰐1）ダ1はN（Wl，．．．，ωk）の元である。
よって、任意の．7r一（ab… 7am）の元yに対し、
yN（lvl， ． ． ． ， lvk）y−1 C N（wl， ． ． ． ， lvk）
となるので、yN（ω1，．．．，婦ガ1＝N（ω1，．．．，Wk）であることから補題は 示された。 □ 2S＝｛Xl，＿1Xm｝のとき、＜S＞＝〈τ1，＿，XM＞と書くことにすると、これは定義 2．5，1の非可換な群への拡張となっている。