I’m interested in some questions about the computational complexity of bounding the mixing time of random walks on Cayley-graphs of finite groups like that of the Rubik’s Cube Group $ G$ . Determining that $ 20$ is the diameter (God’s number) of the Rubik’s Cube Group under the half-turn metric with Singmaster generating set $ s=\langle U, U’, U^2, D, D’, D^2,\cdots\rangle$ was a wonderful result. I’m curious about follow-up questions, such as determining how many half-turn twists would it take to get the cube fully “mixed” to $ \epsilon$ -close to the uniform stationary distribution $ \pi$ , say in the variational distance sense.

For example, noting that there are $ 18$ moves in the half-turn metric, and calling $ n$ the mixing time, can we say something like:

For all but a very small number of elements of $ g\in G$ , are there very close to $ \frac{18^n}{\vert G \vert}$ ways of writing $ g$ as words of length $ \le n$ ?

My intuition is that, after the cube is fully mixed with $ n$ moves, there should not be a large special subset $ A\subset G$ of elements that need a lot more or a lot less than $ 18^n$ ways of writing them, starting from the solved position. On the other hand, if the cube has only been scrambled with $ m\lt n$ twists, then there *should be* a large subset $ A$ that has elements that are in some sense maybe only writable with no more than $ \frac{18^m}{2\vert G \vert}$ different words of length $ \le m$ .

I think we can combine approximate counting techniques to parlay such gaps into an Arthur-Merlin protocol to verify the mixing time is $ \ge n$ :

- Arthur chooses a random element of $ g$ , a random hash $ h$ mapping words of $ G$ onto a set of size $ \frac{18^n}{\vert G \vert}$ , and a random image $ y$ of $ h$
- Merlin tells Arthur a word $ W$ of length up to $ n$ that, when applied to the starting position of the cube, equals $ g$
- The word $ W$ must also satisfy $ h(W)=y$ – indicating that there are likely a
*lot* of words of length $ \le n$ that equal $ g$
- Arthur repeats with Merlin to amplify as needed

Because, for groups I think, the mixing time is at least the diameter, this also may provide an Arthur-Merlin approach to bound the diameter of a large group.