How to deal with intransitivity if you are a young vampire

A question at a talk in Bordeaux made me realise that a lemma I considered to be trivial and universally known may be neither. A vampire movie I saw last weekend convinced me that this was a matter of broader interest.

A dark-haired girl called Eli compensates for her inability to metabolise chocolate by her ability to solve Rubik’s cube. She tells her playmate Oskar to do the corners first. Let us see why this is a reasonable strategy that can be applied in general.

Giving a new definition to "turning"

What we have here is a non-transitive permutation group, generated by the valid moves (turn) in a Rubik’s cube. What is being permuted is the little squares on the sides; the group is non-transitive because you cannot send a corner square to the center, or to a side. The set being acted upon (i.e., the set of little squares) decomposes into three sets: corners squares, side squares and center squares. We can thus speak of three groups (puzzles); if you solve each one of them (i.e., if, in each of them, you know how to get back to the “neutral”, or identity, position where all squares on each face are of one colour) then you’ve solved the original puzzle.

Now, slow down there, Eli. This last sentence is essentially correct, but things are a little more complicated than they appear at first.

For starters, there’s no guarantee that this is a direct product. More concretely: if you do the corner squares first, and then try to solve the rest, you’ll find it hard not to ruin your masterwork – while some ways of permuting side squares leave corner squares untouched, some don’t, and they might be needed; you’d also see later that every way of permuting center squares move the side squares, which would already be in order. Frustrating!

The key thing here is Schreier’s lemma. (“Schreier” may be an excellent name for a character in a vampire movie, but he was actually an Austrian mathematician who died at 28 of general sepsis.) For simplicity, let us regard the set of corner squares X, on the one side, and the set of side and center squares, Y, on the other. The group G consists of all valid moves (= basic moves or compositions of basic moves); clearly, G acts on the union of X and Y (meaning exactly what you think that means: G moves squares around) and leaves X setwise invariant (meaning: corner squares don’t get moved to non-corner squares). Let H be the group of moves leaving X pointwise invariant (i.e., the moves leaving the corner squares alone). The quotient group G/H corresponds to all moves regarded just in terms of their effects on the corners (since Oskar need not care about what happens to non-corner squares at first).

What Eli is implicitly claiming is that, if we can ‘solve’ H and G/H (i.e., express any element as a product in a given set of generators) we can ‘solve’ G. The sticky question is the following – given a set of generators A for G, how do we find a set of generators for H as products of elements of A? In other words, if moving around the middle layers doesn’t give us enough to work with, how do we find compositions (= chains of moves) that also leave the corner squares intact while moving the non-corner squares in other ways? How do we know we’ve got all compositions we need to play with?

Schreier’s idea is the following: first, recall we are assuming Oskar can solve the corners (equivalent to the problem of a 2x2x2 Rubik’s cube). Thus, Oskar can tabulate, for every single possible corner position, a sequence of moves reaching it. (This is the same as getting a coset representative for every coset of H.) Now, for every sequence in his table, and every element g in the set A of basic moves, he can do the following: do the sequence of moves, then apply g, and then (using his table again, backwards) solve the resulting coset position. The resulting sequence h of moves will take a position with solved corners to another, possibly different, position with solved corners. (In other words, h lies in H.) Schreier’s lemma (which isn’t hard to prove, and will be left to mathematical minded readers as an exercise if they don’t already know it) assures us that the set of all such h obtained in this fashion generates H. In other words, this set is enough for Oskar to work with, once he has already solved the corners.

(It’s easy to see that this shows that, given a group G with a normal subgroup H, the diameter of G is bounded by three times thee diameter of G/H times the diameter of H. There’s a slightly more optimised statement in Babai and Seress’s 1992 paper in European J. Combin.)

Advertisements

About valuevar

I am a number theorist with side interests in combinatorics and group theory.
This entry was posted in Uncategorized and tagged , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s