Opened 13 years ago

Closed 3 years ago

Last modified 3 years ago

#4120 closed enhancement (fixed)

New code for binary quadratic forms

Reported by: justin Owned by: justin
Priority: major Milestone: sage-8.3
Component: quadratic forms Keywords:
Cc: justin, jonhanke, tornaria@… Merged in:
Authors: Justin Walker, Jonathan Hanke, Gonzalo Tornaría, John Cremona Reviewers: John Cremona, Peter Bruin, Simon Brandhorst
Report Upstream: N/A Work issues:
Branch: 748d390 (Commits, GitHub, GitLab) Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by pbruin)

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.

Attachments (6)

diff (22.7 KB) - added by justin 13 years ago.
Context diff of new, old versions of quadratic_forms/binary_qf.py
sage-4120.patch (22.6 KB) - added by justin 13 years ago.
sage-4120-2.patch (13.9 KB) - added by justin 13 years ago.
To be applied on top of sage-4120.patch
sage-4120-3.patch (16.5 KB) - added by justin 13 years ago.
To be applied on top of sage-4120-2.patch
sage-trac4120.new.patch (42.0 KB) - added by cremona 12 years ago.
REPLACES earlier patches
4120-110324.patch (31.9 KB) - added by justin 10 years ago.
New patch; replaces previous patches.

Download all attachments as: .zip

Change History (72)

Changed 13 years ago by justin

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

comment:1 Changed 13 years ago by mabshoff

  • Milestone set to sage-3.1.3

comment:2 Changed 13 years ago by mabshoff

Justin,

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

Cheers,

Michael

Changed 13 years ago by justin

comment:3 Changed 13 years ago by justin

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

comment:4 Changed 13 years ago by AlexGhitza

  • Summary changed from New code for binary quadratic forms to [with patch, needs review] New code for binary quadratic forms

comment:5 Changed 13 years ago by cremona

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.

comment:6 Changed 13 years ago by justin

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

comment:7 Changed 13 years ago by justin

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.

Changed 13 years ago by justin

To be applied on top of sage-4120.patch

comment:8 Changed 13 years ago by justin

  • Owner changed from tbd to justin

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 :-}.

Changed 13 years ago by justin

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

comment:9 Changed 13 years ago by justin

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

Changed 12 years ago by cremona

REPLACES earlier patches

comment:10 Changed 12 years ago by cremona

  • Summary changed from [with patch, needs review] New code for binary quadratic forms to [with new patch, needs review] New code for binary quadratic forms

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.

comment:11 Changed 12 years ago by mabshoff

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

Cheers,

Michael

comment:12 Changed 12 years ago by mabshoff

  • Component changed from algebra to quadratic forms

comment:13 Changed 12 years ago by justin

  • Cc justin added

comment:14 Changed 12 years ago by was

  • Summary changed from [with new patch, needs review] New code for binary quadratic forms to [with new patch, needs work] New code for binary quadratic forms

comment:15 Changed 12 years ago by mabshoff

  • Cc jonhanke added

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

comment:16 Changed 12 years ago by tornaria

  • Cc tornaria@… added

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 (#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.

Changed 10 years ago by justin

New patch; replaces previous patches.

comment:17 Changed 10 years ago by justin

  • Report Upstream set to N/A

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

comment:18 Changed 10 years ago by justin

  • Status changed from needs_work to needs_review

comment:19 Changed 10 years ago by cremona

  • Summary changed from [with new patch, needs work] New code for binary quadratic forms to New code for binary quadratic forms

comment:20 Changed 10 years ago by justin

Forgot to make this explicit: Previous patches include a lot more changes than are in the new one, but to simplify the review process (and my life), I've decided to break it up into smaller chunks. More changes will be forthcoming (new trac tickets).

comment:21 Changed 10 years ago by justin

NOTE: And another thing: this patch should be applied against Sage 4.7.alpha2 or later (the release with the patch from #10741).

comment:22 Changed 10 years ago by cremona

  • Authors set to Justin Walker, Jon Hanke, Gonzalo Tornaria, John Cremona
  • Reviewers set to John Cremona
  • Status changed from needs_review to needs_work

Patch applies and tests pass.

My only suggestion is that for invalid input you should raise an appropriate error (ValueError?) rather than printing something and returning []. And all integers =0,1(mod 4) should be allowed, even squares? The docstring should specify exactly what valid inputs are, in any case.

comment:23 follow-up: Changed 10 years ago by justin

I will make the changes to raise errors rather than return unexpected values; that makes sense.

There may be cases where restrictions on discriminants make sense. For example, I don't think that reduction for a degenerate form makes sense, and there are cases where we don't have an implementation for for a specific class of forms (indefinite, say). Thoughts?

comment:24 in reply to: ↑ 23 Changed 10 years ago by cremona

Replying to justin:

I will make the changes to raise errors rather than return unexpected values; that makes sense.

Good! Thanks.

There may be cases where restrictions on discriminants make sense. For example, I don't think that reduction for a degenerate form makes sense, and there are cases where we don't have an implementation for for a specific class of forms (indefinite, say). Thoughts?

OK by me to restrict to B which are 0 or 1 mod 4 and not squares.

comment:25 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:26 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:27 Changed 7 years ago by pbruin

I tried to do some computations with binary quadratic forms of positive discriminant, discovered that a lot of functionality was missing, and then found this ticket, which has been inactive for 3 years... Is anyone planning to work on it?

See also #6106.

Last edited 7 years ago by pbruin (previous) (diff)

comment:28 Changed 7 years ago by pbruin

  • Branch set to u/pbruin/4120-binary_quadratic_forms
  • Commit set to b7337f3a218585648a07a1268ba8e65a1887c1a2

Converted the patch to a Git branch; small fixes to make everything compile and pass tests.

Still needs_work in view of comment:22.

comment:29 Changed 7 years ago by git

  • Commit changed from b7337f3a218585648a07a1268ba8e65a1887c1a2 to 96c1a86e063e7a7512978c574ec40c84641b66d4

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

96c1a86binary_qf.py: clean up code and documentation

comment:30 Changed 7 years ago by pbruin

  • Description modified (diff)
  • Work issues set to more tests for is_reduced, doc of primitive_only

comment:31 Changed 7 years ago by git

  • Commit changed from 96c1a86e063e7a7512978c574ec40c84641b66d4 to ece1df7ed9ebb0d5d1f462edcf78024af24d547d

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

ece1df7binary_qf.py: more doctests, add "implementation" parameter for reduction

comment:32 Changed 7 years ago by pbruin

  • Status changed from needs_work to needs_review
  • Work issues more tests for is_reduced, doc of primitive_only deleted

comment:33 Changed 7 years ago by git

  • Commit changed from ece1df7ed9ebb0d5d1f462edcf78024af24d547d to dcf854dcfeef37a4b50999a9948b05bf4c629901

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

dcf854dMerge branch 'develop' into ticket/4120-binary_quadratic_forms

comment:34 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:35 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:36 Changed 6 years ago by git

  • Commit changed from dcf854dcfeef37a4b50999a9948b05bf4c629901 to 215cb8a6a67461471df0c4c43d70d555fae2d33b

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

215cb8aMerge branch 'develop' into ticket/4120-binary_quadratic_forms

comment:37 Changed 6 years ago by pbruin

  • Reviewers changed from John Cremona to John Cremona, Peter Bruin

I guess my commits can count as reviewer patches. However, I haven't reviewed all the new code in detail, so the branch should probably still be reviewed as a whole.

comment:38 follow-up: Changed 6 years ago by chapoton

  • Status changed from needs_review to needs_info

This ticket currently confuses the patchbot. Temporarily putting to needs info to stop the bot loop-testing it.

comment:39 in reply to: ↑ 38 Changed 6 years ago by pbruin

  • Status changed from needs_info to needs_review

Replying to chapoton:

This ticket currently confuses the patchbot. Temporarily putting to needs info to stop the bot loop-testing it.

It seems that at least the patchbot "eddy" is testing this ticket without adverse effects. Let's see what happens if I set it back to "needs_review". (There was a failure in the last patchbot run, but it seems to be unrelated to this ticket.)

comment:40 Changed 5 years ago by git

  • Commit changed from 215cb8a6a67461471df0c4c43d70d555fae2d33b to 5657f282979e1cb3c9bf7e49c62bbc606f00c108

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

5657f28Merge branch 'develop' into ticket/4120-binary_quadratic_forms

comment:41 Changed 5 years ago by dimpase

  • Milestone changed from sage-6.4 to sage-7.4

comment:42 Changed 4 years ago by dimpase

qfbcompraw is now wrapped, so calling pari directly to use it is no longer necessary, and should be fixed.

cf. the patch part:

+            # There could be more elegant ways, but qfbcompraw isn't
+            # wrapped yet in the PARI C library.  We may as well settle
+            # for the below, until somebody simply implements composition
+            # from scratch in Cython.
+            v = list(pari('qfbcompraw(%s,%s)'%(self._pari_init_(),
+                                            right._pari_init_())))
Last edited 4 years ago by dimpase (previous) (diff)

comment:43 Changed 4 years ago by dimpase

  • Milestone changed from sage-7.4 to sage-7.5

and the same for qfbred, which is now also wrapped.

comment:44 Changed 4 years ago by git

  • Commit changed from 5657f282979e1cb3c9bf7e49c62bbc606f00c108 to 00a4307ffecf6638466fbac3d41f8ca33f43c829

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

301a109Merge branch 'develop' into ticket/4120-binary_quadratic_forms
00a4307Trac 4120: allow construction of BinaryQF from PARI, and use PARI library interface

comment:45 Changed 4 years ago by git

  • Commit changed from 00a4307ffecf6638466fbac3d41f8ca33f43c829 to 959fbab69cbe7118cc2f5691fcfe5b64f80c966c

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

1f20033Merge branch 'develop' into ticket/4120-binary_quadratic_forms
959fbabTrac 4120: replace _pari_() by __pari__()

comment:46 Changed 4 years ago by pbruin

  • Authors changed from Justin Walker, Jon Hanke, Gonzalo Tornaria, John Cremona to Justin Walker, Jon Hanke, Gonzalo Tornaría, John Cremona

(added the accent to Gonzalo Tornaría's name; maybe this will also convince the patchbot to test this ticket)

comment:47 Changed 4 years ago by dimpase

  • Milestone changed from sage-7.5 to sage-8.1

comment:48 Changed 4 years ago by git

  • Commit changed from 959fbab69cbe7118cc2f5691fcfe5b64f80c966c to 2f580cb6d0a13eb66d84b996113d8880b5748a3c

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

2f580cbTrac 4120: EXAMPLE -> EXAMPLES, TEST -> TESTS

comment:49 Changed 3 years ago by chapoton

  • Status changed from needs_review to needs_work

branch does not apply, needs rebase

comment:50 Changed 3 years ago by git

  • Commit changed from 2f580cb6d0a13eb66d84b996113d8880b5748a3c to cc8a94dce0bec479a459b19f1a40ce9b29a6f136

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

cc8a94dMerge branch 'develop' into ticket/4120-binary_quadratic_forms

comment:51 Changed 3 years ago by pbruin

  • Status changed from needs_work to needs_review

comment:52 Changed 3 years ago by sbrandhorst

  • Branch changed from u/pbruin/4120-binary_quadratic_forms to u/sbrandhorst/4120-binary_quadratic_forms

comment:53 Changed 3 years ago by git

  • Commit changed from cc8a94dce0bec479a459b19f1a40ce9b29a6f136 to e3b838eb154e15c1d45e5a5546d0c049711c5c83

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

e3b838eSmall docfix

comment:54 Changed 3 years ago by sbrandhorst

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):
    

comment:55 Changed 3 years ago by sbrandhorst

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.

comment:56 Changed 3 years ago by sbrandhorst

  • Reviewers changed from John Cremona, Peter Bruin to John Cremona, Peter Bruin, Simon Brandhorst

comment:57 Changed 3 years ago by sbrandhorst

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

comment:58 Changed 3 years ago by cremona

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

comment:59 Changed 3 years ago by pbruin

I agree too.

comment:60 Changed 3 years ago by git

  • Commit changed from e3b838eb154e15c1d45e5a5546d0c049711c5c83 to 3f7ea8360268f1f60128a612ad791d13568ef2d0

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

3f7ea83revert to primitive_only=False

comment:61 Changed 3 years ago by git

  • Commit changed from 3f7ea8360268f1f60128a612ad791d13568ef2d0 to 0a08de0d6d63b969e536f3f57a0c998872b2cb1f

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

0a08de0docfix

comment:62 Changed 3 years ago by sbrandhorst

Then let us finally get this reviewed :)

comment:63 Changed 3 years ago by pbruin

  • Branch changed from u/sbrandhorst/4120-binary_quadratic_forms to u/pbruin/4120-binary_quadratic_forms
  • Commit changed from 0a08de0d6d63b969e536f3f57a0c998872b2cb1f to 748d3908d0fb0deaa683202f521a006020c3da08
  • Status changed from needs_review to positive_review

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

comment:64 Changed 3 years ago by chapoton

  • Milestone changed from sage-8.1 to sage-8.3

comment:65 Changed 3 years ago by vbraun

  • Branch changed from u/pbruin/4120-binary_quadratic_forms to 748d3908d0fb0deaa683202f521a006020c3da08
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:66 Changed 3 years ago by jdemeyer

  • Authors changed from Justin Walker, Jon Hanke, Gonzalo Tornaría, John Cremona to Justin Walker, Jonathan Hanke, Gonzalo Tornaría, John Cremona
  • Commit 748d3908d0fb0deaa683202f521a006020c3da08 deleted
Note: See TracTickets for help on using tickets.