68 Tables of Marks

In the first form, G must be a finite group, and TableOfMarks constructs the table of marks of G. This computation requires the knowledge of the complete subgroup lattice of G (see LatticeSubgroups). If the lattice is not yet stored then it will be constructed. This may take a while if G is large. The result has the IsTableOfMarksWithGens value true (see Accessing Subgroups via Tables of Marks).

In the second form, string must be a string, and TableOfMarks gets the table of marks with name string from the GAP library (see The Library of Tables of Marks). If no table of marks with this name is contained in the library then fail is returned.

In the third form, matrix must be a matrix or a list of rows describing a lower triangular matrix where the part above the diagonal is omitted. For such an argument matrix, TableOfMarks returns a table of marks object (see Table of Marks Objects in GAP) for which matrix is the matrix of marks. Note that not every matrix (containing only nonnegative integers and having lower triangular shape) describes a table of marks of a group. Necessary conditions are checked with IsInternallyConsistent (see Other Operations for Tables of Marks), and fail is returned if matrix is proved not to describe a matrix of marks; but if TableOfMarks returns a table of marks object created from a matrix then it may still happen that this object does not describe the table of marks of a group.

gap> tom:= TableOfMarks( AlternatingGroup( 5 ) );
TableOfMarks( AlternatingGroup( [ 1 .. 5 ] ) )
gap> TableOfMarks( "J5" );
fail
gap> a5:= TableOfMarks( "A5" );
TableOfMarks( "A5" )
gap> mat:=
> [ [ 60, 0, 0, 0, 0, 0, 0, 0, 0 ], [ 30, 2, 0, 0, 0, 0, 0, 0, 0 ], 
>   [ 20, 0, 2, 0, 0, 0, 0, 0, 0 ], [ 15, 3, 0, 3, 0, 0, 0, 0, 0 ], 
>   [ 12, 0, 0, 0, 2, 0, 0, 0, 0 ], [ 10, 2, 1, 0, 0, 1, 0, 0, 0 ], 
>   [ 6, 2, 0, 0, 1, 0, 1, 0, 0 ], [ 5, 1, 2, 1, 0, 0, 0, 1, 0 ], 
>   [ 1, 1, 1, 1, 1, 1, 1, 1, 1 ] ];;
gap> TableOfMarks( mat );
TableOfMarks( <9 classes> )

The following TableOfMarks methods for a group are installed.

• If the group is known to be cyclic then TableOfMarks constructs the table of marks essentially without the group, instead the knowledge about the structure of cyclic groups is used.
• If the lattice of subgroups is already stored in the group then TableOfMarks computes the table of marks from the lattice (see TableOfMarksByLattice).
• If the group is known to be solvable then TableOfMarks takes the lattice of subgroups (see LatticeSubgroups) of the group --which means that the lattice is computed if it is not yet stored-- and then computes the table of marks from it. This method is also accessible via the global function TableOfMarksByLattice (see TableOfMarksByLattice).
• If the group doesn't know its lattice of subgroups or its conjugacy classes of subgroups then the table of marks and the conjugacy classes of subgroups are computed at the same time by the cyclic extension method. Only the table of marks is stored because the conjugacy classes of subgroups or the lattice of subgroups can be easily read off (see LatticeSubgroupsByTom).

Conversely, the lattice of subgroups of a group with known table of marks can be computed using the table of marks, via the function LatticeSubgroupsByTom. This is also installed as a method for LatticeSubgroups.

TableOfMarksByLattice computes the table of marks of the group G from the lattice of subgroups of G. This lattice is computed via LatticeSubgroups (see LatticeSubgroups) if it is not yet stored in G. The function TableOfMarksByLattice is installed as a method for TableOfMarks for solvable groups and groups with stored subgroup lattice, and is available as a global variable only in order to provide explicit access to this method.

LatticeSubgroupsByTom computes the lattice of subgroups of G from the table of marks of G, using RepresentativeTom (see RepresentativeTom).

68.4 Printing Tables of Marks

The default ViewObj (see ViewObj) method for tables of marks prints the string "TableOfMarks", followed by --if known-- the identifier (see Identifier!for tables of marks) or the group of the table of marks enclosed in brackets; if neither group nor identifier are known then just the number of conjugacy classes of subgroups is printed instead.

The default PrintObj (see PrintObj) method for tables of marks does the same as ViewObj, except that the group is is Print-ed instead of View-ed.

The default Display (see Display) method for a table of marks tom produces a formatted output of the marks in tom. Each line of output begins with the number of the corresponding class of subgroups. This number is repeated if the output spreads over several pages. The number of columns printed at one time depends on the actual line length, which can be accessed and changed by the function SizeScreen (see SizeScreen).

The optional second argument arec of Display can be used to change the default style for displaying a character as shown above. arec must be a record, its relevant components are the following.

classes

a list of class numbers to select only the rows and columns of the matrix that correspond to this list for printing,

form

one of the strings "subgroups", "supergroups"; in the former case, at position (i,j) of the matrix the number of conjugates of H_j contained in H_i is printed, and in the latter case, at position (i,j) the number of conjugates of H_i which contain H_j is printed.

gap> tom:= TableOfMarks( "A5" );;
gap> Display( tom );
1:  60
2:  30 2
3:  20 . 2
4:  15 3 . 3
5:  12 . . . 2
6:  10 2 1 . . 1
7:   6 2 . . 1 . 1
8:   5 1 2 1 . . . 1
9:   1 1 1 1 1 1 1 1 1

gap> Display( tom, rec( classes:= [ 1, 2, 3, 4, 8 ] ) );
1:  60
2:  30 2
3:  20 . 2
4:  15 3 . 3
8:   5 1 2 1 1

gap> Display( tom, rec( form:= "subgroups" ) );
1:  1
2:  1  1
3:  1  .  1
4:  1  3  . 1
5:  1  .  . . 1
6:  1  3  1 . .  1
7:  1  5  . . 1  . 1
8:  1  3  4 1 .  . . 1
9:  1 15 10 5 6 10 6 5 1

gap> Display( tom, rec( form:= "supergroups" ) );
1:   1
2:  15 1
3:  10 . 1
4:   5 1 . 1
5:   6 . . . 1
6:  10 2 1 . . 1
7:   6 2 . . 1 . 1
8:   5 1 2 1 . . . 1
9:   1 1 1 1 1 1 1 1 1

68.5 Sorting Tables of Marks

SortedTom returns a table of marks where the rows and columns of the table of marks tom are reordered according to the permutation perm.

Note that in each table of marks in GAP, the matrix of marks is assumed to have lower triangular shape (see Table of Marks Objects in GAP). If the permutation perm does not have this property then the functions for tables of marks might return wrong results when applied to the output of SortedTom.

The returned table of marks has only those attribute values stored that are known for tom and listed in TableOfMarksComponents (see TableOfMarksComponents).

gap> tom:= TableOfMarksCyclic( 6 );;  Display( tom );
1:  6
2:  3 3
3:  2 . 2
4:  1 1 1 1

gap> sorted:= SortedTom( tom, (2,3) );;  Display( sorted );
1:  6
2:  2 2
3:  3 . 3
4:  1 1 1 1

gap> wrong:= SortedTom( tom, (1,2) );;  Display( wrong );
1:  3
2:  . 6
3:  . 2 2
4:  1 1 1 1

For the table of marks tom of the group G stored as UnderlyingGroup value of tom (see UnderlyingGroup!for tables of marks), PermutationTom is a permutation p such that the i-th conjugacy class of subgroups of G belongs to the i^p-th column and row of marks in tom.

This attribute value is bound only if tom was obtained from another table of marks by permuting with SortedTom (see SortedTom), and there is no default method to compute its value.

The attribute is necessary because the original and the sorted table of marks have the same identifier and the same group, and information computed from the group may depend on the ordering of marks, for example the fusion from the ordinary character table of G into tom.

gap> MarksTom( tom )[2];
[ 3, 3 ]
gap> MarksTom( sorted )[2];
[ 2, 2 ]
gap> HasPermutationTom( sorted );
true
gap> PermutationTom( sorted );
(2,3)

68.6 Technical Details about Tables of Marks

is the info class for computations concerning tables of marks.

Each table of marks belongs to this category.

Each table of marks belongs to this family.

The list TableOfMarksComponents is used when a table of marks object is created from a record via ConvertToTableOfMarks (see ConvertToTableOfMarks). TableOfMarksComponents contains at position 2i-1 a name of an attribute and at position 2i the corresponding attribute getter function.

ConvertToTableOfMarks converts a record with components from TableOfMarksComponents into a table of marks object with the corresponding attributes.

gap> record:= rec( MarksTom:= [ [ 4 ], [ 2, 2 ], [ 1, 1, 1 ] ],
>  SubsTom:= [ [ 1 ], [ 1, 2 ], [ 1, 2, 3 ] ] );;
gap> ConvertToTableOfMarks( record );;
gap> record;
TableOfMarks( <3 classes> )

68.7 Attributes of Tables of Marks

The matrix of marks (see More about Tables of Marks) of the table of marks tom is stored in a compressed form where zeros are omitted, using the attributes MarksTom and SubsTom. If M is the square matrix of marks of tom (see MatTom) then the SubsTom value of tom is a list that contains at position i the list of all positions of nonzero entries of the i-th row of M, and the MarksTom value of tom is a list that contains at position i the list of the corresponding marks.

MarksTom and SubsTom are defining attributes of tables of marks (see Table of Marks Objects in GAP). There is no default method for computing the SubsTom value, and the default MarksTom method needs the values of NrSubsTom and OrdersTom (see NrSubsTom, OrdersTom).

gap> a5:= TableOfMarks( "A5" );
TableOfMarks( "A5" )
gap> MarksTom( a5 );
[ [ 60 ], [ 30, 2 ], [ 20, 2 ], [ 15, 3, 3 ], [ 12, 2 ], [ 10, 2, 1, 1 ], 
  [ 6, 2, 1, 1 ], [ 5, 1, 2, 1, 1 ], [ 1, 1, 1, 1, 1, 1, 1, 1, 1 ] ]
gap> SubsTom( a5 );
[ [ 1 ], [ 1, 2 ], [ 1, 3 ], [ 1, 2, 4 ], [ 1, 5 ], [ 1, 2, 3, 6 ], 
  [ 1, 2, 5, 7 ], [ 1, 2, 3, 4, 8 ], [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ] ]

Instead of storing the marks (see MarksTom) of the table of marks tom one can use a matrix which contains at position (i,j) the number of subgroups of conjugacy class j that are contained in one member of the conjugacy class i. These values are stored in the NrSubsTom value in the same way as the marks in the MarksTom value.

OrdersTom returns a list that contains at position i the order of a representative of the i-th conjugacy class of subgroups of tom.

One can compute the NrSubsTom and OrdersTom values from the MarksTom value of tom and vice versa.

gap> NrSubsTom( a5 );
[ [ 1 ], [ 1, 1 ], [ 1, 1 ], [ 1, 3, 1 ], [ 1, 1 ], [ 1, 3, 1, 1 ], 
  [ 1, 5, 1, 1 ], [ 1, 3, 4, 1, 1 ], [ 1, 15, 10, 5, 6, 10, 6, 5, 1 ] ]
gap> OrdersTom( a5 );
[ 1, 2, 3, 4, 5, 6, 10, 12, 60 ]

For a table of marks tom, LengthsTom returns a list of the lengths of the conjugacy classes of subgroups.

gap> LengthsTom( a5 );
[ 1, 15, 10, 5, 6, 10, 6, 5, 1 ]

ClassTypesTom distinguishes isomorphism types of the classes of subgroups of the table of marks tom as far as this is possible from the SubsTom and MarksTom values of tom.

Two subgroups are clearly not isomorphic if they have different orders. Moreover, isomorphic subgroups must contain the same number of subgroups of each type.

Each type is represented by a positive integer. ClassTypesTom returns the list which contains for each class of subgroups its corresponding type.

gap> a6:= TableOfMarks( "A6" );;
gap> ClassTypesTom( a6 );
[ 1, 2, 3, 3, 4, 5, 6, 6, 7, 7, 8, 9, 10, 11, 11, 12, 13, 13, 14, 15, 15, 16 ]

ClassNamesTom constructs generic names for the conjugacy classes of subgroups of the table of marks tom. In general, the generic name of a class of non--cyclic subgroups consists of three parts and has the form "(o)_tl", where o indicates the order of the subgroup, t is a number that distinguishes different types of subgroups of the same order, and l is a letter that distinguishes classes of subgroups of the same type and order. The type of a subgroup is determined by the numbers of its subgroups of other types (see ClassTypesTom). This is slightly weaker than isomorphism.

The letter is omitted if there is only one class of subgroups of that order and type, and the type is omitted if there is only one class of that order. Moreover, the braces around the type are omitted if the type number has only one digit.

For classes of cyclic subgroups, the parentheses round the order and the type are omitted. Hence the most general form of their generic names is "o,l". Again, the letter is omitted if there is only one class of cyclic subgroups of that order.

gap> ClassNamesTom( a6 );
[ "1", "2", "3a", "3b", "5", "4", "(4)_2a", "(4)_2b", "(6)a", "(6)b", "(8)", 
  "(9)", "(10)", "(12)a", "(12)b", "(18)", "(24)a", "(24)b", "(36)", "(60)a", 
  "(60)b", "(360)" ]

For a table of marks tom, FusionsTom is a list of fusions into other tables of marks. Each fusion is a list of length two, the first entry being the Identifier (see Identifier!for tables of marks) value of the image table, the second entry being the list of images of the class positions of tom in the image table.

This attribute is mainly used for tables of marks in the GAP library (see The Library of Tables of Marks).

gap> fus:= FusionsTom( a6 );;
gap> fus[1];
[ "L3(4)", [ 1, 2, 3, 3, 14, 5, 9, 7, 15, 15, 24, 26, 27, 32, 33, 50, 57, 55, 
      63, 73, 77, 90 ] ]

UnderlyingGroup is used to access an underlying group that is stored on the table of marks tom. There is no default method to compute an underlying group if it is not stored.

gap> UnderlyingGroup( a6 );
Group([ (1,2)(3,4), (1,2,4,5)(3,6) ])

IdempotentsTom encodes the idempotents of the integral Burnside ring described by the table of marks tom. The return value is a list l of positive integers such that each row vector describing a primitive idempotent has value 1 at all positions with the same entry in l, and 0 at all other positions.

According to A. Dress Dre69 (see also Pfe97), these idempotents correspond to the classes of perfect subgroups, and each such idempotent is the characteristic function of all those subgroups that arise by cyclic extension from the corresponding perfect subgroup (see CyclicExtensionsTom).

IdempotentsTomInfo returns a record with components fixpointvectors and primidems, both bound to lists. The i-th entry of the fixpointvectors list is the 0-1-vector describing the i-th primitive idempotent, and the i-th entry of primidems is the decomposition of this idempotent in the rows of tom.

gap> IdempotentsTom( a5 );
[ 1, 1, 1, 1, 1, 1, 1, 1, 9 ]
gap> IdempotentsTomInfo( a5 );
rec( 
  primidems := [ [ 1, -2, -1, 0, 0, 1, 1, 1 ], [ -1, 2, 1, 0, 0, -1, -1, -1, 
          1 ] ], 
  fixpointvectors := [ [ 1, 1, 1, 1, 1, 1, 1, 1, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 
          0, 1 ] ] )

The identifier of a table of marks tom is a string. It is used for printing the table of marks (see Printing Tables of Marks) and in fusions between tables of marks (see FusionsTom).

If tom is a table of marks from the GAP library of tables of marks (see The Library of Tables of Marks) then it has an identifier, and if tom was constructed from a group with Name value (see Name) then this name is chosen as Identifier value. There is no default method to compute an identifier in all other cases.

gap> Identifier( a5 );
"A5"

MatTom returns the square matrix of marks (see More about Tables of Marks) of the table of marks tom which is stored in a compressed form using the attributes MarksTom and SubsTom (see MarksTom). This may need substantially more space than the values of MarksTom and SubsTom.

gap> MatTom( a5 );
[ [ 60, 0, 0, 0, 0, 0, 0, 0, 0 ], [ 30, 2, 0, 0, 0, 0, 0, 0, 0 ], 
  [ 20, 0, 2, 0, 0, 0, 0, 0, 0 ], [ 15, 3, 0, 3, 0, 0, 0, 0, 0 ], 
  [ 12, 0, 0, 0, 2, 0, 0, 0, 0 ], [ 10, 2, 1, 0, 0, 1, 0, 0, 0 ], 
  [ 6, 2, 0, 0, 1, 0, 1, 0, 0 ], [ 5, 1, 2, 1, 0, 0, 0, 1, 0 ], 
  [ 1, 1, 1, 1, 1, 1, 1, 1, 1 ] ]

MoebiusTom computes the Möbius values both of the subgroup lattice of the group G with table of marks tom and of the poset of conjugacy classes of subgroups of G. It returns a record where the component mu contains the Möbius values of the subgroup lattice, and the component nu contains the Möbius values of the poset.

Moreover, according to an observation of Isaacs et al. (see HIO89, Pah93), the values on the subgroup lattice often can be derived from those of the poset of conjugacy classes. These ``expected values'' are returned in the component ex, and the list of numbers of those subgroups where the expected value does not coincide with the actual value are returned in the component hyp. For the computation of these values, the position of the derived subgroup of G is needed (see DerivedSubgroupTom). If it is not uniquely determined then the result does not have the components ex and hyp.

gap> MoebiusTom( a5 );
rec( mu := [ -60, 4, 2,,, -1, -1, -1, 1 ], nu := [ -1, 2, 1,,, -1, -1, -1, 1 ]
    , ex := [ -60, 4, 2,,, -1, -1, -1, 1 ], hyp := [  ] )
gap> tom:= TableOfMarks( "M12" );;
gap> moebius:= MoebiusTom( tom );;
gap> moebius.hyp;
[ 1, 2, 4, 16, 39, 45, 105 ]
gap> moebius.mu[1];  moebius.ex[1];
95040
190080

WeightsTom extracts the weights from the table of marks tom, i.e., the diagonal entries of the matrix of marks (see MarksTom), indicating the index of a subgroup in its normalizer.

gap> wt:= WeightsTom( a5 );
[ 60, 2, 2, 3, 2, 1, 1, 1, 1 ]

gap> marks:= MarksTom( a5 );;
gap> List( [ 1 .. 9 ], x -> marks[x] / wt[x] );
[ [ 1 ], [ 15, 1 ], [ 10, 1 ], [ 5, 1, 1 ], [ 6, 1 ], [ 10, 2, 1, 1 ], 
  [ 6, 2, 1, 1 ], [ 5, 1, 2, 1, 1 ], [ 1, 1, 1, 1, 1, 1, 1, 1, 1 ] ]

68.8 Properties of Tables of Marks

For a table of marks tom of a group G, the following properties have the same meaning as the corresponding properties for G. Additionally, if a positive integer sub is given as the second argument then the value of the corresponding property for the sub-th class of subgroups of tom is returned.

gap> tom:= TableOfMarks( "A5" );;
gap> IsAbelianTom( tom );  IsPerfectTom( tom );
false
true
gap> IsAbelianTom( tom, 3 );  IsNilpotentTom( tom, 7 );
true
false
gap> IsPerfectTom( tom, 7 );  IsSolvableTom( tom, 7 );
false
true
gap> for i in [ 1 .. 6 ] do
> Print( i, ": ", IsCyclicTom(a5, i), "  " );
> od;  Print( "\n" );
1: true  2: true  3: true  4: false  5: true  6: false  

68.9 Other Operations for Tables of Marks

For a table of marks tom, IsInternallyConsistent decomposes all tensor products of rows of tom. It returns true if all decomposition numbers are nonnegative integers, and false otherwise. This provides a strong consistency check for a table of marks.

For a table of marks tom and a positive integer sub, DerivedSubgroupTom returns either a positive integer i or a list l of positive integers. In the former case, the result means that the derived subgroups of the subgroups in the sub-th class of tom lie in the i-th class. In the latter case, the class of the derived subgroups could not be uniquely determined, and the position of the class of derived subgroups is an entry of l.

Values computed with DerivedSubgroupTom are stored using the attribute DerivedSubgroupsTomPossible (see DerivedSubgroupsTomPossible).

DerivedSubgroupsTom is just the list of DerivedSubgroupTom values for all values of sub.

Let tom be a table of marks. The value of the attribute DerivedSubgroupsTomPossible is a list in which the value at position i --if bound-- is a positive integer or a list; the meaning of the entry is the same as in DerivedSubgroupTom (see DerivedSubgroupTom).

If the value of the attribute DerivedSubgroupsTomUnique is known for tom then it is a list of positive integers, the value at position i being the position of the class of derived subgroups of the i-th class of subgroups in tom. The derived subgroups are in general not uniquely determined by the table of marks if no UnderlyingGroup value is stored, so there is no default method for DerivedSubgroupsTomUnique. But in some cases the derived subgroups are explicitly set when the table of marks is constructed. The DerivedSubgroupsTomUnique value is automatically set when the last missing unique value is entered in the DerivedSubgroupsTomPossible list by DerivedSubgroupTom.

gap> a5:= TableOfMarks( "A5" );
TableOfMarks( "A5" )
gap> DerivedSubgroupsTomPossible( a5 );
[ ,, 1,,,,,, 9 ]
gap> DerivedSubgroupTom( a5, 2 );
1
gap> DerivedSubgroupsTomPossible( a5 );
[ , 1, 1,,,,,, 9 ]
gap> DerivedSubgroupsTom( a5 );
[ 1, 1, 1, 1, 1, 3, 5, 4, 9 ]

Let tom be the table of marks of a group G, say. NormalizerTom tries to find the conjugacy class of the normalizer N in G of a subgroup U in the sub-th class of tom. The return value is either the list of class numbers of those subgroups that have the right size and contain the subgroup and all subgroups that clearly contain it as a normal subgroup, or the class number of the normalizer if it is uniquely determined by these conditions. If tom knows the subgroup lattice of G (see IsTableOfMarksWithGens) then all normalizers are uniquely determined. NormalizerTom should never return an empty list.

NormalizersTom returns the list of positions of the classes of normalizers of subgroups in tom. In addition to the criteria for a single class of subgroup used by NormalizerTom, the approximations of normalizers for several classes are used and thus NormalizersTom may return better approximations than NormalizerTom.

gap> NormalizerTom( a5, 4 );
8
gap> NormalizersTom( a5 );
[ 9, 4, 6, 8, 7, 6, 7, 8, 9 ]

ContainedTom returns the number of subgroups in class sub1 of the table of marks tom that are contained in one fixed member of the class sub2.

ContainingTom returns the number of subgroups in class sub2 of the table of marks tom that contain one fixed member of the class sub1.

gap> ContainedTom( a5, 3, 5 );  ContainedTom( a5, 3, 8 );
0
4
gap> ContainingTom( a5, 3, 5 );  ContainingTom( a5, 3, 8 );
0
2

According to A. Dress Dre69, two columns of the table of marks tom are equal modulo the prime p if and only if the corresponding subgroups are connected by a chain of normal extensions of order p.

In the second form, CyclicExtensionsTom returns the classes of this equivalence relation. In the third form, list must be a list of primes, and the return value is the list of classes of the relation obtained by considering chains of normal extensions of prime order where all primes are in list. In the first form, the result is the same as in the third form, with second argument the set of prime divisors of the size of the group of tom.

(This information is not used by NormalizerTom (see NormalizerTom) although it might give additional restrictions in the search of normalizers.)

gap> CyclicExtensionsTom( a5, 2 );
[ [ 1, 2, 4 ], [ 3, 6 ], [ 5, 7 ], [ 8 ], [ 9 ] ]

Let tom be the table of marks of the group G, say, and let fix be a vector of fixed point numbers w.r.t. an action of G, i.e., a vector which contains for each class of subgroups the number of fixed points under the given action. DecomposedFixedPointVector returns the decomposition of fix into rows of the table of marks. This decomposition corresponds to a decomposition of the action into transitive constituents. Trailing zeros in fix may be omitted.

gap> DecomposedFixedPointVector( a5, [ 16, 4, 1, 0, 1, 1, 1 ] );
[ 0, 0, 0, 0, 0, 1, 1 ]

gap> DecomposedFixedPointVector( a5, [ 0, 0, 0, 0, 1, 1 ] );
[ 2/5, -1, -1/2, 0, 1/2, 1 ]

In the first form EulerianFunctionByTom computes the Eulerian function (see EulerianFunction) of the underlying group G of the table of marks tom, that is, the number of n-tuples of elements in G that generate G. In the second form EulerianFunctionByTom computes the Eulerian function of each subgroup in the sub-th class of subgroups of tom.

For a group G whose table of marks is known, EulerianFunctionByTom is installed as a method for EulerianFunction (see EulerianFunction).

gap> EulerianFunctionByTom( a5, 2 );
2280
gap> EulerianFunctionByTom( a5, 3 );
200160
gap> EulerianFunctionByTom( a5, 2, 3 );
8

The intersections of the groups in the sub1-th conjugacy class of subgroups of the table of marks tom with the groups in the sub2-th conjugacy classes of subgroups of tom are determined up to conjugacy by the decomposition of the tensor product of their rows of marks. IntersectionsTom returns a list l that describes this decomposition. The i-th entry in l is the multiplicity of groups in the i-th conjugacy class as an intersection.

gap> IntersectionsTom( a5, 8, 8 );
[ 0, 0, 1, 0, 0, 0, 0, 1 ]

For a table of marks tom of the group G, say, and the normal subgroup N of G corresponding to the n-th class of subgroups of tom, FactorGroupTom returns the table of marks of the factor group G / N.

gap> s4:= TableOfMarks( SymmetricGroup( 4 ) );
TableOfMarks( SymmetricGroup( [ 1 .. 4 ] ) )
gap> LengthsTom( s4 );
[ 1, 3, 6, 4, 1, 3, 3, 4, 3, 1, 1 ]
gap> OrdersTom( s4 );
[ 1, 2, 2, 3, 4, 4, 4, 6, 8, 12, 24 ]
gap> s3:= FactorGroupTom( s4, 5 );
TableOfMarks( Group( [ f1, f2 ] ) )
gap> Display( s3 );
1:  6
2:  3 1
3:  2 . 2
4:  1 1 1 1

In the first form MaximalSubgroupsTom returns a list of length two, the first entry being the list of positions of the classes of maximal subgroups of the whole group of the table of marks tom, the second entry being the list of class lengths of these groups. In the second form the same information for the sub-th class of subgroups is returned.

For a table of marks tom, MinimalSupergroupsTom returns a list of length two, the first entry being the list of positions of the classes containing the minimal supergroups of the groups in the sub-th class of subgroups of tom, the second entry being the list of class lengths of these groups.

gap> MaximalSubgroupsTom( s4 );
[ [ 10, 9, 8 ], [ 1, 3, 4 ] ]
gap> MaximalSubgroupsTom( s4, 10 );
[ [ 5, 4 ], [ 1, 4 ] ]
gap> MinimalSupergroupsTom( s4, 5 );
[ [ 9, 10 ], [ 3, 1 ] ]

68.10 Standard Generators of Groups

An s-tuple of standard generators of a given group G is a vector (g₁, g₂, ¼, g_s) of elements g_i Î G satisfying certain conditions (depending on the isomorphism type of G) such that

1. ág₁, g₂, ¼, g_s ñ = G and
2. the vector is unique up to automorphisms of G, i.e., for two vectors (g₁, g₂, ¼, g_s) and (h₁, h₂, ¼, h_s) of standard generators, the map g_i ® h_i extends to an automorphism of G.

When called with the group G, StandardGeneratorsInfo returns a list of records with at least one of the components script and description. Each such record defines standard generators of groups isomorphic to G, the i-th record is referred to as the i-th set of standard generators for such groups. The value of script is a dense list of lists, each encoding a command that has one of the following forms.

A definition [ i, n, k ] or [ i, n ]

means to search for an element of order n, and to take its k-th power as candidate for the i-th standard generator (the default for k is 1),

a relation [ i₁, k₁, i₂, k₂, ¼, i_m, k_m, n ] with m > 1

means a check whether the element g_i1^k₁ g_i2^k₂ ¼g_im^k_m has order n; if g_j occurs then of course the j-th generator must have been defined before,

a relation [ [ i₁, i₂, ¼, i_m ], slp , n ]

means a check whether the result of the straight line program slp (see Straight Line Programs) applied to the candidates g_i1, g_i2, ¼, g_im has order n, where the candidates g_j for the j-th standard generators must have been defined before,

a condition [ [ i₁, k₁, i₂, k₂, ¼, i_m, k_m ], f, v ]

means a check whether the GAP function in the global list StandardGeneratorsFunctions (see StandardGeneratorsFunctions) that is followed by the list f of strings returns the value v when it is called with G and g_i1^k₁ g_i2^k₂ ¼g_im^k_m.

generators

a string of names of the standard generators,

description

a string describing the script information in human readable form, in terms of the generators value,

classnames

a list of strings, the i-th entry being the name of the conjugacy class containing the i-th standard generator, according to the ATLAS character table of the group (see ClassNames), and

ATLAS

a boolean; true means that the standard generators coincide with those defined in Rob Wilson's ATLAS of Group Representations (see AGR), and false means that this property is not guaranteed.

There is no default method for an arbitrary isomorphism type, since in general the definition of standard generators is not obvious.

The function StandardGeneratorsOfGroup (see StandardGeneratorsOfGroup) can be used to find standard generators of a given group isomorphic to G.

The generators and description values, if not known, can be computed by HumanReadableDefinition (see HumanReadableDefinition).

gap> StandardGeneratorsInfo( TableOfMarks( "L3(3)" ) );
[ rec( generators := "a, b", 
      description := "|a|=2, |b|=3, |C(b)|=9, |ab|=13, |ababb|=4", 
      script := [ [ 1, 2 ], [ 2, 3 ], [ [ 2, 1 ], [ "|C(",, ")|" ], 9 ], 
          [ 1, 1, 2, 1, 13 ], [ 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 4 ] ], 
      ATLAS := true ) ]

Let info be a record that is valid as value of StandardGeneratorsInfo (see StandardGeneratorsInfo!for groups). HumanReadableDefinition returns a string that describes the definition of standard generators given by the script component of info in human readable form. The names of the generators are taken from the generators component (default names "a", "b" etc. are computed if necessary), and the result is stored in the description component.

ScriptFromString does the converse of HumanReadableDefinition, i.e., it takes a string string as returned by HumanReadableDefinition, and returns a corresponding script list.

If ``condition'' lines occur in the script (see StandardGeneratorsInfo!for groups) then the functions that occur must be contained in StandardGeneratorsFunctions (see StandardGeneratorsFunctions).

gap> scr:= ScriptFromString( "|a|=2, |b|=3, |C(b)|=9, |ab|=13, |ababb|=4" );
[ [ 1, 2 ], [ 2, 3 ], [ [ 2, 1 ], [ "|C(",, ")|" ], 9 ], [ 1, 1, 2, 1, 13 ], 
  [ 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 4 ] ]
gap> info:= rec( script:= scr );
rec( script := [ [ 1, 2 ], [ 2, 3 ], [ [ 2, 1 ], [ "|C(",, ")|" ], 9 ], 
      [ 1, 1, 2, 1, 13 ], [ 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 4 ] ] )
gap> HumanReadableDefinition( info );
"|a|=2, |b|=3, |C(b)|=9, |ab|=13, |ababb|=4"
gap> info;
rec( script := [ [ 1, 2 ], [ 2, 3 ], [ [ 2, 1 ], [ "|C(",, ")|" ], 9 ], 
      [ 1, 1, 2, 1, 13 ], [ 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 4 ] ], 
  generators := "a, b", 
  description := "|a|=2, |b|=3, |C(b)|=9, |ab|=13, |ababb|=4" )

StandardGeneratorsFunctions is a list of even length. At position 2i-1, a function of two arguments is stored, which are expected to be a group and a group element. At position 2i a list of strings is stored such that first inserting a generator name in all holes and then forming the concatenation yields a string that describes the function at the previous position; this string must contain the generator enclosed in round brackets ( and ).

This list is used by the functions StandardGeneratorsInfo (see StandardGeneratorsInfo!for groups), HumanReadableDefinition, and ScriptFromString (see HumanReadableDefinition). Note that the lists at even positions must be pairwise different.

gap> StandardGeneratorsFunctions{ [ 1, 2 ] };
[ function( G, g ) ... end, [ "|C(",, ")|" ] ]

Let info be a record that is valid as value of StandardGeneratorsInfo (see StandardGeneratorsInfo!for groups), G a group, and gens a list of generators for G. In this case, IsStandardGeneratorsOfGroup returns true if gens satisfies the conditions of the script component of info, and false otherwise.

Note that the result true means that gens is a list of standard generators for G only if G has the isomorphism type for which info describes standard generators.

Let info be a record that is valid as value of StandardGeneratorsInfo (see StandardGeneratorsInfo!for groups), and G a group of the isomorphism type for which info describes standard generators. In this case, StandardGeneratorsOfGroup returns a list of standard generators (see Section Standard Generators of Groups) of G.

The optional argument randfunc must be a function that returns an element of G when called with G; the default is PseudoRandom.

In each call to StandardGeneratorsOfGroup, the script component of info is scanned line by line. randfunc is used to find an element of the prescribed order whenever a definition line is met, and for the relation and condition lines in the script list, the current generator candidates are checked; if a condition is not fulfilled, all candidates are thrown away, and the procedure starts again with the first line. When the conditions are fulfilled after processing the last line of the script list, the standard generators are returned.

Note that if G has the wrong isomorphism type then StandardGeneratorsOfGroup returns a list of elements in G that satisfy the conditions of the script component of info if such elements exist, and does not terminate otherwise. In the former case, obviously the returned elements need not be standard generators of G.

gap> a5:= AlternatingGroup( 5 );
Alt( [ 1 .. 5 ] )
gap> info:= StandardGeneratorsInfo( TableOfMarks( "A5" ) )[1];
rec( generators := "a, b", description := "|a|=2, |b|=3, |ab|=5", 
  script := [ [ 1, 2 ], [ 2, 3 ], [ 1, 1, 2, 1, 5 ] ], ATLAS := true )
gap> IsStandardGeneratorsOfGroup( info, a5, [ (1,3)(2,4), (3,4,5) ] );
true
gap> IsStandardGeneratorsOfGroup( info, a5, [ (1,3)(2,4), (1,2,3) ] );
false
gap> s5:= SymmetricGroup( 5 );;
gap> RepresentativeAction( s5, [ (1,3)(2,4), (3,4,5) ], 
>        StandardGeneratorsOfGroup( info, a5 ), OnPairs ) <> fail;
true

68.11 Accessing Subgroups via Tables of Marks

Let tom be the table of marks of the group G, and assume that tom has access to G via the UnderlyingGroup value (see UnderlyingGroup!for tables of marks). Then it makes sense to use tom and its ordering of conjugacy classes of subgroups of G for storing information for constructing representatives of these classes. The group G is in general not sufficient for this, tom needs more information; this is available if and only if the IsTableOfMarksWithGens value of tom is true (see IsTableOfMarksWithGens). In this case, RepresentativeTom (see RepresentativeTom) can be used to get a subgroup of the i-th class, for all i.

GAP provides two different possibilities to store generators of the representatives of classes of subgroups. The first is implemented by the attribute GeneratorsSubgroupsTom (see GeneratorsSubgroupsTom), which uses explicit generators. The second, more general, possibility is implemented by the attributes StraightLineProgramsTom (see StraightLineProgramsTom) and StandardGeneratorsInfo (see StandardGeneratorsInfo!for tables of marks). The StraightLineProgramsTom value encodes the generators as straight line programs (see Straight Line Programs) that evaluate to the generators in question when applied to standard generators of G. This means that on the one hand, standard generators of G must be known in order to use StraightLineProgramsTom. On the other hand, the straight line programs allow one to compute easily generators not only of a subgroup U of G but also generators of the image of U in any representation of G, provided that one knows standard generators of the image of G under this representation (see RepresentativeTomByGenerators for details and an example).

Let tom be a table of marks with IsTableOfMarksWithGens value true. Then GeneratorsSubgroupsTom returns a list of length two, the first entry being a list l of elements of the group stored as UnderlyingGroup value of tom, the second entry being a list that contains at position i a list of positions in l of generators of a representative of a subgroup in class i.

The GeneratorsSubgroupsTom value is known for all tables of marks that have been computed with TableOfMarks (see TableOfMarks) from a group, and there is a method to compute the value for a table of marks that admits RepresentativeTom (see RepresentativeTom).

For a table of marks tom with IsTableOfMarksWithGens value true, StraightLineProgramsTom returns a list that contains at position i either a list of straight line programs or a straight line program (see Straight Line Programs), encoding the generators of a representative of the i-th conjugacy class of subgroups of UnderlyingGroup( tom ); in the former case, each straight line program returns a generator, in the latter case, the program returns the list of generators.

There is no default method to compute the StraightLineProgramsTom value of a table of marks if they are not yet stored. The value is known for all tables of marks that belong to the GAP library of tables of marks (see The Library of Tables of Marks).

This filter shall express the union of the filters IsTableOfMarks and HasStraightLineProgramsTom and IsTableOfMarks and HasGeneratorsSubgroupsTom. If a table of marks tom has this filter set then tom can be asked to compute information that is in general not uniquely determined by a table of marks, for example the positions of derived subgroups or normalizers of subgroups (see DerivedSubgroupTom, NormalizerTom).

gap> a5:= TableOfMarks( "A5" );;  IsTableOfMarksWithGens( a5 );
true
gap> HasGeneratorsSubgroupsTom( a5 );  HasStraightLineProgramsTom( a5 );
false
true
gap> alt5:= TableOfMarks( AlternatingGroup( 5 ) );;
gap> IsTableOfMarksWithGens( alt5 );
true
gap> HasGeneratorsSubgroupsTom( alt5 );  HasStraightLineProgramsTom( alt5 );
true
false
gap> progs:= StraightLineProgramsTom( a5 );;
gap> OrdersTom( a5 );
[ 1, 2, 3, 4, 5, 6, 10, 12, 60 ]
gap> IsCyclicTom( a5, 4 );
false
gap> Length( progs[4] );
2
gap> progs[4][1];
<straight line program>
gap> Display( progs[4][1] );  # first generator of an el. ab group of order 4
# input:
r:= [ g1, g2 ];
# program:
r[3]:= r[2]*r[1];
r[4]:= r[3]*r[2]^-1*r[1]*r[3]*r[2]^-1*r[1]*r[2];
# return value:
r[4]
gap> x:= [ [ Z(2)^0, 0*Z(2) ], [ Z(2^2), Z(2)^0 ] ];;
gap> y:= [ [ Z(2^2), Z(2)^0 ], [ 0*Z(2), Z(2^2)^2 ] ];;
gap> res1:= ResultOfStraightLineProgram( progs[4][1], [ x, y ] );
[ [ Z(2)^0, 0*Z(2) ], [ Z(2^2)^2, Z(2)^0 ] ]
gap> res2:= ResultOfStraightLineProgram( progs[4][2], [ x, y ] );
[ [ Z(2)^0, 0*Z(2) ], [ Z(2^2), Z(2)^0 ] ]
gap> w:= y*x;;
gap> res1 = w*y^-1*x*w*y^-1*x*y;
true
gap> subgrp:= Group( res1, res2 );;  Size( subgrp );  IsCyclic( subgrp );
4
false

Let tom be a table of marks with IsTableOfMarksWithGens value true (see IsTableOfMarksWithGens), and sub a positive integer. RepresentativeTom returns a representative of the sub-th conjugacy class of subgroups of tom.

RepresentativeTomByGenerators and RepresentativeTomByGeneratorsNC return a representative of the sub-th conjugacy class of subgroups of tom, as a subgroup of the group generated by gens. This means that the standard generators of tom are replaced by gens.

RepresentativeTomByGenerators checks whether mapping the standard generators of tom to gens extends to a group isomorphism, and returns fail if not. RepresentativeTomByGeneratorsNC omits all checks. So RepresentativeTomByGenerators is thought mainly for debugging purposes; note that when several representatives are constructed, it is cheaper to construct (and check) the isomorphism once, and to map the groups returned by RepresentativeTom under this isomorphism. The idea behind RepresentativeTomByGeneratorsNC, however, is to avoid the overhead of using isomorphisms when gens are known to be standard generators.

gap> RepresentativeTom( a5, 4 );
Group([ (2,3)(4,5), (2,4)(3,5) ])

For a table of marks tom, a stored value of StandardGeneratorsInfo equals the value of this attribute for the underlying group (see UnderlyingGroup!for tables of marks) of tom, cf. Section Standard Generators of Groups.

In this case, the GeneratorsOfGroup value of the underlying group G of tom is assumed to be in fact a list of standard generators for G; So one should be careful when setting the StandardGeneratorsInfo value by hand.

There is no default method to compute the StandardGeneratorsInfo value of a table of marks if it is not yet stored.

gap> std:= StandardGeneratorsInfo( a5 );
[ rec( generators := "a, b", description := "|a|=2, |b|=3, |ab|=5", 
      script := [ [ 1, 2 ], [ 2, 3 ], [ 1, 1, 2, 1, 5 ] ], ATLAS := true ) ]
gap> # Now find standard generators of an isomorphic group.
gap> g:= SL(2,4);;
gap> repeat
>   x:= PseudoRandom( g );
> until Order( x ) = 2;
gap> repeat
>   y:= PseudoRandom( g );
> until Order( y ) = 3 and Order( x*y ) = 5;
gap> # Compute a representative w.r.t. these generators.
gap> RepresentativeTomByGenerators( a5, 4, [ x, y ] );
Group([ [ [ Z(2^2), Z(2^2)^2 ], [ Z(2^2)^2, Z(2^2) ] ], 
  [ [ 0*Z(2), Z(2)^0 ], [ Z(2)^0, 0*Z(2) ] ] ])
gap> # Show that the new generators are really good.
gap> grp:= UnderlyingGroup( a5 );;
gap> iso:= GroupGeneralMappingByImages( grp, g,
>              GeneratorsOfGroup( grp ), [ x, y ] );;
gap> IsGroupHomomorphism( iso );
true
gap> IsBijective( iso );
true

68.12 The Interface between Tables of Marks and Character Tables

Let tbl be the ordinary character table of the group G, and tom the table of marks of G. FusionCharTableTom determines the fusion of the classes of elements from tbl to the classes of cyclic subgroups on tom, that is, a list that contains at position i the position of the class of cyclic subgroups in tom that are generated by elements in the i-th conjugacy class of elements in tbl.

Three cases are handled differently.

1. The fusion is explicitly stored on tbl. Then nothing has to be done. This happens only if both tbl and tom are tables from the GAP library (see The Library of Tables of Marks and the manual of the GAP Character Table Library).
2. The UnderlyingGroup values of tbl and tom are known and equal. Then the group is used to compute the fusion.
3. There is neither fusion nor group information available. In this case only necessary conditions can be checked, and if they are not sufficient to detemine the fusion uniquely then fail is returned by FusionCharTableTom.

PossibleFusionsCharTableTom computes the list of possible fusions from tbl to tom, according to the criteria that have been checked. So if FusionCharTableTom returns a unique fusion then the list returned by PossibleFusionsCharTableTom for the same arguments contains exactly this fusion, and if FusionCharTableTom returns fail then the length of this list is different from 1. The optional argument quick, a boolean, indicates whether a unique fusion shall be returned as soon as it has been determined, without further checks. The default value of quick is false.

gap> a5c:= CharacterTable( "A5" );;
gap> fus:= FusionCharTableTom( a5c, a5 );
[ 1, 2, 3, 5, 5 ]

PermCharsTom returns the list of transitive permutation characters from the table of marks tom. In the first form, fus must be the fusion map from the ordinary character table of the group of tom to tom (see FusionCharTableTom). In the second form, tbl must be the character table of the group of which tom is the table of marks. If the fusion map is not uniquely determined (see FusionCharTableTom) then fail is returned.

If the fusion map fus is given as first argument then each transitive permutation character is represented by its values list. If the character table tbl is given then the permutation characters are class function objects (see Chapter Class Functions).

gap> PermCharsTom( a5c, a5 );
[ Character( CharacterTable( "A5" ), [ 60, 0, 0, 0, 0 ] ), 
  Character( CharacterTable( "A5" ), [ 30, 2, 0, 0, 0 ] ), 
  Character( CharacterTable( "A5" ), [ 20, 0, 2, 0, 0 ] ), 
  Character( CharacterTable( "A5" ), [ 15, 3, 0, 0, 0 ] ), 
  Character( CharacterTable( "A5" ), [ 12, 0, 0, 2, 2 ] ), 
  Character( CharacterTable( "A5" ), [ 10, 2, 1, 0, 0 ] ), 
  Character( CharacterTable( "A5" ), [ 6, 2, 0, 1, 1 ] ), 
  Character( CharacterTable( "A5" ), [ 5, 1, 2, 0, 0 ] ), 
  Character( CharacterTable( "A5" ), [ 1, 1, 1, 1, 1 ] ) ]
gap> PermCharsTom( fus, a5 )[1];
[ 60, 0, 0, 0, 0 ]

68.13 Generic Construction of Tables of Marks

The following three operations construct a table of marks only from the data given, i.e., without underlying group.

TableOfMarksCyclic returns the table of marks of the cyclic group of order n.

A cyclic group of order n has as its subgroups for each divisor d of n a cyclic subgroup of order d.

TableOfMarksDihedral returns the table of marks of the dihedral group of order m.

For each divisor d of m, a dihedral group of order m = 2n contains subgroups of order d according to the following rule. If d is odd and divides n then there is only one cyclic subgroup of order d. If d is even and divides n then there are a cyclic subgroup of order d and two classes of dihedral subgroups of order d (which are cyclic, too, in the case d = 2, see the example below). Otherwise (i.e., if d does not divide n) there is just one class of dihedral subgroups of order d.

TableOfMarksFrobenius computes the table of marks of a Frobenius group of order p q, where p is a prime and q divides p-1.

gap> Display( TableOfMarksCyclic( 6 ) );
1:  6
2:  3 3
3:  2 . 2
4:  1 1 1 1

gap> Display( TableOfMarksDihedral( 12 ) );
 1:  12
 2:   6 6
 3:   6 . 2
 4:   6 . . 2
 5:   4 . . . 4
 6:   3 3 1 1 . 1
 7:   2 2 . . 2 . 2
 8:   2 . 2 . 2 . . 2
 9:   2 . . 2 2 . . . 2
10:   1 1 1 1 1 1 1 1 1 1

gap> Display( TableOfMarksFrobenius( 5, 4 ) );
1:  20
2:  10 2
3:   5 1 1
4:   4 . . 4
5:   2 2 . 2 2
6:   1 1 1 1 1 1

68.14 The Library of Tables of Marks

@The description of the contents of the library of tables of marks is currently missing.@

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

GAP 4 manual
May 2002