[MathJax on]

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

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

6.1-1 Parent

Returns: The parent quasigroup of the 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 set Parent(Q) equal to Parent(H). Thus, in effect, Parent(Q) is the largest quasigroup from which Q has been created.

6.1-2 Position

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 x![1] is the position of 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 x![1], we always use the position of an element in its parent quasigroup in 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.

6.1-3 PosInParent

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.

6.2 Subquasigroups and Subloops

6.2-1 Subquasigroup

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(Q,S) returns the empty set if 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(Q) for a quasigroup Q with empty center.

6.2-2 Subloop

This is an analog of Subquasigroup(Q,S) that can be used only when Q is a loop. Since there is no difference in the outcome while calling Subquasigroup(Q,S) or Subloop(Q,S) when Q is a loop, it is safe to always call Subquasigroup(Q,S), whether Q is a loop or not.

6.2-3 IsSubquasigroup and IsSubloop

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.

6.2-4 AllSubquasigroups

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

6.2-5 AllSubloops

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

6.2-6 RightCosets

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 Sx=[s_1x,dots,s_mx].

6.2-7 RightTransversal

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.

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

6.3-1 LeftTranslation and RightTranslation

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

6.3-2 LeftSection and RightSection

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

6.4 Multiplication Groups

6.4-1 LeftMultiplicationGroup, RightMultiplicationGroup and MultiplicationGroup

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

6.4-2 RelativeLeftMultiplicationGroup, RelativeRightMultiplicationGroup and RelativeMultiplicationGroup

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 ⟨ L(x)|x∈ S⟩, 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.

6.5 Inner Mapping Groups

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^-1L_yL_x, and the right inner mapping group is generated by all right inner mappings R(x,y) = R_xy^-1R_yR_x.

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

6.5-1 LeftInnerMapping, RightInnerMapping, MiddleInnerMapping

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.

6.5-2 LeftInnerMappingGroup, RightInnerMappingGroup, MiddleInnerMappingGroup

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

6.5-3 InnerMappingGroup

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

6.6 Nuclei, Commutant, Center, and Associator Subloop

See Section 2.3 for the relevant definitions.

6.6-1 LeftNucleus, MiddleNucleus, and RightNucleus

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

6.6-2 Nuc, NucleusOfQuasigroup and NucleusOfLoop

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.

6.6-3 Commutant

Returns: The commutant of a quasigroup Q.

6.6-4 Center

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.

6.6-5 AssociatorSubloop

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 xbackslashα(x), where x is an element of Q and α is a left inner mapping of Q.

6.7 Normal Subloops and Simple Loops

6.7-1 IsNormal

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.

6.7-2 NormalClosure

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.

6.7-3 IsSimple

Returns: true if Q is a simple loop.

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

6.8 Factor Loops

6.8-1 FactorLoop

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

6.8-2 NaturalHomomorphismByNormalSubloop

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 )

6.9 Nilpotency and Central Series

See Section 2.4 for the relevant definitions.

6.9-1 IsNilpotent

Returns: true if Q is a nilpotent loop.

6.9-2 NilpotencyClassOfLoop

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

6.9-3 IsStronglyNilpotent

Returns: true if Q is a strongly nilpotent loop.

A loop Q is said to be strongly nilpotent if its multiplication group is nilpotent.

6.9-4 UpperCentralSeries

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

6.9-5 LowerCentralSeries

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.

6.10 Solvability, Derived Series and Frattini Subloop

See Section 2.4 for definitions of solvability an derived subloop.

6.10-1 IsSolvable

Returns: true if Q is a solvable loop.

6.10-2 DerivedSubloop

Returns: The derived subloop of a loop Q.

6.10-3 DerivedLength

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

6.10-4 FrattiniSubloop and FrattinifactorSize

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.

6.10-5 FrattinifactorSize

6.11 Isomorphisms and Automorphisms

6.11-1 IsomorphismQuasigroups

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 ith element of Q is mapped onto the jth element of L. Note that this convention is used even if the underlying sets of Q, L are not indexed by consecutive integers.

6.11-2 IsomorphismLoops

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.

6.11-3 QuasigroupsUpToIsomorphism

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

6.11-4 LoopsUpToIsomorphism

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

6.11-5 AutomorphismGroup

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(Q,L) (or IsomorphismQuasigroups(Q,L)) and 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.

6.11-6 QuasigroupIsomorph

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

6.11-7 LoopIsomorph

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)=cne 1, the isomorphism (1,c) is applied after f.

6.11-8 IsomorphicCopyByPerm

Returns: LoopIsomorphism(Q,f) if Q is a loop, and QuasigroupIsomorphism(Q,f) if Q is a quasigroup.

6.11-9 IsomorphicCopyByNormalSubloop

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.

6.11-10 Discriminator

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.

6.11-11 AreEqualDiscriminators

Returns: true if D1, D2 are equal discriminators for the purposes of isomorphism searches.

6.12 Isotopisms

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.

6.12-1 IsotopismLoops

Returns: fail if K, L are not isotopic loops, else it returns an isotopism as a triple of bijections on 1,dots,|K|.

6.12-2 LoopsUpToIsotopism

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