% Instructions for viewing file:
% The bibliography for this paper was prepared using bibtex.
% To view this paper cut off the bottom part of this file (starting
% at the line marked CUT HERE) and save that part as spectra.bib
% Then run latex, bibtex and latex twice more on the result of this
file.
\documentclass[12pt]{amsart}
\usepackage{amsmath}
\usepackage{enumerate}
\usepackage{amssymb,amscd,amsthm}
% Topstuff
\newtheorem*{specconj}{Spectral Conjecture}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{main}[theorem]{Main Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{question}[theorem]{Question}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{argument}{Argument}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newcommand{\ds}{\displaystyle}
\newcommand{\integers}{{\mathbb Z}}
\newcommand{\naturals}{{\mathbb N}}
\newcommand{\reals}{{\mathbb R}}
\newcommand{\rationals}{{\mathbb Q}}
\newcommand{\complex}{{\mathbb C}}
\newcommand{\nettrace[1]}{tr_{#1}}
\newcommand{\fstar}{f^*}
\newcommand{\pstar}{p^*}
\newcommand{\Astar}{(A^*)}
\newcommand{\vvec}{{\mathbf v}}
\newcommand{\rvec}{{\mathbf r}}
\newcommand{\cvec}{{\mathbf c}}
\newcommand{\wvec}{{\mathbf w}}
\newcommand{\uvec}{{\mathbf u}}
\newcommand{\xvec}{{\mathbf x}}
\newcommand{\spectrum}{(\lambda_1,\lambda_2,\ldots,\lambda_d)}
\numberwithin{equation}{section}
\begin{document}
\bibliographystyle{amsalpha}
\title[The spectra of nonnegative integer matrices]{The spectra of
nonnegative integer matrices via formal power series}
\author{Ki Hang Kim, Nicholas S. Ormes, Fred W. Roush}
\address{Ki Hang Kim \\
Mathematics Research Group \\ Alabama State University\\
Montgomery, AL 36101-0271\\ and Korean Academy of Science and
Technology}
\email{kkim@asu.alasu.edu}
\address{Nicholas S. Ormes \\
Department of Mathematics \\ University of Texas \\ Austin, TX 78712}
\email{ormes@math.utexas.edu}
\address{Fred W. Roush \\Mathematics Research Group \\
Alabama State University \\ Montgomery, AL 36101-0271}
\email{froush@asu.alasu.edu}
\subjclass{Primary 15A18; Secondary 15A36, 58F03, 58F20}
% eigenvalues, integer matrices, symbolic dynamics, zeta functions
\keywords{spectrum of
nonnegative matrix, zeta function of subshift of finite type}
% Abstract
\begin{abstract}
We characterize the $d$-tuples of nonzero complex numbers $\spectrum$
which can occur as the nonzero part of the spectrum of a matrix with
nonnegative integer/rational entries. These results follow easily from
our main theorem: a characterization of the possible nonzero portions of
spectra of primitive integer matrices (the integer case of Boyle and
Handelman's Spectral Conjecture). For the proof of the main theorem
we use polynomial matrices to reduce the problem of realizing a
candidate spectrum $\spectrum$ to factoring the polynomial
$\prod_{i=1}^d (1-\lambda_it)$ as a product $(1-r(t))\prod_{i=1}^n
(1-q_i(t))$ where the $q_i$'s are polynomials in $t\integers_+[t]$
satisfying some technical conditions and $r$ is a formal power series
in $t\integers_+[[t]]$. To obtain the factorization, we present a
hierarchy of estimates on coefficients of power series of the form
$\prod_{i=1}^d (1-\lambda_it)/\prod_{i=1}^n (1-q_i(t))$ to ensure
non-positivity in nonzero degree terms.
\end{abstract}
\maketitle
% Introduction
\section{Introduction}
\label{sec:intro}
An old problem in matrix theory is to determine the $n$-tuples of
complex numbers which can occur as the spectrum of a matrix with
nonnegative entries (see~\cite[chapter 4]{BePl} or~\cite[chapter
VII]{Minc}). Authors have studied the case where the $n$-tuple is
comprised of real numbers~\cite{Bor, Ciarlet, Fri, Kellog, Perfect,
Salz, Soules, Suli}, the case where the matrices under consideration
are symmetric~\cite{Fiedler, JLL}, and the general problem~\cite{Jo,
LLon, Guo}. Various necessary conditions and sufficient conditions
have been provided, but a complete characterization is known for real
$n$-tuples only for $n\leq 4$~\cite{Kellog,Suli} and for complex
$n$-tuples only for $n \leq 3$~\cite{LLon}.
Motivated by symbolic dynamics, Boyle and Handelman refocused
attention on the {\em nonzero part} of the spectrum by conjecturing
the following~\cite{BHmat1,BHmat2} (see also~\cite[\S 8]{B:matexp}
and~\cite[Chapter 11]{LM}).
\begin{specconj}[Boyle, Handelman]
Let $\Lambda = \spectrum$ be a $d$-tuple of nonzero complex numbers
and let $S$ be a unital subring of $\reals$. There is a primitive
matrix over $S$ with characteristic polynomial $t^m \prod_{i=1}^d (t -
\lambda_i)$ for some $m \geq 0$ if and only if
\begin{enumerate}[{\rm (1)}]
\item the coefficients of the polynomial $\prod_{i=1}^d (t- \lambda_i)$
all belong to $S$,\label{Galois}
\item there exists $\lambda_j$ in $\Lambda$ such that
$\lambda_j > |\lambda_i|$ for all $i \neq j$,\label{Perron}
\item if $S = \integers$, then $tr_n(\Lambda) \geq 0$ for
all $n \geq 1$,
\label{nettrace}
\item[{\rm ($3^{\prime}$)}]if $S \neq \integers$, then for all
$n \geq 1$,
$tr(\Lambda^n) \geq 0$ and for all $k \geq 1$,
$tr(\Lambda^n) >0$ implies $tr(\Lambda^{nk}) >0$.
\end{enumerate}
\end{specconj}
Above, $$tr(\Lambda^n) = \sum_{i=1}^d (\lambda_i)^n
\qquad \text{and} \qquad tr_n(\Lambda)
=\sum_{k|n} \mu\left(\frac{n}{k}\right) tr\left(\Lambda^k\right)$$
where $\mu$ is the M\"{o}bius function
$$ \mu(n) = \begin{cases}
1 &\text{if $n=1$}\\
(-1)^e& \text{if $n$ is the product of $e$ distinct primes}\\
0 &\text{if $n$ is divisible by $k^2$ for some $k \geq 2$}.
\end{cases}
$$
Boyle and Handelman proved the Spectral Conjecture in many cases,
including the case $S = \reals$~\cite{BHmat1,BHmat2}. In this paper
we resolve an important remaining case by proving the Spectral
Conjecture for $S=\integers$ (Theorem~\ref{spectraltheorem}). The
Spectral Conjecture for $S=\rationals$ (Corollary~\ref{cor:rat})
follows from this result as do characterizations of the possible
nonzero spectra of irreducible and general nonnegative matrices over
$\integers$ and $\rationals$
(Corollaries~\ref{cor:irred},~\ref{cor:nonneg}).
It is not difficult to see the necessity of the conditions in the
Spectral Conjecture for $S=\integers$. Suppose $A$ is a primitive
matrix over $\integers$ with det($t$I - $A$) = $t^m\prod_{i=1}^d (t -
\lambda_i)$. Then condition (1) is clearly satisfied. Condition (2)
follows from Perron-Frobenius Theory, the spectral radius of primitive
matrix (a matrix with nonnegative entries such that some power has all
positive entries) is always an eigenvalue of multiplicity one for that
matrix. Condition (3) follows when we interpret $A$ as the adjacency
matrix for a directed graph $G_A$. In this case, $tr(\Lambda^n)$
represents the number of loops of length $n$ in the graph, and
$tr_n(\Lambda)$ represents the number of loops of length $n$ which are
not formed by concatenating a single loop of shorter length some
number of times.
Let $\Lambda = \spectrum$ satisfy the conditions of the Spectral
Conjecture for $\integers$. We outline our construction of a matrix
$A$ over $\integers_+$ with nonzero spectrum $\Lambda$. Firstly, we
note that there is a primitive matrix $A(t)$ over
$t\integers_+[t]$ (the ring of polynomials with nonnegative integer
entries and no constant term) such that $\det({\rm I}-A(t)) =
\prod_{i=1}^d (1-\lambda_it)$ if and only if
there is a primitive integer matrix $A$ with nonzero spectrum
$\Lambda$ (see~\cite[\S 5]{B:matexp}). In Lemma~\ref{thm:reduction},
we use
this fact to essentially reduce the problem of constructing a
polynomial matrix $A(t)$ as above to finding polynomials $q_1,q_2,
\ldots , q_n \in t\integers_+[t]$ and a power series $r \in
t\integers_+[[t]]$ such that
$$\prod_{i=1}^d(1-\lambda_it) = (1-r(t))\prod_{i=1}^n (1-q_i(t)).$$ In
particular, we show that there are integers $o(n) \geq 0$, $n_0 \geq 1$
and a polynomial $q \in t\integers_+[t]$ such that the $n$th coefficient
of
$$\frac{ \prod_{i=1}^d(1-\lambda_it)}{(1-q(t)) \prod_{n=1}^{n_0}
(1-t^n)^{o(n)}}$$ is non-positive for all $n\geq 1$. We obtain the
desired inequality by giving estimates for the $n$th coefficient of
$\prod_{n=1}^{n_0} (1-t^n)^{o(n)}$ in certain linear, polynomial,
subexponential, exponential ranges of $n_0$. For sufficiently large
$n_0$, these estimates imply the non-positivity of coefficients of the
above quotient up to a degree where the additional factor $1-q(t)$
takes over.
With the results here and in~\cite{BHmat1}, a complete
characterization of the spectra of primitive matrices over $\reals$ or
$\integers$ would follow from sharp bounds on the size of the
realizing matrix. However, it seems that bounds of this type will be
quite difficult to pin down. In particular, it follows from an
inequality in~\cite{Jo,LLon} that given any $N$ one can construct a
$3$-tuple satisfying the Boyle-Handelman conditions for $\reals$ such
that the size of a realizing matrix must be at least $N\times
N$ (see~\cite{JLL}). This is in dramatic contrast to the symmetric case
where Johnson, Laffey and Loewy showed that if a $d$-tuple $\spectrum$
of real numbers is the nonzero spectrum of a symmetric matrix then it
is the nonzero spectrum of a symmetric matrix of size no more than
$d(d+1)/2$~\cite{JLL}.
We propose that a variant of the size bound problem may be more
approachable:
Given $\spectrum$ satisfying the Boyle-Handelman conditions,
produce sharp bounds on the size of a polynomial
matrix $A(t)$ with $\det({\rm I} - A(t)) =
\prod_{i=1}^d(1-\lambda_it)$. In some respects, bounds of this type
would be more useful than bounds on ordinary matrices since one can
exhibit a much wider range of behavior with polynomial matrices of a
fixed size. Moreover, it is conceivable that this line of study could
lead to a solution to the original problem. For an example of the
freedom afforded by polynomial matrices, Perrin showed that for every
$\lambda$ which occurs as the spectral radius of a primitive integer
matrix, there is a $2\times 2$ matrix $A(t)$ over $t\integers_+[t]$
with $\det(I-A(t)) = (1-\lambda t)
\prod_{i=1}^d (1-\lambda_it)$ and $\lambda > |\lambda_i|$ for all
$i$~\cite{Perrin} (see also~\cite[\S 5]{B:matexp}).
Our characterization of the possible nonzero spectra of
nonnegative/irreducible/primitive matrices over $\integers$ translates
into a characterization of the possible zeta functions for
general/irreducible/mixing shifts of finite type (SFTs) in symbolic
dynamics. In this setting our work follows Lind's classification of
entropies of SFTs~\cite{Lind:ent2}, Boyle and Handelman's
classification of zeta functions for finitely presented
systems~\cite{BHmat1} and various authors' development of polynomial
matrices as tools in symbolic dynamics~\cite{BGMY, KRW, MT,
Shannon}. In general, there is a deep connection between symbolic
dynamics and the asymptotic algebra of nonnegative matrices
(see~\cite{B:matexp,BHmat2,LM}). Boyle and
Handelman's Generalized Spectral Conjecture (see~\cite[\S
8]{B:matexp}) concerns the matrix relation, strong shift equivalence
over $S$, which in the case $S = \integers_+$ corresponds to conjugacy
between associated SFTs. Strong shift equivalence over $S$ is defined
as the transitive closure of the elementary relation $\sim_S$ where $A
\sim_S B$ if there exist matrices $U,V$ over $S$ such that
$$A = UV \qquad \text{and} \qquad VU= B.$$ Strong shift equivalence
seems to be the strongest asymptotic equivalence
relation~\cite{B:matexp,BHmat2}. In particular strong shift
equivalent matrices have the same nonzero spectrum. Boyle and
Handelman conjecture that a matrix $A$ over a unital ring $S \subseteq
\reals$ is strong shift equivalent to a primitive matrix if and only
if the nonzero spectrum of $A$ satisfies the conditions of the
Spectral Conjecture.
We thank Mike Boyle for helpful discussions and for his detailed
examination of portions of this manuscript.
% Statement
\section{Main Results}
\label{sec:statement}
\subsection{Statements} For a unital ring $S \subseteq \reals$ we will
often refer to the conditions of the Spectral Conjecture for $S$ as
the {\em Boyle-Handelman conditions for $S$}. We will also clean up
notation a bit by noting that for a matrix $A$, there is an $m \geq 0$
such that $\det(t{\rm I}-A) = t^m \prod_{i=1}^d (t-\lambda_i)$ if and
only if $\det({\rm I}-At) = \prod_{i=1}^d (1-\lambda_it)$.
\begin{definition}
A matrix $A$ over $\reals_+$ is {\em primitive} there is an $n>0$ such
that all of the entries of $A^n$ are positive.
\end{definition}
\begin{main}
\label{spectraltheorem}
Let $\Lambda = \spectrum$ be a $d$-tuple of nonzero complex numbers
with $|\lambda_1| \geq |\lambda_2| \geq \cdots \geq |\lambda_d|$.
There exists a primitive integer matrix $A$ such that
$\det({\rm I}-At) = \prod_{i=1}^d (1-\lambda_it)$
if and only if
\begin{enumerate}[{\rm (1)}]
\item the polynomial $\prod_{i=1}^d (1-\lambda_it)$ has
integer coefficients,
\item $\lambda_1 > |\lambda_i|$ for $i = 2,3,\ldots,d$,
\item $\nettrace[n](\Lambda) \geq 0$ for all $n \geq 1$.
\end{enumerate}
\end{main}
As shown in~\cite{BHmat1}, the Spectral Conjecture for $\rationals$
follows from our main result.
\begin{corollary} \label{cor:rat}
Let $\Lambda = \spectrum$ be a $n$-tuple of nonzero complex numbers
with $|\lambda_1| \geq |\lambda_2| \geq \cdots \geq
|\lambda_d|$. There is a primitive rational matrix $A$ with
$\det(I-At) = \prod_{i=1}^d (1 - \lambda_it)$ if and only if
\begin{enumerate}[{\rm (1)}]
\item the polynomial $\prod_{i=1}^d (1- \lambda_it)$
has rational coefficients,
\item $\lambda_1 > |\lambda_i|$ for $i=2,3,\ldots,d$,
\item for all $n \geq 1$,
$tr(\Lambda^n) \geq 0$ and \\
for all $k \geq 1$, $tr(\Lambda^n) >0$ implies $tr(\Lambda^{nk}) >0$.
\end{enumerate}
\end{corollary}
We briefly describe how a characterization of the spectra of
irreducible and nonnegative matrices follow from the primitive case
(see also~\cite{BHmat1}).
\begin{definition}
A matrix $A$ over $\reals_+$ is {\em irreducible} if for all $(i,j)$
there is an $n \geq 0$ such that the $(i,j)$ entry of $A^n$ is
positive.
\end{definition}
If $A$ is irreducible then there is a $p\geq 1$ and a primitive matrix
$B$ such that $\det({\rm I} - At) = \det({\rm I} - Bt^p)$.
This leads to the following.
\begin{corollary}
\label{cor:irred}
Let $\Lambda = \spectrum$ be a $d$-tuple of nonzero complex numbers.
There exists an irreducible matrix $A$ over $\integers$ $(\rationals)$
such that $\det({\rm I} - At) = \prod_{i=1}^d (1-\lambda_it)$ if and
only if there exist an integer $p >0$ and a partition of $\Lambda$
into subtuples $\{\Lambda_k : 0 \leq k < p \}$ such that
\begin{enumerate}[{\rm (1)}]
\item $\Lambda_{k+1} = e^{2\pi i/ p} \Lambda_k$ for $0 \leq k < (p-1)$,
\item $(\Lambda_0)^p$ satisfies the Boyle-Handelman conditions for
$\integers$ $(\rationals)$.
\end{enumerate}
\end{corollary}
If $A$ is a nonnegative matrix then there are irreducible matrices
$A_1, A_2, \ldots , A_m$ such that $\det({\rm I}-At) = \prod_{j=1}^m
\det({\rm I}-A_jt)$.
\begin{corollary}
\label{cor:nonneg}
Let $\Lambda = \spectrum$ be a $d$-tuple of nonzero complex numbers.
There exists a nonnegative matrix $A$ over $\integers$ $(\rationals)$
such that $\det({\rm I}-At) =
\prod_{i=1}^d (1-\lambda_it)$ if and only if there exist an integer
$n > 0$, integers $p(1),p(2),\ldots,p(n) >0$ and a partition of
$\Lambda$ into subtuples $\{\Lambda_{(j,k)} : 1 \leq j \leq n, \ 0
\leq k < p(j)\}$ such that
\begin{enumerate}[{\rm (1)}]
\item $\Lambda_{(j,k+1)} = e^{2 \pi i/ p(j)}
\Lambda_{(j,k)}$ for all $0 \leq k < (p(j)-1)$ and $1 \leq j \leq n$,
\item $(\Lambda_{(j,0)})^{p(j)}$ satisfies the Boyle-Handelman
conditions for $\integers$ $(\rationals)$ for all $1 \leq j \leq n$.
\end{enumerate}
\end{corollary}
\begin{remark}
\label{rem:zeta}
A characterization of zeta functions for SFTs follows from
Corollary~\ref{cor:nonneg}. Suppose $A$ is a nonnegative matrix $A$
and $S_A$ is the corresponding SFT. If $Fix((S_A)^n)$ is the set of
fixed points of the map $(S_A)^n$ then we have the following
definition and result.
\begin{equation*}
\zeta_{(S_A)}(t) =
\exp\left( \sum_{i=1}^{\infty} \frac{\#Fix((S_A)^n)}{n} t^n \right)
= \frac{1}{\det({\rm I} - A t)}.
\end{equation*}
Therefore, a power series in $\integers[[t]]$ is a zeta function if
and only if it is equal to $\prod_{i=1}^d ( 1-\lambda_i t)^{-1}$ where
$\spectrum$ satisfies the conditions of Corollary~\ref{cor:nonneg}.
Moreover, since irreducible matrices give rise to irreducible SFTs and
primitive matrices give rise to mixing SFTs,
Theorem~\ref{spectraltheorem} and Corollary~\ref{cor:irred} give finer
characterizations for zeta functions associated to SFTs in those
classes.
\end{remark}
\subsection{Proof Scheme for Main Theorem}
Proving the sufficiency of the Boyle-Handelman conditions for
$\integers$ will come down to producing a certain factorization of the
polynomial $\prod_{i=1}^d (1-\lambda_it)$ in the ring of formal power
series with integer coefficients. To show this, we must first examine
the behavior of coefficients of large degree in a rational expression.
\begin{lemma}
Suppose $p, q \in t\integers[t]$ and $r
\in \integers[[t]]$ such that
$$\frac{1-p(t)}{1-q(t)} = r(t) = \sum_{i=0}^{\infty} r_n t^n.$$
Suppose that $1-q(t) = (1-\alpha t) \prod_{i=1}^d (1-\alpha_i
t)^{j_i}$ where the $\alpha_i$ are all distinct, $j_i \geq 1$ and
$\alpha > |\alpha_i|$ for $i\geq 1$. Then there exist constants $K, k
>0 $ such that
$$\left|\frac{r_n}{\alpha^{n}} - \frac{\alpha
(1-p(1/\alpha))}{q'(1/\alpha)} \right| < K e^{-k n}.$$
\label{lem:asymptotic}
\end{lemma}
\begin{proof}
First we consider the power series $S(t) = (1-q(t))^{-1}$. Using a
partial fraction decomposition we may write
\begin{equation}
\label{eqn:partfrac}
S(t) = \frac{a}{1-\alpha t} + \sum_{i=1}^d \sum_{j=1}^{j_i}
\frac{a(i,j)}{(1-\alpha_it)^j}
\end{equation}
where $a(i,j)$ are constants. We obtain the formula $a = \alpha
/q'(1/\alpha )$ by multiplying both sides of equation~\ref{eqn:partfrac}
by $1-q(t)$ and plugging in $1/\alpha$.
Since $(1-\alpha_it)^{-j} = \sum_{n=1}^{\infty} \binom{n+j-1}{n}
(\alpha_it)^n$ we have a formula for the $n$th coefficient of $S(t)$
$$s_n = \alpha^n \left( a + \sum_{i=1}^d \sum_{j=1}^{j_i}
\binom{n+j-1}{n} a(i,j)
\left(\alpha_i/\alpha\right)^n\right).$$
Therefore, there exist constants $C,c >0$ such that
$$\left| s_n \alpha^{-n} - \alpha /q'(1/\alpha )\right| =
\left| s_n \alpha^{-n} - a \right| < C e^{-c n}.$$
The formula for $r_n$, the $n$th coefficient of
$S(t) (1-p(t))$, is given by
the following
\begin{equation*}
r_n = s_n - \sum_{i=1}^d p_i s_{n-i}
= s_n \left(1 - \sum_{i=1}^d p_i s_{n-i}/s_n\right).
\end{equation*}
By the estimates on $s_n$, the ratio $s_{n-i}/s_n$ is exponentially
close to $\alpha^{-i}$. This gives $r_n \approx s_n(1-p(1/\alpha))$
with an exponentially small error estimate. Plugging in the estimate
for $s_n$, we obtain the desired result.
\end{proof}
If, as in the previous lemma, a polynomial $1-q(t)$ has a
factorization of the form $(1-\alpha t) \prod_{i=1}^d (1-\alpha_i
t)^{j_i}$ where $j_i \geq 1$ and $\alpha > |\alpha_i|$ for all $i$
then we will call $\alpha$ the {\em Perron value} of $1-q(t)$. If $q
\in t \integers_+[t]$ then $1-q(t)$ has such a factorization as long
as the degrees in which nonzero coefficients occur are relatively
prime.
For the remainder of the paper, suppose $\Lambda = \spectrum$
satisfies the Boyle-Handelman conditions for $\integers$ and $1-p(t) =
\prod_{i=1}^d (1-\lambda_i t)$. As noted in the Introduction, one can
produce a primitive matrix $A$ with entries in $\integers_+$ such that
$\det({\rm I}-At) = 1-p(t)$ if and only if there is a primitive
polynomial matrix $A(t)$ with entries in $t\integers_+[t]$ such that
$\det({\rm I}-A(t)) = 1-p(t)$ (see~\cite{B:matexp} for details). Thus
to prove the remaining direction of the main theorem it suffices to
show that there exist polynomials $q_j \in t \integers_+[t]$ and a
power series $r \in t\integers_+[[t]]$ such that the hypothesis of the
following are satisfied.
\begin{lemma}[Main Reduction]
\label{thm:reduction}
Let $p \in \integers[t]$.
Suppose there exist polynomials
$q_1,q_2,\ldots ,q_m \in t \integers_+[t]$ and a formal power series
$r \in t\integers_+[[t]]$ such that
\begin{enumerate}[{\rm (1)}]
\item there is a Perron value $\alpha$ for the polynomial
$\prod_{j=1}^m (1-q_j(t))$, \label{asump1}
\item $1-p(1/\alpha)<0$,\label{asump2}
\item $1-p(t) = (1-r(t))\prod_{j=1}^m (1-q_j(t))$ in the ring of
formal power series.
\end{enumerate}
Then there exists a
matrix $A(t)$ with entries in $t\integers_+[t]$ such that
$$\det({\rm I}-A(t)) = 1-p(t).$$
\end{lemma}
\begin{proof}
Assume that the polynomials $q_i$ are numbered so that $1/\alpha$ is a
root of the first polynomial $1-q_1(t)$. By
Lemma~\ref{lem:asymptotic}, and hypotheses~\ref{asump1}
and~\ref{asump2} there is a $N>0$ such that for all $1\leq k \leq m$,
the $n$th coefficient of $(1-p(t))\prod_{j=1}^k (1-q_j(t))^{-1}$ is
negative for all $n > N$. Select this $N$ to exceed the degree of
$p(t)$ and the degree of all polynomials $q_j(t)$.
Proceeding by induction, fix $0 \leq k < m$ and assume
\begin{equation}\label{eqn:indhyp}
\frac{1-p(t)}{\prod_{j=1}^k (1-q_j(t))} = 1-a_k(t)
- \sum_{i=1}^k \frac{b_i(t)}{\prod_{j=i}^k (1-q_j(t))}
\end{equation}
where $a_k(t)$ is a polynomial of degree $2N$ and the $b_i(t)$'s are
polynomials in $t^{2N+1}\integers_+[t]$.
The above clearly holds for $k=0$, the
base step of our induction.
Let $a_{k+1} \in t\integers[t]$ where $1 - a_{k+1}(t)$ is the
sum of the first $2N$ terms of $(1-p(t))\prod_{j=1}^{k+1}
(1-q_j(t))^{-1}$. Let $b_{k+1}(t)$ be the polynomial such that
\begin{equation*}
1-a_k(t) = (1 - a_{k+1}(t))(1-q_{k+1}(t)) -b_{k+1}(t).
\end{equation*}
Notice that all coefficients of $b_{k+1}(t)$ in degrees $2N$ and less
are zero. In degrees greater than $2N$, the coefficients of
$b_{k+1}(t)$ are nonnegative since they must cancel with the
coefficients of $a_{k+1}(t) q_{k+1}(t)$.
We plug the above expression for $1-a_k(t)$ into
equation~\ref{eqn:indhyp} and divide both sides by
$(1-q_{k+1}(t))$. We obtain the equation
\begin{equation*}
\frac{1-p(t)}{\prod_{j=1}^{k+1} (1-q_j(t))} = 1-a_{k+1}(t)
- \sum_{i=1}^{k+1} \frac{b_i(t)}{\prod_{j=i}^{k+1} (1-q_j(t))}.
\end{equation*}
Thus, by induction we have
\begin{equation}
1-p(t) = (1- a_m(t))\prod_{j=1}^{m} (1-q_j(t))
- \sum_{i=1}^{m} \left[b_i(t)
\prod_{j=1}^{i-1} (1-q_j(t)) \right]
\label{polyform}
\end{equation}
where the degree of $a_m$ is $2N$ and $b_i \in t^{2N+1}
\integers_+[t]$ for all $i$. But by the hypotheses of the lemma,
$a_m(t)$ is equal to the first $2N$ terms of $r(t)$, therefore all of
the coefficients of $a_m(t)$ are nonnegative.
Now let $A(t)$ be the following polynomial matrix over $t
\integers_+[t]$.
\begin{equation*}
A(t) = \begin{pmatrix}
a_m(t) & 1& 0& \ldots & 0 \\
b_m(t) & q_m(t)& 1& \ddots &\vdots \\
b_{m-1}(t) & 0& q_{m-1}(t)& \ddots & 0 \\
\vdots & \vdots & \ddots& \ddots & 1 \\
b_1(t) & 0 & \ldots& 0 & q_1(t)
\end{pmatrix}.
\end{equation*}
Using equation~\ref{polyform}, we find $\det({\rm I}-A(t)) = 1-p(t)$.
In order to have all entries of $A(t)$ in $t\integers_+[t]$, we may
replace each occurrence of a 1 with a $t$ and each $b_i(t)$ with
$b_i(t)/ t^{m+1-i}$.
\end{proof}
How do we find a factorization of $1-p(t)$ as in the Main Reduction
Lemma? We first note that for the polynomial $1-p(t)$ factors into an
infinite product
\begin{equation}
1-p(t) = \prod_{i=1}^{\infty} (1-t^i)^{o(i)}
\label{eqnfact}
\end{equation}
where $o(i) =
\nettrace[i] (\Lambda)/i$. To see this, take
the logarithm of both sides of equation~\ref{eqnfact} and compare
$i$th coefficients of the resulting power series. We obtain the
formula $tr(\Lambda^i) = \sum_{k|i} k o(k)$. Noting the relation
$tr(\Lambda^i) = \sum_{k|i} tr_k(\Lambda)$, we obtain $o(i) =
tr_i(A)/i$ by induction.
As we will see, we can choose an $n_0$ so that the coefficients of the
power series $(1-p(t))\prod_{i=1}^{n_0} (1-t^i)^{-o(i)}$ are
non-positive up to an arbitrarily high degree. However, as we saw in
Lemma~\ref{lem:asymptotic} this will not give the non-positivity for
all nonzero term coefficients if for example, $1-p(1) >0$. In general,
we are forced to introduce an additional factor $1-q(t)$ with an
appropriate Perron value to control the coefficients in high
degree.
We conclude this section with the outlines of the two different
arguments we will use to determine the sign of coefficients of
$1-p(t)$ times a power series. Let $\lambda$ denote the candidate
Perron eigenvalue $\lambda = \lambda_1$. Let $C(t) =
\sum_{i=0}^{\infty} c_it^i$ denote an arbitrary power series with $c_i
\geq 0$ for all $i$.
\begin{argument}[Differences Argument]
If $( c_{n-1}\lambda - c_n )$ is positive and
large compared to
$\big| \left( c_{n-i} \lambda^i -
c_{n-i+1} \lambda^{i-1} \right)
- \left( c_{n-i+1} \lambda^{i-1}
- c_{n-i+2} \lambda^{i-2} \right) \big|$
for $i=0,1,\ldots , d$ then the $n$th coefficient of $(1-p(t))C(t)$ is
negative.
\end{argument}
Let $D_i$ denote the first order differences, $D_i = c_{n-i} \lambda^i
- c_{n-i+1} \lambda^{i-1}$ for $1 \leq i \leq d$. Then
\begin{equation*}
c_{n-i} \lambda^i = c_n + \sum_{j=1}^{i} D_j
= c_n + i D_1 + \sum_{j=1}^{i} (i-j) (D_{j+1} - D_j).
\end{equation*}
Our assumption is that the second order differences
$(D_{j+1}-D_j)$ are small in comparison to the first order difference
$D_1$. Ignoring the second order differences,
the $n$th coefficient of $(1-p(t)) \sum_{n=1}^{\infty} c_nt^n$
is
$$c_n - \sum_{i=1}^d p_i c_{n-i}
\approx c_n \left(1- \sum_{i=0}^d p_i \lambda^{-i}\right) -
D_1 \sum_{i=0}^d i p_i \lambda^{-i} = -D_1 p'(1/\lambda).$$
We know that $p'(1/\lambda) >0$ by the Perron condition. Therefore,
if the second order differences are a small fraction of
the $D_1 = (\lambda c_{n-1} - c_n)$ then we will obtain an
upper bound on the $n$th coefficient of $(1-p(t))C(t)$ of the form
$-K(\lambda c_{n-1} - c_n)$ where $K>0$ is a constant.
For the second argument, fix $\lambda' \in (|\lambda_2|,
\lambda)$ such that $t \in [1/\lambda, 1/\lambda')$
implies $1-p(t) < 0$
and $p'(t)> 0$.
\begin{argument}[Ratio Argument]
If there exists a number $\alpha \in (\lambda',\lambda)$ such that
$|c_{n-i}/c_n - \alpha^{-i} |$ is small compared to
$|\alpha - \lambda|$ for $i= 1,2,\ldots ,d$ then the $n$th coefficient
of $(1-p(t))C(t)$ is negative.
\end{argument}
This follows since the $n$th coefficient of $(1-p(t))C(t)$
is equal to $c_n - \sum_{i=0}^d p_i c_{n-i}$. Factoring out $c_n$,
we obtain
$$n\text{th coefficient } = c_n \left(1- \sum_{i=0}^d p_i
(c_{n-i}/c_n)\right).$$ If all ratios
$c_{n-i}/c_n$ are sufficiently close to $\alpha^{-i}$ then this $n$th
coefficient will be close to $c_n (1-p(1/\alpha))<0$.
More specifically, since $-p'(1/\lambda)<0$, there is a constant $K>0$
such that $1-p(t) \leq -K |\lambda - 1/t|$ for $t \in (1/\lambda,
1/\lambda')$. So if the difference $|c_{n-i}/c_n -\alpha^{-i}|$ is
some small fraction of $|\lambda - \alpha|$ then we will obtain an
upper estimate on the $n$th coefficient of $(1-p(t))C(t)$ of the form
$ - Kc_n |\alpha - \lambda|/2$.
% Example
\section{Example}
\label{sec:examples}
The polynomial $1-p(t)=1-4t+6t^2-6t^3$ has a factorization
$\prod_{i=1}^3
(1-\lambda_it)$ where $\lambda_1 \approx 2.57474$ and $\lambda_2 =
\overline{\lambda_3} \approx .71263 + 1.35000 i$. Lind and
Marcus~\cite[chapter 11]{LM} give $(\lambda_1, \lambda_2, \lambda_3)$
as an example of an $n$-tuple satisfying the Boyle-Handelman
conditions, but one for which there was no known primitive matrix with
the corresponding nonzero spectrum. We will need a polynomial matrix
$A(t)$ of at least size $4 \times 4$ to realize $1-p(t)$.
To see this, suppose $A(t)$ is a $3 \times 3$ matrix with entries in
$t \integers_+[t]$,
$$A(t) = \begin{pmatrix}a(t) & b(t) & c(t)\\
d(t) & e(t) & f(t)\\
g(t) & h(t) & i(t)\\ \end{pmatrix} $$
such that $\det(I-A(t)) = 1-p(t)$. Equating coefficients,
$a_1 + e_1 + i_1 = 4$ and $a_1e_1 + a_1i_1 + e_1i_1 \geq 6$.
This is impossible since all coefficients are nonnegative integers.
Following our factorization scheme, we begin by dividing $1-p(t)$ by
powers of $1-t^i$. The additional factor $1-q(t)$ will not be
necessary here since $1-p(1)<0$. A calculation shows that for $j =
1,2,3$ the coefficients of the power series $(1-p(t))(1-t)^{-j}$ are
non-positive in degrees 3 to 6. Moreover, the coefficients of
$(1-p(t))(1-t)^{-3}$ are non-positive in degrees 1 to 6. Following the
scheme in the Main Reduction Lemma, we produce the matrix
$$
A(t) = \begin{pmatrix}
t+2t^3+7t^4+15t^5 & t & 0 & 0 \\
15 t^5 & t & t & 0 \\
8 t^4 & 0 & t & t \\
3 t^3 & 0 & 0 & t \\
\end{pmatrix}$$ with $\det(I-A(t)) = 1-4t+6t^2-6t^3$.
Notice that $A(t)^3$ has no nonzero entries i.e., $A(t)$ is
primitive. To point out the advantages of the polynomial matrix
approach, we note that the primitive integer matrix corresponding to
the above is $194 \times 194$.
% Polyrange
\section{Initial estimates on $S(t)$}
\label{sec:polyrange}
For the remainder of the paper, fix $\spectrum$ satisfying the
Boyle-Handelman conditions and let $1-p(t) = \prod_{i=1}^d
(1-\lambda_it)$. Fix $n_0$ and let $S(t) = \sum_{n=1}^{\infty} s_nt^n
= \prod_{i=1}^{n_0} (1-t^i)^{-o(i)}$.
In this section, we show that for any $k \geq 1$, if $n_0$ is
sufficiently large then the $n$th coefficient of the power series
$S(t)(1-p(t))$ will be non-positive for $n_0 < n \leq (n_0)^k$
(Polynomial Range Lemma). We begin by giving estimates for $s_n$ when
$n_0 < n \le 2n_0 +
\log^2 n_0$.
We use the term ``constant'' in the following lemmas to mean a number
which is independent of the choice of $n_0$.
\begin{lemma}
\label{lem:s1}
There exists a constant $K>0$ such that
if $n_0$ is sufficiently large and $n_0 < n \le n_0 + \log^2 n_0$
then
\begin{equation*}
\left|\frac{s_{n+1}}{\lambda s_n} - 1\right|< K \frac{\log^2 n_0}{ n_0}.
\end{equation*}
\end{lemma}
\begin{proof}
We have the following expansions of $S(t)$.
\begin{equation*}
S(t) = \prod_{i=1}^{n_0} (1-t^i)^{-o(i)}
= \prod_{i=n_0+1}^{\infty} (1-t^i)^{o(i)} / (1-p(t)).
\end{equation*}
Let $c_n$ denote the $n$th coefficient of $(1-p(t))^{-1}$.
If $n_00$ such that
\begin{equation*}
\left|c_n \lambda^{-n} - a \right|< C_1 e^{-c n}
\end{equation*}
for all $n>0$. Recalling the relationship between $o(n)$ and the $n$th
net trace, we have constants $C_2, c >0$ such that
\begin{equation*}
\left|o(n)\lambda^{-n} - 1/n\right| < C_2 e^{-c n}
\end{equation*}
for all $n>0$. In the estimates that follow, these will allow us to
replace $c_n \lambda^{-n}$ with $a$ and $o(n) \lambda^{-n}$ with $1/n$.
Using these estimates, if $n_0 < n \le n_0+\log^2 n_0$ then
\begin{equation*}
\begin{split}
\lambda^{-n} \sum_{i=n_0+1}^n c_{n-i} o(i)
< C_3 \log^2 n_0 /n_0
\end{split}
\end{equation*}
for some constant $C_3>0$.
Therefore, the ratio $s_{n+1}/\lambda s_n$ is within a constant times
$\log^2n_0/n_0$ of the ratio $\lambda^{-n-1} c_{n+1}/\lambda^n c_n$.
Applying our estimates on $c_n$ a second time, we find a constant
$K>0$ such that
\begin{equation*}
\left| \frac{s_{n+1}}{\lambda s_n} - 1 \right| < K \frac{\log^2
n_0}{n_0}.
\end{equation*}
\end{proof}
\begin{lemma} \label{lem:s2}
There exist constants $k_1>k_2>0$ such that if $n_0$ is
sufficiently large and $n_0+\log^2 n_0 < n \le 2n_0 +\log^2 n_0$ then
\begin{equation*}
\left(1-\frac{k_1}{n_0}\right) < \frac{s_{n+1}}{\lambda s_n}
< \left(1-\frac{k_2}{n_0}\right).
\end{equation*}
\end{lemma}
\begin{proof}
Assume $n_0n_0\\i+j\leq n}}o(i)o(j)c_{n-i-j}.
\end{equation*}
To obtain our estimates we will examine the difference of scaled
coefficients $|s_n \lambda^{-n}-s_{n+1} \lambda^{-(n+1)}|$ in the
above formula for $s_n$.
Assume that $n_0 + \log^2 n_0 < n \le 2n_0 + \log^2 n_0$.
>From our estimates on $c_i$ and $o(i)$ we obtain
estimates for the last two terms of the form
\begin{equation*}
\lambda^{-n} \sum_{i=n_0+1}^{n/2}\binom{o(i)}{2}c_{n-2i}
< C_1 \left(\frac{\log^2 n_0}{n_0}\right)
\end{equation*}
and
\begin{equation*}
\lambda^{-n} \sum_{\substack{i,j>n_0\\i+j\leq n}}
o(i)o(j)c_{n-i-j} < C_2 \left(\frac{\log^4 n_0}{n_0^2}\right)
\end{equation*}
for constants $C_1,C_2>0$. To obtain the above, notice each term in
the above two summations is less than a constant times $1/n_0^2$.
Finally, we split the difference of the remaining summation terms into
three parts. For each part we will use $c_n \lambda^{-n} \approx a$
and $o(n) \lambda^{-n} \approx 1/n$ with errors which are
exponentially small in $n_0$. Let $n_1 = [\log^2 n_0]$, where $[x]$ is
the greatest integer function. For the first part,
\begin{equation*}
\left|\sum_{i=n_0+1}^{n-n_1} \frac{o(i)}{\lambda^i}
\left( \frac{c_{n-i}}{\lambda^{n-i}}
- \frac{c_{n+1-i}}{\lambda^{n+1-i}}\right)\right|
< C_3 e^{-c \log^2 n_0}
\end{equation*}
for some constants $C_3,c >0$.
The second part is estimated as
\begin{equation*}
\left| \sum_{i=n-n_1+1}^n \frac{c_{n-i}}{\lambda^{n-i}}
\left( \frac{o(i)}{\lambda^i} -
\frac{o(i+1)}{\lambda^{i+1}} \right)\right|
< C_4 \frac{\log^2 n_0}{n_0^2}
\end{equation*}
for some constant $C_4>0$. This leaves only one term
\begin{equation*}
c_{n_1} o(n+1-n_1)\lambda^{-n}
= \left(\frac{a}{n+1-\log^2 n_0}\right)\left( 1 \pm C_5 e^{-c \log^2
n_0}
\right).
\end{equation*}
This last term is the largest in the scaled difference
$s_n\lambda^{-n} - s_{n+1}\lambda^{-(n+1)}$. For $n_0 + \log^2 n_0 <
n \le 2n_0 + \log^2 n_0$, its ratio with $1/n_0$ is bounded between
two positive constants. Therefore, the difference of scaled $s_n$
terms is within two constants of $1/n_0$.
Since the terms $s_n\lambda^{-n}$ are uniformly
bounded in this range we can find two constants $k_1>k_2>0$ such that
if $n_0$ is chosen sufficiently large and $n_0+\log^2 n_0 < n \le 2n_0
+ \log^2 n_0$ then
\begin{equation*}
\left(1-\frac{k_1}{n_0}\right) < \frac{s_{n+1}}{\lambda s_n} <
\left(1-\frac{k_2}{n_0}\right).
\end{equation*}
\end{proof}
To get further results for $S(t)$, we will approximate the coefficients
of $S(t)$ with the coefficients of $\exp(L(t))$ where $L(t)$ is
defined as follows. Let$\tau_n = \sum_{i=1}^d (\lambda_i)^n$,
\begin{equation*}
L(t) = \sum_{i=1}^{n_0} \left(\tau_i /i\right)t^i \quad \quad
L'(t) = \log(S(t)) - L(t).
\end{equation*}
To obtain formulas for $L(t)$ and $L'(t)$ we notice
\begin{equation*}
\begin{split}
\log(S(t)) &= \log\left(\prod_{i=1}^{n_0} (1-t^i)^{-o(i)} \right) \\
&= - \sum_{i=1}^{n_0} o(i) \log(1-t^i)\\ &= \sum_{n=1}^{n_0}
\frac{\tau_n t^n}{n} + \sum_{n=n_0+1}^{\infty} \sum_{\substack{i|n\\
i\leq n_0}} \frac{i o(i)}{n} t^n.
\end{split}
\end{equation*}
The above follows by expanding $\log(1-x)$ into a power series and
gives us a formula for the coefficients $L^\prime_n$. The next lemma
gives estimates on the terms $L'_n$. This will help produce estimates
on how well the coefficients of $S(t)$ approximate those of $\exp
(L(t))$.
\begin{lemma}
\label{lem:L'}
There exists a constant $K > 0$ such that
if $n_0$ is sufficiently large and $n > n_0$ then
\begin{enumerate}[{\rm (1)}]
\item $L'_n \leq K \lambda^{n/2}$
\item $L'_n \leq K \lambda^{n_0}$
\item $[\exp L'(t)]_n \leq K \lambda^{2n/3}$
\end{enumerate}
\end{lemma}
\begin{proof}
If $n> n_0$ our estimates on $o(i)$ give
\begin{equation*}
L'_n = \sum_{\substack{i|n\\ i \leq n_0}} io(i)/n
\leq \sum_{i=1}^{n/2} io(i)/n < C_1 \lambda^{n/2}
\end{equation*}
for some constant $C_1>0$
and
\begin{equation*}
L'_n = \sum_{\substack{i|n\\ i \leq n_0}} io(i)/n
\leq \sum_{i=1}^{n_0} io(i)/n < C_2 \lambda^{n_0}
\end{equation*}
for some constant $C_2 >0$.
For the third estimate, plug in the quantity $\lambda^{-2/3}$ into the
function $L'(t)$.
\begin{equation*}
L'(\lambda^{-2/3}) = \sum_{n=n_0+1}^{\infty} L_n' \lambda^{-2n/3}
< \sum_{n=n_0+1}^{\infty} C_1 \lambda^{n/2} \lambda^{-2n/3}
< C_3 \lambda^{-n_0/6}
\end{equation*}
for some constant $C_3>0$.
Therefore, if we take $n_0$ sufficiently large,
$\exp(L'(\lambda^{-2/3}))$ will be close to one. Let $d_n$ be the
$n$th coefficient of $\exp(L'(t))$. For sufficiently large $n_0$,
\begin{equation*}
2 > \exp(L'(\lambda^{-2/3}))
= 1+\sum_{n=1}^{\infty} d_n \lambda^{-2n/3}.
\end{equation*}
Since all $d_n$ are nonnegative, this implies $d_n < \lambda^{2n/3}$
for all $n$.
\end{proof}
Let
\begin{equation*}
E(t)= \exp(L(t)) = \sum_{n=0}^{\infty} e_n t^n.
\end{equation*}
We will show in the next two lemmas that the
ratio $s_n/e_n$ is approximately one for
$n_0 + \log^2 n_0 < n \le 2n_0 + \log^2 n_0$.
\begin{lemma}
\label{lem:s3}
There exists a constant $K >0$ such that if $n_0$ is sufficiently large,
$n_0 + \log^2 n_0 < n \le 2n_0 + \log^2 n_0$ and
$0 \leq m < n$ then
\begin{equation*}
\frac{s_m}{s_n}< K \lambda^{m-n}.
\end{equation*}
\end{lemma}
\begin{proof}
If $m > n_0 + \log^2 n_0$ then using Lemma~\ref{lem:s2},
\begin{equation*}
\frac{\lambda^{n-m} s_m}{ s_n}
< \left(1 - \frac{k_1}{n_0}\right)^{m-n}
< \left(1 - \frac{k_1}{n_0}\right)^{-n_0}.
\end{equation*}
This upper bound above approaches $e^{k_1}$ as $n_0$ goes to infinity
so we obtain a uniform bound on these ratios.
Let $n_1 = [\log^2 n_0]$.
If $n_0 < m < n_0 + n_1$ then using
Lemma~\ref{lem:s1} we obtain a constant $C_1 >0$ such that
\begin{equation*}
\frac{\lambda^{n_0+n_1-m} s_m}{s_{n_0+n_1}}
<(1 + C_1 \log^2 n_0 /n_0)^{\log^2 n_0}.
\end{equation*}
This upper bound approaches 1 as $n_0$ goes to infinity, so these
ratios are also uniformly bounded.
If $m \leq n_0$ then there is a uniform bound on
$\lambda^{n_0-m} s_m/{s_{n_0}}$ since in this range $s_m$ is equal to
the $m$th coefficient of the series $(1-p(t))^{-1}$. Recall that the
terms of $(1-p(t))^{-1}$ look like $a \lambda^n (1 \pm C_2 e^{-cn})$
with
$C_2, c>0$.
The product of the bounds for each region will be a constant $K>0$ which
uniformly bounds $\lambda^{n-m} s_m/s_n$ for all $m,n$ in the
hypothesis.
\end{proof}
\begin{lemma}
\label{lem:es1}
There exists a constant $K >0 $ such that if $n_0$ is sufficiently
large and $n_0+\log^2 n_0< n \le 2n_0+\log^2 n_0$ then
\begin{equation*}
\left| \frac{s_n}{e_n} -1 \right| < K \lambda^{-n_0/3}
\end{equation*}
\end{lemma}
\begin{proof}
Recall $E(t) = S(t) \exp(-L'(t))$. Therefore
\begin{equation*}
e_n = s_n + \sum_{i=n_0+1}^n s_{n-i} [\exp( -L'(t))]_i
\end{equation*}
>From the estimates on $L'(t)$, there is a constant $C_1>0$ such that
\begin{equation*}
|e_n/s_n -1|\le \sum_{i=n_0+1}^n (s_{n-i}/s_n) \big| [\exp(
-L'(t))]_i\big| < \sum_{i=n_0+1}^n C_1 \lambda^{-i}
\lambda^{2i/3}
\end{equation*}
This gives an upper bound of the form
$K \lambda^{-n_0/3}$ for some $K >0$.
\end{proof}
This shows that at least initially, $e_n$ will give a good
approximation for $s_n$. To continue we will examine the $e_n$ terms.
Notice that from $S(t) = E(t) \exp(L'(t))$, we get
\begin{equation*}
e_n \leq s_n \leq e_n + \sum_{i=n_0}^{n} e_{n-i} \lambda^{2i/3}.
\end{equation*}
Therefore, as long as the ratios $e_{n+1}/e_n$ are at least
$\lambda^{(\epsilon + 2)/3}$ for some $\epsilon$, we will have an
estimate on $s_n/e_n - 1$ which is exponentially small in $n_0$.
To obtain estimates on $e_n$, we will make heavy use of the following
recursive formula which we get from $\frac{d}{dt}E(t) =
\left( \sum_{i=1}^{n_0} \tau_i t^{i-1} \right) E(t)$,
\begin{equation*}
n e_n = \sum_{i=1}^{n_0} \tau_i e_{n-i}.
\end{equation*}
The key to the next estimates on $e_n$ will be to use this recursion
formula to look at the ratio of terms $e_{n+1}/e_n$ in the following
way
\begin{equation*}
\begin{split} \frac{e_{n+1}}{e_{n}} &= \left( \frac{n}{n+1} \right)
\frac{\sum_{i=1}^{n_0} \tau_i e_{n+1-i}}{\sum_{j=1}^{n_0} \tau_j
e_{n-j}}\\ &= \left( \frac{n}{n+1} \right) \sum_{i=1}^{n_0} \left(
\frac{\tau_i e_{n-i}}{\sum_{j=1}^{n_0} \tau_j e_{n-j}} \right)
(e_{n+1-i}/e_{n-i}). \end{split}
\end{equation*}
In this way the ratio $e_{n+1}/e_{n}$ is $n/(n+1)$ times a weighted
average of the previous $n_0$ ratios $e_{n+1-i}/e_{n-i}$. We proceed
to find upper and lower bounds on ratios of consecutive $e_n$ terms.
\begin{lemma}
\label{lem:e1}
There exists a constant $k_3 > 0$ such that
if $n_0$ is sufficiently large and $n_0+ \log^2 n_0 < n$ then
\begin{equation*}
\frac{e_{n+1}}{\lambda e_{n}} < \left(1-\frac{k_3}{n_0}\right)
\end{equation*}
and
\begin{equation*}
\frac{e_{n+1}}{\lambda e_{n}} < \left( \frac{3n_0}{n} \right)^{1/n_0}
\end{equation*}
\end{lemma}
\begin{proof}
By Lemmas~\ref{lem:es1} and~\ref{lem:s2}, there exists a constant $C_1
> 0$ such that if $n_0 + \log^2 n_0 < n \le 2n_0 + \log^2 n_0$ then
\begin{equation*}
\begin{split}
\frac{e_{n+1}}{\lambda e_{n}} &< \frac{s_{n+1}}{\lambda s_{n}} \left(1
+ C_1 \lambda^{-n_0/3}\right)\\ &< \left( 1 - \frac{k_1}{n_0}\right)
\left(1 + C_1 \lambda^{-n_0/3}\right)\\ &<
\left(1-\frac{k_3}{n_0}\right)
\end{split}
\end{equation*}
for some $k_3>0$.
Now by the recursion formula, our upper bound on $e_{n+1}/(\lambda
e_n)$ for this string of $n_0$ consecutive ratios is an upper bound
for all subsequent ratios.
For the second estimate, let $r_n$ represent the ratio
$e_{n+1}/(\lambda e_n)$ and $w_i$ the weight so that $r_n =
n/(n+1) \sum_{i=1}^{n_0} w_i r_{n-i}$.
Fix $n > 2n_0 +\log^2 n_0$. Let $m_1$ be the index of the largest of
the previous $n_0$ ratios i.e., $r_{m_1} = \max_{1\leq i \leq
n_0}r_{n-i}$. Notice that
\begin{equation*}
r_n \leq \left(\frac{n}{n+1}\right) r_{m_1}.
\end{equation*}
As long as $m_i > 2n_0+\log^2 n_0$ define $m_{i+1}$
to be the index
of the largest ratio $r_j$ where $m_i-n_0 \leq j \leq m_i-1$. In
other words, $r_{m_{i+1}} = \max_{1\leq j \leq n_0} r_{m_i-j}$.
Using the fact that $r_i < 1$ for all $i$, by induction we get
\begin{equation*}
r_n \leq \left(\frac{n}{n+1}\right)
\left(\frac{m_1}{m_1+1} \right)
\left( \frac{m_2}{m_2+1} \right) \cdots
\left( \frac{m_N}{m_N+1} \right)
\end{equation*}
for some $N$ with $n_0 + \log^2 n_0 < m_N \le 2 n_0 + \log^2 n_0$.
To obtain an upper bound, let $q = [n/n_0]$.
Take $q-1$ of the above factors $m_i/(m_i+1)$, one
each between $in_0$ and $(i+1)n_0-1$ for $i=2,3, \ldots, q$.
For $i n_0 \leq n \leq (i+1)n_0-1$ we see
\begin{equation*}
\frac{n}{(n+1)} \leq \frac{(i+1)n_0-1}{(i+1)n_0}.
\end{equation*}
This gives an upper bound of
\begin{equation*}
\begin{split} \log(r_n) & \leq \log \left( \prod_{i=3}^{(q+1)}
\left(1-\frac{1}{in_0}\right) \right)\\ &= \sum_{i=3}^{(q+1)} \log
\left(1-\frac{1}{in_0}\right) \\ &< - \sum_{i=3}^{(q+1)}
\frac{1}{in_0} \\ &< - (1/n_0) \log(n/(3n_0)) \end{split}
\end{equation*}
Exponentiating, we obtain our upper bound for $r_n$
\begin{equation*}
r_n < \left(\frac{3n_0}{n}\right)^{1/n_0}
\end{equation*}
\end{proof}
We use a similar technique to establish a lower bound for the ratio
$e_{n+1}/(\lambda e_{n})$.
\begin{lemma}
\label{lem:e2}
There exists a constant $b >0$ such that if $r>0$ is sufficiently small
and $n_0$ is sufficiently large then
$n_0+\log^2 n_0 < n \le e^{r n_0}$ implies
\begin{equation*}
\frac{e_{n+1}}{(\lambda e_{n})}> \left(\frac1n\right)^{b/n_0}.
\end{equation*}
\end{lemma}
\begin{proof}
We obtain a lower bound for the initial coefficients as we did in
Lemma~\ref{lem:e1}. If $n_0$ is sufficiently large and $n_0+\log n_0
< n \le 2n_0 + \log n_0$ then
\begin{equation*}
\frac{e_{n+1}}{\lambda e_{n}}> \frac{s_{n+1}}{\lambda s_{n}}
\left(1 - C_1 \lambda^{-n_0/3}\right)
> \left(1-\frac{k_4}{n_0}\right)
\end{equation*}
for some constant $k_4 >0$.
Suppose we have chosen $n_0$ large enough to ensure
\begin{equation*}
(1-k_4/n_0)^{n_0/3} > 1/n_0.
\end{equation*}
The left hand side approaches $e^{-k_4/3}$ so this is true
for large $n_0$. Then for $n_0 +\log^2 n_0 < n \le 2n_0 + \log^2 n_0$,
\begin{equation*}
e_{n+1}/(\lambda e_{n}) >
(1-k_4/n_0) > (1/n_0)^{3/n_0}.
\end{equation*}
We will show by induction that this is a lower bound for
$e_{n+1}/(\lambda e_{n})$ for all $n> 2n_0 + \log^2 n_0$.
Fix $n > 2n_0 + \log^2 n_0$ and assume $e_{m+1}/(\lambda e_{m}) \geq
(1/m)^{3/n_0}$ for all $(n-n_0) \le m < n$. Then using the notation
of the previous lemma,
\begin{equation*}
r_n = \left( \frac{n}{n+1} \right) \sum_{i=1}^{n_0} w_i r_{n-i} \geq
\left( \frac{n}{n+1} \right)
\sum_{i=1}^{n_0} w_i \left( \frac{1}{n-i} \right)^{3/n_0}.
\end{equation*}
We would now like to replace all of the weights $w_i$ in the above
expression with $(1/n_0)$ making the weighted average into a flat
average. If doing so would produce a smaller estimate then the
following argument would finish the proof.
For sufficiently large $n_0$,
\begin{equation*}
\begin{split} \frac{1}{n_0} \sum_{i=1}^{n_0} \left(\frac{n}{n-i}
\right)^{3/n_0} &= \frac{1}{n_0} \sum_{i=1}^{n_0} \left(1 +
\frac{i}{n-i}\right)^{3/n_0} \\ &> \frac{1}{n_0} \sum_{i=1}^{n_0}
\left(1+\frac{3i}{n_0(n-i)}\right) \\ &> 1 + \frac{3}{n_0^2}
\sum_{i=1}^{n_0} \frac{i}{n} \\ &= 1 + \frac{3 n_0(n_0-1)}{2 n
n_0^2}\\ &> \frac{n+1}{n}. \end{split}
\end{equation*}
Rearranging,
\begin{equation*}
\left(\frac{n}{n+1}\right) \frac{1}{n_0}
\sum_{i=1}^{n_0}\left(\frac{1}{n-i}\right)^{3/n_0} >
\left(\frac{1}{n}\right)^{3/n_0}.
\end{equation*}
It remains then to examine the consequence of replacing $w_i$ with
$(1/n_0)$.
If the weights $w_i$ and the terms $(n-i)^{-3/n_0}$ are both
increasing in $i$ for all $i$, then the flat average is less than the
weighted average. The idea is that the weighted average puts more
weight on the biggest terms than does the flat average, therefore the
weighted average is more. (This is made precise in Lemma~\ref{lem:A4}.)
Recall that the weight $w_i$ is equal to $\tau_i
e_{n-i}/\sum_{j=1}^{n_0} \tau_j e_{n-j}$. The weights may not be
increasing for all $i$, but there is a constant $k$ such that for
sufficiently large $n_0$, the weights $w_i$ are increasing for $i \geq
k \log n_0$. This follows since there exist constants $C_1, c>0$ such
that for $i \geq k \log n_0$
\begin{equation*}
\frac{w_{i+1}}{w_i} =
\frac{\tau_{i+1}}{\lambda \tau_i}\frac{\lambda e_{n-i}}{e_{n-i-1}}
> \left(1 - C_1 e^{-ci}\right)\left(1-\frac{k_3}{n_0}\right)^{-1}
> 1 + \frac{k_3}{n_0} - \frac{C_1}{n_0^{ck}}
\end{equation*}
Let $n_1 =[k \log n_0]$ and
$W = \sum_{i=n_1}^{n_0} w_i$. By Lemma~\ref{lem:A4}
\begin{equation*}
\sum_{i=1}^{n_0} w_i r_{n-i}
\ge W \sum_{i=n_1+1}^{n_0}\frac{w_i}{W}
\left( \frac{1}{n-i} \right)^{3/n_0}
\ge \frac{W}{n_0- n_1} \sum_{i=n_1+1}^{n_0}
\left( \frac{1}{n-i} \right)^{3/n_0}.
\end{equation*}
We now wish to examine the difference between the term
above and $(1/n_0) \sum_{i=1}^{n_0} (n-i)^{-3/n_0}$ which we had
previously.
First we show that $W$ is approximately one.
\begin{equation*}
|W-1| = \sum_{i=1}^{n_1} w_i
= \sum_{i=1}^{n_1} \tau_i e_{n-i} / \sum_{i=1}^{n_0} \tau_i e_{n-i}.
\end{equation*}
Approximating the numerator, we have
$e_{n-i} \leq \lambda^{n_1-i} e_{n-n_1}$ for all $i\leq n_1$, and
$\lambda^{-i} \tau_i$ is uniformly bounded. Therefore,
\begin{equation*}
\begin{split}
\lambda^{-n} \sum_{i=1}^{n_1} \tau_i e_{n-i}
& \le C_2 \lambda^{n_1-n} e_{n-n_1} n_1
\end{split}
\end{equation*}
for some constant $C_2>0$.
Approximating the denominator, we use the fact that the terms $w_i$ are
increasing for $i \ge n_1$. Then
\begin{equation*}
\begin{split}
\lambda^{-n} \sum_{i=1}^{n_0} \tau_i e_{n-i}
& \ge \lambda^{-n} \sum_{i=n_1}^{n_0} \tau_i e_{n-i} \\
& \ge \lambda^{-n} \tau_{n_1} e_{n-n_1} (n_0-n_1)\\
& \ge C_3 \lambda^{n_1-n} e_{n-n_1} n_0
\end{split}
\end{equation*}
for some constant $C_3>0$.
Thus we get an estimate for $W$ of the form
\begin{equation*}
|W-1| \leq C_4 (n_1/n_0)
\end{equation*}
for some constant $C_4 >0$.
Using this, we get the following estimate.
\begin{equation*}
\left[\frac{W}{n_0-n_1} - \frac{1}{n_0}\right] \sum_{i=1}^{n_0}
\left( \frac{1}{n-i} \right)^{3/n_0} \leq C_5 (\log n_0/n_0)
\end{equation*}
for some constant $C_5>0$.
Finally, we get a constant $C_6 >0$ such that
\begin{equation*}
\begin{split}
r_n & = \sum_{i=1}^{n_0} w_i r_{n-i} \\ & \ge \frac{W}{n_0-\log n_0}
\sum_{i=\log n_0}^{n_0} \left( \frac{1}{n-i} \right)^{3/n_0}\\ & \ge
\frac{1}{n_0} \sum_{i=1}^{n_0} \left( \frac{1}{n-i} \right)^{3/n_0} -
C_6 (\log n_0/n_0) \\ & \ge n^{-3/n_0} - C_6 (\log n_0/n_0).
\end{split}
\end{equation*}
Fix $r>0$ and suppose $\hat{b} > 2 C_6 e^{3r}$.
If $n_0$ is sufficiently large and $n_0 < n \le e^{r n_0}$ then
\begin{equation*}
1 - C_6 n^{3/n_0} \frac{\log n_0}{n_0}
> 1 - \frac{\hat{b}\log n_0}{2n_0}> n_0^{-\hat{b}/n_0}
> n^{-\hat{b}/n_0}.
\end{equation*}
The above follows since for large $x$, we have $x^{k/x} \approx 1+k
\log x/x$. Letting $b = \hat{b}+3$, the inequality follows.
\end{proof}
We are now ready to show that the difference between the ratio
$s_n/e_n$ and 1 is exponentially small in $n_0$ for $n_0 < n \le
e^{rn_0}$.
\begin{lemma}
\label{lem:es2}
There exist constants $r>0$ and $K, k>0$ such that
if $n_0$ is sufficiently large and $n_0 < n \leq e^{r n_0}$ then
\begin{equation*}
\left|\frac{s_n}{e_{n}}- 1\right| < K e^{-k n}.
\end{equation*}
\end{lemma}
\begin{proof}
Assume $b>0$ and $00$
such that if $n_0$ is sufficiently large and
$n_0+\log^2 n_0 < n \leq n_0^k$ then
\begin{equation*}
\frac{K_1}{n_0}< \left( \frac{\lambda e_{n}}{e_{n+1}} - 1\right) <
\frac{K_2 \log(n_0)}{n_0}
\end{equation*}
\end{lemma}
\begin{proof}
>From Lemma~\ref{lem:e1} we have $k_3>0$ such that
\begin{equation*}
\frac{\lambda e_{n}}{e_{n+1}}
> \left( 1-\frac{k_3}{n_0} \right)^{-1} > 1+ \frac{K_1}{n_0}
\end{equation*}
for some constant $K_1>0$.
For the other inequality, for sufficiently large $n_0$ we can choose
a constant $K_2 >0$ such that
\begin{equation*}
\frac{\lambda e_{n}}{e_{n+1}} 0$ such that if $n_0$
is sufficiently large and $2n_0+\log^2 n_0 < n \leq n_0^k$ then
\begin{equation*}
\left| \left( \frac{\lambda e_{n+1}}{e_{n+2}} - 1 \right) -
\left( \frac{\lambda^2 e_{n}}{e_{n+2}} -
\frac{\lambda e_{n+1}}{e_{n+2}}\right) \right|
< K \left(\frac{\log n_0 }{n_0^2}\right).
\end{equation*}
\end{lemma}
\begin{proof}
Fix $n$ and let $R_i$ denote $\lambda^{n+2-i} e_i/e_{n+2}$.
>From the recursion formula on $e_n$
\begin{equation*}
R_n = \frac{1}{n} \sum_{i=1}^{n_0} \lambda^{-i} \tau_i R_{n-i}.
\end{equation*}
Using this we get
\begin{equation*}
\begin{split}
\left( R_{n+1} - 1 \right)&
- \left( R_{n} - R_{n+1} \right) \\
&= \frac{1}{n} \sum_{i=1}^{n_0}
\lambda^{-i} \tau_i \left[(R_{n+1-i}- R_{n+2-i})
- (R_{n-i}- R_{n+1-i})\right] \\
&\qquad - \frac{2}{n(n+1)}
\sum_{i=1}^{n_0} \lambda^{-i} \tau_i
\left[ R_{n+1-i} - R_{n+2-i}\right]\\
&\qquad + \frac{2}{n(n+1)(n+2)} \sum_{i=1}^{n_0}
\lambda^{-i} \tau_i R_{n+2-i}
\end{split}
\end{equation*}
Let $D_i = R_{i}-R_{i+1}$. By the previous lemma, each $D_i$ is less
than a constant times $\log n_0/n_0$. We also know that the terms
$\lambda^{-i} \tau_i$ are exponentially close to one. These estimates
give the following.
For some constant $C_1>0$ we get an upper bound on the first term
\begin{equation*}
\begin{split}
\frac{1}{n} &\left| \sum_{i=1}^{n_0} \lambda^{-i}
\tau_i (D_{n+1-i} - D_{n-i}) \right|\\
& = \frac{1}{n} \left|\lambda^{-1} \tau_1 D_{n}
+ \sum_{i=2}^{n_0} (\lambda^{-i} \tau_i-\lambda^{-i+1}
\tau_{i-1})D_{n+1-i} - \lambda^{-n_0} \tau_{n_0}D_{n-n_0}
\right|\\
& 0$ we get an upper bound on the second of the
form
\begin{equation*}
\frac{2}{n(n+1)}
\left| \sum_{i=1}^{n_0} \lambda^{-i} \tau_i D_{n-i}\right|
\le C_2 \frac{\log n_0}{n_0^2}.
\end{equation*}
Using the fact that the $R_i$'s are bounded, for some
$C_3>0$ we get an upper bound of the form
\begin{equation*}
\frac{2}{n(n+1)(n+2)} \sum_{i=1}^{n_0}
\lambda^{-i} \tau_i R_{n-i}
\le C_3 \frac{1}{n_0^2}.
\end{equation*}
Altogether, this gives an upper bound of the form $K \log n_0 /n_0^2$
on the second order differences.
\end{proof}
Taking the previous two lemmas together with some estimates on the
intimal coefficients of $S(t)$ gives us the non-positivity of
coefficients of $(1-p(t))S(t)$ for $n_0 < n \le n_0^k$.
\begin{lemma}[Polynomial Range]
Given any $k \geq 1$ there exist a constant $K>0$ such that
for all sufficiently large $n_0$ if $0 < n \leq n_0^k$
then the $n$th coefficient of
$(1-p(t)) \prod_{i=1}^{n_0} (1-t^i)^{-o(i)}$
is less than $-K s_n/n_0$ where $s_n$ is the $n$th coefficient of
$\prod_{i=1}^{n_0} (1-t^i)^{-o(i)}$.
\end{lemma}
\begin{proof}
Notice that
\begin{equation*}\label{eqn:dumb}
(1-p(t))\prod_{i=1}^{n_0} (1-t^i)^{-o(i)} =
\prod_{i=n_0+1}^{\infty} (1-t^i)^{o(i)}.
\end{equation*}
Therefore, for $1 \leq n \leq n_0$, the $n$th coefficient of this
series is zero.
Fix $n$ such that $n_0 < n \leq 2n_0 + \log^2 n_0$.
We have the
following formula for the $n$th coefficient of this series.
$$ n\text{th coefficient } =
- o(n) + \sum_{\substack{i+j=n\\i,j >n_0}} o(i) o(j) +
\binom{o(n/2)}{2}.$$
(The last term occurs only if $n$ is even.)
We get estimates on these terms similar to those in Lemma~\ref{lem:e1}.
There exist $C_1, C_2, C_3 >0$ such that
\begin{equation*}
\begin{split}
o(n) &> C_1 \lambda^{n_0} /n_0 \\
\sum_{\substack{i+j=n\\i,j >n_0}} o(i) o(j) &
< C_2\lambda^{n_0} \log^2 n_0 /n_0^2 \\
\binom{o(n/2)}{2} &< C_3\lambda^{n_0} /n_0^2.
\end{split}
\end{equation*}
Therefore, for sufficiently large $n_0$ if $n_0 < n \leq 2n_0 + \log^2
n_0$ then the $n$th coefficient is negative.
Now fix $n$ such that $2n_0 +\log^2 n_0 < n \leq n_0^k$. We have a
formula for the $n$th coefficient of $(1-p(t))\prod_{i=1}^{n_0}
(1-t^i)^{-o(i)} = (1-p(t))S(t)$
$$n\text{th coefficient } = s_n \left( 1 - \sum_{i=1}^d p_i
(s_{n-i}/s_n) \right).$$
By Lemma~\ref{lem:es2} we have constants $C_4, c>0$ such that
\begin{equation*}
\sum_{i=1}^d p_i \left| (s_{n-i}/s_n)- (e_{n-i}/e_n)\right|< C_4 e^{-c
n_0}.
\end{equation*}
Now, by Lemmas~\ref{lem:1diff} and~\ref{lem:2diff}, we may apply the
Differences Argument to show that there is a constant $C_5>0$ such that
\begin{equation*}
1 - \sum_{i=1}^d p_i(e_{n-i}/e_n) < -C_5 / n_0.
\end{equation*}
The error from replacing the ratios $s_{n-i}/s_n$ with $e_{n-i}/e_n$
in the formula for the $n$th coefficient is negligible compared to the
above estimate. Therefore, we have an upper bound on
the $n$th coefficient of
$(1-p(t))\prod_{i=1}^{n_0} (1-t^i)^{o(i)}$ of the form $-Ks_n /n_0$
for some constant $K>0$.
\end{proof}
% Matrix methods
\section{Application of Matrix Methods to the Recursion Formula}
\label{sec:matrix}
In this section, we show that there is a choice of $r>0$ such that if
$n_0$ is sufficiently large then the $n$th coefficient of the power
series $S(t)(1-p(t))$ will be non-positive for $n_0^{14} < n \leq e^{r
n_0}$ (Polynomial to Exponential Range Lemma). In order to do so, we
make further use of the recursion formula for $e_n$,
\begin{equation*}
e_n = (1/n) \sum_{i=1}^{n_0} \tau_i e_{n-i}
\end{equation*}
to get estimates on the $e_n$ terms for $n > n_0^k$. We consider the
matrix
$$A_n = \begin{pmatrix}
\tau_1/n& \tau_2/n & \tau_3/n& \cdots & \tau_{n_0}/n \\
1& 0& 0& \cdots & 0\\
0& 1& 0& & 0\\
\vdots& \ddots& \ddots&\ddots & \vdots \\
0& \cdots& 0 &1 & 0
\end{pmatrix}.$$
If we multiply $A_n$ by the column vector comprised of a string of
coefficients $(e_{n-1}, e_{n-2}, \ldots , e_{n-n_0})^{\rm T}$ then we
obtain the string of coefficients $(e_{n}, e_{n-1}, \ldots ,
e_{n-n_0+1})^{\rm T}$. We will get estimates on the coefficients
$e_n$ for $n >n_0^k$ by considering ratios of the entries of
$A_{n+N}A_{n+N-1} \cdots A_n \vvec$ where $\vvec$ is an arbitrary
vector with nonnegative entries.
We begin by getting estimates on the Perron eigenvalue of $A_n$.
Fix $n>n_0$ and let $f(t)$ be the characteristic polynomial of $A_n$,
\begin{equation*}
f(t) = t^{n_0}-\tau_1 t^{n_0-1}/n-\ldots-\tau_{n_0} /n.
\end{equation*}
Note that there exists a unique positive real root $\alpha$ of $f(t)$
whose modulus exceeds that of all other roots.
\begin{lemma}
\label{lem:alphabound}
If $n_0$ is sufficiently large and $n>2n_0$ then
\begin{equation*}
\left(\frac{1}{2n}\right)^{1/n_0} < \frac{\alpha}{\lambda}
< \left(\frac{2n_0}{n}\right)^{1/n_0}.
\end{equation*}
\end{lemma}
\begin{proof}
Choose $n_0$ such that
\begin{equation*}
2n_0 > \sum_{i=1}^{n_0} \lambda^{-i} \tau^i \quad
\text{and} \quad \lambda^{-n_0} \tau_{n_0} >1/2.
\end{equation*}
We first see that $0<\alpha < \lambda$. This follows since
$\alpha$ is the only positive real root of $f(t)$, and we have
$f(0) = -\tau_{n_0}/n < 0$ and
\begin{equation*}
f(\lambda)
= \lambda^{n_0} - (1/n)\sum_{i=1}^{n_0} \tau_i \lambda^{n_0-i}
> \lambda^{n_0} (1 - 2n_0/n) > 0.
\end{equation*}
For the upper bound on $\alpha$,
\begin{equation*}
\alpha^{n_0} = (1/n)\sum_{i=1}^{n_0} \tau_i \alpha^{n_0-i}
< (1/n)\sum_{i=1}^{n_0} \tau_i \lambda^{n_0-i}
< \lambda^{n_0} (2n_0/n).
\end{equation*}
For the lower bound on $\alpha$,
\begin{equation*}
\alpha^{n_0} = (1/n)\sum_{i=1}^{n_0} \tau_i \alpha^{n_0-i}
> (1/n)\tau_{n_0}
> \lambda^{n_0} (1/2n).
\end{equation*}
\end{proof}
Next, we would like an upper bound on the modulus of the other roots
of the polynomial $f(t)$. We begin with some general lemmas about
polynomials whose coefficients satisfy various conditions.
\begin{lemma}
\label{lem:mvt}
Let $q(t) = \sum_{i=0}^d q_i t^i$ be a polynomial with all
coefficients
nonnegative and suppose $\alpha>0$.
If $z \in \complex$ with $|z| < \alpha$ then
\begin{equation*}
\left| \frac{q(z) - q(\alpha)}{z-\alpha} \right| \leq q'(\alpha).
\end{equation*}
Moreover, the inequality is strict as long as $q_i > 0$ for some
$i\geq 2$.
\end{lemma}
\begin{proof}
Let $r(t)$ be the polynomial $(q(t) - q(\alpha))/(t-\alpha)$. Then
$r(t)$ has all nonnegative real coefficients since
\begin{equation*}
r(t) = \frac{\sum_{i=1}^d q_i (t^i - \alpha^i)}{(t-\alpha)}
= \sum_{i=i}^d q_i (t^{i-1} + \alpha t^{i-2} + \cdots +
\alpha^{i-2} t + \alpha^{i-1}).
\end{equation*}
Therefore,
\begin{equation*}
\left| \frac{q(z) - q(\alpha)}{z-\alpha} \right| =
|r(z)| \leq r(|z|) = \frac{q(|z|) - q(\alpha)}{|z|-\alpha}.
\end{equation*}
By the Mean Value Theorem in $\reals$,
\begin{equation*}
\frac{q(|z|) - q(\alpha)}{|z|-\alpha} = q'(\beta)
\end{equation*}
for some $|z| < \beta < \alpha$. Since $q'(t)$ has all nonnegative
coefficients, $q'(\beta) \leq q'(\alpha)$, proving the inequality. If
$q'(t)$ is not constant then $q'(\beta) < q'(\alpha)$ giving a strict
inequality.
\end{proof}
\begin{lemma} \label{lem:dist}
Suppose $f(t) = t^{n_0} - \sum_{i=1}^{n_0} f_i t^{n_0-i}$ where
$n_0>3$ and $f_i \geq 0$ for all $1 \leq i \leq n_0$. Let $\alpha$
be the real root of $f(t)$ whose modulus exceeds the modulus of all
other roots. If $\beta \neq \alpha$ is a root of $f(t)$ then
$|\alpha - \beta| > \alpha/n_0$.
\end{lemma}
\begin{proof}
Let $q(t) = \sum_{i=1}^{n_0} q_i t^{n_0-i}$ be the polynomial
$q(t) = f(t) /(t - \alpha)$. Equating coefficients, we see that
$q_{n_0} \alpha = f_{n_0}$ and $\alpha q_{i-1} = f_{i-1} + q_i$ for
$2 \le i \le n_0$. In particular,
this shows that $q_i \geq 0$ for all $i$.
Therefore by Lemma~\ref{lem:mvt},
\begin{equation*}
\left| \frac{q(\beta) - q(\alpha)}{\beta-\alpha} \right|<
q^{\prime}(\alpha).
\end{equation*}
Since $q(\beta)=0$, after rearranging this becomes
\begin{equation*}
|\alpha - \beta| > \frac{q(\alpha)}{q^{\prime}(\alpha)}.
\end{equation*}
But $q(\alpha) = f'(\alpha)$ and $q^{\prime}(\alpha) = f''(\alpha)/2$,
thus $|\alpha - \beta| > 2 f'(\alpha)/f''(\alpha)$.
Now estimating $2 n_0 f'(\alpha)$,
\begin{equation*}
\begin{split}
2 n_0 f'(\alpha)
&= 2 n_0^2 \alpha^{n_0-1} - 2n_0
\sum_{i=1}^{n_0-1} (n_0-i) f_i \alpha^{n_0-i-1}\\
&= 2 n_0^2 \sum_{i=1}^{n_0} f_i \alpha^{n_0-i-1} -
2 n_0 \sum_{i=1}^{n_0-1} (n_0-i) f_i \alpha^{n_0-i-1}\\
&= 2n_0 \sum_{i=1}^{n_0} i f_i \alpha^{n_0-i-1}.
\end{split}
\end{equation*}
Similarly,
\begin{equation*}
\begin{split}
\alpha f''(\alpha)
&= n_0 (n_0-1) \alpha^{n_0-1} -
\sum_{i=1}^{n_0-2} (n_0-i)(n_0-i-1) f_i \alpha^{n_0-i-1} \\
&= \sum_{i=1}^{n_0-2} \left[2in_0 - i^2 -i\right]
f_i \alpha^{n_0-i-1} \\
& \qquad + n_0(n_0-1) f_{n_0-1}
+ \alpha^{-1} n_0(n_0-1) f_{n_0}.
\end{split}
\end{equation*}
By comparing the coefficients of $\alpha^{n_0-i-1}$ in each expression
we see $2n_0 f'(\alpha) > \alpha f''(\alpha)$. Therefore,
$$|\beta - \alpha| > 2f'(\alpha)/f''(\alpha) > \alpha/n_0.$$
\end{proof}
\begin{lemma} \label{lem:sumbound}
Let $n_0>0$ be an even integer and let $f_1, f_2, \ldots ,f_{n_0}$
be positive real numbers. Assume there exist constants $k_1,k_2>0$
such that for all $i$, \begin{equation*} k_1 < f_{i+1}/f_i < k_2.
\end{equation*} Let $\alpha>0$ be a real number and $\beta$ be a
complex number with $\alpha > |\beta|$ and $|\alpha - \beta| >
\alpha/n_0$. Then there is a constant $K>0$ depending only on
$\alpha$, $k_1$ and $k_2$ such that
\begin{equation*}
\left| \frac{\sum_{i=1}^{n_0} f_i \beta^{n_0-i}}{\sum_{i=1}^{n_0} f_i
\alpha^{n_0-i}} \right| < 1 - K/n_0^2.
\end{equation*}
\end{lemma}
\begin{proof}
We begin with the inequality
\begin{equation*}
\begin{split}
\left|\sum_{i=1}^{n_0} f_i \beta^{n_0-i}\right| &\leq
\sum_{i=1}^{n_0/2} \left| f_{2i-1} \beta^{n_0-2i+1}
+ f_{2i} \beta^{n_0-2i} \right|\\
&< \sum_{i=1}^{n_0/2} f_{2i-1} \alpha^{n_0-2i} |\beta +
f_{2i}/f_{2i-1}|.
\end{split}
\end{equation*}
We have a similar expression for $\sum_{i=1}^{n_0} f_i
\alpha^{n_0-i}$. Let $r_i =f_{2i}/f_{2i-1}$.
We proceed by comparing $|\alpha + r_i |$ to $|\beta +r_i|$.
If $\theta$ is the angle which $\beta$ makes with the positive real
axis then
\begin{equation*}
(\alpha/n_0)^2 < |\alpha - \beta|^2
= \alpha^2 + |\beta|^2 - 2\alpha |\beta| \cos \theta.
\end{equation*}
The above gives an upper bound for $2 |\beta| \cos \theta$ which we
plug into the following
\begin{equation*}
\begin{split}
|\beta + r_i |^2 &= |\beta|^2 + (r_i)^2 + 2 |\beta| r_i \cos \theta \\
&< |\beta|^2 + (r_i)^2 + \alpha r_i +
|\beta|^2 r_i /\alpha - \alpha r_i /n_0^2.
\end{split}
\end{equation*}
Using the fact that $|\beta|< \alpha$, we obtain
\begin{equation*}
|\beta + r_i |^2 < \alpha^2 + (r_i)^2 + 2 \alpha r_i - \alpha r_i /n_0^2
= (\alpha + r_i)^2 - \alpha r_i /n_0^2.
\end{equation*}
Therefore, there exists a $K>0$ depending only on $\alpha$,
$k_1$ and $k_2$ such that
\begin{equation*}
|\beta + r_i | < |\alpha + r_i | (1- K/n_0^2).
\end{equation*}
The desired inequality follows.
\end{proof}
Next we will apply the previous three lemmas to the polynomial $f(t) =
t^{n_0}-(1/n) \sum_{i=1}^{n_0}\tau_i t^{n_0-i}$. This will give us
bounds on the second largest eigenvalue of the matrix $A_n$.
\begin{lemma}
There is a constant $r>0$ such that
if $n_0$ is sufficiently large and $n_0^4 < n \leq e^{r n_0}$
then $|\beta| < (1-1/n_0^4)\alpha$ where $\beta \neq \alpha$
is a root of $f(t)= t^{n_0}-(1/n) \sum_{i=1}^{n_0}\tau_i t^{n_0-i}$.
\label{lem:zetabound}
\end{lemma}
\begin{proof}
Since $\alpha$ and $\beta$ are both roots of $f(t)$
\begin{equation}
\label{eqn:poly}
\left| \frac{\beta^{n_0}}{\alpha^{n_0}}\right| =
\left| \frac{\sum_{i=1}^{n_0} \tau_i \beta^{n_0 - i}}{
\sum_{i=1}^{n_0} \tau_i \alpha^{n_0-i}}\right|.
\end{equation}
Assume $|\beta| \geq (1 - 1/n_0^4) \alpha$. Then for some $C_1>0$ we
have
\begin{equation*}
|\beta/\alpha|^{n_0} > (1 - 1/n_0^4)^{n_0} > 1-C_1/n_0^3.
\end{equation*}
We will show that the right hand side of equation~\ref{eqn:poly} has
an upper bound of the form $1-C_2 /n_0^2$ giving us a contradiction
for sufficiently large $n_0$. We cannot directly apply the previous
lemma since we do not have good estimates on $\tau_{i+1}/\tau_i$ when
$i$ is small.
>From our estimates on $\tau_i$,
\begin{equation}
\sum_{i=1}^{n_0} \tau_i t^{n_0 - i}
= \sum_{i=1}^{n_0} \lambda^i t^{n_0-i} +
\sum_{i=1}^{n_0} \lambda^i a_i t^{n_0-i}
\label{eqn:split}
\end{equation}
where $|a_i| < C_1 e^{-c_1 i}$ for some constants $C_1, c_1 >0$.
We wish to show that this second sum in equation~\ref{eqn:split} is
negligible compared to the first for $t = \alpha, \beta$.
First note that
\begin{equation*}
\left| \sum_{i=1}^{n_0} \lambda^i a_i \alpha^{n_0-i} \right| < C_1
\alpha^{n_0} \sum_{i=1}^{n_0} e^{-c_1 i} \left( \frac{\lambda}{\alpha}
\right)^i
\end{equation*}
Using the upper bound on $\alpha$ from Lemma~\ref{lem:alphabound} and
the fact that $n > n_0^4$ we have $\alpha^{n_0} <
(2n_0/n)\lambda^{n_0} < 2\lambda^{n_0}/n_0^3$. If we select $0 n_0^4$ there is a constant $C_2>0$ such that
\begin{equation*}
\left| \sum_{i=1}^{n_0} \lambda^i a_i t^{n_0-i} \right|
< C_2 \alpha^{n_0} < C_2 \lambda^{n_0}/n_0^3
\end{equation*}
for $t = \alpha, \beta$.
For a lower estimate on the first term, notice that
\begin{equation*}
\left|\sum_{i=1}^{n_0} \lambda^i \beta^{n_0-i}\right|
= \lambda^{n_0} \left|
\frac{1 - (\beta/\lambda)^{n_0}}{1-(\beta/\lambda)}\right|.
\end{equation*}
The numerator is at least $1-(\alpha/\lambda)^{n_0}$ which is at least
$1 - 2/n_0^3$. The denominator is no more than 2. Thus we get a lower
bound on the term $\left|\sum_{i=1}^{n_0} \lambda^i t^{n_0-i}\right|$
of the form $C_3 \lambda^{n_0}$ for some constant $C_3>0$.
Thus there is a constant $C_4 >0$ such that
\begin{equation*}
\left| \frac{\sum_{i=1}^{n_0} \tau_i \beta^{n_0 - i}}{
\sum_{i=1}^{n_0} \tau_i \alpha^{n_0-i}}\right| =
\left|\frac{\sum_{i=1}^{n_0} \lambda^i
\beta^{n_0-i}}{\sum_{i=1}^{n_0} \lambda^i \alpha^{n_0-i}}
\right|( 1 \pm C_4/ n_0^3)
\end{equation*}
Now, for the remaining term use Lemma~\ref{lem:sumbound}. We obtain a
constant $C_5>0$ such that
\begin{equation*}
\left|\frac{\sum_{i=1}^{n_0} \lambda^i \beta^{n_0-i}}{\sum_{i=1}^{n_0}
\lambda^i \alpha^{n_0-i}} \right| < 1 - C_5/n_0^2.
\end{equation*}
Therefore, there exists a constant $C_6>0$ such that
\begin{equation*}
1-C_1/n_0^3 < \left| \frac{\beta^{n_0}}{\alpha^{n_0}}\right| =
\left| \frac{\sum_{i=1}^{n_0} \tau_i \beta^{n_0 - i}}{
\sum_{i=1}^{n_0} \tau_i \alpha^{n_0-i}}\right| < 1-C_6/n_0^2.
\end{equation*}
For sufficiently large $n_0$, this is a contradiction.
\end{proof}
Now we have estimates from Lemma~\ref{lem:alphabound} on the Perron
eigenvalue of $A_n$ and from Lemma~\ref{lem:zetabound} on the second
largest modulus of a root. We would like to use these to show that for
any vector $\vvec$ with nonnegative entries if $N\ge n_0^6$ then
$(A_n)^Nv$ is asymptotically close to the eigenvector for $A_n$. It
will be convenient for us to use the matrix $B_n$ where $B_n$ is $A_n$
scaled by the Perron eigenvalue $\alpha$ i.e.,
\begin{equation*}
B_n = \begin{pmatrix}
\tau_1/n& \tau_2/(n\alpha) &
\tau_3/(n \alpha^2)& \cdots & \tau_{n_0}/(n\alpha^{n_0-1}) \\
1& 0& 0& \cdots & 0\\
0& 1& 0& & 0\\
\vdots& \ddots& \ddots&\ddots & \vdots \\
0& \cdots& 0 &1 & 0
\end{pmatrix}.
\end{equation*}
It will also be convenient for us to use the $\infty$-norm in the
following lemmas. I.e., for $\uvec = (u_1,u_2,\ldots , u_{n_0})$,
$\|\uvec \| = \max |u_j|$.
\begin{lemma}
There exist constants $r, K, k >0$ such that if $n_0$ is sufficiently
large and $n_0^4 < n \leq e^{r n_0}$ then $\vvec \in
(\reals_+)^{n_0}$ implies \begin{equation*} \left|
\frac{\left[(B_n)^{n_0^6}\vvec\right]_{j+1}
}{\left[(B_n)^{n_0^6}\vvec\right]_{j}} - 1 \right| < K e^{-k n_0}.
\end{equation*} \label{lem:matrat}
\end{lemma}
\begin{proof}
Fix $n_0^4 < n \leq e^{r n_0}$, let $B = B_n$. Suppose $\cvec$ is the
column eigenvector for $B$ corresponding to the eigenvalue one, $\cvec
= (1,1,\ldots , 1)^{\rm T}$. By Lemma~\ref{lem:zetabound}, all other
eigenvalues have modulus less than $(1-C_1/n_0^4)$. Let $W$ denote
the span of the complementary generalized eigenvectors. We wish to
write the vector $\vvec$ as $a \cvec + \wvec$ where $\wvec \in
W$. Then
$$B^N \vvec = a \cvec + B^N \wvec.$$
To produce the lower bound for $a$, we note that a row eigenvector
$\rvec$ corresponding to the eigenvalue 1 is perpendicular to all of
$W$. To see this suppose $({\rm I} \beta - A)^m \xvec = 0$. Since 1 is
an eigenvalue of multiplicity one, the following equation shows $\rvec
\xvec = 0$
\begin{equation*}
\rvec ({\rm I} \beta - A)^m \xvec = \sum_{j=0}^m \binom{m}{j} \beta^j
\rvec A^{m-j} \xvec = \sum_{j=0}^m \binom{m}{j} \beta^j \rvec \xvec =
(\beta - 1)^m \rvec \xvec.
\end{equation*}
Take $\rvec = (r_0,r_1, \ldots ,
r_{n_0-1})$ to be the row eigenvector for 1, where $r_j = 1 -
\sum_{i=1}^{j} \tau_i \alpha^{-i}/n = \sum_{i=j+1}^{n_0} \tau_i
\alpha^{-i}/n$.
Using the fact that $\rvec^{\rm T} \in W^{\perp}$ we can write
\begin{equation*}
\begin{split}
\vvec& = \left( \tfrac{\rvec \vvec}{\rvec\cdot \rvec} \right)
\rvec^{\rm T} + \wvec_1 \quad \text{where } \wvec_1 \in W \\ \cvec&
= \left( \tfrac{\rvec \cvec}{\rvec\cdot \rvec} \right) \rvec^{\rm T}
+ \wvec_2 \quad \text{where } \wvec_2 \in W.
\end{split}
\end{equation*}
Thus we may write
\begin{equation*}
\vvec = \left( \tfrac{\rvec \vvec}{\rvec \cvec} \right)
\cvec + \wvec\quad \text{where } \wvec \in W.
\end{equation*}
Without loss of generality, we may assume that $\|\vvec\| = 1$. In
this case, there is a constant $C_1 >0$ such that
\begin{equation*}
\rvec \vvec \geq \min r_j
\ge (1/n) \tau_{n_0} \alpha^{-n_0}
> C_1/n_0.
\end{equation*}
The above follows from the bounds on
$\alpha/\lambda$ from Lemma~\ref{lem:alphabound} and the fact that
$\tau_n$ grows like $\lambda^n$. For the denominator,
\begin{equation*}
\rvec \cvec = (1/n) \sum_{i=1}^{n_0} i \tau_i \alpha^{-i} < n_0/n
\sum_{i=1}^{n_0} i \tau_i \alpha^{-i} = n_0.
\end{equation*}
Therefore we can write $\vvec$ as $a \cvec + \wvec$ where $\wvec \in
W$ and $a > C_1 /n_0^2$.
To estimate $\| \wvec \|$, we simply note that
$\rvec \vvec < \rvec \cvec$ therefore
\begin{equation*}
\|\wvec \| \leq 1 + a \|\cvec\| \leq 2.
\end{equation*}
Now we would like an upper bound for $\| B^{n_0^6} \wvec \|$. To
obtain this estimate, we triangulate the matrix corresponding to
$B|_W$ and keep track of the size of entries of the resulting
matrix. Following the triangulization scheme in~\cite[\S 6.1]{DL},
there are $(n_0-1)$ linearly independent vectors
$\{\uvec_1,\uvec_2,\ldots \uvec_{n_0-1}\}$ in $\complex^{n_0}$ such
that every element of $W$ can be written as a $\complex$-linear
combination of the $\uvec_i$'s and for all $k = 1,2,\ldots, (n_0-1)$,
$A\uvec_k \in$ span$\{\uvec_1,\uvec_2, \ldots , \uvec_k\}$. Moreover,
by Gram-Schmidt, we may assume that these vectors are
orthonormal. Therefore, if $C$ is the $n_0 \times (n_0-1)$ matrix with
columns $\uvec_j$ then $C^{\rm T} B C$ is an $(n_0-1)\times
(n_0-1)$ triangular matrix $D$. The diagonal elements of $D$ are the
eigenvalues corresponding to $W$, so each has modulus less than
$(1-1/n_0^4)$. For all $j$, $\|B \uvec_j^{\rm T}\|_{\infty} < 1$
therefore $\|\uvec_k B \uvec_j^{\rm T}\|_{\infty} < n_0$ for all $k$
and each off-diagonal entry of $D$ has modulus less than $n_0$. This
implies that the entries of $D^N$ are each less than $(1-1/n_0^4)^N
{n_0}^{n_0} \binom{N+n_0-1}{N}$ in modulus (see Lemma~\ref{lem:A3}).
Altogether, this gives a bound on $\|B^N \wvec\| = \| C D^N C^{\rm
T}\wvec\|$ of the form
\begin{equation*}
\|B^N \wvec\| \le (1-1/n_0^4)^N {n_0}^{n_0}\binom{N+n_0-1}{n_0}
\end{equation*}
where $C_3>0$ is a constant. Letting $N = n_0^6$, there exist constants
$C_4, C_5 , c_1, c_2 >0$ such that
\begin{equation*}
(1-1/n_0^4)^{n_0^6} \le C_4 e^{-c_1 n_0^2}
\end{equation*}
and
\begin{equation*}
n_0^{n_0} \binom{n_0^6+n_0-1}{n_0} <
C_5 n_0^{n_0} {n_0}^6 (1+n_0^5)^{n_0} < C_5 e^{c_2 n_0 \log n_0}
\end{equation*}
(see Lemma~\ref{lem:A1}).
Thus we have constants $C_6, C_7, c_3>0$ and
an upper bound on $\|B^{n_0^6} \wvec\|$ of the form
\begin{equation*}
\|B^{n_0^6} \wvec\| < C_6 e^{-c_1 n_0^2 + c_2 n_0 \log n_0} < C_7
e^{-c_3 n_0}
\end{equation*}
for sufficiently large $n_0$.
This tells us that the $j$th coordinate of $B^{n_0^6}\vvec$ is $a
\pm C_7 e^{-c_1 n_0}$ which gives the desired result.
\end{proof}
It remains to show that the difference between using $(A_n)^{n_0^6}$
and the product $A_{n+n_0^6-1} A_{n+n_0^6-2} \cdots A_n$ is
negligible.
For the following, fix $n_0^{14} < n \leq e^{r n_0}$. Let $\alpha$
denote the Perron eigenvalue of the first matrix $A_n$. Let $B_{n+k}$
denote the matrix $A_{n+k}$ scaled by $\alpha$.
\begin{lemma}
There exists a constant $r>0$ such that
if $n_0$ is sufficiently large and $n_0^k < n \leq e^{r n_0}$
then for $\vvec \in (\reals_+)^{n_0}$,
\begin{equation*}
\| (B_n)^{n_0^6}\vvec - B_{n_0+n_0^6-1}B_{n_0+n_0^6-2}\cdots
B_n\vvec\|_{\infty} < n_0^{12-k} \|\vvec\|_{\infty}.
\end{equation*}
\label{lem:nmat}
\end{lemma}
\begin{proof}
Note that with the $\infty$-norm, for any $1 \leq i \leq n_0^6$
\begin{equation*}
\| B_n \vvec - B_{n+i} \vvec \| = \| (B_n-B_{n+i}) \vvec\| \leq
\frac{i}{n+i} \|\vvec\| \leq n_0^{6-k} \|\vvec\|
\end{equation*}
and
\begin{equation*}
\|B_{n+i}\vvec\| \leq \|\vvec\|.
\end{equation*}
Therefore,
\begin{equation*}
\| B_n^{n_0^6}\vvec - B_{n_0+n_0^6-1}B_{n_0+n_0^6-2}\cdots B_n\vvec\|
\leq n_0^6 n_0^{6-k} \|\vvec\| \le n_0^{12-k} \|\vvec\|.
\end{equation*}
\end{proof}
Combining the lemmas of this section, we may select an $r>0$, then an
$n_0$ such that there is an $\alpha < \lambda$ with
$|e_{n+1}/e_n - \alpha|$ as
small as we like compared to $\lambda - \alpha$. This gives the
following lemma.
\begin{lemma}[Polynomial to Exponential Range]
There are constants $K,r>0$ such that if $n_0$ is sufficiently large
and $n_0^{14} < n \le e^{rn_0}$ then the $n$th coefficient of
$(1-p(t)) \prod_{i=1}^{n_0} (1-t^i)^{-o(i)}$ is less than $-Ks_n/n_0$.
\label{thm:polytoexp}
\end{lemma}
\begin{proof}
Lemma~\ref{lem:alphabound} provides bounds on the Perron eigenvalue
$\alpha$ of the matrix $A_n$. Using this lemma, we may choose an
$r>0$ such that if $2n_0 < n \le e^{r n_0}$ then $1-p(1/\alpha) < -C_1
|\lambda - \alpha|$ for some constant $C_1>0$. If necessary,
decrease this value of $r$ so that the estimates from
Lemmas~\ref{lem:es2},~\ref{lem:matrat} and~\ref{lem:nmat} all hold for
$n_0^{14} < n \le e^{r n_0}$.
Fix $n_0^{14} < n \le e^{rn_0}$. Let $m = n - n_0^6$, and let $\alpha$
denote the Perron eigenvalue of the matrix $A_m$. Let $\uvec = (u_0,
u_1, \ldots , u_{n_0-1})$ denote the vector
\begin{equation*}
\uvec = (B_m)^{n_0^6} (e_m/\alpha^m, e_{m-1}/\alpha^{m-1}, \ldots ,
e_{m-n_0+1}/\alpha^{m-n_0+1})^{\rm T}.
\end{equation*}
By Lemma~\ref{lem:nmat}, there is a constant $C_2 >0$ such that
\begin{equation*}
\left| (\alpha^i e_{n-i}/e_n) - (u_i/u_0) \right| < C_2 / n_0^2
\end{equation*}
for all $0 \leq i < n_0$.
By Lemma~\ref{lem:matrat}, there are constants $C_3, c_1>0$ such that
\begin{equation*}
|(u_i/u_0) - 1 | < C_3 e^{-c_1 n_0}
\end{equation*}
for all $0 \leq i < n_0$.
By Lemma~\ref{lem:es2} we have constants $C_4, c_2>0$ such that
\begin{equation*}
\left|(s_n/e_n) -1 \right| < C_4 e^{-c_2 n_0}.
\end{equation*}
Altogether, this gives a constant $C_5>0$ such that
\begin{equation*}
\left| (s_{n-i}/s_n) - \alpha^{-i} \right| < C_5/n_0^2.
\end{equation*}
By Lemma~\ref{lem:alphabound} there is a constant $C_6>0$ such that
\begin{equation*}
|\lambda - \alpha| > C_6 \log n_0/n_0.
\end{equation*}
Therefore, by the Ratios Argument, there is a constant $K>0$ such that
if $n_0$ is sufficiently large, and $n_0^{14} < n \le e^{r n_0}$ then
\begin{equation*}
n\text{th coefficient} < -K s_n /n_0.
\end{equation*}
\end{proof}
% Product
\section{Managing the Product}
\label{sec:product}
Now, in order to complete the proof, we multiply $(1-p(t))S(t)$ by a
power series of the form $(1-q(t))^{-1}$ where $q_i > 0$ for all
$i$. We wish to have the $n$th coefficient of $(1-q(t))^{-1}$ closely
approximate $\beta^n$ for some $\beta$.
Fix $r>0$ to make the Polynomial to Exponential Range Lemma hold. Let
$\beta = \lambda e^{-r/2}$ and let
\begin{equation*}
g(t) = t^{n_0^3} - \sum_{i=n_0^2}^{n_0^3}
\left[ \frac{\beta^i}{n_0^3-n_0^2} \right] t^{n_0^3-i}
\end{equation*}
where $[x]$ denotes the greatest integer function. Let $\gamma$ denote
the unique positive real root of $g(t)$ whose modulus exceeds that of
all other roots.
\begin{lemma}
There is a constant $K>0$ such that if $n_0$ is sufficiently large
then $|\gamma - \beta| < K \beta^{-n_0^2}$.
\end{lemma}
\begin{proof}
Let $n_1 = n_0^2$ and $n_2 = n_0^3$.
Notice that $\gamma < \beta$. If $\gamma < z < \beta$ then
\begin{equation*}
\begin{split}
g'(z) & = n_2 z^{n_2-1} - \sum_{i=n_1}^{n_2} (n_2-i)
\left[\frac{\beta^i}{n_2-n_1} \right] z^{n_2-i-1}\\
& \ge \sum_{i=n_1}^{n_2} i
\left[\frac{\beta^i}{n_2-n_1} \right] z^{n_2-i-1}.
\end{split}
\end{equation*}
Taking only the last term in the sum, if $n_0$ is sufficiently large
then we have a lower bound on $g'(z)$ of the form $\beta^{n_2-1}$.
Replacing $\beta^{n_2}$ with
$\sum_{i=n_1}^{n_2} \beta^i (n_2-n_1)^{-1} \beta^{n_2-i}$
we obtain an upper bound on $g(\beta)$ from
\begin{equation*}
g(\beta) = \beta^{n_2} - \sum_{i=n_1}^{n_2}
\left[\frac{\beta^i}{n_2-n_1}\right] \beta^{n_2-i}
< \sum_{i=n_1}^{n_2} \beta^{n_2-i}.
\end{equation*}
Therefore, by the Mean Value Theorem there is a $z \in (\gamma,
\beta)$ such that
\begin{equation*}
|\gamma - \beta| = g(\beta) / g'(z) < \beta \sum_{i=n_1}^{n_2}
\beta^{-i}
< K \beta^{-n_1}.
\end{equation*}
\end{proof}
Let $1-q(t)$ denote the polynomial $t^{n_2} g(1/t)$. The following
lemmas give estimates on the coefficients of
$R(t) = \sum_{i=0}^{\infty} r_i t^i = (1-q(t))^{-1}$.
\begin{lemma}
There exist constants $K, k >0$ such that if $n_0$ is sufficiently
large and $n> n_0^{21}$ then
\begin{equation*}
\left| \frac{r_{n+1}}{\gamma r_n} -1\right| < K e^{-k n_0^3}
\end{equation*}
\label{lem:rratio}
\end{lemma}
\begin{proof}
Again let $n_1 = n_0^2$ and $n_2 = n_0^3$.
The recursion relation which gives $r_n$ is simply
\begin{equation*}
r_n = \sum_{i=n_1}^{n_2} q_{i} r_{n-i}.
\end{equation*}
Therefore we may directly apply the ``matrix methods'' from the
previous section.
The string of coefficients $(r_{n+i}, r_{n+i-1},\ldots ,
r_{n+i-n_2+1})$ is obtained by multiplying the vector $(r_{n},
r_{n-1},\ldots , r_{n-n_2+1})$ by a recursion matrix raised to the
$i$th power. We have bounds on the ratio of consecutive coefficients
\begin{equation*}
\beta - \left( \frac{n_2-n_1}{\beta^{i}} \right) < \frac{q_{i+1}}{q_i}
< \beta \left(1- \frac{n_2-n_1}{\beta^{i}} \right)^{-1}.
\end{equation*}
Therefore using Lemmas ~\ref{lem:mvt},~\ref{lem:dist},
and~\ref{lem:sumbound} if $\zeta \neq \gamma$ is a root of
$g(z)$ then there is a constant $C_1>0$ such that
\begin{equation*}
\left| \frac{\zeta^{n_2}}{\gamma^{n_2}}\right| =
\left| \frac{\sum_{i=1}^{n_2} q_i \zeta^{n_2 - i}}{
\sum_{i=1}^{n_2} q_i \gamma^{n_2-i}}\right|
< 1 - C_1/ n_2^2.
\end{equation*}
Reasoning in a manner similar to Lemma~\ref{lem:zetabound}, for
sufficiently large $n_0$,
\begin{equation*}
|\zeta| < (1- 1/n_2^4) \gamma.
\end{equation*}
Following the argument in Lemma~\ref{lem:matrat}, there exist
constants $K, k >0$ such that if we multiply an arbitrary vector
$\vvec$ with nonnegative entries by the recursion matrix raised to the
$n_2^6$ power, the result will be a vector $\uvec$ whose entries
satisfy $|u_{j+1}/u_j - \gamma | < K e^{-k n_2}$. This gives the
desired estimate on ratios of coefficients $r_{n+1}/r_n$.
\end{proof}
\begin{lemma}
The coefficient of $t^n$ in $R(t) = (1-r(t))^{-1}$ is less than $n
\beta^n$ for all $n$.
\end{lemma}
\begin{proof}
We consider the $n$th coefficient of $(1-q(t))^{-1} =
\sum_{i=0}^{\infty} \left(q(t)\right)^i$.
The result follows from the fact that
the coefficient of $t^n$ from $(q(t))^i$ is always less than $\beta^n$.
This holds since the number of ways to select $i$ coefficients of $q(t)$
whose indices sum to $n$ is less than or equal to $(n_0^3-n_0^2)^i$.
\end{proof}
We now have the necessary estimates on the $n$th coefficient of the
power series $R(t) = (1-q(t))^{-1}$ for all $n$ and on the $n$th
coefficient of the series $S(t) =
\prod_{i=1}^{n_0} (1-t^i)^{-o(i)}$ as long as $n \le e^{rn_0}$.
The final estimates will be for the $n$th coefficient of $S(t)$ where
$n > e^{rn_0}$.
\begin{lemma}
There exists a $\delta >0$ such that if $n_0$ is sufficiently large
and $n > e^{3r n_0/4}$ then $s_n < (\beta - \delta)^n$.
\end{lemma}
\begin{proof}
We begin by finding estimates on $\binom{o(i) + n/i - 1}{n/i}$ which
is the $n$th coefficient of the series $(1-t^i)^{-o(i)}$ as long as
$i$ divides $n$. We use the formula
\begin{equation*}
\binom{o(i) + n/i - 1}{n/i} < n \left( 1 + \frac{io(i)}{n} \right)^{n/i}
\left(1 + \frac{n}{io(i)} \right)^{o(i)}
\end{equation*}
from Lemma~\ref{lem:A1}.
We will fix $n > e^{3r n_0/4}$ and find estimates on the logarithm of
each
term on the right hand side.
Suppose $i < \log n_0$. Then there exist constants $K, k$ such that if
$n_0$ is sufficiently large then $io(i) < K (\log n)^k$ since there is
a constant $C_1>0$ such that
\begin{equation*}
io(i) < C_1 \lambda^{\log n_0} = C_1 n_0^{\log \lambda}
< K (\log n)^{\log \lambda}.
\end{equation*}
Using the fact that $\log(1+x) < x$ for $x > 0$ we can certainly ensure
\begin{equation*}
\frac{n}{i} \log \left( 1 + \frac{io(i)}{n} \right)
< o(i) < K (\log n)^k.
\end{equation*}
For the other term,
\begin{equation*}
o(i) \log \left( 1 + \frac{n}{io(i)} \right) < o(i) \log (n+1)
< 2 K (\log n)^{k+1}.
\end{equation*}
Altogether, this shows that we can select a $\delta>0$ such that for
sufficiently large $n_0$,
\begin{equation*}
\log \binom{o(i) + n/i - 1}{n/i} < n \log(\beta - 2 \delta).
\end{equation*}
Now suppose $i \ge \log n_0$. Then for one term we have an upper bound
of the form
\begin{equation*}
o(i) \log \left( 1 + \frac{n}{io(i)} \right)
< \frac{n}{i} \le \frac{n}{\log n_0}.
\end{equation*}
For the other term we have two cases. If $io(i) < n$ then
\begin{equation*}
\frac{n}{i} \log \left( 1 + \frac{io(i)}{n} \right)
< \frac{n}{i} \log 2 \le \frac{n \log 2}{\log n_0}.
\end{equation*}
If $io(i) \ge n$, since $i \geq \log n_0$ we may assume
$io(i) < 2 \lambda^i$. Therefore
\begin{equation*}
\frac{n}{i} \log \left( 1 + \frac{io(i)}{n} \right)
< \frac{n}{i} \log \left(\frac{4 \lambda^i}{n} \right)
= n \left( \log \lambda + \frac{\log 4}{i}- \frac{\log n}{i} \right)
\end{equation*}
Recalling $\log n>3 r n_0/4$, this term has an upper bound of the form
\begin{equation*}
\frac{n}{i} \log \left( 1 + \frac{io(i)}{n} \right) <
n \left( \log \lambda + \frac{\log 4}{\log n_0}- \frac{3 r}{4} \right).
\end{equation*}
Since $\log \beta = \log \lambda - r/2$, in either case we can choose
a $\delta >0$ such that for sufficiently large $n_0$,
\begin{equation*}
\log \binom{o(i) + n/i - 1}{n/i} < n \log\left(\beta - 2 \delta
\right).
\end{equation*}
Therefore, we may assume that the $n$th coefficient of
$(1-t^i)^{-o(i)}$ is at most $(\beta-2\delta)^n$ for $n>e^{3 rn_0/4}$.
The $n$th coefficient in the product $\prod_{i=1}^{n_0}
(1-t^i)^{-o(i)}$ is made up of at most $\binom{n + n_0 -1}{n}$ terms
each of which is less than $(\beta - 2 \delta)^n$. Using the upper
bound $\binom{n + n_0-1}{n} < (2n)^{n_0}$, this tells us that
if $n_0$ is sufficiently large and $n > e^{3rn_0/4}$ then we
have an estimate of the $n$th coefficient of $(1-t^i)^{-o(i)}$ of the
form
\begin{equation*}
n\text{th coefficient} < (2n)^{n_0} (\beta-2\delta)^n < (\beta-\delta)^n
\end{equation*}
\end{proof}
We are now ready to finish the main theorem.
\begin{lemma}[Final Factorization]
There is a choice of $\beta$ and $n_0$ such that
if
\begin{equation*}
S(t) = \prod_{i=1}^{n_0} (1-t^i)^{-o(i)} \text{ and }
R(t) = \left(1 - \sum_{i=n_0^2}^{n_0^3}
\left[\frac{\beta^i}{n_0^3-n_0^2} \right] t^{i}\right)^{-1}
\end{equation*}
then the $n$th coefficient of the product $(1-p(t))S(t) R(t)$
is non-positive for all $n\geq 1$.
\end{lemma}
\begin{proof}{\bf Region I:}
The $n$th term of the product $(1-p(t))S(t) R(t)$ looks like
\begin{equation*}
\sum_{i=0}^n s_i r_{n-i} - p_1 \sum_{i=0}^{n-1} s_i r_{n-i-1}- \cdots
- p_d \sum_{i=0}^{n-d} s_i r_{n-i-d}
\end{equation*}
We know from the results of section~\ref{sec:polyrange} that there
exists a constant $C_1>0$ such that given any $\epsilon >0$ and any
$k\geq 1$, if $n_0$ is sufficiently large, $n_0 < n \leq n_0^k$ and $0
\leq i \leq n$ then $s_i/s_n < C_1 (\lambda - \epsilon)^{i-n}$. Thus
\begin{equation*}
\sum_{i=0}^d s_i r_{n-i}/s_n < C_1 n
\left( \frac{\beta}{\lambda-\epsilon}\right)^{n}
\end{equation*}
Therefore, the $n$th term of $(1-p(t))S(t) R(t)$ looks like
\begin{equation*}
\sum_{i=d}^n s_i r_{n-i} - p_1 \sum_{i=d-1}^{n-1} s_i r_{n-i-1}- \cdots
- p_d \sum_{i=0}^{n-d} s_i r_{n-i-d} + e(n)
\end{equation*}
where $e(n)$ is an error term whose absolute value has an upper bound
of the form
\begin{equation*}
|e(n)| < C_2 n \left( \frac{\beta}{\lambda-\epsilon}\right)^{n} s_n.
\end{equation*}
Notice that the error term is zero if $n < n_0^2$. Rearranging the
terms of the $n$th coefficient and ignoring the error term, we obtain
\begin{equation*}
\sum_{i=d}^n s_i r_{n-i} (1 -p_1 s_{i-1}/s_i -\cdots - p_d s_{i-d}/s_i).
\end{equation*}
By the Polynomial Range Lemma, each term in this sum is non-positive
for $n_0 < n \leq n_0^k$. In fact, for $n \geq n_0^2$ we have an
upper bound on the last term in the sum of the form
\begin{equation*}
s_n(1 -p_1 s_{n-1}/s_i -\cdots p_d s_{n-d}/s_n) < - s_n C_3/n_0
\end{equation*}
for some constant $C_3 >0$. This shows that for sufficiently large
$n_0$, the error term will not affect the non-positivity of the $n$th
coefficient in this range.
\noindent{\bf Region II:} We consider the range $n_0^{k-1} < n \le
e^{rn_0}$ and use practically the same argument as in Region I. Let
$n_1 = n_0^2$ and $n_2 = n_0^3$. Given any $\epsilon>0$ if $n_0$ is
sufficiently large and $0 \leq i \leq n_1$ then the ratio $s_i/s_{n_1}
< C_1 (\lambda - \epsilon)^{i-n_1}$.
>From the estimates in this section, given any $\epsilon >0$,
if $n_0$ is sufficiently large and $n_0^{21} < i < n$ then
\begin{equation*}
r_n/r_i < (\beta + \epsilon)^{n-i}.
\end{equation*}
By selecting $\epsilon >0$ small enough, there is a constant $c_1 >0$
such that $(\beta+\epsilon)/(\lambda-\epsilon) < e^{c_1}$. Therefore,
for some constant $C_2 >0$,
\begin{equation*}
\frac{\sum_{i=0}^d s_i r_{n-i}}{s_{n_1} r_{n-n_1}}
< C_2 e^{-c_1 n_1}.
\end{equation*}
Now again, we look at the $n$th term of $(1-p(t)) S(t) R(t)$ as
\begin{equation*}
\sum_{i=d}^n s_i r_{n-i}(1 -p_1 s_{i-1}/s_i -\cdots - p_d
s_{i-d}/s_i)+ e(n)
\end{equation*}
where $e(n)$ is an error term whose absolute value has an upper bound
of the form
\begin{equation*}
e(n) < s_{n_1} r_{n-n_1} C_2 e^{-c_1 n_1}.
\end{equation*}
By the Polynomial Range Lemma and the Polynomial to Exponential Range
Lemma, each term in the sum is non-positive. Moreover, we have an
upper bound on the term
\begin{equation*}
s_{n_1} r_{n-n_1} (1 -p_1 s_{n_1-1}/s_{n_1} -\cdots - p_d
s_{n_1-d}/s_{n_1}) < - s_{n_1} r_{n-n_1} K/n_0.
\end{equation*}
Thus for sufficiently large $n_0$, the error term will not affect the
non-positivity of the $n$th coefficient.
\noindent{\bf Region III:}
We consider the range $n > e^{3rn_0/4} + n_0^{21}$. For $n >
e^{3rn_0/4}$ we have $s_{n} < (\beta - \delta)^n$. Let $n_1 =
n_0^2$ and $n_3 = n_2^7 = n_0^{21}$. By the results of this section
for any $\epsilon >0$ by choosing $n_0$ sufficiently large we have
$r_n > (\beta - \epsilon)^{n- n_3} r_{n_3}$. By selecting $\epsilon$
small enough, there is a constant $c_2 >0$ such that $(\beta-
\delta)/(\beta- \epsilon) < e^{-c_2}$.
If $n >e^{3rn_0/4} + n_3$ then there
exists a constant $C_3 >0$ such that
\begin{equation*}
\frac{s_n + \sum_{i=n_1}^{n_3+d} s_{n-i} r_{i}}{r_n} <
C_3 n_3 e^{-c_2(n-n_3)}.
\end{equation*}
Now looking at the $n$th term of $(1-p(t)) S(t) R(t)$ as
\begin{equation*}
\sum_{i=0}^{n-n_3-d}
s_{n-i} r_{i}(1 -p_1 r_{i-1}/r_{i} -\cdots p_d r_{i-d}/r_{i})+ e(n)
\end{equation*}
where $e(n)$ is an error term whose absolute value is at most
\begin{equation*}
e(n) < r_n C_3 n_3 e^{-c_2(n-n_3)}.
\end{equation*}
Each term in the sum here is non-positive using Lemma~\ref{lem:rratio}
and the ratio argument with the $r_n$ coefficients. Moreover,
we have an upper bound on the first term of the summation
\begin{equation*}
r_n (1 -p_1 r_{n-1}/r_n -\cdots p_d r_{n-d}/r_n) < - r_n K/n_0.
\end{equation*}
Therefore, by choosing $n_0$ sufficiently large, the error
term will not affect the non-positivity of the coefficient.
Therefore, by selecting $n_0$ sufficiently large, we can ensure that
the polynomial $(1-p(t)) S(t) R(t)$ has all non-positive coefficients
in degrees greater than zero.
\end{proof}
The above shows that we may factor $1-p(t)$ in the form appearing in
the Main Reduction Lemma. This proves the remaining direction of the
theorem.
% Appendix
\appendix
\section{Lemmas on Binomial Coefficients and Matrix Theory}
These results are probably known to experts in the appropriate areas
but we do not have convenient references.
\begin{lemma}\label{lem:A4}
Suppose $w_1 \leq w_2 \leq \cdots \leq w_n$ with $\sum_{i=1}^n w_i =1$.
If $r_1 \leq r_2 \leq \cdots \leq r_n$ then
$$\sum_{i=1}^n w_i r_i \geq (1/n) \sum_{i=1}^n r_i.$$
\end{lemma}
\begin{proof}
Since the weights $w_i$ are increasing there is an index $j$ such that
$w_i < 1/n$ for all $1 \leq i < j$ and
$w_i \geq 1/n$ for all $j \leq i \leq n$.
Notice that
$$\sum_{i=j}^{n} (w_i-1/n) = \sum_{i=1}^{j-1} (1/n - w_i).$$
Therefore
$$\sum_{i=j}^{n} (w_i-1/n) r_i \geq \sum_{i=1}^{j-1} (1/n - w_i) r_i.$$
Rearranging we obtain the desired inequality.
\end{proof}
\begin{lemma}\label{lem:A3}
If $A$ is an $n_0 \times n_0$
triangular matrix over $\reals_+$ with diagonal entries
less than $\beta$ and off-diagonal entries less than $\beta K$ then
the entries of $A^N$ are all less than $K^{n_0} \binom{N+n_0+1}{N}
\beta^{N}$.
\end{lemma}
\begin{proof}
The entry $A^N(i,j)$ is the sum of all possible products of the form
$A(i , k_1) A(k_1, k_2) \cdots A(k_{N-1}, j)$. Since $A$ is
triangular, only products where $i\le k_1 \le k_2\le \cdots \le
k_{N-1} \le j$ are nonzero. There are at most $\binom{N+n_0-1}{N}$
nonzero products in the sum. We have the bounds
$A(k_n,k_{n+1}) < K \beta$ for $k_n < k_{n+1}$ and
$A(k_n,k_{n+1}) < \beta$ for $k_n = k_{n+1}$. There are at most $n_0$
terms $A(k_n,k_{n+1})$ in each product with $k_n < k_{n+1}$. Therefore
each term $A^N(i,j)$ is less than $K^{n_0}\binom{N+n_0-1}{N} \beta^N$.
\end{proof}
\begin{lemma}\label{lem:A1}
For all $n,k \geq 1$,
$$\binom{n+k-1}{k} < n (1+ k/n)^n (1+n/k)^k.$$
\end{lemma}
\begin{proof}
We have the following estimates on $\log (n!) = \sum_{i=1}^n \log i$
\begin{equation*}
\int_{1}^{n} \log x dx < \log (n!) < \int_{1}^{n+1} \log x dx.
\end{equation*}
Plugging these in we obtain
\begin{equation*}
\begin{split}
\log \binom{n+k-1}{k} < (n+k) \log(n+k) - k \log k - (n-1) \log(n-1) -2.
\end{split}
\end{equation*}
Using the inequality $(n-1) \log(n-1) +2 > (n-1) \log n$
and combining terms,
\begin{equation*}
\log \binom{n+k-1}{k} < n \log (1+ k/n) + k \log (1+n/k) + \log n.
\end{equation*}
This gives the inequality.
\end{proof}
\bibliography{spectra}
\end{document}
%%%%%%%%%%%%%%%%%% CUT HERE %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%% Top of spectra.bib %%%%%%%%%%%%%%%%%%%%%%%%%%%%
@book {BePl,
AUTHOR = {A. Berman and R.J.Plemmons},
TITLE = {Nonnegative matrices in the mathematical sciences},
NOTE = {Revised reprint of the 1979 original},
SERIES = {Classics in Applied Mathematics},
VOLUME = {9},
PUBLISHER = {Society for Industrial and Applied Mathematics (SIAM),
Philadelphia, PA},
YEAR = {1994},
PAGES = {xx+340}
}
@Article{Bor,
AUTHOR = {Borobia, A.},
TITLE = {On the nonnegative eigenvalue problem},
NOTE = {Special issue honoring Miroslav Fiedler and Vlastimil
Pt\'ak},
JOURNAL = {Linear Algebra Appl.},
VOLUME = {223/224},
YEAR = {1995},
PAGES = {131--140}
}
@incollection {BGMY,
AUTHOR = {Block, L. and Guckenheimer, J. and Misiurewicz,
M. and Young, L. S.},
TITLE = {Periodic points and topological entropy of one-dimensional
maps},
BOOKTITLE = {Global theory of dynamical systems (Proc. Internat. Conf.,
Northwestern Univ., Evanston, Ill., 1979)},
PAGES = {18--34},
SERIES = {Lecture Notes in Math.},
VOLUME = {819},
PUBLISHER = {Springer, Berlin},
YEAR = {1980}
}
@incollection {B:matexp,
AUTHOR = {M. Boyle},
TITLE = {Symbolic dynamics and matrices},
BOOKTITLE = {Combinatorial and graph-theoretical problems in linear
algebra
(Minneapolis, MN, 1991)},
PAGES = {1--38},
SERIES = {IMA Vol. Math. Appl.},
VOLUME = {50},
PUBLISHER = {Springer, New York},
YEAR = {1993}
}
@Article{BHmat1,
AUTHOR = {Boyle, M. and Handelman, D.},
TITLE = {The spectra of nonnegative matrices via symbolic dynamics},
JOURNAL = {Ann. of Math. (2)},
VOLUME = {133},
YEAR = {1991},
NUMBER = {2},
PAGES = {249--316}
}
@article {BHmat2,
AUTHOR = {M. Boyle and D. Handelman},
TITLE = {Algebraic shift equivalence and primitive matrices},
JOURNAL = {Trans. Amer. Math. Soc.},
VOLUME = {336},
YEAR = {1993},
NUMBER = {1},
PAGES = {121--149}
}
@Article{Ciarlet,
AUTHOR = {Ciarlet, P. G.},
TITLE = {Some results in the theory of nonnegative matrices},
JOURNAL = {Linear Algebra and Appl.},
VOLUME = {1},
YEAR = {1968},
NUMBER = {1},
PAGES = {139--152}
}
@Book{DL,
author = {D. B. Damiano and J. B. Little },
title = {A Course in Linear Algebra},
publisher = {Harcourt Brace Jovanavich},
year = {1988},
OPTkey = {},
OPTeditor = {},
OPTvolume = {},
OPTnumber = {},
OPTseries = {},
OPTaddress = {},
OPTedition = {},
OPTmonth = {},
OPTnote = {},
OPTannote = {}
}
@Article{Fiedler,
AUTHOR = {Fiedler, M.},
TITLE = {Eigenvalues of nonnegative symmetric matrices},
JOURNAL = {Linear Algebra and Appl.},
VOLUME = {9},
YEAR = {1974},
PAGES = {119--142}
}
@Article{Fri,
author = {S. Friedland},
TITLE = {On an inverse problem for nonnegative and eventually
nonnegative matrices},
JOURNAL = {Israel J. Math.},
VOLUME = {29},
YEAR = {1978},
NUMBER = {1},
PAGES = {43--60}
}
@article {Guo,
AUTHOR = {Wuwen, G.},
TITLE = {Eigenvalues of nonnegative matrices},
JOURNAL = {Linear Algebra Appl.},
VOLUME = {266},
YEAR = {1997},
PAGES = {261--270}
}
@Article{Jo,
AUTHOR = {Johnson, C. R.},
TITLE = {Row stochastic matrices similar to doubly stochastic
matrices},
JOURNAL = {Linear and Multilinear Algebra},
VOLUME = {10},
YEAR = {1981},
NUMBER = {2},
PAGES = {113--130}
}
@Article{JLL,
author = {C. R. Johnson and T. J. Laffey and R. Loewy},
TITLE = {The real and the symmetric nonnegative inverse eigenvalue
problems are different},
JOURNAL = {Proc. Amer. Math. Soc.},
VOLUME = {124},
YEAR = {1996},
NUMBER = {12},
PAGES = {3647--3651}
}
@Article{Kellog,
author = {R. B. Kellogg},
TITLE = {Matrices similar to a positive or essentially positive
matrix},
JOURNAL = {Linear Algebra and Appl.},
VOLUME = {4},
YEAR = {1971},
PAGES = {191--204}
}
@Article{KR:irred,
AUTHOR = {Kim, K. H. and Roush, F. W.},
TITLE = {The {W}illiams conjecture is false for irreducible
subshifts},
JOURNAL = {Electron. Res. Announc. Amer. Math. Soc.},
FJOURNAL = {Electronic Research Announcements of the American
Mathematical
Society},
VOLUME = {3},
YEAR = {1997},
PAGES = {105--109 (electronic)}
}
@Article{KR:red,
AUTHOR = {Kim, K. H. and Roush, F. W.},
TITLE = {Williams's conjecture is false for reducible subshifts},
JOURNAL = {J. Amer. Math. Soc.},
FJOURNAL = {Journal of the American Mathematical Society},
VOLUME = {5},
YEAR = {1992},
NUMBER = {1},
PAGES = {213--215}
}
@Article{KRW,
AUTHOR = {Kim, K. H. and Roush, F. W. and Wagoner, J. B.},
TITLE = {Inert actions on periodic points},
JOURNAL = {Electron. Res. Announc. Amer. Math. Soc.},
FJOURNAL = {Electronic Research Announcements of the American
Mathematical
Society},
VOLUME = {3},
YEAR = {1997},
PAGES = {55--62 (electronic)}
}
@article {Lind:ent2,
AUTHOR = {Lind, D. A.},
TITLE = {The entropies of topological {M}arkov shifts and a related
class of algebraic integers},
JOURNAL = {Ergodic Theory Dynamical Systems},
VOLUME = {4},
YEAR = {1984},
NUMBER = {2},
PAGES = {283--300},
}
@article {Lind:ent1,
AUTHOR = {Lind, D. A.},
TITLE = {Entropies and factorizations of topological {M}arkov
shifts},
JOURNAL = {Bull. Amer. Math. Soc. (N.S.)},
VOLUME = {9},
YEAR = {1983},
NUMBER = {2},
PAGES = {219--222},
}
@Book{LM,
author = {D. Lind and B. Marcus},
TITLE = {An introduction to symbolic dynamics and coding},
PUBLISHER = {Cambridge University Press, Cambridge},
YEAR = {1995},
PAGES = {xvi+495}
}
@Article{LLon,
AUTHOR = {Loewy, R. and London, D.},
TITLE = {A note on an inverse problem for nonnegative matrices},
JOURNAL = {Linear and Multilinear Algebra},
VOLUME = {6},
YEAR = {1978/79},
NUMBER = {1},
PAGES = {83--90}
}
@article {MT,
AUTHOR = {Marcus, B. and Tuncel, S.},
TITLE = {The weight-per-symbol polytope and scaffolds of invariants
associated with {M}arkov chains},
JOURNAL = {Ergodic Theory Dynamical Systems},
VOLUME = {11},
YEAR = {1991},
NUMBER = {1},
PAGES = {129--180}
}
@book {Minc,
AUTHOR = {H. Minc},
TITLE = {Nonnegative matrices},
SERIES = {Wiley-Interscience Series in Discrete Mathematics and
Optimization},
NOTE = {A Wiley-Interscience Publication},
PUBLISHER = {John Wiley \& Sons, Inc., New York},
YEAR = {1988},
PAGES = {xiv+206}
}
@Article{Perfect,
AUTHOR = {Perfect, H.},
TITLE = {Methods of constructing certain stochastic matrices},
JOURNAL = {Duke Math. J.},
VOLUME = {20},
YEAR = {1953},
PAGES = {395--404}
}
@Article{Perrin,
author = {D. Perrin},
TITLE = {On positive matrices},
NOTE = {Discrete mathematics and applications to computer science
(Marseille, 1989)},
JOURNAL = {Theoret. Comput. Sci.},
VOLUME = {94},
YEAR = {1992},
NUMBER = {2},
PAGES = {357--366}
}
@Article{Salz,
AUTHOR = {Salzmann, F. L.},
TITLE = {A note on eigenvalues of nonnegative matrices},
JOURNAL = {Linear Algebra and Appl.},
VOLUME = {5},
YEAR = {1972},
PAGES = {329--338}
}
@article {Shannon,
AUTHOR = {Shannon, C. E.},
TITLE = {A mathematical theory of communication},
JOURNAL = {Bell System Tech. J.},
VOLUME = {27},
YEAR = {1948},
PAGES = {379--423, 623--656},
}
@Article{Soules,
AUTHOR = {Soules, G. W.},
TITLE = {Constructing symmetric nonnegative matrices},
JOURNAL = {Linear and Multilinear Algebra},
VOLUME = {13},
YEAR = {1983},
NUMBER = {3},
PAGES = {241--251}
}
@Article{Suli,
AUTHOR = {Sule{\u\i}manova, H. R.},
TITLE = {Stochastic matrices with real characteristic numbers},
JOURNAL = {Doklady Akad. Nauk SSSR (N.S.)},
VOLUME = {66},
YEAR = {1949},
PAGES = {343--345}
}
@article {Will,
AUTHOR = {Williams, R. F.},
TITLE = {Classification of subshifts of finite type},
JOURNAL = {Ann. of Math. (2)},
VOLUME = {98},
YEAR = {1973},
PAGES = {120--153; errata, ibid. (2) {\bf 99} (1974), 380--381}
}