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&nbsp;<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&nbsp;<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