Should elliptic curves be unique parents?
Simon King
At [http://groups.google.com/group/sage-support/browse_thread/thread/
9a8e887df34a8e9a sage-support], I already mentioned that elliptic
curves inherit from sage.structure.parent.Parent, but they violate the
"unique parent" property:
sage: K = GF(1<<50,'t')
sage: j = K.random_element()
sage: from sage.structure.parent import Parent
sage: isinstance(EllipticCurve(j=j),Parent)
True
sage: EllipticCurve(j=j) is EllipticCurve(j=j)
False
sage: EllipticCurve(j=j) == EllipticCurve(j=j)
True
Before I open a ticket: Do people working with elliptic curves agree
that it is a bug?
I guess the answer depends on how difficult it is to determine whether
two elliptic curves are equal -- I am no expert for elliptic curves,
but from looking at the code, it seems to me that it would be easy to
make elliptic curves unique parents (perhaps using
UniqueRepresentation with a __classcall__ method).
Best regards,
Simon
John Cremona
look like a bug. Elliptic curves were put into Sage very early (long
before I joined in) so it is perhaps not surprising that they do not
fit the current paradigms.
It's easy to check whether two curves are equal: just check that
E1.base_ring() equals E2.base_ring() (these are usually both fields
but can also be rings) and then that E1.a_invariants() =
E2.a_invariants(): these are immutable tuples of 5 elements of the
base_ring.
John
> --
> 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.
>
>
Simon King
On 13 Jun., 23:32, John Cremona <john.crem...@gmail.com> wrote:
> It's easy to check whether two curves are equal: just check that
> E1.base_ring() equals E2.base_ring() (these are usually both fields
> but can also be rings) and then that E1.a_invariants() =
> E2.a_invariants(): these are immutable tuples of 5 elements of the
> base_ring.
And in addition, if I am not mistaken, the a-invariants are computed
during initialisation anyway.
OK, if you agree that it's a bug then I'll open a ticket tomorrow
morning.
Cheer,s
Simon
Simon King
> OK, if you agree that it's a bug then I'll open a ticket tomorrow
> morning.
John Cremona
> Hi John,
>
> On 13 Jun., 23:32, John Cremona <john.crem...@gmail.com> wrote:
>> It's easy to check whether two curves are equal: just check that
>> E1.base_ring() equals E2.base_ring() (these are usually both fields
>> but can also be rings) and then that E1.a_invariants() =
>> E2.a_invariants(): these are immutable tuples of 5 elements of the
>> base_ring.
>
> Yes, that's what I figured from the __cmp__ method of elliptic curves.
> And in addition, if I am not mistaken, the a-invariants are computed
> during initialisation anyway.
>
Correct -- in fact usually the a-invariants are the input parameters
for the constructor.
John
> OK, if you agree that it's a bug then I'll open a ticket tomorrow
> morning.
>
> Cheer,s
> Simon
>
Simon King
On 14 Jun., 09:47, John Cremona <john.crem...@gmail.com> wrote:
> Correct -- in fact usually the a-invariants are the input parameters
> for the constructor.
are quite different ways of providing the data.
My approach is:
A) Let EllipticCurve_generic inherit from UniqueRepresentation. If I
am not mistaken, every other elliptic curve inherits from that, so,
that should be fine.
B) The __init__ methods should be uniform: ALL __init__ methods should
accept precisely one argument, namely an immutable sequence
"ainvs" (in particular, the underlying field can be obtained from
ainvs).
C) By __classcall__ methods, make sure that the existing ways of
constructing an elliptic curve will still work. In particular, it will
create the immutable sequence "ainv".
One detail to consider: Sometimes an elliptic curve is taken from the
Cremona database (see
sage.schemes.elliptic_curves.ell_rational_field). The database
provides certain attributes. It is possible that an elliptic curve
WITH THE SAME A-INVARIANT is already lurking in the cache, ignorant of
the additional attributes. But if I am not mistaken, the classcall
method could very well assign those additional attributes to an
elliptic curve before returning it. So, it should work.
I think the rest of the discussion should be on the ticket.
Cheers,
Simon
Simon King
I have one question about your database.
In ell_rational_field, I see that attributes such as 'rank',
'torsion_order', 'cremona_label', 'conductor', 'modular_degree',
'gens', 'regulator' are taken from your data base. But in
ell_number_field, only the a-invariants are taken from the database.
Are those attributes not contained in your database, for number
fields? Is there a chance that they will ever be? Is it planned to
extend your database by further attributes?
Cheers,
Simon
John Cremona
On Tue, Jun 14, 2011 at 10:25 AM, Simon King <simon...@uni-jena.de> wrote:
> Hi John,
>
> I have one question about your database.
>
> In ell_rational_field, I see that attributes such as 'rank',
> 'torsion_order', 'cremona_label', 'conductor', 'modular_degree',
> 'gens', 'regulator' are taken from your data base. But in
> ell_number_field, only the a-invariants are taken from the database.
My database has no curves over number fields other than Q.
>
> Are those attributes not contained in your database, for number
> fields? Is there a chance that they will ever be? Is it planned to
> extend your database by further attributes?
>
William has a project to make a database for one field, Q(sqrt(5)).
But there will be no large-scale complete databases over general
number fields for a long time.
John
> Cheers,
Simon King
On 14 Jun., 12:01, John Cremona <john.crem...@gmail.com> wrote:
> My database has no curves over number fields other than Q.
Because it says in ell_number_field.py:
if isinstance(y, str):
field = x
X = sage.databases.cremona.CremonaDatabase()[y]
ainvs = Sequence(X.a_invariants(), universe=field,
immutable=True)
else:
field = x
ainvs = Sequence(y, universe=field, immutable=True)
Then, I think I know what to do in order to make them unique parents,
using UniqueRepresentation. I hope I'll have time later today.
Cheers,
Simon
John Cremona
> Hi John,
>
> On 14 Jun., 12:01, John Cremona <john.crem...@gmail.com> wrote:
>> My database has no curves over number fields other than Q.
>
I don't see how the code below could ever be executed.
Note that Elliptic Curves are normally constructed by the top-level
function EllipticCurve(args) -- found in
elliptic_curves/constructor.py -- which works hard to decipher what
the args might mean and then call the appropriate init function of the
appropriate class. If the args are a string then the the string is
assumed to be a label in my database and the following is executed:
if isinstance(x, str):
return ell_rational_field.EllipticCurve_rational_field(x)
so there is never a situation where a string is passed to the
constructor of EllipticCurve_number_field. I guess that might change
in teh future, but as of right now there is no agreed labelling of
elliptic curves by strings except over Q.
I hope this helps.
John
> I see. But the a-invariants can (apparently) be taken from it anyway?
> Because it says in ell_number_field.py:
> if isinstance(y, str):
> field = x
> X = sage.databases.cremona.CremonaDatabase()[y]
> ainvs = Sequence(X.a_invariants(), universe=field,
> immutable=True)
> else:
> field = x
> ainvs = Sequence(y, universe=field, immutable=True)
>
> Then, I think I know what to do in order to make them unique parents,
> using UniqueRepresentation. I hope I'll have time later today.
>
> Cheers,
> Simon
>
Simon King
having unique parents *and* a database has consequences:
Assume that one constructs an elliptic curve (over the rationals) by
its a-invariants. Then, the resulting curve will not know certain
data, for example it will not know its Cremona label:
sage: E = EllipticCurve([0, 1, 1, -2, 0])
sage: hasattr(E,
'_EllipticCurve_rational_field__cremona_label')
False
sage: E
Elliptic Curve defined by y^2 + y = x^3 + x^2 - 2*x over
Rational Field
Having unique parents means: When we pull an elliptic curve out of the
database that is equal to E, then in fact we must return E. I suggest
that in that situation one simply adds to E the information that is
stored in the database.
Hence, with my preliminary patch, one would have:
# elliptic curves are unique
sage: E is EllipticCurve('389a')
True
# Info from the database is added
sage: E._EllipticCurve_rational_field__cremona_label
'389 a 1'
I hope you'll find that behaviour nice (I do!).
Cheers,
Simon
Nils Bruin
> Having unique parents means: When we pull an elliptic curve out of the
> database that is equal to E, then in fact we must return E. I suggest
> that in that situation one simply adds to E the information that is
> stored in the database.
generators cached on them? Then one could construct a curve, find
generators via own computations, look up the curve in the database ...
now what happens to the generators? Are they overwritten with the ones
from the database?
Similarly with minimal models. Are those cached on the curve? Over Q
that's not such an issue but over number fields the minimal models are
far from unique.
Simon King
On 14 Jun., 17:01, Nils Bruin <nbr...@sfu.ca> wrote:
> What if this information is not canonical? Do elliptic curves have
> generators cached on them?
not...).
> Then one could construct a curve, find
> generators via own computations, look up the curve in the database ...
> now what happens to the generators? Are they overwritten with the ones
> from the database?
before submitting it.
But it could be modified.
One could do the following (in the sense of "if you like it, I can
easily implement it"):
If an elliptic curve E is found in the cache and has attached to it
some data that would be overwritten by *different* data from an
elliptic curve F found in the database, then one can have "E is not
F".
Otherwise, (i.e., if the data from the database do not override stuff
that was computed in a different way), one can safely have "E is F".
> Similarly with minimal models. Are those cached on the curve? Over Q
> that's not such an issue but over number fields the minimal models are
> far from unique.
Cheers,
Simon
John Cremona
elliptic curves over Q is not canonical. William and I once tried to
come up with a definition of a canonical basis for the Mordell-Weil
group but got stuck. (We thought of taking a basis which was first in
some lexicographical ordering based on canonical heights; but it's an
unsolved problem to show that if two points P, Q on E have the same
canonical height then there's an automorphism alpha (e.g. [+1] or
[-1]) such that alpha(P)=Q. We asked Silverman and he said this was
out of reach.)
As elliptic curves over Q are currently implemented one would have to
try quite hard to construct a curve with generators which are not the
ones in the database (E.gens() has a parameter use_database which is
True by default). But this *is* possible and we need to deal with it.
Perhaps Simon's suggestion is a good one: E is F is False if E, F are
the same curve (identical a-invariants) but have some other attributes
which disagree then they should be deemed to be different.
John
Simon King
In sage.databases.cremona.CremonaDatabase().__getitem__, I find that
an elliptic curve is created *with the usual elliptic curve
constructor*, and then certain properties are assigned to it, using
_set_cremona_label, _set_rank, _set_torsion_order, _set_conductor,
_set_modular_degree and _set_gens.
I see several ways to proceed:
1) sage.databases.cremona.CremonaDatabase()[N] is not supposed to be
done directly. Hence, it won't hurt if it always returns a new copy of
an elliptic curve. The EllipticCurve constructor can then take care of
uniqueness, namely uniqueness holds unless the database overwrote a
non-canonical attribute.
2) If I am not mistaken, the only non-canonical property set by the
database is in _set_gens. Do you agree? If you do, then one could
modify _set_gens so that it will not override existing generators
unless explicitly requested.
Cheers,
Simon
Simon King
On 14 Jun., 18:12, John Cremona <john.crem...@gmail.com> wrote:
> Perhaps Simon's suggestion is a good one: E is F is False if E, F are
> the same curve (identical a-invariants) but have some other attributes
> which disagree then they should be deemed to be different.
the unique parent condition, but that violation is far less than it is
now.
But before I can submit a patch, I first need to deal with *many*
doctest failures. It seems that some parts of the code rely on non-
unique parents...
Cheers,
Simon
Nils Bruin
> Perhaps Simon's suggestion is a good one: E is F is False if E, F are
> the same curve (identical a-invariants) but have some other attributes
> which disagree then they should be deemed to be different.
creates one curve E with generators and then another one (same a-
invariants) F without. Now they are not equal. Next you compute (the
same) generators of F now E and F are equal, plus they are not unique
parents anymore. That clearly violates immutability.
It looks to me that elliptic curves have too many things hanging off
them to consider them immutable. Mutables don't have to be unique (in
fact, it's confusing if they were). Having them mutable would of
course make them unhashable, which is really inconvenient. Perhaps if
the a-invariants are not allowed (or at least supposed) to change and
the hash is simply the hash of the a-invariants, would that be
workable?
Simon King
On 14 Jun., 19:43, Nils Bruin <nbr...@sfu.ca> wrote:
> On Jun 14, 9:12 am, John Cremona <john.crem...@gmail.com> wrote:
>
> > Perhaps Simon's suggestion is a good one: E is F is False if E, F are
> > the same curve (identical a-invariants) but have some other attributes
> > which disagree then they should be deemed to be different.
>
> But then the mutability of E and F become a real issue. Suppose one
> creates one curve E with generators and then another one (same a-
> invariants) F without. Now they are not equal.
if and only if the base rings are equal and the a-invariants are
equal.
But in the situation you describe, one would have "E is not F and
E==F". Currently, that happens all the time with elliptic curves.
The purpose of #11474 is to have "E is not F and E==F" ONLY when E is
defined directly, with custom generators, and F is taken from the
database, with the generators found there.
Cheers,
Simon
Nils Bruin
canonical info cached on elliptic curves, can we get away with
considering elliptic curves immutable? (when they are mutable, the
system should definitely not try to make them unique)
As an example, take the elliptic curve
E=EllipticCurve( [1000300025/2, -800300027/2])
A 2-isogeny descent easily shows this curves is of rank at most 2 and
there are two points (with x-coordinates 1,-1) that are independent
(and a few simple saturation computations should easily determine a
full set of generators for the MW-group).
Calling E.rank() takes longer than I have waited for.
Examples like this indicate to me that determining MW-groups of
elliptic curves will be a fairly interactive process for a while. If
generators are "part of" the elliptic curve, then finding them and
registering them really mutates the elliptic curve (even if it doesn't
affect equality).
One alternative is to encode computations with MW-groups in terms of
homomorphisms between abstract abelian groups and the point-set E(QQ).
Then the MW-group is not really a "part" of the elliptic curve (or at
least not its representation wrt. generators).
Simon King
On 15 Jun., 03:58, Nils Bruin <nbr...@sfu.ca> wrote:
> OK, the thing that makes me feel uneasy then is probably that with non-
> canonical info cached on elliptic curves, can we get away with
> considering elliptic curves immutable? (when they are mutable, the
> system should definitely not try to make them unique)
John, you said originally "It [elliptic curves as non-unique parent
structures] does definitely look like a bug."
Has Nils convinced you that it is no bug, after all? If he did, then
#11474 should get a review suggesting that its resolution is
"wontfix".
Cheers,
Simon
John Cremona
this through very carefully.
I very much like Nils's (very Magma-like) idea to have the
Mordell-Weil group of the curve as a separate object which is an
abstract abelian group with a map to the point-set. It used to be the
case that the abelian group infrastructure was not good enough to make
that work at all pleasantly, but now I think it is. In fact we
already have something like this for the torsion subgroup:
sage: E = EllipticCurve('14a1')
sage: T = E.torsion_subgroup()
sage: type(T)
<class 'sage.schemes.elliptic_curves.ell_torsion.EllipticCurveTorsionSubgroup_with_category'>
sage: T.order()
6
sage: T.invariants()
(6,)
sage: T.addition_table()
+ a b c d e f
+------------
a| a b c d e f
b| b c d e f a
c| c d e f a b
d| d e f a b c
e| e f a b c d
f| f a b c d e
and for the group of points over finite fields:
sage: E = EllipticCurve(GF(11),[2,2])
sage: A = E.abelian_group()
sage: A.invariants()
(9,)
sage: A.list()
[(0 : 1 : 0), (1 : 4 : 1), (2 : 5 : 1), (9 : 10 : 1), (5 : 4 : 1), (5
: 7 : 1), (9 : 1 : 1), (2 : 6 : 1), (1 : 7 : 1)]
but it is only "something like" since the abstract group "knows" that
its elements are "really" points on the curve, without having to
explicitly map them to the curve as in Magma.
John
David Harvey
On Jun 15, 2011, at 5:34 AM, John Cremona wrote:
> Nils always convinces me, and I have been too busy recently to think
> this through very carefully.
>
> I very much like Nils's (very Magma-like) idea to have the
> Mordell-Weil group of the curve as a separate object which is an
> abstract abelian group with a map to the point-set.
YES.
david
Simon King
On 15 Jun., 11:34, John Cremona <john.crem...@gmail.com> wrote:
> I very much like Nils's (very Magma-like) idea to have the
> Mordell-Weil group of the curve as a separate object which is an
> abstract abelian group with a map to the point-set.
Let E be an elliptic curve over a number field K.
Current behaviour is that E.gens() (if it succeeds) returns generators
for the Mordell-Weil group of E, i.e., the K-rational points on E. One
may want to work with different generating sets, and they may change
over time, and the choice of generators has a big impact on various
algorithms. Therefore my idea of turning E into a unique parent (and
thus caching gens()) is a bad idea.
However, a cleaner (or Magma-like) approach would be to distinguish
between the elliptic curve and the Mordell-Weil group. Hence, E.gens()
should be eliminated, and there should be a new method
E.mordell_weil() returning the Mordell-Weil group MW of E. MW should
be an abstract group, but with the possibility to simultaneously
define several sets of generators.
Then, E could indeed be a unique parent structure (namely E is F if
and only if E==F if and only if E.base_ring()==F.base_ring() and
E.ainvs()==F.ainvs()). And for the Mordell-Weil group, some
infrastructure from the combinat folks should be applied, since they
can deal with abstract objects that simultaneously have different
bases or sets of generators, IIRC.
But what does that make of #11474? Should it be closed? Should I add
my patch (making E unique), although it leaves a lot of doctest
failures?
Cheers,
Simon
John Cremona
> Hi John, dear David,
>
> On 15 Jun., 11:34, John Cremona <john.crem...@gmail.com> wrote:
>> I very much like Nils's (very Magma-like) idea to have the
>> Mordell-Weil group of the curve as a separate object which is an
>> abstract abelian group with a map to the point-set.
>
> Do I understand correctly:
Pretty much. Though it's not really like (say) for vector spaces and
modules where one might choose to use different generating sets for
different reasons; it's more that finding both the abstract group
structure and any set of generators is pretty hard! That's one reason
why the database has generators, to save the (sometimes great) time
needed to find them. In fact, even over Q there is no algorithm
known even in principal, let alone implemented, which is guaranteed to
always find generators. (The "even in principle" above is related to
unsolved problems surrounding the Birch & Swinnerton-Dyer conjectures,
such as the finiteness of the Tate-Shafarevich group).
For this reason there are times when (say) one cannot prove that the
rank is 1, only that it is either 1 or 3, and one has 1 generator, and
want to store that; or you may know that the rank is at most 2, but
only have one generator, suspect that there is a second one (whose
very existence is based on BSD!) but cannot find it. And so on.
That's the way elliptic curves work....
By the way, all the above is only relevant for elliptic curves over
number fields (including Q) [and other global fields but there's
nothing in Sage about other sorts yet) so the right place to attach a
MordellWeilGroup structure would be to elliptic_curve_number_field.
>
> Let E be an elliptic curve over a number field K.
> Current behaviour is that E.gens() (if it succeeds) returns generators
> for the Mordell-Weil group of E, i.e., the K-rational points on E. One
> may want to work with different generating sets, and they may change
> over time, and the choice of generators has a big impact on various
> algorithms. Therefore my idea of turning E into a unique parent (and
> thus caching gens()) is a bad idea.
>
> However, a cleaner (or Magma-like) approach would be to distinguish
> between the elliptic curve and the Mordell-Weil group. Hence, E.gens()
> should be eliminated, and there should be a new method
> E.mordell_weil() returning the Mordell-Weil group MW of E. MW should
> be an abstract group, but with the possibility to simultaneously
> define several sets of generators.
>
> Then, E could indeed be a unique parent structure (namely E is F if
> and only if E==F if and only if E.base_ring()==F.base_ring() and
> E.ainvs()==F.ainvs()). And for the Mordell-Weil group, some
> infrastructure from the combinat folks should be applied, since they
> can deal with abstract objects that simultaneously have different
> bases or sets of generators, IIRC.
>
> But what does that make of #11474? Should it be closed? Should I add
> my patch (making E unique), although it leaves a lot of doctest
> failures?
I'll have to take a look at that; I don't know what sort of failures tehre are.
John
>
> Cheers,
> Simon
Simon King
> I'll have to take a look at that; I don't know what sort of failures tehre are.
doctest log.
Cheers,
Simon