は多項式 時間で計算可能であるが，自明な結び目と同じ

On computation of HOMFLY polynomials of Montesinos links

村上 雅彦

概 要

Montesinos linkのHOMFLY polynomialをn交点の標準的なlink diagram からO(n³)時間で計算するアルゴリズムの概要を述べる．

1.

_はじめに

Alexander polynomial [1], Jones polynomial [7]，HOMFLY polynomial [3, 17]

は，いず れも絡み目の分類において有用な代表的不変量である．

は多項式 時間で計算可能であるが，自明な結び目と同じ

を持つ非自明な結 び目が知られている．一方，Jones polynomial や

は，Alexander

polynomial

に比べて絡み目の分別能力が優れているものの，それらの計算は困難である

事が知られている．

は，

により示された捻り数と向 き付けられていない

の

を用いた組合せ的な 計算方法を用いると，

次の多項式の

回の和積で計算できる．ここで，

は入力 の

の交点数とする．

は，

の計算時間を

時間に改善した．しかし，一般に

や

の計算は#P–hard である事が

により示されている．この事より，最悪の場合，これらの計算には指数時間必要であ ると予想される．

そこで，絡み目に妥当な制限を設けた場合の

や

を高速に計算するアルゴリズムの研究も行われている．J.A. Makowsky [9, 10] は，

入力の

の木幅が定数で制限されている場合，Jones polynomial は多項式時 間で計算可能である事を示した．J. Mighton [12, 13] は，入力の

の木幅が 高々2 である場合，Jones polynomial は

次の多項式の

回の多項式の演算で 計算可能である事を示した．M. Hara, S. Tani, M. Yamamoto [5] は，arborescent link の

は標準的な

から

次の多項式の

回の多項式 の演算で計算可能である事を示した．M. Hara, M. Murakami, S. Tani, M. Yamamoto

は，2–bridge link, closed 3–braid link, Montesinos link の

は 標準的な

から

次の多項式の

回の多項式の演算で計算可能で ある事を示した．T. Utsumi, K. Imai [19] は，pretzel link の

は標準 的な

から

時間で計算可能である事を示した．Y. Diao, C. Ernst,

は，入力の

の

場合，Jones polynomial は多項式時間で計算可能である事を示しており，特に，

を含む

の

は

時間で計算可能である事を示した．H.M. Morton, H.B. Short [14] はある定数

に対して

の

は多項式時間で計算可能である

∗〒156-8550 東京都世田谷区桜上水3-25-40日本大学文理学部情報科学研究所

e-mail:[email protected]

事を示した．J.A. Makowsky, J.P. Mari˜

はある定数

に対して

の

は多項式時間で計算可能である事を示した．M. Murakami,

は，2–bridge link の

は標準的な

diagram

から

次の多項式の

回の多項式の演算で計算可能である事を示した．

本稿では，

の

を

交点の標準的な

から

時間で計算するアルゴリズムの概要を述べる．

2.

_準備

定義 2.1 HOMFLY polynomial H

は

の集合から変数

の整係数ローラ ン多項式環への写像であり，link diagram

に対して以下で定義される．

H(⃝) = 1, lH

(

@

@ I )

+l⁻¹H (

@@

@ I )

+mH

( I )

= 0.

ここで，⃝ は任意の

である．第

式において

つの

は示されている交点の周辺以外は同一である．

観測 2.2

任意のn 交点のlink diagram の

の次数の絶対値は

項数は

である．

交点の無い

本の垂直な紐からなる

を

とし，交点の無い2 本の水平な 紐からなる

は

とする．任意の整数

に対して，0–tangle を

回捻った

を

とする．これらを

とし

と表す．integer tangle の

本の紐に向きが与えられているとき，その

は向き付けられているといい，

それの向きを

と

で表す．上向きを

とする．北西を通る紐の向 きが

で北東を通る紐の向きが

である

を

と表す（図

参照）．

U 6 6 ? 6K

0–tangle 3–tangle (−2)–tangle ∞–tangle I0−1−1

I3+1+1

I₋2−1+1

I_∞⁺¹⁻¹

図

と

整数

に対して，integer tangle

からなる図

の様な

を

とし，

と表す．向き付けられた

に対して，i 番目の

の北西を通る紐の向きを

，北東を 通る紐の向きを

とし，この

を

と表す（図

参照）．

定理 2.3 ([16]) D = Re^ol1or1(a₁, . . . , a_k)

を

交点

とする．H(D) は

から

時間で計算可能である．

I

I

I

Iak−1

I

@@

ApppppA

I

I

I

I

Iak−1

@@

@@

ppppp ppppp pp I

k

が奇数

が偶数

Re⁺¹⁺¹(a1, . . . , ak) Re⁺¹⁻¹(a1, . . . , ak)

図

整数

に対して，integer tangle

からなる図

の様な

を

とし，

と表す．向き付けられた

に対して，i 番目の

の北西を通る紐の向きを

，北東を 通る紐の向きを

とし，この

を

と表す（図

参照）．

integer tangle I_a1, . . . , I_ak

からなる図

の様な

を

と表す．向 き付けられた

に対して，i 番目の

の北西を通る紐の向き を

，北東を通る紐の向きを

とし，この

を

と表 す（図

参照）．

I

I

I

R I

Pe^{+1,−1,...,+1}(a₁, a₂, . . . , a_k)

図

I

I

I

k R I R

図

整数

に対して，

からなる図

の様なtangle を

という．integer tangle

1, . . . , I_au,1, . . . , I_au,vu, I_a

からなる図

の 様な

を

とし，

と表す．向き付けられた

に 対して，i 番目の

の北西を通る紐の向きを

，南西を通る紐の向きを

とし，この

を

と表す（図

参照） ．integer tangle

1, . . . , I_au,1, . . . , I_au,vu

からなる

図

の様な

を

と表す．向き付け

られた

に対して，i 番目の

の北

西を通る紐の向きを

，南西を通る紐の向きを

とし，この

を

と表す（図

参照），ここで

番 目の

の北東を通る紐の向きの逆を

，南東を通る紐の向きの逆を

とする．u 番目の

の

番目の

の北西を通る紐の向きを

， 北東を通る紐の向きを

とする．

I a

I a

I a

I a

I a

I a

I a

I a

I a

k

が奇数

が偶数

図

3. HOMFLY polynomial

の漸化式

Montesinos diagram

の

の漸化式を以下に示す．これらの漸化式と

の

の漸化式

を用いて

の

を計算する．

補題 3.1

H(Mf^{ot1,ob1,...,otu,obu}(a_1,1, . . . , a_1,v1| · · · |a_u,1, . . . , a_u,vu||a))

=



































−l⁻²H(Mf^{ot1,ob1,...,otu,obu}(a1,1, . . . , a1,v1| · · · |au,1, . . . , au,vu||a−2))

−l⁻¹mH(Mf^{ot1,ob1,...,otu,obu}(a_1,1, . . . , a_1,v1| · · · |a_u,1, . . . , a_u,vu||a−1)) if o^t₁ =o^b₁,

−l²H(Mf^{ot1,ob1,...,otu,obu}(a_1,1, . . . , a_1,v1| · · · |a_u,1, . . . , a_u,vu||a−2))

−lmH(Ne^{ot1,ob1,...,otu,obu,ot1,ob1}(a_1,1, . . . , a_1,v1| · · · |a_u,1, . . . , a_u,vu)) if o^t₁ ̸=o^b₁ and a is even,

−l²H(Mf^{ot1,ob1,...,otu,obu}(a_1,1, . . . , a_1,v1| · · · |a_u,1, . . . , a_u,vu||a−2))

−lmH(Ne^{ot1,ob1,...,otu,obu,ob1,ot1}(a_1,1, . . . , a_1,v1| · · · |a_u,1, . . . , a_u,vu)) if o^t₁ ̸=o^b₁ and a is odd.

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

I

NW SW

NW

SW SW NW

Mf^+1,−1,−1,+1,...,+1,−1(a_1,1, . . . , a_1,v1| · · · |a_u,1, . . . , a_u,vu||a).

図

補題 3.2

H(Mf^{ot1,ob1,...,otu,obu}(a_1,1, . . . , a_1,v1| · · · |a_u,1, . . . , a_u,vu||a))

= {

H(Mf^{ot1,ob1,...,otu,obu}(a_1,1, . . . , a_1,v1| · · · |a_u,1, . . . , a_u,vu)) if a= 0, H(Mf^{ot1,ob1,...,otu,obu,ob1,ot1}(a_1,1, . . . , a_1,v1| · · · |a_u,1, . . . , a_u,vu| ∓1)) if a=±1.

I

I

I

I

I

I

I

I

I

I

I

I

I

I

NW SW

NW

SW SW NWNE SE

図

補題 3.3

H(Mf^{ot1,ob1,...,otu,obu}(a_1,1, . . . , a_1,v1| · · · |a_u,1, . . . , a_u,vu))

=

















































−l⁻²H(Mf^{ot1,ob1,...,otu,obu}(a_1,1, . . . , a_1,v1| · · · |a_u−1,1, . . . , a_u−1,vu−1|a_u,1−2))

−l⁻¹mH(Mf^{ot1,ob1,...,otu,obu}(a_1,1, . . . , a_1,v1| · · · |a_u−1,1, . . . , a_u−1,vu−1|a_u,1−1)) if o^l_u,vu =o^r_u,vu and v_u = 1,

−l⁻²H(Mf^{ot1,ob1,...,otu,obu}(a_1,1, . . . , a_1,v1| · · · |a_u,1, . . . , a_u,vu−1, a_u,vu−2))

−l⁻¹mH(Mf^{ot1,ob1,...,otu,obu}(a_1,1, . . . , a_1,v1| · · · |a_u,1, . . . , a_u,vu−1, a_u,vu −1)) if o^l_u,v

u =o^r_u,v

u and v_u ≥2,

−l²H(Mf^{ot1,ob1,...,otu,obu}(a_1,1, . . . , a_1,v1| · · · |a_u−1,1, . . . , a_u−1,vu−1|a_u,1−2))

−lmH(Mf^{ot1,ob1,...,otu,obu}(a_1,1, . . . , a_1,v1| · · · |a_u−1,1, . . . , a_u−1,vu−1)) if o^l_u,vu ̸=o^r_u,vu and v_u = 1,

−l²H(Mf^{ot1,ob1,...,otu,obu}(a_1,1, . . . , a_1,v1| · · · |a_u,1, . . . , a_u,vu−1, a_u,vu−2))

−lmH(Mf^{ot1,ob1,...,otu,obu}(a1,1, . . . , a1,v1| · · · |au,1, . . . , au,vu−1)) if o^l_u,vu ̸=o^r_u,vu and v_u ≥2.