Improve point counting for hyperelliptic curves

[sagetrac-goncalves]

Harvey's hypellfrob program is shipped with Sage but was not actually used to count points on hyperelliptic curves.

This ticket intends to fix that (and add several other minor improvements).

Depends on #15108

CC: @defeo

Component: algebraic geometry

Keywords: sd53 hyperelliptic curve

Author: Cécile Gonçalves, Jean-Pierre Flori, Jan Tuitman

Branch/Commit: 8029bc6

Reviewer: Jan Tuitman, Jennifer Balakrishnan, Volker Braun

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

[sagetrac-goncalves]

Branch: u/goncalves/ticket/15148

[sagetrac-jantuitman]

comment:3

When you only want the number of rational points (and not the complete zeta function) you can use a (g times) lower precision. In this case you shouldn't use .frobenius_polynomial but ._frobenius_matrix and compute the trace of this matrix.

It is not necessary to exclude the case n>2g, but in this case (and already for n>=g) it is probably better to use .frobenius_polynomial and compute the number of points by expanding a power series (as we discussed in Rennes).

So:

1. for n<g use ._frobenius_matrix to compute matrix F and compute the traces of F, ... ,F^n.

2. for n>=g use .frobenius_polynomial and compute the coefficients of the log of the zeta function.

Would you like to change this, or can I give it a try? (I'm at SAGE days this week, trying to do something useful)

[jpflori]

Changed keywords from none to sd53 hyperelliptic curve

[jpflori]

Changed branch from u/goncalves/ticket/15148 to u/jpflori/15148

[jpflori]

Changed author from Cécile Gonçalves to Cécile Gonçalves, Jean-Pierre Flori, Jan Tuitman

[sagetrac-git]

Commit: 55cdcf3

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

[changeset:55cdcf3]	Refactor point counting code for hyperelliptic curves.
[changeset:86261b1]	Improve count_points
[changeset:a1f9bec]	Merge remote-tracking branch 'origin/build_system' into build_system
[changeset:4cb7db9]	Merge remote-tracking branch 'origin' into build_system

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

[changeset:fc7a569]

First bunch of fixes and missing examples.

[sagetrac-git]

Changed commit from 55cdcf3 to fc7a569

[jpflori]

Reviewer: Jan Tuitman

[jpflori]

Changed branch from u/jpflori/15148 to u/jpflori/ticket/15148

[jpflori]

comment:10

See #11980 for a follow-up.

[jbalakrishnan]

comment:11

This looks good to me.

[jbalakrishnan]

Changed reviewer from Jan Tuitman to Jan Tuitman, Jennifer Balakrishnan

[vbraun]

comment:13

This ticket leads to some test failures (did you check long doctests?). Please fix...

http://build.sagemath.org/sage/builders/%20%20fast%20Volker%20Desktop%20%28Fedora%2019%20x86_64%29%20incremental/builds/22/steps/shell_3/logs/stdio

[jpflori]

comment:14

I thought so... I'll try to fix the failures tonight.

[jpflori]

Work Issues: rebase tests on top of #15108

[jpflori]

comment:15

I think that the doctest failure are caused by #15108 which makes base extension of hyperellipticurves smarter and triggers use of the new code for hyperelliptic curves introduced here and which wasn't used for more general schemes...
The fix should be trivial.

[jpflori]

Dependencies: #15108

[jpflori]

comment:16

And of course I cannot built the latest versions of Sage on my laptop because of glibc's bug in scanf.

[sagetrac-git]

Changed commit from fc7a569 to 63bf717

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

63bf717

Rebase on top of #15108.

[jpflori]

comment:18

Tests and some doc (trivially) updated.
Passes all tests (on POWER7...).

[jpflori]

Changed work issues from rebase tests on top of #15108 to none

[jpflori]

comment:19

For a potential reviewer, the ticket used to be positively reviewed, and the latest changes are really trivial, taking the inclusion of another ticket into account.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

8029bc6

Merge remote-tracking branch 'trac/develop' into ticket/15148

[sagetrac-git]

Changed commit from 63bf717 to 8029bc6

[vbraun]

Changed reviewer from Jan Tuitman, Jennifer Balakrishnan to Jan Tuitman, Jennifer Balakrishnan, Volker Braun

[vbraun]

Changed branch from u/jpflori/ticket/15148 to 8029bc6