\underline{卒業研究報告書 (平成 15 年度)}

Closed 3-braid リンクの Jones 多項式による分類支援システム

A Support System for Classifying Closed 3-braid Links by Jones Polynomial

                http://www.tani.cs.chs.nihon-u.ac.jp/g-2004/nob/

谷研究室鈴木伸和

Nobukazu SUZUKI

概要

closed 3-braid リンクに対して，ある交点数以下のすべての標準的なダイアグラムの Jones 多項式を計算し，比較することによって closed 3-braid リンクを分類するシステムを構築した．現在， 16 交点以下のすべての標準的なダイアグラム (43,046,720 通り) に対して分類が完了している．

1 はじめに

絡み目が自明な絡み目であるかを判定する問題や 2 つの絡み目が与えられたときそれらが同値であるかを判定する問題は結び目理論における基本的な問題である．絡み目が自明であるかを判定する問題は 1999 年に J.Hass， J.C.Lagarias， N.Pippenger[2] によって NP に入ることが示された．一方， 2 つの絡み目が同値であるかを判定する問題は原始帰納的であるかどうかも知られていない．一般に，ライデマイスター移動とよばれる同値変形を何回か行うことによって 2 つの絡み目が同値であるか判定可能である．しかし，その同値変形の回数には制限がないため難しいと考えられている．このこととも関連して，結び目理論では不変量についての研究も盛んに行われている． Jones 多項式は，最も代表的な多項式不変量である． L.H.Kauffman は，絡み目のダイアグラムから組み合わせ論的に Kauffman bracekt 多項式を定義し，ひねり数と組み合わせて Jones 多項式を決定する方法を考案した．一般に Jones 多項式の計算は指数時間かかると予想されている．

村上，原，山本，谷 [4] は closed 3-braid リンクに対して，標準的なダイアグラムから O(n^{2}logn) 時間で計算できることを示しており実装も行っている．本研究では，標準的なダイアグラムに適切に向き付けを行いひねり数を計算することによって Jones 多項式を計算するよう拡張した．さらに， closed 3-braid リンクの標準的なダイアグラムをすべて生成しその Jones 多項式を計算することによって分類を行うシステムをシステムを構築した．現在， 16 交点以下のすべての標準的なダイアグラム (43,046,720 通り) に対して分類が完了している．

2 結び目理論の準備

絡み目とダイアグラム

3 次元ユークリッド空間内に埋め込まれた互いに素な n 本の単純閉曲線を n 成分の絡み目または，単に絡め目(link) という．特に， 1 成分の絡み目を結び目(knot) という．各成分に向きが与えられている絡み目を有向絡み目という．

3 次元ユークリッド空間内で自分自身を横切らないで紐を動かすことを全同位変形という． 2 つの絡み目 L と L′ が同値であるとは， L を L′ に全同位変形可能であることをいう．

絡み目を平面に射影した図で，多重点が横断的に交わっている 2 重点のみからなるものをその絡み目の正則射影図といい，さらに，各 2 重点にもとの絡み目における交差の上下の情報を加えたものをその絡み目のダイアグラムという．また，各 2 重点を交点という．

図 1: 絡み目とダイアグラム Kauffman bracket 多項式

絡み目のダイアグラム L̃ の Kauffman bracket 多項式 ⟨L̃⟩ とは，次のように再帰的に定義される変数 A の整係数 Laurent 多項式のことをいう．

(i) ⟨◯⟩ = 1,

(ii) ⟨^{⧹}⧸_{⧹}⟩ = A⟨ )( ⟩ + A^{−1}⟨ ≍ ⟩,

(iii) ⟨L̃ ⊔ ◯⟩ = (−A^{−2} − A^{2})⟨L̃⟩.

＊ ◯ は自明な結び目の交点を持たないダイアグラム＊ (ii) の式中に現れる 3 つのダイアグラムは，いずれ

も式中で描かれている部分以外は一致している

＊ L̃ ⊔ ◯ は， 2 つのダイアグラム L̃ と ◯ との和で両者間で交点を持たないダイアグラム

ひねり数

有向ダイアグラム L̃ の各交点に対して，図 2 のような規則で +1 または −1 の符号を対応させ，その符号和を L̃ のひねり数 (writhe) といい， w(L̃) と表す．

+1 の交点 −1 の交点

図 2: ひねり数の符号

Jones 多項式

有向絡み目 L の Jones 多項式 X(L) は，次のようにして定義される．ここで， L̃ は任意の L のダイアグラムとする．

X(L) = (−A^{3})^{−w(L̃)}⟨L̃⟩|_{t^{1/2}=A^{−2}}

X(L) は L̃ の取り方によらないことが知られている．整数タングル

絡み目のダイアグラムにおいて，絡み目がちょうど 4 点で交わるような円で囲まれた領域をタングルという．垂直な 2 本の紐からなるタングルを 0-タングル， 0-タングルを k 回捻ってできるタングルを k-タングルといい， I_{k} と表す．これらを総称して整数タングルという．

0–タングル 3–タングル (-2)–タングル

図 3: 整数タングル closed 3-barid リンク

両端が 2 つの平行な平面に接続している 3 本の紐で，それぞれの紐が 2 つの平面の間にあるすべての平行な平面とちょうど 1 回ずつ交わっているものを 3-braid という． 3-braid を正則射影し，射影平面上で紐の両端が自分自身とも他の紐とも交わらないように結ばれているダイアグラムを持つ絡み目を closed 3-braid リンクという．任意の closed 3-braid リンクは，整数タングルを図 5 のようにつないだダイアグラムを持つことは明らかである．

[figure: (a); (b)]

図 4: (a) 3-braid (b) closed 3-braid links ダイアグラム

標準的なダイアグラムと整数列表現

図 5 のように結んだダイアグラムを closed 3-braid リンクの標準的なダイアグラムといい， W̃(a_{1}, …, a_{m}) と表す．また， (a_{1}, …, a_{m}) を W̃(a_{1}, …, a_{m}) の整数列表現という．

m が奇数 m が偶数

図 5: closed 3-braid リンクの標準的なダイアグラム

3 closed 3-braid リンクの分類

ひねり数アルゴリズム

一般に n 成分の絡み目の向き付けは 2^{n−1} 通りある． closed 3-braid リンクの成分数は高々3 である．今回はひねり数が最も大きくなるように向き付けを行う．この方法を用いることによって，向き付けられていない closed 3-braid リンクに対しても Jones 多項式が計算可能となる．

以下のアルゴリズムは， closed 3-braid リンクの標準的なダイアグラムの 1 つの紐を上から下にたどっていき各整数タングルに向きを付けるアルゴリズムである．

Procedure down tangle tangle[i].left, tangle[i].right(i = 1, …, m) を 0 で初期化 i を 1 で初期化 P を”left”で初期化 if m=1

tangle[2].right⟵1 while tangle[1].left, tangle[1].right, tangle[2].right do のすべての値が 0 でない

while i <= m do

if i が奇数 tangle[i].left = 1 ・・・ (＊) if P が”left”

if a_{i} が奇数

i をインクリメント else a_{i} が偶数

i ⟵ i + 2 else P が”right”

if a_{i} が奇数

i ⟵ i + 2 else a_{i} が偶数

i をインクリメント P を”left”に変える

else i が偶数

tangle[i].right = 1 ・・・ (＊) if P が”left”

if a_{i} が奇数

i ⟵ i + 2 else a_{i} が偶数

i をインクリメント P を”right”に変える

else P が”right”

if a_{i} が奇数

i をインクリメント else a_{i} が偶数 i ⟵ i + 2

    od

if i = m + 1 かつ P が”right”

i ⟵ 2

    else

i ⟵ 1

  od

closed 3-braid リンクの標準的なダイアグラムの 1 つの紐を下から上にたどっていき各整数タングルに向きを付けるアルゴリズムは， (＊) において-1 を代入する． tangle[i].left と tangle[i].right の符号が一致すれば，整数タングル a_{i} のひねり数は +a_{i}，一致しなければ， −a_{i} となる． i は 1〜m までの任意の値．各整数タングル a_{i} のひねり数の和が closed 3-braid リンクの標準的なダイアグラムのひねり数となる．

整数列表現アルゴリズム

closed 3-braid リンクの交点数は，整数列表現 (a_{1}, …, a_{m}) の各要素 |a_{i}| (i = 1, …, m) の和であることは明らかである．ある交点数以下の標準的なダイアグラムをすべて列挙するためには整数分割を行うことによって可能である．例えば， 4 の分割は (1, 1, 1, 1), (1, 1, 2), (1, 3), (2, 2), (4) の 5 通りであり，さらに各分割に対して順列と符号を考慮すると交点数 n となるすべての整数列表現を得たことになる．

以下のアルゴリズムは，ある整数のすべての分割の順列を生成する．

Procedure permutaion 入力: 交点数 n 出力: 交点数 n である整数列表現 P[ ] sum ⟵ n i ⟵ n − 1 P[0, …, i] を 1 で初期化

  while i が 0 でない do

sum ⟵ n−P[i] i をデクリメント P[i] をインクリメント sum をインクリメント while sum と n が一致でない do

i をインクリメント P[i] ⟵ 1

sum をインクリメント

od

P[0, …, i] を出力

od

以下のアルゴリズムは，全ての場合の符号が付いた整数列表現を生成する．

Procedure progressive expression 入力: 符号なし整数列表現 P[0, …, m ] 出力: 符号を付けた整数列表現 PE[ ] SIGN[0, …, m] を 0 で初期化

repeat

for i = 0, …, m

if SIGN[i] = 0

PE[i] ⟵ P[i] を (−1) 倍 else SIGN[i] = 1

PE[i] ⟵ P[i] PE[0, …, m] を出力 SIGN[] 配列の要素の並びを 2 進数と見立てて， SIGN[] 配列の要素をインクリメント

until SIGN[0, …, m] の値がすべて 1 PE[0, …, m] を出力

4 まとめ

現在， 16 交点以下のすべての closed 3-braid リンクの標準的なダイアグラム (43,046,720 通り) に対して Jones 多項式を計算し比較することによって分類が完了している．今後の課題

• 分類が完了した整数列表現の探索の高速化

• 入力，出力の GUI 化

参考文献

[1] C. C. Adams. THE KNOT BOOK. W.H. Freeman and Company. 2001.

[2] J.Hass, J. C. Lagarias and N. Pippenger. The computational complexity of knot and links problems. Journal of the ACM, Vol. 46, No.2(1999) 185-211.

[3] W.B.R. Lickorish. An Introduction to Knot Theory. Springer-Verlag New York,Inc. 1997.

[4] M. Murakami, M. Hara, M. Yamamoto, S. Tani. Fast Algorithms for Computing the Jones Polynomials of Certain Links. Preprint. 2004.

付録

作成したプログラムの仕様入力 1: 始点 s, 終点 t 出力 1: 交点数 s から t までのすべての closed 3-braid リンクの標準的なダイアグラムの Jones 多項式による分類結果入力 2: 交点数 n 出力 2: ランダムに 1 つ生成された n 交点の整数列表現の Jones 多項式入力 3: 整数列表現出力 3: 入力された整数列表現の Jones 多項式