# 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 ${}j$th 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 ${}j$th 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 ${}j$th 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 ${}j$th 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.