群論を用いたタイリング問題の判定

全文

(1)平成22年度学位論文. 群論を用いたタイリング問題の判定. 兵庫教育大学大学院. 学校教育研究科. 教科・領域教育学専攻. 自然系コース. M O 8 1 7 4 G. 藤井洋輔.

(2) 1. 目次タイリングについて. Ll. タイリング問題一一．．．．．. 第2章. タイルホモロジー群. 2．1. 符号付タイリングについて．．．．．．．．．. 2．2. 自由アーベル群と符号付タイリング．．．．. 2．3 2．4. タイルホモロジー群行列の単因子．．．．. 2．5. 行列の単因子とアーベル群．．．．．．．．．. 2．6. タイルホモロジー群の計算．．，．．．．．. 2．7. 彩色アルゴリズム．. 第3章. タイルホモトピー群. 3．1. 新しい状況設定．．．．．．．．. 3．2. 自由群について。．．．．. 3．3. タイルホモトピー群タイルホモトピー群がらの準同型．．．．．. 3．4 3．5 3．6. 三角タイリング問題の可能性タイルホモトピ一群による判定．. 5 0 0 0 6 2 4 96 76 97 4 15 16 19 15 25 35 35 45. タイリング可能性を判定する古典的な方法. 1．2. 6 ρ1 00 . 第1章. 謝辞. 83. 参考文献. 84.

(3) 2. はじめに研究の内容タイリングとは、平面上の指定された領域を、指定された有限種類の、単位正方形をつなげた図形であるタイルによって隙間なく敷き詰めるこ. とである。タイリング問題とは、指定された領域とタイルに対してタイリングが可能かどうか、そして可能であるならどうずればタイリングが出来るのかを考える問題である。正方格子平面におけるタイリング問題の判定の方法として、次のようなタイルロの場合を考える。このとき、格子領域を2色で市松模様に塗り分けて不可能性を示す市松アルゴリズムが有名である。他にも、タイルの形によっていろいろな方法が古典的に知られているようである。こういつた判定方法はどのように導かれたのか。そのメカニズムを、タイルホモロジー群を用いた群論によって解明する。さらに、タイルホモロジー群による方法よりも強力で、タイルホモロジ山群による方法では不可能性を示すことが出来ない場合においても適用可能な方法である、タイルホモトピー群による方法について述べる。. 研究の特徴本研究で扱う「タイリング問題」とは、指定された有限種類のタイルを指定された領域へ、タイルが重ならないように隙間なく敷き詰めることが可能か不可能かを考える問題である。このタイリング問題は、ルールさえ理解できれば小さな子どもでも取り組める素朴な問題である。本研究ではタイリング問題を数学的に解決する方法として群論を用いているが、群論の知識がある者にとってその証明のアイデアであるタイルホモトピ一群は非常に単純な発想による解決方法といえる。数学という学問が古くから存在していることや、問題が素朴なものであること、そして群による単純な発想から考えられることから考えれば、このような.

(4) 3. 単純な発想はずっと以前に報告されていても不思議ではないように思える。ところが、本研究で取り上げているこのタイルホモトピー群を用いた解決方法は、1990年にやっと報告されている。多くの人にとって数学はほぼ完成された学問であり、数学における新発見などは非常に難度の高い内容で優秀な数学者にしか成し得ないものであるという固定観念が存在すると思われるのだが、本研究での、それほど難度は高くないと考えられる単純な発想による解決が、最近になってやっと報告されたというこの事実が、この固定観念を払拭するものになるであろうと考えられる。また、第2章でのタイルホモロジー群の計算には行列を用いているのだが、高等学校の学習内容では、行列の内容は以前と比べて縮小されている。物理学や工学、経済学、社会学など様々な分野に応用されている行列であるにもかかわらず、学習当初にはただ行列の計算が出来るというレベルの認識で、それがどういうところに利用できるのかということは頭に残らないこともある。しかし本研究では、タイリングという幾何学的かっ組み合わせ論的な分野の考察に行列を大いに利用している。このことは、行列に対する上で述べたような認識を払拭するきっかけとなるだろう。. 筆者自身、本研究を進めていく上で、こういつた自分の中の数学観の転換が行われていくのが実感できた。また、タイリング問題ではタイルの形や種類の数を変えることで種々の結果が導ける。各自が独自に問題の状況を設定して計算してみることで、より興味深くタイリング問題を探ることが出来る。実際、研究過程では数種類のタイルについて考えてみたのだが、この過程は大変興味深いものであった。こうして自分で問題設定をして自分で解決していく過程を楽しめることもまた本研究の醍醐味である。. 論文の構成以下、修士論文の構成について詳しく述べる。. 第1章「タイリングについて」では、最初にセルや格子図形、タイル T、格子領域R、タイルタイプ集合Σ、そしてタイリングについての定義を行う。格子領域のタイルタイプ集合によるタイリング可能性を、可能であればその例示、不可能であれば不可能性の証明を行うことをタイリング問題という。本論文ではタイリングが不可能である場合の不可能性の証明に焦点を置いて論じている。.

(5) 4. タイリング不可能であることを示す方法としては、総当たり的に場合分けをしながらタイルの置き方を考える方法やタイルの面積と格子領域の面積との関係から示す方法がある。しかし、総当たり的に考える方法は格子領域の面積が大きくなった場合には現実的な方法とは言えない。面積による方法もあまり効果的でないことが多い。そこで、面積が大きくなっても容易に判定出来る古典的な方法の中から、市松アルゴリズムと、セルに数字の1と5を規則的に割り当てる方法を紹介している。第2章「タイルホモロジー群」では、第1章の最後で述べた古典的な判定方法がどういつだ理由で導かれるのかということを、Σによるタイルホモロジー群H（Σ）を用いて示している。タイリングの条件を少し緩めて、タイリングの過程においてはタイル同士が重なること、重なっている部分からタイル単位で1層ずつ取り除くことを許すことにする。そうして最終的に格子領域が1層のタイルで隙間なく埋め尽くされている状態になったとき、符号付タイリング可能であるという。この符号イ寸タイリング可能であるという条件は、タイリング可能であるための必要条件となっている。. 符号付タイリングは自由アーベル群を用いて定式化することが出来る。この自由アーベル群を用いてタイルホモロジー群H（Σ）を定義し、タイルホモロジー群の計算に必要な整数行列の基本変形や行列の単因子論を紹介した後で計算方法を一般化し、さらに具体的な計算例を紹介している。実はこのタイルホモロジー群H（Σ）は、符号付タイリング可能であるための必要十分条件を与えるものである。また、彩色アルゴリズムというタイリング問題の判定方法も紹介する。. 第1章で紹介した古典的な判定方法が彩色アルゴリズムを用いた判定方法の一例となっていることや、タイルホモロジー群H（Σ）も彩色アルゴリズムの1種であることを述べ、彩色アルゴリズムの中でも、タイリング可能であるための最も強い必要条件を与えるものがタイルホモロジー群 H（Σ）であるということも述べている。ところが、実際にはタイリング不可能であるにも関わらず、タイルホモロジ湖心H（Σ）を用いてもタイリン. グ可能性が否定されないこともあるとして、第3章へつなげている。第3章「タイルホモトピー群」では、1990年にJ．H．Conway、 J．C．Lagarias. の2人が考えた、群を用いる新しい判定法であるタイルホモトピー群π（Σ）. について述べている。論証を簡単にするために、第1章での状況設定から少し変えた状況でタイリング問題を考えることにしている。最初にそ.

(6) 5. の状況について整理し、次に、Σによるタイルホモトピー群π（Σ）を導入. するための準備として自由群∫について述べている。その後タイルホモトピー群π（Σ）を定義している。タイルホモトピー群π（Σ）はタイリング. 可能であるための必要条件を与える。次に正方格子上に三角形状にセル. が酉己置された格子領甑と・タイルタイプ集合Σ一［田1によるタイリング問題を考え、これを三角タイリング問題と呼ぶことにしている。. 三角タイリング問題では、タイリング可能であるためのnに関する必要十分条件を求めている。タイルホモトピー群π（Σ）による判定を行う際に、四元数体、群の半直. 積といった知識を用いた。その結果、タイルホモロジー群H（Σ）では否定. 出来なかった三角タイリング問題のタイリング可能性が、タイルホモトピー群π（Σ）によって否定出来た。つまり、タイルホモトピー群π（Σ）の. 方が、タイリング可能であるための真に強い必要条件を与えている。.

(7) 6. 第1章タイリングについてタイリングとは、平面上の指定された領域を、指定された有限種類のタイルによって隙間なく敷き詰めることである。タイリング問題とは、指定された領域とタイルに対してタイリングが可能かどうか、そして可能であるならどうずればタイリングが出来るのかを考える問題である。. 1．1 タイリング問題合同な正多角形で、平面を隙間なく、重ならないように埋め尽くすことを考える。ただし、隣り合う正多角形同士は共有辺が一致することにする。このような平面の分割（以下、格子という）が、正三角形、正方形、. 正六角形を単位とする3種類のみであることは容易に分かる。この3種類のうち、正方形による格子（正方格子）について、用語の定義を交えて述べていく。. 定義1．1．1平面R2内の点pの座標がともに整数であるとき、この点を格子点と呼ぶ。すなわち、格子点全体の集合とはZ2である。2っの格子点 p，qの距離が1であるとき、 pとqは隣接するという。また、4つの頂点がすべて格子点である単位正方形の内部および心寄の点の集合のことをセルという。つまり、セルは、整数i，ゴを用いて、｛（x，y）∈. R21i≦x≦i＋1，ゴ≦y≦ゴ＋1｝と表すことが出来る。これをαi，jと書くこともある。. ここでは、セルに境界を含めて定義した。以下、多角形といえば、これは境界を含むものとする。. 定義1．1．2X⊂R2に対して、 X内の任意の2点pとqを結ぶX内の連続な曲線が存在するとき、Xが（弧状）連結であるという。.

(8) 7. 第1章タイリングについて. Xが有限個の多角形の合併であるとき、弧状連結の定義の「曲線」を「折れ線」に変えても連結性は変わらないことが知られている。つまり、このときは次のように定義を言いかえることが出来る。. 定義1．1．3平面内の有限個の多角形の合併X内に対して、X内の任意の 2点pとqを結ぶX内の連続な折れ線が存在するとき、Xが（弧状）連結であるという。. 定義1．1．4有限個のセルCi（i＝1，．．．，n）の合併集合R＝UlLIQが連結であるとき、これを格子図形という。. 図1．1は格子図形の例である。右端の例のように、1点だけでセルがつながる場合も格子図形に含まれる。. ［コ図1．1：格子図形の例. 格子図形Tl，T2に対して、2つの格子図形Tl，T2に共通に属するセルの和集合をTl∩T2と表すこととする。 Tl∩T2とT1∩T2との違いについヒ . て例を挙げて説明すると、図1．2のように4つのセルからなる2つの格子図形Tl，T2を辺で接して並べたとき、 Tl∩T2＝｛線分ab上の点｝であるが、君∩乃＝のである。格子図形R，Tl，．．．，Tnがあって、 Tl，，．．，Tnにセルをセルに移す平行移. 動（以下、平行移動という）や、セルをセルに移す回転移動（以下、回転移. 動という）等を行って得られる格子図形により、Rを隙間なく重なることなく覆うとき、Tl，＿，TnがRを敷き詰めるといい、そのような敷き詰めが可能かどうかを判定する問題をこの論文では取り扱う。このような問. T2. . T. a. 図1．2：Tl∩ceLI T2とTl∩T2との違いについて.

(9) 第1章タイリングについて. 8. 題を考えるとき、Rを格子領域、 Tl，＿，Tn及びそれを平行移動したもの. をタイルと呼ぶことにする。以下、この問題を詳述する。. 定義1．1．5タイルTに対して、Tを平行移動した格子図形の集合をTのタイルタイプと呼ぶ。つまり、Tのタイルタイプは、｛！（T）1！：R2→R2 は、（x，y）→（x＋i，y＋の（ただしi，」は整数）と表される平行移動｝と表. すことが出来る。Tのタイルタイプを［T］と書く。定義1．1．6タイルTl，＿，Tnに対して、Σ＝∪匙1［Ti］を、 Tl，．．．，Tnのタ. イルタイプ集合という。Tl，＿，Tnのタイルタイプ集合を、［Tl，．．．，Tn］と書く。. 定義1．1．7（敷き詰め・タイリング）タイルTl，．．．， Tnと格子領域Rがあって、次のi）、ii）の条件を満たしているとき、 T1，．．，TnがRを敷き詰め. る、またはタイリングするという。. i）タイルがRを隙間なく埋め尽くす。つまりR＝uLIZである。 ii）2つのタイルは共通のセルを含まない。つまり7迫鐙l Tj＝の（i≠のである。タイルタイプ集合Σ ・＝［Ti，．．．， Tn］と格子領域Rが与えられたとき、Σ. に含まれる有限個のタイルを用いて格子領域Rを敷き詰めることが出来るかどうか、出来るとすればどのように敷き詰めるのかを考える問題のことをタイリング問題という。. ここでは与えられたタイルを平行移動したタイルのみを使ってタイリング問題を考えるように定式化しているが、与えられたタイルTを回転移動やセルをセルに移すように鏡映（以下、鏡映という）した形のタイルも用いてタイリング問題を考える場合は、Tを回転した形・Tを鏡映した形のタイルを用意し、Σの中に含めればよい。この際、記号として、タイルTl，。．．，Tnとそれらを回転させたタイルを含むタイルタイプ集合を［T1，．．，， Tn］R、回転させたタイル・鏡映させたタイルの両方を含むタイルタイプ集合を［Ti，＿，Tn］R，sと書くこととする。. 例1．1．8例として、図1．3の格子領域Rlと図1．4のタイルTlによるタイルタイプ集合［Ti］Rに関するタイリング問題を考える。つまり、Tlを回転および平行移動したタイルでRlを敷き詰める問題である。この場合、タイリングは可能であり、実際図1．5に示すような敷き詰めが存在する。.

(10) 9. 第1章タイリングについて. di 図1．4：Tl. 図1．5：R1の敷き詰め. 図13：Ri. の例例1．1．9例1．1．8と同じタイルタイプ集合［Tl］Rを用いて図1．6に示す格. ﹂一一・十 1 コ塗．＋．L⋮L ：1. 囲﹁﹂一1. 図1．6：R2. 一一一ヒマヰ . @ …. 一一一・一一一一﹂：﹁. ⊥ 「 @田 . ■. 子領域R2を敷き詰めることを考える。このとき、図！．7のセルXlを埋めるには図1．7中央のようにタイルを置く必要がある。このときセルx2を埋めるためには図L7の右のようにタイルを置かねばならない。そうすると、x3のセルの上にタイルを置くことが出来ない。よって、［Ti］Rを用いてR2を敷き詰めることは不可能である。 1 1. ■．⊥一 1. l l. 朋「. 」謡. 図1．7：敷き詰めの過程. 例1，1．10例1．1．9で、タイルタイプの種類に、Tlを鏡映したタイルも含めることにする。すなわち、タイルタイプ集合Σ＝［Tl］R，sとする。この. とき、図1，8のようにしてR2を敷き詰める事が可能である。. 図1．8：［Tl］R，sによるR2の敷き詰めの例.

(11) 10. 第1章タイリングについて. 1．2 タイリング可能性を判定する古典的な方法タイリング問題を考える際にはまず例1．1．8や例1．1．9、例1．1．10のよ. うにして考えるのが最も素朴な考え方である。つまり、タイリング可能な場合は例1．1．8、例1⊥10のようにその方法の例を具体的に示してやればよいし、不可能な場合は例1．1．9のようにして、局所的なタイルの置き方について場合分けを行いながらタイリング不可能であることを示してやればよい。しかし、格子領域の面積が大きくなった場合には、この方法による不可能性の証明は非常に手間のかかる作業になり、あまり現実性のある方法とはいえない。この問題を解決する方法として、つまり格子領域の面積が大きくなってもタイリング問題を判定することが容易に出来る古典的な方法として、市松アルゴリズムなどが知られている。但し、今から述べる判定方法はタイリングが「可能か不可能か」を完全に判定する方法ではなく、タイリングが「不可能であること」の十分条件を与える方法だということに注意する。実際、この判定方法で不可能であることが示せない、と判定されても、それがタイリング可能であると直ちに結論付けることは出来ない。. 市松アルゴリズムとは、その名のとおり格子領域を市松模様、つまり縦横に隣り合うセルは異なる色となるように2色で塗り分けることを用いてタイリング問題を判定する手法のことである。例として、図1．9の、セル2つからなるタイルT3によるタイルタイプ集合［T3］Rを用いたタイリングを考える。この際、T3の面積が2であることから格子領域の面積が2の倍数であることが必要だと分かる。そこで、格子領域R3を図1．10 のように設定する。 1． L 1 ：1 ll ：一一； t ．tl ．t 一. 1 1. 図1．9：タイルT3（面積2）. 図1．10：格子領域R3（面積14）. R3の面積は14であり、これは2の倍数である。しかし、実際には面積が2の倍数であっても敷き詰められない格子領域が存在する。このR3 もその1つである。実際、R3が［T3］Rのタイルで敷き詰め可能か判定す.

(12) 第1章タイリングについて. 11. るために市松アルゴリズムを用いることができる。まず、図Lllのように、R3を白と黒の市松模様に塗り分ける。以下、タイルTに覆われている格子領域R内のセルを、Tの下のセルと表現する。このとき、 T3をR3 上のどこに、どの向きに置いてもT3の下のセルは白と黒が1つずつになる。R3をT3で敷き詰めるとは、 T3が隙間なく重なることなくR3を埋め尽くしている状態なので、T3の下の白のセルの数と黒のセルの数が同じであることから、R3の白のセルの数と黒のセルの数も同じでなければならない。しかしR3の黒のセルは6っ、白のセルは8つとなっているため、［T3］RのタイルでR3を敷き詰めることは不可能であると判定できる。. 図1．11：格子領域R3を市松模様に塗り分ける以上のアルゴリズムを一般化しよう。. 定理1．2．1タイルT及び、！（T）が格子図形となるような合同変換！に対し、正方格子のセル全体を白黒の市松模様に塗り分けたときに、Tのセルが白黒同数になるならば、f（T）のセルも白黒同数になる。証明セルの左下の格子点の座標が＠，y）であるセルをα。，yと表すことに. する。市松模様に塗り分けられた平面には1つおきに同色のセルが並んでいることから、平面上の任意の2つのセルα。，yとαx’，y’について、（x’一 x）＋（yノーy）の値が偶数であればα。，yとα。’，ytは同色であり、奇数であれ. ば異色であることが分かる。ここで、α。，w＝！（α。，y）， a。’，w’＝！（α。・，y・）とする。この2つのセルの色の. 関係も、（z’一z）＋（ωt−w）の値が偶数であれば同色、奇数であれば異色である。 i）！が平行移動のとき、！（a。，y），！（αx，，y，）は整魏，」を用いてαx＋乞紛ゴ，α。t＋曜＋ゴ. と表される。すると、｛（x’＋i）一（x＋i）｝＋｛（y’＋の一（y＋の｝＝＠’一x）＋（ヅー y）より、＠’一 x）＋（ヅーy）が偶数（奇数）ならば｛＠ノ＋の一＠＋i）｝＋｛（y’＋の一（y＋の｝も偶数（奇数）であるので、.

(13) 第1章タイリングについて. 12. αx，yとα。t，y・が同色（異色）ならf（α。，〃）と！（α。，，y，）も同色（異色）であ. ることが分かる。 ii）！がX軸に関する鏡映のとき、！（ax，y），！（α。・，Y・）はa。，一（y＋1），α、，，，一（y，＋1）. と表される。すると、（ゴーx）＋［｛一（y’＋1）｝一｛一（y＋1）｝］＝（x’一 x）十（一2／十y）＝（xノーx）十（2／一y）十2（一！／十y）より、（x’一x）十（！／一！ノ）. が偶数（奇数）ならば（〆一x）＋［｛一（y’＋1）｝一｛一（y＋1）｝］も偶数（奇数）であるので、α。，yとαx’，y’が同色（異色）ならf（％〃）とf（α。，，y，）も. 同色（異色）であることが分かる。 iii）！が原点を中心としてgo度の回転のとき、ノ（α、，，〃），！（αx・，〃’）はα一（、J＋1），。，. α一（〃，＋1）〆と表される。すると、［｛一（y’＋1）｝一｛一（y＋1）｝］＋（ゴー勾＝（x’一x）十（一3〆十y）＝（xノーx）十（2／一y）十2（一L〆十2ノ）より、（xノーx）十（2／一！ノ）. が偶数（奇数）ならば［｛一（Zlt＋1）｝一｛一（y＋1）｝］＋＠’一x）も偶数（奇数）であるので、αx，yとα。・，y’が同色（異色）なら！（％“）と！（α。’，Y・）も. 同色（異色）であることが分かる。. セルをセルに移す一般の合同変換！は平行移動・x軸に関する鏡映・原点を中心とした90度の回転の合成で表すことが出来るので、i）∼iii）から αx，〃とα。，，ytが同色（異色）ならば！（α。，y）とf（α。，iY、）も同色（異色）である. ことが分かる。. このことから、ある1つのセル。と変換後のセルン（c）が同色であった場合、すべてのセルは！によって同色のセルに移る。一方、1つのセル。と変換後のセルン（c）が異色であった場合、すべてのセルは！によって異色のセルに移る。 T・・＝ul＝1ei（Ciはセル）を！によって変換したタイルは！（T）＝uL1！（Cの. であることから、！が同色のセルに移す変換であった場合はTの下のセルが白黒同数であればf（T）の下のセルも白黒同数である。fが異色のセルに移す変換であった場合も、Tの下のセルが白黒同数であれば、 Tの下の白（黒）のセルは！（T）の下の黒（白）のセルに移るので、色が反転するだけで白黒同数のままである。. 以上より、Tの下のセルが白黒同数である場合は、 f（T）の下のセルも. 白黒同数となる。 □ この定理1．2．1を用いることで、先に述べた市松アルゴリズムを一般化することができる。.

(14) 13. 第1章タイリングについて. 定理1．2．2（市松アルゴリズム）タイルTl，．．．，Tn、格子領域Rに対して、白黒の市松模様に塗り分けた格子上でTl，．．．， Tnのセルが白黒同数になるとき、［Ti，．．．，Tn］R，sのタイルがRを敷き詰めるならば、 Rも白黒同. 数に塗り分けられている。証明定理L2，1より、Tl，＿，Tnの下のセルが白黒同数ならば、［Ti，、．．，Tn］R，s. の任意のタイルの下のセルも白黒同数であることが分かる。よって、ITi，．．，Tn］R，s. のタイルがRを敷き詰めるならば、Rのセルも白黒同数になる。ロ市松アルゴリズムが有効な場合もあるが、当然のことながらタイルのセルが白黒同数とはならないときは市松アルゴリズムは使えない。また、市松アルゴリズムはかなり弱い必要条件しか示せない。実際、セルが白黒同数となるタイルとして、例1⊥8のタイルTl（図1．12）を用いて考えてみる。タイルタイプ集合は［Tl］R，sとし、格子領域を図1．13. の面積60の長方形R4とする。. 図L12：Tl 図1．13：6×10の格子領域R4. 図1．14：市松模様に塗り分けたR4（左）と、 Tlの置き方（右）. このとき、Tlの白と黒のセルは図1．14のように同数だが、 R4もセルは白黒同数になるので、定理1．2．2を用いても、敷き詰め不可能だとは示す.

(15) 14. 第1章タイリングについて. ・ . 一 . 一 . 一 . 一. 一 . 一 . 一 . ﹁ . ｝. 一 . 一 . 一 . 皿 . ［ . 1一5一1一5一1一5 ．．L．．．﹁1﹂ILII﹂： 1一一5 一1一5一1一5 1一5⋮1一5一1一5 1LIIτ1←IIT’﹁↑1． 1一5一1一5一1﹁5. 一 . ︸ . レガゴ駅−駅. 一 . 一 . 」. 一. 鴎臥. 1⊥−IT一←一⊥II＋1．. 一 . 一．III司II﹁1↓1．. 1 5一1一5﹁1一5 1一5一1一5一1皿5 1一一5 一1一5一1皿5 一﹁ 1︼5一1﹁5﹁1﹁5. 1一51一5一1一5. 皿. 一. 図1．15：R4のセルに数字を割り当てる −一︻U. 5 5. 図1．16：Tlの置き方の例. ことが出来ない。だからといって、敷き詰め可能であるとは結論付けられない。そして実際、敷き詰めば不可能なのである。このことは市松アルゴリズムとは別の方法を用いて示すことが出来る。. 例1．2．3図1．13の格子領域R4を図1．12のタイルTlのタイルタイプ集合［Tl］R，sを用いて敷き詰めることを考える。. まず、図1．15のようにR4の上から奇数番の行にあたるセルにはすべて 1を割り当て、偶数番の行にあたるセルには5を割り当てる。. 各セルに1または5が割り当てられたR4の上にTlを置き、そのとき Tlの下のセルに割り当てられた数の合計を考える。 Tlの置き方は位置を気にしなければ回転・鏡映・下にくる1または5の数のパターンを考慮すると！6通り考えられるが、Tlの置き方によらず、 Tlの下の全てのセルに割り当てられた数の和は8または16になることが、図1．16から容易に確かめられる。このことから、TlがR4を敷き詰めるためには、 R4のセルに割り当てられた全ての数の和が8の倍数でなければならないことが分かる。ところが、R4のセルに割り当てられた全ての数の和は180であり、これは8の倍数ではない。よって、TlがR4を敷き詰めることは不可能であると結論付けることが出来る。この例1．2．3のような方法をとることでこの問題では確かにうまく判定. することが出来たが、この図1．15のような数の割り当てはどのようにして得られるのであろうか。その系統立った考え方を次章で述べる。.

(16) 15. 第2章タイルホモロジー群この章ではタイルホモロジー群について述べる。前章で述べた市松アルゴリズムや数字を各セルに割り当ててタイリングの必要条件を求める方法はこのタイルホモロジー群を用いて導くことが出来る。前章で述べたタイリングよりも、条件を少し緩めた符号付タイリングも取り上げる。実は、タイルホモロジー一E＄は、符号付タイリングが可能であるための必要十分条件を与えるものである。. 2．1 符号付タイリングについて第1章で述べたタイリングでは、タイルが重ならないようにしてタイルで格子領域を隙間なく埋め尽くした。今回は埋め尽くす際の条件を少し緩めて、タイリングする過程ではタイルが重なること、さらに重なっている部分からタイル単位で1層ずつ取り除くことを許すこととする。そして最終的に格子領域が1層のタイルで隙間なく埋め尽くされている状態になったとき、これを符号付タイリング可能と呼ぶ。以下、このことについて詳述する。定義2．1．1タイルタイプ集合をΣ ＝＝［Ti，．．．，Tn］とおく。写像ω：Σ→Z. があって、ω（T）≠0となるTが有限個であるとき、写像ωを（タイルの）配置という。. 配置ωとセル。に対して、cが属するようなタイルTそれぞれに対するωのの総和Σωのを酒己置ωのセル。における重なり数と呼ぶこ ccT とにする。. 定義2．1．1における配置の意味であるが、タイルT∈Σに対してw（T）. は、Tを何枚重ねて配置するかを表していると考えることが出来る。しかし、ここではω（T）の値として負の値も許されており、ω（T）＝一1と. はTを1層取り除くことを示している。またこのときセル。における重.

(17) 第2章タイルホモロジー群. ！6. なり数は、配置ωでタイルを置いたときに、cの上に何枚タイルが置かれているかを表している。. 定義2．1．2（符号付タイリング）タイルタイプ集合Σ、格子領域Eに対し. て、配置ω：Σ→Zがあって、セル。が格子領域Rに属するときは。での重なり数が1、セル。が格子領域Rに属さないときは。での重なり数が 0であるとき、RはΣのタイルで符号付タイりング可能であるという。定義L1．7のタイリングの記述と今回の符号付タイリングの記述は一見違う内容にみえるが、この符号付タイリングの特別な場合として、第1章で述べたタイリングがある。通常のタイリングでは敷き詰める過程においてタイルが重ならないことから、ω（T）が2以上になることはない。また、タイルを取り除くことも無いため、w（T）は負の数をとらない。このことから、タイリングを、符号付タイリングの表記を用いて次のように表すことが出来る。タイルタイプ集合Σ＝［Ti，．．．，Tn］のタイルSl，．．．，Smが格子領域Rを. 敷き詰めるとする。このとき、配置ω：Σ→Zを、 w（T）一＝（6 EZ；gi．si−i・・…一）（，．，）. と定めると、これは符号付タイリングの特別な場合となる。つまり、符号付タイリング可能であることは、タイリング可能であることの必要条件となっている。よって次の定理を得る。. 定理2．1．3タイルタイプ集合Σ、格子領域Rに対して、RがΣでタイリング可能ならば、RがΣで符号付タイリング可能である。. 2．2 自由アーベル群と符号付タイリング符号付タイリングは自由アーベル群を用いて定式化することができる。群についての基本的な定義は既知として、以下自由アーベル群の定義から始める。. 定義2．2．1（自由アーベル群）Sを集合とする。Sの元の整数係数の形式的な1次結合の全体をA（S）とする。つまり、 A（s）一｛li，1． k・sPiC・・ z 一（f・， k・・・となる・1潮固｝.

(18) 第2章タイルホモロジー群. 17. である。また、A（S）∋α＝Σ、∈s k。sに対して、全ての係数k、が0のと. き・α一〇と書く・さらに・A（s）の2元・α一Σk。・，β一D。・に対. sES sES して、 cu ＋5 ＝ 2（ks ＋ ls）s. sES −a 一 2（一k，）s. sES と定義すると、k，＋∼、≠0となるsは有限個なので、”＋”はA（S）上の. 演算となり、0を単位元、一αをαの逆元とするアーベル群となる。この A（S）を、Sで生成される自由アーベル群という。 Si E S（i＝1，＿，n），α＝Σ k。sにおいて、 s＝Si（i ＝＝ 1，＿，n）を除. いてん。＝0のとき、α ・＝ k，、Sl＋…＋k。。Snとも書く。（係数が±1のとき. は、1を省略することもある。）. この自由アーベル群を用いて、符号付タイリングを定式化する。まず、セルの集合をOellと書くことにし、 Oellで生成される自由アーベル群A（Oeのを考える。以後、 A ・ A（Oell）と表記する。つまり、．4の元は一般に、. Σ秘幽 i，ゴ. と表される。但し、α瑠はセル（セルの表記は定義LL1を参照）であり、島，ゴ∈Zで幅≠0となる（i，のは有限個である。. タイルを配置したとき、各セルに何重にタイルが置かれているかを考えるが、Aの元はこのときの状態を表すものと考えることが出来る。実際、配置ωに対して、砺をwのα吻における重なり数と定めると、Aの元α＝Σ傷，ゴα乞，ゴは、ωの配置で各セルα乞，ゴに何重にタイルが置かれてい. るかをうまく記述する。. さらに、タイルタイプ集合Σの元であるタイルTを次のようにAの元と考える。Tは、 Tに属するセルの（連結な）合併集合であるが、 T＝ Σ。、，j⊂Tα吻∈AというようにAの元と同一視する。また、格子領域Rも. 同様に、R＝Σai，」⊂Rαり∈Aとおく。このように、タイルTや格子領域. Rもこの章ではAの元として考える。定理2．2．2タイルタイプ集合Σ、格子領域Rに対して、RがΣで符号付タイリング可能であることと、R＝ΣL1島町∈Aとなる島∈Z，Ti∈Σ が存在することとは同値である。.

(19) 第2章タイルホモロジー群. 18. 証明定義2．1．1及び2．1．2より、RがΣで符号付タイリング可能である. ことは、ある配置ω：Σ→Zを用いて. 蕊姻一他1：1調と表されるということである。これを用いると、Aの元であるRを次のように表すことが出来る。. 耳レの）鰯伽）一ΣΣ（ω（T）・・，」）. i，jai，J⊂T. 一向の儒→ 圃一Σω（T）T∈A T∈Σ 式（2．2）から式（2．3）までの式変形であるが、どちらもセル％及びαi，j. を含むタイルTの組合せについて和をとっており、和のとり方の順序の変更を行っている。結局、RがΣで符号付タイリング可能ならば、 Rは Σの元の1次結合で表される。一方、R＝Σ篠1ん遇∈．4のとき、 Rは次のように表される。れ R一Σk，T，. 一漁→. 飢忍→％御）式（2．4）における式変形は、式（2．2）から式（2．3）までの式変形と同様の. 変形である。そこで、. ω（T）一｛8翻.

(20) 第2章タイルホモロジー群. 19. のように配置ωを定めると、式（2．4）より. 溜一儲：1調であるので、この配置wで、RはΣによって符号付タイリング可能である。. D 2．3 タイルホモロジ一群前節で述べたように、符号付タイリングは自由アーベル群を用いて定式化することが出来る。ここで、タイルホモロジー群と呼ばれる群を次のように定義する。. 定義2．3．1Σをタイルタイプ集合とする。セルの集合で生成される自由アーベル群Aの部分群B（Σ）として、 B（￡）＝（＃．， kiTilki E Z， Ti E ￡，n〈 oo） c ．4. 1＝1 を定義する1。Aは可換なので、 B（Σ）は正規部分群でもある。さらに、AをB（Σ）で割った群（商群）A／B（Σ）を考え、 H（Σ）ニA▽B（Σ）. と書くことにする。H（Σ）をタイルホモロジー群という。 Aの元αに対し、αを含むH（Σ）の元α＋B（Σ）を石と表す。. 符号付タイリングと自由アーベル群の関係に商群H（Σ）を用いると、次の定理が成り立つ。. 定理2．3．2タイルタイプ集合Σ、格子領域Rに対して、RがΣに符号付タイリングされるということとR＝6∈H（Σ）であることは同値である。証明 R＝OG H（￡） oRE B（E） oR＝2kiTi E ．／t （kt c Z， Tt E ￡，n〈 oo）. t＝1. よって、定理2．2．2より、主張が成り立つ。 □ 1つまり、B（Σ）はタイルで生成されるAの部分群である。（定tc 2．5．1を参照）.

(21) 第2章タイルホモロジー群 20 この定理2．3．2により、符号付タイリングの可能性は、タイルホモロジー群H（Σ）の計算を用いて判定することができる。次に、タイルホモロジ一群H（Σ）＝・・A／B（Σ）の具体的な計算をする上. で必要な次の定理を用意する。. 定理2．3．3アーベル群Aとその部分群B、さらにその部分群0、つまり A⊃B⊃0である群に対して、．4／B or（A／0）／（B／σ）が成り立つ。. 証明ここでは、α∈Aに対するA／0の元を回と表し、さらに［a］に対する（A／0）／（B／0）の元を［回］と表すこととする。つまり、［a］一＝ a＋C ［［a］］一［a］十B／C一（a十C）十B／C である。. ここで、次のような写像！を用意する。 f i A／B 一（A／C）／（B／C）. a＋BHf（a＋B）＝＝［［a］］. この写像！が同型であれば定理は証明される。よって、！がWell−Dcfined. であること、準同型であること、全単射であることを順に述べていく。 Aの2元α，α’について、α＋B＝α’＋Bであるとする。このとき、 a十B＝ a’ 十Boa一 a’ EB であるので、b＝α一α’∈Bとすると、［αト［α’］一［α一α’1一［b］∈B／0 よって、［［α］］＝［［a’］］であるので写像！はWell−Definedである。. また、 f（a ＋ B）＋ f（a’ ＋ B）一［［a］］＋［［a’］］一［［a］＋［a’］］一［［a ＋ a’］］. 一ア（（α＋の＋B））一＝ f（（a ＋ B）＋（a’ ＋ B））. となるので、写像！は準同型である。 fの定義より、！は明らかに全射であるので、単射であれば！は同型である。.

(22) 第2章タイルホモロジー群. 2！. A／Bの2元α＋B，α’＋Bに対して、！（α＋B）＝！（αt＋B）とすると、 f（a ＋ B）＝一 f（a’ ＋ B）｝［［a］］一＝［［a’］］ E （A／C）／（B／C）. ⇒回一同＝［α一α’1∈B／o ⇒1α＿a’］＝［b］∈B／σと書ける。（b∈B）＝〉 a一 a’ ＝b＋c （b E B，cE C）. σの元はBの元でもあることから、α一α’∈Bとなり、. a＋B＝a’＋BEA／B となるので、！は単射である。. 以上から、！は同型であるので、A／B窪（A／0）／（B／0）である。 □. Aは生成元が無限個ある自由アーベル群であるが、定理2．3．3を用いると、タイルホモロジー群H（Σ）＝ノ1／B（Σ）を有限生成な群の中で考えることができる場合も多い。この節では以下、ある具体的なタイルホモロジー群の計算の例を挙げる。. 例2．3．4格子領域Rが、タイルタイプ集合Σ＝1＝コ］Rで符号付タイリングされるための条件を考える。. この場合、Σの各タイルは、セルα乏，ゴの1次結合である．4の元と考えると、整数乞，」を用いてそれぞれαi，ゴ＋αi＋1，ゴ，αi，ゴ＋α乞，ゴ＋1と表される。. Σのタイルを縦に1つ置き、セルが1つ重なるように横向きのタイルを 1つ取り除くことでR1 ， R2を定める。（図2．1）. R1・. mlll一出遁』，R・・ill日一西・’ 図2．1：R，， R2. この図における”＋”，”一”という記号はAの元と考えたときのセルの. 係数で、”＋”のセルにおける係数が1、”一”のセルにおける係数が一1. であることを示している。Rl，R2及びそれらを平行移動させたもので生成されるAの部分群を〈Rl， R2＞Tと表すことにする。 Rl，R2及びそれらを平行移動させたものはB（Σ）に含まれるので、〈Rl，R2＞TはB（Σ）の部分群である。A⊃B（Σ）⊃〈Rl，R2＞Tであるので、定理2．3．3より H（X） or （A／〈R，， R，〉．）／（B（Z）／〈Ri， R2＞T）. として考えることが出来る。.

(23) 第2章タイルホモロジー群. 22. そこで、以下ノ1／〈Rl， R2＞T， B（Σ）／〈Rl，R2＞Tについて考える。この際、. ．4の元αに対するA／〈R1， R2＞Tの元を［α］と書くことにする。. ここで、次の補題を得る。補題2．3．5例2．3．4において、Aの元Σ￠諮乞4％がくR1，R2＞Tの元であることと、. Σ暢一Σ編一〇（2．5） i＋ゴ＝偶数 i＋ゴ＝奇数. であることは同値である。このΣ，＋j一偶数幅，Σ殉＿奇数κ乞4はそれぞれ、Rを白黒の市松模様に塗. り分けたときの、白のセルの係数の和、黒のセルの係数の和となっている。. 証明Rlの左上のセル％＋1と右下のセルαi＋1，ゴについて、 i＋O＋1）が奇数（偶数）であれば、（i＋1）＋ゴも奇数（偶数）である。また、それぞれ. のセルの係数は＋1と一1なので、式（2．5）を満たす。R2においても同様に、式（2．5）を満たす。. このように、Rl，R2が式（2．5）を満たすので、 R1，R2を平行移動したものも同様に式（2．5）を満たす。また、Aの元α，βが式（2．5）を満たすとき、明らかにα＋β，kcu （kは整数）も式（2．5）を満たすので、 Aの元Rl，R2. 及びその平行移動したもので生成される群〈Rl，R2＞Tの元も式（2．5）を満たす。. 一方、α＝L諮乞4α留が式（2．5）を満たすとする。このとき、群A／〈R1，R2＞T において、 ai，」＋1 一 ai＋1，」 E 〈Rl， R2＞T c A より、［ai，o・＋i］一［ai＋i，j］＝［0］ E A／〈Ri， R2＞T. となるので、［ai，o・＋i］＝：［ai＋i，」・］EA／〈Ri，R2＞T （2．6）. である。同様に、［αi＋1，ゴ＋1］＝［α嗣∈A／〈Rl，R2＞T. （2．7）. である。式（2．6）、式（2．7）より、平面での斜め方向のセル、つまり市松模様. に塗り分けた平面において、白のセル、黒のセルはそれぞれA／〈Rl，R2＞T.

(24) 第2章タイルホモロジー群. 23. の中では等しくなるので、［αo，o］＝［αn，m］（n＋m＝イ禺数）. （2．8）. ［αo，1］＝［αn，m］（n＋m＝奇数）. （2．9）. を満たす。よって、α∈．4が式（2．5）を満たすときに、. ［α］一［昇剣. 一瞬蜘轟緬］. （2．10）. ＝［O × ao，o ＋O × ao，i］. 一［o］ E v4／〈Ri， R2＞T ［コ. となることから、［α］＝［0］であるので、α∈〈Rl， R2＞Tとなる。. この補題2．3．5により、次の補題を導くことが出来る。補題2．3．6例2．3．4において、次が成り立つ。 A／〈Ri， R2＞T or Z × Z. 証明補題2．3．5の証明の式（2。8）、式（2．9）より、．4／〈R1，R2＞Tの元は整. 数∬謝を用いて ∬［α。，。］＋ッ［α。，、］. と表される。また、 X［α。，。］＋y［α。，1］一X’［α。，。］＋y’［α。」. とすると、 X［α。，。］＋y［α。，、］＝X’［α。，。］＋y’［α。，・］ x［α。，。］一x’［α。，。］＋y［α。，、］一y’［α。，1］＝［0］. ＠一x’）［α。，。1＋（y一 y’）［α。，、1一［0］. （￠一画。，。＋（y−y’）α。，1∈〈Rl，R・＞T. となるので、補題2．3．5より、ノノ. の＝：「，シ＝㌢.

(25) 第2章タイルホモロジー群. 24. である。以上より、A／〈Rl，R2＞Tの元は一意的に x［ao，o］＋ y［ao，ll. と表すことができる。. そこで、次のような写像fを用意する。 f ， A／〈R，， R2＞T 一Z × Z x［ao，o］＋ y［ao，1］ H一〉 f（x［ao，o］＋ y［ao，1］）＝（x， y）. x［αo，o］＋y［αo，1］という表し方は一意的なので、 fはWell−Definedで全単. 射である。また、準同型であることも容易に確かめられる。 □ 命題2．3．7例2，3．4におけるタイルタイプ集合Σ及びRl，R2に対して、 B（Σ）／〈Rl， R2＞Tは、 A／〈Rl， R2＞Tの元［αo，o＋αo，1］によって生成される。. つまり、B（Σ）／〈Rl，R2＞T＝｛k［α0，0＋αO，i｝lk∈Z｝となる。. 証明 B（Σ）／〈Rl，R2＞Tの元［α］について、αがB（Σ）の元であることから、［a］＝［＃．， kiTi］（ki EZ， Ti E 2），n〈 oo）. と書ける。Ttは隣り合うセルの集合であることから、 z一｛鮒触（Tl一斗のとき）αi，ゴ＋αi＋1，ゴ（Tt＝□のとき）. と表される。このことから、式（2．8）、式（2．9）によって［Ti］＝［αo，o＋αo，1］. となるので、回は次のように表される。. ［α1一［書周一書軸一シ㎞＋a・，・］. ここで、k＝Σ匹1島とおくと［a］＝ k ［ao，o ＋ ao，i］ E B（X）／〈Ri， R2＞T （k E Z）. となる。つまり、［α］は［αO，0＋αO，1｝の整数倍で表すことができる。一方、｛k［α0，0＋α0，1］「k∈Z｝の元k［aO，O＋αO，1］について・αO，O＋α0，1は. タイ，レロを表しているので、これはB（Σ）の元である．. 以上により命題が示された。 □.

(26) 25. 第2章タイルホモロジー群. この命題の結果から、A／〈R1，R2＞T窪Z×Zの同型により、B（Σ）／〈Rl，R2＞T. は｛（k，k）lk∈Z｝⊂Z×Zに移ることが分かる。. このことを用いると、次の定理が導かれる。定理2．3．8例2．3．4において、格子領域Rがタイルタイプ集合Σニ「コ］R. で符号付タイリングされるための必要十分条件は、R内のi＋」が偶数となるセルα留の数とi＋」が奇数となるセルα乞4の数が等しいことである。. 証明定理2．3．2から、RがΣで符号付タイリングされることは R−OE H（￡）と同値である。 R 一 O E H（X）一（A／〈R，， R，〉．）／（B（Z）／〈Ri， R2＞T）. は、. ［R］∈B（Σ）／〈R、，R2＞T一く［α。，。＋α。，1］〉. ということであり、［珂一k・［α。ρ］＋k2［α。，、］. と表すとき、kl＝k2であることを意味する。これは，式（2．10）で見たように、i＋」が偶数となるセルα昭の数とi＋」. が奇数となるセルαりの数が等しいということである。［］. つまり、第1章で述べた市松アルゴリズムにおける、白黒のセルが同数であるという条件は、タイルホモロジー群の中でRが6になるという条件を表しており、符号付タイリングが可能であるための必要十分条件となっている。. 2．4 行列の単因子例2．3．4ではタイルの具体例を挙げて符号付タイリング可能な格子領域. の条件を求めた。では、タイルの形を一般化した場合にはどういつだ方法でタイルホモロジー群が求められるのかを考える。この節では、そのために必要となる線形代数の知識を述べることにする。まず、整数基本行列を用意する。.

(27) 第2章タイルホモロジー群 26 定義2．4．1次の3種類のn次正方行列Rゴ，Q，，凡謎を整数基本行列という。. 馬（i≠のは、単位行列のi行目と」行目を取り換えた行列、Q乞は、単位行列の（i，の成分を一1に変えた行列、凡瀞（i≠のは、単位行列の（i，の成分を整数鳶に変えた行列である。つまり、Pi，j，Q，，凡謎は次のような行列である。. 1. 0. o 1. 0. 01. 乃，ゴ＝. 10. 1. 0. 1. o 1. o. 1 （i ；／3 1SiS n， 1S ］’ 〈一 n）. 1. o 1. Q，＝＝. （1 SiS n）. 一1. o. 1. 1.

(28) 27. 第2章タイルホモロジー群 1. k Ri，ゴ，k＝. 0 1. 齢旨躍1森ご？細 n行m列の整数行列に、右からm次整数基本行列をかける操作を列基本変形、左からn次整数基本行列をかける操作を行基本変形という。つまり、列（行）基本変形とは、Pi，」’の形の行列による2つの列（行）を入れ. 替える操作か、Q，の形の行列による1つの列（行）の符号を変える操作、またはRi，j，kの形の行列によるある列（行）にほかの列（行）の整数倍を加. える操作である。これらをまとめて（整数行列の）基本変形と呼ぶ。. この定義より、整数基本行列の行列式は士1である。整数行列に対して基本変形を行うことで、次の定理が導ける。定理2．42（行列の単因子）n行m列の整数行ijlJ Aに対して、. 0. al. a2. SAT ＝. ar. 0. o. o. 儲謡棚繋激耐㍗愁謙切る）となる整数基本行列の積S，Tが存在する。このときの0以外の成分α1，α2，．．．，αrを、行列Aの単因子という。.

(29) 28. 第2章タイルホモロジー群. 証明 A＝0のときは明らかにS，Tはどんな整数基本行列でもよいので、 A≠0の場合で考える。A； A，とおく。 i）A1に基本変形を行って出来る全ての行列の全ての成分のうち、 oを除いて絶対値が最小のものをd1とする。 Pi，ゴ及びQ，の形の行列による基本変形により、d1を正の数にして（1，1）成分へ移動させる。. 、. 〆l111. A1茎杢変玖＊ノ. ＼. このとき、1行、1列の成分は全てldllの倍数である。なぜならば、仮に1行、1列の成分の中にIdllの倍数でない数kld，1＋α（k∈Z，0＜ α〈1di1）があったとすると、基本変形によりkld11＋αはαへと変換することができる。このとき、0＜α＜Iclilなので、絶対値が最小のものをdiとしたことに矛盾する。凡，殖の形の行列による基本変形を用いて、1行、！列の（1，1）成分以. 外の成分をすべて0にする（掃き出し）。このとき、1行、1列を除いた行列をA2とする。自dll. 0. o＼. 0. ・42. ノ. 雛 kl. A2の成分は全てldilの倍数である。何故ならば、仮にA2の成分の中に1di1の倍数でない数kld，1＋α（k∈Z，0〈α〈1di1）があったと. すると、次の2度の凡，齢の形の行列による基本変形によりkld11＋α はαへと変換することができる。.

(30) 29. 第2章タイルホモロジー群 0. 14．1. 0. 0. 0. 0. 0 ：. 0. 鳶1411＋α. 0 ld．1. 0. 0. ld．1. ・ 0. 0. 0 列基本変形. 一. 0. んld、1＋α. 0 ld．i. 0. 0. ld．1. 0. 0. 0 行基本変形. 一. 一κld、1. α. 0. このとき、0＜α＜1di lなので、絶対値が最小のものをdlとしたことに矛盾する。. ii）A2に対して、 i）と同様の変形を行い、1行、2行、1列および2列を. 除いた行列をA3とする。 r14・1. o o、. 〆1ゴ110. 0. O ld2【. k6. 璽. 0 … 0. 0. ・43. ノ. ・42 ノ. ・ o、. ko o. A2に基本変形を行っても、 A2の成分は全てIdilの倍数のままであるため、1d21は1dilの倍数である。.

(31) 第2章タイルホモロジー群 30 以下、i）、 ii）を繰り返していき、 A，＝O（1≦i≦min＠，m））となるか、. Aiが無くなるまで繰り返し、最後に、α1＝［dil， a2＝ld21，＿，αr＝1d，1 とすればよい。. この際に、行基本変形に用いた整数基本行列の積がSであり、列基本変形に用いた整数基本行列の積がTである。 □. 2．5 行列の単因子とアーベル群定理2．4．2を用いて、アーベル群の商群を計算することを考える。そのために必要となる用語と記号を最初に定義する。定義2．5．1＋を演算とするアーベル群Aの元a1，．．．，amに対して. ｛k・a・＋…＋km・謳，…，編は整数｝で表される集合は、Aの部分群となる。この群を、a1，＿，amで生成される部分群といい、〈al）．．．，am＞で表す。. この定義を用いて、補題を4っ述べる。補題2．5．2znの元a1，．．．，amに対して、次が成り立つ。 Zn／〈ai，．．．，a．〉＝ Z”／〈ai，．．．，a」一i，a」＋ kai，a」＋i，…，arn＞（k E Z，i 7E 」， 1 f｛ i s｛ p， 1 ：｛：」〈一 p）. 証明 a’＝aゴ＋kaiに対して、. a’一aゴ柄a乞 aj ＝ a’ 一 kai より、〈al，・一一，a．〉＝〈al，・・．，ao・一1，at， ao・＋1，．．．，a．〉（2．11）. であるので成り立つ。 □.

(32) 第2章タイルホモロジー群 31 補題2．5．3m個のznの元（縦ベクトル）を並べたn行m列の整数行列 A＝（a1，＿，am），B＝（b1，．．．，bm）について、整数基本行列の積Tを用いて. B＝AT と表されるとき、次が成り立つ。 zn／＜a・，＿，am＞ニzn／〈b1，＿，bm＞. 証明行列ATはAに列基本変形を次々と行った行列である。そこで、 T・Tl…Tp（T1，＿，Tpは基本行列）とし、 AにTlからTiまでを順に右からかけた行列を、 ATi …Ti 一（aii），．．．， a，S（S））. と表すことにする。このとき、（aii），＿，a卿）＝（aii−1），＿，a鏡一1））Tiより、（alの，．．．，a幻）は、. （aii−1），．．．，a鋤1））の縦ベクトルを並び替えたものか、1つの縦ベクトルの. 符号を変えたもの、または補題2．5．2のように1つの縦ベクトルにほかのベクトルのスカラー倍を加えたものである。よって、補題2．5．2の式（2．11）より、〈ai’一1），＿，・Sri）〉＝＝〈ai’），．．．，・鋤. であるから、〈ai，・一．，a．〉＝〈aSi），．．．，afi（i）〉. 一〈ai2），．．．， aA’）〉. 一〈aiP），．．．，ashP）〉＝〈bi，…，bm＞. である。以上より、zn／〈al，… ， a．〉＝zn／〈b1，＿，bm＞が示せた。 □. 補題2．5．4整数n次正則行列で、行列式が土1であるものをAとする。このとき、次の写像！は同型である。 f：zn 一〉 zn x H一〉 f（x）＝ Ax （x E Z”）.

(33) 第2章タイルホモロジー群. 32. 証明！が準同型であることは明らかなので、！が全単射であることを示. す。写像が全単射であることと、写像に対して逆写像があることは同値であることから、！の逆写像があることを確かめる。、4−1が整数n次正則行列であれば、次の写像gが定まる。 g：Zn 一〉 zn x H g（x）＝＝ A−ix （x E z”）. 実際、n次単位行列をEn、 Aの行列式をdetA、 Aの余因子行列をAとすると、. AA 一（det A）En. であることから、. 1 ．． AA ＝ En （det A）となるので、. l r A−1＝（det A）となる。. detA ＝士1であり、Aは整数n次行列であるから、（ 1det A）Aは整数n次. 正則行列である。よって、！には逆写像！一1＝・ gが存在するので！は全単射である。. 以上から、！は同型であることが示された。 □ 補題2．5．5a1，．．．，amをそれぞれznの元とする。このとき、同型な写像 f：Zπ一→Zηによって定まる、次の写像は同型である。 f ： z”／〈ai ，．．．， a．〉一 Z”／〈f（ai），．．．， f（a．）〉. ［X］ H ［f（X）］. 証明まず、［x］＝［y］＝＝〉 x−y E （al，．．．，am＞. 一〉 f（x）一 f（y） E 〈f（ai），．．．，f（a．）〉一〉［f（x）］一［f（y）］ E Z”／〈f（ai），．．．，f（a，n）〉. であるから、この写像はWell−Definedである。また、！が同型であることから、この写像は明らかに準同型であり、全射である。.

(34) 第2章タイルホモロジー群 33 よって、この写像が単射であること、つまり！の核が｛［0］｝であること. がいえれば、この写像が同型であるといえる。！の核の任意の元国について、 f（［x］）一［o］｝［f（x）］＝＝［o］. 一〉 f（x） E 〈f（ai），．．．，f（a．）〉（2．12）. ＝〉 xE 〈ai，．．．， a．〉（2．13）＝〉［x］＝［O］（ Zn／〈al，．．．，a．〉. であることから、fの核は｛［0】｝である。式（2．12）から式（2．13）への変形. は、f一1を用いている。. 以上より、この写像が同型であることは示された。 □ 補題2．5．3から補題2．5．5までを用いて次の定理を導く。. 定理2．5．6m個のznの元（縦ベクトル）を並べたn行m列の整数行列 A＝（a1，＿，am），B＝（b1，．．．，bm）について、整数基本行列のnc S， Tを. 用いて B ＝ SAT が成り立つとき、群zn／＜a1，．．．，am＞とzn／〈b1，．．．，bm＞は同型である。. 証明 0＝ATとおき、0＝（c1，．．．，Cm）とすると、 Tは基本行列の積なので、補題2．5．3より Zn／〈ab．．．，am＞＝＝ Zn／〈cl，．．．，cm＞. が成り立つ。. 次に、整数基本行列の行列式は±1なので、それらの積であるθも行列式は土1であり、補題2．5．4よりSは、 f：zn 一一〉 zn. xH sx （x E zn， sx E zn）. である同型写像！を導く。. さらに、補題2．5．5より、この！によって定まる写像 f ， zn／〈c，，．．．， c．〉一 zn／〈f（ci），．．．， f（c．）〉. ［X］ H ［f（X）］＝一［SX］.