---
title: "The free algebra with R"
author: "Robin K. S. Hankin"
output: html_vignette
bibliography: freealg.bib
vignette: >
  %\VignetteIndexEntry{The free algebra}
  %\VignetteEngine{knitr::rmarkdown}
  %\VignetteEncoding{UTF-8}
---


```{r setup, include=FALSE}
knitr::opts_chunk$set(echo = TRUE)
options(rmarkdown.html_vignette.check_title = FALSE)
library("freealg")
set.seed(1)
```

```{r out.width='20%', out.extra='style="float:right; padding:10px"',echo=FALSE}
knitr::include_graphics(system.file("help/figures/freealg.png", package = "freealg"))
```

To cite the `freealg` package in publications, please use
@hankin2022_freealg.  In this short document I show how free algebras
may be studied using the `freealg` package.  The _free algebra_ is
best introduced by an example: with an alphabet of $\{x,y,z\}$, and
real numbers $\alpha,\beta,\gamma$ we formally define $A=\alpha x^2yx
+ \beta zy$ and $B=-\beta zy + \gamma y^4$.  Addition is commutative
so $A+B=B+A$.  However, multiplication is not commutative so $AB\neq
BA$ in general; both are associative.  We also have consistency in
that $\alpha(\beta P)=(\alpha\beta)P$ for any expression $P$.  Then:

\[
A+B=(\alpha x^2yx + \beta zy) + (-\beta zy + \gamma y^4) = \alpha x^2yx + \gamma y^4
\]

\[
AB=
(\alpha x^2yx + \beta zy)
(-\beta zy + \gamma y^4)
=
-\alpha\beta x^2yxzy +\alpha\gamma x^2yxy^4 -\beta^2zyzy +\beta\gamma zy^5
\]

\[
BA=(-\beta zy + \gamma y^4)(\alpha x^2yx + \beta zy)
=
-\alpha\beta zyx^2yx
-\beta^2 zyzy
+ \alpha\gamma y^4x^2yx
+ \beta\gamma y^4zy
\]

This is a natural set of objects to consider.  Formally, we consider
the free R-module with a basis consisting of all words over an
alphabet of symbols [conventionally lower-case letters] with
multiplication of words defined as concatenation.  The system inherits
associativity from associativity of concatenation; distributivity
follows from the definition of R-module.  However, the free algebra is
not commutative in general.

# The `freealg` package in use

The above examples are a little too general for the `freealg` package;
the idiom requires that we have specific numerical values for the
coefficients $\alpha,\beta,\gamma$.  Here we will use $1,2,3$
respectively.

```{r,label=defineAandB}
(A <- as.freealg("xxyx + 2zy"))
(B <- as.freealg("-2zy + 3yyyy"))
A+B
A*B
B*A
```

Note that the terms are stored in an implementation-specific order.
For example, `A` might appear as `xxyz + 2*zy` or the algebraically
equivalent form `2*zy + xxyz`.  The package follows `disordR`
discipline [@hankin2022_disordR].

Inverses are coded using upper-case letters. 

```{r,useuppercase}
A*as.freealg("X") # X = x^{-1}
```

See how multiplying by $X=x^{-1}$ on the right cancels one of the `x`
terms in `A`.  We can use this device in more complicated examples:

```{r, uppercaseC}
(C <- as.freealg("3 + 5X - 2Xyx"))
A*C
C*A
```

With these objects we may verify that the distributive and associative
laws are true:

```{r,checklaws}
A*(B+C) == A*B + A*C
(A+B)*C == A*C + B*C
A*(B*C) == (A*B)*C
```

Various utilities are included in the package.  For example, the
commutator bracket is represented by reasonably concise idiom:

```{r,label=usecommutator}
a <- as.freealg("a")
b <- as.freealg("b")
.[a,b] # returns ab-ba
```

Using `rfalg()` to generate random free algebra objects, we may verify
the Jacobi identity:


```{r,label=verifyjacobi}
x <- rfalg()
y <- rfalg()
z <- rfalg()

.[x,.[y,z]] + .[y,.[z,x]] + .[z,.[x,y]]
```

The package includes functionality for substitution:


```{r,showsubstitution}
subs("aabccc",b="1+3x")  # aa(1+3x)ccc
```


```{r,sequentialsubstitution}
subs("abccc",b="1+3x",x="1+d+2e")
```

## Experimental functionality

It is possible to extract components of `freealg` objects using
reasonably standard idiom:

```{r showaccessor}
(a <- as.freealg("aaa + 2*aaba + 3*abbbba + 9*xyzabc - 3*abc"))
a[coeffs(a) > 2]
a[coeffs(a) < 0] <- 99
a
```

There is even some experimental functionality for calculus:

```{r,showderiv}
deriv(as.freealg("aaaxaa"),"a")
```

Above, "`da`" means the differential of `a`.  Note how it may appear
at any position in the product, not just the end (cf matrix
differentiation).

# References