On computation of HOMFLY-PT polynomials of 2–bridge diagrams

(1)

On computation of HOMFLY-PT polynomials of 2–bridge diagrams

村上雅彦

(

日本大学

)^∗¹

谷聖一

(

日本大学

)^∗²

竹下文雄

(

日本大学大学院

)^∗3 概要

2–bridge linkのHOMFLY-PT polynomialをn交点2–bridge diagram^からO(n³)時間で計算するアルゴリズムを提案する．また，このアルゴリズムを実装する事により行った計算機実験についても触れる．

1.

はじめに

Alexander polynomial [1], Jones polynomial[7]

，

HOMFLY-PT polynomial[3, 16]

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

Alexander polynomial

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

Alexander polynomial

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

Jones polynomial

や

HOMFLY-PT polynomial

は，

Alexander polynomial

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

Jones polynomial

は，

L.H. Kauﬀman [8]

により示された捻り数と向き付けられていないダイアグラム

の

Kauﬀman bracket polynomial

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

O(n)

次の多項式の

2^O⁽ⁿ⁾

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

n

は入力のダイアグラムの交点数とする．K. Sekine, H. Imai, K. Imai [17] は，Jones polynomial の計算時間を

2^O⁽^√ⁿ⁾

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

Jones polynomial

や

の計算は

#P–hard

である事が

F. Jaeger, D.L. Vertigan, D.J.A. Welsh

[6, 19]

により示されている．このことより，最悪の場合，これらの計算には指数

時間必要であると予想される．

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

Jones polynomial

や

を高速に計算するアルゴリズムの研究も行われている．

J.A. Makowsky [9, 10]

は，入力の

Tait graph

の木幅が定数で制限されている場合，

Jones polynomial

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

J. Mighton [12, 13]

は，入力の

Tait graph

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

O(n)

次の多項式の

O(n⁴)

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

M. Hara, S. Tani, M. Yamamoto [5]

は，

arborescent link

の

Jones polynomial

は標準的なダイアグラムから

O(n)

次の多項式の

O(n³)

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

M. Hara, M. Murakami, S. Tani, M. Yamamoto [15, 4]

は，

2–bridge link, closed

∗1〒156-8550東京都世田谷区桜上水3-25-40 日本大学文理学部情報科学研究所 e-mail:[email protected]

∗2〒156-8550東京都世田谷区桜上水3-25-40 日本大学文理学部情報システム解析学科

e-mail:[email protected]

∗3〒156-8550東京都世田谷区桜上水3-25-40 日本大学大学院総合基礎科学研究科

e-mail:[email protected]

(2)

3–braid link, Montesinos link

の

Jones polynomial

は標準的なダイアグラムから

O(n)

次の多項式の

O(n)

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

T. Ut- sumi, K. Imai [18]

は，pretzel link の

Jones polynomial

は標準的なダイアグラムから

O(n²)

時間で計算可能である事を示した．

Y. Diao, C. Ernst, U. Ziegler [2]

は，

入力の

nested closed tangle diagram

の

tangle depth

が高々定数である場合，

Jones polynomial

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

pretzel link, 2–bridge link, Montesinos link

を含む

Conway algebraic link

の

Jones polynomial

は

O(n²)

時間で計算可能である事を示した．

H.M. Morton, H.B. Short [14]

はある定数

k

に対して

closed k–braid link

の

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

J.A. Makowsky, J.P. Mari˜no [11]

はある定数

k

に

対して

k–algebraic link

の

HOMFLY-PT polynomials

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

ある事を示した．

本稿では，

2–bridge link

の

を

n

交点

2–bridge diagram

から

O(n³)

時間で計算するアルゴリズムを提案する．また，このアルゴリズムを実装する事により行った計算機実験についても触れる．

2.

準備

定義 2.1 HOMFLY-PT polynomial H

は

link diagram

の集合から変数

l, m

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

link diagramLe

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

H() = 1, lH

(

@

@ I )

+l⁻¹H (

@@

@ I )

+mH (

I )

= 0.

ここで，

は任意の

trivial knot diagram

である．第

2

式において

3

つの

link

diagram

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

観測 2.2

任意の

n

交点の

link diagram

の

の次数の絶対値は

O(n)

，項数は

O(n²)

，係数の絶対値は

O(2^O⁽ⁿ⁾)

である．

交点の無い

2

本の垂直な紐からなる

tangle

を

0–tangle

とし，交点の無い

2

本の水平な紐からなる

tangle

は

∞–tangle

とする．任意の整数

k

に対して，0–tangle を

k

回捻った

tangle

を

k–tangle

とする．これらを

integer tangles

とし

I_k

と表す．

integer tangle

の

2

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

integer tangle

は向

き付けられているといい，それの向きを+1

と

−1

で表す．上向きを

+1，下向き

を

−1

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

o^l

で北東を通る紐の向きが

o^r

である

integer tangle Ik

を

Iko^lo^r

と表す（図

1

参照）．

補題 2.3

H(I_k^o^l^o^r) =

{ −l⁻²H(I_k₋₂ô^lô^r)−l⁻¹mH(I_k₋₁ô^lô^r) o^l =o^r

−l²H(I_k₋₂ô^lô^r)−lmH(I_∞ô^lô^r) o^l 6=o^r

(3)

U 6 6 ? 6K

0–tangle 3–tangle (−2)–tangle ∞–tangle I₀⁻¹⁻¹ I₃⁺¹⁺¹ I₋₂⁻¹⁺¹ I_∞⁺¹⁻¹

図

1: Integer tangles

と

∞ tangle.

ここで，

3

つの

link diagram

は示されている

integer tangle

の周辺以外は同一である．

証明 k > 0

の場合は

の定義と

Reidemeister move

より明らかである

(

図

2, 3

参照

)

．

k ≤0

の場合は

の定義と

Reidemeister move

より以下が明らかである

(

図

4, 5

参照

)

．

H(I_k₋₂^o^l^o^r) =

{ −l²H(I_kô^lô^r)−lmH(I_k₋₁ô^lô^r) o^l=o^r

−l⁻²H(I_kô^lô^r)−l⁻¹mH(I_∞ô^lô^r) o^l6=o^r

...

6 6

...

6 6

...

6 6

I_kô^lô^r I_k₋₂ô^lô^r I_k₋₁ô^lô^r

図

2: k > 0

かつ

o^l =o^r.

...

6 ?

...

6 ?

...

6 ?

I_kô^lô^r I_k₋₂ô^lô^r I_∞ô^lô^r

図

3: k >0

かつ

o^l 6=o^r.

...

6 6

...

6 6

...

6 6

I_k₋₂ô^lô^r I_kô^lô^r I_k₋₁ô^lô^r

図

4: k ≤0

かつ

o^l=o^r.

...

6 ?

...

6 ?

...

6 ?

I_k₋₂ô^lô^r I_kô^lô^r I_∞ô^lô^r

図

5: k ≤0

かつ

o^l 6=o^r.

整数

a₁, . . . , a_m

に対して，integer tangle

I_a₁, . . . , I_a_m

からなる図

6

の様なダイア

グラムを

2–bridge diagram

とし，

R(ae ₁, . . . , a_m)

と表す．向き付けられた

2–bridge diagramR(ae ₁, . . . , a_m)

に対して，

i

番目の

integer tangleI_a_i

の北西を通る紐の向き

(4)

を

o^l_i

，北東を通る紐の向きを

o^r_i

とし，この

2-bridge diagram

を

Re^o^l¹^o^r¹(a₁, . . . , a_m)

と表す（図

6

参照）．

o^l₁, o^r₁,(a₁, . . . , a_m)

より

o^l₂, o^r₂, . . . , o^l_m, o^r_m

は計算可能である．

I

_a₁

I

_a₂

I

_a₃

Ia_m−1

I

_a_m

@@

ApppppA

I

_a₁

I

_a₂

I

_a_m

Ia_m−1

@@

ppppp ppppp pp I

m

が奇数

m

が偶数

Re⁺¹⁺¹(a₁, . . . , a_m) Re⁺¹⁻¹(a₁, . . . , a_m)

図

6: 2–bridge diagram

観測 2.4 i≥2

のとき，以下が成り立つ．

o^l_i =











o^r_i₋₁ i

が偶数かつ

a_i₋₁

が偶数

o^l_i₋₁ i

が偶数かつ

a_i₋₁

が奇数

o^l_i₋₂ i

が奇数かつ

ai−2

が偶数

o^r_i₋₂ i

が奇数かつ

a_i₋₂

が奇数

o^r_i =











−o^r₁ if i= 2

o^l_i₋₁ if i

が奇数で

a_i₋₁

が偶数

o^r_i₋₁ if i

が奇数で

ai−1

が奇数

o^r_i₋₂ if i≥4

かつ

i

が偶数かつ

a_i₋₂

が偶数

o^l_i₋₂ if i≥4

かつ

i

が偶数かつ

a_i₋₂

が奇数

3.

アルゴリズム

任意の

n

交点

2–bridge diagram

は

O(n²)

時間で

Tait graph

に変換可能である．

その

Tait graph

から

R(ae ₁, . . . , a_m)

が元の

2–bridge diagram

となる様な整数列

(a₁, . . . , a_m)

は

O(n)

時間で計算可能である

[15]

．ここで

n = |a₁|+· · ·+|a_m|

で

ある．本稿では

(a1, . . . , am)

から

HOMFLY-PT polynomial H(R(ae 1, . . . , am))

を

O(n³)

時間で計算するアルゴリズムを提案する．このアルゴリズムでは重複しな

い

O(n)

個の

をそれぞれ

O(n²)

時間で計算する（図

7

参

照）．補題

3.1, 3.2

で各

がどの様に計算可能か示す．

(5)

H(Reô^l¹ô^r¹(0)) H(Reô^l¹ô^r¹(a1,0)) H(Reô^l¹ô^r¹(a1, . . . , am−1,0))

⇓ ⇓ ⇓

H(Reô^l¹ô^r¹(1)) or H(Reô^l¹ô^r¹(a₁,1)) or H(Reô^l¹ô^r¹(a₁, . . . , a_m₋₁,1)) or H(Reô^l¹ô^r¹(−1)) H(Reô^l¹ô^r¹(a₁,−1)) H(Reô^l¹ô^r¹(a₁, . . . , a_m₋₁,−1))

⇓ ⇓ ⇓

H(Reô^l¹ô^r¹(2)) or H(Reô^l¹ô^r¹(a1,2)) or H(Reô^l¹ô^r¹(a1, . . . , am−1,2)) or H(Reô^l¹ô^r¹(−2)) H(Reô^l¹ô^r¹(a₁,−2)) H(Reô^l¹ô^r¹(a₁, . . . , a_m₋₁,−2))

⇓ ⇓ ⇓

... ⇒ ... ⇒ · · · ⇒ ...

⇓ ⇓ ⇓

H(Reô^l¹ô^r¹(a₁−1)) or H(Reô^l¹ô^r¹(a₁, a₂−1)) or H(Reô^l¹ô^r¹(a₁, . . . , a_m₋₁, a_m−1)) or H(Reô^l¹ô^r¹(a1+ 1)) H(Reô^l¹ô^r¹(a1, a2+ 1)) H(Reô^l¹ô^r¹(a1, . . . , am−1, am+ 1))

⇓ ⇓ ⇓

H(Reô^l¹ô^r¹(a₁)) H(Reô^l¹ô^r¹(a₁, a₂)) H(Reô^l¹ô^r¹(a₁, . . . , a_m₋₁, a_m))

⇓ ⇓

H(Reô^l¹ô^r¹(a₁+ 1)) or H(Reô^l¹ô^r¹(a₁, a₂+ 1)) or H(Reô^l¹ô^r¹(a1−1)) H(Reô^l¹ô^r¹(a1, a2−1))

図

7: 2–bridge diagram

の

の計算

補題 3.1

H(Re^o^l¹^o^r¹(a₁, . . . , a_m))

=











−l⁻²H(Reô^l¹ô^r¹(a₁−2))−l⁻¹mH(Reô^l¹ô^r¹(a₁−1)) o^l_m =o^r_m

かつ

m = 1

−l⁻²H(Re^o^l¹^o^r¹(a1, . . . , am−1, am−2))

−l⁻¹mH(Re^o^l¹^o^r¹(a₁, . . . , a_m₋₁, a_m−1)) o^l_m =o^r_m

かつ

m ≥2

−l²H(Re^o^l¹^o^r¹(a₁−2))−lm o^l_m 6=o^r_m

かつ

m = 1

−l²H(Re^o^l¹^o^r¹(a₁, . . . , a_m₋₁, a_m−2))

−lmH(Re^o^l¹^o^r¹(a₁, . . . , a_m₋₁)) o^l_m 6=o^r_m

かつ

m ≥2 証明

この補題は

Re^o^l¹^o^r¹(a1, . . . , am)

の

m

番目の

integer tangle Iam

o^l_mo^r_m

に補題

2.3

を適用する事により導かれる．

(6)

補題 3.2

H(Re^o^l¹^o^r¹(a1, . . . , am))

=











−lm⁻¹−l⁻¹m⁻¹ m = 1

かつ

a₁ = 0

1 m = 1

かつ

a₁ =±1

または

m = 2

かつ

a₂ = 0

H(Re^o^l¹^o^r¹(a₁∓1)) m = 2

かつ

a₂ =±1 H(Re^o^l¹^o^r¹(a₁, . . . , a_m−2)) m ≥3

かつ

a_m = 0 H(Re^o^l¹^o^r¹(a1, . . . , am−2, am−1∓1)) m ≥3

かつ

am =±1

証明 m = 1

かつ

a₁ = ±1

または

m = 2

かつ

a₂ = 0

の場合は

Reidemeister move

より

Re^o^l¹^o^r¹(±1)

と

Re^o^l¹^o^r¹(a₁,0)

は

trivial knot

である事から導かれる．

m = 1

かつ

a1 = 0

の場合は

Re^o^l¹^o^r¹(0)

と

Re^o^l¹^,⁻^o^r¹(0)

は同じ

link

である事より一般性を失うことなく

o^l₁ =o^r₁

と仮定し

Re^o^l¹^o^r¹(0)

の

integer tangle I₀^o^l¹^o^r¹

に補題

2.3

を適用する事により以下が得られる．

H(Reô^l¹ô^r¹(1)) =−l⁻²H(Reô^l¹ô^r¹(−1))−l⁻¹mH(Reô^l¹ô^r¹(0))

m = 2

かつ

a₂ =±1

の場合は

Re^o^l¹^o^r¹(a₁,±1)

と

Re^o^l¹^o^r¹(a₁∓1)

が

equivalent link

である．

m ≥ 3

かつ

a_m = 0

の場合は

Reidemeister move

より

Re^o^l¹^o^r¹(a₁, . . . , a_m₋₁,0)

と

Re^o^l¹^o^r¹(a₁, . . . , a_m₋₂)

が

equivalent link

である．

m ≥ 3

かつ

a_m = ±1

の場合は

Re^o^l¹^o^r¹(a₁, . . . , a_m₋₁,±1)

と

Re^o^l¹^o^r¹(a₁, . . . , a_m₋₁, a_m∓1)

が

equivalent link

である．

補題

3.3

で図

7

の各

の計算に必要な時間の解析を行う．

補題 3.3 (a1, . . . , am)

を整数列，

o^l₁, o^r₁

を向き，

n = |a1|+ · · · +|am|

とする．

H(Re^o^l¹^o^r¹(a₁, . . . , a_m))

の計算に必要な時間は以下である．

1. m= 1

の場合

O(|a₁|n²)

時間で計算可能である．

2. m= 2

の場合

H(Re^o^l¹^o^r¹(a₁+ 1))

より

O(|a₂|n²)

時間で計算可能である．

3. m≥3

の場合

H(Re^o^l¹^o^r¹(a₁, . . . , a_m₋₂))

と

H(Re^o^l¹^o^r¹(a₁, . . . , a_m₋₂, a_m₋₁+ 1))

より

O(|a_m|n²)

時間で計算可能である．

証明 2–bridge diagram Re^o^l¹^o^r¹(a₁, . . . , a_m)

の

integer tangle I_a₂, . . . , I_a_m

の向き

o^l₂, o^r₂, . . . , o^l_m, o^r_m

は観測

2.4

より

o^l₁, o^r₁

から

O(m)

時間で計算可能である．

1.

補題

3.2

より

H(Re^o^l¹^o^r¹(0)) = −lm⁻¹ −l⁻¹m⁻¹

かつ

H(Re^o^l¹^o^r¹(±1)) = 1

である．観測

2.2

と補題

3.1

より

j = 2, . . . ,|a₁|

に対して

H(Re^o^l¹^o^r¹(±j))

は

H(Re^o^l¹^o^r¹(±j ∓2))

と

H(Re^o^l¹^o^r¹(±j ∓1))

から

O(n²)

時間で計算可能である．

従って

H(Re^o^l¹^o^r¹(a1))

は

O(|a1|n²)

時間で計算可能である

.

On computation of HOMFLY-PT polynomials of 2–bridge diagrams