% PREPRINT 2000 P 3983
\documentclass{article}
\usepackage{amsmath,amsthm,amssymb,amsfonts}
\title{Dynamically defined recurrence dimension}
\author{Petr K\accent23urka, Vincent Penn\'e, Sandro Vaienti}
\font\msbm=msbm10 scaled 1200
\font\eufm=eufm10 scaled 1200
\font\eufb=eufb10 scaled 1200
\newtheorem{dfn}{Definition}
\newtheorem{thm}{Theorem}
\newtheorem{pro}[thm]{Proposition}
\newtheorem{exm}{Example}
\newtheorem{lem}{Lemma}
% ** If you dont have amsmath and amsthm, uncomment these **
%\newtheorem{proof}{Proof}
%\newcommand{\text}{\mbox}
\newcommand{\D}{\displaystyle}
\newcommand{\T}{\textstyle}
\newcommand{\diam}{{\rm diam}}
\newcommand{\card}{{\rm card}}
\newcommand{\supp}{{\rm supp}}
\newcommand{\Per}{{\rm Per}}
\newcommand{\sgn}{{\rm sgn}}
\newcommand{\ep}{\varepsilon}
\newcommand{\la}{\lambda}
%\newcommand{\mod}{\;{\rm mod}\;}
\newcommand{\QED}{$\Box$}
\newcommand{\oo}{\mbox{\eufb o}}
\newcommand{\CC}{\mbox{\eufb C}}
\newcommand{\zer}{{\bf 0}}
\newcommand{\one}{{\bf 1}}
\newcommand{\two}{{\bf 2}}
\newcommand{\ix}{{\bf x}}
%\newcommand{\ZZ}{Z\!\!\!Z}
\newcommand{\ZZ}{\mathbb Z}
%\newcommand{\NN}{I\!\!N}
\newcommand{\NN}{\mathbb N}
%\newcommand{\RR}{I\!\!R}
\newcommand{\RR}{\mathbb R}
\newcommand{\clop}{{\cal V}}
\newcommand{\cir}{{\cal S}^1}
\newtheorem*{rem}{Remark}
\begin{document}
\maketitle
\begin{abstract}
In this paper, we introduce and characterize the
\emph{dynamically defined recurrence dimension}, a new topological invariant
number, following
the idea of a previous article \cite{Penne}, but with some modifications
and improvements. We study some example of Toeplitz subshifts
for which we can show that the recurrence dimension is a topologically
invariant number different from the \emph{topological entropy}.
\end{abstract}
\section{Introduction}
In \cite{afr1} V. Afraimovich proposed to
study the scaling properties of recurrence time by defining, through the
Caratheodory construction, a dimension called either
{\it recurrence dimension} or {\it Afraimovich-Pesin} (AP){\it dimension}
in \cite{Penne}. This dimension is
a variant of the Hausdorff dimension, with the diameter of a set replaced
by some gauge functions of the smallest return
time of the set into itself (Poincar\'e recurrence of the set).
Afraimovich investigated mainly irrational rotations and
used $1/t$ as a gauge function. In \cite{Penne},
a systematic study of the AP-dimension was carried out with
the use of another gauge function, $e^{-t}$ , and we remind here
the principal result of this analysis:
\begin{enumerate}
\item It was proved that the AP-dimension is a topological invariant.
\item It was proved the equivalence of the AP-dimension with the
topological entropy for a large class of dynamical systems
(subshifts of finite type and Axiom-A systems), and a few examples were
exhibited where the AP-dimension was different from
the topological entropy.
\item It was proved a general lower bound for the AP-dimension in terms
of the asymptotic distribution of the periodic points,
$\limsup_{n\rightarrow\infty} \log \frac{Per(n)}{n}$.
\item The notion of the AP-dimension of a measure was introduced, as
the infimum of the AP-dimensions of the sets of full
measure~; it was proved that is was a metric invariant and that for
aperiodic dynamical systems its value was
always zero.
\end{enumerate}
All these results were obtained by considering general open and closed
covers in the Caratheodory construction, in the attempt
to conform the theory to the usual construction of the Hausdorff measures.
If, from one hand, this approach allowed to give
general topological and metric characterizations like those quoted above,
on the other hand it revealed difficult
to compute the AP-dimension in particular
examples and especially to answer the basic question
adressed in
\cite{Penne}, namely: is it possible to exhibit a system
where the AP-dimension is different from the
asymptotic distribution of periodic points? Translated to minimal
dynamical systems, this would mean to find a system with
positive AP-dimension: in this case the AP dimension will really impose
as a new topological invariant to classify such
systems and describe their recurrence properties.\\ A first step in this
direction was obtained by Bruin \cite{Bruin}; he
considered subshifts and he proved that the AP-dimension does not exceed
its
topological entropy; moreover he provided a non trivial example where the
bound is strict.\\ A second improvement was given by
Kurka and Maas \cite{Kurka}. Trying to answer the question adressed
above and motivated by Bruin's result, these authors
studied large classes of minimal subshifts with positive topological
entropy (Toeplitz subshifts and Vershik systems defined by
Bratelli diagrams): in all these cases they showed that the AP-dimension
is zero. The conclusion of Kurka and Maas was that
the class of open covers used in the definition of the AP-dimension was
too large to get a distinguishing topological
invariant. Consequently and still in subshifts, they modified the
definition by replacing the open covers with dynamically
defined partitions into cylinders of the same type of those used in the
computation of topological entropy and pressure for
non-compcat sets \cite{Pesin}. This new structure enjoyed the properties
(1) and (3) quoted above and Bruin's general bound
in terms of the topological entropy; moreover the associated AP-dimension,
which Kurka and Maas called {\it recurrence
dimension} and from now on we will conform to this definition, was found
to be positive for a particular Toeplitz subshift.\\\\
In the present article we follow the same strategy with a few differences
and novelties:
\begin{itemize}
\item We slightly modify the partition into cylinders (see Def. 1 below),
with the aim to obtain a set function, arising from
the Caratheodory construction, which is a {\it Borel measure}. This will
allow us to get some interesting topological
characterizations of the recurrence dimension, besides those quoted above
which still persist, for example the specification
of the recurrence dimension on the non-wandering set. Moreover our
definition could be extended to non zero-dimensional
dynamical systems; we discuss this shortly later although some problems
remain to be solved to get all the desired properties
in the general case.
\item With our new partition, we are able to construct Toeplitz subshifts
with positive recurrence dimension and Toeplitz
subshifts where the recurrence dimension and the topological entropy differ.
\item In section 3 we introduce the {\it polynomial recurrence dimension}
by using the gauge function $1/t$ in the
Caratheodory sum. This dimension will be related to what we call {\it
polynomial entropy}, which is the exponent of the
algebraic growth of the complexity function, whenever the topological
entropy of the subshift is zero. The polynomial
recurrence dimension is therefore computed for sturmian subshifts, thus
completing and improving the previous work of
Afraimovich on irrational rotations \cite{afr1}, and finally for
some Toeplitz flows for which results of general type
hold (Examples 5 and 6).
\end{itemize}
The Caratheodory structures used in this paper are close to the partition
functions employed in the thermodynamic
formalism. Recently Afraimovich and co-workers \cite{afr2}
constructed partition functions where, besides the
exponential of negative Poincar\'e recurrence of a cylinder, there is some
power of the measure of the cylinder. This would
allow to get some sort of multifractal analysis of the systems through the
definition of a whole spectrum of recurrence
dimensions. The meaning of these "generalized recurrence dimensions" is
not yet clear and their computation and
interpretation in the context of the Toeplitz flows analysed in this
paper is surely an interesting challenge.\\
We briefly spoked, at the beginning of this Introduction, of the
recurrence dimension of a mesure; its value was always zero
with the former definition of the AP-dimension. It would be interesting to
reconsider this dimension in the framework
develloped in this paper. There is no reason that it is again zero; on the
contrary it could classify the invariant measures
or, in the case of a uniquely ergodic systems, it could give a new metric
invariant.\\ As a final remark, we would like to
point out that the main interest of this paper was to study the recurrence
dimension for minimal sets, just to show that it is
a non-trivial topological invariant and we investigated in detail its
relationship with other ergodic quantities like
topological entropy and the algebraic growth rate of complexity. The
variety of behaviors of this dimension shows that it
captures fine combinatorial structures of the underlying symbolic systems.
The role of this dimension for systems with higher
chaotic behavior, partially disclosed in \cite{Penne} and
actually pursued by several people, is a very
promising field of research.
\section{Exponential dynamic recurrence dimension}
\subsection{Definition and properties}
In this article, unless precised, we will consider a dynamical system to be a
couple $(X,f)$, where $X$ is a compact metric
space and $f: X \to X$ is a continuous mapping. We consider dynamical
systems on zero-dimensional spaces. A space $X$ is zero-dimensional,
if for every distinct points $x,y \in X$ there
exist disjoint clopen sets $U \ni x$, $V \ni y$. Every zero-dimensional space
is homeomorphic to a subspace of $A^{\NN}$, where $A$ is a finite alphabet.
A clopen partition of a
zero-dimensional space $X$ is a system ${\cal V} = \{V_a:\; a \in A\}$
of nonempty clopen sets $V_a \subseteq X$, which are pairwise disjoint
and their union is $X$. The diameter of a clopen partition is
$\diam({\cal V}) = \max\{\diam(V):\; V \in {\cal V}\}$.
Let ${\cal V} = \{V_a:\; a\in A\}$ be a clopen partition of $X$.
We'll use the notation $A^* = \bigcup_{k>0}A^k$, i.e. the set of all word of
finite length.
For $u \in A^* \cup A^{\NN}$ put
$$ V_u = \{x\in X:\; \forall i<|u|, f^i(x) \in V_{u_i} \} $$
Then
$$ {\cal V}^n = \{V_u:\; u \in A^n,\; V_u \neq \emptyset \}$$
is also a clopen partition. We say that ${\cal V}$ is generating, if
$\diam({\cal V}^n) \to 0$ as $n\to\infty$.
The Poincar\'e recurrence time of a subset $Y \subseteq X$ is
$$ \tau(Y) = \min\{k>0:\; f^k(Y) \cap Y \neq \emptyset \}$$
\begin{dfn}
Let $(X,f)$ be a zero-dimensional dynamical system, ${\cal V}$ a clopen
partition of $X$, $Y \subseteq X$, and $\alpha >0$. Using upper
and lower limits we define the (exponential) upper and lower recurrence
dimensions $\overline r(Y,f)$ and $\underline r(Y,f)$ of $Y$ as
\begin{eqnarray*}
\overline{\underline M}(Y,f,{\cal V},\alpha) &=& \overline{\underline \lim}_{n\to\infty}
\sum_{V \in {\cal V}^n, V\cap Y\neq\emptyset} e^{-\tau(V)\alpha}, \\
\overline{\underline R}(Y,f,{\cal V}) &=& \sup \{\alpha>0:\;
\overline{\underline M}(Y,f,{\cal V},\alpha) = \infty\},\\
\overline{\underline m}(Y,f,\alpha) &=& \lim_{\epsilon\rightarrow 0}
\sup \{\overline{\underline M}(Y,f,{\cal V}, \alpha):\;
\diam({\cal V}) < \epsilon , {\cal V} \text{ clopen partition of $X$}\}, \\
\overline{\underline r}(Y,f) &=& \sup \{\alpha>0:\;
\overline{\underline m}(Y,f,\alpha)=\infty \}.
\end{eqnarray*}
\end{dfn}
Clearly, the upper and lower recurrence dimensions are topologicaly invariants.
We now explain how this definition has been chosen :
\begin{itemize}
\item The set function
$m$ is defined similarly as in \cite{Penne}, except that we restrict ourself
to a specific family of covering, namely a partition and its refinements.
\item We then define $M$ over all partitions in order to get rid of the
arbitrary choice of initial partition. Taking partitions of diameter going to
zero insure us that we get a topologicaly invariant number. The choice of
the upper limit in $\epsilon$ rather than the lower limit is done to get
the nice property (Proposition \ref{nice prop}) that if we consider a
generating
partition, then the dimension $R$ calculated with this partition will be equal
to $r$. Taking the lower limit would not in general bring this property.
%This property is false if we choose the lower limit, the reason comes
%from the fact that $m(X, \alpha)$ as a function of $\alpha$ does not
%always have a \emph{sharp}
%critical exponent, i.e. there is not a number $\alpha_c$ such that
%$m(X, \alpha)$ is equal to $\infty$ if $\alpha<\alpha_c$ and is
%equal to $0$ if $\alpha>\alpha_c$.
\item Finally we define the critical exponent
$r$ as the supremum over all $\alpha$ such that $m(X, \alpha)=\infty$,
which is of course always well defined. Taking the infimum over all
$\alpha$ such that $m(X, \alpha)=0$ gives a less interesting result
since it would give us $\infty$ for every dynamical systems containing
periodic points.
\end{itemize}
\begin{rem}
One could generalize this definition to higher dimensions using homogeneous
spaces and topological partitions.
A metric space is homogeneous, if all its nonempty open set has the same
topological dimension. A topological partition of a homogeneous space
is a finite collection ${\cal V}$ of its open sets, such that for $V,V'
\in {\cal V}$, $V \cap V' = \emptyset$, the (topological) dimension of
$\overline{V} \cap \overline{V'}$ is strictly smaller than the
dimension of $X$, and $\{\overline{V}: V \in {\cal V}\}$ covers $X$.
In zero-dimensional spaces, topological partitions are just clopen partitions.
In real interval, topological partitions consist of finite unions of
open intervals.
\end{rem}
>From now on, we write $r(Y,f)$ whenever the same arguments or statements
apply for both $\overline r(Y,f)$ and $\underline r(Y,f)$, and similarly for
$m$, $M$ and $R$.
\begin{pro} \label{sharp}
If $(X,f)$ is minimal, then
$$ r(A,f) = \inf \{\alpha>0:\; m(A,f,\alpha)=0 \}.$$
\end{pro}
The proof of this fact can be easily adapted from the original article of
V.~Afraimovich \cite{afr1}.
\begin{pro}
The set function $m(.,f,\alpha)$ is a borelian measure.
\end{pro}
\begin{proof}
These are standard arguments for construction of this type.
We first check that it is an outer measure. First it is
monotonic, i.e. $Y\subset Z \Rightarrow m(Y,f,\alpha)\leq m(Z,f,\alpha)$.
It is also $\sigma-$sub-additive, i.e. $m(\bigcup_k U_k,f,\alpha) \leq
\sum_k m(U_k,f,\alpha)$. For details of such proof, see for instance
\cite{Pesin}.
To become a borelian measure, it just needs to verify the following property :
$d(Y,Z)>0 \Rightarrow m(Y\cup Z,f,\alpha)=m(Y,f,\alpha) + m(Z,f,\alpha)$.
This follows immediately from the fact that in the definition
of $M$, we take partitions ${\cal V}$ with diameter going to zero, thus
$Y$ and $Z$ are covered by different sets of the same partitions.
\end{proof}
\begin{pro} \label{prop ineq}
Let $(X,f)$ be a dynamical system and $Y\subseteq X$ an invariant
subset. Then
$$ m(Y,f_{|Y},\alpha) \leq m(Y,f,\alpha) \leq m(X,f,\alpha) $$
$$ r(Y,f_{|Y}) \leq r(Y,f) \leq r(X,f) $$
\end{pro}
\begin{proof}
Let ${\cal V}$ be a clopen partition of $Y$, $\diam({\cal V}) <
\ep$, $\eta > 0$, and $V \in {\cal V}$. Since $V$ is open in $Y$,
for every $x \in V$ there exists $0 < \delta_x < \eta$, such that
$B_{\delta_x}(x) \cap Y \subseteq V$, and $B_{2\delta_x}(x) \cap V' =
\emptyset$ for every $V \neq V' \in {\cal V}$. Let $K \subset V$
be a finite subset such that $\{B_{\delta_x}(x): x \in K\}$ is a
finite cover of $V$, and let $W_V = \bigcup_{x\in K}B_{\delta_x}(x)$.
Since $X$ is totally disconnected, the balls are clopen, so $W_V$
is clopen too, $V = Y \cap W_V$, and $W_V \cap W_{V'} =
\emptyset$, if $V \neq V'$. Let ${\cal W}$ be the clopen cover
consisting of all $W_V, V\in\clop$ and a clopen cover of the complement of
$\bigcup_{V\in\clop} W_V$. Then
${\cal W}$ is a clopen cover of $X$. We get ${\cal V}^n =
\{Y \cap W:\; W \in {\cal W}^n\}$ and $\tau(Y \cap W) \geq \tau(W)$, so
$$ M(Y,f_{|Y},{\cal V},\alpha) \leq M(Y,f,{\cal W},\alpha) $$
Since $\diam({\cal W}) \leq \ep + 2\eta$ for arbitrary small
$\eta$, $m(Y,f_{|Y},\alpha) \leq m(Y,f,\alpha)$. From the
preceding Proposition we get $m(Y,f,\alpha) \leq m(X,f,\alpha)$.
\end{proof}
>From now on, we leave out $f$ in the formulas for $m,M,R,r$.
\begin{pro}
Let $(X,f)$ be a zero-dimensional dynamical system and
$$ Q(n) = \card\{x\in X:\; f^n(x) = x\}.$$
Then
$$ \overline{r}(X) \geq \limsup_{n\to\infty} \frac{\ln Q(n)}{n},\;\;
\underline{r}(X) \geq \liminf_{n\to\infty} \frac{\ln Q(n)}{n} $$
\end{pro}
\begin{proof} Suppose that for every $n$, $Q(n)$ is finite.
For every $n$ there exists $\ep>0$, such that if $f^n(x)=x$,
$f^n(y)=y$, then $d(x,y)>\ep$. If $\diam({\cal V}) < \ep$, then for every $k$
$$ \sum_{V \in {\cal V}^k} e^{-\tau(V)\alpha} \geq Q(n)e^{-n\alpha}$$
If $\alpha < \beta < \limsup_{n\to\infty}\frac{\ln Q(n)}{n}$,
then for an infinite number of $n$, $Q(n) e^{-n\alpha} \geq
e^{n(\beta-\alpha)}$, so $\overline{M}(X,{\cal V},\alpha) = \infty$,
$\overline{m}(X,\alpha) = \infty$ and $\alpha < \overline{r}(X)$.
Similarly for lower limits.
\medskip\\
\end{proof}
\begin{pro} \label{nice prop}
Let $\clop$ be a generating clopen partition. Then $r(X) = R(X,\clop)$.
\end{pro}
We will use the following lemma :
\begin{lem} \label{lemma}
Let ${\cal U}$ and ${\cal V}$ two clopen \emph{generating} partitions of $X$,
then one can find a constant $0n$, ${\cal U}^{k+m}
\succeq {\cal V}^k \succeq {\cal U}^{k-n}$. Every $V \in {\cal
V}^k$ is a subset of some set $U \in {\cal U}^{k-n}$ and a union
$V = U_1 \cup \cdots \cup U_p$, of at most $p
\leq |{\cal U}|^{n+m}$ sets $U_i \in {\cal U}^{k+m}$. We get $\tau(V) \leq
\tau(U_i)$, so
$$ p \cdot e^{-\tau(V)\alpha} \geq e^{-\tau(U_1)\alpha} + \cdots +
e^{-\tau(U_p)\alpha} $$
$$ \sum_{V\in {\cal V}^k} e^{-\tau(V)\alpha} \geq
|{\cal U}|^{-n-m} \sum_{U\in {\cal U}^{k+m}} e^{-\tau(U)\alpha}. $$
Thus $M(X,{\cal V},\alpha) \geq |{\cal U}|^{-m-n} \cdot
M(X,{\cal U},\alpha)$. Interchanging ${\cal U}$ and ${\cal V}$,
we obtain the result.
\end{proof}
\begin{proof}[Proof of the Proposition]
It is well known that if there exists a generator, then there exists an
$\epsilon>0$ such that any clopen partition of diameter less than $\epsilon$ is
also generating. For a given $\alpha$,
let us choose a sequence $\clop_1, \clop_2, \ldots$ of clopen partitions with
diameter going to zero
such that $M(X, \clop_n, \alpha)$ decreases and converges to
$m(X, \alpha)$.
Thus, for $n$ big enough, $\clop_n$ is generating, and we can apply
Lemma \ref{lemma} with $\clop$ and $\clop_n$ for each $n$.
If $\alpha < R(X, \clop)$, then by Lemma \ref{lemma},
$C M(X, \clop_n,\alpha) \geq M(X, \clop, \alpha) = \infty$,
thus since this apply for any $n$ large enough and any $\alpha R(X, \clop)$, then for some $k$ large enough,
$M(X, \clop_k, \alpha)\leq C M(X, \clop, \alpha)<\infty$. Then, since the
sequence $M(X, \clop_n, \alpha)$ is decreasing, this shows that
$m(X, \alpha)<\infty$. This is true for any $\alpha > R(X,\clop)$, thus
$r(X)\leq R(X, \clop)$.
\end{proof}
Recall that a point $x \in X$ is non-wandering, if every its
neighborhood has finite recurrence time. It is a known fact that the
topological entropy of a dynamical system is equal to the topological entropy
of the system restricted to the set of non-wandering points. Here we get
a similar result, not as strong because in Proposition \ref{prop ineq} we have
only an inequality in the first part of the statement.
\begin{pro}
Let $(X, f)$ a zero dimensional dynamical system, and $\Omega$ the set
of non-wandering points, then $r(X) = r(\Omega)$.
\end{pro}
\begin{proof}
If we denote $W = \Omega^c$ the complement of $\Omega$, then for any
point $x\in W$, one can find an open set $U(x)$ such that
$\tau(U(x))=\infty$. Since $W$ is separable, the cover $\{U(x): x
\in W\}$ of $W$ has a countable sub-cover ${\cal F}$.
By $\sigma$-additivity, we have $m(W,\alpha) \leq
\sum_{F\in{\cal F}} m(F,\alpha) = 0$, $m(\Omega,\alpha)=
m(X,\alpha)-m(W,\alpha) = m(X,\alpha)$, and $r(X) = r(\Omega)$.
\end{proof}
For a finite alphabet $A$ denote by $A^{\NN}$ the space of one-sided
sequences of letters of $A$ and $(A^{\NN},\sigma)$ the shift dynamical
system.
A sub-shift is any subset $\Sigma \subseteq A^{\NN}$ which is closed and
$\sigma$-invariant. We denote by ${\cal L}(\Sigma) \subseteq A^*$ the
language of words appearing in $\Sigma$ and ${\cal L}^n(\Sigma) =
{\cal L}(\Sigma) \cap A^n$.
The size of a finite set $A$ is denoted by
$|A|$, and the length of a word $u \in A^n$ is denoted by $|u| = n$.
Denote by $P(n) = |{\cal L}^n(\Sigma)|$ the number of cylinders of length $n$.
The topological entropy of a sub-shift is $h(\Sigma) = \lim_{n\to\infty}
\frac{\ln P(n)}{n}$.
The following result has first been proved by H.Bruin \cite{Bruin},
in a slightly different
context.
\begin{pro}
The recurrence dimension of a sub-shift is less or equal to its topological
entropy.
\end{pro}
\begin{proof} Let $P(n)$ be the number of cylinders of length $n$.
If $u \in {\cal L}^n(\Sigma)$ and $\tau[u] = k < n$, then
$u_{k+i} = u_i$ for all $i \in [0,|u|)$, so the number
of cylinders of length $n$ with the return time $k$ is at most the
number of cylinders of length $k$. For $\tau[u]=k\geq n$ we use
$e^{-\tau[u]} \leq e^{-n}$ to obtain
\begin{eqnarray*}
\sum_{u \in {\cal L}^n(\Sigma)} e^{-\tau[u]\alpha} &\leq&
\sum_{k=1}^{n} P(k)\cdot e^{-k\alpha} \\
M(\Sigma,\alpha) &\leq&
\sum_{k=1}^{\infty} P(k)\cdot e^{-k\alpha}
\end{eqnarray*}
If $\lim_{k\to\infty}\frac{\ln P(k)}{k} < \beta < \alpha$,
then there exists $k_0$,
such that for all $k\geq k_0$, $P(k)e^{-k\alpha} \leq e^{k(\beta-\alpha)}$,
so $M(\Sigma,\alpha) < \infty$, and $r(\Sigma) \leq \alpha$. Thus we get
$$ r(\Sigma) \leq \lim_{k\to\infty} \frac{\ln P(k)}{k}
= h(\Sigma)$$
\end{proof}
Combining Propositions 4 and 7 we get that the recurrence dimension
of a sofic sub-shift is equal to its topological entropy.
\begin{pro} \label{prodimab}
Let $\Sigma \subseteq A^{\NN}$ be a sub-shift and $a,b >0$. Then
\begin{eqnarray*}
\forall n_0, \exists n\geq n_0, \forall u \in {\cal L}^n(\Sigma),
\tau[u] \leq b|u| &\Rightarrow&
\overline{r}(\Sigma) \geq h(\Sigma)/b \\
\exists n_0, \forall n\geq n_0, \forall u \in {\cal L}^n(\Sigma),
\tau[u] \leq b|u| &\Rightarrow&
\underline{r}(\Sigma) \geq h(\Sigma)/b \\
\forall n_0, \exists n\geq n_0, \forall u \in {\cal L}^n(\Sigma),
\tau[u] \geq a|u| &\Rightarrow&
\underline{r}(\Sigma) \leq h(\Sigma)/a \\
\exists n_0, \forall n\geq n_0, \forall u \in {\cal L}^n(\Sigma),
\tau[u] \geq a|u| &\Rightarrow&
\overline{r}(\Sigma) \leq h(\Sigma)/a
\end{eqnarray*}
\end{pro}
\begin{proof}
1. Let $\alpha < h(\Sigma)/b$, and choose $\beta$ with
$\alpha < \beta < h(\Sigma)/b$. There exists $n_0$ such that for all
$n \geq n_0$, $P(n) > e^{bn\beta}$. If for all $u \in {\cal
L}^n(\Sigma)$, $\tau[u] \leq b|u|$, then
$$ \sum_{u \in {\cal L}^n(\Sigma)} e^{-\tau[u]\alpha} \geq P(n) e^{-bn\alpha}
> e^{bn(\beta-\alpha)} \to \infty $$
If this holds for infinite number of $n$, then
$\overline{M}(\Sigma,{\cal A},\alpha) = \infty$ and
$\overline{r}(\Sigma) \geq \alpha$, so $\overline{r}(\Sigma)
\geq h(\Sigma)/b$.\\
2. If this holds for all sufficiently large $n$, then
$\underline{M}(\Sigma,{\cal A},\alpha) = \infty$ and
$\underline{r}(\Sigma) \geq \alpha$, so $\underline{r}(\Sigma)
\geq h(\Sigma)/b$.\\
3. Let $\alpha > h(\Sigma)/a$, and choose $\beta$ with
$\alpha > \beta > h(\Sigma)/a$. There exists $n_1$ such that for all
$n \geq n_1$, $P(n) < e^{an\beta}$. For an infinite number of $n$ we have
$a|u| \leq \tau[u]$ for all $u \in {\cal L}^n(\Sigma)$, and
$$ \sum_{u \in {\cal L}^n(\Sigma)} e^{-\tau[u]\alpha} \leq P(n) e^{-an\alpha}
< e^{an(\beta-\alpha)} \to 0 $$
Thus $\underline M(\Sigma,{\cal A},\alpha) = 0$ and $\underline r(\Sigma)
\leq \alpha$.\\
4. If this holds for all sufficiently large $n$, then $\overline{M}(\Sigma,
{\cal A},\alpha)=0$ and $\overline{r}(\Sigma) \leq \alpha$, so
$\overline{r}(\Sigma) \leq h(\Sigma)/a$.
It follows $\underline{r}(\Sigma) \leq h(\Sigma) / a$.
\end{proof}
\subsection{Examples}
We construct several examples of Toeplitz sub-shifts.
For a point $x \in A^{\NN}$, $p>0$ put
$$ \Per_p(x) = \{k \in \NN:\; \forall n \in \NN, x_{k+np} = x_k \} $$
The $p$-skeleton $y = S_p(x) \in (A\cup\{*\})^{\NN}$ of $x$ is obtained
from $x$ by replacing $x_i$ by $*$ for every $i \not\in \Per_p(x)$,
so $y_i = x_i$ if $i \in \Per_p(x)$, and $y_i = *$ otherwise.
A sequence $x \in A^{\NN}$ is a Toeplitz sequence, if the union of all
$\Per_p(x)$ is $\NN$. A Toeplitz sub-shift is the orbit closure of a
Toeplitz sequence $\Sigma_x = \overline{\oo(x)}$. If $x$ is a Toeplitz
sequence, then $\sigma^p(S_p(x)) = S_p(x)$. An integer $p>1$ is an
essential period of $x$, if $S_p(x)$ is not periodic with any smaller
period than $p$. A periodic structure for an
aperiodic Toeplitz sequence $x \in A^{\NN}$ is a sequence
$p = (p_i)_{i \geq 0}$ such that every $p_i$ is an essential period of
$x$, $p_i$ divides $p_{i+1}$ and the union of all $\Per_{p_i}(x)$ is
$\NN$.
\begin{exm}
There exists a Toeplitz sub-shift $\Sigma$ with
$\underline{r}(\Sigma) \geq h(\Sigma)/2 > 0$.
\end{exm}
\begin{proof} Define sequences $(p_i)_{i\geq 0}$, $(q_i)_{i\geq 0}$ by
$$ p_0 = 3,\; q_0 = 2,\;
p_{n+1} = p_n\cdot 2^{q_n},\; q_{n+1} = q_n\cdot (2^{q_n}-1) $$
so $p_1=12$ and $q_1 = 6$. Construct a sequence of words
$v_n \in \{0,1,*\}^{p_n}$, $w_n \in \two^{p_n}$.
\begin{eqnarray*}
v_0 = {\tt 0\!*\!*}, & & v_1 = {\tt 0000\!*\!*\!0\!*\!*\!0\!*\!*} \\
w_0 = {\tt 000}, & & w_1 = {\tt 000001010011}
\end{eqnarray*}
Suppose we have constructed words $v_n,w_n$, with $|v_n| = |w_n|
= p_n$, $|v_n|_* = q_n$. This means that the number of stars in
$v_n$ is $q_n$. Put $v_{n+1} = w_n(v_n)^{2^{q_n}-1}$ and obtain
$w_{n+1}$ from $v_{n+1}$ by replacing the stars in every $v_n$
by a different combination of binary digits, different from
the combination used in $w_n$. There are exactly $2^{q_n}$
possibilities to do this,
so every combination is used exactly ones. Since $w_n$ is an initial
word of $w_{n+1}$, their limit $w = \D\lim_{n\to\infty} w_n$ is a Toeplitz
sequence with periodic structure $(p_n)_{n\geq 0}$ and skeletons
$(v_n)^{\infty}$. We show that for the sub-shift $\Sigma = \overline{\oo(w)}$,
$\tau[u] \leq 2|u|$ for every $u \in {\cal L}(\Sigma)$ with $|u| >6$.
There exist $k>0$ and $i \geq 1$ such that
$$ \frac{p_k}{2} < |u| \leq \frac{p_{k+1}}{2},\;
(i-1) p_k \leq |u| < i p_k$$
There exists $v \in {\cal L}(\Sigma)^{2ip_k}$ such that $v_{[0,|u|)} = u$
and $v_{[ip_k,ip_k+|u|)} = u$, so $\tau[u] \leq ip_k$. We distinguish
two possibilities
\begin{eqnarray*}
i = 1 &\Rightarrow & \tau[u] \leq p_k \leq 2|u| \\
i > 1 &\Rightarrow & \tau[u] \leq \frac{i}{i-1}|u| \leq 2|u|
\end{eqnarray*}
Thus $\underline{r}(\Sigma) \geq h(\Sigma) /2$. To see that the entropy of $\Sigma$
is positive, note that $P(p_n) \geq 2^{q_n}$ and
$$ \frac{\ln 2^{q_{n+1}}}{p_{n+1}} = \ln 2 \cdot \frac{q_{n+1}}{p_{n+1}}
= \ln 2 \cdot \frac{q_n}{p_n} \cdot \frac{2^{q_n}-1}{2^{q_n}} $$
Since $q_n >n$, we have
$$ \prod_{n=1}^{\infty} \frac{2^{q_n}-1}{2^{q_n}} >
\prod_{n=1}^{\infty} \frac{2^{n}-1}{2^{n}} > 0 $$
so $h(\Sigma) > \limsup_{n\to\infty} \frac{\ln 2^{q_n}}{p_n} > 0$.
\end{proof}
\begin{exm} \label{Toepzero}
There exists a Toeplitz sub-shift with lower recurrence dimension zero
and topological entropy positive.
\end{exm}
\begin{proof} We construct a Toeplitz sub-shift in alphabet
$A=\{0,1,2,3\}$. Put
$$ n_1 = 4,\; p_1 = 4,\; n_{k+1} = \frac{(n_k-k)!}{(n_k-2k)!}\cdot
(n_k-2k)^{2^{k+1}-2k},\; p_k = 2^2 \cdots 2^{k+1}$$
Put $A_k = \{0,1,\ldots,n_k-1\}$, so $A_1 = A$, $A_2 =
\{0,\ldots,11\}$. Construct injective substitutions
$\nu_k: A_{k+1} \to (A_k)^{2^{k+1}}$ such that for every $a \in A_{k+1}$,
$\nu_k(a)$ starts with $01\ldots k-1$, does not contain $0,1,\ldots k-1$
elsewhere, and if $\nu_k(a)_i = \nu_k(a)_j$, then $|i-j| \geq
k+1$. Thus for every $u \in A^*_{k+1}$, every letter in $\nu_k(u)$ differs
from $k$ preceding and $k$ succeeding letters. At position $k$ we have
$n_k-k$ possibilities, at position $k+i$ we have $n_k-k-i$
possibilities for $0\leq i\leq k$ and $n_k-2k$ for $i \geq k$. Thus
there are exactly
$$ n_{k+1} = (n_k-k)\cdots (n_k-2k+1) (n_k-2k)^{2^{k+1}-2k} $$
possibilities to construct $\nu_k(a)$. For example,
if we choose the words of $\nu_k(a)$ in lexicographic order, we get
\begin{eqnarray*}
\nu_1: A_2 &\mapsto& \{0121,0123,0131,0132,0212,0213,0231,0232
,\ldots,0323\} \\
\nu_2: A_3 &\mapsto& \{01234234,01234235,01234236,01234237,\ldots\}
\end{eqnarray*}
For every $k \geq 1$,
$\Sigma_k = \{\sigma^i\nu_1\ldots\nu_k(u):\ u \in
(A_{k+1})^{\NN}, i \geq 0 \} \subseteq A^{\NN} $
is a sub-shift of finite type, and $\Sigma_{k+1} \subseteq \Sigma_k$.
The intersection $\Sigma = \cap_k \Sigma_k$ is a Toeplitz sub-shift with
periodic structure $(p_{k+1})_{k\geq 0}$. It is generated by a Toeplitz
sequence with skeletons
\begin{center} \tt
0***0***0***0***0***0***0***0***0***0***0***0***0***0***0*** \ldots \\
012101230***0***0***0***0***0***0***0***0***0***012101230*** \ldots
\end{center}
For every $a \in A_2$, $\tau[\nu_1(a)] = 12 = 3|\nu_1(a)|$, and for every
$a \in A_{k+1}$,
$$ \tau[\nu_1 \ldots \nu_k(a)] = (k+2)p_k = (k+2)|\nu_1 \ldots \nu_k(a)| $$
If $u \in {\cal L}(\Sigma)$, and $|u| = 2p_k$ for some $k$, then there
exists $a \in A_{k+1}$ with $\nu_1\ldots \nu_k(a) \sqsubseteq u$, so
$$ \tau[u] \geq \tau[\nu_1\ldots \nu_k(a)] = (k+2)p_k = (\T\frac{k}{2}+1)|u|$$
By Proposition \ref{prodimab}, $\underline{r}(\Sigma) \leq
\frac{2h(\Sigma)}{k+2}$, so $\underline{r}(\Sigma) = 0$.
We have $P(p_k) \geq n_{k+1}$, $n_{k+1} > (n_k-2k)^{2^{k+1}-k}$, so
$$ \frac{\ln n_{k+1}}{p_{k}} \geq \frac{2^{k+1}-k}{2^{k+1}} \cdot
\frac{\ln(n_k-2k)}{\ln n_k} \cdot \frac{\ln n_k}{p_{k-1}} $$
Using l'Hospital rule, we get that the product
$\prod_k \frac{2^{k+1}-k}{2^{k+1}}$ is positive. Since $n_k > 2^{k+1}$
and the function $f(x) = \frac{\ln(x-2k)}{\ln x}$ is increasing,
$$ \prod_k \frac{\ln(n_k-2k)}{\ln n_k} \geq
\prod_k \frac{2^{k+1}-k}{2^{k+1}} > 0$$
is positive too and
$$ h(\Sigma) = \lim_{k\to \infty} \frac{\ln P(p_k)}{p_k} \geq
\lim_{k\to\infty} \frac{\ln n_{k+1}}{p_k} > 0 $$
\end{proof}
\begin{exm}
There exists a Toeplitz sub-shift with lower recurrence dimension zero
and upper recurrence dimension positive.
\end{exm}
\begin{proof} We modify Example \ref{Toepzero}, applying formulas for
$n_{k+1}$ and $\nu_k$ only for $k$ even. For $k$ odd, put $n_{k+1} =
n_k^{2^{k+1}}$ and construct a bijective substitution $\nu_k : A_{k+1}
\to (A_k)^{2^{k+1}}$. Thus for $k$ even and $u \in {\cal L}(\Sigma)$
with $|u| = 2p_k$ we get again $\tau[u] \geq (\frac{k}{2}+1)|u|$ and
$\underline{r}(\Sigma) = 0$. For $k$ odd, however, $\tau[u] \leq |u|$,
so $\overline{r}(\Sigma) = h(\Sigma) > 0$.
\end{proof}
\section{Polynomial entropy and dimension}
\subsection{Definition and properties}
When the topological entropy of a sub-shift is zero, its complexity function
$P(n)$ grows slower than any exponential. Its growth may be then polynomial
$P(n) \approx n^a$. We call $a \approx \frac{\ln P(n)}{\ln n}$ the polynomial
entropy. In contrast to the (exponential) entropy, the limit in
question need not exist, so we get lower and upper polynomial
entropies. They could be defined in arbitrary dynamical system using
open covers. For an open cover ${\cal V}$ of a compact metric space
denote by $|{\cal V}|$ the number of elements in its smallest
finite sub-cover.
\begin{dfn}
Let $(X,f)$ be a dynamical system and ${\cal V}$ an open cover
of $X$. The lower ($\underline h(X,f)$) and upper
($\overline{h}(X,f)$) polynomial entropies are defined by
\begin{eqnarray*}
\overline{\underline{H}}_p(X,f,{\cal V}) &=&
\overline{\underline{\lim}}_{n\to\infty} \frac{\ln |{\cal V}^n|}
{\ln n} \\
\overline{\underline{h}}_p(X,f) &=& \lim_{\ep\to\infty}
\sup\{\overline{\underline{H}}_p(X,f,{\cal V}):\;
\diam({\cal V})< \ep,\; {\cal V} \mbox{ open cover of }
X \}
\end{eqnarray*}
\end{dfn}
Similarly as for the (exponential) topological entropy we get
$$ \overline{\underline{h}}_p(X,f) = \lim_{n\to\infty}
\overline{\underline{h}}_p(X,f,{\cal V}_n) $$
whenever $({\cal V}_n)_{n\geq 0}$ is a sequence of open covers
with ${\cal V}_{n+1} \geq {\cal V}_n$ and $\diam({\cal V}_n) \to
0$ as $n \to \infty$. In particular for sub-shifts we get
$$ \underline{h}(\Sigma) = \liminf_{n\to\infty} \frac{\ln P(n)}{\ln n},\;\;
\overline{h}(\Sigma) = \limsup_{n\to\infty} \frac{\ln P(n)}{\ln n} $$
\begin{dfn}
Let $(X,f)$ be a zero-dimensional dynamical system, ${\cal V}$ a clopen
partition of $X$, $Y \subseteq X$, and $\alpha >0$. The lower polynomial
recurrence dimension $\underline{r}_p(Y,f)$ and the upper polynomial
dimension $\overline{r}_p(Y,f)$ of $Y$ is defined by
\begin{eqnarray*}
\overline{\underline {m}}_p(Y,f,{\cal V},\alpha) &=&
\overline{\underline \lim}_{n\to\infty}
\sum_{V \in {\cal V}^n, V\cap Y\neq\emptyset} \frac
{1}{{\tau(V)^\alpha}},\\
\overline{\underline {R}}_p(Y,f,{\cal V}) &=& \sup \{\alpha>0:\;
\overline{\underline {m}}_p(Y,f,{\cal V},\alpha) = \infty\},\\
\overline{\underline {M}}_p(Y,f,\alpha) &=& \lim_{\epsilon\rightarrow 0}
\sup \{\overline{\underline {m}}_p(Y,f,{\cal V}, \alpha):\;
\diam({\cal V}) < \epsilon , {\cal V} \text{ clopen partition of $X$}\}, \\
\overline{\underline {r}}_p(Y,f) &=& \sup \{\alpha>0:\;
\overline{\underline {M}}_p(Y,f,\alpha)=\infty \}.
\end{eqnarray*}
\end{dfn}
Clearly, the polynomial recurrence dimension and polynomial
entropies are topologicaly invariants. From now on we write
$r_p(X,f)$ whenever the same arguments apply for both
$\underline{r}_p(X,f)$ and $\overline{r}_p(X,f)$.
\begin{pro} \label{lower bound}
For every zero dimensional, minimal dynamical system $(X,f)$, $r_p(X,f) \geq 1$.
\end{pro}
\begin{proof}
There exists an ergodic measure $\mu$, which is positive on open sets.
By Lemma of Kac,
$$ \tau(U) \leq \int_U \tau_U(x) \frac{d\,\mu(x)}{\mu(U)} = \frac{1}{\mu(U)} $$
Here $\tau_U(x) = \min\{k>0:\; f^k(x) \in U\}$. For every clopen cover
$$ \sum_{U \in {\cal U}} \ \tau(U)^{-1} \geq \sum_{U \in {\cal U}} \mu(U)
\geq 1$$
so $m_p(X,f,{\cal U},1) >0$. Since the system is minimal, by Proposition
\ref{sharp}, the transition is sharp, thus $r_p(X,f,{\cal U}) \geq 1$.
\end{proof}
\begin{pro}
If $\clop$ is a generating clopen partition, then $r_p(X, f) = R_p(X, f, \clop)$.
\end{pro}
The proof is the same as for the exponential recurrence dimension case.
\begin{pro}
For every sub-shift $\Sigma \subseteq A^{\NN}$,
$r_p(\Sigma) \leq \overline{h}_p(\Sigma) + 1$
\end{pro}
\begin{proof} If $\overline{h}_p(\Sigma)+1 <\alpha$, pick some $\beta$ with
$\overline{h}_p(\Sigma) < \beta <\alpha -1$. There exists $k_0$,
such that for all $k\geq k_0$, $P(k) \leq e^{k\beta}$.
If $u \in {\cal L}^n(\Sigma)$ and $\tau[u] = k < n$, then
$u_{k+i} = u_i$ for all $i \in [0,|u|)$, so the number
of cylinders of length $n$ with the return time $k$ is at most the
number of cylinders of length $k$. For $\tau[u]=k\geq n$ we use
$e^{-\tau[u]} \leq e^{-n}$ to obtain
\begin{eqnarray*}
\sum_{u \in {\cal L}^n(\Sigma)} \tau[u]^{-\alpha} &\leq&
\sum_{k=1}^{n} P(k)\cdot k^{-\alpha} \leq
\sum_{k=1}^n k^{\beta-\alpha} \\
m_p(\Sigma,\alpha) &\leq&
\sum_{k=1}^{\infty} k^{\beta-\alpha} < \infty
\end{eqnarray*}
so $m_p(\Sigma,\alpha) < \infty$, and $r_p(\Sigma) \leq \alpha$.
\end{proof}
\begin{pro} \label{propolent}
Let $\Sigma \subseteq A^{\NN}$ be a sub-shift and $a,b>0$.
\begin{eqnarray*}
\forall n_0, \exists n\geq n_0, \forall u \in {\cal L}^n(\Sigma),
a|u| \leq \tau[u] &\Rightarrow& \underline r_p(\Sigma)
\leq \overline{h}_p(\Sigma) \\
\exists n_0, \forall n\geq n_0, \forall u \in {\cal L}^n(\Sigma),
a|u| \leq \tau[u] &\Rightarrow& \underline r_p(\Sigma)
\leq \underline{h}_p(\Sigma) \\
\exists n_0, \forall n\geq n_0, \forall u \in {\cal L}^n(\Sigma),
\tau[u] \leq b|u| &\Rightarrow& \underline{h}_p(\Sigma)
\leq \overline r_p(\Sigma)
\end{eqnarray*}
\end{pro}
\begin{proof}
1. Let $\overline{h}_p(\Sigma) < \beta < \alpha$ so for every $n \geq n_0$,
$P(n) < n^{\beta}$. There exists an infinite number of $n$ such that
$a|u| \leq \tau[u]$ whenever $|u|=n$. We get
$$ \sum_{u \in {\cal L}^n(\Sigma)} \tau[u]^{-\alpha} \leq P(n) (an)^{-\alpha}
\leq a^{-\alpha} \cdot n^{\beta-\alpha} \to 0 $$
Thus $\underline m_p(\Sigma,{\cal A},\alpha) = 0$, so $\underline r_p(\Sigma) \leq \alpha$ and
$\underline r_p(\Sigma) \leq \overline{h}_p(\Sigma)$.\\
2.Let $\underline{h}_p(\Sigma) < \beta < \alpha$ so there exists an
infinite number of $n$ for which $P(n) < n^{\beta}$,
and $a|u| \leq \tau[u]$ for all $u$ with $|u|=n$. We get again
$\underline m_p(\Sigma,{\cal A},\alpha) = 0$, so $\underline r_p(\Sigma) \leq \alpha$ and
$\underline r_p(\Sigma) \leq \underline{h}_p(\Sigma)$.\\
3. Let $\underline{h}_p(\Sigma) > \beta > \alpha$ so for every $n \geq n_0$,
$P(n) > n^{\beta}$ and
$$ \sum_{u \in {\cal L}^n(\Sigma)} \tau[u]^{-\alpha} \geq P(n) (bn)^{-\alpha}
\geq b^{-\alpha} \cdot n^{\beta-\alpha} \to \infty $$
Thus $\overline m_p(\Sigma,{\cal A},\alpha) = \infty$, so $\overline r_p(\Sigma) \geq \alpha$ and
$\overline r_p(\Sigma) \geq \underline{h}_p(\Sigma)$.
\end{proof}
\subsection{Sturmian sub-shifts}
A sturmian sub-shift is a coding of a one dimensional irrational rotation.
More precisely, let $R_\theta : \cir \rightarrow \cir$, such that
$R_\theta x = x + \theta \mod 1$, with $\theta$ irrational.
Let $\clop = \{ [0, 1-\theta), [1-\theta, 1) \} = \{ V_0, V_1 \}$
%, $S_\theta = \bigcap_{k\geq 0} \bigcup_{V \in \clop^k} V$,
and $\Omega_\theta = \{ \{x_i\}_{i\geq 0} \in \Sigma_2 :\;
\exists x \in [0,1) \text{ s.t. } \forall i\geq 0, R_\theta^i x \in V_{x_i}
\}$. Then the dynamical system $(\Omega_\theta, \sigma)$ is a sturmian
sub-shift.
\begin{exm}
For any sturmian sub-shift, upper and lower polynomial recurrence dimensions
are equal to 1.
\end{exm}
\begin{proof}
There is a conjugation $\phi$ between $S_\theta$ and $\Omega_\theta$ such that
any cylinder $[x_0 \ldots x_{n-1}] \xrightarrow{\phi} V\in\clop^n$. Thus,
$\tau([x_0 \ldots x_{n-1}]) = \tau(V)$. We will use the three distances theorem
and three gaps theorem (see for example \cite{AB} for an excellent review)
to compute the return times of cylinders in a sturmian sub-shift.
The three distance theorem states that the number and the length of intervals
in the dynamic partition $\clop^n$ are
\begin{itemize}
\item $n+1-q_k$ intervals of length $l_1 = \eta_k$,
\item $r+1$ intervals of length $l_2 = \eta_{k-1} - m\eta_k$,
\item $q_k - (r+1)$ intervals of length $l_3 = \eta_{k-1} - (m-1)\eta_k$,
\end{itemize}
where $\frac {p_k} {q_k}$ and $a_k$ are respectively the convergents and
quotients associated to $\theta$, $\eta_k = (-1)^k(q_k \theta - p_k)$, and
$k$, $m$ and $r$ is the unique solution of
\[ n = mq_k + q_{k-1} + r, \quad 1\leq m\leq a_{k+1}, \quad 0\leq r 1$ : we set $k'=k+1, m'=a_{k'+1}-1$, thus the return time
will be $t_1 = q_{k+1}$ again.
\end{itemize}
\item $\beta = l_2 = \eta_{k-1} - m\eta_k$ : there are three cases
\begin{itemize}
\item $m < a_{k+1}-1$ : we set $k'=k, m'=a_{k'+1}-m-1$, thus the return time
of the interval of length $l_2$ will be $t_1 = q_k$.
\item $m=a_{k+1}$ : we set $k'=k+2, m'=a_{k'+1}-1$, thus the return time
will be $t_1 = q_{k+2}$.
\item $m=a_{k+1}-1$ : we set $k'=k+1, m'=a_{k'+1}$, thus the return time
will be $t_2 = q_k$.
\end{itemize}
\item $\beta = l_3 = \eta_{k-1} - (m-1)\eta_k$ : there are two cases
\begin{itemize}
\item $m < a_{k+1}$ : we set $k'=k, m'=a_{k'+1}-m$, thus the return time
of the interval of length $l_3$ will be $t_1 = q_k$.
\item $m=a_{k+1}$ : we set $k'=k+1, m'=a_{k'+1}$, thus the return time
will be $t_2 = q_k$.
\end{itemize}
\end{itemize}
For a fixed $n$, either $m1$, then
there exists $v \in A_k^6$ and a phase $0 \leq m < 5^k$ such that
$u_i = \nu_1\ldots \nu_{k-1}(v)_{m+i}$. Since $5 \leq \tau[v] \leq 10$, we get
$5^k \leq \tau[u] \leq 2\cdot 5^k$. In general, if $5^{k-1} <|u| \leq
5^k$,
then
$$ \frac{|u|}{5} \leq 5^{k-1} \leq \tau[u] \leq 2\cdot 5^k \leq 10|u| $$
We estimate now the complexity of $\Sigma$. If $|u| = 5^{k-1}$, then $u$
is a sub-word of $\nu_1\ldots \nu_{k-1}(ab)$ for some $a,b \in A_k$ and
either $a=0$ or $b=0$. Thus we have at most $2n_k$ possibilities for $ab$
and $5^{k-1}$ possibilities for the phase. On the other hand there are at
least $n_k$ different words of the form $\nu_1\ldots n_{k-1}(a)$, and at least
$2\cdot 5^{k-2}$ different phases for them, in which the distinguishing
part $b0c$ of $\nu_1(a) = 00b0c$ occurs. Thus we get
$$ 2 \cdot 5^{k-2} \cdot n_k \leq P(5^{k-1}) \leq 2 \cdot 5^{k-1} \cdot n_k $$
In general, if $5^{k-1} \leq m < 5^k$, then
$$ 2 \cdot 5^{k-2} \cdot n_k \leq P(m) \leq 2 \cdot 5^{k} \cdot n_{k+1} $$
To construct a sub-shift with polynomial entropies $\alpha = 1$,
put $n_k = 3$ for all $k$ and get
$$ \underline h_p(\Sigma) = r_p(\Sigma) = \overline h_p(\Sigma) = 1$$
Let $\alpha >1$, and let $k_0$ be the first integer with $5^{k_0(\alpha-1)}
\geq 3$. For $k \geq k_0$ define $n_k$ by
$$ 5^{k(\alpha-1)} \leq n_k < 5^{k(\alpha-1)} + 1. $$
Using the sequence $(n_k)_{k\geq k_0}$ we construct a sub-shift in
alphabet $A = A_{k_0} = \{0,\ldots,n_{k_0}-1\}$. We verify easily
$n_k \leq n_{k+1} \leq (n_k-1)^2$.
If $5^{k-1} < m \leq 5^k$, then
$$ \frac{\ln (2\cdot 5^{k-2 + k(\alpha-1)}+1)}{k\ln 5} \leq
\frac{\ln P(m)}{\ln m} \leq
\frac{\ln (2 \cdot 5^{k+(k+1)(\alpha-1)}+1)}{(k-1)\ln 5} $$
Both sides of this inequality tend to $\alpha$ as $k \to \infty$, so
$\underline h_p(\Sigma) = \overline h_p(\Sigma) = \alpha$. By Proposition \ref{propolent},
$\overline r_p(\Sigma) = \underline r_p(\Sigma) = \alpha$.
\end{proof}
\begin{exm}
For every $\alpha>2$ there exists a Toeplitz sub-shift with
$$ \underline r_p(\Sigma) \leq \underline h_p(\Sigma) = \alpha,\;
\overline h_p(\Sigma) = \alpha + 1.$$
\end{exm}
\begin{proof}
We use the construction of the preceding example, but we do no more
require $n_k \leq n_{k+1}$, so not all words $00a0a$ may be present.
We loose the upper estimate for $\tau[u]$, but we still have
$\tau[u] \geq |u|$. Thus we put (for large enough $k$)
$$ n_{2k} = \lceil 5^{2k(\alpha-1)} \rceil,\;
n_{2k+1} = \lceil 5^{(2k+1)\alpha} \rceil $$
and we get $\underline h_p(\Sigma) = \alpha$, $\overline h_p(\Sigma) = \alpha +1$, and
$\underline r_p(\Sigma) \leq \underline h_p(\Sigma)$.
\end{proof}
\begin{thebibliography}{99}
\bibitem{afr1} V. Afraimovich, \emph{Pesin's dimension for Poincar\'e
recurrence}, Chaos {\bf 7} (1997)
\bibitem{afr2} V. Afraimovich, private communication
\bibitem{AB} P. Alessandri, V.Berth\'e, \emph{Three distance theorems and
combinatorics of words}, L'enseignement Math\'ematique, {\bf 44}, 1998, 103-132.
\bibitem{Bruin} H.Bruin, \emph{Dimensions of recurrence times and minimal
sub-shifts}, proceeding of the conference ``Dynamical Systems~:
From crystal to Chaos'',
J.-M. Gambaudo, P. Hubert, S. Vaienti eds, to be published in
World Scientific.
\bibitem{Denker} M.Denker, Ch.Grillenberger, K.Sigmund: Ergodic Theory on
Compact Spaces. Lecture Notes in Mathematics vol. 527, Springer, Berlin 1976.
\bibitem{Herman} H.Herman, I.F.Putnam, Ch.F.Skau, \emph{Ordered Bratelli
diagrams}, dimensions groups and topological dynamics, manuscript.
\bibitem{Kurka} P.K\accent23urka, A.Maass, \emph{Recurrence dimension in
Toeplitz sub-shifts}, proceeding of the conference ``Dynamical Systems~:
From crystal to Chaos'',
J.-M. Gambaudo, P. Hubert, S. Vaienti eds, to be published in
World Scientific.
\bibitem{Lind} D.Lind, B.Marcus: An Introduction to Symbolic
Dynamics and Coding, Cambridge University Press, Cambridge 1995.
\bibitem{Penne} V.Penn\'e, B.Saussol, S.Vaienti: \emph{Dimensions for
recurrence times: topological and dynamical properties},
Discrete and Continuous Dynamical Systems, vol. 4, no. 4, 1998.
\bibitem{Pesin} Y.B.Pesin, Dimension Theory in Dynamical Systems,
The University of Chicago Press, Chicago 1997.
\bibitem{Wiliams} S.Williams, \emph{Toeplitz minimal flows which are not
uniquely ergodic,} Z. Wahrschainlichkeitstheorie verw. Gebiete
67, 95-107 (1984)
\end{thebibliography}
\end{document}