{
  "id": "1902.06037",
  "version": "v1",
  "published": "2019-02-16T04:09:38.000Z",
  "updated": "2019-02-16T04:09:38.000Z",
  "title": "The Conjugacy Problem for Higman's Group",
  "authors": [
    "Owen Baker"
  ],
  "comment": "18 pages, comments welcome",
  "categories": [
    "math.GR"
  ],
  "abstract": "In 1951, Higman constructed a remarkable group $$H=\\left\\langle a,b,c,d \\, \\left| \\, b^a = b^2, c^b = c^2, d^c = d^2, a^d = a^2 \\right. \\right\\rangle$$ and used it to produce the first examples of infinite simple groups. By studying fixed points of certain finite state transducers, we show the conjugacy problem in $H$ is decidable (for all inputs). Diekert, Laun and Ushakov have recently shown the word problem in $H$ is solvable in polynomial time, using the power circuit technology of Myasnikov, Ushakov and Won. Building on this work, we show in a strongly generic setting that the conjugacy problem has a $O(n^7)$ polynomial time solution.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-02-16T04:09:38.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "20F10",
      "68Q70"
    ],
    "keywords": [
      "conjugacy problem",
      "higmans group",
      "polynomial time solution",
      "infinite simple groups",
      "power circuit technology"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 18,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}