4 Creating Quasigroups and Loops

In this chapter we describe several ways in which quasigroups and loops can be created in **LOOPS**.

Let \(X=\{x_1,\dots,x_n\}\) be a set and \(\cdot\) a binary operation on \(X\). Then an \(n\) by \(n\) array with rows and columns bordered by \(x_1\), \(\dots\), \(x_n\), in this order, is a *Cayley table*, or a *multiplication table* of \(\cdot\), if the entry in the row \(x_i\) and column \(x_j\) is \(x_i\cdot x_j\).

A Cayley table is a *quasigroup table* if it is a latin square, i.e., if every entry \(x_i\) appears in every column and every row exactly once.

An unfortunate feature of multiplication tables in practice is that they are often not bordered, that is, it is up to the reader to figure out what is meant. Throughout this manual and in **LOOPS**, we therefore make the following assumption: *All distinct entries in a quasigroup table must be positive integers, say \(x_1 < x_2 < \cdots < x_n\), and if no border is specified, we assume that the table is bordered by \(x_1\), \(\dots\), \(x_n\), in this order.* Note that we do not assume that the distinct entries \(x_1\), \(\dots\), \(x_n\) form the interval \(1\), \(\dots\), \(n\). The significance of this observation will become clear in Chapter 6.

Finally, we say that a quasigroup table is a *loop table* if the first row and the first column are the same, and if the entries in the first row are ordered in an ascending fashion.

`‣ IsQuasigroupTable` ( T ) | ( operation ) |

`‣ IsQuasigroupCayleyTable` ( T ) | ( operation ) |

Returns: `true`

if `T` is a quasigroup table as defined above, else `false`

.

`‣ IsLoopTable` ( T ) | ( operation ) |

`‣ IsLoopCayleyTable` ( T ) | ( operation ) |

Returns: `true`

if `T` is a loop table as defined above, else `false`

.

**Remark:**The package **GUAVA** also contains operations dealing with latin squares. In particular, `IsLatinSquare`

is declared in **GUAVA**.

`‣ CanonicalCayleyTable` ( T ) | ( operation ) |

Returns: Canonical Cayley table constructed from Cayley table `T` by replacing entries \(x_i\) with \(i\).

A Cayley table is said to be *canonical* if it is based on elements \(1\), \(\dots\), \(n\). Although we do not assume that every quasigroup table is canonical, it is often desirable to present quasigroup tables in canonical way.

`‣ CanonicalCopy` ( Q ) | ( operation ) |

Returns: A canonical copy of the quasigroup or loop `Q`.

This is a shorthand for `QuasigroupByCayleyTable(CanonicalCayleyTable(`

when `Q`)`Q` is a declared quasigroup, and `LoopByCayleyTable(CanonicalCayleyTable(`

when `Q`)`Q` is a loop.

`‣ NormalizedQuasigroupTable` ( T ) | ( operation ) |

Returns: A normalized version of the Cayley table `T`.

A given Cayley table `T` is normalized in three steps as follows: first, `CanonicalCayleyTable`

is called to rename entries to \(1\), \(\dots\), \(n\), then the columns of `T` are permuted so that the first row reads \(1\), \(\dots\), \(n\), and finally the rows of `T` are permuted so that the first column reads \(1\), \(\dots\), \(n\).

`‣ QuasigroupByCayleyTable` ( T ) | ( operation ) |

`‣ LoopByCayleyTable` ( T ) | ( operation ) |

Returns: The quasigroup (resp. loop) with quasigroup table (resp. loop table) `T`.

Since `CanonicalCayleyTable`

is called within the above operation, the resulting quasigroup will have Cayley table with distinct entries \(1\), \(\dots\), \(n\).

gap> ct := CanonicalCayleyTable( [[5,3],[3,5]] ); [ [ 2, 1 ], [ 1, 2 ] ] gap> NormalizedQuasigroupTable( ct ); [ [ 1, 2 ], [ 2, 1 ] ] gap> LoopByCayleyTable( last ); <loop of order 2> gap> [ IsQuasigroupTable( ct ), IsLoopTable( ct ) ]; [ true, false ]

Typing a large multiplication table manually is tedious and error-prone. We have therefore included a general method in **LOOPS** that reads multiplication tables of quasigroups from a file.

Instead of writing a separate algorithm for each common format, our algorithm relies on the user to provide a bit of information about the input file. Here is an outline of the algorithm, with file named `filename` and a string `del` as input (in essence, the characters of `del` will be ignored while reading the file):

read the entire content of

`filename`into a string`s`,replace all end-of-line characters in

`s`by spaces,replace by spaces all characters of

`s`that appear in`del`,split

`s`into maximal substrings without spaces, called*chunks*here,let \(n\) be the number of distinct chunks,

if the number of chunks is not \(n^2\), report error,

construct the multiplication table by assigning numerical values \(1\), \(\dots\), \(n\) to chunks, depending on their position among distinct chunks.

The following examples clarify the algorithm and document its versatility. All examples are of the form \(F+D\Longrightarrow T\), meaning that an input file containing \(F\) together with the deletion string \(D\) produce multiplication table \(T\).

**Example:** Data does not have to be arranged into an array of any kind.

\[ \begin{array}{cccc} 0&1&2&1\\ 2&0&2& \\ 0&1& & \end{array}\quad + \quad "" \quad \Longrightarrow\quad \begin{array}{ccc} 1&2&3\\ 2&3&1\\ 3&1&2 \end{array} \]

**Example:** Chunks can be any strings.

\[ \begin{array}{cc} {\rm red}&{\rm green}\\ {\rm green}&{\rm red}\\ \end{array}\quad + \quad "" \quad \Longrightarrow\quad \begin{array}{cc} 1& 2\\ 2& 1 \end{array} \]

**Example:** A typical table produced by **GAP** is easily parsed by deleting brackets and commas.

\[ [ [0, 1], [1, 0] ] \quad + \quad "[,]" \quad \Longrightarrow\quad \begin{array}{cc} 1& 2\\ 2& 1 \end{array} \]

**Example:** A typical TeX table with rows separated by lines is also easily converted. Note that we have to use \(\backslash\backslash\) to ensure that every occurrence of \(\backslash\) is deleted, since \(\backslash\backslash\) represents the character \(\backslash\) in **GAP**

\[ \begin{array}{lll} x\&& y\&&\ z\backslash\backslash\cr y\&& z\&&\ x\backslash\backslash\cr z\&& x\&&\ y \end{array} \quad + \quad "\backslash\backslash\&" \quad \Longrightarrow\quad \begin{array}{ccc} 1&2&3\cr 2&3&1\cr 3&1&2 \end{array} \]

`‣ QuasigroupFromFile` ( filename, del ) | ( operation ) |

`‣ LoopFromFile` ( filename, del ) | ( operation ) |

Returns: The quasigroup (resp. loop) whose multiplication table data is in file `filename`, ignoring the characters contained in the string `del`.

`‣ CayleyTableByPerms` ( P ) | ( operation ) |

Returns: If `P` is a set of \(n\) permutations of an \(n\)-element set \(X\), returns Cayley table \(C\) such that \(C[i][j] = X[j]^{P[i]}\).

The cardinality of the underlying set is determined by the moved points of the first permutation in `P`, unless the first permutation is the identity permutation, in which case the second permutation is used.

In particular, if `P` is the left section of a quasigroup `Q`, `CayleyTableByPerms(`

returns the multiplication table of `Q`)`Q`.

`‣ QuasigroupByLeftSection` ( P ) | ( operation ) |

`‣ LoopByLeftSection` ( P ) | ( operation ) |

Returns: If `P` is a set of permutations corresponding to the left translations of a quasigroup (resp. loop), returns the corresponding quasigroup (resp. loop).

The order of permutations in `P` is important in the quasigroup case, but it is disregarded in the loop case, since then the order of rows in the corresponding multiplication table is determined by the presence of the neutral element.

`‣ QuasigroupByRightSection` ( P ) | ( operation ) |

`‣ LoopByRightSection` ( P ) | ( operation ) |

These are the dual operations to `QuasigroupByLeftSection`

and `LoopByLeftSection`

.

gap> S := Subloop( MoufangLoop( 12, 1 ), [ 3 ] );; gap> ls := LeftSection( S ); [ (), (1,3,5), (1,5,3) ] gap> CayleyTableByPerms( ls ); [ [ 1, 3, 5 ], [ 3, 5, 1 ], [ 5, 1, 3 ] ] gap> CayleyTable( LoopByLeftSection( ls ) ); [ [ 1, 2, 3 ], [ 2, 3, 1 ], [ 3, 1, 2 ] ]

Let \(G\) be a group, \(H\) a subgroup of \(G\), and \(T\) a right transversal to \(H\) in \(G\). Let \(\tau:G\to T\) be defined by \(x\in H\tau(x)\). Then the operation \(\circ\) defined on the right cosets \(Q = \{Ht|t\in T\}\) by \(Hs\circ Ht = H\tau(st)\) turns \(Q\) into a quasigroup if and only if \(T\) is a right transversal to all conjugates \(g^{-1}Hg\) of \(H\) in \(G\). (In fact, every quasigroup \(Q\) can be obtained in this way by letting \(G={\rm Mlt}_\rho(Q)\), \(H={\rm Inn}_\rho(Q)\) and \(T=\{R_x|x\in Q\}\).)

We call the triple \((G,H,T)\) a *right quasigroup (or loop) folder*.

`‣ QuasigroupByRightFolder` ( G, H, T ) | ( operation ) |

`‣ LoopByRightFolder` ( G, H, T ) | ( operation ) |

Returns: The quasigroup (resp. loop) from the right folder (`G`, `H`, `T`).

**Remark:** We do not support the dual operations for left sections since, by default, actions in **GAP** act on the right.

Here is a simple example in which \(T\) is actually the right section of the resulting loop.

gap> T := [ (), (1,2)(3,4,5), (1,3,5)(2,4), (1,4,3)(2,5), (1,5,4)(2,3) ];; gap> G := Group( T );; H := Stabilizer( G, 1 );; gap> LoopByRightFolder( G, H, T ); <loop of order 5>

Let \(K\), \(F\) be loops. Then a loop \(Q\) is an *extension* of \(K\) by \(F\) if \(K\) is a normal subloop of \(Q\) such that \(Q/K\) is isomorphic to \(F\). An extension \(Q\) of \(K\) by \(F\) is *nuclear* if \(K\) is an abelian group and \(K\le N(Q)\).

A map \(\theta:F\times F\to K\) is a *cocycle* if \(\theta(1,x) = \theta(x,1) = 1\) for every \(x\in F\).

The following theorem holds for loops \(Q\), \(F\) and an abelian group \(K\): \(Q\) is a nuclear extension of \(K\) by \(F\) if and only if there is a cocycle \(\theta:F\times F\to K\) and a homomorphism \(\varphi:F\to{\rm Aut}(Q)\) such that \(K\times F\) with multiplication \((a,x)(b,y) = (a\varphi_x(b)\theta(x,y),xy)\) is isomorphic to \(Q\).

`‣ NuclearExtension` ( Q, K ) | ( operation ) |

Returns: The data necessary to construct `Q` as a nuclear extension of the subloop `K` by `Q`\(/\)`K`, namely \([K, F, \varphi, \theta]\) as above. Note that `K` must be a commutative subloop of the nucleus of `Q`.

If \(n=|F|\) and \(m=|\)`K`\(|\), the cocycle \(\theta\) is returned as an \(n\times n\) array with entries in \(\{1,\dots,m\}\), and the homomorphism \(\varphi\) is returned as a list of length \(n\) of permutations of \(\{1,\dots,m\}\).

`‣ LoopByExtension` ( K, F, f, t ) | ( operation ) |

Returns: The extension of an abelian group `K` by a loop `F`, using action `f` and cocycle `t`. The arguments must be formatted as the output of `NuclearExtension`

.

gap> F := IntoLoop( Group( (1,2) ) ); <loop of order 2> gap> K := DirectProduct( F, F );; gap> phi := [ (), (2,3) ];; gap> theta := [ [ 1, 1 ], [ 1, 3 ] ];; gap> LoopByExtension( K, F, phi, theta ); <loop of order 8> gap> IsAssociative( last ); false

An algorithm is said to select a latin square of order \(n\) *at random* if every latin square of order \(n\) is returned by the algorithm with the same probability. Selecting a latin square at random is a nontrivial problem.

In [JM96], Jacobson and Matthews defined a random walk on the space of latin squares and so-called improper latin squares that visits every latin square with the same probability. The diameter of the space is no more than \(4(n-1)^3\) in the sense that no more than \(4(n-1)^3\) properly chosen steps are needed to travel from one latin square of order \(n\) to another.

The Jacobson-Matthews algorithm can be used to generate random quasigroups as follows: (i) select any latin square of order \(n\), for instance the canonical multiplication table of the cyclic group of order \(n\), (ii) perform sufficiently many steps of the random walk, stopping at a proper or improper latin square, (iii) if necessary, perform a few more steps to end up with a proper latin square. Upon normalizing the resulting latin square, we obtain a random loop of order \(n\).

By the above result, it suffices to use about \(n^3\) steps to arrive at any latin square of order \(n\) from the initial latin square. In fact, a smaller number of steps is probably sufficient.

`‣ RandomQuasigroup` ( n[, iter] ) | ( operation ) |

`‣ RandomLoop` ( n[, iter] ) | ( operation ) |

Returns: A random quasigroup (resp. loop) of order `n` using the Jacobson-Matthews algorithm. If the optional argument `iter` is omitted, `n`\({}^3\) steps are used. Otherwise `iter` steps are used.

If `iter` is small, the Cayley table of the returned quasigroup (resp. loop) will be close to the canonical Cayley table of the cyclic group of order `n`.

`‣ RandomNilpotentLoop` ( lst ) | ( operation ) |

Returns: A random nilpotent loop as follows (see Section 6.9 for more information on nilpotency): `lst` must be a list of positive integers and/or finite abelian groups. If

and `lst`=[a1]`a1`

is an integer, a random abelian group of order `a1`

is returned, else `a1`

is an abelian group and `AsLoop(a1)`

is returned. If

, a random central extension of `lst`= [a1,...,am]`RandomNilpotentLoop([a1])`

by `RandomNilpotentLoop([a2,...,am])`

is returned.

To determine the nilpotency class \(c\) of the resulting loop, assume that `lst` has length at least 2, contains only integers bigger than 1, and let \(m\) be the last entry of `lst`. If \(m>2\) then \(c\) is equal to `Length(`

, else \(c\) is equal to `lst`)`Length(`

.`lst`)-1

**LOOPS** contains methods that convert between magmas, quasigroups, loops and groups, provided such conversions are possible. Each of the conversion methods `IntoQuasigroup`

, `IntoLoop`

and `IntoGroup`

returns `fail`

if the requested conversion is not possible.

**Remark:** Up to version 2.0.0 of **LOOPS**, we supported `AsQuasigroup`

, `AsLoop`

and `AsGroup`

in place of `IntoQuasigroup`

, `IntoLoop`

and `IntoGroup`

, respectively. We have changed the terminology starting with version 2.1.0 in order to comply with **GAP** naming rules for `AsSomething`

, as explained in Chapter 3. Finally, the method `AsGroup`

is a core method of **GAP** that returns an fp group if its argument is an associative loop.

`‣ IntoQuasigroup` ( M ) | ( operation ) |

Returns: If `M` is a declared magma that happens to be a quasigroup, the corresponding quasigroup is returned. If `M` is already declared as a quasigroup, `M` is returned.

`‣ PrincipalLoopIsotope` ( M, f, g ) | ( operation ) |

Returns: An isomorphic copy of the principal isotope \((\)`M`,\(\circ)\) via the transposition \((1\),`f`\(\cdot\)`g`\()\). An isomorphic copy is returned rather than \((\)`M`,\(\circ)\) because in **LOOPS** all loops have to have neutral element labeled as \(1\).

Given a quasigroup \(M\) and two of its elements \(f\), \(g\), the principal loop isotope \(x\circ y = R_g^{-1}(x)\cdot L_f^{-1}(y)\) turns \((M,\circ)\) into a loop with neutral element \(f\cdot g\) (see Section 2.6).

`‣ IntoLoop` ( M ) | ( operation ) |

Returns: If `M` is a declared magma that happens to be a quasigroup (but not necessarily a loop!), a loop is returned as follows: If `M` is already declared as a loop, `M` is returned. Else, if `M` possesses a neutral element \(e\) and if \(f\) is the first element of `M`, then an isomorphic copy of `M` via the transposition \((e,f)\) is returned. If `M` does not posses a neutral element, `PrincipalLoopIsotope(`

is returned.`M`, `M.1`, `M.1`)

**Remark:** One could obtain a loop from a declared magma `M` in yet another way, by normalizing the Cayley table of `M`. The three approaches can result in nonisomorphic loops in general.

`‣ IntoGroup` ( M ) | ( operation ) |

Returns: If `M` is a declared magma that happens to be a group, the corresponding group is returned as follows: If `M` is already declared as a group, `M` is returned, else `RightMultiplicationGroup(IntoLoop(`

is returned, which is a permutation group isomorphic to `M`))`M`.

`‣ DirectProduct` ( Q1, ..., Qn ) | ( operation ) |

Returns: If each `Qi` is either a declared quasigroup, declared loop or a declared group, the direct product of `Q1`, \(\dots\), `Qn` is returned. If every `Qi` is a declared group, a group is returned; if every `Qi` is a declared loop, a loop is returned; otherwise a quasigroup is returned.

When \(Q\) is a quasigroup with multiplication \(\cdot\), the *opposite quasigroup* of \(Q\) is a quasigroup with the same underlying set as \(Q\) and with multiplication \(*\) defined by \(x*y=y\cdot x\).

`‣ Opposite` ( Q ) | ( attribute ) |

`‣ OppositeQuasigroup` ( Q ) | ( operation ) |

`‣ OppositeLoop` ( Q ) | ( operation ) |

Returns: The opposite of the quasigroup (resp. loop) `Q`. Note that if `OppositeQuasigroup(`

or `Q`)`OppositeLoop(`

are called, then the returned quasigroup or loop is not stored as an attribute of `Q`)`Q`.

generated by GAPDoc2HTML