to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\end{pmatrix}\mbox{\quad
as well as\quad}B_{1}=\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}}1&4\\\
-1&5\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
to8.5pt{\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{5.70001pt}{-2.0pt}\pgfsys@lineto{5.70001pt}{8.00002pt}\pgfsys@closepath\pgfsys@moveto{5.70001pt}{-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
to8.8pt{\vbox to10.8pt{\pgfpicture\makeatletter\hbox{\hskip
6.40001pt\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{-6.00002pt}{8.00002pt}\pgfsys@moveto{-6.00002pt}{8.00002pt}\pgfsys@lineto{-6.00002pt}{-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}}$

see also the marked submatrices in (6.4). We can now apply Theorem 3.15 and
obtain a $2$-linear representation $(A_{0},A_{1},v)$ of $z$ with dimension
$3$: The vector-valued sequence $v$ is given by

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

and due to (3.14), the matrices $A_{0}$ and $A_{1}$ have the form

$A_{0}=\frac{1}{3}\begin{pmatrix}0&3&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}}5&-1\\\
0&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
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\end{pmatrix}\mbox{\quad
and\quad}A_{1}=\frac{1}{3}\begin{pmatrix}0&0&3\\\ 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&4\\\
0&-1&5\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<EMAIL_ADDRESS>to8.5pt{\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{5.70001pt}{-2.0pt}\pgfsys@lineto{5.70001pt}{8.00002pt}\pgfsys@closepath\pgfsys@moveto{5.70001pt}{-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
to8.8pt{\vbox to10.8pt{\pgfpicture\makeatletter\hbox{\hskip
6.40001pt\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{-6.00002pt}{8.00002pt}\pgfsys@moveto{-6.00002pt}{8.00002pt}\pgfsys@lineto{-6.00002pt}{-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}}$

Note that by (6.2a) we know that the three sequences contained in $v$ are
linearly dependent. This means that we could replace $z\circ(n\mapsto 2n+1)$
by a linear combination of the other two sequences and obtain a linear
representation of dimension 2. However, we prefer to derive a linear
representation with this vector directly as Approach 3 below.

#### Approach 3.

Finally, we can also derive a linear representation of $z$ directly from the
recurrence relations given in Theorem 6.33. By setting

$v=\begin{pmatrix}z\\\ z\circ(n\mapsto 2n)\end{pmatrix},$ (6.5)

we obtain

$v(2n)=\begin{pmatrix}z(2n)\\\ z(4n)\end{pmatrix}=\begin{pmatrix}z(2n)\\\
-z(n)+2z(2n)\end{pmatrix}=\underbrace{\begin{pmatrix}0&1\\\
-1&2\end{pmatrix}}_{\eqqcolon A_{0}}v(n)$ (6.6a) as well as
$v(2n+1)=\begin{pmatrix}z(2n+1)\\\
z(4n+2)\end{pmatrix}=\begin{pmatrix}3z(n)-z(2n)\\\
4z(n)-z(2n)\end{pmatrix}=\underbrace{\begin{pmatrix}3&-1\\\
4&-1\end{pmatrix}}_{\eqqcolon A_{1}}v(n)$ (6.6b)

for all $n\in\mathbb{N}_{0}$. See also [29, Corollary 22].

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

###  6.3 Full Asymptotics

We now come to the main theorem of this section: We provide an explicit
formula for the summatory function $Z(N)=\sum_{0\leq n<N}z(n)$.

######  Theorem 6.34 (Full Asymptotics for the Number of Non-Zero Elements in
the generalized Pascal’s triangle $\mathcal{P}_{2}$).

The summatory function $Z$ of the sequence $z$ equals

$Z(N)=\smashoperator[]{\sum_{0\leq
n<N}^{}}z(n)=N^{\kappa}\cdot\Phi_{Z}(\\{\log_{2}N\\})$ (6.7)

for $N\geq 1$ with $\kappa=\log_{2}3$ and $\Phi_{Z}=2\Phi_{D}$, where
$\Phi_{D}$ is the periodic fluctuation which occurs in the asymptotic
expansion of Stern’s diatomic sequence in Theorem 5.28.

For a plot of $\Phi_{Z}$ see Figure 6.2.

Figure 6.2: Fluctuation in the asymptotic expansion of the summatory function
$Z$. The plot shows the periodic fluctuation $\Phi_{Z}(u)=2\Phi_{D}(u)$
approximated by its Fourier polynomial of degree $2000$ (red) as well as the
function $Z(2^{u})/2^{\kappa u}$ (blue).

######  Proof 6.35 (Proof of Theorem 6.34).

We use the $2$-dimensional linear representation $(A_{0},A_{1},v)$ given in
(6.5) and (6.6), and we want to apply [20, Theorem B] instead of Theorem 4.20
in order to get rid of the error term coming from Theorem 4.20.

The left eigenvectors of the matrix

$C=A_{0}+A_{1}=\begin{pmatrix}3&0\\\ 3&1\end{pmatrix}$

are given by $v_{1}=(1,-2/3)$, which corresponds to the eigenvalue
$\lambda=1$, and $v_{3}=(1,0)$, which corresponds to the eigenvalue
$\lambda=3$. Since the vector $v_{3}$ is equal to the left “choice vector”
$e_{1}$ of the linear representation (see (2.1)), it follows from [20, Section
6.3] that the eigenvalue $\lambda=3$ is the only one which contributes to the
summatory function.

By the above observations, the matrix $C$ has the Jordan decomposition
$C=T^{-1}JT$ with

$J=\begin{pmatrix}3&0\\\ 0&1\end{pmatrix}\mbox{\quad
and\quad}T=\begin{pmatrix}1&0\\\ 1&-2/3\end{pmatrix}.$

With the notation introduced in [20, Section 6.2], we moreover have

$D=\begin{pmatrix}1&0\\\ 0&0\end{pmatrix}\mbox{\quad
and\quad}C^{\prime}=T^{-1}DJT=\begin{pmatrix}3&0\\\ 9/2&0\end{pmatrix}$

as well as

$K=T^{-1}DT(I_{2}-C^{\prime})^{-1}(I_{2}-A_{0})=\begin{pmatrix}-1/2&1/2\\\
-3/4&3/4\end{pmatrix},$

where $I_{2}$ denotes the $2\times 2$ identity matrix. Due to Theorem 6.32 and
the second paragraph of the proof of Theorem 5.28, we can choose
$R=\varphi=\frac{1+\sqrt{5}}{2}$. Now we are ready to apply [20, Theorem B]
for the eigenvalue $\lambda=3$. By noting $Kv(0)=0$, we obtain

$Z(N)=N^{\kappa}\cdot\Phi_{Z}(\\{\log_{2}N\\}),$ (6.8)

where $\Phi_{Z}$ is a $1$-periodic function which is Hölder continuous with
any exponent smaller than $\kappa-\log_{2}\varphi$.

Finally, we argue that $\Phi_{Z}=2\Phi_{D}$. Due to Theorem 6.32 and (5.1b),
we have

$\displaystyle Z(N)$ $\displaystyle=\smashoperator[]{\sum_{0\leq n<N}^{}}z(n)$
$\displaystyle=\smashoperator[]{\sum_{0\leq n<N}^{}}d(2n+1)$
$\displaystyle=\smashoperator[]{\sum_{0\leq
n<N}^{}}d(n)+\smashoperator[]{\sum_{0\leq n<N}^{}}d(n+1)$
$\displaystyle=2D(N)+d(N)$ (6.9) $\displaystyle=2D(N)+O(N^{\log_{2}\varphi})$

as $N\to\infty$. Applying Theorem 5.28 on $D(N)$ and combining the result with
(6.8) yields

$N^{\kappa}\cdot\Phi_{Z}(\\{\log_{2}N\\})=N^{\kappa}\cdot
2\Phi_{D}(\\{\log_{2}N\\})+O(N^{\log_{2}\varphi}).$

Since the set $\\{\\{\log_{2}N\\}\,|\,\mathopen{}N\in\mathbb{N}\\}$ is dense
in the interval $[0,1]$ and both $\Phi_{Z}$ and $2\Phi_{D}$ are continuous,
they have to be equal. This concludes the proof.

We are now able to prove Corollary 5.30.

######  Proof 6.36 (Proof of Corollary 5.30).

The statement of the corollary follows from combining (6.9) with Theorem 6.34.

##  7 Number of Unbordered Factors in the Thue–Morse Sequence

###  7.1 Introduction of the Sequence

The Thue–Morse sequence $t$ is the parity sequence of the binary sum of
digits; see [34, A010060]. In this section, we study the number of unbordered
factors in the Thue–Morse sequence, which are a special kind of subsequences
of $t$. Unbordered factors of the Thue–Morse sequence were first investigated
by Currie and Saari in [12]. Some more interesting insights concerning this
special type of factors can, for example, be found in Charlier, Rampersad and
Shallit [9] and Goč, Henshall and Shallit [16]; see also Goč, Rampersad, Rigo
and Salimov [18].

Before we formally define the sequence of study, we give the following
definitions from combinatorics on words, which can, for example, also be found
in Lothaire [32].

######  Definition 7.37 (Unbordered Factor).

Let $\mathcal{A}$ be an alphabet and $x\colon\mathbb{N}_{0}\to\mathcal{A}$ a
sequence.

  1. 1.

For integers $0\leq i\leq j$, we let $x[i\,.\,.\,j]$ denote the subword
$x(i)x(i+1)\ldots x(j-1)x(j)$ of the infinite word $x(0)x(1)x(2)x(3)\dots$.

  2. 2.

We say that a word $w\in\mathcal{A}^{\star}$ is a _factor of $x$_ if there
exist integers $0\leq i\leq j$ such that $w=x[i\,.\,.\,j]$.

  3. 3.

A word $w\in\mathcal{A}^{\star}$ is said to be _bordered_ if there exists a
non-empty word $v\neq w$ which is both a prefix and a suffix of $w$. In this
case we call $v$ a _border_ of $w$. If $w$ is not bordered, then it is said to
be _unbordered_.

In particular, this implies that the empty word $\varepsilon$ as well as every
word of length $1$ is unbordered. Moreover, a word $w=ab$ of length $2$ with
$a$, $b\in\mathcal{A}$ is unbordered if and only if $a\neq b$.

We illustrate the previous definitions by the following example.

######  Example 7.38 (Some (Un)Bordered Factors of the Thue–Morse Sequence).

If we write the Thue–Morse sequence as an infinite word $t=t(0)t(1)t(2)\dots$,
then it starts with

$t=01101001\,10010110\,10010110\,01101001\dots.$

We visually structured the sequence into blocks of eight letters in order to
emphasize some of its properties. Some bordered factors of $t$ are given in
Table 7.1, whereas the factors in Table 7.2 are unbordered.

bordered factor | border | length
---|---|---
$t[5\,.\,.\,6]=00$ | $0$ | $2$
$t[1\,.\,.\,2]=11$ | $1$ | $2$
$t[3\,.\,.\,5]=010$ | $0$ | $3$
$t[2\,.\,.\,4]=101$ | $1$ | $3$
$t[2\,.\,.\,5]=1010$ | $10$ | $4$
$t[0\,.\,.\,9]=0110100110$ | $0110$ | $10$
Table 7.1: Some bordered factors of the Thue–Morse sequence $t$ unbordered factor | length
---|---
$\varepsilon$ | $0$
$t[0\,.\,.\,0]=0$ | $1$
$t[1\,.\,.\,1]=1$ | $1$
$t[0\,.\,.\,1]=01$ | $2$
$t[2\,.\,.\,3]=10$ | $2$
$t[0\,.\,.\,2]=011$ | $3$
$t[1\,.\,.\,3]=110$ | $3$
$t[4\,.\,.\,6]=100$ | $3$
$t[5\,.\,.\,7]=001$ | $3$
Table 7.2: All unbordered factors of the Thue–Morse sequence $t$ up to length
$3$

It is easy to check that Table 7.2 contains a complete list of the unbordered
factors of the Thue–Morse sequence with length smaller than $4$.

Now the following question may arise: Is there an unbordered factor of $t$
with length $n$ for every $n\geq 0$? Currie and Saarie showed in [12] that $t$
has an unbordered factor of length $n$ if $n\not\equiv
1{\@displayfalse\pmod{6}}$. However, since

$t[39\,.\,.\,69]=0011010010110100110010110100101$

is an unbordered factor of length $31$ in $t$, the given condition is not
necessary. Goč, Henshall and Shallit finally proved the following
characterization.

######  Theorem 7.39 (Goč, Henshall and Shallit [16, Theorem 4]).

There is an unbordered factor of length $n$ in $t$ if and only if
$(n)_{2}\notin 1(01^{*}0)^{*}10^{*}1$, where $(n)_{2}$ denotes the binary
digit expansion of $n\in\mathbb{N}_{0}$ and $1(01^{*}0)^{*}10^{*}1$ has to be
considered as a regular expression.

In this article, we are interested in the number of unbordered factors of
length $n$ in $t$; cf. [34, A309894]. We let $f$ denote this sequence. The
first few elements of this sequence are given in Table 7.3.

$n$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ | $11$ | $12$ | $13$ | $14$ | $15$ | … | $23$
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$f(n)$ | $1$ | $2$ | $2$ | $4$ | $2$ | $4$ | $6$ | $0$ | $4$ | $4$ | $4$ | $4$ | $12$ | $0$ | $4$ | $4$ | … | $8$
Table 7.3: First few elements of the sequence $f$ which counts the number of
unbordered factors in the Thue–Morse sequence of length $n$

Theorem 7.39 characterizes the numbers $n$ with $f(n)=0$. However, for our
purpose, this is not satisfying since we are interested in the numbers $f(n)$
themselves. In particular, we hope that $f$ is regular and that we can
determine a linear representation for it, which consequently can be used to
derive an asymptotic result for the summatory function of $f$.

Finally, before we come to the determination of a linear representation of
$f$, the authors in [17] also investigated the growth rate of $f$, which is
given as follows.

######  Theorem 7.40 (Goč, Mousavi and Shallit [17, Theorem 2]).

The inequality $f(n)\leq n$ holds for all $n\geq 4$, with $f(n)=n$ infinitely
often. This implies

$\limsup_{n\geq 1}\frac{f(n)}{n}=1.$

###  7.2 Regularity and a Linear Representation

Goč, Mousavi and Shallit came up with the following recurrence relations,
which will help us to conclude that $f$ is $2$-regular and to construct a
$2$-linear representation of $f$.

######  Theorem 7.41 (Goč, Mousavi and Shallit [17, Proof of Theorem 2]).

For the number $f(n)$ of unbordered factors of length $n$ in the Thue–Morse
sequence, we have

$\displaystyle f(4n)$ $\displaystyle=2f(2n),$ $\displaystyle(n\geq 2)$
$\displaystyle f(4n+1)$ $\displaystyle=f(2n+1),$ $\displaystyle(n\geq 0)$
$\displaystyle f(8n+2)$ $\displaystyle=f(2n+1)+f(4n+3),$ $\displaystyle(n\geq
1)$ $\displaystyle f(8n+3)$ $\displaystyle=-f(2n+1)+f(4n+2),$
$\displaystyle(n\geq 2)$ $\displaystyle f(8n+6)$
$\displaystyle=-f(2n+1)+f(4n+2)+f(4n+3),$ $\displaystyle(n\geq 2)$
$\displaystyle f(8n+7)$ $\displaystyle=2f(2n+1)+f(4n+3).$ $\displaystyle(n\geq
3)$

This directly yields the following corollary.

######  Corollary 7.42.

For the number $f(n)$ of unbordered factors of length $n$ in the Thue–Morse
sequence, we have

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

In particular, $f$ is $2$-recursive with offset $n_{0}=3$, exponents $M=3$ and
$m=2$ and index shift bounds $\ell=0$ and $u=3$.

Together with the initial values given in Table 7.3, the recurrence relations
stated in the previous corollary completely describe the sequence $f$.

In order to obtain a $2$-linear representation of $f$, we first of all use
Theorem 3.15 (instead of Theorem 3.7 which would lead to a linear
representation of larger dimension). This will give us matrices $A_{0}$ and
$A_{1}$ as well as a vector-valued sequence $v$ such that the relations
$v(2n)=A_{0}v(n)$ and $v(2n+1)=A_{1}v(n)$ hold for all $n\geq 3$, i.e., a
$2$-linear representation with offset $3$ of $f$.

With the notation of Theorem 3.15, the matrices $B_{0}$ and $B_{1}$ are given
by

$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}}2&0&0&0\\\ 0&1&0&0\\\
0&1&0&1\\\ 0&-1&1&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}}\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}}0&0&2&0\\\ 0&0&0&1\\\
0&-1&1&1\\\ 0&2&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}}\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}}$ (7.1)

where the relevant spectrum—relevant with respect to Proposition 4.25—is

$\sigma(B_{0}+B_{1})=\big{\\{}-\sqrt{3}+1,1,2,\sqrt{3}+1\big{\\}},$

and all eigenvalues are simple.

We now apply Theorem 3.15 and obtain

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

as well as the matrices

$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&1&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&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&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}}2&0&0&0\\\
0&0&0&0&1&0&0\\\ 0&0&0&0&1&0&1\\\ 0&0&0&0&-1&1&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}}\\\
\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]{.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}}\text{\ \ and\ \
}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&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&0\\\
0&0&0&0&0&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}}0&0&2&0\\\
0&0&0&0&0&0&1\\\ 0&0&0&0&-1&1&1\\\ 0&0&0&0&2&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<EMAIL_ADDRESS>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}}\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}}$ (7.2)

Next, we use Theorem 3.11 in order to “adjust” the initial values of the
recurrence relations of $f$ given by Corollary 7.42 for $0\leq n\leq 2$.

For this purpose we recall the notation
$\delta_{k}\colon\mathbb{N}_{0}\to\mathbb{C}$ with
$\delta_{k}(n)\coloneqq\llbracket n=k\rrbracket$ for $0\leq k\leq 2$ as
introduced in Theorem 3.11 and set

$w_{r,k}\coloneqq v(2k+r)-A_{r}v(k)$

for $0\leq k\leq 2$ and $0\leq r<2$. Then the matrices
$W_{0}=(w_{0,0},w_{0,1},w_{0,2})$ and $W_{1}=(w_{1,0},w_{1,1},w_{1,2})$ are
given by

$W_{0}=\begin{pmatrix}0&0&0\\\ 0&0&0\\\ 0&0&0\\\ -1&0&0\\\ 0&0&0\\\ -4&0&0\\\
4&2&0\end{pmatrix}\mbox{\quad and\quad}W_{1}=\begin{pmatrix}0&0&0\\\ 0&0&0\\\
0&0&0\\\ -2&0&0\\\ 0&0&0\\\ 2&2&0\\\ -8&-4&-4\end{pmatrix}.$

Moreover, recall that we have introduced matrices $J_{0}$ and $J_{1}$ in (3.9)
by

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

which in this example gives

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

Then by Theorem 3.11 we obtain a $2$-linear representation
$(\widetilde{A}_{0},\widetilde{A}_{1},\widetilde{v})$ of $f$ by the vector
$\widetilde{v}$ given in block form as

$\widetilde{v}=\begin{pmatrix}v\\\ \delta_{0}\\\ \delta_{1}\\\
\delta_{2}\end{pmatrix}$

as well as the block matrices

$\widetilde{A}_{0}=\begin{pmatrix}A_{0}&W_{0}\\\
0&J_{0}\end{pmatrix}\mbox{\quad
and\quad}\widetilde{A}_{1}=\begin{pmatrix}A_{1}&W_{1}\\\
0&J_{1}\end{pmatrix}.$ (7.3)

This final $2$-linear representation has dimension $10$. By applying the
minimization algorithm mentioned in Remark 3.8 (3), we see that the smallest
possible $2$-linear representation of $f$ has dimension $8$.

###  7.3 Joint Spectral Radius

Next, we determine the joint spectral radius of $B_{0}$ and $B_{1}$, which we
need to determine the asymptotics of the summatory function of $f$ in the next
section.

######  Lemma 7.43.

The joint spectral radius of $\mathcal{B}=\\{B_{0},B_{1}\\}$ is $2$ and
$\mathcal{B}$ has the simple growth property.

######  Proof 7.44.

As usual, $\lVert\,\cdot\,\rVert_{\infty}$ denotes the maximum norm of a
vector and the row sum norm of a matrix. Let

$T\coloneqq\operatorname{diag}(2,1/2,1,1)$

and consider the vector norm $\lVert\,\cdot\,\rVert_{T}$ defined by $\lVert
v\rVert_{T}\coloneqq\lVert T^{-1}v\rVert_{\infty}$. This vector norm induces
the matrix norm $\lVert\,\cdot\,\rVert_{T}$ defined by $\lVert
G\rVert_{T}\coloneqq\lVert T^{-1}GT\rVert_{\infty}$.

We consider all products of two matrices in $\mathcal{B}$ and get

$\displaystyle T^{-1}B_{0}^{2}T$ $\displaystyle=\begin{pmatrix}4&0&0&0\\\
0&1&0&0\\\ 0&0&1&0\\\ 0&0&0&1\end{pmatrix},$ $\displaystyle T^{-1}B_{0}B_{1}T$
$\displaystyle=\begin{pmatrix}0&0&2&0\\\ 0&0&0&2\\\ 0&1&0&2\\\
0&-\frac{1}{2}&1&0\end{pmatrix},$ $\displaystyle T^{-1}B_{1}B_{0}T$
$\displaystyle=\begin{pmatrix}0&\frac{1}{2}&0&1\\\ 0&-1&2&0\\\
0&-\frac{1}{2}&1&1\\\ 0&\frac{1}{2}&1&0\end{pmatrix},$ $\displaystyle
T^{-1}B_{1}^{2}T$ $\displaystyle=\begin{pmatrix}0&-\frac{1}{2}&1&1\\\
0&2&0&2\\\ 0&\frac{1}{2}&1&1\\\ 0&1&0&3\end{pmatrix}.$

We observe that all these matrices have row sum norm at most $4$, which
implies that

$\max\\{\lVert G_{1}G_{2}\rVert_{T}\mid G_{1},G_{2}\in\mathcal{B}\\}=4$

and therefore $\rho(\mathcal{B})\leq 2$. Furthermore, we observe that $\lVert
B_{0}^{k}\rVert_{T}=2^{k}$ holds for all even positive integers $k$. We
conclude that $\rho(\mathcal{B})=2$ and that $\mathcal{B}$ has the finiteness
property and thus the simple growth property.

######  Remark 7.45.

As announced in Remark 4.19, the finiteness property may depend on the chosen
norm. Indeed, the set $\mathcal{B}$ in Lemma 7.43 has the finiteness property
with respect to the norm considered in the proof of Lemma 7.43, but does not
have the finiteness property with respect to the row sum norm: By computing
the eigendecomposition of $B_{1}$ or by induction on $k$, we obtain that the
last row of $B_{1}^{k}$ is

$\Bigl{(}0,\ \frac{2}{3}(2^{k}-(-1)^{k}),\ 0,\ \frac{1}{3}(2\cdot
2^{k}+(-1)^{k})\Bigr{)}$

for $k\geq 0$. In particular,

$\lVert
B_{1}^{k}\rVert_{\infty}\geq\frac{4}{3}2^{k}-\frac{1}{3}(-1)^{k}>2^{k}$

holds for all $k\geq 1$.

###  7.4 Asymptotics

Let $\eta\geq 1$ be an integer. We define the Dirichlet series

$\mathcal{F}_{j}(s)\coloneqq\sum_{n\geq\eta}\frac{f(4n+j)}{(4n+j)^{s}}$

for $0\leq j\leq 3$ and set

$\mathcal{F}(s)\coloneqq\begin{pmatrix}\mathcal{F}_{0}(s)\\\
\mathcal{F}_{1}(s)\\\ \mathcal{F}_{2}(s)\\\ \mathcal{F}_{3}(s)\end{pmatrix}.$

In the following theorem, we state the main result of this section: We give an
asymptotic formula for $F(N)\coloneqq\sum_{0\leq n<N}f(n)$.

######  Theorem 7.46 (Asymptotics for the Number of Unbordered Factors).

The summatory function $F$ of the number $f(n)$ of unbordered factors of
length $n$ in the Thue–Morse sequence satisfies

$F(N)=\smashoperator[]{\sum_{0\leq
n<N}^{}}f(n)=N^{\kappa}\cdot\Phi_{F}(\\{\log_{2}N\\})+O(N\log N)$

as $N\to\infty$, where $\kappa=\log_{2}(1+\sqrt{3})=1.44998431347650\ldots$
and $\Phi_{F}$ is a $1$-periodic continuous function which is Hölder
continuous with any exponent smaller than $\kappa-1$. The Fourier coefficients
of $\Phi_{F}$ can be computed efficiently.

Furthermore, the Dirichlet series $\mathcal{F}$ satisfies the functional
equation

$\bigl{(}I-2^{-s}(B_{0}+B_{1})\bigr{)}\mathcal{F}(s)=\begin{pmatrix}\mathcal{G}_{0}(s)\\\
\mathcal{G}_{1}(s)\\\ \mathcal{G}_{2}(s)\\\ \mathcal{G}_{3}(s)\end{pmatrix}$
(7.4)

for $\real s>1$, where $B_{0}$ and $B_{1}$ are the matrices given in (7.1),
and

$\mathcal{G}_{j}(s)=2^{-s}\sum_{k=0}^{3}\Biggl{(}\sum_{n\geq
1}\binom{-s}{n}\biggl{(}c_{j,k}\Bigl{(}\frac{j}{2}-k\Bigr{)}^{n}+c_{j+4,k}\Bigl{(}\frac{j+4}{2}-k\Bigr{)}^{n}\biggr{)}\mathcal{F}_{k}(s+n)\Biggr{)}+\
\smashoperator[l]{\sum_{\eta\leq n<2\eta}^{}}\frac{f(4n+j)}{(4n+j)^{s}},$

where $(c_{j,k})_{0\leq j<8,0\leq k\leq 3}$ are the coefficients of the
$2$-recursive sequence in Corollary 7.42. Moreover, $\mathcal{G}_{j}(s)$ is
analytic for $\real s>1$ and $0\leq j\leq 3$, and, in particular,
$\mathcal{F}(s)$ is meromorphic for $\real s>1$ and can only have poles
$s=\log_{2}(\sqrt{3}+1)+\frac{2\pi i\mu}{\log 2}$ with $\mu\in\mathbb{Z}$.

Table 7.4 and Figure 7.1 show the first few Fourier coefficients and a plot of
the periodic fluctuation of Theorem 7.46, respectively.

$\mu$ | $\varphi_{\mu}$
---|---
$0$ | $\phantom{-}1.081200224751780$
$1$ | $-0.0012296808157996+0.0157152473714320i$
$2$ | $-0.0013742386970566-0.0110033266904103i$
$3$ | $\phantom{-}0.0083338522036749+0.0034850861320328i$
$4$ | $-0.0042230458157050-0.0017461310727764i$
$5$ | $\phantom{-}0.0064055951023042-0.0018152583716649i$
$6$ | $\phantom{-}0.0004060978191922+0.0003312870598610i$
$7$ | $\phantom{-}0.0000421719576760-0.0039180258068148i$
$8$ | $-0.0001216226961034+0.0017930566948364i$
$9$ | $-0.0010960361908015-0.0012530549651823i$
$10$ | $\phantom{-}0.0024882524350784-0.0009385940552233i$
Table 7.4: First few Fourier coefficients of $\Phi_{F}$ Figure 7.1:
Fluctuation in the main term of the asymptotic expansion of the summatory
function $F$. The plot shows the periodic fluctuation $\Phi_{F}(u)$
approximated by its Fourier series of degree $2000$ (red) as well as the
function $F(2^{u})/2^{\kappa u}$ (blue).

######  Proof 7.47 (Proof of Theorem 7.46).

We use Theorem 4.20 with the linear representation
$(\widetilde{A}_{0},\widetilde{A}_{1},\widetilde{v})$ of $f$ as obtained in
Section 7.2. For this purpose, we work out the parameters needed in the
theorem.

_Joint Spectral Radius._ Due to Lemma 7.43, Proposition 4.26 and Proposition
4.24, the joint spectral radius of $\widetilde{A}_{0}$ and $\widetilde{A}_{1}$
is $2$. Moreover, the simple growth property holds. So we set $R=2$.

_Eigenvalues._ Let $\widetilde{C}=\widetilde{A}_{0}+\widetilde{A}_{1}$. We
could of course directly calculate the eigenvalues of $\widetilde{C}$.
However, we want to emphasize the relation to the matrices $B_{0}$ and $B_{1}$
as given in (7.1) and thus, to the recurrence relations given by the property
that the sequence $f$ is $2$-recursive. Let $A_{0}$ and $A_{1}$ be the
matrices in (7.2) and set $C\coloneqq A_{0}+A_{1}$. Then applying Proposition
4.25 yields

$\sigma(C)=\sigma(B_{0}+B_{1})\cup\\{0\\}$

as well as $m_{C}(\lambda)=m_{B_{0}+B_{1}}(\lambda)$ for
$\lambda\in\sigma(B_{0}+B_{1})$, and we recall that

$\sigma(B_{0}+B_{1})=\big{\\{}-\sqrt{3}+1,1,2,\sqrt{3}+1\big{\\}};$

see Section 7.2. Moreover, all eigenvalues of $B_{0}+B_{1}$ are simple and
thus, we have $m_{C}(\lambda)=1$ for all $\lambda\in\sigma(B_{0}+B_{1})$.

Due to Proposition 4.22, we have

$\sigma(\widetilde{C})=\sigma(C)\cup\\{0,1\\}$

and $m_{\widetilde{C}}(\lambda)=m_{C}(\lambda)$ for
$\lambda\in\sigma(B_{0}+B_{1})\setminus\\{1\\}$. All in all, this means for
the spectrum of $\widetilde{C}$ that

$\sigma(\widetilde{C})=\sigma(C)\cup\\{0,1\\}=\sigma(B_{0}+B_{1})\cup\\{0,1\\}=\\{-\sqrt{3}+1,0,1,2,\sqrt{3}+1\\}.$

So the only relevant eigenvalues of $\widetilde{C}$, i.e., the only
eigenvalues $\lambda$ with $\lvert\lambda\rvert\geq R$, are $\sqrt{3}+1$ with
$m_{\widetilde{C}}(\sqrt{3}+1)=1$ and $2$ with $m_{\widetilde{C}}(2)=1$.

Now applying Theorem 4.20 yields the result for the asymptotic expansion.
Finally, Proposition 4.27 implies the correctness of the functional equation
as stated in (7.4).

##  8 Proofs

###  8.1 Proofs of the Reductions to $q$-Regular Sequences in the General Case

For the proof of Theorem 3.7, we need the following lemma.

######  Lemma 8.48.

Let $q\geq 2$, $M>m\geq 0$ and $\ell\leq u$ be integers, and let
$\ell^{\prime}$ and $u^{\prime}$ be as defined in (3.2). Furthermore, let $d$
be an integer with $\ell^{\prime}\leq d\leq q^{M-1}-q^{m}+u^{\prime}$ and
write $d=d^{\prime}q^{M}+r^{\prime}$ with $0\leq r^{\prime}<q^{M}$ and
$d^{\prime}\in\mathbb{Z}$. Then we have

$\ell^{\prime}\leq q^{m}d^{\prime}+\ell\mbox{\quad
and\quad}q^{m}d^{\prime}+u\leq u^{\prime}.$ (8.1)

If additionally $r^{\prime}\geq q^{M-1}$ holds, then

$q^{m}d^{\prime}+q^{m}+u\leq u^{\prime}.$ (8.2)

######  Proof 8.49.

First of all, we note that the equalities

$\Big{\lfloor}\frac{\lfloor
x\rfloor+a}{b}\Big{\rfloor}=\Big{\lfloor}\frac{x+a}{b}\Big{\rfloor}\mbox{\quad
and\quad}\Big{\lceil}\frac{\lceil
x\rceil+a}{b}\Big{\rceil}=\Big{\lceil}\frac{x+a}{b}\Big{\rceil}$ (8.3)

hold for all $x\in\mathbb{R}$ and $a$, $b\in\mathbb{Z}$ with $b>0$; see
Graham, Knuth and Patashnik [19, p. 72].

We now show that the left inequality of (8.1) is true. If $\ell\geq 0$, then
$\ell^{\prime}=0$ and the inequality follows. If $\ell<0$, then we have

$\displaystyle q^{m}d^{\prime}+\ell$
$\displaystyle=\frac{d-r^{\prime}}{q^{M-m}}+\ell$
$\displaystyle>\frac{\ell^{\prime}-q^{M}+\ell q^{M-m}}{q^{M-m}}$
$\displaystyle=\frac{\big{\lfloor}\frac{(\ell+1)q^{M-m}-q^{M}}{q^{M-m}-1}\big{\rfloor}-q^{M}+\ell
q^{M-m}}{q^{M-m}}$
$\displaystyle\geq\Bigg{\lfloor}\frac{\big{\lfloor}\frac{(\ell+1)q^{M-m}-q^{M}}{q^{M-m}-1}\big{\rfloor}-q^{M}+\ell
q^{M-m}}{q^{M-m}}\Bigg{\rfloor}$
$\displaystyle\stackrel{{\scriptstyle\stackrel{{\scriptstyle\text{\eqref{eq:graham-
floor}}}}{{\downarrow}}}}{{=}}\Bigg{\lfloor}\frac{\frac{(\ell+1)q^{M-m}-q^{M}}{q^{M-m}-1}-q^{M}+(\ell+1)q^{M-m}}{q^{M-m}}-1\Bigg{\rfloor}$
$\displaystyle=\bigg{\lfloor}\frac{(\ell+1)q^{M-m}-q^{M}}{q^{M-m}-1}\bigg{\rfloor}-1=\ell^{\prime}-1,$

which is equivalent to $\ell^{\prime}\leq q^{m}d^{\prime}+\ell$.

For the remaining two inequalities, we distinguish between negative and non-
negative upper bounds $u$.

Case 1:

$u\leq-1$. This implies $u^{\prime}=q^{m}-1$ and as a consequence, we have
$d\leq q^{M-1}-1$ as well as $d^{\prime}\leq 0$. The right inequality of (8.1)
as well as (8.2) follow directly.

Case 2:

$u\geq 0$. This implies
$u^{\prime}=q^{m}-1+\big{\lceil}\frac{uq^{M-m}}{q^{M-m}-1}\big{\rceil}$, and
we have

$\displaystyle q^{m}d^{\prime}+u$
$\displaystyle=\frac{d-r^{\prime}}{q^{M-m}}+u\leq\frac{u^{\prime}+q^{M-1}-q^{m}+uq^{M-m}}{q^{M-m}}$
$\displaystyle<\frac{u^{\prime}+q^{M}-q^{m}+uq^{M-m}}{q^{M-m}}$ (8.4)
$\displaystyle=\frac{q^{m}-1+\big{\lceil}\frac{uq^{M-m}}{q^{M-m}-1}\big{\rceil}+q^{M}-q^{m}+uq^{M-m}}{q^{M-m}}$
$\displaystyle<q^{m}+\frac{\big{\lceil}\frac{uq^{M-m}}{q^{M-m}-1}\big{\rceil}+uq^{M-m}}{q^{M-m}}$
$\displaystyle\leq
q^{m}+\Bigg{\lceil}\frac{\big{\lceil}\frac{uq^{M-m}}{q^{M-m}-1}\big{\rceil}+uq^{M-m}}{q^{M-m}}\Bigg{\rceil}$
$\displaystyle\stackrel{{\scriptstyle\stackrel{{\scriptstyle\text{\eqref{eq:graham-
floor}}}}{{\downarrow}}}}{{=}}q^{m}+\Bigg{\lceil}\frac{\frac{uq^{M-m}}{q^{M-m}-1}+uq^{M-m}}{q^{M-m}}\Bigg{\rceil}$
$\displaystyle=q^{m}+\bigg{\lceil}\frac{uq^{M-m}}{q^{M-m}-1}\bigg{\rceil}=u^{\prime}+1.$

This is equivalent to $q^{m}d^{\prime}+u\leq u^{\prime}$, and (8.1) is shown.
Now let $r^{\prime}\geq q^{M-1}$, then it follows that

$\displaystyle q^{m}d^{\prime}+q^{m}+u$
$\displaystyle=\frac{d-r^{\prime}}{q^{M-m}}+q^{m}+u$
$\displaystyle\leq\frac{u^{\prime}+q^{M-1}-q^{m}-q^{M-1}+q^{M}+uq^{M-m}}{q^{M-m}}$
$\displaystyle=\frac{u^{\prime}+q^{M}-q^{m}+uq^{M-m}}{q^{M-m}}.$

We can now use the same steps as above (from (8.4) on) and obtain
$q^{m}d^{\prime}+q^{m}+u\leq u^{\prime}$, which shows that (8.2) holds. This
completes the proof.

######  Proof 8.50 (Proof of Theorem 3.7).

Let $v$ be as stated in Theorem 3.7 and let $(c_{r,k})_{0\leq r<q^{M},\ell\leq
k\leq u}$ be the coefficients of the $q$-recursive sequence $x$. We have to
show that there are matrices $A_{0}$, $\ldots$, $A_{q-1}$ such that
$v(qn+r)=A_{r}v(n)$ holds for all $n\geq n_{1}$ and $0\leq r<q$, as required
in the definition of regular sequences. This is equivalent to the property
that each component of $v(qn+r)$ is a linear combination of the entries in
$v(n)$, where all sequences are restricted to $n\geq n_{1}$.

We fix $0\leq r<q$ and split the proof into three parts depending on the
indices of the blocks $v_{j}$ of $v$ as introduced in (3.3). In each part, the
choice of the components of $v$ as defined in (3.4a) and (3.4b) allows to
represent $v_{j}(qn+r)$ as a linear combination of the entries of $v$.

Furthermore, we let $\operatorname{ind}_{v}(x\circ(n\mapsto q^{j}n+d))$ denote
the absolute position of some sequence $x\circ(n\mapsto q^{j}n+d)$ in the
vector $v$, absolute in the sense that we disregard the block form of
$v$.121212We assume that the operator $\operatorname{ind}_{v}$ is
“intelligent” enough to recognize the sequence $x\circ(n\mapsto q^{j}n+d)$ in
$v$ by the parameters $j$ and $d$, even if there are other sequences in $v$
that are equal to $x\circ(n\mapsto q^{j}n+d)$ (in the sense that all elements
of the sequences are equal). For reasons of simplicity and readability, we
refrain from develop this more explicitly at this point. Moreover, we write
$v_{j,d}$ for the sequence $x\circ(n\mapsto q^{j}n+d)$ where this notation is
convenient.

#### Part 1.

At first, we consider blocks $v_{j}$ of $v$ with $0\leq j<m$.

_Components of $v_{j}$:_ Let $0\leq d<q^{j}$ and consider the component
$v_{j,d}=x\circ(n\mapsto q^{j}n+d)$ of $v$. Then we get

$\displaystyle v_{j,d}(qn+r)$ $\displaystyle=x\bigl{(}q^{j}(qn+r)+d\bigr{)}$
$\displaystyle=x(q^{j+1}n+q^{j}r+d).$

We claim that $x\circ(n\mapsto q^{j+1}n+q^{j}r+d)$ is a component of
$v_{j+1}$. To show this, we first observe that

$0\leq q^{j}r+d\leq q^{j}(q-1)+q^{j}-1=q^{j+1}-1.$ (8.5)

For $j\leq m-2$, this immediately proves the claim. If $j=m-1$, then the
estimates $\ell^{\prime}\leq 0$ (see Remark 3.8) and $q^{j+1}-1=q^{m}-1\leq
u^{\prime}$ together with (8.5) ensure the validity of the claim.

_Corresponding Rows of $A_{r}$:_ The previous considerations imply that the
row $\operatorname{ind}_{v}(v_{j,d})$ of $A_{r}$ has zeros in every entry
except one. Specifically, the entry in column
$\operatorname{ind}_{v}\bigl{(}v_{j+1,q^{j}r+d}\bigr{)}$ is $1$.

#### Part 2.

Secondly, we consider blocks $v_{j}$ of $v$ with $m\leq j\leq M-2$.

_Components of $v_{j}$:_ Let $\ell^{\prime}\leq d\leq q^{j}-q^{m}+u^{\prime}$.
Then the sequence $x\circ(n\mapsto q^{j}n+d)$ is a component of $v_{j}$ and it
holds that

$x\bigl{(}q^{j}(qn+r)+d\bigr{)}=x(q^{j+1}n+q^{j}r+d)$

with

$\ell^{\prime}\leq d\leq q^{j}r+d\leq
q^{j}(q-1)+q^{j}-q^{m}+u^{\prime}=q^{j+1}-q^{m}+u^{\prime}.$

This implies that the sequence $x\circ(n\mapsto q^{j}(qn+r)+d)$ is a component
of $v$, namely in the block $v_{j+1}$.

_Corresponding Rows of $A_{r}$:_ Also in this part, the row
$\operatorname{ind}_{v}(v_{j,d})$ of $A_{r}$ consists of zeros except for
position $\operatorname{ind}_{v}(v_{j+1,q^{j}r+d})$ where we have a $1$.

#### Part 3.

Finally, we have a look at the last block $v_{M-1}$ of $v$.

_Components of $v_{M-1}$:_ Let $\ell^{\prime}\leq d\leq
q^{M-1}-q^{m}+u^{\prime}$ and consider the component
$v_{M-1,d}=x\circ(n\mapsto q^{M-1}n+d)$ of $v_{M-1}$. Write
$d=d^{\prime}q^{M}+r^{\prime}$ with $0\leq r^{\prime}\leq q^{M}-1$ and
$d^{\prime}\in\mathbb{Z}$. The component of $v(qn+r)$ which corresponds to
$v_{M-1,d}$ is given by

$x\bigl{(}q^{M-1}(qn+r)+d\bigr{)}=x\bigl{(}q^{M}(n+d^{\prime})+q^{M-1}r+r^{\prime}\bigr{)}=x\bigl{(}q^{M}(n+d^{\prime})+\tilde{r}\bigr{)}$

with $\tilde{r}\coloneqq q^{M-1}r+r^{\prime}$. Note that $\tilde{r}\leq
q^{M-1}(q-1)+q^{M}-1=2q^{M}-q^{M-1}-1$. We distinguish the following two cases
with respect to the parameter $r$ for determining the rows of $A_{r}$
corresponding to the block $v_{M-1}$.

Case 1:

$0\leq\tilde{r}<q^{M}$. We have

$\begin{split}x\bigl{(}q^{M}(n+d^{\prime})+\tilde{r}\bigr{)}&=\smashoperator[]{\sum_{\ell\leq
k\leq u}^{}}c_{\tilde{r},k}\,x\bigl{(}q^{m}(n+d^{\prime})+k\bigr{)}\\\
&=\smashoperator[]{\sum_{\ell\leq k\leq
u}^{}}c_{\tilde{r},k}\,x\bigl{(}q^{m}n+q^{m}d^{\prime}+k)\end{split}$ (8.6)

for $n+d^{\prime}\geq n_{0}$ due to (3.1). As $d^{\prime}=\lfloor
d/q^{M}\rfloor\geq\lfloor\ell^{\prime}/q^{M}\rfloor$ holds, the condition
$n+d^{\prime}\geq n_{0}$ is fulfilled for $n\geq n_{1}$ by definition of
$n_{1}$. We need to show that $\ell^{\prime}\leq q^{m}d^{\prime}+k\leq
u^{\prime}$ holds for all $\ell\leq k\leq u$. We apply Lemma 8.48 and directly
obtain both inequalities, i.e., $\ell^{\prime}\leq q^{m}d^{\prime}+k$ and
$q^{m}d^{\prime}+k\leq u^{\prime}$, by (8.1). This implies that the sequence
$x\circ(n\mapsto q^{M-1}(qn+r)+d)$ is a linear combination of sequences in
$v$, where all sequences are restricted to $n\geq n_{1}$.

_Corresponding rows of $A_{r}$:_ We have a look at row
$\operatorname{ind}_{v}(v_{M-1,d})$ of $A_{r}$. The first couple of entries
are zero, up to position
$\operatorname{ind}_{v}(v_{m,q^{m}d^{\prime}+\ell})-1$. On position
$\operatorname{ind}_{v}(v_{m,q^{m}d^{\prime}+\ell})$ up to position
$\operatorname{ind}_{v}(v_{m,q^{m}d^{\prime}+u})$ we have the entries
$c_{\tilde{r},\ell}$, …, $c_{\tilde{r},u}$, followed by zeros up to the end of
the row.

Case 2:

$q^{M}\leq\tilde{r}<2q^{M}-q^{M-1}-1$. This implies $r^{\prime}\geq q^{M-1}$
and $0\leq\tilde{r}-q^{M}<q^{M}$. We obtain

$\begin{split}x\bigl{(}q^{M}(n+d^{\prime})+\tilde{r}\bigr{)}&=x\bigl{(}q^{M}(n+d^{\prime}+1)+\tilde{r}-q^{M}\bigr{)}\\\
&=\smashoperator[]{\sum_{\ell\leq k\leq
u}^{}}c_{\tilde{r}-q^{M},k}\,x\bigl{(}q^{m}(n+d^{\prime}+1)+k\bigr{)}\\\
&=\smashoperator[]{\sum_{\ell\leq k\leq
u}^{}}c_{\tilde{r}-q^{M},k}\,x\bigl{(}q^{m}n+q^{m}d^{\prime}+q^{m}+k)\end{split}$
(8.7)

for $n\geq n_{1}-1$, again due to (3.1). Thus, we need to argue that
$\ell^{\prime}\leq q^{m}d^{\prime}+q^{m}+k\leq u^{\prime}$ holds for all
$\ell\leq k\leq u$. For this purpose, we again use Lemma 8.48. The inequality
$q^{m}d^{\prime}+q^{m}+k\leq u^{\prime}$ directly follows from (8.2). For the
lower bound we obtain

$q^{m}d^{\prime}+q^{m}+k\geq
q^{m}d^{\prime}+q^{m}+\ell>q^{m}d^{\prime}+\ell\stackrel{{\scriptstyle\stackrel{{\scriptstyle\text{\eqref{eq:lemma-
bounds-case-1}}}}{{\downarrow}}}}{{\geq}}\ell^{\prime}.$

This shows that also in this case, the sequence $x\circ(n\mapsto
q^{M-1}(qn+r)+d)$ is a linear combination of sequences in $v$, where again all
sequences are restricted to $n\geq n_{1}$.

_Corresponding rows of $A_{r}$:_ We again have a look at row
$\operatorname{ind}_{v}(v_{M-1,d})$ of $A_{r}$. The first couple of entries
are zero, up to position
$\operatorname{ind}_{v}(v_{m,q^{m}d^{\prime}+q^{m}+\ell})-1$. On position
$\operatorname{ind}_{v}(v_{m,q^{m}d^{\prime}+q^{m}+\ell})$ up to position
$\operatorname{ind}_{v}(v_{m,q^{m}d^{\prime}+q^{m}+u})$ we have the entries
$c_{\tilde{r}-q^{M},\ell}$, …, $c_{\tilde{r}-q^{M},u}$, followed by zeros up
to the end of the row.

#### Finalizing the Proof.

At this point, we have completed constructing matrices $A_{r}$ for $0\leq r<q$
row by row and have shown that $(A_{0},\ldots,A_{r-1},v)$ is a linear
representation of $x$. We now gather the information on $A_{r}$ which was
discussed in the proof. We let $D$ denote the dimension of $A_{r}$. If $a_{i}$
is the $i$th row of $A_{r}$, define $j\in\mathbb{N}_{0}$ and $d\in\mathbb{Z}$
by $i=\operatorname{ind}_{v}(v_{j,d})$. Then we have

$a_{i}^{\top}=\begin{cases}\bigl{(}\big{\llbracket}k=\operatorname{ind}_{v}(v_{j+1,q^{j}r+d})\big{\rrbracket}\bigr{)}_{1\leq
k\leq D}&\text{if }0\leq j\leq M-2,\\\
\bigl{(}c_{\tilde{r},k+k_{1}}\cdot\llbracket\ell\leq k+k_{1}\leq
u\rrbracket\bigr{)}_{1\leq k\leq D}&\text{if }j=M-1\text{ and
}\tilde{r}<q^{M},\\\
\bigl{(}c_{\tilde{r}-q^{M},k+k_{2}}\cdot\llbracket\ell\leq k+k_{2}\leq
u\rrbracket\bigr{)}_{1\leq k\leq D}&\text{if }j=M-1\text{ and }\tilde{r}\geq
q^{M},\end{cases}$ (8.8)

where

  * •

$\tilde{r}\coloneqq q^{M-1}r+r^{\prime}$ with $d=d^{\prime}q^{M}+r^{\prime}$,
$d^{\prime}\in\mathbb{Z}$ and $0\leq r^{\prime}<q^{M}$,

  * •

$k_{1}\coloneqq\ell-\operatorname{ind}_{v}(v_{m,q^{m}d^{\prime}+\ell})$ and

  * •

$k_{2}\coloneqq\ell-\operatorname{ind}_{v}(v_{m,q^{m}d^{\prime}+q^{m}+\ell})$.

Note that all these parameters depend on $i$.

######  Proof 8.51 (Proof of Theorem 3.11).

The definitions of $\delta_{k}$ and $w_{r,k}$ in Theorem 3.11 imply that

$v(qn+r)=A_{r}v(n)+\smashoperator[]{\sum_{0\leq
k<n_{0}}^{}}w_{r,k}\,\delta_{k}(n)$

holds for all $0\leq r<q$ and $n\geq 0$. We further have

$\delta_{k}(qn+r)=\llbracket k\geq r\text{ and }k\equiv
r{\@displayfalse\pmod{q}}\rrbracket\cdot\delta_{(k-r)/q}(n)$

for all $0\leq k<n_{0}$, $0\leq r<q$ and $n\geq 0$. With $\widetilde{v}$ and
$\widetilde{A}_{r}$ as defined in (3.7) and (3.8), it follows that
$\widetilde{v}(qn+r)=\widetilde{A}_{r}\widetilde{v}(n)$ holds for all $0\leq
r<q$ and $n\geq 0$. Consequently,
$(\widetilde{A}_{0},\ldots,\widetilde{A}_{q-1},\widetilde{v})$ is a $q$-linear
representation of $x$ and thus, $x$ is $q$-regular. The statement about the
shape of $J_{r}$ follows from the definition of $J_{r}$. This completes the
proof of the theorem.

Corollary 3.12 directly follows by combining Theorem 3.7 and Theorem 3.11.

######  Proof 8.52 (Proof of Corollary 3.13).

First of all, note that for a $q$-regular sequence $g$, its shifted version
$g\circ(n\mapsto n+d)$ is $q$-regular for all integers $d\in\mathbb{Z}$; see
Allouche and Shallit [1, Theorem 2.6 and the subsequent remark].

We use the notation introduced in Theorem 3.7. In order to prove the
corollary, we construct a $q$-linear representation with offset $n_{1}$ of $x$
along the lines of the proof of Theorem 3.7: Parts 1 and 2 of the proof can be
adopted unchanged, but we have to carefully adapt Part 3: In (8.6) and (8.7),
we have to apply (3.10) instead of (3.1) and obtain

$x\bigl{(}q^{M}(n+d^{\prime})+\tilde{r}\bigr{)}=\smashoperator[]{\sum_{\ell\leq
k\leq
u}^{}}c_{\tilde{r},k}\,x\bigl{(}q^{m}n+q^{m}d^{\prime}+k)+g_{\tilde{r}}(n+d^{\prime})$
(8.9)

in the first case and

$x\bigl{(}q^{M}(n+d^{\prime}+1)+\tilde{r}-q^{M}\bigr{)}=\smashoperator[]{\sum_{\ell\leq
k\leq
u}^{}}c_{\tilde{r}-q^{M},k}\,x\bigl{(}q^{m}n+q^{m}d^{\prime}+q^{m}+k)+g_{\tilde{r}-q^{M}}(n+d^{\prime}+1)$
(8.10)

in the second case, where $n\geq n_{1}$ and
$\lfloor\ell^{\prime}/q^{M}\rfloor\leq
d^{\prime}\leq\lfloor(q^{M-1}-q^{m}+u^{\prime})/q^{M}\rfloor$. Thus, if we
append the vectors of the $q$-linear representations of the $q$-regular
sequences $g_{s}\circ(n\mapsto n+d^{\prime\prime})$ for $0\leq s<q^{M}$ and
$\lfloor\ell^{\prime}/q^{M}\rfloor\leq
d^{\prime\prime}\leq\lfloor(q^{M-1}-q^{m}+u^{\prime})/q^{M}\rfloor+1$ to the
vector $v$ as given by (3.3) and analogously join the corresponding matrices
together—with some additional entries $1$ caused by
$g_{\tilde{r}}(n+d^{\prime})$ and $g_{\tilde{r}-q^{M}}(n+d^{\prime}+1)$ in
(8.9) and (8.10), respectively—then we obtain a $q$-linear representation with
offset $n_{1}$ of $x$.

Finally, we correct the offset of the $q$-linear representation by applying
Theorem 3.11. Consequently, $x$ is $q$-regular.

###  8.2 Proof of the Reduction to $q$-Regular Sequences in the Special Case

######  Proof 8.53 (Proof of Theorem 3.15).

We split the proof into two parts depending on the indices of the blocks of
$v$.

#### Part 1.

At first, we consider blocks $v_{j}$ with $0\leq j<m$. These blocks coincide
with (3.4a) in Theorem 3.7. Moreover, these blocks correspond to the first
$\sum_{0\leq j<m}q^{j}=(q^{m}-1)/(q-1)$ rows of the matrices $A_{0}$, …,
$A_{q-1}$ and thus, also to the rows of $J_{r0}$ and $J_{r1}$ for $0\leq r<q$.
By the proof of Theorem 3.7, each of these rows consists of zeros and exactly
one $1$, which in particular means that the only entries of $J_{r0}$ and
$J_{r1}$ are zeros and ones as stated in the theorem. It remains to show that
the matrices $J_{r0}$ are upper triangular with zeros on the diagonal. This
follows from the fact that

$\operatorname{ind}_{v}\bigl{(}x\circ(n\mapsto
q^{j}(qn+r)+d)\bigr{)}>\operatorname{ind}_{v}\bigl{(}x\circ(n\mapsto
q^{j}n+d)\bigr{)}$

holds for all $0\leq j<m$, $0\leq r<q$ and $0\leq d<q^{j}$.

#### Part 2.

We take a look at the block $v_{m}$. The definition of $B_{r}$ in (3.11)
implies that

$v_{m}(qn+r)=B_{r}v_{m}(n)$

holds for all $0\leq r<q$, which, together with Part 1, directly implies that
$(A_{0},\dots,A_{q-1},v)$ as given in (3.12) and (3.14) is indeed a linear
representation of $x$.

###  8.3 Proofs of the Spectral Results

We start with the proof of Proposition 4.22.

######  Proof 8.54 (Proof of Proposition 4.22).

Due to (3.8), we have

$\widetilde{C}=\begin{pmatrix}C&W\\\ 0&J\end{pmatrix}$

with the $n_{0}\times n_{0}$ matrix $J=\sum_{0\leq r<q}J_{r}$ and
$W=\sum_{0\leq r<q}W_{r}$, and thus,
$\sigma(\widetilde{C})=\sigma(C)\cup\sigma(J)$. By the properties of $J_{r}$
noted in Theorem 3.11, $J$ is a lower triangular matrix with
$\operatorname{diag}(J)=(1,0,\dots,0)$. This yields
$\sigma(J)\subseteq\\{0,1\\}$. Furthermore, we can say the following. If
$n_{0}=1$, then $J=(1)$ and thus, $\sigma(J)=\\{1\\}$. If $n_{0}\geq 2$, then
$\operatorname{diag}(J)=(1,0,\dots,0)$ holds with $n_{0}-1\geq 1$ zeros which
implies $\sigma(J)=\\{0,1\\}$. This yields the result as stated.

Before proving Lemma 4.23, we need another lemma.

######  Lemma 8.55.

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

$G=\begin{pmatrix}G^{(11)}&G^{(12)}\\\ 0&G^{(22)}\end{pmatrix}$

where the block $G^{(ij)}$ is a $D_{i}\times D_{j}$ matrix for $1\leq i\leq
j\leq 2$.

Let $R_{1}$ and $R_{2}$ be non-negative constants such that

$\lVert G^{(ii)}_{1}\ldots G^{(ii)}_{k}\rVert=O(R_{i}^{k})$

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

Assume that $R_{1}\neq R_{2}$ and set $R\coloneqq\max\\{R_{1},R_{2}\\}$. Then

$\lVert G_{1}\ldots G_{k}\rVert=O(R^{k})$

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

######  Proof 8.56.

As both the assumption and the statement of the lemma do not depend on the
particular norm by the norm equivalence theorem, it suffices to consider the
maximum norm on vectors and thus the row sum norm on matrices.

It is easily shown by induction on $k$ that

$G_{1}\ldots G_{k}=\begin{pmatrix}G^{(11)}_{1}\ldots
G^{(11)}_{k}&\sum_{j=1}^{k}\bigl{(}G^{(11)}_{1}\ldots
G^{(11)}_{j-1}\bigr{)}G^{(12)}_{j}\bigl{(}G^{(22)}_{j+1}\ldots
G^{(22)}_{k}\bigr{)}\\\ 0&G^{(22)}_{1}\ldots G^{(22)}_{k}\end{pmatrix}.$

If one of $R_{1}$, $R_{2}$ equals zero, all except at most one of the upper
right summands vanish and the result follows easily.

Otherwise, assume without loss of generality that $R_{1}<R_{2}$. Then

$\displaystyle\bigg{\lVert}\sum_{j=1}^{k}\bigl{(}G^{(11)}_{1}\ldots
G^{(11)}_{j-1}\bigr{)}G^{(12)}_{j}\bigl{(}G^{(22)}_{j+1}\ldots
G^{(22)}_{k}\bigr{)}\bigg{\rVert}$
$\displaystyle=O\biggl{(}\sum_{j=1}^{k}R_{1}^{j-1}R_{2}^{k-j}\biggr{)}$
$\displaystyle=O\biggl{(}R_{2}^{k}\sum_{j=1}^{k}\Bigl{(}\frac{R_{1}}{R_{2}}\Bigr{)}^{j}\biggr{)}=O(R_{2}^{k})$

as $k\to\infty$, because the last sum can be estimated from above by a bounded
geometric series.

Adding the contributions of the rows leads to the result.

We are now able to prove Lemma 4.23.

######  Proof 8.57 (Proof of Lemma 4.23).

As the joint spectral radius as well as the simple growth property do not
depend on the choice of the norm, we only consider the row sum norm in this
proof.

By definition of the joint spectral radius, for every choice of constants
$R_{i}>\rho(\mathcal{G}^{(i)})$,

$\lVert G^{(ii)}_{1}\ldots G^{(ii)}_{k}\rVert=O(R_{i}^{k})$

holds for $G_{1}$, …, $G_{k}\in\mathcal{G}$, $1\leq i\leq s$ and $k\to\infty$
(where the implicit constant depends on the $R_{i}$). If $\mathcal{G}^{(i)}$
has the simple growth property, we may also choose
$R_{i}=\rho(\mathcal{G}^{(i)})$. Without loss of generality, we can choose the
$R_{i}$ to be pairwise distinct. Then repeated application of Lemma 8.55 shows
that

$\lVert G_{1}\ldots G_{k}\rVert=O((\max_{1\leq i\leq s}R_{i})^{k})$ (8.11)

holds for all $G_{1}$, …, $G_{k}\in\mathcal{G}$ and $k\to\infty$.
Consequently, we obtain $\rho(\mathcal{G})\leq\max_{1\leq i\leq s}R_{i}$.
Taking the infimum over all possible choices of $R_{i}$ shows that
$\rho(\mathcal{G})\leq\max_{1\leq i\leq s}\rho(\mathcal{G}^{(i)})$. As the
diagonal blocks of the product of block triangular matrices are the products
of the corresponding diagonal blocks, it follows that
$\rho(\mathcal{G})\geq\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, we can choose
$R_{i_{0}}=\rho(\mathcal{G}^{(i_{0})})$ and
$R_{i}<\rho(\mathcal{G}^{(i_{0})})$ for $i\neq i_{0}$ and the simple growth
property of $\mathcal{G}$ follows from (8.11).

######  Proof 8.58 (Proof of Proposition 4.24).

As the matrices $J_{r}$ are lower triangular matrices with diagonal elements
$0$ and $1$, Lemma 4.23 (or Jungers [25, Proposition 1.5]) implies that
$\rho(\mathcal{J})\leq 1$. As $J_{0}$ has a one on the diagonal, we actually
have $\rho(\mathcal{J})=1$.

Since all matrices $\widetilde{A}_{0}$, …, $\widetilde{A}_{q-1}$ are upper
triangular block matrices, we can apply Lemma 4.23 (or Jungers [25,
Proposition 1.5]) once more to obtain the first part of (4.5). The “in
particular”-statement follows directly from (4.5).

Finally, Lemma 4.23 shows that $\widetilde{\mathcal{A}}$ has the simple growth
property under the assumptions stated in the last part of Proposition 4.24.

######  Proof 8.59 (Proof of Proposition 4.25).

Observe that we have

$C=\begin{pmatrix}J_{00}+\cdots+J_{(q-1)0}&J_{01}+\cdots+J_{(q-1)1}\\\
0&B_{0}+\cdots+B_{q-1}\end{pmatrix}.$

So $C$ is an upper triangular block matrix, which implies

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

By Theorem 3.15, $J_{00}+\cdots+J_{(q-1)0}$ is a triangular matrix with zero
diagonal, so its only eigenvalue is $0$, which yields the result.

######  Proof 8.60 (Proof of Proposition 4.26).

The statement $\rho(\mathcal{J})=0$ follows by Lemma 4.23 and the fact that
every matrix in $\mathcal{J}$ is an upper triangular matrix with zeros on the
diagonal. The rest of the proposition can be proven in analogy to Proposition
4.24.

###  8.4 Proof of the Functional Equation in the Special Case

######  Proof 8.61 (Proof of Proposition 4.27).

For $0\leq j<q^{m}$ and $\real s>\log_{q}\rho+1$, replacing $n$ by $qn+\mu$
yields

$\displaystyle\mathcal{X}_{j}(s)$
$\displaystyle=\sum_{n\geq\eta}\frac{x(q^{m}n+j)}{(q^{m}n+j)^{s}}$
$\displaystyle=\sum_{\mu=0}^{q-1}\;\sum_{n\geq\eta}\frac{x(q^{m+1}n+\mu
q^{m}+j)}{(q^{m+1}n+\mu q^{m}+j)^{s}}+\overbrace{\sum_{\eta\leq
n<q\eta}\frac{x(q^{m}n+j)}{(q^{m}n+j)^{s}}}^{\eqqcolon\sigma}.$ We now use
(3.1) and obtain $\displaystyle\mathcal{X}_{j}(s)$
$\displaystyle=\sum_{\mu=0}^{q-1}\;\sum_{n\geq\eta}\frac{\sum_{k=0}^{q^{m}-1}c_{\mu
q^{m}+j,k}\,x(q^{m}n+k)}{(q^{m+1}n+\mu q^{m}+j)^{s}}+\sigma$
$\displaystyle=q^{-s}\sum_{\mu=0}^{q-1}\;\sum_{k=0}^{q^{m}-1}c_{\mu
q^{m}+j,k}\sum_{n\geq\eta}\frac{x(q^{m}n+k)}{\bigl{(}q^{m}n+\frac{\mu
q^{m}+j}{q}\bigr{)}^{s}}+\sigma$
$\displaystyle=q^{-s}\sum_{k=0}^{q^{m}-1}\Bigl{(}\sum_{\mu=0}^{q-1}c_{\mu
q^{m}+j,k}\Bigr{)}\mathcal{X}_{k}(s)+\mathcal{Y}_{j}(s),$

where $\mathcal{Y}_{j}(s)$ is given by

$\mathcal{Y}_{j}(s)=q^{-s}\sum_{k=0}^{q^{m}-1}\;\sum_{\mu=0}^{q-1}c_{\mu
q^{m}+j,k}\biggl{(}\sum_{n\geq\eta}\frac{x(q^{m}n+k)}{\bigl{(}q^{m}n+\frac{\mu
q^{m}+j}{q}\bigr{)}^{s}}-\mathcal{X}_{k}(s)\biggr{)}+\sigma.$ (8.12)

Note that $\sum_{k=0}^{q^{m}-1}\sum_{\mu=0}^{q-1}c_{\mu
q^{m}+j,k}\mathcal{X}_{k}(s)$ is the $j$th row of
$(B_{0}+\cdots+B_{q-1})\mathcal{X}(s)$. It is easy to see that

$\Big{\lvert}\frac{\mu q^{m}+j}{q}-k\Big{\rvert}<q^{m}\leq q^{m}\eta+k$

holds for all $0\leq\mu<q$, $0\leq j<q^{m}$ and $0\leq k<q^{m}$. Consequently,
we apply [20, Lemma 6.3] with $n_{0}=q^{m}\eta+k$ (see (4.6)) as well as
$\beta=\frac{\mu q^{m}+j}{q}-k$ and obtain

$\sum_{n\geq\eta}\frac{x(q^{m}n+k)}{\bigl{(}q^{m}n+\frac{\mu
q^{m}+j}{q}\bigr{)}^{s}}-\mathcal{X}_{k}(s)=\sum_{n\geq
1}\binom{-s}{n}\Bigl{(}\frac{\mu
q^{m}+j}{q}-k\Bigr{)}^{n}\mathcal{X}_{k}(s+n),$ (8.13)

again for all $0\leq\mu<q$, $0\leq j<q^{m}$ and $0\leq k<q^{m}$. Furthermore,
the right-hand side of (8.13) is analytic for $\real s>\log_{q}\rho$. Plugging
(8.13) into (8.12) and reordering terms yields the result. The functional
equation (4.7) implies that $\mathcal{X}_{j}(s)$ is meromorphic for $\real
s>\log_{q}\rho$ and can only have poles where
$q^{s}\in\sigma(B_{0}+\cdots+B_{q-1})$.

## References

  * [1] Jean-Paul Allouche and Jeffrey Shallit, _The ring of $k$-regular sequences_, Theoret. Comput. Sci. 98 (1992), no. 2, 163–197.
  * [2] , _Automatic sequences: Theory, applications, generalizations_, Cambridge University Press, Cambridge, 2003.
  * [3] , _The ring of $k$-regular sequences, II_, Theoret. Comput. Sci. 307 (2003), no. 1, 3–29.
  * [4] Jason P. Bell, _On the values attained by a $k$-regular sequence_, Adv. in Appl. Math. 34 (2005), no. 3, 634–643.
  * [5] Jean Berstel and Christophe Reutenauer, _Noncommutative rational series with applications_ , Encyclopedia of Mathematics and its Applications, vol. 137, Cambridge University Press, Cambridge, 2011.
  * [6] Marjorie Bicknell-Johnson, _Stern’s diatomic array applied to Fibonacci representations_ , Fibonacci Quart. 41 (2003), no. 2, 169–180.
  * [7] Achille Brocot, _Calcul des rouages par approximation, nouvelle méthode_, L’auteur, 1862, Source: Bibliothèque nationale de France.
  * [8] Leonard Carlitz, _A problem in partitions related to the Stirling numbers_ , Riv. Mat. Univ. Parma (2) 5 (1964), 61–75.
  * [9] Émilie Charlier, Narad Rampersad, and Jeffrey Shallit, _Enumeration and decidable properties of automatic sequences_, Internat. J. Found. Comput. Sci. 23 (2012), no. 5, 1035–1066.
  * [10] Michael Coons and Jeffrey Shallit, _A pattern sequence approach to Stern’s sequence_, Discrete Math. 311 (2011), no. 22, 2630–2633.
  * [11] Michael Coons and Lukas Spiegelhofer, _Number theoretic aspects of regular sequences_, Sequences, groups, and number theory, Trends Math., Birkhäuser/Springer, Cham, 2018, pp. 37–87.
  * [12] James D. Currie and Kalle Saari, _Least periods of factors of infinite words_, Theor. Inform. Appl. 43 (2009), no. 1, 165–178.
  * [13] Philippe Dumas, _Joint spectral radius, dilation equations, and asymptotic behavior of radix-rational sequences_, Linear Algebra Appl. 438 (2013), no. 5, 2107–2126.
  * [14] Steven R. Finch, _Mathematical constants_, Encyclopedia of Mathematics and its Applications, vol. 94, Cambridge University Press, Cambridge, 2003.
  * [15] Nathan J. Fine, _Binomial coefficients modulo a prime_, Amer. Math. Monthly 54 (1947), 589–592.
  * [16] Daniel Goč, Dane Henshall, and Jeffrey Shallit, _Automatic theorem-proving in combinatorics on words_, Internat. J. Found. Comput. Sci. 24 (2013), no. 6, 781–798.
  * [17] Daniel Goč, Hamoon Mousavi, and Jeffrey Shallit, _On the number of unbordered factors_, Language and automata theory and applications, Lecture Notes in Comput. Sci., vol. 7810, Springer, Heidelberg, 2013, pp. 299–310.
  * [18] Daniel Goč, Narad Rampersad, Michel Rigo, and Pavel Salimov, _On the number of abelian bordered words (with an example of automatic theorem-proving)_, Internat. J. Found. Comput. Sci. 25 (2014), no. 8, 1097–1110.
  * [19] Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, _Concrete mathematics. A foundation for computer science_ , second ed., Addison-Wesley, 1994.
  * [20] Clemens Heuberger and Daniel Krenn, _Asymptotic analysis of regular sequences_, Algorithmica 82 (2020), no. 3, 429–508.
  * [21] Clemens Heuberger, Daniel Krenn, and Gabriel F. Lipnik, _A note on the relation between recognisable series and regular sequences, and their minimal linear representations_, arXiv:2201.13446 [math.CO], 2022.
  * [22] Clemens Heuberger, Daniel Krenn, and Helmut Prodinger, _Analysis of summatory functions of regular sequences: Transducer and Pascal’s rhombus_, Proceedings of the 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (James Allen Fill and Mark Daniel Ward, eds.), Leibniz International Proceedings in Informatics (LIPIcs), vol. 110, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2018, pp. 27:1–27:18.
  * [23] Andreas M. Hinz, Sandi Klavžar, Uroš Milutinović, Daniele Parisse, and Ciril Petr, _Metric properties of the Tower of Hanoi graphs and Stern’s diatomic sequence_, European J. Combin. 26 (2005), no. 5, 693–708.
  * [24] Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, _Exact and asymptotic solutions of a divide-and-conquer recurrence dividing at half: Theory and applications_, ACM Trans. Algorithms 13 (2017), no. 4, Art. 47, 43 pp.
  * [25] Raphaël Jungers, _The joint spectral radius. Theory and applications_, Lecture Notes in Control and Information Sciences, vol. 385, Springer-Verlag, Berlin, 2009.
  * [26] Daniel Krenn and Gabriel F. Lipnik, _$k$ -Regular sequences in SageMath: Construction of $q$-recursive sequences_, https://trac.sagemath.org/ticket/27940, https://trac.sagemath.org/ticket/31787, https://trac.sagemath.org/ticket/32198, https://trac.sagemath.org/ticket/32921, https://trac.sagemath.org/ticket/33158, 2022.
  * [27] Julien Leroy, Michel Rigo, and Manon Stipulanti, _Generalized Pascal triangle for binomial coefficients of words_, Adv. in Appl. Math. 80 (2016), 24–47.
  * [28] , _Behavior of digital sequences through exotic numeration systems_, Electron. J. Combin. 24 (2017), no. 1, Paper No. 1.44, 36.
  * [29] , _Counting the number of non-zero coefficients in rows of generalized Pascal triangles_, Discrete Math. 340 (2017), no. 5, 862–881.
  * [30] , _Counting subword occurrences in base- $b$ expansions_, Integers 18A (2018), Paper No. A13, 32 pp.
  * [31] M. Lothaire, _Combinatorics on words_, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1997.
  * [32] , _Algebraic combinatorics on words_ , Encyclopedia of Mathematics and its Applications, vol. 90, Cambridge University Press, Cambridge, 2002.
  * [33] Sam Northshield, _Stern’s diatomic sequence $0,1,1,2,1,3,2,3,1,4,\dots$_, Amer. Math. Monthly 117 (2010), no. 7, 581–598.
  * [34] _The On-Line Encyclopedia of Integer Sequences_ , http://oeis.org, 2021.
  * [35] Gian-Carlo Rota and Gilbert Strang, _A note on the joint spectral radius_ , Indag. Math. 22 (1960), 379–381.
  * [36] The SageMath Developers, _SageMath Mathematics Software (Version 9.4)_ , 2021, http://www.sagemath.org.
  * [37] Moritz A. Stern, _Ueber eine zahlentheoretische Funktion_, J. Reine Angew. Math. 55 (1858), 193–220.