%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%            An Effective Version of Kronecker's Theorem
%             on Simultaneous Diophantine Approximation
%
%                    by Gregorio Malajovich
%                       gregorio@lyric.labma.ufrj.br
%
%
%                    Hong Kong, July 18, 1996.
%
%
%
%
%  ABSTRACT: 
%   Kronecker's theorem states that if $1$, $\theta_1$, \dots ,
%   $\theta_n$ are real algebraic numbers, linearly independent over
%   $\bbbq$, and if $\alpha \in \bbbr^n$, then for any $\epsilon > 0$
%   there are $q \in \bbbz$ and $p \in \bbbz^n$ such that
%   $|q \theta_i - \alpha_i - p_i | < \epsilon$~.
%
%   Here, a bound on $q$ is given in terms of the dimension $n$,
%   of the precision $\epsilon$, of the degree of the $\theta_i$'s
%   and of their height.
%
%   A possible connection to the square-root sum problem is discussed.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\documentclass{article}
\usepackage{amsmath, amssymb, amsthm, epsfig}

%
\newcounter{question}

\newtheorem{main}{Main Theorem}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}        {Lemma}
\newtheorem{proposition}  {Proposition}
\newtheorem{corollary}    {Corollary}
\newtheorem{conjecture}   {Conjecture}
\theoremstyle{definition}
\newtheorem{definition}{Definition}
\newtheorem{example}{Example}
\newtheorem{remark}{Remark}
\newtheorem{problem}{Problem}
\newtheorem{induction}{Induction Hypothesis}

\newcommand{\bbbq}{\mathbb Q}
\newcommand{\bbbr}{\mathbb R}
\newcommand{\bbbz}{\mathbb Z}
\newcommand{\bbbn}{\mathbb N}
\newcommand{\np}{\ensuremath{\mathcal {NP}}}
\newcommand{\htheta}{{\hat \theta}}
\newcommand{\dq}{{\mbox{\small deg}_{\bbbq}}}

\begin{document}

\title{An Effective Version of Kronecker's Theorem\\
       on Simultaneous Diophantine Approximation
\thanks{Preprint, City University of Hong Kong, \today.}
       }

\author{Gregorio Malajovich
        \thanks{Partially supported by CNPq (BRASIL)} \\
\small
           Departamento de Matem\'atica Aplicada\\
           Instituto de Matem\'atica da  
           Universidade Federal do Rio de Janeiro\\
           Caixa Postal 68530 -- CEP 21945 -- 
           Rio de Janeiro -- RJ -- BRASIL\\
           gregorio@lyric.labma.ufrj.br}


\maketitle

\begin{abstract}
    Kronecker's theorem states that if $1$, $\theta_1$, \dots , 
    $\theta_n$ are real algebraic numbers, linearly independent over 
    $\bbbq$, and if $\alpha \in \bbbr^n$, then for any $\epsilon > 0$
    there are $q \in \bbbz$ and $p \in \bbbz^n$ such that
    $|q \theta_i - \alpha_i - p_i | < \epsilon$~.
\par
    Here, a bound on $q$ is given in terms of the dimension $n$,
    of the precision $\epsilon$, of the degree of the $\theta_i$'s 
    and of their height.
\par
    A possible connection to the square-root sum problem is discussed. 
\end{abstract}
%
\section{Introduction } \label{sec1}
%
    In most of the literature, Kronecker's theorem on simultaneous
    diophantine approximation is stated in an ineffective way.
    However, there are some effective versions, that require 
    additional hypotheses on the $\theta_i$'s. See for instance
    Rieger~\cite{RIEGER}, Theorem 1 or Larcher and Niederreiter
    ~\cite{LN} section 3. Other available statements (like in
    Baker Br\"udern and Harman~\cite{BBH}) do not seem to imply
    a bound on $q$. 

    Here, an elementary constructive proof of Kronecker's theorem 
    will be given. Using estimates on the height of algebraic numbers,
    it will be possible to obtain effective bounds on $q$. 
    For more on heights,
    see Section~\ref{sec2}. The main result of this paper is: 
\begin{main}*
    There is a function $K(d,n) \in d^{O(n^2)}$ such that if
    $\theta_1$, \dots, $\theta_n$ are real algebraic numbers and
\begin{enumerate}
    \item \label{condma}
          The numbers 
          $1$, $\theta_1$, \dots , $\theta_n$ are linearly independent
          over $\bbbq$
    \item \label{condmb}
          Each $\theta_i$ is algebraic of degree $\leq d$ over $\bbbq$
    \item \label{condmc}
          The height $H(\theta_i)$ of each $\theta_i$ is smaller than
          some $H \in \bbbn$
\end{enumerate}
    then, for any $\alpha \in \bbbr^n$, for any $\epsilon > 0$, there are
    $q \in \bbbz$, $p \in \bbbz^n$ such that
\begin{equation} \label{eqm1}
    | q \theta_i - \alpha_i - p_i | < \epsilon\ , \ i=1,\dots,n
\end{equation}
\begin{equation} \label{eqm2}
    |q| \le \left( \epsilon^{-1} H \right)^{K(d,n)}
\end{equation}
\end{main}
\medskip
\par
    If $\alpha = 0$, this follows from Dirichlet's theorem (in fact,
    the bound will be $|q| \le \epsilon^{-n}$). Removing conclusion 
    (\ref{eqm2}), this is Kronecker's theorem (See Section \ref{sec2}).
\par
    An immediate consequence of the main theorem is the
\begin{corollary} \label{cor1}
    Under conditions \ref{condma}, \ref{condmb} and \ref{condmc} of
    the main theorem, for any $\epsilon > 0$, there are $q \in \bbbz$ 
    and $p \in \bbbz ^n$ such that:
\[ 
    0 < q \theta_i - p < \epsilon
\]
\[
    |q| \le \left( 2 \epsilon^{-1} H \right) ^{K(d,n)} 
\]
\end{corollary}
\medskip
\par
    Indeed, set $\alpha_i = \epsilon / 2$ and apply the main theorem
    to obtain an $\epsilon/2$ approximation of $\alpha$.
\medskip
\par
    The investigation of effective bounds for Kronecker's theorem 
    and for Corollary~\ref{cor1} was motivated by square-root sum decision
    problem (SQRTS), arising from computational geometry: given $n, m, 
    a_1 \dots, a_m, b_1, \dots , b_n \in \bbbn$, decide if
    $\sum \sqrt{a_i} > \sum \sqrt{b_i}$~. Another formulation: given two
    paths joining lattice points in the plane, decide which is
    shorter. This problem is not known to be in $\np$. See Section~
    \ref{sec5} for further comments.
\medskip
\par
    The idea of using `gap theorems' to investigate the square-root
    sum problem was suggested by Steve Smale. The following people
    make important suggestions and comments: Manuel Blum, Wellington
    de Melo, Mike Shub, Steve Smale, Bob Williams. 
\par
    This paper was written as I was visiting the City University of
    Hong Kong, which I thank for its generous support.

\section{Related Results, and a Conjecture} \label{sec2}
    The following are the classical results related to the main
    Theorem of this paper:
\begin{theorem}[(Dirichlet)] \label{dirichlet}
    Let $\theta \in \bbbr^n$ and let $\epsilon > 0$.
    Then there are $q \in \bbbn$, $p \in \bbbz^n$ such that
    $|q \theta_i - p_i| < \epsilon$ for all $i$. Furthermore,
    $1 \le q < \epsilon^{-n}$. 
\end{theorem}
\medskip
\par
    See Schmidt~\cite{Schmidt785} Theorem 1A page 27, or Baker~\cite{Baker}, 
    for a proof.
\medskip
\begin{theorem}[(Kronecker)] \label{kronecker}
    Let $1$, $\theta_1$, \dots, $\theta_n$ be real algebraic
    numbers, linearly independent over $\bbbq$. Then for any
    $\alpha \in \bbbr^n$, there are $q \in \bbbn$ and $p \in
    \bbbz^n$ such that $|q \theta_i - \alpha_i - p_i| < \epsilon$,
    for all $i$.
\end{theorem}
\medskip
\par
    In fact, the statement is more general (see Siegel \cite{Siegel}
    page 63), but no bound for $q$ seems to be known. The proof is 
    non-constructive.   
\medskip
\par
    The bound for $K(d,n)$ in the main theorem seems  
    to be extremely pessimistic. Instead, I would conjecture
    that

\begin{conjecture} \label{conj1}
    There is $K'(d,n)=K'(n) \in n^{O(1)}$ such that the main
    theorem is valid, for $\theta_i = \pm \sqrt{a_i}$, 
    $a_i \in \bbbn$, and $K$ replaced by $K'$.
\end{conjecture} 
\medskip
\par
    Remark that this conjecture is false if one drops the assumption
    that the $\theta_i$'s are algebraic, or if one does not bound
    the height of $\theta$. In that case, even if $n=1$, 
    one could have an arbitrarily 
    small $\theta$, so an arbitrarily large $q$ would be necessary to
    approximate $\alpha = 1/2$.
\medskip
\par
    Estimates on heights of algebraic number will be needed in the proof 
    of the main theorem. The height is a function $H: \bar \bbbq \rightarrow
    \bbbn$. The properties of heights that we will use are listed below.
    Here, $a$, $b \in \bar \bbbq_*$, and $p \in \bbbz_*$~.
\begin{enumerate}
    \item $H(a)^{- \dq(a)} \le |a| \le H(a)^{\dq(a)}$
    \item $H(0) = H(1) = 1$
    \item $H(p) = |p|$
    \item $H(ab) \le H(a)H(b)$
    \item $H(a^{-1}) = H(-a) = H(a)$
    \item $H(a+b) \le 2 H(a)H(b)$  
\end{enumerate}
    \par
    For the precise definition, and proof of the properties above,
    see 
Blum, Cucker, Shub and Smale~\cite{BCSS}, Silverman~\cite{Silverman} or
Schmidt~\cite{Schmidt1467}.
 
\section{Translations of the Torus, Covering Number and Useful Lemmas}
       \label{sec3}

    The $n$-dimensional torus $T^n$ is the quotient $\bbbr^n / \bbbz^n$~.
    A point $x \in \bbbr^n$ will represent the equivalence class
    $x + \bbbz^n$ in $T^n$~. 
\par
    Let $\theta \in \bbbr^n$~. The vector $\theta$ induces a mapping
    $f_{\theta}: x \mapsto x + \theta \mod \bbbz^n$ in the torus $T^n$~.
    This mapping can be interpreted as a dynamical system in $T^n$. 
\par
    For more applications of dynamical systems or ergodic theory
    and for more about mappings of the torus,
    see Furstenberg
    ~\cite{Furstenberg},
    or Baladi, Rockmore, Tongring and Tresser~\cite{BRTT}.
\medskip
\par
    Dirichlet's theorem (Theorem \ref{dirichlet}) says that, whatever
    $\theta$ is, some iterate of the origin $0$ will come back to
    an $\epsilon$-neighborhood of it, in time bounded by $\epsilon^{-n}$.
    It may also happen that $\theta$ is so small, that the first iterate
    will still be in an $\epsilon$ neighborhood of the origin.
\par
    In fact, any point of the torus will return to any neighborhood of itself.
    Points with that property are said to be recurrent (under $F_{\theta}$),
    and in this case all points are recurrent. Also, we have an effective bound
    for the return time.
\par
    Now, if an arbitrary point $\alpha \in T^n$ is given, will some iterate
    of $0$ come within an $\epsilon$-neighborhood of $\alpha$ ? This is
    false in general (e.g. $\theta = \left(\sqrt{2}, 1 - \sqrt{2}\right)$~.
    But this is true under the condition of Kronecker's theorem 
    (Theorem \ref{kronecker}).
\par
    In that case, the orbit of $0$ is dense, and the dynamical system
    $f_{\theta}$ is {\em ergodic}. This means that~:
\begin{enumerate}
\item There is a probability measure $\mu$ invariant by $f_{\theta}^{-1}$
\item Any $f_{\theta}$-invariant set has measure $1$ or $0$.
\end{enumerate} 
\medskip
\par
    Ergodic systems behave at `random', in the following sense: the
    average of any measurable function on almost any orbit of $f_{\theta}$
    converges to the average of that function in $T^{n}$ (This is the
    ergodic theorem). However, little is known about the rate of 
    convergence.
\par
    If Conjecture~\ref{conj1} is false, then even for simple examples 
    like $\theta_i = \sqrt{a_i}$ the rate of convergence may be 
    extremely slow. 
\medskip
\par
    Let denote by $B(\epsilon,x)$ the ball of radius $\epsilon$
    around $x \in T^n$, i.e. the set:
\[
    B(\epsilon,x) = \left\{ y \in T^n \mbox{\ s.t.\ } 
                    |x_i - y_i - p_i| < \epsilon
                    \mbox{ for all $i$ and for some $p_i \in \bbbz$}
                    \right\}
\]
\par
   The orbit $\{ q \theta \mod \bbbz^n \}$ of $0$ generates a covering
   $\left\{ B(\epsilon, q \theta) \right\}_{q \in \bbbn}$ of the torus
   $T^n$~. Since $T^n$ is compact, there is a finite subcovering
   that can be chosen in the form:
\begin{equation} \label{eqcover}
\left\{ B(\epsilon, q \theta) \right\}_{q=1,2,\dots,N}     
\end{equation}
\par
    The smallest $N$ such that (\ref{eqcover}) defines a covering of
    the torus will be called the covering number of $\theta$ and
    $\epsilon$, and denoted $N(\epsilon, \theta)$. The conclusions 
    of the main theorem (equations (\ref{eqm1}) and (\ref{eqm2}))
    may now be restated as:
\par
\[
    N(\epsilon,\theta) \le \left( (\epsilon^{-1} H \right)^{K(d,n)}
\]
\medskip
\par
    Some useful properties of the covering number follow:
\begin{lemma} \label{lemdiscrete}\  \par
    \begin{enumerate}
    \item For all $q \in \bbbz$, $N(\epsilon, \theta) \le qN(\epsilon, q\theta)$
    \item For all $p \in \bbbz^n$, $N(\epsilon, \theta + p) =
          N(\epsilon, \theta)$
    \end{enumerate}   
\end{lemma}
\begin{proof}[of Lemma \ref{lemdiscrete}]
    Item 2 is trivial. In order to prove item 1, consider the orbit
    $\left\{r \theta \right \}_{1 \le r \le q N(\epsilon,q \theta)}$
    of $0$ by $f_\theta$~.
    It contains the orbit
    $\left\{s (q \theta) \right \}_{1 \le s \le N(\epsilon,q \theta)}$
    of $0$ under $f_{q \theta}$. Since this last orbit is within 
    distance $\epsilon$ of any prescribed point, the former one also is.
\qed
\end{proof}
\medskip
\par
    Also, on may embed the translation $f_{\theta}$ into a flow
    $\varphi^t_\theta$ of $T^n$, defined by:
\[
\begin{array}{lcrcl}
    \varphi_\theta & : & \bbbr \times T^n & \rightarrow & T^n \\
    & & t,x & \mapsto & \varphi^t_\theta (x) = x + t \theta \mod \bbbz^n
\end{array}
\]
\medskip
\par
    We may define the covering number for $\varphi_\theta$ in an analogous
    way as the covering number for a discrete transformation. We define
    $\nu (\epsilon, \theta)$ as the infimum of all $s \in \bbbr^+$ such
    that:
\[
\bigcup_{t \in [0,s]} B(\epsilon, \varphi^t_\theta (0)) \supseteq T^n
\]
\medskip
\par
    We will use the following fact in the sequel:
\begin{lemma} \label{lemcontinuous}
    $N(\epsilon, \theta) \le \nu(\epsilon - \max{\theta_i}, \theta)$
\end{lemma}
\begin{proof}[of Lemma \ref{lemcontinuous}]
    Let $\alpha \in T^n$. There is $t \le \nu(\epsilon - \max |\theta_i|,
    \theta)$ such that $t \theta \in {\bar B}(\epsilon - \max |\theta_i, 
    \alpha)$.
    Let $s$ be the largest integer $\le t$. Then 
    $\varphi^s_\theta(0) - \varphi^t_\theta(0) = (t-s) \theta \mod \bbbz^n$,
    and $\max (t-s) |\theta_i| < \max |\theta_i|$. Therefore, by triangular
    inequality, $\varphi^s_\theta(0) \in B(\epsilon, \alpha)$~.
\qed
\end{proof}
\section{Proof of the Main Theorem} \label{sec4}
    Assume, as in the hypothesis of the main theorem, that
    $1$, $\theta_1$, \dots, $\theta_n$ are real algebraic numbers,
    linearly independent over $\bbbq$. Let $H = \max H(\theta_i)$,
    and let $d$ bound the degree of each $\theta_i$ over $\bbbq$.
    Let $D$ be the degree of $\bbbq[\theta_1, \dots, \theta_n]$
    over $\bbbq$. Then $D \le d^n$.
\par
    Given $\epsilon$, we have to bound the covering number 
    $N(\epsilon, \theta)$~. We will proceed by induction on the
    dimension $n$. We will need the
\begin{lemma} \label{lemind}
    Under the conditions above, there are $\htheta_1$, \dots,
    $\htheta_{n-1} \in \bbbq[\theta_1, \dots, \theta_n]$, such that:
    \begin{enumerate}
    \item $1$, $\htheta_1$, \dots , $\htheta_{n-1}$ are linearly 
          independent over $\bbbq$.
    \item $H(\htheta_i) \le \left( \epsilon^{-1} H(\theta) \right)
          ^{4 \max(n+1,D)}$
    \item $N(\epsilon, \theta) \le
           \left( \epsilon^{-1} H(\theta) \right)
          ^{4 D \max(n+1,D)}
          N(\frac{\epsilon}{2}, \htheta)$
    \end{enumerate} 
\end{lemma}

\begin{proof}[of Lemma \ref{lemind}]
    According to Dirichlet's theorem (Theorem \ref{dirichlet}), there are
    $q \in \bbbn$, $p \in \bbbz^n$ such that:
\[
|q \theta_i - p_i | < \frac{\epsilon}{2} \ , \mbox{for $i=1, \dots, n$}
\]
    with $1 \le |q| < \left( \frac{2}{\epsilon} \right) ^n$. In other words,
    the $q^{\mbox{th}}$ iteration of $\theta$ defines a `small' translation
    of the torus.
\par
    We may also bound the `rotation numbers' $p_i$ of $q \theta$ as
    follows:
\[
    |p_i| \le |q|(|\theta_i|+1) \le 2 |q| H(\theta_i) ^{\dq \theta_i}
\]
\par
    We also obtain the following lower bound, to be used later:
\begin{equation}\label{eq3}
    \left| \theta_i - \frac{p_i}{q} \right|
    \ge
    \frac{1}{H \left( \theta_i - \frac{p_i}{q} \right) ^{\dq \theta_i}}
    \ge
    \frac{1}{
       \left(
       4 \left( \frac{2}{\epsilon}\right)^{2n}
       H(\theta_i)^{1+\dq \theta_i}
       \right) ^{ \dq \theta_i }
       }
\end{equation}
\begin{remark} The bound above can be mad much sharper if one knows
   how to bound the constant $c$ appearing in Liouville's theorem
   $|q \theta_i - p_i | > \frac{c}{q^{\dq \theta_i}}$~. Unfortunately,
   we may only assume here a bound on $H(\theta)$.
\end{remark}
\medskip
\par
   The covering number of $\theta$ may be bounded as follows:
\begin{eqnarray*}
   N(\epsilon, \theta) &\le& q N(\epsilon, q \theta) \\
                       &\le& q N(\epsilon, q \theta - p) \\
                       &\le& q \nu(\frac{\epsilon}{2}, q \theta - p)
\end{eqnarray*}
   where the first two inequalities follow from Lemma~\ref{lemdiscrete},
   and the last one from Lemma~\ref{lemcontinuous}, using the fact
   that $|q \theta_i - p_i | < \epsilon / 2$~.
\medskip
\par
   At this point, we bounded the covering number of the translation
   $f_\theta$ in terms of the covering number of the flow $\varphi^t_\theta$
   in the torus. Since $\theta_n$ is not a rational, this flow is
   transversal to the plane $x_n = \alpha_n$, where $\alpha_n$ is a 
   constant, as in the main theorem. 
\par
   We should look now at the first return map, also known
   as Poincar\'e transform, of the flow $\varphi^t_\theta$ in the
   plane $x_n = \alpha_n$. The first return map associates, to any
   point $X=(x_1, \dots, x_{n-1}, \alpha_n)$ of the plane $x_n=\alpha_n$,
   the next point in the orbit of $X$ that belongs to $x_n = \alpha_n$.
   This point is given explicitly by:
\[
    \left(
   \begin{array}{c} x_1 \\ \vdots \\ x_{n-1} \\ \alpha_n \end{array} 
   \right)
   +
   \left(
   \begin{array}{c} \frac{q \theta_1 - p_1}{q \theta_n - p_n} \\ 
   \vdots \\ \frac{q \theta_{n-1} - p_{n-1}}{q \theta_n - p_n}
    \\ \alpha_n \end{array} 
   \right)
\]
\medskip
\par
    Therefore, we set $\htheta_1 = \frac{q \theta_1 - p_1}{q \theta_n - p_n}$,
    \dots, $\htheta_{n-1} = \frac{q \theta_{n-1} - p_{n-1}}{q \theta_n - p_n}$.
\medskip
\par
    In order to arrive to a distance $\le \epsilon / 2$ of a point
    $\alpha = (\alpha_1, \dots, \alpha_n) \in T^n$, starting from
    the origin, one should follow the flow $\varphi^t_\theta$ until
    arrival to the plane $\alpha_n = 0$. Then, one performs as many
    iterations of the first return map as necessary. This 
    number is finite (since $1$, $\htheta_1$, \dots, $\htheta_{n-1}$)
    are linearly independent over $\bbbq$) and bounded above by
    $N(\epsilon / 2, \htheta)$.
\par
    Each iteration of the first return map takes time $\frac{1}
    {|q \theta_n - p_n|}$ in the flow. Also, the plane $x_n = \alpha_n$ 
    may be reached for the first time in time $< \frac{1}
    {|q \theta_n - p_n|}$. 
\par
    Hence,
\[
    \nu( \frac{\epsilon}{2}, q \theta - p)
    \le
    \frac{1} {|q \theta_n - p_n|}
    \left( 1 + N(\frac{\epsilon}{2}, \htheta) \right)
\]
\par
    Therefore,
\[
    N( \frac{\epsilon}{2},\theta)
    \le
    \frac{1} {|\theta_n - p_n/q_n|}
    \left( 1 + N(\frac{\epsilon}{2}, \htheta) \right)
\]
    \par
    Using (\ref{eq3}), one obtains:
\[ 
    N( \frac{\epsilon}{2},\theta)
    \le
    2^{(2n+2) \dq \theta_n}
    \epsilon^{-2n \dq \theta_n}
    H(\theta_n)^{(1+ \dq \theta_n) \dq \theta_n}
    \left( 1 + N(\frac{\epsilon}{2}, \htheta) \right)
\]
\par
    Hence, since $H(\theta_n), \epsilon^{-1} \ge 2$, we can replace the
    right-hand side by a coarser estimate:
\begin{equation} \label{eq6}
    N( \frac{\epsilon}{2},\theta)
    \le
    \left(
    \epsilon^{-1} H(\theta) 
    \right) ^{D \max(4(n+1),D+1) }
    N(\frac{\epsilon}{2}, \htheta)
\end{equation} 
\medskip
\par
   Also,
\[
   H(\htheta_i)
    \le
    H(q \theta_i - p_i) H(q \theta_n - p_n)
    \le 
    4 |q|^2 H(\theta_i) H(\theta_n) |p_i| |p_n|
\]
\par
    This can be estimated by:
\begin{equation} \label{eq7} 
    H(\htheta_i)
    \le
    2^{2n+4}
    \epsilon^{-2n}
    H(\theta_i)^{1+\dq \theta_i}
    H(\theta_n)^{1+\dq \theta_n}
    \le
\left(
    \epsilon^{-1} H(\theta) 
    \right) ^{\max(4(n+1),D+1) }
\end{equation}
\par
  We may bound (\ref{eq6}) and (\ref{eq7}) by
$(\epsilon^{-1}H)^{4 D \max(n+1,D)}$ and 
$(\epsilon^{-1}H)^{4 \max(n+1,D)}$, respectively,
as in the statement of the lemma.
\qed
\end{proof}
\medskip
\par
    We will prove now a more general version of the main
    theorem, where $K(d,n)$ is replaced by a power of
    $D = \mbox{deg}_{\bbbq} \bbbq[\theta_1, \dots, \theta_n]$. 
\begin{induction}*
    Let $\theta_1$, \dots, $\theta_n$ be algebraic numbers, so
    that: 
\begin{enumerate}
    \item 
          $1$, $\theta_1$, \dots , $\theta_n$ are linearly independent
          over $\bbbq$
    \item 
          $\mbox{deg}_{\bbbq} \bbbq[\theta_1, \dots, \theta_n] \le D$
    \item 
          The height $H(\theta_i)$ of each $\theta_i$ is smaller than
          $H \in \bbbn$
\end{enumerate}
    Then $N(\epsilon, \theta) \le 
    \left(\epsilon^{-1} H \right) ^{\left(4 \max(D,n+1) \right)^{2n} }
    $ 
\end{induction}
\medskip
\par
    For $n=1$, $N(\epsilon, \theta) \le \frac{1}{|\theta - p/q|}$
    as above. Furthermore, we may bound the right-hand side by
    $ 4 (\epsilon/2)^{-2D} H^{D(1+D)} \le (H/\epsilon)^{4D^2}$.
\medskip
\par
    Assume the induction hypothesis true at rank $n-1$. According to
    Lemma~\ref{lemind}, 
\[
    N(\epsilon, \theta) \le
    \left(\epsilon^{-1} H \right) ^{4 D \max(D,n+1)}
    N(\epsilon/2, \htheta)
\]
with
\[
    H( \htheta) \le
    \left(\epsilon^{-1} H \right) ^{4 \max(D,n+1)}
\]
\par
   Hence, by induction,
\begin{eqnarray}
    N(\epsilon, \theta) &\le
    \left(\epsilon^{-1} H \right) ^{4 D \max(D,n+1)}
\left(
    \left(\epsilon^{-1} H \right) ^{4 \max(D,n+1)}
    \frac{2}{\epsilon}
\right)
   ^{(4 \max(n+1,D)^{2n-2}}
   \\
  &\le
   \left(\epsilon^{-1} H \right)
    ^{(4 \max(n+1,D)^{2n}}
\end{eqnarray}
\medskip
\par
    Recall that, under the hypotheses of the Main Theorem,
    $D \le d^n$. Also, $n+1 \le d^n$ for all $n \ge 1$,
    since we require $d \ge 2$. Hence $4 \max(n+1,D) \le 4d^n$,
    and:
\[
  \left( 4 d^n \right) ^{2n} = 4^{2n} d^{2n^2}
  \le d^{2n^2+4n}
  \le d^{3n^2}
\]
\par
   Therefore, we set $K(d,n) = d^{3n^2} \in d^{O(n^2)}$, and the
   main theorem is proved.

\section{Connections with the square-root sum problem}
\label{sec5}

   The square-root sum decision problem is defined as:
\begin{problem}(SQRTS) 
    Given $m,n,a_1, \dots , a_m, b_1, \dots, b_m \in \bbbn$,
    decide if $\sum \sqrt{a_i} > \sum \sqrt{b_i}$
\end{problem}
\medskip
\par
    A different formulation of this problem (decide $\sum \sqrt{a_i} > c$
    ,$c \in \bbbn$) appeared in Garey, Graham and Johnson
    ~\cite{GGJ} in connection with the traveling salesman 
    problem in the plane:
\par
    Given a set of lattice (integer) points in the plane,
    decide if there is a path of length $< c$ covering all
    the points. This problem was proven to be $\np$-complete
    for the $\|.\|_1$ metric.
\par
    However, the traveling salesman problem in the plane with the
    usual euclidian metric was only shown to be $\np$-hard, 
    due to the difficulty to check if a given path has length
    $<c$.
\medskip
\par
    This last problem was studied by Tiwari~\cite{Tiwari}, in a
    more particular setting (the $a_i$'s were represented in
    the form $c \sqrt{p_1 \dots p_k}$, $c \in \bbbz$, $p_i$ 
    primes. He concluded that this problem could be solved in
    polynomial time by a RAM machine. (i.e., counting only the
    number of algebraic operations). It is not known if there
    is a polynomial time algorithm for this problem, in the
    bit-complexity model.
\medskip
\par
    As Tiwari's problem, SQRTS can be solved in polynomial time over the
    reals or over $\bbbz$ (RAM machines, without counting bit
    operations). The strategy is to approximate each $\sqrt{a_i}$
    and $\sqrt{b_i}$ up to the necessary precision $\delta$, 
    using $\log -\log \delta$ Newton iterations. Moreover,
    it can be proved that $\sum \sqrt{a_i}-\sum \sqrt{b_i}$ is
    either $0$, or:
\[
    | \sum \sqrt{a_i}-\sum \sqrt{b_i} | > \max(a_i, b_i)^{-2 ^{O(m+n)}} 
\]
\par
   Indeed, write $x = \sum \sqrt{a_i}-\sum \sqrt{b_i}$ as a solution of:
\[
\begin{array}{lcl}
    \theta_1 ^2 - a_1 & = & 0 \\
    & \vdots\\ 
    \theta_m ^2 - a_m & = & 0 \\
    \theta_{m+1} ^2 + b_1 & = & 0 \\
    & \vdots\\
    \theta_{m+n} ^2 + b_n & = & 0 \\
    \theta_1 + \dots + \theta_{m+n} - x & = & 0
\end{array}
\]
    and then apply Canny's gap theorem \cite{Canny} or 
    Pardo and Krick's Corollary 7 in~ \cite{KrickPardo}.
\par
    Therefore, $O(m+n)$ Newton iteration will approximate
    $a_i$ and $b_i$ up to precision
    $\delta \le \frac{1}{2(m+n)} \max(a_i, b_i)^{-2 ^{O(m+n)}}$.
    Thus, it is possible to compute $x$ in time $O(m+n)$ with precision
    enough to decide SQRTS.
\par
    When bit-complexity (Turing complexity, or complexity over $F_2$)
    is concerned, the gap bound above is not satisfactory any more.
    Indeed, $\log -\log \delta$ iterations can produce numbers with
    $- \log \delta$ bits, making the above algorithm exponential time.
\medskip
\par
\begin{proposition}\label{prop1} Conjecture \ref{conj1} implies that
    SQRTS belongs to $\cal P$.
\end{proposition}
\begin{proof}[of Proposition \ref{prop1}]
   Set $\theta_1 = \sqrt{a_1}$, \dots, $\theta_m = \sqrt{a_m}$,
   $\theta_{m+1} = - \sqrt{b_1}$, $\theta_{m+n} = - \sqrt{b_n}$.
   Now, Corollary \ref{cor1} implies that for all $\epsilon > 0$,
   there are $q \in \bbbn$, $p \in \bbbz^{m+n}$ such that 
   $0 < \theta_i - p_i / q < \epsilon / q$, with $1 \le q < 
   (2 \epsilon^{-1} H)^{(m+n)^{O(1)}}$~.
\par
   Set $\epsilon = \frac{1}{2(m+n)}$. Then $q < ((4(m+n)H)^{(m+n)^{O(1)}}$. 
   We may now distinguish two cases.
\par
   {\bf Case 1:} Assume that $\sum \frac{p_i}{q} \ne 0$. Then
   $|\sum \frac{p_i}{q}| \ge \frac{1}{q}$, and:
\[
   | \sum \theta_i| \ge |\sum \frac{p_i}{q}| - |\sum \theta_i - \frac{p_i}{q}| 
   \ge \frac{1}{q} - \frac{1}{2q} \ge \frac{1}{2q} \in H^{-(m+n)^{O(1)}}
\]
\medskip
\par
   {\bf Case 2:} $\sum \frac{p_i}{q} = 0$, so $\sum \theta_i = 
   \sum \theta_i - \frac{p_i}{q}$. However, according to Liouville's
   theorem, $|\theta_i - \frac{p_i}{q}| > \frac{c}{q^2}$, where
   the constant $c$ may be chosen equal to 
   $\frac{1}{2(\max(a_i,b_i) + 1)}$. Therefore,
\[
    \sum \theta_i > \frac{nc}{q^2} \in H^{-(m+n)^{O(1)}}
\] 
\medskip
\par
   Therefore, we conclude that $O( (m+n)^{O(1)} \log H)$ steps of
   Newton iteration suffice to decide SQRTS.
\qed
\end{proof}
\begin{thebibliography}{1}

\bibitem{Baker}
   Alan Baker:
   {\em A Concise Introduction to Number Theory}.
   Cambridge University Press, Cambridge 1984.

\bibitem{BBH}
   R.C.Baker, J.Br\"udern and G.Harman:
   Simultaneous Diophantine Approximation with Square-Free Numbers.
   {\em Acta Arithmetica} {\bf 63} num. 1, 51-60, 1993.

\bibitem{BRTT}
   V. Baladi, D. Rockmore, N. Tongring and C. Tresser:
   Renormalization on the $n$-dimensional torus.
   Nonlinearity {\bf 5}, 1111-1136, 1992.

\bibitem{BCSS}
   Lenore Blum, Felipe Cucker, Mike Shub and Steve Smale:
   Algebraic Settings for the Problem $\cal P = NP$. 
   Preprint, 1995. 

\bibitem{Canny}
   John Canny:
   {\em The complexity of robot motion planning}.
   MIT Press, Cambridge MA, 1988.

\bibitem{Furstenberg}
   Harry Furstenberg:
   {\em Recurrence in Ergodic Theory and Combinatorial Number Theory}.
   Princeton University Press, Princeton, 1981.

\bibitem{GGJ}
   M.R.Garey, R.L.Graham and D.S.Johnson:
   Some $\np$-complete Geometric Problems.
   {\em Proceedings of the Eight Annual ACM Symposium
   on the Theory of Computing,} 10-21.
   Hershey, Pennsylvania, 1976.

\bibitem{LN}
   Gerhard Larcher and Harald Niederreiter:
   Kronecker-type Sequences and Nonarchimedean
   Diophantine Approximations
   {\em Acta Arithmetica} {\bf 63} Num. 4, 379-396, 1993.

\bibitem{KrickPardo}
   Luis Miguel Pardo Vasallo and Teresa Krick:
   A computational Method for Diophantine Approximation.
   {\em Proceedings of the MEGA'94}.
   Progress in Mathematics, Birkhauser, 1955.

\bibitem{RIEGER}
   G.J.Rieger:
   Effective Simultaneous Approximation of Complex Numbers
   by Conjugate Algebraic Integers.
   {\em Acta Arithmetica} {\bf 63} num. 4, 325-334, 1993.
 
\bibitem{Schmidt785}
   Wolfgang M. Schmidt:
   {\em Diophantine Approximation}.
   Lecture Notes in Mathematics 785,
   Springer-Verlag, Berlin, 1980.


\bibitem{Schmidt1467}
   Wolfgang M. Schmidt:
   {\em Diophantine Approximations and Diophantine Equations}.
   Lecture Notes in Mathematics 1467,
   Springer-Verlag, Berlin, 1991.

\bibitem{Siegel}
   Carl Ludwig Siegel:
   {\em Lectures on the Geometry of Numbers}.
   Springer-Verlag, Berlin, 1989.

\bibitem{Silverman}
   Joseph H. Silverman:
   {\em The Arithmetic of Elliptic Curves}.
   Springer-Verlag, New York, 1986.

\bibitem{Tiwari}
   Prasoon Tiwari:
   A problem that is easier to solve on the unit-cost
   algebraic RAM.
   {\em Journal of Complexity} {\bf 8}, num.\,4, 393-397, 1992.
\end{thebibliography}
\end{document}
