Re: [sage-algebra] Re: Bidirectional coercions?

[David R. Kohel]

Hi,

I should just emphasize that coercions (applied automatically) must
be canonical. There were some coercion problems in Magma precisely
with number fields K, L, with K a subfield of L, and K', isomorphic
to K, which created non-commuting coercion diagrams by "recognizing"
K' as "equal" to K (same defining polynomial), then using K' -> K
and K -> L for the coercion.

In general, if two non-equal fields have not been constructed with
a coercion between then then no choice should be made. I don't
see how one can choose any coercion between a cyclotomic field with
embedding and another number field which does not come equipped
with an embedding in a common field.

Thus for Simon's question 1, I agree (with Sage) that there should
be no coercion. For question 2, I wouldn't want or expect coercion
to move outside of the given parents (and certainly not outside of
the domain of number fields). For question 3, I would only return
something which is categorically defined -- the pushout of (K,K->F)
and (L,L->F) should be again a minimal field M with embedding M->F
whose image contains the images of K and L, right? Returning
(F, id:F->F) would be mathematically wrong. Most likely the
determination of such a field would be expensive and not something
that one would to be invoked by automatic coercion.

Cheers,

David

[Simon King]

Hi!

That's an answer to a thread on sage-algebra, that was originally
motivated by a question on number fields.

I disagree with David's answer in various points, though my
disagreement partially depends on properties of
EmbeddedNumberFieldMorphism.

Part 1: Both number fields are embedded.

My questions:
Let K1 and K2 be number fields provided with an embedding into a field
L. Let K3 be a number field embedded into a field L' and assume that
there is a coercion from L to L'.
1. Is it true that EmbeddedNumberFieldMorphism(K1,K2,L) composed with
EmbeddedNumberFieldMorphism(K2,K3,L') is the same as
EmbeddedNumberFieldMorphism(K1,K3,L')?
2. Is it true that EmbeddedNumberFieldMorphism(K1,K1,L) is the
identity?
3. Is it true that EmbeddedNumberFieldMorphism(K1,K2,L) composed with
the given embedding from K2 to L coincides with the given embedding
from K1 to L?
4. Is it true that EmbeddedNumberFieldMorphism(K1,K2,L) coincides with
EmbeddedNumberField(K1,K2,L')?

If the answer to these four questions is affirmative then I must
disagree with David:
Yes, it *is* possible to define coercions between embedded number
fields in a consistent way.

The real question is: Do we *want* these coercions? Apparently David
Roe does not like if there is both a coercion from K1 to K2 and from
K2 to K1, but Nicolas Thiery loves that.



Part 2: Only one number field is embedded
I think David misunderstood: I did not state that there should be a
coercion from a non-embedded to an embedded field. The opposite
coercion (by forgetful functor) should be fine, though. I suppose that
David and I agree here.



Part 3: Pushout of two embedded number fields
Assume that K1->L1 and K2->L2 are embedded number fields, and assume
that EmbeddedNumberFieldMorphism(K1,K2,pushout(L1,L2)) returns None.

The first question is:
Is it possible (i.e., consistent) to define
pushout(K1,K2):=pushout(L1,L2) ? David says 'no', because
mathematically the pushout of K1 and K2 should be the minimal sub-
field of pushout(L1,L2) that contains the images of K1 and K2. I say
'yes', because there are canonical (coercion) embeddings of both K1
and K2 into pushout(L1,L2).

Note that Sage's pushout is not a mathematical pushout, anyway: It
relies on choices (such as pushout(QQ,ZZ['x'])!=Frac(ZZ['x']) ), but
that should be fine as long as these choices are computationally
unique and consistent thorought Sage.

Side question:
Is it implemented in Sage to find the minimal sub-field of
pushout(L1,L2) containing the images of K1 and K2?

Second question:
Assume we agree that it *is* possible to define
pushout(K1,K2):=pushout(L1,L2): Do we *want* that the sum of two
number field elements (one from K1, the other from K2) may be an
element of CDF?

Cheers,
Simon

[Simon King]

Cc to sage-nt, since it also concerns number fields.

On 29 Nov., 15:22, Simon King <simon.k...@uni-jena.de> wrote:
> Since it seems to be the opinion of most of you, I'll try to avoid
> bidirectional coercions in my soon-to-be-posted update of my patch for
> #8800.
>  * I will not use EmbeddedNumberFieldMorphism to construct coercions
> between embedded number fields, since it would produce bidirectional
> coercions.

Ouch. I just found that having bidirectional coercions for embedded
number fields was not my idea: It was already implemented!

Example *without* my patch:
sage: L1.<r2_1> = NumberField(x^2-2, embedding = 1)
sage: L2.<r2_2> = NumberField(x^2-2, embedding =-1)
sage: L1==L2
False
sage: L1.has_coerce_map_from(L2)
True
sage: L2.has_coerce_map_from(L1)
True

So, I think we should make a poll:

(A) Shall I remove the existing bidirectional coercion of number
fields from Sage?

(B) Shall I improve the existing code for bidirectional coercion?
Namely, the following example fails with an error that was reported at
sage-devel or sage-support (don't remember which one, sorry):
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: L1.has_coerce_map_from(L2)
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', (1109, 0))

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', (1109, 0))

...

One of the reasons for the above error is the fact that the pushout of
the codomains of the two embeddings is constructed, but not used in
EmbeddedNumberFieldMorphism in _coerce_map_from_.

Looking forward to a democratic decision...

Simon

[John Cremona]

My vote is not to remove something that's in there and not causing
trouble; and yes, please improve it since you seem quite competent to
do it properly!

John

[David R. Kohel]

Hi,

I would be concerned if in general the determination of an isomorphism
would invoke an expensive computation (before either succeeding or
failing) outside of the user's control.

It might be fast for quadratic fields, for cyclotomic fields (defined
by cyclotomic polynomials). Note that more extensive isomorphism
testing (polynomial factorization) is invoked as well:

sage: P.<x> = PolynomialRing(QQ)
sage: f = x^7 + x + 1
sage: r = [ r[0] for r in f.roots(CC) ]
sage: L1.<r1> = NumberField(f, embedding = r[1])
sage: L2.<r2> = NumberField(f(x+1), embedding = r[1]-1)
sage: L1(r2)
r1 - 1
sage: L2(r1)
r2 + 1
sage: g = f(1/x).numerator()
sage: L3.<r3> = NumberField(g, embedding = 1/r[1])
sage: L3(r1)
-r3^6 - r3^5
sage: L1(r3)
-r1^6 - 1

But if the risks and advantages are well-documented as a feature of
embedded fields, this should not affect number fields without embedding,
hence is harmless if the user doesn't specifically request an embedding.
Assuming there is no impact on unembedded number fields and such are
the default, then I have no objection to leaving this feature.

Does this work for p-adic embeddings as well?

Cheers,

David

[Simon King]

Hi David,

On 29 Nov., 18:26, "David R. Kohel" <ko...@iml.univ-mrs.fr> wrote:
> I would be concerned if in general the determination of an isomorphism
> would invoke an expensive computation (before either succeeding or
> failing) outside of the user's control.  

This is the reason why currently we get "ERROR: An unexpected error
occurred while tokenizing input" in the example above: By oversight,
the ambient field is constructed but not passed as an argument to
EmbeddedNumberFieldMorphism, so that it assumes embedding in CDF,
which takes too long.

> Assuming there is no impact on unembedded number fields and such are
> the default, then I have no objection to leaving this feature.

Yes, EmbeddedNumberFieldMorphism is only invoked (and can only be
invoked) if there is an embedding.

> Does this work for p-adic embeddings as well?

How would one construt a p-adic example? Then I can try (and perhaps
make it another doctest).

Cheers,
Simon

[David Roe]

p-adic embeddings of this kind aren't yet supported in Sage.  I'm writing up an e-mail for sage-padic now with a roadmap toward making such things possible.
David (Roe)

Simon

--
You received this message because you are subscribed to the Google Groups "sage-nt" group.
To post to this group, send an email to sag...@googlegroups.com.
To unsubscribe from this group, send email to sage-nt+u...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/sage-nt?hl=en-GB.

[Robert Bradshaw]

I'm sure that it's not all there, but I was thinking of this when I
wrote the embeddings code:

sage: Q = Qp(5)
sage: K.<a> = NumberField(x^2+1, embedding=Q(-1).sqrt())
sage: a + Q(1)
3 + 5 + 2*5^2 + 5^3 + 3*5^4 + 4*5^5 + 2*5^6 + 3*5^7 + 3*5^9 + 2*5^10 +
2*5^11 + 4*5^13 + 5^14 + 3*5^15 + 2*5^16 + 4*5^17 + 4*5^19 + O(5^20)
sage: a - Q(-1).sqrt()
O(5^20)

- Robert

[Robert Bradshaw]

I'd rather have symmetry breaking when there's a difference, but
otherwise would support there being a coercion in both directions.

> Part 2: Only one number field is embedded
> I think David misunderstood: I did not state that there should be a
> coercion from a non-embedded to an embedded field. The opposite
> coercion (by forgetful functor) should be fine, though. I suppose that
> David and I agree here.

Yep, it's fine if the forgetful functor is applied. Actually, I might
add that I'd probably only want this if the defining polynomials
agree, mapping generator to generator, otherwise an arbitrary choice
would have to be made.

> Part 3: Pushout of two embedded number fields
> Assume that  K1->L1 and K2->L2 are embedded number fields, and assume
> that EmbeddedNumberFieldMorphism(K1,K2,pushout(L1,L2)) returns None.
>
> The first question is:
> Is it possible (i.e., consistent) to define
> pushout(K1,K2):=pushout(L1,L2) ? David says 'no', because
> mathematically the pushout of K1 and K2 should be the minimal sub-
> field of pushout(L1,L2) that contains the images of K1 and K2. I say
> 'yes', because there are canonical (coercion) embeddings of both K1
> and K2 into pushout(L1,L2).
>
> Note that Sage's pushout is not a mathematical pushout, anyway: It
> relies on choices (such as pushout(QQ,ZZ['x'])!=Frac(ZZ['x']) ), but
> that should be fine as long as these choices are computationally
> unique and consistent thorought Sage.
>
> Side question:
> Is it implemented in Sage to find the minimal sub-field of
> pushout(L1,L2) containing the images of K1 and K2?

I think QQbar does this. Perhaps it's not minimal. (Actually, I would
be find with a non-minimal choice if it weren't that much bigger, was
usually minimal, and was significantly cheaper to compute.)

> Second question:
> Assume we agree that it *is* possible to define
> pushout(K1,K2):=pushout(L1,L2): Do we *want* that the sum of two
> number field elements (one from K1, the other from K2) may be an
> element of CDF?

This one is an odd one--my hunch is that I'd rater stay exact. This
can get expensive rather quickly though.

- Robert

[Simon King]

Hi Robert,

On 30 Nov., 05:26, Robert Bradshaw <rober...@math.washington.edu>
wrote:

> > Part 2: Only one number field is embedded
> > I think David misunderstood: I did not state that there should be a
> > coercion from a non-embedded to an embedded field. The opposite
> > coercion (by forgetful functor) should be fine, though. I suppose that
> > David and I agree here.
>
> Yep, it's fine if the forgetful functor is applied. Actually, I might
> add that I'd probably only want this if the defining polynomials
> agree, mapping generator to generator, otherwise an arbitrary choice
> would have to be made.

Sure, that was the idea.

> > Side question:
> > Is it implemented in Sage to find the minimal sub-field of
> > pushout(L1,L2) containing the images of K1 and K2?
>
> I think QQbar does this. Perhaps it's not minimal. (Actually, I would
> be find with a non-minimal choice if it weren't that much bigger, was
> usually minimal, and was significantly cheaper to compute.)

You mean, QQbar has a method that, given some elements, returns a
close-to-minimal subfield containing these elements? How?

> > Assume we agree that it *is* possible to define
> > pushout(K1,K2):=pushout(L1,L2): Do we *want* that the sum of two
> > number field elements (one from K1, the other from K2) may be an
> > element of CDF?
>
> This one is an odd one--my hunch is that I'd rater stay exact. This
> can get expensive rather quickly though.

Of course, the result would be in CDF only if one of the number fields
involved comes with an embedding into CDF. So, I guess by working with
embeddings in exact fields it is possible for the user to stay exact.

Note that the alternative is that arithmetic between K1 and K2 does
not work at all, if one is afraid of using the fields into which they
embed (no threat intended...).

Cheers,
Simon

[David R. Kohel]

Hi,

On Tue, Nov 30, 2010 at 01:28:03AM -0800, Simon King wrote:
> Hi Robert,
>
> On 30 Nov., 05:26, Robert Bradshaw <rober...@math.washington.edu>
> wrote:
> > > Part 2: Only one number field is embedded
> > > I think David misunderstood: I did not state that there should be a
> > > coercion from a non-embedded to an embedded field. The opposite
> > > coercion (by forgetful functor) should be fine, though. I suppose that
> > > David and I agree here.
> >
> > Yep, it's fine if the forgetful functor is applied. Actually, I might
> > add that I'd probably only want this if the defining polynomials
> > agree, mapping generator to generator, otherwise an arbitrary choice
> > would have to be made.
>
> Sure, that was the idea.

This David was me, right?

I still see a potential problem. The forgetful functor would map from
(K,K->F) to K. If K is a "new" object, then there is no problem, since
no choice of isomorphism with an existing object has been made.

But given (K,K->F) and L (containing isomorphic image of K), there is still
an arbitrary choice of embedding K -> L to be made. If now L1 and L2 are
two such fields then can we be sure that (as unembedded number fields) there
can never be any coercion relation between L1 and L2 (which could give rise
to non-commuting coercion diagrams)? If an embedding can only be installed
at creation, then maybe this is impossible.

If Sage doesn't know a relation, a user might intend some relation between
L1 and L2, then automatic coercion could violate the intended relation.

CC.<i> = ComplexField()
L1.<i_1> = NumberField(x^2+1) # intended embedding=+i
L2.<i_2> = NumberField(x^2+1) # intended embedding=-i
H12 = Hom(L1,L2)
h12 = H12(-i_2)
K0.<i_0> = CyclotomicField(4) # embedding=+i

A user might prefer to work with explicit homomorphisms, and get burned by
automatic coercion from some embedded field. Arguably this will involve
a user error in mixing embedded an non-embedded fields, but this could be
very subtle to debug.

Currently no such forgetful coercion exists, right?

However, I find this problematic (in Sage 4.3.1):

sage: CC(i_0)
6.12323399573677e-17 + 1.00000000000000*I
sage: CC(i_1)
1.00000000000000*I
sage: CC(i_2)
1.00000000000000*I

since i_1 and i_2 are not supposed to be embedded.

Cheers,

David

[Simon King]

Hi David,

On 30 Nov., 11:26, "David R. Kohel" <ko...@iml.univ-mrs.fr> wrote:
> > > > Part 2: Only one number field is embedded
> > > > I think David misunderstood: I did not state that there should be a
> > > > coercion from a non-embedded to an embedded field. The opposite
> > > > coercion (by forgetful functor) should be fine, though. I suppose that
> > > > David and I agree here.

> ...

>
> This David was me, right?

Yes.

> I still see a potential problem.  The forgetful functor would map from
> (K,K->F) to K.  If K is a "new" object, then there is no problem, since  
> no choice of isomorphism with an existing object has been made.  
>
> But given (K,K->F) and L (containing isomorphic image of K), there is still
> an arbitrary choice of embedding K -> L to be made.

I don't understand the setting.

Do you say, given some field F, an embedded number field (K,K->F) and
a number field L: Would the "forgetful" approach return a (coercion)
embedding of K into L that may contradict the intentions of the user
(or might contradict an embedding that might be defined later)?

I don't think so. A forgetful coercion would coerce (K,K->F) into K,
but it would not coerce (K,K->F) into some choice of (K,K->L). If K
and L have equal base rings and equal defining polynomial, the
forgetful coercion would send the generator of K to the generator of
L.

But wait. Is your question whether, in the situation just described,
it is possible to provide L with an embedding into F *after* the
forgetful coercion was found? That would indeed be a problem, because
the "forgetful" coercion from K to L would be cached, and the
composition with an "a-posteriori" embedding of L into F would be
different from the original embedding of K into F.

Is that your concern?

I don't know if it can occur. Is it possible to turn a non-embedded
number field into an embedded number field after initialisation?

Certainly the user may choose an embedding L->F (a posteriori) and
then register it as coercion, thus introducing a contradiction in the
system of coercions. But I think that in that case the user would be
to blame, not the automatic coercion system.

> However, I find this problematic (in Sage 4.3.1):
>
> sage: CC(i_0)
> 6.12323399573677e-17 + 1.00000000000000*I
> sage: CC(i_1)
> 1.00000000000000*I
> sage: CC(i_2)
> 1.00000000000000*I
>
> since i_1 and i_2 are not supposed to be embedded.

Sure, but that is conversion, not coercion. AFAIK, conversion has to
coincide with a coercion map, *if* coercion exists. Like here:

sage: K.<i> = NumberField(x^2+1,embedding=-QQbar(I))
sage: CDF(i)
-1.0*I
sage: CC(i)
-1.00000000000000*I

However, since no coercion exists from L1 or L2 to CC, conversion is
just supposed to somehow make sense of i_1 and i_2 in CC. Since it is
possible to "somehow make sense", it would not be appropriate to raise
an exception.

The exception certainly occurs if you try to do arithmetic:
sage: i_1+CC(1)
Traceback (most recent call last):
...
TypeError: unsupported operand parent(s) for '+': 'Number Field in i_1
with defining polynomial x^2 + 1' and 'Complex Field with 53 bits of
precision'

Cheers,
Simon

[Simon King]

Just to clarify:

On 30 Nov., 12:11, Simon King <simon.k...@uni-jena.de> wrote:
> ... A forgetful coercion would coerce (K,K->F) into K,

> but it would not coerce (K,K->F) into some choice of (K,K->L). If K
> and L have equal base rings and equal defining polynomial, the
> forgetful coercion would send the generator of K to the generator of
> L.

There is no contradiction in what I just stated. The forgetful
coercion sends K to L, but it does not send K to (K,K->L).