{
  "id": "2501.14643",
  "version": "v1",
  "published": "2025-01-24T17:03:59.000Z",
  "updated": "2025-01-24T17:03:59.000Z",
  "title": "Complexity of powers of a constant-recursive sequence",
  "authors": [
    "Eric Rowland",
    "Jesus Sistos Barron"
  ],
  "comment": "23 pages, 3 tables",
  "categories": [
    "math.NT"
  ],
  "abstract": "Constant-recursive sequences are those which satisfy a linear recurrence, so that later terms can be obtained as a linear combination of the previous ones. The rank of a constant-recursive sequence is the minimal number of previous terms required for such a recurrence. For a constant-recursive sequence $s(n)$, we study the sequence $\\left(\\text{rank}\\, s(n)^M\\right)_{M\\geq 1}$. We answer a question of Stinchcombe regarding the complexity of the powers of a constant-recursive sequence when the roots of the characteristic polynomial are not all distinct.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2025-01-24T17:03:59.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "constant-recursive sequence",
      "complexity",
      "linear recurrence",
      "characteristic polynomial",
      "linear combination"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 23,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}