By Alexander Chervov


2019-02-10 11:42:11 8 Comments

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]

1 comments

@Derek Holt 2019-02-10 12:30:40

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)

@Mark S 2019-02-10 14:18:05

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.

@Alexander Chervov 2019-02-10 14:49:34

Impressive answer and received so fast. Thank you very much!

@Alexander Chervov 2019-02-10 16:12:54

Concerning 'added later' : what software do you use? I am also puzzled - the group you presented is it Rubiks group or Rubiks is its quotient?

@Noah Snyder 2019-02-10 16:16:01

If I’m reading the data right, the slope starts off quite close to your answer and then slowly decreases to get closer to 13 (as your approximation should be expected to worsen). What a great answer!

@Noah Snyder 2019-02-10 16:17:08

Rubik’s cube group is a quotient if the group in the edit, because all those relations hold in the Rubik’s group but so do further relations.

@Mark S 2019-02-10 16:30:27

This is likely a dumb question but is the group in the edit even finite?

@Alexander Chervov 2019-02-10 16:30:44

@NoahSnyder any idea what are the other relations? I was under impression that these are the only, but seems to be wrong.

@Alexander Chervov 2019-02-10 16:31:59

@MarkS thank you for asking! I was 'afraid to ask'))

@Derek Holt 2019-02-10 16:39:35

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.

@Mark S 2019-02-10 17:08:32

Your $b_i$'s are the half-turns - and removing $a_i^2=b_i$ from your presentation might lead to the putative growth guessed from cube20.org/qtm ?

@Alexander Chervov 2019-02-10 19:06:40

May be you can insert you code in the answer or a link to github

@Derek Holt 2019-02-10 20:54:23

I did the calculation in Magma - I have appended the code.

@YCor 2019-02-10 21:00:20

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).

@Derek Holt 2019-02-10 22:39:56

@YCor I have calculated the Taylor series expansion of the growth function $f$, and you can compare its coefficients with the numbers of elements of the corresponding lengths in the Rubik cube group (which is indeed a quotient of the infinite group). There is a small difference at length $4$, and so I guess there must be new relators of length $8$ in the Rubik cube group. I must try anb find out what they are!

@user21820 2019-02-11 06:56:00

@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).

@Derek Holt 2019-02-11 17:52:39

@user21820 I found $15$ relations of length $8$ and tried adding these to the presentation. The result was still infinite automatic and the growth rate had gone down to $13.339$. Then there appear to be $1824$ relations of length $10$, so I will give up at this point!

@Alexander Chervov 2019-02-12 20:22:04

Is my understanding correct: if I want to find a finite group with similar growth function I can take e.g. Free group and factorize by all words of lengh 'k'. So i will get exponential growth which abrupts at stage k. Or there any caveats?

@Derek Holt 2019-02-12 20:34:33

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.

@Alexander Chervov 2019-02-13 20:14:04

Thank you ! Concerning defining relations - from here : math.stackexchange.com/a/397916/21498 and your comments it seems that defining relations for standard generators are not known , is it correct ?

Related Questions

Sponsored Content

3 Answered Questions

0 Answered Questions

Counting the number of Rubik's cube states in which k = 0 to 4 of the faces are "solved"

  • 2012-12-20 06:28:19
  • FloatingForest
  • 317 View
  • 1 Score
  • 0 Answer
  • Tags:   co.combinatorics

Sponsored Content