Reduce Forms from Stoll and Cremona

[sagetrac-rlmiller]

Implementing the reduce forms algorithm from On the reduction theory of binary forms for both polynomials and projective morphisms. Also includes Newton's method for 2 variables, could be further expanded in the future.

CC: @bhutz @pfili

Component: algebra

Author: Rebecca Lauren Miller, Ben Hutz

Branch: c00aaeb

Reviewer: Ben Hutz, Rebecca Lauren Miller

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

[sagetrac-rlmiller]

Branch: u/rlmiller/binary

[sagetrac-rlmiller]

comment:2

Still having some problems with the examples, and calling value errors. See notes in documentation.

---

New commits:

0544a24

21248 Adding reduced binary form algorithm

[sagetrac-rlmiller]

Commit: 0544a24

[bhutz]

comment:3

Well, the first step here is to move from 7.3beta4 to 7.4beta0.

Let's leave this as needs-work until the issues are worked out.

[bhutz]

Changed branch from u/rlmiller/binary to u/bhutz/binary

[sagetrac-git]

Changed commit from 0544a24 to f777476

[sagetrac-git]

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

f777476

21248: some clean-up and minor error fixing

[bhutz]

comment:6

I did some code/formatting clean-up and made the examples work. For the most part you are just having formatting issues.

I have not tested any functionality yet.

[sagetrac-rlmiller]

Changed branch from u/bhutz/binary to u/rlmiller/binary

[sagetrac-rlmiller]

comment:8

Still need a few more examples, having problems with two examples in projective_morphism.py They worked in the notebook.

---

New commits:

dcc7a4a

21248 Reduced Binary form, added examples and documentation

[sagetrac-rlmiller]

Changed commit from f777476 to dcc7a4a

[bhutz]

comment:9

I think there may be something wrong with the 2nd part of the algorithm. Using the example from the paper that illustrates why you need to use the system of equations, the numerical root finding is not getting the same z as they do.

poly = 19*x^8 - 262*x^7*h + 1507*x^6*h^2 - 4784*x^5*h^3 + 9202*x^4*h^4 -
10962*x^3*h^5 + 7844*x^2*h^6 - 3040*x*h^7 + 475*h^8

[sagetrac-git]

Changed commit from dcc7a4a to 93e8aea

[sagetrac-git]

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

93e8aea

21248 added example fixed errors

[bhutz]

Reviewer: Ben Hutz

[bhutz]

comment:12

• With the updated version of magma, I'm getting consistent results with most examples. Although here is one that is not working correctly:

234*x^11*h + 104832*x^10*h^2 + 21346884*x^9*h^3 + 2608021728*x^8*h^4 +
212413000410*x^7*h^5 + 12109691106162*x^6*h^6 + 493106447396862*x^5*h^7
+ 14341797993350646*x^4*h^8 + 291976289803277118*x^3*h^9 +
3962625618555930456*x^2*h^10 + 32266526239647689652*x*h^11 +
119421058057217196228*h^12

It looks like the z0 part is correct, then the 2nd part is not.

• I'm not sure the inversion is correct. Take a look at part (2) on p13 of the paper. It may be causing the difference here

-234*x^10 - 95940*x^9*h - 17701164*x^8*h^2 - 1935379368*x^7*h^3 -138869177616*x^6*h^4 - 6832744528662*x^5*h^5 - 233468654564574*x^4*h^6 -5470310129096358*x^3*h^7 - 84114643276174446*x^2*h^8 -766469114143193916*x*h^9 - 3142950903278916444*h^10

which has

magma: [1,-41,0,1] vs sage: [-1,-41,0,-1]

or this may be the same error as in the previous bullet point.

• Also, the code is in need of a comments describing what each piece is doing.

• I also think the try/except for the NJinv can be simplified to

if NJinv.base_ring() != KK:
    NJinv = matrix(KK,2,2,[KK(zw.numerator()/zw.denominator()) for zw in NJinv.list()])

Then you can remove the .numerator() on the v0's later in the code.

[bhutz]

comment:13

I though about the one that is way off and here is what is going on. There is a root on the real line of the system of equations to find z(F). Your starting z0 value converges to that solution via Newton's method. However, what you need to find is the other solution which is in the upper half plane

[sagetrac-git]

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

6f744f6

21248 fixed error

[sagetrac-git]

Changed commit from 17ae040 to 5848b82

[sagetrac-git]

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

5848b82

21248: fixed typo, removed special casing

[bhutz]

comment:31

fixed the typo and realized since you are calling reduce on the polynomial with multiple roots, that there is no need to actually do the division. So I just count the multiple roots instead.

Just noticed the other typos. I'll push another fix for those.

[sagetrac-git]

Changed commit from 5848b82 to 0818825

[sagetrac-git]

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

0818825

21248: fix typos

[sagetrac-git]

Changed commit from 0818825 to 1366b9e

[sagetrac-git]

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

1366b9e

21248: fixing more typos

[fchapoton]

comment:34

covergence conditions is still a typo

[sagetrac-rlmiller]

comment:35

Typo fixed just waiting to push. Thanks

[sagetrac-rlmiller]

Changed branch from u/bhutz/binary to u/rlmiller/binary

[sagetrac-rlmiller]

New commits:

c00aaeb

21248 fixed spelling error

[sagetrac-rlmiller]

Changed commit from 1366b9e to c00aaeb

[bhutz]

comment:38

I think we're ready to go here.

[bhutz]

Changed author from Rebecca Lauren Miller to Rebecca Lauren Miller, Ben Hutz

[bhutz]

Changed reviewer from Ben Hutz to Ben Hutz, Rebecca Lauren Miller

[vbraun]

Changed branch from u/rlmiller/binary to c00aaeb

[bhutz]

Changed commit from c00aaeb to none

[bhutz]

comment:41

don't know what happened to the commit when I updated the milestone. I've copy/pasted the commit identifier back in.

[bhutz]

comment:42

apparently, that doesn't work. Have I messed up this ticket now?

[fchapoton]

comment:43

You should rather avoid playing with the milestone once the ticket is closed.

This being said, nothing bad should happen.

Side remark: has anybody proofread this code ? there are several typos (boundry, lease, ...)

[bhutz]

comment:44

Yeah, i don't usually mess with the milestone post closing, but when it was marked positive 7.4 was still in beta, then it got released and this was closed into 7.5.

I didn't expect correcting that to interfere with other fields.

side reply: apparently not as carefully as you.