GAP/Sage canNOT solve Rubik's cube 444 ?
Dear colleagues, As far as I understand GAP/Sage cannot solve Rubik's cube 444 (and higher) i.e. to decompose a random element into product of generators. The group size is around 10ˆ45. ( I mean using algorithms not specific to Rubik's cube, of course, solving Rubik's cube per se is easy. I mean using it as a benchmark for algorithms which can work for any group - like Schreier–Sims algorithm).
Question: Is that correct or there are some ways to make it work ?
Here are some experiments:
1 Here is experiment with GAP (installing it in cloud, solving 333 cube - okay, 444 - crashes 330(!) Gigabytes RAM of Kaggle cloud TPU machine): https://www.kaggle.com/code/alexandervc/group-theory-via-gap-part-1 (https://www.kaggle.com/code/alexander...)
2 Here is a code one can try in SageCell or Co-Calc :
p0 = Permutation( [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 80, 76, 72, 68, 29, 25, 21, 17, 30, 26, 22, 18, 31, 27, 23, 19, 32, 28, 24, 20, 13, 34, 35, 36, 14, 38, 39, 40, 15, 42, 43, 44, 16, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 81, 69, 70, 71, 82, 73, 74, 75, 83, 77, 78, 79, 84, 45, 41, 37, 33, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96] );
p1 = Permutation( [1, 2, 3, 4, 5, 6, 7, 8, 79, 75, 71, 67, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 9, 35, 36, 37, 10, 39, 40, 41, 11, 43, 44, 45, 12, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 85, 68, 69, 70, 86, 72, 73, 74, 87, 76, 77, 78, 88, 80, 81, 82, 83, 84, 46, 42, 38, 34, 89, 90, 91, 92, 93, 94, 95, 96] );
p2 = Permutation( [1, 2, 3, 4, 78, 74, 70, 66, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 5, 36, 37, 38, 6, 40, 41, 42, 7, 44, 45, 46, 8, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 89, 67, 68, 69, 90, 71, 72, 73, 91, 75, 76, 77, 92, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 47, 43, 39, 35, 93, 94, 95, 96] );
p3 = Permutation( [77, 73, 69, 65, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 1, 37, 38, 39, 2, 41, 42, 43, 3, 45, 46, 47, 4, 52, 56, 60, 64, 51, 55, 59, 63, 50, 54, 58, 62, 49, 53, 57, 61, 93, 66, 67, 68, 94, 70, 71, 72, 95, 74, 75, 76, 96, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 48, 44, 40, 36] );
p4 = Permutation( [1, 2, 3, 20, 5, 6, 7, 24, 9, 10, 11, 28, 13, 14, 15, 32, 17, 18, 19, 84, 21, 22, 23, 88, 25, 26, 27, 92, 29, 30, 31, 96, 45, 41, 37, 33, 46, 42, 38, 34, 47, 43, 39, 35, 48, 44, 40, 36, 16, 50, 51, 52, 12, 54, 55, 56, 8, 58, 59, 60, 4, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 61, 85, 86, 87, 57, 89, 90, 91, 53, 93, 94, 95, 49] );
p5 = Permutation( [1, 2, 19, 4, 5, 6, 23, 8, 9, 10, 27, 12, 13, 14, 31, 16, 17, 18, 83, 20, 21, 22, 87, 24, 25, 26, 91, 28, 29, 30, 95, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 15, 51, 52, 53, 11, 55, 56, 57, 7, 59, 60, 61, 3, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 62, 84, 85, 86, 58, 88, 89, 90, 54, 92, 93, 94, 50, 96] );
p6 = Permutation( [1, 18, 3, 4, 5, 22, 7, 8, 9, 26, 11, 12, 13, 30, 15, 16, 17, 82, 19, 20, 21, 86, 23, 24, 25, 90, 27, 28, 29, 94, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 14, 52, 53, 54, 10, 56, 57, 58, 6, 60, 61, 62, 2, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 63, 83, 84, 85, 59, 87, 88, 89, 55, 91, 92, 93, 51, 95, 96] );
p7 = Permutation( [17, 2, 3, 4, 21, 6, 7, 8, 25, 10, 11, 12, 29, 14, 15, 16, 81, 18, 19, 20, 85, 22, 23, 24, 89, 26, 27, 28, 93, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 13, 53, 54, 55, 9, 57, 58, 59, 5, 61, 62, 63, 1, 68, 72, 76, 80, 67, 71, 75, 79, 66, 70, 74, 78, 65, 69, 73, 77, 64, 82, 83, 84, 60, 86, 87, 88, 56, 90, 91, 92, 52, 94, 95, 96] );
p8 = Permutation( [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 77, 78, 79, 80, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 29, 30, 31, 32, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 45, 46, 47, 48, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 61, 62, 63, 64, 93, 89, 85, 81, 94, 90, 86, 82, 95, 91, 87, 83, 96, 92, 88, 84] );
p9 = Permutation( [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 73, 74, 75, 76, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 25, 26, 27, 28, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 41, 42, 43, 44, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 57, 58, 59, 60, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96] );
p10 = Permutation( [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 69, 70, 71, 72, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 21, 22, 23, 24, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 37, 38, 39, 40, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 53, 54, 55, 56, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96] );
p11 = Permutation( [4, 8, 12, 16, 3, 7, 11, 15, 2, 6, 10, 14, 1, 5, 9, 13, 65, 66, 67, 68, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 17, 18, 19, 20, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 33, 34, 35, 36, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 49, 50, 51, 52, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96] );
p12 = Permutation( [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 33, 37, 41, 45, 20, 24, 28, 32, 19, 23, 27, 31, 18, 22, 26, 30, 17, 21, 25, 29, 84, 34, 35, 36, 83, 38, 39, 40, 82, 42, 43, 44, 81, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 16, 69, 70, 71, 15, 73, 74, 75, 14, 77, 78, 79, 13, 68, 72, 76, 80, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96] );
p13 = Permutation( [1, 2, 3, 4, 5, 6, 7, 8, 34, 38, 42, 46, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 88, 35, 36, 37, 87, 39, 40, 41, 86, 43, 44, 45, 85, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 12, 68, 69, 70, 11, 72, 73, 74, 10, 76, 77, 78, 9, 80, 81, 82, 83, 84, 67, 71, 75, 79, 89, 90, 91, 92, 93, 94, 95, 96] );
p14 = Permutation( [1, 2, 3, 4, 35, 39, 43, 47, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 92, 36, 37, 38, 91, 40, 41, 42, 90, 44, 45, 46, 89, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 8, 67, 68, 69, 7, 71, 72, 73, 6, 75, 76, 77, 5, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 66, 70, 74, 78, 93, 94, 95, 96] );
p15 = Permutation( [36, 40, 44, 48, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 96, 37, 38, 39, 95, 41, 42, 43, 94, 45, 46, 47, 93, 61, 57, 53, 49, 62, 58, 54, 50, 63, 59, 55, 51, 64, 60, 56, 52, 4, 66, 67, 68, 3, 70, 71, 72, 2, 74, 75, 76, 1, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 65, 69, 73, 77] );
p16 = Permutation( [1, 2, 3, 61, 5, 6, 7, 57, 9, 10, 11, 53, 13, 14, 15, 49, 17, 18, 19, 4, 21, 22, 23, 8, 25, 26, 27, 12, 29, 30, 31, 16, 36, 40, 44, 48, 35, 39, 43, 47, 34, 38, 42, 46, 33, 37, 41, 45, 96, 50, 51, 52, 92, 54, 55, 56, 88, 58, 59, 60, 84, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 20, 85, 86, 87, 24, 89, 90, 91, 28, 93, 94, 95, 32] );
p17 = Permutation( [1, 2, 62, 4, 5, 6, 58, 8, 9, 10, 54, 12, 13, 14, 50, 16, 17, 18, 3, 20, 21, 22, 7, 24, 25, 26, 11, 28, 29, 30, 15, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 95, 51, 52, 53, 91, 55, 56, 57, 87, 59, 60, 61, 83, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 19, 84, 85, 86, 23, 88, 89, 90, 27, 92, 93, 94, 31, 96] );
p18 = Permutation( [1, 63, 3, 4, 5, 59, 7, 8, 9, 55, 11, 12, 13, 51, 15, 16, 17, 2, 19, 20, 21, 6, 23, 24, 25, 10, 27, 28, 29, 14, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 94, 52, 53, 54, 90, 56, 57, 58, 86, 60, 61, 62, 82, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 18, 83, 84, 85, 22, 87, 88, 89, 26, 91, 92, 93, 30, 95, 96] );
p19 = Permutation( [64, 2, 3, 4, 60, 6, 7, 8, 56, 10, 11, 12, 52, 14, 15, 16, 1, 18, 19, 20, 5, 22, 23, 24, 9, 26, 27, 28, 13, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 93, 53, 54, 55, 89, 57, 58, 59, 85, 61, 62, 63, 81, 77, 73, 69, 65, 78, 74, 70, 66, 79, 75, 71, 67, 80, 76, 72, 68, 17, 82, 83, 84, 21, 86, 87, 88, 25, 90, 91, 92, 29, 94, 95, 96] );
p20 = Permutation( [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 45, 46, 47, 48, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 61, 62, 63, 64, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 77, 78, 79, 80, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 29, 30, 31, 32, 84, 88, 92, 96, 83, 87, 91, 95, 82, 86, 90, 94, 81, 85, 89, 93] );
p21 = Permutation( [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 41, 42, 43, 44, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 57, 58, 59, 60, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 73, 74, 75, 76, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 25, 26, 27, 28, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96] );
p22 = Permutation( [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 37, 38, 39, 40, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 53, 54, 55, 56, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 69, 70, 71, 72, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 21, 22, 23, 24, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96] );
p23 = Permutation( [13, 9, 5, 1, 14, 10, 6, 2, 15, 11, 7, 3, 16, 12, 8, 4, 33, 34, 35, 36, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 49, 50, 51, 52, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 65, 66, 67, 68, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 17, 18, 19, 20, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96] );
G = PermutationGroup([p0,p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11,p12,p13,p14,p15,p16,p17,p18,p19,p20,p21,p22,p23 ])
print('G defined')
G
g = G.an_element() ;
for i in range(1, 1000):
g = g * G.random_element() ;
print('Element to decompose:', g)
print('Start')
t = g.word_problem(G.gens());
print('End')
t
add a comment
