An algorithm for solving the factorization problem in permutation groups (Q1264436): Difference between revisions

A stabilizer chain [\textit{C. Sims}, Comput. Probl. abstract Algebra, Proc. Conf. Oxford 1967, 169-183 (1970; Zbl 0215.10002)] can be used to express elements of a permutation group as words in (given) generators. The words obtained this way however can be very long. To overcome this problem, the author proposes to compute the transversal elements of the stabilizer chain not (as usually done) by an orbit algorithm, but by systematically computing short words in the generators until elements for all transversal positions have been found. This yields a larger strong generating set (SGS) whose elements however are short words in the generators. Thus the standard factorization algorithm using this SGS tends to produce shorter words. Such short words can be useful for practical purposes (like the evaluation of homomorphisms [\textit{C. R. Leedham-Green, C. E. Praeger} and \textit{L. H. Soicher}, J. Symb. Comput. 12, No. 4/5, 527-532 (1991; Zbl 0789.20001)]) even though they are not the shortest possible. The author gives explicit algorithms and lists performance times and word lengths for a couple of examples, using his implementation in the computer algebra system GAP. He notes that the main problem of the algorithm is a situation when long words are needed for some transversal positions as happens for \(S_n=\langle(1,2),(2,3),(3,4),\ldots,(n-1,n)\rangle\).