Math::Group::Thompson - OO methods that calculates the cardinality of the ball of radius 'n' of Thompson group F
use Math::Group::Thompson; my $F = Math::Group::Thompson->new( VERBOSE => 0 ); my $card = $F->cardBn(3,''); print "#B(3) = $card\n";
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.
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: It's 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))} =
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) ).
Resets the counter used on cardBn method, set the FIRST_ELEMENT property at '', and the FIRST_CALL proporty to 1.
Usage: $F->reset;
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.
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'
This method receives a word in F and returns its inverse.
Usage: $w = 'ABC'; $W = $self->inverse($w); # $W == 'ADC'
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'
This method return the hash of inverse relations between the generators elements of F.
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.
There isn't reported bugs yet, but that doesn't mean that there aren't ;) .
Roberto Alamos Moreno <ralamosm@cpan.org>
Thanks to professor Juan Rivera Letelier for his support to my thesis work, and help in the design of cardBn algorithm :) .
Copyright (c) 2004 Roberto Alamos Moreno. All rights reserved. This program is free software; you can redistribute it and/or modify it under the same terms as Perl itself.