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

$$\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

• guarantee that there exists a solution;
• find a solution in polynomial time?

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:

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

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

$$\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)}$$.$$$$

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

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

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