An official website of the United States government
We introduce and study Polish topologies on various spaces of countable enumerated groups, where an enumerated group is simply a group whose underlying set is the set of natural numbers. Using elementary tools and well-known examples from combinatorial group theory, combined with the Baire category theorem, we obtain a plethora of results demonstrating that several phenomena in group theory are generic. In effect, we provide a new topological framework for the analysis of various well known problems in group theory. We also provide a connection between genericity in these spaces, the word problem for finitely generated groups and model-theoretic forcing. Using these connections, we investigate a natural question raised by Osin: when does a certain space of enumerated groups contain a comeager isomorphism class? We obtain a sufficient condition that allows us to answer Osin’s question in the negative for the space of all enumerated groups and the space of left orderable enumerated groups. We document several open questions in connection with these considerations.
more »
« less
This content will become publicly available on March 1, 2026
Two results on complexities of decision problems of groups
In this paper, we answer two questions on the complexities of decision problems of groups, each related to a classical result. First, Miller characterized the complexity of the isomorphism problem for finitely presented groups in 1971. We do the same for the isomorphism problem for recursively presented groups. Second, the fact that every Turing degree appears as the degree of the word problem of a finitely presented group is shown independently by multiple people in the 1960s. We answer the analogous question for degrees of ceers instead of Turing degrees. We show that the set of ceers which are computably equivalent to the word problem of a finitely presented group is [Formula: see text]-complete, which is the maximal possible complexity.
more »
« less
- PAR ID:
- 10586956
- Publisher / Repository:
- World Scientific Publishing Co
- Date Published:
- Journal Name:
- International Journal of Algebra and Computation
- Volume:
- 35
- Issue:
- 02
- ISSN:
- 0218-1967
- Page Range / eLocation ID:
- 311 to 327
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Guruswami, Venkatesan (Ed.)We study the complexity of isomorphism problems for d-way arrays, or tensors, under natural actions by classical groups such as orthogonal, unitary, and symplectic groups. These problems arise naturally in statistical data analysis and quantum information. We study two types of complexity-theoretic questions. First, for a fixed action type (isomorphism, conjugacy, etc.), we relate the complexity of the isomorphism problem over a classical group to that over the general linear group. Second, for a fixed group type (orthogonal, unitary, or symplectic), we compare the complexity of the isomorphism problems for different actions. Our main results are as follows. First, for orthogonal and symplectic groups acting on 3-way arrays, the isomorphism problems reduce to the corresponding problems over the general linear group. Second, for orthogonal and unitary groups, the isomorphism problems of five natural actions on 3-way arrays are polynomial-time equivalent, and the d-tensor isomorphism problem reduces to the 3-tensor isomorphism problem for any fixed d >= 3. For unitary groups, the preceding result implies that LOCC classification of tripartite quantum states is at least as difficult as LOCC classification of d-partite quantum states for any d. Lastly, we also show that the graph isomorphism problem reduces to the tensor isomorphism problem over orthogonal and unitary groups.more » « less
-
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
-
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
-
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
