# Asymptotic Analysis of $q$-Recursive Sequences

Clemens Heuberger  Daniel Krenn  Gabriel F. Lipnik

###### Abstract

For an integer $q\geq 2$, a $q$-recursive sequence is defined by recurrence
relations on subsequences of indices modulo some powers of $q$. In this
article, $q$-recursive sequences are studied and the asymptotic behavior of
their summatory functions is analyzed. It is shown that every $q$-recursive
sequence is $q$-regular in the sense of Allouche and Shallit and that a
$q$-linear representation of the sequence can be computed easily by using the
coefficients from the recurrence relations. Detailed asymptotic results for
$q$-recursive sequences are then obtained based on a general result on the
asymptotic analysis of $q$-regular sequences.

Three particular sequences are studied in detail: We discuss the asymptotic
behavior of the summatory functions of

  * •

Stern’s diatomic sequence,

  * •

the number of non-zero elements in some generalized Pascal’s triangle and

  * •

the number of unbordered factors in the Thue–Morse sequence.

For the first two sequences, our analysis even leads to precise formulæ
without error terms.

Clemens Heuberger

<EMAIL_ADDRESS>https://wwwu.aau.at/cheuberg, Alpen-Adria-
Universität Klagenfurt, Austria

Daniel Krenn

<EMAIL_ADDRESS>http://www.danielkrenn.at, Paris Lodron University of
Salzburg, Austria

Gabriel F. Lipnik

<EMAIL_ADDRESS>https://www.gabriellipnik.at, Graz University of
Technology, Austria

Support

Clemens Heuberger and Daniel Krenn are supported by the Austrian Science Fund
(FWF): P 28466-N35. Gabriel F. Lipnik is supported by the Austrian Science
Fund (FWF): W 1230.

Acknowledgment

The authors thank Helmut Prodinger for drawing their attention to the counting
function of unbordered factors in the Thue–Morse sequence.

2020 Mathematics Subject Classification

05A16; 11A63, 11B37, 30B50, 68Q45, 68R05, 68R15

Key words and phrases

regular sequence, recurrence relation, digital function, summatory function,
asymptotic analysis, Dirichlet series, Stern’s diatomic sequence, Pascal’s
triangle, Thue–Morse sequence

###### Contents

  1. 1 Introduction
  2. 2 Brief Introduction to $q$-Regular Sequences
  3. 3 $q$-Recursive Sequences
    1. 3.1 Definitions
    2. 3.2 Reduction to $q$-Regular Sequences in the General Case
    3. 3.3 Reduction to $q$-Regular Sequences in a Special Case
  4. 4 Asymptotics
    1. 4.1 Growth of Matrix Products
    2. 4.2 Asymptotics for Regular Sequences
    3. 4.3 Spectral Results in the General Case
    4. 4.4 Spectral Results in the Special Case
    5. 4.5 Functional Equation for the Dirichlet Series in the Special Case
  5. 5 Stern’s Diatomic Sequence
    1. 5.1 Introduction of the Sequence
    2. 5.2 Combinatorial Interpretations of the Sequence
    3. 5.3 Regularity and a Linear Representation
    4. 5.4 Asymptotics
  6. 6 Number of Non-Zero Entries in a Generalized Pascal’s Triangle
    1. 6.1 Introduction of the Sequence
    2. 6.2 Regularity and a Linear Representation
    3. 6.3 Full Asymptotics
  7. 7 Number of Unbordered Factors in the Thue–Morse Sequence
    1. 7.1 Introduction of the Sequence
    2. 7.2 Regularity and a Linear Representation
    3. 7.3 Joint Spectral Radius
    4. 7.4 Asymptotics
  8. 8 Proofs
    1. 8.1 Proofs of the Reductions to $q$-Regular Sequences in the General Case
    2. 8.2 Proof of the Reduction to $q$-Regular Sequences in the Special Case
    3. 8.3 Proofs of the Spectral Results
    4. 8.4 Proof of the Functional Equation in the Special Case

##  1 Introduction

####  $q$-Recursive Sequences.

We study a special class of recursively defined sequences, the so-called _$q$
-recursive sequences_. Here $q$ is an integer and at least $2$, and
$q$-recursive sequences are sequences which satisfy a specific type of
recurrence relation: Roughly speaking, every subsequence whose indices run
through a residue class modulo $q^{M}$ is a linear combination of subsequences
where for each of these subsequences, the indices run through a residue class
modulo $q^{m}$ for some $m<M$.

It turns out that this property is quite natural and many combinatorial
sequences are in fact $q$-recursive. A simple nontrivial example of such a
sequence111Throughout this paper, we let $\mathbb{N}$ denote the set of
positive integers and write $\mathbb{N}_{0}\coloneqq\mathbb{N}\cup\\{0\\}$.
Moreover, we write sequences in functional notation, i.e., we write a
(complex-valued) sequence $x$ as a function
$x\colon\mathbb{N}_{0}\to\mathbb{C}$, and as a consequence, the $n$th element
of the sequence is denoted by $x(n)$. In addition, we consider a vector of
complex-valued sequences $v=(x_{1},\dots,x_{D})^{\top}$ as a vector-valued
function $v\colon\mathbb{N}_{0}\to\mathbb{C}^{D}$, and its evaluation is
defined component-wise, i.e., $v(n)=(x_{1}(n),\dots,x_{D}(n))^{\top}$. is when
$h(n)$ is the largest power of $2$ less than or equal to $n$; see [34,
A053644]. Then we have $h(2n)=2h(n)$ and $h(2n+1)=2h(n)$ for $n\geq 1$ as well
as $h(1)=1$, so clearly $q=2$, and we set $M=1$ and $m=0$. This is because the
left-hand sides of the two recurrence relations contain $2^{1}n$ shifted by
$0$ and $1$, and because the right-hand sides only contain $2^{0}n$ (and no
shifts). Another example are divide-and-conquer recurrences, see [24, Equation
(1.2)].

####  $q$-Regular Sequences.

The concept of $q$-recursive sequences is related to $q$-regular sequences
introduced by Allouche and Shallit [1]. One definition of a $q$-regular
sequence $x$ is that every subsequence of the form $x(q^{j}n+r)$ can be
written as a linear combination of the same finite number of sequences; see
Section 2 for more details and a precise description. Again the sequence $h$
([34, A053644]) is an example, now for a $2$-regular sequence; it satisfies
$h(2^{j}n+r)=2^{j}h(n)$ for222By the definition of $q$-regular sequences as
given in Section 2, when representing every subsequence of the form
$h(2^{j}n+r)$ as a linear combination of the same finite number of sequences,
this needs to hold for all $n\geq 0$. In particular, this needs to hold for
$n=0$, which is not fulfilled in the example. However, this is only a minor
technical issue and can be fixed by adding some appropriate sequence to the
linear combination. Details about this repair are provided in Theorem 3.11.
$n\geq 1$, $j\geq 0$ and $0\leq r<2^{j}$, so every $h(2^{j}n+r)$ can be
written in terms of $h(n)$.

Equivalently, every $q$-regular sequence can be modeled by a $q$-linear
representation. Here $x(n)$ is one component of a vector $v(n)$, and there
exist matrices $A_{r}$ with $v(qn+r)=A_{r}v(n)$ for all $0\leq r<q$ and $n\geq
0$; see also Section 2.

#### Linear Representation of $q$-Recursive Sequences.

One main result of this paper is that every $q$-recursive sequence is indeed
$q$-regular; see Section 3.2. Even more can be said: Theorem 3.7 provides an
explicit $q$-linear representation of the sequence.

In Section 3.3, we significantly improve our results for a special case of
$q$-recursive sequences, namely where $M=m+1$.

#### Asymptotics of $q$-Recursive Sequences.

After exploring the concept of $q$-recursive sequences itself, we investigate
the asymptotic behavior of the summatory functions of $q$-recursive sequences,
i.e., sequences of partial sums. There exist explicit results for many
particular regular sequences and also some quite general results. Dumas [13]
as well as the first two authors of this paper together with Prodinger [22,
20] studied the asymptotics of $q$-regular sequences in general. The two works
[22, 20] will also be one of the main ingredients for obtaining the asymptotic
behavior of $q$-recursive sequences. We present details in Section 4. We
investigate an important special case where the asymptotic behavior can be
directly determined from the $q$-recursive sequence without constructing the
representation as a $q$-regular sequence.

#### Explicit Precise Asymptotics for Three Particular Sequences.

We also investigate three specific $q$-recursive sequences in-depth. In
particular, we derive asymptotic results for their summatory functions as well
as explain and illustrate the connection between these results and the fact
that the sequences are $q$-recursive. To be more specific, we analyze

  * •

Stern’s diatomic sequence in Section 5,

  * •

the number of non-zero entries in a generalized Pascal’s triangle in Section
6, and

  * •

the number of unbordered factors in the Thue–Morse sequence in Section 7.

For the first two sequences, our analysis even leads to precise formulæ
without error terms.

#### Proofs.

We finally complete this paper by giving proofs of our results; these are
collected in Section 8.

##  2 Brief Introduction to $q$-Regular Sequences

The concept of $q$-regular sequences333In the standard literature [1, 2],
these sequences are called $k$-regular instead of $q$-regular. was first
introduced by Allouche and Shallit [1] in 1992, and a lot of research on them
has been done since then; see for example Allouche and Shallit [2] and [3],
Bell [4], and Coons and Spiegelhofer [11].

The parameter $q$ acts as a base (or radix); therefore the term _digital
function_ arises in context of such sequences. We start by giving a
definition; see Allouche and Shallit [2].

Let $q\geq 2$ be a fixed integer and $x\colon\mathbb{N}_{0}\to\mathbb{C}$ be a
sequence444The results given in Sections 3.2 and 3.3 are valid for sequences
$x\colon\mathbb{N}_{0}\to R$, where $R$ is a commutative Noetherian ring.
However, in places where we speak about the asymptotics of a sequence, we
always consider complex-valued sequences.. Then $x$ is called _$q$ -regular_
if the complex vector space generated by its $q$-kernel

$\operatorname{\mathcal{K}}_{q}(x)\coloneqq\big{\\{}x\circ(n\mapsto
q^{j}n+r)\,\big{|}\,\mathopen{}\text{integers }j\geq 0,0\leq r<q^{j}\big{\\}}$

has finite dimension. In other words, a sequence $x$ is _$q$ -regular_ if
there are $\Delta\in\mathbb{N}_{0}$ and sequences $x_{1}$, $\dots$,
$x_{\Delta}$ such that for every $j\in\mathbb{N}_{0}$ and $0\leq r<q^{j}$
there exist $c_{1}$, $\dots$, $c_{\Delta}\in\mathbb{C}$ with

$x(q^{j}n+r)=\sum_{i=1}^{\Delta}c_{i}x_{i}(n)$

for all $n\geq 0$.

By Allouche and Shallit [1, Theorem 2.2], a complex-valued sequence $x$ is
$q$-regular if and only if there exist a vector-valued sequence
$v\colon\mathbb{N}_{0}\to\mathbb{C}^{D}$ for some $D\in\mathbb{N}$ whose first
component coincides with $x$ and matrices $A_{0}$, …, $A_{q-1}$ such that

$v(qn+r)=A_{r}v(n)$

holds for all $0\leq r<q$ and $n\geq 0$. If this is the case, the tuple
$(A_{0},\dots,A_{q-1},v)$ is called _$q$ -linear representation_ of $x$, and
$D$ is said to be its _dimension_.

At this point, we note that a $q$-linear representation
$(A_{0},\dots,A_{q-1},v)$ of a sequence $x$ immediately leads to an explicit
expression for $x(n)$ by induction: Let $d_{L-1}\ldots d_{0}$ be the $q$-ary
digit expansion of $n$. Then we have

$x(n)=e_{1}A_{d_{0}}\ldots A_{d_{L-1}}v(0),$ (2.1)

where $e_{1}=(1,0,\ldots,0)$. In particular, the $n$th element $x(n)$ can be
computed in $O(\log n)$ operations in $\mathbb{C}$.

The prototypical and probably best-known example of a $q$-regular sequence is
the binary sum of digits.

######  Example 2.1 (Binary Sum of Digits [34, A064547]).

For $n\in\mathbb{N}_{0}$, let $s(n)$ denote the number of ones in the binary
expansion of $n$. Then we clearly have

$s(2n)=s(n)\mbox{\quad and\quad}s(2n+1)=s(n)+1$ (2.2)

for all $n\geq 0$ and $s(0)=0$. By induction we obtain

$s(2^{j}n+r)=s(n)+s(r)\cdot 1$

for all $n\geq 0$, $j\geq 0$ and $0\leq r<2^{j}$. This means that the complex
vector space generated by the kernel $\operatorname{\mathcal{K}}_{q}(s)$ is
also generated by $s$ and $n\mapsto 1$ and thus, the sequences $s$ is
$2$-regular.

A $2$-linear representation $(A_{0},A_{1},v)$ of $s$ is given by

$A_{0}=\begin{pmatrix}1&0\\\ 0&1\end{pmatrix},\quad
A_{1}=\begin{pmatrix}1&1\\\ 0&1\end{pmatrix}\mbox{\quad
and\quad}v=\begin{pmatrix}s\\\ n\mapsto 1\end{pmatrix},$

where the corresponding recurrence relations $v(2n)=A_{0}v(n)$ as well as
$v(2n+1)=A_{1}v(n)$ can be checked easily by using (2.2).

##  3 $q$-Recursive Sequences

In this section, we introduce the concept of $q$-recursive sequences,
investigate how linear representations of these sequences look like and
thereby conclude that these sequences are $q$-regular. We will also
investigate a more restricted set-up. This special case (as we will call it
from now on in contrast to the general case) is important; two instances will
be discussed in Sections 6 and 7.

###  3.1 Definitions

We start by giving the definition of our sequences of interest.

######  Definition 3.2 ($q$-Recursive Sequence).

Let $q\geq 2$, $M>m\geq 0$, $\ell\leq u$ and
$n_{0}\geq\max\\{-\ell/q^{m},0\\}$ be fixed integers. Let $x$ be a sequence.

If there are constants $c_{s,k}\in\mathbb{C}$ for all $0\leq s<q^{M}$ and
$\ell\leq k\leq u$ such that

$x(q^{M}n+s)=\smashoperator[]{\sum_{\ell\leq k\leq u}^{}}c_{s,k}\,x(q^{m}n+k)$
(3.1)

holds for all $n\geq n_{0}$ and $0\leq s<q^{M}$, then we say that the sequence
$x$ is _$q$ -recursive with offset $n_{0}$, exponents $M$ and $m$, index shift
bounds $\ell$ and $u$, and coefficients $(c_{s,k})_{0\leq s<q^{M},\ell\leq
k\leq u}$_.

We use the convention that if any of the parameters $q$, $n_{0}$, $M$, $m$,
$\ell$, $u$, $(c_{s,k})_{0\leq s<q^{M},\ell\leq k\leq u}$ is not mentioned for
a recursive sequence, then we assume that a value of this parameter exists
such that the sequence is recursive with this value of the parameter.

The sequence where $h(n)$ is the largest power of $2$ less than or equal to
$n$ ([34, A053644]), that was mentioned in the introduction, is indeed a
$2$-recursive sequence with offset $1$, as $h(2n)=2h(n)$ and $h(2n+1)=2h(n)$
hold for $n\geq 1$. On the other hand, the binary sum of digits as introduced
in Example 2.1 does not directly555While the binary sum of digits $s$ does not
directly fit into the framework with $M=1$ and $m=0$, it is a $2$-recursive
sequence with exponents $M=2$ and $m=1$, since the recurrence relations
$s(4n)=s(2n)$, $s(4n+1)=s(2n+1)$, $s(4n+2)=s(2n+1)$ and
$s(4n+3)=-s(2n)+2s(2n+1)$ follow from (2.2) for all $n\geq 0$. This means that
in this and similar cases we can get rid of the inhomogeneity by increasing
the exponents. fit into this framework, because the constant sequence appears
on the right-hand side; see (2.2). For a discussion of such inhomogeneous
$q$-recursive sequences we refer to Corollary 3.13.

Before considering a slightly more involved example, we clarify the role of
the restriction on $n_{0}$.

######  Remark 3.3.

The condition $n_{0}\geq\max\\{-\ell/q^{m},0\\}$ in Definition 3.2 is
necessary because for $n=n_{0}$, (3.1) reduces to

$x(q^{M}n_{0}+s)=\smashoperator[]{\sum_{\ell\leq k\leq
u}^{}}c_{s,k}\,x(q^{m}n_{0}+k),$

and so the smallest argument of $x$ on the right-hand side is
$q^{m}n_{0}+\ell$, which is non-negative by the given condition and therefore
indeed a valid argument.

######  Example 3.4 (Odd Entries in Pascal’s Triangle [34, A006046]).

Let $p(n)$ be the number of odd entries in the first $n$ rows of Pascal’s
triangle. The first few elements are given in Table 3.1.

$n$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$
---|---|---|---|---|---|---|---|---|---|---|---
$p(n)$ | $0$ | $1$ | $3$ | $5$ | $9$ | $11$ | $15$ | $19$ | $27$ | $29$ | $33$
Table 3.1: First few elements of $p$

By Lucas’ theorem on binomial coefficients modulo a prime, the number of odd
entries in row $n$ of Pascal’s triangle is given by $2^{s(n)}$, where $s(n)$
is the binary sum of digits of $n$; see also Fine [15, Theorem 2]. This
implies that

$\displaystyle p(2n)=\smashoperator[]{\sum_{0\leq k<2n}^{}}2^{s(k)}$
$\displaystyle=\smashoperator[]{\sum_{0\leq
k<n}^{}}2^{s(2k)}+\smashoperator[]{\sum_{0\leq k<n}^{}}2^{s(2k+1)}$
$\displaystyle\stackrel{{\scriptstyle\stackrel{{\scriptstyle\text{\eqref{eq:binary-
sum-of-digits}}}}{{\downarrow}}}}{{=}}\smashoperator[]{\sum_{0\leq
k<n}^{}}2^{s(k)}+\smashoperator[]{\sum_{0\leq
k<n}^{}}2^{s(k)+1}=p(n)+2p(n)=3p(n)$

as well as

$\displaystyle p(2n+1)=\smashoperator[]{\sum_{0\leq k<2n+1}^{}}2^{s(k)}$
$\displaystyle=\smashoperator[]{\sum_{0\leq k\leq
n}^{}}2^{s(2k)}+\smashoperator[]{\sum_{0\leq k<n}^{}}2^{s(2k+1)}$
$\displaystyle\stackrel{{\scriptstyle\stackrel{{\scriptstyle\text{\eqref{eq:binary-
sum-of-digits}}}}{{\downarrow}}}}{{=}}\smashoperator[]{\sum_{0\leq k\leq
n}^{}}2^{s(k)}+\smashoperator[]{\sum_{0\leq k<n}^{}}2^{s(k)+1}=p(n+1)+2p(n)$

hold for all $n\geq 0$. Thus, the sequence $p$ is $2$-recursive with exponents
$M=1$ and $m=0$, index shift bounds $\ell=0$ and $u=1$, and offset $n_{0}=0$.

From Allouche and Shallit [1, Example 14 and Theorem 3.1], we know that the
sequence $p$ is $2$-regular as well. This is no coincidence: In the following,
we will show that each $q$-recursive sequence is $q$-regular. Furthermore, if
the recurrence relations in (3.1) are known, we can even give an explicit
$q$-linear representation of $x$.

In analogy to Definition 3.2, we also introduce _$q$ -regular sequences with
offset_.

######  Definition 3.5 ($q$-Regular Sequence with Offset).

Let $q\geq 2$ and $n_{0}\geq 0$ be fixed integers. A sequence $x$ is said to
be _$q$ -regular with offset $n_{0}$_ if there exist a vector-valued sequence
$v\colon\mathbb{N}_{0}\to\mathbb{C}^{D}$ for some $D\in\mathbb{N}$ whose first
component coincides with $x$ and matrices $A_{0}$, …, $A_{q-1}$ such that
$v(qn+r)=A_{r}v(n)$ holds for all $0\leq r<q$ and $n\geq n_{0}$. In this case,
we say that $(A_{0},\ldots,A_{q-1},v)$ is a _$q$ -linear representation with
offset $n_{0}$_ of $x$.

######  Remark 3.6.

A $q$-regular sequence with offset $0$ is $q$-regular in the usual sense.
Likewise, every $q$-linear representation with offset $0$ is a $q$-linear
representation as introduced in Section 2.

###  3.2 Reduction to $q$-Regular Sequences in the General Case

It turns out that every $q$-recursive sequence with any offset is indeed
$q$-regular (Corollary 3.12). This is an implication of the following two
results:

  * •

Theorem 3.7 explicitly constructs a $q$-linear representation with offset
$n_{1}$ of $q$-recursive sequences with offset $n_{0}$, where
$n_{1}\in\mathbb{N}$ is explicitly given. This means that such sequences are
$q$-regular with offset $n_{1}$.

  * •

Theorem 3.11 states that every $q$-regular sequence with some offset is
$q$-regular (without offset) as well. Also here, an explicit $q$-linear
representation of $x$ is given.

######  Theorem 3.7.

Let $x$ be a $q$-recursive sequence with offset $n_{0}$, exponents $M$ and $m$
and index shift bounds $\ell$ and $u$. Furthermore, set666We use Iverson’s
convention: For a statement $S$, we set $\llbracket S\rrbracket=1$ if $S$ is
true and $0$ otherwise; see also Graham, Knuth and Patashnik [19, p. 24].

$\displaystyle\ell^{\prime}$
$\displaystyle\coloneqq\bigg{\lfloor}\frac{(\ell+1)q^{M-m}-q^{M}}{q^{M-m}-1}\bigg{\rfloor}\llbracket\ell<0\rrbracket$
(3.2a) and $\displaystyle u^{\prime}$ $\displaystyle\coloneqq
q^{m}-1+\bigg{\lceil}\frac{uq^{M-m}}{q^{M-m}-1}\bigg{\rceil}\llbracket
u>0\rrbracket.$ (3.2b)

Then $x$ is $q$-regular with offset
$n_{1}=n_{0}-\lfloor\ell^{\prime}/q^{M}\rfloor$, and a $q$-linear
representation $(A_{0},\dots,A_{q-1},v)$ with offset $n_{1}$ of $x$ is given
as follows:

  1. (a)

The vector-valued sequence $v$ is given in block form by

$v=\begin{pmatrix}v_{0}\\\ \vdots\\\ v_{M-1}\end{pmatrix},$ (3.3)

where the blocks are of the following form: For $0\leq j<m$, the block $v_{j}$
has the form

$v_{j}=\begin{pmatrix}x\circ(n\mapsto q^{j}n)\\\ \vdots\\\ x\circ(n\mapsto
q^{j}n+q^{j}-1)\end{pmatrix},$ (3.4a) and for $m\leq j<M$, the block $v_{j}$
has the form777We set $x(n)=0$ for $n<0$ to ensure that all blocks are well-
defined. By the choice of $n_{1}$, this does not have any factual
consequences. $v_{j}=\begin{pmatrix}x\circ(n\mapsto q^{j}n+\ell^{\prime})\\\
\vdots\\\ x\circ(n\mapsto q^{j}n+q^{j}-q^{m}+u^{\prime})\end{pmatrix}.$ (3.4b)

  2. (b)

The matrices $A_{0}$, …, $A_{q-1}$ of the $q$-linear representation with
offset $n_{1}$ can be computed by using the coefficients in (3.1); an explicit
formula for the rows of these matrices is given in (8.8).

The linear representation $(A_{0},\ldots,A_{q-1},v)$ does not depend on the
offset $n_{0}$.

######  Remark 3.8.

  1. 1.

We easily verify that $\ell^{\prime}\leq 0$ holds and it is clear that
$u^{\prime}\geq q^{m}-1\geq 0$. Thus $\ell^{\prime}\leq u^{\prime}$. This
implies that the blocks $v_{j}$ for $m\leq j<M$ in (3.4b) are indeed non-
empty.

  2. 2.

It is easy to check that $x$ itself is a component of $v$. For $m=0$, this is
due to the fact that we have $\ell^{\prime}\leq 0\leq u^{\prime}$. However, it
can happen that $x$ is not the _first component_ of $v$ (as it is required for
a linear representation). Then a simple permutation of the components of $v$
brings $x$ to its first component.

  3. 3.

The dimension of the $q$-linear representation is

$\frac{q^{M}-1}{q-1}+(M-m)\bigl{(}u^{\prime}-\ell^{\prime}-q^{m}+1\bigr{)},$

which is possibly very big. However, we can always apply a minimization
algorithm in order to decrease the dimension of the linear representation as
far as possible. Such an algorithm is presented in Berstel and Reutenauer [5,
Chapter 2] for recognizable series, but can be applied on regular sequences as
well; see [21]. SageMath [36] provides an implementation of this minimization
algorithm.

  4. 4.

The statement of Theorem 3.7 for $M=1$ and $m=n_{0}=0$ is mentioned by the
first two authors of this article in [20, Remark 5.1].

In order to put the main aspects of the previous result across, we present two
examples: The first one is a simple continuation of Example 3.4, and the
second one discusses a $q$-recursive sequence with more involved parameters.
While the latter might not seem to be very natural, it is an intentionally
made choice to keep things illustrative and comprehensible. For further
natural combinatorial examples we refer to Sections 5, 6 and 7.

######  Example 3.9 (Odd Entries in Pascal’s Triangle, continued).

Let $p(n)$ again be the number of odd entries in the first $n$ rows of
Pascal’s triangle. As already mentioned (Example 3.4), $p$ is $2$-recursive
with exponents $M=1$ and $m=0$ and index shift bounds $\ell=0$ and $u=1$ as
well as

$p(2n)=\hbox{\pagecolor{SpringGreen}3}p(n)+\hbox{\pagecolor{LimeGreen}0}p(n+1)\mbox{\quad
and\quad}p(2n+1)=\hbox{\pagecolor{Goldenrod}2}p(n)+\hbox{\pagecolor{Dandelion}1}p(n+1)$
(3.5)

for all $n\geq 0$. Due to Theorem 3.7, $p$ is also $2$-regular (with offset
$n_{1}=0$) and a $2$-regular representation of $p$ can be found as follows. We
have $\ell^{\prime}=0$ and $u^{\prime}=2$, and it is due to the relation
$m=M-1=0$ that the vector $v$ only consists of one block, namely

$v=v_{M-1}=v_{0}=\begin{pmatrix}p\\\ p\circ(n\mapsto n+1)\\\ p\circ(n\mapsto
n+2)\end{pmatrix}.$

Moreover, we can determine the matrices $A_{0}$ and $A_{1}$ in various ways:
By (8.8), these matrices are

$A_{0}=\begin{pmatrix}\hbox{\pagecolor{SpringGreen}3}&\hbox{\pagecolor{LimeGreen}0}&0\\\
\hbox{\pagecolor{Goldenrod}2}&\hbox{\pagecolor{Dandelion}1}&0\\\
0&\hbox{\pagecolor{SpringGreen}3}&\hbox{\pagecolor{LimeGreen}0}\end{pmatrix}\mbox{\quad
and\quad}A_{1}=\begin{pmatrix}\hbox{\pagecolor{Goldenrod}2}&\hbox{\pagecolor{Dandelion}1}&0\\\
0&\hbox{\pagecolor{SpringGreen}3}&\hbox{\pagecolor{LimeGreen}0}\\\
0&\hbox{\pagecolor{Goldenrod}2}&\hbox{\pagecolor{Dandelion}1}\end{pmatrix}.$

However, these matrices can also be obtained in an ad hoc fashion, namely by
inserting $2n$ and $2n+1$ into $v$ and then component-wise applying (3.5). For
example, let us take a look at the third row of $A_{0}$: We have to consider
the third component of $v$, which is $p\circ(n\mapsto n+2)$. We insert $2n$,
which results in $p\circ(n\mapsto 2n+2)$, and we obtain

$p\circ(n\mapsto 2n+2)=p\circ(n\mapsto
2(n+1))=\hbox{\pagecolor{SpringGreen}3}p\circ(n\mapsto
n+1)+\hbox{\pagecolor{LimeGreen}0}p\circ(n\mapsto n+2)$

by (3.5). Thus, we have a $3$ in the second column, because $p\circ(n\mapsto
n+1)$ is the second component of $v$, and a $0$ in the third column, because
$p\circ(n\mapsto n+2)$ is the third component of $v$. Generally speaking, the
rows of $A_{r}$ that correspond to the last block $v_{M-1}$ always consist of
shifted copies of the coefficients in the recurrence relations.

The “step” between the second row and the third row of $A_{0}$ and between the
first row and the second row of $A_{1}$ is caused by the following fact: After
inserting $2n$ or $2n+1$, it can happen that the remainder is too large to
apply the given recurrence relations directly. For instance, this was the case
when determining the third row of $A_{0}$ above: After inserting $2n$, we have
obtained $p\circ(n\mapsto 2n+2)$, and we had to rewrite this to
$p\circ(n\mapsto 2(n+1))$ to be able to apply (3.5). This increase of the
argument by $1$ causes the shift of the entries in the matrix to the right by
$1$. For a more detailed description of this effect, we refer to the two
different cases in Part 3 of the proof of Theorem 3.7 in Section 8.1 and to
(8.8).

Note that the dimension of this linear representation is not minimal since the
sequence $p\circ(n\mapsto n+2)$ can be omitted. This is due to the following
two facts: The third columns of $A_{0}$ and $A_{1}$ correspond to
$p\circ(n\mapsto n+2)$. All non-zero elements of these columns are in the last
row, which again corresponds to $p\circ(n\mapsto n+2)$. This reduction is
possible because the coefficient of $p(n+1)$ in the left recurrence relation
of (3.5) is zero.

######  Example 3.10.

Consider the $2$-recursive sequence $x$ with exponents $M=3$ and $m=1$ given
by the recurrence relations

$\begin{split}x(8n)&=-\phantom{0}1x(2n-1)+\phantom{0}0x(2n)+\phantom{0}1x(2n+1),\\\
x(8n+1)&=-11x(2n-1)+10x(2n)+11x(2n+1),\\\
x(8n+2)&=-21x(2n-1)+20x(2n)+21x(2n+1),\\\
x(8n+3)&=-31x(2n-1)+30x(2n)+31x(2n+1),\\\
x(8n+4)&=-41x(2n-1)+40x(2n)+41x(2n+1),\\\
x(8n+5)&=-51x(2n-1)+50x(2n)+51x(2n+1),\\\
x(8n+6)&=-61x(2n-1)+60x(2n)+61x(2n+1),\\\
x(8n+7)&=-71x(2n-1)+70x(2n)+71x(2n+1),\end{split}$ (3.6)

for all $n\geq 0$. So for the sake of recognition, the coefficients
$(c_{s,k})_{0\leq s<8,-1\leq k\leq 1}$ are given by $c_{s,k}=(-1)^{\llbracket
k<0\rrbracket}10s+k$. The index shift bounds of $x$ are $\ell=-1$ and $u=1$,
and its offset is $n_{0}=0$. With the notation of Theorem 3.7, we further find
$\ell^{\prime}=-3$ and $u^{\prime}=3$.

Due to Theorem 3.7, $x$ is $2$-regular with offset $n_{1}=1$, and by (3.4) and
(8.8), a $2$-linear representation with offset $n_{1}=1$ of $x$ is given by
$(A_{0},A_{1},v)$ with

$v={\small\begin{pmatrix}x\\\ x\circ(n\mapsto 2n-3)\\\ x\circ(n\mapsto
2n-2)\\\ \vdots\\\ x\circ(n\mapsto 2n+3)\\\ x\circ(n\mapsto 4n-3)\\\
x\circ(n\mapsto 4n-2)\\\ \vdots\\\ x\circ(n\mapsto 4n+5)\\\
\end{pmatrix}{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>6.75ptv_{0}\\\ \mathclap{\left.\vphantom{\begin{matrix}x\\\ x\\\ \vdots\\\
x\end{matrix}}\right\\}}\hskip 6.75ptv_{1}\\\
\mathclap{\left.\vphantom{\begin{matrix}x\\\ x\\\ \vdots\\\
x\end{matrix}}\right\\}}\hskip 6.75ptv_{2}\end{matrix}}}$

as well as

$A_{0}=\left(\setcounter{MaxMatrixCols}{17}\begin{smallmatrix}0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0\\\
0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0\\\ 0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0\\\
0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0\\\ 0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0\\\
0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0\\\ 0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0\\\
0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0\\\ 0&\leavevmode\hbox to4.67pt{\vbox
to4.67pt{\pgfpicture\makeatletter\hbox{\hskip 2.33311pt\lower-2.33311pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}-51&50&51&0&0&0&0&0&0&0&0&0&0&0&0&0\\\
0&-61&60&61&0&0&0&0&0&0&0&0&0&0&0&0&0\\\
0&-71&70&71&0&0&0&0&0&0&0&0&0&0&0&0&0\\\ 0&0&0&-1&0&1&0&0&0&0&0&0&0&0&0&0&0\\\
0&0&0&-11&10&11&0&0&0&0&0&0&0&0&0&0&0\\\
0&0&0&-21&20&21&0&0&0&0&0&0&0&0&0&0&0\\\
0&0&0&-31&30&31&0&0&0&0&0&0&0&0&0&0&0\\\
0&0&0&-41&40&41&0&0&0&0&0&0&0&0&0&0&0\\\ 0&0&0&-51&50&51&0&0\leavevmode\hbox
to4.67pt{\vbox to4.67pt{\pgfpicture\makeatletter\hbox{\hskip
2.33311pt\lower-2.33311pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}&0&0&0&0&0&0&0&0&0\end{smallmatrix}\right)\leavevmode\hbox
to4.8pt{\vbox to10.8pt{\pgfpicture\makeatletter\hbox{\hskip
2.4pt\lower-2.4pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ { {}{}{}{}{}}{}{}{}{}{{}}{} {
{}{}{}{}{}}{}{}{}{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0.88,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.88,0}\pgfsys@color@cmyk@stroke{0.91}{0}{0.88}{0.12}\pgfsys@invoke{
}\pgfsys@color@cmyk@fill{0.91}{0}{0.88}{0.12}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0.88,0}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}{}\pgfsys@moveto{-2.0pt}{8.00002pt}\pgfsys@moveto{-2.0pt}{8.00002pt}\pgfsys@lineto{-2.0pt}{-2.0pt}\pgfsys@lineto{2.0pt}{-2.0pt}\pgfsys@lineto{2.0pt}{8.00002pt}\pgfsys@closepath\pgfsys@moveto{2.0pt}{-2.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\mbox{\quad
and\quad}A_{1}=\left(\setcounter{MaxMatrixCols}{17}\begin{smallmatrix}0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0\\\
0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0\\\ 0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0\\\
0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0\\\ 0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0\\\
0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0\\\ 0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0\\\
0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1\\\ 0&\leavevmode\hbox to4.67pt{\vbox
to4.67pt{\pgfpicture\makeatletter\hbox{\hskip 2.33311pt\lower-2.33311pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}0&0&-11&10&11&0&0&0&0&0&0&0&0&0&0&0\\\
0&0&0&-21&20&21&0&0&0&0&0&0&0&0&0&0&0\\\
0&0&0&-31&30&31&0&0&0&0&0&0&0&0&0&0&0\\\
0&0&0&-41&40&41&0&0&0&0&0&0&0&0&0&0&0\\\
0&0&0&-51&50&51&0&0&0&0&0&0&0&0&0&0&0\\\
0&0&0&-61&60&61&0&0&0&0&0&0&0&0&0&0&0\\\
0&0&0&-71&70&71&0&0&0&0&0&0&0&0&0&0&0\\\ 0&0&0&0&0&-1&0&1&0&0&0&0&0&0&0&0&0\\\
0&0&0&0&0&-11&10&11\leavevmode\hbox to4.67pt{\vbox
to4.67pt{\pgfpicture\makeatletter\hbox{\hskip 2.33311pt\lower-2.33311pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}&0&0&0&0&0&0&0&0&0\end{smallmatrix}\right).\leavevmode\hbox
to4.8pt{\vbox to10.8pt{\pgfpicture\makeatletter\hbox{\hskip
2.4pt\lower-2.4pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ { {}{}{}{}{}}{}{}{}{}{{}}{} {
{}{}{}{}{}}{}{}{}{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0.68,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0,0}\pgfsys@color@cmyk@stroke{0}{0.87}{0.68}{0.32}\pgfsys@invoke{
}\pgfsys@color@cmyk@fill{0}{0.87}{0.68}{0.32}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0.68,0,0}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}{}\pgfsys@moveto{-2.0pt}{8.00002pt}\pgfsys@moveto{-2.0pt}{8.00002pt}\pgfsys@lineto{-2.0pt}{-2.0pt}\pgfsys@lineto{2.0pt}{-2.0pt}\pgfsys@lineto{2.0pt}{8.00002pt}\pgfsys@closepath\pgfsys@moveto{2.0pt}{-2.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$

Again, the matrices can also be obtained ad hoc, by inserting $2n$ and $2n+1$
into the components and, if needed, component-wise applying the relations of
(3.6). For example, the fourth row of $A_{1}$ corresponds to $x\circ(n\mapsto
2n-1)$, i.e., the fourth component of $v$. Inserting $2n+1$ yields
$x\circ(n\mapsto 2(2n+1)-1)=x\circ(n\mapsto 4n+1)$, which itself is the $13$th
component of $v$. Thus, we have a $1$ in the $13$th column in the fourth row
of $A_{1}$.

The “interesting” part of the matrices $A_{0}$ and $A_{1}$ is given by entries
in rows corresponding to $v_{M-1}=v_{2}$ and columns corresponding to
$v_{m}=v_{1}$. It is marked by the green and red boxes, respectively, and the
entries can be obtained exactly as described in the previous example. Here the
application of (3.6) is indeed needed and again leads to a block of shifted
copies of the coefficients in the recurrence relations. Also here, one can see
the “steps” in the matrices that were described in Example 3.9.

Up to now, we have reduced $q$-recursive sequences to $q$-regular sequences
with some offset. Next, we get rid of this offset; Allouche and Shallit
implicitly do such an offset correction for offset $1$ in the proof of [1,
Lemma 4.1].

######  Theorem 3.11.

Let $x$ be a $q$-regular sequence with offset $n_{0}$, and let
$(A_{0},\ldots,A_{q-1},v)$ be a $q$-linear representation with offset $n_{0}$
of $x$. Then $x$ is $q$-regular and a $q$-linear representation
$(\widetilde{A}_{0},\dots,\widetilde{A}_{q-1},\widetilde{v})$ of $x$ is given
as follows:

  1. (a)

The vector-valued sequence $\widetilde{v}$ is given in block form by

$\widetilde{v}=\begin{pmatrix}v\\\ \delta_{0}\\\ \vdots\\\
\delta_{n_{0}-1}\end{pmatrix},$ (3.7)

where $\delta_{k}\colon\mathbb{N}_{0}\to\mathbb{C}$ is defined by
$\delta_{k}(n)=\llbracket n=k\rrbracket$ for all $0\leq k<n_{0}$ and $n\geq
0$.

  2. (b)

Let $D\in\mathbb{N}$ be the dimension of $v$. Moreover, for $0\leq r<q$ and
$0\leq k<n_{0}$, let888We set $x(n)=0$ for $n<0$ to ensure that all vectors
are defined. Other definitions of values for negative arguments are possible,
but would result in other values for $W_{r}$. $w_{r,k}\coloneqq
v(qk+r)-A_{r}v(k)\in\mathbb{C}^{D}$, and let $W_{r}$ be the $D\times n_{0}$
matrix which has columns $w_{r,0}$, …, $w_{r,n_{0}-1}$. Then for all $0\leq
r<q$, the matrix $\widetilde{A}_{r}$ is given in block form by

$\widetilde{A}_{r}=\begin{pmatrix}A_{r}&W_{r}\\\ 0&J_{r}\end{pmatrix},$ (3.8)

where $J_{r}\in\\{0,1\\}^{n_{0}\times n_{0}}$ is the matrix defined by

$J_{r}\coloneqq\bigl{(}\llbracket
jq=k-r\rrbracket\bigr{)}_{\begin{subarray}{c}0\leq k<n_{0}\\\ 0\leq
j<n_{0}\end{subarray}}.$ (3.9)

The matrix $J_{r}$ is a lower triangular matrix with diagonal

$\operatorname{diag}(J_{r})=\bigl{(}\llbracket
r=0\rrbracket,0,\dots,0\bigr{)}.$

######  Corollary 3.12.

Every $q$-recursive sequence $x$ with any offset is $q$-regular and a
$q$-linear representation of $x$ is given as the combination of the explicit
constructions of the $q$-linear representations from Theorem 3.7 and Theorem
3.11.

While Section 3 up to this point (in particular Definition 3.2) considered
homogeneous recursive sequences, also inhomogeneities can occur. An example
is, as already mentioned, the binary sum of digits, where the constant
sequence appears. In the following corollary, we deal with such inhomogeneous
recursive sequences.

######  Corollary 3.13.

Let $q\geq 2$, $M>m\geq 0$, $\ell\leq u$ and
$n_{0}\geq\max\\{-\ell/q^{m},0\\}$ be fixed integers. Furthermore, let $x$ be
a sequence such that for all $0\leq s<q^{M}$ there exist $q$-regular sequences
$g_{s}$ and constants $c_{s,k}\in\mathbb{C}$ for $\ell\leq k\leq u$ with

$x(q^{M}n+s)=\smashoperator[]{\sum_{\ell\leq k\leq
u}^{}}c_{s,k}\,x(q^{m}n+k)+g_{s}(n)$ (3.10)

for all $n\geq n_{0}$.

Then $x$ is $q$-regular and a $q$-linear representation of $x$ can be
constructed straightforwardly by combining the explicit constructions of the
$q$-linear representations from Theorem 3.7 and Theorem 3.11 with $q$-linear
representations of shifted versions of the sequences $g_{s}$.

######  Remark 3.14.

The construction of a $q$-linear representation of a $q$-recursive sequence
(given by recurrence relations as in (3.1) or in (3.10)) with offset has been
included [26] in SageMath [36].

###  3.3 Reduction to $q$-Regular Sequences in a Special Case

We now study a specific case of $q$-recursive sequences, namely $q$-recursive
sequences with exponents $M=m+1$ and $m$ and index shift bounds $\ell=0$ and
$u=q^{m}-1$ for some $m\in\mathbb{N}_{0}$. The study of this case is well-
motivated: First of all, it will turn out in Sections 6 and 7 that this choice
of parameters is quite natural, i.e., we will see examples where subsequences
of indices modulo $q^{m+1}$ equal linear combinations of subsequences of
indices modulo $q^{m}$. Moreover, we can give the matrices of the linear
representation in a simpler form than in Theorem 3.7, and the upper bound
$u^{\prime}$ can be improved significantly. Finally, we show that the
asymptotics of the summatory functions of this special case of sequences can
be obtained directly from the recurrence relations in (3.1), without knowing a
linear representation of the sequence explicitly.

Note that in this section we assume the offset to be $n_{0}=0$, mainly for the
sake of readability. However, we want to emphasize that all results can be
stated for arbitrary offset $n_{0}\in\mathbb{N}_{0}$ as well, using Theorem
3.11.

We start by giving an analogon of Theorem 3.7 for our special case.

######  Theorem 3.15.

Let $x$ be a $q$-recursive sequence with exponents $M=m+1$ and $m$ and index
shift bounds $\ell=0$ and $u=q^{m}-1$ and coefficients $(c_{s,k})_{0\leq
s<q^{m+1},0\leq k<q^{m}}$. We define the matrices

$B_{r}=(c_{rq^{m}+d,k})_{\begin{subarray}{c}0\leq d<rq^{m}\\\ 0\leq
k<q^{m}\end{subarray}}$ (3.11)

for $0\leq r<q$. Then $x$ is $q$-regular and a $q$-linear representation
$(A_{0},\dots,A_{q-1},v)$ of $x$ is given as follows:

  1. (a)

The vector-valued sequence $v$ is given in block form by

$v=\begin{pmatrix}v_{0}\\\ \vdots\\\ v_{m}\end{pmatrix},$ (3.12)

where for $0\leq j\leq m$, the block $v_{j}$ has the form

$v_{j}=\begin{pmatrix}x\circ(n\mapsto q^{j}n)\\\ \vdots\\\ x\circ(n\mapsto
q^{j}n+q^{j}-1)\end{pmatrix}.$ (3.13)

  2. (b)

For $0\leq r<q$, the matrices $A_{r}$ are given in block form by

$A_{r}=\begin{pmatrix}J_{r0}&J_{r1}\\\ 0&B_{r}\end{pmatrix},$ (3.14)

where $J_{r0}\in\\{0,1\\}^{\frac{q^{m}-1}{q-1}\times\frac{q^{m}-1}{q-1}}$ and
$J_{r1}\in\\{0,1\\}^{\frac{q^{m}-1}{q-1}\times q^{m}}$. Furthermore, for
$0\leq r<q$, the matrices $J_{r0}$ are upper triangular matrices with zeros on
the diagonal, and the matrices $J_{r0}$ and $J_{r1}$ are given explicitly by
the first case of (8.8) (with $u^{\prime}$ replaced by $q^{m}-1$).

######  Remark 3.16.

  1. 1.

The structure of $v$ is the same as in Theorem 3.7. In particular, the blocks
$v_{j}$ with $0\leq j<m$ coincide with the blocks $v_{j}$ from Theorem 3.7
given in (3.4a).

  2. 2.

The matrices $J_{r0}$ and $J_{r1}$ can be decomposed into blocks of identity
matrices and zero matrices of smaller dimensions, which are horizontally
shifted depending on $r$. For an illustration we refer to Example 3.17.

  3. 3.

The last component of $v$ is $x\circ(n\mapsto q^{m}n+q^{m}-1)$ in contrast to
$x\circ(n\mapsto q^{m}n+u^{\prime})$ when using Theorem 3.7. This means that
using Theorem 3.15 leads to a linear representation whose dimension is
$\frac{q^{m+1}-q}{q-1}$ less than the dimension achieved by Theorem 3.7.

  4. 4.

In the case $m=0$, only rather special sequences can be handled by Theorem
3.15. For instance, for $q=2$ and $m=0$, only sequences of the form
$x(n)=x(0)a^{s(n)}$, where $s(n)$ is the binary sum of digits of $n$ and $a$
is some constant, fulfill the assumptions of this theorem. For all other
$q$-recursive sequences with $m=0$, Theorem 3.7 has to be used.

The following example will allow us to illustrate Theorem 3.15. For the sake
of simplicity, we again choose an artificial example.

######  Example 3.17.

Let us study the $2$-recursive sequence $x$ with exponents $M=3$ and $m=2$
given by the recurrence relations

$\displaystyle f(8n)$ $\displaystyle=f(4n)+f(4n+1)+f(4n+2)+f(4n+3),$
$\displaystyle f(8n+1)$ $\displaystyle=f(4n)+f(4n+1)+f(4n+2)+f(4n+3),$
$\displaystyle f(8n+2)$ $\displaystyle=f(4n)+f(4n+1)+f(4n+2)+f(4n+3),$
$\displaystyle f(8n+3)$ $\displaystyle=f(4n)+f(4n+1)+f(4n+2)+f(4n+3),$
$\displaystyle f(8n+4)$ $\displaystyle=2f(4n)+2f(4n+1)+2f(4n+2)+2f(4n+3),$
$\displaystyle f(8n+5)$ $\displaystyle=2f(4n)+2f(4n+1)+2f(4n+2)+2f(4n+3),$
$\displaystyle f(8n+6)$ $\displaystyle=2f(4n)+2f(4n+1)+2f(4n+2)+2f(4n+3),$
$\displaystyle f(8n+7)$ $\displaystyle=2f(4n)+2f(4n+1)+2f(4n+2)+2f(4n+3)$

for all $n\geq 0$. Then we have

$B_{0}=\begin{pmatrix}\leavevmode\hbox to6.67pt{\vbox
to6.67pt{\pgfpicture\makeatletter\hbox{\hskip 3.33301pt\lower-3.33301pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}1&1&1&1\\\ 1&1&1&1\\\
1&1&1&1\\\ 1&1&1&1\leavevmode\hbox to6.67pt{\vbox
to6.67pt{\pgfpicture\makeatletter\hbox{\hskip 3.33301pt\lower-3.33301pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\\\
\end{pmatrix}\mbox{\quad and\quad}B_{1}=\begin{pmatrix}\leavevmode\hbox
to6.67pt{\vbox to6.67pt{\pgfpicture\makeatletter\hbox{\hskip
3.33301pt\lower-3.33301pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}2&2&2&2\\\ 2&2&2&2\\\
2&2&2&2\\\ 2&2&2&2\leavevmode\hbox to6.67pt{\vbox
to6.67pt{\pgfpicture\makeatletter\hbox{\hskip 3.33301pt\lower-3.33301pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\\\
\end{pmatrix}.\leavevmode\hbox to4.8pt{\vbox
to10.8pt{\pgfpicture\makeatletter\hbox{\hskip 2.4pt\lower-2.4pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ { {}{}{}{}{}}{}{}{}{}{{}}{} {
{}{}{}{}{}}{}{}{}{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0.88,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.88,0}\pgfsys@color@cmyk@stroke{0.91}{0}{0.88}{0.12}\pgfsys@invoke{
}\pgfsys@color@cmyk@fill{0.91}{0}{0.88}{0.12}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0.88,0}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}{}\pgfsys@moveto{-2.0pt}{8.00002pt}\pgfsys@moveto{-2.0pt}{8.00002pt}\pgfsys@lineto{-2.0pt}{-2.0pt}\pgfsys@lineto{2.0pt}{-2.0pt}\pgfsys@lineto{2.0pt}{8.00002pt}\pgfsys@closepath\pgfsys@moveto{2.0pt}{-2.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\leavevmode\hbox
to4.8pt{\vbox to10.8pt{\pgfpicture\makeatletter\hbox{\hskip
2.4pt\lower-2.4pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ { {}{}{}{}{}}{}{}{}{}{{}}{} {
{}{}{}{}{}}{}{}{}{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0.68,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0,0}\pgfsys@color@cmyk@stroke{0}{0.87}{0.68}{0.32}\pgfsys@invoke{
}\pgfsys@color@cmyk@fill{0}{0.87}{0.68}{0.32}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0.68,0,0}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}{}\pgfsys@moveto{-2.0pt}{8.00002pt}\pgfsys@moveto{-2.0pt}{8.00002pt}\pgfsys@lineto{-2.0pt}{-2.0pt}\pgfsys@lineto{2.0pt}{-2.0pt}\pgfsys@lineto{2.0pt}{8.00002pt}\pgfsys@closepath\pgfsys@moveto{2.0pt}{-2.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$

By Theorem 3.15, $x$ is $2$-regular and a $2$-linear representation
$(A_{0},A_{1},v)$ of $x$ is given by

$v=\begin{pmatrix}x\\\ x\circ(n\mapsto 2n)\\\ x\circ(n\mapsto 2n+1)\\\
x\circ(n\mapsto 4n)\\\ x\circ(n\mapsto 4n+1)\\\ x\circ(n\mapsto 4n+2)\\\
x\circ(n\mapsto 4n+3)\end{pmatrix}$

as well as

$A_{0}=\begin{pmatrix}\leavevmode\hbox to6.67pt{\vbox
to6.67pt{\pgfpicture\makeatletter\hbox{\hskip 3.33301pt\lower-3.33301pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}0&\leavevmode\hbox
to6.67pt{\vbox to6.67pt{\pgfpicture\makeatletter\hbox{\hskip
3.33301pt\lower-3.33301pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}1\leavevmode\hbox
to6.67pt{\vbox to6.67pt{\pgfpicture\makeatletter\hbox{\hskip
3.33301pt\lower-3.33301pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}&0&\leavevmode\hbox
to6.67pt{\vbox to6.67pt{\pgfpicture\makeatletter\hbox{\hskip
3.33301pt\lower-3.33301pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}0&0&0&0\\\
0&0&0&\leavevmode\hbox to6.67pt{\vbox
to6.67pt{\pgfpicture\makeatletter\hbox{\hskip 3.33301pt\lower-3.33301pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}1&0&0&0\\\
0&0&0\leavevmode\hbox to6.67pt{\vbox
to6.67pt{\pgfpicture\makeatletter\hbox{\hskip 3.33301pt\lower-3.33301pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}&0&1\leavevmode\hbox
to6.67pt{\vbox to6.67pt{\pgfpicture\makeatletter\hbox{\hskip
3.33301pt\lower-3.33301pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}&0&0\leavevmode\hbox
to6.67pt{\vbox to6.67pt{\pgfpicture\makeatletter\hbox{\hskip
3.33301pt\lower-3.33301pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\\\
0&0&0&\leavevmode\hbox to6.67pt{\vbox
to6.67pt{\pgfpicture\makeatletter\hbox{\hskip 3.33301pt\lower-3.33301pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}1&1&1&1\\\
0&0&0&1&1&1&1\\\ 0&0&0&1&1&1&1\\\ 0&0&0&1&1&1&1\leavevmode\hbox to6.67pt{\vbox
to6.67pt{\pgfpicture\makeatletter\hbox{\hskip 3.33301pt\lower-3.33301pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\\\
\end{pmatrix}\leavevmode\hbox to4.8pt{\vbox
to10.8pt{\pgfpicture\makeatletter\hbox{\hskip 2.4pt\lower-2.4pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ { {}{}{}{}{}}{}{}{}{}{{}}{} {
{}{}{}{}{}}{}{}{}{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0.88,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.88,0}\pgfsys@color@cmyk@stroke{0.91}{0}{0.88}{0.12}\pgfsys@invoke{
}\pgfsys@color@cmyk@fill{0.91}{0}{0.88}{0.12}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0.88,0}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}{}\pgfsys@moveto{-2.0pt}{8.00002pt}\pgfsys@moveto{-2.0pt}{8.00002pt}\pgfsys@lineto{-2.0pt}{-2.0pt}\pgfsys@lineto{2.0pt}{-2.0pt}\pgfsys@lineto{2.0pt}{8.00002pt}\pgfsys@closepath\pgfsys@moveto{2.0pt}{-2.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\leavevmode\hbox
to4.8pt{\vbox to10.8pt{\pgfpicture\makeatletter\hbox{\hskip
2.4pt\lower-2.4pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ { {}{}{}{}{}}{}{}{}{}{{}}{} {
{}{}{}{}{}}{}{}{}{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@invoke{
}\pgfsys@color@gray@fill{.75}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{.75,.75,.75}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}{}\pgfsys@moveto{-2.0pt}{8.00002pt}\pgfsys@moveto{-2.0pt}{8.00002pt}\pgfsys@lineto{-2.0pt}{-2.0pt}\pgfsys@lineto{2.0pt}{-2.0pt}\pgfsys@lineto{2.0pt}{8.00002pt}\pgfsys@closepath\pgfsys@moveto{2.0pt}{-2.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\leavevmode\hbox
to4.8pt{\vbox to10.8pt{\pgfpicture\makeatletter\hbox{\hskip
2.4pt\lower-2.4pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ { {}{}{}{}{}}{}{}{}{}{{}}{} {
{}{}{}{}{}}{}{}{}{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@invoke{
}\pgfsys@color@gray@fill{.75}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{.75,.75,.75}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}{}\pgfsys@moveto{-2.0pt}{8.00002pt}\pgfsys@moveto{-2.0pt}{8.00002pt}\pgfsys@lineto{-2.0pt}{-2.0pt}\pgfsys@lineto{2.0pt}{-2.0pt}\pgfsys@lineto{2.0pt}{8.00002pt}\pgfsys@closepath\pgfsys@moveto{2.0pt}{-2.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\leavevmode\hbox
to4.8pt{\vbox to10.8pt{\pgfpicture\makeatletter\hbox{\hskip
2.4pt\lower-2.4pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ { {}{}{}{}{}}{}{}{}{}{{}}{} {
{}{}{}{}{}}{}{}{}{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@invoke{
}\pgfsys@color@gray@fill{.5}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{.5,.5,.5}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}{}\pgfsys@moveto{-2.0pt}{8.00002pt}\pgfsys@moveto{-2.0pt}{8.00002pt}\pgfsys@lineto{-2.0pt}{-2.0pt}\pgfsys@lineto{2.0pt}{-2.0pt}\pgfsys@lineto{2.0pt}{8.00002pt}\pgfsys@closepath\pgfsys@moveto{2.0pt}{-2.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\leavevmode\hbox
to4.8pt{\vbox to10.8pt{\pgfpicture\makeatletter\hbox{\hskip
2.4pt\lower-2.4pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ { {}{}{}{}{}}{}{}{}{}{{}}{} {
{}{}{}{}{}}{}{}{}{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@invoke{
}\pgfsys@color@gray@fill{.5}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{.5,.5,.5}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}{}\pgfsys@moveto{-2.0pt}{8.00002pt}\pgfsys@moveto{-2.0pt}{8.00002pt}\pgfsys@lineto{-2.0pt}{-2.0pt}\pgfsys@lineto{2.0pt}{-2.0pt}\pgfsys@lineto{2.0pt}{8.00002pt}\pgfsys@closepath\pgfsys@moveto{2.0pt}{-2.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\mbox{\quad
and\quad}A_{1}=\begin{pmatrix}\leavevmode\hbox to6.67pt{\vbox
to6.67pt{\pgfpicture\makeatletter\hbox{\hskip 3.33301pt\lower-3.33301pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}0&0&\leavevmode\hbox
to6.67pt{\vbox to6.67pt{\pgfpicture\makeatletter\hbox{\hskip
3.33301pt\lower-3.33301pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}1\leavevmode\hbox
to6.67pt{\vbox to6.67pt{\pgfpicture\makeatletter\hbox{\hskip
3.33301pt\lower-3.33301pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}&\leavevmode\hbox
to6.67pt{\vbox to6.67pt{\pgfpicture\makeatletter\hbox{\hskip
3.33301pt\lower-3.33301pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}0&0&0&0\\\
0&0&0&0&0&\leavevmode\hbox to6.67pt{\vbox
to6.67pt{\pgfpicture\makeatletter\hbox{\hskip 3.33301pt\lower-3.33301pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}1&0\\\
0&0&0\leavevmode\hbox to6.67pt{\vbox
to6.67pt{\pgfpicture\makeatletter\hbox{\hskip 3.33301pt\lower-3.33301pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}&0&0&0&1\leavevmode\hbox
to6.67pt{\vbox to6.67pt{\pgfpicture\makeatletter\hbox{\hskip
3.33301pt\lower-3.33301pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\\\
0&0&0&\leavevmode\hbox to6.67pt{\vbox
to6.67pt{\pgfpicture\makeatletter\hbox{\hskip 3.33301pt\lower-3.33301pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}2&2&2&2\\\
0&0&0&2&2&2&2\\\ 0&0&0&2&2&2&2\\\ 0&0&0&2&2&2&2\leavevmode\hbox to6.67pt{\vbox
to6.67pt{\pgfpicture\makeatletter\hbox{\hskip 3.33301pt\lower-3.33301pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\\\
\end{pmatrix}.\leavevmode\hbox to4.8pt{\vbox
to10.8pt{\pgfpicture\makeatletter\hbox{\hskip 2.4pt\lower-2.4pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ { {}{}{}{}{}}{}{}{}{}{{}}{} {
{}{}{}{}{}}{}{}{}{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@invoke{
}\pgfsys@color@gray@fill{.75}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{.75,.75,.75}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}{}\pgfsys@moveto{-2.0pt}{8.00002pt}\pgfsys@moveto{-2.0pt}{8.00002pt}\pgfsys@lineto{-2.0pt}{-2.0pt}\pgfsys@lineto{2.0pt}{-2.0pt}\pgfsys@lineto{2.0pt}{8.00002pt}\pgfsys@closepath\pgfsys@moveto{2.0pt}{-2.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\leavevmode\hbox
to4.8pt{\vbox to10.8pt{\pgfpicture\makeatletter\hbox{\hskip
2.4pt\lower-2.4pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ { {}{}{}{}{}}{}{}{}{}{{}}{} {
{}{}{}{}{}}{}{}{}{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{.75,.75,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.75,.75}\pgfsys@color@gray@stroke{.75}\pgfsys@invoke{
}\pgfsys@color@gray@fill{.75}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{.75,.75,.75}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}{}\pgfsys@moveto{-2.0pt}{8.00002pt}\pgfsys@moveto{-2.0pt}{8.00002pt}\pgfsys@lineto{-2.0pt}{-2.0pt}\pgfsys@lineto{2.0pt}{-2.0pt}\pgfsys@lineto{2.0pt}{8.00002pt}\pgfsys@closepath\pgfsys@moveto{2.0pt}{-2.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\leavevmode\hbox
to4.8pt{\vbox to10.8pt{\pgfpicture\makeatletter\hbox{\hskip
2.4pt\lower-2.4pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ { {}{}{}{}{}}{}{}{}{}{{}}{} {
{}{}{}{}{}}{}{}{}{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@invoke{
}\pgfsys@color@gray@fill{.5}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{.5,.5,.5}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}{}\pgfsys@moveto{-2.0pt}{8.00002pt}\pgfsys@moveto{-2.0pt}{8.00002pt}\pgfsys@lineto{-2.0pt}{-2.0pt}\pgfsys@lineto{2.0pt}{-2.0pt}\pgfsys@lineto{2.0pt}{8.00002pt}\pgfsys@closepath\pgfsys@moveto{2.0pt}{-2.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\leavevmode\hbox
to4.8pt{\vbox to10.8pt{\pgfpicture\makeatletter\hbox{\hskip
2.4pt\lower-2.4pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ { {}{}{}{}{}}{}{}{}{}{{}}{} {
{}{}{}{}{}}{}{}{}{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@invoke{
}\pgfsys@color@gray@fill{.5}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{.5,.5,.5}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}{}\pgfsys@moveto{-2.0pt}{8.00002pt}\pgfsys@moveto{-2.0pt}{8.00002pt}\pgfsys@lineto{-2.0pt}{-2.0pt}\pgfsys@lineto{2.0pt}{-2.0pt}\pgfsys@lineto{2.0pt}{8.00002pt}\pgfsys@closepath\pgfsys@moveto{2.0pt}{-2.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\leavevmode\hbox
to4.8pt{\vbox to10.8pt{\pgfpicture\makeatletter\hbox{\hskip
2.4pt\lower-2.4pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ { {}{}{}{}{}}{}{}{}{}{{}}{} {
{}{}{}{}{}}{}{}{}{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0.68,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0,0}\pgfsys@color@cmyk@stroke{0}{0.87}{0.68}{0.32}\pgfsys@invoke{
}\pgfsys@color@cmyk@fill{0}{0.87}{0.68}{0.32}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0.68,0,0}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}{}\pgfsys@moveto{-2.0pt}{8.00002pt}\pgfsys@moveto{-2.0pt}{8.00002pt}\pgfsys@lineto{-2.0pt}{-2.0pt}\pgfsys@lineto{2.0pt}{-2.0pt}\pgfsys@lineto{2.0pt}{8.00002pt}\pgfsys@closepath\pgfsys@moveto{2.0pt}{-2.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$

The dark gray boxes mark the matrices $J_{r0}$ and $J_{r1}$, whereas the
smaller, light gray boxes mark the shifted identity matrices mentioned in
Remark 3.16.

##  4 Asymptotics

We want to study the asymptotic behavior for $q$-recursive sequences (or, to
be precise, of their summatory functions). As we have already seen that such
sequences are $q$-regular, we can apply the results of [20]. This is indeed
what we do, however, our set-up here is more specific than $q$-regular
sequences in general, because the sequences are given by particular recurrence
relations. This leads to more specific results here.

We start by briefly discussing the growth of matrix products, in particular in
conjunction with the joint spectral radius. This is one important quantity
determining the asymptotics of a sequence. Beside that, the eigenvalues of the
sum of matrices of a $q$-linear representation play an important role.

Again, we will distinguish between the general case and the special case
introduced in Section 3.3.

###  4.1 Growth of Matrix Products

Before presenting previous results and adapting them to our purposes, we
recall the notion of the joint spectral radius and introduce some related
notions.

We fix a vector norm $\lVert\,\cdot\,\rVert$ on $\mathbb{C}^{D}$ and consider
its induced matrix norm.

######  Definition 4.18.

Let $\mathcal{G}$ be a finite set of $D\times D$ matrices over $\mathbb{C}$.

  1. (a)

The joint spectral radius of $\mathcal{G}$ is defined as

$\rho(\mathcal{G})\coloneqq\lim_{k\to\infty}\sup\\{\lVert G_{1}\ldots
G_{k}\rVert^{1/k}\mid G_{1},\ldots,G_{k}\in\mathcal{G}\\}.$

  2. (b)

We say that $\mathcal{G}$ has the _finiteness property_ if there exists a
$k\in\mathbb{N}$ such that

$\rho(\mathcal{G})=\sup\\{\lVert G_{1}\ldots G_{k}\rVert^{1/k}\mid
G_{1},\ldots,G_{k}\in\mathcal{G}\\}.$

  3. (c)

We say that $\mathcal{G}$ has the _simple growth property_ if

$\lVert G_{1}\ldots G_{k}\rVert=O(\rho(\mathcal{G})^{k})$

holds for all $G_{1}$, …, $G_{k}\in\mathcal{G}$ and $k\to\infty$.

######  Remark 4.19.

  1. 1.

In the definition of the joint spectral radius, the limit can be replaced by
an infimum over all $k\geq 1$; see Rota and Strang [35] and also [20, Section
7.2]. In particular, the limit in the definition of the joint spectral radius
always exists.

  2. 2.

As any two norms on $\mathbb{C}^{D\times D}$ are equivalent, the definitions
of the joint spectral radius and the simple growth property do not depend on
the chosen norm. The finiteness property, however, depends on the chosen norm;
see Remark 7.45 for an example.

  3. 3.

The finiteness property implies the simple growth property; see [20, Section
7.2].

  4. 4.

The set

$\mathcal{G}\coloneqq\left\\{\begin{pmatrix}1&1\\\ 0&1\end{pmatrix}\right\\}$

has joint spectral radius $1$, but not the simple growth property, because the
$k$th power of the only matrix in $\mathcal{G}$ equals

$\begin{pmatrix}1&1\\\ 0&1\end{pmatrix}^{k}=\begin{pmatrix}1&k\\\
0&1\end{pmatrix}.$

In Lemma 4.23, we will study sufficient conditions under which sets of block
triangular matrices have the simple growth property.

###  4.2 Asymptotics for Regular Sequences

In order to obtain the asymptotics for the summatory function of $q$-recursive
sequences, we now apply a result of the first two authors of this article on
the asymptotic behavior of $q$-regular sequences [20, Theorem A]. So let $x$
be a $q$-recursive sequence with $q$-linear representation
$(A_{0},\dots,A_{q-1},v)$, and set

$C\coloneqq\smashoperator[]{\sum_{0\leq r<q}^{}}A_{r}.$

For a square matrix $G$, let $\sigma(G)$ denote the set of eigenvalues of $G$
and by $m_{G}(\lambda)$ the size of the largest Jordan block of $G$ associated
with some $\lambda\in\mathbb{C}$. In particular, we have $m_{G}(\lambda)=0$ if
$\lambda\notin\sigma(G)$.

Then we choose $R>0$ as follows: If the set
$\mathcal{A}=\\{A_{0},\dots,A_{q-1}\\}$ has the simple growth property, then
we set $R=\rho(\mathcal{A})$. Otherwise, we choose $R>\rho(\mathcal{A})$ such
that there is no eigenvalue $\lambda\in\sigma(C)$ with
$\rho(\mathcal{A})<\lvert\lambda\rvert\leq R$. Furthermore, we let

$\mathcal{X}(s)=\sum_{n\geq 1}n^{-s}x(n)\mbox{\quad
and\quad}\mathcal{V}(s)=\sum_{n\geq 1}n^{-s}v(n)$

denote the Dirichlet series corresponding to $x$ and $v$. Now we are ready to
state the result.

######  Theorem 4.20 (Asymptotic Analysis of $q$-Regular Sequences [20,
Theorem A]).

With the notations above, we have999We let $\\{z\\}\coloneqq z-\lfloor
z\rfloor$ denote the fractional part of a real number $z$.

$X(N)=\smashoperator[]{\sum_{0\leq
n<N}^{}}x(n)=\smashoperator[]{\sum_{\begin{subarray}{c}\lambda\in\sigma(C)\\\
\lvert\lambda\rvert>R\end{subarray}}^{}}N^{\log_{q}\lambda}\quad\smashoperator[]{\sum_{0\leq
k<m_{C}(\lambda)}^{}}\quad\frac{(\log N)^{k}}{k!}\ \Phi_{\lambda
k}(\\{\log_{q}N\\})\\\ +O\bigl{(}N^{\log_{q}R}(\log
N)^{\max\\{m_{C}(\lambda)\colon\lvert\lambda\rvert=R\\}}\bigr{)}$ (4.1)

as $N\to\infty$, where $\Phi_{\lambda k}$ are suitable $1$-periodic functions.
If there are no eigenvalues $\lambda\in\sigma(C)$ with
$\lvert\lambda\rvert\leq R$, the $O$-term can be omitted.

For $\lvert\lambda\rvert>R$ and $0\leq k<m_{C}(\lambda)$, the function
$\Phi_{\lambda k}$ is Hölder continuous with any exponent smaller than
$\log_{q}(\lvert\lambda\rvert/R)$.

The Dirichlet series $\mathcal{V}(s)$ converges absolutely and uniformly on
compact subsets of the half plane $\real s>\log_{q}R+1$ and can be continued
to a meromorphic function on the half plane $\real s>\log_{q}R$. It satisfies
the functional equation

$(I-q^{-s}C)\mathcal{V}(s)=\smashoperator[]{\sum_{1\leq
n<q}^{}}n^{-s}v(n)+q^{-s}\smashoperator[]{\sum_{0\leq r<q}^{}}A_{r}\sum_{k\geq
1}\binom{-s}{k}\biggl{(}\frac{r}{q}\biggr{)}^{k}\mathcal{V}(s+k)$ (4.2)

for $\real s>\log_{q}R$. The right-hand side of (4.2) converges absolutely and
uniformly on compact subsets of $\real s>\log_{q}R$. In particular,
$\mathcal{V}(s)$ can only have poles where $q^{s}\in\sigma(C)$.

For $\lambda\in\sigma(C)$ with $\lvert\lambda\rvert>R$ and $0\leq
k<m_{C}(\lambda)$, the Fourier series

$\Phi_{\lambda k}(u)=\sum_{\mu\in\mathbb{Z}}\varphi_{\lambda k\mu}\exp(2\mu\pi
iu)$ (4.3)

converges pointwise for $u\in\mathbb{R}$ where the Fourier coefficients
$\varphi_{\lambda k\mu}$ are given by the singular expansion

$\frac{x(0)+\mathcal{X}(s)}{s}\asymp\sum_{\begin{subarray}{c}\lambda\in\sigma(C)\\\
\lvert\lambda\rvert>R\end{subarray}}\;\sum_{\mu\in\mathbb{Z}}\;\sum_{0\leq
k<m_{C}(\lambda)}\frac{\varphi_{\lambda
k\mu}}{\bigl{(}s-\log_{q}\lambda-\frac{2\mu\pi i}{\log q}\bigr{)}^{k+1}}$
(4.4)

for $\real s>\log_{q}R$.

######  Remark 4.21.

  1. 1.

[20, Theorem A] only uses the simple growth property implicitly; the full
details are contained in [20, Section 6]. Note that there, the only property
of the joint spectral radius used is [20, Equation (7.1)].

  2. 2.

The given expressions for the Fourier coefficients allow their computation
with high precision; see [20, Part IV]. Furthermore, an implementation is
available at https://gitlab.com/dakrenn/regular-sequence-fluctuations. We will
use this implementation to compute the Fourier coefficients for the examples
in Sections 5, 6 and 7.

  3. 3.

The motivation for analyzing the summatory function instead of the sequence
itself is the following: The asymptotic behavior of regular sequences is often
not smooth (which would imply that in any asymptotic expansion as given in
[20], everything is absorbed by the error term), whereas the asymptotic
behavior of the summatory function is.

However, it is also possible to apply Theorem 4.20 to a $q$-regular sequence
$x$ itself: Let us write

$x(N)=x(0)+\smashoperator[]{\sum_{0\leq n<N}^{}}\bigl{(}x(n+1)-x(n)\bigr{)}.$

So $x$ can be represented as the summatory function of the sequence of
differences

$f(n)\coloneqq x(n+1)-x(n),$

which is again $q$-regular by [1, Theorems 2.5 and 2.6]. Consequently,
applying Theorem 4.20 to $f$ yields an asymptotic analysis for

$F(N)=\smashoperator[]{\sum_{0\leq n<N}^{}}f(n)=x(N)-x(0),$

which differs from the asymptotic behavior of $x$ only by an additive
constant.

###  4.3 Spectral Results in the General Case

In this section, we show that in most cases, the asymptotic behavior of a
regular sequence can be deduced directly from a linear representation which is
valid from some offset $n_{0}\geq 1>0$. In these cases, it is not necessary to
use Theorem 3.11 to construct an augmented linear representation valid for all
non-negative integers. So, we will assume that $n_{0}\geq 1$ because
otherwise, there is nothing to do.

We first consider the significant eigenvalues and then the significant joint
spectral radii (significant with respect to Theorem 4.20).

######  Proposition 4.22.

Let $A_{0}$, …, $A_{q-1}$, $\widetilde{A}_{0}$, …, $\widetilde{A}_{q-1}$ and
$n_{0}$ as in Theorem 3.11. Assume that $n_{0}\geq 1$. Set

$C\coloneqq\smashoperator[]{\sum_{0\leq r<q}^{}}A_{r}\mbox{\quad
and\quad}\widetilde{C}\coloneqq\smashoperator[]{\sum_{0\leq
r<q}^{}}\widetilde{A}_{r}.$

Then $\sigma(\widetilde{C})\subseteq\sigma(C)\cup\\{0,1\\}$ holds. In
particular,

  1. (a)

if $n_{0}=1$, then $\sigma(\widetilde{C})=\sigma(C)\cup\\{1\\}$ and for all
$\lambda\in\mathbb{C}\setminus\\{1\\}$, we have
$m_{C}(\lambda)=m_{\widetilde{C}}(\lambda)$; and

  2. (b)

if $n_{0}\geq 2$, then $\sigma(\widetilde{C})=\sigma(C)\cup\\{0,1\\}$ and for
all $\lambda\in\mathbb{C}\setminus\\{0,1\\}$, we have
$m_{C}(\lambda)=m_{\widetilde{C}}(\lambda)$.

Before stating the second result, we state a lemma dealing with the simple
growth property for sets of block triangular matrices. This is a refinement of
Jungers [25, Proposition 1.5], which deals with the joint spectral radius only
(here restated as the first statement of the lemma).

######  Lemma 4.23.

Let $\mathcal{G}$ be a finite set of
$(D_{1}+D_{2}+\cdots+D_{s})\times(D_{1}+D_{2}+\cdots+D_{s})$ block upper
triangular matrices. For $G\in\mathcal{G}$ write

$G=\begin{pmatrix}G^{(11)}&G^{(12)}&\ldots&G^{(1s)}\\\
0&G^{(22)}&\ldots&G^{(2s)}\\\ \vdots&\vdots&\ddots&\vdots\\\
0&0&\ldots&G^{(ss)}\end{pmatrix}$

where the block $G^{(ij)}$ is a $D_{i}\times D_{j}$ matrix for $1\leq i\leq
j\leq s$. Set $\mathcal{G}^{(i)}\coloneqq\\{G^{(ii)}\mid G\in\mathcal{G}\\}$.
Then $\rho(\mathcal{G})=\max_{1\leq i\leq s}\rho(\mathcal{G}^{(i)})$.

If there is a unique $i_{0}\in\\{1,\ldots,s\\}$ such that
$\rho(\mathcal{G}^{(i_{0})})=\rho(\mathcal{G})$ and $\mathcal{G}^{(i_{0})}$
has the simple growth property, then $\mathcal{G}$ has the simple growth
property.

We now state the result on the joint spectral radius in the context of Theorem
3.11.

######  Proposition 4.24.

Let $\mathcal{A}\coloneqq\\{A_{0},\dots,A_{q-1}\\}$,
$\widetilde{\mathcal{A}}\coloneqq\\{\widetilde{A}_{0},\dots,\widetilde{A}_{q-1}\\}$
and $\mathcal{J}\coloneqq\\{J_{0},\dots,J_{q-1}\\}$ be the sets of matrices
and $n_{0}$ the offset as given in Theorem 3.11, and assume $n_{0}\geq 1$.
Then the joint spectral radii of $\widetilde{\mathcal{A}}$ and $\mathcal{J}$
satisfy

$\rho(\widetilde{\mathcal{A}})=\max\big{\\{}\rho(\mathcal{A}),1\big{\\}}\mbox{\quad
and\quad}\rho(\mathcal{J})=1,$ (4.5)

respectively. In particular, if $\rho(\mathcal{A})\geq 1$ holds, then we have
$\rho(\widetilde{\mathcal{A}})=\rho(\mathcal{A})$.

Furthermore, if $\rho(\mathcal{A})>1$ holds and $\mathcal{A}$ has the simple
growth property, then $\widetilde{\mathcal{A}}$ has the simple growth
property.

Combining Propositions 4.22 and 4.24 with Theorem 4.20 implies that the
asymptotics can also be determined by using the matrices $A_{0}$, …, $A_{q-1}$
(which do not contain the correction for the offset; see Theorem 3.11) instead
of the matrices $\widetilde{A}_{0}$, …, $\widetilde{A}_{q-1}$ from the linear
representation.

Note that if $\rho(\mathcal{A})<1$, then the error in (4.1) is $o(1)$. This
implies that adding constants (created by correction terms if the recurrence
relation is not valid for some $n\geq 0$) is visible in the asymptotic
expansion.

###  4.4 Spectral Results in the Special Case

Next, we are interested in the eigenvalues of the matrix $C=\sum_{0\leq
r<q}A_{r}$ for the special case. It turns out that the eigenvalues of $C$ can
be obtained from the recurrence relations (3.1) more directly than via the
detour to linear representations.

Note that also here we assume the offset to be $n_{0}=0$ for the sake of
readability, analogous to Section 3.3. The following results can be
generalized easily for arbitrary offset.

######  Proposition 4.25.

Let $A_{0}$, …, $A_{q-1}$ and $B_{0}$, …, $B_{q-1}$ be the matrices as given
in Theorem 3.15, let $M=m+1$ and $m$ be the exponents of the corresponding
$q$-recursive sequence with $m\geq 1$ and set $C=\sum_{0\leq r<q}A_{r}$. Then
we have

$\sigma(C)=\sigma(B_{0}+\cdots+B_{q-1})\cup\\{0\\}.$

Moreover, we have $m_{C}(\lambda)=m_{B_{0}+\cdots+B_{q-1}}(\lambda)$ for all
$\lambda\in\mathbb{C}\setminus\\{0\\}$.

######  Proposition 4.26.

Let $\mathcal{A}\coloneqq\\{A_{0},\dots,A_{q-1}\\}$,
$\mathcal{J}\coloneqq\\{J_{00},\dots,J_{(q-1)0}\\}$ and
$\mathcal{B}\coloneqq\\{B_{0},\dots,B_{q-1}\\}$ the sets of matrices as given
in Theorem 3.15. Then the joint spectral radii of $\mathcal{A}$ and
$\mathcal{J}$ satisfy

$\rho(\mathcal{A})=\rho(\mathcal{B})\mbox{\quad and\quad}\rho(\mathcal{J})=0,$

respectively.

Furthermore, if $\rho(\mathcal{B})>0$ holds and $\mathcal{B}$ has the simple
growth property, then $\mathcal{A}$ has the simple growth property.

The two propositions of this section provide the possibility to obtain the
asymptotics of the summatory function without knowing a linear representation
of the sequence; the asymptotics are fully determined by the matrices $B_{0}$,
…, $B_{q-1}$.

###  4.5 Functional Equation for the Dirichlet Series in the Special Case

Theorem 4.20 indicates that functional equations for the Dirichlet series
corresponding to the sequence of interest are essential for computing Fourier
coefficients of the periodic fluctuations. We now give an variant for our
special case of a $q$-recursive sequence which does not require constructing
the $q$-linear representation first.

######  Proposition 4.27.

Let $x$ be a $q$-recursive sequence with exponents $M=m+1$ and $m$, index
shift bounds $\ell=0$ and $u=q^{m}-1$ and coefficients $(c_{j,k})_{0\leq
j<q^{m+1},0\leq k<q^{m}}$, and let $B_{0}$, …, $B_{q-1}$ be the matrices
introduced in (3.11). Let $\rho>0$ be such that $x(n)=O(n^{\log_{q}R})$ as
$n\to\infty$ holds for all $R>\rho$, and let $\eta\geq 1$ be an integer. We
define the Dirichlet series

$\mathcal{X}_{j}(s)\coloneqq\smashoperator[]{\sum_{n\geq\eta}^{}}\
\frac{x(q^{m}n+j)}{(q^{m}n+j)^{s}}=\ \smashoperator[]{\sum_{n\geq
q^{m}\eta+j}^{}}\ \frac{x(n)\llbracket n\equiv
j{\@displayfalse\pmod{q^{m}}}\rrbracket}{n^{s}}$ (4.6)

for $0\leq j<q^{m}$ and $\real s>\log_{q}\rho+1$ and set

$\mathcal{X}(s)\coloneqq\begin{pmatrix}\mathcal{X}_{0}(s)\\\ \vdots\\\
\mathcal{X}_{q^{m}-1}(s)\end{pmatrix}.$

Then the functional equation

$\bigl{(}I-q^{-s}(B_{0}+\cdots+B_{q-1})\bigr{)}\mathcal{X}(s)=\begin{pmatrix}\mathcal{Y}_{0}(s)\\\
\vdots\\\ \mathcal{Y}_{q^{m}-1}(s)\end{pmatrix}$ (4.7)

holds for $\real s>\log_{q}\rho$ with

$\mathcal{Y}_{j}(s)=q^{-s}\sum_{k=0}^{q^{m}-1}\Biggl{(}\sum_{n\geq
1}\binom{-s}{n}\biggl{(}\sum_{\mu=0}^{q-1}c_{\mu q^{m}+j,k}\Bigl{(}\frac{\mu
q^{m}+j}{q}-k\Bigr{)}^{n}\biggr{)}\mathcal{X}_{k}(s+n)\Biggr{)}+\
\smashoperator[l]{\sum_{\eta\leq
n<q\eta}^{}}\frac{x(q^{m}n+j)}{(q^{m}n+j)^{s}}.$ (4.8)

Moreover, $\mathcal{Y}_{j}(s)$ is analytic for $\real s>\log_{q}\rho$ and all
$0\leq j<q^{m}$, and, in particular, $\mathcal{X}(s)$ is meromorphic for
$\real s>\log_{q}\rho$ and can only have poles $s$ where
$q^{s}\in\sigma(B_{0}+\cdots+B_{q-1})$.

##  5 Stern’s Diatomic Sequence

###  5.1 Introduction of the Sequence

We start our detailed study of particular sequences by studying a sequence
which has a long history, namely the so-called101010Note that this sequence
has a strong connection to Stern–Brocot trees, which were first discovered
independently by Stern [37] and Brocot [7]. This is the reason that Stern’s
diatomic sequence is also known as _Stern–Brocot sequence._ _Stern’s diatomic
sequence_ ; see [34, A002487]. After its earliest introduction by Stern [37]
in 1858, the sequence has been studied thoroughly; see Northshield [33] and
the references therein, and also Coons and Shallit [10], Leroy, Rigo and
Stipulanti [28].

Stern’s diatomic sequence $d$ is defined by111111Strictly speaking, $d(0)=0$
follows from (5.1b) for $n=0$. $d(0)=0$, $d(1)=1$ and

$\displaystyle d(2n)$ $\displaystyle=d(n),$ (5.1a) $\displaystyle d(2n+1)$
$\displaystyle=d(n)+d(n+1)$ (5.1b)

for all $n\geq 0$. The first few terms of $d$ are given in Table 5.1.

$n$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ | $11$ | $12$ | $13$ | $14$ | $15$
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$d(n)$ | $0$ | $1$ | $1$ | $2$ | $1$ | $3$ | $2$ | $3$ | $1$ | $4$ | $3$ | $5$ | $2$ | $5$ | $3$ | $4$
Table 5.1: First few elements of Stern’s diatomic sequence $d$

###  5.2 Combinatorial Interpretations of the Sequence

There are several combinatorial interpretations of Stern’s diatomic sequence.
In the following, we give a short overview of the most interesting connections
to combinatorial settings.

  1. 1.

Let us call the word $d_{L-1}\ldots d_{0}$ over the alphabet $\\{0,1,2\\}$ a
_hyperbinary representation_ of some $n\in\mathbb{N}_{0}$ if $n=\sum_{0\leq
i<L}d_{i}2^{i}$ and $d_{L-1}\neq 0$. Then the number of different hyperbinary
representations of $n$ is equal to $d(n+1)$ for all $n\geq 0$; see Northshield
[33, Theorem 3.1].

  2. 2.

Let $\genfrac{\\{}{\\}}{0.0pt}{}{n}{r}$ denote the _Stirling partition
numbers_ , i.e., $\genfrac{\\{}{\\}}{0.0pt}{}{n}{r}$ is the number of
different partitions of the set $\\{1,\dots,n\\}$ in exactly $r$ non-empty
subsets. Then $d(n)$ equals the number of integers $r\in\mathbb{N}_{0}$ such
that $\genfrac{\\{}{\\}}{0.0pt}{}{n}{2r}$ is even and non-zero; see Carlitz
[8].

  3. 3.

Let $F(n)$ be the $n$th _Fibonacci number_. Then $d(n)$ is equal to the number
of different representations of $n$ as a sum of distinct Fibonacci numbers
$F(2k)$ with $k\in\mathbb{N}_{0}$; see Bicknell-Johnson [6].

  4. 4.

An _alternating bit set_ of some integer $n\in\mathbb{N}_{0}$ is a subset $A$
of the positions in the binary expansion of $n$ such that

     * •

the bits of the binary expansion of $n$ at positions which lie in $A$ are
alternating between $1$ and $0$,

     * •

the most significant bit at a position which lies in $A$ is a $1$, and

     * •

the least significant bit at a position which lies in $A$ is a $0$.

In particular, we also allow $A=\emptyset$ to be an alternating bit set. Note
that this definition implies that every alternating bit set has even
cardinality.

Then the number of different alternating bit sets of $n$ is equal to $d(n+1)$;
see Finch [14, Section 2.16.3].

  5. 5.

There is a relation to the well-known _Towers of Hanoi_ ; see Hinz, Klavžar,
Milutinović, Parisse and Petr [23].

Thus, the asymptotic analysis of the summatory function of Stern’s diatomic
sequence is indeed well-motivated, also from a combinatorial point of view.

###  5.3 Regularity and a Linear Representation

In order to be able to apply Theorem 4.20 for the asymptotic analysis of the
summatory function, the sequence $d$ has to be recursive. Due to the
definition of the sequence in (5.1), it is clear that $d$ is $2$-recursive
with exponents $M=1$ and $m=0$, index shift bounds $\ell=0$ and $u=1$, and
offset $n_{0}=0$. Thus, it is also $2$-regular by Theorem 3.7. Note that
Theorem 3.15 is not applicable: The term $d(n+1)$ appears in (5.1b) and
therefore, the upper index shift bound $u$ needs to be at least $1$, whereas
Theorem 3.15 only allows $0$ as an upper index shift bound in the case $m=0$.
So we use Theorem 3.7 to obtain a $2$-linear representation $(A_{0},A_{1},v)$
of $d$: The vector-valued sequence $v$ is given by

$v=\begin{pmatrix}d\\\ d\circ(n\mapsto n+1)\\\ d\circ(n\mapsto
n+2)\end{pmatrix},$

and the matrices are given by

$A_{0}=\begin{pmatrix}1&0&0\\\ 1&1&0\\\ 0&1&0\end{pmatrix}\mbox{\quad
and\quad}A_{1}=\begin{pmatrix}1&1&0\\\ 0&1&0\\\ 0&1&1\end{pmatrix}.$

The correctness of the recurrence relations $v(2n)=A_{0}v(n)$ and
$v(2n+1)=A_{1}v(n)$ for all $n\geq 0$ can easily be verified by using (5.1).

As in Example 3.9, we can see that $d\circ(n\mapsto n+2)$ is actually not
needed in the linear representation, which is due to the fact that the
coefficient of $d(n+1)$ in the recurrence relation (5.1a) is zero. This
implies that $(A_{0}^{\prime},A_{1}^{\prime},v^{\prime})$ with

$v^{\prime}=\begin{pmatrix}d\\\ d\circ(n\mapsto n+1)\end{pmatrix}$

as well as

$A_{0}^{\prime}=\begin{pmatrix}1&0\\\ 1&1\end{pmatrix}\mbox{\quad
and\quad}A_{1}^{\prime}=\begin{pmatrix}1&1\\\ 0&1\end{pmatrix}$

is also a $2$-linear representation of $d$.

By applying the minimization algorithm mentioned in Remark 3.8 (3), we see
that this is the smallest possible $2$-linear representation of $d$.

###  5.4 Asymptotics

Let $\mathcal{V}(s)$ denote the Dirichlet series corresponding to
$v^{\prime}$, i.e.,

$\mathcal{V}(s)=\sum_{n\geq 1}n^{-s}v^{\prime}(n),$

and let $C=A_{0}^{\prime}+A_{1}^{\prime}$. In the following theorem, we state
the main result of this section: We give an asymptotic formula for the
summatory function of $d$ as well as a functional equation for
$\mathcal{V}(s)$.

######  Theorem 5.28 (Asymptotics for Stern’s Diatomic Sequence).

The summatory function $D$ of Stern’s diatomic sequence $d$ satisfies

$D(N)=\smashoperator[]{\sum_{0\leq
n<N}^{}}d(n)=N^{\kappa}\cdot\Phi_{D}(\\{\log_{2}N\\})+O(N^{\log_{2}\varphi})$
(5.2)

as $N\to\infty$, where $\kappa=\log_{2}3=1.5849625007211\ldots$,
$\varphi=\frac{1+\sqrt{5}}{2}=1.6180339887498\ldots$ is the golden ratio,
$\log_{2}\varphi=0.69424191363061\ldots$ and $\Phi_{D}$ is a $1$-periodic
continuous function which is Hölder continuous with any exponent smaller than
$\kappa-\log_{2}\varphi$. The Fourier coefficients of $\Phi_{D}$ can be
computed efficiently.

Furthermore, the Dirichlet series $\mathcal{V}(s)$ satisfies the functional
equation

$(I-2^{-s}C)\mathcal{V}(s)=v^{\prime}(1)+2^{-s}A_{1}^{\prime}\sum_{k\geq
1}\frac{1}{2^{k}}\binom{-s}{k}\mathcal{V}(s+k)$ (5.3)

for all $\real s>\log_{2}\varphi$. Both sides of Equation (5.3) are analytic
for $\real s>\log_{2}\varphi$, and, in particular, $\mathcal{V}(s)$ is
meromorphic for $\real s>\log_{2}\varphi$ and can only have at most simple
poles $s=\log_{2}3+\frac{2i\pi\mu}{\log 2}$ with $\mu\in\mathbb{Z}$.

Table 5.2 shows the first few Fourier coefficients and Figure 5.1 a plot of
the periodic fluctuation of Theorem 5.28.

$\mu$ | $\varphi_{\mu}$
---|---
$0$ | $\phantom{-}0.5129922721107177789989881697483$
$1$ | $-0.00572340619479957230984532582323+0.00692635056470554871320794780023i$
$2$ | $\phantom{-}0.00024322678681282580951796870908+0.00296266191012688412725699259509i$
$3$ | $-0.00145239145783579607592238228126+0.00117965322085442917547658711471i$
$4$ | $\phantom{-}0.00111195666191700704424207971541+0.00018518355971470343780812186861i$
$5$ | $-0.00046732929957426516792963051204+0.00050425058689999021735711128987i$
$6$ | $-0.00044953390461558932213468137492+0.00048773649732968174101103217106i$
$7$ | $\phantom{-}0.00036329328164895877338262637843+0.00035534416834062145852032394307i$
$8$ | $-0.00016679033186561839463311958967-0.00043694014091729453542478927729i$
$9$ | $\phantom{-}0.00030367683575578278808761185183+0.00009371153567156005005069054904i$
$10$ | $-0.00009911479960205956796299031716+0.00019462735102739460438023334462i$
Table 5.2: First few Fourier Coefficients of $\Phi_{D}$ Figure 5.1:
Fluctuation in the main term of the asymptotic expansion of the summatory
function $D$. The plot shows the periodic fluctuation $\Phi_{D}(u)$
approximated by its Fourier series of degree $2000$ (red) as well as the
function $D(2^{u})/2^{\kappa u}$ (blue).

######  Proof 5.29 (Proof of Theorem 5.28).

We use Theorem 4.20 with the linear representation
$(A_{0}^{\prime},A_{1}^{\prime},v^{\prime})$ and work out the parameters
needed in the theorem. Recall that $C=A_{0}^{\prime}+A_{1}^{\prime}$.

_Joint Spectral Radius._ We determine the joint spectral radius of
$A_{0}^{\prime}$ and $A_{1}^{\prime}$. As one matrix is the transpose of the
other, the spectral norm of each of them equals the square root of the
dominant eigenvalue of their product. The maximal spectral norm of the
matrices is an upper bound for the joint spectral radius; the square root of
the dominant eigenvalue of their product is a lower bound for the joint
spectral radius. As both bounds are equal, the joint spectral radius equals
the spectral norm. It turns out that this spectral norm equals
$\varphi=\frac{1+\sqrt{5}}{2}$.

_Finiteness Property._ The finiteness property for $A_{0}^{\prime}$ and
$A_{1}^{\prime}$ is satisfied with respect to the spectral norm, which can be
seen by considering exactly one factor $A_{0}^{\prime}$ or $A_{1}^{\prime}$.
Thus, we choose $R=\varphi$.

_Eigenvalues._ The spectrum of $C$ is given by $\sigma(C)=\\{1,3\\}$.
Furthermore, it is clear that all eigenvalues are simple and thus,
$m_{C}(3)=1$.

Applying Theorem 4.20 yields the result.

It will turn out during the proof of Theorem 6.34 that a slight modification
of the summatory function leads to an exact formula:

######  Corollary 5.30.

With the notations of Theorem 5.28, we have

$\smashoperator[]{\sum_{0\leq
n<N}^{}}d(n)+\frac{1}{2}d(N)=N^{\kappa}\cdot\Phi_{D}(\\{\log_{2}N\\}).$

##  6 Number of Non-Zero Entries in a Generalized Pascal’s Triangle

###  6.1 Introduction of the Sequence

The first two authors of this article have studied Pascal’s rhombus as one
possible generalization of Pascal’s triangle in [20] as well as in [22]
together with Prodinger. In particular, they analyzed the asymptotic behavior
of the number of odd entries in the $n$th row of Pascal’s rhombus.

Here, we consider a generalization of Pascal’s triangle to binomial
coefficients of words. This generalization was first introduced by Leroy, Rigo
and Stipulanti in [27]. We in particular study the sequence counting the
number of non-zero elements in each row (see [34, A007306] except for the
initial value), which was investigated in detail by the same authors in [29]
and [30], and provide an asymptotic result for the summatory function. Our
result coincides with the result in [30]. In contrast to [30], we additionally
provide the periodic fluctuation that occurs in the asymptotics by determining
its Fourier coefficients. This completes the full picture of the summatory
function.

We start with the following definition; also see Lothaire [31, Chapter 6] for
more details on binomial coefficients of words.

######  Definition 6.31 (Scattered Subword, Binomial Coefficients of Words).

Let $u=u_{1}\ldots u_{j}$ and $v=v_{1}\dots v_{k}$ be two words over the same
alphabet.

  1. (a)

We say that $v$ is a _scattered subword_ of $u$ if there exists a strictly
increasing mapping $\pi\colon\\{1,\dots,k\\}\to\\{1,\dots,j\\}$ with
$u_{\pi(i)}=v_{i}$ for all $1\leq i\leq k$. We call $\pi$ an _occurrence_ of
$v$ as a scattered subword of $u$.

  2. (b)

The _binomial coefficient_ of $u$ and $v$, denoted by $\binom{u}{v}$, is
defined as the number of different occurrences of $v$ as a scattered subword
of $u$.

For example, we consider the words $u=u_{1}u_{2}u_{3}u_{4}u_{5}u_{6}=110010$
and $v=v_{1}v_{2}=10$ over the alphabet $\\{0,1\\}$. Then we have

$\binom{110010}{10}=7$ (6.1)

because there are exactly seven possibilities to represent $v$ as a scattered
subword of $u$, namely

$u_{1}u_{3}=u_{1}u_{4}=u_{1}u_{6}=u_{2}u_{3}=u_{2}u_{4}=u_{2}u_{6}=u_{5}u_{6}=v.$

Note that the classical binomial coefficient for two integers $n$,
$k\in\mathbb{N}_{0}$ can be obtained by the identity

$\binom{1^{n}}{1^{k}}=\binom{n}{k},$

where $1^{n}$ denotes the word consisting of $n$ ones.

Next, we define the _generalized Pascal’s triangle_ $\mathcal{P}_{2}$ as an
infinite matrix as follows: The entry in the $n$th row and $k$th column of
$\mathcal{P}_{2}$ is given by $\binom{(n)_{2}}{(k)_{2}}$, where $(n)_{2}$
denotes the binary expansion of some $n\in\mathbb{N}_{0}$, i.e.,

$\mathcal{P}_{2}\coloneqq\Biggl{(}\binom{(n)_{2}}{(k)_{2}}\Biggr{)}_{\begin{subarray}{c}n\geq
0\\\ k\geq 0\end{subarray}}.$

Observe that $\binom{(n)_{2}}{(0)_{2}}=1$ and $\binom{(n)_{2}}{(n)_{2}}=1$
hold for all $n\geq 0$. We let $z$ denote the sequence of interest and define
$z(n)$ as the number of non-zero elements in the $n$th row of
$\mathcal{P}_{2}$. The first few values of $\mathcal{P}_{2}$ are given in
Table 6.1, and the last column shows the first few values of $z$. Figure 6.1
illustrates the non-zero elements in $\mathcal{P}_{2}$.

| $k$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ |
---|---|---|---|---|---|---|---|---|---|---|---
$n$ |  $(n)_{2}$ $(k)_{2}$ | $\varepsilon$ | $1$ | $10$ | $11$ | $100$ | $101$ | $110$ | $111$ | $1000$ | $z(n)$
$0$ | $\varepsilon$ | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1
$1$ | $1$ | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 2
$2$ | $10$ | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 3
$3$ | $11$ | 1 | 2 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 3
$4$ | $100$ | 1 | 1 | 2 | 0 | 1 | 0 | 0 | 0 | 0 | 4
$5$ | $101$ | 1 | 2 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 5
$6$ | $110$ | 1 | 2 | 2 | 1 | 0 | 0 | 1 | 0 | 0 | 5
$7$ | $111$ | 1 | 3 | 0 | 3 | 0 | 0 | 0 | 1 | 0 | 4
$8$ | $1000$ | 1 | 1 | 3 | 0 | 3 | 0 | 0 | 0 | 1 | 5
Table 6.1: The first few elements of the generalized Pascal’s triangle
$\mathcal{P}_{2}$ as well as the corresponding number of non-zero elements in
each row. The values of the ordinary Pascal’s triangle are printed in bold.
Figure 6.1: Non-zero elements in the generalized Pascal’s triangle
$\mathcal{P}_{2}$

The following result by Leroy, Rigo and Stipulanti [29] provides a (at least
on the first glance) surprising connection between the number of non-zero
elements in $\mathcal{P}_{2}$ and Stern’s diatomic sequence.

######  Theorem 6.32 (Leroy–Rigo–Stipulanti [29, Section 4]).

The sequence $z$ satisfies the relation

$z(n)=d(2n+1)$

for all $n\geq 0$, where $d$ is Stern’s diatomic sequence as studied in
Section 5.

###  6.2 Regularity and a Linear Representation

In principle, Theorem 6.32 and the results on the asymptotics of Stern’s
diatomic sequence given in Section 5 could be used to determine the
asymptotics of $z$. However, it turns out that the error term in the
asymptotic expansion of $z$ vanishes. In order to show this, the results of
Section 5 are not sufficient, and we need to have a closer look at the linear
representation of $z$. Theorem 6.32 does not suffice for this purpose, so
instead we intend to present three different possibilities for obtaining a
linear representation. The first one will give some more details on the
reduction via Theorem 6.32, while the others will be based on the following
result, also by Leroy, Rigo and Stipulanti.

######  Theorem 6.33 (Leroy–Rigo–Stipulanti [29, Theorem 21]).

The sequence $z$ satisfies the recurrence relations

$\displaystyle z(2n+1)$ $\displaystyle=3z(n)-z(2n),$ (6.2a) $\displaystyle
z(4n)$ $\displaystyle=-z(n)+2z(2n),$ (6.2b) $\displaystyle z(4n+2)$
$\displaystyle=4z(n)-z(2n)$ (6.2c)

for all $n\geq 0$.

As already mentioned, the previous theorem as well as Theorem 6.32 provide
several possibilities to find a linear representation of $z$, and we discuss
three of them. As a side product of the second approach, it will also be clear
why $z$ is a recursive sequence and therefore fits into our framework.

#### Approach 1.

First of all, it is worth mentioning that we can use Theorem 6.32 to obtain a
$2$-linear representation: Since Stern’s diatomic sequence $d$ is $2$-regular
and $z(n)=d(2n+1)$ holds for all $n\in\mathbb{N}_{0}$, the $2$-regularity of
$z$ follows by Allouche and Shallit [1, Theorem 2.6]. In the proof of [1,
Theorem 2.6] we also find a description for the construction of a $2$-linear
representation of $z$ by using the linear representation of $d$. We do not
want to go into detail here.

#### Approach 2.

The recurrence relations in Theorem 6.33 are not directly in line with the
desired relations in the framework of $q$-recursive sequences as given in
(3.1). This second approach does not only lead to a desired linear
representation of $z$, but it also illustrates how recurrence relations as
given in (6.2) can be disentangled in order to obtain appropriate recurrence
relations for a $q$-recursive sequence. In fact, we will show that the
sequence $z$ is $2$-recursive, which directly implies that it is also
$2$-regular due to Theorem 3.15.

For this purpose, consider the system of equations

$\begin{pmatrix}-3&1&1&0&0&0&0\\\ 1&-2&0&1&0&0&0\\\ -4&1&0&0&0&1&0\\\
0&-3&0&1&1&0&0\\\ 0&0&-3&0&0&1&1\end{pmatrix}\begin{pmatrix}z\\\
z\circ(n\mapsto 2n)\\\ z\circ(n\mapsto 2n+1)\\\ z\circ(n\mapsto 4n)\\\
z\circ(n\mapsto 4n+1)\\\ z\circ(n\mapsto 4n+2)\\\ z\circ(n\mapsto 4n+3)\\\
\end{pmatrix}=0,$ (6.3)

where the first three rows correspond to the relations given in Theorem 6.33
and the last two rows arise from (6.2a) by replacing $n$ by $2n$ and by
$2n+1$, respectively.

We want to get a representation of $z$ as a $2$-recursive sequence. It turns
out that we can achieve such a sequence with exponents $M=2$ and $m=1$, so we
need explicit expressions for $z\circ(n\mapsto 4n)$, $z\circ(n\mapsto 4n+1)$,
$z\circ(n\mapsto 4n+2)$ and $z\circ(n\mapsto 4n+3)$ (corresponding to the last
four columns of the matrix). We also want these expressions to be free from
$z$ itself (corresponding to the first column of the matrix), so we transform
the system in such a way that an identity matrix appears in these columns.
Indeed, we multiply the system from the left with the inverse of the matrix
formed by these five columns and obtain

$\begin{pmatrix}0&\leavevmode\hbox to6.67pt{\vbox
to6.67pt{\pgfpicture\makeatletter\hbox{\hskip 3.33301pt\lower-3.33301pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}-\frac{5}{3}&\frac{1}{3}&1&0&0&0\\\
0&-\frac{4}{3}&-\frac{1}{3}\leavevmode\hbox to6.67pt{\vbox
to6.67pt{\pgfpicture\makeatletter\hbox{\hskip 3.33301pt\lower-3.33301pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}&0&1&0&0\\\
0&\leavevmode\hbox to6.67pt{\vbox
to6.67pt{\pgfpicture\makeatletter\hbox{\hskip 3.33301pt\lower-3.33301pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}-\frac{1}{3}&-\frac{4}{3}&0&0&1&0\\\
0&\frac{1}{3}&-\frac{5}{3}\leavevmode\hbox to6.67pt{\vbox
to6.67pt{\pgfpicture\makeatletter\hbox{\hskip 3.33301pt\lower-3.33301pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}&0&0&0&1\\\
1&-\frac{1}{3}&-\frac{1}{3}&0&0&0&0\end{pmatrix}\begin{pmatrix}z\\\
z\circ(n\mapsto 2n)\\\ z\circ(n\mapsto 2n+1)\\\ z\circ(n\mapsto 4n)\\\
z\circ(n\mapsto 4n+1)\\\ z\circ(n\mapsto 4n+2)\\\ z\circ(n\mapsto 4n+3)\\\
\end{pmatrix}=0.\leavevmode\hbox to2.8pt{\vbox
to14.1pt{\pgfpicture\makeatletter\hbox{\hskip 0.4pt\lower-4.4pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ { {}{}{}{}{}}{}{}{}{}{{}}{} {
{}{}{}{}{}}{}{}{{}{}}{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0.88,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.88,0}\pgfsys@color@cmyk@stroke{0.91}{0}{0.88}{0.12}\pgfsys@invoke{
}\pgfsys@color@cmyk@fill{0.91}{0}{0.88}{0.12}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0.88,0}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{9.30002pt}\pgfsys@moveto{0.0pt}{9.30002pt}\pgfsys@lineto{0.0pt}{-4.0pt}\pgfsys@lineto{2.0pt}{-4.0pt}\pgfsys@lineto{2.0pt}{9.30002pt}\pgfsys@closepath\pgfsys@moveto{2.0pt}{-4.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\leavevmode\hbox
to2.8pt{\vbox to14.1pt{\pgfpicture\makeatletter\hbox{\hskip
0.4pt\lower-4.4pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ { {}{}{}{}{}}{}{}{}{}{{}}{} {
{}{}{}{}{}}{}{}{{}{}}{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0.68,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0,0}\pgfsys@color@cmyk@stroke{0}{0.87}{0.68}{0.32}\pgfsys@invoke{
}\pgfsys@color@cmyk@fill{0}{0.87}{0.68}{0.32}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0.68,0,0}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{9.30002pt}\pgfsys@moveto{0.0pt}{9.30002pt}\pgfsys@lineto{0.0pt}{-4.0pt}\pgfsys@lineto{2.0pt}{-4.0pt}\pgfsys@lineto{2.0pt}{9.30002pt}\pgfsys@closepath\pgfsys@moveto{2.0pt}{-4.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$ (6.4)

Here the first four rows give the system

$\displaystyle z(4n)$ $\displaystyle=\frac{5}{3}z(2n)-\frac{1}{3}z(2n+1),$
$\displaystyle z(4n+1)$ $\displaystyle=\frac{4}{3}z(2n)+\frac{1}{3}z(2n+1),$
$\displaystyle z(4n+2)$ $\displaystyle=\frac{1}{3}z(2n)+\frac{4}{3}z(2n+1),$
$\displaystyle z(4n+3)$ $\displaystyle=-\frac{1}{3}z(2n)+\frac{5}{3}z(2n+1)$

for $n\geq 0$, which is a representation of $z$ as a $2$-recursive sequence
with offset $n_{0}=0$, exponents $M=2$ and $m=1$ and index shift bounds
$\ell=0$ and $u=1$. The last row of (6.4) can be omitted.

The matrices $B_{0}$ and $B_{1}$ as introduced in (3.11) are given by

$B_{0}=\frac{1}{3}\begin{pmatrix}\leavevmode\hbox to6.67pt{\vbox
to6.67pt{\pgfpicture\makeatletter\hbox{\hskip 3.33301pt\lower-3.33301pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}5&-1\\\
4&1\leavevmode\hbox to6.67pt{\vbox
to6.67pt{\pgfpicture\makeatletter\hbox{\hskip 3.33301pt\lower-3.33301pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox