Opened 10 years ago

Closed 6 years ago

#6341 closed enhancement (fixed)

implement Mestre's algorithm for constructing genus 2 hyperelliptic curves

Reported by: ncalexan Owned by: was
Priority: major Milestone: sage-5.13
Component: number theory Keywords: mestre algorithm genus 2 hyperelliptic curves sd35 sd51
Cc: ncalexan, mstreng, jpflori, lassina, fstromberg Merged in: sage-5.13.beta0
Authors: Florian Bouyer, Marco Streng Reviewers: Lassina Dembele, Fredrik Stromberg, Aly Deines
Report Upstream: N/A Work issues:
Branch: u/fstromberg/ticket/6341 (Commits) Commit:
Dependencies: Stopgaps:

Description (last modified by mstreng)

* this ticket is still using the old workflow, just apply patches and ignore the "branch" field *

An implementation of Mestre's algorithm for reconstructing genus 2 hyperelliptic curves from their invariants.

This is limited to fields of characteristic not 2, 3, 5 and to curves with automorphism group generated by the hyperelliptic involution. Curve equations are not reduced, hence are unusably large over QQ, but see below.

That's it. Various other tickets deal with extensions:

  • #14755 reduces the discriminant of the hyperelliptic curve (essential for getting usable models over number fields)
  • #14756 reduces the hyperelliptic curve equation once the discriminant is minimal (also essential for getting usable models over number fields).
  • #12199 treats the case of larger automorphism groups
  • #12200 is about characteristic 2, 3, 5

Apply:

Attachments (20)

trac_6341-mestre-extcode.patch (67.8 KB) - added by ncalexan 10 years ago.
trac_6341-mestre.patch (28.1 KB) - added by ncalexan 10 years ago.
trac_6341-mestre-without-conic.patch (10.8 KB) - added by mstreng 10 years ago.
trac_6341-mestre-extcode-without-qfsolve.patch (38.1 KB) - added by mstreng 10 years ago.
trac_6341_mestre_algorithm.patch (31.6 KB) - added by florian 7 years ago.
An implementation of Mestre Algorithm
trac_6341_mestre_algoritm_2.patch (15.8 KB) - added by florian 7 years ago.
minor changes to first patch
6341_reviewer.patch (49.5 KB) - added by mstreng 7 years ago.
6341_combined.patch (35.4 KB) - added by mstreng 7 years ago.
mestre.patch (94.8 KB) - added by mstreng 7 years ago.
version under construction, apply on top of previous patch, supposed to work for number fields, requires #11455
6341-transformations.patch (16.7 KB) - added by mstreng 7 years ago.
on top of previous
mestre_parentheses.patch (20.8 KB) - added by mstreng 6 years ago.
6341-lifts.patch (1.7 KB) - added by mstreng 6 years ago.
6341-some_fixes.patch (14.3 KB) - added by mstreng 6 years ago.
6341-mestre-only.patch (13.3 KB) - added by mstreng 6 years ago.
only Mestre's algorithm
trac_6341-mestre-only_cleanup.patch (12.3 KB) - added by chapoton 6 years ago.
trac_6341_correcttions.patch (1.7 KB) - added by florian 6 years ago.
6341-more-corrections.patch (7.7 KB) - added by mstreng 6 years ago.
apply after the other three
6341-more-corrections.2.patch (8.2 KB) - added by mstreng 6 years ago.
6341-more-corrections.3.patch (8.4 KB) - added by mstreng 6 years ago.
6341.patch (13.7 KB) - added by mstreng 6 years ago.
ascii version of what was uploaded earlier this week

Download all attachments as: .zip

Change History (58)

comment:1 Changed 10 years ago by ncalexan

  • Description modified (diff)

Changed 10 years ago by ncalexan

Changed 10 years ago by ncalexan

comment:2 Changed 10 years ago by ncalexan

  • Summary changed from implement Mestre's algorithm for constructing genus 2 hyperelliptic curves to [with patch, needs work] implement Mestre's algorithm for constructing genus 2 hyperelliptic curves

Here's a work in progress version. The extcode patch

  • updates Denis Simon's pari qfsolve program;
  • and incorporates Paul van Wamelen's pari genus 2 package.

The main devel patch integrates everything, or at least starts to.

comment:3 Changed 10 years ago by mstreng

  • Cc mstreng added

Changed 10 years ago by mstreng

comment:4 Changed 10 years ago by mstreng

The files "-without..." are the same as ncalexan's files, but with the Conic class removed and put in a separate patch at ticket 727. They still need the Conic class, but it may be better to view this as a separate enhancement.

comment:5 Changed 8 years ago by mstreng

  • Report Upstream set to N/A

This will be revived as part of a student project in August 2011.

comment:6 Changed 7 years ago by mstreng

  • Authors set to Florian Bouyer
  • Keywords sd35 added
  • Summary changed from [with patch, needs work] implement Mestre's algorithm for constructing genus 2 hyperelliptic curves to implement Mestre's algorithm for constructing genus 2 hyperelliptic curves

Code was written by Florian Bouyer in September 2011, it works very nicely. Now it is a coding sprint at Sage Days 35 to put this in.

Changed 7 years ago by florian

An implementation of Mestre Algorithm

comment:7 Changed 7 years ago by florian

  • Status changed from needs_work to needs_review

comment:8 Changed 7 years ago by mstreng

  • Description modified (diff)

apply trac_6341_mestre_algorithm.patch

(this helps patchbot)

comment:9 Changed 7 years ago by mstreng

See also #12199, which will later fill in some special cases.

comment:10 Changed 7 years ago by florian

See also #12200, which will later fill in some special case

Changed 7 years ago by florian

minor changes to first patch

comment:11 Changed 7 years ago by florian

  • Description modified (diff)

I corrected some typos and wasted white spaces pointed out by Marco

comment:12 Changed 7 years ago by florian

  • Description modified (diff)

comment:13 Changed 7 years ago by mstreng

  • Description modified (diff)
  • Reviewers set to Marco Streng
  • Status changed from needs_review to needs_work

I'm reviewing and writing a reviewer's patch. Looks very good, but some small changes are needed that are easier to do than to explain.

Changed 7 years ago by mstreng

Changed 7 years ago by mstreng

comment:14 follow-up: Changed 7 years ago by mstreng

  • Description modified (diff)

I wrapped lines and clarified / corrected documentation and corrected some formulas. I also removed functions that were not needed.

To do:

  • continue with wrapping lines and checking documentation for spelling or formatting problems
  • add the missing examples and possibly some more with non-trivial reduction properties
  • remove functions marked with "to_remove"
  • make sure stoll-cremona reduction is correctly implemented when homogenized to higher degree than the degree of the polynomial
  • add a sanity check at the end of HyperellipticCurve_from_invariants, checking if the curve has the correct invariants before outputting it (RuntimeError? otherwise)

apply 6341_combined.patch

comment:15 in reply to: ↑ 14 Changed 7 years ago by mstreng

  • Priority changed from minor to major
  • Work issues set to see [comment:14]

comment:16 Changed 7 years ago by jpflori

  • Cc jpflori added

comment:17 Changed 7 years ago by mstreng

With a view towards the future (number fields), it may be a good idea to move the code from lines 679 -- 732 to a separate function with input a polynomial, a valuation and a uniformizer. If the uniformizer generates the prime ideal, this gives a local reduction that does not screw up the other primes. If this is not possible (e.g. a non-principal prime of a number field) you can still get a local reduction and combine the local reductions later.

Changed 7 years ago by mstreng

version under construction, apply on top of previous patch, supposed to work for number fields, requires #11455

Changed 7 years ago by mstreng

on top of previous

Changed 6 years ago by mstreng

Changed 6 years ago by mstreng

comment:18 Changed 6 years ago by mstreng

  • Authors changed from Florian Bouyer to Florian Bouyer, Marco Streng
  • Description modified (diff)

Changed 6 years ago by mstreng

Changed 6 years ago by mstreng

only Mestre's algorithm

comment:19 Changed 6 years ago by mstreng

  • Description modified (diff)

I separated off the (huge) reduction code from this simple functionality. Hopefully that helps in finishing this ticket.

comment:20 Changed 6 years ago by chapoton

instructions for the patchbot :

apply 6341-mestre-only.patch

comment:21 Changed 6 years ago by chapoton

  • Description modified (diff)

here is patch, just cleaning things up. There are some doctests failing..

apply 6341-mestre-only.patch trac_6341-mestre-only_cleanup.patch

Last edited 6 years ago by chapoton (previous) (diff)

Changed 6 years ago by chapoton

comment:22 Changed 6 years ago by mstreng

  • Keywords sd51 added

comment:23 Changed 6 years ago by florian

  • Cc lassina added

Changed 6 years ago by florian

comment:24 Changed 6 years ago by florian

  • Description modified (diff)
  • Status changed from needs_work to needs_review

comment:25 Changed 6 years ago by mstreng

  • Cc fstromberg added
  • Reviewers Marco Streng deleted
  • Work issues see [comment:14] deleted

comment:26 Changed 6 years ago by fstromberg

  • Branch set to u/fstromberg/ticket/6341

comment:27 Changed 6 years ago by mstreng

  • Status changed from needs_review to needs_work
  • Work issues set to correct ticket number in error message, not 5534, but 14755

comment:28 Changed 6 years ago by mstreng

  • Description modified (diff)
  • Reviewers set to Lassina Dembele
  • Status changed from needs_work to needs_review

Changed 6 years ago by mstreng

apply after the other three

Changed 6 years ago by mstreng

comment:29 Changed 6 years ago by mstreng

  • Status changed from needs_review to needs_work
  • Work issues changed from correct ticket number in error message, not 5534, but 14755 to complete references (title and journal with volume)

Changed 6 years ago by mstreng

comment:30 Changed 6 years ago by mstreng

  • Description modified (diff)
  • Reviewers changed from Lassina Dembele to Lassina Dembele, Fredrik Stromberg
  • Work issues complete references (title and journal with volume) deleted

(testing now)

comment:31 follow-up: Changed 6 years ago by mstreng

  • Description modified (diff)

for patchbot: apply 6341-mestre-only.patch and trac_6341-mestre-only_cleanup.patch and 6341-mestre-corrections.3.patch

comment:32 Changed 6 years ago by mstreng

  • Status changed from needs_work to needs_review

comment:33 in reply to: ↑ 31 Changed 6 years ago by mstreng

apply 6341-mestre-only.patch and trac_6341-mestre-only_cleanup.patch and 6341-more-corrections.3.patch

comment:34 Changed 6 years ago by mstreng

  • Description modified (diff)

I combined the patches into one, for easier review. Apply only 6341.patch

Changed 6 years ago by mstreng

ascii version of what was uploaded earlier this week

comment:35 Changed 6 years ago by chapoton

apply only 6341.patch

comment:36 Changed 6 years ago by aly.deines

  • Reviewers changed from Lassina Dembele, Fredrik Stromberg to Lassina Dembele, Fredrik Stromberg, Aly Deines
  • Status changed from needs_review to positive_review

This is working for me. I've verified several more non-CM examples in Magma.

comment:37 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-feature to sage-5.13

comment:38 Changed 6 years ago by jdemeyer

  • Merged in set to sage-5.13.beta0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.