The functions in this section are all based on one algorithm which enumerates all vectors of a lattice in a specific range. As the number of vectors of minimal length grows exponentially with the dimension, the general application of this algorithm is restricted to lattices of moderate dimension (up to 40 or 50). However, some tasks like finding a couple of short vectors or finding the minimum of a lattice without symmetry may still be feasible in higher dimensions (even over 100).
For each function which enumerates short vectors of a lattice L, there is a corresponding function which enumerates vectors of L which are close to a given vector w (which usually lies outside L). Note that if one wishes to enumerate short vectors of the coset L + w of the lattice L, where w is any vector of degree compatible with L, one can simply enumerate vectors v in L close to -w and then just take the vectors v + w for each v as the short vectors of the coset.
The functions in this subsection compute invariants of a lattice which
are all related to its minimum.
See [J.H. Conway, N.J.A. Sloane,
Sphere Packings, Lattices and Groups, New York: Springer, 1988.] for
background about minimum, density and kissing numbers.
Minimum(L) : Lat -> RngElt
Return the minimum of the lattice L, i.e., the minimal norm of a non-zero vector in the lattice. Note that this is in general a hard problem and may be very time consuming. See also the attributes section below for how to assert the minimum of a lattice.
Return the centre density of the lattice L, as an element of the real field K. This is defined to be the square root of (Minimum(L)/2)^m / Determinant(L), where m is the rank of L. The argument for the real field K may be omitted, in which case K is taken to be the current default real field.Multiplying the centre density by V_m := pi^(m/2) / (m/2)! gives the ratio of space covered by a sphere packing with spheres of diameter Minimum(L) having the centres of the spheres at the lattice points.
Return the kissing number of the lattice L, which equals the number of vectors of minimal norm (twice the length of the sequence returned by ShortestVectors(L) since that returns only normalized vectors). This is the maximum number of nonoverlapping spheres of diameter Minimum(L) with centres at lattice points which touch a fixed sphere of the same diameter with centre at a lattice point.
> L := Lattice("Lambda", 24);
> time Minimum(L);
4
Time: 0.449
> time KissingNumber(L);
196560
Time: 8.009
> IsEven(L), Norm(L.2);
true 4
Max: RngIntElt Default: Infinity
Return the shortest vectors of the lattice L, i.e., the vectors v in L such that (v, v) is minimal, as a sorted sequence Q. The vectors are computed up to sign (so only one of v and -v appears in Q) and normalized so that the first non-zero entry in each vector is positive, and Q is sorted with respect to lexicographic order. By default, all the (normalized) vectors are computed; the optional parameter Max allows the user to specify the maximal number of computed vectors. Note that unless the minimum of the lattice is already known, it has to be computed by this function, which may be very time consuming.
Max: RngIntElt Default: Infinity
Return the shortest vectors of the lattice L as the rows of a matrix. This is more efficient or convenient for some applications than forming the sequence of vectors. Note that the matrix will lie in the appropriate matrix space and the inner product for L will not be related to the rows of the matrix (which will lie in the appropriate R-space). By default, all the (normalized) vectors are computed; the optional parameter Max allows the user to specify the maximal number of computed vectors.
Max: RngIntElt Default: Infinity
Return the vectors of the lattice L which are closest to the vector w, together with the minimal squared distance d. w may be any element of a lattice of degree n or an R-space of degree n compatible with L, where n is the degree of L. The closest vectors are those vectors v in L such that the squared distance (v - w, v - w) between v and w (and thus the distance between v and w) is minimal; this minimal squared distance is the second return value d. The vectors are returned as a sequence Q, sorted with respect to lexicographic order. Note that the closest vectors are not symmetrical with respect to sign (while the shortest vectors are) so the returned closest vectors are not normalized. By default, all the closest vectors are computed; the optional parameter Max allows the user to specify the maximal number of computed vectors.
Max: RngIntElt Default: Infinity
Return the vectors of the lattice L which are closest to the vector w as a matrix, together with the squared distance d. w may be any element of a lattice of degree n or an R-space of degree n compatible with L, where n is the degree of L. Note that the matrix will lie in the appropriate matrix space and the inner product for L will not be related to the rows of the matrix (which will lie in the appropriate R-space). The vectors are returned as sequence Q, sorted with respect to lexicographic order. Note that the closest vectors are not symmetrical with respect to sign (while the shortest vectors are) so the returned closest vectors are not normalized. By default, all the closest vectors are computed; the optional parameter Max allows the user to specify the maximal number of computed vectors.
> L := Lattice("E", 8);
> S := ShortestVectors(L);
> #S;
120
> KissingNumber(L);
240
> { Norm(v): v in S };
{ 2 }
> Minimum(L);
2
We note that the rank of the space generated by the shortest vectors is
8 so that the successive minima of L are [2, 2, 2, 2, 2, 2, 2, 2]
(see the function SuccessiveMinima below).
> Rank(ShortestVectorsMatrix(L)); 8We next find the vectors in L which are closest to a certain vector in the Q-span of L. The vector is a actually hole of L and the square of its distance from L is 8/9.
> w := RSpace(RationalField(), 8) !
> [ -1/6, 1/6, -1/2, -1/6, 1/6, -1/2, 1/6, -1/2 ];
> C, d := ClosestVectors(L, w);
> C;
[
(-1/2 -1/2 -1/2 -1/2 1/2 -1/2 1/2 -1/2),
(-1/2 1/2 -1/2 -1/2 -1/2 -1/2 1/2 -1/2),
(-1/2 1/2 -1/2 -1/2 1/2 -1/2 -1/2 -1/2),
(-1/2 1/2 -1/2 1/2 1/2 -1/2 1/2 -1/2),
( 1/2 1/2 -1/2 -1/2 1/2 -1/2 1/2 -1/2),
( 0 0 -1 0 0 -1 0 0),
( 0 0 -1 0 0 0 0 -1),
( 0 0 0 0 0 -1 0 -1),
(0 0 0 0 0 0 0 0)
]
> d;
8/9
> { Norm(v): v in C };
{ 0, 2 }
We verify that the squared distance of the vectors in C from w is
8/9.
> { Norm(v - w): v in C };
{ 8/9 }
We finally notice that these closest vectors are in fact amongst the
shortest vectors of the lattice (together with the zero vector).
> Set(C) subset (Set(S) join {-v: v in S} join { L!0 });
true
Max: RngIntElt Default: Infinity
Return the vectors of the lattice L with norm within the prescribed range, together with their norms, as a sorted sequence Q. The sequence Q contains tuples of the form <v, r> where v is a vector and r its norm. Either one positive number u can be given, specifying the range (0, u], or a pair l, u of positive numbers, specifying the range [l, u]. The vectors are computed up to sign (so only one of v and -v appears in Q) and normalized so that the first non-zero entry in each vector is positive, and Q is sorted with respect to first the norms and then the lexicographic order for the vectors. By default, all the (normalized) vectors with norm in the prescribed range are computed; the optional parameter Max allows the user to specify the maximal number of computed vectors.
Max: RngIntElt Default: Infinity
This is very similar to ShortVectors, but returns the vectors of the lattice L with norm within the prescribed range as the rows of a matrix S rather than as a sequence of tuples. This is more efficient or convenient for some applications than forming the sequence. By default, all the (normalized) vectors with norm in the prescribed range are computed; the optional parameter Max allows the user to specify the maximal number of computed vectors. Note that the matrix will lie in the appropriate matrix space and the inner product for L will not be related to the rows of the matrix (which will lie in the appropriate R-space).
Max: RngIntElt Default: Infinity
Return the vectors of the lattice L whose squared distance from the vector w is within the prescribed range, together with their squared distances, as a sorted sequence Q. The returned sequence Q contains tuples of the form <v, d> where v is a vector from L and d=(v - w, v - w) is its squared distance from w. w may be any element of a lattice of degree n or an R-space of degree n compatible with L, where n is the degree of L. Either one positive number u can be given, specifying the range (0, u], or a pair l, u of positive numbers, specifying the range [l, u]. Note that close vectors are not symmetrical with respect to sign (while short vectors are) so the returned close vectors are not normalized. Q is sorted with respect to first the squared distances and then the lexicographic order for the vectors. By default, all the vectors with squared distance in the prescribed range are computed; the optional parameter Max allows the user to specify the maximal number of computed vectors.
Max: RngIntElt Default: Infinity
This is very similar to CloseVectors, but returns the vectors of the lattice L whose squared distance from the vector w is within the prescribed range as the rows of a matrix C rather than as a sequence of tuples. This is more efficient or convenient for some applications than forming the sequence. w may be any element of a lattice of degree n or an R-space of degree n compatible with L, where n is the degree of L. By default, all the close vectors are computed; the optional parameter Max allows the user to specify the maximal number of computed vectors. Note that the matrix will lie in the appropriate matrix space and the inner product for L will not be related to the rows of the matrix (which will lie in the appropriate R-space).
b_1 = (2, 0, ..., 0, n a_1, 0) b_2 = (0, 2, ..., 0, n a_2, 0) ... b_n = (0, 0, ..., 2, n a_2, 0) b_(n+1) = (1, 1, ..., 1, n s, 1).Then every vector v = (v_1, ..., v_(n+2)) in L such that the norm of v is n+1 and v_1, ..., v_n, v_(n+2) in {+-1}, v_(n+1)=0, yields the solution x_i = | v_i - v_(n+2) | / 2 for i=1, ..., n to the original equation.
We first write a function KnapsackLattice which, given the sequence Q and sum s, creates a matrix X representing the above basis and returns the lattice generated by the rows of X. Note that the Lattice creation function will automatically LLL-reduce the matrix X as it creates the lattice.
> function KnapsackLattice(Q, s) > n := #Q; > X := RMatrixSpace(IntegerRing(), n + 1, n + 2) ! 0; > for i := 1 to n do > X[i][i] := 2; > X[i][n + 1] := n * Q[i]; > X[n + 1][i] := 1; > end for; > X[n + 1][n + 1] := n * s; > X[n + 1][n + 2] := 1; > return Lattice(X); > end function;We next write a function Solutions which uses the function ShortVectors to enumerate all vectors of the lattice L having norm exactly n + 1 and thus to find all solutions to the Knapsack problem associated with L. (Note that the minimum of the lattice may be less than n + 1.) The function returns each solution as a sequence of indices for Q.
> function KnapsackSolutions(L)
> n := Rank(L) - 1;
> M := n + 1;
> S := ShortVectors(L, M, M);
> return [
> [i: i in [1 .. n] | v[i] ne v[n + 2]]: t in S |
> forall{i: i in [1 .. n] cat [n + 2] | Abs(v[i]) eq 1} and
> v[n + 1] eq 0 where v is t[1]
> ];
> end function;
We now apply our functions to a sequence Q of 12 integers each less than
1000 and the sum 2676. There are actually 4 solutions. We verify
that each gives the original sum.
> Q := [ 52, 218, 755, 221, 574, 593, 172, 771, 183, 810, 437, 137 ];
> s := 2676;
> L := KnapsackLattice(Q, s);
> L;
Lattice of rank 13 and degree 14
Basis:
( 0 0 0 0 2 0 0 0 0 0 -2 -2 0 0)
( 1 1 1 1 -1 -1 -1 -1 1 1 1 -1 0 -1)
( 1 1 -1 -1 -1 1 -1 -1 -1 1 1 1 0 1)
( 0 2 0 0 0 0 -2 0 -2 0 0 2 0 0)
( 2 0 0 2 0 -2 0 0 2 0 0 2 0 0)
( 0 0 2 0 0 -2 2 -2 0 0 2 0 0 0)
( 3 -1 1 1 -1 1 -1 -1 -1 -1 1 1 0 1)
( 1 1 1 -1 -1 1 1 -1 1 -1 -1 3 0 1)
( 1 -1 -1 3 -1 -1 1 1 -1 1 -1 -1 0 1)
( 1 -1 -1 1 1 1 1 -1 -3 1 1 -1 0 -1)
( 1 3 -3 1 -1 1 1 1 1 -1 1 1 0 1)
( 1 1 1 -3 1 -1 3 1 1 -1 -1 -1 0 -1)
( 1 -1 -1 1 -1 1 1 1 -1 -1 1 -1 -12 1)
> S := KnapsackSolutions(L);
> S;
[
[ 2, 3, 4, 5, 8, 12 ],
[ 3, 4, 5, 7, 8, 9 ],
[ 3, 4, 7, 8, 9, 11, 12 ],
[ 1, 2, 3, 4, 9, 10, 11 ]
]
> [&+[Q[i]: i in s]: s in S];
[ 2676, 2676, 2676, 2676 ]
Finally, we apply our method to a larger example. We let Q be a sequence
consisting of 50 random integers in the range [1, 2^(1000)]. We
let I be a random subset of {1 ... 50} and let s be the sum
of the elements of Q indexed by I. We then solve the Knapsack problem
with input (Q, s) and this time obtain I as the only answer.
> b := 1000;
> n := 50;
> SetSeed(1);
> Q := [Random(1, 2^b): i in [1 .. n]];
> I := {};
> while #I lt n div 2 do
> Include( I, Random(1, n));
> end while;
> I := Sort(Setseq(I)); I;
[ 1, 4, 5, 8, 9, 10, 13, 16, 19, 23, 24, 26, 29, 30, 31, 32, 33, 34,
35, 37, 38, 40, 42, 47, 48 ]
> s := &+[Q[i]: i in I]; Ilog2(s);
1003
> time L := KnapsackLattice(Q, s);
Time: 25.930
> [Ilog2(Norm(b)): b in Basis(L)];
[ 5, 45, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46,
46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46,
46, 46, 46, 46, 46, 46, 46, 46, 46, 47, 47, 47, 47, 47, 47, 47, 47 ]
> time KnapsackSolutions(L);
[
[ 1, 4, 5, 8, 9, 10, 13, 16, 19, 23, 24, 26, 29, 30, 31, 32, 33,
34, 35, 37, 38, 40, 42, 47, 48 ]
]
Time: 1.579
> G := MatrixGroup< 8, Integers() | > [ -673, -291, -225, -316, 250, -32, 70, -100, > 252, 274, 349, 272, -156, -94, -296, 218, > 2532, 1159, 609, 5164, -1450, -181, 188, 742, > -551, 163, 629, -1763, 285, -162, -873, 219, > -2701, -492, 411, -3182, 1062, -397, -1195, 151, > -5018, -1112, 1044,-12958, 2898, -153, -2870, -454, > 2581, 90, -1490, 8197, -1553, 261, 2556, -149, > -3495, -2776, -3218, -2776, 1773, 652, 2459, -1910], > [ 2615, 1314, 1633, 400, -950, -1000, -2480, 1049, > 161, 159, 347, -657, 2, -385, -889, 230, > -2445, -1062, -1147, 269, 744, 1075, 2441, -795, > 1591, 925, 1454, -1851, -350, -1525, -3498, 982, > 10655, 5587, 7476, -1751, -3514, -5575,-13389, 4873, > 6271, 3253, 4653, -6126, -1390, -5274,-11904, 3219, > -3058, -1749, -2860, 5627, 392, 3730, 8322, -2009, > 4875, 1851, 1170, 5989, -2239, 625, 1031, 692] >; > Order(G); 60Since the group is small enough we can generate elements in the endomorphism ring by averaging over the group elements.
> M := MatrixRing(Integers(), 8); > e := [ &+[ M!g * MatrixUnit(M, i, i) * M!(g^-1) : g in G ] : i in [1..4] ]; > E := sub<M | e>; > Dimension(E); 4We now transform E into a lattice of dimension 4 and degree 64 and rescale the basis vectors so that they have lengths of the same order of magnitude.
> L := Lattice(64, &cat[ Eltseq(b) : b in Basis(E) ]); > LL := sub<L | [ Round( Norm(L.4)/Norm(L.i) ) * L.i : i in [1..4] ]>; > Minimum(LL); 910870284600 > SV := ShortVectors(LL, 100*Minimum(LL)); > #SV; 46 > Sing := [ X : v in SV | Determinant(X) eq 0 where X is M!Eltseq(v[1]) ]; > #Sing; 3We thus have found three singular elements amongst the 46 shortest vectors and use the kernel of the first of these to get the representation on a subspace of dimension 4.
> ker := LLL( KernelMatrix(Sing[1]) );
> ker;
[10 0 -9 5 -2 0 5 -4]
[ 3 4 -1 16 -3 -5 -4 3]
[ 8 11 10 1 -4 0 -6 5]
[ 2 10 6 0 -2 10 11 0]
> H := MatrixGroup<4, Integers() | [Solution(ker, ker*g) : g in Generators(G)]>;
> H;
MatrixGroup(4, Integer Ring)
Generators:
[ 1 0 0 0]
[-2 3 -9 5]
[-2 1 -7 4]
[-2 0 -7 4]
[ 0 0 2 -1]
[ 0 -1 4 -2]
[ 2 0 -3 2]
[ 3 1 -8 5]
> #H;
60
Given a lattice L and a range, create a corresponding short vectors lattice enumeration process P. This process provides the environment for enumerating each vector v in L with norm within the range. Either a positive number u can be given, specifying the range (0, u], or a pair l, u of positive numbers, specifying the range [l, u]. Successive calls to NextVector (see below) will result in the enumeration of the vectors.
Given a lattice L, a vector w and a range, create a corresponding close vectors lattice enumeration process P. This process provides the environment for enumerating each vector v in L such its squared distance (v - w, v - w) from w is within the range. w may be any element of a lattice of degree n or an R-space of degree n compatible with L, where n is the degree of L. Either a positive number u can be given, specifying the range (0, u], or a pair l, u of positive numbers, specifying the range [l, u]. Successive calls to NextVector (see below) will result in the enumeration of the vectors.
Given a lattice enumeration process P as created by ShortVectorsProcess or CloseVectorsProcess, return the next element found in the enumeration.If the process is for short vectors, the next short vector of the specified region of the lattice is returned together with its norm, or the zero vector together with -1, indicating that the enumeration process has been completed. The vectors are computed up to sign (so that only one of v and -v will be enumerated) and normalized so that the first non-zero entry in each vector is positive.
If the process is for the vectors close to w, the next close vector v whose squared distance d=(v - w, v - w) from w is in the specified range is returned together with d, or the zero vector together with -1, indicating that the enumeration process has been completed. The close vectors are not symmetrical with respect to sign (while short vectors are) so the returned close vectors are not normalized. Note also that to test for completion the second return value should be tested for equality with -1 (or, preferably, the next function IsEmpty should be used) since the zero vector could be a valid close vector.
Note that the order of the vectors returned by this function in each case is arbitrary, unlike the previous functions where the resulting sequence or matrix is sorted.
Given a lattice enumeration process P, return whether the process P has found all short or close vectors.
Return the first k successive minima of lattice L, or all of the m successive minima of L if k is omitted, where m is the rank of L. The first k successive minima M_1, ..., M_k of a lattice L are defined by the property that M_1, ..., M_k are minimal such that there exist linearly independent vectors l_1, ..., l_k in L with (l_i, l_i) = M_i for 1 <= i <= k. The function returns a sequence containing the minima M_i and a sequence containing the vectors l_i. The lattice L must be an exact lattice (over Z or Q). Note that the minima are unique but the vectors are not.
Given an integral lattice L and a small positive integer n, return the Theta series Theta_L(q) of L as a formal power series in q to precision n (i.e., up to and including the coefficient of q^n). The coefficient of q^k in Theta_L(q) is defined to be the number of vectors of norm k in L. Note that this function needs to enumerate all vectors of L having norm up to and including n, so its application is restricted to lattices where the number of these vectors is reasonably small. The lattice L must be an exact lattice (over Z or Q). Note that the angle bracket notation should be used to assign a name to the indeterminate for the returned Theta series (e.g., T<q> := ThetaSeries(L);).
> function Theta(L, n) > Z := IntegerRing(); > P := ShortVectorsProcess(L, n); > C := [1] cat [0: i in [1 .. n]]; > while not IsEmpty(P) do > v, norm := NextVector(P); > C[Z!norm + 1] +:= 2; > end while; > return PowerSeriesRing(IntegerRing()) ! C; > end function;We now compute the Theta series up to norm 10 of the Gosset lattice E_8 using the function Theta. We compare this Magma-language version with the builtin function ThetaSeries (which is much faster of course because of the lack of interpreter overhead etc.).
> L := Lattice("E", 8);
> time T<q> := Theta(L, 10);
Time: 2.210
> T;
1 + 240*q^2 + 2160*q^4 + 6720*q^6 + 17520*q^8 + 30240*q^10 + O(q^11)
> time TT := ThetaSeries(L, 10);
Time: 0.039
> TT eq T;
true