Cayley, Zig-Zag and Rubik

In order to find out which finite groups are natural and especially whether the Rubik cube group is natural, one has to understand the semi-direct product of two groups. A finite group is natural if and only if one can produce a metric space such that there is exactly one group structure (up to isomorphism) which can be planted on that metric space so that all left and right translations and the inverse operation are isometries. One can assume that the metric space is a weighted Cayley graph. Now, there is a product for Cayley graphs which is compatible with the semi-direct product (Theorem 2.3 of the Alon-Lubotzky-Wigderson paper “Semi-direct product in groups and zig-zag product in graphs: Connections and applications”). For establishing that semi-direct products of natural groups are natural, the zig-zag product has to be extended to weighted graphs: put weights on the generators of the semi-direct product given by the zig-zag product. This product is very natural and just does what the semi-direct product describes. A simple way to describe this is to add 1 to the set of generators. The direct product between two groups is then on the Cayley graph level the Shannon product of the graphs (really cool appearance again of the arithmetic of graphs we have looked at a couple of times). For a semi-direct product , where the product between two generators in the normal fibers N depends on the group multiplication in the base manifold H. one just has to write down zig-zag generators encoding this. The zig and the zag are on the fibers, the – is in the base.