Timeline for Number of positions of Rubik's cube grows with multiplier 13 with the distance - what are explanations and groups with similar growth pattern?
Current License: CC BY-SA 4.0
24 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 13, 2019 at 20:14 | comment | added | Alexander Chervov | 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 ? | |
| Feb 12, 2019 at 20:34 | comment | added | Derek Holt | 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. | |
| Feb 12, 2019 at 20:22 | comment | added | Alexander Chervov | 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? | |
| Feb 12, 2019 at 6:42 | vote | accept | Alexander Chervov | ||
| Feb 11, 2019 at 17:52 | comment | added | Derek Holt | @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! | |
| Feb 11, 2019 at 8:12 | history | edited | Derek Holt | CC BY-SA 4.0 |
added 541 characters in body
|
| Feb 11, 2019 at 6:56 | comment | added | user21820 | @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). | |
| Feb 10, 2019 at 22:39 | comment | added | Derek Holt | @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! | |
| Feb 10, 2019 at 21:00 | comment | added | YCor | 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). | |
| Feb 10, 2019 at 20:54 | comment | added | Derek Holt | I did the calculation in Magma - I have appended the code. | |
| Feb 10, 2019 at 20:53 | history | edited | Derek Holt | CC BY-SA 4.0 |
added 564 characters in body
|
| Feb 10, 2019 at 19:06 | comment | added | Alexander Chervov | May be you can insert you code in the answer or a link to github | |
| Feb 10, 2019 at 16:39 | comment | added | Derek Holt | 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. | |
| Feb 10, 2019 at 16:34 | history | edited | Derek Holt | CC BY-SA 4.0 |
added 16 characters in body
|
| Feb 10, 2019 at 16:31 | comment | added | Alexander Chervov | @MarkS thank you for asking! I was 'afraid to ask')) | |
| Feb 10, 2019 at 16:30 | comment | added | Alexander Chervov | @NoahSnyder any idea what are the other relations? I was under impression that these are the only, but seems to be wrong. | |
| Feb 10, 2019 at 16:30 | comment | added | Mark S | This is likely a dumb question but is the group in the edit even finite? | |
| Feb 10, 2019 at 16:17 | comment | added | Noah Snyder | 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. | |
| Feb 10, 2019 at 16:16 | comment | added | Noah Snyder | 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! | |
| Feb 10, 2019 at 16:12 | comment | added | Alexander Chervov | 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? | |
| Feb 10, 2019 at 14:49 | comment | added | Alexander Chervov | Impressive answer and received so fast. Thank you very much! | |
| Feb 10, 2019 at 14:18 | comment | added | Mark S | 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. | |
| Feb 10, 2019 at 12:56 | history | edited | Derek Holt | CC BY-SA 4.0 |
added 482 characters in body
|
| Feb 10, 2019 at 12:30 | history | answered | Derek Holt | CC BY-SA 4.0 |