New code for binary quadratic forms

[RalphieBoy]

The code supporting binary quadratic forms, in quadratic_forms/binary_qf.py, is missing some functionality. The patch in this ticket provides the following changes:

• better support for indefinite forms
• tests for equivalence, positive and negative definite, indefinite, primitive forms
• action of matrix on a form
• find content
• is_reduced() is rewritten
• polynomial() now uses an instance variable (poly)
• some general cleaning up

Doctests are in place for the new code, so the file remains at 100% coverage.

CC: @RalphieBoy @jonhanke @tornaria

Component: quadratic forms

Author: Justin Walker, Jonathan Hanke, Gonzalo Tornaría, John Cremona

Branch: 748d390

Reviewer: John Cremona, Peter Bruin, Simon Brandhorst

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

[RalphieBoy]

Attachment: diff.gz

Context diff of new, old versions of quadratic_forms/binary_qf.py

[sagetrac-mabshoff]

comment:2

Justin,

the diff is inverse and you should also add an extension patch to the file.

Cheers,

Michael

[RalphieBoy]

comment:3

Attachment: sage-4120.patch.gz

Updated patch, works with 3.1.1 and 3.1.2. Needs review. And maybe testing :-} Also incorporated performance changes from Holdsworth's changes.

[JohnCremona]

comment:5

I am planning to review this, which looks pretty good. First, some preliminary questions/comments:

• I see that we now have some, but not all, support for indefinite forms. (e.g. no equivalence testing, no class number). Why not use pari interface for those, at least until we do our own? (I would have thought that pari was pretty efficient for these things).
• Your action of 2x2 matrices is a left action. Do we want to allow users to use a right action (say, by having RMul and LMul with Mul an alias for one of them)?
• Your action includes multiplication by det(A). Now there are lots of application for this code, some will like that and some will want something else. So why don't we have another parameter for Mul() which is the power of the determinant to be used. Personally I would set the default to 0 but if you wanted it to be 1 (as in your code) I could live with that.
• I still think that quite a lot of the functionality could be factored out into a more general binary form class, but that can be done later by someone (e.g. me) who uses higher degree forms.

[RalphieBoy]

comment:6

The patch also works with 3.1.3.alpha1. Doctests succeed.

[RalphieBoy]

comment:7

Here's a second patch, to be applied on top of sage-4120.patch.

This one fixes some bugs and typos in the first, cleans up some code, and adds more support for indefinite forms (equivalence checking, in particular). Probably adds a few bugs as well, but that's just a by-product.

[RalphieBoy]

Attachment: sage-4120-2.patch.gz

To be applied on top of sage-4120.patch

[RalphieBoy]

comment:8

This is a third patch, applied on sage-4120-2.patch.

This one extends support for indefinite forms and fixes a few bugs (both in code and in the Buchmann/Vollmer algorithms).

One change in particular deserves discussion: I have changed the normalization and reduction procedures to return both the form in question and the transformation matrix used to derive that form. This makes things a bit more awkward in the code, so there are two questions: is this really useful, and if yes, is there a better way to do it?

Also, I assigned this to me :-}.

[RalphieBoy]

To be applied on top of sage-4120-2.patch

[RalphieBoy]

comment:9

Attachment: sage-4120-3.patch.gz

Applied all three patches against 3.1.3.rc0, one at a time, running the doctests each time. All doctests succeeded. No problems noted.

[JohnCremona]

REPLACES earlier patches

[JohnCremona]

comment:10

Attachment: sage-trac4120.new.patch.gz

My patch sage-trac4120new.patch combines the three earlier ones and adds the following:

• Fixing various bugs and typos
• Sorting out a lot of formatting issues in doctests
• Adds some new functions
• Renames Mul to __mul__ so one can say Q*M to apply matrix M to form Q

Regarding the latter I relented and removed the scale parameter; since the det is either +1 or -1 I am happy with multiplying (or dividing) by the determinant.

Issues do remain:

• The various transform function which return a new form Q and a transform T really must satisfy self.T==Q, but they don't. Hence the commented out assertions.
• We must decide whether we are talking about weak or strict equivalence (GL or SL(2,ZZ)). At the moment it is hard to tell which.
• For indefinite forms there are several different notions of "reduced". OK to to stick to one, but we should make this explicit.
• The class number function looks inefficient to me, it should be replaced by the fast code by Skoruppa to list reduced forms (in the definite case at least).

That's all I can remember, but this will need more work before it can go in.

[sagetrac-mabshoff]

comment:11

See also #4470 for Jon Hanke's work on quadratic forms.

Cheers,

Michael

[sagetrac-mabshoff]

comment:15

To comment on the relationship with #4470:

AFAIK the binary quadratic forms are untouched by Jon's work. We
should rename the file to bring it more in line with what is coming
from Jon, i.e. all I have left to do to post a patch is to rename
various files to qf_ from quadratic_forms_, fix the imports and rebase
the extensions to module_list.py. All trivial, it just needs to be
done :p

Cheers,

Michael

[tornaria]

comment:16

I've reviewed the code from the last patch as submitted by John Cremona (sage-trac4120.new.patch). It applies cleanly on 3.3 and also on top of the first two patches in #4470.

Below are some comments about the code in binary_qf.py. I didn't make a difference between old code and code in the patch, since most of the code is in the patch, anyway.

• Constructor:

  • BinaryQF([1,2,3], 4, 5) should raise an error

  • I would like to suggest an additional constructor:

       sage: BinaryQF(2, 1, disc = -23)
       2*x^2 + x*y + 3*y^2
    

    this is handy when the discriminant is fixed and one knows the first two coefficients
    of a form

• __repr__:

  I don't like the fact that a quadratic form is represented by a polynomial, may lead
  to potential confusion. What about something like:
  "Binary quadratic form over Integer Ring with coefficients [a, b, c]"
  ?

• polynomial:

  • the variables for the polynomial are hardcoded... 'x' and 'y'... not very important (I rather not have a "polynomial" function... I'd replace it by a __call__ function which works for elements in any ring, then one can call e.g. Q(x,y) where x and y are in ZZ['x,y'], etc.

• action by matrices:

  • Q * M is a left action --> more natural to be right action!!
    I.e. right now

       sage: Q = BinaryQF(4,-4,15)
       sage: M = matrix(ZZ, 2, [1, 1, 0, 1])
       sage: M1 = matrix(ZZ, 2, [1, 0, 1, 1])
       sage: Q * M * M1 == Q * (M * M1)
       False
       sage: Q * M * M1 == Q * (M1 * M)
       True
    

  • I like the notation Q(M) for the action of matrices -- this is consitent with the
    notation for general quadratic forms and representation by vectors or sublattices (Merge Jon Hanke's qudratic forms code into Sage #4470)

    Maybe * should be reserved for composition?

• is_normal: he doctest doesn't explain what it is

• is_equivalent

  • IMO should return True or False
  • have extra parameter to request transformation matrix
  • needs more doctests (in particular indefinite, etc)
  • sage: Q * Q.is_equivalent(Q1)[1].transpose() == Q1 /// should be True
    this is just an issue with the action of matrices being left action
  • for indefinite: should not compute the cycle for every form!!
    instead, compute self * other^(-1) (in the class group), and check if it is in the
    principal cycle, which should of course be cached once for each discriminant. This is
    helpful since one will probably use many forms of the same discriminant together.

  Not sure about how to do memory management though: it'd be nice if every indefinite
  form of discriminant D holds a reference to the principal cycle of discriminant D, so
  the cycle is deleted when the last indefinite form of discriminant D is deleted ???

  ALSO: IMO the caching of the cycle should be done by the function Cycle() itself, not by
  is_equivalent.

  Moreover, the cycle needs to cache the transformation matrix as well, so we can
  actually figure out the correct transformation matrix.

• matrix: should be the Hessian for consistency with the rest of the code ???
  the advantage is that it makes the matrix over ZZ (with even diagonal)

• is_zero: should not need a gcd to decide if it is 0

• s and ss: internal, should be prepended with __ ???

• class number computation should use pari

• implement conversions between pari <--> sage for BinaryQF and Qfb
  maybe try to wrap around pari functionality as much as possible, for speed ??? (both
  runtime and development!!) E.g. composition, etc.

[RalphieBoy]

New patch; replaces previous patches.

[RalphieBoy]

comment:17

Attachment: 4120-110324.patch.gz

New patch. Primary content is support for indefinite binary forms.

[sagetrac-git]

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

cc8a94d

Merge branch 'develop' into ticket/4120-binary_quadratic_forms

[simonbrandhorst]

Changed branch from u/pbruin/4120-binary_quadratic_forms to u/sbrandhorst/4120-binary_quadratic_forms

[sagetrac-git]

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

e3b838e

Small docfix

[sagetrac-git]

Changed commit from cc8a94d to e3b838e

[simonbrandhorst]

comment:54

Some changes I made:

• removed @cached_method in polynomial as we already cache in _poly
• reduced_form(self, matrix=False, implementation=None): matrix seems missleading to me.
  changed the keywords to transformation and algorithm to stay consistent with other
  parts of sage (for example .hermite_form)
• used long names for methods like is_indef but keep the short alias
• _RhoTau(self, proper=False)
  removed the proper keyword as it is not used.
• use a better bound for a in BinaryQF_reduced_representatives from the Buchmann/Vollmer book
• added a keyword proper for is_equivalent as for indefinite forms we only test improper
  equivalence, we check if the form is in the cycle of the other form but that cycle is improper

Question:

• This requires a deprecation - do we really want to change it? This ticket changes so much
  already I would vote against it:

  -def BinaryQF_reduced_representatives(D, primitive_only=False):
  +def BinaryQF_reduced_representatives(D, primitive_only=True):
  

[simonbrandhorst]

comment:55

The ticket is not perfect but I think it is okay.
As the perfect is the enemy of the good - positive review on my part if you are happy with my changes and resolve the issue with the primitive_only keyword.

[simonbrandhorst]

Changed reviewer from John Cremona, Peter Bruin to John Cremona, Peter Bruin, Simon Brandhorst

[simonbrandhorst]

comment:57

Note on my machine tests pass, doc builds and looks reasonable.

[JohnCremona]

comment:58

I agree with the decision not to change the default for the primitive-only parameter.

[pjbruin]

comment:59

I agree too.

[sagetrac-git]

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

3f7ea83

revert to primitive_only=False

[sagetrac-git]

Changed commit from e3b838e to 3f7ea83

[sagetrac-git]

Changed commit from 3f7ea83 to 0a08de0

[sagetrac-git]

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

0a08de0

docfix

[simonbrandhorst]

comment:62

Then let us finally get this reviewed :)

[pjbruin]

comment:63

Fixed a SEEALSO block (causing docbuild to fail) and two pyflakes complaints. Let's get this ticket in before its 10-year anniversary.

[pjbruin]

Changed commit from 0a08de0 to 748d390

[pjbruin]

Changed branch from u/sbrandhorst/4120-binary_quadratic_forms to u/pbruin/4120-binary_quadratic_forms

[vbraun]

Changed branch from u/pbruin/4120-binary_quadratic_forms to 748d390

[jdemeyer]

Changed author from Justin Walker, Jon Hanke, Gonzalo Tornaría, John Cremona to Justin Walker, Jonathan Hanke, Gonzalo Tornaría, John Cremona

[jdemeyer]

Changed commit from 748d390 to none