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

全文

(1)群論を用いたタイリング問題の判定教科・領域教育学専攻. 自然系コース. M0 8 ユ 7 4G 藤井洋輪. 1 研究の内容. あること、そして群による単純な発想から考えられることから考えれば、このような単純な発想はずっと以前に. タイリングとは、平面上の指定された領域を、指定さ. 報告されていても不思議ではないように思える。ところ. れた有限種類の、単位正方形をつなげた図形であるタイルによって隙間なく敷き詰めることである。タイリング問題とは、指定された領域とタイルに対してタイリングが可能かどうか、そして可能であるならどうすればタイリングが出来るのかを考える問題である。. が、本研究で取り上げているこのタイルホモトピー群を用いた解決方法は、1990年にやっと報告されている。多くの人にとって数学はほぼ完成された学問であり、数. 学における新発見などは非常に難度の高い内容で優秀な数学者にしか成し得ないものであるという固定観念. 正方格子平面におけるタイリング間題の判定の方法として、次のようなタイルロの場合を考える。このと. き、格子領域を2色で市松模様に塗り分けて不可能性を示す市松アルゴリズムが有名である。他にも、タイルの形によっていろいろな方法が古典的に知られているようである。こういった判定方法はどのように導かれたのか。そのメカニズムを、タイルホモロジー群を用いた群. が存在すると思われるのだが、本研究での、それほど難度は高くないと考えられる単純な発想による解決が、最近になってやっと報告されたというこの事実が、この固定観念を払拭するものになるであろうと考えられる。. また、第2章でのタイルホモロジー群の計算には行列を用いているのだが、高等学校の学習内容では、行列の内容は以前と比べて縮小されている。物理学や工学、. 論によって解明する。. 経済学、社会学など様々な分野に応用されている行列で. さらに、タイルホモロジー群による方法よりも強力で、タイルホモロジー群による方法では不可能性を示す. あるにもかかわらず、学習当初にはただ行列の計算が出. 来るというレベルの認識で、それがどういうところに. ことが出来ない場合においても適用可能な方法である、タイルホモトピー群による方法について述べる。. 利用できるのかということは頭に残らないこともある。しかし本研究では、タイリングという幾何学的かっ組み合わせ論的な分野の考察に行列を大いに利用している。このことは、行列に対する上で述べたような認識を払拭. 2 研究の特徴. するきっかけとなるだろう。. 本研究で扱う「タイリング問題」とは、指定された有限種類のタイルを指定された領域へ、タイルが重ならな. 筆者自身、本研究を進めていく上で、こういった自分の中の数学観の転換が行われていくのが実感できた。. いように隙間なく敷き詰めることが可能か不可能かを考える問題である。このタイリング間題は、ルールさえ. また、タイリング問題ではタイルの形や種類の数を変えることで種々の結果が導ける。各自が独自に問題の状. 理解できれば小さな子どもでも取り組める素朴な問題である。. 況を設定して計算してみることで、より興味深くタイリング問題を探ることが出来る。実際、研究過程では数種. 本研究ではタイリング間題を数学的に解決する方法として群論を用いているが、群論の知識がある者にとっ. 類のタイルについて考えてみたのだが、この過程は大変興味深いものであった。こうして自分で問題設定をして. てその証明のアイデアであるタイルホモトピー群は非常に単純な発想による解決方法といえる。数学という学. 自分で解決していく過程を楽しめることもまた本研究の醍醐味である。. 問が古くから存在していることや、問題が素朴なもので. ■320一.

(2) 3 論文の構成. また、彩色アルゴリズムというタイリング間題の判定方法も紹介する。第1章で紹介した古典的な半1」定方法. 以下、修士論文の構成について詳しく述べる。. が彩色アルゴリズムを用いた判定方法の一例となって. 第1章「タイリングについて」では、最初にセルや格. いることや、タイルホモロジー群H（Σ）も彩色アルゴ. 子図形、タイルT、格子領域五、タイルタイプ集合Σ、. リズムの1種であることを述べ、彩色アルゴリズムの. そしてタイリングについての定義を行う。格子領域のタ. 中でも、タイリング可能であるための最も強い必要条. イルタイプ集合によるタイリング可能性を、可能であれ. 件を与えるものがタイルホモロジー群H（Σ）であると. ばその例示、不可能であれば不可能性の証明を行うこと. いうことも述べている。ところが、実際にはタイリング. をタイリング問題という。本論文ではタイリングが不可. 不可能であるにも関わらず、タイルホモロジー群H（Σ）. 能である場合の不可能性の証明に焦点を置いて論じて. を用いてもタイリング可能性が否定されないこともあ. いる。. るとして、第3章へつなげている。. タイリング不可能であることを示す方法としては、総. 当たり的に場合分けをしながらタイルの置き方を考える方法やタイルの面積と格子領域の面積との関係から示す方法がある。しかし、総当たり的に考える方法は格子領域の面積が大きくなった場合には現実的な方法とは言えない。面積による方法もあまり効果的でないことが多い。そこで、面積が大きくなっても容易に判定出来る. 古典的な方法の中から、市松アルゴリズムと、セルに数. 字の1と5を規則的に割り当てる方法を紹介している。. 第3章rタイルホモトピー群」では、1990年に J．H．Conway，J．C．Lagariasの2人が考えた、群を用いる新しい半1」定法であるタイルホモトピー群π（Σ）につい. て述べている。論証を簡単にするために、第1章での状況設定から少し変えた状況でタイリング問題を考えることにしている。最初にその状況について整理し、次に・Σによるタイルホモトピー群π（Σ）を導入するため. の準備として自由群アについて述べている。その後タイルホモトピー群7r（Σ）を定義している。タイルホモトピー群π（Σ）はタイリング可能であるための必要条件を. 第2章rタイルホモロジー群」では、第1章の最後で. 与える。次に正方格子上に三角形状にセルが配置された. 述べた古典的な判定方法がどういった理由で導かれる. 格子領帆と・タイルタイプ集合Σ一F間によ. のかということを、Σによるタイルホモロジー群∬（Σ）. るタイリング問題を考え、これを三角タイリング間題と. を用いて示している。タイリングの条件を少し緩めて、. 呼ぶことにしている。三角タイリング問題では、タイリ. タイリングの過程においてはタイル同士が重なること、. ング可能であるための肌に関する必要十分条件を求め. 重なっている部分からタイル単位で1層ずつ取り除く. ている。. ことを許すことにする。そうして最終的に格子領域が. タイルホモトピー群π（Σ）による判定を行う際に、四. 1層のタイルで隙間なく埋め尽くされている状態になっ. 元数体、群の半直積といった知識を用いた。その結果、. たとき、符号付タイリング可能であるという。この符号. タイルホモロジー群∬（Σ）では否定出来なかった三角. 付タイリング可能であるという条件は、タイリング可能. タイリング間題のタイリング可能性が、タイルホモト. であるための必要条件となっている。. ピー群π（Σ）によって否定出来た。つまり、タイルホモ. 符号付タイリングは自由アーベル群を用いて定式化. トピー群π（Σ）の方が・タイリング可能であるための真. することが出来る。この自由アーベル群を用いてタイル. に強い必要条件を与えている。. ホモロジー群H（Σ）を定義し、タイルホモロジー群の. 計算に必要な整数行列の基本変形や行列の単因子論を紹介した後で計算方法を一般化し、さらに具体的な計算例を紹介している。実はこのタイルホモロジー群∬（Σ）. は、符号付タイリング可能であるための必要十分条件を与えるものである。. 一321■. 主任指導教員清中裕明. 指導教員濱中裕明.

(3)