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 be a vector in , and let be a real number. We would like to find integers such that

for all , and is relatively small, say for a given value .

The question is, for what 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 .

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

We took integer linear combinations of the columns with coefficients , with , and . Setting , we get the desired result. The question now is for what value of 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 , such that

.

For this to be less than , we want

.

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

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