Enumeration of set-theoretic solutions to the Yang–Baxter equation

The Yang–Baxter equation (YBE) was first introduced in the field of statistical mechanics and for several decades it has been studied in mathematics and physics [5, 41]. Recent progress in set-theoretic solutions to the YBE shed new light on the importance of this equation in algebra and combinatorics [19, 18, 21, 13, 25, 27, 34, 38].

A set-theoretic solution to the YBE is a pair $(X,r)$, where $X$ is a set and $r\colon X\times X\to X\times X$ is a bijective map such that

holds, where the juxtaposition denotes the usual composition of maps. Note that this is a functional equation in the space of maps $X^{3}\to X^{3}$, where $X^{3}=X\times X\times X$.

We say that the solutions $(X,r)$ and $(Y,s)$ are isomorphic if there is a bijective map $f\colon X\to Y$ such that

From the combinatorial perspective certain types of solutions are particularly important; these are called non-degenerate solutions. By convention, if $(X,r)$ is a set-theoretic solution to the YBE, we write

The solution $(X,r)$ is then said to be non-degenerate if the maps $\sigma_{x}$ and $\tau_{x}$ are bijective for all $x\in X$.

Set-theoretic solutions to the YBE attracted a lot of attention and lead to several interesting connections between group theory, ring theory and combinatorics. The combinatorial version of the celebrated Yang–Baxter equation was first formulated by Drinfel’d in [12] and considered later in [13, 21] for involutive solutions and in [27, 37] for arbitrary solutions. Set-theoretic solutions are known to have deep connections with bijective $1$-cocycles, ordered groups, groups of I-type, regular subgroups, radical rings, skew braces, nil rings, homology theory, Hopf–Galois extensions [9, 36, 10, 34].

The main result in this article is an explicit classification of solutions to the YBE of small size. This is achieved by using some combinatorial ideas closely connected to the Yang–Baxter equation, Constraint Satisfaction methods [22, 15] and, in particular, the constraint modelling assistant Savile Row [31], and the computational algebra package GAP [16]. Similar techniques have been used to enumerate semi-groups of order $\leqslant 10$, see [11].

The combination of these techniques allows us to build a huge database of involutive and non-involutive solutions to the YBE, a good and useful source of examples that gives an explicit and direct way to approach some open problems concerning the YBE. The database is freely available as a library for GAP  at https://github.com/vendramin/enumeration, with DOI name 10.5281/zenodo.5180745.

In [13] Etingof, Schedler and Soloviev constructed all involutive solutions of size $\leqslant 8$. We summarize our findings on involutive solutions in the following statement.

Our methods can be easily adapted to construct racks of small size. Racks are particular types of solutions to the YBE that play a fundamental role in combinatorial knot theory, see Section 3.1. Using the 16,023 isomorphism classes of racks of size eight, we obtain the following result for non-involutive solutions of size eight.

No previous constructions of non-involutive solutions were known.

Our methods could be used to construct solutions of other sizes. However, the number of non-involutive solutions of size nine is expected to be extremely big. With 16,023 racks of size eight we constructed 422,449,480 non-involutive solutions, so the number of non-involutive solutions of size nine is expected to be enormous, as there are 159,526 racks of size nine.

The paper is organized as follows. In Section 2 we compute the number of involutive solutions. This is done by using a constraint satisfaction program and the language of cycle sets. The algorithm is described at the beginning of the section. As an application we enumerate several types of solutions such as indecomposable, irretractable and multipermutation solutions. We also enumerate counterexamples to a well-known conjecture of Gateva–Ivanova [17]. Finally, in Section 3 we use a similar algorithm and the same computational techniques to enumerate racks, non-involutive solutions and, in particular, non-involutive biquandles.

A solution $(X,r)$ is said to be involutive if $r^{2}=\operatorname{id}$. An involutive solution $(X,r)$ is said to be irretractable if $\tau_{x}\neq\tau_{y}$ for all $x\neq y$. Note that this is equivalent to $\sigma_{x}\neq\sigma_{y}$ for all $x\neq y$, as $T\sigma_{x}T^{-1}=\tau_{x}^{-1}$ holds for all $x\in X$, where $T\colon X\to X$, $T(x)=\tau^{-1}_{x}(x)$, see [13, Proposition 2.2]. An involutive solution $(X,r)$ is said to be square-free if $T(x)=x$ for all $x\in X$, or equivalently if $r(x,x)=(x,x)$ for all $x\in X$.

If $(X,r)$ is an involutive solution, we consider over $X$ the equivalence relation given by

This equivalence relation induces an involutive solution over the set of equivalence classes $X/{\sim}$, known as the retraction $\operatorname{Ret}(X,r)$ of $(X,r)$. An involutive solution $(X,r)$ is a multipermutation solution if there exists $n$ such that $|\operatorname{Ret}^{n}(X,r)|=1$, where $\operatorname{Ret}^{n+1}(X,r)=\operatorname{Ret}(\operatorname{Ret}^{n}(X,r))$. Multipermutation solutions generalize those in Example 1.1.

The permutation group of an involutive solution $(X,r)$ is defined as the subgroup $\mathcal{G}(X,r)$ of $\operatorname{Sym}_{X}$ generated by the set $\{\tau_{x}:x\in X\}$. An involutive solution $(X,r)$ is said to be indecomposable if the group $\mathcal{G}(X,r)$ acts transitively on $X$ and decomposable otherwise.

To construct all isomorphism classes of non-degenerate involutive solutions, we will use the language of cycle sets, introduced by Rump in [33]. A cycle set is a pair $(X,\cdot)$, where $X$ is a set and $X\times X\to X$, $(x,y)\mapsto x\cdot y$, is a binary operation such that the following conditions are satisfied:

1. (1)

   Each map $\varphi_{x}\colon X\to X$, $y\mapsto x\cdot y$, is bijective, and

2. (2)

   $(x\cdot y)\cdot(x\cdot z)=(y\cdot x)\cdot(y\cdot z)$ for all $x,y,z\in X$.

A cycle set $(X,\cdot)$ is said to be non-degenerate if the map $X\to X$, $x\mapsto x\cdot x$, is bijective. Rump proved that non-degenerate involutive solutions are in bijective correspondence with non-degenerate cycle sets, i.e.

The correspondence is given by the following formulas: If $(X,r)$ is a solution, then $(X,\cdot)$, where $x\cdot y=\tau_{x}^{-1}(y)$, is a non-degenerate cycle set. Conversely, if $(X,\cdot)$ is a cycle set, then $(X,r)$, where

is a non-degenerate involutive solution, where $y*x=z$ if and only if $y\cdot z=x$.

The solutions $(X,r)$ and $(Y,s)$ are isomorphic if and only if their associated cycle sets are isomorphic, which means that there is a bijective map $f\colon X\to Y$ such that $f(x_{1}\cdot x_{2})=f(x_{1})\cdot f(x_{2})$ for all $x_{1},x_{2}\in X$. Note that one can write this formula as

for all $x\in X$.

One can translate the definitions given at the beginning of the section in the language of cycle sets. For example, the permutation group of a cycle set $(X,\cdot)$ is then defined as the group generated by the set $\{\varphi_{x}:x\in X\}$, and a cycle set is said to be indecomposable (resp. decomposable) if its permutation group acts transitively (resp. intransitively) on $X$.

For a cycle set $(X,\cdot)$ let $T\colon X\to X$ be the map given by $T(x)=x\cdot x$. By definition, the cycle set is non-degenerate if and only if the map $T$ is bijective. In [13, Proposition 2.2], Etingof, Schedler and Soloviev proved that $T$ is always bijective whenever the solution is finite, thus finite cycle sets are regular. This was proved independently by Rump in [33].

A cycle set $(X,\cdot)$, where $X=\{1,2,\dots,n\}$, is encoded in a table

This means that the rows of $M$ are the permutations $\varphi_{1},\dots,\varphi_{n}$ defining the cycle set structure on $X$. The principal diagonal of $M$ is precisely the bijective map $T\colon X\to X$, $x\mapsto x\cdot x$.

To construct all involutive solutions we need to find all possible matrices $M\in\mathbb{Z}^{n\times n}$ with coefficients in $\{1,2,\dots,n\}$ such that

1. (1)

   for each $i$ the elements $M_{i,j}$ are all different,

2. (2)

   the elements of the principal diagonal of $M$ are all different, and

3. (3)

   $M_{M_{i,j},M_{i,k}}=M_{M_{j,i},M_{j,k}}$ holds for all $i,j,k\in\{1,\dots,n\}$.

Since the map $T$ is bijective, the diagonal $(M_{i,i})_{1\leqslant i\leqslant n}$ has $n$ different elements. This fact is used to reduce our search space. The general idea goes back to Plemmons [32], but in our particular case is based on the following lemma:

Lemma 2.5 implies that there are only a small number of diagonals to consider, each diagonal being a representative of a conjugacy class in the symmetric group $\operatorname{Sym}_{n}$. Thus the original problem is divided into $p(n)$ problems, where $p(n)$ is the number of partitions of $n$. In the particular case of solutions of size nine, this means that there are $p(9)=30$ independent cases to consider. For size ten, there are $p(10)=42$ independent cases to consider.

To construct non-isomorphic solutions we shall need the following notation: If $g\in\operatorname{Sym}_{n}$ and $M$ is a matrix, we denote by $M^{g}$ the matrix given by

for all $i,j\in\{1,\dots,n\}$. To avoid expensive isomorphism checking, we are interested in those matrices $M$ such that

for all $g$ in the centralizer $C_{\operatorname{Sym}_{n}}(T)$ of the permutation $T$ in $\operatorname{Sym}_{n}$, where $\operatorname{lex}$ stands for the lexicographic ordering given by $A\leqslant_{\operatorname{lex}}B$ if and only if

with lexicographical order. This symmetry breaking is in general very hard to implement, as in this case the number of constraints will be extremely large. This happens for example when $T=\operatorname{id}$ or $T$ is a transposition. To deal with this problem, we consider the constraint (2.1) only for those permutations that belong to a certain subset $S$ of $\operatorname{Sym}_{n}$. This is called partial symmetry breaking, see Remark 2.9 below for details. It should be noted that the use of proper subsets of the centralizer of $T$ produce some superfluous solutions and hence some repetitions should be removed by other computational methods.

We briefly describe our method to remove repetitions. Constraint satisfaction methods produce a list of solutions. Among the solutions in this list, only those minimal in their orbits are needed. A GAP script parses the list and, for each solution, checks whether or not the solution is minimal with respect to the lexicographic ordering inside its orbit. This stage of the process is mostly related with permutation groups and, in general, GAP deals with them in a friendly and very efficient way.

The enumeration of involutive solutions of size $\leqslant 8$ first appeared in [13]. Table 2.1 shows some numbers corresponding to solutions of size $\leqslant 10$. New results are presented in shaded cells. It should be noted that our numbers differ sightly from those of [13, Table 1], as our table contains two solutions of size eight that are not present in previous calculations.

Our approach with constraint programming needs about ten minutes to construct all those solutions of size $\leqslant 8$ up to isomorphism. The calculations for solutions of size nine took less than four hours and for size ten it took several days, see Tables 2.2, 2.3 and 2.4 for some runtimes. They were both performed in an Intel(R) Core(TM) i7-8700 CPU @ 3.20GHz, with 32GB RAM. The database of involutive solutions of size $\leqslant 9$ needs about 90MB. Almost 2GB are needed to store all involutive solutions of size $10$.

For size $\leqslant 7$ our calculations coincide with those in  [13], but differ by two for $n=8$ when the map $T$ an $8$-cycle (see Examples 2.6 and 2.7 below). We contacted the authors of  [13] regarding the aforementioned discrepancy and they found the missing solutions after a re-run of their own code.

In [17] Gateva–Ivanova conjectured that all finite square-free solutions are retractable. Despite the fact that the conjecture holds in several cases (see [1, 8, 20, 29]) a counterexample was found in [39]. From a given counterexample one then constructs other counterexamples by different methods, see [3, 7]. It turns out that constructing essentially new counterexamples to the conjecture seems to be quite challenging.

For $n\in\mathbb{N}$ let $g(n)$ be the number of isomorphism classes of counterexamples to Gateva–Ivanova conjecture. Computer calculations show that $g(n)=0$ if $n\leqslant 7$. Other values of $g(n)$ are shown in Table 2.5.

The determination of the exact value of $g(9)$ took about 7 minutes, $g(10)$ took 3 hours and $g(11)$ took four days. The calculations were performed in an Intel(R) Xeon(R) CPU E5-2670, 2.60GHz, with 32GB RAM.

The method presented in Section 2 is now used to compute non-involutive solutions. This time, we translate the problem into the language of skew cycle sets. First we need basic definitions of the theory of racks.