A long computation: the Chebotarev invariant of the Rubik’s group

Motivated by a recent post on God Plays Dice concerning the maximal order of elements in the Rubik’s group (the permutation group that describes the movements of the divine cube), I of course decided to try to compute how many conjugacy classes in it you typically need to know to generate the whole group — in other (self-coined) words, I decided to entrust to Magma the computation of the Chebotarev invariant of this group of order 43252003274489856000.

After two days of hard work on my desktop computer, Magma gave the following answer: the expectation of the waiting time is 5.6686453… and the expectation of the square is 36.7870098… (giving a standard deviation slightly larger than 2). This is actually the longest individual computation I’ve performed myself, and it took about 1 Gb memory; computing the 20 conjugacy classes of maximal subgroups was done in about 1.3 seconds, computing the 81120 conjugacy classes took 45 seconds more, and then precomputing the matrix indicating which subgroups intersected which conjugacy class was roughly one day long, the second day being devoted to the alternating sum over the 220-1 non-empty subsets of maximal subgroups (with the formula indicated at the end of my original post defining the Chebotarev invariant) — this is about one million steps.

The computation was done with floating point numbers with 30 digits precision, but I think the last 10 or so are not to be trusted (and I did not write them down), since they come from this alternating sum with a million terms (but I would trust the first 15, say, because the summands are rationals, hence the approximations used for individual terms are really correct to 30 digits).

Published by

Kowalski

I am a professor of mathematics at ETH Zürich since 2008.

One thought on “A long computation: the Chebotarev invariant of the Rubik’s group”

  1. I found your website when I checked my method to compute the number of conjugacy classes. See the above website. My method was splitting up the problem in a corner problem and an edge problem first. Next, I wrote a procedure (in Maple) with two parameters, which solves the corner problem with parameters (8,3) and the edge problem with parameters (12,2). I really have no idea what your method is.

Leave a Reply to brac37 Cancel reply

Your email address will not be published. Required fields are marked *