Two formulations of a group

   This post talks about an interesting group that can be formulated in two ways: as a group of mappings from an interval (with certain points removed) and as a group of automorphisms of a binary tree. The relations between these two formulations will also be explained. 

1. First formulation: as a group of mappings from an interval to itself (or, in other words, as a group acting on that interval)

   Consider the interval [0, 1] with all dyadic rationals (i.e. numbers that can be expressed as a fraction whose denominator is a power of two) removed and denote the remaining set by C. This group can be described as a group of bijective mappings from C to itself. It is generated by the elements a, b, c, d, which are defined as follows: 
   - a is the mapping that sends each x < 1/2 to x + 1/2 and each x > 1/2 to x - 1/2. In other words, it permutes/swaps the two halves of the interval [0, 1]. 
   - b is the mapping that sends each of the intervals [0, 1/2], [1/2, 3/4], [3/4, 7/8], [7/8, 15/16], ... to itself. Moreover, if the interval is marked with "P" in the following image, the two halves of the interval are permuted/swapped, otherwise no change is made. The intervals are marked with "P" and "I" periodically, with an "I" followed by two "P". For example, the intervals [7/8, 15/16], [15/16, 31/32], [31/32, 63/64], [63/64, 127/128], [127/128, 255/256], [255/256, 511/512] are marked with "P", "P", "I", "P", "P", "I" respectively. 

   - Similarly, c and d also send each of the intervals [0, 1/2], [1/2, 3/4], [3/4, 7/8], [7/8, 15/16], ... to itself. Regarding the element c, if the interval is marked with "P" in the following image, the two halves of the interval are permuted, otherwise no change is made. Similarly as above, the intervals are also marked with "P" and "I" periodically, with an "I" followed by two "P". For example, the intervals [7/8, 15/16], [15/16, 31/32], [31/32, 63/64], [63/64, 127/128], [127/128, 255/256], [255/256, 511/512] are marked with "P", "I", "P", "P", "I", "P" respectively. 

   Meanwhile, whether the two halves of each interval are swapped or not in d is determined by the following image. The next intervals are marked periodically with "I", "P", "P", "I", "P", "P", ...

  

   It is clear that each of the elements a, b, c, d preserves the Lebesgue measure, thus this group might be considered as a group of transformations that preserve the Lebesgue measure. We might also say that this group acts on the interval [0, 1] and the action preserves the Lebesgue measure. 

   This group is usually called the Grigorchuk group, which was named after the mathematician Rostislav Grigorchuk. He is now Distinguished Professor at Texas A&M University and was an invited speaker at the International Congress of Mathematicians in 1990. A part of the talk was about this group, and he also mentioned this formulation instead of the second formulation, which will be mentioned in the next section. 

The group was described as in the image above in the Proceedings of the ICM 1990

2. Second formulation: as a group of automorphisms of a binary tree (or, in other words, a group acting on that tree)

   Recall that in graph theory, an isomorphism between two graphs is a bijective mapping from the vertex set of the first graph to the vertex set of the second graph that preserves adjacency/nonadjacency between pairs of vertices. An automorphism is an isomorphism from a graph to itself. The following fact is quite fundamental/elementary in graph theory or other closely related areas: The set of automorphisms of a graph can be equipped with a group structure, where the operation is simply the composition of mappings. In this case, we consider the group of automorphisms of a particular graph, which is the infinite (rooted) binary tree where each node has exactly two children. This might be considered as a "perfect" form of a binary tree, since we don't need to consider leaves or nodes with only one child. 

   Let R be the root of the tree and let C(1), C(2) be its two children. An automorphism must definitely fix R, while the two children C(1) and C(2) can be swapped. If the two children C(1) and C(2) are swapped, the two subtrees starting from C(1) and C(2) should also be swapped as well. We might choose an isomorphism, denoted by i, between these two subtrees. We can identify the element a with the automorphism that sends the root R to itself and each vertex v of the subtree starting from C(1) to i(v) (and conversely, i(v) is also sent to v).

   To identify the elements b, c, d with the "suitable" automorphisms, we first identify each of the intervals [0, 1/2], [1/2, 3/4], [3/4, 7/8], [7/8, 15/16], ... with the corresponding "branch" (or subtree) of this binary tree as follows. For example, [0, 1/2] is identified with the subtree starting from C(1), while [1/2, 3/4] is identified with the subtree starting from the "left" child of C(2). The corresponding automorphisms are determined according to the following rule: if the interval is marked with "P", the two branches of the corresponding subtree/branch must be swapped, otherwise they are fixed. For example, in the automorphisms corresponding to the elements b and c, the two subtrees of the (sub)tree starting from C(1) should be swapped, but this is not the case in the automorphism corresponding to d since [0, 1/2] is marked with "I" when defining d. 

   

   Since the swapping rule in section 1 is fixed, the swapping rule here must also be fixed. Therefore, restricting the automorphisms corresponding to b and c to the subtree starting from C(1) yields the same mapping/result. This identification might be more natural if we identify the nodes with the dyadic rationals in (0, 1) as follows: 
   - 1/2 is identified with the root R
   - C(1) is identified with 1/4 and C(2) is identified with 3/4
   - Similarly, if a node is identified with r/2^k where r is odd, then its two children is identified with (2r-1)/2^(k + 1) and (2r+1)/2^(k + 1)