Simultaneous diophantine approximation with polynomial bound

2011-10-15T23:04:19Z

For a given number $\alpha$ continued fractions expansion $(p_n, q_n)$ of $\alpha$ has the remarkable property that not only $|\alpha - \frac{p_n}{q_n}| < \frac{1}{q_n^2}$, but the converse holds - if $|\alpha - \frac{p}{q}| < \frac{1}{2q^2}$, then $\frac{p}{q}$ will appear in the expansion of $\alpha$.

Is there any analogue of this fact in simultaneous Diophantine approximation with polynomial bound? More precisely, I want to think of this procedure as allowing me to recover unknown ${ \frac{p_i}{q}}$ with $q$ being exponential in $n$, from known $\alpha_i = \frac{s_i}{r}$ with $r$ only polynomial in $n$ and $|\alpha_i - \frac{p_i}{q}| < \frac{1}{poly(n)}$. Is such a procedure even possible, maybe given some additional constraints? (note that doing 1-dimensional continued fractions component-by-component will not do, as it requires resources exponential in $n$ for each component)

(motivation for the problem comes from considering an unknown $n$-dimensional rational lattice and trying to recover their vectors using some polynomial sampling procedure; I want to think of $q$ as the determinant of this lattice, which is reasonably to assume to be exponential in $n$)

Simultaneous diophantine approximation with polynomial bound - MathOverflow

Simultaneous diophantine approximation with polynomial bound