{
  "id": "1810.13178",
  "version": "v1",
  "published": "2018-10-31T09:41:18.000Z",
  "updated": "2018-10-31T09:41:18.000Z",
  "title": "Asymptotic Analysis of Regular Sequences",
  "authors": [
    "Clemens Heuberger",
    "Daniel Krenn"
  ],
  "comment": "This is a full journal version of the published articles (extended abstracts) arXiv:1802.03266 and arXiv:1808.00842 and therefore supersedes these two",
  "categories": [
    "math.CO"
  ],
  "abstract": "In this article, $q$-regular sequences in the sense of Allouche and Shallit are analysed asymptotically. It is shown that the summatory function of a regular sequence is a sum of periodic fluctuations multiplied by a scaling factor. Each summand corresponds to an eigenvalue of the sum of matrices of a linear representation of the sequence; only the eigenvalues of absolute value larger than the joint spectral radius of the matrices grow faster than the error term. The Fourier coefficients of the fluctuations are expressed in terms of residues of the corresponding Dirichlet generating function. A known pseudo Tauberian argument is extended in order to overcome convergence issues in Mellin--Perron summation in the asymptotic analysis. Apart from the very general result, three examples are discussed in more detail: sequences defined as the sum of outputs written by a transducer when reading a $q$-ary expansion of the input; the number of odd entries in the rows of Pascal's rhombus; and the amount of esthetic numbers in the first~$N$ natural numbers. For these examples, very precise asymptotic formul\\ae{} are presented. In the latter two examples, prior to this analysis only rough estimates were known.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-10-31T09:41:18.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A16",
      "11A63",
      "68Q45",
      "68R05"
    ],
    "keywords": [
      "regular sequence",
      "asymptotic analysis",
      "joint spectral radius",
      "absolute value larger",
      "pseudo tauberian argument"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}