Quandle and Biquandle Homology Calculation in R

Roger Fenn; Ansgar Wenzel

(1) Overview

Introduction

This introduction is divided into two parts: First, we are going to give some mathematical background before introducing the software itself.

Mathematical Background

Racks and Quandles were first described by John Conway and Gavin Wraith in 1959 in unpublished correspondence. In [], David Joyce showed that racks are indeed a knot invariant. Subsequently, Fenn and Rourke introduced racks as proper knot invariants in []. It is instructive to consider racks as groups without their multiplicative elements. Formally, a rack is defined as a set of elements endowed with a binary operation which satisfies the following axioms (where the third axiom holds only for a quandle, not for a rack) for all a, b, c in the rack/quandle R:

∀a, b ∈ R∃! c ∈ Rs.t.a^c = b
$b a (c) (b c) (c) = a c$ M1 \documentclass[10pt]{article} \usepackage{wasysym} \usepackage[substack]{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage[mathscr]{eucal} \usepackage{mathrsfs} \usepackage{pmc} \usepackage[Euler]{upgreek} \pagestyle{empty} \oddsidemargin -1.0in \begin{document} \[ \begin{array}{*{20}{c}} b\\ a\\ {{{(c)}^{({b^c})}}}\\ {(c) = {a^c}} \end{array} \] \end{document}
a^a = a (only quandle)

Biracks and Biquandles are defined similarly, now with two operations, satisfying the following axioms:

a^bc_b = a^{cb^c}
a_{bc_b} = a_cb^c
a_b^c_b = a^c_b^c
a^a = a_a (only biquandle)

In addition, both operations satisfy the rack axiom 1.

Here, the up and down actions allow us to introduce a switch map via f_a(x) = x_a, f^a(x) = x^a as S(a, f_a(b)) = S(b, f^b(a)). The utility of this is clear when one observes that the axioms can be reformulated using the switch map:

S, f^a and f_a are all bijective.
Yang Baxter Equation: S₁S₂S₁ = S₂S₁S₂, where S₁(a, b, c) = (S(a, b), c) and S₂(a, b, c) = (a, S(b, c)).

This reformulation is more amenable to computational work.

The homology of the biquandle is defined as follows:

Let X be a birack. Then $C n R (X)$ M2 \documentclass[10pt]{article} \usepackage{wasysym} \usepackage[substack]{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage[mathscr]{eucal} \usepackage{mathrsfs} \usepackage{pmc} \usepackage[Euler]{upgreek} \pagestyle{empty} \oddsidemargin -1.0in \begin{document} \[ C_n^R(X) \] \end{document} be the free abelian group generated by n-tuples (x₁x₂… x_n), x_i ∈ X, that is, $C n R (X) = Z X n$ M3 \documentclass[10pt]{article} \usepackage{wasysym} \usepackage[substack]{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage[mathscr]{eucal} \usepackage{mathrsfs} \usepackage{pmc} \usepackage[Euler]{upgreek} \pagestyle{empty} \oddsidemargin -1.0in \begin{document} \[ C_n^R(X) = Z{X^n} \] \end{document} .

We define a boundary homomorphism by:

∂ (x 1 x 2 … x n) = ∑ i = 2 n (− 1) i [(x 1 … x i^… x n) − x 1 x i … x i − 1 x i (x i + 1) x i (x n) x i]

M4 \documentclass[10pt]{article} \usepackage{wasysym} \usepackage[substack]{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage[mathscr]{eucal} \usepackage{mathrsfs} \usepackage{pmc} \usepackage[Euler]{upgreek} \pagestyle{empty} \oddsidemargin -1.0in \begin{document} \[ \begin{array}{l} \partial \left({{x_1}{x_2}\, \ldots \,{x_n}} \right) = \mathop \sum \limits_{i = 2}^n {\left({ - 1} \right)^i}\left[{\left({{x_1}\, \ldots \,\widehat {{x_i}}\, \ldots \,{x_n}} \right)} \right.\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left. { - x_1^{{x_i}} \ldots \,\,x_{i - 1}^{{x_i}}{{\left({{x_{i + 1}}} \right)}_{{x_i}}}{{\left({{x_n}} \right)}_{{x_i}}}} \right] \end{array} \] \end{document}

and $(C n R (X), ∂)$ M5 \documentclass[10pt]{article} \usepackage{wasysym} \usepackage[substack]{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage[mathscr]{eucal} \usepackage{mathrsfs} \usepackage{pmc} \usepackage[Euler]{upgreek} \pagestyle{empty} \oddsidemargin -1.0in \begin{document} \[ (C_{_n}^R(X),\,\,\partial) \] \end{document} is called a chain complex of X.

Furthermore, we have a subchain complex $C n D (X) ⊂ C n R (X)$ M6 \documentclass[10pt]{article} \usepackage{wasysym} \usepackage[substack]{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage[mathscr]{eucal} \usepackage{mathrsfs} \usepackage{pmc} \usepackage[Euler]{upgreek} \pagestyle{empty} \oddsidemargin -1.0in \begin{document} \[ C_n^D(X)\,\, \subset \,\,C_n^R(X) \] \end{document} , generated by degenerate n-tuples (x₁x₂…x_n), x_i ∈ X with x_i = x_i+1 for some i. Together with the boundary homomorphism, $(C n D (X), ∂)$ M7 \documentclass[10pt]{article} \usepackage{wasysym} \usepackage[substack]{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage[mathscr]{eucal} \usepackage{mathrsfs} \usepackage{pmc} \usepackage[Euler]{upgreek} \pagestyle{empty} \oddsidemargin -1.0in \begin{document} \[ (C_n^D(X),\,\,\partial) \] \end{document} is is called the degenerate chain complex of X.

Using both of those chain complexes, we can define the biquandle chain complex via the quotient chain complex, $C n Q (X) = C n R (X) / C n D (X)$ M8 \documentclass[10pt]{article} \usepackage{wasysym} \usepackage[substack]{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage[mathscr]{eucal} \usepackage{mathrsfs} \usepackage{pmc} \usepackage[Euler]{upgreek} \pagestyle{empty} \oddsidemargin -1.0in \begin{document} \[ C_n^Q(X) = C_n^R(X)\,/\,C_n^D(X) \] \end{document} . This gives the following short exact sequence of chain complexes:

0 → C n D (X) → C n R (X) → C n Q (X) → 0.

M9 \documentclass[10pt]{article} \usepackage{wasysym} \usepackage[substack]{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage[mathscr]{eucal} \usepackage{mathrsfs} \usepackage{pmc} \usepackage[Euler]{upgreek} \pagestyle{empty} \oddsidemargin -1.0in \begin{document} \[ 0 \to C_n^D\left(X \right) \to C_n^R\left(X \right) \to C_n^Q\left(X \right) \to 0. \] \end{document}

We can then define the birack, biquandle and degenerate homology groups in the usual way. In addition, we have the following long exact sequence of homology groups:

… → H n D (X) → H n R (X) → H n Q (X) → H n − 1 D (X) …

M10 \documentclass[10pt]{article} \usepackage{wasysym} \usepackage[substack]{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage[mathscr]{eucal} \usepackage{mathrsfs} \usepackage{pmc} \usepackage[Euler]{upgreek} \pagestyle{empty} \oddsidemargin -1.0in \begin{document} \[ \ldots \to H_n^D\left(X \right) \to H_n^R\left(X \right) \to H_n^Q\left(X \right) \to H_{n - 1}^D\left(X \right) \ldots \] \end{document}

The algorithm for the homology calculation is described in [] for this specific software.

Software

The software, which is provided as an R package, can be accessed on github. It provides two primary functions. One of these calculates the homology of racks and biracks, whilst the other verifies if a rack or birack is induced by a given set with one or two actions.

Implementation and architecture

This software is implemented in R. It has been tested on MacOS X, CentOS/Ubuntu and Windows without any problems.

The algorithm for the homology calculation is described in the paper [].

The program is divided into the following two main parts: The calculation of the boundary matrix and the subsequent calculation of the Homology. For a graphical description see the following Figure 1, which was created with the following code:

library(proftools)
Rprof(tmp <- tempfile(), line.profiling = T); homology(4,5,F);Rprof(append=F); pd <- readProfileData(tmp)
plotProfileCallGraph(pd,style=google.style,score=“total”,nodeSizeScore = “none”,layout=”dot”,rankDir = “LR”)

Figure 1

Call graph for the calculation of the $H 4 R (Z 5)$ M11 \documentclass[10pt]{article} \usepackage{wasysym} \usepackage[substack]{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage[mathscr]{eucal} \usepackage{mathrsfs} \usepackage{pmc} \usepackage[Euler]{upgreek} \pagestyle{empty} \oddsidemargin -1.0in \begin{document} \[ H_4^R({Z_5}) \] \end{document} .

The boundary matrices are computed using the functions boundary_matrix (for quandle and rack boundary matrices) and boundary_matrix_degenerate (for degenerate boundary matrices), respectively. The methodology of both functions is similar, differing only in the manner in which degenerate or non-degenerate entries are removed where required. In particular, after creating a right-sized matrix, they call boundary_names or boundary-names_degenerate to create the row and column names of the boundary matrix. After this, they loop through the column names to calculate their boundaries and construct the matrix (for details see []). These boundary matrices represent the boundary maps of the simplicial complex of the rack/birack.

After both boundary matrices have been calculated, they are returned to the homology and degenerate_homology functions, respectively. As is the case for the boundary matrices functions, these two functions only differ in the boundary functions called and in their respective output texts.

As an aside, those two functions should be the only ones that would have to be called by the user in order to calculate a homology.

Following on with the algorithm described in [], those two functions calculate the image and kernel of the boundary map representations (the boundary matrices) before finding a representation of the homology group. For this, they call various functions, namely findX, which “finds X” (this is defined in []), row_space, which calculates a basis of the row space of a matrix, matrix_rank, which calculates the rank of a matrix and GaussianElimination, a function written by Prof John Fox (see [] for a source) which does a Gaussian Elimination on a matrix and returns its reduced row echelon form.

Using the function smith, the smith natural form is obtained from the representation matrix of the homology. This is done via repeated calculation of the hermite normal form of the matrix and its transpose, using the hermiteNF function from the numbers package, []. In addition, this function checks if the diagonal of the matrix is in the correct form via the function check_more_push and, if required, will call push_down to do what the name implies.

Finally. The homology group is obtained using the diagonal of the smith normal form.

The second function of this package, the testing if a give operation or operations give rise to a quandle or biquandle is done via the function S_test. This function receives as input the order of the underlying set and then proceeds to test the two requirements for a quandle/biquandle as described before.

Quality control

The results of the program have been compared to known results and in addition, R CMD check has been used to quality check the code itself.

Additionally, a few tests have been provided in test/testthat.R.

(2) Availability

Operating system

Any OS that can install and run R (at least version 3.0.0).

Programming language

R 3.0.0+.

Additional system requirements

The more RAM, the higher the homology groups that can be calculated.

Presently, output is on screen, but can be changed to a file, if necessary.

Required input devices: keyboard only.

Dependencies

The program requires the R standard installation [, ], together with the packages MASS [] and numbers [].

Software location

Code Repository

Names: GitHub

Identifier:https://github.com/ansgarwenzel/quhomology

License: GNU GPL v3.0

Date published: 05/05/2016

Version: 1.1.0

Language

English

Support

Support is currently provided via Github issues.

(3) Reuse potential

This software can be used to calculate the homology groups of most racks and biracks. It is very easy to adapt for application to other eracks/biracks. Furthermore we believe that it can easily be extended to the calculation of Cohomology groups. Finally, the possibility of quickly identifying if a given action/set of actions gives rise to a rack/birack, is very useful.

[B1] Fenn, R 2014 How to calculate Homology. http://www.maths.sussex.ac.uk/Staff/RAF/Maths/.

[B2] Joyce, D 1982 A classifying invariant of knots: the knot quandle. Journal of Pure and Applied Algebra 23: 37–65. DOI: https://doi.org/10.1016/0022-4049(82)90077-9

[B3] Fenn, R and Rourke, C 1992 Racks and links in codimension 2. In Journal of Knot Theory and its Ramifications 1: 343–406.

[B4] Fox, J 2014 GaussianElimination and rref function. http://socserv.mcmaster.ca/jfox/Courses/R-course-Berkeley/.

[B5] R Core Team 2014 R: A language and environment for statistical computing. R Foundation for Statistical Computing. Vienna, Austria. http://www.R-project.org/.

[B6] Venables, W N and Ripley, B D 2002 Modern Applied Statistics with S. Fourth Edition. Springer, New York. ISBN 0-387-95457-0. DOI: https://doi.org/10.1007/978-0-387-21706-2

[B7] Bates, D and Maechler, M 2014 Matrix: Sparse and Dense Matrix Classes and Methods. R package version 1.1–4. http://CRAN.R-project.org/package=Matrix.

[B8] Borchers, H W 2014 numbers: Number-theoretic Functions. R package version 0.4–5, http://CRAN.R-project.org/package=numbers.

Journal of Open Research Software

Software Metapapers