Beating the generator-enumeration bound for p-group isomorphism

•n12logp⁡n+O(1) time reduction from p-group isomorphism to composition-series isomorphism•nO(p)nO(p) time algorithm for p-group composition-series isomorphism•n12log⁡n+O(1) time algorithm for p-group isomorphism•This is the first improvement over the generator-enumeration algorithm for the class of p-groups

We consider the group isomorphism problem: given two finite groups G and H   specified by their multiplication tables, decide if G≅HG≅H. For several decades, the nlogp⁡n+O(1)nlogp⁡n+O(1) generator-enumeration bound (where p is the smallest prime dividing the order of the group) has been the best worst-case result for general groups. In this work, we show an improvement over the generator-enumeration bound for p  -groups, which are believed to be the hard case of the group isomorphism problem. We start by giving a Turing reduction from group isomorphism to n(1/2)logp⁡n+O(1)n(1/2)logp⁡n+O(1) instances of p-group composition-series isomorphism. By showing a Karp reduction from p  -group composition-series isomorphism to testing isomorphism of graphs of degree at most p+O(1)p+O(1) and applying algorithms for testing isomorphism of graphs of bounded degree, we obtain an nO(p)nO(p) time algorithm for p-group composition-series isomorphism. Combining these two results yields an algorithm for p  -group isomorphism that takes at most n(1/2)logp⁡n+O(p)n(1/2)logp⁡n+O(p) time. This algorithm is faster than generator-enumeration when p is small and slower when p is large. Choosing the faster algorithm based on p and n   yields an upper bound of n(1/2+o(1))log⁡nn(1/2+o(1))log⁡n for p-group isomorphism.