2
$\begingroup$

Want to check if a given permutation: $(17)(35)(28)(46)$ is valid?

By a valid permutation mean a permutation, which is also a symmetry of the cube (or oriented cube).

The only way I know is: drawing a cube with vertices labeled $1$ through $8.$ Then draw the same cube but swap the vertices according to the permutation. Then we just have to make sure edges and faces are preserved. So if $12$ is an edge of the original cube, $12$ should be an edge of the permuted cube.

Is there an algebraic way, or based on group action, or any other approach that (without actual drawing of cube) ascertains that $ (17)(35)(28)(46)$ is a valid permutation?

The drawing based approach, though is possible here; but will be not helpful in bigger examples.

$\endgroup$
6
  • 7
    $\begingroup$ I am not clear about what exactly you are asking. (i) Are the vertices of the cube already labelled and you are asking whether a given permutation $\pi\in S_8$ arises from the action of the symmetry group of the cube on the $8$ vertices? (ii) Or perhaps you are asking whether given $\pi\in S_8$ we can label the vertices so that $\pi$ arises from a symmetry. $\endgroup$
    – ancient mathematician
    Aug 6 at 6:36
  • $\begingroup$ @ancientmathematician The former (first) one, but your comment has made me interested in the second one too; though it is obvious that $24\lt 8!.$ Seems both ways are the same. $\endgroup$
    – jiten
    Aug 6 at 8:00
  • 2
    $\begingroup$ @ancientmathematician To quote from summary of class: Thinking of elements of $\text{Cub}$ as of $S_8$ allows to compute compositions easily by multiplying the permutations. However, we still have some disadvantages: $S_8$ is fairly large, and a big disadvantage is that we can't tell the types of symmetries apart via their cycle type. (2.) Specifically, quadruple $2$ cycles could either be represent face rotations or edge rotations. We can't tell face rotations or edge rotations apart just by looking at their cycle type. These are the "trouble-makers". //contd. below. $\endgroup$
    – jiten
    Aug 6 at 9:17
  • 2
    $\begingroup$ 3. So analyzed $\text{Cub}$ via its action on: four space diagonals. We then took some some permutations of the vertices (elements of $S_8$) and thought about how they would permute the space diagonals instead to recognize those elements of $\mathrm{Cub}$ as elements of $S_4$ rather than $S_8.$ With this action, we saw that we can tell apart the various symmetry categories by their cycle types. $\endgroup$
    – jiten
    Aug 6 at 9:17
  • 2
    $\begingroup$ I do not think there is any algebraic way of distinguishing the $(ab)(cd)(ef)(gh)$ (conjugacy more or less means algebraically the same). So we need to use the exact labelling in question. "Drawing the cube" is just a shorthand way of doing this, we can perform the operations without the picture. $\endgroup$
    – ancient mathematician
    Aug 6 at 9:50

1 Answer 1

Reset to default
8
$\begingroup$

The question you ask is a special case of what is called the membership problem.

The membership problem: Let $G$ be a group, and $H$ a subgroup. Is there an algorithm which takes an element $g\in G$ and outputs whether $g\in H$?

In this case $G=S_8$ and $H=\textrm{Sym}(\textrm{cube})$. For arbitrary groups, the membership problem is undecidable, however for subgroups of permutation group it is decidable, and the most well-known algorithm is called the Schreier-Sims algorithm. This runs in polynomial time.

One can implement this algorithm in your particular case, but there is also a more elementary method if you set up the labelling on the cube in a clever way. In your question you didn't specify how the vertices are labelled, but as you pointed out in the comments relabelling doesn't fundamentally change the problem.

For my labelling I am not going to use $\{1,2,\dots,8\}$, instead I will use $\{1,2,3,4,\bar{1},\bar{2},\bar{3},\bar{4}\}$. I am going to label according to the figure below. Notice I have chosen the labelling to represent the fact that the cube contains two regular tetrahedra inside it which together define its eight vertices. On the level of groups this reflects the fact that the symmetry group of the tetrahedron, $S_4$, is an index two subgroup of $\textrm{Sym}(\textrm{cube})$.

enter image description here

Now, as a subgroup of $\textrm{Perm}\{1,2,3,4,\bar{1},\bar{2},\bar{3},\bar{4}\}$, the symmetry group of the cube is generated by $S_4=\textrm{Perm}\{1,2,3,4\}$ (which is the group of symmetries of the blue tetrahedron) together with the permutation $$\sigma=(1\;\bar{1})(2\;\bar{2})(3\;\bar{3})(4\;\bar{4}).$$ This has the effect of swapping the red and blue tetrahedra, and as a symmetry is the antipodal map.

Now suppose we have an element of $\textrm{Sym}(\textrm{cube})$, then it can be expressed as a finite combination of permutations $g_1\sigma g_2 \sigma g_3\sigma\cdots\sigma g_n$ of some length, where the $g_i\in S_4$. We can ask what such a product looks like in cycle notation.

Well if $g\in\textrm{Perm}\{1,2,3,4\}$, then $\sigma g\in\textrm{Perm}\{\bar{1},\bar{2},\bar{3},\bar{4}\}$. Similarly, if $h\in\textrm{Perm}\{\bar{1},\bar{2},\bar{3},\bar{4}\}$, then $\sigma h\in\textrm{Perm}\{1,2,3,4\}$. Therefore, the element $\sigma g_2 \sigma g_3\sigma\cdots\sigma g_n$ will lie in either $\textrm{Perm}\{1,2,3,4\}$ or $\textrm{Perm}\{\bar{1},\bar{2},\bar{3},\bar{4}\}$, depending on whether $n$ is even or odd. Thus $g_1\sigma g_2 \sigma g_3\sigma\cdots\sigma g_n$ will be one of the following

  1. An element of $\textrm{Perm}\{1,2,3,4\}$
  2. An element of $\textrm{Perm}\{\bar{1},\bar{2},\bar{3},\bar{4}\}$
  3. A product of two permutations, one from $\textrm{Perm}\{1,2,3,4\}$ and one from $\textrm{Perm}\{\bar{1},\bar{2},\bar{3},\bar{4}\}$

Moreover it is easy to see that every permutation which is in one of these forms is a symmetry of the cube. Therefore we have proved the following easy solution to the membership problem in this case:

Proposition: An element of $\textrm{Perm}\{1,2,3,4,\bar{1},\bar{2},\bar{3},\bar{4}\}$ lies in $\textrm{Sym}(\textrm{cube})$ if and only if each cycle lies in either $\textrm{Perm}\{1,2,3,4\}$ or $\textrm{Perm}\{\bar{1},\bar{2},\bar{3},\bar{4}\}$.

Edit: after posting my answer I saw OP had added a couple of extra comments. To relate my answer to those, note that each of the four diagonals of the cube has exactly one endpoint in the blue tetrahedron, and one in the red tetrahedron. Tus thinking about permuting diagonals is equivalent to thinking about symmetries of one of the tetrahedra. The corresponding $S_4$ subgroup, which I said was index 2, is the group of orientation preserving symmetries of the cube.

The issue raised in the class summary is about recognising the type of symmetry of the cube (rotation about a vertex, rotation about the midpoint of an edge, reflection, etc) which is not the question you asked, and so not the question I have answered.

$\endgroup$
1
  • $\begingroup$ So lucky to have your answer again. Thanks a lot. $\endgroup$
    – jiten
    Aug 6 at 9:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.