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] = 1 >

where A,B are formal symbols and [x,y] is the usual commutator

[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 base 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 }

With this definition, the ball of radius n of F, can de 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] = 1 that must me avoided when counting the elements of B(n). For example, from [AB^(-1),A^(-1)BA] = 1 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).

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.

reset

Resets the counter used on cardBn method, set the FIRST_ELEMENT property at '', and the FIRST_CALL proporty to 1.

Usage: $F->resetcounter;

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'

reduce

This method receives a word in F and returns an 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->reduce($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 functions prints in STDERR the string received

Usage: note('AA'); # Print AA."\n"

AUTHOR

Roberto Alamos Moreno <ralamosm@gmail.com>

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