2011 年 1 月 III 」報告集 研究集会「結び目の数学

「 結び目の数学 III ^」 報告集

2011 ^年 1 ^月

・

2010

年度科学研究費補助金

(

基盤研究

(A))

「結び目理論研究」

研究代表者：河内明夫（大阪市立大学） 研究課題番号：

21244005

・

2010

年度科学研究費補助金

(

基盤研究

(A))

「クライン群とタイヒミュラー空間の大域幾何的研究」

研究代表者：大鹿健一（大阪大学大学院）研究課題番号：

22244005

による援助を受けております。

研究集会の開催に際して、多くの方々のご協力を賜りました。ここに厚く御礼申し上げ ます。

2011

年

1

月 市原一裕・茂手木公彦

（日本大学文理学部）

On Reeb graphs derived from Heegaard splittings with distance 2g . . . . 11 岡崎 真也（大阪市立大学大学院理学研究科）

On a Heegaard surface homeomorphism obtained by bridge position of a knot . . . . 20 佐藤 匡（東京工業大学大学院理工学研究科）

On the Conway potential function introduced by Kauffman . . . . 25 阿部 由紀子（東京工業大学大学院理工学研究科）

The clock number of a knot . . . . 35 北澤 直樹（東京工業大学大学院理工学研究科）

Surgeries on stable maps between low dimensional manifolds . . . . 45 谷口 里奈（奈良女子大学大学院人間文化研究科）

primitive stableの判定アルゴリズムとその応用. . . . 54 森 さなえ（奈良女子大学大学院人間文化研究科）

Hyperbolic Coxeter groupのgrowth functionについて. . . . 64 清水 理佳（大阪市立大学大学院理学研究科）

The span of the warping polynomial of a knot diagram . . . . 74 芦原 聡介（広島大学大学院理学研究科）

曲面絡み目のバイカンドルとch-ダイアグラム. . . . 85 野坂 武史（京都大学数理解析研究所）

曲面結び目のカンドルホモトピー不変量について. . . . 93 阿部 翠空星（京都大学数理解析研究所）

有限体上のAlexander quandleの4-cocycleについて. . . . 102 合田 洋（東京農工大学大学院工学研究院）

(1,1)-knotのunknotting tunnelについて （林 忠一郎氏（日本女子大学）との共同研究）. . . . 108

張 娟姫（広島大学大学院理学研究科）

Bridge numbers of links and minimal numbers of meridian generators of link groups . . . . 115 鮑 園園（東京工業大学大学院理工学研究科）

H(2)-unknotting operation and Heegaard Floer homology . . . . 122 岡崎 建太（京都大学数理解析研究所）

レンズ空間のスピン精密化Reshetikhin-TuraevSU(2)^{不変量について}. . . . 129 福永 知則（北海道大学大学院理学院）

Homotopy classification of monoliteral phrases with four or less letters . . . . 135 佐藤 友美（東京女子大学大学院理学研究科）

不足度2の有限表示群のAlexanderイデアルについて. . . . 142 伊藤 哲也（東京大学大学院数理科学研究科）

Delta-unknotting operations and x-unknotting operations . . . . 166 中村 伊南沙（京都大学数理解析研究所）

Quandle cocycle invariant of a certainT²-link . . . . 172 矢口 義朗（広島大学大学院理学研究科）

Hurwitz同値の分類による２次元ブレイドの無限型不変量. . . . 178 Yo’av Rieck（University of Arkansas）

The Link Volume of 3-manifolds

(joint work with Yasushi Yamashita (Nara Women’s University)) . . . . 185 大城 佳奈子（広島大学大学院理学研究科）

On pallets for coloring invariants of spatial graphs . . . . 192 岡本 美雪（日本工業大学工学部）

完全3部グラフK3,3,3 の3-絡み目射影内在性について （小林一章氏との共同研究）. . . . 198 櫻井 みぎ和（東京女子大学大学院理学研究科）

A new invariant for virtual knots and forbidden moves . . . . 203 今別府 孝規（広島大学大学院理学研究科）

仮想結び目のチェッカーボード彩色について. . . . 213 下川 航也（埼玉大学大学院理工学研究科）

The XerCD-FtsK system unlinks replication catenanes in a stepwise manner

(joint work with Kai Ishihara, Ian Grainge, David J. Sherratt, and Mariel Vazquez) . . . . 222 小谷 賀子（奈良女子大学大学院人間文化研究科）

Taming essential tori in link exteriors . . . . 228 門田 直之（大阪大学大学院理学研究科）

genus-2 Lefschetz fibrationのsingular fiberの最小本数について. . . . 237 八木 潤（高知大学大学院総合人間自然科学研究科）

The primeness of almost alternating link diagrams . . . . 243 花木 良（奈良教育大学教育学部）

Trivializing number of knots . . . . 253

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

村上 雅彦 ( 日本大学 )

^∗1

谷 聖一 ( 日本大学 )

^∗2

竹下 文雄 ( 日本大学大学院 )

^∗3

概 要

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

1. はじめに

Alexander polynomial [1], Jones polynomial[7] ， HOMFLY-PT polynomial[3, 16]

は，いずれも絡み目の分類において有用な代表的不変量である． Alexander polyno- mial は多項式時間で計算可能であるが，自明な結び目と同じ Alexander polynomial を持つ非自明な結び目が知られている．一方， Jones polynomial や HOMFLY-PT polynomial は， Alexander polynomial に比べて絡み目の分別能力が優れている ものの，それらの計算は困難であることが知られている． Jones polynomial は，

L.H. Kauffman [8] により示された捻り数と向き付けられていないダイアグラム

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

O

(n) 次の多項式の 2

^O(n)

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

n

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

^O(√n)

時間に改善した．しかし，一般に Jones polynomial や HOMFLY-PT polynomial の計算は #P–hard である事が F. Jaeger, D.L. Vertigan, D.J.A. Welsh

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

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

そこで，絡み目に妥当な制限を設けた場合の Jones polynomial や HOMFLY-PT polynomial を高速に計算するアルゴリズムの研究も行われている． J.A. Makowsky [9, 10] は，入力の Tait graph の木幅が定数で制限されている場合， Jones poly- nomial は多項式時間で計算可能である事を示した． 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]

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

の HOMFLY-PT polynomial は多項式時間 で計算可能である事を示した． J.A. Makowsky, J.P. Mari˜ no [11] はある定数

k

に

対して

k–algebraic link

の HOMFLY-PT polynomials は多項式時間で計算可能で

ある事を示した．

本稿では， 2–bridge link の HOMFLY-PT polynomial を

n

交点 2–bridge diagram から

O

(n

³

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

2. 準備

定義 2.1 HOMFLY-PT polynomial H

は link diagram の集合から変数

l, m

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

L!

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

H

(

!

) = 1,

lH"

!!!"

#

#

$ #

+

l⁻¹H"

##

#

$

!

!

" #

+

mH"

$ " #

= 0.

ここで，

!

^は任意の trivial knot diagram である．第 2 式において 3 つの link

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

観測 2.2

任意の

n

交点の link diagram の HOMFLY-PT polynomial の次数の絶対 値は

O

(n) ，項数は

O

(n

²

) ，係数の絶対値は

O

(2

^O(n)

) である．

交点の無い 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

I_k

を

I_k^olor

と表す（図 1 参照）．

補題 2.3

H(I_k^olor

) =

$ −l⁻²H(I_k−2^olor

)

−l⁻¹mH(I_k−1^olor

)

o^l

=

o^r

−l²H(I_k−2^olor

)

−lmH

(I

_∞^olor

)

o^l$

=

o^r

% & ' ' ( ') &

0–tangle 3–tangle (

−

2)–tangle

∞

–tangle

I₀⁻¹⁻¹ I₃⁺¹⁺¹ I₋₂⁻¹⁺¹ I_∞⁺¹⁻¹

図 1: Integer tangles と

∞

tangle.

ここで， 3 つの link diagram は示されている integer tangle の周辺以外は同一で ある．

証明 k >

0 の場合は HOMFLY-PT polynomial の定義と Reidemeister move より 明らかである ( 図 2, 3 参照 ) ．

k ≤

0 の場合は HOMFLY-PT polynomial の定義と Reidemeister move より以下が明らかである ( 図 4, 5 参照 ) ．

H(I_k−2^olor

) =

$ −l²H(I_k^olor

)

−lmH

(I

_k−1^olor

)

o^l

=

o^r

−l⁻²H

(I

_k^olor

)

−l⁻¹mH(I_∞^olor

)

o^l$

=

o^r

!

...

' '

...

' '

.. .

' '

I_k^olor I_k−2^olor I_k−1^olor

図 2:

k >

0 かつ

o^l

=

o^r

.

.. .

' (

...

' (

.. .

' (

I_k^olor I_k−2^olor I_∞^olor

図 3:

k >

0 かつ

o^l$

=

o^r

.

.. .

' '

...

' '

...

' '

I_k−2^olor I_k^olor I_k−1^olor

図 4:

k≤

0 かつ

o^l

=

o^r

.

.. .

' (

.. .

' (

...

' (

I_k−2^olor I_k^olor I_∞^olor

図 5:

k≤

0 かつ

o^l $

=

o^r

.

整数

a₁, . . . , a_m

に対して， integer tangle

I_a1, . . . , I_am

からなる図 6 の様なダイア

グラムを

2–bridge diagram

とし，

R(a! ₁, . . . , a_m

) と表す．向き付けられた 2–bridge

diagram

R(a! ₁, . . . , a_m

) に対して，

i

番目の integer tangle

I_ai

の北西を通る紐の向き

を

o^l_i

，北東を通る紐の向きを

o^r_i

とし，この 2-bridge diagram を

R!^ol1or1

(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₃

!"

#$

I

am−1

!"

#$

I

am

! !

"

"

"

"

# !!!!! #

$ %

!"

#$

I

a₁

!"

#$

I

a₂

!"

#$

I

am

!"

#$

I

am−1

! !

! !

&

&

&

&&

!!!!!!

!!!!!!

$ '

m

が奇数

m

が偶数

R!⁺¹⁺¹

(a

₁, . . . , a_m

)

R!⁺¹⁻¹

(a

₁, . . . , a_m

) 図 6: 2–bridge diagram

観測 2.4 i≥

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

o^l_i

=











o^r_i−1 i

が偶数かつ

a_i−1

が偶数

o^l_i−1 i

が偶数かつ

a_i−1

が奇数

o^l_i−2 i

が奇数かつ

a_i−2

が偶数

o^r_i−2 i

が奇数かつ

a_i−2

が奇数

o^r_i

=















−o^r₁

if

i

= 2

o^l_i−1

if

i

が奇数で

a_i−1

が偶数

o^r_i−1

if

i

が奇数で

a_i−1

が奇数

o^r_i−2

if

i≥

4 かつ

i

が偶数かつ

a_i−2

が偶数

o^l_i−2

if

i≥

4 かつ

i

が偶数かつ

a_i−2

が奇数

3. アルゴリズム

任意の

n

交点 2–bridge diagram は

O

(n

²

) 時間で

Tait graph

に変換可能である．

その

Tait graph

から

R(a! 1, . . . , am

) が元の 2–bridge diagram となる様な整数列

(a

₁, . . . , a_m

) は

O

(n) 時間で計算可能である [15] ．ここで

n

=

|a₁|

+

· · ·

+

|a_m|

^で

ある．本稿では (a

₁, . . . , a_m

) から HOMFLY-PT polynomial

H

(

R(a! ₁, . . . , a_m

)) を

O

(n

³

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

い

O

(n) 個の HOMFLY-PT polynomial をそれぞれ

O

(n

²

) 時間で計算する（図 7 参

照）．補題 3.1, 3.2 で各 HOMFLY-PT polynomial がどの様に計算可能か示す．

H(R!^ol1or1

(0))

H(R!^ol1or1

(a

₁,

0))

H(R!^ol1or1

(a

₁, . . . , a_m−1,

0))

⇓ ⇓ ⇓

H

(

R!^ol1or1

(1)) or

H

(

R!^ol1or1

(a

₁,

1)) or

H

(

R!^ol1or1

(a

₁, . . . , a_m−1,

1)) or

H(R!^ol1or1

(

−

1))

H(R!^ol1or1

(a

₁,−

1))

H(R!^ol1or1

(a

₁, . . . , a_m−1,−

1))

⇓ ⇓ ⇓

H

(

R!^ol1or1

(2)) or

H

(

R!^ol1or1

(a

₁,

2)) or

H

(

R!^ol1or1

(a

₁, . . . , a_m−1,

2)) or

H(R!^ol1or1

(

−

2))

H(R!^ol1or1

(a

₁,−

2))

H(R!^ol1or1

(a

₁, . . . , a_m−1,−

2))

⇓ ⇓ ⇓

...

⇒

...

⇒ · · · ⇒

...

⇓ ⇓ ⇓

H(R!^ol1or1

(a

₁−

1)) or

H(R!^ol1or1

(a

₁, a₂−

1)) or

H

(

R!^ol1or1

(a

₁, . . . , a_m−1, a_m−

1)) or

H

(

R!^ol1or1

(a

₁

+ 1))

H

(

R!^ol1or1

(a

₁, a₂

+ 1))

H(R!^ol1or1

(a

₁, . . . , a_m−1, a_m

+ 1))

⇓ ⇓ ⇓

H

(

R!^ol1or1

(a

₁

))

H(R!^ol1or1

(a

₁, a₂

))

H(R!^ol1or1

(a

₁, . . . , a_m−1, a_m

))

⇓ ⇓

H(R!^ol1or1

(a

₁

+ 1)) or

H(R!^ol1or1

(a

₁, a₂

+ 1)) or

H

(

R!^ol1or1

(a

1−

1))

H

(

R!^ol1or1

(a

1, a2−

1))

図 7: 2–bridge diagram の HOMFLY-PT polynomial の計算

補題 3.1

H

(

R!^ol1or1

(a

₁, . . . , a_m

))

=





















−l⁻²H

(

R!^ol1or1

(a

₁−

2))

−l⁻¹mH

(

R!^ol1or1

(a

₁−

1))

o^l_m

=

o^r_m

かつ

m

= 1

−l⁻²H

(

R!^ol1or1

(a

₁, . . . , a_m−1, a_m−

2))

−l⁻¹mH

(

R!^ol1or1

(a

₁, . . . , a_m−1, a_m−

1))

o^l_m

=

o^r_m

かつ

m≥

2

−l²H(R!^ol1or1

(a

₁−

2))

−lm o^l_m$

=

o^r_m

かつ

m

= 1

−l²H(R!^ol1or1

(a

₁, . . . , a_m−1, a_m−

2))

−lmH(R!^ol1or1

(a

₁, . . . , a_m−1

))

o^l_m$

=

o^r_m

かつ

m≥

2

証明

この補題は

R!^ol1or1

(a

₁, . . . , a_m

) の

m

番目の integer tangle

I_am^olmorm

に補題 2.3

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

!

補題 3.2

H(R!^ol1or1

(a

1, . . . , am

))

=















−lm⁻¹−l⁻¹m⁻¹ m

= 1 かつ

a₁

= 0

1

m

= 1 かつ

a₁

=

±

1 または

m

= 2 かつ

a₂

= 0

H

(

R!^ol1or1

(a

₁∓

1))

m

= 2 かつ

a₂

=

±

1

H

(

R!^ol1or1

(a

₁, . . . , a_m−2

))

m≥

3 かつ

a_m

= 0

H

(

R!^ol1or1

(a

₁, . . . , a_m−2, a_m−1∓

1))

m≥

3 かつ

a_m

=

±

1

証明 m

= 1 かつ

a₁

=

±

1 または

m

= 2 かつ

a₂

= 0 の場合は Reidemeister move より

R!^ol1or1

(

±

1) と

R!^ol1or1

(a

1,

0) は trivial knot である事から導かれる．

m

= 1 かつ

a₁

= 0 の場合は

R!^ol1or1

(0) と

R!^ol1,−or1

(0) は同じ link である事より一般 性を失うことなく

o^l₁

=

o^r₁

と仮定し

R!^ol1or1

(0) の integer tangle

I₀^ol1or1

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

H(R!^ol1or1

(1)) =

−l⁻²H(R!^ol1or1

(

−

1))

−l⁻¹mH

(

R!^ol1or1

(0))

m

= 2 かつ

a₂

=

±

1 の場合は

R!^ol1or1

(a

₁,±

1) と

R!^ol1or1

(a

₁∓

1) が equivalent link で ある．

m ≥

3 かつ

a_m

= 0 の場合は Reidemeister move より

R!^ol1or1

(a

₁, . . . , a_m−1,

0) と

R!^ol1or1

(a

₁, . . . , a_m−2

) が equivalent link である．

m ≥

3 か つ

a_m

=

±

1 の 場 合 は

R!^ol1or1

(a

₁, . . . , a_m−1,±

1) と

R!^ol1or1

(a

₁, . . . , a_m−1, a_m∓

1) が equivalent link である．

!

補題 3.3 で図 7 の各 HOMFLY-PT polynomial の計算に必要な時間の解析を行う．

補題 3.3

(a

₁, . . . , a_m

) を整数列，

o^l₁

,

o^r₁

を向き，

n

=

|a₁|

+

· · ·

+

|a_m|

^とする．

H(R!^ol1or1

(a

₁, . . . , a_m

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

1.

m

= 1 の場合

O

(

|a₁|n²

) 時間で計算可能である．

2.

m

= 2 の場合

H

(

R!^ol1or1

(a

₁

+ 1)) より

O

(

|a₂|n²

) 時間で計算可能である．

3.

m≥

3 の場合

H

(

R!^ol1or1

(a

₁, . . . , a_m−2

)) と

H

(

R!^ol1or1

(a

₁, . . . , a_m−2, a_m−1

+ 1)) よ り

O

(

|a_m|n²

) 時間で計算可能である．

証明

2–bridge diagram

R!^ol1or1

(a

1, . . . , am

) の integer tangle

Ia2, . . . , Iam

の向き

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

は観測 2.4 より

o^l₁, o^r₁

から

O

(m) 時間で計算可能である．

1. 補題 3.2 より

H(R!^ol1or1

(0)) =

−lm⁻¹ − l⁻¹m⁻¹

かつ

H(R!^ol1or1

(

±

1)) = 1 で ある．観測 2.2 と補題 3.1 より

j

= 2, . . . ,

|a₁|

^に対して

H(R!^ol1or1

(

±j))

は

H(R!^ol1or1

(

±j∓

2)) と

H

(

R!^ol1or1

(

±j ∓

1)) から

O

(n

²

) 時間で計算可能である．

従って

H(R!^ol1or1

(a

₁

)) は

O

(

|a₁|n²

) 時間で計算可能である .

2. 補題 3.2 より

H(R!^ol1or1

(a

₁,

0)) = 1 かつ

H

(

R!^ol1or1

(a

₁,±

1)) =

H(R!^ol1or1

(a

₁∓

1)) である．観測 2.2 と補題 3.1 より

j

= 2, . . . ,

|a₂|

^に対して

H(R!^ol1or1

(a

₁,±j))

は

H(R!^ol1or1

(a

₁,±j∓

2)) と

H

(

R!^ol1or1

(a

₁,±j∓

1)) から

O

(n

²

) 時間で計算可能で ある．従って

H(R!^ol1or1

(a

₁, a₂

)) は

H(R!^ol1or1

(a

₁±

1) から

O

(

|a₂|n²

) 時間で計算 可能である．

3. 補題 3.2 より

i

= 3, . . . , m に対して

H(R!^ol1or1

(a

₁, . . . , a_i−1,

0)) =

H(R!^ol1or1

(a

₁, . . . , a_i−2

)) か つ

H(R!^ol1or1

(a

₁, . . . , a_i−1,±

1)) =

H(R!^ol1or1

(a

₁, . . . , a_i−2, a_i−1 ∓

1)) で あ る ．観 測 2.2 と 補 題 3.1 よ り

i

= 3, . . . , m と

j

= 2, . . . ,

|a_i|

^に対して

H(R!^ol1or1

(a

₁, . . . , a_i−1,±j))

は

H(R!^ol1or1

(a

₁, . . . , a_i−1,±j∓

2)) と

H(R!^ol1or1

(a

₁, . . . , a_i−1,±j∓

1)) から

O

(n

²

) 時間で計算可能である．従って

i

= 3, . . . , m に対して

H

(

R!^ol1or1

(a

1, . . . , ai

)) は

H

(

R!^ol1or1

(a

₁, . . . , a_i−2

) と

H(R!^ol1or1

(a

₁, . . . , a_i−2, a_i−1±

1) から

O

(

|a_i|n²

) 時

間で計算可能である．

!

2–bridge diagram の HOMFLY-PT polynomial を効率的に計算する

Pro- cedure 2–bridge

を 提 案 す る ．こ の procedure は ま ず 図 7 の HOMFLY- PT polynomial

H(R!^ol1or1

(a

₁

)),. . . , H(

R!^ol1or1

(a

₁, . . . , a_m

)), H(

R!^ol1or1

(a

₁

+ 1)), . . .,

H(R!^ol1or1

(a

₁, . . . , a_m−1, a_m

+ 1)) の計算の必要性を判定し（表 1 参照），必要と 判定された HOMFLY-PT polynomial のみを図 7 に示された順番で補題 3.1 と 3.2 より計算する．

i H(R!^ol1or1

(a

₁, . . . , a_i

))

H

(

R!^ol1or1

(a

₁, . . . , a_i−1, a_i

+ 1)) 1 必要または不要 必要または不要

.. . .. . .. .

m

必要または不要 必要または不要

表 1: 各 HOMFLY-PT polynomial の計算の必要性の判定

Procedure 2–bridge

入力：

整数列 (a

₁, . . . , a_m

) ，向き

o^l₁

,

o^r₁ 出力：H

(

R!^ol1or1

(a

₁, . . . , a_m

)).

{

^各 HOMFLY-PT polynomial の計算の必要性の判定開始

} fori:=

1

tom do

H

(

R!^ol1or1

(a

₁, . . . , a_i

)) と

H

(

R!^ol1or1

(a

₁, . . . , a_i−1, a_i

+ 1)) を不要で初期化

; H(R!^ol1or1

(a

₁, . . . , a_m

)) の計算を必要とする

;

fori:= mto

3

do

ifH(R!^ol1or1

(a

₁, . . . , a_i

)) か

H(R!^ol1or1

(a

₁, . . . , a_i−1, a_i

+ 1)) の計算の必要

then if o^l_i

=

o^r_i

then H(R!^ol1or1

(a

₁, . . . , a_i−2

)) と

H

(

R!^ol1or1

(a

₁, . . . , a_i−2, a_i−1

+ 1)) の計算を

then

必要とする

else begin

if H(R!^ol1or1

(a

1, . . . , ai

)) の必要かつ

ai

が偶数または

if H(R!^ol1or1

(a

1, . . . , ai−1, ai

+ 1)) の必要かつ

ai

が奇数

then H(R!^ol1or1

(a

₁, . . . , a_i−2

)) の必要性を必要にする

; if H(R!^ol1or1

(a

₁, . . . , a_i

)) の必要かつ

a_i

が奇数または

if H(R!^ol1or1

(a

₁, . . . , a_i−1, a_i

+ 1)) の必要かつ

a_i

が偶数

then H(R!^ol1or1

(a

₁, . . . , a_i−2, a_i−1

+ 1)) の必要性を必要にする

; end;

ifm≥

2

then

if H(R!^ol1or1

(a

₁, a₂

)) か

H

(

R!^ol1or1

(a

₁, a₂

+ 1)) が必要

then if o_l2

=

o_r2

then H(R!^ol1or1

(a

₁

+ 1)) の必要性を必要にする

else

if H(R!^ol1or1

(a

₁, a₂

)) が必要かつ

a₂

が奇数または

if H(R!^ol1or1

(a

₁, a₂

+ 1)) が必要かつ

a₂

が偶数

then H(R!^ol1or1

(a

₁

+ 1)) の必要性を必要にする ;

end;

{

^各 HOMFLY-PT polynomial の計算の必要性の判定終了

} fori:=

1

tom do begin

if H(R!^ol1or1

(a

₁, . . . , a_i

)) が必要

thenH

(

R!^ol1or1

(a

₁, . . . , a_i

)) を計算

;

if H(R!^ol1or1

(a

₁, . . . , a_i−1, a_i

+ 1)) が必要

H(R!^ol1or1

(a

₁, . . . , a_i−1, a_i

+ 1)) を計算

; end;

補題 3.3 より以下の定理が導かれる．

定理 3.4 D

=

R!^ol1or1

(a

₁, . . . , a_m

) を

n

交点 2–bridge diagram とする．

Procedure 2–bridge

は

H

(D) を整数列 (a

₁, . . . , a_m

) と向き

o^l₁

,

o^r₁

から

O

(n

³

) 時間で計算する．

即ち

H

(D) は

D

から

O

(n

³

) 時間で計算可能である．

4. 計算機実験

任意の 2–bridge link はある標準的な 2–bridge diagram で表現可能である．ここで 標準的な 2–bridge diagram とは

R!^ol1or1

(a

₁, . . . , a_m

) （

i

が偶数のとき

a_i <

0 ，

i

が奇 数のとき

a_i>

0 ）で表現される 2–bridge diagram である．

本稿では

n

交点 2–bridge diagram の整数列表現からその HOMFLY-PT polyno-

mial を

O

(n

³

) 時間で計算するアルゴリズムを提案した．このアルゴリズムを実装

し 95 交点以下の 2–bridge diagram の HOMFLY-PT polynomial を計算するプロ

グラムを作成した．プログラムを 34 交点以下の全ての標準的な 2–bridge diagram

の HOMFLY-PT polynomial を 4 台の計算機を用いて計算した（表 2 参照）．表 3

では計算に要した時間を交点数ごとに示している． 19 交点以下の場合はそれぞれ

1 秒未満で計算された．また HOMFLY-PT polynomial 1 個あたり 1 秒未満で計算 された．

CPU Intel Core 2 Duo 2.53 GHz, 2.4 GHz メモリ 4GB

OS Mac OS X 10.6.5 言語 C 言語

表 2: 実験環境

交点数 標準的な 2–bridge diagram の数 時間（秒）

20 524,801 1

21 1,049,258 3

22 2,098,177 5

23 4,195,668 12

24 8,390,657 25

25 16,779,946 80

26 33,558,529 126

27 67,114,324 291

28 134,225,921 588

29 268,446,378 1,868

30 536,887,297 2,815

31 1,073,763,668 6,421

32 2,147,516,417 12,567

33 4,295,010,986 33,647

34 8,590,000,129 60,413

表 3: 計算時間

5. 今後の課題

本稿で提案した 2–bridge diagram からその HOMFLY-PT polynomial を計算する

アルゴリズムを他の基本的な絡み目や不変量に拡張する事が今後の課題としてあ

げられる．また，実装したプログラムの扱える整数の範囲を拡張する事により 96

交点以上の 2–bridge diagram の HOMFLY-PT polynomial を計算可能とする事も

今後の課題としてあげられる．

参考文献

[1] J.W. Alexander, Topological invariants of knots and links, Trans. Amer. Math.

Soc. 30 (1928) 275–306.

[2] Y. Diao, C. Ernst, U. Ziegler, Jones polynomial of knots formed by repeated tangle replacement operations, Topol. Appl.156 (2009) 2226–2239.

[3] P. Freyd, D. Yetter, J. Hoste, W.B.R. Lickorish, K. Millett, A. Ocneanu A new polynomial invariant of knots and links, Bull. Amer. Math. Soc. 12 (1985), 239- 246.

[4] M. Hara, M. Murakami, S. Tani, M. Yamamoto, A fast Algorithm for comput- ing Jones polynomials of Montesinos links, Scientiae Mathematicae Japonicae 69 (2009) 1–26.

[5] M. Hara, S. Tani, M. Yamamoto, A polynomial-time algorithm for computing the Jones polynomials of arborescent links, in: Information Technology Letters, vol.

1, 2002, pp. 16–17 (in Japanese).

[6] F. Jaeger, D.L. Vertigan, D.J.A. Welsh, On the computational complexity of the Jones and Tutte polynomials, Math. Proc. Cambridge Philos. Soc.108 (1990) 35–

53.

[7] V.F.R. Jones, A polynomial invariant for knots via Von Neumann algebras,Bull.

Amer. Math. Soc. 12 (1985) 103–111.

[8] L.H. Kauffman, State models and the Jones polynomial,Topology 26 (1987) 395–

407.

[9] J.A. Makowsky, Colored Tutte polynomials and Kauffman brackets for graphs of bounded tree width, in: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2001, pp. 487–495.

[10] J.A. Makowsky, Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width, Discrete Appl. Math.145 (2005) 276–290.

[11] J.A. Makowsky, J.P. Mari˜no, The parametrized complexity of knot polynomials, J. Comp. Sys. Sci. 67 (2003) 742-756.

[12] J. Mighton, Knot Theory on Bipartite Graphs, Ph.D. Thesis, Dept. of Math., University of Toronto, Canada, 1999.

[13] J. Mighton, Computing the Jones polynomial on bipartite graphs,J. Knot Theory Ramifications 10 (5) (2001), 703–710.

[14] H.R. Morton, H.B. Short, Calculating the 2-variable polynomial for knots pre- sented as closed braids,J. Algorithms 11 (1) (1990), 117–131.

[15] M. Murakami, M. Hara, S. Tani, M. Yamamoto, Fast algorithms for computing Jones polynomials of Certain links, Theor. Comput. Sci.374 (2007) 1–24.

[16] J. Przytycki, P. Traczyk, Conway Algebras and Skein Equivalence of Links,Proc.

Amer. Math. Soc. 100 (1987), 744–748.

[17] K. Sekine, H. Imai, K. Imai, Computation of Jones Polynomial,Trans. Japan Soc.

Ind. Appl. Math.8 (3) (1998) 341–354 (in Japanese).

[18] T. Utsumi, K. Imai, Computation of the Jones Polynomials for Pretzel Links, IPSJ SIG Tech. Rep. (085) (2002) 43–48 (in Japanese).

[19] D.J.A. Welsh, Complexity: Knots, Colorings and Counting, Cambridge Univ.

Press, Cambridge, 1993.

井戸 絢子 奈良女子大学大学院 人間文化研究科

によって導入された の の概念は， 次元多様 体を調べる上で有効であることが多くの研究者によって示されている．例えば，

は次のことを示している

の に対して，

その が を満たすならば次が成り立つ．

は の である．

任意の は に である．

加えて の に対して， が成り立つな

らば， は もしくは の に である．

上記の結果を と が種数 のときに限って考えると， ならば と は であることが分かる． と が種数 のとき，

は次のことを示している．

と は に含まれる種数 の とする．このとき ならば と は である．

よって， と が種数 のとき の結果は改良できること が分かる．以上のことから，ここでは と が種数 の場合を考えたい．つまり，

と は に含まれる の とする．このとき ならば と は であるか？

上記の に対する解答を得ることはできていないが，この を 扱うための方法として， ならば に対して をある標準的に位置にす ることができるということを本稿では報告する．

主結果 と は が 以上の の種数 の とする．今 のとき， の によって構成される の は下図 の形にできる．

1

1 2

3

3

2g‑1

2g‑1 2g‑2

2g‑3

2g‑3

si‑ε sj+ε

図

以下 を の とする．

は で種数が 以上とする．このとき，

次のようにして得られる を の という

は 上の の に対応している．

つの に対応する 上の が ならば，その つの は で繋がれる．

を の つの とする．このとき と の を次 で定義する．

  は の を す

る に対応する の の部分集合とする．このとき の を次で定義する．

の に対して，

を の とする このとき， における の補空間 は に同相であるから

と分解することができる．このことから 次を満たす が存在することが分かる

．

各 に対して， は に ．

このような を の という

の に対して， の議論と

のアイデアを用いることにより，次のような が得られえる． ここでは，

必要となる の条件のみをあげる．詳しくは昨年の結び目の数学 の報告集 ， 及び の補題 を参照

は の での とする．

は有限個の を除いて，横断的に交わっ

ている．

において， は つの もしくは

を除いて，横断的に交わっている．

において， の各成分は 上で な になっ

ている．

上記に加えて，次の条件を満たすような は上記の条件の

中の が存在する．

十分小さい に対して，

は の を する を含む

は の を する を含む

に対して， の各成分は 上でも 上でも な になっている．

図

は前の のとおりとする．

上の点全体の集合に次のような同値関係を入れる．

と は の同じ成分に含まれる この同値関係による の商空間 を から誘導される と呼ぶ．

図

の に対応する を とし，対応する

の を とする．また は か

ら誘導される関数とする．このとき， の各 上の点は， 上でも 上でも な に対応していることに注意する．この に次の ような番号付けのルールを導入する．

図