An algorithm for the simultaneous Diophantine approximation

393 Views Asked by At

The celebrated theorem by Dirichlet states that for given real numbers $\{\gamma_1, \ldots, \gamma_N \}$ and $\epsilon > 0$, there exists an integer $q\leq 1/\epsilon^N $ such that

$$\max \{ \parallel q \gamma_1 \parallel, \parallel q \gamma_2 \parallel, \ldots, \parallel q \gamma_N \parallel \} \leq 1 /\epsilon . $$

The problem is, is there any algorithm for finding such a $q$?

ps. The $N=1$ case is trivial. Let us do $N> 1$.

1

There are 1 best solutions below

0
On

One good reference for this kind of problem is:

Berthé, Valerie. "Multidimensional Euclidean algorithms, numeration and substitutions." Integers B 11 (2011): A2.

In particular, you may find chapters 4, 5 and 6 useful. There are alternatives to the Markovian continued fraction algorithms and the lattice reduction algorithms described in the above survey. Here is one such algorithm in dimension two that works reasonably well:

enter image description here