Seminar: February 22

YouMing Qiao, Tsinghua University

On isomorphism testing of groups with normal Hall subgroups

Group isomorphism problem, when groups are represented as multiplication tables, asks for an efficient algorithm to test if two given groups are isomorphic or not. Though an n^{logn + O(1)} algorithm has been known for decades, whether a polynomial algorithm exists is still elusive. To make progress towards the general case, people have been considering restricted group classes. Abelian groups has been understood well while making further progress seems difficult. In 2008, Le Gall presented efficient isomorphism testing for groups in the form of semidirect product of abelian group by cyclic group, where two components are coprime.

With Jayalal Sarma and Bangsheng Tang, we extend Le Gall's work to a much more general framework, to test isomorphism of groups with at least one normal Hall subgroup (a normal subgroup whose order is coprime with its index). The most notable feature of this framework is to give a connection between group isomorphism problem and group representation theory. In fact, it turns out that the following computational problem in group representation theory lies in the core of testing isomorphism of such groups:

Given two representations \rho and \tau of a group H over Z^d_p, p a prime, determine if there exists an automorphism \phi : H \to H, such that the induced representation \rho\phi = \rho\circ\phi and \tau are equivalent, in time poly(|H|, p^d).

We solve the above problem when H is elementary abelian (that is, a vector space over finite field), by reducing to code equivalence problem, which asks if two linear codes are the same up to permutation of coordinates. Utilizing a singly exponential algorithm by Babai, we can efficiently test isomorphism of groups in the form of semidirect product of abelian group by elementary abelian group, whose orders are coprime. As far as we know, this is the first group class with n^{Omega(log n)} non-isomorphic groups in it, whose isomorphism can be tested efficiently.