An upper bound for the order of an element of the Rubik's cube group

The maximum order of an element of the Rubik's cube group R is 462 might be 462, or might be 1260, or might be something else.

Why? The Rubik's cube group is a subgroup of S₈ × S₁₂ × Z₃⁸ × Z₂¹²; the four factors here arise from possible permutations of the edge and corner pieces, and the orientations of the edges and the corners. (This is in fact twelve times as large as the actual group.) More concretely, it's the subgroup of this group consisting of quadruples (σ, τ, v, w), where σ ∈ S₈ and τ ∈ S₁₂ have the same parity, v is an element of Z₃⁸ whose coordinates sum up to zero, and w is a similar element of Z₂¹². The group operation in this group is given by working componentwise.

(If I have misunderstood what I've heard about Rubik's cubes, then please ignore the rest of this post.)

[edited, 8:48 pm: turns out I have, as the multiplication isn't exactly componentwise.]

So the order of (σ, τ, v, w) is the least common multiple of the orders of σ, τ, v, w in S₈, S₁₂, Z₃⁸, and Z₂¹² respectively. Call these o(σ), o(τ), o(v), o(w). If σ has one 7-cycle and one 1-cycle, τ has one 11-cycle and one 1-cycle, and v and w are nontrivial, then o(σ) = 7, o(τ) = 11, o(v) = 3, o(w) = 2, and so the order of (σ, τ, v, w) is lcm(7, 11, 3, 2) = 462. (This corresponds to a sequence of moves, whatever it may be, that permutes seven of the corners and eleven of the edges cyclically, and disrupts the orientations of both the corners and the edges.) Note that σ and τ are both even permutations.

Furthermore, we can't do better. I don't think there's a particularly elegant proof, but it's not hard to check by brute-force computation that no choice of the cycle types for σ and τ which gives both the same parity allows us to do better. If you let σ have one cycle of order 8, and τ have one cycle of order 7 and one of order 5, and let v, w both be nontrivial, then you'd think the order of (σ, τ, v, w) was lcm(8, 35, 3, 2) = 840, but σ is odd and τ is even. In fact, that's how I got the number 462 -- take lcm(s, t, 3, 2) where s ran over possible orders of elements of S₈ and t ran over possible orders of elements of S₁₂; the largest number you get this way is 840, but it can only come about in the way I described. 462 is the next-largest.

In case you're wondering how I came to this question -- it's easy to see if you play around with the cube that if you do the same sequence of moves over and over again, you eventually get back where you started. (Theoretically, this is a consequence of the fact that any element of a group has finite order.) So I just started to wonder how many times you might have to do the same sequence of moves on a solved cube to get it back to the solved state.

Rubik's deck of cards?

By Igor Kriz and Paul Siegel, at Scientific American: Rubik's Cube Inspired Puzzles Demonstrate Math's "Simple Groups".

The Rubik's cube can be said to be a physical embodiment of the Rubik group, which is a certain subgroup of S₄₈. (Why 48? There are 54 "facets" of the Rubik's cube, nine on each side; six of these don't move, leaving 48.) This subgroup has an easy presentation with six generators, namely rotations of the six faces. As the authors point out, other "Rubik's-type" puzzles embody groups of the same general sort.

The authors have invented puzzles based on certain sporadic groups, namely theMathieu groups M₁₂ and M₂₄ and the Conway group Co₀. These right now only exist as computer programs, although the authors claim that a physical version of the M₂₄ puzzle could be built.

A possibly interesting, although not-at-all well-defined question -- which groups are "buildable", in the sense that one can build a physical object that represents them?

The programs (which run on Windows machines) can be downloaded from Igor Kriz's home page.

Thanks to John Armstrong for pointing me to the article.

Are most groups solvable?

While trying to find a list of small groups (I needed to find a counterexample in a problem involving finite groups, and there would be some brute-force calculations involved, so I figured I wanted to work with the smallest groups possible) I came across The Groups of Order Sixteen Made Easy, by Marcel Wild, from the January 2005 American Mathematical Monthly. The paper gives a classification of the groups of order sixteen without appealing to the general theory of p-groups.

Anyway, towards the end of the paper things are put into the historical context of the theory of group extensions, and we learn that:

The groups that can be obtained from the trivial group by iteratively building cyclic extensions are called solvable. Statistically speaking “most” groups are solvable. For instance, all groups of order less than sixty are solvable.

Of course, groups of order less than sixty make up a negligible portion of all groups; it's certainly possible that all groups of order less than sixty are solvable, but most groups of order n are not solvable when n is large enough. There is the Feit-Thompson theorem, which states that every group of odd order is solvable, but numerical data for n up to 2015 shows that there seem to be more groups of even order than odd order. This isn't surprising; the number of groups of a given finite order depends strongly on the exponents of the primes in its factorization. Nor is this special to 2 -- in general numbers with lots of prime factors are the order of lots of groups.

It looks like the statement is true, though, in any reasonable sense; from Sloane's Encyclopedia, there are only 2240 integers n below 10⁵ such that there exists a non-solvable group of order n. In fact, it looks like the sequence of such numbers has roughly constant density, of about 0.0224. That should be provable or disprovable from the note given in the Encyclopedia, which gives an easy way to find such numbers. The statement that most numbers are solvable (where a number is solvable if all groups of that order are solvable) is even stronger than the statement that most groups are solvable.

But talking about a ``randomly chosen group'' seems a bit silly, anyway; the groups of a given order don't strike me as the sort of set one picks things from at random. Choosing a random element of a group seems like a much more natural operation. (Feel free to correct me if I'm wrong!)

Homophony part two

As at least two readers have pointed out, my claim that the triviality of the homophony group was part of the unwritten folklore is false. Take a look at the paper Quotients Homophones des Groupes Libres/Homophonic Quotients of Free Groups, by Mestre, Schoof, Washington, and Zagier. They use a lot of the same relations that I did in my proof; in particular damn = damn, damned = dammed, barred = bard, bass = base, jeans = genes, ruff = rough, phase = faze. (The last three of these seem to me to be the ones that most people will find.) Like my proof, v is the last generator to fall; they use chivvy = chivy or leitmotif = leitmotiv. I'm not sure how I feel about these; in both cases these seem like alternate spellings, not different words. veldt = felt, as suggested by a commenter on the earlier entry, feels "right" to me; these are quite clearly two different words with different meanings, veldt being a certain kind of open space in Africa, felt being the stuff out of which the tips of markers are made. (I think this is the one I came up with the first time I saw this problem.) They don't seem satisfied with their proofs for v, either; they introduce the space as a 27th generator, and use avowers = of ours to show the triviality of v.

The paper in question is bilingual; the proof that the English homophony group is trivial is given in French, and the proof that the French homophony group is trivial is given in English. I particularly like the acknowledgements:

The third and fourth authors were partially supported by NSF and (by the results of this paper) numerous other government agencies.

A related problem is as follows: consider the group on twenty-six letters A, B, ..., Z with the relations that two words are equivalent if they are permutations of each other and each appears as a word in some dictionary of choice. Identify the center of the group. According to Steven E. Landsburg, "The Jimmy's Book", The American Mathematical Monthly, Vol. 93, No. 8 (Oct., 1986), pp. 636-638, much work was done on this problem at Chicago in the seventies.

To get started: post = pots = stop = opts = spot = tops. Since post = pots, s and t commute; since pots = opts, o and p commute. This is clearly much harder than the homophony group problem. By the way, elation = toenail. (I've been playing lots of Scrabble recently; that set of seven letters seems to come up a lot.)

The homophony group

From Justin Roberts at UCSD, an old homework problem:

"B: (Fun for all the family, ages 6-66...)The homophony group (of English) is the group with 26 generators a,b, ..., z and one relation for every pair of English words which sound the same. Example: "knight = night" shows that k=1, "earn=urn" shows that ea=u, and so on. (Scrabble rules apply; no proper names or slang!) Prove that the group is trivial! (I would guess it's also trivial in French but probably non-trivial in Spanish and very non-trivial in Japanese!)."

I was looking for something else, but I came across this problem, which I saw before in my first algebra class when I'd just learned what a group was; it's part of the folklore, apparently, and I feel like it's good to have the folklore written down. (It might be written down somewhere on the Internet under another name, but it's hard to find because "group" is such a common word in non-mathematical circumstances.)

I can't do it. I did it before, but I remember it took a lot of looking at lists of homophones; I can't find the particular lists of homophones I used years ago. Most of the relations are simpler than they look, because generally if two words in English are spelled the same they have a lot of letters in common. Here's a partial solution -- I prove that the English homophony group is a subgroup of the free group on two generators, namely m and v. (Or maybe three.)

First, we deal with the vowels. The first homophones that come to anyone's mind are probably to = too = two. From to = too we get o = 1. Thus to = two becomes t = tw, so w = 1. (Yes, I know, w isn't a vowel...) Next, consider the relations

rain = rein = reign, sign = sine, earn = urn.

From rain = rein we get a = e. From rain = reign we get ai = eig; but since a = e we can reduce this to i = ig, or g = 1. Thus we can eliminate the "g" in sign = sine to get sin = sine, so e = 1; recalling a = e, we have a = 1. Finally, from earn = urn we have ea = u; since e = a = 1 we have u = 1.

Another candidate for "most canonical homophone" is probably there = their (I'll ignore "they're" because I don't want to deal with apostrophes); we can clip the "the" in each of these to get re = ir. But e = 1, so this is r = ir, or i = 1. Next, i = eye, but i = e = 1, so this reduces to y = 1. (Does "i" count as a word? Of course I mean "I", the first-person singular pronoun. Roberts said "Scrabble rules apply", but Scrabble rules have never had to weigh in on whether "I" is playable. Scrabble rules out words which are "always capitalized" but the way in which "I" is always capitalized seems different from the way that a proper name is.)

At this point we've shown that the letters a, e, g, i, o, u, w, and y are trivial; this set of letters shouldn't be too surprising to anyone reasonable familiar with English spelling.

There are a lot of silent k's; we take no = know. Since w = o = 1, this reduces to n = kn, so k = 1. Similarly, we can leverage the silent h with wine = whine. lam = lamb gives us b = 1, and dam = damn gives n = 1.

Somewhere around here the problem seems to get harder. One key insight is that groups don't have nontrivial idempotents; if we can show that a generator is equal to its square, then it must be equal to 1. This gets us a few more letters: from bard = barred we have r = rr (recall e = 1), so r is trivial. Similarly, from medal = meddle we get dal = ddle; but a = e = 1, so dl = ddl; thus d = 1. This actually isn't how I take care of t, although there are enough double t's in the language that it's robably possible to handle t this way; I take packed = pact, from which ked = t; but k, e, d have already been shown trivial, so t = 1. A bit more trickily, thinking in terms of double letters, bawl = ball gives us w = l; but w = 1, so l = 1.


That's sixteen letters shown trivial so far: a, b, d, e, g, h, i, k, l, n, o, r, t, u, w, y. The remaining letters are c, f, j, m, p, q, s, v, x, and z. These seem trickier somehow... to my ear they have pretty well-defined sound. The easy letters to get rid of, you'll remember, are the vowels, which can basically sound however you want them to in English.

Still, a few more fall quickly. base = bass (the musical kind, not the fish), so s = 1; razor = raiser can now take advantage of the times when s sounds like z, since all the other letters involved are trivial, to give us s = z, so z = 1. The letters that are phonetically kind of k-like fall next; key = quay gives k = q, so q = 1, and choir = quire (the pair I'm proudest of finding, by the way) gives c = q, so c = 1.

Six letters to go: f, j, m, p, v, x.

lox = locks, which takes care of x. genes = jeans, killing j. phase = faze; only the p and f are nontrivial here, so p = f. There are two cheap tricks to handle this. The first is hiccup = hiccough, where all the letters involved are trivial except p, so p = 1; but are those separate words, or alternative spellings of the same word? The second is if = iff, so f = 1. (The problem here, of course, is that iff is a bit iffy as a word... is it really a word, or just an abbreviation for "if and only if"?) Two half-solutions add up to one whole solution, though, so I say that p and f are trivial.

That leaves two generators, m and v. If there are relations between them, they're trivializing ones; we're not going to get a relation like "mv = vm" (which would bring us down from the free group on two generators to the free abelian group on two generators), since that would require two homophonous words in English, both containing m and v, where in one the m comes first and in one the v comes first. I've tried to use the double-letter trick; the closest I can get is "clamor" and "clammer" to get rid of m, but these aren't really pronounced the same.

Any ideas on how to finish this up?

My vocabulary in other languages isn't rich enough to do this. But I agree with Roberts' judgement about French, Spanish, and Japanese; French is full of silent letters, even more so than English.

Edited, 12:24 pm: In the comments, dan suggests dammed = damned to show that m is trivial. And ruff = rough shows f is trivial, which gets around the objections I had before. I want to take advantage of the fact that the f in of is pronounced like v usually is, but I can't.