ShortestVectors

[alexdegt-ops]

Hello everyone,

There seems to be a problem with ShortestVectors. This code

E8 :=
[ [ 2, -1, 0, 0, 0, 0, 0, 0 ], [ -1, 2, -1, 0, 0, 0, 0, 0 ], [ 0, -1, 2, -1, 0, 0, 0, 0 ],
  [ 0, 0, -1, 2, -1, 0, 0, 0 ], [ 0, 0, 0, -1, 2, -1, 0, -1 ], [ 0, 0, 0, 0, -1, 2, -1, 0 ],
  [ 0, 0, 0, 0, 0, -1, 2, 0 ], [ 0, 0, 0, 0, -1, 0, 0, 2 ] ];
ShortestVectors(E8, 2, "positive");

returns 49 vectors only (rather than the expected 120 positive roots). I am using GAP 4.13.0 Without positive it works OK.

[fingolfin]

The documentation states:

If the optional argument "positive" is entered, only those vectors x with nonnegative entries are computed.

And among the 120 shortest vectors, there are 49 with this property, which we can confirm like this:

gap> sv:=ShortestVectors(E8, 2);;
gap> Length(sv.vectors);
120
gap> Number(sv.vectors, v -> ForAll(v, x -> x >= 0));
49

So it seems to do exactly what it is supposed to do?

[alexdegt-ops]

Then, it appears that the documentation is misleading. $E_8$ has 120 positive roots, i.e., square 2 vectors with all coefficients non-negative. The other 120 have all coefficients non-positive. (In fact, for square 2 vectors it is always the case.) Considering that ShortestVectors promises one vector from each pair, one would expect that, with “positive”, it would do the right thing and return, say, [ 1, 2, 3, 4, 5, 3, 1, 3 ] instead of the first vector [ -1, -2, -3, -4, -5, -3, -1, -3 ]. Otherwise, honestly, it is not clear what this option is for at all.

For other root lattices that I tried ($E_6$, $E_7$, and not very big $A$ and $D$) it seems to work correctly.

[fingolfin]

You are right, I missed the bit where it states that "... only one of each pair (x,-x)"

[fingolfin]

Fix at #6253

[alexdegt-ops]

Accidentally, since this function is to be reexamined, I have another request. ShortestVectors works quite well with rational matrices (still assuming that integral vectors are to be found) but, for some reason, it insists that the second parameter (square) must be an integer. Judging by the code, this isn't really necessary. I need this function for all kinds of orthogonal complements, and experimentally it works faster when done over $\mathbb{Q}$ rather then in the honest integral orthogonal complement; at the end, appropriate vectors need to be selected anyway. So, currently, I have to choose between clearing the denominators first (extra time to find the lcm) or taking the ceil of the target square (possibly leading to extra parasitic solutions).

In short, my request is removing the check if the second parameter is an integer.

[ThomasBreuer]

When I try $E_7$, I see the same problem:

gap> E7 := [
> [ 2, -1, 0, 0, 0, 0, 0],
> [ -1, 2, -1, 0, 0, 0, 0],
> [ 0, -1, 2, -1, 0, 0, 0],
> [ 0, 0, -1, 2, -1, 0, -1],
> [ 0, 0, 0, -1, 2, -1, 0],
> [ 0, 0, 0, 0, -1, 2, 0],
> [ 0, 0, 0, -1, 0, 0, 2]];;
gap> sv:= ShortestVectors( E7, 2 );;
gap> Length( sv.vectors );
63
gap> sv2:= ShortestVectors( E7, 2, "positive" );;
gap> Length( sv2.vectors );
42

(Each vector in sv has either only nonnegative or only nonpositive entries, but both kinds occur.)

[alexdegt-ops]

You may be right. I hadn't observed an obvious contradiction before I reached $E_8$, whereupon I just switched to the manual selection.