GitHub - RobinHankin/freealg: Free algebra (original) (raw)

The Free Algebra in R

Overview

The free algebra is an interesting and useful object. Here I present thefreealg package which provides some functionality for free algebra in the R programming environment. The package uses the C++ map class for efficiency and conforms to disordR discipline. Several use-cases are provided.

Installation

You can install the released version of freealg fromCRAN with:

install.packages("freealg") # uncomment this to install the package

library("freealg")

The free algebra

The free algebra is the free R-module with a basis consisting of all words over an alphabet of symbols with multiplication of words defined as concatenation. Thus, with an alphabet of[ $\x,y,z](https://camo.githubusercontent.com/dac592f28e268736849464f7adcab133c57a9fc4b8129c7c7d4248c0a6ea61de/68747470733a2f2f6c617465782e636f6465636f67732e636f6d2f706e672e6c617465783f25354325374278253243792532437a253543253744 "{x,y,z}")$ and

$A=\alpha x^2yx + \beta zy$

and

$B=\gamma z + \delta y^4$

we would have

$AB=\left(\alpha x^2yx+\beta zy\right)\left(\gamma z+\delta y^4\right)=\alpha\gamma x^2yxz+\alpha\delta x^2yxy^4+\beta\gamma zyz+\beta\delta zy^5$

and

$BA=\left(\gamma z+\delta y^4\right)\left(\alpha x^2yx+\beta zy\right)=\alpha\gamma zx^2yx + \alpha\delta y^4 x^2yx + \beta\gamma z^2y + \beta\delta y^4zy.$

A natural and easily implemented extension is to use upper-case symbols to represent multiplicative inverses of the lower-case equivalents (formally we would use the presentation). Thus if

$C=\epsilon\left(x^{-1}\right)^2=\epsilon X^2$

we would have

$AC=\left(\alpha x^2yx+\beta zy\right)\epsilon X^2= \alpha\epsilon x^2yX + \beta\epsilon zyX^2$

and

$CA=\epsilon X^2\left(\alpha x^2yx+\beta zy\right)= \alpha\epsilon yx + \beta\epsilon X^2zy.$

The system inherits associativity from associativity of concatenation, and distributivity is assumed, but it is not commutative.

The `freealg` package in use

Creating a free algebra object is straightforward. We can coerce from a character string with natural idiom:

X <- as.freealg("1 + 3a + 5b + 5abba") X #> free algebra element algebraically equal to #> + 1 + 3a + 5abba + 5*b

or use a more formal method:

freealg(sapply(1:5,seq_len),1:5) #> free algebra element algebraically equal to #> + a + 2ab + 3abc + 4abcd + 5abcde

Y <- as.freealg("6 - 4a +2aaab") X+Y #> free algebra element algebraically equal to #> + 7 - a + 2aaab + 5abba + 5b XY #> free algebra element algebraically equal to #> + 6 + 14a - 12aa + 6aaaab + 2aaab + 30abba - 20abbaa + 10abbaaaab + 30b #> - 20ba + 10baaab X^2 #> free algebra element algebraically equal to #> + 1 + 6a + 9aa + 15aabba + 15ab + 10abba + 15abbaa + 25abbaabba + #> 25abbab + 10b + 15ba + 25babba + 25bb

We can demonstrate associativity (which is non-trivial):

set.seed(0) (x1 <- rfalg(inc=TRUE)) #> free algebra element algebraically equal to #> + 7C + 6Ca + 4B + 3BC + a + 5aCBB + 2bc (x2 <- rfalg(inc=TRUE)) #> free algebra element algebraically equal to #> + 6 + CAAA + 2Ca + 3Cbcb + 7aaCA + 4b + 5c (x3 <- rfalg(inc=TRUE)) #> free algebra element algebraically equal to #> + 3C + 5CbAc + BACB + 2a + 10b + 7cb

(function rfalg() generates random freealg objects). Then

x1*(x2x3) == (x1x2)*x3 #> [1] TRUE

Further information

For more detail, see the package vignette

vignette("freealg")