Group isomorphism problem

Last updated

In abstract algebra, the group isomorphism problem is the decision problem of determining whether two given finite group presentations refer to isomorphic groups.

The isomorphism problem was formulated by Max Dehn, [1] and together with the word problem and conjugacy problem, is one of three fundamental decision problems in group theory he identified in 1911. [2] All three problems, formulated as ranging over all finitely presented groups, are undecidable. In the case of the isomorphism problem, this means that there does not exist a computer algorithm that takes two finite group presentations and decides whether or not the groups are isomorphic, regardless of how (finitely) much time is allowed for the algorithm to run and how (finitely) much memory is available. In fact the problem of deciding whether a finitely presented group is trivial is undecidable, [3] a consequence of the Adian–Rabin theorem due to Sergei Adian and Michael O. Rabin.

However, there are some classes of finitely presented groups for which the restriction of the isomorphism problem is known to be decidable. They include finitely generated abelian groups, finite groups, Gromov-hyperbolic groups [4] , virtually torsion-free relatively hyperbolic groups with nilpotent parabolics [5] , one-relator groups with non-trivial center [6] , and two-generator one-relator groups with torsion [7] .

The group isomorphism problem, restricted to the groups that are given by multiplication tables, can be reduced to a graph isomorphism problem but not vice versa. [8] Both have quasi-polynomial-time algorithms, the former since 1978 attributed to Robert Tarjan [9] and the latter since 2015 by László Babai. [10] A small but important improvement for the case p-groups of class 2 was obtained in 2023 by Xiaorui Sun. [11] [8]

Related Research Articles

In mathematics, especially in the area of abstract algebra known as combinatorial group theory, the word problem for a finitely generated group is the algorithmic problem of deciding whether two words in the generators represent the same element of . The word problem is a well-known example of an undecidable problem.

<span class="mw-page-title-main">Free group</span> Mathematics concept

In mathematics, the free groupFS over a given set S consists of all words that can be built from members of S, considering two words to be different unless their equality follows from the group axioms. The members of S are called generators of FS, and the number of generators is the rank of the free group. An arbitrary group G is called free if it is isomorphic to FS for some subset S of G, that is, if there is a subset S of G such that every element of G can be written in exactly one way as a product of finitely many elements of S and their inverses.

In mathematics, a presentation is one method of specifying a group. A presentation of a group G comprises a set S of generators—so that every element of the group can be written as a product of powers of some of these generators—and a set R of relations among those generators. We then say G has presentation

<span class="mw-page-title-main">Burnside problem</span> If G is a finitely generated group with exponent n, is G necessarily finite?

The Burnside problem asks whether a finitely generated group in which every element has finite order must necessarily be a finite group. It was posed by William Burnside in 1902, making it one of the oldest questions in group theory, and was influential in the development of combinatorial group theory. It is known to have a negative answer in general, as Evgeny Golod and Igor Shafarevich provided a counter-example in 1964. The problem has many refinements and variants that differ in the additional conditions imposed on the orders of the group elements. Some of these variants are still open questions.

<span class="mw-page-title-main">Graph isomorphism</span> Bijection between the vertex set of two graphs

In graph theory, an isomorphism of graphsG and H is a bijection between the vertex sets of G and H

<span class="mw-page-title-main">Geometric group theory</span> Area in mathematics devoted to the study of finitely generated groups

Geometric group theory is an area in mathematics devoted to the study of finitely generated groups via exploring the connections between algebraic properties of such groups and topological and geometric properties of spaces on which these groups can act non-trivially.

The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic.

<span class="mw-page-title-main">Hyperbolic group</span> Mathematical concept

In group theory, more precisely in geometric group theory, a hyperbolic group, also known as a word hyperbolic group or Gromov hyperbolic group, is a finitely generated group equipped with a word metric satisfying certain properties abstracted from classical hyperbolic geometry. The notion of a hyperbolic group was introduced and developed by Mikhail Gromov. The inspiration came from various existing mathematical theories: hyperbolic geometry but also low-dimensional topology, and combinatorial group theory. In a very influential chapter from 1987, Gromov proposed a wide-ranging research program. Ideas and foundational material in the theory of hyperbolic groups also stem from the work of George Mostow, William Thurston, James W. Cannon, Eliyahu Rips, and many others.

In computational mathematics, a word problem is the problem of deciding whether two given expressions are equivalent with respect to a set of rewriting identities. A prototypical example is the word problem for groups, but there are many other instances as well. A deep result of computational theory is that answering this question is in many important cases undecidable.

In abstract algebra, the conjugacy problem for a group G with a given presentation is the decision problem of determining, given two words x and y in G, whether or not they represent conjugate elements of G. That is, the problem is to determine whether there exists an element z of G such that

In mathematics, in the realm of group theory, a countable group is said to be SQ-universal if every countable group can be embedded in one of its quotient groups. SQ-universality can be thought of as a measure of largeness or complexity of a group.

In mathematics, a Hopfian group is a group G for which every epimorphism

In mathematics, especially in the area of abstract algebra known as combinatorial group theory, Nielsen transformations, named after Jakob Nielsen, are certain automorphisms of a free group which are a non-commutative analogue of row reduction and one of the main tools used in studying free groups,. They were introduced in to prove that every subgroup of a free group is free, but are now used in a variety of mathematics, including computational group theory, k-theory, and knot theory. The textbook Combinatorial Group Theory devotes all of chapter 3 to Nielsen transformations.

In the mathematical subject of group theory, the rank of a groupG, denoted rank(G), can refer to the smallest cardinality of a generating set for G, that is

<span class="mw-page-title-main">Zlil Sela</span> Israeli mathematician

Zlil Sela is an Israeli mathematician working in the area of geometric group theory. He is a Professor of Mathematics at the Hebrew University of Jerusalem. Sela is known for the solution of the isomorphism problem for torsion-free word-hyperbolic groups and for the solution of the Tarski conjecture about equivalence of first-order theories of finitely generated non-abelian free groups.

In the mathematical subject of group theory, small cancellation theory studies groups given by group presentations satisfying small cancellation conditions, that is where defining relations have "small overlaps" with each other. Small cancellation conditions imply algebraic, geometric and algorithmic properties of the group. Finitely presented groups satisfying sufficiently strong small cancellation conditions are word hyperbolic and have word problem solvable by Dehn's algorithm. Small cancellation methods are also used for constructing Tarski monsters, and for solutions of Burnside's problem.

In mathematics, the concept of a relatively hyperbolic group is an important generalization of the geometric group theory concept of a hyperbolic group. The motivating examples of relatively hyperbolic groups are the fundamental groups of complete noncompact hyperbolic manifolds of finite volume.

In the mathematical subject of geometric group theory, the Baumslag–Gersten group, also known as the Baumslag group, is a particular one-relator group exhibiting some remarkable properties regarding its finite quotient groups, its Dehn function and the complexity of its word problem.

In the mathematical subject of group theory, a one-relator group is a group given by a group presentation with a single defining relation. One-relator groups play an important role in geometric group theory by providing many explicit examples of finitely presented groups.

In the mathematical subject of group theory, the Adian–Rabin theorem is a result that states that most "reasonable" properties of finitely presentable groups are algorithmically undecidable. The theorem is due to Sergei Adian (1955) and, independently, Michael O. Rabin (1958).

References

  1. ↑ Dehn, Max (1911). "Über unendliche diskontinuierliche Gruppenn". Math. Ann. 71: 116–144. doi:10.1007/BF01456932. S2CID   123478582.
  2. ↑ Magnus, Wilhelm; Karrass, Abraham & Solitar, Donald (1996). Combinatorial Group Theory: Presentations of Groups in Terms of Generators and Relations (2nd ed.). New York: Dover Publications. pp. 24–29. ISBN   0486632814 . Retrieved 14 October 2022– via VDOC.PUB.
  3. ↑ Miller, Charles F. III (1992). "Decision Problems for Groups—survey and Reflections" (PDF). In Baumslag, Gilbert; Miller, C. F. III (eds.). Algorithms and Classification in Combinatorial Group Theory . Mathematical Sciences Research Institute Publications. Vol. 23. New York: Springer-Verlag. pp. 1–59. doi:10.1007/978-1-4613-9730-4_1. ISBN   9781461397328. (See Corollary 3.4)
  4. ↑ Dahmani, François; Guirardel, Vincent (2011). "The isomorphism problem for all hyperbolic groups". Geometric and Functional Analysis . 21 (2): 223–300. arXiv: 1002.2590 . doi:10.1007/s00039-011-0120-0. S2CID   115165062.
  5. ↑ Dahmani, François; Touikan, Nicholas (2019-01-01). "Deciding isomorphy using Dehn fillings, the splitting case". Inventiones mathematicae. 215 (1): 81–169. doi:10.1007/s00222-018-0824-y. ISSN   1432-1297.
  6. ↑ Pietrowski, Alfred (1974-06-01). "The isomorphism problem for one-relator groups with non-trivial centre". Mathematische Zeitschrift. 136 (2): 95–106. doi:10.1007/BF01214345. ISSN   1432-1823.
  7. ↑ Pride, Stephen J. (1977). "The isomorphism problem for two-generator one-relator groups with torsion is solvable". Transactions of the American Mathematical Society. 227: 109–139. doi:10.1090/S0002-9947-1977-0430085-X. ISSN   0002-9947.
  8. 1 2 Hartnett, Kevin (23 June 2023). "Computer Scientists Inch Closer to Major Algorithmic Goal". Quanta Magazine .
  9. ↑ Miller, Gary L. (1978). "On the nlog n isomorphism technique (A Preliminary Report)". Proceedings of the tenth annual ACM symposium on Theory of computing - STOC '78. ACM Press. pp. 51–58. doi:10.1145/800133.804331. ISBN   978-1-4503-7437-8.
  10. ↑ Babai, László (January 9, 2017), Graph isomorphism update
  11. ↑ Sun, Xiaorui (2023). "Faster Isomorphism for p-Groups of Class 2 and Exponent p". arXiv: 2303.15412 [cs.DS].


This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.