NAME

Math::Group::Thompson - 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) = $card\n";

DESCRIPTION

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:
  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))} = 

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.

BUGS

There isn't reported bugs yet, but that doesn't mean that there aren't ;) .

AUTHOR

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

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.

cpanm Math::Group::Thompson

perl -MCPAN -e shell
install Math::Group::Thompson