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=&lt;a&circum;2,a&circum;t&gt;","t=&lt;,t&gt;(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=&lt;,tau&gt;(1,2)","mu=&lt;,mu&circum;-1&gt;(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&gt;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=&lt;a,a&circum;-1,1,...,1,t&gt;"</C>,
487##     while the second (called here `generalized') involves the
488##     recursion <C>"t=&lt;a,a&circum;2,...,a&circum;-1,t&gt;"</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=&lt;a,a&circum;-1,t&gt;")</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=&lt;,b&gt;(1,2)","b=&lt;a,c&gt;","c=&lt;a,a&circum;-1&gt;(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''&gt;(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&lt;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