MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
@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)$? – Alan Haynes Nov 23 '11 at 22:20
@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. – Marcin Kotowski Nov 30 '11 at 23:06
@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. – Alan Haynes Dec 1 '11 at 18:19

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.