%
%      Worst Possible Condition Number of Polynomial Systems
%
%      by Gregorio Malajovich
%         gregorio@labma.ufrj.br
%
%      Preprint.
%      Rio de Janeiro, Oct 27, 1995
%
%      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.org
%      It can be ontained by anonymous ftp.
%
% -----------------------------------------------------------------
%
%      Some corrections were introduced since the Oct 17 version.
%      The old text is commented-out, and the new text follow.
%      The more important modification is in the statement of the
%      Main theorem, where the word variety was replaced by
%      Zariski closed set. GM, Oct27,95.
%
% -----------------------------------------------------------------

\documentstyle[12pt]{amsart}

\newcommand{\aff}{^{\text {\rm aff}}}
\newcommand{\proj}{^{\text {\rm proj}}}
\newcommand{\pseu}{^{\text {\rm pseu}}}
\newcommand{\rtrans}{^{\text{\rm t}}}
\newcommand{\ctrans}{^{\text{\rm *}}}
\newcommand{\dproj}{d_{\text{\rm proj}}}
\newcommand{\exact}{_{\text{\rm exact}}}
\newcommand{\appr}{_{\text{\rm appr}}}
\newcommand{\opt}{_{\text{\rm opt}}}
\newcommand{\diag}{{\text{\rm diag}}}
\newcommand{\discr}{{\text{\rm discr}}}
\newcommand{\rank}{{\text{\rm rank}}}
\newcommand{\sgn}{{\text{\rm sgn}}}
\newcommand{\arc}{{\text{\rm arc}}}
\newcommand{\fl}{\text{\rm fl}}
\newcommand{\tensor}{\otimes}
\newcommand{\drond}{\partial}
\newcommand{\Hd}{{\cal H}_d}
\newcommand{\Pd}{{\cal 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{k}}}}
\newcommand{\infnorm}[1]{{\left \| {#1} \right \|_{\infty}}}
\newcommand{\fnorm}[1]{{\left \| {#1}\right  \|_{\text{\rm f}}}}
\newcommand{\kinner}[2]{{\left < {#1} , {#2} \right  >_{\text{k}}}}
\newcommand{\inner}[2]{{\left < {#1} , {#2} \right  >}}
\newcommand{\norm}[1] {{\left \| {#1} \right \|_2}}
\newcommand{\abs}[1] {{\left | {#1} \right |}}
\newcommand{\onenorm}[1]{{\left \| {#1} \right \|_1}}
\newcommand{\bignorm}[1]{{\left \| {#1} \right \|_2}}
\newcommand{\supnorm}[1]{{\left \| {#1} \right \|_{\infty}}}
\newcommand{\maxnorm}[1]{{\left \| {#1} \right \|_{\text{\rm max}}}}
\newcommand{\maxtwonorm}[1]{{\left \|{#1}\right \|_{\text{\rm max,2}}}}
\newcommand{\height}[1]{{\bold{H}\left({#1}\right)}}
\newcommand{\bheight}[1]{{\bold{B}\left({#1}\right)}}
\newcommand{\cheight}[1]{{\bold{C}\left({#1}\right)}}
\newcommand{\fmu}{{\mu_{\text{\rm f}}}}

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


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


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

\newcounter{linenumber}

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

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

\theoremstyle {definition}

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

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

\renewcommand{\themainmain}{}

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

\title      {Worst Possible Condition Number\\
             of Polynomial Systems}
\author     {Gregorio Malajovich}
\date       {August 27, 1995}
\thanks     {Sponsored by CNPq (Brasil).}
\thanks     {Typeset using \AmS - \LaTeX}
\subjclass  {65H10, 65H20, 68Q25}
\address    {Departamento de Matematica Aplicada da UFRJ \\
             Caixa Postal 68530 \\
              CEP 21945 \\
              Rio \\ RJ \\
              Brasil}
\email      {gregorio@@lyric.labma.ufrj.br}

\begin{document}
\maketitle
\begin{abstract}
         A worst case bound for the condition number of a
         generic system of polynomial equations      with
         integer coefficients is given. For fixed  degree
         and number of equations, the condition number is
         (non-uniformly, generically)   pseudo-polynomial
         in the input size.
\end{abstract}

\section{Introduction}   \label{sec:1}


         The B\'ezout problem may be stated as follows~: given a
         {\em generic} system of $n$ homogeneous polynomial
         equations of degree $d = (d_1, \dots, d_n)$ in $n+1$
         complex variables, {\em find} all the roots in
         complex projective space.
      \par
         To {\em find} a root means to exhibit a (proven)
         {\em approximate zero}, i.e., a point whose iterates
         by a suitable Newton operator will converge quadratically.
         See Smale~\cite{PE}~, and Shub and Smale~\cite{BEZI}~.
  \medskip
      \par
         The complexity of solving the B\'ezout problem was bounded
         in terms of the Shub and Smale condition number $\mu$
         (See Shub and Smale~\cite{BEZI,BEZII,BEZIII,BEZIV,BEZV}~.
         For the corresponding discrete theory, see Malajovich
         ~\cite{PhD,TCS}~).
      \par
         The condition number $\mu$ may be defined by~:
      $$
         \mu(f) = \max_{\zeta \ne 0, f(\zeta) = 0} \mu(f,\zeta)
      $$
      \par
         where~:
      $$
         \mu(f,\zeta) = \knorm{f}
                        \norm{    Df(\zeta)_{| \zeta ^\perp}^{-1}
                                     \diag \left( \| \zeta \|^{d_i - 1}
                                                  \sqrt{d_i} \right)
                                     }
      $$
      \par
         Here, $\knorm{.}$ is Kostlan's invariant norm $\knorm{f} ^2 =
         \sum \knorm{f_i} ^2$ where~:
      $$
         \knorm{f_i}^2 = \sum_{|J|=d_i}  |f_{iJ}|^2
                                         {J_0 ! \dots J_n ! \over d_i !}
      $$
      \par
         This norm is known to be $U(n+1)$-invariant. The set of all $f$
         such that $\mu(f) = \infty$ is an algebraic variety $\Sigma$~,
         called the {\em discriminant variety}~.
  \medskip
      \par
         As we deal with such kind of continuous problems, it makes
         no sense to speak of a worst case complexity (i.e. a worst case
         bound for $\mu$~). Instances of the problem may be arbitrarily
         ill-conditioned.
      \par
         However, one may be concerned with the restriction of a
         continuous problem to a discrete input set. For instance, one
         may study the B\'ezout problem restricted to systems of integer
         or Gaussian integer coefficients.
      \par
         Then one may speak on the classical (Turing, BSS over $\Bbb Z$)
         complexity of solving the restricted (discrete) problem. That
         complexity analysis may use techniques and results from the
         original (continuous) problem.
  \medskip
      \par
         Once we fix $d = (d_1, \dots , d_n)$~, the number of coefficients
         of $f$ is bounded by $\sum_i \binomial{d_i+n-1}{d_i}$~; therefore,
         {\em input size} may be measured by the {\em height} of the
         coefficients of $f$~.
      \par
         Heights may be defined in many ways. For convenience, we will set~:
      $$
         \height{a+bi} = |a| + |b| \ , a,b \in {\Bbb Z}
      $$
      \par
         although this is a not the number-theoretical definition.
  \medskip
      \par
         Let $\Hd$ be the space of all the systems of homogeneous polynomials
         of degree $d = (d_1, \dots d_n)$ in $n$ variables, with complex
         coefficients. We shall prove~:
  \medskip
      \par
{\mainmain
%
%         Bad statement below :
%
%         Let $d$ be fixed. There is a proper variety $\Sigma ' \in \Hd$,
%
%         Correction :
%
         Let $d$ be fixed. There is a Zariski closed set
         $\Sigma \subseteq \Hd$, $\Sigma \ne \Hd$,
%
         and there are numbers $d(\Sigma ')$ and $\mu(\Sigma ')$ such
         that, for any $f \in \Hd$, $f \not \in \Sigma '$, $f$ with Gaussian
         integer coefficients,
      $$
         \mu(f) \le \mu(\Sigma) \  \height{f} ^ {d(\Sigma)}
      $$
      \par
         Furthermore,
      \begin{align*}
         d(\Sigma ') &\le n \prod d_i \sum d_i
         \\
         \mu(\Sigma ') &\le {\pi \over 2} d(\Sigma ')
                         \left( 3
                                \prod d_i
                                \left( { e \over \sqrt{2 \pi} } \right)^{n-1}
                                n^{\sum d_i -n + 2}
                         \right) ^{1 + d(\Sigma ')}
      \end{align*}
      }
   \medskip
      \par
         In other words~: once we fix $d$, the condition number $\mu(f)$
         is pseudo-polynomial (See Garey-Johnson~\cite{GJ}) in the
         input size (for $f$ not in $\Sigma$, of course).
      \par
         Another restatement: for non-degenerate $f$, $\mu(f)$ is non-uniform
         pseudo-polynomial in the input size.
   \medskip
   \par
     One can take the discriminant variety $\Sigma$ instead of $\Sigma '$
     in the statement of the Main Theorem. This will decrease $d(\Sigma)$,
     but may possibly increase $\mu(\Sigma)$~.
   \medskip
      \par
         The main Theorem provides us with an {\em a priori} bound on the
         condition number (for $\mu$ not in $\Sigma$). This bound may be
         used to bound the number of steps and the machine precision
         necessary for a homotopy algorithm to succeed generically.
      \par
         Also, it can be used
         to guarantee that certain $z \in {\Bbb C}^{n+1}$ is indeed an
         approximate zero of a non-degenerate $f$.
         One would use the bound on $\mu(f)$ to bound the Wilkinson condition
         number $\kappa$ of $Df(z)_{|z^{\perp}}$. Standard linear system
         solvers are known to provide a result within error bounded by
         $O(\kappa \macheps)$, where $\macheps$ is the {\em machine epsilon}.
         (Recall $d$ and $n$ are fixed). Therefore, one may compute~:
      $$
         \beta(f,z) = \| {Df(z)_{|z^{\perp}}} ^{-1} f(z)\|
      $$
      \par
         within error $O(\kappa \macheps)$. Therefore, computing $\beta$
         to within error $\delta$ costs $O(\log \height{f} - \log \delta)$~.
      \par
         The invariant $\gamma$ may be bounded as in \cite{BEZI} by
         $\mu {{\max d_i}^{3 \over 2} \over 2}$~, hence we may obtain a
         reasonably cheap bound for $\alpha$.
      \par
         For a more algorithmic explanation of the consequences this
         Theorem, see \cite{PhD}, chapter 5.






\section{Outline of the proof}  \label{sec:2}



         It was proven by Shub and Smale~(\cite{BEZI}) that~:
      $$
         \mu(f,\zeta) = {1 \over d_k (f, \Sigma \cap V_{\zeta}) }
      $$
         \par
         where $V_{\zeta}$ is the subspace  of all $f \in \Hd$ such
         that $f(\zeta) = 0$, and $\Sigma$ is the discriminant variety.
         The distance $d_k$ is taken in Projective Space, i.e.~:
      \begin{equation}
      \label{eq1}
         d_k(f,g) = \min_{\lambda \in {\Bbb C}}
                        {\knorm{f - \lambda g} \over \knorm{f}}
      \end{equation}
      \par
         Equation (\ref{eq1}) implies~:
      $$
         \mu(f) \le {1 \over d_k(f,\Sigma)}
      $$
      \par
         where we removed the restriction of the distance to subspace
%
%     Bad statement below :
%
%        $V_{\zeta}$~. If $\Sigma '$ is a variety containing $\Sigma$,
%
%     Fixed text :
%
         $V_{\zeta}$~. If $\Sigma '$ is a Zariski closed set
          containing $\Sigma$,
%
         then~:
      $$
         \mu(f) \le {1 \over d_k(f,\Sigma')}
      $$

      \par
         Assuming that $f \not \in \Sigma$, we want to obtain a bound
         for $d(f,\Sigma)$. As $\height{f}$ is bounded, such a bound
         $\min_{f \not \in \Sigma, \height{f} \le H} d(f,\Sigma)$
         should certainly exist.
   \medskip
      \par
         The discriminant variety $\Sigma$ is the set of all $f$
         such that there is $\zeta \ne 0$ with $f(\zeta)=0$ and $Df(\zeta)$
         not surjective. (recall
         that $Df(\zeta)$ is a $(n+1) \times n$ matrix). The root $\zeta$
         can be taken to have norm $1$, or to belong to ${\Bbb P}^n$~.
      \par
         An easy way to produce a proper $\Sigma '$ containing $\Sigma$
         is to consider a chart $A_i$ of ${\Bbb P}^n$ given by~:
      $$
         A_i : (x_0, \dots, x_{i-1}, x_{i+1}, \dots , x_n)
         \mapsto (x_0, \dots, x_{i-1}, 1, x_{i+1}, \dots , x_n)
      $$
      \par
%
%     Misprint below :
%     Then $\Sigma ' contains \Sigma$ where $\Sigma '$ is the
%
%     Fixed text :
%
         Then $\Sigma '$ contains $\Sigma$ where $\Sigma '$ is the
%
         zero-set of
         $p = \discr(f \circ A_i) = R(f_1 \circ A_i, \dots,
         f_n \circ A_i, \det D(f \circ A_i)$~, where $R$ is the
         resultant (See Salmon~\cite{SALMON}, Macaulay~\cite{MACAULAY}
         or Van der Waerden~\cite{WAERDEN})~. In section \ref{sec:3},
         we will show that~:
{\proposition \label{prop:1}
         The polynomial $p$ defined above is a multi-homogeneous
         polynomial of degree $r_1, \dots, r_n$ in sets of $m_1$
         variables $f_1$, $\dots$, $m_n$ variables $f_n$, with
         integer coefficients,
         where $m_i = \binomial{d_i + n - 1}{d_i}$ and
         $r_i = (\prod d_j)(1 + {\sum d_j - n
         \over d_i})$~. The sum of the absolute values of the
         coefficients of $p$ is bounded above by~:
      $$
         \bheight{p} \le \left(3 \prod d_i
                  \left( {e \over \sqrt{2 \pi}}\right)^{n-1}
                  n^{\sum d_i - n + {3\over 2}} \ e^{1 \over 12}
                  \right) ^ {\sum r_i}
      $$
         }
   \medskip
      \par
         We may lower each of the numbers $r_i$ by choosing
      the discriminant variety instead of $\Sigma '$. The author does
      not know how to provide a reasonable bound for $\mu(\Sigma)$.
   \medskip
   \par

         In section \ref{sec:4}, we will prove the~:
{\theorem \label{th:1}
         Let $p$ be a multi-homogeneous polynomial of degree $r_1, \dots,
         r_n$ in sets of variables $f_1 \in {\Bbb C}^{m_1}$,
         $\dots$, $f_n \in {\Bbb C}^{m_n}$~,
         with integer coefficients. Assume also that
         groups of variables $f_i$ range over Gaussian integers.
         Then either $p(f)=0$, or~:
      $$
         d_2 (f,Z(p)) \ge
         {1 \over {\pi \over 2} \max \sqrt{m_i} \sum r_i \bheight{p} }
         \left( { 1 \over \height{f} } \right)^{\sum r_i}
      $$
         \par
         where $Z(p)$ is the zero-set of $p$ and $d_2$ is the projective
         $2$-distance.
         }
   \medskip
      \par
         {\bf Proof of the Main Theorem~:} We set $d(\Sigma) = \sum r_i$~.
         In section~\ref{sec:5}, we shall prove the Lemma~:
{\lemma \label{lem:1}
      $$
         \sum r_i \le n \prod d_i \sum d_i
      $$
         }
      \par
         We apply Theorem~\ref{th:1} to the polynomial
         $p = \discr(f)$ defined above. We conclude that if $f$ has
         Gaussian integer coefficients then either $\discr f = 0$~,
         or~:
      $$
         d_2 (d, \Sigma_i)
         \ge
         {1 \over {\pi \over 2} \max \sqrt{m_i} d(\Sigma)
                  \left(3 \prod d_i ({e \over \sqrt{2\pi}})^{n-1}
                  n^{\sum d_i - n + {3 \over 2}} e^{1 \over 12}\right)
                  ^  {d(\Sigma)}
                  }
         \left( {1 \over \height{f}} \right) ^{d(\Sigma)}
      $$
      \par
         Furthermore, we will need from section~\ref{sec:5} the~:
{\lemma \label{lem:2}
      $$
         d_k(f,g) \le \sqrt{n^{\max d_i} ({e \over \sqrt{2 \pi}})^{n-1}
                      e^{1 / 12} \sqrt{n} \ } d_2(f,g)
      $$
         }
      \par
         Therefore, under the conditions of the Main Theorem, either
         $f \in \Sigma_i$ (some $i$), or for all $i$~:
      $$
         d_k (d, \Sigma_i)
         \ge
         {1 \over {\pi \over 2} \max \sqrt{m_i} d(\Sigma)
                  \left(3 \prod d_i ({e \over \sqrt{2\pi}})^{n-1}
                  n^{\sum d_i - n + {3 \over 2}} e^{1 \over 12}\right)
                  ^  {1 + d(\Sigma)}
                  }
         \left( {1 \over \height{f}} \right) ^{d(\Sigma)}
      $$
      \par
         We may also bound~:
      $$
         \sqrt{m_i}
         =
         \sqrt{\binomial{d_i+n-1}{d_i}}
         \le
         \sqrt{(n-1)^{d_i+n-1} }
         \le
         \sqrt{n}^{d(\Sigma)}
      $$
      \par
         So we set, as in Main Theorem~:
      $$
         \mu (\Sigma)
         =
         {\pi \over 2} d(\Sigma)
                         \left( 3
                                \prod d_i
                                \left( { e \over \sqrt{2 \pi} } \right)^{n-1}
                                n^{\sum d_i -n + 2}
                         \right) ^{1 + d(\Sigma)}
      $$
      \par
         With this notation, either $f \in \Sigma_i$ for some $i$,
         or~:
      $$
         d(f,\Sigma) \ge \min d(f,\Sigma_i)
         \ge \mu(\Sigma)^{-1} \left( {1 \over \height{f}} \right) ^{d(\Sigma)}
      $$
      \par
         Therefore,
      $$
         \mu(f) \le {1 \over d_k(f,\Sigma)} \le \mu(\Sigma) \
         \height{f}^{d(\Sigma)}
      $$
      \par
         concluding the proof of the Main Theorem.
   \medskip
      \par
         The following Lemma is proved in Section~\ref{sec:5}~, and
         used two times in this paper. Therefore we state it here~:
      \medskip
      \par
{\lemma \label{lem:3}
         Let $d \ge 1$ be fixed, and let $J = J_1 \dots J_n$~.
      $$
         \max_{|J|=d} \binomial{d}{J}
         \le
         n^d
         \left(
         { e \over \sqrt{2 \pi} }
         \right) ^{n-1}
         \sqrt{n}
         e^{1 \over 12}
      $$
         }



\section{Proof of Proposition \ref{prop:1}}  \label{sec:3}

         The purpose of this section is to prove Proposition~\ref{prop:1}~.
         The first part of the proposition is easy, and will be proved now.
         The second part will require some intermediate results, and therefore
         it will be postponed to the end of this section.
      \par
         The number $m_i$ of $f_{iJ}$ is clearly
         $\binomial{d_i+n-1}{d_i}$~, that is, the number of
         possible monomials of degree $d_i$ in $n$ variables.
      \medskip
      \par
\subsection{Degree of the discriminant}
         Let $p = \discr (f) = R(f_1, \dots , f_n, \det Df)$~, where
         the $f_i$ are non-homogeneous polynomials of degree $d_i$ in
         variables $x_1$, $\dots$, $x_n$. The notation $R(.)$ stands
         for the resultant of a system of polynomials.
      \par
         As it is well-known, the resultant $R(f_1, \dots, f_n, g)$ is
         a multi-homogeneous polynomial in each set of variables $f_i$
         or $g$~, with integer coefficients.
      \par
         It's degree in each set of variables is given by~:
      \begin{align*}
         &\deg_g R(f_1, \dots , f_n, g) = \prod d_i
      \\
         &\deg_{f_i} R(f_1, \dots , f_n, g)
         =
         (\deg g) \prod_{j \ne i} d_j
      \end{align*}
      \par
         Now, if we set $g = \det Df$, then $\deg_x g = \sum d_j - n$~.
         Each coefficient of $g$ is a multi-homogeneous monomial of degree
         $1$ in each set of variables $f_i$ or $g$~. Therefore,
      \begin{align*}
         \deg_{f_i} p
         &=
         \deg_{f_i} R(f_1, \dots , f_n, g)
         + \deg_g R(f_1, \dots , f_n, g) \deg_{f_i} g
         \\
         &=
         \prod d_j
         +
         \left( \prod_{j \ne i} d_j \right)
         \left( \sum d_j - n \right)
         \\
         &=
         \prod d_j
         \left( 1 + {\sum d_j - n  \over d_i} \right)
         \\
         &=
         r_i
      \end{align*}
      \par
         So the degree of $p$ in the set of variables $f_i$ is
         precisely $r_i$.
      \medskip
      \par
\subsection{Alternative definitions of height}
         The second part of proposition~\ref{prop:1} requires
         some alternative definitions of Height. Also, some properties
         of those new heights will be discussed.
      \par
         We shall work in a more general framework.
         In this paper, we shall assume that some {\em height} $\height{.}$
         is defined
         in a ring $R$. The main examples are the integers and the Gaussian
         integers. We require the following axioms to be true~:
      \begin{align*}
         &\height{1} = \height{-1} = \height{i}  = \height{-i} = 1
         \\
         &\height{a+b} \le \height{a} + \height{b}
         \\
         &\height{ab} \le \height{a} \height{b}
      \end{align*}
      \par
        Those are verified by our previous definition of $\height{.}$
        as $\height{a+bi} = |a| + |b|$~.
      \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
        indices. We define a height $\bheight{.}$ on the ring of integers
        of $L$~:
      $$
         \bheight{\sum a_I f^I} = \sum \height{a_I}
      $$
      \par
         The following properties of $\bheight{.}$ are obvious~:
      \begin{align*}
         &\bheight{1} = \bheight{-1} = \bheight{i} = \bheight{-i} = 1
         \\
         &\bheight{g+h} \le \bheight{g} + \bheight{h}
         \\
         &\bheight{gh} \le \bheight{g} \bheight{h}
      \end{align*}
      \par
        We also want to extend this definition to monic integral polynomials
        in $L[t]$ ($t \in R$), but in a different way. We define~:
      $$
         \cheight{ t^d + p_{d-1} t^{d-1} + \dots + p_0 } =
         \max \left(\bheight{p_i}^{1 \over d - i}\right)
      $$
      \par
         This is not properly a height (since it make no sense to
         add monic polynomials).
      \par
         The following facts were proved by Canny~\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*}
         &\cheight{pq} \le \cheight{p} + \cheight{q}
         \\
         &\cheight{p/q} \le \cheight{p} + 2 \cheight{q}
         \\
         &\cheight{det M - t I} \le n \max \bheight{M_{ij}}
      \end{align*}
        }
    \medskip
    \par
         {\bf 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 + r_0
      \end{align*}
      \par
         where~:
      $$
         r_i = \sum_{\begin{Sb} 0 \le j \le m \\
                                0 \le i-j \le n \end{Sb}}
                                p_j q_{i-j}
      $$
      \par
         By definition,
      \begin{align*}
         \cheight{pq} &= \max \bheight{\sum_{\begin{Sb} 0 \le j \le m \\
                                0 \le i-j \le n \end{Sb}}
                                 p_j q_{i-j}^{1 \over n+m-i}}
         \\
         \cheight{pq} &\le \max \left ( \sum_{\begin{Sb} 0 \le j \le m \\
                                0 \le i-j \le n \end{Sb}}
                                 \bheight{p_j} \bheight{q_{i-j}}
                          \right)^{1 \over n+m-i}
      \end{align*}
      \par
         So there is $i$ such that~:
      $$
         \cheight{pq}^{n+m-i}
         \le
         \sum_{\begin{Sb} 0 \le j \le m \\
                                0 \le i-j \le n \end{Sb}}
                                 \cheight{p}^{m-j} \cheight{q}^{n-i+j}
      $$
      \par
         On the other hand,
      $$
         ( \cheight{p} + \cheight{q} )^{n+m-i}
         =
         \sum_{i-n \le j \le m}
         \binomial{n+m-i}{m-j} \cheight{p}^{m - j} \cheight{q}^{n-i+j}
      $$
      \par
         Comparing term by term,
      $$
         \cheight{pq}^{n+m-i}
         \le
         ( \cheight{p} + \cheight{q} )^{n+m-i}
      $$
      \par
         Hence
      $$
         \cheight{pq} \le \cheight{p} + \cheight{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 + r_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*}
         \bheight{r_{m-n-j-1}}
         &\le \bheight{p_{m-j-1}} + \sum_{0 \le i \le j}
         \bheight{r_{m-n-i}} \bheight{q_{n+i-j-1}}
         \\
         \bheight{r_{m-n-j-1}}
         &\le \cheight{p}^{j+1}
         + \sum_{0 \le i \le j}
           \bheight{r_{m-n-i}}
           \cheight{q}^{j+1-i}
      \end{align*}
      \par
         We proceed by induction on $i$.
         Assume that $\bheight{r_{m-n-j}} \le (\cheight{p}
         + 2 \cheight{q})^j$ for all
         $j \le i$. This is trivially true for $i=0$. By induction,
      \begin{align*}
         \bheight{r_{m-n-j-1}}
         &\le \cheight{p}^{j+1}
         + \sum_{0 \le i \le j}
           ( \cheight{p} + 2 \cheight{q} )^i
           \cheight{q}^{j+1-i}
         \\
         &\le \cheight{p}^{j+1}
         + \cheight{q} \sum_{0 \le i \le j}
           ( \cheight{p} + 2 \cheight{q} )^i
           \cheight{q}^{j-i}
         \\
         &\le \cheight{p}^{j+1}
         + \cheight{q} \sum_{0 \le i \le j}
           2^{i-j} ( \cheight{p} + 2 \cheight{q} )^j
         \\
         &\le \cheight{p}^{j+1}
         + 2 \cheight{q} ( \cheight{p} + 2 \cheight{q} )^j
         \\
         &\le \cheight{p} (\cheight{p}  + 2 \cheight{q})^j
         + 2 \cheight{q} ( \cheight{p} + 2 \cheight{q} )^j
         \\
         &\le
         ( \cheight{p} + 2 \cheight{q} )^{j+1}
      \end{align*}
      \par
         Thus,
      $$
         \cheight{r} \le \cheight{p} + 2 \cheight{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
         at most $n-i$
         entries of height $\bheight{.}$ less than $\bheight{M}$,
         so we have~: $|a_i| \le (n \bheight{M})^{n-i}$.
      \par
      $$
        \cheight{\det(M - tI)} \le n \bheight{M}
      $$
      \par
         Lemma \ref{lem:C} is now proved.
   \medskip
      \par
\subsection{Height of the determinant}

      \par
         If $g = \sum g_J x^J \in L[x]$, we write
         $\bheight{g} = \max_J \bheight{g_J}$~.
   \medskip
      \par
   {\lemma \label{lem:g}
         Let $g = \det Df(x) \in L[x]$~. Then~:
      $$
         \bheight{g} \le \prod d_i \left( {e \over \sqrt{2 \pi}}\right)^{n-1}
         n^{\sum d_i-n+{1\over 2}} e^{1 \over 12}
      $$
         }
      \par
         {\bf Proof~: } If we consider $g$ as an element of $R[f,x]$~,
         then we may bound~: $\height{m_I} \le \prod d_i$~, where $m_I$ is the
         coefficient of a monomial of $g$~.
      \par
         Indeed, each monomial~: $m_I f_{1,I_1} f_{2,I_2} \dots f_{n,I_n}
         x ^{\sum I_j - \sum e_j}$ can be written as~:
      $$
         \det
            \begin{pmatrix}
            f_{1,I_1} {\partial x^{I_1} \over \partial x_1}
            &
            \dots
            &
            f_{1,I_1} {\partial x^{I_1} \over \partial x_n}
            \\
            \vdots
            &
            &
            \vdots
            \\
            f_{n,I_n} {\partial x^{I_n} \over \partial x_1}
            &
            \dots
            &
            f_{n,I_n} {\partial x^{I_n} \over \partial x_n}
            \\
            \end{pmatrix}
         =
         \det
            \begin{pmatrix}
            I_{1,1}
            &
            \dots
            &
            I_{1,n}
            \\
            \vdots
            &
            &
            \vdots
            \\
            I_{n,1}
            &
            \dots
            &
            I_{n,n}
            \\
            \end{pmatrix}
         f_{1,I_1} f_{2,I_2} \dots f_{n,I_n}
         x ^{\sum I_j - \sum e_j}
      $$
      \par
         Therefore, we may write~:
      $$
         m_I =
         \det
            \begin{pmatrix}
            I_{1,1}
            &
            \dots
            &
            I_{1,n}
            \\
            \vdots
            &
            &
            \vdots
            \\
            I_{n,1}
            &
            \dots
            &
            I_{n,n}
            \\
            \end{pmatrix}
      $$
      \par
         Each line of this matrix has $2$-norm bounded above by $d_i$.
         Therefore, $m_I \le \prod d_i$~. Set~:
      $$
         \rho = \max_{|J| = \sum d_i - n}
                \# \{ I, | I_j | = d_j, \sum I_j - \sum e_j = J \}
      $$
      \par
         Now we have~: $\bheight{g} \le \rho \prod d_i$~. It remains to bound
         $\rho$. Clearly,
      $$
         \rho \le
         \binomial{\sum d_j - n}{d_1-1 \dots d_n - 1}
         =
         { \sum d_i - n ! \over d_1 - 1 ! \dots d_n - 1 !}
      $$
      \par
         Indeed, this is the number of arrangements of $\sum d_i - n$ different
         variables into $n$ sets of size $d_i - 1$. This seems to the author
         a rather pessimistic bound, and may be improved.
      \par
         We may now apply Lemma~\ref{lem:3}~:
      $$
         \rho
         \le
         n^{\sum d_i - n}
         \left( { e \over \sqrt{2 \pi} } \right) ^{n-1}
         \sqrt{n}
         e^{1 \over 12}
      $$
      \par
         Proving Lemma~\ref{lem:g}~.





   \medskip
      \par
\subsection{Macaulay's formula for the resultant}
         Let $\cal M$ be the vector space generated by all monomials
         of degree ${\cal D} = \sum \tilde d_i - n$ in variables $x_1$,
         $\dots$, $x_n$.
      \par
         To each system of $n+1$ homogeneous polynomials of degree
         $\tilde d_1$, $\dots$, $\tilde d_{n+1}$, we associate a
         matrix $A(f)$, that corresponds to the operator~:
      $$
         g \mapsto \sum g_i f_i
      $$
      \par
         where $g_i$ is a polynomial of degree ${\cal D} - \tilde d_i$. This
         matrix is defined as follows~:
      \par
         Let $x^m$ be a monomial of degree $\cal D$~. Monomial $x^m$
         is said to be unreduced in $x_i$ if and only if $m_i \ge
         \tilde d_i$~. Obviously, $x^m$ is unreduced in at least
         one of the variables $x_1, \dots, x_n$. Let $x_l$ be the first
         variable $x^m$ is unreduced in~:
      \par
         Matrix $A(f)$ maps $x^m$ into ${x^m \over {x_l}^{d_l}}f_l$.
      \par
         Matrix $A(f)$ is square. It is easy to see that if the $f_i$
         have a non-zero common root, then $\det A(f) = 0$. Indeed,
         let $\tilde x$ be that common root, and let $\tilde X \in \cal M$
         be the vector of all $\tilde x^m$~. For any system $g$,
      $$
         g A(f) \tilde X = \sum g_i(\tilde x) f_i(\tilde x) = 0
      $$
      \par
         Therefore, $A(f) \tilde X = 0$, hence $A(f)$ is not surjective.
   \medskip
      \par
         The converse is not true. The polynomial $\det A(f)$ may assume
         different values, depending on the ordering of variables $x_i$~.
         It was proven by Macaulay~\cite{MACAULAY} that~:
      $$
         R(f_1, \dots, f_{n+1}) = \gcd \det A(f)
      $$
      \par
         where the $\gcd$ is taken over all possible orderings of the
         $x_i$'s. Furthermore, let $B(f)$ be the submatrix of $A(x)$
         corresponding to the subspace of monomials unreduced in more
         than one variable.
   {\theorem [Macaulay] \label{th:mac}
      $$
         R(f_1, \dots, f_{n+1}) = { \det A(f) \over \det B(f) }
      $$
         }
         \par
         For a proof, see Macaulay~\cite{MACAULAY}~.
   \medskip
      \par
\subsection{End of the proof of Proposition~\ref{prop:1}}
         We proved (Lemma \ref{lem:g}) that the height $\bheight{\det Df}
         \in L[x]$ is bounded by~:
      $$
         \bheight{\det Df} \le
               \prod d_i \left( {e \over \sqrt{2 \pi}}\right)^{n-1}
               n^{\sum d_i - n + {1\over 2}} e^{1 \over 12}
      $$
      \par
         Hence, the height of matrices $A(f)$ and $B(f)$ defined above
         verifies~:
      $$
         \bheight{ A(f) } \le
               \prod d_i \left( {e \over \sqrt{2 \pi}}\right)^{n-1}
               n^{\sum d_i - n + {1\over 2}} e^{1 \over 12}
      $$
      $$
         \bheight{ B(f) } \le
               \prod d_i \left( {e \over \sqrt{2 \pi}}\right)^{n-1}
               n^{\sum d_i - n + {1\over 2}} e^{1 \over 12}
      $$
      \par
         Let $I$ denote the identity. According to Lemma~\ref{lem:C}~:
      \begin{align*}
         \bheight {\discr(f)}
         &\le (\cheight{\det A - tI} + 2 \cheight{\det B - t I})
           ^{\sum r_i} \\
         &\le (n \bheight{A(f)} + 2 n \bheight{B(f)}) ^{\sum r_i} \\
         &\le (3n \bheight{\det Df})^{\sum r_i} \\
         &\le \left(
              3 n
               \prod d_i \left( {e \over \sqrt{2 \pi}}\right)^{n-1}
               n^{\sum d_i - n + {1\over 2}} e^{1 \over 12}
              \right) ^{\sum r_i}
      \end{align*}

   \medskip
      \par

\section{Proof of Theorem \ref{th:1}} \label{sec:4}



         We shall construct an embedding of $\Hd$ into ${\Bbb C}^N$~,
         $N$ large enough, so that the image of $\Sigma$ be the
         intersection of a hyperplane with the image of $\Hd$~.

\subsection{Embedding of $\Hd$ into ${\Bbb C}^N$}
      \par
         More precisely~: Let
      $$
          V_{r_i} : {\Bbb C}^{m_i} \rightarrow {\Bbb C}^{M_i}
      $$
      \par
         where $M_i = \binomial{m_i + r_i - 1}{r_i}$~, be the $r_i$-uple
         embedding. Let
      $$
         S_n : {\Bbb C}^{M_1} \times \dots \times {\Bbb C}^{M_n}
         \rightarrow
         {\Bbb C}^N \ , \ N = \prod M_i
      $$
      \par
         be the Segre embedding. Define~:
      $$
      \begin{array}{lrcl}
         E : & \Hd & \rightarrow & {\Bbb C}^N \\
             &f   &\mapsto     &S_n(V_{r_1}(f_1), \dots, V_{r_n}(f_n))
      \end{array}
      $$
      \par
         Embedding $E$ maps $\Hd$ into the space of all monomials that
         may appear in multivariate homogeneous polynomial $p(f_1, \dots,
         f_n)$~.
      \par
         Therefore, if we define the push-forward $E_* p$ of $p$ as
         the linear form whose coordinates are the monomials of $p$,
         we have the relation~:
      $$
         p(f) = (E_* p)(E(f))
      $$
      \par
         Hence $\Sigma = p^{\perp} \cap E(\Hd)$~. (We associated
         ${\Bbb C}^n$ to its dual, and $p$ to a vector. Recall that
         $p$ has integer -- hence real -- coefficients).
\subsection{Linear case}

{\lemma  \label{lem:linear}
         Let $\Pi = p^{\perp}$ be a hyperplane in ${\Bbb C}^N$,
         where $p$ has integer coordinates. Let $y \in {\Bbb C}^N$
         have Gaussian integer coordinates. Then either $y \in \Pi$,
         or~:
      $$
         d_2(y,\Pi) \ge {1 \over \bheight{p} \height{y}}
      $$
         }
      \par
         {\bf Proof~:} The orthogonal projection of $y$ in $\Pi$
         is given by~:
      $$
         y - {p p\rtrans \over \norm{p}^2} y
      $$
      \par
         so the projective distance to $\Pi$ is~:
      $$
         d_2(y,\Pi) =
         {\norm{p}  \over \norm{p}^2 \norm{y}} |p\rtrans y|
      $$
      \par
         If $p \not \in \Pi$, then $p \rtrans y \ne 0$~, so
         $|p\rtrans y| \ge 1$ and~:
      $$
         d_2(y,\Pi) \ge {1 \over \norm{p} \norm{y}}
         \ge {1 \over \bheight{p} \height{y}}
      $$
   \medskip
      \par
         Lemma \ref{lem:linear} implies, for $f \not \in \Sigma$, that~:
      $$
         d_2(E(f),E(\Sigma))
         \ge {1 \over \bheight{p} \height{E(f)}}
         \ge {1 \over \bheight{p} \height{f}^{\sum r_i}}
      $$
      \par
         The distance $d_2(f, \Sigma)$ can be bounded once we know
         a bound for the Lipschitz constant of $E$~:
{\lemma \label{lem:lipschitz}
      $$
         d_2(E(f),E(g)) \le \lambda d_2(f,g)
      $$
      \par
         where one can take $\lambda = {\pi \over 2} \sum r_i
         \max \sqrt{m_i}$
         }
      \par
         Lemma \ref{lem:lipschitz} will be proved in the next three
         subsections.
   \medskip
      \par
\subsection{The $r$-uple embedding}

         Let~:
      $$
      \begin{array}{lrcll}
         V_r : &{\Bbb C}^m &\rightarrow &{\Bbb C}^M &,
         \ M = \binomial{m+r-1}{r} \\
         & x & \mapsto & (\dots , x^J , \dots)\rtrans &,
         |J| = r
      \end{array}
      $$
         be the $r$-uple embedding; then~:
{\lemma \label{lem:ruple}
      $$
         {\infnorm{D V_r(x)} \over \norm{V_r(x)}}
         \le
         r {1 \over \norm{x}}
      $$
      \par
         and therefore~:
      $$
         {\norm {D V_r(x)} \over \norm{V_r(x)}}
         \le
         r \sqrt{m} {1 \over \norm{x}}
      $$
         }
      \par
         Indeed, assume without loss of generality that
         $x_1 \ge x_2 \ge \dots \ge x_m$~. Then~:
      $$
         V_r(x) =
         \left(
            {x_1}^r ,
            {x_1}^{r-1} x_2,
            \dots
            {x_1}^{r-1}x_m,
            {x_1}^{r-2}{x_2}^2,
            \dots,
            {x_m}^r
         \right)\rtrans
      $$
      \par
         Therefore,
      \begin{equation}
         \label{eq:l1}
         \norm{V_r(x)} \ge |x_1|^{r-1} \norm{x}
      \end{equation}
   \medskip
      \par
         On the other hand, for all monomials $x^J$,
      $$
         \left|
         {\partial x^J \over \partial x_i}
         \right|
         \le
         J_i |x_1|^{r-1}
      $$
      \par
         Hence,
      \begin{equation}
         \label{eq:l2}
         \infnorm{DV_r(x)}
         =
         \max
         \sum_i
         \left|
         {\partial x^J \over \partial x_i}
         \right|
         \le
         r |x_1|^{r-1}
      \end{equation}
      \par
         Dividing inequality~(\ref{eq:l2}) by inequality~(\ref{eq:l1})
         we prove Lemma~\ref{lem:ruple}.




\subsection{The Segre embedding}

         Let $N = \prod M_i$ and let~:
      $$
      \begin{array}{lrcl}
         S_n :
         &{\Bbb C}^{M_1} \times {\Bbb C}^{M_2} \times \dots
          \times{\Bbb C}^{M_n}
         &\rightarrow
         &{\Bbb C}^N
         \\
         & (y_1, \dots , y_n)
         & \mapsto
         & ( \dots , y_{1,k_1} y_{2,k_2} \dots y_{n,k_n} , \dots )\rtrans
      \end{array}
      $$
      \par
         be the Segre embedding. Then~:
{\lemma \label{lem:segre}
      $$
         { \norm{\partial S_n(y) \over \partial y_j}  \over
         \norm{S(y)} }
         \le
         {1 \over \norm{y_j}}
      $$
      }
      \par
         Indeed,
      $$
         S_n(y)
         =
         \left(
         S_{n-1}\rtrans(y_1, \dots, y_{n-1}) y_{n,1} ,
         \dots ,
         S_{n-1}\rtrans(y_1, \dots, y_{n-1}) y_{n,M_n}
         \right) \rtrans
      $$
      \par
         Hence, $\norm{S_n(y)}^2 = \norm{S_{n-1}(y_1,y_{n-1})}^2
         \norm{y_n}^2$~. Therefore, by induction,
      \begin{equation}
         \label{eq:s1}
         \norm{S_n(y)} = \norm{y_1} \norm{y_2} \dots \norm{y_n}
      \end{equation}
   \medskip
      \par
         The norm of the derivative may be bounded as follows~:
      $$
         {\partial S_n \over \partial y_n}
         =
         \begin{pmatrix}
         S_{n-1}(y_1, \dots , y_{n-1})
         \\
         & S_{n-1}(y_1, \dots , y_{n-1})
         \\
         &&
         \ddots
         \\
         &&& S_{n-1}(y_1, \dots , y_{n-1})
         \end{pmatrix}
      $$
      \par
         Thus,
      \begin{equation}
         \label{eq:s2}
         \norm {\partial S_n \over \partial y_n}
         \le
         \norm { S_{n-1}(y_1, \dots, y_{n-1})}
         =
         \norm{y_1} \norm{y_2} \dots \norm{y_{n-1}}
      \end{equation}
      \par
         Dividing equation~(\ref{eq:s2}) by equation~(\ref{eq:s1}),
         one proves Lemma~\ref{lem:segre} for the case $j=n$. Reordering
         variables, the Lemma is true for any $j$.

\subsection{End of the proof of Theorem \ref{th:1}}


         Let $d_{\arc}$ be the arc-length $2$-distance in Projective
         Space (or in the unit $2$-sphere).
         Lemmas~\ref{lem:ruple} and~\ref{lem:segre} imply that~:
      $$
         d_{\arc}(E(f),E(g))
         \le
         \sum r_i \sqrt{m_i}
         d_{\arc}(f,g)
         \le
         \max \sqrt{m_i} \sum_{r_i} d_{\arc}(f,g)
      $$
         Using inequality $d_2(f,g) \le d_{\arc}(f,g) \le
         {\pi \over 2}d_2(f,g)$, we get~:
      $$
         d_2(E(f),E(g))
         \le
         {\pi \over 2}\max m_i \sum_{r_i} d_2(f,g)
      $$
      \par
         Proving Lemma~\ref{lem:lipschitz}~. Theorem~\ref{th:1} now
         follows directly from Lemma~\ref{lem:linear}.




\section{Proof of Lemmas} \label{sec:5}


\subsection{Proof of Lemma~\ref{lem:1}}

         Recall that $r_i = \prod d_j
         \left( 1 + {\sum d_j - n \over d_i} \right)$~. Therefore~:
      $$
         \sum r_i
         \le
         \prod d_j
         \left(
         n + \sum d_j \sum {1 \over d_j} - n \sum{1 \over d_j}
         \right)
      $$
      \par
         If $\sum {1 \over d_j} \ge 1$, then
         $\sum r_i \le \prod d_j \sum d_j \sum{1 \over d_j}
         \le n \prod d_j \sum d_j$
      \par
         On the other hand, if $\sum {1 \over d_j} < 1$~,
         then $\sum r_i \le \prod d_j (n + \sum d_j)
         < n \prod d_j \sum d_j$~.
      \par
         This proves lemma~\ref{lem:1}


\subsection{Proof of Lemma~\ref{lem:2}}

      \par
         By construction,
      $$
         { \norm{h} \over \sqrt{\max_{i,|J|=d_i} \binomial{d_i}{J} }}
         \le \knorm{h} \le \norm{h}
      $$
      \par
         Therefore, as we switch to projective space,
      $$
         d_k(f,g) \le \sqrt{\max_{i,|J|=d_i} \binomial{d_i}{J} } d_2(f,g)
      $$
      \par
         Inserting Lemma~\ref{lem:3}, we get~:
      $$
         d_k(f,g) \le
         \sqrt{n^{\max d_i} \left( {e \over \sqrt{2 \pi}} \right)^{n-1}
         e^{1 \over 12} \sqrt{n} \binomial{d_i}{J} } d_2(f,g)
      $$
      \par
         As in Lemma~\ref{lem:2}

\subsection{Proof of Lemma~\ref{lem:3}}

      $$
         \max_{|J|=d} \binomial{d}{J}
         =
         \max_{|J|=d} { \Gamma(d+1) \over \prod \Gamma(J_i + 1) }
         \le
         { \Gamma(d+1) \over \Gamma({d \over n} + 1)^n }
      $$
         The following bound is a consequence of Stirling's formula
         (Ahlfors, \cite{AHLFORS}, chapter 5, section 2.5, exercise 2,
         page 206)~:
      $$
         \sqrt{2 \pi}
         z^{z - {1 \over 2}}
         e^{-z}
         \le
         \Gamma(z)
         \le
         \sqrt{2 \pi}
         z^{z - {1 \over 2}}
         e^{-z}
         e^{1 \over 12z}
      $$
      \par
         Using this bound, we obtain~:
      \begin{align*}
         \max_{|J|=d} \binomial{d}{J}
         &\le
         \sqrt{2 \pi} ^{1 - n}
         { (d+1)^{d + {1 \over 2}} \over
           \left( ( {d \over n} + 1 )^{d \over n}+{1 \over 2}
           \right)^n }
         { e^{-d+{1 \over 2}} \over
           \left( e^{-{d \over n} - 1} \right) ^n }
         e ^{1 \over 12(d+1)}
         \\
         &\le
         \sqrt{2 \pi} ^{1 - n}
         \left(
           { d+1 \over {d \over n} + 1 }
           \right)^n
         \left(
           {d \over n} + 1
           \right)^{-{n-1 \over 2}}
         e^{n-1}
         e^{1 \over 12(d+1)}
         \\
         &\le
         n^d
         \left(
         { e \over \sqrt{2 \pi} \sqrt{ {d \over n} + 1 } }
         \right) ^{n-1}
         \sqrt{n}
         e^{1 \over 12}
         \\
         &\le
         n^d
         \left(
         { e \over \sqrt{2 \pi} }
         \right) ^{n-1}
         \sqrt{n}
         e^{1 \over 12}
      \end{align*}
      \par
         As in Lemma~\ref{lem:3}

\newpage
\par

\begin {thebibliography}{12}


\bibitem{AHLFORS}
Lars V. Ahlfors
\newblock{\em Complex Analysis},
\newblock Third edition. McGraw-Hill, Auckland, 1979.

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

\bibitem{GJ}
M. R. Garey and D. Johnson
\newblock {\em Computers and Intractability, a guide to the
    theory of $NP$-completeness},
\newblock Freeman, San Francisco, 1979.

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


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

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

\bibitem{SALMON}
George Salmon.
\newblock{\em Lessons introductory to the modern higher algebra}
\newblock 2$^{\text{nd}}$ edition~: Dublin, 1885. 5$^{\text{th}}$
          edition~: reprint by Chelsea Pub. Co., Bronx, unknown date.

\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{BEZV}
Michael Shub and Steve Smale,
\newblock Complexity of Bezout's Theorem V : Polynomial time ;
\newblock Preprint, Barcelona, 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 {WAERDEN}
B. L. Van der Waerden,
\newblock {\em Modern Algebra, Vol 2.}
\newblock {F. Ungar publishing Co, New York, 1950} 


\end {thebibliography}




\end{document}



