On the decision problems for linear recurrence sequences
Min Sha
In this paper, we show that for almost all linear recurrence sequences of algebraic numbers with integer coefficients (or rational coefficients), the Skolem Problem is decidable by only testing finitely many terms, whose amount is bounded explicitly by using the initial data. The same is also true for both the Positivity Problem and the Ultimate Positivity Problem of real linear recurrence sequences of algebraic numbers with integer coefficients (or rational coefficients).
1505.07147.tex
%------------------------------------------------------------------------------
% Beginning of journal.tex
%------------------------------------------------------------------------------
%
% AMS-LaTeX version 2 sample file for journals, based on amsart.cls.
%
%        ***     DO NOT USE THIS FILE AS A STARTER.      ***
%        ***  USE THE JOURNAL-SPECIFIC *.TEMPLATE FILE.  ***
%
% Replace amsart by the documentclass for the target journal, e.g., tran-l.
%
\documentclass[12pt]{amsart}
\usepackage{amssymb,latexsym}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage[colorlinks,linkcolor=blue,anchorcolor=blue,citecolor=blue]{hyperref}
\usepackage{algorithm}
\usepackage{enumerate}
\usepackage{algpseudocode}
\usepackage{verbatim}
\usepackage{graphicx}

\newcommand\C{{\mathbb C}}
\newcommand\F{{\mathbb F}}
\newcommand\Q{{\mathbb Q}}
\newcommand\R{{\mathbb R}}
\newcommand\Z{{\mathbb Z}}
\newcommand\K{{\mathbb K}}
\newcommand\A{{\mathbb A}}

\newcommand\GL{{\mathrm {GL}}}
\newcommand\SL{{\mathrm {SL}}}
\newcommand\Gal{{\mathrm {Gal}}}


\newcommand\CC{{\mathcal C}}
\newcommand\HH{{\mathcal H}}
\newcommand\OO{{\mathcal O}}
\newcommand\NN{{\mathcal{N}}}
\newcommand\D{{\mathcal D}}
\newcommand\p{\mathfrak{p}}

\newcommand\im{\mathrm{Im}}
\newcommand\ns{\mathrm{ns}}
\newcommand\re{\mathrm{Re}}
\newcommand\ord{\mathrm{ord}}
\newcommand\h{\mathrm{h}}
\newcommand\Arg{\mathrm{Arg}}


\newcommand\al{\alpha}
\newcommand\be{\beta}
\newcommand\ga{\gamma}
\newcommand\PP{{\bf P}}

\def\({\left(}
\def\){\right)}
\def\[{\left[}
\def\]{\right]}
\def\<{\langle}
\def\>{\rangle}
\def\mand{\qquad\mbox{and}\qquad}


\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}


\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\numberwithin{equation}{section}

%    Absolute value notation
\newcommand{\abs}[1]{\lvert#1\rvert}

%    Blank box placeholder for figures (to avoid requiring any
%    particular graphics capabilities for printing this document).
\newcommand{\blankbox}[2]{%
  \parbox{\columnwidth}{\centering
%    Set fboxsep to 0 so that the actual size of the box will match the
%    given measurements more closely.
    \setlength{\fboxsep}{0pt}%
    \fbox{\raisebox{0pt}[#2]{\hspace{#1}}}%
  }%
}

\begin{document}

\title[]{On the decision problems for linear recurrence sequences}

%    Information for first author
\author{Min Sha}
%    Address of record for the research reported here
\address{School of Mathematics and Statistics, University of New South Wales, Sydney, NSW 2052, Australia}
%    Current address
%\curraddr{Department of Mathematics and Statistics,
%Case Western Reserve University, Cleveland, Ohio 43403}
\email{shamin2010@gmail.com}
%    \thanks will become a 1st page footnote.
%\thanks{The first author was supported in part by NSF Grant \#000000.}

%    Information for second author

%    General info
\subjclass[2010]{11B37, 	11C08}

%\date{Januar1 1, 2001 and, in revised form, June 22, 2001.}

%\dedicatory{This paper is dedicated to our advisors.}

\keywords{Linear recurrence sequence, Skolem Problem, Positivity Problem, Ultimate Positivity Problem}

\begin{abstract}
In this paper, we show that for almost all linear recurrence sequences of algebraic numbers with integer coefficients (or rational coefficients), the Skolem Problem is decidable by only testing finitely many terms, whose amount is bounded explicitly by using the initial data. The same is also true for both the Positivity Problem and the Ultimate Positivity Problem of real linear recurrence sequences of algebraic numbers with integer coefficients (or rational coefficients).
\end{abstract}

\maketitle


%% The correct journal style for \specialsection is all uppercase; a known bug
%% in amsart.cls prevents this, so input must be uppercase until it is fixed.
%\specialsection*{This is a Special Section Head}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\footnote{Here is an example of a footnote. Notice that this footnote
%text is running on so that it can stand as an example of how a footnote
%with separate paragraphs should be written.
%\par
%And here is the beginning of the second paragraph.}%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Introduction}

\subsection{Background}

Linear recurrence sequences appear almost everywhere in mathematics and computer science, and they have been studied for a very long time; see \cite{EPSW} for a deep and extensive introduction.
In this paper, we focus on several decision problems relating to such sequences over the complex numbers $\C$.

Recall that a linear recurrence sequence of order $m\ge 1$ is a sequence $\{u_n\}_{n= 0}^{\infty}$ with elements in $\C$ satisfying a recurrence relation
\begin{equation}
\label{sequence}
u_{n+m}=a_1u_{n+m-1}+\cdots+a_mu_n \quad (n=0,1,2,\ldots),
\end{equation}
where $a_1,\dots,a_m\in \C$, $a_m\ne 0$ and $u_j \ne 0$ for at least one
 $j$ in the range $0 \le j \le m-1$, and the sequence $\{u_n\}$ does not satisfy a relation of type \eqref{sequence} of smaller length.

 Here, we call $a_1,\ldots,a_m$ the \textit{coefficients} of the sequence $\{u_n\}$, and the \textit{initial data} of $\{u_n\}$ are $a_1,\ldots,a_m,u_0,\ldots,u_{m-1}$. Moreover, the sequence $\{u_n\}$ is called a linear recurrence sequence of algebraic numbers (resp. integers, rational numbers, real numbers) if all its initial data are algebraic numbers (resp. integers, rational numbers, real numbers). 

 In the sequel, we abbreviate both `linear recurrence sequence' and `linear recurrence sequences' to `LRS'.

Several crucial properties of the LRS $\{u_n\}$ rely on its 
 characteristic polynomial, which is defined as 
\begin{equation}
\label{polynomial}
f(X)=X^m-a_1X^{m-1}-\cdots-a_m=\prod_{i=1}^{k}(X-\alpha_i)^{e_i}  \in \C[X]
\end{equation}
with distinct $\alpha_1,\alpha_2,\ldots,\alpha_k$ (which are called the  \textit{characteristic roots} of $\{u_n\}$) and $e_i>0$ for $1\le i \le k$. Then, $u_n$ can be expressed as
\begin{equation}
\label{expression}
u_n=\sum_{i=1}^{k}f_i(n)\alpha_i^n,
\end{equation}
where $f_i$ is some polynomial of degree $e_i-1$ ($i=1,2,\ldots,k$). We call the sequence $\{u_n\}$ \textit{simple} if $k=m$ (that is $e_1=\cdots=e_m=1$) and \textit{non-degenerate} if $\alpha_i/\alpha_j$ is not a root of unity for any $i\ne j$ with $1\le i,j\le k$. 
If $\{u_n\}$ is non-degenerate, then there are only finitely many integers $n$ such that $u_n=0$.

For the above LRS $\{u_n\}$, the three decision problems we study are the following:

\begin{enumerate}[\quad 1.]
\item \textit{The Skolem Problem} (SP): does $u_n=0$ for some $n$? \label{problem1}

\item \textit{The Positivity Problem} (PP): is $u_n>0$ for all $n$? \label{problem2}

\item \textit{The Ultimate Positivity Problem} (UPP): is $u_n> 0$ for all but finitely many $n$? \label{problem3}
\end{enumerate}
Actually, PP and UPP only make sense for real LRS. Note that SP is widely open in general case. 

The above three problems (and related variants) have applications in various areas, such as theoretical biology, software verification, probabilistic
model checking, quantum
computing, discrete linear dynamical systems,
as well as combinatorics, formal languages, etc;  see \cite{OW14a} for references. We refer the reader to \cite{OW12} for a survey on these problems.

There are only few results towards decidability of SP. For such sequences of order
1 and 2, this problem is relatively straightforward.
Decidability for LRS of algebraic numbers and of orders 3 and 4 is
independently settled positively by Mignotte, Shorey and Tijdeman \cite{MST}, as well as Vereshchagin \cite{Ver}, while that of order not less than 5 is not known. Decidability of SP is
also listed as an open problem and discussed by Tao \cite[Section 1.9]{Tao}; see also \cite{HHHK} for a survey. To taste the difficulty of the problem, we want to point out that Blondel and Portier \cite[Corollary 2.1]{BP} showed that it is NP-hard to decide whether a given integer LRS has a zero. However, it is known that determining whether a given integer LRS has infinitely many zeros is decidable \cite{BM}.

Most recently, Ouaknine and Worrell have made breakthroughs on PP and UPP. They have showed that UPP for integer LRS of order 5 or less is decidable in polynomial time \cite{OW14a}, and PP for
simple integer LRS of order 9 or less is decidable \cite{OW14b}. Moreover, UPP has been shown to be decidable for simple LRS of rational numbers and of all orders \cite{OW14c} in a non-constructive sense; that is, a given LRS of rational numbers can be certified ultimately positive, but no index threshold is provided beyond which all terms of the sequence are positive. Furthermore, it has been proved that it is NP-hard to decide whether a given integer LRS is non-negative; see \cite[Theorem 1]{BDJB}.



\subsection{Our results}

In this paper, we show that the above three problems can be decidable for almost all LRS of algebraic numbers with integer coefficients by testing finitely many initial terms, whose number can be bounded explicitly by a function which is poly-exponential in the initial data. The same is also true for those with rational coefficients; see Theorem \ref{thm:almost}. We also give estimates in some sense on the number of such LRS for which SP might be not decidable explicitly; see Section \ref{sec:except}.




\section{Preliminaries}

In this section, we gather some definitions and results which are used later on.



\subsection{Basic definitions}
\label{sec:basic}

Given a polynomial
$$
f(X)=a_0X^m+a_1X^{m-1}+\cdots+a_m=a_0 (X-\al_1)\cdots (X-\al_m) \in \C[X]
$$
of degree $m\ge 1$, we assume that the roots $\al_1,\dots,\al_m$
(listed with multiplicities)
are labelled so that $|\al_1 | \ge |\al_2| \ge \cdots \ge |\al_m |$. In case $|\al_1|=\cdots =|\al_k |>|\al_{k+1} |$, we say that \textit{$f$ has exactly $k$ roots with maximal modulus}. 

In order to interpret the meaning of ``almost all'' in the results, we introduce the following definition.

\begin{definition}
Given a proposition $\PP$ related to integer polynomials, for integers $m\ge 1$ and $H\ge 1$, we define the sets
\begin{equation*}
\begin{split}
S_m(H) =  \{f(X) = &X^m +a_1X^{m-1} + \cdots + a_m\in \Z[X]~:\\
&  |a_i| \le H, \ i =1, \ldots, m\}
\end{split}
\end{equation*}
and 
\begin{equation*}
\begin{split}
S_m^*(H) =  \{f(X) = &a_0X^m +a_1X^{m-1} + \cdots + a_m\in \Z[X]~:\\
&  a_0\ne 0, |a_i| \le H, \ i =0,1, \ldots, m\}.
\end{split}
\end{equation*}
We say that {\bf P} is true for \emph{almost all} monic integer polynomials
if for any integer $m\ge 1$ the following limit holds:
$$
\lim_{H\to \infty} \frac{|\{f\in S_m(H): \textrm{{\bf P} is true for $f$}\}|}{|S_m(H)|}=1.
$$
Similarly, {\bf P} holds for \emph{almost all} integer polynomials
if for any integer $m\ge 1$ the following limit holds:
$$
\lim_{H\to \infty} \frac{|\{f\in S_m^*(H): \textrm{{\bf P} is true for $f$}\}|}{|S_m^*(H)|}=1.
$$
\end{definition}

Since the behaviour of a LRS depends heavily on its characteristic polynomial, if a certain property is true for almost all monic integer polynomials (resp. integer polynomials), then we say that the corresponding property is true for \textit{almost all} relevant LRS with integer  coefficients (resp. rational coefficients). Note that every LRS with rational coefficients uniquely corresponds to an integer polynomial of content 1. 

\begin{definition}
For a polynomial $f(X)\in \C[X]$ of degree greater than 0, it is called \emph{dominant} if
it has a simple root whose modulus is strictly greater than the moduli of its remaining roots.
If $f(X)$ is dominant, the root with maximal modulus is called the \emph{dominant root} of $f(X)$. 
The polynomial $f(X)$ is called {\em non-degenerate} if
the quotient of its any two distinct roots is not a root of unity.
\end{definition}

The following are two results concerning non-degenerate or dominant  integer polynomials: the first result comes from \cite[Theorem 1.1]{DS1} and \cite[Theorem 1.1]{DS2}, and the second one is from \cite[Theorem 1.4]{DS1} and \cite[Theorem 1.1]{DS3}.

\begin{lemma}
\label{lem:monic}
Almost all monic integer polynomials are non-degenerate and dominant.
\end{lemma}

\begin{lemma}
\label{lem:poly}
Almost all integer polynomials are non-degenerate and either have a dominant root, or have exactly two roots with maximal modulus (counted with multiplicity).
\end{lemma}

Furthermore, several algorithms given in \cite{DS2} test whether a given integer polynomial is dominant or not, and they can be easily amended to test whether a given integer polynomial has exactly two roots with maximal modulus.


\subsection{Previous results}

For SP, Mignotte, Shorey and Tijdeman have proved the following general result; see \cite[Corollary 1]{MST}.

\begin{lemma}
\label{lem:MST}
Let $\{u_n\}$ be a LRS of algebraic numbers defined by \eqref{sequence}.
For its characteristic roots in \eqref{polynomial}, without loss of generality suppose that $|\al_1|\ge |\al_2|\ge \cdots \ge |\al_k|$.
Define an integer $r$ by
$$
|\al_1|=|\al_2|=\cdots=|\al_r|> |\al_{r+1}|.
$$
If either $r=1$, or $2\le r \le 3$ and at least one of the numbers $\al_i/\al_j$ with $1\le i < j \le r$ is not a root of unity, then SP is decidable for $\{u_n\}$.
\end{lemma}

Combining Lemma \ref{lem:MST} with Lemma \ref{lem:monic}, it is easy to see that for almost all LRS of algebraic numbers with integer coefficients  , SP is decidable; from Lemma \ref{lem:poly}, the same is also true for those with rational coefficients. Now, the remaining problem is to estimate the computational complexity. That is, the goal is to obtain a lower bound for the index $n$ beyond which every term $u_n$ is non-zero.

The following result is a weak form of \cite[Theorem 2]{Bell}; see also \cite[Theorem 1]{Burke} and \cite[Theorem 1.3]{Gerhold} for the previous results.

\begin{lemma}
\label{lem:Bell}
Let $\{u_n\}$ be a real LRS defined by \eqref{sequence}, and let $f(X)$ be its characteristic polynomial. If $f$ does not have a positive root with maximal modulus, then there are infinitely many integers $n$ such that $u_n>0$ and also infinitely many integers $n$ such that $u_n<0$.
\end{lemma}

Lemma \ref{lem:Bell} tells us that for PP and UPP, we only need to consider those LRS having a positive characteristic root with maximal modulus.



\subsection{Mahler measure and Weil height}

Given a polynomial $f(x)=a_0x^m+\cdots+a_m=a_0 (x-\al_1)\cdots (x-\al_m) \in \C[x]$ of degree $m\ge 1$, its \textit{length} is defined by 
$$
L(f)=|a_0|+\cdots+ |a_m|,
$$
 its {\it height} by 
 $$
 H(f)=\max_{0 \leq i \leq m} |a_i|,
 $$
and its {\it Mahler measure} by
$$
M(f)=|a_0| \prod_{i=1}^{m} \max\{1,|\al_i|\}.
$$
For each $f \in \C[x]$ of degree $m\ge 1$, these quantities are related by the following inequality
\begin{equation}
\label{Mahler}
H(f) 2^{-m} \leq M(f) \leq H(f) \sqrt{m+1}, 
\end{equation}
for instance, see \cite[(3.12)]{Waldschmidt}. 
We also need the so-called Landau's inequality
\begin{equation}
\label{Landau}
M(f) \leq \(\sum_{i=0}^m |a_i|^2 \)^{1/2},
\end{equation}
 which was proved, for instance, in~\cite{MG}.

Accordingly, for an algebraic number $\al$, its \emph{Mahler measure} $M(\al)$ is defined as the Mahler measure of its minimal polynomial $f$ over the integers $\Z$, that is, $M(\al)=M(f)$.

For a number field $K$, we denote by $M_{K}$ the set of all valuations $v$ of $K$ extending the standard infinite and
$p$-adic valuations of the rational numbers $\Q$: $|2|_{v}=2$ if $v\in M_{K}$ is Archimedean, and $|p|_{v}=p^{-1}$ if $v$ extends the $p$-adic valuation of $\Q$. In particular, if the valuation $v$ of $K$ corresponds to a prime ideal $\p$ of $K$ lying above a prime number $p$, we also denote the valuation $|\,\,|_v$ by $|\,\,|_\p$, then for any $\al \in K$ we have
$$
|\al|_\p = p^{-\ord_\p(\al)/e_{\p}},
$$
where $\ord_\p(\al)$ is the exponent of $\p$ appearing in the prime decomposition of the fractional ideal $\al \OO_K$, $\OO_K$ is the ring of integers of $K$,  and $e_\p$ is the ramification index of $\p$ over $p$.
For any $v\in M_{K}$, let $K_{v}$ be the completion of $K$ with respect to the valuation $v$, and
let $d_{v}=[K_{v}:\Q_{v}]$ be the local degree of $v$. When the valuation $v$ corresponds to a prime ideal $\p$ lying above a prime number $p$, we also denote $K_v$ by $K_\p$ and $\Q_v$ by $\Q_p$, respectively. 

For the above number field $K$, the \emph{(Weil) absolute logarithmic height} of any non-zero $\alpha\in K$ is
defined by
\begin{equation}
\label{Weil}
\h(\alpha)=d^{-1}\sum_{v\in M_{K}}d_{v}\log\max\{|\alpha|_{v},1\}.
\end{equation}
 Actually, we have
\begin{equation}
\label{Mahler-Weil}
 \h(\al)= d^{-1} \log M(\al),
\end{equation}
see \cite[Lemma 3.10]{Waldschmidt} for a proof. 

Given non-zero $\al \in K$, in view of \eqref{Weil} and $\h(\al)=\h(\al^{-1})$, for any valuation $v\in M_K$ we have 
\begin{equation}
\label{Liouville}
| \log |\al |_v | \le d\h(\al)/d_v \le d\h(\al).
\end{equation}

In the sequel, we  use the following formulas without special reference (see, e.g., \cite{Waldschmidt}). For any $n\in \mathbb{Z}$ and $\be_{1},\cdots,\be_{k},\gamma\in \overline{\mathbb{Q}}$, we have
\begin{align*}
&\h(\be_{1}+\cdots+\be_{k})\le \h(\be_{1})+\cdots+\h(\be_{k})+\log k,\\
&\h(\be_{1}\cdots \be_{k})\le \h(\be_{1})+\cdots+\h(\be_{k}),\\
&\h(\gamma^{n})=|n|\h(\gamma),\\
&\h(|\ga|) \le \h(\ga), \\
& \h(\zeta)=0 \textrm{\quad for any root of unity $\zeta\in \overline{\Q}$}.
\end{align*}
Here, $\overline{\Q}$ stands for the algebraic closure of $\Q$.

We also need the following result, which is exactly~\cite[Lemma 3.7]{Waldschmidt}.

\begin{lemma}
\label{antra}
Let $f \in \Z[x_1,\ldots,x_n]$ be a non-zero polynomial in $n$ variables.  Then, for any algebraic numbers $\ga_1,\ldots,\ga_n$, we have
$$
\h(f(\ga_1,\ldots,\ga_n)) \leq \log L(f)+\sum_{i=1}^n \h(\ga_i) \deg_{x_i} f,
$$
where $\deg_{x_i} f$ is the partial degree of $f$ related to $x_i$.
\end{lemma}




 \subsection{Separating the moduli of roots}

The following lemma is a classical result due to Cauchy; see  \cite[Corollary 8.3.2]{Mishra}.

\begin{lemma}
\label{Cauchy}
Let $f(X) \in \C[X]$ be a polynomial of degree $m \ge 1$ defined by
$$
f(X)=a_0X^m+a_1X^{m-1}+\cdots+a_m,
$$
where $a_0\ne 0$ and $(a_1,\dots,a_m)\ne (0,\dots,0)$.
Then, for an arbitrary non-zero root $x$ of $f$, we have
\begin{equation}
\frac{\min_{0\le i \le m}|a_i|}{H(f)+\min_{0\le i \le m}|a_i|}<|x|<1+\frac{1}{|a_0|}\max\{|a_1|,\ldots,|a_{m}|\}.
\notag
\end{equation}
\end{lemma}

We reproduce \cite[Lemma 2.4 and Lemma 2.5]{DS2} as follows.

\begin{lemma}
\label{quadratic}
Let $f(X)\in\Z[X]$ be a quadratic polynomial. Suppose that $f$ has two real roots $\al$ and $\be$ with $|\al| \ne |\be|$. Then, we have
$$
||\al|-|\be|| \ge H(f)^{-1}.
$$
\end{lemma}

\begin{lemma}
Let $f(X)\in\Z[X]$ be a polynomial of degree $m\ge 2$, and let $\alpha$ and $\beta$ be two roots of $f$ satisfying $|\alpha| \ne |\beta|$. Then,
\begin{equation}
\label{distance1}
\left||\alpha|-|\beta|\right|>
2^{m(m-1)/4}(m+1)^{-m^3/4+3m/4-3}H(f)^{-m^3/2+m^2+m/2-2}
\end{equation}
if both $\al$ and $\be$ are non-real.
If, furthermore, $\al$ is real and $\be$ is non-real, then
\begin{equation}
\label{distance2}
\left||\alpha|-|\beta|\right| \ge 2^{-m(m-1)(m-2)/2} (m+1)^{-m(m-1)-1/2}H(f)^{-2m(m-1)-1}.
\end{equation}
Finally, if both $\al$ and $\be$ are real, then
\begin{equation}
\label{distance3}
||\alpha|-|\beta||>(2m+1)^{-3m}H(f)^{2-4m}.
\end{equation}
\end{lemma}

Note that for large enough $m$, \eqref{distance3} is better than \eqref{distance2}, and \eqref{distance2} is better than \eqref{distance1}. However, for small integer $m$, this might be not true. 
 For simplicity, we put them together into two uniform forms.

\begin{lemma}
Let $f(X)\in\Z[X]$ be a polynomial of degree $m\ge 3$, and let $\alpha$ and $\beta$ be two roots of $f$ satisfying $|\alpha| \ne |\beta|$. Then,
\begin{equation}
\label{udis1}
\left||\alpha|-|\beta|\right|>
2^{-m(m-1)(m-2)}(m+1)^{-m^3/4+3m/4-6}H(f)^{-m^3+m^2+m/2-2};
\end{equation}
if furthermore $\al$ is real, then
\begin{equation}
\label{udis2}
\left||\alpha|-|\beta|\right| > 2^{-m(m-1)(m-2)/2} (m+1)^{-m(m-1)-6}H(f)^{-2m(m-1)-1}.
\end{equation}
\end{lemma}

\begin{proof}
Note that \eqref{distance1} is automatically contained in \eqref{udis1}.
Since for $m\ge 4$, 
$$
-m^3/4+3m/4-6 \le -m^2 + 3m/4 - 6 < -m^2 + m -1/2, 
$$
and for $m\ge 3$, 
$$
-m^3+m^2+m/2-2 \le -2m^2 +m/2 -2 < -2m^2+2m-1,
$$
we can see that \eqref{distance2} is implied in \eqref{udis1} by considering $m=3$ individually. In addition, noticing
$$
2^{-m(m-1)(m-2)}(m+1)^{-m^3/4+3m/4-6} < 2^{-3m} (m+1)^{-3m} < (2m+1)^{-3m}
$$
for $m\ge 4$, we know that \eqref{distance3} is included in \eqref{udis1}.

The inequality \eqref{udis2} can be proved similarly by merging \eqref{distance2} and \eqref{distance3}.
\end{proof}




\subsection{Bounding the coefficients}

For further deductions, we need to estimate the coefficients in \eqref{expression}
when the sequence $\{u_n\}$ is a simple LRS of algebraic numbers.

\begin{lemma}
\label{lem:bj}
Let $\{u_n\}$ be a simple LRS of algebraic numbers of order $m \ge 2$  defined by \eqref{sequence}, and let $f(X)$ be its characteristic polynomial.
Write $u_n$ as
$$
u_n=\sum_{j=1}^{m}b_j\al_j^n,
$$
where $\al_1,\ldots,\al_m$ are distinct roots of $f$ and all $b_j$ are non-zero. Then, for any $1\le j \le m$ we have
$$
\h(b_j) <  \sum_{i=0}^{m-1}\h(u_{i})+2m\sum_{k \ne j}\h(\al_k)+m^2\h(\al_j)+\frac{3}{2}m^2-\frac{1}{2}m-1;
$$
furthermore if $f\in \Q[X]$, let $\delta$ be the smallest positive integer such that $\delta f(X)\in \Z[X]$, denote $\delta f(X)$ by $f^*(X)$ and write
$$
f^*(X)=\sum_{i=0}^{m}a_i^*X^{m-i} \in \Z[X],
$$
then we have
\begin{equation}
\label{eq:bj1}
\h(b_j) <  \sum_{i=0}^{m-1}\h(u_{i})+\frac{3}{2}m^2\log \( \sum_{i=0}^{m} |a_i^*|^2 \)+\frac{3}{2}m^2-\frac{1}{2}m-1.
\end{equation}
Finally, if $f\in \Q[X]$ is irreducible, we have
\begin{equation}
\label{eq:bj2}
\h(b_j) <  \sum_{i=0}^{m-1}\h(u_{i})+\frac{3}{2}m\log \( \sum_{i=0}^{m} |a_i^*|^2 \)+\frac{3}{2}m^2-\frac{1}{2}m-1.
\end{equation}
\end{lemma}

\begin{proof}
Here, we follow the arguments in the proof of \cite[Theorem 3.1]{DSS}.

Notice that
\begin{equation}
\label{eq:matrix}
(u_0,u_1, \ldots, u_{m-1})
=
(b_1,b_2, \ldots, b_m)
\left( \begin{array}{cccc}
1 & \al_1 & \ldots & \al_1^{m-1} \\
1 & \al_2 & \ldots & \al_2^{m-1} \\
\vdots & \vdots & \ldots & \vdots\\
1 & \al_m & \ldots & \al_m^{m-1} \\
\end{array} \right),
\end{equation}
and $\al_1, \ldots, \al_m$ are distinct.
To solve the above system of $m$ linear equations in $m$ unknowns $b_1,\ldots,b_m$, we denote the appearing Vandermonde matrix by
$V=\left(\al_i^{j-1}\right)_{1 \leq i,j \leq m}$. By~\cite[Formula (6)]{Klinger1967}, the inverse of $V$ is given by $V^{-1}=\(w_{ij}\)_{1\le i,j \le m}$, where
$$
w_{ij}=
 \frac{(-1)^{i+j} \sigma_{m-i}(\al_1,\ldots,\widehat{\al_{j}},\ldots,\al_m)}{\prod\limits_{n=1}^{j-1}(\al_{j}-\al_n)\prod\limits_{k=j+1}^{m}(\al_{k}-\al_{j})}
$$
 and $\sigma_{k}(\al_1,\ldots,\widehat{\al_{j}},\ldots,\al_m)$ stands for the $k$-th elementary symmetric function in the $m-1$ variables
$\al_1,\ldots,\al_m$ without $\al_{j}$; for instance, in the case $j=m$, we have
$\sigma_{1}(\al_1,\ldots,\al_{m-1})=\al_1+\cdots+\al_{m-1}$ and $\sigma_{m-1}(\al_1,\ldots,\al_{m-1})=\al_1\cdots \al_{m-1}$.

So, for any $j$ with $1\le j \le m$ we have
\begin{equation}\label{uyt}
 b_{j} = \sum_{i=1}^m u_{i-1} w_{ij}.
 \notag
\end{equation}
Since $\sigma_{m-i}(\al_1,\ldots,\widehat{\al_{j}},\ldots,\al_m)$
is a polynomial with coefficients $1$ in $m-1$ variables
 $\al_1,\ldots,\al_m$ (without $\al_{j}$) of degree $m-i$, length ${m-1 \choose m-i}$, and degree $1$ in each variable $\al_k$, $k \ne j$, by Lemma~\ref{antra} we find that
$$
\h(\sigma_{m-i}(\al_1,\ldots,\widehat{\al_{j}},\ldots,\al_m))
\leq \log {m-1 \choose m-i}+\sum_{k \ne j} \h(\al_k).
$$
On the other hand, we observe that
\begin{align*}
\h\(\prod_{k \ne j} (\al_k-\al_j)\) & \le \sum_{k \ne j} \h(\al_k-\al_j) \\
& \le  \sum_{k \ne j} \( \h(\al_k)+\h(\al_j)+\log 2 \) \\
& =   \sum_{k \ne j} \h(\al_k)+(m-1)\h(\al_j)+(m-1)\log 2.
\end{align*}
Thus, we obtain
$$
\h(w_{ij})\le 2\sum_{k \ne j} \h(\al_k)+(m-1)\h(\al_j)+ (m-1)\log 2 + \log {m-1 \choose m-i} .
$$

Hence,  for $1\le j \le m$ we conclude that
\begin{align*}
\h(b_j) & \le \sum_{i=1}^{m} (\h(u_{i-1})+\h(w_{ij}))+\log m\\
&\leq \sum_{i=0}^{m-1}\h(u_{i})+2m\sum_{k \ne j}\h(\al_k)+m(m-1)\h(\al_j) \\
& \qquad +2m(m-1)\log 2 + \log m \\
&< \sum_{i=0}^{m-1}\h(u_{i})+2m\sum_{k \ne j}\h(\al_k)+m^2\h(\al_j)+\frac{3}{2}m^2-\frac{1}{2}m-1,
\end{align*}
where we also use the fact that the binomial coefficient ${m-1 \choose m-i} \le 2^{m-1}$ for any $1\le i \le m$ and 
$$
2m(m-1)\log 2 + \log m \le \frac{3}{2}m^2-\frac{1}{2}m-1.
$$
This gives the first desired upper bound.

Now we assume that $f$ is a polynomial over $\Q$.
For any $1\le i \le m$, denote by $\deg \al_i$ the degree of $\al_i$ as an algebraic number, since
$$
\h(\al_i)=\frac{\log M(\al_i)}{\deg \al_i},
$$
we deduce that
$$
\h(\al_i)\le \log M(\al_i) \le \log M(f^*)
\le \frac{1}{2}\log \( \sum_{i=0}^{m} |a_i^*|^2 \),
$$
where the last inequality follows from Landau's inequality \eqref{Landau}.
Then, collecting relevant results yields the inequality \eqref{eq:bj1}.

Finally, the inequality \eqref{eq:bj2} comes from the fact that $\deg \al_i=m$ for any $1\le i \le m$ when $f$ is an irreducible polynomial over $\Q$.
\end{proof}

In fact, slightly better results can be achieved for such sequences of order 2.

\begin{lemma}
\label{lem:order2}
Let $\{u_n\}$ be a simple LRS of algebraic numbers defined by \eqref{sequence} of order $2$.
Let $f(X)$ and $f^*(X)$ be defined as in Lemma \ref{lem:bj}, and write $u_n$ as
$$
u_n=b_1\al_1^n + b_2\al_2^n,
$$
where $\al_1,\al_2$ are roots of $f$.
Then, we have
$$
\h(b_j) \le \h(u_0)+\h(u_1)+\frac{3}{2} \log (\sum_{i=0}^{2}|a_i^*|^2) + \frac{3}{2}
$$
for $j=1,2$.
\end{lemma}

\begin{proof}

Since for $n\ge 0$
$$
u_n=b_1\al_1^n + b_2 \al_2^n,
$$
 we derive 
$$
b_1 =\frac{u_1-u_0\al_2}{\al_1 - \al_2} \mand b_2 =\frac{u_0\al_1-u_1}{\al_1 - \al_2}.
$$
So, we obtain
\begin{align*}
\h(b_1) & \le \h(u_1-u_0\al_2)+\h(\al_1 - \al_2) \\
& \le \h(u_0)+\h(u_1)+\h(\al_1)+2\h(\al_2)+2\log 2 \\
& < \h(u_0)+\h(u_1)+\frac{3}{2} \log (\sum_{i=0}^{2}|a_i^*|^2) + \frac{3}{2}.
\end{align*}
Similarly, we have
$$
\h(b_2) < \h(u_0)+\h(u_1)+\frac{3}{2} \log (\sum_{i=0}^{2}|a_i^*|^2) + \frac{3}{2}.
$$
\end{proof}



\subsection{Linear form in the logarithms of algebraic numbers}

One key technical tool in this paper is Baker's inequality on linear form in the logarithms of algebraic numbers. Here we restate one of its explicit forms due to Matveev \cite[Corollary 2.3]{Matveev}.

First, recall that for a non-zero complex number $z$, the principal value of the natural logarithm of $z$ is
$$
\log z = \log |z| + \sqrt{-1} \cdot \Arg \, z,
$$
where $\Arg \, z$ is the principal value of the argument of $z$ ($-\pi < \Arg \, z \le \pi$). Note that the definition here coincides with the natural logarithm of positive real numbers.   We also want to indicate that the identity $\log (z_1z_2)=\log z_1 + \log z_2$ can fail in our settings. 

Let
$$
\Lambda = b_1 \log \al_1 + b_2 \log \al_2 + \cdots + b_k \log \al_k,
$$
where $k\ge 2$, $b_1,\ldots,b_k \in \Z$, and $\al_1,\ldots, \al_k$ are non-zero elements of a number field $K$. Let $D=[K:\Q]$ and $B=\max \{ |b_1|,\ldots, |b_k| \}$. For any $1 \le j \le k$,  choose real number $A_j$ such that
$$
A_j \ge \max \{ D\h(\al_j), |\log \al_j | \}.
$$

Suppose that $\Lambda \ne 0$. Then, we have
\begin{equation}
\label{Baker}
\log |\Lambda| > -2^{6k+20}D^2A_1\cdots A_k \log (eD) \log (eB),
\end{equation}
where $e$ is the base of the natural logarithm.




\section{Main results}

\subsection{Characteristic polynomials with dominant roots}
\label{sec:dominant}

We first want to get explicit versions of some results in Lemma \ref{lem:MST} in Section \ref{sec:dominant} and in Section \ref{sec:two}. 

\begin{theorem}
\label{thm:dom}
Let $\{u_n\}$ be a real simple LRS of algebraic numbers defined by \eqref{sequence} of order $m\ge 3$, and let $f(X)$ be its characteristic polynomial. Suppose that $f(X)$ is a polynomial over $\Q$ and has a dominant root, and denote by $d$ the degree of the number field generated by $u_0,\ldots,u_{m-1}$ over $\Q$.  Let $\delta$ be the smallest positive integer such that $\delta f(X)\in \Z[X]$. Denote $\delta f(X)$ by $f^*(X)$, and write
$$
f^*(X)=\sum_{i=0}^{m}a_i^*X^{m-i} \in \Z[X].
$$
Then, for the sequence $\{u_n\}$, SP, PP and UPP are all decidable by only testing the first $\lfloor N_1(u) \rfloor$ terms, where
$$
N_1(u)=2^{m(m-1)(m-2)/2} (m+1)^{m(m-1)+6}H(f^*)^{2m(m-1)+2} C_1(u)
$$
and
$$
C_1(u)=m!\cdot 4d \( \sum_{i=0}^{m-1}\h(u_{i})+\frac{3}{2}m^2\log ( \sum_{i=0}^{m} |a_i^*|^2 )+\frac{3}{2}m^2-\frac{1}{2}m \);
$$
if furthermore $f(X)$ is irreducible, then $C_1(u)$ can be replaced by
$$
C_2(u)=m! \cdot 4d \( \sum_{i=0}^{m-1}\h(u_{i})+\frac{3}{2}m\log ( \sum_{i=0}^{m} |a_i^*|^2 )+\frac{3}{2}m^2-\frac{1}{2}m \).
$$
Finally, if $f(X)$ is an irreducible polynomial over $\Q$ having only real roots, then we can choose
$$
N_1(u)= (2m+1)^{3m}H(f^*)^{4m-1}C_2(u).
$$
\end{theorem}

\begin{proof}
Let $\al_1,\al_2,\ldots,\al_m$ be the roots of $f^*$  such that $|\al_1|>|\al_j|$ for any $2\le j \le m$. Note that they are all distinct and also the roots of $f$. We also note that $\al_1$ is a real number.

 Denote
$$
r(u)=2^{-m(m-1)(m-2)/2} (m+1)^{-m(m-1)-6}H(f^*)^{-2m(m-1)-1}.
$$
Then, by \eqref{udis2} for any $2\le j \le m$ we have
\begin{equation}
\label{eq:diff1}
|\al_1|-|\al_j| > r(u).
\end{equation}

As mentioned before, for any integer $n\ge 0$, $u_n$ can be expressed as
$$
u_n=\sum_{j=1}^{m}b_j\alpha_j^n,
$$
where $b_1,\ldots,b_m$ are all non-zero complex numbers.
Under the assumptions, we know 
$$
\lim_{n\to \infty} \frac{u_n}{\al_1^n}=b_1.
$$
Since the sequence $\{u_n/\al_1^n\}$ is a real sequence,   $b_1$ must be a real number.

Now, we want to find a lower bound for $n$ such that
\begin{equation}
\label{eq:b1a}
|b_1\al_1^n|> \sum_{j=2}^{m}|b_j\alpha_j^n|.
\end{equation}
So, the sign of $u_n$ is the same as that of $b_1\al_1^n$ when the index $n$ is greater than this lower bound. Then, everything is done. Note that  
it is equivalent to require that
$$
|b_1|> \sum_{j=2}^{m}|b_j|\left(|\alpha_j|/|\al_1|\right)^n,
$$
which, by \eqref{eq:diff1}, follows from the inequality
\begin{equation}
\label{eq:b1}
|b_1|> \sum_{j=2}^{m}|b_j|\left(1-r(u)/|\al_1|\right)^n.
\end{equation}

On the other hand, for any $1\le j \le m$, by \eqref{Liouville} we know that
$$
| \log |b_j | |\le [\Q(b_j):\Q]\h(b_j).
$$
Since $b_j \in \Q(u_0,\ldots,u_{m-1},\al_1,\ldots,\al_m)$ by \eqref{eq:matrix} and $[\Q(\al_1,\ldots,\al_m):\Q]\le m!$ ($m!$ is the factorial of $m$), we have $[\Q(b_j):\Q]\le m! \cdot d$. So
$$
| \log |b_j | |\le m!\cdot d \h(b_j).
$$
Using \eqref{eq:bj1}, we get
$$
| \log |b_j | |\le B(u),
$$
that is
\begin{equation}
\label{eq:|bj|}
\exp(-B(u))\le |b_j| \le \exp(B(u))
\end{equation}
for any $1\le j \le m$, where
\begin{equation}
\label{eq:Bu}
B(u)=m! \cdot d \( \sum_{i=0}^{m-1}\h(u_{i})+\frac{3}{2}m^2\log ( \sum_{i=0}^{m} |a_i^*|^2 )+\frac{3}{2}m^2-\frac{1}{2}m-1 \).
\end{equation}

Thus, the inequality \eqref{eq:b1} is implied in the following inequality
$$
\exp(-B(u)) > m \exp(B(u)) \left(1-r(u)/|\al_1|\right)^n,
$$
which is equivalent to
$$
n > \frac{2B(u)+ \log m}{ -\log (1-r(u)/|\al_1|)}.
$$
By Lemma \ref{Cauchy}, it suffices to ensure that
$$
n > \frac{2B(u)+ \log m}{ -\log (1-r(u)/(1+H(f^*)))}.
$$
Using the Taylor expansion $-\log (1-z)=z+z^2/2+z^3/3+ \cdots$ for $|z|<1$, it suffices to require that
\begin{equation}
\label{eq:final1}
n > \frac{2B(u)+ \log m}{ r(u)/(1+H(f^*))}.
\end{equation} 
Thus, we get the following lower bound implying the inequality \eqref{eq:b1a}
\begin{equation}
\label{eq:lower1}
n> 2^{m(m-1)(m-2)/2} (m+1)^{m(m-1)+6}H(f^*)^{2m(m-1)+2} C_1(u).
\end{equation}

 So, if integer $n$ satisfies the
inequality \eqref{eq:lower1}, then the sign of $u_n$ is the same as that of $b_1\al_1^n$, especially $u_n\ne 0$. This completes the proof of the first desired result.

When $f$ is an irreducible polynomial over $\Q$, one can prove the remaining desired results by applying the same arguments and using  \eqref{distance3} and \eqref{eq:bj2}.
\end{proof}

From the above proof it is easy to see that only with respect to SP, Theorem \ref{thm:dom} is also true for non-real simple LRS of algebraic numbers. This also holds for Theorems \ref{thm:nondom} and \ref{thm:order2}.



\subsection{Characteristic polynomials with exactly two roots of maximal modulus}
\label{sec:two}

The case when the sequence $\{u_n\}$ has exactly two characteristic roots with maximal modulus is quite different from the above case and is more complicated.

\begin{theorem}
\label{thm:nondom}
Let $\{u_n\},f(X),f^*(X),d$ be defined as in Theorem \ref{thm:dom}. Suppose that $f$ has exactly two roots, say $\al_1$ and $\al_2$, with maximal modulus such that $\al_1/\al_2$ is not a root of unity.
 Then, for the sequence $\{u_n\}$, SP is decidable by only testing the first $\lfloor N_2(u) \rfloor$ terms, where
$$
N_2(u)=2C_3(u) \log C_3(u)
$$
and
\begin{align*}
& C_3(u) =F(m,d) H(f^*)^{m^3-m^2-m/2+3.5} C_1(u), \\
& F(m,d) =2^{m(m-1)(m-2)+42}\pi (m!\cdot d)^{3.5} (m+1)^{m^3/4-3m/4+6.5};
\end{align*}
if furthermore $f(X)$ is irreducible, then $C_1(u)$ can be replaced by
$C_2(u)$. Here, $C_1(u)$ and $C_2(u)$ have been defined in Theorem \ref{thm:dom}. 
\end{theorem}

\begin{proof}
Under the assumptions, we write $f(X)$ as
$$
f(X)=(X-\al_1)(X-\al_2)\cdots (X-\al_m) \in \Q[X]
$$
such that $\al_1,\al_2,\ldots,\al_m$ are all distinct and $|\al_1|=|\al_2|>|\al_j|$ for any $3\le j \le m$. 
By \eqref{udis1}, for any $3\le j \le m$ we have
$$
|\al_1|-|\al_j| > s(u),
$$
where
$$
s(u)=2^{-m(m-1)(m-2)}(m+1)^{-m^3/4+3m/4-6}H(f^*)^{-m^3+m^2+m/2-2}.
$$

Note that for any integer $n\ge 0$, $u_n$ can be expressed as
$$
u_n=\sum_{j=1}^{m}b_j\alpha_j^n,
$$
where $b_1,\ldots,b_m$ are all non-zero complex numbers. 

In the sequel, we want to find a lower bound for $n$ such that
\begin{equation}
\label{eq:b12a}
|b_1\al_1^n+b_2\al_2^n|> \sum_{j=2}^{m}|b_j\alpha_j^n|.
\end{equation}
So, whenever the index $n$ is greater than this lower bound, we have $u_n \ne 0$. This can complete the proof. 

The key step is to get a lower bound for the left-hand side of \eqref{eq:b12a} by using Baker's inequality on linear form \eqref{Baker}. 
Then, let the right-hand side of \eqref{eq:b12a} be less than the lower bound, this can give the desired lower bound for the index $n$. 

For $n\ge 0$, we have
\begin{equation}
\label{eq:initial}
|b_1\al_1^n+b_2\al_2^n|
=|b_1\al_1^n| \cdot \left|(-1)\cdot \frac{b_2}{b_1}\cdot (\frac{\al_2}{\al_1})^n-1 \right| 
\end{equation}
Here, for $n\ge 0$ we put
$$
\Delta_n = (-1)\cdot \frac{b_2}{b_1}\cdot (\frac{\al_2}{\al_1})^n-1,
$$
and 
\begin{equation}
\label{eq:LaDe}
\Lambda_n = \log (\Delta_n +1). 
\end{equation}
Then, by definition, there exists an odd integer $a$ such that $|a| \le n+1 $ and 
$$
\Lambda_n = a \log (-1) + \log (b_2/b_1) + n \log (\al_2/\al_1), 
$$
which gives a linear form in the logarithms of algebraic numbers. 
We need to handle the exceptional case when $\Lambda_n = 0$.  

In the following, we assume that 
\begin{equation}
\label{eq:1/2}
|\Delta_n| \le 1/2.
\end{equation}
If this is not true, then later on one can see that this implies much better results; see \eqref{eq:tran} and \eqref{eq:Lam1}.

Notice that for any complex number $z$ with $0<|z| \le r <1$, using the Taylor expansion, we have 
\begin{align*}
|\log (1+z)| & = |z-\frac{z^2}{2}+\frac{z^3}{3}- \cdots | \\
& \le |1+\frac{r}{2}+\frac{r^2}{3}+\cdots |\cdot |z| =\frac{|\log (1-r)|}{r}|z|.
\end{align*}
 Using this estimate together with \eqref{eq:LaDe} and \eqref{eq:1/2}, we obtain
\begin{equation}
\label{eq:tran}
\frac{1}{2} |\Lambda_n | = \frac{1}{2} |\log (\Delta_n + 1) | < |\Delta_n | .
\end{equation}

Suppose that $\Lambda_n = 0$. Then $\Delta_n=0$, that is $b_1\al_1^n+b_2\al_2^n=0$.
Let
$$
K=\Q(u_0,\ldots,u_{m-1},\al_1,\ldots,\al_m).
$$
 Then, $[K:\Q] \le m!\cdot d$. If $\al_1/\al_2$ is not a unit of $K$, then there exists a prime ideal $\p$ in the ring of integers of $K$ such that  $\ord_{\p} (\al_1/\al_2)$ is non-zero. Then, we get
 \begin{equation}
 \label{eq:ord1}
 n \le n | \ord_{\p} (\al_1/\al_2) | = |\ord_{\p} (b_2/b_1)|\le
 |\ord_{\p} (b_1)| + |\ord_{\p} (b_2)|.
 \end{equation}
 On the other hand, by definition, for any $1\le j \le m$, we know that
 $$
 |b_j|_\p=p^{-\ord_{\p}(b_j)/e_\p},
 $$
 where $p$ is the underlying prime number of $\p$, and $e_\p$ is the ramification index of $\p$ over $p$. Using \eqref{Liouville}, we obtain
 $$
 | \log |b_j|_{\p} | \le \frac{[K:\Q]}{d_\p}\h(b_j), 
 $$
 where $d_\p=[K_\p : \Q_p]$. Notice that $e_\p \le d_\p$. 
 So, for any $1\le j \le m$ we have
 \begin{equation}
 \label{eq:ord2}
| \ord_{\p}(b_j) | \le \frac{e_{\p}[K:\Q]}{d_\p \log p} \h(b_j) \le
 \frac{[K:\Q]}{ \log p} \h(b_j) \le 2B(u),
 \end{equation}
  where $B(u)$ has been defined in \eqref{eq:Bu}.
 Combining \eqref{eq:ord1} with \eqref{eq:ord2}, we get
 \begin{equation}
 \label{eq:n01}
  n\le 4B(u).
 \end{equation}

 Now, we suppose that $\Lambda_n = 0$ and $\al_1/\al_2$ is a unit of $K$.  Since $\al_1/\al_2$ is not a root of unity,
 there exists an embedding $\sigma: K \hookrightarrow \C$ such that $|\sigma(\al_1)/\sigma(\al_2)|>1$. By \eqref{udis1}, we have
 $$
 |\sigma(\al_1)|-|\sigma(\al_2)| > s(u).
 $$
 Notice that
$$
|\sigma(b_2)/\sigma(b_1)| \le \exp (2B(u)),
$$
which can be deduced similarly as \eqref{eq:|bj|}. In view of
$$
\sigma(b_1)\sigma(\al_1)^n+\sigma(b_2)\sigma(\al_2)^n=0,
$$
we deduce that
\begin{equation}
\label{eq:sigma}
|\sigma(\al_1)/\sigma(\al_2)|^n = |\sigma(b_2)/\sigma(b_1)| \le \exp (2B(u)).
\end{equation}
Since
$$
|\sigma(\al_1)/\sigma(\al_2)|^n > \( 1+s(u)/|\sigma(\al_2)| \)^n
> (1+s(u)/(1+H(f^*)))^n,
$$
where the last inequality follows from Lemma \ref{Cauchy}, we consider the inequality
$$
(1+s(u)/(1+H(f^*)))^n > \exp (2B(u)),
$$
which gives
$$
n > \frac{2B(u)}{\log (1+s(u)/(1+H(f^*)) )}.
$$
Since $\log (1+z) > z -z^2/2 > z/2$ for $0< z <1$, it suffices to require that
\begin{equation}
\label{eq:n02}
n > \frac{4B(u)(1+H(f^*))}{s(u)}.
\end{equation}

Notice that the lower bound in \eqref{eq:n02} is much larger than the upper bound in \eqref{eq:n01}. Thus, if integer $n$ satisfies \eqref{eq:n02}, then the inequality in \eqref{eq:sigma} is not true, and we must have $\Lambda_n \ne 0$.


Now, we assume that $n$ satisfies \eqref{eq:n02}. So, $\Lambda_n \ne 0$. Applying Baker's inequality \eqref{Baker}, we find that
\begin{equation}
\label{eq:Lam}
|\Lambda_n | > \exp \( -2^{38}D^2A_1A_2A_3 \log (eD) \log (en+e) \),
\end{equation}
where $D$ is the degree of the number field generated by $b_2/b_1$ and $\al_2/\al_1$ over $\Q$, and
\begin{align*}
& A_1 = \pi, \\
& A_2 \ge \max \{ D\h(b_2/b_1), |\log (b_2/b_1)| \} , \\
& A_3 \ge \max \{ D\h(\al_2/\al_1), |\log (\al_2/\al_1)| \}.
\end{align*}

 Since both $b_2/b_1$ and $\al_2/\al_1$ are contained in $K$, we have
$$
D\le [K : \Q] \le m!\cdot d.
$$

By \eqref{eq:bj1}, we get
$$
D\h(b_2/b_1) \le D (\h(b_1)+\h(b_2)) \le 2B(u).
$$
 In addition, we note that
$$
| \log (b_2/b_1) | \le \log | b_2/b_1 | + \pi \le D \h(b_2/b_1)+ \pi \le  2B(u)+\pi.
$$
Thus, we choose 
$$
A_2 = \frac{1}{2} C_1(u),
$$
where $C_1(u)$ has been defined in Theorem \ref{thm:dom}. It is easy to see that $A_2 > 2B(u)+\pi$.

Now, we want to choose $A_3$. Since
\begin{align*}
\h(\al_2/\al_1) \le \h(\al_2) + \h(\al_1)
 \le 2\log M(f^*) \le 2\log H(f^*) + \log (m+1),
\end{align*}
where the last inequality follows from \eqref{Mahler}.
On the other hand, we have
$$
|\log (\al_2/\al_1) | \le \log |\al_2/\al_1| + \pi < 2 \log (H(f^*)+1) + \pi,
$$
where the last inequality is derived from Lemma \ref{Cauchy}.
So, we can choose
$$
A_3= m! \cdot 2d (m+1)^{0.5} H(f^*)^{0.5}.
$$

Define
$$
c=2^{39}D^2A_1A_2A_3 \log (eD).
$$
Then, under \eqref{eq:n02}, the inequality \eqref{eq:Lam} becomes
\begin{equation}
\label{eq:Lam1}
|\Lambda_n | > \exp(-c\log n),
\end{equation}
which, together with \eqref{eq:initial} and \eqref{eq:tran}, implies that
\begin{equation}
\label{eq:b1b2}
|b_1\al_1^n+b_2\al_2^n| > \frac{1}{2}|b_1\al_1^n| \exp(-c\log n).
\end{equation}
Substituting relevant results into the definition of $c$, we redefine
$$
c=2^{40}\pi (m!\cdot d)^{3.5}(m+1)^{0.5}H(f^*)^{0.5}C_1(u).
$$

Now, we are ready to find a lower bound for $n$ such that
$$
|b_1\al_1^n+b_2\al_2^n| > \sum_{j=3}^{m}|b_j\alpha_j^n|.
$$
This is implied in the following inequality by using \eqref{eq:b1b2}
$$
\frac{1}{2}|b_1\al_1^n| \exp(-c\log n) \ge  \sum_{j=3}^{m}|b_j\alpha_j^n|.
$$
That is, we need that
$$
|b_1| \exp(-c\log n) \ge 2\sum_{j=3}^{m}|b_j|\left(|\alpha_j|/|\al_1|\right)^n,
$$
which follows from the inequality
\begin{equation}
\label{eq:b12}
|b_1| \exp(-c\log n) \ge 2\sum_{j=3}^{m}|b_j|\left(1-s(u)/|\al_1|\right)^n.
\end{equation}

By \eqref{eq:|bj|}, the inequality \eqref{eq:b12} is implied in the following inequality
$$
\exp(-B(u)-c\log n) \ge 2m \exp(B(u)) \left(1-s(u)/|\al_1|\right)^n,
$$
which is equivalent to
$$
-n\log (1-s(u)/|\al_1|) - c\log n \ge 2B(u)+ \log (2m).
$$
As in \eqref{eq:final1}, it suffices to require that
\begin{equation}
\label{eq:n1}
ns(u)/(1+H(f^*))-c\log n \ge 2B(u)+ \log (2m).
\end{equation}

Notice that the integers $n$ satisfying the following inequalities
also satisfies \eqref{eq:n1},
\begin{equation}
\label{eq:n2}
\left\{\begin{array}{ll}
 c\log n \le  ns(u)/(2+2H(f^*)),\\
 \\
 ns(u)/(2+2H(f^*)) \ge 2B(u)+ \log (2m).\\
\end{array}\right.
\end{equation}

Since the function $x/\log x$ is strictly increasing when $x\ge 3$, for $A\ge 3$, if $x\ge 2A\log A$, then $x/\log x \ge A$. 
Thus, if
\begin{equation}
\label{eq:n3}
n \ge 4cs(u)^{-1}(1+H(f^*)) \log \( 2cs(u)^{-1}(1+H(f^*))\),
\end{equation}
then the first inequality in \eqref{eq:n2} holds, and in fact the second one also holds. Note that the lower bound in \eqref{eq:n3} is much bigger than that in \eqref{eq:n02}.

Thus, by \eqref{eq:n3} we get the following lower bound for the index $n$ implying the inequality \eqref{eq:b12}
\begin{equation}
\label{eq:lower2}
n> 2C_3(u) \log C_3(u).
\end{equation}

 So, if integer $n$ satisfies the
inequality \eqref{eq:lower2}, then we have
$$
|b_1\al_1^n+b_2\al_2^n| > \sum_{j=3}^{m}|b_j\alpha_j^n|.
$$
Thus, $u_n\ne 0$. This completes the proof of the first desired result.

The remaining desired result follows from \eqref{eq:bj2}.
\end{proof}

Following the ideas in \cite{MST} and in the proof of Theorem \ref{thm:nondom}, one can get an explicit result for Lemma \ref{lem:MST} in the case when the sequence $\{u_n\}$ is simple and has exactly three roots with maximal modulus. 
However, this might be very complicated and deserves studying as a separate project.



\subsection{Quadratic characteristic polynomials}

If the sequence $\{u_n\}$ is of order 2, we can get better results.

\begin{theorem}
\label{thm:order2}
Let $\{u_n\}$ be a real simple LRS of algebraic numbers defined by \eqref{sequence} of order $2$. Let $f(X), f^*(X) ,d$ be defined as in Theorem \ref{thm:dom}. 
If $f$ has a dominant root, then for the sequence $\{u_n\}$, SP, PP and UPP are all decidable by only testing the first $\lfloor N_3(u) \rfloor$ terms, where
$$
N_3(u)=4dH(f^*)^2 \( \h(u_0)+\h(u_1)+\frac{3}{2} \log (\sum_{i=0}^{2}|a_i^*|^2) + \frac{3}{2} \).
$$
Otherwise if $f(X)$ does not have a dominant root and the quotient of its two roots is not a root of unity, then SP is decidable by only testing the first $\lfloor N_4(u) \rfloor$ terms, where
$$
N_4(u)=8d \( \h(u_0)+\h(u_1)+\frac{3}{2} \log (\sum_{i=0}^{2}|a_i^*|^2) + \frac{3}{2} \).
$$
\end{theorem}

\begin{proof}
Let $\al_1$ and $\al_2$ be the two characteristic roots of $\{u_n\}$. 
First, we suppose that $|\al_1| > |\al_2|$.  Note that in this case both $\al_1$ and $\al_2$ are real. By Lemma \ref{quadratic}, we know
$$
|\al_1| - |\al_2 | \ge 1/H(f^*).
$$
Then, using Lemma \ref{lem:order2} and applying the same arguments as in the proof of Theorem \ref{thm:dom}, we get that if integer $n$ satisfies
$$
n>N_3(u),
$$
then the sign of $u_n$ is the same as that of $b_1\al_1^n$, especially $u_n\ne 0$. This completes the proof of the first part of the theorem.

Now, we suppose that $|\al_1|=|\al_2|$. 
If $\al_1/\al_2$ is a unit of $K$, then in view of $|\al_1/\al_2|=|\al_2/\al_1|=1$, we find that $\al_1/\al_2$ is a root of unity, 
which contradicts the assumption that $\al_1/\al_2$ is not a root of unity. 
So, $\al_1/\al_2$ must be not a unit of $K$. 
Note that for any integer $n\ge 0$ we have 
$$
u_n = b_1 \al_1^n + b_2 \al_2^n 
$$
for some non-zero complex numbers $b_1$ and $b_2$, 
similar as the deductions of \eqref{eq:n01} we conclude that if integer $n$ satisfies
$$
n > N_4(u),
$$
then $u_n \ne 0$. This completes the proof of the theorem.

\end{proof}



\subsection{Decidability for almost all sequences}

As mentioned before, although Theorems \ref{thm:dom}, \ref{thm:nondom} and \ref{thm:order2} only concern real simple LRS of algebraic numbers, the arguments are still valid for arbitrary simple LRS of algebraic numbers when only considering SP. For example, in this case it is not needed  that the coefficient $b_1$ in the proof of Theorem \ref{thm:dom} is a real number. We merge them into the following. 

\begin{theorem}
\label{thm:Skolem}
Let $\{u_n\}$ be a simple LRS of algebraic numbers defined by \eqref{sequence} of order $m\ge 2$, and let $f(X)$ be its characteristic polynomial. Suppose that $f$ has a dominant root or has exactly two roots with maximal modulus (their quotient is not a root of unity). Then, SP is  decidable by only testing finitely many initial terms, whose amount is bounded explicitly by the initial data as in Theorems \ref{thm:dom}, \ref{thm:nondom} or \ref{thm:order2}. 
\end{theorem}

Now, we are ready to state and prove the key result. 

\begin{theorem}
\label{thm:almost}
For almost all LRS of algebraic numbers with integer coefficients (or rational coefficients), SP is  decidable by only testing finitely many terms, whose amount is bounded explicitly by the initial data as in Theorems \ref{thm:dom}, \ref{thm:nondom} or \ref{thm:order2}. The same is also true for both PP and UPP for real LRS of algebraic numbers with integer coefficients (or rational coefficients).
\end{theorem}

\begin{proof}
Let $\{u_n\}$ be a LRS of algebraic numbers defined by \eqref{sequence} of order $m\ge 2$, and let $f(X)$ be its characteristic polynomial. 

Suppose that $f$ is an integer polynomial. Note that $f$ is monic. Since almost all monic integer polynomials are irreducible (for example, see \cite{Chela}), we assume that $f$ is irreducible. Then, $\{u_n\}$ is a simple LRS.  By Lemma \ref{lem:monic}, almost all monic integer polynomials have a dominant root. Then, this case of SP is done by applying Theorem \ref{thm:Skolem}.

Now, assume that $f$ is a polynomial over $\Q$. Let $\delta$ be the smallest positive integer such that $\delta f(X)\in \Z[X]$. $\delta f$ has the same roots as $f$, but note that $\delta f$ may be not monic. Since almost all integer polynomials are irreducible (for example, see \cite{Kuba}), by Lemma \ref{lem:poly}, we only need to consider the case when $\delta f$ is irreducible and non-degenerate. Furthermore, by Lemma \ref{lem:poly}, we can assume that $\delta f$ has a dominant root or has exactly two roots with maximal modulus. Then, this case of SP is also established by using Theorem \ref{thm:Skolem}. Thus, this completes the proof of the first part. 

For real LRS of algebraic numbers with integer coefficients (or rational coefficients), the remaining desired results can be proved similarly by using Lemma \ref{lem:Bell} and Theorems \ref{thm:dom} and \ref{thm:order2}. Note that for an irreducible and  non-degenerate characteristic polynomial $f$, if it has exactly two roots with maximal modulus,  then these two root must be non-real, thus this case has been done in Lemma \ref{lem:Bell}.
\end{proof}



\subsection{Estimate the exceptional set}
\label{sec:except}

Regarding the results in Theorem \ref{thm:Skolem}, one question of interest is for how many such LRS the Skolem Problem might be not decidable explicitly. It depends on the way how to count LRS. 

For LRS of algebraic numbers with integer coefficients of order $m\ge 3$, we define that two LRS are equivalent if they have the same characteristic polynomial. So, it is equivalent to ask for how many such equivalence classes the Skolem Problem might be not decidable explicitly. 
For the equivalence classes corresponding to the set 
$S_m(H)$ (defined in Section \ref{sec:basic}), 
let $A_m(k,H)$ be the number of polynomials $f\in S_m(H)$ having exactly $k$ roots with maximal modulus, then by \cite[Theorem 3.2]{DS3} and \cite[Theorem 1.1]{DS1} we have 
\begin{equation}
\label{eq:except1}
|S_m(H)| - A_m(1,H) - A_m(2,H)\le c_1(m) H^{m-1}, 
\end{equation}
where $c_1(m)$ is a function with respect to $m$. 
According to Theorem \ref{thm:Skolem}, this can be viewed as an answer to the question. 

On the other hand, for LRS of algebraic numbers with rational coefficients of order $m\ge 3$, we can define the same equivalent relation. For the equivalence classes corresponding to the set 
$$
T_m^*(H)= \{f(X)/H: f\in S_m^*(H)\}, 
$$
let $A_m^*(k,H)$ be the number of polynomials $f\in T_m^*(H)$ having exactly $k$ roots with maximal modulus, then by \cite[Theorem 3.4]{DS3} and \cite[Theorem 1.4]{DS1} we have 
\begin{equation}
\label{eq:except2}
|T_m^*(H)| - A_m^*(1,H) - A_m^*(2,H)\le c_2(m) H^m, 
\end{equation} 
where $c_2(m)$ is a function with respect to $m$. 
This can be viewed as another answer to the question.



\section*{Acknowledgement}

The author want to thank Manas Patra and Igor E. Shparlinski for introducing him into the Skolem Problem and also for useful discussions and helpful comments.  
The research was supported by the Australian Research Council Grant DP130100237.


\begin{thebibliography}{99}

\bibitem{BDJB}
P.C. Bell, J.-C. Delvenne, R.M. Jungers and V.D. Blondel, \textit{The continuous Skolem-Pisot problem}, Theor. Comput. Sci. \textbf{411} (2010),  3625--3634.

\bibitem{Bell}
J.P. Bell and S. Gerhold, \emph{On the positivity set of a linear recurrence sequence}, Israel J. Math. \textbf{157}(1) (2007), 333--345.

\bibitem{BM}
J. Berstel and M. Mignotte, \textit{Deux propri\'et\'es d\'ecidables des suites r\'ecurrentes lin\'eaires}, Bull. Soc. Math. France \textbf{104} (1976), 175--184.

\bibitem{BP}
V.D. Blondel and N. Portier, \textit{The presence of a zero in an integer linear recurrent sequence is NP-hard to decide}, Linear Algebra Appl. \textbf{351-352} (2002), 91--98.

\bibitem{Burke}
J.R. Burke and W.A. Webb, \emph{Asymptotic behaviour of linear recurrences}, Fibonacci Quart. \textbf{19}(4) (1981),  318--321.

\bibitem{Chela}
R.~Chela, \emph{Reducible polynomials}, J. Lond. Math. Soc. {\bf 38} (1963), 183--188.

\bibitem{DS1}
A. Dubickas and M. Sha, \textit{Counting degenerate polynomials of fixed degree and bounded height}, Monatsh. Math., DOI 10.1007/s00605-014-0680-9, to appear, \url{http://arxiv.org/abs/1402.5430}.

\bibitem{DS2}
A. Dubickas and M. Sha, \textit{Counting and testing dominant polynomials}, Exper. Math.,  to appear, \url{http://arxiv.org/abs/1407.2789}.

\bibitem{DS3}
A. Dubickas and M. Sha, \textit{Positive density of integer polynomials with some prescribed properties}, preprint, 2015, \url{http://arxiv.org/abs/1504.05144}.

\bibitem{DSS}
A. Dubickas, M. Sha and I. Shparlinski, \textit{Explicit form of Cassels' $p$-adic embedding theorem for number fields}, Can. J. Math., to appear,  \url{http://arxiv.org/abs/1401.6819}.

\bibitem{EPSW}
G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, {\it Recurrence Sequences},
Mathematical Surveys and Monographs, Am. Math. Soc., Providence, RI, 2003.

\bibitem{Gerhold}
S. Gerhold, \emph{Point lattices and oscillating recurrence sequences}, J. Differ. Equ. Appl. \textbf{11}(6) (2005), 515--533.

\bibitem{HHHK}
V. Halava, T. Harju, M. Hirvensalo and J. Karhum\"aki, \textit{Skolem's problem -- on the border between decidability and undecidability}, Technical  Report 683, Turku Centre for Computer Science, 2005.

\bibitem{Klinger1967}
A. Klinger, \emph{The Vandermonde matrix}, Amer. Math. Monthly \textbf{74} (1967), 571--574.

\bibitem{Kuba}
G.~Kuba, \emph{On the distribution of reducible polynomials}, Math. Slovaca {\bf 59} (2009), 349--356.

\bibitem{Matveev}
E.M. Matveev, \textit{An explicit lower bound for a homogeneous rational linear form in the logarithms of algebraic numbers II}, Izv. Math. \textbf{64}(6) (2000), 1217--1269.

\bibitem{MG}
M. Mignotte and P. Glesser, \emph{Landau's Inequality via Hadamard's}, J. Symb. Comput. \textbf{18}(4) (1994), 379--383.

\bibitem{MST}
M. Mignotte, T.N. Shorey and R. Tijdeman, \textit{The distance between terms of an algebraic recurrence sequence}, J. Reine Angew. Math. \textbf{349} (1984), 63--76.

\bibitem{Mishra}
B. Mishra, \textit{Algorithmic algebra}, Springer, New York, 1993.

\bibitem{OW12}
J. Ouaknine and J. Worrell, \textit{Decision problems for linear recurrence sequences}, In:
Proc. 6th Intern. Workshop on Reachability Problems (RP), LNCS \textbf{7550}, pp. 21--28, Springer, 2012.

\bibitem{OW14a}
 J. Ouaknine and J. Worrell, \textit{Positivity problems for low-order linear recurrence sequences}, In:  Proc. 25th Symp. on Discrete Algorithms (SODA), pp. 366--379, ACM-SIAM, 2014. %Full version as arXiv:1307.2779.

\bibitem{OW14b}
J. Ouaknine and J. Worrell, \textit{On the Positivity Problem for simple linear recurrence sequences},
In: Proc. 41st Intern. Colloq. on Automata, Languages and Programming (ICALP), LNCS \textbf{8573}, pp. 318--329, Springer, 2014. %Full version as  arXiv:1309.1550.

\bibitem{OW14c}
J. Ouaknine and J. Worrell, \textit{Ultimate Positivity is decidable for simple linear recurrence sequences}, In: Proc. 41st Intern. Colloq. on Automata, Languages and Programming (ICALP), LNCS \textbf{8573}, pp. 330--341, Springer, 2014. %Full version as arXiv:1309.1914.

\bibitem{Tao}
T. Tao, \textit{Structure and randomness: pages from year one of a mathematical blog}, American Mathematical Society, 2008.


\bibitem{Ver}
N.K. Vereshchagin, \textit{Occurrence of zero in a linear recursive sequence}, Math. Notes \textbf{38} (1985), 609--615.

\bibitem{Waldschmidt}
M. Waldschmidt, \emph{Diophantine approximation on linear algebraic groups. Transcendence properties of the exponential function in several variables,} Grundlehren der Mathematischen Wissenschaften \textbf{326}, Springer, Berlin, 2000.




\end{thebibliography}

\end{document}

%------------------------------------------------------------------------------
% End of journal.tex
%------------------------------------------------------------------------------


For two LRS defined as \eqref{sequence}, we say that they are equivalent if and only if they have the same characteristic polynomial. Using this relation, we can divide the elements of any subset of LRS (for instance, the set of LRS of algebraic numbers with integer coefficients) into equivalence classes with respect to the subset. Then, in some settings we can count such equivalence classes satisfying some prescribed properties.  

1505.07147.extracted_bib
{BDJB P.C. Bell, J.-C. Delvenne, R.M. Jungers and V.D. Blondel, The continuous Skolem-Pisot problem, Theor. Comput. Sci. 411 (2010), 3625--3634.
1505.07147.extracted_bib
{Bell J.P. Bell and S. Gerhold, On the positivity set of a linear recurrence sequence, Israel J. Math. 157(1) (2007), 333--345.
1505.07147.extracted_bib
{BM J. Berstel and M. Mignotte, Deux propri\'et\'es d\'ecidables des suites r\'ecurrentes lin\'eaires, Bull. Soc. Math. France 104 (1976), 175--184.
1505.07147.extracted_bib
{BP V.D. Blondel and N. Portier, The presence of a zero in an integer linear recurrent sequence is NP-hard to decide, Linear Algebra Appl. 351-352 (2002), 91--98.
1505.07147.extracted_bib
{Burke J.R. Burke and W.A. Webb, Asymptotic behaviour of linear recurrences, Fibonacci Quart. 19(4) (1981), 318--321.
1505.07147.extracted_bib
{Chela R.~Chela, Reducible polynomials, J. Lond. Math. Soc. {38 (1963), 183--188.
1505.07147.extracted_bib
{DS1 A. Dubickas and M. Sha, Counting degenerate polynomials of fixed degree and bounded height, Monatsh. Math., DOI 10.1007/s00605-014-0680-9, to appear, \url{http://arxiv.org/abs/1402.5430.
1505.07147.extracted_bib
{DS2 A. Dubickas and M. Sha, Counting and testing dominant polynomials, Exper. Math., to appear, \url{http://arxiv.org/abs/1407.2789.
1505.07147.extracted_bib
{DS3 A. Dubickas and M. Sha, Positive density of integer polynomials with some prescribed properties, preprint, 2015, \url{http://arxiv.org/abs/1504.05144.
1505.07147.extracted_bib
{DSS A. Dubickas, M. Sha and I. Shparlinski, Explicit form of Cassels' $p$-adic embedding theorem for number fields, Can. J. Math., to appear, \url{http://arxiv.org/abs/1401.6819.
1505.07147.extracted_bib
{EPSW G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, {Recurrence Sequences, Mathematical Surveys and Monographs, Am. Math. Soc., Providence, RI, 2003.
1505.07147.extracted_bib
{Gerhold S. Gerhold, Point lattices and oscillating recurrence sequences, J. Differ. Equ. Appl. 11(6) (2005), 515--533.
1505.07147.extracted_bib
{HHHK V. Halava, T. Harju, M. Hirvensalo and J. Karhum\"aki, Skolem's problem -- on the border between decidability and undecidability, Technical Report 683, Turku Centre for Computer Science, 2005.
1505.07147.extracted_bib
{Klinger1967 A. Klinger, The Vandermonde matrix, Amer. Math. Monthly 74 (1967), 571--574.
1505.07147.extracted_bib
{Kuba G.~Kuba, On the distribution of reducible polynomials, Math. Slovaca {59 (2009), 349--356.
1505.07147.extracted_bib
{Matveev E.M. Matveev, An explicit lower bound for a homogeneous rational linear form in the logarithms of algebraic numbers II, Izv. Math. 64(6) (2000), 1217--1269.
1505.07147.extracted_bib
{MG M. Mignotte and P. Glesser, Landau's Inequality via Hadamard's, J. Symb. Comput. 18(4) (1994), 379--383.
1505.07147.extracted_bib
{MST M. Mignotte, T.N. Shorey and R. Tijdeman, The distance between terms of an algebraic recurrence sequence, J. Reine Angew. Math. 349 (1984), 63--76.
1505.07147.extracted_bib
{Mishra B. Mishra, Algorithmic algebra, Springer, New York, 1993.
1505.07147.extracted_bib
{OW12 J. Ouaknine and J. Worrell, Decision problems for linear recurrence sequences, In: Proc. 6th Intern. Workshop on Reachability Problems (RP), LNCS 7550, pp. 21--28, Springer, 2012.
1505.07147.extracted_bib
{OW14a J. Ouaknine and J. Worrell, Positivity problems for low-order linear recurrence sequences, In: Proc. 25th Symp. on Discrete Algorithms (SODA), pp. 366--379, ACM-SIAM, 2014. %Full version as arXiv:1307.2779.
1505.07147.extracted_bib
{OW14b J. Ouaknine and J. Worrell, On the Positivity Problem for simple linear recurrence sequences, In: Proc. 41st Intern. Colloq. on Automata, Languages and Programming (ICALP), LNCS 8573, pp. 318--329, Springer, 2014. %Full version as arXiv:1309.1550.
1505.07147.extracted_bib
{OW14c J. Ouaknine and J. Worrell, Ultimate Positivity is decidable for simple linear recurrence sequences, In: Proc. 41st Intern. Colloq. on Automata, Languages and Programming (ICALP), LNCS 8573, pp. 330--341, Springer, 2014. %Full version as arXiv:1309.1914.
1505.07147.extracted_bib
{Tao T. Tao, Structure and randomness: pages from year one of a mathematical blog, American Mathematical Society, 2008.
1505.07147.extracted_bib
{Ver N.K. Vereshchagin, Occurrence of zero in a linear recursive sequence, Math. Notes 38 (1985), 609--615.
1505.07147.extracted_bib
{Waldschmidt M. Waldschmidt, Diophantine approximation on linear algebraic groups. Transcendence properties of the exponential function in several variables, Grundlehren der Mathematischen Wissenschaften 326, Springer, Berlin, 2000.