#4120 closed enhancement (fixed)
New code for binary quadratic forms
Reported by:  justin  Owned by:  justin 

Priority:  major  Milestone:  sage8.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: 
Description (last modified by )
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)
Change History (72)
Changed 13 years ago by
comment:1 Changed 13 years ago by
 Milestone set to sage3.1.3
comment:2 Changed 13 years ago by
Justin,
the diff is inverse and you should also add an extension patch to the file.
Cheers,
Michael
Changed 13 years ago by
comment:3 Changed 13 years ago by
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
 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
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
The patch also works with 3.1.3.alpha1. Doctests succeed.
comment:7 Changed 13 years ago by
Here's a second patch, to be applied on top of sage4120.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 byproduct.
comment:8 Changed 13 years ago by
 Owner changed from tbd to justin
This is a third patch, applied on sage41202.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 :}.
comment:9 Changed 13 years ago by
Applied all three patches against 3.1.3.rc0, one at a time, running the doctests each time. All doctests succeeded. No problems noted.
comment:10 Changed 12 years ago by
 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 sagetrac4120new.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
comment:12 Changed 12 years ago by
 Component changed from algebra to quadratic forms
comment:13 Changed 12 years ago by
 Cc justin added
comment:14 Changed 12 years ago by
 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
 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
 Cc tornaria@… added
I've reviewed the code from the last patch as submitted by John Cremona (sagetrac4120.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 inZZ['x,y']
, etc.
 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
 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?
 Q * M is a left action > more natural to be right action!!
I.e. right now
 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.
comment:17 Changed 10 years ago by
 Report Upstream set to N/A
New patch. Primary content is support for indefinite binary forms.
comment:18 Changed 10 years ago by
 Status changed from needs_work to needs_review
comment:19 Changed 10 years ago by
 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
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
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
 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 followup: ↓ 24 Changed 10 years ago by
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
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
 Milestone changed from sage5.11 to sage5.12
comment:26 Changed 7 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:27 Changed 7 years ago by
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.
comment:28 Changed 7 years ago by
 Branch set to u/pbruin/4120binary_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
 Commit changed from b7337f3a218585648a07a1268ba8e65a1887c1a2 to 96c1a86e063e7a7512978c574ec40c84641b66d4
Branch pushed to git repo; I updated commit sha1. New commits:
96c1a86  binary_qf.py: clean up code and documentation

comment:30 Changed 7 years ago by
 Description modified (diff)
 Work issues set to more tests for is_reduced, doc of primitive_only
comment:31 Changed 7 years ago by
 Commit changed from 96c1a86e063e7a7512978c574ec40c84641b66d4 to ece1df7ed9ebb0d5d1f462edcf78024af24d547d
Branch pushed to git repo; I updated commit sha1. New commits:
ece1df7  binary_qf.py: more doctests, add "implementation" parameter for reduction

comment:32 Changed 7 years ago by
 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
 Commit changed from ece1df7ed9ebb0d5d1f462edcf78024af24d547d to dcf854dcfeef37a4b50999a9948b05bf4c629901
Branch pushed to git repo; I updated commit sha1. New commits:
dcf854d  Merge branch 'develop' into ticket/4120binary_quadratic_forms

comment:34 Changed 7 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:35 Changed 7 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:36 Changed 6 years ago by
 Commit changed from dcf854dcfeef37a4b50999a9948b05bf4c629901 to 215cb8a6a67461471df0c4c43d70d555fae2d33b
Branch pushed to git repo; I updated commit sha1. New commits:
215cb8a  Merge branch 'develop' into ticket/4120binary_quadratic_forms

comment:37 Changed 6 years ago by
 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 followup: ↓ 39 Changed 6 years ago by
 Status changed from needs_review to needs_info
This ticket currently confuses the patchbot. Temporarily putting to needs info to stop the bot looptesting it.
comment:39 in reply to: ↑ 38 Changed 6 years ago by
 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 looptesting 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
 Commit changed from 215cb8a6a67461471df0c4c43d70d555fae2d33b to 5657f282979e1cb3c9bf7e49c62bbc606f00c108
Branch pushed to git repo; I updated commit sha1. New commits:
5657f28  Merge branch 'develop' into ticket/4120binary_quadratic_forms

comment:41 Changed 5 years ago by
 Milestone changed from sage6.4 to sage7.4
comment:42 Changed 4 years ago by
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_())))
comment:43 Changed 4 years ago by
 Milestone changed from sage7.4 to sage7.5
and the same for qfbred
, which is now also wrapped.
comment:44 Changed 4 years ago by
 Commit changed from 5657f282979e1cb3c9bf7e49c62bbc606f00c108 to 00a4307ffecf6638466fbac3d41f8ca33f43c829
comment:45 Changed 4 years ago by
 Commit changed from 00a4307ffecf6638466fbac3d41f8ca33f43c829 to 959fbab69cbe7118cc2f5691fcfe5b64f80c966c
comment:46 Changed 4 years ago by
(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
 Milestone changed from sage7.5 to sage8.1
comment:48 Changed 4 years ago by
 Commit changed from 959fbab69cbe7118cc2f5691fcfe5b64f80c966c to 2f580cb6d0a13eb66d84b996113d8880b5748a3c
Branch pushed to git repo; I updated commit sha1. New commits:
2f580cb  Trac 4120: EXAMPLE > EXAMPLES, TEST > TESTS

comment:49 Changed 3 years ago by
 Status changed from needs_review to needs_work
branch does not apply, needs rebase
comment:50 Changed 3 years ago by
 Commit changed from 2f580cb6d0a13eb66d84b996113d8880b5748a3c to cc8a94dce0bec479a459b19f1a40ce9b29a6f136
Branch pushed to git repo; I updated commit sha1. New commits:
cc8a94d  Merge branch 'develop' into ticket/4120binary_quadratic_forms

comment:51 Changed 3 years ago by
 Status changed from needs_work to needs_review
comment:52 Changed 3 years ago by
 Branch changed from u/pbruin/4120binary_quadratic_forms to u/sbrandhorst/4120binary_quadratic_forms
comment:53 Changed 3 years ago by
 Commit changed from cc8a94dce0bec479a459b19f1a40ce9b29a6f136 to e3b838eb154e15c1d45e5a5546d0c049711c5c83
Branch pushed to git repo; I updated commit sha1. New commits:
e3b838e  Small docfix

comment:54 Changed 3 years ago by
Some changes I made:
 removed
@cached_method
inpolynomial
as we already cache in_poly
reduced_form(self, matrix=False, implementation=None):
matrix
seems missleading to me. changed the keywords totransformation
andalgorithm
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
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
 Reviewers changed from John Cremona, Peter Bruin to John Cremona, Peter Bruin, Simon Brandhorst
comment:57 Changed 3 years ago by
Note on my machine tests pass, doc builds and looks reasonable.
comment:58 Changed 3 years ago by
I agree with the decision not to change the default for the primitiveonly parameter.
comment:59 Changed 3 years ago by
I agree too.
comment:60 Changed 3 years ago by
 Commit changed from e3b838eb154e15c1d45e5a5546d0c049711c5c83 to 3f7ea8360268f1f60128a612ad791d13568ef2d0
Branch pushed to git repo; I updated commit sha1. New commits:
3f7ea83  revert to primitive_only=False

comment:61 Changed 3 years ago by
 Commit changed from 3f7ea8360268f1f60128a612ad791d13568ef2d0 to 0a08de0d6d63b969e536f3f57a0c998872b2cb1f
Branch pushed to git repo; I updated commit sha1. New commits:
0a08de0  docfix

comment:62 Changed 3 years ago by
Then let us finally get this reviewed :)
comment:63 Changed 3 years ago by
 Branch changed from u/sbrandhorst/4120binary_quadratic_forms to u/pbruin/4120binary_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 10year anniversary.
comment:64 Changed 3 years ago by
 Milestone changed from sage8.1 to sage8.3
comment:65 Changed 3 years ago by
 Branch changed from u/pbruin/4120binary_quadratic_forms to 748d3908d0fb0deaa683202f521a006020c3da08
 Resolution set to fixed
 Status changed from positive_review to closed
comment:66 Changed 3 years ago by
 Commit 748d3908d0fb0deaa683202f521a006020c3da08 deleted
Context diff of new, old versions of quadratic_forms/binary_qf.py