 % Filename:        deg.tex (LaTeX)
 % Title:        Polynomial-time computation of the degrees
 %       of algebraic varieties in zero-characteristic and its applications
 % Type:                Paper
 % Main Style:        article
 % Input Files:        -
 % Remarks:        A.L.Chistov (author)


 % ��� 518.5+513.6
 % 1991 Math. Subject Class. 14Q15


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

%\documentstyle[a4,amssymb]{article}

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


\newcommand{\bea}{\begin{eqnarray*}}
\newcommand{\eea}{\end{eqnarray*}}
\newcommand{\bthm}[1]{\begin{thms}\label{t#1}}
\newcommand{\bd}[1]{\begin{defns}\label{d#1}}
\newcommand{\bprp}[1]{\begin{props}\label{p#1}}
\newcommand{\br}[1]{\begin{rems}\label{r#1}}
\newcommand{\bl}[1]{\begin{lems}\label{l#1}}
\newcommand{\ethm}{\end{thms}}
\newcommand{\ed}{\end{defns}}
\newcommand{\eprp}{\end{props}}
\newcommand{\er}{\end{rems}}
\newcommand{\el}{\end{lems}}
\newcommand{\lrf}[1]{Lem\-ma~\ref{l#1}}
\newcommand{\trf}[1]{The\-o\-rem~\ref{t#1}}
\newcommand{\rrf}[1]{Re\-mark~\ref{r#1}}
\newcommand{\prf}[1]{Pro\-po\-si\-ti\-on~\ref{p#1}}
\newcommand{\drf}[1]{De\-fi\-ni\-ti\-on~\ref{d#1}}
\newcommand{\bpr}{\noindent {\bf PROOF} \quad}
\newcommand{\erf}[1]{(\ref{#1}}
\newcommand{\srf}[1]{Sec\-tion~\ref{s#1}}
\newcommand{\ctl}[1]{\cite{lit#1}}
\newcommand{\ctt}[1]{\cite{lit#1}}
\newcommand{\bequ}[1]{\begin{equation}\label{#1}}
\newcommand{\eequ}{\end{equation}}
\newcommand{\bco}[1]{\begin{coros}\label{c#1}}
\newcommand{\crf}[1]{Corollary~\ref{c#1}}
\newcommand{\eco}{\end{coros}}
\newcommand{\beaa}[1]{\begin{eqnarray}\label{#1}}
\newcommand{\eeaa}{\end{eqnarray}}
\newcommand{\rf}[1]{(\ref{#1})}





\begin{document}


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



 \title{Polynomial--Time Computation of the Degree\\ of
     Algebraic Varieties\\ in Zero--Characteristic and its Applications}
\author{Alexander L.~Chistov%
\thanks{Research partially supported by the
	Volkswagen--Stiftung, Program on
	Computational Complexity, University of Bonn
                } \\[2ex]
	St.~Petersburg Institute for Informatics and
	Automation of the\\ Academy of Sciences of Russia\\[2ex]
	}
\date{\Large 1999}

\maketitle

\begin{abstract}

Consider an algebraic variety over a zero--characteristic ground field
which is  given as a set of all common
zeros of a family of polynomials of the degree less than $d$ in $n$
variables.
In this paper the following algorithms
with the  working time polynomial in the size of input and $d^n$
are constructed:
an algorithm for the computation
of the degrees of algebraic varieties,
an algorithm for the computation of
the dimension of a given algebraic variety in the neighbourhood of
a given point,
an algorithm for the computation
of the multiplicity of a given point of an algebraic variety,
an algorithm for the computation of a representative system of
smooth points with their tangent spaces on each component
of a given algebraic variety,
an algorithm for deciding whether a given morphism
of algebraic varieties is dominant.  \\[2ex]

1991 Math. Subject Class. 14Q15
\end{abstract}

\newpage
 \section*{Introduction}\label{s0}

In the paper polynomial--time algorithms are suggested for the computation
of such
basic numerical characteristics of algebraic varieties as degrees,
dimensions of
components containing a given point, multiplicities of points. Besides that,
a representative set of
smooth points of a given algebraic variety $V$ with their tangent spaces
is constructed such that each irreducible component of $V$
contains at least one point from this set.
Given a point $x$ of an algebraic variety and a
family ${\mathcal Q}$ of rational functions an algorithm is
suggested to decide whether there is an irreducible component $W$ of this
algebraic variety containing the point $x$ and
such that the family ${\mathcal Q}$ is a basis of transcendence
of the field of rational function of $W$. This gives
an algorithm for deciding whether a given morphism
of algebraic varieties is dominant.
The case of zero--characteristic ground field is considered.

This paper continues  \cite{lit15} and \cite{lit17}.
The methods of real algebraic geometry \cite{lit1}
are essentially used in the present paper as in
\cite{lit15}, \cite{lit17}. The results from  \cite{lit10}
and  \cite{lit9} are important here.
It should be emphasized that the present paper could not appear
until two principle steps were made in \cite{lit15} and \cite{lit17}.
In \cite{lit15} the problem of the computation
of dimension over zero--characteristic ground fields
was solved for the case of projective
varieties.  The algorithm from \cite{lit17} for the computation of
dimensions of all components of
an algebraic variety required additionally four embedded recursions.
Note also that in other terms the construction from \cite{lit15},
\cite{lit17} is
a polynomial--time algorithm for the choice of the projection in the Noether
normalization theorem.

The probabilistic algorithms for
the  problems considered in this paper (and many others
in which it is required to find
some element in ``general position'')
can be easily obtained in any characteristic of the field of coefficients.
The problem of the computation of the dimension of
algebraic varieties is classical and it has been  considered
from the last century \cite{lit50}.
In \cite{lit29} the problem of the computation of
the dimension of algebraic varieties was formulated from the point of view
which is close to theory of complexity.
In \cite{lit14} a well parallelizable arithmetical network
is constructed for the computation of the dimension of
an algebraic variety in non--uniform
polynomial sequential time in the size of input and $d^n$.
In the general case
one can obtain from \cite{lit14} only probabilistic
algorithm for this problem
with the complexity polynomial in $d^n$. In \cite {lit14} also
the problem was stated to find a deterministic algorithm
for the computation of the dimension with a bitwise complexity
$d^{O(n)}$. This problem is solved in \cite{lit15},
\cite{lit17} for zero--characteristic. The situation
in the theory of computation is reflected here that in
many problems random objects (or objects in ``general position'')
are difficult to construct deterministically.

In this paper we construct deterministic algorithms
with a bitwise complexity polynomial in
$d^n$ and the size of input.
The question is open
whether there is such an algorithm for any of the problems
considered in this paper and \cite{lit15},
\cite{lit17} (i.e., for computing dimensions,
degrees, multiplicities and so on)
in the case of non--zero characteristic ground field.
 In \cite{lit3} an
 algorithm is suggested for decomposing an algebraic variety into the
 irreducible components with the complexity polynomial in $d^{n^2}$
and the size of input including the characteristic of the field.
 For an arbitrary characteristic using \cite{lit3} the algorithms
with the similar complexity bound (i.e., polynomial in $d^{n^2}$
and the size of input)
can be obtained  for the  problems considered in this paper and \cite{lit15},
\cite{lit17}. This complexity bound is the best known
for the case of an arbitrary characteristic. We would like to
underline here again that we consider deterministic
computations with a bitwise complexity. This model of computations is
the most important from the theoretical point of view.


Now we give the precise statements. Let $k={\mathbb Q}(t_1,\ldots
 ,t_l,\theta )$ be the field where $t_1,\ldots,t_l$ are
 algebraically independent over the field ${\mathbb Q}$ and $\theta$ is
 algebraic over ${\mathbb Q}(t_1,\ldots ,t_l)$ with the minimal
 polynomial $F\in{\mathbb Q}[t_1,\ldots ,t_l,Z]$ and leading
 coefficient $\, \hbox{lc}_ZF$ of $F$ is equal to 1. Let  homogeneous
polynomials
 $g_0,\ldots ,g_m\in k[X_0,\ldots ,X_n]$ be given. Consider the
 closed algebraic set or which is the same in this paper the algebraic
 variety
 \[
 V=\{(x_0: \ldots : x_n)\, : \, g_i(x_0, \ldots, x_n)=0 \; \forall 0 \leq i
 \leq m\} \subset {\mathbb P}^n(\overline{k}) \: .
 \]
 This is a set of all common zeros of polynomials $g_0, \ldots, g_m$ in the
projective
 space
 ${\mathbb P}^n(\overline{k})$, where $\overline{k}$ is an algebraic closure
of $k$.  In what follows we shall denote for brevity this set
by ${\mathcal Z}(g_0,\ldots,g_m)$.
The similar notations will be used also for the sets of all common zeros
(in affine or projective spaces as it will be seen from the context) of other
polynomials. So $V={\mathcal Z}(g_0,\ldots,g_m)$.

 \noindent
 We shall represent each polynomial $f=g_i$ in the form
 \[
 f=\frac{1}{a_0} \sum_{i_0, \ldots, i_n} \sum_{0 \leq j <
 deg_Z F} a_{i_1, \ldots, i_n,j} \theta^j X_0^{i_0} \cdots X_n^{i_n}
 \, ,
 \]
 where $a_0,a_{i_1, \ldots, i_n,j} \in {\mathbb Z}[t_1, \ldots, t_l], \,
 \gcd_{i_1, \ldots, i_n,j} (a_0,a_{i_1, \ldots, i_n,j})=1$.
 Define the length $l(a)$ of an integer $a$ by the formula
 $l(a)=\min\{s \in {\mathbb Z}: \: |a|<2^{s-1}\}$.
 The length of coefficients $l(f)$ of the polynomial $f$ is defined to
 be the maximum of length of coefficients from ${\mathbb Z}$ of polynomials
 $a_0,a_{i_1, \ldots, i_n,j}$ and the degree
 \[
 \deg_{t_\alpha} (f)=\max_{i_1, \ldots, i_n,j} \{\deg_{t_\alpha} (a_0),
 \deg_{t_\alpha} (a_{i_1, \ldots, i_n,j})\} \, ,
 \]
 where $1 \leq \alpha \leq l$.
 In the similar way $\deg_{t_\alpha} F$ and $l(F)$ are defined.

 \noindent
 We shall suppose that we have the following bounds
 \begin{eqnarray*}
 \deg_{X_0, \ldots, X_n} (g_i)<d, \; \deg_{t_\alpha}(g_i)<d_2, \;
 l(g_i)<M, \\
 \deg_Z (F)<d_1, \; \deg_{t_\alpha} (F)<d_1, \; l(F)<M_1 \: .
 \end{eqnarray*}
 The size $L(f)$ of the polynomial $f$ is defined to be the product of
 $l(f)$ to the number of all the coefficients from ${\mathbb Z}$ of $f$ in
 the dense representation.
 We have
 \[
 L(g_i)<({d+n \choose n}d_1+1)d_2^l M
 \]
 Similarly $L(F)<d_1^{l+1} M_1$. In what follows if there
is  no  special  mention about it we set $l$ to be fix.
One can consider different dense representations
of polynomials. For example, one can consider the class of
polynomials  $f$ in $X_0,\ldots , X_n$ with
 $\deg_{X_i}f<d$ for all $0\le i\le n$ as basic in
a dence representation which is parametrized by $d$.
Then the sizes of these polynomials are estimated by $(d^{n+1}d_1+1)d_2^l M$.
In such a representation $L(f_i)<(d^{n+1}d_1+1)d_2^l M$ and,
therefore, algorithms from the present paper have polynomial complexity,
cf.  \cite{lit3}.

Let $V_s$ be the
union of all the irreducible components of the dimension $n-s$ of
of $V$  where $0\le s\le n$.
The degree $\deg V_s$ of $V_s$ is equal,
see \lrf{1} below, to $\max_H\# V_s\cap H$ where the
maximum
is taken over all the linear subspaces $H$ of ${\mathbb P}^n(\overline{k})$
of the dimension $s$ such  that $\# V_s\cap H<+\infty$.

\bthm{1}
Let a projective algebraic variety $V$ defined over the ground field $k$
be given as a set of common zeros
in ${\mathbb P}^n(\overline{k})$ of a family of homogeneous polynomials
$g_0,\dots ,g_m\in k[X_0,\ldots ,X_n]$
of the degrees less than $d$.
Then  the degrees $\deg V_s$ for all
$0\le s\le n$  can be computed  within the time polynomial
 in $d^n$, $d_1$, $d_2$, $M$, $M_1$, $m$.
\ethm

Let $x\in {\mathbb P}^n(\overline{k})$. The dimension $\dim_x V$ of the
variety
$V$ in the point $x$ (or in the neighbourhood of
the point $x$) is set to be $\max_W\dim W$ where the maximum is taken
over all the irreducible components $W$ of $V$ such that $x\in W$.
Denote by ${\mathcal W}$ the set of all such components $W$.

\bthm{2}
Let $x\in {\mathbb P}^n(\overline{k})$. The dimensions of all the components
containing the the point $x$, i.e. the set $\{\dim W\, :\, W\in {\mathcal
W}\}$ can be
computed within the time polynomial in $d^n$, $d_1$, $d_2$, $M$, $M_1$, $m$
and the size of the point $x$.
Therefore, the dimension $\dim_x V$ of the variety $V$ in the point $x$ can
be computed within the same time.
\ethm

Now let a point $x\in V_s$ and $0\le s\le n$. Denote by ${\mathcal L}$ the
set of linear subspaces $L$ of
${\mathbb P}^n(\overline{k})$ such that $\dim L=s$, $x\in L$
and $\# V_s\cap L<+\infty$. The multiplicity
$\mu (x,V_s)$ of the
point $x$ of the variety $V_s$ can be defined by the formula
\bequ{mu}
\mu (x,V_s)=\min_{L\in {\mathcal L}}\{1+\deg V_s-\#V_s\cap L\},
\end{equation}
see also \crf{0} and \rrf{3} in \srf{3}.
This formula can be explained in the following way, c.f. \cite{lit13}.
By its initial meaning the multiplicity $\mu (x,V_s)$ is equal to
to the number of points infinitely close to $x$ of the intersection of $V_s$
with a generic linear subspace $\tilde{L}$, $\dim \tilde{L}=s$,
which is infinitely close to the point
$x$. So $\# V_s\cap \tilde{L}=\deg V_s$. When one shifts this generic linear
subspace to the generic subspace $\overline{L}$ containing the point $x$
(by an  infinitesimal
 shift) all the points of the intersection which were in the infinitesimal
small neighbourhood of $x$ go to $x$, other points of the intersection
go bijectively to $-1+\# V_s\cap \overline{L}=\max_{L\in {\mathcal
L}}\{-1+\#V_s\cap L\}$
points. So one get this formula for $\mu(x,V_s)$.

\bthm{3} The multiplicities $\mu (x,V_s)$ for all $0\le s\le n$
can be computed within the time polynomial in $d^n$, $d_1$, $d_2$,
$M$, $M_1$, $m$ and the size of the point $x$.
\ethm

\bthm{4}
Let a projective algebraic variety $V$ over the ground field $k$
be given as a set of common zeros
in ${\mathbb P}^n(\overline{k})$ of a family of homogeneous polynomials
$g_0,\dots ,g_m\in k[X_0,\ldots ,X_n]$
of the degrees less than $d$. Let $V_s$ as above be the
union of all the components of
 $V$ of the dimension $n-s$ where $0\le s\le n$.  Then one can construct for
every
$0\le s\le n$ a finite set $A_s$ of smooth points of $V_s$ and for every
point
$x\in A_s$ the tangent space $T_x$ of the variety $V_s$ in the point $x$. The
tangent spaces are considered here as linear subspaces of
${\mathbb P}^n(\overline{k})$. Besides that,
$A_s$ satisfy the property that for every component $W$ of $V_s$ there
exists a point
$x\in A_s\cap W$. The points of $A_s$ are also smooth points of $V$
(i.e. they do not belong to any $V_r$ with $r\ne s$).
The number of elements $\# A_s\le d^{s}$. The working time
of the
algorithm for constructing all $A_s$, $0\le s\le n$ is polynomial in
$d^n$, $d_1$, $d_2$, $M$, $M_1$, $m$.
\ethm

\bthm{5}
Let a projective algebraic variety $V$ over the ground field $k$
be given as a set of common zeros
in ${\mathbb P}^n(\overline{k})$ of a family of homogeneous polynomials
$g_0,\dots ,g_m\in k[X_0,\ldots ,X_n]$
of the degrees less than $d$. Let a family ${\mathcal Q}$ of rational
functions
$q_{s+1},\ldots , q_n\in
k(X_1/X_0,\ldots ,X_n/X_0)$, $0\le s\le n$, be given. Let the degrees and the
lengths of integer coefficients of
numerators and denominators of rational functions $q_{s+1},\ldots , q_n$ are
bounded from above by the same values as
ones for the polynomials $g_0,\ldots , g_m$. Let $x\in {\mathbb
P}^n(\overline{k})$.
An algorithm is
suggested to decide whether there is an irreducible component $W$ of the
algebraic variety $V$ containing the point $x$ and
such that the family ${\mathcal Q}$ is a basis of
transcendence of the field of
rational function $\overline{k}(W)$ of $W$.  The working time of the
algorithm is
polynomial in $d^n$, $d_1$, $d_2$, $M$, $M_1$, $m$
and the size of the point $x$.
\ethm

\br{1}
 The working times of the algorithms from the theorems 1--5 are
essentially
 the same as by solving systems of polynomial equations with a finite set of
 solutions in the projective space.
 So these theorems can be formulated also in the case when $l$ is not fixed,
see
 \cite{lit3}.
\er
\br{0.01}
In what follows we shall assume without loss of generality that the
polynomials
$g_0,\ldots , g_m$ are linearly independent over $k$.
Hence $\dim V\le n-1$ and $V_0=\emptyset$.
\er

\section{Preliminaries}\label{s0.5}


We shall use in this paper the technique from \cite{lit4}, \cite{lit15},
\cite{lit17},
see Introductions of  \cite{lit15}, \cite{lit17}.
Namely, we apply Newton--Puiseux expansions and
the Newton--Puiseux algorithm for constructing roots of a polynomial
in the field of fractional power series in one variable, see also
\cite{lit5}, we apply infinitesimals, standard parts,
constructing real structures.

The real structure on a field $k$ is defined
to be an embedding $k\rightarrow K[\sqrt{-1}]$ where $K$ is a real
ordered field.
An algorithm of the polynomial complexity
for constructing a real structure is suggested in
\cite{lit15} for a field $k$ finitely generated over ${\mathbb Q}$.
It is important here
that for a given  element $a\in K$ one can decide whether $a>0$ within
the polynomial time.
Additionally  $K\subset \overline{k}$ in this construction where
$\overline{k}$ is algebraic closure of $k$.
The absolute value  $|a|$ of an element from $a\in\overline{k}$ can be
defined in the natural
way \cite{lit15}.

Consider inequalities of the type $A<0$ or $A\le 0$ where
$A=\sum_{1\le i\le r}a_i|A_i|^2$, $a_i\in K$, and $A_i$ is a superposition of
polynomials  and functions $B\mapsto |B|^2$ for every $i$.
The upper bound for the degree of $A$ can be easily
defined if we set $\deg |B|^2=2 \deg B$.

Each system of equations and inequalities over $\overline{k}$ is
equivalent to the system of equations and inequalities over
$\widetilde{K}$ with twice as much of variables.
Applying the algorithm of \cite{lit15} for constructing real structures,
transfer principle and \cite{lit10} in this situation we get,
see \cite{lit17}, the following result.

\bprp{0} Consider a system of polynomial
equations in $n$ variables and a fixed number of inequalities with
 polynomials and squares of absolute values
 (of the described type $A<0$ or $A\le 0$)
with coefficients from the field $k$ finitely generated over ${\mathbb Q}$.
Let the degrees of equations and inequalities be less than $d$.
Then one can construct a real structure on $k$ and decide within the time
polynomial in $d^n$ and the size of input whether this system has a solution
in ${\mathbb A}^n(\overline{k})$ relative to the constructed real structure.
 If such a solution exists one can construct it
within the same time. The coordinates of the solution belong to a finite
extension of the field $k$. This finite extension is constructed and
is given by a primitive element and its minimal polynomial.
\eprp

Since $k$ is an arbitrary finitely generated field over ${\mathbb Q} $ this
result is valid
also in the case when one replaces the field of coefficients $k$ by an
extension of $k$ by a fixed number of infinitesimals.
In what follows we shall use many times \prf{0}
for solving systems of polynomial equations
and inequalities with squares of absolute values and infinitesimals
without references to this proposition.

Let $k_1$ be an algebraic extension of the field
${\mathbb Q}(t_1,\ldots , t_l)$.
Let $\varepsilon_i>0$ be an infinitesimal, see \cite{lit17}, relative to
the field $k_1(\varepsilon_1,\ldots ,\varepsilon_{i-1})$,
$1\le i\le v$. Let $0\le w\le v-1$.
Set $K'=k_1(\varepsilon_1,\ldots ,\varepsilon_{v})$ and
$K''=k_1(\varepsilon_1,\ldots ,\varepsilon_{w})$.
Denote by
\[\mathop{\rm st}\nolimits\, :\,{\mathbb P}^n(\overline{K'})
\rightarrow {\mathbb P}^n(\overline{K''}) \]
the mapping of the standard part, see \cite{lit17},
(the standard part of an element $z\in
{\mathbb P}^n(\overline{K'})$
is the element $z_1\in {\mathbb P}^n(\overline{K''})$ which is
infinitesimal close to $z$).
We shall use many times the following result, see \cite{lit17} Proposition~2.
\bprp{1}
Let $W'\subset {\mathbb P}^n$ be a variety
defined over the field $\overline{K''}$
and such that every component of $W'$ has the dimension $n-s$.
Let $D_i \in \overline{K''}[\, X_0, \, \ldots \, ,$ $X_n\, ]$,
$s+1 \le i \le n$, be linear forms
in $X_0, \, \ldots \, ,X_n$ and $\widetilde{D}_i \in
\overline{K'}[\, X_0, \, \ldots \, ,X_n\, ]$,
$s+1 \le i \le n$, linear forms
all nonzero coefficients of
which are infinitesimals relative to the field $K''$.
Then the condition $\# W'\cap{\mathcal Z}(D_{s+1},
\ldots,D_n)<+\infty$ in
${\mathbb P}^n(\overline{K''})$ implies that
 $\# W'\cap {\mathcal
Z}(D_{s+1}-\widetilde{D}_{s+1},\ldots,D_n-\widetilde{D}_n)
 <+\infty$ in
${\mathbb P}^n(\overline{K'})$ and
\begin{eqnarray*}
&&\mathop{\rm st}\nolimits(W'\cap {\mathcal Z}(D_{s+1}-\widetilde{D}_{s+1},
\ldots,D_n-\widetilde{D}_n))=\\
&& W'\cap {\mathcal Z}(D_{s+1},\ldots,D_n)
\end{eqnarray*}
in ${\mathbb P}^n(\overline{K''})$.
\eprp

\section{Computation of the degree of an
algebraic variety and its smooth points}\label{s1}

We need the following lemma.

\bl{1}
Let $V_s$, $0\le s\le n$ be the variety from the statement of \trf{1} and
$L_0,L_{s+1}, L_{s+2},\ldots ,L_n$ be $n-s+1$ linear forms from
$\overline{k}[X_0,\ldots ,X_n]$ such that $V_s\ne \emptyset$ and
\[V_s\cap {\mathcal Z}(L_0,L_{s+1}, L_{s+2},\ldots ,L_n)=\emptyset\]
in ${\mathbb P}^n(\overline{k})$. Denote by
\[p\, :\, V_s\longrightarrow {\mathbb P}^{n-s}(\overline{k}),\,
(X_0 \, :\, \ldots \, : \, X_n) \mapsto
(L_0 \, : \, L_{s+1} \, :\, \ldots  : \, L_n)\]
the linear projection which is a finite morphism \cite{lit7}.
Then
 \begin{enumerate}
 \renewcommand{\labelenumi}{(\roman{enumi})}

 \item there exists a non--empty open in the Zariski topology subset $U$ of
${\mathbb P}^{n-s}(\overline{k})$ such that for every $x\in U$ the
cardinality
$\# p^{-1}(x)=\deg V_s$,

 \item if for some point $x\in {\mathbb P}^{n-s}(\overline{k})$ the
cardinality
$\# p^{-1}(x)=\deg V_s$ then for every $y\in p^{-1}(x)$ the point
$y$ is a smooth point of the variety
 $V_s$ and the differential of $p$ in the point $y$
\[d_yp\, :\, T_{y,V_s}\longrightarrow T_{x,{\mathbb P}^{n-s}}\]
is the isomorphism of tangent spaces $T_{y,V_s}$ and $T_{x,{\mathbb
P}^{n-s}}$
of the varieties $V_s$ and ${\mathbb P}^{n-s}(\overline{k})$ in the points
$y$
and $x$
respectively.

 \end{enumerate}
\el

 \noindent
 {\bf PROOF} \quad
Replacing $k$ by $\overline{k}$ we
can suppose without loss of generality that $V_s=W$ is irreducible over
$\overline{k}$. Let $Y\in \overline{k}[X_0,\ldots ,X_n]$ be a linear form.
Consider the morphism
\[p_1\, :\, W\longrightarrow {\mathbb P}^{n-s+1}(\overline{k}),\quad
(X_0 \, :\, \ldots \, : \, X_n)
\mapsto (Y\, :\, L_0 \, : \, L_{s+1} \, :\ldots : \, L_n).\]
Since $p$ is finite morphism $p_1(W)$ is a closed subset in
${\mathbb P}^{n-s+1}(\overline{k})$ and $p_1(W)={\mathcal Z}(G)$ where $G\in
\overline{k}[Y,L_0,L_{s+1},\ldots ,L_n]$ is a irreducible
homogeneous polynomial with leading coefficient  $\mbox{lc}_Y G=1$.

By the theorem about primitive element for fields
there exists a linear form $Y\in \overline{k}[X_0,\ldots ,X_n]$
such that  the morphism $p_1$
induces the birational isomorphism $W\longrightarrow p_1(W)$ which we shall
denote $p_2$. So there exists an open subset $U_1\subset W$ such that
$p_2(U_1)$ is open in $p_1(W)$ and $p_2$ induces the isomorphism
$U_1\longrightarrow p_2(U_1)$.

There exists a projection
$p_3\, :\, p_1(W)\longrightarrow {\mathbb P}^{n-s}(\overline{k})$
such that $p=p_3\circ p_2$. Denote by
$R=\hbox{Res}_Y(G,G'_Y)$ the discriminant of the
polynomial $G$ relative to $Y$. Then $0\ne R$ is a homogeneous polynomial
since
$G$ is a separable homogeneous polynomial. If $R(x)\ne 0$ then
the cardinality $\# p_3^{-1}(x)=\deg_Y G$,
 for every $y\in p_3^{-1}(x)$ the point $y$ is a smooth point of the variety
 $p_1(W)$ and the differential of $p_3$ in the point $y$
\[d_yp_3\, :\, T_{y,p_1(W)}\longrightarrow T_{x,{\mathbb P}^{n-s}}\]
is the isomorphism of tangent spaces $T_{y,p_1(W)}$ and $T_{x,{\mathbb
P}^{n-s}}$
of the varieties $p_1(W)$ and ${\mathbb P}^{n-s}(\overline{k})$ in the points
$y$ and $x$
respectively. The last statement follows here just from the fact that
$G'_Y(y)\ne 0$ since $R(x)\ne 0$.

Set $U={\mathbb P}^{n-s}(\overline{k})
\setminus({\mathcal Z}(R)\cup p_3(p_2(W)\setminus p_2(U_1)))$.
Then for every $x\in U$
 \begin{enumerate}
 \renewcommand{\labelenumi}{(\alph{enumi})}

 \item the cardinality $\# p^{-1}(x)=\deg G$,

 \item for every $y\in p^{-1}(x)$ the point $y$ is a smooth point of the
variety
 $W$ and the differential of $p$ in the point $y$
\[d_yp\, :\, T_{y,W}\longrightarrow T_{x,{\mathbb P}^{n-s}}\]
is the isomorphism of tangent spaces $T_{y,W}$ and $T_{x,{\mathbb P}^{n-s}}$
of the varieties $W$ and ${\mathbb P}^{n-s}(\overline{k})$ in the points $y$
and $x$
respectively.

 \end{enumerate}
Let us show that $\deg G=\deg W$.
Let $\varepsilon>0$ be an infinitesimal relative to the field $k$.
So the map of the standard part
\[\hbox{st}\, :\, {\mathbb P}^{r}(\overline{k(\varepsilon)})\longrightarrow
{\mathbb P}^{r}(\overline{k})\]
 is defined for every $r\ge 0$, see \cite{lit17}.
Denote by ${\mathcal H}_1$
the set of families $H$ of  $n-s+1$ linear forms
$H_0,H_{s+1}, H_{s+2},\ldots ,H_n$ in
$X_0,\ldots ,X_n$ such that
if one replace in the formulation of \lrf{1} the forms $L_0,L_{s+1},
L_{s+2},\ldots ,L_n$
by $H_0,H_{s+1}, H_{s+2},\ldots ,H_n$  then (i) will be satisfied for
 $U(H)$ and $p(H)$ corresponding to $U$ and $p$.
Consider ${\mathcal H}_1$ as a subset of ${\mathbb A}^{(n-s+1)(n+1)}$. Then
\cite{lit7}, c.f. also \srf{3}, ${\mathcal H}_1$
is an open subset of  ${\mathbb A}^{(n-s+1)(n+1)}$ in the Zariski topology.

Therefore, there exists a family $H_0,H_{s+1}, H_{s+2},\ldots ,H_n$
in ${\mathcal H}_1(\overline{k(\varepsilon)})$ such that all the forms
$H_j-L_j$ have infinitesimal coefficients.
Thus, by \prf{1}
for every $x\in U\cap U(H)$ for every $y^*\in p(H)^{-1}(x)$ the
element $y=\hbox{st}\, y^*\in p^{-1}(x)$. The differential
of $p$ in the point $y$ is an  isomorphism. Therefore, by  the
implicit function theorem there exists a unique $y'\in p(H)^{-1}(x)$ such
that $\hbox{st}y'=y$. Hence, $y'=y^*$. Thus,
\[\deg W=\# p(H)^{-1}(x)= \# p^{-1}(x)=\deg_Y G\]
and, therefore, $\deg G=\deg W$. Assertion (i) is proved.

To prove (ii) note that if $R(x)\ne 0$ and $y\in p^{-1}(x)$ then
the point $p_1(y)$ is smooth, the local ring ${\mathcal O}_{p_1(y),p_1(W)}$
of
the
variety $p_1(W)$ in the point $p_1(y)$ is
integrally closed. Therefore, the local rings
\[{\mathcal O}_{y,W}\simeq{\mathcal O}_{p_1(y),p_1(W)}\]
since ${\mathcal O}_{y,W}$ is integral over ${\mathcal O}_{p_1(y),p_1(W)}$
and has
the same
fraction field. Thus, $p_1$ is an isomorphism in the neighbourhood of each
point
$y\in p^{-1}(x)$.  Now (ii) follows from the fact that for each point $x$
for which
$\# p^{-1}(x)=\deg W$ there exists a linear form $Y$ such that the
corresponding
$p_1$ is birational, $\# p_3^{-1}(x)=\deg W$ and so $R(x)\ne 0$, see
above. The Lemma is proved.


We shall suppose without loss of generality that
 \[\, \deg(g_i) = \deg_{X_0,\,\ldots\, ,X_n}(g_i) = d\,\]
 for all $0\le i\le m$ replacing if it is necessary each polynomial
 $g_i$ by the family  of polynomials $\,\{g_iX_j^{-\deg (g_i)+d}\}_{0\le
j\le n}\,$.

Recall that in \cite{lit17} the algorithm of polynomial complexity
is suggested which finds all $s$ for which $V_s\ne \emptyset$.  For
every $s$ at the step $s$ the algorithm of \cite{lit17}  constructs
 polynomials $h_1,\,\ldots\, ,h_s$ and linear forms
 $L^{(s)}_{s+1},\,\ldots\, ,L^{(s)}_n$ in $X_0,\,\ldots\, ,X_n$ with integer
 coefficients of the size $O(n\, \hbox{log}d)\,$ such that
 \[
 h_i = \sum_{0\le j\le m}\lambda_{i,j}g_j,\ \lambda_{i,j}\in{\mathbb Z}
 \]
 for all $i,j$. Besides that, the following property is fulfilled.
 Let
 \[
 W_s ={\mathcal Z}(h_1, \ldots, h_s) \subset {\mathbb P}^n(\overline{k})
 \]
 be the variety of all common zeros of polynomials
 $h_1,\,\ldots\, ,h_s$ in ${\mathbb P}^n(\overline{k})$,
 the variety  $W'$ be the union of  all irreducible
 the components  $U_1$ of $W_s$  such that $\hbox{dim}U_1=n-s$,  and
  $W''$ be the union of  all
 the components  $U_1$ of $W_s$  such that $\hbox{dim}U_1>n-s$.
 Then the subset of ${\mathbb P}^n(\overline{k})$
 \[W'\cap {\mathcal Z}(L^{(s)}_{s+1},\,\ldots,\, L^{(s)}_n)\]
 is finite and
 \[W'\cap {\mathcal Z}(L^{(s)}_{s+1},\,\ldots,\, L^{(s)}_n)\cap W''\,
=\,\emptyset \,.\]
The form $L^{(s)}_0$  is not equal to zero in each point
of $W'\cap {\mathcal Z}(L^{(s)}_{s+1},\,\ldots,\, L^{(s)}_n)$.  Besides that
$W''$ consists of all components $U$ of ${\mathcal Z}(g_0,\ldots,g_m)$ with
$\dim U>n-s$.

 We shall denote also $W' =W'_s,  W'' =W''_s$
 when the dependence on $s$ will be essential.


Set $L_{s,j}=L_j^{(s)}$, $s+1\le j\le n$ or $j=0$.
Compute, see \cite{lit17}, all the points $\{x_u\}_{1\le u \le
N}$
of the set $W'\cap {\mathcal Z}(L_{s,s+1},\,\ldots,\, L_{s,n})$.
Let $x_u=(x_{u,0}:\ldots :x_{u,n})$ where all $x_{u,i}$ are from a finite
extension of $k$. Construct
a real structure for the field $K=k(x_{u,0},\ldots ,x_{u,n})$,
see \cite{lit15}, \cite{lit17}, which induces the a structure on
$\overline{k}$ (it is uniquely defined up to a conjugation).

 Let $\varepsilon_1>0$ be an infinitesimal
  relative to the field $K$ and $\varepsilon_2>0$
an infinitesimal relative to the field $K(\varepsilon_1)$,
the field $K_1=K(\varepsilon_1,\varepsilon_2)$.

Let $Y_0,\ldots,Y_n$ be new  variables. For every $1\le u\le N$
 consider the following system of equations and inequalities
 with coefficients in $K_1$
\bequ{1}
\left\{\begin{array}{ll}
 h_i=0, &  1\le i \le s, \\
 h_i(Y_0,\dots,Y_n)=0, & 1\le i\le s, \\
 L_{s,j}(X_0-Y_0,\ldots,X_n-Y_n)=0, & j\in\{0,s+1,\ldots,n\}, \\
 \sum_{0\le i\le n}|X_i-x_{u,i}|^2\le \varepsilon_1, &  \\
 \sum_{0\le i\le n}|Y_i-x_{u,i}|^2\le \varepsilon_1, &  \\
 \sum_{0\le i\le n}|Y_i-X_i|^2\ge \varepsilon_2, &
  \end{array}
\right. \eequ

\br{2}
One can add also to this system the equation
$L_{s,0}(X_0-x_{u,0},\ldots,$ $X_n-x_{u,n})=0$ but it is not necessary.
\er

\bl{2}
Let $W'=W'_s$ be as above. Then $N=\deg W'$ if and only if for every $1\le
u\le
N$
there do not exist solutions of system \rf{1} in ${\mathbb
A}^{2n+2}(\overline{K_1})$.
If for every $1\le u\le N$
there do not exist solutions of system \rf{1}  in ${\mathbb
A}^{2n+2}(\overline{K_1})$
then all the points $\{x_u\}_{1\le u \le N}$ of the variety $W'$ are smooth
and the
differentials of the projection
\[p\, :\, W'\longrightarrow {\mathbb P}^{n-s}(\overline{k}),\quad
(X_0 \, :\, \ldots \, : \, X_n) \mapsto
(L_{s,0} \, : \, L_{s,s+1} \, :\, \ldots  : \, L_{s,n})\]
in the points $\{x_u\}_{1\le u \le N}$ are isomorphisms.
\el

\noindent
 {\bf PROOF} \quad
Follows directly from
 \lrf{1} if one replaces
$g_0,\ldots ,g_m$ by $h_1,\ldots ,h_s$ and, therefore, $V_s$ by $W'_s$,
 c.f. also the proof \lrf{8} below.

Return to the description of the algorithm. Our aim now is to compute $\deg
W'$.
Construct a solution of system \rf{1} for some $1\le u\le N$
or ascertain that for every $1\le u\le N$
there do not exist solutions of system \rf{1} in ${\mathbb
A}^{2n+2}(\overline{K_1})$.
In the last case by \lrf{2} the degree $\deg W'=N$ is already computed.
Suppose that there exists a solution
\[(x'_0,\ldots ,x'_n,y'_0,\ldots ,y'_n)\in {\mathbb
A}^{2n+2}(\overline{K_1})\]
of system \rf{1} with $u=u_0$. Denote $x'=(x'_0:\ldots :x'_n)$
and $y'=(y'_0:\ldots :y'_n)$. So $x',y'\in {\mathbb P}^n(\overline{K_1})$.
Set
\[L'_i=L_{s,i}-(L_{s,i}/L_{s,0})(x')L_{s,0},\,
s+1\le i\le n,\; L'_0=L_{s,0}.\]
Compute, see  \cite{lit17}, all the points from the
set $W'\cap {\mathcal Z}(L'_{s+1},\,\ldots,\, L'_n)$ in
${\mathbb P}^n(\overline{K_1}$.
Denote $N'=\# W'\cap {\mathcal Z}(L'_{s+1},\,\ldots,\, L'_n)$. By \prf{1}
for every $x^*\in W'\cap {\mathcal Z}(L'_{s+1},\,\ldots,\, L'_n)$ there
exists
$1\le u\le n$ such that $\hbox{st}\,x^*=x_u$. So $N'\ge N$. Further,
$x',y'\in W'\cap {\mathcal Z}(L'_{s+1},\,\ldots,\, L'_n)$, $x'\ne y'$ and
$\hbox{st}\,x'=\hbox{st}\,y'$. Therefore, $N'\ge N+1>N$.

Let $D_{s+1},\ldots , D_n\in \overline{K_1}[X_0,\ldots , X_n]$
be linear forms (in what follows we shall
consider also other ground fields different from $K_1$).
Similarly to definition~1 from \cite{lit17} the property ${\mathcal A}$
of linear forms
$D_{s+1},\ldots , D_n$ is called good
if and only if the it satisfies the following condition.
 Consider $\mathcal A$ as a function of $D_{s+1},\ldots,D_n$.
 Let $D_i=\sum_{0\le j\le n}l_{i,j}L_j$  where
 $l_{i,j}\in \overline{K_1}$ for all $i,j$. Replace one
 arbitrary coefficient $l_{i,j}$  in the forms $D_{s+1},\ldots,D_n$
 by the coefficient $\varepsilon'$
 where $\varepsilon'$ is an infinitesimal  relative to the field
 $K_1$. We get the new linear form $D'_i$ with coefficients in
 $\overline{K_1(\varepsilon')}$. Suppose for the convenience of the
notations
 that we have replaced $l_{s+1,0}$ and got $D'_{s+1}$. The condition for
 the property ${\mathcal A}$ is as follows.
 There exists a polynomial $P$ such that if the property $\mathcal A$
 holds for the forms $D_{s+1} \, , \, \ldots \, , \, D_n$ then
 \begin{enumerate}
 \renewcommand{\labelenumi}{(\roman{enumi})}
 \item it is not satisfied for at most
 $P(d^n)$ arbitrary values $\varepsilon^*$ of $\varepsilon'$
(considered as a variable) for the
 forms $D'_{s+1}|_{\varepsilon'=\varepsilon^*}, D_{s+2}\, ,\ldots,D_n$,
 \item for a given value $\varepsilon^*$ of $\varepsilon'$
 one can check the property $\mathcal A$  for the forms
 $D'_{s+1}|_{\varepsilon'=\varepsilon^*}, D_{s+2},\, \ldots,\, D_n$
 within the time polynomial in $d^n$, $d_1$, $d_2$, $M_1$, $M_2$
 (provided that the size of $\varepsilon^*$ is bounded by the same values).
\end{enumerate}
For a good property $\mathcal A$  one can construct  replacing subsequently
coefficients of linear forms $D_{s+1},\ldots , D_n$
by integer coefficients (c.f.
the algorithm from \cite{lit17} Section~3 step~(\underline{24});
it is called in \cite{lit17} second auxiliary algorithm)
 linear forms $M_{s+2} \, , \, \ldots \, , \, M_n$ in $X_0,\ldots , X_n$
with integer coefficients with the lengths $O(n\log \,d)$
satisfying the property $\mathcal A$  within the time polynomial in
$d^n$, $d_1$, $d_2$, $M_1$, $M_2$. In what follows we shall use
few times this construction
(not formulating explicitly the property $\mathcal A$ except
of the first time)
referring to it as to the analog of the
second auxiliary algorithm from \cite{lit17}.

Now note that according to \cite{lit17}
the property that
\begin{eqnarray*}
&&\# W'\cap {\mathcal Z}(D_{s+1},\,\ldots,\, D_n)\ge N' \quad \mbox{and} \\
&&W'\cap {\mathcal Z}(D_{s+1},\,\ldots,\, D_n)\cap W''=\emptyset \quad
\mbox{and} \quad D_0=L'_0
\end{eqnarray*}
is good.

So apply the analog of the
considered second auxiliary algorithm to the linear forms
$L'_0,L'_{s+1},\ldots ,L'_n$ and construct linear forms $M_0,M_{s+1},\ldots
,M_n$
with coefficients from ${\mathbb Z}$ with the lengths $O(n\log \,
d)$ such that
\begin{eqnarray*}
&&\# W'\cap {\mathcal Z}(M_{s+1},\,\ldots,\, M_n)\ge N',\\
&&W'\cap {\mathcal Z}(M_{s+1},\,\ldots,\, M_n)\cap W''=\emptyset \:\mbox{and}
\: M_0=L'_0.
\end{eqnarray*}


After that, return recursively to the beginning of the algorithm described
replacing the forms $L_{s,0},L_{s,s+1},\ldots ,L_{s,n}$ by
$M_0,M_{s+1},\ldots ,M_n$. Since $N'>N$ there are at most $d^s$ such returns
in the algorithm.

Thus, we shall compute $\deg\, W'$ in the required time and we can suppose
without loss
of generality by \lrf{2} that $N=\deg\, W'$, all the points $x_u,\, 1\le
u\le N$ are
smooth on the variety $W'$ and  the
differentials of the projection
$p$, see \lrf{2},
in the points $x_u,\, 1\le u \le N$ are isomorphisms.

Let us show how to choose among the points $x_u,\, 1\le u \le N$
the points from $V_s$.
Let $ 1\le u \le N$. Consider the following system of equations and
inequalities in $X_0,\ldots , X_n$, $Z$
with coefficients from $\overline{k(\varepsilon_1)}$
\bequ{2}
h_1=\ldots =h_s=h_{s+1}Z-1=0,\, \sum_{0\le i\le n}|X_i-x_{u,i}|^2<
\varepsilon_1.
\eequ

\bl{3}
The point $x_u=(x_{u,0}:\ldots :x_{u,n})\in V_s$ if and only if
system \rf{2} has no solutions in ${\mathbb
A}^{n+1}(\overline{k(\varepsilon_1)})$.
\el

\noindent
 {\bf PROOF} \quad
It follows directly from the fact that the point $x_u$ is smooth and from the
definition of polynomials $h_1,\ldots ,h_{s+1}$, see above (and also
\cite{lit17}).
The lemma is proved.

Now construct, c.f. \cite{lit15}, \cite{lit17}, solving systes \rf{2} the
subset
$A\subset \{1,\ldots ,N\}$ of all indices $u$ such that \rf{2}  has no
solutions in ${\mathbb A}^{n+1}(\overline{k(\varepsilon_1)})$.

By \lrf{1}, \lrf{2} and \lrf{3}
we have $\# A=\deg \, V_s$, the set $V_s\cap
{\mathcal Z}(L_{s,s+1},\,\ldots,\, L_{s,n})=\{x_u\, :\, u\in A\}$ and
the
differentials of the projection
$p$, see \lrf{2},
in the points $x_u,\, u\in A$ are isomorphisms.

Thus, the degree $\deg V_s$  and the set of smooth points
$\{x_u\, :\, u\in A\}\subset V_s$ can be computed for every $s$.
Each point $x_u$, $u\in A$, does not belong to $W''$. Hence the points
$x_u$, $u\in A$ are smooth points of $V$
\trf{1}
is proved.

To prove \trf{4} it is sufficient now to construct the tangent spaces of
$V_s$ in the points from $\{x_u\, :\, u\in A\}$.

\bl{4}
Let $\phi=(\phi_1,\ldots ,\phi_r)\, :\, V'\longrightarrow \overline{k}^r$,
$r\ge 0$,
be a morphism of algebraic varieties which is given by the
rational functions $\phi_1,\ldots ,\phi_r\in \overline{k}(V')$, let
the point $y\in V'$ be smooth, the rational functions  $\phi_1,\ldots
,\phi_r$
are defined in the point $y$ and the differential
\[d_y\phi\, :\, T_{y, V'}\longrightarrow T_{\phi(y),\overline{k}^r}\]
of $\phi$ in the point $y$ be an isomorphism of the tangent spaces
$T_{y, V'}$ of $V'$ in the point $y$ and $T_{\phi(y),\overline{k}^r}$ of
$\overline{k}^r$ in $\phi(y)$. Denote
\[C_j=\{(z_1,\ldots ,z_r)\in\overline{k}^r\, :\,
z_m-\phi_m(y)=0,\, 1\le m\le r,\, m\ne j\}\]
for every $1\le j\le r$.
Then $D_j=\phi^{-1}(C_j)=\{x\in V'\, :\, \phi_m(x)-\phi_m(y)=0,\,
0\le m\le r,\, m\ne j\}$
is a curve in some neighbourhood of $y$, the point $y$ is smooth on $D_j$.
So the tangent space $T_{y,D_j}$ of $D_j$ in the point $y$ is
the subset $T_{y,D_j}\subset T_{y, V'}$. Finally, we have $\sum_{1\le j\le
r}T_{y,D_j}=
T_{y, V'}$.
\el

\noindent
 {\bf PROOF} \quad
In the case if one replaces $\overline{k}$ by
${\mathbb C}$ the statements of the lemma
follow directly from the implicit function theorem. Now it
is sufficient to apply the transfer principle for the field supplied with a
real
structure, c.f. \cite{lit15}, see \cite{lit1}. The lemma is proved.

Now set $V'=p^{-1}({\mathbb P}^{n-s}(\overline{k})
\setminus{\mathcal Z}(L_{s,0}))\subset W'$ where $p$ is the projection
from \lrf{2} and $y=x_u$ for some $u\in A$.
So ${\mathbb P}^{n-s}(\overline{k})
\setminus{\mathcal Z}(L_{s,0})\simeq \overline{k}^{n-s}$. Set
$\phi=p|_{V'}$. Apply
\lrf{4}.
We have
\[D_j={\mathcal Z}(h_1,\ldots ,h_s)\cap  {\mathcal Z}(
L_{s,m}-(L_{s,m}/L_{s,0})(x_u)L_{s,0},\,
s+1\le m\le n,\, m\ne
s+j)\]
for $1\le j\le n-s$ in some neighbourhood of $x_u$.

Thus, construct using the algorithm from \cite{lit3}
generic points of curves $D_j$
(more precisely irreducible components of $D_j$ containing the point $x_u$)
and Newton--Puiseux expansions
of coordinate functions of generic points of $D_j$ in uniformizing elements
in some neighbourhood of $x_u$, c.f.
 \cite{lit15} section~3, steps (\underline{11}),
 (\underline{12}), (\underline{13}) and also \cite{lit17},
section 1, step (\underline{16}). Now one can easily
construct the tangent space $T_{x_u,D_j}$ of $D_j$ in the point $x_u$.
Hence, by \lrf{4} all the tangent spaces $T_{x_u, V_s}$, $u\in A$, can be
constructed in
the required time. \trf{4} is proved.

\br{lp} Actually one can see
that the algorithm from \cite{lit3} (or it minor
modifcation) gives a system of local
parameters of $D_j$ in the neighborhood of the smooth point
$x_u$. So it is not necessary even to consider Newton--Puiseux expansions.
\er



\section{Dimensions of
components containing a point and dominantness of
a morphism of algebraic varieties}\label{s1.5}

Now we are going to prove \trf{2}. This theorem follows immediately from
the following lemma.

\bl{5}
Let $x\in V$, see the Introduction. Then one can decide whether $x\in V_s$
within the time polynomial
 in $d^n$, $d_1$, $d_2$, $M$, $M_1$, $m$ and the size of the point $x$.
\el

\noindent
 {\bf PROOF} \quad
Let us construct the set $\{x_u\, :\, u\in A\}$ of smooth points of $V$
and linear forms $L_{s,s+1},\,\ldots,\,L_{s,n}$ such that
\[\{x_u\, :\, u\in A\}=V_s\cap{\mathcal
Z}(L_{s,s+1},\,\ldots,\,L_{s,n}),\]
see \srf{1}.  Construct linear forms $L_i$, $s+1\le i\le
n$, vanishing in the point $x$ and such that $L_i$, $s+2\le i\le
n$, are linear forms in $L_{s,s+1},\ldots , L_{s,n}$. Denote
 ${\mathcal L}={\mathcal Z}(L_{s+2},\ldots, L_n)$.


The intersection ${\mathcal L}\cap V_s$ is a curve. Denote it by $C_s$.
Each irreducible component
of $C_s$ is an irreducible component of the variety of solutions of the
system
\bequ{3}
h_1=\ldots =h_s=L_{s+2}=\ldots =L_n=0.
\eequ
There is a linear form $L'$ (coinciding with one of the linear forms
$L_{s,s+1},\ldots , L_{s,n}$) such that
\[C_s\cap{\mathcal Z}(L')=V_s\cap{\mathcal Z}(L_{s,s+1},\ldots ,
L_{s,n}).\]
Hence, each irreducible component
of $C_s$ being a projective algebraic variety
has a non--empty intersection with ${\mathcal Z}(L')$ and,
therefore, contains some point
$x_u$, $u\in A$.
The points $\{x_u\, :\, u\in A\}$ are smooth on the variety of solutions of
\rf{3}
by the construction of \srf{1} and $C_s\supset \{x_u\, :\, u\in A\}$.
So applying the algorithm from \cite{lit3}, c.f. also
\cite{lit15}, \cite{lit17},
 construct in the required time the systems of equations which gives
one--dimensional irreducible components of the variety of solutions of
\rf{3}.
Then substituting in them the coordinates of the points from $\{x_u\, :\,
u\in A\}$
choose among these irreducible components those which are components of
$C_s$.
Finally, substituting in the systems of equations which gives
irreducible components of $C_s$ the coordinates of the point $x$ decide
whether $x\in C_s$, i.e. whether $x\in V_s$. The lemma is proved.
\trf{2} is proved.
\bco{31}
Let $\varepsilon>0$ be an infinitesimal relative to the field $k$.
Under conditions of \lrf{3} for every $0\le s\le n$ one can
construct the family of points
$x_\beta\in {\mathbb P}^n(\overline{k(\varepsilon)})$, $\beta\in B_s$, such
that
\begin{itemize}
\item every point $x_\beta$ is infinitesimal close to $x$,
\item every point $x_\beta\in V_s$ and $x_\beta$
is a smooth point of the algebraic variety $V$,
\item for every irreducible component $W_1$ of $V_s$ containing the point
$x$ there is $\beta\in B_s$ such that
$x_\beta\in W_1$.
\end{itemize}
\eco
\noindent {\bf PROOF} \quad
Choose $s+1\le i_0\le n$ such that the linear forms
$L_{s,i_0},L_{s+1},\ldots , L_n$ are linearly independent.
We shall  suppose without loss of generality and for convenience of
notations that $i_0=s+1$. Construct the isolated solutions
of the system
\bequ{31}
h_1=\ldots =h_s=L_{s+1}-\varepsilon L_{s,s+1}=L_{s+2}=\ldots =L_n=0.
\end{equation}
Choose among these solutions those which are infinitesimal close to the
point $x$.
We claim that the obtained family of
solutions gives the required family $x_\beta$, $\beta\in B_s$. Indeed,
by \prf{1}
it is sufficient to check only
that $x_\beta$ is a smooth point of the algebraic variety $V$. To ascertain
this fact note
that every irreducible component of
the curve $C_s$ contains some smooth point $x_u$, $u\in A$ of $V$
and $x_u\in V_s$. Hence,
the curve $C_s$ contains only a finite set of singular points of $V$.
Therefore, the point
$x_\beta$ is a smooth point of $V$ since it is infinitesimal close to $x$.
The corollary is proved.

Our aim now is to prove \trf{5}. We can suppose without loss of generality
that $V$ is an affine
algebraic variety which is a set of zeroes of polynomials $g_0,\ldots ,
g_m\in k[X_1,\ldots ,X_n]$,  rational functions $q_{s+1},\ldots , q_n\in
k(X_1,\ldots ,X_n)$,
the degrees (respectively the lengths of integer coefficients) of
(non--homogeneous) polynomials $g_0,\ldots , g_m$, of numerators and
denominators of rational functions from the family $q_{s+1},\ldots , q_n$
are bounded from above by $d$ (respectively $M$).
At fist we decide whether $V_s\ne \emptyset$
using the algorithm from \cite{lit17}.
If $V_s=\emptyset$ then there are no irreducible components of $V_s$.

Let $V_s\ne \emptyset$. Extending the field $k$ by an infinitesimal
$\varepsilon>0$ (and replacing $k$ by $k(\varepsilon)$),
applying \crf{31} and considering separately every point
$x_\beta$, $\beta\in B_s$ we can suppose without loss of generality that
$x$ is a smooth point of the algebraic variety $V$  and $x\in V_s$
where $0\le s\le n$ is known. Therefore, there is only
one irreducible component $W_1$ of the algebraic variety $V$ containing
the point $x$ and $W_1\subset V_s$.

Let $q_i=q^{(1)}_i/q^{(2)}_i$
where $q_i=q^{(1)}_i,q^{(2)}_i\in k[X_1,\ldots ,X_n]$ and $\mathop{\rm
GCD}\nolimits(q^{(1)}_i,q^{(2)}_i)=1$
in the ring $k[X_1,\ldots ,X_n]$ for every $s+1\le i\le n$.
Introduce new variables $Y_{s+1},\ldots ,Y_n $, $Z_{s+1},\ldots ,Z_n$.
Consider the algebraic variety
\[V'={\mathcal Z}(g_0,\ldots , g_m, q^{(2)}_iY_i-1, q^{(2)}_iZ_i-q^{(1)}_i,
s+1\le i\le n)
\subset{\mathbb A}^{n+2(n-s)}(\overline{k}).\]
Denote by
\bea
&&\pi\, :\, {\mathbb A}^{n+2(n-s)}(\overline{k})\rightarrow {\mathbb
A}^{n}(\overline{k}), \\
&&(X_1,\ldots ,X_n,Y_{s+1},\ldots ,Y_n,Z_{s+1},\ldots
,Z_n)\mapsto(X_1,\ldots ,X_n)
\eea
the linear projection. Let $\varepsilon_1>0$ be an infinitesimal relative to
the field $k$.
Consider the following system of algebraic
equations and inequalities in
$X_1,\ldots ,X_n$, $Y_{s+1},\ldots ,Y_n$, $Z_{s+1},\ldots ,Z_n$
\bequ{32}\left\{\begin{array}{ll}
 g_i=0, & 0\le i\le m,\\
 q^{(2)}_iY_i-1=0, & s+1\le i\le n,\\
 q^{(2)}_iZ_i-q^{(1)}_i=0, & s+1\le i\le n,\\
 \sum_{1\le i\le n}|X_i-X_i(x)|^2=\varepsilon_1.
 \end{array}
 \right. \end{equation}
Let us show that if the family ${\mathcal Q}$ is algebraically
independent over $\overline{k}$ in the field $\overline{k}(W_1)$ then
there is a solution $x'\in {\mathbb
A}^{n+2(n-s)}(\overline{k(\varepsilon_1)})$  of system \rf{32}.
Indeed, in this case there is
an irreducible component $W'_1$ of the algebraic variety $V'$ such that
$W'_1$ is birationally isomorphic to $W_1$ and
this birational isomorphism is induced  by the projection $\pi$.
Hence,
there is a solution  $x'\in {\mathbb
A}^{n+2(n-s)}(\overline{k(\varepsilon_1)})$  of system \rf{32}.
Note that if there is a solution $x'\in {\mathbb
A}^{n+2(n-s)}(\overline{k(\varepsilon_1)})$  of system \rf{32}
then $x'\in V'$, $q^{(2)}_i(x')\ne 0$ and there is an irreducible component
$W'_1$ of the algebraic variety
$V'$ such that $W'_1$ is birationally isomorphic to $W_1$. The rational
functions $q_i$ coincide with the
coordinates functions $Z_i$ on the algebraic variety $V'$, $s+1\le i\le n$.

Thus, replacing $k$ by $k(\varepsilon_1)$,
$n$ by $n+2(n-s)$,
the algebraic variety $V$ by $V'$ and the point $x$ by $x'$
we can suppose additionally without loss of generality that the rational
functions $q_i$ are the coordinates functions $Z_i$,
$s+1\le i\le n$. Finally, effecting a linear transformation of
${\mathbb A}^n$ we can assume without loss
of generality that $q_i$ are
the coordinates functions $X_i$, $s+1\le i\le n$,
$x=(0,\ldots , 0)\in {\mathbb A}^n(\overline{k})$ is a smooth point of
the algebraic variety
$V$ and $x\in V_s$ where $0\le s\le n$ is known.

Let $\varepsilon_i>0$ be an infinitesimal relative to the field
$k(\varepsilon_2,\ldots , \varepsilon_{i-1})$,
$2\le i\le 4$. Let $\xi=(\xi_1,\dots ,\xi_n)\in V_s$.
Let $s\le r\le n-1$.  Let $L_{r+1},\ldots , L_n\in
{\mathbb Z}[X_0,\ldots , X_n]$ be linear forms
with integer coefficients.
Consider the following system of algebraic equations and inequalities in
$X_1,\ldots ,X_n$, $Y_1,\ldots , Y_n$.
\bequ{33}\left\{\begin{array}{ll}
 g_i=0, & 0\le i\le m,\\
 g_i(Y_1,\ldots , Y_n)=0, & 0\le i\le m, \\
 \sum_{1\le i\le n}|X_i-\xi_i|^2=\varepsilon_2,\\
 \sum_{1\le i\le n}|X_i-Y_i|^2=\varepsilon_4^2,\\
 X_i-Y_i=0, & s+1\le i\le r,\\
 |X_{r+1}-Y_{r+1}|^2>\varepsilon_4^2\varepsilon_3.
 \end{array}
 \right. \end{equation}

In what follows we shall identify for convenience of notations the
tangent space ${\mathcal Z}(\sum_{1\le i\le n}a_{\gamma,i}dX_i,\,\gamma
\in \Gamma)$ (where $a_{\gamma,i }$ belongs to the coefficients field)
in a point of an arbitrary affine algebraic variety with the subspace \\
${\mathcal Z}(\sum_{1\le i\le n}a_{\gamma,i}X_i,\,\gamma\in \Gamma)
\subset{\mathbb A}^n$, herewith ${\mathbb A}^n$
has the coordinates functions $X_1,\ldots ,X_n$.
\bl{33}
Let $\xi\in V_s$ be a smooth point of $V$.
Let $W_1$ be the unique
irreducible component of the algebraic variety $V$ such that $\xi\in W_1$.
Let $s\le r\le n-1$.
Let the intersection of the tangent space in the point $\xi$ of the algebraic
variety $W_1$
\bequ{transv}
T_{\xi,W_1}\cap{\mathcal Z}(X_{s+1},\ldots , X_r,L_{r+1},\ldots , L_n)=\{0\}
\end{equation}
(and, hence,
the linear forms $X_{s+1},\ldots , X_r$, $L_{r+1},\ldots , L_n$
are algebraically independent in the field of rational functions
$\overline{k}(W_1)$ of the irreducible component $W_1$).
Then system \rf{33} has a solution in ${\mathbb
A}^{2n}(\overline{k(\varepsilon_2,\varepsilon_3,\varepsilon_4)})$ if and
only if the coordinates functions $X_{s+1},\ldots , X_r, X_{r+1}$
are algebraically independent over $\overline{k}$ in the field of rational
functions $\overline{k}(W_1)$ of the algebraic variety $W_1$.
\el
\noindent {\bf PROOF} \quad
Let system \rf{33} has a solution
\bequ{34}
(x'_1,\ldots , x'_n,y'_1,\ldots ,y'_n)\in {\mathbb
A}^{2n}(\overline{k(\varepsilon_2,\varepsilon_3,\varepsilon_4)}).
\end{equation}
Set $x'= (x'_1,\ldots , x'_n)$ and $y'=(y'_1,\ldots ,y'_n)$. Then by
\rf{transv} and
since $x'$ is infinitesimal close to $\xi$ equality \rf{transv} holds if
one replaces the point $\xi$ by $x'$. Hence, the coordinate functions $X_j$,
$1\le j\le n$,
on the tangent space $T_{x',W_1}$ of the algebraic variety $W_1$ in the
point $x'$ satisfy equalities
\[X_j=\sum_{s+1\le i\le r}\alpha_{j,i}X_i+\sum_{r+1\le u\le
n}\beta_{j,u}L_u, \quad
1\le j\le n,\]
for some elements $\alpha_{j,i}\in
\overline{k(\varepsilon_2,\varepsilon_3,\varepsilon_4)}$, $s+1\le i\le r$,
$1\le j\le n$, and
$\beta_{j,u} \in \overline{k(\varepsilon_2,\varepsilon_3,\varepsilon_4)}$,
$r+1\le u\le n$, $1\le j\le n$.

We can apply the implicit function theorem
in the point $x'$ when all coordinates
functions on $W_1$ are considered as formal power series
with coefficients in
$\overline{k(\varepsilon_2,\varepsilon_3,\varepsilon_4)}$ in the
linear polynomials $X_{s+1}-X_{s+1}(x'),$ $\ldots , X_{r}-X_r(x')$,
$L_{r+1}-L_{r+1}(x'),\ldots , L_n-L_n(x')$. By \rf{transv} and since
the point $x'$ is infinitesimal close to $\xi$ all the coefficients of these
formal power series are not infinitely large relative to the field $k$.
By \rf{33} $x'_i=y'_i$ for $s+1\le i\le r$ and
$|x'_{r+1}-y'_{r+1}|^2>\varepsilon_4^2\varepsilon_3$.
Hence, the implicit function theorem implies
that there is $r+1\le i_0\le n$ such that
$\beta_{r+1,i_0}\ne 0$.
We shall suppose without loss of generality for convenience of notations
that $i_0=r+1$.
Therefore, the coordinate functions $X_j$, $1\le j\le n$,
on the tangent space $T_{x',W_1}$ of
the algebraic variety $W_1$ in the
point $x'$ satisfy equalities
\[X_j=\sum_{s+1\le i\le r+1}\alpha'_{j,i}X_i+
\sum_{r+2\le i\le n}\beta'_{j,i}L_i, \quad
1\le j\le n,\]
for some elements $\alpha'_{j,i}\in
\overline{k(\varepsilon_2,\varepsilon_3,\varepsilon_4)}$, $s+1\le i\le r+1$,
$1\le j\le n$, and
$\beta'_{j,i} \in \overline{k(\varepsilon_2,\varepsilon_3,\varepsilon_4)}$,
$r+2\le i\le n$,
$1\le j\le n$.
Hence,
\bequ{tr1}
T_{x',W_1}\cap {\mathcal Z}(X_{s+1},\ldots , X_{r+1},L_{r+2},\ldots ,
L_n)=\{0\}.
\end{equation}
Therefore, by the implicit function theorem the coordinates functions
$X_{s+1},\ldots,$ $X_r, X_{r+1}$
are algebraically independent in the field of rational functions
$\overline{k}(W_1)$ of the algebraic variety $W_1$.

Conversely, let the coordinates functions $X_{s+1},\ldots , X_r, X_{r+1}$
be algebraically independent in the field of rational functions
$\overline{k}(W_1)$ of the algebraic variety $W_1$. Then there is
$r+1\le i_0 \le n$ such that the linear forms
\[X_{s+1},\ldots , X_r, X_{r+1},L_{r+1},\ldots ,
L_{i_0-1},L_{i_0+1},\ldots , L_n\]
are algebraically independent in the field $\overline{k}(W_1)$.  We shall
suppose without loss of generality for convenience of notations that
$i_0=r+1$.

The set of points $x'\in W_1(\overline{k(\varepsilon_2)})$ such that \rf{tr1}
holds
contains a non--empty open in the Zariski topology subset of
$W_1(\overline{k(\varepsilon_2)})$. Hence, c.f. the
proof of \lrf{6} below and Lemma~9 from \cite{lit17}, there is a smooth point
$x'=(x'_1,\ldots , x'_n)\in W_1(\overline{k(\varepsilon_2)})$ such that
\rf{tr1} holds and $\sum_{1\le i\le n}|x'_i-\xi_i|^2=\varepsilon_2$.

We can apply the implicit
function theorem in the point $x'$ when all coordinates
functions on $W_1$ are considered as formal power series
with coefficients in
$\overline{k(\varepsilon_2)}$ in the
linear polynomials $X_{s+1}-X_{s+1}(x'),$ $\ldots , X_{r}-X_r(x')$,
$L_{r+1}-L_{r+1}(x'),\ldots , L_n-L_n(x')$.
Hence, c.f. the proof of \lrf{6} below and Lemma~9 from \cite{lit17},
system \rf{33} with the additional equations
\[ L_i(X_1-Y_1,\ldots , X_n-Y_n)=0, \quad r+2\le i\le n, \]
has a solution \rf{34}.
The lemma is proved.

\bco{35}
Under conditions of \lrf{33} if system \rf{33} has a solution one can
construct solution
\rf{34} of this system and compute $i_0$ within the polynomial time in $d^n$
and the size of input. So we shall suppose as previously
without loss of generality that $i_0=r+1$. Then equality \rf{tr1} holds.
\eco
\noindent {\bf PROOF} \quad
It is sufficient to check that one can compute $i_0$. Applying \lrf{4}
to the point $x'$ and the morphism $\phi$ given by the linear forms
$X_1,\ldots ,X_r$, $L_{r+1},\ldots ,L_n$
construct the tangent space $T_{x',W_1}$ and then $i_0$ can be computed
immediately. The corollary is proved.

Now we can describe the algorithm which is required to construct in \trf{5}.
Denote by $W_1$ the unique
irreducible component of $V_s$
such that $x\in W_1$. Set $z_s=x=(0,\ldots , 0)$. Applying \lrf{4}
construct
the tangent space $T_{z_s,W_1}$. Then construct linear forms $D^{(s)}_i$,
$s+1\le i\le n$, with lengths of integer coefficients $O(n\log d)$ such that
\[T_{z_s,W_1}\cap{\mathcal Z}(D^{(s)}_{s+1},\ldots , D^{(s)}_n)=\{0\}.\]
Set $a^{(s)}_{i}=0$, $s+1\le i\le n$.

Let $s\le r\le n-1$ and we have already constructed
recursively $z_r\in W_1$ which is a smooth point of $V$,
linear forms $D^{(r)}_i$, $s+1\le i\le n$, with lengths of integer
coefficients $O(n\log d)$ and
integers $a^{(r)}_i$, $s+1\le i\le n$, with lengths
$O(n\log d)$ such that $D^{(r)}_i=X_i$ for all $s+1\le i\le r$, the point
$z_r$ is isolated in the algebraic variety
\[{\mathcal Z}(g_0,\ldots , g_m,D^{(r)}_{s+1}-a^{(r)}_{s+1},\ldots ,
D^{(r)}_n-a^{(r)}_n)
\subset {\mathbb A}^n(\overline{k})\]
and the intersection
\[T_{z_r,W_1}\cap{\mathcal Z}(D^{(r)}_{s+1},\ldots , D^{(r)}_n)=\{0\}.\]

The base of the recursion is $r=s$.
We shall refer to this recursion as to the first
one. Now we shall describe the next step of this recursion, i.e. our aim
is to construct the point $z_{r+1}$,
linear forms $D^{(r+1)}_i$ and integers $a^{(r+1)}_i$,  $s+1\le i\le n$.


Using \lrf{33} for $\xi=z_r$
we decide whether $X_{s+1},\ldots , X_{r+1}$ are
algebraically independent in the field of rational functions
$\overline{k}(W_1)$ of the algebraic variety $W_1$.

In the case when $X_{s+1},\ldots , X_{r+1}$ are
algebraically dependent over $\overline{k}$ in the field of rational
functions
$\overline{k}(W_1)$ the coordinates functions $X_{s+1},\ldots , X_n$   are
also algebraically dependent
in this field and the described algorithm finishes its work.

In the case when $X_{s+1},\ldots , X_{r+1}$ are
algebraically independent we apply \crf{35},
construct the point $(x',y')$ (it depends on $r$)
which is solution \rf{34} of system \rf{33} with $\xi=z_r$
and compute $i_0$. Set the family
$D^{(r+1)}_i$, $r+2\le i\le n$, to be $D^{(r)}_i$, $r+1\le i\le n$,
$i\ne i_0$. We shall suppose
without loss of generality that $i_0=r+1$. Then set
$D^{(r+1)}_i=D^{(r)}_i$, $r+2\le i\le n$,
and $D^{(r+1)}_i=X_i$ for all $s+1\le i\le r+1$.

Let us show how to construct the required integers $a^{(r+1)}_i$,
$s+1\le i\le n$ and the point $z_{r+1}$.
Set $b_i=D^{(r+1)}_i(x')$, $s+1\le i\le n$. Set $z'_s=x'$.
Suppose that $s\le j\le n-1$ and we have already
constructed recursively integers $a^{(r+1)}_i$, $s+1\le i\le j$ with
lengths $O(n\log d)$ and
$z'_j\in W_1$ which is a smooth point of $V$ and such that
\begin{eqnarray*}
&&z'_j\in V^{(j)}={\mathcal Z}(g_0,\ldots , g_m,
D^{(r+1)}_{s+1}-a^{(r+1)}_{s+1},\ldots , D^{(r+1)}_j-a^{(r+1)}_j, \\
&&D^{(r+1)}_{j+1}-b_{j+1},\ldots , D^{(r+1)}_n-b_n)
\subset {\mathbb A}^n(\overline{k})
\end{eqnarray*}
and the intersection
\bequ{tr2}
T_{z'_j,W_1}\cap{\mathcal Z}(D^{(r+1)}_{s+1},\ldots , D^{(r+1)}_n)=\{0\}.
\end{equation}
Note that \rf{tr2} implies that $z'_j$ is an isolated  point
of the algebraic variety $V^{(j)}$.


The base of the recursion is $j=s$.
We shall refer to this recursion as to the second
one. Now we shall describe the next step of this recursion, i.e.
our aim is to construct the point $z'_{j+1}$
and the integer $a^{(r+1)}_{j+1}$.

Since $z'_j$ is a smooth point of $V$ the algebraic variety
\begin{eqnarray*}
&&{\mathcal Z}(g_0,\ldots , g_m,
D^{(r+1)}_{s+1}-a^{(r+1)}_{s+1},\ldots , D^{(r+1)}_j-a^{(r+1)}_j, \\
&&D^{(r+1)}_{j+2}-b_{j+2},\ldots , D^{(r+1)}_n-b_n)
\subset {\mathbb A}^n(\overline{k})
\end{eqnarray*}
contains a unique irreducible component $C'_j$ such that the point $z'_j\in
C'_j$. The component $C'_j$
is a curve and $\deg C'_j$ is bounded from above by a polynomial in $d^s$ by
the
B\'ezout inequality. Construct the generic point of $C'_j$ and a system of
polynomial equations giving the
curve $C'_j$ using the algorithm from \cite{lit3}.
There is,
see e.g. \cite{lit25}, a family $\psi_1,\ldots , \psi_s$
of local parameters of the algebraic variety $W_1$ in the
point $z'_j$ with degrees polynomial in $d^s$. Hence by \rf{tr2} the curve
$C'_j$ contains only a polynomial in $d^n$ number of points $z''$ of $V$
such that the equality
\bequ{tr3}
T_{z'',V}\cap{\mathcal Z}(D^{(r+1)}_{s+1},\ldots , D^{(r+1)}_n)=\{0\}.
\end{equation}
does not hold. In particular the curve
$C'_j$ contains only a polynomial in $d^n$ number of singular points of $V$.
For a given point $z''\in C'_j$ one can compute applying the
algorithm of \trf{3} from \srf{2} and \srf{4}
all the multiplicities $\mu(z'',V_i)$,
$0\le i\le n$, within the time polynomial in $d^n$ and the size of input
including the size of the point $z''$ (the algorithm of \srf{2} and \srf{4}
does not use the algorithm under description).
Now $z''$ is a smooth point of $V$ if and only if $\mu(z'',V_s)=1$ and
$\mu(z'',V_u)=0$ for all $u\ne s$.

The algorithm from \srf{2} and \srf{4} also allows to construct
for  $z''\in W_1$ which is a smooth point of $V$ the family of linear forms
$\phi_{s+1},\ldots , \phi_n$ in $X_1,\ldots ,X_n$
with lengths of integer coefficients $O(n\log d)$ such that
\[T_{z'',W_1}\cap{\mathcal Z}(\phi_{s+1},\ldots , \phi_n)=\{0\} \]
(the tangent space of a smooth point coincides with the tangent cone in this
point).
Hence, we can apply \lrf{4} and construct the tangent space $T_{z'',W_1}$.
So one can decide for a given point $z''\in C'_j$ whether \rf{tr3} holds
within the time polynomial in $d^n$ and the size of input
including the size of the point $z''$.

Now enumerate integers $a=0,1,\ldots$. Construct, c.f. \cite{lit17}
step (\underline{16}), the intersection
\[B_j=C'_j\cap{\mathcal Z}(D^{(r+1)}_{j+1}-a)\subset{\mathbb
A}^n(\overline{k}).\]
If $B_j$ is infinite proceed to the next value of
$a$.

If $B_j$ is finite enumerate points $z''\in B_j$.
For a considered point $z''$ decide whether \rf{tr3}
holds. If equality \rf{tr3} does not hold proceed to the next element
$z''\in B_j$. If all the elements from $B_j$ are enumerated
proceed to the next value of $a$.
If equality \rf{tr3} holds set $a^{(r+1)}_{j+1}=a$ and $z'_{j+1}=z''$.

Thus, by the previous considerations we shall construct the required
$z'_{j+1}$ and the integer $a^{(r+1)}_{j+1}$  with the length
$O(n\log d)$.

If $j<n-1$ then replace $j$ by $j+1$ and
proceed to the next step of the second recursion.
If $j=n-1$ then set $z_{r+1}=z'_{j+1}$ and if $r<n-1$
replace $r$ by $r+1$ and proceed to the next step of the first recursion.
If $j=n-1$ and $r=n-1$ then the algorithm finishes its work.

Thus, we shall decide finally whether the family $X_{s+1},\ldots ,X_n$ is
algebraically independent in the field $\overline{k}(W_1)$.
The estimation for the working time of the described algorithm
follows immediately from the estimations for the working
time of the algorithms applied. \trf{5} is proved.



\section{Computation of the multiplicity of a point}\label{s2}


The aim of this and next sections is to proof \trf{3}.
Consider an algebraic variety $V$ such as in the Introduction and a point
$x$.
Denote by $\mathop{\rm con}\nolimits(x,V)$
the tangent cone of the variety $V$ in the point $x$.
If $x$ is not an isolated point of $V$ then $\mathop{\rm con}\nolimits(x,V)$
consists by definition of the lines containing $x$
which are limits of secants of $V$ containing $x$
 when another point of the
intersection of the secant with $V$ tends to $x$ (the degenerated case when
the line $l$
is such that $x\in l\subset V$ is not excluded: in this case this line
$l\subset\mathop{\rm con}\nolimits(x,V)$). Strictly speaking this definition
is valid for the case when the ground field is ${\mathbb C}$. Another
definition of
$\mathop{\rm con}\nolimits(x,V)$ is valid for arbitrary fields (and in the
case when $x$ is an arbitrary not necessary isolated point of $V$ or even
when
$x\not\in V$).  The cone is defined as
the variety of zeros of  the ideal generated by the forms of the least
degree of the
elements of the ideal of the initial variety in the case when it is affine
and the
point $x$ has zero coordinates, see just below. Factually,
if one uses the second
definition in many cases one can give the sense to the first one.

We can effect a linear automorphism of
${\mathbb P}^n(\overline{k})$ and shall
suppose without loss of generality (may be replacing
the ground field $k$)  that
$x=(1:0:\ldots :0)$. We shall use the following definition of the cone
$\mathop{\rm con}\nolimits(x,V)$.
Identify ${\mathbb A}^n(\overline{k})=
{\mathbb P}^n(\overline{k})\setminus{\mathcal Z}(X_0)$.
Let $X_1,\ldots ,X_n$ be the coordinate functions in ${\mathbb
A}^n(\overline{k})$
corresponding to $X_1/X_0,\ldots ,X_n/X_0$ in ${\mathbb P}^n(\overline{k})$.
Denote $U=V\setminus{\mathcal Z}(X_0)\subset {\mathbb A}^n(\overline{k})$.
Let $I(U)\subset k[X_1,\ldots ,X_n]$ be the ideal
of the affine variety $U$. Each
non--zero element $F\in k[X_1,\ldots ,X_n]$ is represented as a sum
$F=F_r+F_{r+1}+\ldots +F_m$ of homogeneous in
$X_1,\ldots ,X_n$ polynomials $F_j$  such that $\deg
F_j=j$ and $F_r\ne 0$. So for each non--zero element of
$F\in k[X_1,\ldots ,X_n]$ the form of the least degree $F_r\ne 0$ is
defined. Set also the form of the least degree of the zero
polynomial to be zero.
Denote by $I'(U)$ (respectively $I'(V)$) the ideal of the ring
$k[X_1,\ldots ,X_n]$ (respectively $k[X_0,\ldots , X_n]$)
generated by the forms of the least degree of the elements of $I(U)$. Then
$\mathop{\rm con}\nolimits(x,U)$ (respectively $\mathop{\rm
con}\nolimits(x,V)$)
is set of zeros of the ideal
$I'(U)$ in ${\mathbb A}^n(\overline{k})$ (respectively $I'(V)$ in
${\mathbb P}^n(\overline{k})$). Other definitions of the tangent cone,
 the proof of the equivalence of the  definition with
secants and  the one which we use see in
\cite{lit16}, \cite{lit27} and \lrf{consec} below.


Now let $x=(0,\ldots ,0)=(1:0:\ldots :0)$ and $Z$ be a new variable.
Introduce the variety of secants $\mathop{\rm sec}\nolimits(x,U)\subset
( {\mathbb A}^n\times{\mathbb A}^1)(\overline{k})$ of the variety
$U$ in the following way.
Let $I_1$ be the ideal of $k[X_1\ldots, X_n,Z]$
generated by all the polynomials $p(ZX_1,\ldots ,ZX_n)$  for all $p\in I(U)$.
 Then  $\mathop{\rm sec}\nolimits(x,U)$ is a union of all
components $U_1$ of the variety of zeros of the ideal $I_1$ in
$( {\mathbb A}^n\times{\mathbb A}^1)(\overline{k})$  such that
$U_1\not\subset {\mathcal Z}(Z)$.

\bl{consec}
The equality
$\mathop{\rm con}\nolimits (x,U)=\mathop{\rm sec}\nolimits(x,U)\cap{\mathcal
Z}(Z)$ holds. If $x\in U$ then
the dimension in the point $\dim_x U=\dim\mathop{\rm con}\nolimits (x,U)$.
\el
\bpr
If $x$ is an isolated point of $U$ or $x\not\in U$ the proof
is straightforward. So we shall assume that $x$
is not an isolated point of $U$.
We have the isomorphism of algebraic varieties
\bequ{cs}
\begin{array}{ll}
&U\times ({\mathbb A}^1\setminus\{0\})\simeq
\mathop{\rm sec}\nolimits(x,U)\setminus{\mathcal Z}(Z),\\
&((X_1,\ldots ,X_n),Z)\mapsto ((X_1/Z,\ldots ,X_n/Z),Z)
\end{array}\end{equation}
which induces the isomorphism of rings of regular functions
\[\overline{k}[X_1,\ldots ,X_n]/I(U)\otimes_{\overline{k}}
\overline{k}[Z,Z^{-1}]\simeq\overline{k}[Z,Z^{-1}]
\otimes_{\overline{k}[Z]}\overline{k}[X_1,\ldots ,X_n,Z]/I_1.\]
Let a polynomial $F$ is vanishing on $\mathop{\rm con}\nolimits(x,U)$. Then
$F^a$ is  the form of the least degree of a polynomial $F_1\in I(U)$
for some integer $a\ge 1$. Therefore,
$F^a=F_1(ZX_1,\ldots ,ZX_n)/Z^{a\deg F}+ZF_2$ for a polynomial $F_2$.
Hence $F$ is vaishing on $\mathop{\rm sec}\nolimits(x,U)\cap{\mathcal Z}(Z)$.
Conversely, let a polynomial $F\in\overline{k}[X_1,\ldots ,X_n,Z]$.
Let us show that  $F$ can be uniquely represented in the
in the form
\bequ{gr}
F=\sum_{i\in J}Z^iF_i(ZX_1,\ldots ,ZX_n)
\eequ
where $F_i\in \overline{k}[X_1,\ldots ,X_n]$,
$Z^iF_i(ZX_1,\ldots ,ZX_n)\in \overline{k}[X_1,\ldots ,X_n,Z]$
and $J\subset {\mathbb Z}$
is a finite set. Indeed, it is sufficient to check
\rf{gr} for monomials and in this case
it is straightforward. Note that \rf{gr} induces
the graduation of the algebra $\overline{k}[X_1,\ldots ,X_n,Z]$
such that $Z^iF_i(ZX_1,\ldots ,ZX_n)$ is the graded component of
$F$ of degree $i$.
Since $I_1$ has a system of homogeneous generators of degree $0$
relative to this graduation
the ideal $I_1$ is a graded ideal relative to the considered graduation.
If $F$ is vanishing on
$\mathop{\rm sec}\nolimits(x,U)$ then $Z^bF\in I_1$ for some integer $b\ge
1$.
Hence $Z^{b+i}F_i(ZX_1,\ldots ,ZX_n)\in I_1$ since
homogeneous components of an element of a graded ideal belong
to this ideal.
Since $Z$ is not vanishing on every component of $\mathop{\rm
sec}\nolimits(x,U)$ the
polynomials $F_i(ZX_1,\ldots ,ZX_n)$ are vanishing on
$\mathop{\rm sec}\nolimits(x,U)$ for all $i\in J$. Hence $F_i\in I(U)$,
$i\in J$ since
we have the surjective projection
\[\mathop{\rm sec}\nolimits(x,U)\setminus{\mathcal Z}(Z)\rightarrow
U\setminus\{x\},\:
(X_1,\ldots ,X_n,Z)\mapsto (ZX_1,\ldots ,ZX_n)\]
and $U\setminus\{x\}$ is a dense subset of $U$ in the Zariski topology
due to the fact that $x$ is not isolated point of $U$.
Set $J_1=\{i\in J: Z^iF_i(ZX_1,\ldots ,ZX_n)|_{Z=0}\ne 0\}$.
Then $\sum_{i\in J_1}Z^iF_i(ZX_1,\ldots ,ZX_n)|_{Z=0}$ belongs to the ideal
generated by the forms of the least degree of the ideal $I(U)$.
Now suppose that a polynomial $G$ is vanishing
on $\mathop{\rm sec}\nolimits(x,U)\cap{\mathcal Z}(Z)$.
Then there exists a polynomial $G_1$ and an integer $a\ge 1$ such that
$F=G^a+ZG_1$ is vanishing on $\mathop{\rm sec}\nolimits(x,U)$. Therefore,
$G^a=\sum_{i\in I_1}Z^iF_i(ZX_1,\ldots ,ZX_n)|_{Z=0}$ is vanishing on
$\mathop{\rm con}\nolimits(x,U)$. Hence $G$ is also vanishing on
$\mathop{\rm con}\nolimits(x,U)$.
The first assertion of the lemma is proved.

Note that \rf{cs} implies that $\dim\mathop{\rm sec}\nolimits(x,U)=
1+\dim U$. By \rf{cs} for any algebraic varieties $U_1$ and $U_2$
the equality $\mathop{\rm sec}\nolimits(x,U_1\cup U_2)=
\mathop{\rm sec}\nolimits(x,U_1)\cup
\mathop{\rm sec}\nolimits(x,U_2)$ holds.
Hence, to prove the last assertion
we can suppose without loss of generality that $U$
is irreducible and $x\in U$.
Then \rf{cs} implies that
$(x,0)\in\mathop{\rm sec}\nolimits(x,U)$. Thus,
$\mathop{\rm sec}\nolimits(x,U)$
has a non--empty intersection with ${\mathcal Z}(Z)$. Therefore,
$\dim\mathop{\rm con}\nolimits(x,U)=\dim_x U$. The lemma is proved.

Factually the equivalence
of the definition of the tangent cone with secants and
the second one with the ideal of forms of the least degree follows
from the proved lemma.

Consider in details the case when $V$ is a curve.
We need the following definition.
Let an algebraic curve $V\subset {\mathbb P}^{n}(\overline{k})$ and its
branch
$V^*$ in the point $x=(1:0:\ldots :0)$ with a uniformizing element $\tau$ be
given,
i.e. we have the
representations of the coordinate functions of $V$ as formal power series
\[(X_i/X_0)|_{V}=
\gamma_{i,m}\tau^m+\sum_{m<j\in {\mathbb Z}}\gamma_{i,j}\tau^j,\; 1\le i\le
n,\]
where $\gamma_{i,j}\in\overline{k}$ for all $1\le i\le n, 0<m\in {\mathbb Z}$
and
$(\gamma_{1,m},\ldots ,\gamma_{n,m})\ne (0,\ldots ,0)$. Then the tangent
line $l$
to this branch is the closure in ${\mathbb P}^n$ of the affine line $l'$
defined by the formula
\[l'=\{(\gamma_{1,m}t,\ldots ,\gamma_{n,m}t)\, :\, t\in \overline{k}\}.\]
Note that $l$ does not depend on the choice of the uniformizing element
$\tau$.
It turns out that $\mathop{\rm con}\nolimits(x,V)=\cup_{i\in I}l_i$ is a
union of all
tangent
lines $l_i$ to all branches of $V$ containing the point $x=(1:0:\ldots :0)$.

Now we can go to the description of the algorithm
for the computation of the multiplicity
of a point of an algebraic variety.
We shall use the construction from \cite{lit17} and the notations $W_s$,
$W'_s$,
$W''_s$,  $h_1,\ldots h_s$, $L^{(s)}_{s+1},\,\ldots,\, L^{(s)}_n$ for
$1\le s\le n-1$, and $W^{(1)}$, see \srf{1}.
Recall that $W^{(1)}$  is a union of all components $U_1$ of $W'_s$ such that
$U_1\cap {\mathcal Z}(h_{s+1})\ne U_1$. So $V_{s+1}$ is a union of some
components of
$W^{(1)}\cap {\mathcal Z}(h_{s+1})$.

If $s=0$ set $W'_s=W^{(1)}={\mathbb P}^n(\overline{k})$,
$W''_s=\emptyset$
and $L^{(s)}_n=X_j$ for $1\le j\le n$. So we shall suppose further that
$0\le s\le n-1$.
Our aim is to compute the multiplicity $\mu(x,V_{s+1})$ for $0\le s\le n-2$.
The case $s=n-1$ is trivial since in this case $V_{s+1}$ consists of points.
Further, decide using the algorithm from \srf{1.5} whether $x\in V_{s+1}$.
If $x\not\in V_{s+1}$ then $\mu(x,V_{s+1})=0$.
So in what follows we shall suppose without loss of generality
that $x\in V_{s+1}$.

Let us show that if linear forms $D_{s+2},\ldots ,D_n$ in $X_0,\ldots ,X_n$
with
coefficients from an extension $k_1$ of $k$ are given such that
 $W^{(4)}=W^{(1)}\cap {\mathcal Z}(h_{s+1})\cap{\mathcal Z}(D_{s+2},\ldots
,D_n)$ is
a finite
set in ${\mathbb P}^n(\overline{k_1})$ then one can construct within the
polynomial time in the size of input and $d^{s+1}$
 all the points from this finite set. Indeed, if $W^{(4)}$ is finite then
one see immediately from the construction of \cite{lit17} that
$W^{(1)}\cap{\mathcal Z}(D_{s+2},\ldots ,D_n)$ is a union of all
irreducible components $C$ of dimension one of
${\mathcal Z}(h_1,\ldots ,h_s,D_{s+2},\ldots ,D_n)$ such that $h_{s+1}$ is
not
identically zero on $C$.  Using the algorithm from \cite{lit3}
construct generic points and systems
of equations defining all such curves $C$ and may be some additional curves
$C'$ which are contained in the components of the dimension more than one of
the algebraic variety ${\mathcal Z}(h_1,\ldots ,h_s,D_{s+2},\ldots ,D_n)$.
The working time of the algorithm for constructing all
these curves is polynomial in $d^n$ and
the size of input.
Note that $h_{s+1}$ is identically zero on each $C'$. So
we can choose all the required curves $C$ among constructed

Now the union of all
intersections $C\cap{\mathcal Z}(h_{s+1})$ is the required set $W^{(4)}$.
Hence, it is sufficient to construct all the intersections $C\cap{\mathcal
Z}(h_{s+1})$.
The algorithm for this using the Newton--Puiseux expansions in the case when
$h_{s+1}$ is a linear form is described in \cite{lit17}, \cite{lit15}. The
general case
can be reduced to this one in the following way. Let $\xi$
be a constructed generic point
of $C$ and $k_1(\xi)$ be the field generated by coordinates of $\xi$. So
according
to \cite{lit3} $\xi$ is algebraic over a field $k_1(t)$ where $t=D'/D''$ is
a rational
function on $C$ which is equal to the quotient of two linear forms $D'$ and
$D''$
with coefficients from $k$ and
the degree $[k_1(\xi):k_1(t)]$ is bounded by a polynomial in $d^{s+1}$.
There are
at most ${\mathcal P}(d^{s+1})$ (for a polynomial ${\mathcal P}$)
 values of $t$ from $\overline{k_1}$ in which the specializations
of $\xi$ are not defined. The set of these values is included in the set of
roots of
 a polynomial $F_1\in k_1[t]$ which is known when the generic point is
constructed.
Herewith $\deg_tF_1\le {\mathcal P}(d^{s+1})$. Let $N_{k_1(\xi)/k_1(t)}$
denotes
the norm from the field $k_1(\xi)$ to the field $k_1(t)$. Compute
$N_{k_1(\xi)/k_1(t)}(h_{s+1}(\xi))=F_2/F_3$ where $F_2,F_3\in k_1[t]$ and
$\deg_tF_2\le {\mathcal P}(d^{s+1})$, $\deg_tF_1\le {\mathcal P}(d^{s+1})$.
Then the set of values  from $k_1$ which
can take $t$ on $C\cap{\mathcal Z}(h_{s+1})$
is included in the set of roots of the polynomial $F=F_1F_2F_3$. Construct
all the roots
 $y$ of this polynomial and the set $T_1$ of all the points  from  all the
intersection
$C\cap{\mathcal Z}(D'-D''y)$ and also $C\cap{\mathcal Z}(D'')$. Then
construct the
set $T_2$
of all the points $z\in T_1$ such that $h_{s+1}(z)=0$. Thus, we get
the required set
$C\cap{\mathcal Z}(h_{s+1})=T_2$.

In \cite{lit17} linear forms $L^{(s+1)}_{s+2},\ldots ,L^{(s+1)}_n$
are constructed with integer coefficients of the size $O(n\,\hbox{log}d)$.
 It follows from \cite{lit17} that for every irreducible component $U_1$ of
$W'_s$
 with $U_1\cap {\mathcal Z}(h_{s+1})\ne U_1$ the set
 \[U_1\cap {\mathcal Z}( h_{s+1})\cap{\mathcal Z}( L^{(s+1)}_{s+2},\ldots,
L^{(s+1)}_n)\] is a finite subset of ${\mathbb P}^n(\overline{k})$.
 Construct all the points from the set
\[W^{(1)}\cap {\mathcal Z}(h_{s+1})\cap{\mathcal
Z}(L^{(s+1)}_{s+2},\ldots ,L^{(s+1)}_n).\]
Construct a linear form $L''_0$
with integer coefficients of the size $O(n\,\hbox{log}d)$ which is not
vanishing in any
point of the set $W^{(1)}\cap {\mathcal Z}(h_{s+1})\cap
{\mathcal Z}(L^{(s+1)}_{s+2},\ldots ,L^{(s+1)}_n)$ and in the point $x$. So
$W^{(1)}\cap {\mathcal Z}(h_{s+1})\cap
{\mathcal Z}(L''_0,L^{(s+1)}_{s+2},\ldots ,L^{(s+1)}_n)=\emptyset$.

Set $L_j=L^{(s+1)}_j-(L^{(s+1)}_j/L''_0)(x)L''_0$ for all $s+2\le j\le n$
and $L_0=L''_0$.
Then
$W^{(1)}\cap {\mathcal Z}(h_{s+1})\cap{\mathcal Z}(L_{s+2},\ldots ,L_n)$ is
a finite
set containing
$x$ and $W^{(1)}\cap {\mathcal Z}(h_{s+1})\cap{\mathcal Z}(L_0,L_{s+2},\ldots
,L_n)=\emptyset$. Besides that, $ L_{s+2},\ldots ,L_n$ are linear forms in
$X_1,\ldots ,X_n$ since $x=(1:0:\ldots :0)$.

Set $V'=W^{(1)}\cap {\mathcal Z}(h_{s+1})$ and $U'=V'
\setminus{\mathcal Z}(X_0)\subset {\mathbb A}^n(\overline{k})$.
Hence, the dimension of
every irreducible component of $V'$ is $n-s-1$ and $x\in V'$.

Our aim now is to construct a family of linear forms $M_0,M_{s+2},
M_{s+3},\ldots ,M_n$
with coefficients from $\mathbb {Z}$ of the length $O(n\log \, d)$
such that $M_0=L_0$, the forms $M_{s+2},\ldots ,M_n\in k[X_1,\ldots ,$
$X_n]$ and
\begin{eqnarray*}
&&V'\cap {\mathcal Z}(M_0,M_{s+2}, M_{s+3},\ldots ,M_n)=\emptyset,\\
&&\mathop{\rm con}\nolimits(x,V')\cap {\mathcal Z}(M_0,M_{s+2},\ldots
,M_n)=\emptyset
\end{eqnarray*}
in ${\mathbb P}^{n}(\overline{k})$.


As in \srf{1} construct a real structure for the field $k$, see
\cite{lit15},
\cite{lit17}, which induces a real structure on $\overline{k}$. Let
$\varepsilon_i>0$  be an infinitesimal relative to the
 field $k(\varepsilon_0,\ldots ,\varepsilon_{i-1})$, $0\le i\le 2$, and
the field $K_2=k(\varepsilon_0,\varepsilon_1,\varepsilon_2)$.

If $z\in \overline{k(\varepsilon_0,\ldots ,\varepsilon_i)}$,
$0\le i\le 2$, is not infinitely
great relative to the field $\overline{k(\varepsilon_0,\ldots
,\varepsilon_{i-1})}$
the the standard part $\hbox{st}_{\varepsilon_i}(z)\in
\overline{k(\varepsilon_0,\ldots ,\varepsilon_{i-1})}$ is defined, see
\cite{lit17},
If $z=(z_1,\ldots z_n)\in
{\mathbb A}^{n}(\overline{k(\varepsilon_0,\ldots ,\varepsilon_i)})$ and all
the
standard
parts $\hbox{st}_{\varepsilon_i}(z_j)$, $1\le j\le n$ are defined then set
\[\hbox{st}_{\varepsilon_i}(z)=(\hbox{st}_{\varepsilon_i}(z_1),\ldots ,
\hbox{st}_{\varepsilon_i}(z_n))\in
{\mathbb A}^{n}(\overline{k(\varepsilon_0,\ldots ,\varepsilon_{i-1})}).\]
Besides that, the  maps of the standard part
\[\hbox{st}_{\varepsilon_i}\, :\,
{\mathbb P}^{n}(\overline{k(\varepsilon_0,\ldots
,\varepsilon_i)})\longrightarrow
{\mathbb P}^{n}(\overline{k(\varepsilon_0,\ldots ,\varepsilon_{i-1})})\]
are defined, see \cite{lit17}, for $i=0,1,2$.

Denote $L={\mathcal Z}(L_{s+2},\ldots ,L_n)\subset {\mathbb
A}^{n}(\overline{k})$
where ${\mathbb A}^{n}$ has the coordinate functions $X_1,\ldots ,X_n$.
Consider the following system of equations and inequalities with
coefficients from
the field $K_2$ in $X_1\ldots ,X_n,Y_1\ldots ,Y_n, Z_1,\ldots ,Z_n, Z$
\bequ{4}\left\{\begin{array}{ll}
 h_i(1,Z_1,\ldots ,Z_n)=0, &  1\le i \le s, \\
 h_{s+1}(1,Z_1,\ldots ,Z_n)Z-1=0, & \\
 h_i(1,X_1,\ldots ,X_n)=0, &  1\le i \le s+1, \\
 \sum_{1\le i\le n}|X_i-Z_i|^2\le \varepsilon_2, &  \\
 \sum_{1\le i\le n}|X_i|^2= \varepsilon_1^2, &  \\
 L_j(Y_1,\ldots ,Y_n)=0, & s+2\le j\le n, \\
 \sum_{1\le i\le n}|X_i-Y_i|^2<\varepsilon_0\varepsilon_1^2. &
 \end{array}
 \right.
\eequ

\bl{6}
Let the family $L_0,L_{s+2}, L_{s+3},\ldots ,L_n$ of linear forms be as
above.
The following conditions are equivalent
\begin{enumerate}
 \renewcommand{\labelenumi}{(\roman{enumi})}
\item $\mathop{\rm con}\nolimits(x,V')\cap {\mathcal Z}(L_0,L_{s+2},
L_{s+3},\ldots
,L_n)=\emptyset$
in ${\mathbb P}^{n}(\overline{k})$
\item $\mathop{\rm con}\nolimits(x, U')\cap {\mathcal Z}(L_{s+2},
L_{s+3},\ldots
,L_n)=\{x\}$
in ${\mathbb A}^{n}(\overline{k})$
\item system \rf{4} has no solutions in
${\mathbb A}^{3n+1}(\overline{K_2})$.
\end{enumerate}
\el

\noindent
 {\bf PROOF} \quad
The equivalence of (i) and (ii) is straightforward.

Suppose that there exists a solution
\[(x^*_1,\ldots ,x^*_n,y^*_1,\ldots
,y^*_n,z^*_1,\ldots ,z^*_n,z')\in
{\mathbb A}^{3n+1}(\overline{K_2})\]
 of system \rf{4}. Denote
$x^*=(x^*_1,\ldots ,x^*_n)$ and $y^*=(y^*_1,\ldots ,y^*_n)$.
We have
 \[\begin{array}{ll}
 h_i(1,z^*_1\ldots ,z^*_n)=0, &  1\le i \le s, \\
 h_{s+1}(1,z^*_1\ldots ,z^*_n)\ne 0, & \\
 h_i(1,x^*_1\ldots ,x^*_n)=0, &  1\le i \le s+1, \\
 \sum_{1\le i\le n}|x^*_i-z^*_i|^2\le \varepsilon_2, &
\end{array}\]
Therefore, $\sum_{1\le i\le n}|\hbox{st}_{\varepsilon_2}x^*_i-z^*_i|^2$ is
infinitesimal
relative to the field $k(\varepsilon_0,\varepsilon_1)$.
The point
$\hbox{st}_{\varepsilon_2}x^*$ is defined over the
field $\overline{k(\varepsilon_0,\varepsilon_1)}$. Hence, the polynomials
$h_1,\ldots , h_s$ are vanishing in the point $\hbox{st}_{\varepsilon_2}x^*$.
The polynomial
$h_{s+1}$ is not vanishing in the point $x^*$ which is infinitesimal close to
$\hbox{st}_{\varepsilon_2}x^*$. Thus, $\hbox{st}_{\varepsilon_2}x^*\in U'$,
c.f. also \cite{lit17} the proof of Lemma~13.
Therefore, the line
(the standard parts here are considered in ${\mathbb A}^n$)
\[l=\{(\hbox{st}_{\varepsilon_0}\circ
\hbox{st}_{\varepsilon_1})(\hbox{st}_{\varepsilon_2}y^*/\varepsilon_1)t\,
:\, t\in
\overline{k}\}\subset \mathop{\rm con}\nolimits(x,U')\cap{\mathcal
Z}(L_{s+2},\ldots
,L_n),\]
since $l$ is in the set of zeros of the corresponding ideal of the  forms of
the least
degree.

Conversely, suppose that there exists a line $l\subset\mathop{\rm
con}\nolimits(x,U')
\cap {\mathcal Z}( L_{s+2},\ldots ,L_n)$, $x\in l$. Choose a point $x\ne
(l_1,\ldots ,l_n)\in l\subset {\mathbb A}^{n}(\overline{k})$.
Then there exists an algebraic  curve
$C\subset \mathop{\rm sec}\nolimits(x,U')$ such that $\{(l_1,\ldots ,l_n)\}$
is a component
of $C\cap{\mathcal Z}(Z)$.
So there exists a branch $C^*$ of $C$ in the point $(l_1,\ldots ,l_n)$
with a uniformizing element $\tau$ such that the corresponding
 representations of the coordinate functions of $C$ as formal power series
has the form
\begin{eqnarray*}
&&Z|_{C}=z_m\tau^m+\sum_{m<j\in{\mathbb Z}}z_j\tau^j, \\
&&X_i|_{C}=l_i+\sum_{0<j\in{\mathbb Z}}x_{i,j}\tau^j, \quad 1\le i\le n
\end{eqnarray*}
where $0<m\in{\mathbb Z}$, $z_j,x_{i,j}\in \overline{k}$ for all $j$,
$z_m\ne 0$.
Consider the irreducible algebraic curve $C_1$ which has the branch
$C_1^*$ in the point $x$ with a uniformizing element $\tau$
such that
\[X_i|_{C_1}=(z_m\tau^m+\sum_{m<j\in{\mathbb Z}}z_j\tau^j)
(l_i+\sum_{0<j\in{\mathbb Z}}x_{i,j}\tau^j), \quad 1\le i\le n. \]
Then $C_1$ is contained in $U'$ and has the tangent line $l$.
Choose a new uniformizing element $\tau_1$ of the branch $C_1^*$ such
that $\tau_1\in \overline{k}(C_1)$ where $\overline{k}(C_1)$ is the field of
rational
functions on $C_1$. So we have
\[X_i|_{C_1}=w_{i,m}\tau_1^m+\sum_{m<j\in{\mathbb Z}}w_{i,j}\tau_1^j,\quad
 1\le i\le n\]
where $w_{i,j}\in \overline{k}$ for all $j$ and $x\ne (w_{1,m},\ldots
,w_{n,m})\in l$.
Denote $X_i|_{C_1}=w_i$ for $1\le i\le n$.
So $(w_1,\ldots ,w_n)\in C_1$ in ${\mathbb A}^n(\overline{k((\tau_1))})$
where
$k((\tau_1))$ is a field of formal power series in $\tau_1$ and
$(w_1,\ldots ,w_n)$
corresponds to the embedding $\overline{k}[C_1]\hookrightarrow
\overline{k}[[\tau_1]]$
where $\overline{k}[C_1]$ is the ring of regular functions on $C_1$ and
$\overline{k}[[\tau_1]]$  is  the ring of formal
power series in $\tau_1$.

Let the real structure of $\overline{k}$ be given by
the isomorphism $\overline{k}\simeq \widetilde{K}[\sqrt{-1}]$ where
$\widetilde{K}$ is a real closed field. By the definition the real
structure on the field $\overline{k(\varepsilon_1)}$
is induced by the real structure on the field of fractional power series in
$\varepsilon_1$ with coefficient from $\overline{k}$.
 The real elements from this field are
fractional power series with coefficients from  $\widetilde{K}$.

Let us show that there exists a point $x^*\in C_1$ in ${\mathbb
A}^n(\overline{k(\varepsilon_1)})$
such that $|x^*|^2=\varepsilon_1^2$ and $x\ne
\hbox{st}_{\varepsilon_1}(x^*/\varepsilon_1)\in l$. Besides that, this
point $x^*$
will be defined by a through homomorphism
\[\overline{k}[C_1]\hookrightarrow \overline{k}[[\tau_1]]\rightarrow
\overline{k}[[\varepsilon_1^{1/m}]]\]
such that $\tau_1\mapsto\tau^*\in\widetilde{K}[[\varepsilon_1^{1/m}]]$.
Here $\overline{k}[[\varepsilon_1^{1/m}]]$ is the  ring of formal
power series in  $\varepsilon_1^{1/m}$.

To prove this assertion represent $w_{i,j}=u_{i,j}+\sqrt{-1}v_{i,j}$
where $u_{i,j},v_{i,j}\in \widetilde{K}$ for all $i,j$. Set
\[u_i=u_{i,m}\tau_1^m+\sum_{m<j\in{\mathbb Z}}u_{i,j}\tau_1^j,\;
v_i=v_{i,m}\tau_1^m+\sum_{m<j\in{\mathbb Z}}v_{i,j}\tau_1^j,\; 1\le i\le n.\]
So $w_i=u_{i}+\sqrt{-1}v_{i}$ for $1\le i\le n$.

The functions $w_i$ are algebraic over the field $\overline{k}(\tau_1)$ and
hence they are algebraic over the field $\widetilde{K}(\tau_1)$ for $1\le
i\le n$.
 We have
the embedding $\overline{k}[C_1]\hookrightarrow
\widetilde{K}[\sqrt{-1}]((\tau_1))$
of $\overline{k}[C_1]$ into the field of formal power
series $ \widetilde{K}[\sqrt{-1}]((\tau_1))$.
Therefore, the functions $u_{i}-\sqrt{-1}v_{i}$ are also algebraic over the
field
$\widetilde{K}(\tau_1)$. Hence $u_i,v_i$ are algebraic over
$\widetilde{K}(\tau_1)$
and over $\overline{k}(\tau_1)$ for all $1\le i\le n$.

There exists a formal power series
$\tau^*\in\widetilde{K}((\varepsilon_1^{1/m}))$
such that
\[\tau^*=(\sum_{1\le i\le n}|w_{i,m}|^2)^{-1/(2m)}\varepsilon_1^{1/m}+
\sum_{m<j\in{\mathbb Z}}\tau^*_j\varepsilon_1^{j/m},\; \tau^*_j\in
\widetilde{K}\]
and the substitution $\tau_1\mapsto\tau^*$ defines the homomorphism
$\psi :\overline{k}[[\tau_1]]\rightarrow\overline{k}[[\varepsilon_1^{1/m}]]$
for which $\sum_{1\le i\le n}(u_i^2+v_i^2)|_{\tau_1=\tau^*}=\varepsilon_1^2$
(it is just the inversion of a function in the ring of formal power series).

The element $\tau^*\in\overline{k(\varepsilon_1)}$ since $\psi$ is
a homomorphism and $\sum_{1\le i\le n}(u_i^2+v_i^2)$ and $\tau_1$ are
algebraically independent  over $\overline{k}$. Now
set $x_i^*=w_i|_{\tau_1=\tau^*}$ for $1\le i\le n$. Then similarly
$x_i^*\in\overline{k(\varepsilon_1)}$ for $1\le i\le n$.
Set $x^*=(x_1^*,\ldots ,x_n^*)$. Then $x^*\in C_1$,
$|x^*|^2=\varepsilon_1^2$ and $x\ne
\hbox{st}_{\varepsilon_1}(x^*/\varepsilon_1)\in l$ since $\psi$ is a
homomorphism. Our assertion is proved.

Set $y^*=\varepsilon_1\hbox{st}_{\varepsilon_1}(x^*/\varepsilon_1)$.
Since $x^*\in W^{(1)}\cap{\mathcal Z}(h_{s+1})$ there exists a point
$z^*\in {\mathbb A}^n(\overline{K_2})$ such that
$(x^*,y^*,z^*,h_{s+1}(z^*)^{-1})$
gives a solution of system \rf{4}. The lemma is proved.

Return to the description of the algorithm.
Decide whether  system \rf{4} has a solution.
If  system \rf{4} has no solutions then by \lrf{6} we can set
 $M_i=L_i$ for $i=0,s+2,\ldots ,n$.
Suppose that system \rf{4} has a solution.
Construct such a solution $(x^*,y^*,z^*,h_{s+1}(z^*)^{-1})\in
{\mathbb A}^{3n+1}(\overline{K_2})$,
see \cite{lit15}, \cite{lit17}.
Recall that $L={\mathcal Z}(L_{s+2}, L_{s+3},\ldots ,L_n)$. Construct,
see the proof of \lrf{6}, the line
\[l=\{(\hbox{st}_{\varepsilon_0}\circ
\hbox{st}_{\varepsilon_1})(\hbox{st}_{\varepsilon_2}y^*/\varepsilon_1)t\,
:\, t\in
\overline{k}\}\subset \mathop{\rm con}\nolimits(x,U')\cap L.\]
Construct a linear forms $L_1$ in $X_1,\ldots ,X_n$
such that $L_1$ is not identically zero on the line $l$.
Denote $L'={\mathcal Z}( L_{1},L_{s+2}, L_{s+3},\ldots ,L_n)$. This is a
linear
subspace such that $L'+l=L$.

Define the line
\[l'=\{x^*t\, :\, t\in\overline{K_2}\}.\]
Construct the linear subspace $L'+l'$. Then the subspace $L'+l'$
is infinitely close to $L'+l$ since $x^*,y^*$ are obtained from  a solution
of \rf{4}.
The subspace $L'+l'={\mathcal Z}(L'_{s+2},\ldots ,L'_n)$
in ${\mathbb A}^{n}(\overline{K_2})$ where $L'_j=L_j-\delta_jL_1$
and $\delta_j$ are infinitesimal relative to the field $k$ for  $s+2\le j\le
n$.
Construct such linear forms
$L'_{s+2},\ldots ,L'_n\in\overline{K_2}[X_1,\ldots ,X_n]$.
Set also $L'_0=L_0$.

Now by \prf{1}  we have
\[\# V'\cap {\mathcal Z}(L_{s+2},\ldots ,L_n)\le
\# V'\cap {\mathcal Z}(L'_{s+2},\ldots ,L'_n)<+\infty.\]
Further, there exist two points $x,x^*\in
V'\cap {\mathcal Z}(L'_{s+2}, L'_{s+3},\ldots ,L'_n)$ such that their
standard
parts in ${\mathbb P}^{n}(\overline{k})$ are equal to $x$. Therefore,
\[N=
\# V'\cap {\mathcal Z}(L_{s+2}, L_{s+3},\ldots ,L_n)<
\# V'\cap {\mathcal Z}(L'_{s+2}, L'_{s+3},\ldots ,L'_n)=N'.\]

Set  $M_0=L_0$.
Now our aim is to apply the analog of the second auxiliary algorithm from
\cite{lit17}
to the linear forms
$L'_0,L'_{s+2},\ldots ,L'_n$ and construct linear forms $M_{s+2},\ldots
,M_n$ in
$X_1,\ldots ,X_n$
which have integer coefficients with lengths $O(n\log \,d)$ such that
$\# V'\cap {\mathcal Z}(M_{s+2},\,\ldots,\, M_n)\ge N'$ and
$V'\cap {\mathcal Z}(M_0,M_{s+2},\,\ldots,$ $M_n)=\emptyset$.
Note here that the second condition can be checked effectively  during
this auxiliary algorithm. Indeed, suppose we replace one coefficient, say in
$M_{s+2}$
(we do not introduce new notations for linear forms which appear during
the second auxiliary algorithm but use for them the notation
$M_{s+2},\,\ldots ,\, M_n$). Then as it is known from the previous step of
the
implemented algorithm $\# V'\cap {\mathcal Z}(M_0,M_{s+3},\,\ldots\,
,M_n)<+\infty$ and, therefore, the points from
this set can be computed as it
was described above.  Further we can substitute the coordinates of these
points in $M_{s+1}$ with the replaced coefficient and therefore decide
whether $V'\cap {\mathcal Z}(M_0,M_{s+2},\,\ldots\, ,M_n)=\emptyset$ for new
obtained linear forms.

If this second condition is satisfied then
$\# V'\cap {\mathcal Z}(M_{s+2},\,\ldots,\, M_n)<+\infty$ and the first
condition can be also
verified as it was described above.
Thus, we can apply the analog of the second auxiliary algorithm from
\cite{lit17}
to the linear forms
$L'_0,L'_{s+2},\ldots ,L'_n$ and construct the required linear
forms $M_{s+2},\ldots ,M_n$ in $X_1,\ldots ,X_n$.


After that, return recursively to the beginning of the algorithm described
replacing the forms $L_0,L_{s+2},\ldots ,L_n$ by
$M_0,M_{s+2},\ldots ,M_n$. Since $N'>N$ there are
at most $d^{s+1}$ such returns in the algorithm.

So we shall obtain finally by \lrf{6} a family of linear forms
$M_0,M_{s+2}$, $M_{s+3},\ldots ,M_n$
such that $M_0=L_0$, the forms $M_{s+2},\ldots ,M_n\in
k[X_1,\ldots ,X_n]$ have
integer coefficients with lengths $O(n\log \,d)$,
\begin{eqnarray*}
&&V'\cap {\mathcal Z}(M_0,M_{s+2}, M_{s+3},\ldots ,M_n)=\emptyset,\\
&&\mathop{\rm con}\nolimits(x,V')\cap {\mathcal Z}(M_0,M_{s+2},
M_{s+3},\ldots ,M_n)=\emptyset
\end{eqnarray*}
in ${\mathbb P}^{n}(\overline{k})$.
We shall suppose replacing as described above the forms $L_0,L_{s+2},\ldots
,$ $L_n$ by
$M_0,M_{s+2},\ldots ,M_n$ that these properties are satisfied for
$L_0,L_{s+2},\ldots ,L_n$,
i.e. the forms $L_{s+2}, L_{s+3},\ldots ,L_n\in k[X_1,\ldots ,X_n]$ have
integer coefficients with lengths $O(n\log \, d)$ and
\begin{eqnarray*}
&&V'\cap {\mathcal Z}(L_0,L_{s+2}, L_{s+3},\ldots ,L_n)=\emptyset,\\
&&\mathop{\rm con}\nolimits(x,V')\cap {\mathcal Z}(L_0,L_{s+2},
L_{s+3},\ldots ,L_n)=\emptyset
\end{eqnarray*}
in ${\mathbb P}^{n}(\overline{k})$.

Construct, see above,
all the points $x_u$, $1\le u\le N$, from the set
\[V'\cap{\mathcal Z}(L_{s+2}, L_{s+3},\ldots ,L_n)\]
in ${\mathbb P}^{n}(\overline{k})$.
We can suppose without loss of generality that
$x_1=x$. Construct a linear form $L_{s+1}$ in $X_1,\ldots ,X_n$
with coefficients from $\mathbb {Z}$ of the length $O(n\log \,
d)$ such
that $L_{s+1}(x_u)\ne 0$ for all $2\le j\le N$.
Denote by
\[p_x\, :\, V'\setminus\{x\}\longrightarrow {\mathbb
P}^{n-s-1}(\overline{k}), \quad
\; (X_0:\ldots :X_n)\mapsto (L_{s+1}:L_{s+2}:\ldots :L_n)\]
the linear projection.

\section{Background lemmas}\label{s3}

Let $W\subset {\mathbb P}^n(\overline{k})$ be an
irreducible algebraic variety
of the dimension $\dim W=n-s-1$ and
$L_{s+1}$, $L_{s+2}, \ldots ,L_n
\in\overline{k}[X_1,\ldots ,X_n]$ be linear forms.
Consider the following conditions. The intersection
\bequ{pr0}
W\cap{\mathcal Z}(L_{s+1},\ldots , L_n)\setminus\{x\}=\emptyset.
\eequ
The equality \rf{pr0} holds and the projection
\[
 p\, :\, W\setminus\{x\}\longrightarrow {\mathbb P}^{n-s-1}(\overline{k}),
\quad (X_0:\ldots :X_n)\mapsto (L_{s+1}:L_{s+2}:\ldots :L_n)
\]
is a dominant morphism, i.e. the closure in the Zariski topology
\bequ{pr}
\overline{p(W\setminus\{x\})}=
{\mathbb P}^{n-s-1}(\overline{k}).
\eequ
The intersection
\bequ{cpr}
\mathop{\rm con}\nolimits(x,W)\cap {\mathcal Z}(L_{s+1},L_{s+2}, \ldots
,L_n)\setminus\{x\}=\emptyset \quad
\mbox{if} \quad x\in W.
\eequ


\bl{a0}
Let $W\subset {\mathbb P}^n(\overline{k})$ be an irreducible algebraic
variety of the dimension $\dim W=n-s-1$ and
the linear forms $L_{s+1}$, $L_{s+2}, \ldots ,L_n
\in\overline{k}[X_1,\ldots ,X_n]$  satisfy condition
\rf{pr0}. Let
\[1<\# W\cap{\mathcal Z}(L_{s+2},\ldots , L_n)<+\infty\]
in ${\mathbb P}^n(\overline{k})$.
Then the morphism $p$ is dominant, i.e. the equality \rf{pr} holds.
\el

\bpr
Indeed, we should show that the closure $F$ in the Zariski
topology of the image $p(W\setminus\{x\})$ coincides with
${\mathbb P}^{n-s-1}(\overline{k})$.
By \prf{1} for every
$\lambda_{s+2},\ldots ,\lambda_n\in \overline{k(\varepsilon)}$
which are infinitesimal relative to the field $k$   the set \\
$W\cap{\mathcal Z}(L_{s+2}-\lambda_{s+2}L_{s+1},\ldots ,
L_n-\lambda_{n}L_{s+1})\setminus\{x\}\ne\emptyset$
in ${\mathbb P}^{n}(\overline{k(\varepsilon)})$. Therefore,
$p^{-1}((1:\lambda_{s+2}:\ldots :\lambda_n))$ is not empty in
${\mathbb P}^{n-s}(\overline{k(\varepsilon)})$. Therefore,
\[F(\overline{k(\varepsilon)})=
{\mathbb P}^{n-s-1}(\overline{k(\varepsilon)}),\]
and hence, $F={\mathbb P}^{n-s-1}(\overline{k})$. The lemma is proved.

\lrf{a0} implies that condition \rf{pr} is
satisfied for any component $W$ of $V'$ such that
there exists $x_u\in W$, $u\ge 2$, and the linear
forms $L_{s+1},L_{s+2}, \ldots ,L_n$ constructed in \srf{2}.

Denote by ${\mathcal H}$ the set of all families $H$ of $n-s$ linear forms
$H_{s+1},H_{s+2}, \ldots ,$ $H_n\in \overline{k}[X_1,\ldots ,X_n]$. We
can identify ${\mathcal H}$ with the algebraic variety
${\mathbb A}^{(n-s)n}(\overline{k})$.

Denote by ${\mathcal H}_1$ the subset of ${\mathcal H}$ consisting of all
families
$H$ of  $n-s$ linear forms $H_{s+1},H_{s+2},\ldots$, $H_n$ such that
\[W\cap{\mathcal Z}(H_{s+1},H_{s+2},\ldots ,H_n)=\{x\}.\]

\bl{a1}
Let $W\subset {\mathbb P}^n(\overline{k})$ be an irreducible algebraic
variety of the dimension $\dim W=n-s-1$
such that there are linear forms $L_{s+1}$, $L_{s+2}, \ldots ,L_n
\in\overline{k}[X_1,\ldots ,X_n]$  satisfying
\rf{pr0} and \rf{pr}.
Then ${\mathcal H}_1$ contains  a non-empty open subset of ${\mathcal H}$ in
the Zariski topology.
\el
\bpr
Indeed, denote by
\[\pi : {\mathbb P}^{n}\setminus\{x\} \rightarrow {\mathbb P}^{n-1},\;
(X_0:\ldots :X_n)\mapsto (X_1:\ldots :X_n)\]
the linear projection
Note that the closure in the Zariski topology of the image
$\pi (W\setminus\{x\})$ is an irreducible variety of
 the dimension $n-s-1$ since the closure in the Zariski topology of
$p(W\setminus\{x\})$ is ${\mathbb P}^{n-s-1}$.
Hence there exist homogeneous polynomials $F_1,\ldots ,F_{s}
\in K[X_1\ldots ,X_n]$ such that $\dim{\mathcal Z}(F_1,\ldots ,F_{s})=n-s-1$
in
${\mathbb P}^{n-1}$ and
$\pi (W\setminus\{x\})\subset {\mathcal Z}(F_1,\ldots ,F_{s})$.
The condition
\[T={\mathcal Z}(F_1,\ldots ,F_{s},H_{s+1},H_{s+2},\ldots ,H_n)=\emptyset\]
in ${\mathbb P}^{n-1}(\overline{k})$ implies that
$W\cap{\mathcal Z}(H_{s+1},H_{s+2},\ldots,H_n)\setminus\{x\}=\emptyset$. But
$T=\emptyset$ is
equivalent to the condition that
at least one coefficient of the corresponding $U$--resultant
is not equal to zero.  Now the  assertion of the lemma follows
from the fact that the
coefficients of the $U$--resultant are polynomials in coefficients of linear
forms  $H_{s+1},H_{s+2}, \ldots ,H_n$. The lemma is proved.

\bl{a4}
Let $W\subset {\mathbb P}^n(\overline{k})$ be an irreducible algebraic
variety of the dimension $\dim W=n-s-1$
such that there are linear forms $L_{s+1}$, $L_{s+2}, \ldots ,L_n
\in\overline{k}[X_1,\ldots ,X_n]$  satisfying
condition \rf{cpr}.  Let $x\in W$.
Then there exists a non--empty open subset $U_4$ of
${\mathbb P}^{n-s-1}(\overline{k})$
such that $U_4\subset{\mathbb P}^{n-s-1}(\overline{k})
\setminus{\mathcal Z}(L_{s+1})$ and
if $(1:\lambda_{s+1}:\ldots :\lambda_n)\in U_4$ then
\[\mathop{\rm con}\nolimits(x,W)\cap
{\mathcal Z}(L_{s+2}-\lambda_{s+1}L_{s+1}, \ldots,
L_n-\lambda_nL_{s+1})=\{x\}.\]
\el
\bpr
We have $\dim\pi (\mathop{\rm con}\nolimits(x,W)\setminus\{x\})\le n-s-2$ and
\[\pi (\mathop{\rm con}\nolimits(x,W)\setminus\{x\})\cap
{\mathcal Z}(L_{s+1}, \ldots ,L_n)=\emptyset.\]
Thus, there exists a non--empty open subset $U_4\subset
{\mathbb P}^{n-s-1}(\overline{k})
\setminus{\mathcal Z}(L_{s+1})$
such that if $(1:\lambda_{s+1}:\ldots :\lambda_n)\in U_4$ then
\[\pi (\mathop{\rm con}\nolimits(x,W)\setminus\{x\})\cap
{\mathcal Z}(L_{s+2}-\lambda_{s+1}L_{s+1}, \ldots
,L_n-\lambda_nL_{s+1})=\emptyset.\]
Therefore, if $(1:\lambda_{s+1}:\ldots :\lambda_n)\in U_4$ then
\[\mathop{\rm con}\nolimits(x,W)\cap
{\mathcal Z}(L_{s+2}-\lambda_{s+1}L_{s+1}, \ldots
,L_n-\lambda_nL_{s+1})=\{x\}.\]
The lemma is proved.


Let $W$ be an irreducible algebraic variety from the formulation of \lrf{a1}
and $H$ be a family of $n-s$ linear forms $H_{s+1},H_{s+2}, \ldots ,H_n$
in $X_1,\ldots ,X_n$ with coefficients from
$\overline{k}$. Let $H\in {\mathcal H}_1$.
Denote by $p(H) : W\setminus\{x\}\rightarrow {\mathbb P}^{n-s-1}$ the
projection
corresponding to $p$  if we replace $L_{s+1},L_{s+2}, \ldots ,L_n$ by
$H_{s+1},H_{s+2}, \ldots ,$ $H_n$. Set
\bequ{fi}  \begin{array}{ll}
& U_3(H)=\{z\in {\mathbb P}^{n-s} : \# p(H)^{-1}(z)<+\infty\,\}, \\
&\delta(H)=\sup\{\# p(H)^{-1}(z) : z\in U_3(H)\,\}, \\
& U(H)=\{z\in U_3(H) : \# p(H)^{-1}(z)=\delta(H)\},  \\
&\delta=\sup\{\# p(H)^{-1}(z) : z\in U_3(H), H\in {\mathcal H}_1\,\}.
\end{array} \end{equation}
Note that if $H\in {\mathcal H}_1$ and
the projection $p(H)$ is not dominant then
by \lrf{a0} $\delta(H)=0$ and $U_3(H)=U(H)$
contains a non--empty open in the Zariski topology
subset of ${\mathbb P}^{n-s-1}(\overline{k})$.

Denote by $\widetilde{H}$ the family
$\widetilde{H}_{s+1},\widetilde{H}_{s+2},
\ldots ,\widetilde{H}_n$ which is a
the generic element of ${\mathcal H}_1$, i.e. the field $K$
generated by the coefficients of linear forms from $\widetilde{H}$ over $k$
is purely transcendental over $\overline{k}$ of
the transcendency degree $(n-s)n$.


\bl{a2}
Let $W$ be as in the formulation of \lrf{a1}
and $H\in {\mathcal H}_1$ be such that
the projection $p(H)$ is a dominant morphism.
Then $0<\delta(H)<+\infty$ and
$U(H)$ contains a non--empty open in the Zariski topology subset $U$
of ${\mathbb P}^{n-s-1}(\overline{k})$ such that for every $x^*\in U$
for every $y\in p^{-1}(x^*)$ the point $y$ is a smooth point of the
variety $W$ and the differential of $p$ in the point $y$
\[d_yp\, :\, T_{y,W}\longrightarrow T_{x,{\mathbb P}^{n-s}}\]
is an isomorphism of tangent spaces $T_{y,W}$ and $T_{x,{\mathbb P}^{n-s}}$
of the varieties $W$ and ${\mathbb P}^{n-s}(\overline{k})$ in the points $y$
and $x$ respectively.
\el
\bpr
Let $Y\in \overline{k}[X_0,\ldots , X_n]$ be a linear form.
Consider the linear projection
\[p_1\, :\, W\setminus\{x\}\longrightarrow {\mathbb
P}^{n-s}(\overline{k}),\quad
(X_0 \, :\, \ldots \, : \, X_n)
\mapsto (Y\, :\, H_{s+1} \, : \, H_{s+2} \, :\ldots : \, H_n).\]
Since $p(H)$ is a dominant morphism there exists an irreducible homogeneous
polynomial
$G\in
\overline{k}[Y,H_{s+1},H_{s+2},\ldots ,H_n]$ such that the closure of $p_1(W)$ in the
Zariski topology
$\overline{p_1(W)}={\mathcal Z}(G)$ and $p_1(W)$
contains an open subset of the closed set ${\mathcal Z}(G)$.

By the theorem about primitive element for fields
there exists a linear form $Y\in \overline{k}[X_0,\ldots ,X_n]$
such that that the morphism $p_1$
induces the birational isomorphism $W\setminus\{x\} \longrightarrow
{\mathcal Z}(G)$
which we shall denote
$p_2$. So there exists an open subset $U_1\subset W$ such that
$p_2(U_1)$ is open in ${\mathcal Z}(G)$ and $p_2$ induces the isomorphism
$U_1\rightarrow p_2(U_1)$.

Denote $U_2={\mathcal Z}(G)\setminus{\mathcal Z}(H_{s+1}, H_{s+2},\ldots
,H_n)$.
There exists a projection
$p_3\, :\, U_2\longrightarrow {\mathbb P}^{n-s}(\overline{k})$
such that $p=p_3\circ p_2$ (on the open subset where the right and left parts
are defined). Denote by $R=\hbox{Res}_Y(G,G'_Y)$ the discriminant
of the
polynomial $G$ relatively to $Y$. Then $0\ne R$ is a homogeneous polynomial
since $G$ is a separable homogeneous polynomial.

If $R(x^*)\ne 0$ then
the cardinality $\# p_3^{-1}(x^*)=\deg_Y G$,
 for every $y\in p_3^{-1}(x^*)$ the point $y$ is a smooth point of the
variety
 $U_2$ and the differential of $p_3$ in the point $y$
\[d_yp_3\, :\, T_{y,U_2}\longrightarrow T_{x,{\mathbb P}^{n-s}}\]
is an isomorphism of tangent spaces $T_{y,p_1(W)}$ and $T_{x,{\mathbb
P}^{n-s}}$
of the varieties $U_2$ and ${\mathbb P}^{n-s}(\overline{k})$ in the points
$y$
and $x$
respectively. The last statement follows here just from the fact that
$G'_Y(y)\ne 0$ since $R(x^*)\ne 0$.

Denote by $F$ the closure in the Zariski topology of the set
$p_3(U_2\setminus p_2(U_1))$
Set $U={\mathbb P}^{n-s-1}(\overline{k})\setminus({\mathcal Z}(R)\cup F)$
(hence $U\ne \emptyset$). Then for every $x^*\in U$
 \begin{enumerate}
 \renewcommand{\labelenumi}{(\alph{enumi})}

 \item the cardinality $\# p(H)^{-1}(x^*)=\deg_Y G$,

 \item for every $y\in p(H)^{-1}(x^*)$ the point $y$ is a smooth point of the
variety
 $W$ and the differential of $p$ in the point $y$
\[d_yp\, :\, T_{y,W}\longrightarrow T_{x,{\mathbb P}^{n-s}}\]
is an isomorphism of tangent spaces $T_{y,W}$ and $T_{x,{\mathbb P}^{n-s}}$
of the varieties $W$ and ${\mathbb P}^{n-s}(\overline{k})$ in the points $y$
and $x$
respectively.
\end{enumerate}
Let $\varepsilon>0$ be an infinitesimal relative to the field $K$.
Now if $z^*\in U(H)$ there is a point
$z\in U$ in ${\mathbb P}^{n-s-1}(\overline{K(\varepsilon)})$
which is infinitesimal close to $z^*$.
Hence, by \prf{1}  $\# p(H)^{-1}(z^*)\le\# p(H)^{-1}(z)$.
Therefore, $\delta(H)=\deg_YG$ and $U\subset U(H)$. The lemma is proved.


\bl{a3}
Let $W$ be as in the formulation of \lrf{a1}.
For every $z\in U(\widetilde{H})$ the equalities
\[\delta=\delta(\widetilde{H})=\# p(\widetilde{H})^{-1}(z)\]
hold. Therefore,
$\delta$ is an integer which depends only on $W$ and $x$.
\el
\bpr
The equality $\delta(\widetilde{H})=\# p(\widetilde{H})^{-1}(z)$
follows from
\lrf{a2}. Further, if $H\in {\mathcal H}_1$ and $z\in U_3(H)$
are arbitrary then we can set the coefficients of the forms
$H_j-\widetilde{H}_j$ to be infinitesimals for all $j$ and by \prf{1} the
point $z\in U_3(\widetilde{H})$ and $\# p(\widetilde{H})^{-1}(z)\ge \#
p(H)^{-1}(z)$.
Hence, $\delta=\delta(\widetilde{H})$. The lemma is proved.

\bl{a5}
Let $q\, :\, V_1\rightarrow V_2$ be a dominant regular morphism of
irreducible algebraic varieties $V_1$ and $V_2$ defined
over the field $k$. Let $\dim V_1=\dim V_2$. Let $z\in V_2$ and
\[\# q^{-1}(z)=[k(V_1):k(V_2)],\]
i.e. the number of elements of the inverse image of the point $z$ coincides
with the degree
of the extension of the fields of rational functions of $V_1$ and $V_2$.
Then there is
an open in the Zariski topology subset $U'\subset V_2$ such that $z\in U'$
and the morphism
\[q^{-1}(U')\rightarrow U'\]
induced by $q$ is finite.
\el
\noindent {\bf PROOF} \quad
Denote $[k(V_1):k(V_2)]=\alpha$.
Denote by $\widetilde{V}_i$, $i=1,2$, the
normalization of the algebraic variety $V_i$ in the field $k(V_1)$, see
\cite{lit7}, \cite{lit17}.
So we have the commutative diagram of morphisms of algebraic varieties
\[\begin{CD}
\widetilde{V}_1@>\widetilde{q}>>\widetilde{V}_2  \\
@V\pi_1VV                       @V\pi_2VV\\
V_1            @>q>>                  V_2
\end{CD}\]
where $\pi_1$ and $\pi_2$ are finite morphisms and
$\widetilde{q}$ is a birational isomorphism induced by $q$. We have
$\#\pi_2^{-1}(z)\le \alpha$
since $\pi_2$ is finite.
By the Zariski main theorem $\widetilde{q}$ is invertible in some
neighborhood in the Zariski topology of every point
$z'\in \pi_2^{-1}(z)$ if $\widetilde{q}^{-1}(z')\ne \emptyset$. Hence,
$\#\pi_2^{-1}(z)\ge\#\pi_1^{-1}(q^{-1}(z))$. But $\#q^{-1}(z)=\alpha$.
Therefore, $\#\pi_2^{-1}(z)=\#\pi_1^{-1}(q^{-1}(z))$ and
$\widetilde{q}$ is invertible in some neighborhood in the Zariski topology
$U''$ of the
finite set $\pi_2^{-1}(z)$. So we have the isomorphism of algebraic varieties
\[\widetilde{q}^{-1}(U'')\simeq U''\]
induced by $\widetilde{q}$. Set
$U'=V_2\setminus\pi_2(\widetilde{V}_2\setminus U'')$.
Then $z\in U'$ and the morphism
\[\pi_1^{-1}(q^{-1}(U'))=\widetilde{q}^{-1}(\pi_2^{-1}(U'))\rightarrow U'\]
is finite. Hence, the morphism $q^{-1}(U')\rightarrow U'$ is also finite.
The lemma is proved.

\bl{7} Let $W\subset {\mathbb P}^n(\overline{k})$ be an irreducible algebraic
variety of the dimension $\dim W=n-s-1$
and the linear forms $L_{s+1}$, $L_{s+2}, \ldots ,L_n
\in\overline{k}[X_1,\ldots ,X_n]$  satisfy
\rf{pr0}, \rf{pr} and \rf{cpr}. Then
 \begin{enumerate}
 \renewcommand{\labelenumi}{(\roman{enumi})}

 \item there exists a non--empty open in the Zariski topology subset $U$ of
${\mathbb P}^{n-s}(\overline{k})$ such that for every $x^*\in U$ the
cardinality
$\# p^{-1}(x^*)=\delta>0$, and $\delta$ is an integer  defined in \rf{fi}
which depends only on $W$ and $x$.

 \item if for some point $x^*\in {\mathbb P}^{n-s}(\overline{k})$ the
cardinality
$\# p^{-1}(x^*)=\delta$ then for every $y\in p^{-1}(x^*)$ the point
$y$ is a smooth point of the variety
 $W$ and the differential of $p$ in the point $y$
\[d_yp\, :\, T_{y,W}\longrightarrow T_{x,{\mathbb P}^{n-s}}\]
is the isomorphism of tangent spaces $T_{y,W}$ and $T_{x^*,{\mathbb
P}^{n-s}}$
of the varieties $W$ and ${\mathbb P}^{n-s}(\overline{k})$ in the points $y$
and $x^*$
respectively.

 \item if for some point $x^*\in {\mathbb P}^{n-s}(\overline{k})$ the
cardinality
$\# p^{-1}(x^*)<+\infty$ then \\
$\# p^{-1}(x^*)\le\delta$.

 \end{enumerate}
\el

 \noindent
 {\bf PROOF} \quad
The family $L_{s+1},\ldots , L_n$ belongs
to ${\mathcal H}_1$. Set in \lrf{a2} the family $H$ to be
$L_{s+1},\ldots , L_n$. We shall use
the notations $Y$, $p_1$, $p_2$, $p_3$, $G$, $R$, $U$
from the proof of \lrf{a2} and $U_4$ from \lrf{a4}.
Let us show that $\deg_Y G=\delta$. Set the coefficients of the forms
$\widetilde{H}_j-L_j$ to be infinitesimals relative
the field $k$ for all $j$.
So the map of the standard part
\[\hbox{st} \, :\, {\mathbb P}^{r}(\overline{K})\longrightarrow
{\mathbb P}^{r}(\overline{k})\]
is defined.
Thus, by \prf{1}
for every $x^*\in U\cap U(\widetilde{H})\cap U_4$
for every $y^*\in p(\widetilde{H})^{-1}(x^*)$
the element $y=\hbox{st}\, y^*\in p^{-1}(x^*)$ or $x=\hbox{st}\, y^*$.
The differential
of $p$ in the point $y\in p^{-1}(x^*)$ is an  isomorphism. If $y\in
p^{-1}(x^*)$
then by the implicit function theorem  there exists a unique
$y'\in p(\widetilde{H})^{-1}(x^*)$ such
that $\hbox{st}(y')=y$. Hence, in this case $y'=y^*$.

Let us show that there exists no $y^*$ such as above  for which
$x=\hbox{st}\, y^*$.
Indeed, suppose contrary, that  $x=\hbox{st}\, y^*$.
Denote $y^*=(y^*_1,\ldots ,y^*_n)\in {\mathbb A}^n(\overline{k})$ and
$x^*=(1:\lambda_{s+1}:\ldots :\lambda_n)$.
Set $|y^*|=(\sum_{1\le i\le n}|y^*_i|^2)^{1/2}$.
Then
\[x\ne \hbox{st}(y^*/|y^*|)\in \mathop{\rm con}\nolimits(x,W)\cap
{\mathcal Z}(L_{s+2}-\lambda_{s+1}L_{s+1}, \ldots ,L_n-\lambda_nL_{s+1})\]
since if $F\in\overline{k}[X_1,\ldots ,X_n]$, $F(y^*)=0$
and $F_r$ is the form of the least degree of $F$
then $F_r(\hbox{st}(y^*/|y^*|))=0$. A contradiction is obtained which proves
our assertion.

Thus,
\[\delta=\# p(\widetilde{H})^{-1}(x^*)= \# p^{-1}(x^*)=\deg_Y G\]
and, therefore, $\deg G=\delta$ and (i) is proved.

Now (iii) follows from (i) and the definition of $\delta$.

To prove (ii) note that by \lrf{a5} ( with $k$ replaced by $\overline{k}$)
for every point $x^*$ with
$\# p^{-1}(x^*)=\delta=[\overline{k}(W):\overline{k}({\mathbb P}^{n-s-1})]$
(here the inclusion $\overline{k}({\mathbb P}^{n-s-1})\subset\overline{k}(W)$
of fields rational functions is induced by $p$) there exists
an open set $U'$ in the Zariski topology such that $x^*\in U'$ and
the morphism $p^{-1}(U')\rightarrow U'$ induced by $p$ is finite.
Now there exists a linear form $Y$ such that the corresponding
$p_1$ is birational, $\# p_1(p^{-1}(x^*))=\delta$. We have for this form
$(\hbox{lc}_YG)(x^*)\ne 0$ since the morphism $p^{-1}(U')\rightarrow U'$
is finite and $x^*\in U'$.  Hence $p_3^{-1}(x^*)<+\infty$. Therefore,
$p_3^{-1}(x^*)=p_1(p^{-1}(x^*))=\delta$. Hence, $R(x^*)\ne 0$.

Further, if $R(x^*)\ne 0$, $\# p^{-1}(x^*)=\delta$
and $y\in p^{-1}(x^*)$ then
the point $p_1(y)$ is smooth, the local ring ${\mathcal O}_{p_1(y),p_1(W)}$
of the variety $p_1(W)$ in the point $p_1(y)$ is
integrally closed. Therefore, by the Zariski main theorem
the local rings
\[{\mathcal O}_{y,W}\simeq{\mathcal O}_{p_1(y),p_1(W)}.\]
Thus, $p_1$ is an isomorphism in the neighbourhood of each point
$y\in p^{-1}(x^*)$. From here and (a) and (b) proved above assertion
(ii) follows immediately. The Lemma is proved.

\bco{0}
Under the conditions of \lrf{7} the multiplicity \\
$\mu(x, V_{s+1})=\deg V_{s+1}-\delta$.
\eco
\noindent {\bf PROOF} \quad
This follows immediately from the definition of the multiplicity \rf{mu}
given in the Introduction and lemmas proved in this Section.

\br{3}
As it follows from \crf{1} from \lrf{9}, see
below, \lrf{7} and \crf{0} are also valid when
the condition \rf{pr} is not satisfied. In this case $\delta=0$
and $W=\mathop{\rm con}\nolimits(x,W)$.
\er

\bl{9}
Let $W$ be an irreducible an irreducible algebraic variety
of the dimension $n-s-1$ and linear forms
$L_0,L^{(i)}_{s+2},$
$\ldots ,L^{(i)}_n\in$ $\overline{k}[X_0,\ldots ,X_n]$, $i=0,1$
be such that
\begin{eqnarray*}
&&L^{(i)}_{s+2},\ldots ,L^{(i)}_n\in \overline{k}[X_1,\ldots ,X_n], \\
&&W\cap {\mathcal Z}(L_0,L^{(0)}_{s+2},\,\ldots,\, L^{(0)}_n)=\emptyset, \\
&&\mathop{\rm con}\nolimits(x,W)\cap
{\mathcal Z}(L_0,L^{(0)}_{s+2},\,\ldots,\,L^{(0)}_n)=\emptyset
\quad\hbox{if}\quad x\in W, \\
&&W\cap {\mathcal Z}(L^{(1)}_{s+2},\,\ldots,\, L^{(1)}_n)<+\infty
\end{eqnarray*}
in  ${\mathbb P}^n(\overline{k})$. Further, let all the points of
$W\cap {\mathcal Z}(L^{(0)}_{s+2},\,\ldots,\, L^{(0)}_n)\setminus\{x\}$ be
smooth
and the differentials of the projection
\[p^{(0)}\, :\, W\longrightarrow {\mathbb P}^{n-s-1}(\overline{k}),
\quad (X_0:\ldots :X_n)\mapsto (L_0:L^{(0)}_{s+2}:\ldots :L^{(0)}_n)\]
are isomorphisms in all the points from
$W\cap {\mathcal Z}(L^{(0)}_{s+2},\,\ldots,\, L^{(0)}_n)\setminus\{x\}$.
Then
\[\# W\cap {\mathcal Z}(L^{(0)}_{s+2},\,\ldots,\, L^{(0)}_n)\ge
\# W\cap {\mathcal Z}(L^{(1)}_{s+2},\,\ldots,\, L^{(1)}_n).\]
\el

\noindent
 {\bf PROOF} \quad
Suppose contrary, that
\[\# W\cap {\mathcal Z}(L^{(0)}_{s+2},\,\ldots,\, L^{(0)}_n)<
\# W\cap {\mathcal Z}(L^{(1)}_{s+2},\,\ldots,\, L^{(1)}_n).\]

Let $\varepsilon>0$ be an infinitesimal relative to the field $k$.
So the map of the standard part
\[\hbox{st}\, :\, {\mathbb P}^{n}(\overline{k(\varepsilon)})\longrightarrow
{\mathbb P}^{n}(\overline{k})\]
is defined.

We have, c.f. \cite{lit3},
$+\infty >\# W\cap\{L^{(0)}_j+
\varepsilon L^{(1)}_j=0,\; s+2\le j\le n\}\ge
\# W\cap {\mathcal Z}(L^{(1)}_{s+2},\,\ldots,\, L^{(1)}_n)$ (here one can use
\prf{1} if only for a moment one considers $1/\varepsilon$
as an infinitesimal).
Let $x^*\in W\cap\{L^{(0)}_j+
\varepsilon L^{(1)}_j=0,\; s+2\le j\le n\}$.
 Then $\hbox{st}(x^*)\in
W\cap {\mathcal Z}(L^{(0)}_{s+2},\,\ldots,\, L^{(0)}_n)$ by \prf{1}.
The differentials of the projection $p^{(0)}$
are isomorphisms in all the point from
$W\cap {\mathcal Z}(L^{(0)}_{s+2},\,\ldots,\, L^{(0)}_n)\setminus\{x\}$.
Thus, by the
implicit function theorem (applied to formal power series) for every $x''\in
W\cap {\mathcal Z}(L^{(0)}_{s+2},\,\ldots,\, L^{(0)}_n)\setminus\{x\}$ there
exists
a unique $x^*\in W\cap\{L^{(0)}_j+
\varepsilon L^{(1)}_j=0,\; s+2\le j\le n\}$ such that $\hbox{st}(x^*)=x''$.
Hence, $x\in W$ and there exists at least
one $x'\in W\cap\{L^{(0)}_j+
\varepsilon L^{(1)}_j=0,\; s+2\le j\le n\}$ such that $\hbox{st}(x')=x$.

Denote $x'=(x'_1,\ldots ,x'_n)\in {\mathbb A}^n$.
Set $|x'|=(\sum_{1\le i\le n}|x'_i|^2)^{1/2}$.
We have $\hbox{st}(x')=x$ and, therefore,
\[x\ne \hbox{st}(x'/|x'|)\in \mathop{\rm con}\nolimits(x,W)\cap
{\mathcal Z}(L^{(0)}_{s+2},\,\ldots,\, L^{(0)}_n)\]
since if $F\in\overline{k}[X_1,\ldots ,X_n]$, $F(x')=0$
and $F_r$ is the form of the least degree of $F$ then
$F_r(\hbox{st}(x'/|x'|))=0$. A contradiction is obtained. The lemma is
proved.

\bco{1}
Let $W$ and $L^{(i)}_{s+2},\ldots ,L^{(i)}_n$, $i=1,2$,
be as in the formulation of \lrf{9}. Let
\[ W\cap {\mathcal Z}(L^{(0)}_{s+2},\,\ldots,\, L^{(0)}_n)=\{x\}.\]
 Then
\[ W\cap {\mathcal Z}(L^{(1)}_{s+2},\,\ldots,\, L^{(1)}_n)=\{x\}.\]
More than that, in this case $W= \mathop{\rm con}\nolimits(x,W)$.
\eco

\noindent
 {\bf PROOF} \quad
It is necessary to prove only the last statement. Consider the projection
$\pi : {\mathbb P}^n(\overline{k})\setminus\{x\}\rightarrow {\mathbb
P}^{n-1}(\overline{k})$
defined in the proof of \lrf{a1}.

Let us show that the closure $W_1$ in the Zariski topology
of $\pi (W\setminus\{x\})$  has the dimension $n-s-2$. Indeed, otherwise this
dimension is equal to $n-s-1$. Hence there exist linear forms
$H_{s+1},H_{s+2}, \ldots ,H_n$ in
$\overline{k}[X_1,\ldots ,X_n]$ such that
\[ W_1\cap {\mathcal Z}(H_{s+1},\ldots ,H_{n})=\emptyset.\]
Therefore, the morphism of $W\setminus\{x\}\rightarrow {\mathbb
P}^{n-s-1}(\overline{k})$,
$(X_0:\ldots :X_n)\mapsto (H_{s+1}:\ldots :H_n)$ is dominant.
Hence there exists $z_1,\ldots ,z_n\in \overline{k}$ such that
\[ W\cap {\mathcal Z}(H_{s+2}-z_{s+2}H_{s+1},\ldots ,H_{n}-z_{n}H_{s+1})
\setminus\{x\}\]
is a non--empty finite set. Now set $L^{(1)}_j=H_{j}-z_{j}H_{s+1}$, $s+2\le
j\le n$.
Hence
$\# W\cap {\mathcal Z}(L^{(1)}_{s+2},\ldots ,L^{(1)}_{n})
\setminus\{x\}\ge 1$
which is a contradiction. Our assertion is proved.

Now the irreducible algebraic variety $\pi^{-1}(W_1)\supset W\setminus\{x\}$
and $\dim \pi^{-1}(W_1)=\dim W$. Hence
$W=\mathop{\rm con}\nolimits(x,W)=\pi^{-1}(W_1)\cup\{x\}$.
The corollary is proved.





\section{Conclusion of the description of the algorithm for computing
the multiplicity}\label{s4}

Our aim now is to construct a family of linear forms $M_0,M_{s+2},
M_{s+3},\ldots ,M_n$
such that $M_0=L_0$, the forms $M_{s+2}, M_{s+3},\ldots ,M_n\in
k[X_1,\ldots ,X_n]$
have the coefficients from $\mathbb {Z}$ of the length $O(n\log
\, d)$,
\[V'\cap {\mathcal Z}(M_0,M_{s+2}, M_{s+3},\ldots ,M_n)=\emptyset,\]
\[\mathop{\rm con}\nolimits(x,V')\cap {\mathcal Z}(M_0,M_{s+2},
M_{s+3},\ldots
,M_n)=\emptyset\]
in ${\mathbb P}^{n}(\overline{k})$, all the points from
$V'\cap {\mathcal Z}(M_{s+2}, M_{s+3},\ldots ,M_n)\setminus\{x\}$ are smooth
points of the variety $V'$, and the intersection of tangent spaces
\[T_{x_1,V'}\cap {\mathcal Z}(M_{s+2}, M_{s+3},\ldots ,M_n)=\{x_1\}\]
 for every
point $x_1\in V'\cap {\mathcal Z}(M_{s+2}, M_{s+3},\ldots
,M_n)\setminus\{x\}$.

Recall that in \srf{2} the points $x_u$, $1\le u\le N$
are constructed, herewith $x_1=x$.
Let $x_u=(x_{u,0}:\ldots :x_{u,n})$ where all $x_{u,i}$ are from a finite
extension of $k$. Construct
a real structure for the field $K=k(x_{u,0},\ldots ,x_{u,n})$,
see \cite{lit15}, \cite{lit17}, which induces a real structure on
$\overline{k}$.

 Let the  infinitesimals $\varepsilon_0,\varepsilon_1,\varepsilon_2$ and the
field
$K_2=k(\varepsilon_0,\varepsilon_1,\varepsilon_2)$ be as \srf{2}.

Let $Y_0,\ldots,Y_n$, $Z_0,\ldots,Z_n$, $T_0,\ldots,T_n$, $Z$, $T$ be new
 variables. For every $2\le u\le N$
 consider the following system of equations and inequalities
 with coefficients in $K_2$
 \bequ{7}
\left\{\begin{array}{ll}
 h_i=0, &  1\le i \le s+1, \\
 h_i(Y_0,\dots,Y_n)=0, & 1\le i\le s+1, \\
 h_i(Z_0,\dots,Z_n)=0, & 1\le i\le s, \\
 h_i(T_0,\dots,T_n)=0, & 1\le i\le s, \\
 h_{s+1}(Z_0,\dots,Z_n)Z-1=0, \\
 h_{s+1}(T_0,\dots,T_n)T-1=0, \\
 \sum_{0\le i\le n}|X_i-Z_i|^2\le \varepsilon_2, \\
 \sum_{0\le i\le n}|Y_i-T_i|^2\le \varepsilon_2, \\
 L_j(X_0-Y_0,\ldots,X_n-Y_n)=0, & s+1\le j\le n, \\
 L_{s+1}(X_0-x_{u,0},\ldots,X_n-x_{u,n})=0,\\
 \sum_{0\le i\le n}|X_i-x_{u,i}|^2\le \varepsilon_0, &  \\
 \sum_{0\le i\le n}|Y_i-x_{u,i}|^2\le \varepsilon_0, &  \\
 \sum_{0\le i\le n}|Y_i-X_i|^2\ge \varepsilon_1, &
  \end{array}
\right. \eequ

We have the following analog of \lrf{2}.

\bl{8}
Let $V'$ and the projection
$p_{x}\, :\, V'\setminus\{x\}\longrightarrow {\mathbb
P}^{n-s-1}(\overline{k})$ be as in \srf{2}.
If for every $2\le u\le N$
there do not exist solutions of system \rf{7}
in ${\mathbb A}^{4n+2}(\overline{K_2})$
then all the points $\{x_u\}_{2\le u \le N}$ of the variety $V'$ are smooth
and the differentials of the projection $p_x$
in points $\{x_u\}_{2\le u \le N}$ are isomorphisms.
\el

\noindent
 {\bf PROOF} \quad
Let $\varepsilon_3>0$  be an infinitesimal
relative to the field $k(\varepsilon_0)$ such that
$\varepsilon_1$  is an infinitesimal relative to the
field $k(\varepsilon_0,\varepsilon_3)$. Suppose that at least one point
$x_{u_0}$ is not smooth or it is smooth but the
differential of the projection $p$ in the point $x_{u_0}$ is not an
isomorphism.
 Denote $p_{x}(x_{u_0})=w\in{\mathbb P}^{n-s-1}(\overline{k})$.

Suppose that there exists only one component $W$ of $V'$
such that $x_{u_0}\in W$. Denote by $A(W)$ the set of indices $u$
such that $x_{u}\in W$, $1\le u\le N$,
and set $p=p_{x}|_{W\setminus\{x\}}$, $N(W)=\# A(W)$. Apply \lrf{7}.
Then by this lemma $N(W)-1<\delta$ and there exists
$w^*\in {\mathbb P}^{n-s-1}(\overline{k(\varepsilon_3)})$ such that
$\hbox{st}_{\varepsilon_3}(w^*)=w$ and $\# p^{-1}(w^*)=\delta$. By \prf{1}
there exist two different elments $x',y'\in \# p^{-1}(w^*)$ such that
$\hbox{st}_{\varepsilon_3}(x')=\hbox{st}_{\varepsilon_3}(y')=x_{u_1}$
for some $u_1\in A(W)$.

Recall that $L={\mathcal Z}(L_{s+2}, L_{s+3},\ldots ,L_n)$.
 Denote $\hbox{st}=\hbox{st}_{\varepsilon_0}
\circ\hbox{st}_{\varepsilon_3}$. Let us show that $u_1\ne 1$.
Indeed, otherwise
$x\ne \hbox{st}(x'/|x'|)\in \mathop{\rm con}\nolimits(x,W)\subset
\mathop{\rm con}\nolimits(x,V')$ since if $F\in\overline{k}[X_1,\ldots
,X_n]$, $F(x')=0$
and $F_r$ is the form of the least degree of $F$ then
$F_r(\hbox{st}(x'/|x'|))=0$. Further
\[(L_j-(L_j/L_{s+1})(w^*)L_{s+1})(x'/|x'|)=0\]
and  $(L_j/L_{s+1})(w^*)$ is an infinitesimal for every $s+2\le j\le n$.
Therefore, we have $L_j(\hbox{st}(x'/|x'|))=0$ for every $s+2\le j\le n$.
Hence $x\ne \hbox{st}(x'/|x'|)\in \mathop{\rm con}\nolimits(x,V')\cap L$.
This contradiction proves our assertion.

Hence $u\ge 2$. From the fact that $x',y'\in W\subset V'$
we get the existence of
$z',t'\in {\mathbb P}^{n}(\overline{k(\varepsilon_3,\varepsilon_2)})$
such that $h_i(z')=h_i(t')=0$ for $1\le i\le s$, $h_{s+1}(z')\ne 0$,
$h_{s+1}(t')\ne 0$ and
$\hbox{st}_{\varepsilon_2}(z')=x'$, $\hbox{st}_{\varepsilon_2}(t')=y'$.
Thus, system \rf{7} with $u=u_1$ has a solution in
${\mathbb P}^{n}(\overline{k(\varepsilon_3,\varepsilon_2)})$. Now the
the isomorphism of the fields with real structures
$\overline{k(\varepsilon_3,\varepsilon_2)}\simeq
\overline{k(\varepsilon_0^a,\varepsilon_2)}$ induced by
$\varepsilon_3\mapsto\varepsilon_0^a$ for sufficiently great $0<a\in {\mathbb
Z}$
gives a solution of system \rf{7} with $u=u_1$ in
${\mathbb P}^{n}(\overline{k(\varepsilon_0,\varepsilon_2)})$.

If there exist two different components $W_1$ and $W_2$ of $W$ then
there exists a point $w^*\in {\mathbb
P}^{n-s-1}(\overline{k(\varepsilon_3)})$
such that
$w^*\not\in p(W_1\cap W_2)$ and $\hbox{st}_{\varepsilon_3}(w^*)=w$.
Then by \prf{1}
there exist two different $x',y'\in \# p^{-1}(w^*)$ such that $x'\in W_1$,
$y'\in W_2$,
$\hbox{st}_{\varepsilon_3}(x')=\hbox{st}_{\varepsilon_3}(y')=x_{u_0}$.
Further the proof
is similar to the considered case of one component $W$. The lemma is proved.

Return to the description of the algorithm.
Construct a solution of system \rf{7} for some $u$
or ascertain that for every $2\le u\le N$
there exists no solutions of system \rf{7} in ${\mathbb
A}^{4n+2}(\overline{K_2})$.
In the last case by \lrf{8} all the points $\{x_u\}_{2\le u \le N}$ of
the variety $V'$ are smooth and the differentials of the projection $p_x$
in the points $\{x_u\}_{2\le u \le N}$ are isomorphisms.

Suppose that there exists a solution
\[(x'_0,\ldots ,x'_n,y'_0,\ldots ,y'_n,z'_0,\ldots ,z'_n,t'_0,\ldots
,t'_n,z,t)
\in {\mathbb A}^{4n+2}(\overline{K_2})\]
of some system \rf{7} with $u=u_0$. Denote $x'=(x'_0:\ldots :x'_n)$
and $y'=(y'_0:\ldots :y'_n)$. So $x',y'\in {\mathbb P}^n(\overline{K_2})$.
Compute $x^*=\hbox{st}_{\varepsilon_2}(x')$ and
$y^*=\hbox{st}_{\varepsilon_2}(y')$.
Then $x^*,y^*\in V'$ since the polynomials $h_1,\ldots , h_s$
are vanishing in these points and the
polynomial $h_{s+1}$ is not vanishing
in the points $(z'_0,\ldots , z'_n)$ and
$(t'_0,\ldots , t'_n)$ which are
infinitesimal close to $x^*$ and $y^*$ respectively. Set
\[L'_i=L_i-(L_i/L_{s+1})(x^*)L_{s+1},\,
s+2\le i\le n.\]
Compute all the points from the set $V'\cap
{\mathcal Z}(L'_{s+2},\,\ldots,\, L'_n)$ in
${\mathbb P}^n(\overline{K_2})$.
Denote $N'=\# V'\cap {\mathcal Z}(L'_{s+2},\,\ldots,\, L'_n)$. By \prf{1}
for every $x''\in V'\cap {\mathcal Z}(L'_{s+2},\,\ldots,\, L'_n)$ there
exists
$1\le u\le N$ such that
$(\hbox{st}_{\varepsilon_0}\circ\hbox{st}_{\varepsilon_1})\,(x'')=x_u$.
So $N'\ge N$. Further,
$x^*,y^*\in V'\cap {\mathcal Z}(L'_{s+2},\,\ldots,\, L'_n)$, $x^*\ne y^*$ and
$(\hbox{st}_{\varepsilon_0}\circ\hbox{st}_{\varepsilon_1})\,(x^*)=
(\hbox{st}_{\varepsilon_0}\circ\hbox{st}_{\varepsilon_1})\,(y^*)$.
Therefore, $N'\ge N+1>N$.

Apply the analog of the  second auxiliary algorithm from \cite{lit17}
described in \srf{2} to the linear forms
$L'_{s+2},\ldots ,L'_n$ and construct linear forms $M_{s+2},$ $\ldots ,M_n$
in $X_1,\ldots ,X_n$ with coefficients from $\mathbb {Z}$ of
the length $O(n\log \, d)$ such that
\bea
&&\# V'\cap {\mathcal Z}(M_{s+2},\,\ldots,\, M_n)\ge N'>N,  \\
&&V'\cap {\mathcal Z}(L_0,M_{s+2},\,\ldots\, ,M_n)=\emptyset
\eea
in ${\mathbb P}^n(\overline{k})$.
Set also $M_0=L_0$

After that, return recursively to the beginning of the algorithm described
replacing the forms $L_0,L_{s+2},\ldots ,L_n$ by
$M_0,M_{s+2},$ $\ldots,$ $M_n$. Since $N'>N$ there are at most $d^{s+1}$
such returns in the algorithm.

Thus, effecting this recursive construction till the end
we can suppose without loss
of generality by \lrf{8} that  all the points $x_u$, $2\le u\le N$ (if they
exist) are
smooth of the variety $V'$ and  the differentials of the projection
$p_x$, see \lrf{8}, in the points $x_u$, $2\le u \le N$ are isomorphisms.

The condition that  the differentials of the projection
\[\widetilde{p}\, :\, W\longrightarrow {\mathbb P}^{n-s-1}(\overline{k}),
\; (X_0:\ldots :X_n)\mapsto (L_0:L_{s+2}:\ldots :L_n)\]
are isomorphisms in all the point from
$V'\cap {\mathcal Z}(L_{s+2},\,\ldots,\, L_n)\setminus\{x\}$
follows from the condition that
the differentials of the projection
\[p_{x}\, :\, V'\setminus\{x\}\longrightarrow {\mathbb
P}^{n-s-1}(\overline{k}),
\; (X_0:\ldots :X_n)\mapsto (L_{s+1}:L_{s+2}:\ldots :L_n).\]
are isomorphisms in all the point from
$W\cap {\mathcal Z}(L_{s+2},\,\ldots,\, L_n)\setminus\{x\}$.
The both conditions are equivalent to the fact that the intersection of
tangent spaces
$T_{x_u,V'}\cap {\mathcal Z}(L_{s+2}, L_{s+3},\ldots ,L_n)=\{x_u\}$ for every
point $x_u\in V'\cap {\mathcal Z}(L_{s+2}, L_{s+3},\ldots
,L_n)\setminus\{x\}$.
That is we have the required linear forms $M_j=L_j$, $j=0,s+2,s+3,\ldots ,n$.


Now construct applying \lrf{5} the subset of indices
$A\subset \{2,\ldots ,N\}$ such that
\bequ{8}
\{x_u\, :\, u\in A\}=V_{s+1}\cap {\mathcal Z}(L_{s+2},\,\ldots,\, L_n)
\eequ
in ${\mathbb P}^n(\overline{k})$.



\bl{10}
Let $\mu(x,V_{s+1})$  be the multiplicity of the point $x$ of the variety
$V_{s+1}$. Then
\bequ{9}
\mu(x,V_{s+1})=\deg V_{s+1}-\# A.
\eequ
\el

\noindent
 {\bf PROOF} \quad
Let $W$ be an arbitrary irreducible component of $V'$ and
$A(W)\subset \{1,\ldots ,N\}$ be the subset of indices
such that
\[\{x_u\, :\, u\in A(W)\}=W\cap {\mathcal Z}(L_{s+2},\,\ldots,\, L_n)\]
in ${\mathbb P}^n(\overline{k})$.

Consider the set of families $H$ of $n-s-1$ linear forms $H_{s+2},\ldots
,H_n$ in
$X_1,\ldots ,X_n$ with coefficients from $\overline{k}$.
So by the definition
of the multiplicity there exists such a family $H=\{H_j\}_{s+2\le j\le n}$
for which $\# (W\cap {\mathcal Z}(H_{s+2},\,\ldots,\,
H_n)\setminus\{x\})<+\infty$ and
$\mu(x,W)=\deg W-\# (W\cap {\mathcal Z}(H_{s+2},\,\ldots,\,
H_n)\setminus\{x\})$.
The conditions of \lrf{9}
are satisfied for $L^{(0)}_j=L_j$, $j=0,s+2,\ldots ,n$ and
$L^{(1)}_j=H_j$, $j=s+2,\ldots ,n$. Now applying
\lrf{9} we get that
\[\# (W\cap {\mathcal Z}(L_{s+2},\,\ldots,\, L_n)\setminus\{x\})\ge
\# (W\cap {\mathcal Z}(H_{s+2},\,\ldots,\, H_n)\setminus\{x\}).\]
Hence by the definition of the multiplicity
\begin{eqnarray*}
&&\# A(W)=\# (W\cap {\mathcal Z}(L_{s+2},\,\ldots, \,L_n)\setminus\{x\})=  \\
&&\# (W\cap {\mathcal Z}(H_{s+2},\,\ldots,\, H_n)\setminus\{x\})=
\deg W-\mu(x,W).
\end{eqnarray*}
Hence $\sum_{W\subset V_{s+1}}\mu (x,W)=\deg V_{s+1} -\#A$. But
$\mu (x,V_{s+1})\ge \sum_{W\subset V_{s+1}}\mu (x,W)$ as a simple
consequence of the definition
of the multiplicity. Hence $\mu (x,V_{s+1})\ge\deg V_{s+1} -\#A$. Finally we
have
$-1+ \deg V_{s+1}-\# V_{s+1}\cap {\mathcal Z}(L_{s+2},\,\ldots,\, L_n)=\deg
V_{s+1} -\#A$ and
therefore $\mu (x,V_{s+1})=\deg V_{s+1} -\#A$. The lemma is proved.


Thus, by \lrf{10} we can compute the multiplicity $\mu(x,V_{s+1})$.
The algorithm for the computation of the multiplicity of a point is
completely described. \trf{3} is proved.

 \newpage

 \begin{thebibliography}{88}

 \bibitem{lit1} {\bf Bochnak J., Coste M., Roy
 M.--F.:} {\it ``G\'eom\'etrie alg\'ebrique r\'eelle''},
 Springer--Verlag, Berlin, Heidelberg, New York, 1987.


  \bibitem{lit15} {\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{lit17} {\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{lit3} {\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 (Russian) [English
 transl.: J. Sov. Math. 34, (4), (1986) p.\ 1838--1882].

 \bibitem{lit4} {\bf Chistov A. L.:} {\it ``Polynomial complexity of the
 Newton--Puiseux algorithm''}, (Lecture Notes in Computer Science, Vol.
 233), Springer, New York, Berlin, Heidelberg, 1986, p.\ 247--255.

 \bibitem{lit5} {\bf Chistov A. L.:} {\it ``Polynomial complexity
 algorithms for computational problems in the theory of algebraic
 curves''}, Zap. Nauchn. Semin. Leningrad. Otdel. Mat. Inst. Steklov
 (LOMI) 176 (1989) p.\ 127--150 (Russian).

 \bibitem{lit25} {\bf Chistov A. L., Karpinski M.:} {\it ``Complexity
 of Deciding Solvability of Polynomial Equations over p-adics''}, Research
 Report No. 85183-CS, Institut f\"ur Informatik der Universit\"at Bonn,
 May 1997, 18 p.


 \bibitem{lit14} {\bf Giusti M., Heintz J.:}
 {\it ``La d\'etermination des
 points isol\'es et de la dimension d'une vari\'et\'e alg\'ebrique peut
 se faire en temps polynomial''},  Proc. Int. Meeting on Commutative Algebra,
 Cortona (1993).


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

 \bibitem{lit16} {\bf Igusa J.:} Mem. Coll. Sci. Univ. Kyoto 27 (1951),
189--201.

 \bibitem{lit50} {\bf Kroneker L.:} {\it ``Grundz\"uge einer
arithmetischen theorie der algebraischen grossen''}, J. Reine und
angew. Math., 92 (1882) S.\ 1--122.

 \bibitem{lit29} {\bf Lazard D.:} {\it ``Alg\`ebre lin\'eaire
sur $k[x_1, \ldots, x_n]$ et \'elimination''},
Bul. S.M.F. 105 (1977) p.\ 165--190.

 \bibitem{lit8} {\bf Lazard D.:} {\it ``R\'esolution des syst\`emes
 d'\'equations alg\'ebrique''}, Theoretical Computer Science 15 (1981),
 p.\ 77--110.

 \bibitem{lit13} {\bf Mumford D.:}{\it  ``Algebraic geometry I. Complex
 projective varieties''}, Springer--Verlag, Berlin, Heidelberg, New York,
1976.

 \bibitem{lit9} {\bf Milnor J.:} {\it ``On Betti numbers of real
 varieties''}, Proceedings of the American Math. Soc. 15 (2) (1964),
 p.\ 275--280.

 \bibitem{lit10} {\bf Renegar J.:} {\it ``A faster PSPACE algorithm for
 deciding the existential theory of reals''}, Proc. 29th Annual Symp. on
 Foundations of Computer Sci., October 24--26, 1988, p.\ 291--295.

 \bibitem{lit27} {\bf Samuel P.:} {\it ``M\'etodes d'algebre abstracte
 en g\'eom\'etrie alg\'ebrique''}, B. 1967.

 \end{thebibliography}

\end{document}



--=====================_944530748==_--


