Examples
Analyzing Rubik's Cube using GAP.jl
The following Julia session shows the GAP computations from the Rubik's Cube example from the GAP webpages.
We consider the group of transformations of Rubik's magic cube. If we number the faces of this cube as follows
+--------------+
| |
| 1 2 3 |
| |
| 4 top 5 |
| |
| 6 7 8 |
| |
+--------------+--------------+--------------+--------------+
| | | | |
| 9 10 11 | 17 18 19 | 25 26 27 | 33 34 35 |
| | | | |
| 12 left 13 | 20 front 21 | 28 right 29 | 36 rear 37 |
| | | | |
| 14 15 16 | 22 23 24 | 30 31 32 | 38 39 40 |
| | | | |
+--------------+--------------+--------------+--------------+
| |
| 41 42 43 |
| |
| 44 bottom 45 |
| |
| 46 47 48 |
| |
+--------------+then the group is generated by the following generators, corresponding to the six faces of the cube.
julia> cube = @gap("Group(
( 1, 3, 8, 6)( 2, 5, 7, 4)( 9,33,25,17)(10,34,26,18)(11,35,27,19),
( 9,11,16,14)(10,13,15,12)( 1,17,41,40)( 4,20,44,37)( 6,22,46,35),
(17,19,24,22)(18,21,23,20)( 6,25,43,16)( 7,28,42,13)( 8,30,41,11),
(25,27,32,30)(26,29,31,28)( 3,38,43,19)( 5,36,45,21)( 8,33,48,24),
(33,35,40,38)(34,37,39,36)( 3, 9,46,32)( 2,12,47,29)( 1,14,48,27),
(41,43,48,46)(42,45,47,44)(14,22,30,38)(15,23,31,39)(16,24,32,40) );")
GAP: <permutation group with 6 generators>First we want to know the size of this group.
julia> cube_size = GAP.Globals.Size(cube)
GAP: 43252003274489856000Since this is a little bit unhandy, let us factorize this number.
julia> cf = GAP.Globals.Collected(GAP.Globals.Factors(cube_size))
GAP: [ [ 2, 27 ], [ 3, 14 ], [ 5, 3 ], [ 7, 2 ], [ 11, 1 ] ](The result tells us that the size is $2^{27} 3^{14} 5^3 7^2 11$.)
In order to convert this GAP list to Julia, we can either use gap_to_julia or a suitable Vector constructor, see Conversions. Note that the one-argument version of the former returns a vector of Any objects.
julia> GAP.gap_to_julia(cf)
5-element Vector{Any}:
Any[2, 27]
Any[3, 14]
Any[5, 3]
Any[7, 2]
Any[11, 1]
julia> Vector{Vector{Int}}(cf)
5-element Vector{Vector{Int64}}:
[2, 27]
[3, 14]
[5, 3]
[7, 2]
[11, 1]Next let us investigate the operation of the group on the 48 points.
julia> orbs = GAP.Globals.Orbits(cube, GapObj(1:48))
GAP: [ [ 1, 3, 17, 14, 8, 38, 9, 41, 19, 48, 22, 6, 30, 33, 43, 11, 46, 40, 24, 27, 25, 35, 16, 32 ], [ 2, 5, 12, 7, 36, 10, 47, 4, 28, 45, 34, 13, 29, 44, 20, 42, 26, 21, 37, 15, 31, 18, 23, 39 ] ]
julia> length(orbs)
2The first orbit contains the points at the corners, the second those at the edges; clearly the group cannot move a point at a corner onto a point at an edge.
So to investigate the cube group we first investigate the operation on the corner points. Note that the constructed group that describes this operation will operate on the set [1..24], not on the original set orbs[1].
julia> cube1 = GAP.Globals.Action(cube, orbs[1])
GAP: <permutation group with 6 generators>
julia> GAP.Globals.NrMovedPoints(cube1)
24
julia> GAP.Globals.Size(cube1)
88179840Now this group obviously operates transitively, but let us test whether it is also primitive.
julia> corners = GAP.Globals.Blocks(cube1, GAP.Globals.MovedPoints(cube1))
GAP: [ [ 1, 7, 22 ], [ 2, 14, 20 ], [ 3, 12, 16 ], [ 4, 17, 18 ], [ 5, 9, 21 ], [ 6, 10, 24 ], [ 8, 11, 23 ], [ 13, 15, 19 ] ]Those eight blocks correspond to the eight corners of the cube; on the one hand the group permutes those and on the other hand it permutes the three points at each corner cyclically.
julia> blockhom1 = GAP.Globals.ActionHomomorphism(cube1, corners, GAP.Globals.OnSets)
GAP: <action homomorphism>
julia> cube1b = GAP.Globals.Image(blockhom1)
GAP: Group([ (1,2,4,3), (1,3,6,5), (1,5,8,2), (3,4,7,6), (5,6,7,8), (2,8,7,4) ])
julia> GAP.Globals.Size(cube1b)
40320Now a permutation group of degree 8 that has order 40320 must be the full symmetric group Sym(8) on eight points.
The next thing then is to investigate the kernel of this operation on blocks, i.e., the subgroup of cube1 of those elements that fix the blocks setwise.
julia> ker1 = GAP.Globals.Kernel(blockhom1)
GAP: <permutation group with 7 generators>
julia> println(Vector{Int}(GAP.Globals.Factors(GAP.Globals.Size(ker1))))
[3, 3, 3, 3, 3, 3, 3]
julia> GAP.Globals.IsElementaryAbelian(ker1)
trueWe can show that the product of this elementary abelian group $3^7$ with the Sym(8) is semidirect by finding a complement, i.e., a subgroup that has trivial intersection with the kernel and that generates cube1 together with the kernel.
julia> cmpl1 = GAP.Globals.ComplementClassesRepresentatives(cube1, ker1)
GAP: [ <permutation group of size 40320 with 7 generators> ]
julia> cmpl1 = cmpl1[1]; GAP.Globals.Size(cmpl1)
40320We verify the complement properties:
julia> GAP.Globals.Size(GAP.Globals.Intersection(cmpl1, ker1))
1
julia> GAP.Globals.ClosureGroup(cmpl1, ker1) == cube1
trueThere is even a more elegant way to show that cmpl1 is a complement.
julia> GAP.Globals.IsBijective(GAP.Globals.RestrictedMapping(blockhom1, cmpl1))
trueOf course, theoretically it is clear that cmpl1 must indeed be a complement.
In fact we know that cube1 is a subgroup of index 3 in the wreath product of a cyclic 3 with Sym(8). This missing index 3 tells us that we do not have total freedom in turning the corners. The following tests show that whenever we turn one corner clockwise we must turn another corner counterclockwise.
julia> @gap("(1, 7, 22)") in cube1
false
julia> @gap("(1, 7, 22)(2, 20, 14)") in cube1
trueMore or less the same things happen when we consider the operation of the cube group on the edges.
julia> cube2 = GAP.Globals.Action(cube, orbs[2]); GAP.Globals.Size(cube2)
980995276800
julia> edges = GAP.Globals.Blocks(cube2, GAP.Globals.MovedPoints(cube2))
GAP: [ [ 1, 11 ], [ 2, 17 ], [ 3, 19 ], [ 4, 22 ], [ 5, 13 ], [ 6, 8 ], [ 7, 24 ], [ 9, 18 ], [ 10, 21 ], [ 12, 15 ], [ 14, 20 ], [ 16, 23 ] ]
julia> blockhom2 = GAP.Globals.ActionHomomorphism(cube2, edges, GAP.Globals.OnSets);
julia> cube2b = GAP.Globals.Image(blockhom2); GAP.Globals.Size(cube2b)
479001600
julia> ker2 = GAP.Globals.Kernel(blockhom2)
GAP: <permutation group with 11 generators>
julia> GAP.Globals.Factors(GAP.Globals.Size(ker2))
GAP: [ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 ]
julia> GAP.Globals.IsElementaryAbelian(ker2)
true
julia> cmpl2 = GAP.Globals.ComplementClassesRepresentatives(cube2, ker2); length(cmpl2)
4So there are even 4 classes of complements here. This time we get a semidirect product of a $2^11$ with an Sym(12), namely a subgroup of index 2 of the wreath product of a cyclic 2 with Sym(12). Here the missing index 2 tells us again that we do not have total freedom in turning the edges. The following tests show that whenever we flip one edge we must also flip another edge.
julia> @gap("(1, 11)") in cube2
false
julia> @gap("(1, 11)(2, 17)") in cube2
trueSince cube1 and cube2 are the groups describing the actions on the two orbits of cube, it is clear that cube is a subdirect product of those groups, i.e., a subgroup of the direct product. Comparing the sizes of cube1, cube2, and cube we see that cube must be a subgroup of index 2 in the direct product of those two groups.
julia> BigInt(GAP.Globals.Size(cube1)) * BigInt(GAP.Globals.Size(cube2))
86504006548979712000
julia> GAP.Globals.Size(cube)
GAP: 43252003274489856000(Note that both GAP.Globals.Size(cube1) and GAP.Globals.Size(cube2) have the Julia type Int64, and forming their product yields an overflow. In order to obtain the correct value we have created arbitrary precision integers for the two values before multiplying them.)
This final missing index 2 tells us that we cannot operate on corners and edges totally independently. The following tests show that whenever we exchange a pair of corners we must also exchange a pair of edges (and vice versa).
julia> @gap("(17, 19)(11, 8)(6, 25)") in cube
false
julia> @gap("(7, 28)(18, 21)") in cube
false
julia> @gap("(17, 19)(11, 8)(6, 25)(7, 28)(18, 21)") in cube
trueAs a last part of the structure analysis of the cube group let us compute the centre of the cube group, i.e., the subgroup of those operations that can be performed either before or after any other operation with the same result.
julia> z = GAP.Globals.Centre(cube)
GAP: Group([ (2,34)(4,10)(5,26)(7,18)(12,37)(13,20)(15,44)(21,28)(23,42)(29,36)(31,45)(39,47) ])We see that the centre contains one nontrivial element, namely the operation that flips all 12 edges simultaneously.
Finally we turn to the original idea connected with the cube, namely to find a sequence of turns of the faces that will transform the cube back into its original state. This amounts to a decomposition of a given element of the cube group into a product of the generators. For this purpose we introduce a free group and a homomorphism of it onto the cube group.
julia> f = GAP.Globals.FreeGroup(GapObj(["t", "l", "f", "r", "e", "b"], recursive = true))
GAP: <free group on the generators [ t, l, f, r, e, b ]>
julia> fhom = GAP.Globals.GroupHomomorphismByImages(f, cube)
GAP: [ t, l, f, r, e, b ] -> [ (1,3,8,6)(2,5,7,4)(9,33,25,17)(10,34,26,18)(11,35,27,19), (1,17,41,40)(4,20,44,37)(6,22,46,35)(9,11,16,14)(10,13,15,12), (6,25,43,16)(7,28,42,13)(8,30,41,11)(17,19,24,22)(18,21,23,20), (3,38,43,19)(5,36,45,21)(8,33,48,24)(25,27,32,30)(26,29,31,28), (1,14,48,27)(2,12,47,29)(3,9,46,32)(33,35,40,38)(34,37,39,36), (14,22,30,38)(15,23,31,39)(16,24,32,40)(41,43,48,46)(42,45,47,44) ]Using this homomorphism, we can now decompose elements into generators. The method used utilizes a stabilizer chain and does not enumerate all group elements, therefore the words obtained are not the shortest possible, though they are short enough for hand solutions.
The computed decompositions may be different in different sessions, because they involve the computation of pseudo random elements. Therefore the results shown in the following may look different in actual Julia sessions.
First we decompose the nonidentity centre element:
julia> zgen = GAP.Globals.GeneratorsOfGroup(z)[1]
GAP: (2,34)(4,10)(5,26)(7,18)(12,37)(13,20)(15,44)(21,28)(23,42)(29,36)(31,45)(39,47)
julia> pre1 = GAP.Globals.PreImagesRepresentative(fhom, zgen)
GAP: t^-1*l*t*l^-1*e^-1*t*f^-1*e*l*f*(t^-1*l^-1)^2*t*l*f*t*r*t^-1*r^-1*f^-1*l^-1*e^-1*t^-1*e*t*l*t*f*t*r*t^-1*r^-1*f^-1*t^-2*f*t^-1*f^-1*t^2*e*l^-1*e^-1*t^-1*l*t*l*f*t^-1*f^-1*l^-1*t*l*t^2*l^-1*t^-1*l*t^-1*l^-1*t^2*f^-1*l^-1*t^-1*l*t*f*t*l^-1*t*l*f^-1*l*f*l^-1*t^-2*l^-1*f^-1*l*f*l*t*e^-1*t*e*l*t*l^-1*e*l*e^-1*t^-1*f*l*f*l^-1*f^-1*t^-2*f^-1*t*l^-1*f*t^-2*f^-2*b*r^-1*b^-1*t^-2*e^-1*r^-2*e*t^-1*r*b*e^-1*b^-1*l^-1*r^-2*t^-2*l^-1*b^-1*r^-1*e^-1
julia> length(pre1)
134Next we decompose some element arbitrarily chosen by us:
julia> pre2 = GAP.Globals.PreImagesRepresentative(fhom, @gap("(17, 19)(11, 8)(6, 25)(7, 28)(18, 21)"))
GAP: l^-1*t^-1*l*f*r*t*r^-1*f^-1*l*t*f*t^-1*f^-1*l^-1*t^2*f*t*l*t*l^-1*f^-1*l*t^-1*l^-1*f*t^-1*f^-1*l*t*l^-1*t*l*t^-2*l^-1*f*(t*r*t^-1*r^-1)^2*f^-1*t*l*f^-1*l^-1*f*l^-1*t^-1*l*t^-2*f*t*(f^-1*l^-1)^2*l^-1*f*l*e^-1*t*e*l*t^-1*e^-1*t^-1*e*l*b*f^-1*b^-1
julia> length(pre2)
77Last we let GAP choose a random element ...
julia> r = GAP.Globals.Random(cube)
GAP: (1,6,9,17,35,11)(2,13,29,42,4,34,20,36,23,10)(3,22,14,8,38,24,27,16,40,19,32,43,33,41,46,25,48,30)(5,39,28,37,18,31,44,26,47,21,12,7,45,15)
julia> pre3 = GAP.Globals.PreImagesRepresentative(fhom, r)
GAP: r*e^-1*t^-1*e^-1*r^-2*e*f*t^2*b^-1*e^-1*b*l*f^-1*r*t^-1*r^-1*l*b*f^-2*b^-1*f^-1*l*f*t^-1*l^-1*f^-1*l^-1*f*e*l^-1*e^-1*l^-2*t^-1*l*f^-1*l^-1*f*l^-1*t^-1*l^2*f*t*f^-1*(t^-1*l^-1)^3*e*l*e^-1*t*l*t^-1*l*t^2*l^-1*t^-1*l*t^-1*l^-1*f*t*f^-1*l*t*l^-1*f*l*t^-1*l^-1*t^-1*f^-1*t^-1*f*r*t*r^-1*t^-1*f^-1*t^-1*l^-1*t^-1*e^-1*t*e*l*f*r*t*r^-1*t^-1*f^-1*l^-1*t^-1*(l*t)^2*f^-1*l^-1*e^-1*f*t^-1*e*l*t^-1*l^-1*t
julia> length(pre3)
116... and we verify that the decomposition is correct:
julia> GAP.Globals.Image(fhom, pre3) == r
trueThis concludes our example.