# 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.