{
  "id": "1603.06122",
  "version": "v1",
  "published": "2016-03-19T18:00:33.000Z",
  "updated": "2016-03-19T18:00:33.000Z",
  "title": "Integer Complexity: Representing Numbers of Bounded Defect",
  "authors": [
    "Harry Altman"
  ],
  "comment": "31 pages, 4 figures",
  "categories": [
    "math.NT"
  ],
  "abstract": "Define $\\|n\\|$ to be the complexity of $n$, the smallest number of ones needed to write $n$ using an arbitrary combination of addition and multiplication. John Selfridge showed that $\\|n\\|\\ge 3\\log_3 n$ for all $n$. Based on this, this author and Zelinsky defined the \"defect\" of $n$, $\\delta(n):=\\|n\\|-3\\log_3 n$, and this author showed that the set of all defects is a well-ordered subset of the real numbers. This was accomplished by showing that for a fixed real number $r$, there is a finite set $S$ of polynomials called \"low-defect polynomials\" such that for any $n$ with $\\delta(n)<r$, $n$ has the form $f(3^{k_1},\\ldots,3^{k_r})3^{k_{r+1}}$ for some $f\\in S$. However, using the polynomials produced by this method, many extraneous $n$ with $\\delta(n)\\ge r$ would also be represented. In this paper we show how to remedy this and modify $S$ so as to represent precisely the $n$ with $\\delta(n)<r$ and remove anything extraneous. Since the same polynomial can represent both $n$ with $\\delta(n)<r$ and $n$ with $\\delta(n)\\ge r$, this is not a matter of simply excising the appropriate polynomials, but requires \"truncating\" the polynomials to form new ones.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-03-19T18:00:33.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "11A67"
    ],
    "keywords": [
      "integer complexity",
      "representing numbers",
      "bounded defect",
      "low-defect polynomials",
      "arbitrary combination"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 31,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2016arXiv160306122A"
    }
  }
}