２００４年度卒業研究ゼミ

勉強テーマ「結び目の自明・非自明の判定アルゴリズム」

まず、「数学情報ゼミ」のページを読んで下さい。３彩色定理を用いれば或（あ）る種の結び目はほどけないことを簡単に示すことができたのでした。しかし、８の字結び目がほどけないことは証明できませんでした。どんな結び目の図が与えられても、それがほどけるかほどけないか判定できる一定の手続き（アルゴリズム）は在（あ）るのでしょうか？　実は、１９６０年頃に Walfgang Haken というドイツの数学者がその判定アルゴリズムを発明しました。位相幾何学の最も重要な成果の一つであり、人類の最も貴重な財産の一つと言っても過言ではないでしょう。しかし、その方法は３次元位相幾何学を専門に学んだ人でないと容易には理解できないものでした。２００１年になって、Joel Hass と Jeffrey C. Lagarias という数学者が共同研究で、その方法を誰にでも分かるような形に直しました。まず、それを解説しましょう。

上の図は結び目の図の部分的な変形を表していて、Reidemeister moves と呼ばれています。結び目の図に Reidemeister move をしても図の表す結び目は同じものです。RI move は結び目の図の１角形領域を囲む紐（ひも）を１８０度ひねって１角形を消し、交差点を一つ減らす操作です。逆に、何もなかったところをつまんで１８０度回転し、１角形領域を作り出す操作も RI move と言います。１角形と言いましたが、交差点のところを角と考えています。RII move は２角形領域を囲む２本の紐のどちらかが両方の交差点の上を通り、もう一方の紐が両方の交差点の下を通るときに、２角形領域を消す操作です。逆に２角形領域を作る操作も RII move と呼ばれます。RIII move はちょっと難しいですね。交差点 B と C を通る紐が両方の交差点の上を通っていることに注目して下さい。この紐を図の下のほうに移動していって、交差点 A を通り越させます。ただし、紐の端の点は固定しておきます。３角形領域が１つ消えて、別の３角形領域が新たに生じます。実は、この３種類の変形によって、結び目の立体的な変形を全て表せることが証明できます。もう少し数学的に言うと、２つの結び目の図が同じ結び目を表すならば、一方の図に Reidemeister moves を有限回適用して、もう一方の図に変形することができるという定理が証明されています。下の図は Reidemeister moves によって自明結び目の図を実際にほどく作業を表しています。

Hass と Lagarias が証明したのは「交差点がｎ個の結び目の図が自明結び目を表すならば、うまく Reidemeister moves を適用すれば 2^{100000000000n} 回以下でほどける」という定理です。上の図の交差点は３つですから n=3 です。実際、2 回の Reidemeister moves でほどけていて、2 ≦ 2^{100000000000×3} が正しく満たされています。おめでとう！とてつもなく大きな数が出てきて面食らっているかもしれませんが、とにかく具体的な n の式で何回以下と分かったことが画期的なのです。さて、この定理を用いるとどんな結び目の図が与えられてもほどけるかほどけないか判定できます。すなわち「ありとあらゆる組み合わせで 2^{100000000000n} 回の Reidemeister moves を適用してみて、ほどけたら自明結び目、ほどけなかったら非自明結び目である。」ということになります。３次元空間の中でいかにフニャフニャ動かしてもほどけないということが、限られた回数の Reidemeister moves を調べただけで分かってしまうのです。しかしながら、2^{100000000000n} という数は大き過ぎて、実用的な判定法になっているとは言えません。コンピュータで計算しようとしても、全然メモリが足りないでしょう。この数は宇宙の全ての分子の数と比べるのが面白そうです。幾（いく）つだったかなあ？何かの本で読んだのですが、忘れてしまいました。

兎（と）にも角（かく）にも数学的には結び目がほどけるかほどけないか判定できることになりました。この Hass と Lagarias の定理の証明までを勉強する予定でしたが、実際は時間が足りず、Haken の判定方法までで勉強は終わりにして研究に入りました。だから、Haken の判定方法の最初のところを大雑把に紹介しましょう。でも、ちょっと難しいですよ。

上の図のように自明結び目は円盤を張ります。つまり、３次元空間の中の或（あ）る円盤の縁（ふち）になっています。実際、結び目が円盤の縁になっていたら、円盤を小さく縮めていくと縁の結び目も小さくなってほどけていきます。逆に、ほどける結び目だったら、ほどいていって、ほどけた状態のときに平らな円盤の縁になっています。次に、先程ほどいていった過程をビデオの逆回しのように逆さに辿って行きます。この逆回しのときにビデオの最後の平らだった円盤も結び目と一緒にフニャフニャと変形していくと、ほどき始める前の結び目も円盤の縁になっていることがわかります。

したがって、結び目が与えられたとき、その結び目を縁とする円盤があれば自明結び目だし、無ければ非自明結び目であることになります。しかし、空間の中のありとあらゆるフニャフニャ曲面を一つ一つ円盤かどうか調べるのは、全部で無限個あるので人間には扱いきれません。「綺麗」な形の限られた個数の円盤だけを考えれば済むようにしたいものです。「綺麗」の基準を決めるために舞台装置を整えます。まず、下の図のように十分に大きな立方体を用意すれば与えられた結び目がすっぽり入ります。もしも結び目が円盤の縁になっていたら、円盤ごと立方体の中に押し込められることが証明できます。次に、立方体から結び目を太くしたドーナツを繰り抜いて取り除きます。そうして残った部分の立体図形を記号Ｅによって表します。さて、位相幾何Ｉでは曲面を多角形たちに分割しました。同じように立体Ｅも有限個の四面体（三角錐）たちの面と面を張り合わせて得られるものとみなすことができます。ただし、四面体の辺や面は真っ直ぐとは限らずに、フニャフニャと曲がっていても構いません。具体的な分割方法の解説はこのページでは省略します。

曲面が四面体たちに対して「綺麗」な位置にあるとは、その曲面が各々の四面体たちと下の図のような三角形と四角形たちで交わることと定義します（取り決めます）。このとき、曲面は normal surface であると言います。もしも結び目を縁とする円盤があったら、それは「綺麗」な位置にある円盤に取り直せる、つまり normal surface に変形できることが証明できます。さて、ところが、問題はまだまだこれからです。normal surfaces は無限個あるのです。何とかして有限個だけ調べれば済むようにしないといけません。綺麗なだけでなく「簡単な」形の曲面 fundamental surfaces を定義すると、それが有限個になります。実は、normal surfaces は或る連立１次方程式の解たちに対応していて・・如何でしょう？ちょっと大変ですね。でも、４年生は殆どの必要な単位を取ってしまっていてゼミの勉強に集中できるので、このくらいやりがいがあった方が良いのです。それにしても２００４年度のゼミの学生たちは本当に良く頑張りました。