QuadraticForm.basis_of_short_vectors may not return an actual ZZ-basis

[sagetrac-afiori]

QuadraticForm.basis_of_short_vectors() does not actually ensure the list of vectors it returns is a basis, it only assures that it spans a full rank sub-lattice.

In particular in the following example (E8):

Q = QuadraticForm( matrix( [[2,0,0,0,0,0,0,1],
                            [0,2,1,1,1,1,1,1],
                            [0,1,2,1,1,1,1,1],
                            [0,1,1,2,1,1,1,1],
                            [0,1,1,1,2,1,1,1],
                            [0,1,1,1,1,2,1,1],
                            [0,1,1,1,1,1,2,0],
                            [1,1,1,1,1,1,0,2]] ))
B = Q.basis_of_short_vectors()
matrix(B).det()

The result is -2, which indicates we did not get a basis.

I am attaching some sample code which (once properly merged {and tested}) could be used to correct the issue.

CC: @yyyyx4

Component: quadratic forms

Keywords: basis, automorphisms

Stopgaps: todo

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

[sagetrac-afiori]

Attachment: fix_basis.sage.gz

Sample code to correct a non-basis from basis_of_short_vectors

[jdemeyer]

comment:1

Isn't this just a matter of defining what "basis" means?

[jdemeyer]

Stopgaps: todo

[sagetrac-afiori]

comment:4

I suppose someone might want a rational basis for the associated rational vector space which consists only of integral vectors... but that seems unlikely to be a common use case.
In any case, if I recall correctly... the code which computes automorphism groups of lattices uses this function, and consequently computes the automorphism group of E8 incorrectly.
The simplest stopgap would be to check if you are returning a basis, and if not just return the original basis.
The code I had posted before (before I had learned to build patches under the old system) probably works, though as I don't currently have a working sage install to test it in (and still haven't done anything with current system for building patches) I am not really in a position to do much testing.

[nbruin]

comment:6

It looks to me the well-defined notion here would be the "successive minima" of a lattice: a sequence of vectors in the lattice where each vector is of minimal length while being linearly independent from the previous ones. Such a set is indeed not necessarily a basis. So we should check that the routine actually computes this and then rename it.

I think for most applications, the lengths themselves are usually more important than the vectors that attain them.

Naturally, this notion needs a (positive) definite quadratic form.