# How to get group of hypercube rotations as a subgroup of symmetric group?

How do I find generators of group of rotations of d-dimensional cube into itself when viewed as a subgroup of symmetric group of order $2^d$?

This is related to my previous question but not specializing to $d=3$

-
Without having thought about it much, I'd guess that we're still just permuting the diagonal lines... Do you know if that's true? –  Aaron Mazel-Gee Dec 22 '10 at 12:26
Have a look at jucs.org/jucs_6_1/the_automorphism_group_of/Harary_F.pdf and the references therein. –  Alex B. Dec 22 '10 at 13:16

I'll describe the cube, the symmetries of the cube, and the generators of the symmetry of the cube.

The plus–minus–stars description of the faces of a cube:

The d-dimensional cube can be thought of as the set of points in Rd with coordinates between −1 and +1.

Its vertices are all sequences of plusses and minuses of length d. For d=2 you get the four vertices { ++, +−, −+, −− }. For d=3 you get the eight vertices { +++, ++−, …, −−+, −−−}.

Its edges are obtained from vertices by allowing one of the coordinates to vary. For d=2 you get the four edges { ☆+, ☆−, +☆, −☆ } where for instance +☆ = { (1,y) : −1 ≤ y ≤ 1 } and ☆− = { (x,−1) : −1 ≤ x ≤ 1 }. For d=3 you get the twelve edges { ☆++, ☆+−, …, −+☆, −−☆ }.

Its 2-faces are obtained from vertices by allowing two of the coordinates to vary. For d=2 you get the single face { ☆☆ } where ☆☆ = { (x,y) : −1 ≤ x,y ≤ 1 }. For d=3 you get the six faces { ☆☆+, ☆☆−, ☆+☆, ☆−☆, +☆☆, −☆☆ }.

Its k-faces for k ≤ d are obtained from vertices by allowing k of the coordinates to vary.

For some people the cube is defined by its k-faces for 0 ≤ k ≤ d. A symmetry of Rd is defined by what it does to an affine basis such as the all −1s vector combined with the vertices of the cube with exactly 1 coordinate with a +1 and d−1 coordinates with a −1. So a symmetry is uniquely determined by where it sends the 0-faces (the vertices).

The symmetries of the cube as signed permutations:

A symmetry of the cube must take k-faces to k-faces. In particular, it must take edges to edges. Since it is determined by what it does to the vertices, we get two distinct operations:

• for each coordinate, we must send it to another coordinate
• for each coordinate, we can either reverse it or not

For instance ☆++ can be sent to any of the other edges, like −☆+. For the first point, we see that the first coordinate has been sent to the second coordinate (permuting the stars). For the second point we have two possibilities based on what happens to the vertices inside ☆++: we must send { +++, −++ } to { −++, −−+ }, but we can do this in two distinct ways (negating the sign or not).

For the first point, we get the action of the symmetry group on certain "blocks" gives rise to the symmetric group on d objects. For the second point, we get that the action of the symmetry group on each block gives rise to the symmetric group on 2 objects.

In other words, for every coordinate we have to decide where to send it and whether to negate it. The collection of all such decisions is called the group of signed permutations, also known as the hyperoctahedral group. Using the matrix or coordinate representation it is easy to check that all such signed permutations are in fact symmetries of the cube.

For instance, for d=2 we could say "switch the coordinates, then negate the first coordinate," which can be written simply as (x,y)↦(−y,x) in function notation, or in matrix notation: \begin{bmatrix}0&1\\-1&0\end{bmatrix}

More compactly, we could say [1,2]↦[-2,1] where we permute the coordinates and mark which coordinates get negated. The action on the vertices is easy to describe: it sends [ ++, +−, −+, -- ] to [ −+, ++, −−, +− ].

In general, to describe such a symmetry we need to choose a permutation of the vertices (an element of the symmetric group on d objects), and then d choices of ± to decide whether to negate a coordinate or not. The size of the group is thus d!⋅2d and the structure of the group is the wreath product of Sym(d) acting on Sym(2), and the permutation structure of the group on the vertices is more specifically the product action. In GAP this is written as:

WreathProductProductAction( SymmetricGroup(2), SymmetricGroup(d) );


The generators of the symmetry group on the vertices:

The part of the symmetry group that just permutes the coordinates without doing any negating is called the symmetric group and has two common generating sets:

• { (1,2), (2,3), …, (d−1,d) }, the coxeter generators, and
• { (1,2,3,…,d), (1,2) }, the d-cycle generating set.

The Coxeter generators are better for many theoretical reasons, and the d-cycle generating set is very short and good for computational reasons.

This part of the symmetry group can switch the first coordinate with any other coordinate, and so to finish generating the group it in fact suffices to merely switch the sign of one coordinate. Thus we have the two generating sets:

• { (1,2), (2,3), …, (d−1,d), −d }, the coxeter generators, and
• { (1,2,3,…,d), (1,2), −d }, a d-cycle generating set

The presentation of the group on the Coxeter generators is very nice. Call them g(1), g(2), … g(d−1), g(d). Then we always have g(k)2 = 1 is the identity, g(i)⋅g(j) = g(j)⋅g(i) as long as 1 ≤ i ≤ d−2, and i+2 ≤ j ≤ d, that is, as long as i and j are not adjacent. Furthermore, g(k)⋅g(k+1)⋅g(k) = g(k+1)⋅g(k)⋅g(k+1) for 1 ≤ k ≤ d−2, but for k = d−1 we have the longer: g(d−1)⋅g(d)⋅g(d−1)⋅g(d) = g(d)⋅g(d−1)⋅g(d)⋅g(d−1).

If you label the vertices from 1 to 2d, then it is a little bit of a hassle to write down the generators, just because there are so many points. I would probably just use:

GeneratorsOfGroup( symmetry_group );


in GAP myself, but you could write them out if you wanted.

-