It's known that every position of Rubik's cube can be solved in 20 moves or less. That page includes a nice table of the number of positions of Rubik's cube which can be solved in k moves, for $k = 0, 1, \ldots, 20$. (Some of the entries of the table are approximations, but they're good enough for the purposes of this question.)

In particular, the median number of moves needed is 18, and in fact about 70 percent of all positions require eighteen moves.

This seems a bit counterintuitive to me -- I'd expect the median to be around half the maximum number of moves needed. Consider for example generating $S_n$, the symmetric group on $n$ elements, from the adjacent transpositions $(k, k+1)$ for $k = 1, 2, \ldots, n-1$. The number of such transpositions needed to get from the identity permutation to any permutation $\sigma$ using adjacent transpositions is the number of inversions of that permutation -- that is, the number of pairs $(i,j)$ such that $i < j$ and $\sigma(i) > \sigma(j)$. The maximum number of inversions of a permutation in $S_n$ is ${n \choose 2}$. The mean is ${1 \over 2} {n \choose 2}$; this is also the median if it's a whole number; and the distribution is symmetric around ${1 \over 2} {n \choose 2}$. Another similar case is $(Z/2Z)^n$ generated by the generators of the factors -- the diameter is $n$, the typical distance between elements is $n/2$.

My question: which of these situations is, in some sense, "more typical"? More formally, what's known about the relationship between the diameter of the Cayley graph of a group and the typical distance between two vertices? And is there a third case, where the median or mean distance between two random elements is less than half the diameter? Here I'm looking for something like the distribution of Erdos numbers as given by Grossman -- the maximum Erdos number is 15 but the median is only 5 -- although of course there is the complication here that the collaboration graph is very far from being vertex-transitive.

  • $\begingroup$ they write that they used about 35 CPU years to find all solutions, does it really means that they've being running the program for 35 years? if so, it means that they have started to run it earlier then the first result on Rubik's Cube have appeared. can somebody explain what they actually mean and how much time it took to run their program? $\endgroup$ – Kate Juschenko Apr 12 '11 at 20:06
  • 1
    $\begingroup$ @Kate: This means that it would take 35 years if you would run the program on a single CPU. In practice, the program is run on many CPUs simultaneously; such a program is easy to distribute among several CPUs since all possible starting configurations can be dealt with separately. $\endgroup$ – Tom De Medts Apr 12 '11 at 20:12
  • 1
    $\begingroup$ CPU years are like man-years (please forgive my use of the old-fashioned term): it was likely a cloud of over 100 computers working during the same period. Gerhard "Ask Me About System Desin" Paseman, 2011.04.12 $\endgroup$ – Gerhard Paseman Apr 12 '11 at 20:14
  • $\begingroup$ @Tom: thanks. I can imagine that they've being running all this on several processors, but what actually 1 CPU year means? I believe that it highly depends on the configuration, right? what is the point then to define a CPU time if it actually changes with the time. It seams to be not correct to write "it took us a year to solve the problem", if all this year computer was doing its calculations. Instead, it would be better to say that "it took one CPU year", independently on where exactly the program have been computed. It could be that with the help of google, 35 years were reduced to seconds $\endgroup$ – Kate Juschenko Apr 12 '11 at 20:29
  • 1
    $\begingroup$ A source I saw said that "Google won’t disclose exactly what kind of computing resources it offered to the group." An that it would take a single "Intel four-core, 2.8-GHz Nehalem chip-based desktop computer 1.1 billion seconds, or about 35 years" I've heard that Google uses 2 mid range processors per server so maybe it was 2500 2 processor computers for about 11 days. We may never know. $\endgroup$ – Aaron Meyerowitz Apr 13 '11 at 4:33

Your facts about $S_n$ are actually all facts about Coxeter groups with the generating set given by simple reflections: the distribution is symmetric around the mean, which is half the diameter. It even has a unique local maximum (assuming you allow the floor and roof of the mean to be "one maximum" even if they're different). In the Weyl group case, you can think of this as Hard Lefschetz for the flag variety.

I think perhaps the lesson here is that Coxeter groups a not a good representative of "groups in general."

  • $\begingroup$ This is exactly the sort of answer I was hoping to get. Thanks! $\endgroup$ – Michael Lugo Apr 13 '11 at 1:16
  • $\begingroup$ Ok. Douglas and Jordan's answers are pretty good too, so people should read those as well. $\endgroup$ – Ben Webster Apr 13 '11 at 2:05
  • 1
    $\begingroup$ Who is "Jordan"? (I kid. JSE's secret identity is hardly a secret.) $\endgroup$ – Michael Lugo Apr 13 '11 at 2:20
  • 3
    $\begingroup$ My understanding was that for etiquette purposes, one simply wasn't suppose to write his first and last names together (a bit like with Voldemort). $\endgroup$ – Ben Webster Apr 13 '11 at 2:36

I can answer one of those questions: The diameter is at most twice the median distance by the pigeonhole principle.

Let $m$ be the median. Let $S$ be the set of products of up to $m$ generators. For any $g\in G$, let $S^{-1} g = \{s^{-1}g | s\in S\}.$

By the definition of median, $|S| >= |G|/2$ with equality only if $m$ is a half-integer. If $|S| > |G|/2$ then for any $g\in G$, $S \cap S^{-1}g$ is nonempty, which lets us write $g$ as a product of two elements of $S$. If $|S| = |G|/2$ then every element of $S$ is a product of at most $m-1/2$ generators. For any $g\in G$, either $S \cap S^{-1}g$ is nonempty or $S \cup S^{-1}g = G$, so any $h\in G$ which requires $m+1/2$ generators must be in $S^{-1}g$, which means $g$ can be written as $h$ times an element of $S$, a product of at most $(m+1/2)+(m-1/2) = 2m$ generators.

  • $\begingroup$ I'd like to let it be known that I wish I could accept two answers. After all, I did ask two questions. $\endgroup$ – Michael Lugo Apr 13 '11 at 1:17
  • $\begingroup$ Tell Douglas that you will repost the second part as a new question for him to answer. After he cuts and pastes, you can accept it and close down the question. Gerhard "Ask Me About System Design" Paseman, 2011.04.12 $\endgroup$ – Gerhard Paseman Apr 13 '11 at 1:36
  • $\begingroup$ That doesn't seem worth the trouble, to be honest. My hope was that by posting that comment I would attract more votes to Douglas's answer. $\endgroup$ – Michael Lugo Apr 13 '11 at 1:57
  • $\begingroup$ Thanks. My answer was elementary and it's fitting to accept Ben Webster's answer to the harder question. $\endgroup$ – Douglas Zare Apr 13 '11 at 2:08

Your question about the median is equivalent to: if the diamaeter of a group in some set of generators is d, how long does it take to generate half the group? The answer, as you've observed, depends a lot on what the group is and how the generators look. A case lots of people are currently thinking about is that where G is a finite group of Lie type; in this case, the Cayley graph (we now know, thanks to work of Helfgott, Pyber-Szabo, Breuillard-Green-Tao, Golsefidy-Varju, etc.) is an expander; since "most random graphs are expanders," this might be thought of as a reasonably generic case.

Now I am remembering a talk I saw Breuillard give about this so forgive any inaccuracy; but I believe the size of the set of words of length n grows exponentially in n for n up to some multiple of log G (so the number of words is |G|^c for some c < 1) then there's a transitional phase, but then once you've covered c|G| of the words in the group you finish up very quickly. These correspond to the "early period," "middle period," "late period" in this post of Terry's, though in the post he's talking about the closely related random walk rathen than the volume balls. In other words, the number of steps necessary to cover half the group is probably very close to the diameter in these cases.

  • $\begingroup$ Latecomer's comment here. As you know, you get expansion only when the girth is large (>> (log n)); otherwise you just get polylog diameter (and what you call "esperantism", i.e., polylog mixing time). The girth is in fact large for a large family of examples (including anything you can write down, i.e., projections) but obviously not always. If the girth is large, then, by definition, you've got exponential growth for the first >> log n steps. Then you apply a result of |A A A|>=|A|^{1+delta} type for a constant number of steps - the middle period. Then you finish up the job in 3 steps. $\endgroup$ – H A Helfgott Sep 21 '11 at 13:31
  • $\begingroup$ Speaking of which - Akos Seress and I just put up a paper on the arxiv giving a bound on the diameter of the symmetric group. So it isn't just linear groups now. $\endgroup$ – H A Helfgott Sep 21 '11 at 13:33

To expand on JSE's answer a bit: for simple finite groups of Lie type, the Gowers "quasirandom groups" argument with the additional trick of Nikolov-Pyber shows that once one has generated $|G|^{1-\delta}$ elements, three times that many steps give the whole group, for some $\delta>0$ which depends only on the Lie rank of the group (I think it is $1/9$ or so for $SL_2$). I've just written this up for my representation theory class


(section 4.7.1).

Such ideas are also already present in the work of Helfgott on growth in $SL_2$ -- part (b) of his "Key proposition" -- but the sharp constant $3$ was not; the crucial group-theoretic idea in the argument of Gowers is the use of the large size of a non-trivial representation of the group.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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