{
  "id": "1903.07040",
  "version": "v1",
  "published": "2019-03-17T07:42:03.000Z",
  "updated": "2019-03-17T07:42:03.000Z",
  "title": "Generic-case complexity of Whitehead's algorithm, revisited",
  "authors": [
    "Ilya Kapovich"
  ],
  "comment": "34 pages; comments are welcome!",
  "categories": [
    "math.GR",
    "math.DS",
    "math.GT"
  ],
  "abstract": "In \\cite{KSS06} it was shown that with respect to the simple non-backtracking random walk on the free group $F_N=F(a_1,\\dots,a_N)$ the Whitehead algorithm has strongly linear time generic-case complexity and that \"generic\" elements of $F_N$ are \"strictly minimal\" in their $Out(F_N)$-orbits. Here we generalize these results, with appropriate modifications, to a much wider class of random processes generating elements of $F_N$. We introduce the notion of a \\emph{$(M,\\lambda, \\epsilon)$-minimal} conjugacy class $[w]$ in $F_N$, where $M\\ge 1, \\lambda>1$ and $0<\\epsilon<1$. Roughly, this means that every $\\phi\\in Out(F_N)$ either increases the length $||w||_A$ by a factor of at least $\\lambda$, or distorts the length $||w||_A$ multiplicatively by a factor $\\epsilon$-close to $1$, and the size of the component of the automorphism graph of $F_N$ corresponding to $[w]$ is bounded by $M$. We then show that if a conjugacy class $[w]$ in $F_N$ is sufficiently close to a ``filling\" projective geodesic current $[\\nu]\\in PCurr(F_N)$, then, after applying a single \"reducing\" automorphism $\\psi=\\psi(\\nu)\\in Out(F_N)$ depending on $\\nu$ only, the element $\\psi([w])$ is $(M,\\lambda, \\epsilon)$ for some uniform constants $M,\\lambda,\\epsilon$. Consequently, for such $[w]$, Whitehead's algorithm for the automorphic equivalence problem in $F_N$ works in quadratic time on the input $([w], [w'])$ where $[w']$ is arbitrary, and in linear time if $[w']$ is also projectively close to $[\\nu]$. We then show that a wide class of random processes produce \"random\" conjugacy classes $[w_n]$ that projectively converge to some filling current in $PCurr(F_N)$. For such $[w_n]$ Whitehead's algorithm has at most quadratic generic-case complexity.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-03-17T07:42:03.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "20F65",
      "20F10",
      "20F67",
      "37D99",
      "60B15",
      "68Q87",
      "68W40"
    ],
    "keywords": [
      "whiteheads algorithm",
      "conjugacy class",
      "strongly linear time generic-case complexity",
      "quadratic generic-case complexity",
      "random processes produce"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 34,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}