Opened 7 years ago
Last modified 3 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)
Change History (9)
Changed 7 years ago by
comment:1 Changed 7 years ago by
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^{0}(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^{0}:
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 7 years ago by
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^{0}(9D_{0}) 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_{0} 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 7 years ago by
- Cc pbruin added
comment:4 Changed 6 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:5 Changed 6 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:6 Changed 6 years ago by
- Milestone changed from sage-6.3 to sage-6.4
comment:7 Changed 3 years ago by
- Keywords sd86.5 added
comment:8 Changed 3 years ago by
- Branch set to u/roed/implement_computations_in_picard_groups_via_global_sections_of_line_bundles
first draft version