1############################################################################# 2## 3#W examples.gd Laurent Bartholdi 4## 5#H @(#)$Id$ 6## 7#Y Copyright (C) 2006, Laurent Bartholdi 8## 9############################################################################# 10## 11## All interesting examples of Mealy machines and groups I came through 12## 13############################################################################# 14 15############################################################################# 16## 17#E AddingMachine(n) 18#E AddingGroup(n) 19## 20## <#GAPDoc Label="AddingMachine"> 21## <ManSection> 22## <Func Name="AddingGroup" Arg="n"/> 23## <Func Name="AddingMachine" Arg="n"/> 24## <Func Name="AddingElement" Arg="n"/> 25## <Description> 26## The second function constructs the adding machine on the alphabet 27## <C>[1..n]</C>. This machine has a trivial state 1, and a non-trivial 28## state 2. It implements the operation "add 1 with carry" on sequences. 29## 30## <P/> The third function constructs the Mealy element on the adding 31## machine, with initial state 2. 32## 33## <P/> The first function constructs the state-closed group generated 34## by the adding machine on <C>[1..n]</C>. This group is 35## isomorphic to the <C>Integers</C>. 36## <Example><![CDATA[ 37## gap> Display(AddingElement(3)); 38## | 1 2 3 39## ---+-----+-----+-----+ 40## a | a,1 a,2 a,3 41## b | a,2 a,3 b,1 42## ---+-----+-----+-----+ 43## Initial state: b 44## gap> ActivityPerm(FRElement(AddingMachine(3),2),2); 45## (1,4,7,2,5,8,3,6,9) 46## gap> G := AddingGroup(3); 47## <self-similar group over [ 1 .. 3 ] with 1 generator> 48## gap> Size(G); 49## infinity 50## gap> IsRecurrentFRSemigroup(G); 51## true 52## gap> IsLevelTransitive(G); 53## true 54## ]]></Example> 55## </Description> 56## </ManSection> 57## 58## <ManSection> 59## <Var Name="BinaryAddingGroup"/> 60## <Var Name="BinaryAddingMachine"/> 61## <Var Name="BinaryAddingElement"/> 62## <Description> 63## These are respectively the same as <C>AddingGroup(2)</C>, 64## <C>AddingMachine(2)</C> and <C>AddingElement(2)</C>. 65## </Description> 66## </ManSection> 67## <#/GAPDoc> 68## 69DeclareAttribute("AddingMachine",IsPosInt); 70DeclareAttribute("AddingElement",IsPosInt); 71DeclareGlobalFunction("AddingGroup"); 72DeclareGlobalVariable("BinaryAddingMachine"); 73DeclareGlobalVariable("BinaryAddingElement"); 74DeclareGlobalVariable("BinaryAddingGroup"); 75############################################################################# 76 77############################################################################# 78## 79#E FiniteDepthBinaryGroup(l) 80#E FinitaryBinaryGroup 81#E BoundedBinaryGroup 82#E PolynomialStateGrowthBinaryGroup 83#E FiniteStateBinaryGroup 84#E FullBinaryGroup 85## 86## <#GAPDoc Label="FiniteDepthBinaryGroup"> 87## <ManSection> 88## <Var Name="FullBinaryGroup"/> 89## <Func Name="FiniteDepthBinaryGroup" Arg="l"/> 90## <Var Name="FinitaryBinaryGroup"/> 91## <Var Name="BoundedBinaryGroup"/> 92## <Var Name="PolynomialGrowthBinaryGroup"/> 93## <Var Name="FiniteStateBinaryGroup"/> 94## <Description> 95## These are the finitary, bounded, polynomial-growth, finite-state, 96## or unrestricted groups acting on the binary tree. They are 97## respectively shortcuts for 98## <C>FullSCGroup([1..2])</C>, 99## <C>FullSCGroup([1..2],l)</C>, 100## <C>FullSCGroup([1..2],IsFinitaryFRSemigroup)</C>, 101## <C>FullSCGroup([1..2],IsBoundedFRSemigroup)</C>, 102## <C>FullSCGroup([1..2],IsPolynomialGrowthFRSemigroup)</C>, 103## and <C>FullSCGroup([1..2],IsFiniteStateFRSemigroup)</C>. 104## 105## <P/> They may be used to draw random elements, or to test membership. 106## </Description> 107## </ManSection> 108## <#/GAPDoc> 109## 110DeclareGlobalFunction("FiniteDepthBinaryGroup"); 111DeclareGlobalVariable("FinitaryBinaryGroup"); 112DeclareGlobalVariable("BoundedBinaryGroup"); 113DeclareGlobalVariable("PolynomialGrowthBinaryGroup"); 114DeclareGlobalVariable("FiniteStateBinaryGroup"); 115DeclareGlobalVariable("FullBinaryGroup"); 116############################################################################# 117 118############################################################################# 119## 120#E MixerMachine 121#E MixerGroup 122## 123## <#GAPDoc Label="MixerMachine"> 124## <ManSection> 125## <Func Name="MixerGroup" Arg="A, B, f [g]"/> 126## <Func Name="MixerMachine" Arg="A, B, f [g]"/> 127## <Returns>A Mealy "mixer" machine/group.</Returns> 128## <Description> 129## The second function constructs a Mealy "mixer" machine <C>m</C>. This is a 130## machine determined by a permutation group <A>A</A>, 131## a finitely generated group <A>B</A>, and a matrix of homomorphisms 132## from <A>B</A> to <A>A</A>. If <A>A</A> acts on <C>[1..d]</C>, then 133## each row of <A>f</A> contains at most <M>d-1</M> homomorphisms. The optional 134## last argument is an endomorphism of <A>B</A>. If absent, it is treated 135## as the identity map on <A>B</A>. 136## 137## <P/> The states of the machine are 1, followed by some elements 138## <C>a</C> of <A>A</A>, followed by as many copies of some elements 139## <C>b</C> of <A>B</A> as there are rows in <A>f</A>. The elements in <A>B</A> 140## that are taken is the smallest sublist of <A>B</A> containing its generators 141## and closed under <A>g</A>. The elements in <A>A</A> that are taken are the 142## generators of <A>A</A> and all images of all taken elements of <A>B</A> under 143## maps in <A>f</A>. 144## 145## <P/> The transitions from <C>a</C> are towards 1 and the outputs are the 146## permutations in <A>A</A>. The transitions from <C>b</C> are periodically 147## given by <A>f</A>, completed by trivial elements, and finally by <M>b^g</M>; 148## the output of <C>b</C> is trivial. 149## 150## <P/> This construction is described in more detail in 151## <Cite Key="MR1856923"/> and <Cite Key="MR2035113"/>. 152## 153## <P/> <C>Correspondence(m)</C> is a list, with in first position the 154## subset of the states that correspond to <A>A</A>, in second position 155## the states that correspond to the first copy of <A>B</A>, etc. 156## 157## <P/> The first function constructs the group generated by the 158## mixer machine. For examples 159## see <Ref Func="GrigorchukGroups"/>, <Ref Func="NeumannGroup"/>, 160## <Ref Func="GuptaSidkiGroups"/>, and <Ref Var="ZugadiSpinalGroup"/>. 161## <Example><![CDATA[ 162## gap> grigorchukgroup := MixerGroup(Group((1,2)),Group((1,2)), 163## [[IdentityMapping(Group((1,2)))],[IdentityMapping(Group((1,2)))],[]])); 164## <self-similar group over [ 1 .. 2 ] with 4 generators> 165## gap> IdGroup(Group(grigorchukgroup.1,grigorchukgroup.2)); 166## [ 32, 18 ] 167## ]]></Example> 168## </Description> 169## </ManSection> 170## <#/GAPDoc> 171## 172DeclareGlobalFunction("MixerMachine"); 173DeclareGlobalFunction("MixerGroup"); 174############################################################################# 175 176############################################################################# 177## 178#E GrigorchukGroup 179#E GrigorchukGroups 180## 181## <#GAPDoc Label="GrigorchukGroup"> 182## <ManSection> 183## <Func Name="GrigorchukMachines" Arg="omega"/> 184## <Func Name="GrigorchukGroups" Arg="omega"/> 185## <Returns>One of the Grigorchuk groups.</Returns> 186## <Description> 187## This function constructs the Grigorchuk machine or group associated 188## with the infinite sequence <A>omega</A>, which is assumed (pre)periodic; 189## <A>omega</A> is either a periodic list (see <Ref Oper="PeriodicList"/>) 190## or a plain list describing the period. Entries in the list are 191## integers in <C>[1..3]</C>. 192## 193## <P/> These groups are <Ref Func="MixerGroup"/>s. The most famous 194## example is <C>GrigorchukGroups([1,2,3])</C>, which is also called 195## <Ref Var="GrigorchukGroup"/>. 196## 197## <P/> These groups are all 4-generated and infinite. 198## They are described in <Cite Key="MR764305"/>. 199## <C>GrigorchukGroups([1])</C> is infinite dihedral. If <A>omega</A> 200## contains at least 2 different digits, <C>GrigorchukGroups([1])</C> has 201## intermediate word growth. If <A>omega</A> 202## contains all 3 digits, <C>GrigorchukGroups([1])</C> is torsion. 203## 204## <P/> The growth of <C>GrigorchukGroups([1,2])</C> has been studied in 205## <Cite Key="MR2144977"/>. 206## <Example><![CDATA[ 207## gap> G := GrigorchukGroups([1]); 208## GrigorchukGroups([ 1 ]) 209## gap> Index(G,DerivedSubgroup(G)); IsAbelian(DerivedSubgroup(G)); 210## 4 211## true 212## gap> H := GrigorchukGroups([1,2]); 213## GrigorchukGroups([ 1, 2 ]) 214## gap> Order(H.1*H.2); 215## 8 216## gap> Order(H.1*H.4); 217## infinity 218## gap> IsSubgroup(H,G); 219## true 220## ]]></Example> 221## </Description> 222## </ManSection> 223## 224## <ManSection> 225## <Var Name="GrigorchukMachine"/> 226## <Var Name="GrigorchukGroup"/> 227## <Description> 228## This is Grigorchuk's first group, introduced in <Cite Key="MR565099"/>. 229## It is a 4-generated infinite torsion group, and has intermediate 230## word growth. It could have been defined as 231## <C><![CDATA[FRGroup("a=(1,2)","b=<a,c>","c=<a,d>","d=<,b>")]]></C>, 232## but is rather defined using Mealy elements. 233## 234## <P/> The command <C>EpimorphismFromFpGroup(GrigorchukGroup,n)</C> 235## constructs an approximating presentation for the 236## Grigorchuk group, as proven in <Cite Key="MR819415"/>. Adding the 237## relations <C>Image(sigma&circum;(n-2),(a*d)&circum;2)</C>, 238## <C>Image(sigma&circum;(n-1),(a*b)&circum;2)</C> and 239## <C>Image(sigma&circum;(n-2),(a*c)&circum;4)</C> yields the quotient 240## acting on <M>2^n</M> points, as a finitely presented group. 241## </Description> 242## </ManSection> 243## 244## <ManSection> 245## <Var Name="GrigorchukOverGroup"/> 246## <Description> 247## This is a group strictly containing the Grigorchuk group (see 248## <Ref Var="GrigorchukGroup"/>). 249## It also has 250## intermediate growth (see <Cite Key="MR1899368"/>, but it contains 251## elements of infinite order. It could have been defined as 252## <C><![CDATA[FRGroup("a=(1,2)","b=<a,c>","c=<,d>","d=<,b>")]]></C>, 253## but is rather defined using Mealy elements. 254## 255## <Example><![CDATA[ 256## gap> IsSubgroup(GrigorchukOverGroup,GrigorchukGroup); 257## true 258## gap> Order(Product(GeneratorsOfGroup(GrigorchukOverGroup))); 259## infinity 260## gap> GrigorchukGroup.2=GrigorchukSuperGroup.2*GrigorchukSuperGroup.3; 261## true 262## ]]></Example> 263## 264## <P/> The command <C>EpimorphismFromFpGroup(GrigorchukOverGroup,n)</C> will 265## will construct an approximating presentation for the 266## Grigorchuk overgroup, as proven in <Cite Key="MR2009317"/>. 267## </Description> 268## </ManSection> 269## 270## <ManSection> 271## <Var Name="GrigorchukTwistedTwin"/> 272## <Description> 273## This is a group with same closure as the Grigorchuk group (see 274## <Ref Var="GrigorchukGroup"/>), but not isomorphic to it. 275## It could have been defined as 276## <C><![CDATA[FRGroup("a=(1,2)","x=<y,a>","y=<a,z>","z=<,x>")]]></C>, 277## but is rather defined using Mealy elements. 278## 279## <Example><![CDATA[ 280## gap> AbelianInvariants(GrigorchukTwistedTwin); 281## [ 2, 2, 2, 2 ] 282## gap> AbelianInvariants(GrigorchukGroup); 283## [ 2, 2, 2 ] 284## gap> PermGroup(GrigorchukGroup,8)=PermGroup(GrigorchukTwistedTwin,8); 285## true 286## ]]></Example> 287## </Description> 288## </ManSection> 289## <#/GAPDoc> 290## 291DeclareGlobalFunction("GrigorchukMachines"); 292DeclareGlobalFunction("GrigorchukGroups"); 293DeclareGlobalVariable("GrigorchukMachine"); 294DeclareGlobalVariable("GrigorchukGroup"); 295DeclareGlobalVariable("GrigorchukOverGroup"); 296DeclareGlobalVariable("GrigorchukTwistedTwin"); 297############################################################################# 298 299############################################################################# 300## 301#E SunicMachine 302#E SunicGroup 303## 304## <#GAPDoc Label="SunicMachine"> 305## <ManSection> 306## <Func Name="SunicGroup" Arg="phi"/> 307## <Func Name="SunicMachine" Arg="phi"/> 308## <Returns>The Sunic machine associated with the polynomial <A>phi</A>.</Returns> 309## <Description> 310## A "Sunic machine" is a special kind of <Ref Func="MixerMachine"/>, in which 311## the group <M>A</M> is a finite field <M>GF(q)</M>, the group <M>B</M> is an 312## extension <M>A[x]/(\phi)</M>, where <M>\phi</M> is a monic polynomial; there 313## is a map <M>f:B\to A</M>, given say by evaluation; and there is an endomorphism 314## of <M>g:B\to B</M> given by multiplication by <M>\phi</M>. 315## 316## <P/> These groups were described in <Cite Key="MR2318546"/>. In particular, 317## the case <M>q=2</M> and <M>\phi=x^2+x+1</M> gives the original 318## <Ref Var="GrigorchukGroup"/>. 319## <Example><![CDATA[ 320## gap> x := Indeterminate(GF(2));; 321## gap> g := SunicGroup(x^2+x+1); 322## SunicGroup(x^2+x+Z(2)^0) 323## gap> g = GrigorchukGroup; 324## true 325## ]]></Example> 326## </Description> 327## </ManSection> 328## <#/GAPDoc> 329## 330DeclareGlobalFunction("SunicMachine"); 331DeclareGlobalFunction("SunicGroup"); 332############################################################################# 333 334############################################################################# 335## 336#E AleshinMachine 337#E AleshinGroup 338#E BabyAleshinMachine 339#E BabyAleshinGroup 340## 341## <#GAPDoc Label="AleshinMachine"> 342## <ManSection> 343## <Func Name="AleshinGroups" Arg="l"/> 344## <Func Name="AleshinMachines" Arg="l"/> 345## <Returns>The Aleshin machine with <C>Length(l)</C> states.</Returns> 346## <Description> 347## This function constructs the bireversible machines introduced by 348## Aleshin in <Cite Key="MR713968"/>. The argument <A>l</A> is a 349## list of permutations, either <C>()</C> or <C>(1,2)</C>. 350## The groups that they generate are contructed as 351## <Ref Func="AleshinGroups"/>. 352## 353## <P/> If <C>l=[(1,2),(1,2),()]</C>, this is <Ref Var="AleshinGroup"/>. 354## More generally, if <C>l=[(1,2,(1,2),(),...,()]</C> has odd length, 355## this is a free group of rank <C>Length(l)</C>, 356## see <Cite Key="MR2318547"/> and <Cite Key="0604328"/>. 357## 358## <P/> If <C>l=[(1,2),(1,2),...]</C> has even length and contains an 359## even number of <C>()</C>'s, then this is also a free group of 360## rank <C>Length(l)</C>, see <Cite Key="0610033"/>. 361## 362## <P/> If <C>l=[(),(),(1,2)]</C>, this is <Ref Var="BabyAleshinGroup"/>. 363## more generally, if <C>l=[(),(),...]</C> has even length and contains 364## an even number of <C>(1,2)</C>'s, then this is the free product of 365## <C>Length(l)</C> copies of the order-2 group. 366## </Description> 367## </ManSection> 368## 369## <ManSection> 370## <Var Name="AleshinGroup"/> 371## <Var Name="AleshinMachine"/> 372## <Description> 373## This is the first example of non-abelian free group. It is the group 374## generated by <C>AleshinMachine([(1,2),(1,2),()])</C>. 375## It could have been defined as 376## <C><![CDATA[FRGroup("a=<b,c>(1,2)","b=<c,b>(1,2)","c=<a,a>")]]></C>, 377## but is rather defined using Mealy elements. 378## </Description> 379## </ManSection> 380## 381## <ManSection> 382## <Var Name="BabyAleshinGroup"/> 383## <Var Name="BabyAleshinMachine"/> 384## <Description> 385## There are only two connected, transitive bireversible machines 386## on a 2-letter alphabet, with 3 generators: <C>AleshinMachine(3)</C> 387## and the baby Aleshin machine. 388## 389## <P/> The group generated by this machine 390## is abstractly the free product of three <M>C_2</M>'s, see 391## <Cite Key="MR2162164" Where="1.10.3"/>. It could have been defined as 392## <C><![CDATA[FRGroup("a=<b,c>","b=<c,b>","c=<a,a>(1,2)")]]></C>, 393## but is rather defined here using Mealy elements. 394## <Example><![CDATA[ 395## gap> K := Kernel(GroupHomomorphismByImagesNC(BabyAleshinGroup,Group((1,2)), 396## GeneratorsOfGroup(BabyAleshinGroup),[(1,2),(1,2),(1,2)])); 397## <self-similar group over [ 1 .. 2 ] with 4 generators> 398## gap> Index(BabyAleshinGroup,K); 399## 2 400## gap> IsSubgroup(AleshinGroup,K); 401## true 402## ]]></Example> 403## </Description> 404## </ManSection> 405## 406## <ManSection> 407## <Var Name="SidkiFreeGroup"/> 408## <Description> 409## This is a group suggested by Sidki as an example of a non-abelian 410## state-closed free group. Nothing is known about that group: whether 411## it is free as conjectured; whether generator <A>a</A> is state-closed, 412## etc. It is defined as 413## <C>FRGroup("a=<a&circum;2,a&circum;t>","t=<,t>(1,2)")]]></C>. 414## </Description> 415## </ManSection> 416## <#/GAPDoc> 417## 418DeclareGlobalFunction("AleshinMachines"); 419DeclareGlobalFunction("AleshinGroups"); 420DeclareGlobalVariable("AleshinMachine"); 421DeclareGlobalVariable("AleshinGroup"); 422DeclareGlobalVariable("BabyAleshinMachine"); 423DeclareGlobalVariable("BabyAleshinGroup"); 424DeclareGlobalVariable("SidkiFreeGroup"); 425############################################################################# 426 427############################################################################# 428## 429#E BrunnerSidkiVieiraMachine 430#E BrunnerSidkiVieiraGroup 431## 432## <#GAPDoc Label="BrunnerSidkiVieiraMachine"> 433## <ManSection> 434## <Var Name="BrunnerSidkiVieiraGroup"/> 435## <Var Name="BrunnerSidkiVieiraMachine"/> 436## <Description> 437## This machine is the sum of two adding machines, one in standard 438## form and one conjugated by the element <C>d</C> described below. 439## 440## The group that it generates is described in <Cite Key="MR1656573"/>. 441## It could have been defined as 442## <C>FRGroup("tau=<,tau>(1,2)","mu=<,mu&circum;-1>(1,2)")</C>, 443## but is rather defined using Mealy elements. 444## <Example><![CDATA[ 445## gap> V := FRGroup("d=<e,e>(1,2)","e=<d,d>"); 446## <self-similar group over [ 1 .. 2 ] with 2 generators> 447## gap> Elements(V); 448## [ <2|identity ...>, <2|e>, <2|d>, <2|e*d> ] 449## gap> AssignGeneratorVariables(BrunnerSidkiVieiraGroup); 450## #I Assigned the global variables [ "tau", "mu", "" ] 451## gap> List(V,x->tau^x)=[tau,mu,mu^-1,tau^-1]; 452## true 453## ]]></Example> 454## </Description> 455## </ManSection> 456## <#/GAPDoc> 457## 458DeclareGlobalVariable("BrunnerSidkiVieiraMachine"); 459DeclareGlobalVariable("BrunnerSidkiVieiraGroup"); 460############################################################################# 461 462############################################################################# 463## 464#E GuptaSidkiMachines 465#E GuptaSidkiGroups 466#E GuptaSidkiGroup 467#E FabrykowskiGuptaGroup 468#E ZugadiSpinalGroup 469## 470## <#GAPDoc Label="GuptaSidkiMachines"> 471## <ManSection> 472## <Func Name="GuptaSidkiGroups" Arg="n"/> 473## <Func Name="GeneralizedGuptaSidkiGroups" Arg="n"/> 474## <Func Name="GuptaSidkiMachines" Arg="n"/> 475## <Returns>The Gupta-Sidki group/machine on an <A>n</A>-letter alphabet.</Returns> 476## <Description> 477## This function constructs the machines introduced by Gupta 478## and Sidki in <Cite Key="MR696534"/>. They generate finitely generated 479## infinite torsion groups: the exponent of every element divides some 480## power of <A>n</A>. The 481## special case <M>n=3</M> is defined as <Ref Var="GuptaSidkiGroup"/> 482## and <Ref Var="GuptaSidkiMachine"/>. 483## 484## <P/> For <M>n>3</M>, there are (at least) two natural ways to 485## generalize the Gupta-Sidki construction: the original one involves 486## the recursion <C>"t=<a,a&circum;-1,1,...,1,t>"</C>, 487## while the second (called here `generalized') involves the 488## recursion <C>"t=<a,a&circum;2,...,a&circum;-1,t>"</C>. 489## A finite L-presentation for the latter is implemented. It is not 490## as computationally efficient as the L-presentation of the normal 491## closure of <C>t</C> (a subgroup of index <M>p</M>), which is an 492## ascending L-presented group. The inclusion of that subgroup may be 493## recoverd via <C>EmbeddingOfAscendingSubgroup(GuptaSidkiGroup)</C>. 494## </Description> 495## </ManSection> 496## 497## <ManSection> 498## <Var Name="GuptaSidkiGroup"/> 499## <Var Name="GuptaSidkiMachine"/> 500## <Description> 501## This is an infinite, 2-generated, torsion 3-group. It could have 502## been defined as <C>FRGroup("a=(1,2,3)","t=<a,a&circum;-1,t>")</C>, 503## but is rather defined using Mealy elements. 504## </Description> 505## </ManSection> 506## 507## <ManSection> 508## <Func Name="NeumannGroup" Arg="P"/> 509## <Func Name="NeumannMachine" Arg="P"/> 510## <Returns>The Neumann group/machine on the permutation group <A>P</A>.</Returns> 511## <Description> 512## The first function constructs the Neumann group associated 513## with the permutation group <A>P</A>. 514## These groups were first considered in 515## <Cite Key="MR840129"/>. In particular, <C>NeumannGroup(PSL(3,2))</C> 516## is a group of non-uniform exponential growth 517## (see <Cite Key="MR1981466"/>), and <C>NeumannGroup(Group((1,2,3)))</C> 518## is <Ref Var="FabrykowskiGuptaGroup"/>. 519## 520## <P/> The second function constructs the Neumann machine associated to the 521## permutation group <A>P</A>. It is a shortcut for 522## <C>MixerMachine(P,P,[[IdentityMapping(P)]])</C>. 523## 524## <P/> The attribute <C>Correspondence(G)</C> is set to a list of 525## homomorphisms from <A>P</A> to the <C>A</C> and <C>B</C> copies of 526## <C>P</C>. 527## </Description> 528## </ManSection> 529## 530## <ManSection> 531## <Var Name="FabrykowskiGuptaGroup"/> 532## <Func Name="FabrykowskiGuptaGroups" Arg="p"/> 533## <Description> 534## This is an infinite, 2-generated group of intermediate word growth. 535## It was studied in <Cite Key="MR942349"/> and <Cite Key="MR1153150"/>. 536## It could have been defined as <C><![CDATA[FRGroup("a=(1,2,3)","t=<a,,t>")]]></C>, 537## but is rather defined using Mealy elements. It has a torsion-free 538## subgroup of index 3 and is branched. 539## 540## <P/> The natural generalization, replacing 3 by <M>p</M>, is 541## constructed by the second form. It is a specific case of 542## Neumann group (see <Ref Func="NeumannGroup"/>), for which an 543## ascending L-presentation is known. 544## </Description> 545## </ManSection> 546## 547## <ManSection> 548## <Var Name="ZugadiSpinalGroup"/> 549## <Description> 550## This is an infinite, 2-generated group, which 551## was studied in <Cite Key="MR1899368"/>. It has a torsion-free subgroup 552## of index 3, and is virtually branched but not branched. 553## It could have been defined as <C><![CDATA[FRGroup("a=(1,2,3)","t=<a,a,t>")]]></C>, 554## but is rather defined using Mealy elements. 555## 556## <P/> Amaia Zugadi computed its Hausdorff dimension to be <M>1/2</M>. 557## </Description> 558## </ManSection> 559## <#/GAPDoc> 560## 561DeclareGlobalFunction("GuptaSidkiMachines"); 562DeclareGlobalFunction("GuptaSidkiGroups"); 563DeclareGlobalFunction("GeneralizedGuptaSidkiGroups"); 564DeclareGlobalVariable("GuptaSidkiMachine"); 565DeclareGlobalVariable("GuptaSidkiGroup"); 566DeclareGlobalFunction("NeumannMachine"); 567DeclareGlobalFunction("NeumannGroup"); 568DeclareGlobalVariable("FabrykowskiGuptaGroup"); 569DeclareGlobalFunction("FabrykowskiGuptaGroups"); 570DeclareGlobalVariable("ZugadiSpinalGroup"); 571############################################################################# 572 573############################################################################# 574## 575#E HanoiMachine 576#E HanoiGroup 577#E GuptaSidkiGroup 578#E FabrykowskiGuptaGroup 579## 580## <#GAPDoc Label="OtherGroups"> 581## <ManSection> 582## <Func Name="HanoiGroup" Arg="n"/> 583## <Returns>The Hanoi group on an <A>n</A> pegs.</Returns> 584## <Description> 585## This function constructs the Hanoi group on <A>n</A> pegs. 586## Generators of the group correspond to moving a peg, and tree 587## vertices correspond to peg configurations. This group is studied 588## in <Cite Key="MR2217913"/>. 589## </Description> 590## </ManSection> 591## 592## <ManSection> 593## <Var Name="DahmaniGroup"/> 594## <Description> 595## This is an example of a non-contracting weakly branched group. It was 596## first studied in <Cite Key="MR2140091"/>. It could have been defined as 597## <C><![CDATA[FRGroup("a=<c,a>(1,2)","b=<b,a>(1,2)","c=<b,c>")]]></C>, 598## but is rather defined using Mealy elements. 599## 600## <P/> It has relators <M>abc</M>, <M>[a^2c,[a,c]]</M>, 601## <M>[cab,a^{-1}c^{-1}ab]</M> and <M>[ac^2,c^{-1}b^{-1}c^2]</M> 602## among others. 603## 604## <P/> It admits an endomorphism on its derived subgroup. Indeed 605## <C>FRElement(1,Comm(a,b))=Comm(c&circum;-1,b/a)</C>, 606## <C>FRElement(1,Comm(a,c))=Comm(a/b,c)</C>, 607## <C>FRElement(1,Comm(b,c))=Comm(c,(a/b)&circum;c)</C>. 608## </Description> 609## </ManSection> 610## 611## <ManSection> 612## <Var Name="MamaghaniGroup"/> 613## <Description> 614## This group was studied in <Cite Key="MR2139928"/>. It is fractal, 615## but not contracting. It could have been defined as 616## <C>FRGroup("a=<,b>(1,2)","b=<a,c>","c=<a,a&circum;-1>(1,2)")]]></C>, 617## but is rather defined using Mealy elements. 618## 619## It partially admits branching on its subgroup 620## <C>Subgroup(G,[a&circum;2,(a&circum;2)&circum;b,(a&circum;2)&circum;c])</C>, 621## and, setting <C>x=Comm(a&circum;2,b)</C>, on 622## <C>Subgroup(G,[x,x&circum;a,x&circum;b,x&circum;(b*a),x&circum;(b/a)])</C>. 623## One has <C>FRElement(1,x)=(x&circum;-1)&circum;b/x</C>. 624## </Description> 625## </ManSection> 626## 627## <ManSection> 628## <Var Name="WeierstrassGroup"/> 629## <Description> 630## This is the iterated monodromy group associated with the 631## Weierstrass <M>\wp</M>-function. 632## 633## <P/> Some relators in the group: <M>(atbt)^4</M>, 634## <M>((atbt)(bt)^4n)^4</M>, <M>((atbt)^2(bt)^4n)^2</M>. 635## 636## <P/> Set <M>x=[a,t]</M>, <M>y=[b,t]</M>, <M>z=[c,t]</M>, and 637## <M>w=[x,y]</M>. Then <M>G'=\langle x,y,z\rangle</M> of index 8, and 638## <M>\gamma_3=\langle[\{x,y,z\},\{a,b,c\}]\rangle</M> of index 32, and 639## <M>\gamma_4=G''=\langle w\rangle^G</M>, of index 256, and 640## <M>G''>(G'')^4</M> since <M>[[t^a,t],[t^b,t]]=(w,1,1,1)</M>. 641## 642## <P/> The Schreier graph is obtained in the complex plane as the image 643## of a <M>2^n\times 2^n</M> lattice in the torus, via Weierstrass's 644## <M>\wp</M>-function. 645## 646## <P/> The element <M>at</M> has infinite order. 647## 648## <P/> <M>[c,t,b][b,t,c][a,t,c][c,t,a]</M> has order 2, and belongs 649## to <M>G''</M>; so there exist elements of arbitrary large finite order 650## in the group. 651## 652## <!--<P/> Its Lie algebra has polynomial growth.--> 653## </Description> 654## </ManSection> 655## 656## <ManSection> 657## <Var Name="StrichartzGroup"/> 658## <Description> 659## This group generates the graph of the Strichartz hexacarpet. 660## 661## <P/> The Strichartz hexacarpet is the dual graph to the infinitely 662## iterated barycentric subdivision of the triangle. The Strichartz group 663## acts on <M>\{1,\dots,6\}^n</M> for all <M>n</M>, and the Schreier 664## graph with <M>6^n</M> vertices is the <M>n</M>th Strichartz graph. 665## 666## <P/> Conjecturally, that graph's radius is 667## <M>1/18(2^(n+1)(13+3n)+(-1)^n-9)</M> and its diameter is 668## <M>1/9(2^(n-1)(31+12n)+2(-1)^(n-1)-18)</M>. 669## 670## <P/> See <Cite Key="MR3004256"/> for details. 671## </Description> 672## </ManSection> 673## <#/GAPDoc> 674## 675DeclareGlobalFunction("HanoiGroup"); 676DeclareGlobalVariable("DahmaniGroup"); 677DeclareGlobalVariable("MamaghaniGroup"); 678DeclareGlobalVariable("WeierstrassGroup"); 679DeclareGlobalVariable("StrichartzGroup"); 680############################################################################# 681 682############################################################################# 683## 684#E FRAffineGroup 685#E CayleyMachine 686#E CayleyGroup 687## 688## <#GAPDoc Label="FRAffineGroup"> 689## <ManSection> 690## <Oper Name="FRAffineGroup" Arg="d, R, u [transversal]"/> 691## <Returns>The <A>d</A>-dimensional affine group over <A>R</A>.</Returns> 692## <Description> 693## This function constructs a new FR group <C>G</C>, which is finite-index 694## subgroup of the <A>d</A>-dimensional affine group over 695## <M>R_u</M>, the local ring over <A>R</A> in which all 696## non-multiples of <A>u</A> are invertible. 697## 698## Since no generators of <C>G</C> are known, <C>G</C> is in fact returned 699## as a full SC group; only its attribute <C>Correspondence(G)</C>, 700## which is a homomorphism from <M>GL_{d+1}(R_u)</M> to <C>G</C>, 701## is relevant. 702## 703## <P/> The affine group can also be described as a subgroup of 704## <M>GL_{d+1}(R_u)</M>, consisting of those matrices <M>M</M> with 705## <M>M_{i,d+1}=0</M> and <M>M_{d+1,d+1}=1</M>. The finite-index 706## subgroup is defined by the conditions <M>u|M_{i,j}</M> for all 707## <M>j<i</M>. 708## 709## <P/> The only valid arguments are <C>R=Integers</C> and 710## <C>R=PolynomialRing(S)</C> for a finite ring <C>S</C>. 711## The alphabet of the affine group is <M>R/RuR</M>; an explicit 712## transversal of <M>RuR</M> be specified as last argument. 713## 714## <P/> The following examples construct the "Baumslag-Solitar group" 715## <M>\mathbb Z[\frac12]\rtimes_2\mathbb Z</M> first introduced in 716## <Cite Key="MR0142635"/>, the "lamplighter group" 717## <M>(\mathbb Z/2)\wr\mathbb Z</M>, and a 2-dimensional affine group. 718## Note that the lamplighter group may also be defined via 719## <Ref Func="CayleyGroup"/>. 720## <Example><![CDATA[ 721## gap> A := FRAffineGroup(1,Integers,3); 722## <self-similar group over [ 1 .. 3 ]> 723## gap> f := Correspondence(A); 724## MappingByFunction( ( Integers^ 725## [ 2, 2 ] ), <self-similar group over [ 1 .. 3 ]>, function( mat ) ... end ) 726## gap> BaumslagSolitar := Group([[2,0],[0,1]]^f,[[1,0],[1,1]]^f); 727## <self-similar group over [ 1 .. 3 ] with 2 generators> 728## gap> BaumslagSolitar.2^BaumslagSolitar.1=BaumslagSolitar.2^2; 729## true 730## gap> R := PolynomialRing(GF(2));; 731## gap> A := FRAffineGroup(1,R,R.1);; 732## gap> f := Correspondence(A);; 733## gap> Lamplighter := Group(([[1+R.1,0],[0,1]]*One(R))^f,([[1,0],[1,1]]*One(R))^f); 734## <self-similar group over [ 1 .. 2 ] with 2 generators> 735## gap> Lamplighter = CayleyGroup(Group((1,2))); 736## true 737## gap> StructureDescription(Group(Lamplighter.2,Lamplighter.2^Lamplighter.1)); 738## "C2 x C2" 739## gap> ForAll([1..10],i->IsOne(Comm(Lamplighter.2,Lamplighter.2^(Lamplighter.1^i)))); 740## true 741## gap> A := FRAffineGroup(2,Integers,2);; 742## gap> f := Correspondence(A);; 743## gap> a := [[1,4,0],[2,3,0],[1,0,1]]; 744## [ [ 1, 4, 0 ], [ 2, 3, 0 ], [ 1, 0, 1 ] ] 745## gap> b := [[1,2,0],[4,3,0],[0,1,1]]; 746## [ [ 1, 2, 0 ], [ 4, 3, 0 ], [ 0, 1, 1 ] ] 747## gap> Display(b^f); 748## | 1 2 749## ----+------+------+ 750## a | b,1 c,2 751## b | d,2 e,1 752## c | a,2 f,1 753## ... 754## bh | cb,1 be,2 755## ca | bd,1 bf,2 756## cb | ae,2 bh,1 757## ----+------+------+ 758## Initial state: a 759## gap> a^f*b^f=(a*b)^f; 760## true 761## ]]></Example> 762## </Description> 763## </ManSection> 764## 765## <ManSection> 766## <Func Name="CayleyGroup" Arg="G"/> 767## <Func Name="CayleyMachine" Arg="G"/> 768## <Meth Name="LamplighterGroup" Arg="IsFRGroup, G"/> 769## <Returns>The Cayley machine/group of the group <A>G</A>.</Returns> 770## <Description> 771## The <E>Cayley machine</E> of a group <A>G</A> is a machine with 772## alphabet and stateset equal to <A>G</A>, and with output and 773## transition functions given by multiplication in the group, in the 774## order <C>state*letter</C>. 775## 776## <P/> The second function constructs a new FR group <C>CG</C>, which acts on 777## <C>[1..Size(G)]</C>. Its generators are in 778## bijection with the elements of <A>G</A>, and have as output the 779## corresponding permutation of <A>G</A> induced by right multiplication, 780## and as transitions all elements of <A>G</A>; see 781## <Ref Func="CayleyMachine"/>. 782## This construction was introduced in <Cite Key="MR2197829"/>. 783## 784## <P/> If <A>G</A> is an abelian group, then <C>CG</C> is 785## the wreath product <M>G\wr\mathbb Z</M>; it is created by the 786## constructor <C>LamplighterGroup(IsFRGroup,G)</C>. 787## 788## <P/> The attribute <C>Correspondence(CG)</C> is a list. Its 789## first entry is a homomorphism from <A>G</A> into <C>CG</C>. Its 790## second entry is the generator of <C>CG</C> that has trivial output. 791## <C>CG</C> is generated <C>Correspondence(CG)[2]</C> and the image 792## of <C>Correspondence(CG)[1]</C>. 793## 794## <P/> In the example below, recall the definition of <C>Lamplighter</C> 795## in the example of <Ref Oper="FRAffineGroup"/>. 796## <Example><![CDATA[ 797## gap> L := CayleyGroup(Group((1,2))); 798## CayleyGroup(Group( [ (1,2) ] )) 799## gap> L=LamplighterGroup(IsFRGroup,CyclicGroup(2)); 800## true 801## gap> (1,2)^Correspondence(L)[1]; 802## <Mealy element on alphabet [ 1, 2 ] with 2 states, initial state 1> 803## gap> IsFinitaryFRElement(last); Display(last2); 804## true 805## | 1 2 806## ---+-----+-----+ 807## a | b,2 b,1 808## b | b,1 b,2 809## ---+-----+-----+ 810## Initial state: a 811## ]]></Example> 812## </Description> 813## </ManSection> 814## <#/GAPDoc> 815## 816DeclareOperation("FRAffineGroup",[IsPosInt,IsRing,IsRingElement]); 817DeclareOperation("FRAffineGroup",[IsPosInt,IsRing,IsRingElement,IsCollection]); 818DeclareGlobalFunction("CayleyMachine"); 819DeclareGlobalFunction("CayleyGroup"); 820DeclareConstructor("LamplighterGroup",[IsFRGroup,IsGroup]); 821############################################################################# 822 823############################################################################# 824## 825#E BinaryKneadingGroup 826#E BasilicaGroup 827## 828## <#GAPDoc Label="BinaryKneadingGroup"> 829## <ManSection> 830## <Func Name="BinaryKneadingGroup" Arg="angle/ks"/> 831## <Func Name="BinaryKneadingMachine" Arg="angle/ks"/> 832## <Returns>The [machine generating the] iterated monodromy group of a quadratic polynomial.</Returns> 833## <Description> 834## The first function constructs a Mealy machine whose state closure is 835## the binary kneading group. 836## 837## <P/> The second function constructs a new FR group <C>G</C>, 838## which is the iterated monodromy group of a quadratic polynomial, 839## either specified by its angle or by its kneading sequence(s). 840## 841## <P/> If the argument is a (rational) angle, the attribute 842## <C>Correspondence(G)</C> is a function returning, for any rational, 843## the corresponding generator of <C>G</C>. 844## 845## <P/> If there is one argument, which is a list or a string, it is 846## treated as the kneading sequence of a periodic (superattracting) 847## polynomial. The sequence is implicity assumed to end by '*'. 848## The attribute <C>Correspondence(G)</C> is a list of the generators of 849## <C>G</C>. 850## 851## <P/> If there are two arguments, which are lists or strings, they are 852## treated as the preperiod and period of the kneading sequence of a 853## preperiodic polynomial. The last symbol of the arguments must differ. 854## The attribute <C>Correspondence(G)</C> is a pair of lists of 855## generators; <C>Correspondence(G)[1]</C> is the preperiod, and 856## <C>Correspondence(G)[2]</C> is the period. The attribute 857## <C>KneadingSequence(G)</C> returns the kneading sequence, as a pair 858## of strings representing preperiod and period respectively. 859## 860## <P/> As particular examples, <C>BinaryKneadingMachine()</C> is the 861## adding machine; <C>BinaryKneadingGroup()</C> is the 862## adding machine; and <C>BinaryKneadingGroup("1")</C> is 863## <Ref Var="BasilicaGroup"/>. 864## <Example><![CDATA[ 865## gap> BinaryKneadingGroup()=AddingGroup(2); 866## true 867## gap> BinaryKneadingGroup(1/3)=BasilicaGroup; 868## true 869## gap> g := BinaryKneadingGroup([0,1],[0]); 870## BinaryKneadingGroup("01","0") 871## gap> ForAll(Correspondence(g)[1],IsFinitaryFRElement); 872## true 873## gap> ForAll(Correspondence(g)[2],IsFinitaryFRElement); 874## false 875## gap> ForAll(Correspondence(g)[2],IsBoundedFRElement); 876## true 877## ]]></Example> 878## </Description> 879## </ManSection> 880## 881## <ManSection> 882## <Var Name="BasilicaGroup"/> 883## <Description> 884## The <E>Basilica group</E>. This is a shortcut for 885## <C>BinaryKneadingGroup("1")</C>. It is the first-discovered amenable 886## group that is not subexponentially amenable, 887## see <Cite Key="MR2176547"/> and <Cite Key="MR1902367"/>. 888## <Example><![CDATA[ 889## gap> IsBoundedFRSemigroup(BasilicaGroup); 890## true 891## gap> pi := EpimorphismFromFreeGroup(BasilicaGroup); F := Source(pi);; 892## [ x1, x2 ] -> [ a, b ] 893## gap> sigma := GroupHomomorphismByImages(F,F,[F.1,F.2],[F.2,F.1^2]); 894## [ x1, x2 ] -> [ x2, x1^2 ] 895## gap> ForAll([0..10],i->IsOne(Comm(F.2,F.2^F.1)^(sigma^i*pi))); 896## true 897## ]]></Example> 898## </Description> 899## </ManSection> 900## 901## <ManSection> 902## <Var Name="FornaessSibonyGroup"/> 903## <Description> 904## The <E>Fornaess-Sibony group</E>. This group was studied by 905## Nekrashevych in <Cite Key="0811.2777"/>. It is the iterated 906## monodromy group of the endomorphism of <M>\mathbb CP^2</M> 907## defined by <M>(z,p)\mapsto((1-2z/p)^2,(1-2/p)^2)</M>. 908## <Example><![CDATA[ 909## gap> Size(NucleusOfFRSemigroup(FornaessSibonyGroup)); 910## 288 911## gap> List(AdjacencyBasesWithOne(FornaessSibonyGroup),Length); 912## [ 128, 128, 36, 36, 16, 16, 8 ] 913## gap> p := AdjacencyPoset(FornaessSibonyGroup); 914## <general mapping: <object> -> <object> > 915## gap> Draw(HasseDiagramBinaryRelation(p)); 916## ]]></Example> 917## This produces (in a new window) the following picture: 918## <Alt Only="LaTeX"><![CDATA[ 919## \includegraphics[height=3cm,keepaspectratio=true]{fornaess-sibony.jpg} 920## ]]></Alt> 921## <Alt Only="HTML"><![CDATA[ 922## <img alt="Hasse Diagram" src="fornaess-sibony.jpg"> 923## ]]></Alt> 924## </Description> 925## </ManSection> 926## <#/GAPDoc> 927## 928DeclareAttribute("KneadingSequence",IsFRGroup); 929DeclareGlobalFunction("BinaryKneadingMachine"); 930DeclareGlobalFunction("BinaryKneadingGroup"); 931DeclareGlobalVariable("BasilicaGroup"); 932DeclareGlobalVariable("FornaessSibonyGroup"); 933############################################################################# 934 935############################################################################# 936## 937#E I2Machine 938#E I2Monoid 939#E I4Machine 940#E I4Monoid 941## 942## <#GAPDoc Label="I2Machine"> 943## <ManSection> 944## <Var Name="I2Machine"/> 945## <Var Name="I2Monoid"/> 946## <Description> 947## The Mealy machine <M>I_2</M>, and the monoid that it generates. 948## This is the smallest 949## Mealy machine generating a monoid of intermediate word growth; see 950## <Cite Key="MR2194959"/>. 951## 952## <P/> For sample calculations in this monoid see 953## <Ref Func="SCSemigroup"/>. 954## </Description> 955## </ManSection> 956## 957## <ManSection> 958## <Var Name="I4Machine"/> 959## <Var Name="I4Monoid"/> 960## <Description> 961## The Mealy machine generating <M>I_4</M>, and the monoid 962## that it generates. This is a very small 963## Mealy machine generating a monoid of intermediate word growth; see 964## <Cite Key="MR2394721"/>. 965## 966## <P/> For sample calculations in this monoid see 967## <Ref Func="SCMonoid"/>. 968## </Description> 969## </ManSection> 970## <#/GAPDoc> 971## 972DeclareGlobalVariable("I2Machine"); 973DeclareGlobalVariable("I2Monoid"); 974DeclareGlobalVariable("I4Machine"); 975DeclareGlobalVariable("I4Monoid"); 976############################################################################# 977 978############################################################################# 979## 980#E PSZAlgebra 981## 982## <#GAPDoc Label="PSZAlgebra"> 983## <ManSection> 984## <Func Name="PSZAlgebra" Arg="k [,m]"/> 985## <Description> 986## This function creates an associative algebra <C>A</C>, over 987## the field <A>k</A> of positive characteristic, generated by 988## <A>m</A> derivations <C>d0,...,d(m-1),v</C>. If the argument <A>m</A> 989## is absent, it is taken to be <C>2</C>. 990## 991## <P/> This algebra has polynomial growth, and is not nilpotent. 992## Petrogradsky showed in <Cite Key="MR2293788"/> that 993## the Lie subalgebra of <C>PSZAlgebra(GF(2))</C> generated by 994## <M>v,[u,v]</M> is nil; this result was generalized by 995## Shestakov and Zelmanov in <Cite Key="MR2390328"/> to arbitrary <A>k</A> 996## and <M>m=2</M>. 997## 998## <P/> This ring is <M>\mathbb Z^m</M>-graded; 999## the attribute <C>Grading</C> is set. It is graded nil <Cite Key="PSZ"/>. 1000## <Example><![CDATA[ 1001## gap> a := PSZAlgebra(2); 1002## PSZAlgebra(GF(2)) 1003## gap> Nillity(a.1); Nillity(a.2); 1004## 2 1005## 4 1006## gap> IsNilElement(LieBracket(a.1,a.2)); 1007## true 1008## gap> DecompositionOfFRElement(LieBracket(a.1,a.2))=DiagonalMat([a.2,a.2]); 1009## true 1010## ]]></Example> 1011## </Description> 1012## </ManSection> 1013## 1014## <ManSection> 1015## <Func Name="GrigorchukThinnedAlgebra" Arg="k"/> 1016## <Description> 1017## This function creates the associative envelope <C>A</C>, over 1018## the field <A>k</A>, of Grigorchuk's group <Ref Var="GrigorchukGroup"/>. 1019## 1020## <P/> <A>k</A> may be a field or an prime representing the prime 1021## field <C>GF(k)</C>. In characteristic 2, this ring is graded, and 1022## the attribute <C>Grading</C> is set. 1023## 1024## <P/> For more information on the structure of this thinned algebra, 1025## see <Cite Key="MR2254535"/>. 1026## <Example><![CDATA[ 1027## gap> R := GrigorchukThinnedAlgebra(2); 1028## <self-similar algebra-with-one on alphabet GF(2)^2 with 4 generators, of dimension infinity> 1029## gap> GrigorchukGroup.1^Embedding(GrigorchukGroup,R)=R.1; 1030## true 1031## gap> Nillity(R.2+R.1); 1032## 16 1033## gap> x := 1+R.1+R.2+(R.1-1)*(R.4-1); # x has infinite order 1034## <Linear element on alphabet GF(2)^2 with 5-dimensional stateset> 1035## gap> Inverse(x); 1036## <Linear element on alphabet GF(2)^2 with 9-dimensional stateset> 1037## gap> Grading(R).hom_components(4); 1038## <vector space of dimension 6 over GF(2)> 1039## gap> Random(last); 1040## <Linear element on alphabet GF(2)^2 with 6-dimensional stateset> 1041## gap> Nillity(last); 1042## 4 1043## ]]></Example> 1044## </Description> 1045## </ManSection> 1046## 1047## <ManSection> 1048## <Func Name="GuptaSidkiThinnedAlgebra" Arg="k"/> 1049## <Description> 1050## This function creates the associative envelope <C>A</C>, over 1051## the field <A>k</A>, of Gupta-Sidki's group <Ref Var="GuptaSidkiGroup"/>. 1052## 1053## <P/> <A>k</A> may be a field or an prime representing the prime 1054## field <C>GF(k)</C>. 1055## 1056## <P/> For more information on the structure of this thinned algebra, 1057## see <Cite Key="MR1423285"/>. 1058## <Example><![CDATA[ 1059## gap> R := GuptaSidkiThinnedAlgebra(3); 1060## <self-similar algebra-with-one on alphabet GF(3)^3 with 4 generators> 1061## gap> Order(R.1); 1062## 3 1063## gap> R.1*R.3; 1064## <Identity linear element on alphabet GF(3)^3> 1065## gap> IsOne(R.2*R.4); 1066## true 1067## gap> x := 1+R.2*(1+R.1+R.3); # a non-invertible element 1068## <Linear element on alphabet GF(3)^3 with 5-dimensional stateset> 1069## gap> Inverse(x); 1070## #I InverseOp: extending to depth 3 1071## #I InverseOp: extending to depth 4 1072## #I InverseOp: extending to depth 5 1073## #I InverseOp: extending to depth 6 1074## Error, user interrupt in 1075## ]]></Example> 1076## </Description> 1077## </ManSection> 1078## 1079## <ManSection> 1080## <Func Name="GrigorchukLieAlgebra" Arg="k"/> 1081## <Func Name="GuptaSidkiLieAlgebra" Arg="k"/> 1082## <Description> 1083## Two more examples of self-similar Lie algebras; see 1084## <Cite Key="1003.1125"/>. 1085## </Description> 1086## </ManSection> 1087## 1088## <ManSection> 1089## <Func Name="SidkiFreeAlgebra" Arg="k"/> 1090## <Description> 1091## This is an example of a free 2-generated associative ring over 1092## the <M>\mathbb Z</M>, defined by self-similar matrices. It is due 1093## to S. Sidki. The argument is a field on which to construct the algebra. 1094## The recursion is <C>s=[[1,0],[0,2*s]]</C> and 1095## <C>t=[[0,2*s],[0,2*t]]</C>. 1096## <Example><![CDATA[ 1097## gap> R := SidkiFreeAlgebra(Rationals); 1098## <self-similar algebra-with-one on alphabet Rationals^2 with 2 generators> 1099## gap> V := VectorSpace(Rationals,[R.1,R.2]); 1100## <vector space over Rationals, with 2 generators> 1101## gap> P := [V];; for i in [1..3] do Add(P,ProductSpace(P[i],V)); od; 1102## gap> List(P,Dimension); 1103## [ 2, 4, 8, 16 ] 1104## gap> R := SidkiFreeAlgebra(GF(3)); 1105## <self-similar algebra-with-one on alphabet GF(3)^2 with 2 generators> 1106## gap> V := VectorSpace(GF(3),[R.1,R.2]);; 1107## gap> P := [V];; for i in [1..3] do Add(P,ProductSpace(P[i],V)); od; 1108## gap> List(P,Dimension); 1109## [ 2, 4, 7, 12 ] 1110## ]]></Example> 1111## </Description> 1112## </ManSection> 1113## 1114## <ManSection> 1115## <Func Name="SidkiMonomialAlgebra" Arg="k"/> 1116## <Description> 1117## This is an example of a self-similar algebra that does not come from 1118## a semigroup; it is due to S. Sidki. 1119## The argument is a field on which to construct the algebra. 1120## The recursion is <C>s=[[0,0],[1,0]]</C> and 1121## <C>t=[[0,t],[0,s]]</C>. Sidki shows that this algebra, like the 1122## Grigorchuk thinned algebra in characteristic 2 (see <Ref 1123## Func="GrigorchukThinnedAlgebra"/>), admits a monomial presentation, 1124## and in particular is a graded ring. 1125## <Example><![CDATA[ 1126## gap> R := SidkiMonomialAlgebra(Rationals); 1127## <self-similar algebra-with-one on alphabet Rationals^2 with 2 generators> 1128## gap> m := FreeSemigroup("s","t");; 1129## gap> lambda := MagmaEndomorphismByImagesNC(m,[m.2,m.1*m.2]);; 1130## gap> u := [m.1^2];; for i in [1..3] do u[2*i] := m.2*u[2*i-1]^lambda; u[2*i+1] := u[2*i]^lambda; od; 1131## gap> u; # first relations 1132## [ s^2, t^3, s*t*s*t*s*t, t^2*s*t^2*s*t^2*s*t, 1133## s*t*s*t^2*s*t*s*t^2*s*t*s*t^2*s*t, 1134## t^2*s*t^2*s*t*s*t^2*s*t^2*s*t*s*t^2*s*t^2*s*t*s*t^2*s*t, 1135## s*t*s*t^2*s*t*s*t^2*s*t^2*s*t*s*t^2*s*t*s*t^2*s*t^2*s*t*s*t^2*s*t*s*t^2*s*t^2*s*t*s*t^2*s*t ] 1136## gap> pi := MagmaHomomorphismByImagesNC(m,R,[R.1,R.2]);; 1137## gap> Image(pi,u); 1138## [ <Zero linear element on alphabet Rationals^2> ] 1139## gap> # growth given by fibonacci numbers 1140## gap> List([0..6],Grading(R).hom_components); 1141## [ <vector space over Rationals, with 1 generators>, <vector space over Rationals, with 2 generators>, 1142## <vector space of dimension 3 over Rationals>, <vector space of dimension 4 over Rationals>, 1143## <vector space of dimension 5 over Rationals>, <vector space of dimension 7 over Rationals>, 1144## <vector space of dimension 8 over Rationals> ] 1145## ]]></Example> 1146## </Description> 1147## </ManSection> 1148## <#/GAPDoc> 1149## 1150DeclareGlobalFunction("PSZAlgebra"); 1151DeclareGlobalFunction("GrigorchukThinnedAlgebra"); 1152DeclareGlobalFunction("GuptaSidkiThinnedAlgebra"); 1153DeclareGlobalFunction("GrigorchukLieAlgebra"); 1154DeclareGlobalFunction("GuptaSidkiLieAlgebra"); 1155DeclareGlobalFunction("SidkiFreeAlgebra"); 1156DeclareGlobalFunction("SidkiMonomialAlgebra"); 1157############################################################################# 1158 1159#E examples.gd. . . . . . . . . . . . . . . . . . . . . . . . . . . ends here 1160