When progress on a problem stalls as long as it did for group isomorphism, invention is usually necessary to get unstuck. \u201cWhen you have a big advance, that should be some indication that there\u2019s a new idea,\u201d Grochow said.<\/p>\n

Sun\u2019s 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.<\/p>\n

The groups Sun\u2019s algorithm works for are called p<\/em>-groups of class 2 and exponent p. <\/em>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\u2019t 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.<\/p>\n

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.<\/p>\n

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 \u2014 a notion of isomorphism of matrix spaces that corresponds to that of groups.<\/p>\n

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.<\/p>\n

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\u2019s no obviously fast way to compare it to another. Instead, Sun\u2019s 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.<\/p>\n

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 \u2014 and as long as there aren\u2019t too many of these kinds of squares, you can still solve the puzzle in a reasonable amount of time.<\/p>\n

\u201cI 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,\u201d Wilson said. \u201cIf you\u2019ve narrowed the scope, now it\u2019s a good time to switch gears and use the computer to search for the right values.\u201d<\/p>\n

Sun\u2019s breakthrough was showing that it\u2019s always possible to do this splitting for the matrix spaces corresponding to p<\/em>-groups of class 2 and exponent p<\/em>. 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\u2019s slightly lower than Tarjan\u2019s $latex n^{{(log,n)}}$ method. (Both algorithms also include constant terms, which don\u2019t have a big effect on the runtime, and which we\u2019ve left out for clarity.)<\/p>\n

The result doesn\u2019t determine which speed category group isomorphism falls into; it\u2019s still somewhere between exponential and polynomial time. But Sun has nudged it slightly closer to the polynomial side of things, and there\u2019s 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.<\/p>\n

\u201cIf you can solve it for p<\/em>-groups, probably you can solve the whole thing,\u201d Grochow said. \u201cMaybe.\u201d<\/p>\n<\/div>\n

<\/br><\/br><\/br><\/p>\n