\Chapter{Methods based on permutation groups}

Most calculations in the {\LOOPS} package are delegated to groups, taking
advantage of the various permutations and permutation groups associated with
quasigroups. This chapter explains in detail how the permutations associated
with a quasigroup are calculated, and it also describes some of the core
methods of {\LOOPS} based on permutations. Additional core methods can be found
in Chapter "Testing properties of quasigroups and loops".

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Parent of a quasigroup}

Let $Q$ be a quasigroup and $S$ a subquasigroup of $Q$. Since the
multiplication in $S$ coincides with the multiplication in $Q$, it is
reasonable not to store the multiplication table of $S$. However, the
quasigroup $S$ then must know that it is a subquasigroup of $Q$. In order to
facilitate this relationship, we introduce the attribute

\>Parent( <Q> ) A

for a quasigroup $Q$.

When $Q$ is <not> created as a subquasigroup of another quasigroup, the
attribute `Parent( <Q> )' is set to $Q$. When $Q$ is created as a subquasigroup
of a quasigroup $H$, we let `Parent( <Q> ) := Parent( <H> )'. Thus, in effect,
`Parent( <Q> )' is the largest quasigroup from which $Q$ has been created.

Let $Q$ be a quasigroup with parent $P$, where $P$ is some $n$-element
quasigroup. Let $x$ be an element of $Q$. Then `x![1]' is the position of $x$
among the elements of $P$, i.e., `x![1] = Position( Elements( P ), x )'. The
position of $x$ among the elements of $Q$ is obtained via

\>Position( <Q>, x ) O

While referring to elements of $Q$ by their positions, we therefore must decide
if the positions are meant among the elements of $Q$, or among the elements of
$P$. Since it requires no calculation to obtain `x![1]', <we always use the
position of an element in its parent quasigroup>. In this way, many attributes
of a quasigroup, including its Cayley table, are permanently tied to its
parent. It is now clear why we have not insisted that Cayley tables of
quasigroups must have entries covering the entire interval $1$, $\dots$, $m$,
for some $m$.

When $S$ is a list of quasigroup elements, not necessarily from the same
quasigroup, the operation

\>PosInParent( <S> )

returns the list of positions of elements of $S$ in the corresponding parent,
i.e., `PosInParent( <S> )[ i ] = S[ i ]![ 1 ] = Position( Parent( S[ i ] ), S[
i ] )'.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Comparing quasigroups with common parent}

\noindent Assume that $A$, $B$ are two quasigroups with common parent $Q$. Let
$G_A$, $G_B$ be the canonical generating sets of $A$ and $B$, respectively,
obtained by the method `GeneratorsSmallest', described above. Then we
define $A \< B$ if and only if $G_A \< G_B$ lexicographically.

Note that if $A$ is a subquasigroup of $B$, we get $A\<B$, but not necessarily
vice versa.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Subquasigroups and subloops}

When $S$ is a subset of a quasigroup $Q$ (loop $L$), the smallest subquasigroup
of $Q$ (subloop of $L$) generated by $S$ is returned via:

\>Subquasigroup( <Q>, <S> ) O
\>Subloop( <L>, <S> ) O

In fact, we allow $S$ to be a list of integers, too, representing the positions
of the respective elements in the parent quasigroup (loop).

The following two operations test if a quasigroup (loop) $S$ is a subquasigroup
(subloop) of a quasigroup $Q$. They return `true' if and only if $Q$ and $S$
have the same parent, and if $S$ is a subset of $Q$.

\>IsSubquasigroup( <Q>, <S> ) O
\>IsSubloop( <Q>, <S> ) O

The operation

\>AllSubloops( <L> ) O

returns a list of all subloops of the loop $L$.

Let $S$ be a subloop of $L$. The list of all right cosets\index{coset} of $S$
in $L$ is obtained via

\>RightCosets( <L>, <S> ) F

The coset $S$ is listed first, and the elements of each coset are ordered in
the same way as elements of $S$, i.e., if $S = [s_1,\dots,s_m]$ then
$Sx=[s_1x$, $\dots$, $s_mx]$.

When $S$ is a subloop of $L$, the right transversal\index{transversal} of $S$
with respect to $L$ is a subset of $L$ containing one element from each right
coset of $S$ in $L$. It is obtained by

\>RightTransversal( <L>, <S> ) O

and it returns the first element from each right coset obtained by
`RightCosets( <L>, <S> )'.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Translations and sections}

When $x$ is an element of a quasigroup $Q$, the left translation $L_x$ is a
permutation of $Q$. In {\LOOPS}, all permutations associated with quasigroups
and their elements are permutations in the sense of \GAP, i.e., bijections of
some interval $1$, $\dots$, $n$. Moreover, following our convention, the
numerical entries of the permutation point to the positions among elements of
`Parent( <Q> )', not $Q$.

The left and right translations by $x$ in $Q$ are obtained by

\>LeftTranslation( <Q>, <x> ) O
\>RightTranslation( <Q>, <x> ) O

The following two attributes calculate the left and right section of a
quasigroup $Q$:

\>LeftSection( <Q> ) A
\>RightSection( <Q> ) A

Here is an example illustrating the main features of the subquasigroup
construction and the relationship between a quasigroup and its parent.

Note how the Cayley table of the subquasigroup is created only upon explicit
demand. Also note that changing the names of elements of a subquasigroup
(subloop) automatically changes the names of the elements of the parent
subquasigroup (subloop). This is because the elements are shared.

\beginexample
gap> M := MoufangLoop( 12, 1 );; S := Subloop( M, [ M.5 ] );
<loop of order 3>
gap> [ Parent( S ) = M, Elements( S ), PosInParent( S ) ];
[ true, [ l1, l3, l5], [ 1, 3, 5 ] ]
gap> HasCayleyTable( S );
false
gap> SetLoopElmName( S, "s" );; Elements( S ); Elements( M );
[ s1, s3, s5 ]
[ s1, s2, s3, s4, s5, s6, s7, s8, s9, s10, s11, s12 ]
gap> CayleyTable( S );
[ [ 1, 3, 5 ], [ 3, 5, 1 ], [ 5, 1, 3 ] ]
gap> LeftSection( S );
[ (), (1,3,5), (1,5,3) ]
gap> [ HasCayleyTable( S ), Parent( S ) = M ];
[ true, true ]
gap> L := LoopByCayleyTable( CayleyTable( S ) );; Elements( L );
[ l1, l2, l3 ]
gap> [ Parent( L ) = L, IsSubloop( M, S ), IsSubloop( M, L ) ];
[ true, true, false ]
gap> LeftSection( L );
[ (), (1,2,3), (1,3,2) ]
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Multiplication groups}

The left multiplication group, right multiplication group and the
multiplication group of a quasigroup $Q$ are calculated as follows:

\>LeftMultiplicationGroup( <Q> ) A
\>RightMultiplicationGroup( <Q> ) A
\>MultiplicationGroup( <Q> ) A

Let $S$ be a subloop of a loop $L$. Then the <relative left multiplication
group>\index{relative left multiplication group} of $L$ with respect to $S$ is
the group $\langle L(x)|x\in S\rangle$, where $L(x)$ is the left translation by
$x$ in $Q$ restricted to $S$. The <relative right multiplication
group>\index{relative right multiplication group} and <relative multiplication
group> \index{relative multiplication group} are defined analogously.

\>RelativeLeftMultiplicationGroup( <L>, <S> ) O
\>RelativeRightMultiplicationGroup( <L>, <S> ) O
\>RelativeMultiplicationGroup( <L>, <S> ) O

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Inner mapping groups}

The <inner mapping group>\index{inner mapping group} of a loop $L$ is the
stabilizer of the unit element in ${\rm{Mlt}}(L)$. The elements of this
stabilizer are called <inner maps> of $L$.

The <left inner mapping group>\index{left inner mapping group} of a loop $L$ is
the stabilizer of the unit element in ${\rm{LMlt}}(L)$. The <right inner
mapping group>\index{right inner mapping group} is defined dually.

Equivalently, the left inner mapping group is generated by all <left inner
mappings>\index{left inner mapping} $L(x,y) = L_{yx}^{-1}L_yL_x$, and the right
inner mapping group is generated by all <right inner mappings>\index{right
inner mapping} $R(x,y) = R_{xy}^{-1}R_yR_x$.

In analogy with group theory, we define the <conjugation>\index{conjugation},
or the <middle inner mapping>\index{middle inner mapping} by $x$ as $T(x) =
L_x^{-1}R_x$. The <middle inner mapping>\index{middle inner mapping} is then
the subgroup of ${\rm{Mlt}}(L)$ generated by all conjugations.

The corresponding commands in {\LOOPS} are

\>LeftInnerMapping( <L>, <x>, <y> ) O
\>MiddleInnerMapping( <L>, <x> ) O
\>RightInnerMapping( <L>, <x>, <y> ) O
\>LeftInnerMappingGroup( <L> ) A
\>MiddleInnerMappingGroup( <L> ) A
\>RightInnerMappingGroup( <L> ) A
\>InnerMappingGroup( <L> ) A

Here is an example for multiplication groups and inner mapping groups:

\beginexample
gap> M := MoufangLoop( 12, 1 );
<Moufang loop 12/1>
gap> LeftSection( M )[ 2 ];
(1,2)(3,4)(5,6)(7,8)(9,12)(10,11)
gap> Mlt := MultiplicationGroup( M ); Inn := InnerMappingGroup( M );
<permutation group of size 2592 with 23 generators>
Group([ (4,6)(7,11), (7,11)(8,10), (2,6,4)(7,9,11), (3,5)(9,11), (8,12,10) ])
gap> Size( Inn );
216
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Nuclei, commutant, center, and associator subloop}

Let $Q$ be a quasigroup. The <left nucleus>\index{left nucleus} $N_\lambda(Q)$
of $Q$ is the set $\{x\in Q| x(yz)=(xy)z$ for every $y$, $z\in Q\}$. One
defines similarly the <middle nucleus>\index{middle nucleus} $N_\mu(Q)$ and the
<right nucleus>\index{right nucleus} $N_\rho(Q)$. Then the
<nucleus>\index{nucleus} $N(Q)$ of $Q$ is the intersection of the three nuclei.

The nuclei are calculated in {\LOOPS} as follows:

\>LeftNucleus( <Q> ) A
\>MiddleNucleus( <Q> ) A
\>RightNucleus( <Q> ) A
\>Nuc( <Q> ) A

Unfortunately, the word `Nucleus' is reserved in the core of {\GAP} for a
global function with two variables. That is the reason why we have used the
abbreviation `Nuc', which is also common in the literature. However, we support
these synonyms of `Nuc':

\>NucleusOfLoop( <Q> ) A
\>NucleusOfQuasigroup( <Q> ) A

Since all nuclei are subquasigroups of $Q$, they are returned as subquasigroups
(resp. subloops). When $Q$ is a loop then all nuclei are in fact groups, and
they are returned as associative loops.

The <commutant>\index{commutant} $C(Q)$ of $Q$ is the set $\{x\in Q\,|\,xy=yx$
for every $y\in Q\}$. It is also known under the name <Moufang
center>\index{Moufang center} and <centrum>\index{centrum}. It is obtained via

\>Commutant( <Q> ) A

The center $Z(Q)$ is defined as the intersection of $C(Q)$ and $N(Q)$, and it
is obtained via

\>Center( <Q> ) A

It is a subgroup of $<Q>$ and is therefore returned as an associative loop.

Finally, the <associator subloop>\index{associator subloop} of a loop $L$ is
the smallest normal subloop $A(L)$ of $L$ containing all associators of $L$.
Equivalently, $A(L)$ is the smallest normal subloop $K$ such that $L/K$ is
associative. We use another equivalent reformulation for the purposes of
computation: $A(L)$ is the smallest normal subloop of $L$ containing
$\{x\setminus\alpha(x)\,|\,x\in L,\,\alpha$ is a left inner mapping$\}$.

\>AssociatorSubloop( <L> )  A

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Normal subloops}

A subloop $S$ of a loop $L$ is <normal>\index{normal subloop} if it is
invariant under all inner mappings of $L$. Normality is tested via:

\>IsNormal( <L>, <S> ) O

When $S$ is a subset of a loop $L$ or a subloop of $L$, the <normal
closure>\index{normal closure} of $S$ in $L$ is the smallest normal subloop of
$L$ containing $S$. It is obtained by

\>NormalClosure( <L>, <S> ) O

A loop $L$ is <simple>\index{simple loop} if all normal subloops of $L$ are
trivial. The corresponding test in {\LOOPS} is:

\>IsSimple( <L> ) O

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Factor loops}

When $N$ is a normal subloop of a loop $L$, the factor loop $L/N$ can be
obtained directly via the command `L/N', or by

\>FactorLoop( <L>, <N> ) O

The natural projection from $L$ to $L/N$ is returned by

\>NaturalHomomorphismByNormalSubloop( <L>, <N> ) O

Here is an illustrating example:

\beginexample
gap> M := MoufangLoop( 12, 1 );; S := Subloop( M, [ M.3 ] );
<loop of order 3>
gap> IsNormal( M, S );
true
gap> F := FactorLoop( M, S );
<loop of order 4>
gap> NaturalHomomorphismByNormalSubloop( M, S );
MappingByFunction( <loop of order 12>, <loop of order 4>,
    function( x ) ... end )
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Nilpotency and central series}

The definition of nilpotency and nilpotence class is the same as in group
theory. The corresponding commands are:

\>NilpotencyClassOfLoop( <L> ) A
\>IsNilpotent( <L> ) P

When $L$ is not nilpotent, `NilpotencyClassOfLoop( <L> )' returns `fail'.

A loop $L$ is said to be <strongly nilpotent>\index{strongly nilpotent loop} if
its multiplication group is nilpotent. This property is obtained by

\>IsStronglyNilpotent( <L> ) P

Let $L$ be a loop. Define <iterated centers>\index{iterated centers} $Z_i(L)$
as follows: $Z_0(L)=Z(L)$, $Z_{i+1}(L) = \pi_i^{-1}( Z_i(L) )$, where $\pi_i$
is the canonical projection $L\to L/Z_i(L)$. The longest series $Z_i(L)$,
$Z_{i-1}(L)$, $\dots$, $Z_0(L)$ with $Z_i(L)>Z_{i-1}(L)>\cdots >Z_0(L)$ is
called the <upper central series>\index{upper central series} of $L$, and is
returned via

\>UpperCentralSeries( <L> ) A

The <lower central series>\index{lower central series}, defined in the usual
way, is obtained by

\>LowerCentralSeries( <L> ) A

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Solvability}

The definition of solvability, derived subloop, derived length, Frattini
subloop and Frattini factor size is the same as for groups. Frattini subloop is
calculated only for strongly nilpotent loops.

\>IsSolvable( <L> ) P
\>DerivedSubloop( <L> ) A
\>DerivedLength( <L> ) A
\>FrattiniSubloop( <L> ) A
\>FrattinifactorSize( <L> ) A

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Isomorphisms and automorphisms}

All isomorphisms between two loops can be found with {\LOOPS}. The operation

\>IsomorphismLoops( <L>, <M> ) O

returns a single isomorphism between loops $L$, $M$ if the loops are
isomorphic, and `fail' otherwise.

If an isomorphism exists, it is returned as a permutation $p$ of $1$, $\dots$,
$|L|$, where $i^p=j$ means that the $i$th element of $L$ is mapped onto the
$j$th element of $M$. This is true even if $L$ or $M$ are not their own
parents.

Since one frequently needs to filter a list of loops up to isomorphism, we
support

\>LoopsUpToIsomorphism( <ls> ) O

Given a list $ls$ of loops, the operation returns a sublist of $ls$ containing
one loop from each isomorphism class of loops present in $ls$.

The attribute

\>AutomorphismGroup( <L> ) A

returns the automorphism group of the loop $L$, with the same convention on
permutations as in the case of `IsomorphismLoops'.

Since two isomorphisms \"differ\" by an automorphism, all isomorphisms can be
obtained by the above two functions.

While dealing with Cayley tables, it is often useful to rename or reorder the
elements without changing the isomorphism type. When $Q$ is a quasigroup of
size $n$ and $p$ is a permutation of $\{1,\dots,n\}$,

\>IsomorphicCopyByPerm( Q, p )

returns quasigroup $(Q,\circ)$ such that $p(xy) = p(x)\circ p(y)$, i.e.,
$x\circ y = p( p^{-1}(x)p^{-1}(y))$. When $Q$ is a declared loop, a loop is
returned. Consequently, when $Q$ is a declared loop and $p(1) = k\ne 1$, then
$p$ is first replaced by $p\circ (1,k)$, to make sure that the Cayley table is
normalized.

When $S$ is a normal subloop of $L$,

\>IsomorphicCopyByNormalSubloop( L, S )

returns an isomorphic copy of $L$ in which the elements are ordered according
to the right cosets of $S$. In particular, the Cayley table of $S$ will appear
in the top left corner of the Cayley table of the resulting loop.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{How are isomorphisms computed}

In order to speed up the search for isomorphisms and automorphisms, we first
calculate some loop invariants preserved under isomorphisms, and use these
invariants to partition the loop into blocks of elements preserved under
isomorphisms. These invariants for a loop $L$ can be obtained via

\>Discriminator( <L> ) O

Since the details are technical, we will not present them here. See \cite{Vo}
or the file `iso.gi' for more.

If two loops have different discriminators, they are not isomorphic. If they
have identical discriminators, they may or may not be isomorphic. The operation

\>AreEqualDiscriminators( <D1>, <D2> ) O

returns `true' if the discriminators $D1$, $D2$ are equal.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Isotopisms}

The package contains a slow method for testing if two loops are isotopic:

\>IsotopismLoops( <K>, <L> ) O

It returns `fail' if $K$, $L$ are not isotopic, else it returns an isotopism as
a triple of bijections on $\{1,\dots,|K|\}$.

The method works as follows: It is well known that if a loop $K$ is isotopic to
a loop $L$ then there exist a principal loop isotope $P$ of $K$ such that $P$
is isomorphic to $L$. The algorithm first finds all principal isotopes of $K$,
then filters them up to isomorphism, and then checks if any of them is
isomorphic to $L$. This is rather slow already for small orders, say $30$.

The function

\>LoopsUpToIsotopism( <ls> ) O

filters the list $ls$ in a way similar to `LoopsUpToIsomorphism', but using
isotopism as the underlying equivalence relation.