The `freealg` package: the free algebra in R

knitr::opts_chunk$set(collapse = TRUE, comment = "#", dev = "png", fig.width = 7, fig.height = 3.5, message = FALSE, warning = FALSE)
options(width = 80, tibble.width = Inf)


The freealg package provides some functionality for the free algebra, using the Standard Template library of C++, commonly known as the STL. It is very like the mvp package for multivariate polynomials, but the indeterminates do not commute: multiplication is word concatenation.

The free algebra

A vector space over a commutative field $\mathbb{F}$ (here the reals) is a set $\mathbb{V}$ together with two binary operations, addition and scalar multiplication. Addition, usually written $+$, makes $\left(\mathbb{V},+\right)$ an Abelian group. Scalar multiplication is usually denoted by juxtaposition (or sometimes $\times$) and makes $\left(\mathbb{V},\cdot\right)$ a semigroup. In addition, for any $a,b\in\mathbb{F}$ and $\mathbf{u},\mathbf{v}\in\mathbb{V}$, the following laws are satisfied:

An algebra is a vector space endowed with a binary operation, usually denoted by either a dot or juxtaposition of vectors, from $\mathbb{V}\times\mathbb{V}$ to $\mathbb{V}$ satisfying:

There is no requirement for vector multiplication to be commutative. Here we assume associativity so in addition to the axioms above we have

The free associative algebra is, in one sense, the most general associative algebra. Here we follow standard terminology and drop the word `associative' while retaining the assumption of associativity. Given a set of indeterminates $\left{X_1,X_2,\ldots,X_n\right}$ one considers the set of words, that is, finite sequences of indeterminates. The vector space is then scalar multiples of words together with a formal vector addition; words are multiplied by concatenation. This system automatically satisfies the axioms of an associative algebra together with the requirement that addition of vectors satisfies distributivity.

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}$ and

[ A=\alpha x^2yx + \beta zy \qquad B=\gamma z + \delta y^4 ]

we would have

[ A\cdot B= \left(\alpha x^2yx+\beta zy\right) \cdot \left(\gamma z+\delta y^4\right)= \alpha\gamma x^2yxz+\alpha\delta x^2yxy^4+\beta\gamma zyz+\beta\delta zy^5 ] and [ B\cdot A= \left(\gamma z+\delta y^4\right) \cdot \left(\alpha x^2yx+\beta zy\right) =\alpha\gamma zx^2yx+\beta\gamma z^2y+\alpha\delta y^4x^2yx+\beta\delta y^4zy. ]

Note that multiplication is not commutative, but it is associative.

The STL map class

Here, a term is defined to be a scalar multiple of a word, and an element of the free algebra is considered to be the sum of a finite number of terms.

Thus we can view an element of the free algebra as a map from the set of words to the reals, each word mapping to its coefficient. Note that the empty word maps to the constant term. In STL terminology, a map is a sorted associative container that contains key-value pairs with unique keys. It is used in the package to map words to their coefficients, and is useful here because search and insertion operations have logarithmic complexity.

Package conventions

The indeterminates are the strictly positive integers (that is, we identify $X_i$ with integer $i$); a natural and easily implemented extension is to allow each indeterminate $X_i$ to have an inverse $X_{-i}$.

It is natural to denote indeterminates $X_1,X_2,X_3\ldots$ with lower-case letters $a,b,c,\ldots$ and their multiplicative inverses with upper-case letters $A,B,C\ldots$

Thus we might consider $X=5a +43xy +6yx-17a^3b$ to be the map

{[1] -> 5, [24,25] -> 43, [25,24] -> 6, [1,1,1,2] -> -17}

In standard template library language, this is a map from a list of signed integers to a double; the header in the package reads

typedef std::list<signed int> word; // a 'word' object is a list of signed ints
typedef map <word, double> freealg; // a 'freealg' maps word objects to reals

Although there are a number of convenience wrappers in the package, we would create object $X$ as follows:

X <- freealg(words = list(1, c(24,25), c(25,24), c(1,1,1,2)), coeffs = c(5, 43, 6, -17))

(the print method translates from integers to letters). Note that the key-value pairs do not have a well-defined order in the map class; so the terms of a free algebra object may appear in any order. This does not affect the algebraic value of the object and allows for more efficient storage and manipulation. See also the mvp [@hankin2019] and spray [@hankin2019a] packages for similar issues.

The package in use

There are a variety of ways of creating free algebra objects:

(X <- as.freealg("3aab -2abbax"))  # caret ("^") not yet implemented
(Y <- as.freealg("2 -3aab -aBBAA"))  # uppercase letters are inverses
(Z <- as.freealg(1:3))

Then the usual arithmetic operations work, for example:

X^2        # powers are implemented
X+Y        #  'aab' term cancels
1000+Y*Z   # algebra multiplication and addition works as expected


Algebraic substitution is implemented in the package with the subs() function:

p <- as.freealg("1+aab+4aba")

Substitution works nicely with the magrittr package:

"1+aaab+4abaa" %>% subs(b="1+x+3aa")


The package includes functionality to differentiate free algebra expressions. However, the idiom is not as cute as in the mvp package because freealg uses integers to distinguish the variables, while mvp uses symbolic expressions. Starting with a univariate freealg example we have:

k <- as.freealg("3 + 4aa + 7aaaaaa") # 3 + 4a^2 + 7a^6
deriv(k,1)   # dk/da  = 8a+42a^4

However, because of noncommutativity one has more complex behaviour. Observe that the Leibniz formula, if written $\left(xy\right)'=x'y+xy'$, still holds for noncommutative systems:

deriv(as.freealg("abaaaa"),1)  # d(aba^4)/da = ba^4 + 4aba^3

The package includes symbolwise multiplicative inverses and these too are differentiable in the package:

deriv(as.freealg("A"),1)    # d(a^-1)/da = -a^-2

but again noncommutativity complicates matters:

deriv(as.freealg("Aba"),1)    # d(a^-1ba)/da = -a^-2ba + a^-1b

The package can perform multiple partial differentiation by passing a vector second argument. To calculate, say, $\frac{d^3\left(a^3ba^{-1}cb^5\right)}{da^2\,db}$, is straighforward:

X <- as.freealg("aaabAcbbbbb")

We can then perform a number of consistency checks, remembering that multiplication is not commutative:

(X <- rfalg(maxsize=10,include.negative=TRUE))
d <- deriv(X,1)
deriv(X^3,1) == X^2*d + X*d*X + d*X^2

Observe carefully that the usual chain rule is not applicable here. If multiplication is commutative, one has $d(X^3)/da=3X^2dX/da$, but the above idiom shows that $d(X^3)/da=X^2\,dX/da + XdX/da\, X+dX/da\,X^2$. Now we check Young's theorem, that partial derivatives commute:

deriv(X,1:2) == deriv(X,2:1)

If differentiation commutes pairwise we may perform any number of partial derivatives in any order with the same result:

deriv(X,c(1,2,3,1,2,3)) == deriv(X,c(3,3,2,1,2,1))

We can also verify the Leibniz formula for products, remembering to maintain the order of the terms:

(X <- rfalg(maxsize=10,include.negative=TRUE))
(Y <- rfalg(maxsize=10,include.negative=TRUE))
deriv(X*Y,1) == deriv(X,1)*Y + X*deriv(Y,1)

Higher derivatives are somewhat harder:

f1 <- function(x){deriv(x,1)}
f2 <- function(x){deriv(x,2)}
f1(f2(X)) == f2(f1(X))  # Young
f1(f2(X*Y)) == X*f1(f2(Y)) + f1(X)*f2(Y) + f2(X)*f1(Y) + f1(f2(X))*Y # Leibniz

The print method

The default print method uses uppercase letters to represent multiplicative inverses, but it is possible to set the usecaret option, which makes changes the appearance:

phi <- rfalg(n=5,inc=TRUE)
options("usecaret" = TRUE)
options("usecaret" = FALSE)  # reset to default

An example

Haiman [-@haiman1993] poses the following question, attributed to David Richman:

"find the constant term of $\left(x+y+x^{-1}+y^{-1}\right)^p$ when $x$ and $y$ do not commute".

Package idiom is straightforward. Consider $p=4$:

X <- as.freealg("x+y+X+Y")

We could even calculate the first few terms of Sloane's A035610:

f <- function(n){constant(as.freealg("x+y+X+Y")^n)}


Try the freealg package in your browser

Any scripts or data that you put into this service are public.

freealg documentation built on April 19, 2021, 9:06 a.m.