Each quarter turn of a Rubik's cube permutes its 54 coloured stickers, so the
positions reachable from the solved cube correspond to the subgroup of the
symmetric group on 54 points generated by the six face turns. Lean can prove
its order with perm_group:
namespaceRubiksCubeTutorialdefU:Equiv.Perm(Fin54):=c[0,2,8,6]*c[1,5,7,3]*c[9,18,36,45]*c[10,19,37,46]*c[11,20,38,47]defR:Equiv.Perm(Fin54):=c[2,51,29,20]*c[5,48,32,23]*c[8,45,35,26]*c[9,11,17,15]*c[10,14,16,12]defF:Equiv.Perm(Fin54):=c[6,9,29,44]*c[7,12,28,41]*c[8,15,27,38]*c[18,20,26,24]*c[19,23,25,21]defD:Equiv.Perm(Fin54):=c[15,51,42,24]*c[16,52,43,25]*c[17,53,44,26]*c[27,29,35,33]*c[28,32,34,30]defL:Equiv.Perm(Fin54):=c[0,18,27,53]*c[3,21,30,50]*c[6,24,33,47]*c[36,38,44,42]*c[37,41,43,39]defB:Equiv.Perm(Fin54):=c[0,42,35,11]*c[1,39,34,14]*c[2,36,33,17]*c[45,47,53,51]*c[46,50,52,48]/-- The positions reachable by turning the faces. -/defRubikGroup:Subgroup(Equiv.Perm(Fin54)):=Subgroup.closure{U,R,F,D,L,B}theoremcard_rubikGroup:Nat.cardRubikGroup=43252003274489856000:=⊢ Nat.card↥RubikGroup=43252003274489856000All goals completed! 🐙endRubiksCubeTutorial
The perm_group tactic comes from HexPermGroupTheory.
It runs the Schreier–Sims algorithm in compiled code to build a certificate
for a stabilizer chain of the group. Lean's kernel checks the certificate, so
the theorem depends only on the standard axioms.
Each face has nine stickers, numbered consecutively on the up, right, front,
down, left and back faces in that order. Unfolded, with the front face in the
middle, the numbering is:
Each turn above is a clockwise quarter turn of one face, seen from outside the
cube, written in Mathlib's cycle notation as five 4-cycles. Two of them move
the face's own corner and edge stickers. Each of the other three moves one
sticker on each of the four neighbouring faces. For example, U sends sticker
0 to 2, and moves the top row of the front face (18, 19, 20) onto the
left face. The centre stickers 4, 13, 22, 31, 40 and 49 never move.
Turning faces cannot twist a single corner, flip a single edge, or exchange
two edges while leaving every other piece in place. The permutations below do
each of these. The corner with stickers 8, 9 and 20 lies between the up,
right and front faces. The edge with stickers 7 and 19 lies between the up
and front faces, and the edge with stickers 5 and 10 between the up and
right faces.
namespaceRubiksCubeTutorial/-- Turn the up-right-front corner a third of a turn. -/deftwist:Equiv.Perm(Fin54):=c[8,9,20]/-- Flip the up-front edge. -/defflip:Equiv.Perm(Fin54):=c[7,19]/-- Exchange the up-front and up-right edges. -/defswap:Equiv.Perm(Fin54):=c[5,7]*c[10,19]theoremtwist_not_mem:twist∉RubikGroup:=⊢ twist∉RubikGroupAll goals completed! 🐙theoremflip_not_mem:flip∉RubikGroup:=⊢ flip∉RubikGroupAll goals completed! 🐙theoremswap_not_mem:swap∉RubikGroup:=⊢ swap∉RubikGroupAll goals completed! 🐙endRubiksCubeTutorial
By hand, one would show that every face turn preserves three invariants: the
corner twists sum to zero modulo 3, the edge flips sum to zero modulo 2, and
the corner and edge permutations have the same sign. perm_group does not use
these invariants. It sifts each permutation through the stabilizer chain of
RubiksCubeTutorial.RubikGroup, and the kernel checks that the sift
fails. The chain itself is checked once, while proving card_rubikGroup, and
the three proofs above reuse it.
If the cube may be taken apart and put back together, the eight corners can go
into the corner slots in any order, each in any of three orientations. The
twelve edges can go into the edge slots in any order, each in either
orientation. That gives 8! · 3⁸ · 12! · 2¹² positions, and adding twist,
flip and swap to the six face turns generates all of them:
The index is 12 = 3 · 2 · 2: the factors come from the corner-twist sum, the
edge-flip sum and the relative sign of the corner and edge permutations. If
every reassembled position is equally likely, a cube put back together at
random can be solved with probability 1/12.
perm_group does not call GAP, or any other program: the certificate is built
by compiled Lean code in HexPermGroup and checked by Lean's kernel. For
comparison only, we timed GAP, a separate computer algebra system, computing
the same order from the same six generators.
GAP takes about 3 milliseconds. perm_group spends about 60 milliseconds
building its certificate in compiled code, about 25 times as long as GAP, and
Lean's kernel then takes about three seconds to check it. For the sporadic
group M24, GAP takes under half a millisecond, building the certificate about
two and a half milliseconds, and checking it about a third of a second. The
measurements, for nine sporadic groups as well as the cube, are in
reports/20261006-perm-group-gap-comparison.md of the hex-dev repository.
Mathlib's Subgroup.closure does not compute orders or orbits, so for these
computations we build the same group in HexPermGroup.
Perm.ofEquiv converts each turn to a Hex.Perm:
The 24 corner stickers form one orbit and the 24 edge stickers another: turns
can carry any corner sticker to any other, but never to an edge. The six
centres are fixed.
By the orbit-stabilizer theorem, the stabilizer of sticker 8 has 1/24 of
the group's order. Fixing sticker 8 fixes both the position and the
orientation of its corner, so stickers 9 and 20 are fixed too: the
stabilizer of 8 is the subgroup fixing all three.
With that corner fixed, the other 21 corner stickers form one orbit and the 24
edge stickers another. The twist, flip and parity invariants still restrict
how the pieces can be arranged at the same time.
These numbers are computed by #eval and are not checked by the kernel. The
theorems Hex.PermGroup.Group.order_card and
Hex.PermGroup.Group.contains_spec identify the computed order and
membership test with the cardinality of, and membership in, the corresponding
Mathlib subgroup; see the HexPermGroup chapter.