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.

Informally, the free group \(\left(X,\circ\right)\) on a set \(S=\{a,b,c,...,z\}\) is the set \(X\) of words that are objects like \(W=c^{-4}bb^2aa^{-1}ca\), with a group operation of string juxtaposition. Usually one works only with words that are in reduced form, which has successive powers of the same symbol combined, so \(W\) would be equal to \(c^{-4}b^3ca\); see how \(b\) appears to the third power and the \(a\) term in the middle has vanished.

The group operation of juxtaposition is formally indicated by \(\circ\), but this is often omitted in algebraic notation; thus, for example \(a^2b^{-3}c^2\circ c^{-2}ba =a^2b^{-3}c^2c{^-2}ba =a^2b^{-2}ba\).

In R package freegroup, 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

library("freegroup")
(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 <- as.free("aabbbcccc"))
#>   aabbbcccc 
#> a^2.b^3.c^4

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

x+y
#>            aabbbcccc 
#> a^2.b^-3.c^5.b^3.c^4

(see how the \(a\) “cancels out” in the juxtaposition). One motivation for the use of “+” rather than “*” is that Python uses + for appending strings:

>>> "a" + "abc"
'aabc'
>>>

However, note that the + symbol is usually reserved for commutative operations; note that string juxtaposition is associative. Multiplication by integers—denoted in freegroup idiom by *—is also defined. Suppose we want to concatenate 5 copies of x:

x*5
#> [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:

x*(0:3)
#> [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, for example:

abc(1:9)
#> [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

And we can also generate random free objects:

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

Inverses are calculated using unary or binary minus:

(u <- rfree(10,4))
#>  [1] c.b^3.c^4      a^2.d^-3.b^-3  b^-2.a^-2.b^-2 c^-3.b^5       c.a^2.b       
#>  [6] b^-3.a^4.b^-1  c^3.b^4.d^4    c^3.d^-2.c^3   a.b^4.a^4.d^3  b^2.a^3.c^-2
-u
#>  [1] c^-4.b^-3.c^-1      b^3.d^3.a^-2        b^2.a^2.b^2        
#>  [4] b^-5.c^3            b^-1.a^-2.c^-1      b.a^-4.b^3         
#>  [7] d^-4.b^-4.c^-3      c^-3.d^2.c^-3       d^-3.a^-4.b^-4.a^-1
#> [10] c^2.a^-3.b^-2
u-u
#>  [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:

sum(u)
#> [1] c.b^3.c^4.a^2.d^-3.b^-5.a^-2.b^-2.c^-3.b^5.c.a^2.b^-2.a^4.b^-1.c^3.b^4.d^4.c^3.d^-2.c^3.a.b^4.a^4.d^3.b^2.a^3.c^-2

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

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

Thus:

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

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

free(rbind(1:30,1))
#> [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 = state.abb)
free(rbind(1:50,1))
#> [1] AL.AK.AZ.AR.CA.CO.CT.DE.FL.GA.HI.ID.IL.IN.IA.KS.KY.LA.ME.MD.MA.MI.MN.MS.MO.MT.NE.NV.NH.NJ.NM.NY.NC.ND.OH.OK.OR.PA.RI.SC.SD.TN.TX.UT.VT.VA.WA.WV.WI.WY