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