# Should elliptic curves be unique parents?

25 views

### Simon King

Jun 13, 2011, 3:42:50 PM6/13/11
to sage-nt
Hi!

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

Jun 13, 2011, 5:32:03 PM6/13/11
Sorry I have not been able to respond earlier. It does definitely
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

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

Jun 13, 2011, 6:31:47 PM6/13/11
to sage-nt
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.

OK, if you agree that it's a bug then I'll open a ticket tomorrow
morning.

Cheer,s
Simon

### Simon King

Jun 14, 2011, 2:43:46 AM6/14/11
to sage-nt
On 14 Jun., 00:31, Simon King <simon.k...@uni-jena.de> wrote:
> OK, if you agree that it's a bug then I'll open a ticket tomorrow
> morning.

It is #11474

### John Cremona

Jun 14, 2011, 3:47:41 AM6/14/11
On Mon, Jun 13, 2011 at 11:31 PM, Simon King <simon...@uni-jena.de> wrote:
> 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

Jun 14, 2011, 4:58:59 AM6/14/11
to sage-nt
Hi John,

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.

I am just working on the code, and I am afraid that quite often there
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

Jun 14, 2011, 5:25:08 AM6/14/11
to sage-nt
Hi John,

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

Jun 14, 2011, 6:01:17 AM6/14/11
Not much time right now...

On Tue, Jun 14, 2011 at 10:25 AM, Simon King <simon...@uni-jena.de> wrote:
> Hi John,
>
>
> 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

Jun 14, 2011, 8:02:37 AM6/14/11
to sage-nt
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 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
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

Jun 14, 2011, 8:11:00 AM6/14/11
On Tue, Jun 14, 2011 at 1:02 PM, Simon King <simon...@uni-jena.de> wrote:
> 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
>                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

Jun 14, 2011, 10:34:11 AM6/14/11
to sage-nt
Hi all,

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

Jun 14, 2011, 11:01:54 AM6/14/11
to sage-nt
On Jun 14, 7:34 am, Simon King <simon.k...@uni-jena.de> wrote:

> 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.

What if this information is not canonical? Do elliptic curves have
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

Jun 14, 2011, 11:22:14 AM6/14/11
to sage-nt
Hi Nils,

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?

That question is addressed to the number theorists on this list (I am
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?

With my current patch, yes. And that's essentially why I ask here
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.

But, as John said, the database is over Q only.

Cheers,
Simon

### John Cremona

Jun 14, 2011, 12:12:53 PM6/14/11
Nils is quite right, that some of the database info stored for
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

Jun 14, 2011, 1:18:50 PM6/14/11
to sage-nt
Hi!

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

Jun 14, 2011, 12:35:57 PM6/14/11
to sage-nt
Hi John,

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.

OK, then I'll try it in that way: There would still be a violation of
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

Jun 14, 2011, 1:43:47 PM6/14/11
to sage-nt
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. 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

Jun 14, 2011, 1:53:07 PM6/14/11
to sage-nt

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.

No, they ARE equal. Elliptic curves (that is the status quo) are 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

Jun 14, 2011, 9:58:53 PM6/14/11
to sage-nt
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)

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

Jun 15, 2011, 2:11:57 AM6/15/11
to sage-nt
Hi Nils, hi John,

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)

That somehow sounds convincing to me (but IANANT).

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

Jun 15, 2011, 5:34:21 AM6/15/11
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. 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,)
+ 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

Jun 15, 2011, 6:27:49 AM6/15/11

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

Jun 15, 2011, 7:05:39 AM6/15/11
to sage-nt
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:

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

Jun 15, 2011, 7:46:42 AM6/15/11
On Wed, Jun 15, 2011 at 12:05 PM, Simon King <simon...@uni-jena.de> wrote:
> 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

Jun 15, 2011, 9:34:29 AM6/15/11
to sage-nt
On 15 Jun., 13:46, John Cremona <john.crem...@gmail.com> wrote:
> I'll have to take a look at that;  I don't know what sort of failures tehre are.

FWIW: I posted my preliminary patch to the ticket, together with the
doctest log.

Cheers,
Simon