[Up] [Previous] [Next] [Index]

5 Some methods based on permutation groups

Sections

  1. Parent of a quasigroup
  2. Comparing quasigroups with common parent
  3. Subquasigroups and subloops
  4. Translations and sections
  5. Multiplication groups
  6. Inner mapping groups
  7. Nuclei, commutant, center, and associator subloop
  8. Normal subloops
  9. Factor loops
  10. Nilpotency and central series
  11. Solvability
  12. Isomorphisms and automorphisms
  13. How are isomorphisms computed

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.

5.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. 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 obvious why we have not insisted on Cayley tables of quasigroups to cover the entire interval 1, ..., 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 ] ).

    5.2 Comparing quasigroups with common parent

    noindentAssume that A, B are two quasigroups with common parent Q. Let GA, GB 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 GA < GB lexicographically.

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

    5.3 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 closed under multiplication in Q.

  • IsSubquasigroup( Q, S ) O
  • IsSubloop( Q, S ) O

    5.4 Translations and sections

    When x is an element of a quasigroup Q, the left translation Lx 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, ..., 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.

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

    5.5 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 of L with respect to S is the group 〈L(x)|xS〉, where L(x) is the left translation by x in Q restricted to S. The relative right multiplication group and relative multiplication group are defined analogously.

  • RelativeLeftMultiplicationGroup( L, S ) O
  • RelativeRightMultiplicationGroup( L, S ) O
  • RelativeMultiplicationGroup( L, S ) O

    5.6 Inner mapping groups

    The inner mapping group of a loop L is the stabilizer of the unit element in Mlt(L). The elements of this stabilizer are called inner maps of L.

    The left inner mapping group of a loop L is the stabilizer of the unit element in LMlt(L). The right inner mapping group is defined dually.

  • InnerMappingGroup( L ) A
  • LeftInnerMappingGroup( L ) A
  • RightInnerMappingGroup( L ) A

    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
    

    5.7 Nuclei, commutant, center, and associator subloop

    Let Q be a quasigroup. The left nucleus Nλ(Q) of Q is the set {xQ| x(yz)=(xy)z for every y, zQ}. One defines similarly the middle nucleus Nμ(Q) and the right nucleus Nρ(Q). Then the nucleus N(Q) of Q is the intersection of the three nuclei. These 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).

    The commutant C(Q) of Q is the set {xQ| xy=yx for every yQ}. It is also known under the name Moufang center . 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

    Finally, the associator subloop of a loop L is the subloop of L generated by all associators of L. (Note that some authors define the associator subloop as the smallest normal subloop A of L such that L/A is associative. The two definitions are not equivalent in general.)

  • AssociatorSubloop( L ) A

    5.8 Normal subloops

    A subloop S of a loop L is normalindexnormal 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 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 simpleindexsimple loop if all normal subloops of L are trivial. The corresponding test in LOOPS is:

  • IsSimple( L ) O

    5.9 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:

    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 )
    

    5.10 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 nilpotentindexstrongly nilpotent loop if its multiplication group is nilpotent. This property is obtained by:

  • IsStronglyNilpotent( L ) P

    Let L be a loop. Define iterated centers Zi(L) as follows: Z0(L)=Z(L), Zi+1(L) = πi−1( Zi(L) ), where πi is the canonical projection LL/Zi(L). The longest series Zi(L), Zi−1(L), ..., Z0(L) with Zi(L) > Zi−1(L) > … > Z0(L) is called the upper central series of L, and is returned via

  • UpperCentralSeries( L ) A

    The lower central series , defined in the usual way, is obtained by

  • LowerCentralSeries( L ) A

    5.11 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

    5.12 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, ..., |L|, where ip=j means that the ith element of L is mapped onto the jth element of M. This is true even if L or M are not their own parents.

    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.

    5.13 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 VoEJC or the file loop_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.

    [Up] [Previous] [Next] [Index]

    loops manual
    szeptember 2005