|
#############################################################################
##
## This file is part of GAP, a system for computational discrete algebra.
## This file's authors include Heiko Theißen.
##
## 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
##
#############################################################################
##
#C IsPermGroup( <obj> )
##
## <#GAPDoc Label="IsPermGroup">
## <ManSection>
## <Filt Name="IsPermGroup" Arg='obj' Type='Category'/>
##
## <Description>
## A permutation group is a group of permutations on a finite set
## <M>\Omega</M> of positive integers.
## &GAP; does <E>not</E> require the user to specify the operation domain
## <M>\Omega</M> when a permutation group is defined.
## <P/>
## <Example><![CDATA[
## gap> g:=Group((1,2,3,4),(1,2));
## Group([ (1,2,3,4), (1,2) ])
## ]]></Example>
## <P/>
## Permutation groups are groups and therefore all operations for groups
## (see Chapter <Ref Chap="Groups"/>) can be applied to them.
## In many cases special methods are installed for permutation groups
## that make computations more effective.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareSynonym( "IsPermGroup", IsGroup and IsPermCollection );
#############################################################################
##
#M IsSubsetLocallyFiniteGroup( <G> ) . . . . . . for magmas of permutations
##
#T Here we assume implicitly that all permutations are finitary!
#T (What would be a permutation with unbounded largest moved point?
#T Perhaps a permutation of possibly infinite order?)
##
InstallTrueMethod( IsSubsetLocallyFiniteGroup, IsPermCollection );
#############################################################################
##
#M CanEasilySortElements
##
InstallTrueMethod( CanEasilySortElements, IsPermGroup and IsFinite );
#############################################################################
##
#M KnowsHowToDecompose( <G> ) . . . . . . . . always true for perm. groups
##
InstallTrueMethod( KnowsHowToDecompose, IsPermGroup );
#############################################################################
##
#M IsGeneratorsOfMagmaWithInverses( <permcoll> ) . . . true for perm. colls.
##
InstallTrueMethod( IsGeneratorsOfMagmaWithInverses, IsPermCollection );
#############################################################################
##
#F MinimizeExplicitTransversal
##
## <ManSection>
## <Func Name="MinimizeExplicitTransversal" Arg='obj'/>
##
## <Description>
## </Description>
## </ManSection>
##
DeclareGlobalFunction( "MinimizeExplicitTransversal" );
#############################################################################
##
#F AddCosetInfoStabChain
##
## <ManSection>
## <Func Name="AddCosetInfoStabChain" Arg='obj'/>
##
## <Description>
## </Description>
## </ManSection>
##
DeclareGlobalFunction( "AddCosetInfoStabChain" );
#############################################################################
##
#F NumberCoset
#F CosetNumber
##
## <ManSection>
## <Func Name="NumberCoset" Arg='obj'/>
## <Func Name="CosetNumber" Arg='obj'/>
##
## <Description>
## </Description>
## </ManSection>
##
DeclareGlobalFunction( "NumberCoset" );
DeclareGlobalFunction( "CosetNumber" );
#############################################################################
##
#F IndependentGeneratorsAbelianPPermGroup
##
## <ManSection>
## <Func Name="IndependentGeneratorsAbelianPPermGroup" Arg='obj'/>
##
## <Description>
## </Description>
## </ManSection>
##
DeclareGlobalFunction( "IndependentGeneratorsAbelianPPermGroup" );
#############################################################################
##
#F OrbitPerms( <perms>, <pnt> )
##
## <#GAPDoc Label="OrbitPerms">
## <ManSection>
## <Func Name="OrbitPerms" Arg='perms, pnt'/>
##
## <Description>
## returns the orbit of the positive integer <A>pnt</A>
## under the group generated by the permutations in the list <A>perms</A>.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction( "OrbitPerms" );
#############################################################################
##
#F OrbitsPerms( <perms>, <D> )
##
## <#GAPDoc Label="OrbitsPerms">
## <ManSection>
## <Func Name="OrbitsPerms" Arg='perms, D'/>
##
## <Description>
## returns the list of orbits of the positive integers in the list <A>D</A>
## under the group generated by the permutations in the list <A>perms</A>.
## <Example><![CDATA[
## gap> OrbitPerms( [ (1,2,3)(4,5), (3,6) ], 1 );
## [ 1, 2, 3, 6 ]
## gap> OrbitsPerms( [ (1,2,3)(4,5), (3,6) ], [ 1 .. 6 ] );
## [ [ 1, 2, 3, 6 ], [ 4, 5 ] ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction( "OrbitsPerms" );
#############################################################################
##
#F SylowSubgroupPermGroup
##
## <ManSection>
## <Func Name="SylowSubgroupPermGroup" Arg='obj'/>
##
## <Description>
## </Description>
## </ManSection>
##
DeclareGlobalFunction( "SylowSubgroupPermGroup" );
#############################################################################
##
#F SignPermGroup
##
## <ManSection>
## <Func Name="SignPermGroup" Arg='obj'/>
##
## <Description>
## </Description>
## </ManSection>
##
DeclareGlobalFunction( "SignPermGroup" );
#############################################################################
##
#F CycleStructuresGroup
##
## <ManSection>
## <Func Name="CycleStructuresGroup" Arg='obj'/>
##
## <Description>
## </Description>
## </ManSection>
##
DeclareGlobalFunction( "CycleStructuresGroup" );
#############################################################################
##
#F ApproximateSuborbitsStabilizerPermGroup( <G>, <pnt> )
##
## <#GAPDoc Label="ApproximateSuborbitsStabilizerPermGroup">
## <ManSection>
## <Func Name="ApproximateSuborbitsStabilizerPermGroup" Arg='G, pnt'/>
##
## <Description>
## returns an approximation of the orbits of <C>Stabilizer( <A>G</A>, <A>pnt</A> )</C>
## on all points of the orbit <C>Orbit( <A>G</A>, <A>pnt</A> )</C>,
## without computing the full point stabilizer;
## As not all Schreier generators are used,
## the result may represent the orbits of only a subgroup of the point
## stabilizer.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction("ApproximateSuborbitsStabilizerPermGroup");
#############################################################################
##
#A AllBlocks( <G> )
##
## <#GAPDoc Label="AllBlocks">
## <ManSection>
## <Attr Name="AllBlocks" Arg='G'/>
##
## <Description>
## computes a list of representatives of all block systems for a
## permutation group <A>G</A> acting transitively on the points moved by the
## group.
## <P/>
## Each representative in the returned list is sorted and contains the
## smallest point moved by <A>G</A>.
## <P/>
## <Example><![CDATA[
## gap> AllBlocks(g);
## [ [ 1, 8 ], [ 1, 2, 3, 8 ], [ 1, 4, 5, 8 ], [ 1, 6, 7, 8 ], [ 1, 3 ],
## [ 1, 3, 5, 7 ], [ 1, 3, 4, 6 ], [ 1, 5 ], [ 1, 2, 5, 6 ], [ 1, 2 ],
## [ 1, 2, 4, 7 ], [ 1, 4 ], [ 1, 7 ], [ 1, 6 ] ]
## ]]></Example>
## <P/>
## The stabilizer of a block can be computed via the action
## <Ref Func="OnSets"/>:
## <P/>
## <Example><![CDATA[
## gap> Stabilizer(g,[1,8],OnSets);
## Group([ (1,8)(2,3)(4,5)(6,7) ])
## ]]></Example>
## <P/>
## If <C>bs</C> is a partition of the action domain, given as a set of sets,
## the stabilizer under the action <Ref Func="OnSetsDisjointSets"/> returns
## the largest subgroup which preserves <C>bs</C> as a block system.
## <P/>
## <Example><![CDATA[
## gap> g:=Group((1,2,3,4,5,6,7,8),(1,2));;
## gap> bs:=[[1,2,3,4],[5,6,7,8]];;
## gap> Stabilizer(g,bs,OnSetsDisjointSets);
## Group([ (6,7), (5,6), (5,8), (2,3), (3,4)(5,7), (1,4),
## (1,5,4,8)(2,6,3,7) ])
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "AllBlocks", IsPermGroup );
#############################################################################
##
#F TransitiveGroupsAvailable(<deg>)
##
## <ManSection>
## <Func Name="TransitiveGroupsAvailable" Arg='deg'/>
##
## <Description>
## To offer a clearer interface to the transitive groups library, this
## function checks whether the transitive groups of degree <A>deg</A> are
## available to load and will, if needed, load basic data structures for
## this degree.
## </Description>
## </ManSection>
##
DeclareGlobalFunction( "TransitiveGroupsAvailable" );
# dummy declarations to satisfy library references to transitive groups
# library
DeclareGlobalFunction( "NrTransitiveGroups" );
DeclareGlobalFunction( "TransitiveGroup" );
DeclareGlobalFunction( "TRANSProperties" );
#############################################################################
##
#A TransitiveIdentification( <G> )
##
## <#GAPDoc Label="TransitiveIdentification">
## <ManSection>
## <Attr Name="TransitiveIdentification" Arg='G'/>
##
## <Description>
## Let <A>G</A> be a permutation group, acting transitively on a set of up
## to 30 points.
## Then <Ref Func="TransitiveIdentification"/> will return the position of
## this group in the transitive groups library.
## This means, if <A>G</A> acts on <M>m</M> points and
## <Ref Func="TransitiveIdentification"/> returns <M>n</M>,
## then <A>G</A> is permutation isomorphic to the group
## <C>TransitiveGroup(m,n)</C>.
## <P/>
## Note: The points moved do <E>not</E> need to be [1..<A>n</A>], the group
## <M>\langle (2,3,4),(2,3) \rangle</M> is considered to be transitive on 3
## points. If the group has several orbits on the points moved by it the
## result of <Ref Func="TransitiveIdentification"/> is undefined.
## <Example><![CDATA[
## gap> TransitiveIdentification(Group((1,2),(1,2,3)));
## 2
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "TransitiveIdentification", IsPermGroup );
#############################################################################
##
#F PrimitiveGroupsAvailable(<deg>)
##
## <ManSection>
## <Func Name="PrimitiveGroupsAvailable" Arg='deg'/>
##
## <Description>
## To offer a clearer interface to the primitive groups library, this
## function checks whether the primitive groups of degree <A>deg</A> are
## available to load and will, if needed, load basic data structures for
## this degree.
## </Description>
## </ManSection>
##
DeclareGlobalFunction( "PrimitiveGroupsAvailable" );
#############################################################################
##
#A PrimitiveIdentification( <G> )
##
## <#GAPDoc Label="PrimitiveIdentification">
## <ManSection>
## <Attr Name="PrimitiveIdentification" Arg='G'/>
##
## <Description>
## For a primitive permutation group for which an <M>S_n</M>-conjugate exists in
## the library of primitive permutation groups
## (see <Ref Sect="Primitive Permutation Groups"/>),
## this attribute returns the index position. That is <A>G</A> is
## conjugate to
## <C>PrimitiveGroup(NrMovedPoints(<A>G</A>),PrimitiveIdentification(<A>G</A>))</C>.
## <P/>
## Methods only exist if the primitive groups library is installed.
## <P/>
## Note: As this function uses the primitive groups library, the result is
## only guaranteed to the same extent as this library. If it is incomplete,
## <C>PrimitiveIdentification</C> might return an existing index number for a
## group not in the library.
## <Example><![CDATA[
## gap> PrimitiveIdentification(Group((1,2),(1,2,3)));
## 2
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "PrimitiveIdentification", IsPermGroup );
#############################################################################
##
#A ONanScottType( <G> )
##
## <#GAPDoc Label="ONanScottType">
## <ManSection>
## <Attr Name="ONanScottType" Arg='G'/>
##
## <Description>
## returns the type of a primitive permutation group <A>G</A>,
## according to the O'Nan-Scott classification.
## The labelling of the different types is not consistent in the literature,
## we use the following identifications. The two-letter code given is the
## name of the type as used by Praeger.
## <List>
## <Mark>1</Mark>
## <Item>
## Affine. (HA)
## </Item>
## <Mark>2</Mark>
## <Item>
## Almost simple. (AS)
## </Item>
## <Mark>3a</Mark>
## <Item>
## Diagonal, Socle consists of two normal subgroups. (HS)
## </Item>
## <Mark>3b</Mark>
## <Item>
## Diagonal, Socle is minimal normal. (SD)
## </Item>
## <Mark>4a</Mark>
## <Item>
## Product action with the first factor primitive of type 3a. (HC)
## </Item>
## <Mark>4b</Mark>
## <Item>
## Product action with the first factor primitive of type 3b. (CD)
## </Item>
## <Mark>4c</Mark>
## <Item>
## Product action with the first factor primitive of type 2. (PA)
## </Item>
## <Mark>5</Mark>
## <Item>
## Twisted wreath product (TW)
## </Item>
## </List>
## See <Cite Key="EickHulpke01"/> for correspondence to other labellings used
## in the literature.
## As it can contain letters, the type is returned as a string.
## <P/>
## If <A>G</A> is not a permutation group or does not act primitively on the
## points moved by it, the result is undefined.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "ONanScottType", IsPermGroup );
#############################################################################
##
#A SocleTypePrimitiveGroup( <G> )
##
## <#GAPDoc Label="SocleTypePrimitiveGroup">
## <ManSection>
## <Attr Name="SocleTypePrimitiveGroup" Arg='G'/>
##
## <Description>
## returns the socle type of the primitive permutation group <A>G</A>.
## The socle of a primitive group is the direct product of isomorphic simple
## groups,
## therefore the type is indicated by a record with components
## <C>series</C>, <C>parameter</C> (both as described under
## <Ref Attr="IsomorphismTypeInfoFiniteSimpleGroup" Label="for a group"/>),
## and <C>width</C> for the number of direct factors.
## <P/>
## If <A>G</A> does not act primitively on its moved points, an error is returned.
## <Example><![CDATA[
## gap> g:=AlternatingGroup(5);;
## gap> h:=DirectProduct(g,g);;
## gap> p:=List([1,2],i->Projection(h,i));;
## gap> ac:=Action(h,AsList(g),
## > function(g,h) return Image(p[1],h)^-1*g*Image(p[2],h);end);;
## gap> Size(ac);NrMovedPoints(ac);IsPrimitive(ac,[1..60]);
## 3600
## 60
## true
## gap> ONanScottType(ac);
## "3a"
## gap> SocleTypePrimitiveGroup(ac);
## rec(
## name := "A(5) ~ A(1,4) = L(2,4) ~ B(1,4) = O(3,4) ~ C(1,4) = S(2,4) \
## ~ 2A(1,4) = U(2,4) ~ A(1,5) = L(2,5) ~ B(1,5) = O(3,5) ~ C(1,5) = S(2,\
## 5) ~ 2A(1,5) = U(2,5)", parameter := 5, series := "A", width := 2 )
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "SocleTypePrimitiveGroup", IsPermGroup );
#############################################################################
##
#F DiagonalSocleAction( <grp>,<n> )
##
## <ManSection>
## <Func Name="DiagonalSocleAction" Arg='grp,n'/>
##
## <Description>
## returns the direct product of <A>n</A> copied of <A>grp</A> in diagonal action.
## </Description>
## </ManSection>
##
DeclareGlobalFunction( "DiagonalSocleAction" );
#############################################################################
##
#F ReducedPermdegree( <g> )
##
## <ManSection>
## <Func Name="ReducedPermdegree" Arg='g'/>
##
## <Description>
## This functions tries to find cheaply a smaller domain on which the
## permutation group <A>g</A> acts faithfully. It returns a monomorphism from
## <A>g</A> onto an isomorphic group of smaller degree or <K>fail</K> if no such
## domain is found.
## <P/>
## In contrast to <C>SmallerDegreePermutationRepresentation</C> little effort
## is spent on fincting completely different actions. The degree obtained
## by <C>ReducedPermdegree</C> therefore in general is not that small, on the
## other hand <C>ReducedPermdegree</C> works fast enough (and returns a
## sufficiently well-behaved homomorphism) that it can be used within other
## routines.
## </Description>
## </ManSection>
##
DeclareGlobalFunction( "ReducedPermdegree" );
DeclareGlobalFunction("MovedPointsPerms");
#############################################################################
##
#A OrbitsMovedPoints( <G> )
##
## <#GAPDoc Label="OrbitsMovedPoints">
## <ManSection>
## <Attr Name="OrbitsMovedPoints" Arg='G'/>
##
## <Description>
## For a permutation group <A>G</A>, this attribute returns the orbits on the points moved
## as a set of sets.
## <Example><![CDATA[
## gap> OrbitsMovedPoints(Group((9,5),(7,3,2)));
## [ [ 2, 3, 7 ], [ 5, 9 ] ]
## ]]></Example>
## <P/>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "OrbitsMovedPoints", IsPermGroup );
#############################################################################
##
#F LogPerm( <a>, <b> )
##
## <ManSection>
## <Func Name="LogPerm" Arg='a,b'/>
##
## <Description>
## For two permutations <A>a</A> and <A>b</A> this function returns a
## positive integer <A>e</A> such that <A>a^e=b</A>, or <K>false</A> if no such
## element exists.
## </Description>
## </ManSection>
##
DeclareGlobalFunction("LogPerm");
# use for pcgs conversion
DeclareGlobalFunction("CreateIsomorphicPcGroup");
[ Dauer der Verarbeitung: 0.34 Sekunden
(vorverarbeitet)
]
|
