Ask Your Question
0

Rational reconstruction in ring of integers

asked 2012-12-25 08:14:36 -0500

this post is marked as community wiki

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 flag offensive close merge delete

2 answers

Sort by ยป oldest newest most voted
0

answered 2013-03-24 02:55:53 -0500

Snark gravatar image

updated 2013-03-27 06:33:13 -0500

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.

edit flag offensive delete link more
0

answered 2013-01-08 03:06:34 -0500

this post is marked as community wiki

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.

edit flag offensive delete link more

Comments

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?

Snark gravatar imageSnark ( 2013-01-10 00:36:35 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2012-12-25 08:14:36 -0500

Seen: 172 times

Last updated: Mar 27 '13