   %
   %      A generic worst-case bound on the Condition Number
   %      of an Homotopy path
   %
   %      by Gregorio Malajovich
   %         gregorio@lyric.labma.ufrj.br
   %
   %      Preprint.
   %      Rio de Janeiro, Nov 29, 1995.
   %
   %      This is an AMS-Latex file.
   %      AMS-Latex is a kind of upgrade of Latex, by the AMS.
   %      Its primary distribution site is e-math.ams.org
   %      It can be obtained by anonymous ftp.
   %
   % -----------------------------------------------------------------


   \documentstyle[12pt]{amsart}

   \newcommand{\aff}{^{\text {\rm aff}}}
   \newcommand{\proj}{^{\text {\rm proj}}}
   \newcommand{\pseu}{^{\text {\rm pseu}}}
   \newcommand{\rtrans}{^{\text{\rm t}}}
   \newcommand{\ctrans}{^{\text{\rm *}}}
%   \newcommand{\dproj}{d_{\text{\rm proj}}}
   \newcommand{\dcp}{d_{\Bbb P}}
   \newcommand{\drp}{d_{\Bbb {RP}}}
   \newcommand{\exact}{_{\text{\rm exact}}}
   \newcommand{\appr}{_{\text{\rm appr}}}
   \newcommand{\opt}{_{\text{\rm opt}}}
   \newcommand{\diag}{{\text{\rm diag}}}
   \newcommand{\discr}{{\text{\rm discr}}}
   \newcommand{\rank}{{\text{\rm rank}}}
   \newcommand{\sgn}{{\text{\rm sgn}}}
   \newcommand{\arc}{{\text{\rm arc}}}
   \newcommand{\fl}{\text{\rm fl}}
   \newcommand{\tensor}{\otimes}
   \newcommand{\drond}{\partial}
   \newcommand{\Hd}{{\cal H}_{\bold{d}}}
   \newcommand{\Pd}{{\cal P}_{\bold{d}}}
   \newcommand{\round}{\hbox{Round}}
   \renewcommand{\Re}{\text{\rm Re}}
   \renewcommand{\Im}{\text{\rm Im}}
   \newcommand{\imag}{\hbox{im}}
   \newcommand{\COMP}{\hbox{COMP}}
   \newcommand{\PR}[2]{\left[\begin{array}{c}{#1}\\{#2}\ctrans\end{array}\right]}
   \newcommand{\PDf}[2]{\left[\begin{array}{c}Df(#1)\\{#2}\ctrans\end{array}\right]}
   \newcommand{\PV}[1]{\left[\begin{array}{c}{#1}\\0\end{array}\right]}
   \newcommand{\GDf}[2]{{Df({#1})_{|#2}}}
   \newcommand{\Df}[2]{\GDf{#1}{V({#2})}}
   \newcommand{\DfI}[2]{\GDf{#1}{V({#2})}^{-1}}
   \newcommand{\binomial}[2]{\left(\begin{array}{c}{#1}\\{#2}\end{array}\right)}
   \newcommand{\macheps}{{\epsilon _m}}
   \newcommand{\knorm}[1]{{\left \| {#1} \right \|_{\text{k}}}}
   \newcommand{\infnorm}[1]{{\left \| {#1} \right \|_{\infty}}}
   \newcommand{\fnorm}[1]{{\left \| {#1}\right  \|_{\text{\rm f}}}}
   \newcommand{\kinner}[2]{{\left < {#1} , {#2} \right  >_{\text{k}}}}
   \newcommand{\inner}[2]{{\left < {#1} , {#2} \right  >}}
   \newcommand{\norm}[1] {{\left \| {#1} \right \|_2}}
   \newcommand{\abs}[1] {{\left | {#1} \right |}}
   \newcommand{\onenorm}[1]{{\left \| {#1} \right \|_1}}
   \newcommand{\bignorm}[1]{{\left \| {#1} \right \|_2}}
   \newcommand{\supnorm}[1]{{\left \| {#1} \right \|_{\infty}}}
   \newcommand{\maxnorm}[1]{{\left \| {#1} \right \|_{\text{\rm max}}}}
   \newcommand{\maxtwonorm}[1]{{\left \|{#1}\right \|_{\text{\rm max,2}}}}
   \newcommand{\height}[1]{{\bold{H}\left({#1}\right)}}
   \newcommand{\bheight}[1]{{\bold{B}\left({#1}\right)}}
   \newcommand{\cheight}[1]{{\bold{C}\left({#1}\right)}}
   \newcommand{\fmu}{{\mu_{\text{\rm f}}}}

   \newcommand{\path}[2]{{#1}^{(#2)} }
   \newcommand{\fpath}[1]{\path{f}{#1}}
   \newcommand{\gpath}[1]{\path{g}{#1}}
   \newcommand{\fpair}{(\fpath{0},\fpath{1})}
   \newcommand{\gpair}{(\gpath{0},\gpath{1})}




   \newcommand{\rem}[1]{{\par \tt #1}}
   \newcommand{\ignore}[1]{{}}


   \newcommand{\noteind}[2]{\@writefile{not}{\string{ {#1} & \text{#2} & \text{Page \pageref}}}}


   \renewcommand{\paragraph}[1]{\medskip \par \noindent {\bf {#1} \/} }

   \newcounter{linenumber}

   \newenvironment{algorithm}
         { \medskip \centerline { {\bf Algorithm \ }}
           \begin {list}{\arabic{linenumber}}{\usecounter{linenumber}}
         }
         {  \end{list}  }

   \newtheorem {main}        {Main Theorem}
   \newtheorem {mainmain}    {Main Theorem}
   \newtheorem {theorem}     {Theorem}
   \newtheorem {corollary}   {Corollary}
   \newtheorem {proposition} {Proposition}
   \newtheorem {lemma}       {Lemma}
   \newtheorem {claim}       {Claim}
   \newtheorem {remark}      {Remark}

   \theoremstyle {definition}

   \newtheorem {definition}  {Definition}
   \newtheorem {problem}     {Problem}

   \theoremstyle {remark}
   \newtheorem   {note}        {Note}

   \renewcommand{\themainmain}{}

   \newcommand{\glossaryentry}[2]{#1 & #2 \cr}

   \title      [A generic worst-case bound ...]
               {A generic worst-case bound\\
                on the condition number of a homotopy path}
   \author     {Gregorio Malajovich}
   \date       {November 29, 1995}
   \thanks     {Sponsored by CNPq (Brasil).}
   \thanks     {Typeset using \AmS -\LaTeX}
   \subjclass  {65H10, 65H20, 68Q25}
   \keywords   {homotopy, conditioning, gap theorem}
   \address    {Departamento de Matematica Aplicada da UFRJ \\
                Caixa Postal 68530 \\
                 CEP 21945 \\
                 Rio \\ RJ \\
                 Brasil}
   \email      {gregorio@@lyric.labma.ufrj.br}

   \begin{document}
   \maketitle
   \begin{abstract}
            The number of steps of homotopy algorithms for
            solving systems of polynomials is usually bounded
            by the condition number of the homotopy path.
            A generic bound on the condition number of homotopy
            path between systems with integer coefficients will
            be given.
   \end{abstract}

\section{Introduction}

            In~\cite{M}, it was proven that there is a Zariski closed
            set $\Sigma '$ in the space of all systems of homogeneous
            polynomial
            equations of degree $\bold{d} =
            (\bold{d}_1 , \dots , \bold{d}_n)$ in $n+1$
            variables, with the following property~:
            For any $f$ not in $\Sigma '$, $f$
            with integer (resp. Gaussian integer) coefficients, the
            Shub and Smale condition number $\mu(f)$ of $f$ satisfies~:
   $$
            \mu(f) \le \mu(\Sigma ') \ \height{f} ^{d(\Sigma ')}
   $$
   \par
            The numbers $\mu(\Sigma ')$ and $d(\Sigma ')$ depend
            only on $n$ and $\bold{d}$, and~:
  $$
     \height{f} = \max
            \left( \Re |f_{iJ}| + \Im |f_{iJ}| \right)
   $$
   \par

            where $f_{iJ}$ ranges over all the coefficients of $f$.
            For more details, see ~\cite{M} and~\cite{Bez1}.
   \medskip
   \par
            In this paper, a similar theorem is proven for the
            condition number of a
            linear homotopy path $\{ \fpath{t} \} = \{ (1-t) \fpath{0}
            + t \fpath{1} \}$~. Here, $t$ is a real parameter in $[0,1]$.
            The same homotopy path will be represented by the
            pair $(\fpath{0},\fpath{1})$~.
   \par
            This bound will provide a {\em generic} worst case bound for
            the number of steps of a homotopy algorithm.
            See ~\cite{PhD,TCS,Bez1,Bez2,Bez3,Bez4,Bez5}.
   \medskip
   \par
            Let $\Hd$ be the complex vector space of all systems
            of $n$ homogeneous polynomial equations
            of degree $\bold{d}$ in $n+1$
            variables. The notation ${\Bbb P} (\Hd)$ will denote
            the projectivization of the complex vector space $\Hd$.
            One may consider a path as a subset of ${\Bbb P} (\Hd)$~.
            Its Zariski-closure is always a complex line (provided
            $\fpath{0} \ne \fpath{1}$). Generically speaking, it meets the
            discriminant variety $\Sigma \subset {\Bbb P} (\Hd)$~.
            This is still true if one fixes one of the systems
            $\fpath{0}$ and $\fpath{1}$.
  \medskip
  \par
            We may also represent the path $\{ \fpath{t} \}$ by an
            element $(\fpath{0},\fpath{1})$ of the space
            ${\cal H} = \Hd \times \Hd$. Once again, it makes sense
            to look at the Zariski closure of the set of paths
            meeting the discriminant variety $\Sigma$, as subsets of
            $\Bbb P(\Hd)$. Clearly, all non-constant paths
            are in this closure.
            Therefore, it makes no sense to look for a closed set in
            $\cal H$ to generalize $\Sigma'$ of~\cite{M}.
  \par
            However, a generalization is possible if we consider
            the {\em real} vector space
            ${\Bbb R}({\cal H}) = \left( \Re({\cal H}),
            \Im({\cal H}) \right)$~. This space is endowed with
            Zariski topology as a real vector space. Indeed,
            we will prove~:
{\main      Let $n$ and $\bold{d}=(\bold{d}_1, \dots , \bold{d}_n)$
            be fixed. Let $\cal H$
            be the complex vector space of all pairs
            $(\fpath{0}, \fpath{1})$ of
            polynomial systems of degree $\bold{d}$. Then there is a
            non-trivial Zariski
            closed set $\Sigma ''$ in ${\Bbb R}(\cal H)$ such
            that, for all $\fpair$ not in $\Sigma ''$ and for all
            $t \in [0,1]$~,
$$
            \mu( \fpath{t} )
            \le
            \mu(\Sigma '') \ \height{ \fpair } ^{d(\Sigma '')}
$$
    \par
            where the numbers $\mu(\Sigma '')$ and $d(\Sigma '')$
            depend only on $d$, and~:
$$
    \height{ \fpair } =
            \max \left( \height{\fpath{0}}, \height{\fpath{1}} \right)
$$
   \par
   Moreover, one can choose $d(\Sigma'') = 2 n \prod \bold{d}_j \
   \sum \bold{d}_j$
            }



     \medskip
     \par
            We will first construct the set $\Sigma''$ containing all
            the singular paths. Then, using a result in~\cite{M},
            we will bound the `distance' between a path $\{ \fpath{t} \}
            \not \in \Sigma''$ and $\Sigma''$, in terms of
            $\height{\fpair}$~. Finally, we will
            bound the condition number $\mu(\{ \fpath{t} \} )$
            in terms of the inverse of the
            distance to $\Sigma''$~.
            A suitable distance may be
            introduced in the `real projectivization'
            of ${\Bbb R}({\cal H})$ by~:
$$
           \drp(  \fpair , \gpair ) ^2
           =
           {1 \over 2}
           \left(
           \drp ( \fpath{0} , \gpath{0} ) ^2
           +
           \drp ( \fpath{1} , \gpath{1} ) ^2
           \right)
$$
            \par
            On the right hand side,
            $\drp(.,.)$ is the projective 2-distance~:
$$
            \drp(f,g) = \min_{\lambda \in {\Bbb R}_*}
                          { \knorm{f - \lambda g} \over \knorm{f} }
$$
      \par
            This distance can also be interpreted as the sine of the
            (real) angle between $f$ and~$g$. The norm $\knorm{.}$
            denotes the $SU(n+1)$ invariant norm in $\Hd$ (See
            ~\cite{KOSTLAN,Bez1}).
      \par
            This is similar to the usual projective distance~:
$$
            \dcp(f,g) = \min_{\lambda \in {\Bbb C}_*}
                          { \knorm{f - \lambda g} \over \knorm{f} }
$$
   \par
            Clearly, $\dcp(f,g) \le \drp(f,g)$.
\medskip




\section{Breaking the algebraic structure}


   In order to construct the set $\Sigma''$, we will need somehow to
   `break' the algebraic structure of the problem. The crucial
   step for this is the following, elementary fact~:

{\lemma
         Let $g \in {\Bbb C}[x]$~. Let $R$ denote the resultant of
         two degree $\deg g$ polynomials. Then $g$ has a real
         factor of degree $\ge 1$ if and only if $R(g,\bar g) = 0$~.
         }
\medskip
\par
\pf
   Suppose $g$ has a real factor $r$. Then $r$ has a real zero $\zeta$,
   or a pair of conjugate zeros $\zeta$ and $\bar \zeta$. In both cases,
   $\zeta$ is a common zero of $g$ and $\bar g$. Therefore the resultant
   $R(g,\bar g)$ vanishes.
\par
   Conversely, suppose that $R(g,\bar g) = 0$. Then $g$ and $\bar g$ have
   a common zero $\zeta$. Furthermore, $g(\bar \zeta) = \overline{
   {\bar g}(\zeta)} = 0$~, so $\bar \zeta$ is a zero of $g$, and
   the polynomial $(x-\zeta)(x-\bar \zeta) = x^2 - 2 x \ \Re(\zeta)
   + |\zeta|^2$ divides $g$. \qed
\medskip
\par
   We may now construct the polynomial
   $h(t) = R(\fpath{t} \det D'\fpath{t})$
   where $D'$ denotes the derivative with respect to $x_1$, \dots,
   $x_n$, and where $R$ denotes Macaulay's resultant~\cite{CANNY,MACAULAY}
   of $n+1$
   homogeneous polynomials in $n+1$ variables. $R$ is a polynomial
   of degree $(\prod_{j \ne i} \bold{d}_j) (\sum \bold{d}_j - n) +
   \prod_j \bold{d}_j$
   in each set of `variables' $\fpath{t}_j$~. As a polynomial in $t$,
   it has degree bounded by $n \prod \bold{d}_j \sum \bold{d}_j$.
\par
   Vanishing of the resultant is a necessary and sufficient condition
   for $\fpath{t}$ and $\det D'\fpath{t}$ to have a common root
   in $\Bbb P ^n$~. This common root may be a degenerate root of
   $\fpath{t}$ or a root of $\fpath{t}$ at `infinity' $x_0=0$~.
   Indeed, if $\fpath{t}(x)=0$ and $D'\fpath{t}(x)$ is not
   surjective, we obtain~:
$$
   0
   =
   D\fpath{t}(x) . x
   =
   x_0 {\partial \fpath{t} \over \partial x_0}
   +
   D'\fpath{t}(x) . \left( \begin{array}{c} x_1 \\ \vdots \\ x_n
   \end{array} \right)
$$
\par
   However, if $D\fpath{t}(x)$ is surjective, the columns of
   $D'\fpath{t}(x)$ cannot spawn ${\partial \fpath{t} \over \partial x_0}$~,
   hence $x_0=0$.
\medskip
\par
   Clearly, if $f_t \in \Sigma$ for some real $t$, then $h$ has a real
   factor. We now define the mapping~:
$$
   \begin{array}{ccccl}
   p: & {\cal H} & \rightarrow & {\Bbb C} \\
     & (\fpath{0}, \fpath{1}) & \mapsto & R(h, \bar h)
   \end{array}
$$
   \par
   The mapping $p$ defines a polynomial from ${\Bbb R}(\cal H)$
   into $\Bbb R^2$. If some $\fpath{t} \in \Sigma$, then
   $p(\fpath{0},\fpath{1})$ vanishes. Let $\Sigma'' = Z(p)$.

{\lemma
   The set $\Sigma''$ is a non-trivial closed set.}
\medskip
\par
   We mean that $p$ does not vanish uniformly on ${\Bbb R}(\cal H)$.
\medskip
\par
\pf
   Let $\fpair$ be generic, in the following sense~: We require
   $\fpath{0}$ and $\fpath{1}$ to be non-degenerate, and to have no root
   at `infinity' $x_0 = 0$. We also want $\fpath{0}$ and $\fpath{1}$ not
   colinear.
\medskip
\par
   We will prove that for a `generic' complex number $\lambda$
   (in a sense we will precise later),
   the path $(\fpath{0}, \lambda \fpath{1})$ is not in
   $\Sigma''$. Compare with Theorem 1 in \cite{MS}.
\par
   Indeed, let $h^{\lambda}(t) = R(\fpath{t}, \det D'\fpath{t})$
   where $\fpath{t} = (1-t) \fpath{0} + t \lambda \fpath{1}$.
\par
   The polynomial $h^{\lambda}$ does not vanish uniformly in $t$,
   since $\fpath{0}$ has no degenerate solution, and no solution
   at infinity. Let $D$ be the (maximal) degree of $h^\lambda$,
   as a polynomial in $t$.
\medskip
\par
   Let $t_1, \dots, t_D$ be the roots of $h^1$. We will see that
   a `generic' choice of $\lambda$ will put $t_1$, \dots, $t_D$
   in position $s_1$, \dots, $s_D$ such that $s_i \ne \bar s_j$
   for all $i, j$, possibly $i=j$.
   Therefore, $h^{\lambda}$ has no real factor in general,
   and $(\fpath{0}, \lambda \fpath{1})$ is not in
   $\Sigma''$~.
\medskip
\par
   Indeed, for almost all $\lambda$, we may choose $s_i$
   such that~:
$$
   (1-t_i) \fpath{0} + t_i \fpath{1}
   =
   c_i
   \left(
   (1-s_i) \fpath{0} + s_i \lambda \fpath{1} \right)
$$
\par
   where $c_i$ is some complex number. If we do that,
   $h^{\lambda}(s_i) = h(t_i) {c_i}^D = 0$~. We have to solve~:
$$
  c_i = {1 - s_i \over 1 - t_i} = {\lambda s_i \over t_i}
$$
   \par
   Recall that the genericity hypothesis in $\fpair$ prevents
   $t_i=0$ or $t_i=1$. We obtain~:
$$
   s_i \lambda - s_i \lambda t_i = t_i - s_i t_i
$$
   \par
   Solutions are~:
$$
   s_i = {t_i \over \lambda - \lambda t_i + t_i}
$$
   \par
   Those $s_i$ are finite for all $\lambda \ne {- t_i \over 1 - t_i}$,
   all $i$. We still need
   to prove that for `generic' $\lambda$, there are no $i,j$
   (possibly $i=j$) such that $s_i = \bar s_j$, or again~:
   $\Im({s_i}^{-1} + {s_j}^{-1}) = 0$. (Recall that $s_i \ne 0$).
\par
   The situation to avoid is~:
$$
   \Im \left(
     {\lambda - \lambda t_i + t_i \over t_i}
     +
     {\lambda - \lambda t_j + t_j \over t_j}
   \right)
    = 0
$$
\par
   This is~:
$$
   \Im \left(
   { t_j - 2 t_i t_j + t_i \over t_i t_j } \lambda + 2
   \right) = 0
$$
\medskip
\par
   Therefore, it suffices that $\lambda$ avoids a finite set
   of points and real lines in complex plane. \qed


\section{End of the proof}




\par
        We are now under the hypotheses of Theorem 1 in \cite{M}~:
   {\theorem \label{th:1}
            Let $p$ be a multi-homogeneous polynomial of degree $r_1, \dots,
            r_n$ in sets of variables $f_1 \in {\Bbb C}^{m_1}$,
            $\dots$, $f_n \in {\Bbb C}^{m_n}$~,
            with integer coefficients. Assume also that
            groups of variables $f_i$ range over Gaussian integers.
            Then either $p(f)=0$, or~:
         $$
            \dcp (f,Z(p)) \ge
            {1 \over {\pi \over 2} \max \sqrt{m_i} \sum r_i \bheight{p} }
            \left( { 1 \over \height{f} } \right)^{\sum r_i}
         $$
            \par
            where $Z(p)$ is the zero-set of $p$ and $d$ is the
            complex projective
            $2$-distance.
            }
   \medskip
   \par
       Here, the number $\bheight{p}$ depends only on $p$.
       We set $d(\Sigma '') = \sum r_i
       \le 2 n (\prod \bold{d}_j) (\sum \bold{d}_j - n)$~. We define
       $\mu(\Sigma'')$ as
       ${\pi \over 2} \max \sqrt{m_i} \sum r_i \bheight{p}$~. Then,
       using $\drp \le \drp$~, we
       obtain a weaker version of the Main Theorem~:
  {\theorem
            Let $n$ and $\bold{d}=(\bold{d}_1, \dots , \bold{d}_n)$
            be fixed. Let $\cal H$
            be the space of all pairs $(\fpath{0}, \fpath{1})$ of
            polynomial systems of degree $\bold{d}$. Then there is a
            non-trivial Zariski
            closed set $\Sigma ''$ in $\Bbb R (\cal H)$ such
            that, for all $\fpair$ not in $\Sigma ''$ and for all
            $t \in [0,1]$~,
$$
            {
            1 \over \drp(\fpair , \Sigma'')
            }
            \le
            \mu(\Sigma '') \ \height{ \fpair } ^{d(\Sigma '')}
$$
    \par
            where the numbers $\mu(\Sigma '')$ and $\d(\Sigma '')$
            depend only on $d$, and~:
$$
    \height{ \fpair } =
            \max ( \height{\fpath{0}}, \height{\fpath{1}} )
$$
            }
    \medskip
    \par
     In order to conclude the proof of the Main Theorem,
     we will need the
 {\lemma
       $$
           \max_{t \in [0,1]} \mu(\fpath{t}) \le
            {
            1 \over \drp( \fpair, \Sigma'')
            }
       $$
       }
    \medskip
    \par
    Since $\mu$ is real-scaling invariant, we may assume without loss
    of generality that $\knorm{\fpath{t}} = 1$ always.
    \medskip
    \par
       It was proven in~\cite{Bez1} that for a given system $f$,
    $$
    \mu(f) \le {1 \over \dcp(f, \Sigma)}
    $$
   \par
         The condition number of a homotopy path was defined by~:
    $$
    \mu( \{ \fpath{t} \} )
    =
    \max_{t \in [0,1]}
    \mu( \fpath{t} )
    $$
    \par
    Hence~:
    $$
    \mu( \{ \fpath{t} \} )
    \le
    \max \begin{Sb} t \in [0,1] \\ g \in \Sigma \end{Sb}
    {1 \over \dcp(\fpath{t}, g)}
    =
    {1 \over {\min \begin{Sb} t \in [0,1] \\ g \in {\Bbb R}(\Sigma) \end{Sb}
    \dcp(\fpath{t}, g)}}
    $$
\par
    Suppose that this minimum was attained at some $t \in [0,1]$
    and some $g \in \Sigma$~:
    $$
    \dcp(\fpath{t},g)
    =
    {
    \min_{\lambda \in \Bbb C_*}
    \knorm{ \fpath{t} - \lambda g} \over \knorm{\fpath{t}}
    }
    $$
    \par
    Since $\lambda g$ also belongs to $\Sigma$, we may scale $g$
    by $\lambda$ so that~:
    $$
    \dcp(\fpath{t}, g)
    =
    {
    \knorm{\fpath{t} - g} \over \knorm{\fpath{t}}
    }
    =
    \drp(\fpath{t}, g)
    $$
    \par
    This shows that~:
    $$
    \mu(\{ \fpath{t} \}) \le {1 \over \drp(\fpath{t},g)}
    $$
  \medskip
  \par
    We may now define a new homotopy path $\gpath{s}$ that is,
    in some sense, the translation of $\fpath{t}$~:
    $$
    \gpath{s} = \fpath{s} + (g - \fpath{t})
    $$
     \par
     With that definition~:
    $$
    \drp( \{ \fpair \} , \{ \gpair \} ) ^2
    =
    {1 \over 2}
    \left(
    \drp(\fpath{0} , \gpath{0} )^2
    +
    \drp(\fpath{1} , \gpath{1} )^2
    \right)
    $$
 \par
    But $\drp(\fpath{0}, \gpath{0}) \le
    {\knorm {g - \fpath{t}} \over \knorm{\fpath{0}}}
    =
    \knorm {g - \fpath{t}}$, and similarly for
    $\drp(\fpath{0}, \gpath{0})$. Therefore~:
    $$
    \drp( \{ \fpair \} , \{ \gpair \} ) ^2
    \le
    \knorm{g - \fpath{t}} ^2 = \drp(\fpath{t}, g)^2
    $$
    \par
    Therefore,
    $$
    \mu( \{ \fpath{t} \} )
    \le
    {1 \over \drp( \fpath{t}, g) }
    \le
    {1 \over \drp( \fpair , \gpair ) }
    $$
    \par
    Moreover, since $\gpair \in \Sigma ''$,
    $$
    \drp( \fpair, \gpair)
    \ge
    \drp( \fpair, \Sigma'')
    $$
    \medskip
    \par
    Thus, we obtained~:
    $$
    \mu( \{ \fpath{t} \} )
    \le
    {
    1
    \over
    \drp( \fpair, \Sigma'')
    }
    $$
    \medskip
    \par
    This proves the Lemma, and hence the Main Theorem.

\begin {thebibliography}{12}


   \bibitem{CANNY}
   John Canny,
   \newblock {\em The complexity of robot motion planning},
   \newblock MIT Press, Cambridge, Mass., 1988.

\bibitem{KOSTLAN}
   Eric Kostlan,
   \newblock{\em Random polynomials and the statistical fundamental
          theorem of algebra},
   \newblock Preprint, Univ. of Hawaii, 1987.

   \bibitem{MACAULAY}
   F. S. Macaulay,
   \newblock Some formul\ae {} in elimination,
   \newblock {\em Proceedings of the London Mathematical Society},
   \newblock Vol XXXV, 1903.


   \bibitem {PhD}
   Gregorio Malajovich
   \newblock {\em On the complexity of path-following Newton algorithms
     for solving systems of polynomial equations with integer coefficients.}
   \newblock PhD Thesis, Berkeley, 1993.
   \newblock United Microfilms Inc, 300 North Zeeb Road, Ann Arbor,
             MI, 48106-1346 USA, Phone 800-521-0600.

   \bibitem {TCS}
   Gregorio Malajovich
   \newblock On generalized Newton algorithms~: quadratic convergence,
             path-following and error analysis.
   \newblock {\em Theoretical Computer Science} {\bf 133} 65-84, 1994.

   \bibitem {M}
   Gregorio Malajovich
   \newblock {\em Worst possible condition number of polynomial systems.}
   \newblock Preprint, Rio de Janeiro, 1995.

   \bibitem{MS}
   Alexander Morgan and Andrew Sommese,
   \newblock Computing all solutions to polynomial systems using homotopy
   continuation.
   \newblock {\em Applied Mathematics and Computation} {\bf 24},
   115-138, 1987.

   \bibitem{Bez1}
   Michael Shub and Steve Smale,
   \newblock On the Complexity of Bezout's Theorem I - Geometric aspects.
   \newblock {\em Journal of the AMS}, {\bf 6}, 2, Apr 1993.

   \bibitem{Bez2}
   Michael Shub and Steve Smale,
   \newblock On the complexity of Bezout's Theorem II - Volumes and
             Probabilities.
   \newblock in: F. Eysette and A. Galligo, eds~:
   \newblock {\em Computational Algebraic geometry}.
   \newblock Progress in Mathematics {\bf 109}, Birkhauser, 267-285, 1993.

   \bibitem{Bez3}
   Michael Shub and Steve Smale,
   \newblock Complexity of Bezout's Theorem III ; Condition number and packing.
   \newblock {\em Journal of Complexity} {\bf 9}, 4-14, 1993.

   \bibitem{Bez4}
   Michael Shub and Steve Smale,
   \newblock Complexity of Bezout's Theorem IV ; Probability of success ;
   Extensions
   \newblock Preprint, Berkeley, 1993.

   \bibitem{Bez5}
   Michael Shub and Steve Smale,
   \newblock Complexity of Bezout's Theorem V : Polynomial time ;
   \newblock Preprint, Barcelona, 1993.

   \end {thebibliography}

   \end{document}

