stylewarning/cl-permutation

Shortest path to a trivial cubic?

Closed this issue · 3 comments

jcguu95 commented

Since the action of the rubik group on the set of rubik states is free, the following proves that there are exactly43252003274489856000 different states on a 3x3 rubik's cube (well done!).

(group-order rubik-3x3)
43252003274489856000

I have heard a rumor that no matter which state you start with, there is a solution taking at most 20 steps to solve a 3x3 rubik cube. Can this program help compute this too?

stylewarning commented

@jcguu95 This is a great question but this is an extremely difficult thing to prove and, to my knowledge, requires an enormous amount of calculation to enumerate and optimally solve a lot of coset classes.

The source code that was run on a huge cluster of computers to prove the result is here.

CL-PERMUTATION can routinely enumerate all positions of a smaller group, though. And it has tools to study other properties of groups and their subgroups as well.

jcguu95 commented

Oh, thanks for pointing out that code. Do you happen if their algorithm involves something more sophisticated than a brute-force method? More generally, I wonder what strong generating sets can tell us beyond

  1. the order of a finite group
  2. if an permutation element belongs to a certain subgroup
stylewarning commented

It can give us a (non-optimal) decomposition of an element in terms of generators. (As such, it can give us an upper bound on the length of such sequences.)

It can determine whether a given group is a subgroup of another.

It can determine whether a given group is a normal subgroup of another.

It can give us a map to any group element and an integer between $0$ and $\vert G\vert-1$.

It allows us to produce a uniformly random element of a group.

Those are prominent examples.

  • ❤️1