The free algebra with R

Robin K. S. Hankin

To cite the freealg package in publications, please use Hankin (2022b). 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.

(A <- as.freealg("xxyx + 2zy"))
## free algebra element algebraically equal to
## + xxyx + 2zy
(B <- as.freealg("-2zy + 3yyyy"))
## free algebra element algebraically equal to
## + 3yyyy - 2zy
A+B
## free algebra element algebraically equal to
## + xxyx + 3yyyy
A*B
## free algebra element algebraically equal to
## + 3xxyxyyyy - 2xxyxzy + 6zyyyyy - 4zyzy
B*A
## free algebra element algebraically equal to
## + 3yyyyxxyx + 6yyyyzy - 2zyxxyx - 4zyzy

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 (Hankin 2022a).

Inverses are coded using upper-case letters.

A*as.freealg("X") # X = x^{-1}
## free algebra element algebraically equal to
## + xxy + 2zyX

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:

(C <- as.freealg("3 + 5X - 2Xyx"))
## free algebra element algebraically equal to
## + 3 + 5X - 2Xyx
A*C
## free algebra element algebraically equal to
## + 5xxy + 3xxyx - 2xxyyx + 6zy + 10zyX - 4zyXyx
C*A
## free algebra element algebraically equal to
## - 2Xyxxxyx - 4Xyxzy + 10Xzy + 3xxyx + 5xyx + 6zy

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

A*(B+C) == A*B + A*C
## [1] TRUE
(A+B)*C == A*C + B*C
## [1] TRUE
A*(B*C) == (A*B)*C
## [1] TRUE

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

a <- as.freealg("a")
b <- as.freealg("b")
.[a,b] # returns ab-ba
## free algebra element algebraically equal to
## + ab - ba

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

x <- rfalg()
y <- rfalg()
z <- rfalg()

.[x,.[y,z]] + .[y,.[z,x]] + .[z,.[x,y]]
## free algebra element algebraically equal to
## 0

The package includes functionality for substitution:

subs("aabccc",b="1+3x")  # aa(1+3x)ccc
## free algebra element algebraically equal to
## + aaccc + 3aaxccc
subs("abccc",b="1+3x",x="1+d+2e")
## free algebra element algebraically equal to
## + 4accc + 3adccc + 6aeccc

Experimental functionality

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

(a <- as.freealg("aaa + 2*aaba + 3*abbbba + 9*xyzabc - 3*abc"))
## free algebra element algebraically equal to
## + aaa + 2aaba + 3abbbba - 3abc + 9xyzabc
a[coeffs(a) > 2]
## free algebra element algebraically equal to
## + 3abbbba + 9xyzabc
a[coeffs(a) < 0] <- 99
a
## free algebra element algebraically equal to
## + aaa + 2aaba + 3abbbba + 99abc + 9xyzabc

There is even some experimental functionality for calculus:

deriv(as.freealg("aaaxaa"),"a")
## free algebra element algebraically equal to
## + aaaxa(da) + aaax(da)a + aa(da)xaa + a(da)axaa + (da)aaxaa

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

Hankin, Robin K. S. 2022a. “Disordered Vectors in R: Introducing the disordR Package.” arXiv. https://doi.org/10.48550/ARXIV.2210.03856.
———. 2022b. “The Free Algebra in R.” arXiv. https://doi.org/10.48550/ARXIV.2211.04002.