Opened 6 years ago

Last modified 2 years ago

#15113 new enhancement

Implement computations in picard groups via global sections of line bundles

Reported by: nbruin Owned by:
Priority: major Milestone: sage-6.4
Component: algebraic geometry Keywords: sd86.5
Cc: pbruin Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: u/roed/implement_computations_in_picard_groups_via_global_sections_of_line_bundles (Commits) Commit:
Dependencies: Stopgaps:

Description

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.

Attachments (1)

picard_group.sage (17.9 KB) - added by nbruin 6 years ago.
first draft version

Download all attachments as: .zip

Change History (9)

Changed 6 years ago by nbruin

first draft version

comment:1 Changed 6 years ago by nbruin

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 H0(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 Pic0:

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.

comment:2 Changed 6 years ago by nbruin

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 H0(9D0) 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 7D0 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.

comment:3 Changed 6 years ago by pbruin

  • Cc pbruin added

comment:4 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:5 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:6 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:7 Changed 2 years ago by roed

  • Keywords sd86.5 added

comment:8 Changed 2 years ago by roed

  • Branch set to u/roed/implement_computations_in_picard_groups_via_global_sections_of_line_bundles
Note: See TracTickets for help on using tickets.