Lattice Rules by Component Scaling^{∗}

J. N. Lyness^{†}  T. Sørevik^{‡}

Abstract

We introduce a theory of rectangular scaling of integer lattices. This may be used to construct families of lattices. We determine the relation between the Zaremba index ρ(Λ) of various members of the same family. It appears that if one member of a family has a high index, some of the other family members of higher order may have extraordinarily high indices.

We have applied a technique based on this theory to lists of good lattices available to us. This has enabled us to construct lists of excellent previously-unknown lattices of high order in three and four dimensions and of moderate order in five dimensions.

AMS Subject Classification: 65D32 06B99 Key words: lattice rules, number theoretic rules, Zaremba index, figure of merit, scaled lattice

1 Background

The purpose of this paper is to find s-dimensional integer lattices Λ that have relatively high Zaremba indices or figures of merit. This index may be defined in terms of absolute values of the nonzero components of a lattice point x = (x_{1}, x_{2}, ..., x_{s}).

Definition 1 The product coordinate distance function of x is

ρ(x) = x̄_{1}x̄_{2}...x̄_{s},  (1.1)

where

\overline{x_{i}} = max(| x_{i} |, 1).  (1.2)

In terms of this we have the following definition.

∗This work was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy, under Contract W-31-109-Eng-38, and by the Norwegian Council for Humanities and Science.

†Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL ‡Dept. of Informatics, University of Bergen, Norway

Definition 2 The Zaremba index or figure of merit, ρ(Λ), of an s-dimensional integer lattice is

ρ(Λ) = min_{x∈Λ;x≠0} ρ(x).  (1.3)

Note that all lattice points of an integer lattice have integer components. Thus ρ(x) and ρ(Λ) are positive integers. In Section 3 we shall generalize this definition to other point sets.

The Zaremba index, ρ(Λ), is a recognized measure of efficiency of the multidimensional quadrature rule based on Λ_{Q}, the lattice reciprocal to Λ. This lattice rule employs all N points of Λ_{Q} lying in [0, 1)^{s}, N being the order of Λ. Thus, attention has been devoted to searching in L_{s}(N), the set of s-dimensional integer lattices of order N, with a view to finding optimal lattices of this order, that is, lattices Λ′ for which ρ(Λ′) coincides with

ρ_{s}(N) = max_{Λ∈L_{s}(N)} ρ(Λ).  (1.4)

It is convenient to introduce a “measure of goodness” of a lattice using which one can compare lattices having different values of N. Our measure is based on the Zaremba conjecture that suggests that there exists a constant z_{s} such that

ρ_{s}(N) ≤ z_{s} \frac{N}{(log N)^{s−2}} ; s ≥ 2.  (1.5)

For s = 2 the conjecture has been proved by Zaremba [Zar66]. Following Kedem and Zaremba [KZ74], we assign to every lattice a value defined by

z(Λ) = \frac{ρ(Λ)(log N)^{s−2}}{N} .  (1.6)

This is of course nothing more than a scaled version of ρ(Λ). However, this value is useful when examining a list that contains lattices of different orders N to recognize quickly those lattices which have an outstanding value of ρ.

This paper is not directly concerned with the conjectures on which such estimates are based. We note, however, that there exists a bound on ρ_{s}(N) of order O(N/(log N)^{s−1})

[Zar74] and that both the conjecture and bound are in the context of number theoretic rules; that is they are restricted to lattice rules of rank 1.

For an account of the general theory, of which this conjecture forms part, we refer the reader to recent papers by Niederreiter [Nie88],[Nie92], who has extended the theory to cover lattice rules of general rank. This developing theory is mainly devoted to existence proofs and asymptotic bounds. The present paper, on the other hand, is devoted to providing concrete examples of lattices whose reciprocal may be used to construct costeffective lattice rules. These examples seem to confirm the theory and are in compliance with the truth of the conjecture.

In our searches [LS91] and [LS92], each integer lattice Λ is represented by an s × s generator matrix B. All elements of Λ are integer weighted sums of the rows of B, and Λ is of order N =| det B |. The lattice Λ_{Q} on which the corresponding lattice rule is based has a generator matrix A = (B^{−1})^{T}.

2 Component Scaled Lattices

Theorem 3 Given s nonzero real numbers k_{1}, k_{2}, ..., k_{s} and a lattice Λ, there exists a lattice Λ′ such that

p = (p_{1}, p_{2}, ..., p_{s}) ∈ Λ ⇔ p′ = (k_{1}p_{1}, k_{2}p_{2}, ..., k_{s}p_{s}) ∈ Λ′.  (2.1)

The proof is almost trivial, whatever definition of a lattice is invoked.

Definition 4 Λ′ in the theorem is termed a rectangularly scaled version of Λ, obtained by using an s-dimensional scaling factor (k_{1}, k_{2}, ..., k_{s}) or a scaling matrix K = diag(k_{1}, k_{2}, ..., k_{s}). N_{K} =| det(K) |=| ∏_{i=1}^{s} k_{i} | is called the order of this scaling.

Rectangular scaling of a lattice has several trivial and obvious properties. In particular, a set of successive scaling operations is itself a scaling operation, and the scaling operation is commutative. If B is a generator matrix for Λ, then BK is one for Λ′. When Λ and Λ′ are scaled versions of one another, so are their reciprocal lattices, Λ^{⊥} and Λ^{⊥′}; the scaling matrices involved are inverses of one another.

It appears that, when one confines oneself to the set of integer lattices, one may construct distinct families of lattices, in which each member is a rectangularly scaled version of every other member. Each family is specified by a unique family root lattice Λ.

Definition 5 A family root lattice is one whose generator matrix, B, has columns each of whose greatest common divisor is 1.

Other members of the family are precisely those whose generator matrices are B′ = B diag(k_{1}, k_{2}, ..., k_{s}) with k_{i} integer. To determine to which family some integer lattice Λ′ belongs one takes its generator matrix B′ and calculates the greatest common divisors, h_{1}, h_{2}, ..., h_{s} of its columns. Then the matrix B = B′ diag(h_{1}^{−1}, h_{2}^{−1}, ..., h_{s}^{−1}) is a generator matrix of the family root lattice that generates the family to which Λ′ belongs.

We are interested in the relation between ρ(Λ) and ρ(Λ′).

We consider first the scaling of only one coordinate using a scaling factor (k_{1}, 1, ..., 1) with k_{1} > 1. As mentioned before, corresponding to every point x = (x_{1}, x_{2}, ..., x_{s}) of Λ is a point x′ = (x′_{1}, x′_{2}, ..., x′_{s}). Applying Definition 1, we find

ρ(x′) = k_{1}ρ(x) when x_{1} ≠ 0
ρ(x′) = ρ(x) when x_{1} = 0.

It follows from this and Definition 2 that

ρ(Λ) ≤ ρ(Λ′) ≤ k_{1}ρ(Λ).  (2.2)

The possibility of successive scaling in each coordinate in turn and the commutative property of the scaling operation, allows us to state the following theorem.

Theorem 6 Let Λ′ be a rectangularly scaled version of Λ obtained by using a scaling factor k = (k_{1}, k_{2}, ..., k_{s}) with each k_{i} ≥ 1. Then

N′ = k_{1}k_{2}...k_{s}N  (2.3)

and

ρ(Λ) ≤ ρ(Λ′) ≤ k_{1}k_{2}...k_{s}ρ(Λ).  (2.4)

We note that, under the hypotheses of this theorem, ρ(Λ′)/N′ cannot exceed ρ(Λ)/N. However, since

z(Λ) = \frac{ρ(Λ)(log N)^{s−2}}{N} ,  (2.5)

we see that if, in fact, ρ(Λ′)/N′ = ρ(Λ)/N, then the z-value of Λ′ is greater than the z-value of Λ; in this case, if Λ is a “good” lattice, then Λ′ is better. Because of this, the present authors decided to carry out scaling of lattices already known to be good lattices, to see whether we could discover some better lattices or “good” lattices of higher order.

In its simplest terms, the idea developed in this paper is to take a set of lattices that are known to be good, scale them in various ways and inspect the scaled lattices (which are generally of higher order) to see whether any of them are good. In some cases, if we are lucky, we may find that the value of z(Λ′) is close to or even exceeds the upper limit of those already known. In this very fortunate case the new lattice is relatively as good or even better than the original lattice and has a higher order.

The underlying philosophy of this approach is that a calculation of this sort, while nontrivial, is orders of magnitude shorter than for example a direct search to find ρ(N′). If in a minor proportion of the calculations, say one in a thousand, we find a good lattice, the whole calculation can be termed a success.

The organization of this search requires some care. One can find lattices with arbitrarily high indices ρ(Λ) by making N sufficiently large. To see this simply consider the scaled versions of the unit lattice Λ_{0}. The lattice Λ′ = kΛ_{0} (which can be obtained from Λ_{0} using k = (k, k, …, k)) has ρ(Λ) = k and N(Λ) = k^{s}.

In providing guidelines for the scope of the search, the following theorem is helpful.

Theorem 7 Under the hypothesis of the previous theorem,

ρ(Λ′) ≤ N(N′/N)^{1/s}.  (2.6)

Proof. All integer lattices of order N contain the sublattice NΛ_{0} (where Λ_{0} is the unit lattice). Thus Λ′ contains each of the points (k_{1}N, 0, 0, …, 0),(0, k_{2}N, 0, …, 0),… (0, 0, …, k_{s}N) and it follows that

ρ(Λ′) ≤ Nk_{i} i = 1, 2, …, s.  (2.7)

Since all k_{i} are positive integers, we may take the geometric mean of the s equations in (2.7) and using (2.3) obtain (2.6). □

In order to make the search finite, we choose a lower bound \overline{\overline{z}} (generally (2/3)\overline{z}_{s} of Section 4) and limit the search to lattices Λ′ for which z(Λ′) > \overline{\overline{z}}. ¿From the theorem we see that

z(Λ′) ≤ (N/N′)^{1−1/s} log^{s−2} N′  (2.8)

and so is bounded by a quantity that approaches zero with large N′. Thus, since N′ is restricted to integer multiples of N, the number of family members to be treated is finite. In fact, elementary manipulation yields the following lemma.

Lemma 8 z(Λ′) < \overline{\overline{z}} when

N′/ log^{s−1} N′ > N/\overline{\overline{z}}  (2.9)

and

\overline{\overline{z}} log N′ > 1.  (2.10)

In practice (2.10) is satisfied trivially and so we may restrict our search to values of N′ violating (2.9).

3 Scaling an Individual Lattice

In Sections 4, 5, and 6 we shall describe and analyze results obtained by scaling lists of lattices, all of which are reasonably good lattices. In this section we present a more detailed theory about rectangular scaling. The thrust of this section is to provide information, using which, ρ(Λ′) for a family of lattices may be readily calculated. Readers interested principally in the results of our numerical experiments may omit this section in a first reading. Without loss in generality we shall assume as before that the lattice Λ is a family root lattice (see Definition 5) and that Λ′ is a scaled version obtained using a scaling factor k, all of whose components are positive integers.

The behavior of ρ(Λ′) as a function of k is given by the function in (3.1) below.

Theorem 9 Under the hypotheses of the preceding theorems, there exist 2^{s} − 1 positive integers A, A_{1}, …, A_{23...s}, which depend only on Λ such that

\frac{ρ(Λ′)}{N′} = \frac{1}{N} min (A, \frac{A_{1}}{k_{1}} , \frac{A_{2}}{k_{2}} , \frac{A_{3}}{k_{3}} , ..., \frac{A_{12}}{k_{1}k_{2}} , \frac{A_{13}}{k_{1}k_{3}} , ..., \frac{A_{23}}{k_{2}k_{3}} , ...) .  (3.1)

Note that these denominators comprise all distinct products of up to s − 1 distinct components of k. There is no term in (k_{1}, k_{2}, …, k_{s})^{−1}.

Note also that (3.1), while containing many inequalities, actually defines a function of k. The rest of this section is devoted to establishing Theorem 9 and to showing how to calculate a set of constants A_{i,j,...} from a generator matrix B of Λ. It will appear that each coefficient A_{i,j,...} can be conveniently defined in terms of functions of the form ρ(S), where S is a specified set of points belonging to Λ_{0} and

ρ(S) = min_{x∈S;x≠0} ρ(x),  (3.2)

where ρ(x) as defined in Section 1 is the absolute value of the product of the nonzero components of x. This notation is a natural generalization of that introduced in Definition 2.

We now partition the elements of Λ into 2^{s} distinct sets. We distinguish these using an s-component binary index u = (u_{1}, u_{2}, …, u_{s}), that is, one in which each component is either 1 or 0.

Definition 10 Let Λ be an s-dimensional integer lattice and t an s-component binary index. Then

Γ^{(t)} = {x|x ∈ Λ and x_{i} = 0 when t_{i} = 0 and x_{i} ≠ 0 when t_{i} ≠ 0}.  (3.3)

Note that Γ^{(t)} is not a lattice (except technically for Γ^{(0,0,...,0)} which is the single point (0, 0, …, 0)). These 2^{s} distinct sets form a partition of Λ; that is,

Λ = ⋃ ; \begin{matrix}u_{i} = 0, 1 \\ 1 ≤ i ≤ s \end{matrix} Γ^{(u)}.  (3.4)

This partition has been constructed with the following property in view.

Lemma 11 When (x_{1}, x_{2}, …, x_{s}) ∈ Γ^{(u)},

ρ(k_{1}x_{1}, k_{2}x_{2}, …, k_{s}x_{s}) = k^{(u)}ρ(x_{1}, x_{2}, …, x_{s}),  (3.5)

where

k^{(u)} = k_{1}^{u_{1}}k_{2}^{u_{2}} … k_{s}^{u_{s}}  (3.6)

is the product of those components k_{i} of k for which u_{i} = 1.

Theorem 12 Under the hypotheses of Theorem 6,

ρ(Λ′) = min ; \begin{matrix}u_{i} = 0, 1 \\ 1 ≤ i ≤ s \\ u ≠ 0 \end{matrix} (k^{(u)}ρ(Γ^{(u)})),  (3.7)

these quantities being defined in (3.6), (3.2), and (3.3).

Proof. The theorem follows because

ρ(Λ′) = min ; \begin{matrix}x ∈ Λ \\ x ≠ 0 \end{matrix} ρ(k_{1}x_{1}, k_{2}x_{2}, …, k_{s}x_{s})

= min ; \begin{matrix}u_{i} = 0, 1 \\ 1 ≤ i ≤ s \\ u ≠ 0 \end{matrix} min_{x∈Γ^{(u)}} ρ(k_{1}x_{1}, k_{2}x_{2}, …, k_{s}x_{s}).  (3.8)

The first equality above follows from the definition of ρ and of the scaled lattice. The second follows from the partition (3.4) above. When we apply successively Lemma 11 and (3.2), we find that the expression on the right in (3.8) reduces to the right-hand side of (3.7). □

Theorem 9 may be obtained from this theorem by simply dividing by N′ = k_{1}k_{2} … k_{s}N and recognizing that, when u ≠ 0, the set Γ^{(u)} is not empty and ρ(Γ^{(u)}) is a positive integer.

One readily identifies

A_{i,j...} = ρ(Γ^{(u)}),  (3.9)

where u is the binary index that has zeros in positions corresponding to i, j …, the subscripts of A, and units elsewhere.

Since the point set Γ^{(u)} contains the point (u_{1}N, u_{2}N, …, u_{s}N), it follows that when u ≠ 0,

1 ≤ ρ(Γ^{(u)}) ≤ N^{u_{1}+u_{2}+...+u_{s}}  (3.10)

and (3.7) supports the 2^{s} − 1 inequalities

ρ(Λ′) ≤ (k_{1}N)^{u_{1}}(k_{2}N)^{u_{2}} … (k_{s}N)^{u_{s}}  u ≠ 0, u_{i} = 0, 1 i = 1, 2, …, s.  (3.11)

There is a somewhat unexpected reformulation of Theorem 12. We recall that the points of Γ^{(u)} of Definition 10 do not form a lattice. We may, however, form a lattice Λ^{(u)} from the points of Γ^{(u)} by adding all points of the form x ± y, where x, y ∈ Γ^{(u)}, and iterating. This turns out to be a (u_{1} + u_{2} + … + u_{s})-dimensional projection of Λ, defined by the following.

Definition 13 Let Λ be an s-dimensional lattice and t an s-component binary index. Then

Λ^{(t)} = {x|x ∈ Λ and x_{i} = 0 when t_{i} = 0}.  (3.12)

It follows quite simply that partition (3.4) of Λ induces a similar partition of Λ^{(t)}, namely,

Λ^{(t)} = ⋃ ; \begin{matrix}0 ≤ u_{i} ≤ t_{i} \\ 1 ≤ i ≤ s \end{matrix} Γ^{(u)}  (3.13)

from which it follows that

ρ(Λ^{(t)}) = min ; \begin{matrix}0 ≤ u_{i} ≤ t_{i} \\ 1 ≤ i ≤ s \\ u ≠ 0 \end{matrix} ρ(Γ^{(u)}).  (3.14)

Lemma 14 For a given s-dimensional lattice Λ and s-dimensional binary index t,

min ; \begin{matrix}0 ≤ u_{i} ≤ t_{i} \\ 1 ≤ i ≤ s \\ u ≠ 0 \end{matrix} k^{(u)}ρ(Γ^{(u)}) = min (k^{(t)}ρ(Λ^{(t)}), min ; \begin{matrix}0 ≤ u_{i} ≤ t_{i} \\ 1 ≤ i ≤ s \\ u ≠ t \\ u ≠ 0 \end{matrix} k^{(u)}ρ(Γ^{(u)})) ,  (3.15)

where Λ^{(t)}, Γ^{(u)} are defined in terms of Λ in Definitions 13 and 10, and ρ is defined in (3.2).

The reader will recognize that the two sides of Equation (3.15) differ only in that a single term has been changed.

Proof. To establish the lemma, we take the right-hand side of (3.15) and replace the cofactor of k^{(t)} by the expression given in (3.14). This procedure leaves us with an expression involving two somewhat similar sets of terms. By inspection we see that, except for the principal term in which u = t there are a pair of terms corresponding to each u, one of which has a factor k^{(t)} and the other k^{(u)}. In all cases k^{(u)} ≤ k^{(t)} and the first term can be discarded. Doing this leaves the expression on the left-hand side of (3.15) and so establishes the lemma. □

Theorem 15

ρ(Λ′) = min ; \begin{matrix}u_{i} = 0, 1 \\ 1 ≤ i ≤ s \\ u ≠ 0 \end{matrix} (k^{(u)}ρ(S^{(u)})),

where S stands for Γ or Λ and may be chosen variously in each of 2^{s} − 1 terms.

Proof. One may successively apply the lemma to the right-hand side of (3.7). Each application alters one Γ to S. The lemma must be applied in a proper order. Any ordering in which all terms having Σt_{i} = d are treated before any having Σt_{i} > d with d = 1, 2, …, s is suitable. □

Theorem 15 sets the stage for the calculation of ρ(Λ′) in the situation in which Λ is defined by a generator matrix B in utlf (Hermite Normal Form) and in which software is available to calculate ρ(Λ) for up to s-dimensional lattices from its B matrix. The problem is to identify a generator matrix of Λ^{(t)}.

Let B be in utlf and the binary index vector t = (0, 0, …, 0, 1, 1, …, 1) be a string of s − σ zeros followed by a string of σ ones with, of course, σ = ∑_{i=1}^{s} t_{i}. In this case it is almost self-evident that a generator matrix of Λ^{(t)} is obtained by replacing the first s − σ rows of B by zeros. Thus, ρ(Λ^{(t)}) may be obtained by applying the software to the σ-dimensional lattice whose generator is the σ × σ lower right-hand minor of B.

When t = (t_{1}, t_{2}, …, t_{s}) is not of that form, we exploit the circumstance that ρ is invariant under permutations of the coordinate system. Thus, let P be an s × s permutation matrix, and set t = P t, \overline{B} = BP, and let \overline{Λ} be the lattice whose generator matrix is \overline{B}. Then ρ(Λ^{(t)}) = ρ(\overline{Λ}^{(t)}). Thus, one finds the permutation P which takes t into t′ of form (0, 0, 0, 1, …, 1), applies it to the columns of B to obtain \overline{B}, and then puts \overline{B} in utlf. This problem is now reduced to the one described in the preceding paragraph.

In our numerical calculations, in pilot schemes we calculated each ρ(Λ′) individually using our own software. However, applying the results of the previous two paragraphs led to a much faster code. For each root lattice Λ we calculated 2^{s} − 1 constants required in (3.1). This involved calculating only one s-dimensional figure of merit A = ρ(Λ), the other constants A_{i,j,...} being lower-dimensional figures of merit. Then we relied on (3.1) to calculate z(Λ′) for all lattices Λ′ in which we were interested. These included at most those with N′ violating (2.9).

4 The Highlight Lists

Applying the technique of Section 3, we have found apparently endless lists of lattices, hundreds of which are excellent or interesting by previously acceptable standards. In order not to overwhelm the reader, we are presenting our results in two parts. In this section we present two “highlight” lists. These include three- and four-dimensional lattices with exceptionally high z-values and also lattices with moderate z-values but exceptionally high values of N.

In Section 5 we shall give in more detail some of the actual results and explain precisely how they were obtained; then in Section 6 we shall comment on some aspects of these results.

To provide criteria for our lists, we have defined an s-dimensional benchmark lattice as follows:

Definition 16 The s-dimensional lattice \overline{Λ}_{s} of order 2^{s+1} whose generator matrix in utlf is

B(\overline{Λ}_{s}) = ( \begin{matrix}2 & 0 & ... & 0 & 2 \\ 0 & 2 & ... & 0 & 2 \\ ⋮ & ⋮ & & ⋮ & ⋮ \\ 0 & 0 & ... & 2 & 2 \\ 0 & 0 & ... & 0 & 4 \end{matrix} )  (4.1)

is termed the s-dimensional benchmark lattice.

Clearly, ρ(\overline{Λ}_{s}) = 4 and

\overline{z}_{s} = z(\overline{Λ}_{s}) = \frac{1}{2} (\frac{(s + 1) log 2}{2})^{(s−2)} .  (4.2)

The authors have introduced this benchmark simply because it is convenient in the context of discussing our lists of lattice rules. No intrinsic mathematical property is implied or conjectured.

The highlight lists include:

1. all s-dimensional lattices Λ known to us having z(Λ) ≥ \overline{z}_{s}, and

2. All s-dimensional lattices Λ known to us satisfying both

• z(Λ) > 2/3\overline{z}_{s} and

• z(Λ) > z(Λ̃) for all Λ̃ known to us whose order, Ñ, exceeds N, the order of Λ.

Tables 1–8 and A1 and A2 contain lists of lattices. Each line corresponds to a single lattice Λ. The s(s+1)/2 entries which follow N and ρ are elements of an upper triangular matrix B. This is the upper triangular lattice form or Hermite Normal form of any generator matrix of Λ (see the remarks at the end of Section 1). Then comes the rank of the corresponding lattice rule. (See [SL89] for a full discussion of rank.) In this column an entry 0 indicates rank 1 simple (see [LS92]), and an entry 1 indicates rank 1 not simple.

In Tables 1 and 2, we identify the list from which this lattice was taken. These lists are specified in Section 5; the abbreviations are B = Blue, G = Green, SG = Scaled Green, and SB = Scaled Blue.

The authors must emphasize that these are lists of lattices that happen to be known to us at this time. In Section 6 we shall discuss the question of how many other lattices there may be that belong on such a list but have not been encountered yet. Only for N < \overline{N} (= 4000 for s = 3 and 600 for s = 4) are these lists complete.

It is of interest to note the extremely disparate values of N involved. ¿From complete lists of optimal lattices of order up to \overline{N}, we obtain excellent lattices of order up to say 5\overline{N}, a few of these being better than any found previously. After this the list degrades in quality only slowly, containing lattices of good (but not top) quality up to order 50\overline{N}.

The tail of the list is unlikely to include any optimal lattices at all. However, for these extraordinarily high orders, an example of a lattice of moderate quality is of some interest.

Undoubtedly, the most outstanding lattices on these lists are

(i) a three-dimensional lattice having N = 9760, ρ = 864, and z = 0.81319, and (ii) a four-dimensional lattice having N = 8992, ρ = 212, and z = 1.95413.

The results of scaling the short list [BP85] of five-dimensional rank 1 simple lattices were relatively unexciting. Possible reasons for this are mentioned in Section 5. We found no lattices whose z-values exceeded \overline{z}_{5}, and only 25 whose z-values exceeded 2/3 \overline{z}_{5}. We have listed in Table 8 all the lattices known to us whose z-values exceed 2/3 \overline{z}_{5}.

Table 1. A Highlight List of Three-Dimensional Lattices

N  ρ b_{11} b_{12} b_{13} b_{22} b_{23}  b_{33} rank  z  source
16  4 2 0  2 2  2  4 3 0.69315  G
1672 160 2 0 90 2 130 418 3 0.71022  G
2352 216 2 0 111 2 171 588 2 0.71293  G
3069 270 1 1 464 3 168 1023 2 0.70637  G
4704 390 2 0 228 3 148 784 2 0.70109 SG,SB
4880 432 1 0 638 2 1002 2440 2 0.75183 SG,SB
4900 400 1 0 452 2 748 2450 2 0.69363 SG
8922 700 1 0 823 2 1362 4461 1 0.71367 SB
9760 864 2 0 638 2 1002 2440 3 0.81319 SG,SB
9800 800 2 0 452 2 748 2450 3 0.75022 SG
17844 1356 1 0 2656 2 4062 8922 2 0.74392 SB
19416 1404 1 0 1431 2 3540 9708 2 0.71399 SG
20008 1440 2 0 1314 2 2048 5002 3 0.71279 SG
45576 2968 2 0 1658 2 4192 11394 3 0.69857 SB
48264 2864 2 0 1820 3 1184 8044 2 0.63995 SG
67410 3822 2 0 2469 3 1548 11235 2 0.63040 SG
67527 3762 3 0 1971 3 3072 7503 3 0.61952 SG
68238 3678 2 0 3441 3 5328 11373 2 0.59994 SG
90984 4680 2 0 5368 3 3680 15164 2 0.58734 SG
109050 5310 2 0 7940 3 3080 18175 1 0.56482 SG
130860 5808 2 0 9528 3 3696 21810 2 0.52292 SG
153819 6678 3 0 2487 3 6288 17091 3 0.51852 SB
160064 6688 4 0 2628 4 4096 10004 3 0.50070 SG
179760 7424 3 0 3292 4 2064 14980 2 0.49970 SG
227460 8880 3 0 6710 4 4600 18955 1 0.48155 SG

Table 2. A Highlight List of Four-Dimensional Lattices

N  ρ b_{11} b_{12} b_{13}  b_{14} b_{22} b_{23}  b_{24} b_{33}  b_{34}  b_{44} rank  z
32  4  2  0  0  2  2  0  2  2  2  4  4  1.50142  G
928  32  2  0  0  34  2  0  44  2  52  116  4  1.61001  SG
992  32  2  0  0  20  2  0  46  2  54  124  4  1.53568  SG
1008  32  2  0  0  16  2  2  8  6  12  42  4  1.51832  SG
1008  32  2  0  0  16  2  2  8  6  30  42  4  1.51832  SG
1354  40  1  0  0  492  1  0  550  1  658  1354  0  1.53607  B
1748  48  1  0  0  286  1  0  360  1  472  1748  0  1.53074  B
2097  54  1  0  0  435  1  0  936  1 1035  2097  0  1.50633  B
2112  55  1  0  0  100  1  0  162  1  830  2112  0  1.52617  B
2215  60  1  0  0  257  1  0  448  1  558  2215  0  1.60730  B
2248  60  1  0  0  106  1  0  178  2  442  1124  2  1.58980  SG
2320  64  2  0  0  34  2  0  56  2  82  290  4  1.65661  SG
2477  63  1  0  0  128  1  0  701  1  915  2477  0  1.55328  B
2570  65  1  0  0  787  1  0 1138  1 1246  2570  0  1.55921  B
2686  66  1  0  0  852  1  0 1142  1 1218  2686  0  1.53190  B
2730  68  1  0  0  170  1  0  452  1 1328  2730  0  1.55928  B
2836  72  1  0  0  418  1  0 1010  1 1290  2836  0  1.60464  B
3298  84  1  0  0  535  1  0  701  1  937  3298  0  1.67153  B
4496  106  1  0  0  106  2  0  178  2  442  1124  3  1.66790 SG,SB
8992  212  2  0  0  106  2  0  178  2  442  1124  4  1.95413 SG,SB
9908  180  1  0  0  256  1  0 1402  2 1830  4954  2  1.53803  SB
20232  318  2  0  0  159  2  0  267  3  663  1686  2  1.54517 SG,SB
52768  672  2  0  0 1070  2  0 1402  2 1874  6596  4  1.50574  SB
267138 2268  3  0  0 1605  3  0 2103  3 2811  9894  4  1.32561  SB
474912 3024  3  0  0 2140  3  0 3748  4 2804 13192  2  1.08787  SB

5 Lists of Scaled Lattices

In the preceding section we presented two short lists that included the best lattices we have found so far. These were extracted from results that we outline in detail in this section. This is in order that subsequent workers can relate their investigation to ours for purposes that may include confirming or extending our work.

All our work involves taking a list of lattices and treating each member of the list in the way described in Section 3. We now describe the seven different lists that were used as input. The three blue lists (containing only rank 1 simple lattices) have been available in the literature for several years. The two red lists have appeared in the literature only very recently. The two green lists have not been published. Each list is in a format corresponding to that used in Table 1.

1. Three Dimensions

• Green list N ∈ [16, 4000]; contains 6557 entries. These are all the lattices in this range for which ρ(Λ) = ρ_{3}(N). This list is unpublished.

• Red list N ∈ [16, 3916]; contains 68 entries. This is a subset of the green list above, containing entries for N if and only if ρ_{3}(N) > ρ(M) for all M < N. This list is published in [LS91]

• Blue list N ∈ [21, 6066]; contains 101 entries. This is a concatenation of lists published by Maisonneuve [Mai72] and Kedem and Zaremba [KZ74]. It contains only rank-1 simple lattices, assembled from this subclass, using the standard red list convention described above.

2. Four Dimensions

• Green list As above; N ∈ [20, 600]; contains 16127 entries, but is not complete. It contains most lattices for which ρ(Λ) = ρ_{4}(N). If there exist more than ten lattices Λ for a single value of N, some may be missing but at least ten are included. This list is unpublished.

• Red list As above; N ∈ [32, 562]; contains 23 entries. this list is published in [LS92].

• Blue list As above; N ∈ [52, 3298]; contains 47 entries. This is a concatenation of lists published by Maisonneuve [Mai72] and Bourdeau and Pitre [BP85].

3. Five Dimensions

• Blue list N ∈ [112, 772]; contains 9 entries. This list is published in [BP85]. Seven of these are repeated in the first part of Table 8.

Each of these seven lists were processed in the same way. This process produced from the input list, three more lists. These are specified below in the case that the input list is the three-dimensional green list.

1. We form first a three-dimensional raw scaled green list. For this, we require \overline{\overline{z}}, a cut-off value specified in (5.1) below. This list contains each lattice with z(Λ) ≥ \overline{\overline{z}} obtained by scaling every member of the green list. This huge list includes duplicate entries, and for some values of N, entries with different rho values.

2. From this, by cutting out all duplicates entries and any entries for which there is another lattice of the same order with a higher value of ρ, we produce a green scaled green list. We have retained this list in our files.

3. Next we use the standard procedure to produce a red scaled green list. This, as usual, retains only lattices on the green scaled green list for which ρ(Λ) > ρ(Λ̃) for all Λ̃ on that list having Ñ < N. This list is given in Table 5.

The cut-off values we used were

\overline{\overline{z}} = (2/3)\overline{\overline{z}}_{3} ≃ 0.46
\overline{\overline{z}} = (2/3)\overline{\overline{z}}_{4} ≃ 1.00  (5.1)
\overline{\overline{z}} = (5/9)\overline{\overline{z}}_{5} ≃ 2.50

in 3, 4, and 5 dimensions, respectively. Table 3 gives some information on the length and the scope of the lists in this section.

Table 3. Length and Scope of Lists Involved

Kind of list  Input lists  Green scaled lists  Red scaled lists
Dim. Type  Length N_{min} N_{max} Length N_{min} N_{max} Length Table
Blue  101  21  6066  177  4044 153819  29  4
3-d Green  6557  16  4000  4910  4002 227460  80  5
Red  68  16  3916  42  4032  31328  17  A1
Blue  46  52  3298  162  624 474912  47  6
4-d Green  16127  20  600  4750  602 365625  55  7
Red  23  32  562  51  640  80928  25  A2
5-d^{1} Blue  7  112  772  117  112  15768  17

1See remarks at end of Section 4. We note that, when the input is a green or a red list of lattices with N ∈ [N_{min}, \overline{N}], there is no need to remain scaled lattices having N ≤ \overline{N} because these lattices, or better ones having the same N′ are available by definition on the input list. This is not the case when the input is a blue list. The input blue list comprises excellent lattices, all of which are rank 1 simple. One may well find an interesting lattice of higher rank having N′ ≥ N but N′ < \overline{N}. Tables 4 and 6 (in which \overline{N} = 6066 and 3298, respectively) contain a handful of such lattices. These are generally of technical interest only. By including them we specify precisely the effect of scaling a blue list.

Table 4. Red Scaled Blue List in Three Dimensions

N  ρ b_{11} b_{12}  b_{13} b_{22}  b_{23}  b_{33} rank  z
4108  270  1  0  556  1 1408  4108  0  0.546880
4142  312  1  0  966  1 1422  4142  0  0.627380
4358  336  1  0 1398  1 1998  4358  0  0.646080
4704  390  2  0  228  3  148  784  2  0.701090
4880  432  1  0  638  2 1002  2440  2  0.751830
5862  450  1  0  538  1 1902  5862  0  0.666040
6066  460  1  0  600  1 1581  6066  0  0.660540
7430  544  1  0 1039  2 1425  3715  1  0.652600
7664  552  1  0 1194  2 1600  3832  2  0.644210
7698  576  1  0  603  2 1701  3849  1  0.669580
7734  588  1  0  600  1 2019  7734  0  0.680710
8922  700  1  0  823  2 1362  4461  1  0.713670
9760  864  2  0  638  2 1002  2440  3  0.813190
14112  908  2  0  454  2  746  3528  3  0.614780
15328  958  2  0  728  2 1778  3832  3  0.602340
15396 1032  2  0  603  2 1701  3849  2  0.646300
17436 1040  1  0 2094  2 1299  8718  1  0.582530
1  0 1299  2 2094  8718  2  0.582530
17844 1356  1  0 2656  2 4062  8922  2  0.743920
22788 1484  1  0 1658  2 4192 11394  2  0.653430
26766 1646  1  0 2656  3 4062  8922  2  0.626940
31008 1680  2  0 2190  2 3664  7752  3  0.560330
32940 2016  3  0  957  3 1503  3660  3  0.636650
34872 2080  2  0 1299  2 2094  8718  2  0.623870
45576 2968  2  0 1658  2 4192 11394  3  0.698570
69282 3042  3  0 1206  3 3402  7698  3  0.489390
69744 3120  2  0 1732  3 2792 11624  2  0.498910
78080 3584  4  0 1276  4 2004  4880  3  0.517100
102546 4452  2  0 2487  3 6288 17091  2  0.500920
153819 6678  3  0 2487  3 6288 17091  3  0.518520

Table 5. Red Scaled Green List in Three Dimensions

N  ρ b_{11} b_{12} b_{13} b_{22} b_{23} b_{33} rank  z
4002 280 1 0 958 1 1258 4002 0 0.580330
4008 288 2 0 219 2 294 1002 2 0.596120
4044 308 1 0 400 1 1054 4044 0 0.632530
4050 312 1 3 178 9 410 450 1 0.639910
4185 324 3 0 108 3 168 465 3 0.645620
4358 336 1 0 1398 1 1998 4358 0 0.646080
4528 344 2 0 218 2 316 1132 3 0.639530
4580 348 1 0 348 1 2002 4580 0 0.640490
4588 360 1 0 808 2 588 2294 2 0.661560
4704 390 2 0 228 3 148 784 2 0.701090
4880 432 1 0 638 2 1002 2440 2 0.751830
5862 450 1 0 538 1 1902 5862 0 0.666040
6066 460 1 0 600 1 1581 6066 0 0.660540
6198 468 1 0 1203 2 1470 3099 1 0.659340
1 0 864 2 234 3099 1 0.659340
6322 480 1 0 800 1 2998 6322 0 0.664480
6682 504 1 0 1808 1 2624 6682 0 0.664290
6976 506 1 0 1644 1 3034 6976 0 0.641950
7116 510 1 0 1606 1 2120 7116 0 0.635720
7184 560 1 2 586 4 1544 1796 2 0.692170
7544 572 2 0 336 2 582 1886 3 0.676980
7698 576 1 0 603 2 1701 3849 1 0.669580
7734 588 1 0 600 1 2019 7734 0 0.680710
8391 598 1 0 1635 1 3849 8391 0 0.643890
8628 630 1 0 792 1 3363 8628 0 0.661750
8836 660 1 0 942 2 2126 4418 2 0.678720
9297 702 1 0 864 3 234 3099 2 0.689950
9760 864 2 0 638 2 1002 2440 3 0.813190
12944 936 1 0 954 2 2360 6472 2 0.684670
13524 940 1 0 2488 2 984 6762 2 0.661160
14068 948 1 0 1880 2 800 7034 2 0.643660
14260 980 1 0 996 2 2440 7130 2 0.657360
14820 1032 1 0 1702 2 2650 7410 2 0.668760
15420 1080 1 0 2002 2 3050 7710 2 0.675410
16914 1120 1 0 2973 2 1755 8457 1 0.644690
16926 1152 1 0 1712 3 644 5642 1 0.662680
18372 1160 2 0 1713 2 2049 4593 2 0.619940
18882 1224 2 0 669 3 1449 3147 2 0.638250
19194 1260 1 0 1839 2 1161 9597 1 0.647420
19416 1404 1 0 1431 2 3540 9708 2 0.713990

N  ρ b_{11} b_{12} b_{13} b_{22} b_{23}  b_{33} rank  z
20008 1440 2 0 1314 2 2048 5002 3 0.712790
21810 1470 1 0 4764 2 1848 10905 1 0.673340
22980 1512 1 0 4266 2 771 11490 1 0.660750
24132 1584 2 0 888 2 1365 6033 2 0.662380
25888 1618 1 0 1908 2 4720 12944 2 0.635100
27048 1764 2 0 984 2 2488 6762 3 0.665570
29080 1936 1 0 6352 2 2464 14540 2 0.684240
32176 1992 2 0 1184 2 1820 8044 3 0.642560
32940 2016 3 0 957 3 1503 3660 3 0.636650
33075 2034 3 0 678 3 1122 3675 3 0.639970
34758 2052 2 0 1101 3 2688 5793 2 0.617300
35868 2136 2 0 1167 2 4131 8967 2 0.624550
36198 2148 2 0 1365 3 888 6033 2 0.622880
38388 2232 2 0 1161 2 1839 9597 2 0.613730
39348 2418 2 0 2220 2 2931 9837 2 0.650170
42064 2448 2 0 2164 2 4876 10516 3 0.619620
44940 2548 2 0 1548 2 2469 11235 2 0.607410
2 0 2112 2 3249 11235 2 0.607410
45492 2664 2 0 2760 2 4026 11373 2 0.628070
48264 2864 2 0 1820 3 1184 8044 2 0.639950
54525 2904 1 0 7940 3 3080 18175 1 0.580880
57582 3006 2 0 1839 3 1161 9597 2 0.572200
60656 3120 2 0 3680 2 5368 15164 3 0.566480
60858 3180 2 0 3732 3 1476 10143 2 0.575630
65430 3186 2 0 4044 3 1788 10905 2 0.539950
67410 3822 2 0 2469 3 1548 11235 2 0.630400
76776 4008 2 0 2452 3 1548 12796 2 0.587220
87240 4248 2 0 6352 3 2464 14540 2 0.553950
90495 4440 3 0 1480 3 2275 10055 2 0.559960
90984 4680 2 0 5368 3 3680 15164 2 0.587340
109050 5310 2 0 7940 3 3080 18175 1 0.564820
120660 5370 3 0 2275 4 1480 10055 1 0.520740
130860 5808 2 0 9528 3 3696 21810 2 0.522920
144792 5976 3 0 2730 4 1776 12066 2 0.490450
151640 6130 2 0 6710 4 4600 18955 2 0.482240
160064 6688 4 0 2628 4 4096 10004 3 0.500700
174480 7104 2 0 9528 4 3696 21810 3 0.491420
179760 7424 3 0 3292 4 2064 14980 2 0.499700
191940 7440 3 0 3065 4 1935 15995 1 0.471540
227460 8880 3 0 6710 4 4600 18955 1 0.481550

Table 6. Red Scaled Blue List in Four Dimensions

N  ρ  b_{11} b_{12} b_{13}  b_{14} b_{22} b_{23}  b_{24} b_{33}  b_{34}  b_{44} rank  z
624  16  2  0  0  12  2  0  21  2  27  78  3  1.06215
2  0  0  9  2  0  15  2  36  78  3  1.06215
708  18  1  0  0  27  2  0  60  2  78  177  2  1.09489
718  22  1  0  0  158  1  0  210  1  234  718  0  1.32521
732  24  1  0  0  248  1  0  294  1  324  732  0  1.42637
932  26  1  0  0  116  1  0  288  1  314  932  0  1.30416
1124  30  1  0  0  106  1  0  178  1  442  1124  0  1.31706
1234  36  1  0  0  170  1  0  306  1  404  1234  0  1.47811
1354  40  1  0  0  492  1  0  550  1  658  1354  0  1.53607
1748  48  1  0  0  286  1  0  360  1  472  1748  0  1.53074
1990  50  1  0  0  256  1  0  584  1  684  1990  0  1.44969
2052  51  1  0  0  184  1  0  282  1  598  2052  0  1.44561
2097  54  1  0  0  435  1  0  936  1 1035  2097  0  1.50633
2112  55  1  0  0  100  1  0  162  1  830  2112  0  1.52617
2248  60  1  0  0  106  1  0  178  2  442  1124  2  1.58980
2686  66  1  0  0  852  1  0 1142  1 1218  2686  0  1.53190
2730  68  1  0  0  170  1  0  452  1 1328  2730  0  1.55928
2836  72  1  0  0  418  1  0 1010  1 1290  2836  0  1.60464
4496  106  1  0  0  106  2  0  178  2  442  1124  3  1.66790
5672  108  1  0  0  194  1  0  718  2  994  2836  2  1.42248
6744  120  1  0  0  159  2  0  267  2  663  1686  2  1.38308
8448  126  1  0  0  830  2  0  100  2  162  2112  3  1.21931
8508  144  1  0  0  627  1  0 1935  2 1515  4254  1  1.38584
8992  212  2  0  0  106  2  0  178  2  442  1124  4  1.95413
16116  218  1  0  0 1278  2  0 1713  2 1827  4029  2  1.26949
20232  318  2  0  0  159  2  0  267  3  663  1686  2  1.54517
26384  336  1  0  0  614  2  0 1402  2 1874  6596  3  1.31989
1  0  0 1070  2  0 1402  2 1874  6596  3  1.31989
32232  432  2  0  0 1278  2  0 1713  2 1827  4029  3  1.44428
42976  436  2  0  0 1704  2  0 2284  2 2436  5372  4  1.15467
43821  468  3  0  0  156  3  0  228  3  495  1623  4  1.21996
45522  477  3  0  0  159  3  0  267  3  663  1686  4  1.20550
48348  480  2  0  0 1035  2  0 1281  3  882  4029  2  1.15504
2  0  0  375  2  0 1257  3  585  4029  2  1.15504
52768  672  2  0  0  614  2  0 1402  2 1874  6596  4  1.50574
89046  756  1  0  0 1605  3  0 2103  3 2811  9894  3  1.10276
1  0  0  79  3  0 2103  3 2811  9894  3  1.10276
108783 972  3  0  0  327  3  0  558  3 1386  4029  4  1.20172
118728 1008  2  0  0  79  2  0 2103  3 2811  9894  2  1.15914
2  0  0 1605  2  0 2103  3 2811  9894  2  1.15914
2  0  0 1605  2  0 2811  3 2103  9894  2  1.15914
145044 1080  3  0  0 1176  3  0 1380  3 1708  5372  3  1.05174
178092 1512  2  0  0 1605  3  0 2103  3 2811  9894  3  1.24098
2  0  0  79  3  0 2103  3 2811  9894  3  1.24098
257856 1728  3  0  0  744  4  0  436  4 1848  5372  3  1.04043
267138 2268  3  0  0  79  3  0 2103  3 2811  9894  3  1.32561
474912 3024  3  0  0 2140  3  0 3748  4 2804 13192  2  1.08787

Table 7. Red Scaled Green List in Four Dimensions

N  ρ  b_{11} b_{12} b_{13} b_{14} b_{22} b_{23} b_{24} b_{33}  b_{34}  b_{44} rank  z
676  22  1  0  0  50  1  0 158  2  34  338  2  1.38186
1  0  0  54  1  0 128  2  12  338  2  1.38186
688  24  1  0  0 106  1  0 144  2  22  344  2  1.48920
900  25  1  0  4  9  1  6  25 30  0  30  2  1.28535
928  32  2  0  0  34  2  0  44  2  52  116  4  1.61001
1281  34  1  0  0  54  1  0 129  3  98  427  1  1.35893
1344  36  1  0  0  45  2  0  99  2  162  336  2  1.38989
1556  40  1  0  0  84  1  0 218  2  244  778  2  1.38871
1692  42  1  0  0  96  1  0 412  2  134  846  2  1.37169
1952  48  2  0  0  24  2  0  42  2  56  244  4  1.41160
2  0  0  24  2  0  40  2  92  244  4  1.41160
2200  50  1  0  2  28  2  2  94 10  20  110  3  1.34617
2248  60  1  0  0 106  1  0 178  2  442 1124  2  1.58980
2320  64  2  0  0  34  2  0  56  2  82  290  4  1.65661
3132  72  2  0  0  51  3  0  66  3  78  174  3  1.48950
4080  80  2  0  0  40  2  0  62  2  154  510  4  1.35530
2  0  0  40  2  0  62  2  134  510  4  1.35530
4496  106  1  0  0 106  2  0 178  2  442 1124  3  1.66790
6192  108  2  0  0 196  2  0 234  3  168  516  3  1.32960
6736  120  2  0  0  62  2  0 206  2  294  842  4  1.38435
7312  128  2  0  0 218  2  0 340  2  414  914  4  1.38576
7888  144  2  0  0 172  2  0 314  2  382  986  4  1.46987
8992  212  2  0  0 106  2  0 178  2  442 1124  4  1.95413
14112  216  2  0  0 174  2  0 284  3  510 1176  3  1.39735
18816  224  2  0  0 174  2  0 284  4  510 1176  4  1.15326
19632  252  2  0  0 616  2  0 684  3  180 1636  3  1.25424
20232  318  2  0  0 159  2  0 267  3  663 1686  2  1.54517
26622  324  2  0  0 258  3  0 471  3  573 1479  3  1.26360
31590  360  2  0  0 327  3  0 483  3  543 1755  3  1.22327
37017  432  3  0  0 327  3  0 510  3  621 1371  4  1.29135
39933  486  3  0  0 258  3  0 471  3  573 1479  4  1.36616
47385  540  3  0  0 327  3  0 483  3  543 1755  4  1.32089
65808  576  3  0  0 680  3  0 828  4  436 1828  2  1.07736
3  0  0 436  3  0 680  4  828 1828  2  1.07736
70992  648  3  0  0 344  3  0 628  4  764 1972  2  1.13893
3  0  0 628  3  0 764  4  344 1972  2  1.13893
81360  720  3  0  0 632  3  0 916  4  392 2260  2  1.13133
87744  768  3  0  0 436  4  0 680  4  828 1828  3  1.13395
94656  792  3  0  0 344  4  0 628  4  764 1972  3  1.09849
108480 864  3  0  0 392  4  0 472  4 1056 2260  3  1.07067
3  0  0 392  4  0 632  4  916 2260  3  1.07067
112320 960  3  0  0 436  4  0 644  4  724 2340  3  1.15586
116992 1024  4  0  0 436  4  0 680  4  828 1828  4  1.19200
126208 1056  4  0  0 344  4  0 628  4  764 1972  4  1.15434
144640 1152  4  0  0 392  4  0 472  4 1056 2260  4  1.12446
149760 1280  4  0  0 436  4  0 644  4  724 2340  4  1.21376
219375 1500  3  0  0 545  5  0 805  5  905 2925  3  1.03422
228500 1600  4  0  0 545  5  0 850  5 1035 2285  3  1.06614
285625 2000  5  0  0 545  5  0 850  5 1035 2285  4  1.10505
365625 2500  5  0  0 545  5  0 805  5  905 2925  4  1.12191

Table 8. Five-dimensional Lattices having z(Λ) > 3.0

Rank 1 simple lattices in this list having N ∈ [112, 772] have been taken from [BP85]. The others are scaled versions of these or of the benchmark lattice.

N  ρ b_{11} b_{12} b_{13} b_{14} b_{15} b_{22} b_{23} b_{24} b_{25} b_{33} b_{34} b_{35} b_{44} b_{45}  b_{55} rank  z
64  4  2  0  0  0  2  2  0  0  2  2  0  2  2  2  4  5  4.49583
96  4  2  0  0  0  3  2  0  0  3  2  0  3  2  3  6  4  3.96210
128  4  2  0  0  0  4  2  0  0  4  2  0  4  2  4  8  5  3.56961
1  0  0  0  12  1  0  0  22  1  0  48  1  52  128  0  3.56961
144  4  2  0  0  0  3  2  0  0  3  2  0  3  3  3  96  3  3.40971
160  4  2  0  0  0  5  2  0  0  5  2  0  5  2  5  10  4  3.26808
192  4  2  0  0  0  4  2  0  0  4  2  0  4  3  4  8  4  3.02758
2  0  0  0  6  2  0  0  6  2  0  6  2  6  12  5  3.02758
1  0  0  0  18  1  0  0  33  1  0  72  1  78  192  0  3.02758
275  5  1  0  0  0  31  1  0  0  71  1  0  91  1 136  275  0  3.22179
308  6  1  0  0  0  18  1  0  0  62  1  0  70  1 102  308  0  3.66511
438  8  1  0  0  0  38  1  0  0  50  1  0  96  1 168  438  0  4.10962
448  6  1  0  0  0  12  1  0  0  54  2  0  22  2  28  112  3  3.04710
1  0  0  0  22  1  0  0  54  2  0  12  2  28  112  3  3.04710
512  8  1  0  0  0  22  1  0  0  48  2  0  12  2  52  128  3  3.79336
657  8  1  0  0  0  57  1  0  0  75  1  0 144  1 252  657  0  3.32502
666  9  1  0  0  0  15  1  0  0  42  1  0 175  1 269  666  0  3.71336
1  0  0  0  57  1  0  0 137  1  0 223  1 240  666  0  3.71336
1  0  0  0  57  1  0  0 221  1  0 240  1 307  666  0  3.71336
768  8  1  0  0  0  22  1  0  0  48  2  0  12  3  52  128  2  3.05476
1  0  0  0  22  1  0  0  48  2  0  52  3  12  128  2  3.05476
1  0  0  0  33  1  0  0  72  2  0  18  2  78  192  3  3.05476
772 10  1  0  0  0 154  1  0  0 170  1  0 230  1 256  772  0  3.80758
924  9  1  0  0  0  93  1  0  0 105  1  0 153  2  27  462  0  3.10161
1158 10  1  0  0  0 231  1  0  0 255  1  0 345  1 384 1158  0  3.03166
1536 12  1  0  0  0  33  2  0  0  18  2  0  72  2  78  192  4  3.08556
1544 12  1  0  0  0  78  1  0  0 264  1  0 378  2  10  772  2  3.07610
2048 16  2  0  0  0  12  2  0  0  22  2  0  48  2  52  128  5  3.46294
1  0  0  0  44  2  0  0  24  2  0  96  2 104  256  4  3.46294
2560 16  1  0  0  0  55  2  0  0  30  2  0 120  2 130  320  4  3.02077
2664 18  1  0  0  0 442  1  0  0 480  1  0 614  2 114 1332  2  3.31566
3088 20  1  0  0  0  78  1  0  0 378  2  0  10  2 264  772  3  3.36013
4632 24  1  0  0  0 117  1  0  0 567  2  0  15  2 396 1158  2  3.11591
7008 32  2  0  0  0  16  2  0  0  70  2  0 144  2 186  438  5  3.17025

6 Comments about Lists

6.1 Evaluation of Scaled Lists

An immediate question that comes to mind is to what extent any list obtained here compares with the corresponding complete list. The authors believe that, at best, one retains about 70% of a complete list, and that this percentage diminishes to zero as the order N significantly exceeds the order \overline{N} of the input list. The rest of this subsection is devoted to this question.

We carried out some numerical experiments in an environment in which the answer, in the form of a complete red list, is available. We applied our scaling technique to only part of our three-dimensional green list, the first part having N ≤ \overline{N} = 250. This produced first a long repetitive raw scaled green list and after massaging, as described in Section 5, a green scaled green list containing 450 lattices sharing 326 distinct values of N lying in [251,13376]. Since we have available a complete green list for N ∈ [1, 4000], we were able to observe the quality of this particular green scaled green list.

Table 9. The Three-Dimensional Green Scaled Green List with \overline{N} = 250

N-values for which

Scaled Distinct  ρ_{L}(N)/ρ_{3}(N)
Interval  Lattices N-values =1 ϵ(1, 0.9) ≤ 0.9
N ∈ [251, 500]  209  1112 94  15  3
N ∈ [501, 1000]  120  100 56  32  12
N ∈ [1001, 2000]  75  69 19  27  23
N ∈ [2001, 4000]  31  30 4  2  24
N > 4000  15  15  ?  ?  ?
Total  450  326 173  76  62

Table 9 gives a breakdown of the distribution of lattices in this list and their quality. Here ρ_{L}(N) is the lower bound on ρ_{3}(N) based only on the lattices in this list. Examination of this table shows that for values of N near to \overline{N}, we seem to be obtaining lattices for about half the values of N. Of these, 80% are optimal, the rest being generally of reasonably high quality. On the other hand, for values of N exceeding 8\overline{N} in a range containing 2000 values of N, we have found lattices for only 30 of these values, and only four of these are optimal. Fourteen of these 450 lattices may also be found on the three-dimensional red list which has 45 entries for N ∈ [251, 4000].

A second numerical experiment concerns a scaled three-dimensional red list. We compare a plot of ρ_{3}(N) based on a scaled red list with a similar plot based on the complete red list. We consider five such plots. For the complete red list we define a piecewise constant function

ρ̃(N) = max ; \begin{matrix}Λ ∈ L_{3}(M) \\ M ≤ N \end{matrix} ρ(Λ)  (6.1)

The discontinuities of ρ̃(N) occur at values of N appearing on the red list. At such values, ρ̃(N − 1) < ρ̃(N). One can define the analogous function for a red scaled list based on an input green list for N ∈ [1, N_{i}], where N_{i} = 125.2^{i}.

We have constructed four functions ρ̃_{i}(N) i = 1, 2, 3, 4. In general, ρ̃_{i}(N) ≤ ρ̃(N), but for some values of N this is an equality. We list in Table 10 the percentage of values of N in an interval (N_{j}, N_{j+1}] j = 1, 2, 3, 4 for which ρ̃_{i}(N) = ρ_{3}(N).

Naturally, when j < i, this is 100%, and when j >> i, this reduces to zero.

Table 10. Information about Red Scaled Green Lists

% of N satisfying (N_{1}, N_{2}] (N_{2}, N_{3}] (N_{3}, N_{4}] (N_{4}, N_{5}]
ρ̃_{1}(N) = ρ̃(N)  51.6  62.4  46.6  0.0
ρ̃_{2}(N) = ρ̃(N)  75.0  63.4  38.15
ρ̃_{3}(N) = ρ̃(N)  95.2  74.4
ρ̃_{4}(N) = ρ̃(N)  85.65

Examination of the complete red lists in three and four dimensions which appeared in [LS92] and [LS91] respectively shows that a proportion that varies unsteadily between 15% and 40% are root lattices, the majority of lattices on these lists being scaled lattices. If this state of affairs were to prevail for higher values of N, then any red scaled list would omit between 15% and 40% of the optimal lattices since it cannot by definition include root lattices.

Finally, we state one further reason that we believe these lists to be incomplete. This one is based on the actual lists, rather than on extrapolation. We have presented separately in Tables 5 and 4 a red scaled green list and the corresponding red scaled blue list. The first contains 80 entries and appears to be an excellent list in many ways, having as far as one can see the same characteristics as the actual red list for N < 4000. However, there are some known rules missing. We know this because they appear on the clearly inferior and shorter red scaled blue list. These two lists contain six entries in common. There are eight entries on the red scaled blue list that merit inclusion on the red scaled green list, but are not there. If included, they would in total displace eight entries already there.

One sees that a few missing entries do not alter the overall nature of the list very much. The missing entries are simply replaced by entries representing marginally inferior lattices; the effect on the list as a whole is local. Also, it is not particularly the entries with the highest z-values that seem to be missing.

6.2 Suitable Input for a Scaled List

We have listed the three-dimensional red scaled red list (Table A1) and the red scaled green list (Table 5). Only two elements N = 4185 and N = 4704 occur on both. Thereafter the red scaled red list deteriorates significantly when compared with the red scaled green list. However, the input red list contains all the really good elements of the input green list. The heuristic conclusion in this case is that, for scaling purposes, one does not want to start with optimal lattices having optimal N values. It appears that one will discover more if one inputs a list of good but not excellent lattices.

All our results appear to support to some extent this conclusion. We have found the red scaled blue list to be intermediate. The blue list being restricted to rank 1 simple lattices is not as good as the red list but seems to provide better scaled lattices. Any conclusion based on our four-dimensional lists must take into account that the blue list includes much higher values of N than the green list.

Theoretical support for this state of affairs can be found in Section 3. There it is noted that, starting with a family root lattice, the effect of scaling is in general to improve the z-value at first but then there is a steady decay in z-value. It is consistent with this situation that, for optimal values of N, the best lattices are not root lattices but are already scaled versions—but not very highly scaled. As mentioned above, the majority of the lattices on our red list are like this, and scaling them is unlikely to provide better ones.

6.3 Comments on Red Lists

It has been traditional to report results of the type treated here using red lists (i.e., lists of optimal lattices). One reason is that it is feasible to publish such a list. A red list contains in one page an excellent selection from a green list of fifty pages. Another reason is linked to the numerical quadrature application in which the cost is taken to be proportional to N the number of function values and the quality of the result to ρ. However, the present authors believe that, for the values of N now reached in three or four dimensions, the red list has become an anachronism. For many purposes a highlight list is adequate. For deeper investigation, the green list is probably needed. And, in applications, questions such as embedding of one rule in another and convenience in locating points using the relevant machine architecture may be much more significant than a small margin in the plot of N versus ρ.

While the red list contains an excellent selection, occasionally good lattices are excluded because they are “in the shadow of” marginally better lattices. An example of this occurs in three dimensions with N = 9760 and N = 9800. The first has ρ = 864 and the second ρ = 800, so the second does not occur on a red list. In fact, we know only three lattices with z(Λ) > 0.75; these are the two mentioned above and one with N = 4880. Thus, our red list has omitted what might be considered the third best lattice available. In investigations relating to the distribution of good lattices, one may prefer to know about all good lattices, even if in applications some are not going to be used.

6.4 The Tail of the List

We mentioned towards the end of Section 2 that it is trivial to find infinite sequences of lattices having monotonic increasing ρ(Λ′) and N′. Thus, an incomplete red list can be extended indefinitely. The lists we have presented have the additional requirement that z(Λ) should exceed a specified amount \overline{\overline{z}}. The reader should note that this by itself need not render a list finite. In fact, numerical and theoretical evidence suggests the opposite. Our list deteriorates and so is finite simply because it can contain only a subset of lattices, namely, those which are scaled versions of root lattices having N ≤ \overline{N}. Inequalities (2.8) and (2.9) apply to the scaled versions of each of this finite collection of root lattices, and so to the concatenation from which our lists are formed. It is important to realize that this deterioration is a property of our selection process and has nothing to do with the asymptotic behavior of a complete red list of optimal lattices.

7 Concluding Remarks

The basic contribution of this paper is the introduction of a very simple theory of rectangular scaling of lattices and a description of the behavior of ρ(Λ) under such scaling. This theory, described in Sections 2 and 3, remains to be fully exploited. In the rest of this paper we have used it only to provide lists of good lattices from existing lists. We are sure that many more applications of a more detailed and innovative nature may exist.

The rest of this paper is concerned with carrying out this scaling process on lists of lattices. By any measure, this has been very successful, producing a cornucopia of new good lattices. Indeed, so many and varied are the outputs of this process that organization and selection of results for publication has become a problem in itself. This aspect of the work is described and discussed in Sections 5 and 6.

We have uncovered many high-order lattice rules in dimensions 3, 4, and to some extent 5. The best are listed in Tables 1, 2, and 8, respectively. These turn out as might be expected in view of the current advanced theory (see, for example, Niederreiter [Nie92]). It is our hope that these concrete examples will provide a spur to the recognition and practical application of lattice rules in actual scientific projects involving multidimensional quadrature.

Appendix: Red Scaled Red Lists

The two lists in this appendix are included to illustrate the discussion in Section 6.2. At first glance both lists appear reasonable. However, in fact, these lists as a whole are significantly \underline{inferior} to those given in Tables 4 and 5, and 6 and 7, respectively, though they do contain some very good lattices.

Table A1 Red Scaled Red List in Three Dimension

\begin{matrix}N & ρ & b_{11} & b_{12} & b_{13} & b_{22} & b_{23} & b_{33} & rank & z \\ 4185 & 324 & 3 & 0 & 108 & 3 & 168 & 465 & 3 & 0.645620 \\ 4704 & 390 & 2 & 0 & 228 & 3 & 148 & 784 & 2 & 0.701090 \\ 5874 & 414 & 1 & 0 & 1044 & 2 & 303 & 2937 & 1 & 0.611650 \\ 7056 & 444 & 3 & 0 & 148 & 3 & 228 & 784 & 2 & 0.557620 \\ 7248 & 448 & 2 & 0 & 260 & 3 & 376 & 1208 & 2 & 0.549400 \\ 7696 & 480 & 2 & 0 & 466 & 2 & 834 & 1924 & 3 & 0.558120 \\ 8811 & 540 & 1 & 0 & 621 & 3 & 378 & 2937 & 2 & 0.556720 \\ 8820 & 555 & 3 & 0 & 185 & 3 & 285 & 980 & 2 & 0.571660 \\ 9408 & 588 & 3 & 0 & 228 & 4 & 148 & 784 & 2 & 0.571830 \\ 11748 & 621 & 1 & 0 & 1392 & 3 & 404 & 3916 & 1 & 0.495370 \\ 13212 & 648 & 2 & 0 & 1137 & 2 & 1428 & 3303 & 2 & 0.465390 \\ 13376 & 672 & 4 & 0 & 180 & 4 & 260 & 836 & 3 & 0.477330 \\ 15664 & 808 & 2 & 0 & 404 & 2 & 1392 & 3916 & 3 & 0.498250 \\ 17622 & 909 & 2 & 0 & 621 & 3 & 378 & 2937 & 2 & 0.504320 \\ 23352 & 1080 & 2 & 0 & 1304 & 2 & 2140 & 5838 & 3 & 0.465190 \\ 23496 & 1212 & 2 & 0 & 1392 & 3 & 404 & 3916 & 2 & 0.519160 \\ 31328 & 1440 & 2 & 0 & 828 & 4 & 504 & 3916 & 3 & 0.475840 \end{matrix}

Table A2 Red Scaled Red List in Four Dimensions

N  ρ b_{11} b_{12} b_{13} b_{14} b_{22} b_{23} b_{24} b_{33} b_{34} b_{44} rank  z
640 16 2 0 2 6 4 0 8 4 16 20 4 1.04376
864 24 1 0 0 42 2 0 69 3 54 144 2 1.26997
2 0 0 15 2 0 33 3 21 72 2 1.26997
1 0 0 42 2 0 69 3 12 144 2 1.26997
1124 30 1 0 0 106 1 0 178 1 442 1124 0 1.31706
1944 36 3 0 0 15 3 3 12 6 30 36 4 1.06190
3 0 0 15 3 0 21 3 33 72 4 1.06190
2164 40 1 0 0 152 1 0 330 2 104 1082 2 1.09017
2248 60 1 0 0 106 1 0 178 2 442 1124 2 1.58980
4328 72 1 0 0 104 2 0 152 2 330 1082 3 1.16625
1 0 0 104 2 0 242 2 400 1082 3 1.16625
4496 106 1 0 0 106 2 0 178 2 442 1124 3 1.66790
6744 120 1 0 0 159 2 0 267 2 663 1686 2 1.38308
8656 144 2 0 0 104 2 0 152 2 330 1082 4 1.36734
8992 212 2 0 0 106 2 0 178 2 442 1124 4 1.95413
19476 216 2 0 0 156 2 0 228 3 495 1623 2 1.08193
2 0 0 156 2 0 495 3 228 1623 2 1.08193
20232 318 2 0 0 159 2 0 267 3 663 1686 2 1.54517
35968 356 2 0 0 212 2 0 356 4 884 2248 4 1.08922
38952 360 2 0 0 208 3 0 304 3 660 2164 2 1.03259
40464 424 2 0 0 212 3 0 356 3 884 2248 2 1.17917
43821 468 3 0 0 156 3 0 228 3 495 1623 4 1.21996
45522 477 3 0 0 159 3 0 267 3 663 1686 4 1.20550
77904 624 3 0 0 208 3 0 304 4 660 2164 2 1.01613
80928 636 3 0 0 212 3 0 356 4 884 2248 2 1.00373

References

[BP85] M. Bourdeau and A. Pitre. Tables of good lattices in four and five dimensions. Numer. Math., 47:39–43, 1985.

[KZ74] G. Kedem and S. K. Zaremba. A table of good lattice points in three dimensions. Numer. Math., 23:175–180, 1974.

[LS91] J. N. Lyness and T. Sørevik. An algorithm for finding optimal integration lattices of composite order. Technical Report MCS-P258-0891, Mathematics and Computer Science Division, Argonne National Laboratory, 1991.

[LS92] J. N. Lyness and T. Sørevik. A search program for finding optimal integration lattices. Computing, to appear, 1992.

[Mai72] D. Maisonneuve. Recherche et utilisation des bons treillis, programming et resultats numeriques. In S. K. Zaremba, editor, Applications of Number Theory to Numerical Analysis, pages 121–201, London, 1972. Academic Press.

[Nie88] H. Niederreiter. Quasi-monte carlo methods for numerical integration. In G. Hämmerlin and H. Brass, editors, Numerical Integration III, pages 157–171. Birkhäuser Verlag, 1988.

[Nie92] H. Niederreiter. The existence of efficient lattice rules for multidimensional numerical integration. Math. Comput., 98:305–314, 1992.

[SL89] I. H. Sloan and J. N. Lyness. The representation of lattice quadrature rules as multiple sums. Math. Comp., 52:81–94, 1989.

[Zar66] S. K. Zaremba. Good lattice points, discrepancy and numerical integration. Ann. Mat. Pura Appl., 73:293–317, 1966.

[Zar74] S. K. Zaremba. Good lattice points modulo composite numbers. Monatsh. Math., 78:446–460, 1974.