Duality Theory and Propagation Rules for Higher Order Nets

We (J. Baldeaux, J.D., F. Pillichshammer) just submitted a manuscript on Duality Theory and Propagation Rules for Higher Order Nets (you can download the manuscript by clicking on the title). In a nutshell, propagation rules are methods to construct, from given nets with some given parameters, new nets with at least one parameter different from the given nets. Duality theory on the other hand is the vehicle which allows us to analyse those propagation rules. It is an analytic description (using Walsh functions in our case) of the geometric properties of nets.

The manuscript is a continuation of the paper with P. Kritzer on Duality Theory and Propagation Rules for Generalized Digital Nets [44]. (Note that in some papers the notion `generalized (digital) net’ was used instead of the term `(digital) higher order net’.) The difference is that we do not assume that the point sets are constructed by the digital construction scheme.

Most propagation rules for classical {(t,m,s)}-nets have a higher order analogue. This applies to digital as well as geometric nets. Additionally there are also some further propagation rules which do not exist for classical nets (for example the higher order to higher order construction). The higher order to higher order propagation rule is, as of now, still the only method to obtain higher order nets from classical nets. Fortunately it works in the digital as well as geometric case.

1. A subnet propagation rule for digital higher order nets

We give an example of a propagation rule in the following. In the classical case there is a propagation rule which states that:

  • If there exists a (digital) {(t,m,s)}-net in base {b} (over {\mathbb{F}_b}), then for any {t \le m^\prime \le m} there exists a (digital) {(t,m^\prime,s)}-net in base {b} (over {\mathbb{F}_b}).

A reference to the original result and the proof of this statement can be found in the book [B1], Lemma 4.17 on page 138 for the geometric case and Theorem 4.60 on page 173 for the digital case.

Let {C_1, \ldots, C_s \in \mathbb{F}_b^{\alpha m \times m}} be the generating matrices of a digital higher order net in the sense of Definition 4.3 in [31].

Definition 1 Let {n, m,\alpha \ge 1} be natural numbers, let {0 <\beta \le \min(1,\alpha m/n)} be a real number and let {0 \le t \le \beta n} be a natural number. Let {\mathbb{F}_b} be the finite field of order {b} and let {C_1,\ldots, C_s \in \mathbb{F}_b^{n \times m}} with {C_j = (c_{j,1}, \ldots, c_{j,n})^\top}. If for all {1 \le i_{j,\nu_j} < \cdots < i_{j,1} \le n}, with

\displaystyle \sum_{j = 1}^s \sum_{l=1}^{\min(\nu_j,\alpha)} i_{j,l} \le \beta n - t

the vectors

\displaystyle c_{1,i_{1,\nu_1}}, \ldots, c_{1,i_{1,1}}, \ldots, c_{s,i_{s,\nu_s}}, \ldots, c_{s,i_{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}.

We are interested in cases where {n \ge m}. Informally we refer to such nets as digital higher order nets.

We now want to show that the subnet propagation rule applies for digital {(t, \alpha, \beta, n ,m,s)}-nets with generating matrices {C_1,\ldots, C_s \in \mathbb{F}_b^{n \times m}}. First note that Lemma 4.61, p. 173 in the book [B1], applies also for digital higher order nets.

Lemma 4.62 does not apply directly since it demands that the first {m} rows of the generating matrices {C_1, \ldots, C_s} are linearly independent. This is not necessarily true and, as in the classical case, one cannot easily make the first {m} rows linearly independent.

Let {C_1,\ldots,C_s \in \mathbb{F}_b^{n \times m}} be the generating matrices of a digital {(t,\alpha,\beta, n \times m, s)}-net. We can apply Theorem 4.11 in [31] for each generating matrix {C_i} individually. We have that each {C_i} generates a digital {(t, \alpha, \beta, n \times m,1)}-net.

Let {e_i} be the largest integer such that the first {e_i} rows of {C_i} are linearly independent and let {e = \max_{1 \le i \le s} e_i}. Let {f} be the largest integer such that for {i_k = f-(k-1)} with {1 \le k \le e} we have

\displaystyle i_1 + \cdots + i_\alpha = \alpha i_1 - 1 - \cdots - (\alpha-1) = \alpha f - \frac{\alpha(\alpha-1)}{2} \le \beta n - t.

From this we obtain

\displaystyle f = \left \lfloor \frac{\beta n - t}{\alpha} + \frac{\alpha-1}{2} \right\rfloor.

By the linear independence property of Definition 1 it follows that the first {f} rows of {C_i} are linearly independent. Hence the generating matrices {C_1, \ldots, C_s} of a digital {(t,\alpha, \beta, n \times m, s)}-net each satisfy that the first {f} rows are linearly independent. Hence

\displaystyle e \ge \left \lfloor \frac{\beta n - t}{\alpha} + \frac{\alpha-1}{2} \right\rfloor.

Lemma 2 Let {C_1, \ldots, C_s \in \mathbb{F}_b^{n \times m}} be the generating matrices of a digital {(t,\alpha,\beta, n \times m, s)}-net over {\mathbb{F}_b^{n \times m}}. Let {e_i} denote the largest integer such that the first {e_i} rows of {C_i} are linearly independent and let {e = \max_{1\le i \le s} e_i}. Then

\displaystyle e \ge \left \lfloor \frac{\beta n - t}{\alpha} + \frac{\alpha-1}{2} \right\rfloor.

If one uses the construction of [31] based on a digital {(0,m,s\alpha)}-net, then the generating matrices obtained this way satisfy {e=m}. In fact, it suffices if the projection onto the first {\alpha} coordinates of the underlying classical digital net have {t = 0}, since then {e_1 = m} and therefore {e = m}.

Let {C_1, \ldots, C_s \in \mathbb{F}_b^{n \times m}} be the generating matrices of a digital {(t,\alpha,\beta, n \times m, s)}-net over {\mathbb{F}_b^{n \times m}}. Assume that the first {e} rows of {C_s} are linearly independent. Then we can multiply {C_1,\ldots, C_s} with a matrix {Z}, {C^\prime_i = C_i Z}, such that the first {e} rows of {C^\prime_s = (c^{(s)}_1, \ldots, c^{(s)}_n)^\top} are given by {c^{(s)}_1 = (0,\ldots, 0, 1)^\top \in \mathbb{F}_b^m}, {c^{(s)}_2 = (0, \ldots, 0, 1,0)^\top \in \mathbb{F}_b^m}, and so on.

Let {m \ge m^\prime \ge m-e} and let {D_i} be the left upper {(n-m+m^\prime) \times m^\prime} submatrix of {C_i} for {1 \le i < s} and {D_s} be the left lower {(n-m+ m^\prime) \times m^\prime} submatrix of {C_s}. We have the following theorem.

Theorem 3 Let {C_1,\ldots, C_s \in\mathbb{F}_b^{m \times m}} be the generating matrices of a digital {(t,\alpha,\beta, n \times m, s)}-net over {\mathbb{F}_b} where {n \ge m}. Assume that the first {e} rows of {C_s} are linearly independent. Let {m \ge m^\prime \ge m-e} be an integer and define {D_1,\ldots, D_s \in \mathbb{F}_b^{(n-m+m^\prime) \times m^\prime}} as above. Then {D_1,\ldots, D_s} generate a digital {(t^\prime, \alpha, \beta, (n-m+m^\prime) \times m^\prime, s)}-net over {\mathbb{F}_b} where

\displaystyle t^\prime \le t + (\alpha-\beta) (m-m^\prime).

Proof: The proof follows along the same lines as the proof of Theorem 4.60, p. 174, in the book [B1]. We choose {n - m^\prime \ge i_{j,1} > \ldots > i_{j,\nu_j} \ge 1} for {j = 1,\ldots, s} such that

\displaystyle \sum_{j=1}^s \sum_{k=1}^{\min(\alpha,\nu_j)} i_{j,k} \le \beta n - \alpha (m-m^\prime)-t. \ \ \ \ \ (1)

We need to show that the rows of {D_1,\ldots, D_s} corresponding to the {i_{j,k}} as in Definition 1 are linearly independent.

Arrange the rows of {C^\prime_1,\ldots, C^\prime_s}, where {C^\prime_i = C_i Z}, with the left part being the rows of {D_1,\ldots, D_s} apart from the rows of zeroes, as in the proof of Theorem 4.60. For {j = 1, \ldots, s-1} and {1 \le k \le \nu_j} let {i_{j,k}^\prime = i_{j,k}}. For {\nu_s > 0} let {i_{s,k}^\prime = i_{s,k} + m-m^\prime} for {1 \le k \le \nu_s} and {i_{s,k}^\prime = i_{s,\nu_s}+(m-m^\prime)-(k-\nu_s)} for {\nu_s < k \le \nu_s-1+i_{s,\nu_s}+m-m^\prime}. For {\nu_s = 0} let {i_{s,k}^\prime = m-m^\prime-(k-1)} for {1 \le k \le m-m^\prime}. Let {\nu_s^\prime = \nu_s} if {\nu_s \ge \alpha} and let {\nu_s^\prime = \nu_s + m - m^\prime} if {0 \le \nu_s < \alpha}.

Then, the digital {(t,\alpha,\beta, n \times m, s)}-net property of the digital higher order net with generating matrices {C^\prime_1,\ldots, C^\prime_s} implies that the rows corresponding to {i^\prime_{j,k}} are linearly independent whenever

\displaystyle \sum_{j=1}^{s-1} \sum_{k=1}^{\min(\alpha, \nu_j)} i^\prime_{j,k} + \sum_{k=1}^{\min(\alpha, \nu^\prime_s)} i^\prime_{s,k} \le \beta n - t. \ \ \ \ \ (2)

When the rows of {C^\prime_1,\ldots, C^\prime_s} corresponding to {i^\prime_{j,k}} are linearly independent, then the rows of {D_1,\ldots, D_s} corresponding to {i_{j,k}} are linearly independent. Hence it suffices to show that (2) holds.

Equation (1) implies that

\displaystyle \beta n - t \ge \sum_{j=1}^s \sum_{k=1}^{\min(\alpha,\nu_j)} i_{j,k} + \alpha (m-m^\prime) \ge \sum_{j=1}^{s-1} \sum_{k=1}^{\min(\alpha, \nu_j)} i^\prime_{j,k} + \sum_{k=1}^{\min(\alpha, \nu^\prime_s)} i^\prime_{s,k}.

Hence the corresponding rows of {D_1,\ldots, D_s} are linearly independent and therefore the result follows. \Box

Theorem 3 implies the classical case where {\alpha = \beta = 1} and {n = m}, since there we can assume that {e = m}. (Note that if {m^\prime < t} we obtain a {(m^\prime,m^\prime,s)}-net, which always holds.)

For small {m^\prime} the result only shows that {t^\prime \le \beta (n-m+m^\prime)}. This happens if {m^\prime \le m - \frac{\beta n - t}{\alpha}}. Hence Theorem 3 is only useful if

\displaystyle m^\prime > m- \frac{\beta n-t}{\alpha}.

On the other hand, Lemma 2 implies that

\displaystyle m-e \le m - \frac{\beta n-t}{\alpha} - \frac{\alpha-1}{2} + \frac{\alpha-1}{\alpha} \le m - \frac{\beta n - t}{\alpha}.

Hence Theorem 3 covers all relevant cases.

Corollary 4 (Propagation Rule XV) Let {C_1,\ldots, C_s \in\mathbb{F}_b^{m \times m}} be the generating matrices of a digital {(t,\alpha,\beta, n \times m, s)}-net over {\mathbb{F}_b} where {n \ge m}. Let {m \ge m^\prime > m - (\beta n - t)/\alpha} be an integer and define {D_1,\ldots, D_s \in \mathbb{F}_b^{(n-m+m^\prime) \times m^\prime}} as above. Then {D_1,\ldots, D_s} generate a digital {(t^\prime, \alpha, \beta, (n-m+m^\prime) \times m^\prime, s)}-net over {\mathbb{F}_b} where

\displaystyle t^\prime = t + \lfloor (\alpha-\beta) (m-m^\prime)\rfloor.

Advertisements

One response to “Duality Theory and Propagation Rules for Higher Order Nets

  1. Pingback: Construction Algorithms for Higher Order Polynomial Lattice Rules « Quasi-Random Ideas. By Josef Dick.

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