Opened 8 years ago

Closed 6 years ago

#11980 closed enhancement (fixed)

Improve naive point counting and implement zeta_function for hyperelliptic curves over finite fields

Reported by: dkrenn Owned by: cremona
Priority: major Milestone: sage-6.3
Component: elliptic curves Keywords: sd35 hyperelliptic curve sd53
Cc: jantuitman, minz, defeo, vbraun Merged in:
Authors: Daniel Krenn, Jean-Pierre Flori Reviewers: Marco Streng, Volker Braun
Report Upstream: N/A Work issues:
Branch: c5b2f5d (Commits) Commit: c5b2f5d92936577e517f3a871e8f673727f33b10
Dependencies: #15148 Stopgaps:

Description (last modified by jpflori)

The following is not implemented (but can be done for hyperelliptic curves):

sage: P.<x> = PolynomialRing(GF(9,'a'))
sage: H = HyperellipticCurve(x^5+x^2+1)
sage: H.count_points(5)
Traceback (most recent call last)
...
NotImplementedError: Point counting only implemented for schemes over prime fields

Also, having a count_points for all cases, the Frobenius polynomial can be calculated. At the moment, this is calculated via frobenius_matrix, which is not always available:

sage: R.<t> = PolynomialRing(GF(8, 'a'))
sage: H = HyperellipticCurve(t^5 + t + 2, t + 1)
sage: H.frobenius_polynomial()
Traceback (most recent call last):
...
NotImplementedError: only implemented for curves y^2 = f(x)

Further, the zeta function can be calculated easily when the Frobenius polynomial is known.

Use git branch.

Attachments (1)

trac_11980_count_points_frob_zeta.patch (10.1 KB) - added by dkrenn 8 years ago.

Download all attachments as: .zip

Change History (31)

Changed 8 years ago by dkrenn

comment:1 Changed 8 years ago by dkrenn

  • Status changed from new to needs_review

comment:2 Changed 8 years ago by dkrenn

  • Authors set to Daniel Krenn
  • Dependencies changed from [http://trac.sagemath.org/sage_trac/ticket/11930 11930] to 11930

comment:3 Changed 8 years ago by dkrenn

  • Dependencies changed from 11930 to #11930

comment:4 Changed 8 years ago by mstreng

  • Dependencies #11930 deleted
  • Status changed from needs_review to needs_work

With the changes at #11930 it is no longer necessary to use is_singular, so that test could be removed.

comment:5 Changed 8 years ago by mstreng

  • Keywords sd35 hyperelliptic curve added
  • Reviewers set to Marco Streng
  • Work issues set to correct number of points at infinity, examples for even degree

In case f has even degree, the points at infinity are counted incorrectly by this patch. To get the correct characteristic polynomial of Frobenius, we must consider the smooth model of the curve. This is what you get when you desingularize at infinity. This smooth curve has 0, 1 or 2 points at infinity defined over the base field, so instead of just with 1, the count must start with 0, 1 or 2. (The count will not always agree with the count from the base class, as the base class thinks about the singular curve. See also #11800.)

In case H : y^2 = f(x) with degree(f) > 2, there are three cases:

  • degree(f) is odd: there is a unique point at infinity over the base field (a rational Weierstrass point at infinity)
  • degree(f) is even and its leading coefficient is a square: there are two points at infinity defined over the base field
  • degree(f) is even and its leading coefficient is not a square: there is no point at infinity defined over the base field (there are two points over a quadratic extension, and they are conjugate to each other)

A similar list of cases can be written down in greater generality (including characteristic 2).

Alternative to get the patch in quickly: raise an error if the curve is not of the form y^2 = f(x) with f of odd degree > 2.

comment:6 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:7 Changed 7 years ago by mstreng

  • Dependencies set to #15115

comment:8 Changed 7 years ago by jpflori

  • Dependencies changed from #15115 to #15115 #15148
  • Keywords sd53 added

See also #15148 where we are modifying count_points to actually use hypellfrob. (The ticket is not uptodte, I should be uploading there this afternoon hopefully.)

comment:9 Changed 7 years ago by jpflori

Ok, so Ive finished #15148, and after looking at what was I suggested here, I think what has to be done here, on top of #15148:

  • we should add the zeta_function method,
  • enhance the naive point counting I introduced in #15148 with some ideas from this ticket, namely replace my use of the extension method of finite fields by that of embeddings of a subfield into a super field using the Hom functor and the embedding it computes.

comment:10 Changed 7 years ago by jpflori

  • Dependencies changed from #15115 #15148 to #15148

And I don't think this should depend on #15115 as it makes no use of the modification there. Ok the current number of point is wrong, in the spirit of what is fixed in #15115, but in my code at #15148 it is right, so provided we base this ticket on top of #15148, the dependency on #15115 goes away.

comment:11 Changed 7 years ago by jpflori

  • Authors changed from Daniel Krenn to Daniel Krenn, Jean-Pierre Flori
  • Branch set to u/jpflori/ticket/11980
  • Description modified (diff)
  • Status changed from needs_work to needs_review
  • Summary changed from hyperelliptic curves: count_points and frobenius_polynomial do not work in all cases, not zeta_function available to Improve naive point counting and implement zeta_function for hyperelliptic curves over finite fields
  • Work issues correct number of points at infinity, examples for even degree deleted

comment:12 Changed 7 years ago by git

  • Commit set to 534116b53fae0aae1919fb4d99ba4cee0ee20c44

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

[changeset:534116b]Improve naive point counting and implement zeta_function.
[changeset:fc7a569]First bunch of fixes and missing examples.
[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

comment:13 Changed 7 years ago by jpflori

  • Cc jantuitman added

comment:14 Changed 7 years ago by minz

  • Cc minz added

comment:15 Changed 6 years ago by jpflori

  • Cc defeo added

FYI, this still works fine without modifications after the merge of #15108 and the changes at #15148.

comment:16 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:17 Changed 6 years ago by chapoton

  • Status changed from needs_review to needs_work

There are some failing doctests, see patchbot report.

comment:18 Changed 6 years ago by jpflori

Did the patchbot actually managed to use the latest version?

Last time I had a look at it it was stuck with an old comit, anyway, I'll give it a look tomorrow.

comment:19 Changed 6 years ago by git

  • Commit changed from 534116b53fae0aae1919fb4d99ba4cee0ee20c44 to 4f370fd3bedf021b68470b233806be83cbe12623

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

63bf717Rebase on top of #15108.
08bca28Merge branch 'ticket/15148' into ticket/11980
c1e4ec7Merge remote-tracking branch 'trac/develop' into ticket/11980
8029bc6Merge remote-tracking branch 'trac/develop' into ticket/15148
824a500Merge branch 'ticket/15148' into ticket/11980
4f370fdMerge remote-tracking branch 'trac/develop' into ticket/11980

comment:20 Changed 6 years ago by jpflori

I've merged the latest #15148 (hint: please review) and latest trac/develop (I don't know if the patchbot can make that alone, especially the former one using the dependencies field). No problem in the schemes directory, I'm running the full long testsuite now.

comment:21 Changed 6 years ago by jpflori

I only got one error in ppl.pyx, but I fear it is unrelated.

comment:22 Changed 6 years ago by jpflori

And not reproducible...

comment:23 Changed 6 years ago by jpflori

  • Status changed from needs_work to needs_review

comment:24 Changed 6 years ago by jpflori

  • Cc vbraun added

comment:25 Changed 6 years ago by git

  • Commit changed from 4f370fd3bedf021b68470b233806be83cbe12623 to 279cdd006f7b4b6e9616fc992339aee7fb960039

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

279cdd0Merge remote-tracking branch 'trac/develop' into ticket/11980

comment:26 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:27 Changed 6 years ago by chapoton

  • Branch changed from u/jpflori/ticket/11980 to public/ticket/11980
  • Commit changed from 279cdd006f7b4b6e9616fc992339aee7fb960039 to c5b2f5d92936577e517f3a871e8f673727f33b10

This looks good, as far as I can tell, but I am not competent to check that the new results are mathematically correct. I have made two tiny changes to the doc, and also taken the opportunity to run pyflakes on the changed file. Found three unused variable assignements. Two have been removed, the third one looks very suspect, so I have just added a comment besides it. I have also cleaned-up a little bit the code formatting around the suspect variable assignement.


New commits:

317f67fMerge branch 'u/jpflori/ticket/11980' of ssh://trac.sagemath.org:22/sage into 11980
c5b2f5dtrac #11980 minor doc changes + a little code formatting and pyflakes check

comment:28 Changed 6 years ago by jpflori

IIRC there is no deep mathematics introduced here.

Just need to use jacobi symbols to know how many ordinates go with an abscissa (0,1 or 2), the number of points at infinity (as here IIRC we're really computing the number of points on the desingularization of the curve).

The zeta funciton thing is just a very simple toy addition.

comment:29 Changed 6 years ago by vbraun

  • Reviewers changed from Marco Streng to Marco Streng, Volker Braun

comment:30 Changed 6 years ago by vbraun

  • Branch changed from public/ticket/11980 to c5b2f5d92936577e517f3a871e8f673727f33b10
  • Resolution set to fixed
  • Status changed from needs_review to closed
Note: See TracTickets for help on using tickets.