skip to main content

Attention:

The NSF Public Access Repository (PAR) system and access will be unavailable from 11:00 PM ET on Thursday, February 13 until 2:00 AM ET on Friday, February 14 due to maintenance. We apologize for the inconvenience.


Title: On p-Group Isomorphism: search-to-decision, counting-to-decision, and nilpotency class reductions via tensors

In this paper we study some classical complexity-theoretic questions regarding GroupIsomorphism(GpI). We focus onp-groups (groups of prime power order) with oddp, which are believed to be a bottleneck case for GpI, and work in the model of matrix groups over finite fields. Our main results are as follows.

Although search-to-decision and counting-to-decision reductions have been known for over four decades for GraphIsomorphism(GI), they had remained open for GpI, explicitly asked by Arvind & Torán (Bull. EATCS, 2005). Extending methods from TensorIsomorphism(Grochow & Qiao, ITCS 2021), we show moderately exponential-time such reductions withinp-groups of class 2 and exponentp.

Despitethe widely held belief thatp-groups of class 2 and exponentpare the hardest cases of GpI, there was no reduction to these groups from any larger class of groups. Again using methods from Tensor Isomorphism (ibid.), we show the first such reduction, namely from isomorphism testing ofp-groups of “small” class and exponentpto those of class two and exponentp.

For the first results, our main innovation is to develop linear-algebraic analogues of classical graph coloring gadgets, a key technique in studying the structural complexity ofGI. Unlike the graph coloring gadgets, which support restricting to various subgroups of the symmetric group, the problems we study require restricting to various subgroups of the general linear group, which entails significantly different and more complicated gadgets.

The analysis of one of our gadgets relies on a classical result from group theory regarding random generation of classical groups (Kantor & Lubotzky, Geom. Dedicata, 1990). For the nilpotency class reduction, we combine a runtime analysis

of the Lazard correspondence with TensorIsomorphism-completeness results (Grochow & Qiao, ibid.).

 
more » « less
Award ID(s):
2047756
PAR ID:
10494305
Author(s) / Creator(s):
;
Publisher / Repository:
ACM
Date Published:
Journal Name:
ACM Transactions on Computation Theory
ISSN:
1942-3454
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Kabanets, Valentine (Ed.)
    In this paper we study some classical complexity-theoretic questions regarding Group Isomorphism (GpI). We focus on p-groups (groups of prime power order) with odd p, which are believed to be a bottleneck case for GpI, and work in the model of matrix groups over finite fields. Our main results are as follows. - Although search-to-decision and counting-to-decision reductions have been known for over four decades for Graph Isomorphism (GI), they had remained open for GpI, explicitly asked by Arvind & Torán (Bull. EATCS, 2005). Extending methods from Tensor Isomorphism (Grochow & Qiao, ITCS 2021), we show moderately exponential-time such reductions within p-groups of class 2 and exponent p. - Despite the widely held belief that p-groups of class 2 and exponent p are the hardest cases of GpI, there was no reduction to these groups from any larger class of groups. Again using methods from Tensor Isomorphism (ibid.), we show the first such reduction, namely from isomorphism testing of p-groups of "small" class and exponent p to those of class two and exponent p. For the first results, our main innovation is to develop linear-algebraic analogues of classical graph coloring gadgets, a key technique in studying the structural complexity of GI. Unlike the graph coloring gadgets, which support restricting to various subgroups of the symmetric group, the problems we study require restricting to various subgroups of the general linear group, which entails significantly different and more complicated gadgets. The analysis of one of our gadgets relies on a classical result from group theory regarding random generation of classical groups (Kantor & Lubotzky, Geom. Dedicata, 1990). For the nilpotency class reduction, we combine a runtime analysis of the Lazard Correspondence with Tensor Isomorphism-completeness results (Grochow & Qiao, ibid.). 
    more » « less
  2. The group isomorphism problem determines whether two groups, given by their Cayley tables, are isomorphic. For groups with order $n$, an algorithm with $n^{(\log n + O(1))}$ running time, attributed to Tarjan, was proposed in the 1970s (Miller, STOC 1978). Despite the extensive study over the past decades, the current best group isomorphism algorithm has an $n^{(1 / 4 + o(1))\log n}$ running time (Rosenbaum 2013). The isomorphism testing for $p$-groups of (nilpotent) class 2 and exponent $p$ has been identified as a major barrier to obtaining an $n^{o(\log n)}$ time algorithm for the group isomorphism problem. Although the $p$-groups of class 2 and exponent $p$ have much simpler algebraic structures than general groups, the best-known isomorphism testing algorithm for this group class also has an $n^{O(\log n)}$ running time. In this paper, we present an isomorphism testing algorithm for $p$-groups of class 2 and exponent $p$ with running time $n^{O((\log n)^{5/6})}$ for any prime $p > 2$. Our result is based on a novel reduction to the skew-symmetric matrix tuple isometry problem (Ivanyos and Qiao, SIAM J. Computing, 2019). To obtain the reduction, we develop several tools for matrix space analysis, including a matrix space individualization-refinement method and a characterization of the low rank matrix spaces. 
    more » « less
  3. Antonis Achilleos ; Dario Della Monica (Ed.)
    In this paper, we explore the descriptive complexity theory of finite groups by examining the power of the second Ehrenfeucht-Fraisse bijective pebble game in Hella's (Ann. Pure Appl. Log., 1989) hierarchy. This is a Spoiler-Duplicator game in which Spoiler can place up to two pebbles each round. While it trivially solves graph isomorphism, it may be nontrivial for finite groups, and other ternary relational structures. We first provide a novel generalization of Weisfeiler-Leman (WL) coloring, which we call 2-ary WL. We then show that the 2-ary WL is equivalent to the second Ehrenfeucht-Fraisse bijective pebble game in Hella's hierarchy. Our main result is that, in the pebble game characterization, only O(1) pebbles and O(1) rounds are sufficient to identify all groups without Abelian normal subgroups (a class of groups for which isomorphism testing is known to be in P; Babai, Codenotti, & Qiao, ICALP 2012). In particular, we show that within the first few rounds, Spoiler can force Duplicator to select an isomorphism between two such groups at each subsequent round. By Hella's results (ibid.), this is equivalent to saying that these groups are identified by formulas in first-order logic with generalized 2-ary quantifiers, using only O(1) variables and O(1) quantifier depth. 
    more » « less
  4. We study 2-generated subgroups $\langle f,g\rangle <\operatorname{Homeo}^{+}(I)$ such that $\langle f^{2},g^{2}\rangle$ is isomorphic to Thompson’s group $F$ , and such that the supports of $f$ and $g$ form a chain of two intervals. We show that this class contains uncountably many isomorphism types. These include examples with non-abelian free subgroups, examples which do not admit faithful actions by $C^{2}$ diffeomorphisms on 1-manifolds, examples which do not admit faithful actions by $PL$ homeomorphisms on an interval, and examples which are not finitely presented. We thus answer questions due to Brin. We also show that many relatively uncomplicated groups of homeomorphisms can have very complicated square roots, thus establishing the behavior of square roots of $F$ as part of a general phenomenon among subgroups of $\operatorname{Homeo}^{+}(I)$ . 
    more » « less
  5. Abstract

    We prove three results concerning the existence of Bohr sets in threefold sumsets. More precisely, lettingGbe a countable discrete abelian group and$\phi _1, \phi _2, \phi _3: G \to G$be commuting endomorphisms whose images have finite indices, we show that

    If$A \subset G$has positive upper Banach density and$\phi _1 + \phi _2 + \phi _3 = 0$, then$\phi _1(A) + \phi _2(A) + \phi _3(A)$contains a Bohr set. This generalizes a theorem of Bergelson and Ruzsa in$\mathbb {Z}$and a recent result of the first author.

    For any partition$G = \bigcup _{i=1}^r A_i$, there exists an$i \in \{1, \ldots , r\}$such that$\phi _1(A_i) + \phi _2(A_i) - \phi _2(A_i)$contains a Bohr set. This generalizes a result of the second and third authors from$\mathbb {Z}$to countable abelian groups.

    If$B, C \subset G$have positive upper Banach density and$G = \bigcup _{i=1}^r A_i$is a partition,$B + C + A_i$contains a Bohr set for some$i \in \{1, \ldots , r\}$. This is a strengthening of a theorem of Bergelson, Furstenberg and Weiss.

    All results are quantitative in the sense that the radius and rank of the Bohr set obtained depends only on the indices$[G:\phi _j(G)]$, the upper Banach density ofA(in (1)), or the number of sets in the given partition (in (2) and (3)).

     
    more » « less