The freegroup package

This package provides some functionality for manipulating the free group on a finite list of symbols.

There is an excellent wikipedia page.

Basically, the free group~\(\left(X,\circ\right)\) on a set \(S=\{a,b,c,...,z\}\) is the set \(X\) of words that are things like \(c^{-4}bb^2aa^{-1}ca\). Usually one works only with words that are in reduced form, which has successive powers of the same symbol combined, in this case it would be \(c^{-4}b^3ca\); see how the \(a\) term in the middle has vanished.

The group operation is juxtaposition; thus, for example \(a^2b^{-3}c^2\circ c^{-2}ba =a^2b^{-3}c^2c^-2ba =a^2b^{-2}ba\).

A word is represented by a two-row integer matrix: The top row is the integer representation of the symbol and the second row is the corresponding power. For example, say we want to represent~\(a^2b^{-3}ac^2a^{-2}\) we would identify \(a\) as 1, \(b\) as 2, etc and write

(M <- rbind(c(1,2,3,3,1),c(2,-3,2,3,-2)))
#>      [,1] [,2] [,3] [,4] [,5]
#> [1,]    1    2    3    3    1
#> [2,]    2   -3    2    3   -2

(see how negative entries in the second row correspond to negative powers). Then to convert to a more useful form we would have

(x <- free(M))
#> [1] a^2.b^-3.c^5.a^-2

The representation for R object x is still a two-row matrix, but the print method is active and uses a more visually appealing scheme.

We can coerce strings to free objects:

(y <-"aabbbcccc"))
#>   aabbbcccc 
#> a^2.b^3.c^4

The free group operation is simply juxtaposition, represented here by the plus symbol, “+”:

#> [1] a^2.b^-3.c^5.b^3.c^4

See how the \(a\) “cancels out” in the juxtaposition. Note that concatenation is associative. Multiplication is also defined. Suppose we want to concatenate 5 copies of x:

#> [1] a^2.b^-3.c^5.b^-3.c^5.b^-3.c^5.b^-3.c^5.b^-3.c^5.a^-2

The package is vectorized:

#> [1] 0                                   a^2.b^-3.c^5.a^-2                  
#> [3] a^2.b^-3.c^5.b^-3.c^5.a^-2          a^2.b^-3.c^5.b^-3.c^5.b^-3.c^5.a^-2

There are a few methods for creating free objects:

#> [1] a                 a.b               a.b.c             a.b.c.d          
#> [5] a.b.c.d.e         a.b.c.d.e.f       a.b.c.d.e.f.g     a.b.c.d.e.f.g.h  
#> [9] a.b.c.d.e.f.g.h.i
#>  [1] d^-2.c^3.b^-1    a^4.d.c^-4       d^2.b^4.c^-1.b^2 d^2.a.c^3.d^-4  
#>  [5] d^-3             b^-2.c^-2.b^-4.a b^5              c^-1.a^-1       
#>  [9] c^-2.a^-2.c      c^-5.d^6

Inverses are calculated using unary or binary minus:

(u <- rfree(10,4))
#>  [1] a^3.b^-3.c^4.b^-4 c^-1              c^2.d^3.b^3.a^-4  a^2              
#>  [5] a^3.b^4.c.d^-4    d^3.c^2           c^2.b^-3          a^-2.b^-4.a^-4   
#>  [9] a^-3.c^3.d^3      b.d^-6
#>  [1] b^4.c^-4.b^3.a^-3  c                  a^4.b^-3.d^-3.c^-2 a^-2              
#>  [5] d^4.c^-1.b^-4.a^-3 c^-2.d^-3          b^3.c^-2           a^4.b^4.a^2       
#>  [9] d^-3.c^-3.a^3      d^6.b^-1
#>  [1] 0 0 0 0 0 0 0 0 0 0

We can take the “sum” of a vector of free objects simply by juxtaposing the elements:

#> [1] a^3.b^-3.c^4.b^-4.c.d^3.b^3.a.b^4.c.d^-1.c^4.b^-3.a^-2.b^-4.a^-7.c^3.d^3.b.d^-6

Powers are defined as per group conjugation: x^y == y^{-1}xy (or, written in additive notation, -y+x+y):

#>  [1] a^3.b^-3.c^4.b^-4 c^-1              c^2.d^3.b^3.a^-4  a^2              
#>  [5] a^3.b^4.c.d^-4    d^3.c^2           c^2.b^-3          a^-2.b^-4.a^-4   
#>  [9] a^-3.c^3.d^3      b.d^-6
z <- alpha(26)
#>  [1] z^-1.a^3.b^-3.c^4.b^-4.z z^-1.c^-1.z              z^-1.c^2.d^3.b^3.a^-4.z 
#>  [4] z^-1.a^2.z               z^-1.a^3.b^4.c.d^-4.z    z^-1.d^3.c^2.z          
#>  [7] z^-1.c^2.b^-3.z          z^-1.a^-2.b^-4.a^-4.z    z^-1.a^-3.c^3.d^3.z     
#> [10] z^-1.b.d^-6.z


sum(u^z) == sum(u^z)
#> [1] TRUE

If we have more than 26 symbols the print method runs out of letters:

#> [1] a.b.c.d.e.f.g.h.i.j.k.l.m.n.o.p.q.r.s.t.u.v.w.x.y.z.NA.NA.NA.NA

If this is a problem (it might not be: the print method might not be important) it is possible to override the default symbol set:

options(symbols =