Math 2.0

Group theory and generalizations Infinite groups and combinatorial group theory Problem

Conjugacy problem

Builds on Finitely generated groupConjugate elementsPresentation of a group

Problem

Let GG be a finitely generated group with a finite generating set SS. A word is a finite sequence of elements of SS and their inverses. The conjugacy problem for GG asks for an algorithm that takes two words uu and vv and decides whether they represent conjugate elements of GG. That is, the algorithm decides whether v=gug−1v = g u g^{-1} in GG for some g∈Gg \in G.

Remarks

Whether the problem is solvable does not depend on the finite generating set. A word ww represents the identity if and only if it is conjugate to the empty word. So an algorithm for the conjugacy problem solves the word problem, and every group with unsolvable word problem has unsolvable conjugacy problem. The converse fails: there are finitely presented groups with solvable word problem and unsolvable conjugacy problem.

The problem is solvable in many classes of groups. In a free group, two elements are conjugate if and only if their cyclically reduced forms are cyclic permutations of each other. It is also solvable for finitely generated abelian groups, where it is the word problem, for hyperbolic groups, and for braid groups. It is one of the three decision problems, with the word problem and the isomorphism problem, that Max Dehn posed for groups given by presentations.

Reading path

To understand this page from the ground up, read these 4 pages in order. The foundations come first.

Show the path as a graph
Conjugate elements, concept, no evidence levelConjugate elementsconceptFinitely generated group, concept, no evidence levelFinitely generated gr…conceptPresentation of a group, concept, no evidence levelPresentation of a gro…conceptConjugacy problem, problem, no evidence levelConjugacy problemproblem
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Conjugate elements concept
  2. Finitely generated group concept
  3. Presentation of a group concept
  4. Conjugacy problem problem

Further reading

  1. Web https://en.wikipedia.org/wiki/Conjugacy_problem
About this page
Tag4AF7AF7690
URIm2://4AF7AF7690
Kindproblem
WritingW0 stub
MSC20F10, 03D40
StatusThis copy of the site has no build data. Run m2 status 4AF7AF7690.
AboutConjugate elements, Finitely generated group
UsesFinitely generated group, Conjugate elements, Presentation of a group
Same as
Changed2 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.