# The freegroup package

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

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))
#>  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"))
#>  a^2.b^3.c^4

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

x+y
#>  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
#>  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)
#>  0                                   a^2.b^-3.c^5.a^-2
#>  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)
#>  a                 a.b               a.b.c             a.b.c.d
#>  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
#>  a.b.c.d.e.f.g.h.i

And we can also generate random free objects:

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

Inverses are calculated using unary or binary minus:

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

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

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

Thus:

sum(u^z) == sum(u^z)
#>  TRUE

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

free(rbind(1:30,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))
#>  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