Pattern sequences in \(\langle q,r\rangle\)-numeration systems (Q2270526)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Pattern sequences in \(\langle q,r\rangle\)-numeration systems
scientific article

    Statements

    Pattern sequences in \(\langle q,r\rangle\)-numeration systems (English)
    0 references
    0 references
    0 references
    28 July 2009
    0 references
    Let \(q\geq 2\) and \(0\leq r\leq q-2\) be integers. In this paper, the authors study pattern sequences for words in \(\langle q,r\rangle\)-numeration systems through their generating functions. This is done by showing that the generating functions of such systems satisfy certain Mahler-type functional equations. Recall that in the \(\langle q,r\rangle\)-numeration system (a generalization of the standard \(q\)-ary numeration), every positive integer \(n\) is uniquely expressed as \[ n=\sum_{i=0}^k\varepsilon_i q^i,\quad \varepsilon_i\in\Sigma_{q,r},\quad \varepsilon_k>0, \] where \[ \Sigma_{q,r}:=\{-r,1-r,\dots,0,1,\dots,q-1-r\}. \] Denote the set of all (finite) words over \(\Sigma_{q,r}\) by \(\Sigma_{q,r}^*\), and define \(e_{q,r}(w;n)\) to be the number of (possibly overlapping) occurrences of \(w\) in the \(\langle q,r\rangle\)-expansion of \(n\). The sequence \[ \{e_{q,r}(w;n)\}_{n\geq 0} \] is called the \textit{pattern sequence} for the word \(w\) in the \(\langle q,r\rangle\)-numeration system. The authors' main result is the following. Let \(w_{r,1},\ldots,w_{r,m_r}\in\Sigma_{q,r}^*\) \((0\leq r\leq q-2)\) and let \[ f_{r,i}(a)=\sum_{n\geq 0}e_{q,r}(w_{r,i};n)z^n\quad (0\leq r\leq q-2, 1\leq i\leq m_r). \] Then the \(f_{r,i}(z)\) \((0\leq r\leq q-2, 1\leq i\leq m_r)\) are algebraically independent over \(\mathbb{C}(z)\) if and only if for some \(r\) there exist \(c_1,\dots, c_{m_r}\in\mathbb{C}\), not all zero, such that the sequence \[ \left\{\sum_{i=0}^{m_r} c_i e_{q,r}(w_{r,i};n)\right\}_{n\geq q^l} \] is periodic with period \(q^{l-1}\), where \(l=\max_{0\leq r\leq q-2, 1\leq i\leq m_r} |w_{r,i}|.\) Moreover, if the \(f_{r,i}(z)\) \((0\leq r\leq q-2, 1\leq i\leq m_r)\) are algebraically independent over \(\mathbb{C}\), the numbers \(f_{r,i}(\alpha)\) \((0\leq r\leq q-2, 1\leq i\leq m_r)\) are algebraically independent for any algebraic number \(\alpha\) with \(0<|\alpha|<1\). A nice corollary of this result is that for given \(w_r\in\Sigma_{q,r}^*,\) \((r=0,1,\ldots,q-2)\), any nontrivial linear combination over \(\mathbb{C}\) \[ \left\{\sum_{r=0}^{q-2} c_r e_{q,r}(w_{r};n)\right\}_{n\geq 0} \] of the pattern sequences cannot be a linear recurrence sequence. In particular, pattern sequences in different \(\langle q,r\rangle\)-numeration systems are linearly independent over \(\mathbb{C}\), while within one \(\langle q,r\rangle\)-numeration system they can be linearly dependent over \(\mathbb{C}\). The authors give many examples and the paper is very easy to read.
    0 references
    0 references
    \(\langle q,r\rangle\)-expansion
    0 references
    \(\langle q,r\rangle\)-numeration systems
    0 references
    pattern sequences
    0 references
    algebraic independence
    0 references
    Mahler-type functional equations
    0 references

    Identifiers