×

zbMATH — the first resource for mathematics

On complexity of multiplication in finite soluble groups. (English) Zbl 1315.20012
Summary: We determine a reasonable upper bound for the complexity of collection from the left to multiply two elements of a finite soluble group by restricting attention to certain polycyclic presentations of the group. As a corollary we give an upper bound for the complexity of collection from the left in finite \(p\)-groups in terms of the group order.

MSC:
20D10 Finite solvable groups, theory of formations, Schunck classes, Fitting classes, \(\pi\)-length, ranks
68Q25 Analysis of algorithms and problem complexity
20F05 Generators, relations, and presentations of groups
68W30 Symbolic computation and algebraic computation
Software:
Magma; GAP
PDF BibTeX Cite
Full Text: DOI arXiv
References:
[1] Bosma, W.; Cannon, J.; Playoust, C., The {\scmagma} algebra system. I. the user language, J. Symbolic Comput., 24, 3-4, 235-265, (1997) · Zbl 0898.68039
[2] Cannon, J. J.; Eick, B.; Leedham-Green, C. R., Special polycyclic generating sequences for finite soluble groups, J. Symbolic Comput., 38, 5, 1445-1460, (2004) · Zbl 1125.20304
[3] GAP — groups, algorithms, and programming, version 4.7.5, (2014)
[4] Gebhardt, V., Efficient collection in infinite polycyclic groups, J. Symbolic Comput., 34, 3, 213-228, (2002) · Zbl 1043.20018
[5] Höfling, B., Efficient multiplication algorithms for finite polycyclic groups, (2004), Braunschweig
[6] Leedham-Green, C. R.; Soicher, L. H., Collection from the left and other strategies, Computational Group Theory, Part 1, J. Symbolic Comput., 9, 5-6, 665-675, (1990) · Zbl 0726.20001
[7] Sims, C. C., Computation with finitely presented groups, Encyclopedia Math. Appl., Vol. 48, (1994), Cambridge University Press Cambridge · Zbl 0828.20001
[8] Vaughan-Lee, M. R., Collection from the left, Computational Group Theory, Part 1, J. Symbolic Comput., 9, 5-6, 725-733, (1990) · Zbl 0705.20017
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.