text:
\begin{document}

\vskip 1pc

\title{Topological entropy and AF subalgebras of graph
$C^*$-algebras}

\author[Ja A Jeong]{Ja A Jeong$^{\dagger}$}
\thanks{$^{\dagger}$Partially supported by KOSEF R14-2003-006-01000-0}
\address{
Mathematical Sciences Division\\
BK21, Seoul National University\\
Seoul, 151--742\\
Korea, email: jajeong\-@\-math.\-snu.\-ac.\-kr }
\author[Gi Hyun Park]{Gi Hyun Park$^{\ddagger}$}
\thanks{$^{\ddagger}$Partially supported by KOSEF  R01-2001-000-00001-0}
\address{
Department of Mathematics\\
Hanshin University\\
Osan, 447--791\\
Korea, email: ghpark\-@\-hanshin.\-ac.\-kr }
\date{}
\subjclass[2000]{46L05, 46L55}

\begin{abstract}   Let $\mathcal A_E$ be the canonical AF subalgebra of
a graph $C^*$-algebra $C^*(E)$   associated with a locally finite
directed graph $E$. For Brown-Voiculescu's topological entropy
$ht(\Phi_E)$ of the canonical completely positive map $\Phi_E$ on
$C^*(E)$,  $ht(\Phi_E)=ht(\Phi_E|_{\mathcal A_E})=h_l(E)=h_b(E)$
is known to hold for a finite graph $E$, where $h_l(E)$ is the
loop entropy of Gurevic and $h_b(E)$ is the block entropy of
Salama. For an irreducible infinite graph $E$, the inequality
$h_l(E)\leq ht(\Phi_E|_{\mathcal A_E})$ has been known recently.
It is shown in this paper that
$$ht(\Phi_E|_{\mathcal A_E})\leq \max\{ h_b(E), h_b(\,{}^{t}E)\},$$
where  ${}^tE$ is  the graph $E$ with the direction  of  the edges
reversed. Some Irreducible infinite graphs  $E_p(p>1)$ with
$ht(\Phi_E|_{\mathcal A_{E_p}})=\log p$ are also examined.
\end{abstract}

\maketitle

\setcounter{equation}{0}

\section{Introduction}

 Voiculescu \cite{Vo} introduced a notion of topological
entropy $ht(\alpha)$ for an automorphism $\alpha$ of a nuclear
unital $C^*$-algebra $A$ to measure the growth of $\alpha^n$ as
$n\to \infty$ using the fact that a nuclear $C^*$-algebra has the
completely positive approximation property. The definition extends
very well to automorphisms of exact $C^*$-algebras (as done by
Brown in \cite{Br}) due to the deep result by Kirchberg \cite{Kr}
that exact $C^*$-algebras are nuclearly embeddable. But without
effort one can define $ht(\Phi)$ even for a completely positive
(cp) map on an exact $C^*$-algebra as described in \cite{BG}.
Since a $C^*$-subalgebra of an exact $C^*$-algebra is always
exact, if $\Phi:A\to A$ is a cp map  on an exact $C^*$-algebra $A$
and $B$ is a $\Phi$-invariant $C^*$-subalgebra of $A$ then
$ht(\Phi|_B)$ can be defined and
 the monotonicity $ht(\Phi|_B)\leq
ht(\Phi)$  holds.

  The topological entropy has been computed in several cases, for
  example, the equality $ht(\alpha *\beta)=\max\{ ht(\alpha),
  ht(\beta)\}$ for the reduced free product automorphism
  $\alpha *\beta$ was proved in
  \cite{BDS}, when the free product is with amalgamation over a
  finite dimensional $C^*$-algebra.  Also Dykema  \cite{Dy}  showed that
  $ht(\alpha)=0$ for certain classes of automorphisms $\alpha$ of
  reduced amalgamated free products of $C^*$-algebras, which turns
  out to
  extend St\o rmer's result \cite{St} that the Connes-St\o rmer entropy of
  the free shift automorphism of the II${}_1$-factor $L(F_\infty)$ is
  zero.

In this paper we are concerned  with  the topological entropy of
the shift type cp maps on $C^*$-algebras arising from directed
graphs.
 A typical one  is the canonical cp map $\Phi_A:\mathcal O_A\to \mathcal O_A$
of the Cuntz Krieger algebra   $\mathcal O_A$ given by
$$\Phi_A(x)=\sum_{i=1}^n s_i x
 s_i^*,$$ where $s_1, \dots, s_n$ are the partial isometries that
 generate  $\mathcal O_A$. The reason we call $\Phi_A$ shift type  is
 that  $\mathcal O_A$ contains a $\Phi_A$-invariant commutative
 $C^*$-subalgebra $\mathcal D_A$
which is isomorphic to $C(X_A)$ in such a way
 that the restriction $\Phi_A|_{\mathcal D_A}$ corresponds to the shift map
 $\sigma_{X_A}$ on the (compact) shift space $X_A$ associated
 with the incidence matrix $A$.
 The topological  entropy of $\Phi_A$ is then computed
 (see \cite{Cd}, \cite{BG}, \cite{PWY})
  as $ht(\Phi_A)=\log r(A)$ ($r(A)$ is the spectral radius of  $A$).
  But  $\log r(A)=h_{top}(X_A)$ is a well known
   fact, so that one can deduce by  \cite{De} that
   $ht(\Phi_A)=ht(\Phi_A|_{\mathcal D_A}).$
On the other hand, $\mathcal O_A$ also contains another important
$\Phi_A$-invariant  $C^*$-subalgebra $\mathcal A_A$ which is an AF
algebra with $\mathcal D_A\subset \mathcal A_A$. Thus by
monotonicity of entropy, we have $ht(\Phi_A)=ht(\Phi_A|_{\mathcal
A_A})=ht(\Phi_A|_{\mathcal D_A}).$

The Cuntz-Krieger algebras $\mathcal O_A$ are now well understood
as graph $C^*$-algebras $C^*(E)=C^*(s_e,p_v)$ associated with
finite directed graphs $E$ and  the cp
 map $\Phi_A$ of $\mathcal O_A$  is interpreted as the  map
$\Phi_E:C^*(E)\to C^*(E)$ given by $\Phi_E(x)=\sum_{e\in E^1} s_e
x s_e^*.$ Hence if $E$ is a finite graph (possibly with sinks)
which contains an infinite path, it follows that
$ht(\Phi_E)=ht(\Phi_E|_{\mathcal A_E})=ht(\Phi_E|_{\mathcal
D_E})=\log r(A_E)$, where $\mathcal A_E$ is the AF subalgebra of
$C^*(E)$ corresponding to $\mathcal A_A$ in $\mathcal O_A$ and
$A_E$ is the edge matrix of $E$ (see \cite{JP}).

If $E$ is infinite but locally finite then the map $\Phi_E$ is
known to be a contractive cp map, and furthermore if $E$ is
 irreducible and $\mathcal A_E$ is the canonical AF subalgebra of
 $C^*(E)$, the inequality
 $h_l(E)\leq ht(\Phi_E|_{\mathcal A_E})$ is known to hold \cite{JP}.
   The purpose of
the present paper is then to give an upper bound for
$ht(\Phi_E|_{\mathcal A_E})$ and we actually prove the following
(see Theorem 3.9)
$$ht(\Phi_E|_{\mathcal A_E})\leq \max \{h_b(E),h_b({}^t E)\}.$$
 In particular, for an irreducible infinite
 graph $E_p$ constructed in  \cite{Sa} so that
 $h_l(E_p)=h_b(E_p)=p>1$, we have
   $ht(\Phi_{E_p}|_{\mathcal A_{E_p}})=\log p$.

We believe that the result would be helpful to compute the entropy
$ht(\Phi_E)$ of  $\Phi_E$ on the whole graph $C^*$-algebra
$C^*(E)$.

\vskip 1pc
\section{Preliminaries}

\subsection{Graph $C^*$-algebras}
A (directed) graph is a quadruple $E=(E^0,E^1,r,s)$ of  the vertex
set $E^0$, the edge set $E^1$, and  the range, source maps
$r,s:E^1\to E^0$. A family $\{p_v,s_e\mid v\in E^0, e\in E^1 \}$
of mutually orthogonal projections $p_v$ and partial isometries
$s_e$  is called a {\it Cuntz-Krieger $E$-family} if the following
relations
hold; \begin{align*} &s_e^*s_e=p_v, \ \ s_es_e^*\leq p_{s(e)},\\
&p_v=\sum_{s(e)=v} s_es_e^*, \ \ \text{ if }
0<|s^{-1}(v)|<\infty.\end{align*} The {\it graph $C^*$-algebra}
$C^*(E)$ is then defined to be a $C^*$-algebra generated by a
universal Cuntz-Krieger $E$-family (see \cite{KPR}, \cite{BPRS}).
We call $E$  {\it locally finite} if each vertex receives and
emits only finitely many edges. Throughout this paper we consider
only locally finite graphs, and adopt the  notations  in
\cite{KPR}.
 If a finite path $\alpha\in E^*$ of length $|\alpha|>0$ is a
 return path, that is,
 $s(\alpha)=r(\alpha)$, then $\alpha$ is called a {\it loop} at $v=s(\alpha)$.
  A graph $E$ is said to be {\it irreducible} if for any two vertices $v,w$
there is a finite path $\alpha\in E^*$ with $s(\alpha)=v$ and
$r(\alpha)=w$. It is known that if $E$ is irreducible and every
loop has an exit then $C^*(E)$ is simple.

\subsection{Topological entropy of cp maps}

    Let $A$ be a $C^{*}$-algebra, $\pi:A \to B(H)$  a faithful
    $*$-representation, and  $Pf(A)$ be the set of all finite
    subsets of $A$. For $\omega\in Pf(A)$ and $\delta>0$, put
 \begin{align*}
 CPA(\pi,A)& = \{ (\phi, \psi, B) \mid \phi : A\to B, \psi : B \to B(H)
    \text{ are contractive cp maps }\\
  &\ \hskip 2cm  \text{  and } \dim B < \infty \},\\
    rcp(\pi,\omega,\delta)& =\inf \{ rank(B) \mid (\phi,\psi, B) \in
    CPA(\pi, A),\ \| \psi \circ \phi (x) - \pi (x) \| < \delta,\\
    & \ \hskip 2cm
    \text{ for all } x \in \omega \},\end{align*}
 where $rank(B)$ denotes the dimension
    of a maximal abelian subalgebra of $B$.

Since the cp $\delta$-rank $rcp(\pi,\omega,\delta)$ is independent
of the choice of $\pi$ (see \cite{Br}, \cite{BG}) and graph
$C^*$-algebras $C^*(E)$ are nuclear we may write $rcp(
\omega,\delta)$ for $rcp(\pi, \omega,\delta)$ assuming that
$C^*(E)\subset B(H)$  for a Hilbert space $H$.\vskip 1pc

\begin{dfn} \rm (\cite{Br}, \cite{BG})
    Let $A\subset B(H)$ be a $C^*$-algebra and  $\Phi:A\to A $
be  a cp map. Put
 \begin{align*} ht(\Phi,\omega,\delta) &=
\limsup_{n\to \infty} \frac{1}{n} \log\big( rcp(\,\cup_{i=0}^{n-1}
\Phi^{i}(\omega), \delta)\big)\\
ht(\Phi,\omega)&=\sup_{\delta>0}
ht(\Phi,\omega,\delta).\end{align*}
     Then $ht(\Phi):=\sup_{\omega\in Pf(A)}
ht(\Phi,\omega)$ is called the {\it topological entropy} of
 $\Phi$.
\end{dfn}

\vskip .5pc
\begin{remark} \rm We refer the reader to \cite{BG} and \cite{Br}
for the following useful properties  and  their proofs. Let $A$ be
an exact $C^*$-algebra and $\Phi:A\to A$ be a cp map.

\renewcommand{\theenumi}{\arabic{enumi}}
\renewcommand{\labelenumi}{{\theenumi}.}
\setlength{\itemsep}{10mm} \begin{enumerate}\item[(a)] If
 $\theta:A\to B$ is a
$C^*$-isomorphism then  $ht(\Phi)=ht(\theta\Phi\theta^{-1}).$

\item[(b)] Let $\tilde A$ be the unital $C^*$-algebra obtained by
adjoining a unit and $\tilde \Phi : \tilde A \to \tilde A$ be the
extension of $\Phi$. Then $ht(\tilde \Phi) =ht(\Phi).$

\item[(c)] If $A_0 \subset A$ is a $\Phi$-invariant
$C^*$-subalgebra of $A$, $ht( \Phi|_{A_0}) \leq ht(\Phi).$

\end{enumerate}
\end{remark}

 We will use the following Arveson's extension
theorem several times.

\vskip .5pc

\noindent {\bf Arveson Extension Theorem} (see \cite{Br}) Let $A$
be a unital $C^*$-algebra, $S\subset A$  a unital subspace with
$S=S^*$, and $\phi:S\to B$ be a contractive cp map where $B=B(H)$
or $dim(B)<\infty$. Then $\phi$ extends to a cp map
$\bar{\phi}:A\to B$. If $S$ is a $C^*$-subalgebra of $A$ then we
obtain a unital cp extension of $\phi$ even when $S$ does not
contain the unit of $A$.

\vskip 1pc

If $E$ is a locally finite graph, the map  $\Phi_E:C^*(E)\to
C^*(E)$, defined by
$$ \Phi_E(x)= \sum_{e\in E^1} s_e xs_e^*,$$ is well defined,
contractive, and completely positive \cite{JP}.
 For a finite
graph $E$, the topological entropy $ht(\Phi_E)$ has been obtained
as follows (see \cite{BG}, \cite{Cd}, \cite{PWY}, or  \cite{JP}).

\vskip 1pc
\begin{thm}
Let $E$ be a finite  graph possibly with sinks and $A_E$ be the
edge matrix of $E$. If  $E$ contains an infinite path  then
$$ht(\Phi_E)=\log r(A_E),$$ where $r(A_E)$ is the
spectral radius of $A_E$.
\end{thm}
\vskip .5pc

 By $h_{top}(X)$ we denote the topological entropy of a
compact space $(X,T)$ together with a continuous map $T:X\to X$
(for definition, see \cite[Definition 4.1.1]{LM} or
\cite[p.23]{Kt} ). Let $E$ be a locally finite infinite graph and
 $X_E$ the locally compact shift space of (one-sided) infinite paths
 with the one point compactification $\bar{X}_{E}$.
Then the first identity in the following theorem is shown for the
doubly infinite path space of $E$ by Gurevic \cite{Gu}. See
Definition 3.1 for $h_b(E)$.

\begin{thm}[\expandafter{\cite[Theorem 4.4]{JP}}]
Let $E$ be a locally finite irreducible infinite graph. Then
$$ h_{top}(\bar{X}_{E})=\sup_{E'}h_b(E')\,\leq \, ht(\Phi_E),$$
where the supremum  is taken over all the finite (irreducible)
subgraphs of $E$.
\end{thm}

\vskip 1pc

\section{Main results}
 Throughout this section $E$ will denote a locally
finite infinite graph unless stated otherwise.
 For a path $\alpha\in E^*$, let $\alpha^0$ be the set of
vertices lying on $\alpha=\alpha_1\cdots\alpha_n$, that is,
$\alpha^0=\{s(\alpha_1), r(\alpha_1), \dots , r(\alpha_n)\}$. For
a fixed vertex $v$  we consider the following subsets of finite
paths $E^n$ of length $n$.

\renewcommand{\theenumi}{\arabic{enumi}}
\renewcommand{\labelenumi}{{\theenumi}.}
\setlength{\itemsep}{10mm}
\begin{enumerate}
 \item [(i)]$E^n(v)=\{\alpha\in E^n\mid v\in \alpha^0\}$,
 \item[(ii)] $E_s^n(v)=\{\alpha\in E^n\mid s(\alpha)=v\}$,
 \item[(iii)] $E_{s}^n(v^\star)=\{\alpha \in E_s^n(v)\mid
r(\alpha_i)\neq v, \  1\leq i\leq n\}$,
 \item[(iv)] $E_l^n(v)=\{\alpha\in E^n\mid \alpha \text{ is a loop at }
v\}$.\end{enumerate} Similarly we can think of $E_r^n(v)$ and
$E_{r}^n(v^\star)$.

\renewcommand{\theenumi}{\arabic{enumi}}
\renewcommand{\labelenumi}{{\theenumi}.}
\setlength{\itemsep}{10mm}

\vskip 1pc \begin{dfn} Let $E$ be an irreducible graph and let
$v\in E^0$.
\begin{enumerate}
 \item[(a)]
 $h_l (E):=\limsup_n \frac{1}{n}\log |E_l^n(v)|$
 is called the {\it loop
entropy} of $E$.

 \vskip .5pc\noindent \item[(b)]  $h_{b} (E):=\limsup_n \frac{1}{n}
\log |E_s^n(v)|$ is called the {\it block entropy} of $E$.
\end{enumerate}\end{dfn}

\noindent Note  that both entropies $h_l(E)$ and  $h_b(E)$
 are independent of the choice of a
vertex $v$ \cite{Sa}.
    If ${}^tE$  denotes  the graph $E$ with the
direction of all edges  reversed, then clearly $h_l (E)=h_l
({}^tE)$ while $h_b(E)\neq h_b({}^t E)$ in general as we will see
in Example 3.3.

We will use the following notation for the infinite series with
coefficients from (i)-(iv) above.
\begin{enumerate}
\item[(i)$'$] $E(v,z):=\sum |E^n(v)|z^n,$
 \item[(ii)$'$] $E_s(v,z):=\sum |E_s^n(v)| z^n,$
\item[(iii)$'$] $E_{s}(v^\star,z):=\sum |E_{s}^n(v^\star)| z^n,$
\item[(iv)$'$] $E_l(v,z):=\sum |E_l^n(v)|z^n.$ \end{enumerate}

 We denote the
radius of convergence of the series $E_s(v^\star,z)$ by
$R_{E_s^\star}$. Thus
$$R_{E_s^\star}^{-1}=\limsup_{n\to \infty} \big|
E_s^n(v^\star)\big|^{1/n}.$$ Similarly $R_{E_r^\star}$ denotes the
radius of convergence of $E_r(v^\star,z):=\sum |E_{r}^n(v^\star)|
z^n$.

 \vskip 1pc
\begin{prop}[\cite{Sa}] If $E$ is an irreducible graph, then
 $$h_b(E)=\max\{ \log \big( R_{E^\star_{s}}^{-1}\big), \, h_l(E)\}.$$
 \end{prop}

\vskip 1pc \noindent  Note that if $E$ is irreducible then
 $h_b({}^tE)=\limsup \frac{1}{n} \log |E_r^n(v)|$ and so
  from the above proposition we have
$$h_b({}^tE)=\max\{\log \big( R_{E^\star_{r}}^{-1}\big), \, h_l(E)\}.$$

\vskip 1pc
 The following example shows that $h_b(E)\neq h_b({}^tE)$ in
 general.
\vskip 1pc
\begin{ex} For each pair of positive real numbers
$1<p\leq q$, \rm Salama \cite{Sa} constructed an irreducible
infinite graph $E_{p,q}$ with $$h_l(E_{p,q})=\log p\ \ \text{and}\
\ h_b(E_{p,q})=\log q.$$  For example,  the following graph
$E:=E_{2,8}$ satisfies $h_l(E)=\log 2$ and $h_b(E)=\log 8$.
 There are 8 edges from the vertex $n$ to the vertex $n+1$ for each $n\geq
 0$.

\setlength{\unitlength}{1.7cm}

\hspace*{6cm}
\begin{picture}(8,1.5)

\put(-3.25,0){\circle{0.5}}\put(-2.9,-0.28){$0$}
\put(-3,0){\circle*{0.07}}
 \put(-2.6,0.3){\circle*{0.07}} \put(-2.2,0.6){\circle*{0.07}}
\put(-1.8,0){\circle*{0.07}}\put(-1.85,-0.3){1}
\put(-0.6,0){\circle*{0.07}}\put(-0.65,-0.3){$2$}
\put(0.6,0){\circle*{0.07}}\put(0.55,-0.3){$3$}
\put(1.8,0){\circle*{0.07}}\put(1.75,-0.3){$4$}

\put(3,0){\circle*{0.07}}

 \put(-1.8,0.9){\circle*{0.07}}
\put(-1.4,0.9){\circle*{0.07}}\put(-1,0.9){\circle*{0.07}}

\put(-0.6,0.9){\circle*{0.07}}\put(-0.2,0.9){\circle*{0.07}}\put(0.2,0.9){\circle*{0.07}}
\put(0.6,0.9){\circle*{0.07}}
\put(1,0.9){\circle*{0.07}}\put(1.4,0.9){\circle*{0.07}}\put(1.8,0.9){\circle*{0.07}}
\put(2.2,0.9){\circle*{0.07}}\put(2.6,0.9){\circle*{0.07}}\put(3,0.9){\circle*{0.07}}

\put(-1.4,0.9){\vector(-1,0){0.3}}
\put(-1,0.9){\vector(-1,0){0.3}}
\put(-0.6,0.9){\vector(-1,0){0.3}}
\put(-0.2,0.9){\vector(-1,0){0.3}}
\put(0.2,0.9){\vector(-1,0){0.3}}
\put(0.6,0.9){\vector(-1,0){0.3}}

\put(1.0,0.9){\vector(-1,0){0.3}}

\put(1.4,0.9){\vector(-1,0){0.3}}

\put(1.8,0.9){\vector(-1,0){0.3}}

\put(2.2,0.9){\vector(-1,0){0.3}}

\put(2.6,0.9){\vector(-1,0){0.3}}

\put(3,0.9){\vector(-1,0){0.3}}

\put(-3.01,0.07){\vector(1,-2){0}}

\put(-2.9,0.02){\vector(1,0){1.0}}\put(-2.9,-0.02){\vector(1,0){1.0}}

\put(-1.7,0.02){\vector(1,0){1.0}}\put(-1.7,-0.02){\vector(1,0){1.0}}

\put(-0.5,0.02){\vector(1,0){1.0}}\put(-0.5,-0.02){\vector(1,0){1.0}}

\put(0.7,0.02){\vector(1,0){1.0}}\put(0.7,-0.02){\vector(1,0){1.0}}

\put(1.9,0.02){\vector(1,0){1.0}}\put(1.9,-0.02){\vector(1,0){1.0}}

\put(-1.8,0.1){\vector(0,1){0.7}}

\put(-0.6,0.1){\vector(0,1){0.7}}

\put(0.6,0.1){\vector(0,1){0.7}}

\put(1.8,0.1){\vector(0,1){0.7}}

\put(-2.6,0.3){\vector(-4,-3){0.3}}

\put(-2.2,0.6){\vector(-4,-3){0.3}}

\put(-1.8,0.9){\vector(-4,-3){0.3}}

\put(2.6,0.4){$\cdots\cdots\rightarrow$}

\put(-2.4,0.05){8}

\put(-1.2,0.05){8}\put(0,0.05){8}\put(1.2,0.05){8}\put(2.4,0.05){8}

\put(-3.5,0.7){$E$}
\end{picture}

\vskip 1cm \noindent Now we show that $$\log \big(
R_{E^\star_{r}}^{-1}\big) \leq h_l(E),$$ which then implies
$h_b({}^tE)=h_l(E)$ by the above proposition (hence
$h_b({}^tE)\neq h_b(E)$). For a fixed vertex $0$ we have
\begin{align*}R_{E^\star_r}^{-1}&=\limsup_{n\to \infty}|E_{r}^{n}(0^\star)|^{1/n}\\
&=\limsup_{n\to \infty}\big| \{\alpha\in E_r^n(0)\mid
s(\alpha_i)\neq 0, \text{ for } 1\leq i\leq n
\}\big|^{1/n}.\end{align*}
 With  $ n_{k+1}=4k+1\, (k\geq 0),$
$$|E_{r}^{n_{k+1}-1}(0^\star)|=|E_{r}^{4k}(0^\star)|
 =1+8^{k-1}+8^{k-4}+8^{k-7}+\cdots,$$
 and a computation gives
  $$\limsup_{k\to \infty} |E_{r}^{4k}(0^\star)|^{\frac{1}{4k}}= 8^{1/4}.$$
 But it is not hard to see that $$\limsup_{n\to \infty} |E_{r}^{n}(0^\star)|^{\frac{1}{n}}=
  \limsup_{k\to \infty} |E_{r}^{4k}(0^\star)|^{\frac{1}{4k}}\, ,$$
hence $\log (R_{f^\star_r}^{-1})=\log 8^{1/4}<\log2=h_l(E).$
\end{ex}

\vskip 1pc

\begin{lem} If $E$ is an irreducible graph then the value
$$ \limsup_{n\to \infty} \frac{1}{n} \log |E^n(v)|
$$ is independent
of the choice of a vertex $v$.
\end{lem}

\proof
 Let
$v,w$ be two vertices of $E$. Then there exist two paths $\mu\in
E^{k}$,
  $\nu\in E^{m}$ with $s(\mu)=r(\nu)=v$, $s(\nu)=r(\mu)=w$
  because $E$ is irreducible. We assume that $\mu$ and $\nu$ have
  the smallest length, respectively.
  If $\alpha=\alpha_1\alpha_2\cdots \alpha_n\in E^n(v)$ then with $i_0=\min \{i\mid
  s(\alpha_i)=v\}$
  write $\alpha=\alpha'\alpha''$, where
  $\alpha'=\alpha_1\cdots\alpha_{i_0-1}$ and
  $\alpha''=\alpha_{i_0}\cdots\alpha_n$ (if $i_0=1$,
  $\alpha=\alpha''$).
  Then the map $$E^n(v)\to E^{n+k+m}(w),\ \
  \alpha=\alpha'\alpha''\mapsto \alpha'\mu\nu\alpha''$$ is
  injective, hence $|E^n(v)|\leq |E^{n+k+m}(w)|$ for each
  $n$. Therefore \begin{align*}
  \limsup_{n\to \infty} \frac{1}{n} \log |E^n(v)|&\leq
  \limsup_{n\to \infty} \frac{1}{n} \log |E^{n+k+m}(w)|\\&\leq
  \limsup_{n\to \infty} \frac{1}{n} \log |E^n(w)|.\end{align*}
\endproof

\medbreak \vskip 1pc

\begin{prop} Let $E$ be an irreducible graph and $v_0\in E^0$.

\noindent {\rm (a)} If $E$ is  finite, then $$\limsup_{n\to
\infty} \frac{1}{n} \log |E_l^n(v_0)|=\limsup_{n\to \infty}
\frac{1}{n} \log |E^n|.$$

In particular, $h_l(E)=h_{b}(E)=h_{b}({}^tE).$

\noindent {\rm (b)} If $E$ is  infinite,  then
$$ \limsup_{n\to \infty} \frac{1}{n} \log |E^n(v_0)|
\ = \ \max \{h_b(E), \, h_b({}^tE)\}.$$
\end{prop}

\proof (a)  Let $E^0=\{v_0, v_1, \dots, v_{k-1}\}$. Since $E$ is
irreducible there exist finite paths $\{\mu_i,\, \nu_i\mid 0\leq
i\leq k-1\}$
 such that $ s(\mu_i)=r(\nu_i)=v_0$, $r(\mu_i)=v_i=s(\nu_i).$
 Suppose $|\mu_i|=m_i$, $|\nu_j|=l_j.$
     If $\alpha\in E^n$ is a path with $s(\alpha)=v_i$,
     $r(\alpha)=v_j$ then $\mu_i\alpha \nu_j\in E_l^{n+m_i+l_j}(v_0)$
     is a loop at $v_0$.
 The map $\alpha\mapsto \mu_i\alpha \nu_j$ is not necessarily injective, but
 there exist at most $k_0$ paths in $E^n$ that have the same image in
 $E_l^{n+m_i+l_j}(v_0)$ under the map, where $k_0=\max_{i,j}\{m_i+l_j\}$.
 Hence we  have
$$ |E^n|\leq k_0\cdot \big|\cup_{0\leq i,j\leq k-1}
 E_l^{n+m_i+l_j}(v_0)\big|
 \leq k_0 k^2 \max_{i,j}|E_l^{n+m_i+l_j}(v_0)|.$$
On the other hand, for each $n$, there exists a $k_n\in \{0,\dots
,k_0\}$ such that
$$|E_l^{n+k_n}(v_0)|=\max_{i,j}|E_l^{n+m_i+l_j}(v_0)|.$$
Then $|E^n|\leq k_0k^2|E_l^{n+k_n}(v_0)|$ and it follows that
$$\limsup_{n\to \infty}\frac{1}{n}\log |E^n| \leq \limsup_{n\to
\infty}\frac{1}{n}\log |E_l^n(v_0)|.$$

\noindent (b) Note first that
\begin{align*}
|E^n(v)| &= \big| \cup_{k=0}^n\{\alpha\beta\mid \alpha\in
E_{r}^k(v^\star),\, \beta\in E_s^{n-k}(v_0)\}\big|\\&=
\sum_{k=0}^n \big|E_{r}^k(v^\star)\big|\, \big| E_s^{n-k}(v)
\big|=\sum_{k=0}^n\big| ({}^tE)_{s}^k(v^\star)\big|\, \big|
E_s^{n-k}(v) \big|.\end{align*} Then
 \begin{align*}E(v,z)
 &=\sum_n \Big(\sum_{k=0}^n |({}^tE)_{s}^k(v^\star)|\, | E_s^{n-k}(v)
 |\Big)z^n\\
 &=\Big(\sum_n |({}^tE)_{s}^n(v^\star)|z^n \Big)\, \Big( \sum_n | E_s^{n}(v)|z^n\Big)\\
 &=({}^tE)_{s}(v^\star,z)\cdot E_s(v,z),\end{align*}
so that the radius  of convergence $R_E$ of $E(v,z)$ is equal to
  $\min \big\{ R_{({}^tE)^\star_s}, \,
 R_{E_s}\big\}.$
  Thus  $$R_E^{-1}=\max \big\{\,  R_{({}^tE)^\star_{s}}^{-1}, \,
 R_{E_s}^{-1}\,\big\}.$$
  But  Proposition 3.2 gives $$\log \big(R_{({}^tE)^\star_s}^{-1}\big)\leq
 h_b({}^tE),$$ and also by definition $\log (R_{E_s}^{-1})=h_b(E).$
 Therefore
 $$\limsup_{n\to \infty} \frac{1}{n} \log |E^n(v)|
 =\log (R_E^{-1})\leq \max \{h_b({}^tE),\, h_b(E)\}.$$
\endproof  \medbreak

\vskip 1pc

Let $E$ be an irreducible infinite graph and let $\mathcal D_E$ be
the commutative $C^*$-subalgebra of $C^*(E)$ generated by the
projections $\{p_\alpha=s_\alpha s_\alpha^*\mid \alpha\in E^*\}$.
Then $\mathcal D_E=\overline{\rm span}\{p_\alpha\mid \alpha\in
E^*\}$ and    the map
$$w: \mathcal D_E\to C_0(X_E),\ w(p_\alpha)=\chi_{[\alpha]},$$  is
a $C^*$-isomorphism \cite{JP}. Here $\chi_{[\alpha]}$ is the
characteristic function  on the cylinder  set $[\alpha]=\{\beta\in
X_E\mid \beta=\alpha\beta'\}$ which is both open and closed.
Furthermore, from the proof of Theorem 2.4 we know that
$h_{top}(\bar{X}_E)=ht(\Phi_E|_{\mathcal D_E}).$
   Put $$\mathcal A_E:=\overline{\rm span}\{\, s_\alpha s_\beta^*\,\mid\,
\alpha,\beta\in E^*, \ |\alpha|=|\beta|\,\}.$$ Then  $\mathcal
A_E$ is a $\Phi_E$-invariant AF $C^*$-subalgebra of $C^*(E)$ with
$\mathcal D_E\subset \mathcal A_E$, hence
$$ht(\Phi_E|_{\mathcal D_E})\leq ht(\Phi_E|_{\mathcal A_E}).$$
  Also, for each $v\in E^0$, $\mathcal
A_E$ contains a  $\Phi_E$-invariant AF subalgebra  $\mathcal
A_E(v)$, $$\mathcal A_E(v):=\overline{\rm span}\{\, s_\alpha
s_\beta^*\,\mid\, \,r(\alpha)=r(\beta)=v,\, |\alpha|=|\beta|\,
\}.$$

\vskip 1pc

\begin{lem} Let $v$ be a vertex of an irreducible  graph $E$ with
at least two vertices
 and let $ n\geq 1$.  Then the elements in the set $$\omega(n,v)=\big\{s_\alpha
s_\beta^*\, \big|\ \, r(\alpha)=r(\beta)=v,\, |\alpha|=|\beta|\leq
n \big\}$$ are linearly independent.
\end{lem}
\proof We prove the assertion by induction on $n$.
  For $n=1$, suppose $$x=\sum_{\substack{{e,f\in E^1}\\
  {r(e)=r(f)=v}}} \lambda_{ef}s_e s_f^*+\lambda_0 p_v=0.$$
  If $e_0$ and $f_0$ are edges with $r(e_0)=r(f_0)=v$ and
 either $s(e_0)\neq v$ or $s(f_0)\neq v$  then $s_{e_0}^*p_v
 s_{f_0}=0$, hence
$$0=s_{e_0}^* x s_{f_0}=\lambda_{e_0 f_0}(s_{e_0}^*s_{e_0}
)(s_{f_0}^*s_{f_0})=\lambda_{e_0 f_0}p_v,$$ thus $\lambda_{e_0
f_0}=0$. Similarly, $\lambda_{e f}=0$ if $e$ and $f$ are loops at
$v$ and $e\neq f$. Then $x$ becomes $$x=\sum_{e\in E_l^1(v)}
\lambda_{ee} s_e s_e^* +\lambda_0 p_v=0.$$
  By  irreducibility of $E$ and the assumption that $|E^0|>1$,
  there exists an edge $f$ with
  $s(f)=v, r(f)\neq v$. Then $s_f s_f^* x=\lambda_0 s_f
  s_f^*=0$, so that $\lambda_0=0$ and we have $x=\sum_{e\in E_l^1(v)}
   \lambda_{ee} s_e s_e^*=0.$ Since the projections
  $\{s_e s_e^*\mid e\in E_l^1(v)\}$  are mutually orthogonal, it
  follows that $\lambda_{ee}=0$ for each $e\in E_l^1(v)$.

  Now suppose that the assertion is
true for $n-1$. If
$$x=\sum_{\substack{{|\alpha|=|\beta|\leq
n}\\{r(\alpha)=r(\beta)=v}}} \lambda_{\alpha\beta} s_\alpha
s_\beta^*=0,\ \lambda_{\alpha\beta}\in \mathbb C,$$ then for an
edge $e\in E^1$ we have $$0=s_e^* x
s_e=\sum_{\substack{{\alpha=e\alpha'}\\{\beta=e\beta'}}}\lambda_{\alpha\beta}
s_e^* s_\alpha s_\beta^* s_e= \sum_{|\alpha'|=|\beta'|\leq n-1}
\lambda_{(e\alpha')(e\beta')} s_{\alpha'}(s_{\beta'})^*.$$
 Note that the elements $s_{\alpha'}(s_{\beta'})^*$ appearing in the sum
 are distinct. Thus
by induction hypothesis, one sees that
$\lambda_{(e\alpha')(e\beta')}=0$. But the edge $e$ was arbitrary,
and so we conclude that the coefficients $\lambda_{\alpha\beta}$
are all zero. \endproof  \medbreak

\vskip 1pc

\begin{prop} {\rm (cf. \cite[Proposition 2.6]{Br})}
Let $\Phi:A\to A$ be a  contractive cp map of an exact
$C^*$-algebra $A$. If $\{\omega_\lambda\}_{\lambda\in \Lambda}$ is
a net (partially ordered by inclusion) of finite subsets in $A$
such that the linear span of $\ \cup_{\lambda,l\in \mathbb
Z^+}\Phi^l(\omega_\lambda)$ is dense in $A$ then
$$ht(\Phi)=\sup_\lambda ht(\Phi, \omega_\lambda ).$$
\end{prop}

\vskip 1pc

\begin{thm}
 Let $E$ be an irreducible infinite graph. Then for each $v\in
 E^0$,
 $$ht(\Phi_E|_{\mathcal A_E(v)})\,\leq\,
 h_b({}^tE).$$
 \end{thm}

\proof  Let  $A_n(v)$ be the $C^*$-subalgebra of $\mathcal A_E(v)$
generated by  $\omega(n,v).$
 Then  from
\[ s_\alpha s_\beta^*\cdot s_\mu s_\nu^*=\left\{
\begin{array}{ll} s_{\alpha\mu'}s_\nu^*, & \text{if }\ \mu=\beta\mu',\\
s_\alpha s_{\nu\beta'}^*, & \text{if}\ \beta=\mu\beta',\\
0, & \text{otherwise,}
 \end{array} \right.   \] we see that $A_n(v)={\rm span}(\omega(n,v))$
 is finite dimensional.

 Since $\{\omega(n,v)\}_n$ is an increasing
sequence of finite subsets in $\mathcal A_E(v)$ such that  the
linear span of $\cup_n \omega(n,v)$ is dense in $\mathcal A_E(v)$,
 by Proposition 3.7 it suffices to show that
$$ ht(\Phi_E, \omega(n,v))\leq  h_b({}^tE), \ \ n\in \mathbb N.$$
    Set
$E_l^*(v):=\cup_{k\geq 0} E_l^k(v)$ and  $r(n):=|\,\cup_{k=0}^n
E_r^k(v)\,|.$
   Fix $n_0\in \mathbb N$, and define a map
$\phi:\omega(n_0,v)\to M_{r(n_0)}$  by
$$ \phi (s_\alpha
s_\beta^*)= \sum_{\substack{{|\alpha\gamma|\leq n_0}\\{\gamma\in
E_l^*(v)}}} e_{(\alpha\gamma)(\beta\gamma)},$$ where
$\{e_{\mu\nu}\}$ is the standard matrix units of of the matrix
algebra $M_{r(n_0)}$.
  Since the elements in $\omega({n_0},v)$ are linearly
independent by Lemma 3.6, one can extend the map to the linear map
$\phi: A_{n_0}(v)\to M_{r(n_0)}$.  Now we show that $\phi$ is in
fact a $*$-isomorphism. To prove that it is a $*$-homomorphism, we
only need to see that
$$\phi((s_\alpha s_\beta^*)(s_\mu s_\nu^*))=
\phi(s_\alpha s_\beta^*)\phi(s_\mu s_\nu^*).$$
   If
$\beta=\mu\beta'$,  then $s_\alpha s_\beta^* s_\mu
s_\nu^*=s_\alpha (s_{\nu\beta'})^*$
   and \begin{align*}\phi(s_\alpha
s_\beta^*)\phi(s_\mu s_\nu^*)&=\sum_{\substack{{|\alpha\gamma|\leq
n_0}\\{\gamma\in E_l^*(v)}}}
e_{(\alpha\gamma)(\mu\beta'\gamma)}\cdot
\sum_{\substack{{|\mu\delta|\leq n_0}\\{\delta\in E_l^*(v)}}}
e_{(\mu\delta)(\nu\delta)}\\
 &= \sum_{\substack{{|\alpha\gamma|\leq n_0}\\{\gamma\in E_l^*(v)}}}
e_{(\alpha\gamma)(\nu\beta'\gamma)}=\phi(s_\alpha
(s_{\nu\beta'})^*)=\phi(s_\alpha s_\beta^* s_\mu s_\nu^*).
\end{align*}
  If $\mu=\beta\mu'$, a similar proof works. Otherwise,
$\phi((s_\alpha s_\beta^*)(s_\mu s_\nu^*))=0= \phi(s_\alpha
s_\beta^*)\phi(s_\mu s_\nu^*).$
    In order to show that $\phi$ is injective, let
  $\phi(\sum_{\alpha,\beta}\lambda_{\alpha\beta}\, s_\alpha
  s_\beta^*)=0$. Then
  $$\sum_{\alpha,\beta}\lambda_{\alpha\beta}\phi(s_\alpha
  s_\beta^*)=\sum_{\alpha,\beta}\lambda_{\alpha\beta}
  \big(\sum_{\substack{{|\alpha\gamma|\leq {n_0}}\\{\gamma\in E_l^*(v)}}}
e_{(\alpha\gamma)(\beta\gamma)}\big)=0.$$
 But  the vectors,
 $\sum_{\substack{{|\alpha\gamma|\leq {n_0}}\\{\gamma\in E_l^*(v)}}}
e_{(\alpha\gamma)(\beta\gamma)}$ $(r(\alpha)=r(\beta)=v,\,
|\alpha|=|\beta|\leq {n_0}),$ are linearly independent in
$M_{r(n_0)}$. In fact, if
$A:=\sum_{\alpha,\beta}\lambda_{\alpha\beta}
  \big(\sum_{\substack{{|\alpha\gamma|\leq {n_0}}\\{\gamma\in E_l^*(v)}}}
e_{(\alpha\gamma)(\beta\gamma)}\big)=0,$ then
$e_{vv}Ae_{vv}=\lambda_{vv}e_{vv}=0$, that is, $\lambda_{vv}=0$,
and for any $\alpha,\beta\in E^1_r(v)$,
$e_{\alpha\alpha}Ae_{\beta\beta}=\lambda_{\alpha\beta}e_{\alpha\beta}=0$,
hence  $\lambda_{\alpha\beta}=0.$
   Repeating the process one has
$\lambda_{\alpha\beta}=0$ for any $\alpha,  \beta\in
\cup_{k=0}^{n_0} E^k_r(v).$
   Therefore
$\sum_{\alpha,\beta}\lambda_{\alpha\beta}\, s_\alpha s_\beta^*=0$,
and  the map $\phi$ is injective. The surjectivity of $\phi$
follows from
 $\dim(A_{n_0}(v))=r(n_0)^2$. We simply write $\phi$ for
   $\phi:A_{n_0+l}(v)\to M_{r(n_0+l)}$ $(l\geq 0)$,
   and $\bar\phi$ for its contractive cp
 extension to $\mathcal A_E(v)$ that exists by   Arveson's extension
 theorem.

 For each $n\in \mathbb N$ and  $0\leq l\leq n-1$, note that
  $$\cup_{l=0}^{n-1}\Phi_E^l(\omega(n_0,v))\,\subseteq \,{\rm
 span}(\omega(n_0+n-1,v)).$$
 Then the element
 $$(\bar\phi,\,\psi:=\phi^{-1}\, ,M_{r(n_0+n-1)})
 \in CPA(id,\mathcal A_E(v))$$ satisfies
 $\psi\circ\bar\phi|_{\omega(n_0+n-1,v)}=id_{\omega(n_0+n-1,v)}.$ Thus for
 each $\delta>0$
$$rcp(id,\omega(n_0+n-1,v),\delta)\leq r(n_0+n-1),$$ and so
\begin{align*}ht(\Phi_E|_{\mathcal A_E(v)}, \omega(n_0,v),\delta)&\leq
\limsup_{n\to \infty}\frac{1}{n}\log (r(n_0+n-1))\\
&=\limsup_{n\to \infty}\frac{1}{n}\log (r(n))\\
&=\limsup_{n\to \infty}\frac{1}{n}\log \big|\,\cup_{k=0}^n E_r^k(v)\,\big|\\
&=h_b({}^tE).\end{align*} For the last equality, note that if
$k\leq n$ then $ \big|\, E_r^k(v)\,\big|\leq \big|\,
E_r^n(v)\,\big|,$
 hence $\big|\,\cup_{k=0}^n E_r^k(v)\,\big|\leq (n+1)\cdot
 \big|\,E_r^n(v)\,\big|.$
\endproof  \medbreak

\vskip 1pc Since  $h_l (E)=\sup_{E'\subset E}h(X_{E'})$ is well
known (see \cite[Proposition 7.2.6]{Kt}), we see from Theorem 2.4
and its proof that $h_l(E)\leq ht(\Phi_E|_{\mathcal A_E})$ holds.
The following theorem gives an upper bound for
$ht(\Phi_E|_{\mathcal A_E})$.

\vskip 1pc
\begin{thm} Let $E$ be an irreducible infinite graph and $\mathcal A_E$ be
the AF subalgebra of  $C^*(E)$ generated by the partial isometries
$\{s_\alpha s_\beta^*\mid \alpha, \beta\in E^*,
|\alpha|=|\beta|\}$. Then
$$ht(\Phi_E|_{\mathcal A_E}) \leq \ \max\{h_b({}^t E), h_b(E)\}.$$
\end{thm}

\proof  Let $E^0=\{v_1, v_2, \cdots\}$. For each $n_0\in \mathbb
N$ and $n_1\in \mathbb Z^+=\{0\}\cup \mathbb N$, put
\begin{align*}
\omega(n_0,n_1)&:=\Big\{s_\alpha s_\beta^*\,\big|\,
\alpha,\beta\in
E^{n_1}, r(\alpha)=r(\beta)\in \{ v_1,\cdots, v_{n_0}\} \Big\},\\
\omega_\Sigma  (n_0,n_1)&:=\Big\{ \sum  s_{\alpha_i}
s_{\beta_i}^*\, \big |\, s_{\alpha_i} s_{\beta_i}^*\in
\omega(n_0,n_1)\Big\}.\end{align*}
  Note that $\omega_\Sigma  (n_0,n_1)$ is not the linear span of $\omega(n_0,n_1)$.
  Then $\{\omega_\Sigma (n_0,n_1)\mid n_0\in \mathbb N,n_1\in \mathbb Z^+\}$ is a
  net of finite subsets in $\mathcal A_E$ which is
  partially ordered by  inclusion. In fact, given two finite sets
  $\omega_\Sigma (n_0,n_1)$, $\omega_\Sigma (m_0,m_1)$ ($n_1\leq
  m_1$), one may write each element $s_\alpha s_\beta^*\in \omega
  (n_0,n_1)$ as $$s_\alpha s_\beta^*=
  s_{\alpha} (\sum_{|\mu|=m_1-n_1} s_\mu s_\mu^*) s_\beta^*=
  \sum  s_{\alpha\mu} (s_{\beta\mu})^*\in \omega_\Sigma
  (m_2,m_1),$$
where $m_2>\max \{n_0, m_0\}$ is an integer large enough so that
$r(\alpha\mu)\in \{v_1, \cdots, v_{m_2}\}$ for any $\alpha\mu$
appearing in the last sum, then clearly $\omega_\Sigma
(n_0,n_1)\cup\omega_\Sigma (m_0,m_1)$ is contained in
$\omega_\Sigma (m_2,m_1).$

   Since the linear span of the set $\cup_{n_0,n_1,n}\Phi_E^n (\omega_\Sigma
   (n_0,n_1))$ is dense in $\mathcal A_E$, by Proposition 3.7, we
   show that for each finite set  $\omega_\Sigma(n_0,n_1)$,
$$ht(\Phi_E,\omega_\Sigma (n_0,n_1))\,\leq\, \max\{h_b({}^t E), h_b(E)\}.$$
If $s_\alpha s_\beta^*\in \omega(n_0,n_1)$,
$r(\alpha)=r(\beta)=v$,  then for $l\leq n-1$,
$$\Phi_E^l(s_\alpha s_\beta^*)=\sum_{|\mu|=l} s_{\mu\alpha}
s_{\mu\beta}^*=\sum_{|\mu|=l}s_{\mu\alpha}(\sum_{\substack{{|\nu|=n-l}\\
{s(\nu)=v}} } s_\nu s_\nu^*) s_{\mu\beta}^*=
\sum_{\substack{{|\mu\alpha\nu|=n+n_1}\\{|\mu|=l}}}
s_{\mu\alpha\nu}
(s_{\mu\beta\nu})^*,$$ because $p_v=\sum_{\substack{{|\nu|=n-l}\\
{s(\nu)=v}} } s_\nu s_\nu^*.$
  Hence one sees  that
$$\cup_{i=0}^{n-1}
\Phi_E^i(\omega_\Sigma(n_0,n_1)) \subseteq\   \Big\{
\sum_{|\mu\alpha\nu|=n+n_1}s_{\mu\alpha\nu}
(s_{\mu\beta\nu})^*\,\big|\, s_\alpha s_\beta^*\in
\omega(n_0,n_1)\Big\}.$$
 Since the set $\{s_{\mu}s_\nu^*\mid \mu,\nu\in
\cup_{i=1}^{n_0} E^{n_1+n}(v_i)\}$ forms a matrix units, it
generates the $C^*$-subalgebra of $\mathcal A_E$ which is
isomorphic to $M_{k_n}$, where $k_n=|\cup_{i=1}^{n_0}
E^{n_1+n}(v_i)|$. Let
 $$\rho_n:{\rm span}\{s_\alpha s_\beta^*\mid \alpha,\beta\in
\cup_{i=1}^{n_0} E^{n_1+n}(v_i)\}\to M_{k_n}$$ be a
$*$-isomorphism with the inverse $\rho^{-1}$. Then by Arveson's
extension theorem $\rho$ extends to a contractive cp map
$\bar{\rho}:\mathcal A_E\to M_{k_n}$, so that we obtain an element
$(\bar{\rho},\rho^{-1},M_{k_n})\in CPA(id, \mathcal A_E)$ such
that $\|\rho^{-1}\circ\bar{\rho}(x)-x\|=0$ if
$$ x\ \in
\cup_{i=0}^{n-1} \Phi_E^i(\omega_\Sigma(n_0,n_1)) \subseteq   \
{\rm span}\{s_\alpha s_\beta^*\mid \alpha,\beta\in
\cup_{i=1}^{n_0} E^{n_1+n}(v_i)\}.$$ Hence
$$rcp\big(\cup_{i=0}^{n-1} \Phi_E^i(\omega_\Sigma(n_0,n_1)),\,\delta\big)
\,\leq \, k_n$$ holds for
any $\delta>0$.
 Thus
$$ht(\Phi_E,\omega_\Sigma (n_0,n_1))\,\leq\, \limsup_{n\to \infty}
\frac{1}{n} \log (k_n).$$
 On the other hand, the irreducibility of $E$ implies that there is
 an $N$ such that  $|E^{n_1+n}(v_i)|\leq |E^{n_1+n+N}(v_1)|$
 for $1\leq i\leq n_0$. Hence $k_n=|\cup_{i=1}^{n_0} E^{n_1+n}(v_i)|\leq
 n_0 |E^{n_1+n+N}(v_1)|.$
Therefore
 $$\limsup_{n\to \infty} \frac{1}{n} \log
 k_n \leq \limsup_{n\to \infty} \frac{1}{n} \log
 |E^{n}(v_1)|,$$ and
the assertion then follows from Proposition 3.5(b).
 \endproof  \medbreak

\vskip 1pc
\begin{ex} \rm Let $E:=E_{\{r_n\},\{l_n\}}$ be a Salama's infinite
irreducible graph (see \cite{Sa}). We assume here that $l_n+1\leq
l_{n+1}$ for each $n$. There are $r_k$ edges from the vertex $k-1$
to $k$, and there is only one path (of length $l_k-l_{k-1}$) from
the vertex $v_k$ to $v_{k-1}$.

\setlength{\unitlength}{1.7cm}

\hspace*{6cm}
\begin{picture}(8,1.7)

\put(-3.25,0){\circle{0.5}}\put(-2.9,-0.28){$0$}
\put(-3,0){\circle*{0.07}}
 \put(-2.6,0.3){\circle*{0.07}} \put(-2.2,0.55){$\cdot$}
\put(-1.8,0){\circle*{0.07}}\put(-1.85,-0.3){1}
\put(-1.85,1){$v_1$}
\put(-0.6,0){\circle*{0.07}}\put(-0.65,-0.3){$2$}\put(-0.65,1){$v_2$}
\put(0.6,0){\circle*{0.07}}\put(0.55,-0.3){$3$}\put(0.55,1){$v_3$}

\put(1.8,0){\circle*{0.07}}\put(1.75,-0.3){$4$}\put(1.75,1){$v_4$}

\put(3,0){\circle*{0.07}}

 \put(-1.8,0.9){\circle*{0.07}}
\put(-1.4,0.9){\circle*{0.07}}\put(-1.04,0.86){$\cdot$}

\put(-0.6,0.9){\circle*{0.07}}\put(-0.2,0.9){\circle*{0.07}}\put(0.18,0.86){$\cdot$}
\put(0.6,0.9){\circle*{0.07}}
\put(1,0.9){\circle*{0.07}}\put(1.35,0.86){$\cdot$}\put(1.8,0.9){\circle*{0.07}}
\put(2.2,0.9){\circle*{0.07}}\put(2.6,0.9){\circle*{0.07}}\put(3,0.9){\circle*{0.07}}

\put(-1.4,0.9){\vector(-1,0){0.3}} \put(-1.3,0.9){$\dots$}
\put(-0.6,0.9){\vector(-1,0){0.3}}
\put(-0.2,0.9){\vector(-1,0){0.3}} \put(-0.1,0.9){$\dots$}
\put(0.6,0.9){\vector(-1,0){0.3}}

\put(1.0,0.9){\vector(-1,0){0.3}}

\put(1.1,0.9){$\dots$}

\put(1.8,0.9){\vector(-1,0){0.3}}

\put(2.2,0.9){\vector(-1,0){0.3}}

\put(2.3,0.9){$\dots$}

\put(3,0.9){\vector(-1,0){0.3}}

\put(-3.01,0.07){\vector(1,-2){0}}

\put(-2.9,0.02){\vector(1,0){1.0}}\put(-2.9,-0.02){\vector(1,0){1.0}}

\put(-1.7,0.02){\vector(1,0){1.0}}\put(-1.7,-0.02){\vector(1,0){1.0}}

\put(-0.5,0.02){\vector(1,0){1.0}}\put(-0.5,-0.02){\vector(1,0){1.0}}

\put(0.7,0.02){\vector(1,0){1.0}}\put(0.7,-0.02){\vector(1,0){1.0}}

\put(1.9,0.02){\vector(1,0){1.0}}\put(1.9,-0.02){\vector(1,0){1.0}}

\put(-1.8,0.1){\vector(0,1){0.7}}

\put(-0.6,0.1){\vector(0,1){0.7}}

\put(0.6,0.1){\vector(0,1){0.7}}

\put(1.8,0.1){\vector(0,1){0.7}}

\put(-2.6,0.3){\vector(-4,-3){0.3}}

\put(-2.3,0.47){$\cdot$}

\put(-2.4,0.4){$\cdot$}

\put(-2.5,0.33){$\cdot$}

\put(-1.8,0.9){\vector(-4,-3){0.3}}

\put(2,0.4){$\cdots\cdots\rightarrow$}

\put(-2.4,0.06){$r_1$}

\put(-1.2,0.06){$r_2$}\put(0,0.06){$r_3$}\put(1.2,0.06){$r_4$}\put(2.4,0.06){$r_5$}

\put(-3.5,1.0){$E$}

\put(-2.8,0.6){$l_1-1$}

\put(-1.4,1){$l_2-l_1$}

\put(-0.2,1){$l_3-l_2$}

\put(1,1){$l_4-l_3$}
\end{picture}

\vskip 1cm

\noindent Note that for each $n$, $|E^n_r(0^\star)|\leq
|E^n_s(0^\star)|$, which then implies by Proposition 3.2 that
$$h_b({}^tE)\leq h_b(E).$$ Thus
from Theorem 3.9, we have $$ht(\Phi_E|_{\mathcal A_E})\leq
h_b(E).$$
   In particular, if  $E_p:=E_{p,p}$ $(p>1)$ is an
   irreducible infinite graph of Salama satisfying
  $h_l(E_p)=h_b(E_p)=\log p,$  we have
 $$ht(\Phi_{E_p}|_{\mathcal
A_{E_p}})=\log p.$$
\end{ex}

 \vskip 1.5pc


TITLE: Equation for reducing leave to zero
QUESTION [5 upvotes]: I'm not a mathematician at all, but I'm looking for a formula that will help with the following problem:
It's coming up to Christmas and our employees want to take leave, but some employees will have accrued less leave than than the amount they wish to take in which case they are entitled to take all of their leave and the rest will be unpaid leave.
The problem is, that for every hour of leave paid to an employee, they are entitled to accrue an additional 0.038462 hours of leave, so as they take leave, they also accrue leave, which in turn they are entitled to take. The problem is, this makes it very hard to work out how much leave to give them so that their leave balance comes to 0
To give an example, I have an employee that currently has 10 hours leave but wants to take 20 hours all up.
Since he takes 10 hours leave, he will accrue 10 x 0.038462 in leave for that pay run. So he's actually is entitled to take 10.38462 hours leave.
So I change his leave taken to be 10.38462, but that means he accrues an additinal 0.0147932 hours of leave which you add on to the 10.38462 which then accrues another amount of leave and so on.
So what I'm wondering is, if there's a formula that I could use to work out how much leave an employee could be paid given that every time they take leave, an additional amount of leave is accrued?

REPLY [4 votes]: Yes. Multiply the number of hours by 1.04.
For every one hour of leave, an employee gains an additional $x$ hours ($x$ being 0.038462 in this case). And for these $x$ hours of additional leave, the employee gains an additional $x \times x = x^2$ hours of leave, and so on.
So an employee entitled to $N$ hours of leave can actually take
$$N(1 + x + x^2 + x^3 + ...)$$
hours. This is called a Taylor series. As long as $-1 \le x \le +1$, it adds up to
$$\frac{N}{1 - x}$$
For $x$ = 0.038462, this comes out as very close to 1.04. So close, in fact, that I expect 1.04 is the exact figure, and the number you've been using is actually an approximation of $1 - \frac{1}{1.04}$.

REPLY [3 votes]: Let $x$ be the amount of leave they end up taking and $a$ the amount they have already accrued.  Their total leave $x$ should be the leave they already have plus the leave they will accrue while on leave, so
$$x = a + 0.038462x$$
You can solve this for $x$ to get
$$x = \frac{a}{1 - 0.038462}$$


TITLE: Box-Muller method for correlated normals
QUESTION [1 upvotes]: The standard Box-Muller method produces two independent normal variables given two uniform ones. Is it possible to extend the method such that given a correlation coefficient $\rho\in[-1, 1]$ and two independent uniform random variables it produces to standard normal random variables, but with correlation $\rho$?
I am aware that the most common way to get correlated normal random variables is to get independent ones first and then multiply them by the square root of the correlation matrix. At this time I am seeking an alternative approach though.

REPLY [0 votes]: Found it finally in this paper.
Let $U_1$ and $U_2$ be independent uniforms on $(0, 1)$. Then the standard Box-Muller algorithm tells us that the random variables:
$$
V_1 = \sqrt{-2 \log U_2} \cos(2\pi U_1)
$$
$$
V_2 = \sqrt{-2 \log U_2} \sin(2\pi U_1)
$$
are independent $N(0, 1)$. Let $W_1$ and $W_2$ be correlated normals:
$$
W_1 = V_1
$$
$$
W_2 = \rho V_1 + \sqrt{1-\rho^2} V_2
$$
Then using the definitions above we get:
$$
W_1 = \sqrt{-2 \log U_2} \cos(2\pi U_1)
$$
and
$$\require{enclose}
W_1 = \sqrt{-2 \log U_2} \left[\rho\cos(2\pi U_1) + \sqrt{1-\rho^2}\sin(2\pi U_1)\right]\\
\enclose{horizontalstrike}{=  \sqrt{-2 \log U_2} \left[\sin(\arcsin \rho)\cos(2\pi U_1) \cos(\arccos \rho)\sin(2\pi U_1) \right]}\\
=  \sqrt{-2 \log U_2} \left[\sin(\arcsin \rho)\cos(2\pi U_1) + \cos(\arcsin \rho)\sin(2\pi U_1) \right]\\
= \sqrt{-2 \log U_2} \sin(2\pi U_1 + \arcsin \rho)
$$


TITLE: Showing the Exponential Function is Continuous
QUESTION [2 upvotes]: Consider the function $e^x$ on the reals.  I want to show that $e^x$ is continuous at the any point $t \in \mathbb{R}$.  Is the following argument valid?
(1) Let $\{t_n\}$ be an arbitrary sequence of reals s.t. $t_n \to t$ and $t_n \ne t$.
(2) Then $\lim\limits_{t_n \to t}$ $e^{t_n} = \lim\limits_{t_n \to t}1 + \frac{{t_n}^2}{2} + \frac{{t_n}^3}{6} + \ldots = 1 + \frac{{t}^2}{2} + \frac{{t}^3}{6} + \ldots = e^t$
So that since $\{t_n\}$ is arbitrary it follows $e^x$ is continuous at $t$.

REPLY [2 votes]: A very elementary and interesting exposition, related with this question, can be found in the book "Calculus, Early Trascendentals" by James Stewart, 4th Edition, Section 1.5 "Exponential Functions", pages 56 and 57. It is not a demonstration at all, it begins by defining 2^x for integers, then for rational numbers, finally for irrational numbers, and by construction it is at least plausible that 2^x must be continuous. May be not what you need, yet I believe it is fun to read.


text:
\begin{document}

\begin{center} {\LARGE  {\bf A Remark on Deriving Precise Upper Bounds of the Number of the RNA Secondary Structures  \vspace{.25cm} }  }  \\

{\Large    \emph{Alexander I. Kheyfits  \vspace{.25cm}   } }

akheyfits@gc.cuny.edu   \vspace{.25cm}

\end{center}

\noindent {\bf {Abstract}.} An elementary, at the undergraduate level, derivation is given of precise upper bounds of the number of the various RNA structures. The method works when the generating function has multiple singularities at the circle of convergence. Nor does the method require the Taylor coefficients to be positive. Examples from the current research literature are considered.
\vspace{.5cm}

\begin{center}
\today
\end{center}

\vspace{.5cm}

\footnoterule \vspace{.25cm}

\par 2010 Mathematics Subject Classification: 92-08, 05A16.

\section{Introduction}

Since Waterman and Stein \cite{Wat, StWat} defined the RNA secondary structures in graph-theoretical terms, derivation of the upper bounds or precise asymptotic formulas for the various structures became an important problem; the number of relevant papers is growing, see, e.g., \cite{CKK, FuC, LoPoCl} and the references therein. Derivation of these estimates in the current literature is based on the deep result of complex analysis, that can be traced back to G. Darboux; we refer the reader to the very informative survey of various methods \cite{LoPoCl}.

During the workshop \emph{Teaching Discrete and Algebraic Mathematical Biology to Undergraduates} at the Mathematical Biosciences Institute at Ohio State University, Columbus, OH, 7/29/2013 - 8/02/2013, several speakers discussed these estimates. However, the Darboux theorem and its modern analogs are well beyond the current undergraduate curriculum.

The goal of this methodical note is to show that precise upper bounds for the number of the secondary structures in many cases can be derived quite elementary, within the power of an undergraduate student taking an Introductory Complex Analysis class, and without the use of CAS. Of course, the method is not limited to the secondary structures, in the last two examples we find the bounds for the number of RNA shapes \cite{LoPoCl}. The method is based on the well-known Cauchy-Hadamard formula for the radius of convergence of Taylor series, or even on its real-valued relative -- the root-test for convergence of the power series.

Moreover, unlike some other methods, it is irrelevant for the method, whether the generating function has more than one singularity on the circle of convergence. Nor does the method require the Taylor coefficients to be positive.

For the readers convenience, in the next section we remind what are the RNA primary and secondary structures. Then we describe our method, and in Section 3 we consider examples of its application.

\section{RNA Structures and the Cauchy-Hadamard Formula }

\subsection{RNA Primary Structures}

Living cells contain important (macro)molecules, called RiboNucleic Acids (RNA). These acids contain essential genetic information, for example, about  viruses, thus, it is important to know their structure. Biologists distinguish primary, secondary, and tertiary structures of RNA. Unlike the double helix of the DNA, each RNA is a  \emph{linearly ordered strand}, or just a \emph{string}, consisting of other molecules, called \emph{ribonucleotides}. This string is the backbone of any RNA. Traditionally, it is represented by a horizontal straight segment with nodes occupied by the nucleotides. If the RNA contains $n$ ribonucleotides, we select $n$ points of the segment and number them consecutively from left to the right by the natural numbers $1,2,\ldots ,n$; these dots represent the ribonucleotides in the RNA. For more information the reader can consult, for example, \cite{Re} or \cite{WaZ}.

When we start studying new objects, it is often necessary to know their quantity. In particular, it is important to know the number of the primary and secondary structures of RNA. It is not always possible to find a precise formula for the number of the secondary structures subject to various restrictions. And even if such a formula is derived, it can be very cumbersome, and therefore useless. That is why, a lot of work has been done to derive different \emph{asymptotic} formulas for the numbers of various secondary structures, see, e.g., \cite{Re, WaZ} and the references therein. A formula is called asymptotic, if it gives better and better \emph{relative approximation} of a quantity under consideration, when a certain parameter (e.g., the size of a system or time) is approaching a crucial threshold; for example, if time tends to infinity.

There are four different ribonucleotides, called \emph{adenine} (denoted hereafter $\mathcal{A}$), \emph{cytosine} ($\mathcal{C}$), \emph{guanine} ($\mathcal{G}$), and \emph{uracil} ($\mathcal{U}$). The linear ordering of these four nucleotides in either order, where each of them can repeat indefinitely, is called the \emph{primary structure} of the RNA. Thus, the primary structure of an RNA can be depicted by drawings like this,
\begin{figure}[hbt]
\psset{xunit=1cm,yunit=1cm}
\def\xlim{6.5}
\def\ylim{.75}
\begin{pspicture*}(-\xlim,-\ylim)(\xlim,\ylim)
\psline(-4.75,0)(-3.25,0)      \psline(-2.75,0)(-1.25,0)   \psline(-.75,0)(.75,0)        \psline(1.25,0)(2.75,0)
\psline(4.75,0)(3.25,0)

\rput(-5,0){$\circle{.5}$}  \rput(-3,0){$\circle{.5}$}    \rput(-1,0){$\circle{.5}$}     \rput(1,0){$\circle{.5}$}   \rput(3,0){$\circle{.5}$} \rput(5,0){$\circle{.5}$}

\rput(-5,0){$A$}    \rput(-3,0){$G$}    \rput(-1,0){$G$}     \rput(1,0){$U$}  \rput(3,0){$A$}   \rput(5,0){$C$}

\rput(-5,-.5){$1$}    \rput(-3,-.5){$2$}    \rput(-1,-.5){$3$}     \rput(1,-.5){$4$}  \rput(3,-.5){$5$}   \rput(5,-.5){$6$}

\end{pspicture*}
\caption{A string (primary structure) with 6 nodes occupied by the nucleotides $\mathcal{A-G-G-U-A-C}$.}
\end{figure}

In mathematical parlance, the pictures like this are called \emph{graphs}. They are studied in the \emph{graph theory}. The graph in Fig. 1 is \emph{labeled} -- its vertices are labeled by the symbols of the nucleotides. The graph theory is a mathematical theory, and even though mathematics by itself cannot solve biological problems, it can give useful insights and help to solve biological problems \cite{Wig}.

\subsection{Counting the Primary Structures}

We begin by solving an easy problem of calculating the number of primary structures of RNA of some specified length, say $n$. We denote the number of different linear strings, containing $n$ nucleotides, without any restrictions on the neighboring ones, as $\widetilde{R}(n)$. Since every string starts with one of the four nucleotides, either $\mathcal{A}$, or $\mathcal{C}$, or $\mathcal{G}$, or $\mathcal{U}$, followed by a string of length $n-1$, we can immediately produce the basic equation
\[\widetilde{R}(n)=4\times \widetilde{R}(n-1).\]
Such equations are called \emph{recurrence relations} or \emph{difference equations}. In the same fashion,
\[\widetilde{R}(n-1)=4\times \widetilde{R}(n-2),\]
and we can \emph{iterate} this equation, getting the equation
\[\widetilde{R}(n)=4 \widetilde{R}(n-1)=4^2 \widetilde{R}(n-2)=4^3 \widetilde{R}(n-3)=\cdots =4^{n-1} \widetilde{R}(1).\]
Since we have an obvious initial condition $\widetilde{R}(1)=4$, the total number of primary structures without any restriction is
\[\widetilde{R}(n)=4^n.\]
We can notice that this is just the number of permutations (or arrangements) with repetitions of $n$ elements of four different kinds of elements\footnote{For all basic information from combinatorics and graph theory see for example \cite{Kh}.}.

Thus, the number of the RNA grows exponentially, as $4^n$. Therefore, the number of the secondary structures in the literature is usually compared with the exponential function $b^n$.

Now we take up the RNA strings with restrictions on the neighboring nucleotides. Of course, in real molecules there are always small deviations from the basic rules, that is, certain "forbidden" pairs can occur, even though with a small probability. We neglect these "outliers" and consider only RNA, where \emph{all the base pairs} are only of these three types, called Watson-Crick pairing:
\beq \mathcal{A-U;\; C-G;\; G-U}.\eeq

We compute the number of the primary structures satisfying these restrictions. The very first nucleotide can be either $\mathcal{A}$, or $\mathcal{C}$, or $\mathcal{G}$, or $\mathcal{U}$. Let us denote the number of strings of length $n$ and starting with $\mathcal{A}$, as $R_{\mathcal{A}}(n)$, and similarly, $R_{\mathcal{C}}(n)$, $R_{\mathcal{G}}(n)$, $R_{\mathcal{U}}(n)$. If the very first molecule is an $\mathcal{A}$, then the second nucleotide can be only $\mathcal{U}$. Since this $\mathcal{U}$ starts a string of $n-1$ bases,  thus
\[R_{\mathcal{A}}(n)=R_{\mathcal{U}}(n-1).\]
Similarly,
\[R_{\mathcal{C}}(n)=R_{\mathcal{G}}(n-1).\]
However, if the first nucleotide is a $\mathcal{G}$, then the second molecule must be either $\mathcal{C}$ or $\mathcal{U}$, thus
\[R_{\mathcal{G}}(n)=R_{\mathcal{C}}(n-1)+R_{\mathcal{U}}(n-1).\]
Similarly, if the first nucleotide is a $\mathcal{U}$, then the second molecule is either $\mathcal{A}$ or $\mathcal{G}$.

Since an RNA must start with some nucleotide, then
\[R(n)=R_{\mathcal{A}}(n)+R_{\mathcal{C}}(n)+R_{\mathcal{G}}(n)+R_{\mathcal{U}}(n).\]

Collecting all these equations together, we deduce the recurrence equation
\[R(n)=R_{\mathcal{U}}(n-1)+ R_{\mathcal{G}}(n-1)+ R_{\mathcal{C}}(n-1)+R_{\mathcal{U}}(n-1)+ R_{\mathcal{A}}(n-1)+R_{\mathcal{G}}(n-1)\]
\beq =R_{\mathcal{A}}(n-1)+R_{\mathcal{C}}(n-1)+2R_{\mathcal{G}}(n-1)+2R_{\mathcal{U}}(n-1). \eeq

To have the unique solution, we must supply the \emph{initial conditions}, which in this case are, obviously, \beq R_A(1)=R_C(1)= R_G(1)=R_U(1)=1;\; R(1)=4.\eeq

Using equations (2)-(3), we can easily compute the number $R(n)$ for any given $n$; for large $n$ we should probably use computers. For example, if $n=2$ then $n=14$ we get $R(2)=1+1+2+2=6$. Indeed, we can list these strands explicitly,
\[\mathcal{A-U};\; \mathcal{C-G};\; \mathcal{G-C};\; \mathcal{G-U},\; \mathcal{U-A};\; \mathcal{U-G}.\]

\subsection{Secondary Structures}

An RNA molecule is not rigid like a metal bar, it is flexible and can be conveniently thought of as a smooth flexible string, which can be crumpled, and then stretched again without any noticeable change.

Imagine now that we attached small pieces of velcro tape at some places of this string. If we now fold it over, then these pieces of velcro tape can hook one another, and we cannot easily stretch the tape in a linear structure as before. In real molecules instead of velcro tape there are certain pairs of nucleotides. If they happen to be close enough one to another, they are capable of forming chemical bonds. According to Watson-Crick, these are three \emph{base pairs} of the nucleotides, given by equation (1) in either order. For example, the string in Fig. 1 can fold over into the one in Fig. 2, where the new ties are pairs $\mathcal{C-G}$ and $\mathcal{G-C}$, but it cannot fold into the one in Fig. 3.
\begin{figure}[hbt]
\psset{xunit=1cm,yunit=1cm}
\def\xlim{6.5}
\def\ylim{2}
\begin{pspicture*}(-\xlim,-\ylim)(\xlim,\ylim)
\psline(-3.75,-1)(-2.25,-1)          \psline(-1.75,-1)(-.25,-1)      \psline(.25,-1)(1.75,-1)

\rput(-4,-1){$\circle{.5}$}    \rput(-2,-1){$\circle{.5}$}  \rput(0,-1){$\circle{.5}$}    \rput(2,-1){$\circle{.5}$}     \rput(2,1){$\circle{.5}$}   \rput(0,1){$\circle{.5}$}

\psline(2,-.75)(2,.75)        \psline(1.75,1)(.25,1)      \psline(.05,-.77)(.05,.73)    \psline(-.05,-.77)(-.05,.73)

\rput(-4,-1){$A$}    \rput(-2,-1){$G$}    \rput(0,-1){$G$}     \rput(2,-1){$U$}
\rput(2,1){$A$}   \rput(0,1){$C$}

\end{pspicture*}
\caption{A secondary structure built on the primary string $\mathcal{A-G-G-U-A-C}$.}
\end{figure}

\begin{figure}[hbt]
\psset{xunit=1cm,yunit=1cm}
\def\xlim{6.5}
\def\ylim{2}
\begin{pspicture*}(-\xlim,-\ylim)(\xlim,\ylim)
\psline(-3.75,-1)(-2.25,-1)          \psline(-1.75,-1)(-.25,-1)      \psline(.25,-1)(1.75,-1)

\rput(-4,-1){$\circle{.5}$}    \rput(-2,-1){$\circle{.5}$}  \rput(0,-1){$\circle{.5}$}    \rput(2,-1){$\circle{.5}$}     \rput(2,1){$\circle{.5}$}   \rput(0,1){$\circle{.5}$}

\psline(2,-.75)(2,.75)        \psline(1.75,1)(.25,1)      \psline(.05,.75)(1.85,-.85)
\rput(-4,-1){$A$}    \rput(-2,-1){$G$}    \rput(0,-1){$G$}     \rput(2,-1){$U$}
\rput(2,1){$A$}   \rput(0,1){$C$}

\end{pspicture*}
\caption{This structure is forbidden by the Watson-Crick pairing.}
\end{figure}

This folding of RNA molecules in the plane is called the \emph{secondary structure} of the RNA molecule. Since different nucleotides can come close to each other, a primary structure can generate different secondary structures, which significantly complicates the analysis of the RNA. It is supposed that the secondary structure is a two-dimensional object, thus it can be drawn in the plane.

The \emph{secondary structure} of the RNA describes the ordering and location of these base pairs of the nucleotides. The secondary structure is responsible for many crucial biological phenomena, and the graph theory is helpful in discovering these structures.

The secondary structure, as defined by M. Waterman \cite{Wat}, ia also a graph. We consider hereafter only \emph{simple} graphs, i.e., graphs without loops or parallel edges. To a simple graph, there corresponds a square matrix of size  $n\times n$, such that its element $a{i,j}=1$ if and only if the vertices $v_i$ and $v_j$ are connected with an edge and is $0$ otherwise; this matrix is called the \emph{adjacency matrix} of the graph. The secondary structure is a horizontal backbone of length $n$, i.e., just a primary structure, enriched by several arcs in the upper half-plane, whose end-points are the nodes of the backbone. In notation and terminology we follow \cite{Re}. The arcs of the secondary structure are subject to certain restrictions. The arc with ends at the nodes $i$ and $j>i$ is denoted as $(i,j)$, the \emph{length} of the arc is $j-i\geq 1$. Not every family of arcs corresponds to a secondary structure.

A secondary structure is a  simple graph on the backbone of the length $n$, such that the adjacency matrix $A=(a_{i,j})$ possesses the following three properties.  \\

1) For the basic string to be a backbone, we require that $a_{1,2}=a_{2,3}=\cdots =a_{n-1,n}=1$.

2) Next, not counting the neighbors, every point can be adjacent to at most one other point of the backbone. In terms of the incidence matrix, this means that for any $i,\; 1\leq i\leq n,$ there exists at most one $j$ with $j\neq i\pm 1$, such that $a_{i,j}=1$.

3) Finally, it is assumed that if the vertices $a_i$ and $a_j,\; i<j,$ are adjacent and $i<k<j$, then the vertex $a_k$ \emph{cannot be adjacent} with any vertex to the left of $a_i$ or to the right of $a_j$. In terms of the adjacency matrix this means that if $a_{k,l}=1$ and $i < k < j $, then also $i < l < j $. \\

It follows that the arcs of a secondary structure \emph{do not intersect}, it is a \emph{non-crossing} structure.  \\

\section{Asymptotic Enumeration of the Secondary Structures. Examples}

\subsection{Convolution and Generating functions of Sequences}

Even if $n$ is about 10, the total listing of all the secondary structures is cumbersome, so that we want to estimate their quantity. A convenient device for  this is their \emph{generating function}, that is, the power series
\[S(x)=\sum_0^{\infty}S_n x^n,\]
where $S_n$ is the number of secondary structures with $n$ nods, $n=0,1,2,\ldots $, and $x$ is an indeterminate, real or complex. If the series is divergent, it can be considered as formal power series, or we can truncate the series and consider \emph{generating polynomials}, as discussed, e.g., in \cite{Kh}. However, in the following examples all the series have positive radii of convergence.

Given two sequences, $a=\{a_0,a_1,\ldots \}$ and $b=\{b_0,b_1,\ldots \}$ with generating functions $f_a(x)$ and $f_b(x)$ respectively, the generating function of their linear combination $\alpha a+\beta b$ with any real or complex coefficients $\alpha$ and $\beta$ is the linear combination
\[f_{\alpha a+\beta b}(x)=\alpha f_a(x)+\beta f_b(x),\]
thus, the correspondence between the sequences and their generating functions is a linear transformation. There is also an operation with sequences, which corresponds to the multiplication of their generating functions. Indeed, let $f_a(x)$ and $f_b(x)$ be two absolutely convergent power series. Multiplying them termwise and combining like terms, we get the series
\[f_a(x)\times f_b(x)=\sum_0^{\infty} c_n x^n, \]
where
\[c_0=a_0\cdot b_0,\; c_1=a_0\cdot b_1+a_1\cdot b_0,\ldots , c_n=a_0\cdot b_n+ a_1\cdot b_{n-1}+a_2\cdot b_{n-2}+\cdots +a_n\cdot b_0,\ldots .\]

Thus defined sequence
\[c=\{c_n\}_{n=0}^{\infty}\]
is called the \emph{convolution} or the \emph{Cauchy product} of the sequences $a$ and $b$, and corresponds to the multiplication of the generating functions.  \\

Let $S^{\lambda}(x)$ be the generating function of the secondary structures with the arc length at least $\lambda \geq 2$. If $\lambda=2$, the recurrent relation
\beq S^{\lambda}_n=S^{\lambda}_{n-1}+\sum^{n-1-\lambda}_{j=0} S^{\lambda}_{n-2-\lambda} S^{\lambda}_j \eeq
was derived by Waterman \cite{Wat}. To solve it, we must supply $\lambda+1$ initial conditions. We assume
\[S^{\lambda}_0=S^{\lambda}_1=\cdots =S^{\lambda}_{\lambda}=1.\]

\subsection{Computing the Generating Functions for the Secondary Structures}

The crucial observation is that recurrent relation (4) contains a sum of pairwise products quite similar to the equation for the convolution. First, consider the case $\lambda =2$ and to simplify writing, set $S(x)=S^{\lambda}(x)$. Multiplying (4) by $x^n$, after some simple algebra one derives the following quadratic equation\footnote{However, the method has the broader scope. In Example 3 below, the method is applied to the generating function satisfying a cubic equation.} for the generating function,
\beq x^2 S^2(x)+(x-1-x^2)S(x)+1=0. \eeq
Solving it by the quadratic formula, we find
\[S(x)=\frac{1}{2x^2}\left(x^2-x+1\pm \sqrt{1-2x-x^2-2x^3+x^4} \right). \]

From (5) we see that $S(0)=1$, therefore, we have to choose the sign $"-"$ above, and finally get
\[S(x)=\frac{1}{2x^2}\left(x^2-x+1-\sqrt{1-2x-x^2-2x^3+x^4} \right). \]

\subsection{Estimations of the Number of the Secondary Structures}

We need the following facts from introductory Complex Analysis course. If a power series $f(z)=\sum_{n=0}^{\infty}f_nz^n$ has a positive radius of convergence $R$, then its sum $f(z)$ is an analytic function in the open disc $|z|<R$, $R$ is the distance from the $z=0$ to the nearest singular point, which must be located on the boundary $|z|=R$, and the Cauchy-Hadamard formula
\[\frac{1}{R}=\limsup_{n\rightarrow \infty}\sqrt[n]{|f_n|} \]
is valid. We can even (with some reservations) refer, instead of the Cauchy-Hadamard formula, to the root test, which is more-or-less real valued version of the latter.

Therefore, $\sqrt[n]{|f_n|}\leq 1/R$, and we have the required upper bound for the coefficients $f_n$,
\beq |f_n|\leq \left(\frac{1}{R}\right)^n,\; n=1,2,3,\ldots . \eeq

By the definition of the upper limit, there is a subsequence $f_{n_k}\rightarrow \infty$ as $k\rightarrow \infty$, such that \[\frac{1}{R}=\limsup_{n\rightarrow \infty}\sqrt[n]{|f_n|}. \]
This shows that the upper bound (6) is precise, it cannot be made smaller. Moreover, the method works if there are several singularities on the circle of convergence. Nor does the method require the Taylor coefficients to be positive. However, preserving this elementary level, we can derive only the precise exponential upper bound for the quantities at question, and cannot find the principal term of the asymptotic formulas explicitly, as more sophisticated methods do. To demonstrate the method, we apply it to several known examples from the existing literature.

\begin{examp} Consider the generating function $S(x)$ above. The origin $x=0$ is a \emph{removable singularity}, as can be straightforwardly seen by rationalizing the numerator,
\[S(x)=\frac{2}{x^2-x+1+\sqrt{1-2x-x^2-2x^3+x^4}}. \]
The radicand $1-2x-x^2-2x^3+x^4$ is a symmetric polynomial of forth degree. The corresponding equation $x^4-2x^3-x^2-2x+1=0$ can be explicitly solved by dividing over $x^4$ and substituting $t=x+1/x$; it has two real roots, $z_1=\frac{3-\sqrt{5}}{2}$, $z_2=\frac{3+\sqrt{5}}{2}$, and two complex conjugate roots, $z_{3,4}=\frac{-1\pm \imath \sqrt{3}}{2}$; $|z_{3,4}|=1$. The root, closest to the origin, is $z_1$, thus $S(z)$ is analytic in the open disc $|z|<R=|z_1|<1$. Finally, from (6) we get the estimate
\[|S_n|\leq \left(\frac{2}{3- \sqrt{5}}\right)^n =\left(\frac{3+ \sqrt{5}}{2} \right)^n,\]
which is, up to the pre-exponential factor, the estimate derived in \cite[p, 65]{Re}, \cite{LoPoCl}, and some other places  by making use of certain more sophisticated tools of complex analysis.  \end{examp}

\begin{rem} It must be noted that the function $S(z)$ is a many-valued analytic function of the complex argument $z$ with the branching points at the roots $z_1-z_4$ of the radicand and at infinity. To select a single-valued branch of $S$, we can cut the plane, for example, along the rays going from the points $z_1, z_3, z_4$ to infinity. The generating function $S(x)$ is given by the principal branch of $S(z)$ corresponding to the choice $\sqrt{1}=+1$. In the disk $|z|<|z_1|$, this generating function $S(x)$ is represented by the Taylor series with positive coefficients $S_n$. The same remark is valid for all the examples that follow. \end{rem}

\begin{examp}  In general case, that is, for the secondary structures with any arc length $\lambda \geq 2$, the difference equation is (\cite{Re})
\[S^{\lambda}(n)=S^{\lambda}(n-1)+\sum^{n-1-\lambda}_{j=0} S^{\lambda}(n-2-j) S^{\lambda}(j),\]
leading again to a quadratic equation for the generating function,
\[x^2 \left(S^{\lambda}(x)\right)^2-(1-x+x^2+\cdots +x^{\lambda})S^{\lambda}(x)+1=0, \]
which again can be explicitly solved for $S^{\lambda}$ by the quadratic formula. For example, if $\lambda=3$, the radicand is the polynomial $1-2x-x^2-x^4+2x^5+x^6$, which can be factored,
\[1-2x-x^2-x^4+2x^5+x^6=(1-2x-x^2)(1-x^4),\]
with the smallest root $\sqrt{2}-1$. Repeating the same reasoning as above, we get the estimate
\[S^3(n) \leq \left(\sqrt{2}+1\right)^n. \]
If $\lambda =4$, the radicand is a polynomial of $8^{th}$ degree, whose roots are to be evaluated numerically; the smallest one is $~0.436911$, leading to the estimate
\[S^4(n) \leq 2.28879^n. \] \end{examp}

\begin{examp}  Many authors consider secondary structures subject to various restrictions, see for example, \cite{WaZ, WZW, Kra} and the references therein. The presented approach works even if the equation for the generating function is of degree higher than $2$, as in the next example. We consider \emph{saturated secondary structures} studied in \cite{Kra}. In this case the generating function $S=S(z)=\sum_{n\geq 0}S_n z^n$ satisfies the system of two nonlinear equations (see, e.g., \cite{Kra} and the references therein)
\[S(z)=z+z^2+zT(z)+z^2T+z^2S+z^2S^2, \]
\[T(z)=z^2S+z^2TS.\]
Eliminating $T$, one derives the cubic equation for $S$,
\[z^4S^3+z^2(z^2-2)S^2+(1-z^2)S-z(1+z)=0. \]
We solve the cubic equation for $S$ by the classical Cardano formula. When the parameter $z$ is within the range of interest, the equation has one real root,
\[S_r(z)=\frac{2-z^2}{3z^3}+\frac{1}{3\sqrt[3]{2}z^3}\left\{A^{1/3}+
\frac{\sqrt[3]{2}(z^4-z^2+1)}{3A^{1/3}}\right\},\]
where
\[A=-2z^6+30z^4+27z^3+3z^2-2 \vspace{.3cm} \]
\[+(3z)^{3/2}\sqrt{-4z^7-4z^6+32z^5+60z^4+35z^3+6z^2-5z-4}.\]
The equation $A=0$ simplifies to $(z^4-z^2+1)^3=0$ with all the roots on the unit circle. The radicand in the $A$ has the smallest root at $z_0\approx0.424687310$, which is the radius of convergence, $R$, of $S(z)$. It should be mentioned that we chose the branch of the radical which is positive in a right neighborhood of $z_0$. Hence, we get the bound
\[S_n\leq \cdot (1/R)^n =const \cdot 2.354673^n \]
in complete agreement with \cite{Kra}.  \end{examp}

\begin{examp}  In the case of \emph{canonical secondary structures} \cite{Kra}, the generating function $S$ also satisfies a system of two nonlinear equations,
\[S(z) = z + zS(z) + z^2Q(z) + z^2S(z)Q(z),\]
\[Q(z) = z^3 + z^2Q(z) + z^4S(z)Q(z) + z^3S(z).\]
Eliminating $Q$, we get the quadratic equation for $S$ with the discriminant
\[\Delta(z)=z^{10}-4z^9-2z^8+6z^7+3z^6-8z^5-z^4+4z^3-z^2-2z+1=0.\]
Its smallest in absolute value root is $R\approx 0.5081360362$, which is the closest to the origin singular point of $S(z)$, and the upper bound for the number of the saturated secondary structures on $n$ nucleotides is its reciprocal $1/R~1.967977$, again in perfect agreement with \cite{Kra}.   \end{examp}

\begin{examp} Next, we consider an example from \cite[Theor. 2, p. 352]{FuC}, where the authors derived the generating function for a certain class of secondary structures,
\[S_0(z)=\frac{1}{2z^2(1+z)^2}\left(1-z-z^2(1+z)^2-\sqrt{P(z)} \right) \vspace{.2cm}\]
\[P(z)=(z^4+2z^3+z^2+z-1)^2-4z^3(1+z)^2.\]
Here $z=0$ is a removal singularity and $z=-1$ is beyond the disc of convergence, since the closest to the origin singular point is the branching point of the radical at the smallest root of the polynomial $P$. This root is $z_0\approx 0.32471796$, thus the radius of convergence is $R\approx 3.0795963$ and the upper bound of the number of the secondary structures at question is $\cdot 3.0795963$, again in agreement with \cite{FuC}.         \end{examp}

In the two examples to follow, we bound the number of various RNA shapes. The equations for the generating functions were derived in the informative paper by Lorenz, Ponty, and Clote \cite{LoPoCl}, we only suggest an elementary derivation of the main exponential term of the asymptotics.

\begin{examp} In the case of $\pi-$shapes, the generating function $S(z)$ satisfies the simple quadratic equation
\[S=z^2S^2+z^2S+z^2,\]
therefore, since $S(0)=0$,
\[S(z)=\frac{1}{2z^2}\left(1-z^2-\sqrt{1-2z^2-3z^4} \right).\]
The radicand is a biquadratic equation with roots $\pm \imath$ and $\pm 1/\sqrt{3}$. Thus, the distance from the boundary to the nearest singularity is $1/\sqrt{3}$, and the bound we sought for, is $s_n\leq (\sqrt{3})^n$.

It should be emphasized that it is irrelevant for this method whether there are multiple singularities on the circle of convergence.
\end{examp}
\begin{examp} In the last example we estimate the number of $\pi-$shapes compatible with the RNA sequences of length $n$. The equation for the generating function, also taken from \cite{LoPoCl}, is
\[z^2(1-z)^2S^2+(z-1+z^5-z^6)S+z^5=0.\]
Solving it by the quadratic formula and canceling by $1-z$, we get
\[S(z)=\frac{1}{2z^2(1-z)}\left(1-z^5-\sqrt{z^10-4z^7-2z^5+1} \right).\]
The singularity, closest to the origin, which gives the radius of analyticity of the generating function, is $R \approx ).756328$, hence, the required upper bound is its reciprocal $1/R \approx 1.32218$.
\end{examp}

\subsection*{\textbf{Acknowledgement}} The author is thankful to the MBI for inviting him to the workshop, and to Professors Raina Robeva and Peter Clote for useful discussions. Numerical computations in the examples above were made by making use of the Wolfram Mathematica free online root finder. The author wants to acknowledge the excellent performance of this widget. \\

config: arxiv


TITLE: Solution to Poisson's equation.
QUESTION [3 upvotes]: I am trying to figure out the solution for a Poisson's equation, which relates the scalar electric potential $\phi$ to the electric charge density $q$. I found the below equation and it's solution from an electromagnetic textbook, but unfortunately no steps were shown to get the solution. Thanks in advance.
Poisson's equation:
$$\bigtriangledown^2\phi = -\frac{q}{\epsilon}$$
Solution:
$$\phi = \frac{1}{4\pi\epsilon} \iiint_{V} \frac{q}{r} \,dv'$$

REPLY [1 votes]: The use of delta functions to solve pde is know as theory of distributions and the solutions found are meaningful in a distributional sense (read that up).
If you are looking for classical solution (exact) read below :
Let a continuous function $f(x,y,z)$ have first order partial derivatives $f_x,f_y,f_z$ exist at every point and the function and all its first order partial derivatives are absolutely integrable.
If for $x',y',z' \in R$ there is a non negative integrable function $h(x',y',z')$ such that for some measurable set $A \subset R^3$ with finite Lebesegue outer measure:
$f_x(x+x',y',z')< h(x',y',z')$ almost everywhere in $R^3$
$f_y(x',y+y',z')< h(x',y',z')$ almost everywhere in $R^3$
$f_z(x',y',z+z') < h(x',y',z')$ almost everywhere in $R^3$
$ r'=\sqrt{|x-x'|^2+|y-y'|^2+|z-z'|^2}$
let:
$$g(x,y,z)=\int_{-\infty}^{\infty} \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} \frac {f(x',y',z')}{4\pi r'}dx'dy'dz',\ \ \text{s.t.}\ \ \nabla^2g= \frac {\partial^2g}{\partial x^2}+\frac {\partial^2g}{\partial y^2}+\frac {\partial^2g}{\partial z^2}$$
How to show that $\nabla^2g=-f$  ?
ANSWER :
Theorem 1. If a sequence of  absolutely continuous functions {$f_n$} converges pointwise to some $f$  and if the sequence of  derivatives {$f_n’$}  converges almost everywhere to some  $g$ and if {$f_n’$} is uniformly integrable then $\lim\limits_{n\mapsto \infty} f_n’ = g= f’$ almost everywhere. Where the derivative of  $f$ is $f’$. If the convergence is pointwise and $ g $ is continuous then $ f'$ = $ g $ everywhere.
Proof : by FTC  $f_n(x) – f_n(a) = \int_a^x f_n’ dx$
By Vitali convergence theorem : $\lim\limits_{n\mapsto \infty}\int_a^x f_n’ dx = \int_a^x g dx$
Therefore $\lim\limits_{n\mapsto \infty}( f_n(x) – f_n(a))= \int_a^x g dx$
$f(x)-f(a) = \int_a^x g dx$
$f(x)’=g$ almost everywhere
If the convergence is pointwise and $ g $ is continuous then $ f'$ = $ g $ everywhere.
Theorem 2. Divergence Theorem
Theorem 3. Leibniz Integral Rule : Measure theoretic version
$ r'=\sqrt{|x-x'|^2+|y-y'|^2+|z-z'|^2}$
$ r=\sqrt{|x'|^2+|y'|^2+|z'|^2}$
Define $f_N=\int_{-N}^{N} \int_{-N}^{N} \int_{-N}^{N}f(x’,y’,z’)\frac {1}{4\pi r’}erf(\frac {r’N}{\sqrt 2})dx'dy'dz'$
$erf(\frac {r’N}{\sqrt 2})=\frac {2}{\sqrt \pi}\int_0^{\frac {r’N}{\sqrt 2}}e^{-t^2}dt$
$\lim\limits_{N\mapsto \infty}erf(\frac {r’N}{\sqrt 2})=1$
$\lim\limits_{N\mapsto \infty} f_{N} = g$
$\frac {1}{4\pi r’}erf(\frac {r’N}{\sqrt 2})$ can be developed into a power series of $r'$ by simply plugging Taylor's expansion of $erf(\frac {r’N}{\sqrt 2})$
By theorem 3 $\frac {\partial f_{N}}{\partial x}=\int_{-N}^{N} \int_{-N}^{N} \int_{-N}^{N} \frac {f(x',y',z')(x'-x)erf(\frac {r’ N}{\sqrt 2})}{4\pi r'^3}dx'dy'dz'-$
$\int_{-N}^{N} \int_{-N}^{N} \int_{-N}^{N}\frac {N(x' - x)f(x',y',z') e^{-(\frac {r’^2 N^2}{ 2})}}{\sqrt 2 4\pi r'^2}dx'dy'dz'$
The existence of$\int_{-\infty}^{\infty} \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} \frac {f(x',y',z')}{4\pi r'}dx'dy'dz' $ and  $\int_{-\infty}^{\infty} \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} \frac {f(x',y',z')(x'-x)}{4\pi r'^3}dx'dy'dz' $ which is also continuous can be shown by converting to polar coordinates.
Now we can apply theorem $1$  to conclude  $\lim\limits_{N\mapsto \infty} \nabla f_{N} =\nabla g$
$\nabla^2 f_{N} =-\int_{-N}^N \int_{-N}^N \int_{-N}^N \frac {N^3f(x',y',z')e^{-(\frac {r’^2 N^2}{ 2})}}{(\sqrt{2\pi})^3}dx'dy'dz'$
$\int_{-\infty}^{\infty} \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} \frac {f(x',y',z')(x'-x)}{4\pi r'^3}dx'dy'dz' = \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} \frac {f(x'+x,y'+y,z'+z)(x')}{4\pi r^3}dx'dy'dz'$
it follows from theorem 3 :
$\nabla^2  g=\int_{-\infty}^{\infty} \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} \frac {f_x(x'+x,y'+y,z'+z)(x')}{4\pi r^3}dx'dy'dz'+\int_{-\infty}^{\infty} \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} \frac {f_y(x'+x,y'+y,z'+z)(y')}{4\pi r^3}dx'dy'dz'+\int_{-\infty}^{\infty} \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} \frac {f_z(x'+x,y'+y,z'+z)(z')}{4\pi r^3}dx'dy'dz'$
Now application of  dominated convergence theorem ,the fact that $\lim\limits_{N\mapsto \infty} \nabla f_{N} =\nabla f$ and using theorem 2 : $\int_a^b \int_a^b \int_a^b(\nabla .\nabla  f_N )dxdydz = \int_{R^2} \nabla f_N .dA$
$ \int_{R^2} \nabla g .dA=\lim\limits_{N\mapsto \infty}\int_{R^2} \nabla f_{N} .dA$
$\int_a^b  \int_a^b \int_a^b \lim\limits_{N\mapsto \infty} (\nabla^2  f_{N} )=\lim\limits_{N\mapsto \infty} \int_a^b  \int_a^b \int_a^b  (\nabla^2  f_{N} )$
And $\int_a^b \int_a^b \int_a^b(\nabla^2  g )dxdydz =\int_{R^2} \nabla g .dA=\lim\limits_{N\mapsto \infty}\int_{R^2} \nabla f_{N} .dA=\lim\limits_{N\mapsto \infty} \int_a^b  \int_a^b \int_a^b  (\nabla^2  f_{N} )=\int_a^b  \int_a^b \int_a^b \lim\limits_{N\mapsto \infty} (\nabla^2  f_{N} )$
$\int_a^b \int_a^b \int_a^b((\nabla^2  g )-\lim\limits_{N\mapsto \infty} (\nabla^2  f_{N} ))dxdydz=0$
Since this is true for any $a$ and $b$ ,we conclude $\nabla^2g=\lim\limits_{N\mapsto \infty} (\nabla^2  f_{N} )=-f$ .


TITLE: Measurability of $\xi$ in the mean value theorem
QUESTION [28 upvotes]: Suppose $f\in C^1(\mathbb{R})$, by mean value theorem, for any $x\in (0,\infty)$, there exists $\xi(x)\in (0,x)$ such that $$\frac{f(x)-f(0)}{x}=f'(\xi(x)).$$ My question is:

Question: Can $\xi(x)$ always be chosen to be a measurable function in $x$?

REPLY [5 votes]: How about: Define $\xi(x)$ as the least number $\xi$ such that
$$
\frac{f(x)-f(0)}{x}=f'(\xi)
$$
From the $C^1$ hypothesis we know $f'$ is continuous.
That does not quite work, because we may get $\xi(x) = 0$ sometimes.
OK, define $\xi(x)$ as the least number $\xi \ge x/2$ such that
$$
\frac{f(x)-f(0)}{x}=f'(\xi)
$$
if there is such a $\xi$, otherwise the greatest number $\xi \le x/2$ such that
$$
\frac{f(x)-f(0)}{x}=f'(\xi)
$$


TITLE: Finding the Smallest Convex Hull of an Adjacency Matrix
QUESTION [1 upvotes]: Let's say I have a an adjacency matrix of a directed graph, with at most one 1 in each row (self-loops are allowed but are 1, not 2). My goal is to rearrange the matrix using only row and column swaps. If I treat the positive entries as points, I can shrink the size of the convex hull by putting empty columns and rows at the ends. But, I don't know if that admits the smallest cluster. How do I know if the convex hull is the smallest possible without using brute force?
Here is an example:
We have the 9X9 adjacency matrix,
\begin{Vmatrix}
0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0  \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\
\end{Vmatrix}
which with dots is:
\begin{Vmatrix}
  &   &   &   & \cdot &   &   &   &   \\
  &   &   &   &   & \cdot &   &   &    \\
\cdot &   &   &   &   &   &   &   &   \\
  &   &   &   &   & \cdot &   &   &   \\
  &   &   &   &   & \cdot &   &   &   \\
  &   &   &   &   &   &   &   &   &\\
\cdot &   &   &   &   &   &   &   &   \\
\cdot &   &   &   &   &   &   &   &   \\
  &   &   & \cdot &   &   &   &   &   \\
\end{Vmatrix}
then rearranged is:
 \begin{Vmatrix}
  & \cdot &   &   &   &   &   &   &   \\
  &   & \cdot &   &   &   &   &   &    \\
\cdot &   &   &   &   &   &   &   &   \\
  &   & \cdot &   &   &   &   &   &   \\
  &   & \cdot &   &   &   &   &   &   \\
\cdot &   &   &   &   &   &   &   &   \\
\cdot &   &   &   &   &   &   &   &   \\
  &   &   & \cdot &   &   &   &   &   \\
  &   &   &   &   &   &   &   &   \\
\end{Vmatrix}
with the convex hull of the latter clearly having the smaller area.

REPLY [0 votes]: This isn't a proof. I noticed that we can treat each row as an integer since it has at most one 1 in a row. The column position of the one gives us the value, with the zero row being 0. We can then sort numbers based on how many duplicates there are for that number. So, if we have 1,2,4,4,4,5,5,6,6,6 we can sort it to,
4,4,4,6,6,6,5,5,2,1. We then make the first value 1's, the next new value 2's, and so on. This would give us 1,1,1,2,2,2,3,3,4,5. Then we can do our first step backwards. I am not sure if this always works though.


text:
\begin{document}
\maketitle

{\bf Abstract.}
{\small Given $A\in \mathbf{Z}^{m\times n},\ rank A=m,\ b\in \mathbf{Z}^{m}$. Let $d$ be the maximum of absolute values of the $m\times m$ minors of the matrix $(A\: b)$, $M=\{x\in \mathbf{Z}^n | Ax=b,\ x\ge 0\}.$ It is shown that if $M\not=\emptyset$, then there exists
$x^0=(x^0_1,...,x^0_n)\in M,$ such that $x^0_i\le d\ (i=1,2,..,n).$
}
\bigskip

\centerline{\bf Introduction}
\medskip

Let $A(m\times n)$ be a matrix of rank m with integer elements, $b$ be an integer
vector, $d$ be the maximum of the absolute values of the $m\times m$ minors of $(A\: b)$, $M$ be the set of nonnegative integer solutions for the system
$Ax=b$, $N=\{1,...,n\}$.

In $[1]$ the conjecture was made that the following theorem is true:

\begin{theorem} If $M$ is nonempty, then there exists  $x^0\in M$ such that
$x_i^0\le d, i\in N.$ \end{theorem}
This conjecture was considered in [1-3], howerever, full and strict
answer had not given. The complete proof of the theorem was given in [4]. See also [5].
In this paper I state the translation of the proof from [4].

\paragraph{Notation.} Let $H$ denotes the matrix
which rows are the lattice basis for integer solutions of system
$Ax=0$;

$h_{1},...,h_{n}$ be columns of $H$;

 $a_{1},...,a_{n}$ be columns of $A$;

 $x^{1}$ be any vector of $M$;

 $M^{1}$ be the set of integer solutions of the system
 $H^{T}y+x^{1}\ge0$.
 \medskip

  \centerline{\bf The proof of Theorem 1}
 \medskip

 Without loss of generality, assume that g.c.d of all $m\times m$
 minors of $A$ is equal to $1$. It is clear that the relation
 $x=H^{T}y+x^{1}$  determines one-to-one mapping between $M$ and $M^{1}$.
 We should use next result from [6]:

\begin{lemma}. Let $I\subseteq N,\mid I \mid=m,A^{1}$ be the matrix that consists
 the columns of matrix $H$ with index from $N\setminus I$. Then
 $\mid\det A^{1}\mid=\mid\det H^{1}\mid$ .\end{lemma}

The theorem can be proved by induction on $n$. Case $n=m$
 is obvious.
  Assume that theorem is true for
${n\le n_0}$ and prove it is true for $n=n_0+1.$

1. Suppose first that from ${u^TA\ge0}$ it follows that
$u=0.$  According to Minkowsky-Farkas' theorem the cone
$$Ax=0,x\ge 0$$ has dimension $n-m.$ Then cone $H^Ty\ge 0$
has dimension $n-m$ as well. Suppose without loss of generality
that equation $h_1^Ty=0$ determines $(n-m-1)$  dimensional
face of cone and $x_1^1 =max(-h_1^Ty)$ for subject
$H^Ty+x^1\ge 0.$ Let $s$ be g.c.d. of components of vector
$h_1$ and $r$ be minimal nonnegative integer number such
that $x_1^1-r$ is divided to $s$. Then the set $M^1$ is
described by system
\begin{center}
   \parbox{10cm}
   {
   $h_1^Ty+x_1^1-r\ge 0\\\rm h_i^Ty+x_i^1\ge 0,
       i\in \{2,3,..,n\}
      $
   }
\end{center}
and there is $y^0\in M^1$, such that $h_1^Ty^0+x_1^1-r= 0$, hence the
system $a_2x_2+...+a_nx_n=b-ra_1$ has a nonnegative integer solution.
From the lemma it follows that $s$ is divisor of each minor of extended
matrix of the system. Therefore there exists a matrix $D$
with determinant $s$
such that vectors $ a_i^1=D^{-1}a_i, i\in\{ 2,3,..,n\}$ and
$b^1=D^{-1}(b-ra_1)$ have integer components. Since $r\le s-1$ ,maximal
absolute value of minors with rank $m$ is not more than d and by
induction the system has solution
$(x_2^0,x_3^0,...,x_n^0)$,
which components  do not exceed    $ d$. As $x^0$ it is
possible to choose $(r,x_2^0,x_3^0,...,x_n^0)$

2. Suppose now that there exists $u\ne 0$ such that $u^TA\ge 0.$
If $u^TA > 0$ then $M$ is bounded, hence,  the theorem is true.
Otherwise, we can do an unimodular transformation for rows of matrix
$(A b)$, permute columns and get the matrix
$\left(\begin{array}{l}\rm
a_1^1...a_v^1\;a_{v+1}^1...a_n^1\;b^1\\\medskip\rm
0\;...\;0\;\;a_{v+1}^2...a_n^2\;b^2\end{array}\right)$
where submatrix $(a_1^1...a_v^1)$ has rank $k$ and consists of
$k$ rows
and columns $(a_{v+1}^2...a_n^2)$ have positive last component.
Set $ b^3=b^1-a^1_{v+1}x^1_{v+1}-...--a^1_{n}x^1_{n}$ and consider
the system \begin{equation} a^1_1x_1^1+....+a^1_vx_v^1=b^3 .\label{eq1}\end{equation}
We will prove that if $d^1$ is maximal absolute value of $k\times k$ minors of this
system, then $d^1$ does not exceed $d.$

Let $k\ge 2$. Suppose without loss of generality that $d^1=abs(det(
a_1^1\;...a_{k-1}\; b^3)).$ Show that it is possible to choose the set
$I=\{i_1,...,i_j\}$ , where $j=n-m$, so that determinants

$$det\left(\begin{array}{l}\rm a_1^1...a_{k-1}^1\;a_{i_1}^1...a_{i_j}^1\;b^3
\smallskip
\\
\rm 0\;...\;0\;\;\;\;\;a_{i_1}^2...a_{i_j}^2\;0\end{array}\right)
,
det\left(\begin{array}{l}
\rm a_1^1...a_{k-1}^1\;a_{i_1}^1...a_{i_j}^1\;a_i^1\smallskip      \\\rm
0\;...\;0\;\;\;\;\;a_{i_1}^2...a_{i_j}^2\;a_i^2\end{array}\right),i\notin I$$

are either nonpositive or nonnegative.

Define $\lambda\ne0$ so that $\lambda^ta^1_i,i\in \{1,...,k-1\}$ and
$\lambda^Tb^3>0.$
Further find a vertex $\mu=(\mu_1,...,\mu_n)$ of the set of solution  of the
system $ u^Ta_i^2+\lambda^Ta_i^1\ge 0, i\in\{v+1,...,n\}.$
As the set $I$ we
choose the set of numbers of linear indepedent inequalities wich are equalities
on $\mu.$  Let $\lambda_e\ne 0$ ,then replace $e$-th row of each
determinant by linear combination of rows with coefficients
$\lambda_1,...,\lambda_k,\mu_1,...,\mu_{m-k}$.
Decomposing each determinant on the $e$-th row we get the sequence of numbers
$ Z\lambda_e\lambda^T b^3, Z\lambda_e(\lambda^Ta_i^1+\mu^Ta_i^2),i\notin I$
where $Z$ is value of algebraic supplement. Obviosly, all numbers
are either nonpositive or nonnegative.

Now we have
$$d\ge
| det\left(\begin{array}{l}\rm a_1^1...a_{k-1}^1\;a_{i_1}^1...a_{i_j}^1\;b^1
\smallskip      \\\rm
0\;...\;0\;\;\;\;\;a_{i_1}^2...a_{i_j}^2\;b^2\end{array}\right)|=
|\sum_{i\in
I}det\left(\begin{array}{l}\rm a_1^1...a_{k-1}^1\;a_{i_1}^1...a_{i_j}^1\;a_i^1
\smallskip      \\\rm
0\;...\;0\;\;\;\;\;a_{i_1}^2...a_{i_j}^2\;a_i^2\end{array}\right)x_i^1|=$$
$$|det\left(\begin{array}{l}
\rm a_1^1...a_{k-1}^1\;a_{i_1}^1...a_{i_j}^1\;b^3\smallskip      \\\rm
0\;...\;0\;\;\;\;\;a_{i_1}^2...a_{i_j}^2\;0\end{array}\right)x_i^1|\ge
|det\left(\begin{array}{l}\rm a_1^1...a_{k-1}^1\;a_{i_1}^1...a_{i_j}^1\;b^3
\smallskip      \\\rm
0\;...\;0\;\;\;\;\;a_{i_1}^2...a_{i_j}^2\;0\end{array}\right)x_i^1|\ge d^1$$

If $k=1$, then put
$\lambda_1=\left\{ \begin{array}{l}\rm\; 1\; for\; b^3>0,
\smallskip      \\\rm -1\; for\; b^3\le 0,\;e=1\end{array}\right.$
and repeat reasoning.

By induction hypothesis the system (\ref{eq1}) has solution
$(x^0_1,...,x^0_v)$, and $x^0_i\le d$ for $ i\in \{1,2,...,v\}.$
Since $x_i^1$ for $i\in\{v+1,...,n\}$ is bounded from above by $\max\{ x_i|\,Ax=b,\;x\ge 0\},$ hence,
it does not exceed $d$. So we may take $x^0=(x^0_1,...,x^0_v,x^1_{v+1},...,x^1_n).$ The proof is completed.

A little modification of the above proof allow to prove that there exists vertex $x$ of $conv(M)$ such that
 $x_i\le d$ for all $i\in N.$
\begin{center} Ñïèñîê ëèòåðàòóðû.
\end{center}

1. Borosh I.,Treybig B. Bounds on positive integral solutions of linear
diophantine equations.// Proc. Amer. Math. Soc. - 1976, v.55,N 2, pp.299-304.

2. Borosh I., Flahive M., Rubin D. and Treybig B. A sharp Bound
for  solutions of linear diophantine equations.// Proc. Amer. Math. Soc. -
1989, v.105,N 4, pp.844-846.

3. Ivanov N.N. Upper bounds for solution of integer programming. // Kibernetika, (6):112-114,1988.

4. Veselov S. I. The proof of one conjecture linear diophantine equations. (Russian) Manuscript
667B93, deposited at VINITI, Moscow, 1993.

5. Veselov, S.I. The proof of a generalization of Borosh-Treybig's hypothesis for Diophantine equations. (Russian)
Diskretn. Anal. Issled. Oper., Ser. 1 8, No.1, 17-22 (2001).

6. V. N. Shevchenko. Qualitative Topics in Integer Linear Programming,
volume 156 of Translations of Mathematical Monographs.
AMS, Providens, Rhode Island, 1997.

\end{document}


TITLE: how to linearize this differential equation?
QUESTION [0 upvotes]: I need the transfer function of:
$K1*\dot Q(t) + K2*Q(t) + K3*Q(t)^2 + K4 = 0 $
Being K1, K2, K3 and K4 constants that depend on the system parameters.
The problem is that it is a nonlinear equation, so I can not apply laplace, I tried a technique of linearization at the point of stability but resulted in 0.
Any tips?
appreciate

REPLY [1 votes]: Consider the differential equation $\dot{x} = f(x,t)$, suppose that there exists $x_0$ such that $f(x_0)=0$, and defive $z=x-x_0$. Then $\dot{z}\approx \frac{\partial f}{\partial x}(x_0,t)z$.
In your case, $\dot{z}(t) \approx -\frac{1}{K_1}\left(K_2 + 2K_3Q_0\right)z$, where $z(t):=Q(t)-Q_0$ and $Q_0$ is the real solution of the quadratic equation $K_3Q^2 + K_2Q + K_4 = 0$ around which you linearize.


TITLE: How to plot $\{z \in \mathbb{C} : |z-i|>|z+i|\}$
QUESTION [2 upvotes]: How would I draw the set $\{z \in \mathbb{C} : |z-i|>|z+i|\}$ and $\{z \in \mathbb{C} : |z-i|\not=|z+i|\}$?
Im not sure how to solve the second one, and for the first one, I tried squaring both sides and trying to work something out, but I got no where.
$|z-i|^2>|z+i|^2\\\\(z-i)(\bar z+i)>(z+i)(\bar z-i)\\ z\bar z+1+i(z -\bar z)>z \bar z+1 +i(\bar z -z)\\i(z-\bar z)>i(\bar z-z)$
What would the 'general' method/approach be for drawing the sets?
Edit: How would I draw $\{z \in \mathbb{C} : |z-i|\not=|z+i|\}$?
After a similar calculation using Zev Chonoles' post, I got that $-b\not=b$, hence $z=a+ib$ satisfies $|z-i|\not=|z+i|$ if and only if $-b\not=b$.
For $\{z \in \mathbb{C} : |z-i|>|z+i|\}$

REPLY [1 votes]: One could simply look at the absolute value of a complex number as it's distance from origin, or in other words, $|a-b|$ is the distance of $a$ from $b$.
Now, in your problem you want find all the points such that their distance from $i$ is more than their distance from $-i$. Well, find all the points who have the same distance from $i$ and $-i$. That's a line (namely the line that is perpendicular to the line segment $\overline{i,-i}$).
So far you've got the solution to the second part of the problem. Now, choose the half-plane which includes $-i$. That is that answer for the first part.


TITLE: Scheme $\{x\in \mathbb{R}^{d}:|x^{2}|\leq \varepsilon\}$ glued by which affine schemes?
QUESTION [0 upvotes]: I am trying to see why the $\{x\in \mathbb{R}^{d}:|x^{2}|\leq \varepsilon\}$ (equipped with a ring, say sheaf of continuous functions on that set) is a scheme i.e.to which affine schemes is it locally isomorphic to; to which spectrum of a commutative ring?
My background is in analysis, so I would appreciate any comments/remarks from there.
I am trying to find a simple example of a scheme with an analytic flavour to it.
Attempt
I am thinking of schemes as manifolds with the parameter space being algebraic varieties of polynomials i.e. locally viewed as the locus of a system of polynomials.
The "thickened variety" is $\{x\in \mathbb{R}^{d}:|x^{2}|\leq \varepsilon\}=B_{0}(\sqrt{\varepsilon})$. So is one possible "gluing" the locus of the equations $\{x_{1}^{2}+...+x_{d}^{2}=r^{2}\}$ for all $r\leq \sqrt{\varepsilon}$?

REPLY [1 votes]: I think the issue your idea of a scheme. As you say, each scheme is a locally ringed space (topological space+sheaf of functions), but everything must be defined algebraically.
The functions on a scheme are only the algebraic ones (e.g. polynomials), which is a much smaller ring than all continuous functions. Also, the topological space must be cut out by polynomials using equalities only, we cannot use inequalities. Because you have less choice, everything is more rigid in algebraic geometry.
If we blindly take the spectrum of something like $C[0,1]$, we get something pathological that doesn't reflect $[0,1]$.
I'm no expert on this stuff, but I think the "Tate algebra" and "rigid analytic varities" are closer to what you want. Here, we can define a disk of radius $r$, but it's over a nonarchimedian field instead of $\mathbb{R}$.


TITLE: Blind deconvolution of a function convolved with itself
QUESTION [1 upvotes]: I have a function/vector $f$ that I know is the result of an unknown function $g$ convolved with itself:
$f = g \ast g$
Is there any way to do a blind deconvolution on $f$ with this constraint?

REPLY [2 votes]: Taking the Fourier transform, we have
$$
\widehat{f} = \widehat{g}^2,
$$
so that $\widehat{g} = \sqrt{\widehat{f}}$.  Then take the inverse Fourier transform to find $g$.  This doesn't quite work, I think, because you have to choose a branch of the square root.  I think this shows the solution is not unique, but you can still find them by this method.


TITLE: Can this system of equations be solved?
QUESTION [3 upvotes]: I'm doing some Lagrange multiplier examples that I thought up and I was trying to think of an example where the method of 'solving the constraint explicitly' fails. I'm trying to maximize
$$f(x,y)=x^2 y + y^2 x$$
given the constraint
$$g(x,y)=xe^x +ye^y -1 =0$$
I made this constraint up because I'm pretty sure it can't be solved explicity for either variable. Now, I form the Lagrange function
$$F(x,y)=f(x,y)-\lambda g(x,y)$$
and differentiate w.r.t. $x$ and $y$ and solve the system of equations:
$$0=2xy+y^2- \lambda (x+1) e^x$$
$$0=2xy+x^2- \lambda (y+1) e^y$$
Theoretically I should be able to solve this for $x$ and $y$ that depend on $\lambda$ and then choose the $\lambda$ so the constraint is actually satisfied, but I don't know how to do that.
Instead, I tried 'solving' for $\lambda$ from the first one and substitute into the other and I get
$$(2xy+y^2)(y+1)e^y=(2xy+x^2)(x+1)e^x$$
Dividing by $xy$ (this excludes any points on either axis), I get
$$(2+\frac{y}{x})(y+1)e^y=(2+\frac{x}{y})(x+1)e^x$$
Which is like saying $$h(x,y)=h(y,x)$$ where $h$ is either side of the previous equation. Again, I'm not sure what to do at this point.

REPLY [1 votes]: The constraint and function are unchanged by swapping $x$ and $y$, so the point with $y=x$ must be a maxima or minima, in this case $x=W(\frac{1}2)$ where $W$ is the Lambert W function.


TITLE: How to write recursive formula as explicit (specifically, exponential)?
QUESTION [0 upvotes]: I recall learning in school how to convert arithmetic and geometric sequence formulas between recursive and explicit, but I don't remember learning a systematic method to approach it. For example, let $a_n=2a_{n-1}+2$ where $a_0=5$. How would I convert this to an explicit form defined in terms of $n$? Beyond this specific example, is there a generalized method to do so?

REPLY [1 votes]: Leu us consider the general case of $$a_n=\alpha\, a_{n-1}+\beta$$ Let first $a_n=b_n+\gamma$ which makes
$$b_n+\gamma=\alpha\,(b_{n-1}+\gamma)+\beta\implies b_n=\alpha\,b_{n-1}+(\alpha\gamma+\beta-\gamma)$$ To come back to something simple, let (assuming $\alpha\neq 1$)
$$\alpha\gamma+\beta-\gamma=0 \implies \gamma=\frac \beta {1-\alpha}$$ So, we are left with
$$ b_n=\alpha\,b_{n-1} \implies b_n=c \,\alpha^{n-1}\implies a_n=c\, \alpha^{n-1}+\frac \beta {1-\alpha}$$


TITLE: In each cell of $n$x$n$ is a number so that in every $3$x$3$ subtable the sum of numbers is negative and the sum of all numbers is positive.
QUESTION [2 upvotes]: In each unit cell of a $n\times n$ table we have a number so that in every $3\times 3$ subtable the sum of numbers is negative and the sum of all numbers is positive.
  For which $n\geq 4$ we can have such an arangement?

Clearly we don't have such an arangement if $3\mid n$. Now suppose $3\nmid n$. Then if $n=7$ (or $3$ or $10$ or $13$) we see that a configuration
\begin{array} {|r|r|r|r|r|r|r|}
\hline
7 & -1 & -1& 7&-1&-1&7 \\
\hline
-1 & -1 & -1& -1&-1&-1&-1 \\
\hline
-1 & -1 & -1& -1&-1&-1&-1 \\
\hline
7 & -1 & -1& 7&-1&-1&7 \\
\hline
-1 & -1 & -1& -1&-1&-1&-1 \\
\hline
-1 & -1 & -1& -1&-1&-1&-1 \\
\hline
7 & -1 & -1& 7&-1&-1&7 \\
\hline
\end{array}
works. So I tried to generalise this for an arbitrary $3n+1$, instead of $7$ we put a positive $a$ and instead of $-1$ we put a negative $b$. So I have to prove that there are such $a,b$ that satisfies $a+8b<0$ and $$(n+1)^2a+(8n^2+4n)b>0$$
for an arbitrary $n$, but I fail to do that. Any idea how to solve this.

REPLY [3 votes]: For every $n$ the quotient
$$
Q = \frac{8n^2 + 4n}{(n+1)^2} < 8.
$$
That means you can always find $a$ and $b$ such that
$$
Q < \frac{a}{b} < 8.
$$
$Q$ has limit $8$ so if you want integers for $a$ and $b$ they will have to be large when $n$ is large.