{
  "id": "1907.03147",
  "version": "v1",
  "published": "2019-07-06T16:06:25.000Z",
  "updated": "2019-07-06T16:06:25.000Z",
  "title": "HTP-complete rings of rational numbers",
  "authors": [
    "Russell Miller"
  ],
  "categories": [
    "math.LO",
    "math.NT"
  ],
  "abstract": "For a ring $R$, Hilbert's Tenth Problem $HTP(R)$ is the set of polynomial equations over $R$, in several variables, with solutions in $R$. We view $HTP$ as an enumeration operator, mapping each set $W$ of prime numbers to $HTP(\\mathbb Z[W^{-1}])$, which is naturally viewed as a set of polynomials in $\\mathbb Z[X_1,X_2,\\ldots]$. It is known that for almost all $W$, the jump $W'$ does not $1$-reduce to $HTP(R_W)$. In contrast, we show that every Turing degree contains a set $W$ for which such a $1$-reduction does hold: these $W$ are said to be \"HTP-complete.\" Continuing, we derive additional results regarding the impossibility that a decision procedure for $W'$ from $HTP(\\mathbb Z[W^{-1}])$ can succeed uniformly on a set of measure $1$, and regarding the consequences for the boundary sets of the $HTP$ operator in case $\\mathbb Z$ has an existential definition in $\\mathbb Q$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-07-06T16:06:25.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "12L05",
      "03D45",
      "03C40"
    ],
    "keywords": [
      "rational numbers",
      "htp-complete rings",
      "boundary sets",
      "turing degree contains",
      "polynomial equations"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}