1############################################################################# 2## 3## This file is part of GAP, a system for computational discrete algebra. 4## This file's authors include Heiko Theißen. 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 12 13############################################################################# 14## 15#V InfoBckt 16## 17## <#GAPDoc Label="InfoBckt"> 18## <ManSection> 19## <InfoClass Name="InfoBckt"/> 20## 21## <Description> 22## is the info class for the partition backtrack routines. 23## </Description> 24## </ManSection> 25## <#/GAPDoc> 26## 27DeclareInfoClass( "InfoBckt" ); 28 29DeclareGlobalFunction( "UnslicedPerm@" ); 30DeclareGlobalFunction( "PreImageWord" ); 31DeclareGlobalFunction( "ExtendedT" ); 32DeclareGlobalFunction( "MeetPartitionStrat" ); 33DeclareGlobalFunction( "MeetPartitionStratCell" ); 34DeclareGlobalFunction( "StratMeetPartition" ); 35DeclareGlobalFunction( "Suborbits" ); 36DeclareGlobalFunction( "OrbitalPartition" ); 37DeclareGlobalFunction( "EmptyRBase" ); 38DeclareGlobalFunction( "IsTrivialRBase" ); 39DeclareGlobalFunction( "AddRefinement" ); 40DeclareGlobalFunction( "ProcessFixpoint" ); 41DeclareGlobalFunction( "RegisterRBasePoint" ); 42DeclareGlobalFunction( "NextRBasePoint" ); 43DeclareGlobalFunction( "RRefine" ); 44DeclareGlobalFunction( "PBIsMinimal" ); 45DeclareGlobalFunction( "SubtractBlistOrbitStabChain" ); 46DeclareGlobalFunction( "PartitionBacktrack" ); 47 48DeclareGlobalFunction("SuboLiBli"); 49DeclareGlobalFunction("SuboSiBli"); 50DeclareGlobalFunction("SuboTruePos"); 51DeclareGlobalFunction("SuboUniteBlist"); 52DeclareGlobalFunction("ConcatSubos"); 53 54DeclareGlobalFunction("Refinements_ProcessFixpoint"); 55DeclareGlobalFunction("Refinements_Intersection"); 56DeclareGlobalFunction("Refinements_Centralizer"); 57DeclareGlobalFunction("Refinements__MakeBlox"); 58DeclareGlobalFunction("Refinements_SplitOffBlock"); 59DeclareGlobalFunction("Refinements__RegularOrbit1"); 60DeclareGlobalFunction("Refinements_RegularOrbit2"); 61DeclareGlobalFunction("Refinements_RegularOrbit3"); 62DeclareGlobalFunction("Refinements_Suborbits0"); 63DeclareGlobalFunction("Refinements_Suborbits1"); 64DeclareGlobalFunction("Refinements_Suborbits2"); 65DeclareGlobalFunction("Refinements_Suborbits3"); 66DeclareGlobalFunction("Refinements_TwoClosure"); 67 68 69DeclareGlobalVariable( "Refinements" ); 70 71DeclareGlobalFunction( "NextLevelRegularGroups" ); 72DeclareGlobalFunction( "RBaseGroupsBloxPermGroup" ); 73DeclareGlobalFunction( "RepOpSetsPermGroup" ); 74DeclareGlobalFunction( "RepOpElmTuplesPermGroup" ); 75DeclareGlobalFunction( "ConjugatorPermGroup" ); 76DeclareGlobalFunction( "NormalizerPermGroup" ); 77 78 79############################################################################# 80## 81#F ElementProperty( <G>, <Pr>[, <L>[, <R>]] ) one element with property 82## 83## <#GAPDoc Label="ElementProperty"> 84## <ManSection> 85## <Func Name="ElementProperty" Arg='G, Pr[, L[, R]]'/> 86## 87## <Description> 88## <Ref Func="ElementProperty"/> returns an element <M>\pi</M> of the 89## permutation group <A>G</A> such that the one-argument function <A>Pr</A> 90## returns <K>true</K> for <M>\pi</M>. 91## It returns <K>fail</K> if no such element exists in <A>G</A>. 92## The optional arguments <A>L</A> and <A>R</A> are subgroups of <A>G</A> 93## such that the property <A>Pr</A> has the same value for all elements in 94## the cosets <A>L</A> <M>g</M> and <M>g</M> <A>R</A>, respectively, 95## with <M>g \in <A>G</A></M>. 96## <P/> 97## A typical example of using the optional subgroups <A>L</A> and <A>R</A> 98## is the conjugacy test for elements <M>a</M> and <M>b</M> for which one 99## can set <A>L</A><M>:= C_{<A>G</A>}(a)</M> and 100## <A>R</A><M>:= C_{<A>G</A>}(b)</M>. 101## <P/> 102## <Example><![CDATA[ 103## gap> propfun:= el -> (1,2,3)^el in [ (1,2,3), (1,3,2) ];; 104## gap> SubgroupProperty( g, propfun, Subgroup( g, [ (1,2,3) ] ) ); 105## Group([ (1,2,3), (2,3) ]) 106## gap> ElementProperty( g, el -> Order( el ) = 2 ); 107## (2,4) 108## ]]></Example> 109## <P/> 110## Chapter <Ref Chap="Permutations"/> describes special operations to 111## construct permutations in the symmetric group without using backtrack 112## constructions. 113## <P/> 114## Backtrack routines are also called by the methods for permutation groups 115## that compute centralizers, normalizers, intersections, 116## conjugating elements as well as stabilizers for the operations of a 117## permutation group via <Ref Func="OnPoints"/>, <Ref Func="OnSets"/>, 118## <Ref Func="OnTuples"/> and <Ref Func="OnSetsSets"/>. 119## Some of these methods use more specific refinements than 120## <Ref Func="SubgroupProperty"/> or <Ref Func="ElementProperty"/>. 121## For the definition of refinements, and how one can define refinements, 122## see Section <Ref Sect="The General Backtrack Algorithm with Ordered Partitions"/>. 123## </Description> 124## </ManSection> 125## <#/GAPDoc> 126## 127DeclareGlobalFunction( "ElementProperty" ); 128 129 130############################################################################# 131## 132#F SubgroupProperty( <G>, <Pr>[, <L> ] ) . . . . . . . . fulfilling subgroup 133## 134## <#GAPDoc Label="SubgroupProperty"> 135## <ManSection> 136## <Func Name="SubgroupProperty" Arg='G, Pr[, L ]'/> 137## 138## <Description> 139## <A>Pr</A> must be a one-argument function that returns <K>true</K> or 140## <K>false</K> for elements of the group <A>G</A>, 141## and the subset of elements of <A>G</A> that fulfill <A>Pr</A> must 142## be a subgroup. (<E>If the latter is not true the result of this operation 143## is unpredictable!</E>) This command computes this subgroup. 144## The optional argument <A>L</A> must be a subgroup of the set of all 145## elements in <A>G</A> fulfilling <A>Pr</A> and can be given if known 146## in order to speed up the calculation. 147## </Description> 148## </ManSection> 149## <#/GAPDoc> 150## 151DeclareGlobalFunction( "SubgroupProperty" ); 152 153 154############################################################################# 155## 156#O PartitionStabilizerPermGroup( <G>, <part> ) 157## 158## <ManSection> 159## <Oper Name="PartitionStabilizerPermGroup" Arg='G, part'/> 160## 161## <Description> 162## <A>part</A> must be a list of pairwise disjoint sets of points 163## on which the permutation group <A>G</A> acts via <C>OnPoints</C>. 164## This function computes the stabilizer in <A>G</A> of <A>part</A>, that is, 165## the subgroup of all those elements in <A>G</A> that map each set in <A>part</A> 166## onto a set in <A>part</A>, via <C>OnSets</C>. 167## </Description> 168## </ManSection> 169## 170DeclareGlobalFunction( "PartitionStabilizerPermGroup" ); 171 172 173############################################################################# 174## 175#A TwoClosure( <G> ) 176## 177## <#GAPDoc Label="TwoClosure"> 178## <ManSection> 179## <Attr Name="TwoClosure" Arg='G'/> 180## 181## <Description> 182## The <E>2-closure</E> of a transitive permutation group <A>G</A> on 183## <M>n</M> points is the largest subgroup of the symmetric group <M>S_n</M> 184## which has the same orbits on sets of ordered pairs of points as the group 185## <A>G</A> has. 186## It also can be interpreted as the stabilizer of the orbital graphs of 187## <A>G</A>. 188## <Example><![CDATA[ 189## gap> TwoClosure(Group((1,2,3),(2,3,4))); 190## Sym( [ 1 .. 4 ] ) 191## ]]></Example> 192## </Description> 193## </ManSection> 194## <#/GAPDoc> 195## 196DeclareAttribute( "TwoClosure", IsPermGroup ); 197