{
  "id": "0810.0390",
  "version": "v1",
  "published": "2008-10-02T11:39:21.000Z",
  "updated": "2008-10-02T11:39:21.000Z",
  "title": "Decision problems and profinite completions of groups",
  "authors": [
    "Martin R. Bridson"
  ],
  "categories": [
    "math.GR"
  ],
  "abstract": "We consider pairs of finitely presented, residually finite groups $P\\hookrightarrow\\G$ for which the induced map of profinite completions $\\hat P\\to \\hat\\G$ is an isomorphism. We prove that there is no algorithm that, given an arbitrary such pair, can determine whether or not $P$ is isomorphic to $\\G$. We construct pairs for which the conjugacy problem in $\\G$ can be solved in quadratic time but the conjugacy problem in $P$ is unsolvable. Let $\\mathcal J$ be the class of super-perfect groups that have a compact classifying space and no proper subgroups of finite index. We prove that there does not exist an algorithm that, given a finite presentation of a group $\\G$ and a guarantee that $\\G\\in\\mathcal J$, can determine whether or not $\\G\\cong\\{1\\}$. We construct a finitely presented acyclic group $\\H$ and an integer $k$ such that there is no algorithm that can determine which $k$-generator subgroups of $\\H$ are perfect.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2008-10-02T11:39:21.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "20E18",
      "20F10"
    ],
    "keywords": [
      "profinite completions",
      "decision problems",
      "conjugacy problem",
      "residually finite groups",
      "finite index"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2008arXiv0810.0390B"
    }
  }
}