Simultaneous diophantine approximation with polynomial bound - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T19:51:24Z http://mathoverflow.net/feeds/question/78233 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/78233/simultaneous-diophantine-approximation-with-polynomial-bound Simultaneous diophantine approximation with polynomial bound Marcin Kotowski 2011-10-15T23:04:19Z 2011-10-15T23:13:59Z <p>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}| &lt; \frac{1}{q_n^2}$, but the converse holds - if $|\alpha - \frac{p}{q}| &lt; \frac{1}{2q^2}$, then $\frac{p}{q}$ will appear in the expansion of $\alpha$.</p> <p>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}| &lt; \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)</p> <p>(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$)</p>