2
$\begingroup$

Suppose we have $n$ linearly independent (over $\mathbb{Q}$) irrational numbers $\{ \alpha_i | 1\leq i \leq n \}$. For the simultaneous Diophantine approximation problem

$$ |q \alpha_i - p_i | < \epsilon , $$

where $q$ and the $p$'s are all integers, we have the LLL algorithm. The problem is, by this algorithm, for each precision $\epsilon$, we get only one $q$. But we know that such $q$ have a density of $\epsilon^{n-1} $.

So, how can we get a series of $q$ with the prescribed precision $\epsilon$?

$\endgroup$

1 Answer 1

3
$\begingroup$

One very practical method of finding the $q$'s you are looking for is presented here:

Kovács, Attila, and Norbert Tihanyi. "Efficient computing of n-dimensional simultaneous Diophantine approximation problems." Acta Universitatis Sapientiae, Informatica 5.1 (2013): 16-34.

In what has to be one of the coolest applications of simultaneous Diophantine approximation ever, the authors use their algorithm to find many (but not all) values of the Riemann-Siegel Z function where Z(t) >500. See: http://riemann-siegel.com/index.php for more details.

Another choice is the method described in:

Bosma, Wieb, and Ionica Smeets. "Finding simultaneous Diophantine approximations with prescribed quality." The Open Book Series 1.1 (2013): 167-185.

From the abstract: "We give an algorithm that finds a sequence of approximations with Dirichlet coefficients bounded by a constant only depending on the dimension. The algorithm uses LLL lattice basis reduction."

Added (3/27):

You may find this paper helpful:

Lagarias, J. C. "Geodesic multidimensional continued fractions." Proceedings of the London Mathematical Society 3.3 (1994): 464-488.

Doug Hensley references the Lagarias algorithm in this paper (book chapter?):

http://www.math.tamu.edu/~doug.hensley/SimultaneousDiophantine.pdf

If you are not too concerned with the quality of the approximations this book presents many algorithms that work (w/o LLL) and may be useful:

Brentjes, Arne Johan. "Multi-dimensional continued fraction algorithms." MC Tracts 145 (1981): 1-183.

This book may still be available for purchase through ntis.gov and is well worth the cost.

A complete answer to your question depends on how the $q$'s you are looking for compare to the given $\epsilon$ and the desired computational complexity of the process for finding them. In the extremes, I don't know if there is a completely satisfying answer.

$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .