# Efficient Dirichlet approximation (continued fractions?) over a number field

Is there an efficient algorithm for Dirichlet approximation for a given (high-degree) number field and its ring of integers, perhaps analogous to the Euclidean/continued fractions algorithm for the integers?

In more detail, I have the following setup: let $K$ be a fixed number field of degree $n$ with canonical/Minkowski embedding $\sigma \colon K \to \mathbb{C}^n$, and let $O_K$ denote the ring of integers. Assume that a "high quality" (w.r.t. $\sigma$) integral basis of $O_K$ is known. (An example of particular interest is cyclotomic number fields.)

Given some $\omega \in K$, I would like to find (as efficiently as possible) an ideal $J \subset O_K$ of "not too large" norm, and a field element $x \in J^{-1}$ such that $\| \sigma(\omega - x) \|$ is "rather small" relative to $N(J)$ -- significantly smaller than the distance from a typical $\gamma$ to $J^{-1}$.

When $K=\mathbb{Q}$, we of course have the Dirichlet approximation theorem and an efficient continued fractions algorithm, which gives us a sequence of $J=q\mathbb{Z}$, $x=p/q$ such that $| \omega - x | \leq 1/q^2$.

For $K=\mathbb{Q}(i)$ or $K=\mathbb{Q}(\zeta_3)$, whose rings of integers are respectively the Gaussian and Eisenstein integers, there are analogous approximation bounds and continued fractions algorithms due to Hurwitz, Ford, and others.

Dirichlet's approximation theorem generalizes to any number field (depending on exactly how one defines the approximation quality; see this question), but I have not found anything about an efficient approximation algorithm (or a conjecture that the problem is computationally hard). Similarly, there is a great deal of work devoted to showing that various number rings are Euclidean domains (with either the standard norm or some other function), but I haven't seen anything about whether the associated continued fraction algorithms yield good approximations in the sense described above.

• I'm not sure how large degree or discriminant these number fields are for your purposes, but just explicitly finding an ideal $J$ of small norm may be quite hard. I guess it comes down to finding integral elements of small norm in the product-of-conjugates sense. But once you have $J$ in hand, finding a basis for $J^{-1}$ is not too hard? And then it boils down to the usual nearest neighbor lattice problem? Jul 20, 2016 at 15:50
• @gradstudent You're right that for fixed J the problem is just a lattice problem. But, the question here is whether we can do much better than that by choosing J adaptively. For example, in the simple one-dimensional case when the number field is just the rationals, where we just want to approximate some x by a rational p/q number with low-ish denominator q, we can do much much better if we're allowed to choose q dependent on x. Jul 27, 2016 at 14:11
• The norm of $J$ need not be exceptionally small -- e.g., $n^n$ would be fine, and it is easy to find such ideals. The degree of the number field could be in the hundreds or more. Jul 27, 2016 at 14:41
• I see. And the naive coordinate-by-coordinate approach is insuffiicent? What I mean is is $(a_1,\dots,a_n)$ is your $\mathbf{Z}$-basis, and $\omega = \sum r_i a_i$ for $r_i \in \mathbb{Q}$, then $r_i \approx p_i / q_i$ for say $q_i \leq B$. Then set $Q$ equal to the least common multiple of the $q_i$, and take $J = Q\mathcal{O}_K$ to be your ideal. Then if you want to find an ideal of smaller norm, you can try factoring $J$. Jul 29, 2016 at 9:08
• Thanks, but I don't think this would work -- it's basically simultaneous Diophantine approximation on the $r_i$, which doesn't give a good enough approximation for what we need. Jul 29, 2016 at 12:29