% 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)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 $j0$ 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_{mN$ 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 $0N$. 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==_--