数理解析研究所講究録1093 巻 1999 年 51-56

51

絡み目の Jones 多項式の計算
原正雄 (Masao HARA)
谷聖– (Sei’ichi TANI)
山本慎 (Makoto YAMAMOTO)

1

東海大学情報数理学科
日本大学応用数学科
中央大学数学科

はじめに
絡み目の Jones 多項式は代表的な絡み目型の不変量のひとつであり, Jones 多項式を求める問題は #P-完全であることが知られている. 本稿では, 絡み目の Jones 多項式を次数の高い項から順に計算するアルゴリズムを考察し, これを改良することにより Jones 多項式の次数を計算する発見的アルゴリズムを提示する.

さらにこの次数を計算するアルゴリズムがプレッツェル絡み目などの有名な絡み目のクラスに対して有効に働くことを例をもって示す.

2絡み目に関する準備
まず, 絡み目に関する用語の定義を簡単に与える. 詳しくは, [S] などを参照されたい.

絡み目の定義 :3 次元ユークリッド空間内に埋め込まれた, 互いに素な$n$個の閉曲線 (円周$S^{1}$) を$n$成分の絡み目または単に絡み目 (link) という. 特に, 1 成分の絡み目を結び目 (knot) という.
絡み目のダイアグラム : 絡み目を平面に射影した図で, 多重点が横断的に交わっている 2 重点のみのものをその絡み目の正則射影という. さらに, 各 2 重点にもとの絡み目における交叉の上下の情報を加えたものを,その絡み目のダイアグラムといい, 2 重点を交点という.

ダイアグラム

図152

絡み目のグラフ : 絡み目のダイアグラムにより分けられる平面の領域をチェッカーボードのように白黒 2 色に塗り分ける. このうち–方の色, たとえば非有界な領域を含まない色の, 各領域に 1 つずつ点を取る. それらの点を図 2 のように線で結び, 各線には, 図 3 のように$+$,–をつける. このようにして得られるグラフを, その絡み目またはダイアグラムのグラフという.

-の線+の線

図3

図23Kauffman ブラケット多項式
次に, Kauffman ブラケット多項式を定義する (cf. [K]).
絡み目 $L$ のダイアグラムを$s:Earrow\{+,$ $-\}$ をステート$\tilde{L}$, グラフをとする. $G$ の辺集合 $E$ から集合 $\{+.’-\}$ への写像

$G(V, E, \mathrm{s}\mathrm{g}\mathrm{n})$(state) という. ステート$s$に対して,$E_{s}$を $E_{\theta}=\{e\in E|\mathrm{s}\mathrm{g}\mathrm{n}(e)=s(e)\}$ とし, $sG$ を $sG=(V, E_{\mathit{8}})$ とする. グラフのステート全体の集合を $S$ で表す.

Kauffinan ブラケット多項式$\langle G\rangle$を次の式で定義する.

$\langle G\rangle=\sum_{S\in s}A\mu(\epsilon)(-A^{2}-A^{-}2\beta(s)-1)$

ただし, $\mu(s)=\sum_{Ee\in}S(e)$ とし,多項式は$2^{|E|}$$\beta(s)\#\mathrm{h}sG$.の $0$ 次元と 1 次元の$\mathrm{B}\mathrm{e}\mathrm{t}\mathrm{t}\mathrm{i}.\text{数の和_{と}する}$. Kauffman ブラケット個の多項式の和をとる計算になる.

Kauffman ブラケット多項式は絡み目型の不変量ではない. つまり, 同じ絡み目でもダイアグラムによってそのグラフの Kauffman ブラケット多項式が異なる場合がある.

FACT: 同じ絡み目の 2 つのグラフ$G_{1},$ $G_{2}$に対して, ある整数 $w$ が存在し,$\langle G_{1}\rangle=(-A-3)w\langle G_{2}\rangle$が成り立つ.
絡み目 $L$ の各成分に向きがついているとき $L$ を有効絡み目という. 有効絡み目の (有効) ダイアグラム$\tilde{L}$に対して, $V_{L}(A)=(-A^{-3})w(L)\sim\langle c_{\sim\rangle}L$ とおくとし, ここでの$V_{L}$

で$w(\tilde{L})$$A=t^{\frac{3}{4}}$$V_{L}$

は$\tilde{L}$はライズ (wdthe) とよばれる整数であり,の選び方によらないことが知られている. ただ$G_{L}\sim$

はしのグラフである. Jones 多項式とはこと変数変換したものである. 詳しくは [K] を参照.

534アルゴリズム
単純に$\langle G\rangle$を計算するアルゴリズムは次のようになる.

完全に計算するアルゴリズム :入力 絡み目のグラフ$G$

出カブラケット多項式$\langle G\rangle$$s:=$ (すべて $+1$ の state)(

Put $(s)$$*\mathrm{q}\mathrm{u}\mathrm{e}$while (que$\neq\emptyset$にを入れる$s$$*$))

begin$s:=$ get(から state を取り出す$*\mathrm{q}\mathrm{u}\mathrm{e}$$*$)$\langle G\rangle:=\langle G\rangle+P(S)$for( の最後の $-1$ 位置の)+1to $N$ do$\mathrm{i}:=$

$s$

begin
$s’:=$ (put$s$の$\mathrm{i}$番目の辺を +1 から $-1$ に変えた state)$(_{S^{\mathit{1}}})$

endend上のアルゴリズムを改良してブラケット多項式の最高次数を高速に計算するアルゴリズムを作ることができる. このアルゴリズムには現在予想される最高次数を計算するための que と, それの次数の係数がのとき, さらに計算を続けるための que の 2 つの que を使用する.
最高次数を求めるアルゴリズム :入力 絡み目のグラフ$G$

出カブラケット多項式$\langle G\rangle$

s:=(すべて +1 の state)putl $(s)$($*_{\mathrm{q}\mathrm{u}}\mathrm{e}1$$\mathrm{d}\mathrm{e}\mathrm{g}:=\deg \mathrm{P}(S)$に$s$を入れる$*$)( 予想される最高次数 )
$*$

$*$

repeatprocedure(deg)( 最高次数が $\deg$ の state の和を計算する$*$

quel $:=$ que2$\mathrm{d}\mathrm{e}\mathrm{g}:=$deg-4

until $(\deg\langle G\rangle>=\deg)$ or (queend$1=\emptyset$)

$*$)

$0$

54

proc\’eure(deg: integer)
beghl

while (quel$\neq\emptyset$)

begin($s:=$ getl$*_{\mathrm{q}\mathrm{u}}\mathrm{e}1$から state を取り出す$*$)$\langle G\rangle:=\langle G\rangle+P(S)$for$\mathrm{i}:=$( の最後の $-1$ 位置の)+1to $N$ do$s$

begin

1$:=$

($s$の$\mathrm{i}$番目の辺を +1 から $-1$ に変えた state)

if $\deg=\deg^{\mathrm{p}}(S’)$’
then putl $(s)$else$\mathrm{p}\mathrm{u}\mathrm{t}2(S’)$

end
end

5

プレッツェル絡み目
3 以上の整数 $m$ と$0$でない整数 $P1,P2,$ $\ldots,Pm$ に対して, プレッツェj 絡み日 (poetzel link) $P(p_{1},p_{2}, \ldots,p_{m})$とは, 図 4 のような絡み目のことである. ただし, 交点の符号はダイアグラムのグラフで対応する線の符号と –致するものとする. たとえば, $P(-3,5,7)$ は図 5 のようになる.

$\mathrm{r}(^{- s,0},r/$

図4

図5

簡単のため, $|p_{i}|\leq 2(i=1,2, \ldots, m)$ のみの場合を考える.
$P1,P2,$ $\ldots,Pm$の符号がすべて–致しているか\searrow または, それらの中に正の数が 2 個以上含まれているプ55

レッツェノレ絡み目 $P(p_{1},p_{2}, \ldots,p_{m})$ に対しては, すべての符号が $+$ のステートのみが, Kauffmann ブラケット多項式の最高次数を与えることが知られている (cf. [LT]). したがって, これらの場合はこのステートのみを調べることでこのアルゴリズムは終了する, 以下, それ以外のプレッツェル絡み目に対して計算機実験.の結果を述べる.

このアルゴリズムではステート に対応する多項式の次数が高いものから計算していくが, その過程で実際に多項式の和をとるステート (quel に蓄えられるステート) を計算ステート, 定義式の$\beta$を計算するが多項式の和は計算しないステート (quel または que2 に蓄えられるステート) を検査ステートとよぶ.

交点数が 10, 15, ..., 50 のプレッツェル締み目のうち計算ステートが交点数の 2 剰以下で次数が求まる絡み目の割合を調べた結果が次の表とグラフである. 多項式の和や$\beta$の計算は交点数の線形時間でできるので, 全体として $O(|E|^{3})$ 時間で Kauffman ブラケット多項式が求まるものの割合の目安となる.

$1\cup$13$\Delta\cup$$3\cup$$4\supset$

図6$\partial\supset$$4\cup$$4\supset$$\supset\cup$

56

参考文献
.Kaufinan, State Models and the Jones Polynomial, em Topology, 26(1987), 395-407.

[K]$\mathrm{L}.\mathrm{H}$[LT]$\mathrm{W}.\mathrm{B}$.R.Lickorish and$\mathrm{M}.\mathrm{B}$.Thistlethwaite, Some links with non-trivial polynomials and theircrossing-numbers, Comment. Math. Helv., 63(1988), 527-539.
[S]鈴木晋–, 結び目理論入門, サイエンス社, 1991.