VOTE: use the smooth model instead of the plane projective model for hyperelliptic curves

[Giacomo Pope]

Dear all,

Summary

To better support arithmetic on Jacobians and have a more natural implementation of hyperelliptic curves, we should implement them as toric varieties with a weighted polynomial ring (1 : 3 : 1) instead of plane projective curves.

Yes / No

Discussion

I am currently hoping to improve hyperelliptic curves and Jacobians of hyperelliptic curve in Sage. One big motivation for me is to try and get our computations with similar coverage to what exists in Magma to allow more academics in the field to benefit from the open-source community of Sage. The first main goal of this is for full featured arithmetic on the Jacobians of hyperelliptic curves.

The big blocker for me currently is that currently Sage implements hyperelliptic curves in the plane projective model. This is not an issue for the current methods, and it also allows for sensible arithmetic on Jacobians when there is one point at infinity. However, the more natural model I believe is the smooth model which uses a weighted polynomial (weights of (1 : 3 : 1)). For example, this would allow us to have a natural way of performing arithmetic on the real model of hyperelliptic curves. Something important for my own research. 

I believe in terms of Sage code this means changing the hyperelliptic curves to be toric varieties rather than projective varieties and will ultimately lead to a lot of work in rewriting the classes. 

This is not unexpected though. For example the docstring of the `points()` method discusses the possibility of this change in the future: https://github.com/sagemath/sage/blob/e417e2205be84d6d567b8897527fa6945ad09bdb/src/sage/schemes/hyperelliptic_curves/hyperelliptic_finite_field.py#L805-L858

This is associated with the sage-devel thread: https://groups.google.com/g/sage-devel/c/eKY85KwFldE which discusses progress on implementing arithmetic for Jacobians of hyperelliptic curves where there are 2, 1 (all cases) or 0 (only even genus) points at infinity. The work being done there uses a weighted polynomial ring to compute on the smooth model of hyperelliptic curves. 

A note on inheritance

There is currently another hiccup in this transition. The class EllipticCurve_finite_field is a child of HyperellipticCurve_finite_field which seems to have happened at some point in the past when computing lists of points on the curve. As far as I can tell, this inheritance has no other used functionality. (Please correct me if I am missing something). I have shown in https://github.com/sagemath/sage/pull/37595 that this inherited method is always slower than using the group structure on the elliptic curve, so this inheritance can be removed once PR 37595 has been merged.

[Nils Bruin]

The change makes sense, but you should investigate if it is at all possible to do this going through normal deprecation procedures, which would probably involve having both functionalities for some time (likely via differently named methods or via a flag implemented in a backward-compatime way), then having a deprecation period on the "old" functionality. After that the deprecated functionality can be removed. After a suitable wait period, the vacated space in the namespace can now be used for the new method. You'll be taking a couple of years before you're there.

If it's not possible, you'd better have very good reasons to probably break people's code out there with very little warning.

Once you find a way to do this, there's another choice in convention to consider: do you go with (1:1:g+1) weights or with (1:g+1:1) ? I.e., with [X:Z:Y] or [X:Y:Z]. Both have precedent and people who are used to the other convention will find it really annoying to adjust.

[Giacomo Pope]

I chose the weighting (1 : g + 1 : 1) following Galbraith's textbook https://www.math.auckland.ac.nz/~sgal018/crypto-book/ch10.pdf when implementing the arithmetic on the Jacobian. This is not a "good" answer though.

I would love to hear from more people about what they use / would want to use. 

As for deprecations, I won't know exactly how much will change before I start working on this but if anyone's code fundamentally uses the fact it's a projective variety and the functions coming from this then I suppose everything will simply have to exist as a second class with deprecation warnings. I don't know what's best here.

Ultimately (even if I wait 2 years) I think it would be good for sage to have more functioning arithmetic on Jacobians but this is obviously a very small slice of pie in the whole meal of hyperellptic curves.

As one data point, the following magma code

```

R<x> := PolynomialRing(Rationals());
f := x^6 + x + 1;
H := HyperellipticCurve(f);
Ambient(H)

```

Outputs

Projective Space of dimension 2 over Rational Field
Variables: $.1, $.2, $.3
The grading is:
    1, 3, 1

Matching my proposed grading.

[Nils Bruin]

On Monday 11 March 2024 at 15:04:50 UTC-7 Giacomo Pope wrote:

I chose the weighting (1 : g + 1 : 1) following Galbraith's textbook https://www.math.auckland.ac.nz/~sgal018/crypto-book/ch10.pdf when implementing the arithmetic on the Jacobian. This is not a "good" answer though.

I would love to hear from more people about what they use / would want to use.

I think it makes sense because at least it means the representation of most points is still compatible.

 

As for deprecations, I won't know exactly how much will change before I start working on this but if anyone's code fundamentally uses the fact it's a projective variety and the functions coming from this then I suppose everything will simply have to exist as a second class with deprecation warnings. I don't know what's best here.

Yes, with a change as fundamental as this, I think you may be best of just copying over the class and make your adjustments there. We'll have two underlying "implementations" of hyperelliptic curves, with different projective closures. We'll start out with the bad backward compatible one as default. At some point, we deprecate that. Then you can change the default. Then we can delete the old implementation. And then you can reintroduce the old naming as an alias/default.

I suspect most code that relies on non-weighted projective closures is broken anyway, but you'd need pretty strong arguments to deviate from normal deprecation.

 

Ultimately (even if I wait 2 years) I think it would be good for sage to have more functioning arithmetic on Jacobians but this is obviously a very small slice of pie in the whole meal of hyperellptic curves.

We can have the functionality without delay. It might just not be available on "default" objects until 2 years down the road. That's a little unfortunate and makes it less discoverable, but I think we do need to take backward compatibility seriously.

Also note that with this course of action, there is hardly anything controversial to the first steps: you're just adding functionality. So a sagedevel vote might not even be necessary.

[Giacomo Pope]

Yes, I didn't properly think about breaking changes so if I simply add a new implementation into sage then maybe this thread can switch from a VOTE to simply people giving advice / feedback if they so wish.

[Dima Pasechnik]

Sage's treatment of weighted polynomial rings is  buggy, cf. e.g.

https://github.com/sagemath/sage/issues/37167

this is something that should be addressed, one way or another

--
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+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/dc78d787-5e82-4fdb-92cd-f299b71972c5n%40googlegroups.com.

[Giacomo Pope]

I'm (somewhat) aware of bugs which come from poor treatment of weighted polynomial rings. In my mind this has two solutions.

1) Someone who is an expert in toric varieties has another look through the current code, adds more extensive testing and methods for computations in the area

2) We work with what we currently have for the hyperelliptic curve case and when something appears to be broken we attempt to fix it.

I am in no position to do 1) as I do not know enough. As a result I will start one 2) but I am happy for more work to be done in parallel?

My current experimentation I believe we want to define the curve in the following way

```

sage: def projective_model(f, h, g):
....:     """
....:     Compute the weighted projective model (1 : g + 1 : 1)
....:     """
....:     k = f.base_ring()
....:     T = toric_varieties.WP([1, g + 1, 1], base_ring=k, names="X, Y, Z")
....:     (X, Y, Z) = T.gens()
....:
....:     if h.is_zero():
....:         d = f.degree()
....:         F = sum(f[i] * X**i * Z**(d - i) for i in range(d + 1))
....:         G = Y**2 - F
....:     else:
....:         d = max(h.degree(), (f.degree() / 2).ceil())
....:         H = sum(h[i] * X**i * Z**(d - i) for i in range(d + 1))
....:         F = sum(f[i] * X**i * Z**(2*d - i) for i in range(2*d + 1))
....:         G = Y**2 + H*Y - F
....:
....:     return T.subscheme([G])
....:
sage: f = x^7 + 1
sage: h = x
sage: g = HyperellipticCurve(f, h).genus() # simply make sure this is a "good" choice of f, h for this field
sage: g
3
sage: projective_model(f, h, g)
Closed subscheme of 2-d toric variety covered by 3 affine patches defined by:
  -X^7*Z - Z^8 + X*Y*Z^3 + Y^2

```

Which suggests to me that the generic class for hyperelliptic curves is a child class HyperellipticCurve_generic(AlgebraicScheme_subscheme_toric) and we start building this from here.