Some possible simplifications of the notation of higher order nets and sequences

In this entry I discuss the definition of (digital) higher order nets and sequences and some possible simplifications of the notation.

Digital higher order nets and sequences have been introduced in

whereas higher order nets have been introduced in

  • [2] J. Dick and J. Baldeaux, Equidistribution properties of generalized nets and sequences. In: Proceedings of the MCQMC’08 conference, Montreal, Canada, P. L’Ecuyer and A. Owen (eds.), pp. 305–323, 2009. doi: 10.1007/978-3-642-04107-5_19 An earlier version can be found here.

There are several parameters occurring in the definition of higher order nets, namely t, \alpha,\beta, n, m, s, b and for higher order sequences we have the parameters t, \alpha, \beta, \sigma, s, b.

(Digital) higher order nets and sequences are point sets \{\boldsymbol{x}_0,\ldots, \boldsymbol{x}_{b^m-1}\} \subset [0,1)^s and sequences \{\boldsymbol{x}_0,\boldsymbol{x}_1, \ldots, \} such that

\displaystyle \left|\int_{[0,1]^s} f(\boldsymbol{x}) \,\mathrm{d} \boldsymbol{x} - \frac{1}{N} \sum_{n=0}^{N-1} f(\boldsymbol{x}_n) \right| = \mathcal{O} (N^{-\alpha} (\log N)^{\alpha s}),

where {}N =b^m is the number of quadrature points and {} \alpha is the smoothness of the integrand {}f.

Definitions

For convenience we repeat the definitions of those (digital) higher order nets and sequences here. A discussion of the parameters occurring in these definitions follows in the subsequent section.

Defintion [Digital (t,\alpha,\beta, n \times m, s)-net]
Let s,\alpha,n,m \in \mathbb{N}, let 0 \textless \beta \le \min(1,\alpha m/n) be a real number and let 0 \le t \le \beta n be an integer. Let \mathbb{F}_b be the finite field of order {}b, where {}b is a prime power. Let C_1,\ldots, C_s \in \mathbb{F}_b^{n \times m} where \boldsymbol{c}_j^{(i)} \in \mathbb{F}_b^m is the {}jth row vector of C_i for 1 \le j \le n and 1 \le i \le s. If for all 1 \le d_{i,\nu_i} \textless \cdots \textless d_{i,1} \le n, with

\displaystyle \sum_{i=1}^s \sum_{j=1}^{\min(\nu_i,\alpha)} d_{i,j} \le \beta n - t,

the vectors

\displaystyle \boldsymbol{c}^{(1)}_{d_1,\nu_1},\ldots, \boldsymbol{c}^{(1)}_{d_1,1},\ldots, \boldsymbol{c}^{(s)}_{d_s,\nu_s},\ldots, \boldsymbol{c}^{(s)}_{d_s,1}

are linearly independent over \mathbb{F}_b, then the digital net with generating matrices C_1,\ldots, C_s is called a digital (t,\alpha,\beta, n \times m, s)-net over \mathbb{F}_b.

For \alpha=\beta = 1 and n = m one obtains a digital (t,m,s)-net over \mathbb{F}_b.

Definition [Digital (t,\alpha,\beta,\sigma, s)-sequence]
Let s,\alpha, \sigma \in \mathbb{N} and t \in \mathbb{N}_0 and let 0 \textless \beta \le \min(1, \alpha/\sigma) be a real number. Let \mathbb{F}_b be the finite field of order {}b, where {}b is a prime power. Let C_1,\ldots, C_s \in \mathbb{F}_b^{\mathbb{N} \times \mathbb{N}}, where \boldsymbol{c}^{(i)}_j \in \mathbb{F}_b^{\mathbb{N}} is the {}jth row vector of the matrix C_i for j \in \mathbb{N} and 1 \le i \le s. Further let C_i^{(\sigma m \times m)} denote the left upper \sigma m \times m submatrix of C_i for 1 \le i \le s. If for all m \textgreater t/(\beta \sigma) the matrices C_1^{\sigma m \times m)},\ldots, C_s^{(\sigma m \times m)} generate a digital (t, \alpha,\beta, \sigma m \times m, s)-net over \mathbb{F}_b, then the digital sequence with generating matrices C_1,\ldots, C_s is a digital (t, \alpha,\beta, \sigma, s)-sequence over \mathbb{F}_b.

For \alpha = \beta = \sigma = 1 one obtains a digital (t,s)-sequence over \mathbb{F}_b.

Before we can define the analogue geometrical concepts, we need the notion of a higher order elementary interval (which is actually not an interval anymore, but a union of intervals). We need some notation. Let \boldsymbol{\nu}=(\nu_1,\ldots, \nu_s) \in \mathbb{N}_0^s, let |\boldsymbol{\nu}|_1 = \sum_{i=1}^s \nu_i, let \boldsymbol{d}_{\boldsymbol{\nu}} = (d_{1,1},\ldots, d_{1,\nu_1}, \ldots, d_{s,1},\ldots, d_{s,\nu_s}), let \boldsymbol{a}_{\boldsymbol{\nu}} \in \{0,1,\ldots, b-1\}^{|\boldsymbol{\nu}|_1} and let \boldsymbol{a}_{\boldsymbol{\nu}} = (a_{1,d_{1,1}}, \ldots, a_{1,d_{1,\nu_1}},\ldots, a_{s,d_{s,1}}, \ldots, a_{s,d_{s,\nu_s}}), where the components d_{i,l} and a_{i,l}, l = 1,\ldots, \nu_i, do not appear in \boldsymbol{d}_{\boldsymbol{\nu}} and \boldsymbol{a}_{\boldsymbol{\nu}} if \nu_i = 0. By a higher order elementary interval we mean a subset of [0,1)^s of the form

\displaystyle J(\boldsymbol{d}_{\boldsymbol{\nu}}, \boldsymbol{a}_{\boldsymbol{\nu}}) = \prod_{i=1}^s \bigcup_{\stackrel{a_{i,l}=0}{l \in \{1,\ldots, n\} \setminus \{d_{i,1},\ldots, d_{i,\nu_i} \}}}^{b-1} \left[\frac{a_{i,1}}{b} + \cdots + \frac{a_{i,n}}{b^n}, \frac{a_{i,1}}{b} + \cdots + \frac{a_{i,n}}{b^n} +\frac{1}{b^n}\right),

where b \ge 2 is an integer and where for i = 1,\ldots, s we have 1 \le d_{i,\nu_i} \textless \cdots \textless d_{i,1} \le n in case \nu_i \textgreater 0 and \{d_{i,1},\ldots, d_{i,\nu_i}\} = \emptyset if \nu_i = 0.

An example of a higher order (or generalized) elementary interval can be found in [2].

Definition [(t,\alpha,\beta, n, m, s)-net]
Let n,m,\alpha \ge 1 be natural numbers, let 0 \textless \beta \le 1 be a real number, and let 0 \le t \le \beta n be an integer. Let b \ge 2 be an integer and let P=\{\boldsymbol{x}_0,\ldots, \boldsymbol{x}_{b^m-1}\} \in [0,1)^s, s \ge 1. The point set {}P is called a (t,\alpha,\beta, n,m,s)-net in base {}b if for all integers 1 \le d_{i,\nu_i} \textless \cdots \textless d_{i,1}, where \nu_i \ge 0, with

\displaystyle \sum_{i=1}^s \sum_{j=1}^{\min(\nu_i,\alpha)} d_{i,j} \le \beta n - t

where for \nu_i = 0 we set the empty sum \sum_{j=1}^{\min(\nu_i,\alpha)} d_{i,j} = 0, the higher order elementary interval J(\boldsymbol{d}_{\boldsymbol{\nu}}, \boldsymbol{a}_{\boldsymbol{\nu}}) contains exactly b^{m-|\boldsymbol{\nu}|_1} point of {}P for each \boldsymbol{a}_{\boldsymbol{\nu}} \in \{0,1,\ldots, b-1\}^{|\boldsymbol{\nu}|_1}.

For \alpha = \beta = 1 and n = m one obtains a (t,m,s)-net in base {}b.

Definition [(t,\alpha,\beta,\sigma,s)-sequence]
Let \alpha, \sigma \ge 1 and t \ge 0 be integers and 0 \textless \beta \le 1 be a real number. Let S= \{\boldsymbol{x}_0,\boldsymbol{x}_1,\ldots\} be a sequence of numbers in [0,1)^s. Then {}S is a (t,\alpha,\beta,\sigma, s)-sequence in base {}b if for all k \ge 0 and all m \textgreater t/(\beta \sigma) we have that \boldsymbol{x}_{kb^m}, \ldots, \boldsymbol{x}_{(k+1)b^m-1} is a (t,\alpha,\beta, \sigma m, m, s)-net in base {}b.

For \alpha=\beta=\sigma=1 one obtains a (t,s)-sequence in base {}b.

Meaning of the parameters

Some parameters have the same meaning as for classical (t,m,s)-nets and (t,s)-sequences, and are therefore not discussed further. These are

  • {}b, the base or \mathbb{F}_b the finite field over which the net or sequence is constructed,
  • {}s the dimension,
  • {}m is equal to m = \log_b N, where {}N is the number of points and \log_b is the logarithm in base {}b.

Now to the remaining parameters of (digital) higher order nets and (digital) higher order sequences. There are a few guiding principles which we follow in defining (digital) higher order nets and sequences:

  1. each parameter in the definition of higher order nets should have an analogue in the definition for digital higher order nets and vice versa,
  2. each parameter in the definition of higher order sequences should have an analogue in the definition for digital higher order sequences and vice versa,
  3. (digital) higher order sequences should be a direct extension of (digital) higher order nets,
  4. (digital) higher order nets should be a finite version of (digital) higher order sequences, and
  5. (digital) (t,m,s)-nets should be a special case of (digital) higher order nets and analogously for sequences.

A consequence of these guiding principles is that all definitions are related to each other and hence one should not consider a definition just on its own. In other words, each definition should only be considered in conjunction with all other definitions.

One could of course ignore one or more of the above principles and arrive at a different definition of some object (which might appear more natural). However, it makes the objects more difficult to relate to each other. For instance, a digital (t,\alpha,\beta, n \times m, s)-net over \mathbb{F}_b is a (t,\alpha,\beta, n,m,s)-net in base {}b and analogously for (digital) higher order sequences. This is a natural result and holds since in the definitions the parameters of each object have direct analogues in the related object.

In the error bound above we said that \alpha denotes the smoothness of the integrand {}f. We make one assumption which makes the definition a bit more complicated, namely, we assume that \alpha is not a known fixed number, that is, we simply do not know the smoothness of the integrand. Since we assume that we do not know {}\alpha we cannot talk about an order \alpha net in this context. So we think of the remaining parameters as a function of \alpha and, for a given point set or sequence, we would like to know the value of the remaining parameters t, \beta,\sigma for each value of \alpha. In this sense, it would also be possible to write for instance digital (t(\alpha), \beta(\alpha), n\times m, s)-net instead of digital (t, \alpha,\beta, n \times m, s)-net (and analogously for the other three cases).

Using the guiding principles we can explain one more parameter immediately. Namely, {}n is the number of rows of the generating matrices C_1,\ldots, C_s \in \mathbb{F}_b^{n \times m}. By principle (2) it follows that we also need to have the parameter {}n in the definition of higher order nets (though it does not have such an immediate interpretation as for digital higher order nets).

The parameter \sigma is introduced because of principle (4). Namely, when one considers the first b^m points of a digital (t,\alpha,\beta,\sigma,s)-sequence, then the left upper \sigma m \times m submatrices of the generating matrices of the digital higher order sequence generate a digital (t,\alpha,\beta, \sigma m \times m, s)-net. Hence, by principle (4) n = \sigma m. Notice that we cannot choose n = \alpha m in this case, since \alpha is not a fixed number (i.e. the smoothness \alpha is not known).

Next we discuss the parameter \beta. If one considers only (digital) higher order nets, then one could argue that the parameter \beta is redundant. But to understand \beta one needs to consider (digital) higher order sequences rather than (digital) higher order nets. The parameter \beta then appears in the definition of (digital) higher order nets because of principle (3), we want (digital) higher order sequences to be a direct extension of (digital) higher order nets. If one ignores principle (3) then one could define (digital) higher order nets without using \beta.

For sequences, it has been shown that \sum_{i=1}^s \sum_{j=1}^{\min(\nu_i,\alpha)} d_{i,j} in the definition of (digital) higher order sequences cannot grow faster than \alpha m as m \to \infty. The value of \beta must then satisfy that this sum diverges as fast or faster than \beta \sigma m as m \to\infty.

Simplification 1: Assume that \alpha is known

This is not really a simplification of the notation, since it does not have the same level of generality anymore as the above concepts. Nonetheless, this case is valuable since it is much simpler to understand.

So assume now that \alpha is a given number. For digital higher order nets we can set the parameter {}n to \alpha m always if \alpha is known. The same can be done for higher order nets and hence the parameter {}n is not needed in this case. Similarly we can just assume that \sigma=\alpha and hence this parameter is also not needed.

Now consider the parameter \beta. In the general case the situation is the following: First choose a sequence {}S, then choose a value of \alpha and \sigma and then find out what are the parameters t,\beta such that {}S is a (t,\alpha,\beta,\sigma,s)-sequence. But now the situation is different. We can now first fix \alpha and then choose a sequence {}S which is good for the given value of \alpha. The important point is that, using for instance the construction from [1], we know that there exists a sequence {}S for which we can choose \beta, \sigma such that \beta \sigma = \alpha. Sequences for which we cannot choose \beta \sigma = \alpha are not really of interest since they do not yield the optimal rate of convergence (notice that \alpha > \beta \sigma is not possible, see [Theorem 4, 2]. Hence we can restrict ourselves to sequences for which \beta \sigma =\alpha. In fact, we can simply choose \beta=1 and \alpha = \sigma. With this understanding we do not need to include the parameters \beta,\sigma (in the general case this is not possible, since currently there is no sequence for which \beta \sigma = \alpha for all \alpha). Since we can always choose \beta=1 for sequences, we can do the same for nets. Thus we can set \beta=1, \sigma = \alpha and n=\alpha m for known \alpha.

Thus, in this case we could simply speak of (t,\alpha,m,s)-nets and (t,\alpha,s)-sequences or (digital) order \alpha-nets and (digital) order \alpha-sequences, as suggested by Art.

With our current knowledge, this information is usually sufficient, since known propagation rules provide enough information about the remaining parameters. That is, for arbitrary \alpha^\prime, we can obtain useful values for t(\alpha^\prime), \beta(\alpha^\prime),n,\sigma for (digital) order \alpha nets or (digital) order \alpha sequences for the case when \alpha \neq \alpha^\prime. And this information is competitive with respect to the parameters obtained from the current constructions.

However, this somewhat hides the question whether there are constructions which are better than what can be obtained from the current propagation rules for the cases when \alpha^\prime \textgreater \alpha. In other words, it would be interesting to know whether a sequence exists for which \beta(\alpha) \sigma = \alpha for all \alpha. Currently this is only possible for \alpha in a chosen range.

In the notion of extensibility we can describe this in the following way:

  1. fixed case: \alpha is known and we can define (digital) order \alpha nets and (digital) order \alpha sequences;
  2. finitely extensible case: \alpha unknown and we know higher order nets and sequences which are optimal for all 1 \le \alpha \le \alpha^\prime, where \alpha^\prime is an arbitrarily chosen finite number;
  3. infinitely extensible case: \alpha unknown and we know higher order nets and sequences which are optimal for all \alpha \in \mathbb{N};

Because of the known propagation rules, for some papers which only deal with the first or second case, the notation of (digital) order \alpha nets and (digital) order \alpha sequences can be sufficient. A solution to the third case is currently not known.

Simplification 2: Removing {}n and \sigma

We now go back to the general case where \alpha is not known and consider all the parameters in this setting.

We now provide some definitions which do not include the parameters n and \sigma. Though n has a natural meaning for digital higher order nets (the number of rows of the generating matrices), one could do without specifying it. For sequences on the other hand, one could simply set \sigma:=\alpha in the definition and not mention it as a parameter. In this case the definition could be modified to the following (we only consider the digital case, the other case can be modified analogously).

Defintion [Digital (t,\alpha,\beta, m, s)-net]
Let s,\alpha,m \in \mathbb{N}, let 0 \textless \beta \le 1 be a real number and let 0 \le t \le \alpha m be an integer. Let \mathbb{F}_b be the finite field of order {}b, where {}b is a prime power. Let C_1,\ldots, C_s \in \mathbb{F}_b^{n \times m} (for some integer n) where \boldsymbol{c}_j^{(i)} \in \mathbb{F}_b^m is the {}jth row vector of C_i for 1 \le j \le n and 1 \le i \le s. If for all 1 \le d_{i,\nu_i} \textless \cdots \textless d_{i,1} \le n, with

\displaystyle \sum_{i=1}^s \sum_{j=1}^{\min(\nu_i,\alpha)} d_{i,j} \le \beta \alpha m - t,

the vectors

\displaystyle \boldsymbol{c}^{(1)}_{d_1,\nu_1},\ldots, \boldsymbol{c}^{(1)}_{d_1,1},\ldots, \boldsymbol{c}^{(s)}_{d_s,\nu_s},\ldots, \boldsymbol{c}^{(s)}_{d_s,1}

are linearly independent over \mathbb{F}_b, then the digital net with generating matrices C_1,\ldots, C_s is called a digital (t,\alpha,\beta, m, s)-net over \mathbb{F}_b.

Definition [Digital (t,\alpha,\beta, s)-sequence]
Let s,\alpha, \in \mathbb{N} and t \in \mathbb{N}_0 and let 0 \textless \beta \le 1 be a real number. Let \mathbb{F}_b be the finite field of order {}b, where {}b is a prime power. Let C_1,\ldots, C_s \in \mathbb{F}_b^{\mathbb{N} \times \mathbb{N}}, where \boldsymbol{c}^{(i)}_j \in \mathbb{F}_b^{\mathbb{N}} is the {}jth row vector of the matrix C_i for j \in \mathbb{N} and 1 \le i \le s. Further let C_i^{(\alpha m \times m)} denote the left upper \alpha m \times m submatrix of C_i for 1 \le i \le s. If for all m \textgreater t/(\beta \alpha) the matrices C_1^{(\alpha m \times m)},\ldots, C_s^{(\alpha m \times m)} generate a digital (t, \alpha,\beta, m, s)-net over \mathbb{F}_b, then the digital sequence with generating matrices C_1,\ldots, C_s is a digital (t, \alpha,\beta, s)-sequence over \mathbb{F}_b.

This is also a possible definition. It does however hide the dependence of the convergence rate on the number n. For instance consider the following result, first stated with the usual definition and then with the simplified definition:

  1. the convergence rate of the integration error using a digital (t,\alpha,\beta,n \times m,s)-net cannot, in general, be asymptotically smaller than b^{-n}.
  2. the convergence rate of the integration error using a digital (t,\alpha,\beta,m,s)-net with generating matrices C_1,\ldots, C_s \in \mathbb{F}_b^{n \times m} cannot, in general, be asymptotically smaller than b^{-n}.

I believe the first version is somewhat simpler, since {}n is included as a parameter. This is to illustrate the motivation for including {}n as a parameter. Similarly, some propagation rules also benefit from including the parameter {}n. To summarize, yes one can do without specifying {}n, but in some instances it is easier if it is included in the notation.

The motivation for including \sigma is principle 3, but \sigma could reasonably be left out. The reason for writing (t,\alpha,\beta, n \times m,s)-nets for higher order nets is guiding principle 1. The case for higher order sequences also follows from the guiding principles.

Simplification 3: Removing \beta?

Now we turn to \beta. This parameter is important for higher order sequences and is included in higher order nets because of guiding principle 3. So let us discuss the meaning of \beta for higher order sequences. The important higher order sequences are those for which \alpha = \beta \sigma, see [page 15, 2] for more information. Now \beta depends on \alpha and \sigma is a parameter which can be chosen independent of \alpha. Currently there is no higher order sequence known for which \alpha = \beta(\alpha) \sigma for all \alpha \ge 1. For the constructions currently known we only have \alpha = \beta(\alpha) \sigma for all 1 \le \alpha \le \alpha^\prime for some finite and arbitrarily chosen \alpha^\prime. Currently there is no sequence known for which \beta(\alpha) \sigma = \alpha for all \alpha \ge 1. Currently the best known sequences have parameters of the form

\displaystyle \beta \sigma = \left\{\begin{array}{rl} \alpha & \mbox{for } 1 \le \alpha \le \alpha^\prime, \\ & \\ \alpha^\prime & \mbox{for } \alpha \textgreater \alpha^\prime. \end{array} \right.

for some arbitrary but fixed \alpha^\prime \in \mathbb{N}. If there would be explicit constructions of higher order sequences for which \alpha = \beta \sigma for all \alpha \in \mathbb{N}, then the parameter \beta would be redundant. As long as this is not the case, the parameter \beta is important when \alpha is not known.

For (digital) higher order nets, the parameter \beta is included because of guiding principle 4.

Conclusion

To conclude, yes, some simplifications of the notation for (digital) higher order nets and sequences are possible and make sense in certain situations. Especially the assumption that \alpha is known simplifies the notation considerably. If \alpha is not known then one could do without \sigma and to some extend {}n. Still I believe that it is useful to adhere to the guiding principles to keep the notation consistent with each other. Comments are welcome.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s