6 Methods Based on Permutation Groups

6.11 Isomorphisms and Automorphisms

6.11-1 IsomorphismQuasigroups

6.11-2 IsomorphismLoops

6.11-3 QuasigroupsUpToIsomorphism

6.11-4 LoopsUpToIsomorphism

6.11-5 AutomorphismGroup

6.11-6 QuasigroupIsomorph

6.11-7 LoopIsomorph

6.11-8 IsomorphicCopyByPerm

6.11-9 IsomorphicCopyByNormalSubloop

6.11-10 Discriminator

6.11-11 AreEqualDiscriminators

6.11-1 IsomorphismQuasigroups

6.11-2 IsomorphismLoops

6.11-3 QuasigroupsUpToIsomorphism

6.11-4 LoopsUpToIsomorphism

6.11-5 AutomorphismGroup

6.11-6 QuasigroupIsomorph

6.11-7 LoopIsomorph

6.11-8 IsomorphicCopyByPerm

6.11-9 IsomorphicCopyByNormalSubloop

6.11-10 Discriminator

6.11-11 AreEqualDiscriminators

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 7.

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\).

`‣ Parent` ( Q ) | ( attribute ) |

Returns: The parent quasigroup of the quasigroup `Q`.

When `Q` is not created as a subquasigroup of another quasigroup, the attribute `Parent(`

is set to `Q`)`Q`. When `Q` is created as a subquasigroup of a quasigroup `H`, we set `Parent(`

equal to `Q`)`Parent(`

. Thus, in effect, `H`)`Parent(`

is the largest quasigroup from which `Q`)`Q` has been created.

`‣ Position` ( Q, x ) | ( operation ) |

Returns: The position of `x` among the elements of `Q`.

Let `Q` be a quasigroup with parent `P`, where `P` is some \(n\)-element quasigroup. Let `x` be an element of `Q`. Then

is the position of `x`![1]`x` among the elements of `P`, i.e.,

.`x`![1] = Position(Elements(`P`),`x`)

While referring to elements of `Q` by their positions, the user should understand whether the positions are meant among the elements of `Q`, or among the elements of the parent `P` of `Q`. Since it requires no calculation to obtain

, we always use the position of an element in its parent quasigroup in `x`![1]**LOOPS**. 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\), \(n\) for some \(n\).

`‣ PosInParent` ( S ) | ( operation ) |

Returns: When `S` is a list of quasigroup elements (not necessarily from the same quasigroup), returns the corresponding 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])

Quasigroups with the same parent can be compared as follows. 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`

(see Section 5.5). Then we define \(A<B\) if and only if \(G_A<G_B\) lexicographically.

`‣ Subquasigroup` ( Q, S ) | ( operation ) |

Returns: When `S` is a subset of elements or indices of a quasigroup (resp. loop) `Q`, returns the smallest subquasigroup (resp. subloop) of `Q` containing `S`.

We allow `S` to be a list of elements of `Q`, or a list of integers representing the positions of the respective elements in the parent quasigroup (resp. loop) of `Q`.

If `S` is empty, `Subquasigroup(`

returns the empty set if `Q`,`S`)`Q` is a quasigroup, and it returns the one-element subloop of `Q` if `Q` is a loop.

**Remark:** The empty set is sometimes considered to be a subquasigroup of `Q` (although not in **LOOPS**). The above convention is useful for handling certain situations, for instance when the user calls `Center(`

for a quasigroup `Q`)`Q` with empty center.

`‣ Subloop` ( Q, S ) | ( operation ) |

This is an analog of `Subquasigroup(`

that can be used only when `Q`,`S`)`Q` is a loop. Since there is no difference in the outcome while calling `Subquasigroup(`

or `Q`,`S`)`Subloop(`

when `Q`,`S`)`Q` is a loop, it is safe to always call `Subquasigroup(`

, whether `Q`,`S`)`Q` is a loop or not.

`‣ IsSubquasigroup` ( Q, S ) | ( operation ) |

`‣ IsSubloop` ( Q, S ) | ( operation ) |

Returns: `true`

if `S` is a subquasigroup (resp. subloop) of a quasigroup (resp. loop) `Q`, `false`

otherwise. In other words, returns `true`

if `S` and `Q` are quasigroups (resp. loops) with the same parent and `S` is a subset of `Q`.

`‣ AllSubquasigroups` ( Q ) | ( operation ) |

Returns: A list of all subquasigroups of a loop `Q`.

`‣ AllSubloops` ( Q ) | ( operation ) |

Returns: A list of all subloops of a loop `Q`.

`‣ RightCosets` ( Q, S ) | ( function ) |

Returns: If `S` is a subloop of `Q`, returns a list of all right cosets of `S` in `Q`.

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

`‣ RightTransversal` ( Q, S ) | ( operation ) |

Returns: A right transversal of a subloop `S` in a loop `Q`. The transversal consists of the list of first elements from the right cosets obtained by `RightCosets(`

.`Q`,`S`)

When `S` is a subloop of `Q`, the right transversal of `S` with respect to `Q` is a subset of `Q` containing one element from each right coset of `S` in `Q`.

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., they are bijections of some interval \(1\), \(\dots\), \(n\). Moreover, following our convention, the numerical entries of the permutations point to the positions among elements of the parent of \(Q\), not among elements of \(Q\).

`‣ LeftTranslation` ( Q, x ) | ( operation ) |

`‣ RightTranslation` ( Q, x ) | ( operation ) |

Returns: If `x` is an element of a quasigroup `Q`, returns the left translation (resp. right translation) by `x` in `Q`.

`‣ LeftSection` ( Q ) | ( operation ) |

`‣ RightSection` ( Q ) | ( operation ) |

Returns: The left section (resp. right section) of a quasigroup `Q`.

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 a 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.

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) ]

`‣ LeftMultiplicationGroup` ( Q ) | ( attribute ) |

`‣ RightMultiplicationGroup` ( Q ) | ( attribute ) |

`‣ MultiplicationGroup` ( Q ) | ( attribute ) |

Returns: The left multiplication group, right multiplication group, resp. multiplication group of a quasigroup `Q`.

`‣ RelativeLeftMultiplicationGroup` ( Q, S ) | ( operation ) |

`‣ RelativeRightMultiplicationGroup` ( Q, S ) | ( operation ) |

`‣ RelativeMultiplicationGroup` ( Q, S ) | ( operation ) |

Returns: The relative left multiplication group, the relative right multiplication group, resp. the relative multiplication group of a quasigroup `Q` with respect to a subquasigroup `S` of `Q`.

Let \(S\) be a subquasigroup of a quasigroup \(Q\). Then the *relative left multiplication group* of \(Q\) 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* and the *relative multiplication group* are defined analogously.

By a result of Bruck, the left inner mapping group of a loop is generated by all *left inner mappings* \(L(x,y) = L_{yx}^{-1}L_yL_x\), and the right inner mapping group is generated by all *right inner mappings* \(R(x,y) = R_{xy}^{-1}R_yR_x\).

In analogy with group theory, we define the *conjugations* or the *middle inner mappings* as \(T(x) = L_x^{-1}R_x\). The *middle inner mapping grroup* is then the group generated by all conjugations.

`‣ LeftInnerMapping` ( Q, x, y ) | ( operation ) |

`‣ RightInnerMapping` ( Q, x, y ) | ( operation ) |

`‣ MiddleInnerMapping` ( Q, x ) | ( operation ) |

Returns: The left inner mapping \(L(\)`x`,`y`\()\), the right inner mapping \(R(\)`x`,`y`\()\), resp. the middle inner mapping \(T(\)`x`\()\) of a loop `Q`.

`‣ LeftInnerMappingGroup` ( Q ) | ( attribute ) |

`‣ RightInnerMappingGroup` ( Q ) | ( attribute ) |

`‣ MiddleInnerMappingGroup` ( Q ) | ( attribute ) |

Returns: The left inner mapping group, right inner mapping group, resp. middle inner mapping group of a loop `Q`.

`‣ InnerMappingGroup` ( Q ) | ( attribute ) |

Returns: The inner mapping group of a loop `Q`.

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

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

See Section 2.3 for the relevant definitions.

`‣ LeftNucleus` ( Q ) | ( attribute ) |

`‣ MiddleNucleus` ( Q ) | ( attribute ) |

`‣ RightNucleus` ( Q ) | ( attribute ) |

Returns: The left nucleus, middle nucleus, resp. right nucleus of a quasigroup `Q`.

`‣ Nuc` ( Q ) | ( attribute ) |

`‣ NucleusOfQuasigroup` ( Q ) | ( attribute ) |

`‣ NucleusOfLoop` ( Q ) | ( attribute ) |

Returns: These synonymous attributes return the nucleus of a quasigroup `Q`.

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.

**Remark:** The name `Nucleus`

is a global function of **GAP** with two variables. We have therefore used `Nuc`

rather than `Nucleus`

for the nucleus. This abbreviation is sometimes used in the literature, too.

`‣ Commutant` ( Q ) | ( attribute ) |

Returns: The commutant of a quasigroup `Q`.

`‣ Center` ( Q ) | ( attribute ) |

Returns: The center of a quasigroup `Q`.

If `Q` is a loop, the center of `Q` is a subgroup of `Q` and it is returned as an associative loop.

`‣ AssociatorSubloop` ( Q ) | ( attribute ) |

Returns: The associator subloop of a loop `Q`.

We calculate the associator subloop of `Q` as the smallest normal subloop of `Q` containing all elements \(x\backslash\alpha(x)\), where \(x\) is an element of `Q` and \(\alpha\) is a left inner mapping of `Q`.

`‣ IsNormal` ( Q, S ) | ( operation ) |

Returns: `true`

if `S` is a normal subloop of a loop `Q`.

A subloop \(S\) of a loop \(Q\) is *normal* if it is invariant under all inner mappings of \(Q\).

`‣ NormalClosure` ( Q, S ) | ( operation ) |

Returns: The normal closure of a subset `S` of a loop `Q`.

For a subset \(S\) of a loop \(Q\), the *normal closure* of \(S\) in \(Q\) is the smallest normal subloop of \(Q\) containing \(S\).

`‣ IsSimple` ( Q ) | ( operation ) |

Returns: `true`

if `Q` is a simple loop.

A loop \(Q\) is *simple* if \(\{1\}\) and \(Q\) are the only normal subloops of \(Q\).

`‣ FactorLoop` ( Q, S ) | ( operation ) |

Returns: When `S` is a normal subloop of a loop `Q`, returns the factor loop `Q`\(/\)`S`.

`‣ NaturalHomomorphismByNormalSubloop` ( Q, S ) | ( operation ) |

Returns: When `S` is a normal subloop of a loop `Q`, returns the natural projection from `Q` onto `Q`\(/\)`S`.

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 )

See Section 2.4 for the relevant definitions.

`‣ IsNilpotent` ( Q ) | ( property ) |

Returns: `true`

if `Q` is a nilpotent loop.

`‣ NilpotencyClassOfLoop` ( Q ) | ( attribute ) |

Returns: The nilpotency class of a loop `Q` if `Q` is nilpotent, `fail`

otherwise.

`‣ IsStronglyNilpotent` ( Q ) | ( property ) |

Returns: `true`

if `Q` is a strongly nilpotent loop.

A loop \(Q\) is said to be *strongly nilpotent* if its multiplication group is nilpotent.

`‣ UpperCentralSeries` ( Q ) | ( attribute ) |

Returns: When `Q` is a nilpotent loop, returns the upper central series of `Q`, else returns `fail`

.

`‣ LowerCentralSeries` ( Q ) | ( attribute ) |

Returns: When `Q` is a nilpotent loop, returns the lower central series of `Q`, else returns `fail`

.

The *lower central series* for loops is defined analogously to groups.

See Section 2.4 for definitions of solvability an derived subloop.

`‣ IsSolvable` ( Q ) | ( property ) |

Returns: `true`

if `Q` is a solvable loop.

`‣ DerivedSubloop` ( Q ) | ( attribute ) |

Returns: The derived subloop of a loop `Q`.

`‣ DerivedLength` ( Q ) | ( attribute ) |

Returns: If `Q` is solvable, returns the derived length of `Q`, else returns `fail`

.

`‣ FrattiniSubloop` ( Q ) | ( attribute ) |

Returns: The Frattini subloop of `Q`. The method is implemented only for strongly nilpotent loops.

*Frattini subloop* of a loop \(Q\) is the intersection of maximal subloops of \(Q\).

`‣ FrattinifactorSize` ( Q ) | ( attribute ) |

`‣ IsomorphismQuasigroups` ( Q, L ) | ( operation ) |

Returns: An isomorphism from a quasigroup `Q` to a quasigroup `L` if the quasigroups are isomorphic, `fail`

otherwise.

If an isomorphism exists, it is returned as a permutation \(f\) of \(1,\dots,|\)`Q`\(|\), where \(i^f=j\) means that the \(i\)th element of `Q` is mapped onto the \(j\)th element of `L`. Note that this convention is used even if the underlying sets of `Q`, `L` are not indexed by consecutive integers.

`‣ IsomorphismLoops` ( Q, L ) | ( operation ) |

Returns: An isomorphism from a loop `Q` to a loop `L` if the loops are isomorphic, `fail`

otherwise, with the same convention as in `IsomorphismQuasigroups`

.

`‣ QuasigroupsUpToIsomorphism` ( ls ) | ( operation ) |

Returns: Given a list `ls` of quasigroups, returns a sublist of `ls` consisting of representatives of isomorphism classes of quasigroups from `ls`.

`‣ LoopsUpToIsomorphism` ( ls ) | ( operation ) |

Returns: Given a list `ls` of loops, returns a sublist of `ls` consisting of representatives of isomorphism classes of loops from `ls`.

`‣ AutomorphismGroup` ( Q ) | ( attribute ) |

Returns: The automorphism group of a loop or quasigroups `Q`, with the same convention on permutations as in `IsomorphismQuasigroups`

.

**Remark:** Since two isomorphisms differ by an automorphism, all isomorphisms from `Q` to `L` can be obtained by a combination of `IsomorphismLoops(`

(or `Q`,`L`)`IsomorphismQuasigroups(`

) and `Q`,`L`)`AutomorphismGroup(`

. `L`)

While dealing with Cayley tables, it is often useful to rename or reorder the elements of the underlying quasigroup without changing the isomorphism type of the quasigroups. **LOOPS** contains several functions for this purpose.

`‣ QuasigroupIsomorph` ( Q, f ) | ( operation ) |

Returns: When `Q` is a quasigroup and `f` is a permutation of \(1,\dots,|\)`Q`\(|\), returns the quasigroup defined on the same set as `Q` with multiplication \(*\) defined by \(x*y = \)`f`\((\)`f`\({}^{-1}(x)\)`f`\({}^{-1}(y))\).

`‣ LoopIsomorph` ( Q, f ) | ( operation ) |

Returns: When `Q` is a loop and `f` is a permutation of \(1,\dots,|\)`Q`\(|\) fixing \(1\), returns the loop defined on the same set as `Q` with multiplication \(*\) defined by \(x*y = \)`f`\((\)`f`\({}^{-1}(x)\)`f`\({}^{-1}(y))\). If `f`\((1)=c\ne 1\), the isomorphism \((1,c)\) is applied after `f`.

`‣ IsomorphicCopyByPerm` ( Q, f ) | ( operation ) |

Returns: `LoopIsomorphism(`

if `Q`,`f`)`Q` is a loop, and `QuasigroupIsomorphism(`

if `Q`,`f`)`Q` is a quasigroup.

`‣ IsomorphicCopyByNormalSubloop` ( Q, S ) | ( operation ) |

Returns: When `S` is a normal subloop of a loop `Q`, returns an isomorphic copy of `Q` 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.

In order to speed up the search for isomorphisms and automorphisms, we first calculate some loop invariants preserved under isomorphisms, and then we use these invariants to partition the loop into blocks of elements preserved under isomorphisms. The following two operations are used in the search.

`‣ Discriminator` ( Q ) | ( operation ) |

Returns: A data structure with isomorphism invariants of a loop `Q`.

See [Voj06] or the file `iso.gi`

for more details. The format of the discriminator has been changed from version 3.2.0 up to accommodate isomorphism searches for quasigroups.

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

`‣ AreEqualDiscriminators` ( D1, D2 ) | ( operation ) |

Returns: `true`

if `D1`, `D2` are equal discriminators for the purposes of isomorphism searches.

At the moment, **LOOPS** contains only slow methods for testing if two loops are isotopic. 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.

`‣ IsotopismLoops` ( K, L ) | ( operation ) |

Returns: `fail`

if `K`, `L` are not isotopic loops, else it returns an isotopism as a triple of bijections on \(1,\dots,|\)`K`\(|\).

`‣ LoopsUpToIsotopism` ( ls ) | ( operation ) |

Returns: Given a list `ls` of loops, returns a sublist of `ls` consisting of representatives of isotopism classes of loops from `ls`.

generated by GAPDoc2HTML