Nearly Linear Time Isomorphism Algorithms for Some Nonabelian Group Classes

• Published in: Theory of computing systems 2021-04, Vol.65 (3), p.497-514
• Main Authors: Das, Bireswar, Sharma, Shivdutt
• Format: Article
• Language: English
• Subjects: Algorithms; Computation; Computer Science; Group theory; Isomorphism; Quotients; Special Issue on Computer Science Symposium in Russia; Theory of Computation
• ISSN: 1432-4350; 1433-0490
• DOI: 10.1007/s00224-020-10010-z

The isomorphism problem for groups, when the groups are given by their Cayley tables is a well-studied problem. This problem has been studied for various restricted classes of groups. Kavitha gave a linear time isomorphism algorithm for abelian groups (JCSS 2007). Although there are isomorphism algorithms for certain nonabelian group classes represented by their Cayley tables, the complexities of those algorithms are usually super-linear. In this paper, we design linear and nearly linear time isomorphism algorithms for some nonabelian groups. More precisely, We design a linear-time algorithm to factor Hamiltonian groups. This allows us to obtain an O ( n ) algorithm for the isomorphism problem of Hamiltonian groups, where n is the order of the groups. We design a nearly linear time algorithm to find a maximal abelian direct factor of an input group. As a byproduct we obtain an O ~ ( n ) isomorphism for groups that can be decomposed as a direct product of a nonabelian group of bounded order and an abelian group, where n is the order of the groups. We observe that testing normality, computing the center of a group, finding a logarithmic sized generating set, computing quotient groups for groups given by their Cayley table could be done in linear or nearly linear time.