next up previous
Next: Application: integer relations between Up: Discrete Math, Tenth Problem Previous: Short vectors

Application: polynomial time algorithm for Simultaneous Diophantine Approximation

Throughout this section, let $ \alpha=(\alpha_1,\cdots \alpha_n)$ be a vector in $ \mathbb{Q}^n$, and let $ \epsilon>0$ be a real number. We would like to find integers $ q>0, p_1,\dots,p_n$ such that

$\displaystyle \vert q\alpha_i-p_i\vert<\epsilon
$

for all $ i$, and $ q$ is relatively small, say $ q\le Q$ for a given value $ Q$.

The question is, for what $ Q$ can we

Dirichlet's Theorem provides an answer to the existence question:

Theorem 3.1 (Dirichlet)   There exists a solution to the above problem with $ Q=\epsilon^{-n}$.

Recall our second proof of Dirichlet's theorem which used Minkowski's theorem. We examined the matrix:

\begin{displaymath}
% latex2html id marker 1689\left[
\begin{array}{ccccc}
-1...
...n \\
0 & \ldots & 0 & 0 & \epsilon/Q \\
\end{array}\right]
\end{displaymath}

We took integer linear combinations of the columns with coefficients $ \{p_1\cdots p_{n+1}\}$, with $ \sum p_i {\mathbf{b}}_i=x$, and $ \Vert x\Vert _\infty\leq \epsilon$. Setting $ p_{n+1}=q$, we get the desired result. The question now is for what value of $ Q$ can we construct such a vector (not just guarantee its existence).

From part (b) of Theorem 2.11, we can find a Lovasz-reduced basis for the lattice spanned by the columns of this matrix, and that gives a vector $ x$, such that

$\displaystyle \Vert x\Vert _\infty\leq\Vert x\Vert\leq2^{n/4}\Delta^{1/(n+1)}
\leq2^{n/4}\left(\frac{\epsilon}{Q}\right)^{1/(n+1)}$.$\displaystyle $

For this to be less than $ \epsilon$, we want

$\displaystyle Q=\frac{2^{n(n+1)/4}}{\epsilon^n}$.$\displaystyle $

So for this value of $ Q$, Lovasz's Lattice Reduction algorithm finds a solution in polynomial time.


next up previous
Next: Application: integer relations between Up: Discrete Math, Tenth Problem Previous: Short vectors
Varsha Dani 2003-07-25