Content-Type: multipart/mixed; boundary="-------------0107060831144"

This is a multi-part message in MIME format.

---------------0107060831144
Content-Type: text/plain; name="01-247.keywords"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment; filename="01-247.keywords"

Bootstrap Percolation
---------------0107060831144
Content-Type: application/x-tex; name="boot18.tex"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline; filename="boot18.tex"

\documentclass[twoside,reqno,12pt,notitlepage]{amsproc}
%\usepackage[dvips,final]{graphicx} %sostituire pctex32 con dvips
%\usepackage{psfrag}
\usepackage{hyperref}

%\linespread{1.6} 

\marginparwidth 70pt
\headheight 30 pt
\oddsidemargin = 0pt
\evensidemargin = 30pt
\textwidth= 430pt
%\setlength{\baselineskip}{30pt}
\parindent=0pt
\newtheorem{thm}{\bf Theorem}[section]
\newtheorem{prop}[thm]{\bf Proposition}
\newtheorem{defin}[thm]{\textsl{\bf Definition}{}}
\newtheorem{lemma}[thm]{\bf Lemma}
\newtheorem{ans}[thm]{\bf Ansatz} 
\newenvironment{dimo}{\begin{proof}[{\bf {Proof}}]}{\end{proof}}

\numberwithin{equation}{section}

\usepackage{latexsym}

\usepackage{amsfonts,amssymb}
 
\usepackage{enumerate}

\smallskipamount=0.3truecm
\medskipamount=0.6truecm
\bigskipamount=1truecm

%%%%%%%%%%%%%% miedef

%

%%%%%%%%%%%%%%grafici



%%%%%%%%%%%%%%%%%%%%%%%%% GRECO

\let\a=\alpha \let\b=\beta  \let\c=\chi \let\d=\delta  \let\e=\varepsilon
\let\f=\varphi \let\g=\gamma \let\h=\eta    \let\k=\kappa  \let\l=\lambda
\let\m=\mu   \let\n=\nu   \let\o=\omega    \let\p=\pi  \let\ph=\varphi
\let\r=\rho  \let\s=\sigma \let\t=\tau   \let\th=\vartheta
\let\y=\upsilon \let\x=\xi \let\z=\zeta
\let\D=\Delta \let\F=\Phi  \let\G=\Gamma  \let\L=\Lambda \let\Th=\Theta
\let\O=\Omega 
%\let\P=\Pi   
\let\Ps=\Psi \let\Si=\Sigma \let\X=\Xi
\let\Y=\Upsilon

%%%%%%%%%%%%%%%%%%%%%%% CALLIGRAFICHE
%
\def\cA{{\cal A}} \def\cB{{\cal B}} \def\cC{{\cal C}} \def\cD{{\cal D}}
\def\cE{{\cal E}} \def\cF{{\cal F}} \def\cG{{\cal G}} \def\cH{{\cal H}}
\def\cI{{\cal I}} \def\cJ{{\cal J}} \def\cK{{\cal K}} \def\cL{{\cal L}}
\def\cM{{\cal M}} \def\cN{{\cal N}} \def\cO{{\cal O}} \def\cP{{\cal P}}
\def\cQ{{\cal Q}} \def\cR{{\cal R}} \def\cS{{\cal S}} \def\cT{{\cal T}}
\def\cU{{\cal U}} \def\cV{{\cal V}} \def\cW{{\cal W}} \def\cX{{\cal X}}
\def\cY{{\cal Y}} \def\cZ{{\cal Z}} 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% mie
\def\P{{\Bbb P}}
\def\R{{\Bbb R}}
\def\E{{\Bbb E}}
\def\N{{\Bbb N}}
\def\fracscript#1#2{\frac{\scriptstyle #1}{\scriptstyle #2}}

\def\compo{\circ}
\def\mm#1#2{m_-(#1,#2,p)}                               % #1=d  #2=\ell
\def\LL#1#2{{\L^{#1}(#2)}}                              % #1=d  #2=lato
\def\Lcrit#1#2{\LL{#1}{\mm{#1}{#2}}}                    % #1=d  #2=\ell
\def\eexp#1{\exp^{ \compo #1}}                          % #1= iterazioni
\def\esp{\frac{1}{d-\ell+1}}
\def\dl{{d,\ell}}
\def\mioto{\stackrel{p \to 0}{\longrightarrow}}
\def\costa{\b}
\def\ca{\a}
\def\costp{\ca_{+}}
\def\costm{\ca_{-}}
\def\costb{\f}
\def\costc{\g}                                          % #1=p
\def\defmmeno#1#2{\eexp{(#2-2)}                         % #1=d  #2=\ell
              \left( {\costa_-(#1,#2)}{
              p^{{-\frac{\scriptstyle 1}
                            {\scriptstyle #1-#2+1}}}}\right)}  
\def\defmpiu#1#2{\eexp{(#2-2)}                          % #1=d  #2=\ell
              \left( {\costa_+(#1,#2)}{
              p^{{-\frac{\scriptstyle 1}{\scriptstyle #1-#2+1}}}}\right)}      
\def\defn#1#2{\eexp{(#2-3)}
              \left( {\costb(#1,#2)}{                   % #1=d  #2=\ell
              p^{{-\frac{\scriptstyle 1}{\scriptstyle
                    #1-#2+1}}}}\right)}    
\def\boott#1#2{X^{#1}_#2}                               % #1=d  #2=vol
\def\boot#1#2#3{\boott{#1}{#2}(#3)}                     % #1=d  #2=vol #3=x 
\def\YY#1#2#3{Y^#1(#3)}                                 % #1=d  #2=vol #3=x
\def\ZZ#1#2#3{Z^#1(#3)}                                 % #1=d  #2=vol #3=x
\def\iniz#1#2#3{X^#1_{#2,0}(#3)}                        % #1=d  #2=vol #3=x
\def\ddim{$d$-dimensional }
\def\EEa#1#2#3{{#1 \conx{\dl}#2 \ 
                             \text{\rm in } {#3}}} % #1=x  #2=y #3=vol
\def\EE#1#2#3#4{\EEa{#1 }{#2}{\LL{#3}{#4}}}        % #1=x  #2=y #3=d  #4=\ell
\def\conk#1{\stackrel{Z}{\longleftrightarrow}}
\def\conx#1{\stackrel{\; X^{#1}}{\longleftrightarrow}}
\def\longconx#1{\stackrel{\; X^{#1}}{\longleftarrow\!\longrightarrow}}
\def\EEEa#1#2#3{{#1
              {\conk{#3}} #2 
              \ \hbox{{ in }} {#3}}}               % #1=x  #2=y #3=gamma
\def\EEE#1#2#3{\EEEa{#1}{#2}{\slice{#3}}}          % #1=x  #2=y #3=k
\def\norma#1{||#1||_\infty}                        % #1=x
\def\ux{\underline x}
\def\uy{\underline y}
\def\bx{\overline x}
\def\by{\overline y}
\def\xd#1#2{(#1,#2)}                               % #1=\ux #2=x
\def\slice#1{{T_{{#1}}}}                           % #1=k
\def\cc{\costc}
\def\tonda#1{\left( #1 \right)}
\def\quadra#1{\left[ #1 \right]}
\def\graffa#1{\Big\{ #1 \Big\}}
\def\nota#1{\marginpar{\tiny #1}}
%%%%%%%%%%% compatibilita`

\def\acapo{\par\noindent}
\def\Bbb{\mathbb}
\def\cal{\mathcal}
%\def\Eq{\label}
  \def\QED{\par\rightline{$\mbox$}}
\def\Z{\Bbb Z}

%\def\Bbb#1{\fam\msbfam\relax#1} 

%%%%%%%%%%%%%%


\title[\today]{{The threshold regime of finite volume bootstrap percolation.}}

\author[R. Cerf,  F. Manzo]{R. 
Cerf\footnote{Universit\'e Paris Sud, Orsay, France.},  
F. Manzo\footnote{Universit\'e Paris Sud, Orsay, France
and Technische Universit\"at, Berlin, Germany.}.\footnote{Work
partially supported by the European network ``Stochastic Analysis and
Its Applications'' ERB-FMRX-CT96-0075} \today}

\begin{document}           
\bigskip

\maketitle                 

\begin{abstract}

We prove that the threshold regime for
bootstrap percolation in a $d$-dimensional 
box of diameter $L$ with parameters $p$ and $\ell$,
where $3 \le \ell \le d$,
is $L \sim \eexp{(\ell -1)} (C p^{-1/(d-\ell +1)})$,
where $\eexp{(\ell -1)}$ is the exponential iterated $\ell-1 $ times
and $C$ is bounded from above and from below by two positive 
constants depending on $d$, $\ell$ only.



\end{abstract}
%\vfill
%\eject
\section{ \label{Section 1.} Introduction. } \ 

We consider the {\it bootstrap percolation} model,
with initial occupation density $p$ and  parameter $\ell$,
in a finite set $\G \subset \Z^d$.
More precisely, each site $x$ of $\G \subset \Z^d $ is
initially independently occupied with probability $p$ and
empty with probability $1-p$.
Afterwards, we increase deterministically the set of occupied sites
in $\G$ with the help of the following rule, until exhaustion:
any site with at least $\ell$ occupied 
nearest neighbors in $\G$ is occupied.
For a discussion on the physical relevance of this model,
we refer to \cite{[AL]}; for a nice review paper
on bootstrap percolation, see \cite{[Ad]}.


We say that a set $\G$ is {\it internally spanned}
if all its sites are occupied in the final configuration.
The basic question we are interested in  is whether or not
$\LL{d}{L}$ is internally spanned,
where $\LL{d}{L}$ is the $d$-dimensional cubic box  
of diameter $L$.

Let us denote the probability of this event by
$$
R(L,p,\dl):=
\P \left(
\lower 6pt
\vbox{
\hbox{\text{the box}
$\LL{d}{L}\text{ is internally spanned
by the bootstrap }$}
\hbox{$
\text{percolation process in }
\LL{d}{L} \text{ with parameters }
p\text{ and }\ell $}}
\right)
$$

We focus on the behavior of $R(L,p,\dl)$
when $L$ goes to infinity and $p$ goes to zero.
In the case $\ell >d $ we have that 
$$
\lim_{(L,p) \to (\infty,0)} R(L,p,\dl) =0.
$$
Indeed, the presence of a small empty cubic region in the initial 
configuration precludes the complete filling of $\LL{d}{L}$.
More interesting is the case $\ell \le d$.
Obviously, for $L$ fixed and $p$ very small the initial
configuration will be completely empty 
with high probability, hence
$
\lim_{p \to 0} R(L,p,\dl) =0.
$
On the other hand, from the much less obvious 
results of van Enter \cite{[vE]} and Schonmann \cite{[S]},
we know that for $p$ fixed and $\ell \le d$,
$
\lim_{L \to \infty} R(L,p,\dl) =1.
$
Therefore, we see that 
$
\lim_{L \to \infty} \lim_{p \to 0} R(L,p,\dl) =0,
$
while
$
\lim_{p \to 0} \lim_{L \to \infty} R(L,p,\dl) =1.
$

These different limiting  behaviors indicate the occurrence of
an interesting phenomenon:
if we send simultaneously $L \to \infty$ and $p \to 0$, the
limit of $R(L,p,\dl) $ will depend on the relative speeds of 
these convergences, i.e. if $p$ goes extremely quickly 
(respectively slowly) to $0$
compared to the way $L$ goes to $\infty$, then 
$R(L,p,\dl) $ will converge to $0$
(respectively $1$).
A natural problem is to describe precisely
each regime and the threshold between them.
In \cite{[AL]}, Aizenman and Lebowitz handled the case 
$\ell=2$, $d \ge 2$.
The threshold regime is
$$
L \sim \exp \tonda{\text{const }p^{-\frac{1}{d-1}}}.
$$

In \cite{[CeCi]}, Cerf and Cirillo analyzed the case $d=\ell=3$,
for which the threshold regime turned out to be
$$
L \sim \exp \exp \tonda{\text{const }p^{-1}}.
$$

We deal here with the general case $2<\ell \le d$.
While the proof of the upper bound on $L$ derives directly from 
an idea of \cite{[ADE]} and the results of \cite{[S]}, 
the proof of the lower bound 
is obtained by using induction on the parameters
$(\ell,d)$:
by using the technique introduced in \cite{[CeCi]}, we reduce
the estimate of the spanning probability
for the model $(\ell,d)$ to the spanning
probability for the model $(\ell-1,d-1)$.
The base of the induction is the 
Aizenman-Lebowitz case $d \ge \ell=2$.

A very challenging and interesting open problem is
to decide whether a sharp constant can be put in the 
exponentials to separate the two regimes.
Similar interesting questions can be raised 
in anisotropic models, as considered for instance
in \cite{[M]}.

%[omissis organizzazione del'articolo]\

\section{ \label{Section 2.} Basic notation. } \

%[omissis]\




For 
$t \in \R$, $n \in \N$,
we denote by 
$\eexp{n}(t) $
the exponential {\it iterated $n$ times} of $t$:
we set 
$\eexp{0}(t) := t$ 
and 
$\eexp{(n+1)}(t) := \exp ( \eexp{n}(t))$.
By $\LL{d}{l}$ we denote the  \ddim
hypercube with diameter $l$ centered at $0$.

Let us give some definitions related to
{\it site percolation} 
(see \cite{G}).
On a finite set $\G \subset \Z^d$, 
let us consider a random configuration
$\o \in \{0,1\}^\G$
obtained by occupying 
(namely, by setting $\o(x)=1$) the sites 
with the product probability measure $\P_d^p$ 
with density $p$.
We denote by
%\begin{equation*}
%  \label{eq:defprob}
$\P_d^p \tonda{\cE}$
%\end{equation*}
the probability of the event $\cE$ 
($\cE$ is a set of configurations in $\{0,1\}^\G$).
%with respect to the product measure with 
%probability $p$ on $\G \subset \Z^d$.

We say that a configuration $\o$ is {\it larger}
than a configuration $\o'$ if the set of the occupied
sites in the former contains the set of the occupied 
sites in the latter.

An event $\cE$ is called {\it increasing} if
%for any pair of configurations 
%$\o, \o' \in \{0,1\}^\G$
%such that $\o'$ is larger than $\o$ and $\o \in \cE$,
%we have $\o' \in \cE$.
for any configuration $\o \in \cE$, all configurations
$\o' > \o$ are in $\cE$.

Our main object of investigation is the following 
{\it bootstrap}
process, defined as a function of a site percolation
configuration.
On a finite set $\G \subset \Z^d$, 
let us consider a random initial configuration
obtained by occupying the sites 
with a product measure with probability $p$.
We update this initial configuration by 
using iteratively the following deterministic rule:
\begin{enumerate}
\item we occupy every empty site with at least $\ell$
      occupied nearest neighbors.
\item we leave all other sites unchanged.
\end{enumerate}
Since $\G$ is finite, and the updating procedure
cannot empty occupied sites, this procedure stops
after a finite number of steps. 
We denote by
$\boott{{d,\ell}}{\G}$
the final configuration of the \ddim 
bootstrap process in the set 
$\G$.
Thus $\boott{{d,\ell}}{\G}$ is a random map
from $\G$  to $\{0,1\}$ and for $x \in \G$,
$\boott{{d,\ell}}{\G}(x)=1$ if $x$ is occupied
and $0$ otherwise.

We will use the following basic facts:
\begin{enumerate}
\item[a)] The final configuration 
      of the bootstrap process is 
      a monotonic increasing function of the
      initial configuration.
\item[b)] The updating procedure gives the same
      final configuration if applied to 
      any configuration 
      larger than the initial
      configuration and lower than 
      the final one.
\end{enumerate}
In particular, b) implies that the updating order 
does not affect the final configuration.
We say that a finite set $\G \subset \Z^d$ 
is {\it  internally spanned}
if 
$\boot{{d,\ell}}{{\G}}{x}=1$ for any $ x \in \G$.
We focus our attention on the behavior of 
the following probability:
\begin{equation*}
  R(L,p,\dl):=
  \P^d_p \tonda{
\forall x \in \LL{d}{L} \quad
   \boot{\dl}{\LL{d}{L}}{x}=1 
}
\end{equation*}


We call {\it $\G$-clusters} the maximal 
connected sets of occupied sites in 
$X^{{d,\ell} }_{{\G}}$. 
Notice that all clusters are internally spanned.
%[migliorare]
We say that 
{\it $x$ is connected to $y$ in $\G$}
if there exists a $\G$-cluster 
$\cC$
such that 
$\{x,y\} \subset \cC \subset \G$;
we denote this event by
$\left\{ \EEa{x}{y}{\G} \right\}$.
%We consider the event of two simultaneous
%"compatible" connections:
%we denote by
%$\left\{ \EE{x}{y}{d}{l} \right\} \compo 
%\left\{ \EE{w}{z}{d}{l}  \right\}$
%the event 
%"there are two clusters 
%$\G_1$ and $\G_2$ 
%such that 
%$\{ \G_1 \cup \partial \G_1 \} \cap 
%\{ \G_2 \cup \partial \G_2 \} = \emptyset$, 
%$\{x,y\} \subset \G_1 \subset \LL{d}{l}$
%and
%$\{w,z\} \subset \G_2 \subset \LL{d}{l}$"


We will use the symbols $c$, $C$ and $\cc$ for  
positive constants
(possibly depending on the parameters of the bootstrap percolation 
model).
 
%and the symbol $\cc$ for arbitrarily large constants.

\section{ \label{Section 3.} Main result. } \

The following theorem describes the threshold regime of
finite volume bootstrap percolation for all values
$3\leq \ell\leq d$.

\begin{thm}
For $2 < \ell \le d$,
there exist $2$ constants
$0<\costm(d,\ell) \leq \costp(d,\ell) < \infty$,
independent of $p$, such that if
\begin{equation}
 \label{eq:defl}
  L_{\pm} (\dl,p) :=
  \eexp{(\ell-1)} \tonda{ \ca_{\pm} \ p^{\scriptstyle {-\esp }}},
\end{equation}
then 
$$
\hbox{\rm a) }
\P^{d,\ell}_{p} \tonda{\forall \; x \in \LL{d}{L} \quad
X^{{d,\ell} }_{{\LL{d}{L}}}( {x})
 = 1  }
\to 1\ \ \ \text{ if } (p,L) \to (0,\infty )
\ \hbox{ with } L \ge L_+(\dl,p) 
$$
$$
\hbox{\rm b) } 
\P^{d,\ell}_{p} \tonda{\forall \; x \in \LL{d}{L}\quad 
X^{{d,\ell} }_{{\LL{d}{L}}} ({x})
= 1 }
\to 0\ \ \ \text{ if } (p,L) \to (0,\infty )
\ \hbox{ with } L \le L_- (\dl,p) 
$$
\end{thm}

{\bf Remark:}  The case $2=\ell \le d$ is handled in
\cite{[AL]}. 
The result in the case $\ell=d$ was a conjecture
proposed in \cite{[ADE]}. The specific case
$\ell=d=3$ was solved in \cite{[CeCi]}.

\medskip
It looks like the phenomenon hidden behind this behavior is
linked with the notion 
 of  "critical droplet".%\nota{ dobbiamo citare van enter?}
Indeed, the spanning
probability has the same asymptotic behavior
as the probability of finding in the volume 
$\LL{d}{L}$ a suitably large internally-spanned
cluster.

\medskip
To prove this result, we use an inductive procedure.
This is very natural for the estimate of the lower bound a).
Indeed, the problem of the filling of a face 
of an hypercube once the hypercube is full  is a 
bootstrap percolation problem  with parameters $(d-1,\ell-1)$.
By far less immediate is to see how to use induction in the
proof of case b).
We use there a natural generalization of the construction
of Cerf and Cirillo, relating in this way a bootstrap 
percolation model with parameters $(d,\ell,p)$ with a bootstrap 
percolation model with parameters $(d-1,\ell-1,2p-p^2)$.

\bigskip

\section{Proof of case a)}

\bigskip

This is the easiest part of the proof.
The argument is nothing new. 
In fact the idea of the argument
is already present in \cite{[ADE]}.
To estimate from below the
spanning probability,
we use  iteratively
Straley's argument and
the renormalization procedure introduced
in \cite{[AL]}.

First, we use  the renormalization scheme introduced in \cite{[AL]}
and \cite{[S]} to prove that if 
$R(L^*,p,\dl ) \ge ({ e (2d-1)})^{-1}$
for some $L^*$, 
then $R(L,p,\dl) \ge 1 - C e^{-{L}/{L^*}}$
for all $L>L^*$.
Assume (for simplicity's sake) that $L$ is an integer multiple of
$L^*$.
We tile $\LL{d}{L}$ with the translates of $\LL{d}{L^*}$.
As initial condition for
the bootstrap percolation process on the renormalized lattice
we use the indicator functions of the events
$$ \{ L^* x + \LL{d}{L^*}\text{ is internally spanned}\}
\,,\quad x\in{\Bbb Z}^d\,.$$
It is clear that if the bootstrap process defined on the 
renormalized lattice spans the volume, so does the
process on the original lattice.
Hence,
\begin{equation}  
\label{rinormalizzazione}
  R (L,p,\dl) 
  \ge
  R \tonda{\frac L{L^*},R(L^*,p,\dl),\dl}
\end{equation}  
If a box is
not  spanned then in the initial condition
there must exist a cluster 
of empty sites that crosses the box.
A standard site-percolation estimate, based on a Peierls type
argument, gives
\begin{equation}  
\label{pierls}
  1-R (N,q,\dl) 
  \le
  \sum_{l=N}^{\infty} {q}^{l}  2d (2d-1)^{l-1} =
  \frac{2d}{2d-1} \ \frac{
  \tonda{(2d-1) q }^{N-1}}
{1- (2d-1){q}}
\end{equation} 
By \eqref{rinormalizzazione} and by \eqref{pierls}
with $N=L/L^*$ and $q=R (L^*,p,\dl) \ge {(e (2d-1))}^{-1}$,
we get
\begin{equation}
   R (L,p,\dl) 
  \ge
  1- C {e}^{-{L}/{L^*}} .
 \label{eq:maggiorata} 
\end{equation}
Next, we prove by induction
the following property:
there exists
$ \costa_+ (\dl)>0$ such that if we set
\begin{equation*}
  m_+ (\dl,p) := \defmpiu{d}{\ell}
\end{equation*}
then
\begin{equation}
 \label{hpr1}
  \forall L>m_+(d,\ell,p)\qquad
  R(L,p,\dl)
  \ge
  1- \exp{\tonda{- \frac{L}{L_+ (\dl,p)}}}
\end{equation}
%In the case $\ell = 1$, a single
%occupied site in the initial condition is sufficient to span
%the entire volume.
%Hence, $\forall \; L \in \N \; , p \in [0,1]$,
%\begin{equation}
% \label{elle1}
% R(L,p,\dl)= 1- \tonda{1- p}^{L^d} 
% \ge
% 1- \exp \tonda{ -p L^d}
%\end{equation}
%For $L \ge L_+(d,1,p) = \costp(d,1) p^{-\frac{1}{d}}$, we get
%$R(L,p,\dl) \ge 1- e^{\costp(d,1)} = ({e (2d -1)})^{-1}$
%for $\costp(d,1) = - \ln \tonda{1- ({e (2d -1)})^{-1}}$.
For $\ell = 1$ and $\costp(d,1)=1$, \eqref{hpr1} is immediate, 
since a single
occupied site in the initial condition is sufficient to span
the entire volume.
In the case $\ell = 2$,   \eqref{hpr1} has been 
proven in \cite{[AL]} (see (1.5) therein).
We end our induction proof 
by showing that if  \eqref{hpr1} holds
for $(d-1,\ell-1)$ then 
$R (L^*,p,\dl) \ge ({ e (2d-1)})^{-1}$
for $L^* \ge  L_+(\dl,p)$.

%Let $\cE_{\dl}$ be the event 
%$$
%  \graffa{\exists \text{ in }\LL{d}{L} \text{ at time }0 
%  \text{ a translate of } \LL{d}{L_+(d-1,\ell-1,p) } 
%  \text{ completely occupied}}.
%$$
Let $m_+:=m_+ (\dl,p)$ (we drop the dependency of $m_+$
on $\dl,p$ to lighten the notation).
In the case $2 < \ell \le d$,
for $\costa_+ (\dl) > \costp (d-1,\ell-1)$
and sufficiently small $p$, 
we have that
\begin{equation}
  m_+ \ge  L_+^2(d-1,\ell-1,p)\,.
 \label{eq:l2}
\end{equation}
To estimate from below the probability that
$\LL{d}{L}$ is spanned,  
we consider the event

\smallskip
1) at time $0$ there exists  in $\LL{d}{L}$  
a box 
$x \;  m_+ + \LL{d}{m_+} $
completely occupied and  

2) for every 
$m_+ \le k \le L$
the $(d-1)$-dimensional
bootstrap percolation models with 
parameters $(p,\ell -1)$
restricted to the faces of the boxes
$x \; m_+ + \LL{d}{k}$  are internally spanned. 
%(see \cite{[S]} for more details on this construction).

The idea %behind this construction 
is that
once a box $x \; m_+ + \LL{d}{k}$ is occupied,
the sites on a face of the box have
an occupied neighbor in the box and 
therefore need only $\ell-1$ neighbors in
the face to become occupied. 
This procedure can be iterated to fill the 
whole $\LL{d}{L}$.\footnote{We warn the reader that this 
argument is 
sligthly oversimplified since we are not considering the
edges.  We refer to \cite{[S]} for the full construction.}
Thus,
\begin{equation*}
  R(L,p,\dl) 
  \ge
  \tonda{1- \tonda{1-p^{m_+^d}}^{\tonda{\frac {L}{m_+}}^d} }
  \prod_{k=m_+ +1}^{L}
   R(k,p,d-1,\ell-1)^{2d} \ge
\end{equation*}
\begin{equation*}
  \tonda{1-e^{{-p^{m_+^d}}{\tonda{\frac {L}{m_+}}^d}}}
  \exp \tonda{ - 
   \sum_{k=m_++1}^{L} 2d \; e^{- \tonda{\frac{k}{\sqrt {m_+}}}}}
  \ge 
\end{equation*}
\begin{equation}
\label{tendea1}
  \tonda{1-e^{{-p^{m_+^d}}{\tonda{\frac {L}{m_+}}^d}}}
  \exp  \tonda{ - 2d \sqrt {m_+} \; e^{- c  \sqrt {m_+}} }
%    \frac{1}{1-e^{- m_+^{-1/2}}}    }
\end{equation}
The factor $\sqrt {m_+}$ in the above formula \eqref{tendea1}
comes from \eqref{eq:l2}.
The last term in  \eqref{tendea1} clearly tends to one for 
$M \to \infty$.
By using \eqref{eq:defl}
we see that also the first term 
goes to $1$ as $p \to 0$
for any $L \ge  L_+(\dl,p)$:
Indeed, for sufficiently small $p$,
\begin{eqnarray}
  m_+p^{-\frac{m_+^d}{d}} 
   \le
  p^{-c m_+^d}= &
   \exp \tonda{c \ln p^{-1} 
     \tonda{ \exp 
       \tonda{ d  \eexp{(\ell-3)} 
    \left( {\costa_+(d,\ell)}{p^{{-\frac{\scriptstyle 1}{\scriptstyle
                    d-\ell+1}}}}\right)}}} \nonumber\\
  \  & \le
  \eexp{(\ell-1)}\left( 
    {\ca}{p^{{-\frac{\scriptstyle 1}{\scriptstyle
                    d-\ell+1}}}}\right)
 \label{eq:spiega}
\end{eqnarray}
for sufficiently large $\costp (d,\ell)$, r.h.s. of
\eqref{eq:spiega}
tends to infinity slower than $L_+$ and 
for $L \ge L_+$, r.h.s. of \eqref{tendea1} can be bounded by
$({ e (2d-1)})^{-1} $.
We can then use the bound in \eqref{eq:maggiorata}
and get \eqref{hpr1}.

%Property \eqref{hpr1} implies that the spanning
%probability can be bounded by the probability that
%a completely full translate of the
%hypercube $\LL{d }{ m_+ (\dl) } $ is found in the 
%initial configuration.
%Hence,
%\begin{equation}
%\label{p1}
%\P_p^{\dl} \tonda{
%\boot{d}{\ell}{x} 
%\equiv 1 \ 
%\forall \; x \in \LL{d}{L} } \ge
%1 - \tonda{1- p^{ m_+^d (\dl) } }^{(\frac{L}{ m_+ (\dl)})^d}
%\ge
%\end{equation}
%$$
%\ge 
%1-\exp \tonda{- \frac{L}{ L_+ (d-1,\ell-1,p)}}.
%$$

%In the last inequality, we used that 
%$L_+(\dl,p) >> p^{-c m_+^d (\dl) }$ for any constant $c$.

%Supposing that \eqref{hpr1} is valid for $(\dl)$, it
%is easy to show that it also holds for $(d+1,\ell+1)$.
%The key argument is that a 
%face of a completely full ($d+1$)-dimensional hypercube
%with side-length $l$  is a
%$d$-dimensional cube where all the sites have at least
%one occupied neighbor in the last dimension.
%Hence,
%$$
%\P_p^{d+1,\ell+1} \tonda{
%\boot{d+1}{\ell+1}{x} 
%\equiv 1 \ 
%\forall \; x \in \LL{d+1}{L} |
%\LL{d +1}{ m_+ (d+1,\ell+1) } \text{ full at time } t=0}
%\ge 
%$$
%$$
%\ge
%\prod_{k = \lceil (m_+ (d+1,\ell+1) -1)/2 \rceil }^{L} 
%\tonda{1 - \tonda{1-\P_p^{\dl} \tonda{
%\boot{d}{\ell}{x} 
%\equiv 1 \ 
%\forall \; x \in \LL{d}{ 2k+1} }
%}}
%\ge
%$$
%$$
%\ge
%\prod_{k= +1}^{L- \lceil m_+ (d+1,\ell+1) \rceil } 
%\tonda{1-\exp \tonda{- c \frac{ m_+ (d+1,\ell+1)+2k}{ L_+ (d-1,\ell-1,p)}}}
%\ge 
%$$
%\begin{equation}
%\label{hpr1b}
%\ge
%\exp \tonda{- c' L \exp \tonda{-\frac{m_+(\dl)}{L_+(d-1,\ell-1,p)}}}^d 
%\mioto 1.
%\end{equation}

%[mettere a posto i $k$]

%The basis of the induction is the result of \cite{[AL]}
%for the case $d \ge \ell =2$.

%[Oppure il caso $\ell=1$]


\bigskip

\section{Proof of case b)}

In order to prove part b) of the Theorem, we 
give a bound on the probability that
two points are in the same cluster
for the bootstrap percolation process
in a box with diameter of the order of the critical droplet.
Since we choose the box with a sufficiently small
diameter, the final configuration is  "sub-critical" 
and looks like 
subcritical site percolation.
This is the content of our key estimate.
Let us set
\begin{equation}
  \label{defmmoins}
  \mm{d}{\ell}:= \defmmeno{d}{\ell},
\end{equation}
where 
$\costa_- ({d,\ell})$
is a constant independent from $p$.

\begin{lemma}
\label{L1}
Let $d \ge 1$ be fixed.

For $\ell = 1$:  
\begin{equation}
\forall m \in \N\qquad
  \P^d_p \left( \EE{x}{y}{d}{m}\right) 
  =
  1-(1-p)^{m^d}
\label{hpr21}
\end{equation}

For $d \ge \ell = 2$:
there exist $ \costa_- (d,2) > 0$, $C >0$ and 
$p(d,2)>0 $ 
such that: 

\smallskip $\forall p<p (d,2)\quad \forall m < \mm{d}{2} \quad \forall
x,y \in \LL{d}{m}$
\begin{equation}
  \P^d_p \left( \EE{x}{y}{d}{m}\right) 
  \leq
  \tonda{C \norma{x-y}^{d-1} p}^{{\norma{x-y}}/{2}}
\label{hpr22}
\end{equation}


For $3 \leq \ell \le d$:
there exist $ \costa_- (d,l) > 0$,
$ \costc(d,\ell) > 0$, $ p(d,\ell)>0 $ such that: 

\smallskip $\forall p<p (d,\ell) \quad \forall m < \mm{d}{\ell}\quad
\forall x,y \in \LL{d}{m}$
\begin{equation}
  \P^d_p \left( \EE{x}{y}{d}{m}\right) \leq
  p^{- \costc \ \norma{x-y}}
\label{hpr2}
\end{equation}
\end{lemma}

Next, for a box of diameter $l$ to be internally spanned
there must exist internally spanned regions of all 
intermediate diameters \cite{[AL]} (more precisely,
for any $k \leq l/2$ there must exist an
internally spanned region of diameter 
between $k$ and $2k+1$).
We choose this intermediate diameter of the order of 
$\mm{d}{\ell}$ to get the desired bound. 

%We use this  idea together with the argument
%of \cite{[AL]} on the necessity of having an internally-spanned
%region (critical droplet) with suitable diameter
%(to be precise, the argument claims that 
%there must exist internally-spanned regions
%with diameter between $k$ and $2k+1$
%for any $k$, but we are interested in a suitable
%$k$ for our estimate).
%In this way we bound the spanning probability
%with the probability of finding a suitably large 
%cluster in the volume.

%Before stating the inductive hypothesis, 
%let us start by giving some technical remarks.

%The following Lemma is a direct consequence of 
%van den Berg - Kesten inequality.
%For completeness, we give an explicit proof.

%\bigskip



%\begin{lemma}
%\label{vdbk}
%\end{lemma}
%{\it $\forall \; l \in \N$,
%$$
%  \P^d_p \left(
%  \left\{ \EE{x}{y}{d}{l} \right\} \cap 
%  \left\{ \EE{w}{z}{d}{l}  \right\} \cap 
%  \left\{ \EE{x}{w}{d}{l}  \right\}^c  
%\right) \leq
%$$
%\begin{equation}  
%  \leq
%  \P^d_p \left( \EE{x}{y}{d}{l} \right) 
%  \P^d_p \left( \EE{w}{z}{d}{l} \right) 
%  \label{l1}
%\end{equation}
%}
%\begin{proof}
%The proof is rather straightforward: 
%l.h.s. of \eqref{l1} can be written as the sum,
%over all possible 
%$\G_1 \subset  \LL{d}{l} \setminus \{w,z\}$
%such that $\G_1 \supset \{x,y\}$
%and 
%over all possible 
%$\G_2 \subset  \LL{d}{l}$
%compatible with $\G_1$ and
%such that $\G_2 \supset \{w,z\}$,
%of the probability that $\G_1$ and $\G_2$ 
%are supports of $\LL{d}{l}$-clusters.
%Since $\G_1 \cap \G_2 = \emptyset$,
%the probability that $\G_2$ is internally spanned 
%is independent of the fact that $\G_1$ is
%internally spanned.
%On the other hand, the probability that 
%$\partial \G_2$ is empty conditioned to the fact
%that $\partial \G_1$ is empty is larger or equal to 
%the probability that $\partial \G_2$ is empty.
%Hence, l.h.s. of \eqref{l1} is smaller or equal to 
%the sum, 
%over all $\G_1$ as before,  
%of the probability that $\G_1$ is the support of a 
%$\LL{d}{l}$-cluster
%times the sum,
%over all $\G_2$ as before, 
%of the probability that $\G_2$ is the support of a 
%$\LL{d}{l}$-cluster.
%By removing the requirement  that 
%$\G_1 \cap \{w,z\} = \emptyset$ and 
%the compatibility condition, we get r.h.s. of 
%\eqref{l1}.
%\end{proof}

%We use the argument of \cite{[AL]} and  show that
%in order to have the spanning of a given volume,
%there must exist into the volume at least one
%internally-spanned cluster with diameter within $k$
%and $2k+1$ for every integer $k$ up to the semi-diameter 
%of the volume itself.
%In our application, we will only be interested
%in $k \sim \mm{d}{\ell}$.

\begin{lemma}
\label{L2}
{\rm \cite{[AL]}}
{\it 
If $\G \subset \Z^d $ is internally spanned then
for all $k < ( \text{\rm diam} \G -1) /2$ 
there exists $\G_1 \subset \G$ internally spanned
with 
$ k \leq  \text{\rm diam} \G_1 \leq 2k+1$.
}
\end{lemma}

{\it Sketch of proof.}
The proof can be found in \cite{[AL]}.
The idea is to realize the bootstrap percolation by 
an iterative algorithm which occupies at most one 
new site at each step. 
%close to the current cluster having maximal diameter.
%%This is a well known result, based on the fact that
%%when occupying an empty site we can connect
%%at most $d$ different clusters.
The new cluster obtained in this way
has diameter not larger than $2k+1$, if $k$ is 
the maximal diameter of the clusters that coalesce 
with the  newly occupied site.

\medskip
We now finish the proof of the case b) of the Theorem
with the help of the two previous lemmata.
Suppose $\G$ is a region which is internally spanned.
Let $\L^d $ be a box such that 
$\G \subset \L^d$, $\text{diam } \G =\text{diam } \L^d$ 
and let $x,y \in \G$ be such that
$\norma{x-y}= \text{diam } \G$.
Then the event $\{\EEa{x}{y}{\L^d}\}$ occurs.
Therefore, by lemma \ref{L2}
we have, for any $L, \k$ such that
$2\k+1 < L$ 
\begin{eqnarray*}
  R(L,p,\dl) \le
  \P^d_p \tonda{ {\exists \; m \quad 
    \k \le m < 2 \k +1 \quad
    \exists z \in \LL{d}{L} \quad 
    z+\LL{d}{m} \subset \LL{d}{L} \quad 
    \atop
    \exists \; x,y \in z+\LL{d}{m} \quad 
    \norma{x-y}= m, \quad 
    \EEa{x}{y}{z+\LL{d}{m}} }}
  \\
   \le
  (\k+1) L^d (2 \k +1)^{2 d} 
    \max_{\k \le m < 2 \k +1} 
    \max_{\scriptstyle z \in \LL{d}{L} \atop 
           \scriptstyle z+\LL{d}{m} \subset \LL{d}{L}}
    \max_{\scriptstyle  x,y \in z+\LL{d}{m} \atop 
           \scriptstyle  \norma{x-y}= m}
    \P^d_p \tonda{\EEa{x}{y}{z+\LL{d}{m}} }
\end{eqnarray*}
We distinguish two cases in order to bound $R(L,p,\dl)$.
If $L < m_- (\dl,p) $, where $m_- (\dl,p)$ is defined in \eqref{defmmoins}, 
then we  choose $\k = L / 3$ and we apply Lemma \ref{L1}
in the case $\ell > 2$
to get 
$$
  R(L,p,\dl)
  \le 
  L^{3d+1} p^{\cc \fracscript{L}{3}}.
$$
If $L \ge m_- (\dl,p) $,
we choose $\k= m_- (\dl,p) / 3$ and
we get 
$$
  R(L,p,\dl)
  \le 
  L^{3d+1} p^{\cc {m_- (\dl,p)}/{3}}.
$$
From these inequalities, we see that
there exists $\costm (\dl) > 0$ 
such that if 
$$
L \le
\eexp{(\ell-1)} \tonda{ \ca_{-} \ p^{\scriptstyle {-\esp }}},
$$
then $R(L,p,\dl)$ goes to $0$ in the limit
where $(L,p) \to (\infty,0)$.

\medskip
{\it Proof of Lemma 5.2.}
The result for $\ell=1$ is immediate, since 
a single occupied site in the initial configuration
is sufficient to span the entire volume.

For the case $\ell=2$, we use a procedure 
introduced  by Aizenman and Lebowitz in \cite{[AL]}.
We consider an integer 
\begin{equation*}
m \leq \mm{d}{2}=
\costa_-(d,2) \; p^{{-\frac{\scriptstyle 1}
                        {\scriptstyle d-1}}},
\end{equation*}
and we set
$q:=2p-p^2.$



Let $x \in \Z^d$ be a $d$-dimensional vector; 
we denote by $\ux$ its first $d-1$ coordinates and
by $\bx$ the last one. 
We write $x=\xd{\ux}{\bx}$. 

By symmetry, we can suppose that 
$\xd{\ux}{\bx}$ and $\xd{\uy}{\by}$ 
in $\Z^d$ are
such that $\by-\bx = \norma{\xd{\ux}{\bx} - \xd{\uy}{\by}}$,
namely that 
the distance along the $d$-th direction is larger than
or equal to the distance in the other directions.
%$|\bx-\by| \ge \max_{1 \le d-1} |x_i - y_i|$.
We consider the slices 
$$
\slice{i}:=\left\{ (\ux,\bx) \in \LL{d}{m} \ ; 
\  \bx \in \{2i, 2i+1 \} \right\},\ i \in \Z.
$$
Suppose  $\{\EE{x}{y}{d}{m}\}$ occurs.
Let $\cC$ be the $\LL{d}{m}$-cluster that contains 
$x$ and $y$ and let $A$ and $B$ the first and the
last indices of the slices intersecting $\cC$.
It is immediate to see that in  all the slices 
$\slice{i}$ for 
$i \in [A,B]$
there exists at least one occupied site $\xd{\ux',\bx'}$
such that $\norma{\ux - \ux'} \le \norma{x - y}$.
Let us set  $l:=\norma{x-y}$.
By \eqref{hpr21},
\begin{equation}
\label{ceci1}
  \P^d_p \left( \EE{x}{y}{d}{m}\right) 
  \leq
  d \tonda{1-\tonda{
     1-q}^{{
       (2 l +1 )}^{d-1}}}^{ l /{2}},
%  \leq
\end{equation}
where the factor $d$ comes from the possible
directions where $\norma{x-y}$ is realized.
By using the fact that 
$\ln t \le t - 1$, 
we bound the r.h.s. of \eqref{ceci1} by
%$$
%  \exp \tonda{\frac{\norma{x-y}}{2} 
%        \ln (1- \exp({(2\norma{x-y}+1)^{d-1} }\ln (1-q)))}
%  \leq
%$$
\begin{equation*}
%\label{ceci}
%  \leq
  d \tonda{ -  \ln (1-q)^{{(2 l +1)}^{d-1}}}^\frac{l}{2};
\end{equation*}
for small $q$, $ \ln (1-q) \ge - 2 q $ and hence we get 
bound  \eqref{hpr22}.  
%The factor $d$ in \eqref{ceci} comes from the number
%of possible directions where $\norma{x-y}$ is realized.  

For $\ell \ge 3$, we use an induction on the dimension 
 $d$ and on the parameter $\ell$.
%:for $\ell \ge 4$, we assume the thesis is true for
%$d-1$, $\ell -1$ and prove it for $d$, $\ell$; 
%then
%we show that in the case $\ell=3$ \eqref{hpr2}
%follows from \eqref{hpr22}.



Following \cite{[CeCi]}, we define an auxiliary map $\ZZ{d}{\LL{d}{m}}{x}$ on 
$\Z^d$ 
in the following way.  
In every slice $\slice{i}$,
we increase the initial configuration 
by occupying a site $(\ux,2i)$ (resp $(\ux,2i+1)$)
if the corresponding site 
$(\ux,2i+1)$ (resp. $(\ux,2i)$)
belonging to the other hyper-plane in the
same slice is occupied. 
We build a configuration $\YY{d}{\LL{d}{m}}{(\ux,\bx)}$
by updating on each slice this initial configuration according
to the bootstrap percolation process 
in $\slice{i}$ with the neighboring slices occupied; 
more precisely, we occupy 
$\LL{d}{m}\setminus \slice{i}$, 
we run $\boott{d,\ell}{\LL{d}{m}}$
under this initial condition
and we define 
$\YY{d}{\LL{d}{m}}{\ux,2i)}=\YY{d}{\LL{d}{m}}{\ux,2i+1)}$
as the restriction to $\slice{i}$ of this 
bootstrap percolation process.

The monotonicity properties of bootstrap percolation
with respect to the initial configuration imply that
$\YY{d}{\LL{d}{m}}{(\ux,\bx)} \ge 
\boot{{d,\ell}}{\LL{d}{m}}{(\ux,\bx)}$.
The interesting point is that 
%$\YY{d}{\LL{d}{m}}{(\ux,2i)}=\YY{d}{\LL{d}{m}}{(\ux,2i+1)}$ 
%and that 
the set 
$\{ \ux \in \LL{d-1}{m} \ ; \  
\YY{d}{\LL{d}{m}}{(\ux,2i)}=1 \}$
is equal to the
($d-1$)-dimensional bootstrap of the ($d-1$)-dimensional
configuration where the site 
$\ux\in \LL{d}{m}$ is occupied if either
$\xd{\ux}{2i}$ or $\xd{\ux}{2i+1}$ was initially occupied. 
%$$
%\{ \ux \in \LL{d-1}{m} \ ; \  
%\iniz{d}{\LL{d}{m}}{(\ux,2i)}=1 \text{ or }
%\iniz{d}{\LL{d}{m}}{(\ux,2i+1)}=1\};
%$$
Thus, 
$\YY{d}{\LL{d}{m}}{(\ux,\bx)}$ is a stack of 
($d-1$)-dimensional bootstraps with parameters $\ell-1$
and $q=2p-p^2$.
We set
\begin{equation*}
n:=\defn{d}{\ell},
\end{equation*}
for a suitable constant $\costb(d,\ell)$
which will be chosen later on (see before \eqref{l=3}).
%\nota{In
%effetti, usiamo $\costb(\dl)$ solo nel caso $\ell=3$, altrimenti 
%nella \eqref{somma} lo
%maggioriamo con $\infty$!}
We finally define our process as 
$\ZZ{d}{\LL{d}{m}}{(\ux,\bx)}:=\YY{d}{\LL{d}{m}}{(\ux,\bx)}$
if the slice containing $(\ux,\bx)$ does not contain any 
cluster larger than $n$; 
otherwise, we set 
$\ZZ{d}{\LL{d}{m}}{(\ux,\bx)}:=1$ 
for  all the sites 
$(\ux,\bx)$ in the slice.
For $\G \in \LL{d}{m}$,
we denote by 
$
\big\{ \EEEa{\ux}{\uy}{\G} \big\}
$
the event 
$$\exists\,\cC
%there is a connected set 
\subset \slice{i},\quad
\cC\text{ is connected},\quad
\{(\ux,2i),(\uy,2i)\} \subset \cC,\quad
\forall \; (\uy',\by') \in \cC\quad
\ZZ{d}{\LL{d}{m}}{(\uy,\by)}=1\,.$$

By construction, we get for all $i \in [A,B]$ 
\begin{equation*}
  \P^d_p \left(\big\{ \EEE{\ux}{\uy}{i}\big\}
          \cap
          \big\{
                  \; \forall \; y \in \slice{i} \quad
\ZZ{d}{\LL{d}{m}}{y}=1\big\}^c
         \right)
  \le
  \P^{d-1}_q \left( 
%      \EE{\ux}{\uy}{d-1}{m}
       \ux \longconx{d-1,\ell-1} \uy \ \text{\rm in } \LL{d-1}{m}
  \right).
%\label{dmu}
\end{equation*}


Let $\{I_k\}_{k \leq U}$ be the ordered set of indices,
between $A$ and $B$  
of the slices that are completely full in 
$Z^{d}$ i.e.  
$
\big\{k ; \ZZ{d}{\LL{d}{m}}{(\ux,2I_k)}=1 
\ \forall \; \ux \in \LL{d-1}{m}\big\}
$.
We set $I_0:=A$, $I_{U}:=B$


We decompose our event $\big\{\EE{x}{y}{d}{m}\big\}$
according to the possible values of 
$A$, $B$, $U$ and  $\{I_k\}_{k \leq U}$.
We have
$$
  \P^d_p \left( \EE{x}{y}{d}{m} \right) \leq
  d
  \sum_{a=1}^m
  \sum_{b=\by-\bx+a}^{m} \ 
  \sum_{u=0}^{b-a} 
  \sum_{i_1<\cdots<i_u}
    \P^d_p \Big( \left\{ \EE{x}{y}{d}{m} \right\} \cap 
$$
\begin{equation} 
    \{A=a\} \cap 
      \{B=b\} \cap 
      \left\{ U=u \right\} \cap 
      \left\{ I_1=i_1, \ldots,  I_u=i_u \right\} 
    \Big)
\label{1}
\end{equation}
where the factor $d$ comes from the possible choices of the direction
where $\norma{x-y}$ is realized.
We get 
$$
\P^d_p \left( \left\{ \EE{x}{y}{d}{m} \right\} \cap 
  \{A=a\} \cap 
  \{B=b\} \cap 
  \left\{ U=u \right\} \cap 
  \left\{ I_1=i_1, \ldots,  I_u=i_u \right\}  
\right)
$$
\begin{equation}
\leq
  \prod_{v=1}^{u} 
   \P^d_p 
    \left(\forall \; \ux' \in \LL{d-1}{m} \; 
          \ZZ{d}{}{\ux',2i_v}=1 \right)
  \prod_{v=1}^{u+1} 
   \P^d_p \left(\cE(i_{v-1}+1,i_{v}-1) \right),
\label{2}
\end{equation}
where, for $i < j $,
$\cE (i,j)$ is the event: \acapo 
$$
\graffa{[i,j] \cap \{I_k\}_{k \leq U} = \emptyset ,\ 
\exists \; x(i) \in \slice{i}, \; y(j) \in \slice{j} ; \;
\graffa{\EEEa{x(i)}{y(j)}{\bigcup_{h=i}^j \slice{h}}}}
$$
that is, in the process $Z^d$, none of the slices 
between $T_i $ and $T_j$
is full and there exists
an occupied path between the slices $T_i $ and $T_j$.

The occurrence of
$\cE (i,j)$  
implies that there is a path 
$\{ (\ux_h,2 j_h) \}_{h \leq R}$
(where $R$ is a random value larger than
or equal to $j-i$)
such that
\begin{itemize}
  \item
$j_0=i$, $j_R=j$,
  \item
$\EEE{\ux_h}{\ux_{h+1}}{j_h}$
  \item
if $j_h = j_{h'}$  then the event
$\graffa{\EEE{\ux_h}{\ux_{h'}}{j_{h}}}$
does not occur.
\end{itemize}


We  estimate $\P^d_p \left( \cE(i,j) \right) $
with the help of the \ddim bootstrap percolation process
with parameters $d-1$, $\ell-1$ and $2p-p^2$ by
$$\displaylines{
  \P^d_p \left( \cE(i,j) \right) \leq\hfill\cr
%  \leq
  \sum_{r \geq j-i}  
  \sum_{
    \begin{subarray}{c}
      \ux_0,\ldots,\ux_r \ s.t. \\
      \norma{\ux_{h+1}-\ux_{h}} \leq n
    \end{subarray}}
  \kern -10 pt 2^r \ 
  \P^d_p 
   \Big( \bigcap_{h=1}^r \graffa{
    \big\{ \EEE{\ux_h}{\ux_{h+1}}{i_h} \big\}
     \bigcap_{\scriptstyle{ h' :h<h'\le r \atop \text{ s.t. } i_h=i_{h'}}}
     \big\{ \EEE{\ux_h}{\ux_{h'}}{i_h} \big\}^c
   } \Big)
 % \leq
}$$
Now,
$$
  \P^d_p 
   \Big( \bigcap_{h=1}^r \graffa{
    \left\{ \EEE{\ux_h}{\ux_{h+1}}{i_h} \right\}
     \bigcap_{h' \in (h,r] \atop \text{ s.t. } i_h=i_{h'}}
     \left\{ \EEE{\ux_h}{\ux_{h'}}{i_h} \right\}^c
   } \Big)
 \leq
$$
\begin{equation}
\label{vbk}
  \P^d_p \tonda{
    \left\{ \EEE{\ux_1}{\ux_{2}}{i_1} \right\}
    \compo
    \left\{ \EEE{\ux_2}{\ux_{3}}{i_2} \right\}
    \compo \cdots \compo
    \left\{ \EEE{\ux_{r-1}}{\ux_{r}}{i_{r+1}} \right\}},
\end{equation}
where the symbol $\compo$ denotes the disjoint occurrence
of the events (see \cite{G} \S 2.3 p. 37 for the definition of
disjoint events in percolation).  
Roughly speaking, given
two increasing events 
$\cE$,  $\cE'$, we define their
{\it disjoint occurrence}
$\cE \compo \cE'$ as the set of
all configurations $\o$  
which contain two disjoint sets
of occupied sites such that the 
first set implies $\cE$ and
the second set implies $\cE'$.

Notice that the events we are considering are increasing
events.
We can  use the van den Berg-Kesten inequality
to bound r.h.s. of \eqref{vbk} by
\begin{equation}
 \label{bound1}
  \prod_{h=0}^{r-1}
  \P^{d-1}_q \left(  \EE{\ux_{h+1}}{\ux_h}{d-1}{n} \right)
\end{equation}

{\bf Remark:}
In fact, to get the bound  \eqref{bound1} we 
use an inequality which is simpler than 
the van den Berg-Kesten inequality and that can be proved as 
follows (in the case of two events): 
$$\displaylines{
  \P^d_p 
   \left(  
    \left\{ \EEa{x}{y}{\G} \right\}
     \cap
    \left\{ \EEa{w}{z}{\G} \right\}
     \cap
    \left\{ \EEa{x}{w}{\G} \right\}^c
   \right)\cr
=
\sum_{\cC \subset \G \atop \{x,y\}\in \cC}
  \P^{d}_p \tonda{\cC \text{ is a } \G\text{-cluster }   }
  \P^{d}_p 
   \tonda{  
    \big\{ \EEa{w}{z}{\G \setminus \tonda{\cC \cup \partial \cC}}\big\}
    | \;
    \cC \text{ is a } \G\text{-cluster } }.
 \label{mia1}}
$$
However, the event $\{ \EEa{w}{z}{\G'}\}$ does not depend on the
configuration outside $\G'$; moreover, its probability is non decreasing 
with the set $\G'$.
Thus, we can bound the second 
term of the product in the above sum
by $\P^{d}_p \tonda{\EEa{w}{z}{\G}}$
and  the whole sum by 
$
  \P^d_p 
   \left(  
    \left\{ \EEa{x}{y}{\G} \right\}
   \right)
  \P^d_p 
   \left(  
     \left\{ \EEa{w}{z}{\G} \right\}
   \right)
$.
%A simple induction procedure allows
%to prove 
The analogous result
for a finite number of connections
is proved by induction.

We use \eqref{bound1} 
to bound \eqref{vbk}
\begin{equation}
  \leq
  \sum_{r \geq j-i} \ 
  \sum_{
    \begin{subarray}{c}
      \ux_0,\ldots,\ux_r \ s.t. \\
      \norma{\ux_{h+1}-\ux_{h}} \leq n
    \end{subarray}}
  2^r \ 
  \prod_{h=1}^H
  \P^{d-1}_q \left(  \EE{\ux_{h+1}}{\ux_h}{d-1}{n} \right),
\label{eij}
\end{equation}
where 
the factor $2^r$ comes from the number
of choices for the sequence of slices
with $R=r$.
Let $\r_h:=\norma{\ux_h - \ux_{h-1}}$ be the distance
between consecutive points in the path.
Once chosen the point $\ux_{h-1}$ 
on the slice $\slice{i_{h-1}}$, there
are 
$$
|\LL{d-1}{2\r_h+1} \setminus \LL{d-1}{2\r_h-1}|=
(2\r_h+1)^{d-1}-(2\r_h - 1)^{d-1} 
\leq 
C  \r_h^{d-2}
$$
ways to choose the point $\ux_{h}$ at a distance
 $\r_h$ from $\ux_{h-1}$.


In the case $\ell=3$, we  use
\eqref{hpr22} and bound r.h.s. of \eqref{eij} by
$$
 \P_p^{d,3} \tonda{\cE(i,j)}
\leq
 m^{d-1}
  \sum_{r \geq j-i} \ 
  \left(
    \sum_{\r=1}^n
    2 C \r^{d-2} 
 \tonda{C_1 \r^{d-2} q }^{\frac{\r}{2}}
  \right)^{r}
$$
For $\ell=3$ we have 
$n=\f (\dl) p^{- \frac{\scriptstyle1}{\scriptstyle d-2}}$.
We estimate the inner sum of the above term:
\begin{eqnarray*}
   \sum_{\r=1}^n
    2 C \r^{d-2} 
 \tonda{C_1 \r^{d-2} q }^{\frac{\r}{2}}
=
   \sum_{\r=1}^8
   2 C \r^{d-2} 
 \tonda{C_1 \r^{d-2} q }^{\frac{\r}{2}}
+
   \sum_{\r=9}^n
    2 C \r^{d-2} 
 \tonda{C_1 \r^{d-2} q }^{\frac{\r}{2}} \\
\le
2 C 8^{d-2} \tonda{C_1 8^{d-2} q}^{\fracscript{1}{2}}
+ 
2 C n^{d-1} \max_{9 \le \r \le n} \tonda{C_1 \r^{d-2} q}^{\fracscript{\r}{2}}.
\end{eqnarray*}
Let $f(\r):= \tonda{C_1 \r^{d-2} q}^{\fracscript{\r}{2}}$.
For $\f (\dl)$ small enough $f(\r)$ is decreasing on
$[9,n]$, whence
\begin{eqnarray*}
   \sum_{\r=1}^n
    2 C \r^{d-2} 
 \tonda{C_1 \r^{d-2} q }^{\frac{\r}{2}}
\le & \\
  2 C 8^{d-2} \tonda{C_1 8^{d-2} q}^{\fracscript{1}{2}}
  + &
  2 C \tonda{\f (\dl) p^{ - \frac{\scriptstyle1}{\scriptstyle d-2}}}^{d-1}
  \tonda{C_1 9^{d-2} q}^{\fracscript{9}{2}}
\le
  C_2 \sqrt q 
\end{eqnarray*}
for some $C_2$ depending on $\f(\dl)$.
For $p$ small enough so that $C_2 \sqrt q \le \frac{1}{2}$,
\begin{equation}
\P_p^{d,3} \tonda{\cE(i,j)}
\leq
2 m^{d-1}
\tonda{C_2 \sqrt {2p}}^{j-i}
 \leq
   m^{d-1}
   p^{\cc (i-j)}.
\label{l=3}
\end{equation}

In the case $\ell >3$, we can use the 
inductive hypothesis.
For sufficiently small $p$,
r.h.s of \eqref{eij} can be bounded by
\begin{equation}
  m^{d-1}
  \sum_{r \geq j-i} \ 
  \sum_{\r_1,\ldots,\r_r  \leq n}
  2^r \ 
  \prod_{h=0}^{r-1} \ 
  C \r_h^{d-2}
  p^{\cc \r_h}
=
  m^{d-1}
  \sum_{r \geq j-i} \ 
  \left(
    \sum_{\r=1}^n
    C' \r^{d-2}
    p^{\cc \r}
  \right)^r
%  m^{d-1}
%  \sum_{r \geq j-i} \ 
%  \left(
%    \sum_{\r=1}^n
%    C' \r^{d-2}
%    p^{\cc_1 \r}
%  \right)^r
\label{eij2}
\end{equation}
Since, for sufficiently small $p$, 
$\r^{d-2}  p^{\cc \r}$ is decreasing with $\r$
we can get the bound:
\begin{equation}
 \sum_{\r=1}^n
  C' \r^{d-2}
  p^{\cc \r}
\le
 C' p^{\cc} \tonda{1+ \int_0^\infty (\r +1)^{d-2} p^{\cc \r} \text{d} \r}
\le 
 p^{\cc_1},
\label{somma}
\end{equation}
where $\cc_1$ is a positive constant smaller than $\cc$.
%Let 
%$S(t):=\sum_{\r=1}^t    2 \r^{d-1} e^{\cc \r} $.
%$$
%S(t+1)=S(t)+ 2 (t+1)^{d-1} e^{-\cc \r}=
%2 e^{- \cc} + \sum_{\r=1}^t    2 (\r+1)^{d-1} e^{- \cc (\r+1)}
%\leq
%$$
%$$
%2 e^{- \cc}(1 + S(t)).
%$$
%Hence, we get 
%\begin{equation}
%  S(t) \leq \frac{2 e^{- \cc}
%%-  (t+1)^{d-1} e^{-\cc (\r-1)}
%  }{1-2 e^{- \cc}} < \frac{1}{2} e^{-c}
%\label{somma}
%\end{equation}
%if $e^{- \cc} < \frac{1}{2} e{-c}$.
By putting \eqref{somma} into 
\eqref{eij2}, we get
\begin{equation*}
  \P^d_p \left( \cE(i,j) \right) \leq
  m^{d-1}
  \sum_{r \geq j-i} \  
  p^{\cc_1 r}
\le
  m^{d-1} p^{\cc_1 (j-i)},
%\label{eij3}
\end{equation*}
formally, the same bound given by \eqref{l=3}
for the case $\ell=3$.


For $\ell \ge 3$, 
coming back to \eqref{2}, we get
$$\displaylines{
  \P^d_p \left( \left\{ \EE{x}{y}{d}{m} \right\} \cap 
    \left\{ M=k \right\} \cap 
    \left\{ I_1=i_1, \ldots,  I_k=i_k \right\} \right) 
 \,\leq\,\hfill\cr
\left( m^{d-1} p^{\cc_1 n} \right)^k
 \left( m^{k(d-1)} p^{\cc_2(b-a)} \right)\,
=\,
 \left( m^{2(d-1)} p^{\cc_1 n}  \right)^k
 \left( p^{\cc_2(b-a)} \right)
\,\le\,
  \left( p^{\cc_3}\right)^k
  \left( p^{\cc_2 (b-a)} \right),  
}$$
where, in the last inequality we used the definitions
of $n$ and $m$ and where $\cc_2$, $\cc_3$
are positive constants.
Finally, by plugging this inequality in
\eqref{1}, we get
$$
  \P^d_p \left( \EE{x}{y}{d}{m} \right) 
 \leq
  d m^2
  \sum_{u=0}^{m} 
   p^{\cc_4 u}
 \leq
   p^{\cc \norma{x-y}} 
$$
which is the desired estimate.

\begin{thebibliography}{99}
%\bibitem{[AA]}
%J. Adler, A. Aharony (1988).
%Diffusion percolation: I. Infinite time limit and bootstrap 
%percolation.
%{\sl J. Phys. A: Math. Gen.} {\bf 21}, 1387.

\bibitem[Ad]{[Ad]}
J. Adler (1991).
Bootstrap percolation. 
{\sl Physica A} {\bf 171}, 453-470. 

%\bibitem{[ASA]}
%J. Adler, D. Stauffer, A. Aharony (1989).
%Comparison of bootstrap percolation models.
%{\sl J. Phys. A: Math. Gen.} {\bf 22}, L297.

  
\bibitem[ADE]{[ADE]}
J. Adler, J.A.M.S. Duarte, A.C.D. van Enter (1990).
Finite--size effects for some bootstrap percolation models.
{\sl J. Statist. Phys.} {\bf 60}, 323--32.
\bibitem[AL]{[AL]}
M. Aizenman, J.L. Lebowitz (1988).
Metastability effects in bootstrap percolation.
{\sl J. Phys. A: Math. Gen.} {\bf 21}, 3801.

%\bibitem{[tutti]}
%N.S. Branco, R.R. Dos Santos, S.L.A. de Queiroz,
%{\sl J. Phys. C} {\bf 17}, L373 (1984);
%M.A. Khan, H. Gould, J. Chalupa, 
%{\sl J. Phys. C} {\bf 18}, L233 (1985);
%N.S. Branco, S.L.A. de Queiroz, R.R. Dos Santos, 
%{\sl J. Phys. C} {\bf 19}, 1909 (1986).

\bibitem[CeCi] {[CeCi]}
R. Cerf, E.N.M. Cirillo (1999)
Finite size scaling in three--dimensional bootstrap percolation
{\sl Ann. Probab.} {\bf 27}, No.4, 1837-1850 

%\bibitem{[CLR]}
%J. Chalupa, P.L. Leath, G.R. Reich (1979).
%Bootstrap percolation on a Bethe lattice. 
%{\sl J. Phys. C: Solid State Physics} {\bf 12}, L31.

\bibitem[vE]{[vE]}
A.C.D. van Enter (1987).
Proof of Straley's argument for Bootstrap Percolation.
{\sl J. Statist. Phys.} {\bf 48}, 943.




%\bibitem{[EAD2]}
%A.C.D. van Enter, J. Adler, J.A.M.S. Duarte (1991).
%Addendum: Finite--size effects for some bootstrap percolation models.
%{\sl J. Statist. Phys.} {\bf 62}, 505.

\bibitem[G]{G}
G. Grimmett (1999)
Percolation. 2nd ed. (English)
Berlin: Springer.

%\bibitem{[Gr]}
%D. Griffeath (1988).
%Cyclic random competition: a case history in experimental mathematics.
%{\sl Notices of the American Mathematical Society} {\bf 35}, 1472.

%\bibitem{[KL]}
%P.M. Kogut, P.L. Leath (1981).
%{\sl J. Phys. C: Solid State Physics} {\bf 14}, 3187.

%\bibitem{[LZ]}
%R. Le Normand, C. Zarcone (1984).
%``Kinetics of Aggregation and Gelation", eds. F. Family and D.P. Landau  
%(Elsevier, Amsterdam).

\bibitem[M]{[M]}
T.S. Mountford (1995).
Critical length for semi--oriented bootstrap percolation.
{\sl Stochastic Process. Appl.} {\bf 56}, 185--205.


%\bibitem{[N]}
%J. von Neumann (1966).
%Theory of self--reproducing automata.
%Univ. of Illinois Press, Urbana.

%\bibitem{[S1]}
%R.H. Schonmann (1990).
%Critical Points of two--dimensional bootstrap 
%percolation--like cellular
%automata.
%{\sl J. Statist. Phys.} {\bf 58}, 1239.

%\bibitem{[S2]}
%R.H. Schonmann (1990).
%Finite size scaling behavior of a biased majority rule cellular
%automaton.
%{\sl Phys. A} {\bf 167}, 619--627.

\bibitem[S]{[S]}
R.H. Schonmann (1992).
On the behavior of some cellular automata related to bootstrap
percolation.
{\sl Ann. Probab.} {\bf 20}, 174.

%\bibitem{[TM]}
%T. Toffoli, N. Margolus (1987).
%Cellular automata machines. A new environment for modeling.
%MIT Press.

%\bibitem{[U]}
%S. Ulam (1950).
%Random processes and transformations.
%Proc. Internat. Congr. Math., 264--275.

%\bibitem{[V]}
%G.Y. Vichniac (1984).
%Simulating physics with cellular automata.
%{\sl Phys. D} {\bf 10}, 96.

%\bibitem{[W]}
%S. Wolfram (1983).
%Statistical mechanics of cellular automata.
%{\sl Rev. Modern Phys.} {\bf 55}, 601 (1983).
%S. Wolfram (1986).
%Theory and applications of cellular automata.
%World Scientific, Singapore.

\end{thebibliography}

\end{document}
---------------0107060831144--
