Dear GAP-Forum, dear Bob,
Recently I saw a post at rec.puzzles regarding a permutation puzzle, which
the poster had done some analysis using magma. I wanted to do the same sort
of analysis with GAP.
My colleague Markus Pueschel (now at CMU) and me have written some special purpose
software to tackle exactly this type of puzzles. I just ran it and found a word with 33 letters
that represents the permutation (15,16) in the group you gave, generated by the generators
you gave. Here is what I typed:
# Posting by Bob on a Permutation-based Puzzle,
# Sebastian.Egner@philips.com, 19-Sept-2000,
# GAP v3.4.4 using "abstabch.g" by S. Egner and M. Pueschel.
# We define the permutation group.. G := Group( (1,2,3,7,11,10,9,5), (2,3,4,8,12,11,10,6), (5,6,7,11,15,14,13,9), (6,7,8,12,16,15,14,10) );
# ..and store some abstract generators into it.
G.abstractGenerators :=
List(["a", "b", "c", "d"], AbstractGenerator);
# Then we compute an abstract stabilizer chain (takes 30 min on my SGI-Indy)..
#
# gap> Read("abstabch.g");
# gap> AbstractStabChainGenerationOneStrategy(G, 1000, [ ]);
#
# level basepoint cosets (orbit size) (max. length) (avg. length)
# 1 16 16 16+ 6 3.0
# 2 14 15 15+ 5 2.8
# 3 15 14 14+ 5 3.7
# 4 13 13 13+ 6 4.0
# 5 8 12 12+ 5 2.6
# 6 4 11 11+ 5 3.8
# 7 6 10 10+ 5 3.7
# 8 12 9 9+ 8 5.5
# 9 1 8 8+ 4 2.0
# 10 2 7 7+ 10 8.5
# 11 5 6 6+ 12 8.6
# 12 11 5 5+ 14 8.4
# 13 10 4 4+ 19 12.7
# 14 9 3 3+ 22 14.6
# 15 7 2 2+ 21 10.5
#
# total: 135 135* 147 95.0
# (orbits: + = complete, * = generating set known)
#
# ..and use it to factor the permutation at hand (takes 2 s):
#
# gap> w := trembleFactorPerm(G, 100, (15,16));
#
# d^-1*b*c^2*a^-1*c^-1*d^-1*a^-1*d*a*b^-1*a^-2*c^-1*d^-1*c*d*
# c^-1*a*d^-1*c^-1*d*a^-1*d*a^-1*d^-1*a^2*d*a^-1*d^-1*a*b
#
# (This word consists of 33 letters or inverse letters.)
#
# Let's check if w is does represent (15,16):
#
# gap> MappedWord(w, G.abstractGenerators, G.generators);
#
# (15,16)
So this refutes Andrew's conjecture ;-) that you need 796257 letters.
If you want to know how the program works in detail (it is
a relatively complex, substantially heuristic method)
you can read the following article. The program itself is
not really fit for publication and it has been implemented
for the older version GAP3 and is not available for the
new version GAP4.
S. Egner, M. Pueschel:
Solving Puzzles related to Permutation Groups.
Proc. of the Int'l Symposium on Symbolic and Algebraic Computing
(ISSAC), Rostock (Germany), 1998.
Bye,
Sebastian.
----
Dr. Sebastian Egner
Philips Research Labs
Prof. Holstlaan 4 (building WY2)
5656 AA Eindhoven
The Netherlands
tel. +31 40 27-43309
fax +31 40 27-44911
email sebastian.egner@philips.com