License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2012.453
URN: urn:nbn:de:0030-drops-34008
URL: http://drops.dagstuhl.de/opus/volltexte/2012/3400/
Go to the corresponding Portal


Babai, László ; Qiao, Youming

Polynomial-time Isomorphism Test for Groups with Abelian Sylow Towers

pdf-format:
Document 1.pdf (606 KB)


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 polynomial-time 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 polynomial-time 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 p-groups. We use tools from the theory of permutation group algorithms, and develop an algorithm for a parameterized versin of the graph-isomorphism-hard 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 =	{{Polynomial-time Isomorphism Test for Groups with Abelian Sylow Towers}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{453--464},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{Christoph D{\"u}rr and Thomas Wilke},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2012/3400},
  URN =		{urn:nbn:de:0030-drops-34008},
  doi =		{http://dx.doi.org/10.4230/LIPIcs.STACS.2012.453},
  annote =	{Keywords: polynomial-time algorithm, group isomorphism, solvable group}
}

Keywords: polynomial-time algorithm, group isomorphism, solvable group
Seminar: 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
Issue Date: 2012
Date of publication: 24.02.2012


DROPS-Home | Fulltext Search | Imprint Published by LZI