Polynomial-time isomorphism test for groups with abelian Sylow subgroups
Saveliy V. Skresanov · 2026
Read Polynomial-time isomorphism test for groups with abelian Sylow subgroups by Saveliy V. Skresanov (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-26748.txt.
Introduction
Skresanov generalizes a 2012 polynomial-time isomorphism test for solvable groups to the wider class of solvable A-groups, groups whose Sylow subgroups are abelian. The group isomorphism problem asks whether two finite groups given by Cayley tables are the same up to relabeling. His algorithm builds on methods of Babai and Qiao plus structural properties of A-groups, extending their result beyond groups with abelian Sylow factors in a normal series.
Catalog record
| CREATOR | Saveliy V. Skresanov |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 64373 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.26748
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Polynomial-time isomorphism test for groups with abelian Sylow subgroups Saveliy V. Skresanov Abstract The group isomorphism problem in computational complexity asks whether two finite groups given by their Cayley tables are isomorphic or not. Although polynomial-time isomorphism tests exist for many specific types of groups, no general polynomial-time algorithm is known, classes of solvable and nilpotent groups being the main obstacles. In 2012 Babai and Qiao gave a polynomial-time isomorphism test for the class of solvable groups admitting normal series with abelian Sylow factors. We generalize their result and give a polynomial-time isomorphism test for A-groups, i.e. groups with abelian Sylow subgroups. The algorithm heavily relies both on the computational methods developed by Babai and Qiao, and structural properties of A-groups. 1 Introduction The group isomorphism problem in computational complexity is a problem of testing whether two finite groups given by their Cayley tables are isomorphic or not. Although computations with groups given by Cayley tables are impractical for most orders, the Cayley table model serves as a useful theoretical tool. From the one hand, many group-theoretical tasks like computing centralizers, normalizers, Sylow subgroups etc. are performed trivially in polynomial time for groups given by Cayley tables. On the other hand, the group isomorphism problem is polynomial-time reducible to the graph isomorphism problem and hence serves as a lower bound on the complexity of the latter. It is well-known [ 20 ] that isomorphism of groups of order n can be tested in time n^{\log n+O(1)} , since such a group has at most \log n generators (all logarithms are base 2 in this work). Since Babai’s algorithm [ 1 ] for testing isomorphism of graphs on n vertices in time n^{O((\log n)^{c})} , c>1 , the group isomorphism problem became one of the main obstacles to further reducing the time complexity of graph isomorphism. There has been a lot of progress in the group isomorphism problem for specific classes of groups, see the introduction of [ 11 ] for an overview. We note here that, perhaps unsurprisingly, isomorphism of abelian groups can be tested in polynomial time and even in linear time [ 17 ] . On the other end of the spectrum, one can test in polynomial time isomorphism of groups with no nontrivial normal abelian subgroups or, in other words, groups with the trivial solvable radical [ 2 ] . Partly because of the latter result, it is widely believed that solvable groups or even nilpotent groups are the hardest cases of the group isomorphism problem, see [ 3 , Subsection 1.1] and [ 11 , Subsection 1.2] . Sylow subgroups of a finite group are nilpotent, and although there is no known reduction of the group isomorphism problem to the isomorphism problem for Sylow subgroups of a group, it is natural to consider some group classes with restrictions on the Sylow structure. One such class of groups was considered by Babai and Qiao in [ 3 ] . A finite group G has an abelian Sylow tower if there is a normal series G=N_{1}\unrhd N_{2}\unrhd\dots\unrhd N_{k}=1 , such that for every i=1,\dots,k-1 the group N_{i}/N_{i+1} is abelian and isomorphic to a Sylow subgroup of G . A group with an abelian Sylow tower is solvable and every its nilpotent subgroup is abelian. The main result of [ 3 ] gives a polynomial-time isomorphism test for groups with abelian Sylow towers. Proposition 1.1 ( [ 3 , Theorem 1.1] ) . Let G and G_{0} be groups given by their Cayley tables, and assume that G and G_{0} have abelian Sylow towers. In polynomial time one can check if G and G_{0} are isomorphic and find the coset of isomorphisms, if they are. We note that the set of isomorphisms between G and G_{0} is either empty, or a coset of \Aut(G) in the symmetric group \Sym(G\sqcup G_{0}) , where G\sqcup G_{0} is the disjoint union of G and G_{0} . We can compute this coset if we can compute permutation generators of \Aut(G) and a coset representative. Groups with abelian Sylow towers are a particular case of A-groups , that is, groups with abelian Sylow subgroups. The class of A-groups is closed with respect to taking subgroups, quotients and direct products, and contains nonsolvable groups, such as the alternating group \mathrm{Alt}(5) . As in the case of groups with abelian Sylow towers, every nilpotent subgroup of an A-group is abelian. The main result of this paper is a polynomial-time isomorphism test for A-groups given by Cayley tables. Theorem 1.2 . Let G and G_{0} be groups given by their Cayley tables, and assume that all Sylow subgroups of G and G_{0} are abelian. In polynomial time one can check if G and G_{0} are isomorphic and find the coset of isomorphisms, if they are. It is mentioned in [ 3 , Subsection 1.1] that there are at most n^{O(\log n)} isomorphism classes of solvable A-groups of order at most n , and at least n^{\Omega(\log n)} of those are groups with abelian Sylow towers. Notice that a solvable A-group does not always have an abelian Sylow tower, the group \Sym(3)\times\mathrm{Alt}(4) being an example, so Theorem 1.2 is an improvement to Proposition 1.1 even in the solvable case. Our proof of Theorem 1.2 follows the general strategy from [ 3 ] , so we explain the latter first. If the group G has an abelian Sylow tower, then one can decompose G as a semidirect product G=A\rtimes H , where A is an abelian p -group, and |H| is not divisible by p . By [ 3 , Theorem 1.2] , the isomorphism problem for G reduces to the isomorphism problem for H , if \Aut(H) is given to the algorithm as part of input. This reduction allows us to work along the abelian Sylow tower, until we are left with the isomorphism problem for abelian groups. The reduction itself is nontrivial, and relies on polynomial-time solutions to two problems about representations of H on A : the “representation-transporting automorphisms problem” [ 3 , Problem 2] and the “intertwining automorphisms problem” [ 3 , Problem 3] (we postpone the formal treatment of these problems to Sections 3 and 4 ). Polynomial-time algorithms for these tasks utilize representation theory of finite groups and heavily depend on the fact that |A| and |H| are coprime. In order to prove Theorem 1.2 , we first show that the isomorphism problem for A-groups can be reduced to the problem of computing the full group of automorphisms. The argument here follows [ 25 ] , but works inside the class of A-groups. Unfortunately the main result of [ 25 ] was formulated for the class of all finite groups, so in Section 6 we reprove that result for an arbitrary class of groups closed with respect to direct products and direct factors. Now, when G is an arbitrary A-group, we no longer have a decomposition G=A\rtimes H , where A is an abelian p -group and |H| is not divisible by p . Instead, as follows from the results of Broshi [ 4 ] , if G has a nontrivial solvable radical then there exists a characteristic abelian p -subgroup A of