10.4230/LIPICS.STACS.2011.567
Qiao, Youming
Youming
Qiao
Sarma M.N., Jayalal
Jayalal
Sarma M.N.
Tang, Bangsheng
Bangsheng
Tang
On Isomorphism Testing of Groups with Normal Hall Subgroups
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2011
Article
Group Isomorphism Problem
Normal Hall Subgroups
Computational Complexity
Schwentick, Thomas
Thomas
Schwentick
Dürr, Christoph
Christoph
Dürr
2011
2011-03-11
2011-03-11
2011-03-11
en
urn:nbn:de:0030-drops-30443
10.4230/LIPIcs.STACS.2011
978-3-939897-25-5
1868-8969
10.4230/LIPIcs.STACS.2011
LIPIcs, Volume 9, STACS 2011
28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
2013
9
48
567
578
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Schwentick, Thomas
Thomas
Schwentick
Dürr, Christoph
Christoph
Dürr
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2011
9
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
12 pages
707760 bytes
application/pdf
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
A normal Hall subgroup $N$ of a group $G$ is a normal subgroup with its order coprime with its index. Schur-Zassenhaus theorem states that every normal Hall subgroup has a complement subgroup, that is a set of coset representatives H which also forms a subgroup of G. In this paper, we present a framework to test isomorphism of groups with at least one normal Hall subgroup, when groups are given as multiplication tables. To establish the framework, we first observe that a proof of Schur-Zassenhaus theorem is constructive, and formulate a necessary and sufficient condition for testing isomorphism in terms of the associated actions of the semidirect products, and isomorphisms of the normal parts and complement parts.
We then focus on the case when the normal subgroup is abelian. Utilizing basic facts of representation theory of finite groups and a technique by Le Gall [STACS 2009], we first get an efficient isomorphism testing algorithm when the complement has bounded number of generators. For the case when the complement subgroup is elementary abelian, which does not necessarily have bounded number of generators, we obtain a polynomial time isomorphism testing algorithm by reducing to generalized code isomorphism problem. A solution to the latter can be obtained by a mild extension of the singly exponential (in the number of coordinates) time algorithm for code isomorphism problem developed recently by Babai. Enroute to obtaining the above reduction, we study the following computational problem in representation theory of finite groups: given two representations rho and tau of a group $H$ over Z_p^d , p a prime, determine if there exists an automorphism phi:H -> H, such that the induced representation rho_phi=rho o phi and tau are equivalent, in time poly(|H|,p^d).
LIPIcs, Vol. 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011), pages 567-578