Construction of interlaced polynomial lattice rules for infinitely differentiable functions

Abstract

We study multivariate integration over the s-dimensional unit cube in a weighted space of infinitely differentiable functions. It is known from a recent result by Suzuki that there exists a good quasi-Monte Carlo (QMC) rule which achieves a super-polynomial convergence of the worst-case error in this function space, and moreover, that this convergence behavior is independent of the dimension under a certain condition on the weights. In this paper we provide a constructive approach to finding a good QMC rule achieving such a dimension-independent super-polynomial convergence of the worst-case error. Specifically, we prove that interlaced polynomial lattice rules, with an interlacing factor chosen properly depending on the number of points N and the weights, can be constructed using a fast component-by-component algorithm in at most $O(sN(\log N)^2)$ arithmetic operations to achieve a dimension-independent super-polynomial convergence. The key idea for the proof of the worst-case error bound is to use a variant of Jensen’s inequality with a purposely-designed concave function.

1 Introduction

We study the approximation of multivariate integrals of real-valued functions defined over the s-dimensional unit cube $[0,1]^s$,

$$\begin{aligned} I(f) = \int _{[0,1]^s}f(\varvec{x}) \mathrm {d}\varvec{x}. \end{aligned}$$

Quasi-Monte Carlo (QMC) integration approximates I(f) by using a deterministically chosen finite point set $P\subset [0,1]^s$ as

$$\begin{aligned} I(f;P) = \frac{1}{|P|}\sum _{\varvec{x}\in P}f(\varvec{x}) , \end{aligned}$$

where |P| denotes the cardinality of P. Note that we interpret P here as a set in which the multiplicity of elements matters. In order to make the integration error $|I(f;P)-I(f)|$ small for a class of functions f, P needs to be carefully designed depending on the class to which the function f belongs. Digital nets and sequences are a well-known choice for constructing good quadrature points for several classes of functions [10, 20].

A classical criterion for measuring the distribution properties of point sets is the so-called star-discrepancy. The Koksma–Hlawka inequality bounds the integration error using a point set by the star-discrepancy of this point set times the total variation in the sense of Hardy and Krause, see for instance [17, Chapter 2, Section 5]. Thus a low-discrepancy point set of N points yields a small integration error bound, typically of order $N^{-1+\varepsilon }$ with arbitrarily small $\varepsilon >0$, assuming that the function f has bounded total variation in the sense of Hardy and Krause. Regarding explicit constructions of low-discrepancy digital nets and sequences, we refer to [10, Chapter 8] and [20, Chapter 4]. Polynomial lattice point sets, first introduced in [21], are a special construction method for digital nets and have been extensively studied in the literature, see for instance [10, Chapter 10] and [24]. Polynomial lattice rules are QMC rules using a polynomial lattice point set as quadrature points. While we usually resort to some computer search algorithm to find good polynomial lattice rules for $s>2$, the major advantage of polynomial lattice rules lies in their flexibility, that is, we can design a suitable QMC rule for the problem at hand.

In order to achieve a faster convergence of the integration error, explicit constructions of point sets, referred to as higher order digital nets, have been established by Dick [2, 3] which can fully exploit the smoothness of an integrand. Specifically QMC rules using higher order digital nets achieve the optimal convergence rate of the integration error of order $N^{-\alpha +\varepsilon }$ with arbitrarily small $\varepsilon >0$, when the function f has square integrable partial mixed derivatives up to order $\alpha \ge 2$ in each variable. We remark that recent applications in the area of uncertainty quantification, in particular partial differential equations with random coefficients, are in need of using these types of quadrature rules, see for instance [7]. The above result by Dick is based chiefly on analyzing the decay of the Walsh coefficients of smooth functions [3, 4].

Numerical integration of infinitely many times differentiable functions in certain function spaces has recently been considered in [8, 11, 15, 16]. However, the results on higher order digital nets in [2, 3] do not improve if one assumes that the integrand is infinitely many times differentiable. More precisely, if one sets $\alpha = \infty$ in [2, 3] one obtains constants which are infinite and the error bounds become trivial. To improve the error bounds in these papers for function spaces consisting of infinitely many times differentiable functions using higher order digital nets requires new bounds on the Walsh coefficients. Such an analysis of the Walsh coefficients was recently done in [28, 30], where they obtained a space $\mathcal {F}_s$ of infinitely differentiable functions whose Walsh coefficients decay with a certain order. The worst-case error in $\mathcal {F}_s$ by a digital net is closely related to the Walsh figure of merit (WAFOM) introduced in [18, 26], which is one of the computable quality criteria of digital nets, although WAFOM was originally derived in a different way from [28, 30]. Moreover, Suzuki [27] considered a weighted space $\mathcal {F}_{s,\varvec{u}}$ of infinitely differentiable functions and studied tractability of multivariate integration in $\mathcal {F}_{s,\varvec{u}}$, where the positive real numbers $\varvec{u}=(u_j)_{j\in \mathbb {N}}$ are the weights. His result can be summarized as follows: There exists a good QMC rule using a digital net which achieves an super-polynomial convergence of the worst-case error in $\mathcal {F}_{s,\varvec{u}}$ as $C(s)e^{-c(s)(\log N)^2}$, and moreover, the convergence can be independent of the dimension s as $Ce^{-c(\log N)^p}$ for some $1<p<2$ under a certain condition on the weights $\varvec{u}$.

In this paper, beyond the existence result of [27], we provide a constructive approach to finding good QMC rules achieving a dimension-independent super-polynomial convergence of the worst-case error. Specifically we prove that interlaced polynomial lattice rules can be constructed using a fast component-by-component (CBC) algorithm, in at most $O(sN(\log N)^2)$ arithmetic operations, to achieve a dimension-independent super-polynomial convergence. As first studied in [12,13,14], interlaced polynomial lattice rules belong to the family of higher order digital nets and therefore achieve a higher order polynomial convergence of the integration error. We use them as QMC rules achieving a super-polynomial convergence in this paper. For this purpose, we are required to choose an interlacing factor depending on the number of points and the weights, instead of keeping it fixed (as for instance in [2, 3]). Furthermore, in order to show the worst-case error bound with a super-polynomial convergence, we purposely design a concave function to modify Jensen’s inequality which has been often used in the literature to obtain error bounds with an improved rate of convergence.

Our approach requires to set the weights for constructing a tailored QMC rule, as often encountered in this type of construction algorithms. In practical applications, however, it is not always the case where one can know in advance to which function class the functions of interest belong. To work around this drawback, it must be interesting to study whether a good convergence property which such a tailored QMC rule holds for a specific function class can be also established for other function classes, as discussed for instance in [14, Remark 1]. We observe in Sect. 5 that our constructed rules empirically work even for some functions not belonging to the target space. In another direction for constructing a robust QMC rule working for many different function classes, one can implement a more elaborate construction algorithm as given in [5]. However, theoretical analysis of these issues is beyond the scope of this paper and we leave them open for further research.

The remainder of this paper is organized as follows. In the next section, we introduce the necessary background and notation, namely Walsh functions, a weighted space $\mathcal {F}_{s,\varvec{u}}$ of infinitely differentiable functions, our considering super-polynomial convergence and interlaced polynomial lattice rules. We also describe the main results of this paper. Namely, we introduce a component-by-component algorithm, state a result on the convergence behavior of interlaced polynomial lattice rules and discuss the dependence of the worst-case error bound on the dimension. In Sect. 3, we study the worst-case error in $\mathcal {F}_{s,\varvec{u}}$ for QMC rules using a digital net and derive a computable upper bound. We prove in Sect. 4 that the CBC algorithm can be used to obtain good interlaced polynomial lattice rules which achieve a dimension-independent super-polynomial convergence of the worst-case error. Thereafter we describe the fast CBC algorithm using the fast Fourier transform as in [22, 23], and show that interlaced polynomial lattice rules achieving a dimension-independent super-polynomial convergence can be constructed in at most $O(sN(\log N)^2)$ arithmetic operations using O(N) memory. Finally, we conclude this paper with numerical experiments in Sect. 5.

2 Background, notation and results

Throughout this paper, we use the following notation. Let $\mathbb {N}$ be the set of positive integers and let $\mathbb {N}_0{:=}\mathbb {N}\cup \{0\}$. For a positive integer $b\ge 2$, let $\mathbb {Z}_b$ be a finite ring with b elements, which we identify with the set $\{0,1,\dots ,b-1\}$ equipped with addition and multiplication modulo b. For $x\in [0,1)$, we denote its b-adic expansion by $x=\sum _{i=1}^{\infty }\xi _i b^{-i}$ with $\xi _i\in \mathbb {Z}_b$ for all i, which is unique in the sense that infinitely many $\xi _i$ are different from $b-1$. The operators $\oplus$ and $\ominus$ denote digitwise addition and subtraction modulo b, respectively. That is, for $x, x'\in [0,1)$ whose unique b-adic expansions are $x=\sum _{i=1}^{\infty }\xi _i b^{-i}$ and $x'=\sum _{i=1}^{\infty }\xi '_i b^{-i}$, $\oplus$ and $\ominus$ are defined as

$$\begin{aligned} x\oplus x' = \sum _{i=1}^{\infty }\eta _i b^{-i}\quad \text {and}\quad x\ominus x' = \sum _{i=1}^{\infty }\eta '_i b^{-i}, \end{aligned}$$

where $\eta _i=\xi _i+\xi '_i \pmod b$ and $\eta '_i=\xi _i-\xi '_i \pmod b$, respectively. Similarly, we define digitwise addition and subtraction for non-negative integers based on their b-adic expansions. In case of vectors in $[0,1)^s$ or $\mathbb {N}_0^s$, the operators $\oplus$ and $\ominus$ are applied componentwise.

2.1 Walsh functions

Walsh functions were first introduced in [29] for the case $b=2$ and were later generalized to arbitrary base $b \ge 2$, see for instance [1]. We refer to [10, Appendix A] for more information on Walsh functions in the context of numerical integration. We first give the definition for the one-dimensional case.

Definition 1

Let $b\ge 2$ be a positive integer and let $\omega _b{:=}\exp (2\pi \sqrt{-1}/b)$ be a b-th root of unity. We denote the b-adic expansion of $k\in \mathbb {N}_0$ by $k = \kappa _0+\kappa _1b+\dots +\kappa _{a-1}b^{a-1}$ with $\kappa _i\in \mathbb {Z}_b$. The k-th b-adic Walsh function ${}_b\mathrm {wal}_k: [0,1)\rightarrow \{1,\omega _b,\dots ,\omega _b^{b-1}\}$ is defined as

$$\begin{aligned} {}_b\mathrm {wal}_k(x) {:=} \omega _b^{\kappa _0\xi _1+\dots +\kappa _{a-1}\xi _a} , \end{aligned}$$

for $x\in [0,1)$ with its unique b-adic expansion $x=\xi _1b^{-1}+\xi _2b^{-2}+\cdots$.

This definition can be generalized to the higher-dimensional case.

Definition 2

Let $b\ge 2$ be a positive integer. For a dimension $s\in \mathbb {N}$, let $\varvec{x}=(x_1,\ldots , x_s)\in [0,1)^s$ and $\varvec{k}=(k_1,\ldots , k_s)\in \mathbb {N}_0^s$. The $\varvec{k}$-th b-adic Walsh function ${}_b\mathrm {wal}_{\varvec{k}}: [0,1)^s \rightarrow \{1,\omega _b,\ldots , \omega _b^{b-1}\}$ is defined as

$$\begin{aligned} {}_b\mathrm {wal}_{\varvec{k}}(\varvec{x}) {:=} \prod _{j=1}^s {}_b\mathrm {wal}_{k_j}(x_j) . \end{aligned}$$

Since we always use Walsh functions in a fixed base b, we omit the subscript and simply write $\mathrm {wal}_k$ or $\mathrm {wal}_{\varvec{k}}$ in the remainder of this paper. From the fact that the system $\{\mathrm {wal}_{\varvec{k}}: \varvec{k}\in \mathbb {N}_0^s\}$ is a complete orthonormal system in $L_2([0,1]^s)$ for any $s\in \mathbb {N}$ [10, Theorem A.11], we have a Walsh series expansion for any $f\in L_2([0,1]^s)$

$$\begin{aligned} \sum _{\varvec{k}\in \mathbb {N}_0^s}\hat{f}(\varvec{k})\mathrm {wal}_{\varvec{k}} , \end{aligned}$$

where $\hat{f}(\varvec{k})$ denotes the $\varvec{k}$-th Walsh coefficient of f, which is defined as

$$\begin{aligned} \hat{f}(\varvec{k}) {:=} \int _{[0,1]^s}f(\varvec{x})\overline{\mathrm {wal}_{\varvec{k}}(\varvec{x})}\mathrm {d}\varvec{x}. \end{aligned}$$

For continuous functions $f: [0,1]^s\rightarrow \mathbb {R}$ for which $\sum _{\varvec{k}\in \mathbb {N}_0^s}|\hat{f}(\varvec{k})|<\infty$, the Walsh series of f converges to f pointwise absolutely. In fact, for any function $f : [0,1]^s \rightarrow \mathbb {R}$ in a weighted space $\mathcal {F}_{s,\varvec{u}}$ which we consider in this paper, its Walsh series converges to f pointwise absolutely.

2.2 Weighted function space $\mathcal {F}_{s,\varvec{u}}$

We first define the function $\mu (a;\cdot ) : \mathbb {N}_0\rightarrow \mathbb {R}$ for a real number a.

Definition 3

Let a be a real number. For $k\in \mathbb {N}$, we denote its b-adic expansion by $k = \kappa _1 b^{c_1-1}+\kappa _2 b^{c_2-1}+\cdots +\kappa _v b^{c_v-1}$ such that $\kappa _1,\dots ,\kappa _v \in \{1,2,\dots ,b-1\}$ and $c_1>\ldots> c_v >0$. The function $\mu (a;\cdot ) : \mathbb {N}_0\rightarrow \mathbb {R}$ is defined as

$$\begin{aligned} \mu (a;k) {:=} \sum _{i=1}^{v}(c_i+a) , \end{aligned}$$

(1)

and $\mu (a;0){:=}0$.

Remark 1

Let us consider the case $a=0$. If the sum on the right-hand side of (1) which runs over $i=1,\dots ,v$ is replaced by the sum which runs over $i=1,\dots ,\min (\alpha ,v)$ for a fixed $\alpha \in \mathbb {N}$, we recover the definitions by Niederreiter, Rosenbloom and Tsfasman in [19, 25] for $\alpha =1$ and by Dick in [3] for $\alpha \ge 2$. Our function $\mu _a$ with $a=0$ has been used in [18, 26]. The parameter a was included in the definition originally by Yoshiki [30] for $a=1$ and later by Suzuki [27] for an arbitrary real number a.

For the higher-dimensional case, we consider a vector of s real numbers $\varvec{a}=(a_1,\dots ,a_s)$ and define the function $\mu (\varvec{a};\cdot ): \mathbb {N}_0^s\rightarrow \mathbb {R}$ as follows.

Definition 4

Let $\varvec{a}=(a_1,\dots ,a_s)$ be a vector of s real numbers, and let $\varvec{k}=(k_1,\dots ,k_s)\in \mathbb {N}_0^s$. The function $\mu (\varvec{a};\cdot ): \mathbb {N}_0^s\rightarrow \mathbb {R}$ is defined as

$$\begin{aligned} \mu (\varvec{a};\varvec{k}) {:=} \sum _{j=1}^{s}\mu (a_j;k_j) . \end{aligned}$$

We are now ready to introduce a weighted space $\mathcal {F}_{s,\varvec{u}}$ of infinitely differentiable functions. Let $\varvec{u}=(u_j)_{j\in \mathbb {N}}$ be a sequence of positive real numbers which we call weights, and we assume that $u_1\ge u_2\ge \cdots >0$ throughout this paper.

Definition 5

Let $\varvec{u}=(u_j)_{j\in \mathbb {N}}$ be a sequence of weights. We define a weighted space $\mathcal {F}_{s,\varvec{u}}$ as

$$\begin{aligned} {\mathcal {F}}_{s,\varvec{u}} {:=} \left\{ f\in C^{\infty }([0,1]^s) : ||f||_{{\mathcal {F}}_{s,\varvec{u}}} {:=} \sup _{(\alpha _1,\ldots ,\alpha _s)\in \mathbb {N}_0^s}\frac{||f^{(\alpha _1,\ldots ,\alpha _s)}||_{L^1}}{\prod _{j=1}^{s}u_j^{\alpha _j}}<\infty \right\} , \end{aligned}$$

where $f^{(\alpha _1,\ldots ,\alpha _s)}$ denotes the $(\alpha _1,\ldots ,\alpha _s)$-th mixed partial derivative of f, i.e., $(\partial /\partial x_1)^{\alpha _1} \cdots (\partial /\partial x_s)^{\alpha _s}f$.

In the function space ${\mathcal {F}}_{s,\varvec{u}}$, $u_j$ small means that higher order partial mixed derivatives associated with the j-th coordinate must be relatively small. Thus, the weights $\varvec{u}$ play a role in moderating the importance of different variables. Owing to the refined analyses of the Walsh coefficients in [28, 30], it was shown that the Walsh coefficients of any function in $\mathcal {F}_{s,\varvec{u}}$ decay with a certain order, as we describe in the following. Let

$$\begin{aligned} m_b {:=} \min _{c=1,2,\dots ,b-1}|1-\overline{\omega _b}^{c}| = 2\sin (\pi /b), \end{aligned}$$

and

$$\begin{aligned} M_b {:=} \max _{c=1,2,\dots ,b-1}|1-\overline{\omega _b}^{c}| = {\left\{ \begin{array}{ll} 2 &{}\quad \text {if } b \text { is even}, \\ 2\sin ((b+1)\pi /2b) &{}\quad \text {if } b \text { is odd.} \end{array}\right. } \end{aligned}$$

Moreover, let

$$\begin{aligned} C_b = {\left\{ \begin{array}{ll} 2 &{}\quad \text {if } b=2, \\ M_b+\frac{bm_b}{b-M_b} &{}\quad \text {if } b\ne 2. \end{array}\right. } \end{aligned}$$

Then we have the following.

Proposition 1

[28, 30] Let $\varvec{u}=(u_j)_{j\in \mathbb {N}}$ be a sequence of weights, and let $m_b$ and $C_b$ be constants depending only on b as above. For any function f in $\mathcal {F}_{s,\varvec{u}}$ and $\varvec{k}\in \mathbb {N}_0^s$, the $\varvec{k}$-th Walsh coefficient of f is bounded by

$$\begin{aligned} |\hat{f}(\varvec{k})| \le ||f||_{{\mathcal {F}}_{s,\varvec{u}}} b^{-\mu (\varvec{a};\varvec{k})} , \end{aligned}$$

where $\varvec{a}=(a_j)_{j\in \mathbb {N}}$ is a sequence given by $a_j = -\log _b( C_b m_b^{-1} u_j)$ for all $j = 1, \ldots , s$.

2.3 Super-polynomial convergence

From [27], it is known that there exists a good QMC rule which achieves a dimension-independent super-polynomial convergence of the worst-case error in $\mathcal {F}_{s,\varvec{u}}$ under a certain condition on the weights $\varvec{u}$. Here we briefly recall the result of [27].

The initial error in $\mathcal {F}_{s,\varvec{u}}$ is given by the error of the zero algorithm, i.e.,

$$\begin{aligned} e^{\mathrm {wor}}(\mathcal {F}_{s,\varvec{u}};\emptyset ) = \sup _{\begin{array}{c} f\in \mathcal {F}_{s,\varvec{u}}\\ ||f||_{\mathcal {F}_{s,\varvec{u}}}\le 1 \end{array}}\left| I(f)\right| , \end{aligned}$$

which indeed equals 1 for any s and $\varvec{u}$. Hence the integration problem in $\mathcal {F}_{s,\varvec{u}}$ is well normalized. The worst-case error in $\mathcal {F}_{s,\varvec{u}}$ for a QMC rule using a point set P is defined as

$$\begin{aligned} e^{\mathrm {wor}}(\mathcal {F}_{s,\varvec{u}};P) = \sup _{\begin{array}{c} f\in \mathcal {F}_{s,\varvec{u}}\\ ||f||_{\mathcal {F}_{s,\varvec{u}}}\le 1 \end{array}}\left| I(f;P)-I(f)\right| . \end{aligned}$$

We are interested in a dimension-independent super-polynomial convergence of the worst-case error of the form

$$\begin{aligned} e^{\mathrm {wor}}(\mathcal {F}_{s,\varvec{u}};P) \le C e^{-c (\log {n})^{p}} \qquad \text {for all } n, s \in \mathbb {N}, \end{aligned}$$

(2)

where C and c are positive constants independent of n and s. The following existence result is from [27].

Theorem 1

[27] Consider the integration problem in the weighted function space $\mathcal {F}_{s,\varvec{u}}$ for a sequence of weights $\varvec{u}$. If $\varvec{u}$ satisfies $\liminf _{j\rightarrow \infty }\log (u_j^{-1})/j^r>0$ for $r>0$, then there exists a QMC rule which achieves a dimension-independent super-polynomial convergence of the worst-case error in $\mathcal {F}_{s,\varvec{u}}$ as (2) with $p=(2r+1)/(r+1)$.

2.4 Interlaced polynomial lattice rules

Here we give the definition of interlaced polynomial lattice rules, which are based on polynomial lattice rules, introduced by Niederreiter [21], and a digit interlacing composition, introduced by Dick [2, 3].

We first introduce polynomial lattice rules. In this subsection, let b be a prime number, and let $\mathbb {Z}_b$ be the finite field with b elements. We denote by $\mathbb {Z}_b[x]$ the set of all polynomials over $\mathbb {Z}_b$, and denote by $\mathbb {Z}_b((x^{-1}))$ the field of formal Laurent series over $\mathbb {Z}_b$. Every element of $\mathbb {Z}_b((x^{-1}))$ can be represented as

$$\begin{aligned} L = \sum _{l=w}^{\infty }t_l x^{-l} , \end{aligned}$$

for some integer w and $t_l\in \mathbb {Z}_b$ for all l. For a given integer m, we define the mapping $v_m$ from $\mathbb {Z}_b((x^{-1}))$ to the interval [0, 1) by

$$\begin{aligned} v_m\left( \sum _{l=w}^{\infty }t_l x^{-l} \right) =\sum _{l=\max (1,w)}^{m}t_l b^{-l}. \end{aligned}$$

A non-negative integer k whose b-adic expansion is given by $k=\kappa _0+\kappa _1 b+\cdots +\kappa _{a-1} b^{a-1}$ will be identified with the polynomial $k(x)=\kappa _0+\kappa _1 x+\cdots +\kappa _{a-1} x^{a-1}\in \mathbb {Z}_b[x]$. For $\varvec{k}=(k_1,\ldots , k_s)\in (\mathbb {Z}_b[x])^s$ and $\varvec{q}=(q_1,\ldots , q_s)\in (\mathbb {Z}_b[x])^s$, we define the inner product as

$$\begin{aligned} \varvec{k}\cdot \varvec{q}{:=} \sum _{j=1}^{s}k_j q_j \in \mathbb {Z}_b[x] , \end{aligned}$$

(3)

and we write $q\equiv 0 \pmod p$ if p divides q in $\mathbb {Z}_b[x]$. Using this notation, polynomial lattice rules are constructed as follows.

Definition 6

Let $m, s \in \mathbb {N}$. Let $p \in \mathbb {Z}_b[x]$ such that $\deg (p)=m$ and let $\varvec{q}=(q_1,\ldots ,q_s) \in (\mathbb {Z}_b[x])^s$. A polynomial lattice point set $P(\varvec{q},p)$ is a set consisting of $b^m$ points $\varvec{x}_0,\ldots ,\varvec{x}_{b^m-1}$ that are defined as

$$\begin{aligned} \varvec{x}_n {:=} \left( v_m\left( \frac{n(x)q_1(x)}{p(x)} \right) , \ldots , v_m\left( \frac{n(x)q_s(x)}{p(x)} \right) \right) \in [0,1)^s , \end{aligned}$$

for $0\le n<b^m$. A QMC rule using this point set is called a polynomial lattice rule with generating vector $\varvec{q}$ and modulus p.

We add one more notation and introduce the concept of the so-called dual polynomial lattice of a polynomial lattice point set. For $k\in \mathbb {N}_0$ with its b-adic expansion $k= \kappa _0 + \kappa _1 b+\cdots + \kappa _{a-1} b^{a-1}$, let $\mathrm {tr}_m(k)$ be the polynomial of degree at most m obtained by truncating the associated polynomial $k(x)\in \mathbb {Z}_b[x]$ as

$$\begin{aligned} \mathrm {tr}_m(k)= \kappa _0 + \kappa _1 x+\cdots + \kappa _{m-1}x^{m-1}, \end{aligned}$$

where we set $\kappa _{a} = \cdots = \kappa _{m-1} = 0$ if $a< m$. For a vector $\varvec{k}=(k_1,\ldots , k_s)\in \mathbb {N}_0^s$, we define $\mathrm {tr}_m(\varvec{k})=(\mathrm {tr}_m(k_1),\ldots , \mathrm {tr}_m(k_s))$. With this notation, we introduce the following definition of the dual polynomial lattice $P^{\perp }(\varvec{q},p)$.

Definition 7

The dual polynomial lattice of a polynomial lattice point set with modulus $p\in \mathbb {Z}_b[x]$, $\deg (p)=m$, and generating vector $\varvec{q}\in (\mathbb {Z}_b[x])^s$ is given by

$$\begin{aligned} P^{\perp }(\varvec{q},p) = \{ \varvec{k}\in \mathbb {N}_0^s:\ \mathrm {tr}_m(\varvec{k})\cdot \varvec{q}\equiv 0 \pmod p \} , \end{aligned}$$

where the inner product is in the sense of (3).

The following important lemma relates the dual polynomial lattice to numerical integration of Walsh functions, see [10, Lemmas 4.75 and 10.6] for the proof.

Lemma 1

Let $P(\varvec{q},p)=\{\varvec{x}_0,\varvec{x}_1,\dots ,\varvec{x}_{b^m-1}\}\subset [0,1)^{s}$ be a polynomial lattice point set with modulus $p\in \mathbb {Z}_b[x]$, $\deg (p)=m$, and generating vector $\varvec{q}\in (\mathbb {Z}_b[x])^s$, and let $P^{\perp }(\varvec{q},p)$ be its dual polynomial lattice. Then we have

$$\begin{aligned} \frac{1}{b^m}\sum _{n=0}^{b^m-1}\mathrm {wal}_{\varvec{k}}(\varvec{x}_n)= {\left\{ \begin{array}{ll} 1 &{}\quad \text {if } \varvec{k}\in P^{\perp }(\varvec{q},p), \\ 0 &{}\quad \text {otherwise.} \\ \end{array}\right. } \end{aligned}$$

We introduce the digit interlacing composition next. Let d be a positive integer called interlacing factor, and let $\varvec{x}=(x_1,\ldots ,x_d)$ be a generic point in $[0,1)^d$ whose unique b-adic expansions are given by $x_j=\sum _{i=1}^{\infty }\xi _{i,j} b^{-i}$. Then the digit interlacing function $\mathcal {D}_d: [0,1)^d \rightarrow [0,1)$ is defined as

$$\begin{aligned} \mathcal {D}_d(\varvec{x}) {:=} \sum _{i=1}^{\infty }\sum _{j=1}^{d}\xi _{i,j}b^{-d(i-1)-j}. \end{aligned}$$

We also define such a function for ds-dimensional vectors $\varvec{x}=(x_1,\ldots ,x_{ds})$ by applying $\mathcal {D}_d$ to every consecutive d components, that is,

$$\begin{aligned} \mathcal {D}_d(\varvec{x}) {:=} \left( \mathcal {D}_d(x_1,\dots ,x_d), \mathcal {D}_d(x_{d+1},\dots ,x_{2d}), \ldots , \mathcal {D}_d(x_{d(s-1)+1},\dots ,x_{ds})\right) . \end{aligned}$$

Now we are ready to introduce the definition of interlaced polynomial lattice rules [12,13,14].

Definition 8

Let $m,s,d \in \mathbb {N}$. Let $p \in \mathbb {Z}_b[x]$ such that $\deg (p)=m$ and let $\varvec{q}=(q_1,\ldots ,q_{ds}) \in (\mathbb {Z}_b[x])^{ds}$. An interlaced polynomial lattice point set $\mathcal {D}_d(P(\varvec{q},p))$ of order d is a set consisting of $b^m$ points defined as

$$\begin{aligned} \mathcal {D}_d(P(\varvec{q},p)) {:=} \left\{ \mathcal {D}_d(\varvec{x}) : \varvec{x}\in P(\varvec{q},p) \right\} . \end{aligned}$$

A QMC rule using this point set is called an interlaced polynomial lattice rule of order d with generating vector $\varvec{q}$ and modulus p.

2.5 The results

We now describe the main results of this paper. In the following, let b be a prime number and let $m,s,d\in \mathbb {N}$. For $p \in \mathbb {Z}_b[x]$ with $\deg (p)=m$ and $\varvec{q}=(q_1,\ldots ,q_{ds}) \in (\mathbb {Z}_b[x])^{ds}$, we denote the polynomial lattice point set by $P(\varvec{q},p)=\{\varvec{x}_0,\dots ,\varvec{x}_{b^m-1}\}\subset [0,1)^{ds}$ with $\varvec{x}_n=(x_{n,1},x_{n,2},\dots ,x_{n,ds})$, and denote the b-adic expansion of $x_{n,j}$ by $x_{n,j}=\sum _{i=1}^{\infty }\xi _{i,n,j} b^{-i}$ for $0\le n<b^m$ and $1\le j\le ds$. Moreover, we denote the interlaced polynomial lattice point set by $\mathcal {D}_d(P(\varvec{q},p))=\{\varvec{y}_0,\dots ,\varvec{y}_{b^m-1}\}\subset [0,1)^{s}$, where $\varvec{y}_n=\mathcal {D}_d(\varvec{x}_n)$ for $0\le n<b^m$.

Let $\varvec{u}$ be a sequence of weights, and as in Proposition 1, let $\varvec{a}= (a_j)_{j\in \mathbb {N}}$ be the sequence given by

$$\begin{aligned} a_j = -\log _b( C_b m_b^{-1} u_j), \quad j \in \mathbb {N}. \end{aligned}$$

In Sect. 3, we show that the worst-case error in $\mathcal {F}_{s,\varvec{u}}$ by a QMC rule using $\mathcal {D}_d(P(\varvec{q},p))$ as quadrature points is bounded by

$$\begin{aligned} e^{\mathrm {wor}}(\mathcal {F}_{s,\varvec{u}};\mathcal {D}_d(P(\varvec{q},p))) \le C_{\varvec{u}}-1+C_{\varvec{u}}B_{\varvec{u}}(\varvec{q},p) , \end{aligned}$$

where $C_{\varvec{u}}$ and $B_{\varvec{u}}(\varvec{q},p)$ are given by

$$\begin{aligned} C_{\varvec{u}}=\prod _{j=1}^{s}\prod _{h=1}^{d}\prod _{i=m+1}^{\infty }\left\{ 1+\frac{b-1}{b^{d(i-1)+h+a_j}}\right\} , \end{aligned}$$

and

$$\begin{aligned} B_{\varvec{u}}(\varvec{q},p) = -1+\frac{1}{b^m}\sum _{n=0}^{b^m-1}\prod _{j=1}^{s}\prod _{h=1}^{d}\prod _{i=1}^{m}\left\{ 1+\frac{\eta (\xi _{i,n,d(j-1)+h})}{b^{d(i-1)+h+a_j}}\right\} , \end{aligned}$$

respectively, where $\eta : \{0,1,\dots ,b-1\}\rightarrow \mathbb {R}$ is defined as

$$\begin{aligned} \eta (\xi ) {:=} {\left\{ \begin{array}{ll} b-1 &{}\quad \text {if } \xi =0, \\ -1 &{}\quad \text {otherwise.} \end{array}\right. } \end{aligned}$$

Since $C_{\varvec{u}}$ is independent of the modulus p and generating vector $\varvec{q}$, $B_{\varvec{u}}(\varvec{q},p)$ can be used as a quality criterion for searching for good p and $\varvec{q}$. In the following we introduce the CBC algorithm.

We restrict $q_j$, $1\le j\le ds$, to non-zero polynomials over $\mathbb {Z}_b$ with its degree less than m, where $m=\deg (p)$. Provided that p is irreducible, we can set $q_1=1$ without loss of generality. We denote by $R_{b,m}$ the set of all non-zero polynomials over $\mathbb {Z}_b$ with degree less than m, i.e.,

$$\begin{aligned} R_{b,m}=\{ q\in \mathbb {Z}_b[x]: \deg (q)<m\ \text {and}\ q\ne 0\} . \end{aligned}$$

We note that $|R_{b,m}|=b^m-1$. Further, we write $\varvec{q}_{\tau }=(q_1,\ldots , q_{\tau })$ for $1\le \tau \le ds$. The idea is now to search for the polynomials $q_j \in R_{b,m}$ component-by-component. To do so, we need to define $B_{\varvec{u}}(\varvec{q}_{\tau },p)$ for arbitrary $1 \le \tau \le ds$. This is done in the following way. Let $1 \le \tau \le ds$ and $\beta = \lceil \tau /d \rceil$. Then

$$\begin{aligned} B_{\varvec{u}}(\varvec{q}_{\tau },p)&= -1+\frac{1}{b^m}\sum _{n=0}^{b^m-1}\prod _{j=1}^{\beta -1}\prod _{h=1}^{d}\prod _{i=1}^{m}\left\{ 1+\frac{\eta (\xi _{i,n,d(j-1)+h})}{b^{d(i-1)+h+a_j}}\right\} \nonumber \\&\qquad \times \prod _{h=1}^{\tau -d(\beta -1)}\prod _{i=1}^{m}\left\{ 1+\frac{\eta (\xi _{i,n,d(\beta -1)+h})}{b^{d(i-1)+h+a_{\beta }}}\right\} . \end{aligned}$$

(4)

The CBC construction proceeds as follows.

Algorithm 1

Let $b,m,s,d,\varvec{u}=(u_j)_{j\in \mathbb {N}}$ be as above.

• 1. Choose an irreducible polynomial $p\in \mathbb {Z}_b[x]$ with $\deg (p)=m$.

• 2. Set $q_1=1$.

• 3. For $\tau =2,\ldots , ds$, find $q_{\tau }$ by minimizing $B_{\varvec{u}}((\varvec{q}_{\tau -1},q),p)$ as a function of $q\in R_{b,m}$.

In Sect. 4.3, we show that one can also use the fast CBC algorithm of [22, 23] to find good generating vectors.

Next we show that the generating vector $\varvec{q}$ found by Algorithm 1 satisfies the following bound.

Theorem 2

Let b be a prime and $p\in \mathbb {Z}_b[x]$ be irreducible with $\deg (p)=m$. Let $\phi :[0,\infty )\rightarrow [0,\infty )$ be a concave and unbounded monotonic increasing function. Suppose that $\varvec{q}=(q_1,\ldots , q_{ds})$ is constructed using Algorithm 1. Then we have

$$\begin{aligned} B_{\varvec{u}}(\varvec{q},p) \le \phi ^{-1}\left[ \frac{1}{b^m-1}\sum _{\begin{array}{c} \varvec{k}\in \mathbb {N}_0^s\setminus \{\varvec{0}\}\\ k_j<b^{dm}, \forall j \end{array}}\phi \left( b^{-\mu (\varvec{a};\varvec{k})}\right) \right] . \end{aligned}$$

The proof of this result is presented in Sect. 4.1.

The function $\phi (x)=x^{\lambda }$, $0<\lambda \le 1$, has been often used to obtain these types of error bounds in the literature. In this case, one may apply so-called Jensen’s inequality

$$\begin{aligned} \phi \left( \sum _{n}c_n\right) \le \sum _{n}\phi (c_n), \end{aligned}$$

(5)

for any sequence of non-negative real numbers $(c_n)$. The inequality (5), however, also holds for any concave function $\phi :[0,\infty )\rightarrow [0,\infty )$ [6, Section 2.3]. In our case, the function $\phi (x)=x^{\lambda }$ is not a good choice because it does not give us the worst-case error bound with a super-polynomial convergence. Instead we use $\phi$ which maps $b^{-\mu (\varvec{a};\varvec{k})}$ to $b^{-(\mu (\varvec{a};\varvec{k}))^{\lambda }}$ for $0<\lambda \le 1$. Such a map can be designed as follows. For $b=2$, let $\tilde{x}_{\lambda }=2^{-(\log 2)^{1/\lambda }}$ for $0<\lambda \le 1$. Then

$$\begin{aligned} \phi (x) = {\left\{ \begin{array}{ll} 2^{-(\log _2 (1/x))^{1/\lambda }} &{}\quad \text {if } 0< x< \tilde{x}_{\lambda }, \\ \frac{\lambda \log _2(\tilde{x}_{\lambda })^{\lambda -1}}{e\tilde{x}_{\lambda }}(x-\tilde{x}_{\lambda })+\frac{1}{e} &{}\quad \text {if } x\ge \tilde{x}_{\lambda }. \end{array}\right. } \end{aligned}$$

(6)

For $b\ge 3$,

$$\begin{aligned} \phi (x) = {\left\{ \begin{array}{ll} b^{-(\log _b (1/x))^{1/\lambda }} &{}\quad \text {if } 0< x< \frac{1}{b}, \\ \lambda \left( x-\frac{1}{b}\right) +\frac{1}{b} &{}\quad \text {if } x\ge \frac{1}{b}. \end{array}\right. } \end{aligned}$$

(7)

Note that we set $\phi (0)=0$ for any b and $0<\lambda \le 1$, and that the function $\phi$ is concave and unbounded monotonic increasing on $[0,\infty )$. As above we need a slight modification for the case $b=2$ since the function $\phi (x) =2^{-(\log _2 (1/x))^{1/\lambda }}$ is concave over the interval $(0,\tilde{x}_{\lambda })$ but not over the interval (0, 1 / 2). Using this function and under the same condition on the weights with Theorem 1, we have the following corollary of Theorem 2.

Corollary 1

Assume that $\varvec{u}$ satisfies $\liminf _{j\rightarrow \infty }\log (u_j^{-1})/j^r >0$ for $r>0$. Let b be a prime and $p\in \mathbb {Z}_b[x]$ be irreducible with $\deg (p)=m$. Suppose that $\varvec{q}=(q_1,\ldots , q_{ds})$ is constructed using Algorithm 1. Then there exist constants $D_{r,\lambda },E_{r,\lambda }>0$ both independent of s such that we have

$$\begin{aligned} B_{\varvec{u}}(\varvec{q},p) \le E_{r,\lambda }b^{-\left( \log _b\left( \frac{b^m-1}{D_{r,\lambda }}\right) \right) ^{1/\lambda }} , \end{aligned}$$

for any $(r+1)/(2r+1)<\lambda \le 1$. Moreover, by setting $d\ge m^{r/(r+1)}$, the worst-case error satisfies the bound

$$\begin{aligned} e^{\mathrm {wor}}(\mathcal {F}_{s,\varvec{u}};\mathcal {D}_d(P(\varvec{q},p))) \le E'_{r,\lambda }b^{-\left( \log _b\left( \frac{b^m-1}{D_{r,\lambda }+1}\right) \right) ^{1/\lambda }} , \end{aligned}$$

where $E'_{r,\lambda }>0$ is a constant independent of s.

The proof of this result is presented in Sect. 4.2.

This result means that we can construct a QMC rule which achieves a dimension-independent super-polynomial convergence of the worst-case error in $\mathcal {F}_{s,\varvec{u}}$ as (2) with $1<p<(2r+1)/(r+1)$. This is a bit weaker than Theorem 1 (shown by Suzuki in [27]), since we do not have an error bound for the endpoint $p=(2r+1)/(r+1)$. Under an additional assumption, however, it is even possible to include the case $\lambda =(r+1)/(2r+1)$ in Corollary 1, see Remark 2. The most important advantage of our approach is that a good QMC rule can be explicitly constructed by using a CBC algorithm.

3 The worst-case error in $\mathcal {F}_{s,\varvec{u}}$

To analyze the worst-case error of interlaced polynomial lattice rules, we introduce a digit interlacing composition for non-negative integers. Let d be an interlacing factor, and let $\varvec{k}=(k_1,\ldots ,k_d)\in \mathbb {N}_0^d$ whose b-adic expansions are given by $k_j=\sum _{i=0}^{\infty }\kappa _{i,j} b^i$, which is actually a finite expansion. Then the digit interlacing function $\mathcal {E}_d: \mathbb {N}_0^d \rightarrow \mathbb {N}_0$ is defined as

$$\begin{aligned} \mathcal {E}_d(\varvec{k}) {:=} \sum _{i=0}^{\infty }\sum _{j=1}^{d}\kappa _{i,j}b^{di+j-1} . \end{aligned}$$

It is obvious to show that $\mathcal {E}_d$ is bijective. We also define such a function for ds-dimensional vectors $\varvec{k}=(k_1,\ldots ,k_{ds})\in \mathbb {N}_0^{ds}$ by applying $\mathcal {E}_d$ to every consecutive d components, that is,

$$\begin{aligned} \mathcal {E}_d(\varvec{k}) {:=} \left( \mathcal {E}_d(k_1,\dots ,k_d), \mathcal {E}_d(k_{d+1},\dots ,k_{2d}), \ldots , \mathcal {E}_d(k_{d(s-1)+1},\dots ,k_{ds})\right) . \end{aligned}$$

The following lemma relates an interlaced polynomial lattice point set to numerical integration of Walsh functions, see [12, Lemma 1] for the proof.

Lemma 2

Let $\mathcal {D}_d(P(\varvec{q},p))=\{\varvec{y}_0,\varvec{y}_1,\dots ,\varvec{y}_{b^m-1}\}\subset [0,1)^s$ be an interlaced polynomial lattice point set of order d with modulus $p\in \mathbb {Z}_b[x]$, $\deg (p)=m$, and generating vector $\varvec{q}\in (\mathbb {Z}_b[x])^{ds}$. For $\varvec{k}\in \mathbb {N}_0^{ds}$, we have

$$\begin{aligned} \frac{1}{b^m}\sum _{n=0}^{b^m-1}\mathrm {wal}_{\mathcal {E}_d(\varvec{k})}(\varvec{y}_n)= {\left\{ \begin{array}{ll} 1 &{}\quad \text {if } \varvec{k}\in P^{\perp }(\varvec{q},p),\\ 0 &{}\quad \text {otherwise.} \\ \end{array}\right. } \end{aligned}$$

We introduce another function $\tilde{\mu }(a,h;\cdot ): \mathbb {N}_0\rightarrow \mathbb {R}$ for a real number a and an integer $h\in \{1,2,\dots , d\}$. For $k\in \mathbb {N}$, we denote its b-adic expansion by $k = \kappa _1 b^{c_1-1}+\kappa _2 b^{c_2-1}+\cdots +\kappa _v b^{c_v-1}$ such that $\kappa _1,\dots ,\kappa _v \in \{1,2,\dots ,b-1\}$ and $c_1>\ldots> c_v >0$. The function $\tilde{\mu }(a,h;\cdot ): \mathbb {N}_0\rightarrow \mathbb {R}$ is defined as

$$\begin{aligned} \tilde{\mu }(a,h;k) {:=} \sum _{i=1}^{v}\left[ d(c_i-1)+h+a\right] , \end{aligned}$$

and $\tilde{\mu }(a,h;0){:=}0$. For vectors of real numbers $\varvec{a}$ and $\varvec{k}\in \mathbb {N}_0^{ds}$, we define

$$\begin{aligned} \tilde{\mu }(\varvec{a};\varvec{k}) {:=} \sum _{j=1}^{s}\sum _{h=1}^{d}\tilde{\mu }(a_j,h; k_{d(j-1)+h}) . \end{aligned}$$

With a slight abuse of notation, for $u\subset \{1,2,\ldots ,ds\}$ and $\varvec{k}_u\in \mathbb {N}_0^s$, we write $\tilde{\mu }(\varvec{a};\varvec{k}_u){:=} \tilde{\mu }(\varvec{a};(\varvec{k}_u,\varvec{0}))$, where the vector $(\varvec{k}_u,\varvec{0})$ denotes the ds-dimensional vector whose j-th component is $k_j$ for $j\in u$ and 0 otherwise. From Definition 4 and the definition of $\mathcal {E}_d$, we have

$$\begin{aligned} \mu (\varvec{a};\mathcal {E}_d(\varvec{k})) = \tilde{\mu }(\varvec{a};\varvec{k}) . \end{aligned}$$

(8)

Now the worst-case error for numerical integration in $\mathcal {F}_{s,\varvec{u}}$ using an interlaced polynomial lattice rule is given as follows.

Proposition 2

Let $\mathcal {D}_d(P(\varvec{q},p))\subset [0,1)^s$ be an interlaced polynomial lattice point set of order d with modulus $p\in \mathbb {Z}_b[x]$, $\deg (p)=m$, and generating vector $\varvec{q}\in (\mathbb {Z}_b[x])^{ds}$. For a sequence of the weights $\varvec{u}$, we have

$$\begin{aligned} e^{\mathrm {wor}}(\mathcal {F}_{s,\varvec{u}};\mathcal {D}_d(P(\varvec{q},p))) \le \sum _{\varvec{k}\in P^{\perp }(\varvec{q},p)\setminus \{\varvec{0}\}}b^{-\tilde{\mu }(\varvec{a};\varvec{k})} , \end{aligned}$$

where $P^{\perp }(\varvec{q},p)$ is the dual polynomial lattice of $P(\varvec{q},p)$, and $\varvec{a}$ is a sequence of real numbers given as in Proposition 1.

Proof

We write $\mathcal {D}_d(P(\varvec{q},p))=\{\varvec{y}_0,\varvec{y}_1,\dots ,\varvec{y}_{b^m-1}\}$. Let us consider a function $f\in \mathcal {F}_{s,\varvec{u}}$. Given the Walsh series expansion of f and the fact that $\mathcal {E}_d$ is bijective, the signed integration error becomes

$$\begin{aligned} I(f;\mathcal {D}_d(P(\varvec{q},p)))-I(f)&= \frac{1}{b^m}\sum _{n=0}^{b^m-1}f(\varvec{y}_n)- \hat{f}(\varvec{0}) \\&= \frac{1}{b^m}\sum _{n=0}^{b^m-1}\sum _{\varvec{k}\in \mathbb {N}_0^{ds}}\hat{f}(\mathcal {E}_d(\varvec{k}))\mathrm {wal}_{\mathcal {E}_d(\varvec{k})}(\varvec{y}_n) - \hat{f}(\varvec{0}) \\&= \sum _{\varvec{k}\in \mathbb {N}_0^{ds}}\hat{f}(\mathcal {E}_d(\varvec{k}))\frac{1}{b^m}\sum _{n=0}^{b^m-1}\mathrm {wal}_{\mathcal {E}_d(\varvec{k})}(\varvec{y}_n) - \hat{f}(\varvec{0}) \\&= \sum _{\varvec{k}\in P^{\perp }(\varvec{q},p)\setminus \{\varvec{0}\}}\hat{f}(\mathcal {E}_d(\varvec{k})) , \end{aligned}$$

where we use Lemma 2 in the last equality. Then we obtain

$$\begin{aligned} e^{\mathrm {wor}}(\mathcal {F}_{s,\varvec{u}};\mathcal {D}_d(P(\varvec{q},p)))&= \sup _{\begin{array}{c} f\in \mathcal {F}_{s,\varvec{u}}\\ ||f||_{\mathcal {F}_{s,\varvec{u}}} \le 1 \end{array}}\left| \sum _{\varvec{k}\in P^{\perp }(\varvec{q},p)\setminus \{\varvec{0}\}}\hat{f}(\mathcal {E}_d(\varvec{k}))\right| \\&\le \sup _{\begin{array}{c} f\in \mathcal {F}_{s,\varvec{u}}\\ ||f||_{\mathcal {F}_{s,\varvec{u}}} \le 1 \end{array}}\sum _{\varvec{k}\in P^{\perp }(\varvec{q},p)\setminus \{\varvec{0}\}}\left| \hat{f}(\mathcal {E}_d(\varvec{k}))\right| \\&\le \sup _{\begin{array}{c} f\in \mathcal {F}_{s,\varvec{u}}\\ ||f||_{\mathcal {F}_{s,\varvec{u}}} \le 1 \end{array}}||f||_{\mathcal {F}_{s,\varvec{u}}}\sum _{\varvec{k}\in P^{\perp }(\varvec{q},p)\setminus \{\varvec{0}\}}b^{-\mu (\varvec{a};\mathcal {E}_d(\varvec{k}))} \nonumber \\&= \sum _{\varvec{k}\in P^{\perp }(\varvec{q},p)\setminus \{\varvec{0}\}}b^{-\tilde{\mu }(\varvec{a};\varvec{k})} , \end{aligned}$$

where we use the triangle inequality, Proposition 1 and the identity (8) in the first inequality, the second inequality and the last equality, respectively. $\square$

Since the error bound in Proposition 2 is independent of a particular function f, it can be used as a quality criterion for the construction of interlaced polynomial lattice rules. The following proposition gives a concise formula for the bound on $e^{\mathrm {wor}}(\mathcal {F}_{s,\varvec{u}};\mathcal {D}_d(P(\varvec{q},p)))$ in Proposition 2.

Proposition 3

Let $P(\varvec{q},p)=\{\varvec{x}_0,\varvec{x}_1,\dots ,\varvec{x}_{b^m-1}\}\subset [0,1)^{ds}$ be a polynomial lattice point set with modulus $p\in \mathbb {Z}_b[x]$, $\deg (p)=m$, and generating vector $\varvec{q}\in (\mathbb {Z}_b[x])^{ds}$. Let $\mathcal {D}_d(P(\varvec{q},p))$ be its interlaced polynomial lattice point set. We denote the b-adic expansion of $x_{n,j}$ by $x_{n,j}=\sum _{i=1}^{\infty }\xi _{i,n,j} b^{-i}$ for $0\le n<b^m$ and $1\le j\le ds$. For a sequence of real numbers $\varvec{a}$, we have

$$\begin{aligned} \sum _{\varvec{k}\in P^{\perp }(\varvec{q},p)\setminus \{\varvec{0}\}}b^{-\tilde{\mu }(\varvec{a};\varvec{k})} = -1+\frac{1}{b^m}\sum _{n=0}^{b^m-1}\prod _{j=1}^{s}\prod _{h=1}^{d}\prod _{i=1}^{\infty }\left\{ 1+\frac{\eta (\xi _{i,n,d(j-1)+h})}{b^{d(i-1)+h+a_j}}\right\} , \end{aligned}$$

where $\eta : \{0,1,\dots ,b-1\}\rightarrow \mathbb {R}$ is defined as

$$\begin{aligned} \eta (\xi ) {:=} {\left\{ \begin{array}{ll} b-1 &{}\quad \text {if } \xi =0, \\ -1 &{}\quad \text {otherwise.} \end{array}\right. } \end{aligned}$$

Proof

Using Lemma 1, we have

$$\begin{aligned}&\sum _{\varvec{k}\in P^{\perp }(\varvec{q},p)\setminus \{\varvec{0}\}}b^{-\tilde{\mu }(\varvec{a};\varvec{k})} \\&= \sum _{\varvec{k}\in \mathbb {N}_0^{ds}\setminus \{\varvec{0}\}}b^{-\tilde{\mu }(\varvec{a};\varvec{k})}\frac{1}{b^m}\sum _{n=0}^{b^m-1}\mathrm {wal}_{\varvec{k}}(\varvec{x}_n) \\&= -1+\frac{1}{b^m}\sum _{n=0}^{b^m-1}\sum _{\varvec{k}\in \mathbb {N}_0^{ds}}b^{-\tilde{\mu }(\varvec{a};\varvec{k})}\mathrm {wal}_{\varvec{k}}(\varvec{x}_n) \\&= -1+\frac{1}{b^m}\sum _{n=0}^{b^m-1}\prod _{j=1}^{s}\prod _{h=1}^{d}\sum _{k_{d(j-1)+h}=0}^{\infty }b^{-\tilde{\mu }(a_j,h;k_{d(j-1)+h})}\mathrm {wal}_{k_{d(j-1)+h}}(x_{n,d(j-1)+h}) . \end{aligned}$$

Let us consider the function $\psi _{a,h,M}:[0,1)\rightarrow \mathbb {R}$, for a real number a and $h,M\in \mathbb {N}$ with $1\le h\le d$, given by

$$\begin{aligned} \psi _{a,h,M}(x) = \sum _{k=0}^{b^M-1}b^{-\tilde{\mu }(a,h;k)}\mathrm {wal}_{k}(x) , \end{aligned}$$

for $x\in [0,1)$. Denoting the unique b-adic expansion of $x\in [0,1)$ by $x=\sum _{i=1}^{\infty }\xi _{i} b^{-i}$, and denoting also the b-adic expansion of $k\in \mathbb {N}_0$, $0\le k<b^M$, by $k=\sum _{i=0}^{M-1}\kappa _{i} b^{i}$, we have

$$\begin{aligned} \tilde{\mu }(a,h;\kappa _0+\kappa _1 b+\dots +\kappa _{M-1}b^{M-1}) = \sum _{i=1}^{M}\left[ d(i-1)+h+a\right] \chi (\kappa _{i-1}\ne 0) , \end{aligned}$$

where $\chi$ denotes the indicator function, and

$$\begin{aligned} \mathrm {wal}_{k}(x) = \prod _{i=1}^{M}\omega _b^{\kappa _{i-1} \xi _i} . \end{aligned}$$

Then we have

$$\begin{aligned} \psi _{a,h,M}(x)&= \sum _{\kappa _0=0}^{b-1}\sum _{\kappa _1=0}^{b-1}\cdots \sum _{\kappa _{M-1}=0}^{b-1}\prod _{i=1}^{M}b^{-\left[ d(i-1)+h+a\right] \chi (\kappa _{i-1}\ne 0)}\omega _b^{\kappa _{i-1} \xi _i} \\&= \prod _{i=1}^{M}\sum _{\kappa _{i-1}=0}^{b-1}b^{-\left[ d(i-1)+h+a\right] \chi (\kappa _{i-1}\ne 0)}\omega _b^{\kappa _{i-1} \xi _i} \\&= \prod _{i=1}^{M}\left\{ 1+\frac{\eta (\xi _i)}{b^{d(i-1)+h+a}}\right\} . \end{aligned}$$

By letting M go to $\infty$ we obtain that

$$\begin{aligned} \sum _{k=0}^{\infty }b^{-\tilde{\mu }(a,h;k)}\mathrm {wal}_{k}(x) = \lim _{M\rightarrow \infty }\psi _{a,h,M}(x) = \prod _{i=1}^{\infty }\left\{ 1+\frac{\eta (\xi _i)}{b^{d(i-1)+h+a}}\right\} , \end{aligned}$$

which converges pointwise absolutely. Hence the result follows. $\square$

In order to evaluate the bound on $e^{\mathrm {wor}}(\mathcal {F}_{s,\varvec{u}};\mathcal {D}_d(P(\varvec{q},p)))$ as shown in Proposition 3, one needs to compute an infinite product. This infeasible computation can be avoided in the following way. As already stated in Subsection 2.5, we have $\xi _{m+1,n,j}=\xi _{m+2,n,j}=\cdots =0$ for any $0\le n<b^m$ and $1\le j\le ds$. By setting

$$\begin{aligned} C_{\varvec{u}}=\prod _{j=1}^{s}\prod _{h=1}^{d}\prod _{i=m+1}^{\infty }\left\{ 1+\frac{b-1}{b^{d(i-1)+h+a_j}}\right\} , \end{aligned}$$

we have

$$\begin{aligned}&\quad e^{\mathrm {wor}}(\mathcal {F}_{s,\varvec{u}};\mathcal {D}_d(P(\varvec{q},p))) \nonumber \\&\le -1+\frac{C_{\varvec{u}}}{b^m}\sum _{n=0}^{b^m-1}\prod _{j=1}^{s}\prod _{h=1}^{d}\prod _{i=1}^{m}\left\{ 1+\frac{\eta (\xi _{i,n,d(j-1)+h})}{b^{d(i-1)+h+a_j}}\right\} \nonumber \\&= C_{\varvec{u}}-1+C_{\varvec{u}}\left[ -1+\frac{1}{b^m}\sum _{n=0}^{b^m-1}\prod _{j=1}^{s}\prod _{h=1}^{d}\prod _{i=1}^{m}\left\{ 1+\frac{\eta (\xi _{i,n,d(j-1)+h})}{b^{d(i-1)+h+a_j}}\right\} \right] \nonumber \\&=: C_{\varvec{u}}-1+C_{\varvec{u}}B_{\varvec{u}}(\varvec{q},p). \end{aligned}$$

(9)

In (12) below we show that $C_{\varvec{u}}-1 \le E b^{-dm}$ for some constant $E > 0$, so that the main term in (9) is $B_{\varvec{u}}(\varvec{q}, p)$. Since an infinite product does not appear in $B_{\varvec{u}}(\varvec{q},p)$, we can use $B_{\varvec{u}}(\varvec{q},p)$ as a quality criterion for searching for good generating vectors $\varvec{q}$ instead of $e^{\mathrm {wor}}(\mathcal {F}_{s,\varvec{u}};\mathcal {D}_d(P(\varvec{q},p)))$. Note that $B_{\varvec{u}}(\varvec{q},p)$ can be also expressed as

$$\begin{aligned} B_{\varvec{u}}(\varvec{q},p) = \sum _{\begin{array}{c} \varvec{k}\in P^{\perp }(\varvec{q},p)\setminus \{\varvec{0}\}\\ k_j<b^m, \forall j \end{array}}b^{-\tilde{\mu }(\varvec{a};\varvec{k})} . \end{aligned}$$

4 Component-by-component algorithm

4.1 Error bounds for the algorithm

In the proof of Theorem 2 and its subsequent analysis, we use Jensen’s inequality (5) for a concave and unbounded monotonic increasing function $\phi :[0,\infty )\rightarrow [0,\infty )$.

As mentioned in Sect. 2.5, for arbitrary $1\le \tau \le ds$ , we define $B_{\varvec{u}}(\varvec{q}_{\tau },p)$ as in (4), which can be also expressed as

$$\begin{aligned} B_{\varvec{u}}(\varvec{q}_{\tau },p) = \sum _{\begin{array}{c} \varvec{k}\in P^{\perp }(\varvec{q}_{\tau },p)\setminus \{\varvec{0}\}\\ k_j<b^m, \forall j \end{array}}b^{-\tilde{\mu }(\varvec{a};\varvec{k})} . \end{aligned}$$

In order to prove Theorem 2, we first show the following proposition.

Proposition 4

Let b be a prime and $p\in \mathbb {Z}_b[x]$ be irreducible with $\deg (p)=m$. Let $\phi :[0,\infty )\rightarrow [0,\infty )$ be a concave and unbounded monotonic increasing function. Suppose that $\varvec{q}=(q_1,\ldots , q_{ds})$ is constructed using Algorithm 1. Then, for any $\tau =1,\dots ,ds$, we have

$$\begin{aligned} B_{\varvec{u}}(\varvec{q}_{\tau },p) \le \phi ^{-1}\left[ \frac{1}{b^m-1}\sum _{\begin{array}{c} \varvec{k}\in \mathbb {N}_0^\tau \setminus \{\varvec{0}\}\\ k_j<b^{m}, \forall j \end{array}}\phi \left( b^{-\tilde{\mu }(\varvec{a};\varvec{k})}\right) \right] . \end{aligned}$$

Proof

We prove the proposition by induction on $\tau$. Let us consider the case $\tau =1$ first. Since $p\in \mathbb {Z}_b[x]$ is irreducible with $\deg (p)=m$ and $q_1=1$, we have $P^{\perp }(1,p)=\{b^m k: k\in \mathbb {N}_0\}$, which implies

$$\begin{aligned} B_{\varvec{u}}(1,p) = \sum _{\begin{array}{c} k \in P^{\perp }(1,p)\setminus \{0\}\\ k <b^m \end{array}}b^{-\tilde{\mu }(a_1,1;k)}=0. \end{aligned}$$

Thus we have

$$\begin{aligned} B_{\varvec{u}}(1,p) \le \phi ^{-1}\left[ \frac{1}{b^m-1}\sum _{0< k <b^m}\phi \left( b^{-\tilde{\mu }(a_1,1;k)}\right) \right] . \end{aligned}$$

Suppose that for some integer $1\le \tau <ds$ we have already obtained $\varvec{q}_{\tau }\in (R_{b,m})^{\tau }$ such that

$$\begin{aligned} B_{\varvec{u}}(\varvec{q}_{\tau },p) \le \phi ^{-1}\left[ \frac{1}{b^m-1}\sum _{\begin{array}{c} \varvec{k}\in \mathbb {N}_0^\tau \setminus \{\varvec{0}\}\\ k_j<b^{m}, \forall j \end{array}}\phi \left( b^{-\tilde{\mu }(\varvec{a};\varvec{k})}\right) \right] . \end{aligned}$$

Now we consider a $q\in R_{b,m}$. We have

$$\begin{aligned} B_{\varvec{u}}((\varvec{q}_{\tau },q),p)&= \sum _{\begin{array}{c} \varvec{k}\in P^{\perp }((\varvec{q}_{\tau },q),p)\setminus \{\varvec{0}\}\\ k_j<b^m, \forall j \end{array}}b^{-\tilde{\mu }(\varvec{a};\varvec{k})} \\&= \sum _{\begin{array}{c} \varvec{k}\in P^{\perp }((\varvec{q}_{\tau },q),p)\setminus \{\varvec{0}\}\\ k_j<b^m \text { for } 1\le j\le \tau \\ k_{\tau +1}=0 \end{array}}b^{-\tilde{\mu }(\varvec{a};\varvec{k})} + \sum _{\begin{array}{c} \varvec{k}\in P^{\perp }((\varvec{q}_{\tau },q),p)\setminus \{\varvec{0}\}\\ k_j<b^m \text { for } 1\le j\le \tau \\ 0<k_{\tau +1}<b^m \end{array}}b^{-\tilde{\mu }(\varvec{a};\varvec{k})} \\&= B_{\varvec{u}}(\varvec{q}_{\tau },p)+\theta _{\varvec{u}}((\varvec{q}_{\tau },q),p) , \end{aligned}$$

where we write

$$\begin{aligned} \theta _{\varvec{u}}((\varvec{q}_{\tau },q),p) {:=} \sum _{\begin{array}{c} \varvec{k}\in P^{\perp }((\varvec{q}_{\tau },q),p)\setminus \{\varvec{0}\}\\ k_j<b^m \text { for } 1\le j\le \tau \\ 0<k_{\tau +1}<b^m \end{array}}b^{-\tilde{\mu }(\varvec{a};\varvec{k})}. \end{aligned}$$

To find $q_{\tau +1}\in R_{b,m}$ which minimizes $B_{\varvec{u}}((\varvec{q}_{\tau },q),p)$ as a function of q, we only need to consider the term $\theta _{\varvec{u}}((\varvec{q}_{\tau },q),p)$. Using an averaging argument and Jensen’s inequality (5) for a concave and unbounded monotonic increasing function $\phi :[0,\infty )\rightarrow [0,\infty )$, we have

$$\begin{aligned} \phi \left( \theta _{\varvec{u}}(\varvec{q}_{\tau +1},p)\right)&\le \frac{1}{b^m-1}\sum _{q\in R_{b,m}} \phi \left( \theta _{\varvec{u}}((\varvec{q}_{\tau },q),p)\right) \\&\le \frac{1}{b^m-1}\sum _{q\in R_{b,m}} \sum _{\begin{array}{c} \varvec{k}\in P^{\perp }((\varvec{q}_{\tau },q),p)\setminus \{\varvec{0}\}\\ k_j<b^m \text { for } 1\le j\le \tau \\ 0<k_{\tau +1}<b^m \end{array}} \phi \left( b^{-\tilde{\mu }(\varvec{a};\varvec{k})} \right) \\&= \sum _{\begin{array}{c} \varvec{k}\in \mathbb {N}_0^{\tau +1}\setminus \{\varvec{0}\}\\ k_j<b^m \text { for } 1\le j\le \tau \\ 0<k_{\tau +1}<b^m \end{array}}\frac{\phi \left( b^{-\tilde{\mu }(\varvec{a};\varvec{k})} \right) }{b^m-1}\sum _{\begin{array}{c} q\in R_{b,m}\\ \mathrm {tr}_m(\varvec{k})\cdot (\varvec{q}_{\tau },q)\equiv 0 \pmod p \end{array}}1 . \end{aligned}$$

Since $k_{\tau +1}$ cannot be a multiple of $b^m$, the inner sum in the last expression equals 0 if $(k_1,\dots ,k_{\tau })\in P^{\perp }(\varvec{q}_{\tau },p)$, and equals 1 otherwise. Through this argument, we obtain

$$\begin{aligned} \phi \left( \theta _{\varvec{u}}(\varvec{q}_{\tau +1},p)\right)&\le \frac{1}{b^m-1}\sum _{\begin{array}{c} \varvec{k}\in \mathbb {N}_0^{\tau +1}\setminus \{\varvec{0}\}\\ \varvec{k}_{\tau }\notin P^{\perp }(\varvec{q}_{\tau },p) \\ k_j<b^m \text { for } 1\le j\le \tau \\ 0<k_{\tau +1}<b^m \end{array}}\phi \left( b^{-\tilde{\mu }(\varvec{a};\varvec{k})} \right) \\&\le \frac{1}{b^m-1}\sum _{\begin{array}{c} \varvec{k}\in \mathbb {N}_0^{\tau +1}\setminus \{\varvec{0}\}\\ k_j<b^m \text { for } 1\le j\le \tau \\ 0<k_{\tau +1}<b^m \end{array}}\phi \left( b^{-\tilde{\mu }(\varvec{a};\varvec{k})} \right) . \end{aligned}$$

Finally, using Jensen’s inequality (5) again, we have

$$\begin{aligned}&\quad \phi \left( B_{\varvec{u}}(\varvec{q}_{\tau +1},p)\right) \\&\le \phi \left( B_{\varvec{u}}(\varvec{q}_{\tau },p)\right) + \phi \left( \theta _{\varvec{u}}(\varvec{q}_{\tau +1},p) \right) \\&\le \frac{1}{b^m-1}\sum _{\begin{array}{c} \varvec{k}\in \mathbb {N}_0^\tau \setminus \{\varvec{0}\}\\ k_j<b^{m}, \forall j \end{array}}\phi \left( b^{-\tilde{\mu }(\varvec{a};\varvec{k})}\right) + \frac{1}{b^m-1} \sum _{\begin{array}{c} \varvec{k}\in \mathbb {N}_0^{\tau +1}\setminus \{\varvec{0}\}\\ k_j<b^m \text { for } 1\le j\le \tau \\ 0<k_{\tau +1}<b^m \end{array}}\phi \left( b^{-\tilde{\mu }(\varvec{a};\varvec{k})} \right) \\&= \frac{1}{b^m-1}\sum _{\begin{array}{c} \varvec{k}\in \mathbb {N}_0^{\tau +1}\setminus \{\varvec{0}\}\\ k_j<b^{m}, \forall j \end{array}}\phi \left( b^{-\tilde{\mu }(\varvec{a};\varvec{k})}\right) . \end{aligned}$$

Hence the result follows. $\square$

Now we are ready to prove Theorem 2.

Proof of Theorem 2

From Proposition 4 in which let $\tau =ds$, and using the identity (8) and the fact that $\mathcal {E}_d$ is bijective between $\{0,1,\ldots ,b^m-1\}^{d}$ and $\{0,1,\ldots ,b^{dm}-1\}$, we have

$$\begin{aligned} B_{\varvec{u}}(\varvec{q},p)&\le \phi ^{-1}\left[ \frac{1}{b^m-1}\sum _{\begin{array}{c} \varvec{k}\in \mathbb {N}_0^{ds}\setminus \{\varvec{0}\}\\ k_j<b^{m}, \forall j \end{array}}\phi \left( b^{-\tilde{\mu }(\varvec{a};\varvec{k})}\right) \right] \\&= \phi ^{-1}\left[ \frac{1}{b^m-1}\sum _{\begin{array}{c} \varvec{k}\in \mathbb {N}_0^{ds}\setminus \{\varvec{0}\}\\ k_j<b^{m}, \forall j \end{array}}\phi \left( b^{-\mu (\varvec{a};\mathcal {E}_d(\varvec{k}))}\right) \right] \\&= \phi ^{-1}\left[ \frac{1}{b^m-1}\sum _{\begin{array}{c} \varvec{k}\in \mathbb {N}_0^{s}\setminus \{\varvec{0}\}\\ k_j<b^{dm}, \forall j \end{array}}\phi \left( b^{-\mu (\varvec{a};\varvec{k})}\right) \right] , \end{aligned}$$

which implies the result. $\square$

So far, we have proved the following bound on the worst-case error:

$$\begin{aligned}&\quad e^{\mathrm {wor}}(\mathcal {F}_{s,\varvec{u}};\mathcal {D}_d(P(\varvec{q},p))) \nonumber \\&\le C_{\varvec{u}}-1+C_{\varvec{u}}\phi ^{-1}\left[ \frac{1}{b^m-1}\sum _{\begin{array}{c} \varvec{k}\in \mathbb {N}_0^{s}\setminus \{\varvec{0}\}\\ k_j<b^{dm}, \forall j \end{array}}\phi \left( b^{-\mu (\varvec{a};\varvec{k})}\right) \right] , \end{aligned}$$

(10)

for a concave and unbounded monotonic increasing function $\phi :[0,\infty )\rightarrow [0,\infty )$. In the following section we investigate the error bound in more detail using the function $\phi$ defined in (6) for $b=2$ and in (7) for $b\ge 3$.

4.2 Dependence of the error bounds on the dimension

Here we study the dependence of the worst-case error bounds with a super-polynomial convergence on the dimension by partly relying on the results in [27]. First we focus on the term

$$\begin{aligned} \sum _{\begin{array}{c} \varvec{k}\in \mathbb {N}_0^{s}\setminus \{\varvec{0}\}\\ k_j<b^{dm}, \forall j \end{array}}\phi \left( b^{-\mu (\varvec{a};\varvec{k})}\right) . \end{aligned}$$

As mentioned in Sect. 2.5, we use the purposely-designed concave function as in (6) for $b=2$ and in (7) for $b\ge 3$. Note again that we set $\phi (0)=0$ for any b and $0<\lambda \le 1$, and that the function $\phi$ is concave and unbounded monotonic increasing on $[0,\infty )$. We have the following result.

Lemma 3

Let $\phi :[0,\infty ) \rightarrow [0,\infty )$ be given as in (6) and (7). If a sequence of the weights $\varvec{u}$ satisfies $\liminf _{j\rightarrow \infty }\log (u_j^{-1})/j^r>0$ for some $r>0$, then there exists a constant $D'_{r,\lambda }$ depending only on r and $\lambda$ such that

$$\begin{aligned} \sum _{\begin{array}{c} \varvec{k}\in \mathbb {N}_0^{s}\setminus \{\varvec{0}\}\\ k_j<b^{dm}, \forall j \end{array}}\phi \left( b^{-\mu (\varvec{a};\varvec{k})}\right) \le D'_{r,\lambda } , \end{aligned}$$

for any $(r+1)/(2r+1)<\lambda \le 1$.

Proof

Since the case $b=2$ can be proven in the same way as the case $b\ge 3$, we only consider the latter case in the following. Since $\phi (b^{-x})=b^{-x^\lambda }$ for $x\ge 1$, we have

$$\begin{aligned} \sum _{\begin{array}{c} \varvec{k}\in \mathbb {N}_0^{s}\setminus \{\varvec{0}\}\\ k_j<b^{dm}, \forall j \end{array}}\phi \left( b^{-\mu (\varvec{a};\varvec{k})}\right)&\le \sum _{\begin{array}{c} \varvec{k}\in \mathbb {N}_0^{s}\setminus \{\varvec{0}\}\\ \mu (\varvec{a};\varvec{k})<1 \end{array}}\phi \left( b^{-\mu (\varvec{a};\varvec{k})}\right) +\sum _{\begin{array}{c} \varvec{k}\in \mathbb {N}_0^{s}\setminus \{\varvec{0}\}\\ \mu (\varvec{a};\varvec{k})\ge 1 \end{array}}\phi \left( b^{-\mu (\varvec{a};\varvec{k})}\right) \nonumber \\&= \sum _{\begin{array}{c} \varvec{k}\in \mathbb {N}_0^{s}\setminus \{\varvec{0}\}\\ \mu (\varvec{a};\varvec{k})<1 \end{array}}\phi \left( b^{-\mu (\varvec{a};\varvec{k})}\right) +\sum _{\begin{array}{c} \varvec{k}\in \mathbb {N}_0^{s}\setminus \{\varvec{0}\}\\ \mu (\varvec{a};\varvec{k})\ge 1 \end{array}}b^{-(\mu (\varvec{a};\varvec{k}))^{\lambda }} \nonumber \\&= \sum _{\begin{array}{c} \varvec{k}\in \mathbb {N}_0^{s}\setminus \{\varvec{0}\}\\ \mu (\varvec{a};\varvec{k})<1 \end{array}}\phi \left( b^{-\mu (\varvec{a};\varvec{k})}\right) + \sum _{i=1}^{\infty }\sum _{\begin{array}{c} \varvec{k}\in \mathbb {N}_0^{s}\setminus \{\varvec{0}\}\\ i\le \mu (\varvec{a};\varvec{k})<i+1 \end{array}}b^{-(\mu (\varvec{a};\varvec{k}))^{\lambda }} \nonumber \\&\le \sum _{\begin{array}{c} \varvec{k}\in \mathbb {N}_0^{s}\setminus \{\varvec{0}\}\\ \mu (\varvec{a};\varvec{k})<1 \end{array}}\phi \left( b^{-\mu (\varvec{a};\varvec{k})}\right) + \sum _{i=1}^{\infty }\mathrm {vol}_{\varvec{a}}(i+1)b^{-i^{\lambda }} , \end{aligned}$$

(11)

where

$$\begin{aligned} \mathrm {vol}_{\varvec{a}}(i+1) {:=} \left| \{\varvec{k}\in \mathbb {N}_0^s \setminus \{\varvec{0}\}: i\le \mu (\varvec{a};\varvec{k})<i+1 \}\right| . \end{aligned}$$

We now introduce the modified function $\mu '(\varvec{a}; \cdot )$ as follows [27, Definition 2.5]: For a real number a and $k\in \mathbb {N}$ whose b-adic expansion is given by $k = \kappa _1 b^{c_1-1}+\kappa _2 b^{c_2-1}+\cdots +\kappa _v b^{c_v-1}$ such that $\kappa _1,\dots ,\kappa _v \in \{1,2,\dots ,b-1\}$ and $c_1>\ldots> c_v >0$, we define

$$\begin{aligned} \mu '(a;k) {:=} \sum _{i=1}^{v}\max (c_i+a ,1) , \end{aligned}$$

and $\mu '(a;0){:=}0$. For a vector $\varvec{a}$ and $\varvec{k}\in \mathbb {N}_0^s$, we define

$$\begin{aligned} \mu '(\varvec{a};\varvec{k}) {:=} \sum _{j=1}^{s}\mu '(a_j;k_j) . \end{aligned}$$

Then it holds from [27, Section 2.2] that there exists a constant $c\ge 0$ such that $\mu (\varvec{a}; \varvec{k}) \ge \mu '(\varvec{a}; \varvec{k}) - c$ for any $\varvec{k}\in \mathbb {N}_0^s$. Thus we have $\mathrm {vol}_{\varvec{a}}(i+1) \le \mathrm {vol}_{\varvec{a}}'(i+c+1)$ where

$$\begin{aligned} \mathrm {vol}_{\varvec{a}}'(i+c+1) {:=} \left| \{\varvec{k}\in \mathbb {N}_0^s \setminus \{\varvec{0}\}: \mu '(\varvec{a};\varvec{k}) <i+c+1 \}\right| . \end{aligned}$$

Now the assumption $\liminf _{j\rightarrow \infty }\log (u_j^{-1})/j^r>0$ implies that there exist constants $a>0$ and $A \in \mathbb {N}_0$ such that $a_j \ge aj^r$ holds for all $j > A$. Then it holds from [27, Section 6.3] that the constant c can be bounded above independently of s, and moreover from [27, Lemma 6.12] that $\mathrm {vol}_{\varvec{a}}'(i+c+1)$ is bounded by

$$\begin{aligned} \mathrm {vol}_{\varvec{a}}'(i+c+1) \le \exp \left\{ A_{a,r}(i+c+1)^{(r+1)/(2r+1)}\right\} , \end{aligned}$$

where

$$\begin{aligned} A_{a,r} = (b-1)\left( A + \frac{\Gamma (1/r)}{ra^{1/r}}\right) + N + 1. \end{aligned}$$

In the above, we write $N = (b-1)\sum _{j=1}^s|\{i \in \mathbb {N}\mid i + a_j \le 1\}|$, which is bounded by a constant independent of s under the assumption $\liminf _{j\rightarrow \infty }\log (u_j^{-1})/j^r>0$, and $\Gamma (z)=\int _{0}^{\infty }t^{z-1}\exp (-t)\mathrm {d}t$ denotes the Gamma function.

Thus, for the second term of (11), we obtain

$$\begin{aligned} \sum _{i=1}^{\infty }\mathrm {vol}_{\varvec{a}}(i+1)b^{-i^{\lambda }} \le \sum _{i=1}^{\infty }\exp \left\{ A_{a,r}(i+c+1)^{(r+1)/(2r+1)}-i^{\lambda }\log b\right\} . \end{aligned}$$

The above infinite sum converges when $\lambda > (r+1)/(2r+1)$, which implies that the second term of (11) is bounded by a constant independent of s.

Again from [27, Section 6.3], when $\liminf _{j\rightarrow \infty }\log (u_j^{-1})/j^r>0$ it is possible to show that the number of $\varvec{k}\in \mathbb {N}_0^{s}\setminus \{\varvec{0}\}$ such that $\mu (\varvec{a};\varvec{k})<1$ is bounded by a constant independent of s. Thus, the first term of (11) is bounded by a constant independent of s. Since both terms of (11) are finite and depend only on r and $\lambda$, we have the result. $\square$

Remark 2

If $A_{a,r}< \log b$, $D'_{r,\lambda }$ is finite even when $\lambda = (r+1)/(2r+1)$, and thus, Lemma 3 and Corollary 1 also hold for the endpoint $\lambda =(r+1)/(2r+1)$. This corresponds to Theorem 1 (shown by Suzuki in [27]), while our approach is constructive.

Now we are ready to prove Corollary 1.

Proof of Corollary 1

Since $D'_{r,\lambda }$ is independent of s, there exists an $m_0\in \mathbb {N}$ independent of s such that either $D'_{r,\lambda }/(b^{m_0}-1)\le 1/e$ for the case $b=2$, or $D'_{r,\lambda }/(b^{m_0}-1)\le 1/b$ for the case $b\ge 3$. For $m\ge m_0$, we obtain

$$\begin{aligned} B_{\varvec{u}}(\varvec{q},p)&\le \phi ^{-1}\left[ \frac{1}{b^m-1}\sum _{\begin{array}{c} \varvec{k}\in \mathbb {N}_0^{s}\setminus \{\varvec{0}\}\\ k_j<b^{dm}, \forall j \end{array}}\phi \left( b^{-\tilde{\mu }(\varvec{a};\varvec{k})}\right) \right] \\&\le \phi ^{-1}\left[ \frac{D'_{r,\lambda }}{b^m-1}\right] = b^{-\left( \log _b\left( \frac{b^m-1}{D'_{r,\lambda }}\right) \right) ^{1/\lambda }} . \end{aligned}$$

Since $B_{\varvec{u}}(\varvec{q},p)$ is obviously finite even for $m< m_0$ and can be bounded independently of s from Proposition 4 and Lemma 3, there exists constants $D''_{r,\lambda },E''_{r,\lambda }>0$ both independent of s such that

$$\begin{aligned} B_{\varvec{u}}(\varvec{q},p) \le E''_{r,\lambda } b^{-\left( \log _b\left( \frac{b^m-1}{D''_{r,\lambda }}\right) \right) ^{1/\lambda }} , \end{aligned}$$

for $m< m_0$ and any $(r+1)/(2r+1)< \lambda \le 1$. As $D'_{r,\lambda }$, $D''_{r,\lambda }$ and $E''_{r,\lambda }$ are all independent of s, there exists constants $D_{r,\lambda },E_{r,\lambda }>0$ such that the first part of Corollary 1 holds.

Let us consider the term $C_{\varvec{u}}$. Using the inequality $\log (1+x)\le x$ for $x>0$, $C_{\varvec{u}}$ can be bounded by

$$\begin{aligned} \log (C_{\varvec{u}})&= \sum _{j=1}^{s}\sum _{h=1}^{d}\sum _{i=m+1}^{\infty }\log \left( 1+\frac{b-1}{b^{d(i-1)+h+a_j}}\right) \\&\le \sum _{j=1}^{s}\sum _{h=1}^{d}\sum _{i=m+1}^{\infty }\frac{b-1}{b^{d(i-1)+h+a_j}}= \frac{1}{b^{dm}}\sum _{j=1}^{s}\frac{1}{b^{a_j}} . \end{aligned}$$

Since the function $\exp (\cdot )$ is convex, we have

$$\begin{aligned} C_{\varvec{u}}-1&\le \exp \left( \frac{1}{b^{dm}}\sum _{j=1}^{s}\frac{1}{b^{a_j}}\right) -\exp (0) \le \frac{1}{b^{dm}}\left\{ \exp \left( \sum _{j=1}^{s}\frac{1}{b^{a_j}}\right) -1\right\} . \end{aligned}$$

(12)

As in the proof of Lemma 3, the assumption $\liminf _{j\rightarrow \infty }\log (u_j^{-1})/j^r>0$ implies that there exist constants $a>0$ and $A \in \mathbb {N}_0$ such that $a_j \ge aj^r$ holds for all $j > A$. Thus, we have

$$\begin{aligned} \exp \left( \sum _{j=1}^{s}\frac{1}{b^{a_j}}\right)&= \exp \left( \sum _{j=1}^{A}\frac{1}{b^{a_j}}+\sum _{j=A+1}^{s}\frac{1}{b^{a_j}}\right) \\&\le \exp \left\{ \sum _{j=1}^{A}\left( \frac{1}{b^{a_j}}-\frac{1}{b^{aj^r}}\right) +\sum _{j=1}^{\infty }\frac{1}{b^{aj^r}}\right\} \\&\le \exp \left\{ A\max _{j=1,\ldots ,A}\left( \frac{1}{b^{a_j}}-\frac{1}{b^{aj^r}}\right) +\frac{\Gamma (1/r)}{r(a\log b)^{1/r}}\right\} =: E''_r, \end{aligned}$$

where we use the result of [27, Lemma 6.11] in the second inequality and $\Gamma$ again denotes the Gamma function. Hence we have

$$\begin{aligned} C_{\varvec{u}}-1 \le \frac{E''_r}{b^{dm}}\quad \text {and}\quad C_{\varvec{u}}\le E''_r . \end{aligned}$$

Now let $d\ge m^{r/(r+1)}$. Using the above bounds on $B_{\varvec{u}}(\varvec{q},p)$ and $C_{\varvec{u}}$, we have

$$\begin{aligned} e^{\mathrm {wor}}(\mathcal {F}_{s,\varvec{u}};\mathcal {D}_d(P(\varvec{q},p)))&\le C_{\varvec{u}}-1+C_{\varvec{u}}B_{\varvec{u}}(\varvec{q},p) \\&\le E''_r\left\{ b^{-m^{(2r+1)/(r+1)}}+E_{r,\lambda }b^{-\left( \log _b\left( \frac{b^m-1}{D_{r,\lambda }}\right) \right) ^{1/\lambda }} \right\} \\&\le E'_{r,\lambda }b^{-\left( \log _b\left( \frac{b^m-1}{D_{r,\lambda }+1}\right) \right) ^{1/\lambda }} , \end{aligned}$$

where $E'_{r,\lambda }=E''_r(1+E_{r,\lambda })$, which proves the second part of Corollary 1. $\square$

4.3 Fast construction algorithm

We show how one can apply the fast CBC construction of [22, 23] using the fast Fourier transform. According to Algorithm 1, we choose an irreducible polynomial p with $\deg (p)=m$, set $q_1=1$ and construct the polynomials $q_2,q_3,\ldots ,q_{ds}$ inductively. For some $1\le \tau <ds$, assume that $\varvec{q}_{\tau -1}=(q_1,\ldots ,q_{\tau -1})$ are already found. Let $\beta = \lfloor \tau /d\rfloor$ and $\gamma =\tau -d(\beta -1)$. Using the notation as in the proof of Proposition 3, we compute

$$\begin{aligned}&\quad B_{\varvec{u}}((\varvec{q}_{\tau -1},q),p) \\&= -1+\frac{1}{b^m}\sum _{n=0}^{b^m-1}\left( \prod _{j=1}^{\beta -1}\prod _{h=1}^{d}\psi _{a_j,h,m}(x_{n,d(j-1)+h})\right) \prod _{h=1}^{\gamma }\psi _{a_{\beta },h,m}(x_{n,d(\beta -1)+h}) , \end{aligned}$$

for all $q\in R_{b,m}$, where $\{\varvec{x}_0,\ldots ,\varvec{x}_{b^m-1}\}\subset [0,1)^{\tau }$ is a polynomial lattice point set $P((\varvec{q}_{\tau -1},q),p)$.

We introduce the following notation

$$\begin{aligned} \rho _{n,\tau -1}{:=}\left( \prod _{j=1}^{\beta -1}\prod _{h=1}^{d}\psi _{a_j,h,m}(x_{n,d(j-1)+h})\right) \prod _{h=1}^{\gamma -1}\psi _{a_{\beta },h,m}(x_{n,d(\beta -1)+h}) , \end{aligned}$$

for $0\le n<b^m$, where the empty product is equal to 1. Then it is straightforward to confirm that

$$\begin{aligned} B_{\varvec{u}}((\varvec{q}_{\tau -1},q),p)&= -1+\frac{1}{b^m}\left[ \rho _{0,\tau -1}\psi _{a_{\beta },\gamma ,m}(0) +\sum _{n=1}^{b^m-1}\rho _{n,\tau -1}\psi _{a_{\beta },\gamma ,m}(x_{n,\tau }) \right] \end{aligned}$$

holds. Therefore, in order to find $q=q_{\tau }\in R_{b,m}$ which minimizes $B_{\varvec{u}}((\varvec{q}_{\tau -1},q),p)$ as a function of q, we only need to compute

$$\begin{aligned} \sum _{n=1}^{b^m-1}\rho _{n,\tau -1}\psi _{a_{\beta },\gamma ,m}(x_{n,\tau }) \end{aligned}$$

(13)

for all $q\in R_{b,m}$. In the following, we show how we can exploit a feature of polynomial lattice point sets to apply the fast CBC construction using the fast Fourier transform.

Since we choose an irreducible polynomial p, there exists a primitive element $g\in R_{b,m}$, which satisfies

$$\begin{aligned} \{g^0 \bmod {p}, g^1 \bmod {p}, \ldots , g^{b^m-2} \bmod {p}\} = R_{b,m}, \end{aligned}$$

and $g^{-1} \bmod {p}=g^{b^m-2} \bmod {p}$. When $q=g^i \bmod {p}$, we can rewrite (13) as

$$\begin{aligned} c_i&= \sum _{n=0}^{b^m-2}\rho _{g^{-n} \bmod {p},\tau -1}\psi _{a_{\beta },\gamma ,m}\left( x_{g^{-n}\bmod {p},\tau }\right) \\&= \sum _{n=0}^{b^m-2}\rho _{g^{-n} \bmod {p},\tau -1}\psi _{a_{\beta },\gamma ,m}\left( v_m\left( \frac{(g^{i-n}\bmod p)(x)}{p(x)}\right) \right) , \end{aligned}$$

for $0\le i<b^m-1$. Here the first argument $g^{-n} \bmod {p}$ of $\rho$ is understood as an integer by identifying the polynomial $g^{-n} \bmod {p}\in \mathbb {Z}_b[x]$ with an integer based on its b-adic expansion. Let us denote $\varvec{c}=(c_i)_{0\le i< b^m-1}$, $\varvec{\rho }_{\tau -1}=(\rho _{g^{-n} \bmod {p},\tau -1})_{0\le n< b^m-1}$, and

$$\begin{aligned} \Psi _{a_\beta ,\gamma } = \left[ \psi _{a_{\beta },\gamma ,m}\left( v_m\left( \frac{(g^{i-n}\bmod p)(x)}{p(x)}\right) \right) \right] _{0\le i,n<b^m-1} . \end{aligned}$$

Then we have

$$\begin{aligned} \varvec{c}= \Psi _{a_\beta ,\gamma }\varvec{\rho }_{\tau -1} . \end{aligned}$$

Let $i_0$ be an integer $0\le i_0 < b^m-1$ which satisfies $c_{i_0}\le c_{i}$ for all $0\le i<b^m-1$. Then we set $q_{\tau }=g^{i_0} \bmod {p}$. After finding $q_{\tau }$, we just update $\varvec{\rho }_{\tau }$ by

$$\begin{aligned} \rho _{g^{-n} \bmod {p},\tau }{:=}\rho _{g^{-n} \bmod {p},\tau -1} \psi _{a_{\beta },\gamma ,m}\left( v_m\left( \frac{(g^{i_0-n}\bmod p)(x)}{p(x)}\right) \right) . \end{aligned}$$

Since the matrix $\Psi _{a_\beta ,\gamma }$ is circulant, we only need to evaluate one column (or one row) of $\Psi _{a_\beta ,\gamma }$ for computing all the elements of $\Psi _{a_\beta ,\gamma }$. One column consists of $b^m-1$ elements, each of which can be evaluated in O(m) arithmetic operations. Moreover, the matrix-vector multiplication $\Psi _{a_\beta ,\gamma }\varvec{\rho }_{\tau -1}$ can be efficiently done in $O(mb^m)$ arithmetic operations by using the fast Fourier transform as shown in [22, 23]. This reduces the computational cost significantly as compared to the naive matrix-vector multiplication. Since we construct the polynomials $q_2,q_3,\ldots ,q_{ds}$ inductively, the total computational cost becomes $O(dsmb^m)$ arithmetic operations. As for memory, we only need to store the vector $\varvec{\rho }_{\tau }$, which requires $O(b^m)$ memory space.

From Corollary 1, to obtain a worst-case error bound with a dimension-independent super-polynomial convergence, it is sufficient to set $d\ge m^{r/(r+1)}$. This means that the total computational cost is given by $O(sm^{(2r+1)/(r+1)}b^m)$ arithmetic operations, which can be bounded above by $O(sm^2b^m) (= O(sN(\log N)^2))$ arithmetic operations for any $r>0$.

5 Numerical experiments

We conclude this paper with numerical experiments. In our experiments, we focus on the case $b=2$ and choose the weights $u_j=2^{-j^r}$ for $r>0$, i.e., $a_j=j^r$, which satisfies the condition $\liminf _{j\rightarrow \infty }\log (u_j^{-1})/j^r>0$. In Figure 1, we report the values of $B_{\varvec{u}}(\varvec{q},p)$ as functions of $m\ (=\deg (p))$ up to 15 with several values of s for the cases $r=0.5$ (top), $r=1$ (middle), and $r=2$ (bottom), respectively, where p and $\varvec{q}$ are found by Algorithm 1, and the interlacing factor is given by $d=\lceil m^{r/(r+1)} \rceil$, as Corollary 1 suggests. Since the first dm digits appearing in the dyadic expansion of every coordinate of each point can be non-zero, the range of m is restricted so that $dm\le 52$, by considering the double precision arithmetic. For $r=0.5$ and $r=1$, one can observe that the rate of convergence is improved as m increases for the low-dimensional cases $s=1$ and $s=2$, while one cannot do so for the higher-dimensional cases within this range of m. For $r=2$, one can observe an improvement of the rate of convergence even for the higher-dimensional cases and the convergence behaviors for $s\ge 2$ are almost identical, i.e., dimension-independent.

Fig. 1

$B_{\varvec{u}}(\varvec{q},p)$ as functions of m for $r=0.5$ (top), $r=1$ (middle), and $r=2$ (bottom)

Fig. 2

The absolute integration error as functions of m for $f_1$ with $r=0.5$ (top), $r=1$ (middle), and $r=2$ (bottom)

Fig. 3

The absolute integration error as functions of m for $f_2$ with $w=0.5$ (top) and $w=0.1$ (bottom) by Sobol’ sequence (left) and our constructed interlaced polynomial lattice rule (right)

Fig. 4

The absolute integration error as functions of m for $f_3$ with $w=0.5$ (top) and $w=0.1$ (bottom) by Sobol’ sequence (left) and our constructed interlaced polynomial lattice rule (right)

Next we consider the test function

$$\begin{aligned} f_1(\varvec{x}) = \prod _{j=1}^{s}\exp \left( -\frac{x_j}{2^{j^r}}\right) \end{aligned}$$

as integrand, which belongs to $\mathcal {F}_{s,\varvec{u}}$ for $u_j=2^{-j^r}$. Figure 2 shows the absolute integration error $|I(f_1;\mathcal {D}_d(P(\varvec{q},p)))-I(f_1)|$ as functions of m with several values of s for $r=0.5$ (top), $r=1$ (middle), and $r=2$ (bottom), respectively, where p and $\varvec{q}$ are again found by Algorithm 1 for each given r. Regardless of r, one can observe that a convergence better than 1 / N is achieved for any s. For $r=0.5$, we see a sudden drop between $m=8$ and $m=9$ for the low-dimensional cases $s=1$ and $s=2$. This is because of the increment of the interlacing factor d from 2 to 3. A similar behavior can be found for $r=1$ between $m=9$ and $m=10$, where the interlacing factor d is incremented from 3 to 4. It is interesting to see that the rate of convergence is improved after d increases. For $r=2$, the rate of convergence is roughly $N^{-4}$ even for $s=16$ and the convergence behaviors for $s\ge 2$ are almost identical.

Finally we consider the following two test functions

These were used in [9] as examples belonging to a certain function class with finite smoothness. In fact $f_3\notin \mathcal {F}_{s,\varvec{u}}$ for any choice of $\varvec{u}$ with $u_j=2^{-j^r}$ for $r>0$, and thus, there is no theoretical guarantee that our constructed interlaced polynomial lattice rule does work efficiently. We compare the performance of our constructed rule with that of the Sobol’ sequence. We search for p and $\varvec{q}$ by setting $r=1$ in Algorithm 1. Figures 3 and 4 show the absolute integration error as functions of m for $f_2$ and $f_3$, respectively. We see that our constructed rule is superior to Sobol’ sequence in terms of both the magnitude of the error and the rate of convergence. Regardless of the integrand and the dimension, the Sobol’ sequence achieves an error convergence of order $N^{-1}$. On the other hand, our constructed rule can exploit the smoothness of the functions and achieve an error convergence of higher order. Thus our constructed rule works even for some functions not belonging to $\mathcal {F}_{s,\varvec{u}}$.