\documentstyle[12pt,leqno]{article}
\topmargin -0.8in
\textheight 9.7in
\oddsidemargin -0.2in
\textwidth 6.8in
\parindent 0in
\parskip 1em
\def\DITEM{\item[\(\bullet\)]}
\def\LL#1{\label{#1}%\hfill\quad\fbox{\fbox{\small\bf #1}}\qquad\qquad
}
\def\RF#1{\ref{#1}%\quad\fbox{\small\bf #1}\quad
}
\def\RFL#1#2#3{{\bf (#2\RF{#1}\(_{#3}\))}}
\newcounter{NSEC}\newcounter{NSUSEC}
\def\SEC#1{\vskip 0.3in {\Large\bf\setcounter{NSUSEC}{0}\refstepcounter{NSEC}
\arabic{NSEC}. #1}\vskip 0.1in}
\def\SUSEC#1{\vskip 0.2in {\large\bf\refstepcounter{NSUSEC}
\arabic{NSEC}.\arabic{NSUSEC}. #1}\vskip 0in}
\def\Tpoint{\sf\hskip -0.4em. }
\newtheorem{Definition}{Definition}
\def\DEFINITION#1{\begin{Definition}\Tpoint #1\end{Definition}}
\newtheorem{Theorem}{Theorem}
\def\THEOREM#1{\begin{Theorem}\Tpoint #1\end{Theorem}}
\newtheorem{Lemma}{Lemma}
\def\LEMMA#1{\begin{Lemma}\Tpoint #1\end{Lemma}}
\newtheorem{Note}{Note}
\def\NOTE#1{\begin{Note}\Tpoint #1\end{Note}}
\def\FORM#1{\begin{equation}#1\end{equation}}
\def\MB#1{\hbox{\kern0.50ex}\( #1 \)\hbox{\kern0.50ex}}
\def\ML#1{\hbox{\kern0.50ex}\( #1 \)\hbox{\kern0.01ex}}
\def\MR#1{\hbox{\kern0.01ex}\( #1 \)\hbox{\kern0.50ex}}
\def\BR{\char'051~}
\newcounter{NASS}
\def\SEP{\topsep=0em\parskip=0em\parsep=0em\itemsep=0em}
\newenvironment{ASS}%
{\begin{list}%
{\hbox{\kern5ex}\arabic{NASS}\BR\hbox{\kern0.5ex}}%
{\usecounter{NASS}\labelwidth=7ex \SEP }}%
{\end{list}}
\newenvironment{LIST}[2]%
{\begin{list}%
{\hbox{\kern5ex}{\bf (#1\arabic{NASS}\(_{#2}\))}\hbox{\kern0.5ex}}%
{\usecounter{NASS}\labelwidth=7ex \SEP }\sf}%
{\end{list}}
\def\empset{\hskip -0.1em \raisebox{-0.3ex}{
\begin{picture}(10,10)(0,0)
\put(0, 0){\line(1, 1){10}}
\put(5, 5){\circle{8}}
\end{picture}~}}
\def\HB#1{\hbox{\quad#1\quad}}
\def\TERM#1{{\sc #1}}
\def\SET#1{\{#1\}}
\def\PROOF{\par{\bf Proof: }}
\def\IMPLIES{~\Longrightarrow~}
\def\TRUSS#1{\langle #1 \rangle}
\def\QED{~~\raisebox{-0.3ex}{$\Box$}~~}
\def\SEG#1{[1,#1]}
\def\const{{\rm const}}
\def\ORIGIN{{\cal O}}
\def\MEM{\hbox{\sf mem}}
\def\TRANS{\hbox{\bf trans}}
\def\R{{\bf R}}
\def\Z{{\bf Z}}
\def\EX{{\bf E}}
\def\ALMOST{\hbox{\sc almostmax}}
\def\ARITHM{\hbox{\sc arithm}}
\def\ROUND{\hbox{\sc round}}
\def\Space{\hbox{\bf Space}}
\def\Time{\hbox{\bf Time}}
\def\Volume{\hbox{\bf Volume}}
\def\V{\hbox{\bf V}}
\def\Carrier{\hbox{\bf Carrier}}
\def\SIZE{{\hskip 0.1em\sf size\hskip 0.1em}}
\def\INITIAL{{init}}
\def\INNER{{inner}}
\def\TR{{\bf TR}}
\def\NEIGHBOR{{\bf N}}
\def\DRAG{\hbox{\sf DRAG}}
\def\VETO{\hbox{\sf VETO}}
\def\drag{{drag}}
\def\veto{{veto}}
\def\TOP{\hbox{\sf TOP}}
\def\IND{\hbox{\sf IND}}
\def\LIFETIME{\hbox{\sf lifetime}}
\def\STAIRS{\hbox{\bf Stairs\hskip 0.1em}}
\def\STEP{\hbox{\sf STEP}}
\def\NN{n}
\def\NL{r}
\def\NGR{\nabla}
\def\RIGHTPART#1{\cases{\theta+(C\theta)^2 &if \MB{k=1},\cr
(C\theta)^{k+1} &if \MB{k>1}#1}}
\def\SPANTREE{\hbox{\sf span-tree}}
\def\SPANTRUSS{\hbox{\sf span-truss}}
\def\HUB{v}
\def\RUB{k}
\def\hub{\hbox{\bf hub}}
\def\rub{\hbox{\bf rub}}
\def\CONV{\hbox{\sc conv}}
\def\RAY{\hbox{\sc ray}}
\def\UNION{\hbox{\sc union}}
\def\RANGE{\hbox{\sc range}}
\def\ROOT{\hbox{\sc root}}
\def\BUSH{\hbox{\sc bush}}
\def\TRANSIT{{tran}}
\def\PROPER{{prop}}
\def\VEC{\hbox{\sc vec}}
\def\VER{\hbox{\sc ver}}
\def\ver{\VER_{span}}
\def\ARROW{\hbox{\sc arrow}}
\def\BOOST{\hbox{\sc boost}}
\def\TYPE{\hbox{\sc type}}
\def\NORM{\hbox{\sf norm}}
\def\DIST{\hbox{\sf dist}}
\def\DIAM{\hbox{\sf diam}}
\def\SPAN{\hbox{\sf span}}
\def\ersatz{\hbox{\sc ersatz}}
\def\PIT{\hbox{\sc pit}}
\def\fin{\hbox{\sf fin}}
\def\inf{\hbox{\sf inf}}
\def\INF{\hbox{\sf INF}}
\def\TOWER{\hbox{\sf Tower}}
\def\FLOOR{\hbox{\sf Floor\hskip 0.1em}}
\def\alfa{\alpha}
\def\gama{\gamma}
\def\epsi{\varepsilon}
\def\delt{\delta}
\def\A{{\cal A}}
\def\B{{\cal B}}
\def\C{{\cal C}}
\def\D{{\cal D}}
\def\E{{\cal E}}
\def\F{{\cal F}}
\def\M{{\cal M}}
\def\Q{{\cal Q}}
\def\T{{\cal T}}
\def\U{{\cal U}}
\begin{document}\baselineskip=1.5em %2.5em
\centerline{\fbox{P R E P R I N T}}
\begin{center}
\vskip 1em
{\LARGE More on Critical Phenomena in Growth Systems}
\vskip 1em
{\Large Andrei Toom}
\vskip 0.1em
{\large Incarnate Word College}\\
4301 Broadway, San Antonio, Texas 78209
\vskip 1em
\end{center}
\begin{abstract}
This paper treats of interacting infinite or finite systems
whose components' states are in the set \MB{\SET{0,1,2,\ldots}}.
Components interact with each other in a local deterministic way,
in addition to which every component's state grows by one
with a constant probability \MB{\theta} at every moment of the discrete time.
Theorem 1 states conditions under which an infinite deterministic
(\MB{\theta=0}) system is an `eroder', that is every initial condition with
a finite set of positive components turns into `all zeroes' after a finite time.
Theorems 2,3,4 are about probabilistic systems with initial states
`all zeroes'. Our main question about infinite systems is whether the average
value of components tends to infinity or remains bounded as \MB{t\to\infty}.
The analogous question about finite systems is how long the system's
average remains less than a constant: this time may be bounded or
tend to infinity as the system' size tends to infinity.
Both in the infinite and finite cases sufficient conditions for
the latter ways of behavior are given here, which are also necessary under
natural assumptions.
\end{abstract}
\SEC{Introduction}
This paper's approach is similar to that of \cite{Toom-92}
(and we refer to \cite{Toom-92} to save space),
but the main results are stronger now.
Note that some notations of our paper are different from those of
\cite{Toom-92} and some terms (e.g. polar) are given new definitions here.
\MB{\R} stands for the set of real numbers,
\MB{\R_+} is the set of non-negative real numbers,
\MB{\Z} is the set of integers,
\MB{\Z_+} is the set of non-negative integers,
\MB{\Z_{++}} is the set of positive integers,
\MB{\SEG{k}} is the segment \MB{ \SET{i\in\Z~:~1\leq i\leq k} }, and
\MB{\Z_{\SIZE}} is the ring of residues modulo \TERM{size}.
As usual \MB{[x]} stands for the greatest integer that does not exceed
a given real \MB{x}. Also let \MB{[x]^+} stand for \MB{\max([x],0)}
and \MB{\ROUND(x)=[x+0.5]} stand for the nearest integer.
Expectation is denoted \MB{\EX (\cdot)}.
Let us compare random processes with the state space \ML{\R_+^{\Z^2}}.
To specify a state means to assign a real number
\MB{x(i,j) \geq 0} to every \ML{(i,j) \in \Z^2}.
Take some initial state and assume that at every moment of the
discrete time every \MB{x(i,j)} undergoes the following two steps:
\begin{description}%\labelwidth=2in
\item[Step 1 : \/ ] \MB{x(i,j)} takes the value of some deterministic
\TERM{transition function} \MB{\TRANS(\cdot)} of its and its neighbors'
previous states.
\item[Step 2 : \/ ] \MB{x(i,j)} is incremented by 1 with probability
\MB{\theta} independently of the others' increments and of the prehistory.
\end{description}
%The only difference between processes in question is in
%the value of \MB{\theta} and in
%the transition function \MB{\TRANS(\cdot)} used in {\bf Step 1}.
If \MB{\theta=0}, our processes are deterministic; these are the subject
of our Theorem \RF{T-det} which gives a sufficient and necessary condition
under which any initial state with a finite set of non-zero components
turns into `all zeroes' after several steps.
Our Theorems 2-4 refer to random processes with initial conditions `all zeroes'.
In this case our systems are space-uniform, so expectations of
\MB{x(i,j)} at time \MB{t} are the same for all
\MB{(i,j) \in \Z^2} and we may call them \ML{\EX_\theta(t)}.
We are interested in the behavior of \MB{\EX_\theta(t)} as \ML{t\to\infty}.
Theorem 1 of \cite{Toom-92} showed that in a fairly general case
\MB{\EX_\theta(t)} tends to infinity provided \MB{\theta} is close enough to 1.
It is very easy to present transition functions for which
\MB{\EX_\theta(t)} tends to infinity with any \ML{\theta>0},
for example if {\bf Step 1} does not change the value of \MB{x(i,j)} at all,
or \MB{\TRANS(\cdot)} equals the arithmetical mean of its arguments.
However, in the process in which
\FORM{
\TRANS(\cdot)=\ROUND(\ARITHM(x(i,j),~x(i+1,j),~x(i,j+1))), \LL{round-NEC}
}
where \MB{\ARITHM(\cdot)} means the arithmetical mean,
\MB{\EX_\theta(t)} remains bounded by a constant,
provided \MB{\theta} is small enough. This follows from our Theorem \RF{T-inf}.
(In fact, this process takes values in \ML{\Z_+^{\Z^2}}.)
Note that the function (\RF{round-NEC})
does not favor smaller or greater values since
$$
\forall~x,y,z,~a\in\Z~:~\ROUND(\ARITHM(a-x,a-y,a-z)=a-\ROUND(\ARITHM(x,y,z)).
$$
Our Theorem \RF{T-inf} can be applied also to the following function
which may seem to favor greater values:
\FORM{
\TRANS(\cdot)=\ALMOST(x(i,j),~x(i+1,j),~x(i,j+1))), \LL{ALMOST}
}
where
$$
\ALMOST(x,y,z)=\cases{\max\SET{x,y,z} &if at least two among \MB{x,y,z}
equal \MB{\max(x,y,z)},\cr
\max\SET{x,y,z}-1 &otherwise.}
$$
Thus, for some functions \MB{\TRANS(\cdot)}, including (\RF{round-NEC})
and (\RF{ALMOST}), there is a critical value of \MB{\theta},
which separates two modes of behavior --
with bounded and growing \ML{\EX_\theta(t)}.
Theorem \RF{T-fin} proves the analogous phenomenon for finite systems
in the same assumptions about the deterministic interaction.
Of course, in finite systems \MB{\EX_\theta(t)} can not remain
bounded forever: it remains bounded during time which grows
exponentially in the system's size.
Geometrical positions of neighbors are essential.
For example, it is fairly evident that the processes which apply the
same functions \MB{\ROUND(\ARITHM(\cdot))} and \MB{\ALMOST(\cdot)} to
\MB{x(i,j),~x(i+1,j),~x(i-1,j)}, have \MB{\EX_\theta(t)\to\infty}
for any \ML{\theta >0}. Theorem \RF{T-back} generalizes this fact and
states the class of transition functions with which the key condition
(\RF{sigma=O}) of Theorems \RF{T-inf} and \RF{T-fin} is not only sufficient,
but also necessary for the statements of these theorems to be true.
\SEC{Definitions and Formulations \LL{S-def+form}}
Cardinality of a finite set \MB{S} is denoted \ML{|S|}.
For any real function \MB{F} on any non-empty set \MB{S} we denote:
\begin{eqnarray*}
& Max(F,S)=\max\{ F(e)~:~e \in S \}, \qquad
Min(F,S)=\min\{ F(e)~:~e \in S \}, &\\
& Gap(F,S)=Max(F,S)-Min(F,S). &
\end{eqnarray*}
A \TERM{family} means a set whose elements are sets.
A family \MB{F} given, \MB{\UNION(F)}
stands for the union of elements of \MB{F}.
Say that any two elements of a set are \TERM{connected} by this set.
Call a family \MB{F} \TERM{connected} if for any \MB{a,b \in\UNION(F)}
there is a sequence \MB{c_0=a,~c_1,~\ldots,~c_j=b} in which every
two next terms are connected by some element of \MB{F}.
Let \MB{\Space=\Z^{\dim}} in the infinite
and \MB{\Space=\Z^{\dim}_\SIZE} in the finite case.
Let \MB{\Time= \{t \in \Z~:~t \geq -\MEM \} },
where \MB{\MEM\in\Z_{++}} is called \TERM{memory}, and
$$
\V=\Volume=\Space \times \Time=\SET{(s,t): s \in \Space,~ t \in \Time}.
$$
Elements of \MB{\V} are called \TERM{points} and
subsets of \MB{\V} are called \TERM{point-sets}.
If \ML{v=(s,t) \in \V}, then \MB{s(v)=s} and \MB{t(v)=t}.
Points with \MB{t < 0} are called \TERM{initial},
those with \MB{t \geq 0} are called \TERM{inner}.
\MB{\V_\INITIAL} and \MB{\V_\INNER} stand for the initial and inner sets,
i.e. sets of initial and inner points.
Every inner point \MB{(s,t)} has \MB{\NN} \TERM{neighbors}
$$
\NEIGHBOR_i(s,t)=(s-\Delta s_i,~t-\Delta t_i),~~i\in\SEG{\NN},
$$
where the sequence of \TERM{neighbor vectors}
\FORM{
\Delta=((\Delta s_1,~\Delta t_1),\ldots,(\Delta s_\NN,\Delta t_\NN))
\LL{n-vectors}
}
is one and the same for all inner points and
\MB{1 \leq \Delta t_i \leq \MEM} for all \MB{i\in\SEG{\NN}}.
For every inner point \MB{v} its neighborhood \MB{\NEIGHBOR(v)} is
the set of its neighbors. Initial points have empty neighborhoods.
To represent the system of neighborhoods,
we shall use the directed graph \MB{V} which has \MB{\V} as its
set of vertices, and edges that go to every point from its neighbors.
We shall also use the non-directed graph \MB{V'} with \MB{\V} as
its set of vertices, in which two vertices are connected if one is
the the other's neighbor or they are different neighbors of one point.
Every point \MB{v} has one and the same set
\MB{X_v \equiv X_0=\Z_+} of possible states.
To every point \MB{(s,t) \in \V} there corresponds a variable
\MB{x(s,t)\in X_0} which represent the state of this point,
that is the state of component \MB{s} at time \ML{t}.
The set \MB{X=X_0^{\V}} is the configuration space
whose elements \MB{x} are called \TERM{configurations}.
Generally, to any subvolume \MB{S \subseteq \V} there corresponds
its configuration space \MB{X_S=X_0^S} whose elements \MB{x(S)}
are called configurations on \MB{S}.
Given two configurations \MB{x} and \MB{y} on a subvolume \MB{S},
\MB{x~\preceq~y} means that \MB{x(v)~\leq~y(v)} for all \MB{v\in S}.
For any configuration \MB{x} its \TERM{carrier} \MB{\Carrier(x)}
stands for the set of those points \MB{v} where \MB{x(v)>0}.
Call a configuration \TERM{finitary} if its carrier is finite.
For all inner points one and the same transition function is given
\FORM{
\TRANS~:~X_{\NEIGHBOR(v)} \mapsto
X_v,\HB{where}X_{\NEIGHBOR(v)}=X_0^\NN\HB{and}X_v=X_0. \LL{trans}
}
Since our systems are uniform (i.e. neighbor vectors and the
transition function are the same for all inner points), it is
sufficient to speak about the neighborhood and transition function
of the origin \MB{\ORIGIN} when imposing conditions.
Throughout the paper we assume
\FORM{
\forall~x~: Min(x,~\NEIGHBOR(\ORIGIN)) ~\leq~
\TRANS(x(\NEIGHBOR(\ORIGIN))) ~\leq~
Max(x,~\NEIGHBOR(\ORIGIN)). \LL{m-trans-m}
}
Sometimes we also assume monotony
\FORM{
x \preceq y \IMPLIES
\TRANS(x(\NEIGHBOR(\ORIGIN)) \leq \TRANS(y(\NEIGHBOR(\ORIGIN)), \LL{monotony}
}
and translation-invariance in the set of states
\FORM{\hskip 0.3in
\forall~a\in\Z~:~(\forall~v\in\NEIGHBOR(\ORIGIN)~:~x(v)=y(v)+a) \IMPLIES
\TRANS(x(\NEIGHBOR(\ORIGIN)))=\TRANS(y(\NEIGHBOR(\ORIGIN)))+a. \LL{+a}
}
\NOTE{
Given (\RF{monotony}), (\RF{+a}) and
$$
(\forall~v\in\NEIGHBOR(\ORIGIN)~:~x(v)=0) \IMPLIES \TRANS(x)=0.
$$
Then (\RF{m-trans-m}) follows. \LL{N-monot+a-}
}
All of these assumptions seem not to be very restrictive;
both our examples (\RF{round-NEC}) and (\RF{ALMOST}) satisfy them.
\DEFINITION{
A non-empty subset \MB{S \subseteq \NEIGHBOR(\ORIGIN)} is called
a \TERM{drag-set} (of \MB{\ORIGIN}) if for all \MB{x} \LL{D-drag}
$$
\TRANS(x(\NEIGHBOR(\ORIGIN))) = Max(x,\NEIGHBOR(\ORIGIN))
\IMPLIES Max(x,S) = Max(x,\NEIGHBOR(\ORIGIN)).
$$
}
Drag-sets of any inner point \MB{v} are drag-sets shifted by \ML{v}.
Let \MB{\DRAG(\Delta,\TRANS)} stand for the family of drag-sets.
Since \MB{\NEIGHBOR(\ORIGIN)} is always a drag-set, this family is
non-empty, whence our next definition makes sense.
Since our volume \MB{\V} is a subset of the \ML{(\dim+1)}-dimensional
discrete space \ML{\Z^{\dim+1}}, we can embed it into
a continuous space \ML{R^{\dim+1}} with the same origin \ML{\ORIGIN}.
Let \MB{\CONV(S)} stand for the convex hull of any \ML{S \subset R^{\dim+1}}.
For any number \MB{k} and any set \MB{S \subset R^{\dim+1}} we define:
$$
k\cdot S=\{k\cdot v~:~v\in S\}, \qquad \RAY(S)=\cup\{k\cdot S~:~k \geq 0\}.
$$
\DEFINITION{
For any sequence (\RF{n-vectors}) of neighbor vectors
and any transition function (\RF{trans}) denote \LL{D-sigma}
$$
\sigma_\drag(\Delta,\TRANS)=
\cap\{\RAY(\CONV(S))~:~S\in\DRAG(\Delta,\TRANS)\}.
$$
}
The following condition plays the key role in our paper:
\FORM{
\sigma_\drag(\Delta,\TRANS)=\{ \ORIGIN \}. \LL{sigma=O}
}
In the deterministic case for every initial condition
\MB{y} the corresponding \TERM{trajectory}
\MB{\TR(y)=x \in X} is defined by
\FORM{
x(v)=\cases{y(v) &if $t(v) < 0$, \cr
\TRANS(x(\NEIGHBOR(v))) &if $t(v) \geq 0$.} \LL{def-det}
}
Our first theorem generalizes some results of \cite{Toom-80} and shows
relevance of the condition (\RF{sigma=O}) for the deterministic case.
Call the deterministic map (\RF{def-det}) an \TERM{eroder} if for any
finitary initial condition the resulting trajectory is also finitary.
\THEOREM{
Consider the infinite case.
Assume (\RF{m-trans-m}), (\RF{monotony}) and (\RF{+a}).
Then the map (\RF{def-det}) is an eroder
if and only if (\RF{sigma=O}) holds. \LL{T-det}
}
Theorems 2,3,4 are about \TERM{random processes},
i.e. normed measures on \MB{X} defined as follows.
Let us use (every time the same) mutually independent \TERM{hidden variables}
\MB{h(v)} for all inner points \ML{v}, everyone of which equals 1
with probability \MB{\theta} and 0 with probability \ML{1-\theta}.
Thus we have the hidden product-measure \MB{\eta} on the
configuration space \MB{H=\SET{0,1}^V} of the hidden variables.
To any sequence (\RF{n-vectors}) of neighbor vectors,
any transition function (\RF{trans}) and any value of \MB{\theta}
there corresponds a process, i.e. the normed measure on \MB{X}
induced by \MB{\eta} with the map from \MB{H} to \MB{X}
defined in the following inductive way:
$$
x(v)=\cases{0 &if $t(v) < 0$, \cr
\TRANS(x(\NEIGHBOR(v)))+h(v) &if $t(v) \geq 0$.}
$$
\THEOREM{
Consider the infinite case. Assume (\RF{m-trans-m}) and (\RF{sigma=O}).
Then there is such a constant \MB{C} that
for all inner \MB{v} and small enough \MB{\theta} \LL{T-inf}
\FORM{
Prob(x(v) \geq k) \leq \RIGHTPART{} \LL{prob-inf}
}
and\\
\FORM{
\EX (x(v)) = \theta + O(\theta^2). \LL{exp-inf}
}
}
\THEOREM{
Consider the finite case. Assume (\RF{m-trans-m}) and (\RF{sigma=O}).
Then for any \MB{T} there is such a constant \MB{C} that
for any \MB{s,~t \leq T^\SIZE}, any large enough \MB{\SIZE}
and any small enough \MB{\theta} \LL{T-fin}
\FORM{
Prob(x(s,t) \geq k)\leq\RIGHTPART{} \LL{prob-fin}
}
and
\FORM{
\EX(x(s,t))=\theta+O(\theta^2). \LL{exp-fin}
}
}
\THEOREM{
Consider both infinite and finite case.
Assume (\RF{m-trans-m}), (\RF{monotony}), (\RF{+a})
and negation of (\RF{sigma=O}).
Then there is such a constant \MB{C>0}
that \MB{\EX (x(s,t)) \geq C\cdot\theta\cdot t}
for all \MB{\theta} and \MB{(s,t) \in\V}. \LL{T-back}
}
Let us compare present results with those of \cite{Toom-92}.
The following are some definitions of \cite{Toom-92} in present notations.
A \TERM{veto-set} \MB{S} is such a subset of \MB{\NEIGHBOR(\ORIGIN)} that
\MB{\forall~x~:~\TRANS(x(\NEIGHBOR(\ORIGIN))) \leq Max(x,S)}. Let
\MB{\VETO(\Delta,\TRANS)} stands for the family of veto-sets and denote
$$
\sigma_\veto(\Delta,\TRANS)=\cap\{\RAY(\CONV(S))~:~S\in\VETO(\Delta,\TRANS)\}.
$$
It is evident that every veto-set is a drag-set, whence
\MB{\sigma_\drag(\Delta,\TRANS) \subseteq \sigma_\veto(\Delta,\TRANS)}.
Thus Theorems 2 and 3 of \cite{Toom-92} follow from
our Theorems \RF{T-inf} and \RF{T-fin}.
On the other hand, not every drag-set is a veto-set.
For example, in our processes (\RF{round-NEC}) and (\RF{ALMOST})
every inner point has three neighbors, every two of which form a drag-set,
but not a veto-set. Thus, in both examples
\MB{\sigma_\drag(\Delta,\TRANS)= \{\ORIGIN\}}, but
\MB{\sigma_\veto(\Delta,\TRANS)\neq\{\ORIGIN\}}.
So our Theorems \RF{T-inf},\RF{T-fin},\RF{T-back} can be applied
to these examples while Theorems 2 and 3 of \cite{Toom-92} can not.
However, if \MB{\TRANS(\cdot)} can be expressed through minima and maxima
of its arguments, every drag-set is a veto-set.
So Theorem 4 of \cite{Toom-92} follows from our Theorem \RF{T-back}.
\SEC{Preliminaries}
This section contains some facts and definitions which
are used more than once in the proofs of our theorems.
For any set \MB{S \subseteq \NEIGHBOR(\ORIGIN)}
define a state \MB{\IND_S \in X_{\NEIGHBOR(\ORIGIN)}} as follows:
$$
\forall~v\in\NEIGHBOR(\ORIGIN)~:~\IND_S(v)=\cases{0 &if \MB{v \in S},\cr
1 &otherwise.}
$$
\LEMMA{
Given (\RF{m-trans-m}), (\RF{monotony}) and (\RF{+a}).
Then a set \MB{S \subseteq \NEIGHBOR(\ORIGIN)} is a drag-set
if and only if \MB{\TRANS(\IND_S)=0}. \LL{L-drag}
}
\PROOF If \MB{S=\NEIGHBOR(\ORIGIN)}, then \MB{S} is evidently a drag-set
and \MB{\TRANS(\IND_S)=0} from (\RF{m-trans-m}).
Now let \MB{S \subset \NEIGHBOR(\ORIGIN)}.
Then \MB{Max(\IND_S,~\NEIGHBOR(\ORIGIN))=1}.
1) Assume \MB{\TRANS(\IND_S)=1}.
Then \MB{\TRANS(\IND_S)=Max(\IND_S,~\NEIGHBOR(\ORIGIN))},
while \MB{Max(\IND_S,~S)=0<1=Max(\IND_S,~\NEIGHBOR(\ORIGIN))}
whence \MB{S} is not a drag-set.
2) Now assume that \MB{S} is not a drag-set.
So there is such \MB{x \in X_{\NEIGHBOR(\ORIGIN)}} that
\MB{Max(x,S)From now on, whenever (\RF{sigma=O}) is given, we fix the number \MB{\NL}
and the \ML{\NL}-tuple \MB{L=(L_1,\ldots,L_\NL)} which satisfy assertions
of Lemma \RF{L-lin}.
Choose any norm \MB{\NORM(v)=\NORM(s,t)} in \MB{\R^{\dim+1}}
such that all the \MB{(\dim+1)} unit basis vectors have norm 1.
Define distance \MB{\DIST(v,w)=\NORM(v-w)}.
Let distance \MB{\DIST(S_1,S_2)} between two finite sets stand for
the minimal distance between a point of \MB{S_1} and a point of \ML{S_2}
and let \MB{\DIAM(S)} stand for the diameter of any set \ML{S},
that is the maximal distance between its points. Denote
\FORM{
\lambda=\max\{\NORM(\Delta s_i, \Delta t_i)~:~i\in\SEG{\NN}\} \HB{and}
\rho=\max\{ L_i(v)~:~i\in\SEG{\NL},~~\NORM(v)\leq 1\}. \LL{def-lambda-rho}
}
\SEC{Proof of Theorem \RF{T-det}}
Proof of Theorem \RF{T-det} consists of the following two lemmas.
For any finitary \MB{x} on a subvolume \MB{S \subseteq \V} denote
\MB{\TOP(x)=Max(x,S)}.
\LEMMA{
Consider the infinite case. Assume (\RF{m-trans-m}) and (\RF{sigma=O}).
Then for any finitary initial condition \MB{y} the resulting trajectory
\MB{\TR(y)} is also finitary and \LL{L-det-O}
$$
\DIAM(\Carrier(\TR(y))) ~\leq~
\const\cdot(\DIAM(\Carrier(y)) + \TOP(y)) + \const.
$$
}
\LEMMA{
Consider the infinite case.
Assume (\RF{m-trans-m}), (\RF{monotony}), (\RF{+a})
and negation of (\RF{sigma=O}).
Then for any \MB{T\in\Z_{++}} there is a finitary initial condition \MB{x}
such that for every \MB{t\in\Time} there is \MB{s_t} such that
\MB{y(s_t,t)=T} where \MB{y=\TR(x)}. \LL{L-det-non-O}
}
\SUSEC{Proof of Lemma \RF{L-det-O}}
>From uniformity we may assume
\FORM{
\exists~v\in\Carrier(y)~:~s(v)=0 \LL{s=0}
}
whence
$$
\forall~w\in\Carrier(y)~:~\NORM(w) \leq \DIAM(\Carrier(y))+\MEM.
$$
%\NOTE{
%From (\RF{m-trans-m})
%\MB{\TOP(\TR(y))=\TOP(y)} for any finitary initial \MB{y}. \LL{N-init}
%}
\NOTE{
For any finitary initial \MB{y} and \MB{T\in\Time} \LL{N-diam-T}
$$
\DIAM(\SET{ (s,t)\in\Carrier(\TR(y))~:~t~\leq~T})~\leq~
\DIAM(\Carrier(y))+2\cdot\lambda\cdot T.
$$
}
Call a configuration \MB{x \in X} \TERM{superior} if
\MB{x(v) ~\geq~ \TRANS(x(\NEIGHBOR(v)))} for all inner \MB{v}.
\NOTE{
Given (\RF{monotony}).
Given a trajectory \MB{x} and a superior \MB{y} such that
\MB{x(v)~\leq~y(v)} for all initial \MB{v}. Then \MB{x \preceq y}. \LL{N-x-y}
}
Choose some \MB{i \in\SEG{\NL}} and let \MB{L_i} stand for any
of the functions provided by Lemma \RF{L-lin}.
Given any infinite increasing sequence \MB{K}
of real numbers \MB{k_1~<~k_2~<~k_3~<~\ldots}, let \TERM{stairs}
stand for the following configuration \MB{\STAIRS_i(K)=x \in X}:
$$
\forall~v\in\V~:~x(v)=\cases{0 &if \MB{L_i(v) k_{j+1}-k_j \geq 2\cdot\lambda\cdot\rho.
$$
But this is impossible since
$$
L_i(u_2)-L_i(u_1)=L_i(u_2-u_1) \leq
\max\SET{L_i(w)~:~\NORM(w)\leq 2\cdot\lambda} \leq
2\cdot\lambda\cdot\rho.
$$
This contradiction proves (\RF{in-gap}).
Thus \MB{Gap(x,\NEIGHBOR(v))} is 0 or 1. Now note that
\FORM{
\TRANS(x(\NEIGHBOR(v)))=Min(x,\NEIGHBOR(v)) \LL{trans=min}
}
follows from (\RF{m-trans-m}) if \MB{Gap(x,\NEIGHBOR(v))=0}
and from Lemma \RF{L-drag} if \MB{Gap(x,\NEIGHBOR(v))=1}.
On the other hand, (\RF{lin-drag}) assures that the set
\MB{\SET{e\in\NEIGHBOR(v)~:~L_i(e) \leq L_i(v)}} is a drag-set,
whence this set is non-empty, whence \MB{Min(L_i,\NEIGHBOR(v)) \leq L_i(v)},
whence \MB{Min(x,\NEIGHBOR(v)) \leq x(v)}.
This and (\RF{trans=min}) prove our lemma \QED
\NOTE{
For any values of parameters \MB{C>0} and \MB{C_1,\ldots,C_\NL}
the configuration \MB{[C\cdot L_i(v)+C_i]^+} is a stairs.
This stairs satisfies (\RF{F-stairs}), provided \LL{N-[.]}
\FORM{
C \leq (2\cdot\lambda\cdot\rho)^{-1}. \LL{in-C}
}
}
Let \TERM{lifetime} of any configuration \MB{x}
stand for \MB{\max\{ t(v)~:~x(v)>0 \} }.
\LEMMA{
For any constants \MB{C>0} and \MB{C_1,\ldots,C_\NL} the configuration
\MB{ \min\{ [C\cdot L_i+C_i]^+ ~:~i\in\SEG{\NL} \} } has a finite
lifetime which does not exceed \MB{(C_1+\ldots+C_\NL)/C}. \LL{L-lifetime}
}
\PROOF Take any \MB{(s,t)} where \MB{y(s,t)>0}.
Then for all \MB{i\in\SEG{\NL}}
$$
[C\cdot L_i(s,t)+C_i]^+>0, \HB{whence}
[C\cdot L_i(s,t)+C_i]>0, \HB{whence}
L_i(s,t)>-C_i/C.
$$
Summing the last inequalities and using (\RF{lin-sum}) proves our lemma \QED
\LEMMA{
Take any finitary initial \MB{y} and assume (\RF{s=0}).
Take any \MB{i\in\SEG{\NL}} and denote \MB{x=[C\cdot L_i+C']^+}
where \MB{C>0} satisfies (\RF{in-C}) and \LL{L-y-x}
\FORM{
C'=\TOP(y)+C\cdot\rho\cdot(\DIAM(\Carrier(y)) + \MEM) + 1. \LL{def-C'}
}
Then \MB{\TR(y)~\leq~x}.
}
\PROOF First let us prove that \MB{y(v) \leq x(v)} for every initial \MB{v}.
This is evident if \MB{v\notin\Carrier(y)}.
Now let \MB{v \in\Carrier(y)}.
Then using (\RF{s=0})
\begin{eqnarray*}
x(v)~\geq~C\cdot L_i(v)+C'-1~\geq~C'-1-C\cdot\rho\cdot\NORM(v)&~\geq~& \\
C'-1-C\cdot\rho\cdot(\DIAM(Carrier(y))+\MEM)&~\geq~&\TOP(y)~\geq~y(v).
\end{eqnarray*}
Now to prove Lemma \RF{L-y-x} in general:
Note \RF{N-[.]} and Lemma \RF{L-stairs} assure that \MB{x} is a superior,
which allows to apply Note \RF{N-x-y} \QED
Now to prove Lemma \RF{L-det-O}. Take any finitary initial \MB{y},
assume (\RF{s=0}) and denote \MB{C=(2\cdot\lambda\cdot\rho)^{-1}}.
Then from Lemma \RF{L-y-x}
$$
y~\preceq~\min\{ [C\cdot L_i+C']^+~:~i\in\SEG{\NL} \}.
$$
where \MB{C'} is defined by (\RF{def-C'}).
>From Lemma \RF{L-lifetime} lifetime of the last expression
does not exceed \MB{\const\cdot C'}. Together with (\RF{def-C'})
and Note \RF{N-diam-T} this proves Lemma \RF{L-det-O} \QED
\SUSEC{Proof of Lemma \RF{L-det-non-O}}
Call a set \MB{S \subset V} \TERM{steady} if for every
inner \MB{v \in S} every drag-set of \MB{v} intersects \ML{S}.
\LEMMA{
Given assumptions of Theorem \RF{T-det},
there is such a steady set \ML{\TOWER}, that \LL{L-steady}
\FORM{
\forall~t \in\Time~:~
1 \leq |\SET{ v \in\TOWER\cap\Z^{\dim+1}~:~t(v)=t }| \leq\const. \LL{in-steady}
}
}
\PROOF is similar to that of Lemma 24 in \cite{Toom-92} \QED
Denote \MB{\STEP=\{ x\in X_{\NEIGHBOR(\ORIGIN)}~:~
Gap(x,~\NEIGHBOR(\ORIGIN))=1 \}}.
\LEMMA{
Given (\RF{m-trans-m}), (\RF{monotony}) and (\RF{+a}).
Then for any \MB{x \in \STEP} \LL{L-STEP}
\FORM{\hskip 0.2in
(\forall~S\in\DRAG~:~ Max(x,S)=Max(x,\NEIGHBOR(\ORIGIN))
\IMPLIES \TRANS(x(\NEIGHBOR(\ORIGIN))=Max(x,\NEIGHBOR(\ORIGIN)). \LL{STEP}
}
}
\PROOF Take any \MB{x\in\STEP}, assume
\MB{Max(x,S)=Max(x,\NEIGHBOR(\ORIGIN))} for all \MB{S \in\DRAG}, but
\MB{\TRANS(x(\NEIGHBOR(\ORIGIN))) < Max(x,\NEIGHBOR(\ORIGIN))}
and come to a contradiction. Denote \MB{M=Min(x,\NEIGHBOR(\ORIGIN))} and
\MB{S= \{ v \in \NEIGHBOR(\ORIGIN)~:~x(v)=M \}}.
Then \MB{\IND_S=x-M} and from (\RF{+a}) \MB{\TRANS(\IND_S)=\TRANS(x)-M=0}.
Then \MB{S} is a drag-set from Lemma \RF{L-drag}.
On the other hand \MB{Max(x,S)=M < Max(x,\NEIGHBOR(\ORIGIN))}
which contradicts our assumption \QED
Now to prove Lemma \RF{L-det-non-O}.
Take any steady set \MB{\TOWER} which satisfies (\RF{in-steady})
and define an initial configuration \MB{y} as follows:
$$
\forall~v\in\V_\INITIAL~:~y(v)=\cases{T &if \MB{v\in\TOWER},\cr
0 &otherwise.}
$$
>From (\RF{in-steady}) \MB{y} is finitary.
Now let us prove by contradiction that
\MB{x(v)=T} for all \MB{v\in\TOWER} where \MB{x=\TR(y)}.
Let the set \MB{\SET{v\in\TOWER~:~x(v)0)\geq\theta} for any inner \MB{v} \QED
It remains to assure the assumptions of Lemma \RF{L-T-inf}.
\SUSEC{Polars and Trusses}
Let a \TERM{vector field} \MB{\phi} on a set \MB{S} stand for a map
\MB{\phi~:~S \to \Z^\NL}. A vector field \MB{\phi} given,
\MB{\phi(v)} stands for its value on any \MB{v \in S}; this value
is a vector whose components are \MB{\phi(v)_1,\ldots,\phi(v)_\NL}.
For any \MB{Q \subseteq S} denote
\MB{\phi(Q)=\sum\{ \phi(v)~:~v \in Q \}}.
Call a vector field \MB{\phi} \TERM{even} or \TERM{\ML{p}-even}
on a set \MB{Q} if all the components of \MB{\phi(Q)} equal \ML{p}.
Call a vector field on \MB{S} \TERM{overall-even}
if it is even on all subsets of \MB{S}.
A vector field \MB{\phi} on a set \MB{S} given, its \TERM{range} is
\MB{\RANGE(\phi)=\{v\in S~:~\phi(v)\neq 0\}}.
The zero vector field, which equals 0 on every element, has empty range.
Call a vector field \TERM{trivial} if its range consists of one element.
\DEFINITION{
Call a vector field \MB{\pi} on \MB{S} a \TERM{polar} if
all of the following conditions hold: \LL{D-polar}
\vskip -0.2in
\begin{itemize}
\item \MB{\pi} is even on \MB{S}.
\item For any \MB{v \in S} and any \MB{j \in\SEG{\NL}}
the value of \MB{\pi(v)_j} is either \MB{0} or \MB{1} or \MB{-1}.
\item For every \MB{j \in\SEG{\NL}} there is at most
one point \MB{v} where \MB{\pi(v)_j=1};
if it exists, it is called the \MB{j}-th \TERM{positive pole} of \MB{\pi}
and denoted \MB{\pi^+(j)}.
\item For every \MB{j \in\SEG{\NL}} there is at most
one point \MB{v} where \MB{\pi(v)_j=-1};
if it exists, it is called the \MB{j}-th \TERM{negative pole} of \MB{\pi}
and denoted \MB{\pi^-(j)}.
\end{itemize}
}
Both positive and negative \MB{j}-poles of a polar are called its \MB{j}-poles.
Call a polar a \TERM{posipole} if it has all the \MB{\NL} positive poles
(which may coincide) and none negative, and
a \TERM{negapole} if it has all the \MB{\NL} negative poles
(which may coincide) and none positive.
\MB{Trivial^+(v)} and \MB{Trivial^-(v)} stand for the trivial
posipole and negapole all of whose poles coincude with \MB{v}.
Let us claim two sequences of polars equivalent if one
turns into the other by some permutation, and call
the resulting classes of equivalence \TERM{trusses}.
\MB{\pi\in\T} means that polar \MB{\pi} is a member of truss \MB{\T},
but different members of a truss may coincide.
We designate a truss by any sequence
\MB{\T=\TRUSS{\pi_1,\ldots,\pi_k}} of its members.
\MB{j}-poles of members of a truss are called its \MB{j}-poles.
\MB{|\T|} stands for the number of members in the truss \ML{\T}.
For any two trusses \MB{\A} and \MB{\B} their concatenation
\MB{\A \ast \B} results from writing one sequence after the other.
Thus \MB{\T\ast\TRUSS{\pi}} means truss \MB{\T}
to which polar \MB{\pi} is added.
Conversely, \MB{\pi\in\T} given, \MB{\T-\pi} means
\MB{\T} from which \MB{\pi} is excluded.
Of course,
$$
|\A\ast\B|=|\A|+|\B|, \qquad |\T\ast\TRUSS{\pi}|=|\T|+1
\HB{and} |\T-\pi|=|\T|-1.
$$
For any truss \MB{\T} its range \MB{\RANGE(\T)} is
defined as the union of ranges of its members.
There is the empty truss whose number of members is 0 and whose range is empty.
To any truss \MB{\T} there corresponds its vector field \MB{\VEC(\T)}
which is the sum of its members as vector fields.
A truss \MB{\T} given, \MB{\VEC(\T,v)} and \MB{\VEC(\T,S)}
stand for the values of the corresponding vector field on
the point \MB{v} and set \MB{S}.
Call a truss \ML{p}-even, even or overall-even if its vector field is.
Call a truss \TERM{connected} if the family of ranges of its members is connected.
\NOTE{
Given a truss \MB{\T} which consists of trivial posipoles and negapoles,
and a non-empty truss \MB{\U}. Then: \LL{N-trivial}
\begin{ASS}
\item \MB{\U} is overall-even iff \MB{\T\ast\U} is overall-even.\\
\item If \MB{\T\ast\U} is connected, then \MB{\U} is also connected
and \MB{\RANGE(\U)=\RANGE(\T\ast\U)}.
\end{ASS}
}
For any \MB{\NL}-tuple \MB{F=(F_1,\ldots,F_\NL)} of functions on a set \MB{S},
any polar \MB{\pi} and truss \MB{\T} on \MB{S} and any \MB{v \in S} denote
\begin{eqnarray*}
& Sum(F,\pi,v)=\sum\{ F_j(v) \cdot \pi(v)_j~:~j\in\SEG{\NL} \} \qquad
Sum(F,\pi) =\sum \{ Sum(F,\pi,v)~:~v \in S \}, & \\
& Sum(F,\T ) =\sum \{ Sum(F,\pi)~:~\pi \in\T \}. &
\end{eqnarray*}
Take the functions \MB{L_1,\ldots,L_\NL}
which satisfy (\RF{lin-0}), (\RF{lin-sum}) and (\RF{lin-drag}),
provided by Lemma \RF{L-lin} and define
$$
L'_i=L_i + \frac{~t~}{\NL},~~i\in\SEG{\NL}.
$$
Note that
\FORM{
L'_1 +\ldots+ L'_\NL \equiv 0 \LL{lin'=0}
}
and
\FORM{
\HB{for all} i\in\SEG{\NL} \HB{the set}
\SET{ e\in\NEIGHBOR(\ORIGIN)~:~L'_i(e) \leq -\frac{~1~}{\NL} }
\HB{ia a drag-set}. \LL{lin'-drag}
}
\LEMMA{
If a truss \MB{\T} on \MB{\V} is overall-even, then \MB{Sum(L',\T)=0},
where \MB{L'=(L'_1,\ldots,L'_\NL)}. \LL{L-sum}
}
\PROOF By grouping together addends that pertain to a point
and using (\RF{lin'=0}) \QED
\SUSEC{Polars and Trusses on Graphs}
All the graphs in this paper have no loops.
In most cases (except Lemma \RF{L-Euler}) every two
vertices \MB{a} and \MB{b} are connected with at most one edge,
which is denoted \MB{a-b} if it is non-directed,
and \MB{a \to b} if it is directed from \MB{a} to \ML{b}.
If \MB{G} and \MB{G'} stand for graphs,
\MB{G' \subseteq G} means that \MB{G'} is a subgraph of \ML{G}.
A graph \MB{G} given, \MB{\VER(G)} stands for the set of its vertics.
A polar on a graph \MB{G} means a polar on the set of vertices of \ML{G}.
A polar \MB{\pi} on a graph \MB{G} is called an \TERM{edger} on \MB{G}
if \MB{\RANGE(\pi)} consists of two vertices connected with an edge.
We say that \MB{\pi} lies on this edge and that this edge underlies \ML{\pi}.
Posi-edger stands for an edger which is a posipole.
An edger \MB{\beta} on \MB{V} is called a \ML{k}\TERM{-boost}
or a \TERM{boost} from \MB{u} to \MB{v} if \MB{\RANGE(\beta)=\SET{u,v}}
where \MB{u\in\NEIGHBOR(v)} and \MB{\beta} has only two poles:
\MB{\beta^+(k)=u} and \MB{\beta^-(k)=v}.
A \ML{k}-boost from \MB{u} to \MB{v} is called a \ML{k}\TERM{-arrow}
from \MB{u} to \MB{v} if \MB{L_k(u)-L_k(v) \leq 0}.
Let \MB{\BOOST(u \to v)} and \MB{\ARROW(u \to v)}
stand for the boost and arrow from \MB{u} to \MB{v}.
\NOTE{
It follows from (\RF{lin-sum}) and Lemma \RF{L-sum} that: \LL{N-sum}
\begin{description}
\DITEM \MB{Sum(L',\pi)=0} for any trivial polar \MB{\pi}.
\DITEM \MB{Sum(L',\alfa)\geq 1} for any arrow \MB{\alfa}.
\DITEM \MB{|Sum(L,\epsi)|\leq \const} for any edger \MB{\epsi} on \MB{V'}.
(One may take this \MB{\const=2\cdot\lambda\cdot\rho'} where\\
\MB{ \rho'=\max\{ L'_i(v)~:~\NORM(v)\leq 1,~~i\in\SEG{\NL}\} }.)
\end{description}
}
\LEMMA{
Given an overall-even truss \ML{\A \ast \E} on \ML{\V}, where
\MB{\A} consists of arrows and \MB{\E} consists of edgers on \ML{V'}.
Then \ML{|\A| \leq |\E| \cdot\const}. \LL{L-AE}
}
\PROOF From Lemma \RF{L-sum} and Note \RF{N-sum}
$$
0=Sum(L',\A\ast\E)=Sum(L',\A)+Sum(L',\E) \geq |\A|-\const\cdot |\E|,
$$
whence \MB{|\A| \leq \const\cdot |\E|} \QED
\SUSEC{Description of the family $\Phi(~\cdot~,~\cdot~)$}
For any inner point \MB{\HUB} and any \MB{\RUB\in\Z_{++}}
let \MB{\Psi(\HUB,\RUB)} stand for the set of triplets \MB{(\A,~\E,~S)}
where \MB{\A} and \MB{\E} are trusses and \MB{S} is a set,
which satisfy the following {\bf Conditions F:}
\begin{LIST}{F}{}
\item \MB{\A} consists of arrows,
\MB{\E} consists of edgers on \ML{V'}. \LL{AE-F}\\
\item The truss \MB{\A\ast\E} is overall-even and connected. \LL{even+conn-F}
\item \ML{\HUB\in\RANGE(\A\ast\E)}. \LL{v-F}
\item \ML{S\subseteq\RANGE(\A\ast\E)}. \LL{S-F}
\item \ML{|S|-\RUB \geq |\E|/\NL}. \LL{S-E-F}
\end{LIST}
Now we define the family \MB{\Phi(\HUB,\RUB)} as follows:
One element of this family is the set \MB{\{\HUB\}}.
Otherwise a set \MB{S} belongs to \MB{\Phi(\HUB,\RUB)}
if there are such trusses \MB{\A} and \MB{\E} that
\MB{(\A,\E,S)\in\Psi(\HUB,\RUB)}.
Proof of (\RF{S-F-inf}) is based on the following lemma.
\LEMMA{
Consider all triplets \MB{(\A,\E, S)} where \MB{\A,\E} are trusses
and \MB{S} is a point-set, such that: \LL{L-Euler}
\begin{description}
\DITEM \MB{\A} and \MB{\E} consist of edgers on \MB{V'}.
\DITEM Truss \MB{\A\ast\E} is connected.
\DITEM \MB{\RANGE(\A\ast\E)} contains a given point.
\DITEM \ML{S \subseteq\RANGE(\A\ast\E)}.
\DITEM \ML{|\A\ast\E|=k}.
\end{description}
The number of these triplets does not exceed \ML{\const^k}.
}
\PROOF It follows from Euler's theorem that to every triplet in question
there corresponds a circuit on \MB{V'} which starts and ends at the given
point and makes \MB{2k} steps, every edger represented by two steps
in the two opposite directions along the underlying edge.
Let us encode the triplet by moving along this circuits step by step.
At every step we must choose the edge to move along,
choose the poles our edger has (among the \MB{2\NL} possible ones),
distribute these poles between the two ends,
and decide whether the current edger belongs to \MB{\A} or \MB{\E}
and whether the current point belongs to \ML{S}.
Note that the degree of any vertex of
\MB{V'} does nor exceed \ML{\NN^2+2\NN}.
Therefore the number of triplets in question does not exceed \MB{\const^k}.
(We may take this \MB{\const=(2^{3\NL+2}(\NN^2+2\NN))^{2}}~) \QED
Now to prove (\RF{S-F-inf}). Evaluate the cardinalities of sets
$$
\Phi_j(\HUB,\RUB)=\{ S \in \Phi(\HUB,\RUB)~:~ |S|=j \} \HB{where} j \in \Z_+.
$$
First \MB{|\Phi_j(\HUB,\RUB)|=0} for all \ML{j<\RUB},
because of \RFL{S-E-F}{F}{}.
Now evaluate \MB{|\Phi_j(\HUB,\RUB)|} for \ML{j \geq \RUB}.
Remember that \MB{\Phi_1(\HUB,1)} contains the special element \MB{\{\HUB\}}
and leave it alone. Without this element, \MB{|\Phi_j(\HUB,\RUB)|} is no more
than the number of different corresponding triplets \ML{(\A,\E,S)}.
If \MB{S \in \Phi_j(\HUB,\RUB)}, then the corresponding trusses
have (\RFL{S-E-F}{F}{}, then \RFL{AE-F}{F}{} and \RFL{even+conn-F}{F}{}
allow to apply Lemma \RF{L-AE})
$$
|\E| \leq\const\cdot(j-\RUB) \IMPLIES
|\A| \leq\const\cdot(j-\RUB) \IMPLIES
|\A\ast\E|\leq\const\cdot(j-\RUB).
$$
In the case \MB{j=\RUB} this implies that \MB{\A} and \MB{\E} are empty,
whence \ML{S} is empty also, which is impossible since \MB{|S|=j\geq\RUB>0}.
Thus, including \MB{\{\HUB\}}
$$
|\Phi_k(\HUB,\RUB)|=\cases{1 &if \MB{\RUB=1},\cr
0 &otherwise.}
$$
In the case \MB{j>\RUB}, due to \RFL{AE-F}{F}{}, \RFL{even+conn-F}{F}{},
\RFL{v-F}{F}{} and \RFL{S-F}{F}{} we can apply Lemma \RF{L-Euler} to obtain
$$
|\Phi_j(\HUB,\RUB)| \leq
\sum_{i=0}^{\const\cdot(j-\RUB)} \const^{i} \leq
\const^{j-\RUB}.
$$
Therefore for all \MB{\theta} small enough
$$
\sum \{\theta^{|S|},~~S \in \Phi(\HUB,\RUB)\}=
\sum_{j=0}^\infty |\Phi_j(\HUB,\RUB)| \cdot \theta^j \leq
\sum_{j=\RUB+1}^\infty \const^{j-\RUB}\cdot \theta^j \leq
(\const\cdot\theta)^{\RUB+1}
$$
which proves (\RF{S-F-inf}).
\SEC{Proof of Theorem \RF{T-inf}: More Technicalities}
\SUSEC{Segmentation}
Suppose that some directed graph \MB{G \subseteq V}
contains an edge \ML{u \to v}. To \TERM{segment} this edge
means to delete this edge from \MB{G} and substitute it by a `chain'
\FORM{
u=i_0 \to i_1 \to i_2 \to\cdots\to i_{\Delta t-1} \to i_{\Delta t}=v,\LL{chain}
}
where \MB{i_0} and \MB{i_{\Delta t}} are our vertices \MB{u} and \ML{v},
and \ML{i_k,~~~~k=1,\ldots,\Delta t-1=t(v)-t(u)-1}, are new intermediate
vertices connected by \MB{\Delta t} new intermediate edges.
We define the time function on the newly introduced vertices by the rule
$$
t(i_k)=t(u)+k,~~~k\in\SEG{\Delta t-1}.
$$
\NOTE{
Segmentation of \MB{u \to v} changes nothing if \ML{t(v)-t(u)=1}.
Thus, segmentation is unnecessary in the special case \MB{\MEM=1}.
}
\SUSEC{Spanning Truss}
Given a posipole \MB{\pi} on a connected non-directed graph \MB{G},
its (non-unique) \TERM{spanning kit} consists of
a \TERM{spanning tree} \MB{\SPANTREE(\pi,G)} and
a \TERM{spanning truss} \MB{\SPANTRUSS(\pi,G)}
which are defined as follows:
First, \MB{\SPANTREE(\pi,G)} is a minimal connected subgraph of \MB{G}
whose set of vertices contains \MB{\RANGE(\pi)}.
Of course, \MB{\SPANTREE(\pi,G)} is a tree, whence every edge of it is
a bridge. Based on this, for every edge \MB{a-b} of \MB{\SPANTREE(\pi,G)}
let us form a posi-edger \MB{\epsi_{a-b}} on \MB{g} whose \ML{k}-th pole
for any \MB{k\in\SEG{\NL}} coincides with \MB{a} or \MB{b}, namely
with that one of the two, which does not remains connected with \MB{\pi(k)}
if the edge \MB{a-b} is deleted from \MB{\SPANTREE(\pi,G)}.
Now, \MB{\SPANTRUSS(\pi,G)} consists of these posi-edgers
for all edges of \MB{\SPANTREE(\pi,G)}.
\NOTE{ \LL{N-span}
\begin{ASS}
\item
\MB{\VER(\SPANTREE(\pi,G))=\RANGE(\SPANTRUSS(\pi,G))\supseteq\RANGE(\pi)}.
\item \MB{|\RANGE(\SPANTRUSS(\pi,G))|=|\SPANTRUSS(\pi,G)|+1}.\\
\item Truss \MB{\TRUSS{\pi}\ast\SPANTRUSS(\pi,G)} is 1-even on every element
of its range. Therefore no two \ML{k}-th poles of it coincide.\\
\item Any truss \MB{\T} given, if \MB{\T\ast\TRUSS{\pi}} is connected,
then \MB{\T\ast\SPANTRUSS(\pi,G)} is connected also.
\end{ASS}
}
Let us classify all the poles of \MB{\SPANTRUSS(\pi,G)} into two categories:
\TERM{end poles}: the \ML{k}-th end pole
coincides with the \MB{k}-th pole of \MB{\pi}, and
\TERM{inner poles}: all the others.
\SUSEC{Transit Neighbors}
Given any directed graph \ML{G}, call those vertices whence edges go
to a vertex, \ML{G}-\TERM{neighbors} of this vertex.
The set of \ML{G}-neighbors of a vertex \MB{v} is called
its \TERM{\ML{G}-neighborhood} and denoted \ML{\NEIGHBOR_G(v)}.
Neighborhoods \MB{\NEIGHBOR(\cdot)} without indices, which we defined
in Section \RF{S-def+form} for all points, are \ML{V}-neighborhoods,
where the graph \MB{V} was also defined in Section \RF{S-def+form}.
\TERM{\ML{G}-neighborhood} of a set \MB{S} of vertices is the
union of \ML{G}-neighborhoods of elements of \ML{S}.
Further, \MB{\NEIGHBOR_G^k(S)} is defined for every \MB{k \in \Z_+}
and every set \MB{S \subseteq \VER(G)} by the inductive rule:
$$
\NEIGHBOR_G^0(S)=S, \qquad \NEIGHBOR_G^{k+1}(S)=\NEIGHBOR_G(\NEIGHBOR_G^k(S)).
$$
The \TERM{transit} and the \TERM{proper} \ML{G}-neighborhoods of \MB{S} are
$$
\NEIGHBOR_G^\TRANSIT(S) =\bigcup_{k=0}^\infty \NEIGHBOR_G^k(S) \HB{and}
\NEIGHBOR_G^\PROPER (S) =\bigcup_{k=1}^\infty \NEIGHBOR_G^k(S)
$$
and their elements are called transit and proper
\ML{G}-neighbors of \ML{S} respectively.
Call two vertices \TERM{\ML{G}-comparable} if
one is a transit \ML{G}-neighbor of the other.
Call two sets \ML{G}-comparable if some element of the
first and some element of the second are \ML{G}-comparable;
otherwise these sets are \ML{G}-uncomparable.
\SEC{Proof of Theorem \RF{T-inf}: Auxiliary Graphs}
Throughout this and the next sections,
an inner point \ML{\hub}, a positive integer \MB{\rub}
and a hidden configuration \MB{h} are fixed, such that
\FORM{
x(\hub) \geq \rub. \LL{x(hub)-rub}
}
Our purpose is to assure (\RF{S-W-inf}), that is to present such a set
\MB{S \subseteq W(h)} that \MB{S \in \Phi(\hub,\rub)}.
\SUSEC{Graph $G$}
A typed graph is a directed graph whose vertices have \TERM{types}:
every vertex \MB{v} has \ML{\TYPE(v)\in\SET{X,A,B,C,D}}.
To obtain a typed graph \ML{G}, we shall construct
inductively a sequence of typed graphs
\MB{G_0,~G_1,~G_2,~\ldots} and at some step we stop.
Some vertices of these graphs belong to \ML{\V},
others will be newly introduced due to segmentation.
Along with this, we shall prove the following
{\bf Conditions G$_i$:}
\begin{LIST}{G}{i}
\item \MB{x(\cdot)>0} for all those vertices of \MB{G_i}
which belong to \ML{\V}. \LL{x-0-G}\\
\item A vertex of \MB{G} has type \MB{D} iff
it does not belong to \MB{\V}. \LL{typeD-G}\\
\item A vertex of \MB{G} has empty \ML{G_i}-neighborhood iff
its type is \MB{X} or \MB{C}. \LL{typeC-G}\\
\end{LIST}
{\bf Initial condition:}
We start with a graph \MB{G_0} which has one vertex \MB{\hub}
of type \MB{X} and no edges. Note that {\bf Conditions G$_0$} hold.
{\bf Stop-Rule:} As soon as none vertex of \MB{G_i} has type \ML{X},
we stop and define \ML{G=G_i}.
{\bf Induction Step:}
Suppose that the graph \MB{G_i} has a vertex \MB{v} whose type is \MB{X}.
By the induction assumption, \ML{x(v)>0}. Let us consider three cases.
{\bf Case 0.} Let \MB{\TRANS(x(\NEIGHBOR(v)))=0}. Then \MB{v} is an upstart.
In this case we turn \MB{G_i} into \MB{G_{i+1}}
only by changing type of \MB{v} from \MB{X} to \MB{C}.
Now let \MB{\TRANS(x(\NEIGHBOR(v)))>0}. Then, due to Definition \RF{D-drag}
at least one of the following two cases takes place:
{\bf Case 1.} Every drag-set for \MB{v} contains a point
where \ML{x(\cdot) \geq \TRANS(x(\NEIGHBOR(v)))}.
Then, from (\RF{lin-drag}), for every \MB{k \in\SEG{\NL}}
there exists \MB{n_k(v) \in \NEIGHBOR(v)} where
\FORM{
x(n_k(v)) \geq \TRANS(x(\NEIGHBOR(v)))
\HB{and} L_k(n_k(v))-L_k(v) \leq 0. \LL{G-1}
}
In this case we obtain \MB{G_{i+1}} from \MB{G_i}
by changing type of the vertex \ML{v} from \MB{X} to \MB{A}
and introducing the segmented edges \ML{n_k(v) \to v,~~k\in\SEG{\NL}}.
{\bf Case 2.} There is a point \MB{n(v) \in \NEIGHBOR(v)} where
\FORM{
x(n(v))>\TRANS(x(\NEIGHBOR(v))). \LL{G-2}
}
In this case we obtain \MB{G_{i+1}} from \MB{G_i}
by changing type of the vertex \ML{v} from \MB{X} to \MB{B}
and introducing the segmented edge \ML{n(v) \to v}.
In both cases all the newly introduced intermediate vertices,
which do not belong to \MB{\V}, are assigned type \MB{D}.
The end-points \MB{n_k(v)} and \MB{n(v)} may belong to \MB{G_i},
in which case they keep the same type they had in \MB{G_i};
otherwise they are assigned type \MB{X}.
Note that {\bf Conditions G$_i$} given, {\bf Conditions G$_{i+1}$}
are also true in all cases.
\LEMMA{
G-induction stops. \LL{L-Gstop}
}
\PROOF The number of vertices of \MB{G_i} plus the number of those
vertices of \MB{G_i} whose type is \MB{C}, increases at every step.
On the other hand, only elements of the finite set
\MB{\NEIGHBOR^\TRANSIT(\hub)} can be vertices of \MB{G_i} \QED
\NOTE{
A vertex of G has type \MB{C} iff it is an upstart. \LL{N-Cup}
}
\SUSEC{Tree $T$}
Let us call vertices of \MB{G} \TERM{leaves} and classify them into
equivalence classes called \TERM{branches} by the following two rules:
\begin{itemize}
\item If two leaves have equal time values and a common
transit \ML{G}-neighbor, then they are equivalent.
\item Only those leaves are equivalent for which
it follows from the previous rule and transitivity.
\end{itemize}
Now define a directed graph \MB{T} by the following two rules:
\begin{itemize}
\item \MB{\VER(T)} is the set of branches.
\item Branches \MB{A,B} given, \MB{A \in \NEIGHBOR_T(B)} iff
\ML{\exists~ a \in A,~b \in B~:~a \in \NEIGHBOR_G(b)}.
\end{itemize}
\NOTE{
The leaf \MB{\hub} is equivalent to no other leaf.
Graph \MB{T} is a tree in which all edges are directed
towards the vertex \ML{\SET{\hub}}. \LL{N-tree}
}
A branch \MB{B} given, its \TERM{bush}, called \MB{\BUSH(B)}
stands for \MB{\NEIGHBOR_G^\TRANSIT(B)}. A \TERM{bush} stands for
a bush of some branch, which is called its \TERM{root}.
\NOTE{
If two bushes are \ML{G}-comparable,
then their roots are \ML{T}-comparable. \LL{N-bushes}
}
Say that a branch \TERM{cuts} a set \MB{S} of branches if
\MB{S \subseteq \NEIGHBOR_T^\TRANSIT(B)}.
For any set \MB{S} of branches there is just one branch that cuts \ML{S},
all of whose \ML{T}-neighbors do not cut \ML{S};
call this branch \TERM{root} of \MB{S} and denote it \MB{\ROOT(S)}.
For any polar \MB{\pi} on \MB{G} its \TERM{root} or \MB{\ROOT(\pi)}
stands for the root of the set of branches which intersect its range,
and its \TERM{bush} stands for \MB{\BUSH(\pi)=\BUSH(\ROOT(\pi))}.
\SUSEC{Graphs $\NGR(\cdot)$}
For any branch \MB{A} whose \ML{T}-neighborhood is non-empty,
define a non-directed graph \MB{\NGR(A)} by the following two rules:
\begin{itemize}
\item \ML{\VER(\NGR(A))=\NEIGHBOR_T(A)}.
\item Two different vertices \MB{B^1,B^2} of \MB{\NGR(A)}
are connected with an edge in \MB{\NGR(A)} iff there exist\\
\ML{a \in A, \qquad
b^1 \in \NEIGHBOR_G^\TRANSIT(B^1) \cap \NEIGHBOR_G(a), \qquad
b^2 \in \NEIGHBOR_G^\TRANSIT(B^2) \cap \NEIGHBOR_G(a)}.
\end{itemize}
\LEMMA{
Every \MB{\NGR(A)} is connected. \LL{L-connected}
}
\PROOF is similar to that of Lemma 9 in \cite{Toom-92} \QED
\SEC{Proof of Theorem \RF{T-inf}: Q-Induction}
\SUSEC{Conditions Q$_i$}
Now \MB{i} is an integer parameter which
grows from \MB{0} to some maximal value.
For every value of \MB{i} we shall form a \ML{(4+\NL)}-tuple
$$
\Omega_i=(\A_i,~\B_i,~\C_i,~\D_i,~S_i^1,\ldots,~S_i^\NL)
$$
where \MB{\A_i,~\B_i,~\C_i} and \MB{\D_i} are trusses
and \ML{S_i^1,\ldots,S_i^\NL} are point-sets.
Thereby we shall also define a truss \MB{\Q_i=\A_i\ast\B_i\ast\C_i\ast\D_i}
and \MB{\NL} functions \MB{F_i^1,\ldots,F_i^\NL} on \MB{V}
\FORM{
F_i^j(v)=\cases{x(v)-h(v) &if \MB{v \in S_i^j},\cr
x(v) &otherwise.} \LL{def-F}
}
We shall construct \MB{\Omega_i}
inductively, the integer parameter \MB{i} increasing from zero.
Along with constructing them, we shall prove by induction
that they satisfy the following {\bf Conditions Q$_i$}:
\begin{LIST}{Q}{i}
\item \MB{\A_i} consists of arrows,
\MB{\B_i} consists of boosts,
\MB{\C_i} consists of posi-edgers on \MB{V'},
\MB{\D_i} consists of negapoles. \LL{ABCD-Q}
\item \MB{\Q_i} is overall-even and connected. \LL{even+conn-Q}
\item \MB{\hub\in\RANGE(\Q_i)\subseteq(\VER(G)\cap\V)}. \LL{Range-Q}
\item \MB{\forall~j~:~S_i^j \subseteq\RANGE(\Q_i(j)) \cap W(h)}. \LL{S-W-Q}
\item \MB{\sum_{j=1}^\NL |S_i^j| + Sum(F_i,\D_i)
\geq \NL\cdot x(\hub) + |\B_i| + \NL\cdot |\C_i| }. \LL{S-x-Q}
\item \MB{\VEC (\Q_i-\delta,~\BUSH(\delta))} is a posipole
for every \MB{\delta\in\D_i}. \LL{posipole-Q}
\item For every \MB{j \in\SEG{\NL}} every \MB{j}-pole of \MB{\Q_i} has a
transit \MB{G}-neighbor which is a \MB{j}-pole of \MB{\D_i}. \LL{neighbor-Q}
\end{LIST}
{\bf Initial Condition:} \MB{\A_0,~\B_0,~\C_0} and
\MB{S_0^1,\ldots,S_0^\NL} are empty and
\MB{\D_0=\TRUSS{Trivial^-(\hub)}}.
Note that {\bf Conditions Q$_0$} hold.
{\bf Stop-Rule:} We stop as soon as
all of the following {\bf Conditions S$_i$} hold:
\begin{LIST}{S}{i}
\item \MB{\forall~j~:~(\RANGE(\D_i(j))\cap W(h))\subseteq S_i^j }.\LL{D-S-S}
\item \MB{\RANGE(\D_i) \subseteq U(h)}. \LL{D-U-S}
\item All the members of \MB{\D_i} are trivial. \LL{trivial-S}
\end{LIST}
\LEMMA{
{\bf Conditions Q$_i$} given, for every \MB{j\in\SEG{\NL}}
no proper \ML{G}-neighbor of an element of \MB{\RANGE(\D_i(j))}
can belong to \MB{S_i^j}. \LL{L-noproper}
}
\PROOF Assume the contrary: there are \MB{v=\delta^-(j)}
and \MB{u \in \NEIGHBOR^\PROPER(v) \cap S_i^j}.
Then from \RFL{S-W-Q}{Q}{i} \MB{u\in\RANGE(Q_i(j))}.
Then from \RFL{neighbor-Q}{Q}{i} \MB{u} has a transit
\MB{G}-neighbor \MB{w \in D_i(j)}.
Then from \RFL{posipole-Q}{Q}{i} \MB{w=\delta^-(j)}
which is impossible since \MB{w \neq v} \QED
\LEMMA{
{\bf Conditions Q$_i$} given, bushes of members of \MB{\D_i}
are pairwise \ML{G}-uncomparable. \LL{L-uncomparable}
}
\PROOF Assume the contrary: bushes of \MB{\delta,~\delta' \in\D_i}
are \ML{G}-comparable. Then from Note \RF{N-bushes}
$$
\ROOT(\delta) \in \NEIGHBOR_G^\TRANSIT(\ROOT(\delta'))
$$
(or vice versa, which is analogous),
whence \MB{\BUSH(\delta')} contains at least \MB{2\cdot\NL} negative poles.
Then, from \RFL{even+conn-Q}{Q}{i},
it contain at least \MB{2\cdot\NL} positive poles,
which contradicts \RFL{posipole-Q}{Q}{i} \QED
\NOTE{
Condition \RFL{D-S-S}{S}{i} given, \MB{F_i^j(v)=x(v)-h(v)}
for all \MB{j\in\SEG{\NL}}, \MB{v\in\RANGE(\D_i(j))}. \LL{N-F=}
}
\SUSEC{Induction step}
Assume that \MB{\Omega_i} is constructed and
{\bf Conditions Q$_i$} proven. Assume also that at least one of
{\bf Conditions S$_i$} fails and define \MB{\Omega_{i+1}}.
{\bf Case 1:} \RFL{D-S-S}{S}{i} fails, i.e. there is
\MB{j\in\SEG{\NL}} and \MB{v=\delta^-(j)\in\RANGE(\D_i)},
which belongs to \MB{W(h)} but not to \ML{S_i^j}.
In this case the only difference between \MB{\Omega_{i+1}} and \MB{\Omega_i}
is that \MB{S^j_{i+1}=S^j_i\cup\{ v\} }.
{\bf Case 2:} \RFL{D-S-S}{S}{i} holds, but \RFL{D-U-S}{S}{i} fails,
i.e. \MB{\RANGE(\D_i(j)) \cap W \subseteq S_i^j} for every \MB{j}, but
there is some \MB{v=\delta^-(k) \in\RANGE(D_i)} which is not an upstart.
Then, according to Stop-Rule of G-Induction,
\MB{\TYPE(v)} is \MB{A} or \ML{B}. Consider these two cases.
{\bf Case 2A:} \ML{\TYPE(v)=A}. Then there exist
\ML{n_1(\delta^-(k)),\ldots,n_\NL(\delta^-(k))}.
In this case the only difference between \MB{\Omega_{i+1}} and \MB{\Omega_i}
is that \MB{\A_{i+1}=\A_i\ast\TRUSS{\ARROW(n_k(\delta^-(k))\to\delta^-(k))}}
and \MB{\D_{i+1}} differs from \MB{\D_i} in only one respect:
instead of \MB{\delta} it contains \MB{\delta_{new}} which has only one pole
different from that of \MB{\delta},
namely \MB{\delta^-_{new}(k)=n_k(\delta^-(k))}.
{\bf Case 2B:} \MB{\TYPE(v)=B}. Then there exists \ML{n(\delta^-(k))}.
In this case the only difference between \MB{\Omega_{i+1}} and \MB{\Omega_i}
is that \MB{\B_{i+1}=\B_i \ast \TRUSS{\BOOST(n(\delta^-(k))\to\delta^-(k))}}
and \MB{\D_{i+1}} differs from \MB{\D_i} in only one respect:
instead of \MB{\delta} it contains \MB{\delta_{new}} which has only one pole
different from that of \MB{\delta},
namely \MB{\delta^-_{new}(k)=n(\delta^-(k))}.
{\bf Case 3:} \RFL{D-S-S}{S}{i} and \RFL{D-U-S}{S}{i} hold,
but \RFL{trivial-S}{S}{i} fails.
So \MB{\D_i} contains a non-trivial negapole \MB{\delta}.
Let us prove that \MB{\RANGE(\delta) \cap \ROOT(\delta) = \empset} in this case.
Assume the contrary: there is some \MB{\delta^-(k) \in \ROOT(\delta)}.
Since all the elements of \MB{\RANGE(\delta)} are upstarts,
they have no \ML{G}-neighbors (Note \RF{N-Cup}).
Since \MB{\delta^-(k)} has no \ML{G}-neighbors,
\MB{\ROOT(\delta)} is the branch that contains \MB{\delta^-(k)}
and nothing else. This contradicts our assumption.
Thus, every pole of \MB{\delta} belongs to the transit \ML{G}-neighborhood
of some \ML{T}-neighbor of \ML{\ROOT(\delta)}.
This allows us to define a posipole \MB{\pi} on \MB{\NEIGHBOR_T(\ROOT(\delta))}
by the following rule applied to all \MB{k\in\SEG{\NL}}:~~
\MB{\pi^+(k)} is that \ML{T}-neighbor of \MB{\ROOT(\delta)}
whose bush contains \ML{\delta^-(k)}.
>From Lemma \RF{L-connected}, the graph \MB{\NGR(\ROOT(\delta))} is connected.
Therefore there exists a spanning kit which consists of
\MB{\SPANTREE(\pi,\NGR(\ROOT(\delta))} and
\MB{\SPANTRUSS(\pi,\NGR(\ROOT(\delta))}.
For every member \MB{\epsi} of this spanning truss
(which is a posi-edger on the spanning tree)
we form a posi-edger \MB{\gama(\epsi)} on \MB{G} as follows.
Denote
$$
\RANGE(\epsi)=\SET{A,B} \subset \NEIGHBOR_T(\ROOT(\gama)).
$$
Since vertices \MB{A} and \MB{B} of \ML{\NGR(\ROOT(\delta))}
are connected with an edge in this graph, there are leaves
$$
c \in V, \qquad a \in \NEIGHBOR_G^\TRANSIT(A) \cap \NEIGHBOR_G(c),
\qquad b \in \NEIGHBOR_G^\TRANSIT(B) \cap \NEIGHBOR_G(c).
$$
Now define our posi-edger \MB{\gama} as follows:
\FORM{
\forall~ k\in\SEG{\NL}~:~\gama^+(k)=\cases{a &if $\epsi(k)=A$,\cr
b &if $\epsi(k)=B$.} \LL{def-gamma}
}
Truss \MB{\Gamma_i} consists of these \MB{\gamma}.
\NOTE{
\MB{|\Gamma_i|=|\SPANTRUSS(\pi,\NGR(\ROOT(\delta))|}. \LL{N-Gamma}
}
\NOTE{
\MB{j \in\SEG{\NL}} given, all the \MB{j}-poles of the truss
\MB{\TRUSS{\delta}\ast\Gamma_i} are mutually \MB{G}-uncomparable, because
they belong to mutually \MB{\T}-uncomparable branches. \LL{N-uncomparable}
}
In {\bf Case 3} the only difference between
\MB{\Omega_{i+1}} and \MB{\Omega_i} is that
\MB{\C_{i+1}=\C_i\ast\Gamma_i} and
\MB{\D_{i+1}} differs from \MB{\D_i} as follows.
Denote
$$
\T_{i+1}=\A_{i+1}\ast\B_{i+1}\ast\C_{i+1}
\HB{and}
\ver=\VER(\SPANTREE(\pi,\NGR(\ROOT(\delta))).
$$
>From statement 3 of Note \RF{N-span},
\MB{\T_{i+1}} is 1-even on every \MB{B\in\ver}.
Thus, for every \MB{k\in\SEG{\NL}} every branch \MB{B\in\ver}
serves as the \ML{k}-th pole just for one member of
\MB{\TRUSS{\pi}\ast\SPANTRUSS(\pi,\NGR(\ROOT(\delta))}.
This means that for every \MB{B \in \ver}
and for every \MB{k \in \SEG{\NL}} the truss \MB{\TRUSS{\delta}\ast\Gamma_i}
has just one positive \ML{k}-th pole in \ML{\BUSH(B)},
and let it be the negative \ML{k}-th pole
of the new negapole \MB{\delta_B} that corresponds to \ML{B}.
Now define
$$
\D_{i+1}=(\D_i-\delta)\ast\TRUSS{\delta_B~:~B \in\ver}.
$$
Thus \MB{\Omega_{i+1}} is defined in all cases.
Now let us prove the implication
{\bf Conditions Q$_i$} \MB{\IMPLIES}
{\bf Conditions Q$_{i+1}$}.
The only non-trivial proofs are the following ones.
\RFL{even+conn-Q}{Q}{i+1} in {\bf Case 3}
follows from statements 4) and 3) of Note \RF{N-span}.
Proof of \RFL{S-x-Q}{Q}{i+1} in all cases
involves estimation of the difference
\FORM{
Sum(F_{i+1},\D_{i+1})-Sum(F_i,\D_i). \LL{sum-sum}
}
{\bf Case 1:} In this case the difference (\RF{sum-sum}) equals \MB{-1},
because, due to Lemma \RF{L-uncomparable},
only one addend of \MB{Sum(F_i,\D_i)} may decrease,
namely \MB{F_i^j(\delta^-(j))}, and it decreases by \MB{1}.
This is compensated by the fact that \MB{|S_{i+1}^j|-|S_i^j|=1} \QED
{\bf Case 2A:} In this case all we need to prove is that
the difference (\RF{sum-sum}) is non-negative, which boils down to
\MB{F_{i+1}^k(n_k(v)) \geq F_i^k(v)}.
Since \MB{S_{i+1^j}=S_i^j} for all \MB{j}, this can be rewritten as
\FORM{
F_i^k(n_k(v)) \geq F_i^k(v). \LL{in-F-F}
}
Let us prove it. Since \RFL{D-S-S}{S}{i} holds,
$$
F_i^k(v)=x(v)-h(v)=\TRANS(x(\NEIGHBOR(v))).
$$
On the other hand, from Note \RF{N-F=}, \MB{n_k(v)} cannot
belong to \MB{S_i^k}, whence \MB{F_i^k(n_k(v))=x(n_k(v))},
and (\RF{in-F-F}) follows from (\RF{G-1}) \QED
{\bf Case 2B:} In this case all we need to prove is that
the difference (\RF{sum-sum}) is positive, which boils down to
$$
F_i^k(n(v)) > F_i^k(v).
$$
The right side equals \MB{x(v)-h(v)=\TRANS(x(\NEIGHBOR(v)))} from Note
\RF{N-F=} and the left side equals \MB{x(n(v))} from Lemma \RF{L-noproper}.
Thus the inequality to prove follows from (\RF{G-2}) \QED
{\bf Case 3:} In this case the proof boils down to the fact that
the difference (\RF{sum-sum}) is not less than \MB{\NL\cdot|\ver|}.
Let us prove it.
\NOTE{
\MB{x(\cdot)>0} at all inner poles, because they are vertices
of \MB{G} (see \RFL{x-0-G}{G}{i}). \LL{N-inner-x}
}
\LEMMA{
No inner \MB{j}-pole belongs to \MB{S_i^j}. \LL{L-inner-S}
}
\PROOF Assume that there is an inner \ML{j}-pole \MB{v \in S_i^j}.
Then, from \RFL{S-W-Q}{Q}{i}, \MB{v\in\RANGE(\Q_i(j))}.
Then, from \RFL{neighbor-Q}{Q}{i},
\MB{v} has a transit \MB{G}-neighbor \MB{w \in\D_i(j)}.
Then, from Lemma \RF{L-uncomparable} \MB{w=\delta^-(j)},
which contradicts Note \RF{N-uncomparable} \QED
Now let us estimate the difference (\RF{sum-sum}).
Since \MB{S_{i+1}^j=S_i^j} for all \MB{j\in\SEG{\NL}},
this difference equals \MB{Sum(F_i,\D_{i+1})-Sum(F_i,\D_i)}
which is not less than \MB{\NL\cdot |\ver|}.
\SUSEC{Result of Q-Induction}
\LEMMA{
{\bf Q-induction} stops. \LL{L-Qstop}
}
\PROOF From \RFL{S-W-Q}{Q}{i} the sum \MB{\sum |S_i^j|} is limited,
whence {\bf Case 1} cannot occur infinitely.
>From \RFL{Range-Q}{Q}{i} and Lemma \RF{L-uncomparable}
\MB{|\D_i|} cannot be greater than \MB{|G|}, whence
{\bf Case 3} also cannot occurs infinitely,
because every its occurence increases \MB{|\D_i|}.
Now, \MB{Sum(F_i,\D_i)} is also limited because every value of
functions \MB{F_i^j} on vertices of \MB{G} cannot exceed \MB{t(\hub)}.
Thus, the left side of \RFL{S-x-Q}{Q}{i} is limited, whence
the right side is also limited, whence \MB{|\B_i|} and \MB{|\C_i|}
are limited, whence {\bf Case 2} also cannot occur infinitely \QED
\LEMMA{
When {\bf Q-Induction} stops, \ML{Sum(F_i,\D_i)=0}. \LL{L-Sum=0}
}
\PROOF It follows from (\RF{def-F}) and \RFL{D-U-S}{S}{i} \QED
When {\bf Q-Induction} stops, we obtain the trusses
\MB{\A_{i},~\B_{i},\C_i,~\D_i} and the sets \MB{S_i^1,\ldots,S_i^\NL}
for which {\bf Conditions Q$_i$} and {\bf S$_i$} hold, and define
\FORM{
\A=\A_i, \qquad \E=\B_i\ast\C_i, \qquad
S=\RANGE(\A\ast\E) \cap W(h). \LL{def-AES}
}
\NOTE{
\MB{S \supseteq \cup \{ S_i^j~:~j \in \SEG{\NL} \}}. \LL{N-SS}
}
\LEMMA{
Let {\bf Conditions Q$_i$} and {\bf Conditions S$_i$} hold.
Then either \MB{\hub} is an upstart, in which case \MB{S=\{\hub\}}, or
\MB{\A,~\E,~S} defined by (\RF{def-AES}) satisfy {\bf Conditions F}. \LL{Q+S-F}
}
\PROOF First let \MB{\hub\in U(h)}.
Then G-induction stops without making a step, and \MB{\VER(G)=\{\hub\}}.
Q-induction makes \MB{\NL} steps, at everyone of which
{\bf Case 1} takes place. In result we obtain
$$
\A_\NL=\B_\NL=\C_\NL=\empset,
\qquad \D_\NL=\TRUSS{Trivial^-(\hub)},
\qquad \forall~ j~:~S_\NL^j=\{\hub\},
\HB{whence} S=\{\hub\}.
$$
Now let \MB{\hub\notin U(h)}. Then \MB{G}-induction makes at least one step,
\MB{G} contains more that one vertex and \MB{\A\ast\E} is non-empty,
whence Note \RF{N-trivial} can be applied. Then:
(\RF{S-W-inf}) follows from \RFL{S-W-Q}{Q}{i}.
\RFL{AE-F}{F}{} follows from \RFL{ABCD-Q}{Q}{i}.
\RFL{even+conn-F}{F}{} follows from
\RFL{even+conn-Q}{Q}{i} and \RFL{trivial-S}{S}{i}.
\RFL{v-F}{F}{} follows from \RFL{Range-Q}{Q}{i}.
\RFL{S-F}{F}{} follows from (\RF{def-AES}). %\RFL{S-W-Q}{Q}{i}.
\RFL{S-E-F}{F}{} follows from \RFL{S-W-Q}{Q}{i},
Note \RF{N-SS}, \RFL{S-x-Q}{Q}{i} and Lemma \RF{L-Sum=0} \QED
Thus Theorem \RF{T-inf} is proved \QED
\SEC{Proof of Theorem \RF{T-fin}}
\SUSEC{Main Lemma}
Proof of Theorem \RF{T-fin} is similar to and based on the
proof of Theorem \RF{T-inf}.
In this case for every inner point \MB{\HUB} and every \MB{\RUB\in\Z_{++}}
we construct two finite families \MB{\Phi' (\HUB,\RUB)}
and \MB{\Phi''(\HUB,\RUB)}
of point-sets which have the following three properties (where \MB{C=\const}):
\FORM{
\forall~ h\in H~:~(x(\HUB)\geq\RUB)\IMPLIES
\exists~ S\in\Phi'(\HUB,\RUB)\cup\Phi''(\HUB,\RUB)~:~S\subseteq W(h).
\LL{S-W-fin}
}
\FORM{
\sum\{\theta^{|S|}~:~S \in \Phi'(\HUB,\RUB)\} \leq \RIGHTPART{} \LL{S-in-F'}
}
\FORM{
\sum\{ \theta^{|S|}~:~S\in\Phi''(\HUB,\RUB) \}\leq
\const\cdot t(v) \cdot (C\cdot\theta)^{\RUB+1+\const\cdot\SIZE}. \LL{S-in-F''}
}
\LEMMA{
Given families \MB{\Phi'(\HUB,\RUB)} and \MB{\Phi''(\HUB,\RUB)}
for all \MB{v\in\V_\INNER,~~k\in\Z_{++}} and \MB{C=\const}
which satisfy (\RF{S-W-fin}), (\RF{S-in-F'}) and (\RF{S-in-F''}).
Then Theorem 2 holds. \LL{L-T-fin}
}
\PROOF Any constant \MB{T} given, while \MB{t(v) < T^\SIZE},
the right part of (\RF{S-in-F''}) is still less
than \MB{\const\cdot (\const\cdot \theta)^{\RUB+1+\const\cdot\SIZE}}.
Then we can choose such \MB{\SIZE_0} that for all
\MB{\SIZE \geq \SIZE_0} this expression is \MB{O(\theta^{\RUB+1})}.
Thus, from (\RF{S-W-fin}), then (\RF{S-in-F'}) and (\RF{S-in-F''}):
\begin{eqnarray*}
\lefteqn{Prob(x(\HUB) \geq \RUB) \leq
\sum\{Prob(W(h) \supseteq S)~:~S\in\Phi'(\HUB,\RUB)\cup\Phi''(\HUB,\RUB)\} =}\\
&&\sum\{\theta^{|S|}~:~S\in\Phi'(\HUB,\RUB)\cup\Phi''(\HUB,\RUB)\}\leq
\RIGHTPART{,}
\end{eqnarray*}
which proves (\RF{prob-fin}).
Then (\RF{exp-fin}) follows from (\RF{prob-fin}) and from
the fact that \MB{Prob(x(v)>0)\geq\theta} for any inner \MB{v} \QED
\SUSEC{Span}
\NOTE{
If a connected truss \MB{\T} consists of edgers on \MB{V'}, then
\MB{\DIAM(\RANGE(\T)) \leq\const\cdot |\T|}. \LL{N-conn-diam}
}
\NOTE{
\MB{\DIAM(S_1 \cup S_2) ~\leq~
\DIAM(S_1)+\DIAM(S_2)+\DIST(S_1,S_2)}. \LL{N-2-diam}
}
Denote \MB{\SPAN(S)=\DIAM(S)+\lambda} and
call two point-sets \TERM{\ML{\lambda}-close} if the distance
between them does not exceed \ML{\lambda}.
(Note that any non-empty set is \ML{\lambda}-close to itself.)
Call a family of point-sets \TERM{\ML{\lambda}-connected}
if it is possible to go from any its element to any other,
every step made between \ML{\lambda}-close sets.
\LEMMA{
If a family \MB{F} of point-sets is \ML{\lambda}-connected,
then \MB{ \SPAN(\UNION(F)) \leq\sum \{ \SPAN(S),~S \in F \} }. \LL{L-conn-span}
}
\PROOF By induction, based on Note \RF{N-2-diam} \QED
\LEMMA{
For any \ML{v \in V} \LL{L-span-n}
$$
\SPAN (N_G^\TRANSIT(v)) \leq
\sum \{ \SPAN (\NEIGHBOR_G^\TRANSIT(w)),~w \in \NEIGHBOR_G(v) \}+\lambda.
$$
}
\PROOF This follows from Lemma \RF{L-conn-span} \QED
\SUSEC{Infinite Representation of The Finite Case \LL{SS-fin-inf}}
We are considering a process \MB{P_\SIZE} on
a finite volume \MB{V_\SIZE=\Z_\SIZE^{\dim} \cdot Time}.
Let us call elements of the finite volume \ML{\SIZE}-points.
Let \MB{V_\infty=\Z_\infty^{\dim} \cdot Time}
stand for the corresponding infinite volume
whose elements are called \ML{\infty}-points now.
The map \MB{\fin~:~V_\infty \mapsto V_\SIZE} is defined as follows:
\MB{\fin(s,t)=(s',t)} where components of \MB{s'}
are residues of components of \MB{s} modulo \ML{\SIZE}.
The opposite map \MB{\inf~:~V_\SIZE \mapsto V_\infty} is defined by
$$
\forall~(s,t) \in V_\SIZE~:~\inf(s,t)=(s,t) \in V_\infty.
$$
Call elements of the finite and infinite hidden spaces
\TERM{hidden \ML{\SIZE}-configurations} and \TERM{\ML{\infty}-configurations}.
To every hidden \ML{\SIZE}-configuration \MB{h} there corresponds
a periodical hidden \ML{\infty}-configuration \ML{h'=\INF(h)}
defined by the rule
$$
\forall~v \in V_\infty~:~h'(v)=h(\fin(v)).
$$
We shall use the auxiliary infinite process \MB{P'_\infty} on \MB{V_\infty}
induced by the finite hidden measure \MB{\eta_\SIZE} with this map.
\NOTE{
\MB{\forall~v \in V_\infty~:~P'_\infty|_v \equiv P_\SIZE|_{\fin(v)}}.
\LL{N-inf=fin}
}
Say that a set \MB{S \subset V_\infty} \TERM{overlaps} if there are
different \MB{v,v' \in S~:~\fin(v)=\fin(v')}.
\NOTE{
If \MB{S \subset V_\infty} does not overlap, then \ML{|\fin(S)|=|S|}.
\LL{N-not-overlap}
}
\NOTE{
If \MB{S \subset V_\infty} overlaps, then \ML{\DIAM(S) \geq \SIZE}.
\LL{N-overlap}
}
\SUSEC{Description of the families
$\Phi'(~\cdot~,~\cdot~)$ and $\Phi''(~\cdot~,~\cdot~)$}
{\bf To define \MB{\Phi'(v,k)}:} One element of it is \MB{\SET{v}}.
Otherwise a point-set \MB{S \subset \V_\SIZE} belongs to
\MB{\Phi'(v,k)} if it is representable as \MB{S=\fin(S_\infty)}
where \MB{S_\infty} is such a subset of \MB{V_\infty} for which
there are such trusses \MB{\A} and \MB{\E} on \MB{V_\infty},
that \MB{(\A,\E,S_\infty)\in\Psi(\HUB,\RUB)}
and \MB{S_\infty} does not overlap.
\LEMMA{
Family \MB{\Phi'(v,k)} satisfies (\RF{S-in-F'}). \LL{L-F'}
}
\PROOF is like that of ( \RF{S-F-inf}) \QED
{\bf To define \MB{\Phi''(v,k)}:} A point-set \MB{S \subset V_\SIZE}
belongs to \MB{\Phi''(v,k)} if it is representable as \MB{S=\fin(S_\infty)}
where \MB{S_\infty} is such a subset of \MB{V_\infty} for which
there are such trusses \MB{\A} and \MB{\E} on \MB{V_\infty}
and such a point \MB{w \in \NEIGHBOR^\TRANSIT(v)}
that \MB{(\A,\E,S_\infty)\in\Psi(w,\RUB)}
and \MB{S_\infty} does not overlap and
\FORM{
\SPAN(\RANGE(\A\ast\E)) \geq (\SIZE-\lambda) /\NN. \LL{span-F''}
}
\LEMMA{
Family \MB{\Phi''(v,k)} satisfies (\RF{S-in-F''}). \LL{L-F''}
}
\PROOF From (\RF{span-F''}) and definition of span
$$
\DIAM(\RANGE(\A \ast \E)) \geq \frac{\SIZE-\lambda}{\NN} - \lambda.
$$
Then from \RFL{even+conn-F}{F}{} and Note \RF{N-conn-diam}
$$
|\A \ast \E| \geq\const\cdot\SIZE - \const.
$$
Due to \RFL{AE-F}{F}{} and \RFL{even+conn-F}{F}{}
we can apply Lemma \RF{L-AE} which gives
$$
|\E| \geq\const\cdot\SIZE - \const.
$$
Then from \RFL{S-E-F}{F}{}, the fact that \MB{S_\infty} does not overlap
and Note \RF{N-not-overlap}
$$
|S|=|S_\infty| \geq C_1 \SIZE - C_2,
$$
where \MB{C_1>0} and \MB{C_2} are constants. Now let us prove
(\RF{S-in-F''}) by evaluating the cardinalities of the sets
$$
\Phi''_j(v,k)= \{ S \in \Phi''(v,k)~:~|S|=j \}.
$$
As we have proved, \MB{|\Phi''_j(v,k)|=0} for all \MB{j < C_1\SIZE-C_2}.
Now let \MB{j \geq C_1\cdot\SIZE-C_2}.
>From \RFL{S-E-F}{F}{} \MB{|\E|\leq\NL\cdot (j-k)},
then from Lemma \RF{L-AE} \MB{|\A \ast \E| \leq\const\cdot j},
then from Lemma \RF{L-Euler} \MB{|\Phi''_j(v,k)|\leq\const^j}.
Thus,
\begin{eqnarray*}
&&\sum \{ \theta^{|S|},~S \in \Phi''(v,k) \} ~\leq~ \\
&&\const\cdot \SIZE^{\dim} \cdot t(v) \cdot
\sum_{j=C_1\SIZE-C_2}^\infty (\const\cdot\theta)^j ~\leq~
\const\cdot\SIZE^{\dim}\cdot t(v)\cdot (\const\cdot\theta)^{\const\cdot\SIZE}.
\end{eqnarray*}
For small enough \MB{\theta}, this is less
than the right part of (\RF{S-in-F''}) \QED
\SUSEC{Final}
In section \RF{SS-fin-inf} we have represented
the finite process \MB{P_\SIZE} as a special
infinite process \MB{P'_\infty},
to which we can apply constructions of the infinite case.
Given a \ML{\infty}-point \ML{v}, a number \MB{k} and
a hidden \ML{\infty}-configuration \MB{h} such that \MB{x(v) \geq k>0},
we obtain the triplet \ML{(\A,~\E,~S)} defined by (\RF{def-AES}).
Let \MB{\T_\infty(v,h,k)=\A\ast\E} stand for the
concatenation of the first two terms of this triplet,
and \MB{S_\infty(v,h,k)} stand for the last term of this triplet.
\LEMMA{
If \MB{S_\infty(v,h,k)} overlaps, then there exists
a \ML{\SIZE}-point \MB{\ersatz(v,h,k) \in \NEIGHBOR^\TRANSIT(v)} such that
\MB{S_\infty(\ersatz(v,h,k),h,k)} does not overlap, and \LL{L-ersatz}
$$
\SPAN(\RANGE(\T(\ersatz(v,h,k),~h,~k))) \geq (\SIZE-\lambda) /\NN.
$$
}
\PROOF Take the set of those points \MB{w \in \NEIGHBOR_G^\TRANSIT(v)}
for which \MB{S_\infty(w,h,k)} overlaps, take a point in this set
whose time is the smallest, and call this point \ML{\PIT}.
Let us prove by contradiction that among \ML{G}-neighbors of \MB{\PIT}
there is at least one which fits our need. Assume the contrary:
$$
\forall~w \in N_G(\PIT)~:~\SPAN(\RANGE(\T(w,h,k))) < (\SIZE-\lambda) / \NN.
$$
Then from \RFL{S-E-F}{F}{} and Lemma \RF{L-span-n}
$$
\SPAN(S_\infty(\PIT,h,k)) \leq \SPAN (N_G^\TRANSIT(\PIT)) < \SIZE
$$
which contradicts Note \RF{N-overlap} \QED
Now define a set \MB{S_\SIZE \in \Phi'(v,k)~\cup~\Phi''(v,k)}
for any \ML{\SIZE}-point \ML{v}, hidden \ML{\SIZE}-configuration \MB{h}
and \ML{k \in\SEG{x(v)}}:
\FORM{
S_\SIZE(v,~h,~k)=\fin(S_\infty(\inf(v),\INF(h),k)) \LL{def-S-fin-dsnt}
}
if \MB{S_\infty(\inf(v),\INF(h),k)} does not overlap, and
\FORM{
S_\SIZE(v,~h,~k)=\fin(S_\infty(\ersatz(\inf(v)),~\INF(h),~k))\LL{def-S-fin-does}
}
if \MB{S_\infty(\inf(v),\INF(h),k)} overlaps.
\NOTE{
In both cases of the definition of \MB{S_\SIZE},
(\RF{S-W-fin}) is assured. \LL{N-assured}
}
\LEMMA{
Every \MB{S_\SIZE(v,h,k)} defined by (\RF{def-S-fin-dsnt})
belongs to \MB{\Phi'(v,k)} and\\
every \MB{S_\SIZE(v,h,k)} defined by (\RF{def-S-fin-does})
belongs to \ML{\Phi''(v,k)}. \LL{L-F+F}
}
\PROOF The first assertion can be proved as in the infinite case.
Let us prove the second. All assertions but the last one
were proved when treating of the infinite case.
The last assertion (\RF{span-F''}) follows from Lemma \RF{L-ersatz} \QED
Thus Theorem \RF{T-fin} is proved \QED
\SEC{Proof of Theorem \RF{T-back}}
\NOTE{
If a point-set \MB{\TOWER} satisfies (\RF{in-steady}), then any \MB{v \in V}
belongs to \MB{\TOWER} shifted by some \ML{s \in \Space}. \LL{N-any-in-S}
}
Now take any steady set \MB{\TOWER} which satisfies (\RF{in-steady})
and separate it into parts by the rule:
$$
\FLOOR_i=\{ v \in\TOWER~:~(i-1)\cdot\MEM \leq t(v) < i\cdot\MEM \}.
$$
\NOTE{
\MB{\forall~i~:~1 \leq |\FLOOR_i| \leq\const}. \LL{N-Floor}
}
\LEMMA{
\MB{\forall~ v \in V~:~\EX_\theta(v) \geq \theta^\const \cdot t(v)/\MEM},
where \MB{\const} is that of Note \RF{N-Floor}. \LL{L-EX-t}
}
\PROOF First we prove that
$$
\forall~v \in\FLOOR_i~:~E_\theta(\min\{x(v)~:~v \in\FLOOR_i\})
\geq \theta^{\const} \cdot i.
$$
This is because
\begin{eqnarray*}
&&\min\{x(v),~v \in\FLOOR_{i+1}\}= \\
&&\min\{\TRANS(x(N(v)))+h(v),~v \in\FLOOR_{i+1} \} \geq \\
&&\min\{\TRANS(x(N(v))),~v\in\FLOOR_{i+1}\}+\min\{h(v),~v\in\FLOOR_{i+1}\}\geq\\
&&\min \{ x(v),~v \in\FLOOR_i \} +\min\{h(v),~v\in\FLOOR_{i+1} \}.
\end{eqnarray*}
(Expectation of the last term is no less than \ML{\theta^\const}.)
Hence and from Note \RF{N-any-in-S} Lemma \RF{L-EX-t} follows \QED
Theorem \RF{T-back} follows from Lemma \RF{L-EX-t} \QED
\begin{thebibliography}{10}
\bibitem{Toom-92} Andrei Toom. A Critical Phenomenon in Growth Systems.
Submitted to {\sl Journal of Statistical Physics}.
\bibitem{Toom-80} Andrei Toom.
Stable and Attractive Trajectories in Multicomponent Systems.
{\sl Multicomponent Random Systems} (Ed. by R. Dobrushin and Ya. Sinai).
Advances in Probability and Related Topics, Dekker, c1980, v. 6, pp. 549-576.
\bibitem{T+M} Andrei Toom \& Leonid Mityushin.
Two Results regarding Non-Computability for Univariate Cellular Automata.
{\it Problems of Information Transmission}, 1976, v. 12, n. 2, pp. 135-140.
\bibitem{Petri} N. V. Petri.
The Unsolubility of The Problem of Discerning of Annuling Iterative Nets.
{\sl Researches in the Theory of Algorithms and Mathematical Logic.}
Nauka, Moscow, 1979 (In Russian).
\bibitem{Galperin} G. A. Gal'perin.
One-Dimensional Local Monotone Operators with Memory.
{\sl Soviet Math. Dokl.}, vol. 17 (1976), no. 3, pp.688-692.
%\bibitem{Rockafellar} R. T. Rockafellar. Convex Analysis.
%Princeton Univ. Press, 1970.
\end{thebibliography}
\end{document}