Math::Group::Thompson - OO methods that calculates the cardinality of the ball of radius 'n' of Thompson group F

Location : Home > Languages > Perl > Package
Title : Math::Group::Thompson

　Math::Group::Thompson - トンプソン群 F における半径 n の球の計算

use Math::Group::Thompson;

my $F = Math::Group::Thompson->new( VERBOSE => 0 );
my $card = $F->cardBn(3,'');

print "#B(3) = $card\n";

説明

　Math::Group::Thompson モジュールはトンプソン群（Thompson group） F における半径 n の球の濃度（cardinality）の計算を行うオブジェクト指向メソッドを提供する。なお、本モジュールでは F を以下の表現で用いる。

F = < A,B | [AB^(-1),A^(-1)BA] = [AB^(-1),A^(-2)BA^2] = e >

ただし A,B は形式記号で、 [x,y] は通常の交換子であり、e は F の単位元とする。

[x,y] = xyx^(-1)y^(-1)

　これは、F の任意の元 g に対し以下のように書くことができる。

g = a_{1}a_{2} ... a_{n}

　ただし、全ての a_{i} は A, B, A^(-1), B^(-1) について i <= n. である。

　内部的には Math::Group::Thompson は A, B, A^(-1), B^(-1) をそれぞれ A, B, C, D で表している。

　F の生成集合として S = { A,B,A^(-1),B^(-1) } を検討する。また距離関数 L を以下のように定義する。

L(g) = min{ n | Sの n この元で単語として記述可能な元 g }

　L(e) = 0 と定義する。この定義の下では、F における半径 n の球は以下のように定義できる。

B(n) = { g in F | L(g) <= n }

　すなわち、本モジュールは F の元 g に対し #B(n) または #(gB(n) - B(n)) を計算する。

B(n+1) = (AB(n)-B(n))U(BB(n)-B(n))U(CB(n)-B(n))U(DB(n)-B(n)) U B(n)

だから

#B(n+1) = #(AB(n)-B(n))+#(BB(n)-B(n))+#(CB(n)-B(n))+#(DB(n)-B(n))+#B(n)

　また、本モジュールは [AB^(-1),A^(-1)BA] = [AB^(-1),A^(-2)BA^2] = e から導出される特別な関係を格納する。ただしこれは B(n) の元を数えるときには破棄されなければならない。例えば [AB^(-1),A^(-1)BA] = e からは以下のような関係が導出される。

A^(-1)BAA = AB^(-1)A^(-1)BAB
A^(-1)BAAB^(-1) = AB^(-1)A^(-1)BA

　１つめの関係は AB^(-1)A^(-1)BAB を含む単語 g があれば、ある n に対し B(n) の元の要素をカウントしてはならないことを示している。それは単語 AB^(-1)A^(-1)BAB は A^(-1)BAA に縮小され、このことから g は既に B(n) の元としてカウントされているからである。
　２つめの関係は A^(-1)BAAB^(-1) を含む単語 w があれば B(n) の元としてカウントしてはならないことを示している。w は既に B(n) の元としてカウントされているからである。
　また関係 [AB^(-1),A^(-1)BA] = 1 から長さ 4 及び長さ 6 長さ 5 の単語間の関係導出することができる。２つめの関係 [AB^(-1),A^(-2)BA^2] = 1 からは長さ 6 と長さ 8 、長さ 7 の単語間の関係を導出することができる。

メソッド

new

　トンプソンオブジェクトを生成する。

使用方法：

my $F = new->Math::Group::Thompson( VERBOSE => $v );

　引数 Verbose を指定すると Math::Group::Thompson が生成されたあらゆる単語を出力する ($v == 1) または出力しない ($v == 0) かを指定できる。また $v がファイル名である場合には（明らかに 0 または 1 と異なる）ファイルに出力する。verbose で指定されたファイルが損座ウイ知れば上書きされてしまうのでユーザは整合性を確認する必要がある。

注意：
　 n の値が非常に小さいときには #B(n) または #gB(n)-B(n) は極めて大きな値となるので単語をファイルに書き出すことは推奨されない。
　例えば n = 19 のときには #B(n) ~ 3^n = 1162261467 ~ 1.1 GBくらいの容量が必要となる。

  #B(1) + sum(i=2 to 19){i*(#B(i) - #B(i-1))} =

cardBn

　本メソッドは最初の呼び出し時の引数が '' であるか否かに従って #B(n) または #(gB(n) - B(n)) を計算する。

使用方法：

my $c = $F->cardBn($radius,$g);

ただし $radius は非負の整数であり、$g は F の元（A, B, C, D で記述された単語）とする。
　初めて cardBn が呼び出されたときに $g が '' に等しくなければ、cardBn は次の集合の濃度を返す。

gB(n) - B(n) = { w in F | w は gB(n) の元でありかつ B(n) の元でない }

　初めて cardBn が呼び出されたときに $g が '' に等しければ、cardBn は #B(n) を返す。
　本アルゴリズムは F が指数的に成長するので指数時間の計算時間が必要である。（もう少し正確には本アルゴリズムは O(3^n) のオーダーである。）

reset

　cardBn メソッドで用いたカウンタを初期化し、FIRST_ELEMENT プロパティを '' にし、 FIRST_CALL プロパティを 1 に設定する。

使用方法：

$F->reset;

multiply

　F の２単語間の積を求める。本メソッドは属性 INV に格納されている逆関係を考慮する。

使用方法：

my $mul = $F->multiply($g,$w);

ただし $g 及び $w は F の元で、 $mul は $g$w の結果である。

rotate

　本モジュールは引数として F の単語を受け取り、単語の最後の文字を最初の文字の場所になるように置き換える。

使用方法：

$w = 'ABC';
$W = $self->rotate($w); # $W は 'CBA' に等しい

inverse

　本メソッドは F 内の単語を受け取り、その逆を返す。

使用方法：

$w = 'ABC';
$W = $self->inverse($w); # $W == 'ADC'

divide

　本メソッドは F 内の単語を受けとり、最初の元が単語の前半分であり、２つめの元が後ろ半分の逆であるような２次元配列を返す。

使用方法：

$w = 'AABC';
($w1,$w2) = $self->divide($w); # Now $w1 == 'AA' and $w2 == 'AD'

get_inv

　本メソッドは F の生成元間の逆関係のハッシュを返す。

note

　本メソッドは STDERR に受け取った文字列を出力するか対応するファイルに書き出す。

使用方法：

$F->note('AA'); # AAを出力する。またはファイルに格納する。

バグ

　これまでのところ報告されているバグはないが、それはバグがないことを意味するわけではない。;)

著者

　Roberto Alamos Moreno, <ralamosm@cpan.org>

　理論的な業績及び cardBn アルゴリズムの設計における支援について、 Juan Rivera Letelier 博士に対し感謝する。 :) .

著作権

　本プログラムはフリーソフトウェアであり、 Perl 本体と同等の条件で修正／再配布してもよい。

Updated : 2007/02/14