Number fields with and without a given embedding

[Simon King]

Hi!

When defining a number field, it is optional to provide a canonical
embedding into the real lazy field.

If two number fields are defined by the same polynomial and the same
generator name, they are still considered different, if only one of
them defines a canonical embedding.

Example:
sage: K.<a> = NumberField(x^3-5,embedding=0)
sage: L.<a> = NumberField(x^3-5)
sage: K==L
False

But even more, there is no coercion:
sage: K.has_coerce_map_from(L)
False
sage: L.has_coerce_map_from(K)
False

Shouldn't there be one coercion? But in what direction? L to K or K to
L?

Cheers,
Simon

[John Cremona]

I never use these canonical embeddings, and cannot think of a reason
for defining one field twice in this way...

Now this would be more useful:

sage: K.<a> = NumberField(x^2+3)
sage: L.<w> = NumberField(x^2+x+1)

sage: K.has_coerce_map_from(L)
False
sage: L.has_coerce_map_from(K)
False

sage: K.is_isomorphic(L)
True
sage: K.embeddings(L)
[
Ring morphism:
From: Number Field in a with defining polynomial x^2 + 3
To: Number Field in w with defining polynomial x^2 + x + 1
Defn: a |--> 2*w + 1,
Ring morphism:
From: Number Field in a with defining polynomial x^2 + 3
To: Number Field in w with defining polynomial x^2 + x + 1
Defn: a |--> -2*w - 1
]

to turn into a coercion!

John

> --
> To post to this group, send an email to sage-...@googlegroups.com
> To unsubscribe from this group, send an email to sage-devel+...@googlegroups.com
> For more options, visit this group at http://groups.google.com/group/sage-devel
> URL: http://www.sagemath.org
>

[Simon King]

Hi John!

On 24 Nov., 22:40, John Cremona <john.crem...@gmail.com> wrote:
> I never use these canonical embeddings, and cannot think of a reason
> for defining one field twice in this way...

Well, it is imaginable that some automatic constructions (say, in
pushout) create such a situation. And if it occurs, the program should
know how it is supposed to cope with it.

> Now this would be more useful:
>
> sage: K.<a> = NumberField(x^2+3)
> sage: L.<w> = NumberField(x^2+x+1)
> sage: K.has_coerce_map_from(L)
> False
> sage: L.has_coerce_map_from(K)
> False
> sage: K.is_isomorphic(L)
> True
> sage: K.embeddings(L)
> [
> Ring morphism:
>   From: Number Field in a with defining polynomial x^2 + 3
>   To:   Number Field in w with defining polynomial x^2 + x + 1
>   Defn: a |--> 2*w + 1,
> Ring morphism:
>   From: Number Field in a with defining polynomial x^2 + 3
>   To:   Number Field in w with defining polynomial x^2 + x + 1
>   Defn: a |--> -2*w - 1
> ]
>
> to turn into a coercion!

Since there are two different embeddings, I doubt that one can turn it
into a coercion:
A coercion must be unique for the given pair of parents; hence, you
need an algorithm to pick one of the above embeddings. Moreover, the
choices must be consistent, i.e., the concatenation of two coercion
maps must be a coercion map.

Can you propose a canonical and consistent choice of isomorphism?

Cheers,
Simon

[Simon King]

On 24 Nov., 23:56, Simon King <simon.k...@uni-jena.de> wrote:
> > I never use these canonical embeddings, and cannot think of a reason
> > for defining one field twice in this way...
>
> Well, it is imaginable that some automatic constructions (say, in
> pushout) create such a situation. And if it occurs, the program should
> know how it is supposed to cope with it.

The reason for my question was a bug that I introduced while working
at #8800. I can solve it by being more careful with the data stored in
the construction functors, and also by allowing broader conversion
(not coercion) between different number fields.

Nevertheless, I think this case of coercion between a number field
with and a number field without embedding (which direction??) should
be covered.

Cheers,
Simon

[John Cremona]

Despite my earlier comment I am not proposing automatic coercion
between isomorphic number fields since there is (often, not always!)
more than one isomorphism.

Surely a number field + embedding is a richer structure than an
abstract number field, so the coercion should go from the former to
the latter as a forgetful functor.

Are you going to similarly come up with the question of coercion
between two number fields which are the same abstract field and with
mathematically the same embedding, but with one of higher precision
than the other?

John

PS What's wrong with sage-nt?!

[luisfe]

I agree that there should be a coercion, coercion from K to L should
not be hard to implement.

Coercion from L to K would certainly be interesting, but I do not
figure out right now how to make it consistent.

Suppose the following:

sage: K.<r4> = NumberField(x^4-2)
sage: L1.<r2_1> = NumberField(x^2-2, embedding = r4**2)
sage: L2.<r2_2> = NumberField(x^2-2, embedding = -r4**2)
sage: K.has_coerce_map_from(L1)
True
sage: K.has_coerce_map_from(L2)
True
sage: L3.<a> = NumberField(x^2-2)

If there where coercions from non-embedded fields to embedding field,
there would be an embedding from L3 to L1 and L3 to L2. So, the
coercion model would discover two possible coercions from L3 to K. How
can we make them compatible? It seems that making a consistent
coercion framework would be equivalent to compute a "canonical"
coercion from every NumberField to QQbar. Specifying an embedding
would be like overriding the "canonical" coercion by a different one.

But then I could play a different game and construct:

sage: K=Qp(7)
sage: R = K[x](x^2-2).roots()
sage: L1.<r1> = NumberField(x^2-2, embedding=R[0][0])
sage: L2.<r2> = NumberField(x^2-2, embedding=R[1][0])
sage: K(r1)
3 + 7 + 2*7^2 + 6*7^3 + 7^4 + 2*7^5 + 7^6 + 2*7^7 + 4*7^8 + 6*7^9 +
6*7^10 + 2*7^11 + 7^12 + 7^13 + 2*7^15 + 7^16 + 7^17 + 4*7^18 + 6*7^19
+ O(7^20)
sage: K(r2)
4 + 5*7 + 4*7^2 + 5*7^4 + 4*7^5 + 5*7^6 + 4*7^7 + 2*7^8 + 4*7^11 +
5*7^12 + 5*7^13 + 6*7^14 + 4*7^15 + 5*7^16 + 5*7^17 + 2*7^18 + O(7^20)

By the way, is there a problem with coercions?
With the first set of fields I encounter the following error:

sage: r4+r2_1
r4^2 + r4
sage: r4+r2_2
-r4^2 + r4
sage: r2_1+r2_2
ERROR: An unexpected error occurred while tokenizing input
The following traceback may be corrupted or invalid
The error message is: ('EOF in multi-line statement', (1077, 0))

[Simon King]

Hi John!

On 25 Nov., 10:30, John Cremona <john.crem...@gmail.com> wrote:
> Surely a number field + embedding is a richer structure than an
> abstract number field, so the coercion should go from the former to
> the latter as a forgetful functor.

To the contrary, it seems to me that a coercion should go from the
poorer structure to the richer structure, if there is a canonical way
to do so.

Example: A field is richer than a ring - and we have
sage: GF(5).has_coerce_map_from(Integers(5))
True
sage: Integers(5).has_coerce_map_from(GF(5))
False

For number fields, we *do* have a canonical choice, namely (provided
that the defining polynomials match) sending the generator to the
generator.

Of course, mapping generator to generator would work in both
directions. However, if there is a way to preserve structure (here:
embedding) then one should by all means do so.

> Are you going to similarly come up with the question of coercion
> between two number fields which are the same abstract field and with
> mathematically the same embedding, but with one of higher precision
> than the other?

Let K be a number field and R be some ring.

I think there should be coercion from R to K if
* R coerces into the base ring of K (which might be another number
field)
or
* R is a number field and
+ R.base_ring() coerces into K.base_ring() (again covering stacks
of number fields)
+ R.relative_polynomial() == K.relative_polynomial() and
+ either R has no given embedding or
- R.coerce_embedding()(R.gen())==K.coerce_embedding()(K.gen())
and
- R.coerce_embedding()(R.gen()).parent() coerces into
K.coerce_embedding()(K.gen()).parent()

The last line means that it goes from higher to lower precision, since
we have
sage: RealField(4).has_coerce_map_from(RealField(50))
True

> PS What's wrong with sage-nt?!

I thought this was a question on coercion (of number fields), not on
number fields as such.

But I guess the simple reason is that I don't usually read sage-nt.

Cheers,
Simon

[Simon King]

Hi Luis!

On 25 Nov., 10:34, luisfe <lftab...@yahoo.es> wrote:
> Suppose the following:
>
> sage: K.<r4> = NumberField(x^4-2)
> sage: L1.<r2_1> = NumberField(x^2-2, embedding = r4**2)
> sage: L2.<r2_2> = NumberField(x^2-2, embedding = -r4**2)
> sage: K.has_coerce_map_from(L1)
> True
> sage: K.has_coerce_map_from(L2)
> True
> sage: L3.<a> = NumberField(x^2-2)
>
> If there where coercions from non-embedded fields to embedding field,
> there would be an embedding from L3 to L1 and L3 to L2. So, the
> coercion model would discover two possible coercions from L3 to K. How
> can we make them compatible?

Excellent argument!

I was not aware that there already is a coercion from L1 and L2 to K.
Then, indeed, it is not possible to extend everything consistently in
a structure preserving way, and I have to withdraw the answer that I
just gave to John.

> By the way, is there a problem with coercions?
> With the first set of fields I encounter the following error:
>
> sage: r4+r2_1
> r4^2 + r4
> sage: r4+r2_2
> -r4^2 + r4
> sage: r2_1+r2_2
> ERROR: An unexpected error occurred while tokenizing input
> The following traceback may be corrupted or invalid
> The error message is: ('EOF in multi-line statement', (1077, 0))

That seems fine to me. You can add r4 with r2_1 or r2_2, because there
is coercion from L1 or L2 to K. But I guess there is no way to
construct a canonical parent into which both L1 and L2 coerce (K is
certainly not canonical, or is it?). So, the coercion system would not
find a parent structure in which to perform the sum of r2_1 and r2_2.

Cheers,
Simon

[luisfe]

As long as you construct L1 with a specified embedding to K, from a
user point of view you are stating "I am working on this subfield L1
of K, but I want a subfield representation in terms of powers of
r2_1". In that sense yes, K would be canónical. It would not be in L2
had not an embedding to K or an embedding to a different field.

I am not sure if construction time embedding is treated equally to any
other embedding to other fields you can make sage aware after
construction of L1 by register_coercion. If it is treated just equal
the rest of possible embeddings, yes, K would not be canonical.

However what I wanted to point out is that my Sage installation hangs
on that computation, repeating the ERROR.

[Simon King]

Hi Luis,

On 25 Nov., 11:45, luisfe <lftab...@yahoo.es> wrote:
> As long as you construct L1 with a specified embedding to K, from a
> user point of view you are stating "I am working on this subfield L1
> of K, but I want a subfield representation in terms of powers of
> r2_1". In that sense yes, K would be canónical.

Sounds good to me. And I think I know how this could be implemented:

The job of finding a canonical common parent is done by
sage.categories.pushout.pushout(). It starts with considering the
constructions that yield to L1 and L2 - in both cases, one has an
AlgebraicExtensionFunctor, say, F1 and F2, starting at the same base
ring, QQ.

Then, pushout() tries to process F1 and F2 into another construction
functor, F, so that F1(QQ) and F2(QQ) both coerce into F(QQ).

This can be done by
- concatenation of F1 and F2, but the order would not be canonical
- merging of F1 and F2, but this is not implemented yet.

I believe one could implement a merge of F1 and F2 so that F1.merge(F2)
(QQ) yields K in your example above, making an algorithm out of your
argument that K really is a canonical parent of L1 and L2. And this
would solve the coercion bug you encounter.

Cheers,
Simon

[John Cremona]

I think I am out of my depth already, but I just wanted to make sure
that you knew of the composite_fields() method for number fields. In
Luis's example, you can do all of L1.composite_fields(K),
L2.composite_fields(K), K.composite_fields(L1),
K.composite_fields(L2), in each case it reurns a list of one element
which is K itself; but L1.composite_fields(L2) crashes. That may be
for the same reason as the problem Luis encountered.

Take a look at the docstring for composite_fields() : it has a
parameter preserve_embedding which, if both fields come with
embeddings, only gives compositums (composita?) which are compatible
with both embeddings.

What I have difficulty with is the relation between (a) explicit code
with actual objects, such as the code for composite_fields(), and (b)
the very general merging-functors sort of code. Is it the case that
both are needed, and that (a) uses (b)?

John

[Simon King]

Hi John,

On 25 Nov., 12:45, John Cremona <john.crem...@gmail.com> wrote:
> I think I am out of my depth already, but I just wanted to make sure
> that you knew of the composite_fields() method for number fields.  In
> Luis's example,  you can do all of L1.composite_fields(K),
> L2.composite_fields(K), K.composite_fields(L1),
> K.composite_fields(L2), in each case it reurns a list of one element
> which is K itself;  but L1.composite_fields(L2) crashes.  That may be
> for the same reason as the problem Luis encountered.

I don't think so:

sage: K.<r4> = NumberField(x^4-2)
sage: L1.<r2_1> = NumberField(x^2-2, embedding = r4**2)
sage: L2.<r2_2> = NumberField(x^2-2, embedding = -r4**2)

sage: from sage.categories.pushout import pushout,construction_tower
sage: pushout(L1,L2)
---------------------------------------------------------------------------
CoercionException Traceback (most recent call
last)
...
CoercionException: ('Ambiguous Base Extension', Number Field in r2_1
with defining polynomial x^2 - 2, Number Field in r2_2 with defining
polynomial x^2 - 2)

And as long as there is such error, r2_1+r2_2 won't work.

> What I have difficulty with is the relation between (a) explicit code
> with actual objects, such as the code for composite_fields(), and (b)
> the very general merging-functors sort of code.  Is it the case that
> both are needed, and that (a) uses (b)?

It seems to me that (b) is in the very centre of Sage's coercion
model, in particular when we consider the pushout: The arguing is
solely with functors, without any rings involved.

Hence, if the "abstract nonsense" (thus (b)) is not right then
arithmetic between elements of L1 and L2 won't work. And I don't see
how the method composite_fields() could be used in the coercion
framework, since this is about objects (not functors).

However, looking at the code of composite_fields, I think that one
would do very similar things in the merge() method of
AlgebraicExtensionFunctor. Trying it now.

Cheers,
Simon

[Simon King]

Hi Luis,

With merging as I proposed in my previous post, one gets

sage: K.<r4> = NumberField(x^4-2)
sage: L1.<r2_1> = NumberField(x^2-2, embedding = r4**2)
sage: L2.<r2_2> = NumberField(x^2-2, embedding = -r4**2)
sage: from sage.categories.pushout import pushout

sage: pushout(L1,L2)
Number Field in r4 with defining polynomial x^4 - 2

But apparently something else is wrong, since r2_1+r2_2 still yields
the ERROR that you observed, even though
sage: K(r2_1) + K(r2_2)
0

Now I'm puzzled where the ERROR comes from.

Cheers,
Simon

[luisfe]

mmm, with a clean sage 4.6 I get

sage: pushout(L1,L2)
Exception RuntimeError: 'maximum recursion depth exceeded while
calling a Python object' in <type 'exceptions.TypeError'> ignored
...
RuntimeError: maximum recursion depth exceeded

I will try with patch #8800

With your new code does John's example L1.composite_fields(L2) work?

[Simon King]

Hi Luis,

On 25 Nov., 14:01, luisfe <lftab...@yahoo.es> wrote:
> mmm, with a clean sage 4.6 I get
>
> sage: pushout(L1,L2)
> Exception RuntimeError: 'maximum recursion depth exceeded while
> calling a Python object' in <type 'exceptions.TypeError'> ignored
> ...
> RuntimeError: maximum recursion depth exceeded
>
> I will try with patch #8800

No, this won't work, since
(1) it relies on #8807
(2) there is some bit rot, so, it won't apply
(3) it does not contain the changes discussed here, yet.

> With your new code does John's example L1.composite_fields(L2) work?

I did not change anything in composite_fields, so, I guess it would
still work.
Cheers,
Simon

[luisfe]

Hi Simon,

On 25 nov, 13:53, Simon King <simon.k...@uni-jena.de> wrote:
> Now I'm puzzled where the ERROR comes from.

I might be wrong, since coercion still looks "magic" like me. But it
seems that before trying pushout of the objects, Sage tries
L1.coerce_map_from(L2)

Now, it seems that, whenever BOTH fields have an embedding defined, it
tries to obtain numeric appoximations somewhere. Maybe it assumes that
embedding means real/complex embedding?

sage: L1.<r2_1>=NumberField(x^2-2, embedding=1)
sage: L2.<r2_2>=NumberField(x^2-2, embedding=-1)
sage: r2_1+r2_2 # Cool!
0
sage: _.parent() is L1
True
sage: L1.coerce_map_from(L2)
Generic morphism:
From: Number Field in r2_2 with defining polynomial x^2 - 2
To: Number Field in r2_1 with defining polynomial x^2 - 2
Defn: r2_2 -> -r2_1

To construct this morphism I guess that some kind of numerics is
involved

sage: CC(r2_2)
-1.41421356237309

sage: L3.<r2_3>=NumberField(x^2-2)
sage: CC(r2_3)

...
RuntimeError: maximum recursion depth exceeded

The infinite bucle looks related with caches recursion error appears
is the same as trying L1.coerce_map_from(L2). I guess that, when
trying r2_1 + r2_2 encounters the previous error but something nasty
happens with the error message... But all this needs further research.

But this only happens if both fields have embeddings defined to
another number field


sage: L1.<r2_1>=NumberField(x^2-2, embedding=r4**2)
sage: L2.<r2_2>=NumberField(x^2-2, embedding=-r4**2)
sage: L3.<r4_3>=NumberField(x^2-2)
sage: L4.<r4_2>=NumberField(x^2-2)
sage: L5.<r5_2>=NumberField(x^2-2, embedding=1)
sage: L4.coerce_map_from(L3) #returns None, none field have embedding
defined
sage: L1.coerce_map_from(L3) #returns None, L1 has embedding defined
sage: L4.coerce_map_from(L1) #returns None
sage: L1.coerce_map_from(L2)
Boom
sage: L1.coerce_map_from(L5) #returns None
sage: L5.coerce_map_from(L1) #returns None

[Simon King]

Hi Luis!

On 25 Nov., 15:43, luisfe <lftab...@yahoo.es> wrote:
> I might be wrong, since coercion still looks "magic" like me. But it
> seems that before trying pushout of the objects, Sage tries
> L1.coerce_map_from(L2)

That's correct, and in fact this is where things go boom.

> The infinite bucle looks related with caches recursion error appears
> is the same as trying L1.coerce_map_from(L2). I guess that, when
> trying r2_1 + r2_2 encounters the previous error but something nasty
> happens with the error message... But all this needs further research.

Could very well be. I tried to step through the computation using
%trace. Almost immediately, the _repr_ method of number fields was
called - this could very well be in order to create an error message.
And then it was called over and over again.

Well, let's see what debugging reveals.

BTW, #8800 originally was about raising the doctest coverage of
sage.categories.pushout. I found at least 10 bugs while trying to
provide full doc tests coverage - and I think bugs in the coercion
model are potentially very nasty, as coercion is used all over the
place.

Cheers,
Simon

[Simon King]

On 25 Nov., 17:04, Simon King <simon.k...@uni-jena.de> wrote:
> Well, let's see what debugging reveals.

Got it!

In NumberField_absolute._coerce_map_from_, an
EmbeddedNumberFieldMorphism is constructed. The optional argument
(namely the ambient field) is constructed, but it was forgotten to
pass it as an optional argument to the init method of
EmbeddedNumberFieldMorphism. Hence, EmbeddedNumberFieldMorphism tries
to locate both number fields L1 and L2 in CDF, rather than in K as it
should.

With the other changes proposed in this thread (merging of
construction functors), I finally obtain

sage: K.<r4> = NumberField(x^4-2)
sage: L1.<r2_1> = NumberField(x^2-2, embedding = r4**2)
sage: L2.<r2_2> = NumberField(x^2-2, embedding = -r4**2)

sage: r2_1+r2_2
0

Thanks for all your input on coercion!
Simon

[William Stein]

On Wed, Nov 24, 2010 at 1:40 PM, John Cremona <john.c...@gmail.com> wrote:
> I never use these canonical embeddings, and cannot think of a reason
> for defining one field twice in this way...
>
> Now this would be more useful:
>
> sage: K.<a> = NumberField(x^2+3)
> sage: L.<w> = NumberField(x^2+x+1)
> sage: K.has_coerce_map_from(L)
> False
> sage: L.has_coerce_map_from(K)
> False
> sage: K.is_isomorphic(L)
> True
> sage: K.embeddings(L)
> [
> Ring morphism:
>  From: Number Field in a with defining polynomial x^2 + 3
>  To:   Number Field in w with defining polynomial x^2 + x + 1
>  Defn: a |--> 2*w + 1,
> Ring morphism:
>  From: Number Field in a with defining polynomial x^2 + 3
>  To:   Number Field in w with defining polynomial x^2 + x + 1
>  Defn: a |--> -2*w - 1
> ]
>
> to turn into a coercion!

And it is easy to do so:

sage: phi = K.embeddings(L)
sage: phi[0].register_as_coercion()
sage: a + w
3*w + 1

William