の判定アルゴリズムとその応用

(1)

.

.. .

.

primitive stable

の判定アルゴリズムとその応用

谷口里奈

奈良女子大学大学院人間文化研究科情報科学専攻

2010年12月20日

谷口里奈(奈良女子大学) primitive stableの判定アルゴリズムとその応用 2010年12月20日 1 / 40

(2)

. .

1 研究背景

メビウス変換

2元生成メビウス変換群

Farey triangulationとMarkov写像 BowditchのQ条件(BQ条件) Schottky群

primitive stable

.

. .

2 primitive stableについて

研究目的

primitive stableの判定アルゴリズム

.

. .

3 primitive stableの判定アルゴリズムの実装

primitive stableと離散群研究結果1

primitive stableとBQ条件研究結果²

(x,y,z)=(x,x,x) (x,y,z)=(x,_x^x₋₁,_x^x₋₁)

.

. .

4 まとめと今後の課題

(3)

メビウス変換

.

.. .

.

与えられた4つの複素数a,b,c,dがad−bc =1を満たす時、複素数zから以下の式への変換をメビウス変換という

T(z) = az+b cz+d

このメビウス変換を2×2行列に対応させ、T全体からなる集合を以下のように定義する

SL(2,C)=

{( a b c d

) a,b,c,d∈ C ad−bc=1

}

(4)

2

元生成メビウス変換群

2

元生成メビウス変換群

.

.. .

.

a,b∈SL(2,C)

a,bで生成される群を2元生成メビウス変換群という

M : {ρ: F2=< a,b>→SL(2,C)} MにはSL(2,C)が共役により作用

.

.. .

. .

共役による作用とは、

c∈SL(2,C)

ρ(a)∈SL(2,C)をcρ(a)c⁻¹とすることである

この作用による商空間Xをcharacter varietyと呼ぶ X = M//SL(2,C)

= {(x,y,z)|x,y,z∈C}

M → X:(a,b)→(t r(a),t r(b),t r(ab))

(5)

Farey triangulation

と

Markov

写像

Farey triangulation

.

.. .

.

単位円板を無限個の三角形で分割する方法の1つ

(6)

Markov

写像

.

.. .

.

(x,y,z)∈ X

V:Farey triangulationの頂点全体の集合

%:V →Cを以下で定義

%(v1)= x, %(v2)= y, %(v3)= z その他の頂点については次の規則で定義

%(w₄)=%(w₁)%(w₂)−%(w₃)

%を(x,y,z)から定まるMarkov写像と呼ぶ

(7)

Bowditch

の

Q

条件

(BQ

条件

)

BQ条件はFarey triangulationとMarkov写像を用いて考えることができる

定義

(Bowditch,1994)

.

.. .

.

(x,y,z)∈ Xに対し、%が以下の2つを満たす時、BQ条件を満たすという任意の頂点v ∈ Vに対して%(v) <[−2,2]

|%(v)| ≤2となる頂点v∈ Vは有限個

(8)

Schottky

群

定義

(Schottky

群)

.

.. .

.

n元生成メビウス変換群{g₁,· · · ,g_n}^が^Schottky^{群であるとは、}

2n個の互いに交わらないclosed disk D₁,D⁰

1,· · · ,D_n,D⁰_nが存在して、

giがDiをD⁰

iの外に移す時である

(9)

F= F_n:{x₁,x₂,· · · ,x_n}^{で生成される自由群} Γ^:F=< x1,· · · ,xn>^のCayley graph(Word tree) B :{x1,· · · ,xn,x⁻¹

1 ,· · · ,x⁻¹_n }からなる両側無限既約文字列全体 ω˜:primitive wordω∈ Fを繰り返した両側無限文字列

primitive word

.

.. .

. .

ω ∈ Fがprimitive wordとは、f ∈ ^Aut(F)と xi ∈ {x1,· · ·,xn,x⁻¹

1 ,· · · ,x⁻_n¹}が存在して以下を満たす時である f (xi) =ω

P={ω|ω˜ はprimitive stable}はΓ内の両側無限道を定める

(10)

.

.. .

.

注意、m∈SL(2,C)はポアンカレ拡張によりH³に作用する ω:(Fの要素)↔(Γの点)、x ∈H³、ρ∈M

ω→ρ(ω)(x)(∈H³)により、τρ,x :Γ→H³が定まる

.

定義

(primitive stable)(Minsky,2009)

.

.. .

.

ρ : Fn→SL(2,C)がprimitive stableとは、

定数K, δ、点x(∈ H³)が存在して、

τ_ρ,xがPの全ての道(∈ Γ⁾を(K, δ)-quasi-geodesicに移す時である

●primitive stableの例、

.

(Minsky,Moriah)

.

.. .

.

以下のようなメビウス変換の列{ρn}を構成した ρn: F_n→SL(2,C)

ρn∈ D ∩ PS n→ ∞

ρnは結び目の双曲構造に収束する

(11)

メビウス変換のポアンカレ拡張

.

.. .

.

L=(

1 0

0 1

)

,I=(

i 0

0 −i )

,J=(

0 1

−1 0 )

,K=(

0 i

i 0

)

. .

.. .

.

T(z)= ^az_cz⁺₊_d^bのポアンカレ拡張はT(ξ)=( Aξ+B)(Cξ+D)⁻¹である

.

1 基点x=(x,y,t)∈H³、ρ(ω)=

( a b c d

) を代入

.

2 基点xを2×2行列型に変換

(x,y,t)∈H³ →xL+yI+tJ=ξ

.

3 ρ(ω)= ( a b

c d )

の各要素a,b,c,d∈Cをそれぞれ2×2行列型に変換

a = ar+aii A = arL+aiI=

( ar+aii 0 0 ar−aii

) (b,c,dも同様)

.

4 T(ξ)を計算→2×2行列型からxL+yI+tJを使って(x,y,t)型に変換

(12)

(K, δ)-quasi-geodesic

.

.. .

.

h :R→H³が(K, δ)-quasi-geodesicとは、

任意のm,n∈ Rに対して以下が成り立つ時である

1

K|m−n| −δ≤ d(h(m),h(n))≤ K|m−n|+δ

|m−n|^:2点m,n間の距離

d(h(m),h(n)):2点h(m),h(n)間の双曲距離

(13)

の未解決問題

”ON DYNAMICS OF Out(F_n)ON PSL₂(C)CHARACTERS”

において、Yair N.Minskyは以下の未解決問題を挙げている Question(1)

.

.. .

.

(x,y,z)∈ X^がprimitive stableかどうかを判定するアルゴリズムはあるか？

D ⊂ X^{:離散群に対応する}X^の集合

.

Question(2)

.

.. .

.

Xの3つの部分集合BQ,PS,Dの関係性は？

(14)

研究目的

(x,y,z)がprimitive stableかどうかを判定するアルゴリズムはまだ知られていない

.

.. .

.

1

primitive stableの判定アルゴリズムを2元生成の場合において提案する

↓ S ⊂ X:Schottky群に対応するXの集合⊂ D

Minskyはあるρ∈ PSについて、ρ<Sを示すことによって

(X − D)∩ PS,φを示したが、具体的なパラメータは示していない

.

.. .

.

2

離散的でないprimitive stableρを発見することによって、(X − D)∩ PS の具体的なパラメータを求め、primitive stableと離散群の関係性を調べる

. .

.. .

.

3

primitive stableとBQ条件の関係性を調べる

(15)

の判定アルゴリズム

補題

(Minsky,2009)

.

.. .

.

1 ρ^が^Schottky→ρ^はprimitive stable

.

2 primitive stableはopen condition

.

3 ρがprimitive stable→Fの全てのproper free factorAにおいて、

ρ|AはSchottky

今回はこの補題の² の証明で述べられているquasi-geodesicの条件を使用して、primitive stableの判定アルゴリズムを考える

(16)

quasi-geodesic

の条件

ρ∈ M

x∈ H³

τ =τ_ρ,x: Γ→H³ ω=primitive word

ω˜^:ωを繰り返した両側無限文字列

L∈ Γ^:ω˜ に対応した道(primitive leaf)={· · · ,v₋₂,v₋₁,v₀,v₁,v₂,· · · } pi =τ(vi)(∈ H³)

τ|L

が

quasi-geodesic

であるための十分条件

(Minsky)

.

.. .

.

c >0とk ∈Nが存在して、以下を満たす時である

.

.. .

.

P_i:[ p_i,p_i₊_k]の垂直2等分面とする全ての jに対して、

PjkはP( j+1)kをP( j−1)kから引き離す d(P_jk,P_{( j}₊_1)k) > c

(17)

.

.. .

.

長さ3k以下のprimitive wordにおいて、τ|Lがquasi-geodesicである条件が成立

⇓

.

.. .

.

全てのprimitive wordにおいて、τ|Lがquasi-geodesicである条件が成立

成立理由:

primitive word作成に、Jane GilmanとLinda Keenが

”ENUMERATING PALINDROMES AND PRIMITIVES IN RANK TWO FREE GROUPS”において示した方法を使用

この方法を用いて作成したprimitive wordの性質によって成立する

⇓

. .

.. .

.

ρ ∈ Mはprimitive stableである

有限個のprimitive wordでquasi-geodesicの判定をすることによって、primitive

stableの判定アルゴリズムを考えることが可能となる

(18)

primitive word

の作成方法

(Jane Gilman,Linda Keen)

.

.. .

.

F2 =< A,B>

.

Enumeration Scheme for positive rationals

.

.. .

.

E⁰

1 = A⁻¹,E¹

0 = B,E¹

1 = A⁻¹B

p

q = ^m_n₊⁺_s^r(^m_n < _q^p < ^r_s)

.

1 もしp×q=奇数 ⇒ E^p

q = E^r

sE^m

n

.

2 もしp×q=偶数 ⇒ E^p

q = E^m

nE^r

s

.

Enumeration Scheme for negative rationals

.

.. .

.

E0

1 = A,E1

0 = B,E−1

1 = B A

p

q = ^m_n₊⁺_s^r(^r_s < ^p_q < ^m_n)

.

1 もしp×q=奇数 ⇒ E^p

q = E^r

sE^m

n

.

2 もしp×q=偶数 ⇒ E^p

q = E^m

nE^r

s

(19)

アルゴリズム概要

.

1 パラメータ(x,y,z)を代入⇒2×2行列a,b(∈SL(2,C))に変換

.

Indra’s Pearls

に表記されている方法

.

.. .

.

^.

1 複素数のパラメータ(ta,tb,tab)を代入

.

2 t_C = t²_a+t²

b+t²

ab−t_at_bt_ab−2を計算

.

3 Q= √

2−tCを計算

.

4 R=±√

tC+2と定義する

.

5 z0 = _t_b^(t_t^ab_ab⁻₋^2)(t_2t_a₊^b⁺_iQt^R)_ab を計算

.

6 2元生成群を2×2行列に変換

a=





ta

2

t_at_ab−2t_b+2iQ (2t_ab+4)z₀ (t_at_ab−2t_b−2iQ)z₀

2tab−4

t_a 2



,b =





t_b−iQ 2

t_bt_ab−2t_a−iQt_ab (2t_ab+4)z₀ (t_bt_ab−2t_a+iQt_ab)z₀

(2tab−4)

t_b+iQ 2





(20)

.

2 kの値を設定し、3k以下の長さのprimitive wordをリストアップ (= ω⁾

⇒リストアップしたwordを繰り返して長さ3kの文字列にする (= ω˜⁾

.

3 基点 p₁ =(0,0,1)(∈H³)

文字列ω˜ をa,b(∈ SL(2,C))によって、行列に変換(=ρ( ˜ω))) ρ0, ρ1, ρ2を計算

.

4 基点 p₁とρ0, ρ1, ρ2から、メビウス変換のポアンカレ拡張より p₀,p₂,p₃(∈ H³)を求め、垂直2等分面P₀,P₁,P₂を計算

P0:[ p0,p1]の垂直2等分面 P1:[ p1,p2]の垂直2等分面 P2:[ p2,p3]の垂直2等分面

(21)

.

5 求めたP₀,P₁,P₂からquasi-geodesicの判定

P1がP0をP2から引き離していたら、quasi-geodesicである

.

6 長さ3k以下のprimitive wordにおけるquasi-geodesicの判定結果より代入したパラメータ(x,y,z)はprimitive stableであるかを判定

.

.. .

.

もし長さ3k以下の全てのprimitive wordにおいてquasi-geodesicの条件を満たしていたらprimitive stableと判定

長さ3k以下の全てのprimitive wordにおいて1つでもquasi-geodesicの条件を満たさなかったら、² のkの値を変更して3k以下の長さのprimitive wordをリストアップするところから始める

primitive stableと判定されるまでこの動作を繰り返す

(22)

の判定アルゴリズムの実装

primitive stableの判定アルゴリズムの実装をすることによって、以下の2

点について調べる

.

.. .

. .

離散的でないprimitive stableρを発見し、(X − D)∩ PS, φを示す具体的なパラメータ

primitive stableとBQ条件の関係性

(23)

と離散群

.

.. .

.

離散的でないprimitive stableρを発見することによって、(X − D)∩ PS の具体的なパラメータを求める

⇓

離散的でないパラメータを求めて、primitive stableの判定アルゴリズムでprimitive stableを探す

(24)

命題

(Jorgensen)

.

.. .

.

a,b ∈SL(2,C) t r(a) = t r(b)

< a,b>が離散的ならば、以下の式を満たす

|t r(aba⁻¹b⁻¹)−2| > 1 8 ここで、

t r(aba⁻¹b⁻¹) = x²+y²+ z²−xyz−2

⇓

.

.. .

.

|(x²+y²+z²−xyz−2)−2| ≤ ¹₈ x= y

⇒< a,b >^{は離散的でない}

. .

.. .

.

この条件を満たすパラメータを使用して、実験を行う

(25)

k=30の場合

赤:PS満たす ^(x^{軸:複素数}^x^{の実部、y}^{軸:複素数}^x^の虚部)

左:(x,y,z)=(x,x,z|x²+y²+z²−xyz−4=₁₆¹)、右:(x,y,z)=(x,x,z|x²+y²+z²−xyz−4= ₂₀¹)

(26)

と

BQ

条件

.

.. .

.

primitive stableとBQ条件の関係性を調べる

⇓

既存のBQ条件を判別するアルゴリズムを使用して、primitive stableと BQ条件の描画結果を比較することによって、関係性を調べていく

(27)

(x,y,z)=(x,x,x) k= 10の場合

緑:PSとBQ両方満たす、赤:BQのみ満たす ^(x軸:複素数xの実部、y軸:複素数xの虚部)

(28)

研究結果

²(primitive stable

と

BQ

条件の関係性

) (x,y,z)=(x,x,x) k= 30の場合

(29)

(x,y,z)=(x,x,x) k= 50の場合

(30)

研究結果

と

BQ

条件の関係性

) (x,y,z)=(x,x,x) k= 80の場合

(31)

(x,y,z)=(x,x,x) k= 100の場合

(32)

研究結果

と

BQ

条件の関係性

) (x,y,z)=(x,x,x) k= 130の場合

(33)

(x,y,z)=(x, _x₋^x₁,_x₋^x₁) (x=³⁺^√₂⁻³ とした時、8の字結び目の双曲構造を表す)

k =10の場合

(34)

研究結果

と

BQ

条件の関係性

) (x,y,z)=(x, _x₋^x₁,_x₋^x₁) (x=³⁺^√₂⁻³ とした時、8の字結び目の双曲構造を表す)

k =20の場合

(35)

k =30の場合

(36)

研究結果

と

BQ

条件の関係性

) (x,y,z)=(x, _x₋^x₁,_x₋^x₁) (x=³⁺^√₂⁻³ とした時、8の字結び目の双曲構造を表す)

k =50の場合

(37)

k =80の場合

(38)

まとめ

Question(1)(primitive stable

の判定アルゴリズム)(Minsky)

.

.. .

.

未解決問題であった(x,y,z) ∈ Xがprimitive stableかどうかを判別するアルゴリズムを2元生成の場合において作成し、実装することに成功した

(39)

Question(2)(BQ,PS,D

の関係性)(Minsky)

.

.. .

.

primitive stable

と離散群の関係性

.

.. .

.

離散群でないパラメータ(x,y,z)= (x,x,z|x²+y²+ z²−xyz−4 = ₁₆¹), (x,y,z)=(x,x,z|x²+y²+ z²−xyz−4= ₂₀¹)において、primitive stable の存在が確認された

⇒

Minskyが数学的に証明した(X − D)∩ PS, φを、計算機を用いて数値

的に証明できた

.

primitive stable

と

BQ

条件の関係性

.

.. .

.

kの値を増やすごとに、primitive stableを満たす部分がBQ条件を満たす部分と満たさない部分の境界線に近付いていくことが観察された

⇒PS= BQが成り立つことが期待される

(40)

今後の課題

(Minsky,Moriah,2010)

.

.. .

.

以下のようなメビウス変換の列{ρn}を構成した ρn: Fn→SL(2,C)

ρn∈ D ∩ PS n→ ∞

ρnは結び目の双曲構造に収束する

.

今後の課題

.

.. .

.

n≥3

n元生成の(x,y,z)∈ Xがprimitive stableかどうかを判別するアルゴリズ

ムを作成する