[sage-devel] Re: Finite fields coercion bug

2016-10-14 Thread Peter Bruin 
Hello,

Kwankyu Lee wrote:

> On Thursday, October 13, 2016 at 9:59:50 PM UTC+2, David Roe wrote:
>
>   In order to create finite fields with arbitrary variable names that fit
>   into a lattice of fields, one possibility would be able to give an
>   algebraic closure explicitly as an argument to GF.  Is that what you're
>   suggesting?
>   sage: F = GF(3).algebraic_closure('custom')
>   sage: K9 = GF(9,'b',Fpbar=F)
>   sage: K81 = GF(81,'c',Fpbar=F)
>   sage: K81.has_coerce_map_from(K9)
>   True
>
> This currently works 
> sage: K9 = GF(9,'b',prefix='custom')
> sage: K81 = GF(81,'c',prefix='custom')
> sage: K81.has_coerce_map_from(K9)
> True
> But the following betrays my expectation..
> sage: K=GF(3).algebraic_closure('custom')
> sage: K81.gen() in K
> False
> sage: K.has_coerce_map_from(K81)
> False

One reason why this doesn't work is that you gave the custom variable
names 'b' and 'c' to K9 and K81.  However, even when you omit this, it
doesn't work, which I think is a bug.

It is also possible to first construct the algebraic closure of F_p and
then construct other finite fields as subfields of this:

sage: K = GF(3).algebraic_closure('custom')
sage: K9, i9 = K.subfield(2)
sage: K.has_coerce_map_from(K9)
True

However, there is a similar problem here:

sage: K81, i81 = K.subfield(4)
sage: K81.has_coerce_map_from(K9)
False

This should return True.

Peter

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: Finite fields coercion bug

2016-10-14 Thread Kwankyu Lee 
On Thursday, October 13, 2016 at 9:59:50 PM UTC+2, David Roe wrote:
>
>
> In order to create finite fields with arbitrary variable names that fit 
> into a lattice of fields, one possibility would be able to give an 
> algebraic closure explicitly as an argument to GF.  Is that what you're 
> suggesting?
> sage: F = GF(3).algebraic_closure('custom')
> sage: K9 = GF(9,'b',Fpbar=F)
> sage: K81 = GF(81,'c',Fpbar=F)
> sage: K81.has_coerce_map_from(K9)
> True
>

This currently works 

sage: K9 = GF(9,'b',prefix='custom')
sage: K81 = GF(81,'c',prefix='custom')
sage: K81.has_coerce_map_from(K9)
True

But the following betrays my expectation..

sage: K=GF(3).algebraic_closure('custom')
sage: K81.gen() in K
False
sage: K.has_coerce_map_from(K81)
False

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: Finite fields coercion bug

2016-10-13 Thread Nils Bruin 
On Thursday, October 13, 2016 at 12:16:36 PM UTC-7, John Cremona wrote:
>
> Kwankyu's point is also a good one.  It really is not acceptable (from 
> a user's point of view) to ask if there any coercions, be told there 
> are none, and then be prevented from defining one! 
>

It's a necessity for sanity, though: These parents are global objects, so 
they should be immutable in their behaviour. Once it has been decided there 
is no coercion to some existing object, it cannot happen that later on, 
such a coercion is available. That's observably mutated behaviour. It can 
also cause inconsistencies in the coercion discovery: the fact that a 
coercion was NOT found can have forced the construction and caching of a 
coercion elsewhere. This could be inconsistent with later discoveries if 
there is now a coercion found.

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: Finite fields coercion bug

2016-10-13 Thread David Roe 
On Thu, Oct 13, 2016 at 5:09 PM, Kwankyu Lee  wrote:

> Hi David,
>
> First, thank you for technical explanations. They are compelling.
>
> On Thursday, October 13, 2016 at 9:59:50 PM UTC+2, David Roe wrote:
>>
>>
>> In order to create finite fields with arbitrary variable names that fit
>> into a lattice of fields, one possibility would be able to give an
>> algebraic closure explicitly as an argument to GF.  Is that what you're
>> suggesting?
>> sage: F = GF(3).algebraic_closure('custom')
>> sage: K9 = GF(9,'b',Fpbar=F)
>> sage: K81 = GF(81,'c',Fpbar=F)
>> sage: K81.has_coerce_map_from(K9)
>> True
>>
>
> Still speaking from a user's point of view, is there also a technical
> difficulty in keeping just one lattice of fields? So a new creation of a
> finite field gets automatically fitted into the canonical lattice?
>

You want to be able to create finite fields that don't fit into the
lattice, because as the degree increases it becomes very expensive to
compute polynomials that are compatible with the other extensions that
you've already constructed.  In contrast, constructing a finite field using
a random polynomial is relatively cheap.  Currently, Sage uses the presence
or absence of a specified variable name to determine whether you want a
field that fits into this lattice or not.

One application for having multiple lattices is to support algebraic
closures for non-prime fields (which is not yet implemented in Sage).
David

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: Finite fields coercion bug

2016-10-13 Thread Kwankyu Lee 
Hi David,

First, thank you for technical explanations. They are compelling.

On Thursday, October 13, 2016 at 9:59:50 PM UTC+2, David Roe wrote:
>
>
> In order to create finite fields with arbitrary variable names that fit 
> into a lattice of fields, one possibility would be able to give an 
> algebraic closure explicitly as an argument to GF.  Is that what you're 
> suggesting?
> sage: F = GF(3).algebraic_closure('custom')
> sage: K9 = GF(9,'b',Fpbar=F)
> sage: K81 = GF(81,'c',Fpbar=F)
> sage: K81.has_coerce_map_from(K9)
> True
>

Still speaking from a user's point of view, is there also a technical 
difficulty in keeping just one lattice of fields? So a new creation of a 
finite field gets automatically fitted into the canonical lattice? 

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: Finite fields coercion bug

2016-10-13 Thread David Roe 
On Thu, Oct 13, 2016 at 3:16 PM, John Cremona 
wrote:

> Thanks Peter for the explanation.  Nevertheless, I'm not sure that the
> normal user could have guess that one only gets the clever stuff
> (compatible embeddings into the algebraci closure.  The docstring GF?
> does imply this but again does not make a big thing of it.
>
> I think a better design (just of the user interface) would be to
> separate these two things: (i) whether or not you want the field being
> constructed to be part of the potentially costly lattice of fields,
> and (ii) whether or not you want to pick your own name.
>

In order to create finite fields with arbitrary variable names that fit
into a lattice of fields, one possibility would be able to give an
algebraic closure explicitly as an argument to GF.  Is that what you're
suggesting?
sage: F = GF(3).algebraic_closure('custom')
sage: K9 = GF(9,'b',Fpbar=F)
sage: K81 = GF(81,'c',Fpbar=F)
sage: K81.has_coerce_map_from(K9)
True

This would be pretty easy to implement (feel free to suggest a name for the
keyword other than 'Fpbar').


> Kwankyu's point is also a good one.  It really is not acceptable (from
> a user's point of view) to ask if there any coercions, be told there
> are none, and then be prevented from defining one!
>

This is much tougher, for technical reasons (I agree that it's not ideal
from a user's perspective).  Suppose that you're trying to determine
whether there's a coercion from A to B.  You know that there's a coercion
from C to B, so you check to see if there's a coercion from A to C,
discovering that there isn't.  After searching for a bit, you determine
that none of the ideas for constructing a coercion from A to C worked out,
so there isn't a coercion.  In order to forgo this search every time a
coercion from A to B is requested, you cache the result: there is no
coercion A to B and no coercion A to C.  These caches are stored on B and C.

Now suppose that the user wants to add a coercion from A to C.  If you
allowed this, then the coercion diagram becomes inconsistent, since this
coercion should have implied a coercion from A to B.  But there's no easy
way to update the cache on B, since it's not stored on A or C.  Sage's
solution is to not allow registering coercions A to B once it has used the
fact that there is no coercion.

Now, it's possible that one could restructure the system to make this
possible.  But it wouldn't be easy, and may involve other costs.  If you
have suggestions on how to update the documentation to make the issues
clearer, that's another matter.  :-)
David

>
> Meanwhile, now we know what is going on we can work round it (here we
> is me + my student Marco Caselli, who came to me saying that  it
> appeared to be impossible to iterate over a finite field if it was
> constructed as an extension of another -- which is true if you
> construct things in a perfectly innocent way without realising what is
> happening behind the scenes).
>
> John
>
> On 13 October 2016 at 18:25, Kwankyu Lee  wrote:
> > Hi,
> >
> > On Thursday, October 13, 2016 at 7:14:27 PM UTC+2, Peter Bruin wrote:
> >>
> >> Even though there is no coercion map in this situation, simply trying to
> >> discover a coercion "taints" the target parent by registering the fact
> >> that there is no coercion.
> >
> >
> > Then should we consider this behavior as a bug? There is a coercion rule
> > that there can be at most one coercion from a parent to another parent,
> but
> > it should not be disallowed to register one when there is none yet.
> Right?
> >
> > --
> > You received this message because you are subscribed to the Google Groups
> > "sage-devel" group.
> > To unsubscribe from this group and stop receiving emails from it, send an
> > email to sage-devel+unsubscr...@googlegroups.com.
> > To post to this group, send email to sage-devel@googlegroups.com.
> > Visit this group at https://groups.google.com/group/sage-devel.
> > For more options, visit https://groups.google.com/d/optout.
>
> --
> You received this message because you are subscribed to the Google Groups
> "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sage-devel+unsubscr...@googlegroups.com.
> To post to this group, send email to sage-devel@googlegroups.com.
> Visit this group at https://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/d/optout.
>

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: Finite fields coercion bug

2016-10-13 Thread John Cremona 
Thanks Peter for the explanation.  Nevertheless, I'm not sure that the
normal user could have guess that one only gets the clever stuff
(compatible embeddings into the algebraci closure.  The docstring GF?
does imply this but again does not make a big thing of it.

I think a better design (just of the user interface) would be to
separate these two things: (i) whether or not you want the field being
constructed to be part of the potentially costly lattice of fields,
and (ii) whether or not you want to pick your own name.

Kwankyu's point is also a good one.  It really is not acceptable (from
a user's point of view) to ask if there any coercions, be told there
are none, and then be prevented from defining one!

Meanwhile, now we know what is going on we can work round it (here we
is me + my student Marco Caselli, who came to me saying that  it
appeared to be impossible to iterate over a finite field if it was
constructed as an extension of another -- which is true if you
construct things in a perfectly innocent way without realising what is
happening behind the scenes).

John

On 13 October 2016 at 18:25, Kwankyu Lee  wrote:
> Hi,
>
> On Thursday, October 13, 2016 at 7:14:27 PM UTC+2, Peter Bruin wrote:
>>
>> Even though there is no coercion map in this situation, simply trying to
>> discover a coercion "taints" the target parent by registering the fact
>> that there is no coercion.
>
>
> Then should we consider this behavior as a bug? There is a coercion rule
> that there can be at most one coercion from a parent to another parent, but
> it should not be disallowed to register one when there is none yet. Right?
>
> --
> You received this message because you are subscribed to the Google Groups
> "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sage-devel+unsubscr...@googlegroups.com.
> To post to this group, send email to sage-devel@googlegroups.com.
> Visit this group at https://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/d/optout.

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] Re: Finite fields coercion bug

2016-10-13 Thread Kwankyu Lee 
Hi,

On Thursday, October 13, 2016 at 7:14:27 PM UTC+2, Peter Bruin wrote:
>
> Even though there is no coercion map in this situation, simply trying to 
> discover a coercion "taints" the target parent by registering the fact 
> that there is no coercion.


Then should we consider this behavior as a bug? There is a coercion rule 
that there can be at most one coercion from a parent to another parent, but 
it should not be disallowed to register one when there is none yet. Right?

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] Re: Finite fields coercion bug

2016-10-13 Thread Peter Bruin 
Hello John,

> I think this is a bug.  In one Sage session:
>
> sage: F4 = GF(4)
> sage: F16 = GF(16)
> sage: F4.gen() in F16
> True
> sage: F16.has_coerce_map_from(F4)
> True
>
> -- all is well.  But in a new session:
>
> sage: F4 = GF(4, names='a')
> sage: F16 = GF(16, names='b')
> sage: F4.gen() in F16
> False
> sage: F16.has_coerce_map_from(F4)
> False
>
> Why should the fact that I have given non-default names to the
> generators (the default names are z2 and z4) stop the coercion being
> dicovered?

Creating finite fields without a variable name was implemented in
.  If you don't specify a
variable, then the field is created as a subfield of an algebraic
closure, and there are canonical inclusions between such fields.
Otherwise, the finite field does not have such a distinguished
embedding.

By the way, creating finite fields without a variable name is something
that you should only do for small fields, because constructing an
algebraic closure requires computing (pseudo-)Conway polynomials.

> Worse than that, I tried to create my own coercion from F4 to F16 in
> the second situation and it prevented me from doing so, saying there
> already was one, while at the same time telling me there was no
> coercion.  Inconsistent!

Even though there is no coercion map in this situation, simply trying to
discover a coercion "taints" the target parent by registering the fact
that there is no coercion.  It does work if you don't call
has_coerce_map() first:

sage: F4 = GF(4, names='a')
sage: F16 = GF(16, names='b')
sage: f = F4.Hom(F16)[0]
sage: F16.register_coercion(f)

You can't rely on this to work, though, because it can fail if F16 was
already created in this Sage session.

Peter

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.