Linear relations between pattern sequences in a \(\langle q, r\rangle\)-numeration system (Q663284): Difference between revisions

The authors of this paper discuss some problems in the theory of Numeration. Every possitive integer \(n\) can be represented uniquely in the form \(n=\sum^{k-1}_{i=0}b_{i}q^{i}\), where \(q\geq 2\) and \(r\) are integers, \(0\leq r\leq q-2\); \(b_{i}\in \Sigma_{q,r}:=\left\{-r, -r+1, \ldots , 0, 1, \ldots, q-r-1\right\}\). Here \(b_{i}\) are the digits in the \(\left\langle q, r\right\rangle\)-expansion of \(n\). (\(\left\langle q, 0\right\rangle\) is the ordinary numeration system, for instance \(q=10\) etc.) Every finite string of element in \(\Sigma_{q,r}\) is called pattern (or word) over \(\Sigma_{q,r}\). The set of all finite nonempty words is denoted by \(\Sigma^{*}_{q,r}\). The length \(| w| \) is by definition the number of the elements in \(w\). \(w^{k}\) means \(ww\ldots w\) (\(k\) times); \(w^{0}\) means an empty set; \(e_{q,r}(w;n)\) means the number of occurrences of \(w\) in the \(\left\langle q, r\right\rangle\)-expansion of \(n\),\(e_{q,r}(w;0)=0\) for any \(w\in\Sigma^{*}_{q,r}\). Finally, the authors define generating function of the pattern sequence \({e_{q,r}(w;n)}_{n\geq 0}\) for \(w\in \Sigma^{*}_{q,r}\) by \[ f(w;z)=\sum_{n\geq 0}e_{q,r} (w;n)z^{n} \] The authors prove six theorems. The first is (Theorem 1): let \(m\geq2\) and \(w_{1},\ldots,w_{m}\in\Sigma^{*}_{q,r}\) with \(l=\max_{1\leq i\leq m}| w_{i}| \). Then the following five statements are equivalent: (i) \(f(w_{1};z),\ldots, f(w_{m};z)\) are algebraically dependent over \({\mathbb C}(z)\). (ii) \(f(w_{1};z),\ldots, f(w_{m};z)\) are algebraically dependent over \({\mathbb C}\;\text{ mod }\, {\mathbb C}(z)\). (iii) There exist \(c_{1},\ldots, c_{m}\in {\mathbb C}\), not all zero, such that \(\left\{\sum^{m}_{i=1}c_{i}e_{q,r}(w_{i};n)\right\}_{n\geq0}\) is a linear recurrence sequence. (iv) There exist \(c_{i},\ldots, c_{m}\in {\mathbb C}\), not all zero, such that \(\left\{\sum^{m}_{i=1}c_{i} e_{q,r}(w_{i};n)\right\}_{n\geq0}\) is a purely periodic sequence with a period \(q^{l-1}\). (v) The rank of the matrix \(\left(e_{q,r} (w_{i};n)-e_{q,r}(w_{i};\overline{n})\right)_{q^{l-1}\leq n \leq q^{l}, 1\leq i\leq m}\) is less than \(m\), where \(n\equiv \overline{n} \pmod{q^{l-1}}\) with \(0\leq n\overline{n}<q^{l-1}\).