{
  "id": "2406.01836",
  "version": "v1",
  "published": "2024-06-03T23:09:12.000Z",
  "updated": "2024-06-03T23:09:12.000Z",
  "title": "Scott analysis, linear orders and almost periodic functions",
  "authors": [
    "David Gonzalez",
    "Matthew Harrison-Trainor",
    "Meng-Che \"Turbo\" Ho"
  ],
  "comment": "15 pages",
  "categories": [
    "math.LO"
  ],
  "abstract": "For any limit ordinal $\\lambda$, we construct a linear order $L_\\lambda$ whose Scott complexity is $\\Sigma_{\\lambda+1}$. This completes the classification of the possible Scott sentence complexities of linear orderings. Previously, there was only one known construction of any structure (of any signature) with Scott complexity $\\Sigma_{\\lambda+1}$, and our construction gives new examples, e.g., rigid structures, of this complexity. Moreover, we can construct the linear orders $L_\\lambda$ so that not only does $L_\\lambda$ have Scott complexity $\\Sigma_{\\lambda+1}$, but there are continuum-many structures $M \\equiv_\\lambda L_\\lambda$ and all such structures also have Scott complexity $\\Sigma_{\\lambda+1}$. In contrast, we demonstrate that there is no structure (of any signature) with Scott complexity $\\Pi_{\\lambda+1}$ that is only $\\lambda$-equivalent to structures with Scott complexity $\\Pi_{\\lambda+1}$. Our construction is based on functions $f \\colon \\mathbb{Z}\\to \\mathbb{N}\\cup \\{\\infty\\}$ which are almost periodic but not periodic, such as those arising from shifts of the $p$-adic valuations.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-06-03T23:09:12.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "scott complexity",
      "periodic functions",
      "scott analysis",
      "scott sentence complexities",
      "construction"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 15,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}