Math::Group::Thompson 0.96

Math::Group::Thompson Perl module contains OO methods that calculates the cardinality of the ball of radius n of Thompson group F. SYNOPSIS use Math::Group::Thompson; my $F = Math::Group::Thompson->new( VERBOSE => 0 ); my $card = $F->cardBn(3,); print "#B(3) = $cardn"; The Math::Group::Thompson module provides objetct oriented methods that calculates the cardinality of the ball of radius n of Thompson group F. This module uses the presentation of F F = < A,B | [AB^(-1),A^(-1)BA] = [AB^(-1),A^(-2)BA^2] = e > where A,B are formal symbols, [x,y] is the usual commutator and e is the identity element of F. [x,y] = xyx^(-1)y^(-1) This means that for every g in F, g can be written as word g = a_{1}a_{2} ... a_{n} where all the a_{i} are A,B,A^(-1) or B^(-1) for all i <= n. Internally, Math::Group::Thompson representates A,B,A^(-1),B^(-1) as A,B,C,D respectively. Considering the set S = { A,B,A^(-1),B^(-1) } as a generator set for F. One can define the length function L, as L(g) = min{ n | g can be written as a word with n elements of S } We have to define L(e) = 0 With this definition, the ball of radius n of F, can be defined as B(n) = { g in F | L(g) <= n } So, what this module do is to calculate #B(n) or #(gB(n) - B(n)), where g in F, depending on what you need. Note that by definition of S, 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) so #B(n+1) = #(AB(n)-B(n))+#(BB(n)-B(n))+#(CB(n)-B(n))+#(DB(n)-B(n))+#B(n) Also, this module stores some special relations derived from [AB^(-1),A^(-1)BA] = [AB^(-1),A^(-2)BA^2] = e that must me avoided when counting the elements of B(n). For example, from [AB^(-1),A^(-1)BA] = e it can be derived the relations A^(-1)BAA = AB^(-1)A^(-1)BAB A^(-1)BAAB^(-1) = AB^(-1)A^(-1)BA among many other relations. The first relation show us that if we have a word g that contains AB^(-1)A^(-1)BAB it MUST NOT be counted as an element of B(n) for some n, because the word AB^(-1)A^(-1)BAB can be reduced to A^(-1)BAA and this implies that g was already counted as an element of B(n). Second relation tell us that if we have a word w that contains A^(-1)BAAB^(-1) it MUST NOT be counted as an element of B(n) because w was already counted (or will be counted) as and element of B(n). Resuming, relation [AB^(-1),A^(-1)BA] = 1, allow us to derive relations between words with length 4 and length 6, and between words of length 5. And the second relation [AB^(-1),A^(-2)BA^2] = 1 can be used to derive relations between words with length 6 and words with length 8, and between words of length 7. METHODS new Creates the Thompson object. Usage: my $F = new->Math::Group::Thompson( VERBOSE => $v ); Verbose argument tells Math::Group::Thompson whether print every word generated ($v == 1) or not ($v == 0), or store them in a file, where $v is the name of the file (obviously different to 0 or 1). If the verbose file exists it is replaced, so you have to check for its integrity. NOTE: Its not recommend to store the words on a file because for very small values of n, #B(n) or #gB(n)-B(n) are very very large. For example for n = 19, #B(n) ~ 3^n = 1162261467 ~ 1.1 Giga, but the space ocupped by the file will be (in bytes): #B(1) + sum(i=2 to 19){i*(#B(i) - #B(i-1))} = cardBn This method calculates #B(n) or #(gB(n) - B(n)) depending on if the argument passed to the first call of cardBn is or not. Usage: my $c = $F->cardBn($radius,$g); where $radius is an integer number >= 0 and $g is an element of F (word written with A,B,C or D). If the first time cardBn is called $g is not equal to , then cardBn returns the cardinality of the set gB(n) - B(n) = { w in F | w in gB(n) and w not in B(n) } If the firs time cardBn is callen $g is equal to , then cardBn returns #B(n). This algorithm runs on exponential time because F is of exponential growth (more "exactly", this algorithm is O(3^n) ). reset Resets the counter used on cardBn method, set the FIRST_ELEMENT property at , and the FIRST_CALL proporty to 1. Usage: $F->reset; multiply Multiplication between two words of F. This method considers the inverse relations stored in the attribute INV. Usage: my $mul = $F->multiply($g,$w); where $g and $w are elements of F, and $mul is the result of $g$w. rotate This module receives as argument a word in F and puts the last letter on word in its first place. Usage: $w = ABC; $W = $self->rotate($w); # $W is now equal to CBA inverse This method receives a word in F and returns its inverse. Usage: $w = ABC; $W = $self->inverse($w); # $W == ADC divide This method receives a word in F and returns a 2-dimensional array where the first element is the first half of the word, and the second is the inverse of the second half of the word. Usage: $w = AABC; ($w1,$w2) = $self->divide($w); # Now $w1 == AA and $w2 == AD get_inv This method return the hash of inverse relations between the generators elements of F. note This method prints in STDERR the string received or puts it on the correspondent file. Usage: $F->note(AA); # Print AA."n" or store it on a file..

Requirements:	No special requirements
Platforms:	Linux
Keyword:	Libraries,  Mathgroupthompson,  Oo,  Programming,  Radius N,  Thompson Group,  Word
Users rating:	0/10