›› 2012, Vol. 27 ›› Issue (4): 687-701.doi: 10.1007/s11390-012-1255-7

• Special Section on Theoretical Computer Science • Previous Articles     Next Articles

On Isomorphism Testing of Groups with Normal Hall Subgroups

You-Ming Qiao1 (乔友明), Jayalal Sarma M.N.2, and Bang-Sheng Tang1 (唐邦晟)   

  1. 1. Institute for Theoretical Computer Science, Tsinghua University, Beijing 100084, China;
    2. Department of Computer Science and Engineering, Indian Institute of Technology Madras, Chennai 600036, India
  • Received:2011-03-13 Revised:2012-02-29 Online:2012-07-05 Published:2012-07-05
  • Supported by:

    The work was supported in part by the National Natural Science Foundation of China under Grant No. 60553001, and the National Basic Research 973 Program of China under Grant Nos. 2007CB807900 and 2007CB807901.

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, which asks whether two linear subspaces are the same up to permutation of coordinates. 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 et al. (SODA 2011). Enroute to obtaining the above reduction, we study the following computational problem in representation theory of finite groups: given two representations ρ and τ of a group H over Zpd, p a prime, determine if there exists an automorphism Φ:HH, such that the induced representation ρΦ=ρ ο Φ and τ are equivalent, in time poly(|H|, pd).

[1] Dehn M. Über unendliche diskontinuierliche gruppen. MathematischeAnnalen, 1911, 71: 116-144.

[2] Adian S. The unsolvability of certain algorithmic problems inthe theory of groups. Trudy Moskov. Math. Obshch, 1957, 6:231-298.

[3] Babai L, Szemerèdi E. On the complexity of matrix groupproblems i. In Proc. IEEE Annual Symposium on Foundationsof Computer Science (FOCS), West Palm Beach,Florida, USA, October 24-26, 1984, pp.229-240.

[4] Köbler J, Schöning U, Torán J. The Graph Isomorphism Problem:Its Structural Complexity. Boston: Birkhauser, 1993.

[5] Chattopadhyay A, Torán J, Wagner F. Graph isomorphism isnot AC0 reducible to group isomorphism. In Proc. AnnualConference on Foundations of Software Technology and TheoreticalComputer Science (FSTTCS 2010), Chennai, India,Dec. 15-18, 2010, pp.317-326.

[6] Babai L, Luks E M. Canonical labeling of graphs. In Proc.the 15th Annual ACM Symposium on Theory of Computing(STOC), Boston, Massachusetts, USA, April 25-27, 1983,pp.171-183.

[7] Miller G L. On the nlogn isomorphism technique. In Proc.the 10th Annual ACM Symposium on Theory of Computing,San Diego, California, USA, May 1-3, 1978, pp.51-58.

[8] Lipton R J, Snyder L, Zalcstein Y. The complexity of wordand isomorphism problems for finite groups. Technical Report,John Hopkins, 1976.

[9] Savage C. An O(n2) algorithm for abelian group isomorphism.Technical Report, North Carolina State University, 1980.

[10] Vikas N. An O(n) algorithm for abelian p-group isomorphismand an O(n log n) algorithm for abelian group isomorphism.Journal of Computer and System Sciences, 1996, 53(1): 1-9.

[11] Kavitha T. Linear time algorithms for abelian group isomorphismand related problems. Journal of Computer and SystemSciences, 2007, 73(6): 986-996.

[12] Gall F L. Efficient isomorphism testing for a class of groupextensions. In Proc. the 26th International Symposiumon Theoretical Aspects of Computer Science (STACS 2009),Freiburg, Germany, February 26-28, 2009, pp.625-636.

[13] Wilson J B. Decomposing p-groups via Jordan algebras. Journalof Algebra, 2009, 322(8): 2642-2679.

[14] Wilson J B. Finding central decompositions of p-groups.Journal of Group Theory, 2009, 12(6): 813-830.

[15] Kayal N, Nezhmetdinov T. Factoring groups efficiently. InProc. the 36th International Colloquium on Automata, Languagesand Programming (ICALP 2009), Rhodes, Greece,July 5-12, 2009, pp.585-596.

[16] Wilson J B. Finding direct product decompositions in polynomialtime. 2010. http://arxiv.org/pdf/1005.0548.pdf.

[17] Taunt D R. Remarks on the isomorphism problem in theoriesof construction of finite groups. Mathematical Proceedings ofthe Cambridge Philosophical Society, 1955, 51(1): 16-24.

[18] Menegazzo F. The number of generators of a finite group.Irish Math. Soc. Bulletin, 2003, 50: 117-128.

[19] Babai L. Equivalence of linear codes. Technical Report, Universityof Chicago, 2010.

[20] Babai L, Codenotti P, Grochow J, Qiao Y. Towards efficientalgorithm for semisimple group isomorphism. In Proc. ACMSIAMAnnual Symposium of Discrete Algorithms (SODA),San Francisco, California, USA, January 23-25, 2011.

[21] Holt D F, Eick B, O’Brien E A. Handbook of ComputationalGroup Theory. London: Chapman and Hall/CRC, 2005.

[22] Rotman J J. An Introduction to the Theory of Groups (4thedition). Springer-Verlag, 1995.

[23] Serre J P. Linear Representations of Finite Groups. NewYork: Springer-Verlag, 1977.

[24] R′onyai L. Computing the structure of finite algebras. Journalof Symbolic Computation, 1990, 9(3): 355-373.

[25] Shoup V. On the deterministic complexity of factoring polynomialsover finite fields. Information Processing Letters,1990, 33(5): 261-267.

[26] Steel A. A new algorithm for the computation of canonicalforms of matrices over fields. Journal of Symbolic Computation,1997, 24(3-4): 409-432.

[27] Seress A. Permutation Group Algorithms. Cambridge: CambridgeUniversity Press, 2003.

[28] Babai L. Coset intersection in moderately exponential time.Chicago Journal of Theoretical Computer Science, to appear.

[29] Luks E M. Hypergraph isomorphism and structural equivalenceof Boolean functions. In Proc. the 31st Annual ACMSymposium on Theory of Computing, Atlanta, Georgia, USA,May 1-4, 1999, pp.652-658.

[30] Kantor W M, Luks E M, Mark P D. Sylow subgroups in parallel.Journal of Algorithms, 1999, 31(1): 132-195.

[31] Babai L, Qiao Y. Polynomial-time isomorphism test forgroups with abelian Sylow towers. In Proc. the 29th InternationalSymposium on Theoretical Aspects of ComputerScience, Pairs, France, Feb. 28-March 3, 2012, pp.453-464.

[32] Petrank E, Roth R M. Is code equivalence easy to decide?IEEE Trans. Information Theory, 1997, 43(5): 1602-1604.

[33] Buchmann J, Schmidt A. Computing the structure of a finiteabelian group. Mathematics of Computation, 2005, 74(252):2017-2026.

[34] Ranum A. The group of classes of congruent matrices with applicationto the group of isomorphisms of any abelian group.Transactions of the American Mathematical Society, 1907,8(1): 71-91.
No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhang Bo; Zhang Ling;. Statistical Heuristic Search[J]. , 1987, 2(1): 1 -11 .
[10] Sun Yongqiang; Lu Ruzhan; Huang Xiaorong;. Termination Preserving Problem in the Transformation of Applicative Programs[J]. , 1987, 2(3): 191 -201 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved