|
#############################################################################
##
## This file is part of GAP, a system for computational discrete algebra.
## This file's authors include Götz Pfeiffer, Thomas Merkwitz.
##
## Copyright of GAP belongs to its developers, whose names are too numerous
## to list here. Please refer to the COPYRIGHT file for details.
##
## SPDX-License-Identifier: GPL-2.0-or-later
##
## This file contains the declarations of the category and family of tables
## of marks, and their properties, attributes, operations and functions.
##
## 1. Tables of Marks
## 2. More about Tables of Marks
## 3. Table of Marks Objects in ⪆
## 4. Constructing Tables of Marks
## 5. Printing Tables of Marks
## 6. Sorting Tables of Marks
## 7. Technical Details about Tables of Marks
## 8. Attributes of Tables of Marks
## 9. Properties of Tables of Marks
## 10. Other Operations for Tables of Marks
## 11. Accessing Subgroups via Tables of Marks
## 12. The Interface between Tables of Marks and Character Tables
## 13. Generic Construction of Tables of Marks
##
#############################################################################
##
## 1. Tables of Marks
##
## <#GAPDoc Label="[1]{tom}">
## The concept of a <E>table of marks</E> was introduced by W. Burnside
## in his book <Q>Theory of Groups of Finite Order</Q>,
## see <Cite Key="Bur55"/>.
## Therefore a table of marks is sometimes called a <E>Burnside matrix</E>.
## <P/>
## The table of marks of a finite group <M>G</M> is a matrix whose rows and
## columns are labelled by the conjugacy classes of subgroups of <M>G</M>
## and where for two subgroups <M>A</M> and <M>B</M> the <M>(A, B)</M>-entry
## is the number of fixed points of <M>B</M> in the transitive action of
## <M>G</M> on the cosets of <M>A</M> in <M>G</M>.
## So the table of marks characterizes the set of all permutation
## representations of <M>G</M>.
## <P/>
## Moreover, the table of marks gives a compact description of the subgroup
## lattice of <M>G</M>, since from the numbers of fixed points the numbers
## of conjugates of a subgroup <M>B</M> contained in a subgroup <M>A</M>
## can be derived.
## <P/>
## A table of marks of a given group <M>G</M> can be constructed from the
## subgroup lattice of <M>G</M>
## (see <Ref Sect="Constructing Tables of Marks"/>).
## For several groups, the table of marks can be restored from the &GAP;
## library of tables of marks
## (see <Ref Sect="The Library of Tables of Marks"/>).
## <P/>
## Given the table of marks of <M>G</M>, one can display it
## (see <Ref Sect="Printing Tables of Marks"/>)
## and derive information about <M>G</M> and its Burnside ring from it
## (see <Ref Sect="Attributes of Tables of Marks"/>,
## <Ref Sect="Properties of Tables of Marks"/>,
## <Ref Sect="Other Operations for Tables of Marks"/>).
## Moreover, tables of marks in &GAP; provide an easy access to the classes
## of subgroups of their underlying groups
## (see <Ref Sect="Accessing Subgroups via Tables of Marks"/>).
## <#/GAPDoc>
##
#############################################################################
##
## 2. More about Tables of Marks
##
## <#GAPDoc Label="[2]{tom}">
## Let <M>G</M> be a finite group with <M>n</M> conjugacy classes of
## subgroups <M>C_1, C_2, \ldots, C_n</M> and representatives
## <M>H_i \in C_i</M>, <M>1 \leq i \leq n</M>.
## The <E>table of marks</E> of <M>G</M> is defined to be the
## <M>n \times n</M> matrix <M>M = (m_{ij})</M> where the
## <E>mark</E> <M>m_{ij}</M> is the number of fixed points of the subgroup
## <M>H_j</M> in the action of <M>G</M> on the right cosets of <M>H_i</M>
## in <M>G</M>.
## <P/>
## Since <M>H_j</M> can only have fixed points if it is contained in a point
## stabilizer the matrix <M>M</M> is lower triangular if the classes
## <M>C_i</M> are sorted according to the condition that if <M>H_i</M>
## is contained in a conjugate of <M>H_j</M> then <M>i \leq j</M>.
## <P/>
## Moreover, the diagonal entries <M>m_{ii}</M> are nonzero
## since <M>m_{ii}</M> equals the index of <M>H_i</M> in its normalizer
## in <M>G</M>. Hence <M>M</M> is invertible.
## Since any transitive action of <M>G</M> is equivalent to an action on the
## cosets of a subgroup of <M>G</M>, one sees that the table of marks
## completely characterizes the set of all permutation representations of
## <M>G</M>.
## <P/>
## The marks <M>m_{ij}</M> have further meanings.
## If <M>H_1</M> is the trivial subgroup of <M>G</M> then each mark
## <M>m_{i1}</M> in the first column of <M>M</M> is equal to the index of
## <M>H_i</M> in <M>G</M> since the trivial subgroup fixes all cosets of
## <M>H_i</M>.
## If <M>H_n = G</M> then each <M>m_{nj}</M> in the last row of <M>M</M> is
## equal to <M>1</M> since there is only one coset of <M>G</M> in <M>G</M>.
## In general, <M>m_{ij}</M> equals the number of conjugates of <M>H_i</M>
## containing <M>H_j</M>, multiplied by the index of <M>H_i</M> in its
## normalizer in <M>G</M>.
## Moreover, the number <M>c_{ij}</M> of conjugates of <M>H_j</M> which are
## contained in <M>H_i</M> can be derived from the marks <M>m_{ij}</M> via
## the formula
## <Display Mode="M">
## c_{ij} = ( m_{ij} m_{j1} ) / ( m_{i1} m_{jj} )
## </Display>.
## <P/>
## Both the marks <M>m_{ij}</M> and the numbers of subgroups <M>c_{ij}</M>
## are needed for the functions described in this chapter.
## <P/>
## A brief survey of properties of tables of marks and a description of
## algorithms for the interactive construction of tables of marks using
## &GAP; can be found in <Cite Key="Pfe97"/>.
## <#/GAPDoc>
##
#############################################################################
##
## 3. Table of Marks Objects in &GAP;
##
## <#GAPDoc Label="[3]{tom}">
## A table of marks of a group <M>G</M> in &GAP; is represented by an
## immutable (see <Ref Sect="Mutability and Copyability"/>) object
## <A>tom</A> in the category <Ref Filt="IsTableOfMarks"/>,
## with defining attributes <Ref Attr="SubsTom"/> and
## <Ref Attr="MarksTom"/>.
## These two attributes encode the matrix of marks in a compressed form.
## The <Ref Attr="SubsTom"/> value of <A>tom</A> is a list where for each
## conjugacy class of subgroups the class numbers of its subgroups are
## stored.
## These are exactly the positions in the corresponding row of the matrix of
## marks which have nonzero entries.
## The marks themselves are stored via the <Ref Attr="MarksTom"/> value of
## <A>tom</A>, which is a list that contains for each entry in
## <C>SubsTom( <A>tom</A> )</C> the corresponding nonzero value of the
## table of marks.
## <P/>
## It is possible to create table of marks objects that do not store a
## group, moreover one can create a table of marks object from a matrix of
## marks (see <Ref Attr="TableOfMarks" Label="for a matrix"/>).
## So it may happen that a table of marks object in &GAP; is in fact
## <E>not</E> the table of marks of a group.
## To some extent, the consistency of a table of marks object can be checked
## (see <Ref Sect="Other Operations for Tables of Marks"/>),
## but &GAP; knows no general way to prove or disprove that a given matrix
## of nonnegative integers is the matrix of marks for a group.
## Many functions for tables of marks work well without access to the group
## –this is one of the arguments why tables of marks are so
## useful–,
## but for example normalizers (see <Ref Oper="NormalizerTom"/>)
## and derived subgroups (see <Ref Oper="DerivedSubgroupTom"/>) of
## subgroups are in general not uniquely determined by the matrix of marks.
## <P/>
## &GAP; tables of marks are assumed to be in lower triangular form,
## that is, if a subgroup from the conjugacy class corresponding to the
## <M>i</M>-th row is contained in a subgroup from the class corresponding
## to the <M>j</M>-th row j then <M>i \leq j</M>.
## <P/>
## The <Ref Attr="MarksTom"/> information can be computed from the values of
## the attributes <Ref Attr="NrSubsTom"/>, <Ref Attr="LengthsTom"/>,
## <Ref Attr="OrdersTom"/>, and <Ref Attr="SubsTom"/>.
## <Ref Attr="NrSubsTom"/> stores a list containing for each entry in the
## <Ref Attr="SubsTom"/> value the corresponding number of conjugates that
## are contained in a subgroup,
## <Ref Attr="LengthsTom"/> a list containing for each conjugacy class
## of subgroups its length,
## and <Ref Attr="OrdersTom"/> a list containing for each class of subgroups
## their order.
## So the <Ref Attr="MarksTom"/> value of <A>tom</A> may be missing
## provided that the values of <Ref Attr="NrSubsTom"/>,
## <Ref Attr="LengthsTom"/>, and <Ref Attr="OrdersTom"/> are stored in
## <A>tom</A>.
## <P/>
## Additional information about a table of marks is needed by some
## functions.
## The class numbers of normalizers in <M>G</M> and the number of the
## derived subgroup of <M>G</M> can be stored via appropriate attributes
## (see <Ref Attr="NormalizersTom"/>,
## <Ref Oper="DerivedSubgroupTom"/>).
## <P/>
## If <A>tom</A> stores its group <M>G</M> and a bijection from the rows and
## columns of the matrix of marks of <A>tom</A> to the classes of subgroups
## of <M>G</M> then clearly normalizers, derived subgroup etc. can be
## computed from this information.
## But in general a table of marks need not have access to <M>G</M>,
## for example <A>tom</A> might have been constructed from a generic table
## of marks
## (see <Ref Sect="Generic Construction of Tables of Marks"/>),
## or as table of marks of a factor group from a given table of marks
## (see <Ref Oper="FactorGroupTom"/>).
## Access to the group <M>G</M> is provided by the attribute
## <Ref Attr="UnderlyingGroup" Label="for tables of marks"/>
## if this value is set.
## Access to the relevant information about conjugacy classes of subgroups
## of <M>G</M>
## –compatible with the ordering of rows and columns of the marks in
## <A>tom</A>– is signalled by the filter
## <Ref Filt="IsTableOfMarksWithGens"/>.
## <#/GAPDoc>
##
#############################################################################
##
## 4. Constructing Tables of Marks
##
#############################################################################
##
#A TableOfMarks( <G> )
#A TableOfMarks( <string> )
#A TableOfMarks( <matrix> )
##
## <#GAPDoc Label="TableOfMarks">
## <ManSection>
## <Attr Name="TableOfMarks" Arg='G' Label="for a group"/>
## <Attr Name="TableOfMarks" Arg='string' Label="for a string"/>
## <Attr Name="TableOfMarks" Arg='matrix' Label="for a matrix"/>
##
## <Description>
## In the first form, <A>G</A> must be a finite group,
## and <Ref Attr="TableOfMarks" Label="for a group"/>
## constructs the table of marks of <A>G</A>.
## This computation requires the knowledge of the complete subgroup lattice
## of <A>G</A> (see <Ref Attr="LatticeSubgroups"/>).
## If the lattice is not yet stored then it will be constructed.
## This may take a while if <A>G</A> is large.
## The result has the <Ref Filt="IsTableOfMarksWithGens"/> value
## <K>true</K>.
## <P/>
## In the second form, <A>string</A> must be a string,
## and <Ref Attr="TableOfMarks" Label="for a string"/> gets
## the table of marks with name <A>string</A> from the &GAP; library
## (see <Ref Sect="The Library of Tables of Marks"/>).
## If no table of marks with this name is contained in the library then
## <K>fail</K> is returned.
## <P/>
## In the third form, <A>matrix</A> 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 <A>matrix</A>,
## <Ref Attr="TableOfMarks" Label="for a matrix"/> returns
## a table of marks object
## (see <Ref Sect="Table of Marks Objects in GAP"/>)
## for which <A>matrix</A> 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
## <Ref Meth="IsInternallyConsistent" Label="for tables of marks"/>
## (see <Ref Sect="Other Operations for Tables of Marks"/>),
## and <K>fail</K> is returned if <A>matrix</A> is proved not to describe a
## matrix of marks;
## but if <Ref Attr="TableOfMarks" Label="for a matrix"/> 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.
## <P/>
## For an overview of operations for table of marks objects,
## see the introduction to Chapter <Ref Chap="Tables of Marks"/>.
## <P/>
## <Example><![CDATA[
## gap> tom:= TableOfMarks( AlternatingGroup( 5 ) );
## TableOfMarks( Alt( [ 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> )
## ]]></Example>
## <P/>
## The following <Ref Attr="TableOfMarks" Label="for a group"/> methods
## for a group are installed.
## <List>
## <Item>
## If the group is known to be cyclic then
## <Ref Attr="TableOfMarks" Label="for a group"/> constructs the
## table of marks essentially without the group, instead the knowledge
## about the structure of cyclic groups is used.
## </Item>
## <Item>
## If the lattice of subgroups is already stored in the group then
## <Ref Attr="TableOfMarks" Label="for a group"/> computes the
## table of marks from the lattice
## (see <Ref Func="TableOfMarksByLattice"/>).
## </Item>
## <Item>
## If the group is known to be solvable then
## <Ref Attr="TableOfMarks" Label="for a group"/> takes the
## lattice of subgroups (see <Ref Attr="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
## <Ref Func="TableOfMarksByLattice"/>.
## </Item>
## <Item>
## 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 <Ref Func="LatticeSubgroupsByTom"/>).
## </Item>
## </List>
## <P/>
## Conversely, the lattice of subgroups of a group with known table of marks
## can be computed using the table of marks, via the function
## <Ref Func="LatticeSubgroupsByTom"/>.
## This is also installed as a method for <Ref Attr="LatticeSubgroups"/>.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "TableOfMarks", IsGroup );
DeclareAttribute( "TableOfMarks", IsString );
DeclareAttribute( "TableOfMarks", IsTable );
#############################################################################
##
#F TableOfMarksByLattice( <G> )
##
## <#GAPDoc Label="TableOfMarksByLattice">
## <ManSection>
## <Func Name="TableOfMarksByLattice" Arg='G'/>
##
## <Description>
## <Ref Func="TableOfMarksByLattice"/> computes the table of marks of the
## group <A>G</A> from the lattice of subgroups of <A>G</A>.
## This lattice is computed via <Ref Attr="LatticeSubgroups"/>
## if it is not yet stored in <A>G</A>.
## The function <Ref Func="TableOfMarksByLattice"/> is installed as a method
## for <Ref Attr="TableOfMarks" Label="for a group"/> 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.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction( "TableOfMarksByLattice" );
#############################################################################
##
#F LatticeSubgroupsByTom( <G> )
##
## <#GAPDoc Label="LatticeSubgroupsByTom">
## <ManSection>
## <Func Name="LatticeSubgroupsByTom" Arg='G'/>
##
## <Description>
## <Ref Func="LatticeSubgroupsByTom"/> computes the lattice of subgroups of
## <A>G</A> from the table of marks of <A>G</A>,
## using <Ref Oper="RepresentativeTom"/>.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction( "LatticeSubgroupsByTom" );
#############################################################################
##
## 5. Printing Tables of Marks
##
## <#GAPDoc Label="[5]{tom}">
## <ManSection>
## <Meth Name="ViewObj" Arg='tom' Label="for a table of marks"/>
##
## <Description>
## The default <Ref Oper="ViewObj"/> method for tables of marks prints
## the string <C>"TableOfMarks"</C>,
## followed by –if known– the identifier
## (see <Ref Attr="Identifier" Label="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.
## </Description>
## </ManSection>
##
## <ManSection>
## <Meth Name="PrintObj" Arg='tom' Label="for a table of marks"/>
##
## <Description>
## The default <Ref Oper="PrintObj"/> method for tables of marks
## does the same as <Ref Oper="ViewObj"/>,
## except that <Ref Oper="PrintObj"/> is used for the group instead of
## <Ref Oper="ViewObj"/>.
## </Description>
## </ManSection>
##
## <ManSection>
## <Meth Name="Display" Arg='tom[, arec]' Label="for a table of marks"/>
##
## <Description>
## The default <Ref Oper="Display"/> method for a table of marks <A>tom</A>
## produces a formatted output of the marks in <A>tom</A>.
## 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
## <Ref Func="SizeScreen"/>.
## <P/>
## An interactive variant of <Ref Oper="Display"/> is the
## <Ref Oper="Browse" BookName="browse"/> method for tables of marks
## that is provided by the &GAP; package <Package>Browse</Package>,
## see <Ref Meth="Browse" Label="for tables of marks"
## BookName="browse"/>.
## <P/>
## The optional second argument <A>arec</A> of <Ref Oper="Display"/> can be
## used to change the default style for displaying a table of marks.
## <A>arec</A> must be a record, its relevant components are the following.
## <P/>
## <List>
## <Mark><C>classes</C></Mark>
## <Item>
## a list of class numbers to select only the rows and columns of the
## matrix that correspond to this list for printing,
## </Item>
## <Mark><C>form</C></Mark>
## <Item>
## one of the strings <C>"subgroups"</C>, <C>"supergroups"</C>;
## in the former case, at position <M>(i,j)</M> of the matrix the number
## of conjugates of <M>H_j</M> contained in <M>H_i</M> is printed,
## and in the latter case, at position <M>(i,j)</M> the number of
## conjugates of <M>H_i</M> which contain <M>H_j</M> is printed.
## </Item>
## </List>
## <P/>
## <Example><![CDATA[
## 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
##
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
#############################################################################
##
## 6. Sorting Tables of Marks
##
#############################################################################
##
#C IsTableOfMarks( <obj> )
##
## <#GAPDoc Label="IsTableOfMarks">
## <ManSection>
## <Filt Name="IsTableOfMarks" Arg='obj' Type='Category'/>
##
## <Description>
## Each table of marks belongs to this category.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareCategory( "IsTableOfMarks", IsObject );
#############################################################################
##
#O SortedTom( <tom>, <perm> )
##
## <#GAPDoc Label="SortedTom">
## <ManSection>
## <Oper Name="SortedTom" Arg='tom, perm'/>
##
## <Description>
## <Ref Oper="SortedTom"/> returns a table of marks where the rows and
## columns of the table of marks <A>tom</A> are reordered according to the
## permutation <A>perm</A>.
## <P/>
## <E>Note</E> that in each table of marks in &GAP;,
## the matrix of marks is assumed to have lower triangular shape
## (see <Ref Sect="Table of Marks Objects in GAP"/>).
## If the permutation <A>perm</A> does <E>not</E> have this property then
## the functions for tables of marks might return wrong results when applied
## to the output of <Ref Oper="SortedTom"/>.
## <P/>
## The returned table of marks has only those attribute values stored that
## are known for <A>tom</A> and listed in
## <Ref Var="TableOfMarksComponents"/>.
## <P/>
## <Example><![CDATA[
## 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
##
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "SortedTom", [ IsTableOfMarks, IsPerm ] );
#############################################################################
##
#A PermutationTom( <tom> )
##
## <#GAPDoc Label="PermutationTom">
## <ManSection>
## <Attr Name="PermutationTom" Arg='tom'/>
##
## <Description>
## For the table of marks <A>tom</A> of the group <M>G</M> stored as
## <Ref Attr="UnderlyingGroup" Label="for tables of marks"/>
## value of <A>tom</A>,
## <Ref Attr="PermutationTom"/> is a permutation <M>\pi</M> such that the
## <M>i</M>-th conjugacy class of subgroups of <M>G</M> belongs to the
## <M>i^\pi</M>-th column and row of marks in <A>tom</A>.
## <P/>
## This attribute value is bound only if <A>tom</A> was obtained from
## another table of marks by permuting with <Ref Oper="SortedTom"/>,
## and there is no default method to compute its value.
## <P/>
## 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
## <M>G</M> into <A>tom</A>.
## <P/>
## <Example><![CDATA[
## gap> MarksTom( tom )[2];
## [ 3, 3 ]
## gap> MarksTom( sorted )[2];
## [ 2, 2 ]
## gap> HasPermutationTom( sorted );
## true
## gap> PermutationTom( sorted );
## (2,3)
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "PermutationTom", IsTableOfMarks );
#############################################################################
##
## 7. Technical Details about Tables of Marks
##
#############################################################################
##
#V InfoTom
##
## <#GAPDoc Label="InfoTom">
## <ManSection>
## <InfoClass Name="InfoTom"/>
##
## <Description>
## is the info class for computations concerning tables of marks.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareInfoClass( "InfoTom" );
#############################################################################
##
#V TableOfMarksFamily
##
## <#GAPDoc Label="TableOfMarksFamily">
## <ManSection>
## <Fam Name="TableOfMarksFamily"/>
##
## <Description>
## Each table of marks belongs to this family.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
BindGlobal( "TableOfMarksFamily",
NewFamily( "TableOfMarksFamily", IsTableOfMarks ) );
#############################################################################
##
#F ConvertToTableOfMarks( <record> )
##
## <#GAPDoc Label="ConvertToTableOfMarks">
## <ManSection>
## <Func Name="ConvertToTableOfMarks" Arg='record'/>
##
## <Description>
## <Ref Func="ConvertToTableOfMarks"/> converts a record with components
## from <Ref Var="TableOfMarksComponents"/> into a table of marks object
## with the corresponding attributes.
## <P/>
## <Example><![CDATA[
## 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> )
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction( "ConvertToTableOfMarks" );
#############################################################################
##
## 8. Attributes of Tables of Marks
##
#############################################################################
##
#A MarksTom( <tom> ) . . . . . . . . . . . . . . . . . . defining attribute
#A SubsTom( <tom> ) . . . . . . . . . . . . . . . . . . defining attribute
##
## <#GAPDoc Label="MarksTom">
## <ManSection>
## <Attr Name="MarksTom" Arg='tom'/>
## <Attr Name="SubsTom" Arg='tom'/>
##
## <Description>
## The matrix of marks (see <Ref Sect="More about Tables of Marks"/>)
## of the table of marks <A>tom</A> is stored in a compressed form
## where zeros are omitted,
## using the attributes <Ref Attr="MarksTom"/> and <Ref Attr="SubsTom"/>.
## If <M>M</M> is the square matrix of marks of <A>tom</A>
## (see <Ref Attr="MatTom"/>) then the <Ref Attr="SubsTom"/> value of
## <A>tom</A> is a list that contains at position <M>i</M> the list
## of all positions of nonzero entries of the <M>i</M>-th row of <M>M</M>,
## and the <Ref Attr="MarksTom"/> value of <A>tom</A> is a list
## that contains at position <M>i</M> the list of the corresponding marks.
## <P/>
## <Ref Attr="MarksTom"/> and <Ref Attr="SubsTom"/> are defining attributes
## of tables of marks (see <Ref Sect="Table of Marks Objects in GAP"/>).
## There is no default method for computing the <Ref Attr="SubsTom"/> value,
## and the default <Ref Attr="MarksTom"/> method needs the values of
## <Ref Attr="NrSubsTom"/> and <Ref Attr="OrdersTom"/>.
## <P/>
## <Example><![CDATA[
## 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 ] ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "MarksTom", IsTableOfMarks );
DeclareAttribute( "SubsTom", IsTableOfMarks );
#############################################################################
##
#A NrSubsTom( <tom> )
#A OrdersTom( <tom> )
##
## <#GAPDoc Label="NrSubsTom">
## <ManSection>
## <Attr Name="NrSubsTom" Arg='tom'/>
## <Attr Name="OrdersTom" Arg='tom'/>
##
## <Description>
## Instead of storing the marks (see <Ref Attr="MarksTom"/>) of the
## table of marks <A>tom</A> one can use a matrix which contains at position
## <M>(i,j)</M> the number of subgroups of conjugacy class <M>j</M>
## that are contained in one member of the conjugacy class <M>i</M>.
## These values are stored in the <Ref Attr="NrSubsTom"/> value in the same
## way as the marks in the <Ref Attr="MarksTom"/> value.
## <P/>
## <Ref Attr="OrdersTom"/> returns a list that contains at position <M>i</M>
## the order of a representative of the <M>i</M>-th conjugacy class of
## subgroups of <A>tom</A>.
## <P/>
## One can compute the <Ref Attr="NrSubsTom"/> and <Ref Attr="OrdersTom"/>
## values from the <Ref Attr="MarksTom"/> value of <A>tom</A>
## and vice versa.
## <P/>
## <Example><![CDATA[
## 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 ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "NrSubsTom", IsTableOfMarks );
DeclareAttribute( "OrdersTom", IsTableOfMarks );
#############################################################################
##
#A LengthsTom( <tom> )
##
## <#GAPDoc Label="LengthsTom">
## <ManSection>
## <Attr Name="LengthsTom" Arg='tom'/>
##
## <Description>
## For a table of marks <A>tom</A>,
## <Ref Attr="LengthsTom"/> returns a list of the lengths of
## the conjugacy classes of subgroups.
## <P/>
## <Example><![CDATA[
## gap> LengthsTom( a5 );
## [ 1, 15, 10, 5, 6, 10, 6, 5, 1 ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "LengthsTom", IsTableOfMarks );
#############################################################################
##
#A ClassTypesTom( <tom> )
##
## <#GAPDoc Label="ClassTypesTom">
## <ManSection>
## <Attr Name="ClassTypesTom" Arg='tom'/>
##
## <Description>
## <Ref Attr="ClassTypesTom"/> distinguishes isomorphism types of the
## classes of subgroups of the table of marks <A>tom</A>
## as far as this is possible from the <Ref Attr="SubsTom"/> and
## <Ref Attr="MarksTom"/> values of <A>tom</A>.
## <P/>
## Two subgroups are clearly not isomorphic if they have different orders.
## Moreover, isomorphic subgroups must contain the same number of subgroups
## of each type.
## <P/>
## Each type is represented by a positive integer.
## <Ref Attr="ClassTypesTom"/> returns the list which contains for each
## class of subgroups its corresponding type.
## <P/>
## <Example><![CDATA[
## 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 ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "ClassTypesTom", IsTableOfMarks );
#############################################################################
##
#A ClassNamesTom( <tom> )
##
## <#GAPDoc Label="ClassNamesTom">
## <ManSection>
## <Attr Name="ClassNamesTom" Arg='tom'/>
##
## <Description>
## <Ref Attr="ClassNamesTom"/> constructs generic names for the conjugacy
## classes of subgroups of the table of marks <A>tom</A>.
## In general, the generic name of a class of non-cyclic subgroups consists
## of three parts and has the form
## <C>"(</C><A>o</A><C>)_{</C><A>t</A><C>}</C><A>l</A><C>"</C>,
## where <A>o</A> indicates the order of the subgroup,
## <A>t</A> is a number that distinguishes different types of subgroups of
## the same order, and <A>l</A> 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 <Ref Attr="ClassTypesTom"/>).
## This is slightly weaker than isomorphism.
## <P/>
## 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 <C>{}</C> around the type are omitted
## if the type number has only one digit.
## <P/>
## 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
## <C>"<A>o</A>,<A>l</A>"</C>.
## Again, the letter is omitted if there is only one class of cyclic
## subgroups of that order.
## <P/>
## <Example><![CDATA[
## 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)" ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "ClassNamesTom", IsTableOfMarks );
#############################################################################
##
#A FusionsTom( <tom> )
##
## <#GAPDoc Label="FusionsTom">
## <ManSection>
## <Attr Name="FusionsTom" Arg='tom'/>
##
## <Description>
## For a table of marks <A>tom</A>,
## <Ref Attr="FusionsTom"/> is a list of fusions into other tables of marks.
## Each fusion is a list of length two, the first entry being the
## <Ref Attr="Identifier" Label="for tables of marks"/>) value
## of the image table, the second entry being the list of images of
## the class positions of <A>tom</A> in the image table.
## <P/>
## This attribute is mainly used for tables of marks in the &GAP; library
## (see <Ref Sect="The Library of Tables of Marks"/>).
## <P/>
## <Example><![CDATA[
## 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 ] ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "FusionsTom", IsTableOfMarks, "mutable" );
#############################################################################
##
#A UnderlyingGroup( <tom> )
##
## <#GAPDoc Label="UnderlyingGroup:tom">
## <ManSection>
## <Attr Name="UnderlyingGroup" Arg='tom' Label="for tables of marks"/>
##
## <Description>
## <Ref Attr="UnderlyingGroup" Label="for tables of marks"/> is used
## to access an underlying group that is stored on the table of marks
## <A>tom</A>.
## There is no default method to compute an underlying group if it is not
## stored.
## <P/>
## <Example><![CDATA[
## gap> UnderlyingGroup( a6 );
## Group([ (1,2)(3,4), (1,2,4,5)(3,6) ])
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "UnderlyingGroup", IsTableOfMarks );
#############################################################################
##
#A IdempotentsTom( <tom> )
#A IdempotentsTomInfo( <tom> )
##
## <#GAPDoc Label="IdempotentsTom">
## <ManSection>
## <Attr Name="IdempotentsTom" Arg='tom'/>
## <Attr Name="IdempotentsTomInfo" Arg='tom'/>
##
## <Description>
## <Ref Attr="IdempotentsTom"/> encodes the idempotents of the integral
## Burnside ring described by the table of marks <A>tom</A>.
## The return value is a list <M>l</M> of positive integers such that each
## row vector describing a primitive idempotent has value <M>1</M> at all
## positions with the same entry in <M>l</M>, and <M>0</M> at all other
## positions.
## <P/>
## According to A. Dress <Cite Key="Dre69"/>
## (see also <Cite Key="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 <Ref Oper="CyclicExtensionsTom" Label="for a prime"/>).
## <P/>
## <Ref Attr="IdempotentsTomInfo"/> returns a record with components
## <C>fixpointvectors</C> and <C>primidems</C>, both bound to lists.
## The <M>i</M>-th entry of the <C>fixpointvectors</C> list is the
## <M>0-1</M>-vector describing the <M>i</M>-th primitive idempotent,
## and the <M>i</M>-th entry of <C>primidems</C> is the decomposition of this
## idempotent in the rows of <A>tom</A>.
## <P/>
## <Example><![CDATA[
## gap> IdempotentsTom( a5 );
## [ 1, 1, 1, 1, 1, 1, 1, 1, 9 ]
## gap> IdempotentsTomInfo( a5 );
## rec(
## fixpointvectors := [ [ 1, 1, 1, 1, 1, 1, 1, 1, 0 ],
## [ 0, 0, 0, 0, 0, 0, 0, 0, 1 ] ],
## primidems := [ [ 1, -2, -1, 0, 0, 1, 1, 1 ],
## [ -1, 2, 1, 0, 0, -1, -1, -1, 1 ] ] )
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "IdempotentsTom", IsTableOfMarks );
DeclareAttribute( "IdempotentsTomInfo", IsTableOfMarks );
#############################################################################
##
#A Identifier( <tom> )
##
## <#GAPDoc Label="Identifier:tom">
## <ManSection>
## <Attr Name="Identifier" Arg='tom' Label="for tables of marks"/>
##
## <Description>
## The identifier of a table of marks <A>tom</A> is a string.
## It is used for printing the table of marks
## (see <Ref Sect="Printing Tables of Marks"/>)
## and in fusions between tables of marks
## (see <Ref Attr="FusionsTom"/>).
## <P/>
## If <A>tom</A> is a table of marks from the &GAP; library of tables of
## marks (see <Ref Sect="The Library of Tables of Marks"/>)
## then it has an identifier,
## and if <A>tom</A> was constructed from a group with <Ref Attr="Name"/>
## then this name is chosen as
## <Ref Attr="Identifier" Label="for tables of marks"/> value.
## There is no default method to compute an identifier in all other cases.
## <P/>
## <Example><![CDATA[
## gap> Identifier( a5 );
## "A5"
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "Identifier", IsTableOfMarks );
#############################################################################
##
#A MatTom( <tom> )
##
## <#GAPDoc Label="MatTom">
## <ManSection>
## <Attr Name="MatTom" Arg='tom'/>
##
## <Description>
## <Ref Attr="MatTom"/> returns the square matrix of marks
## (see <Ref Sect="More about Tables of Marks"/>) of the table of marks
## <A>tom</A> which is stored in a compressed form using the attributes
## <Ref Attr="MarksTom"/> and <Ref Attr="SubsTom"/>
## This may need substantially more space than the values of
## <Ref Attr="MarksTom"/> and <Ref Attr="SubsTom"/>.
## <P/>
## <Example><![CDATA[
## 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 ] ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "MatTom", IsTableOfMarks );
#############################################################################
##
#A MoebiusTom( <tom> )
##
## <#GAPDoc Label="MoebiusTom">
## <ManSection>
## <Attr Name="MoebiusTom" Arg='tom'/>
##
## <Description>
## <Ref Attr="MoebiusTom"/> computes the Möbius values both of the subgroup
## lattice of the group <M>G</M> with table of marks <A>tom</A>
## and of the poset of conjugacy classes of subgroups of <M>G</M>.
## It returns a record where the component
## <C>mu</C> contains the Möbius values of the subgroup lattice,
## and the component <C>nu</C> contains the Möbius values of the poset.
## <P/>
## Moreover, according to an observation of Isaacs et al.
## (see <Cite Key="HIO89"/>, <Cite Key="Pah93"/>),
## the values on the subgroup lattice often can be derived
## from those of the poset of conjugacy classes.
## These <Q>expected values</Q> are returned in the component <C>ex</C>,
## and the list of numbers of those subgroups where the expected value does
## not coincide with the actual value are returned in the component
## <C>hyp</C>.
## For the computation of these values, the position of the derived subgroup
## of <M>G</M> is needed (see <Ref Oper="DerivedSubgroupTom"/>).
## If it is not uniquely determined then the result does not have the
## components <C>ex</C> and <C>hyp</C>.
## <P/>
## <Example><![CDATA[
## gap> MoebiusTom( a5 );
## rec( ex := [ -60, 4, 2,,, -1, -1, -1, 1 ], hyp := [ ],
## mu := [ -60, 4, 2,,, -1, -1, -1, 1 ],
## nu := [ -1, 2, 1,,, -1, -1, -1, 1 ] )
## 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
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "MoebiusTom", IsTableOfMarks );
#############################################################################
##
#A WeightsTom( <tom> )
##
## <#GAPDoc Label="WeightsTom">
## <ManSection>
## <Attr Name="WeightsTom" Arg='tom'/>
##
## <Description>
## <Ref Attr="WeightsTom"/> extracts the <E>weights</E> from the table of
## marks <A>tom</A>, i.e., the diagonal entries of the matrix of marks
## (see <Ref Attr="MarksTom"/>),
## indicating the index of a subgroup in its normalizer.
## <P/>
## <Example><![CDATA[
## gap> wt:= WeightsTom( a5 );
## [ 60, 2, 2, 3, 2, 1, 1, 1, 1 ]
## ]]></Example>
## <P/>
## This information may be used to obtain the numbers of conjugate
## supergroups from the marks.
## <Example><![CDATA[
## 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 ] ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "WeightsTom", IsTableOfMarks );
#############################################################################
##
## 9. Properties of Tables of Marks
##
## <#GAPDoc Label="[6]{tom}">
## For a table of marks <A>tom</A> of a group <M>G</M>,
## the following properties have the same meaning as the corresponding
## properties for <M>G</M>.
## Additionally, if a positive integer <A>sub</A> is given
## as the second argument
## then the value of the corresponding property for the <A>sub</A>-th class
## of subgroups of <A>tom</A> is returned.
## <P/>
## <ManSection>
## <Prop Name="IsAbelianTom" Arg='tom[, sub]'/>
## <Prop Name="IsCyclicTom" Arg='tom[, sub]'/>
## <Prop Name="IsNilpotentTom" Arg='tom[, sub]'/>
## <Prop Name="IsPerfectTom" Arg='tom[, sub]'/>
## <Prop Name="IsSolvableTom" Arg='tom[, sub]'/>
##
## <Description>
## <Example><![CDATA[
## 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
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
#############################################################################
##
#P IsAbelianTom( <tom>[, <sub>] )
##
## <ManSection>
## <Prop Name="IsAbelianTom" Arg='tom[, sub]'/>
##
## <Description>
## <Ref Func="IsAbelianTom"/> tests if the underlying group of the table of
## marks <A>tom</A> is abelian.
## If a second argument <A>sub</A> is given then <Ref Func="IsAbelianTom"/>
## returns whether the groups in the <A>sub</A>-th class of subgroups in
## <A>tom</A> are abelian.
## </Description>
## </ManSection>
##
DeclareProperty( "IsAbelianTom", IsTableOfMarks );
DeclareOperation( "IsAbelianTom", [ IsTableOfMarks, IsPosInt ] );
#############################################################################
##
#P IsCyclicTom( <tom>[, <sub>] )
##
## <ManSection>
## <Prop Name="IsCyclicTom" Arg='tom[, sub]'/>
##
## <Description>
## <Ref Func="IsCyclicTom"/> tests if the underlying group of the table of
## marks <A>tom</A> is cyclic.
## If a second argument <A>sub</A> is given then <Ref Func="IsCyclicTom"/>
## returns whether the groups in the <A>sub</A>-th class of subgroups in
## <A>tom</A> are cyclic.
## <P/>
## A subgroup is cyclic if and only if the sum over the corresponding row of
## the inverse table of marks is nonzero
## (see <Cite Key="Ker91" Where="page 125"/>).
## Thus we only have to decompose the corresponding idempotent.
## </Description>
## </ManSection>
##
DeclareProperty( "IsCyclicTom", IsTableOfMarks );
DeclareOperation( "IsCyclicTom", [ IsTableOfMarks, IsPosInt ] );
#############################################################################
##
#P IsNilpotentTom( <tom>[, <sub>] )
##
## <ManSection>
## <Prop Name="IsNilpotentTom" Arg='tom[, sub]'/>
##
## <Description>
## <Ref Func="IsNilpotentTom"/> tests if the underlying group of the table
## of marks <A>tom</A> is nilpotent.
## If a second argument <A>sub</A> is given then
## <Ref Func="IsNilpotentTom"/> returns whether the groups in the
## <A>sub</A>-th class of subgroups in <A>tom</A> are nilpotent.
## </Description>
## </ManSection>
##
DeclareProperty( "IsNilpotentTom", IsTableOfMarks );
DeclareOperation( "IsNilpotentTom", [ IsTableOfMarks, IsPosInt ] );
#############################################################################
##
#P IsPerfectTom( <tom>[, <sub>] )
##
## <ManSection>
## <Prop Name="IsPerfectTom" Arg='tom[, sub]'/>
##
## <Description>
## <Ref Func="IsPerfectTom"/> tests if the underlying group of the table of
## marks <A>tom</A> is perfect.
## If a second argument <A>sub</A> is given then <Ref Func="IsPerfectTom"/>
## returns whether the groups in the <A>sub</A>-th class of subgroups in
## <A>tom</A> are perfect.
## </Description>
## </ManSection>
##
DeclareProperty( "IsPerfectTom", IsTableOfMarks );
DeclareOperation( "IsPerfectTom", [ IsTableOfMarks, IsPosInt ] );
#############################################################################
##
#P IsSolvableTom( <tom>[, <sub>] )
##
## <ManSection>
## <Prop Name="IsSolvableTom" Arg='tom[, sub]'/>
##
## <Description>
## <Ref Func="IsSolvableTom"/> tests if the underlying group of the table of
## marks <A>tom</A> is solvable.
## If a second argument <A>sub</A> is given then <Ref Func="IsSolvableTom"/>
## returns whether the groups in the <A>sub</A>-th class of subgroups in
## <A>tom</A> are solvable.
## </Description>
## </ManSection>
##
DeclareProperty( "IsSolvableTom", IsTableOfMarks );
DeclareOperation( "IsSolvableTom", [ IsTableOfMarks, IsPosInt ] );
#############################################################################
##
## 10. Other Operations for Tables of Marks
##
## <#GAPDoc Label="[7]{tom}">
## <ManSection>
## <Meth Name="IsInternallyConsistent"
## Arg='tom' Label="for tables of marks"/>
##
## <Description>
## For a table of marks <A>tom</A>,
## <Ref Meth="IsInternallyConsistent" Label="for tables of marks"/>
## decomposes all tensor products of rows of <A>tom</A>.
## It returns <K>true</K> if all decomposition numbers are nonnegative
## integers, and <K>false</K> otherwise.
## This provides a strong consistency check for a table of marks.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
#############################################################################
##
#O DerivedSubgroupTom( <tom>, <sub> )
#F DerivedSubgroupsTom( <tom> )
##
## <#GAPDoc Label="DerivedSubgroupTom">
## <ManSection>
## <Oper Name="DerivedSubgroupTom" Arg='tom, sub'/>
## <Func Name="DerivedSubgroupsTom" Arg='tom'/>
##
## <Description>
## For a table of marks <A>tom</A> and a positive integer <A>sub</A>,
## <Ref Oper="DerivedSubgroupTom"/> returns either a positive integer
## <M>i</M> or a list <M>l</M> of positive integers.
## In the former case, the result means that the derived subgroups of the
## subgroups in the <A>sub</A>-th class of <A>tom</A> lie in the
## <M>i</M>-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 <M>l</M>.
## <P/>
## Values computed with <Ref Oper="DerivedSubgroupTom"/> are stored
## using the attribute <Ref Attr="DerivedSubgroupsTomPossible"/>.
## <P/>
## <Ref Func="DerivedSubgroupsTom"/> is just the list of
## <Ref Oper="DerivedSubgroupTom"/> values for all values of <A>sub</A>.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "DerivedSubgroupTom", [ IsTableOfMarks, IsPosInt ] );
DeclareGlobalFunction( "DerivedSubgroupsTom");
#############################################################################
##
#A DerivedSubgroupsTomPossible( <tom> )
#A DerivedSubgroupsTomUnique( <tom> )
##
## <#GAPDoc Label="DerivedSubgroupsTomPossible">
## <ManSection>
## <Attr Name="DerivedSubgroupsTomPossible" Arg='tom'/>
## <Attr Name="DerivedSubgroupsTomUnique" Arg='tom'/>
##
## <Description>
## Let <A>tom</A> be a table of marks.
## The value of the attribute <Ref Attr="DerivedSubgroupsTomPossible"/> is
## a list in which the value at position <M>i</M> –if bound–
## is a positive integer or a list; the meaning of the entry is the same as
## in <Ref Oper="DerivedSubgroupTom"/>.
## <P/>
## If the value of the attribute <Ref Attr="DerivedSubgroupsTomUnique"/> is
## known for <A>tom</A> then it is a list of positive integers,
## the value at position <M>i</M> being the position of the class of derived
## subgroups of the <M>i</M>-th class of subgroups in <A>tom</A>.
## <P/>
## The derived subgroups are in general not uniquely determined by the table
## of marks if no <Ref Attr="UnderlyingGroup" Label="for tables of marks"/>
## value is stored, so there is no default method for
## <Ref Attr="DerivedSubgroupsTomUnique"/>.
## But in some cases the derived subgroups are explicitly set when the table
## of marks is constructed.
## In this case, <Ref Oper="DerivedSubgroupTom"/> does not set values in
## the <Ref Attr="DerivedSubgroupsTomPossible"/> list.
## <P/>
## The <Ref Attr="DerivedSubgroupsTomUnique"/> value is automatically set
## when the last missing unique value is entered in the
## <Ref Attr="DerivedSubgroupsTomPossible"/> list by
## <Ref Oper="DerivedSubgroupTom"/>.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
## Currently the `DerivedSubgroupsTomUnique' value seems to be set
## automatically in all cases.
## Therefore, no example is shown.
##
DeclareAttribute( "DerivedSubgroupsTomPossible", IsTableOfMarks, "mutable" );
DeclareAttribute( "DerivedSubgroupsTomUnique", IsTableOfMarks );
#############################################################################
##
#O NormalizerTom( <tom>, <sub> )
#A NormalizersTom( <tom> )
##
## <#GAPDoc Label="NormalizerTom">
## <ManSection>
## <Oper Name="NormalizerTom" Arg='tom, sub'/>
## <Attr Name="NormalizersTom" Arg='tom'/>
##
## <Description>
## Let <A>tom</A> be the table of marks of a group <M>G</M>.
## <Ref Oper="NormalizerTom"/> tries to find the conjugacy class of the
## normalizer <M>N</M> in <M>G</M> of a subgroup <M>U</M> in the
## <A>sub</A>-th class of <A>tom</A>.
## 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 <A>tom</A> knows the subgroup lattice of <M>G</M>
## (see <Ref Filt="IsTableOfMarksWithGens"/>)
## then all normalizers are uniquely determined.
## <Ref Oper="NormalizerTom"/> should never return an empty list.
## <P/>
## <Ref Attr="NormalizersTom"/> returns the list of positions of the classes
## of normalizers of subgroups in <A>tom</A>.
## In addition to the criteria for a single class of subgroup used by
## <Ref Oper="NormalizerTom"/>,
## the approximations of normalizers for several classes are used and thus
## <Ref Attr="NormalizersTom"/> may return better approximations than
## <Ref Oper="NormalizerTom"/>.
## <P/>
## <Example><![CDATA[
## gap> NormalizerTom( a5, 4 );
## 8
## gap> NormalizersTom( a5 );
## [ 9, 4, 6, 8, 7, 6, 7, 8, 9 ]
## ]]></Example>
## <P/>
## The example shows that a subgroup with class number 4 in <M>A_5</M>
## (which is a Kleinian four group)
## is normalized by a subgroup in class 8.
## This class contains the subgroups of <M>A_5</M> which are isomorphic to
## <M>A_4</M>.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "NormalizerTom", [ IsTableOfMarks, IsPosInt ] );
DeclareAttribute( "NormalizersTom", IsTableOfMarks );
#############################################################################
##
#O ContainedTom( <tom>, <sub1>, <sub2> )
##
## <#GAPDoc Label="ContainedTom">
## <ManSection>
## <Oper Name="ContainedTom" Arg='tom, sub1, sub2'/>
##
## <Description>
## <Ref Oper="ContainedTom"/> returns the number of subgroups in class
## <A>sub1</A> of the table of marks <A>tom</A> that are contained in one
## fixed member of the class <A>sub2</A>.
## <P/>
## <Example><![CDATA[
## gap> ContainedTom( a5, 3, 5 ); ContainedTom( a5, 3, 8 );
## 0
## 4
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "ContainedTom", [IsTableOfMarks, IsPosInt, IsPosInt ] );
#############################################################################
##
#O ContainingTom( <tom>, <sub1>, <sub2> )
##
## <#GAPDoc Label="ContainingTom">
## <ManSection>
## <Oper Name="ContainingTom" Arg='tom, sub1, sub2'/>
##
## <Description>
## <Ref Oper="ContainingTom"/> returns the number of subgroups in class
## <A>sub2</A> of the table of marks <A>tom</A> that contain one fixed
## member of the class <A>sub1</A>.
## <P/>
## <Example><![CDATA[
## gap> ContainingTom( a5, 3, 5 ); ContainingTom( a5, 3, 8 );
## 0
## 2
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "ContainingTom", [ IsTableOfMarks, IsPosInt, IsPosInt ] );
#############################################################################
##
#O CyclicExtensionsTom( <tom>, <p> )
#A CyclicExtensionsTom( <tom>[, <list>] )
##
## <#GAPDoc Label="CyclicExtensionsTom">
## <ManSection>
## <Oper Name="CyclicExtensionsTom" Arg='tom, p' Label="for a prime"/>
## <Attr Name="CyclicExtensionsTom" Arg='tom[, list]'
## Label="for a list of primes"/>
##
## <Description>
## According to A. Dress <Cite Key="Dre69"/>,
## two columns of the table of marks <A>tom</A> are equal modulo the prime
## <A>p</A> if and only if the corresponding subgroups are connected by a
## chain of normal extensions of order <A>p</A>.
## <P/>
## Called with <A>tom</A> and <A>p</A>,
## <Ref Oper="CyclicExtensionsTom" Label="for a prime"/>
## returns the classes of this equivalence relation.
## <P/>
## In the second form, <A>list</A> 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 <A>list</A>.
## The default value for <A>list</A> is the set of prime divisors of the
## order of the group of <A>tom</A>.
## <P/>
## (This information is <E>not</E> used by <Ref Oper="NormalizerTom"/>
## although it might give additional restrictions in the search of
## normalizers.)
## <P/>
## <Example><![CDATA[
## gap> CyclicExtensionsTom( a5, 2 );
## [ [ 1, 2, 4 ], [ 3, 6 ], [ 5, 7 ], [ 8 ], [ 9 ] ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "CyclicExtensionsTom", IsTableOfMarks );
DeclareOperation( "CyclicExtensionsTom", [ IsTableOfMarks, IsPosInt ] );
DeclareOperation( "CyclicExtensionsTom", [ IsTableOfMarks, IsList ] );
#############################################################################
##
#A ComputedCyclicExtensionsTom( <tom> )
#O CyclicExtensionsTomOp( <tom>, <p> )
#O CyclicExtensionsTomOp( <tom>, <list> )
##
## <ManSection>
## <Attr Name="ComputedCyclicExtensionsTom" Arg='tom'/>
## <Oper Name="CyclicExtensionsTomOp" Arg='tom, p'/>
## <Oper Name="CyclicExtensionsTomOp" Arg='tom, list'/>
##
## <Description>
## The attribute <Ref Func="ComputedCyclicExtensionsTom"/> is used by the
## default <Ref Func="CyclicExtensionsTom"/> method to store the computed
## equivalence classes for the table of marks <A>tom</A> and access them in
## subsequent calls.
## <P/>
## The operation <Ref Func="CyclicExtensionsTomOp"/> does the real work for
## <Ref Func="CyclicExtensionsTom"/>.
## </Description>
## </ManSection>
##
DeclareAttribute( "ComputedCyclicExtensionsTom", IsTableOfMarks, "mutable" );
DeclareOperation( "CyclicExtensionsTomOp", [ IsTableOfMarks, IsPosInt ] );
DeclareOperation( "CyclicExtensionsTomOp", [ IsTableOfMarks, IsList ] );
#############################################################################
##
#O DecomposedFixedPointVector( <tom>, <fix> )
##
## <#GAPDoc Label="DecomposedFixedPointVector">
## <ManSection>
## <Oper Name="DecomposedFixedPointVector" Arg='tom, fix'/>
##
## <Description>
## Let <A>tom</A> be the table of marks of a group <M>G</M>
## and let <A>fix</A> be a vector of fixed point numbers w.r.t. an
## action of <M>G</M>, i.e., a vector which contains for each class of
## subgroups the number of fixed points under the given action.
## <Ref Oper="DecomposedFixedPointVector"/> returns the decomposition of
## <A>fix</A> into rows of the table of marks.
## This decomposition corresponds to a decomposition of the action into
## transitive constituents.
## Trailing zeros in <A>fix</A> may be omitted.
## <P/>
## <Example><![CDATA[
## gap> DecomposedFixedPointVector( a5, [ 16, 4, 1, 0, 1, 1, 1 ] );
## [ 0, 0, 0, 0, 0, 1, 1 ]
## ]]></Example>
## <P/>
## The vector <A>fix</A> may be any vector of integers.
## The resulting decomposition, however, will not be integral, in general.
## <Example><![CDATA[
## gap> DecomposedFixedPointVector( a5, [ 0, 0, 0, 0, 1, 1 ] );
## [ 2/5, -1, -1/2, 0, 1/2, 1 ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "DecomposedFixedPointVector",
[ IsTableOfMarks, IsList ] );
#############################################################################
##
#O EulerianFunctionByTom( <tom>, <n>[, <sub>] )
##
## <#GAPDoc Label="EulerianFunctionByTom">
## <ManSection>
## <Oper Name="EulerianFunctionByTom" Arg='tom, n[, sub]'/>
##
## <Description>
## Called with two arguments, <Ref Oper="EulerianFunctionByTom"/> computes
## the Eulerian function (see <Ref Oper="EulerianFunction"/>) of the
## underlying group <M>G</M> of the table of marks <A>tom</A>,
## that is, the number of <A>n</A>-tuples of elements in <M>G</M> that
## generate <M>G</M>.
## If the optional argument <A>sub</A> is given then
## <Ref Oper="EulerianFunctionByTom"/> computes the Eulerian function
## of each subgroup in the <A>sub</A>-th class of subgroups of <A>tom</A>.
## <P/>
## For a group <M>G</M> whose table of marks is known,
## <Ref Oper="EulerianFunctionByTom"/>
## is installed as a method for <Ref Oper="EulerianFunction"/>.
## <P/>
## <Example><![CDATA[
## gap> EulerianFunctionByTom( a5, 2 );
## 2280
## gap> EulerianFunctionByTom( a5, 3 );
## 200160
## gap> EulerianFunctionByTom( a5, 2, 3 );
## 8
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "EulerianFunctionByTom", [ IsTableOfMarks, IsPosInt ] );
DeclareOperation( "EulerianFunctionByTom",
[ IsTableOfMarks, IsPosInt, IsPosInt ] );
#############################################################################
##
#O IntersectionsTom( <tom>, <sub1>, <sub2> )
##
## <#GAPDoc Label="IntersectionsTom">
## <ManSection>
## <Oper Name="IntersectionsTom" Arg='tom, sub1, sub2'/>
##
## <Description>
## The intersections of the groups in the <A>sub1</A>-th conjugacy class of
## subgroups of the table of marks <A>tom</A> with the groups in the
## <A>sub2</A>-th conjugacy classes of subgroups of <A>tom</A>
## are determined up to conjugacy by the decomposition of the tensor product
## of their rows of marks.
## <Ref Oper="IntersectionsTom"/> returns a list <M>l</M> that describes
## this decomposition.
## The <M>i</M>-th entry in <M>l</M> is the multiplicity of groups in the
## <M>i</M>-th conjugacy class as an intersection.
## <P/>
## <Example><![CDATA[
## gap> IntersectionsTom( a5, 8, 8 );
## [ 0, 0, 1, 0, 0, 0, 0, 1 ]
## ]]></Example>
## Any two subgroups of class number 8 (<M>A_4</M>) of <M>A_5</M> are either
## equal and their intersection has again class number 8,
## or their intersection has class number <M>3</M>,
## and is a cyclic subgroup of order 3.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "IntersectionsTom",
[ IsTableOfMarks, IsPosInt, IsPosInt ] );
#############################################################################
##
#O FactorGroupTom( <tom>, <n> )
##
## <#GAPDoc Label="FactorGroupTom">
## <ManSection>
## <Oper Name="FactorGroupTom" Arg='tom, n'/>
##
## <Description>
## For a table of marks <A>tom</A> of a group <M>G</M>
## and the normal subgroup <M>N</M> of <M>G</M> corresponding to the
## <A>n</A>-th class of subgroups of <A>tom</A>,
## <Ref Oper="FactorGroupTom"/> returns the table of marks of the factor
## group <M>G / N</M>.
## <P/>
## <Example><![CDATA[
## gap> s4:= TableOfMarks( SymmetricGroup( 4 ) );
## TableOfMarks( Sym( [ 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
##
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "FactorGroupTom", [ IsTableOfMarks, IsPosInt ] );
#############################################################################
##
#A MaximalSubgroupsTom( <tom>[, <sub>] )
##
## <#GAPDoc Label="MaximalSubgroupsTom">
## <ManSection>
## <Attr Name="MaximalSubgroupsTom" Arg='tom[, sub]'/>
##
## <Description>
## Called with a table of marks <A>tom</A>,
## <Ref Attr="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 <A>tom</A>,
## the second entry being the list of class lengths of these groups.
## <P/>
## Called with a table of marks <A>tom</A> and a position <A>sub</A>,
## the same information for the <A>sub</A>-th class of subgroups is
## returned.
## <P/>
## <Example><![CDATA[
## gap> MaximalSubgroupsTom( s4 );
## [ [ 10, 9, 8 ], [ 1, 3, 4 ] ]
## gap> MaximalSubgroupsTom( s4, 10 );
## [ [ 5, 4 ], [ 1, 4 ] ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "MaximalSubgroupsTom", IsTableOfMarks );
DeclareOperation( "MaximalSubgroupsTom", [ IsTableOfMarks, IsPosInt ] );
#############################################################################
##
#O MinimalSupergroupsTom( <tom>, <sub> )
##
## <#GAPDoc Label="MinimalSupergroupsTom">
## <ManSection>
## <Oper Name="MinimalSupergroupsTom" Arg='tom, sub'/>
##
## <Description>
## For a table of marks <A>tom</A>,
## <Ref Oper="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 <A>sub</A>-th
## class of subgroups of <A>tom</A>,
## the second entry being the list of class lengths of these groups.
## <P/>
## <Example><![CDATA[
## gap> MinimalSupergroupsTom( s4, 5 );
## [ [ 9, 10 ], [ 3, 1 ] ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "MinimalSupergroupsTom", [ IsTableOfMarks, IsPosInt ] );
#############################################################################
##
## 11. Accessing Subgroups via Tables of Marks
##
## <#GAPDoc Label="[8]{tom}">
## Let <A>tom</A> be the table of marks of the group <M>G</M>,
## and assume that <A>tom</A> has access to <M>G</M> via the
## <Ref Attr="UnderlyingGroup" Label="for tables of marks"/> value.
## Then it makes sense to use <A>tom</A> and its ordering of conjugacy
## classes of subgroups of <M>G</M> for storing information for constructing
## representatives of these classes.
## The group <M>G</M> is in general not sufficient for this,
## <A>tom</A> needs more information;
## this is available if and only if the <Ref Filt="IsTableOfMarksWithGens"/>
## value of <A>tom</A> is <K>true</K>.
## In this case, <Ref Oper="RepresentativeTom"/> can be used
## to get a subgroup of the <M>i</M>-th class, for all <M>i</M>.
## <P/>
## &GAP; provides two different possibilities to store generators of the
## representatives of classes of subgroups.
## The first is implemented by the attribute
--> --------------------
--> maximum size reached
--> --------------------
[ Verzeichnis aufwärts0.54unsichere Verbindung
Übersetzung europäischer Sprachen durch Browser
]
|
