# Rational reconstruction in ring of integers

This post is a wiki. Anyone with karma >750 is welcome to improve it.

I was wondering how to do the following in sage: let's say I have a number field $F$, an embedding $i$ of that field in the complex numbers, and an algebraic integer $\alpha\in F$, for which I know $i(\alpha)$ with good numerical precision. How can I find the exact value?

edit retag close merge delete

Sort by » oldest newest most voted

I finally found the time to think about the matter and look for a solution. Let us say I'm interested in an element $z$ in the integer ring of a number field $\mathbb K$; then if that field is Galois and I have an approximation of all complex embeddings of $z$, I can get a hold of the precise element by multiplying my approximations as a vector-column by the Minkowski embedding of the field to the left. Just take the nearest integer in each component and this gives an expression of the exact element which corresponds to the approximations.

An example is worth thousands words:

K.<a>=NumberField(x**2-2)
K.Minkowski_embedding()**(-1)*matrix(2,1,[477.6,0.1]) # this gives almost the element
(239-169*a).complex_embeddings() # check that it's looking good


(Added later) I must add that this example shows that a single embedding/approximation won't be enough : as you see the approximation $0.1$ could be an approximation of zero or of $239-169\sqrt2$, and there's no way to tell which.

more

This post is a wiki. Anyone with karma >750 is welcome to improve it.

If you are thinking of representing them as floating point numbers, in general it will not be possible to represent the exact value, but you can represent it to arbitrary precision. For example, when creating your number field you can pick an embedding into CC like so:

sage: K.<a> = NumberField(x^3 - 2, embedding=1.2)
sage: CC(a)
1.25992104989487


This gives you 53-bit of floating point precision. For more precision, you can use a a field with more precision:

sage: CC100 = ComplexField(100)
sage: CC100(a)
1.2599210498948731647672106073


Instead of fixing one embedding upon creating your number field, you can also compute all the embeddings into a given field L with K.embeddings(L), and use one of them explicitly.

The field QQbar represents the algebraic closure of the rationals and allows you to do exact arithmetic with arbitrary algebraic numbers. Depending on what you want to do this may also be suitable for you.

more

What you say is nice, but explains how to obtain numerical approximations of known elements of a number field given an embedding. The question is about the converse: given a numerical approximation, how to find out the element?

( 2013-01-10 00:36:35 -0600 )edit