# A Construction of Polynomial Lattice Rules with Small Gain Coefficients

Recently J. Baldeaux and myself submitted the manuscript titled A Construction of Polynomial Lattice Rules with Small Gain Coefficients.

In this paper we construct polynomial lattice rules which have, in some sense, small gain coefficients using a component-by-component approach. The gain coefficients, as introduced by Art Owen, indicate to what degree the method improves upon Monte Carlo. We show that the variance of an estimator based on a scrambled polynomial lattice rule constructed component-by-component decays at a rate of $N^{-(2\alpha + 1) +\delta}$, for all $\delta >0$, assuming that the function under consideration bounded fractional variation of order $\alpha$ and where $N$ denotes the number of quadrature points. We give some further comments on the paper.

Let

$\displaystyle \widehat{I}(f) = \frac{1}{b^m} \sum_{n=0}^{b^m-1} f(\boldsymbol{x}_n),$

where $\boldsymbol{x}_0, \ldots, \boldsymbol{x}_{b^m-1}$ are a randomly scrambled polynomial lattice point set. Since random scrambling yields an unbiased estimator one has

$\displaystyle \mathbb{E}[\widehat{I}(f)] = \int_{[0,1]^s} f(\boldsymbol{x}) \, \mathrm{d} \boldsymbol{x}.$

Hence one considers the variance of the estimator

$\displaystyle \mathrm{Var}[\widehat{I}(f)] = \mathbb{E}[(\widehat{I}(f) - \mathbb{E}[\widehat{I}(f)])^2].$

It is known that

$\displaystyle \mathrm{Var}(\widehat{I}(f)) = \sum_{\emptyset \neq u \subseteq [s]} \frac{b^{|u|}}{(b-1)^{|u|}} \sum_{\boldsymbol{l}_u \in \mathbb{N}^{|u|}} \frac{\sigma^2_{(\boldsymbol{l}_u,\boldsymbol{0})}(f)}{b^{|\boldsymbol{l}_u|_1}} |L_u((\boldsymbol{l}_u,\boldsymbol{0})) \cap \mathcal{D}_p(\boldsymbol{q})| \hspace{1cm} (1)$

The term $\sigma_{(\boldsymbol{l}_u,\boldsymbol{0})}(f)$ depends only on the function $f$, whereas the term $|L_u((\boldsymbol{l}_u,\boldsymbol{0})) \cap \mathcal{D}_p(\boldsymbol{q})|$ depends only on the polynomial lattice (here $\mathcal{D}_p(\boldsymbol{q})$ is the dual lattice which has generating vector $\boldsymbol{q}$ and modulus $p$). We define the function norm

$\displaystyle \|f\|_\alpha = \max_{u \subseteq [s]} \gamma^{-1/2}_u \sup_{\boldsymbol{l}_u \in \mathbb{N}^{|u|}} b^{\alpha |\boldsymbol{l}_u|_1} \sigma_{(\boldsymbol{l}_u,\boldsymbol{0})}(f).$

(We also show that if $f$ has bounded fractional variation of order $\alpha$ then $\|f\|_\alpha < \infty$.) Hence one can estimate

$\displaystyle \sigma_{(\boldsymbol{l}_u,\boldsymbol{0})}(f) \le \gamma_u^{1/2} b^{-\alpha |\boldsymbol{l}_u|_1}.$

Using this bound in Equation (1) one obtains

$\displaystyle \mathrm{Var}[\widehat{I}(f)] \le \|f\|_\alpha \sum_{\emptyset \neq u \subseteq [s]} \frac{b^{|u|}}{(b-1)^{|u|}} \sum_{\boldsymbol{l}_u \in \mathbb{N}^{|u|}} \frac{1}{b^{(2\alpha + 1) |\boldsymbol{l}_u|_1}} |L_{(\boldsymbol{l}_u, \boldsymbol{0})} \cap \mathcal{D}_p(\boldsymbol{q}). \hspace{1cm} (2)$

We show that

$\displaystyle B(\boldsymbol{q}, \alpha, \boldsymbol{\gamma}) := \sum_{\emptyset \neq u \subseteq [s]} \frac{b^{|u|}}{(b-1)^{|u|}} \sum_{\boldsymbol{l}_u \in \mathbb{N}^{|u|}} \frac{1}{b^{(2\alpha + 1) |\boldsymbol{l}_u|_1}} |L_{(\boldsymbol{l}_u, \boldsymbol{0})} \cap \mathcal{D}_p(\boldsymbol{q})$

can be used as quality criterion in a component-by-component construction of polynomial lattices. We need to assume that $0 < \alpha \le 1$, as for $\alpha = 0$ one has $B(\boldsymbol{q}, 0, \boldsymbol{\gamma}) = \infty$. We show that we obtain optimal upper bounds on the variance with this approach. Further, if one constructs a polynomial lattice rule for some $0 < \alpha \le 1$, then this polynomial lattice rule will also be optimal if the function $f$ has smoothness $\alpha^\prime$ with $\alpha \le \alpha^\prime \le 1$. Unfortunately our method can only be used for $\alpha > 0$ and hence the boundary case $\alpha = 0$ is excluded.

It would be interesting to also obtain a result for $\alpha = 0$. One may proceed in the following way. To obtain Equation (2) from Equation (1) we used Hölder's inequality. Hence using Hölder's inequality with different parameters one can obtain a $r$ function norm and bound $B(\boldsymbol{q}, \alpha, \boldsymbol{\gamma})$ in norm $1 - 1/r$. Indeed, if one uses the $1$-norm for $f$ and the $\infty$-norm for $B(\boldsymbol{q}, \alpha, \boldsymbol{\gamma})$ one obtains a function $B(\boldsymbol{q}, \alpha, \boldsymbol{\gamma})$ which is also finite for $\alpha = 0$. One could then use this bound as quality criterion in a component-by-component approach. Although interesting, we did not find a closed form expression for this bound and hence we were not able to use the component-by-component approach. In fact, the only case where we could find a closed form expression for $B(\boldsymbol{q}, \alpha, \boldsymbol{\gamma})$ which we used in the paper and which we outlined above.