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