%
%
%      On the Complexity of Path-Following Newton Algorithms
%           for Solving Systems of Polynomial Equations
%                  with Integer Coefficients.
%
%
%      by Gregorio Malajovich
%         gregorio@labma.ufrj.br
%
%
%
%      PhD Thesis.  Berkeley, Dec. 1993.
%
%
%      Also available at :
%
%
%            United Microfilms Inc.,
%            300 North Zeeb Road,
%            Ann Arbor, MI, 48106-1346,
%            USA
%            Phone 800-521-0600
%
%      Copyright (c) 1993 by Gregorio Malajovich.
%
%      Notice : some of the contents here have been improved,
%      and may appear as separate papers. Please contact the
%      author for an update.
%
%
%      This is an AMS-Latex file.
%      AMS-Latex is a kind of upgrade of Latex, by the AMS.
%      Its primary distrbution site is e-math.ams.com
%      It can be reached by anonymous ftp.
%
%      In order to compile this file, you'll need thesis.sty also.
%
%
%
% -----------------------------------------------------------------

\documentclass{amsbook}
\usepackage{thesis}

\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{\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{\fl}{\text{\rm fl}}
\newcommand{\tensor}{\otimes}
\newcommand{\drond}{\partial}
\newcommand{\Hd}{{\mathcal H}_d}
\newcommand{\Pd}{{\mathcal P}_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{\rm k}}}}
\newcommand{\fnorm}[1]{{\left \| {#1}\right  \|_{\text{\rm f}}}}
\newcommand{\norm}[1] {{\left \| {#1} \right \|_2}}
\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{\fmu}{{\mu_{\text{\rm f}}}}

\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}
\renewcommand{\themain}{}
\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}


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


\begin{document}
\bibliographystyle{plain}

% The title page and copyright page are unnumbered.

\pagenumbering{arabic}
\pagestyle{headings}

%
% title page is done in {titlepage} environment
%
\begin{titlepage}
%
% no page number
%
\begin{center}
\begin{large}			% title is set in \large size
On the Complexity of Path-Following Newton Algorithms \\
for Solving Systems of Polynomial Equations \\
with Integer Coefficients. \\
%\vspace{\stretch{0.25}}
%(Version 2 -- \today)
\end{large}

\vspace{\stretch{0.25}}		% (rubber) vertical space after title
by\\
[\stretch{0.25}]		% (rubber) vertical space
Gregorio Malajovich-Mu\~{n}oz\\ 
\vspace{\stretch{0.25}}
B.S. (Universidade Federal do Rio de Janeiro) 1989\\
M.S. (Universidade Federal do Rio de Janeiro) 1990\\
\vspace{\stretch{1.0}}
A thesis submitted in partial satisfaction of the\\
requirements for the degree of \\
Doctor of Philosophy\\
in \\
Mathematics \\
in the \\
{\large GRADUATE DIVISION} \\
of the \\
{\large UNIVERSITY of CALIFORNIA at BERKELEY} \\
\vspace{\stretch{0.5}}
\end {center}

\hspace\labelsep
Committee in charge:\par
\list{}{\itemindent 0.25in \let\makelabel\relax}
\item Professor Steve Smale, Chair
\item Professor Hendrik W. Lenstra
\item Professor John Canny 
\endlist
\vspace{\stretch{0.25}}		% (rubber) vertical space before year
\begin{center}
{\large 1993 \par}		% set year in \large size
\end{center}
\end{titlepage}

%\cleardoublepage

\begin{signaturepage}
\vspace*{\stretch{1.0}}	% (rubber) space before sig. introduction
%
% sig. introduction is centered
%
\begin{center}
%
% double-space signature introduction
%
\renewcommand{\baselinestretch}{2.0}\large\normalsize
%
The thesis of Gregorio Malajovich Mu\~{n}oz is approved~: \\
\end{center}
%
\vspace{\stretch{1.0}}	% (rubber) space before sig. lines
%
\begin{center}
\def\xlen{4in}
\def\xspace{0.25in}
\begin{minipage}{\xlen}
\begin{flushright}
\rule{\xlen}{1pt} \\ Chair \hspace{\stretch{1.0}} Date \\[\xspace]
\rule{\xlen}{1pt} \\ Date \\ [\xspace]
\rule{\xlen}{1pt} \\ Date \\[\xspace]
\end{flushright}
\end{minipage}
\end{center}
%
\vspace{\stretch{1.0}}	% (rubber) length before univ. & year
%
\begin{center}
University of California, Berkeley \\
1993
%
\vspace{\stretch{1.0}}	% (rubber) length before page number
%
\end{center}
\end{signaturepage}
%\cleardoublepage

\begin{copyrightpage}
\vspace*{\stretch{1.0}}
\begin{center}
On the Complexity of Path-Following Newton Algorithms \\
for Solving Systems of Polynomial Equations \\
with Integer Coefficients. \\
{\copyright} copyright 1993 \\
by \\
Gregorio Malajovich-Mu\~{n}oz.\\
\end{center}
\end{copyrightpage}
%\cleardoublepage

%\cleardoublepage

% The table of contents, list of figures, list of tables uses
% lower-case Roman numerals.
\pagenumbering{roman}

\setcounter{page}{3}    % Graduate division is crazy.
\pagestyle{myheadings}
\markright{}
\tableofcontents

%\cleardoublepage


%\listoffigures
%\cleardoublepage

%\listoftables
%\cleardoublepage

%\acknowledgement
%\cleardoublepage


\pagenumbering{arabic}
\pagestyle{headings}


\chapter {Introduction}
\label   {ch:intro}

\begin {abstract}
Complexity of solving systems of polynomial equations with integer
coefficients can be bounded for a generic class of systems.
\end   {abstract}

\section {Systems of polynomials with Integer coefficients}
\label{sec:systems}
Let $\Hd$\glossary{$\Hd$&A space of systems of polynomial equations}
be the space of all systems of 
$n$\glossary{$n$&In most places, number of equations.}
homogeneous polynomial
equations with degree 
$d = (d_1 , \dots , d_n)$\glossary{$d=(d_1,\dots,d_n)$&Degree of the systems of polynomials}
in variables 
$(x_0, \dots , x_n)$ with complex coefficients. 
The space $\Hd$ is a complex vector space, with coordinates given by
the coefficients of each polynomial.
\par
A {\em zero} of a system $f \in \Hd$ is a point $\zeta \in \Bbb C^{n+1}$,
$\zeta \ne 0$, such that $f(\zeta) = 0$. Alternatively, a zero
of $f$ is a ray $\{ \lambda \zeta : \lambda \in \Bbb C \} $,
for $f(\zeta) = 0$~. This ray can be interpreted as a point in
projective space $\Bbb {CP}^n$.
\par
We will consider several versions of {\em Newton iteration}. One of them
will be given by the operator $N\pseu : x \mapsto x - Df(x)^\dagger f(x)$,
where $Df(x)^\dagger$ denotes the Moore-Penrose pseudo-inverse of  
$Df(x)$ (See Chapter \ref{ch:condpath}).
\par
Since the concept of a zero is not practical computationally,
we will consider the following concept of {\em approximate zero}~:
{\definition \label{def:approximate}
             Let $f \in \Hd$, and let $z = z_0 \in \Bbb C^{n+1}$, $z \ne 0$.
             Let $z_{i+1} = N\pseu(z_i)$.
             The point $z$ is said to be an {\em approximate zero} of $f$
             if and only if there is a zero $\zeta$ of $f$
             {\em associated} to $z$, such that~:
             $$
             \min_{\lambda} { \norm {z_i - \lambda \zeta}
                              \over \norm{z_i} }
             <
             2^{-2^i - 1}
             $$
             }
\medskip
\par
Another important notion is a version of the concept of {\em height}. 
If $a,b \in \Bbb Z$, we define $H(a) = |a|$~
\glossary{$H(x)$&Height of a rational point or polynomial}
 and $H(a+bi) = |a| + |b|$.
(This is not the standard definition).
If $v$ is a vector, we define $H(v) = \max H(v_j)$ . If $f$ is a 
polynomial (or a system of polynomials), $H(f)$ is the maximum
of the height of the coefficients of $f$.
\par
Let $S(f)$\glossary{$S(f)$&the number of non-zero coefficients of $f$}
denote 
the number of non-zero coefficients of $f$.
A reasonable measure of the {\em size} of an input $f \in \Hd$ 
would be the quantity $S(f) \log H(f)$.

              

\section {Global complexity of polynomial-solving}
\label{sec:global}
For the purpose of our complexity analysis, a
{\em system $f$ of polynomials with integer coefficients}
(resp. {\em with Gaussian integer coefficients}) will
be the list of integers 
$n, (d_1, \dots , d_n) , (S(f_1), f_1), \dots , (S(f_n), f_n)$,
where each $f_i$ is a list of monomials $f_{iJ} \ x^J$. Those
monomials will be represented
by integers $f_{iJ}, J_0, \dots , J_n$ 
(resp. $\Re (f_{iJ}), \Im (f_{iJ}), J_0, \dots , J_n$).
\par
We define an  {\em approximate solution} of a system $f$ of polynomials 
as a list $X_1,$  $\dots,$ $X_{\prod d_i}$
of points of $\Bbb C^{n+1}$ with Gaussian integer
coefficients, such that 
each $X_i$ is an approximate zero of $f$
associated to a different zero ray of $f$, and
there is a $X_i$ associated to every zero ray of $f$.
Each $X_i$ will be represented by the list of its coordinates
(real and imaginary parts).     
\par
We will give an algorithm to obtain an approximate solution
of a {\em generic} system of polynomial equations with Gaussian integer
coefficients. By generic, we mean that it should not belong to
a certain {\em real} algebraic variety of the realization of $\Hd$.
The algorithm will require~:
$$
O\left(
(\max d_i)^{3/2} \mu^2 \left( (n+1) S(f) \max d_i + (n+1)^3 \right)
\right)
$$
\par
floating point operations, with relative precision
$$
O\left({1 \over \mu^2 (\max d_i)^2 (n+1)^3 + \max S(f_i) } \right)
$$
\par
Here, $\mu$ is a condition number, to be defined later.
\par
This result can be stated more precisely in the language of the theory of
computation. Our main model of computation will be the Blum - Shub - Smale machine
over $\Bbb Z$ (See \cite{BSS}). The complexity results we will obtain
will be equivalent, up to polynomial time, to Turing complexity.
In this setting, we will prove the
\par
{\main \label{main} 
       There is (we can construct)
       a Blum-Shub-Smale machine $M$ over $\Bbb Z$,
       that to the input $f \in \Hd$ 
       (a system of polynomials with Gaussian integer coefficients),
       associates the list of integers
       $M(f)$ representing
       $\prod d_i$ points of $\Bbb C^{n+1}$ with Gaussian integer
       coefficients~; 
       \par
       For each $n$, for each $d=(d_1, \dots , d_n)$ 
       there is a Zariski open set $U_d$ in $\Hd$
       (considered as a real projective space)~;
       \par
       If $f \in U_d$, then~:
       \par 1 --
       $M(f)$ is an approximate solution to $f$.
       \par 2 --
       The output $M(f)$ is computed within time~:
       $$
     \left(
       (\prod d_i)
       (\max d_i)^{3/2} \mu^2 
       +
       n (\prod d_i)^2 \sum d_i
     \right)
      \left( (n+1) S(f) \max d_i + (n+1)^3 \right)
      \times
       $$
       $$
       \times
       P(\log \mu, \max d_i, \log n, \log S(f), \log \log H(f))
       $$
       \par
       where $P$ is a polynomial, and $\mu$ is a condition number, to
       be defined. 
       \par
       3 --
       The condition number $\mu$ can be bounded by~:
       $$
       \mu < \mu_0 H(f)^{d_0}
       $$
       \par
       where the numbers $\mu_0$ and $d_0$ will be defined
       later, and depend solely on $d=(d_1, \dots , d_n)$.
       } 

 
\section {The geometry of polynomial-solving}
\label{sec:ig}
There are mainly two known classes of algorithms for solving systems
of polynomial equations. The oldest class consists of algorithms derived
from elimination theory. Elimination theory reduces polynomial solving
to a linear problem in a high-dimensional space (e.g. dimension 
$\binomial{\sum d_i}{n}$), the space of monomials of degree
$\sum d_i - n$. 
\par
Some of those algorithms were developed at the start of this century
(See Macaulay~\cite{MAC} or Van der Waerden~\cite{VAN})~. At
that time, those algorithms were deemed untractable for more than
~2 or ~3 equations.
\par
Modern algorithms using algebraic ideas include Gr\"obner Bases
factorizations or numeric algorithms like those of Canny \cite{CANNY}
or Renegar \cite{RENEGAR}. Some of those algorithms are particularly 
suitable to some kinds of sparse systems. When the system is 
sparse, it is possible to reduce the linear problem to a more modest
dimension.
\medskip
\par
The other class of algorithms are the homotopy (path-following)
methods. Several path-following procedures have been suggested
(see Morgan, \cite{MOR}). Basically, the algorithm follows a
path $[f_0,f_1]$ in the space of polynomial systems $\Hd$. Here,
$f_1$ is the system we want to solve, and $f_0$ is some system
that we know beforehand how to solve.
\par
If we complexify and projectivize both the spaces of systems and
of solutions, then the solution rays ${\lambda x_t : f_t(x_t)=0}$ 
depend smoothly on $f$, except in some degenerate locus $\Sigma$.
It turns out that the degenerate locus is an algebraic variety,
called the {\em discriminant variety}.
\par
Path-following algorithms produce a finite sequence $f_{t_i}$ in
$[f_0, f_1]$ ; at each step, an approximate solution $x_{t_i}$
for $f_i$ is computed, using the previous approximate solution
$x_{t_{i-1}}$ of $f_{t_{i-1}}$. In this thesis, this is done by
a generalization of Newton iteration.
\par
The complexity of that kind of path-following methods was
studied by Shub and Smale in \cite{BEZI}, assuming a model of
real number computations. Among other
important results, they bounded the number of homotopy steps
necessary to follow a path in terms of a condition number
$\mu([f_0,f_1]) = \max _{f \in [f_0,f_1]} \mu(f)$.
\par
The condition number $\mu(f)$ has a simple geometric interpretation~:
it is the inverse of the minimum of $\rho(f,\zeta)$, the
{\em distance} between $f$ and the discriminant variety along the
fiber $\{ f(\zeta) = 0 \}$.
\par
Therefore, the number of homotopy steps depends on how far is the
path $[f_0,f_1]$ from the discriminant variety.


\section {Outline of this Thesis.}


In Chapter \ref{ch:condpath}, the results of \cite{BEZI} on the
the quadratic convergence of Newton iteration and on the
count of homotopy steps will be extended to the case of
approximate Newton iteration. 
\par
Indeed, the iterates of good enough approximations $x_0$ of
a zero $\zeta$ will verify a condition of the form~:
 $$
             \min_{\lambda} { \norm {x_i - \lambda \zeta}
                              \over \norm{x_i} }
             <
             \max \left( 2^{-2^i - 1} , k \delta \right)
 $$    
\par
where $k$ is a small integer, provided the {\em error} of each
iteration is bounded by $\delta$.
\par
The robustness theorem of \cite{BEZI} will also be extended
to the case of approximate Newton iteration. 
\medskip
\par
The worst case complexity of approximate Newton iteration is
the subject of Chapter \ref{ch:newton}. For instance, given
$f$, $x$ and $\delta$, we want an algorithm to approximate 
$x - Df(x)^\dagger f(x)$, with {\em error} at most $\delta$,
i.e., with precision $\delta \norm{x}$.
\par
Methods like exact rational or integer calculation, or like
interval arithmetics, are not very efficient for computational
or even theoretical complexity purposes, because of coefficient
growth. Therefore, the construction of approximate Newton
operators will be carried on using a machine with a fixed
finite precision. Rigorous error bounds will be obtained,
using standard numerical analysis techniques. The fixed precision
machine can easily be constructed from a machine over the integers,
equivalent (up to polynomial time classes) to a Turing machine.
\par
The machine precision necessary to obtain the $\delta \norm{x}$ 
approximation of $x - Df(x)^\dagger f(x)$ can be bounded in terms
of $n$, $d$, the height $H(f)$ of $f$ and the condition number $\mu(f,x)$.
\par
The global complexity of solving systems of polynomial equations
will be~, roughly speaking~, about $\mu^2 \log \mu$ times a polynomial
in~ $n$ and $\max d_i$~, times the number of solutions~ $\prod d_i$,
times the number of non-zero coefficients.
\medskip
\par
In order to give complexity bounds in terms of classical
complexity theory, it makes sense to require $f$ to have only 
integer (or Gaussian integer) coefficients. Although this 
precludes average-case complexity analysis using measure theory,
this requirement will allow us to obtain some worst case
bounds that would be impossible to obtain using computability
over the reals. 
In Chapter \ref{ch:gap}, it will be proved that there are numbers
$\mu(\Sigma)$ and $d(\Sigma)$ depending solely on $n$ and $d$, such that
whenever $\mu(f)$ is finite,
$\mu(f) < \mu(\Sigma)H(f)^{d(\Sigma)}$. Here, $H$ is the height of
$f$. 
\par
A similar analysis carries on to the conditioning of a whole path
in the space $\Hd$. This will provide us with a worst case bound
for $\mu$, hence for the complexity of solving a generic system $f$.
By {\em generic}, we understand that $f$ should not belong to a
real algebraic variety in the realization of $\Hd$, that we will
define. 
\medskip
\par
Chapter \ref{ch:global} will provide the algorithms 
for solving $f$, and the algorithms for certifying a
given approximate solution.
\par
Although it is not practical to implement a computer
program that will always succeed (provided  enough memory 
is available, of course), it is cheap to implement
a reasonably reliable program, with certification
procedures that would guarantee the results obtained. 
Some implementation details will also be discussed.


\section {Acknowledgements}
\par
I am thankful to Steve Smale, John Canny, Hendrik W. Lenstra for
their suggestions and advice while writing this thesis.
\par
Also, conversations with the following people were extremely
useful~:
     Lenore Blum,
     Felipe Cucker,
        Jim Demmel,
       Alan Edelman,
        Tom Emerson,
    Ioannis Emiris,
       Dima Grigoriev,
        Jan Hetting,
       Yili Huang,
   Myong-Hi Kim,
     Pascal Koiran
       T.Y. Li,
      Klaus Meer,
  Christian Michaux,
      Erich Novak,
     Victor Pan,
       Doug Priest,
    Maurice Rojas,
    Raymond Russell,
       Mike Shub,
       Rose St. John,
     Denise Wolf.
\medskip
\par
I was supported by a fellowship from the Conselho Nacional
de Pesquisa (CNPq) of Brasil. Special thanks to Patricia Pinheiro,
Marilene Farinasso, and all other CNPq staff that helped to
mantain CNPq active while under very adverse circumstances.
\par
Special thanks to
all the people that helped to convince the government of Brasil
to stop retaining the founds for tuition
and fees of the fellowship recipients; This was at a time some of us
were having our registration blocked.
\medskip
\par
During the years of my PhD, I was on a leave of absence
from the Universidade Federal do Rio de Janeiro. 
I am also thankful to IBM-Brasil, IBM-Yorktown Heights, and to the
Centre de Recerca Matem\`{a}tica of the Institut d'Estudis Catalans.
\medskip
\par
Special thanks to Luiz Carlos Guimaraes, without whom I
probably would not be studying mathematics at this time.
\medskip
\par
Special thanks to my parents, for their encouragement and support.
\medskip
\par
I also would like to thank all the people that
brought to existence all those electronic lists and newsgroups~:
Brasnet, Bras-Noticias, Sinopse, JCL noticias, CNPQ-l, pg-net, RUI.
\par
This thesis was typeset in AMS-\LaTeX, using a modification of
ucthesis document style.
\medskip
Berkeley, July 28, 1993 and Bellaterra, November 1, 1993.



\chapter [On generalized Newton algorithms ...]
         {On generalized Newton algorithms~:\\ 
          Quadratic Convergence, Path-following \\
          and error analysis}
\label   {ch:qct}
\label   {ch:condpath}

\begin {abstract}
   Three versions of the Newton method for approximating zeros of
   a system of homogeneous polynomial equations are presented. 
   Quadratic convergence theorems are obtained for exact and
   approximate iteration
   of the corresponding operators. \\
   A bound on the number of approximate Newton steps necessary 
   for path-following is estimated. This extends results in
   Shub - Smale \cite{BEZI}    
\end   {abstract}

\section {Introduction}
\label{sec:qct:intro}
Let $\Hd$ be the space of all systems of $n$ homogeneous polynomials
in $n+1$ complex variables, of degree $d = (d_1, d_2 , \dots, d_n)$,
with complex coefficients. Let 
$D = \max \ d_i$\glossary{$D$&Abreviation for $\max d_i$},
and assume $D \ge 2$.
The space $\Hd$
is endowed with the unitarily invariant 
{\em Kostlan norm} $\knorm{.}$,
defined by
$\knorm{f} = \sqrt{\sum \knorm{f_i}^2}$~
\glossary{$\knorm{.}$&Kostlan's unitary invariant norm}
,
where~:
$$
\knorm{f_i}
= \sqrt{ \sum_{|J|=d_i} { |f_{iJ}|^2 \over \binomial{d_i}{J}}}
= \sqrt{ \sum_{|J|=d_i} { |f_{iJ}|^2 \over
 \left( {d_i ! \over J_0 ! J_1 ! \dots J_n !} \right) } }
$$
\par
The Kostlan norm $\knorm{.}$ induces a metric 
$\dproj(f,g) = \min_{\lambda} {\knorm{\lambda f - g} \over \knorm{g}}$
in $\Hd$~
\glossary{$\dproj(f,g)$&Projective distance between $f$ and $g$ by
$\knorm{.}$}~.
\par
A zero of $f \in \Hd$ is a point $\zeta \in \Bbb {CP}^n$ such that 
$f(\zeta) = 0$.
Alternatively, it is a line through the origin in $\Bbb C^{n+1}$
such that $f(\zeta)=0$ for all $\zeta$ in that line.
\par

   Let $f \in \Hd$, and $x$ range over ${\Bbb C}^{n+1}$.
   $Df(x)$ is a linear operator from $\Bbb C ^{n+1}$ into
   $\Bbb C ^{n}$.
   A generalized
   Newton operator is defined by the mapping~:
   $$
    N_V : x \mapsto x - \DfI{x}{x} f(x)
   $$\glossary{$N_V$&Generalized Newton operator}
   \par
   where $V$\glossary{$V$&Certain family of hyperplanes}
   is a smooth family of hyperplanes
   in ${\Bbb C}^{n+1}$ , $V(ax)=aV(x)$, and each 
   $V(x)$ contains the point $x$. $V(x)$
   will inherit the metric of ${\Bbb C}^{n+1}$.
   The notation $\DfI{x}{x} f(x)$ represents a point
   of $V(x)$, as contained in $\Bbb C^{n+1}$.
   \par
   Different choices of $V$ lead to different versions of 
   Newton iteration, as we will see. 
   \par
   To each generalized Newton operator, we can associate 
   a few {\em invariants}.
   Those are functions of $\Hd \times {\Bbb C}^{n+1}$, and
   are invariant under the group generated by the following
   transformations ~: 
   \par
   Unitary~:
   $$
   (f,x) \mapsto (f \circ U^{-1}, Ux) \ , \ U \in U(n+1)
   $$
   \par
   Scaling~:
   $$
   (f_1, \dots , f_n,x) \mapsto (a_1 f_1, \dots , a_n f_n , b x)\  ,
       \ a_i,b \in {\Bbb C}_\star
   $$
   \par
   Scaling invariance implies that those invariants can be
   considered as functions of ${\Bbb P}(\Hd) \times \Bbb {CP}^n$.
   We define~:
   \begin{align*}
    \beta(f,z) &=
    \beta(z) = 
    {1 \over \norm{z}} . \norm{ \DfI{z}{z} f(z)} 
   \\
    \gamma(f,z) &=
    \gamma(z) = 
      \max \left\{
      1,
       \norm{z}
            \max_{k \ge 2} \left(
	    {1 \over k!}
	     \norm{ \DfI{z}{z} D^kf(z) } 
	     \right)^{1 \over k-1} 
       \right\}
   \\
    \alpha(f,z) &= \alpha(z) = \beta(z) \gamma(z)
   \end{align*}\glossary{$\beta$&Newton step length}\glossary{$\gamma$&A
   kind of measure of the non-linearity of a
   mapping}\glossary{$\alpha$&Product of $\beta$ and $\gamma$}
   \par
   Here, we have always $\gamma \ge 1$. Also, 
   $D^kf(z)$ is a multilinear operator from
   $\left(\Bbb C^{n+1}\right)^k$ into $\Bbb C^n$. Therefore, those
   definitions are slightly different from the ones in \cite{BEZI},
   where $D^kf(z)$ is restricted to what we call $V(x)^k$. 
   \par
   Invariance of $\alpha$, $\beta$ and
   $\gamma$ follows from the definitions.

\paragraph {The Newton operator in affine space~:}

   If we set~:
   $$
   V(x) = x + \left\{ 0, y_1, \cdots , y_n \right\}
   $$
   \par
   we obtain the (classical) Newton operator in affine space
   $N\aff$\glossary{$N\aff$&Newton operator in affine space}.
   If $\alpha(z_0)$ is small enough, successive iterates of
   $z_0$ will converge {\em quadratically} to a zero of $f$~.
   The following theorem is essentially the Quadratic Convergence
   Theorem by Shub and Smale in \cite{BEZI}~: 

{\theorem \label{qct:a1:aff}
          Let $f \in \Hd$ Let $z_0 \in {\Bbb C}^{n+1}$ have its
          first coordinate non-zero. Let
          $\alpha\aff(z_0) < 1/8$. Let the sequence $(z_i)$ be defined
          by $z_{i+1} = N\aff(z_i)$. Then there is a zero $\zeta$
          of $f$ such that $\dproj(z_i, \zeta) \le 2^{-2^i -1}$
          }
   \medskip
   \par
   Above, distance in projective space is measured by~:
   $$
   \dproj(x,y) = 
   \min_{\lambda \in {\Bbb C}} 
   \left\{
   \norm{ x - \lambda y } \over \norm{x} 
   \right\}
   $$\glossary{$\dproj(x,y)$&Distance between points $x$ and $y$ in
       projective space}
   \par
   There is a robust form of this theorem, that incorporates
   some error in each iteration. Since $N\aff(f,z_i)$ scales
   in $\norm{z_i}$, it makes sense to measure the error at
   each iteration by~:
   $$
   \norm{z_{i+1} - N\aff(f,z_i)} \over \norm{z_i}
   $$
   \par
   Indeed, we will prove~:
{\theorem \label{qct:a2:aff}
          Let $f \in \Hd$, let $z_0 \in {\Bbb C}^{n+1}$, let the first
          coordinate of $z_0$ be non-zero,
          and let $\delta \ge 0$
          verify ~: $(\beta\aff(f,z_0) + \delta) \gamma\aff(f,z_0) < 1/16$, and
          $\gamma\aff(f,z_0) \delta < 1/384$. 
          Let the sequence $(z_i)$, where the first coordinates of $z_i$
          and $z_0$ are equal,
          verify~:
          $$
          { \norm{z_{i+1} - N\aff(f,z_i)} \over \norm{z_i} }
          \le
          \delta
          $$
          \par
          Then there is a zero $\zeta$ of $f$ such that~:
          $$
          \dproj(z_i, \zeta)
          \le
          \max \left( 2^{-2^i -1} , 6 \delta \right)
          $$
          }
 
   Another version of the affine Newton operator was constructed 
   by Morgan \cite{MOR} by 
   fixing a random vector $y$, and setting $V(x) = x + y^\bot$.
   This {\em random change of coordinates}
   allows him to use the classical Newton operator
   (in affine space) with systems
   that have zeros at infinity.
   There are more general Newton operators that
   allow to approximate zeros at infinity.



\paragraph {The Newton operator in projective space~:}
   If we define~:
   $$
   V(x) = x + x^\bot
   $$
   \par
   we obtain the Newton operator in projective space,
   which may also be described by:
   $$
   N\proj(x) = x - \PDf{x}{x}^{-1} \PV{f(x)}
   $$\glossary{$N\proj$&Newton operator in projective space}
   
   where $x\ctrans$ means complex transpose of $x$. This operator was defined
   by Shub~\cite{SHUB}.

   We will prove the Theorems~:

{\theorem \label{qct:a1:proj}
          Let $f \in \Hd$ and let $z_0 \in {\Bbb C}^{n+1}$ be such that
          $\alpha\proj(z_0) < 1/32$. Let the sequence $(z_i)$ be defined
          by $z_{i+1} = N\proj(z_i)$. Then there is a zero $\zeta$
          of $f$ such that $\dproj(z_i, \zeta) \le 2^{-2^i -1}$
          }

{\theorem \label{qct:a2:proj}
          Let $f \in \Hd$, $z_0 \in {\Bbb C}^{n+1}$
          and assume that $\delta \ge 0$
          verifies ~:
          $$(\beta\proj(f,z_0) + \delta) \gamma\proj(f,z_0) < 1/32 ,$$
           and
          $\gamma \proj(f,z_0) \delta < 1/640$. Let the sequence $(z_i)$
          verify~:
          $$
          { \norm{z_{i+1} - N\proj(f,z_i)} \over \norm{z_i} }
          \le
          \delta
          $$
          \par
          Then there is a zero $\zeta$ of $f$ such that~:
          $$
          \dproj(z_i, \zeta)
          \le
          \max \left( 2^{-2^i -1} , 10 \delta \right)
          $$
          }

\paragraph {Pseudo Newton operator}
   If we make~:
   $$
   V(x) = x + \ker Df(x) ^\bot
   $$
   \par 
   we obtain the pseudo-Newton operator~:
   $$
   N\pseu (x) = x - Df(x)^{\dagger} f(x)
   $$\glossary{$N\pseu$&Pseudo-Newton operator}
   \par
   where $A^\dagger$ is the Moore-Penrose pseudo-inverse of $A$,
   defined by~:
   $$
   A^\dagger = {A_{|(ker A)^\bot}}^{-1}
   $$\glossary{$A^{\dagger}$&Moore-Penrose pseudo-inverse of matrix $A$}
   \par
   This notation refers to the case $\rank Df(x) = n$. In the case
   $\rank Df(x) < n$, the operator $N\pseu$ is not defined.
   \par
   An equivalent definition in our case is the following~: In the particular
   case the matrix to invert is diagonal, we set~: 
   $$
   \left[
       \begin {array}{ccccc}
         \lambda_1 \\
         & \lambda_2 \\
         && \cdots \\
         &&& \lambda_n & 0 \\
       \end {array}
   \right] ^ \dagger
   =
   \left[
       \begin {array}{ccccc}
         {\lambda_1} ^{-1} \\
         & {\lambda_2} ^{-1}\\
	 && \cdots \\
         &&& {\lambda_n} ^{-1} & 0\\
       \end {array}
   \right] 
   $$
   \par
   Then we extend this definition to all matrices
   of rank $n$ by
   setting, for any $U$, $V$ unitary:
   $$
   (U \Lambda V)^\dagger = V\ctrans \Lambda^\dagger U\ctrans
   $$

   A very important property of the pseudo-inverse of
   $A : {\Bbb C}^{n+1} \rightarrow {\Bbb C}^n$ is that
   $A^\dagger y$ is the vector of minimal norm in the linear
   space $A^{-1} y$.
   Hence,
   $$
   \norm { A ^ \dagger } = \min \norm { {A_{|V}}^{-1}} 
   $$
   \par
    when $V$ ranges over all hyperplanes through the origin. This 
   Newton operator 
   was suggested by Allgower and Georg \cite{ALLGOWER}.
   We will prove the Theorems~:

{\theorem \label{qct:a1:pseu}
          Let $f \in \Hd$ and let $z_0 \in {\Bbb C}^{n+1}$ be such that
          $\alpha\pseu(z_0) < 1/8$. Let the sequence $(z_i)$ be defined
          by $z_{i+1} = N\pseu(z_i)$. Then there is a zero $\zeta$
          of $f$ such that $\dproj(z_i, \zeta) \le 2^{-2^i -1}$
          }

{\theorem \label{qct:a2:pseu}
          Let $f \in \Hd$, $z_0 \in {\Bbb C}^{n+1}$
          and let $\delta \ge 0$
          verify ~: $(\beta\pseu(f,z_0) + \delta) \gamma\pseu(f,z_0) < 1/16$,
           and
          $\gamma\pseu(f,z_0) \delta < 1/384$. Let the sequence $(z_i)$
          verify~:
          $$
          { \norm{z_{i+1} - N\pseu(f,z_i)} \over \norm{z_i} }
          \le
          \delta
          $$
          \par
          Then there is a zero $\zeta$ of $f$ such that~:
          $$
          \dproj(z_i, \zeta)
          \le
          \max \left( 2^{-2^i -1} , 6 \delta \right)
          $$
          }



\paragraph {Path-following and conditioning~:}


    The robustness results in \cite{BEZI} come out naturally in
    the generalized case. We can define some more invariants 
    associated to a generalized Newton operator~:
    \begin{align*}
    \mu(f,x) 
    &=
    \max
    \left\{
      1,
      \knorm{ f } \ \norm{ \DfI{x}{x} \diag(\sqrt{d_i} \|x\|^{d_i-1})} 
    \right\}
    \\
    \eta(f,x)
    &=
    {
    \norm{ \diag({d_i}^{-1} \norm{x}^{-d_i}) f(x)} 
    \over
    \knorm{ f} 
    }
    \end{align*}\glossary{$\mu(f,x)$&Condition number of $f$
    at $x$}\glossary{$\eta(f,x)$&A corrected norm of $f(x)$}
    \par
    Invariants $\mu$ and $\eta$ are invariants under unitary transformations
    and under scalings of the form $(f,x) \mapsto (af,bx)$, 
    $a,b \in {\Bbb C}_\star$. The following estimates relate $\mu$ and
    $\eta$ to $\beta$ and $\gamma$~:
    \begin{align*}
    \beta(f,x) &\le \mu(f,x) \eta(f,x)
    \\
    \gamma(f,x)
    &\le
    {\mu(f,x) D^{3/2} \over 2}
    \end{align*}

    The first estimate is obvious. The second one follows from
    the same proof as in Shub and Smale \cite{BEZI}, III-1 and 
    (in the case $\gamma=1$)
    from the fact $1 \le D^{3/2}  / 2$ when $D \ge 2$.

    \par
    Also, as in ~\cite{BEZI}, the following estimates are true~:
{\lemma \label {lem:etamu}
    \begin{align*}
    \eta(g,\zeta) &\le \dproj (f,g) + \eta(f,\zeta)
    \\
    \mu(g,\zeta)
    &\le
    { \mu(f,\zeta) (1 + \dproj(f,g))
      \over
      1 - \sqrt{D} \dproj(f,g) \mu(f,\zeta)
    }
    \end{align*}
    }
    \medskip
    \par
    The number of steps and precision necessary for following
    a path $(f_t,\zeta _t)$ will depend on the following Theorems,
    that are modified versions of Theorem 3 in \cite{BEZI}, I-3~:

{\theorem \label{rob:aff} 
	  There are $\bar \alpha = 0.02$, $\bar u = 0.05$ such that, if
	  $\bar \gamma \ge 1$ and~:
          \begin{align*}
          \eta\aff(f,\zeta) \mu\aff(f,\zeta)
                 &\le {\bar \alpha \over \bar \gamma}
          \\
          \dproj(x,\zeta) &\le {\bar u \over \bar \gamma}
          \\
          \gamma\aff(f,\zeta) &\le \bar \gamma
          \end{align*}
          \par
	  Then setting $x'=N\aff(f,x)$, 
	  and $\zeta'$ the zero associated to $x'$, we get~:
	  $$
	  \dproj(x',\zeta ') \le {\bar u \over 2 \bar \gamma}
          $$
	  }

{\theorem \label{rob:proj} 
	  There are $\bar \alpha = 0.01$, $\bar u = 0.005$ such that, if
	  $\bar \gamma \ge 1$ and~:
          \begin{align*}
          \eta\proj(f,\zeta) \mu\proj(f,\zeta)
          &\le {\bar \alpha \over \bar \gamma}
          \\
          \dproj(x,\zeta) &\le {\bar u \over \bar \gamma}
          \\
          \gamma\proj(f,\zeta) &\le \bar \gamma
          \end{align*}
	  \par 
	  Then setting $x'=N\proj(f,x)$, 
	  and $\zeta'$ the zero associated to $x'$, we get~:
	  $$
	  \dproj(x',\zeta ') \le {\bar u \over 2 \bar \gamma}
          $$
	  }

{\theorem \label{rob:pseu} 
	  There are $\bar \alpha = 0.02$, $\bar u = 0.05$ such that, if
	  $\bar \gamma \ge 1$ and~:
          \begin{align*}
          \eta\pseu (f,\zeta) \mu\pseu(f,\zeta) &\le
            {\bar \alpha \over \bar \gamma}
          \\
          \dproj(x,\zeta) &\le {\bar u \over \bar \gamma}
          \\
          \gamma\pseu(f,\zeta) &\le \bar \gamma
          \end{align*}
          \par
	  Then setting $x'=N\pseu(f,x)$, 
	  and $\zeta'$ the zero associated to $x'$, we get~:
	  $$
	  \dproj(x',\zeta ') \le {\bar u \over 2 \bar \gamma}
          $$
	  }

     It is immediate that~:
 
{\corollary \label{rob:cor}
          In each of the three cases $N = N\aff, N\proj, N\pseu$, 
	  there are $\bar \alpha$, $\bar u$ such that, if
	  $\bar \gamma \ge 1$ and~:
          \begin{align*}
          \eta(f,\zeta) \mu(f,\zeta) &\le {\bar \alpha \over \bar \gamma}
          \\
          \dproj(x,\zeta) &\le {\bar u \over \bar \gamma}
          \\
          \gamma(f,\zeta) &\le \bar \gamma
          \\
          \delta &\le {\bar u \over 2 \bar \gamma}
          \end{align*}
          \par
          Then setting $x'$ such that ${\norm{x' - N(f,x)} \over \norm{x}}
          \le \delta$, 
	  and if $\zeta'$ is the zero associated to $x'$, we get~:
	  $$
          \dproj(x',\zeta ') \le {\bar u \over \bar \gamma}
          $$
	  }

     A generalization of the Main Theorem of Shub and Smale in~
     \cite{BEZI} for approximate Newton iteration follows~:

{\theorem \label{th:main}
          Assume that $N = N\aff$, $N\proj$ or $N\pseu$. Let $\bar \alpha$
          and $\bar u$ be given by Theorems \ref{rob:aff}, \ref{rob:proj}
          or \ref{rob:pseu}, respectively.
          \par 
          Let $(f_t, \zeta_t)$ be a path in $\Hd \times {\Bbb C}^{n+1}$,
          so that $f_t(\zeta_t) = 0$. Let $\mu \ge \max(\mu(f_t,\zeta_t))$ be
          finite.
          Let $\bar \gamma \ge {2 \over 3} D^{3/2} \mu$. Let $z_0$ verify
          $\dproj(z_0, \zeta_0) \le {\bar u \over \bar \gamma}$. Let $(t_i)$
          be a sequence such that $\dproj(f_{t_i},f_{t_{i+1}}) \le \Delta
          \le {3 \over 8} {\bar \alpha \over \mu \bar \gamma}$. 
          Let $(z_i)$ verify~:
          $${\norm{z_{i+1} - N(f_{t_{i+1}}, z_i)}
          \over \norm{z_i}} \le \delta \le {\bar u \over 2 \bar
          \gamma}$$
          \par
          Then $\dproj(z_i, \zeta_{t_i}) \le {\bar u \over \bar \gamma}$, and
          hence $\alpha(f_{t_i},z_i)  \le \bar \alpha$.
          }

     In particular, if the length of the path $f_t$ is bounded by $L$,
     then ${16 \over 9} {L \mu ^2 D^{3/2} \over \bar \alpha}$ steps
     of approximate Newton iteration with error less than 
     ${9 \over 4} {\bar u \over D^{3/2} \bar \mu}$ suffices to 
     {\em follow} the path $(f_t, \zeta_t)$ and obtain a zero of $f_1$.
\ignore{
     The actual construction of sequence $z_i$ will be the subject
     of Chapter \ref{ch:newton}.
}



\section {Estimates on $\beta$}
\label{sec:beta}
Let the generalized Newton operator $N$
be one of $N\aff$, $N\proj$ or $N\pseu$. Let $z_i$ be a sequence
of points satisfying~:
$$
{ \norm{ z_{i+1} - N(f,z_i) } \over \norm{z_i} } \le \delta
$$
\par
for some $\delta \ge 0$. In the affine case $N = N\aff$, assume furthermore
that $V(z_i) = V(z_{i+1})$. This follows from the hypothesis
of Theorem~ \ref{qct:a2:aff} according to which the first coordinates
of all the $z_i$ are equal.
\par
The case $\delta = 0$ represents the 
exact iteration $z_{i+1}=N(f,z_i)$. For notational convenience,
we will write~:
\begin{align*}
\beta_i &= \beta(f,z_i)   \\
\gamma_i &= \gamma(f,z_i)  \\
\alpha_i &= \alpha(f,z_i) = \beta_i \gamma_i  \\
u_i &= { \norm{z_{i+1} - z_i } \over \norm{z_i} } \gamma_i \\
\tilde \alpha_i &= (\beta_i + \delta) \gamma_i \\
\psi(u) &= 1 + 2u^2 - 4u
\end{align*}
\medskip
\par
The following bounds are obvious, since $\gamma_i \ge 1$~:
\begin{equation}
\label{eq:e1}
{ \norm{z_{i+1} } \over \norm{z_i}} \le 1 + u_i
\end{equation}
\begin{equation}
\label{eq:e2}
{ \norm{z_i} \over \norm{z_{i+1}}} \le {1 \over 1 - u_i}
\end{equation}
\medskip
\par
Let $p(z)$ be the projection of ${\Bbb C}^{n+1}$ into
the $n$-plane $V(z)$, in the direction of $\ker Df(z)$.
(We assume that $Df(z)$ has rank $n$).
Let $p(z',z)$ be the restriction of $p(z)$ to $V(z')$.
Let $\kappa$ be a constant, $\kappa \ge \norm{p(z_i,z_{i+1})}$ for all $i$.
In the cases $N = N\proj$ and $N = N\pseu$, we require the stronger
condition $\kappa \ge \norm{p(z_{i+1})}$.
\par
If we are using $N = N\aff$, we have $V(z_i) = V(z_{i+1})$, 
hence can take $\kappa = 1$.
\par
If we are using $N = N\pseu$, then by construction we have
that $V(z_i) \perp \ker Df(z_i)$. It follows that we can
also take $\kappa = 1$. Later on, we will bound $\kappa$ in
the case $N = N\proj$.
\par
The idea of the proof
of the quadratic convergence theorem will be to show that,
under certain circumstances, $\tilde \alpha _{i+1} \le
4 {\tilde \alpha_i}^{\ 2}$
\par
We start with~:
{ \lemma \label{lem:beta}
         Under the conditions above,
         $$
         \beta_{i+1} 
           - \kappa^2 
             { \norm{z_i} \over \norm{z_{i+1}}}
             { (1 - u_i)^2 \over \psi(u_i)} \delta
         \le
         \kappa 
             { \norm{z_i} \over \norm{z_{i+1}}}
             { 1 - u_i \over \psi(u_i)} 
             \gamma_i
             (\beta_i + \delta)^2
         $$
         }

\paragraph{Proof of Lemma \ref{lem:beta}}

In order to prove Lemma \ref{lem:beta}, we break $\beta_{i+1}$
as follows~:
\begin {align}
\label{eq:beta:break}
\beta_{i+1}
&=
{1 \over \norm{z_{i+1}}}
\norm{\DfI{z_{i+1}}{z_{i+1}} f(z_{i+1})}\\
&\le
{1 \over \norm{z_{i+1}}}
\norm{\DfI{z_{i+1}}{z_{i+1}} \Df{z_{i+1}}{z_{i}} } \notag \\
& \ \norm{\DfI{z_{i+1}}{z_{i}} \Df{z_{i}}{z_{i}} }
\norm{\DfI{z_{i}}{z_{i}} f(z_{i+1})} \notag
\end {align}

\paragraph{Part 1~:} $ \DfI{z_{i+1}}{z_{i+1}} \Df{z_{i+1}}{z_{i}}$
is the projection $p(z_{i},z_{i+1})$ from $V(z_i)$ into $V(z_{i+1})$
in the direction $\ker Df(z_{i+1})$. It follows that its norm is
bounded by $\kappa$~:
\begin{equation}
\label{eq:beta:part1}
\norm{\DfI{z_{i+1}}{z_{i+1}} \Df{z_{i+1}}{z_{i}} }
\le \kappa 
\end{equation}

\paragraph{Part 2~:} We first write~:
$$
\DfI{z_i}{z_i} \Df{z_{i+1}}{z_i} 
=
I
+
\sum_{k \ge 2}
k 
 {
 \DfI{z_i}{z_i} D^kf(z_i) \over k! 
 }
 (z_{i+1} - z_i)^{k-1}
$$
\par
We obtain the inequality~:
$$
\norm {
       \DfI{z_i}{z_i} \Df{z_{i+1}}{z_i} 
       - I
      }
\le
\sum_{k \ge 2}
k {u_i}^{k-1}
\le
{1 \over (1 - u_i)^2 } - 1
$$
\par
It follows that~:
\begin{equation}
\label{eq:beta:part2}
\norm { 
      \DfI{z_{i+1}}{z_i} \Df{z_i}{z_i} 
      }
\le
{1 \over 2 - {1 \over (1 - u_i)^2 } } 
\le
{ (1 - u_i)^2 \over \psi(u_i) }
\end{equation}

\paragraph{Part 3~:} We expand~:
\begin{multline*}
\DfI{z_i}{z_i} f(z_{i+1}) 
=
\DfI{z_i}{z_i} f(z_i)
+
\DfI{z_i}{z_i} Df(z_i) (z_{i+1} - z_i)
\\
+ \sum_{k \ge 2}
{\DfI{z_i}{z_i} D^kf(z_i) \over k!}
(z_{i+1} - z_i)^k
\end{multline*}
\par
Since (by hypothesis)
$z_{i+1}$ cannot be at distance more than $\norm{z_i} \delta$
of $z_i - \DfI{z_i}{z_i} f(z_i)$, the projection of $z_{i+1}$ into
$V(z_i)$ cannot be at distance more than $\kappa \norm{z_i} \delta$ of
the projection of $z_i - \DfI{z_i}{z_i} f(z_i)$. Thus~:
$$
\norm {
      \DfI{z_i}{z_i} f(z_i)
      +
      \DfI{z_i}{z_i} Df(z_i) (z_{i+1} - z_i)
      }
\le
\kappa \delta \norm{z_i}
$$
\par
For the terms of order $\ge 2$, we have~:
\begin{align*}
\norm
{
\sum_{k \ge 2}
{\DfI{z_i}{z_i} D^kf(z_i) \over k!}
(z_{i+1} - z_i)^k
}&\le
\sum_{k \ge 2} 
\left(
 { \norm{z_{i+1} - z_i}  \over \norm{z_i}}
 \gamma_i  
\right) ^{k-1}
\norm{z_{i+1} - z_i}
\\
&\le
{u_i \over 1 - u_i} 
\norm{z_{i+1} - z_i}
\\
&\le
{u_i \over 1 - u_i} 
(\beta_i + \delta) \norm{z_i}
\end{align*}
\par
Hence, we obtain~: 
\begin{equation}
\label{eq:beta:part3}
\norm { \DfI{z_i}{z_i} f(z_{i+1}) }
\le
{u_i \over 1 - u_i} 
(\beta_i + \delta) \norm{z_i}
+
\kappa \delta \norm{z_i}
\end{equation} 

\paragraph{Putting all together~:} 

Inserting bounds  (\ref{eq:beta:part1}),  (\ref{eq:beta:part2}) and 
(\ref{eq:beta:part3}) into inequality (\ref{eq:beta:break}), we
get~:
$$
\beta_{i+1}
\le
{ \norm{z_i} \over \norm{z_{i+1}} }
\kappa
{1 - u_i \over \psi(u_i)}
\gamma_i
(\beta_i + \delta)^2
+
{ \norm{z_i} \over \norm{z_{i+1}} }
\kappa^2
{(1 - u_i)^2 \over \psi(u_i)}
\delta
$$
\par
Hence,
$$
\beta_{i+1}
-
\left(
{ \norm{z_i} \over \norm{z_{i+1}} }
\kappa^2
{(1 - u_i)^2 \over \psi(u_i)}
\right)
\delta
\le
{ \norm{z_i} \over \norm{z_{i+1}} }
\kappa
{1 - u_i \over \psi(u_i)}
\gamma_i
(\beta_i + \delta)^2
$$ 
\par
This proves Lemma \ref{lem:beta}. 

\section {Estimates on $\gamma$}
\label{sec:gamma}


{ \lemma \label{lem:gamma}
         Let $z_i \in {\Bbb C^{n+1}}$ verify $\norm{p(z_i,z_{i+1})} \le \kappa$,
         let $\gamma_i = \gamma(f,z_i)$ and $u_i = { \norm{z_{i+1}-z_i} \over
         \norm{z_i} } \gamma_i$. Then we have~:
         $$
         \gamma_{i+1} \le \kappa { \norm{z_{i+1}} \over \norm{z_i}}
         {1 \over \psi(u_i) (1 - u_i) } \gamma_i
         $$
         }

Note that in the statement above, we do not require 
${ \norm{z_{i+1} - N(z_i) } \over \norm{z_i}} \le \delta$.

\paragraph{Proof of Lemma \ref{lem:gamma}~:} We first estimate
$\norm{ { \DfI{z_{i+1}}{z_{i+1}} D^kf(z_{i+1}) \over k! }}$.
\par
According to the
estimates (\ref{eq:beta:part1}) and (\ref{eq:beta:part2}), we
have~:
$$
\norm{ { \DfI{z_{i+1}}{z_{i+1}} D^kf(z_{i+1}) \over k! } } 
\le
\kappa {(1 - u_i)^2 \over \psi(u_i) }
\norm{ { \DfI{z_{i}}{z_{i}} D^kf(z_{i+1}) \over k!} }
$$
\par
Moreover, 
\begin {align*}
\norm{ { \DfI{z_{i}}{z_{i}} D^kf(z_{i+1}) \over k!} }
&\le
\sum_{l \ge 0}
\norm{ { \DfI{z_{i}}{z_{i}} D^{k+l}f(z_{i}) \over k!l! }}
\norm{ z_{i+1} - z_i}^l
\\
&\le
\sum_{l \ge 0} { k+l ! (\gamma_i)^{k-1} {u_i}^l \over k! l! \norm{z_i}^{k-1} } 
\\
&\le
{ {\gamma_i}^{k-1} \over \norm{z_i}^{k-1} }
\sum_{l \ge 0} { k+l! {u_i}^l \over k! l! } 
\\
&\le
{ {\gamma_i}^{k-1} 
  \over
 (1 - u_i)^{k+1}
 \norm{z_i}^{k-1}
}
\end{align*}
\par
Thus,
$$ 
\norm{ { \DfI{z_{i+1}}{z_{i+1}} D^kf(z_{i+1}) \over k! } } 
\le
\kappa { {\gamma_i}^{k-1} \over \psi(u_i) (1 - u_i)^{k-1} \norm{z_i}^{k-1}}
$$
\par
Using $\psi(u_i) \le 1$, $\kappa \ge 1$
 and extracting the $(k-1)$-th root, we obtain~:
$$
\gamma_{i+1} \le \kappa { \norm{z_{i+1}} \over \norm{z_i}}
{1 \over \psi(u_i) (1 - u_i) } \gamma_i
$$
\par
This proves Lemma \ref{lem:gamma}.


\section {Estimates on $\alpha$}
\label{sec:alpha}
In this section, we prove Theorems \ref{qct:a1:aff}, \ref{qct:a2:aff},
\ref{qct:a1:pseu} and \ref{qct:a2:pseu}.
\par
Combining Lemma \ref{lem:beta}, equation ~(\ref{eq:e2})
and Lemma ~\ref{lem:gamma}, we obtain the
following result~:
{ \lemma \label{lem:alpha}
         Under the hypotheses and notations of Lemma \ref{lem:beta},
         $$
         \left( \beta_{i+1} 
                - \kappa^2 {1 - u_i \over \psi(u_i)} \delta
         \right)
         \gamma_{i+1}
         \le
         \kappa^2 {1 \over \psi(u_i)^2}
         (\beta_i + \delta)^2
         {\gamma_i}^2
         $$
         }

\paragraph {Proof of theorems \ref{qct:a1:aff} and \ref{qct:a1:pseu}~:}
If we make $\delta = 0$, Lemma~\ref{lem:alpha} reads:
\begin{equation}
\label{eq:alpha:shrinks}
\alpha_{i+1} \le { \kappa ^2 \over \psi(u_i)^2 } {\alpha_i}^2
\end{equation}

Assume that we are in the hypotheses of theorems \ref{qct:a1:aff} or
\ref{qct:a1:pseu}. Then $\kappa = 1$. 
Also, $u_i = \alpha_i$. Assume by induction that $\alpha_i \le 1/8$,
we obtain $\psi(u_i) > 0.531 > 1/2$ and equation~(\ref{eq:alpha:shrinks})
implies~:
$$
\alpha_{i+1} \le 4 {\alpha_i}^2 \le 1/16 \le 1/8 
$$
\par
By induction, $\alpha _i \le 2^{-2^i - 2}$ and hence~:
$$
\beta_i \le \alpha_i \le 2^{ -2^i - 2}
$$
$$
\dproj(z_i,\zeta) \le \sum_{j \ge i} \beta_i \le 2 \alpha_i \le 2^{-2^i-1}
$$
\par
This proves theorems \ref{qct:a1:aff} and \ref{qct:a1:pseu}. 
\medskip
\par

Lemma \ref{lem:alpha} allows us to prove the following statement~:

{ \lemma \label{lem:alpha2}
         Assuming the hypotheses of Lemma \ref{lem:beta},
         and using the same notation,
         let ${ \norm{z_{i+1} - N(z_i)} \over \norm{z_i}} \le \delta$,
         $\delta > 0$,
         $(\beta_0 + \delta) \gamma_0 \le 1/8$, and suppose that for
         $\delta \ne 0$, $0 \le i < j$ we have~:
         \begin {equation}
         \label{eq:bigbeta} 
        \beta_{i+1} \ge 
          {
          1 + {\kappa^2 (1 - u_i) \over \psi(u_i)} 
          \over
          {4 \psi(u_i)^2 \over \kappa^2 } - 1 
          }
        \delta   
         \end{equation}
         \par where the denominator is positive.
         \par
         Then $(\beta_{i+1} + \delta) \gamma_{i+1} \le 
         4 ((\beta_i + \delta) \gamma_i)^2$, and hence
         $ (\beta_j + \delta) \gamma_j \le 2 ^ {-2^j - 2} $.
         \par
         This also implies $\beta_j \le 2^{-2^j - 2}$, and
         $\dproj(z_j, \zeta) \le 2^{-2^j -1}$, where $\zeta$ is a zero
         of $f$.
         } 


 
\paragraph {Proof of Lemma \ref{lem:alpha2}~:}
Equation (\ref{eq:bigbeta}) is the same as~:
$$
\beta_{i+1} + \delta 
\le
{4 \psi(u_i)^2 \over \kappa^2}
\left(
 \beta_{i+1} - \kappa^2 {1 - u_i \over \psi(u_i)} \delta
\right)
$$
\par
Plugging this formula in Lemma \ref{lem:alpha}, we obtain~:
$$
( \beta_{i+1} + \delta ) \gamma_{i+1} 
\le
4 ((\beta_i + \delta) \gamma_i)^2
$$
\par
This proves lemma \ref{lem:alpha2}.
\medskip
\par
Lemma \ref{lem:alpha2} means that in the conditions of Theorems 
\ref{qct:a2:aff} , \ref{qct:a2:proj} and \ref{qct:a2:pseu}, as long
as $\delta$ is {\em small enough} relatively to $\beta$, we have
quadratic convergence. We still have to prove that as soon as we are
no more in the conditions of Lemma \ref{lem:alpha2}, the sequence
$z_i$ gets {\em trapped} in a disk of radius $6 \delta$ over $\zeta$.

{\lemma \label{lem:trapped}
        If equation (\ref{eq:bigbeta}) is not true, and $u_i \le 1/16$,
        then $\beta_{i+1} \le {28 \over 15}\kappa^4 \delta$
        }

\paragraph{Proof of Lemma \ref{lem:trapped}~:}

$$
\beta_{i+1} 
  < 
  {
  1 + {\kappa^2 (1 - u_i) \over \psi(u_i)} 
  \over
  {4 \psi(u_i)^2 \over \kappa^2 } - 1 
  }
 \delta   
\le
{ 1 + {4 \over 3} \kappa^2 \over {9 \over 4 \kappa^2} - 1 } \delta
\le
{28 \over 15} \kappa^4 \delta
$$
 
{ \lemma \label{lem:D}
         Let $\zeta$ be a zero of $f$. 
         Let the disk $D$ of center $\zeta$ and radius $2 k \delta$ , 
             $k \ge 3$, verify for each $z \in D$
             the condition $\gamma(f,z) \le \Gamma$, 
             with $(k+1) \Gamma \delta < 0.1$. 
         Let $\beta(z_i) < k \delta$, $z_i \in D$. 
         Then $\beta(z_{i+1}) \le ({k \kappa \over 6} + 2 \kappa^2 )  \delta$.
         In particular, if $\kappa = 1$, $\beta(z_{i+1}) \le k \delta$ 
             and $z_{i+1} \in D$.
         }

\paragraph{Proof of Lemma \ref{lem:D}~:} According to Lemma \ref{lem:beta},

$$
\beta_{i+1} 
\le
\kappa
{ \norm{z_i} \over \norm{z_{i+1}} }
{1 - u_i \over \psi(u_i)}
\gamma_i
(\beta_i + \delta)^2
+
\kappa^2
{ \norm{z_i} \over \norm{z_{i+1}} }
{(1 - u_i)^2 \over \psi(u_i)}
\delta
$$
\par
Using equation (\ref{eq:e2}),
\begin{align*}
\beta_{i+1}
&\le
{\kappa \over \psi(u_i)} \Gamma ((k+1) \delta)^2
+
{\kappa ^2 (1 - u_i) \over \psi(u_i)} \delta
\\
&\le
\left(
  {\kappa (k+1)^2 \over \psi( (k+1) \delta \Gamma ) }
  \Gamma \delta
  +
  {\kappa^2 \over \psi( (k+1)\Gamma \delta)}
\right)
\delta
\\
&\le
{ \kappa (k+1)^2 \Gamma \delta + \kappa^2 
  \over
  \psi((k+1) \Gamma \delta)
  }
  \delta
\end{align*}
\par
Using $(k+1) \Gamma \delta < 0.1$, we get $\psi( (k+1) \Gamma \delta) >0.6$,
hence~:
$$
\beta_{i+1} \le {\kappa(k+1) 0.1 + \kappa^2 \over 0.6} \delta
\le
\left( {1 \over 6} \kappa k + {11 \over 6} \kappa^2 \right) \delta
\le
\left( {k \kappa \over 6} + 2 \kappa^2 \right) \delta
$$  
\par
This proves lemma \ref{lem:D}.
\medskip
\par
{ \lemma \label{lem:growth}
         Let $u={ \norm{z - z_i} \over \norm{z_i} } \gamma_i \le {1 \over 16}$.
         Then $\gamma(z) \le 1.52 \kappa \gamma_i$.
         }

For the proof, we use Lemma \ref{lem:gamma} and equation~(\ref{eq:e1}),
according to which~:
$$
\gamma(z) \le { \kappa(1 + u) \over \psi(u) (1 - u) } \gamma_i
$$
\par
If $u \le 1/16$, then $\psi(u) > 3/4$ and~: 
$$
\gamma(z) 
\le
{4 \times 17 \over 3 \times 15} \kappa \gamma_i
\le
1.52 \kappa \gamma_i 
$$
\medskip
\par
\paragraph{Proof of theorems \ref{qct:a2:aff} and \ref{qct:a2:pseu}~:}

Assume the hypotheses of Theorem \ref{qct:a2:aff}
(resp. of Theorem \ref{qct:a2:pseu}).
\par
Let $k = 3$. 
\par
Let us fix $j$ such that $\beta_i \ge k \delta$
for $i \le j$ and $\beta_{j+1} \le k \delta$. Let $D$ be the disk 
of radius $2 k \delta$ over $\zeta$.
\par
Assuming that $\alpha_i < {1 \over 8}$, Lemma ~\ref{lem:beta}
implies that $\dproj(z_i, \zeta) \le 2 \beta_i$. Indeed, by
applying Lemma ~\ref{lem:beta} to the {\em exact} Newton
iteration starting from $z_i$, one would obtain~:
\begin {equation}
\label{eq:star}
\beta_{i+1} \le {\kappa \over \psi(\alpha_i)} \alpha_i \beta_i
< {\beta_i \over 2}
\end{equation}
\par
Therefore, $\zeta$ is at distance at most $2 \beta_j$
of $z_j$, and
all points in $D$ are within distance $4 \beta_j$ of $z_j$.
We have to consider several cases~:
\medskip
\par
General case : $j \ge 1$. In that case,
$\alpha_j \le 4 {\alpha_0} ^2 \le 1/64$. If $z \in D$ is scaled properly,
${ \norm{z - z_j} \over \norm{z_j}} \gamma_j \le 4 \alpha_j \le 1/16$.
Therefore, we can apply Lemma \ref{lem:growth} and obtain $\gamma(z) \le
1.52 \kappa \gamma_j$.
\par
We fix $\Gamma \le 2 \gamma_j$.
\par
We also have $(k+1) \Gamma \delta < 2{k+1 \over k} \alpha_j
\le 3 \alpha_j < 0.1$.
\par
Hence, we apply Lemma \ref{lem:D} by induction, and conclude
that $z_{j+1}, z_{j+2}, \dots$ belong to $D$.
\medskip
\par  
Special cases : $j = 0$ and $j$ does not exist (this means that
$\beta_0 < 3 \delta$). The case $j=0$ is the more difficult, so we
prove only this case. The proof of the other case is similar. 
\par
We claim that $\Gamma = 4 \gamma_0$ verifies   
$\max_D \gamma \le 2 \gamma_1 \le 4 \gamma_0 = \Gamma$. 
Indeed, $u_0 < 1/16$, hence by Lemma \ref{lem:growth},
$\gamma_1 \le 2 \gamma_0$. The distance from $z_1$ to any point
of $D$ is bounded by $4k \delta$ , 
and $4 k  \delta \gamma_1 \le 8 k \delta \gamma_0 < 1/16$.
We can use Lemma \ref{lem:growth} again, and conclude that
$\max_D \gamma(z) \le 2 \gamma_1 \le 4 \gamma_0$.
Thus, we can set $\Gamma = 4 \gamma_0$.
\par
In order to use Lemma \ref{lem:D}, we have to check that
$(k+1) \Gamma \delta < 0.1$. This amounts to check that
$4 (k+1) \gamma_0 \delta < 0.1$. This follows from the hypothesis  
on $\gamma_0 \delta$. Thus, we use Lemma \ref{lem:D} by induction,
and conclude that $z_{j+k} \in D$.
\par
\medskip
Theorems \ref{qct:a2:aff} and \ref{qct:a2:pseu} are now proved.
In order to prove Theorems \ref{qct:a1:proj} and \ref{qct:a2:proj}
we still need to be able to bound $\kappa$.
 

\section {Estimates on $\kappa$}
\label{sec:kappa}
We prove here Theorems \ref{qct:a1:proj} and \ref{qct:a2:proj}. Let
$z_i$ be a sequence such that~:
$$
{ \norm{z_{i+1} - N\proj(z_i) }
  \over
  \norm{z_i} }
\le \delta \ , \delta \ge 0
$$
\par
Assume that $\tilde \alpha\proj_i = (\beta\proj_i + \delta) \gamma\proj_i
\le \bar \alpha_0$, $\bar \alpha_0$ a constant no more than $1/32$.
\par
Since $\alpha\pseu(z_i) \le \alpha\proj(z_i) \le \tilde \alpha\proj(z_i)
\le \bar\alpha_0$, it follows from equation ~(\ref{eq:star}) that there
is a zero $\zeta$ at distance of $z_i$ no more than $2 \beta\pseu(z_i)  \le 
2 \bar \alpha_0 / \gamma\pseu(z_i) \le 1/16 \gamma\pseu(z_i)$. 

{\lemma \label{lem:kappa} In the conditions above,
        $$
        \norm{p(z_{i+1})}
        \le
        {1 \over \sqrt{1 - 
           \left(
             {  
              9.12  
              \bar\alpha_0
              \over
              \psi( 
               4.56 \bar\alpha_0
                  )
              }
            \right) ^2
             } } 
        $$ }

\paragraph{Proof of Lemma \ref{lem:kappa}~:}
Let us scale $\zeta$ so that $\norm{\zeta} = 1$. Also, we can scale
$z_i$ so that $z_i \in \zeta + \zeta^\perp$.
Let us choose $y \in \ker Df(z_{i+1})$. By similarity of
triangles,
$$\norm{p(z_{i+1})} = \sqrt{1 - \dproj(y,z_{i+1})^2}^{\ -1}$$
\par
We now estimate $\dproj(y, z_{i+1})$. We set~: 
$$
v = { \norm {z_{i+1} - \zeta} \over \norm{\zeta} } \gamma\pseu(\zeta)
$$

\par
We apply Lemma \ref{lem:growth} to obtain~:
$$
\gamma\pseu(\zeta) \le 1.52 \gamma\pseu(z_i) \le 1.52 \gamma\proj(z_i)
$$
\par
Also,
$$
{ \norm{z_{i+1} - \zeta } \over \norm{\zeta}}
\le
{ \norm{z_{i+1} - z_i } \over \norm{\zeta}}
+
{ \norm{z_i - \zeta } \over \norm{\zeta}}
\le
{ \norm{z_i} \over \norm{\zeta} } (\beta_i + \delta + 2 \beta_i)
\le
3 (\beta_i + \delta)
$$
\par
Hence,
$$
v = 
{ \norm{z_{i+1} - \zeta } \over \norm{\zeta}}
\gamma \pseu(\zeta)
\le
4.56 \bar \alpha_0
$$
\medskip
\par
We can scale $y$ so that we can write $y = \zeta + y^\perp$, 
$y^\perp \perp \zeta$, then
$\dproj(y,\zeta) \le \norm{y^\perp}$. By the choice of $y$,
$$
Df(z_{i+1}) y =
Df(z_{i+1}) (\zeta + y^\perp) = 0
$$
\par
Expanding $Df$ around $\zeta$, we obtain~:
$$
   Df(\zeta) (\zeta + y^\perp)
   +
   \sum_{k \ge 2}
      k
      \left(
         D^kf(\zeta)
         \over
         k!
      \right)
      (z_{i+1} - \zeta)^{k-1}
   \left(
     \zeta + y^\perp
   \right)
   = 0
$$
\par
Obviously, $Df \zeta = 0$ ; we apply $Df(z_{i+1})^\dagger$ to the
equation, and obtain~:
$$
   y^\perp
   +
   \sum_{k \ge 2}
      k
      \left(
         Df(\zeta)^\dagger
         D^kf(\zeta)
         \over
         k!
      \right)
      (z_{i+1} - \zeta)^{k-1}
   \left(
     \zeta + y^\perp
   \right)
   = 0
   $$
\par
Now, we have~:
\begin{align*}
\norm
{
   \sum_{k \ge 2}
      k
      \left\{
         Df(\zeta)^\dagger
         D^kf(\zeta)
         \over
         k!
      \right\}
      (z_{i+1} - \zeta)^{k-1}
}
&\le
\sum k \gamma(\zeta)^{k-1} (z_{i+1} - \zeta)^{k-1}
\\
&\le
\sum k v^{k-1}
\\
&\le
{1 \over (1-v)^2} -1
\end{align*}
\par
Thus,
$$
\dproj(y,\zeta) \le 
\norm{y^\perp} 
\le
{ {1 \over (1 - v)^2 } - 1 
  \over
  2 - { 1 \over (1 - v)^2 }
  }
\le
{2 - v \over \psi(v)}
v
\le
{2v \over \psi(v) }
$$

Putting all together,
$$
        \norm{p(z_{i+1})}
        \le
        \sqrt{1 - 
           \left(
             {  
              2 \times 
               4.56 \bar\alpha_0
              \over
              \psi( 
               4.56 \bar\alpha_0
                  )
             }  
           \right) ^2
             } ^{\ -1}
$$
\par
and Lemma \ref{lem:kappa} is proved.


\paragraph {Proof of Theorem \ref{qct:a1:proj}} We check
numerically (using Lemma \ref{lem:kappa})
that for $\bar \alpha_0 = 1/32$, we have
$\kappa \le 1.26$. 
\par
Also, ${\kappa^2 \over \psi(\bar \alpha_0)^2} \le 2.06 \le 4$,
so equation \ref{eq:alpha:shrinks} gives~:
$$
\alpha_{i+1} \le 4 {\alpha_i}^2 \le 1/32 
$$
\par
And this proves theorem \ref{qct:a1:proj}.

\paragraph {Proof of Theorem \ref{qct:a2:proj}~:}
Using $\kappa \le 1.2567$, Lemmas \ref{lem:trapped}, 
\ref{lem:D} and \ref{lem:growth} become :



{\lemma \label{lem:trapped:k}
        If equation (\ref{eq:bigbeta}) is not true, and $u_i \le 1/16$,
        then $\beta_{i+1} \le 4.66 \delta < 5 \delta$
        }
{ \lemma \label{lem:D:k}
         Let $\zeta$ be a zero of $f$.
         Let the disk $D$ of center $\zeta$ and radius $2 k \delta$ ,
             $k \ge 4$, verify for each $z \in D$
             the condition $\gamma(f,z) \le \Gamma$,
             with $(k+1) \Gamma \delta < 0.1$.
         Let $\beta(z_i) < k \delta$, $z_i \in D$.
         Then $\beta(z_{i+1}) \le ({k \kappa \over 6} + 2 \kappa^2 )  \delta$.
         In particular, if $\kappa \le 1.2567$, then
         $\beta(z_{i+1}) \le k \delta$
         and $z_{i+1} \in D$.
         }
{ \lemma \label{lem:growth:k}
         Let $u={ \norm{z - z_i} \over \norm{z_i} } \gamma_i \le {1 \over 16}$.
         Then $\gamma(z) \le 1.52 \kappa \gamma_i\le 1.92 < 2$.
         }
\medskip
\par
At this time, we set $k=5$. 
The same proof of Theorems   \ref{qct:a2:aff} and \ref{qct:a2:pseu}
applies word by word to prove Theorem \ref{qct:a2:proj}.   


\section {Proof of the Robustness results}
\label{sec:robust}
\paragraph {Proof of Lemma \ref{lem:etamu}~:}

    The first estimate is easy. The second follows from~:

    \begin{align*}
    \mu(g,\zeta) &= \mu(\lambda g, \zeta)
    \\
    &=
    \knorm{ \lambda g}
    \norm{
    \left(
       \diag( {d_i}^{-1/2} \norm{ \zeta }^{1-d_i} )
       D(\lambda g(\zeta))_{|V_g(\zeta)}
    \right) ^{-1}
    }
    \\
    &\le
    \knorm{ \lambda g }
    \norm{
    \left(
       \diag( {d_i}^{-1/2} \norm{ \zeta }^{1-d_i} )
       D(\lambda g(\zeta))_{|V_f(\zeta)}
    \right) ^{-1}
    }
    \end{align*}
Then we proceed as in \cite{BEZI}, using Lemma 5 of III-1.

\paragraph{Bounds on $\alpha(f,x)$~:}
   Let us put ourselves in the conditions of Theorems
   \ref{rob:aff} , \ref{rob:proj} or \ref{rob:pseu}.
   \par
   By hypothesis, $ { \norm{x - \zeta} \over \norm{\zeta}} \le \bar u$.
   Also, we assume that $\bar u < 1/16$.
   \par
   The following estimate is very similar to Lemma \ref{lem:beta}~:
{\lemma \label{lem:beta:zeta} 
   $$
   \beta(f,x) \le
   \kappa (1 - \bar u)
   {
   (1 - \bar u ) \beta(f,\zeta) + \kappa \dproj(x,\zeta)
   \over
   \psi(\bar u)
   }
   {
   \norm{\zeta} \over \norm{x}
   }
   $$
   }

\paragraph{Proof of Lemma \ref{lem:beta:zeta}~:} Using the fact that
$ { \norm{x - \zeta} \over \norm{\zeta} } \gamma(\zeta) \le \bar u$,
we can write, using Parts 1 and 2 of the proof of Lemma~\ref{lem:beta}~:
$$
\beta(f,x) \le 
\kappa
{(1 - \bar u)^2 \over \psi(\bar u)}
{1 \over \norm{x}}
\norm{ \DfI{\zeta}{\zeta} f(x) }
$$
\par
Expanding the last term into its Taylor series, we obtain~:
\begin{align*}
\norm{ \DfI{\zeta}{\zeta} f(x) }
&\le
\norm{ \DfI{\zeta}{\zeta} f(\zeta) 
+
\DfI{\zeta}{\zeta} Df(\zeta) (x - \zeta)}
\\
& \ +
\norm{ \sum_{k \ge 2} {\DfI{\zeta}{\zeta} D^kf(\zeta) \over k!} 
            (x - \zeta)^{k-1} }
\\
&\le
\norm{\zeta} (\beta (f,\zeta)  + \kappa \dproj(x,\zeta) )  
+
\norm{\zeta} {\bar u \over 1 - \bar u} \dproj(x,\zeta)
\end{align*}
\par
Therefore,
\begin{align*}
\beta(f,x) 
&\le
\kappa
{ \norm{\zeta} \over \norm{x} }
(1 - \bar u)
{ (1 - \bar u) \beta (f,\zeta) + ((1 - \bar u) \kappa + \bar u) \dproj(x,\zeta)
 \over \psi (\bar u) }
\\
&\le
\kappa
{ \norm{\zeta} \over \norm{x} }
(1 - \bar u)
{ (1 - \bar u) \beta (f,\zeta) + \kappa \dproj(x,\zeta)
 \over \psi (\bar u) }
\end{align*}
\par
This proves Lemma \ref{lem:beta:zeta}
\medskip
   \par
   Lemma \ref{lem:gamma} gives~:
   $$   
   \gamma(f,x) 
   \le
   \kappa
   { \gamma(f,\zeta) \over \psi(\bar u) (1 - \bar u) }
   {\norm{x} \over \norm{\zeta}}
   $$
   \par
   Using Lemma \ref{lem:beta:zeta} together with the previous estimate, we
   obtain~:
{\lemma \label{lem:alpha:x}
   $$
   \alpha(f,x) \le 
   \kappa ^2 
   {
   (1 - \bar u) \alpha(f,\zeta) + \kappa \bar u
   \over
   \psi(\bar u) ^2
   } $$
   }
   \par
   Now we use Lemma \ref{lem:beta} and obtain~:
{\lemma \label{lem:beta:x}
   $$
   \beta(f,x')
   \le
   \kappa
   { \norm{x} \over \norm{x'} }
   {1 - \alpha(f,x) \over \psi(\alpha(f,x))}
   \alpha(f,x) \beta(f,x)
   $$
   }

\paragraph{Proof of Theorems \ref{rob:aff} and \ref{rob:pseu}~:}

   We first set $\kappa = 1$. Let us assume for a while that ~:

   \begin{equation}
    \label{rob:gen:1}
    {(1 - \bar u) \bar \alpha + \bar u \over \psi(\bar u)^2} < 1/32
   \end {equation}
   \par
   It follows from Lemma \ref{lem:alpha:x}
   that $\alpha(f,x) < 1/8$ , and Lemma \ref{lem:beta:x}
   implies~:
   $$
   \beta(f,x') \le {1 \over 8 \psi(1/8)} \beta(f,x) 
   $$
   \par
   Hence ~:
   $$
   \beta(f,x') \le 
   {1 \over 8 \psi(1/8)}  
   (1- \bar u)
   { (1 - \bar u) \bar \alpha + \bar u 
   \over
   \psi(\bar u)
   }
   {
   1
   \over
   \bar \gamma
   }
   $$
   \par
   Hence, in order to obtain $\beta(f,x') \le \bar u / 2 \bar \gamma$,
   we need~:
   \begin {equation} 
   \label{rob:gen:2}
   {1 \over 8 \psi(1/8)}  
   (1- \bar u)
   { (1 - \bar u) \bar \alpha + \bar u 
   \over
   \psi(\bar u)
   }
   <
   {\bar u \over 2}
   \end{equation}
   \par
   Numerically, we can verify that~: $\bar u = 0.05$ and $\bar \alpha = 0.02$
   make conditions (\ref{rob:gen:1}) and (\ref{rob:gen:2}) true, proving
   Theorems \ref{rob:aff} and \ref{rob:pseu}.


\paragraph{Proof of Theorem \ref{rob:proj} ~:}

   Let us assume now that ~:
   \begin{equation}
    \label{rob:proj:1}
    \kappa^2 {(1 - \bar u) \bar \alpha + \kappa \bar u 
             \over \psi(\bar u)^2} < 1/32
   \end {equation}
   \par
   It follows from Lemma \ref{lem:alpha:x}
   that $\alpha(f,x) < 1/32$ , and from Lemma \ref{lem:beta:x}
   we obtain~:
   $$
   \beta(f,x') \le \kappa {1 \over 32 \psi(1/32)} \beta(f,x) 
   $$
   \par
   Hence ~:
   $$
   \beta(f,x') \le 
   \kappa {1 \over 32 \psi(1/32)}  
   (1- \bar u)
   { (1 - \bar u) \bar \alpha + \bar u 
   \over
   \psi(\bar u)
   }
   {
   1
   \over
   \bar \gamma
   }
   $$
   \par
   Hence, in order to obtain $\beta(f,x') \le \bar u / 2 \bar \gamma$,
   we need~:
   \begin {equation} 
   \label{rob:proj:2}
   \kappa {1 \over 32 \psi(1/32)}  
   (1- \bar u)
   { (1 - \bar u) \bar \alpha + \bar u 
   \over
   \psi(\bar u)
   }
   <
   {\bar u \over 2}
   \end{equation}
   \par
   If we further assume $\bar \alpha < 1/32$, we have always
   $\kappa < 1.2567$.
   Numerically, we can verify that~: $\bar u = 0.005$ and $\bar \alpha = 0.01$
   make conditions (\ref{rob:proj:1}) and (\ref{rob:proj:2}) true, proving
   Theorem \ref{rob:proj}.


\paragraph{Proof of Theorem \ref{th:main}~:}

We first set~:

$$
\bar \gamma \ge {2 \over 3} D^{3/2} \mu
$$
\par
and~:
$$
\Delta \le {3 \over 8} {\bar \alpha \over \mu \bar \gamma}
\le {9 \over 16} {\bar \alpha \over \mu^2 D^{3/2} }
$$
\par
We assume by induction that $\dproj(z_{i-1},\zeta_{t_{i-1}}) \le  
{\bar u \over \bar \gamma} $. We want to verify that we are
in the conditions of Corollary \ref{rob:cor}.
\par
Using $\bar \alpha \le 0.02$, we obtain the estimates~: $\Delta \le 0.04$ and
$\sqrt{D} \Delta \mu \le 0.04$. 
\par
We use Lemma \ref{lem:etamu}~:
\begin{align*}
\gamma(f_{t_i},\zeta_{t_{i-1}}) 
&\le
{D^{3/2} \over 2}
\mu(f_{t_i}, \zeta_{t_{i-1}})
\\
&\le
{D^{3/2} \over 2}
\mu(f_{t_{i-1}}, \zeta_{t_{i-1}})
{1 + \Delta \over 1 - \sqrt{D} \Delta \mu}
\\
&\le
{1.04 \over 1.92} D^{3/2} \mu
\\
&\le
{2 \over 3} D^{3/2} \mu
\le \bar \gamma
\end{align*}
\begin{align*}
\eta(f_{t_i}, \zeta_{t_{i-1}})
\mu(f_{t_i}, \zeta_{t_{i-1}})
&\le
\Delta \mu 
{1 + \Delta \over 1 - \sqrt{D} \Delta \mu}
\\
&\le
{3 \over 8} {1.04 \over 0.96} {\bar \alpha \over \bar \gamma}
\\
&\le
{\bar \alpha \over \bar \gamma}
\end{align*}
\par
Now we can apply Corollary \ref{rob:cor}, and conclude that
$\dproj(z_i,\zeta_{t_i}) \le {\bar u  \over \bar \gamma}$. This proves
Theorem \ref{th:main}.

 



\chapter {Construction of the Approximate Newton Operator}
\label   {ch:newton}

\begin {abstract}
The approximate Newton Operators are constructed, and their
complexity is estimated.
\end   {abstract}



\section {Introduction}
\label{sec:newton:intro}
Let $f = (f_1, \dots , f_n)$ be a system of polynomials of
degree $d = (d_1 , \dots , d_n)$ in variables $x_i$, with 
Gaussian integer coefficients.
Let $D = \max \ d_i$. Let $S(f)$ be the number of non-zero coefficients of $f$.
We will consider together the case in which the
$f_i$ are polynomials in variables $x_1, \dots , x_n$ representing
points in affine space, and the case
in which the $f_i$ are homogeneous in variables $x_0, \dots , x_n$. 
\par
In chapter \ref{ch:condpath}, we defined three versions of the
Newton operator. In the case the $f_i$ are non-homogeneous,
the (classical) Newton method in affine space is defined by~:
$$
  N\aff (f,x) = x - Df(x)^{-1} f(x)
$$
\par
In the homogeneous case, we can define methods~:
\begin{align*}
N\proj (f,x) &= x - \PDf{x}{x} ^{-1} \PV{f(x)}
\\
N\pseu (f,x) &= x - Df(x)^\dagger f(x)
\end{align*}
\par
where $x\ctrans$ is the complex transpose of vector $x$ and
$A^\dagger$ is the Moore-Penrose pseudo-inverse of matrix $A$.
\par
The two methods above can be considered as mappings from the
space ${\Bbb C}^{n+1}$ into itself. We can also consider the
affine method as a mapping from a subset of ${\Bbb C}^{n+1}$ into itself ~:  
\par
Indeed, if $f$ is non-homogeneous, we define~:
$$
N\aff(x_0, \dots , x_n) =
{x_0}^d N\aff(x_1 / x_0 , \dots , x_n / x_0)
$$
\par
so that we have mappings of all spaces $x_0 = c$ into themselves,
for $c \ne 0$. We unified the three methods by the notation
$N(f,x) = x - {Df(x)_{|V(x)}}^{-1}$, where $V(x)$ associates
to each $x$ an hyperplane passing through $x$, and 
$V(\lambda x)=\lambda V(x)$.
\par
Since $N(f, \lambda x) = \lambda N(f,x), \lambda \in \Bbb C$, 
it follows that $N(f,.)$ sends lines through the origin into
lines through the origin. Therefore, it makes sense to consider
$N(f,.)$ as a mapping of the projective space.
\medskip
\par
The system
$f$ will be given as a list of polynomials $f_1, \dots, f_n$. 
Each polynomial $f_i$ is
a list of monomials
$\dots f_{iJ} x^J \dots$. A monomial is a list of $n+3$
integers~: $\Re(f_{iJ}), \Im(f_{iJ}), J_0, J_1, \dots , J_n$, where
$J_0$ can be omitted in the non-homogeneous case.
\par
We define the height $H(f)
= \max ( | \Re(f_{iJ}) | + | \Im(f_{iJ}) |)$. This is not the standard
definition of Height. The point $x$ will
be given as a list $(x_0, \dots, x_n)$ of Gaussian integers. Of course,
if the input is given as a list of complex floating point
numbers, the same complexity analysis below will be true.
We define the {\em height} $H(x)$ of $x$ as
$H(x) = \max ( |\Re(x_i)| + |\Im(x_i)| ) $.
\medskip
\par
The objective of this chapter is to construct algorithms to compute 
{\em approximately} the operators $N\aff$, $N\proj$ and $N\pseu$. This
means that if $N$ is one of those operators, and if
$N'$ is the mapping computed
by some algorithm, we want to guarantee that the {\em error}
$\sup_x { \norm{N'(f,x) - N(f,x)} \over \norm{x} }$ is small.
Also,
we want a bound on the {\em complexity} of those algorithms.
\medskip
\par
The concepts of {\em algorithm} and {\em complexity} require the
definition of a computation and complexity model. Here, we will
consider two different settings~: numerical analysis and theoretical
computer science. 
\par
From the numerical analysis point of view, 
the complexity will be the number of floating point operations
performed for a given input. For the model of computation, we will 
explain in section \ref{sec:def} what we mean by an
{\em $\macheps$-machine}, or a {\em machine}
performing {\em correctly rounded} finite precision
floating point arithmetics {\em with monotone subtraction}. The later
are standard properties verified by the arithmetic of most computers
today. 
\par
One consequence of the correctly rounded arithmetic is that the 
computed result $\fl (a \diamond b)$\glossary{$\fl(a\diamond b)$&Computed result of $a \diamond b$}
of an arithmetic operation $a \diamond b$ verifies~: 
$\fl(a \diamond b) = (a \diamond b) (1 + \epsilon)$ with
$| \epsilon |$ not greater than a fixed constant $\macheps$, called
the {\em machine epsilon}.  

{\theorem \label{th:n1}
          Let $16 < k \in \Bbb N$ be fixed. 
          Then there is a machine $N'$ performing
          correctly rounded arithmetic with monotone subtraction,
          with machine epsilon $\macheps = 2^{-k-1}$,
          and requiring $O(nDS(f)+n^3)$ floating point operations,
          such that, if $H(f), H(x) \le {1\over 2 \macheps}$~:
\begin{align*}
{ \norm {N'(f,x) - N(f,x)} \over \norm{x} }
\le
 &4 \mu(f,x) \sqrt{D}
\left( p(n) + 2D + 2 + 2\max(S(f_i)) \right)
\macheps
\\
&+ O(\macheps^2)
\end{align*}
          \par
          where $O(\macheps ^2)$ means a function bounded by
          some $B(n,D,S(f),\mu) \macheps^2$.
          }
\medskip
\par
Above, $p(n)$ is a function
of $n$, defined as $5 n^2 (g_{cp}(n) + 1)$ for the affine method,
as $5 (n+1)^2 (g_{cp}(n+1) + 1)$ for the projective method,
and $(3.25 (n+1)^3 + 11 (n+1)^2)$ for the pseudo-Newton method. 
$g_{cp}(n)$ is the {\em maximum complete pivot growth} 
for a matrix of size $n$ ,
see Golub and Van Loan \cite {GOLUB} or Wilkinson \cite{WILKINSON2}.
The function $g_{cp}(n)$ can be bounded by the formula
$g_{cp}(n) \le \sqrt{n} \sqrt{2 \times 3^{1 \over 2} \times \dots
\times n^{1\over{n-1}} }$.
\par
The {\em condition number} $\mu(f,x)$ is defined by~:
$$
\mu(f,x) = 
 \knorm{f}
 \bignorm{ {Df(x)_{|V(x)}}^{-1}
    \diag( \sqrt{d_i} \norm{x}^{d_i -1} ) } 
$$
\par
The {\em Kostlan norm} $\knorm{.}$ is the unitarily invariant norm in the
space of polynomials~, and is defined by 
$\knorm{f} = \sqrt{\sum \knorm{f_i}^2}$,
where~: 
$$
\knorm{f_i} = \sqrt{ \sum_{|J|=d_i} { |f_{iJ}|^2 \over \binomial{d_i}{J}}} 
$$

As it often happens in numerical analysis, the linear factor in
theorem \ref{th:n1} may be extremely pessimistic. The actual error may
be much smaller.
On the other hand, the result above says little about the behavior of
the high order terms in $\macheps ^2$.
\medskip 
\par
From the point of view of theoretical
computer science, we will use the Blum - Shub - Smale model
over $\Bbb Z$ (See \cite{BSS}) (equivalent to the Turing model), 
and give a bound for the height
of numbers used in calculations. The cost of each operation
with numbers of height $H$ will be $O(\log H)$ or $O(\log H \log \log H)$.
The cost of accessing position $n$ in the memory is $n$. In this
setting, we obtain~:
{\theorem \label{th:np}
        There is a machine over $\Bbb Z$ such that, given
          a system $f$ of $n$ polynomials of degree at most $D$,
          with S(f) non-zero Gaussian integer coefficients, 
          a vector $x$ of floating-point complex numbers, 
          $\bar \mu \ge \mu(f,x)$, 
          and $\delta > 0$, returns
          $N_\delta(f,x)$ such that ~:
          $$
        { \norm{ N_\delta (f,x) - N\pseu (f,x) }
         \over
         \norm{x} }
         \le
         \delta
          $$
          \par
          within polynomial time in $n$, $D$,
          $\log H(f)$, $\log H(x)$, $S(f)$,
          $\log \bar \mu$, $- \log \delta$. 
          }
\medskip
\par
We will prove this theorem only for the pseudo-Newton method.
The proof for the affine and projective Newton methods is similar.
\medskip
\par
In all this chapter, we assume without loss of generality that
$x$ is scaled so that ${1\over 2} < \norm{x} \le 1$ (just by performing
a division by a power of 2).
\medskip
\par
The results above were obtained after a few arbitrary choices.
In many senses, they are not the best possible algorithms for
that problem. 
\par
Simple precision is used wherever it is possible. While the usual
numerical analysis literature uses double precision, for instance,
to add a list of single precision numbers, this procedure
requires an additional hypothesis on the size of the list. 
See, for instance, Golub and Van Loan \cite{GOLUB} sections 2.4.6
and 2.4.7, Wilkinson \cite{WILKINSON} equation (5.2) of chapter 3,
page 113, or ibid., start of section 37, chapter 3, page 152.
\par
In our setting, computing the dot product $<v,w> = v^{\ctrans} w$,
where $v^{\ctrans}$ is the complex transpose
of $v$, and $v$ and $w$ are vectors of dimension $n$, 
will introduce a total error in the result that is bounded
by~:
$$
\left((1 + \macheps)^n - 1\right) \norm {v} \norm{w}
\le n \macheps \norm{v} \norm{w}
$$
\par
Using double
precision we would obtain error bounded by $\macheps \norm{v} \norm{w}$, 
but only provided $n$ is small enough.
\par
Also, simple and vectorizable algorithms are given preference
over more precise and expensive ones. For instance, there are
single precision algorithms for adding a list of numbers 
up to precision $\macheps$,
or up to arbitrary precision (See Priest, \cite{PRIEST}). But
precision is not a severe issue here, while speed is crucial.


\section {Basic definitions}
\label   {sec:def}
First of all, we have to define (for the numerical analysis purpose)
a model of computation. We want to model the floating point arithmetic
of modern computers. Let us fix a number $k \ge 16$, the number of bits of
mantissa.
\par
{\definition The set $\Bbb R_{fp}$ of {\em floating point numbers} 
             is the class of all reals 
             of the form $A 2^B$, 
             with $A, B \in \Bbb Z$ 
             and $|A| \le 2^k$. 
             }
\medskip
\par
This definition deliberately ignores the possibility of overflow
or underflow (exponents too small or to large). Now we can define
a model of computer~: 
{\definition \label{def:machine}
             An {\em $\macheps$-machine} means a Blum-Shub-Smale machine
             over the reals \cite{BSS}, with coefficients in
             $\Bbb R_{fp}$, with the following
             modifications~:
             \begin{itemize}
             \item The even positions of memory contain always
                   integer values.
             \item The odd positions of memory contain always
                   floating point numbers in $\Bbb R_{fp}$.
             \item Computation nodes contain one arithmetic 
                   operation each, from $+$, $-$, $/$, $*$, and
                   square root. 
             \item Decision nodes are in the form $x_i \ge 0$ or
                   $x_i > 0$ or $x_i = 0$. 
             \item If a division by zero or a square root of a
                   negative number occur, execution stops and
                   the machine outputs nothing.
             \item There is a function $\fl : {\Bbb R} \rightarrow
                   {\Bbb R}_{fp}$ such that, when a real number $x$ is
                   to be stored in an odd position of memory, it
                   gets rounded-off to $\fl(x)$
             \item {\em Correct arithmetics :}
                   $\fl(x)$ is one of the elements of ${\Bbb R}_{fp}$
                   nearest to $x$.
             \item {\em Monotone subtraction :}
             For all $a, b \in {\Bbb R}_{fp}$, we have~:
             $\fl(a - b) = - \fl(b -a)$
             \end{itemize}
             }
\medskip
\par
Now we introduce some definitions regarding rounding-off~:
\par
A consequence of Definition \ref{def:machine} is the $1 + \epsilon$ property.
If representable numbers have $t$ bits of mantissa, let 
$\macheps = 2^{-t-1}$\glossary{$\macheps$&Machine epsilon}.
Assuming that $t \ge 16$, we will have always
$\macheps \le 2^{-17} = {1 \over 131072}$. 
Then the machine verifies the $1+\epsilon$ property, defined 
below~:
\par
{\definition \label{def:onepluseps}
        A machine verifies the $1 + \epsilon$ property
        if it is true, for all $a, b \in {\Bbb R}_{fp}$, that~:
        $$
        \fl (a \diamond b) = (a \diamond b) (1 + \epsilon)\ ,
        \ |\epsilon| \le \macheps
        $$
        \par where $\diamond$ is one of $+$, $-$, $\times$, $ / $. Also, 
        $\fl(\sqrt{x}) = \sqrt{x} (1 + \epsilon), |\epsilon| \le
        \macheps$.
        }
\medskip
\par
We say that the relative error of $a \diamond b$ is less than $\macheps$.
\par
This property is known to hold
in most computer systems available at this time, except
CRAY systems.
\medskip
\par
We will also need to perform complex arithmetics. A complex number
can be represented by its real and imaginary parts, where elementary
operations between real numbers are performed with correct 
arithmetics. Therefore, complex arithmetics can be performed
by an $\epsilon$-machine. However, it is convenient to set
$\macheps = 2^{-t-1} \times 6$,
so the $1 + \epsilon$ property will hold for complex sum, subtraction,
multiplication and division. Let us prove this only for divisions~:
$$
{z \over w} = {z \bar w \over w \bar w}
$$
\par
Let $\epsilon = 2^{-t-1}$. Then $\fl(w \bar w) = w \bar w (1 + \epsilon_1)^2$
and $\Re(\fl(z \bar w)) = \Re(z \bar w) (1 + \epsilon_2)^2$, where 
$|\epsilon_1|, |\epsilon_2| \le \epsilon$. It follows that~:
$$
\Re \left(\fl \left( { z \over w } \right) \right)
 =
{\Re (z \bar w) \over w \bar w}
{( 1 + \epsilon_3) ^ 3 \over (1 - \epsilon_3) ^ 2 }
$$
\par
Since $\epsilon < 2^{-17}$, we get~:
$$
\Re \left(\fl \left( { z \over w } \right) \right)
 =
{\Re (z \bar w) \over w \bar w}
(1 + 6 \epsilon_4)
$$
\par
Proceeding in the same way for the imaginary part, we obtain~:
\begin {align*}
 \fl (z / w) - z / w &= 6 \epsilon_4 \Re(z/w) + 6 i \epsilon_5
\Im(z/w)
\\
| {\fl(z / w) \over z/w } - 1 | &\le 6 \epsilon
\\
\fl(z/w) &= {z \over w} (1 + 6 \epsilon_6)
\end{align*}
\par
where $|\epsilon_3|, |\epsilon_4|,|\epsilon_5|, |\epsilon_6| \le \epsilon$.
\medskip
\par
The following notation will be very useful. If $\macheps$ is the
{\em machine epsilon}, the relative error of each calculation,
we define the function~:
$$
\macheps(k) = {1 \over (1 - \macheps)^k} -1
$$
\par
Then we have the following properties, for $k, l, n \ge 1$~:
\begin{align*}
\macheps &< \macheps(1)
\\
(1 + \macheps(k)) (1 + \macheps(l)) &= 1 + \macheps(k+l)
\\
\macheps(k) + \macheps(l) &< \macheps(k+l)
\\
n \macheps(k) &\le \macheps(n k)
\\
{1 + \macheps(k) \over 1 - \macheps(l)} &< 1 + \macheps (k+l)
\\
{1 - \macheps(k) \over 1 + \macheps(l)} &> 1 - \macheps (k+l)
\end{align*}
\par
However, under the assumption that $k \macheps$ is small, 
$\macheps(k) \simeq k \macheps $. 
\par
We will often find inequalities of the form $p \macheps(q) < 1$~; those
can be solved by using the
{ \lemma \label{lem:macheps}
         Let $p, q > 1$, and let $\macheps < {1 \over 2 p q}$. Then
         $p \macheps(q) < 1$.
         }
\par
Proof~: $pq \macheps < {1 \over 2}$ implies that $1 - pq\macheps  
> {1 \over 2} $, hence $(1 - \macheps)^{pq}>{1 \over 2}$, so
${1 \over (1 - \macheps)^{pq}} < 2$, and therefore 
$p \macheps(q) \le \macheps(pq) <1$.
\par
This shows that there is a machine using $k$ bits of precision
such that $p \macheps(q) < 1$, where $k < 1 + \log_2 p + \log_2 q$.
\medskip
\par


\section {Algorithms}
\label   {sec:algo}
Suppose we are given $x$ and $f$ as in the hypotheses of Theorem
\ref{th:n1}. 
$S(f)$ is the number of non-zero coefficients of $f$. If
$f$ is dense, $S(f) = \sum \binomial{d_i+n}{n}$.
\par
If $1 \le i \le n$ and if $K$ is a multi-index of degree
$d_i$, we denote $f_{iK}$ the coefficient of $f_i$ associated
to multi-index $K$. 
\par
We define the following procedure in order to compute the approximate
Newton method in affine space~:
\medskip

{
\tt
\noindent
{ALGORITHM \ } $z'' \leftarrow $ Affine ( $f$, $x$ )
 
\begin{list}{\arabic{linenumber}}{\usecounter{linenumber}}
\item \label{lin:1}
      Compute $y_I = x^I$, where multi-index $I$ appears in
      $f$ or in $Df$. 
\item \label{lin:2}
      Compute $b_i = \sum f_{iK} \ y_K$
\item \label{lin:3}
      Compute $A_{ij} = \sum \deg_j(K)\ f_{iK} \ y_{K-e_j}$
\item \label{lin:4}
      Compute $L$, $U$, $P_1$, $P_2$ by gaussian elimination \\
      with complete pivoting, where $P_1 A P_2 = L U$, \\ 
      $P_1$ and $P_2$ are permutations, \\
      $L$ is lower triangular with entries $\le 1$, \\
      $U$ is upper triangular.
      For notational convenience, \\ 
      we will forget about
      $P_1$ and $P_2$ and write $A = LU$.
\item \label{lin:5}
      Compute $z = L^{-1}b$ by forward-substitution.
\item \label{lin:6}
      Compute $z'= U^{-1}z$ by back-substitution.
\item \label{lin:7}
      Compute $z'' = x - z'$.

\end{list}
}
\par
The following are upper bounds of the 
floating point operation count for each line.
\par
Line \ref{lin:1} costs at most $(1+n) (D-1) S(f)$ floating point operations,
since there are $S(f)$ non-zero coefficients, each of which appears
at most once in $f$ and $n$ times in $Df$. 
\par
Line \ref{lin:2} requires at most $2 S(f)$ operations, while
Line \ref{lin:3} requires at most $3 n S(f)$ operations.
\par
For Line \ref{lin:4}, we need to perform Gaussian elimination,
and that takes at most ${2 \over 3} n^3$ floating point operations. 
See Golub and Van Loan
\cite{GOLUB}, Algorithm 3.2.3, page 97.
\par
Forward and backward substitution require ${n (n-1) \over 2}$ multiplications,
${n (n-1) \over 2}$ sums or subtractions and $n$ divisions, hence 
each of them takes 
at most $n^2$ operations. In the case of Line \ref{lin:5}, we know that
the diagonal of $L$ contains only ones, so we do not need to perform
the $n$ divisions. Hence, the cost of Lines
\ref{lin:5} and \ref{lin:6} is bounded by $n(n-1)$ and $n^2$, respectively.
\par
Line \ref{lin:7} requires only $n$ operations. 
\par
Hence, the total operation count is~:
\begin {equation}
(nD + 2n + D + 1) S(f) + {2 \over 3} n^3 + 2n^2 
\end{equation}
\medskip
\par
For the Newton method in Projective space, we will have $n+1$ variables,
and we use the formula~:
$$
N\proj(f,x) = x - \PDf{x}{x}^{-1} \PV{f(x)}
$$
\par
Using the same algorithm, the operation count becomes~:
\begin {equation}
(nD + 2n + 2D + 3) S(f) + {2 \over 3} (n+1)^3 + 2 (n+1)^2 
\end{equation}
\medskip
\par
For the pseudo-Newton case, we can modify the algorithm as follows~: \\
\medskip

{
\tt
\noindent
{ALGORITHM \ } $z'' \leftarrow $ Pseudo ( $f$, $x$ )
 
\begin{list}{\arabic{linenumber}}{\usecounter{linenumber}}
\item \label{lin:b1}
      Compute $y_I = x^I$, where multi-index $I$ appears in
      $f$ or in $Df$. 
\item \label{lin:b2}
      Compute $b_i = \sum f_{iK} \ y_K$
\item \label{lin:b3}
      Compute $A_{ij} = \sum \deg_j(K)\ f_{iK} \ y_{K-e_j}$
\item \label{lin:b4}
      Compute $Q$, $R$ such that $A^t = Q 
      \left[ \begin{array}{c} R \\ 0 \end{array} \right]$
\item \label{lin:b5}
      Compute $z = {R^t}^{-1}b$ by forward-substitution.
\item \label{lin:b6}
      Compute $z'= Q_{:,1:n} z$.
\item \label{lin:b7}
      Compute $z'' = x - z'$.

\end{list}
}

Lines \ref{lin:1} to \ref{lin:3} are as above.
\par
For Line \ref{lin:4}, we use Householder QR factorization,
as in Algorithm 5.2.1, page 212 in Golub and Van Loan
\cite{GOLUB}. This algorithm takes $2n^2 (n+1 - n/3) = {4 \over 3}
n^3 + 2 n^2$ floating point operations. This includes $n$ square
root operations on real numbers.
\par
Line \ref{lin:5} will take at
most $(n+1)^2$ operations. 
\par
Q is returned not as a matrix, but
as a list of Householder vectors. Thus, computing step \ref{lin:6}
will require $3 n^2$ operations. 
\medskip

{
\small
\begin{tabular}{c|c|c|c}
\multicolumn{4}{c}{Operation count (summary)}\\
\multicolumn{4}{c}{}\\
Line & Affine & Projective & Pseudo-Newton \\ \hline
\ref{lin:1} &
    $(1+n) (D-1) S(f)$ &
    $(2+n) (D-1) S(f)$ &
    $(2+n) (D-1) S(f)$ \\ 
\ref{lin:2} &
    $2 S(f)$ &
    $2 S(f)$ &
    $2 S(f)$ \\ 
\ref{lin:3} &
    $3 n S(f)$ &
    $3 (n+1) S(f)$ &
    $3 (n+1) S(f)$ \\ \hline
\ref{lin:4} &
    $ {2 \over 3} n^3 $ &
    $ {2 \over 3} (n+1)^3 $ &
    $ {4 \over 3} n^3 + 2 n^2$ \\
\ref{lin:5} &
    $ n(n-1) $ &
    $ (n+1) n $ &
    $ (n+1)^2 $ \\
\ref{lin:6} &
    $ n^2 $ &
    $ (n+1)^2 $ &
    $ 3n^2 $ \\ \hline
\ref{lin:7} &
    $n$ &
    $n+1$ &
    $n+1$ \\  \hline
Total &
    $(nD + 2n + D + 1) S(f)$ &
    $(nD + 2n + 2D +3) S(f)$ &
    $(nD + 2n + 2D + 3) S(f)$ \\
&
    $+ {2 \over 3}n^3 + 2n^2$ &
    $+ {2 \over 3}n^3 + 6n^2 + 6n + {8 \over 3}$ &
    $+ {4 \over 3}n^3 + 4n^2 + 3n + 2$
\end{tabular}
}


\section {Sketch of the proof of Theorems \ref{th:n1} and \ref{th:np}}
\label   {sec:sketch}
Let us consider for a while the operators~:
$$
M\aff : A, b \mapsto A^{-1} b
$$
$$
M\proj : x', A, b \mapsto \left[ \begin{array}{c} A \\ {{x'}\ctrans} \end{array}
\right]^{-1} \left( \begin{array}{c} b \\ 0 \end{array} \right)
$$
$$
M\pseu : A, b \mapsto A^\dagger b
$$

We divide the algorithm in three phases ~: Phase 1 is lines \ref{lin:1}
to \ref{lin:3}, Phase 2 is lines \ref{lin:4} to \ref{lin:6}, and
Phase 3 is line \ref{lin:7}.
\par 
Given $x$, $f$, Phase 1 computes $A$ and $b$,
with a certain error $\delta_1 A$ and $\delta_1 b$. Those are called
{\em forward error} of Phase 1. It will be easy to find a bound for them.
$x = x' $ is passed exactly to Phase 2.
\par
The forward error of Phase 2 is harder to bound. It is much easier
to prove that given $A$, $x'$, $b$, Phase 2 returns
$M(x' + \delta_2 x, A + \delta_2 A, b + \delta_2 b)$, where
$\delta_2 x$, $\delta_2 A$ and $\delta_2 b$ are called the {\em backward
error} of Phase 2. We will give bounds for those quantities.
\par
If we set $\delta_x' = \delta_2 x$, 
$\delta A = \delta_1 A + \delta_2 A$, $\delta b = \delta_1 b + \delta_2 b$,
then we are indeed computing $M(x + \delta x',\Df{x}{x} + \delta A, 
f(x) + \delta b)$,
$M$ one of $M\aff$, $M\proj$, $M\pseu$. 
\par
We will bound the derivatives of $M$, and then obtain bounds on the
total error of Phases 1 and 2. 
\par
Phase 3 is just a subtraction, and hence, the total error of 
the algorithm is easy to bound.


\section {Forward error analysis of Phase 1}
\label {sec:forward}
If $A$ is a matrix, we define $\maxnorm{A} = \max |A_{ij}|$~
\glossary{$\maxnorm{.}$&sup norm of a matrix, considered as a vector}.
This
is a {\em vector} norm, not a {\em matrix} norm : it is not true
in general that $\maxnorm{AB} \le \maxnorm{A} \maxnorm{B}$. 
In this section, we bound $\maxnorm{\delta_1 A}$ and $\norm{\delta_1 b}$.
We recall that $\|x\| \le 1$, so~:
$$
\| f(x) \| \le \knorm{f}
$$
\par
where $\knorm{.}$ is the Kostlan norm. 
\par
Since each of the $f_{iK} \ x^K$ is computed with relative error
$\macheps(d_i)$, the sum $f_i(x)$ is computed up to a total error
$\delta_1 b$ such that~:
$$
| \delta_1 b_i | \le 
\macheps(d_i + S(f_i)) \sum |f_{iK} | \ |x^K|
$$
\par
Adding squares for each $i$ and extracting the square root, we obtain~:
\begin {equation}
\label{for:b}
\norm {\delta_1 b} \le 
\knorm{f} \macheps(D + \max S(f_i) )
\end {equation}
\medskip
\par
In order to bound $\maxnorm{\delta_1 A}$, we claim that
$$
\knorm{ {\partial \over \partial x_j} f_i }
\le
\sqrt{d_i} \knorm{f_i}
$$
\par
Indeed,  
$$
\knorm {{\partial \over \partial x_j} f_i} 
\le
\sqrt { \sum { {f_{iJ}}^2 \over \binomial{d_i - 1}{J - e_j} }} \max J_j
$$
$$
\le
\sqrt{d_i} \sqrt { \sum { {f_{iJ}}^2 \over \binomial{d_i}{J} }}
$$
\par
From this claim we deduce that~:
\begin {equation}
\label{for:A}
\maxnorm {\delta_1 A} \le \sqrt{d_i} \knorm{f} \macheps(D + S(f_i)+1)
\end{equation}


\section {Some backward error analysis identities}
\label {sec:some}

\paragraph {Products~:} 
From the $(1 + \epsilon)$ property, we deduce~:
\begin {equation}
\fl (a b) = (a + \delta a) b
\end {equation} 
\par
where $| \delta a | \le |a| \macheps$. 
\paragraph {Divisions~: }
\begin {equation}
\fl(b / a) = {b \over a + \delta a}
\end {equation}
\par
with $| \delta a | \le |a| \macheps(1)$. Indeed, ${b \over a}(1+\macheps)
= {b \over a + \delta a}$ with $|\delta a| \le |a| ({1 \over 1 + \epsilon}-1)$,
where $|\epsilon | \le \macheps$, so $({1 \over 1 + \epsilon}-1) \le 
\macheps(1)$.  

\paragraph{Sums of products~:} For sums of products, we have~:
\begin{equation}
\label{eq:sumofprod}
\fl( \sum_{1 \le i \le n} a_i b_i )  = \sum_{1 \le i \le n}
 (a_i + \delta a_i) b_i 
\end{equation}
\par
with $|\delta a_i| \le |a_i| \macheps(n)$.
\medskip
\par
\paragraph{Backward and forward substitution~:}
Now, let $U$ be a $n \times n$ upper-triangular matrix. We want to compute
$z = U^{-1} y$ by backward substitution~:
$$
\text{For \ } i= n \text{\ down to \ }1,\ 
    z_i = {y_i - \sum_{j > i} U_{ij} z_j \over U_{ii}}
$$

Let $|U|$ denote the matrix of the absolute values of the
coefficients of $U$. Then we have~:
$$
z = (U + \delta U) ^{-1} y 
$$
\par 
where $|\delta U_{ij} | \le \macheps(n) |U_{ij}|$ when
$i \ne j$, and $|\delta U_{ii}| \le \macheps(2) |U_{ii}|$.
Thus, we have always, for $n \ge 2$~:
\begin {equation}
\label {eq:Uback}
| \delta U_{ij} | \le \macheps(n) |U_{ij}|
\end {equation}
\par
This is still true when $n=1$, trivially. 
The same bound is true for forward substitution.
\medskip
\par
\paragraph{Householder transforms~:}
We will now bound the backward error of a Householder transform.
We compute the Householder transform in the following order~:
$$
H_v(y)
=
y + \left( {-2 (v^t y) \over (v^t v) } \right) v
$$
\par
According to equation (\ref{eq:sumofprod}), $v^t v$ and $v^t y$ are
computed with total error bounded by $\norm{v}^2 \macheps(n)$ and
$\norm{v} \norm{y} \macheps(n)$, respectively. Multiplication by
$-2$ is just adding one to the exponent, and changing sign, so 
it does not introduce new rounding-off error. 
\par
Let $w = - 2 {v^t y \over v^t v} v$. Each $w_i$ is computed up
to error $\macheps(2n+2) \norm{y}$. 
Therefore, and since $\norm{H_v(y)} = \norm{y}$,
the total error is less than $\macheps(2n+3)\norm{y}$.
Since $H_v$ is unitary, this is also the backward error~:
\begin {equation}
\norm{ \delta y } \le \norm{y} \macheps(2n+3)
\end {equation}

\paragraph{Products of Householder transforms~:}
Let $Q = H_1 H_2 \dots H_n$ be a product of Householder 
transforms. Then~:
$$
\fl (Qy) = (Q + \delta Q ) y =
(H_1 + \delta H_1) (H_2 + \delta H_2) \dots (H_n + \delta H_n) y
$$
\par
That means that~:
$$
\norm{ \delta Q } \le \sum \norm{\delta H_i} 
+ \sum \norm{\delta H_i} \norm{\delta H_j} + \dots
$$
$$
\le \macheps(2n^2 + 3n) 
$$
\par
If, however, the $i$-th Householder vector contains at most $i$
non-zero coordinates, we obtain the bound~:
$$
\macheps(\sum_i^n 2i+3) = \macheps(n^2 + 4n)
$$
\paragraph {LU decomposition~:}
We also need to bound the backward error $\delta _g A$ of the
LU decomposition~: $A + \delta _g A = L U$. Recall that we use
complete pivoting, but we do not write the permutation matrices,
since permutation introduces no floating point operation.
Let $|L|$ be the matrix
of the absolute values of elements of $L$. Since we perform
$n-1$ pivot steps, we have the formula below (see also Theorem 3.3.1
page 105 in Golub and Van Loan \cite{GOLUB})~:
$$
|\delta_g A| \le |L| |U| \macheps(3n-3)
$$
\par
By construction $|L_{ij}| \le 1$, but $|U_{ij}|$ is harder to
bound ; indeed, it is usual to define the {\em pivot growth
factor} $g_{cp}$ such that, {\em in exact arithmetic}~:
\begin {equation}
\label{gauss:gcp}
|U_{ij}| \le g_{cp} \max |A_{ij}|
\end {equation}
\par
It is known that $g_{cp}$, in the case of complete pivoting,
can be bounded by the formula 
$$
g_{cp}(n) \le \sqrt{n} \sqrt{2 \times 3^{1 \over 2} \times \dots 
\times n^{1\over{n-1}} }   
$$
\par
We obtain the formula ~:
\begin {equation}
\label{eq:gaussback}
|\delta A_{ij}| \le
         n g_{cp}(n)
         \max |A_{ij}| 
         \macheps(3n-3)
\end {equation}

\paragraph {QR decomposition~:}
Again, we set ~:
$$
A + \delta_{qr} A = Q R
$$
\par
At step $i$, in order to obtain the Householder vector $v$,
setting $x = A_{i:n,i}$, we first compute
$\beta = x_1 + \sgn(x_1) \norm{x}$. This is done
with relative error bounded by $\macheps({n-i+1 \over 2}+1)$.
Then we do $v_1 = x_1$ and 
for $j = 2, \dots , n-i+1$, we compute $v_j = x_j / \beta$.
We obtain $v$ with relative error (in each coordinate)
bounded by $\macheps({n-i+1 \over 2} + 2)$. This also
bounds the error $\norm{ H_v - H_{\fl(v)} }$ . 
\par
Applying $H_{\fl(v)}$ introduces further error, bounded by
$\macheps(2(n-i+1) + 3)$. It follows that per step, we introduce
error~:
$$
\norm{ \delta H } \le \macheps \left( { 5n - 5i + 10 \over 2 } \right)
$$
\par
It follows that at the end, we obtain $Q$ and $R$ such that~:
$$
(Q + \delta Q ) R = A
$$
\par
with error~:
$$
\norm{ \delta Q } \le \macheps(2.25 n^2 + 5.25 n)
$$
\par
We easily see that $\delta_{qr} A = - \delta Q \ R$. We know that
$\norm{ R } = \norm{ A }$, so we obtain~:
$$
\norm{ \delta_{qr} A } \le \norm{A} 
\macheps(2.25 n^2 + 5.25 n)
\le n \max(|A_{ij}|)
\macheps(2.25 n^2 + 5.25 n)
$$


\section {Backward error analysis of Phase 2}
\label {sec:backward}
The Newton operator in affine space produces
matrices $L$ and $U$ such that
$A - LU = \delta _g A$, where $\delta _g A$ verifies equation 
(\ref {eq:gaussback}).  Because of rounding-off in lines 
\ref{lin:5} and \ref{lin:6}, the algorithm computes
$\fl (M(A,b)) = (U + \delta U)^{-1} (L+\delta L)^{-1} b$, so
we write~:
$$
(A + \delta_2 A)^{-1}  = (U + \delta U)^{-1} (L+\delta L)^{-1} 
$$
\par
Or~:
\begin{align*}
A + \delta_2 A &= (L + \delta L) (U + \delta U)
\\
&= A + \delta _g A + \delta L U + L \delta U + \delta L \delta U
\end{align*}
\par
Subtracting $A$ from both sides, and passing to the matrix of
absolute values, we obtain~:
$$
| \delta_2 A | \le
| \delta_g A| + | \delta L| |U| + |L| |\delta U| + |\delta L| |\delta U|
$$
\par
Inserting formulas (\ref{eq:Uback}) , 
(\ref{gauss:gcp}) and (\ref{eq:gaussback}), we obtain~:
\begin{equation}
\label{back:aff}
\maxnorm { \delta_2 A } = \max(|A_{ij}|) 
\le
\macheps( 5 n^2 (g_{cp}(n) + \macheps(n))) 
(\maxnorm{A} + \maxnorm{\delta_2 A})
\end {equation} 

For the Newton operator in projective space, we obtain~:
\begin{equation}
\label{back:proj}
\maxnorm{ \delta_2 A } 
\le
\macheps(5 (n+1)^2 (g_{cp}(n+1) + \macheps(n+1)))
( \maxnorm{A} + \maxnorm{\delta_2 A})
\end {equation} 

For the pseudo-Newton method, we write~: 
$$
 \delta_2 A_{ij} = 
 \delta_{qr} A_{ij}  +  \delta R \ Q^t
   + R \ \delta Q^t + \delta R \ \delta Q^t
$$
$$
\norm{ \delta_2 A_{ij}} \le 
 \norm{\delta_{qr} A_{ij}}  
 + \norm{\delta R} \ \norm{Q^t}
 + \norm{R} \ \norm{\delta Q^t} 
 + \norm{\delta R} \ \norm{\delta Q^t}
$$
\par
Hence,
\begin{align}
\label{back:pseu}
\maxnorm{\delta_2 A} &\le \norm{\delta_2 A}
\\
&\le
\macheps( 3.25 (n+1)^2 + 10.25 (n+1) + \macheps( (n+1)^3 + 4 (n+1)^2 ) )
\notag \\
& \ (n+1) (\maxnorm{A} + \maxnorm{ \delta_2 A})
\notag
\end{align}

\section {Conditioning of $M$}
\label {sec:cond}
\paragraph {Conditioning of matrix inversion~:}
Let $A(t)$ be a non-singular matrix, depending on a parameter
$t$. From the formula $A(t)^{-1} A(t) = I$ we obtain~:
\begin {equation}
{ \partial \over \partial t} 
(A (t)^{-1})
=
A(t)^{-1}
{ \partial \over \partial  t} 
A(t)
A(t)^{-1}
\end {equation}
\par
Let us use that formula for $A$ as depending of entry $A_{ij}$~:
$$
{ \partial \over \partial A_{ij}} A^{-1}
=
A^{-1}
\left[ 
0\ e_i \ 0
\right]
A^{-1} 
$$
\par
Recall that $M\aff (A,b) = A^{-1} b$, so we write~:
$$
{ \partial \over \partial A_{ij}} M(A,b)
=
\left[ 
0 A^{-1}e_i 0
\right]
A^{-1} 
b
$$
\par

We now consider the operator ${\partial \over \partial A} M(A,b)$. This
operator associates to each $n \times n$ matrix $X$ the vector
$Y A^{-1} b$, where $Y_{ij} = (A^{-1})_{ij} X_{ij}$. 
\par
Let $\maxtwonorm{.}$\glossary{$\maxtwonorm{.}$&A norm of the space of mappings of matrices into vectors}
be defined as the norm of operators from the 
vector space
of $n \times n$ matrices endowed with the norm $\maxnorm{.}$ into
the space of $n$ vectors endowed with the 2-norm $\norm{.}$. From the 
inequality~: $\norm{Y} \le \maxnorm{X} \norm{A^{-1}}$, we deduce
the formula~:
\begin {equation}
\maxtwonorm{ { \partial \over \partial A} M(A,b) } 
\le
\norm{ A^{-1}} \norm{ A^{-1}b} 
\end {equation} 
\par
Also, considering ${\partial \over \partial b} M(A,b)$ as a linear
operator and using the matrix 2-norm, we have~:
$$
\norm{ { \partial \over \partial b} M(A,b) } 
\le
\norm { A^{-1} } 
$$
\paragraph {Conditioning for Newton in projective space~:}
Recall the definition of $M\proj$~:
$$
M\proj (x,A,b) = \PR{A}{x} ^{-1} \PV{b}
$$
\par As in the case of Newton in affine space,
$$
{ \partial \over \partial A_{ij}} M\proj(x,A,b)
=
\left[ 
0 \PR{A}{x}^{-1}e_i 0
\right]
\PR{A}{x}^{-1} 
b
$$
\par Hence~:
$$
\maxtwonorm{ { \partial \over \partial A} M\proj(x,A,b)} 
\le
\bignorm { \PR{A}{x}^{-1} } \bignorm{ \PR{A}{x}^{-1}b} 
$$
\par 
The derivative on $x$ is the same as the derivative in $A$. 
As in the affine case, also, 
$$
\norm { { \partial \over \partial b} M(x,A,b)} 
\le
\bignorm{ \PR{A}{x}^{-1}} 
$$

\paragraph {The pseudo-Newton case ~:}
Now, $M\pseu (A,b) = A^\dagger b$. It is easy to check that~:
$$
\norm{ { \partial \over \partial b} N\pseu(A,b) } =\norm{ A^\dagger } 
$$
\par
For the derivative in $A_{ij}$, we parametrize~:
$$
A(t) = A + e_i {e_j}^t t
$$
\par
Let $V(t)$ be the space $\ker A(t) ^\perp$. Then we have~:
$$
\norm { A(t)^\dagger } = \norm{ {A(t)_{| V(t)}} ^{-1}}
\le \norm{ {A(t) _{| V(0) }} ^{-1} } = \norm{ A(0)^\dagger } 
$$
\par 
by construction of the pseudo-inverse. Thus~:
$$
\maxtwonorm{ { \partial \over \partial A} M\pseu(A,b)} 
\le
\norm{ A^\dagger } \norm{A^\dagger b}
$$

\paragraph {What does this mean~:} In a first order setting,
we can assume that $Df(x) - A = \delta A$ with $\maxnorm{\delta A}
 \in O(\macheps)$,
so that it makes sense to discard the terms in $\macheps ^2$, and write~:
\begin{align*}
\norm{ \fl(M\aff) - M\aff } <
    &\norm{ Df(x)^{-1} } \ \norm{ Df(x)^{-1} f(x) } \ \maxnorm{ \delta A}
\\
  & + \norm{ Df(x)^{-1} } \ \norm{ \delta b } + O(\macheps ^2)
\end{align*}
\par
Inserting inequalities $\norm{ Df(x)^{-1} } \le {2 \mu(f,x) \over \knorm{f}}$
and $\norm{ Df(X)^{-1} f(x) } \le \beta(f,x)$, we get the formula~:
\begin {equation}
\label{cond:aff}
\norm{ \fl(M\aff) - M\aff } < 
  {2 \mu(f,x) \over \knorm{f} } 
  \left( \beta(f,x) \maxnorm { \delta A } + \norm { \delta b} 
  \right)
\end {equation}
\par In the same way, we obtain formulas~:
\begin {equation}
\label{cond:proj}
\norm{ \fl(M\proj) - M\proj } < 
  {2 \mu(f,x) \over \knorm{f} } 
  \left( \beta(f,x) \maxnorm{ \delta A } + \beta(f,x) \maxnorm{ \delta x }
         + \norm { \delta b} 
  \right)
\end {equation}

\begin {equation}
\label{cond:pseu}
\norm { \fl(M\pseu) - M\pseu } < 
  {2 \mu(f,x) \over \knorm{f} } 
  \left( \beta(f,x) \supnorm { \delta A } + \norm { \delta b} 
  \right)
\end {equation}

It is possible to make the formulas above more rigorous, by
bounding $\norm{A^{-1}}$ and $\norm{A^{-1} b}$ for $A$, $b$ in 
neighborhoods of $\Df{x}{x}^{-1}$ and $f(x)$, respectively. This
will be done to establish the polynomial time bound for the
algorithm.


\section {First order analysis}
\label {sec:first}
At this time, we can compute the error in $N(f,x)$, up to
$O(\macheps^2)$ and prove Theorem \ref{th:n1}. 
Recall we defined the function $p(n)$ in 
three different cases~:
\begin{align*}
p\aff (n) &=
5 n^2 (g_{cp}(n) + 1) 
\\
p\proj(n) &=
5 (n+1)^2 (g_{cp}(n+1) +1 ) 
\\
p\pseu(n) &= (3.25 (n+1)^3 + 11 (n+1)^2)
\end{align*}
\par
We summarize the results obtained in equations
(\ref{for:A}), (\ref{for:b}),
(\ref{back:aff}), (\ref{back:proj}) , (\ref{back:pseu}) ,
(\ref{cond:aff}), (\ref{cond:proj}) and (\ref{cond:pseu}) in
the following table. Depending on the algorithm, $p = p\aff$,
$p\proj$ or $p\pseu$. In the projective case, $x'$ is considered as
part of matrix $A$~:
\medskip

\begin{center}
{

\begin{tabular}{c|c}
\multicolumn{2}{c}{First order analysis}\\
\multicolumn{2}{c}{}\\
Quantity & Bound \\ \hline
$\maxnorm{ \delta_1 A}$ & 
      $(D + 1 + \max S(f_i)) \sqrt{D} \knorm{f} \macheps$ \\ 
$\maxnorm{ \delta_2 A }$ &
      $p(n) \sqrt{D} \knorm{f} \macheps$\\
$\maxtwonorm {\drond N \over \drond A} $&
      ${2 \mu(f,x) \over \knorm{f}} $\\
$\norm{ \delta_1 b }$&
      $(D+\max S(f_i)) \knorm{f} \macheps $\\
$\norm {\drond N \over \drond b} $&
      ${2 \mu(f,x) \beta(f,x) \over \knorm{f}} $\\
Step \ref{lin:7} &
      $(1 + \beta(f,x))\macheps$ \\ 
\hline 
Total &
      $ ( 2 \mu(f,x) \sqrt{D} (p(n) + D + 1 + \max(S(f_i)) ) $\\
&
      $+ \beta(f,x) (D + \max(S(f_i))) ) + 1 + \beta(f,x)) \macheps $\\
      
\end {tabular}
}
\end{center}
\medskip
\par
In any of the three cases, taking into account that $\beta(f,x) < 1$
(Indeed, $\beta$ is typically much smaller, near an approximate zero), 
and dividing by $\norm{x}  \ge {1 \over 2}$, we obtain the bound~:
\begin{align*}
{ \| N'(f,x) - N(f,x) \| \over \|x\| }
\le
& 4 \mu(f,x) \sqrt{D}
\left( p(n) + 2D + 2 + 2\max(S(f_i)) \right) 
\macheps
\\
&
+ O(\macheps^2)
\end{align*}
\par
This proves Theorem \ref{th:n1} ~.



\section {Construction of the finite precision machine}
\label {sec:constr}
In this section, we show how to construct a Blum-Shub-Smale machine
over $\Bbb Z$ simulating a complex $\epsilon$-machine, and therefore
performing correct arithmetics with the
$1+ \epsilon$ property.
Let $H$ be an integer not less than $2 / \macheps$, where $\macheps$
is fixed. We will prove that
{ \lemma \label{lem:construction}
  An $\epsilon$-machine can be
  simulated by a machine over $\Bbb Z$,
  such that sum, subtraction, multiplication, division, and
  square rooting can be performed in time $O(- \log(\epsilon)
  (\log (- \log \epsilon))^2 )$, provided no overflow or underflow
  occur. 
  \par
  In particular, if $c = \max( -\log(\epsilon) , r + e_0)$ where
  $r$ is the number of floating point operations 
  and $e_0$ is the maximum number of exponent bits in the input
  and in the constants in the machine, then no overflow or
  underflow occur and complex sum, subtraction, multiplication,
  division and square rooting can be performed in time
  $O(c (\log c)^2)$
  } 

{\bf Proof :} The second part of the Lemma follows from the fact
that if we start with $e_0$ bits of exponent, we can only multiply
the exponent by 2 at each floating point operation, so the final
exponent will be at most $2^{e_0 + r} \le 2^c$, so that $c$ bits
will accommodate all the possible values of the exponent during the
computation.
\par
Floating point numbers can be represented by two integers~:
the mantissa and the exponent.
Computation of sum, subtraction, multiplication and division
are easy. We will show how to compute square roots within
the time bound $O(- \log(\epsilon)(\log (- \log \epsilon))^2 )$.
\par
Let $z$ be a real floating-point number, and assume without
loss of generality that $1/2 < z \le 2$. We want to find a
root of ~:
$$
f(x) = x^2 - z
$$
\par
We compute~:
\begin {align*}
f'(x) &= 2x \\
f''(x) &= 2
\end {align*}
\par We will use the affine Newton algorithm in one variable. The invariants
are~:
\begin {align*}
\beta(x) &= {x^2 - z \over 2x} \\
\gamma(x) &= {1 \over 2x} \\
\alpha(x) &= {x^2 - z \over 4 x^2}
\end{align*}
\par
Let $x_0 = {z + 1 \over 2}$, then~:
$$
\alpha(x_0) = {1 \over 4} {(z-1)^2 \over (z+1)^2}
$$
\par
It is easy to verify that the function $\alpha(x_0)$ in function
of $z$ is bounded above by $1 \over 36$ when $z$ is in $[1/2, 2]$.
Also, $\gamma(z) \le 4$.
\medskip
\par
Assume we have a machine with precision $\macheps \le \epsilon / 48$,
$\macheps < 5768$. 
\par
The operator 
$N\aff: x \mapsto x - {f(x) \over f'(x)}= {x + {z \over x} \over 2}$ 
can be computed in two floating point operations.
$$
| \fl ({z \over x}) - ({z \over x}) | < |x| \macheps | {z \over x^2} | 
   \le 2 |x| \macheps
$$
$$
{ |\fl(N\aff(x)) - N\aff(x) | \over |x| } < (1 + 2 \macheps)(1 + \macheps)-1
 < 4 \macheps 
$$
\par
Hence 
$$
{ |\fl(N\aff(x)) - N\aff(x) | \over \sqrt{1 + x^2} } 
 < 4 \macheps 
$$
\par
Thus, we can compute the operator $N\aff: x \mapsto x - {f(x) \over f'(x)}$ 
in such a way that~:
$$
{ \norm {\fl(N\aff(x)) - N\aff(x)} \over \norm{x} } \le \delta
$$
\par
with $\delta \le \epsilon / 12$, with $\delta < 1442$.
We are in the conditions of Theorem \ref{qct:a2:aff}, 
Chapter \ref{ch:condpath}~:
$$
\alpha(x_0) + \delta \gamma(x_0)  < 1/16, \epsilon \gamma(x_0)< 1/384
$$
According to that Theorem, we are able obtain an approximation of
precision $6 \delta < \epsilon / 2$ in
$\log_2 -\log_2 \delta$ iterations, each of these consisting
of 2 floating point operations with precision $\epsilon / 48$.
\par
This does not give us always the correctly rounded result. This algorithm may 
give us a value $x$ at distance $\epsilon / 2$ of
two representable numbers $x_1$ and $x_2$. Those numbers are
the candidates to be the correctly rounded
result. In order to choose the right one, we still have to
compute $\sgn(x^2 - z)$. But this introduces a
very small additional cost. 
\par
Hence, the cost of square-rooting is still $O(\log H (\log \log H)^2 )$,
and Lemma \ref{lem:construction} is proved.


\section {Polynomial time analysis}
\label {sec:poly}
We are proving Theorem \ref{th:np} for the pseudo-Newton method
only. A very similar proof could be given for the other two methods,
by using QR factorization instead of LU factorization.
\par
We will first give rigorous bounds to $\|A^{-1}\|$ and $\|A^{-1} b\|$. This
bounds will be provided by the Lemma~:

{ \lemma \label{lem:rigbounds}
         Assume that~: 
         \begin{align*}
         \norm{\delta A} &< { \knorm{f} \over 4 \mu(f,x) }\\
         \norm{\delta b} &< {\knorm {f} \over 2}
         \end{align*}
         \par Then ~: 
         \begin {align*}
         \norm{ (\Df{x}{x} + \delta A)^{-1} } &<
         {4 \mu(f,x) \over \knorm{f}} \\
         \norm{ (\Df{x}{x} + \delta A)^{-1} (f(x) + \delta b)}
         &< \beta(f,x) + 4 \mu(f,x)
         \end {align*}
         }

Let $A = \Df{x}{x} + \delta A$, and $b = f(x) + \delta b$.
\par
Under the hypotheses of the Lemma, we have~:
$$
\norm{ \delta A } < {1 \over 2 \norm{ \Df{x}{x}^{-1} } }
$$
\par
Hence
$$
\norm{ \Df{x}{x}^{-1} A - I } < {1 \over 2}
$$
\par Inverting, we get~:
$$
\norm{ A^{-1} \Df{x}{x} - I } < {1 \over 2} + {1 \over 4} + {1 \over 8} + \dots
< 1
$$
\par Multiplying by $\Df{x}{x}^{-1}$~:
$$
\norm{ \delta A^{-1}} = \norm{ A^{-1} - \Df{x}{x}^{-1} } 
< \norm{ \Df{x}{x}^{-1}} 
$$
\par It follows that~:
$$
\norm{ A^{-1} } < 2 \norm{ \Df{x}{x} ^{-1} } < {4 \mu(f,x) \over \knorm{f}}
$$
\medskip
\par
For $\norm{A^{-1} b}$, we observe that we have~:
$$ 
\norm{ \delta b } < {\knorm{f}  \over 2}
$$
\par
Now we write~:
\begin {align*}
\norm{ A^{-1} b } &\le
     \norm{ \Df{x}{x}^{-1} f(x)} 
    +\norm{ \Df{x}{x}^{-1}} \norm{ \delta b} \\
& \  +\norm{ \delta A } \norm{ f(x)}
    +\norm{ \delta A } \norm{ \delta b} \\
&\le
    \beta(f,x) 
   +\mu(f,x)
   +2 \mu(f,x)
   + \mu(f,x) \\
&\le \beta(f,x)  + 4 \mu(f,x)
\end{align*}
\par
This proves lemma \ref{lem:rigbounds}
\medskip
\par
It follows from Lemma \ref{lem:rigbounds} that for $A$ in a neighborhood
of radius $\delta A$ of $\Df{x}{x}$ and for $b$ in a neighborhood 
of radius $\delta b$ of $f(x)$, such that $\norm{ \delta A } \le 
\knorm{f} / 4 \mu(f,x)$ and $\norm{ \delta b } \le \knorm{f} / 2$,
the following bounds hold~:
\begin {align*}
\maxtwonorm{ { \partial \over \partial A } M\pseu (A,b)} 
&\le
\norm{  A^\dagger } \norm{ A^\dagger b } \\
&\le
{ 4 \mu(f,x) \over \knorm{f} } (\beta(f,x) + 4 \mu(f,x))
\\
\norm{ { \partial \over \partial b } M\pseu (A,b)}
&\le
\norm{ A^\dagger } \le
{4 \mu(f,x) \over \knorm{f} } 
\end{align*}
\par
We can use the mean value inequality and, for any $A$, $b$ in the
same neighborhood, we obtain~:
\begin{multline}
\label{eq:totalerror}
\norm{ M\pseu(A,b) - Df(x)^\dagger f(x)} 
\le \\
\le
{4 \mu(f,x) \over \knorm{f} } 
(\beta(f,x) + 4 \mu(f,x)) 
\sqrt{n+1}
\maxnorm{ \delta A} 
+
{4 \mu(f,x) \over \knorm{f} } 
\norm{ \delta b} 
\end {multline}
\medskip
\par 
Now, assume the hypotheses of theorem \ref{th:np}. We choose
$\macheps$ so that the following conditions are true~:

\begin{eqnarray}
\label {cond0}
16 \bar \mu (1 + 4 \bar \mu) \sqrt{D}
\macheps(2  D + 2 + 2\max S(f_i) + p(n) ) 
&< \delta
\\
\label {cond1}
8 \bar \mu \sqrt{D} \macheps(2D + 1 + 2\max S(f_i)+p(n)) 
&<
1 
\\
\label{cond2}
\macheps(p(n)) &< 1/2
\\
\macheps H(f) &< 1/2\
\\
 \macheps H(x) &< 1/2
\end{eqnarray}

It is easy to see that condition (\ref{cond0}) implies conditions
(\ref{cond1}) and (\ref{cond2}). By using Lemma \ref{lem:macheps},
we choose~:
\begin{equation}
\label{choice:epsilon}
\macheps 
=
{1 \over  
{32 \over \delta} \bar \mu (1 + 4 \bar \mu) \sqrt{D}
(2  D + 1 + 2\max S(f_i) + p(n) )   
+
2 H(f)
+ 
2 H(x)
}
\end{equation}
\par
This choice of $\macheps$ limits the computing time for each elementary
floating point operation to a polynomial in $-\log \delta$, $\log \bar \mu$,
$\log D$, $\log n$, $\log \max S(f_i)$, $\log H(f)$, $\log H(x)$,
and logarithms of the above.
The total number of floating point operations is already bounded by
a polynomial in $n$, $D$, and $S(f)$. Lemma \ref{lem:construction}
 gives a worst case time
bound that is polynomial in $n$, $D$, 
$\log H(f)$, $\log H(x)$, $S(f)$, $\log \bar \mu$ and $- \log \delta$,
as stated in the theorem. 
\medskip
\par
It remains to prove that the result obtained is within error $\delta$
of the correct pseudo-Newton iteration.
\par
Equation (\ref{back:pseu}), together with condition (\ref{cond2})
becomes~:
$$
\maxnorm{\delta_2 A} \le \macheps(p\pseu(n)) (\maxnorm{A} + \maxnorm{\delta A})
$$
\par
Adding equation (\ref{for:A}), and knowing that $\maxnorm{A} \le \knorm{f}
\sqrt{D}$, we obtain~:
$$
\maxnorm{\delta A} \le 
\knorm{f} \sqrt{D} \macheps(D + 1 + \max S(f_i))
+
\macheps(p\pseu(n)) (\maxnorm{A} + \maxnorm{\delta A})
$$
\par
Rearranging,
$$
\maxnorm{\delta A} \le 
{
\knorm{f} \sqrt{D} \macheps(D + 1 + \max S(f_i) + p\pseu(n))
\over
1 - 
\macheps(p(n))
}
$$
\par
Introducing again condition (\ref{cond2}), we get~:
$$
\maxnorm{\delta A} \le 
2 \knorm{f} \sqrt{D} \macheps(D + 1 + \max S(f_i) + p\pseu(n))
\le { \knorm{f} \over 4 \bar \mu }
$$
\par
The last inequality following from condition (\ref{cond1}).
For $\norm{ \delta b }$, we had the bound (\ref{for:b})~:
$$
\norm{ \delta b } \le \knorm{f} \macheps(D + \max S(f_i))
 < \knorm{f} / 2
$$
\par
Hence, we can use bound (\ref{eq:totalerror}). The
total error is less than~:
$$
8 \bar \mu (\beta + 4 \bar \mu) \sqrt{D}
\macheps(D + 1 + \max S(f_i) + p\pseu(n))
+
$$
$$
+
4 \bar \mu  \macheps(D + \max S(f_i)) + (1 + \beta) \macheps
$$
\par
Since $\beta \le 1$, the total error of the algorithm is
less than~:
$$
8 \bar \mu (1 + 4 \bar \mu) \sqrt{D}
\macheps(2D + 2 + \max S(f_i) + p\pseu(n))
$$
\par
According to condition (\ref{cond0}), this is less than $\delta / 2$,
so that the error over $\norm{x}$ is less than $\delta$, qed. 





\chapter {Gap theory and estimate of the condition number}
\label   {ch:gap}

\begin {abstract}
In this chapter, gap theorems are introduced. The
condition number of systems and paths is estimated in terms
of heights. Newton iteration is used to decide if a root
is rational. A result on root separation is also stated.
\end   {abstract}



\section {Introduction}
\label{sec:gap:intro}
Let $\Hd$ be the space of all systems of $n$ homogeneous
polynomial equations of degree $d = (d_1, \dots , d_n)$ in
$n+1$ variables $(x_0 , \dots , x_n)$, with complex
coefficients. Let $\Sigma$ be the locus of all systems 
in $\Hd$ such that there is a solution $x \ne 0$, $f(x)=0$
such that $Df(x)$ does not have full rank. $\Sigma$ is
an algebraic variety, called the {\em discriminant variety}.
Systems belonging to $\Sigma$ are called {\em degenerate}.
\par 
Let $f = (f_1 , \dots , f_n) \in \Hd$ be non-degenerate, $n \ge 2$, 
$D = \max d_i \ge 2$. If we require $f$ to have
only integer (or rational, or gaussian integer, or gaussian rational) 
coefficients,
then we will be able to obtain a certain number of conclusions about 
the roots of the system. 
\medskip
\par
In this chapter, we are interested about two kind of bounds~: Bounds
on the minimal distance between two different roots, and bounds
on some {\em height} of rational roots. By {\em height}, we understand
a measure of the number of bits necessary to represent
a point in projective space~: 
\par
If $a \in {\Bbb Z}$, we define the height $H(a) = |a|$. For
Gaussian integers, we define~: $H(a + bi) = H(a) + H(b)$. Then
we have $H(x \pm y) \le H(x) + H(y)$ and $H(x y) \le H(x) H(y)$. 
This is not the standard definition of height.
\par
Let $z$ be a point in ${\Bbb C}^{n+1}$, considered as a point in
projective space. We say that $z$ is rational if there is 
$\lambda \in {\Bbb C}$ such that $\lambda z \in {\Bbb Q}^{n+1}$.
By multiplying by the smallest common multiple, we can assume
without loss of generality that $z$ has integer coordinates, without
common factor. Then we set the height $H(z) = \max |z_j|$. 
\par
If $f_j$ is a polynomial with rational
coefficients, we define $H(f_j)$ as the height of the vector of
its coefficients. The height of the system $f$ is the maximum of
$H(f_j)$.
\par
This definition of height is not adequate to all the situations
we will have to face, and we will see definitions more suitable
to several particular cases.
\par
\medskip
In Shub and Smale \cite{BEZI}, and in chapter \ref{ch:condpath},
the complexity of path-following was bounded in terms of a
condition number $\mu$.
It was proved by
Shub and Smale in \cite{BEZI} that the condition number
$$
\mu(f) = \max_{f(\zeta)=0} \knorm{f} \norm{ Df(x)^{-1} 
         \diag(\norm{x}^{d_i - 1} \sqrt{d_i})}
$$
\par
verifies $\mu(f) = 1 / \rho(f)$, where $\rho(f)$ is the
Maximum distance in Kostlan's metric 
between $f$ and the discriminant variety $\Sigma$, along
a fiber $\{ f : f(\zeta _i)=0 \}$.
This implies the inequality~:
$$
\mu(f) \le {1 \over \dproj(f, \Sigma)}
$$
\par
A consequence of that is the existence of a finite {\em complexity exponent} 
$d(\Sigma)$ and of a {\em geometric
condition number} $\mu(\Sigma)$ depending solely on $d$ and $n$, 
such that~:
{\theorem \label{th:mu1}
          Let $f \in \Hd$ have gaussian
          integer coefficients. 
          Then either $f \in \Sigma$, either
          $$
          \mu(f) \le \mu(\Sigma) H(f)^{d(\Sigma)}
          $$
          \par
          where we can set~:
          \begin {align*}
            d(\Sigma) &= n \prod d_j \sum d_j \ge \sum r_i
           \\
            \mu(\Sigma)
            &=
            \sqrt{D!} d(\Sigma)
            \left(
            3 n! n (d(\Sigma) + \max S(f_i)) (2 \sum d_j)^n \prod(d_j - 1)
            \right)
            ^{d(\Sigma)}
           \end {align*}
         } 
\par
It is immediate from Theorem \ref{th:mu1} that~:
{\corollary \label{cor:mu1}
             There is a universal polynomial $M_{\mu}$ such that
             if $\mu(f)$ is finite, then~:
             $$
             \mu(f) < 2 
               ^ { M_{\mu} (n, D, \prod d_i, \log H(f), \log \dim \Hd)}
             $$
             }
\par
Moreover, it is possible to obtain a result about conditioning
of a whole path in projective space. Indeed, it will be necessary
to extend the path to a {\em real} line, embedded in projective 
space. Generically, this line does not cut the discriminant variety.
If we denote by $\mu([f_0,f_1])$ the condition number of the path
$[f_0,f_1]$, and write $f_t = (1-t)f_0+t f_1$, then we will prove~: 
{\theorem \label{th:mu2}
          There is a proper variety $\Sigma_0$ 
          in $\Hd \times \Hd$ considered
          as a real projective space, so that for $f_t \not \in \Sigma_0$
          the following estimate is true~:
          $$
          \mu(f_t) \le \mu(\Sigma_0) H(f_t)^{d(\Sigma_0)}
          $$
          \par
          where we can set~:
          \begin {align*}
           d(\Sigma_0) &= 2 n \prod (d_j + 1)^2 (1 + \sum d_j)^2
           \\
           \mu(\Sigma_0)
              &=
              \sqrt{D!}
              d(\Sigma_0)
          \\
          & \  \times
              \left(
                 3
                  2^D
                 n! n
                 (d(\Sigma_0) + \max S(f_i) - 1)
                 \prod (d_j - 1)
                 (-1 + 4 \sum d_j)^{2n+1}
              \right)
              ^ {d(\Sigma_0)}
          \end{align*}
          }
\par
Theorems \ref{th:mu1} and \ref{th:mu2} are obtained by estimating
the height and degree of polynomials defining $\Sigma$ and $\Sigma_0$. 
\medskip
\par
Besides the estimate on the number of approximate Newton steps
defined in chapter \ref{ch:condpath}, several other useful
 results can be obtained in terms of $\mu$ or
$\log \mu$. 
\par
We will need the notations and conclusions of chapters \ref{ch:condpath}
and \ref{ch:newton}. Since we will be using mainly the pseudo-Newton
operator, we recall some definitions~:
\begin {align*}
\beta(f,x) &=
{1 \over \norm{x}}
\norm{ Df(x)^\dagger f(x)} 
\\
\gamma(f,x) &=
\norm{x}
\max_k \left\{ 1 , 
   \left(
   { \norm{ Df(x)^\dagger D^kf(x) } \over k! }
   \right) ^{1 \over k-1}
      \right\}
\\
\alpha(f,x) &= \beta(f,x) \gamma(f,x)
\end{align*}
\par    
{\theorem \label{main1}
       There is a machine over $\Bbb Z$
       such that, given input ($f \in \Hd$,
       $x_0 \in {\Bbb C^{n+1}}$), such that
       $f$ is non-degenerate, $\alpha(f,x_0) \le 1/16$, and
       $\zeta$ is the zero associate to $x_0$, returns
       $\zeta$ if $\zeta$ is rational, and fails otherwise.
       Moreover, the execution time of that program
       is bounded by a polynomial in
       $\prod d_i$, $n$, $D$, $\log H(f)$, and $\dim \Hd$. 
       }
\par
The condition on $\alpha$ is the condition of the 
Theorem \ref{qct:a2:pseu}, Chapter \ref{ch:condpath}. Together
with the construction of the approximate Newton operator 
(Theorem \ref{th:np}, Chapter \ref{ch:newton}), 
theorem \ref{qct:a2:pseu}, Chapter \ref{ch:condpath}
can be used to generate a sequence $x_i$
quadratically convergent to the nearest zero $\zeta$~:
$$
d(x_i,\zeta) \le   
    \max \{2^{-2^i-1},
    6 \epsilon \}
$$
\par
where $\epsilon$ is the {\em error} of the approximate Newton operator.
The cost of obtaining $x_i$ was found to be a polynomial in $\log H(f)$,
$\dim \Hd$, $\log \mu(f,\zeta)$ and 
$- \log \epsilon$. We will use this analysis
to prove the theorem.
\medskip
\par

Also, the following result on separation of roots comes naturally in
terms of $\gamma$, hence of $\mu$~:
{\theorem \label{th:gamma}
          Let $f \in \Hd$, and assume that $x_1$, $x_2$ are different
          roots of $f$. Then $\dproj(x_1,x_2) \ge
          \sin \tan^{-1} 1 / 2\gamma(f,x_1)$ }

\par
It follows that $\dproj(x_1,x_2) \ge {1 \over \sqrt{2} D^{3/2} \mu(f)}
\ge {1 \over \sqrt{2} D^{3/2} \mu(\Sigma) H(f)^{d(\Sigma)}}$.


\section {The Macaulay resultant}
\label {sec:mac}
{\theorem[Macaulay \cite{MAC}] \label{th:resultant}
        Let $\mathcal H$ be the space of all the systems
        $f = (f_0, \dots , f_n)$ of homogeneous polynomials 
        of degree $d = (d_0, \dots , d_n)$
        in variables $x = (x_0, \dots , x_n)$.
        Let $\Sigma$ be the locus in $\mathcal H$ of systems $f$
        having a non-trivial solution $x$, $x \ne 0$, $f(x)=0$.
        Then ~:
        \par
        \begin{enumerate}
           \item \label{it:res:2}
              The locus $\Sigma$ is an algebraic variety,
              the zero set of
              a polynomial $R$ of degree $\sum_i \prod_{j \ne i} d_i$ 
              in the coefficients of $f$, given by~:
               $$R(f) = \gcd \det A_j$$
              \par
              where $A_j$ are matrices to be defined, of size
              $\binomial{\sum d_j}{n}$, and with entries  
              either coefficients of $f$, either zero.
           \item \label{it:res:3}
              There is a submatrix $B_j$ of $A_j$, such that~:
               $$
               R(f) = { \det A_j \over \det B_j }
               $$ 
           \item \label{it:res:4} Poisson formula~:
              If we fix some $f_1, \dots , f_n$ non-singular, 
              then $R$ is given, as a polynomial in the coefficients
              of $f_0$ and up to a multiplicative constant,
              by~:
               $$
               R(f_0) = \prod_{f_1(\zeta) = 0 , \dots , 
                               f_n(\zeta) = 0 } f_0(\zeta)
               $$
        \end{enumerate}
        }

\par
  The polynomial $R$ is called the {\em resultant} 
  of the (undetermined) system $f$. It follows from Bezout theorem
  that the resultant has degree $d_1 \dots d_n$ in the coefficients 
  of $f_0$. 
\par
  An important particular case is when $f_0$ is linear,
  of the form~: $f_0(x) = u x$. In that case, we write~:
  $$
  R_u(f_1, \dots , f_n) = R(f_0 , \dots , f_n)
  $$\glossary{$R_u(f)$&$u$-resultant of a system $f$ of $n$ polynomials}
\par
  When $f_1, \dots f_n$ are fixed, 
  $R_u$ is called the $u$-resultant of $f_1, \dots , f_n$ and
  is a polynomial in $u_0, \dots , u_n$.
\par
  In this section, we follow some of the ideas in Macaulay's
  paper \cite{MAC} in order to construct matrices $A_j$ and
  to sketch a proof of Theorem~
  \ref{th:resultant}, but with a different notation.
\medskip
\par
\paragraph {Idea of the Proof of Theorem \ref{th:resultant}~:}
  For reasons that will become apparent later, we set
  $\mathcal D = \left( \sum d_j \right) - n$
  \par
  Consider the condition~:
\begin {equation} 
  \exists x \ne 0 : f(x) = 0
  \label{c1}
\end {equation} 
  \par
  It is equivalent to~:
\begin {equation} 
  \exists x \ne 0 : 
  \forall g = (g_0, \dots , g_n), \ \text{deg}\  g_j = \mathcal D - d_j, \ 
  \sum f_j(x) g_j(x) = 0
  \label{c2}
\end{equation}
  \par
  Proof: (\ref{c1}) $\Rightarrow$ (\ref{c2}) is trivial. Assume $x$ is
  given by (\ref{c2}).
  There is $i$ with $x_i \ne 0$. Set
  $g_j = \lambda_j {x_i}^{\mathcal D - d_j}$. In other words~: 
  $$
  \forall \lambda,\  \sum \lambda_j {x_i}^{ {\mathcal D} - d_j} f_j(x) = 0
  $$
  \par
  Changing to coordinates $\lambda_j ' = \lambda_j {x_i}^{ {\mathcal D} - d_j}$,
  we obtain~:
  $$
  \forall \lambda',\  \sum \lambda_j' f_j(x) = 0
  $$
  \par
  It follows that $f_j(x) = 0$.
  \medskip 
  \par
  Now we introduce some notation. 
  $M_d, d \in {\Bbb N}$ is the linear space generated by all 
  monomials of degree $d$ in $n+1$ variables. $\rho_d$ is the
  $d$-uple embedding~:
  $$
  \begin{array}{lrcl}
  \rho_d : & {\Bbb C}^{n+1} & \rightarrow & M_d \\
	   &        x       & \mapsto     & (x^{\alpha_0}, \dots, x^{\alpha_N})
  \end{array}
  $$
  \par
  Where $N$ is the dimension of $M_d$, and $\alpha_i$ ranges through all
  possible monomials of degree $d$.
  $$
  N = \dim M_d = \binomial{n+d}{n}
  $$
  \par
  There is a natural isomorphism between the dual of $M_d$ and
  the linear space of homogeneous polynomials of degree $d$~:
  $$
  {\rho_d}^* : \tilde f \mapsto f , f(x) = \tilde f \rho_d (x)
  $$
  \par
  When $d = (d_0 , \dots , d_n)$, those maps can be extended as
  follows~:
  $$
  \begin{array}{lrcl}
  \rho_d : &
  {\Bbb C}^{n+1} &
  \rightarrow &
  M_{d_0} \times \dots \times M_{d_n} \\
  &
  x &
  \mapsto &
  \left( \rho_{d_0}(x), \dots , \rho_{d_n(x)} \right) 
  \end{array}
  $$
  $$
  \begin{array}{lrcl}
  {\rho_d}^* : &
  \left(M_{d_0} \times \dots \times M_{d_n}\right)^*&
  \rightarrow &
  \Hd \\
  &
  \left( \tilde f_0 , \dots , \tilde f_n \right) &
  \mapsto &
  \left( \rho_{d_0}^*(f_0), \dots , \rho_{d_n}^*(f_n) \right) 
  \end{array}
  $$
  \par 
  The latest one is still an isomorphism of linear spaces.
  \par
  Multiplication of polynomial $g_0$ of degree $d_0'$
  by a fixed polynomial $f_0$
  of degree $d_0$ corresponds to a linear mapping~:
  $$
  \begin{array}{lrcl}
   \hat f_0 : & {M_{d_0'}}^* & \rightarrow & {M_{d_0 + d_0'}}^* \\
   & \tilde g_0 & \mapsto & \tilde g_0 \hat f_0 
  \end{array}
  $$
  \par
  Where
  $$
  (\tilde g_0 \hat f_0) \rho_{d_0 + d_0'} (x)
  =
  g_0(x) f_0(x)
  $$
  \par
  We write $\tilde g_0 \hat f_0$ in that order because
  $\tilde g_0$ is a row vector (a covector).
  \medskip
  \par

  Also, the sum of two polynomials of same degree $\mathcal D$ is
  associated to the sum in ${M_{\mathcal D}}^*$. So we can define the
  operator corresponding to~:
  $$
  g_0, \dots , g_n \mapsto f_0 g_0 + \dots + f_n g_n
  $$
  \par
  whenever the $f_i g_i$ have the same degree ; in our case
  we will want degree $\mathcal D$ (we will see why shortly).
  So we get a linear operator $\hat f$~:
  $$
  \begin{array}{lrcl}
  \hat f : &
  {M_{\mathcal D - d_0}}^* \times \dots \times {M_{\mathcal D - d_n}}^* &
  \rightarrow &
  {M_{\mathcal D}}^* \\
  &
  \tilde g_0, \dots , \tilde g_n &
  \mapsto &
  \tilde g_0 \hat f_0 + \dots + \tilde g_n \hat f_n \\
  &&& = (\tilde g_0 , \dots , \tilde g_n) \hat f \\
  &&& = \tilde g \hat f 
  \end{array}
  $$
  \par
  Here, $\hat f$ can be seen as a matrix with more
  rows than columns. It defines a bilinear mapping 

  $$
  \tilde g, \tilde x \mapsto \tilde g \hat f \tilde x
  $$

  \par Indeed, we are speaking about a tri-linear map, if we consider
  the coefficients of $f$ as input.
  \par
  We get the following conditions, clearly equivalent to conditions 
  ~(\ref{c1}) and~(\ref{c2})~:
\begin {equation}
  \exists x : 
  \forall \tilde g ,
  \tilde g \hat f \rho_{\mathcal D} (x) = 0
  \label{c3}
\end{equation}
\begin{equation} 
  \exists x :
  \hat f \rho_{\mathcal D} (x) = 0
  \label{c4}
\end{equation} 
  \par
  There is a very convenient condition for
  (\ref{c4}) to be true.
  \medskip
  \par
  We define the subspaces $M^{(i,j)}$ of ${M_{\mathcal D}}^*$ as follows~: 
  let let $L(i,j)$ be the
  set $\{ j+1, \dots , i-1 \}$ or eventually
  the set $\{ j+1, \dots, n , 0 , \dots , i-1 \}$.
  In particular, $L(i,0) = \{1, \dots , i-1\}$.
  \par
  We define $M^{(i,j)}$ as the subspace of $M_{\mathcal D}$ of
  monomials of degree $< d_k$ in $x_k$ for $k$ in $L(i,j)$, and
  of degree $\ge d_i$ in $x_i$.
  \par
  Because we set $\mathcal D = \left( \sum d_j \right) - n$,
  We can write~:
  $$
  {M_{\mathcal D}}^* \simeq M^{(0,j)} \times \dots \times M^{(n,j)}
  $$
  \par
  There is a natural embedding of $M^{(i,j)}$ into ${M_{\mathcal D - d_I}}^*$
  given by the division by ${x_i}^{d_i}$.
  \par
  This extends to embeddings $I_j$ of ${M_{\mathcal D}}^*$ into
  ${M_{\mathcal D - d_0}}^* \times \dots {M_{\mathcal D - d_n}}^*$~:
  $$
  \begin {array}{ccccccc}
  {M_{\mathcal D}}^*
       & \rightarrow & M^{(0,j)} & \times & \dots & \times & M^{(n,j)}\\
	     & \searrow    &\downarrow &        & \dots &        & \downarrow\\
	     & I_j         & {M_{\mathcal D - d_0}}^*
		& \times & \dots & \times &
			{M_{\mathcal D - d_n}}^*\\
  \end {array}
  $$
  \par
  We denote by $A_j = I_j \hat f$ the linear operator
  $\tilde g \mapsto \tilde g I_j \hat f$
  (notice again that $\tilde g$ is a row vector, so we write $\tilde g I_j$ 
  for $I_j$ applied to $\tilde g$).
  This definition gives us a square matrix
  $A_j$ for every $j$. $\det A_j$ is a polynomial in the
  coefficients of $f$.
  \par
  We can finally define the resultant of $f$ as:
  $$
  R = \gcd (\det A_j)
  $$\glossary{$R(f)$&Resultant of a system $f$ of $n+1$ polynomials}
  \par
  where $\det A_j$ are considered as polynomials in variables $\tilde f$.
  The condition~:
\begin {equation}
  R(\tilde f) = 0
  \label{c5}
\end{equation} 
  \par
  is equivalent to conditions (\ref{c1}) to (\ref{c4}).
  It follows from the construction that condition
  (\ref{c4}) implies condition (\ref{c5}). 

  We will use the Lemma~:
{\lemma \label{lem:degree}
        Let $f_1, \dots , f_n$ be non-degenerate. Then 
        the numerator
        $R(\tilde f)$ is a polynomial of degree $d_1 d_2 \dots d_n$ in
	the coefficients of $f_0$.}
  \medskip
  \par
  Lemma \ref{lem:degree} is proved in \cite{MAC}, pages ~10 and ~11.
  The idea of the
  proof is to show that what we call $\det A_j {\det A_0}^{-1}$ contains no
  coefficient of $f_0$ in the denominator. (We will not perform
  that computation here). It follows that
  the product of all the irreducible factors of $\det A_0$ containing
  coefficients of $f_0$ divides $R(f)$. Therefore, the degree of $R(f)$
  in the coefficients of $f_0$ is not less than the degree of
  $\det A_0$ in those coefficients. But since $R(f)$ divides
  $\det A_0$, those degrees are equal ~; by construction of
  $A_0$, they are equal to $\dim M^{(0,0)} = d_1 d_2 \dots d_n$.
  \medskip
  \par
  Assuming Lemma \ref{lem:degree}, when we specialize the coefficients
  of $f_1, \dots , f_n$, generically, we have the following
  expression, up to a multiplicative constant~:
  $$
  R(f) = \prod f_0( \zeta_i )
  $$
  \par
  where $\zeta_i$ ranges over all the roots of $f_1, \dots , f_n$.
  Indeed, it is clear that $f_0( \zeta_i )$ divides 
  $R(f_0, f_1, \dots , f_n)$ as a polynomial in $\tilde f_0$
  ($\zeta_i$ is fixed, so $f_0(\zeta_i)$ is a polynomial of
  degree 1 in $\tilde f_0$).
  Just note that $f_0 ( \zeta) = 0$ for $\zeta$ solution of
  $f_1, \dots , f_n$ implies that $R(f) = 0$. Hence according to
  Hilbert's Nullstellensatz, $\prod f_0(\zeta_i)$
  divides $R(f)^k$, as polynomials in $\tilde f_0$, for some $k$. 
  But since by hypothesis the roots $\zeta_i$ are disjoint, 
  $\prod f_0(\zeta_i)$ cannot have a multiple factor, so it
  has to divide $R(f)$. 
  \par 
  Moreover, by
  Bezout theorem, there are $d_1 d_2 \dots d_n$ different roots
  $\zeta_i$. Using Lemma \ref{lem:degree}, 
  the two polynomials have the same
  degree, so they are equal up to a multiplicative constant.
  This implies item (\ref{it:res:4}) of Theorem \ref{th:resultant}.
  \medskip
  \par
  Using Item \ref{it:res:4}, the condition $R(\tilde f) = 0$ 
  implies that there is $\zeta$ such that $f(\zeta)=0$.
  \par
  If we add the degree in the coefficient of each $f_i$, we conclude
  that the total degree of each $R(f)$ is $\sum_i \prod_{j \ne i} d_j$.
  This will concludes the proof of Item \ref{it:res:2} of
  Theorem \ref{th:resultant}.


  We still have to sketch the proof of item \ref{it:res:3}
  of Theorem \ref{th:resultant}.
  \medskip 
  \par

  \paragraph{Proof of Item (\ref{it:res:3}) of Theorem \ref{th:resultant}~:}
  Let $V^* = \cap_{j,k} \ker I_k - I_j \subset {M_{\mathcal D}^*}$. Let
  $W^*$ be its orthogonal complement. Spaces $V^*$ and $W^*$ are
  subspaces of $M_{\mathcal D}^*$, and $V^*$ is spanned by all monomials
  $x^\alpha$ with only one $\alpha_i \ge d_i$. Therefore, it has
  dimension $\sum_i \prod_{j \ne i} d_j$. 
  \par
  Let $A_k = I_k \hat f$ as above, and let $B_k$ be the sub-matrix
  of $A_k$ corresponding to rows and columns in $W^*$ and $W$,
  respectively. We want to prove that~:
  $$
  R(f) = { \det A_k \over \det B_k }
  $$
  \par
  It is enough to show that $ { \det A_k \over \det B_k } $ is 
  a polynomial. For in that case, $R(f)$ and ${ \det A_k \over \det B_k } $
  have the same degree ; by definition of $R$, there is a polynomial
  $b(f)$ such that $R(f) b(f) = \det A_k$, and that polynomial is clearly
  of the same degree than $\det B_k$. Therefore, $b(f) = \det B_k$, up
  to a multiplicative constant. This implies Item \ref{it:res:3}.
  \par
  We write~:
  $$
  A_k = 
  \left[
  \begin {array}{cc} M & P \\ N & B_k \end{array} 
  \right]  
  $$
  \par
  where $M \in L(V,V)$, $N \in L(W,V)$, $P \in L(V,W)$ and
  of course $B_k \in L(W,W)$. We also define~:
  $$
  \tilde B_k
  =
  \left [
  \begin {array}{cc} I_V & 0 \\ 0 & B_k \end{array} 
  \right ]  
  $$
  \par
  We consider the operator $p = A_k {\tilde B_k} ^{-1}$ in $M_{\mathcal D}$. 
  Let $e_j$ be a basis (column) vector. Then either $e_j \in V$, either
  $e_j \in W$. 
  \par
  If $e_j \in V$, then ${\tilde B_k}^{-1} e_j = e_j$, and hence
  $A_k {\tilde B_k}^{-1} e_j$ is a vector whose coordinates are
  coefficients of $f$. 
  \par
  If $e_j \in W$, then ${\tilde B_k}^{-1} e_j \in W$, and~:
  $$
  A_k {\tilde B_k}^{-1} e_j
  =
  e_j
  +
  \left [
  \begin {array}{c} P \\ 0 \end{array} 
  \right ]  
  {B_k}^{-1}
  e_j 
  $$ 
  \par
  Therefore, $p$ has the form~:
  $$
  p
  =
  \left [
  \begin {array}{cc} M & P' \\ 0 & I_W \end{array} 
  \right ]  
  $$
  \par
  The matrix $M$ is non-singular, since the coefficients in
  ${x_i}^{d_i}$ appear in the main diagonal of $M$, and only
  there. Therefore, $\det M$ is a non-zero polynomial.
  \par
  It follows that $\det p = \det M \det I_W = \det M$,
  and therefore $\det p$ is a polynomial in the coefficients
  of $f$. Moreover,
  $$
  \det p =
  { \det A_k \over \det \tilde {B_k} }
  = 
  { \det A_k \over \det B_k }
  $$
  \par
  This concludes the sketch of the proof of Theorem \ref{th:resultant}.



\section {Gap Theorems}
\label{sec:canny}
   Let $f = (f_1, \dots , f_n) \in \Hd$ be non-degenerate, with integer
   coefficients of absolute value less than some integer $H(f)$.
   Let $D = \max d_j$.
   Let $x$ be a solution of $f$. Assume $|x_i|$ and $|x_j|$ are
   non-zero. We will show that $|x_i| \over |x_j|$ is bounded
   away from zero. The following is a version of Canny's gap
   theorem \cite{CANNY}.


{\theorem [Canny] \label{th:canny}
          In the conditions above,
          $$
          { |x_i| \over |x_j| }
          \ge
          \left(
            3 H(f) \binomial{\sum d_j}{n}
          \right)
          ^{-(n+1)\prod d_j}
          $$ }

   This is also true when the coefficients of $f$ are gaussian integers.
   We also want to be able to decide when $x$ is a rational solution
   (i.e., all the $|x_i| \over |x_j|$ are rational). Almost the same
   proof of Canny's theorem will lead to~:

{\theorem \label{th:gap}
          Let $f(x) = 0$, and $|x_i|, x_j \in {\Bbb N}_*$ have
          no common factor. Then~:
          $$
          |x_i|, x_j \le
          \left(
            3 H(f) \binomial{\sum d_j}{n} 
          \right)
          ^{(n+1) \prod d_j}
          $$
          }


  In order to prove the theorems, 
  we will need some alternative definitions of Height.
  First of all, assume that $H$ is defined in a ring $R$. The main
  examples are the integers and the Gaussian integers. Assume 
  furthermore that~:
\begin{align*}
H(1) &= H(-1) = H(i)  = H(-i) = 1
\\
H(a+b) &\le H(a) + H(b)
\\
H(ab) &\le H(a) H(b)
\end{align*}
\par
  Let $K$ be the field of fractions of $R$, and let $L = K[f_1, \dots, f_N]$
  where the $f_i$ are indeterminates (transcendental) over $K$.
  If $a$ is an integer in $L$, 
  $a$ can be written
  in the form $a = \sum a_I f^I$, where $a_I \in R$ and $I$ are
  multi-indices. We define a height $B$ on the ring of integers
  of $L$~: 
$$
B(\sum a_I f^I) = \sum H(a_I)
$$\glossary{$B$&A different definition of height}
\par
The following properties of $B$ are obvious~:
\begin{align*}
B(1) &= B(-1) = B(i) = B(-i) = 1
\\
B(g+h) &\le B(g) + B(h)
\\
B(gh) &\le B(g) B(h)
\end{align*}
\par
  We also want to extend this definition to integral polynomials in $L[t]$, 
but in a different way. We define~:
$$
C ( t^d + p_{d-1} t^{d-1} + \dots + p_0 ) = 
\max \left(B(p_i)^{1 \over d - i}\right)
$$\glossary{$C$&A different definition of height}
\par
The following facts were proved in \cite{CANNY} for the 
particular case $L = K = \Bbb Q$.

{\lemma \label{lem:C} 
  Let $p, q$ integral polynomials in $L$ and let $M$ be a $n \times n$
  matrix with integral entries in $L$.
  \begin{align*}
  C(pq) &\le C(p) + C(q)
  \\
  C(p/q) &\le C(p) + 2 C(q)
  \\
  C(det M - t I) &\le n \max B(M_{ij})
  \end{align*}
  }

\paragraph {Proof of lemma \ref{lem:C}~:}


\par
Part 1~:
We write~:
\begin{align*}
p(t) &= t^m + p_{m-1} t^{m-1} + \dots + p_0
\\
q(t) &= t^n + q_{n-1} t^{n-1} + \dots + q_0
\\
r(t) &= p(t) q(t) = t^{m+n} + r_{m+n-1} t^{m+n-1} + \dots + t_0
\end{align*}
\par where~:
$$
r_i = \sum_{0 \le j \le m, 0 \le i-j \le n} p_j q_{i-j}
$$
\par
By definition,
\begin{align*}
C(pq) &= \max B\left ( \sum p_j q_{i-j} \right)^{1 \over n+m-i}
\\
C(pq) &\le \max \left ( \sum B(p_j) B(q_{i-j}) \right)^{1 \over n+m-i}
\end{align*}
\par
So there is $i$ such that~:
$$
C(pq)^{n+m-i}
 \le
 \sum C(p)^{m-j} C(q)^{n-i+j} 
$$
\par
On the other hand,
$$
( C(p) + C(q) )^{n+m-i}
= 
\sum_{i-n \le j \le m}
\binomial{n+m-i}{m-j} C(p)^{m - j} C(q)^{n-i+j}
$$
\par
Comparing term by term,
$$
C(pq)^{n+m-i}
\le
( C(p) + C(q) )^{n+m-i}
$$
\par
Hence
$$
C(pq) \le C(p) + C(q)
$$ 


\medskip
\par
Part 2~:
\begin{align*}
p(t) &= t^m + p_{m-1} t^{m-1} + \dots + p_0
\\
q(t) &= t^n + q_{n-1} t^{n-1} + \dots + q_0
\\
r(t) &= p(t) / q(t) = t^{m-n} + r_{m-n-1} t^{m-n-1} + \dots + t_0
\end{align*}
\par
Since $p$ and $q$ are monic, the quotient $r(t)$ can be computed
by the following recurrence~:
\begin{align*}
r_{m-n} &= 1
\\
r_{m-n-j-1} &= p_{m-j-1} - \sum_{0 \le i \le j} r_{m-n-i} q_{n+i-j-1}
\end{align*}
\par
We have~:
\begin{align*}
B(r_{m-n-j-1}) 
&\le B(p_{m-j-1}) + \sum_{0 \le i \le j} B(r_{m-n-i}) B(q_{n+i-j-1})
\\
B(r_{m-n-j-1}) 
&\le C(p)^{j+1}
+ \sum_{0 \le i \le j} 
     B(r_{m-n-i}) 
     C(q)^{j+1-i}
\end{align*}
\par
We proceed by induction on $i$. 
Assume that $B(r_{m-n-j}) \le (C(p) + 2 C(q))^j$ for all
$j \le i$. This is trivially true for $i=0$. By induction, 
\begin{align*}
B(r_{m-n-j-1}) 
&\le C(p)^{j+1}
+ \sum_{0 \le i \le j} 
     ( C(p) + 2 C(q) )^i 
     C(q)^{j+1-i}
\\
&\le C(p)^{j+1}
+ C(q) \sum_{0 \le i \le j} 
     ( C(p) + 2 C(q) )^i 
     C(q)^{j-i}
\\
&\le C(p)^{j+1}
+ C(q) \sum_{0 \le i \le j} 
     2^{i-j} ( C(p) + 2 C(q) )^j 
\\
&\le C(p)^{j+1}
+ 2 C(q) ( C(p) + 2 C(q) )^j 
\\
&\le C(p) (C(p)  + 2 C(q))^j
+ 2 C(q) ( C(p) + 2 C(q) )^j 
\\
&\le
( C(p) + 2 C(q) )^{j+1} 
\end{align*}
\par
Thus,
$$
C(r) \le C(p) + 2 C(q)
$$ 
\medskip
\par
  Part 3~:
  $$
  \det(M-tI) = t^n + a_{n-1} t^{n-1} + \dots + a_0
  $$
  \par
  Coefficient $a_i$ is the sum of $n^{n-i}$ products of $n-i$
  entries of $B$-height less than $B(M)$, 
  so we have~: $|a_i| \le (n B(M))^{n-i}$.
  \par
  $$
  C(\det(M - tI)) \le n B(M)
  $$

{\lemma \label{lem:B}  
      Let $f = (f_0, \dots, f_n)$ be an indeterminate system of
      homogeneous equations of degree $d_0, \dots, d_n$
      in $n+1$ variables, with integer (resp. Gaussian integer)
      coefficients. Let $\tilde f$ denote the coefficients 
      of $f$, and let $L = {\Bbb Q}[\tilde f]$ 
      (resp. $L = {\Bbb Q}[i][\tilde f] $). 
      \par
      Then~:
       $$
       B(R(\tilde f)) \le 
       \left( 3 \binomial{\sum d_j}{n} \right) ^ 
        {\deg R}
       $$
      \par
       If $f_1, \dots , f_n$ are determinate, then~:
       $$
       B(R(\tilde f_0)) \le 
       \left( 3 \binomial{\sum d_j}{n} H(f_1, \dots , f_n) \right) ^ 
        {\deg R}
       $$
      }

\par
As it was proved in Theorem \ref{th:resultant}, $\deg R =
\sum_i \prod_{j \ne i} d_j$. 
Theorems \ref{th:canny} and \ref{th:gap} follow directly from 
Lemma~ \ref{lem:B}~:
\par
Set $\tilde f_0 = u x_i + x_j$. Then $R(\tilde f_0)$ is a polynomial
in $u$, given by~:
$$
R(u) = r_{\prod d_i} u^{\prod d_i} + \dots + r_0
$$
\par
In particular, if $x_i$ and $x_j$ are rational, they divide
$r_{\prod d_i}$ and $r_0$, respectively. This implies theorem
\ref{th:gap}.
\par
In any case, $|u| = | - { x_j \over x_i} | $
is either less than one, either 
\begin{align*}
|u| &\le { |r_0| + \dots + |r_{\prod d_i - 1}| \over |r_{\prod d_i}| }
\\
&\le
H(r_0) + \dots + H(r_{\prod d_i -1 })
\\
&\le
B(R(u))
\end{align*}
\par
Hence,
$$
{| x_i | \over |x_j|} \ge \left( 3 H(f) \binomial{\sum d_j}{n} \right)
^{- \sum_i \prod_{j \ne i} d_j}
$$
\par
proving Theorem \ref{th:canny}



\paragraph {Proof of Lemma \ref{lem:B}~:} 

Consider the system $g_v$, 
depending on indeterminate $v$, defined by~:
  $$
  g_i(x) = f_i(x) - v {x_i}^{d_i}
  $$
  \par
  Assume that some or all of the coefficients of $f$ are determinate
  (the same proof works if they are all undeterminate, by setting
  $H(f) = 1$). As in the section before, set~:
  $$
  A_k = I_k \hat g
  $$
  \par
  and let $B_k$ be the sub-matrix of $A_k$ from Theorem \ref{th:resultant}.
  \par
  The variable $v$ appears in the main diagonal of $A_k$ and $B_k$.
  Using Part 3 of Lemma \ref{lem:C}, we conclude that 
  $\det A_k$ and $\det B_k$ verify, as polynomials in $v$~:
  $$
  C( \det A_k ) \le H(f) \binomial{\sum d_j}{n} 
  $$
  $$
  C( \det B_k ) \le H(f) \binomial{\sum d_j}{n} 
  $$
  \par
  Therefore, if we consider $R(f)$ as a polynomial in $v$,
  Part 2 of Lemma \ref{lem:C} implies~:
  $$
  C( R(f)(v) ) \le 3 H(f) \binomial{\sum d_j}{n} 
  $$
  \par
  The degree in $v$ of $R(f)$ is $\sum_i \prod_{j \ne i} d_j$.
  Therefore the resultant $R(f)(0)$ of $f$ verifies~:
  $$
  B( R(f)(0) ) \le 
  \left(
  3 H(f) \binomial{\sum d_j}{n} 
  \right)
  ^ 
  {\deg R}
  $$
  \par
  This proves Lemma \ref{lem:B}.



\section {Worst possible conditioning}
\label{sec:gap:cond}
Let $f = (f_1, \dots f_n) \in \Hd$. If $v \in \Bbb C^{n+1}$, $v \ne 0$,
we define the following polynomial from $\Hd$ into $\Bbb C$~:
$$
\discr_v(f) = R(f_1, \dots , f_n, \det \PR{Df}{v} )
$$\glossary{$\discr_v(f)$&$v$-discriminant of $f$}
\par
In the particular case $v = e_1 = (1, 0, \dots 0)$, $\discr_v(f)=0$ is
a necessary and sufficient condition for the existence of $\zeta \ne 0$,
$f(\zeta) = 0$, such that $Df(\zeta)_{|V(\zeta)}$ does not have
full rank. Therefore, we can write~:
$$
\Sigma\aff = Z(\discr_{e_1}(f))
$$\glossary{$\Sigma\aff$&Affine discriminant variety}
\par
In the projective and pseudo-Newton case, $f$ is degenerate if
and only if there is $\zeta \ne 0$, $f(\zeta) = 0$, such that
$Df(\zeta)$ has rank $< n$. Indeed, $Df(\zeta) \zeta  = 0$,
so $Df(\zeta)$ has rank $< n$ if and only if $\PR{Df(\zeta)}{\zeta}$
has rank $< n+1$. This is equivalent, in other notation, to say
that $Df(\zeta)_{|V(\zeta)}$ has rank $<n$. 
\par
Thus, 
$$
\Sigma = \Sigma\proj = \Sigma\pseu
=
\left\{
  f : \exists \zeta \ne 0 , f(\zeta) = 0, \rank(Df(\zeta)) < n
\right \}
$$\glossary{$\Sigma$&Discriminant variety}
{\lemma \label{lem:discr}
        Let $N > \prod d_i$, 
        and let $V=\{v_1, v_2, \dots v_n\}$ be a family 
            of non-zero vectors of $\Bbb C^{n+1}$, 
            not two of them colinear.
        Let $\discr$ be the ideal generated 
        by the polynomials $discr_v$  
        while $v \in V$. 
        Then $\Sigma = Z(\discr)$.
        }

\paragraph {Proof of Lemma \ref{lem:discr}~:}
If $f \in \Sigma$, then by definition there is $\zeta \ne 0$ such
that $f(\zeta) = 0$ and $\rank Df(\zeta) <n$. It follows that
for any $v \in V$, $\PR{Df(\zeta)}{v}$ has rank $< n+1$, hence
$\discr_v(f) = 0$ for all $v \in V$.
\par
Reciprocally, let $\discr_v(f) = 0$ for all $v \in V$. Then 
for all $v \in V$, there is $\zeta_v \ne 0$ such that
$f(\zeta_v) = 0$ and $\rank \PR{Df(\zeta_v)}{v} < n+1$.
\par
If there are infinitely many zeros of $f$, then $f \in \Sigma$ and we are 
done. Assume there are only finitely many zeros. By Bezout's theorem,
there are at most $\prod d_i$ different zeros of $f$.  
\par
This implies that at least two of the $\zeta_v$ should be the same.
Call this point $\zeta$. There are $v,w \in V$ such that~:
$Df(\zeta) v = Df(\zeta) w = 0$, $v$ and $w$ linearly independent.
Therefore, $\rank Df(\zeta) < n$, hence $f \in \Sigma$. This
proves Lemma \ref{lem:discr}.
\medskip
\par
Let us fix $V = \{  (1,v_1, \dots , v_n), v_i \in \Bbb N, 0\le v_i \le n \}$.
Then $V$ contains more than $\prod d_i$ non-colinear elements.

\medskip
\par
Let $r_i$ be the degree of $\discr_v$ in the coefficients of $f_i$. 
Then~:
{\lemma \label{lem:discr:vB} 
        $$
        r_i = \deg_{f_i} (\discr_v) 
            = \prod d_j + (-n + \sum d_j) \prod_{j \ne i} d_j
        $$
        $$
        B(\discr_v) \le 
                 \left(3 n! n 
                 \binomial{-n + 2 \sum d_j}{n}\prod (d_j - 1)\right)
                   ^{\sum r_i}  
        $$
        }
\par
Indeed, the degree in $\zeta$ of $\det \PR{Df}{v}$ is $-n + \sum d_i$.
Each coefficient of this polynomial is a product of a coefficient of
each $f_i$ and a numeric value not bigger than $n ! n \prod (d_j - 1)$.
It follows from Theorem \ref{th:resultant} that
$r_i = \prod d_j + (-n + \sum d_j) \prod_{j \ne i} d_j$.
\par
Consider now the polynomial $R\left(f_1, \dots , f_n, \det \PR{Dg}{v}\right)$.
By Lemma \ref{lem:B}, 
$$
B( R(f_1, \dots , f_n, \det \PR{Dg}{v}) )
\le
\left(3 \binomial{-n +2\sum d_j}{n} 
n! n \prod (d_j - 1)\right)^{\sum r_i}  
$$
Since specialization equating variables do not increase $B$, we
obtain~:
$$
B( R(f_1, \dots , f_n, \det \PR{Df}{v}) )
\le
\left(3 \binomial{-n + 2\sum d_j}{n} 
n! n \prod (d_j - 1)\right)^{\sum r_i}  
$$

 
\paragraph {Proof of Theorem \ref{th:mu1}~:}
         
Consider the mapping~:

$$
\begin {array}{rrcll}
  \sigma : & \Hd & \rightarrow & {\Bbb C}^N \\
           & f = f_1 f_2 \dots f_n &
           \mapsto & \dots (f^I = f_1^{I_1}f_2^{I_2}\dots f_n^{I_n}) \dots &
           , |I_j| = r_j
\end{array}
$$
\par
where $N = \prod \binomial{r_i + S(f_i) - 1}{r_i}$.
$N \le \left( \max r_i + \max S(f_i) - 1 \right)^{\sum{r_i}}$
\par
This mapping associates to each system $f$, a vector whose coordinates
are the values of all the monomials of degree $r_i$ in $f_i$. Since
according to Lemma \ref{lem:discr:vB} the discriminant $\discr_v$ has
degree $r_i$ in $f_i$, we obtain~:
$$
\discr_v(f) = \sigma_* (\discr_v)  \sigma(f) 
$$
\par
Above, the {\em pull-forward} $\sigma_*$ associates to each polynomial
of degree $r_i$ in each $f_i$, the (row) vector
of its coefficients. Using that $|a| \le H(a)$, 
$\onenorm {\sigma_* (\discr_v)} \le B(\discr_v)$.
\par
{\lemma \label {lem:variety:linear}
        Let $p,q \in \Bbb C^N$, $p\rtrans q \ne 0$. 
        Then $\dproj (p^\perp, q) \ge {1 \over \norm{p} \norm{q}}
        \ge {1 \over \onenorm{p} \norm{q}}$
        }
\par
Lemma \ref{lem:variety:linear} follows from the fact that the nearest
point to $q$ in $p^\perp$ is its orthogonal projection 
$q - {p p^* q\over \norm{p}^2}$. Therefore, the distance $\dproj(q,p^\perp)$
is not less than $p^* q \over \norm{p} \norm{q}$ 
\par
Lemma \ref{lem:variety:linear} gives us a bound on the distance between
$\sigma(f)$ and $\sigma(\discr_v)^\perp$~:
\begin{multline*}
\dproj(\sigma(f),\sigma(\discr_v)^\perp) \ge 
\\
\ge
\left(
  3 n! n \binomial{-n + 2 \sum d_j}{n} \prod (d_j - 1)
\right)
^{- \sum r_i }
\left(
\sqrt{N} \prod(H(f_i)^{r_i})
\right)
^{-1}
\end{multline*}
\par
Now we consider a path $\gamma : [0,1] \rightarrow \Hd$, with
$\knorm{\gamma(t)} = c$ and $\knorm{\gamma'(t)}  = cv$. Then
$\dproj(\gamma(0), \gamma(1)) \le v$. We compute~: 
\begin{align*}
\norm { ( \sigma \circ \gamma) (t) } 
 &\ge
 \sqrt{ \sum_I (\sigma_I \circ \gamma)(t) ^2}
\\
&\ge
 \prod_i ( \max_j | \gamma_i(t)_j|^{r_i - 1} )
 \norm{\gamma(t)}
\\
&\ge
 \prod_i ( \max_j | \gamma_i(t)_j|^{r_i - 1} )
 \knorm{\gamma(t)}
\\
\norm{\gamma'(t)} &\le \knorm{\gamma'(t)} \sqrt{D !}
\\
\norm{( \sigma \circ \gamma)'(t)}
&\le
cv \sqrt{D!}\sqrt{N} \max_i r_i \prod_i \max_j |\gamma_i(t)_J|^{r_i -1}
\end{align*}
\par
Thus,
$$
{
\norm{( \sigma \circ \gamma)'(t)}
\over
\norm { ( \sigma \circ \gamma) (t) }
}
\le
v \sqrt{D!} \sqrt{N} \max_i r_i
$$
\par
And hence~:
$$
{
\norm{ (\sigma \circ \gamma) (1)  - (\sigma \circ \gamma) (0) }
\over
\norm{ (\sigma \circ \gamma) (0) }
}
\le
v \sqrt{D!} \sqrt{N} \max_i r_i
$$
\par
Assume furthermore that $\gamma(0) = f$ and that $\discr_v (\gamma(1)) =0$.
Then ~:
$$
{
\norm{ (\sigma \circ \gamma) (1)  - (\sigma \circ \gamma) (0) }
\over
\norm{ (\sigma \circ \gamma) (0) }
}
\le \sqrt{N} \sqrt{D!} \max r_i \dproj(f,Z(\discr_v))
$$
\par
Introducing Lemma \ref{lem:variety:linear}, we obtain~:
\begin {multline*}
\dproj(f, Z(discr_v)) \ge
\\
\ge
\left( \sqrt{D!} N \max r_i \right)^{-1}
\left(3 \binomial{-n + 2 \sum d_i}{n}
n! n \prod (d_j - 1) H(f) \right)^{-\sum r_i}
\end{multline*}
\par
Where $N \le (\max r_i + \max S(f_i) - 1)^{\sum r_i}$. 
\medskip
\par
Let $f \not \in \Sigma$. Then there is $v$ in $V$ such that 
$\discr_v(f) \ne 0$. The equation above bounds the distance of
$f$ to the variety $Z(\discr_v)$, that contains $\Sigma$. 
\par
Therefore, we can set the bound~:
$$
d(\Sigma) = n \prod d_j \sum d_j \ge \sum r_i
$$\glossary{$d(\Sigma)$&Complexity exponent of the discriminant
variety $\Sigma$}
\par
This exponent is clearly less than $\sum r_i$. We also can set~:
$$
\mu(\Sigma)
=
\sqrt{D!} d(\Sigma)
\left(
 3 n! n (d(\Sigma) + \max S(f_i)) (2 \sum d_j)^n \prod(d_j - 1)
\right)
^d(\Sigma) 
$$\glossary{$\mu(\Sigma)$&Condition number of the discriminant variety
$\Sigma$}
\par
and Theorem \ref{th:mu1} is proved.
\medskip
\par
\paragraph {Proof of Theorem \ref{th:mu2}~:}


Let us suppose that there are reals $\tilde t_1, \tilde t_2$ such that
$\tilde t_1 f + \tilde t_2 g \in \Sigma$. Then in particular, there
is $\zeta$ such that~:
$$
\tilde t_1 f(\zeta) + \tilde t_2 g(\zeta) = 0
$$
\par 
and
$$
\det \left[
\begin{array}{c}
{\partial \over \partial \zeta} \tilde t_1 f(\zeta) + \tilde t_2 g(\zeta) \\
(1 \ , \ 0 \dots 0) 
\end{array}
\right]
= 0
$$
\par
Moreover, we can equate one of the $\tilde t_i$ to one of the $\zeta_i$,
say $t_1 = \zeta_{n+1}$. Then, we obtain a system of the form~: 
\begin{equation}
\label{real:system}
\begin{array}{lcc}
\Re \left( t_1 f(\zeta) + t_2 g(\zeta) \right) & = & 0 \\
\Im \left( t_1 f(\zeta) + t_2 g(\zeta) \right) & = & 0 \\
\Re \left(
\det \left[
\begin{array}{c}
{\partial \over \partial \zeta} (t_1 f(\zeta) + t_2 g(\zeta)) \\
(1 \ , \ 0 \dots 0) 
\end{array}
\right]
\right) & = & 0 \\
\Im \left(
\det \left[
\begin{array}{c}
{\partial \over \partial \zeta} (t_1 f(\zeta) + t_2 g(\zeta)) \\
(1 \ , \ 0 \dots 0) 
\end{array}
\right]
\right) & = & 0
\end{array}
\end{equation}
\par
If we have in mind that $t_1$ and $t_2$ are {\em real} variables,
it is clear that system (\ref{real:system}) is a system 
of $2n+2$ real homogeneous 
equations in $2n + 2$ real variables ($t_1, t_2, \Re(\zeta_1), \Im(\zeta_1),
\dots , \Im(\zeta_n)$). 
\par
If there are $\tilde t_1$ and $\tilde t_2$ such that
$\tilde t_1 f + \tilde t_2 g \in \Sigma$, then system (\ref{real:system})
has a solution, and therefore its resultant vanishes. The converse is not
true, since there may exist a complex solution that is not a real solution.
\par
Let us call $R(f,g)$ the resultant of system (\ref{real:system}). Then, in
the {\em realization} of $\Hd \times \Hd$, we define the variety~:
$$
\Sigma_0 = \{ f,g : R(f,g)=0 \}
$$\glossary{$\Sigma_0$&Real variety of paths with a degenerate system}
\par
This variety is proper ~: if we set $f$ = $g$, there is $f$ such that
there is no real solution for system (\ref{real:system}), since any
real solution would imply the existence of a complex solution for
$f(\zeta) = 0, \det \PR{Df(\zeta)}{e_1} =0$, and not all $f$ are
degenerate.
\medskip
\par
Let $r_i$ be the degree of $R$ in the coefficients of $f_i$ and $g_i$.
Then ~:
$$
r_i = 2 \prod (d_j + 1) \prod_{j \ne i} (d_j + 1) (\sum d_j)^2
    \ + \ 2 \prod(d_j + 1)^2 \sum d_j
$$
\par
Therefore,
$$
\sum r_i \le 2 n \prod (d_j + 1)^2 (1 + \sum d_j)^2
$$
\par
So we set~: 
$$
d(\Sigma_0) = 2 n \prod (d_j + 1)^2 (1 + \sum d_j)^2
$$\glossary{$d(\Sigma_0)$&Complexity exponent of $\Sigma_0$}
\par
When we {\em realize} a complex polynomial of degree $d$, we obtain two
polynomials of height at most $2^d$. Therefore, the height of system
(\ref{real:system}) is bounded by~:
$$
2^{D} n! \prod(d_j - 1)
$$
\par
Therefore, Lemma \ref{lem:B} implies~:
$$
B(R) \le 
\left( 
   3 \binomial{-1 + 4 \sum d_j}{n} 2^{D} n!n \prod(d_j - 1) \right)
     ^ {d(\Sigma _0)} 
$$
\par
Thus, as in the proof of Theorem \ref{th:mu1}, we can bound  
$\mu(f_t)$ by $ \sqrt{D!} N B(R) d(\Sigma_0) $, and
set~:
\begin{multline*}
\mu(\Sigma_0)
=
\sqrt{D!}
d(\Sigma_0)
\times
\\
\times
\left(
 3
 2^D
 n! n
 (d(\Sigma_0) + \max S(f_i) - 1)
 \prod (d_j - 1)
 (-1 + 4 \sum d_j)^{2n+1}
\right)
^ {d(\Sigma_0)}
\end{multline*}\glossary{$\mu(\Sigma_0)$&Condition number of $\Sigma_0$}
\par
And theorem \ref{th:mu2} is proved.
 

\section {Diophantine decision problem}
\label {sec:diophantus}

In this section, we are concerned about the following problem~:
Let $0 \le x \le 1$ be a real number, such that $2^{-k} x$ is an
integer. Let $H$ be an integer, and let $\epsilon < 1/2H^2$.
We want to decide if there is a rational $p \over q$ in 
$[x-\epsilon, x+\epsilon]$, such that $q \le H$. In the case it
exists, we want to be able to find it. Consider that $\epsilon = 2^{-k'}$
for some $k'\ge k$.
\par
If a solution exists, it is unique. Indeed, let $p \over q$ and $p' \over q'$
be different solutions. Then $| {p \over q} - {p' \over q'} | = 
| {p q' - p' q \over q q' } | \ge {1 \over H^2} \ge 2 \epsilon$, a
contradiction.
{\lemma \label{lem:approx}
        There is a program that solves this problem within
        polynomial time on $\log k'$} 
\par
The cases $x-\epsilon \le 0$ and $x + \epsilon \ge 1$ are trivial,
and can be discarded. Thus, we assume that $x \in [\epsilon, 1- \epsilon]$.
\par
Geometrically, we consider the $(q,p)$ plane. Let $Q$ be the
square $0 < q,p \le H$. The set of rationals $1 \le q,p \le 1$ is
represented by the lattice of points of $Q$ with integer coordinates.
\par
Let $\Delta$ be the line of equation $p = q x$. Let $\Delta_1$ and
$\Delta_2$ be the lines of equation $p = (q + \epsilon) x $ and
$p = (q - \epsilon) x$, respectively. $\Delta$ corresponds to
the real number $x$, and the condition $x - \epsilon \le {p \over q}
\le x + \epsilon$ is true if and only if $(p,q)$ belongs to the cone $C$
limited by $\Delta_1$ and $\Delta_2$.
\par
Thus, we want to find a lattice point $(p,q)$ in $Q \cap C$. In order
to do that, we use the continued fraction expansion of $x$.
\par
Consider the recurrence~:
\begin{align*}
r_0 &= x
\\
r_{i+1} &= {1 \over r_i} - \lfloor {1 \over r_i} \rfloor
\end{align*}
\par
We also write~:
$$
\sigma_{i+1} = \lfloor {1 \over r_i} \rfloor
$$
\par
Notice that when $r_0$ is rational,
$H(r_{i+1}) \le H(r_0)$, so the $r_i$ can be computed
with rational arithmetics in a bounded number of bits.
\par
We can also define the approximants $p_i,q_i$ of $x$ by the
recurrence~:
\begin {align*}
p_0 &= 0, q_0 = 1, p_1 = 1,q_1 =1
\\
p_{i+1} &= p_{i-1} + \sigma_i p_i
\\
q_{i+1} &= q_{i-1} + \sigma_i q_i
\end{align*}
\par
It is a fact that~:
$$
{p_i \over q_i}
=
{1 \over {\sigma_1 + 
   {1 \over \dots
      {1 \over \sigma_{i-1}}}}}
$$
\par
The pairs $p_i, q_i$ have no common denominator, and in the case $x$
is rational (our case) $x$ is attained in a finite number of steps.  
Indeed, from the recurrence, we easily obtain that $p_{i+2} \ge 2 p_i$
and $q_{i+2} \ge 2 q_i$, so $p_i / q_i = x$ for some $i \le 2k$.
\par
$p_i / q_i$ are known to be the best possible approximations
of $x$ with a given height~:
{\theorem [181 in \cite{HARDY}]
          If $n > 1$, $0 < q < q_n$, and $p/q \ne p_n / q_n$,
          then
           $$
           \left | {p_n \over q_n} - x \right |
           <
           \left | {p \over q} - x \right |
           $$}
That implies that if $(q_i,p_i)$ does not belong to $C$, then
there is no lattice point in $C$ at the left of $q_i$. 
\par
For odd $i$'s, $q_i,p_i$ is below $\Delta$. For even $i$'s,
$q_i,p_i$ is above $\Delta$.
\par
Now we come to the algorithm~: we compute $q_i, p_i$, until
$q_i, p_i$ is in $C$ or $q_{i-2}, p_{i-2}$ is not in $Q$.
\par
If $q_i, p_i$ is in $Q$, then we are done (output $p_i,q_i$). 
\par
If $q_{i-2},p_{i-2}$ is not in $Q$, then there is no rational
solution of bounded height, and we are also done (output NO SOLUTION).
\par
There is a third case. There might be lattice points in $C \cap Q$
along segments $ ((q_{i-2},p_{i-2}) (q_i,p_i)) $ or
$ ((q_{i-1},p_{i-1}) (q_{i+1},p_{i+1})) $. 
\par
Assume for instance that $i$ is even, and we want to check for
lattice points in $Q \cap C$ along  $ ((q_{i-2},p_{i-2}) (q_i,p_i)) $.
Then we write the parametric equation~:
$$
(q,p) = (q_{i-2},p_{i-2}) + \lambda (q_{i-1},p_{i-1})
$$
\par
We combine it with the equation of $\Delta_2$, and obtain~:
$$
\lambda = 
  { 
  q_{i-2} (x - \epsilon) - p_{i-2}
  \over
  p_{i-1} - q_{i-1} (x - \epsilon)
  }
$$
\par
The natural candidate to a solution on this side is the point~:
$$
(q,p) = (q_{i-2},p_{i-2}) + \lceil \lambda \rceil (q_{i-1},p_{i-1})
$$
\par
If this fail, we have to look for the point~: 
$$
(q,p) = (q_{i-1},p_{i-1}) + \lceil \lambda' \rceil (q_{i},p_{i})
$$
\par
Where 
$$
\lambda' = 
  { 
  q_{i-1} (x + \epsilon) - p_{i-1}
  \over
  p_{i} - q_{i} (x + \epsilon)
  }
$$
\par
If this one also fails to be in $Q \cap C$, there is no rational
solution to our problem. The other case ($i$ odd) is analogous.
\par
Since all the computations can be performed by rational
arithmetics in precision $k'$, and there are at most
$O(\log k')$ continued fraction iterations, the total time
is polynomial in $\log k'$.


\section {Proof of theorem \ref{main1}}
\label {sec:proof}
In order to deal with points in the projective space, the usual
concept of height may be unadequate; instead we define the
height of ratios:
$$
H_r(x_0 : \dots x_n) 
=
\max_{x_j \ne 0} H({x_i \over x_j})
$$
where the height of a rational is given by $H(p/q) = \max(|p|,q)$,
whenever $p$ and $q$ have no common divisor.
\par
Theorem \ref{th:gap} can be restated more conveniently in
terms of $H_r$~:
{\theorem Let $f \in \Hd$ be non-degenerate, $f(\zeta) = 0$,
          and let $\zeta$ be rational. Then 
          $H_r(x) \le \prod {d_i}^{-1}(3 n H(f) \dim \Hd)^{\prod d_i}$.}
\par
Also, there is a "gap" between different rational points
of a bounded height~:
{\lemma Let $x$,$x'$ be rational points of ${\Bbb C}^{n+1}$
        (this means that $x,x' \in {\Bbb Q}^{n+1}$),
        such that $\dproj(x,x') \ne 0$. Let 
        $H = \max (H_r(x), H_r(x'))$. Then
        $\dproj(x,x') \ge {1 \over H^2 (n+1)}$
        }
\par
Proof : assume without loss of generality that $x_0 = 1$,
$|x_j| \le 1$ for all $j$, $x_i' = 1$ for some $i$, and
$|x_j'| \le 1$. 

$$
d( {x \over \|x\|}, {x' \over \|x'\|} )
\ge
{1 \over \sqrt{n+1}} d(x,x')
\ge
{1 \over H^2 \sqrt{n+1}}
$$
\par
since we are projecting from an hypercube into its inscribed
hypersphere. Now we project into the hyperplane passing by
$x/\|x\|$ perpendicular to $x'$. In the worst case~:
$$
\dproj(x,x') 
\ge 
{1 \over \sqrt{n+1}}
d( {x \over \|x\|}, {x' \over \|x'\|} )
\ge
{1 \over H^2 (n+1)}
$$
\par
Now, the Quadratic Convergence Theorem provides us
a point $x \in {\Bbb C}^{n+1}$ and
a neighborhood of radius $\delta < {1 \over 2 H^2 (n+1)}$
over $x$, containing a root $\zeta$. Here, we set
$H = \prod  d_i (3 n H(f) \dim \Hd)^{\prod d_i}$, so that if $\zeta$ is 
rational, it belongs to a ball of radius $\delta$ over $x$. 
\par
Thus, we need about $1 + \log (-\log \delta)$ iterations
of $N_\epsilon$, $\epsilon = \delta^2$. We need also
that $\epsilon \gamma < 1/40$, but $\gamma$ can be
bounded in terms of $\mu$ by using theorem \ref{th:mu1}.
Thus we obtain 
a polynomial time bound in $\prod d_i$, $n$, $D$,
$\log H(f)$, $\dim H_d$ and $\log \mu(\zeta)$. However,
since $\log \mu(\zeta)$ is bounded by the polynomial
in Corollary \ref{cor:mu1}, we obtain a polynomial time
bound in $\prod d_i$, $n$, $D$,
$\log H(f)$ and $\dim \Hd$ alone. 
\par
Without loss of generality, we assume $x_0 = 1$ and
$0 \le x_j \le 1$. We have $| x_i - \zeta_i | \le {1 \over 2H^2}$,
so we can use the diophantine approximation algorithm to find
the $\zeta_i$'s , if they exist. This can be done in time
$n$ times a polynomial in $\log H$.
This proves theorem \ref{main1}.



\section {Separation of roots}
\label{sec:gap:gamma}

   We prove theorem \ref{th:gamma} as follows~: Let $h = x_2 - x_1$. By
   scaling $x_2$, assume first that $x_2 \in x_1 + ker Df(x_1)^\perp =
   x_1 + x_1^\perp$.  
   We have~:
   \begin{align*}
   f(x_1) &= 0
   \\
   f(x_2) &= 0 = f(x_1) + Df(x_1) h
     + { D^2f(x_1) h^2 \over 2 }
     + \dots
     + { D^kf(x_1) h^k \over k! }
     + \dots
   \end{align*}
   \par
   So :
   $$
   - Df(x_1) h 
   =
   \sum_{k \ge 2}
   {1 \over k!}
   D^kf(x_1) h^k
   $$
   \par
   Multiplying both terms by $Df(x_1)^\dagger$, and using that 
   $h \in ker Df(x_1)^\perp$, we obtain~:
   $$
   h =
   \sum_{k \ge 2}
   {1 \over k!}
   Df(x_1)^\dagger D^kf(x_1) h^k
   $$
   \par
   Passing to the norms, and dividing by $\| h \|$~:
   $$
   1
   \le
   \sum_{k \ge 2}
   {1 \over k!}
   \| Df(x_1)^\dagger D^kf(x_1) \| \|h\|^{k-1}
   \le
   \sum_{k \ge 2}
   {1 \over k!}
   {\gamma(f,x_1)^{k-1} \|h\|^{k-1} \over \|x_1\|^{k-1} }
   $$
   
   This implies~:
   $$
   1
   \le
   { 1 \over 1 - \gamma(f,x_1) {\|x_2 - x_1\| \over \| x_1 \|} }  
   - 1 
   $$
   
   We get~:
   \begin{align*}
   \gamma(f,x_1) {\|x_2 - x_1\| \over \| x_1 \|} 
   &\ge {1 \over 2}
   \\
   {\|x_2 - x_1\| \over \| x_1 \|} 
   &\ge {1 \over 2 \gamma(f,x_1)}
   \end{align*}

   Now, assuming again $x_2 \in x_1 + x_1^\perp$,
   we have~:
   $$
   d_p(x_1,x_2) = \sin \tan^{-1} {\| x_2 - x_1 \| \over \|x_1\| } \qed
   $$


   However, we can say nothing about the height of a root
   $x$ solely in terms of $\gamma$, since $\gamma$ is rotation-invariant~:
   any root $x$ can be mapped anywhere in projective space, without
   changing $\gamma$.




\chapter {Global complexity of solving systems of polynomials}
\label   {ch:global}
\begin {abstract}
A global algorithm for solving systems of polynomial
equations is constructed. Main Theorem~ \ref{main} is proved.
\end   {abstract}

\section {Introduction}

A Theorem on the global complexity of solving systems of polynomial
equations with integer coefficients was stated in Chapter \ref{ch:intro}.
Here, we will construct an algorithm corresponding to the machine
in Main Theorem \ref{main}, and prove the Theorem.
\par
We will use the analysis of the Pseudo-Newton iteration from
Chapter \ref{ch:qct}, together with the construction of a
Pseudo-Newton operator {\tt Pseudo$(f,x)$} in Chapter \ref{ch:newton}.
Chapter \ref{ch:gap} will provide us with a worst case estimate
of the condition number of $f$.
\par
Basically, we have to answer here to the following questions~:
How to get a starting system, how to certify an approximate
solution, and how to design a global algorithm that will succeed
generically.
\par
Since the worst case bounds on $\mu$ are too pessimistic, the 
algorithm will rather guess an upper bound for $\mu$, and
attempt to solve the system. If this fails, the algorithm will
increase the upper bound, and try again. This approach leads
to algorithms that are also tractable in practice.


\section {How to obtain starting points.}

Obtaining starting points for a homotopy path is easy. Obtaining
good starting points is, at this time, an open problem
(see \cite{BEZIII}). We give only the easy and less efficient way~:
\par
Let $g_k(x) = x^k - 1 = (x - \zeta^0) \dots (x - \zeta^{k-1})$,
where $\zeta$ is a $k$-th root of unity. Then the system
$f$, $f_i(x) = g_{d_i}(x_0,x_i)$ is clearly a non-degenerate
starting point. 

{\lemma  \label{lem:start} 
         There is an algorithm {\tt STARTPOINT}~, returning
         a system of polynomials
         $f = $ {\tt STARTPOINT} $(n,d) \in \Hd$, with height $1$,
         together with an approximate solution $X$ of $f$. 
         } 

\par
We will indicate the proof of the Lemma. We have to bound
the cost of obtaining a $d$-th root of unity.
\par
Consider the polynomial in one variable : $g(x) = x^d - 1$. 
Let $\zeta$ be a $d$-th root of unity, $g(\zeta) = 0$.
$g'(\zeta) = d \zeta^{d-1} = {d \over \zeta}$.

$$
\mu\aff(g,\zeta)
\le
\knorm{g}
\norm{ {\zeta \over d} \sqrt{d} |\zeta|^{d-1} }
=
\sqrt{ {2 \over d} }
$$

We use Lemma \ref{lem:alpha:x} of chapter \ref{ch:qct}. According
to that Lemma, if~:
$$
{\norm { (1,x) - (1,\zeta) }  \over \norm{ (1,\zeta) } } \gamma(\zeta) 
\le \bar u
$$
\par
then~:
$$
\alpha(f,x) \le {\bar u \over \psi(\bar u)^2}
$$
\par
Using that $\gamma(f,\zeta) \le {d^{3/2} \over 2} \mu(f,\zeta)$,
we obtain that~:
{\lemma If $|x - \zeta| \le {2 \bar u \over d}$, then $\alpha(f,x)
\le {\bar u \over \psi(\bar u)^2}$}
\par
That means that if we are able to obtain an approximation good
enough of $\zeta$, we obtain an approximate zero associated
to $\zeta$. We can compute $\zeta$ to a higher precision by
Affine Newton iteration, and then compute all the $\zeta^i$
to obtain the approximate solution of $f$.
\par
In order to obtain a good approximation of $\zeta$, we can write~:
$$
\zeta = 1 + ai + {1 \over 2} (ai)^2 + \dots + {1 \over k!} (ai)^k + E_k
$$
\par
We will approximate $\zeta$ by truncating the series. Suppose we
want to do that with error $\delta$, we need to choose $k$ such
that $|E_k| < \delta$.
\par
Since $a = {2 \pi \over d}$ and the cases $d = 1$ and $d=2$ are trivial,
we can assume that $a < 3$. Then for $k > 6$, $a^k / k! \le 2^{6-k}$. 
This allows us to compute the approximation of $\zeta$ using a 
number of terms logarithmic in $\delta^{-1}$. 
\par
Therefore, it is easy to see that a $2 \delta$ approximation of
$\zeta$ can be obtained within time polynomial in $- \log \delta$.
Setting $\delta < {1 \over 16 d}$, we get $\alpha(f,x) < 1/8$. 
According to Theorem \ref{qct:a1:aff},
$x$ is an approximate zero associated to $\zeta$.
 

\section {How to bound $\mu$}
In this section, we give procedures to certify that a given list of
points is an approximate zero of a system of polynomial equations.

{\lemma \label{lem:vermu}
        There is a procedure to compute a bound M 
        (finite or not) such that~:
        $$
        \mu(f,x) \le M \le 4 \sqrt{n} \mu(f,x)
        $$
        \par
        That procedure is polynomial time in $n$, $D$, $\prod d_i$,
        $S(f)$, $\log H(f)$.
        } 


The following algorithm returns the bound mu$(f,x)$ for
$\mu(f,x)$, such that, ignoring the numeric error, 
$2 \mu(f,x) \le \text{mu}(f,x) \le 2 \sqrt{n} \mu(f,x)$.
Of course, numerical error will occur, and that is
the reason Lemma \ref{lem:vermu} is weaker than the bound
above. Let us first state the algorithm, and then proceed
with the error analysis.
\medskip

{
\tt
\noindent
{ALGORITHM \ } $z'' \leftarrow $ mu ( $f$, $x$ )

\begin{list}{\arabic{linenumber}}{\usecounter{linenumber}}
\item \label{mu:1}
      Compute 
      $A = \left[ {\partial f_i \over \partial x_j} 
                  {d_i}^{-1/2} {\|x\|_2}^{-d_i + 1}
          \right]$
\item \label{mu:2}
      Make $A^t = Q \left[ \begin{array}{c}R \\ 0 \end{array} \right]$
\item \label{mu:3}
      Compute $c = {R^t} ^{-1} I$
\item \label{mu:4}
      Set mu $= 2 \|f\|_k \|c\|_f$
\end{list}
}

\paragraph{Proof of correctness~:} Assume there is no numerical
error.
\begin{align*}
\mu(f,x) &= \knorm{f} \norm{Df^\dagger \diag(\sqrt{d_i} \norm{x}^{d_i - 1})}
\\
&=
\knorm{f} \norm{Q 
      {\left[ \begin{array}{c} R\rtrans \\ 0 \end{array}\right]} ^{-1}} 
\\
&=
\knorm{f} \norm{{R\rtrans} ^{-1}} 
\end{align*}
\par
We use the fact~:
$$
\norm {{R\rtrans}^{-1}}
\le
\fnorm {{R\rtrans}^{-1}}
\le
\sqrt{n} \norm {{R\rtrans}^{-1}}
$$
\par
It follows that~:
$$
2\mu(f,x) \le 2\text{mu}(f,x) = 2\knorm{f} \fnorm {{R\rtrans}^{-1}}
\le 2\sqrt{n} \mu(f,x)
$$

\paragraph{First order error analysis~:}


Let $q = 4 D + S(f) + \max S(f_i) + 2.25 n^3 + 6.25 n^2 + 2n + 1$~
\glossary{$q$&A polynomial in $D$, $S(f)$ and $n$.}.
Let $M_i(f,x)= {R\rtrans} ^{-1} e_i$, 
then $\norm{M_i(f,x)} = \norm{A^\dagger b_i}$. 

\par
Line \ref{mu:1}~: $A$ is computed with forward error bounded by~:
$$
\maxnorm{\delta_1 A} \le \knorm{f} \macheps(2D + \max S(f_i) + 2n + 1)
$$
\par
Line \ref{mu:2}~: This line introduces some backward error in $A$~:
\begin{align*}
\norm {\delta_{qr} A}
&\le
\norm{A}
\macheps(2.25 n^2 + 5.25 n)
\\
\maxnorm {\delta_{qr} A}
&\le
n \maxnorm{A}
\macheps(2.25 n^2 + 5.25 n)
\end{align*}
\par
Since $\maxnorm{A} \le \knorm{f}$,
$$
\maxnorm {\delta_{qr} A}
\le
\knorm{f}
\macheps(2.25 n^2 + 5.25 n)
$$
\par
Line \ref{mu:3}~:
This line introduces backward error in $R$, hence in $A$~:
$$
\maxnorm{\delta_R A}
\le
\maxnorm{\delta_2 R}
\le
\maxnorm{R} \macheps(n)
\le
n \maxnorm{A} \macheps(n)
$$
\par 
We can write~:
$$
\maxnorm{\delta_2 A} \le \knorm{f} \macheps(n^2)
$$
\par
Therefore~:
\begin{align*}
\maxnorm{\delta A} &\le \knorm{f} \macheps(2D + \max S(f_i)
  + 2.25 n^3 + 6.25 n^2 + 2n + 1)
\\
&\le \knorm{f} \macheps(q - S(f) - 2 D)
\end{align*}
\par
Now,
$$
\maxtwonorm{D M_i(f,x)} \le \norm {A^\dagger e_i} \norm{A^\dagger}
$$
\par
Line \ref{mu:4} introduces forward error bounded by $\knorm{f}
\macheps(S(f) + 2D)$, therefore, in first order analysis,
$$
\norm{\delta \text{mu}}
\le
\mu^2 \macheps(q)
$$
\par
\medskip
\paragraph{A preliminary Lemma~:} In order to give some rigorous
bounds for $\mu$, we shall need the following Lemma~:
{ \lemma \label{lem:muC}
         Let $C$, $\delta C$ be matrices, so that $\maxnorm{\delta C}
         \le \knorm{f} \macheps(q)$.
         \par
         Let $2n \knorm{f} \norm{C^{\dagger}}
         \macheps(q) < 1$. Then~:
         $$
         {1 \over 2} \norm{C^{\dagger}} 
          \le
         \norm{(C + \delta C)^{\dagger}}
          \le
         2 \norm{C^{\dagger}} 
         $$
         }

\paragraph{Proof~:}
$$
\norm{ \delta C} \le n \maxnorm{\delta C} \le n \knorm{f} \macheps(q)
\le {1 \over 2 \norm{C^{\dagger}}}
$$
\par
Therefore, $\norm {(C + \delta C)^{\dagger}}$ verifies~:
$$
{1 \over 2} \norm{C^{\dagger}}
\le
\norm{(C + \delta C)^{\dagger}}
\le
2 \norm{C^{\dagger}}
$$

\paragraph {Proof of Lemma \ref{lem:vermu}~:}

\par
Step 1 : Choose $\macheps$ so that~:
\begin{equation}
\label{eq:mach}
4 n^{3/2} \mu(\Sigma) H(f) ^{d(\Sigma)} \macheps(q) < 1
\end{equation}

\par
where $\mu(\Sigma)$ and $d(\Sigma)$ are defined in Theorem
\ref{th:mu1} of Chapter \ref{ch:gap}. It is clear from the
corollary of the same theorem that the number of bits of 
precision we are requiring is bounded by a polynomial in
$n$, $D$, $\prod d_i$, $\dim \Hd$ and also $\log H(f)$.
\medskip
\par
Step 2~: Compute {\tt mu}$(f,x)$. In case a division by zero
occurs, or in case ${ \text{mu}(f,x) \over 2 \sqrt{n} }
> \mu(\Sigma) H(f)^{d(\Sigma)}$, then return $\infty$.
\par
Indeed, assume that $\mu$ is finite.
$\maxnorm{\delta A}  \le \knorm{f} \macheps(q)$,
so that~:
$$
\knorm{f} \fnorm{A + \delta A}
\le
\knorm{f} \norm{A + \delta A} \sqrt{n}
\le 2 \knorm{f} \norm{A} \sqrt{n}
\le 2 \mu \sqrt{n}
$$
\par
That implies that~:
$$
\mu \ge \mu(\Sigma) H(f) ^{d(\Sigma)}
$$
\par
contradicting Theorem \ref{th:mu1} of Chapter \ref{ch:gap}.
\medskip
\par
Step 3 : Since
${ \text{ mu}(f,x) \over 2 \sqrt{n} }
\le \mu(\Sigma) H(f)^{d(\Sigma)}$, we can use equation~(\ref{eq:mach})
to obtain~:
$$
2 n \knorm{f} \fnorm{(A + \delta A)^{\dagger}} \macheps(q) < 1
$$
\par
Hence,
$$
2 n \knorm{f}\norm{(A + \delta A)^{\dagger}} \macheps(q) < 1
$$
\par
Therefore, Lemma \ref{lem:muC} implies~:
\begin{align*}
{1 \over 2} \norm{ A^{\dagger} }
&\le
\norm { (A + \delta A)^{\dagger} }
\le
2 \norm{ A^{\dagger} }
\\
\mu
&\le
2 \knorm{f} \norm { (A + \delta A)^{\dagger} }
\le 
4 \mu
\\
\mu
&\le
2 \knorm{f} \fnorm { (A + \delta A)^{\dagger} }
\le
4 \sqrt{n} \mu
\end{align*}
\par
Thus,
$$
\mu \le \text{ mu} \le 4 \sqrt{n} \mu
$$

\section {More estimates on $\mu$}

{\lemma \label{lem:glomu}
       Let $f \in \Hd$, and assume that $x, \zeta \in {\Bbb C}^{n+1}$ 
       are non-zero.
       Let $u = \dproj(x,\zeta) \gamma\pseu(f,\zeta)$. 
       Then~:
       $$
       \mu\pseu(f,x) \le { (1 - u)^2 \over \psi(u) } \mu\pseu(f,\zeta)
       $$
       }

\paragraph {Proof of Lemma \ref{lem:glomu}~:}
Let $\zeta$ be scaled in such a way that $\dproj(x,\zeta) =
{\norm{x - \zeta} \over \norm{\zeta}}$. We proceed as in
Lemma \ref{lem:beta} of Chapter \ref{ch:qct}, and break
$\mu(f,x)$ in~:
\begin{align*}
\mu(f,x) \le
  &\knorm{f}
  \norm {\DfI{x}{x} \Df{x}{\zeta}}
\\
& \   \norm {\DfI{x}{\zeta} \Df{\zeta}{\zeta}}
\\
& \   \norm {\DfI{\zeta}{\zeta} \diag{ \norm{\zeta}^{d_i} \sqrt{d_i} } }
\\
& \   \norm {\diag \left( { \norm{x} \over \norm{\zeta} } \right)^{d_i}}
\end{align*}
\par
Using the estimates of Part 1 and Part 2 of the proof of Lemma
\ref{lem:beta} Chapter \ref{ch:qct}, and using also the fact that
$\norm{x} \le \norm{\zeta}$, we obtain~:
$$
\mu(f,x) \le { (1 - u)^2 \over \psi(u) } \mu(f,x)
$$
\par
This proves the Lemma \ref{lem:glomu}.
\par
 In particular, if
$\mu(f,\zeta) \le \bar \mu$, and if $4 \dproj(x,\zeta) \gamma\pseu(f,\zeta)
< {1 \over 2}$, it is possible to conclude that $\mu(f,x) \le 2 \bar \mu$.
This kind of estimate allows to bound $\mu$ in a neighborhood
of the path we are following. It allows us to bound the conditioning
of approximate zeros, and therefore to set the machine precision
necessary for Newton iteration, as it is required in Chapter \ref{ch:newton}.


\section {How to bound $\eta$}
Let $q = 4D + S(f) + \max S(f_i) + 2.25 n^3 + 6.25 n^2 + 2n + 1$.
Computing a bound for $\eta$ is straight-forward~:
\medskip


{
\tt
\noindent
{ALGORITHM \ } eta $ \leftarrow $ eta ( $f$, $x$ )

\begin{list}{\arabic{linenumber}}{\usecounter{linenumber}}
\item \label{eta:1}
      Compute $n_1 = \|f\|_k$
\item \label{eta:2}
      Compute $n_2 = \|x\|_2$
\item \label{eta:3}
      Set $b_i = { f_i(x) \over ( \sqrt{d_i} n_1 n_2 )  }$
\item \label{eta:4}
      Set eta$ = (1 + {1 \over 8})\|b\|_2$
\end{list}
}

\paragraph {Forward error analysis~:}

\par
Line \ref{eta:1} : The forward error is $|\delta n_1| 
 \le \knorm{f} \macheps(S(f) + 2D)$
\par
Line \ref{eta:2} : We have $|\delta n_2| \le \norm{x} \macheps(2n+2)$
\par
Line \ref{eta:3} : The error is bounded by~:
$$
|\delta b_i| 
\le
{1 \over \sqrt{d_i}}
\macheps( S(f) + \max S(f_i) + 3D + 2n + 2 )
$$
\par
Line \ref{eta:4} : We get~:
$$
| \delta \text{eta} |
\le
\macheps(S(f)  + \max S(f_i) + 3D + 4n + 1 )
\le
\macheps(q)
$$
\par
And therefore,
{ \lemma \label{lem:vereta}
         In the conditions above,
         $\eta \le \text{\tt eta} \le 2 \eta$.}
 

\section {How to certify an approximate solution.}
We already proved the following facts~:
{\lemma \label{lem:pess}
        Assume the following condition is verified~:
        \begin{equation}
        \label{cond:pessimistic} 
        4 n^{3/2} \mu(\Sigma) H(f)^{d(\Sigma)} \macheps(q) < 1.
        \end{equation}
        Then~:
        \begin {align*}
        \mu(f,x) &< \text{\tt mu}(f,x) < 4 \sqrt{n} \mu(f,x)
        \\
        \eta(f,x) &< \text{\tt eta}(f,x) < 2 \eta(f,x)
        \\
        \beta(f,x) &< \text{\tt mu}(f,x)\text{\tt eta}(f,x)
        \\
        \gamma(f,x) &< D^{3/2} \text{\tt mu}(f,x)
        \\
        \alpha(f,x) &< {D^{3/2} \over 2}\text{\tt mu}(f,x)^2\text{\tt eta}(f,x)
        \end{align*}
        }
\medskip
\par
Let $f$ and $x$ be given. Let $\zeta$ be the zero associated to $x$.
The following algorithm will return
an approximate zero of $f$, or fail. If it fails, one of the
following conditions will be false~:

\begin{equation}
\label{cond:dist}
\dproj(x,\zeta) \le {\bar u \over \bar \gamma}
\end {equation}

\begin {equation}
\label{cond:mu}
\mu(f,\zeta) \le \bar \mu
\end{equation}

\par
Constant $\bar \mu$ was defined in Theorem \ref{rob:pseu} of
Chapter \ref{ch:qct}. Constant $\bar \gamma$ is defined
in Corollary \ref{rob:cor}, Chapter \ref{ch:qct}. 
\par
If conditions (\ref{cond:dist}) and (\ref{cond:mu}) are true,
then by Lemma \ref{lem:glomu}, $\mu(f,x) \le 2 \bar \mu$. We
will prove that in that case, the output of the algorithm is
an approximate zero of $f$, associated to $\zeta$.


{
\tt
\noindent
{ALGORITHM \ } $y \leftarrow $ Zero ($f$, $x$, $\bar \mu$)

\begin{list}{\arabic{linenumber}}{\usecounter{linenumber}}
\item Let $k, \delta \leftarrow \lceil 2 + \log \log n \rceil, 
      \lceil {1 \over 200n} \rceil$ 
\item Let $\macheps$ be such that Pseudo has precision $\delta$\\
      and condition (\ref{cond:pessimistic}) is true.
\item Let $y \leftarrow $Pseudo $^k (f, x)$
\item Let $a \leftarrow {D^{3/2} \over 2}$mu$(f,x)$ eta$(f,x)$
\item If $a \ge {1 \over 8}$ Fail.
\item Return $y$.

\end{list}
}

\par
It is clear that $\alpha(f,y) < a < 32 n \alpha(f,y)$.
So if the algorithm succeeds, $y$ is certainly an 
approximate zero of $f$.
\par
Now assume conditions (\ref{cond:dist}) and (\ref{cond:mu}). 
Then $\alpha(f,y) < \min(2^{-2^k - 1}, \delta) \alpha(f,x)
\le {1 \over 32 n} \alpha(f,x)$. 
\par
Therefore, $a \le \alpha(f,x) \le 2 \bar u < 1/8$, and
the algorithm shall succeed. Moreover, the result $y$ 
is obtained from $x$ by an approximate Newton iteration, 
so it is associated to the same zero ray $\zeta$.
\medskip
\par
Let we note $Y = ${\tt Zero}$(X)$ for the application
of {\tt Zero} to a list of points $X$. The next algorithm
if it succeeds, returns an approximate solution of $f$.
\par
If it is given an approximate solution of $f$ as input,
and conditions (\ref{cond:dist}) and (\ref{cond:mu}) are
true for every point in $X$, it succeeds.


{
\tt
\noindent
{ALGORITHM \ } $Z \leftarrow $ Solution ($f$, $X$, $\bar \mu$)

\begin{list}{\arabic{linenumber}}{\usecounter{linenumber}}

\item \label{sol:1}
      If Length($X$) $\ne \prod d_i$ then FAIL.
\item \label{sol:2}
      Let $Y \leftarrow $Zero$(f,X,\bar \mu)$.
\item \label{sol:3}
      Let $Z = $Pseudo$^k(f,Y)$, where $k$, $\delta$ and $\epsilon$ are 
      chosen \\
      so that each point of $Z$ is at distance less than
      ${1 \over 4 \sqrt{2} D^{3/2} \bar \mu}$ \\
      of its associated zero.
\item \label{sol:4}
      If two of the $Z_i$ are at distance less than 
      $1 \over 2 \sqrt{2} D^{3/2} \bar \mu$, then FAIL.
\item Return $Z$.      
\end{list}
}
\par
Lines \ref{sol:3} and \ref{sol:4} check that there are not two elements of
$X$ with the same associated zero. This follows from Theorem
\ref{qct:a2:pseu} of Chapter \ref{ch:qct} and Theorem
\ref{th:gamma} of Chapter \ref{ch:gap}.  Line \ref{sol:1} checks
that there is one $X_i$ for each zero of $f$. 
 

\section {How to solve a generic system.}

Given a path $[f_0, f_1]$, it is easy to produce equally
spaced systems $f_{t_i}$ in $\Hd$. We just set~:
$$
t_i = {1 \over 2} + {\tan \theta_i \over \tan \theta_{\max}}
$$
\par
where ~: 
$$
2 \sin \theta_{\max} = 
\knorm {  {f_0 \over \knorm{f_0}} -  {f_1 \over \knorm{f_1}} }
$$
\par
and $\theta_i = \left( 2 {i \over N} - 1 \right)  \theta _{\max}$,
where $i$ ranges between $0$ and $N$. $\theta_{\max}$ is half
of the angular distance between $f_0$ and $f_1$. It follows from
trigonometry that the points~:
$$
f_{t_i} =  (1 - t_i) {f_0 \over \knorm{f_0}} +  t_i {f_1 \over \knorm{f_1}} 
$$
\par
are equally spaced.
\medskip
Now, path-following can be codified by the following algorithm~:
\medskip

{
\tt
\noindent
{ALGORITHM \ } $Y_1 \leftarrow $ Pathfollow $(f_0,f_1,Y_0)$
\begin{list}{\arabic{linenumber}}{\usecounter{linenumber}}
      \item \label{pf:1}
      $\bar \alpha, \bar u , \bar \gamma, \delta, Z,i 
      \leftarrow
      0.02, 0.05, {2 \over 3} D^{3/2} \bar mu, {\bar mu \over 2 \bar \gamma},
      Y_0,0$.
\item \label{pf:2}
      Let $t_i$ be s.t. $d_{proj}(f_{t_i},f_{t_{i+1}}) \le {3 \bar \alpha \over
      8 \bar \mu \bar \gamma}$
\item \label{pf:3}
      REPEAT $i,Z \leftarrow i+1,$Pseudo$(f_{t_i},Z)$
\item \label{pf:4}
      $Y_1 \leftarrow Z$ 
\end{list}
}
\par 
Line \ref{pf:2} can be done as described above, using that
$\dproj(f_0,f_1) \le 1$. Line \ref{pf:3} should be executed
with the precision given by Corollary \ref{rob:cor} of Chapter
\ref{ch:qct}. The actual machine precision necessary for that
is bounded in Theorem \ref{th:np} of Chapter \ref{ch:newton}. 
For a bound on the condition number, we should take $2 \bar \mu$,
to use the result of Lemma \ref{lem:glomu}.
\par
The following algorithm is corresponds to the machine of 
the Main Theorem.
\medskip

{
\tt
\noindent
{ALGORITHM \ } $X_1 \leftarrow $ SOLVE $(f_1)$ 
\begin{list}{\arabic{linenumber}}{\usecounter{linenumber}}
\item \label{solve:1}
      $f_0, X_0 \leftarrow $ STARTPOINT$(n,d)$ ; $\bar \mu = 2$ ;
\item \label{solve:2}
      REPEAT
\item \label{solve:3}
      $\ \bar \mu \leftarrow 2 \bar \mu$
\item \label{solve:4}
      \ $X_1 \leftarrow $Pathfollow$(f_0,f_1,X_0
        , \bar \mu)$ 
\item \label{solve:5}
      \ $Z \leftarrow $Solve$(f,X,\bar \mu)$.
\item \label{solve:6}
      \ UNTIL $Z \ne $ FAIL
\item \label{solve:7}
      Output $Z$  
\end{list}
}
\medskip
\par
A better version of this algorithm retraces only the paths
where the final result was not proven to be an approximate zero,
and the paths where the final result was near the final result
of another path.
\medskip 
\par
\paragraph {Proof of the Main Theorem ~:}

\par
The set $U_d$ are the complements of a section of the real algebraic variety
$\Sigma_0$ defined in Theorem \ref{th:mu2} Chapter \ref{ch:gap}. This section
is just the section of all the $(f_0, f)$ where $f_0 = ${\tt STARTPOINT}$(n,d)$~
\glossary{$U_d$&Non-degenerate locus for global solving}.
Since this section is proper in $f_0 \times \Hd$, the set $U_d$ is a 
non-trivial open set.
\par
We set $\mu_0 = \mu(\Sigma_0)$\glossary{$\mu_0$&Conditioning
of solving polynomial systems} and
$d_0 = d(\Sigma_0)$\glossary{$d_0$&Complexity exponent of
solving polynomial systems}. The bound on
$\mu$ comes from Theorem \ref{th:mu2}.
\par 
The complexity analysis of {\tt Solve} follows from the complexity
analysis of all the called procedures. 
\par
It follows from Corollary \ref{rob:cor} in Chapter \ref{ch:qct}
that the number of homotopy steps is bounded by 
$O(\mu ^2 D^{3/2})$. There are $\prod d_i$ paths to follow.
The cost of each approximate Newton iteration is $O(nD S(f)+n^3)$
floating point operations (Theorem \ref{th:n1}) with
precision $\macheps$, where $\macheps$ can be bound, as in the
proof of Theorem \ref{th:np} of Chapter \ref{ch:newton}, by
equation (\ref{choice:epsilon})~: 
$$
\macheps
=
{1 \over
{32 \over \delta} \bar \mu (1 + 4 \bar \mu) \sqrt{D}
(2  D + 1 + 2\max S(f_i) + p(n) )
+
2 H(f)
+
2 H(x)
}
$$
\par
The cost of performing each arithmetic operation is
about $\log \macheps \log \log \macheps$. Therefore, 
The cost of Path-following can be bounded by~:
\begin{equation}
\label{cost:path}
       (\prod d_i)
       (\max d_i)^{3/2} \mu^2
      \left( (n+1) S(f) \max d_i + (n+1)^3 \right)
      \times
\end{equation}
$$
       \times
       P(\log \mu, \max d_i, \log n, \log S(f), \log \log H(f))
$$
       \par
       where $P$ is a polynomial.
\medskip
\par
In Lemma \ref{lem:pess}, we require $\macheps$ to
verify condition (\ref{cond:pessimistic})~:
        $$
        4 n^{3/2} \mu(\Sigma) H(f)^{d(\Sigma)} \macheps(q) < 1.
        $$
\par
This is the reason we cannot give a more convenient bound for the time
spent checking the results of path-following. We can only state
that the cost of certifying is bounded by~:
\begin{equation}
\label{cost:cert}
       n (\prod d_i)^2 \sum d_i
      \left( (n+1) S(f) \max d_i + (n+1)^3 \right)
      \times
\end{equation}
       $$
       \times
       P(\log \mu, \max d_i, \log n, \log S(f), \log \log H(f))
       $$
\par
Adding equations (\ref{cost:path}) and (\ref{cost:cert}), we
obtain the time bound of the Main theorem.
This concludes the proof.


\section {Computational matters.}

A simplified version of the algorithms in this Thesis was 
implemented. It is available through anonymous ftp
at {\em math.berkeley.edu} until Dec 31, 1993.
Starting Jan 1, 1994, it will be available
in another site, hopefuly {\em labma.ufrj.br}.
\medskip
\par
Some of the algorithms mentioned earlier in this text can be
adapted to benefit from the architecture of modern computers.
Three issues are extremely important~:
\begin {itemize}
\item Overhead. Each time an evaluation of $f$ or $Df$ is
      performed, it is necessary to go through the data
      structure representing $f$. In some machines, this can
      be relatively time-consuming for big systems. 
      Therefore, it is a good idea to follow a large number of
      paths at once, and to go through the data structure only once
      per evaluation, for all this group of paths.
\item Pipelining. In order to take advantage of vector facilities,
      it is necessary to reduce the most time-consuming routines
      to certain vector operations. One possibility is, when
      following a large number of paths, to perform the arithmetic
      operations with vectors, each coordinate corresponding
      to one path.
\item Parallelism. If several processors are available, there
      is a natural parallelization of the algorithm, that is to
      assign a group of paths to every processor. The algorithm
      is suitable to SIMD machines (Single Instruction Multiple
      Data) as well as to MIMD machines (Multiple Instruction
      Multiple Data). If there are also vector facilities
      available, there will be a trade-off between parallelism
      and pipe-lining.
\end{itemize}
 






\appendix

\chapter {Glossary of notations}


\halign{\hfil#&\quad#\hfil&\quad\hfil#\cr
\glossaryentry{ $\norm{.}$   & Vector and matrix 2-norm}{}
\glossaryentry{ $\fnorm{.}$  & Frobenius norm of a matrix}{}
\glossaryentry{ $\onenorm{.}$& Matrix 1 norm}{}
\glossaryentry{ $\supnorm{.}$& Matrix sup norm}{}
\glossaryentry{ $M\rtrans$   & Real transpose of Matrix $M$}{}
\glossaryentry{ $M\ctrans$   & Complex transpose of Matrix $M$}{}
\glossaryentry{ $\diag(a_i)$ & Diagonal matrix $A$ such that $A_{i,i}=a_i$}{}
\glossaryentry{ $\rank M$    & Rank of matrix $M$}{}
\glossaryentry{ $\Re(z)$     & Real part of $z$}{}
\glossaryentry{ $\Im(z)$     & Imaginary part of $z$}{}
\glossaryentry{$\Hd$&A space of systems of polynomial equations}{1}
\glossaryentry{$n$&In most places, number of equations.}{1}
\glossaryentry{$d=(d_1,\dots,d_n)$&Degree of the systems of polynomials}{1}
\glossaryentry{$H(x)$&Height of a rational point or polynomial}{2}
\glossaryentry{$S(f)$&the number of non-zero coefficients of $f$}{2}
\glossaryentry{$D$&Abreviation for $\max d_i$}{8}
\glossaryentry{$\knorm{.}$&Kostlan's unitary invariant norm}{8}
\glossaryentry{$\dproj(f,g)$&Projective distance between $f$ and $g$ by $\knorm{.}$}{8}
\glossaryentry{$N_V$&Generalized Newton operator}{9}
\glossaryentry{$V$&Certain family of hyperplanes}{9}
\glossaryentry{$\beta$&Newton step length}{9}
\glossaryentry{$\gamma$&A    kind of measure of the non-linearity of a    mapping}{9}
\glossaryentry{$\alpha$&Product of $\beta$ and $\gamma$}{9}
\glossaryentry{$N\aff$&Newton operator in affine space}{10}
\glossaryentry{$\dproj(x,y)$&Distance between points $x$ and $y$ in        projective space}{10}
\glossaryentry{$N\proj$&Newton operator in projective space}{11}
\glossaryentry{$N\pseu$&Pseudo-Newton operator}{12}
\glossaryentry{$A^{\dagger}$&Moore-Penrose pseudo-inverse of matrix $A$}{12}
\glossaryentry{$\mu(f,x)$&Condition number of $f$     at $x$}{13}
\glossaryentry{$\eta(f,x)$&A corrected norm of $f(x)$}{13}
\glossaryentry{$\fl(a\diamond b)$&Computed result of $a \diamond b$}{33}
\glossaryentry{$\macheps$&Machine epsilon}{36}
\glossaryentry{$\maxnorm{.}$&sup norm of a matrix, considered as a vector}{41}
\glossaryentry{$\maxtwonorm{.}$&A norm of the space of mappings of matrices into vectors}{47}
\glossaryentry{$R_u(f)$&$u$-resultant of a system $f$ of $n$ polynomials}{61}
\glossaryentry{$R(f)$&Resultant of a system $f$ of $n+1$ polynomials}{64}
\glossaryentry{$B$&A different definition of height}{68}
\glossaryentry{$C$&A different definition of height}{68}
\glossaryentry{$\discr_v(f)$&$v$-discriminant of $f$}{73}
\glossaryentry{$\Sigma\aff$&Affine discriminant variety}{73}
\glossaryentry{$\Sigma$&Discriminant variety}{73}
\glossaryentry{$d(\Sigma)$&Complexity exponent of the discriminant variety $\Sigma$}{77}
\glossaryentry{$\mu(\Sigma)$&Condition number of the discriminant variety $\Sigma$}{77}
\glossaryentry{$\Sigma_0$&Real variety of paths with a degenerate system}{78}
\glossaryentry{$d(\Sigma_0)$&Complexity exponent of $\Sigma_0$}{78}
\glossaryentry{$\mu(\Sigma_0)$&Condition number of $\Sigma_0$}{79}
\glossaryentry{$q$&A polynomial in $D$, $S(f)$ and $n$.}{88}
\glossaryentry{$U_d$&Non-degenerate locus for global solving}{95}
\glossaryentry{$\mu_0$&Conditioning of solving polynomial systems}{95}
\glossaryentry{$d_0$&Complexity exponent of solving polynomial systems}{95}
}


%\vspace{\stretch{1.0}}




\chapter {The Author's Address and e-mail}
The author's permanent mailing address is~:
\bigskip \\
\noindent Gregorio Malajovich \medskip \\
\noindent Departamento de Matematica Aplicada \\
\noindent Instituto de Matematica \\
\noindent Universidade Federal do Rio de Janeiro \\
\noindent Caixa Postal 68530 \\
\noindent Rio de Janeiro, RJ \\
\noindent CEP 21945 \\
\noindent BRASIL \medskip \\
\noindent gregorio@@labma.ufrj.br \\



\begin {thebibliography}{12}

\bibitem{ALLGOWER}
Eugene L. Allgower and Kurt Georg,
\newblock Continuation and Path-Following. 
\newblock Preprint, Colorado State University, may 1992. 
\newblock {\em Acta Numerica} (1992) 1-64

\bibitem {LAPACK}
E. Anderson et alli,
\newblock {\em LAPACK users' guide.}
\newblock SIAM, Philadelphia, 1992.

\bibitem{BSS}
Lenore Blum, Mike Shub and Steve Smale,
\newblock {On a theory of computation and complexity
over the real numbers~: NP-completeness, recursive functions
and universal machines.}
\newblock {\em Bulletin of the AMS,} {\bf 21}, 1, July 1989.

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

\bibitem{GOLUB}
Gene H. Golub and Charles F. Van Loan,
\newblock {\em Matrix Computations.}
\newblock The John Hopkins University Press, Baltimore and London, 1989,
second printing, 1990.

\bibitem{HARDY}
G. H. Hardy and E. M. Wright,
\newblock {\em Theory of Numbers},
\newblock 4th edition,
\newblock Oxford at the Clarendon Press, 1965.

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

\bibitem{MOR}  
Alexander Morgan
\newblock {\em Solving polynomial systems using continuation for engineering
and scientific purposes.}
\newblock Prentice Hall Inc, Englewood Cliffs, New Jersey, 1987.

\bibitem{PRIEST}
Douglas M. Priest,
\newblock {\em On properties of floating point arithmetics : numerical
stability and cost of accurate computations.}
\newblock Draft of PhD Thesis, Berkeley, 9 Nov 1992.

\bibitem {RENEGAR}
James Renegar,
\newblock {On the worst-case arithmetic complexity of approximating
           zeros of systems of polynomials.}
\newblock {{\em Siam J. on Computing,} {\bf 18}, 2 , 350-370, Apr 1989.}

\bibitem{SHUB}
Michael Shub,
\newblock Some remarks on Bezout's Theorem and complexity theory.
\newblock {\em in} M. Hirsch, J. Marsden and M. Shub (ed),
\newblock {\em From Topology to Computation},
\newblock Proceedings of the Smalefest, 1993.

\bibitem{BEZI}
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{BEZII}
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{BEZIII}
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{BEZIV}
Michael Shub and Steve Smale,
\newblock Complexity of Bezout's Theorem IV ~; Probability of success~ ;
Extensions
\newblock Preprint, Berkeley, 1993.

\bibitem{PE}
Steve Smale,
\newblock Newton method estimates from data at one point,
\newblock in R. Erwing, K. Gross and C. Martin (editors).
\newblock {\em The merging of disciplines~: New directions
  in Pure, Applied and Computational Mathematics}.
\newblock Springer, New York, 1986

\bibitem {VAN}
B. L. Van der Waerden,
\newblock {\em Modern Algebra, Vol 2.}
\newblock {F. Ungar publishing Co, New York, 1950} 

\bibitem{WILKINSON}
J. H. Wilkinson,
\newblock {\em The algebraic eigenvalue problem},
\newblock Clarendon Press, Oxford, 1965, Reprinted 1969.

\bibitem{WILKINSON2}
J. H. Wilkinson,
\newblock Error analysis of direct methods of matrix inversion,
\newblock {\em Journal of the ACM}, {\bf 8}, 281-330, 1961.

\end {thebibliography}




\end{document}


