1############################################################################# 2## 3## This file is part of GAP, a system for computational discrete algebra. 4## This file's authors include Alexander Hulpke. 5## 6## Copyright of GAP belongs to its developers, whose names are too numerous 7## to list here. Please refer to the COPYRIGHT file for details. 8## 9## SPDX-License-Identifier: GPL-2.0-or-later 10## 11## This file contains the declarations of operations for cosets. 12## 13 14############################################################################# 15## 16#V InfoCoset 17## 18## <#GAPDoc Label="InfoCoset"> 19## <ManSection> 20## <InfoClass Name="InfoCoset"/> 21## 22## <Description> 23## The information function for coset and double coset operations is 24## <Ref InfoClass="InfoCoset"/>. 25## </Description> 26## </ManSection> 27## <#/GAPDoc> 28## 29DeclareInfoClass("InfoCoset"); 30 31############################################################################# 32## 33#F AscendingChain( <G>, <U> ) . chain of subgroups G = G_1 > ... > G_n = U 34## 35## <#GAPDoc Label="AscendingChain"> 36## <ManSection> 37## <Func Name="AscendingChain" Arg='G, U'/> 38## 39## <Description> 40## This function computes an ascending chain of subgroups from <A>U</A> to 41## <A>G</A>. 42## This chain is given as a list whose first entry is <A>U</A> and the last 43## entry is <A>G</A>. 44## The function tries to make the links in this chain small. 45## <P/> 46## The option <C>refineIndex</C> can be used to give a bound for refinements 47## of steps to avoid &GAP; trying to enforce too small steps. 48## The option <C>cheap</C> (if set to <K>true</K>) will overall limit the 49## amount of heuristic searches. 50## </Description> 51## </ManSection> 52## <#/GAPDoc> 53## 54DeclareGlobalFunction("AscendingChain"); 55 56############################################################################# 57## 58#O AscendingChainOp(<G>,<U>) chain of subgroups 59## 60## <ManSection> 61## <Oper Name="AscendingChainOp" Arg='G,U'/> 62## 63## <Description> 64## This operation does the actual work of computing ascending chains. It 65## gets called from <C>AscendingChain</C> if no chain is found stored in 66## <C>ComputedAscendingChains</C>. 67## </Description> 68## </ManSection> 69## 70DeclareOperation("AscendingChainOp",[IsGroup,IsGroup]); 71 72############################################################################# 73## 74#A ComputedAscendingChains(<U>) list of already computed ascending chains 75## 76## <ManSection> 77## <Attr Name="ComputedAscendingChains" Arg='U'/> 78## 79## <Description> 80## This attribute stores ascending chains. It is a list whose entries are 81## of the form [<A>G</A>,<A>chain</A>] where <A>chain</A> is an ascending chain from <A>U</A> up 82## to <A>G</A>. This storage is used by <C>AscendingChain</C> to avoid duplicate 83## calculations. 84## </Description> 85## </ManSection> 86## 87DeclareAttribute("ComputedAscendingChains",IsGroup, 88 "mutable"); 89 90############################################################################# 91## 92#F RefinedChain(<G>,<c>) . . . . . . . . . . . . . . . . refine chain links 93## 94## <ManSection> 95## <Func Name="RefinedChain" Arg='G,c'/> 96## 97## <Description> 98## <A>c</A> is an ascending chain in the Group <A>G</A>. The task of this routine is 99## to refine <A>c</A>, i.e., if there is a "link" <M>U>L</M> in <A>c</A> with <M>[U:L]</M> too big, 100## this procedure tries to find subgroups <M>G_0,...,G_n</M> of <A>G</A>; such that 101## <M>U=G_0>...>G_n=L</M>. This is done by extending L inductively: Since normal 102## steps can help in further calculations, the routine first tries to 103## extend to the normalizer in U. If the subgroup is self-normalizing, 104## the group is extended via a random element. If this results in a step 105## too big, it is repeated several times to find hopefully a small 106## extension! 107## <P/> 108## The option <C>refineIndex</C> can be used to tell &GAP; that a specified 109## step index is good enough. The option <C>refineChainActionLimit</C> can be 110## used to give an upper limit up to which index guaranteed refinement 111## should be tried. 112## </Description> 113## </ManSection> 114## 115DeclareGlobalFunction("RefinedChain"); 116 117############################################################################# 118## 119#O CanonicalRightCosetElement( U, g ) canonical representative of U*g 120## 121## <#GAPDoc Label="CanonicalRightCosetElement"> 122## <ManSection> 123## <Oper Name="CanonicalRightCosetElement" Arg='U, g'/> 124## 125## <Description> 126## returns a <Q>canonical</Q> representative of the right coset 127## <A>U</A> <A>g</A> 128## which is independent of the given representative <A>g</A>. 129## This can be used to compare cosets by comparing their canonical 130## representatives. 131## <P/> 132## The representative chosen to be the <Q>canonical</Q> one 133## is representation dependent and only guaranteed to remain the same 134## within one &GAP; session. 135## <Example><![CDATA[ 136## gap> CanonicalRightCosetElement(u,(2,4,3)); 137## (3,4) 138## ]]></Example> 139## </Description> 140## </ManSection> 141## <#/GAPDoc> 142## 143DeclareOperation("CanonicalRightCosetElement", 144 [IsGroup,IsObject]); 145 146############################################################################# 147## 148#C IsDoubleCoset(<obj>) 149## 150## <#GAPDoc Label="IsDoubleCoset"> 151## <ManSection> 152## <Filt Name="IsDoubleCoset" Arg='obj' Type='Category' Label="operation"/> 153## 154## <Description> 155## The category of double cosets. 156## </Description> 157## </ManSection> 158## <#/GAPDoc> 159## 160DeclareCategory("IsDoubleCoset", 161 IsDomain and IsExtLSet and IsExtRSet); 162 163############################################################################# 164## 165#A LeftActingGroup(<dcos>) 166#A RightActingGroup(<dcos>) 167## 168## <ManSection> 169## <Attr Name="LeftActingGroup" Arg='dcos'/> 170## <Attr Name="RightActingGroup" Arg='dcos'/> 171## 172## <Description> 173## return the two groups that define a double coset <A>dcos</A>. 174## </Description> 175## </ManSection> 176## 177DeclareAttribute("LeftActingGroup",IsDoubleCoset); 178DeclareAttribute("RightActingGroup",IsDoubleCoset); 179 180############################################################################# 181## 182#O DoubleCoset(<U>,<g>,<V>) 183## 184## <#GAPDoc Label="DoubleCoset"> 185## <ManSection> 186## <Oper Name="DoubleCoset" Arg='U, g, V'/> 187## 188## <Description> 189## The groups <A>U</A> and <A>V</A> must be subgroups of a common supergroup 190## <A>G</A> of which <A>g</A> is an element. 191## This command constructs the double coset <A>U</A> <A>g</A> <A>V</A> 192## which is the set of all elements of the form <M>ugv</M> for any 193## <M>u \in <A>U</A></M>, <M>v \in <A>V</A></M>. 194## For element operations such as <K>in</K>, a double coset behaves 195## like a set of group elements. The double coset stores <A>U</A> in the 196## attribute <C>LeftActingGroup</C>, 197## <A>g</A> as <Ref Attr="Representative"/>, 198## and <A>V</A> as <C>RightActingGroup</C>. 199## </Description> 200## </ManSection> 201## <#/GAPDoc> 202## 203DeclareOperation("DoubleCoset",[IsGroup,IsObject,IsGroup]); 204 205############################################################################# 206## 207#O DoubleCosets(<G>,<U>,<V>) 208#O DoubleCosetsNC(<G>,<U>,<V>) 209## 210## <#GAPDoc Label="DoubleCosets"> 211## <ManSection> 212## <Func Name="DoubleCosets" Arg='G, U, V'/> 213## <Oper Name="DoubleCosetsNC" Arg='G, U, V'/> 214## 215## <Description> 216## computes a duplicate free list of all double cosets 217## <A>U</A> <M>g</M> <A>V</A> for <M>g \in <A>G</A></M>. 218## The groups <A>U</A> and <A>V</A> must be subgroups of the group <A>G</A>. 219## The <C>NC</C> version does not check whether <A>U</A> and <A>V</A> are 220## subgroups of <A>G</A>. 221## <Example><![CDATA[ 222## gap> dc:=DoubleCosets(g,u,v); 223## [ DoubleCoset(Group( [ (1,2,3), (1,2) ] ),(),Group( [ (3,4) ] )), 224## DoubleCoset(Group( [ (1,2,3), (1,2) ] ),(1,3)(2,4),Group( 225## [ (3,4) ] )), DoubleCoset(Group( [ (1,2,3), (1,2) ] ),(1,4) 226## (2,3),Group( [ (3,4) ] )) ] 227## gap> List(dc,Representative); 228## [ (), (1,3)(2,4), (1,4)(2,3) ] 229## ]]></Example> 230## </Description> 231## </ManSection> 232## <#/GAPDoc> 233## 234DeclareGlobalFunction("DoubleCosets"); 235DeclareOperation("DoubleCosetsNC",[IsGroup,IsGroup,IsGroup]); 236 237############################################################################# 238## 239#O DoubleCosetRepsAndSizes(<G>,<U>,<V>) 240## 241## <#GAPDoc Label="DoubleCosetRepsAndSizes"> 242## <ManSection> 243## <Oper Name="DoubleCosetRepsAndSizes" Arg='G, U, V'/> 244## 245## <Description> 246## returns a list of double coset representatives and their sizes, 247## the entries are lists of the form <M>[ r, n ]</M> 248## where <M>r</M> and <M>n</M> are an element of the double coset and the 249## size of the coset, respectively. 250## This operation is faster than <Ref Oper="DoubleCosetsNC"/> because no 251## double coset objects have to be created. 252## <Example><![CDATA[ 253## gap> dc:=DoubleCosetRepsAndSizes(g,u,v); 254## [ [ (), 12 ], [ (1,3)(2,4), 6 ], [ (1,4)(2,3), 6 ] ] 255## ]]></Example> 256## </Description> 257## </ManSection> 258## <#/GAPDoc> 259## 260DeclareOperation("DoubleCosetRepsAndSizes",[IsGroup,IsGroup,IsGroup]); 261 262############################################################################# 263## 264#A RepresentativesContainedRightCosets(<D>) 265## 266## <#GAPDoc Label="RepresentativesContainedRightCosets"> 267## <ManSection> 268## <Attr Name="RepresentativesContainedRightCosets" Arg='D'/> 269## 270## <Description> 271## A double coset <M><A>D</A> = U g V</M> can be considered as a union of 272## right cosets <M>U h_i</M>. 273## (It is the union of the orbit of <M>U g</M> under right multiplication by 274## <M>V</M>.) 275## For a double coset <A>D</A> this function returns a set 276## of representatives <M>h_i</M> such that 277## <A>D</A> <M>= \bigcup_{{h_i}} U h_i</M>. 278## The representatives returned are canonical for <M>U</M> (see 279## <Ref Oper="CanonicalRightCosetElement"/>) and form a set. 280## <Example><![CDATA[ 281## gap> u:=Subgroup(g,[(1,2,3),(1,2)]);;v:=Subgroup(g,[(3,4)]);; 282## gap> c:=DoubleCoset(u,(2,4),v); 283## DoubleCoset(Group( [ (1,2,3), (1,2) ] ),(2,4),Group( [ (3,4) ] )) 284## gap> (1,2,3) in c; 285## false 286## gap> (2,3,4) in c; 287## true 288## gap> LeftActingGroup(c); 289## Group([ (1,2,3), (1,2) ]) 290## gap> RightActingGroup(c); 291## Group([ (3,4) ]) 292## gap> RepresentativesContainedRightCosets(c); 293## [ (2,3,4) ] 294## ]]></Example> 295## </Description> 296## </ManSection> 297## <#/GAPDoc> 298## 299DeclareAttribute( "RepresentativesContainedRightCosets", IsDoubleCoset ); 300 301############################################################################# 302## 303#C IsRightCoset(<obj>) 304## 305## <#GAPDoc Label="IsRightCoset"> 306## <ManSection> 307## <Filt Name="IsRightCoset" Arg='obj' Type='Category'/> 308## 309## <Description> 310## The category of right cosets. 311## <P/> 312## <Index>left cosets</Index> 313## &GAP; does not provide left cosets as a separate data type, but as the 314## left coset <M>gU</M> consists of exactly the inverses of the elements of 315## the right coset <M>Ug^{{-1}}</M> calculations with left cosets can be 316## emulated using right cosets by inverting the representatives. 317## </Description> 318## </ManSection> 319## <#/GAPDoc> 320## 321DeclareCategory("IsRightCoset", IsDomain and IsExternalOrbit and 322 IsMultiplicativeElementWithInverse); 323 324############################################################################# 325## 326#P IsBiCoset( <C> ) 327## 328## <#GAPDoc Label="IsBiCoset"> 329## <ManSection> 330## <Prop Name="IsBiCoset" Arg='C'/> 331## 332## <Description> 333## <Index>bicoset</Index> 334## A (right) coset <M>Ug</M> is considered a <E>bicoset</E> if its set of 335## elements simultaneously forms a left coset for the same subgroup. This is 336## the case if and only if the coset representative <M>g</M> normalizes the 337## subgroup <M>U</M>. 338## </Description> 339## </ManSection> 340## <#/GAPDoc> 341## 342DeclareProperty( "IsBiCoset", IsRightCoset ); 343 344############################################################################# 345## 346#O RightCoset( <U>, <g> ) 347## 348## <#GAPDoc Label="RightCoset"> 349## <ManSection> 350## <Oper Name="RightCoset" Arg='U, g'/> 351## 352## <Description> 353## returns the right coset of <A>U</A> with representative <A>g</A>, 354## which is the set of all elements of the form <M>ug</M> for all 355## <M>u \in <A>U</A></M>. <A>g</A> must be an 356## element of a larger group <A>G</A> which contains <A>U</A>. 357## For element operations such as <K>in</K> a right coset behaves like a set of 358## group elements. 359## <P/> 360## Right cosets are 361## external orbits for the action of <A>U</A> which acts via 362## <Ref Func="OnLeftInverse"/>. 363## Of course the action of a larger group <A>G</A> on right cosets is via 364## <Ref Func="OnRight"/>. 365## <Example><![CDATA[ 366## gap> u:=Group((1,2,3), (1,2));; 367## gap> c:=RightCoset(u,(2,3,4)); 368## RightCoset(Group( [ (1,2,3), (1,2) ] ),(2,3,4)) 369## gap> ActingDomain(c); 370## Group([ (1,2,3), (1,2) ]) 371## gap> Representative(c); 372## (2,3,4) 373## gap> Size(c); 374## 6 375## gap> AsList(c); 376## [ (2,3,4), (1,4,2), (1,3,4,2), (1,3)(2,4), (2,4), (1,4,2,3) ] 377## gap> IsBiCoset(c); 378## false 379## ]]></Example> 380## </Description> 381## </ManSection> 382## <#/GAPDoc> 383## 384DeclareOperation("RightCoset",[IsGroup,IsObject]); 385 386 387############################################################################# 388## 389#F RightCosets(<G>,<U>) 390#O RightCosetsNC(<G>,<U>) 391## 392## <#GAPDoc Label="RightCosets"> 393## <ManSection> 394## <Func Name="RightCosets" Arg='G, U'/> 395## <Oper Name="RightCosetsNC" Arg='G, U'/> 396## 397## <Description> 398## computes a duplicate free list of right cosets <A>U</A> <M>g</M> for 399## <M>g \in</M> <A>G</A>. 400## A set of representatives for the elements in this list forms a right 401## transversal of <A>U</A> in <A>G</A>. 402## (By inverting the representatives one obtains 403## a list of representatives of the left cosets of <A>U</A>.) 404## The <C>NC</C> version does not check whether <A>U</A> is a subgroup of 405## <A>G</A>. 406## <Example><![CDATA[ 407## gap> RightCosets(g,u); 408## [ RightCoset(Group( [ (1,2,3), (1,2) ] ),()), 409## RightCoset(Group( [ (1,2,3), (1,2) ] ),(1,3)(2,4)), 410## RightCoset(Group( [ (1,2,3), (1,2) ] ),(1,4)(2,3)), 411## RightCoset(Group( [ (1,2,3), (1,2) ] ),(1,2)(3,4)) ] 412## ]]></Example> 413## </Description> 414## </ManSection> 415## <#/GAPDoc> 416## 417DeclareGlobalFunction("RightCosets"); 418DeclareOperation("RightCosetsNC",[IsGroup,IsGroup]); 419 420############################################################################# 421## 422#F IntermediateGroup(<G>,<U>) . . . . . . . . . subgroup of G containing U 423## 424## <#GAPDoc Label="IntermediateGroup"> 425## <ManSection> 426## <Func Name="IntermediateGroup" Arg='G, U'/> 427## 428## <Description> 429## This routine tries to find a subgroup <M>E</M> of <A>G</A>, 430## such that <M><A>G</A> > E > <A>U</A></M> holds. 431## If <A>U</A> is maximal in <A>G</A>, the function returns <K>fail</K>. 432## This is done by finding minimal blocks for 433## the operation of <A>G</A> on the right cosets of <A>U</A>. 434## </Description> 435## </ManSection> 436## <#/GAPDoc> 437## 438DeclareGlobalFunction("IntermediateGroup"); 439 440# forward declaration for recursive call. 441DeclareGlobalFunction("DoConjugateInto"); 442 443