[with new patch, needs work] New code for binary quadratic forms

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

Justin,

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

Cheers,

Michael

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

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.

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

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.

To be applied on top of sage-4120.patch

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

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

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

REPLACES earlier patches

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.

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

Cheers,

Michael

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