Reduction of the group isomorphism problem to the group automorphism problem

Saveliy V. Skresanov · 2025

Read Reduction of the group isomorphism problem to the group automorphism problem by Saveliy V. Skresanov (2025) 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-2503-01180.txt.

Introduction

Deciding whether two groups are secretly the same, under a renaming of their elements, is the group isomorphism problem, a classic hard nut in computer science. Saveliy Skresanov proves that this problem reduces, in polynomial time, to the group automorphism problem: telling whether a single group has hidden symmetries. The result mirrors a famous fact for graphs, where isomorphism and automorphism are known to be polynomial-time equivalent. His reduction places the two group problems on the same footing.

Skresanov also gives reductions to related tasks, including counting automorphisms. Reductions of this kind matter because they let algorithms and hardness results travel between problems: a fast method for one becomes a fast method for the other. The author presents the work as closing an analogy that graph theory had long enjoyed and group theory had not.

Catalog record

CREATORSaveliy V. Skresanov
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE15 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-01180

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Reduction of the group isomorphism problem to the group automorphism problem Saveliy V. Skresanov Abstract It is well known that the graph isomorphism problem is polynomial-time reducible to the graph automorphism problem (in fact these two problems are polynomial-time equivalent). We show that, analogously, the group isomorphism problem is polynomial-time reducible to the group automorphism problem. Reductions to other relevant problems like automorphism counting are also given. 1 Introduction The graph isomorphism problem — the problem of deciding whether two input graphs given by their adjacency matrices are isomorphic or not — is one of the main candidates for a problem of intermediate computational complexity. Indeed, graph isomorphism can be easily seen to lie in class NP, and the common conjecture is that it is not NP-complete, see some evidence in [ 11 ] . Nevertheless, no polynomial-time algorithm is known for graph isomorphism. The long history of improving time complexity of graph isomorphism algorithms culminated in a 2015 breakthrough by Babai [ 1 ] , who gave a quasipolynomial algorithm for that task. More precisely, his algorithm decides whether two graphs on n vertices are isomorphic or not in time n^{O((\log n)^{c})} for some constant c\geq 1 . This brings time complexity of graph isomorphism close to the one for the group isomorphism problem , that is, the problem of deciding whether two groups given by their Cayley tables are isomorphic or not. Indeed, the latter has a simple algorithm attributed to Tarjan in [ 10 ] of complexity n^{O(\log n)} , where n is the order of the input groups. One important property of the graph isomorphism problem often used in studying its complexity, is the fact that it is polynomial-time equivalent to many other related problems, see [ 9 ] . For example, it is polynomial-time equivalent to the problem of finding generators of the full automorphism group of some input graph. Since Luks’s algorithm for isomorphism of graphs of bounded degree [ 8 ] , this latter problem played the main role in enabling the use of group-theoretical techniques in isomorphism testing. The reduction of the graph isomorphism problem to the problem of finding the full automorphism group of some graph is easy to state. By considering connected components, we may assume that our input graphs \Gamma_{1} and \Gamma_{2} are connected. Compute generators of the full automorphism group of their disjoint union \Gamma_{1}\sqcup\Gamma_{2} . Then \Gamma_{1} and \Gamma_{2} are isomorphic if and only if there exists a generator which swaps their vertex sets. Given access to the graph automorphism oracle, it can be easily seen that all the required steps can be computed in polynomial time. The goal of this paper is to provide a similar reduction of the group isomorphism problem to the group automorphism problem. The idea of the proof follows the procedure described above, but instead of connected components we consider directly indecomposable groups, and direct products instead of disjoint unions. To make the argument work, we require some nontrivial results and algorithms for finite groups, for example, the description of the full automorphism group of a direct product by Bidwell, Curran and McCaughan [ 2 , 3 ] , and a polynomial-time algorithm for factoring groups into direct factors by Kayal and Nezhmetdinov [ 6 ] . To state the result, we introduce a set of computational problems for groups, which follow similar problems for graphs from [ 9 ] . Recall that all input groups are given by their Cayley tables, and generators of the full automorphism group \Aut(G) of a group G are given as permutations on the set G . The automorphic partition of G is the set of orbits of \Aut(G) in the natural action on G . \displaystyle\mathrm{GrpISO}(G,H):\text{ determine if two groups }G\text{ and }H\text{ are isomorphic or not.} \displaystyle\mathrm{GrpIMAP}(G,H):\text{ find an isomorphism between }G\text{ and }H\text{ if it exists.} \displaystyle\mathrm{GrpICOUNT}(G,H):\text{ count the number of isomorphisms between }G\text{ and }H. \displaystyle\mathrm{GrpACOUNT}(G):\text{ count the number of automorphisms of }G. \displaystyle\mathrm{GrpAGEN}(G):\text{ find generators of the full automorphism group of }G. \displaystyle\mathrm{GrpAPART}(G):\text{ find the automorphic partition of }G. For two computational problems P_{1} and P_{2} we write P_{1}\propto P_{2} if P_{1} is polynomial-time reducible to P_{2} . Problems P_{1} and P_{2} are polynomial-time equivalent if P_{1}\propto P_{2} and P_{2}\propto P_{1} . Theorem 1 . The following hold: (i) \mathrm{GrpISO}\propto\mathrm{GrpACOUNT}\propto\mathrm{GrpAGEN} , (ii) \mathrm{GrpISO}\propto\mathrm{GrpAPART}\propto\mathrm{GrpAGEN} , (iii) \mathrm{GrpIMAP}\propto\mathrm{GrpAGEN} , (iv) \mathrm{GrpICOUNT} and \mathrm{GrpACOUNT} are polynomial-time equivalent. We noted that for graphs, isomorphism and automorphism problems are polynomial-time equivalent. The reduction of automorphism group computation to isomorphism testing uses graph gadgets, which essentially allow coloring graph vertices. By individualising graph vertices in a special way, it is possible to deduce automorphisms of the graph using several queries to the graph isomorphism oracle. Unfortunately this technique seems to be unavailable for groups, as it is not clear how to “color” group elements while preserving the group structure. One way to remedy this is to consider isomorphism problems for colored groups , where elements of the groups can be colored and isomorphisms must preserve the colors. It is shown in [ 4 , Lemma 8.1] that problems \mathrm{GrpISO} , \mathrm{GrpIMAP} and \mathrm{GrpAGEN} are polynomial-time equivalent for colored groups, and in fact the proof of [ 4 , Lemma 8.1] can be easily adapted to show that problems \mathrm{GrpICOUNT} , \mathrm{GrpACOUNT} and \mathrm{GrpAPART} are also polynomial-time equivalent to \mathrm{GrpISO} for colored groups. We remark that even for abelian colored groups the isomorphism problem is highly nontrivial, since a polynomial-time algorithm for such a problem would greatly simplify current algorithms for computing 2-closures of primitive affine permutation groups. Indeed, in many important cases the latter problem reduces to the following task: given a finite vector space V and a linear group G\leq\mathrm{GL}(V) acting on V , find the largest subgroup of \mathrm{GL}(V) having the same orbits on V as G . This can be easily seen to be reducible to the problem of computing the full automorphism group of a colored abelian group V , where the color classes are the orbits of G on V . Current algorithms for this problem heavily utilize the group-theoretical structure of G and do not work for all input groups, for example, see [ 13 ] and references therein. 2 Preliminaries We refer the reader to [ 5 ] for the basic facts about finite groups. We write G\times H for the direct product of groups G and H , and G\rtimes H for the semidirect product, where H is assumed to act on G by automorphisms. Let Z(G) denote the center of G , and let [G,G] stand for the derived subgroup. We write \Aut(G) for the full automorphism group of G , and \Hom(G,H) for the set of all homomorphisms from the group G into the group H . Given an element g\in G , we write |g| for its order. Input groups to the algorithms are given by their Cayley tables. A subgroup of such a group is given as a list of its elements, and a homomorphism {\phi:G\to H} is given as a list of pairs (g,\phi(g)) , g\in G ; observe that the space required is polynomial in the sizes of the input groups. Note that

Read the complete text