Opened 3 years ago

Closed 2 months ago

#11474 closed defect (fixed)

Elliptic curves should be unique parent structures

Reported by: SimonKing Owned by: cremona
Priority: major Milestone: sage-6.3
Component: elliptic curves Keywords: unique parent
Cc: cremona, defeo, sbesnier, jpflori Merged in:
Authors: Peter Bruin Reviewers: Volker Braun
Report Upstream: N/A Work issues:
Branch: f7f3755 (Commits) Commit: f7f37555460bcf62c657cba260f7151a9d5c6576
Dependencies: #10665, #16317 Stopgaps:

Description (last modified by SimonKing)

While elliptic curves are derived from sage.structure.parent.Parent, they violate the "unique parent" condition:

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 

Some people on sage-nt originally agreed that it is a bug. Other people think it isn't...

Attachments (2)

trac11474_unique_elliptic_curves.patch (24.4 KB) - added by SimonKing 3 years ago.
Make elliptic curves unique parents -- doesn't work yet
test11474.log (234.2 KB) - added by SimonKing 3 years ago.
doctest log

Download all attachments as: .zip

Change History (45)

comment:1 Changed 3 years ago by SimonKing

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 in the cache, ignorant of the additional attributes.

But the classcall method could very well assign those additional attributes to an elliptic curve found in the cache before returning it. So, it should still work.

comment:2 Changed 3 years ago by SimonKing

Or should perhaps ProjectiveCurve_generic already be a unique parent? That's what elliptic curves derive from. Or even AlgebraicScheme_subscheme? How far should one go?

comment:3 Changed 3 years ago by SimonKing

  • Description modified (diff)

Changed 3 years ago by SimonKing

Make elliptic curves unique parents -- doesn't work yet

Changed 3 years ago by SimonKing

doctest log

comment:4 Changed 3 years ago by SimonKing

  • Authors set to Simon King
  • Status changed from new to needs_info

The discussion on sage-nt shows that it is even not clear whether we want elliptic curves to be unique parents (yet).

Anyway, I posted a preliminary patch. There are some doctest failures -- a test log is attached as well.

Some of the errors are easy to understand: Previously, one had a "Generic morphism", but with unique parents one has a "Generic endomorphism". Others seem more tricky. For example one gets

sage -t  devel/sage/sage/schemes/elliptic_curves/ell_field.py
// ** nInitExp failed: using Z/2^2
**********************************************************************
File "/mnt/local/king/SAGE/sage-4.7.rc2/devel/sage-main/sage/schemes/elliptic_curves/ell_field.py", line 1038
:
    sage: E.weierstrass_p(prec=8, algorithm='pari')
Exception raised:
    Traceback (most recent call last):
      File "/mnt/local/king/SAGE/sage-4.7.rc2/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/mnt/local/king/SAGE/sage-4.7.rc2/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/mnt/local/king/SAGE/sage-4.7.rc2/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_14[7]>", line 1, in <module>
        E.weierstrass_p(prec=Integer(8), algorithm='pari')###line 1038:
    sage: E.weierstrass_p(prec=8, algorithm='pari')
      File "/mnt/local/king/SAGE/sage-4.7.rc2/local/lib/python/site-packages/sage/schemes/elliptic_curves/ell
_field.py", line 1064, in weierstrass_p
        return weierstrass_p(self, prec=prec, algorithm=algorithm)
      File "/mnt/local/king/SAGE/sage-4.7.rc2/local/lib/python/site-packages/sage/schemes/elliptic_curves/ell_wp.py", line 141, in weierstrass_p
        wp = compute_wp_pari(E, prec)
      File "/mnt/local/king/SAGE/sage-4.7.rc2/local/lib/python/site-packages/sage/schemes/elliptic_curves/ell_wp.py", line 168, in compute_wp_pari
        wpp = ep.ellwp(n=prec)
    AttributeError: 'dict' object has no attribute 'ellwp'

Hence, first there is a (warning or error?) message "// ** nInitExp failed: using Z/2^2", and then something is a dict that ought to be a completely different object.

On the bright side, one has the following.

Elliptic curves are unique, even when they are created in different ways:

sage: E = EllipticCurve('5077a'); E
Elliptic Curve defined by y^2 + y = x^3 - 7*x + 6 over Rational Field
sage: E is EllipticCurve('5077a') is EllipticCurve(QQ, E.a_invariants()) is EllipticCurve(j = E.j_invariant())
True

If an elliptic curve is provided with some custom attribute and the "same" curve is found in the database with different attributes, then one has no uniqueness of parents; this is in order to prevent the database from overriding stuff that the user has computed:

sage: E = EllipticCurve([0, 1, 1, -2, 0])
sage: E is EllipticCurve('389a')
True
sage: E._EllipticCurve_rational_field__cremona_label = 'bogus'
sage: E is EllipticCurve('389a')
False
sage: E.label()
'bogus'
sage: EllipticCurve('389a').label()
'389a1'

However, if the custom attribute is removed, then the data from the database are used to provide a value for that attribute:

sage: del E._EllipticCurve_rational_field__cremona_label
sage: E is EllipticCurve('389a') # uniqueness of parents again
True
# The label has implicitly been updated
sage: E._EllipticCurve_rational_field__cremona_label
'389 a 1'

comment:5 Changed 14 months ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:6 Changed 8 months ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:7 Changed 6 months ago by pbruin

  • Cc cremona added

I think this would still be good to fix. The consensus seems to be that an EllipticCurve object should be defined uniquely by its base ring and the coefficients ai, and nothing else. The datum consisting of the base ring and the Weierstrass coefficients is "enough" in the sense that if these are identical for two given elliptic curves, then there is a canonical isomorphism between them.

However, in the sage-nt discussion linked to above, there was some discussion about situations like the following. The user creates an elliptic curve E (say over Q) without using Cremona's database, and computes generators for its Mordell-Weil group. Now he later tries to load the same curve from the database, but the generators don't agree. Should the two curves be identical or not?

Intuitively, I would say they should be identical; the fact that there is no canonical basis for the MW group does not justify breaking the unique parents convention (equality of parents, as determined by some defining data, implies identity).

On the question of whether the generators from the database should override the ones computed by the user, I think the answer is no. The database provides a convenient way to avoid a possibly long computation, but the basis returned by it has no mathematical property that makes it preferred over any other one.

Compare to NumberField: it seems strange to call two number fields non-identical if they agree in all respects except that different bases for the unit group have been computed. (Actually, NumberField may be a bad example because the current implementation also uses various other parameters to decide whether to construct a new instance. The point is that it does not take any basis for the unit group into account.)

comment:8 follow-up: Changed 6 months ago by pbruin

There is also the related question on whether an elliptic curve E itself or the Abelian group of rational points of E should be regarded as the parent of the rational points of E. Same question for the (co)domain of isogenies; see #12880.

comment:9 Changed 5 months ago by defeo

  • Cc defeo sbesnier added

comment:10 in reply to: ↑ 8 Changed 5 months ago by defeo

Replying to pbruin:

There is also the related question on whether an elliptic curve E itself or the Abelian group of rational points of E should be regarded as the parent of the rational points of E. Same question for the (co)domain of isogenies; see #12880.

What happened to the idea of having the MW group as an object different from the elliptic curve? Possibly attaching different representations of it to the same curve? The sage-nt discussion mentions it, but I don't see any trace of it in the patch.

I really like the idea, as I like the general idea of having the Abelian group of (rational?) points as a separate object.

Sébastien (cc-ed) is working on this (and the related questions with isogenies) for its masters' thesis. If there is a consensus on having a separate object for the Abelian group, I think he will be happy (or at least his advisor will :) to do it and finalize this ticket.

comment:11 follow-up: Changed 5 months ago by cremona

I also like the idea of having a separate object for the group of points. Then for an elliptic curve E defined over K one could have different point groups for E(K) and for E(L) for extensions L of K. Magma did that a few years ago and it was very convenient. I have not thought at all about how to implement it though.

About isogeny (c)domains it is not so clear to me. An isogeny is both a map from one curve to another (preserving the base point), and also a group homomorphism. If we are going to separate out the curve E from its group(s) E(K), E(L), then should we not keep these separate for isogenies too?

comment:12 in reply to: ↑ 11 Changed 5 months ago by pbruin

Replying to cremona:

I also like the idea of having a separate object for the group of points. Then for an elliptic curve E defined over K one could have different point groups for E(K) and for E(L) for extensions L of K. Magma did that a few years ago and it was very convenient. I have not thought at all about how to implement it though.

There is already a very basic class in sage.schemes.projective_homset; you can do

sage: E=EllipticCurve('37a1')
sage: K.<a>=QuadraticField(57)
sage: E(K)
Abelian group of points on Elliptic Curve defined by y^2 + y = x^3 + (-1)*x over Number Field in a with defining polynomial x^2 - 57
sage: type(E(K))
<class 'sage.schemes.projective.projective_homset.SchemeHomset_points_abelian_variety_field_with_category'>
sage: P=(0,0)
sage: E(P) == E(QQ)(P)
True

We could create a subclass of SchemeHomset_points_abelian_variety for groups of points of elliptic curves, and then separate subclasses of that for different base fields (rationals, general number fields, finite fields, maybe the complex field, etc.) Then we could start moving functionality so that E.rank() is defined as E.group_of_points(E.base_field()).rank(), etc.

(In the above example it looks as if E(K) is interpreted as the group of K-points of E.base_extend(K) rather than as the group of K-points of E, but this could probably be changed.)

About isogeny (c)domains it is not so clear to me. An isogeny is both a map from one curve to another (preserving the base point), and also a group homomorphism. If we are going to separate out the curve E from its group(s) E(K), E(L), then should we not keep these separate for isogenies too?

Yes, I think we should. To rephrase your point, an isogeny is a map f: E -> E' between elliptic curves over a field K (preserving 0), and induces group homomorphisms f(L): E(L) -> E'(L) for every extension L/K. (In categorical language, E determines a functor from K-algebras to Abelian groups, and f determines a morphism [natural transformation] between two such functors.)

Of course, as a Sage user you should still be able to construct a point P from its coordinates (u, v) by typing P = E(u, v) as an alternative for P = E(K)(u, v), and likewise you should be able to apply an isogeny f to P by typing either f(P) or f(K)(P).

comment:13 follow-up: Changed 5 months ago by sbesnier

So, if I make it short:

  • the idea would be to generalize the "abelian_group" method which is currently only avaible for EC on Galois fields to all the EC in order to have an actual "AbelianGroup?" in the sage category system (in addition with "Scheme"). Hence, the "non-uniqueness of set of generators" problem is moved into this "new" class of "Abelian Group of points on EC..." and it is easy to make EC unique.
  • Moreover, it would be nice to do the same separation between isogenies seen as scheme-morphim and isogenis seen as group-morphim.

Am I right? May I begin to refactoring the code in this way?

I've disscussed today with Luca today and he thinks that would be good to create a new category "AbelianVarieties?" which require to implement this "abelian_group" method. What do you think about that ?

Last edited 5 months ago by sbesnier (previous) (diff)

comment:14 in reply to: ↑ 13 ; follow-up: Changed 5 months ago by pbruin

Replying to sbesnier:

So, if I make it short:

  • the idea would be to generalize the "abelian_group" method which is currently only avaible for EC on Galois fields to all the EC in order to have an actual "AbelianGroup?" in the sage category system (in addition with "Scheme"). Hence, the "non-uniqueness of set of generators" problem is moved into this "new" class of "Abelian Group of points on EC..." and it is easy to make EC unique.
  • Moreover, it would be nice to do the same separation between isogenies seen as scheme-morphim and isogenis seen as group-morphim.

Am I right? May I begin to refactoring the code in this way?

I think this sounds like a good plan. It does have a certain the risk of becoming a big project, so be careful to split it into well-defined steps and to proceed one step at a time.

Just some thoughts about the first of your two points for now. Before doing any coding, I would say it is essential to have a clear picture of both the mathematical objects and the Sage (or Python) objects representing them, and of the relations between them. Currently, given an elliptic curve E over a field K, there are at least three kinds of objects to consider:

  • the Sage object E representing the curve itself as a scheme (type EllipticCurve_rational_field or similar);
  • the group of points E(K) (or more generally E(L) for an extension L of K), which does not care about the group structure but is the parent of (the Sage objects representing the) K-rational points of E (type SchemeHomset_points_abelian_variety_field);
  • if K is a finite field, there is also E.abelian_group(), which returns an object of type AdditiveAbelianGroupWrapper. This represents the group structure of E(K) concretely by returning a product of at most two finite cyclic groups and an embedding of this product into the "abstract" group E(K) (which in this case is an isomorphism).

This looks like the right framework for elliptic curves over number fields as well, since the group of K-points is finitely generated. For general fields (e.g. C), it only makes sense to have the first two kinds of objects. So writing a variant of E.abelian_group() for elliptic curves over number fields could be a logical first step.

In general it is important to find out what functionality is already available, and how much of it you can use. (Remember that a guiding principle of Sage is "building the car, not reinventing the wheel". This originally refers to the fact that Sage builds on many other pieces of software, but it is also a good general slogan.)

I've disscussed today with Luca today and he thinks that would be good to create a new category "AbelianVarieties?" which require to implement this "abelian_group" method. What do you think about that ?

It would indeed be nice to have a category of Abelian varieties, but this is probably largely independent of the rest of what you want to do. The current implementation of EllipticCurve_finite_field.abelian_group() does not refer to categories either. I would guess it is easiest to do the other things first without involving a category of Abelian varieties (in the code; you can of course always keep it in mind as the place where things live mathematically). If you need to specify a category somewhere, Schemes(K) will probably be good enough for now, since this is the category in which elliptic curves over K currently live.

comment:15 in reply to: ↑ 14 ; follow-up: Changed 5 months ago by defeo

  • the group of points E(K) (or more generally E(L) for an extension L of K), which does not care about the group structure but is the parent of (the Sage objects representing the) K-rational points of E (type SchemeHomset_points_abelian_variety_field);
  • if K is a finite field, there is also E.abelian_group(), which returns an object of type AdditiveAbelianGroupWrapper.

I haven't dug enough into the way Sage represents groups, but do these two objects need to be different ? If groups in Sage need to have explicitly set generators, then obviously yes: we don't want to compute generators unless the user asks us to.

But if a group can be represented abstractly (by its elements and an algorithm for the group operation), then it seems to me that these two should be the same, with the generators computed lazily when the user asks for them.

comment:16 in reply to: ↑ 15 Changed 5 months ago by pbruin

Replying to defeo:

  • the group of points E(K) (or more generally E(L) for an extension L of K), which does not care about the group structure but is the parent of (the Sage objects representing the) K-rational points of E (type SchemeHomset_points_abelian_variety_field);
  • if K is a finite field, there is also E.abelian_group(), which returns an object of type AdditiveAbelianGroupWrapper.

I haven't dug enough into the way Sage represents groups, but do these two objects need to be different ? If groups in Sage need to have explicitly set generators, then obviously yes: we don't want to compute generators unless the user asks us to.
But if a group can be represented abstractly (by its elements and an algorithm for the group operation), then it seems to me that these two should be the same, with the generators computed lazily when the user asks for them.

But don't you then run into the same difficulty with unique representation that we now have for elliptic curves, namely caching non-canonical data inside a canonical object? If you keep the two objects (i.e. the abstract group vs. the generators) separate, then it is clear that the way for the user to remember a choice of generators is to store the result of E.abelian_group() as opposed to the result of E(K).

Also, I would say it is conceptually better to keep them separate, since the AdditiveAbelianGroupWrapper is actually not a group at all, but a homomorphism from some "standard" Abelian group (product of cyclic groups) to another group, in this case E(K).

comment:17 Changed 5 months ago by cremona

I agree with Peter here (we have been discussing these issues in our common room in Warwick).

I particularly want to emphasize that what you have in mind is quite a large project, which needs to be done step by step, with plenty of input from other experienced Sage users who will be greatly affected by such changes (e.g. me!). Also, be careful that the improved design will not be accompanied by a decrease in efficiency.

Some of what is being proposed here would have been done a lot earlier, but Sage's support for f.g. abelian groups was not good enough in the early days. As soon as it became good enough it was applied to the simplest of these cases, namely the group of points of an e.c. over a finite field.

We want to keep separate the abstract abelian group from the concrete realization of it as a set of points, so that we can use generaic abelian group functionality to (for example) compute kernels. And as well as the easy map from the abstract group to the concrete point set (using known generators) we must also provide the harder map in the reverse direction, which is a form of elliptic logarithm. This is actually easier in the number field case since we can use canonical heights to express a point as a linear combination of the generators.

comment:18 follow-up: Changed 5 months ago by sbesnier

Considering the EC part, we already have almost what we want isn't it?

Let E=EllipticCurve(whatever), we "only" have to:

  • make E unique : it is already almost done by Simon's patch, although this patch maintains the gens in E. Meanwhile, the files had been edited for other reasons; will nevertheless the automatic tools work or might I manually edit the files thanks to the diff in order to reuse Simon's work?
  • turn E(K) into an actual group
  • extend the support of E.abelian_group(K) when K is a number field (and move the method in E(K)?)
  • move .rank(), .gens() and other non-canonical methods/attribute to `E.abelian_group(K)

John wrote:

And as well as the easy map from the abstract group to the concrete point set (using known generators) we must also provide the harder map in the reverse direction, which is a form of elliptic logarithm.

I'm not sure to see the point. You would like to have the map E(K) -> E.abelian_group() which calculate calculate the generators, and also the map E.abelian_group() -> E (or E(K)?) which calculates the a-invariants of E (or anything which determines E uniquely) from the generators?

comment:19 in reply to: ↑ 18 Changed 5 months ago by cremona

Replying to sbesnier:

Considering the EC part, we already have almost what we want isn't it?

Let E=EllipticCurve(whatever), we "only" have to:

  • make E unique : it is already almost done by Simon's patch, although this patch maintains the gens in E. Meanwhile, the files had been edited for other reasons; will nevertheless the automatic tools work or might I manually edit the files thanks to the diff in order to reuse Simon's work?

Don't use the patch as it is: for a start Sage no longer uses patches but git branches, and also as the patch is 3 years old it certainly will not apply cleanly. What will be needed is a new git branch based on the current development branch (also known as version 6.2.beta8) onto which the same changes as made by the patch are applied. You can try to use Sage's methods for converting patches to git branches, but it would be a miracle if that worked on a 3-year-old patch! If you are nervous, someone else might do this step for you. Then after committing Simon's changes in the new branch you can add your changes, make a new commit, and everyone will be able to try it out.

  • turn E(K) into an actual group
  • extend the support of E.abelian_group(K) when K is a number field (and move the method in E(K)?)
  • move .rank(), .gens() and other non-canonical methods/attribute to `E.abelian_group(K)

John wrote:

And as well as the easy map from the abstract group to the concrete point set (using known generators) we must also provide the harder map in the reverse direction, which is a form of elliptic logarithm.

I'm not sure to see the point. You would like to have the map E(K) -> E.abelian_group() which calculate calculate the generators, and also the map E.abelian_group() -> E (or E(K)?) which calculates the a-invariants of E (or anything which determines E uniquely) from the generators?

My point is that somewhere there has to be code which, given a point and known generators, expresses that point as a Z-linear combination of the generators. Assuming that E.abelian_group was an abstract abelian group, this code would be used in mapping from E(K) to it.

comment:20 follow-up: Changed 5 months ago by pbruin

One remark about the approach to follow to make elliptic curves satisfy unique representation: it turns out that there is an important problem with using UniqueRepresentation (which Simon's patch introduces) together with caching (which is certainly used by EllipticCurve), see https://groups.google.com/forum/#!topic/sage-devel/q5uy_lI11jg. If I remember correctly, for non-trivial parents it is recommended to use a UniqueFactory, which gives more flexibility than UniqueRepresentation. (I personally also understand UniqueFactory better than the __classcall__() magic of Simon's patch, but that may be simply because I am too familiar with this part of the internals of Sage.) Maybe Simon or someone else can elaborate on this point?

comment:21 follow-up: Changed 5 months ago by jpflori

  • Cc jpflori added

comment:22 in reply to: ↑ 21 ; follow-up: Changed 5 months ago by defeo

I'm trying to gitify Simon's code, but I get heaps of errors when I doctest. They all seem to be the same:

      File "/home/dfl/sage/local/lib/python2.7/site-packages/sage/databases/cremona.py", line 873, in elliptic_curve
        F = EllipticCurve_rational_field.__new__(EllipticCurve_rational_field)
    TypeError: sage.misc.fast_methods.WithEqualityById.__new__(EllipticCurve_rational_field) is not safe, use sage.structure.parent.Parent.__new__()

Does anyone understand it?

comment:23 in reply to: ↑ 22 ; follow-up: Changed 5 months ago by cremona

Replying to defeo:

I'm trying to gitify Simon's code, but I get heaps of errors when I doctest. They all seem to be the same:

      File "/home/dfl/sage/local/lib/python2.7/site-packages/sage/databases/cremona.py", line 873, in elliptic_curve
        F = EllipticCurve_rational_field.__new__(EllipticCurve_rational_field)
    TypeError: sage.misc.fast_methods.WithEqualityById.__new__(EllipticCurve_rational_field) is not safe, use sage.structure.parent.Parent.__new__()

Does anyone understand it?

Not really, but what it is doing at that point of sage/databases/cremona.py is constructing an elliptic curve from some data such as the label, which causes it to look that up in the database. What is the state of your local/share/cremona/cremona_mini.db file? Is it 8537088 bytes? If not, you could try sage -f elliptic_curves.

comment:24 in reply to: ↑ 23 Changed 5 months ago by defeo

Not really, but what it is doing at that point of sage/databases/cremona.py is constructing an elliptic curve from some data such as the label, which causes it to look that up in the database. What is the state of your local/share/cremona/cremona_mini.db file? Is it 8537088 bytes? If not, you could try sage -f elliptic_curves.

My cremona_mini.db is up to date. The error doesn't seem related to the database. In a sage shell

sage: from sage.schemes.elliptic_curves.ell_rational_field import EllipticCurve_rational_field
sage: EllipticCurve_rational_field.__new__(EllipticCurve_rational_field)
---------------------------------------------------------------------------
...
AttributeError: 'EllipticCurve_rational_field' object has no attribute '_EllipticCurve_generic__ainvs'

With Simon's patch applied (using the __classcall__ magic all over the place).

sage: from sage.schemes.elliptic_curves.ell_rational_field import EllipticCurve_rational_field
sage: EllipticCurve_rational_field.__new__(EllipticCurve_rational_field)
---------------------------------------------------------------------------
...
TypeError: sage.misc.fast_methods.WithEqualityById.__new__(EllipticCurve_rational_field) is not safe, use sage.structure.parent.Parent.__new__()
sage: Parent.__new__(EllipticCurve_rational_field)
---------------------------------------------------------------------------
...
AttributeError: 'EllipticCurve_rational_field' object has no attribute sage: '_EllipticCurve_generic__ainvs'

Either way, I don't understand how this line is supposed to work. I think we need help from Simon, if we want to resurrect his patch.

comment:25 Changed 5 months ago by sbesnier

pbruin wrote:

One remark about the approach to follow to make elliptic curves satisfy unique representation: it turns out that there is an important problem with using UniqueRepresentation? (which Simon's patch introduces) together with caching (which is certainly used by EllipticCurve?), see ​https://groups.google.com/forum/#!topic/sage-devel/q5uy_lI11jg. If I remember correctly, for non-trivial parents it is recommended to use a UniqueFactory?, which gives more flexibility than UniqueRepresentation?. (I personally also understand UniqueFactory? better than the classcall() magic of Simon's patch, but that may be simply because I am too familiar with this part of the internals of Sage.) Maybe Simon or someone else can elaborate on this point?

If I correctly understand Nils position, it would be better to use a UniqueFactory isn't it and not the UniqueRepresentation ? In that case, is it usefull to gitify this UniqueRepresentation patch ?

comment:26 Changed 5 months ago by defeo

  • Branch set to u/defeo/ticket/11474
  • Modified changed from 04/18/14 07:31:02 to 04/18/14 07:31:02

comment:27 Changed 5 months ago by defeo

  • Commit set to 8cbb73e266096e02efc917545aab36d067b7e063

If I correctly understand Nils position, it would be better to use a UniqueFactory isn't it and not the UniqueRepresentation ? In that case, is it usefull to gitify this UniqueRepresentation patch ?

Probably not. Anyway, I gitified it, thus I'm pushing it, even if it doesn't work. At least, it will be easier to read Simon's proposed changes.

There were conflicts with #10999 (which is another bug related to uniqueness) in ell_rational_field.py. I hopefully merged them correctly.


New commits:

8cbb73e11474: Make elliptic curves unique parents.

comment:28 Changed 5 months ago by jpflori

For what it's worth, there was a similar new issue a long time ago:

comment:29 in reply to: ↑ 20 Changed 5 months ago by SimonKing

Replying to pbruin:

If I remember correctly, for non-trivial parents it is recommended to use a UniqueFactory, which gives more flexibility than UniqueRepresentation. (I personally also understand UniqueFactory better than the __classcall__() magic of Simon's patch, but that may be simply because I am too familiar with this part of the internals of Sage.) Maybe Simon or someone else can elaborate on this point?

I don't recall what I did in this patch, and I do not have the bandwith to look at it right now. So, for now I can only try to explain my general point of view to factory versus CachedRepresentation versus UniqueRepresentation versus WithEqualityById.

If one uses a factory, then one can rather cleanly separate the creation of the cache key from the input data, additional data used to create the object (without being relevant to the cache) and the creation of the object to be returned. What it returns is not a unique parent, because comparison and hash is (and can not) be taken care of by the factory. Drawbacks:

  • One needs to write the factory code. At least in trivial cases, CachedRepresentation involves less manual work.
  • Suppose you used to have a factory for some parents, but later decide to remove the factory. If you remove the factory from Sage, then old pickles will break, since they rely on the factory being available. This is in contrast to CachedRepresentation, where you just need that the class name is preserved: If you remove CachedRepresentation from the base classes, then old pickles can still be opened.
  • I think it is not nice that one has to do MyFancyStuff(args) to create an object, but then the resulting object is not an instance of MyFancyStuff. But that might be a matter of taste.

CachedRepresentation is essentially equivalent to using a factory. In particular, it does not result in unique parents. Drawbacks:

  • It can not be used on extension classes, since a metaclass is involved (which is not supported by Cython).
  • It does not cleanly separate creation of the cache, additional arguments and object creation. You can write __classcall(_private)__ so that it does exactly the same as a factory, it can look up stuff in a database, and so on. But the code is less clean and thus more error prone.

So, at this point, we have some kind of factory, but no uniqueness of parents. In order to add unique parent behaviour, one can simply add WithEqualityById to the list of base classes (and make sure that hash and comparison will not be overridden in the sub-class).

UniqueRepresentation simply is a ready-made combination of CachedRepresentation and WithEqualityById, there is nothing more to it.

I hope that these remarks help to assess whether it would be better to use a factory PLUS WithEqualityById on elliptic curves, or "simply" use UniqueRepresentation.

comment:30 Changed 5 months ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:31 Changed 4 months ago by cremona

There seem to be a lot of other tickets waiting for this one. It is tagged "needs info": what info, and from whom? What is the status of the branch & commits listed?

comment:32 Changed 4 months ago by SimonKing

I have put "needs_info" at some point, because it has not been clear whether we actually want unique parent behaviour for elliptic curves. Peter Bruin has replied something on that question, but I think we never came to a real conclusion.

comment:33 follow-up: Changed 4 months ago by cremona

Thanks. We need to reach a conclusion while there are other "needs review" tickets claiming to depend on this. I used to know what that meant, but now... it may or may not mean that the branches asking for review include the unreviewed commits here. For example #12880.

comment:34 in reply to: ↑ 33 ; follow-up: Changed 4 months ago by pbruin

Replying to cremona:

Thanks. We need to reach a conclusion while there are other "needs review" tickets claiming to depend on this. I used to know what that meant, but now... it may or may not mean that the branches asking for review include the unreviewed commits here. For example #12880.

I think the other tickets depend on this one in the sense that they need elliptic curves to be unique parents, not in the sense that they already include commits that belong to this ticket.

In my opinion we should definitely make elliptic curves unique parents. The question is whether we should use UniqueRepresentation or UniqueFactory (or a custom cache, but I don't see why that would be needed). I would personally prefer a UniqueFactory, mostly because I think it is more natural and uses less black magic than UniqueRepresentation + __classcall__, and hence will be easier to understand/extend for other developers.

The idea is that the UniqueFactory is the place where we do all the work related to converting various input data into the 5-tuple of a-coefficients. There are many possible input data, for example:

  • a-coefficients
  • base ring + a-coefficients
  • c-coefficients
  • Cremona label
  • base ring + Cremona label
  • j-invariant

The logic of converting any of these input data into a-coefficients is very similar for the various base rings, so it seems best to do it all in one place. I imagine that the future UniqueFactory would do the work of the current (user-level) function sage.schemes.elliptic_curves.EllipticCurve plus the handling of Cremona labels, which is currently duplicated [triplicated?] in EllipticCurve_rational_field, EllipticCurve_number_field and EllipticCurve_padic_field.

Of course, whoever implements this in the end has to make the choice how to do it. Unfortunately I am currently a bit too busy with some research things and don't have a lot of time for it at the moment.

comment:35 in reply to: ↑ 34 ; follow-up: Changed 4 months ago by SimonKing

Replying to pbruin:

In my opinion we should definitely make elliptic curves unique parents. The question is whether we should use UniqueRepresentation or UniqueFactory (or a custom cache, but I don't see why that would be needed). I would personally prefer a UniqueFactory, mostly because I think it is more natural and uses less black magic than UniqueRepresentation + __classcall__, and hence will be easier to understand/extend for other developers.

... except for the fact that UniqueFactory alone is not enough to create a unique parent. You need to additionally adapt __cmp__ etc, and this is what inheritance from UniqueRepresentation does on top of __classcall__.

The idea is that the UniqueFactory is the place where we do all the work related to converting various input data into the 5-tuple of a-coefficients. There are many possible input data, for example:

  • a-coefficients
  • base ring + a-coefficients
  • c-coefficients
  • Cremona label
  • base ring + Cremona label
  • j-invariant

This I consider a valid argument for using a factory. But a tad more needs to be done.

comment:36 in reply to: ↑ 35 ; follow-up: Changed 4 months ago by pbruin

Replying to SimonKing:

Replying to pbruin:

I would personally prefer a UniqueFactory, mostly because I think it is more natural and uses less black magic than UniqueRepresentation + __classcall__, and hence will be easier to understand/extend for other developers.

... except for the fact that UniqueFactory alone is not enough to create a unique parent. You need to additionally adapt __cmp__ etc, and this is what inheritance from UniqueRepresentation does on top of __classcall__.

Something that I think you recently clarified to me elsewhere, and which might be worth emphasising here too, is that "unique parents" really refers to two conditions:

  • equivalent input data (in the sense that we regard the resulting objects as being "the same", e.g. a-coefficients vs. Cremona label corresponding to the same curve) should result in identical parents;
  • parents should compare equal if and only if they are identical.

I was thinking about the first point, which is the more difficult one here. If we end up solving this by implementing a UniqueFactory, then the second point can be solved by simply inheriting from WithEqualityById, right?

comment:37 in reply to: ↑ 36 Changed 4 months ago by SimonKing

Replying to pbruin:

  • equivalent input data (in the sense that we regard the resulting objects as being "the same", e.g. a-coefficients vs. Cremona label corresponding to the same curve) should result in identical parents;
  • parents should compare equal if and only if they are identical.

I was thinking about the first point, which is the more difficult one here. If we end up solving this by implementing a UniqueFactory, then the second point can be solved by simply inheriting from WithEqualityById, right?

Yes.

comment:38 Changed 4 months ago by cremona

Sounds like quite a big job, needing people who know enough about elliptic curves and also enough about UniqueFactories?. Perhaps we can recruit Nils Bruin to help?

comment:39 Changed 3 months ago by pbruin

  • Dependencies set to #10665, #16317

I have been working on a branch that makes elliptic curves unique using UniqueFactory. It simultaneously cleans up the elliptic curve construction code and the relation of Sage elliptic curves to the data in Cremona's database.

My approach removes the need for a separate "database curve" attached to an elliptic curve over Q. With my branch, an elliptic curve constructed from the database is identical to the same curve constructed using Weierstrass coefficients. Moreover, the curves returned by E.database_curve() and E.minimal_model() are now identical, and both of them are identical to E if E is already in canonical minimal form.

I have to add some documentation and will upload my branch soon. There are unfortunately two remaining doctest failures, which are manifestations of #10665 and #16317.

comment:40 Changed 3 months ago by pbruin

  • Authors changed from Simon King to Peter Bruin
  • Branch changed from u/defeo/ticket/11474 to u/pbruin/11474-elliptic_curves_unique
  • Commit changed from 8cbb73e266096e02efc917545aab36d067b7e063 to 9871e7fa0e194b6e21a2f7a5f2d727bbd855ff88
  • Status changed from needs_info to needs_review

comment:41 Changed 2 months ago by git

  • Commit changed from 9871e7fa0e194b6e21a2f7a5f2d727bbd855ff88 to f7f37555460bcf62c657cba260f7151a9d5c6576

Branch pushed to git repo; I updated commit sha1. New commits:

f7f3755Trac 11474: fix doctest that depended on the extended Cremona database

comment:42 Changed 2 months ago by vbraun

  • Reviewers set to Volker Braun

comment:43 Changed 2 months ago by vbraun

  • Branch changed from u/pbruin/11474-elliptic_curves_unique to f7f37555460bcf62c657cba260f7151a9d5c6576
  • Resolution set to fixed
  • Status changed from needs_review to closed
Note: See TracTickets for help on using tickets.