Breaking Ground in Isomorphism Testing: A Leap Forward for a Bottleneck Case of Group Isomorphism

Guest post by Josh Grochow and Youming Qiao

There has, quietly, been somewhat of a breakthrough in isomorphism testing. No, not as big as Babai's 2016 Graph Isomorphism in Quasipolynomial Time. But a first foothold in climbing a wall for which no one had gotten much off the ground before. The result, due to Xiaorui Sun in this year's STOC, is an algorithm for testing isomorphism of a certain class of groups - p-groups of class 2 and exponent p if you must know, but we'll get to that - in time $n^{O({\log }^{5/6}n)}$ where n is the order of the group. To understand why we're excited about this we have to tell a bit of a story. 

In the 1970s, when Graph Isomorphism was still a mystery, people also thought more widely about isomorphism testing of other combinatorial and algebraic structures. For finite groups of order n, Robert Tarjan realized that there is an $n^{\log n+O(1)}$-time algorithm, simply because a group of order n has a generating set of size $\log n$. This observation was recorded by Gary Miller in a paper in STOC'78, and independently realized by Felsch and Neubüser. A natural question is then whether Group Isomorphism can be solved in time poly(n) where n is the group order.

Not only is this question natural from the perspective of studying groups computationally, it is also natural from the perspective of Graph Isomorphism. For Group Isomorphism reduces to Graph Isomorphism in polynomial-time (as does the isomorphism problem for any finite algebraic or relational structure, see Zemlyachenko, Korneenko, & Tyshkevich). While this has been known for a long time, Babai’s result on Graph Isomorphism brings the running times quite close: $n^{O({\log }^{2}n)}$ for graphs, and $n^{O(\log n)}$ for groups. So not only does Group Isomorphism stand in the way of getting Graph Isomorphism into P, but in our current state of knowledge, it even stands in the way of shaving off more than a single log in the exponent of the runtime.

Since the general Group Isomorphism problem seems difficult, attention turned to special classes of groups. It was not hard to see that isomorphism of Abelian groups could be computed in polynomial time. However, a group class that is just “one step away” from Abelian - groups G where, when you mod out by the center Z(G), what’s left is Abelian -  turned out to be difficult. Such groups are called class-2 nilpotent, and in one sense, their  group-theoretic structure is relatively straightforward: both G/Z(G) and Z(G) are Abelian. Yet, to devise an efficient isomorphism testing procedure turned out to be extremely difficult (see e.g. Garzon-Zalcstein, Rosenbaum-Wagner, O’Brien, Wilson), to the point that this is usually considered as a bottleneck for putting Group Isomorphism in P. 

Among class-2 nilpotent groups, the “key case” to resolve is widely believed, for several reasons, to be p-groups of class 2 and exponent p. In such groups, both the center Z(G) and quotient G/Z(G) are elementary abelian, i.e., of the form $(Z_p{)}^d$. Despite having an even simpler group-theoretic structure, this group class still turns out to be difficult! For a long time, the asymptotic growth of the exponent of the runtime for solving this restricted problem has not improved over the $n^{\log n+O(1)}$-time algorithm, which works for all groups.¹

Xiaorui Sun’s result represents the first substantial improvement, cracking open this decades-old quest. His algorithm runs in time $n^{O({\log }^{5/6}n)}$, and its techniques are indeed novel. The starting point of this algorithm is to consider the following equivalent problem in (multi)linear algebra: let $f,g:Z_p^d\times Z_p^d\to Z_p^e$ be two skew-symmetric bilinear maps. Do there exist change of bases A in $GL(d,p)$ and B in $GL(e,p)$, such that for all $u,v$ in $Z_p^d$, $f(A(u),A(v))=B(g(u,v))$?

Baer’s Correspondence sets up an equivalence of categories between p-groups of class 2 and exponent p, and skew-symmetric bilinear maps over $Z_p$. This viewpoint allows Xiaorui to use multilinear algebra to study the structure of these bilinear maps. He also crucially depends on a result of Ivanyos and Qiao, which built on Wilson’s use of involutive algebras in this context. He also uses the individualization-and-refinement technique (but for matrix spaces, not graphs!), a characterization of spaces of matrices of low rank, and reducing a tensor to a “semi-canonical” form part of which is somewhat reminiscent of the Tucker decomposition.

All this results in an algorithm which solves the above problem on bilinear maps in time $p^{(d+e{)}^{1.8}\log p}$. For groups of order $p^n$ with ${\log }_p(n)$ larger than ${\log }^{5}p$, Baer’s Correspondence then says that this algorithm does it; when ${\log }_{p}n$ is smaller than $lo{g}^{5}p,$ he can fall back on the generator-enumerator algorithm, since the number of generators is at most $lo{g}_{p}n$.

For us, who have been working on Group Isomorphism for more than a decade, Xiaorui’s result represents an exciting development on this classic algorithmic problem, and we look forward to seeing more progress in this direction in the near future. 

---

¹Rosenbaum & Wagner improved the exponent to $\frac{1}{2}\log p(n)+O(1)$, and later improved to $\frac{1}{4}\log p(n)+O(1)$ for all groups, see p.5 of Le Gall & Rosenbaum. In 2014, at a conference on Groups, Computation, and Geometry organized by Wilson, Brooksbank, Hulpke, Kantor, and Penttila, it was concluded that modern practical methods, such as those used in GAP and MAGMA, still take $n^{O(\log n)}$ steps in the worst case.