# Linear dynamical systems with continuous weight functions

Rajab Aghamov  TU DresdenDresdenGermany ,  Christel Baier  TU
DresdenDresdenGermany ,  Toghrul Karimov  Max Planck Institute for Software
SystemsSaarbrückenGermany ,  Joël Ouaknine  Max Planck Institute for Software
SystemsSaarbrückenGermany and  Jakob Piribauer  TU DresdenDresdenGermany

###### Abstract.

In discrete-time linear dynamical systems (LDSs), a linear map is repeatedly
applied to an initial vector yielding a sequence of vectors called the orbit
of the system. A weight function assigning weights to the points in the orbit
can be used to model quantitative aspects, such as resource consumption, of a
system modelled by an LDS. This paper addresses the problems to compute the
mean payoff, the total accumulated weight, and the discounted accumulated
weight of the orbit under continuous weight functions and polynomial weight
functions as a special case. Besides general LDSs, the special cases of
stochastic LDSs and of LDSs with bounded orbits are considered. Furthermore,
the problem of deciding whether an energy constraint is satisfied by the
weighted orbit, i.e., whether the accumulated weight never drops below a given
bound, is analysed.

linear dynamical systems, mean payoff, total reward, discounted reward

††ccs: Theory of computation Timed and hybrid models

##  1\. Introduction

Table 1. Overview of the results. | LDS type | weight function | algorithmic results |
---|---|---|---|---
mean payoff | arbitrary | polynomial | computable | (Thm. 3.4)
| bounded orbit | continuous | integral representation computable | (Thm. 3.8)
| stochastic, irreducible | continuous | computable with polynomially many evaluations of the weight function. | (Thm. 3.10)
| stochastic, reducible | continuous | computable with exponentially many evaluations of the weight function. | (Thm. 3.12)
total/discounted weight | arbitrary | polynomial | computable | (Thm. 4.1)
satisfaction of energy constraints | arbitrary | polynomial | decidable in dimension 3 | (Thm. 4.7)
stochastic | linear | Positivity-hard | (Thm. 4.8)
| dimension 4 | polynomial | Diophantine-hard | (Thm. 4.9)

Dynamical systems describing how the state of a system changes over time
constitute a prominent modelling paradigm in a wide variety of fields. A
_discrete-time linear dynamical system_ (LDS) in ambient space
$\mathbb{R}^{d}$ starts at some initial point $q\in\mathbb{R}^{d}$. The
dynamics of the system are given by a linear update function in form of a
matrix $M\in\mathbb{R}^{d\times d}$ that is applied to the current state of
the system at each time step. This gives rise to the _orbit_
$(q,Mq,M^{2}q,\dots)$.

The investigation of LDSs is particularly important as they are arguably the
simplest form of dynamical systems, but nevertheless exhibit many challenging
problems. Further, the linearisation of more complex systems is ubiquitous in
control theory and engineering (see, e.g., (lee1987linearization, ;
aranda1996linearization, )) and so many real world problems are solved via the
use of linearisations.

Algorithmic problems concerning LDSs form a lively area of research in
computer science. Surprisingly, several seemingly simple decidability
questions about the orbit of a given LDS have been open for many decades (for
an overview, see (KarimovKO022, )). For example, two prominent problems about
_linear recurrence sequences_ , the Positivity Problem and the Skolem Problem,
are subsumed by the following problem: given $(M,q)$ and a target set $H$,
decide whether there exists $n\in\mathbb{N}$ such that $M^{n}q\in H$. Deep
results establish the decidability of special cases of the Skolem
(tijdeman_distan_between_terms_algeb_recur_sequen, ; Verescchagin, ) and
Positivity (ouaknine13_posit_probl_low_order_linear_recur_sequen, ;
ouaknine_simple-positivity, ) problems in low dimensions. In general, the
decidability status of these two problems has, however, been open for many
decades. Furthermore, in order to verify that a system modelled as an LDS
satisfies desirable properties, typical formal verification problems such as
model-checking problems asking whether the orbit of an LDSs satisfies certain
temporal properties have been studied (AKK21, ; KLO22, ).

In this paper, we address quantitative verification questions arising when
systems are equipped with a weight function. To the best of our knowledge,
such quantitative verification tasks on weighted LDSs have not been
investigated in the literature. The work (kelmendi2022, ) on computing the
_density_ of the visits of an orbit to a semialgebraic set, however, has
direct consequences for weighted LDSs with _non-continuous_ weight functions
that we explain in more detail in the section on related work below.

We consider _continuous_ weight functions $w\colon\mathbb{R}^{d}\to\mathbb{R}$
assigning a weight to each state in the ambient space. Such weight functions
can be used to model various quantitative aspects of a system, such as
resource or energy consumption, rewards or utilities, or execution time for
example. Given a weight function $w$, we obtain a sequence of weights of the
states in the orbit $(w(q),w(Mq),w(M^{2}q),\dots)$. The goal of this paper is
to provide algorithmic answers to the following typical questions arising for
weighted systems:

  * a)

What is the _mean payoff_ , i.e., the average weight collected per step?

  * b)

What is the _total accumulated weight_ of the orbit and what is the so-called
_discounted accumulated weight_ , where weights obtained after $k$ time steps
are discounted with a factor $\lambda^{k}$ for a given $\lambda\in(0,1)$?

  * c)

Is there an $n\in\mathbb{N}$ such that the sum of weights obtained in the
first $n$ steps lies below a given bound? This problem is referred to as
_satisfaction of an energy constraint_ because it corresponds to determining
whether a system ever runs out of energy when weights model the energy used or
gained per step.

###### Example 1.1.

Assume a scheduler assigns tasks to $d$ different processors
$P_{1},\dots,P_{d}$ and that the load of the processors at different time
steps can be modeled as an LDS with matrix $M\in\mathbb{Q}^{d\times d}$ and
orbit $(M^{k}q)_{k\in\mathbb{N}}$ for a $q\in\mathbb{Q}^{d}$. Further, assume
for each processor $P_{i}$ there is an optimal load $\mu_{i}$ under which it
works most efficiently. To evaluate the scheduler, we want to know how closely
the real loads in the long-run match the ideal loads. As a measure for how
well a vector $x$ matches the vector $\mu$ of ideal loads, we use the average
squared distance

$\delta_{\mu}(x)=\frac{1}{d}\sum_{i=1}^{d}(x_{i}-\mu_{i})^{2}.$

To see how well the scheduler manages to get close to optimal loads in the
long-run after a possible intialization phase, we consider the mean payoff of
the orbit with respect to the weight function $\delta_{\mu}$, i.e.,

$\lim_{\ell\to\infty}\frac{1}{\ell+1}\sum_{k=0}^{\ell}\delta_{\mu}(M^{k}q).$

If, on the other hand, we know that the orbit will tend to the optimal loads
for $k\to\infty$, we might instead also want to measure the total deviation
$\sum_{k=0}^{\infty}\delta_{\mu}(M^{k}q)$. If this value is small, the orbit
converges to the optimal loads rather quickly without large deviations
initially.

In order to obtain algorithmic results, we consider different combinations of
restricted classes of LDSs and restricted classes of continuous weight
functions. Namely, besides arbitrary rational LDSs, we consider also LDSs with
bounded orbit and _stochastic LDSs_. Stochastic LDSs occur in the context of
the verification of probabilistic systems: For a finite-state Markov chain,
the sequence of distributions over the state space naturally forms an LDS. The
initial distribution can be written as a vector
$\iota_{\mathit{init}}\in[0,1]^{d}$. Afterwards, the transition probability
matrix $P$ can be repeatedly applied to obtain the distribution
$P^{k}\iota_{\mathit{init}}$ over states after $k$ steps. In contrast to the
path semantics where a probability measure over infinite paths in a Markov
chain is defined, the view of a Markov chain as an LDS is also called the
_distribution transformer semantics_ of Markov chains (see, e.g., (AgrawalApp,
)).

For the weight functions, we consider general continuous functions. Of course,
for algorithmic results, we have to make additional assumptions on the
computability or approximability of these functions. Furthermore, we consider
the subclass of polynomial weight functions with rational coefficients.

#### Contribution.

We address the problems mentioned above for weighted LDSs with rational
entries under _continuous_ weight functions. Our contributions are as follows
(see also Table 1).

  * a)

Mean payoff: For rational LDSs equipped with a polynomial weight function, we
show that it is decidable whether the mean payoff exists, in which case it is
rational and computable. We then show how to decide whether the orbit of a
rational LDS is bounded. If the orbit of a rational LDS is bounded, we show
how to compute the set of accumulation points of the orbit and prove that the
mean payoff of the orbit can be expressed as an integral of the weight
function over a computable parametrisation of this set. As the parametrisation
can be computed explicitly, the integral can be approximated to arbitrary
precision for any weight function $w$ that is sufficiently well-behaved.

Next, we consider stochastic LDSs, which constitute a special case of LDSs
with bounded orbits. Here, the orbit only has finitely many accumulation
points. We show that in case the transition matrix is irreducible, one can
compute polynomially many rational points in polynomial time such that the
mean payoff is the arithmetic mean of the weight function evaluated at these
points. In the reducible case, on the other hand, exponentially many such
rational points have to be computed.

  * b)

Total and discounted accumulated weights: For rational LDSs and polynomial
weight functions, we prove that the total as well as the discounted
accumulated weight of the orbit is computable and rational if finite.

  * c)

Satisfaction of energy constraints: First we prove that it is decidable
whether an energy constraint is satisfied by an orbit under a polynomial
weight function for LDSs of dimension $d=3$. We furthermore provide two
different hardness results regarding possible extensions of this decidability
result: At $d=4$, the problem is hard with respect to certain open decision
problems in Diophantine approximation that are at the moment wide open.
Further, also restricting to stochastic LDSs and linear weight functions, does
not lead to decidability in general: we show that the energy satisfaction
problem is at least as hard as the Positivity Problem for linear recurrence
sequences in this case. The decidability status of the Positivity Problem is
open, and it is known from
(ouaknine13_posit_probl_low_order_linear_recur_sequen, ) that its resolution
would amount to major mathematical breakthroughs.

#### Related work.

Verification problems for linear dynamical systems have been extensively
studied for decades, starting with the question about the decidability of the
Skolem (tijdeman_distan_between_terms_algeb_recur_sequen, ; Verescchagin, )
and Positivity (ouaknine13_posit_probl_low_order_linear_recur_sequen, ;
ouaknine_simple-positivity, ) problems at low orders, which are special cases
of the reachability problem for LDSs. Decidable cases of the more general
Model-Checking Problem for LDSs have been studied in (AKK21, ; KLO22, ). In
addition, decidability results for parametric LDSs (Baier0JKLLOPW021, ) as
well as various notions of robust verification (BGV22, ; DCostaKMOSW22, ) have
been obtained. See (KarimovKO022, ) for a survey of what is decidable about
discrete-time linear dynamical systems.

There is very little related work on LDSs with weight functions. Closest to
our work is the work by Kelmendi (kelmendi2022, ). There, it is shown that the
_natural density_ (which is a notion of frequency) of visits of a rational LDS
in a semialgebraic set always exists and is approximable to arbitrary
precision. A consequence of this result is that the mean payoff of a rational
LDS with respect to a “semialgebraic step function”, which takes a partition
of the ambient space $\mathbb{R}^{d}$ into finitely many semialgebraic sets
$S_{1},\dots,S_{k}$ and assigns a rational weight $w_{i}$ to the points in
$S_{i}$, can be approximated to arbitrary precision. As these step functions
are not continuous, this result is orthogonal to our results.

When it comes to Markov chains viewed as LDSs under the distribution
transformer semantics, it is known that Skolem and Positivity-hardness results
for general LDSs persist (AkshayAOW15, ). Vahanwala has recently shown (mihir,
) that this is the case even for ergodic Markov chains. In (AgrawalApp, ),
Markov chains under the distribution transformer semantics are treated
approximatively–in contrast to our work–by discretising the probability value
space $[0,1]$ into a finite set of intervals and the problem to decide whether
an approximation of the trajectory obtained in this way satisfies a property
is studied.

##  2\. Preliminaries

We briefly present our notation and introduce the concepts used in the
subsequent sections.

###  2.1. Linear dynamical systems

A (discrete-time) _linear dynamical system_ (LDS) $(M,q)$ of dimension $d>0$
consists of an update matrix $M\in\mathbb{R}^{d\times d}$ and an initial
vector $q\in\mathbb{R}^{d}$. If the entries of $M$ and $q$ are rational, we
say that the LDS is _rational_. The _orbit_ $\mathcal{O}(M,q)$ of $(M,q)$ is
the sequence $(M^{k}q)_{k\in\mathbb{N}}$. We say that the orbit of $(M,q)$ is
bounded if there exists $c\in\mathbb{R}$ such that the Euclidean length
$||M^{k}q||<c$ for all $k\in\mathbb{N}$. An LDS is called _stochastic_ if the
matrix $M$ and the initial vector $q$ have only non-negative entries and the
entries of each column of $M$ as well as the entries of $q$ sum up to $1$. In
this case we refer to the matrix $M$ as stochastic too.111 In order to keep
the notation in line with the notation for general LDSs, we deviate from the
standard convention that rows of stochastic matrices sum up to $1$ and that
stochastic matrices are applied to distributions by multiplication from the
right.

###  2.2. Algebraic numbers

A number $\alpha\in\mathbb{C}$ is _algebraic_ if there exists a polynomial
$p\in\mathbb{Q}[x]$ such that $p(\alpha)=0$. Algebraic numbers form a subfield
of $\mathbb{C}$ denoted by $\overline{\mathbb{Q}}$. The minimal polynomial of
$\alpha\in\overline{\mathbb{Q}}$ is the (unique) monic polynomial
$p\in\mathbb{Q}[X]$ of the smallest degree such that $p(\alpha)=0$. The
_degree_ of $\alpha$, denoted by $\deg(\alpha)$, is the degree of the minimal
polynomial of $\alpha$. For each $\alpha\in\overline{\mathbb{Q}}$ there exists
a unique polynomial $P_{\alpha}=\sum_{i=0}^{d}a_{i}x^{i}\in\mathbb{Z}[x]$ with
$d=\deg(\alpha)$, called the _defining polynomial_ of $\alpha$, such that
$P_{\alpha}(\alpha)=0$ and $\gcd(a_{0},\ldots,a_{d})=1$. The polynomial
$P_{\alpha}$ and the minimal polynomial of $\alpha$ have identical roots, and
are _square-free_ , i.e., all of their roots appear with multiplicity one. The
_(naive) height_ of $\alpha$, denoted by $H(\alpha)$, is equal to $\max_{0\leq
i\leq d}|a_{i}|$. We represent an algebraic number $\alpha$ in computer memory
by its defining polynomial $P_{\alpha}$ and sufficiently precise rational
approximations of $\operatorname{Re}(\alpha),\operatorname{Im}(\alpha)$ to
distinguish $\alpha$ from other roots of $P_{\alpha}$. We denote by
$||\alpha||$ the bit length of a representation of
$\alpha\in\overline{\mathbb{Q}}$. We can perform arithmetic effectively on
algebraic numbers represented in this way.

###  2.3. Linear recurrence sequences

A sequence $(u_{n})_{n\in\mathbb{N}}$ is a _linear recurrence sequence_ over a
ring $R\subseteq\mathbb{C}$ if there exists a positive integer $d$ and a
_recurrence relation_ $(a_{0},\ldots,a_{d-1})\in R^{d}$ such that
$u_{n+d}=\sum_{i=0}^{d-1}a_{i}u_{n+i}$ for all $n$. The _order_ of
$(u_{n})_{n\in\mathbb{N}}$ is the smallest positive integer $d$ such that
$(u_{n})_{n\in\mathbb{N}}$ satisfies a recurrence relation in $R^{d}$. In this
work we will mostly encounter LRSs over $\mathbb{Q}$, called _rational LRSs_.
Examples of rational LRSs include the Fibonacci sequence, $u_{n}=p(n)$ for
$p\in\mathbb{Q}[x]$, and $u_{n}=\cos(n\theta)$ where
$\theta\in\\{\arg(\lambda)\colon\lambda\in\mathbb{Q}(i)\\}$. We refer the
reader to the books by Everest et al. (everest-recurrence-sequences, ) and
Kauers & Paule (kauers-tetrahedron, ) for a detailed discussion of linear
recurrence sequences.

An LRS $(u_{n})_{n\in\mathbb{N}}$ that is not eventually zero satisfies a
unique minimal recurrence relation $u_{n+d}=\sum_{i=0}^{d-1}a_{i}u_{n+i}$ such
that $d>0$ and $a_{0}\neq 0$. Writing
$A=\begin{bmatrix}a_{1}&\cdots&a_{d-1}\end{bmatrix}$ and
$q=\begin{bmatrix}u_{0}&\cdots&u_{d-1}\end{bmatrix}^{\top}$, the matrix

$C\coloneqq\begin{bmatrix}\mathbf{0}&I_{d-1}\\\
a_{0}&A\end{bmatrix}=\begin{bmatrix}0&1&\cdots&0\\\
\vdots&\vdots&\ddots&\vdots\\\ 0&0&\cdots&1\\\
a_{0}&a_{1}&\cdots&a_{d-1}\end{bmatrix}\in R^{d\times d}$

is called the _companion matrix_ of $(u_{n})_{n\in\mathbb{N}}$. We have that

$C^{n}q=\begin{bmatrix}u_{n}&\cdots&u_{n-d+1}\end{bmatrix}^{\top}$

and $u_{n}=e_{1}C^{n}q$ for all $n\in\mathbb{N}$, where $e_{i}$ denotes the
$i$th standard basis vector. As $a_{0}\neq 0$, the matrix $C$ is invertible
and does not have zero as an eigenvalue.

The _characteristic polynomial_ of $(u_{n})_{n\in\mathbb{N}}$ is
$p(x)=x^{d}-\sum_{i=0}^{d-1}a_{i}x^{i}$. Note that $p$ is identical to the
characteristic polynomial $\det(xI-C)$ of the companion matrix $C$. The
_eigenvalues_ (also called the _roots_) of $(u_{n})_{n\in\mathbb{N}}$ are the
$d$ (possibly non-distinct) roots $\lambda_{1},\ldots,\lambda_{d}$ of the
characteristic polynomial $p$. An LRS is

  * •

_simple_ (or _diagonalisable_) if its characteristic polynomial does not have
a repeated root, and

  * •

_non-degenerate_ if (i) all real eigenvalues are non-negative, and (ii) for
every pair of distinct eigenvalues $\lambda_{1},\lambda_{2}$, the ratio
$\lambda_{1}/\lambda_{2}$ is not a root of unity.

For each LRS $(u_{n})_{n\in\mathbb{N}}$ there exists effectively computable
$L$ such that the sequences $u^{(k)}_{n}=u_{nL+k}$ for $0\leq k<L$ are all
non-degenerate (everest-recurrence-sequences, , Section 1.1.9). If
$(u_{n})_{n\in\mathbb{N}},(v_{n})_{n\in\mathbb{N}}$ are LRSs over a field $R$,
and $\circ\in\\{+,-,\cdot\\}$, then $w_{n}=u_{n}\circ v_{n}$ also defines an
LRS over $R$ (kauers-tetrahedron, , Theorem 4.2). Moreover, if
$(u_{n})_{n\in\mathbb{N}}$ and $(v_{n})_{n\in\mathbb{N}}$ are both simple,
then so is $(w_{n})_{n\in\mathbb{N}}$.

#### The exponential polynomial representation of an LRS

Every LRS $(u_{n})_{n\in\mathbb{N}}$ of order $d>0$ over
$\overline{\mathbb{Q}}$ can be written in the form

(1) $u_{n}=\sum_{j=1}^{m}p_{j}(n)\lambda_{j}^{n}$

where $m\geq 1$, $\lambda_{1},\ldots,\lambda_{m}$ are the distinct non-zero
eigenvalues of $(u_{n})_{n\in\mathbb{N}}$, and each $p_{i}$ is a non-zero
polynomial with algebraic coefficients; see (everest-recurrence-sequences, ,
Chapter 1). Whenever these conditions on $m,\lambda_{i}$ and $p_{i}$ are met,
we say that the right-hand side is in the _exponential polynomial form_. Every
LRS $(u_{n})_{n\in\mathbb{N}}$ that is not eventually zero has a unique
representation as in (1) where the right-hand side is in the exponential
polynomial form. Moreover, the right-hand side of (1) is never identically
zero. This is a folklore result, but we provide a proof in the appendix for
completeness.

###### Lemma 2.1.

Let $u_{n}=\sum_{i=1}^{m}p_{i}(n)\lambda_{i}^{n}$ where $m\geq 1$,
$\lambda_{1},\ldots,\lambda_{m}\in\overline{\mathbb{Q}}$ are non-zero and
pairwise distinct, and each $p_{i}\in\overline{\mathbb{Q}}[x]$ is non-zero.
Then, the sequence $(u_{n})_{n\in\mathbb{N}}$ is not identically zero.
Specifically, there exists $0\leq n<d$, where
$d=\sum_{i=1}^{m}(\deg(p_{i})+1)$, such that $u_{n}\neq 0$.

We can also characterise the exponential polynomial representations of real-
valued LRS.

###### Lemma 2.2.

Let $(u_{n})_{n\in\mathbb{N}}$ be as in the statement of 2.1. If
$u_{n}\in\mathbb{R}$ for all $n\in\mathbb{N}$, then for every $1\leq i\leq m$
there exists $j$ with $1\leq j\leq m$ such that $p_{j}(n)=\overline{p_{i}}(n)$
and $\lambda_{j}=\overline{\lambda_{i}}$.

###### Proof.

We have
$\overline{u_{n}}=\sum_{j=1}^{m}\overline{p_{j}}(n)\overline{\lambda_{j}}^{n}$.
Moreover, $u_{n}=\overline{u_{n}}$ since $u_{n}\in\mathbb{R}$ for all $n$. The
result then follows from the uniqueness of the exponential polynomial
representation. ∎

Throughout this work we will encounter sequences of the form $u_{n}=p(M^{n}q)$
where $p$ is a polynomial with rational coefficients and $q$ is a vector with
rational entries. Since

$p(M^{n}q)=p(e_{1}M^{n}q,\ldots,e_{d}M^{n}q),$

each $u^{(k)}_{n}=e_{k}M^{n}q$ is an LRS over $\mathbb{Q}$ (this can be seen,
e.g., by applying the Cayley-Hamilton theorem), and LRS over $\mathbb{Q}$ are
closed under addition and multiplication, the sequence
$(p(M^{n}q))_{n\in\mathbb{N}}$ is itself an LRS over $\mathbb{Q}$.

#### Decision problems about LRS

Sign patterns of LRS have been studied for a long time. Two prominent open
problems in this area are the _Skolem Problem_ and the _Positivity Problem_.
The Skolem Problem is to find an algorithm that, given an LRS $u_{n}$, decides
if the set $Z=\\{n\colon u_{n}=0\\}$ is non-empty. The most well-known result
in this direction is the celebrated Skolem-Mahler-Lech theorem, which (non-
constructively) shows that $Z$ is semilinear. In particular, it shows that a
non-degenerate $(u_{n})_{n\in\mathbb{N}}$ can have only finitely many zeros.
The Positivity Problem, on the other hand, asks to find an algorithm that
determines if $u_{n}\geq 0$ for all $n$.

###  2.4. Markov Chains

A finite-state _discrete-time Markov chain_ (DTMC) $M$ is a tuple
$(S,P,\iota_{\mathit{init}})$, where $S$ is a finite set of states, $P:S\times
S\rightarrow[0,1]$ is the transition probability function where we require
$\sum_{s^{\prime}\in S}P_{ss^{\prime}}=1$ for all $s\in S$ and
$\iota_{init}:S\rightarrow[0,1]$ is the initial distribution, such that
$\sum_{s\in S}\iota_{init}(s)=1$. For algorithmic problems, all transition
probabilities are assumed to be rational. A finite path $\rho$ in $M$ is a
finite sequence $s_{0}s_{1}\ldots s_{n}$ of states such that
$P(s_{i},s_{i+1})>0$ for all $0\leq i\leq n-1$. We say that a state $t$ is
reachable from $s$ if there is a finite path from $s$ to $t$. If all states
are reachable from all other states, we say that $M$ is _irreducible_ ;
otherwise, we say it is _reducible_. A set $B\subseteq S$ of states is called
a bottom strongly connected component (BSCC) if it is strongly connected,
i.e., all states in $B$ are reachable form all other states in $B$ and if
there are no outgoing transitions, i.e., $P(s,t)>0$ and $s\in B$ implies $t\in
B$.

W.l.o.g., we identify $S$ with $\\{1,\dots,d\\}$ for $d=|S|$. Then,
overloading notation, we consider $P\in\mathbb{R}^{d\times d}$ as a matrix
with $P_{ij}=P(j,i)$ for $i,j\leq d$.222This is the transpose of the
transition matrix usually defined so that we are in line with our notation for
LDSs. Likewise, we consider $\iota_{\mathit{init}}$ to be a (column333Also
here, usually, this is defined as a row vector.) vector in $\mathbb{R}^{d}$
with $(\iota_{\mathit{init}})_{i}=\iota_{\mathit{init}}(i)$ for $i\leq d$.
Then, the sequence of distributions over states after $k$ steps is given by
$P^{k}\iota_{\mathit{init}}$, which forms a stochastic LDS. We also write
$P^{(k)}_{ij}$ for $(P^{k})_{ij}$, which is the probability to move from state
$j$ to $i$ in exactly $k$ steps. Further, we say that the matrix $P$ is
irreducible if the underlying Markov chain is irreducible. The period $d_{i}$
of a state $i$ is given by: $d_{i}=\textbf{gcd}\\{m\geq 1:P^{(m)}_{ii}>0\\}$.
If $d_{i}=1$, then we call the state $i$ aperiodic. A Markov chain (and its
matrix) are aperiodic if and only if all its states are aperiodic. The period
of a Markov chain $M$ and of its transition probability matrix $P$ is the
least common multiple of the periods of the states of $M$.

A vector $\pi\in\mathbb{R}^{d}$ is called a stationary distribution of the
Markov chain if: a) $\pi$ is a distribution, i.e., $\pi_{j}\geq 0$ for all $j$
with $1\leq j\leq d$, and $\sum_{j=1}^{d}\pi_{j}=1$; b) $\pi$ is stationary,
i.e., $\pi=P\pi$, which is to say that $\pi_{i}=\sum_{i\in S}P_{ij}\pi_{j}$
for all $j\in S$. For aperiodic Markov chains, it is known that the sequence
of distributions over states $(P^{k}\iota_{\mathit{init}})_{k\in\mathbb{N}}$
converges to a stationary distribution $\pi$, which can be computed in
polynomial time (see (Kulkarni1995, ; BK08, )).

##  3\. Mean payoff

In this section, we address the computation of the _mean payoff_ of an orbit.
The mean payoff is the average weight collected per step in the long-run. For
an LDS given by $M\in\mathbb{Q}^{d\times d}$ and $q\in\mathbb{Q}^{d}$ and a
weight function $w\colon\mathbb{R}^{d}\to\mathbb{R}$, we define the mean
payoff of the orbit as

$\mathit{MP}_{w}(M,q)\coloneqq\lim_{k\to\infty}\frac{1}{k+1}\sum_{i=0}^{k}w(M^{i}q).$

In the sequel, we address the problem to compute the mean payoff of the orbit
of an LDS with respect to continuous weight functions. To this end, we
restrict either the class of weight functions or the class of LDSs. In Section
3.1, we address the problem for polynomial weight functions. In Sections 3.2
and 3.3 , we consider continuous weight functions on LDSs with bounded orbit
and stochastic LDSs, respectively.

###  3.1. Polynomial weight-functions

In order to compute the mean payoff of the orbit of a rational LDS $(M,q)$
with respect to a polynomial weight function $p$ with rational coefficients,
we first recall that the sequence $(p(M^{n}q))_{n\in\mathbb{N}}$ is an LRS.
The following lemma states that the sequence of partial sums of the weights is
also an LRS.

###### Lemma 3.1.

Let $(M,q)$ be an LDS with $M\in\mathbb{Q}^{d\times d}$ and
$q\in\mathbb{Q}^{d}$, and let $p\in\mathbb{Q}[X_{1},\dots,X_{d}]$ be a
polynomial weight function with rational coefficients. The sequence

$u_{n}=\sum_{i=0}^{n}p(M^{i}q)$

is a rational LRS.

###### Proof.

As discussed in subsection 2.3, $w_{n}=p(M^{i}q)$ is a rational LRS. Suppose
$(w_{n})_{n\in\mathbb{N}}$ satisfies a recurrence relation
$w_{n+k}=a_{0}w_{n}+\ldots+a_{k-1}w_{n+k01}$, where
$a_{0},\ldots,a_{k-1}\in\mathbb{Q}$. Then
$u_{n+k+1}=u_{n+k}+a_{k-1}(w_{n+k}-w_{n+k-1})+\ldots+a_{0}(w_{n+1}-w_{n})$.
Hence $(u_{n})_{n\in\mathbb{N}}$ itself is an LRS of order at most $k+1$. ∎

Computing $\mathit{MP}_{w}(M,q)$ therefore boils down to determining whether
the limit $\lim_{n\to\infty}u_{n}/n$ exists for an LRS
$(u_{n})_{n\in\mathbb{N}}$ and computing the limit in case it exists.

###### Lemma 3.2.

Let $(u_{n})_{n\in\mathbb{N}}$ be an LRS over $\mathbb{Q}$. It is decidable
whether $\lim_{n\to\infty}u_{n}/n$ exists, in which case the limit is rational
and effectively computable.

###### Proof.

Suppose $(u_{n})_{n\in\mathbb{N}}$ is not eventually zero and write
$u_{n}=\sum_{i=1}^{m}p_{i}(n)\lambda_{i}^{n}$, where $m>0$,
$\lambda_{1},\ldots,\lambda_{m}$ are non-zero and pairwise distinct,
$|\lambda_{1}|\geq\ldots\geq|\lambda_{m}|>0$, and each $p_{i}$ is not
identically zero. Invoking (power-of-positivity, , Theorem 2), for every
$\epsilon>0$ it holds that $|u_{n}|>(|\lambda_{1}|-\epsilon)^{n}$ for
sufficiently large $n$. Hence if $|\lambda_{1}|>1$, then the limit does not
exist. Similarly, if $|\lambda_{1}|<1$, then the limit is zero. Suppose
therefore $|\lambda_{1}|=1$. Let $k$ be the largest integer such that
$|\lambda_{i}|=1$ for all $1\leq i\leq k$, and define
$v_{n}=\sum_{i=1}^{k}p_{i}(n)\lambda_{i}^{n}$. It suffices to consider
$\lim_{n\to\infty}v_{n}/n$ as
$\lim_{n\to\infty}\sum_{i=k+1}^{m}p_{i}(n)\lambda_{i}^{n}=0$.

Write $v_{n}=\sum_{i=0}^{l}n^{i}\sum_{j=1}^{k_{i}}c_{i,j}\lambda_{i,j}^{n}$
where $\sum_{j=1}^{k_{i}}c_{i,j}\lambda_{i,j}^{n}$ is in the exponential-
polynomial form for all $i$. If $l=0$, then $(v_{n})_{n\in\mathbb{N}}$ is
bounded and $\lim_{n\to\infty}v_{n}/n=0$. Assume therefore $l\geq 1$. Let

$w_{n}=\sum_{j=1}^{k_{l}}c_{l,j}\lambda_{l,j}^{n}.$

By construction, $k_{l}\geq 1$, and by 2.1, $(w_{n})_{n\in\mathbb{N}}$ is not
identically zero. It is shown in (braverman, , Lemma 4) that if
$\lambda_{l,j}\neq 1$ for some $j$ (which is implied by $k_{l}>1$), then there
exist $a,b\in\mathbb{R}$ such that $a<b$, $w_{n}<a$ for infinitely many $n$,
and $w_{n}>b$ for infinitely many $n$. Hence $\lim_{n\to\infty}v_{n}/n$ can
exist only if $k_{l}=1$ and $\lambda_{l,1}=1$. Suppose $k_{l}=1$ and
$\lambda_{l,1}=1$ indeed. Then $\lim_{n\to\infty}v_{n}/n$, when it exists, is
equal to $\lim_{n\to\infty}\frac{n^{l}c_{l,1}}{n}$. Since $l\geq 1$, the
latter limit exists if and only if $l=1$, in which case it is equal to
$c_{l,1}$ .

Suppose $\lim_{n\to\infty}v_{n}/n$ exists. To see that it must be rational,
observe that by construction there exists $1\leq i\leq k$ such that
$\lambda_{i}=1$ and $p_{i}(n)$ is equal to either $c_{l,1}$ or $nc_{l,1}$.
Recall that $\alpha\in\mathbb{C}$ is rational if and only if it is fixed by
every automorphism of $\mathbb{C}$. Since $(u_{n})_{n\in\mathbb{N}}$ takes
rational values, $\sigma(u_{n})=u_{n}$ for all $n\in\mathbb{N}$ and $\sigma$
an automorphism of $\mathbb{C}$. Moreover,
$\sigma(u_{n})=\sum_{i=1}^{m}\sigma(p_{i}(n))\sigma(\lambda_{i})^{n}$ and
$\sigma(\lambda_{l,1})=\lambda_{l,1}=1$ for every automorphism $\sigma$. By
the uniqueness of the exponential-polynomial representation,
$\sigma(c_{l,1}\lambda_{l,1}^{n})=c_{l,1}\lambda_{l,1}^{n}$ for all $n$ and
$\sigma$, which implies that $c_{l,1}$ is rational. ∎

###### Corollary 3.3.

For a rational LRS $(u_{n})_{n\in\mathbb{N}}$, it is decidable whether
$\lim_{n\to\infty}u_{n}$ exists, in which case the limit is rational and
effectively computable.

###### Proof.

The sequence $(n)_{n\in\mathbb{N}}$ is an LRS over $\mathbb{Q}$, and since
rational LRS are closed under multiplication, $v_{n}=nu_{n}$ also defines a
rational LRS. It remains to observe that
$\lim_{n\to\infty}u_{n}=\lim_{n\to\infty}v_{n}/n$ and apply Lemma 3.2. ∎

From the lemma and the corollary above, for both $(u_{n})_{n\in\mathbb{N}}$
and $(u_{n}/n)_{n\in\mathbb{N}}$, if the limit exists it is equal to a
coefficient of some $p_{i}$ appearing in the exponential polynomial solution
of $(u_{n})_{n\in\mathbb{N}}$. Hence the complexity of computing the limit is
bounded by the complexity of computing the exponential polynomial; The latter
is known to be in polynomial time if we assume the order of the LRS is fixed
(ouaknine13_posit_probl_low_order_linear_recur_sequen, ); in general, if the
description length of $(u_{n})_{n\in\mathbb{N}}$ is $\mathcal{I}$ and its
order is $d$, the time required to compute the exponential polynomial
representation of $u_{n}$ is polynomial in $\mathcal{I}^{d}$. thm:MP_LRS puts
us into the position to prove the first main result on the computation of the
mean payoff:

###### Theorem 3.4.

Let $(M,q)$ be an LDS with $M\in\mathbb{Q}^{d\times d}$ and
$q\in\mathbb{Q}^{d}$, and $p\in\mathbb{Q}[X_{1},\dots,X_{d}]$ be a polynomial
weight function with rational coefficients. It is decidable whether the mean
payoff

$\mathit{MP}_{p}(M,q)=\lim_{k\to\infty}\frac{1}{k+1}\sum_{i=0}^{k}p(M^{i}q)$

exists, in which case it is rational and computable.

###### Proof.

Immediate by 3.2 and Lemma 3.1. ∎

###  3.2. Bounded LDSs

If the orbit of an LDS is bounded, we can get our hands on the mean payoff
with respect to a continuous weight function. We exploit that the orbit of an
LDS approaches a limiting shape – which is the set of accumulation points of
the orbit – closer and closer in this case. This allows us to express the mean
payoff in terms of an integral of the weight function over this limiting
shape. This integral computes the “average” value of the weight function on
the limiting shape. Of course, we have to carefully ensure that we also know
how “frequently” the orbit approaches different parts of the limiting shape.
Let us illustrate this idea first:

###### Example 3.5.

Let $w\colon\mathbb{R}^{3}\to\mathbb{R}$ be a continuous weight function and
consider the LDS

$M=\begin{bmatrix}3/5&4/5&0\\\ -4/5&3/5&0\\\ 0&0&1/2\end{bmatrix}\quad\text{
and }\quad q=\begin{bmatrix}1\\\ 0\\\ 1\end{bmatrix}.$

Looking only at the first two coordinates a rotation is repeatedly applied in
this LDS. In the complex plane, this rotation is given by multiplication with
$3/5-4/5i$. As $3/5-4/5i$ is not a root of unity, the orbit never reaches a
point with $(1,0)$ in the first two coordinates again. In fact, the first two
components of the orbit are dense in the unit circle. Furthermore, these
components visit each interval of the same length on the circle with the same
frequency. The third component is halved at every step and converges to $0$.
As the weight function is continuous, we can hence treat the third coordinate
as equal to $0$ when determining the mean payoff. So, the set of accumulation
points of the orbit is $L=\\{v\in\mathbb{R}^{3}\mid v_{3}=0,|v|=1\\}$, which
we can parametrise via $T\colon[0,1)\to\mathbb{R}^{3}$ with
$T\colon\alpha\mapsto\begin{bmatrix}\cos(2\pi\alpha)&\sin(2\pi\alpha)&0\end{bmatrix}^{\top}$.
As this parametrisation moves through the circle with constant speed
reflecting the fact that the orbit is “equally distributed” over the circle in
the first two components, we can now express the mean payoff of the orbit with
respect to the weight function $w$ as

$\mathit{MP}_{w}(M,q)=\int_{0}^{1}w\left(\begin{bmatrix}\cos(2\pi\alpha)&\sin(2\pi\alpha)&0\end{bmatrix}^{\top}\right)\,\,\mathrm{d}\alpha.$

In the sequel, we work out all the necessary steps to check whether the orbit
of an LDS is bounded and to obtain such an expression for the mean payoff as
an integral for arbitrary rational LDSs with bounded orbit.

#### Jordan normal form and boundedness of the orbit

Throughout this section, fix a matrix $M\in\mathbb{Q}^{d\times d}$, an initial
vector $q\in\mathbb{Q}^{d}$, and a continuous weight function
$w\colon\mathbb{R}^{d}\to\mathbb{R}$. We first transform the matrix $M$ into
Jordan normal form by computing matrices $J$ and $B$ as well as the inverse
$B^{-1}$ with algebraic entries such that

$M=B\cdot J\cdot B^{-1}$

where $J$ is in Jordan form with the eigenvalues of $M$ on the diagonal and
$B$ is an invertible matrix with generalized eigenvectors of $M$ as columns in
polynomial time (cai-jnf-in-poly-time, ). Since multiplication with $B$ is a
linear bijection, $(M^{k}\cdot q)_{k\in\mathbb{N}}$ is bounded if and only if
the sequence $(J^{k}\cdot(B^{-1}q))_{k\in\mathbb{N}}$ is bounded. To check
whether this is the case, we first simplify the sequence.

We use the notation $J_{\alpha,\ell}$ to denote a Jordan block of size $\ell$
with $\alpha$ on the diagonal. Observe that multiplying a Jordan block to a
vector $q=[q_{1},\dots,q_{k},0,\dots,0,]^{\top}$ in which the last $\ell-k$
components are $0$ results in a vector where this is still the case:

$J_{\alpha,\ell}\cdot q=\begin{bmatrix}\alpha&1&0&\dots&0\\\
0&\ddots&\ddots&\ddots&\vdots\\\ \vdots&\ddots&\alpha&1&0\\\
\vdots&&\ddots&\alpha&1\\\
0&\dots&\dots&0&\alpha\end{bmatrix}\cdot\begin{bmatrix}q_{1}\\\ \dots\\\
q_{k}\\\ 0\\\ \dots\\\
0\end{bmatrix}=\begin{bmatrix}J_{\alpha,k}\cdot\begin{bmatrix}q_{1}\\\
\dots\\\ q_{k}\end{bmatrix}\\\ 0\\\ \dots\\\ 0\end{bmatrix}$

Looking at the initial vector $B^{-1}q$, this allows us to simplify the LDS by
determining the coordinates at which the orbit
$(J^{k}B^{-1}q)_{k\in\mathbb{N}}$ always stays $0$. Suppose the Jordan blocks
in $J$ end at coordinates $i_{1},\dots,i_{m}$, respectively, with $1\leq
i_{1}<i_{2}<i_{m}=d$. Now, let

$\displaystyle I=\\{i\in\\{1,\dots,d\\}\mid$ for some index $h$,
$\displaystyle\text{ all $j$ with $i\leq j\leq i_{h}$ satisfy
$(B^{-1}q)_{j}=0$}\\}.$

So, $I$ contains only dimensions $j$ such that $(J^{k}(B^{-1}q))_{j}=0$ for
all $k$. We now set all columns and rows of $J$ with an index in $I$ to $0$.
This does not affect the orbit $(BJ^{k}B^{-1}q)_{k\in\mathbb{N}}$. After this
simplification, the following condition, which we can assume w.l.o.g., is
satisfied.

###### Assumption 1.

The LDS given by $M\in\mathbb{Q}^{d\times d}$ and $q\in\mathbb{Q}^{d}$ has the
following property: For the Jordan normal form $M=B\cdot J\cdot B^{-1}$ of $M$
and $v\stackrel{{\scriptstyle\text{\tiny def}}}{{=}}B^{-1}q$, we have that
$v_{i}\not=0$ for any coordinate $1\leq i\leq d$ at which a non-zero Jordan
block of $J$ ends.

###### Proposition 3.6.

Under Assumption 1, the orbit $(J^{k}q)_{k\in\mathbb{N}}$ is bounded if and
only if all eigenvalues on the diagonal of $J$ have modulus at most $1$ and
the Jordan blocks in $J$ with an eigenvalue $\alpha$ with $|\alpha|=1$ have
size $1$.

We delegate the proof to the appendix. Proposition 3.6 allows us to decide
whether the orbit of the LDS given by $M$ and $v$ is bounded. From now on, we
assume that it is bounded. We now further simplify the LDS by removing all
eigenvalues with modulus less than $1$: For a Jordan block $J_{\alpha,\ell}$
with $|\alpha|<1$, we know $J_{\alpha,\ell}\to 0$ for $k\to\infty$. As we
apply the function $B$ viewed as a linear map and the _continuous_ function
$w$ to the points in the orbit and as the mean payoff does not depend on a
prefix of the orbit, we can set all such Jordan blocks to $0$ without
affecting the mean payoff. So, w.l.o.g. we can work under the following
assumption after this simplification because the Jordan blocks with
eigenvalues with modulus $1$ have size $1$ in the light of Proposition 3.6:

###### Assumption 2.

The matrix $M$ of the rational LDS $(M,q)$ is diagonalisable and all non-zero
eigenvalues have modulus $1$. So, there is a computable algebraic matrix $B$
with computable inverse $B^{-1}$ and a computable algebraic diagonal matrix
$D$ whose entries all have modulus $1$ or $0$ with $M=B\cdot D\cdot B^{-1}$.

#### Multiplicative relations between the eigenvalues

Before we can parametrise the set of accumulation points of the orbit, we have
to detect _multiplicative relations_ between the elements on the diagonal of
$D$. Before defining (the group of) multiplicative relations, let us
illustrate this concept in an example:

###### Example 3.7.

Consider the matrix $D=\begin{bmatrix}\lambda&0\\\
0&\bar{\lambda}\end{bmatrix}$ for an algebraic number $\lambda$ with
$|\lambda|=1$ that is not a root of unity. Then, $\lambda\cdot\bar{\lambda}=1$
is a multiplicative relation between $\lambda$ and $\bar{\lambda}$. Further,
$(\lambda^{k})_{k\in\mathbb{N}}$ is dense in the torus
$\mathbb{T}\coloneqq\\{x\in\mathbb{C}\mid|x|=1\\}$. Now, the sequence
$\left(\lambda^{k},\bar{\lambda}^{k}\right)_{k\in\mathbb{N}}$ is dense in
$L\coloneqq\\{(x,y)\in\mathbb{T}^{2}\mid x\cdot y=1\\}$, but not in
$\mathbb{T}^{2}$. So, for an initial vector $v$, the set of accumulation
points of $(D^{k}v)_{k\in\mathbb{N}}$ is $L\cdot v$ and not
$\mathbb{T}^{2}\cdot v$.

We follow an approach also taken in (kelmendi2022, ) to detect multiplicative
relations between the algebraic numbers
$\lambda_{1},\ldots,\lambda_{d}\in\overline{\mathbb{Q}}$. We work under
Assumption 2 and we first reorder the coordinates such that the entries on the
diagonal of $D$ are
$\lambda_{1},\dots,\lambda_{\ell},\lambda_{\ell+1},\dots,\lambda_{d}$ where
$\lambda_{i}$ is not $0$ or $1$ for $i\leq\ell$ and the entries $\lambda_{j}$
with $j>\ell$ are all equal to $0$ or $1$. The group

$G\coloneqq
G(\lambda_{1},\ldots,\lambda_{\ell})=\\{(m_{1},\ldots,m_{\ell})\in\mathbb{Z}^{\ell}\mid\>\lambda_{1}^{m_{1}}\cdots\lambda_{\ell}^{m_{\ell}}=1\\}$

is called the _group of multiplicative relations_ between
$\lambda_{1},\ldots,\lambda_{\ell}$. If this group is consists only of the
neutral element, we say that $\lambda_{1},\ldots,\lambda_{\ell}$ are
_multiplicatively independent_.

Note that $G$ is a free abelian group, and has a basis of at most $\ell$
elements from $\mathbb{Z}^{\ell}$. By a deep result of Masser (masser-mult-
relations, ), $G$ has a basis $B$ such that for each $v\in B$,
$\|v\|_{\infty}<p(\|\lambda_{1}\|+\ldots+\|\lambda_{\ell}\|)^{\ell}$, where
$p$ is an absolute polynomial. Hence a basis of $G$ can be computed in
polynomial space (given $\lambda_{1},\ldots,\lambda_{\ell}$) by simply
enumerating all possible bases satisfying Masser’s bound. As described in
detail in (kelmendi2022, ), each element $(b_{1},\dots,b_{\ell})\in B$ of the
basis allows us to express one of the eigenvalues in terms of the others:
Suppose $b_{j}\not=0$. Then, the equation
$\lambda_{1}^{b_{1}}\cdots\lambda_{\ell}^{b_{\ell}}=1$, allows us to conclude

$\lambda_{j}^{b_{j}}=\prod_{i\not=j}\lambda_{i}^{-b_{i}}\qquad\text{ and hence
}\qquad\lambda_{j}=\rho_{j}\prod_{i\not=j}\lambda_{i}^{-b_{i}/b_{j}}$

where $\rho_{j}$ is a $b_{j}$th root of unity. Applying this procedure
consecutively to all elements of the basis $B$, we can divide and reorder the
eigenvalues $\lambda_{1},\dots,\lambda_{\ell}$ as
$\lambda_{1},\dots,\lambda_{m},\lambda_{m+1},\dots,\lambda_{\ell}$ such that
$\lambda_{1},\dots,\lambda_{m}$ are multiplicatively independent and such that
each $\lambda_{j}$ with $m+1\leq j\leq\ell$ is not $1$ and can be written as

$\lambda_{j}=\rho_{j}\cdot\prod_{i=1}^{m}\lambda_{i}^{q_{j,i}}$

where $\rho_{j}$ is a root of unity and $q_{j,i}\in\mathbb{Q}$ for $1\leq
i\leq m$.

#### Subsequences without periodicity

The fact that expression for the eigenvalues $\lambda_{j}$ with $m+1\leq
j\leq\ell$ contains the $b_{j}$th root of unity $\rho_{j}$ introduces a
periodic behavior to the sequence $(\lambda_{j}^{k})_{k\in\mathbb{N}}$. In
order to eliminate this periodic behavior, we divide the orbit into
subsequences as follows: We let $P$ be the least common multiple of the values
$b_{j}$ for $m+1\leq j\leq\ell$. As $\rho_{j}$ is a $b_{j}$th root of unity,
$\rho_{j}^{P}=1$ for all $j$ with $m+1\leq j\leq\ell$. We now split the
sequence $(D^{k})_{k\in\mathbb{N}}$ into the $P$ subsequences of the form
$(D^{Pk+r})_{k\in\mathbb{N}}$ for $r\in\\{0,\dots,P-1\\}$. The diagonal
entries of $D^{kP}$ are

$\lambda_{1}^{Pk},\dots,\lambda_{m}^{Pk},\prod_{i=1}^{m}(\lambda_{i}^{Pk})^{q_{m+1,i}},\dots,\prod_{i=1}^{m}(\lambda_{i}^{Pk})^{q_{\ell,i}},\lambda_{\ell+1},\dots,\lambda_{d}.$

Recall here that $\lambda_{\ell+1},\dots,\lambda_{d}$ are all $0$ or $1$.

We can now express any point in the orbit $BD^{Pk+r}B^{-1}q$ in terms of
$\lambda_{1}^{k},\dots,\lambda_{m}^{k}$ and $D^{r}$. To this end, we define
the map $T_{r}\colon\mathbb{T}^{m}\to\mathbb{R}^{d}$ by setting

$\displaystyle\Delta=\mathrm{diag}\left(\mu_{1}^{P},\dots,\mu_{m}^{P},\prod_{i=1}^{m}(\mu_{i}^{P})^{q_{m+1,i}},\dots,\prod_{i=1}^{m}(\mu_{i}^{P})^{q_{\ell,i}},\lambda_{\ell+1},\dots,\lambda_{d}\right),$

where $\mathrm{diag}(x_{1},\dots,x_{d})$ denotes a diagonal matrix with
$x_{1},\dots,x_{d}$ on the diagonal, and

$\displaystyle T_{r}(\mu_{1},\dots,\mu_{m})=BD^{r}\Delta B^{-1}q.$

The map $T$ is chosen such that

$T_{r}(\lambda_{1}^{k},\dots,\lambda_{m}^{k})=BD^{Pk+r}B^{-1}q.$

This is also the reason why $T_{r}$ maps into $\mathbb{R}^{d}$.

#### Parametrising the set of accumulation points

For a real $x$, we define $x\mod 1:=x-\lfloor x\rfloor$. For $1\leq j\leq m$,
we define the number $\alpha_{j}\in[0,1)$ as the unique number with
$\lambda_{j}=e^{2\pi i\alpha_{j}}$. Let $S\colon[0,1)^{m}\to\mathbb{T}^{m}$
(recall that $\mathbb{T}\coloneqq\\{x\in\mathbb{C}\mid|x|=1\\}$) be the map

$\displaystyle(\beta_{1},\dots,\beta_{m})\mapsto(e^{2\pi
i\beta_{1}},\dots,e^{2\pi i\beta_{m}}).$

So, we get $(\lambda_{1}^{k},\dots,\lambda_{m}^{k})=S(k\alpha_{1}\mod
1,\dots,k\alpha_{m}\mod 1)$ and hence

$BD^{Pk+r}B^{-1}q=T_{r}(S(k\alpha_{1}\mod 1,\dots,k\alpha_{m}\mod 1)).$

Following the exposition in (kelmendi2022, ), we can now apply an
equidistribution theorem by Weyl (Weyl1916, ). First, observe that the fact
that $\lambda_{1},\dots,\lambda_{m}$ are multiplicatively independent means
that the values $1,\alpha_{1},\dots,\alpha_{m}$ are linearly independent over
$\mathbb{Q}$: If there were a non-zero vector $c_{0},c_{1},\dots,c_{m}$ with
$c_{0}+\sum_{j=1}^{m}c_{j}\alpha_{j}=0$, this vector would witness a
multiplicative relation between $\lambda_{1},\dots,\lambda_{m}$. In (Weyl1916,
), it is now shown that for any measurable set $U\subseteq[0,1)^{m}$, we have

$\lim_{n\to\infty}\frac{|\\{0\leq k\leq n\mid(k\alpha_{1}\mod
1,\dots,k\alpha_{m}\mod 1)\in U\\}|}{n+1}=\mathcal{L}(U)$

where $\mathcal{L}$ is the Lebesgue measure. For more details, we also refer
to the exposition of this argument in (kelmendi2022, ).

This means that the sequence of arguments $((k\alpha_{1}\mod
1,\dots,k\alpha_{m}\mod 1))_{k\in\mathbb{N}}$ is dense and “equally
distributed” in the cube $[0,1)^{m}$, and hence the sequence
$((\lambda_{1}^{k},\dots,\lambda_{m}^{k}))_{k\in\mathbb{N}}$ is dense and
“equally distributed” in the $m$-dimensional torus $\mathbb{T}^{m}$ where
“equally distributed” means that every subset of the same size is hit equally
often in the sense of Equation ($\ast$).

#### Mean payoff as integral

Now, we are in the position to prove the main result of this subsection: The
mean payoff of a bounded orbit wrt a continuous weight function can be
expressed as an integral.

###### Theorem 3.8.

Let $M\in\mathbb{Q}^{d\times d}$ be a matrix and $q\in\mathbb{Q}^{d}$ an
initial vector satisfying Assumption 2. Let
$w\colon\mathbb{R}^{d}\to\mathbb{R}$ be a continuous weight function. Let
$P\in\mathbb{N}$ and $T_{r}\colon\mathbb{T}^{m}\to\mathbb{R}^{d}$ for $r<P$,
and $S\colon[0,1)^{m}\to\mathbb{T}^{m}$ be as above. Then, for each $r$ with
$0\leq r<P$, the mean payoff of the sub-orbit $(M^{kP+r}q)_{k\in\mathbb{N}}$
wrt $w$ exists and can be expressed as

$\mathit{MP}_{w}(M^{P},M^{r}q)=\lim_{k\to\infty}\frac{1}{k+1}\sum_{i=0}^{k}w(M^{kP+r}q)=\int_{[0,1)^{m}}w\circ
T_{r}\circ S\,\,\mathrm{d}\mathcal{L}$

where $\mathcal{L}$ is the Lebesgue measure on $[0,1)^{m}$. The mean payoff of
the original orbit is then the arithmetic mean

$\mathit{MP}_{w}(M,q)=\frac{\sum_{r=0}^{P-1}\mathit{MP}_{w}(M^{P},M^{r}q)}{P}.$

###### Proof.

Let $\alpha_{1},\dots,\alpha_{m}\in[0,1)$ be such that $\lambda_{j}=e^{2\pi
i\alpha_{j}}$ as above. For $r<P$, we have constructed $S$ and $T_{r}$ such
that

$M^{kP+r}q=T_{r}(S(k\alpha_{1}\mod 1,\dots,k\alpha_{m}\mod 1))$

for all $k$. As $w$ is continuous, it can be written as sum of Lebesgue
measurable step functions $w=\sum_{j=0}^{\infty}f_{j}\cdot\mathbbm{1}_{A_{j}}$
where, for all $j$, the coefficient $f_{j}$ is in $\mathbb{R}$, the set
$A_{j}\subseteq\mathbb{R}^{d}$ is measurable, and $\mathbbm{1}_{A_{j}}$ is $1$
on points in $A_{j}$ and $0$ otherwise. For $\mathbbm{1}_{A_{j}}$, we now
observe

$\displaystyle\lim_{k\to\infty}\frac{1}{k+1}\sum_{i=0}^{k}\mathbbm{1}_{A_{j}}(M^{kP+r}q)$
$\displaystyle=\lim_{k\to\infty}\frac{1}{k+1}\sum_{i=0}^{k}\mathbbm{1}_{A_{j}}(T_{r}(S(k\alpha_{1}\mod
1,\dots,k\alpha_{m}\mod 1)))$ $\displaystyle=\lim_{k\to\infty}\frac{|\\{i\leq
k\mid T_{r}(S(i\alpha_{1}\mod 1,\dots,i\alpha_{m}\mod 1))\in A_{j}\\}|}{k+1}$
$\displaystyle=\mathcal{L}((T_{r}\circ S)^{-1}(A_{j}))$

where the last equality follows from equation ($\ast$) that is stated above
and shown in (Weyl1916, ). But, we also have

$\int_{[0,1)^{m}}\mathbbm{1}_{A_{j}}\circ T_{r}\circ
S\,\,\mathrm{d}\mathcal{L}=\mathcal{L}((T_{r}\circ S)^{-1}(A_{j})).$

Putting this together, we obtain

$\displaystyle\mathit{MP}_{w}(M^{P},M^{r}q)$
$\displaystyle=\lim_{k\to\infty}\frac{1}{k+1}\sum_{i=0}^{k}w(M^{kP+r}q)$
$\displaystyle=\sum_{j=0}^{\infty}f_{j}\cdot\lim_{k\to\infty}\frac{1}{k+1}\sum_{i=0}^{k}\mathbbm{1}_{A_{j}}(M^{kP+r}q)$
$\displaystyle=\sum_{j=0}^{\infty}f_{j}\cdot\int_{[0,1)^{m}}\mathbbm{1}_{A_{j}}\circ
T_{r}\circ S\,\,\mathrm{d}\mathcal{L}$ $\displaystyle=\int_{[0,1)^{m}}w\circ
T_{r}\circ S\,\,\mathrm{d}\mathcal{L}.$

This finishes the proof of the first claim. The claim that the mean payoff
$MP_{w}(M,q)$ can now be expressed as the arithmetic mean is obvious. ∎

#### Approximation of the mean payoff

Although we can compute explicit representations of the functions $T_{r}$ and
$S$, it remains unclear – even for simple functions $w$ – how to compute the
integrals $\int_{[0,1)^{m}}w\circ T_{r}\circ S\,\,\mathrm{d}\mathcal{L}$ whose
arithmetic mean is the mean payoff of the original LDS. Nevertheless, the
numerical approximation of integrals is an extensively studied area (see,
e.g., (davis2007methods, )). The function $S$ is a simple parametrisation of
the $d$-dimensional torus and the function $T_{r}$ is a polynomial with
algebraic coefficients that we can explicitly compute. In particular, both
functions are differentiable and we can bound the modulus of the gradient of
$T_{r}\circ S$ on $[0,1]^{m}$. So, if the function $w$ can be approximated and
is well-behaved, e.g., if $w$ is Lipschitz continuous with known upper bound
for its Lipschitz constant, also the integrals that we obtained can be
approximated to arbitrary precision. In particular, for a polynomial weight
function $w$, the mean payoff can be approximated to arbitrary precision as
polynomials are Lipschitz continuous on the compact set $T_{r}\circ
S([0,1]^{m})$ and a bound for the Lipschitz constant can be computed from the
gradient of $w$. For more details on conditions under which the integral can
be approximated to arbitrary precision, we refer the reader to
(davis2007methods, ).

###  3.3. Stochastic LDSs

Stochastic LDSs are a special case of LDSs with a bounded orbit. In this
section, we will show that in the case of stochastic LDSs, we can compute the
mean payoff of the orbit under a continuous weight function by evaluating the
weight function on finitely many points. In the aperiodic case, the orbit even
converges to a single point so that it suffices to evaluate the weight
function once:

###### Lemma 3.9.

Let $P\in\mathbb{Q}^{d\times d}$ be a stochastic, aperiodic matrix and
$\iota_{\mathit{init}}\in\mathbb{Q}^{d}$ an initial distribution. Furthermore,
let $w\colon\mathbb{R}^{d}\to\mathbb{R}$ be a continuous weight function.
Then, $\mathit{MP}_{w}(P,\iota_{\mathit{init}})=w(\pi)$ where $\pi$ is the
stationary distribution $\lim_{k\to\infty}P^{k}\iota_{\mathit{init}}$ of $P$,
which is computable in polynomial time.

###### Proof.

As described in Section 2.4, we know that the orbit
$(P^{k}\iota_{\mathit{init}})_{k\in\mathbb{N}}$ converges to a stationary
distribution $\pi$ in this case, which can be computed in polynomial time
(Kulkarni1995, ; BK08, ). So, $\lim_{k\to\infty}P^{k}\iota_{\mathit{init}}$
exists and, as $w$ is continuous, we know
$\lim_{k\to\infty}w(P^{k}\iota_{\mathit{init}})=w(\pi)$. It is straightforward
to observe that

$\mathit{MP}_{w}(P,\iota_{\mathit{init}})\stackrel{{\scriptstyle\text{\tiny
def}}}{{=}}\lim_{k\to\infty}\frac{1}{k+1}\sum_{i=0}^{k}w(P^{i}\iota_{\mathit{init}})=w(\lim_{k\to\infty}P^{k}\iota_{\mathit{init}})=w(\pi).\qed$

Hence the computation of the mean payoff boils down to evaluating the function
$w$ once on a rational point computable in polynomial time in this case. We
next address the periodic case by splitting up the orbit into subsequences.

For an irreducible and periodic Markov chain with period $L$, we have that
$P^{L}$ is aperiodic and $L\leq d$ by (NorrisMC, , Theorem 1.8.4). Together
with Lemma 12, this allows us to characterize
$\mathit{MP}_{w}(P^{L},P^{r}\iota_{\mathit{init}})$, which is the mean payoff
of $(P^{Lk+r}\iota_{\mathit{init}})_{k\in\mathbb{N}}$. We conclude

$\mathit{MP}_{w}(P,\iota_{\mathit{init}})=\frac{1}{L}\sum_{r=0}^{L-1}\mathit{MP}_{w}(P,P^{r}\iota_{\mathit{init}}).$

So, for irreducible stochastic LDSs, we can divide
$(P^{Lk+r}\iota_{\mathit{init}})_{k\in\mathbb{N}}$ into $L$ equally spaced
subsequences and compute the mean payoff
$\mathit{MP}_{w}(P,\iota_{\mathit{init}})$ as the arithmetic mean of the mean
payoffs of these subsequences.

###### Theorem 3.10.

Let $P\in\mathbb{Q}^{d\times d}$ be a stochastic, irreducible matrix and
$\iota_{\mathit{init}}\in\mathbb{Q}^{d}$ an initial distribution. Let
$w\colon\mathbb{R}^{d}\to\mathbb{R}$ be a continuous weight function. Then, we
can compute points $\pi_{0},\dots,\pi_{L-1}\in\mathbb{Q}^{d}$ in polynomial
time for some $L\leq d$ such that
$\mathit{MP}_{w}(P,\iota_{\mathit{init}})=\frac{1}{L}\sum_{i=0}^{L-1}w(\pi_{i})$.

As the points $\pi_{0},\dots,\pi_{L-1}$ can be computed in polynomial time and
are hence of length at most polynomial in the length of the original input, we
can conclude the following statement about the approximation of the mean
payoff:

###### Corollary 3.11.

Assume that the value $w(a)$ can be approximated in time
$f_{w}(\|a\|,\epsilon)$ up to some precision $\epsilon\geq 0$ (where
$\epsilon=0$ corresponds to exact computation) for all rational inputs
$a\in\mathbb{Q}^{d}$, where $\|a\|$ is the bitlength of $a$. There is a fixed
polynomial $p$ such that the mean payoff
$\mathit{MP}_{w}(P,\iota_{\mathit{init}})$ can be approximated up to precision
$\epsilon$ in time at most $d\cdot
f_{w}(p(\|(P,\iota_{\mathit{init}})\|,\epsilon)+p(\|(P,\iota_{\mathit{init}})\|)$
where $\|(P,\iota_{\mathit{init}})\|$ is the bit length of the original input.

When a Markov chain is reducible, the states can be renamed in a way such
that, the matrix representation of the Markov chain will contain distinct
blocks corresponding to the bottom strongly connected components (BSCCs) on
the diagonal along with additional columns at the right representing states
that do not belong to any BSCC:

$\begin{bmatrix}\begin{matrix}\leavevmode\resizebox{20.00003pt}{}{\Huge$\square$}\end{matrix}&0...0&0...0&\ast&\ast\\\
0...0&\begin{matrix}\leavevmode\resizebox{25.00003pt}{}{\Huge$\square$}\end{matrix}&0...0&\ast&\ast\\\
0...0&0...0&\begin{matrix}\leavevmode\resizebox{20.00003pt}{}{\Huge$\square$}\end{matrix}&\ast&\ast\\\
0...0&0...0&0....0&\ast&\ast\end{bmatrix}$

Each block representing a BSCC constitutes an irreducible Markov chain. Assume
we have $k$ blocks with periods $L_{1},L_{2},...,L_{k}$ correspondingly. Let
$l$ be the least common multiple of the periods. Now we will have $l$
subsequences of the orbit each of which will converge. The convergence of the
rows in the bottom is a result of the fact that Markov chain will enter a BSCC
with probability 1. So, in general, we have $l$ subsequences of the orbit, all
of which converge. We observe that $l\leq d^{d}$, from which the following
result follows:

###### Theorem 3.12.

Let $P\in\mathbb{Q}^{d\times d}$ be a stochastic matrix and
$\iota_{\mathit{init}}\in\mathbb{Q}^{d}$ an initial distribution. Let
$w\colon\mathbb{R}^{n}\to\mathbb{R}$ be a continuous weight function. Then, we
can compute points $\pi_{0},\dots,\pi_{l-1}\in\mathbb{Q}^{d}$ in exponential
time for some $l\leq d^{d}$ such that
$\mathit{MP}_{w}(P,\iota_{\mathit{init}})=\frac{1}{l}\sum_{i=0}^{l-1}w(\pi_{i})$.

As the transition matrix $P^{l}$ of the $l$ subsequences as well as the
initial values $P^{r}\iota_{\mathit{init}}$ with $0\leq r<l$ can be computed
in polynomial time by repeated squaring, each of the points $\pi_{i}$ with
$0\leq i<l$ can be computed in polynomial time. Assuming that the value $w(a)$
can be approximated in time $f_{w}(\|a\|,\epsilon)$ for all rational inputs
$a\in\mathbb{Q}^{d}$, we can hence conclude that there is again a fixed
polynomial $q$ such that the mean payoff of reducible stochastic LDSs can be
approximated to precision $\epsilon$ in time bounded by $d^{d}\cdot
f_{w}(q(\|(P,\iota_{\mathit{init}})\|,\epsilon)+d^{d}\cdot
q(\|(P,\iota_{\mathit{init}})\|)$ analogously to 3.11.

##  4\. Total (discounted) reward and satisfaction of energy constraints

In this section, again let $M\in\mathbb{Q}^{d\times d}$ be a matrix,
$q\in\mathbb{Q}^{d}$ be an initial vector, and
$w\colon\mathbb{R}^{d}\to\mathbb{R}$ be a polynomial weight function with
rational coefficients. We define the _total reward_ as

$\mathrm{tr}(M,q,w):=\sum_{k=0}^{\infty}w(M^{k}q).$

Likewise, for a rational discount factor $\delta\in(0,1)$ we define the _total
discounted reward_ as

$\mathrm{dr}(M,q,w,\delta):=\sum_{k=0}^{\infty}\delta^{k}w(M^{k}q).$

Both of these quantities, when they exist, can be determined effectively.

###### Theorem 4.1.

It is decidable whether the series $\sum_{k=0}^{\infty}w(M^{k}q)$ and
$\sum_{k=0}^{\infty}\delta^{k}w(M^{k}q)$ converge, in which case their values
are rational and can be computed.

###### Proof.

Let $u_{n}=\sum_{k=0}^{n}w(M^{k}q)$. As discussed in subsection 3.1,
$(u_{n})_{n\in\mathbb{N}}$ is a rational LRS, and we can apply 3.3. Similarly,
let $v_{n}=\sum_{k=0}^{\infty}\delta^{k}w(M^{k}q)$. As
$(\delta^{n})_{n\in\mathbb{N}}$ is itself a (rational) LRS and such LRS are
closed under pointwise multiplication, $v_{n}$ is also a rational LRS. We
again apply 3.3. ∎

We next discuss _energy constraints_. We say that a series of real weights
$(w_{i})_{i\in\mathbb{N}}$ satisfies the energy constraint with budget $B$ if

$\sum_{i=0}^{k}w_{i}\geq-B$

for all $k\in\mathbb{N}$. We will prove that for LDS $(M,q)$ of dimension at
most 3, satisfaction of energy constraints is decidable. The proof is based on
the fact that three-dimensional systems are tractable thanks to Baker’s
theorem (karimov-ltl-3d, ). For higher-dimensional systems, no such
tractability result is known. We will show that deciding satisfaction of
energy constraints is, in general, at least as hard as the Positivity Problem,
already with linear weight functions.

###  4.1. Baker’s theorem and its applications

A _linear form in logarithms_ is an expression of the form
$\Lambda=b_{1}\operatorname{Log}\alpha_{1}+\ldots+b_{m}\operatorname{Log}\alpha_{m}$
where $b_{i}\in\mathbb{Z}$ and $\alpha_{i}\in\overline{\mathbb{Q}}$ for all
$1\leq i\leq m$. Here $\operatorname{Log}$ denotes the principal branch of the
complex logarithm. The celebrated theorem of Baker places a lower bound on
$|\Lambda|$ in case $\Lambda\neq 0$. Baker’s theorem, as well as its $p$-adic
analogue, play a critical role in the proof of
(tijdeman_distan_between_terms_algeb_recur_sequen, ) that the Skolem Problem
is decidable for LRS of order at most 4, as well as decidability of the
Positivity Problem for low-order LRS.

###### Theorem 4.2 (Special case of the main theorem in (baker-rational-sharp-
version-1993, )).

Let
$\Lambda=b_{1}\operatorname{Log}\alpha_{1}+\ldots+b_{m}\operatorname{Log}\alpha_{m}$
be as above, $D=[\mathbb{Q}(\alpha_{1},\ldots,\alpha_{m}):\mathbb{Q}]$, and
suppose $A,B\geq e$ are such that $A>H(\alpha_{i})$ and $B>|b_{i}|$ for all
$1\leq i\leq m$. If $\Lambda\neq 0$, then

$\log|\Lambda|>-(16mD)^{2(m+2)}(\log A)^{m}\log B.$

A direct consequence of Baker’s theorem is the following (ouaknine_simple-
positivity, , Corollary 8). Recall that $\mathbb{T}$ denotes
$\\{z\in\mathbb{C}\colon|z|=1\\}$.

###### Lemma 4.3.

Let $\alpha\in\mathbb{T}\cap\overline{\mathbb{Q}}$ and
$\beta\in\overline{\mathbb{Q}}$. For all $n\geq 2$, if $\alpha^{n}\neq\beta$
then $|\alpha^{n}-\beta|>n^{-C}$ where $C$ is an effective constant that
depends on $\alpha$ and $\beta$.

If $\alpha$ is not a root of unity, $\alpha^{n}=\beta$ holds for at most one
$n$ and $n$ can be effectively bounded.

###### Lemma 4.4.

Let $\alpha,\beta\in\overline{\mathbb{Q}}$ be non-zero, and suppose $\alpha$
is not a root of unity. There exists effectively computable $N\in\mathbb{N}$
such that $\alpha^{n}\neq\beta$ for all $n\in\mathbb{N}$ with $n>N$.

Combining the two lemmas above, we obtain the following.

###### Theorem 4.5.

Let $\alpha\in\mathbb{T}$, $\beta\in\mathbb{Q}$, and suppose $\alpha$ is not a
root of unity. There exists effectively computable $N,C\in\mathbb{N}$ such
that for $n>N$, $|\alpha^{n}-\beta|>n^{-C}$.

The next lemma summarises the family of linear recurrence sequences to which
we can apply Baker’s theorem. For reasons of space we delegate the proof to
the appendix.

###### Lemma 4.6.

Let $\gamma\in\mathbb{T}$ be not a root of unity,
$r_{1},\ldots,r_{\ell}\in\mathbb{R}$ be non-zero, and
$u_{n}=\sum_{i=1}^{m}c_{i}\Lambda_{i}^{n}$ be an LRS over $\mathbb{R}$ where
$m\geq 1$, $c_{i},\Lambda_{i}\in\overline{\mathbb{Q}}$ are non-zero for all
$i$, and $\Lambda_{1},\ldots,\Lambda_{m}$ are pairwise distinct. Suppose each
$\Lambda_{i}$ is in the multiplicative group generated by
$\\{\gamma,r_{1},\ldots,r_{\ell}\\}$.

  * (a)

There exists effectively computable $N_{1}$ such that $u_{n}\neq 0$ for all
$n>N_{1}$.

  * (b)

For $n>N_{1}$, $|u_{n}|>L^{n}n^{-C}$, where $L=\max_{i}|\Lambda_{i}|$ and $C$
is an effectively computable constant.

  * (c)

It is decidable whether $u_{n}\geq 0$ for all $n$.

###  4.2. Satisfaction of energy constraints

Before giving our decidability result, we need one final ingredient about
partial sums of LRS. Let $w_{n}=n^{l}\lambda^{n}$ for some $l\geq 0$ and
$\lambda\in\overline{\mathbb{Q}}$, and $u_{n}=\sum_{k=0}^{n}w_{k}$. If
$\lambda=1$, then $u_{n}=p(n)$, where $p$ is a polynomial of degree $l+1$. If
$\lambda\neq 1$, then $u_{n}=q(n)\lambda^{n}$, where $q$ is a polynomial of
degree at most $l$ with algebraic coefficients. In particular, $q(n)$ is a
solution of the functional equation $\lambda f(n)-f(n-1)=n^{l}$. It follows
that if the LRS $(w_{n})_{n\in\mathbb{N}}$ has only real eigenvalues, then so
does the sequence given by $u_{n}=\sum_{k=0}^{n}w_{k}$. Similarly, if
$(w_{n})_{n\in\mathbb{N}}$ is diagonalisable and does not have 1 as an
eigenvalue, then the same applies to $(u_{n})_{n\in\mathbb{N}}$. In fact, the
eigenvalues of $(u_{n})_{n\in\mathbb{N}}$ form a subset of the eigenvalues of
$(w_{n})_{n\in\mathbb{N}}$.

###### Theorem 4.7.

Let $M\in\mathbb{Q}^{3\times 3}$, $q\in\mathbb{Q}^{3}$, $\delta\leq 1$ be a
discount factor, and $w\colon\mathbb{R}^{3}\to\mathbb{R}$ be a polynomial
weight function with rational coefficients. For $B\in\mathbb{Q}_{\geq 0}$, it
is decidable whether the weights $(\delta^{n}w(M^{n}q))_{n\in\mathbb{N}}$
satisfy the energy constraint with budget $B$.

###### Proof.

Let $w_{n}=\delta^{n}w(M^{n}q)$ and $u_{n}=B+\sum_{i=0}^{n}w(M^{i}q)$. We have
to decide if $u_{n}\geq 0$ for all $n$. First suppose $M$ has only real
eigenvalues. Then $w_{n}$ and $u_{n}$ are both LRSs with only real
eigenvalues. By taking subsequences if necessary, we can assume
$(u_{n})_{n\in\mathbb{N}}$ is non-degenerate. Write
$u_{n}=\sum_{i=1}^{m}p_{i}(n)\rho_{i}^{n}$ where the right-hand side is in the
exponential-polynomial form. In particular, for all $i$, $p_{i}$ is not the
zero polynomial. Since $(u_{n})_{n\in\mathbb{N}}$ is non-degenerate, wlog we
can assume $\rho_{1}>\ldots>\rho_{m}>0$. If $p_{1}(n)$ is negative for
sufficiently large $n$, then the energy constraint is not satisfied.
Otherwise, we can compute $N$ such that for all $n>N$, $u_{n}>0$. It remains
to check whether $u_{n}\geq 0$ for $0\leq n\leq N$. Next, suppose $M$ has non-
real eigenvalues $\lambda,\overline{\lambda}$, and a real eigenvalue $\rho$.
Write $\gamma=\lambda/|\lambda|$ and $r=|\lambda|$. Then $u_{n}$ is of the
form

$u_{n}=cn+\sum_{i=1}^{m}c_{i}\Lambda_{i}^{n}\coloneqq cn+v_{n}$

where $\Lambda_{1},\ldots,\Lambda_{m}$ are pairwise distinct and in the
multiplicative group generated by $r,\rho,\delta,\gamma$. Wlog we can assume
$c_{i}\neq 0$ for all $i$, but $c$ may be zero. If $\gamma$ is a root of unity
of order $k>0$ (i.e. $\gamma^{k}=1$), then we can take subsequences
$(u^{(0)}_{n})_{n\in\mathbb{N}},\ldots,(u^{(k-1)}_{n})_{n\in\mathbb{N}}$,
where $u^{(j)}_{n}=u_{nk+j}$ for $n\in\mathbb{N}$ and $0\leq j<k$, and each
$(u^{(j)}_{n})_{n\in\mathbb{N}}$ has only real eigenvalues. We can then apply
the analysis above. Hereafter we assume $\gamma$ is not a root of unity.

Suppose $c=0$. Then 4.6 (c) applies and we can decide if $u_{n}$ is positive.
Next, suppose $c\neq 0$ and $L\coloneqq\max_{i}|\Lambda_{i}|\leq 1$. We can
compute $N_{2}$ such that $|cn|>|v_{n}|$ for all $n>N_{2}$. Hence in this case
$u_{n}\geq 0$ for all $n$ if and only if $c>0$ and $u_{n}>0$ for $0\leq n\leq
N_{2}$. Finally, suppose $c\neq 0$ and $L>1$. Applying 4.6 (b), there exists
effectively computable $N_{3}$ such that $|u_{n}|>|cn|$ for $n>N_{3}$. Hence
$u_{n}\geq 0$ for all $n$ if and only if $u_{n}\geq 0$ for $0\leq n\leq N_{3}$
and $\sum_{i=1}^{m}c_{i}\Lambda_{i}^{n}\geq 0$ for $n>N_{3}$. The latter can
be decided by applying 4.6 (c) to the sequence
$v_{n}=\sum_{i=1}^{m}c_{i}\Lambda_{i}^{N_{3}+n}=\sum_{i=1}^{m}(c_{i}\Lambda_{i}^{N_{3}})\Lambda_{i}^{n}$.
∎

###  4.3. Positivity and Diophantine hardness

Recall that the energy satisfaction problem is to decide, given a matrix
$M\in\mathbb{Q}^{d\times d}$, $q\in\mathbb{Q}^{d}$, $B\in\mathbb{Q}$, and a
polynomial $p$ with rational coefficients, whether there exists $n$ such that
$\sum_{k=0}^{n}p(M^{k}q)<B$. This problem is at least as hard as the
Positivity Problem already for stochastic LDSs and linear weight functions.

###### Theorem 4.8.

The Positivity Problem can be reduced to the energy satisfaction problem above
restricted to a Markov chain $(M,q)$ and a linear weight function $w$.

###### Proof.

It is known from (AkshayAOW15, ; mihir, ) that the Positivity Problem for
arbitrary LRS over $\mathbb{Q}$ can be reduced to the following problem: given
a Markov chain $(M,q)$, decide whether there exists $n$ such that
$e_{1}M^{n}q\geq 1/2$. We reduce the latter to the energy satisfaction
problem. Given a Markov chain $(M,q)\in\mathbb{Q}^{d\times d}\times d$, let

$P=\begin{bmatrix}M&\mathbf{0}\\\ \mathbf{0}&M\end{bmatrix}$

and $t=(1/2q,1/2Mq)\in\mathbb{Q}^{2d}$. Observe that $(P,t)$ is also a Markov
chain. Moreover, $P^{n}t=(1/2M^{n}q,1/2M^{n+1}q)$. We choose the weight
function $w(x_{1},\ldots,x_{2d})=2(x_{d+1}-x_{1})$ and $B=1/2-e_{1}\cdot q$.
Then $w(P^{n}q)=e_{1}M^{n+1}q-e_{1}M^{n}q$, and
$u_{n}\coloneqq\sum_{k=0}^{n}w(P^{n}q)\geq B$ if and only if
$e_{1}M^{n+1}q\geq 1/2$. Hence there does not exist $n$ such that
$e_{1}M^{n}q\geq 1/2$ if and only if $e_{1}\cdot q<1/2$ and there does not
exist $n$ such that $u_{n}<B$. ∎

The Positivity Problem for LRS of order 6 was shown in
(ouaknine13_posit_probl_low_order_linear_recur_sequen, ) to be _Diophantine-
hard_. Specifically, for $r\in\mathbb{Q}$ and $\lambda\in\mathbb{Q}(i)$ (that
is, $\lambda=a+bi$ where $a,b\in\mathbb{Q}$) let

$u^{\lambda,r}_{n}=-n+\frac{n}{2}(\lambda^{n}+\overline{\lambda^{n}})+\frac{ri}{2}(\overline{\lambda^{n}}-\lambda^{n})=r\operatorname{Im}(\lambda^{n})-n\operatorname{Re}(\lambda^{n})+n.$

If for all $r$ and $\lambda$ we can decide whether $u^{\lambda,r}_{n}\geq 0$
for all $n\geq 0$, then we could compute the _Lagrange constants_ of a large
class of numbers, which would amount to a major mathematical breakthrough in
number theory. The following theorem states that a solution to the energy
satisfaction problem for rational LDS in dimension 4 with polynomial weight
functions would also yield this breakthrough.

###### Theorem 4.9.

The energy satisfaction problem for rational LDSs in dimension 4 and
polynomial weight functions with rational coefficients is Diophantine-hard.

###### Proof.

We prove the following: If we can decide the energy satisfaction problem with
$d=4$, then we can decide for every $r,\lambda$ whether $u^{\lambda,r}_{n}\geq
0$ for all $n$. Fix $r\in\mathbb{Q}$ and $\lambda=a+bi\in\mathbb{Q}(i)$.
Define

$M=\begin{bmatrix}a&-b&1&0\\\ b&a&0&1\\\ 0&0&a&-b\\\ 0&0&b&a\end{bmatrix}$

and the initial point $q=(0,0,0,1)$. We have

$M^{n}q=[-n\operatorname{Im}(\lambda^{n-1})\>\>\>n\operatorname{Re}(\lambda^{n-1})\>\>\>-\operatorname{Im}(\lambda^{n})\>\>\>\operatorname{Re}(\lambda^{n})]^{\top}.$

Recall that for all $n\in\mathbb{N}$, (i)
$\operatorname{Re}(\lambda^{n+1})=a\operatorname{Re}(\lambda^{n})-b\operatorname{Im}(\lambda^{n})$
and (ii)
$\operatorname{Im}(\lambda^{n+1})=a\operatorname{Im}(\lambda^{n})+b\operatorname{Re}(\lambda^{n})$.
Hence there exist polynomials $p_{1},\ldots,p_{4}$ with rational coefficients
such that $p_{1}(M^{n}q)=n\operatorname{Im}(\lambda^{n})$,
$p_{2}(M^{n}q)=n\operatorname{Re}(\lambda^{n}),p_{3}(M^{n}q)=\operatorname{Re}(\lambda^{n})$
and $p_{4}(M^{n}q)=\operatorname{Im}(\lambda^{n})$ for all $n$. Next, consider

$w_{n}=u^{\lambda,r}_{n+1}-u^{\lambda,r}_{n}=r\operatorname{Im}(\lambda^{n+1})-n\operatorname{Re}(\lambda^{n+1})-r\operatorname{Im}(\lambda^{n})+n\operatorname{Re}(\lambda^{n})+1.$

Since $u^{\lambda,r}_{0}=0$, we have
$u^{\lambda,r}_{n+1}=\sum_{k=0}^{n}w_{n}$. Moreover, using facts (i), (ii) and
the polynomials $p_{1},\ldots,p_{4}$ we can construct a polynomial $p$ with
rational coefficients such that $w_{n}=p(M^{n}q)$ for all $n$. Hence
$u^{\lambda,r}_{n}\geq 0$ for all $n$ if and only if the weights
$(p(M^{n}q))_{n\in\mathbb{N}}$ satisfy the energy constraint with budget
$B=0$. ∎

##  5\. Conclusion

We have shown how to compute (or approximate) the mean-payoff and the total or
discounted weight of the orbit of rational LDSs for several combinations of
restricted classes of LDSs and classes of continuous weight functions (see
Table 1). Remarkably, these results concerning _infinite horizon_ questions do
not rely on restrictions of the dimension – in contrast to decidability
results for the Skolem (tijdeman_distan_between_terms_algeb_recur_sequen, ;
Verescchagin, ) and the Positivity
(ouaknine13_posit_probl_low_order_linear_recur_sequen, ; ouaknine_simple-
positivity, ) problems, which can be seen as special cases of reachability
questions about the orbit of an LDS.

For the question whether an orbit of a rational LDS with a polynomial weight
function satisfies an energy constraints, on the other hand, we have shown
decidability for dimension 3 by utilising results about LRSs based on Baker’s
theorem and Diophantine-hardness for dimension 4. Further, the restriction to
stochastic LDSs and linear weight functions turned out to be Positivity-hard.

Instead of continuous weight functions, also functions $w$ assigning a weight
to each semialgebraic set in a collection of semialgebraic sets
$S_{1},\ldots,S_{m}$ constitute an interesting class of weight functions.
Here, several interesting questions can be asked. E.g., given an LDS
$(M,q)\in\mathbb{Q}^{d\times d}\times\mathbb{Q}^{d}$ and $w$, compare the
(discounted) total reward/mean-payoff to a given threshold. Here at time $n$
the reward received is $\sum_{i=1}^{m}\mathbbm{1}(M^{n}q\in S_{i})w(S_{i})$.
This problem appears to be difficult with deep connections to Diophantine
approximation.

###### Acknowledgements.

Joël Ouaknine is also part of Keble College, Oxford as emmy.network Fellow.
The authors were supported by DFG grant 389792660 as part of TRR 248 (see
https://perspicuous-computing.science) and by Deutscher Akademischer
Austauschdienst, Projekt-ID: 57616814 (Konrad Zuse Schools of Excellence in
Artificial Intelligence 2022 - 2027).

## References

  * (1) Manindra Agrawal, S. Akshay, Blaise Genest, and P. S. Thiagarajan.  Approximate verification of the symbolic dynamics of markov chains.  J. ACM, 62(1):2:1–2:34, 2015.  doi:10.1145/2629417.
  * (2) S. Akshay, Timos Antonopoulos, Joël Ouaknine, and James Worrell.  Reachability problems for markov chains.  Inf. Process. Lett., 115(2):155–158, 2015.  doi:10.1016/j.ipl.2014.08.013.
  * (3) S. Akshay, Hugo Bazille, Blaise Genest, and Mihir Vahanwala.  On robustness for the skolem and positivity problems.  In Petra Berenbrink and Benjamin Monmege, editors, 39th International Symposium on Theoretical Aspects of Computer Science, STACS 2022, March 15-18, 2022, Marseille, France (Virtual Conference), volume 219 of LIPIcs, pages 5:1–5:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.  doi:10.4230/LIPIcs.STACS.2022.5.
  * (4) S. Almagor, T. Karimov, E. Kelmendi, J. Ouaknine, and J. Worrell.  Deciding $\omega$-regular properties on linear recurrence sequences.  Proc. ACM Program. Lang., 5(POPL), 2021.
  * (5) Eduardo Aranda-Bricaire, Ülle Kotta, and Claude H Moog.  Linearization of discrete-time systems.  SIAM Journal on Control and Optimization, 34(6):1999–2023, 1996.
  * (6) Christel Baier, Florian Funke, Simon Jantsch, Toghrul Karimov, Engel Lefaucheux, Florian Luca, Joël Ouaknine, David Purser, Markus A. Whiteland, and James Worrell.  The orbit problem for parametric linear dynamical systems.  In Serge Haddad and Daniele Varacca, editors, 32nd International Conference on Concurrency Theory, CONCUR 2021, August 24-27, 2021, Virtual Conference, volume 203 of LIPIcs, pages 28:1–28:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.  doi:10.4230/LIPIcs.CONCUR.2021.28.
  * (7) Christel Baier and Joost-Pieter Katoen.  Principles of Model Checking.  MIT Press, 2008.
  * (8) Mark Braverman.  Termination of integer linear programs.  In Proceedings of the 18th International Conference on Computer Aided Verification, CAV’06, page 372–385, Berlin, Heidelberg, 2006. Springer-Verlag.  doi:10.1007/11817963_34.
  * (9) Jin-Yi Cai.  Computing jordan normal forms exactly for commuting matrices in polynomial time.  International Journal of Foundations of Computer Science, 05(03n04):293–302, 1994.  arXiv:https://doi.org/10.1142/S0129054194000165, doi:10.1142/S0129054194000165.
  * (10) Philip J Davis and Philip Rabinowitz.  Methods of numerical integration.  Courier Corporation, 2007.
  * (11) Julian D’Costa, Toghrul Karimov, Rupak Majumdar, Joël Ouaknine, Mahmoud Salamati, and James Worrell.  The pseudo-reachability problem for diagonalisable linear dynamical systems.  In Stefan Szeider, Robert Ganian, and Alexandra Silva, editors, 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022, August 22-26, 2022, Vienna, Austria, volume 241 of LIPIcs, pages 40:1–40:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.  doi:10.4230/LIPIcs.MFCS.2022.40.
  * (12) Graham Everest, Alf van der Poorten, Igor Shparlinski, and Thomas Ward.  Recurrence Sequences.  2003\.  URL: http://dx.doi.org/10.1090/surv/104, doi:10.1090/surv/104.
  * (13) Toghrul Karimov, Edon Kelmendi, Joris Nieuwveld, Joël Ouaknine, and James Worrell.  The power of positivity.  To appear in the Proceedings of LICS23, 2023.
  * (14) Toghrul Karimov, Edon Kelmendi, Joël Ouaknine, and James Worrell.  What’s decidable about discrete linear dynamical systems?  In Jean-François Raskin, Krishnendu Chatterjee, Laurent Doyen, and Rupak Majumdar, editors, Principles of Systems Design - Essays Dedicated to Thomas A. Henzinger on the Occasion of His 60th Birthday, volume 13660 of Lecture Notes in Computer Science, pages 21–38. Springer, 2022.  doi:10.1007/978-3-031-22337-2\\_2.
  * (15) Toghrul Karimov, Engel Lefaucheux, Joël Ouaknine, David Purser, Anton Varonka, Markus A. Whiteland, and James Worrell.  What’s decidable about linear loops?  Proc. ACM Program. Lang., 6(POPL), 2022.
  * (16) Toghrul Karimov, Joel Ouaknine, and James Worrel.  On ltl model checking for low-dimensional discrete linear dynamical systems.  In 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020, LIPIcs 170, 2020.
  * (17) Manuel Kauers and Peter Paule.  The Concrete Tetrahedron.  Springer Vienna, 2011.  URL: https://doi.org/10.1007%2F978-3-7091-0445-3, doi:10.1007/978-3-7091-0445-3.
  * (18) Edon Kelmendi.  Computing the density of the positivity set for linear recurrence sequences.  In Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1–12, 2022.
  * (19) Vidyadhar G. Kulkarni.  Modeling and Analysis of Stochastic Systems.  Chapman & Hall, Ltd., 1995.
  * (20) Hong-Gi Lee, Ari Arapostathis, and Steven I Marcus.  Linearization of discrete-time systems.  International Journal of Control, 45(5):1803–1822, 1987.
  * (21) David W Masser.  Linear relations on algebraic groups.  New Advances in Transcendence Theory, pages 248–262, 1988.
  * (22) J. R. Norris.  Markov Chains.  Cambridge University Press, 2009.
  * (23) Joël Ouaknine and James Worrell.  Positivity problems for low-order linear recurrence sequences.  In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 12 2013.  doi:10.1137/1.9781611973402.27.
  * (24) Joël Ouaknine and James Worrell.  On the positivity problem for simple linear recurrence sequences,.  In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Automata, Languages, and Programming, pages 318–329, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg.
  * (25) R. Tijdeman, M. Mignotte, and T.N. Shorey.  The distance between terms of an algebraic recurrence sequence.  Journal für die reine und angewandte Mathematik (Crelles Journal), 1984(349):63–76, 1984.  doi:10.1515/crll.1984.349.63.
  * (26) Mihir Vahanwala.  Skolem and positivity completeness of ergodic markov chains.  CoRR, abs/2305.04881, 2023.  arXiv:2305.04881, doi:10.48550/arXiv.2305.04881.
  * (27) N. K. Vereshchagin.  The problem of appearance of a zero in a linear recurrence sequence (in Russian).  Mat. Zametki, 38(2), 1985.
  * (28) Hermann Weyl.  Über die gleichverteilung von zahlen mod. eins.  Mathematische Annalen, 77(3):313–352, 1916.
  * (29) G. Wüstholz and A. Baker.  Logarithmic forms and group varieties.  Journal für die reine und angewandte Mathematik, 442:19–62, 1993.  URL: http://eudml.org/doc/153550.

##  Appendix A Omitted proofs

#### Proof of 2.1

See 2.1

###### Proof.

Suppose $\deg(p_{k})\geq 1$ for some $1\leq k\leq m$. Consider the sequence
$v_{n}=u_{n+1}-\lambda_{k}u_{n}$. It will be of the form

$v_{n}=\sum_{i\in I}q_{i}(n)\lambda_{i}^{n}$

where $I\subseteq\\{1,\ldots,m\\}$ with $k\in I$, $\deg(q_{k})<\deg(p_{k})$,
and for all $i\in I$, $q_{i}$ is not identically zero with
$\deg(q_{i})\leq\deg(p_{i})$. Observe that if $(u_{n})_{n\in\mathbb{N}}$ is
identically zero, then so is $(v_{n})_{n\in\mathbb{N}}$. Moreover, if $v_{n}$
is non-zero, then either $u_{n}$ or $u_{n+1}$ is non-zero. Repeating the
process of constructing $v_{n}$ from $u_{n}$ at most
$\sum_{i=1}^{m}\deg(p_{i})$ times, we obtain

$w_{n}=\sum_{i=1}^{m}c_{i}\lambda_{i}^{n}$

that is identically zero if $u_{n}$ is identically zero, where each $c_{i}$ is
an algebraic number and
$c\coloneqq[c_{1}\>\cdots\>c_{m}]^{\top}\neq\mathbf{0}$.

It remains to argue that $w_{n}$ cannot be identically zero. Consider the
system of equations

$\sum_{i=1}^{m}x_{i}\lambda_{i}^{n}=0\quad\quad\textrm{for $0\leq n<m$}.$

We can write it as $Mx=\mathbf{0}$, where $x=[x_{1}\>\cdots\>x_{m}]^{\top}$
and $M$ is a Vandermonde matrix with $\det(M)=\prod_{i\neq
j}(\lambda_{i}-\lambda_{j})$. Since $\lambda_{1},\ldots,\lambda_{m}$ are
distinct by assumption, $M$ is invertible and $Mx=0$ if and only if
$x=\mathbf{0}$. Since $c\neq\mathbf{0}$, it follows that $w_{n}\neq 0$ for
some $0\leq n<m$. Hence there exists $n^{\prime}\leq
n+\sum_{i=1}^{m}\deg(p_{i})=n+(d-m)<d$ such that $u_{n^{\prime}}\neq 0$. ∎

#### Proof of 3.6

See 3.6

###### Proof.

First, assume there is an eigenvalue $\alpha$ on the diagonal of $J$ with
$|\alpha|>1$. Let $i$ be a coordinate at which a Jordan block containing
$\alpha$ ends. Then, $q_{i}\not=0$ and hence $(J^{k}q)_{i}=\alpha^{k}q_{i}$ is
not bounded. Next, assume there is a Jordan block of size $\ell>1$ with an
eigenvalue $\alpha$ with $|\alpha|=1$. W.l.o.g. assume that this is the first
Jordan block. Then, the first $\ell$ coordinates of $J^{k}q$ are given by
$J_{\alpha,\ell}^{k}\cdot\begin{bmatrix}q_{1}&\dots&q_{\ell}\end{bmatrix}^{\top}$
and we have $q_{\ell}\not=0$. We compute

$(J^{k}q)_{\ell-1}=\alpha^{k}\cdot q_{\ell-1}+k\cdot\alpha^{k-1}\cdot
q_{\ell},$

which diverges for $k\to\infty$.

For the other direction, observe that $J_{\alpha,\ell}^{k}$ tends to $0$ if
$|\alpha|<1$. Further, the powers of Jordan blocks of size $1$ with an
eigenvalue $\alpha$ with $|\alpha|=1$ are bounded as they simply contain
$\alpha^{k}$, which has modulus $1$. ∎

#### Proof of 4.6

See 4.6

###### Proof.

Define $\mathcal{D}=\\{i\colon|\Lambda_{i}|=L\\}$ and
$\mathcal{R}=\\{i\colon|\Lambda_{i}|<L\\}$. The terms $c_{i}\Lambda_{i}^{n}$
for $i\in\mathcal{D}$ are called _dominant_. We have

$u_{n}=\underbrace{\sum_{i\in\mathcal{D}}c_{i}\Lambda_{i}^{n}}_{v_{n}}+\underbrace{\sum_{i\in\mathcal{R}}c_{i}\Lambda_{i}^{n}}_{z_{n}}.$

We first investigate $|v_{n}|$ as $n\to\infty$. Recall that each $\Lambda_{i}$
is of the form $\gamma^{m_{0}}r_{1}^{m_{1}}\cdots r_{\ell}^{m_{\ell}}$, where
$m_{0},\ldots,m_{\ell}\in\mathbb{Z}$. That is, for all $i$,
$\Lambda_{i}=|\Lambda_{i}|\gamma^{k_{i}}$ for some $k_{i}\in\mathbb{Z}$. Hence
we can write

(2) $v_{n}=L^{n}\sum_{i=-K}^{K}b_{i}\gamma^{in}$

where each $b_{i}$ is equal to some $c_{j}$ and $b_{-K},b_{K}\neq 0$. The
values of $i$ range over $\\{-K,\ldots,K\\}$ because $v_{n}$ is real-valued
and hence the summands in Equation 2 appear in conjugate pairs. We have

$v_{n}=\gamma^{-Kn}L^{n}\sum_{i=0}^{2K}b_{-K+i}\gamma^{in}=\gamma^{-Kn}L^{n}\prod_{i=0}^{2K}(\gamma^{n}-\alpha_{i})$

where $\alpha_{0},\ldots,\alpha_{2K}\in\overline{\mathbb{Q}}$ are the zeros of
the polynomial $p(z)=\sum_{i=0}^{2K}b_{-K+i}z^{i}$. Since $\gamma$ is not a
root of unity, we can apply Theorem 4.5 to each factor
$(\gamma^{n}-\alpha_{i})$ to conclude that there exist effectively computable
$N_{1},C$ such that $|v_{n}|>L^{n}n^{-C}$ for al $n>N_{1}$. Since
$|\Lambda_{i}|<L$ for all $i\in\mathcal{R}$, there exists (effectively
computable) $N_{2}$ such that $|v_{n}|>|z_{n}|$ for $n>N_{2}$. We have proven
(a) and (b).

Since $u_{n}$ is real-valued, by 2.2 for each $1\leq i\leq m$ there exists
$1\leq j\leq m$ such that $c_{j}\Lambda_{j}=\overline{c_{i}\Lambda_{i}}$.
Hence both $v_{n}$ and $z_{n}$ are real-valued. By the analysis above
$\operatorname{sign}(u_{n})=\operatorname{sign}(v_{n})$ for $n>N_{2}$. Hence
to check if $u_{n}$ is positive we have to check whether $u_{n}\geq 0$ for
$0\leq n\leq N_{2}$ and $v_{n}\geq 0$ for $n>N_{2}$. We show how to do the
latter. Since $\gamma\in\mathbb{T}$ is not a root of unity,
$(\gamma^{n})_{n\in\mathbb{N}}$ is dense in $\mathbb{T}$. Define
$f(z)=z^{-K}p(z)$, noting that $v_{n}=f(\gamma^{n})$. Consider $Z\coloneqq
f(\mathbb{T})\subset\mathbb{R}$, which is compact and equal to the closure of
$\\{\gamma^{-Kn}p(\gamma^{n})\mid n\in\mathbb{N}\\}$. If $Z$ contains a
negative number, then by density of $(\gamma^{n})_{n\in\mathbb{N}}$ in
$\mathbb{T}$, $v_{n}$ is negative for infinitely many $n$. Hence $u_{n}<0$ for
infinitely many $n$. Otherwise, $v_{n}\geq 0$ for all $n$ and hence $u_{n}\geq
0$ for all $n>N_{2}$. This concludes the proof of (c). ∎