Outdated Archival Version

These pages are not updated anymore. They reflect the state of 20 August 2005. For the current production of this journal, please refer to http://www.math.psu.edu/era/.

%_ **************************************************************************
%_ * The TeX source for AMS journal articles is the publishers TeX code     *
%_ * which may contain special commands defined for the AMS production      *
%_ * environment.  Therefore, it may not be possible to process these files *
%_ * through TeX without errors.  To display a typeset version of a journal *
%_ * article easily, we suggest that you retrieve the article in DVI,       *
%_ * PostScript, or PDF format.                                             *
%_ **************************************************************************
% Author Package file for use with AMS-LaTeX 1.2
\controldates{16-APR-2001,16-APR-2001,16-APR-2001,16-APR-2001}
 
\documentclass{era-l}
\usepackage{mspm}

\issueinfo{7}{04}{}{2001}
\dateposted{April 18, 2001}
\pagespan{17}{27}
\PII{S 1079-6762(01)00090-7}
\copyrightinfo{2001}{American Mathematical Society}
\copyrightinfo{2001}{American Mathematical Society}


\theoremstyle{plain}
\newtheorem{Thm}{Theorem}[section]
\newtheorem{Prop}{Proposition}[section]
\newtheorem*{maint}{Main Theorem}
\newtheorem*{maindt}{Main $1$-dimensional Theorem}

\theoremstyle{remark}
\newtheorem{Rm}{Remark}[section]

\theoremstyle{definition}
\newtheorem{Def}{Definition}[section]
\newtheorem{Q}{Question}
\newtheorem{Prob}{Problem}

\newcommand{\bprop}{\begin{Prop}}
\newcommand{\eprop}{\end{Prop}}
\newcommand{\bthm}{\begin{Thm}}
\newcommand{\ethm}{\end{Thm}}
\newcommand{\brm}{\begin{Rm}}
\newcommand{\erm}{\end{Rm}}
\newcommand{\R}{\mathbb R}
\newcommand{\Z}{\mathbb Z}
\newcommand{\dt}{\delta}
\newcommand{\al}{\alpha}
\newcommand{\myr}{\mathbf r}
\newcommand{\gm}{\gamma}
\newcommand{\gmncdt}{\gm_n(C,\dt)}
\newcommand{\lb}{\lambda}
\newcommand{\myeps}{\varepsilon}
\newcommand{\inv}{^{-1}}
\newcommand{\veps}{{\vec \myeps}}


\begin{document}

\title[Periodic points I]{A stretched exponential bound on the rate of growth
of the number of periodic points for prevalent diffeomorphisms I}

\author{Vadim Yu. Kaloshin}

\address{Fine Hall, Princeton University,
Princeton, NJ 08544}
\email{kaloshin@math.princeton.edu}

\author{Brian R. Hunt}
\address{Department of Mathematics and Institute for
Physical Science and Technology, University of Maryland,
College Park, MD 20742}
\email{bhunt@ipst.umd.edu}

\commby{Svetlana Katok}

\date{December 21, 2000}

\subjclass[2000]{Primary 37C20, 37C27, 37C35, 34C25, 34C27}

\keywords{Periodic points, prevalence, diffeomorphisms}

\begin{abstract}
For diffeomorphisms of smooth compact manifolds, we consider the
problem of how fast the number of periodic points with period $n$
grows as a function of $n$.  In many familiar cases (e.g.,
Anosov systems) the growth is exponential, but arbitrarily fast growth
is possible; in fact, the first author has shown that arbitrarily fast
growth is topologically (Baire) generic for $C^2$ or smoother
diffeomorphisms.  In the present work we show that, by contrast, for a
measure-theoretic notion of genericity we call ``prevalence'', the
growth is not much faster than exponential.  Specifically, we
show that for each $\delta > 0$, there is a prevalent set of
({$C^{1+\rho}$} or smoother) diffeomorphisms for which the number of
period $n$ points is bounded above by
$\operatorname{exp}(C n^{1+\delta})$ for some
$C$ independent of $n$.  We also obtain a related bound on the decay
of the hyperbolicity of the periodic points as a function of $n$.
The contrast between topologically generic and measure-theoretically
generic behavior for the growth of the number of periodic points and
the decay of their hyperbolicity shows this to be a subtle and complex
phenomenon, reminiscent of KAM theory.
\end{abstract}
\maketitle

\section{Introduction}

Let $\textup{Diff}^{\,r}(M)$ be the space of $C^r$ diffeomorphisms  of
a finite-dimensional smooth compact manifold $M$ with the uniform
$C^r$-topology, where $\dim M \geq 2,$ and let $f \in
\textup{Diff}^{\,r}(M)$.  Consider the number of periodic points of
period $n$,
\begin{equation} \label{grow}
P_n(f)=\# \{x \in M :   x=f^n(x)\}.
\end{equation}
The main question of this paper is:
\begin{Q}
How quickly can $P_n(f)$ grow with $n$ for a ``generic'' $C^r$
diffeomorphism $f$?
\end{Q}

We put the word ``generic'' in quotes because, as the
reader will see, the answer depends on the notion of genericity.

For technical reasons one sometimes counts only {\em isolated\/}
points of period $n$; let
\begin{multline}
P^i_n(f)=\# \{x \in M:\ x=f^n(x) \textup{ and } y \neq f^n(y)\\
\textup{ for } y \neq x \textup{ in some neighborhood of } x\}.
\end{multline}

We call a diffeomorphism $f \in \textup{Diff}^{\,r}(M)$ an
{\em Artin-Mazur diffeomorphism\/} (or simply {\em A-M diffeomorphism\/})
if the number of isolated periodic orbits of $f$ grows   at most
exponentially fast, i.e., for some number $C>0$,
\begin{equation}
P^i_n(f) \leq \exp(Cn) \quad {\textup{for all }} n \in \mathbb Z_+.
\end{equation}
Artin and Mazur {\cite{AM}} proved the following result.
\bthm
For $0\leq r\leq \infty$, A-M diffeomorphisms are dense
in $\textup{Diff}^{\,r}(M)$ with the uniform $C^r$-topology.
\ethm

We say that a point $x \in M$ of period $n$ for $f$ is hyperbolic if
$df^n(x)$, the derivative of $f^n$ at $x$, has no eigenvalues with
modulus $1$.  (Notice that a hyperbolic solution to $f^n(x) = x$ must
also be isolated.)  We call $f \in \textup{Diff}^{\,r}(M)$ a strongly
Artin-Mazur diffeomorphism if for some number $C > 0$,
\begin{equation}
P_n(f) \leq \exp(Cn) \quad {\textup{for all }} n \in \mathbb Z_+,
\end{equation}
and all periodic points of $f$ are hyperbolic (whence $P_n(f) =
P^i_n(f)$).  In {\cite{K1}} an elementary proof of the following
extension of the Artin-Mazur result is given.
\bthm
For $0\leq r<\infty$, strongly A-M diffeomorphisms are dense in
$\textup{Diff}^{\,r}(M)$ with the uniform $C^r$-topology.
\ethm

According to the standard terminology, a set in $\textup{Diff}^{\,r}(M)$ is
called residual if it contains a countable intersection of open
dense sets, and a property is called (Baire) generic if
diffeomorphisms with that property form a residual set.
It turns out the A-M property is not generic, as is shown
in {\cite{K2}}. Moreover:

\bthm [\cite{K2}] \label{supergrowth} For any $2\leq r <\infty$
there is an open set $\mathcal{N} \subset \textup{Diff}^{\,r}(M)$ such that for
any given sequence $a=\{a_n\}_{n \in \mathbb Z_+}$ there is a Baire
generic set $\mathcal{R}_a$ in $\mathcal{N}$ depending on the sequence $a_n$
with the property that if $f \in \mathcal{R}_a$, then for infinitely many
$n_k \in \mathbb Z_+$ we have $P^i_{n_k}(f)>a_{n_k}$.
\ethm

Of course, since $P_n(f) \geq P^i_n(f)$, the same statement can be made
about $P_n(f)$.  But in fact it is shown in \cite{K2} that $P_n(f)$ is
infinite for $n$ sufficiently large, due to a continuum of periodic
points, for at least a dense set of $f \in \mathcal{N}$.

The proof of this theorem is based on a result of
Gonchenko-Shilnikov-Turaev \cite{GST1}. Two slightly
different detailed proofs of their result are given
in {\cite{K2}} and {\cite{GST2}}. The proof in {\cite{K2}}
relies on a strategy outlined in \cite{GST1}.

However, it seems unnatural that if you pick a diffeomorphism
at random then it may have an arbitrarily fast growth of the
number of periodic points. Moreover, Baire generic sets in
Euclidean spaces can have zero Lebesgue measure. Phenomena
that are Baire generic, but have a small probability are
well known in dynamical systems, KAM theory, number theory,
etc.\ (see {\cite{O}}, {\cite{HSY}}, {\cite{K3}} for various
examples). This partially motivates the problem posed by
Arnold {\cite{A}}:
\begin{Prob}
Prove that ``with probability one'' $f \in \textup{Diff}^{\,r}(M)$ is an
A-M diffeomorphism.
\end{Prob}

Arnold suggested the following interpretation of ``with probability
one'': {\em for a (Baire) generic finite parameter family of
diffeomorphisms $\{f_{\myeps}\}$, for Lebesgue almost every ${\myeps}$ we have
that $f_{\myeps}$ is A-M\/} ({\it cf.\/} \cite{K3}).  As Theorem 1.3 shows,
a result on the genericity of the set of A-M diffeomorphisms based on
(Baire) topology is likely to be extremely subtle, if possible at
all.\footnote{ For example, using techniques from \cite{GST2} and
\cite{K2} one can prove that for a Baire generic finite-parameter
family $\{f_{\myeps}\}$ and a Baire generic parameter value ${\myeps}$
the corresponding diffeomorphism $f_{\myeps}$ is not A-M. Unfortunately,
how to estimate from below the measure of non-A-M diffeomorphisms
in a Baire generic finite-parameter family is
so far an unreachable question.} We use instead
a notion of ``probability one'' based on prevalence \cite{HSY,K3},
which is independent of Baire genericity.  We also are able to state
the result in the form Arnold suggested for generic families using this
measure-theoretic notion of genericity.

For a rough understanding of prevalence, consider a Borel measure
$\mu$ on a Banach space $V$.  We say that a property holds
``$\mu$-almost surely for perturbations'' if it holds on a Borel set
$P \subset V$ such that {\it for all $v \in V$ we have $v + w \in P$
for almost every $w$ with respect to $\mu$}.\footnote{A similar notion
of prevalence is used in \cite{VK}.}  Notice that if $V = \mathbb
R^k$ and $\mu$ is Lebesgue measure, then ``$\mu$-almost surely for
perturbations'' is equivalent to ``Lebesgue almost
everywhere''.  Moreover, the Fubini-Tonelli Theorem implies that if
$\mu$ is any Borel probability measure on $\mathbb R^k$, then a
property that holds $\mu$-almost surely for perturbations
must also hold Lebesgue almost everywhere.  Based on this
observation, we call a property on a Banach space ``prevalent'' if it
holds $\mu$-almost surely for perturbations for some
Borel probability measure $\mu$ on $V$, which for technical reasons
(cf. \cite{HSY}) we
require to have compact support.  In order to apply this notion to the
Banach manifold $\textup{Diff}^{\,r}(M)$, we must describe how we make
perturbations in this space, which we will do in the next section.

Our first main result is a partial solution to
Arnold's problem. It says that {\em for a prevalent diffeomorphism
$f\in$ \textup{Diff}$^r(M)$, with $1 < r \leq \infty$, and all $\dt>0$
there exists $C=C(\dt)>0$ such that for all $n \in \Z_+$,\/}
\begin{equation} \label{growthbound}
P_n(f) \leq \exp(Cn^{1+\dt}).
\end{equation}

The Kupka-Smale theorem (see e.g. {\cite{PM}}) states that for
a generic diffeomorphism all periodic points are hyperbolic and
all associated stable and unstable manifolds intersect one another
transversally.  The paper {\cite {K3}} shows that the Kupka-Smale theorem
also holds on a prevalent set.
So, the Kupka-Smale theorem, in particular, says that a Baire generic
(resp.\ prevalent) diffeomorphism has only hyperbolic periodic points,
but {\em how hyperbolic are the periodic points, as functions of their
period, for a Baire generic (resp.\ prevalent) diffeomorphism $f$?\/}
This is the second main problem we deal with in this paper.

Recall that a linear operator $L:\R^N \to \R^N$ is
{\em hyperbolic\/} if it has no eigenvalues on the unit circle
$\{|z|=1\}\subset \mathbb C$. Denote by $|\cdot|$ the Euclidean
norm in $\mathbb C^N$. Then we define the {\em hyperbolicity\/} of
a linear operator $L$ by
\begin{equation} \label{hyp-lin}
\gm(L)=\inf_{\phi \in [0,1)}\inf_{|v|=1}|Lv - \exp(2\pi i \phi) v|.
\end{equation}
We also say that $L$ is $\gm$-hyperbolic if $\gm(L)\geq\gm$.
In particular, if $L$ is $\gm$-hyperbolic, then its eigenvalues
$\{\lb_j\}_{j=1}^N\subset \mathbb C$ are at least $\gm$-distant
from the unit circle, i.e., $\min_j ||\lb_j|-1|\geq \gm$.
The {\em hyperbolicity\/} of a periodic point $x=f^n(x)$ of period
$n$, denoted by $\gm_n(x,f)$, equals the hyperbolicity of
the derivative $df^n(x)$ of $f^n$ at points $x$, i.e.,
$\gm_n(x,f)=\gm(df^n(x))$. Similarly to the number of periodic
points $P_n(f)$ of period $n$, define
\begin{equation} \label{hyp-map}
\gm_n(f)=\min_{\{x: x=f^n(x)\}}\gm_n(x,f).
\end{equation}

The idea of Gromov {\cite{G}} and Yomdin {\cite{Y}} for measuring
hyperbolicity is that a $\gm$-hyperbolic point of period $n$ of a
$C^2$ diffeomorphism $f$ has an $M_2^{-2n}\gm$-neighborhood (where
$M_2 = \|f\|_{C^2}$) free from periodic points of the same
period.\footnote{In {\cite{Y}} hyperbolicity is introduced as the
minimal distance of eigenvalues to the unit circle. This way of
defining hyperbolicity does not guarantee the existence of a
$M_2^{-2n}\gm$-neighborhood free from periodic points of the same
period \cite{KH}.} One can prove the following slightly more
general result.

\bprop \label{per-hyp} Let $M$ be a compact manifold of dimension $N$,
let $f:M \to M$ be a $C^{1+\rho}$ diffeomorphism (where $0 < \rho
\leq 1$) that has only hyperbolic periodic points, and let
$M_{1+\rho} = \max(\|f\|_{C^{1+\rho}}, 2^{1/\rho})$.  Then there is
a constant $C=C(M)>0$ such that for each $n\in \Z_+$ we have
\begin{equation}
P_n(f)\leq C\left(M_{1+\rho}\right)^{nN(1 +
\rho)/\rho}\gm_n(f)^{-N/\rho}.
\end{equation}
\eprop

Proposition \ref{per-hyp} implies that a lower estimate on
the decay of hyperbolicity $\gm_n(f)$ gives an upper estimate
on the growth of the number of periodic points $P_n(f)$.  Therefore, a natural
question is:
\begin{Q}
How quickly can $\gm_n(f)$ decay with $n$ for a ``generic'' $C^r$
diffeomorphism $f$?
\end{Q}
The existence of a lower bound on the rate of decay of $\gm_n(f)$ for
Baire generic $f \in \textup{Diff}^{\,r}(M)$ would imply
the existence of an upper bound on the rate of growth of the number
of periodic points $P_n(f)$, whereas no such bound exists by
Theorem \ref{supergrowth}. Thus again we consider genericity in
the measure-theoretic sense of prevalence.  Our second main result,
which in view of Proposition \ref{per-hyp} implies the first main
result, is that {\em for a prevalent diffeomorphism
$f\in$ \textup{Diff}$^r(M)$, with $1 < r \leq \infty$, and all
$\dt>0$ there exists $C=C(\dt)>0$ such that\/}
\begin{equation} \label{hyperbolicitydecay}
\gm_n(f) \geq \exp(-Cn^{1+\dt}).
\end{equation}

Now we shall discuss in more detail our definition of prevalence
(``probability one'') in the space of diffeomorphisms
$\textup{Diff}^{\,r}(M)$.

\section{Prevalence in the space of diffeomorphisms
$\textup{Diff}^{\,r}(M)$}\label{prevalence}

The space of $C^r$ diffeomorphisms $\textup{Diff}^{\,r}(M)$
of a compact manifold $M$ is a Banach manifold.  Locally we can
identify it with a Banach space, which gives it a local linear
structure in the sense that we can perturb a diffeomorphism by
``adding'' small elements of the Banach space.  As we described in
the previous section, the notion of prevalence requires 
additive perturbations with respect to a probability measure that
is independent of the place that the perturbation is performed.  Thus
although there is not a unique way to put a linear structure on
$\textup{Diff}^{\,r}(M)$, it is important to make a choice that is
consistent throughout the Banach manifold.

The way we make perturbations on $\textup{Diff}^{\,r}(M)$ by small
elements of a Banach space is as follows.  First we embed $M$ into
the interior of the closed unit ball $B^N \subset \R^N$, which we
can do for $N$ sufficiently large by the Whitney Embedding Theorem
\cite{W}. We emphasize that our results hold for {\it{every}} possible
choice of an embedding of $M$ into $\R^N$.  We then consider a closed
tubular neighborhood $U \subset B^N$ of $M$ and the Banach space $C^r(U,\R^N)$
of $C^r$ functions from $U$ to $\R^N$.  Next, we extend every element
$f \in \textup{Diff}^{\,r}(M)$ to an element $F \in C^r(U,\R^N)$ that is
strongly contracting in the directions transverse to $M$.  Again the
particular choice of how we make this extension is {\it{not}} important
to our results; in the Appendix we describe one way to make this
extension so that the results of Sacker \cite{Sac} and Fenichel
\cite{F} apply as follows.  Since $F$ has $M$ as an invariant
manifold, if we add to $F$ a small perturbation in $g \in
C^r(U,\R^N)$, the perturbed map $F + g$ has an invariant manifold
in $U$ that is close to $M$.  Then $F + g$ restricted to its
invariant manifold corresponds in a natural way to an element of
$\textup{Diff}^{\,r}(M)$, which we consider to be the perturbation of $f
\in \textup{Diff}^{\,r}(M)$ by $g \in C^r(U,\R^N)$.  The details of this
construction are described in the Appendix.

In this way we reduce the problem to the study of maps in
$\textup{Diff}^{\,r}(U)$, the open subset of $C^r(U,\R^N)$ consisting
of those elements that are diffeomorphisms from $U$ to some subset
of its interior.  The construction we described in the previous
paragraph ensures that the number of periodic points $P_n(f)$ and
their hyperbolicity $\gamma_n(f)$ for elements of $\textup{Diff}^{\,r}(M)$
are the same for the corresponding elements of $\textup{Diff}^{\,r}(U)$,
so the bounds that we prove on these quantities for almost every
perturbation of any element of $\textup{Diff}^{\,r}(U)$ hold as well for
almost every perturbation of any element of $\textup{Diff}^{\,r}(M)$.
Another justification for considering diffeomorphisms in Euclidean
space is that the problem of exponential/superexponential growth of
the number of periodic points $P_n(f)$ for a prevalent
$f \in \textup{Diff}^{\,r}(M)$ is a {\em local problem\/} on $M$ and
is not affected by a global shape of $M$.

The results stated in the next section apply to any compact domain
$U \subset \R^N$, but for simplicity we state them for the closed unit
ball $B^N$.  In the previous section, we said that a property is
{\em prevalent\/} on a Banach space such as $C^r(B^N,\R^N)$ if
it holds on a Borel subset $S$ for which there exists a Borel
probability measure $\mu$ on $C^r(B^N,\R^N)$ with compact support
such that for all $F \in C^r(B^N,\R^N)$ we have $F + g \in S$ for
almost every $g$ with respect to $\mu$.  The complement of
a prevalent set is said to be {\em shy\/}. We then say that
a property is prevalent on an open subset of $C^r(B^N,\R^N)$ such as
$\textup{Diff}^{\,r}(B^N)$ if the exceptions to the property in
$\textup{Diff}^{\,r}(B^N)$ form a shy subset of $C^r(B^N,\R^N)$.

In this paper the perturbation measure $\mu$ that we use is supported
within the analytic functions in $C^r(B^N,\R^N)$.  In this sense
we foliate $\textup{Diff}^{\,r}(B^N)$ by analytic leaves that are compact
and overlapping.  The main result then says that {\em for every
analytic leaf $L \subset \textup{Diff}^{\,r}(B^N)$ and every $\dt>0$,
for almost every diffeomorphism $f \in L$ in the leaf $L$ both
\eqref{growthbound} and \eqref{hyperbolicitydecay} are satisfied.\/}
Now we define an analytic leaf as a ``Hilbert brick'' in the space of
analytic functions, and a natural product Lebesgue probability measure
$\mu$ on it.

\section{Formulation of main results}\label{mainres}

Fix a coordinate system $x=(x_1,\dots,x_N) \in \R^N \supset B^N$ and
the scalar product $\langle x,y \rangle = \sum_i x_i y_i$.  Let
$\alpha=(\alpha_1,\dots,\alpha_N)$ be a multiindex from $\Z_+^N$, and
let $|\alpha|=\sum_i \alpha_i$.  For a point $x=(x_1,\dots,x_N) \in
\R^N$ we write $x^\alpha=\prod_{i=1}^N x_i^{\alpha_i}$.  Associate to
a real analytic function $\phi:B^N \to \R^N$ the set of coefficients
of its expansion:
\begin{equation} \label{expan}
\phi_{\veps}(x)=\sum_{\alpha \in \Z_+^N}
\veps_\alpha x^\alpha.
\end{equation}
Denote by $W_{k,N}$ the space of $N$-component homogeneous
vector-polynomials of degree $k$ in $N$ variables, and by
$\nu(k,N)=\dim W_{k,N}$ the dimension of $W_{k,N}$. According
to the notation of the expansion (\ref{expan}),
denote coordinates in $W_{k,N}$ by
\begin{equation} \label{homogcoord}
\veps_k=
\left(\{\veps_{\alpha}\}_{|\alpha|=k}\right)\in W_{k,N}.
\end{equation}
In $W_{k,N}$ we use a scalar product that is invariant with respect to the
orthogonal transformation of $\R^N \supset B^N$ defined as follows:
\begin{equation} \label{scalprod}
\langle \veps_k,\vec \zeta_k \rangle_k=
\sum_{|\al|=k} \binom{k}{\al}^{-1} \langle\veps_{\al},\vec
\zeta_{\al}\rangle, \quad \|\veps_k\|_k=
\bigl(\langle \veps_k,\veps_k \rangle_k \bigr)^{1/2}.
\end{equation}
Denote by
\begin{equation} \label{ball}
B^N_k(r)=\left\{\veps_k \in W_{k,N}:  \|\veps_k\|_k \leq
r\right\}
\end{equation}
the closed $r$-ball in $W_{k,N}$ centered at the origin.  Let
$Leb_{k,N}$ be Lebesgue measure on $W_{k,N}$ induced by the scalar
product (\ref{scalprod}) and normalized by a constant so that the
volume of the unit ball is one: $Leb_{k,N}(B^N_k(1))=1$.

Fix a nonincreasing sequence of positive numbers
$\myr=\left(\{r_k\}_{k=0}^\infty\right)$ such that $r_k \to 0$ as
$k\to \infty$ and define a Hilbert brick of size $\myr$,
\begin{eqnarray}
\label{Brick}
\begin{aligned}
HB^N(\myr) & =
\{\veps=\{\veps_{\alpha}\}_{\alpha \in \mathbb Z_+^N}: 
\textup{for all}\ k \in  \mathbb Z_+, \|\veps_k\|_k\leq r_k\}
\\
& = B^N_0(r_0) \times B^N_1(r_1) \times \dots \times B^N_k(r_k)
\times \cdots \\
& \subset  W_{0,N} \times W_{1,N} \times \dots
\times W_{k,N} \times \cdots .
\end{aligned} \end{eqnarray}
Define {\em a product Lebesgue probability measure $\mu^N_{\myr}$ associated to the
Hilbert brick $HB^N(\myr)$ of size $\myr$\/} by normalizing for each
$k \in \Z_+$ the corresponding Lebesgue measure $Leb_{k,N}$ on
$W_{k,N}$ to the Lebesgue probability measure on the $r_k$-ball
$B^N_k(r_k)$: \begin{eqnarray} \label{measure}
\begin{aligned}
\mu_{k,r}^N= r^{-\nu(k,N)} Leb_{k,N}\quad
\textup{and} \quad
\mu^N_{\myr}=\bigtimes_{k=0}^\infty \mu_{k,r_k}^N.
\end{aligned}
\end{eqnarray}

\begin{Def} \label{admissible}
Let $f \in \textup{Diff}^{\,r}(B^N)$ be a $C^r$
diffeomorphism of $B^N$ into its interior. We call
$HB^N(\myr)$ a Hilbert brick of an admissible size
$\myr = \left(\{r_k\}_{k=0}^\infty\right)$ with respect to $f$
if:
\begin{itemize}
\item[A)] for each $\veps \in HB^N(\myr)$, the corresponding
function $\phi_\veps(x)=\sum_{\al \in \Z_+^N} \veps_\al x^\al$
is analytic on $B^N$;
\item[B)] for each $\veps \in HB^N(\myr)$, the corresponding
map $f_\veps(x)=f(x)+\phi_\veps(x)$ is a diffeomorphism
from $B^N$ into its interior, i.e.,
$\{f_{\veps}\}_{\veps \in HB^N(\myr)} \subset
\textup{Diff}^{\,r}(B^N)$;
\item[C)] for all $\dt>0$ and all $C>0$, the sequence
$r_k \exp(C k^{1+\dt})\to \infty$ as $k \to \infty$.
\end{itemize}
\end{Def}

\brm The first and second conditions ensure that the family
$\{f_{\veps}\}_{\veps \in HB^N(\myr)}$ lie in an analytic leaf within
the class of diffeomorphisms $\textup{Diff}^{\,r}(B^N)$. The third
condition provides us enough freedom to perturb. It is important for
our method to have infinitely many parameters to perturb. If the $r_k$
decayed too fast to zero, it would make our family of
perturbations essentially finite-dimensional.
\erm

An example of an admissible sequence $\myr =
(\{r_k\}_{k=0}^\infty)$ is $r_k = \tau/k!$, where $\tau$ depends on
$f$ and is chosen sufficiently small to ensure that condition (B)
holds. Notice that the diameter of $HB^N(\myr)$ is then
proportional to $\tau$, so that $\tau$ can be chosen as some
multiple of the distance from $f$ to the boundary of
$\textup{Diff}^{\,r}(B^N)$.



\begin{maint}%Main Theorem.} {\em
For each $0 < \rho \leq \infty$ and every 
$C^{1+\rho}$ diffeomorphism $f \in \break\textup{Diff}^{1+\rho}(B^N)$,
consider a Hilbert brick $HB^N(\myr)$ of an admissible size $\myr$
with respect to $f$ and the family of analytic perturbations of $f$,
\begin{equation} \label{anptb}
\{f_\veps(x)=f(x)+\phi_\veps(x)\}_{\veps \in HB^N(\myr)},
\end{equation}
with the product Lebesgue probability measure $\mu^N_{\myr}$
associated to $HB^N(\myr)$. Then for every $\dt>0$ and
for $\mu^N_{\myr}$-a.e.\ $\veps$ there is $C=C(\veps,\dt)>0$
such that for all $n \in \Z_+$
\begin{equation} \label{growth}
\begin{aligned}
\gm_n(f_\veps) > \exp(-Cn^{1+\dt}), \qquad
P_n(f_\veps) < \exp(Cn^{1+\dt}).
\end{aligned}
\end{equation}
\end{maint} %}
\brm
The fact that the measure $\mu^N_{\myr}$ depends on $f$ does not
conform to our definition of prevalence.  However, we can decompose
$\textup{Diff}^{\,r}(B^N)$ into a nested countable union of sets  $\mathcal{
S}_j$ that are each a positive distance from the boundary of
$\textup{Diff}^{\,r}(B^N)$ and for each $j \in \Z^+$ choose an admissible
sequence ${\myr}_j$ that is valid for all $f \in \mathcal{S}_j$.  Since
a countable intersection of prevalent subsets of a Banach space is
prevalent \cite{HSY}, the Main Theorem implies the results stated in
terms of prevalence in the Introduction.
\erm

In the Appendix we deduce from the Main Theorem the following result.
\bthm \label{genparam} Let
$\{f_{\myeps}\}_{{\myeps} \in B^m}\subset \textup{Diff}^{1+\rho}(M)$
be a generic $m$-parameter family of $C^{1+\rho}$ diffeomorphisms
of a compact manifold $M$ for some $\rho>0$.
Then for every $\dt>0$ and a.e.\ ${\myeps}\in B^m$ there is a constant
$C=C({\myeps},\dt)$ such that \eqref{growth} is satisfied for
every $n\in \Z_+$.
\ethm

In the Appendix we also give a precise meaning to the term
{\em generic\/}.

Let us formulate the most general result we shall prove.
\begin{Def} Let $\gm\geq 0$ and
$f \in \textup{Diff}^{1+\rho}(B^N)$ be a $C^{1+\rho}$
diffeomorphism for some $\rho>0$. A point $x \in B^N$
is called $(n,\gm)$-periodic if $\|f^n(x)-x\|\leq \gm$,
and $(n,\gm)$-hyperbolic if $\gm_n(x,f)=\gm(df^n(x))\geq \gm$.
\end{Def}

(Notice that a point can be $(n,\gm)$-hyperbolic regardless of its
periodicity, but this property is of interest primarily for
$(n,\gm)$-periodic points.)  For positive $C$ and $\dt$ let
$\gmncdt=\exp(-C n^{1+\dt})$.
\bthm \label{main}  Given the hypotheses of the Main Theorem,
for every $\dt>0$ and for $\mu^N_{\myr}$-a.e.\ $\veps$ there is
$C=C(\veps,\dt)>0$ such that for all $n \in \Z_+$, every
$(n,\gm^{1/\rho}_n(C,\dt))$-periodic point $x \in B^N$ is
$(n,\gmncdt)$-hyperbolic.  (Here we assume $0 < \rho \leq 1$; in a
space $\textup{Diff}^{1+\rho}(B^N)$ with $\rho > 1$, the statement
holds with $\rho$ replaced by $1$.)
\ethm

This result together with Proposition \ref{per-hyp}
implies the Main Theorem,
because every periodic point of period $n$ is $(n,\gm)$-periodic
for all $\gm>0$.
\brm \label{domain}
In the statement of the Main Theorem and Theorem \ref{main}
the unit ball $B^N$ can be replaced by a bounded open set
$U \subset \R^N$.  After scaling, $U$ can be regarded as
a subset of the unit ball $B^N$.
\erm

One can define a distance on a compact manifold $M$ and almost
periodic points of diffeomorphisms of $M$. Then one
can cover $M=\bigcup_i U_i$ by coordinate charts and define
hyperbolicity for almost periodic points using these charts
$\{U_i\}_i$ (see {\cite{Y}} for details). This gives
a precise meaning to the following result.
\bthm Let
$\{f_{\myeps}\}_{{\myeps} \in B^m}\subset \textup{Diff}^{1+\rho}(M)$
be a generic $m$-parameter family of diffeomorphisms
of a compact manifold $M$ for some $\rho>0$.  Then for every $\dt>0$
and almost every ${\myeps}\in B^m$ there is a constant
$C=C({\myeps},\dt)$ such that every $(n,\gm^{1/\rho}_n(C,\dt))$-periodic
point $x$ in $B^N$ is $(n,\gmncdt)$-hyperbolic.  (Here again we assume
$0 < \rho \leq 1$, replacing $\rho$ with $1$ in the conclusion if
$\rho > 1$.)
\ethm
The meaning of the term generic is the same as in Theorem
\ref{genparam} and is discussed in the Appendix.

\section{Formulation of the main result in
the $1$-di\-men\-si\-o\-nal case}

The proof of the main result about estimating
the rate of growth of the number of periodic points for
diffeomorphisms in $N$ dimensions has many
complications related to multidimensionality. To describe a model
which is, on one hand, nontrivial, and on the other hand, useful
for understanding the general technique, we apply our method to
the $1$-dimensional maps. The statement of the main result for
the $1$-dimensional maps has another important feature: it explains
the statement of the main multidimensional result.

Fix the interval $I=[-1,1]$. Associate to a real analytic function
$\phi:I\to \R$ the set of coefficients of its expansion
\begin{equation}
\phi_{\myeps}(x)=\sum_{k=0}^\infty {\myeps}_k x^k.
\end{equation}
For a nonincreasing sequence of positive numbers
$\myr=(\{r_k\}_{k=0}^\infty)$ such that $r_k\to 0$ as
$k \to \infty$, following the multidimensional notation, we define
a Hilbert brick of size $\myr$,
\begin{equation}
HB^1(\myr)=\{{\myeps}=\{{\myeps}_k\}_{k=0}^\infty: 
\textup{for all}\  k\in \Z_+,\ |{\myeps}_k|\leq r_k\},
\end{equation}
and the product probability measure $\mu^1_{\myr}$ associated to
the Hilbert brick $HB^1(\myr)$ of size $\myr$, which considers
each ${\myeps}_k$ to be an independent random variable uniformly
distributed on $[-r_k,r_k]$.

%{\bf
\begin{maindt} %Main $1$-dimensional Theorem.}\ {\it
For each $0 < \rho \leq \infty$
and every $C^{1+\rho}$ map  $f: I \to I$ of the interval $I=[-1,1]$
consider a Hilbert brick $HB^1(\myr)$ of an admissible size
$\myr$ with respect to $f$ and the family of analytic perturbations
of $f$,
\begin{equation} \label{anptb1}
\{f_{\myeps}(x)=f(x)+\phi_{\myeps}(x)\}_{{\myeps} \in HB^1(\myr)},
\end{equation}
with the product Lebesgue probability measure $\mu^1_{\myr}$
associated to $HB^1(\myr)$. Then for every $\dt>0$ and
$\mu^1_{\myr}$-a.e.\ ${\myeps}$ there is $C=C({\myeps},\dt)>0$
such that for all $n \in \Z_+$
\begin{equation} \label{growth1}
\gm_n(f_{\myeps}) > \exp(-Cn^{1+\dt}), \quad
P_n(f_{\myeps}) < \exp(Cn^{1+\dt}).
\end{equation}
\end{maindt}

In \cite{MMS} Martens-de Melo-Van Strien prove in a sense a stronger
statement for $C^2$ maps. They showed that for any $C^2$ map $f$ of
an interval without ``flat'' critical points there are some $\gm>0$ and
$n_0\in \Z_+$ such that for any $n>n_0$ we have $\gm_n(f)>1+\gm$.
This also implies that the number of periodic points is bounded by
an exponential function of the period.  The notion of a flat critical point
used in \cite{MMS} is a nonstandard one from the point of view of
singularity theory.  For $C^2$ maps, the authors call $x_0$ a flat critical
point of $f$ if $f'(x_0) = f''(x_0) = 0$; the distance from $f(x)$ to
$f(x_0)$ does not have to decay to $0$ as $x\to x_0$ faster than any
power of $x - x_0$.

In \cite{KK} an example of a $C^2$-unimodal map with a critical
point having tangency of order $4$ and an arbitrarily fast rate of
growth of the number of periodic points is given.
Another advantage of the Main $1$-dimensional Theorem is that it works
for $C^{1+\rho}$ maps with $0< \rho<1$, whereas the result
in \cite{MMS} works only for $C^2$ maps.

\section{Strategy of the proof}\label{strategy}
Here we describe the strategy of the proof of Theorem \ref{main}.  The
basic technique is developed and many of the technical difficulties
are resolved by the first author in \cite{K4}.  The
general idea is to fix $C > 0$ and prove an upper bound on the
measure of the set of ``bad'' parameter values $\veps \in HB^N(\myr)$
for which the conclusion of the theorem does not hold.  The upper
bound we obtain will approach zero as $C \to \infty$, from which it
follows immediately that the set of $\veps \in HB^N(\myr)$ that are
``bad'' for all $C > 0$ has measure zero.  For a given $C > 0$, we
bound the measure of ``bad'' parameter values inductively as follows.

{\it Stage 1}.\ We delete all parameter values $\veps\in
HB^N(\myr)$ for which the corresponding diffeomorphism $f_\veps$
has an almost fixed point that is not sufficiently
hyperbolic, and bound the measure of the deleted set.

{\it Stage 2}.\ After Stage 1, we consider only parameter values for which
all almost fixed points are sufficiently hyperbolic. Then we delete
all parameter values $\veps$ \ for which
$f_\veps$ has an almost periodic point of period $2$ which is not
sufficiently hyperbolic, and bound the measure of that set.

{\it Stage n}.\ We consider only parameter values for which
all almost periodic points of period at most $n-1$ are sufficiently
hyperbolic (we shall call this {\em the Inductive Hypothesis\/}). Then
we delete all parameter values $\veps$ for which
$f_\veps$ has an almost periodic point of period $n$ which
is not sufficiently hyperbolic, and bound the measure of that set.

The main difficulty in the proof is then to find a bound on the
measure of ``bad'' parameter values at stage $n$ such that
the bounds are summable over $n$ and that the sum approaches zero as
$C \to \infty$.  Let us formalize the problem.  Fix positive $\rho$,
$\dt$, and $C$, and recall that $\gmncdt=\exp(-C n^{1+\dt})$ for
$n \in \Z_+$.  Assume $\rho \leq 1$; if not, change its value to $1$.
\begin{Def} \label{inductive}
A diffeomorphism $f\in \textup{Diff}^{1+\rho}(B^N)$
satisfies the Inductive Hypothesis of order $n$ with
constants $(C,\dt,\rho)$, denoted $f\in IH(n,C,\dt,\rho)$, if for all
$k\leq n$, every $(k,\gm^{1/\rho}_k(C,\dt))$-periodic point is
$(k,\gm_k(C,\dt))$-hyperbolic.
\end{Def}

For $f \in \textup{Diff}^{1+\rho}(M)$, consider the sequence of sets
\begin{equation} \label{badset}
B_n(C,\dt,\rho,\myr,f) = \{\veps \in HB^N(\myr):
f_\veps \in IH(n-1,C,\dt,\rho)
\textup{ but } f_\veps \notin IH(n,C,\dt,\rho) \}
\end{equation}
in the parameter space
$HB^N(\myr)$.
In other words, $B_n(C,\dt,\rho,\myr,f)$
is the set of ``bad'' parameter values
$\veps \in HB^N(\myr)$ for which all almost periodic
points of $f_\veps$ with period strictly less than $n$ are
sufficiently hyperbolic, but there is an almost periodic point of
period $n$ that is not sufficiently hyperbolic.  Let
\begin{equation}\begin{split} \label{norms}
M_1&=\sup_{\veps \in HB^N(\myr)} \max\{\|f_\veps\|_{C^1},
\|f_\veps\inv\|_{C^1}\};\\
M_{1+\rho}&=\sup_{\veps \in HB^N(\myr)}
\max\{\|f_\veps\|_{C^{1+\rho}},M_1,2^{1/\rho}\}.
\end{split}\end{equation}

Our goal is to find an upper bound $\mu_n(C,\dt,\rho,
\myr,M_{1+\rho})$ for the measure
\[\mu_{\myr}^N\left(
B_n(C,\dt,\rho,\myr,f)\right)\]
of the set of ``bad'' parameter
values.  Then $\sum_{n=1}^\infty \mu_n(C,\dt,\rho,\myr,M_{1+\rho})$
is an upper bound for the measure of
$\bigcup_{n=1}^\infty B_n(C,\dt,\rho,\myr,f)$, which is the set of
all parameter values $\veps$ for which $f_\veps$ has (for some $n$) an
$(n,\gm^{1/\rho}_n(C,\dt))$-periodic point that is not
$(n,\gm_n(C,\dt))$-hyperbolic.  If this sum converges and
\begin{equation} \label{converge}
\sum_{n=1}^\infty \mu_n(C,\dt,\rho,\myr,M_{1+\rho})=
\mu(C,\dt,\rho,\myr,M_{1+\rho})\to 0 \quad \textup{as}\ C \to \infty
\end{equation}
for every positive $\rho$, $\dt$, and $M_{1+\rho}$, then Theorem
\ref{main} follows.  In the subsequent article we describe
the key construction we use to obtain a bound $\mu_n(C,\dt,\rho,
\myr,M_{1+\rho})$ that meets condition (\ref{converge}).

\section*{Appendix: Extension of $\textup{Diff}^{\,r}(M)$ to Euclidean
space}

Here we explain how to extend a diffeomorphism $f \in
\textup{Diff}^{\,r}(M)$ to a smooth function on a tubular  neighborhood of
$M$, as described in Section~2.
Given a smooth ($C^\infty$) compact manifold $M$ of dimension $D$, for
$N > 2D$ the Whitney Embedding Theorem says that a generic smooth
function from $M$ to $\R^N$ is a diffeomorphism between $M$ and its
image.  To simplify notation, we identify $M$ with its image, so that
$M$ becomes a submanifold of $\R^N$.

Let $U \subset \R^N$ be a closed neighborhood of $M$, chosen
sufficiently small that there is a well-defined projection $\pi : U
\to M$ for which $\pi(x)$ is the closest point in $M$ to $x$.  Then
for each $y \in M$, $\pi^{-1}(y)$ is an $(N - D)$-dimensional disk.
We then extend each $f \in \textup{Diff}^{\,r}(M)$ to a function $F \in
C^r(U)$ that is a diffeomorphism from $U$ to a subset of its interior
as follows.  For each $0 < \rho < 1$ and $y \in M$ choose a linear
function $h_{\rho,y,f} : \pi^{-1}(y) \to \pi^{-1}(f(y))$ that maps $y$
to $f(y)$ and contracts distances by a factor of $\rho$, and such that
$h_{\rho,y,f}$ depends continuously on $f$ and is $C^r$ as a function
of $y$.  Let $\rho = \min(\|f^{-1}\|_{C^1}^{-r},1)/2$ and let
\[
F(x) = h_{\rho,\pi(x),f}(x).
\]
Then by Fenichel's Theorem \cite{F}, every sufficiently small
perturbation $F_\varepsilon \in C^r(U)$ of such an $F$ has an
invariant manifold $M_\varepsilon \subset U$ for which
$\pi|_{M_\varepsilon}$ is a $C^r$ diffeomorphism from $M_\varepsilon$
to $M$. Then to such an $F_\varepsilon$ we can associate
a diffeomorphism $f_\varepsilon \in \textup{Diff}^{\,r}(M)$ by letting
\[
f_\varepsilon(y) = \pi(F_\varepsilon(\pi|_{M_\varepsilon}^{-1}(y))).
\]

Notice that the periodic points of $F_\varepsilon$ all lie on
$M_\varepsilon$ and are in one-to-one correspondence with the periodic
points of $f_\varepsilon$.  Furthermore, because $f_\varepsilon$ and
$F_\varepsilon|_{M_\varepsilon}$ are conjugate, the hyperbolicity of
each periodic orbit is the same for either map.  Thus any estimate of
$P_n(F_\varepsilon)$ or $\gamma_n(F_\varepsilon)$ applies also to
$f_\varepsilon$.

\begin{thebibliography}{GST2}

\bibitem[A]{A}
Problems of Arnold's seminar,
FAZIS, Moscow, 2000.
\bibitem[AM]{AM}
M. Artin and B. Mazur,
On periodic points,
Ann. Math. \textbf{81} (1965), 82--99.
\MR{31:754}
\bibitem[F]{F}
N. Fenichel,
Persistence and smoothness of invariant manifolds for flows,
Indiana Univ.\ Math.\ J.\ \textbf{21} (1971), 193--226.
\MR{44:4313}
\bibitem[GST1]{GST1}
S. V. Gonchenko, L. P. Shil'nikov, D. V. Turaev,
On models with non-rough Poincar\'e homoclinic curves,
Physica D \textbf{62} (1993), 1--14.
\MR{94c:58098}
\bibitem[GST2]{GST2}
S.\ Gonchenko, L.\ Shil'nikov, D.\ Turaev,
Homoclinic tangencies of an arbitrary order in
Newhouse regions, Preprint, in Russian.
%\bi{GY}
%A.\ Grigoriev, S.\ Yakovenko,
%Topology of Generic Multijet Preimages and Blow-up via
%Newton Interpolation,
%J. of Diff. Equations, {\bf{150}}, 349-362, (1998).
\bibitem[G]{G} M.\ Gromov,
On entropy of holomorphic maps,
Preprint.
\bibitem[HSY]{HSY}
B. R. Hunt, T. Sauer, J. A. Yorke,
Prevalence: a translation-invariant ``almost every'' for 
infinite-dimensional spaces,
Bull.\ Amer.\ Math.\ Soc.\ \textbf{27} (1992), 217--238;
Prevalence: an addendum,
Bull.\ Amer.\ Math.\ Soc.\ \textbf{28} (1993), 306--307.
\MR{93k:28018}; \MR{93k:28019}
\bibitem[K1]{K1}
V. Yu.\ Kaloshin,
An extension of the Artin-Mazur theorem,
Ann.\ Math.\ \textbf{150} (1999), 729--741.
\MR{2000j:37020}
\bibitem[K2]{K2}
V. Yu.\ Kaloshin,
Generic diffeomorphisms with superexponential growth of number of
periodic orbits, Comm. Math. Phys. \textbf{211} (2000),
no.1, 253-271.
\CMP{2000:12}
\bibitem[K3]{K3}
V. Yu.\ Kaloshin,
Some prevalent properties of smooth dynamical systems,
Tr.\ Mat.\ Inst.\ Steklova \textbf{213} (1997), 123--151.
\MR{99h:58100}
\bibitem[K4]{K4}
V. Yu.\ Kaloshin,
Ph.D. thesis, Princeton University, 2001.
%\bi{K5}
%Va.\ Kaloshin,
%Stretched exponential bound on growth of the number
%of periodic points for prevalent diffeomorphisms, part 1,
%in preparation
\bibitem[KH]{KH}
V.\  Kaloshin, B.\ Hunt,
Stretched exponential bound on growth of the number
of periodic points for prevalent diffeomorphisms, part 2,
in preparation.
\bibitem[KK]{KK} V.\ Kaloshin, O.\ Kozlovski,
An example of a $C^2$-unimodal map with an
arbitrarily fast growth of the number of periodic points,
in preparation
\bibitem[MMS]{MMS}
M.\ Martens, W.\ de Melo, S.\ Van Strien,
Julia-Fatou-Sullivan theory for real
one-dimensional dynamics,
Acta Math. \textbf{168} (1992),
no. 3-4, 273--318.
\MR{93d:58137}
\bibitem[PM]{PM}
J. Palis and W. de Melo,
{\it Geometric Theory of Dynamical Systems: An Introduction},
Springer-Verlag, 1982.
\MR{84a:58004}
\bibitem[O]{O}
J. C. Oxtoby,
{\it Measure and Category},
Springer-Verlag, 1971.
\MR{52:14213}
\bibitem[Sac]{Sac}
R. J. Sacker,
A perturbation theorem for invariant manifolds and H\"older
continuity,
J.\ Math.\ Mech.\ \textbf{18} (1969), 705--762.
\MR{39:578}
\bibitem[VK]{VK} M. Vishik, S. Kuksin, Quasilinear elliptic equations  and
Fredholm manifolds, Moscow Univ. Math. Bull.
\textbf{40} (1985), no. 6, 26--34.
\MR{88a:35086}
\bibitem[W]{W}
H. Whitney,
Differentiable manifolds,
Ann.\ Math.\ \textbf{37} (1936), 645--680.
\bibitem[Y]{Y} Y. Yomdin, A quantitative version of the Kupka-Smale
Theorem, Ergod. Th. Dynam. Sys. \textbf{5} (1985),  449--472.
\MR{87c:58091}
\end{thebibliography}

\end{document}