[sixfiveotwo]

My intuition when reading the first lines of this article was that, just like when searching exhaustively for the correct combination on a padlock, one would cycle through each subgroup, where each of them would represent a digit on the lock. On the lock, one would do 9 steps (not 10, as this would loop the lock to a previously seen combination) on the least significant digit, then propagate the carry to the next digits. But it seems that this more complicated than that, as the steps at which subgroups connect (the carry) are not always the same?

[sixfiveotwo]

Clearly that first intuition doesn't work. The Hamiltonian cycle for decimal numbers is perhaps an equivalent of grey code? And if it exists, is there a connection with the Rubik's cube cycle?

[robryk]

The reason why it's not so simple is that various operations on the cube do not commute (whereas rotations of different wheels on a combination lock do).

[sixfiveotwo]

Yes indeed, I realized that it was way more complicated than what I initially imagined.

When I first read the article, the sequence of subgroups that were described evoked that image of a combination lock to me:

< UR >

< U, R >

< U, R, D >

< U, R, D, L >

< U, R, D, L, F >

The behavior of the basic operations on the cube reminds me of the product of quaternion base vectors (i,j,k). For instance, the product of i and j would yield either k or -k depending on the order of i and j. I think the point I wanted to make is that on a combination lock, each operation on a wheel only affect that wheel, not the others, so one cannot produce another operation by combining several of them, like what we see with quaternions. However, on the cube, it is often possible to go from one combination to another by different sequences of different operations.

But that may not matter much, if all we care about is going through every possible combination exactly once, just like what one does when using gray code on binary numbers (which is why I alluded to that in my other post), and that for that purpose we can find a set of sequences of operations - let's call them large operations - that are orthogonal (and thus emulating the rotating wheel aspect of the combination lock). I suppose that these subgroups represent the large operations. The problem you bring up now is that these large operations are not commutative, and so finding a correct way to apply them to build the circuit is more involved than simply spinning the wheels on a lock.

Is that correct?

Edit: I just had a first look at cayley graphs on wikipedia, and they use quaternion rotations as an example!