< ^ From:

> < ^ Subject:

Dear Bob, dear GAP-Forum,

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 wrote some special purpose

software to solve 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 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

> < [top]