{
  "id": "2103.08302",
  "version": "v1",
  "published": "2021-03-09T14:57:02.000Z",
  "updated": "2021-03-09T14:57:02.000Z",
  "title": "Mixed quantifier prefixes over Diophantine equations with integer variables",
  "authors": [
    "Zhi-Wei Sun"
  ],
  "comment": "20 pages",
  "categories": [
    "math.NT",
    "math.LO"
  ],
  "abstract": "In this paper we study mixed quantifiers over Diophantine equations with integer variables. For example, we prove that $\\forall^2\\exists^4$ over $\\mathbb Z$ is undecidable, that is, there is no algorithm to determine for any $P(x_1,\\ldots,x_6)\\in\\mathbb Z[x_1,\\ldots,x_6]$ whether $$\\forall x_1\\forall x_2\\exists x_3\\exists x_4\\exists x_5\\exists x_6(P(x_1,\\ldots,x_6)=0),$$ where $x_1,\\ldots,x_6$ are integer variables. We also have some similar undecidable results with universal quantifies bounded, for example, $\\exists^2\\forall^2\\exists^2$ over $\\mathbb Z$ with $\\forall$ bounded is undecidable. We conjecture that $\\forall^2\\exists^2$ over $\\mathbb Z$ is undecidable.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-03-09T14:57:02.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "03D35",
      "11U05",
      "03D25",
      "11D99"
    ],
    "keywords": [
      "integer variables",
      "mixed quantifier prefixes",
      "diophantine equations",
      "universal quantifies",
      "similar undecidable results"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 20,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}