“In other words,” Sun said, “in order to further improve graph isomorphism, group isomorphism is a big bottleneck.”

A Problem Transformed

When progress on a problem stalls as long as it did for group isomorphism, invention is usually necessary to get unstuck. “When you have a big advance, that should be some indication that there’s a new idea,” Grochow said.

Sun’s work contains a few ideas that involve targeting an important type of group and finding a clever way to break those groups into pieces in order to compare them.

The groups Sun’s algorithm works for are called p-groups of class 2 and exponent p. They are similar to groups in which the product of two elements is another element and the product remains the same regardless of the order in which you multiply them. But what really matters is what they represent for the overall group isomorphism problem. These groups have a very simple structure, which means they should be easy to compare. But despite this simplicity, researchers hadn’t figured out a way to speed up the algorithm. Until they could, it felt hopeless to make improvements for the general question of group isomorphism.

Sun began by switching the setting from groups to matrices, arrays of numbers that serve as foundational objects in linear algebra. This was possible due to a theorem from the 1930s called the Baer correspondence, which transforms this version of the group isomorphism question into a perfectly analogous problem about matrices. In particular, Sun worked with matrix spaces, which are collections of matrices with a special property: The (linear) combination of any two matrices in the space equals another matrix in the space.

In other words, these spaces are structured a lot like groups. So instead of trying to understand when two groups are isomorphic, Sun could just try to understand when two matrix spaces are isometric — a notion of isomorphism of matrix spaces that corresponds to that of groups.

Sun was not the first researcher to adopt this approach, but he was the first to introduce an additional step: splitting a matrix space into two pieces. One piece is the core of the space, in which all the matrices are simple. The other piece is the space surrounding that core, in which all the matrices are particularly complex. This move corresponds to splitting a group into subgroups that contain only some of the total elements.

Sun then applied different algorithmic methods to each of these pieces. The core has a simple structure, so he used a characterization of the structure to represent it in a more organized way. The outer layer is more complex, so there’s no obviously fast way to compare it to another. Instead, Sun’s method takes an approach called individualization and refinement to rule out most of the possible ways of mapping one outer layer onto the other and then uses a computer to work through all remaining possible ways to determine whether an isomorphic matching exists.

The method is similar in spirit to how you might solve a sudoku puzzle. There are some squares whose potential values are constrained by what you already know (the core of the matrix space), allowing you to fill them in quickly. Then there are others (the outer layer) which have fewer constraints, but which you can figure out just by trying all possible values — and as long as there aren’t too many of these kinds of squares, you can still solve the puzzle in a reasonable amount of time.

“I fill in all the things I can quickly tell are constrainable, and now I might go back in and try my heart out on the missing boxes,” Wilson said. “If you’ve narrowed the scope, now it’s a good time to switch gears and use the computer to search for the right values.”

Sun’s breakthrough was showing that it’s always possible to do this splitting for the matrix spaces corresponding to p-groups of class 2 and exponent p. He then proved that after such a split, a combination of algorithmic techniques makes it possible to determine whether two spaces are isomorphic in $latex n^{{(log,n)}^{5/6}}$ time, a value that’s slightly lower than Tarjan’s $latex n^{{(log,n)}}$ method. (Both algorithms also include constant terms, which don’t have a big effect on the runtime, and which we’ve left out for clarity.)

The result doesn’t determine which speed category group isomorphism falls into; it’s still somewhere between exponential and polynomial time. But Sun has nudged it slightly closer to the polynomial side of things, and there’s reason to believe more than that should be possible. After all, his work provides computer scientists with a faster group isomorphism algorithm for the hardest kind of groups, raising the possibility that a similar speedup could be within reach for groups of all kinds.

“If you can solve it for p-groups, probably you can solve the whole thing,” Grochow said. “Maybe.”