{
  "id": "2007.00070",
  "version": "v1",
  "published": "2020-06-30T19:24:32.000Z",
  "updated": "2020-06-30T19:24:32.000Z",
  "title": "Automata and tame expansions of $(\\mathbb{Z},+)$",
  "authors": [
    "Christopher D. C. Hawthorne"
  ],
  "comment": "20 pages",
  "categories": [
    "math.LO"
  ],
  "abstract": "The problem of characterizing which automatic sets of integers are stable is here initiated. Given a positive integer $d$ and a subset $A\\subseteq \\mathbb{Z}^m$ whose set of representations base $d$ is sparse and recognized by a finite automaton, a necessary condition is found for $x+y\\in A$ to be a stable formula in $\\operatorname{Th}(\\mathbb{Z},+,A)$. Combined with a theorem of Moosa and Scanlon this gives a combinatorial characterization of the $d$-sparse $A\\subseteq \\mathbb{Z}^m$ such that $(\\mathbb{Z},+,A)$ is stable. This characterization is in terms of what were called \"$F$-sets\" by Moosa and Scanlon and \"elementary $p$-nested sets\" by Derksen. For $A\\subseteq \\mathbb{Z}$ $d$-automatic but not $d$-sparse, it is shown that if $x+y\\in A$ is stable then finitely many translates of $A$ cover $\\mathbb{Z}$. Automata-theoretic methods are also used to produce some NIP expansions of $(\\mathbb{Z},+)$, in particular the expansion by the monoid $(d^\\mathbb{N},\\times )$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-06-30T19:24:32.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "03C45",
      "68Q45",
      "11B85",
      "F.4.1",
      "F.4.3"
    ],
    "keywords": [
      "tame expansions",
      "representations base",
      "finite automaton",
      "necessary condition",
      "combinatorial characterization"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 20,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}