Re: [sage-devel] Re: Help and Advice | Arithmetic of Jacobians in the Split/Real Model is Broken

[Giacomo Pope]

OK -- I'll do my best to break things down into the most manageable sizes 
to give this the best chance.

As for the maths/arithmetic, what we have coded gets Sage to the same point 
as Magma, although with a different representation. 

In our implementation, we follow the 
paper: https://eprint.iacr.org/2008/265. Generically, a divisor is 
represented by (u, v : n) where (u, v) are the Mumford coordinates of the 
divisor and n is the coefficient of \infty_+. As we can always deduce the 
coefficient m of \infty_- from deg(u) and n, this is omitted. Additionally, 
when the curve itself is ramified or inert then we can also deduce n and we 
instead represent elements as (u, v).

Unless I am mistaken, we can handle arithmetic with a unique representation 
of all divisors of Jac(C) for all cases with the exception of inert curves 
with odd genus. In this case, we raise an error when trying to perform 
arithmetic on this case. I believe this is what Magma does to.



On Wednesday, October 9, 2024 at 7:26:18 PM UTC+1 Nils Bruin wrote:

> On Wednesday 9 October 2024 at 09:31:45 UTC-7 giaco...@gmail.com wrote:
>
> 1. This will be a very large PR, is this generally an OK thing to do?
>
>
> Generally smaller PRs are easier to get merged, but I'm not sure if 
> merging n PRs of size m takes more or less time than merging one PR of size 
> n*m. If you can easily get some parts split off to merge as smaller PRs 
> you'd be able to get a "foot in the door" by getting those merged. But if 
> that really doesn't make sense, you could also prefer to stick with the 
> large PR. Especially with a large PR, I would recommend to design it such 
> that you DON'T change things outside of it. That way, the scope of your 
> large PR remains limited. That makes review easier.
>
> Further tie-in into the rest of the infrastructure, where you do need to 
> touch files outside your primary domain is probably better done in 
> follow-up PRs. You could already make them, but they would have a 
> dependence on the main initial PR.
>  
>
> 2. I believe it might be easier to make changes to this code in the 
> current repo before merging to sage, so if people reading this want to 
> contribute then we're discussing the code in the Sage zulip and we'd be 
> happy for more people to look at and improve the code
>
>
> You can try that, but I would expect that deviating from the normal flow 
> of things (which is: a PR on sagemath) would slow down the review process. 
> It's already hard to find people for that, and now you want them to follow 
> a custom procedure? You may be able to get the best of both worlds by some 
> git magic where you keep your own repo overlayed with the pull request. I 
> don't know if a tree can live in two repositories at once or if there are 
> ways to conveniently synchronize two subtrees of two distinct projects.
>  
> Mathematical comment: you'll get problems for mumford representation on 
> nonsplit imaginary hyperelliptic curves of odd genus. You want an odd 
> degree divisor to serve as a base of representing all classes and such a 
> thing might simply not exist. Indeed, there may be points on the Jacobian 
> that do not allow a representing divisor over the base field.
>

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/sage-devel/19f66c87-4918-4858-a51a-f5ec71560681n%40googlegroups.com.

Re: [sage-devel] Re: Help and Advice | Arithmetic of Jacobians in the Split/Real Model is Broken

[Giacomo Pope]

Hey all, 

Wanted to bump this as we have done a bunch of work (slowly, over the 
months) at rewriting the whole hyperelliptic curve class to work over the 
smooth model:

https://github.com/GiacomoPope/HyperellipticCurves

The plan we have is to introduce a new directory

/schemes/hyperelliptic_curves_smooth_model 

with this new curve and have `HyperellipticCurveSmoothModel` be a new 
object exported (to work along side HyperellipticCurve)

I was writing here for a few questions

1. This will be a very large PR, is this generally an OK thing to do?
2. I believe it might be easier to make changes to this code in the current 
repo before merging to sage, so if people reading this want to contribute 
then we're discussing the code in the Sage zulip and we'd be happy for more 
people to look at and improve the code
3. If people object to: /schemes/hyperelliptic_curves_smooth_model then I 
would love to know of a better/different solution

Any advice would be appreciated -- I really want to find a way to get this 
new code into sage as I think having working arithmetic of Jac(C) for many 
more cases is desirable and will allow for some really nice additional 
functionality for hyperelliptic curves into sagemath
On Monday, March 18, 2024 at 4:58:08 PM UTC Giacomo Pope wrote:

> To make discussion on this point easier, I have made a GitHub issue: 
> https://github.com/sagemath/sage/issues/37626
>
> For progress on this code, we have all doctests passing from the old 
> implementation except:
>
> - we cannot define toric varieties over rings, so we can't have 
> hyperelliptic curves over rings
> - we cannot use the current rational_points method from algebraic_schemes 
> due to missing methods in the homset of toric varieties
>
> We are also working on pairings as well as isomorphisms on top of 
> supporting all older features.
>
> On Friday, March 15, 2024 at 6:47:02 PM UTC Giacomo Pope wrote:
>
>> Back again with more class questions and general advice help
>>
>> While getting all the old sage code into this new project, I realised 
>> there are places where we really rely on the underlying curve classes. One 
>> example is that we need
>>
>> ```
>> def dimension():
>> return 1
>> ```
>>
>> To avoid some crashes, but more generally we also need 
>> `rational_points()` which lives all the way inside `Algebraic_scheme`. 
>> There's also a whole bunch of other things...
>>
>> I started exploring more and I found `Curve_generic` which we can create 
>> with the data I already have:
>>
>> ```
>> sage: H = HyperellipticCurveSmoothModel(x^5 + x + 1)
>> sage: C = Curve_generic(H._projective_model.ambient_space(), 
>> H._projective_model.defining_polynomials())
>> sage: type(C)
>> 
>> sage: C
>> Generic Curve over Rational Field defined by -X^5*Z - X*Z^5 - Z^6 + Y^2
>> sage: C.ambient_space()
>> 2-d toric variety covered by 3 affine patches
>> ```
>>
>> this gets us some of the way and I think is an OK starting point, but 
>> then things like asking for the curve crash for weighted projective space:
>>
>> ```
>> sage: Curve(H)
>>
>> ---
>> TypeError Traceback (most recent call 
>> last)
>> .
>> TypeError: ambient space neither affine nor projective
>> ```
>>
>> and calls to things like C.rational_points() have more issues
>>
>> ```
>> sage: C.rational_points(bounds=2)
>>
>> ---
>> KeyError  Traceback (most recent call 
>> last)
>> .
>> AttributeError: 'SchemeHomset_points_subscheme_toric_field_with_category' 
>> object has no attribute 'points'
>> ```
>>
>> Which just goes to show that these toric varieties are a little 
>> underdeveloped.
>>
>> Something which might be really nice would be 
>>
>> ```
>> class WeightedProjectiveCurve(Curve_generic, 
>> AlgebraicScheme_subscheme_toric):
>> ```
>>
>> Intended to mirror the similar:
>>
>> ```
>> class ProjectiveCurve(Curve_generic, 
>> AlgebraicScheme_subscheme_projective):
>> ```
>>
>> This could then be the class which is inherited by the Hyperelliptic 
>> curve class and we could aim for better coverage here.
>>
>> Any opinions on this? Any idea of people who might have thought about or 
>> made progress in this area?
>>
>> Otherwise, the project continues. Functions for finite fields are all 
>> 

Re: [sage-devel] Re: Help and Advice | Arithmetic of Jacobians in the Split/Real Model is Broken

[Giacomo Pope]

To make discussion on this point easier, I have made a GitHub 
issue: https://github.com/sagemath/sage/issues/37626

For progress on this code, we have all doctests passing from the old 
implementation except:

- we cannot define toric varieties over rings, so we can't have 
hyperelliptic curves over rings
- we cannot use the current rational_points method from algebraic_schemes 
due to missing methods in the homset of toric varieties

We are also working on pairings as well as isomorphisms on top of 
supporting all older features.

On Friday, March 15, 2024 at 6:47:02 PM UTC Giacomo Pope wrote:

> Back again with more class questions and general advice help
>
> While getting all the old sage code into this new project, I realised 
> there are places where we really rely on the underlying curve classes. One 
> example is that we need
>
> ```
> def dimension():
> return 1
> ```
>
> To avoid some crashes, but more generally we also need `rational_points()` 
> which lives all the way inside `Algebraic_scheme`. There's also a whole 
> bunch of other things...
>
> I started exploring more and I found `Curve_generic` which we can create 
> with the data I already have:
>
> ```
> sage: H = HyperellipticCurveSmoothModel(x^5 + x + 1)
> sage: C = Curve_generic(H._projective_model.ambient_space(), 
> H._projective_model.defining_polynomials())
> sage: type(C)
> 
> sage: C
> Generic Curve over Rational Field defined by -X^5*Z - X*Z^5 - Z^6 + Y^2
> sage: C.ambient_space()
> 2-d toric variety covered by 3 affine patches
> ```
>
> this gets us some of the way and I think is an OK starting point, but then 
> things like asking for the curve crash for weighted projective space:
>
> ```
> sage: Curve(H)
> ---
> TypeError Traceback (most recent call last)
> .
> TypeError: ambient space neither affine nor projective
> ```
>
> and calls to things like C.rational_points() have more issues
>
> ```
> sage: C.rational_points(bounds=2)
> ---
> KeyError  Traceback (most recent call last)
> .
> AttributeError: 'SchemeHomset_points_subscheme_toric_field_with_category' 
> object has no attribute 'points'
> ```
>
> Which just goes to show that these toric varieties are a little 
> underdeveloped.
>
> Something which might be really nice would be 
>
> ```
> class WeightedProjectiveCurve(Curve_generic, 
> AlgebraicScheme_subscheme_toric):
> ```
>
> Intended to mirror the similar:
>
> ```
> class ProjectiveCurve(Curve_generic, AlgebraicScheme_subscheme_projective):
> ```
>
> This could then be the class which is inherited by the Hyperelliptic curve 
> class and we could aim for better coverage here.
>
> Any opinions on this? Any idea of people who might have thought about or 
> made progress in this area?
>
> Otherwise, the project continues. Functions for finite fields are all 
> working, generic functions mostly and the padic functions are a WIP as we 
> need to adapt to the fact we have different points at infinity (and I dont 
> know how to properly handle the case when there's two (yet)).
>
> Finally, looking at the rational_points() method itself, this is something 
> people have at least considered:
>
> ```
> .. TODO::
>
> Implement Stoll's model in weighted projective space to
> resolve singularities and find two points (1 : 1 : 0) and
> (-1 : 1 : 0) at infinity.
> ```
>
>
> On Wednesday, March 13, 2024 at 6:23:38 PM UTC Giacomo Pope wrote:
>
>> Thanks so much for the context
>>
>> Oh interesting. In this case I wonder whether we should work on and 
>> include a new class (maybe something as simple as a WeightedProjectiveSpace 
>> and a curve from this) mirroring the implementation for the plane curves. 
>> Alternatively I could go into the old plane curve code and write these 
>> useful functions specifically for the hyperelliptic curves (and here even 
>> gain that these algorithms can be optimised). For example, I already had to 
>> include a `dimension()` method on the curve to properly compute the 
>> Jacobian. Potentially AlgebraicScheme_subscheme_toric is indeed the wrong 
>> inheritance
>>
>> On Wednesday, March 13, 2024 at 6:18:12 PM UTC Nils Bruin wrote:
>>
>>> One thing that may deserve a cursory check is the overhead involved in 
>>> inheriting from AlgebraicScheme_subscheme_toric class . Some parent 
>>> structures are optimized for prolonge

Re: [sage-devel] Re: Help and Advice | Arithmetic of Jacobians in the Split/Real Model is Broken

[Giacomo Pope]

Back again with more class questions and general advice help

While getting all the old sage code into this new project, I realised there 
are places where we really rely on the underlying curve classes. One 
example is that we need

```
def dimension():
return 1
```

To avoid some crashes, but more generally we also need `rational_points()` 
which lives all the way inside `Algebraic_scheme`. There's also a whole 
bunch of other things...

I started exploring more and I found `Curve_generic` which we can create 
with the data I already have:

```
sage: H = HyperellipticCurveSmoothModel(x^5 + x + 1)
sage: C = Curve_generic(H._projective_model.ambient_space(), 
H._projective_model.defining_polynomials())
sage: type(C)

sage: C
Generic Curve over Rational Field defined by -X^5*Z - X*Z^5 - Z^6 + Y^2
sage: C.ambient_space()
2-d toric variety covered by 3 affine patches
```

this gets us some of the way and I think is an OK starting point, but then 
things like asking for the curve crash for weighted projective space:

```
sage: Curve(H)
---
TypeError Traceback (most recent call last)
.
TypeError: ambient space neither affine nor projective
```

and calls to things like C.rational_points() have more issues

```
sage: C.rational_points(bounds=2)
---
KeyError  Traceback (most recent call last)
.
AttributeError: 'SchemeHomset_points_subscheme_toric_field_with_category' 
object has no attribute 'points'
```

Which just goes to show that these toric varieties are a little 
underdeveloped.

Something which might be really nice would be 

```
class WeightedProjectiveCurve(Curve_generic, 
AlgebraicScheme_subscheme_toric):
```

Intended to mirror the similar:

```
class ProjectiveCurve(Curve_generic, AlgebraicScheme_subscheme_projective):
```

This could then be the class which is inherited by the Hyperelliptic curve 
class and we could aim for better coverage here.

Any opinions on this? Any idea of people who might have thought about or 
made progress in this area?

Otherwise, the project continues. Functions for finite fields are all 
working, generic functions mostly and the padic functions are a WIP as we 
need to adapt to the fact we have different points at infinity (and I dont 
know how to properly handle the case when there's two (yet)).

Finally, looking at the rational_points() method itself, this is something 
people have at least considered:

```
.. TODO::

Implement Stoll's model in weighted projective space to
resolve singularities and find two points (1 : 1 : 0) and
(-1 : 1 : 0) at infinity.
```


On Wednesday, March 13, 2024 at 6:23:38 PM UTC Giacomo Pope wrote:

> Thanks so much for the context
>
> Oh interesting. In this case I wonder whether we should work on and 
> include a new class (maybe something as simple as a WeightedProjectiveSpace 
> and a curve from this) mirroring the implementation for the plane curves. 
> Alternatively I could go into the old plane curve code and write these 
> useful functions specifically for the hyperelliptic curves (and here even 
> gain that these algorithms can be optimised). For example, I already had to 
> include a `dimension()` method on the curve to properly compute the 
> Jacobian. Potentially AlgebraicScheme_subscheme_toric is indeed the wrong 
> inheritance
>
> On Wednesday, March 13, 2024 at 6:18:12 PM UTC Nils Bruin wrote:
>
>> One thing that may deserve a cursory check is the overhead involved in 
>> inheriting from AlgebraicScheme_subscheme_toric class . Some parent 
>> structures are optimized for prolonged use *after* creation and may do a 
>> lot of caching/precomputation. There may be scenarios where one wants to 
>> construct *lots* of hyperelliptic curves (for instance, when computing 
>> reductions of hyperelliptic curves mod lots of primes). An expensive parent 
>> may then add undue overhead. In that case it may be better to spin off the 
>> functionality required into a "lightweight" structure that gets wrapped in 
>> the expensive, full functionality parent. After all, for core algorithms a 
>> hyperelliptic curve is just a 3*g+5 length sequence of ring/field elements: 
>> the coefficients of the defining equation.
>>
>> There are of course also odd genus hyperelliptic curves that cover a 
>> genus 0 curve that is not isomorphic to a P^1, but computing in their 
>> Jacobians has its own problems, so you should probably not try to include 
>> them in your current design.
>>
>> One thing that may be worthwhile: hyperelliptic curves do inherit some 
>> interesting functionality from plane curv

Re: [sage-devel] Re: Help and Advice | Arithmetic of Jacobians in the Split/Real Model is Broken

[Giacomo Pope]

Thanks so much for the context

Oh interesting. In this case I wonder whether we should work on and include 
a new class (maybe something as simple as a WeightedProjectiveSpace and a 
curve from this) mirroring the implementation for the plane curves. 
Alternatively I could go into the old plane curve code and write these 
useful functions specifically for the hyperelliptic curves (and here even 
gain that these algorithms can be optimised). For example, I already had to 
include a `dimension()` method on the curve to properly compute the 
Jacobian. Potentially AlgebraicScheme_subscheme_toric is indeed the wrong 
inheritance

On Wednesday, March 13, 2024 at 6:18:12 PM UTC Nils Bruin wrote:

> One thing that may deserve a cursory check is the overhead involved in 
> inheriting from AlgebraicScheme_subscheme_toric class . Some parent 
> structures are optimized for prolonged use *after* creation and may do a 
> lot of caching/precomputation. There may be scenarios where one wants to 
> construct *lots* of hyperelliptic curves (for instance, when computing 
> reductions of hyperelliptic curves mod lots of primes). An expensive parent 
> may then add undue overhead. In that case it may be better to spin off the 
> functionality required into a "lightweight" structure that gets wrapped in 
> the expensive, full functionality parent. After all, for core algorithms a 
> hyperelliptic curve is just a 3*g+5 length sequence of ring/field elements: 
> the coefficients of the defining equation.
>
> There are of course also odd genus hyperelliptic curves that cover a genus 
> 0 curve that is not isomorphic to a P^1, but computing in their Jacobians 
> has its own problems, so you should probably not try to include them in 
> your current design.
>
> One thing that may be worthwhile: hyperelliptic curves do inherit some 
> interesting functionality from plane curves (particularly via their affine 
> patch) in the form of "riemann_surface". It may be worth keeping that, even 
> if the particular code there could be expanded to work much more 
> efficiently on hyperelliptic curves.
>
> On Wednesday 13 March 2024 at 10:32:08 UTC-7 Giacomo Pope wrote:
>
>> Thanks David, there's a bunch of nice things we could do for genus two in 
>> various cases which would be worth including. The inert case, where all 
>> degree zero divisors (except the identity element) have u with degree 2 
>> would probably allow something particularly nice. 
>>
>> As another update I have done a fairly brutish refactoring of the proof 
>> of concept code to follow the design decisions of the previous 
>> implementation. https://github.com/GiacomoPope/HyperellipticCurves
>>
>> Hyperelliptic curves are created from a dynamic class constructor on top 
>> of the AlgebraicScheme_subscheme_toric class (before this was a curve over 
>> the plane projective curves)
>> A generic class offers most features, but other classes will cover the 
>> case of finite fields, rational fields and padic fields
>> The Jacobian is a small class built on top of `jacobian_generic` which is 
>> built from the curve
>> The set of rational points of the Jacobian is built on top of 
>> SchemeHomSet and the elements (divisors) are morphisms built on top of 
>> SchemeMorphism
>>
>> I will do my best to clean up and refactor code to the standard of code 
>> which is included into Sage now, but I would love to know any feedback 
>> advice on whether this structure is still the one to use. The older version 
>> of this code dates back to the beginning of Sage so it's very possible we 
>> have new ideas of how things should be done and if we're doing the work or 
>> rewriting the whole set of classes I may as well do a good job.
>>
>> Giacomo
>>
>> On Wednesday, March 13, 2024 at 3:36:09 AM UTC David Roe wrote:
>>
>>> There is also this old trac ticket 
>>> <https://github.com/sagemath/sage/issues/23154> about implementing fast 
>>> arithmetic in genus 2 Jacobians, which never made it into Sage.  I've CCed 
>>> Mike Jabobson, who worked on it.
>>> David
>>>
>>>
>>> On Tue, Mar 12, 2024 at 12:10 PM Giacomo Pope  
>>> wrote:
>>>
>>>> Thank you for linking this and I agree this is a great way to 
>>>> cross-compare the work we have been doing. I am not an expert in this area 
>>>> so I am not sure I should do a full review but I'm happy to look over it 
>>>> if 
>>>> this helps.
>>>>
>>>> As a small update on this work, I now have 
>>>>
>>>> class HyperellipticCurveSmoothModel(Alg

Re: [sage-devel] Re: Help and Advice | Arithmetic of Jacobians in the Split/Real Model is Broken

[Giacomo Pope]

Thanks David, there's a bunch of nice things we could do for genus two in 
various cases which would be worth including. The inert case, where all 
degree zero divisors (except the identity element) have u with degree 2 
would probably allow something particularly nice. 

As another update I have done a fairly brutish refactoring of the proof of 
concept code to follow the design decisions of the previous 
implementation. https://github.com/GiacomoPope/HyperellipticCurves

Hyperelliptic curves are created from a dynamic class constructor on top of 
the AlgebraicScheme_subscheme_toric class (before this was a curve over the 
plane projective curves)
A generic class offers most features, but other classes will cover the case 
of finite fields, rational fields and padic fields
The Jacobian is a small class built on top of `jacobian_generic` which is 
built from the curve
The set of rational points of the Jacobian is built on top of SchemeHomSet 
and the elements (divisors) are morphisms built on top of SchemeMorphism

I will do my best to clean up and refactor code to the standard of code 
which is included into Sage now, but I would love to know any feedback 
advice on whether this structure is still the one to use. The older version 
of this code dates back to the beginning of Sage so it's very possible we 
have new ideas of how things should be done and if we're doing the work or 
rewriting the whole set of classes I may as well do a good job.

Giacomo

On Wednesday, March 13, 2024 at 3:36:09 AM UTC David Roe wrote:

> There is also this old trac ticket 
> <https://github.com/sagemath/sage/issues/23154> about implementing fast 
> arithmetic in genus 2 Jacobians, which never made it into Sage.  I've CCed 
> Mike Jabobson, who worked on it.
> David
>
>
> On Tue, Mar 12, 2024 at 12:10 PM Giacomo Pope  wrote:
>
>> Thank you for linking this and I agree this is a great way to 
>> cross-compare the work we have been doing. I am not an expert in this area 
>> so I am not sure I should do a full review but I'm happy to look over it if 
>> this helps.
>>
>> As a small update on this work, I now have 
>>
>> class HyperellipticCurveSmoothModel(AlgebraicScheme_subscheme_toric)
>>
>> So this new class builds on top of AlgebraicScheme_subscheme_toric and 
>> the smooth projective model is built using a toric variety. The points on 
>> the curve are currently SchemeMorphism_point_toric_field, potentially I 
>> will need to make a child class of these if methods on the points 
>> themselves are required.
>>
>> With the working arithmetic and this new inheritance my work is now going 
>> to be the rather slow and painful rewrite of all hyperelliptic methods from 
>> the current implementation to ensure everything works on the smooth degree 
>> model.
>>
>> On Monday, March 11, 2024 at 6:23:38 AM UTC Kwankyu Lee wrote:
>>
>>> On Friday, March 8, 2024 at 7:37:04 PM UTC+9 Giacomo Pope wrote:
>>>
>>> As a small update, the repository now contains code to
>>>
>>> - perform arithmetic for
>>>   - the imaginary model (ramified, one point at infinity) for all cases
>>>   - the real model (split, two points at infinity) for all cases
>>>   - the real model (inert, zero points at infinity) for even genus
>>>   Which allows us to do "as much" as Magma does for Jacobians of 
>>> hyperellipticc curves from the perspective of arithmetic. 
>>>
>>> My current "test" for the arithmetic is that D - D = 0 for all cases, 
>>> that jacobian_order * D = zero and that order_from_multiple(D) works. If 
>>> people have other ideas for tests, please let me know. Of course at the 
>>> moment these tests are over finite fields but you can reasonable use other 
>>> fields (as Sabrina's message shows) but I am less sure about how to do 
>>> randomised testing here.
>>>
>>>
>>> I just set https://github.com/sagemath/sage/pull/35467 to "needs 
>>> review" status. The PR implements Jacobian arithmetic for general 
>>> projective curves.
>>>
>>> It is slow compared with Jacobian arithmetic using Mumford 
>>> representation, but could be used to crosscheck the computations.
>>>
>> -- 
>>
> 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/7f646c6d-bd0b-452d-a730-30144415f590n%40google

Re: [sage-devel] Re: Help and Advice | Arithmetic of Jacobians in the Split/Real Model is Broken

[Giacomo Pope]

Thank you for linking this and I agree this is a great way to cross-compare 
the work we have been doing. I am not an expert in this area so I am not 
sure I should do a full review but I'm happy to look over it if this helps.

As a small update on this work, I now have 

class HyperellipticCurveSmoothModel(AlgebraicScheme_subscheme_toric)

So this new class builds on top of AlgebraicScheme_subscheme_toric and the 
smooth projective model is built using a toric variety. The points on the 
curve are currently SchemeMorphism_point_toric_field, potentially I will 
need to make a child class of these if methods on the points themselves are 
required.

With the working arithmetic and this new inheritance my work is now going 
to be the rather slow and painful rewrite of all hyperelliptic methods from 
the current implementation to ensure everything works on the smooth degree 
model.

On Monday, March 11, 2024 at 6:23:38 AM UTC Kwankyu Lee wrote:

> On Friday, March 8, 2024 at 7:37:04 PM UTC+9 Giacomo Pope wrote:
>
> As a small update, the repository now contains code to
>
> - perform arithmetic for
>   - the imaginary model (ramified, one point at infinity) for all cases
>   - the real model (split, two points at infinity) for all cases
>   - the real model (inert, zero points at infinity) for even genus
>   Which allows us to do "as much" as Magma does for Jacobians of 
> hyperellipticc curves from the perspective of arithmetic. 
>
> My current "test" for the arithmetic is that D - D = 0 for all cases, that 
> jacobian_order * D = zero and that order_from_multiple(D) works. If people 
> have other ideas for tests, please let me know. Of course at the moment 
> these tests are over finite fields but you can reasonable use other fields 
> (as Sabrina's message shows) but I am less sure about how to do randomised 
> testing here.
>
>
> I just set https://github.com/sagemath/sage/pull/35467 to "needs review" 
> status. The PR implements Jacobian arithmetic for general projective curves.
>
> It is slow compared with Jacobian arithmetic using Mumford representation, 
> but could be used to crosscheck the computations.
>

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/sage-devel/7f646c6d-bd0b-452d-a730-30144415f590n%40googlegroups.com.

Re: [sage-devel] VOTE: use the smooth model instead of the plane projective model for hyperelliptic curves

[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.
On Monday, March 11, 2024 at 11:17:02 PM UTC Dima Pasechnik wrote:

> 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
>
>
>
> On Mon, Mar 11, 2024 at 9:31 PM Giacomo Pope  wrote:
>
>> 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 
&

[sage-devel] Re: VOTE: use the smooth model instead of the plane projective model for hyperelliptic curves

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

On Monday, March 11, 2024 at 10:24:46 PM UTC Nils Bruin wrote:

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

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/sage-devel/39d3d787-ab42-4417-bec4-bc00ce345bb1n%40googlegroups.com.

[sage-devel] Re: VOTE: use the smooth model instead of the plane projective model for hyperelliptic curves

[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 := 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.

On Monday, March 11, 2024 at 9:52:09 PM UTC Nils Bruin wrote:

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

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/sage-devel/608132ed-19f5-4502-9506-ddd892ff3d85n%40googlegroups.com.

[sage-devel] 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.

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/sage-devel/dc78d787-5e82-4fdb-92cd-f299b71972c5n%40googlegroups.com.

Re: [sage-devel] Re: Help and Advice | Arithmetic of Jacobians in the Split/Real Model is Broken

[Giacomo Pope]

As a small update, the repository now contains code to

- perform arithmetic for
  - the imaginary model (ramified, one point at infinity) for all cases
  - the real model (split, two points at infinity) for all cases
  - the real model (inert, zero points at infinity) for even genus
  Which allows us to do "as much" as Magma does for Jacobians of 
hyperellipticc curves from the perspective of arithmetic. 

My current "test" for the arithmetic is that D - D = 0 for all cases, that 
jacobian_order * D = zero and that order_from_multiple(D) works. If people 
have other ideas for tests, please let me know. Of course at the moment 
these tests are over finite fields but you can reasonable use other fields 
(as Sabrina's message shows) but I am less sure about how to do randomised 
testing here.

- We also have a function which can randomly (but not uniformly) sample 
elements of the Jacobian for all the cases.
- We can compute the order of the Jacobian from the frob. polynomial and 
using the arithmetic and in-build `order_from_multiple` then find the order 
of divisors

I think the next thing to do is to look at isomorphisms and maybe even 
isogenies (Richelot only for genus two perhaps?)

If you are interested in this area and want to contribute, then I think 
fleshing out the code in this repo will be easier during these early stages 
and once it feels complete we can look at replacing the current code in 
sagemath with this newer version.

On Thursday, March 7, 2024 at 9:40:58 PM UTC Sabrina Kunzweiler wrote:

> Thanks for mentioning the related discussion. We checked that in the new 
> implementation in Giacomo's repository, this issue is solved. 
>
> In the example that was given in the chat, we obtain the following output:
> ```
> sage: R. = QQ[]
> sage: f = 144*x^6 - 240*x^5 + 148*x^4 + 16*x^3 - 16*x^2 - 4*x + 1
> sage: H = HyperellipticCurveNew(f)
> sage: J = Jacobian(H)
> sage: P = J(H([0,1]))-J(H([0,-1]))
> sage: (5*P).is_zero()
> False
> sage: 5*P
> (1, 0 : 2)
> ```
> Here, this means $$ 5 P = (1:12:0) - (1:-12:0) $$ which coincides with the 
> result from magma. 
>
>
> Kwankyu Lee schrieb am Donnerstag, 7. März 2024 um 05:44:33 UTC+1:
>
>> It's still here: https://github.com/sagemath/sage/issues/32024
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/sage-devel/16695996-c9bc-4a08-a1a4-37179e7a8956n%40googlegroups.com.

Re: [sage-devel] Help and Advice | Arithmetic of Jacobians in the Split/Real Model is Broken

[Giacomo Pope]

Thanks John.

>From my minimal local testing I have at least that

- random sampling on the jacobian can find every point on the jacobian 
(there is a fast method using sums of J(P) for P on the curve, but this 
doesnt guarantee all elements of the jacobian are found)
- that multiplication by any random point by the order of the jacobian 
gives the zero element
- that every element has an order dividing the order of the jacobian 
computed using `order_from_multiple`
- that this seems to work for char 2 and odd char providing there are two 
points at infinity (base assumption).
- that the implementation of negation works as expected and for random 
points D - D is always zero

Now that these basic features are in place and we have addition, 
subtraction and multiplication by scalars, I want to make sure the 
functions are as simple as possible to aid with the integration into sage.

On Wednesday, March 6, 2024 at 1:52:26 PM UTC John Cremona wrote:

> I'm going to forward this to sage-nt as there may be people who read that 
> but not this.
>
> Meanwhile I would recommend getting something to work correctly before 
> worrying too much about what is most efficient.
>
>
> John
>
> On Wed, 6 Mar 2024, 12:52 Giacomo Pope,  wrote:
>
>> *=== Summary*
>>
>> Arithmetic of divisors for Jacobians of hyperelliptic curves with two 
>> points at infinity is not currently properly supported for SageMath. Worse, 
>> there are no checks or error handling and the output of the arithmetic is 
>> simply wrong.
>>
>> Minimal example:
>>
>> sage: R. = PolynomialRing(GF(11))
>> sage: f = x^6 + x + 1
>> sage: H = HyperellipticCurve(f)
>> sage: J = H.jacobian()
>> sage: D = J(H.lift_x(1))
>> sage: jacobian_order = sum(H.frobenius_polynomial())
>> sage: jacobian_order * D
>> (x + 10, y + 5) # this should be (1)
>>
>> I wrote about this as a GitHub issue as well: 
>> https://github.com/sagemath/sage/issues/37109 but I am now coming to 
>> sage-devel as I have *some* progress and want to try and have advice / 
>> conversation about how we can improve this.
>>
>> *=== Suggestion*
>>
>> I have been working on a small proof of concept for arithmetic with 
>> Sabrina Kunzweiler using sage (
>> https://github.com/GiacomoPope/HyperellipticCurves) which has been 
>> implemented following the balanced strategy of the following paper:
>>
>> Efficient Hyperelliptic Arithmetic using Balanced Representation for 
>> Divisors
>> Steven D. Galbraith, Michael Harrison, and David J. Mireles Morales
>> https://www.math.auckland.ac.nz/~sgal018/ANTS08.pdf
>>
>> This is similar but distinct to what Magma uses for arithmetic. 
>> Essentially the arithmetic is the same as Cantor, but to ensure a unique 
>> representation of the zero degree divisors there is an integer weight n 
>> together with Mumford polynomials (u, v). By keeping track of this weight 
>> during composition and reduction arithmetic is complete. We can ensure 
>> deg(u) <= g by using composition and reduction at infinity. 
>>
>> This implementation works as I expect and I am happy with it. But getting 
>> it into Sage will be a bigger job. I will try and outline some of the 
>> issues I see but as with everything the unknown unknowns will be the 
>> biggest issue.
>>
>> Minimal working implementation: 
>> https://github.com/GiacomoPope/HyperellipticCurves
>>
>> *=== Potential Issues*
>>
>> *Weighted projective models*
>>
>> The balanced representation is naturally tied to a weighted projective 
>> model for the hyperelliptic curve (with weights (1 : 3 : 1)) which is much 
>> less built out than unweighted polynomial rings in sagemath. 
>>
>> Two recent issues with the weighted polynomial ring:
>>
>> https://github.com/sagemath/sage/issues/37155
>> https://github.com/sagemath/sage/issues/37167
>>
>> In our implementation I simply build the weighted projective model in a 
>> normal polynomial ring by computing the correct weights but there could be 
>> further complications if we really try and implement this "properly" from 
>> the construction class in sage. This feels like the first big blocker.
>>
>> A "concrete" example of why we need this is when writing down the two 
>> points at infinity for the real model. These are not "points" on the 
>> current curve because the projective model is different and causes a range 
>> of issues.
>>
>> *Constructing the right classes*
>>
>> I think aside from maybe needing additional methods on the hyperelliptic 
>> cur

Re: [sage-devel] sensational bug!

[Giacomo Pope]

This was also something I saw 
in: https://github.com/sagemath/sage/issues/37455 and I haven't been able 
to locally reproduce it either.

On Wednesday, March 6, 2024 at 12:18:51 PM UTC dmo...@deductivepress.ca 
wrote:

> I think this is issue 
> #35715  on the sagemath 
> github. So I think the discussion should go there.
>
> On Wednesday, March 6, 2024 at 6:53:04 AM UTC-5 Martin R wrote:
>
>> It is not my machine, just the bot, see the link above.
>>
>> On Wednesday 6 March 2024 at 12:42:19 UTC+1 Dima Pasechnik wrote:
>>
>>> Not confirmed here, either. We need more details about the machine, the 
>>> OS, the setup, etc.
>>>
>>> Is it reproducible, i.e. if you repeat this command, does it fail again?
>>>
>>> Dima
>>>
>>> On Wed, Mar 6, 2024 at 9:47 AM 'Martin R' via sage-devel <
>>> sage-...@googlegroups.com> wrote:
>>>
 On 
 https://github.com/sagemath/sage/actions/runs/8168335359/job/22330264302?pr=37545

 I see

 sage -t --long --random-seed=286735480429121101562228604801325644303 
 src/sage/rings/tests.py 
 ** 
 Error: Failed example:: Got: Random testing has revealed a problem in 
 test_karatsuba_multiplication 
 Please report this bug! You may be the first 
 person in the world to have seen this problem. 
 Please include this random seed in your bug report: 
 Random seed: 305806809989734915896642073966608392384 
 ValueError('Multiplication failed') 
 test_karatsuba_multiplication(QQbar, 3, 3, numtests=2) # long time, 
 needs sage.rings.number_field 
 Expected nothing 
 Got: 
 Random testing has revealed a problem in test_karatsuba_multiplication 
 Please report this bug! You may be the first 
 person in the world to have seen this problem. 
 Please include this random seed in your bug report: 
 Random seed: 305806809989734915896642073966608392384 
 ValueError('Multiplication failed') 

 -- 
 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/522bab60-a7e7-47f4-8d17-2c8ce329b85dn%40googlegroups.com
  
 
 .

>>>

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/sage-devel/be384c9a-c5b4-40e7-97d2-a518a60ef756n%40googlegroups.com.

[sage-devel] Help and Advice | Arithmetic of Jacobians in the Split/Real Model is Broken

[Giacomo Pope]

*=== Summary*

Arithmetic of divisors for Jacobians of hyperelliptic curves with two 
points at infinity is not currently properly supported for SageMath. Worse, 
there are no checks or error handling and the output of the arithmetic is 
simply wrong.

Minimal example:

sage: R. = PolynomialRing(GF(11))
sage: f = x^6 + x + 1
sage: H = HyperellipticCurve(f)
sage: J = H.jacobian()
sage: D = J(H.lift_x(1))
sage: jacobian_order = sum(H.frobenius_polynomial())
sage: jacobian_order * D
(x + 10, y + 5) # this should be (1)

I wrote about this as a GitHub issue as 
well: https://github.com/sagemath/sage/issues/37109 but I am now coming to 
sage-devel as I have *some* progress and want to try and have advice / 
conversation about how we can improve this.

*=== Suggestion*

I have been working on a small proof of concept for arithmetic with Sabrina 
Kunzweiler using sage (https://github.com/GiacomoPope/HyperellipticCurves) 
which has been implemented following the balanced strategy of the following 
paper:

Efficient Hyperelliptic Arithmetic using Balanced Representation for 
Divisors
Steven D. Galbraith, Michael Harrison, and David J. Mireles Morales
https://www.math.auckland.ac.nz/~sgal018/ANTS08.pdf

This is similar but distinct to what Magma uses for arithmetic. Essentially 
the arithmetic is the same as Cantor, but to ensure a unique representation 
of the zero degree divisors there is an integer weight n together with 
Mumford polynomials (u, v). By keeping track of this weight during 
composition and reduction arithmetic is complete. We can ensure deg(u) <= g 
by using composition and reduction at infinity. 

This implementation works as I expect and I am happy with it. But getting 
it into Sage will be a bigger job. I will try and outline some of the 
issues I see but as with everything the unknown unknowns will be the 
biggest issue.

Minimal working implementation: 
https://github.com/GiacomoPope/HyperellipticCurves

*=== Potential Issues*

*Weighted projective models*

The balanced representation is naturally tied to a weighted projective 
model for the hyperelliptic curve (with weights (1 : 3 : 1)) which is much 
less built out than unweighted polynomial rings in sagemath. 

Two recent issues with the weighted polynomial ring:

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

In our implementation I simply build the weighted projective model in a 
normal polynomial ring by computing the correct weights but there could be 
further complications if we really try and implement this "properly" from 
the construction class in sage. This feels like the first big blocker.

A "concrete" example of why we need this is when writing down the two 
points at infinity for the real model. These are not "points" on the 
current curve because the projective model is different and causes a range 
of issues.

*Constructing the right classes*

I think aside from maybe needing additional methods on the hyperelliptic 
curve, once the projective model is right and points on the curve are well 
defined for all cases. I do not have any intuition on whether the balanced 
model will for example have issues with the p-Adic implementation as I have 
no experience in this area.

Using the language 
of https://www.math.auckland.ac.nz/~sgal018/crypto-book/ch10.pdf, the 
"imaginary" or ramified model is what is currently well supported in sage. 
Here we have only one point at infinity. For the split or "real" model, 
this is what is sketched out in my own repo and what I want to address, 
there are two distinct points at infinity. Proper representation of the 
degree zero divisors needs more than (u, v) for unique representation. For 
the inert model, where there are no points at infinity over the base ring, 
I think we should simply reject all arithmetic and force the user to change 
the curve model or work over a field extension. This is what Magma does.

This leads me to the Jacobian. I believe we should have a 
`Jacobian_ramified` and `Jacobian_split` class and `Jacobian_inert`, each 
with their own efficient (or missing) arithmetic and representation (the 
inert case simply has NotImplemented for arithmetic. The hyperelliptic 
curve class should know the number of points at infinity and then select 
this class without user input (so H.jacobian() does whatever the use 
expects).

This will end up being a fairly large refactoring of the current code and I 
believe this will be hazardous work! 

*=== Backwards compatibility *

This is where I am most worried. I am familiar with and probably capable of 
working with the curves over finite fields and building sensible classes 
which allow for efficient arithmetic for odd and even genus for the 
ramified and split models, but I know there's a lot more maths than the 
arithmetic of these divisors and I need to ensure everything which everyone 
needs works in the same way while making all these changes.

*=== Next steps*

This feels like a relati

Re: [sage-devel] VOTE: Use "CI Fix" label for merging into continuous integration runs

[Giacomo Pope]

+1

On Monday, March 4, 2024 at 1:57:48 PM UTC Dima Pasechnik wrote:

> +1
>
> On Mon, Mar 4, 2024 at 8:43 AM David Roe  wrote:
>
>> The following proposal has been made several times the last few weeks: in 
>> PR #37428 , in this thread 
>>  and then in this 
>> thread .  It is 
>> orthogonal to the ongoing vote in this thread 
>> .  With no further 
>> discussion, I'm calling a vote.
>>
>> *Background*
>>
>> Starting in Sage 10.2, PRs with the Blocker label have been merged into 
>> all other PRs before running CI; see the changelog 
>> 
>>  
>> and this post 
>>  
>> for more details.  This has led to disagreements about whether this label 
>> should be applied.
>>
>> *Proposal*
>> We use "CI Fix" rather than Blocker to determine whether an open PR 
>> should be merged before running CI.  Blocker will retain its previous 
>> meaning of a PR that should be merged before the next release is finished.  
>> The process below describes how to resolve disagreements about whether the 
>> "CI Fix" label should be applied.
>> a. Only PRs with positive review should be marked with the "CI Fix" 
>> label.  This should be done if both author and reviewer agree that it is 
>> appropriate, and a rationale should be given in a comment on the ticket.
>> b. If a PR becomes disputed (as described in this proposal 
>> ), the "CI Fix" 
>> status can be voted on separately upon request; otherwise it should be 
>> applied if and only if positive review is applied.
>>
>> Voting will be open until Wednesday, March 13.
>> David
>>
>>
>> -- 
>> You received this message because you are subscribed to the Google Groups 
>> "sage-devel" group.
>> To unsubscribe from this group and stop receiving emails from it, send an 
>> email to sage-devel+...@googlegroups.com.
>> To view this discussion on the web visit 
>> https://groups.google.com/d/msgid/sage-devel/CAChs6_mYLUWXMU6AZKJGPKd2oz0AC_qAUjnGoD9Q9yixzNBC2w%40mail.gmail.com
>>  
>> 
>> .
>>
>

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/sage-devel/77cc05b2-1c52-4aae-80ca-4d0ec0830e2dn%40googlegroups.com.

Re: [sage-devel] Re: Degree of the zero polynomial ring for `LaurentPolynomialRing`

[Giacomo Pope]

As an aside, the univariate LaurentPolynomialRing had a notion of 
`valuation` but the multivariate one didn't...

In the PR: https://github.com/sagemath/sage/pull/37490 I added random 
elements but also a notion of valuation() for the multivariate case and 
just made it act similarly to the univariate one.

On Friday, March 1, 2024 at 6:18:01 PM UTC Nils Bruin wrote:

> On Friday 1 March 2024 at 09:49:15 UTC-8 Giacomo Pope wrote:
>
> Following this discussion, I have made a draft PR to change the degree for 
> *only* the LaurentPolynomialRing and I will see if the CI detects anything.
>
> https://github.com/sagemath/sage/pull/37513
>
> I agree that if we change the LaurentPolynomialRing we should also change 
> the `LaurentSeriesRing`, at the moment `LazyLaurentSeriesRing` has no 
> method `degree()` but *does* have a `valuation()` method... so this is odd.
>
>
> OK, let's keep it that way then! I don't think there is a notion on 
> LaurentSeriesRing that deserves the name "degree". Sorry about mixing that 
> one in. I thought it existed. And I think it does:
>
>  sage: R.=LaurentSeriesRing(QQ)
> sage: z=R(0)
> sage: z.valuation()
> +Infinity
> sage: z.degree()
> -1
>
> but if it's not documented, perhaps we can just ignore it.
>

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/sage-devel/a1a59d64-4f6a-46da-9ee4-5a414d612918n%40googlegroups.com.

Re: [sage-devel] Re: Degree of the zero polynomial ring for `LaurentPolynomialRing`

[Giacomo Pope]

Following this discussion, I have made a draft PR to change the degree for 
*only* the LaurentPolynomialRing and I will see if the CI detects anything.

https://github.com/sagemath/sage/pull/37513

I agree that if we change the LaurentPolynomialRing we should also change 
the `LaurentSeriesRing`, at the moment `LazyLaurentSeriesRing` has no 
method `degree()` but *does* have a `valuation()` method... so this is odd.

On Friday, March 1, 2024 at 5:29:53 PM UTC Martin R wrote:

> Could you expand on 'the whole valuation interpretation of "degree" goes 
> out of the window'?  What do you mean with "valuation interpretation"?
>
> Is raising an exception out of the question?
>
> On Friday 1 March 2024 at 18:11:40 UTC+1 Nils Bruin wrote:
>
>> On Friday 1 March 2024 at 04:26:43 UTC-8 Dima Pasechnik wrote:
>>  
>>
>> It seems that exactly the same algorithm will work (I didn't check this!) 
>> for Laurent polynomials (they still form a Euclidean domain), and there you 
>> better set degree(0)=-oo, otherwise it's going to be a problem.
>>
>> I think it's been established 
>> that LaurentPolynomialRing(QQ,'x').zero().degree() == -1 is problematic. 
>> With the definition that (1/x).degree() == -1 it clearly is.
>>
>> I think the question is more: do we have enough evidence that setting 
>> degree(0) == -oo for *all* polynomial rings is significantly better (if 
>> better at all) that it's worth the pain and incompatibilities that would 
>> ensue from changing the rest of sage as well? That's not so clear to me. 
>> From the perspective of multivariate polynomials, the whole valuation 
>> interpretation of "degree" goes out of the window, so there "-1" is largely 
>> available and quite possibly used extensively by the underlying libraries.
>>
>> I guess one could see what happens if the change is made to Laurent 
>> polynomials (and Laurent series as well, perhaps?). Based on how that goes 
>> one could re-evaluate degrees of 0 polynomials in other polynomial rings.
>>
>> Alternatively, we could deprecate degree on them in favour of using 
>> valuation-inspired terms instead, where the extension val(0)=oo is more 
>> universal. As Oscar's example in Matlab shows, the concept of degree gets 
>> (mis)used for other, more implementation-oriented definitions as well, so 
>> perhaps the term should just be avoided for Laurent polynomials.
>>
>

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/sage-devel/6a79e795-60d5-4385-b2fb-79e53be18bc1n%40googlegroups.com.

Re: [sage-devel] Re: Degree of the zero polynomial ring for `LaurentPolynomialRing`

[Giacomo Pope]

There seem to be two things we could do here:

1. Have some form of vote / discussion on whether the degree of the zero 
polynomial should *ever* be -1
2. Modify the degree calls for the LaurentSeries and LaurentPolynomialRing 
(maybe other Laurent* which I am unfamiliar with) to have the zero 
polynomial have degree -Infinity.

Option 1 may be cleaner in the long run, but I assume will cause issues for 
more people in the short term. Option 2 seems fairly harmless and there's 
no good argument for degree -1 in this case.

If anyone is interested in option 2, I will find time to make a PR to do 
this, but I will not start this work without other people's input as this 
is not code I am familiar with using and so I don't know what people could 
be relying on.
On Wednesday, February 28, 2024 at 6:41:48 PM UTC Dima Pasechnik wrote:

> On Wed, Feb 28, 2024 at 5:00 PM Nils Bruin  wrote:
>
>> On Wednesday 28 February 2024 at 08:03:45 UTC-8 Giacomo Pope wrote:
>>
>>
>> I don't know the history of this choice or what we should be doing 
>> generally. -1 for polynomials with only positive degree seems like a 
>> computer science workaround, but for the LaurentPolynomialRing it just 
>> seems wrong?
>>
>>
>> I think it's more than just a CS workaround. It has its roots in 
>> dimension considerations: the space of polynomials of degree at most d is 
>> (d+1)-dimensional. WIth that convention, 0 having degree -1 makes perfect 
>> sense.
>>
>
> well, it's the convention used in Singular.
> But GAP and Macaulay2 use -infinity.
>
> The arguments for -infinity:
>
> 1) degree of the product should be the sum of degrees; so it's got to be 
> infinite.
> 2) it should be -infinity, to make sense of the rule that if you do 
> division f/g with remainder r,
> the degree of the remainder should be less than the deg(r)<=deg(f), but if 
> r=0 then the only way
> to get this is to use -infinity.
>
> Dima
>  
>
>>
>> For deg = - ord_infty it should definitely be -oo, though, and for 
>> Laurent polynomials the dimension argument doesn't work.
>>
>> -- 
>>
> 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/ac40d2e7-5e71-43e1-8914-869081f9bdd9n%40googlegroups.com
>>  
>> <https://groups.google.com/d/msgid/sage-devel/ac40d2e7-5e71-43e1-8914-869081f9bdd9n%40googlegroups.com?utm_medium=email&utm_source=footer>
>> .
>>
>

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/sage-devel/6d95b253-fb17-4e2f-a61c-c723737774e8n%40googlegroups.com.

Re: [sage-devel] Re: Degree of the zero polynomial ring for `LaurentPolynomialRing`

[Giacomo Pope]

Not a "maths" why, but I know anything which uses singular currently 
returns -1 because of the following snippet

cdef long singular_polynomial_deg(poly *p, poly *x, ring *r) noexcept:
cdef long _deg, deg
cdef int dummy

deg = -1
_deg = -1
if p == NULL:
return -1
...

I don't know the history of this choice or what we should be doing 
generally. -1 for polynomials with only positive degree seems like a 
computer science workaround, but for the LaurentPolynomialRing it just 
seems wrong?
On Wednesday, February 28, 2024 at 3:29:25 PM UTC Dima Pasechnik wrote:

> in the polynomial case, the usual convention is deg(0)=-infinity
> I don't know why Sage uses -1 instead:
> R.=QQ[]
> f=0*x*y
> f.degree()
>
> gives -1.
>
> On Wed, Feb 28, 2024 at 1:50 PM 'Martin R' via sage-devel <
> sage-...@googlegroups.com> wrote:
>
>> Sorry, I confused it with valuation, but I guess it is still a related 
>> question.
>> On Wednesday 28 February 2024 at 14:36:35 UTC+1 Giacomo Pope wrote:
>>
>>> This is not what I see on the current beta:
>>>
>>> sage: R. = LaurentSeriesRing(QQ)
>>> sage: R.zero().degree()
>>> -1
>>> sage: R. = LazyLaurentSeriesRing(QQ)
>>> sage: R.zero().degree()
>>>
>>> ---
>>> AttributeErrorTraceback (most recent call 
>>> last)
>>> Cell In[4], line 1
>>> > 1 R.zero().degree()
>>>
>>> File ~/sage/sage/src/sage/structure/element.pyx:489, in 
>>> sage.structure.element.Element.__getattr__()
>>> 487 AttributeError: 
>>> 'LeftZeroSemigroup_with_category.element_class' object has no attribute 
>>> 'blah_blah'...
>>> 488 """
>>> --> 489 return self.getattr_from_category(name)
>>> 490 
>>> 491 cdef getattr_from_category(self, name) noexcept:
>>>
>>> File ~/sage/sage/src/sage/structure/element.pyx:502, in 
>>> sage.structure.element.Element.getattr_from_category()
>>> 500 else:
>>> 501 cls = P._abstract_element_class
>>> --> 502 return getattr_from_other_class(self, cls, name)
>>> 503 
>>> 504 def __dir__(self):
>>>
>>> File ~/sage/sage/src/sage/cpython/getattr.pyx:357, in 
>>> sage.cpython.getattr.getattr_from_other_class()
>>> 355 dummy_error_message.cls = type(self)
>>> 356 dummy_error_message.name = name
>>> --> 357 raise AttributeError(dummy_error_message)
>>> 358 cdef PyObject* attr = instance_getattr(cls, name)
>>> 359 if attr is NULL:
>>>
>>> AttributeError: 'LazyLaurentSeriesRing_with_category.element_class' 
>>> object has no attribute 'degree'
>>>
>>> On Wednesday, February 28, 2024 at 12:05:32 PM UTC Martin R wrote:
>>>
>>>> LazyLaurentSeriesRing(QQ) currently gives +Infinity.
>>>>
>>>> On Wednesday 28 February 2024 at 12:50:45 UTC+1 Giacomo Pope wrote:
>>>>
>>>>> While chasing various bugs which appeared in the CI, I ended up adding 
>>>>> a small method for computing random elements for the 
>>>>> LaurentPolynomialRing 
>>>>> class.
>>>>>
>>>>> When writing randomised testing I got myself confused about the degree 
>>>>> of the zero polynomial. For the univariate and multivariate polynomial 
>>>>> rings, we currently use that the degree for 0 (both R(0).degree() as well 
>>>>> as R(0).degree(x)) is -1. This is unambiguous for the case of these types.
>>>>>
>>>>> However for the LaurentPolynomialRings, a polynomial with negative 
>>>>> valuation is very natural. For example the following code snippet shows 
>>>>> the 
>>>>> ambiguity.
>>>>>
>>>>> sage: L. = LaurentPolynomialRing(QQ)
>>>>> sage: f = (1/x); f
>>>>> x^-1
>>>>> sage: f.degree()
>>>>> -1
>>>>> sage: L.zero().degree()
>>>>> -1
>>>>>
>>>>> I don't feel familiar enough with the mathematics here and the usual 
>>>>> use cases in sage to offer a PR "fixing" this, or whether it even needs 
>>>>> fixing. However, I got confused so I thought maybe others might get 
>>>>> confused and someone on this list might 

[sage-devel] Re: Degree of the zero polynomial ring for `LaurentPolynomialRing`

[Giacomo Pope]

Ahh ok, thank you. Considering the following output I think a PR to make 
the degree of zero for these Laurent classes -Infinity is reasonable?

```
sage: R. = LaurentSeriesRing(QQ)
sage: R.zero().valuation()
+Infinity
sage: R.zero().degree()
-1
sage: 
sage: R. = LaurentPolynomialRing(QQ)
sage: R.zero().valuation()
+Infinity
sage: R.zero().degree()
-1
sage: 
sage: R. = LazyLaurentSeriesRing(QQ)
sage: R.zero().valuation()
+Infinity
sage: R.zero().degree()
# Errors



On Wednesday, February 28, 2024 at 1:50:23 PM UTC Martin R wrote:

> Sorry, I confused it with valuation, but I guess it is still a related 
> question.
> On Wednesday 28 February 2024 at 14:36:35 UTC+1 Giacomo Pope wrote:
>
>> This is not what I see on the current beta:
>>
>> sage: R. = LaurentSeriesRing(QQ)
>> sage: R.zero().degree()
>> -1
>> sage: R. = LazyLaurentSeriesRing(QQ)
>> sage: R.zero().degree()
>>
>> ---
>> AttributeErrorTraceback (most recent call 
>> last)
>> Cell In[4], line 1
>> > 1 R.zero().degree()
>>
>> File ~/sage/sage/src/sage/structure/element.pyx:489, in 
>> sage.structure.element.Element.__getattr__()
>> 487 AttributeError: 
>> 'LeftZeroSemigroup_with_category.element_class' object has no attribute 
>> 'blah_blah'...
>> 488 """
>> --> 489 return self.getattr_from_category(name)
>> 490 
>> 491 cdef getattr_from_category(self, name) noexcept:
>>
>> File ~/sage/sage/src/sage/structure/element.pyx:502, in 
>> sage.structure.element.Element.getattr_from_category()
>> 500 else:
>> 501 cls = P._abstract_element_class
>> --> 502 return getattr_from_other_class(self, cls, name)
>> 503 
>> 504 def __dir__(self):
>>
>> File ~/sage/sage/src/sage/cpython/getattr.pyx:357, in 
>> sage.cpython.getattr.getattr_from_other_class()
>> 355 dummy_error_message.cls = type(self)
>> 356 dummy_error_message.name = name
>> --> 357 raise AttributeError(dummy_error_message)
>> 358 cdef PyObject* attr = instance_getattr(cls, name)
>> 359 if attr is NULL:
>>
>> AttributeError: 'LazyLaurentSeriesRing_with_category.element_class' 
>> object has no attribute 'degree'
>>
>> On Wednesday, February 28, 2024 at 12:05:32 PM UTC Martin R wrote:
>>
>>> LazyLaurentSeriesRing(QQ) currently gives +Infinity.
>>>
>>> On Wednesday 28 February 2024 at 12:50:45 UTC+1 Giacomo Pope wrote:
>>>
>>>> While chasing various bugs which appeared in the CI, I ended up adding 
>>>> a small method for computing random elements for the LaurentPolynomialRing 
>>>> class.
>>>>
>>>> When writing randomised testing I got myself confused about the degree 
>>>> of the zero polynomial. For the univariate and multivariate polynomial 
>>>> rings, we currently use that the degree for 0 (both R(0).degree() as well 
>>>> as R(0).degree(x)) is -1. This is unambiguous for the case of these types.
>>>>
>>>> However for the LaurentPolynomialRings, a polynomial with negative 
>>>> valuation is very natural. For example the following code snippet shows 
>>>> the 
>>>> ambiguity.
>>>>
>>>> sage: L. = LaurentPolynomialRing(QQ)
>>>> sage: f = (1/x); f
>>>> x^-1
>>>> sage: f.degree()
>>>> -1
>>>> sage: L.zero().degree()
>>>> -1
>>>>
>>>> I don't feel familiar enough with the mathematics here and the usual 
>>>> use cases in sage to offer a PR "fixing" this, or whether it even needs 
>>>> fixing. However, I got confused so I thought maybe others might get 
>>>> confused and someone on this list might have a suggestion.
>>>>
>>>> I think the "usual" suggestion would be to have the degree as -infty, 
>>>> but then there's a question about whether this should be done for other 
>>>> polynomial rings...
>>>>
>>>> I made an issue for this on GitHub too:
>>>>
>>>> https://github.com/sagemath/sage/issues/37491
>>>>
>>>

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/sage-devel/1d06c246-f250-4c37-997e-066ddaefbaean%40googlegroups.com.

[sage-devel] Re: Degree of the zero polynomial ring for `LaurentPolynomialRing`

[Giacomo Pope]

This is not what I see on the current beta:

sage: R. = LaurentSeriesRing(QQ)
sage: R.zero().degree()
-1
sage: R. = LazyLaurentSeriesRing(QQ)
sage: R.zero().degree()
---
AttributeErrorTraceback (most recent call last)
Cell In[4], line 1
> 1 R.zero().degree()

File ~/sage/sage/src/sage/structure/element.pyx:489, in 
sage.structure.element.Element.__getattr__()
487 AttributeError: 
'LeftZeroSemigroup_with_category.element_class' object has no attribute 
'blah_blah'...
488 """
--> 489 return self.getattr_from_category(name)
490 
491 cdef getattr_from_category(self, name) noexcept:

File ~/sage/sage/src/sage/structure/element.pyx:502, in 
sage.structure.element.Element.getattr_from_category()
500 else:
501 cls = P._abstract_element_class
--> 502 return getattr_from_other_class(self, cls, name)
503 
504 def __dir__(self):

File ~/sage/sage/src/sage/cpython/getattr.pyx:357, in 
sage.cpython.getattr.getattr_from_other_class()
355 dummy_error_message.cls = type(self)
356 dummy_error_message.name = name
--> 357 raise AttributeError(dummy_error_message)
358 cdef PyObject* attr = instance_getattr(cls, name)
359 if attr is NULL:

AttributeError: 'LazyLaurentSeriesRing_with_category.element_class' object 
has no attribute 'degree'

On Wednesday, February 28, 2024 at 12:05:32 PM UTC Martin R wrote:

> LazyLaurentSeriesRing(QQ) currently gives +Infinity.
>
> On Wednesday 28 February 2024 at 12:50:45 UTC+1 Giacomo Pope wrote:
>
>> While chasing various bugs which appeared in the CI, I ended up adding a 
>> small method for computing random elements for the LaurentPolynomialRing 
>> class.
>>
>> When writing randomised testing I got myself confused about the degree of 
>> the zero polynomial. For the univariate and multivariate polynomial rings, 
>> we currently use that the degree for 0 (both R(0).degree() as well as 
>> R(0).degree(x)) is -1. This is unambiguous for the case of these types.
>>
>> However for the LaurentPolynomialRings, a polynomial with negative 
>> valuation is very natural. For example the following code snippet shows the 
>> ambiguity.
>>
>> sage: L. = LaurentPolynomialRing(QQ)
>> sage: f = (1/x); f
>> x^-1
>> sage: f.degree()
>> -1
>> sage: L.zero().degree()
>> -1
>>
>> I don't feel familiar enough with the mathematics here and the usual use 
>> cases in sage to offer a PR "fixing" this, or whether it even needs fixing. 
>> However, I got confused so I thought maybe others might get confused and 
>> someone on this list might have a suggestion.
>>
>> I think the "usual" suggestion would be to have the degree as -infty, but 
>> then there's a question about whether this should be done for other 
>> polynomial rings...
>>
>> I made an issue for this on GitHub too:
>>
>> https://github.com/sagemath/sage/issues/37491
>>
>

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/sage-devel/e245cd6a-a18b-4d72-bf55-d55d8d699d5dn%40googlegroups.com.

[sage-devel] Degree of the zero polynomial ring for `LaurentPolynomialRing`

[Giacomo Pope]

While chasing various bugs which appeared in the CI, I ended up adding a 
small method for computing random elements for the LaurentPolynomialRing 
class.

When writing randomised testing I got myself confused about the degree of 
the zero polynomial. For the univariate and multivariate polynomial rings, 
we currently use that the degree for 0 (both R(0).degree() as well as 
R(0).degree(x)) is -1. This is unambiguous for the case of these types.

However for the LaurentPolynomialRings, a polynomial with negative 
valuation is very natural. For example the following code snippet shows the 
ambiguity.

sage: L. = LaurentPolynomialRing(QQ)
sage: f = (1/x); f
x^-1
sage: f.degree()
-1
sage: L.zero().degree()
-1

I don't feel familiar enough with the mathematics here and the usual use 
cases in sage to offer a PR "fixing" this, or whether it even needs fixing. 
However, I got confused so I thought maybe others might get confused and 
someone on this list might have a suggestion.

I think the "usual" suggestion would be to have the degree as -infty, but 
then there's a question about whether this should be done for other 
polynomial rings...

I made an issue for this on GitHub too:

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

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/sage-devel/0efa0dd8-b322-4896-b9af-a88effeaa195n%40googlegroups.com.

Re: [sage-devel] Re: Labels and Reviewing

[Giacomo Pope]

Apologies for the basic question in this thread, but recently I have seen 
lots of conversation about the different labels and I want to clarify 
something for myself.

In the past few PR I have made for Sage, randomised testing has uncovered 
(usually) trivial bugs. I then write new PRs to fix these bugs.

If there is code causing CI failure in random testing, should I mark the 
fix for this as a "blocker", even if the chance of this failure is small? I 
don't want to be melodramatic in my PR for fixes but I also want to make 
sure I'm labelling things as expected,

On Wednesday, February 28, 2024 at 6:08:20 AM UTC David Roe wrote:

> On Wed, Feb 28, 2024 at 1:01 AM Kwankyu Lee  wrote:
>
>> Thank you for making progress on these urgent issues. I suggest the 
>> following:
>>
>> 1. Open two other new threads, each of which is for voting on each 
>> proposal. 
>> 2. On a proposal, it should be clear that *a positive vote (+1) is for 
>> the whole proposal,* and if one is negative to any part of the proposal, 
>> (s)he should give a negative vote (-1).  
>>
>
> Voting threads seem reasonable.  I'll wait a day or two to see if people 
> have any final comments before voting.
>  
>
>> 3. A proposal is accepted if the number of positive votes is at least 
>> twice of the number of the negative votes.
>>
>
> Despite the fact that we're asking for this threshold in voting on a PR, 
> the standard for votes on proposals on sage-devel is just a plain majority 
> (though of course I hope that we can come to a 2-1 consensus!).
>
> A minor suggestion for Proposal 2: for the label to be readable, I suggest 
>> "CI fix" for the name of the label (a blank between words). 
>>
>
> I'm happy to adjust the label to be "CI fix."
>  
>
>> We may use this thread to get more comments on the Proposals before 
>> opening voting threads.
>>
>> -- 
>> 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/554961a0-4ace-4317-bfcf-55b6a128bcden%40googlegroups.com
>>  
>> 
>> .
>>
>

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/sage-devel/b84b22d2-9b57-460c-9f8d-5f8ebe2f982en%40googlegroups.com.

Re: [sage-devel] Need advice on PR attempting to modify coercion for Python int type

[Giacomo Pope]

To follow up on this, with a few more tweaks I have all the CI passing. If 
a coercion expert wants to review the PR I would appreciate that, but I'm 
hopeful that this change is a net positive for sagemath.

On Tuesday, February 20, 2024 at 2:53:26 PM UTC Giacomo Pope wrote:

> Yes, I tried locally and although the little example for elliptic curves 
> works and shows a "fixed" issue with multiplication by an int, several new 
> multiplications fail.
>
> Picking one of these tests at random (the whole logos failure is 40Mb!!) I 
> think I have identified one of the issues. 
>
> Before I was accessing the Integer class from _Integer from the snippet 
> from parent.pyx. However this seems to be None for certain files and so my 
> coercion was breaking. By instead importing ZZ directly from the right file 
> this seems tp have fixed some tests so I will commit this and check how the 
> whole CI does. I'm not convinced what I did it "best" yet but I will be 
> interested to see if my breaking change was simply a missing import for 
> certain files.
>
>
>
> On Tuesday, February 20, 2024 at 2:17:57 PM UTC Dima Pasechnik wrote:
>
>> Did you try running tests locally?
>> Our CI sometimes acts up
>>
>>
>> On 20 February 2024 12:49:03 GMT, Giacomo Pope  
>> wrote:
>>
>>> Hey all, 
>>>
>>> I have been trying to work on a fix for scalar multiplication of points 
>>> on elliptic curves over finite fields. The issue at the moment is that when 
>>> we multiply by a Sage type, such as an Integer, the coercion system 
>>> discovers the action via `_acted_upon_` and a fast method via Pari is 
>>> called.
>>>
>>> However, when the scalar multiplication is called with a Python `int`, 
>>> then this falls through to `IntegerMulAction` which instead performs the 
>>> scalar multiplication using Sage defined addition and doubling which is 
>>> much slower (about 10x slower by the timing I have in the PR).
>>>
>>> My initial fix was to simply add a `__mul__` method for elliptic curve 
>>> points, but through conversations with the reviewers of the PR, instead a 
>>> fix was proposed within the `discover_action()` method, which attempts a 
>>> precomposition from python `int` to Sage `Integer` which then allows for 
>>> the discovery of the action for `_acted_upon_`.
>>>
>>> This fix "worked" in that the action works fine for my elliptic curve 
>>> example and the speed for `int` and `Integer` now are both fast, but the CI 
>>> tests run and it seems my change has totally broken Sage.
>>>
>>> I really want to do the correct fix here, but I don't understand how 
>>> much change could have broken so much internally as I thought my fix would 
>>> only discover good actions... I would really appreciate some support in 
>>> finding the right solution for this.
>>>
>>> A link to the PR is here: https://github.com/sagemath/sage/pull/37369
>>>
>>> Thank you! 
>>>
>>>

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/sage-devel/c33194b9-6d7d-497c-ae55-040dcc04c250n%40googlegroups.com.

Re: [sage-devel] Need advice on PR attempting to modify coercion for Python int type

[Giacomo Pope]

Yes, I tried locally and although the little example for elliptic curves 
works and shows a "fixed" issue with multiplication by an int, several new 
multiplications fail.

Picking one of these tests at random (the whole logos failure is 40Mb!!) I 
think I have identified one of the issues. 

Before I was accessing the Integer class from _Integer from the snippet 
from parent.pyx. However this seems to be None for certain files and so my 
coercion was breaking. By instead importing ZZ directly from the right file 
this seems tp have fixed some tests so I will commit this and check how the 
whole CI does. I'm not convinced what I did it "best" yet but I will be 
interested to see if my breaking change was simply a missing import for 
certain files.



On Tuesday, February 20, 2024 at 2:17:57 PM UTC Dima Pasechnik wrote:

> Did you try running tests locally?
> Our CI sometimes acts up
>
>
> On 20 February 2024 12:49:03 GMT, Giacomo Pope  wrote:
>
>> Hey all, 
>>
>> I have been trying to work on a fix for scalar multiplication of points 
>> on elliptic curves over finite fields. The issue at the moment is that when 
>> we multiply by a Sage type, such as an Integer, the coercion system 
>> discovers the action via `_acted_upon_` and a fast method via Pari is 
>> called.
>>
>> However, when the scalar multiplication is called with a Python `int`, 
>> then this falls through to `IntegerMulAction` which instead performs the 
>> scalar multiplication using Sage defined addition and doubling which is 
>> much slower (about 10x slower by the timing I have in the PR).
>>
>> My initial fix was to simply add a `__mul__` method for elliptic curve 
>> points, but through conversations with the reviewers of the PR, instead a 
>> fix was proposed within the `discover_action()` method, which attempts a 
>> precomposition from python `int` to Sage `Integer` which then allows for 
>> the discovery of the action for `_acted_upon_`.
>>
>> This fix "worked" in that the action works fine for my elliptic curve 
>> example and the speed for `int` and `Integer` now are both fast, but the CI 
>> tests run and it seems my change has totally broken Sage.
>>
>> I really want to do the correct fix here, but I don't understand how much 
>> change could have broken so much internally as I thought my fix would only 
>> discover good actions... I would really appreciate some support in finding 
>> the right solution for this.
>>
>> A link to the PR is here: https://github.com/sagemath/sage/pull/37369
>>
>> Thank you! 
>>
>>

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/sage-devel/9667e799-81ce-4a8c-a575-3ed0a7f7a823n%40googlegroups.com.

[sage-devel] Need advice on PR attempting to modify coercion for Python int type

[Giacomo Pope]

Hey all, 

I have been trying to work on a fix for scalar multiplication of points on 
elliptic curves over finite fields. The issue at the moment is that when we 
multiply by a Sage type, such as an Integer, the coercion system discovers 
the action via `_acted_upon_` and a fast method via Pari is called.

However, when the scalar multiplication is called with a Python `int`, then 
this falls through to `IntegerMulAction` which instead performs the scalar 
multiplication using Sage defined addition and doubling which is much 
slower (about 10x slower by the timing I have in the PR).

My initial fix was to simply add a `__mul__` method for elliptic curve 
points, but through conversations with the reviewers of the PR, instead a 
fix was proposed within the `discover_action()` method, which attempts a 
precomposition from python `int` to Sage `Integer` which then allows for 
the discovery of the action for `_acted_upon_`.

This fix "worked" in that the action works fine for my elliptic curve 
example and the speed for `int` and `Integer` now are both fast, but the CI 
tests run and it seems my change has totally broken Sage.

I really want to do the correct fix here, but I don't understand how much 
change could have broken so much internally as I thought my fix would only 
discover good actions... I would really appreciate some support in finding 
the right solution for this.

A link to the PR is here: https://github.com/sagemath/sage/pull/37369

Thank you! 

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/sage-devel/c9638664-e2a7-49fa-81fa-86d548d6f08fn%40googlegroups.com.