# The curse of dimensionality for the $L_{p}$-discrepancy with finite $p$

Erich Novak and Friedrich Pillichshammer

###### Abstract

The $L_{p}$-discrepancy is a quantitative measure for the irregularity of
distribution of an $N$-element point set in the $d$-dimensional unit cube,
which is closely related to the worst-case error of quasi-Monte Carlo
algorithms for numerical integration. Its inverse for dimension $d$ and error
threshold $\varepsilon\in(0,1)$ is the minimal number of points in $[0,1)^{d}$
such that the minimal normalized $L_{p}$-discrepancy is less or equal
$\varepsilon$. It is well known, that the inverse of $L_{2}$-discrepancy grows
exponentially fast with the dimension $d$, i.e., we have the curse of
dimensionality, whereas the inverse of $L_{\infty}$-discrepancy depends
exactly linearly on $d$. The behavior of inverse of $L_{p}$-discrepancy for
general $p\not\in\\{2,\infty\\}$ has been an open problem for many years. In
this paper we show that the $L_{p}$-discrepancy suffers from the curse of
dimensionality for all $p$ in $(1,2]$ which are of the form
$p=2\ell/(2\ell-1)$ with $\ell\in\mathbb{N}$.

This result follows from a more general result that we show for the worst-case
error of numerical integration in an anchored Sobolev space with anchor 0 of
once differentiable functions in each variable whose first derivative has
finite $L_{q}$-norm, where $q$ is an even positive integer satisfying
$1/p+1/q=1$.

Keywords: Discrepancy, numerical integration, curse of dimensionality,
tractability, quasi-Monte Carlo MSC 2010: 11K38, 65C05, 65Y20

##  1 Introduction and main result

For a set $\mathcal{P}$ consisting of $N$ points
${\boldsymbol{x}}_{1},{\boldsymbol{x}}_{2},\ldots,{\boldsymbol{x}}_{N}$ in the
$d$-dimensional unit-cube $[0,1)^{d}$ the local discrepancy function
$\Delta_{\mathcal{P}}:[0,1]^{d}\rightarrow\mathbb{R}$ is defined as

$\Delta_{\mathcal{P}}({\boldsymbol{t}})=\frac{|\\{k\in\\{1,2,\ldots,N\\}\ :\
{\boldsymbol{x}}_{k}\in[{\boldsymbol{0}},{\boldsymbol{t}})\\}|}{N}-{\rm
volume}([{\boldsymbol{0}},{\boldsymbol{t}})),$

for ${\boldsymbol{t}}=(t_{1},t_{2},\ldots,t_{d})$ in $[0,1]^{d}$, where
$[{\boldsymbol{0}},{\boldsymbol{t}})=[0,t_{1})\times[0,t_{2})\times\ldots\times[0,t_{d})$.
For a parameter $p\in[1,\infty]$ the $L_{p}$-discrepancy of the point set
$\mathcal{P}$ is defined as the $L_{p}$-norm of the local discrepancy function
$\Delta_{\mathcal{P}}$, i.e.,

$L_{p,N}(\mathcal{P}):=\left(\int_{[0,1]^{d}}|\Delta_{\mathcal{P}}({\boldsymbol{t}})|^{p}\,{\rm
d}{\boldsymbol{t}}\right)^{1/p}\quad\mbox{for $p\in[1,\infty)$,}$

and

$L_{\infty,N}(\mathcal{P}):=\sup_{{\boldsymbol{t}}\in[0,1]^{d}}|\Delta_{\mathcal{P}}({\boldsymbol{t}})|\quad\mbox{for
$p=\infty$.}$

Traditionally, the $L_{\infty}$-discrepancy is called star-discrepancy and is
denoted by $D_{N}^{\ast}(\mathcal{P})$ rather than
$L_{\infty,N}(\mathcal{P})$. The study of $L_{p}$-discrepancy has its roots in
the theory of uniform distribution modulo one; see [2, 13, 21, 23] for
detailed information. It is of particular importance because of its close
relation to numerical integration. We will refer to this issue in Section 2.

Since one is interested in point sets with $L_{p}$-discrepancy as low as
possible it is obvious to study for $d,N\in\mathbb{N}$ the quantity

${\rm disc}_{p}(N,d):=\min_{\mathcal{P}}L_{p}(\mathcal{P}),$

where the minimum is extended over all $N$-element point sets $\mathcal{P}$ in
$[0,1)^{d}$. This quantity is called the $N$-th minimal $L_{p}$-discrepancy in
dimension $d$.

Traditionally, the $L_{p}$-discrepancy is studied from the point of view of a
fixed dimension $d$ and one asks for the asymptotic behavior for increasing
sample sizes $N$. The celebrated result of Roth [31] is the most famous result
in this direction and can be seen as the initial point of discrepancy theory.
Later, Schmidt [36] extended Roth’s lower bound to arbitrary $p>1$. For
$p\in(1,\infty)$ it is known that for every dimension $d\in\mathbb{N}$ there
exist positive reals $c_{d,p},C_{d,p}$ such that for every $N\geq 2$ it holds
true that

$c_{d,p}\frac{(\log N)^{\frac{d-1}{2}}}{N}\leq{\rm disc}_{p}(N,d)\leq
C_{d,p}\frac{(\log N)^{\frac{d-1}{2}}}{N}.$

The upper bound was proven by Davenport [7] for $p=2$, $d=2$, by Roth [32] for
$p=2$ and arbitrary $d$ and finally by Chen [4] in the general case. For more
details see [2]. Explicit constructions of point sets can be found in [6, 7,
8, 11, 22, 33].

Similar results, but less accurate, are available also for
$p\in\\{1,\infty\\}$. See the above references for further information. The
currently best asymptotical lower bound in the $L_{\infty}$-case can be found
in [3].

All the classical bounds have a poor dependence on the dimension $d$. For
large $d$ these bounds are only meaningful in an asymptotic sense (for very
large $N$) and do not give any information about the discrepancy in the pre-
asymptotic regime (see, e.g., [27, 28] or [10, Section 1.7] for discussions).
Nowadays, motivated by applications of point sets with low discrepancy for
numerical integration, there is dire need of information about the dependence
of discrepancy on the dimension.

This problem is studied with the help of the so-called inverse of
$L_{p}$-discrepancy (or, in a more general context, the information
complexity; see Section 2). This concept compares the minimal
$L_{p}$-discrepancy with the initial discrepancy

${\rm disc}_{p}(0,d):=\left(\int_{[0,1]^{d}}\left({\rm
volume}([{\boldsymbol{0}},{\boldsymbol{t}}))\right)^{p}\,{\rm
d}{\boldsymbol{t}}\right)^{1/p},$

which can be interpreted as the $L_{p}$-discrepancy of the empty point set,
and asks for the minimal number $N$ of nodes that is necessary in order to
achieve that the $N$-th minimal $L_{p}$-discrepancy is smaller than
$\varepsilon$ times ${\rm disc}_{p}(0,d)$ for a threshold
$\varepsilon\in(0,1)$. In other words, for $d\in\mathbb{N}$ and
$\varepsilon\in(0,1)$ the inverse of the minimal $L_{p}$-discrepancy is
defined as

$N_{p}^{{\rm disc}}(\varepsilon,d):=\min\\{N\in\mathbb{N}\ :\ {\rm
disc}_{p}(N,d)\leq\varepsilon\ {\rm disc}_{p}(0,d)\\}.$

The question is now how fast $N_{p}^{{\rm disc}}(\varepsilon,d)$ increases,
when $d\rightarrow\infty$ and $\varepsilon\rightarrow 0$.

It is well known and easy to check that for the initial $L_{p}$-discrepancy we
have

${\rm disc}_{p}(0,d)=\left\\{\begin{array}[]{ll}\frac{1}{(p+1)^{d/p}}&\mbox{if
$p\in[1,\infty)$},\\\\[5.0pt] 1&\mbox{if $p=\infty$}.\end{array}\right.$ (1)

Here we observe a difference in the cases of finite and infinite $p$. While
for $p=\infty$ the initial discrepancy equals 1 for every dimension $d$, for
finite values of $p$ the initial discrepancy tends to zero exponentially fast
with the dimension.

For $p\in\\{2,\infty\\}$ the behavior of the inverse of the minimal
$L_{p}$-discrepancy is well understood. In the $L_{2}$-case it is known that
for all $\varepsilon\in(0,1)$ we have

$(1.125)^{d}(1-\varepsilon^{2})\leq N_{2}^{{\rm disc}}(\varepsilon,d)\leq
1.5^{d}\varepsilon^{-2}.$

Here the lower bound was first shown by Woźniakowski in [38] (see also [26,
35]) and the upper bound follows from an easy averaging argument, see, e.g.,
[28, Sec. 9.3.2].

In the $L_{\infty}$-case it was shown by Heinrich, Novak, Wasilkowski and
Woźniakowski in [16] that there exists an absolute positive constant $C$ such
that for every $d\in\mathbb{N}$ and $\varepsilon\in(0,1)$ we have

$N_{\infty}^{{\rm disc}}(\varepsilon,d)\leq Cd\varepsilon^{-2}.$

The currently smallest known value of $C$ is $6.23401\ldots$ as shown in [15]
(thereby improving on other results from [1, 12, 14, 29]). On the other hand,
there exist numbers $c>0$ and $\varepsilon_{0}\in(0,1)$ such that for all
$d\in\mathbb{N}$ and all $\varepsilon\in(0,\varepsilon_{0})$ we have

$N_{\infty}^{{\rm disc}}(\varepsilon,d)\geq cd\varepsilon^{-1},$

as shown by Hinrichs in [17].

So while the inverse of $L_{2}$-discrepancy grows exponentially fast with the
dimension $d$, the inverse of star-discrepancy depends only linearly on the
dimension $d$. One says that the $L_{2}$-discrepancy suffers from the curse of
dimensionality. In information based complexity theory the behavior of the
inverse of star-discrepancy is called “polynomial tractability” (see, e.g.,
[27, 28]).

As we see, the situation is clear (and quite different) for
$p\in\\{2,\infty\\}$. But what happens for all other $p\not\in\\{2,\infty\\}$?
This question has been open for many years.

Just for completeness we remark that the problem has been considered also for
other (semi) norms of the local discrepancy function rather than
$L_{p}$-norms, that are in some sense “close” to the $L_{\infty}$-norm.
Positive results (tractability) have been obtained for exponential Orlicz
norms in [9]. On the other hand, for the BMO-seminorm the curse of
dimensionality has been shown in [30].

All known proofs for lower bounds on the inverse of $L_{2}$-discrepancy are
based on Hilbert-space methods. A very powerful tool in this context developed
in [26] (see also [28, Chapter 12]) is the method of decomposable reproducing
kernels. Unfortunately, it is not obvious how these $L_{2}$-methods could be
applied to the general $L_{p}$-case directly. So one has to find a new way or
one has to figure out the essence of the Hilbert-space based proofs with the
hope to get rid of all $L_{2}$-specific factors in order to find a way to
extend these proofs to the general $L_{p}$-case. We shall follow the latter
path.

Our main result is formulated in the following theorem.

######  Theorem 1.

For every $p$ of the form $p=\frac{2\ell}{2\ell-1}$ with $\ell\in\mathbb{N}$
there exists a real $C_{p}$ that is strictly larger than 1, such that for all
$\varepsilon\in(0,1)$ we have

$N_{p}^{{\rm disc}}(\varepsilon,d)\geq C_{p}^{d}(1+o(1))\quad\mbox{for
$d\rightarrow\infty$}.$

In particular, for all these $p$ the $L_{p}$-discrepancy suffers from the
curse of dimensionality.

At first glance, one would think that the result could be easily extended to
any number $p\in(1,2]$ by means of monotonicity of the $L_{p}$-norm and
squeezing any $p$ between two values of the form given in the theorem above.
However, notice that we have to take the normalized discrepancy into account,
which destroys monotonicity. Having a more careful look at the problem shows
that it might be not so easy to follow this first intuition and in fact, so
far we did not succeed in showing the curse of dimensionality for all
$p\in(1,2]$.

Theorem 1 will follow from a more general result about the integration problem
in the anchored Sobolev space with a $q$-norm that will be introduced and
discussed in the following Section 2. This result will be stated as Theorem 3.

Sometimes a generalized notion of $L_{p}$-discrepancy is studied, where every
point ${\boldsymbol{x}}_{k}$ is equipped with an own weight $a_{k}$ (rather
than the weight $1/N$ for every point). The result from Theorem 1 even holds
for this generalized $L_{p}$-discrepancy. This more general conclusion will be
stated in Section 4 as Theorem 4.

We add a conjecture: We guess that the curse holds for all $p$ with
$1<p<\infty$.

##  2 Relation to numerical integration

It is well known that the $L_{p}$-discrepancy is related to multivariate
integration (see, e.g., [28, Chapter 9]). From now on let $p,q\geq 1$ be such
that $1/p+1/q=1$. For $d=1$ let $W_{q}^{1}([0,1])$ be the space of absolutely
continuous functions whose first derivatives belong to the space
$L_{q}([0,1])$. For $d>1$ consider the $d$-fold tensor product space which is
denoted by

$W_{q}^{\boldsymbol{1}}:=W_{q}^{(1,1,\ldots,1)}([0,1]^{d})$

and which is the Sobolev space of functions on $[0,1]^{d}$ that are once
differentiable in each variable and whose first derivative
$\partial^{d}f/\partial{\boldsymbol{x}}$ has finite $L_{q}$-norm, where
$\partial{\boldsymbol{x}}=\partial x_{1}\partial x_{2}\ldots\partial x_{d}$.
Now consider the subspace of functions that satisfy the boundary conditions
$f({\boldsymbol{x}})=0$ if at least one component of
${\boldsymbol{x}}=(x_{1},\ldots,x_{d})$ equals 0 and equip this subspace with
the norm

$\|f\|_{d,q}:=\left(\int_{[0,1]^{d}}\left|\frac{\partial^{d}}{\partial{\boldsymbol{x}}}f({\boldsymbol{x}})\right|^{q}\,{\rm
d}{\boldsymbol{x}}\right)^{1/q}\quad\mbox{for $q\in[1,\infty)$,}$

and

$\|f\|_{d,\infty}:=\sup_{{\boldsymbol{x}}\in[0,1]^{d}}\left|\frac{\partial^{d}}{\partial{\boldsymbol{x}}}f({\boldsymbol{x}})\right|\quad\mbox{for
$q=\infty$.}$

That is, consider the space

$F_{d,q}:=\\{f\in W_{q}^{\boldsymbol{1}}\ :\ f({\boldsymbol{x}})=0\ \mbox{if
$x_{j}=0$ for some $j\in[d]$ and $\|f\|_{d,q}<\infty$}\\},$

where here and throughout this paper we write $[d]:=\\{1,2,\ldots,d\\}$.

Now consider multivariate integration

$I_{d}(f):=\int_{[0,1]^{d}}f({\boldsymbol{x}})\,{\rm
d}{\boldsymbol{x}}\quad\mbox{for $f\in F_{d,q}$}.$

We approximate the integrals $I_{d}(f)$ by algorithms based on $N$ function
evaluations of the form

$A_{d,N}(f)=\varphi(f({\boldsymbol{x}}_{1}),f({\boldsymbol{x}}_{2}),\ldots,f({\boldsymbol{x}}_{N})),$
(2)

where $\varphi:\mathbb{R}^{N}\rightarrow\mathbb{R}$ is an arbitrary function
and where
${\boldsymbol{x}}_{1},{\boldsymbol{x}}_{2},\ldots,{\boldsymbol{x}}_{N}$ are
points in $[0,1]^{d}$, called integration nodes. Since $f\equiv 0$ belongs to
$F_{d,q}$ we choose $\varphi$ such that $\varphi(0,0,\ldots,0)=0$. Typical
examples are linear algorithms of the form

$A_{d,N}^{{\rm lin}}(f)=\sum_{k=1}^{N}a_{j}f({\boldsymbol{x}}_{k}),$ (3)

where ${\boldsymbol{x}}_{1},{\boldsymbol{x}}_{2},\ldots,{\boldsymbol{x}}_{N}$
are in $[0,1]^{d}$ and $a_{1},a_{2},\ldots,a_{N}$ are real weights that we
call integration weights. If $a_{1}=a_{2}=\ldots=a_{N}=1/N$, then the linear
algorithm (3) is a so-called quasi-Monte Carlo algorithm, for which we will
write $A_{d,N}^{{\rm QMC}}$.

Define the worst-case error of an algorithm (2) by

$e(F_{d,q},A_{d,N})=\sup_{f\in F_{d,q}\atop\|f\|_{d,q}\leq
1}\left|I_{d}(f)-A_{d,N}(f)\right|.$ (4)

For a quasi-Monte Carlo algorithm $A_{d,N}^{{\rm QMC}}$ it is well known (see,
e.g., [35]) that

$e(F_{d,q},A_{d,N}^{{\rm QMC}})=L_{p}(\overline{\mathcal{P}}),$

where $L_{p}(\overline{\mathcal{P}})$ is the $L_{p}$-discrepancy of the point
set111We remark that in [35] the anchored space with anchor $\boldsymbol{1}$
is considered which results in a worst case error of exactly
$L_{p}(\mathcal{P})$, where $\mathcal{P}$ is the node set of the QMC rule.
Here we have chosen the anchor as $\boldsymbol{0}$, and therefore in the
formula for the worst-case error the point set $\overline{\mathcal{P}}$
appears. For details see also [28, Section 9.5.1] for the case $p=2$.

$\overline{\mathcal{P}}=\\{\boldsymbol{1}-{\boldsymbol{x}}_{k}\ :\
k=1,2,\ldots,N\\},$ (5)

where $\boldsymbol{1}-{\boldsymbol{x}}_{k}$ is defined as the component-wise
difference of the vector containing only ones and ${\boldsymbol{x}}_{k}$. From
this point of view we now study the more general problem of numerical
integration in $F_{d,q}$ rather than only the $L_{p}$-discrepancy (which
corresponds to quasi-Monte Carlo algorithms – although with suitably
“reflected” points).

We define the $N$-th minimal worst-case error as

$e_{q}(N,d):=\min_{A_{d,N}}|e(F_{d,q},A_{d,N})|$

where the minimum is extended over all algorithms of the form (2) based on $N$
function evaluations along points
${\boldsymbol{x}}_{1},{\boldsymbol{x}}_{2},\ldots,{\boldsymbol{x}}_{N}$ from
$[0,1)^{d}$. Note that for all $d,N\in\mathbb{N}$ we have

$e_{q}(N,d)\leq{\rm disc}_{p}(N,d).$ (6)

The initial error is

$e_{q}(0,d)=\sup_{f\in F_{d,q}\atop\|f\|_{d,q}\leq 1}\left|I_{d}(f)\right|.$

######  Lemma 2.

Let $d\in\mathbb{N}$ and let $q\in(1,\infty]$ and $p\in[1,\infty)$ with
$1/p+1/q=1$. Then we have

$e_{q}(0,d)=\frac{1}{(p+1)^{d/p}}$

and the worst-case function in $F_{d,q}$ is given by
$h_{d}({\boldsymbol{x}})=h_{1}(x_{1})\cdots h_{1}(x_{d})$ for
${\boldsymbol{x}}=(x_{1},\ldots,x_{d})\in[0,1]^{d}$, where
$h_{1}(x)=1-(1-x)^{p}$.

###### Proof.

Since we are dealing with tensor products of one-dimensional spaces it
suffices to prove the result for $d=1$. For $f\in F_{1,q}$ we have

$\int_{0}^{1}f(x)\,{\rm d}x=\int_{0}^{1}\int_{0}^{x}f^{\prime}(t)\,{\rm
d}t\,{\rm d}x=\int_{0}^{1}f^{\prime}(t)g(t)\,{\rm d}t,$

where $g(t)=1-t$. Applying Hölder’s inequality we obtain

$\left|\int_{0}^{1}f(x)\,{\rm
d}x\right|\leq\|f^{\prime}\|_{L_{q}}\|g\|_{L_{p}}=\|f\|_{1,q}\|g\|_{L_{p}}$

with equality if $f^{\prime}(t)=c(g(t))^{p-1}=c(1-t)^{p-1}$ for some $c$. This
holds for $f(t)=h_{1}(t):=1-(1-t)^{p}$.

We have

$\int_{0}^{1}h_{1}(t)\,{\rm d}t=\frac{p}{p+1}$

and

$\|h_{1}\|_{1,q}=\left(\int_{0}^{1}(px^{p-1})^{q}\,{\rm
d}x\right)^{1/q}=p\left(\frac{1}{(p-1)q+1}\right)^{1/q}=p(1+p)^{1/p-1}.$

Hence,

$e_{q}(0,1)=\int_{0}^{1}\frac{h_{1}(t)}{\|h_{1}\|_{1,q}}\,{\rm
d}t=\frac{1}{(p+1)^{1/p}}.$

∎

Note that for all $q\in(1,\infty]$ and $p\in[1,\infty)$ with $1/p+1/q=1$ and
for all $d\in\mathbb{N}$ we have

$e_{q}(0,d)={\rm disc}_{p}(0,d).$

Now we define the information complexity as the minimal number of function
evaluations necessary in order to reduce the initial error by a factor of
$\varepsilon$. For $d\in\mathbb{N}$ and $\varepsilon\in(0,1)$ put

$N^{{\rm int}}_{q}(\varepsilon,d):=\min\\{N\in\mathbb{N}\ :\
e_{q}(N,d)\leq\varepsilon\ e_{q}(0,d)\\}.$

From (6), (1) and Lemma 2 it follows that for all $q\in(1,\infty]$ and
$p\in[1,\infty)$ with $1/p+1/q=1$ and for all $d\in\mathbb{N}$ and
$\varepsilon\in(0,1)^{d}$ we have

$N^{{\rm int}}_{q}(\varepsilon,d)\leq N^{{\rm disc}}_{p}(\varepsilon,d).$

Hence, Theorem 1 follows from the following more general result.

######  Theorem 3.

For every positive even integer $q$ there exists a real $C=C(q)$, which
depends on $q$ and which is strictly larger than 1, such that for all
$\varepsilon\in(0,1)$ we have

$N_{q}^{{\rm int}}(\varepsilon,d)\geq C^{d}(1+o(1))\quad\mbox{for
$d\rightarrow\infty$}.$ (7)

In particular, for all even integer $q$ the integration problem in $F_{d,q}$
suffers from the curse of dimensionality.

The proof of this result will be given in the following section.

Information about the base $C=C(q)$ of the exponentiation in Theorem 3 will be
given in Section 4.

##  3 The proof of Theorem 3

The proof of Theorem 3 is based on a suitable decomposition of the worst-case
function $h_{1}$ from Lemma 2. This decomposition depends on $q$ and $p$,
respectively, and will determine the base $C$ of the exponentiation in (7).

###### Proof of Theorem 3.

Let $q$ be an even, positive interger and let $p$ be such that $1/p+1/q=1$.
Obviously, then $p=q/(q-1)$ and $p\in(1,2]$. According to Lemma 2 the
univariate worst-case function equals

$h_{1}(x)=1-(1-x)^{p}$

and

$\|h_{1}\|_{1,q}=\frac{p}{(p+1)^{(p-1)/p}}.$

Now we decompose $h_{1}$ in a suitable way into a sum of three functions. For
real parameters $c$ and $a$, with $a\in(0,1)$ and $c\in(0,a/11)$ that will be
determined later put

$h_{1,2,(0)}(x)=\left\\{\begin{array}[]{ll}\frac{1-(1-x)^{p}}{2}&\mbox{if
$x\in[0,c)$,}\\\\[5.0pt] \frac{1-(1-c)^{p}}{2}&\mbox{if
$x\in[c,a-10c)$,}\\\\[5.0pt] \frac{1-(1-c)^{p}}{20c}(a-x)&\mbox{if
$x\in[a-10c,a)$,}\\\\[5.0pt] 0&\mbox{if $x\in[a,1]$,}\end{array}\right.$

and

$h_{1,2,(1)}(x)={\bf 1}_{[a,1]}(x)\left((1-a)^{p}-(1-x)^{p}\right),$

and

$h_{1,1}(x)=\left\\{\begin{array}[]{ll}1-(1-x)^{p}-h_{1,2,(0)}(x)&\mbox{if
$x\in[0,a)$,}\\\\[5.0pt] 1-(1-a)^{p}&\mbox{if $x\in[a,1]$.}\end{array}\right.$

Then we have

$h_{1,1}(x)+h_{1,2,(0)}(x)+h_{1,2,(1)}(x)=1-(1-x)^{p}=h_{1}(x)$

and $h_{1,2,(0)}(x)$ and $h_{1,2,(1)}(x)$ have disjoint support as well as the
derivatives $h_{1,1}^{\prime}$ and $h_{1,2,(1)}^{\prime}$. See Figure 1 for a
graphical illustration of the decomposition.

Figure 1: Plot of the functions $h_{1},h_{1,1},h_{1,2,(0)}$, and $h_{1,2,(1)}$
for $q=4$ (hence $p=4/3$) and $a=0.8$ and $c=0.04$ (later we will use a
different choice of parameters; but with the ones chosen here one gets a
better impression of the principle situation).

Let $d\in\mathbb{N}$. For $\mathfrak{u}\subseteq[d]$ let
$\mathfrak{u}^{c}=[d]\setminus\mathfrak{u}$. Now, for
${\boldsymbol{x}}=(x_{1},\ldots,x_{d})\in[0,1]^{d}$ let

$\displaystyle h_{d}({\boldsymbol{x}})$ $\displaystyle=$
$\displaystyle\prod_{j=1}^{d}h_{1}(x_{j})$ $\displaystyle=$
$\displaystyle\prod_{j=1}^{d}(h_{1,1}(x_{j})+h_{1,2,(0)}(x_{j})+h_{1,2,(1)}(x_{j}))$
$\displaystyle=$
$\displaystyle\sum_{\mathfrak{u}\subseteq[d]}\prod_{j\in\mathfrak{u}^{c}}h_{1,1}(x_{j})\sum_{\mathfrak{v}\subseteq\mathfrak{u}}\prod_{j\in\mathfrak{v}}h_{1,2,(0)}(x_{j})\prod_{j\in\mathfrak{u}\setminus\mathfrak{v}}h_{1,2,(1)}(x_{j}).$

We have

$\|h_{d}\|_{d,q}=\|h_{1}\|_{1,q}^{d}=\left(\frac{p}{(p+1)^{(p-1)/p}}\right)^{d}.$

For a point ${\boldsymbol{x}}\in[0,1]^{d}$ and for $\mathfrak{u}\subseteq[d]$
let ${\boldsymbol{x}}(\mathfrak{u})$ denote the projection of
${\boldsymbol{x}}$ on the coordinates $j\in\mathfrak{u}$.

Now let $N\in\mathbb{N}$ and let
$\mathcal{P}=\\{{\boldsymbol{x}}_{1},{\boldsymbol{x}}_{2},\ldots,{\boldsymbol{x}}_{N}\\}$
be a set of $N$ quadrature nodes in $[0,1]^{d}$. For this specific choice
define the “fooling function”

$g_{d}({\boldsymbol{x}})=\sum_{\mathfrak{u}\subseteq[d]}\prod_{j\not\in\mathfrak{u}}h_{1,1}(x_{j})\sum_{\mathfrak{v}\subseteq\mathfrak{u}}\Big{.}^{*}\prod_{j\in\mathfrak{v}}h_{1,2,(0)}(x_{j})\prod_{j\in\mathfrak{u}\setminus\mathfrak{v}}h_{1,2,(1)}(x_{j}),$
(8)

where the $\ast$ in $\sum^{*}_{\mathfrak{v}\subseteq\mathfrak{u}}$ indicates
that the summation is restricted to all $\mathfrak{v}\subseteq\mathfrak{u}$
such that for all $k\in\\{1,2,\ldots,N\\}$ it holds that

$({\boldsymbol{x}}_{k}(\mathfrak{v}),{\boldsymbol{x}}_{k}(\mathfrak{u}\setminus\mathfrak{v}))\not\in[0,a]^{|\mathfrak{v}|}\times[a,1]^{|\mathfrak{u}|-|\mathfrak{v}|}.$

This condition means that every point from the set $\mathcal{P}$ is outside
the support of
$\prod_{j\not\in\mathfrak{u}}h_{1,1}(x_{j})\prod_{j\in\mathfrak{v}}h_{1,2,(0)}(x_{j})\prod_{j\in\mathfrak{u}\setminus\mathfrak{v}}h_{1,2,(1)}(x_{j})$
and this guarantees that

$g_{d}({\boldsymbol{x}}_{k})=0\quad\mbox{for all $k\in\\{1,2,\ldots,N\\}$.}$

Observe that the fooling function $g_{d}$ is an element of the
$3^{d}$-dimensional (tensor product) subspace generated, for $d=1$, by the
three functions $h_{1,1}$, $h_{1,2,(0)}$ and $h_{1,2,(1)}$. Formally, we prove
the lower bound for this finite-dimensional subspace. We use here notation
from the theory of decomposable kernels (see, e.g., [28, Section 11.5]). This
theory can only be applied for $q=p=2$ and then one can choose the three
functions orthogonal which simplifies the proof a lot (see also Section 5).

Now we show that $\|g_{d}\|_{d,q}\leq\|h_{d}\|_{d,q}$. This is the only part
of the proof where we need that $q$ is an even integer. We have

$\displaystyle\|h_{d}\|_{d,q}^{q}$ $\displaystyle=$
$\displaystyle\int_{[0,1]^{d}}\left|\sum_{\mathfrak{u}\subseteq[d]}\prod_{j\not\in\mathfrak{u}}h_{1,1}^{\prime}(x_{j})\sum_{\mathfrak{v}\subseteq\mathfrak{u}}\prod_{j\in\mathfrak{v}}h_{1,2,(0)}^{\prime}(x_{j})\prod_{j\in\mathfrak{u}\setminus\mathfrak{v}}h_{1,2,(1)}^{\prime}(x_{j})\right|^{q}\,{\rm
d}{\boldsymbol{x}}$ $\displaystyle=$
$\displaystyle\sum_{\mathfrak{u}_{1}\subseteq[d]}\sum_{\mathfrak{v}_{1}\subseteq\mathfrak{u}_{1}}\sum_{\mathfrak{u}_{2}\subseteq[d]}\sum_{\mathfrak{v}_{2}\subseteq\mathfrak{u}_{2}}\ldots\sum_{\mathfrak{u}_{q}\subseteq[d]}\sum_{\mathfrak{v}_{q}\subseteq\mathfrak{u}_{q}}\int_{[0,1]^{d}}$
$\displaystyle\hskip
28.45274pt\prod_{j\in\mathfrak{u}_{1}^{c}}h_{1,1}^{\prime}(x_{j})\prod_{j\in\mathfrak{u}_{2}^{c}}h_{1,1}^{\prime}(x_{j})\ldots\prod_{j\in\mathfrak{u}_{q}^{c}}h_{1,1}^{\prime}(x_{j})$
$\displaystyle\hskip
28.45274pt\prod_{j\in\mathfrak{v}_{1}}h_{1,2,(0)}^{\prime}(x_{j})\prod_{j\in\mathfrak{v}_{2}}h_{1,2,(0)}^{\prime}(x_{j})\ldots\prod_{j\in\mathfrak{v}_{q}}h_{1,2,(0)}^{\prime}(x_{j})$
$\displaystyle\hskip
28.45274pt\prod_{j\in\mathfrak{u}_{1}\setminus\mathfrak{v}_{1}}h_{1,2,(1)}^{\prime}(x_{j})\prod_{j\in\mathfrak{u}_{2}\setminus\mathfrak{v}_{2}}h_{1,2,(0)}^{\prime}(x_{j})\ldots\prod_{j\in\mathfrak{u}_{q}\setminus\mathfrak{v}_{q}}h_{1,2,(1)}^{\prime}(x_{j})\,{\rm
d}{\boldsymbol{x}}$ $\displaystyle=$
$\displaystyle\sum_{\mathfrak{u}_{1}\subseteq[d]}\sum_{\mathfrak{v}_{1}\subseteq\mathfrak{u}_{1}}\sum_{\mathfrak{u}_{2}\subseteq[d]}\sum_{\mathfrak{v}_{2}\subseteq\mathfrak{u}_{2}}\ldots\sum_{\mathfrak{u}_{q}\subseteq[d]}\sum_{\mathfrak{v}_{q}\subseteq\mathfrak{u}_{q}}\prod_{j=1}^{d}\int_{0}^{1}h_{1,1}^{\prime}(x)^{\alpha_{j}}h_{1,2,(0)}^{\prime}(x)^{\beta_{j}}h_{1,2,(1)}^{\prime}(x)^{\gamma_{j}}\,{\rm
d}x,$

where, for $j\in[d]$, we put

$\displaystyle\alpha_{j}$ $\displaystyle=$
$\displaystyle|\\{t\in\\{1,2,\ldots,q\\}\ :\ j\in\mathfrak{u}_{t}^{c}\\}|,$
$\displaystyle\beta_{j}$ $\displaystyle=$
$\displaystyle|\\{t\in\\{1,2,\ldots,q\\}\ :\ j\in\mathfrak{v}_{t}\\}|,$
$\displaystyle\gamma_{j}$ $\displaystyle=$
$\displaystyle|\\{t\in\\{1,2,\ldots,q\\}\ :\
j\in\mathfrak{u}\setminus\mathfrak{v}_{t}\\}|.$

Note that $\alpha_{j},\beta_{j},\gamma_{j}$ also depend on
$\mathfrak{u}_{1},\mathfrak{v}_{1},\mathfrak{u}_{2},\mathfrak{v}_{2},\ldots,\mathfrak{u}_{q},\mathfrak{v}_{q}$.
We have $\alpha_{j},\beta_{j},\gamma_{j}\in\\{0,1,\ldots,q\\}$ and
$\alpha_{j}+\beta_{j}+\gamma_{j}=q$.

For given
$\mathfrak{u}_{t}\subseteq[d],\mathfrak{v}_{t}\subseteq\mathfrak{u}_{t}$ for
$t\in\\{1,2,\ldots,q\\}$, put

$I(\alpha_{j},\beta_{j},\gamma_{j})=\int_{0}^{1}h_{1,1}^{\prime}(x)^{\alpha_{j}}h_{1,2,(0)}^{\prime}(x)^{\beta_{j}}h_{1,2,(1)}^{\prime}(x)^{\gamma_{j}}\,{\rm
d}x.$

Now we show that $I(\alpha_{j},\beta_{j},\gamma_{j})\geq 0$ for all
$\alpha_{j},\beta_{j},\gamma_{j}\in\\{0,1,\ldots,q\\}$ with
$\alpha_{j}+\beta_{j}+\gamma_{j}=q$. This will help us later on when we show
that the norm of $g_{d}$ is dominated by the norm of $h_{d}$.

If $\alpha_{j}>0$ and $\gamma_{j}>0$, then we have
$I(\alpha_{j},\beta_{j},\gamma_{j})=0$, because $h_{1,1}^{\prime}$ and
$h_{1,2,(1)}^{\prime}$ have disjoint support. Likewise, if $\beta_{j}>0$ and
$\gamma_{j}>0$, then we have $I(\alpha_{j},\beta_{j},\gamma_{j})=0$, because
$h_{1,2,(0)}$ and $h_{1,2,(1)}$ have disjoint support.

If $(\alpha_{j},\beta_{j},\gamma_{j})\in\\{(0,0,q),(0,q,0),(q,0,0)\\}$, then
obviously $I(\alpha_{j},\beta_{j},\alpha_{j})>0$.

It remains to consider the case $\alpha_{j}>0,\beta_{j}>0$ and $\gamma_{j}=0$.
In this case $\alpha_{j}+\beta_{j}=q$. If $\alpha_{j}$ (and then also
$\beta_{j}$) is even, then $I(\alpha_{j},\beta_{j},\gamma_{j})>0$.

So it remains to deal with the cases where $\alpha_{j}$ is odd.

Let $a^{*}=1-10^{-q}$ and $c^{*}=10^{-q}$. Let
$\alpha,\beta\in\\{1,\ldots,q-1\\}$ be odd and assume that $\alpha+\beta=q$.
We show that

$I(\alpha,\beta,0)\geq 0\quad\mbox{ for all $a\in[a^{*},1]$ and all
$c\in[0,c^{*}]$.}$ (9)

Let $a\in[a^{*},1]$ and $c\in[0,c^{*}]$. We have

$\displaystyle I(\alpha,\beta,0)$ $\displaystyle=$
$\displaystyle\int_{0}^{c}\left(\frac{p}{2}(1-x)^{p-1}\right)^{\alpha}\left(\frac{p}{2}(1-x)^{p-1}\right)^{\beta}\,{\rm
d}x$ $\displaystyle+\int_{c}^{a-10c}0\,{\rm d}x$
$\displaystyle+\int_{a-10c}^{a}\left(p(1-x)^{p-1}+\frac{1-(1-c)^{p}}{20c}\right)^{\alpha}\left(-\frac{1-(1-c)^{p}}{20c}\right)^{\beta}\,{\rm
d}x$ $\displaystyle=$
$\displaystyle\int_{0}^{c}\left(\frac{p}{2}(1-x)^{p-1}\right)^{q}\,{\rm d}x$
$\displaystyle-\left(\frac{1-(1-c)^{p}}{20c}\right)^{\beta}\int_{a-10c}^{a}\left(p(1-x)^{p-1}+\frac{1-(1-c)^{p}}{20c}\right)^{\alpha}\,{\rm
d}x.$

Note that $(p-1)q=p$ and hence

$\displaystyle I(\alpha,\beta,0)$ $\displaystyle=$
$\displaystyle\left(\frac{p}{2}\right)^{q}\frac{1-(1-c)^{p+1}}{p+1}$
$\displaystyle-\left(\frac{1-(1-c)^{p}}{20c}\right)^{\beta}\int_{a-10c}^{a}\left(p(1-x)^{p-1}+\frac{1-(1-c)^{p}}{20c}\right)^{\alpha}\,{\rm
d}x.$

We have $1-(1-c)^{p}\leq pc$ and $1-a+10c\leq 11c^{*}$. Hence,

$\displaystyle\left(\frac{1-(1-c)^{p}}{20c}\right)^{\beta}\int_{a-10c}^{a}\left(p(1-x)^{p-1}+\frac{1-(1-c)^{p}}{20c}\right)^{\alpha}\,{\rm
d}x$ $\displaystyle\leq$
$\displaystyle\left(\frac{p}{20}\right)^{\beta}\int_{a-10c}^{a}\left(p(1-x)^{p-1}+\frac{p}{20}\right)^{\alpha}\,{\rm
d}x$ $\displaystyle\leq$
$\displaystyle\left(\frac{p}{20}\right)^{\beta}10c\left(p(1-a+10c)^{p-1}+\frac{p}{20}\right)^{\alpha}$
$\displaystyle=$
$\displaystyle\left(\frac{p}{2}\right)^{q}\frac{10c}{10^{\beta}}\left(2(11c^{*})^{p-1}+\frac{1}{10}\right)^{\alpha}$
$\displaystyle\leq$
$\displaystyle\left(\frac{p}{2}\right)^{q}\frac{10c}{10^{q}}\left(\frac{32}{10}\right)^{q-1},$

where we used

$\displaystyle 2(11c^{*})^{p-1}+\frac{1}{10}\leq
2\frac{11^{p-1}}{10^{(p-1)q}}+\frac{1}{10}=2\frac{11^{p-1}}{10^{p}}+\frac{1}{10}=\frac{2}{11}\left(\frac{11}{10}\right)^{p}+\frac{1}{10}\leq\frac{1}{10}\frac{32}{10}.$

Now we obtain

$\displaystyle
I(\alpha,\beta,0)\geq\left(\frac{p}{2}\right)^{q}\left(\frac{1-(1-c)^{p+1}}{p+1}-\frac{c}{10^{q-1}}\left(\frac{32}{10}\right)^{q-1}\right).$

We use $1-(1-c)^{p+1}\geq(p+1)(1-c)^{p}c$. Then we get

$\displaystyle I(\alpha,\beta,0)$ $\displaystyle\geq$
$\displaystyle\left(\frac{p}{2}\right)^{q}c\left((1-c)^{p}-\frac{1}{10^{q-1}}\left(\frac{32}{10}\right)^{q-1}\right)$
$\displaystyle\geq$
$\displaystyle\left(\frac{p}{2}\right)^{q}c\left(\left(1-\frac{1}{10^{q}}\right)^{p}-\left(\frac{32}{100}\right)^{q-1}\right)$
$\displaystyle=$
$\displaystyle\left(\frac{p}{2}\right)^{q}c\left(\left(1-\frac{1}{10^{q}}\right)^{q/(q-1)}-\left(\frac{32}{100}\right)^{q-1}\right)$
$\displaystyle\geq$
$\displaystyle\left(\frac{p}{2}\right)^{q}c\frac{6601}{10000}\geq 0.$

Hence (9) is shown.

From now on let $a\in[a^{*},1)$ and $c\in(0,c^{*}]$. We summarize: for
$\alpha_{j},\beta_{j},\gamma_{j}\in\\{0,1,\ldots,q\\}$ and
$\alpha_{j}+\beta_{j}+\gamma_{j}=q$ we have the following situation:

$\begin{array}[]{c|c|c||c|l}\alpha_{j}&\beta_{j}&\gamma_{j}&I(\alpha_{j},\beta_{j},\gamma_{j})&\mbox{reason}\\\
\hline\cr=0&=0&>0&>0&\gamma_{j}=q\\\ =0&>0&=0&>0&\beta_{j}=q\\\
0&>0&>0&=0&\mbox{disjoint support of $h_{1,2,(0)}$ and $h_{1,2,(1)}$}\\\
>0&=0&=0&>0&\alpha_{j}=q\\\ >0&=0&>0&=0&\mbox{disjoint support of
$h_{1,1}^{\prime}$ and $h_{1,2,(1)}^{\prime}$}\\\ >0&>0&=0&>0&\mbox{special
choice $a\in[a^{*},1)$ and $c\in(0,c^{*}]$}\\\ >0&>0&>0&=0&\mbox{disjoint
support of $h_{1,2,(0)}$ and $h_{1,2,(1)}$}\end{array}$

Thus, in any case we have $I(\alpha_{j},\beta_{j},\gamma_{j})\geq 0$. Hence

$\displaystyle\|h_{d}\|_{d,q}^{q}$ $\displaystyle=$
$\displaystyle\sum_{\mathfrak{u}_{1}\subseteq[d]}\sum_{\mathfrak{v}_{1}\subseteq\mathfrak{u}_{1}}\sum_{\mathfrak{u}_{2}\subseteq[d]}\sum_{\mathfrak{v}_{2}\subseteq\mathfrak{u}_{2}}\ldots\sum_{\mathfrak{u}_{q}\subseteq[d]}\sum_{\mathfrak{v}_{q}\subseteq\mathfrak{u}_{q}}\prod_{j=1}^{d}I(\alpha_{j},\beta_{j},\gamma_{j})$
$\displaystyle\geq$
$\displaystyle\sum_{\mathfrak{u}_{1}\subseteq[d]}\sum_{\mathfrak{v}_{1}\subseteq\mathfrak{u}_{1}}\Big{.}^{*}\sum_{\mathfrak{u}_{2}\subseteq[d]}\sum_{\mathfrak{v}_{2}\subseteq\mathfrak{u}_{2}}\Big{.}^{*}\ldots\sum_{\mathfrak{u}_{q}\subseteq[d]}\sum_{\mathfrak{v}_{q}\subseteq\mathfrak{u}_{4}}\Big{.}^{*}\prod_{j=1}^{d}I(\alpha_{j},\beta_{j},\gamma_{j})$
$\displaystyle=$
$\displaystyle\int_{[0,1]^{d}}\left|\sum_{\mathfrak{u}\subseteq[d]}\prod_{j\not\in\mathfrak{u}}h_{1,1}^{\prime}(x_{j})\sum_{\mathfrak{v}\subseteq\mathfrak{u}}\Big{.}^{*}\prod_{j\in\mathfrak{v}}h_{1,2,(0)}^{\prime}(x_{j})\prod_{j\in\mathfrak{u}\setminus\mathfrak{v}}h_{1,2,(1)}^{\prime}(x_{j})\right|^{q}\,{\rm
d}{\boldsymbol{x}}$ $\displaystyle=$ $\displaystyle\|g_{d}\|_{d,q}^{q}.$

Now set
$\widetilde{g}_{d}({\boldsymbol{x}}):=(1/\|h_{d}\|_{d,q})g_{d}({\boldsymbol{x}})$
such that $\|\widetilde{g}_{d}\|_{d,q}\leq 1$.

Put, for $(a,c)\in[a^{*},1]\times[0,c^{*}]$,

$\displaystyle I_{1,2,(0)}(a,c)$ $\displaystyle:=$
$\displaystyle\int_{0}^{1}h_{1,2,(0)}(x)\,{\rm d}x$ $\displaystyle=$
$\displaystyle\frac{(1-(1-c)^{p})((p+1)(a-5c)-1)+pc(1-c)^{p}}{2(p+1)}$

and

$I_{1,2,(1)}(a):=\int_{0}^{1}h_{1,2,(1)}(x)\,{\rm
d}x=(1-a)^{p+1}\frac{p}{p+1}.$

Next we show that we can choose $c\in(0,c^{*})$ such that
$I_{1,2,(0)}(a^{*},c)=I_{1,2,(1)}(a^{*})$.

We have

$\displaystyle\frac{I_{1,2,(0)}(a^{*},c^{*})}{I_{1,2,(1)}(a^{*})}$
$\displaystyle=$
$\displaystyle\frac{(1-(1-c^{*})^{p})((p+1)(a^{*}-5c^{*})-1)+pc^{*}(1-c^{*})^{p}}{2(1-a^{*})^{p+1}p}$
$\displaystyle=$
$\displaystyle\frac{(1-(1-c^{*})^{p})((p+1)(1-6c^{*})-1)+pc^{*}(1-c^{*})^{p}}{2(c^{*})^{p+1}p}$
$\displaystyle\geq$
$\displaystyle\frac{p(1-c^{*})^{p-1}((p+1)(1-6c^{*})-1)+pc^{*}(1-c^{*})^{p}}{2(c^{*})^{p+1}p}$
$\displaystyle=$
$\displaystyle\frac{(1-c^{*})^{p-1}}{2(c^{*})^{p+1}}((p+1)(1-6c^{*})-1+c^{*}(1-c^{*}))$
$\displaystyle\geq$ $\displaystyle\frac{1-11c^{*}-(c^{*})^{2}}{2(c^{*})^{2}}$
$\displaystyle=$
$\displaystyle\tfrac{1}{2}10^{2q}-\tfrac{11}{2}10^{q}-\tfrac{1}{2}>1.$

Hence $I_{1,2,(0)}(a^{*},c^{*})>I_{1,2,(1)}(a^{*})$. Now, since
$I_{1,2,(0)}(a^{*},0)=0<I_{1,2,(1)}(a^{*})$, we can find a $c\in(0,c^{*})$
such that $I_{1,2,(0)}(a^{*},c)=I_{1,2,(1)}(a^{*})$, according to the mean
value theorem.

From now on let

$c\in(0,c^{*})\mbox{ be such that $I_{1,2,(0)}(a^{*},c)=I_{1,2,(1)}(a^{*})$.}$
(10)

In the following we use $(x)_{+}=x$ if $x>0$ and 0 if $x\leq 0$. Since
$\widetilde{g}_{d}({\boldsymbol{x}}_{k})=0$ for all $k\in\\{1,2,\ldots,N\\}$
and since $\varphi(0,0,\ldots,0)=0$ (here $\varphi$ is from (2)) we have for
any algorithm (2) that is based on $\mathcal{P}$ that

$\displaystyle e(F_{d,q},A_{d,N})$ (11) $\displaystyle\geq$
$\displaystyle\int_{[0,1]^{d}}\widetilde{g}_{d}({\boldsymbol{x}})\,{\rm
d}{\boldsymbol{x}}$ $\displaystyle=$
$\displaystyle\frac{1}{\|h_{d}\|_{d,q}}\sum_{\mathfrak{u}\subseteq[d]}\left(\int_{0}^{1}h_{1,1}(x)\,{\rm
d}x\right)^{d-|\mathfrak{u}|}$ $\displaystyle\hskip
51.21504pt\times\sum_{\mathfrak{v}\subseteq\mathfrak{u}}\Big{.}^{*}\left(\int_{0}^{1}h_{1,2,(0)}(x)\,{\rm
d}x\right)^{|\mathfrak{v}|}\left(\int_{0}^{1}h_{1,2,(1)}(x)\,{\rm
d}x\right)^{|\mathfrak{u}|-|\mathfrak{v}|}.$

Put

$\displaystyle\alpha_{1}:=\int_{0}^{1}h_{1,1}(x)\,{\rm
d}x=\frac{p}{p+1}(1-(1-a^{*})^{p+1})-I_{1,2,(0)}(a^{*},c)$

and remember that according to our choice (10) we have

$\displaystyle\int_{0}^{1}h_{1,2,(0)}(x)\,{\rm
d}x=\int_{0}^{1}h_{1,2,(1)}(x)\,{\rm d}x.$

Now we continue from (11) and obtain

$\displaystyle e(F_{d,q},A_{d,N})$ $\displaystyle\geq$
$\displaystyle\frac{1}{\|h_{d}\|_{d,q}}\sum_{\mathfrak{u}\subseteq[d]}\alpha_{1}^{d-|\mathfrak{u}|}\left(\int_{0}^{1}h_{1,2,(0)}(x)\,{\rm
d}x\right)^{|\mathfrak{u}|}\sum_{\mathfrak{v}\subseteq\mathfrak{u}}\Big{.}^{*}1$
$\displaystyle\geq$
$\displaystyle\frac{1}{\|h_{d}\|_{d,q}}\sum_{\mathfrak{u}\subseteq[d]}\alpha_{1}^{d-|\mathfrak{u}|}\left(\int_{0}^{1}h_{1,2,(0)}(x)\,{\rm
d}x\right)^{|\mathfrak{u}|}(2^{|\mathfrak{u}|}-N)_{+}$ $\displaystyle=$
$\displaystyle\frac{1}{\|h_{d}\|_{d,q}}\sum_{\mathfrak{u}\subseteq[d]}\alpha_{1}^{d-|\mathfrak{u}|}\left(2\int_{0}^{1}h_{1,2,(0)}(x)\,{\rm
d}x\right)^{|\mathfrak{u}|}\left(1-\frac{N}{2^{|\mathfrak{u}|}}\right)_{+},$

where we used that for every $\mathfrak{u}\subseteq[d]$ at most $N$ of the
intervals

$\prod_{j\in\mathfrak{v}}[0,a^{*}]\prod_{j\in\mathfrak{u}\setminus\mathfrak{v}}[a^{*},1]\prod_{j\not\in\mathfrak{u}}[0,1]$

with $\mathfrak{v}\subseteq\mathfrak{u}$ can contain a point from the node set
$\mathcal{P}_{N}$.

Put

$\alpha_{2}:=2\int_{0}^{1}h_{1,2,(0)}(x)\,{\rm d}x.$

Then we have further

$\displaystyle e(F_{d,q},A_{d,N})$ $\displaystyle\geq$
$\displaystyle\frac{1}{\|h_{d}\|_{d,q}}\sum_{\mathfrak{u}\subseteq[d]}\alpha_{1}^{d-|\mathfrak{u}|}\alpha_{2}^{|\mathfrak{u}|}\left(1-\frac{N}{2^{|\mathfrak{u}|}}\right)_{+}$
$\displaystyle=$
$\displaystyle\frac{1}{\|h_{d}\|_{d,q}}\sum_{k=0}^{d}{d\choose
k}\alpha_{1}^{d-k}\alpha_{2}^{k}\left(1-\frac{N}{2^{k}}\right)_{+}$
$\displaystyle=$
$\displaystyle\frac{1}{\|h_{d}\|_{d,q}}\alpha_{1}^{d}\sum_{k=0}^{d}{d\choose
k}\alpha_{3}^{k}\left(1-\frac{N}{2^{k}}\right)_{+},$

where we put

$\alpha_{3}:=\frac{\alpha_{2}}{\alpha_{1}}>0.$

Since the lower bound on the error is independent of the choice of
$\mathcal{P}_{N}$ it follows that

$e_{q}(N,d)\geq\frac{1}{\|h_{d}\|_{d,q}}\alpha_{1}^{d}\sum_{k=0}^{d}{d\choose
k}\alpha_{3}^{k}\left(1-\frac{N}{2^{k}}\right)_{+}.$

For the normalized $n$-th minimal error we therefore obtain

$\frac{e_{q}(N,d)}{e_{q}(0,d)}\geq\frac{1}{\|h_{d}\|_{d,q}\,e_{q}(0,d)}\alpha_{1}^{d}\sum_{k=0}^{d}{d\choose
k}\alpha_{3}^{k}\left(1-\frac{N}{2^{k}}\right)_{+}.$

We have

$\|h_{d}\|_{d,q}\,e_{q}(0,d)=\left(\frac{p}{p+1}\right)^{d}$

and hence

$\frac{e_{q}(N,d)}{e_{q}(0,d)}\geq\left(\frac{p+1}{p}\right)^{d}\alpha_{1}^{d}\sum_{k=0}^{d}{d\choose
k}\alpha_{3}^{k}\left(1-\frac{N}{2^{k}}\right)_{+}.$ (12)

Now we proceed using ideas from [28, p. 185]. Let $b\in(0,1)$ and let
$N=\lfloor C^{d}\rfloor$ with $C\in(1,2^{\alpha_{3}/(1+\alpha_{3})})$. This
means that

$\frac{C}{2^{\alpha_{3}/(1+\alpha_{3})}}<1.$

Then there exists a positive $c$ such that

$c<\frac{\alpha_{3}}{1+\alpha_{3}}\quad\mbox{ and }\quad\frac{C}{2^{c}}<1.$

Put $k(d):=\lfloor cd\rfloor$. For sufficiently large $d$ we have

$\frac{N}{2^{k}}\leq\frac{C^{d}}{2^{cd-1}}=2\left(\frac{C}{2^{c}}\right)^{d}\leq
b\quad\mbox{ for all $k\in(k(d),d]$.}$ (13)

Put further $C_{d,k}:={d\choose k}\alpha_{3}^{k}$. Then (12) and (13) imply
that

$\displaystyle\frac{e_{q}(\lfloor C^{d}\rfloor,d)}{e_{q}(0,d)}$
$\displaystyle\geq$
$\displaystyle\left(\frac{p+1}{p}\right)^{d}\alpha_{1}^{d}\sum_{k=k(d)+1}^{d}C_{d,k}\left(1-\frac{N}{2^{k}}\right)_{+}$
$\displaystyle\geq$
$\displaystyle(1-b)\left(\frac{p+1}{p}\right)^{d}\alpha_{1}^{d}\sum_{k=k(d)+1}^{d}C_{d,k}$
$\displaystyle=$
$\displaystyle(1-b)\left(\frac{p+1}{p}\right)^{d}\alpha_{1}^{d}\left(\sum_{k=0}^{d}C_{d,k}-\sum_{k=0}^{k(d)}C_{d,k}\right).$

Note that

$\sum_{k=0}^{d}C_{d,k}=(1+\alpha_{3})^{d}=\frac{(\alpha_{1}+\alpha_{2})^{d}}{\alpha_{1}^{d}}$

and

$\displaystyle\alpha_{1}+\alpha_{2}$ $\displaystyle=$
$\displaystyle\int_{0}^{1}h_{1,1}(x)\,{\rm
d}x+2\int_{0}^{1}h_{1,2,(0)}(x)\,{\rm d}x$ $\displaystyle=$
$\displaystyle\int_{0}^{1}h_{1,1}(x)\,{\rm
d}x+\int_{0}^{1}h_{1,2,(0)}(x)\,{\rm d}x+\int_{0}^{1}h_{1,2,(1)}(x)\,{\rm d}x$
$\displaystyle=$ $\displaystyle\int_{0}^{1}h_{1}(x)\,{\rm d}x$
$\displaystyle=$ $\displaystyle\int_{0}^{1}1-(1-x)^{p}\,{\rm d}x$
$\displaystyle=$ $\displaystyle\frac{p}{p+1}.$

This yields

$\displaystyle\frac{e_{q}(\lfloor C^{d}\rfloor,d)}{e_{q}(0,d)}$
$\displaystyle\geq$
$\displaystyle(1-b)\left(\frac{p+1}{p}(\alpha_{1}+\alpha_{2})\right)^{d}\left(1-\frac{\sum_{k=0}^{k(d)}C_{d,k}}{(1+\alpha_{3})^{d}}\right)$
$\displaystyle=$
$\displaystyle(1-b)\left(1-\frac{\sum_{k=0}^{k(d)}C_{d,k}}{(1+\alpha_{3})^{d}}\right).$

Now put

$\alpha(d):=\frac{\sum_{k=0}^{k(d)}C_{d,k}}{(1+\alpha_{3})^{d}}.$

It is shown in [28, p. 185] that $\alpha(d)$ tends to zero when
$d\rightarrow\infty$. Hence, for any positive $\delta$ we can find an integer
$d(\delta)$ such that for all $d\geq d(\delta)$ we have

$1\geq\frac{e_{q}(\lfloor C^{d}\rfloor,d)}{e_{q}(0,d)}\geq(1-b)(1-\delta).$

Since $b$ and $\delta$ can be arbitrarily close to zero, it follows that

$\lim_{d\rightarrow\infty}\frac{e_{q}(\lfloor C^{d}\rfloor,d)}{e_{q}(0,d)}=1,$

and this holds true for all $C\in(1,2^{\alpha_{3}/(1+\alpha_{3})})$.

Now we proceed like in [28, p. 186]. Take $\varepsilon\in(0,1)$. For large $d$
we have

$\varepsilon e_{q}(0,d)<e_{q}(\lfloor C^{d}\rfloor,d)=e_{q}(0,d)(1+o(1))$

and therefore $N_{q}^{{\rm int}}(\varepsilon,d)\geq C^{d}(1+o(1))$. Since
$C>1$ this means the curse of dimensionality. ∎

##  4 Some remarks

Some remarks are in order.

### Possible values for $C$ in Theorem 3.

According to the proof of Theorem 3 we have

$\alpha_{3}=\frac{\alpha_{2}}{\alpha_{1}}=\frac{2I_{1,2,(0)}(a^{*},c)}{\frac{p}{p+1}(1-(1-a^{*})^{p+1})-I_{1,2,(0)}(a^{*},c)},$

where $c$ is choosen according to (10), which implies

$I_{1,2,(0)}(a^{*},c)=I_{1,2,(1)}(a^{*})=\frac{p}{p+1}(1-a^{*})^{p+1}.$

Hence,

$\alpha_{3}=\frac{2(1-a^{*})^{p+1}}{1-2(1-a^{*})^{p+1}}$

and further

$\frac{\alpha_{3}}{1+\alpha_{3}}=2(1-a^{*})^{p+1}=\frac{2}{10^{q(p+1)}}\quad\mbox{
and }\quad 2^{\alpha_{3}/(1+\alpha_{3})}=4^{10^{-q(p+1)}}.$

We compute some values for $2^{\alpha_{3}/(1+\alpha_{3})}$:

$\begin{array}[]{c|c}q&2^{\alpha_{3}/(1+\alpha_{3})}\\\ \hline\cr
2&1.01396\ldots\\\ 4&1.000003482\ldots\\\ 6&1.00000000051675\ldots\end{array}$

######  Remark 1.

Our choice for $a^{*}$ was very arbitrary. One can try to find the smallest
possible $a^{*}$ such that all conditions are satisfied, i.e.,
$I(\alpha,1-\alpha,0)\geq$ for all odd $\alpha$ in $\\{1,\ldots,q-1\\}$ and
$I_{1,2,(0)}=I_{1,2,(1)}$. This way one can improve the value of
$2^{\alpha_{3}/(1+\alpha_{3})}$. For example for $q=4$ we also found
$a^{*}=0.930338256\ldots$ and $c=0.00186068\ldots$. With this choice we obtain

$2^{\alpha_{3}/(1+\alpha_{3})}=1.00277\ldots.$

Hence we can deduce that

$N_{4}^{{\rm int}}(\varepsilon,d)\geq(1.00277)^{d}(1+o(1)).$

### History and related problems.

During the proof of Theorem 3 we already observed that, formally, we prove a
lower bound for the integration problem and a $3^{d}$-dimensional tensor
product space. We give some history of such problems, in particular
(in)tractability results. The first results appeared in 1997. In [25] it is
proved that some non-trivial problems are easy (tractable) and for other
problems the curse of dimensionality is present. An important case is the
space of trigonometric polynomials of degree one in each variable; Sloan and
Woźniakowski [34] prove the curse for this space. The same space, but with
different norms, was studied later in [24]. To prove the curse for this norm,
a new technique was developed in [37] and further studied in [18] and [19].

As we explain in the next section, also the method of decomposable kernels
(see, e.g., [28, Theorem 11.12]) can be seen as a contribution to this
problem, even if the authors at that time did not present it that way. This
technique works fine in the case of finite smoothness and is related to the
technique of bump functions, see [20] for a discussion and new results. Bump
functions do not work for analytic functions, see again [18, 19], and
surprisingly they also do not work for functions of very low degree of
smoothness, see [20].

### Generalized $L_{p}$-discrepancy.

Sometimes a more general version of $L_{p}$-discrepancy is considered. Here
for points
$\mathcal{P}=\\{{\boldsymbol{x}}_{1},{\boldsymbol{x}}_{2},\ldots,{\boldsymbol{x}}_{N}\\}$
and corresponding coefficients $\mathcal{A}=\\{a_{1},a_{2},\ldots,a_{N}\\}$
the discrepancy function is

$\overline{\Delta}_{\mathcal{P},\mathcal{A}}({\boldsymbol{t}})=\sum_{k=1}^{N}a_{k}{\bf
1}_{[0,{\boldsymbol{t}})}({\boldsymbol{x}}_{k})-t_{1}t_{2}\cdots t_{d}$

for ${\boldsymbol{t}}=(t_{1},t_{2},\ldots,t_{d})$ in $[0,1]^{d}$ and the
generalized $L_{p}$-discrepancy is

$\overline{L}_{p,N}(\mathcal{P},\mathcal{A})=\left(\int_{[0,1]^{d}}|\overline{\Delta}_{\mathcal{P},\mathcal{A}}({\boldsymbol{t}})|^{p}\,{\rm
d}{\boldsymbol{t}}\right)^{1/p}\quad\mbox{for $p\in[1,\infty)$,}$

with the usual adaptions for $p=\infty$. If $a_{1}=a_{2}=\ldots=a_{N}=1/N$,
then we are back to the classical definition of $L_{p}$-discrepancy from
Section 1.

Now the $N$-th minimal generalized $L_{p}$-discrepancy in dimension $d$ is
defined as

$\overline{{\rm
disc}}_{p}(N,d):=\min_{\mathcal{P},\mathcal{A}}\overline{L}_{p}(\mathcal{P},\mathcal{A})$

where the minimum is extended over all $N$-element point sets $\mathcal{P}$ in
$[0,1)^{d}$ and over all corresponding coefficients $\mathcal{A}$, and its
inverse is

$N_{p}^{\overline{{\rm disc}}}(\varepsilon,d):=\min\\{N\in\mathbb{N}\ :\
\overline{{\rm disc}}_{p}(N,d)\leq\varepsilon\ \overline{{\rm
disc}}_{p}(0,d)\\},$

where, obviously, $\overline{{\rm disc}}_{p}(0,d)={\rm disc}_{p}(0,d)$.

Turn to the integration problem in $F_{d,q}$, then the worst-case error (4) of
a linear algorithm (3) is

$e(F_{d,q},A_{d,N}^{{\rm
lin}})=\overline{L}_{p}(\overline{\mathcal{P}},\mathcal{A}),$

where $\overline{\mathcal{P}}$ is given in (5) and $\mathcal{A}$ consists of
exactly the coefficients from the given linear algorithm. Again, this is well
known (see [28] or [35]).

With these preparations it follows from Theorem 3 that also the generalized
$L_{p}$-discrepancy suffers for all $p$ of the form $p=\frac{2\ell}{2\ell-1}$
with $\ell\in\mathbb{N}$ from the curse of dimensionality.

######  Theorem 4.

For every $p$ of the form $p=\frac{2\ell}{2\ell-1}$ with $\ell\in\mathbb{N}$
there exists a real $C_{p}$ that is strictly larger than 1, such that for all
$\varepsilon\in(0,1)$ we have

$N_{p}^{\overline{{\rm disc}}}(\varepsilon,d)\geq
C_{p}^{d}(1+o(1))\quad\mbox{for $d\rightarrow\infty$}.$

In particular, for all these $p$ the generalized $L_{p}$-discrepancy suffers
from the curse of dimensionality.

##  5 The case $p=q=2$ revisited and an outlook on the general problem

As already mentioned, the case $p=q=2$ is well established and can be tackled
with the method of decomposable kernels (see [26] and also [28, Chapter 12]).
This method can be mimicked with the method presented here by taking the
decomposition

$\displaystyle h_{1,1}(x)$ $\displaystyle=$ $\displaystyle(2-a)\min(x,a),$
$\displaystyle h_{1,2,(0)}(x)$ $\displaystyle=$
$\displaystyle\mathbf{1}_{[0,a]}(x)x(a-x),$ $\displaystyle h_{1,2,(1)}(x)$
$\displaystyle=$
$\displaystyle\mathbf{1}_{[a,1]}(x)\left(x(2-x)-a(2-a)\right)$

for some $a\in(0,1)$ (compare this with [28, p. 192]). See Figure 2.

Figure 2: Plot of the functions $h_{1},h_{1,1},h_{1,2,(0)}$, and $h_{1,2,(1)}$
for $q=p=2$ and $a=4^{1/3}/(1+4^{1/3})$.

Define the fooling function $g_{d}$ like in (8), but with the present
decomposition, it follows almost immediately from orthogonality arguments that
$\|g_{d}\|_{d,2}\leq\|h_{d}\|_{d,2}$. Choosing $a=4^{1/3}/(1+4^{1/3})$
(compare again with [28, p. 192]) gives in addition that
$\int_{0}^{1}h_{1,2,(0)}(x)\,{\rm d}x=\int_{0}^{1}h_{1,2,(1)}(x)\,{\rm d}x$
such that the whole proof of Theorem 3 goes through with the present
decomposition, but now one obtains the improved quantity

$2^{\alpha_{3}/(1+\alpha_{3})}=1.08332\ldots,$

i.e.,

$N_{2}^{{\rm int}}(\varepsilon,d)\geq(1.08332)^{d}(1+o(1)),$

which is exactly the value obtained in [28, p. 193]. This reproves the result
for $p=q=2$, but without using the method of decomposable kernels.

From this point of view, the following decomposition for general
$q\in(1,\infty)$ would be somehow obvious:

$\displaystyle h_{1,1}(x)$ $\displaystyle=$
$\displaystyle\frac{1-(1-a)^{p}}{a}\min(x,a),$ $\displaystyle h_{1,2,(0)}(x)$
$\displaystyle=$
$\displaystyle\mathbf{1}_{[0,a]}(x)\left((1-(1-x)^{p})-\frac{x}{a}(1-(1-a)^{p})\right),$
$\displaystyle h_{1,2,(1)}(x)$ $\displaystyle=$
$\displaystyle\mathbf{1}_{[a,1]}(x)\left((1-(1-x)^{p})-(1-(1-a)^{p})\right).$

Choosing $a=2^{\frac{p}{p+1}}/(1+2^{\frac{p}{p+1}})$ one obtains again that
$\int_{0}^{1}h_{1,2,(0)}(x)\,{\rm d}x=\int_{0}^{1}h_{1,2,(1)}(x)\,{\rm d}x$.
However, choosing the fooling function $g_{d}$ like in (8) the problem is to
show the estimate $\|g_{d}\|_{d,q}\leq\|h_{d}\|_{d,q}$. As soon as this could
be done, one can tackle the general $q$ case with the proof method from
Theorem 3.

## References

  * [1] C. Aistleitner: Covering numbers, dyadic chaining and discrepancy. J. Complexity 27 (6): 531–540, 2011.
  * [2] J. Beck and W.W.L. Chen: Irregularities of Distribution. Cambridge University Press, Cambridge, 1987.
  * [3] D. Bilyk, M.T. Lacey, and A. Vagharshakyan: On the small ball inequality in all dimensions. J. Funct. Anal. 254 (9): 2470–2502, 2008.
  * [4] W.W.L. Chen: On irregularities of distribution. Mathematika 27: 153–170, 1981.
  * [5] W.W.L. Chen: On irregularities of distribution II. Quart. J. Math. Oxford 34: 257–279, 1983.
  * [6] W.W.L. Chen and M.M. Skriganov: Explicit constructions in the classical mean squares problem in irregularities of point distribution. J. Reine Angew. Math. 545: 67–95, 2002.
  * [7] H. Davenport: Note on irregularities of distribution. Mathematika 3: 131–135, 1956.
  * [8] J. Dick: Discrepancy bounds for infinite-dimensional order two digital sequences over $\mathbb{F}_{2}$. J. Number Theory 136: 204–232, 2014.
  * [9] J. Dick, A. Hinrichs, F. Pillichshammer, and J. Prochno: Tractability properties of the discrepancy in Orlicz norms. J. Complexity 61, paper ref. 101468, 9 pp., 2020.
  * [10] J. Dick, P. Kritzer, and F. Pillichshammer: Lattice Rules – Numerical Integration, Approximation, and Discrepancy. Springer Series in Computational Mathematics 58, Springer, Cham, 2022.
  * [11] J. Dick and F. Pillichshammer: Optimal $\mathcal{L}_{2}$ discrepancy bounds for higher order digital sequences over the finite field $\mathbb{F}_{2}$. Acta Arith. 162: 65–99, 2014.
  * [12] B. Doerr: A sharp discrepancy bound for jittered sampling. Math. Comp. 91(336): 1871–1892, 2022.
  * [13] M. Drmota and R.F. Tichy: Sequences, Discrepancies and Applications. Lecture Notes in Mathematics 1651, Springer Verlag, Berlin, 1997.
  * [14] M. Gnewuch and N. Hebbinghaus: Discrepancy bounds for a class of negatively dependent random points including Latin hypercube samples. Ann. Appl. Probab. 31(4): 1944–1965, 2021.
  * [15] M. Gnewuch, H. Pasing, and Ch. Weiss: A generalized Faulhaber inequality, improved bracketing covers, and applications to discrepancy. Math. Comp. 90 (332): 2873–2898, 2021.
  * [16] S. Heinrich, E. Novak, G. Wasilkowski, and H. Woźniakowski: The inverse of the star-discrepancy depends linearly on the dimension. Acta Arith. 96(3): 279–302, 2001.
  * [17] A. Hinrichs: Covering numbers, Vapnik-Červonenkis classes and bounds for the star-discrepancy. J. Complexity 20(4): 477–483, 2004.
  * [18] A. Hinrichs, D. Krieg, E. Novak and J. Vybíral: Lower bounds for the error of quadrature formulas for Hilbert spaces, J. Complexity 65, paper ref. 101544, 20 pp., 2021.
  * [19] A. Hinrichs, D. Krieg, E. Novak and J. Vybíral: Lower bounds for integration and recovery in $L_{2}$, J. Complexity 72, paper ref. 101662, 15 pp., 2022.
  * [20] D. Krieg and J. Vybíral: New lower bounds for the integration of periodic functions. Preprint arXiv 2302.02639.
  * [21] L. Kuipers and H. Niederreiter: Uniform Distribution of Sequences. John Wiley, New York, 1974.
  * [22] L. Markhasin: $L_{p}$\- and $S_{p,q}^{r}B$-discrepancy of (order $2$) digital nets. Acta Arith. 168: 139–159, 2015.
  * [23] J. Matoušek: Geometric Discrepancy – An Illustrated Guide, Algorithms and Combinatorics, 18, Springer-Verlag, Berlin, 1999.
  * [24] E. Novak: Intractability results for positive quadrature formulas and extremal problems for trigonometric polynomials. J. Complexity 15: 299–316, 1999.
  * [25] E. Novak, I.H. Sloan and H. Woźniakowski: Tractability of tensor product linear operators, J. Complexity 13: 387–418, 1997.
  * [26] E. Novak and H. Woźniakowski: Intractability results for integration and discrepancy. J. Complexity 17(2): 388–441, 2001.
  * [27] E. Novak and H. Woźniakowski: Tractability of Multivariate Problems. Volume I: Linear Information. EMS Tracts in Mathematics 16, Zürich, 2008.
  * [28] E. Novak and H. Woźniakowski: Tractability of Multivariate Problems. Volume II: Standard Information for Functionals. EMS Tracts in Mathematics 12, Zürich, 2010.
  * [29] H. Pasing and C. Weiss: Improving a constant in high-dimensional discrepancy estimates. Publ. Inst. Math. (Beograd) (N.S.) 107(121): 67–74, 2020.
  * [30] F. Pillichshammer: The BMO-discrepancy suffers from the curse of dimensionality. J. Complexity 76, paper ref. 101739, 7 pp., 2023.
  * [31] K.F. Roth: On irregularities of distribution. Mathematika 1: 73–79, 1954.
  * [32] K.F. Roth: On irregularities of distribution. IV. Acta Arith. 37: 67–75, 1980.
  * [33] M.M. Skriganov: Harmonic analysis on totally disconnected groups and irregularities of point distributions. J. Reine Angew. Math. 600: 25–49, 2006.
  * [34] I.H. Sloan and H. Woźniakowski: An intractability result for multiple integration. Math. Comp. 66: 1119–1124, 1997.
  * [35] I.H. Sloan and H. Woźniakowski: When are quasi-Monte Carlo algorithms efficient for high-dimensional integrals? J. Complexity 14: 1–33, 1998.
  * [36] W.M. Schmidt: Irregularities of distribution. X. In: Number Theory and Algebra, pp. 311–329, Academic Press, New York, 1977.
  * [37] J. Vybíral: A variant of Schur’s product theorem and its applications. Adv. Math. 368, paper ref. 107140, 9 pp., 2020.
  * [38] H. Woźniakowski: Efficiency of quasi-Monte Carlo algorithms for high dimensional integrals. In: Monte Carlo and Quasi-Monte Carlo Methods 1998 (H. Niederreiter and J. Spanier, eds.), pp. 114–136, Springer Verlag, Berlin, 2000.

Author’s Address:

Erich Novak, Mathematisches Institut, FSU Jena, Ernst-Abbe-Platz 2, 07740
Jena, Germany. Email<EMAIL_ADDRESS>

Friedrich Pillichshammer, Institut für Finanzmathematik und Angewandte
Zahlentheorie, JKU Linz, Altenbergerstraße 69, A-4040 Linz, Austria. Email:
<EMAIL_ADDRESS>