hex

38.6. The Rubik's cube group🔗

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:

namespace RubiksCubeTutorial def U : Equiv.Perm (Fin 54) := 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] def R : Equiv.Perm (Fin 54) := 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] def F : Equiv.Perm (Fin 54) := 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] def D : Equiv.Perm (Fin 54) := 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] def L : Equiv.Perm (Fin 54) := 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] def B : Equiv.Perm (Fin 54) := 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. -/ def RubikGroup : Subgroup (Equiv.Perm (Fin 54)) := Subgroup.closure {U, R, F, D, L, B} theorem card_rubikGroup : Nat.card RubikGroup = 43252003274489856000 := ⊢ Nat.card ↥RubikGroup = 43252003274489856000 All goals completed! 🐙 end RubiksCubeTutorial

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.

38.6.1. Stickers and turns🔗

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:

             0  1  2
             3  4  5
             6  7  8
 36 37 38   18 19 20    9 10 11   45 46 47
 39 40 41   21 22 23   12 13 14   48 49 50
 42 43 44   24 25 26   15 16 17   51 52 53
            27 28 29
            30 31 32
            33 34 35

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.

38.6.2. Positions that cannot be reached🔗

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.

namespace RubiksCubeTutorial /-- Turn the up-right-front corner a third of a turn. -/ def twist : Equiv.Perm (Fin 54) := c[8, 9, 20] /-- Flip the up-front edge. -/ def flip : Equiv.Perm (Fin 54) := c[7, 19] /-- Exchange the up-front and up-right edges. -/ def swap : Equiv.Perm (Fin 54) := c[5, 7] * c[10, 19] theorem twist_not_mem : twist ∉ RubikGroup := ⊢ twist ∉ RubikGroup All goals completed! 🐙 theorem flip_not_mem : flip ∉ RubikGroup := ⊢ flip ∉ RubikGroup All goals completed! 🐙 theorem swap_not_mem : swap ∉ RubikGroup := ⊢ swap ∉ RubikGroup All goals completed! 🐙 end RubiksCubeTutorial

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.

38.6.3. Taking the cube apart🔗

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:

namespace RubiksCubeTutorial /-- The positions reachable by turning faces and reassembling pieces. -/ def Assembly : Subgroup (Equiv.Perm (Fin 54)) := Subgroup.closure {U, R, F, D, L, B, twist, flip, swap} theorem card_assembly : Nat.card Assembly = 519024039293878272000 := ⊢ Nat.card ↥Assembly = 519024039293878272000 All goals completed! 🐙 theorem rubikGroup_le_assembly : RubikGroup ≤ Assembly := ⊢ RubikGroup ≤ Assembly ⊢ {U, R, F, D, L, B} ⊆ {U, R, F, D, L, B, twist, flip, swap} x:Equiv.Perm (Fin 54)hx:x ∈ {U, R, F, D, L, B}⊢ x ∈ {U, R, F, D, L, B, twist, flip, swap} x:Equiv.Perm (Fin 54)hx:x = U ∨ x = R ∨ x = F ∨ x = D ∨ x = L ∨ x = B⊢ x ∈ {U, R, F, D, L, B, twist, flip, swap} ⊢ U ∈ {U, R, F, D, L, B, twist, flip, swap}⊢ R ∈ {U, R, F, D, L, B, twist, flip, swap}⊢ F ∈ {U, R, F, D, L, B, twist, flip, swap}⊢ D ∈ {U, R, F, D, L, B, twist, flip, swap}⊢ L ∈ {U, R, F, D, L, B, twist, flip, swap}⊢ B ∈ {U, R, F, D, L, B, twist, flip, swap} ⊢ U ∈ {U, R, F, D, L, B, twist, flip, swap}⊢ R ∈ {U, R, F, D, L, B, twist, flip, swap}⊢ F ∈ {U, R, F, D, L, B, twist, flip, swap}⊢ D ∈ {U, R, F, D, L, B, twist, flip, swap}⊢ L ∈ {U, R, F, D, L, B, twist, flip, swap}⊢ B ∈ {U, R, F, D, L, B, twist, flip, swap} All goals completed! 🐙 theorem relIndex_rubikGroup : RubikGroup.relIndex Assembly = 12 := ⊢ RubikGroup.relIndex Assembly = 12 h:RubikGroup.relIndex Assembly * Nat.card ↥(RubikGroup ⊓ Assembly) = Nat.card ↥Assembly⊢ RubikGroup.relIndex Assembly = 12 h:RubikGroup.relIndex Assembly * 43252003274489856000 = 519024039293878272000⊢ RubikGroup.relIndex Assembly = 12 exact Nat.eq_of_mul_eq_mul_right (h:RubikGroup.relIndex Assembly * 43252003274489856000 = 519024039293878272000⊢ 0 < 43252003274489856000 All goals completed! 🐙) (h.trans (h:RubikGroup.relIndex Assembly * 43252003274489856000 = 519024039293878272000⊢ 519024039293878272000 = 12 * 43252003274489856000 All goals completed! 🐙)) end RubiksCubeTutorial

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.

38.6.4. How long this takes🔗

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.

38.6.5. Where a sticker can go🔗

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:

namespace RubiksCubeTutorial open Hex Hex.PermGroup def cube : Group 54 := Group.ofGenerators (#[U, R, F, D, L, B].map Perm.ofEquiv) end RubiksCubeTutorial

The stickers fall into eight orbits:

#[24, 24, 1, 1, 1, 1, 1, 1]#eval RubiksCubeTutorial.cube.orbits.map (·.size)
#[24, 24, 1, 1, 1, 1, 1, 1]

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.

(1802166803103744000, 1802166803103744000)#eval ((RubiksCubeTutorial.cube.stabilizer 8).order, (RubiksCubeTutorial.cube.pointwise [8, 9, 20]).order)
(1802166803103744000, 1802166803103744000)

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.

#[21, 24, 1, 1, 1, 1, 1, 1, 1, 1, 1]#eval (RubiksCubeTutorial.cube.stabilizer 8).orbits.map (·.size)
#[21, 24, 1, 1, 1, 1, 1, 1, 1, 1, 1]

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.