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)  # Introduction 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: • Compatibility:$a\left(b\mathbf{v}\right)=(ab)\mathbf{v}$• Identity:$1\mathbf{v}=\mathbf{v}$, where$1\in\mathbb{F}$is the multiplicative identity • Distributivity of vector addition:$a\left(\mathbf{u}+\mathbf{v}\right)=a\mathbf{u}+b\mathbf{v}$• Distributivity of field addition:$(a+b)\mathbf{v}=a\mathbf{v}+b\mathbf{v}$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: • Left distributivity:$\mathbf{u}\cdot(\mathbf{v}+\mathbf{w})= \mathbf{u}\cdot\mathbf{v} + \mathbf{u}\cdot\mathbf{w}$. • Right distributivity:$(\mathbf{u}+\mathbf{v})\cdot\mathbf{w}= \mathbf{u}\cdot\mathbf{w} + \mathbf{v}\cdot\mathbf{w}$. • Compatibility:$(a\mathbf{u})\cdot(b\mathbf{v})= (ab)(\mathbf{u}\cdot\mathbf{v})$. There is no requirement for vector multiplication to be commutative. Here we assume associativity so in addition to the axioms above we have • Associativity:$\left(\mathbf{u}\cdot\mathbf{v}\right)\cdot\mathbf{w}=\mathbf{u}\cdot\left(\mathbf{v}\cdot\mathbf{w}\right)$. 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 { -> 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: library("freealg") X <- freealg(words = list(1, c(24,25), c(25,24), c(1,1,1,2)), coeffs = c(5, 43, 6, -17)) dput(X) X  (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  # Substitution Algebraic substitution is implemented in the package with the subs() function: subs("1+4a",a="xx") p <- as.freealg("1+aab+4aba") subs(p,a="1+x",b="y+xx")  Substitution works nicely with the magrittr package: library("magrittr") "1+aaab+4abaa" %>% subs(b="1+x+3aa")  # Calculus 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 k 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") X deriv(X,c(1,1,2))  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) phi options("usecaret" = TRUE) phi 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")
X^2
constant(X^4)


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

f <- function(n){constant(as.freealg("x+y+X+Y")^n)}
sapply(c(0,2,4,6,8,10),f)
`

# References

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