Implement computations in picard groups via global sections of line bundles

[nbruin]

In a bunch of papers, Kamal Khuri Makdisi outlines how standard techniques to compute with coherent sheafs via global sections of their twists can be used to obtain (at least asymptotically) efficient algorthims to compute in the Picard group of an algebraic curve (he outlines Pic^0, but the ideas readily generalize to all of Pic).

A little experimentation shows that these techniques can be fairly efficient in practice as well (and certainly usable!). We'll have to see if the method can be truly competitive with the Hess-type "function field as finite extension of k(x)" approach.

In any case, Kamal's approach is much easier to implement and, thanks to its uniformity, much easier to trust, so at least as a stepping stone, it's useful to have an implementation available.

CC: @pjbruin

Component: algebraic geometry

Keywords: sd86.5

Branch/Commit: u/roed/implement_computations_in_picard_groups_via_global_sections_of_line_bundles @ 1ea07dd

Issue created by migration from https://trac.sagemath.org/ticket/15113

[nbruin]

Attachment: picard_group.sage.gz

first draft version

[nbruin]

comment:1

An example script: this computes on an elliptic curve

sage: load "picard_group.sage"
sage: k=GF(79)
sage: n=2
sage: P.<x,y,z>=k[]
sage: F=x^3+5*z^3-y^2*z
sage: I=plane_curve(F)

The n=2 in this case ends up computing mainly with the "medium model" addflip algorithm, which seems the fastest choice here.

We tell the system about a rational point. This allows the determination of unique representatives of divisor classes, at a small computational cost (which could be eliminated with more careful programming)

sage: I.initpickvector([0,1,0],3)

We define a point. Note that computing in H⁰(O(6*Z)) (which is what we do) doesn't quite give enough room to compute in all of Pic (the strategies implemented have trouble with some degree 2 classes), but we can compute in Pic⁰:

sage: Z=I.point([0,1,0],n)
sage: G=I.point([-1,2,1],n)
sage: P=G-Z

Check what the order of the point should be:

sage: E=EllipticCurve(k,[0,0,0,0,5])
sage: Ept=E([-1,2,1])
sage: Ept.order()
31

And verify that our arithmetic agrees:

sage: 31*P==Z-Z
True
sage: for n in range(100):
...       if n*P == 2*n*P:
...           print n
0
31
62
93

We are about 100 times slower than normal elliptic curve arithmetic, which I think is quite a promising start.

sage: timeit("_=10^30*P")
5 loops, best of 3: 373 ms per loop
sage: timeit("_=10^30*Ept")
125 loops, best of 3: 3.29 ms per loop

A genus 3 example, with 42-torsion

sage: n=4
sage: k.<a>=GF(41)
sage: R.<x,y,z>=k[]
sage: F=x^3*y+x^3*z+x^2*y^2+x^2*y*z+x^2*z^2+x*y^2*z+x*y*z^2+y^3*z+y*z^3
sage: I=plane_curve(F)
sage: Z=I.zeros(n)[1]
sage: L=[I.point(l,n) for l in [ 0, 1, 0 ],[ 0, 0, 1 ],[ -1, 0, 1 ],[ 1, 0, 0 ],[ -1, 1, 0 ]]
sage: G=[l+L[0]-(L[0]+L[0]) for l in L[1:]]
sage: [42*g == Z for g in G]
[True, True, True, True]
sage: timeit('_=10^30*G[1]')
5 loops, best of 3: 773 ms per loop

The current script has a constructor for projective plane curves. Note that:

• the code should also work to a large extent on singular curves. The sheafs and their global sections still make sense. We just need to see exactly what we're computing in (probably some generalized jacobian).
• the code has been designed such that divisor (perhaps with some small modifications, but it's a draft anyway) can be reused for other models too. The idea would be to provide other implementations that provide Riemann-Roch spaces for other models as well (general smooth projective curves, modular curves via modular form expansions).

The timings above used #15104, which is quite necessary to get linear algebra to perform reasonably.

Finally, the code does not require k to be a finite field, although there are probably some matrix features that would have to get implemented in some other matrix classes too, but those are very straightforward. It is rather important to do something about divisor class representation for non-finite fields (hence initpickvector), since otherwise coefficients explode even in the (non-unique!) representatives of torsion classes.

[nbruin]

comment:2

Todo:

• negation is currently just an addflip with an appropriate zero representative. This can be made a little more efficient
• in the 'small' model, computations are going all the way up to H⁰(9D₀) in Kamal's notation, which is 3n for me. In cases where n is divisible by 3, Kamal's remarks should directly reduce this to 7D₀ and in other cases, similar ideas might apply as well. Currently this means that the small approach to genus 3 curves (n=3) is a little slower than the medium approach (n=4). Of course, we would not limit ourselves to line bundles that are a multiple of the hyperplane sections (for curves with a rational point we can do much better), we'd get more choice of degrees.

[roed314]

Changed keywords from none to sd86.5

[roed314]

Branch: u/roed/implement_computations_in_picard_groups_via_global_sections_of_line_bundles

[kwankyu]

Commit: 1ea07dd

[kwankyu]

comment:9

referenced in #34232.

[kwankyu]

comment:10

The commit is not by me. Trac seems to have been confused. Anyway, #34232 sort of supersedes the commit.