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 ⋅ 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 ⋅, if the entry in the row x_i and column x_j is x_i⋅ 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 < ⋯ < 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(Q) when Q is a declared quasigroup, and LoopByCayleyTable(CanonicalCayleyTable(Q) when 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⟹ 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 backslashbackslash to ensure that every occurrence of backslash is deleted, since backslashbackslash 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(Q) returns the multiplication table of 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 τ:G-> T be defined by x∈ Hτ(x). Then the operation ∘ defined on the right cosets Q = {Ht|t∈ T} by Hs∘ Ht = Hτ(st) turns Q into a quasigroup if and only if T is a right transversal to all conjugates g^-1Hg of H in G. (In fact, every quasigroup Q can be obtained in this way by letting G= Mlt_ρ(Q), H= Inn_ρ(Q) and T={R_x|x∈ 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≤ N(Q).
A map θ:F× F-> K is a cocycle if θ(1,x) = θ(x,1) = 1 for every x∈ 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 θ:F× F-> K and a homomorphism φ:F-> Aut(Q) such that K× F with multiplication (a,x)(b,y) = (aφ_x(b)θ(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, φ, θ] as above. Note that K must be a commutative subloop of the nucleus of Q.
If n=|F| and m=|K|, the cocycle θ is returned as an n× n array with entries in {1,dots,m}, and the homomorphism φ 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 lst=[a1] and 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 lst= [a1,...,am], a random central extension of 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(lst), else c is equal to 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,∘) via the transposition (1,f⋅g). An isomorphic copy is returned rather than (M,∘) 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∘ y = R_g^-1(x)⋅ L_f^-1(y) turns (M,∘) into a loop with neutral element f⋅ 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(M, M.1, M.1) is returned.
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(M)) is returned, which is a permutation group isomorphic to 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 ⋅, the opposite quasigroup of Q is a quasigroup with the same underlying set as Q and with multiplication * defined by x*y=y⋅ x.
‣ Opposite( Q ) | ( attribute ) |
‣ OppositeQuasigroup( Q ) | ( operation ) |
‣ OppositeLoop( Q ) | ( operation ) |
Returns: The opposite of the quasigroup (resp. loop) Q. Note that if OppositeQuasigroup(Q) or OppositeLoop(Q) are called, then the returned quasigroup or loop is not stored as an attribute of Q.
generated by GAPDoc2HTML