The functions in this section are all based on one algorithm which enumerates all vectors of a lattice in a specified hyperball [FP83], [Kan83], [SE94]. As the underlying computational problems (the Shortest and Closest Lattice Vector Problems) are hard [Ajt98], [vEB81], the general application of this algorithm is restricted to lattices of moderate dimension (up to 50 or 60). 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. The function EnumerationCost provides an estimate of the cost of running the enumeration algorithm on a specified input. This allows to know beforehand if the computation is likely to terminate within a reasonable amount of time.
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∈L close to -w and then just take the vectors v + w for each v as the short vectors of the coset.
The enumeration routine underlying all the functions described below relies on floating-point approximations. However, it can be run in a rigorous way in some cases, see [PS08]. By default, the outputs of the functions Minimum, PackingRadius, HermiteNumber, CentreDensity, Density, KissingNumber, ShortestVectors, ShortestVectorsMatrix, ShortVectors, ShortVectorsMatrix and ThetaSeries are guaranteed to be correct. This correctness guarantee can be turned off by setting the optional parameter Proof to false. However, this comes virtually for free, the additional computations being most often negligible. In the present version of Magma, the outputs of all other functions are only likely to be correct.
The enumeration algorithm from [FP83], [Kan83], [SE94] can be interpreted as a search within a large tree. This can be extremely time-consuming. Schnorr, Euchner and Hörner [SE94], [SH95] introduced techniques to prune the latter tree: the correct output might be missed, but the execution of the algorithm is likely to terminate faster. A new pruning strategy is available for the functions Minimum, PackingRadius, HermiteNumber, CentreDensity, Density, KissingNumber, ShortestVectors, ShortestVectorsMatrix, ShortVectors, ShortVectorsMatrix and ThetaSeries. Naturally, if the pruning strategy is used, the result cannot be guaranteed to be correct anymore. Let (b1, b2, ..., bd) be a basis of a lattice L, let (b1 * , b2 * , ..., bd * ) denote its Gram-Schmidt orthogonalisation, and let μi, j = (bi, bj * )/|bj * |2 for i ≥j. Suppose we are interested in finding all vectors in L of norm ≤u. The enumeration algorithm considers the equations: | ∑j=id ( ∑k=jd μk, j xk ) bj * |2 ≤u, for i=d, d - 1, ..., 1,
where the xk's are integers. If the Prune optional parameter is set to [p1, ..., pd], then the equations above will be replaced by:
| ∑j=id ( ∑k=jd μk, j xk ) bj * |2 ≤pi u, for i=d, d - 1, ..., 1.
The pi's must belong to the interval [0, 1]. For a given input ((b1, ..., bd), u) to the enumeration procedure, it is possible to heuristically estimate both the running-time gain and the probability of missing a solution. See Subsection Lattice Enumeration Utilities for more details.
The functions in this subsection compute invariants of a lattice which are all related to its minimum. See [JC98] for background about minimum, density and kissing numbers.
Proof: BoolElt Default: true
Prune: SeqEnum Default: [1.0, ...,1.0]
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.
Proof: BoolElt Default: true
Prune: SeqEnum Default: [1.0, ...,1.0]
The packing radius is half the square root of the minimum of the non-zero lattice L.
Return the n-th Hermite constant raised to the power of n. The exact value is provided if n ≤8 or n=24, and otherwise an upper bound is returned. The n-th Hermite constant is defined as the maximum of Min(L)/Determinant(L)1/n over all n-dimensional lattices L, and this intrinsic returns the nth power of this.
Proof: BoolElt Default: true
Prune: SeqEnum Default: [1.0, ...,1.0]
Return the Hermite number, Min(L)/Determinant(L)^(1/(Dimension)(L)), of the non-zero lattice L.
Proof: BoolElt Default: true
Prune: SeqEnum Default: [1.0, ...,1.0]
The center density of the lattice L, as an element of the real field K. This is defined to be the square root of (Min(L)/4)^(Rank(L))/(Determinant(L)). The argument for the real field K may be omitted, in which case K is taken to be the current default real field.The product of the centre density by the volume of a sphere of radius 1 in n-dimensional space gives the density of the lattice-centered sphere packing of L, called the density of the lattice.
Proof: BoolElt Default: true
Prune: SeqEnum Default: [1.0, ...,1.0]
The density of the lattice L, as an element of the real field K, i.e., the density of the lattice-centered sphere packing. If the argument for the real field K is omitted, the field K is taken to be the default real field.
Proof: BoolElt Default: true
Prune: SeqEnum Default: [1.0, ...,1.0]
Return the kissing number of the lattice L, which equals the number of vectors of minimal non-zero 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);
> IsEven(L), Norm(L.2);
true 4
> time Minimum(L);
4
Time: 0.020
> Density(L);
0.00192957430940392304790334556369
> time KissingNumber(L);
196560
Time: 0.180
Max: RngIntElt Default: ∞
Proof: BoolElt Default: true
Prune: SeqEnum Default: [1.0, ...,1.0]
Return the shortest non-zero vectors of the lattice L, i.e., the vectors v∈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: ∞
Proof: BoolElt Default: true
Prune: SeqEnum Default: [1.0, ...,1.0]
Return the shortest non-zero 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.
Return a single non-zero shortest vector of the lattice L. This is equivalent to calling ShortestVectors with the parameter Max := 1 and extracting the single vector.
Max: RngIntElt Default: ∞
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∈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: ∞
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.
Return a single vector of the lattice L which is closest to the vector w. This is equivalent to calling ClosestVectors with the parameter Max := 1 and extracting the single vector.
> 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 an actual 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: ∞
Proof: BoolElt Default: true
Prune: SeqEnum Default: [1.0, ...,1.0]
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: ∞
Proof: BoolElt Default: true
Prune: SeqEnum Default: [1.0, ...,1.0]
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).
Return a single non-zero vector of the lattice L with norm within the prescribed range, or the zero vector of L if there is no such vector. This is equivalent to calling one of the above functions with the parameter Max := 1 and extracting the single vector when it exists.
Max: RngIntElt Default: ∞
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.
Note that CloseVectors does not try to improve the given basis for enumeration purposes (for instance, with LLL and EnumerationCost). It always operates with respect to the BasisMatrix (and InnerProductMatrix) of the lattice, though internal manipulations are done to move the problem from the input ring(s) to the integers before an enumeration is done.
Also, if the target vector is in the lattice, one can gain a factor of 2 by transforming the problem to use ShortVectors (which identifies a vector with its additive inverse in the output).
Max: RngIntElt Default: ∞
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).
Return a single non-zero vector of the lattice L whose squared distance from the vector w is within the prescribed range, or the zero vector of L if there is no such vector. This is equivalent to calling one of the above functions with the parameter Max := 1 and extracting the single vector when it exists.
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
Determinant: 1846735827632128
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)
( 1 1 1 1 -3 1 1 -1 -1 1 -1 -1 0 1)
( 1 -1 -3 1 1 -1 -1 1 -1 1 1 1 0 1)
( 2 2 0 0 0 -2 2 2 -2 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 3 -1 -1 -1 -1 1 0 -1)
(-1 -1 -1 -1 1 1 1 1 -1 -1 -1 1 0 1)
( 2 0 0 2 0 2 0 0 0 0 -2 0 0 -2)
(-1 -1 -1 1 1 -1 -1 1 -1 1 1 -3 0 -1)
(-1 -1 1 -1 -1 1 -1 -1 -1 3 -1 1 0 -3)
( 0 -2 0 0 2 0 -2 0 -2 0 0 0 12 0)
> 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, 21000]. 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, 3, 4, 7, 10, 11, 13, 14, 18, 20, 22, 23, 26, 28, 29, 34, 35, 37, 40, 41,
42, 45, 48, 49, 50 ]
> s := &+[Q[i]: i in I]; Ilog2(s);
1003
> time L := KnapsackLattice(Q, s);
Time: 0.570
> [Ilog2(Norm(b)): b in Basis(L)];
[ 5, 46, 46, 45, 47, 47, 46, 46, 46, 46, 46, 46, 46, 45, 47, 46, 46, 46, 46,
47,46, 46, 45, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 45, 46, 46,
45, 45, 46, 46, 46, 46, 46, 45, 46, 46, 46, 46, 46 ]
> time KnapsackSolutions(L);
[
[ 1, 3, 4, 7, 10, 11, 13, 14, 18, 20, 22, 23, 26, 28, 29, 34, 35, 37, 40,
41, 42, 45, 48, 49, 50 ]
]
Time: 0.040
> 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]
[-13 3 4 10 1 5 8 2]
> H := MatrixGroup<4, Integers() | [Solution(ker, ker*g) : g in Generators(G)]>;
> H;
MatrixGroup(4, Integer Ring)
Generators:
[ 1 0 0 0]
[-3 -2 -4 -5]
[-2 -3 -3 -4]
[ 2 3 4 5]
[-1 -1 -1 -1]
[ 2 1 2 2]
[-4 -2 -1 -2]
[ 3 2 1 2]
> #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∈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∈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 M1, ..., Mk of a lattice L are defined by the property that M1, ..., Mk are minimal such that there exist linearly independent vectors l1, ..., lk in L with (li, li) = Mi for 1 ≤i ≤k. The function returns a sequence containing the minima Mi and a sequence containing the vectors li. The lattice L must be an exact lattice (over Z or Q). Note that the minima are unique but the vectors are not.This uses ShortVectors and then tests for independence, and thus can be quite expensive. In particular, for skewed lattices in low dimensions it is often not the right tool, as many inutile short vectors will be found. In many cases, the diagonal entries from the Gram matrix of a suitable reduction are sufficiently good approximations. An example where the problem can be seen to occur: a 20-dimensional lattice with a 5-dimensional subspace generated by vectors of norm 105, with the shortest vector not in this subspace having around norm 1090. To rigorously determine the 6th minima by direct vector enumeration is hopeless, and to use trickier methods, such as cosets of the subspace, would involve around (105)5 sublattices.
Proof: BoolElt Default: true
Prune: SeqEnum Default: [1.0, ...,1.0]
Given an integral lattice L and a small positive integer n, return the Theta series ΘL(q) of L as a formal power series in q to precision n (i.e., up to and including the coefficient of qn). The coefficient of qk in Θ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 E8 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: 0.050
> T;
1 + 240*q^2 + 2160*q^4 + 6720*q^6 + 17520*q^8 + 30240*q^10
> time TT<r> := ThetaSeries(L, 10);
Time: 0.000
> TT;
1 + 240*q^2 + 2160*q^4 + 6720*q^6 + 17520*q^8 + 30240*q^10 + O(q^11)
Proof: BoolElt Default: true
Prune: SeqEnum Default: [1.0, ...,1.0]
Restriction of ThetaSeries to integral lattices.
(Procedure.) Set the verbose printing level for the lattice enumeration algorithm to be v. Currently the legal values for v are true, false, 0, and 1 (false is the same as 0, and true is the same as 1). When the verbose level is non-zero, some information about the current status of the enumeration algorithm is printed out every 15 seconds. This concerns the functions Minimum, CentreDensity, CenterDensity, Density, KissingNumber, ShortestVectors, ShortestVectorsMatrix, ShortVectors, ShortVectorsMatrix and ThetaSeries.
Prune: SeqEnum Default: [1.0, ...,1.0]
Estimate the number of nodes in the tree to be visited during the execution of the enumeration algorithm, for the lattice L and an hyperball of squared radius u. If u is not provided, an upper bound to the lattice minimum is used. Since the cost per tree node is relatively constant, this function can be used to obtain a heuristic estimate of the running-time of the enumeration algorithm. Note that in some cases the enumeration may run faster than expected, because the tree to be visited may be shrunk during the execution, as described in [SE94]. Contrary to the enumeration itself, this function runs in time polynomial in the input bit-size (if the value of the Prune optional parameter is the default one). It relies on the Gaussian heuristic, which consists in estimating the number of integral points within an n-dimensional body by its volume (see [HS07] for more details).If the Prune parameter is set to [p1, ..., pd], then EnumerationCost estimates the cost of the tree pruned with the strategy described in the introduction of the present section, with pruning coefficients p1, ..., pd. Although the enumeration itself is likely to terminate faster, the estimation of the cost may be significantly more time-consuming.
The actual speed of enumeration depends on the dimension, and to a lesser extent on the shape of the lattice. The main task at each step is to calculate an inner product; if the dimension is large this will take longer, while if the lattice doesn't have too many short vectors, the tree search will not spend so much time with long(er) inner products. As a general guess, on a desktop machine 25 million vectors can be searched per second in dimension 40.
Prune: SeqEnum Default: [1.0, ...,1.0]
Estimate the number of nodes in each layer of the tree to be visited during the execution of the enumeration algorithm, for the lattice L and a hyperball of squared radius u. If u is not provided, an upper bound to the lattice minimum is used.
> B:=RMatrixSpace(IntegerRing(), 50, 51) ! 0; > for i := 1 to 50 do B[i][1] := RandomBits(1000); end for; > for i := 1 to 50 do B[i][i+1] := 1; end for; > B := LLL(B); > EnumerationCost (Lattice(B)); 4.06E18
The value above is an estimate of the number of nodes in the enumeration tree that corresponds to the computation of the shortest non-zero vectors in the lattice spanned by the rows of B. This is much too high to have a chance to terminate. Reducing B further allows us to compute these shortest non-zero vectors.
> B:=LLL(B:Delta:=0.999); > EnumerationCost(Lattice(B)); 1.03E13 > B:=LLL(B:Delta:=0.999, DeepInsertions); > EnumerationCost(Lattice(B)); 7.43E7 > time _:=ShortestVectors(Lattice(B)); 3.660
In larger dimensions, reducing the lattice further may not prove sufficient to make the enumeration reasonably tractable. Then pruning the enumeration tree can be considered.
> B:=RMatrixSpace(IntegerRing(), 65, 66) ! 0; > for i := 1 to 65 do B[i][1] := RandomBits(1000); end for; > for i := 1 to 65 do B[i][i+1] := 1; end for; > B := LLL(B:Delta:=0.999); > B := LLL(B:Delta:=0.999, DeepInsertions); > EnumerationCost(Lattice(B)); 2.77E12 > p:=[1.0: i in [1..65]]; > for i:=10 to 55 do p[i] := (100-i)/90.; end for; > for i:=56 to 65 do p[i]:=0.5; end for; > EnumerationCost(Lattice(B):Prune:=p); 1.75E10 > time _:=ShortestVectors(Lattice(B):Prune:=p); Time: 422.120
Assuming that the number of visited tree nodes per time unit remains roughly constant, the execution would have taken around 18 hours without pruning. It is possible to estimate the likeliness of not missing the optimal solution, by looking at the first coefficient returned by EnumerationCostArray. Assuming the Gaussian heuristic, this is the ratio between the first coefficients of EnumerationCostArray with and without the pruning table.
> t1:= EnumerationCostArray(Lattice(B):Prune:=p)[1]; > t2:= EnumerationCostArray(Lattice(B))[1]; > t1/t2; 0.992
Experimentally, it seems that pruning coefficients that decrease linearly (except for the first and last indices) provide good trade-offs between efficiency gain and success likeliness.
> SetNthreads(4); // 4 threads > L := Lattice(LatticeDatabase(),"Leech"); > D := DirectSum([L,L]); // dimension 48 > cpu := Cputime(); t := Time(); > ThetaSeries(D,6); // real time of 1 min 1 + 393120*$.1^4 + 33546240*$.1^6 + O($.1^7) > Cputime(cpu); Time(t); 210.020 60.740[r]
There are situations where parallelization is not beneficial, or even harmful. For instance, when ShortVectors returns thousands or millions of vectors, these will need to put serially into a Magma array, and thus any gains from a parallel search will likely be lost. Also, in lattices of small dimension the splitting into parallel parts need not be too efficient.