2
$\begingroup$

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$)

$\endgroup$
3
  • $\begingroup$ @Marcin There are two things that are confusing me. First, do you really mean to allow $r$ to grow with $n$? It seems like the dependence of the problem on $r$ is artificial since you can just multiply it through the whole equation. Secondly, do you really mean $poly(n)$ on the RHS of your inequality, or should it be $poly(q)$? $\endgroup$ Nov 23, 2011 at 22:20
  • $\begingroup$ @AH: I do mean poly(n) - poly(q) would be exponential in n. r must grow with n, otherwise, you can't even hope to recover q. $\endgroup$ Nov 30, 2011 at 23:06
  • $\begingroup$ @Marcin I think your question has an answer but it is hard to determine exactly what you are asking. For example why can't you recover $q$ if $r$ does not grow with $n$? No matter what $r$ is, for any $q$, if the RHS is less that $1/2q$ then there is always a choice of $p_i$'s that works. That is also why I asked if you really to say mean $1/poly (n)$ on the RHS. If $q$ grows along any sequence which is exponential in $n$ but the bound on the right hand side is only $1/poly (n)$ then for every large enough $q$ there will be many choices for $p_i$'s. $\endgroup$ Dec 1, 2011 at 18:19

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.