13
$\begingroup$

Rubik's cube and its generalizations attracts certain attention of mathematical community. It is somehow "noteworthy" that it has been proved that diameter of the Rubik's cube group is 20, i.e. cubik can be turned into initial position at worst at 20 moves. It rises certain interesting questions e.g. MO139469.

Not only the diameter has been calculated, but the position count for all distances presented has been too. If one plots it at logarithmic scale one sees linear dependence almost everywhere:

Log(number of positions)

So looking more carefully we see that number of positions at next step is approximately 13 times greater (see details below).

Question 1 Is there some explanation of such exponential grow ?

Question 2 What are the other examples of groups with similar growth pattern ?

Remarks: What seems puzzling for me, that exponential growth corresponds to (for example) free group (obviously number of words of length n in k-letter alphabet is k^n), but for groups+generators which are similar to abelian groups the growth should be similar to normal distribution (a version of central limit theorem) - for example for $(Z/2Z)^n$ it corresponds to the setup of the most classical central limit theorem, which can be visualized by the Galton board (Bean machine). Similar results has been extented to permutation groups and metrics of them see MO320497. So it is somehow strange for me that Rubik's group+generators looks like free group, rather than abelian.


Datum (from http://www.cube20.org) + Python code:

# Distance      Count of Positions  
datum  =[ 0 ,   1   ,
1   ,   18  ,
2   ,   243 ,
3   ,   3240    ,
4   ,   43239   ,
5   ,   574908  ,
6   ,   7618438 ,
7   ,   100803036   ,
8   ,   1332343288  ,
9   ,   17596479795 ,
10  ,   2.32248E+11 ,
11  ,   3.06329E+12 ,
12  ,   4.03744E+13 ,
13  ,   5.31653E+14 ,
14  ,   6.98932E+15 ,
15  ,   9.13651E+16 ,
16  ,   1.1E+18 ,
17  ,   1.2E+19 ,
18  ,   2.9E+19 ,
19  ,   1.5E+18 ,
20  ,   490000000 ]

import matplotlib.pyplot as plt
import numpy as np
plt.plot(np.log( datumCount),'*-' )
plt.xlabel('Distance')
plt.ylabel('Log(number of positions)')
plt.show()

datumCount = datum[1::2]
print( np.array(datumCount[1:])/np.array( datumCount[:-1]) )

[1.80000000e+01 1.35000000e+01 1.33333333e+01 1.33453704e+01
 1.32960522e+01 1.32515776e+01 1.32314572e+01 1.32172933e+01
 1.32071666e+01 1.31985490e+01 1.31897368e+01 1.31800776e+01
 1.31680718e+01 1.31463944e+01 1.30721014e+01 1.20396081e+01
 1.09090909e+01 2.41666667e+00 5.17241379e-02 3.26666667e-10]
$\endgroup$
  • 3
    $\begingroup$ This hole at $n=3$ is very weird, if not suspicious. Actually, if $b(n)$ is the cardinal of the $n$-ball, one has $b(6)\le b(3)^2$, which is not satisfied here with $b(3)^2=(324+243+18+1)^2=343396$. Stupid interpolation would naturally expect a value for the cardinal of the 3-sphere between 3200 and 3300. 324 thus sound like a misprint, it's probably something around 3240. $\endgroup$ – YCor Feb 10 at 17:56
  • 3
    $\begingroup$ Well, checked OEIS: oeis.org/A080601, it's indeed 3240. $\endgroup$ – YCor Feb 10 at 18:03
  • $\begingroup$ @YCor thank you very much ! I rechecked the datum - it is indeed 3240. I corrected the post. $\endgroup$ – Alexander Chervov Feb 10 at 19:26
21
$\begingroup$

This is a very crude attempt to explain the growth rate of $13$, can be almost certainly be improved upon.

In the situation where $20$ is the diameter, there are $18$ moves (or monoid generators), with three moves for each face, i.e. two quarter-turns and on half-turn.

For each position except for the starting position, moving the same face as on the previous move will not yield a new position, so that reduces the number of moves to new positions to $15$.

I think the main reason why we get $13$ rather than $15$ is that moves of opposite faces commute. In approximately $1/5$ of the positions, the penultimate move commutes with the last move. In those cases, moving the opposite face to the final move will not give a new position (but unfortunately I think the $1/5$ is an overestimate).

In the remaining $4/5$ of the positions, moving the opposite face will give a position that could also have been reached by moving the opposite face first. So the number of new positions reached in this way should be divided by two.

That yields an estimate of $12/4 + 4(12 + 3/2)/5 = 66/5$, which is just slightly more than $13$.

But on reflection, I think the proportion of positions where the final two moves commute is closer to $1/10$ than $1/5$, giving the estimate $12/10 + 9(12+3/2)/5 = 267/20 = 13.35$.

Of course these are all overestimates, because there are other group relations that reduce the number of positions, but I believe that I have identified the principal relations involved that reduce the growth rate from that of the free monoid.

Added later After writing the above, I realized that my estimate is calculating the growth rate of the group with the presentation $$\langle a_i, b_i\ (1 \le i \le 6) \mid a_i^4= 1,a_i^2=b_i\ (1 \le i\le 6), a_1a_4=a_4a_1,a_2a_5=a_5a_2,a_3a_6=a_6a_3 \rangle,$$

and that I could do that exactly on the computer. So I did, and the principal term in the growth function came out as (a multiple of) $(13.3485)^n$, which is surprsingly (to me) close to my second crude estimate of $13.35$.

I did this computation in Magma - here is the code, followed by the Taylor series expansion of the growth function $f$.

> G := Group<a,a2,b,b2,c,c2,d,d2,e,e2,f,f2 | a^4,b^4,c^4,d^4,e^4,f^4,
>                          a^2=a2,b^2=b2,c^2=c2,d^2=d2, e^2=e2,f^2=f2,
>                          a*d=d*a, b*e=e*b, c*f=f*c >;
> A := AutomaticGroup(G);
> f := GrowthFunction(A);
> PZ<x> := FunctionField(IntegerRing());
> PZ!f;
  (-9*x^2 - 6*x - 1)/(18*x^2 + 12*x - 1)
> PR := PolynomialRing( RealField(6) );
> [ r[1]^-1 : r in Roots(PR!Denominator(f)) ];
  [ -1.34847, 13.3485 ]

> LR<x> := LaurentSeriesRing(Z);
> LR!f;
1 + 18*x + 243*x^2 + 3240*x^3 + 43254*x^4 + 577368*x^5 + 7706988*x^6 + 
  102876480*x^7 + 1373243544*x^8 + 18330699168*x^9 + 244686773808*x^10 + 
  3266193870720*x^11 + 43598688377184*x^12 + 581975750199168*x^13 + 
  7768485393179328*x^14 + 103697388221736960*x^15 + 1384201395738071424*x^16 +
  18476969736848122368*x^17 + 246639261965462754048*x^18 + 
  3292256598848819251200*x^19 + O(x^20)
$\endgroup$
  • 3
    $\begingroup$ Lovely! The diameter under the quarter-turn metric is 26 - quarter-turns have less of a problem with wherein moving the same face twice doesn't yield a new position. The growth rate under the quarter-turn metric starts out at around $n^9$ but then appears to saturate after move 20 or so. $\endgroup$ – Mark S Feb 10 at 14:18
  • 3
    $\begingroup$ Most of the comments have been answered! The group with which I did the calculation is an infinite automatic group, and you can calculate its growth rate from its word acceptor automaton. You can do that in my KBMAG package, which is accessible from GAP or Magma. It would be interesting to know what are the shortest additional relations in the Rubik cube group, because they might enable a more accurate calculation. There are relations like $(b_ib_j)^6=1$, but adjoining them made virtually no difference to the growth rate. $\endgroup$ – Derek Holt Feb 10 at 16:39
  • 2
    $\begingroup$ Next one could compute the cardinal of spheres in this infinite group and check to which extent it matches with the spheres in the Rubik cube's group (which I guess is a quotient although I can't read it explicit stated). $\endgroup$ – YCor Feb 10 at 21:00
  • 2
    $\begingroup$ @DerekHolt: The simplest commutators are length 8, and perform a 3-cycle on some blocks of pieces (usually 3 corners). There is also the 2-pair swap (F2R2F2R2F2R2), and the 3-cycle on edges (F2U'DR2UD'), which can also be done in 8-half-turns (R2U2F2U2R2U2F2U2). $\endgroup$ – user21820 Feb 11 at 6:56
  • 2
    $\begingroup$ The problem is that if you make all words of length $k$ relators then that will imply many relators of length less than $k$. Since free groups $F$ are residually finite, there exists a finite quotient $F/N$ such that all reduced words of length at most $k$ in $F$ map onto distinct elements of $F/N$, and so $F/N$ has the same growth as $F$ up to length $k$, but I have no idea how large $F/N$ would have to be. In any case this sounds like a new question. $\endgroup$ – Derek Holt Feb 12 at 20:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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