Throughout this section, let be a vector in , and let be a real number. We would like to find integers such that

The question is, for what can we

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

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.