Grigorchuk groups
Grigorchuk groups
Original Grigorchuk group
Original Grigorchuk group
Originally the setup was for measure preserving maps of Interval[{0,1}],
i.e., maps which preserve the total length of possibly disconnected subsets.
Not continuous. Later authors claim that the group is more naturally defined
asa subgroup of the automorphisms of the infinite binary tree.
Originally the setup was for measure preserving maps of Interval[{0,1}],
i.e., maps which preserve the total length of possibly disconnected subsets.
Not continuous. Later authors claim that the group is more naturally defined
asa subgroup of the automorphisms of the infinite binary tree.
Needs["DiscreteMath`Combinatorica`"]
ShowLabeledGraph[SetGraphOptions[CompleteBinaryTree[15],Table[{n,VertexColorHue[n/20]},{n,15}]]];
It is generated by four involutions p, f, g, and h.
But they have a recursive definition. The first one p switchs the top two
branches. Then f is p on the right branch and g and the left branch.
Similarly, g is p on the right and h on the left. The map h is the identity
on the right and f on the left.
But they have a recursive definition. The first one p switchs the top two
branches. Then f is p on the right branch and g and the left branch.
Similarly, g is p on the right and h on the left. The map h is the identity
on the right and f on the left.
The difference between f, g and h is in the value of Mod[_, 3] of what levels
they switch the branches of the next to left-most node.
The difference between f, g and h is in the value of Mod[_, 3] of what levels
they switch the branches of the next to left-most node.
The set of relations is infinite. But there are some simple relations which
hold, which imply for instance that only three of the generators are
necessary as long as p is included.
The set of relations is infinite. But there are some simple relations which
hold, which imply for instance that only three of the generators are
necessary as long as p is included.
f[f[n]]g[g[n]]h[h[n]]p[p[n]]n
f[g[n]]g[f[n]]h[n]
h[g[n]]g[h[n]]f[n]
h[f[n]]f[h[n]]g[n]
definitions for p,f,g,h
definitions for p,f,g,h
p[1]:=1
p[n_Integer]:=FromDigits[MapAt[#/.{10,01}&,IntegerDigits[n,2],2],2]
f[1]:=1
f[n_Integer]:=With[{pos=Flatten[Position[IntegerDigits[n,2],1,1,2]]},If[Length[pos]<2||Last[pos]Length[IntegerDigits[n,2]]||Mod[Last[pos],3]1,n,FromDigits[MapAt[#/.{10,01}&,IntegerDigits[n,2],pos[[-1]]+1],2]]]
g[1]:=1
g[n_Integer]:=With[{pos=Flatten[Position[IntegerDigits[n,2],1,1,2]]},If[Length[pos]<2||Last[pos]Length[IntegerDigits[n,2]]||Mod[Last[pos],3]0,n,FromDigits[MapAt[#/.{10,01}&,IntegerDigits[n,2],pos[[-1]]+1],2]]]
h[1]:=1
h[n_Integer]:=With[{pos=Flatten[Position[IntegerDigits[n,2],1,1,2]]},If[Length[pos]<2||Last[pos]Length[IntegerDigits[n,2]]||Mod[Last[pos],3]2,n,FromDigits[MapAt[#/.{10,01}&,IntegerDigits[n,2],pos[[-1]]+1],2]]]
depth 4 pictures
depth 4 pictures
finite state automata
finite state automata
Generalized Grigorchuk group
Generalized Grigorchuk group
In the original example, the generators f, g and h all followed the sequence,
Swap, Swap, Identity, on successive levels, acting on the second node from
the left. The difference was that they were off by one on different
levels,
In the original example, the generators f, g and h all followed the sequence,
Swap, Swap, Identity, on successive levels, acting on the second node from
the left. The difference was that they were off by one on different
levels,
TableForm[{f{S,S,Id,S,S,Id},g{S,Id,S,S,Id,S},h{Id,S,S,Id,S,S}}]
f=={S,S,Id,S,S,Id} |
g=={S,Id,S,S,Id,S} |
h=={Id,S,S,Id,S,S} |
In the generalized case, one takes an infinite string of 0,1, and 2's and
defines the generators using the appropriate column from above.
In the generalized case, one takes an infinite string of 0,1, and 2's and
defines the generators using the appropriate column from above.
basictrans={{S,S,Id},{S,Id,S},{Id,S,S}};
f[w_List]:=basictrans[[1]][[w+1]]
g[w_List]:=basictrans[[2]][[w+1]]
h[w_List]:=basictrans[[3]][[w+1]]
So the levels where the second to the left node get switched depend on the
generator f,g, or h, and the sequence w. Each infinite string w gives a
different group.
So the levels where the second to the left node get switched depend on the
generator f,g, or h, and the sequence w. Each infinite string w gives a
different group.
The original group corresponds to the repeating sequence {0,1,2,0,1,2,...}
The original group corresponds to the repeating sequence {0,1,2,0,1,2,...}
Solve[27xx+5,x]
x
5
26
RealDigits[5/26,3]
{{{1,2,0}},-1}
RealDigits[5/26,3,8,-1]
{{0,1,2,0,1,2,0,1},0}
Facts
Facts
Assume that the string w contains infinitely many of each of {0,1,2}.
Assume that the string w contains infinitely many of each of {0,1,2}.
Every element of the group has a finite order of a power of 2.
Every element of the group has a finite order of a power of 2.
The word problem in p,f,g,h is solvable.
Inifinitely many relations are necessary to present the group.
Inifinitely many relations are necessary to present the group.
The group has intermediate growth in the number of distinct word length.
The group has intermediate growth in the number of distinct word length.
References
References
http://citeseer.nj.nec.com/cache/papers/cs/7024/http:zSzzSzmath.yale.eduzSzuserszSzpakizSzgrig9.pdf/muchnik99growth.pdf
http://www.ma.umist.ac.uk/mcraven/material/petrides-grigorchukgps.pdf