8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – grad student Jul 20 '16 at 15:50
  • 1
    $\begingroup$ @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. $\endgroup$ – Noah Stephens-Davidowitz Jul 27 '16 at 14:11
  • $\begingroup$ 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. $\endgroup$ – Chris Peikert Jul 27 '16 at 14:41
  • $\begingroup$ 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$. $\endgroup$ – grad student Jul 29 '16 at 9:08
  • $\begingroup$ 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. $\endgroup$ – Chris Peikert Jul 29 '16 at 12:29
1
$\begingroup$

Attila Pethő, Michael E. Pohst, Csanád Bertók, On multidimensional Diophantine approximation of algebraic numbers, Journal of Number Theory, Volume 171, February 2017, Pages 422-448, ISSN 0022-314X, http://dx.doi.org/10.1016/j.jnt.2016.07.002. (http://www.sciencedirect.com/science/article/pii/S0022314X16301858) Keywords: Diophantine approximation; Continued fractions; Jacobi–Perron algorithm; LLL-algorithm

$\endgroup$
  • $\begingroup$ I read this paper but don't see its relevance to my question. Can you elaborate? $\endgroup$ – Chris Peikert Apr 11 '17 at 18:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.