# On a reduced digit-by-digit component-by-component construction of lattice
point sets

Peter Kritzer, Onyekachi Osisiogu P. Kritzer is supported by the Austrian
Science Fund, Project F5506, which is part of the Special Research Program
“Quasi-Monte Carlo Methods: Theory and Applications”, and Project P34808. For
the purpose of open access, the authors have applied a CC BY public copyright
licence to any author accepted manuscript version arising from this
submission.O Osisiogu is partially supported by the Austrian Science Fund,
Project F5506, which is part of the Special Research Program “Quasi-Monte
Carlo Methods: Theory and Applications”.

###### Abstract

In this paper, we study an efficient algorithm for constructing point sets
underlying quasi-Monte Carlo integration rules for weighted Korobov classes.
The algorithm presented is a reduced fast component-by-component digit-by-
digit (CBC-DBD) algorithm, which useful for to situations where the weights in
the function space show a sufficiently fast decay. The advantage of the
algorithm presented here is that the computational effort can be independent
of the dimension of the integration problem to be treated if suitable
assumptions on the integrand are met. The new reduced CBC-DBD algorithm is
designed to work for the construction of lattice point sets, and the
corresponding integration rules (so-called lattice rules) can be used to treat
functions in different kinds of function spaces. We show that the integration
rules constructed by our algorithm satisfy error bounds of almost optimal
convergence order. Furthermore, we give details on an efficient implementation
such that we obtain a considerable speed-up of a previously known CBC-DBD
algorithm that has been studied in [8]. This improvement is illustrated by
numerical results.

Keywords: Numerical integration; lattice points; quasi-Monte Carlo methods;
component-by-component construction; digit-by-digit construction; weighted
function spaces; fast implementation.

2010 MSC: 65D30, 65D32, 41A55, 41A63.

##  1 Introduction

In this paper we study numerical integration of functions defined over the
$d$-dimensional unit cube. For an integrable function
$f:[0,1)^{d}\rightarrow{\mathbb{R}}$, we denote the integral of $f$ by

$I_{d}(f):=\int_{[0,1]^{d}}f({\bm{x}})\,\mathrm{d}{\bm{x}},$

and we study the efficient construction of high-dimensional _quadrature rules_
of the form

$Q_{N}(f,({\bm{x}}_{k})_{k=0}^{N-1}):=\frac{1}{N}\sum_{k=0}^{N-1}\,f({\bm{x}}_{k})$

for numerically approximating $I_{d}$. We assume that the integrand $f$ lies
in a Banach space $({\mathcal{F}},\left\|\cdot\right\|_{{\mathcal{F}}})$, and
that the integration nodes ${\bm{x}}_{0},\ldots,{\bm{x}}_{N-1}\in[0,1)^{d}$
are to be chosen deterministically. Here $Q_{N}$ is called a _quasi-Monte
Carlo (QMC)_ rule, which is a special case of an equal-weight integration
rule. One way to measure the quality of a QMC integration rule $Q_{N}$ is to
consider the _worst-case error_ in the unit ball of the space
$({\mathcal{F}},\left\|\cdot\right\|_{{\mathcal{F}}}),$ i.e.,

$e_{N,d}(Q_{N},{\mathcal{F}}):=\sup_{\begin{subarray}{c}f\in{\mathcal{F}}\\\
\|f\|_{{\mathcal{F}}}\leq
1\end{subarray}}\left|I_{d}(f)-Q_{N}(f,({\bm{x}}_{k})_{k=0}^{N-1})\right|.$

In general, it is highly non-trivial to choose the set of integration nodes
such that the resulting rule has a low worst-case error. There are two main
types of QMC point sets
$\mathcal{P}=\\{{\bm{x}}_{0},{\bm{x}}_{1},\dots,{\bm{x}}_{N-1}\\}$, namely
_lattice point sets_ and _digital nets_. In this paper we consider lattice
point sets, which are obtained by considering discrete subsets of
${\mathbb{R}}^{d}$ that are closed under both addition and subtraction and
contain ${\mathbb{Z}}^{d}$ as a subset; by intersecting such a discrete set
with the $d$-dimensional unit cube $[0,1)^{d}$, we then obtain a lattice point
set. We are interested in a special kind of lattice point sets that is
essentially based on one _generating vector_ ${\bm{z}}$. These lattice point
sets were first introduced by Korobov [14] and independently by Hlawka [12]
and are among the most prominently studied QMC point sets to approximate
multivariate integrals (see standard textbooks such as [5, 13, 19, 22], and
also [6]). For a natural number $N\in{\mathbb{N}}$ and an integer generating
vector ${\bm{z}}\in\\{1,2,\dots,N-1\\}^{d}$, a point set with points of the
form

${\bm{x}}_{k}:=\left\\{\frac{k}{N}{\bm{z}}\right\\}=\left(\left\\{\frac{kz_{1}}{N}\right\\},\ldots,\left\\{\frac{kz_{d}}{N}\right\\}\right)\in[0,1)^{d},\qquad\text{for
}k=0,1,\ldots,N-1,$

is called a _rank-1 lattice point set_ , which we shall sometimes denote by
$P({\bm{z}},N)$. For vectors ${\bm{x}}\in{\mathbb{R}}^{d}$ we apply
$\\{\cdot\\}$ component-wise, where $\\{x\\}=x-\lfloor x\rfloor$ denotes the
fractional part of $x$. A QMC rule using such a point set as integration nodes
is called a _(rank-1) lattice rule_ with generating vector ${\bm{z}}$. We
remark that, given $N$ and $d$, a rank-1 lattice rule is completely determined
by the choice of the generating vector
${\bm{z}}=(z_{1},\ldots,z_{d})\in{\mathbb{Z}}_{N}^{d}$, where we write
${\mathbb{Z}}_{N}:=\\{0,\ldots,N-1\\}$. However, it should be obvious that not
every choice of a generating vector ${\bm{z}}$ also yields a rank-1 lattice
rule with good quality for approximating the integral, and it is usually
necessary to tailor the choice of the integration nodes to the function space
${\mathcal{F}}$ under consideration. For lattice rules we consider certain
Banach spaces which are based on assuming sufficient decay of the Fourier
coefficients of their elements to guarantee certain smoothness properties.
These spaces are called weighted Korobov classes, which we will denote by
$E_{d,{\bm{\gamma}}}^{\alpha}$, where $d$ denotes the number of variables the
functions depend on, $\alpha>1$ is a real number frequently referred to as the
smoothness parameter, and ${\bm{\gamma}}=(\gamma_{j})_{j\geq 1}$ is a sequence
of strictly positive reals, which model the importance of different
coordinates. The idea of these additional parameters $\gamma_{j}$, which we
refer to as weights in the definition of the function spaces under
consideration, goes back to Sloan and Woźniakowski [23], see also [24, 10],
and this will be made more precise by incorporating the weights in the norm of
the space $E_{d,{\bm{\gamma}}}^{\alpha}$ in Section 2. If we denote the
variables in the integration problem by ${\bm{x}}=(x_{1},\ldots,x_{d})$, a
small value of $\gamma_{j}$ corresponds to a low influence of the variable
$x_{j}$, while a large $\gamma_{j}$ means high influence of $x_{j}$. Regarding
the role of these weights in integration problems, we favor a situation in
which the weights decay sufficiently fast for coordinates with increasing
indices, which helps in vanquishing the curse of dimensionality that is
inherent to many high-dimensional problems. Indeed, under certain summability
conditions on the weights, it is even possible to obtain bounds on the
integration error that do not depend on the dimension of the problem at all.
Such a situation is called _strong polynomial tractability_ , see, e.g., [20],
for a general reference.

Regarding the construction of generating vectors, for dimensions $d\leq 2$
explicit constructions of good generating vectors are available, see, e.g.,
[22, 19], but there are no explicit constructions of good generating vectors
known for $d>2$; how to find a generating vector ${\bm{z}}$ that guarantees a
low worst-case error of integration in a given function space is a crucial
question regarding rank-1 lattice rules. One way to find good generating
vectors is the component-by-component (CBC) construction, which is based on a
greedy algorithm choosing one component of the generating vector at a time. It
was shown in [18] for prime $N$ (see also [2] for the case of composite $N$)
that it is possible to find generating vectors yielding essentially optimal
results for certain spaces of $d$-variate functions by the CBC construction.
Furthermore, it was shown in [21] that a fast CBC construction can reduce the
computational cost of these algorithms to only $\mathcal{O}(dN\log N)$, by
making use of a clever ordering of the points of a rank-1 lattice, and the
Fast Fourier Transform.

In the paper [4] the weights ${\bm{\gamma}}=(\gamma_{j})_{j\geq 1}$ in a given
function space were incorporated in the CBC construction of lattice rules. To
be more precise, depending on the weight $\gamma_{j}$, $j\in{\mathbb{N}}$, the
search space for the $j$th component $z_{j}$ of the generating vector
${\bm{z}}$ can be shrinked as compared to the usual CBC construction, and this
reduction is the motivation for the modified CBC algorithm to be called the
“reduced” CBC construction. Under suitable assumptions on the integrands
considered, it was shown in [4] that the lattice point sets obtained by the
reduced CBC construction can still yield excellent results when used as
integration nodes in a QMC rule, while the construction cost can be made
independent of the dimension $d$ of the integration problem. It was also shown
in [4] that the fast CBC construction principle of Nuyens and Cools, which was
mentioned above, can be adapted to the reduced CBC construction.

A different construction algorithm for generating vectors of good lattice
rules inspired by articles of Korobov (see [15] and [16], and [17] for an
English translation) was dealt with in the recent paper [8], where a so-called
component-by-component digit-by-digit (CBC-DBD) algorithm was presented. In
this approach, one constructs the generating vector ${\bm{z}}$ in a component-
by-component (CBC) fashion, in which each component $z_{j}$ is assembled
digit-by-digit (DBD). That is, for a number $N=2^{m}$ of points we greedily
construct the components $z_{j}$ bit-by-bit starting from the least
significant bit. It was shown that the rules constructed by the CBC-DBD
algorithm yield a convergence rate that is arbitrarily close to the optimal
rate. It is also possible to have a fast implementation of the CBC-DBD
algorithm which has a computational cost of $\mathcal{O}(dN\log N)$, and also
numerical results on the performance of the CBC-DBD algorithm are presented in
[8]. We remark that the error analysis for the CBC-DBD algorithm is such that
no prior knowledge of the smoothness parameter $\alpha$ is required to
construct the generating vector. The resulting generating vector will still
deliver the near optimal rate of convergence, for arbitrary smoothness
parameters $\alpha>1$, and this result can be stated independently of the
dimension, assuming that the weights satisfy certain summability conditions.

In the present paper, we would like to study a combination of the reduced CBC
algorithm from [4] and the CBC-DBD construction algorithm approach from [8],
and present a _reduced (fast) CBC-DBD algorithm_ for generating vectors of
good lattice rules with a large number of lattice points in high dimensions,
assuming sufficiently fast decaying weights. This new algorithm will work by
constructing the generating vector ${\bm{z}}$ in a component-by-component
(CBC) fashion in which each component $z_{j}$ is assembled digit-by-digit
(DBD). However, the search space for each component will be reduced in
comparison to what is shown in [8], thus speeding up the construction method.
We will show that for suitable choices of weights the construction cost of the
reduced fast CBC-DBD algorithm can be made independent of the dimension. The
main aim of this paper is to show that one can reduce the construction cost of
the lattice rule by making the search for later components smaller than the
earlier ones, while still achieving (strong) polynomial tractability.

The structure of this paper is as follows. In the subsequent section (Section
2), we outline the general setting, and then our construction algorithm as
well as the main result are stated and proved in Section 3. Section 4 contains
remarks on how to efficiently implement our newly found algorithm and some
numerical results.

Regarding notation, let ${\mathbb{N}}:=\\{1,2,\dots\\}$ be the set of natural
numbers, let ${\mathbb{N}}_{0}:=\\{0,1,2,\dots\\}$, and let ${\mathbb{Z}}$ be
the set of integers. Additionally, let the set of non-zero integers be denoted
by ${\mathbb{Z}}_{*}:={\mathbb{Z}}\setminus\\{0\\}$. For sets of components we
use fraktur font, e.g., ${\mathfrak{u}}\subset{\mathbb{N}}$. To denote the
projection of a vector ${\bm{x}}\in[0,1)^{d}$ or
${\bm{\ell}}\in{\mathbb{Z}}^{d}$ to the components in a set
${\mathfrak{u}}\subseteq[d]:=\\{1,\dots,d\\}$, we write
${\bm{x}}_{\mathfrak{u}}:=(x_{j})_{j\in{\mathfrak{u}}}$ or
${\bm{\ell}}_{\mathfrak{u}}:=(\ell_{j})_{j\in{\mathfrak{u}}}$, respectively.

##  2 Setting and overview

We consider one-periodic real-valued $L_{2}$ functions defined on $[0,1]^{d}$
with absolutely convergent Fourier series

$\displaystyle
f({\bm{x}})=\sum_{{\bm{\ell}}\in{\mathbb{Z}}^{d}}\hat{f}({\bm{\ell}})\,{\mathrm{e}}^{2\pi\mathrm{i}{\bm{\ell}}\cdot{\bm{x}}}\qquad\text{with}\qquad\hat{f}({\bm{\ell}}):=\int_{[0,1]^{d}}f({\bm{x}})\,{\mathrm{e}}^{-2\pi\mathrm{i}{\bm{\ell}}\cdot{\bm{x}}}\,\mathrm{d}{\bm{x}},$

where $\hat{f}({\bm{\ell}})$ are the Fourier coefficients of $f$ and
${\bm{\ell}}\cdot{\bm{x}}:=\sum_{j=1}^{d}\ell_{j}x_{j}=\ell_{1}x_{1}+\cdots+\ell_{d}x_{d}$
is the vector dot product.

It is known that rank-1 lattice point sets, as introduced in Section 1, have a
property commonly referred to as the _character property_. Indeed, for a
rank-1 lattice point set with generating vector ${\bm{z}}\in{\mathbb{Z}}^{d}$,
it is true that

$\frac{1}{N}\sum_{k=0}^{N-1}{\mathrm{e}}^{2\pi\mathrm{i}({\bm{\ell}}\cdot{\bm{z}})\,k/N}=\begin{cases}1&\text{if
}{\bm{\ell}}\cdot{\bm{z}}\equiv 0{\;({\rm{mod}}\;N)},\\\
0&\text{otherwise.}\end{cases}$

We introduce the dual of a rank-1 lattice, which is of great importance in
representing the error of approximating an integral by a lattice rule $Q_{N}$.

######  Definition 1 (Dual lattice).

Let $N\geq 2$ be the number of points and let
${\bm{z}}\in\\{1,\dots,N-1\\}^{d}$ be the generating vector of a rank-1
lattice point set $P({\bm{z}},N)$. The dual lattice
$\Lambda^{\top}({\bm{z}},N)$ of a rank-1 lattice $P({\bm{z}},N)$ is given by

$\displaystyle\mathcal{D}=\Lambda^{\top}({\bm{z}},N):=\\{{\bm{\ell}}\in{\mathbb{Z}}^{d}\
|\ {\bm{\ell}}\cdot{\bm{z}}\equiv 0{\;(\operatorname{mod}\;N)}\\}.$

For a non-empty set ${\mathfrak{u}}\subseteq[d],$ we can further define

$\mathcal{D}_{\mathfrak{u}}=\mathcal{D}_{\mathfrak{u}}({\bm{z}}_{\mathfrak{u}}):=\\{{\bm{\ell}}_{\mathfrak{u}}\in{\mathbb{Z}}^{|{\mathfrak{u}}|}_{*}\
|\ {\bm{\ell}}_{\mathfrak{u}}\cdot{\bm{z}}_{\mathfrak{u}}\equiv
0{\;(\operatorname{mod}\;N)}\\}.$

Then, to obtain the integration error for a given function $f$ in terms of its
Fourier coefficients, we interchange the order of summation and use the
character property of the lattice points, and get

$\displaystyle Q_{N}(f,{\bm{z}})-I_{d}(f)$ $\displaystyle=$
$\displaystyle\sum_{{\bm{0}}\neq{\bm{\ell}}\in{\mathbb{Z}}^{d}}\hat{f}({\bm{\ell}})\left[\frac{1}{N}\sum_{k=0}^{N-1}{\mathrm{e}}^{2\pi\mathrm{i}({\bm{\ell}}\cdot{\bm{z}})\,k/N}\right]$
$\displaystyle=$
$\displaystyle\\!\\!\\!\\!\sum_{\begin{subarray}{c}{\bm{0}}\neq{\bm{\ell}}\in{\mathbb{Z}}^{d}\\\
{\bm{\ell}}\cdot{\bm{z}}\equiv
0{\;({\rm{mod}}\;N)}\end{subarray}}\\!\\!\\!\\!\hat{f}({\bm{\ell}})$
$\displaystyle=$
$\displaystyle\sum_{{\bm{0}}\neq{\bm{\ell}}\in{\mathbb{Z}}^{d}}\hat{f}({\bm{\ell}})\,\delta_{N}({\bm{\ell}}\cdot{\bm{z}}),$

where, for $a\in{\mathbb{Z}}$,

$\delta_{N}(a):=\frac{1}{N}\sum_{k=0}^{N-1}{\mathrm{e}}^{2\pi\mathrm{i}ak/N}=\begin{cases}1&\text{if
}a\equiv 0{\;({\rm{mod}}\;N)},\\\ 0&\text{otherwise.}\end{cases}$

For a vector ${\bm{\ell}}\in{\mathbb{Z}}^{d}$, smoothness parameter
$\alpha>1$, and strictly positive weights ${\bm{\gamma}}=(\gamma_{j})_{j\geq
1}$, we define

$r_{\alpha,{\bm{\gamma}}}({\bm{\ell}}):=\prod_{j\in\operatorname{supp}({\bm{\ell}})}\gamma_{j}\left|\ell_{j}\right|^{\alpha},$
(1)

where $\operatorname{supp}({\bm{\ell}}):=\\{j\in[d]:\ell_{j}\neq 0\\}$ is the
support of ${\bm{\ell}}$. As usual, we define the empty product as one such
that $r_{\alpha,{\bm{\gamma}}}({\bm{0}})=1$. Formally, we will also use a
function $r_{1,{\bm{\gamma}}}$ below, which is obtained by replacing $\alpha$
by 1 in (1).

We then define our function space $E_{d,{\bm{\gamma}}}^{\alpha}$ of one-
periodic real-valued $L_{2}$ functions defined on $[0,1]^{d}$ with absolutely
convergent Fourier series. The norm in this space is given as

$\displaystyle\|f\|_{E_{d,{\bm{\gamma}}}^{\alpha}}:=\sup_{{\bm{\ell}}\in{\mathbb{Z}}^{d}}|\hat{f}({\bm{\ell}})|\,r_{\alpha,{\bm{\gamma}}}({\bm{\ell}}),$

and for $\alpha>1$, dimension $d\in{\mathbb{N}}$, and positive weight sequence
${\bm{\gamma}}=(\gamma_{j})_{j\geq 1}$, our weighted function space is

$E_{d,{\bm{\gamma}}}^{\alpha}:=\left\\{f\in
L^{2}([0,1]^{d})\colon\|f\|_{E_{d,{\bm{\gamma}}}^{\alpha}}<\infty\right\\}.$
(2)

It is known (see, for example, [5]) that the worst-case error of an $N$-point
rank-1 lattice rule generated by ${\bm{z}}\in{\mathbb{Z}}^{d}$ in the space
$E_{d,{\bm{\gamma}}}^{\alpha}$ is given by

$e_{N,d,\alpha,{\bm{\gamma}}}({\bm{z}})=\sum_{\begin{subarray}{c}{\bm{0}}\neq{\bm{\ell}}\in\mathcal{D}\end{subarray}}r_{\alpha,{\bm{\gamma}}}^{-1}({\bm{\ell}})=\sum_{{\bm{0}}\neq{\bm{\ell}}\in{\mathbb{Z}}^{d}}\frac{\delta_{N}({\bm{\ell}}\cdot{\bm{z}})}{r_{\alpha,{\bm{\gamma}}}({\bm{\ell}})}.$
(3)

We remark that the worst-case error (3) is sometimes referred to as
$P_{\alpha}$ in the literature on lattice rules. As pointed out above, it is
the main goal of the present paper to state a new effective construction
method for good instances of ${\bm{z}}$ such that
$e_{N,d,\alpha,{\bm{\gamma}}}({\bm{z}})$ is reasonably small.

It is well known, see, e.g., [22], that the optimal convergence rate of the
worst-case integration error in the space $E_{d,{\bm{\gamma}}}^{\alpha}$ is of
order ${\mathcal{O}}(N^{-\alpha})$. Furthermore, we would like to remark that
in the literature on lattice rules often a slightly different, but related,
function space than $E_{d,{\bm{\gamma}}}^{\alpha}$ is studied. Indeed, by
modifying the norm in the space to
$\left(\sum_{{\bm{\ell}}\in{\mathbb{Z}}^{d}}|\hat{f}({\bm{\ell}})|^{2}\,r_{\alpha,{\bm{\gamma}}}({\bm{\ell}})\right)^{1/2}$,
one obtains a reproducing kernel Hilbert space, which is often referred to as
“Korobov space”. It is known (see, e.g., [6]) that the worst-case error in
that space corresponds to the square root of the worst-case error in
$E_{d,{\bm{\gamma}}}^{\alpha}$, and so all results shown in the present paper
can directly be carried over to related results for the Korobov space. Note
also that, by using embedding results, any results on the error in
$E_{s,{\bm{\gamma}}}^{\alpha}$ immediately yield results on the worst-case
error of “tent-transformed” lattice rules in certain Sobolev spaces of
functions whose mixed partial derivatives of order $1$ and $2$ in each
variable are square integrable (with $\alpha=2$ and $\alpha=4$ in our
notation, respectively), see [1, 5, 7, 9] for further details.

###  2.1 The quality criterion used in this paper

In this section and the following we shall always assume that the number $N$
of points equals $2^{m}$, where $m\in{\mathbb{N}}$. Furthermore, we assume
that we are given a sequence of non-negative integers $(w_{j})_{j\geq 1}$
ordered in a non-decreasing fashion, to be more precise,
$w_{1},w_{2},\ldots\in{\mathbb{N}}_{0}$ with $0=w_{1}\leq w_{2}\leq\cdots$,
and we put $Y_{j}:=2^{w_{j}}$ for $j\in[d]$. The numbers $w_{j}$ for $j\geq 1$
are also called _reduction indices_ , as they will help to reduce the
computational cost of the CBC-DBD algorithm studied in this paper. In what
follows, we set $d^{*}$ as the largest $j$ such that $w_{j}<m$, i.e.,
$d^{*}:=\max\\{j\in{\mathbb{N}}:w_{j}<m\\}$. Moreover, we will usually (unless
stated otherwise) assume that the generating vector ${\bm{z}}$ of a lattice
rule under consideration takes the form
${\bm{z}}=(Y_{1}z_{1},\dots,Y_{d}z_{d})\in{\mathbb{Z}}^{d}$, where
$z_{j}\in\\{1,3,5,\dots,2^{m-w_{j}}-1\\}$ for $j\in[d^{*}]$, and $z_{j}$ is
odd if $j>d^{*}$ (in fact, we will often choose $z_{j}=1$ for $j>d^{*}$, but
any choice of odd numbers $z_{j}$ for those $j$ would yield the same results
for our lattices rules).

We define the following quality measure $T_{\bm{\gamma}}(N,{\bm{z}},{\bm{w}})$
for $N\in{\mathbb{N}}$ and
${\bm{w}}=(w_{1},\dots,w_{d})\in{\mathbb{N}}_{0}^{d}$ with $0=w_{1}\leq
w_{2}\leq\cdots$, by

$T_{\gamma}(N,{\bm{z}},{\bm{w}}):=\sum_{{\bm{0}}\neq{\bm{\ell}}\in
M_{N,d,{\bm{w}}}}\frac{\delta_{N}({\bm{\ell}}\cdot{\bm{z}})}{r_{1,{\bm{\gamma}}}({\bm{\ell}})},$
(4)

where the set $M_{N,d,{\bm{w}}}$ is defined as follows. Let

$M_{N,j,w_{j}}:=\\{-(2^{\max(0,m-w_{j})}-1),\ldots,2^{\max(0,m-w_{j})}-1\\}\qquad\text{for
}j\in[d].$

Furthermore, we write

$\\{M_{N,j,w_{j}}^{*}:=\left(\\{-(2^{\max(0,m-w_{j})}-1),\ldots,2^{\max(0,m-w_{j})}-1\\}\setminus\\{0\\}\right).$

Note that $M_{N,j,w_{j}}^{*}=\emptyset$ for $j>d^{*}$. Furthermore, let

$M_{N,d,{\bm{w}}}=M_{N,1,w_{1}}\times\cdots\times
M_{N,d,w_{d}},\qquad\text{and}\qquad
M_{N,d,{\bm{w}}}^{*}=M_{N,1,w_{1}}^{*}\times\cdots\times M_{N,d,w_{d}}^{*}.$

Then, for $\emptyset\neq{\mathfrak{u}}\subseteq[d]$, by
$M_{N,\left|{\mathfrak{u}}\right|,{\bm{w}}_{{\mathfrak{u}}}}$ and
$M_{N,\left|{\mathfrak{u}}\right|,{\bm{w}}_{{\mathfrak{u}}}}^{*}$, we denote
the projections of $M_{N,d,{\bm{w}}}$ and $M_{N,d,{\bm{w}}}^{*}$ onto the
components with indices in ${\mathfrak{u}}$, respectively. Likewise we define
the auxiliary quantity

$T_{\alpha,{\bm{\gamma}}}(N,{\bm{z}},{\bm{w}}):=\sum_{{\bm{0}}\neq{\bm{\ell}}\in
M_{N,d,{\bm{w}}}}\frac{\delta_{N}({\bm{\ell}}\cdot{\bm{z}})}{r_{\alpha,{\bm{\gamma}}}({\bm{\ell}})}.$

Let us denote the Riemann zeta function by
$\zeta(\alpha):=\sum_{n=1}^{\infty}n^{-\alpha}$ for $\alpha>1$. Moreover, we
write, for a non-empty set ${\mathfrak{u}}\subseteq[d]$,

$\gamma_{{\mathfrak{u}}}:=\prod_{j\in{\mathfrak{u}}}\gamma_{j},$

and we put $\gamma_{\emptyset}=1$.

The following proposition shows that we can use
$T_{\alpha,{\bm{\gamma}}}(N,{\bm{z}},{\bm{w}})$ as a suitable approximation to
the worst-case error of a rank-1 lattice rule.

######  Proposition 1.

Let $N=2^{m}$, let ${\bm{\gamma}}=(\gamma_{j})_{j\geq 1}$ be a sequence of
positive weights, let
${\bm{z}}=(Y_{1}z_{1},\ldots,Y_{d}z_{d})\in{\mathbb{Z}}^{d}$, and let
${\bm{w}}=(w_{j})_{j\geq 1}$ be a sequence in ${\mathbb{N}}_{0}$, with
$0=w_{1}\leq w_{2}\leq\cdots$. Furthermore, assume that all $z_{j}$,
$j\in[d]$, are odd, and that $z_{j}\in\\{1,3,5,\dots,2^{m-w_{j}}-1\\}$ for
$j\in[d^{*}]$. Then, for $\alpha>1$, we have that

$\displaystyle
e_{N,d,\alpha,{\bm{\gamma}}}({\bm{z}})-T_{\alpha,{\bm{\gamma}}}(N,{\bm{z}},{\bm{w}})$
$\displaystyle=$
$\displaystyle\sum_{{\bm{0}}\neq{\bm{\ell}}\in{\mathbb{Z}}^{d}}\frac{\delta_{N}({\bm{\ell}}\cdot{\bm{z}})}{r_{\alpha,{\bm{\gamma}}}({\bm{\ell}})}-\sum_{{\bm{0}}\neq{\bm{\ell}}\in
M_{N,d,{\bm{w}}}}\frac{\delta_{N}({\bm{\ell}}\cdot{\bm{z}})}{r_{\alpha,{\bm{\gamma}}}({\bm{\ell}})}$
$\displaystyle\leq$
$\displaystyle\sum_{\emptyset\neq{\mathfrak{u}}\subseteq[d]}\gamma_{\mathfrak{u}}\,\frac{(4\zeta(\alpha))^{\left|{\mathfrak{u}}\right|}}{2^{\alpha\max(0,m-\max_{j\in{\mathfrak{u}}}w_{j})}}.$

###### Proof.

We can rewrite the difference
$e_{N,d,\alpha,{\bm{\gamma}}}({\bm{z}})-T_{\alpha,{\bm{\gamma}}}(N,{\bm{z}},{\bm{w}})$
as

$\sum_{\emptyset\neq{\mathfrak{u}}\subseteq[d]}\left(\sum_{{\bm{\ell}}_{{\mathfrak{u}}}\in{\mathbb{Z}}_{*}^{\left|{\mathfrak{u}}\right|}}\frac{\delta_{N}({\bm{\ell}}_{{\mathfrak{u}}}\cdot{\bm{z}}_{{\mathfrak{u}}})}{r_{\alpha,{\bm{\gamma}}_{\mathfrak{u}}}({\bm{\ell}}_{{\mathfrak{u}}})}-\sum_{{\bm{\ell}}_{{\mathfrak{u}}}\in
M_{N,|{\mathfrak{u}}|,{\bm{w}}_{{\mathfrak{u}}}}^{*}}\frac{\delta_{N}({\bm{\ell}}_{{\mathfrak{u}}}\cdot{\bm{z}}_{{\mathfrak{u}}})}{r_{\alpha,{\bm{\gamma}}_{\mathfrak{u}}}({\bm{\ell}}_{{\mathfrak{u}}})}\right),$

motivating us to define, for ${\mathfrak{u}}\neq\emptyset$,
${\mathfrak{u}}\subseteq[d]$,

$T_{{\mathfrak{u}},{\bm{w}}_{{\mathfrak{u}}}}:=\sum_{{\bm{\ell}}_{{\mathfrak{u}}}\in{\mathbb{Z}}_{*}^{\left|{\mathfrak{u}}\right|}}\frac{\delta_{N}({\bm{\ell}}_{{\mathfrak{u}}}\cdot{\bm{z}}_{{\mathfrak{u}}})}{r_{\alpha,\gamma_{\mathfrak{u}}}({\bm{\ell}}_{{\mathfrak{u}}})}-\sum_{{\bm{\ell}}_{{\mathfrak{u}}}\in
M_{N,|{\mathfrak{u}}|,{\bm{w}}_{{\mathfrak{u}}}}^{*}}\frac{\delta_{N}({\bm{\ell}}_{{\mathfrak{u}}}\cdot{\bm{z}}_{{\mathfrak{u}}})}{r_{\alpha,\gamma_{\mathfrak{u}}}({\bm{\ell}}_{{\mathfrak{u}}})}.$

In the following we distinguish two cases for
$\emptyset\neq{\mathfrak{u}}\subseteq[d]$, depending on whether
$\left|{\mathfrak{u}}\right|=1$

Case 1: Suppose that $\left|{\mathfrak{u}}\right|=1$, i.e.,
${\mathfrak{u}}=\\{j\\}$ for some $j\in[d]$. Then we have

$\displaystyle T_{{\mathfrak{u}},{\bm{w}}_{{\mathfrak{u}}}}$ $\displaystyle=$
$\displaystyle T_{\\{j\\},w_{j}}$ $\displaystyle=$
$\displaystyle\sum_{\ell_{j}\in{\mathbb{Z}}_{*}}\frac{\delta_{N}(\ell_{j}Y_{j}z_{j})}{r_{\alpha,\gamma_{\\{j\\}}}(\ell_{j})}-\sum_{\ell_{j}\in
M_{N,\\{j\\},w_{j}}^{*}}\frac{\delta_{N}(\ell_{j}Y_{j}z_{j})}{r_{\alpha,\gamma_{\\{j\\}}}(\ell_{j})}$
$\displaystyle=$ $\displaystyle\sum_{\left|\ell_{j}\right|\geq
2^{\max(0,m-w_{j})}}\frac{\delta_{N}(\ell_{j}Y_{j}z_{j})}{r_{\alpha,\gamma_{\\{j\\}}}(\ell_{j})}$
$\displaystyle=$ $\displaystyle\sum_{\left|\ell_{j}\right|\geq
2^{\max(0,m-w_{j})}}\gamma_{j}\frac{\delta_{N}(\ell_{j}Y_{j}z_{j})}{\left|\ell_{j}\right|^{\alpha}}$
$\displaystyle=$ $\displaystyle
2\gamma_{j}\sum_{t=1}^{\infty}\frac{1}{(t2^{\max(0,m-w_{j})})^{\alpha}}=\frac{2\zeta(\alpha)}{2^{\alpha\max(0,m-w_{j})}}\gamma_{j},$

which follows from the fact that if $\ell_{j}Y_{j}z_{j}\equiv 0\text{ (mod
$N$)}$, this is equivalent to $\ell_{j}\equiv 0\text{ (mod
$2^{\max(0,m-w_{j})}$})$.

Case 2: For ${\mathfrak{u}}\neq\emptyset$, ${\mathfrak{u}}\subseteq[d]$ with
$\left|{\mathfrak{u}}\right|>1$, and $i\in{\mathfrak{u}}$, we write, for
short,
${\bm{\ell}}_{{\mathfrak{u}}\setminus\\{i\\}},{\bm{z}}_{{\mathfrak{u}}\setminus\\{i\\}}\in{\mathbb{Z}}^{\left|{\mathfrak{u}}\right|-1}$
to denote the projections of ${\bm{\ell}}$ and ${\bm{z}}$, respectively, onto
those components with indices in ${\mathfrak{u}}\setminus\\{i\\}$.

In this case, we estimate

$T_{{\mathfrak{u}},{\bm{w}}_{{\mathfrak{u}}}}\leq\sum_{i\in{\mathfrak{u}}}\sum_{{\bm{\ell}}_{{\mathfrak{u}}\setminus\\{i\\}}\in{\mathbb{Z}}_{*}^{\left|{\mathfrak{u}}\right|-1}}\sum_{\left|\ell_{i}\right|\geq
2^{\max(0,m-w_{i})}}\frac{\delta_{N}(\ell_{i}Y_{i}z_{i}+{\bm{\ell}}_{{\mathfrak{u}}\setminus\\{i\\}}\cdot{\bm{z}}_{{\mathfrak{u}}\setminus\\{i\\}})}{r_{\alpha,\gamma_{{\mathfrak{u}}}}({\bm{\ell}}_{{\mathfrak{u}}})}.$

For $i\in{\mathfrak{u}}$ and
${\bm{\ell}}_{{\mathfrak{u}}\setminus\\{i\\}}\in{\mathbb{Z}}_{*}^{\left|{\mathfrak{u}}\right|-1}$,
we write
$b:={\bm{\ell}}_{{\mathfrak{u}}\setminus\\{i\\}}\cdot{\bm{z}}_{{\mathfrak{u}}\setminus\\{i\\}}$,
and consider the expression

$\displaystyle\sum_{\left|\ell_{i}\right|\geq
2^{\max(0,m-w_{i})}}\frac{\delta_{N}(\ell_{i}Y_{i}z_{i}+b)}{r_{\alpha,\gamma_{{\mathfrak{u}}}}({\bm{\ell}}_{{\mathfrak{u}}})}=\gamma_{{\mathfrak{u}}}\sum_{\left|\ell_{i}\right|\geq
2^{\max(0,m-w_{i})}}\frac{\delta_{N}(\ell_{i}Y_{i}z_{i}+b)}{\prod_{j\in{\mathfrak{u}}}\left|\ell_{j}\right|^{\alpha}}$
$\displaystyle=$
$\displaystyle\gamma_{{\mathfrak{u}}}\left(\prod_{\begin{subarray}{c}j\in{\mathfrak{u}}\\\
j\neq
i\end{subarray}}\left|\ell_{j}\right|^{-\alpha}\right)\sum_{\left|\ell_{i}\right|\geq
2^{\max(0,m-w_{i})}}\frac{\delta_{N}(\ell_{i}Y_{i}z_{i}+b)}{\left|\ell_{i}\right|^{\alpha}}$
$\displaystyle=$
$\displaystyle\gamma_{{\mathfrak{u}}}\left(\prod_{\begin{subarray}{c}j\in{\mathfrak{u}}\\\
j\neq
i\end{subarray}}\left|\ell_{j}\right|^{-\alpha}\right)\sum_{t=1}^{\infty}\sum_{\ell_{i}=t2^{\max(0,m-w_{i})}}^{(t+1)2^{\max(0,m-w_{i})}-1}\left[\frac{\delta_{N}(\ell_{i}Y_{i}z_{i}+b)}{\left|\ell_{i}\right|^{\alpha}}+\frac{\delta_{N}(\ell_{i}Y_{i}z_{i}-b)}{\left|\ell_{i}\right|^{\alpha}}\right]$
$\displaystyle\leq$
$\displaystyle\gamma_{{\mathfrak{u}}}\left(\prod_{\begin{subarray}{c}j\in{\mathfrak{u}}\\\
j\neq
i\end{subarray}}\left|\ell_{j}\right|^{-\alpha}\right)\sum_{t=1}^{\infty}\frac{1}{(t2^{\max(0,m-w_{i})})^{\alpha}}\sum_{\ell_{i}=t2^{\max(0,m-w_{i})}}^{(t+1)2^{\max(0,m-w_{i})}-1}\left(\delta_{N}(\ell_{i}Y_{i}z_{i}+b)+\delta_{N}(\ell_{i}Y_{i}z_{i}-b)\right)$
$\displaystyle=$
$\displaystyle\gamma_{{\mathfrak{u}}}\left(\prod_{\begin{subarray}{c}j\in{\mathfrak{u}}\\\
j\neq
i\end{subarray}}\left|\ell_{j}\right|^{-\alpha}\right)\frac{1}{2^{\alpha\max(0,m-w_{i})}}\sum_{t=1}^{\infty}\frac{1}{t^{\alpha}}\sum_{\ell_{i}=t2^{\max(0,m-w_{i})}}^{(t+1)2^{\max(0,m-w_{i})}-1}\left(\delta_{N}(\ell_{i}Y_{i}z_{i}+b)+\delta_{N}(\ell_{i}Y_{i}z_{i}-b)\right)$
$\displaystyle=$
$\displaystyle\gamma_{{\mathfrak{u}}}\left(\prod_{\begin{subarray}{c}j\in{\mathfrak{u}}\\\
j\neq
i\end{subarray}}\left|\ell_{j}\right|^{-\alpha}\right)\frac{2\zeta(\alpha)}{2^{\alpha\max(0,m-w_{i})}},$

where the last equality follows from the fact that

$\sum_{\ell_{i}=t2^{\max(0,m-w_{i})}}^{(t+1)2^{\max(0,m-w_{i})}-1}\delta_{N}(\ell_{i}Y_{i}z_{i}+b)=1$

holds since the congruence
$\ell_{i}Y_{i}z_{i}+b=\ell_{i}2^{w_{i}}z_{i}+b\equiv 0{\;({\rm{mod}}\;N)}$ is
equivalent to $\ell_{i}2^{w_{i}}\equiv-z_{i}^{-1}b{\;({\rm{mod}}\;N)}$, and
then the latter congruence can have at most one solution $\ell_{i}$ in
$\\{t2^{\max(0,m-w_{i})},\ldots,(t+1)2^{\max(0,m-w_{i})}-1\\}$, see also [15,
Corollary of Proposition 1]. Therefore, we can estimate
$T_{{\mathfrak{u}},{\bm{w}}_{\mathfrak{u}}}$ for $\left|u\right|>1$, by

$\displaystyle T_{{\mathfrak{u}},{\bm{w}}_{{\mathfrak{u}}}}$
$\displaystyle\leq$
$\displaystyle\gamma_{{\mathfrak{u}}}2\zeta(\alpha)\sum_{i\in{\mathfrak{u}}}\frac{1}{2^{\alpha\max(0,m-w_{i})}}\sum_{{\bm{\ell}}_{{\mathfrak{u}}\setminus\\{i\\}}\in{\mathbb{Z}}_{*}^{\left|{\mathfrak{u}}\right|-1}}\prod_{\begin{subarray}{c}j\in{\mathfrak{u}}\\\
j\neq i\end{subarray}}\left|\ell_{j}\right|^{-\alpha}$ $\displaystyle=$
$\displaystyle\gamma_{{\mathfrak{u}}}2\zeta(\alpha)\sum_{i\in{\mathfrak{u}}}\frac{1}{2^{\alpha\max(0,m-w_{i})}}\left(2\sum_{\ell=1}^{\infty}\frac{1}{\ell^{\alpha}}\right)^{\left|{\mathfrak{u}}\right|-1}$
$\displaystyle=$
$\displaystyle(2\zeta(\alpha))^{\left|{\mathfrak{u}}\right|}\gamma_{{\mathfrak{u}}}\sum_{i\in{\mathfrak{u}}}\frac{1}{2^{\alpha\max(0,m-w_{i})}}$
$\displaystyle\leq$
$\displaystyle\frac{(2\zeta(\alpha))^{\left|{\mathfrak{u}}\right|}\gamma_{{\mathfrak{u}}}\left|{\mathfrak{u}}\right|}{2^{\alpha\max(0,m-\max_{i\in{\mathfrak{u}}}w_{i})}}$
$\displaystyle\leq$
$\displaystyle\gamma_{{\mathfrak{u}}}\frac{(4\zeta(\alpha))^{\left|{\mathfrak{u}}\right|}}{2^{\alpha\max(0,m-\max_{i\in{\mathfrak{u}}}w_{i})}}.$

In summary we obtain, by the results for both cases from above,

$\sum_{\emptyset\neq{\mathfrak{u}}\subseteq[d]}T_{{\mathfrak{u}},{\bm{w}}_{{\mathfrak{u}}}}\leq\sum_{\emptyset\neq{\mathfrak{u}}\subseteq[d]}\gamma_{\mathfrak{u}}\frac{(4\zeta(\alpha))^{\left|{\mathfrak{u}}\right|}}{2^{\alpha\max(0,m-\max_{j\in{\mathfrak{u}}}w_{j})}},$

as claimed. ∎

We have obtained a key ingredient for the worst-case error analysis from the
result on the truncation error in Proposition 1.

##  3 The construction method for rank-1 lattice rules

In this section, we will introduce, formulate, and analyze a method for the
construction of lattice rules. Firstly, we want to be able to estimate
efficiently the quantity $T_{\bm{\gamma}}(N,{\bm{z}},{\bm{w}})$ in (4), which
is needed for our construction method, and to do this we summarize some
auxiliary statements which will be needed in the following analysis.

###  3.1 Preliminary results

The following lemma (see [8] for a proof) shows that the function
$\log(\sin^{-2}(\pi x))$ can be written in terms of its truncated Fourier
series with uniformly bounded remainder term. We also bear in mind that it
cannot be evaluated in $x=0$ and $x=1$.

######  Lemma 1.

Let $N\in{\mathbb{N}}$, then for any $x\in(0,1)$ there exists a
$\tau(x)\in{\mathbb{R}}$ with $|\tau(x)|\leq 1$ such that

$\log(\sin^{-2}(\pi x))=\log 4+\sum_{\begin{subarray}{c}\ell=-(N-1)\\\
\ell\neq 0\end{subarray}}^{N-1}\frac{{\mathrm{e}}^{2\pi\mathrm{i}\ell
x}}{|\ell|}+\frac{\tau(x)}{N\|x\|}=\sum_{\ell=-(N-1)}^{N-1}\frac{{\mathrm{e}}^{2\pi\mathrm{i}\ell
x}}{b(\ell)}+\frac{\tau(x)}{N\|x\|},$

with coefficients

$\displaystyle b(\ell)$
$\displaystyle:=\left\\{\begin{array}[]{cc}\left|\ell\right|,&{\text{for
}}\ell\neq 0,\\\ 1/\log 4,&{\text{for }}\ell=0,\end{array}\right.$ (7)

where $\|x\|$ denotes the distance to the nearest integer of $x$, i.e.,

$\|x\|:=\min\\{\\{x\\},1-\\{x\\}\\}.$

What is more, we will make use of the following lemma, which was also proved
in [8].

######  Lemma 2.

For $j\in[d]$, let $u_{j},v_{j},\overline{u}_{j}$, and $r_{j}$ be real numbers
which satisfy

$\displaystyle(a)\quad
u_{j}=v_{j}+r_{j},\quad(b)\quad|u_{j}|\leq\bar{u}_{j},\quad(c)\quad\bar{u}_{j}\geq
1.$

Then, for any subset $\emptyset\neq{\mathfrak{u}}\subseteq[d]$ there exists a
$\theta_{{\mathfrak{u}}}$ with $|\theta_{{\mathfrak{u}}}|\leq 1$ such that the
following identity holds,

$\displaystyle\prod_{j\in{\mathfrak{u}}}u_{j}$
$\displaystyle=\prod_{j\in{\mathfrak{u}}}v_{j}+\theta_{{\mathfrak{u}}}\left(\prod_{j\in{\mathfrak{u}}}(\bar{u}_{j}+|r_{j}|)\right)\sum_{j\in{\mathfrak{u}}}|r_{j}|.$
(8)

###  3.2 The reduced CBC-DBD construction

We are now ready to study the reduced component-by-component digit-by-digit
(CBC-DBD) construction for lattice rules. To this end, we assume again
throughout the section that $N$ is of the form $2^{m}$ for some positive
integer $m$; this choice of $N$ is natural as the components of the generating
vector will be constructed digit by digit, i.e., bit by bit as we consider $N$
to be a power of $2$. We first show the following estimate on the quantity
$T_{\bm{\gamma}}(N,{\bm{z}},{\bm{w}})$, which already indicates the target
function to be minimized in Algorithm 1 below.

######  Theorem 1.

Let $N=2^{m}$, with $m>3$, let ${\bm{\gamma}}=(\gamma_{j})_{j\geq 1}$ be
positive weights, and let ${\bm{w}}=(w_{j})_{j\geq 1}$ be a sequence of
reduction indices in ${\mathbb{N}}_{0}$ with $0=w_{1}\leq w_{2}\leq\cdots$.
Furthermore, let $Y_{j}:=2^{w_{j}}$ for $j\in[d]$, and let
${\bm{z}}=(Y_{1}z_{1},\ldots,Y_{d}z_{d})\in\\{1,\ldots,N-1\\}^{d}$, where we
assume that all $z_{j}$, $j\in[d]$, are odd, and that
$z_{j}\in\\{1,3,\ldots,2^{m-w_{j}}-1\\}$ for $j\in[d^{*}]$. Then the following
estimate holds,

$\displaystyle T_{\bm{\gamma}}(N,{\bm{z}},{\bm{w}})$
$\displaystyle\leq\sum_{\emptyset\neq{\mathfrak{u}}\subseteq[d^{*}]}\frac{\gamma_{{\mathfrak{u}}}}{N}2^{w_{j_{\left|{\mathfrak{u}}\right|}}+1}(6\log
N)^{\left|{\mathfrak{u}}\right|}(1+\log N)$
$\displaystyle+\sum_{\emptyset\neq{\mathfrak{u}}\subseteq[d^{*}]}\frac{\gamma_{{\mathfrak{u}}}}{N}H_{N,{\mathfrak{u}},{\bm{w}}}-\sum_{\emptyset\neq{\mathfrak{u}}\subseteq[d^{*}]}\gamma_{{\mathfrak{u}}}(\log
4)^{\left|{\mathfrak{u}}\right|},$

where $j_{\left|{\mathfrak{u}}\right|}$ denotes the largest element of
${\mathfrak{u}}$ for $\emptyset\neq{\mathfrak{u}}\subseteq[d^{*}]$, where
$d^{*}:=\max\\{j\in{\mathbb{N}}:w_{j}<m\\}$, and where

$H_{N,{\mathfrak{u}},{\bm{w}}}:=\sum_{t=0}^{2^{w_{j_{\left|{\mathfrak{u}}\right|}}}-1}\
\
\sum_{k=t2^{m-w_{j_{\left|{\mathfrak{u}}\right|}}}+1}^{(t+1)2^{m-w_{j_{\left|{\mathfrak{u}}\right|}}}-1}\prod_{j\in{\mathfrak{u}}}\log\left(\frac{1}{\sin^{2}(\pi
z_{j}k/2^{m-w_{j}})}\right).$

###### Proof.

We have

$\displaystyle T_{{\bm{\gamma}}}(N,{\bm{z}},{\bm{w}})$ $\displaystyle=$
$\displaystyle\sum_{{\bm{0}}\neq{\bm{\ell}}\in
M_{N,d,{\bm{w}}}}\frac{\delta_{N}({\bm{\ell}}\cdot{\bm{z}})}{r_{1,{\bm{\gamma}}}({\bm{\ell}})}$
$\displaystyle=$
$\displaystyle\sum_{\emptyset\neq{\mathfrak{u}}\subseteq[d]}\gamma_{{\mathfrak{u}}}\sum_{{\bm{\ell}}_{{\mathfrak{u}}}\in
M_{N,\left|{\mathfrak{u}}\right|,{\bm{w}}_{{\mathfrak{u}}}}^{*}}\frac{\delta_{N}({\bm{\ell}}_{{\mathfrak{u}}}\cdot{\bm{z}}_{{\mathfrak{u}}})}{\prod_{j\in{\mathfrak{u}}}\left|\ell_{j}\right|}.$

Note that
$M_{N,\left|{\mathfrak{u}}\right|,{\bm{w}}_{{\mathfrak{u}}}}^{*}=\emptyset$ if
${\mathfrak{u}}\cap\\{d^{*}+1,d^{*}+2,\ldots,d\\}\neq\emptyset$. Therefore,
recalling the definition of $b(\ell)$ in (7),

$\displaystyle T_{{\bm{\gamma}}}(N,{\bm{z}},{\bm{w}})$ $\displaystyle=$
$\displaystyle\sum_{\emptyset\neq{\mathfrak{u}}\subseteq[d^{*}]}\gamma_{{\mathfrak{u}}}\sum_{{\bm{\ell}}_{{\mathfrak{u}}}\in
M_{N,\left|{\mathfrak{u}}\right|,{\bm{w}}_{{\mathfrak{u}}}}^{*}}\frac{\delta_{N}({\bm{\ell}}_{{\mathfrak{u}}}\cdot{\bm{z}}_{{\mathfrak{u}}})}{\prod_{j\in{\mathfrak{u}}}\left|\ell_{j}\right|}$
$\displaystyle=$
$\displaystyle\sum_{\emptyset\neq{\mathfrak{u}}\subseteq[d^{*}]}\gamma_{{\mathfrak{u}}}\sum_{{\bm{\ell}}_{{\mathfrak{u}}}\in
M_{N,\left|{\mathfrak{u}}\right|,{\bm{w}}_{{\mathfrak{u}}}}^{*}}\frac{\delta_{N}({\bm{\ell}}_{{\mathfrak{u}}}\cdot{\bm{z}}_{{\mathfrak{u}}})}{\prod_{j\in{\mathfrak{u}}}b(\ell_{j})}$
$\displaystyle\leq$
$\displaystyle\sum_{\emptyset\neq{\mathfrak{u}}\subseteq[d^{*}]}\gamma_{{\mathfrak{u}}}\sum_{{\bm{0}}\neq{\bm{\ell}}_{{\mathfrak{u}}}\in
M_{N,\left|{\mathfrak{u}}\right|,{\bm{w}}_{{\mathfrak{u}}}}}\frac{\delta_{N}({\bm{\ell}}_{{\mathfrak{u}}}\cdot{\bm{z}}_{{\mathfrak{u}}})}{\prod_{j\in{\mathfrak{u}}}b(\ell_{j})}$
$\displaystyle=$
$\displaystyle\sum_{\emptyset\neq{\mathfrak{u}}\subseteq[d^{*}]}\frac{\gamma_{{\mathfrak{u}}}}{N}\sum_{k=0}^{N-1}\left(\sum_{{\bm{\ell}}_{{\mathfrak{u}}}\in
M_{N,\left|{\mathfrak{u}}\right|,{\bm{w}}_{{\mathfrak{u}}}}}\frac{e^{2\pi\mathrm{i}k{\bm{\ell}}_{{\mathfrak{u}}}\cdot{\bm{z}}_{{\mathfrak{u}}}/N}}{\prod_{j\in{\mathfrak{u}}}b(\ell_{j})}-(\log
4)^{\left|{\mathfrak{u}}\right|}\right)$ $\displaystyle=$
$\displaystyle\sum_{\emptyset\neq{\mathfrak{u}}\subseteq[d^{*}]}\frac{\gamma_{{\mathfrak{u}}}}{N}\sum_{k=0}^{N-1}\sum_{{\bm{\ell}}_{{\mathfrak{u}}}\in
M_{N,\left|{\mathfrak{u}}\right|,{\bm{w}}_{{\mathfrak{u}}}}}\frac{e^{2\pi\mathrm{i}k{\bm{\ell}}_{{\mathfrak{u}}}\cdot{\bm{z}}_{{\mathfrak{u}}}/N}}{\prod_{j\in{\mathfrak{u}}}b(\ell_{j})}-\sum_{\emptyset\neq{\mathfrak{u}}\subseteq[d^{*}]}\gamma_{\mathfrak{u}}(\log
4)^{\left|{\mathfrak{u}}\right|}$ $\displaystyle=$
$\displaystyle\sum_{\emptyset\neq{\mathfrak{u}}\subseteq[d^{*}]}\frac{\gamma_{{\mathfrak{u}}}}{N}\sum_{k=0}^{N-1}\prod_{j\in{\mathfrak{u}}}\left(\log
4+\sum_{\ell_{j}\in
M_{N,j,w_{j}}^{*}}\frac{e^{2\pi\mathrm{i}k\ell_{j}2^{w_{j}}z_{j}/2^{m}}}{\left|\ell_{j}\right|}\right)-\sum_{\emptyset\neq{\mathfrak{u}}\subseteq[d^{*}]}\gamma_{\mathfrak{u}}(\log
4)^{\left|{\mathfrak{u}}\right|}$ $\displaystyle=$
$\displaystyle\sum_{\emptyset\neq{\mathfrak{u}}\subseteq[d^{*}]}\frac{\gamma_{{\mathfrak{u}}}}{N}\sum_{k=0}^{N-1}\prod_{j\in{\mathfrak{u}}}\left(\log
4+\sum_{\ell_{j}\in
M_{N,j,w_{j}}^{*}}\frac{e^{2\pi\mathrm{i}k\ell_{j}z_{j}/2^{m-w_{j}}}}{\left|\ell_{j}\right|}\right)-\sum_{\emptyset\neq{\mathfrak{u}}\subseteq[d^{*}]}\gamma_{\mathfrak{u}}(\log
4)^{\left|{\mathfrak{u}}\right|}.$

We can analyze the first term in (3.2) as follows. We assume that

${\mathfrak{u}}=\\{j_{1},j_{2},\ldots,j_{\left|{\mathfrak{u}}\right|}\\},$

such that $1\leq j_{1}<j_{2}<\cdots<j_{\left|{\mathfrak{u}}\right|}$. This
implies

$m\geq m-w_{j_{1}}\geq m-w_{j_{2}}\geq\cdots\geq
m-w_{j_{\left|{\mathfrak{u}}\right|}}.$

Suppose now that $k\in\\{0,1,\ldots,N-1\\}$ is such that $k\not\equiv 0\text{
(mod ${2^{m-w_{j_{\left|{\mathfrak{u}}\right|}}}}$)}.$ This also implies

$k\not\equiv 0\text{ (mod $2^{m-w_{j_{i}}}$)}\quad\forall
i\in\\{1,\ldots,\left|{\mathfrak{u}}\right|\\}.$

Therefore, for fixed $\emptyset\neq{\mathfrak{u}}\subseteq[d^{*}]$, we can
rewrite the inner sum over $k$ of the first term in (3.2) as

$\displaystyle\sum_{k=0}^{N-1}\prod_{j\in{\mathfrak{u}}}\left(\log
4+\sum_{\ell_{j}\in
M_{N,j,w_{j}}^{*}}\frac{e^{2\pi\mathrm{i}k\ell_{j}z_{j}/2^{m-w_{j}}}}{\left|\ell_{j}\right|}\right)$
(10) $\displaystyle=$
$\displaystyle\sum_{t=0}^{2^{w_{j_{\left|{\mathfrak{u}}\right|}}}-1}\ \
\sum_{k=t2^{m-w_{j_{\left|{\mathfrak{u}}\right|}}}+1}^{(t+1)2^{m-w_{j_{\left|{\mathfrak{u}}\right|}}}-1}\left(\prod_{j\in{\mathfrak{u}}}\left(\log
4+\sum_{\ell_{j}\in
M_{N,j,w_{j}}^{*}}\frac{e^{2\pi\mathrm{i}k\ell_{j}z_{j}/2^{m-w_{j}}}}{\left|\ell_{j}\right|}\right)\right)$
$\displaystyle+\sum_{t=0}^{2^{w_{j_{\left|{\mathfrak{u}}\right|}}}-1}\left(\prod_{j\in{\mathfrak{u}}}\left(\log
4+\sum_{\ell_{j}\in
M_{N,j,w_{j}}^{*}}\frac{e^{2\pi\mathrm{i}t2^{m-w_{j_{\left|{\mathfrak{u}}\right|}}}\ell_{j}z_{j}/2^{m-w_{j}}}}{\left|\ell_{j}\right|}\right)\right)$
$\displaystyle=:$
$\displaystyle\Sigma_{{\mathfrak{u}}}^{(1)}+\Sigma_{{\mathfrak{u}}}^{(2)}.$

Now we estimate the second summand $\Sigma_{{\mathfrak{u}}}^{(2)}$ in (10) as
follows,

$\displaystyle\Sigma_{{\mathfrak{u}}}^{(2)}\leq\left|\Sigma_{{\mathfrak{u}}}^{(2)}\right|$
$\displaystyle\leq$
$\displaystyle\sum_{t=0}^{2^{w_{j_{\left|{\mathfrak{u}}\right|}}}-1}\prod_{j\in{\mathfrak{u}}}\left(\log
4+\sum_{\ell_{j}\in M_{N,j,w_{j}}^{*}}\frac{1}{\left|\ell_{j}\right|}\right)$
$\displaystyle=$
$\displaystyle\sum_{t=0}^{2^{w_{j_{\left|{\mathfrak{u}}\right|}}}-1}\prod_{j\in{\mathfrak{u}}}\left(\log
4+2\sum_{\ell=1}^{2^{m-w_{j}}-1}\frac{1}{\ell}\right)$ $\displaystyle\leq$
$\displaystyle\sum_{t=0}^{2^{w_{j_{\left|{\mathfrak{u}}\right|}}}-1}\prod_{j\in{\mathfrak{u}}}\left(\log
4+2\sum_{\ell=1}^{N-1}\frac{1}{\ell}\right)$ $\displaystyle\leq$
$\displaystyle\sum_{t=0}^{2^{w_{j_{\left|{\mathfrak{u}}\right|}}}-1}\prod_{j\in{\mathfrak{u}}}\left(\log
4+4\log N\right)$ $\displaystyle\leq$
$\displaystyle\sum_{t=0}^{2^{w_{j_{\left|{\mathfrak{u}}\right|}}}-1}(6\log
N)^{\left|{\mathfrak{u}}\right|}$ $\displaystyle=$ $\displaystyle
2^{w_{j_{\left|{\mathfrak{u}}\right|}}}(6\log
N)^{\left|{\mathfrak{u}}\right|},$

where we implicitly assumed that $N\geq 3$ (which is no significant
restriction). Let us now analyze $\Sigma_{{\mathfrak{u}}}^{(1)}$ in (10),
where we proceed similarly to [8]. For $j\in{\mathfrak{u}}$ we get

$\displaystyle\Sigma_{{\mathfrak{u}}}^{(1)}$ $\displaystyle=$
$\displaystyle\sum_{t=0}^{2^{w_{j_{\left|{\mathfrak{u}}\right|}}}-1}\ \
\sum_{k=t2^{m-w_{j_{\left|{\mathfrak{u}}\right|}}}+1}^{(t+1)2^{m-w_{j_{\left|{\mathfrak{u}}\right|}}}-1}\left(\prod_{j\in{\mathfrak{u}}}v_{j}(k)-\prod_{j\in{\mathfrak{u}}}u_{j}(k)+\prod_{j\in{\mathfrak{u}}}u_{j}(k)\right)$
(11) $\displaystyle=$
$\displaystyle\sum_{t=0}^{2^{w_{j_{\left|{\mathfrak{u}}\right|}}}-1}\ \
\sum_{k=t2^{m-w_{j_{\left|{\mathfrak{u}}\right|}}}+1}^{(t+1)2^{m-w_{j_{\left|{\mathfrak{u}}\right|}}}-1}\prod_{j\in{\mathfrak{u}}}u_{j}(k)$
$\displaystyle+\sum_{t=0}^{2^{w_{j_{\left|{\mathfrak{u}}\right|}}}-1}\ \
\sum_{k=t2^{m-w_{j_{\left|{\mathfrak{u}}\right|}}}+1}^{(t+1)2^{m-w_{j_{\left|{\mathfrak{u}}\right|}}}-1}\left(\prod_{j\in{\mathfrak{u}}}v_{j}(k)-\prod_{j\in{\mathfrak{u}}}u_{j}(k)\right)$
$\displaystyle=$
$\displaystyle\sum_{t=0}^{2^{w_{j_{\left|{\mathfrak{u}}\right|}}}-1}\ \
\sum_{k=t2^{m-w_{j_{\left|{\mathfrak{u}}\right|}}}+1}^{(t+1)2^{m-w_{j_{\left|{\mathfrak{u}}\right|}}}-1}\prod_{j\in{\mathfrak{u}}}u_{j}(k)$
$\displaystyle+\sum_{t=0}^{2^{w_{j_{\left|{\mathfrak{u}}\right|}}}-1}\ \
\sum_{k=t2^{m-w_{j_{\left|{\mathfrak{u}}\right|}}}+1}^{(t+1)2^{m-w_{j_{\left|{\mathfrak{u}}\right|}}}-1}(-\theta_{{\mathfrak{u}}}(k))\left(\prod_{j\in{\mathfrak{u}}}(\overline{u}_{j}(k)+\left|r_{j}(k)\right|)\right)\sum_{j\in{\mathfrak{u}}}\left|r_{j}(k)\right|,$

where in (11) we used Lemma 2 with

$\displaystyle u_{j}=u_{j}(k):=\log\left(\frac{1}{\sin^{2}(\pi
z_{j}k/2^{m-w_{j}})}\right),\quad\qquad\qquad\overline{u}_{j}=\overline{u}_{j}(k):=2\log
N,$ $\displaystyle v_{j}=v_{j}(k):=\log 4+\sum_{\ell_{j}\in
M_{N,j,w_{j}}^{*}}\frac{e^{2\pi\mathrm{i}k\ell_{j}z_{j}/2^{m-w_{j}}}}{\left|\ell_{j}\right|},\quad
r_{j}=r_{j}(k):=\frac{\tau_{j}(k)}{2^{m-w_{j}}\left\|z_{j}k/2^{m-w_{j}}\right\|},$

where the terms $\theta_{{\mathfrak{u}}}(k)$ are defined analogously to Lemma
2, and satisfy $\left|\theta_{{\mathfrak{u}}}(k)\right|\leq 1$ and the
$\tau_{j}(k)$ are analogous to Lemma 1, and also satisfy
$\left|\tau_{j}(k)\right|\leq 1$. It can be checked easily that the conditions
in the lemmas are fulfilled. Indeed, Condition (a) in Lemma 2 is satisfied due
to Lemma 1. Furthermore, as in [8, Proof of Theorem 2], we see that

$\sin^{2}\left(\pi\frac{z_{j}k}{2^{m-w_{j}}}\right)\geq\left(\frac{1}{2^{m-w_{j}}}\right)^{2}.$

Therefore,

$\left|u_{j}(k)\right|=\log\left(\frac{1}{\sin^{2}(\pi
z_{j}k/2^{m-w_{j}})}\right)\leq\log\left(\left(2^{m-w_{j}}\right)^{2}\right)\leq
2\log N=\overline{u}_{j}(k).$

Furthermore, $\overline{u}_{j}(k)\geq 1$, as long as $N\geq 2$, which again is
not a real restriction. Next we show how to bound the second summand in (11)
independently of the choice of ${\bm{z}}$ as follows,

$\displaystyle\sum_{t=0}^{2^{w_{j_{\left|{\mathfrak{u}}\right|}}}-1}\ \
\sum_{k=t2^{m-w_{j_{\left|{\mathfrak{u}}\right|}}}+1}^{(t+1)2^{m-w_{j_{\left|{\mathfrak{u}}\right|}}}-1}(-\theta_{{\mathfrak{u}}}(k))\left(\prod_{j\in{\mathfrak{u}}}(\overline{u}_{j}(k)+\left|r_{j}(k)\right|)\right)\sum_{j\in{\mathfrak{u}}}\left|r_{j}(k)\right|$
$\displaystyle\leq$
$\displaystyle\sum_{t=0}^{2^{w_{j_{\left|{\mathfrak{u}}\right|}}}-1}\ \
\sum_{k=t2^{m-w_{j_{\left|{\mathfrak{u}}\right|}}}+1}^{(t+1)2^{m-w_{j_{\left|{\mathfrak{u}}\right|}}}-1}\left|\theta_{{\mathfrak{u}}}(k)\right|\left(\prod_{j\in{\mathfrak{u}}}\left(2\log
N+\frac{\left|\tau_{j}(k)\right|}{2^{m-w_{j}}\left\|z_{j}k/2^{m-w_{j}}\right\|}\right)\right)$
$\displaystyle\times\sum_{j\in{\mathfrak{u}}}\frac{\left|\tau_{j}(k)\right|}{2^{m-w_{j}}\left\|z_{j}k/2^{m-w_{j}}\right\|}$
$\displaystyle\leq$
$\displaystyle\sum_{t=0}^{2^{w_{j_{\left|{\mathfrak{u}}\right|}}}-1}\ \
\sum_{k=t2^{m-w_{j_{\left|{\mathfrak{u}}\right|}}}+1}^{(t+1)2^{m-w_{j_{\left|{\mathfrak{u}}\right|}}}-1}\left|\theta_{{\mathfrak{u}}}(k)\right|\left(\prod_{j\in{\mathfrak{u}}}(1+2\log
N)\right)\sum_{j\in{\mathfrak{u}}}\frac{\left|\tau_{j}(k)\right|}{2^{m-w_{j}}\left\|z_{j}k/2^{m-w_{j}}\right\|}$
$\displaystyle=$ $\displaystyle\left(\prod_{j\in{\mathfrak{u}}}(1+2\log
N)\right)\sum_{j\in{\mathfrak{u}}}\sum_{t=0}^{2^{w_{j_{\left|{\mathfrak{u}}\right|}}}-1}\
\
\sum_{k=t2^{m-w_{j_{\left|{\mathfrak{u}}\right|}}}+1}^{(t+1)2^{m-w_{j_{\left|{\mathfrak{u}}\right|}}}-1}\frac{\left|\theta_{{\mathfrak{u}}}(k)\right|\left|\tau_{j}(k)\right|}{2^{m-w_{j}}\left\|z_{j}k/2^{m-w_{j}}\right\|}$
$\displaystyle\leq$ $\displaystyle(1+2\log
N)^{\left|{\mathfrak{u}}\right|}\sum_{j\in{\mathfrak{u}}}\sum_{t=0}^{2^{w_{j_{\left|{\mathfrak{u}}\right|}}}-1}\
\
\sum_{k=t2^{m-w_{j_{\left|{\mathfrak{u}}\right|}}}+1}^{(t+1)2^{m-w_{j_{\left|{\mathfrak{u}}\right|}}}-1}\frac{1}{2^{m-w_{j}}\left\|z_{j}k/2^{m-w_{j}}\right\|}$
$\displaystyle\leq$ $\displaystyle(1+2\log
N)^{\left|{\mathfrak{u}}\right|}\sum_{j\in{\mathfrak{u}}}\sum_{t=0}^{2^{w_{j_{\left|{\mathfrak{u}}\right|}}}-1}\
\
\sum_{k=1}^{2^{m-w_{j}}-1}\frac{1}{2^{m-w_{j}}\left\|z_{j}k/2^{m-w_{j}}\right\|}$
$\displaystyle\leq$ $\displaystyle(1+2\log
N)^{\left|{\mathfrak{u}}\right|}2\left|{\mathfrak{u}}\right|2^{w_{j_{\left|{\mathfrak{u}}\right|}}}(1+\log
N)$ $\displaystyle\leq$ $\displaystyle(1+2\log
N)^{\left|{\mathfrak{u}}\right|}2^{\left|{\mathfrak{u}}\right|}2^{w_{j_{\left|{\mathfrak{u}}\right|}}}(1+\log
N)$ $\displaystyle\leq$ $\displaystyle(6\log
N)^{\left|{\mathfrak{u}}\right|}2^{w_{j_{\left|{\mathfrak{u}}\right|}}}(1+\log
N),$

where we used that

$2^{m-w_{j}}\left\|\frac{z_{j}k}{2^{m-w_{j}}}\right\|\geq
2^{m-w_{j}}\left\|\frac{1}{2^{m-w_{j}}}\right\|=1,$

that $2\left|{\mathfrak{u}}\right|\leq 2^{\left|{\mathfrak{u}}\right|}$, and
that $2^{m-w_{j}}\geq 2^{m-w_{j_{\left|{\mathfrak{u}}\right|}}}$ for
$j\in{\mathfrak{u}}$, and hence, if $k$ runs through the integers
$\\{t2^{m-w_{j_{\left|{\mathfrak{u}}\right|}}}+1,\ldots,(t+1)2^{m-w_{j_{\left|{\mathfrak{u}}\right|}}}-1\\}$,
the values of $\left\|z_{j}k/2^{m-w_{j}}\right\|$ are a subset of the values
of $\left\|z_{j}k/2^{m-w_{j}}\right\|$ when $k$ runs through the integers
$\\{1,\ldots,2^{m-w_{j}}-1\\}$. Then, due to [15, Corollary of Proposition 4],
we know that

$\sum_{k=1}^{2^{m-w_{j}}-1}\frac{1}{2^{m-w_{j}}\left\|z_{j}k/2^{m-w_{j}}\right\|}\leq
2(1+\log 2^{m-w_{j}})\leq 2(1+\log N).$

Combining the estimates for $\Sigma_{{\mathfrak{u}}}^{(1)}$ and
$\Sigma_{{\mathfrak{u}}}^{(2)}$, this yields

$\displaystyle\Sigma_{{\mathfrak{u}}}^{(1)}+\Sigma_{{\mathfrak{u}}}^{(2)}$
$\displaystyle=$ $\displaystyle 2^{w_{j_{\left|{\mathfrak{u}}\right|}}}(6\log
N)^{\left|{\mathfrak{u}}\right|}+H_{N,{\mathfrak{u}},{\bm{w}}}+(6\log
N)^{\left|{\mathfrak{u}}\right|}2^{w_{j_{\left|{\mathfrak{u}}\right|}}}(1+\log
N)$ $\displaystyle\leq$ $\displaystyle
2^{w_{j_{\left|{\mathfrak{u}}\right|}}+1}(6\log
N)^{\left|{\mathfrak{u}}\right|}(1+\log N)+H_{N,{\mathfrak{u}},{\bm{w}}},$

where

$H_{N,{\mathfrak{u}},{\bm{w}}}=\sum_{t=0}^{2^{w_{j_{\left|{\mathfrak{u}}\right|}}}-1}\
\
\sum_{k=t2^{m-w_{j_{\left|{\mathfrak{u}}\right|}}}+1}^{(t+1)2^{m-w_{j_{\left|{\mathfrak{u}}\right|}}}-1}\prod_{j\in{\mathfrak{u}}}u_{j}(k).$

Hence,

$\displaystyle T_{{\bm{\gamma}}}(N,{\bm{g}},{\bm{w}})$ $\displaystyle\leq$
$\displaystyle\sum_{\emptyset\neq{\mathfrak{u}}\subseteq[d^{*}]}\frac{\gamma_{{\mathfrak{u}}}}{N}2^{w_{j_{\left|{\mathfrak{u}}\right|}}+1}(6\log
N)^{\left|{\mathfrak{u}}\right|}(1+\log N)$
$\displaystyle+\sum_{\emptyset\neq{\mathfrak{u}}\subseteq[d^{*}]}\frac{\gamma_{{\mathfrak{u}}}}{N}H_{N,{\mathfrak{u}},{\bm{w}}}-\sum_{\emptyset\neq{\mathfrak{u}}\subseteq[d^{*}]}\gamma_{{\mathfrak{u}}}(\log
4)^{\left|{\mathfrak{u}}\right|}.$

∎

In the following, we write

$H_{s,N,{\bm{\gamma}},{\bm{w}}}:=\sum_{\emptyset\neq{\mathfrak{u}}\subseteq[s]}\gamma_{{\mathfrak{u}}}H_{N,{\mathfrak{u}},{\bm{w}}}.$

The next lemma motivates the choice of our quality function for the algorithm.
In particular, assuming we have already fixed the first (i.e., the least
significant) $v-1$ bits of $z_{s}$ for $s\in[d^{*}]$, we would like to find
out how good a specific choice for the $v$th bit is, in terms of
$H_{s,N,{\bm{\gamma}},{\bm{w}}}$. To this end, we consider the average over
all remaining $m-w_{s}-v$ bits.

For the base 2-digit representation of a $z_{s}$ with $1\leq s\leq d$, we
write

$z_{s}=z_{s}^{(0)}+z_{s}^{(1)}2+z_{s}^{(2)}2^{2}+\cdots.$

######  Lemma 3.

For an integer $v\in\\{1,\dots,m-w_{s}-1\\}$, with $m\in{\mathbb{N}}$ and
$s\in[d^{*}]$, let $z\in\\{0,1\\}$ and
${\bm{z}}=(z_{1},\ldots,z_{s})\in{\mathbb{Z}}^{s}$, and where the first $v-1$
bits of $z_{s}$ have been selected. We write
$z_{s,v-1}:=z_{s}^{(0)}+z_{s}^{(1)}2+\cdots+z_{s}^{(v-2)}2^{v-2}$, and
$\widetilde{z}_{s}:=z_{s}^{(0)}+z_{s}^{(1)}2+\cdots+z_{s}^{(v-2)}2^{v-2}+z2^{v-1}$.
Then the average of $H_{s,N,{\bm{\gamma}},{\bm{w}}}$ over the next $m-w_{s}-v$
bit choices for $z_{s}$ is given by

$\displaystyle\frac{1}{2^{m-w_{s}-v}}\sum_{\overline{z}\in{\mathbb{Z}}_{2^{m-w_{s}-v}}}H_{s,N,{\bm{\gamma}},{\bm{w}}}(z_{1},\ldots,z_{s-1},\widetilde{z}_{s}+\overline{z}2^{v})$
$\displaystyle=\sum_{t=v}^{m-w_{s}}\frac{1}{2^{t-v}}\sum_{\ell=0}^{2^{w_{s}}-1}\
\ \sum_{\begin{subarray}{c}k=\ell 2^{t}+1\\\ k\equiv
1{\;({\rm{mod}}\;2)}\end{subarray}}^{(\ell+1)2^{t}-1}\sum_{\begin{subarray}{c}\emptyset\neq{\mathfrak{u}}\subseteq[s]\\\
s\in{\mathfrak{u}}\end{subarray}}\gamma_{{\mathfrak{u}}}\log\left(\frac{1}{\sin^{2}(\pi
k\widetilde{z}_{s}/2^{v})}\right)$
$\displaystyle\times\prod_{\begin{subarray}{c}j\in{\mathfrak{u}}\\\ j\neq
s\end{subarray}}\log\left(\frac{1}{\sin^{2}\left(\pi
z_{j}\frac{k}{2^{t}}\,\frac{2^{m-w_{s}}}{2^{m-w_{j}}}\right)}\right)$
$\displaystyle+S_{N,v,{\bm{\gamma}},{\bm{w}}}({\bm{z}}),$ (12)

where the term $S_{N,v,{\bm{\gamma}},{\bm{w}}}({\bm{z}})$, which is
independent of $z$ and $\bar{z}$, is given by

$\displaystyle S_{N,v,{\bm{\gamma}},{\bm{w}}}({\bm{z}})$
$\displaystyle=\sum_{r=1}^{s-1}\sum_{\begin{subarray}{c}k=0\\\ k\not\equiv
0{\;({\rm{mod}}\;2^{m-w_{r}})}\end{subarray}}^{N-1}\sum_{\begin{subarray}{c}\emptyset\neq{\mathfrak{u}}\subseteq[r]\\\
r\in{\mathfrak{u}}\end{subarray}}\gamma_{{\mathfrak{u}}}\prod_{j\in{\mathfrak{u}}}\log\left(\frac{1}{\sin^{2}(\pi
z_{j}k/2^{m-w_{j}})}\right)$ $\displaystyle+\sum_{\ell=0}^{2^{w_{s}}-1}\ \
\sum_{t=1}^{v-1}\sum_{\begin{subarray}{c}k=\ell 2^{t}+1\\\ k\equiv
1{\;({\rm{mod}}\;2)}\end{subarray}}^{(\ell+1)2^{t}-1}\sum_{\begin{subarray}{c}\emptyset\neq{\mathfrak{u}}\subseteq[s]\\\
s\in{\mathfrak{u}}\end{subarray}}\gamma_{{\mathfrak{u}}}\left(\prod_{\begin{subarray}{c}j\in{\mathfrak{u}}\\\
j\neq s\end{subarray}}\log\left(\frac{1}{\sin^{2}\left(\pi
z_{j}\frac{k}{2^{t}}\,\frac{2^{m-w_{s}}}{2^{m-w_{j}}}\right)}\right)\right)$
$\displaystyle\times\log\left(\frac{1}{\sin^{2}(\pi z_{s,v-1}k/2^{t})}\right)$
$\displaystyle+\sum_{\ell=0}^{2^{w_{s}}-1}\ \
\sum_{t=v}^{m-w_{s}}\frac{2^{t-v}-1}{2^{t-v}}(\log
4)\sum_{\begin{subarray}{c}k=\ell 2^{t}+1\\\ k\equiv
1{\;({\rm{mod}}\;2)}\end{subarray}}^{(\ell+1)2^{t}-1}\sum_{\begin{subarray}{c}\emptyset\neq{\mathfrak{u}}\subseteq[s]\\\
s\in{\mathfrak{u}}\end{subarray}}\gamma_{{\mathfrak{u}}}\prod_{\begin{subarray}{c}j\in{\mathfrak{u}}\\\
j\neq s\end{subarray}}\log\left(\frac{1}{\sin^{2}\left(\pi
z_{j}\frac{k}{2^{t}}\,\frac{2^{m-w_{s}}}{2^{m-w_{j}}}\right)}\right).$

###### Proof.

For arbitrary ${\bm{z}}=(z_{1},\ldots,z_{s})$, we can rewrite the quantity
$H_{s,N,{\bm{\gamma}},{\bm{w}}}$ as follows,

$\displaystyle H_{s,N,{\bm{\gamma}},{\bm{w}}}$ $\displaystyle=$ $\displaystyle
H_{s,N,{\bm{\gamma}},{\bm{w}}}({\bm{z}})$ $\displaystyle:=$ $\displaystyle
N\sum_{\emptyset\neq{\mathfrak{u}}\subseteq[s]}\frac{\gamma_{{\mathfrak{u}}}}{N}H_{N,{\mathfrak{u}},{\bm{w}}}$
$\displaystyle=$
$\displaystyle\sum_{\emptyset\neq{\mathfrak{u}}\subseteq[s]}\gamma_{{\mathfrak{u}}}\sum_{t=0}^{2^{w_{j_{\left|{\mathfrak{u}}\right|}}}-1}\
\
\sum_{k=t2^{m-w_{j_{\left|{\mathfrak{u}}\right|}}}+1}^{(t+1)2^{m-w_{j_{\left|{\mathfrak{u}}\right|}}}-1}\prod_{j\in{\mathfrak{u}}}u_{j}(k)$
$\displaystyle=$
$\displaystyle\sum_{\emptyset\neq{\mathfrak{u}}\subseteq[s]}\gamma_{{\mathfrak{u}}}\sum_{t=0}^{2^{w_{j_{\left|{\mathfrak{u}}\right|}}}-1}\
\
\sum_{k=t2^{m-w_{j_{\left|{\mathfrak{u}}\right|}}}+1}^{(t+1)2^{m-w_{j_{\left|{\mathfrak{u}}\right|}}}-1}\prod_{j\in{\mathfrak{u}}}\log\left(\frac{1}{\sin^{2}(\pi
z_{j}k/2^{m-w_{j}})}\right)$ $\displaystyle=$
$\displaystyle\sum_{\emptyset\neq{\mathfrak{u}}\subseteq[s]}\gamma_{{\mathfrak{u}}}\sum_{\begin{subarray}{c}k=0\\\
k\not\equiv
0{\;({\rm{mod}}\;2^{m-w_{j_{\left|{\mathfrak{u}}\right|}}})}\end{subarray}}^{N-1}\prod_{j\in{\mathfrak{u}}}\log\left(\frac{1}{\sin^{2}(\pi
z_{j}k/2^{m-w_{j}})}\right)$ $\displaystyle=$
$\displaystyle\sum_{r=1}^{s}\sum_{\begin{subarray}{c}k=0\\\ k\not\equiv
0\text{ (mod
$2^{m-w_{r}}$)}\end{subarray}}^{N-1}\sum_{\begin{subarray}{c}\emptyset\neq{\mathfrak{u}}\subseteq[r]\\\
r\in{\mathfrak{u}}\end{subarray}}\gamma_{{\mathfrak{u}}}\prod_{j\in{\mathfrak{u}}}\log\left(\frac{1}{\sin^{2}(\pi
z_{j}k/2^{m-w_{j}})}\right).$ (13)

Hence, we would like to estimate

$\displaystyle\frac{1}{2^{m-w_{s}-v}}\sum_{\overline{z}\in{\mathbb{Z}}_{2^{m-w_{s}-v}}}\sum_{r=1}^{s}\sum_{\begin{subarray}{c}k=0\\\
k\not\equiv
0{\;({\rm{mod}}\;2^{m-w_{r}})}\end{subarray}}^{N-1}\sum_{\begin{subarray}{c}\emptyset\neq{\mathfrak{u}}\subseteq[r]\\\
r\in{\mathfrak{u}}\end{subarray}}\gamma_{{\mathfrak{u}}}\prod_{j\in{\mathfrak{u}}}\log\left(\frac{1}{\sin^{2}(\pi
z_{j}k/2^{m-w_{j}})}\right),$ (14)

where we now assume that
$z_{s}=z_{s,v-1}+z2^{v-1}+\overline{z}2^{v}=\widetilde{z}_{s}+\overline{z}2^{v}$.
Observe that all terms in the sum over $r\in\\{1,2,\ldots,s\\}$ for which
$1\leq r\leq s-1$ are independent of $\overline{z}$, and from this we obtain
the first sum in the definition of $S_{m,v,{\bm{\gamma}},{\bm{w}}}$. Therefore
we need to analyze the remaining part of (14), which equals

$\displaystyle\frac{1}{2^{m-w_{s}-v}}\sum_{\overline{z}\in{\mathbb{Z}}_{2^{m-w_{s}-v}}}\sum_{\begin{subarray}{c}k=0\\\
k\not\equiv
0{\;({\rm{mod}}\;2^{m-w_{s}})}\end{subarray}}^{N-1}\sum_{\begin{subarray}{c}\emptyset\neq{\mathfrak{u}}\subseteq[s]\\\
s\in{\mathfrak{u}}\end{subarray}}\gamma_{{\mathfrak{u}}}\prod_{j\in{\mathfrak{u}}}\log\left(\frac{1}{\sin^{2}(\pi
z_{j}k/2^{m-w_{j}})}\right).$

Now, we are going to use the general identity

$\sum_{k=1}^{2^{p}-1}f(k/2^{p})=\sum_{t=1}^{p}\sum_{\begin{subarray}{c}k=1\\\
k\equiv 1{\;({\rm{mod}}\;2)}\end{subarray}}^{2^{t}-1}f(k/2^{t}).$ (15)

Then, we can write

$\displaystyle\frac{1}{2^{m-w_{s}-v}}\sum_{\overline{z}\in{\mathbb{Z}}_{2^{m-w_{s}-v}}}\sum_{\begin{subarray}{c}k=0\\\
k\not\equiv
0{\;({\rm{mod}}\;2^{m-w_{s}})}\end{subarray}}^{N-1}\sum_{\begin{subarray}{c}\emptyset\neq{\mathfrak{u}}\subseteq[s]\\\
s\in{\mathfrak{u}}\end{subarray}}\gamma_{{\mathfrak{u}}}\prod_{j\in{\mathfrak{u}}}\log\left(\frac{1}{\sin^{2}(\pi
z_{j}k/2^{m-w_{j}})}\right)$ $\displaystyle=$
$\displaystyle\frac{1}{2^{m-w_{s}-v}}\sum_{\overline{z}\in{\mathbb{Z}}_{2^{m-w_{s}-v}}}\sum_{\ell=0}^{2^{w_{s}}-1}\
\
\sum_{k=\ell\,2^{m-w_{s}}+1}^{(\ell+1)2^{m-w_{s}}-1}\sum_{\begin{subarray}{c}\emptyset\neq{\mathfrak{u}}\subseteq[s]\\\
s\in{\mathfrak{u}}\end{subarray}}\gamma_{{\mathfrak{u}}}\prod_{j\in{\mathfrak{u}}}\log\left(\frac{1}{\sin^{2}(\pi
z_{j}k/2^{m-w_{j}})}\right)$ $\displaystyle=$
$\displaystyle\frac{1}{2^{m-w_{s}-v}}\sum_{\overline{z}\in{\mathbb{Z}}_{2^{m-w_{s}-v}}}\sum_{\ell=0}^{2^{w_{s}}-1}\
\
\sum_{k=1}^{2^{m-w_{s}}-1}\sum_{\begin{subarray}{c}\emptyset\neq{\mathfrak{u}}\subseteq[s]\\\
s\in{\mathfrak{u}}\end{subarray}}\gamma_{{\mathfrak{u}}}\prod_{j\in{\mathfrak{u}}}\log\left(\frac{1}{\sin^{2}(\pi
z_{j}(k+\ell\,2^{m-w_{s}})/2^{m-w_{j}})}\right)$ $\displaystyle=$
$\displaystyle\frac{1}{2^{m-w_{s}-v}}\sum_{\overline{z}\in{\mathbb{Z}}_{2^{m-w_{s}-v}}}\sum_{\ell=0}^{2^{w_{s}}-1}\
\
\sum_{k=1}^{2^{m-w_{s}}-1}\sum_{\begin{subarray}{c}\emptyset\neq{\mathfrak{u}}\subseteq[s]\\\
s\in{\mathfrak{u}}\end{subarray}}\gamma_{{\mathfrak{u}}}$
$\displaystyle\times\prod_{j\in{\mathfrak{u}}}\log\left(\frac{1}{\sin^{2}(\pi
z_{j}\ell\,2^{w_{j}-w_{s}}+\pi z_{j}k/2^{m-w_{j}})}\right)$ $\displaystyle=$
$\displaystyle\frac{1}{2^{m-w_{s}-v}}\sum_{\overline{z}\in{\mathbb{Z}}_{2^{m-w_{s}-v}}}\sum_{\ell=0}^{2^{w_{s}}-1}\
\
\sum_{k=1}^{2^{m-w_{s}}-1}\sum_{\begin{subarray}{c}\emptyset\neq{\mathfrak{u}}\subseteq[s]\\\
s\in{\mathfrak{u}}\end{subarray}}\gamma_{{\mathfrak{u}}}$
$\displaystyle\times\prod_{j\in{\mathfrak{u}}}\log\left(\frac{1}{\sin^{2}(\pi
z_{j}\ell\,2^{w_{j}-w_{s}}+(\pi z_{j}k/2^{m-w_{s}})2^{w_{j}-w_{s}})}\right)$
$\displaystyle=$
$\displaystyle\frac{1}{2^{m-w_{s}-v}}\sum_{\overline{z}\in{\mathbb{Z}}_{2^{m-w_{s}-v}}}\sum_{\ell=0}^{2^{w_{s}}-1}\
\ \sum_{t=1}^{m-w_{s}}\sum_{\begin{subarray}{c}k=1\\\ k\equiv
1{\;({\rm{mod}}\;2)}\end{subarray}}^{2^{t}-1}\sum_{\begin{subarray}{c}\emptyset\neq{\mathfrak{u}}\subseteq[s]\\\
s\in{\mathfrak{u}}\end{subarray}}\gamma_{{\mathfrak{u}}}$
$\displaystyle\times\prod_{j\in{\mathfrak{u}}}\log\left(\frac{1}{\sin^{2}(\pi
z_{j}\ell\,2^{w_{j}-w_{s}}+(\pi z_{j}k/2^{t})2^{w_{j}-w_{s}})}\right)$
$\displaystyle=$
$\displaystyle\frac{1}{2^{m-w_{s}-v}}\sum_{\overline{z}\in{\mathbb{Z}}_{2^{m-w_{s}-v}}}\sum_{\ell=0}^{2^{w_{s}}-1}\
\ \sum_{t=1}^{m-w_{s}}\sum_{\begin{subarray}{c}k=1\\\ k\equiv
1{\;({\rm{mod}}\;2)}\end{subarray}}^{2^{t}-1}\sum_{\begin{subarray}{c}\emptyset\neq{\mathfrak{u}}\subseteq[s]\\\
s\in{\mathfrak{u}}\end{subarray}}\gamma_{{\mathfrak{u}}}$
$\displaystyle\times\prod_{j\in{\mathfrak{u}}}\log\left(\frac{1}{\sin^{2}\left(\pi
z_{j}\frac{\ell
2^{t}+k}{2^{t}}\,\frac{2^{m-w_{s}}}{2^{m-w_{j}}}\right)}\right)$
$\displaystyle=$
$\displaystyle\frac{1}{2^{m-w_{s}-v}}\sum_{\overline{z}\in{\mathbb{Z}}_{2^{m-w_{s}-v}}}\sum_{\ell=0}^{2^{w_{s}}-1}\
\ \sum_{t=1}^{m-w_{s}}\sum_{\begin{subarray}{c}k=\ell\,2^{t}+1\\\ k\equiv
1{\;({\rm{mod}}\;2)}\end{subarray}}^{(\ell+1)2^{t}-1}\sum_{\begin{subarray}{c}\emptyset\neq{\mathfrak{u}}\subseteq[s]\\\
s\in{\mathfrak{u}}\end{subarray}}\gamma_{{\mathfrak{u}}}\prod_{j\in{\mathfrak{u}}}\log\left(\frac{1}{\sin^{2}\left(\pi
z_{j}\frac{k}{2^{t}}\,\frac{2^{m-w_{s}}}{2^{m-w_{j}}}\right)}\right)$
$\displaystyle=$ $\displaystyle\sum_{\ell=0}^{2^{w_{s}}-1}\ \
\sum_{t=1}^{m-w_{s}}\sum_{\begin{subarray}{c}k=\ell 2^{t}+1\\\ k\equiv
1{\;({\rm{mod}}\;2)}\end{subarray}}^{(\ell+1)2^{t}-1}\sum_{\begin{subarray}{c}\emptyset\neq{\mathfrak{u}}\subseteq[s]\\\
s\in{\mathfrak{u}}\end{subarray}}\gamma_{{\mathfrak{u}}}\left(\prod_{\begin{subarray}{c}j\in{\mathfrak{u}}\\\
j\neq s\end{subarray}}\log\left(\frac{1}{\sin^{2}\left(\pi
z_{j}\frac{k}{2^{t}}\,\frac{2^{m-w_{s}}}{2^{m-w_{j}}}\right)}\right)\right)$
$\displaystyle\times\frac{1}{2^{m-w_{s}-v}}\sum_{\overline{z}\in{\mathbb{Z}}_{2^{m-w_{s}-v}}}\log\left(\frac{1}{\sin^{2}(\pi(\widetilde{z}_{s}+\overline{z}2^{v})k/2^{t})}\right),$

where we remind the reader that $\widetilde{z}_{s}$ =
$z_{s}^{(0)}+z_{s}^{(1)}2+\cdots+z_{s}^{(v-2)}2^{v-2}+z2^{v-1}$. Therefore, in
the above summation, if $t\in\\{1,2,\ldots,v-1\\}$, then

$\sin^{2}(\pi(\widetilde{z}_{s}+\overline{z}2^{v})k/2^{t})=\sin^{2}(\pi(z_{s}^{(0)}+\cdots+z_{s}^{(v-2)}2^{v-2})k/2^{t}).$

Consequently, we obtain

$\displaystyle\frac{1}{2^{m-w_{s}-v}}\sum_{\overline{z}\in{\mathbb{Z}}_{2^{m-w_{s}-v}}}\sum_{\begin{subarray}{c}k=0\\\
k\not\equiv
0{\;({\rm{mod}}\;2^{m-w_{s}})}\end{subarray}}^{N-1}\sum_{\begin{subarray}{c}\emptyset\neq{\mathfrak{u}}\subseteq[s]\\\
s\in{\mathfrak{u}}\end{subarray}}\gamma_{{\mathfrak{u}}}\prod_{j\in{\mathfrak{u}}}\log\left(\frac{1}{\sin^{2}(\pi
z_{j}k/2^{m-w_{j}})}\right)$ $\displaystyle=$
$\displaystyle\sum_{\ell=0}^{2^{w_{s}}-1}\ \
\sum_{t=1}^{m-w_{s}}\sum_{\begin{subarray}{c}k=\ell 2^{t}+1\\\ k\equiv
1{\;({\rm{mod}}\;2)}\end{subarray}}^{(\ell+1)2^{t}-1}\sum_{\begin{subarray}{c}\emptyset\neq{\mathfrak{u}}\subseteq[s]\\\
s\in{\mathfrak{u}}\end{subarray}}\gamma_{{\mathfrak{u}}}\left(\prod_{\begin{subarray}{c}j\in{\mathfrak{u}}\\\
j\neq s\end{subarray}}\log\left(\frac{1}{\sin^{2}\left(\pi
z_{j}\frac{k}{2^{t}}\,\frac{2^{m-w_{s}}}{2^{m-w_{j}}}\right)}\right)\right)$
$\displaystyle\times\frac{1}{2^{m-w_{s}-v}}\sum_{\overline{z}\in{\mathbb{Z}}_{2^{m-w_{s}-v}}}\log\left(\frac{1}{\sin^{2}(\pi(\widetilde{z}_{s}+\overline{z}2^{v})k/2^{t})}\right)$
$\displaystyle=$ $\displaystyle\sum_{\ell=0}^{2^{w_{s}}-1}\ \
\sum_{t=1}^{v-1}\sum_{\begin{subarray}{c}k=\ell 2^{t}+1\\\ k\equiv
1{\;({\rm{mod}}\;2)}\end{subarray}}^{(\ell+1)2^{t}-1}\sum_{\begin{subarray}{c}\emptyset\neq{\mathfrak{u}}\subseteq[s]\\\
s\in{\mathfrak{u}}\end{subarray}}\gamma_{{\mathfrak{u}}}\left(\prod_{\begin{subarray}{c}j\in{\mathfrak{u}}\\\
j\neq s\end{subarray}}\log\left(\frac{1}{\sin^{2}\left(\pi
z_{j}\frac{k}{2^{t}}\,\frac{2^{m-w_{s}}}{2^{m-w_{j}}}\right)}\right)\right)$
$\displaystyle\times\log\left(\frac{1}{\sin^{2}(\pi(z_{s}^{(0)}+z_{s}^{(1)}2+\cdots+z_{s}^{(v-2)}2^{v-2})k/2^{t})}\right)$
$\displaystyle+$ $\displaystyle\sum_{\ell=0}^{2^{w_{s}}-1}\ \
\sum_{t=v}^{m-w_{s}}\sum_{\begin{subarray}{c}k=\ell 2^{t}+1\\\ k\equiv
1{\;({\rm{mod}}\;2)}\end{subarray}}^{(\ell+1)2^{t}-1}\sum_{\begin{subarray}{c}\emptyset\neq{\mathfrak{u}}\subseteq[s]\\\
s\in{\mathfrak{u}}\end{subarray}}\gamma_{{\mathfrak{u}}}\left(\prod_{\begin{subarray}{c}j\in{\mathfrak{u}}\\\
j\neq s\end{subarray}}\log\left(\frac{1}{\sin^{2}\left(\pi
z_{j}\frac{k}{2^{t}}\,\frac{2^{m-w_{s}}}{2^{m-w_{j}}}\right)}\right)\right)$
$\displaystyle\times\frac{1}{2^{m-w_{s}-v}}\sum_{\overline{z}\in{\mathbb{Z}}_{2^{m-w_{s}-v}}}\log\left(\frac{1}{\sin^{2}(\pi(\widetilde{z}_{s}+\overline{z}2^{v})k/2^{t})}\right).$

For the last expression, we argue as in the proof of Lemma 6 in [8] to obtain,
for $t\in\\{v,\dots,m-w_{s}\\}$,

$\displaystyle\sum_{\ell=0}^{2^{w_{s}}-1}\ \
\sum_{t=v}^{m-w_{s}}\sum_{\begin{subarray}{c}k=\ell 2^{t}+1\\\ k\equiv
1{\;({\rm{mod}}\;2)}\end{subarray}}^{(\ell+1)2^{t}-1}\sum_{\begin{subarray}{c}\emptyset\neq{\mathfrak{u}}\subseteq[s]\\\
s\in{\mathfrak{u}}\end{subarray}}\gamma_{{\mathfrak{u}}}\prod_{\begin{subarray}{c}j\in{\mathfrak{u}}\\\
j\neq s\end{subarray}}\log\left(\frac{1}{\sin^{2}\left(\pi
z_{j}\frac{k}{2^{t}}\,\frac{2^{m-w_{s}}}{2^{m-w_{j}}}\right)}\right)$
$\displaystyle\times\frac{1}{2^{m-w_{s}-v}}\sum_{\overline{z}\in{\mathbb{Z}}_{2^{m-w_{s}-v}}}\log\left(\frac{1}{\sin^{2}(\pi(\widetilde{z}_{s}+\overline{z}2^{v})k/2^{t})}\right)$
$\displaystyle=$ $\displaystyle\sum_{\ell=0}^{2^{w_{s}}-1}\ \
\sum_{t=v}^{m-w_{s}}\sum_{\begin{subarray}{c}k=\ell 2^{t}+1\\\ k\equiv
1{\;({\rm{mod}}\;2)}\end{subarray}}^{(\ell+1)2^{t}-1}\sum_{\begin{subarray}{c}\emptyset\neq{\mathfrak{u}}\subseteq[s]\\\
s\in{\mathfrak{u}}\end{subarray}}\gamma_{{\mathfrak{u}}}\prod_{\begin{subarray}{c}j\in{\mathfrak{u}}\\\
j\neq s\end{subarray}}\log\left(\frac{1}{\sin^{2}\left(\pi
z_{j}\frac{k}{2^{t}}\,\frac{2^{m-w_{s}}}{2^{m-w_{j}}}\right)}\right)$
$\displaystyle\times\frac{2^{m-w_{s}-t}}{2^{m-w_{s}-v}}\sum_{\overline{z}\in{\mathbb{Z}}_{2^{t-v}}}\log\left(\frac{1}{\sin^{2}(\pi(\widetilde{z}_{s}+\overline{z}2^{v})k/2^{t})}\right)$
$\displaystyle=$ $\displaystyle\sum_{\ell=0}^{2^{w_{s}}-1}\ \
\sum_{t=v}^{m-w_{s}}\sum_{\begin{subarray}{c}k=\ell 2^{t}+1\\\ k\equiv
1{\;({\rm{mod}}\;2)}\end{subarray}}^{(\ell+1)2^{t}-1}\sum_{\begin{subarray}{c}\emptyset\neq{\mathfrak{u}}\subseteq[s]\\\
s\in{\mathfrak{u}}\end{subarray}}\gamma_{{\mathfrak{u}}}\prod_{\begin{subarray}{c}j\in{\mathfrak{u}}\\\
j\neq s\end{subarray}}\log\left(\frac{1}{\sin^{2}\left(\pi
z_{j}\frac{k}{2^{t}}\,\frac{2^{m-w_{s}}}{2^{m-w_{j}}}\right)}\right)$
$\displaystyle\times\left((1-2^{v-t})\log
4+2^{v-t}\log\left(\frac{1}{\sin^{2}(\pi\widetilde{z}_{s}k/2^{v})}\right)\right),$

where in the last step we proceeded exactly as in the proof of Lemma 6 in [8].
This, together with the previous identity yields the claim. ∎

We observe that in Lemma 3 only the first term depends on the $v$th bit $z$ of
$z_{s}$, while $S_{N,v,{\bm{\gamma}},{\bm{w}}}({\bm{z}})$ is independent of
this bit. This now leads to the introduction of the following digit-wise
quality function for the reduced CBC-DBD algorithm which is based on the first
term in (12). Note that the quality function is not exactly equal to the first
term in (12), but we add further terms that, though independent of the
argument of the function, facilitate fast implementation (see Section 4).

######  Definition 2.

Let $x\in{\mathbb{N}}$ be an odd integer, let $m,d^{*}\in{\mathbb{N}}$, let
${\bm{w}}=(w_{j})_{j\geq 1}$ be a sequence of reduction indices in
${\mathbb{N}}_{0}$ with $0=w_{1}\leq w_{2}\leq\cdots$, and let
${\bm{\gamma}}=(\gamma_{j})_{j\geq 1}$ be a sequence of positive weights. For
$1\leq s\leq d^{*}$ and $1\leq v\leq m-w_{s}$ we define the quality function
$h_{s,v,m,{\bm{\gamma}},{\bm{w}}}:{\mathbb{Z}}\rightarrow{\mathbb{R}}$ as

$\displaystyle h_{s,v,m,{\bm{\gamma}},{\bm{w}}}(x):$ $\displaystyle=$
$\displaystyle\sum_{t=v}^{m-w_{s}}\frac{1}{2^{t-v}}\sum_{\ell=0}^{2^{w_{s}}-1}\
\ \sum_{\begin{subarray}{c}k=\ell 2^{t}+1\\\ k\equiv
1{\;({\rm{mod}}\;2)}\end{subarray}}^{(\ell+1)2^{t}-1}\sum_{\begin{subarray}{c}{\mathfrak{u}}\subseteq[s]\\\
s\in{\mathfrak{u}}\end{subarray}}\gamma_{{\mathfrak{u}}\setminus\\{s\\}}\prod_{\begin{subarray}{c}j\in{\mathfrak{u}}\\\
j\neq s\end{subarray}}\log\left(\frac{1}{\sin^{2}\left(\pi
z_{j}\frac{k}{2^{t}}\,\frac{2^{m-w_{s}}}{2^{m-w_{j}}}\right)}\right)$
$\displaystyle\times\left(1+\gamma_{s}\log\left(\frac{1}{\sin^{2}(\pi
kx/2^{v})}\right)\right),$

where we assume that $z_{j}\in\\{1,3,\ldots,2^{m-w_{j}}-1\\}$ is odd for
$j\in[s-1]$.

Based on the quality function $h_{s,v,m,{\bm{\gamma}},{\bm{w}}}$, we formulate
the following reduced component-by-component digit-by-digit (CBC-DBD)
algorithm.

Algorithm 1 Reduced component-by-component digit-by-digit construction

Input: Integer $m\in{\mathbb{N}}$, dimension $d,{\bm{w}}=(w_{j})_{j\geq 1}$
with $0=w_{1}\leq w_{2}\leq\cdots$ and $Y_{j}=2^{w_{j}}$ for
$j\in\\{1,\dots,d\\}$, and positive weights ${\bm{\gamma}}=(\gamma_{j})_{j\geq
1}$.

Set $z_{1}=z_{1,m}=1$ and $z_{1,1}=z_{1,2}=\cdots=z_{d,1}=1$.

If $d>d^{*}$, set $z_{d^{*}+1}=\cdots=z_{d}=1$.

for $s=2$ to $\min\\{d,d^{*}\\}$ do

for $v=2$ to $m-w_{s}$ do

$z^{\ast}=\underset{z\in\\{0,1\\}}{\operatorname*{argmin}}\;h_{s,v,m,{\bm{\gamma}},{\bm{w}}}(z_{s,v-1}+z\,2^{v-1})$

$z_{s,v}=z_{s,v-1}+z^{\ast}\,2^{v-1}$

end for

$z_{s}=z_{s,m-w_{s}}$

end for

Set ${\bm{z}}=(Y_{1}z_{1},\ldots,Y_{d}z_{d})$.

Return: Generating vector ${\bm{z}}$ for $N=2^{m}$.

###  3.3 Error convergence behavior of the constructed lattice rules

In the following, we study the worst-case error behavior of the constructed
lattice rules, i.e, we want to show that under certain suitable conditions on
the weights ${\bm{\gamma}}$, Algorithm 1 can construct generating vectors
which yield lattice point sets with very good properties if they are used as
integration nodes in a QMC rule. For
${\bm{z}}=(Y_{1}z_{1},\ldots,Y_{d}z_{d})$, we write ${\bm{z}}_{[s]}$ to denote
the vector $(z_{1},\ldots,z_{s})$ for $s\in[d]$.

######  Theorem 2.

Let $m\in{\mathbb{N}}$, $N=2^{m}$, ${\bm{w}}=(w_{j})_{j\geq 1}$ in
${\mathbb{N}}_{0}$ with $0=w_{1}\leq w_{2}\leq\cdots$, and let
${\bm{\gamma}}=(\gamma_{j})_{j\geq 1}$ be positive product weights.
Furthermore, let the generating vector
${\bm{z}}=(Y_{1}z_{1},\ldots,Y_{d}z_{d})\in{\mathbb{Z}}^{d}$ be constructed by
Algorithm 1. Denote by ${\bm{z}}_{[s]}$ the vector $(z_{1},\ldots,z_{s})$ for
$s\in[d]$. Then the following estimate holds for $s\in[d^{*}]$,

$H_{s,N,{\bm{\gamma}},{\bm{w}}}({\bm{z}}_{[s]})\leq(1+\gamma_{s}\log
4)H_{s-1,N,{\bm{\gamma}},{\bm{w}}}({\bm{z}}_{[s-1]})+\gamma_{s}(\log
4)(2^{m}-2^{w_{s}}).$

###### Proof.

We will prove the stated estimate via an inductive argument over the selection
of the $m-w_{s}$ bits of the component $z_{s}$ for $s\in[d^{*}]$. We first
observe that according to the formulation of Algorithm 1, the $v$th bit of
$z_{s}$ with $v\in\\{2,\dots,m-w_{s}\\}$, has been selected by minimizing
$h_{s,v,m,{\bm{\gamma}},{\bm{w}}}(z_{s,v-1}+z2^{v-1})$ with respect to the
choices $z\in\\{0,1\\}$, and that we have chosen $z_{s,v-1}$ by the same
algorithm. By Lemma 3 and Definition 2 this is equivalent to minimizing

$\frac{1}{2^{m-w_{s}-v}}\sum_{\overline{z}\in{\mathbb{Z}}_{2^{m-w_{s}-v}}}H_{s,N,{\bm{\gamma}},{\bm{w}}}(z_{1},\ldots,z_{s-1},z_{s,v-1}+z2^{v-1}+\overline{z}2^{v})$

with respect to $z\in\\{0,1\\}$. By the standard averaging argument, this
yields

$\displaystyle\operatorname*{argmin}_{z\in\\{0,1\\}}\frac{1}{2^{m-w_{s}-v}}\sum_{\overline{z}\in{\mathbb{Z}}_{2^{m-w_{s}-v}}}H_{s,N,{\bm{\gamma}},{\bm{w}}}(z_{1},\ldots,z_{s-1},z_{s,v-1}+z2^{v-1}+\overline{z}2^{v})$
$\displaystyle\leq$
$\displaystyle\frac{1}{2}\frac{1}{2^{m-w_{s}-v}}\sum_{z\in{\mathbb{Z}}_{2}}\sum_{\overline{z}\in{\mathbb{Z}}_{2^{m-w_{s}-v}}}H_{s,N,{\bm{\gamma}},{\bm{w}}}(z_{1},\ldots,z_{s-1},z_{s,v-1}+z2^{v-1}+\overline{z}2^{v})$
$\displaystyle=$
$\displaystyle\frac{1}{2^{m-w_{s}-v+1}}\sum_{\overline{z}\in{\mathbb{Z}}_{2^{m-w_{s}-v+1}}}H_{s,N,{\bm{\gamma}},{\bm{w}}}(z_{1},\ldots,z_{s-1},\underbrace{z_{s,v-2}+\tilde{z}\,2^{v-2}}_{=z_{s,v-1}}+\bar{z}\,2^{v-1}),$

where we split up $z_{s,v-1}$ according to Algorithm 1 such that $\tilde{z}$
is the $(v-1)$th bit of $z_{s}$, selected in the previous step of the
algorithm. Noting that the inequality in (3.3) holds for any
$v\in\\{2,\ldots,m-w_{s}\\}$, we can inductively use this estimate for
$v=m-w_{s},m-w_{s}-1,\ldots,2$ to obtain

$\displaystyle H_{s,N,{\bm{\gamma}},{\bm{w}}}({\bm{z}}_{[s]})$
$\displaystyle=$
$\displaystyle\operatorname*{argmin}_{z\in\\{0,1\\}}H_{s,N,{\bm{\gamma}},{\bm{w}}}(z_{1},\ldots,z_{s-1},z_{s,m-w_{s}-1}+z2^{m-w_{s}-1})$
(17) $\displaystyle\leq$
$\displaystyle\frac{1}{2^{m-w_{s}-1}}\sum_{\overline{z}\in{\mathbb{Z}}_{2^{m-w_{s}-1}}}H_{s,N,{\bm{\gamma}},{\bm{w}}}(z_{1},\ldots,z_{s-1},1+\overline{z}2),$

where we used that $z_{s,1}=1$. Now setting $v=1$ in our expression in Lemma 3
to equate the right-hand side term in (17), we get

$\displaystyle H_{s,N,{\bm{\gamma}},{\bm{w}}}({\bm{z}}_{[s]})$
$\displaystyle\leq$
$\displaystyle\sum_{t=1}^{m-w_{s}}\frac{1}{2^{t-1}}\sum_{\ell=0}^{2^{w_{s}}-1}\sum_{\begin{subarray}{c}k=\ell
2^{t}+1\\\ k\equiv
1{\;({\rm{mod}}\;2)}\end{subarray}}^{(\ell+1)2^{t}-1}\sum_{\begin{subarray}{c}\emptyset\neq{\mathfrak{u}}\subseteq[s]\\\
s\in{\mathfrak{u}}\end{subarray}}\gamma_{{\mathfrak{u}}}\prod_{\begin{subarray}{c}j\in{\mathfrak{u}}\\\
j\neq s\end{subarray}}\log\left(\frac{1}{\sin^{2}\left(\pi
z_{j}\frac{k}{2^{t}}\frac{2^{m-w_{s}}}{2^{m-w_{j}}}\right)}\right)$
$\displaystyle\times\log\left(\frac{1}{\sin^{2}(\pi k/2)}\right)$
$\displaystyle+\sum_{r=1}^{s-1}\sum_{\begin{subarray}{c}k=0\\\ k\not\equiv
0{\;({\rm{mod}}\;2^{m-w_{r}})}\end{subarray}}^{N-1}\sum_{\begin{subarray}{c}\emptyset\neq{\mathfrak{u}}\subseteq[r]\\\
r\in{\mathfrak{u}}\end{subarray}}\gamma_{{\mathfrak{u}}}\prod_{j\in{\mathfrak{u}}}\log\left(\frac{1}{\sin^{2}(\pi
z_{j}k/2^{m-w_{j}})}\right)$ $\displaystyle+\sum_{\ell=0}^{2^{w_{s}}-1}\ \
\sum_{t=1}^{m-w_{s}}\frac{2^{t-1}-1}{2^{t-1}}(\log
4)\sum_{\begin{subarray}{c}k=\ell 2^{t}+1\\\ k\equiv
1{\;({\rm{mod}}\;2)}\end{subarray}}^{(\ell+1)2^{t}-1}\sum_{\begin{subarray}{c}\emptyset\neq{\mathfrak{u}}\subseteq[s]\\\
s\in{\mathfrak{u}}\end{subarray}}\gamma_{{\mathfrak{u}}}$
$\displaystyle\times\prod_{\begin{subarray}{c}j\in{\mathfrak{u}}\\\ j\neq
s\end{subarray}}\log\left(\frac{1}{\sin^{2}\left(\pi
z_{j}\frac{k}{2^{t}}\,\frac{2^{m-w_{s}}}{2^{m-w_{j}}}\right)}\right).$

Note that for odd $k$ we have $\log(\sin^{-2}(\pi k/2))=\log 1=0$, so we
obtain, using (13) and (15),

$\displaystyle H_{s,N,{\bm{\gamma}},{\bm{w}}}({\bm{z}}_{[s]})$
$\displaystyle\leq$
$\displaystyle\sum_{r=1}^{s-1}\sum_{\begin{subarray}{c}k=0\\\ k\not\equiv
0{\;({\rm{mod}}\;2^{m-w_{r}})}\end{subarray}}^{N-1}\sum_{\begin{subarray}{c}\emptyset\neq{\mathfrak{u}}\subseteq[r]\\\
r\in{\mathfrak{u}}\end{subarray}}\gamma_{{\mathfrak{u}}}\prod_{j\in{\mathfrak{u}}}\log\left(\frac{1}{\sin^{2}(\pi
z_{j}k/2^{m-w_{j}})}\right)$ $\displaystyle+\sum_{\ell=0}^{2^{w_{s}}-1}\ \
\sum_{t=1}^{m-w_{s}}(\log 4)\sum_{\begin{subarray}{c}k=\ell 2^{t}+1\\\ k\equiv
1{\;({\rm{mod}}\;2)}\end{subarray}}^{(\ell+1)2^{t}-1}\sum_{\begin{subarray}{c}\emptyset\neq{\mathfrak{u}}\subseteq[s]\\\
s\in{\mathfrak{u}}\end{subarray}}\gamma_{{\mathfrak{u}}}\prod_{\begin{subarray}{c}j\in{\mathfrak{u}}\\\
j\neq s\end{subarray}}\log\left(\frac{1}{\sin^{2}\left(\pi
z_{j}\frac{k}{2^{t}}\,\frac{2^{m-w_{s}}}{2^{m-w_{j}}}\right)}\right)$
$\displaystyle=$ $\displaystyle
H_{s-1,N,{\bm{\gamma}},{\bm{w}}}({\bm{z}}_{[s-1]})$ $\displaystyle+(\log
4)\sum_{\ell=0}^{2^{w_{s}}-1}\ \
\sum_{t=1}^{m-w_{s}}\sum_{\begin{subarray}{c}k=\ell 2^{t}+1\\\ k\equiv
1{\;({\rm{mod}}\;2)}\end{subarray}}^{(\ell+1)2^{t}-1}\sum_{\begin{subarray}{c}\emptyset\neq{\mathfrak{u}}\subseteq[s]\\\
s\in{\mathfrak{u}}\end{subarray}}\gamma_{{\mathfrak{u}}}\prod_{\begin{subarray}{c}j\in{\mathfrak{u}}\\\
j\neq s\end{subarray}}\log\left(\frac{1}{\sin^{2}\left(\pi
z_{j}\frac{k}{2^{t}}\,\frac{2^{m-w_{s}}}{2^{m-w_{j}}}\right)}\right)$
$\displaystyle=$ $\displaystyle
H_{s-1,N,{\bm{\gamma}},{\bm{w}}}({\bm{z}}_{[s-1]})$ $\displaystyle+(\log
4)\sum_{\ell=0}^{2^{w_{s}}-1}\sum_{k=\ell
2^{m-w_{s}}+1}^{(\ell+1)2^{m-w_{s}}-1}\sum_{\begin{subarray}{c}\emptyset\neq{\mathfrak{u}}\subseteq[s]\\\
s\in{\mathfrak{u}}\end{subarray}}\gamma_{{\mathfrak{u}}}\prod_{\begin{subarray}{c}j\in{\mathfrak{u}}\\\
j\neq s\end{subarray}}\log\left(\frac{1}{\sin^{2}\left(\pi
z_{j}k/2^{m-w_{j}}\right)}\right)$ $\displaystyle=$ $\displaystyle
H_{s-1,N,{\bm{\gamma}},{\bm{w}}}({\bm{z}}_{[s-1]})$ $\displaystyle+(\log
4)\,\gamma_{s}\sum_{\begin{subarray}{c}k=0\\\ k\not\equiv
0{\;({\rm{mod}}\;2^{m-w_{s}})}\end{subarray}}^{N-1}\sum_{{\mathfrak{u}}\subseteq[s-1]}\gamma_{{\mathfrak{u}}}\prod_{j\in{\mathfrak{u}}}\log\left(\frac{1}{\sin^{2}\left(\pi
z_{j}k/2^{m-w_{j}}\right)}\right)$ $\displaystyle=$ $\displaystyle
H_{s-1,N,{\bm{\gamma}},{\bm{w}}}({\bm{z}}_{[s-1]})$ $\displaystyle+(\log
4)\,\gamma_{s}\left[\sum_{\begin{subarray}{c}k=0\\\ k\not\equiv
0{\;({\rm{mod}}\;2^{m-w_{s}})}\end{subarray}}^{N-1}1\right.$
$\displaystyle+\left.\sum_{\begin{subarray}{c}k=0\\\ k\not\equiv
0{\;({\rm{mod}}\;2^{m-w_{s}})}\end{subarray}}^{N-1}\sum_{\emptyset\neq{\mathfrak{u}}\subseteq[s-1]}\gamma_{{\mathfrak{u}}}\prod_{j\in{\mathfrak{u}}}\log\left(\frac{1}{\sin^{2}\left(\pi
z_{j}k/2^{m-w_{j}}\right)}\right)\right]$ $\displaystyle=$ $\displaystyle
H_{s-1,N,{\bm{\gamma}},{\bm{w}}}({\bm{z}}_{[s-1]})$ $\displaystyle+(\log
4)\,\gamma_{s}\left[(2^{m}-2^{w_{s}})\phantom{\sum_{\begin{subarray}{c}k=0\\\
k\not\equiv 0{\;({\rm{mod}}\;2^{m-w_{s}})}\end{subarray}}^{N-1}}\right.$
$\displaystyle+\left.\sum_{r=1}^{s-1}\sum_{\begin{subarray}{c}k=0\\\
k\not\equiv
0{\;({\rm{mod}}\;2^{m-w_{s}})}\end{subarray}}^{N-1}\sum_{\begin{subarray}{c}\emptyset\neq{\mathfrak{u}}\subseteq[r-1]\\\
r\in{\mathfrak{u}}\end{subarray}}\gamma_{{\mathfrak{u}}}\prod_{j\in{\mathfrak{u}}}\log\left(\frac{1}{\sin^{2}\left(\pi
z_{j}k/2^{m-w_{j}}\right)}\right)\right]$ $\displaystyle\leq$ $\displaystyle
H_{s-1,N,{\bm{\gamma}},{\bm{w}}}({\bm{z}}_{[s-1]})$ $\displaystyle+(\log
4)\,\gamma_{s}\left[(2^{m}-2^{w_{s}})\phantom{\sum_{\begin{subarray}{c}k=0\\\
k\not\equiv 0{\;({\rm{mod}}\;2^{m-w_{s}})}\end{subarray}}^{N-1}}\right.$
$\displaystyle+\left.\sum_{r=1}^{s-1}\sum_{\begin{subarray}{c}k=0\\\
k\not\equiv
0{\;({\rm{mod}}\;2^{m-w_{r}})}\end{subarray}}^{N-1}\sum_{\begin{subarray}{c}\emptyset\neq{\mathfrak{u}}\subseteq[r-1]\\\
r\in{\mathfrak{u}}\end{subarray}}\gamma_{{\mathfrak{u}}}\prod_{j\in{\mathfrak{u}}}\log\left(\frac{1}{\sin^{2}\left(\pi
z_{j}k/2^{m-w_{j}}\right)}\right)\right]$ $\displaystyle=$ $\displaystyle
H_{s-1,N,{\bm{\gamma}},{\bm{w}}}({\bm{z}}_{[s-1]})$ $\displaystyle+(\log
4)\left[\gamma_{s}(2^{m}-2^{w_{s}})+\gamma_{s}H_{s-1,N,{\bm{\gamma}},{\bm{w}}}({\bm{z}}_{[s-1]})\right].$

Hence we have the claimed result. ∎

Based on the result in Theorem 2 we can use an inductive argument to show that
the quantity $H_{s,N,{\bm{\gamma}},{\bm{w}}}$ is sufficiently small if
${\bm{z}}_{[s]}$ has been constructed by Algorithm 1. We obtain the following
estimate.

######  Theorem 3.

Let $m\in{\mathbb{N}}$, $N=2^{m}$, ${\bm{w}}=(w_{j})_{j\geq 1}$ in
${\mathbb{N}}_{0}$ with $0=w_{1}\leq w_{2}\leq\cdots$, and let
${\bm{\gamma}}=(\gamma_{j})_{j\geq 1}$ be positive product weights.
Furthermore, let the generating vector
${\bm{z}}=(Y_{1}z_{1},\ldots,Y_{d}z_{d})\in{\mathbb{Z}}^{d}$ be constructed by
Algorithm 1. Denote by ${\bm{z}}_{[s]}$ the vector $(z_{1},\ldots,z_{s})$ for
$s\in[d]$. Then the following upper bound on
$H_{s,N,{\bm{\gamma}},{\bm{w}}}({\bm{z}}_{[s]})$ holds for $s\in[d^{*}]$,

$H_{s,N,{\bm{\gamma}},{\bm{w}}}({\bm{z}}_{[s]})\leq
N\left[-1+\prod_{j=1}^{s}(1+\gamma_{j}\log 4)\right].$

###### Proof.

Observe that due to Theorem 2,

$\displaystyle H_{s,N,{\bm{\gamma}},{\bm{w}}}({\bm{z}}_{[s]})\leq
H_{s-1,N,{\bm{\gamma}},{\bm{w}}}({\bm{z}}_{[s-1]})+(\log
4)\left[\gamma_{s}(2^{m}-2^{w_{s}})+\gamma_{s}H_{s-1,N,{\bm{\gamma}},{\bm{w}}}({\bm{z}}_{[s-1]})\right]$
(18)

holds for $2\leq s\leq d^{*}$. We can apply this estimate inductively to
obtain the following,

$\displaystyle H_{s,N,{\bm{\gamma}},{\bm{w}}}({\bm{z}}_{[s]})$
$\displaystyle\leq$ $\displaystyle(1+\gamma_{s}\log
4)\left[(1+\gamma_{s-1}\log
4)H_{s-2,N,{\bm{\gamma}},{\bm{w}}}({\bm{z}}_{[s-2]})+\gamma_{s-1}(\log
4)(2^{m}-2^{w_{s-1}})\right]$ $\displaystyle+\gamma_{s}(\log
4)(2^{m}-2^{w_{s}})$ $\displaystyle=$ $\displaystyle
H_{s-2,N,{\bm{\gamma}},{\bm{w}}}({\bm{z}}_{[s-2]})\prod_{j=s-1}^{s}(1+\gamma_{j}\log
4)+\gamma_{s-1}(\log 4)(2^{m}-2^{w_{s-1}})$
$\displaystyle+\gamma_{s}\gamma_{s-1}(\log
4)^{2}(2^{m}-2^{w_{s-1}})+\gamma_{s}(\log 4)(2^{m}-2^{w_{s}})$
$\displaystyle\leq$ $\displaystyle\left(\prod_{j=s-1}^{s}(1+\gamma_{j}\log
4)\right)\left[(1+\gamma_{s-2}\log
4)H_{s-3,N,{\bm{\gamma}},{\bm{w}}}({\bm{z}}_{[s-3]})+\gamma_{s-2}(\log
4)(2^{m}-2^{w_{s-2}})\right]$ $\displaystyle+\gamma_{s-1}(\log
4)(2^{m}-2^{w_{s-1}})+\gamma_{s}\gamma_{s-1}(\log
4)^{2}(2^{m}-2^{w_{s-1}})+\gamma_{s}(\log 4)(2^{m}-2^{w_{s}})$
$\displaystyle=$ $\displaystyle
H_{s-3,N,{\bm{\gamma}},{\bm{w}}}({\bm{z}}_{[s-3]})\prod_{j=s-2}^{s}(1+\gamma_{j}\log
4)+\gamma_{s-2}(\log 4)(2^{m}-2^{w_{s-2}})$
$\displaystyle+\gamma_{s}\gamma_{s-2}(\log
4)^{2}(2^{m}-2^{w_{s-2}})+\gamma_{s-1}\gamma_{s-2}(\log
4)^{2}(2^{m}-2^{w_{s-2}})$
$\displaystyle+\gamma_{s}\gamma_{s-1}\gamma_{s-2}(\log
4)^{3}(2^{m}-2^{w_{s-2}})+\gamma_{s-1}(\log 4)(2^{m}-2^{w_{s-1}})$
$\displaystyle+\gamma_{s}\gamma_{s-1}(\log
4)^{2}(2^{m}-2^{w_{s-1}})+\gamma_{s}(\log 4)(2^{m}-2^{w_{s}}).$

Repeating this argument inductively, we finally arrive at

$\displaystyle H_{s,N,{\bm{\gamma}},{\bm{w}}}({\bm{z}}_{[s]})$
$\displaystyle\leq$ $\displaystyle
H_{1,N,{\bm{\gamma}},{\bm{w}}}(z_{1})\prod_{j=2}^{s}(1+\gamma_{j}\log
4)+\sum_{\emptyset\neq{\mathfrak{u}}\subseteq\\{2:s\\}}\gamma_{{\mathfrak{u}}}(\log
4)^{\left|{\mathfrak{u}}\right|}(2^{m}-2^{\min_{j\in{\mathfrak{u}}}w_{j}})$
(19) $\displaystyle\leq$ $\displaystyle
H_{1,N,{\bm{\gamma}},{\bm{w}}}(z_{1})\prod_{j=2}^{s}(1+\gamma_{j}\log
4)+\sum_{\emptyset\neq{\mathfrak{u}}\subseteq\\{2:s\\}}\gamma_{{\mathfrak{u}}}(\log
4)^{\left|{\mathfrak{u}}\right|}2^{m}.$

However, recall that we have, by definition,

$\displaystyle H_{1,N,{\bm{\gamma}},{\bm{w}}}(z_{1})$ $\displaystyle=$
$\displaystyle
H_{1,N,{\bm{\gamma}},{\bm{w}}}(1)=\sum_{k=1}^{N-1}\gamma_{1}u_{1}(k)=\gamma_{1}\sum_{k=1}^{N-1}\log\left(\frac{1}{\sin^{2}(\pi
k/2^{m})}\right)$ $\displaystyle=$
$\displaystyle-2\gamma_{1}\sum_{k=1}^{N-1}\log\left(\sin\left(\frac{\pi
k}{N}\right)\right)=\gamma_{1}(N-m-1)\log 4$ $\displaystyle\leq$
$\displaystyle\gamma_{1}N\log 4-\gamma_{1}\log 4\leq\gamma_{1}N\log 4,$

where we used the identity

$\prod_{k=1}^{N-1}\left(2\sin\left(\frac{\pi k}{N}\right)\right)=N.$

Consequently, combining this bound with (19), expanding the expression, and
using that $\gamma_{\mathfrak{u}}=\prod_{j\in{\mathfrak{u}}}\gamma_{j}$,
finally gives

$\displaystyle H_{s,N,{\bm{\gamma}},{\bm{w}}}({\bm{z}}_{[s]})$
$\displaystyle\leq$ $\displaystyle N\gamma_{1}(\log
4)\left(\prod_{j=2}^{s}(1+\gamma_{j}\log
4)\right)+N\sum_{\emptyset\neq{\mathfrak{u}}\subseteq\\{2:s\\}}\gamma_{{\mathfrak{u}}}(\log
4)^{\left|{\mathfrak{u}}\right|}$ $\displaystyle=$ $\displaystyle
N\left(\gamma_{1}(\log 4)\prod_{j=2}^{s}(1+\gamma_{j}\log
4)+(-1)+\prod_{j=2}^{s}(1+\gamma_{j}\log 4)\right)$ $\displaystyle=$
$\displaystyle N\prod_{j=1}^{s}(1+\gamma_{j}\log
4)-N=N\left[-1+\prod_{j=1}^{s}(1+\gamma_{j}\log 4)\right],$

which is the claim.

∎

We are now able to show the main result regarding the reduced component-by-
component digit-by-digit construction.

######  Theorem 4.

Let $N=2^{m}$, with $m\in{\mathbb{N}}$, let ${\bm{w}}=(w_{j})_{j\geq 1}$ be a
sequence in ${\mathbb{N}}_{0}$ with $0=w_{1}\leq w_{2}\leq\cdots$, and let
${\bm{\gamma}}=(\gamma_{j})_{j\geq 1}$ be positive product weights.
Furthermore, denote by ${\bm{z}}=(Y_{1}z_{1},\ldots,Y_{d}z_{d})$ the
corresponding generating vector constructed by Algorithm 1. Then the following
estimate holds,

$T_{\bm{\gamma}}(N,{\bm{z}},{\bm{w}})\leq\sum_{\emptyset\neq{\mathfrak{u}}\subseteq[d^{*}]}\gamma_{{\mathfrak{u}}}\frac{2(6\log
N)^{\left|{\mathfrak{u}}\right|+1}}{2^{m-\max_{j\in{\mathfrak{u}}}w_{j}}}.$
(20)

###### Proof.

Recall from Theorem 1 that

$\displaystyle T_{\bm{\gamma}}(N,{\bm{z}},{\bm{w}})$ $\displaystyle\leq$
$\displaystyle\sum_{\emptyset\neq{\mathfrak{u}}\subseteq[d^{*}]}\frac{\gamma_{{\mathfrak{u}}}}{N}2^{w_{j_{\left|{\mathfrak{u}}\right|}}+1}(6\log
N)^{\left|{\mathfrak{u}}\right|}(1+\log N)$
$\displaystyle+\frac{1}{N}H_{d^{*},N,{\bm{\gamma}},{\bm{w}}}-\sum_{\emptyset\neq{\mathfrak{u}}\subseteq[d^{*}]}\gamma_{{\mathfrak{u}}}(\log
4)^{\left|{\mathfrak{u}}\right|}.$

Then, using the structure of product weights, along with the estimate for
$H_{d^{*},N,{\bm{\gamma}},{\bm{w}}}$ in Theorem 3, we obtain

$\displaystyle T_{\bm{\gamma}}(N,{\bm{z}},{\bm{w}})$ $\displaystyle\leq$
$\displaystyle\frac{2(1+\log
N)}{N}\sum_{\emptyset\neq{\mathfrak{u}}\subseteq[d^{*}]}\gamma_{{\mathfrak{u}}}2^{w_{j_{\left|{\mathfrak{u}}\right|}}}(6\log
N)^{\left|{\mathfrak{u}}\right|}$
$\displaystyle+\frac{1}{N}N\left(-1+\prod_{j=1}^{d^{*}}(1+\gamma_{j}\log
4)\right)-\prod_{j=1}^{d^{*}}(1+\gamma_{j}\log 4)+1$ $\displaystyle=$
$\displaystyle\frac{2(1+\log
N)}{N}\sum_{\emptyset\neq{\mathfrak{u}}\subseteq[d^{*}]}\gamma_{{\mathfrak{u}}}2^{w_{j_{\left|{\mathfrak{u}}\right|}}}(6\log
N)^{\left|{\mathfrak{u}}\right|}$ $\displaystyle\leq$
$\displaystyle\sum_{\emptyset\neq{\mathfrak{u}}\subseteq[d^{*}]}\gamma_{{\mathfrak{u}}}\frac{2(6\log
N)^{\left|{\mathfrak{u}}\right|+1}}{2^{m-\max_{j\in{\mathfrak{u}}}w_{j}}},$

where we used that for a non-empty set ${\mathfrak{u}}\subseteq[d^{*}]$ we
have $w_{j_{\left|{\mathfrak{u}}\right|}}=\max_{j\in{\mathfrak{u}}}w_{j}$.
This is the claimed result. ∎

We now have the following corollary.

######  Corollary 1.

Let $N=2^{m}$, with $m\in{\mathbb{N}}$, let ${\bm{w}}=(w_{j})_{j\geq 1}$ be a
sequence in ${\mathbb{N}}_{0}$ with $0=w_{1}\leq w_{2}\leq\cdots$, and let
${\bm{\gamma}}=(\gamma_{j})_{j\geq 1}$ be positive product weights satisfying

$\displaystyle\sum_{j\geq 1}\gamma_{j}2^{w_{j}}$ $\displaystyle<\infty.$

Furthermore, denote by ${\bm{z}}=(Y_{1}z_{1},\ldots,Y_{d}z_{d})$ the
generating vector constructed by Algorithm 1 run for the weights
${\bm{\gamma}}=(\gamma_{j})_{j\geq 1}$. Then, for any $\delta>0$ and each
$\alpha>1$, the generating vector ${\bm{z}}$ satisfies

$e_{N,d,\alpha,{\bm{\gamma}}^{\alpha}}({\bm{z}})\leq\frac{1}{N^{\alpha}}\left(C_{1}({\bm{\gamma}}^{\alpha})+C_{2}({\bm{\gamma}},\delta)N^{\alpha\delta}\right)$

with weight sequence ${\bm{\gamma}}^{\alpha}=(\gamma_{j}^{\alpha})_{j\geq 1}$
and positive constants $C_{1}({\bm{\gamma}}^{\alpha})$ and
$C_{2}({\bm{\gamma}},\delta)$, which are independent of $d$ and $N$.
Additionally, if Algorithm 1 is run for weights
${\bm{\gamma}}^{1/\alpha}=(\gamma_{j}^{1/\alpha})_{j\geq 1}$ with $\alpha>1$,
satisfying

$\displaystyle\sum_{j\geq 1}\gamma_{j}^{1/\alpha}2^{w_{j}}$
$\displaystyle<\infty,$

then, for any $\delta>0$, the resulting generating vector
$\widetilde{{\bm{z}}}=(Y_{1}\widetilde{z}_{1},\ldots,Y_{d}\widetilde{z}_{d})$
satisfies the error bound

$e_{N,d,\alpha,{\bm{\gamma}}}(\widetilde{{\bm{z}}})\leq\frac{1}{N^{\alpha}}\left(F_{1}({\bm{\gamma}})+F_{2}({\bm{\gamma}}^{1/\alpha},\delta)N^{\alpha\delta}\right),$

with positive constants $F_{1}({\bm{\gamma}})$ and
$F_{2}({\bm{\gamma}}^{1/\alpha},\delta)$, which are independent of $d$ and
$N$.

###### Proof.

We know from Proposition 1 that the worst-case error
$e_{N,d,\alpha,{\bm{\gamma}}^{\alpha}}({\bm{z}})$ satisfies

$\displaystyle
e_{N,d,\alpha,{\bm{\gamma}}^{\alpha}}({\bm{z}})\leq\sum_{\emptyset\neq{\mathfrak{u}}\subseteq[d]}\gamma_{\mathfrak{u}}^{\alpha}\,\frac{(4\zeta(\alpha))^{\left|{\mathfrak{u}}\right|}}{2^{\alpha\max(0,m-\max_{j\in{\mathfrak{u}}}w_{j})}}+T_{\alpha,{\bm{\gamma}}^{\alpha}}(N,{\bm{z}},{\bm{w}}).$

al Taking into account that we have product weights
$\gamma_{\mathfrak{u}}=\prod_{j\in{\mathfrak{u}}}\gamma_{j}$, this yields

$\displaystyle e_{N,d,\alpha,{\bm{\gamma}}^{\alpha}}({\bm{z}})$
$\displaystyle\leq\frac{1}{N^{\alpha}}\sum_{\emptyset\neq{\mathfrak{u}}\subseteq[d]}\left(\prod_{j\in{\mathfrak{u}}}(\gamma_{j}^{\alpha}\,4\zeta(\alpha))\right)2^{\alpha\max_{j\in{\mathfrak{u}}}w_{j}}+T_{\alpha,{\bm{\gamma}}^{\alpha}}(N,{\bm{z}},{\bm{w}})$
$\displaystyle\leq\frac{1}{N^{\alpha}}\prod_{j=1}^{d}\left(1+\gamma_{j}^{\alpha}\,4\zeta(\alpha)2^{\alpha
w_{j}}\right)+T_{\alpha,{\bm{\gamma}}^{\alpha}}(N,{\bm{z}},{\bm{w}}),$

where we used that for $\emptyset\neq{\mathfrak{u}}\subseteq[d]$ we have
$\max_{j\in{\mathfrak{u}}}w_{j}\leq\sum_{j\in{\mathfrak{u}}}w_{j}$. Since
$\alpha>1$, we can use an inequality sometimes called Jensen’s inequality,
which states that
$\sum_{i=1}^{n}a_{i}\leq\left(\sum_{i=1}^{n}a_{i}^{p}\right)^{1/p}$ for non-
negative $a_{1},\dots,a_{n}$ and $0\leq p\leq 1$, and thus we have

$T_{\alpha,{\bm{\gamma}}^{\alpha}}(N,{\bm{z}},{\bm{w}})=\sum_{{\bm{0}}\neq{\bm{\ell}}\in
M_{N,d,{\bm{w}}}}\frac{\delta_{N}({\bm{\ell}}\cdot{\bm{z}})}{r_{\alpha,{\bm{\gamma}}^{\alpha}}({\bm{\ell}})}\leq\left(\sum_{{\bm{0}}\neq{\bm{\ell}}\in
M_{N,d,{\bm{w}}}}\frac{\delta_{N}({\bm{\ell}}\cdot{\bm{z}})}{r_{1,{\bm{\gamma}}}({\bm{\ell}})}\right)^{\alpha}=(T_{\bm{\gamma}}(N,{\bm{z}},{\bm{w}}))^{\alpha},$

and by Theorem 4 we know that the ${\bm{z}}$ generated by Algorithm 1 is such
that

$T_{\bm{\gamma}}(N,{\bm{z}},{\bm{w}})\leq\sum_{\emptyset\neq{\mathfrak{u}}\subseteq[d^{*}]}\gamma_{{\mathfrak{u}}}\frac{2(6\log
N)^{\left|{\mathfrak{u}}\right|+1}}{2^{m-\max_{j\in{\mathfrak{u}}}w_{j}}}.$

From this, we deduce, using
$\gamma_{\mathfrak{u}}=\prod_{j\in{\mathfrak{u}}}\gamma_{j}$, that we have

$\displaystyle 2^{m}T_{\bm{\gamma}}(N,{\bm{z}},{\bm{w}})$ $\displaystyle\leq$
$\displaystyle 2(6\log
N)\sum_{\emptyset\neq{\mathfrak{u}}\subseteq[d^{*}]}\gamma_{{\mathfrak{u}}}(6\log
N)^{\left|{\mathfrak{u}}\right|}2^{\max_{j\in{\mathfrak{u}}}w_{j}}$ (21)
$\displaystyle\leq$ $\displaystyle 2(6\log
N)\sum_{\emptyset\neq{\mathfrak{u}}\subseteq[d^{*}]}\left(\prod_{j\in{\mathfrak{u}}}(\gamma_{j}\,6\log
N)\right)\,2^{\sum_{j\in{\mathfrak{u}}}w_{j}}$ $\displaystyle\leq$
$\displaystyle 2(6\log N)\prod_{j=1}^{d^{*}}\left(1+\gamma_{j}\,(6\log
N)\,2^{w_{j}}\right)$ $\displaystyle\leq$ $\displaystyle(1+2(6\log
N))\prod_{j=1}^{d^{*}}\left(1+\gamma_{j}\,(6\log N)\,2^{w_{j}}\right)$
$\displaystyle\leq$
$\displaystyle\widetilde{C}(\delta/2)2^{m\delta/2}\prod_{j=1}^{\infty}\left(1+\gamma_{j}\,(6\log
N)\,2^{w_{j}}\right),$

for arbitrary $\delta>0$, where $\widetilde{C}(\delta/2)$ is a constant
depending only on $\delta$, and where we again used for
$\emptyset\neq{\mathfrak{u}}\subseteq[d^{*}]$ that we have
$\max_{j\in{\mathfrak{u}}}w_{j}\leq\sum_{j\in{\mathfrak{u}}}w_{j}$. Due to the
given condition imposed on the weights, i.e., $\sum_{j\geq
1}\gamma_{j}2^{w_{j}}<\infty$, we can use the result in [11, Lemma 3] to see
that the product in (21) can be bounded by
$\hat{C}({\bm{\gamma}},\delta)2^{m\delta}$, where
$\hat{C}({\bm{\gamma}},\delta)$ may depend on the weights ${\bm{\gamma}}$ and
$\delta$, but is independent of the dimension. This yields

$(T_{\bm{\gamma}}(N,{\bm{z}},{\bm{w}}))^{\alpha}\leq\frac{1}{N^{\alpha}}\left(\widetilde{C}(\delta/2)\right)^{\alpha}\left(\hat{C}({\bm{\gamma}},\delta)\right)^{\alpha}N^{\alpha\delta}.$

Setting then
$C_{1}({\bm{\gamma}}^{\alpha})=\prod_{j=1}^{\infty}(1+\gamma_{j}^{\alpha}4\zeta(\alpha)2^{\alpha
w_{j}})$, which is finite due to our assumption on the weights, and
$C_{2}({\bm{\gamma}},\delta)=\left(\widetilde{C}(\delta/2)\right)^{\alpha}\left(\hat{C}({\bm{\gamma}},\delta)\right)^{\alpha}$
we get the claimed estimate.

Similarly, for weights ${\bm{\gamma}}^{1/\alpha}$ and due to the condition
imposed on the weights, i.e., $\sum_{j\geq
1}\gamma_{j}^{1/\alpha}2^{w_{j}}<\infty$, and by using the result in [11,
Lemma 3] we have

$(T_{{\bm{\gamma}}^{1/\alpha}}(N,\widetilde{{\bm{z}}},{\bm{w}}))^{\alpha}\leq\frac{1}{N^{\alpha}}\left(\widetilde{C}(\delta/2)\right)^{\alpha}\left(\hat{C}({\bm{\gamma}}^{1/\alpha},\delta)\right)^{\alpha}N^{\alpha\delta}.$

Then setting
$F_{1}({\bm{\gamma}})=\prod_{j=1}^{\infty}(1+\gamma_{j}4\zeta(\alpha)2^{w_{j}})$
and
$F_{2}({\bm{\gamma}}^{1/\alpha},\delta)=\left(\widetilde{C}(\delta/2)\right)^{\alpha}\left(\hat{C}({\bm{\gamma}}^{1/\alpha},\delta)\right)^{\alpha}$
we get the claimed estimate. ∎

The result in Corollary 1 involves two cases regarding the worst-case error
behavior of the generating vectors constructed by Algorithm 1. To be more
precise, we can run the algorithm with weights ${\bm{\gamma}}$, and hence it
does not depend on the parameter $\alpha$, then the algorithm produces a
generating vector for which bounds on the worst-case errors in the spaces
$E_{d,{\bm{\gamma}}^{\alpha}}^{\alpha}$ hold simultaneously for all
$\alpha>1$. On the other hand, when we run Algorithm 1 with weights
$\gamma^{1/\alpha}$, we have a dependence on the parameter $\alpha$, and the
algorithm yields error bounds for the worst-case error in the spaces
$E_{d,{\bm{\gamma}}}^{\alpha}$.

##  4 Fast implementation of the construction scheme

In this section we discuss the efficient implementation of the introduced
reduced CBC-DBD algorithm and analyze its complexity.

###  4.1 Implementation and cost analysis of the reduced CBC-DBD algorithm

We recall the definition of the quality function in Definition 2, and we see
that for product weights $h_{d,v,m,{\bm{\gamma}},{\bm{w}}}$ can be rewritten
as follows. Let $x\in{\mathbb{N}}$ be an odd integer, let
$m,d\in{\mathbb{N}}$, and let ${\bm{\gamma}}=(\gamma_{j})_{j\geq 1}$ be
positive product weights. For $1\leq s\leq d$, $1\leq v\leq m-w_{s}$, and odd
integers $z_{1},\ldots,z_{s-1}$ the quality function
$h_{s,v,m,{\bm{\gamma}},{\bm{w}}}$ reads

$\displaystyle\\!\\!\\!\\!\\!\\!h_{s,v,m,{\bm{\gamma}},{\bm{w}}}(x):$
$\displaystyle=\sum_{t=v}^{m-w_{s}}\frac{1}{2^{t-v}}\sum_{\ell=0}^{2^{w_{s}}-1}\
\ \sum_{\begin{subarray}{c}k=\ell 2^{t}+1\\\ k\equiv
1{\;({\rm{mod}}\;2)}\end{subarray}}^{(\ell+1)2^{t}-1}\left(1+\gamma_{s}\log\left(\frac{1}{\sin^{2}(\pi
kx/2^{v})}\right)\right)$
$\displaystyle\times\prod_{j=1}^{s-1}\left[1+\gamma_{j}\log\left(\frac{1}{\sin^{2}\left(\pi
z_{j}\frac{k}{2^{t}}\,\frac{2^{m-w_{s}}}{2^{m-w_{j}}}\right)}\right)\right],$

where the components $z_{1},\dots,z_{s-1}$ have been determined in the
previous steps of the algorithm. We are interested in the cost of a single
evaluation of the function $h_{s,v,m,{\bm{\gamma}},{\bm{w}}}$, which is
crucial for the total cost of Algorithm 1, hence we will discuss an efficient
evaluation procedure in the following paragraph.

For integers $t\in\\{2,\ldots,m-w_{s}\\}$ (note that we always have $v\geq 2$
in Algorithm 1, so we do not need to consider the case $t=1$) and odd
$k\in\\{\ell 2^{t}+1,\ldots,(\ell+1)2^{t}-1\\}$ for
$\ell\in\\{0,\ldots,2^{w_{s}}-1\\}$, we define $r(s,t,k)$ as

$r(s,t,k):=\prod_{j=1}^{s}\left(1+\gamma_{j}\log\left(\frac{1}{\sin^{2}\left(\pi
z_{j}\frac{k}{2^{t}}\frac{2^{m-w_{s}}}{2^{m-w_{j}}}\right)}\right)\right),$

and observe that for the evaluation of $h_{s,v,m,{\bm{\gamma}},{\bm{w}}}(x)$
we can compute and store the terms $r(s-1,t,k)$ for suitable values of $t$
since they are independent of $v$ and $x$. This way we can rewrite
$h_{s,v,m,{\bm{\gamma}},{\bm{w}}}(x)$ as

$\sum_{t=v}^{m-w_{s}}\frac{1}{2^{t-v}}\sum_{\ell=0}^{2^{w_{s}}-1}\ \
\sum_{\begin{subarray}{c}k=\ell 2^{t}+1\\\ k\equiv
1{\;({\rm{mod}}\;2)}\end{subarray}}^{(\ell+1)2^{t}-1}r(s-1,t-w_{s-1}+w_{s},k)\left(1+\gamma_{s}\log\left(\frac{1}{\sin^{2}\left(\pi
kx/2^{v}\right)}\right)\right).$ (22)

Note that if $v\leq t\leq m-w_{s}$, then $0\leq v-w_{s-1}+w_{s}\leq
t-w_{s-1}+w_{s}\leq m-w_{s-1}$. In Algorithm 1, after having determined
$z_{s}$, the values of $r(s,v,k)$ for odd integers ${k\in\\{\ell
2^{v}+1,\ldots,(\ell+1)2^{v}-1\\}}$ with $\ell\in\\{0,\ldots,2^{w_{s}}-1\\}$
are computed via the recurrence relation

$r(s,t,k)=r(s-1,t-w_{s-1}+w_{s},k)\left(1+\gamma_{s}\log\left(\frac{1}{\sin^{2}(\pi
kz_{s}/2^{t})}\right)\right).$

Now, for an algorithmic implementation, we introduce the vector
${\bm{u}}=(u(1),\ldots,u(2^{m}-1))\in{\mathbb{R}}^{2^{m}-1}$ , whose
components, for the current $s\in\\{1,\ldots,d^{*}\\}$, are given by

$u(k\,2^{m-w_{s}-t})=\prod_{j=1}^{s}\left(1+\gamma_{j}\log\left(\frac{1}{\sin^{2}\left(\pi
z_{j}\frac{k}{2^{t}}\frac{2^{m-w_{s}}}{2^{m-w_{j}}}\right)}\right)\right)$

for each $t\in\\{1,\ldots,m-w_{s}\\}$ and corresponding odd index $k\in\\{\ell
2^{t}+1,\ldots,(\ell+1)2^{t}-1\\}$ for $\ell\in\\{0,\ldots,2^{w_{s}}-1\\}$.
Note that $k\,2^{m-w_{s}-t}$ runs through the whole range
$\\{1,\ldots,2^{m}-1\\}$ when $t$, $k$, and $\ell$ are chosen as stated.
Furthermore, note that the quantity $u(k\,2^{m-w_{s}-t})$ corresponds to
$r(s,t,k)$ for $t\geq 2$, and that for the evaluation of
$h_{s,v,m,{\bm{\gamma}},{\bm{w}}}$ we do not require the values of $r(s,t,k)$
for $t=2,\ldots,v-1$. Combining these findings leads to the following fast
implementation of Algorithm 1.

Algorithm 2 Fast reduced component-by-component digit-by-digit algorithm

Input: Integers $m,d\in{\mathbb{N}}$, positive product weights
${\bm{\gamma}}=(\gamma_{j})_{j\geq 1}$, and integer reduction indices
$(w_{j})_{j\geq 1}$ with $0=w_{1}\leq w_{2}\leq\cdots$.

for $t=2$ to $m=m-w_{1}$ do

for $k=1$ to $2^{t}-1$ in steps of $2$ do

$u(k2^{m-w_{1}-t})=\left(1+\gamma_{1}\log\left(\frac{1}{\sin^{2}(\pi
k/2^{t})}\right)\right)$

end for

end for

Set $s=1$ and let $d^{*}$ be the largest integer such that $w_{d^{*}}<m$. Set
$z_{1,1}=\cdots=z_{d,1}=1$.

while $s\leq\min\\{d,d^{*}\\}$ do

for $v=2$ to $m-w_{s}$ do

$z^{\ast}=\underset{z\in\\{0,1\\}}{\operatorname*{argmin}}\;h_{s,v,m,{\bm{\gamma}},{\bm{w}}}(z_{s,v-1}+z\,2^{v-1})$
with $h_{s,v,m,{\bm{\gamma}},{\bm{w}}}$ evaluated using (22)

$z_{s,v}=z_{s,v-1}+z^{\ast}2^{v-1}$

for $\ell=0$ to $2^{w_{s}}-1$ do

for $k=\ell 2^{v}+1$ to $(\ell+1)2^{v}-1$ in steps of $2$ do

$u(k2^{m-w_{s}-v})=u(k2^{m-w_{s-1}-v})\left(1+\gamma_{s}\log\left(\frac{1}{\sin^{2}(\pi
kz_{s,v}/2^{v})}\right)\right)$

end for

end for

end for

Set $z_{s}:=z_{s,m-w_{s}}$.

end while

if $d>d^{*}$ then

set $z_{d^{*}+1}=\cdots=z_{d}=1$

end if

Set ${\bm{z}}=(Y_{1}z_{1},\ldots,Y_{d}z_{d})$.

Return: Generating vector ${\bm{z}}=(Y_{1}z_{1},\ldots,Y_{d}z_{d})$ for
$N=2^{m}$.

The computational complexity of Algorithm 2 is then summarized in the
following theorem.

######  Theorem 5.

Let $N=2^{m}$ with $m\in{\mathbb{N}}$, let ${\bm{\gamma}}=(\gamma_{j})_{j\geq
1}$ be a given sequence of positive weights, and let integer reduction indices
$w_{j}$ with $0=w_{1}\leq w_{2}\leq\cdots$ be given. Moreover, denote by
$d^{*}$ the largest integer such that $w_{d^{*}}<m$. Then Algorithm 2
constructs a generating vector ${\bm{z}}=(z_{1},\ldots,z_{d})$ using

${\mathcal{O}}\left(\min\\{d,d^{*}\\}\,2^{m}+\sum_{s=1}^{\min\\{d,d^{*}\\}}(m-w_{s})2^{m}\right)$

operations and requiring ${\mathcal{O}}(2^{m})$ memory.

###### Proof.

Due to the relation in (22), the cost of evaluating
$h_{s,v,m,{\bm{\gamma}},{\bm{w}}}(x)$ for one fixed $v$ can be reduced to
${\mathcal{O}}(\sum_{t=v}^{m-w_{s}}2^{w_{s}+t-1})$ operations. Moreover,
updating the values of $u$ needs ${\mathcal{O}}(2^{w_{s}+v-1})$ operations, so
the computational cost for one fixed $v$ in the inner loop over
$v=2,\dots,m-w_{s}$ of Algorithm 2 is of order
${\mathcal{O}}(\sum_{t=v}^{m-w_{s}}2^{w_{s}+t-1})$. Thus, the number of
calculations in the inner loop over $v=2,\dots,m-w_{s}$ of Algorithm 2 is of
order

$\displaystyle{\mathcal{O}}\left(\sum_{v=2}^{m-w_{s}}2\sum_{t=v}^{m-w_{s}}2^{w_{s}+t-1}\right)$
$\displaystyle={\mathcal{O}}\left(\sum_{v=2}^{m-w_{s}}\sum_{t=v}^{m-w_{s}}2^{w_{s}+t}\right)={\mathcal{O}}\left((m-w_{s})\,2^{m+1}-2(2^{m+1}-2^{w_{s}+1})\right)$
$\displaystyle={\mathcal{O}}\left((m-w_{s})\,2^{m}\right).$

Hence, the outer loop over $s=1,\ldots,\min\\{d,d^{*}\\}$, which is the main
cost of Algorithm 2, can be executed in

${\mathcal{O}}\left(\sum_{s=1}^{\min\\{d,d^{*}\\}}(m-w_{s})2^{m}\right)$

operations. Furthermore, we observe that initialization and updating of the
vector ${\bm{u}}\in{\mathbb{R}}^{2^{m}-1}$ can both be executed in
${\mathcal{O}}(\min\\{d,d^{*}\\}2^{m})$ operations. Additionally, storing the
vector ${\bm{u}}$ requires ${\mathcal{O}}(2^{m})$ of memory. ∎

The run-time of Algorithm 2 can also be reduced further by precomputing and
storing the $2^{m}$ values

$\log\left(\frac{1}{\sin^{2}(\pi k/2^{m})}\right)\quad\text{for}\quad
k=1,\ldots,2^{m}-1.$

The derivation leading to the fast implementation in Algorithm 2 is using
arguments that were also used in [8], where a non-reduced component-by-
component digit-by-digit construction for lattice rules in weighted Korobov
spaces has been studied.

##  5 Numerical results

In this section, we illustrate the error convergence behavior of the lattice
rules constructed by the reduced fast CBC-DBD algorithm and display the
computational complexity of the construction using numerical experiments. As
in the previous section, we consider lattice rules in the weighted Korobov
space $E_{s,{\bm{\gamma}}}^{\alpha}$ of smoothness $\alpha>1$, and we assume
product weights $\gamma_{\mathfrak{u}}=\prod_{j\in{\mathfrak{u}}}\gamma_{j}$
given in terms of positive reals $(\gamma_{j})_{j\geq 1}$. For
${\bm{z}}=(z_{1},\dots,z_{d})$, the worst-case error is then given by

$e_{N,d,\alpha,{\bm{\gamma}}}({\bm{z}})=-1+\frac{1}{2^{m}}\sum_{k=0}^{2^{m}-1}\prod_{j=1}^{d}\left(1+\gamma_{j}\,\sum_{\ell\in{\mathbb{Z}}_{*}}\frac{e^{2\pi\mathrm{i}k\ell
z_{j}/2^{m}}}{\left|\ell\right|^{\alpha}}\right).$

To demonstrate the performance of the algorithm, we compare the worst-case
errors of the constructed lattice rules as well as the algorithm’s computation
times with the corresponding quantities obtained by the non-reduced component-
by-component digit-by-digit algorithm, see [8]. Both constructions deliver
lattice rules for the space $E_{s,{\bm{\gamma}}}^{\alpha}$ consisting of
$2^{m}$ cubature points. The different algorithms have been implemented in
double-precision and arbitrary-precision floating-point arithmetic, with the
latter provided by the multi-precision Python library mpmath.

###  5.1 Error convergence behavior

Let $m,d\in{\mathbb{N}}$, $\alpha>1$, a sequence of positive weights
${\bm{\gamma}}=(\gamma_{j})_{j\geq 1}$, and reduction indices $(w_{j})_{j\geq
1}$ with $0=w_{1}\leq w_{2}\leq\cdots$ be given. In particular, we consider
the convergence rate of the worst-case error
$e_{2^{m},d,\alpha,{\bm{\gamma}}^{\alpha}}({\bm{z}})$ for different weight
sequences ${\bm{\gamma}}=(\gamma_{j})_{j\geq 1}$ of the form
$\gamma_{j}=c^{j}$ with $c\in(0,1)$ or $\gamma_{j}=1/j^{q}$ with $q>1$ and
reduction indices of the form $w_{j}=\lfloor p\log_{2}j\rfloor$ with $p>0$. We
display the computational results for dimension $d=100$ for different
sequences of product weights, different values of $m$, and reduction indices
$w_{j}$. We stress that the almost optimal error rates of
${\mathcal{O}}(N^{-\alpha+\delta})$, as guaranteed by Corollary 1, may not
always be visible for the weights, reduction indices, and ranges of $N$
considered in our numerical experiments. The graphs shown are therefore to be
understood as illustrations of the pre-asymptotic behavior of the worst-case
error. Figures 1 and 2 show numerical results using different choices of
weights $(\gamma_{j})_{j\geq 1}$ for reduction indices of the form
$w_{j}=\lfloor 2\log_{2}j\rfloor$ and
$w_{j}=\lfloor\frac{7}{2}\log_{2}j\rfloor$, respectively. The generating
vectors ${\bm{z}}$ are obtained by the reduced fast CBC-DBD algorithm and the
non-reduced fast CBC-DBD algorithm, respectively.

Error convergence in the space $E_{d,{\bm{\gamma}}}^{\alpha}$ with
$d=100,\alpha=2$, $w_{j}=\lfloor 2\log_{2}j\rfloor$.

$10^{1}$$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{-10}$$10^{-9}$$10^{-8}$$10^{-7}$$10^{-6}$$10^{-5}$$10^{-4}$$10^{-3}$$10^{-2}$Number
of points $N=2^{m}$Worst-case error
$e_{N,d,\alpha,\mathbf{\gamma^{\alpha}}}(\mathbf{z})$${\mathcal{O}}(N^{-1.90})$
(a) Weight sequence ${\bm{\gamma}}=(\gamma_{j})_{j=1}^{d}$ with
$\gamma_{j}=1/j^{3}$.

$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{-10}$$10^{-9}$$10^{-8}$$10^{-7}$$10^{-6}$$10^{-5}$$10^{-4}$$10^{-3}$$10^{-2}$Number
of points $N=2^{m}$Worst-case error
$e_{N,d,\alpha,\mathbf{\gamma^{\alpha}}}(\mathbf{z})$${\mathcal{O}}(N^{-2.00})$
(b) Weight sequence ${\bm{\gamma}}=(\gamma_{j})_{j=1}^{d}$ with
$\gamma_{j}=1/j^{8}$.

$10^{1}$$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{-11}$$10^{-10}$$10^{-9}$$10^{-8}$$10^{-7}$$10^{-6}$$10^{-5}$$10^{-4}$$10^{-3}$Number
of points $N=2^{m}$Worst-case error
$e_{N,d,\alpha,\mathbf{\gamma^{\alpha}}}(\mathbf{z})$${\mathcal{O}}(N^{-1.98})$
(c) Weight sequence ${\bm{\gamma}}=(\gamma_{j})_{j=1}^{d}$ with
$\gamma_{j}=(0.3)^{j}$.

$10^{1}$$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{7}$Number
of points $N=2^{m}$Worst-case error
$e_{N,d,\alpha,\mathbf{\gamma^{\alpha}}}(\mathbf{z})$${\mathcal{O}}(N^{-0.98})$
(d) Weight sequence ${\bm{\gamma}}=(\gamma_{j})_{j=1}^{d}$ with
$\gamma_{j}=(0.95)^{j}$.

CBC-DBDreduced CBC-DBD

Figure 1: Convergence of the worst-case errors
$e_{N,d,\alpha,{\bm{\gamma}}^{\alpha}}({\bm{z}})$ in the weighted space
$E_{d,{\bm{\gamma}}}^{\alpha}$ for smoothness parameter $\alpha=2$ with
dimension $d=100$ and reduction indices $w_{j}=\lfloor 2\log_{2}j\rfloor$. The
generating vector ${\bm{z}}$ is constructed via the reduced CBC-DBD
construction and the non-reduced CBC-DBD construction for $N=2^{m}$,
respectively.

Error convergence in the space $E_{d,{\bm{\gamma}}}^{\alpha}$ with
$d=100,\alpha=2$, $w_{j}=\lfloor\frac{7}{2}\log_{2}j\rfloor$.

$10^{1}$$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{-11}$$10^{-10}$$10^{-9}$$10^{-8}$$10^{-7}$$10^{-6}$$10^{-5}$$10^{-4}$$10^{-3}$$10^{-2}$$10^{-1}$Number
of points $N=2^{m}$Worst-case error
$e_{N,d,\alpha,\mathbf{\gamma^{\alpha}}}({\bm{z}})$${\mathcal{O}}(N^{-1.31})$
(a) Weight sequence ${\bm{\gamma}}=(\gamma_{j})_{j\geq 1}$ with
$\gamma_{j}=1/j^{3}$.

$10^{1}$$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{-10}$$10^{-9}$$10^{-8}$$10^{-7}$$10^{-6}$$10^{-5}$$10^{-4}$$10^{-3}$$10^{-2}$Number
of points $N=2^{m}$Worst-case error
$e_{N,d,\alpha,\mathbf{\gamma^{\alpha}}}({\bm{z}})$${\mathcal{O}}(N^{-2.00})$
(b) Weight sequence ${\bm{\gamma}}=(\gamma_{j})_{j\geq 1}$ with
$\gamma_{j}=1/j^{8}$.

$10^{1}$$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{-12}$$10^{-11}$$10^{-10}$$10^{-9}$$10^{-8}$$10^{-7}$$10^{-6}$$10^{-5}$$10^{-4}$$10^{-3}$$10^{-2}$Number
of points $N=2^{m}$Worst-case error
$e_{N,s,\alpha,\mathbf{\gamma^{\alpha}}}({\bm{z}})$${\mathcal{O}}(N^{-1.79})$
(c) Weight sequence ${\bm{\gamma}}=(\gamma_{j})_{j\geq 1}$ with
$\gamma_{j}=(0.3)^{j}$.

$10^{1}$$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{7}$$10^{8}$Number
of points $N=2^{m}$Worst-case error
$e_{N,d,\alpha,\mathbf{\gamma^{\alpha}}}({\bm{z}})$${\mathcal{O}}(N^{-0.84})$
(d) Weight sequence ${\bm{\gamma}}=(\gamma_{j})_{j\geq 1}$ with
$\gamma_{j}=(0.95)^{j}$.

CBC-DBDreduced CBC-DBD

Figure 2: Convergence of the worst-case errors
$e_{N,d,\alpha,{\bm{\gamma}}^{\alpha}}({\bm{z}})$ in the weighted space
$E_{d,{\bm{\gamma}}}^{\alpha}$ for smoothness parameter $\alpha=2$ with
dimension $d=100$ and reduction indices
$w_{j}=\lfloor\frac{7}{2}\log_{2}j\rfloor$. The generating vector ${\bm{z}}$
is constructed via the reduced CBC-DBD construction and the non-reduced CBC-
DBD construction for $N=2^{m}$, respectively.

The results in Figures 1 and 2 show that the reduced fast CBC-DBD algorithm
constructs generating vectors of good lattice rules which have worst-case
errors that are essentially comparable to those of lattice rules obtained by
the non-reduced fast CBC-DBD algorithm. We observe asymptotic error rates for
both algorithms considered. Only in Part (a) of Figures 1 and 2, respectively,
the errors of the lattice rules obtained by the reduced construction seem to
be significantly higher than those of the non-reduced case. This error
behavior can be explained as follows. As illustrated in Figures 1 and 2,
throughout we use $b=2$ and $\alpha=2$. Corollary 1 assures independence of
the dimension $d$ whenever the chosen weights $\gamma_{j}$ satisfy

$\sum_{j\geq 1}\gamma_{j}b^{w_{j}}=\sum_{j\geq 1}\gamma_{j}2^{w_{j}}<\infty.$
(23)

However, the sequence of weights $\gamma_{j}=1/j^{3}$ does not always satisfy
Condition (23) if we choose the reduction indices as $w_{j}=\lfloor
p\log_{2}j\rfloor$, since

$\sum_{j\geq 1}\gamma_{j}2^{w_{j}}=\sum_{j\geq 1}j^{-3}2^{\lfloor
p\log_{2}j\rfloor}\geq\sum_{j\geq
1}j^{-3}2^{p\log_{2}j-1}\geq\frac{1}{2}\sum_{j\geq 1}j^{p-3}.$

The latter series only convergence if whenever $3-p>1$, and this is not
satisfied for our choices of $p$ made in Figures 1 and 2, which is $p=2$ and
$p=7/2$, respectively. Thus, this gives rise to the difference in the errors
obtained by the reduced CBC-DBD and non-reduced CBC-DBD algorithms. This
phenomenon is to be expected and shows that the reduction indices and the
weights must be balanced carefully, and that in general the reduced algorithm
works better for situations where the weights $\gamma_{j}$ decay fast.

###  5.2 Computational complexity

Here, we illustrate the computational complexity of the reduced fast CBC-DBD
construction in Algorithm 2 which was proved in Theorem 5. For this purpose,
let $N=2^{m}$, let the weight sequence ${\bm{\gamma}}=(\gamma_{j})_{j\geq 1}$
be given by $\gamma_{j}=(0.95)^{j}$, and let the reduction indices be given by
$w_{j}=\lfloor\frac{3}{2}\log_{2}j\rfloor$ for $j\geq 1$. We measure and
compare the computation times of implementations of Algorithm 2 and the non-
reduced fast CBC-DBD algorithm for lattice rules (see [8] for details on the
implementation of the latter). Note that the chosen weight sequence does not
affect the computation times. The timings were performed on an Intel Core i5
CPU with 2.3 GHz using Python 3.6.3.

Table 1: Computation times (in seconds) for constructing the generating vector ${\bm{z}}$ of a lattice rule with $N=2^{m}$ points in $d$ dimensions using the reduced CBC-DBD algorithm (bold font) and the non-reduced CBC-DBD construction (normal font) with $\alpha=2$, $\gamma_{j}=(0.95)^{j}$, and $w_{j}=\lfloor\frac{3}{2}\log_{2}j\rfloor$. |  $d=50$ |  $d=100$ |  $d=500$ |  $d=1000$ |  $d=2000$
---|---|---|---|---|---
$m=10$ |  0.077 |  0.154 |  0.799 |  1.571 |  3.182
0.017 |  0.018 |  0.02 |  0.021 |  0.025
$m=12$ |  0.128 |  0.252 |  1.224 |  2.424 |  4.908
0.035 |  0.046 |  0.052 |  0.054 |  0.057
$m=14$ |  0.211 |  0.415 |  2.044 |  4.049 |  8.256
0.066 |  0.089 |  0.138 |  0.136 |  0.141
$m=16$ |  0.43 |  0.874 |  4.363 |  8.796 |  17.631
0.103 |  0.152 |  0.299 |  0.354 |  0.359
$m=18$ |  1.467 |  2.982 |  14.924 |  30.545 |  59.967
0.195 |  0.272 |  0.577 |  0.761 |  0.904
$m=20$ |  7.222 |  14.538 |  73.21 |  147.759 |  294.616
0.5 |  0.623 |  1.146 |  1.516 |  1.931

In Table 1 we display the computation times for the construction of the
generating vector ${\bm{z}}$ via the two considered algorithms, where for the
reduction indices we use $w_{j}=\lfloor\frac{3}{2}\log_{2}j\rfloor$. We
emphasize that the used algorithms solely construct the generating vector
${\bm{z}}$ but do not calculate the worst-case error
$e_{N,d,\alpha,{\bm{\gamma}}}({\bm{z}})$, which allows for an unbiased
comparison between the considered algorithms. Table 1 illustrates a dramatic
difference in the computational cost between the non-reduced fast CBC-DBD
construction and the reduced fast CBC-DBD construction. The extent of the
speed-up depends on the chosen reduction indices $w_{j}$. Note, however, that
the reduction indices have to be chosen such that they are balanced with the
weights, in order to guarantee useful error convergence.

##  6 Conclusion

In this paper, we have presented a combination of the CBC-DBD algorithm
introduced in [8] and the reduced construction method in [4] for constructing
good lattice rules for numerical integration in weighted Korobov spaces. In
particular, we have aimed to gain from the reduced construction method to
shrink the computational cost as compared to the non-reduced CBC-DBD
algorithm. We showed that the reduced CBC-DBD construction with quality
measure independent of the smoothness parameter $\alpha$, similarly to [8]
also formulated for product weights, yields lattice rules which admit error
convergence rates that are arbitrarily close to the optimal convergence order.
We remark that there has recently been considerable interest in finding
algorithms that guarantee some degree of universality with respect to the
smoothness parameter and/or the weights (see, e.g., [3]), and also our result
can be seen as a step in this direction. Furthermore, the errors can be
bounded independently of the dimension if the weights satisfy suitable
summability conditions. In addition to these theoretical results, we have
derived a fast implementation of the considered algorithm. Numerical tests
confirm our main findings.

## References

  * [1] R. Cools, F.Y. Kuo, D. Nuyens, G. Suryanarayana. Tent-transformed lattice rules for integration and approximation of multivariate non-periodic functions. J. Complexity 36, 166–181, 2016.
  * [2] J. Dick. On the convergence rate of the component-by-component construction of good lattice rules. J. Complexity 20, 493–522, 2004.
  * [3] J. Dick, T. Goda. Stability of lattice rules and polynomial lattice rules constructed by the component-by-component algorithm. J. Comput. Appl. Math. 382, 113062, 2021.
  * [4] J. Dick, P. Kritzer, G. Leobacher, F. Pillichshammer. A reduced fast component-by-component construction of lattice points for integration in weighted spaces with fast decreasing weights. J. Comput. Appl. Math. 276, 1–15, 2015.
  * [5] J. Dick, P. Kritzer, F. Pillichshammer. Lattice Rules. Springer, Cham, 2022.
  * [6] J. Dick, F.Y. Kuo, I.H. Sloan. High-dimensional integration—the quasi-Monte Carlo way. Acta Numer. 22, 133–288, 2013.
  * [7] J. Dick, D. Nuyens, F. Pillichshammer. Lattice rules for nonperiodic smooth integrands. Numer. Math. 126, 259–291, 2014.
  * [8] A. Ebert, P. Kritzer, D. Nuyens, O. Osisiogu. Digit-by-digit and component-by-component constructions of lattice rules for periodic functions with unknown smoothness. Journal of Complexity, 66, 101555, 2021.
  * [9] T. Goda, K. Suzuki, T. Yoshiki. Lattice rules in non-periodic subspaces of Sobolev spaces. Numer. Math. 141, 399–427, 2019.
  * [10] F.J. Hickernell. A generalized discrepancy and quadrature error bound. Math. Comp., 67, 299–322, 1998.
  * [11] F.J. Hickernell, H. Niederreiter. The existence of good extensible rank-$1$ lattices. J. Complexity, 19, 286–300, 2003.
  * [12] E. Hlawka. Zur angenäherten Berechnung mehrfacher Integrale. Monatsh. Math., 66, 140–151, 1962.
  * [13] L.K. Hua, Y. Wang. Applications of Number Theory to Numerical Analysis. Springer, Berlin, 1981.
  * [14] N.M. Korobov. Approximate evaluation of repeated integrals. Dokl. Akad. Nauk SSSR, 124, 1207–1210, 1959. In Russian. English translation of the theorems in [25].
  * [15] N.M. Korobov. Number-theoretic methods in approximate analysis. Goz. Izdat. Fiz.-Math., 1963. In Russian. English translation of results on optimal coefficients in [25].
  * [16] N.M. Korobov. On the computation of optimal coefficients. Dokl. Akad. Nauk SSSR, 267:289–292, 1982. In Russian. English translation see [17].
  * [17] N.M. Korobov. On the computation of optimal coefficients. Dokl. Akad. Nauk SSSR, 26:590–593, 1982.
  * [18] F.Y. Kuo. Component-by-component constructions achieve the optimal rate of convergence for multivariate integration in weighted Korobov and Sobolev spaces. J. Complexity 19, 301–320, 2003.
  * [19] H. Niederreiter. Random Number Generation and Quasi-Monte Carlo Methods. SIAM, Philadelphia, 1992.
  * [20] E. Novak, H. Woźniakowski. Tractability of Multivariate Problems. Volume I: Linear Information. EMS, Zurich, 2008.
  * [21] D. Nuyens, R. Cools. Fast algorithms for component-by-component construction of rank-$1$ lattice rules in shift-invariant reproducing kernel Hilbert spaces. Math. Comp. 75, 903–920, 2006.
  * [22] I.H. Sloan, S. Joe. Lattice Methods for Multiple Integration. Clarendon Press, Oxford, 1994.
  * [23] I.H. Sloan, H. Woźniakowski. When are quasi Monte Carlo algorithms efficient for high-dimensional problems?. J. Complexity 14, 1–33, 1998.
  * [24] I.H. Sloan, H. Woźniakowski. Tractability of multivariate integration for weighted Korobov classes. J. Complexity 17, 697–721, 2001.
  * [25] A.H. Stroud. Approximate Calculation of Multiple Integrals. Prentice-Hall Series in Automatic Computation, 1971.

Authors’ addresses:

Peter Kritzer
Johann Radon Institute for Computational and Applied Mathematics (RICAM)
Austrian Academy of Sciences
Altenbergerstr. 69, 4040 Linz, Austria.
<EMAIL_ADDRESS>

Onyekachi Osisiogu
Department of Applied Mathematics
Illinois Institute of Technology
Chicago, IL USA.
<EMAIL_ADDRESS>
and
Johann Radon Institute for Computational and Applied Mathematics (RICAM)
Austrian Academy of Sciences
Altenbergerstr. 69, 4040 Linz, Austria.