1#############################################################################
2##
3##  This file is part of GAP, a system for computational discrete algebra.
4##  This file's authors include Frank Celler.
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 generic methods for  groups  defined by rewriting
12##  systems.
13##
14
15
16#############################################################################
17##
18#M  ElementByRws( <fam>, <elm> )
19##
20InstallMethod( ElementByRws,
21    true,
22    [ IsElementsFamilyByRws, IsObject ],
23    0,
24
25function( fam, elm )
26    elm := Immutable([ elm ]);
27    return Objectify( fam!.defaultType, elm );
28end );
29
30##
31##  Some collectors,  for example a Deep Thought  collector, store the
32##  rhs of conjugate and power relations as generators exponent lists.
33##  If ElementByRws() is called for those rhs, we need to convert them
34##  first to words in the appropriate free group.
35##
36InstallMethod( ElementByRws,
37    true,
38    [ IsElementsFamilyByRws, IsList ],
39    0,
40
41function( fam, list )
42    local  elm, freefam;
43
44    freefam := UnderlyingFamily( fam!.rewritingSystem );
45    elm := ObjByExtRep( freefam, list );
46    elm := Immutable([ elm ]);
47    return Objectify( fam!.defaultType, elm );
48end );
49
50
51#############################################################################
52##
53#M  PrintObj( <elm-by-rws> )
54##
55InstallMethod( PrintObj,
56    true,
57    [ IsMultiplicativeElementWithInverseByRws and IsPackedElementDefaultRep ],
58    0,
59
60function( obj )
61    Print( obj![1] );
62end );
63
64
65#############################################################################
66##
67#M  UnderlyingElement( <elm-by-rws> )
68##
69InstallMethod( UnderlyingElement,
70    true,
71    [ IsMultiplicativeElementWithInverseByRws and IsPackedElementDefaultRep ],
72    0,
73
74function( obj )
75    return obj![1];
76end );
77
78
79#############################################################################
80##
81#M  ExtRepOfObj( <elm-by-rws> )
82##
83InstallMethod( ExtRepOfObj,
84    true,
85    [ IsMultiplicativeElementWithInverseByRws ],
86    0,
87
88function( obj )
89    return ExtRepOfObj( UnderlyingElement( obj ) );
90end );
91
92
93#############################################################################
94##
95
96#M  Comm( <elm-by-rws>, <elm-by-rws> )
97##
98InstallMethod( Comm,
99    "rws-element, rws-element",
100    IsIdenticalObj,
101    [ IsMultiplicativeElementWithInverseByRws,
102      IsMultiplicativeElementWithInverseByRws ],
103    0,
104
105function( left, right )
106    local   fam;
107
108    fam := FamilyObj(left);
109    return ElementByRws( fam, ReducedComm( fam!.rewritingSystem,
110        UnderlyingElement(left), UnderlyingElement(right) ) );
111end );
112
113
114#############################################################################
115##
116#M  InverseOp( <elm-by-rws> )
117##
118InstallMethod( InverseOp,
119    "rws-element",
120    true,
121    [ IsMultiplicativeElementWithInverseByRws ],
122    0,
123
124function( obj )
125    local   fam;
126
127    fam := FamilyObj(obj);
128    return ElementByRws( fam, ReducedInverse( fam!.rewritingSystem,
129        UnderlyingElement(obj) ) );
130end );
131
132
133#############################################################################
134##
135#M  LeftQuotient( <elm-by-rws>, <elm-by-rws> )
136##
137InstallMethod( LeftQuotient,
138    "rws-element, rws-element",
139    IsIdenticalObj,
140    [ IsMultiplicativeElementWithInverseByRws,
141      IsMultiplicativeElementWithInverseByRws ],
142    0,
143
144function( left, right )
145    local   fam;
146
147    fam := FamilyObj(left);
148    return ElementByRws( fam, ReducedLeftQuotient( fam!.rewritingSystem,
149        UnderlyingElement(left), UnderlyingElement(right) ) );
150end );
151
152
153#############################################################################
154##
155#M  OneOp( <elm-by-rws> )
156##
157InstallMethod( OneOp,
158    "rws-element",
159    true,
160    [ IsMultiplicativeElementWithInverseByRws ],
161    0,
162
163function( obj )
164    local   fam;
165
166    fam := FamilyObj(obj);
167    return ElementByRws( fam, ReducedOne(fam!.rewritingSystem) );
168end );
169
170
171#############################################################################
172##
173#M  Quotient( <elm-by-rws>, <elm-by-rws> )
174##
175InstallMethod( \/,
176    "rws-element, rws-element",
177    IsIdenticalObj,
178    [ IsMultiplicativeElementWithInverseByRws,
179      IsMultiplicativeElementWithInverseByRws ],
180    0,
181
182function( left, right )
183    local   fam;
184
185    fam := FamilyObj(left);
186    return ElementByRws( fam, ReducedQuotient( fam!.rewritingSystem,
187        UnderlyingElement(left), UnderlyingElement(right) ) );
188end );
189
190
191#############################################################################
192##
193#M  <elm-by-rws> * <elm-by-rws>
194##
195InstallMethod( \*,
196    "rws-element * rws-element",
197    IsIdenticalObj,
198    [ IsMultiplicativeElementWithInverseByRws,
199      IsMultiplicativeElementWithInverseByRws ],
200    0,
201
202function( left, right )
203    local   fam;
204
205    fam := FamilyObj(left);
206    return ElementByRws( fam, ReducedProduct( fam!.rewritingSystem,
207        UnderlyingElement(left), UnderlyingElement(right) ) );
208end );
209
210
211#############################################################################
212##
213#M  <elm-by-rws> ^ <elm-by-rws>
214##
215InstallMethod( \^,
216    "rws-element ^ rws-element",
217    IsIdenticalObj,
218    [ IsMultiplicativeElementWithInverseByRws,
219      IsMultiplicativeElementWithInverseByRws ],
220    0,
221
222function( left, right )
223    local   fam;
224
225    fam := FamilyObj(left);
226    return ElementByRws( fam, ReducedConjugate( fam!.rewritingSystem,
227        UnderlyingElement(left), UnderlyingElement(right) ) );
228end );
229
230
231#############################################################################
232##
233#M  <elm-by-rws> ^ <int>
234##
235InstallMethod( \^,
236    "rws-element ^ int",
237    IsIdenticalObj,
238    [ IsMultiplicativeElementWithInverseByRws,
239      IsInt ],
240    0,
241
242function( left, right )
243    local   fam;
244
245    fam := FamilyObj(left);
246    return ElementByRws( fam, ReducedPower( fam!.rewritingSystem,
247        UnderlyingElement(left), right ) );
248end );
249
250
251#############################################################################
252##
253#M  <elm-by-rws> = <elm-by-rws>
254##
255InstallMethod( \=,
256    IsIdenticalObj,
257    [ IsMultiplicativeElementWithInverseByRws,
258      IsMultiplicativeElementWithInverseByRws ],
259    0,
260
261function( left, right )
262    return UnderlyingElement(left) = UnderlyingElement(right);
263end );
264
265
266#############################################################################
267##
268#M  <elm-by-rws> < <elm-by-rws>
269##
270InstallMethod( \<,
271    IsIdenticalObj,
272    [ IsMultiplicativeElementWithInverseByRws,
273      IsMultiplicativeElementWithInverseByRws ],
274    0,
275
276function( left, right )
277    return UnderlyingElement(left) < UnderlyingElement(right);
278end );
279
280
281#############################################################################
282##
283
284#M  MultiplicativeElementsWithInversesFamilyByRws( <rws> )
285##
286InstallMethod( MultiplicativeElementsWithInversesFamilyByRws,
287    true,
288    [ IsRewritingSystem and IsBuiltFromGroup ],
289    0,
290
291function( rws )
292    local   fam;
293
294    # create a new family in the category <IsElementsFamilyByRws>
295    fam := NewFamily(
296        "MultiplicativeElementsWithInversesFamilyByRws(...)",
297        IsMultiplicativeElementWithInverseByRws
298          and IsAssociativeElement,
299        IsElementsFamilyByRws );
300
301    # store the rewriting system
302    fam!.rewritingSystem := Immutable(rws);
303
304    # create the default type for the elements
305    fam!.defaultType := NewType( fam, IsPackedElementDefaultRep );
306
307    # that's it
308    return fam;
309
310end );
311
312
313
314#############################################################################
315##
316
317#M  GroupByRws( <rws> )
318##
319InstallMethod( GroupByRws,
320    true,
321    [ IsRewritingSystem and IsBuiltFromGroup ],
322    0,
323
324function( rws )
325
326    # it must be confluent
327    if not IsConfluent(rws)  then
328        Error( "the rewriting system must be confluent" );
329    fi;
330
331    # use the no-check to do the work
332    return GroupByRwsNC(rws);
333end );
334
335
336#############################################################################
337##
338#M  GroupByRwsNC( <rws> )
339##
340InstallMethod( GroupByRwsNC,"rewriting system", true,
341    [ IsRewritingSystem and IsBuiltFromGroup ], 100,
342
343function( rws )
344    local   pows,conjs,fam,  gens,  g,  id,  grp,defpcgs,i;
345
346    # give the rewriting system a chance to optimise itself
347    ReduceRules(rws);
348
349    # construct a new family containing the group elements
350    fam := MultiplicativeElementsWithInversesFamilyByRws(rws);
351
352    # construct the generators
353    gens := [];
354    for g  in GeneratorsOfRws(rws)  do
355        Add( gens, ElementByRws( fam, ReducedForm( rws, g ) ) );
356    od;
357    id := ElementByRws( fam, ReducedOne(rws) );
358
359    # and a group
360    grp := GroupByGenerators( gens, id );
361
362    # it is the whole family
363    SetIsWholeFamily( grp, true );
364
365    # check the true methods
366    if HasIsFinite( rws ) then
367      SetIsFinite( grp, IsFinite( rws ) );
368    fi;
369    if IsPolycyclicCollector( rws ) then
370      defpcgs:=DefiningPcgs( ElementsFamily(FamilyObj(grp)) );
371      SetFamilyPcgs( grp, defpcgs);
372      SetHomePcgs( grp, defpcgs);
373      SetGroupOfPcgs(defpcgs,grp);
374      if HasIsFiniteOrdersPcgs(defpcgs) and IsFiniteOrdersPcgs(defpcgs) then
375        SetSize(grp,Product(RelativeOrders(defpcgs)));
376        if HasRelativeOrders(rws)
377           and not ForAll(RelativeOrders(rws),IsPrimeInt) then
378           Info(InfoWarning,1,
379            "You are creating a Pc group with non-prime relative orders.");
380           Info(InfoWarning,1,
381            "Many algorithms require prime relative orders.");
382           Info(InfoWarning,1,"Use `RefinedPcGroup' to convert.");
383        fi;
384      fi;
385
386      if IsSingleCollectorRep(rws) then
387        pows:=rws![SCP_POWERS];
388        conjs:=rws![SCP_CONJUGATES];
389        for i in [1..Length(pows)] do
390          if IsBound(pows[i]) then
391            # this certainly could be done better, if one knew more about rws
392            # than I do. AH
393            defpcgs!.powers[i]:=ExponentsOfPcElement(defpcgs,
394                                  ElementByRws(fam,pows[i]));
395          else
396            defpcgs!.powers[i]:=defpcgs!.zeroVector;
397          fi;
398        od;
399        for pows in [1..Length(conjs)] do
400          for i in [1..Length(conjs[pows])] do
401            if IsBound(conjs[pows][i]) then
402            # this certainly could be done better, if one knew more about rws
403            # than I do. AH
404              defpcgs!.conjugates[pows][i]:=ExponentsOfPcElement(defpcgs,
405                                              ElementByRws(fam,conjs[pows][i]));
406            else
407              defpcgs!.conjugates[pows][i]:=ExponentsOfPcElement(defpcgs,
408                                              defpcgs[pows]);
409            fi;
410          od;
411        od;
412      fi;
413
414    fi;
415
416    # that's it
417    return grp;
418
419end );
420