% “„Š 518.5+513.6

% 2000 Math. Subject Class. 14Q15

\documentclass[a4paper]{article}
\usepackage{amsfonts,amscd}


%\documentstyle[a4,amssymb]{article}

%\renewcommand{\baselinestretch}{1.2}
%\parskip 2ex plus 1ex minus 1ex




\begin{document}

 \title{Polynomial--Time Algorithms in Zero--Characteristic for a New
 Model of Representation of Algebraic Varieties}
\author{Alexander L.~Chistov%
 \\[2ex]
St.~Petersburg Institute for Informatics and
Automation of the\\ Academy of Sciences of Russia\\
14th line 39, St.~Petersburg 199178, Russia,\\
e-mail: labta@iias.spb.su  or sliss@iias.spb.su }
\date{\Large 2004}

\newtheorem{thms}{THEOREM}
\newtheorem{lems}{LEMMA}
\newtheorem{rems}{REMARK}
\newtheorem{defns}{DEFINITION}
\newtheorem{props}{PROPOSITION}
\newtheorem{coros}{COROLLARY}

\maketitle

\begin{abstract}
We suggest a model of representation of algebraic varieties based on
representative systems of points of its irreducible components.
Deterministic
polynomi\-al--time algorithms to substantiate this model are described in
zero--charac\-te\-ristic.  The main result here is a construction
of the intersection of algebraic varieties.  As applications we get
efficient algorithms for constructing the smooth stratification and smooth
cover of an algebraic variety introduced by the author earlier.
\end{abstract}




\newpage

\section*{Introduction}

The present work concludes the series of papers \cite{2}, \cite{3}, \cite{4},
\cite{5}, \cite{6}, \cite{7}, \cite{8}, \cite{9} (the correction of Lemma~2
\cite{9}, see in \cite{10}), \cite{10},
\cite{11}, where the polynomial--time algorithms
for to algebraic varieties in zero--characteristic are suggested
(we do not use the results of \cite{11} in the present paper;
but the particular case of \cite{11} from \cite{8} is necessary here).
Before formulating our results we describe how to give
a quasiprojective algebraic variety using
a representative system of points of its irreducible components.
The model of representation of algebraic varieties suggested here slightly
generalizes the one outlined in \cite{7}, see the remarks below. In \cite{7}
the description of the algorithms for
this representation was postponed.
It hase become possible only using the results
of four more papers \cite{5}, \cite{8}, \cite{9}, \cite{10}.


Let $k$ be a field of zero--characteristic
with algebraic closure $\overline{k}$.
Let $X_0,X_1,\ldots $ be independent
variables over $k$. Denote by
${\Bbb P}^n(\overline{k})$, $n\ge 0$, the projective space over the field
$\overline{k}$ with coordinates $X_0,\ldots , X_n$. We shall suppose that
${\Bbb P}^n(\overline{k})$ is defined over $k$.  For arbitrary
homogeneous polynomials $g_1,\ldots ,g_m\in\overline{k}[X_0,\ldots , X_n]$
we shall denote by ${\cal Z}(g_1,\ldots ,g_m)$ the set of all common
zeroes of polynomials $g_1,\ldots ,g_m$ in ${\Bbb P}^n(\overline{k})$.
The similar notations will be used for the sets of zeroes of ideals and
polynomials with other fields of coefficients in affine and projective
spaces (this will be seen from the context).


Let $W$ be a quasiprojective algebraic variety in ${\Bbb
P}^n(\overline{k})$ and $W$ is defined over $k$.
Then we represent
$$
W=\bigcup_{1\le i\le b}W^{(i)}\setminus\bigcup_{b+1\le i\le a}W^{(i)},
\eqno (1)
$$
where  $1\le b\le a$ are integers, and
all $W^{(i)}$, $1\le i\le a$, are projective algebraic varieties in ${\Bbb
P}^n(\overline{k})$ defined over $k$.
Each algebraic variety $W^{(i)}$, $1\le i\le a$,
is a union of some irreducible components of the
variety $V^{(i)}={\cal Z}(f^{(i)}_1,\ldots ,
f^{(i)}_{m(i)})\subset{\Bbb
P}^n(\overline{k})$ where homogeneous polynomials
$f^{(i)}_1,\ldots , f^{(i)}_{m(i)}\in k[X_0,\ldots ,X_n]$ are given,
$m(i)\ge 1$.
For every $0\le s\le n$
denote by $V^{(i,s)}$ (respectively $W^{(i,s)}$)
the union of all irreducible components of dimension $n-s$
of ${\cal Z}(f^{(i)}_1,\ldots , f^{(i)}_{m(i)})$ (respectively
$W^{(i)}$).
Therefore $W^{(i,s)}$ is a union of
some irreducible components of $V^{(i,s)}$.
For every $0\le s\le n$ the
family of linear forms $L^{(i,s)}_{s+1},\ldots , L^{(i,s)}_n\in
k[X_0,\ldots ,X_n]$ is given such that the number of points
$$
\# V^{(i,s)}\cap{\cal Z}(L^{(i,s)}_{s+1},\ldots , L^{(i,s)}_n)
<+\infty
\eqno (2)
$$
is finite, every point
$\xi\in V^{(i,s)}\cap{\cal Z}(L^{(i,s)}_{s+1},\ldots , L^{(i,s)}_n)$
is a smooth point
of the algebraic variety ${\cal Z}(f^{(i)}_1,\ldots , f^{(i)}_{m(i)})$,
and
the intersection of the tangent spaces in the point $\xi$ of $V^{(i)}_s$ and
${\cal Z}(L^{(i,s)}_{s+1},\ldots , L^{(i,s)}_n)$ is transversal, i.e.,
$$
T_{\xi, V^{(i)}_s}\cap
{\cal Z}(L^{(i,s)}_{s+1},\ldots , L^{(i,s)}_n)=\{\xi\}
\eqno (3)
$$
(we consider the tangent space $T_{\xi, V^{(i)}_s}$ as a subspace of
${\Bbb P}^n(\overline{k})$).
The set of points
$$
\Xi^{(i,s)}= W^{(i,s)}
\cap{\cal Z}(L^{(i,s)}_{s+1},\ldots , L^{(i,s)}_n)
$$
is given. Each point from  $\Xi^{(i,s)}$ is represented in form
(11), see below. Hence the following property holds.
Let $\xi\in V^{(i,s)}
\cap{\cal Z}(L^{(i,s)}_{s+1},\ldots , L^{(i,s)}_n)$
and $E$ be the uniquely defined irreducible over $k$
component
of the algebraic variety $V^{(i,s)}$ such that $\xi\in E$. Then $\xi\in
\Xi^{(i,s)}$ if and only if $E$ is a component of $W^{(i)}$.
In what follows, unless we state otherwise, we assume that the degrees
$\deg_{X_0,\ldots , X_n}f^{(i)}_j<d$ for all $i,j$.

Thus, formally the suggested in this paper representation of $W$ is a
quadruple
$$
(f,L,\Xi,b),
\eqno (4)
$$
where $f$ is a
family of polynomials
$$
f^{(i)}_{j},\quad 1\le j\le m(i),\,1\le i\le a,
\eqno (5)
$$
$L$ is a family of linear forms
$$
L^{(i,s)}_w,\quad s+1\le w\le n,\,  0\le s\le n,\, 1\le i\le a,
\eqno (6)
$$
and $\Xi$ is a family of finite sets of points
$$
\Xi^{(i,s)},\quad 0\le s\le n,\, 1\le i\le a.
\eqno (7)
$$
Denote also
$$
\Xi^{(i)}=\bigcup_{0\le s\le n}\Xi^{(i,s)}.
\eqno (8)
$$

In \cite{7}
only the case $b=1$ is considered. In the present paper in comparison
with \cite{7} we replace the low index $s$ by the upper one
to avoid an ambiguity of the notation when one consider more than one
algebraic variety, see below.

Notice that (2) and (3) can be always verified using the
algorithms from
\cite{4}, see the Introduction of \cite{7} for details. Note also that
for a given point $y\in {\Bbb P}^n(\overline{k})$
one can decide whether
$y\in W^{(i,s)}$ using the algorithms from \cite{4} and \cite{1},
see the Introduction of \cite{7}.
Thus, for a given point $y\in {\Bbb P}^n(\overline{k})$ one can decide
also within the polynomial time whether
$y\in W^{(i)}$, $1\le i\le a$, and whether $y\in W$.

Let $W=\bigcup_{i\in I}W_i$ be the decomposition of $W$ into the union of
defined over $k$ and irreducible over $k$ (respectively
irreducible over $\overline{k}$) components and representation (4) is
given. Then using Theorem~1 \cite{8} (or
more strong Theorem~3 \cite{10}) and Theorem~2 \cite{8}
one can construct for every $i\in I$ the
representation $(f,L_i,\Xi_i,1)$
of the irreducible component  $W_i$ (in the case when $W_i$ is irreducible
over $\overline{k}$ we construct the minimal
field of definition $k_i$ of $W_i$ containing $k$ and replace the ground
field $k$ by $k_i$
in the representation of $W_i$, see \cite{8} for details).
The working time of this algorithm is polynomial in $d^n$ and the size of
input, see \cite{8} (and also the proof of Theorem~1 below for the partial
case
$\nu=1$).


Further, see Theorem~3 below,
let $W_1,W_2$ be two quasiprojective algebraic varieties which are similar
to $W$ and are
given in the similar way (with the same bound $d$ for degrees of the
polynomials). Then
one can decide whether $W_1=W_2$
within the time in $d^n$ and the size of input.
In \cite{7} this is proved only when $W_1$ and $W_2$ are
projective algebraic varieties.
The general case of quasiprojective algebraic varieties is difficult.

To prove Theorem~3 we need at first describe an algorithm for constructing
an intersection of $\nu$ quasiprojective algebraic varieties given
in the considered model
within the time in $d^{n\nu}$ and the size of input, see Theorem~1 below.
This algorithm uses the reduction to the diagonal. Here one needs to apply
Theorem~1 \cite{10}. The last theorem has a long proof. It is
based on \cite{9}, \cite{8}, \cite{7}
and other our papers, see the Introduction of \cite{10}.
Besides that in Theorem~1 indices of intersection of algebraic varieties
are computed when they are defined.
Notice here that at the output of the algorithm from Theorem~1
the intersection of quasiprojective algebraic varieties is not given in the
considered model. The irreducible components of the intersections
not always can be given using representative systems of points of
irreducible components of an algebraic variety ${\cal V}$ with good
upper bounds for degrees of polynomials giving ${\cal V}$.
Still we get at the output of the algorithm
from Theorem~1 all the information about the intersection.
One can consider the representation of the intersection of algebraic
varieties from assertion (a) of Theorem~1 as a
generalization of representation (4) to the case of intersections of
algebraic varieties given in form (4).


Denote $m=m(1)$, and $f_i=f_i^{(1)}$, $1\le i\le m$.
Let $V={\cal Z}(f_1,\ldots , f_m)\subset{\Bbb P}^n(\overline{k})$ be
an algebraic variety.
Recall the definition from \cite{7}.
\par\medskip\noindent{\bf DEFINITION~1}\hspace{0.1em} {\it  Smooth cover of
the algebraic variety $V$ is a finite family
$$
V_\alpha,
\quad\alpha\in A,\eqno (9)
$$
of quasiprojective smooth
algebraic varieties $V_\alpha\subset{\Bbb P}^n(\overline{k})$, $\alpha\in
A$ such that $V$ is represented as a union
$V=\cup_{\alpha\in A}V_\alpha$. Further, we shall require that
all irreducible components of $V_\alpha$ have the same dimension (which
depends only on $\alpha$).  Smooth stratification of the algebraic
variety $V$ is a smooth cover $V_\alpha$,
$\alpha\in A$, of $V$ such that additionally
for any two $\alpha_1,\alpha_2\in A$ if
$\alpha_1\ne \alpha_2$ then $V_{\alpha_1}\cap V_{\alpha_2}=\emptyset$.
}\par\medskip


In this paper we assume that
the degree of an arbitrary projective algebraic variety is the
sum of the degrees of all its
irreducible components (of different dimensions). The degree of
a quasiprojective algebraic variety ${\cal V}$
is by definition the degree of its closure in the corresponding
projective space.

In \cite{7} using the construction of local parameters from \cite{5} we prove
the existence of smooth cover (respectively smooth stratification) (9)
of the algebraic variety $V$
with the bound for the degrees of strata  $2^{2^{n^C}}d^n$, and the number
of strata $2^{2^{n^C}}d^n$ (respectively the number
of strata $2^{2^{n^C}}d^{n(n+1)/2}$)
for an absolute constant $0<C\in{\Bbb R}$, see
Theorem~2 \cite{7}.
The constructions of \cite{7} are quite explicit.
It turns out that it is sufficient to use additionally only
Theorem~1 and Theorem~2
(the last only one in the case $(\nu,nn_1)=(3,2)$) to obtain
the algorithms for
constructing the smooth cover and
smooth stratification from Theorem~2 \cite{7}
within the time polynomial in $2^{2^{n^C}}d^n$ (respectively
$2^{2^{n^C}}d^{n(n+1)/2}$)
and the size of input, see Theorem~4 below.

Now we proceed to the precise statements. Let the integers $a,b$;  $m(i)$,
$1\le i\le b$, the homogeneous polynomials
$f^{(i)}_j\in k[X_0,\,\ldots\, ,X_n]$, $1\le j\le m(i)$,  $1\le i\le a$,
the algebraic varieties $V^{(i)}$, $W^{(i)}$, and  $W$ be as above.

Let  the field $k={\Bbb Q}(t_1,\,\ldots\, ,t_l,\theta )$
where $t_1,\,\ldots\, ,t_l$ are
 algebraically independent over the field ${\Bbb Q}$ and $\theta$ is
 algebraic over ${\Bbb Q}  (t_1,\,\ldots\, ,t_l)$ with the minimal
 polynomial $F\in{\Bbb Q}  [t_1,\,\ldots\, ,t_l,Z]$ and leading
 coefficient $ {\mathrm  lc}_ZF$ of $F$ is equal to 1.
 We shall represent each polynomial $f=f_j^{(i)}$ in
the form
$$
 f=\frac{1}{a_0} \sum_{i_0, \ldots, i_n} \sum_{0 \leq j <
 \deg_Z F} a_{i_0, \ldots, i_n,j} \theta^j X_0^{i_0} \cdots X_n^{i_n}
 \, ,
$$
 where $a_0,a_{i_0, \ldots, i_n,j} \in {\Bbb Z}  [t_1, \ldots, t_l]$,
 $\mbox{\rm G\,C\,D\,}_{i_0, \ldots, i_n,j}
 (a_0,a_{i_0, \ldots, i_n,j})=1$.
 Define the length ${\rm l}(a)$ of an integer $a$ by the formula
 ${\rm l}(a)=\min\{s \in {\Bbb Z}  : \: |a|<2^{s-1}\}$.
 The length of coefficients ${\rm l}(f)$ of the polynomial $f$ is defined to
 be the maximum of lengths of coefficients from ${\Bbb Z}$ of polynomials
 $a_0,a_{i_0, \ldots, i_n,j}$ and the degree
$$
 \deg_{t_\gamma} (f)=\max_{i_0, \ldots, i_n,j} \{\deg_{t_\gamma} (a_0),
 \deg_{t_\gamma} (a_{i_0, \ldots, i_n,j})\} \, ,
$$
 where $1 \leq \gamma \leq l$.
 In the similar way we shall define degrees and lengths
of integer coefficients of other polynomials,
in particular $\deg_{t_\gamma} F$ and ${\rm l}(F)$ are defined.

 \noindent
 We shall suppose that we have the following bounds
\setcounter{equation}{9} \begin{eqnarray}
&& \deg_{X_0, \ldots, X_n} (f_j^{(i)})<d, \; \deg_{t_\gamma}(f_j^{(i)})<d_2,
\;{\rm l}(f_j^{(i)})<M, \label{10}\\
&& \deg_Z (F)<d_1, \; \deg_{t_\gamma} (F)<d_1, \; {\rm l}(F)<M_1.\nonumber
 \end{eqnarray}
for all $1\le j\le m(i)$, $1\le i\le a$, $1\le\gamma\le l$.
 The size ${\rm L}(f)$ of the polynomial $f$ is defined to be the product of
 ${\rm l}(f)$ to the number of all the coefficients from ${\Bbb Z}$ of
$f$ in
 the dense representation.
 We have
$$
 {\rm L}(f_j^{(i)})<({d+n \choose n}d_1+1)d_2^l M
$$
 Similarly ${\rm L}(F)<d_1^{l+1} M_1$.

\par\medskip\noindent{\bf REMARK~1}\hspace{0.1em} {\it  Unless
we state otherwise, in what follows we suppose $l$ to be fixed.
The working time of the algorithms from  Theorem~1, Theorem~2 and Theorem~4,
see
below, is
essentially the same as for solving systems of polynomial equations with a
finite set of solutions in the projective space.
 So this theorems can be formulated also in the case when $l$ is not fixed,
see \cite{1}. Notice that the constants $O(\ldots)$,
see Theorem~1, Theorem~2 and Theorem~4 below,
in the estimate of the lengths of integer coefficients
of linear forms $L'_j$, $L_j$ are absolute; they does not depend on $l$.
}\par\medskip




We shall represent a point $z\in V$ with coordinates from a
finite extension of $k$ as follows. An index $0\le i_0\le n$ is
known such that $X_{i_0}(z)\ne 0$  and an isomorphism of fields
$$
k(z)=k((X_1/X_{i_0})(z),\ldots , (X_n/X_{i_0})(z))=
k[\eta]\simeq k[Z]/(\Phi)
\eqno (11)
$$
is given where $\eta=\sum_{0\le i\le n}c_i(X_i/X_{i_0})(z)$,  the
coefficients $c_i\in {\Bbb Z}$ are given and $\Phi\in k[Z]$ is
minimal polynomial of $\eta$ over $k$ with leading coefficient
$\mbox{\rm lc}_Z\Phi=1$ (so the point $z$ is defined up
to a conjugation over $k$).

Let $g\in k[\eta]$ be an arbitrary element. Then $g=G(\eta)$ for the
uniquely defined polynomial
$A\in k[Z]$ such that $\deg_ZG<\deg_Z\Phi$. The length of integer
coefficients ${\rm l}(g)$,
the size ${\rm L}(g)$ and the degrees $\deg_{t_\alpha}g$,
$1\le \alpha\le l$, of $g$
are defined by the formulas
$$
{\rm l}(g)={\rm l}(G),\quad {\rm L}(g)={\rm L}(G), \quad
\deg_{t_\alpha}g=\deg_{t_\alpha}G.
$$
Let us define the size of the point $z$ to be
${\rm L}(\Phi)+\sum_{0\le i\le n}{\rm L}(X_i/X_{i_0})$.
Now let $\Xi$ be an arbitrary finite set of points defined over $k$, and
every point from
$\Xi$ is given in form
(11). Hence $\Xi$ gives a zero--dimensional algebraic varieties defined
over $k$.
Put the size ${\rm L}(\Xi)$ of $\Xi$ to be the sum of sizes of its
irreducible
over $k$
components.

\medskip Recall that in \cite{10} we give the definition of transversality of
intersection of algebraic varieties.
Now we give the analogous natural definition related to the proper
intersections.
Let $W_1,\ldots , W_\nu\subset{\Bbb P}^n(\overline{k})$, $\nu\ge 1$,
be  $\nu$ quasiprojective algebraic varieties
defined over $k$. Let $E$ be an arbitrary defined over $k$ and irreducible
over $k$ component of $W_1\cap\ldots\cap W_\nu$. We
shall say that the intersection
$W_1\cap\ldots\cap W_\nu$ is proper at $E$
(in the ambient space ${\Bbb P}^n(\overline{k})$) if and
only if for every defined over $k$ and
irreducible over $k$ component $E_i$, $1\le i\le\nu$, of $W_i$ such
that $E_i\supset W$ the equality
$\sum_{1\le i\le\nu}(n-\dim E_i)=n-\dim E$ holds
(and hence $\dim E_i$ depends only on $i$).
The intersection of $W_1,\ldots , W_\nu$ is proper
(in the ambient space ${\Bbb
P}^n(\overline{k})$) if and only if it is proper
at every its defined over $k$ and irreducible over $k$ component.

If $\nu=2$ then the index of intersection $i(W_1,W_2;E)=
i(W_1,W_2;E')$ where $E'$ is an arbitrary irreducible over
$\overline{k}$ component of $E$, and the index of intersection
$i(W_1,W_2;E')$ is defined in the usual way, see,
e.g., \cite{12}.

For an arbitrary  $\nu>2$ we define the index of intersection
$i(W_1,\ldots , W_\nu;E)$ of the algebraic varieties $W_1,\ldots ,
W_\nu$ at $E$ recursively
by the formula $i(W_1,\ldots , W_\nu;$ $E)=\sum_{E''}i(W_1,\ldots ,
W_{\nu-1};E'')
i(E'',W_\nu;E)$ where $E''$ runs over all the irreducible over
$k$ components of
$W_1\cap\ldots\cap W_{\nu-1}$ such that $E''\supset E$.
For $\nu=1$ it is natural to put $i(W_1;E)=1$.

Here all the indices of intersection are considered in ${\Bbb
P}^n(\overline{k})$. To specify this we denote
$i_{{\Bbb P}^n(\overline{k})}(W_1,\ldots, W_\nu;E)=
i(W_1,\ldots, W_\nu;E)$. Assume that all $W_j$,
$1\le j\le\nu$, are subvarieties of an affine space ${\Bbb
A}^n(\overline{k})$.
One can identify ${\Bbb A}^n(\overline{k})={\Bbb
P}^n(\overline{k})\setminus{\cal Z}(X_0)$.
We shall denote also in this case
$i_{{\Bbb A}^n(\overline{k})}(W_1,\ldots, W_\nu;E)=
i(W_1,\ldots, W_\nu;E)$ when the last index of intersection
is defined.

We shall use the reduction to diagonal for indices of intersection.
Namely, let $\nu\ge 1$ be an integer. Let us identify the affine space
${\Bbb A}^{n\nu}(\overline{k})=({\Bbb A}^n(\overline{k}))^\nu$.
Put $\Delta=\{(x,x,\ldots , x)\in{\Bbb A}^{n\nu}(\overline{k})\, :\,
x\in{\Bbb A}^n(\overline{k})\}$ to be the diagonal subvariety.
Now we identify
$$
{\Bbb A}^n(\overline{k})=({\Bbb A}^n(\overline{k}))^\nu\cap\Delta.
\eqno (12)
$$
Let $W_1,\ldots , W_\nu$ be affine algebraic varieties in ${\Bbb
A}^n(\overline{k})$ and $E$ be a defined over $k$ and irreducible over $k$
component of
$W_1\cap\ldots\cap W_\nu$ such that the last intersection is proper at $E$.
Then by (12) the variety $E$ is a defined over $k$ and irreducible over
$k$ component of $(W_1\times\ldots \times W_\nu)\cap\Delta$
holds. Obviously the last intersection is proper at
$E$. We have
$$
i_{{\Bbb A}^n(\overline{k})}(W_1,\ldots , W_\nu;E)=i_{{\Bbb
A}^{n\nu}(\overline{k})}(W_1\times\ldots \times W_\nu,\Delta;E).
\eqno (13)
$$
This formula of reduction to diagonal is well known for $\nu=2$, see, e.g.,
\cite{12}.
For an arbitrary $\nu$ it is proved by the induction on $\nu$ using the
general properties of indices of intersection (these
general properties also can be found in \cite{12}; we leave the details to
the
reader).


\medskip Let $\nu\ge 1$ be an integer. For every integer $1\le\alpha\le\nu$
let $m_\alpha(i)$,
$a_\alpha$, $b_\alpha$, $f_{\alpha,j}^{(i)}$, $W_\alpha$,
$V_\alpha$, $W_\alpha^{(i)}$, $V_\alpha^{(i)}$, $W_\alpha^{(i)}$,
$V_\alpha^{(i,s)}$, $W_\alpha^{(i,s)}$,
$L_{\alpha,\beta}^{(i,s)}$, $\Xi_\alpha^{(i,s)}$,
$(f_\alpha,L_\alpha,\Xi_\alpha,b_\alpha)=\rho_\alpha$ are similar to the
introduced above
$m(i)$, $a$, $b$, $f_j^{(i)}$, $W$,
$V$, $W^{(i)}$, $V^{(i)}$, $W^{(i)}$,
$V^{(i,s)}$, $W^{(i,s)}$,
$L_\beta^{(i,s)}$, $\Xi^{(i,s)}$,
$(f,L,\Xi,b)=\rho$ respectively. In what follows in this paper we
suppose that inequalities (10) with
$f_{\alpha,j}^{(i)}$ in place of $f_j^{(i)}$
hold for every $1\le\alpha\le\nu$.


\par\medskip\noindent{\bf THEOREM~1}\hspace{0.1em} {\it  Assume that for
every $1\le\alpha\le\nu$ a representation
$(f_\alpha,L_\alpha,\Xi_\alpha,$ $b_\alpha)$ of a quasiprojective algebraic
variety $W_\alpha$ is given.
Then one can construct linear forms $L_0,\ldots , L_{n+1}\in k[X_0,\ldots ,
X_n]$ with integer coefficients of
length $O(n\nu\log d+\sum_{1\le i\le\nu}\log b_i+
\log(\sum_{1\le i\le\nu}a_i))$, the finite set of indices
$J$, and for every $j\in J$
the finite set $\Xi_j$ of points
from $W_1\cap\ldots\cap W_\nu$ (each point is represented in form (11))
such that the following assertions hold.
\begin{enumerate} \renewcommand{\labelenumi}{(\alph{enumi})}
\item For every $j\in J$ there is the unique defined over $k$ and
irreducible over $k$ component of
$W_1\cap\ldots\cap W_\nu$ (denote it by $E_j$) such that $\dim E_j=n-s(j)$
and
$\Xi_j=E_j\cap{\cal Z}(L_{s(j)+1},\ldots,
L_n)$ in ${\Bbb P}^n(\overline{k})$. Conversely, for every defined over
$k$ and irreducible over $k$ component $E'$ of
$W_1\cap\ldots\cap W_\nu$ there is $j'\in J$ such that $E'=E_{j'}$. Hence
$W_1\cap\ldots\cap W_\nu=\bigcup_{j\in
J}E_j$ is the decomposition of $W_1\cap\ldots\cap W_\nu$
into the union of irreducible over $k$ components.
Let
$\overline{E}_j$ be the closure of $E_j$
with respect to the Zariski topology
in ${\Bbb P}^n(\overline{k})$.
Then for every $j\in J$
$$
\Xi_j\cap{\cal Z}(L_0)=\emptyset,\quad\#\Xi_j=
\#(L_{n+1}/L_0)(\Xi_j)=\deg\overline{E}_j
\eqno (14)
$$
(here and below $\#(.)$ denote the number of elements of a set), and
all the points of $\Xi_j$ are smooth points of $W_1\cap\ldots\cap
W_\nu$. The variety
$$
E_j=\overline{E}_j\setminus
\Bigl(\,\bigcup_{1\le\alpha\le\nu}\;\bigcup_{b_\alpha+1\le i\le a_\alpha}
W_\alpha^{(i)}\,\Bigr).
$$
\item If the intersection of $W_1,\ldots , W_\nu$ is proper at
$E_j$ then one can compute the index of intersection
$i_{{\Bbb P}^n(\overline{k})}(W_1,\ldots, W_\nu;E_j)$, and for every
point $\xi\in\Xi_j$ the
equality
$i_{{\Bbb P}^n(\overline{k})}(W_1,\ldots, W_\nu;E_j)=
i_{{\Bbb P}^n(\overline{k})}(W_1,\ldots, W_\nu,
{\cal Z}(L_{s+1},\ldots, L_n);$ $\xi)$ holds.
\item For an arbitrary point $z\in{\Bbb P}^n(\overline{k})$ (given in
form (11)) one can decide
whether $z\in E_j$, and more than that, compute the multiplicity
$\mu(z,E_j)$ of the
point $z$ at $E_j$.
\item Let us identify the set of all $(n+2)$--tuples of linear forms from
$\overline{k}[X_0,\ldots , X_n]$ with the affine space
${\Bbb A}^{(n+1)(n+2)}(\overline{k})$.
For every $j\in J$ and
an arbitrary  $\lambda^*=(L^*_0,\ldots , L^*_{n+1})$, where all
$L^*_j\in\overline{k}[X_0,\ldots , X_n]$ are linear forms, put
$\Xi^*_j=E_j\cap{\cal Z}(L_{s(j)+1},\ldots , L_n)\subset{\Bbb
P}^n(\overline{k})$.
Let ${\mathfrak l}\in{\Bbb A}^{(n+1)(n+2)}(\overline{k})$ be a line
defined over $k'$ such that $\overline{\lambda}=(L_0,\ldots , L_{n+1})
\in{\mathfrak l}$. Then for all $\lambda^*\in{\mathfrak l}(k')$
(here ${\mathfrak l}(k')$ is the set of all $k'$--points of ${\mathfrak l}$),
except at most a polynomial in $d^{n\nu}
(\sum_{1\le i\le\nu}a_i)\prod_{1\le\alpha\le\nu}b_\alpha$
number, assertion (a) holds with $\lambda^*,\Xi^*_j$, $j\in J$,
in place of $\overline{\lambda},\Xi_j$, $j\in J$. For every element
$\lambda^*\in{\mathfrak l}(k')$ one can decide whether
assertions (a) hold with $\lambda^*,\Xi^*_j$, $j\in J$,
in place of $\overline{\lambda},\Xi_j$, $j\in J$.
\end{enumerate}
The working time of
the algorithm for constructing linear forms $L_0,\ldots ,L_n$ and the family
of finite sets $\Xi_j$, $j\in J$, satisfying (a)
and also of the algorithm from assertion (b)
is polynomial
in $d^{n\nu}$, $\prod_{1\le \alpha\le\nu}b_\alpha$, and the sum of sizes
$\sum_{1\le \alpha\le\nu}{\rm L}((f_\alpha,L_\alpha,\Xi_\alpha,b_\alpha))$.
More precisely, this working time is polynomial in
$d^{n\nu}$, $\prod_{1\le\alpha\le\nu}b_\alpha$, $\sum_{1\le
\alpha\le\nu}a_\alpha$, $M$, $M_1$,
$d_1$, $d_2$, $\sum_{1\le \alpha\le\nu,\;1\le i\le a_\alpha}m(\alpha,i)$,
and
$$
\sum_{0\le s\le n,\;1\le \alpha\le\nu,\;1\le i\le a_\alpha}
{\rm L}(\Xi_\alpha^{(i,s)}),\quad
\sum_{0\le s\le n,\;s+1\le w\le n,\;
1\le \alpha\le\nu,\;1\le i\le a_\alpha}{\rm L}(L_{\alpha,w}^{(i,s)}).
$$
The working time of the algorithm from (c) (respectively (d))
is polynomial in the same values and the size ${\rm L}(z)$ of the point $z$
(respectively the size ${\rm L}(\lambda^*)$ of the element $\lambda^*$).
}\par\medskip


\par\medskip\noindent{\bf THEOREM~2}\hspace{0.1em} {\it  Assume that the
conditions of Theorem~1 hold, i.e., for every
$1\le\alpha\le\nu$ a representation
$(f_\alpha,L_\alpha,\Xi_\alpha,$ $b_\alpha)$ of a quasiprojective algebraic
variety $W_\alpha$ is given.
Let $\nu_1$ be an integer such that $1\le\nu_1\le\nu$.
Then one can construct linear forms $L_0,\ldots , L_{n+1}\in k[X_0,\ldots ,
X_n]$ with integer coefficients of
length $O(n\nu\log d+\sum_{1\le i\le\nu}\log b_i+
\log(\sum_{1\le i\le\nu}a_i))$, the finite set of indices
$J^{(1)}$ (respectively $J^{(2)}$), and for every $j\in J^{(1)}$
(respectively $j\in J^{(2)}$)
the finite set $\Xi_j$ of points
from $W_1\cap\ldots\cap W_{\nu_1}$ (respectively
$W_{\nu_1+1}\cap\ldots\cap W_\nu$)
such that the following assertions hold.
\begin{enumerate} \renewcommand{\labelenumi}{(\alph{enumi})}
\item For every $j\in J^{(1)}$ (respectively $j\in J^{(2)}$)
there is the unique defined over $k$ and
irreducible over $k$ component $E$ of
$W_1\cap\ldots\cap W_{\nu_1}$
(respectively $W_{\nu_1+1}\cap\ldots\cap W_\nu$) such that $\dim
E=n-s(j)$
and
$\Xi_j=E\cap{\cal Z}(L_{s(j)+1},\ldots,
L_n)$ in ${\Bbb P}^n(\overline{k})$.
Denote $E=E_j$.
Conversely, for every defined over
$k$ and irreducible over $k$ component $E'$ of
$W_1\cap\ldots\cap W_{\nu_1}$
(respectively $W_{\nu_1+1}\cap\ldots\cap W_\nu$)
there is $j'\in J^{(1)}$ (respectively $j'\in J^{(2)}$) such that
$E'=E_{j'}$.
Hence
$$
W_1\cap\ldots\cap W_{\nu_1}=\bigcup_{j\in
J^{(1)}}E_j\,, \qquad
W_{\nu_1+1}\cap\ldots\cap W_\nu=\bigcup_{j\in
J^{(2)}}E_j
$$
are the decompositions of $W_1\cap\ldots\cap W_{\nu_1}$ and
$W_{\nu_1+1}\cap\ldots\cap W_\nu$
into the unions of irreducible over $k$ components.
Let
$\overline{E}_j$ be the closure of $E_j$
with respect to the Zariski topology
in ${\Bbb P}^n(\overline{k})$.
Then for every $j\in J^{(1)}$ (respectively $j\in J^{(2)}$)
$$
\Xi_j\cap{\cal Z}(L_0)=\emptyset,\quad\#\Xi_j=
\#(L_{n+1}/L_0)(\Xi_j)=\deg\overline{E}_j,
\eqno (15)
$$
and
all the points of $\Xi_j$ are smooth points of $W_1\cap\ldots\cap W_{\nu_1}$
(respectively $W_{\nu_1+1}\cap\ldots\cap W_\nu$).
Put $A^{(1)}=\{1,\ldots ,\nu_1\}$, $A^{(2)}=\{\nu_1+1,\ldots ,\nu\}$.
Then for every $j\in J^{(i)}$, $i=1,2$ the variety
$$
E_j=\overline{E}_j\setminus
\Bigl(\,\bigcup_{\alpha\in A^{(i)}}\;\bigcup_{b_\alpha+1\le i\le a_\alpha}
W_\alpha^{(i)}\,\Bigr).
$$
\item One can decide for every $j_1\in J^{(1)}$ for every $j_2\in J^{(2)}$
whether $E_{j_1}\subset\overline{E}_{j_2}$.
More precisely, for the constructed linear
forms $L_0,\ldots, L_{n+1}$ the inclusion $E_{j_1}\subset\overline{E}_{j_2}$
holds if and only if $\Xi_{j_1}\subset\overline{E}_{j_2}$.
\item One can decide for every $j_1\in J^{(1)}$ for every $j_2\in J^{(2)}$
whether $E_{j_1}\subset E_{j_2}$.
\end{enumerate}
The working time of each of the algorithms from
this theorem is polynomial
in $d^{n\nu}$, $\prod_{1\le \alpha\le\nu}b_\alpha$, and the sum of sizes
$\sum_{1\le \alpha\le\nu}{\rm L}((f_\alpha,L_\alpha,\Xi_\alpha,b_\alpha))$.
More precisely, the considered working time is polynomial in
$d^{n\nu}$, $\prod_{1\le\alpha\le\nu}b_\alpha$, $\sum_{1\le
\alpha\le\nu}a_\alpha$, $M$, $M_1$,
$d_1$, $d_2$, $\sum_{1\le \alpha\le\nu,\;1\le i\le a_\alpha}m(\alpha,i)$,
and
$$
\sum_{0\le s\le n,\;1\le \alpha\le\nu,\;1\le i\le a_\alpha}
{\rm L}(\Xi_\alpha^{(i,s)}),\quad
\sum_{0\le s\le n,\;s+1\le w\le n,\;
1\le \alpha\le\nu,\;1\le i\le a_\alpha}{\rm L}(L_{\alpha,w}^{(i,s)}).
$$
}\par\medskip


As an immediate consequence of Theorem~2 we get the following result.

\par\medskip\noindent{\bf THEOREM~3}\hspace{0.1em} {\it  Assume that
representations
$(f_\alpha,L_\alpha,\Xi_\alpha,b_\alpha)$, $\alpha=1,2$ of two
quasiprojective algebraic variety $W_\alpha$ are given.
Then one can decide whether $W_1\subset W_2$. Hence one can decide also
whether $W_2\subset W_1$ and whether $W_1=W_2$.
The working time of this algorithm is polynomial in $d^n$
and the sizes
${\rm L}((f_\alpha,L_\alpha,\Xi_\alpha,b_\alpha))$
of the given representations of $W_\alpha$, $\alpha=1,2$.
}\par\medskip

\noindent{\bf PROOF}\quad Indeed by Theorem~2 one can decide whether
$W_1\subset W_2$ and
$W_2\subset W_1$. The theorem is proved (modulo Theorem~2).

\par\medskip\noindent{\bf THEOREM~4}\hspace{0.1em} {\it  One can construct a
smooth cover (respectively a smooth
stratification) $V_\alpha$,
$\alpha\in A$, of
the algebraic variety $V$ such that every
quasiprojective algebraic variety $V_\alpha$
is defined over $k$, irreducible over $k$, and
represented in the accepted way.
Let $\dim V_\alpha=n-s$ where $0\le s\le n$, and $s=s(\alpha)$
depends on $\alpha$.
Let (4) be the constructed representation of $V_\alpha$
(it depends on $\alpha$).
Denote
$h_{\alpha,j}=f^{(1)}_{j}$, $1\le j\le m(1)$, and
$\Delta_\alpha=f^{(2)}_{1}$ if $a\ge 2$, see (5).
Then the constructed representation of $V_\alpha$ satisfies the following
properties.
\begin{enumerate} \renewcommand{\labelenumi}{(\roman{enumi})}
\item The integer $b=1$. For the case of smooth cover $a=2$ if $s<n$, and
$a=1$ if $s=n$.
For the case of smooth stratification $a\le 2^{2^{n^{C}}}d^{n(n+1)/2}$
for an absolute constant $0<C\in {\Bbb R}$.
\item $m(1)=s$ and if $a\ge 2$ then $m(2)=1$. Hence if $a\ge 2$ then
$V_\alpha$ is an irreducible component of the algebraic variety
${\cal Z}(h_{\alpha,1},\ldots , h_{\alpha,s})
\setminus{\cal Z}(\Delta_\alpha)$ in the
case of the smooth cover
(respectively an open in the Zariski topology subset of
an irreducible component of the latter algebraic
variety in the case of smooth stratification).
\item There are linearly independent linear forms $Y_0,\ldots , Y_n\in
k[X_0,\ldots ,X_n]$ such that
$X_i=\sum_{0\le j\le n}x_{i,j}Y_j$, all the coefficients
$x_{i,j}\in k$,  all $x_{i,j}$ are integers with lengths
$O(2^{n^C}+n\log d)$
for an absolute constant $C>0$, and
$$
\Delta_\alpha=
\det(\partial h_{\alpha,i}/\partial Y_j)_{1\le i,j\le s}=
\det(\sum_{0\le v\le n}x_{v,j}
\partial h_{\alpha,i}/\partial X_v)_{1\le i,j\le s}.
$$
Hence $V_\alpha$ is a smooth algebraic variety by the
implicit function theorem.
Besides that, in the case of smooth cover
one can take $Y_i=X_{\sigma(i)}$ for some
permutation $\sigma$ of the set $0,\ldots , n$.
\item The lengths of integer coefficients of all linear forms from the
family $L$ is $O(2^{n^C}+n\log d)$
for an absolute constant $0<C\in {\Bbb R}$.
\item For all $\alpha\in A$,
$1\le j\le s(\alpha)$
degrees $\deg_{X_0,\ldots , X_n}h_{\alpha,j}$
are less than $n^{2^{s(\alpha)^{C}}}d$
for an absolute constant $0<C\in {\Bbb R}$.
In the case of smooth stratification for all $i>2$, $j$
degrees $\deg_{X_0,\ldots , X_n}f^{(i)}_{j}$
are less than $2^{2^{n^{C}}}d$.
\item For all $\alpha\in A$, $1\le j\le s(\alpha)$
lengths of coefficients of polynomials $h_{\alpha,j}$ are bounded from above
by a polynomial in
$n^{2^{s(\alpha)^{C}}}d^n$, $d_1$, $d_2$, $M$, $M_1$, $m$
for an absolute constant $0<C\in {\Bbb R}$.
Further, in the case of smooth stratification
lengths of coefficients of all polynomials from the family $f$ are bounded
from above by a polynomial in
$2^{2^{n^{C}}}d^n$, $d_1$, $d_2$, $M$, $M_1$, $m$
for an absolute constant $0<C\in {\Bbb R}$. The similar estimation holds
for
the size $L(\xi)$ of each point $\xi\in\Xi^{(i,s)}$ for all $i,s$, see
(7).
\item The number of elements $\# A$ of $A$ is bounded from above by
$2^{2^{n^{C}}}d^{n}$ for the case of smooth cover
(respectively $2^{2^{n^{C}}}d^{n(n+1)/2}$
for the case of smooth stratification)
for an absolute constant $0<C\in {\Bbb R}$.
\end{enumerate}
The working time of the algorithm for constructing the smooth cover
(respectively the smooth stratification) is polynomial in
$2^{2^{n^{C}}}d^n$, $d_1$, $d_2$, $M$, $M_1$, $m$
(respectively $2^{2^{n^{C}}}d^n$, $d_1$, $d_2$, $M$, $M_1$, $m$),
where $0<C\in {\Bbb R}$ is an absolute constant.
}\par\medskip

\noindent{\bf PROOF}\quad In Theorem~2 \cite{7} we prove the existence of
all the objects from the statement of Theorem~2.
According to Sections~2--5 of \cite{7} it is sufficient to use Theorem~1 and
Theorem~2
of the present paper to obtain the algorithms for the constructions
from proof of Theorem~2 \cite{7}.
More precisely, using Theorem~1 and Theorem~2 one can construct
immediately the algebraic
varieties arising from the proof of Theorem~2 \cite{7}.
We leave to the reader to repeat everything in details.

The required bounds for the working time of the algorithms from
Theorem~4 follow immediately from the ones for the applied algorithms.
The theorem is proved (modulo Theorem~1 and Theorem~2).

\medskip In the case when $k$ is a subfield of ${\Bbb R}$
Theorem~4 gives as an immediate consequence an algorithm for computing
dimension of a real algebraic variety $V({\Bbb R})$
within the time polynomial
in the size of input and $2^{2^{n^{C}}}d^n$, see Theorem~3 \cite{7}.
So we obtain one more proof of the last theorem.


\section{Proof of Theorem~1}\label{s1}

\par\medskip\noindent{\bf LEMMA~1}\hspace{0.1em} {\it  Let $V$ be a
projective algebraic variety in ${\Bbb
P}^n(\overline{k})$ such that all the irreducible components of $V$ have the
same dimension $n-s$ where $0\le s\le n$. Let $L_0,\ldots
,L_{n+1}\in\overline{k}[X_0,\ldots , X_n]$ be linear forms.
Denote $\Xi=V\cap{\cal Z}(L_{s+1},\ldots , L_n)$ in ${\Bbb
P}^n(\overline{k})$. Assume that for  $\overline{\lambda}=(L_0,\ldots
,L_{n+1})$ the following condition holds.
$$
{\cal Z}(L_s)\cap\Xi=\emptyset.
\eqno (16)
$$
Let us identify the set of all $(n+2)$--tuples of linear forms from
$\overline{k}[X_0,\ldots , X_n]$ with the affine space
${\Bbb A}^{(n+1)(n+2)}(\overline{k})$.
Let $\lambda^*=(L^*_0,\ldots , L^*_{n+1})\in
{\Bbb A}^{(n+1)(n+2)}(\overline{k})$, where all
$L^*_j\in\overline{k}[X_0,\ldots , X_n]$ are linear forms. Put
$\Xi^*=V\cap{\cal Z}(L_{s+1},\ldots , L_n)\subset{\Bbb
P}^n(\overline{k})$.
Let ${\mathfrak l}\in{\Bbb A}^{(n+1)(n+2)}(\overline{k})$ be a line
such that $\overline{\lambda}
\in{\mathfrak l}$. Then for all $\lambda^*\in{\mathfrak l}$,
except at most a polynomial in $2^{n-s+1}\deg V$
number, condition (16) holds for  $\lambda^*$ in place of
$\overline{\lambda}$, i.e., for $L^*_s,\Xi^*$
in place of $L_s,\Xi$.
}\par\medskip

\noindent{\bf PROOF}\quad Let
$\overline{\lambda}\ne\lambda^{(1)}=(L^{(1)}_0,\ldots,L^{(1)}_{n+1})
\in{\mathfrak l}$.
Then the B\'ezout theorem implies that for all $t\in\overline{k}$, except at
most polynomial
in $2^{n-s+1}\deg V$ number, the intersection
$V\cap{\cal Z}(L_j+tL^{(1)}_j,\,s\le j\le n)=\emptyset$ in ${\Bbb
P}^n(\overline{k})$, cf., e.g., the proof of Lemma~19 \cite{10}. The lemma is
proved.

\medskip Further, let $f_1,\ldots ,f_m$,
$V$, $W$, $s$, $\sigma$, $x^{(0)}$, $e_0,\ldots , e_r$, $p$,  ${\cal
U}'_0$, ${\cal U}''_0$, ${\cal U}'''_0$ are similar to the ones
from the statement of Theorem~1 \cite{10} and Theorem~2 \cite{10},
but we do not require at present that $\dim(W\cap{\cal Z}(e_0,\ldots ,
e_r))<\dim W$.

Notice that $\dim(W\cap{\cal Z}(e_0,\ldots ,
e_r))=\dim W$ is equivalent to $W\subset{\cal Z}(e_0,\ldots ,$ $e_r)$.
In this case $\sigma=n+1$, and
$p\, :\,\emptyset\rightarrow{\Bbb P}^r(\overline{k})$ is a trivial
morphism. Obviously one can decide
(directly or using Theorems~1~and~2 \cite{8})
whether $W\subset{\cal Z}(e_0,\ldots , e_r)$.

Let $L'_w\in\overline{k}[X_0,\ldots ,X_r]$, $w\in\{0,\sigma+1,\ldots , n\}$,
be a family of linear forms.
Put $L'_{n+1}=L'_0$. Set $L'=(L'_0,L'_{\sigma+1},\ldots , L'_n)$.


Recall that in \cite{10} for $V,W,p$
for every $\sigma\le i\le n+1$ the algebraic varieties
$W_i(L')=W(L'_{\sigma+1},\ldots , L'_i)$,
$W^{(\beta)}_i(L')=W^{(\beta)}(L'_{\sigma+1},\ldots , L'_i)$,  $\beta=1,2,3$,
are defined (for $i=\sigma$ they do not depend on $L'$).

{\it If $W\subset{\cal Z}(e_0,\ldots , e_r)$ then
by definition ${\cal U}'_0={\cal
U}''_0={\cal U}''_0$ is the set consisting of one element $L'=()$, and
$W_{n+1}(L')=\emptyset$, $W^{(1)}_{n+1}(L')=W$,
$W^{(2)}_{n+1}(L')=\emptyset$, $W^{(3)}_{n+1}(L')=\emptyset$.}


Put $\widetilde{e}_i=e'_i=L'_i(e_0,\ldots , e_r)$, $i\in\{\sigma+1,\ldots ,
n+1\}$, cf. the Introduction of \cite{10}.
For convenience of notation set $\widetilde{e}_\sigma=0$, the variety
$W_{\sigma-1}(L')=W$.
Hence now $W=W_{\sigma-1}(L')\cap{\cal
Z}(e'_\sigma)$.
Hence
$$
W_{i-1}(L')\cap{\cal Z}(\widetilde{e}_i)=W_i(L')\cup W^{(1)}_i(L')
\cup W^{(2)}_i(L')\cup W^{(3)}_i(L'),
\quad \sigma\le i\le n+1.
\eqno (17)
$$
When $i\ge\sigma+1$ and
$W\not\subset{\cal Z}(e_0,\ldots , e_r)$ equality (17) follows from
the Introduction of \cite{10}.

Assertions (a) and (b) of Theorem~1 \cite{10} are simplified in the case when
$W\subset{\cal Z}(e_0,\ldots , e_r)$. Namely,
let $\overline{\lambda}=(L_0,\ldots , L_{n+1})$
where all $L_w\in k[X_0,\ldots , X_n]$ are linear forms. {\it If
$W\subset{\cal Z}(e_0,\ldots , e_r)$ then
by definition we shall say that assertions (a) and (b) of Theorem~1 \cite{10}
hold for ($V,W$ and) $\overline{\lambda}$ if and only if
$\overline{\lambda}$
satisfies assertion of Theorem~3 \cite{10}
for $V,W$.} If
$W\subset{\cal Z}(e_0,\ldots , e_r)$ then one can construct
$\overline{\lambda}$ satisfying assertions (a) and (b) of Theorem~1 \cite{10}
using Theorem~3 \cite{10}.
Obviously, if $W\subset{\cal Z}(e_0,\ldots , e_r)$ then assertion
(g) of Theorem~1 \cite{10} remains true (its proof is just simplified).




Now let $N>0$ be an integer.
Suppose that $f^{(j)}_1,\ldots , f^{(j)}_{m(j)}
\in k[X_0,$ $\ldots , X_n]$, $V^{(j)}$, $W^{(j)}$, $s(j)$, $\sigma(j)$,
$x^{(0,j)}$,
$e^{(j)}_0,\ldots , e^{(j)}_r$,  $p^{(j)}$, ${\cal
U}'''_{j,0}$, for every $1\le j\le N$
are similar to the considered $f_1,\ldots ,f_m$,
$V$, $W$, $s$, $\sigma$, $x^{(0)}$, $e_0,\ldots , e_r$, $p$,  ${\cal
U}'''_0$
Hence we do not exclude that $W^{(j)}\subset{\cal Z}(e^{(j)}_0,\ldots,
e^{(j)}_r)$ for some $j$.

Let
$f^{(j)}_1,\ldots , f^{(j)}_{m(j)}$, $0\le j\le N$,
satisfy the same
estimations for degrees and lengths of coefficients as $f_1,\ldots ,f_m$
from Theorem~1 \cite{10} do.  Assume that $e^{(j)}_\alpha=e_\alpha$, $0\le
\alpha\le r$, are the same for all $1\le
j\le N$. Further, suppose that if $e_\alpha\ne 0$ then
$$
\deg_{X_0, \ldots, X_n} (e_\alpha)=d', \; \deg_{t_\gamma}(e_\alpha)<d'_2, \;
 {\rm l}(e_\alpha)<M',
$$
for all $1\le\gamma\le l$, $0\le \alpha\le r$,
i.e., $e_0,\ldots , e_r$ satisfy the
estimations for degrees and lengths of coefficients
from the statement of Theorem~1 \cite{10}.

Let us replace in the definitions of $W(L'_{\sigma+1},\ldots , L'_i)$,
$W^{(\beta)}(L'_{\sigma+1},\ldots , L'_i)$,  $\beta=1,2,3$, $\sigma\le
i\le n+1$,
the triple $(V,W,p)$ by $(V^{(j)},W^{(j)},p^{(j)})$
(hence the $\sigma$ is replaced by $\sigma(j)$; and
$L'_{\sigma(j)+1},\ldots , L'_{n+1}\in\overline{k}[X_0,\ldots ,X_r]$ are
linear forms, $L'_{n+1}=L'_0$).
Denote the obtained varieties by $W^{(j)}(L'_{\sigma(j)+1},\ldots , L'_i)$,
$W^{(j,\beta)}(L'_{\sigma(j)+1},\ldots , L'_i)$,  $\beta=1,2,3$,
$\sigma(j)+1\le i\le n+1$ respectively (since we shall not use $V,W,p$ in
what follows the
first notation $W^{(j)}(L'_{\sigma(j)+1},\ldots , L'_i)$ will not lead to an
ambiguity for $j\le 3$).


Put $e'_{j,i}=\widetilde{e}_i=L'_i(e_0,\ldots , e_r)$ for all
$i\in\{\sigma(j)+1,\ldots , n+1\}$, $1\le j\le N$.
For convenience of notation set $e'_{j,\sigma(j)}=0$, for every
$1\le j\le N$. Hence now
(17) holds for $V^{(j)},W^{(j)},p^{(j)}$ in place of  $V,W,p$.
(note that here $e'_{j,i}$ corresponds to $\widetilde{e}_i$).
Set $\iota=\iota(j,i)=i-\sigma(j)+s(j)$.




Put $\sigma=\min\{\sigma(j)\, :\, 1\le j\le N\}$
(we shall not use the old
$\sigma$ defined for $V,W,p,L'$ in what follows, and, hence,
this new definition
of $\sigma$ will not lead to an ambiguity of notation).
Put $L'=(L'_0,L'_{\sigma+1},\ldots , L'_n)$.
Further, denote for brevity $W^{(j)}_i(L')=W^{(j)}(L'_{\sigma(j)+1},\ldots ,
L'_i)$ and
$W^{(j,\beta)}_i(L')=W^{(j,\beta)}(L'_{\sigma(j)+1},\ldots ,$ $L'_i)$,
for all $\beta=1,2,3$, $\sigma(j)\le i\le n+1$.






\par\medskip\noindent{\bf LEMMA~2}\hspace{0.1em} {\it  Under considered
assumptions for $V^{(j)}$, $W^{(j)}$, $p^{(j)}$,
$1\le j\le N$, one can compute an element
$L'=(L'_0,L'_{\sigma+1},\ldots , L'_n)$
such that $(L'_0,L'_{\sigma(j)+1},\ldots,$ $L'_n)\in{\cal
U}'''_{j,0}$ for every $1\le j\le N$,
and all linear forms $L'_w$, $w\in\{0,\sigma+1,\ldots , n\}$
have integer coefficients of length $O(n\log d+(n-\sigma)\log d'+\log N)$.
Further, for this $L'$ one can construct linear forms
$L_0,\ldots , L_{n+1}$ with integer coefficients of length
$O(n\log d+(n-\sigma)\log d'+\log N)$ such that assertions (a) and (b) of
Theorem~1 \cite{10} holds for $V^{(j)}$ and
$(L'_0,L'_{\sigma(j)+1},\ldots, L'_n)$ in place of $V$ and
$(L'_0,L'_{\sigma+1},\ldots, L'_n)$
for all $0\le j\le N$ (i.e., linear forms
$L'_0,L'_{\sigma(j)+1},\ldots , L'_n$ and
$L_0,\ldots , L_{n+1}$ do not
depend on $j$;
other objects from the statement of this theorem for $V^{(j)}$ depend on
$j$).
Further, the linear forms $L_0,\ldots , L_{n+1}$
satisfy additionally the following conditions.
For all $x\in W_{i-1}^{(j)}(L')\cap
{\cal Z}(e'_{j,i})\cap{\cal Z}(L_{\iota(j,i)+1},\ldots , L_n)$
for all $1\le j,\,\beta\le N$ for all
$\sigma(j)\le i\le n+1$, $\sigma(\beta)\le\alpha\le n+1$
the multiplicity
\setcounter{equation}{17} \begin{eqnarray}
&&\mu(x,W^{(\beta)}_{\alpha-1}(L')\cap{\cal
Z}(e'_{\beta,\alpha}))=\nonumber \\
&&\min\{\mu(x',W^{(\beta)}_{\alpha-1}(L')\cap{\cal
Z}(e'_{\beta,\alpha}))\, :\, x'\in W^{(j)}_{i-1}(L')\cap{\cal
Z}(e'_{j,i})\}. \label{18}
\end{eqnarray}
In particular if $E_1$ (respectively $E_2$) is a defined over
$k$ and irreducible over $k$ component of
$W^{(j)}_{i-1}(L')\cap{\cal
Z}(e'_{j,i})$ (respectively of $W^{(\beta)}_{\alpha-1}(L')\cap{\cal
Z}(e'_{\beta,\alpha})$) such that $E_1\not\subset E_2$ then $x\not\in E_2$.
The working time of this algorithm is polynomial in $d^n(d')^{n-\sigma}$,
$d_1$, $d_2$, $M$, $M_1$, $m$, $N$ and
the sum of sizes $\sum_{0\le i\le N}{\rm L}(x^{(0,i)})$
of the points $x^{(0,i)}$.
}\par\medskip

\noindent{\bf PROOF}\quad  Applying Theorem~2 (a) \cite{10} we construct for
every $1\le j\le N$
an element $L^{(j)}\in{\cal U}'''_{j,0}$. Further, using
Theorem~2 (f) \cite{10}
and the algorithm of reduction to integer coefficients, see Proposition~2
\cite{9}, we construct an element
$L'=(L'_0,L'_{\sigma+1},\ldots , L'_n)$
such that all linear forms $L'_\alpha$,
$\alpha\in\{0,\sigma+1,\ldots , n\}$
have integer coefficients of length $O(n\log d+(n-\sigma)\log d'+\log N)$
and $(L'_0,L'_{\sigma(j)+1},\ldots, L'_n)\in{\cal
U}'''_{j,0}$ for every $1\le j\le N$.

Applying Theorem~1 \cite{10}
(and the remarks given above
in the case when $W^{(j)}\in{\cal Z}(e_0,\ldots , e_r)$)
we construct for
every $1\le j\le N$ an element
$\overline{\lambda}^{(j)}=(L^{(j)}_0,\ldots , L^{(j)}_{n+1})$
(similar $\overline{\lambda}$) satisfying assertions (a) and (b) of
Theorem~1 \cite{10}
for $(V^{(j)},W^{(j)},p^{(j)})$ in place of $(V,W,p)$.
Further, using  Theorem~1 (g) \cite{10}
and the algorithm of reduction to integer coefficients, see Proposition~2
\cite{9}, we construct an element
$\overline{\lambda}=(L_0,\ldots , L_{n+1})$ such that for this
$\overline{\lambda}$ the assertions of
Theorem~1 \cite{10} holds for $(V^{(j)},W^{(j)},p^{(j)})$ in place of
$(V,W,p)$
for all $0\le j\le N$.

Now we are going to describe a recursion with respect to $(L_0,\ldots
,L_{n+1})$.
The recursive assumption is that for all $0\le j\le N$ the assertions of
Theorem~1 \cite{10} hold for $(\overline{\lambda},V^{(j)},W^{(j)},p^{(j)})$
in place of $(\overline{\lambda},V,W,p)$, and
an integer $1\le w\le n$ is known
(the base of the recursion $w=n$) such that
for every $1\le j\le N$ for
every $\sigma(j)\le i\le n+1$
if $\iota=\iota(i,j)\ge w+1$ then
$$
W^{(j)}_{i-1}(L')\cap{\cal Z}(e'_{j,i})\cap{\cal Z}(L_\iota,\ldots ,
L_n)=\emptyset
\eqno (19)
$$
in ${\Bbb P}^n(\overline{k})$.
At the next step of the recursion using  Theorem~1 (g) \cite{10}, Lemma~1
and the algorithm of reduction to integer coefficients, see Proposition~2
\cite{9}, we construct the minimal possible integer $t_w>0$ such that the
formulated recursive assumption
holds for $w-1$ and
$(L_0,\ldots , L_w+t_wL_0,L_{w+1},\ldots , L_{n+1})$ in place of
$(L_0,\ldots ,L_{n+1})$.
By the estimates from Theorem~1 (g) \cite{10} and Lemma~1
the integer $t_w$ is of length $O(n\log d+(n-\sigma)\log d'+\log N)$.
After that we replace $L_0,\ldots ,L_{n+1}$ by $(L_0,\ldots ,
L_w+t_wL_0,L_{w+1},\ldots , L_{n+1})$.
If $w-1\ge 1$ we proceed to the next step of the recursion.
Thus, at the end of the recursion the recursive assumption holds with $w=0$.
Obviously (19) is satisfied also if $\iota(j,i)=0$.
Hence at the end of the recursion (19) is fulfilled
for every $1\le j\le N$ for
every $\sigma(j)\le i\le n+1$.

\medskip Further, for every $\sigma\le i\le n+1$ we define the linear
projection
$\varphi^{(i)}\, :\, {\Bbb P}^n(\overline{k})\setminus{\cal
Z}(L_0,L_{\iota+1},\ldots ,L_n)\rightarrow{\Bbb
P}^{n-\iota}(\overline{k})$,
$(X_0,\ldots , X_n)\mapsto(L_0:L_{\iota+1}:\ldots : L_n)$.
For every $\sigma(j)\le i\le n+1$
for every $1\le j\le N$ put
$\varphi^{(j)}_i$ to be the restriction of $\varphi^{(i)}$ to
$W^{(j)}_{i-1}(L')\cap{\cal Z}(e'_{j,i})$. Hence
$\varphi^{(j)}_i$ is a finite dominant
morphism by assertions (a) and (b) of Theorem~1 \cite{10} for
$V^{(j)},W^{(j)},p^{(j)}$ in place of
$V,W,p$. Let $z=(1:z_1:\ldots : z_n)\in{\Bbb P}^n(\overline{k})$ be a
point.
Denote for brevity
$P^{(j)}_i(z)=(\varphi^{(j)}_i)^{-1}((1:z_{\iota+1}:\ldots :
z_n))$.

Notice that $W^{(j)}_{i-1}(L')$ is a union of some
irreducible component of $V^{(j)}_{i-1}(L')=
{\cal Z}(f^{(a)}_1,\ldots ,
f^{(j)}_{m(j)},\,
L'_{\sigma(j)+1},\ldots , L'_{i-1})$. Hence applying Theorem~2 \cite{9}
to the set $U''={\cal Z}(e'_{j,i},L_{\iota+1}-z_{\iota+1}L_0,\ldots ,
L_n-z_nL_0)$
and after that Theorem~2 \cite{8} one can construct $P^{(j)}_i(z)$
(cf. also \cite{10} Section~5 where the algorithm for computing
$\varphi_i^{-1}((1:\nu_{\iota+1}:\ldots : N_n))$ is described).
Set
$$
\mu(z)=\sum_{1\le j,\,\beta\le N}\;\sum_{\sigma(j)\le i\le n+1}\;
\sum_{\sigma(\beta)\le\alpha\le n+1}\;
\sum_{x\in P^{(j)}_i(z)}
\mu(x,W^{(\beta)}_{\alpha-1}(L')\cap{\cal Z}(e'_{\beta,\alpha})).
$$
Therefore, according to Theorem~1 (e) \cite{10} one can compute $\mu(z)$
for a given $z$.
Our aim now is to construct a point $z$ with minimal possible $\mu(z)$.

Let us describe a new recursion with respect to $\overline{\lambda}$ and
$z=(1:z_1:\ldots : z_n)$. We take the constructed
$\overline{\lambda}=(L_0,\ldots , L_{n+1})$ and $z=(1:0:\ldots : 0)$
as the base of the new recursion.
The recursive assumption is that
linear forms $L_0,L_1-z_1L_0,\ldots , L_n-z_nL_0, L_{n+1}$
(in place of $L_0,\ldots , L_{n+1}$) satisfy
assertions (a) and (b)
of Theorem~1 \cite{10} for $(V^{(j)},W^{(j)},p^{(j)})$ in place of $(V,W,p)$
for all $0\le j\le N$ and, besides that (put $z_0=0$),
for every $1\le j\le N$ for
every $\sigma(j)\le i\le n+1$
$$
W^{(j)}_{i-1}(L')\cap{\cal Z}(e'_{j,i})\cap
{\cal Z}(L_{\iota(j,i)}-z_{\iota(j,i)}L_0,\ldots , L_n-z_nL_0)=\emptyset
\eqno (20)
$$
in ${\Bbb P}^n(\overline{k})$. Notice that (20) for the base of
the recursion follows from (19).
Further, (20) implies that for every $(i,j,\beta,\alpha,x)$ such that
$1\le j,\,\beta\le N$, $\sigma(j)\le i\le n+1$,
$\sigma(\beta)\le \alpha\le n+1$, $x\in P^{(j)}_i(z)$, and
$\dim W^{(j)}_{i-1}(L')\cap{\cal Z}(e'_{j,i})>
\dim W^{(\beta)}_{\alpha-1}(L')\cap{\cal Z}(e'_{\beta,\alpha})$
for every irreducible component $E_1$ of $W^{(j)}_{i-1}(L')\cap$\\ ${\cal
Z}(e'_{j,i})$
for every irreducible component $E_2$ of
$W^{(\beta)}_{\alpha-1}(L')\cap{\cal Z}(e'_{\beta,\alpha})$
the intersection
$$
(E_1\cap{\cal Z}(L_{\iota(j,i)+1}-z_{\iota(j,i)}L_0,\ldots ,
L_n-z_nL_0))\cap E_2=\emptyset.
$$




Let us describe the general step of this recursion.
We enumerate the  $5$--tuples $(i,j,\beta,\alpha,x)$ such that
$1\le j,\,\beta\le N$, $\sigma(j)\le i\le n+1$,
$\sigma(\beta)\le \alpha\le n+1$, $x\in P^{(j)}_i(z)$, and
$\dim W^{(j)}_{i-1}(L')\cap{\cal Z}(e'_{j,i})\le
\dim W^{(\beta)}_{\alpha-1}(L')\cap{\cal Z}(e'_{\beta,\alpha})$
(the last condition is equivalent to $\iota(j,i)\ge\iota(\beta,\alpha)$).

For the considered $(i,j,\beta,\alpha,x)$
we compute the set
$P^{(j)}_i(z)$, see above, and after that the integer $\mu(z)$.
Recall that for an arbitrary projective algebraic variety $E\subset{\Bbb
P}^n(\overline{k})$ we denote by $\mbox{\rm
con}(E)\subset{\Bbb A}^{n+1}(\overline{k})$ the
affine algebraic variety which is the set of all zeroes of the homogeneous
ideal of $E$ in ${\Bbb A}^{n+1}(\overline{k})$.

Applying Theorem~2 \cite{9}
to the variety $(\mbox{\rm
con}(V^{(j)}_{i-1}(L'))\times\mbox{\rm
con}(V^{(\beta)}_{\alpha-1}(L')))(\overline{k_2})$
we decide
whether there is a pair $(x'',x''')\in (W^{(j)}_{i-1}(L')\times
W^{(\beta)}_{\alpha-1}(L'))(\overline{k_2})$ such that
$$
\left\{
\begin{array}{ll}
\sum_{0\le w\le n}|(X_w/L_0)(x'')-(X_w/L_0)(x)|^2
\le\varepsilon_1,&\\
\varepsilon_2\le\sum_{0\le w\le n}|(X_w/L_0)(x'')-(X_w/L_0)(x''')|^2
\le\varepsilon_1,&\\
\varphi^{(\alpha)}(x'')=\varphi^{(\alpha)}(x'''), \\
e'_{j,i}(x'')=e'_{\beta,\alpha}(x''')=0,
\end{array}
\right.
\eqno (21)
$$
cf. system~(2) from \cite{4}.
If there does not exist such a pair $(x'',x''')$,
and not all $(i,j,\beta,\alpha,x)$ are enumerated then
we proceed to the next $(i,j,\beta,\alpha,x)$.
Suppose that there exists a pair $(x'',x''')\in (W^{(j)}_{i-1}(L')\times
W^{(\beta)}_{\alpha-1}(L'))(\overline{k_2})$ satisfying (21).
Then we compute
$\varphi^{(j)}_i(x'')=(1:z''_{\iota+1}:\ldots : z''_n)$ where all
$z''_w\in\overline{k_2}$. Put $z''_w=z'_w$ for $1\le \alpha\le\iota$ and
$z''=(1:z''_1:\ldots : z''_n)$.
Then $\mu(z'')<\mu(z')$.




It is not difficult to see, by e.g., \cite{4}, that
for every $\beta$ for every $\alpha$ for an arbitrary line
${\mathfrak l}\subset{\Bbb P}^n(\overline{k_2})$ and any point
$x^*\in{\mathfrak l}$ the number of elements
$x^{**}\in{\mathfrak l}$ with
$\mu(x^{**},W^{(\beta)}_{\alpha-1}(L')\cap{\cal
Z}(e'_{\beta,\alpha}))>
\mu(x^*,W^{(\beta)}_{\alpha-1}(L')\cap{\cal Z}(e'_{\beta,\alpha}))$
is bounded from above by
a polynomial in $d^n(d')^{n-\sigma}$, cf. also the proof of Lemma~1 \cite{7}.
Therefore, applying Theorem~1 (g) \cite{10}, Lemma~1 and
the algorithm of reduction to integer coefficients, see Proposition~2
\cite{9}, to the points $z''$ and $(1:0:\ldots : 0)$
one can construct
a point $\widetilde{z}=(1:\widetilde{z}_1:\ldots : \widetilde{z}_n)
\in{\Bbb P}^n(\overline{k})$
with integer $\widetilde{z}_w$ of length
$O(n\log d+(n-\sigma)\log d'+\log N)$ such that
for $\overline{\lambda}$ and $\widetilde{z}$
(in place of $\overline{\lambda}$ and $z$) the recursive assumption holds.
Then we replace $(\overline{\lambda},z)$ by
$(\overline{\lambda},\widetilde{z})$
and proceed to the next step of the recursion.

Finally we shall come to the case when for all
enumerated $5$--tuples $(i,j,\beta,\alpha,$ $x)$
there is no pair $(x'',x''')$ satisfying all the considered conditions.
Then \\
$\mu(x,W^{(\beta)}_{\alpha-1}(L')\cap{\cal
Z}(e'_{\beta,\alpha}))=\min\{\mu(x',W^{(\beta)}_{\alpha-1}(L')\cap{\cal
Z}(e'_{\beta,\alpha}))\, :\, x'\in W^{(j)}_{i-1}(L')\cap{\cal
Z}(e'_{j,i})\}$ for all $x\in P^{(j)}_i(z)$ for all
$1\le j,\,\beta\le N$,
$\sigma(j)\le i\le n+1$,  $\sigma(\beta)\le \alpha\le n+1$.
This step is final.
We replace $L_0,\ldots , L_{n+1}$ by $L_0,L_1-z_1L_0,\ldots ,
L_n-z_nL_0,L_{n+1}$ respectively.
Now the new $L_0,\ldots ,L_{n+1}$ satisfy
all the required conditions.

The required bound for the
working time of the described algorithm
follows immediately from the ones for the working times of the applied
algorithms. The lemma is proved.


\medskip Let us proceed to the proof of Theorem~1.
Let us show that the case $\nu=1$ is reduced to $\nu=2$.  Indeed, it is
sufficient to define
$m_\alpha(i)$,
$a_\alpha$, $b_\alpha$, $f_{\alpha,j}^{(i)}$, $W_\alpha$,
$V_\alpha$, $W_\alpha^{(i)}$, $V_\alpha^{(i)}$, $W_\alpha^{(i)}$,
$V_\alpha^{(i,s)}$, $W_\alpha^{(i,s)}$,
$L_{\alpha,\beta}^{(i,s)}$, $\Xi_\alpha^{(i,s)}$,
$(f_\alpha,L_\alpha,\Xi_\alpha,b_\alpha)=\rho_\alpha$ for $\alpha=2$ to
be the corresponding objects with $\alpha=1$, and apply Theorem~1 for
$\nu=2$.
Thus, we shall assume in what follows without loss of generality that
$\nu\ge 2$. Besides that, we shall assume also that $n\ge 1$.


Let $\rho=(f,L,\Xi,b)$ be representation (4).
We shall use the following notations. Put $n(\rho)=n$,
$a(\rho)=a$, $b(\rho)=b$,
$q_1(i,\rho)=V^{(i)}$, and
$q_2(i,\rho)=W^{(i)}$
for every $1\le i\le a=a(\rho)$. These functorial
notations $n(.)$, $a(.)$, $b(.)$,
$q_1(.,.)$ and $q_2(.,.)$ are used
also for other representations similar to (4).
Put the set
$$
B_1=\{(i_1,\ldots , i_\nu)\, :\, 1\le i_\alpha\le
b_\alpha\;\&\;i_\alpha\in{\Bbb Z}\;\&\;1\le\alpha\le\nu
\;\&\;\alpha\in{\Bbb Z}\}.
$$
Notice that
$$
\bigcap_{1\le\alpha\le\nu}W_\alpha=\Bigl(\,\bigcup_{(i_1,\ldots , i_\nu)\in
B_1}\;\bigcap_{1\le\alpha\le\nu}
W_\alpha^{(i_\alpha)}\,\Bigr)\setminus
\Bigl(\,\bigcup_{1\le\alpha\le\nu}\;\bigcup_{b_\alpha+1\le i\le a_\alpha}
W_\alpha^{(i)}\,\Bigr).
\eqno (22)
$$
Enumerating $c=1,2,\ldots$ let us construct the set of integers
${\cal C}$ such that for every $c\in{\cal C}$
the intersection
$$
\Bigl(\bigcup_{1\le\alpha\le\nu}\bigcup_{1\le j\le
a_\alpha}\Xi^{(j)}_\alpha\Bigr)\cap
{\cal Z}\Bigl(\sum_{0\le i\le n}c^iX_i\Bigr)=\emptyset
\eqno (23)
$$
in ${\Bbb P}^n(\overline{k})$, the number of elements
$$
\#{\cal C}=n\,\Bigl(d^{n\nu}\prod_{1\le\alpha\le\nu}b_\alpha+
d^n\sum_{1\le\alpha\le\nu}a_\alpha\Bigr)+n+1,
\eqno (24)
$$
and all the elements of ${\cal C}$ are minimal possible, i.e., the sum
$\sum_{c\in{\cal C}}c$ is minimal possible.
By the B\'ezout theorem the maximal element $\max{\cal C}$ of
${\cal C}$ is bounded from above by a polynomial in
$d^{n\nu}$,
$(\sum_{1\le\alpha\le\nu}a_\alpha)$, $\prod_{1\le\alpha\le\nu}b_\alpha$.
Put
$$
{\cal H}=\Bigl\{\,\sum_{0\le i\le n}c^iX_i\, :\, c\in{\cal
C}\,\Bigr\}.
$$
Hence ${\cal H}$ is a set of linear forms with integer coefficients.


For every $H\in{\cal H}$ we perform the following construction.
The defined below objects depends on $H$ although we do not indicate it
explicitly in the notations.
Let us identify ${\Bbb
P}^n(\overline{k})\setminus{\cal Z}(H)={\Bbb A}^n(\overline{k})$,
where ${\Bbb A}^n(\overline{k})$ has the coordinate functions
$Y_i=X_i/H$, $1\le i\le n$.
For every quasiprojective variety $E\subset{\Bbb P}^n(\overline{k})$ put
$\widetilde{E}=E\setminus{\cal Z}(H)\subset{\Bbb A}^n(\overline{k})$.
Below
for convenience we denote $\widetilde{W}_\alpha=\widetilde{W_\alpha}$ and so
on, i.e., we use tilde without taking into account upper and low indices.
This will not lead to an ambiguity. Now (22) implies
$$
\bigcap_{1\le\alpha\le\nu}\widetilde{W}_\alpha=
\Bigl(\,\bigcup_{(i_1,\ldots , i_\nu)\in B_1}\;\bigcap_{1\le\alpha\le\nu}
\widetilde{W}_\alpha^{(i_\alpha)}\,\Bigr)\setminus
\Bigl(\,\bigcup_{1\le\alpha\le\nu}\bigcup_{b_\alpha+1\le i\le a_\alpha}
\widetilde{W}_\alpha^{(i)}\,\Bigr).
\eqno (25)
$$

Let us identify ${\Bbb A}^{n\nu}(\overline{k})=({\Bbb
A}^n(\overline{k}))^\nu$, where for every  $1\le i\le\nu$ the  $i$-th
factor
${\Bbb A}^n(\overline{k})$ of ${\Bbb A}^{n\nu}(\overline{k})$
in the left part of the last equality has
the coordinate functions
$Y_{i,j}$, $1\le j\le n$. Hence  ${\Bbb A}^{n\nu}(\overline{k})$
has the coordinate functions $Y_{i,j}$, $1\le i\le\nu$, $1\le j\le n$.
Put $\Delta=\{(x,x,\ldots , x)\in{\Bbb A}^{n\nu}(\overline{k})\, :\,
x\in{\Bbb A}^n(\overline{k})\}$ to be the diagonal subvariety,
cf. the Introduction.

Let us identify ${\Bbb A}^{n\nu}(\overline{k})\subset
{\Bbb P}^{n\nu}(\overline{k})$, where ${\Bbb P}^{n\nu}(\overline{k})$
has the homogeneous coordinate functions $X_{0,0}$, $X_{i,j}$, $1\le
i\le\nu$, $1\le j\le n$,
and all $Y_{i,j}=X_{i,j}/X_{0,0}$. Put $\overline{\Delta}$ to be the closure
of $\Delta$ in ${\Bbb P}^{n\nu}(\overline{k})$ with respect to the
Zariski
topology.

Further, we assume that the identification (12) holds.
Hence (12) implies $\bigcap_{1\le\alpha\le\nu}
\widetilde{W}_\alpha^{(i_\alpha)}=(\prod_{1\le\alpha\le\nu}
\widetilde{W}_\alpha^{(i_\alpha)})\cap\Delta$
for every $(i_1,\ldots , i_\nu)\in B_1$, and
$\widetilde{W}_\alpha^{(i)}=(\widetilde{W}_\alpha^{(i)})^\nu\cap\Delta$
for all $b_\alpha+1\le i\le a_\alpha$, $1\le\alpha\le\nu$.
Notice that the intersection $\bigcap_{1\le\alpha\le\nu}
\widetilde{W}_\alpha^{(i_\alpha)}$ is transversal if and only if the
intersection $(\prod_{1\le\alpha\le\nu}
\widetilde{W}_\alpha^{(i_\alpha)})\cap\Delta$ is transversal,
and in this case
$\deg\bigcap_{1\le\alpha\le\nu}
\widetilde{W}_\alpha^{(i_\alpha)}=\deg\prod_{1\le\alpha\le\nu}
\widetilde{W}_\alpha^{(i_\alpha)}=\prod_{1\le\alpha\le\nu}\deg
\widetilde{W}_\alpha^{(i_\alpha)}$. In the general case the inequality
$\deg\bigcap_{1\le\alpha\le\nu}
\widetilde{W}_\alpha^{(i_\alpha)}\le\deg\prod_{1\le\alpha\le\nu}
\widetilde{W}_\alpha^{(i_\alpha)}$ holds.


For every $(i_1,\ldots , i_\nu)\in B_1$ denote
\begin{eqnarray*}
&&V_{i_1,\ldots ,
i_\nu}=\prod_{1\le\alpha\le\nu}\widetilde{V}^{(i_\alpha)}_\alpha
\subset{\Bbb A}^{n\nu}(\overline{k}),\\
&&W_{i_1,\ldots , i_\nu}=
\prod_{1\le\alpha\le\nu}\widetilde{W}^{(i_\alpha)}_\alpha
\subset V_{i_1,\ldots , i_\nu}. \\
\end{eqnarray*}
Hence $V_{i_1,\ldots , i_\nu}$ is an affine algebraic variety
given by a system of polynomial equations with respect to $Y_{i,j}$, $1\le
i\le\nu$, $1\le j\le n$, and
$W_{i_1,\ldots , i_\nu}$ is
a union of some irreducible components of $V_{i_1,\ldots , i_\nu}$.
Denote by $\overline{V}_{i_1,\ldots , i_\nu}$ (respectively
$\overline{W}_{i_1,\ldots , i_\nu}$) the
closure of
$V_{i_1,\ldots , i_\nu}$ (respectively of $W_{i_1,\ldots , i_\nu}$) with
respect to the Zariski topology  in
${\Bbb P}^{n\nu}(\overline{k})$.
Hence $\overline{V}_{i_1,\ldots , i_\nu}$ is a projective algebraic variety
given by a system of polynomial equations with respect to $X_{0,0}$,
$X_{i,j}$, $1\le i\le\nu$, $1\le j\le n$, and
$\overline{W}_{i_1,\ldots , i_\nu}$ is
a union of some irreducible components of $V_{i_1,\ldots , i_\nu}$.


Let $\overline{V}_{i_1,\ldots , i_\nu}\cup{\cal Z}(X_{0,0})=
\bigcup_{j\in J'_{i_1,\ldots , i_\nu}}E_j$ be the decomposition into the
union
of defined over $k$ and irreducible over $k$ components $E_j$, $j\in
J'_{i_1,\ldots , i_\nu}$.

For every $(i_1,\ldots, i_\nu)\in B_1$ we apply Theorem~1 \cite{8} to the
algebraic variety
$\overline{V}_{i_1,\ldots , i_\nu}\cup{\cal Z}(X_{0,0})$ (in place of
$V$)
and construct for every $j\in J'_{i_1,\ldots , i_\nu}$ a representation
$\rho_j$ similar to (4)
of the irreducible component $E_j$ such that
$n(\rho_j)=n\nu$, $a(\rho_j)=b(\rho_j)=1$,
$q_1(1,\rho_j)=\overline{V}_{i_1,\ldots , i_\nu}\cup{\cal Z}(X_{0,0})$
and $q_2(1,\rho_j)=E_j$.
Put $\Xi_{i_1,\ldots,
i_\nu}=\prod_{1\le\alpha\le\nu}\Xi^{(i_\alpha)}_\alpha\subset
{\Bbb A}^{n\nu}(\overline{k})\subset{\Bbb P}^{n\nu}(\overline{k})$.
By (23) for every irreducible component $E$ of $\overline{V}_{i_1,\ldots
, i_\nu}\cup{\cal Z}(X_{0,0})$ the
intersection $E\cap\Xi_{i_1,\ldots,
i_\nu}\ne\emptyset$ if and only if $E$ is an irreducible component of
$\overline{W}_{i_1,\ldots , i_\nu}$,
i.e. the finite set $\Xi_{i_1,\ldots,i_\nu}$
gives $\overline{W}_{i_1,\ldots, i_\nu}$ as the
union of some irreducible components of $\overline{V}_{i_1,\ldots ,
i_\nu}\cup{\cal Z}(X_{0,0})$.
Now using Theorem~2 \cite{8} we construct the
subset $J_{i_1,\ldots , i_\nu}\subset J'_{i_1,\ldots , i_\nu}$ such that
$$
\overline{W}_{i_1,\ldots, i_\nu}=
\bigcup_{j\in J_{i_1,\ldots , i_\nu}}E_j.
$$
Notice that $E_j\not\subset{\cal Z}(X_{0,0})$ for every $j\in
J_{i_1,\ldots, i_\nu}$
for every $(i_1,\ldots , i_\nu)\in B_1$.


Set $a'_1=a_1+\#{\cal C}$. Let
$H_j$, $a_1+1\le j\le a'_1$, be the family of linear forms such
that the set $\{H_j\, :\,
a_1+1\le j\le a'_1\}={\cal H}$. Put
$V^{(j)}_1=W^{(j)}_1={\cal Z}(H_j)$
for every $a_1+1\le j\le a'_1$.


Put
$$
B_2=\{(\alpha,i)\, :\, 1\le\alpha\le\nu\;\&\;\alpha\in{\Bbb
Z}\;\&\;b_\alpha+1\le i\le
a_\alpha\;\&\;i\in{\Bbb
Z}\}
$$
and $B'_2=B_2\cup\{(1,i)\, :\,a_1+1\le
i\le a'_1\}$. Hence $B_2\subset B'_2$.
Set for every $(\alpha,i)\in B'_2$
\begin{eqnarray*}
&&V_{\alpha;i}=(\widetilde{V}^{(i)}_\alpha)^\nu\subset{\Bbb
A}^{n\nu}(\overline{k}) \\
&&W_{\alpha;i}=(\widetilde{W}^{(i)}_\alpha)^\nu
\subset V_{\alpha;i}.
\end{eqnarray*}
Hence $V_{\alpha;i}$ is an affine algebraic variety
given by a system of polynomial equations with respect to $Y_{i,j}$, $1\le
i\le\nu$, $1\le j\le n$, and
$W_{\alpha;i}$ is
a union of some irreducible components of $V_{\alpha;i}$.
Denote by $\overline{V}_{\alpha;i}$ (respectively
$\overline{W}_{\alpha;i}$) the
closure of
$V_{\alpha;i}$ (respectively of $W_{\alpha;i}$) with respect to the Zariski
topology in
${\Bbb P}^{n\nu}(\overline{k})$.
Hence $\overline{V}_{\alpha;i}$ is a projective algebraic variety
given by a system of polynomial equations with respect to $X_{0,0}$,
$X_{i,j}$, $1\le i\le\nu$, $1\le j\le n$, and
$\overline{W}_{\alpha;i}$ is
a union of some irreducible components of $\overline{V}_{\alpha;i}$.




Let $\overline{V}_{\alpha;i}\cup{\cal Z}(X_{0,0})=
\bigcup_{j\in J'_{\alpha;i}}E_j$ be the decomposition into the
union
of defined over $k$ and irreducible over $k$ components $E_j$, $j\in
J'_{\alpha;i}$.

For every $(\alpha,i)\in B'_2$ we apply Theorem~1 \cite{8} to the
algebraic variety
$\overline{V}_{\alpha;i}\cup{\cal Z}(X_{0,0})$ (in place of
$V$)
and construct for every $j\in J'_{\alpha;i}$
a representation $\rho_j$ similar to (4)
of the irreducible component $E_j$ such that
$n(\rho_j)=n\nu$, $a(\rho_j)=b(\rho_j)=1$,
$q_1(1,\rho_j)=\overline{V}_{\alpha;i}\cup{\cal
Z}(X_{0,0})$ and $q_2(1,\rho_j)=E_j$.
Since $\Xi^{(j)}_\alpha$ for all $1\le\alpha\le\nu$, $1\le j\le a_\alpha$,
are known we are able to construct the set $\Xi_{\alpha;i}$ of smooth points
of $\overline{V}_{\alpha;i}\cup{\cal
Z}(X_{0,0})$ satisfying the following property.
For every irreducible component $E$ of $\overline{V}_{\alpha;i}\cup{\cal
Z}(X_{0,0})$ the intersection $\Xi_{\alpha;i}\cap E\ne\emptyset$ if and only
if $E$ is an irreducible component of
$\overline{W}_{\alpha;i}$.
After that using Theorem~2 \cite{8} we construct a
subset $J_{\alpha;i}\subset J'_{\alpha;i}$ such that
$$
\overline{W}_{\alpha;i}=
\bigcup_{j\in J_{\alpha;i}}E_j.
$$
Notice that $E_j\not\subset{\cal Z}(X_{0,0})$ for every $j\in
J_{\alpha;i}$
for every $(\alpha,i)\in B'_2$.

Let us construct also the representation $\rho_{j_{0,0}}$ such that
$n(\rho_{j_{0,0}})=n\nu$, \\
$a(\rho_{j_{0,0}})=b(\rho_{j_{0,0}})=1$,
$q_1(\rho_{j_{0,0}})=q_2(\rho_{j_{0,0}})={\cal
Z}(X_{0,0})$.

To simplify the notation we shall assume without loss of generality that
\begin{itemize}
\item for all $(i_1,\ldots , i_\nu)\in B_1$, $(i'_1,\ldots , i'_\nu)\in B_1$
if $(i_1,\ldots , i_\nu)\ne(i'_1,\ldots , i'_\nu)$ \\ then
$J_{i_1,\ldots , i_\nu}\cap J_{i'_1,\ldots , i'_\nu}=\emptyset$,
\item for all $(i_1,\ldots , i_\nu)\in B_1$, $(\alpha,i)\in B'_2$
the intersection $J_{i_1,\ldots , i_\nu}\cap J_{\alpha;i}=\emptyset$,
\item for all $(\alpha,i)\in B'_2$, $(\alpha',i')\in B'_2$ if
$(\alpha,i)\ne(\alpha',i')$ then
$J_{\alpha;i}\cap J_{\alpha';i'}=\emptyset$,
\end{itemize}
replacing if it is necessarily the considered sets of indices for new ones.
Put
\begin{eqnarray*}
&&J_1=\bigcup_{(i_,\ldots , i_\nu)\in B_1}J_{i_1,\ldots , i_\nu},
\quad J'_2=\bigcup_{(\alpha,i)\in B'_2}J_{\alpha;i},
\quad J'_0=\{j_{0,0}\}\cup J_1\cup J'_2,\\
&&J_2=\bigcup_{(\alpha,i)\in B_2}J_{\alpha;i},
\quad J_0=J_1\cup J_2,
\end{eqnarray*}
Besides that, we shall suppose in what follows without loss of generality
that $J'_0\cap{\Bbb Z}=\emptyset$, i.e., that each element of $J'_0$
is not an integer. Denote $V^{(j)}=q_1(1,\rho_j)$, $W^{(j)}=q_2(1,\rho_j)$
for all $j\in J'_0$.

Set $r=n(\nu-1)-1$, and $e_0,\ldots , e_r$ to be the family of polynomials
$X_{1,i}-X_{w,i}$, $2\le w\le\nu$, $1\le i\le n$ (we choose an arbitrary
linear order on the elements of the last family
to obtain $e_0,\ldots , e_r$).
Notice that $\overline{\Delta}={\cal Z}(e_0,\ldots , e_r)$. More
than that, $e_0,\ldots , e_r$ generate the homogeneous ideal of
$\overline{\Delta}\subset{\Bbb P}^{n\nu}(\overline{k})$,
and $\dim\overline{\Delta}=n\nu-r-1$.
Denote by $\delta\,:\,{\Bbb P}^{n\nu}(\overline{k})\setminus{\cal
Z}(e_0,\ldots , e_r)\rightarrow
{\Bbb P}^r(\overline{k})$, $(X_0:\ldots : X_n)\mapsto(e_0:\ldots : e_r)$
the morphism of the linear projection.
Denote by $p^{(j)}\, :\, W^{(j)}\setminus{\cal
Z}(e_0,\ldots , e_r)\rightarrow{\Bbb P}^r(\overline{k})$ the
restriction of $\delta$ to $W^{(j)}\setminus{\cal
Z}(e_0,\ldots , e_r)$ for every
$j\in J'_0$. Note that if  $W^{(j)}\subset\overline{\Delta}$ then $\dim
W^{(j)}=0$
(but, of course, not conversely).

Let $j\in J'_0$ and $\sigma(j)\le i\le n\nu+1$.
Now $W^{(j)}_i(L'')$ (respectively $W^{(j,\beta)}_i(L'')$, $\beta=1,2,3$) is
a projective algebraic subvariety of ${\Bbb P}^{n\nu}(\overline{k})$,
and the dimension of every irreducible component of
$W^{(j)}_i(L'')$ (respectively $W^{(j,\beta)}_i(L'')$)
is $n\nu-\iota(j,i)=n\nu-i+\sigma(j)-s(j)$, see the
Introduction of \cite{10} and the beginning of the section.



Notice that at present for all $j\in J'_0$ and $\sigma(j)\le i\le
n\nu+1$ the algebraic variety $W^{(j,3)}_i(L')=\emptyset$ since
$L''\in{\cal U}''_{j,0}$, see \cite{10}. Further, for every
$j\in J'_0$
$$
\bigcup_{\sigma(j)\le i\le
n\nu+1}W^{(j,1)}_i(L'')=W^{(j)}\cap\overline{\Delta},
\eqno (26)
$$
again since
$L''\in{\cal U}''_{j,0}$ (recall that ${\cal U}'''_{j,0}
\subset{\cal U}''_{j,0}$),
see the Introduction of \cite{10}. We denote in this case $W^{(j,1)}_i(L'')=
W^{(j,1)}_i$.



Now we are going to apply Lemma~2 with  $N=\#J'_0$ and the set of indices
$j\in J'_0$ in place of $j\in\{1,\ldots , N\}$. We replace also  $(n,\sigma)$
by $(n\nu,\sigma_1)$. At present
all the other objects from the statement of this lemma are defined in
the natural way using the representations $\rho_j$, $j\in J'_0$.

Thus, applying Lemma~2 we get linear forms $L''_0,L''_{\sigma_1+1},\ldots ,
L''_{n\nu}\in k[X_0,\ldots ,$ $X_r]$
in place of $L'_0,L'_{\sigma+1},\ldots, L'_n$. Set
$L''=(L''_0,L''_{\sigma_1+1},\ldots,
L''_{n\nu})$ and $e''_{j,w}=e''_w=L''_w(e_0,\ldots , e_r)$
(recall that $L''_{n\nu+1}=L''_0$,
see the Introduction of \cite{10}), and $e''_{j,\sigma(j)}=0$
for all $w\in\{0,\sigma(j)+1,\ldots , n\nu+1\}$ and $j\in J'_0$.
Further, we construct linear forms
and  $L'''_0,\ldots , L'''_{n\nu+1}\in
k[X_{0,0},X_{i,j},\,1\le j\le\nu,\,1\le i\le n]$ in place of $L_0,\ldots
,L_{n+1}\in k[X_0,\ldots , X_n]$.
We have replaced the notation $L'_j$ by $L''_j$ (respectively $L_w$ by
$L'''_w$) to avoid an ambiguity in
what follows.

Applying Theorem~1 \cite{10} let us construct for every $j\in J'_0$ for every
$\sigma(j)-1\le i\le n\nu+1$ the finite sets
\begin{eqnarray*}
&&A^{(j)}_i=W^{(j)}_{i-1}(L'')\cap{\cal Z}(e''_{j,i})\cap{\cal
Z}(L'''_{\iota(j,i)+1},\ldots , L'''_{n\nu}), \\
&&A^{(j,1)}_i=W^{(j,1)}_i\cap{\cal
Z}(L'''_{\iota(j,i)+1},\ldots , L'''_{n\nu}).
\end{eqnarray*}


Let $E$ be a defined over $k$ and irreducible over $k$ component of
$W^{(j,1)}_i$ with $j\in J'_0$ and $\sigma(j)\le i\le
n\nu+1$. According to Lemma~2 an irreducible component $E\subset{\cal
Z}(X_{0,0})$
if and only if $E\cap{\cal Z}(L'''_{\iota+1},\ldots ,
L'''_{n\nu})\subset{\cal Z}(X_{0,0})$.
Put for every $j\in J_0$
\begin{eqnarray*}
&&D(H,j)=\deg
(W^{(j)}\cap\overline{\Delta}\setminus{\cal Z}(X_{0,0}))=\\
&&\sum_{\sigma(j)\le i\le n\nu+1}\deg
(W^{(j,1)}_i\setminus{\cal Z}(X_{0,0}))
=\sum_{\sigma(j)\le i\le n\nu+1}\#(A^{(j,1)}_i\setminus{\cal
Z}(X_{0,0})).
\end{eqnarray*}
Let us compute $D(H,j)$
by the previous formula for every $j\in J_0$,
and after that $D(H)=\sum_{j\in J_0}D(H,j)$.

We construct the subset ${\cal H}_0\subset{\cal H}$ such that
$D(H')=\max\{D(H)\,
:\, H\in{\cal H}\}$ for every $H'\in{\cal H}_0$. We claim that
\begin{enumerate} \renewcommand{\labelenumi}{(\alph{enumi})}
\item for every $H\in{\cal H}_0$
for every $(i_1,\ldots , i_\nu)\in B_1$ for each defined over $k$ and
irreducible over $k$ component $E_\alpha$ of
$V^{(i_\alpha)}_\alpha$, $1\le\alpha\le\nu$,
the inclusion
$\bigcap_{1\le\alpha\le\nu}\widetilde{E}_\alpha\subset
\bigcap_{1\le\alpha\le\nu}E_\alpha$ induces the one--to--one
correspondence between the defined
over $k$ and irreducible over $k$
components of the algebraic varieties
$\bigcap_{1\le\alpha\le\nu}\widetilde{E}_\alpha$ and
$\bigcap_{1\le\alpha\le\nu}E_\alpha$,
\item the number of elements $\#{\cal H}_0\ge n+1$.
\end{enumerate}
Indeed, the required assertion follows from the B\'ezout theorem and the
fact that for every nonempty projective algebraic
variety ${\cal V}\subset{\Bbb P}^n(\overline{k})$ there are at most
$n$ distinct linear forms $H\in{\cal H}$ such that
${\cal V}\subset{\cal Z}(H)$.
Let us construct a subset ${\cal H}_1\subset{\cal H}_0$ such that
the number of elements $\#{\cal H}_1=n+1$.




Further, for every $H\in{\cal H}_1$ we perform the following
construction. Let $E$ be a defined over $k$ and irreducible over $k$
component of $W^{(j,1)}_i$ with $j\in J_0$
and $\sigma(j)\le i\le n\nu+1$. Let $\dim E=n\nu-\iota$.
Then
$$
E\cap{\cal Z}(L'''_{\iota+1},\ldots , L'''_{n\nu})=\Xi_E\subset
A^{(j,1)}_i,
$$
and $\iota=i-\sigma(j)+s(j)$. Notice that $E\not\subset{\cal
Z}(X_{0,0})$ by property (a).
We identify
$$
E\setminus{\cal Z}(X_{0,0})\subset
{\Bbb A}^{n\nu}(\overline{k})\cap\Delta={\Bbb
A}^n(\overline{k})={\Bbb P}^n(\overline{k})\setminus{\cal
Z}(H)\subset{\Bbb P}^n(\overline{k})
\eqno (27)
$$
using isomorphism (12).
For all $j\in J_0$ let us construct all such subsets $\Xi_E$ applying
assertions (a) and (b)
of Theorem~1 \cite{10}.
Note also that under identifying (27) the intersection $\Xi_E\cap
\bigl(\bigcup_{H\in{\cal H}_1}{\cal Z}(H)\bigr)=\emptyset$ by
the choice of $(V_{1;i},W_{1;i})$, $a_1+1\le i\le a'_1$, and Lemma~2.



{\it Let $J'\subset J_0$ be a subset.
We shall say that a defined over $k$ and irreducible over $k$ component $E$
of $W^{(j)}\cap\overline{\Delta}$ with
$j\in J'$ is maximal with respect to $J'$ if and only if for every
$j'\in J'$ for every defined over $k$ and irreducible over $k$ component
$E'$ of $W^{(j')}\cap\overline{\Delta}$ the inclusion $E\subset E'$ implies
the equality $E=E'$.
}


Let $E_\gamma$, $\gamma=1,2$, be a defined over $k$ and irreducible over $k$
component of $W^{(j_\gamma)}\cap\overline{\Delta}$ with $j_\gamma\in J_0$
and $E_\gamma\not\subset{\cal Z}(X_{0,0})$.
According to Lemma~2 an irreducible component $E_1\subset E_2$
if and only if $\Xi_{E_1}\subset E_2$.

Hence applying Theorem~1 \cite{10}
one can construct the sets $\Xi_j$, $j\in I_1$ (respectively $\Xi_j$,
$j\in I_2$), such that
\begin{itemize}
\item for every $j\in I_1$ (respectively $j\in I_2$)
the set $\Xi_j=\Xi_E$ for a defined over $k$ and
irreducible over $k$ component $E$ of
$W^{(j')}\cap\overline{\Delta}$ with $j'\in J_1$ (respectively $j'\in J_2$)
such that $E$ is maximal
with respect to $J_0$ (respectively with respect to $J_2$)
and $E\not\subset{\cal Z}(X_{0,0})$.
\item conversely, for every $j'\in J_1$
(respectively $j'\in J_2$) for every defined over $k$ and
irreducible over $k$ component $E$ of $W^{(j')}\cap\overline{\Delta}$
such that $E$ is maximal
with respect to $J_0$ (respectively with respect to $J_2$)
and $E\not\subset{\cal Z}(X_{0,0})$
there is $j\in I_1$ (respectively $j\in I_2$) with
$\Xi_j=\Xi_E$,
\item for all $j_1,j_2\in I_1$
(respectively $j_1,j_2\in I_2$) if $j_1\ne j_2$ then
$\Xi_{j_1}\ne\Xi_{j_2}$.
\end{itemize}
For every $j\in I_1\cup I_2$ put $\overline{E}_j=\overline{E}$, where
$\Xi_j=\Xi_E$ and $\overline{E}$
is the the closure of $E\setminus{\cal Z}(X_{0,0})$ in
${\Bbb P}^n(\overline{k})$ with respect to the Zariski topology by
inclusion (27).
We identify $\Xi_j\subset{\Bbb P}^n(\overline{k})$ by (27).
Now $\overline{E}_j$, $j\in I_1$ (respectively $\overline{E}_j$, $j\in I_2$)
is the family
of all the defined over $k$ and irreducible over $k$ components of
$\bigcup_{(i_1,\ldots , i_\nu)\in B_1}\bigcap_{1\le\alpha\le\nu}
W^{(i_\alpha)}_\alpha$ (respectively
$\bigcup_{1\le\alpha\le\nu}\;\bigcup_{b_\alpha+1\le i\le a_\alpha}
W_\alpha^{(i)}$) by Lemma~2, by property (a) and since $H\in{\cal
H}_1\subset{\cal H}_0$.


Let $j_1\in I_1$, $j_2\in I_2$.
Let ${\Bbb P}^{n\nu}(\overline{k})\supset E_\gamma\setminus{\cal
Z}(X_{0,0})=E_{j_\gamma}\setminus{\cal Z}(H)$, $\gamma=1,2$, according to
(27).
Again applying Theorem~1 \cite{10} we
decide for every $j_1\in I_1$ for every $j_2\in I_2$ whether
$\Xi_{E_1}\subset E_2$. It is equivalent to $\Xi_{j_1}\subset
\overline{E}_{j_2}$ and also to
$\overline{E}_{j_1}\subset\overline{E}_{j_2}$
by Lemma~2. Thus, we construct the subset
$$
J=\{j\in I_1\, :\, \Xi_j\not\subset
\overline{E}_{j_2}\quad\mbox{for all}\quad j_2\in I_2\}.
$$
Hence by Lemma~2
for every $j\in J$ for every $j_2\in J_2$ the set $\Xi_j\not\subset
W^{(j_2)}\cap\overline{\Delta}$.
For every $j\in J$ denote
$$
E_j=\overline{E}\setminus
\Bigl(\,\bigcup_{1\le\alpha\le\nu}\;\bigcup_{b_\alpha+1\le i\le a_\alpha}
W_\alpha^{(i)}\,\Bigr),
$$
where $E$ is a defined over $k$ and irreducible over $k$ component of
$W^{(j_1)}\cap\overline{\Delta}$ for some $j_1\in J_1$ such that the set
$\Xi_j=\Xi_E$, and $\overline{E}$ is defined above.
Now $E_j$, $j\in J$
is the family
of all the defined over $k$ and irreducible over $k$ components of
$W_1\cap\ldots\cap W_\nu$ by property (a) and since $H\in{\cal
H}_1\subset{\cal H}_0$.


Set
$$
(L'_0,L'_{\sigma+1},\ldots , L'_n)=(L''_0,L''_{\sigma_1+1},\ldots ,
L''_{n\nu})
$$
and $L'=(L'_0,L'_{\sigma+1},\ldots , L'_n)$ (hence
$\sigma=\sigma_1-n(\nu-1)$). We construct $L'$.
Consider the ho\-mo\-mor\-ph\-ism $\tau\,
:\,\overline{k}[X_{0,0},X_{i,j},\,1\le i\le\nu,\,1\le j\le n]
\rightarrow\overline{k}[X_0,\ldots , X_n]$
of $\overline{k}$--al\-ge\-b\-ras such that $\tau(X_{0,0})=H$,
$\tau(X_{i,j})=X_j$ for all
$1\le i\le\nu$, $1\le j\le n$. Put
$$
(L_0,\ldots ,
L_{n+1})=(\tau(L'''_0),\tau(L'''_{n(\nu-1)+1}),\tau(L'''_{n(\nu-1)+2}),\ldots ,
\tau(L'''_{n\nu+1}))
$$
and construct linear forms $L_0,\ldots, L_{n+1}$.
Using isomorphism (12) we identify  $\Xi_j\subset{\Bbb
A}^n(\overline{k})\subset{\Bbb P}^n(\overline{k})$ for every $j\in J$
(respectively $j\in I_1$, $j\in I_2$).
According to the described construction assertion (a) of Theorem~1 holds
for the obtained
$E_j$, $\Xi_j$, $j\in J$, linear forms $L'_0,L'_{\sigma+1},\ldots, L'_n$ and
$L_0,\ldots, L_{n+1}$ for every $H\in{\cal H}_1$.
Recall that these objects depend on $H$.

Now we slightly change the notations.  {\it In what follows
in the general case to take into account the dependence on $H$
we shall denote $J(H)$ in place of $J$, and $\Xi_j(H)$ in place of $\Xi_j$
for every $j\in J(H)$.
Let us choose $H_0\in{\cal H}_1$.
Put $J=J(H_0)$, $\Xi_j=\Xi_j(H_0)$ for every $j\in J(H_0)$, and
$L'_0,L'_{\sigma+1},\ldots, L'_n$,
$L_0,\ldots, L_{n+1}$ to be the constructed linear forms corresponding to
$H_0$.} Thus, assertion (a) is proved.

\medskip Let us prove (c). Let us enumerate linear forms $H\in{\cal
H}_1$.
Suppose that $z\not\in{\cal Z}(H)$. Then we enumerate $j\in J(H)$.
Let us choose a defined over $k$ and irreducible over $k$ component $E$ of
$W^{(j_1)}\cap\overline{\Delta}$ for some $j_1\in J_1$
such that $\Xi_j(H)=\Xi_E$, see above.
Using isomorphism (12) and
applying Theorem~1 \cite{10} we decide whether $z\in E$ (respectively
$z\in\bigcup_{j_2\in J_2}(W^{(j_2)}\cap\overline{\Delta})$).
Now $z\in E_j$ if and only if $z\in E$ and
$z\not\in\bigcup_{j_2\in J_2}(W^{(j_2)}\cap\overline{\Delta})$.
If $z\in E_j$
then the multiplicity $\mu(z,E_j)=\mu(z,E)$ is computed by Theorem~1 (c)
\cite{10} applied to $V^{(j_1)},W^{(j_1)},p^{(j_1)}$ in place of $V,W,p$.

Notice that
by Lemma~2 and our construction for every $H\in{\cal H}_1$ for every
$j\in J(H)$ the intersection $\Xi_j\cap(\bigcup_{H'\in{\cal
H}_1}{\cal Z}(H'))=\emptyset$. Hence using the considered case when
$z\not\in{\cal Z}(H_0)$ and
applying Theorem~1 \cite{10} one can decide
for every $H\in{\cal H}_1$ for every $j\in J(H)$ for every $j_0\in J$
whether $\Xi_j\subset E_{j_0}$.
By Lemma~2 the set $\Xi_j\subset E_{j_0}$ if and only if $E_j=E_{j_0}$.
Thus, we are able to construct
the bijection $\gamma_H\, :\, J(H)\rightarrow J$ such
that for every $j\in J(H)$ the irreducible component
$E_{\gamma_H(j)}=E_j$. In what follows replacing
$J(H)$ by $J$ using $\gamma_H$ we shall suppose without loss of
generality that $J(H)=J$ and $\gamma_H$ is the identity mapping
for every $H\in{\cal H}_1$.

Finally, for every point $z\in{\Bbb P}^n(\overline{k})$ there is
$H\in{\cal H}_1$ such that $H(z)\ne 0$ since
${\cal H}_1\subset{\cal H}$ and $\#{\cal H}_1=n+1$. Thus, one
can
decide whether $z\in E_j$ and
compute the multiplicity $\mu(z,E_j)$ for every $j\in J$. Assertion (c) is
proved.

\medskip Let us prove (b). Let $E_j$, $j\in J$, be a defined over $k$ and
irreducible
over $k$ component of $W_1\cap\ldots\cap W_\nu$, and the last intersection
is proper at $E_j$.
Then $\widetilde{E}_j$ is a irreducible over $k$ component of
$\widetilde{W}_1\cap\ldots\cap\widetilde{W}_\nu$ and
$i_{{\Bbb P}^n(\overline{k})}(W_1,\ldots , W_\nu;E_j)=i_{{\Bbb
A}^n(\overline{k})}(\widetilde{W}_1,\ldots
,\widetilde{W}_\nu;\widetilde{E}_j)$.
As above we identify $\widetilde{E}_j$
with the defined over $k$ and irreducible over $k$ component of
$(\widetilde{W}_1\times\ldots
\times\widetilde{W}_\nu)\cap\Delta$. Now using the reduction to the diagonal,
see the Introduction (13), we get
$i_{{\Bbb A}^n(\overline{k})}(\widetilde{W}_1,\ldots
,\widetilde{W}_\nu;\widetilde{E}_j)=i_{{\Bbb
A}^{n\nu}(\overline{k})}(\widetilde{W}_1\times\ldots
\times\widetilde{W}_\nu,\Delta;\widetilde{E}_j)$.
Let $\widetilde{E}$ (respectively $E$) be the closure of $\widetilde{E}_j$
in ${\Bbb A}^{n\nu}(\overline{k})$
(respectively ${\Bbb P}^{n\nu}(\overline{k})$) with respect to the
Zariski topology.

Set $i(Q^{(1)},Q^{(2)};Q^{(3)})=0$ for any
projective (respectively affine) algebraic varieties
$Q^{(1)},Q^{(2)},Q^{(3)}$ such that  $Q^{(3)}$ is defined over $k$ and
irreducible over $k$ and
$Q^{(3)}$ is not an irreducible component of $Q^{(1)}\cap Q^{(2)}$.

Let $\gamma\in J_{i_1,\ldots, i_\nu}$ for some $(i_1,\ldots, i_\nu)\in B_1$.
Suppose that $E$ is an irreducible component of $\overline{W}_{i_1,\ldots,
i_\nu}\cap\overline{\Delta}$.
Then the intersection $\overline{W}_{i_1,\ldots,
i_\nu}\cap\overline{\Delta}$ is proper at $E$.
Recall that $e_0,\ldots , e_r$ generate the ideal of
$\overline{\Delta}\subset{\Bbb P}^{n\nu}(\overline{k})$ and
$\dim\overline{\Delta}=n\nu-r-1$. Hence
each $e_w$, $0\le w\le r$, is a linear combination of
$e''_0,e''_{\sigma_1+1},\ldots ,
e''_{n\nu}$. Therefore, $n\nu-\sigma_1=r$, the variety
$E$ is an irreducible component of $W^{(\gamma)}_{n\nu}(L'')\cap{\cal
Z}(e''_{n\nu+1})$, and the last intersection is proper at $E$.
Recall that $e''_0=e''_{n\nu+1}$, see the Introduction of \cite{10}.
Hence by the property of indices of
intersection corresponding to the
associativity of intersection
\begin{eqnarray*}
&&i_{{\Bbb P}^{n\nu}(\overline{k})}(W^{(\gamma)},\overline{\Delta};E)
=i_{{\Bbb P}^{n\nu}(\overline{k})}(W^{(\gamma)},{\cal
Z}(e''_{\sigma_1+1}\ldots , e''_{n\nu+1});E)= \\
&&\sum_{E'}i_{{\Bbb P}^{n\nu}(\overline{k})}(W^{(\gamma)},{\cal
Z}(e''_{\sigma_1+1},\ldots , e''_{n\nu});E')
i_{{\Bbb P}^{n\nu}(\overline{k})}(E',{\cal Z}(e''_{n\nu+1});E),
\end{eqnarray*}
where
$E'$ runs over all the defined over $k$ and irreducible over $k$ components
of $W^{(\gamma)}_{n\nu}(L'')$.
But, see the Introduction of
\cite{10}, for every $E'$ the index of intersection
$i(W^{(\gamma)},{\cal Z}(e''_{\sigma_1+1},\ldots ,
e''_{n\nu});E')=1$ since $L''\in{\cal U}'_{j,0}$,
see the notation before Lemma~2. Hence $i(W^{(\gamma)},\overline{\Delta};E)=
\sum_{E'}i(E',{\cal Z}(e''_{n\nu+1});E)=
i(W^{(\gamma)}_{n\nu}(L''),{\cal Z}(e''_{n\nu+1});E)$.

Now by the general properties of indices of intersection
\begin{eqnarray*}
&&i_{{\Bbb
A}^{n\nu}(\overline{k})}(\widetilde{W}_1\times\ldots
\times\widetilde{W}_\nu,\Delta;\widetilde{E}_j)=\sum_{(i_,\ldots , i_\nu)\in
B_1}
i_{{\Bbb
A}^{n\nu}(\overline{k})}(W_{i_1,\ldots , i_\nu},\Delta;\widetilde{E})=\\
&&\sum_{(i_,\ldots , i_\nu)\in B_1}
i_{{\Bbb
P}^{n\nu}(\overline{k})}(\overline{W}_{i_1,\ldots ,
i_\nu},\overline{\Delta};E)=
\sum_{(i_,\ldots , i_\nu)\in B_1}\;\sum_{\gamma\in J_{i_1,\ldots , i_\nu}}
i_{{\Bbb
P}^{n\nu}(\overline{k})}(E_\gamma,\overline{\Delta};E)\\
&&=\sum_{(i_,\ldots , i_\nu)\in B_1}\;\sum_{\gamma\in J_{i_1,\ldots , i_\nu}}
i_{{\Bbb
P}^{n\nu}(\overline{k})}(W^{(\gamma)}_{n\nu}(L''),{\cal
Z}(e''_{n\nu+1});E).
\end{eqnarray*}
We compute each index of intersection $i_{{\Bbb
P}^{n\nu}(\overline{k})}(W^{(\gamma)}_{n\nu}(L''),{\cal
Z}(e''_{n\nu+1});E)$
applying Theorem~1 (f) \cite{10}. After that one can calculate by the given
formula
$i_{{\Bbb
A}^{n\nu}(\overline{k})}(\widetilde{W}_1\times\ldots
\times\widetilde{W}_\nu,\Delta;\widetilde{E}_j)=
i_{{\Bbb P}^n(\overline{k})}(W_1,\ldots , W_\nu;E_j)$.
The equality $i_{{\Bbb P}^n(\overline{k})}(W_1,$ $\ldots, W_\nu;E_j)=
i_{{\Bbb P}^n(\overline{k})}(W_1,\ldots, W_\nu,
{\cal Z}(L_{s+1},\ldots, L_n);$ $\xi)$
follows from the property of indices of intersection
corresponding to the associativity of intersection.
Assertion (b) is proved.

Using isomorphism (12)
assertion (d) follows immediately from assertion (g) of Theorem~1 \cite{10}
applied for every $j_0\in J_0$ to
$V^{(j_0)},W^{(j_0)},p^{(j_0)}$ in place of $V,W,p$.

The required bounds for the working time of the algorithms from
Theorem~1 follow immediately from the ones for the applied algorithms.
The theorem is proved.





\section{Proof of Theorem~2}\label{s2}

The proof of Theorem~2 is similar to the proof of Theorem~1.
More than that, we reduce Theorem~2 to Theorem~1.
If $\nu=\nu_1$ then all the assertions of Theorem~2 follow from Theorem~1
immediately.
Thus, we shall suppose in what follows without loss of generality that
$\nu>\nu_1$, and hence $\nu\ge 2$.
Besides that, we shall assume also that $n\ge 1$.

Put
${\cal V}^{(1)}_\alpha=
{\cal W}^{(1)}_\alpha={\Bbb P}^n(\overline{k})$, and ${\cal
V}^{(j)}_\alpha=V^{(j-1)}_\alpha$, ${\cal
W}^{(j)}_\alpha=W^{(j-1)}_\alpha$ for every $1\le\alpha\le\nu$, $2\le j\le
a_\alpha+1$.
For every $1\le\alpha\le\nu$ let us replace
the pair $(a_\alpha,b_\alpha)$ by
$(a_\alpha+1,b_\alpha+1)$.
Now the conditions from the statement of Theorem~1 are fulfilled for
${\cal V}^{(j)}_\alpha$,
${\cal W}^{(j)}_\alpha$, $1\le j\le a_\alpha+1$,
in place of $V^{(j)}_\alpha$,
$W^{(j)}_\alpha$, $1\le j\le a_\alpha$ in the natural way.
We apply the construction from the proof of Theorem~1 to
${\cal V}^{(j)}_\alpha$, ${\cal W}^{(j)}_\alpha$, $1\le j\le
a_\alpha+1$,
in place of $V^{(j)}_\alpha$, $W^{(j)}_\alpha$, $1\le j\le a_\alpha$.

In what follows ${\cal H}$, $B_1$ $B_2$, $J_{i_1,\ldots , i_\nu}$
for $(i_1,\ldots , i_\nu)\in B_1$,
$J_{\alpha;i}$ for $(\alpha,i)\in B_2$, $J_0$, $J_1$, $J_2$,
the sets of points $\Xi_E$ for
all defined over $k$ and irreducible over $k$ components $E$ of
$W^{(j)}\cap\overline{\Delta}$ for all $j\in J_0$, ${\cal H}_1$,
linear forms  $L_0,\ldots , L_{n+1}$,
$L'_0,L'_{\sigma+1},\ldots , L'_n$
and other objects constructed in
the proof of Theorem~1 correspond to ${\cal V}^{(j)}_\alpha$,
${\cal W}^{(j)}_\alpha$, $1\le j\le a_\alpha+1$.
At present we assume that $\Xi_E$, and
linear forms $L_0,\ldots , L_{n+1}$,
$L'_0,L'_{\sigma+1},\ldots , L'_n$ correspond to $H\in{\cal H}_1$, and
hence they depend on $H$, see Section~1 (we do not fix $H_0$ at this stage).
For every $H\in{\cal H}_1$ we perform the following construction.
Some objects defined below depends on $H$ although we do not indicate it
explicitly in the notations.
Put
\begin{eqnarray*}
&&B_{1,1}=\{(i_1,\ldots , i_{\nu_1},1,\ldots , 1)\in B_1\, :\,
2\le i_\alpha\le b_\alpha+1\,\forall\, 1\le\alpha\le\nu_1\}\,,\\
&&{\cal B}_{1,1}=\{(i_1,\ldots , i_{\nu_1})\, :\,
(i_1,\ldots , i_{\nu_1},1,\ldots , 1)\in B_{1,1}\}\,,\\
&&J_{1,1}=\bigcup_{(i_1,\ldots , i_\nu)\in B_{1,1}}
J_{i_1,\ldots , i_\nu}\,,\\
&&B_{1,2}=\{(1,\ldots , 1,i_{\nu_1+1},\ldots , i_\nu)\in B_1\, :\,
2\le i_\alpha\le b_\alpha+1\,\forall\,\nu_1+1\le\alpha\le\nu\}\,,\\
&&{\cal B}_{1,2}=\{(i_{\nu_1+1},\ldots , i_\nu)\, :\,
(1,\ldots , 1,i_{\nu_1+1},\ldots , i_\nu)\in B_{1,2}\}\,,\\
&&J_{1,2}=\bigcup_{(i_1,\ldots , i_\nu)\in B_{1,2}}
J_{i_1,\ldots , i_\nu}\,, \\
&&B_{2,1}=\{(\alpha,i)\in B_2\, :\, 1\le\alpha\le\nu_1\}, \\
&&J_{2,1}=\bigcup_{(\alpha,i)\in B_{2,1}}J_{\alpha;i}\,,\\
&&B_{2,2}=\{(\alpha,i)\in B_2\, :\, \nu_1+1\le\alpha\le\nu\}, \\
&&J_{2,2}=\bigcup_{(\alpha,i)\in B_{2,2}}J_{\alpha;i}.
\end{eqnarray*}

Below we use the definition of a component which
maximal with respect to a set of indices. This definition is given in
Section~1.
Applying Theorem~1 \cite{10}
we construct the family $\Xi_j$, $j\in I_{1,1}$ (respectively
$j\in I_{1,2}$, $j\in I_{2,1}$, $j\in I_{2,2}$), such that
\begin{itemize}
\item for every $j\in I_{1,1}$ (respectively
$j\in I_{1,2}$, $j\in I_{2,1}$, $j\in I_{2,2}$)
the set $\Xi_j=\Xi_E$ for a defined over $k$ and
irreducible over $k$ component $E$ of
$W^{(j')}\cap\overline{\Delta}$ with
$j'\in J_{1,1}$ (respectively
$j'\in J_{1,2}$, $j'\in J_{2,1}$, $j'\in J_{2,2}$)
such that
$E\not\subset{\cal Z}(X_{0,0})$ and $E$ is maximal
with respect to $J_{1,1}\cup J_{1,2}$ (respectively with respect to
$J_{1,2}$, $J_{2,1}\cup J_{2,2}$, $J_{2,2}$).
\item conversely, for every $j'\in J_{1,1}$ (respectively
$j'\in J_{1,2}$, $j'\in J_{2,1}$, $j'\in J_{2,2}$)
for every defined over $k$ and
irreducible over $k$ component $E$ of $W^{(j')}\cap\overline{\Delta}$
such that $E\not\subset{\cal Z}(X_{0,0})$ and $E$ is maximal
with respect to $J_{1,1}\cup J_{1,2}$ (respectively with respect to
$J_{1,2}$,
$J_{2,1}\cup J_{2,2}$, $J_{2,2}$)
there is $j\in I_{1,1}$ (respectively
$j\in I_{1,2}$, $j\in I_{2,1}$, $j\in I_{2,2}$) with
$\Xi_j=\Xi_E$,
\item for all $j_1,j_2\in I_{1,1}$ (respectively
$j_1,j_2\in I_{1,2}$, $j_1,j_2\in I_{2,1}$, $j_1,j_2\in I_{2,2}$)
if $j_1\ne j_2$ then
$\Xi_{j_1}\ne\Xi_{j_2}$, and hence $E_{j_1}\ne E_{j_2}$ by Lemma~2.
\end{itemize}


For every $j\in I_{1,1}\cup I_{1,2}\cup I_{2,1}\cup I_{2,2}$ put
$\overline{E}_j=\overline{E}$, where
$\Xi_j=\Xi_E$ and $\overline{E}$
is the the closure of $E\setminus{\cal Z}(X_{0,0})$ in
${\Bbb P}^n(\overline{k})$ with respect to the Zariski topology by
inclusion (27).
Now $\overline{E}_j$, $j\in I_{1,1}$ (respectively
$j\in I_{1,2}$, $j\in I_{2,1}$, $j\in I_{2,2}$)
is the family
of all the defined over $k$ and irreducible over $k$ components of
$\bigcup_{(i_1,\ldots , i_{\nu_1})\in
{\cal B}_{1,1}}\bigcap_{1\le\alpha\le\nu_1}
W^{(i_\alpha)}_\alpha$ (respectively
$\bigcup_{1\le\alpha\le\nu_1}\;\bigcup_{b_\alpha+1\le i\le a_\alpha}
W_\alpha^{(i)}$, \\ $\bigcup_{(i_{\nu_1+1},\ldots , i_\nu)\in
{\cal B}_{1,2}}\bigcap_{\nu_1+1\le\alpha\le\nu}
W^{(i_\alpha)}_\alpha$,
$\bigcup_{\nu_1+1\le\alpha\le\nu}\;\bigcup_{b_\alpha+1\le i\le a_\alpha}
W_\alpha^{(i)}$) by Lemma~2,
by property (a) from Section~1 and since $H\in{\cal
H}_1\subset{\cal H}_0$.


Let $j_1\in I_{i,1}$, $j_2\in I_{i,2}$ for some $i=1,2$.
Let ${\Bbb P}^{n\nu}(\overline{k})\supset E_\gamma\setminus{\cal
Z}(X_{0,0})=E_{j_\gamma}\setminus{\cal Z}(H)$, $\gamma=1,2$, according to
(27).
Again applying Theorem~1 \cite{10} we
decide for every $i=1,2$
for every $j_1\in I_{i,1}$ for every $j_2\in I_{i,2}$ whether
$\Xi_{E_1}\subset E_2$. It is equivalent to $\Xi_{j_1}\subset
\overline{E}_{j_2}$ and also to
$\overline{E}_{j_1}\subset\overline{E}_{j_2}$
by Lemma~2. Thus, we construct for $i=1,2$ the subset
$$
J^{(i)}=\{j\in I_{i,1}\, :\, \Xi_j\not\subset
\overline{E}_{j_2}\quad\mbox{for all}\quad j_2\in I_{i,2}\}.
$$
Hence by Lemma~2
for every $j\in J^{(i)}$ for every $j_2\in J_{i,2}$ the set $\Xi_j\not\subset
W^{(j_2)}\cap\overline{\Delta}$ for $i=1,2$.
Recall that the sets
$A^{(1)}=\{1,\ldots ,\nu_1\}$, $A^{(2)}=\{\nu_1+1,\ldots ,\nu\}$,
see the statement of Theorem~2.
For every $j\in J^{(i)}$ denote
$$
E_j=\overline{E}\setminus
\Bigl(\,\bigcup_{\alpha\in A^{(i)}}\;\bigcup_{b_\alpha+1\le i\le a_\alpha}
W_\alpha^{(i)}\,\Bigr),
$$
where $E$ is a defined over $k$ and irreducible over $k$ component of
$W^{(j_1)}\cap\overline{\Delta}$ for some $j_1\in J_{i,1}$ such that the set
$\Xi_j=\Xi_E$, and $\overline{E}$ is defined above.
Therefore, $E_j$, $j\in J^{(i)}$
is the family
of all the defined over $k$ and irreducible over $k$ components of
$\bigcap_{\alpha\in A^{(i)}}W_\alpha$ by property (a)
from Section~1 and since
$H\in{\cal
H}_1\subset{\cal H}_0$.

Now we slightly change the notations.  {\it In what follows
in the general case to take into account the dependence on $H$
for every $i=1,2$
we shall denote $J^{(i)}(H)$ in place of $J^{(i)}$, and $\Xi_j(H)$ in place
of $\Xi_j$ for every $j\in J^{(i)}(H)$.
Let us choose $H_0\in{\cal H}_1$, cf. the construction from the
proof of Theorem~1.
Put $J^{(i)}=J^{(i)}(H_0)$, $\Xi_j=\Xi_j(H_0)$ for every $j\in
J^{(i)}(H_0)$, and
$L'_0,L'_{\sigma+1},\ldots, L'_n$,
$L_0,\ldots, L_{n+1}$ to be the constructed linear forms corresponding to
$H_0$.} Now assertion (a) of Theorem~2 holds. Assertion (a) is proved.


For every $i=1,2$
for every $H\in{\cal H}_1$ for every $j\in J^{(i)}(H)$ for every $j_0\in
J^{(i)}$ applying assertion (c) of Theorem~1
one can decide  whether $\Xi_j\subset E_{j_0}$.
By Lemma~2 the set $\Xi_j\subset E_{j_0}$ if and only
if $E_j=E_{j_0}$.
Thus, we are able to construct
the bijection $\gamma_{i,H}\, :\, J^{(i)}(H)\rightarrow J^{(i)}$ such
that for every $j\in J^{(i)}(H)$ the irreducible component
$E_{\gamma_{i,H}(j)}=E_j$. In what follows replacing
$J^{(i)}(H)$ by $J^{(i)}$ using $\gamma_{i,H}$ we shall suppose without loss
of
generality that $J^{(i)}(H)=J^{(i)}$ and $\gamma_{i,H}$ is the identity
mapping for every $H\in{\cal H}_1$ for every $i=1,2$.


Let us prove (b).
Let $j_1\in J^{(1)}$,  $j_2\in J^{(2)}$ be arbitrary indices.
Let $H\in{\cal H}_1$ be an arbitrary linear form.
Recall that there are $j'_i\in J_{1,i}$, $i=1,2$,
and a defined over $k$ and
irreducible over $k$ component $E_i$ of
$W^{(j'_i)}\cap\overline{\Delta}$ such that $\Xi_{j_i}=\Xi_{E_i}$.
We choose such $j'_i$ and $E_i$ for every $H\in{\cal H}_1$ and every
$i=1,2$.
Then by Lemma~2 and the described construction
the inclusion $E_{j_1}\subset\overline{E}_{j_2}$ holds
if and only if $\Xi_{E_1}\subset E_2$ for $H=H_0$
(or any other fixed $H\in{\cal H}_1$).
We decide
whether $\Xi_{E_1}\subset E_2$ using assertion (c) of Theorem~1.
Assertion (b) is proved.

Let us prove (c).
Let $j_1\in J^{(1)}$,  $j_2\in J^{(2)}$ be arbitrary indices.
Recall that at present ${\cal H}_1$
is from the construction
from the proof of Theorem~1 with ${\cal V}_\alpha$,  ${\cal W}_\alpha$
in place of $V_\alpha$, $W_\alpha$, see above, and $\bigcap_{H\in{\cal
H}_1}{\cal Z}(H)=\emptyset$
in ${\Bbb P}^n(\overline{k})$ by property (b) from Section~1.
Now $E_{j_1}\subset E_{j_2}$ if and only if
$E_{j_1}\subset\overline{E}_{j_2}$
and for every $H\in{\cal H}_1$
$$
(E_{j_1}\setminus{\cal Z}(H))\cap
\Bigl(\,\bigcup_{\nu_1+1\le\alpha\le\nu}\bigcup_{b_\alpha+1\le j\le
a_\alpha}W^{(j)}_\alpha\,\Bigr)
\subset\bigcup_{1\le\alpha\le\nu_1}\bigcup_{b_\alpha+1\le j\le
a_\alpha}W^{(j)}_\alpha.
\eqno (28)
$$
Thus, it remains to decide for every $H\in{\cal H}_1$ whether (28)
holds.


We enumerate $H\in{\cal H}_1$.
Let  $j'_i\in J_{1,i}$, $i=1,2$, and the irreducible components $E_i$ of
$W^{(j'_i)}\cap\overline{\Delta}$ be as above.
Recall that $j'_1\in J_{i_1,\ldots ,
i_\nu}$, where
$i_1,\ldots , i_\nu$ are known according to our construction
(and $i_1,\ldots , i_{\nu_1}\ge 2$, $i_{\nu_1+1}=\ldots = i_\nu=1$).
We identify $E_{j_1}\setminus{\cal Z}(H)$  with
$E_1\setminus{\cal Z}(X_{0,0})$.
Recall that in the proof of Theorem~1 the algebraic varieties $V_{i_1,\ldots
,
i_\nu}$, $\overline{V}_{i_1,\ldots , i_\nu}$
are defined.
Now $V_{i_1,\ldots ,
i_\nu}$, $\overline{V}_{i_1,\ldots , i_\nu}$ correspond to
${\cal V}_\alpha$,  ${\cal W}_\alpha$
in place of $V_\alpha$, $W_\alpha$, see above.
Similarly for every $1\le\alpha\le\nu$ for every
$b_\alpha+2\le j\le
a_\alpha+1$ the algebraic varieties $V_{\alpha;j}$, $W_{\alpha;j}$,
$\overline{V}_{\alpha;j}$,
$\overline{W}_{\alpha;j}$ are defined. They also
correspond to
${\cal V}_\alpha$,  ${\cal W}_\alpha$
in place of $V_\alpha$, $W_\alpha$.

Further, we identify
$E_1\setminus{\cal Z}(X_{0,0})$
with an irreducible component of $V_{i_1,\ldots , i_\nu}\cap\Delta$, and
$E_1$ with an irreducible component of $\overline{V}_{i_1,\ldots ,
i_\nu}\cap\overline{\Delta}$.
Hence  for every $\nu_1+1\le\alpha\le\nu$ for every $b_\alpha+2\le j\le
a_\alpha+1$ the algebraic variety $(E_{j_1}\setminus{\cal Z}(H))\cap
W^{(j)}_\alpha$
is identified with
$(E_1\setminus{\cal Z}(X_{0,0}))\cap W_{\alpha;j}
=E_1\cap\overline{W}_{\alpha;j}\setminus{\cal Z}(X_{0,0})$.
Now (28) is equivalent to
$$
E_1\cap\Bigl(\,\bigcup_{\nu_1+1\le\alpha\le\nu}\bigcup_{b_\alpha+2\le j\le
a_\alpha+1}
\overline{W}_{\alpha,j}\,\Bigr)\subset
\bigcup_{1\le\alpha\le\nu_1}\bigcup_{b_\alpha+2\le j\le a_\alpha+1}
(\overline{W}_{\alpha,j}\cup{\cal Z}(X_{0,0})).
\eqno (29)
$$

The algebraic variety  $\overline{V}_{i_1,\ldots , i_\nu}\cap
\overline{\Delta}$ is given explicitly by a
system of homogeneous polynomial equations with respect to $X_{0,0}$,
$X_{i,j}$, $1\le i\le\nu$, $1\le j\le n$.
According to the described construction one can find the representation
$\rho_1$ of $E_1$ such that
$n(\rho_1)=n\nu$, $a(\rho_1)=b(\rho_1)=1$, $q_1(1,\rho_1)=
(\overline{V}_{i_1,\ldots , i_\nu}\cap\overline{\Delta})\cup{\cal
Z}(X_{0,0})$,
$q_2(1,\rho_1)=E_1$.

Let us construct some bijections
\begin{eqnarray*}
&&\tau_1\, :\, \Bigl\{\,1,\ldots , \sum_{1\le \alpha\le
\nu_1}(a_\alpha-b_\alpha)\,\Bigr\}\rightarrow
\{(\alpha,j)\, :\, 1\le\alpha\le\nu_1\,\&\,\\
&&b_\alpha+2\le j\le a_\alpha+1\}, \\
&&\tau_2\, :\,\Bigl\{\,1,\ldots ,\sum_{\nu_1+1\le \alpha\le
\nu}(a_\alpha-b_\alpha)\,\Bigr\}\rightarrow
\{(\alpha,j)\, :\, \nu_1+1\le\alpha\le\nu\,\&\,\\
&&b_\alpha+2\le j\le
a_\alpha+1\}.
\end{eqnarray*}
The algebraic variety  $\overline{V}_{\alpha;j}$ is given explicitly by a
system of homogeneous polynomial equations with respect to $X_{0,0}$,
$X_{i,w}$, $1\le i\le\nu$, $1\le w\le n$.
According to the described construction one can find the representation
$\rho'$ (respectively $\rho''$) of
$\bigcup_{1\le\alpha\le\nu_1}\bigcup_{b_\alpha+2\le j\le a_\alpha+1}
(\overline{W}_{\alpha,j}\cup{\cal Z}(X_{0,0}))$
(respectively \\ $\bigcup_{\nu_1+1\le\alpha\le\nu}\bigcup_{b_\alpha+2\le j\le
a_\alpha+1}\overline{W}_{\alpha,j}$)
such that $n(\rho')=n\nu$, $a(\rho')=b(\rho')=\\
\sum_{1\le\alpha\le\nu_1}(a_\alpha-b_\alpha)$, $q_1(i,\rho')=
\overline{V}_{\alpha;j}\cup{\cal
Z}(X_{0,0})$, $q_2(i,\rho')=\overline{W}_{\alpha;j}\cup{\cal Z}(X_{0,0})$
(respectively $n(\rho'')=n\nu$, $a(\rho'')=b(\rho'')=
\sum_{\nu_1+1\le\alpha\le\nu}(a_\alpha-b_\alpha)$, $q_1(i,\rho'')=
\overline{V}_{\alpha;j}\cup{\cal
Z}(X_{0,0})$, $q_2(i,\rho'')=\overline{W}_{\alpha;j}$)
where $(\alpha,j)=\tau_1(i)$ (respectively $(\alpha,j)=\tau_2(i)$).

Finally, applying assertion (b) of Theorem~2 with $(3,2,n\nu)$ in place of
$(\nu,\nu_1,n)$, and
with
$$
E_1,\quad \bigcup_{\nu_1+1\le\alpha\le\nu}\bigcup_{b_\alpha+2\le j\le
a_\alpha+1}\overline{W}_{\alpha,j}\,,\quad
\bigcup_{1\le\alpha\le\nu_1}\bigcup_{b_\alpha+2\le j\le a_\alpha+1}
(\overline{W}_{\alpha,j}\cup{\cal Z}(X_{0,0}))
$$
given by $\rho_1$, $\rho''$,  $\rho'$
(in place of $W_1,\ldots , W_\nu$ given by $\rho_1,\ldots ,\rho_\nu$, see
the notations before the statement
of Theorem~1) we decide whether (29) holds.
As we have seen $E_{j_1}\subset E_{j_2}$ if and only if
$E_{j_1}\subset\overline{E}_{j_2}$ and (29) is satisfied
for every $H\in{\cal H}$. Thus, assertion (c) is
proved.

The required bounds for the working time of the algorithms from
Theorem~2 follow immediately from the ones for the applied algorithms.
The theorem is proved.




\newpage

 \begin{thebibliography}{88}

 \bibitem{1} {\bf Chistov A. L.:} {\it ``Polynomial complexity algorithm
 for factoring polynomials and constructing components of a variety in
 subexponential time''}, Zap. Nauchn. Semin. Leningrad.  Otdel. Mat.
 Inst. Steklov (LOMI) 137 (1984), p.\ 124--188 (in Russian) [English
 transl.: J. Sov. Math. 34, (4), (1986) p.\ 1838--1882].


 \bibitem{2} {\bf Chistov A. L.:}
 {\it `` Polynomial--Time Computation of
 the Dimension of Algebraic Varieties in Zero--Characteristic''},
 Journal of Symbolic Computation,
 22 \# 1 (1996) 1--25.

 \bibitem{3} {\bf  Chistov A. L.:}  {\it ``Polynomial--time computation
 of the dimensions of
 components of algebraic varieties in zero--characteristic''},
 Journal of Pure and Applied Algebra, 117 \& 118 (1997)
 145--175.

\bibitem{4} {\bf  Chistov A. L.:}
{\it ``Polynomial--time computation of the degrees
of algebraic varieties in zero--characteristic and its applications''},
Zap. Nauchn. Semin. St-Petersburg.
Otdel. Mat. Inst. Steklov (POMI) v. 258 (1999), p. 7--59 (in Russian)
\footnote{Preliminary versions of \cite{4}, \cite{5}, \cite{6} and \cite{7}
in English can
be found as Preprints (1999) , http://www.MathSoc.spb.ru}

\bibitem{5} {\bf  Chistov A. L.:}
{\it ``Strong version of the basic deciding algorithm for
  the existential theory   of real fields''},
Zap. Nauchn. Semin. St-Petersburg.  Otdel. Mat.
Inst. Steklov (POMI) 256 (1999) p. 168--211 (Russian).
[English transl.: J. of Mathematical Sciences
v.107 No.5 p.4265--4295]

\bibitem{6} {\bf  Chistov A. L.:}
{\it ``Efficient Construction of Local Parameters
of Irreducible Components of an Algebraic Variety''},
Proc. of the St.--Petersburg Mathematical
Society, 1999, v. 7, p. 230--266 (Russian).

\bibitem{7} {\bf  Chistov A. L.:}
{\it ``Efficient Smooth Stratification of an Algebraic Variety in
Zero--Characteristic  and its Applications''},
Zap. Nauchn. Semin. St-Petersburg.
Otdel. Mat. Inst. Steklov (POMI) v. 266 (2000) p.254--311 (in Russian)
[English transl.: to appear in J. of Mathematical Sciences].

\bibitem{8} {\bf  Chistov A. L.:} {\it
``Monodromy and irreducibility criteria
with algorithmic applications in zero--characteristic''},
Zap. Nauchn. Semin. St-Petersburg.  Otdel. Mat.
Inst. Steklov (POMI) 292 (2002) p. 130--152 (in Russian)
[in English, see Preprint of St.Petersburg
Mathematical Society (2004)].


\bibitem{9} {\bf  Chistov A. L.:} {\it
``Polynomial--time computation of the degree of a
  dominant morphism in zero--characteristic I''},
Zap. Nauchn. Semin. St-Petersburg.  Otdel. Mat.
Inst. Steklov (POMI) 307 (2004) p. 189--235 (in Russian)
[in English, see Preprint of St.Petersburg
Mathematical Society (2004)].

\bibitem{10} {\bf  Chistov A. L.:} {\it
``Polynomial--time computation of the degree of a
  dominant morphism in zero--characteristic II''},
Preprint of St.Petersburg
Mathematical Society (2004), http://www.MathSoc.spb.ru


\bibitem{11} {\bf  Chistov A. L.:} {\it
``A deterministic  polynomial--time algorithm for the first
 Bertini theorem''},
Preprint of St.Petersburg
Mathematical Society (2004), http://www.MathSoc.spb.ru


\bibitem{12} {\bf Hartshorne R.:} {\it ``Algebraic geometry''},
 Springer--Verlag, New York, Heidelberg, Berlin, 1977.







\end{thebibliography}

\end{document}