Unravelling the (miniature) Rubik’s Cube throughits Cayley Graph
Daniel Bump1 and Daniel Auerbach2
October 13, 2006

1

Introduction

There are many interesting questions one can ask about a highly symmetric graph.
A graph with a transitive automorphism group can be obtained starting with a group
G and a small set S of generators. We assume that S is closed under inverses. Thenthe vertices of this Cayley graph are the elements of the group, and elements x andy will be joined by an edge if x−1 y ∈ S.
Anyone who has worked with groups knows that they have great individuality.
A nonabelian simple group is very different in character than a p-group. A Cayley
graph is just a group with additional structure (the edge relation) so one might also
expect it to have its own unique individual character. Yet if it is at all large it is achallenge to view it as something more than just an amorphous collection of points
with an edge relationship. How can one perceive its true structure?
The Rubik’s cube is a popular toy which in reality is nothing but a group with agiven set of generators – in other words, its essence is a Cayley graph CG . Inside thegroup of the Rubik’s cube, one may consider the subgroup with two generators, andthe corresponding Cayley graph. For the miniature (2 × 2 × 2) Rubik’s cube, thisgroup of order 29,160 and its Cayley graph (of the same size) are of just the rightsize to make interesting experiments. It is small enough that a model can be kept inmemory in a computer, so that any question can potentially be answered by brute
1

Department of Mathematics, Building 380, Stanford University, Stanford, CA 94305-2125.
email: bumpmath.stanford.edu
2
Google, Inc. email: dtauerbachgmail.com

1force computation. Yet it is large enough that it may already exhibit unexpected
properties of large highly symmetric graphs.
The decision to focus on the two-generator group (generated just by rotationsof two adjacent faces) is motivated not only by the desire to obtain a Cayley graphof convenient size, but also by a circumstance described by Singmaster [6] – thetwo-generator group is a particularly interesting group. It is a wreath product basedon the group of permutations of the six vertices that are moved by the two operations, and this permutation group is itself isomorphic to PGL2 (F5 ), the group of the
projective line over the field of five elements; in turn it is isomorphic to S5 .
Cube enthusiasts may note that the two-generator group – of either the standard(3×3×3) miniature cube – is the basis of a good puzzle. If one scrambles a cube using
just two generators, can one then unscramble it using just those two generators? The
fact that this puzzle is a good alternative to the usual cube-scrambling puzzle is areflection of the remarkable richness of the two generator group.
We will try to bring this Cayley graph CG to life in this paper. We will see thatits diameter is 17. We will consider how the “ball of radius r” consisting of all points
of distance r from the origin grows with r. Perhaps surprisingly, when r is near the
diameter, the rate of growth of the ball slows dramatically. Although the graph has
thousands of vertices, only a few – 18 altogether – are at maximal distance from theorigin. We call these vertices the antipodes and we will consider the structure of thesubgraph formed by these.
We will show that the graph can be used to obtain a presentation of the group,that is, a complete set of relations between the generators. We will apply thisinformation to construct interesting operations for the group of the full (3 × 3 × 3)
Rubik’s cube.
Finally we will turn to questions about the random walk on the graph – howquickly does making random operations from the set of generators scramble the
cube? We will consider this question from a couple of different points of view.
Repeatedly making random operations chosen from the set S of generators produces a Markov process. How quickly the process converges to randomness is fromone point of view a question of computing the eigenvalues of the Markov transition
matrix. This in turn reduces to a problem in group representation theory – each
irreducible representation of the group will supply some of these eigenvalues. We
will compute all of them. On the other hand, we will also study this Markov process
brute force computation.
We would like to thank Persi Diaconis and Hua Zhou for interesting conversations and helpful comments. For support, we thank Stanford’s VPUE and Gunnar
Carlsson (Auerbach) and NSF grant DMS-0354662 (Bump).
2

2

Introduction to the 2 generator group

Let G denote the group generated by taking clockwise rotations of the right and top
faces of the miniature (2 × 2 × 2) Rubik’s Cube. Denote by R a clockwise rotationof the right face, and let U denote a clockwise rotation of the top face, so thatG = hR, U i. Following Singmaster [6], we also sometimes denote R−1 by R0 , U −1 by
U 0 . Let K denote the subgroup of G corresponding to operations that do not change
the position of any of the 6 cubes which are generally affected by the group (i.e. Kchanges only the orientation of these cubes).
Proposition 1. K is an abelian, normal subgroup of G of order 35 .
Proof. Given any operation g ∈ G, and k ∈ K, we clearly have that gkg −1 ∈ K,
since cube positions are not affected by k. Hence, K is normal in G. Moreover, K
is clearly abelian.
To see that the order |K| ≤ 35 , we observe that there are 3 possible orientation
changes (or twists) for each of the 6 cubes and so the order of K must be ≤ 36 .
Now label each possible twist by a different number: 0 for no change, 1 for clockwise
twist, 2 for counterclockwise twist. It is well-known that the total number of twists
must be ≡ 0 modulo 3 (Singmaster [6]) and so |K| ≤ 35 .
So we need only show that |K| ≥ 35 . The operation RU R0 U RU 2 R0 U 2 ∈ K twists
three corners clockwise by one twist, and it is easy to see that this operation, together
with its conjugates, generates a group containing any operation twisting the corners
in such a way that the total number of twists is ≡ 0 modulo 3 and so |K| > 35 .
Operations in G only affect the locations and orientations of 6 pieces. We label
these by the points of the projective line P1 (F5 ) = F5 ∪ {∞} over the field with 5
elements (Figure 1).
The group G acts on the six pieces by permuting them and also affecting theirorientation. The quotient G/K also acts faithfully as a group of permutations of
P1 (F5 ) (ignoring orientation). Thus it may be regarded as a subgroup of the group
S6 of permutations of the six element set P1 (F5 ).
A particular group of permutations of P1 (F5 ) is the group PGL(2, F5 ) acting bylinear fractional transformations. Thus the group GL(2, F5 ) acts by
ax + ba b,
x ∈ F5 ∪ {∞},
: x 7−→c d
cx + dwhere it is understood that if x = ∞ then ax+b
= ac , while if cx + d = 0 then
cx+d
ax+b
= ∞. Since the center Z of GL(2, F5 ) consisting of scalar matrices acts trivially,
cx+dthis is really an action of GL(2, F5 )/Z = PGL(2, F5 ).
3

∞

2

1

0
3
4

Figure 1: The labeling of the 6 pieces moved by G.
Proposition 2. (Singmaster [6]) As a permutation group acting on P1 (F5 ), we
have G/K = PGL(2, F5 ).
Proof. Let us check that generators of G/K are contained in PGL(2, F5 ). Noticethat R, RU generate G, so we need only to show that R, RU ∈ PGL(2, F5 ). In
keeping with the labeling scheme given and the action described above, we see that
R corresponds to the cycle (012∞), while RU corresponds to the cycle (01234). But
an easy verification then shows that R and RU have corresponding fractional linear
transformations:


0 1
R=
∈ P GL(2, F5 )
2 1


1 1
RU =
∈ P GL(2, F5 )0 1
So indeed we see that G/K ⊂ PGL(2, F5 ). It is also easy to verify that these twoelements generate PGL(2, F5 ).
Corollary 1. G/K ∼= S5 , and |G/K| = 5!.
Proof. The well-known isomorphism PGL(2, F5 ) ∼= S5 may be checked by labelingthe 5-Sylow subgroups of S5 as follows:h(12345)i = ∞,h(12543)i = 2,h(12354)i = 0,h(12534)i = 3,h(12453)i = 1,h(12435)i = 4.

(Here h(12345)i denotes the cyclic subgroup generated by the 5-cycle (12345).) The
group S5 acts on P1 (F5 ) by conjugating its Sylow subgroups, and we claim that4the group of permutations of P1 (F5 ) thus obtained is PGL(2, F5 ). To see that it iscontained in PGL(2, F5 ) it is enough to check for generators of S5 that conjugationinduces a linear fractional transformation. For example conjugation by (12345) induces the transformation that fixes ∞ and cyclicly permutes 0 −→ 1 −→ 2 −→ 3 −→4 −→ 0, whichto the linear fractional transformation x 7−→ x + 1, or corresponds
1 1
the matrix
in GL(2, F5 ). Similarly (45) has the effect 0 ←→ ∞, 1 ←→ 2,
0 1
3 ←→ 4, which is the linear fractional transformation x 7−→ 2/x, or the matrix
0 2
in GL(2, F5 ). Since S5 is generated by (12345) and (45), we see that every
1 0
permutation of the 5-Sylow subgroups thus labeled is in PGL(2, F5 ) and so we haveconstructed a homomorphism S5 −→ PGL(2, F5 ). Both groups have the same order
120, and the homomorphism is nontrivial since the only nontrivial normal subgroupof S5 is A5 , and we have already seen that an element (12345) of A5 acts nontrivially,
so it is an isomorphism.
Now we show that G is a semidirect product K n H for a subgroup H. Thismeans that H ∩ K = {1} and that G = HK. (We already know that K C G.) This
fact – that the two generator group is a semidirect product – is false for the larger
two generator group of the 3 × 3 × 3 Rubik’s cube.
To construct the group H, let us suppose we have a cube in a solved configuration.
Suppose further that the F (front) face is red and that the opposite face—the B
face—is orange. Consider an operation which leaves only red or orange facelets on
both the F and B faces. This element of G is said to solve the F and B faces mod
identification of F and B colors. Let H denote the set of operations of G which solve
the cube mod the identification of F and B colors. It is clear that H is a group.
Proposition 3. Every element of G/K has a unique representative in H, and so G
is the semidirect product K o H.
Proof. Exactly six cubes move during the operation of the cube. If the locations ofthese six cubes are given, there is exactly one way for each them to be oriented thatsolves the F and B faces mod identification of F and B colors. Thus H ∩ K = {1}.
What we must show is that if a permutation of the six cubes is attainable within G,then this orientation that solves the cube modulo identification of F and B colors
can be achieved within H. Let
h1 = RU R0 U RU 0 R0 U RU 2 R0 U ∈ H
h2 = U RU 0 RU R0 U 0 RU R2 U 0 R ∈ H
5

It is direct to see that these elements are in fact in H, and moreover, that h1 has thesame image as U in G/K and h2 has the same image as R in G/K. Now consider
the subgroup H1 of H generated by h1 and h2 . We can write any element of G in
the form hk (where h ∈ H1 and k ∈ K), since up to a twist, the generators of G arecontained in H1 . Thus, it is clear that H1 = H and that HK = G, and so we havethe desired semi-direct product.

3

The Cayley graph

As G is a semi-direct product, one can enumerate all elements of G as pairs (k, h)with k ∈ K and h ∈ H. Given this, the Cayley graph of G is easily modelled using a
program in C++, and some facts that are set out in this section were proved using
this computer program.
Let CG denote the Cayley graph of G with respect to the set S = {R, R0 , U, U 0 }of generators. This is the graph whose vertices are the elements of G, and whoseedges are the pairs of x and y such that x−1 y ∈ {R, R0 , U, U 0 }. The group G acts
transitively on the graph on the left. The graph is kept entirely in memory during
the computations.
Proposition 4. CG has diameter 17.
Proof. This was checked by computer. We recursively label the elements of the graphby integers d which will represent the distance from the origin. The identity element
is assigned the label d = 0, and at the d-th step, all elements that are neighbors of avertex at distance d that are not already labeled are given the label d + 1. After 17
steps, no more unlabeled vertices are found and the algorithm terminates.
Loops in the Cayley graph correspond to relations between the generators. For example, after applying R2 U 2 R2 U 2 R2 U 2 one returns to the starting point. This meansthat the graph has a loop, or equivalently, that the “braid relation” R2 U 2 R2 U 2 R2 U 2 =1 is satisfied in the group.
Lemma 1. The group G admits a character χ : G −→ {±1} such that χ(x) = −1
for all x ∈ S. If x1 · · · xr = 1 with xi ∈ S, then r is even.
Thus every loop in the Cayley graph has even length.
Proof. We have noted that G/K ∼= S5 , and χ may be taken to be the sign characterof S5 pulled back to G. Applying χ to x1 · · · xr = 1 gives (−1)r = 1, so r is even.

6This fact is the basis of a computer algorithm to compute relations in the group,
leading to a presentation. Since by Lemma 1 any relation has even length, one canlook for situations where there are two distinct paths of equal length that start at
the origin and have the same endpoint.
In the course of proving Proposition 4 we used a computer to compute the distancefrom every vertex to the origin, and we may now reuse this information to implement
this idea. Let us a vertex x a H-vertex if it has at least two distinct adjacent vertices
that are closer to the identity vertex than x (i.e. they have shorter walks to theidentity than does x). To find relations, the algorithm that we will now describe
goes through the entire graph, identifying H-vertices.
Given the labeling of the vertices by their distance from the origin, the H-vertices
are easily identified. For each H-vertex N and each pair of adjacent vertices A andB that are closer to the identity than N , the algorithm produces one relation. Let
us describe this relation. Let a be some shortest walk from the identity to N that
goes through node A, and let b be some shortest walk that goes from the identity
to N going through node B. Then ab−1 = 1 is clearly a relation, and is the relation
generated for the ordered triplet (N, A, B). If there are other H-vertices on either
path a or b, then this relation is not uniquely determined, but this does not matter.
The important thing is that some such relation exists.
After generating all such relations, the algorithm cuts down on the total number
by eliminating unnecessary relations. It does this by considering only a subset of thetotal number of triplets (N, A, B) that are necessary, by eliminating relations that
contain other relations, and by eliminating redundant cycles. To illustrate this lastpoint, let us consider a quick example. If we have two relations abc = 1 and bca = 1,
these two relations are redundant and we can throw one of them out. So we get apresentation of G. There are too many relations to list them all here, but we give 14of the shortest relations below:
R4
U4
RU RU RU 0 R0 U 0 R0 U 0 R0 U 0 R0 U 0 R0 U RU RU
R0 U 0 R0 U RU RU R0 U 0 RU 0 R0 U 0 R0 U 0 RU RU
R0 U RU RU R0 U 0 R0 U 0 RU R0 U 0 R0 U 0 R0 U RU
RU RU R0 U 0 R0 U 0 R0 U R0 U 0 R0 U 0 RU RU RU 0
RU RU 0 R0 U 0 R0 U 0 RU R0 U 0 RU RU RU 0 R0 U 0
R0 U 0 R2 U RU RU 2 R0 U 0 R2 U 0 R0 U RU RU R0 U 0 R
We have listed all of the relations of length < 12 and two of the relations of length
12.
There is a homomorphism φ : G3 −→ G from the two-generator group G3 of the3 × 3 × 3 Rubik’s cube, since any operation satisfied by the counterparts of R and7

U in G3 is obviously satisfied in G. The kernel of φ is the group of edge operations
that effect the edges of the full Rubik’s cube, but have no effect on the corners. A
reasonable strategy for solving the full Rubik’s cube is to first put the corners inplace, then deal with the edges, so a table of edge operations is a useful thing. As we
mentioned in the introduction, a pleasant puzzle is to scramble the cube using the
2 generator group, then restore it using only operations from the 2 generator group,
and if one wants to be proficient at this task, it is important to know some edge
operations that only use R and U . For example, the operation RU RU RU 0 R0 U 0 R0 U 0is an extremely pleasant edge three-cycle that is easy to use and remember.
Finally, we present a table that partitions all vertices of CG into their distancesfrom the identity.
r
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Number ofvertices at distance r
1
4
10
24
58
130
271
526
980
1750
2731
3905
5229
5848
4792
2375
508
18

log B(r)log(r)−−
2.321932.46497
2.64272.842433.02772
3.191623.33333
3.46023
3.574493.66043.72191
3.76469
3.779483.75763.701363.62837

Table 1: The number of vertices at distance r from the origin.
Our next point is speculative. We note the striking fact is that after distance 14,
the number of vertices at each distance shrinks dramatically, with only a handful at
distance 17. One is tempted to try to visualize the graph as something like a sphere8

or other homogenous space of some dimension, since in a sphere of circumference
A the area of the set of points at distance between x and x + ∆x decreases as x
approaches A/2. But if one accepts this idea, what would be the dimension of the
manifold?
The notion of fractal dimension suggests the following considerations. Let B(r) be
the number of vertices of distance < r from the identity. In a manifold of dimensiond, we would expect the volume of a ball of radius r to satisfy:
log B(r) ∼ d log(r)for small r. So this suggests that CG can be thought of as having fractal dimension
between 2 and 3. This is not intended to be a rigorous statement, and indeed is amisuse of the concept of dimension. However it seems plausible that on a large scale
the graph has some interesting topology that we have not yet been able to discover,and this may be an interesting direction for future work.
Since there are exactly 18 vertices at maximal distance, we wondered if they all
were close to each other (which would support the idea that the graph could bethought of as a sphere). We call these 18 vertices the antipodes. They are
A1 = RU 0 RU 0 RU 0 R2 U R0 U RU 0 R0 U R2
A3 = U 0 RU 0 R2 U 0 RU 0 RU 0 RU 0 R2 U R2
A5 = U RU 0 RU 0 RU 0 RU 0 R0 U R0 U 0 RU R2
A7 = R0 U 2 RU 2 RU 0 RU 0 RU 0 RU 2 R2
A9 = U 2 RU 0 R2 U 0 RU 0 RU 0 RU R0 U R2
A11 = U 2 RU 0 RU 0 RU 0 RU R0 U 2 RU R2
A13 = U R0 U 2 RU R0 U R0 U R0 U R2 U R2
A15 = U 0 RU 0 RU 0 RU 0 R2 U R0 U R2 U R2
A17 = R0 U RU 0 RU R0 U RU 0 RU 2 R0 U R2

A2 = R0 U R0 U R0 U R2 U R0 U 0 RU R0 U R2
A4 = U 0 R0 U RU 0 RU R0 U RU 0 RU 0 RU R2
A6 = U R 0 U R 2 U R 0 U R 0 U R 0 U R 2 U 0 R 2
A8 = RU R2 U 0 R2 U R0 U R0 U 2 R0 U R2
A10 = U R0 U 0 RU R0 U R0 U R0 U RU 0 RU R2
A12 = U 0 R0 U R0 U 0 RU 0 RU 0 RU 0 R0 U RU 0 R2
A14 = U 2 RU 0 RU R0 U R0 U R0 U 2 R0 U R2
A16 = R2 U 0 RU 0 R2 U R2 U 0 RU 0 RU R2
A18 = U R0 U R2 U R0 U R0 U R0 U 0 R2 U R2 .

The subgraph of the antipodes can be grouped into 4 clusters. The first two
clusters have 4 elements each:

A12

A1

A2

A16

A10

A17

A8

A14

Here vertices connected with a horizontal line have distance 6 from each other,and those pairs of vertices that have no lines between them all have distance 8 fromeach other.
The next two subgraphs are of the form:
9

A11

{{
{{
{
{
{{

A6 B

BB
BB
BB
B

A7 B

A13

BB
BB
BB
B

A4

A15

{{
{{
{
{
{{

{{
{{
{
{
{{

A5 C

CC
CC
CC
C

A18 C

CC
CC
CC
C

A3

||
||
|
|
||

A9

Here vertices connected with a horizontal line have distance 6 from each other, andvertices connected with a slanted slash have distance 8 from each other. Moreover,the pairs {A11 , A13 } and {A15 , A9 } have respective distance 10. The pairs {A6 , A4 },{A6 , A13 }, {A11 , A4 } and {A5 , A3 }, {A5 , A9 }, {A15 , A3 } all have respective distance
12. The smallest distance between any two clusters is 10.

4

The Markov process

The adjacency matrix of the Cayley graph of G = {g1 , · · · , gN } (where N = |G| =29,160) is the matrix whose rows and columns correspond to the elements of g, witha value 1 in the i, j-th position if gi and gj are adjacent in the graph, and otherwise
0. Dividing this matrix by 4 gives a matrix we will denote by M . It is clear that
M is a symmetric doubly stochastic matrix. As we will explain, it is the transition
matrix of a Markov process. Its eigenvalues will prove important, so we first discuss
how to compute them.
If ξ is a function on the group, then we may think of ξ as a vector whose entries
are indexed by the group elements, and the i-th entry has value ξ(gi ). Then we may
compute the vector M ξ, andPinterpret that as a function on G. Alternatively, we
may think of ξ as the entry
ξ(g) · g of the group algebra C[G],Pand the element of
the group algebra corresponding in this way is 41 (R+R0 +U +U 0 ) ξ(g)·g. Hence we
may identify vectors with elements of the group algebra, and then application of thematrix M corresponds to left multiplication by the special element 41 (R+R0 +U +U 0 )of C[G]. By abuse of notation, we will sometimes write M = 14 (R + R0 + U + U 0 )with this understanding.
Lemma 2. The eigenvalues of M are real. If λ is an eigenvalue of M , so is −λ.
The largest eigenvalue is 1.
Proof. Since it is symmetric, the eigenvalues are real. If M ξ = λξ, we can multiply
the entries in the vector ξ by ±1 to obtain another vector with eigenvalue −λ as10follows. The rows of ξ are indexed by the elements of G multiply the g-th entryby χ(g), where χ is the character of Lemma 1. By the Perron-Frobenius theorem(Horn and Johnson [2]), the top eigenvalue of M is 1, and it occurs with multiplicity
one.
The eigenvalues of M can be computed using group representation theory. Let
π1 , π2 , · · · , π48 be the irreducible representations of G, let χ1 , · · · , χ48 be their characters, and let di = χi (1) be their degrees. Then the regular representation decomposesas
48
M
C[G] ∼
di πi .
=
i=1

Thus we may find the eigenvalues of M in C[G] by finding the eigenvalues of M
in each of the irreducible representations πi , then counting each eigenvalue withmultiplicity di .
Since G is a semi-direct product with abelian kernel K, a theorem of Mackey
constructs all irreducible representations by induction from characters of certain
subgroups of G. See Mackey [4] Theorem 14.1 and Lang [3], Exercise 7 on page 724.
However there is no need to compute these eigenvalues by this method since thecomputer program GAP [1] is capable of producing the characteristic polynomialsof the linear transformations induced by M on each irreducible G-module. The
following short program will suffice to produce these after a few hours.
G:=Group((1,12,8,6)(3,11,9,5)(2,10,7,4),(10,13,17,8)(7,11,14,18)(15,16,9,12));r:=(1,12,8,6)(3,11,9,5)(2,10,7,4);
rp:=Inverse(r);u:= (10,13,17,8)(7,11,14,18)(15,16,9,12);
up:=Inverse(u);A:=IrreducibleRepresentations(G);Q:=List([1..48],
i -> CharacteristicPolynomial((rˆA[i]+rpˆA[i]+uˆA[i]+upˆA[i])*1/4);
The characteristic polynomials thus produced may then be evaluated using Mathematica. The nonnegative eigenvalues are listed with multiplicity in Table 2. For
each λ > 0 in this table, −λ also occurs with the same multiplicity, but these are
not listed.
Let ξ1 , · · · , ξN (N = |G| =29,160) be an orthonormal basis of L2 (G) consisting of
eigenvectors for M in with respect to the L2 norm. Let λ1 , · · · , λN be the eigenvalues,
so M ξi = λi ξi . Such an orthonormal set of eigenvalues exists since the matrix M is11

symmetric. By Lemma 2, both 1 and −1 are eigenvalues of M , and both occur withmultiplicity one. We order the eigenvalues so that λ1 = 1 and λ2 = −1. We have
ξ1 (g) = 1,

ξ2 (g) = χ(g).

The next eigenvalue λ3 = 0.964905 has multiplicity 20 as does −λ3 , so we canfurther order the basis such that λ3 = λ4 = . . . = λ22 and λ23 = . . . = λ42 = −λ3 ,and |λi | < λ3 when i > 42.
Consider the Markov process corresponding to the random walk on the Cayley
graph. Specifically, let us start P
with a probability distribution p on G, that is, a+function p : G → R such that g∈G p(g) = 1. After we apply a random elementof the generating set, we obtain another probability distribution.
P We may associate+with the probability distribution p : G → R the elementp(g) · g of the groupalgebra C[G], and after applying a random twist, this element is multiplied by M =1(R + R0 + U + U 0 ).
4
Let p0 be the probability distribution corresponding to the solved cube, so thatp0 (1) = 1, while p0 (g) = 0 for g 6= 1. Iterating the Markov process by randomly
twisting the cube k times gives the distribution pk = M k p0 . After k operations, thecube will necessarily be at an even or odd distance from the identity, depending onwhether k is even or odd. Except for this constraint, pk should be approximately
random if k is large. More precisely, if k is large, we expect pk − Lk to be small,
where
 2
if χ(g) = (−1)k ,|G|
Lk (g) =0 otherwise.
To quantify this expectation, there are various measures of closeness. We will use
the L1 and L2 norms on G with the total volume normalized to 1. Thus
!1/p
1 X||f kp =|f (g)|p.
|G| g∈G
In the literature on random walks on a finite group G, it is customary to measure thedistance between two probability distributions p and q by the total variation distance(see Diaconis [1] and Saloff-Coste [5]). This is defined by:
kp − qktv = max F (A),F (A) =A⊂G

X

p(g) − q(g) .

g∈AProposition 5. If p and q are probability distributions, we havekp − qktv =|G|||p − q||1 .
2

12

(1)

Proof. Let A1 = {g ∈ G|p(g) > q(g)} and A2 = {g ∈ G|p(g) < q(g)}. Then since
p and q are real, it is easy to see that F (A) is maximal when A = A1 or A2 , andsince p and q are probability distributions,
it is easyP
Pto see that F (A1 ) = F (A2 ).
Moreover on A1 or A2 we have | (p(g) − q(g))| =|p(g) − q(g)| since all terms
have the same sign, so
X
F (A1 ) + F (A2 ) =|p(g) − q(g)| = |G| × ||p − qk1 .
g∈G

Proposition 6. We havekpk − Lk ktv 6|G|||pk − Lk ||2 .
23/2

Proof. In view of Proposition 5, we must show that1||pk − Lk ||1 6 √ ||pk − Lk ||2 .
2This is basically the Cauchy-Schwartz inequality, taking into account that the support of pk − Lk is contained {g|χ(g) = (−1)k }, a set of order |G|/2. To be precise,let fk (g) = |pk (g) − Lk (g)|. Then


|G|
1
Lk 6 kfk k2 · k(|G|/2)Lk k2 = √ kfk k2 .
(2)||pk − Lk ||1 = fk ,2
2

Proposition 7. We haveλk||pk − Lk ||2 6 p 3 ,|G|
Proof. We can write the initial distribution
p0 =

N
X

ci ξi .

(3)

i=1

The first two eigenfunctions are ξ1 (g) = 1 and ξ2 (g) = χ(g). Since p0 is a probability
distribution,X
p0 (g) = |G| hp0 , ξ1 i = |G|c1 ,
(4)
1=
g∈G

13

1
so c1 = |G|and c1 ξ1 is the uniform distribution where every state has equal proba1
bility. Similarly c2 = |G|
since (4) would remain true if we replace ξ1 by ξ2 , whichequals ξ1 at the origin (which is the only place where p0 6= 0).
We can choose our orthonormal basis so that ξ3 is a constant times the projectionof p0 on the λ3 -eigenspace. This means that c4 = . . . = c22 = 0. We can take
ξ20+i = χξi when i = 3, 4, · · · , 22. Then, since p0 = χp0 , we have c23 = c3 andc24 = . . . = c42 = 0. Thus

p0 = c1 ξ1 + c2 ξ2 + c3 ξ3 + c23 ξ23 +X

ci ξi =i>431
(ξ1 + ξ2 ) + c3 (ξ3 + ξ23 ) + . . . ,|G|

1and since Lk = |G|(ξ1 + (−1)k ξ2 )pk − Lk = c3 λk3 (ξ3 + (−1)k ξ23 ) +X

ci λki ξi .

(5)

i>43

Thus
||pk − Lk ||2 = ||Xi>2ci ξi k2 =

sX

v
u |G|
uX
k
|λ |2k |c |2 6 λ t|c |2 ,
i

i>2

i

i

3

(6)

i=1

since λ3 is the largest of the eigenvalues that occur. But by the Plancherel formula
s
s
X
1 X
1
p0 (g)2 = p .
|ci |2 = kp0 k2 =|G| g∈G|G|i

Theorem 1. There exist constants C1odd , C1even and C2 > 0 such that as k −→ ∞
 even k
Ctv λ3 if k is even,kpk − Lk ktv ∼
odd k
Ctv
λ3 if k is odd,
kpk − Lk k2 ∼ C2 λk3 .

(7)

even
odd
At the end we will give evidence that Ctv= Ctv, and conjecture a value forthis. This is an interesting empirical observation for which we have no explanation.

Proof. First let k run through the set of all even positive integers, or through all odd
positive integers. We will prove the existence of constants Ciodd and Cieven (i = 1, 2)
such that (7) is true for k thus restricted. At the end, we will show C2odd = C2even .
14

It is clear from (5) that pk − Lk equals c3 λk3 (ξ3 + (−1)k ξ23 ) plus terms that are
more rapidly decreasing as k −→ ∞. Thus if i = 1, 2
 even k
Cieven = c3 kξ3 + ξ23 ki ,Ci λ3 if k is even,kpk − Lk ki ∼Ciodd = c3 kξ3 − ξ23 ki .
Ciodd λk3 if k is odd,
odd
In view of (1), the statement follows for the total variation
p distance. We have C2 =even
22
C2 since ξ3 and ξ23 are orthogonal, so both equal c3 kξ3 k2 + kξ23 k2 .

By Propositions 6 and 7 we have
p
|G|
odd
even
Ctv
, Ctv
6 3/2 ∼
= 60.37 · · · ,2

1
C2 6 p= .005856 · · · .
|G|

(8)

How sharp are these bounds? To answer this, we tabulated kpk − Lk ktv andkpk − Lk k2 in Table 3, simply by iterating the Markov process and computing thevalues directly. We found that ||pk − Lk ||tv λ−k
and ||pk − Lk ||2 λ−ktend to limits
3
3that are close to square roots of rational numbers that√we can identify, and so we
odd
even
conjecturethat the actual values are Ctv= Ctv= 3 = 1.73205 · · · and C2 =√40
= 0.000216891 · · · . Thus the a priori bounds (8) are not sharp. Still, they are|G|
the best that we know how to obtain by purely theoretical methods.

References[1] P. Diaconis, Group representations in probability and statistics. Institute ofMathematical Statistics Lecture Notes—Monograph Series, 11. Institute of Mathematical Statistics, Hayward, CA, 1988.
[1] The GAP Group. GAP - Groups, Algorithms, and Programming, Version 4.4.
http://www.gap-system.org.
[2] R. Horn and C. Johnson, Matrix Analysis. Cambridge University Press, Cambridge 1985.
[3] S. Lang. Algebra, volume 211 of Graduate Texts in Mathematics. Springer-Verlag,
New York, third edition, 2002.
[4] G. Mackey, Induced representations of locally compact groups. I. Ann. of Math.
(2) 55, (1952). 101–139.

15

[5] Laurent Saloff-Coste. Random walks on finite groups. In Probability on discrete
structures, volume 110 of Encyclopaedia Math. Sci., pages 263–346. Springer,
Berlin, 2004.
[6] David Singmaster. Notes on Rubik’s magic cube. Enslow Publishers, Hillside,N.J., fifth edition, 1981.
[7] Hua Zhou. Scrambling a Rubik’s cube. Preprint, 2005.

16

1.000000
0.907849
0.886611
0.835757
0.831096
0.827309
0.819279
0.804298
0.795839
0.7862760.770755
0.7581680.750000
0.720600
0.710455
0.683013
0.667817
0.658431
0.640388
0.624062
0.606594
0.591803
0.574576
0.552810
0.539565
0.518901
0.492263
0.478352
0.444028
0.427234
0.416355
0.400032
0.393554
0.390388
0.368314
0.356082
0.331079
0.316075
0.301470
0.284554
0.275524
0.2661030.211505
0.190111
0.169539
0.118314
0.093062
0.076615
0.051983

1
40
30
60
60
60
20
30
60
12
20
40
51
40
60
10
20
30
5
60
60
30
30
30
20
40
120
30
30
40
30
60
60
5
30
30
120
48
20
40
60
120
40
48
30
30
30
30
20

0.964905
0.907045
0.871275
0.835030
0.830034
0.826586
0.8191540.802612
0.791877
0.785399
0.766137
0.756365
0.736625
0.720196
0.710296
0.673817
0.660964
0.654514
0.635712
0.623212
0.604352
0.591660
0.572932
0.544301
0.537475
0.512703
0.490689
0.457161
0.443226
0.424228
0.415291
0.397816
0.393444
0.381148
0.362423
0.346821
0.325694
0.314854
0.301067
0.283465
0.274968
0.264351
0.198295
0.186409
0.167326
0.117065
0.091040
0.070351
0.044628

20
60
30
60
60
48
30
30
40
30
60
30
60
60
60
60
48
30
30
30
30
30
48
60
60
30
60
30
48
20
30
60
30
60
120
40
164
20
30
40
40
120
30
40
40
48
120
30
60

0.936084
0.906972
0.855006
0.832707
0.829343
0.824754
0.809017
0.800488
0.790766
0.782159
0.766118
0.754269
0.736556
0.720192
0.698521
0.668016
0.660754
0.652425
0.629204
0.619106
0.602651
0.575695
0.567158
0.544279
0.536339
0.511862
0.488542
0.455708
0.438052
0.420769
0.408431
0.397815
0.393070
0.380994
0.361707
0.345492
0.324601
0.309017
0.300165
0.282041
0.268420
0.259595
0.197840
0.183013
0.166980
0.106347
0.089895
0.068591
0.037735

30
60
20
60
48
60
84
20
60
40
40
20
60
60
48
20
60
60
60
60
60
15
60
60
30
60
40
60
120
20
30
60
30
12
40
12
40
84
60
30
30
30
30
10
60
60
120
40
20

0.909367
0.904508
0.847422
0.832706
0.829218
0.820615
0.8062010.800106
0.790764
0.778619
0.765693
0.752256
0.725562
0.717310
0.688847
0.668013
0.660738
0.641324
0.6291810.610474
0.601785
0.575694
0.567155
0.542606
0.532916
0.511852
0.487392
0.444737
0.432685
0.420616
0.401645
0.396107
0.392473
0.373564
0.360534
0.344989
0.319624
0.306798
0.2971550.280577
0.266718
0.250001
0.195990
0.176079
0.157835
0.106303
0.085426
0.060219
0.007424

30
12
20
60
60
60
60
60
60
20
40
60
60
30
60
20
60
60
60
40
60
119
60
60
20
60
60
30
40
30
30
60
60
20
40
20
120
30
120
60
120
10
40
120
120
120
120
30
120

0.908049
0.888077
0.837335
0.832269
0.829145
0.819993
0.806200
0.798320
0.788831
0.775149
0.763270
0.752252
0.721957
0.711052
0.688712
0.667821
0.659446
0.641287
0.624378
0.607727
0.596907
0.575693
0.561738
0.542604
0.520404
0.500000
0.487390
0.444065
0.427291
0.4172700.400033
0.393558
0.392469
0.368842
0.357762
0.344096
0.319198
0.303628
0.294180
0.276563
0.266447
0.250000
0.1928380.170410
0.145004
0.104916
0.081867
0.055113
0.000000

30
120
30
30
60
60
60
40
30
20
40
60
30
30
60
20
40
60
60
60
40
30
60
60
20
54
60
60
120
12
60
60
60
60
20
120
30
48
120
40
120
86
120
20
30
30
60
40
4944

Table 2: Nonnegative eigenvalues of M , with multiplicities.

17

k||pk − Lk ||tv
50.989163100.896468
150.790351
20
0.691236
25
0.59871230
0.51413740
0.37283850
0.267605
600.19111670
0.135807
800.0960715
90
0.067769
95
0.0568745
100
0.047711
150
0.00811339
175
0.00332912
200
0.00136435
300 0.0000383523
500 3.02499 × 10−8||pk − Lk ||20.00105344
0.00048854
0.000278645
0.000180163
0.0001264
0.0000938488
0.0000575967
0.0000381118
0.0000260214
0.0000179994
0.0000125222
8.73526 × 10−6
7.29994 × 10−6
6.10191 × 10−6
1.02085 × 10−6
4.17877 × 10−7
1.71063 × 10−7
4.80408 × 10−93.78898 × 10−12||pk − Lk ||tv λ−k3
1.18262
1.281411.35068
1.41233
1.46253
1.50156
1.55646
1.59686
1.630141.65578
1.674291.68819
1.69389
1.69888
1.72393
1.72795
1.72987
1.73151
1.73159||pk − Lk ||2 λ−k
30.00125947
0.000698321
0.000476193
0.000368108
0.000308768
0.000274089
0.000240445
0.000227422
0.000221951
0.000219452
0.00021823
0.000217604
0.000217414
0.000217275
0.00021691
0.000216896
0.000216892
0.000216892
0.000216892

Table 3: The convergence of the random walk to the uniform distribution.

18