The Perl Toolchain Summit needs more sponsors. If your company depends on Perl, please support this very important event.


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)


#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.

  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);


$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 <>

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.

1 POD Error

The following errors were encountered while parsing the POD:

Around line 573:

=back doesn't take any parameters, but you said =back 4