Application: integer relations between real numbers

More generally, given real numbers $\alpha_j$, we need integers $p_i$, not all zero, such that $\vert\sum p_i\vert<\epsilon$. What we would like to know is for what $Q$, can we find such integers, $p_i$, such that $p_i<Q$? To this end, we construct the following matrix:

$$% latex2html id marker 1726\left[ \begin{array}{ccccc} \a... ...\ & \ddots & \\ 0 & & \epsilon/Q \\ \end{array}\right]$$

(Notice that this is not a square matrix.) Now we would like a vector $x$, such that $x=\sum p_i{\mathbf{b}}_i$ and $\Vert x\Vert _\infty\leq \epsilon$. Such a vector with repsect to this matrix would be a solution to our problem. Again applying part b of Theorem 2.11, we know that

$$\Vert x\Vert _\infty\leq\Vert x\Vert\leq2^{n/4}\Delta^{1/(n+1)}$$.$$$$

Now we need only compute $\Delta$, and solve $2^{n/4}\Delta^{1/(n+1)}=\epsilon$ for $Q$. Recall that we can compute $\Delta$ using the Gram matrix, $\Delta^2=$det$(A^TA)$.

Exercise 4.1   Let $A$ be the matrix:

$$% latex2html id marker 1751\left[ \begin{array}{ccccc} \a... ...& 0 \\ & \ddots & \\ 0 & & \beta \\ \end{array}\right]$$

and show that $\Delta=\vert\beta\vert^{n-1}\sqrt{\beta^2+\sum\alpha_i^2}$.

Exercise 4.2   Find the appropriate $Q$ for the above example.