# Rational approximation to a set of reals

Are there any well known algorithms for finding good rational approximations to sets of real numbers?

Given just two real numbers, I can use continued fractions to find a rational approximation to their ratio, then use the numerator and denominator; for example a "good" rational approximation to { $\sqrt{2}$, $\sqrt{3}$ } is {9, 11} and {40, 49} is better.

However, with sets of three or more reals, there are some obvious special cases, but I can't see any obvious solution for the general case: in particular, pairwise approximations won't give a "good" approximation for the whole set (in general), i.e. there will be sets of smaller integers which are a better approximation.

Any reasonable definition of good will do - even defining what would count as a "reasonable" definition of good is interesting (in my opinion) even if a rather trivial question! A suitably cunning definition of "good" might even suggest an algorithm... :-)

I do think this question is more mathematical than computational, although perhaps a little elementary for this site, but please suggest where else I could ask it, if it is not appropriate here (and you can't point me at an answer).

-
The underlying mathematical technique is lattice basis reduction (LBR). Finding a small denominator $d_0 \in \bf Z$ such that each of $n$ real numbers $a_1,a_2,\ldots,a_n$ is within $\epsilon$ of an integer is almost the problem of finding a short nonzero vector in the $n+1$ dimensional lattice of integer vectors $(d_0, d_1, d_2, \ldots, d_n)$ with the quadratic form $d_0^2 + \epsilon^{-2} \sum_{i=1}^n (d_i - a_i d_0)^2$. In the familiar case $n=1$ we get 2-dimensional LBR which is essentially the same as the familiar Euclidean algorithm for rational approximation. –  Noam D. Elkies Jul 28 '12 at 17:11

## 1 Answer

Given reals $x_1,x_2,\dots,x_n$ and real $Q$, Dirichlet's Pigeonhole Principle argument guarantees the existence of integers $p_1,p_2,\dots,p_n,q$ such that $1\le q\le Q^n$ and $|p_n-qx_n|\le1/Q$. There is a good exposition here.

-
True, but even for $n=1$ one must do more to efficiently find such a solution when $Q$ is too large for exhaustive search. –  Noam D. Elkies Jul 29 '12 at 0:47
Sure, but 1. Jonathan has asked for a definition of good rational approximation, and I have given one, and 2. I believe the article does go into the practical aspects. In short, I think Jonathan will benefit from checking it out. –  Gerry Myerson Jul 29 '12 at 6:32