The Canonical Forms of a Lattice Rule

J. N. Lyness

Abstract. Much of the elementary theory of lattice rules may be presented as an elegant application of classical results. These include Kronecker group representation theorem and the Hermite and Smith normal forms of integer matrices. The theory of the canonical form is a case in point. In this paper, some of this theory is treated in a constructive rather than abstract manner. A step-by-step approach that parallels the group theory is described, leading to an algorithm to obtain a canonical form of a rule of prime power order. The number of possible distinct canonical forms is derived, and this is used to determine the number of integration lattices having specified invariants.

1. Notation Used to Describe and Classify Lattice Rules

An s-dimensional lattice, Λ, is a set of points having the property that, when p and q are members of Λ, so are p + q and p − q. It may be defined by this property, together with a restriction that there are no points of accumulation. A very familiar lattice is the unit lattice Λ_{0}, which comprises all points p = (p_{1}, p_{2}, …, p_{s}), all of whose components p_{i} are integers. An integration lattice is a lattice that contains the unit lattice Λ_{0} as a sublattice. A lattice rule Q(Λ) is a quadrature rule for [0, 1)^{s} that employs the points of Λ ∩ [0, 1)^{s} as an abscissa set A(Q) and assigns an equal weight to each. Some lattice rules are useful for integrating naturally periodic functions. Other lattice rules may be very inefficient. A representative selection of the literature on lattice rules may be found in Sloan (1992) and Niederreiter (1992).

The investigation of lattice rules is hampered by two features: first, the large numbers of different rules that are available, and second, a bewildering lack of uniqueness in the various convenient representations for investigating rules and for classifying them.

A classical approach to lattices is based on the generator matrix. It is readily shown that, given any s-dimensional lattice Λ, there exists a set of s generators a_{1}, a_{2}, …, a_{s} such that all points

p = ∑_{i=1}^{s} λ_{i}a_{i} λ_{i} integer

lie in the lattice, and all lattice points are of this form. The s×s matrix A whose j-th row is a_{j} (j = 1, 2, …, s) is referred to as a generator matrix of the lattice. When Λ is an integration lattice, it is readily shown that all elements of A are rational and that N = |det A|^{−1} is the order of A(Q), the abscissa set of Q(Λ). An approach based particularly on the generator matrix (A^{−1})^{T} of the reciprocal lattice Λ^{⊥} has proved fruitful. However, inconvenient aspects of this approach include the absence of uniqueness of A and the difficulty of proceeding from the matrix A to a sum of function values.

The standard number theoretic rules of Korobov (1959) are also lattice rules. These are conventionally expressed in the form

Qf = \frac{1}{n} ∑_{j=1}^{n} \overline{f} (\frac{z}{n}j) .  (1.1)

Here z ∈ Λ_{0}, and \overline{f}(x) is a periodic continuation of f(x) that coincides with f(x) in [0, 1)^{s}. As is conventional, we denote x modulo Λ_{0} by {x}. The components of {x} are the respective nonnegative fractional parts of the components of x.

Only some lattice rules (those of rank 1) can be expressed in this form. On the other hand, all lattice rules may be expressed in a natural generalization of form (1.1) that we refer to as a t-cycle D − Z rule form. This is

Qf = \frac{1}{d_{1}d_{2} … d_{t}} ∑_{j_{1}=1}^{d_{1}} ∑_{j_{2}=1}^{d_{2}} ⋯ ∑_{j_{t}=1}^{d_{t}} \overline{f} (∑_{i=1}^{t} \frac{z_{i}}{d_{i}} j_{i}) ,  (1.2)

where d_{i} are integers and z_{i} ∈ Λ_{0}. Associated with this form are two integer matrices. D = diag{d_{1}, d_{2}, …, d_{t}} is a t × t diagonal matrix, and Z is the t × s matrix whose j-th row is z_{j}.

It is not difficult to show that this form represents a lattice rule. In fact, it is the rule of lowest order N that includes

c_{i} = {z_{i}/d_{i}} i = 1, 2, …, t.

The lattice Λ is generated by these c_{i} together with the unit vectors e_{k}, k = 1, 2, …, s. Note that the m-panel product trapezoidal rule is a lattice rule. One of its s-cycle D − Z forms has D = mI and Z = I.

Form (1.2) is not unique. Moreover, it may be repetitive. That is, for some integer k, it may include only d_{1}d_{2} … d_{t}/k distinct abscissas, each repeated k times.

Definition 1.3 The component z/n, where z = (ζ_{1}, ζ_{2}, …, ζ_{s}) ∈ Λ_{0} is termed proper when gcd(ζ_{1}, ζ_{2}, …, ζ_{s}, n) = 1 and c = z/n ∈ [0, 1)^{s}. (Colloquially, z/n is in its lowest terms and the point is in the integration region.)

If z/n in (1.1) is not proper, then the form is repetitive. This sort of trivial repetition is easy to recognize. However, possible repetition in the general t-cycle D − Z form need not be at all obvious.

It is straightforward to show (see Sloan and Lyness 1989) that a necessary and sufficient condition for the rule form Qf in (1.2) to be repetitive is that there exist integers j_{1}, j_{2}, …, j_{t} with j_{i} ∈ [0, d_{i}), not all zero, such that

∑_{i=1}^{t} \frac{j_{i}z_{i}}{d_{i}} ∈ Λ_{0}.  (1.4)

One classification of lattice rules based on the t-cycle form relies on the circumstance that the elements of the abscissa set A(Q) form a group G under addition modulo Λ_{0}.

In Sloan and Lyness (1989), the Kronecker group representation theorem was applied to this group to show that a t-cycle nonrepetitive D − Z form exists in which all elements d_{i} exceed 1, and d_{i+1} | d_{i}, and the z_{i} are linearly independent. Such a rule form was termed a canonical form. From the nomenclature of group theory, these particular values of d_{i} are termed invariants, and this particular value of t is termed the rank of the rule Q. The rank and invariants are unique to the lattice, but the choice of z_{i} in the canonical form is far from unique. However, no constructive approach for proceeding from a general t-cycle form to a canonical form was made available at that time.

This paper is concerned with finding a canonical form of a rule defined by a general t-cycle D − Z form. We shall, in fact, show only how to find nonrepetitive forms in which d_{i+1} | d_{i}. We may then rely on Corollary 4.6 of Sloan and Lyness (1989) which assures us that a form that appears to be canonical is indeed canonical if it is nonrepetitive. (See Theorem 3.1 below.)

2. Decomposition and Reassembly

The accompanying table illustrates the underlying group theory.

G  F_{1} F_{2}  F_{s}
S_{1} E_{11} E_{12} … E_{1s}
S_{2} E_{21} E_{22} … E_{2s}
⋮
S_{q} E_{q1} E_{q2} … E_{qs}

Each entry is an Abelian group. Any group in the initial row (column) is the direct sum of the other groups in that row (column), and the groups in all but the initial column are cyclic groups. The table illustrates the decomposition of an Abelian group G of order N = p_{1}^{β_{1}}p_{2}^{β_{2}} … p_{q}^{β_{q}} into the direct sum of cyclic groups F_{k}. Here p_{1}, p_{2}, …, p_{q} are distinct primes, and β_{i} are positive integers. The first stage is the decomposition of G into the direct sum

G = S_{1} ⊕ S_{2} ⊕ … ⊕ S_{q}  (2.1)

of its Sylow p groups. S_{j}, which is of order p_{j}^{β_{j}}, contains all elements of G whose order is any integer power of p_{j}. Any noncyclic Abelian group of prime power order may be decomposed into a direct sum of cyclic groups. Thus,

S_{j} = E_{j,1} ⊕ E_{j,2} ⊕ … ⊕ E_{j,s},  (2.2)

where E_{j,k} is a cyclic group of order p_{j}^{β_{j,k}}. These have been arranged in order so that β_{j,k} ≥ β_{j,k+1}. Clearly, ∑_{k=1}^{s} β_{j,k} = β_{j}. There may be fewer nontrivial groups than indicated here. The theory is not compromised if some trivial groups E_{j,k}, which contain only the identity element, are included but ignored. For these, β_{j,k} = 0.

Finally, we apply the result that the direct sum of cyclic groups whose orders are mutually prime is also a cyclic group. Thus,

F_{k} = E_{1,k} ⊕ E_{2,k} ⊕ … ⊕ E_{q,k}  (2.3)

is a cyclic group of order n_{k} = ∏_{j=1}^{q} p_{j}^{β_{jk}}. Note that, since β_{j,k} ≥ β_{j,k+1}, it follows that n_{k+1} | n_{k}.

What is illustrated here is the Kronecker decomposition of an Abelian group G into the direct sum of s cyclic groups F_{k}; k = 1, 2, …, s. The nontrivial values of n_{k} are termed the invariants of G, and the number of these is termed the rank of G.

The above remarks comprise at most a schematic for a possible derivation of a famous theorem in group theory. For our purposes, as we shall see, we do not need group theory. We may use the schematic to derive a canonical form.

It appears that in our application, the decomposition (2.1) into Sylow p groups is very simple, as is the recomposition (2.3) of the cyclic groups E_{j,k} into F_{k}. However, the middle stage (2.2) is nontrivial. The following examples illustrate the first and third operations. These are justified in the following theorem.

Theorem 2.4 Let n = pq, (p, q) = 1, and z, z_{1}, z_{2} ∈ Λ_{0}. Then

∑_{j=1}^{n} \overline{f} (\frac{jz}{n} + ϵ) = ∑_{j_{1}=1}^{p} ∑_{j_{2}=1}^{q} \overline{f} (\frac{j_{1}z}{p} + \frac{j_{2}z}{q} + ϵ)

and

∑_{j_{1}=1}^{p} ∑_{j_{2}=1}^{q} \overline{f} (\frac{j_{1}z_{1}}{p} + \frac{j_{2}z_{2}}{q} + ϵ) = ∑_{j=1}^{n} \overline{f} (\frac{jz_{3}}{pq} + ϵ) ,

where z_{3} = qz_{1} + pz_{2}. Moreover, if z_{1}/p and z_{2}/q are proper (see Definition (1.3) above), so is {z_{3}/pq}.

The proof of either part is trivial. Note that there are no minor restrictions. For example, z_{2}/q need not be in its lowest terms. The ϵ is notationally helpful in establishing extensions of these results.

As an example, we put the following rule into canonical form.

Example 2.5

Qf = \frac{1}{12.15} ∑_{j_{1}=1}^{12} ∑_{j_{2}=1}^{15} \overline{f} (\frac{(5, 8, 3)}{12}j_{1} + \frac{(8, 1, 0)}{15}j_{2}) .  (2.5)

This may be reexpressed as

\frac{1}{4.3.3.5} ∑_{j_{1}=1}^{4} ∑_{j_{2}=1}^{3} ∑_{j_{3}=1}^{3} ∑_{j_{4}=1}^{5} \overline{f}(x),

where

x = \frac{(5, 8, 3)}{4}j_{1} + \frac{(5, 8, 3)}{3}j_{2} + \frac{(8, 1, 0)}{3}j_{3} + \frac{(8, 1, 0)}{5}j_{4}.

This may be replaced by

x′ = \frac{(1, 0, 3)}{4}j_{1} + \frac{(2, 2, 0)}{3}j_{2} + \frac{(2, 1, 0)}{3}j_{3} + \frac{(3, 1, 0)}{5}j_{4}.

The sum in (2.5), which contains 180 elements of G, has now been reexpressed as the direct sum of three Sylow p groups, with p = 2, 3, and 5, respectively. Those with p = 2 and 5 are already cyclic groups. The Sylow 3 group is the direct sum of two cyclic groups.

The intermediate stage comprises, in general, removing repetition from each of the Sylow p groups. In this case, it is clear by inspection that the groups of order 3 are distinct. That is, the sums over j_{2} and j_{3} include nine distinct terms and not three. Applying the second part of Theorem 2.4 twice, we find successively

Qf = \frac{1}{180} ∑_{j_{12}=1}^{12} ∑_{j_{3}=1}^{3} ∑_{j_{4}=1}^{5} \overline{f}(x′′)

= \frac{1}{180} ∑_{j_{124}=1}^{60} ∑_{j_{3}=1}^{3} \overline{f}(x′′′)

= \frac{1}{180} ∑_{k_{1}=1}^{60} ∑_{k_{2}=1}^{3} \overline{f} (\frac{(31, 52, 45)}{60}k_{1} + \frac{(2, 1, 0)}{3}k_{2}) .  (2.6)

Here

x′′ = \frac{(11, 8, 9)}{12}j_{12} + \frac{(2, 1, 0)}{3}j_{3} + \frac{(3, 1, 0)}{5}j_{4},

and

x′′′ = \frac{(91, 52, 45)}{60}j_{124} + \frac{(2, 1, 0)}{3}j_{3}.

This rule form (2.6) is in canonical form.

The reader may have noticed that the overall result can be significantly altered by what appears at first sight to be a minor change in the problem. For example, if in Example 2.5 we replace the second vector (8,1,0) by (7,1,0), we find that the vector (2,1,0) in x′ must be replaced by (1,1,0). The middle stage becomes

∑_{j_{2}=1}^{3} ∑_{j_{3}=1}^{3} \overline{f} (\frac{(2, 2, 0)}{3}j_{2} + \frac{(1, 1, 0)}{3}j_{3} + ϵ) = 3 ∑_{j_{23}=1}^{3} \overline{f} (\frac{(1, 1, 0)}{3}j_{23} + ϵ) .

The new form Qf is repetitive, and Q has one invariant instead of two.

A satisfactory procedure to obtain the canonical form cannot rely on the chance recognition of this sort of circumstance. Subsequent sections are devoted to providing an algorithm for handling this problem.

3. Rules of Prime Power Order

As a preliminary, we remove some trivial complications. We are interested only in sequential proper forms. Qf is sequential if d_{1} ≥ d_{2} ≥ … ≥ d_{t} > 1. The i-th component is proper if z_{i}/d_{i} is in its lowest terms and c_{i} = z_{i}/d_{i} ∈ [0, 1)^{s}. The form is sequential proper when it is sequential and each element is proper. It is a trivial task to reexpress Qf in a t′ cycle D − Z, sequential proper form.

A geometric view is that the rule may be defined by t points c_{1}, c_{2}, …, c_{t} of orders d_{1}, d_{2}, …, d_{t}, respectively. A sequential proper form may be immediately constructed by reordering the points so that d_{1} ≥ d_{2} … ≥ d_{t} > 1, and setting z_{i} = d_{i}{c_{i}}.

It still may be repetitive (trivially if c_{i} = c_{i+1} and d_{i} = d_{i+1}).

Theorem 4.5 and its corollary 4.6 in Sloan and Lyness 1989 assure us that a non repetitive sequential proper rule form in which d_{i+1} | d_{i} is a canonical form. This is difficult to exploit as it is difficult in general to recognize a non repetitive form. However, the theory becomes much easier as soon as we restrict ourselves to prime power forms. In this section we deal with lattices and rule forms of prime power order; these are t cycle D − Z rule forms in which

d_{j} = p^{α_{j}}  j = 1, 2, …, t,  (3.1)

where p is a prime. For these, the divisibility condition is naturally satisfied and it follows:

Theorem 3.1 A prime power sequential proper form is canonical if and only if it is non repetitive.

In other words, a prevalent situation in which a rule form is both non repetitive and not canonical does not arise in the prime power order context.

In this section and in sections 4 and 5, we deal with lattices and rule forms of prime power order only. The problem of finding a canonical form reduces to that of recognizing and removing repetition.

Theorem 3.2 Let Qf and Q′f be prime power t-cycle D − Z forms having the same prime p, and the same Z matrix. Let D = diag(d_{1}, d_{2}, …, d_{t}) and D′ = diag(p, p, …, p) = pI. Then Qf and Q′f are either both repetitive or both nonrepetitive.

Proof. The condition for Qf to be repetitive is that there exist integers j_{i} ∈ [0, d_{i}) i = 1, 2, …, t not all zero such that

∑_{i=1}^{t} j_{i}z_{i}/d_{i} ∈ Λ_{0}.  (3.3)

Let us suppose that Qf is repetitive and the above j_{i} exist. Let I′ be {i | j_{i} ≠ 0}. Let j_{i}/d_{i} = γ_{i}/m_{i} in their lowest terms. Then γ_{i} ≠ 0, i ∈ I′, and

∑_{i∈I′} γ_{i}z_{i}/m_{i} ∈ Λ_{0}.  (3.4)

Let p^{λ} = max_{i∈I′} m_{i}. Let I′′ be {i | m_{i} = p^{λ}}. Then multiplying (3.4) by p^{λ−1} and subsuming all integers to the right, we obtain

∑_{i∈I′′} γ_{i}z_{i}/p ∈ Λ_{0}.  (3.5)

This statement implies that Q′f is repetitive.

The converse is marginally simpler to prove. If we set

\begin{matrix}j_{i} = γ_{i}d_{i}/p & i ∈ I′′ \\ j_{i} = 0 & i ∈ / I′′, \end{matrix}

we recover (3.3) from (3.5). □

Recasting this theorem geometrically is revealing.

Corollary 3.6 Any nonrepetitive prime power t-cycle rule form includes precisely p^{t} − 1 distinct points of order p.

Theorem 3.2 shows that the critical quantities in determining whether a prime power form is repetitive is the Z matrix. The integers d_{i} play a secondary role. This is confirmed in the following theorem.

Theorem 3.7 A t-cycle D − Z form of a prime power rule is repetitive if and only if the rank of Z modulo p is less than t.

Proof: In view of Theorem 3.2, we need only establish this for a t-cycle D′ − Z form where

D′ = diag{p, p, …, p}.

If this is repetitive, there exist j_{1}, j_{2}, …, j_{t}, not all zero such that

{∑_{i=1}^{t} j_{i}z_{i}/p} = 0.

This implies that ∑_{i=1}^{t} j_{i}z_{i} = pu for some u ∈ Λ_{0}; this is the condition that the rank of Z modulo p is less than t. □

The simple results of this section may be readily incorporated into an algorithm that transforms a general p-power t-cycle D − Z rule form into a sequential, proper, and non-repetitive form. In the final form, Z either is unimodular or contains a t × t unimodular submatrix.

This algorithm is a variant of a standard triangularization technique.

At the start of the j-th stage, we have

d_{1} ≥ d_{2} ≥ … ≥ d_{j} ≥ … ≥ d_{t} > 1

all being powers of p, and z_{i}/d_{i} i = 1 … j − 1 are all proper. Associated with z_{1}, z_{2}, …, z_{j−1} we have distinct integers i_{1}, i_{2}, …, i_{j−1}, which we term column indices. Moreover,

\begin{matrix}Z_{r,i_{c}} = 1 & when & r = c \\ Z_{r,i_{c}} = 0 & when & r > c \end{matrix} \} \begin{matrix}c = 1, 2, …, j − 1 \\ r = 1, 2, …, t \end{matrix} .

The j-th stage comprises the following:

1. Let z_{j} = (ζ_{1}, ζ_{2}, …, ζ_{s}). Identify a component, say ζ_{ℓ}, for which (ζ_{ℓ}, p) = 1. Set i_{j} = ℓ. Replace z_{j} by kz_{j}, where k = ζ_{ℓ}^{−1}(mod d_{j}) and then replace z_{j} by z′_{j} = (ζ′_{1}, ζ′_{2}, …, ζ′_{s}) with ζ′_{i} ∈ [0, d_{j}). (This leaves ζ′_{ℓ} = 1.)

2. For i > j, replace z_{i} by z_{i} − Z_{i,ℓ}z_{j}. (This leaves Z_{i,ℓ} = 0; i > j.)

3. Carry out trivial adjustments on Z and D necessary to leave a t′-cycle D − Z sequential proper form.

Comments:

1. We have by hypothesis that z_{j}/d_{j} is proper. Thus, there is some component of z_{j}, say the ℓ-th, that is not a multiple of p, and ℓ may be chosen for i_{j} in 1.

3. These adjustments include the following:

a. Put any improper z_{i}/d_{i} into proper form z′_{i}/d′_{i}. b. Remove any rows z_{i} for which either z_{i} = 0 or d_{i} = 1; naturally this step reduces

the value of t.

c. If necessary, reorder the rows of Z so that the ordering of d_{i} is sequential.

The final Z matrix is an integer matrix. If its columns were permuted in accordance with the column indices, it would be upper triangular with unit diagonal. Thus, it contains a t × t unimodular submatrix (corresponding to retaining only the columns numbered i_{1}, i_{2}, …, i_{t}).

Because of this unimodularity, it follows that when t = s, the matrix A = D^{−1}Z is a generator matrix of Λ. In general, t < s, and Ã = D^{−1}Z comprises the first t rows of a generator matrix. The remaining s − t rows of the generator matrix may be chosen as unit vectors e_{λ}, the λ being the elements of [1, s] not assigned to be column indices.

Finally, note that Z is not unique. In general, the column indices can be chosen in many ways, and rows having the same d element may be interchanged.

4. Canonical Form Redundancy of Prime Power Forms

In the preceding section, we remarked that the Z matrix is not unique. In this section, we quantify this lack of uniqueness. We take an r-cycle prime power rule form Qf which is in canonical form; we see how many distinct reassignments of Z exist. Initially, we shall have to assume that the result depends on p, D, and Z. However, it will appear that it simply depends on p and D. Let

Qf = \frac{1}{n_{1}n_{2} … n_{r}} ∑_{j_{1}=1}^{n_{1}} ∑_{j_{2}=1}^{n_{2}} … ∑_{j_{r}=1}^{n_{r}} \overline{f} (∑_{k=1}^{r} \frac{j_{k}z_{k}}{n_{k}} )  (4.1)

be a canonical form of Q. Here as before,

n_{1} ≥ n_{2} ≥ … ≥ n_{r} > 1,

and each n_{i} is a power of p. Also, z_{k} ∈ [0, n_{k})^{s}, k = 1, 2, …, r. Note that, since this is a canonical form, we know that z_{k}/n_{k} is in its lowest terms. Each member of the set of generators

c_{k} = z_{k}/n_{k}  (4.2)

is itself an element of [0, 1)^{s}.

Definition 4.3 ¯ μ̄_{s}(n_{1}, n_{2}, …, n_{s}; N; Z) is the number of distinct ways of assigning the Z-matrix so that the rule is the same. (Here z_{k} ∈ [0, n_{k})^{s}.)

Geometrically, this is the number of different point sets c_{1}, c_{2}, …, c_{r} that can be put into (4.1) leaving the same rule. These points are ∈ [0, 1)^{s}.

It will appear that ¯ μ̄_{s} is independent of Z, and we shall later drop the Z in the definition.

The construction of a formula for ¯ μ̄_{s} uses relatively straightforward concepts that nevertheless must be applied with care. We shall suppose that we assign the vectors z_{j} (or c_{j} = z_{j}/n_{j}) in turn, starting with j = 1 and ending with j = r. Clearly, every c_{j} has to be a member of the abscissa set. Thus, when we start the j-th stage, we may limit the choice for c′_{j} as follows:

c′_{j} = ∑_{i=1}^{r} λ_{i}^{j}c_{i} λ_{i}^{j} ∈ [0, n_{i})  (4.4)

or

z′_{j} = ∑_{i=1}^{r} λ_{i}^{j} \frac{n_{j}}{n_{i}} z_{i}.  (4.5)

It is convenient to drop the { } symbol here. The restriction λ_{i}^{j} ∈ [0, n_{i}) in (4.4) simply prevents duplication, since λ_{i}^{j}c_{i} ≡ (λ_{i}^{j} + n_{i})c_{i}. When assigning c′_{j}, it is clear that for those values of i for which n_{i} < n_{j}, we may choose any available λ_{i}^{j}, and hence there are n_{i} distinct choices for each such λ_{i}^{j}. However, for those values of i for which n_{i} > n_{j}, the choice has to be restricted so that z′_{j} in (4.5) turns out to be in Λ_{0}. That is, λ_{i}^{j}(n_{j}/n_{i}) must be an integer. Thus, for these values of i, there are only n_{j} distinct choices for each λ_{i}^{j}. (Geometrically, this recognizes that c_{j} is of order n_{j} and therefore only multiples of c_{i} of this order or less may be included.) There remain values of i for which n_{i} = n_{j}.

To fix ideas, suppose n_{j+1} > n_{j} > n_{j−1}. Then there is only one value λ_{j}^{j} remaining to assign. Since z_{j} itself must be attainable, we can allow λ_{j}^{j} to take one of n_{j}(1 − p^{−1}) distinct values only.

In this case, then, the number of ways of assigning z′_{j} is the product over i of the number of ways of assigning λ_{j}^{i}. This gives

∏_{i=1}^{j−1} n_{j} × n_{j} (1 − \frac{1}{p}) × ∏_{i=j+1}^{r} n_{i}.

Thus, when n_{j−1} > n_{j} > n_{j+1}, whatever the individual values of z_{i}, i = 1, 2, …, r, the number of ways of reassigning z_{j}, without changing any other z_{i} is

n_{j}^{j} ∏_{i=j+1}^{r} n_{i} (1 − \frac{1}{p^{λ(j)}} ) with λ(j) = 1.

In general, we cannot expect all n_{j} to be distinct. Let us suppose

n_{j} > n_{j+1} = n_{j+2} = … = n_{j+w} > n_{j+w+1}  (4.6)

and isolate the part of the calculation involving the assignment of c′_{j+1} … c′_{j+w} to the extent that this is affected by c_{j+1} … c_{j+w}. For convenience, we suppress the subscript j and denote by n the common value n_{j+1}. We need to consider the number of possibilities for

c′_{1} = ∑_{i=1}^{w} λ_{i}^{1}c_{i}
c′_{2} = ∑_{i=1}^{w} λ_{i}^{2}c_{i}  (4.7)
…
c′_{w} = ∑_{i=1}^{w} λ_{i}^{w}c_{i}.

These are assigned in the following order. First, λ_{i}^{1}, i = 1, 2, …, w are assigned. We need c′_{1} to be of order n. To ensure this, λ_{i}^{1} may be chosen in any way so long as at least one term λ_{i}^{1}c_{i} is of order n. This is equivalent to choosing a point of order n in a w-dimensional space. The number of points is n^{w}(1 − p^{−w}). Later in the calculation, we have to assign c′_{2}. However, c_{1} has already been assigned and is of order n. To ensure that nc_{2} is independent of nc_{1}, one must ensure that at least one of λ_{i}^{2}c_{i}, i = 2, 3, …, w is of order n. λ_{1}^{2} is not restricted. The number of points available is n^{w}(1 − p^{−w+1}).

Continuing in this way, we find the number of ways of assigning c′_{k}, k = 1, 2, …, w to be

n^{w}(1 − p^{−w−1+k}).

We note again that the result does not depend in detail on the rule form. It depends only on p and on n_{1}, n_{2}, …, n_{r}. When several n_{j} are equal, it depends particularly on the pattern. It is notationally convenient to define an integer index.

Definition 4.8 With respect to

n_{1} ≥ n_{2} ≥ n_{3} ≥ … ≥ n_{r}, the index
λ(j) = k − j,  (4.8)

where k is the smallest integer for which n_{k} < n_{j}.

Theorem 4.9 Given a rule form Qf, the number of nontrivial ways of reassigning c_{j} so that the rule remains unaltered is

∏_{i=1}^{r} n_{max(i,j)} (1 − \frac{1}{p^{λ(j)}} ) .  (4.9)

This number, large as it is, refers only to the number of ways of reassigning c_{j}. Since it is independent of the individual choice for the other generators c_{i} (i ≠ j), we obtain the total number of nontrivial assignments as the product of r corresponding terms. Thus, we have the following corollary.

Corollary 4.10

¯μ̄_{s}(n_{1}, n_{2}, …, n_{s}; N) = ∏_{j=1}^{r} n_{j}^{j} ∏_{i=j+1}^{r} n_{i}(1 − p^{−λ(j)})  (4.10)
= N ∏_{t=1}^{r} n_{t}^{2t−2}(1 − p^{−λ(t)}).

5. The Number of Distinct Prime Power Rules Having Specified Invariants

In the preceding section we derived a formula for ¯ μ̄_{s}(n_{1}, n_{2}, …, n_{s}; N). This is the number of distinct assignments for c_{1}, c_{2}, …, c_{r} that give rise to the same rule Q. The formula is the same for any rule having these invariants. We may exploit this fact to derive a formula for the number of distinct rules ν_{s}(n_{1}, n_{2}, …, n_{s}; N) having these invariants.

Definition 5.1 μ̄_{s}(n_{1}, n_{2}, …, n_{s}; N) is the number of distinct ways of assigning the Z matrix so that the rule has these invariants. (Here z_{k} ∈ [0, n_{k})^{s}.)

Geometrically, this is the number of different point sets c_{1}, c_{2}, …, c_{r} that can be substituted into (4.1) to give a nonrepetitive rule form.

Comparing Definition 5.1 with Definition 4.3 shows that μ̄_{s} is larger than ¯ μ̄_{s}. Since the redundancy is the same for each distinct rule, it follows that

ν_{s}(n_{1}, n_{2}, …, n_{s}; N) = \frac{μ̄_{s}(n_{1}, n_{2}, …, n_{s}; N)}{¯μ̄_{s}(n_{1}, n_{2}, …, n_{s}; N)}.  (5.2)

The determination of μ̄_{s} is an exercise of the same type as the determination of ¯ μ̄_{s} but much easier in detail. (The formula does not bring in the pattern of n_{i} explicitly.)

The rule may be defined by an assignment of r points c_{1}, c_{2}, …, c_{r}. (c_{i} = z_{i}/n_{i} is a point of order n_{i}.) μ̄_{s} is the number of distinct point assignments. This is calculated as ∏_{j=1}^{r} P_{j}, where P_{j} is the number of ways of choosing c_{j} once c_{1}, c_{2}, and c_{j−1} have already been assigned.

The number of points of order n_{j} is n_{j}^{s}(1 − p^{−s}). (This is because when n = p^{α}, the grid containing n^{s} points contains all points of orders 1, p, …, p^{α}. The number of order precisely p^{α} is (p^{α})^{s} − (p^{α−1})^{s}.) However, if c_{1}, c_{2}, …, c_{j−1} have already been assigned, in view of Theorem 3.2, c_{j} must be chosen so that the order p points it introduces have not been included previously. There are in total p^{s} −1 order p points. The number of these in the span of c_{1}, c_{2}, …, c_{j−1} is p^{j−1} − 1. Thus, a proportion (p^{j−1} − 1)/(p^{s} − 1) of the order p points is not available; alternatively stated, a proportion (p^{s} − p^{j−1})/(p^{s} − 1) = (1 − p^{−s+j−1})/(1 − p^{−s}) is available. It follows relatively painlessly that of the n_{j}^{s}(1 − p^{−s}) points of order n_{j}, only that proportion give rise to available order p points. Thus, c_{j} may be chosen in n_{j}^{s}(1 − p^{j−1−s}) ways. Hence,

μ̄_{s} = ∏_{j=1}^{r} P_{j} = ∏_{j=1}^{r} n_{j}^{s}(1 − p^{j−1−s})
= N^{s} ∏_{j=1}^{r}(1 − p^{j−1−s}).  (5.3)

The final stage gives the following theorem.

Theorem 5.4

ν_{s}(n_{1}, n_{2}, …, n_{s}; N) = ∏_{j=1}^{⌊s/2⌋} (\frac{n_{j}}{n_{s+1−j}} )^{s−2j+1} ∏_{j=1}^{r} \frac{(1 − 1/p^{s+1−j})}{(1 − 1/p^{λ(j)})}.  (5.4)

Here n_{1} ≥ n_{2} ≥ … ≥ n_{r} > 1, and we have set n_{j} = 1 for all j ∈ [r + 1, s]. The index λ(j) is defined in (4.8).

With a single exception, ν_{s} > 1. The exception is the s-dimensional m copy rule. Here all the invariants are equal, and the set λ(j) comprises the first s positive integers.

The first three cases are

ν_{s}(n_{1}, 1^{s−1}; N) = N^{s−1}(1 − 1/p^{s})/(1 − 1/p)  (5.5)
ν_{s}(n_{1}, n_{2}, 1^{s−2}; N) = (N^{s−1}/n_{2}^{2})(1 − 1/p^{s})(1 − 1/p^{s−1})/(1 − 1/p^{j_{1}})(1 − 1/p), (5.6)

where

j_{1} = 1 when n_{1} > n_{2} > 1
= 2 when n_{1} = n_{2} > 1,
ν_{s}(n_{1}, n_{2}, n_{3}, 1^{s−3}; N) = \frac{N^{s−1}}{n_{2}^{2}n_{3}^{4}} \frac{(1 − 1/p^{s})(1 − 1/p^{s−1})(1 − 1/p^{s−2})}{(1 − 1/p^{k_{1}})(1 − 1/p^{k_{2}})(1 − 1/p)},  (5.7)

where

k_{1} = k_{2} = 1 when n_{1} > n_{2} > n_{3} > 1
k_{1} = 3; k_{2} = 2 when  n_{1} = n_{2} = n_{3} > 1
k_{1} = 2; k_{2} = 1 otherwise.

These are valid only when n_{1} ≥ n_{2} ≥ … ≥ n_{r} > 1 and each n_{i} is a power of the same prime p.

These results have been obtained independently by Joe and Hunt (1992). Their general approach follows much the same lines as the one here. However, their derivation of ¯ μ̄_{s} is embedded in group theory.

These results resemble a similar result (Lyness and So/revik 1989) for ν_{s}(N), the number of distinct lattice rules of order N. When N = p^{β}, this is

ν_{s}(N) = N^{s−1} ∏_{i=1}^{s−1} [(1 − \frac{1}{p^{i+β}} ) /(1 − \frac{1}{p^{i}} )] .  (5.8)

6. A General Formula for ν_{s}(n; N)

A simple application of the group decomposition described in Section 2 allows us to base a general formula for ν_{s}(n; N) on the one valid only for prime power rules in Theorem 5.4. The decomposition (2.1) of G into the direct sum of Sylow p groups has the property that when G has invariants n(G), the invariants n(S_{p}) of each Sylow p group is known. The uniqueness of this decomposition leads to the result that the number of distinct abscissa sets for which G has invariants n(G) is the product of the several corresponding numbers for each component S_{p}.

Theorem 6.1 Let the prime decomposition of N be

N = p_{1}^{β_{1}}p_{2}^{β_{2}} … p_{q}^{β_{q}}.

Let the invariants n_{k} of a rule Q of order N be given by

n_{k} = p_{1}^{β_{1k}}p_{2}^{β_{2k}} … p_{q}^{β_{qk}} k = 1, 2, …, s.

Then the number of distinct rules Q having these invariants is

ν_{s}(n_{1}, n_{2}, …, n_{s}, N) = ∏_{j=1}^{q} ν_{s}(p_{j}^{β_{j1}}, p_{j}^{β_{j2}}, …, p_{j}^{β_{js}}; p_{j}^{β_{j}}),

where an explicit expression for each of the factors on the right appears in (5.4) above.

In the statement of the above theorem, we have followed various conventions from earlier sections. In particular,

β_{j,i} ≥ β_{j,i+1}.

This theorem is a natural extension of a result in Lyness and So/revik (1989) to the effect that the number of distinct lattice rules of order N is given by

ν_{s}(N) = ∏_{j=1}^{q} ν_{s}(p_{j}^{β_{j}}).

7. Concluding Remarks

The general thrust of this article is to provide a straightforward and concrete approach to some of the basic structure of lattice rules. This approach has led through several areas which are new only in a marginal sense.

For example, spelling out the group theory and applying it as in Section 2 is new. Something like it was submitted in an earlier version of Sloan and Lyness (1989) but was excised by the referee. Again, the simple procedure in Section 3 for the reduction of a prime power rule to canonical form has not appeared before. What will soon be available is a more general process in which the Smith Normal Form of a generator matrix is used to obtain a general canonical form; see Lyness and Keast (1991) and Langtry (1991). However, in that process the simple underlying geometry is obscured.

The results of Sections 4 to 6 about the number of lattice rules with given invariants were available to the author in 1989 and promised in 1991. These were subsequently derived independently by Joe and Hunt (1992). In broad outline, their derivation parallels the one given here. However, in their work, ¯ μ̄_{s} appears as the result of a nontrivial argument based on group theory, whereas here it is derived in a direct way as a straightforward redundancy factor in a matrix representation.

This author hopes that this somewhat pedestrian exposition of these ideas will help enlighten an elegant branch of numerical quadrature.

Acknowledgment

This work was supported in part by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy, under Contract W-31-109-Eng-38.

References

Joe S. and Hunt D. C. (1992), “The Number of Lattice Rules Having Given Invariants,” Bull. Australian Math. Soc. 46, pp. 479–495. See also Applied Mathematics Preprint AM91/44, UNSW.

Korobov N. M. (1959), “The Approximate Computation of Multiple Integrals” (Russian), Dokl. Akad. Nauk. SSSR 124, pp. 1207–1210.

Lyness J. N. and Keast P. (1991), “Application of the Smith Normal Form to the Structure of Lattice Rules,” Preprint MCS-P269-0891, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, Ill.

Lyness J. N. and So/revik T. (1989), “The Number of Lattice Rules,” BIT 29, pp. 527–534.

Langtry T. N. (1991), “The Determination of Canonical Forms for Lattice Quadrature Rules,” private communication.

Niederreiter H. (1992), “Random Number Generation and Quasi-Monte Carlo Methods ,”CBMS-NSF 63, SIAM, Philadelphia.

Sloan I. H. (1992), “Numerical Integration in High Dimensions—The Lattice Rule Approach,” in Numerical Integration, T. O. Espelid and A. Genz (eds.), 55–69, Kluwer Academic Publishers, The Netherlands.

Sloan I. H. and Lyness J. N. (1989), “The Representation of Lattice Quadrature Rules as Multiple Sums,” Math. Comput. 52, pp. 81–94.

Dr. J. N. Lyness Mathematics and Computer Science Division Argonne National Laboratory 9700 South Cass Avenue Argonne, IL 60439 lyness@mcs.anl.gov