- Joined
- Dec 24, 2015

- Messages
- 1,478

- Likes
- 936

Thread starter
#1

Foreword: I've been sitting on this idea for months, as a potential approach to lowering megaminx God's number bounds, but kept getting side tracked. Might as well post it publicly.

On a 3×3×3 and related puzzles (e.g. big cubes), there is a considerable amount of variety in the types of subgroups generated by face moves. (We will not consider generating sets with move sequences longer than one move, e.g. ⟨R U R', F' U F⟩, although that is interesting in its own right.) First off, we have the well known constraints that adding up the orientations of all eight corners will give a number divisible by 3, and likewise that adding up the orientations of all twelve edges will give a number divisible by 2. We also have an additional parity constraint on the permutation parity of all twenty pieces. We can then classify the subgroups by whether they have any further constraints beyond these.

The variety of subgroups we can get on a 3×3×3 stems from the fact that the basic moves—the quarter turns—have order 4, which is a composite number. This allows us to introduce half turns successively, which can introduce interesting structure. This is all to build up to the main point, which is that megaminx subgroups are a lot more boring, because every face move has order 5, which is prime! There's no such thing as a half turn, or a third turn, or a quarter turn. You get 1/5, 2/5, 3/5 and 4/5. Nothing else. Furthermore, from any one of these four choices, we can recover the other three by repeatedly doing whichever one we choose. For example, from a U2 move, you can get U by doing it three times, U2' by doing it three times, and U' by doing it two times.

This is what the classification of megaminx subgroups is like. Consider the 12 possible face moves as vertices of the icosahedral graph; let the adjacency graph be the subgraph induced by whatever moves we're restricting ourselves to.

Unlike on a 3×3×3, the only time we ever get nontrivial constraints on the corner orientation is when the fourth category is involved, which is a pretty degenerate and uninteresting case. The fifth category is also generally uninteresting because it reduces to the previous categories, but for those paying attention, this was how Ben and I proved an upper bound of 34 moves for solving a kilominx. None of these categories for megaminx include "weird constraints" like how ⟨U, R⟩ on a 3×3×3 can't arbitrarily permute corners even if they're in the same orbit.

But what if we could have some notion of half turns on a megaminx? This is almost certainly not a new idea; if you look at the PLL alg R2 U2 R2' U R2 U2 R2', it's structurally very similar to ⟨R2, U⟩ algs that might be used as PBL for square-1 or 2×2×2. In general, if you always start with a clockwise R2, and alternate between R2 and R2' thereafter, it will be impossible to twist corners. We can collect the states attainable via such ⟨"R2.5", U⟩ sequences where the "R2.5"s always alternate between R2 and R2', starting with R2. If you do this on an actual megaminx, observe that there's a block formed by three edge pieces and a corner piece attached to the right face's centre that just rotates back and forth.

If we further restrict this collection to the states with an even number of R2.5 moves, this leaves us a collection of states where the aforementioned block of pieces is solved. This

While the set is not a group with the group operation inherited from the megaminx group, it

It's not immediately obvious, but you can in fact solve

And that's about all of the usefulness of the ⟨R2.5, U⟩ not-really-a-subgroup explored in one short paragraph. This isn't super interesting on its own; it gets more interesting when we throw in

We can extend exactly the same idea to get ⟨U, L2.5, R2.5⟩. Previously, when we were looking at only ⟨U, R2.5⟩, it didn't really matter whether we started with R2 or with R2', since these are equivalent up to mirroring. For ⟨U, L2.5, R2.5⟩, we have four choices. We could start with L2/R2, or L2'/R2', or L2/R2', or L2'/R2. The first two choices are equivalent up to mirroring, but in fact all of these lead to essentially equivalent sets of states and group actions/homomorphisms. As above, we can readily compute the number of states: 9!/2 × 7! × 2² / 2 = 1,828,915,200. We also define other not-really-groups, generated by sets like ⟨U, L2.5, R⟩. This

In the opposite direction, we can also consider ⟨U2.5, R2.5⟩, which is isomorphic to the ⟨U2, R2⟩ group on a 3×3×3, a tiny group with only 12 states. Again, here it doesn't really matter whether we start with U2/R2 or U2'/R2, etc.

How many more faces can we throw into the mix while still being able to preserve some notion of corner orientation? For instance, if we try to generalise this to ⟨U, L2.5, F2.5, R2.5, bR2.5, bL2.5⟩, that's way too much freedom and it turns out that we

(There are a few different types of "corner twists" we might want to think about. One is twisting a single corner while leaving the rest of the puzzle intact; this is impossible no matter what moves you use. One is to twist two corners in opposite directions. This is sometimes possible, but a pure two-twist alg can be hard to find. The most general notion is to twist one corner in-place, while possibly leaving the rest of the puzzle completely messed up. This is a lot easier to find algs for, so it's the definition we'll use. Note that on some puzzles, e.g. a skewb, the second and third types of corner twists are not necessarily equivalent.)

If 6-gen is too much, let's scale back to 3-gen and see what happens. It turns out that ⟨U, R2.5, F2.5⟩

How many states are in ⟨U, R2.5, F2.5⟩? The F-dfR edge (green-cream with scramble orientation) and the R-dbR edge (red-pink) effectively track whether the F and R faces (respectively) have had an even or odd number of turns so far (2^2 possibilities). These two pieces will always stay attached to the F and R centres, respectively. For corner permutation, it's possible to do an A perm with ⟨U, R2.5⟩, and since we can set up any three corners anywhere, we can achieve every even permutation (10!/2).

Edges are more interesting. Naïvely, it might look like there's only one orbit of edges, consisting of all 12 edges moved by the U, R and F moves. Or maybe you'd think to exclude the green-cream and red-pink edges, since those don't really move, so there's one orbit of 10 edges. Still wrong! There are actually two "orbits", but to make this more precise, we can consider only states where an even number of R2.5 moves and an even number of F2.5 moves have been made. Among these states, there are two orbits of edges: one with seven pieces, and one with three pieces. As with the corners, we can do a U perm with ⟨U, R2.5⟩, and since we can set up any three edges among the seven-edge orbit anywhere, we can achieve every even permutation for that orbit (7!/2). For the three-edge orbit, we can cycle those with R2 F2 R2' F2' (which also affects some corners, but we've already established that corners can be arbitrarily evenly permuted), so we get all even permutations for this orbit as well (3!/2). (The three-edge orbit is analogous to the E-slice edges for ⟨U, R2, F2⟩ on a 3×3×3.)

Multiplying all of these factors together, we get \( 2^2\times(10!/2)\times(7!/2)\times(3!/2)=54,867,456,000 \) states in ⟨U, R2.5, F2.5⟩.

What about 4-gen? Unfortunately, we've already shown above that we can twist corners in ⟨U, L2.5, F2.5, R2.5⟩. I'm not sure if this even preserves edge orientation; I think it does, but I haven't tried very hard to find an edge-flip alg in this move set. The 5-gen and 6-gen sets ⟨U, L2.5, F2.5, R2.5, bR2.5⟩, ⟨U, L2.5, F2.5, R2.5, bR2.5, bL2.5⟩ might be almost equivalent to the normal-move sets ⟨U, L, F, R, bR⟩ and ⟨U, L, F, R, bR, bL⟩ in terms of the states reachable (modulo having a few edge pieces "bandaged" to the centres).

What about ⟨U2.5, R2.5, F2.5⟩? What about using more faces than just those on one hemisphere? All left as an exercise for the reader (because I haven't done the work myself yet!).

**tl;dr**: if it took me a long time to write this, it should take you a long time to read itOn a 3×3×3 and related puzzles (e.g. big cubes), there is a considerable amount of variety in the types of subgroups generated by face moves. (We will not consider generating sets with move sequences longer than one move, e.g. ⟨R U R', F' U F⟩, although that is interesting in its own right.) First off, we have the well known constraints that adding up the orientations of all eight corners will give a number divisible by 3, and likewise that adding up the orientations of all twelve edges will give a number divisible by 2. We also have an additional parity constraint on the permutation parity of all twenty pieces. We can then classify the subgroups by whether they have any further constraints beyond these.

- No additional constraints; we get the whole group. Examples: ⟨U, D, L, R, F, B⟩, ⟨U2, D, L, R, F, B⟩, ⟨D, L, R, F, B⟩, ⟨D, L, R, F2, B⟩, ⟨D, L2, R, F2, B⟩.
- Some pieces that can move are stuck within certain orbits, but otherwise have no additional constraints. Examples: ⟨U, L, R, F⟩, ⟨U, R, F⟩.
- Same as previous, but edges can never be flipped. Examples: ⟨U, L, R, F2⟩, ⟨U, R, F2⟩, ⟨U, L, R⟩, ⟨U, L2, R⟩.
- Same as previous, but corners can never be twisted. Examples: ⟨U, D, L2, R2, F2, B2⟩, ⟨U, D, R2, F2⟩.

(Side note: There is no face-move-generated subgroup where corners can't twist but edges can flip. This changes if you allow slice moves.) - Single moves, or a collection of single moves on non-touching faces. Examples: ⟨U⟩, ⟨U, D⟩, ⟨U, D2⟩.
- Weird constraints that don't fall in the above categories. Examples: ⟨U2, D2, L2, R2, F2, B2⟩, ⟨U, R⟩, ⟨U, R2⟩.

The variety of subgroups we can get on a 3×3×3 stems from the fact that the basic moves—the quarter turns—have order 4, which is a composite number. This allows us to introduce half turns successively, which can introduce interesting structure. This is all to build up to the main point, which is that megaminx subgroups are a lot more boring, because every face move has order 5, which is prime! There's no such thing as a half turn, or a third turn, or a quarter turn. You get 1/5, 2/5, 3/5 and 4/5. Nothing else. Furthermore, from any one of these four choices, we can recover the other three by repeatedly doing whichever one we choose. For example, from a U2 move, you can get U by doing it three times, U2' by doing it three times, and U' by doing it two times.

This is what the classification of megaminx subgroups is like. Consider the 12 possible face moves as vertices of the icosahedral graph; let the adjacency graph be the subgraph induced by whatever moves we're restricting ourselves to.

- No additional constraints. (Note that on a megaminx, the parity of the edges and the parity of the corners must both be even, in contrast to a 3×3×3, where they only need to be both even or both odd.)
- Pieces stuck within orbits, but otherwise no additional constraints. Examples: ⟨U, L, F, R⟩, ⟨U, L, F, R, bR⟩.

Any time we have three mutually touching faces, and the adjacency graph of chosen faces is connected, we end up in this category. (Connectedness of the graph is important because of the permutation parity constraint.) - Same as previous, but edges can never be flipped. Examples: ⟨U, L, R⟩, ⟨L, F, R, bR⟩, ⟨L, U, R, dbR, D, dbL⟩.

Any time we have a bipartite connected adjacency graph, we end up in this category. Up to symmetry, there are two distinct choices of six-move sets that generate subgroups in this category. - Single moves. Examples: ⟨U⟩, ⟨R⟩, you get the idea.
- Some combination of the above three categories on non-touching groups of faces. Examples: ⟨U, L, F, D, dbR⟩ = ⟨U, L, F⟩ × ⟨D, dbR⟩; ⟨U, bL, dfL, dbR⟩ = ⟨U, bL⟩ × ⟨dfL⟩ × ⟨dbR⟩.

(Basically, classify each individual component of the adjacency graph, then throw them together.)

Unlike on a 3×3×3, the only time we ever get nontrivial constraints on the corner orientation is when the fourth category is involved, which is a pretty degenerate and uninteresting case. The fifth category is also generally uninteresting because it reduces to the previous categories, but for those paying attention, this was how Ben and I proved an upper bound of 34 moves for solving a kilominx. None of these categories for megaminx include "weird constraints" like how ⟨U, R⟩ on a 3×3×3 can't arbitrarily permute corners even if they're in the same orbit.

But what if we could have some notion of half turns on a megaminx? This is almost certainly not a new idea; if you look at the PLL alg R2 U2 R2' U R2 U2 R2', it's structurally very similar to ⟨R2, U⟩ algs that might be used as PBL for square-1 or 2×2×2. In general, if you always start with a clockwise R2, and alternate between R2 and R2' thereafter, it will be impossible to twist corners. We can collect the states attainable via such ⟨"R2.5", U⟩ sequences where the "R2.5"s always alternate between R2 and R2', starting with R2. If you do this on an actual megaminx, observe that there's a block formed by three edge pieces and a corner piece attached to the right face's centre that just rotates back and forth.

If we further restrict this collection to the states with an even number of R2.5 moves, this leaves us a collection of states where the aforementioned block of pieces is solved. This

*is*a subgroup of the megaminx group, but it's*not*a subgroup generated by half turns, because half turns don't really exist on a megaminx and we're sorta hacking it in. If we don't restrict the collection to those with an even number of R2.5 moves, then we don't even get a group. (Proof: R2 is in this set, but (R2)^2 = R' isn't.) However, we do get a transitive group*action*of the free product \( (\mathbb Z/2)*(\mathbb Z/5) \) on this set in the natural way: the \( (\mathbb Z/2) \) part corresponds to R2.5 moves (R2 or R2' depending on how the block is oriented) while the \( (\mathbb Z/5) \) part corresponds to U/U2/U2'/U' moves.While the set is not a group with the group operation inherited from the megaminx group, it

*is*possible to define a group operation on the set by going through move sequences. Given two states \( X \) and \( Y \), to compute the product \( XY \), we pick some move sequences \( S_X,S_Y\in(\mathbb Z/2)*(\mathbb Z/5) \) such that \( S_X \) applied to a solved megaminx produces state \( X \) and \( S_Y \) applied to a solved megaminx produces state \( Y \). Then we declare the state obtained by \( S_XS_Y \) to be the result of multiplying \( X \) and \( Y \). It is not a priori obvious that this is well-defined, since the choices of \( S_X \) and \( S_Y \) are very much not unique. (Exercise: prove this.) From this and the above group action, we get a group homomorphism from \( (\mathbb Z/2)*(\mathbb Z/5) \) to the ⟨"R2.5", U⟩ states. Note that while this is a*subset*of the megaminx group and it's a*group*, it's*not a subgroup*of the megaminx group, because our group operation is not compatible with the usual megaminx group operation.It's not immediately obvious, but you can in fact solve

*every*PLL case in this move set. (Contrast a 3×3×3, where ⟨R2, U⟩ can solve only the edge PLLs.) The worst case is a 5-cycle of edges iirc, requiring 20 or so moves. It's not just the PLLs, of course. The megaminx analogue of TTLL can also be solved entirely in ⟨R2.5, U⟩, since we never need to orient corners there. To compute the total number of states in ⟨R2.5, U⟩, we note that there are seven mobile corners that can't twist and will always have even parity (7!/2), six mobile edges that can't flip (6!), and one block on the right face that can point in either of two directions (2), although this is overcounting by a factor of two since the edge permutation parity will uniquely determine which way the block is pointing. This gives a value of 7!/2 × 6! × 2 / 2 = 1814400.And that's about all of the usefulness of the ⟨R2.5, U⟩ not-really-a-subgroup explored in one short paragraph. This isn't super interesting on its own; it gets more interesting when we throw in

*more faces*.We can extend exactly the same idea to get ⟨U, L2.5, R2.5⟩. Previously, when we were looking at only ⟨U, R2.5⟩, it didn't really matter whether we started with R2 or with R2', since these are equivalent up to mirroring. For ⟨U, L2.5, R2.5⟩, we have four choices. We could start with L2/R2, or L2'/R2', or L2/R2', or L2'/R2. The first two choices are equivalent up to mirroring, but in fact all of these lead to essentially equivalent sets of states and group actions/homomorphisms. As above, we can readily compute the number of states: 9!/2 × 7! × 2² / 2 = 1,828,915,200. We also define other not-really-groups, generated by sets like ⟨U, L2.5, R⟩. This

*does*have twistable corners, as well as a larger number of freely-movable pieces, so the total number of states would be \( 3^9\times(10!/2)\times10!\times2/2\approx1.296\times10^{17} \).In the opposite direction, we can also consider ⟨U2.5, R2.5⟩, which is isomorphic to the ⟨U2, R2⟩ group on a 3×3×3, a tiny group with only 12 states. Again, here it doesn't really matter whether we start with U2/R2 or U2'/R2, etc.

How many more faces can we throw into the mix while still being able to preserve some notion of corner orientation? For instance, if we try to generalise this to ⟨U, L2.5, F2.5, R2.5, bR2.5, bL2.5⟩, that's way too much freedom and it turns out that we

*can*flip edges and twist corners with this move set; for example, F2 R2 U2' L2 F2' R2' F2 R2 F2' R2' U' L2' U twists the UFL corner anticlockwise, while R2 bR2 R2' bL2 L2 F2 R2 F2' R2' L2' bL2' bR2' flips the FR edge. This is in contrast to how the 3×3×3 analogue, ⟨U, L2, F2, R2, B2⟩, preserves both edge orientation and corner orientation.(There are a few different types of "corner twists" we might want to think about. One is twisting a single corner while leaving the rest of the puzzle intact; this is impossible no matter what moves you use. One is to twist two corners in opposite directions. This is sometimes possible, but a pure two-twist alg can be hard to find. The most general notion is to twist one corner in-place, while possibly leaving the rest of the puzzle completely messed up. This is a lot easier to find algs for, so it's the definition we'll use. Note that on some puzzles, e.g. a skewb, the second and third types of corner twists are not necessarily equivalent.)

If 6-gen is too much, let's scale back to 3-gen and see what happens. It turns out that ⟨U, R2.5, F2.5⟩

*does*preserve both edge orientation and corner orientation. Without loss of generality, suppose we start with R2/F2 (as opposed to R2'/F2', etc.). The choice actually matters here, but if we choose a different convention, we can just conjugate the whole thing by R2 or F2 or R2 F2 as necessary. To see why the choice matters, observe that R2 F2 R2' F2' U2 F2 R2 F2' R2' U2' and R2' F2 R2 F2' U2 F2 R2' F2' R2 U2' have different orders; the former is a pair of 3-cycles and so has order 3, while the latter is a pair of 2-cycles and a 3-cycle, and so has order 6. In particular, this also means that our group action does not lead to a group homomorphism in the way described a couple of paragraphs above: ⟨U, R2.5, F2.5⟩ doesn't even behave like a group in any meaningful sense. (If we did have a homomorphism, then conjugating an element shouldn't change its order.)How many states are in ⟨U, R2.5, F2.5⟩? The F-dfR edge (green-cream with scramble orientation) and the R-dbR edge (red-pink) effectively track whether the F and R faces (respectively) have had an even or odd number of turns so far (2^2 possibilities). These two pieces will always stay attached to the F and R centres, respectively. For corner permutation, it's possible to do an A perm with ⟨U, R2.5⟩, and since we can set up any three corners anywhere, we can achieve every even permutation (10!/2).

Edges are more interesting. Naïvely, it might look like there's only one orbit of edges, consisting of all 12 edges moved by the U, R and F moves. Or maybe you'd think to exclude the green-cream and red-pink edges, since those don't really move, so there's one orbit of 10 edges. Still wrong! There are actually two "orbits", but to make this more precise, we can consider only states where an even number of R2.5 moves and an even number of F2.5 moves have been made. Among these states, there are two orbits of edges: one with seven pieces, and one with three pieces. As with the corners, we can do a U perm with ⟨U, R2.5⟩, and since we can set up any three edges among the seven-edge orbit anywhere, we can achieve every even permutation for that orbit (7!/2). For the three-edge orbit, we can cycle those with R2 F2 R2' F2' (which also affects some corners, but we've already established that corners can be arbitrarily evenly permuted), so we get all even permutations for this orbit as well (3!/2). (The three-edge orbit is analogous to the E-slice edges for ⟨U, R2, F2⟩ on a 3×3×3.)

Multiplying all of these factors together, we get \( 2^2\times(10!/2)\times(7!/2)\times(3!/2)=54,867,456,000 \) states in ⟨U, R2.5, F2.5⟩.

What about 4-gen? Unfortunately, we've already shown above that we can twist corners in ⟨U, L2.5, F2.5, R2.5⟩. I'm not sure if this even preserves edge orientation; I think it does, but I haven't tried very hard to find an edge-flip alg in this move set. The 5-gen and 6-gen sets ⟨U, L2.5, F2.5, R2.5, bR2.5⟩, ⟨U, L2.5, F2.5, R2.5, bR2.5, bL2.5⟩ might be almost equivalent to the normal-move sets ⟨U, L, F, R, bR⟩ and ⟨U, L, F, R, bR, bL⟩ in terms of the states reachable (modulo having a few edge pieces "bandaged" to the centres).

What about ⟨U2.5, R2.5, F2.5⟩? What about using more faces than just those on one hemisphere? All left as an exercise for the reader (because I haven't done the work myself yet!).

Likes:
CuberStache and Keroma12