Babai, László ;
Qiao, Youming
Polynomialtime Isomorphism Test for Groups with Abelian Sylow Towers
Abstract
We consider the problem of testing isomorphism of groups of order n
given by Cayley tables. The trivial n^{log n} bound on the time
complexity for the general case has not been improved over the past
four decades. Recently, Babai et al. (following Babai et al. in SODA
2011) presented a polynomialtime algorithm for groups without abelian
normal subgroups, which suggests solvable groups as the hard case for
group isomorphism problem. Extending recent work by Le Gall (STACS
2009) and Qiao et al. (STACS 2011), in this paper we design a
polynomialtime algorithm to test isomorphism for the largest class of
solvable groups yet, namely groups with abelian Sylow towers, defined
as follows. A group G is said to possess a Sylow tower, if there
exists a normal series where each quotient is isomorphic to Sylow
subgroup of G. A group has an abelian Sylow tower if it has a Sylow
tower and all its Sylow subgroups are abelian. In fact, we are able
to compute the coset of isomorphisms of groups formed as coprime
extensions of an abelian group, by a group whose automorphism group is
known.
The mathematical tools required include representation theory,
Wedderburn's theorem on semisimple algebras, and M.E. Harris's 1980
work on p'automorphisms of abelian pgroups. We use tools from the
theory of permutation group algorithms, and develop an algorithm for a
parameterized versin of the graphisomorphismhard setwise stabilizer
problem, which may be of independent interest.
BibTeX  Entry
@InProceedings{babai_et_al:LIPIcs:2012:3400,
author = {L{\'a}szl{\'o} Babai and Youming Qiao},
title = {{Polynomialtime Isomorphism Test for Groups with Abelian Sylow Towers}},
booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
pages = {453464},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897354},
ISSN = {18688969},
year = {2012},
volume = {14},
editor = {Christoph D{\"u}rr and Thomas Wilke},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3400},
URN = {urn:nbn:de:0030drops34008},
doi = {10.4230/LIPIcs.STACS.2012.453},
annote = {Keywords: polynomialtime algorithm, group isomorphism, solvable group}
}
2012
Keywords: 

polynomialtime algorithm, group isomorphism, solvable group 
Seminar: 

29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Issue date: 

2012 
Date of publication: 

2012 