Beating the generator-enumeration bound for p-group isomorphism

We consider the group isomorphism problem: given two finite groups G and H specified by their multiplication tables, decide if G ? H . For several decades, the n log p ? 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 ) log p ? 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 ) and applying algorithms for testing isomorphism of graphs of bounded degree, we obtain an n O ( 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 ) log p ? 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 ? n for p-group isomorphism. n 1 2 log p ? n + O ( 1 ) time reduction from p-group isomorphism to composition-series isomorphism n O ( p ) time algorithm for p-group composition-series isomorphism n 1 2 log ? n + O ( 1 ) time algorithm for p-group isomorphismThis is the first improvement over the generator-enumeration algorithm for the class of p-groups