\end{cases}
\]

Essentially, the proposition claims that the average hole size of random points is on average of optimal order $n^{-1/d}$, whereas the largest hole is logarithmically larger compared to optimal points. Its proof will be discussed in Section <ref>.

Together with Theorem <ref> we obtain the following corollary on the power of random information for $L_q$-approximation and integration in Sobolev spaces.

Let $X_1,X_2,\ldots$ be independent and uniformly distributed on a bounded convex domain $\Omega\subset \mathbb{R}^d$, $1\le p,q \le \infty$ and $s\in\mathbb{N}$ as in (<ref>). Consider the random $n$-point set $\pnran=\{X_1,\ldots,X_n\}$. Then

\[
\IE\, r\big(W_p^s(\Omega)\hookrightarrow L_q(\Omega),\pnran\big)
\,\asymp\, \begin{cases}
r\big(W^s_p(\Omega)\hookrightarrow L_q(\Omega),n/\log n\big) & \text{if } q\ge p,\\
r\big(W^s_p(\Omega)\hookrightarrow L_q(\Omega),n\big) & \text{if } q< p.\vphantom{\Big|}
\end{cases}
\]

Summarizing, we get that, on average, $n$ random points are as asympotically as good as $n/\log n$ optimal ones if $q\ge p$ and asymptotically optimal if $q<p$. This generalizes the one-dimensional result in <cit.> ($s$ has to be replaced by one there) and gives an answer to Question <ref> for the integration and the $L_q$-approximation problem.

Before discussing the extension to other function spaces, let us note a few things.

We stated Corollary <ref> for the expected value of the radius of random information but in fact it also holds with arbitrarily high probability by adjusting the constants and using Markov's inequality giving that, for $q<p$,

\[
\IP\big[r\big(W_p^s(\Omega)\hookrightarrow L_q(\Omega),\pnran\big)> C\,\varepsilon^{-1}\,r\big(W^s_p(\Omega)\hookrightarrow L_q(\Omega),n\big)\big]\le \varepsilon,
\]

where $C>0$ is some constant independent of $n$ and $\varepsilon>0$ can be made arbitrarily small.

Proposition <ref> is a slightly modified version of Proposition 1 in <cit.>. There, we overlooked that estimates on arbitrary large moments are necessary for deducing Corollary <ref>. Thus, the proof of <cit.> is flawed and it is necessary to carry out some minor amendments. The details will be explained at the end of Section <ref>.

Instead of the worst-case error criterion one can consider a randomized error criterion for a general random algorithm, where one first takes the expected error on an individual function and then the supremum over all functions in the unit ball.  Together with Krieg and Novak we studied in <cit.> the power of random information in the randomized setting by adapting the techniques from Section <ref> below. See also the references cited there for further information.

In the remainder of this section we will present generalizations of the above results to other classes of sets $\Omega$ and also to other function spaces on $\Omega$ including Sobolev-Slobodeckij spaces of fractional smoothness, Triebel-Lizorkin spaces, Hölder-Zygmund spaces and Bessel potential spaces.

Let $\Omega\subset\IR^d$ be a bounded convex domain. Several of the function spaces mentioned are part of the scale of Triebel-Lizorkin spaces $F^s_{p\tau}(\Omega)$, where $0<p<\infty$, $0<\tau\le \infty$ and $s>d/p$, which ensures $F^s_{p\tau}(\Omega)\hookrightarrow C_b(\Omega)$. As for $W^s_p(\Omega)$ the condition $s>d/p$ can be weakened for $p\le 1$ but for simplicity we will always assume that $s>d/p$ holds for the $F$-spaces we consider. These are closely related to Besov spaces $B^s_{p\tau}(\Omega)$ for which also $\tau=\infty$ is possible and we provide a more information on both scales in Appendix <ref>. Here, we simply note that $F^s_{p\tau}(\Omega)$ covers a variety of interesting spaces:

* For $\tau=2$ and $1<p<\infty$, we obtain the fractional Sobolev space (or Bessel potential space) $H^s_p(\Omega)$, see e.g.  <cit.>. If additionally $s\in\mathbb{N}$, we arrive at the classical Sobolev spaces $W^s_p(\Omega)$ from Definition <ref>.

* For $s\not\in\IN$, $1\le p<\infty$ and $\tau=p$, we obtain the Sobolev-Slobodeckij space $W^s_p(\Omega)$ of fractional smoothness, see e.g. Dupont and Scott <cit.>, and note that $ F^s_{pp}(\Omega) $ is equal to the Besov space $B^s_{pp}(\Omega)$.

We also want to discuss the Hölder spaces $C^s(\Omega)$, which are not included in this scale.  For $s\in\IN$, the Hölder space $C^s(\Omega)$ is the space of all $s$ times continuously differentiable functions with

\[
\Vert f \Vert_{C^s(\Omega)} := \max_{|\alpha| \le s}\, \sup_{x\in\Omega}\, \vert D^{\alpha}f (x) \vert < \infty,
\]

where $\alpha$ is a multi-index as in Definition <ref>. For $ s\not\in\IN $, the space $C^s(\Omega)$ is defined to be the space of functions $f \in C^{\lfloor s\rfloor}(\Omega)$ with

\begin{equation}\label{eq:semi-norm-hoelder}
:=\max_{|\alpha|=\lfloor s\rfloor}\,\sup_{\substack{x,y\in\Omega\\x\ne y}}\, \frac{|D^{\alpha}f(x)-D^{\alpha}f(y)|}{\|x-y\|^{\{s\}}} < \infty,
\end{equation}

where $ s=\lfloor s\rfloor + \{s\} $ with $ 0< \{s\}<1 $ and $C^{0}(\Omega)=C(\Omega)$.  It is equipped with the norm $\|\cdot\|_{C^{\lfloor s\rfloor}(\Omega)}+|\cdot|_{C^s(\Omega)}$.

Theorem <ref>, Corollary <ref> and Corollary <ref> remain valid for arbitrary real parameters $0<p,q,\tau\le \infty$ and $s\in\IR$ with $s>d/p$ if we replace $W_p^s(\Omega)$ either by $C^s(\Omega)$ for $p=\infty$ or by $F^s_{p\tau}(\Omega)$ for $p<\infty$.

We defer the proof to Appendix <ref>. In particular, Theorem <ref> implies that the fine index $\tau$, measuring smoothness on a finer scale, does not influence the asymptotic quality of point sets.

In order to discuss general domains, we define the function spaces on a general bounded measurable set $\Omega\subset\IR^d$ by restriction of the corresponding function spaces on $\IR^d$. Let

\begin{equation} \label{eq:restriction}
A(\Omega):=\{ f\vert_\Omega \colon f\in A(\IR^d)\},
\qquad \Vert g \Vert_{A(\Omega)} := \inf_{f \in A(\IR^d)\colon f\vert_\Omega=g} \Vert f \Vert_{A(\IR^d)}
\end{equation}

for $A\in \{W_p^s, F^s_{p\tau}, C^s\}$ with parameters as above. If there is a bounded extension operator ${\rm ext}\colon A(\Omega)\to A(\IR^d)$ with $\chg{{\rm ext}(f\vert_\Omega)} = f$ these spaces coincide with the (intrinsically) defined ones above. Here and everywhere else in this thesis, equality between function spaces is meant up to equivalence of norms and the equivalence constants vanish in the asymptotic notation.

It can be deduced from the proofs below that Theorem <ref>, Corollary <ref> and Corollary <ref> and also Theorem <ref> remain valid in the case

* $q\ge p$ if $\Omega$ satisfies an interior cone condition, see Definition <ref> in the following section, and if there is a bounded extension operator. This includes all bounded Lipschitz domains. For more information see Appendix <ref> for Sobolev spaces as well as Appendix <ref> for the other function spaces.

* $q<p$ if $\Omega$ is a bounded convex set with non-empty interior.

In our paper <cit.> Theorem <ref> did not apply to Theorem <ref>b, the equivalence of the integration to the $L_1$-approximation problem. Here, we use a novel approach not published yet in order to remedy this. The idea is to use a different way to construct fooling functions and estimate their norm. We want to thank M. Ullrich for pointing us to the concept of atomic decompositions which we, together with my coauthor D. Krieg, employed to prove this extension. See also the discussion in Section <ref>.

As mentioned, our paper <cit.> relies on the work of <cit.> discussed here. There, we showed an analogon of Theorem <ref> for Bessel potential spaces on the sphere. In particular, the lower bounds in <cit.> (see also Remark 2 there) partially rely on the lower bound discussed in the previous Remark <ref>, which we provide in this thesis.

§ LOCAL MOVING LEAST SQUARES ON GOOD CUBES

In the following, we will discuss the strategy behind the proof of the upper bound of the characterization given in Theorem <ref>a (and its extension, Theorem <ref>). The goal is to find, for each point set $\Pn$ in the domain $\Omega$, a reconstruction map $\varphi$ using information given by the function values at $\Pn$ such that the corresponding algorithm has a worst-case error over the unit ball of the Sobolev space $W^s_p(\Omega)$ which is bounded by a constant times the $L_{\gamma}(\Omega)$-norm of the distance function to $\Pn$.

For finding a suitable algorithm we use the technique of moving least squares which enables to reconstruct polynomials exactly and then use the fact that Sobolev functions can be well approximated by polynomials via Taylor's theorem. Let us give some details.

Building on earlier work, moving least squares approximation was developed by Lancaster and Salkauskas <cit.> in 1981 and in recent decades attracted attention due to the increase in computing power, see Wendland <cit.> for additional references. It is a special case of weighted least squares approximation, a variant of the usual least squares method, working as follows.

Given a point set $\Pn=\{x_1,\dots,x_n\}$ and a function $f$ belonging to a space $F$, one tries to find a function $g_m$ in a fixed $m$-dimensional subspace $X_m$ of $F$ which minimizes the weighted sum of squares

\[
\sum_{i=1}^{n}|f(x_i)-g(x_i)|^2\, w(x,x_i), \quad w\ge 0,
\]

for the point $x$ and then returns $g_m(x)$ as an approximation to $f(x)$. This procedure reproduces elements from $X_m$ exactly provided they are uniquely defined by the function values at $\Pn$. In general, increasing the number of points $n$ allows to increase the dimension $m$ and thus for a better approximation. On a side note, weighted least squares approximation is the backbone of the results in <cit.> described in the introduction to this chapter and effective for recovery, see for example Cohen and Migliorati <cit.>.

In the case of moving least squares on a $d$-dimensional domain, the finite-dimensional space is the space of polynomials

\[
\cP_m^d:=\Big\{\sum_{|\alpha|\le m}c_{\alpha}x^{\alpha}\colon c_{\alpha}\in\IR\text{ for all }\alpha\in \IN_0^d\Big\}
\]

of degree at most $m\in\IN$ in $d$ variables, where $x^{\alpha}=x_1^{\alpha_1}\cdots x_d^{\alpha_d}$ is the monomial associated to the multi-index $\alpha$. Further, the weight function $w$ is a bump function depending on $(x-x_i)/\delta$, where $\delta>0$ is a suitably chosen scaling parameter.  If the point set $\Pn$ is locally dense enough, then polynomials can be reconstructed exactly using moving least squares. This will be made precise by the following lemma which follows directly from results by Wendland <cit.> (see also <cit.> in his book).

To measure the local density of a point set $\Pn\subset \IR^d$ on a set $\Omega\subset\IR^d$, we use the covering radius as given in (<ref>), which measures the radius of the largest hole of the point set $\Pn$ in $\Omega$. In the following, a hole in a point set $\Pn\subset \Omega$ will be a ball contained in $\Omega$ empty of $\Pn$, i.e., not containing a point of $\Pn$.

Let $K \subset\mathbb{R}^d$ be a compact set satisfying an interior cone condition with parameters $r$ and $\theta$, and let $m\in \mathbb{N}$. There are constants $c_0,c_1,c_2>0$ depending solely on $\theta,m$ and $d$ such that for any $\Pn=\{x_1,\dots,x_n\}\subset K$ with covering radius $h_{\Pn,K}\le c_1 r$ there exist continuous functions $u_1,\dots,u_n\colon K\to\mathbb{R}$ with

* $\displaystyle \pi(y)=\sum_{i=1}^n \pi(x_i) u_i(y)$ for all $y\in K$
and $\pi\in \mathcal{P}_m^d $,

* $\displaystyle \sum_{i=1}^n |u_i(y)| \le c_0$ for all $y\in  K$ and

* $u_i(y)=0$ for all $i\le n$ and $y\in K$ with $\Vert x_i-y \Vert \ge c_2 h_{\Pn, K}$.

Before we elaborate on the interior cone condition, let us give some background on how this lemma follows from <cit.>. There, it is required that the point set $\Pn$ (or rather an underlying sequence of $n$-point sets) is quasi-uniform, that is there exists a constant $c_{\rm qu}>0$ with

\begin{equation} \label{eq:quasi-uniform}
\le q_{\Pn}
\le c_{qu} h_{\Pn,K},
\end{equation}

where $q_{\Pn}:=\frac{1}{2}\min_{i\neq j}\|x_i-x_j\|_2$ is the separation distance of $\Pn=\{x_1,\dots,x_n\}$. In Appendix <ref> we will deduce Lemma <ref> by throwing away points too close to others in order to arrive at a quasi-uniform point set without affecting the local density by much.

We say that a set $\Omega\subset \mathbb{R}^d$ satisfies an interior cone condition with radius $r>0$ and angle $\theta\in (0,\pi/2)$ if, for all $x\in \Omega$, there is a direction $\xi(x)\in \mathbb{S}^{d-1}$ such that the cone

\[
C(x,\xi(x),r,\theta):=\left\{x+\lambda y\colon y\in \mathbb S^{d-1}, \langle y, \xi(x)\rangle \geq \cos\theta,\lambda\in [0,r]\right\}
\]

with apex $x$ is contained in $\Omega$. See Figure <ref> for an illustration.

[path fading=fade right,line cap=round,line join=round,x=1cm,y=1cm, scale=1]
at (4,1) $\Omega$;
[shift=(4.98,1.85),color=lgrey,fill=lgrey,fill opacity=0.10000000149011612] (0,0) – (-80:0.8888888888888862) arc (-80:-35:0.8888888888888862) – cycle;
[thick] (0,-1.5) –(1.06,0.59);
[thick] (0,-1.5) – (2.5,-1.7);
[thick]  (1.06,0.59)– (2.52,1.85);
[thick]  (2.52,1.85)– (5.5,2.9);
[thick]  (8,2)– (5.5,2.9);
[thick] (8,2)–(9,1);
[thick]  (2.5,-1.7)– (6.8,-1.39);
[thick]  (9,1)– (6.8,-1.39);

(4.98,1.85)– (7.437456132866975,0.12927069094686194);
(4.98,1.85)– (7.437456132866975,0.12927069094686194) node [midway,yshift=7pt,sloped]$r$;
(4.98,1.85)– (5.500944533000792,-1.1044232590366234);
[shift=(4.98,1.85)]  plot[domain=4.886921905584122:5.672320068981571,variable=](1*3*cos(r)+0*3*sin(r),0*3*cos(r)+1*3*sin(r));
[->,thick] (4.98,1.85) – (5.724243218734402,0.6817721536851105) node [very near end,xshift=14pt,yshift=-4pt]$\xi(x)$;
(4.98,1.85) circle (.04) node [yshift=7pt] at (4.98,1.85) $x$;
[xshift=15pt,yshift=-16pt] at (4.98,1.85) $\theta$;
(5.724243218734402,0.6817721536851105)– (6.591898825040471,-0.6801743374386566);
[shift=(0.88,-0.81),color=lgrey,fill=lgrey,fill opacity=0.10000000149011612] (0,0) – (0:0.8888888888888862) arc (0:45:0.8888888888888862) – cycle;
(0.88,-0.81)– (3.88,-0.81);
[shift=(0.88,-0.81)]  plot[domain=0:0.7853981633974483,variable=](1*3*cos(r)+0*3*sin(r),0*3*cos(r)+1*3*sin(r));
(0.88,-0.81)– (3.0013203435596427,1.3113203435596423);
(0.88,-0.81)– (3.0013203435596427,1.3113203435596423) node [midway,yshift=7pt,sloped]$r$;
[->,thick] (0.88,-0.81) – (2.2670836530974685,-0.2354511387410111) node [very near end,xshift=3pt,yshift=-8pt]$\xi(x)$;
(0.88,-0.81) circle (.04) node [yshift=-7pt] at (0.88,-0.81) $x$;
[xshift=16pt,yshift=11pt] at (0.88,-0.81) $\theta$;
(2.267,-0.235)– (3.6516385975338603,0.33805029709526946);

For each $x\in\Omega$ the cone $C(x,\xi(x),r,\theta)$ may point in a different direction but is of the same shape.

The interior cone condition above is related to similar regularity conditions, in part proposed to characterize the class of domains for which certain (Sobolev) function space embedding and extension theorems hold, see for example the books by Adams and Fournier <cit.> and Grisvard <cit.>. Let us mention here that bounded convex domains satisfy an interior cone condition as above. The following lemma is a consequence of <cit.>.

Any bounded convex set $\Omega\subset \IR^d$ containing a closed ball of radius $r$ satisfies an interior cone condition with radius $r$ and angle $\theta=2\arcsin\bigl(r/2\,\diam(\Omega)\bigr)$.

Here and in the following, balls and cubes are always assumed full-dimensional. For applying Lemma <ref> to a non-compact set, and in particular a bounded convex domain, we shall need the following lemma, proven in Appendix <ref>.

If a set $\Omega\subset\IR^d$ satisfies an interior cone condition, then its closure $\overline{\Omega}$ satisfies an interior cone condition with the same parameters $r$ and $\theta$.

Let us continue by explaining the ideas behind the proof of the upper bound of Theorem <ref>a. The strategy is different depending on whether $q\ge p$, where we basically extend the proof of <cit.> to point sets with non-optimal covering radius and employ Lemma <ref> on $\overline{\Omega}$, or $q<p$, where it will be applied to small parts of the domain, which themselves satisfy an interior cone condition. This case distinction is also reflected by the structure of Appendix <ref>, where Sections <ref> and <ref> contain the proofs needed for the case $q\ge p$ and $q<p$, respectively. The proof for the already known case $q\ge p$ is meant as a preparation for the novel approach developed in <cit.> for the case $q<p$ on the basis of the mentioned works <cit.>. In the following, we will explain the ideas behind starting with a brief description of the simpler case.

In the case $q\ge p$, we apply Lemma <ref> to the closure of the bounded convex domain $\Omega$, which satisfies an interior cone condition by Lemma <ref> and Lemma <ref>. To bound the approximation error of the resulting algorithm $f\mapsto \sum_{i=1}^{n}f(x_i)u_i$, we cover $\Omega$ by parts of diameter $h_{\Pn,\Omega}$ and use error estimates on the local approximation of Sobolev functions by polynomials. For more details see Section <ref>.

In the case $p>q$, we cannot achieve the desired bound by applying Lemma <ref> to the whole domain. Instead, we have to suitably cover it by pieces adapted to the point set $\Pn$ which satisfy an interior cone condition in such a way such that the constants involved in the error bounds do not depend on the point set. Our approach requires that the radius of the interior cone condition satisfied by any piece of the cover should be proportional to the diameter of the piece. This is where the convexity of the domain comes into play.  If the cover is constructed with cubes as it is the case in our work <cit.>, the following lemma supplies the required interior cone condition. To dispose of the convexity assumption, a different approach seems to be required as Figure <ref> shows, see Question <ref> below.

Let $\Omega\subset\mathbb{R}^d$ be a bounded convex set containing a closed ball of radius $r>0$. Then there exist constants $c_{\theta}>0$ and $\theta'\in (0,\pi/2)$ depending on $\Omega$ and $r$ such that closure of the intersection of $\Omega$ with any cube $Q(x, \varrho )$ of radius $0< \varrho \le r$ centered at some $x\in \Omega$  satisfies an interior cone condition with radius $c_\theta  \varrho $ and angle $\theta'$.

Note that the exact choice of $r>0$ does not matter as this lemma is applied to very small cubes if the points become more and more dense. We use the notation

\begin{equation} \label{eq:cubes-balls}
Q(x,\varrho):=\{y\in\IR^d\colon\|x-y\|_{\infty}<\varrho\}\quad \text{and}\quad B(x,\varrho):=\{y\in\IR^d\colon\|x-y\|_2<\varrho\}
\end{equation}

for an open cube or ball centered at $x\in\IR^d$ and of radius $\varrho>0$.

[thick] (0,0) rectangle (4,3);
[white,very thick] (1.5,0) – (2.5,0);
[white] (1.5,0) – (2.5,0)–(2,2)–(1.5,0);
[thick] (1.5,0)–(2,2);
[thick] (2.5,0)–(2,2);
(1.0,0.9) rectangle (2.1,2);
(1.55,1.45) circle (.02) node[xshift=4pt,yshift=-4pt] $x$;
at (3.0,2.1) $\Omega$;

The depicted bounded domain $\Omega$ is not convex and its intersection with the small cube has two connected components. By translating the cube to the left, one of the components becomes arbitrarily small and therefore cannot contain a single cone which has radius proportional to the cube. This can happen for an arbitrarily small cube and shows that Lemma <ref> does not apply to $\Omega$. This remains unchanged by suitably rounding the corners of $\Omega$ such that its boundary is smooth.

One reason why we choose cubes in order to construct the covering is that they form a family which is invariant under translations and rescalings. This is needed to ensure the independence of the constants in the Sobolev embedding theorem, which is used for the estimates on the local error of polynomial approximation by Sobolev functions, see Lemma <ref>. However, other set systems such as balls may work as well, see Remark <ref> below.

Combined with Lemma <ref>, the local cone condition from Lemma <ref> yields the following local approximation result, which will be applied for each cube in a suitable cover of the domain.

Let $\Omega\subset\IR^d$ be a bounded convex set containing a ball of radius $r>0$, $1\le p\le\infty$ and $s\in\IN$ as in (<ref>). There are constants $\cgood \in(0,1)$ and $C>0$, such that for any cube $Q(x,\varrho)\subset\IR^d$ of radius $0< \varrho \le  r $ centered at $x\in\Omega$ and any point set $\Pn=\{x_1,\dots,x_n\}\subset \Omega$ with

\begin{equation}\label{eq:good-cube}
\sup_{y\in \Omega\cap Q(x,\varrho)} \dist(y,\Pn) \le \cgood\, \varrho ,
\end{equation}

there are bounded continuous functions $u_1,\dots,u_n\colon \Omega\cap Q(x,\varrho)\to \IR$ such that for any $f\in W^s_{p}(\IR^d)$, we have

\[
\sup_{y\in \Omega\cap Q(x,\varrho)} \Big\vert f(y) - \sum_{i=1}^n f(x_i) u_i(y) \Big\vert
\le C\,  \varrho ^{s-d/p}|f|_{W^s_{p}(Q(x,\varrho))}.
\]

The local upper bound provided by this lemma is in terms of a Sobolev seminorm $|\cdot|_{W^s_p(Q(x,\varrho))}$ which is essentially the sum in the definition of the norm (Definition <ref>) restricted to $|\alpha|=s$, see also (<ref>).

Lemma <ref> applies if condition (<ref>) is satisfied, that is, if the covering radius $h_{\Pn,\Omega\cap Q(x,\varrho)}$ with respect to the point set $\Pn$ and the domain $\Omega\cap Q(x,\varrho)$ is small compared to the radius $\varrho$ of the cube. This motivates the following definition.

We say that $Q(x,\varrho)$ with $x\in\Omega$ and $0<\varrho\le r$ is a good cube if it satisfies condition (<ref>).

The smaller the radius of a good cube, the better the bound provided by Lemma <ref> if $s-d/p>0$. Therefore, we would like to work for every $x\in\Omega$ with a good cube $Q_{\Pn}(x)$ of smallest radius possible as given by the following definition for which we provide some justification below.

Define for each $\Pn\subset\Omega$ and $x\in\Omega$ the radius $r_{\Pn}(x)$ as the infimum over all $ \varrho \in(0, r )$ such that $Q=Q(x,\varrho)$ satisfies (<ref>) and let $Q_{\Pn}(x):=Q\big(x,r_{\Pn}(x)\big)$.

The radius $r_{\Pn}(x)$ is well-defined since we may assume that, without loss of generality, for any $\Pn\subset \Omega$ and $x\in \Omega$ there is some $ \varrho \in(0, r )$ such that (<ref>) holds for the cube $Q(x,\varrho)$. Otherwise, we have $\|\dist(\cdot,\Pn)\|_{L_{\gamma}(\Omega)}\ge c$ for some $c>0$, see Lemma <ref> in Appendix <ref>. Then the upper bound of Theorem <ref>a would become trivial.

The infimum in Definition <ref> is in fact attained, see Lemma <ref> in Appendix <ref>. Consequently, also $r_{\Pn}(x)$ satisfies (<ref>) and $Q_{\Pn}(x)$ is a good cube, the smallest of all good cubes centered at $x$. Note that we could also have chosen $r_{\Pn}(x)$ to be the minimizer up to a constant factor and the proof still works.

Subsequently, we consider only the collection $\{Q_{\Pn}(x)\colon x\in\Omega\}$ of good cubes of minimal radius and we will cover the domain by a suitable finite subset of them. The following proposition yields a suitable cover. It follows from a Besicovitch-type covering theorem for cubes as presented by de Guzman <cit.>.

Let $\Omega\subset\IR^d$ be bounded. There exist $M_1,M_2\in\mathbb{N}$ depending only on $d$ such that for any point set $\Pn\subset\Omega$ there are centers $y_1,\ldots, y_N\in \Omega$ such that the cubes $Q_i:=Q_{\Pn}(y_i)$, where $i=1,\dots,N$,

* form a cover, i.e., $\Omega\subset \bigcup_{i=1}^N Q_i$,

* can be distributed in at most $M_1$ families, i.e., $\{Q_1,\ldots,Q_N\}=\bigcup_{j=1}^{M_1}\cQ_j,$ with each family $\cQ_j$ consisting of pairwise disjoint cubes,

* cover efficiently, i.e., no point of $\IR^d$ is contained in more than $M_2$ of them.

To complete the proof of the upper bound of Theorem <ref>, apply Lemma <ref> to each of the cubes $Q_i$ given by Proposition <ref> to get, for every $i=1,\ldots,N$, a linear algorithm $S_{\Pn,i}\colon W^s_p(\Omega\cap Q_i)\to L_q(\Omega\cap Q_i)$. Then select for each point $x\in\Omega$ a cube $Q_i$ containing $x$ and let $S_{\Pn}(f)(x):=S_{\Pn,i}(f)(x)$. In this way, we form a global linear sampling algorithm $f\mapsto S_{\Pn}(f)=\varphi\big(f(x_1),\ldots,f(x_n)\big)\in L_{q}(\Omega)$, defined on $\Omega$. In fact, since the components $S_{\Pn,i}(f)$ are bounded, the algorithm returns a bounded function. It remains to combine the estimates given by Lemma <ref> with Hölder's inequality and the efficiency of the covering. A detailed proof will be provided in Appendix <ref>. We have not used the second property of the covering in Proposition <ref>; it will be needed for the lower bound described in the next section.

Note that Proposition <ref> also works if the cubes are replaced by the familiy of all translations and rescalings of a fixed bounded set satisfying an interior cone condition, see <cit.> where this is attributed to A. P. Morse. It should be possible to replace everywhere in our proofs the cubes by such a family.

Concerning Proposition <ref>, we proved in <cit.> the existence of a similar cover directly, see Lemma 11 and 12 as well as Proposition 2 there. During a seminar talk on our work by David Krieg in Linz, Simon Hackl suggested that the required cover may be obtained using <cit.>. Together with D. Krieg, we succeeded in thus simplifying the proof in this way and the author wants to thank S. Hackl. This is one reason why the proof of the upper bound in the case $q<p$, which is given here, is slightly different from the one given in <cit.>.

§ FOOLING FUNCTIONS AND THE INTEGRATION PROBLEM

We come now to the lower bound of Theorem <ref>a which relies on the well-known technique of fooling functions and also discuss the related equivalence between $L_1$-approximation and integration stated in Theorem <ref>b, and its extension Theorem <ref>.

Given a sampling set $\Pn$, a fooling function forces any algorithm using information provided by $\Pn$ to produce a large worst-case error. Exhibiting such a function is a popular approach to lower bounds for sampling algorithms. To elaborate a bit, let $\Omega$ be some domain and $f_\ast\in W^s_p(\Omega)$ with norm at most one and $f_\ast(x_i)=0$ for all $i=1,\ldots,n$. Then an algorithm of the form $S_{\Pn}\colon f\mapsto \varphi\big(f(x_1),\ldots,f(x_n)\big)$ cannot distinguish $f_\ast$ from $-f_\ast$, i.e., it satisfies $S_{\Pn}(f_*)=S_{\Pn}(-f_*)$. Therefore, the radius of information satisfies

\begin{align*}
r\big(W_p^s(\Omega)\hookrightarrow L_q(\Omega),\Pn\big) &\,=\, \inf_{S_{\Pn}} \sup_{\|f\|_{W^s_p(\Omega)}\le 1} \Vert S_{\Pn}(f) - f \Vert_{L_q(\Omega)}\\
&\ge\, \inf_{u\in L_q(\Omega)}\, \max\left\{ \Vert u - f_* \Vert_{L_q(\Omega)}, \Vert u + f_* \Vert_{L_q(\Omega)} \right\}\\
&\ge\, \|f_\ast\|_{L_q(\Omega)}.
\end{align*}

This reproves the lower bound in relation (<ref>). Any $f_{\ast}$ with sufficiently large $\|f_{\ast}\|_{L_q(\Omega)}$ can be a fooling function. In particular, it is meaningful to rescale such that $\|f_{\ast}\|_{W^s_p(\Omega)}=1$. We describe how to construct such a function.

In the case $q\ge p$ it is enough to consider a smooth non-negative function $f_\ast$ which is supported in a large hole with radius close to $h_{\Pn,\Omega}$. Scaling properties of the Sobolev and the $L_q$-norm can then be used to obtain the required estimates.

Again, the case $q<p$ demands a different approach. There, we have to take multiple disjoint holes in which the fooling function is supported. Intuitively, this is because we are interested in an average error. This distinction is well-known in the literature, see, e.g., the proofs of the lower bounds in <cit.> and in <cit.>. To obtain the disjoint holes we will use the cover of Proposition <ref> and select a family of disjoint cubes as in Definition <ref> with a large sum of radii. The following lemma then provides a suitable hole of proportional size in every such cube and makes clear why we did choose good cubes of small radius.

There exists a constant $\chole\in (0,\infty)$ such that for every point set $\Pn\subset \Omega$ and any $x\in\Omega$ the intersection $\Omega\cap Q_{\Pn}(x)$, contains a ball of radius $\chole\, r_{\Pn}(x)$.

To obtain the required estimates in the case $q<p$, we need some control over the Sobolev norm of a sum of functions with disjoint supports. Implicitly we used a property of Sobolev spaces, see for example <cit.>, which states that the Sobolev norm of a sum of a linear combination of functions $f_1,\ldots,f_M$ with pairwise disjoint support, which are obtained by scaling and translating a fixed function, can be described using an $\ell_p$-norm of the coefficients. This property is shared by other function spaces to a certain extent as discussed below.

Before this, we comment on the proof of Theorem <ref>b which states that for the Sobolev spaces $W^s_p(\Omega)$ the radius of information for the integration problem is asymptotically equivalent to the one for the $L_1$-approximation problem.

In order to obtain a suitable sampling algorithm to approximate the integral, we use the fact that if we have an algorithm $S_{\Pn}$ of the form $S_{\Pn}\colon f\mapsto \varphi\big(f(x_1),\ldots,f(x_n)\big)$ for the problem of $L_1$-approximation, then $S_{\Pn}(f)\in L_1(\Omega)$ and

\[
\Big|\int_{\Omega} f(x)- \int_{\Omega} S_{\Pn}(f)(x)\dd x\Big|
\le \|f-S_{\Pn}(f)\|_{L_1(\Omega)}.
\]

Regarding the lower bound, the above approach using fooling functions also applies to the integration problem if $f_\ast\ge 0$ since then $\|f_\ast\|_{L_1(\Omega)}={\rm INT}(f_\ast)$. Thus, Theorem <ref>b is proven if we can find non-negative fooling functions.

Indeed, we shall use non-negative fooling functions in the proofs in Appendix <ref> below. In Section <ref> there, we employ techniques which will also be suitable for the extension to other function spaces mentioned in Theorem <ref>. In our original work <cit.> we extended the lower bound for the $L_q$-approximation problem to Triebel-Lizorkin spaces, which do not behave as well as Sobolev spaces with respect to sums of functions of disjoint supports of different sizes, by using a wavelet characterization pointed out to us by W. Sickel.

However, the generalization of Theorem <ref>b dealing with the integration problem did not succeed using the wavelets as these have to satisfy moment conditions which require them to have an integral of zero. Using atomic decompositions instead gives non-negative fooling functions and thus proves also the extension of Theorem <ref>b to the Triebel-Lizorkin spaces, see also Remark <ref> above. This will be done in the Appendix, Section <ref>.

At this point, we want to say a few more words on the proof of the generalization to other spaces, that is the proof of Theorem <ref>. As a crucial ingredient, we need a bound on polynomial approximation in terms of a seminorm that scales well. The work <cit.> contains the required tools, even for spaces on the more general bounded Lipschitz domains defined below. Further, our method requires that the seminorms on the cubes can be glued together in a suitable manner. In this regard, our attempt at an extension of Theorem <ref> to Besov spaces failed. We believe that this is solely a shortcoming of our technique and that Theorem <ref> holds also for Besov spaces, see also Question <ref>. For a definition of Triebel-Lizorkin and Besov spaces and details of the proof see Appendix <ref>.

§ OPTIMAL QUANTIZERS AND THE DISTORTION OF RANDOM POINTS

In the following, we shall prove Proposition <ref> on the expected average hole size of random points, which together with Theorem <ref>, leads to the main result of Corollary <ref>.

At the heart of the study of the radius of information of an arbitrary, and thus in particular also a typical or random, point set $\Pn=\{x_1,\ldots,x_n\}$ for the problems considered in this chapter lies the quantity

\begin{equation} \label{eq:distortion}
\|\dist(\cdot,\Pn)\|_{L_{\gamma}(\IR^d,\mu)}^{\gamma}
=\int_{\IR^d}\dist(x,\Pn)^{\gamma}\dd \mu(x),
\end{equation}

where $0<\gamma<\infty$ and $\mu$ is a Borel measure on $\IR^d$ which we assume to be absolutely continuous with respect to the Lebesgue measure. In the context of quantization theory, which originated from signal processing, the number $D_{\mu,\Pn,\gamma}$ is also called the distortion, see the monograph <cit.> by Graf and Luschgy for more information on this subject. Before, we considered only the Lebesgue measure restricted to a domain $\Omega$ but in the following we shall provide some background from a more general perspective.

Roughly speaking, quantization means replacing a continuous object by a discrete one. In quantization theory one seeks to replace a random vector $X$ in $\IR^d$ with law $\mu$ by a quantized version which assumes only finitely many values. For this, one uses a Borel measurable map $T\colon\IR^d\to\IR^d$ with an image of cardinality $\#T(\IR^d)=n\in\IN$ and forms the random variable $T(X)$. Such a map is called an $n$-quantizer. To measure how well the quantized version $T(X)$ represents $X$ itself, one considers the quantization error $ \IE \|X-T(X)\|_2^r $, where $1\le r <\infty$ is such that $\IE \|X\|_2^r<\infty$.

If the image of an $n$-quantizer is some $n$-point set $\Pn\subset \IR^d$, then the optimal quantizer $T_{\Pn}$ maps a realization of $X$ to the closest point of $\Pn$. This means that it is of the form

\begin{equation} \label{eq:opt-quant}
\end{equation}

C(x_i,\Pn):=\{x\in\IR^d\colon \|x-x_i\|_2=\dist(x,\Pn)\}
are the Voronoi cells with respect to $\Pn$. By deciding ties arbitrarily, the collection $\{C(x_i,\Pn)\colon i=1,\ldots,n\}$ becomes a disjoint partition of $\IR^d$. A moment of thought reveals that the quantization error of $T_{\Pn}$ is exactly the distortion, i.e.,

\begin{equation} \label{eq:dist-quant}
\IE\|X-T_{\Pn}(X)\|_2^r
= D_{\mu,\Pn,r}.
\end{equation}

In quantization theory, one is often interested in the minimal quantization error over all $n$-quantizers, or equivalently in the infimum of the distortion over all $n$-point sets $\Pn$. In (<ref>) we gave rough asymptotics for this quantity but in fact exact asymptotics are available. Also for random quantizers precise limit theorems have been obtained, for example, by Cohort <cit.> and Yukich <cit.> who build on work of Zador <cit.>. We deduce from <cit.> the following statement on random distortion.

Let $0<\gamma<\infty$ and $X_1,X_2,\ldots$ be independent and uniformly distributed on a bounded measurable set $\Omega\subset \mathbb{R}^d$ satisfying an interior cone condition. Consider the random $n$-point set $\pnran=\{X_1,\ldots, X_n\}$. Then, for every $p=2,3,\ldots$,

\[
n^{\gamma/d}\frac{1}{\vol(\Omega)}\int_{\Omega}\dist(x,\pnran)^{\gamma}{\rm d}x
\,\xrightarrow[n\to\infty]{L_p}\,
\left(\frac{\vol(\Omega)}{\vol\bigl(\IB_2^d\bigr)}\right)^{\gamma/d}\Gamma\Bigl(1+\frac{\gamma}{d}\Bigr).
\]

In order to deduce this from <cit.>, it remains to observe that the interior cone condition satisfied by $\Omega$ yields a constant $c_{\Omega}>0$ such that for every $x\in\Omega$ and every $0<\varrho\le 1+\sup_{x\in\Omega}\|x\|_2$ we have $\vol\bigl(\Omega\cap B(x,\varrho)\bigr)\ge c_{\Omega} \vol\bigl(B(x,\varrho)\bigr)$.

We are now ready to give the proof of Proposition <ref>. If $0<\gamma<\infty$, the lower bound is clear from the behaviour of optimal points as mentioned in (<ref>). For the upper bound, an application of Jensen's inequality shows that for $p= p(\alpha,\gamma)\in \IN$ chosen large enough such that $p\ge \alpha/\gamma$ we have

\[
\Big(\IE \,n^{\alpha/d} \|\dist(\cdot,P)\|_{L_{\gamma}}^{\alpha}\Big)^{\gamma/\alpha}
\le
\Big(\IE \Big[n^{\gamma/d} \int_{\Omega}\dist(x,P)^{\gamma}\dd x \Big]^{p}\Big)^{1/p}.
\]

By Lemma <ref> the bounded convex domain $\Omega$ satisfies the assumptions of Proposition <ref>, and thus the right-hand side converges to some finite limit. This concludes the proof of Proposition <ref> for this choice of $\gamma$.

The case $\gamma=\infty$ follows from asymptotics for the size of the largest hole in a random point set which were given by  Reznikov and Saff <cit.>. More precisely, we obtain the statement of Proposition <ref> in this case from Corollary 2.3 there applied to $\Phi(r)=r^d$ together with the fact that convex domains satisfy an interior cone condition.

The form of the limit theorem in Proposition <ref> is different from the one used in <cit.>. There, we relied on <cit.> which gives an almost sure convergence together with convergence in $L_2$ but we neglected that convergence of arbitrary high moments is necessary. The above proof remedies this.

Actually, we used only a special instance of Cohort's result which is valid for different measures $\mu$, too. Further, the arguments behind the proof of Proposition <ref> transfer also to points sampled from other measures which are absolutely continuous with respect to the Lebesgue measure and have a density bounded from below. One probably needs to employ different methods and arrives at qualitatively distinct results if more general measures are considered.

Proposition <ref> also holds in more general spaces. For example, a simplified proof working on general Riemannian manifolds was presented by us in <cit.> and shows that one may easily obtain convergence in $L_p$ for $0<p<\infty$ using Jensen's inequality.

One can also show Corollary <ref> without Theorem <ref> or Proposition <ref> by using techniques similar in spirit to <cit.>.

Regarding the asymptotic constant in Proposition <ref>, note that the quantity $\bigl(\vol(\Omega)/\vol\bigl(\IB_2^d\bigr)\bigr)^{1/d}$ is related to the concept of volume ratio, which plays an important role in Banach space geometry, see, e.g.,  Szarek and Tomczak-Jaegermann <cit.>. Further, as $\gamma\to\infty$ the factor $\bigl(\Gamma(1+\frac{\gamma}{d})\bigr)^{1/\gamma}$ tends to infinity, which corresponds to the fact that the covering radius of $\pnran$ is typically of larger order than $n^{-1/d}$.

On smoothly bounded domains or polytopes, exact asymptotics are also available for the covering radius of i.i.d. uniform random points. In <cit.> a proof may be found for the case of three-dimensional polytopes but in fact it generalizes to arbitrary dimension. Even more precise results such as a limiting Gumbel law, an important extreme value distribution showing up as the limit distribution of rescaled maxima, were derived by Penrose <cit.>. Further, the covering radius of a random point set is connected to the coupon collector's problem, which asks for the number of coupons (points) that a collector has to draw in order to obtain a complete collection (hit every set in a diameter-bounded equal volume partition of $\Omega$).

§ OPEN QUESTIONS

When discussing the moving least squares method, we started with general subspaces which we then replaced by the space of polynomials. It would be interesting to consider other subspaces and develop a more general formulation of our results.

Can  Theorem <ref> be generalized to other function spaces?

It seems worthwhile to pass from moving least squares to general weighted least squares in order to extend our results to other function spaces where smoothness is not determined via polynomials. In particular, it could be of interest to study the integration problem in Hilbert spaces of functions on which function evaluations are continuous. These widely used spaces are called reproducing kernel Hilbert spaces and the corresponding kernel allows for an analysis of sampling methods, see for example the book <cit.> by Berlinet and Thomas-Agnan or <cit.>.

As mentioned in Section <ref>, we could not extend our results to Besov spaces.
The following question is left open maybe due to our own incompetence or due to the lack of a suitable seminorm.

Does Theorem <ref> also hold for Besov spaces $B^s_{p\tau}$?

Similar to the proof of Theorem 23 in <cit.> one may use interpolation arguments to prove an upper bound, but in this way an additional $\varepsilon>0$ appears in the exponent of the $L_{\gamma}$-norm in the case $q<p$. Therefore, new ideas seem to be required.

As explained in Section <ref>, convexity is central to our proof technique and therefore new ideas seem necessary to answer the following question.

Can Theorem <ref> be extended to general bounded Lipschitz domains?

A possible approach could consist in using a different cover adapted to the boundary of the domain, as well as to the point set used. However, caution is required to ensure independence of the constants from the point set.

We did not track the hidden constants in Theorem <ref> (and the derived results). As the dependence of the involved constants on the dimension is important for tractability considerations, the following question comes to mind.

What is the dependence of the constants in Theorem <ref> on the dimension?

We think that our proof technique leaves an exponentially growing gap with regard to this question. It appears easier to determine for fixed dimension the asymptotic constants in front of the expected radius of random information if $n$ tends to infinity. For example, one could use a more elaborate fooling function such as a smoothed version of the distance function, as suggested to us by M. Ullrich, and employ the full strength of the limiting behaviour of random distortion given by Proposition <ref>. Such questions are of interest also for the minimal radius and optimal points, see, e.g., Novak <cit.>.

One drawback of the linear algorithm attaining the upper bound in the integration problem is that we do not know the weights it uses.

Can the weights of a suitable linear algorithm achieving the asymptotic upper bound in Theorem <ref>b be expressed geometrically?

It is clear that the weights of any linear algorithm (of the form  (<ref>)) achieving the asymptotic upper bound have to depend on the point set. In the upcoming Chapter <ref> we will see that these weights can be given explicitly for Hölder spaces with small smoothness and this choice may be optimal for higher smoothness too.

CHAPTER: INTERLUDE - OPTIMAL TRANSPORT AND CUBATURE RULES

This chapter connects the integration problem to the concept of discrepancy, which is related to equal-weight integration, and thus links Chapter <ref> with the upcoming Chapter <ref>. The focus will be on the weights used by (near-)optimal cubature rules for Hölder and Lipschitz functions. For these weights a geometric expression as volumes of Voronoi cells is shown, and further that equal weights can be optimal in high dimensions for uniform random points. Along the way, we pile dirt onto heaps and use classical results from probability to study Monte Carlo.

The main results of Chapter <ref> show that we can assess the quality of any point set $\Pn$ for several approximation and integration problems in terms of the distortion, an average over the distance function to $\Pn$ defined in (<ref>). Much alike, both the distortion and the discrepancy, which will be introduced in Chapter <ref>, measure the distance between a measure $\mu$ and a point set $\Pn$, which can be represented by a sum of Dirac measures. Distances between measures have been studied in the field of optimal transport, which gave rise to the concept of the Wasserstein (or Kantorovich) distance, a well known way to metrize the space of measures. We refer to the book of Villani <cit.> for a comprehensive account and limit ourselves to a brief introduction in the following.

To transport the unit mass from a Borel probability measure $\mu$ on $\IR^d$ to another, say $\nu$, one can use a transference plan or coupling $\pi$ which is a probability measure on $\IR^d\times \IR^d$ with marginals $\mu$ and $\nu$. We collect all such transference plans between $\mu$ and $\nu$ into a set denoted by $\Pi(\mu,\nu)$. Optimal transport concerns itself with finding a transference plan with minimal transportation cost, that is, attaining the infimum in

\[
\mathcal{T}_r(\mu,\nu)
:=\inf_{\pi\in \Pi(\mu,\nu)}\int_{\IR^d\times \IR^d} \|x-y\|_2^r \dd\pi(x,y),
\]

where we took the Euclidean distance raised to some power $0<r<\infty$ as a cost function.  By setting $W_r=\mathcal{T}_r^{1/r}$ for $ 1\le r<\infty$ and $W_r=\mathcal{T}_r$ for $0<r<1,$ one can define a metric on the space of probability measures with finite $r$-th moments, the Wasserstein (or Kantorovich) distance, see <cit.>. The case $r=1$ is especially interesting as we will see in a moment.

To prepare for the connection between Wasserstein distance and the integration problem, assume from now on that $\mu$ is absolutely continuous with respect to the Lebesgue measure and that $\nu$ is supported on a point set $\Pn=\{x_1,\ldots,x_n\}\subset \IR^d$, i.e., of the form

\begin{equation} \label{eq:discrete}
\nu_{\Pn,a}
\text{where }a=(a_1,\dots,a_n)\in\IR^n
\text{ with }\sum_{i=1}^{n}a_i=1,
\end{equation}

where for any $x\in\IR^d$ the Dirac measure of any $A\subset \IR^d$ equals one if $x\in A$ and zero else.

The optimal transportation cost between $\mu$ and $\nu_{\Pn,a}$ as above attains a minimal value which is equal to the distortion, that is, for any $0<r<\infty$,

\begin{equation} \label{eq:transport}
\inf_{a\in\IR^n} \mathcal{T}_r(\mu,\nu_{\Pn,a})
= \int_{\IR^d} \min_{i=1,\dots,n} \|x-x_i\|_2^r \dd\mu(x)
\quad(=D_{\mu,\Pn,r})
\end{equation}

and the infimum over the weights is in fact attained at

\begin{equation} \label{eq:voronoi}
\mu\big(C(x_1,\Pn)\big),\dots,\mu\big(C(x_n,\Pn)\big)
\end{equation}

where $C(x_i,\Pn)$ is the Voronoi cell of $x_i$ as in (<ref>). A proof can be deduced from <cit.> and will be provided for completeness in Appendix <ref>. The idea behind is to consider the coupling induced by the map $(x,y)\mapsto \big(x,T_{\Pn}(x)\big)$, where $T_{\Pn}$ is the quantizer from (<ref>) in Section <ref> mapping $x$ to the nearest point of $\Pn$.

Let us recall the integration problem on $\IR^d$. Suppose we are given a normed space of functions $F$ on $\IR^d$ such that the embedding $F\hookrightarrow C_b(\IR^d)$ holds, see Section <ref>. The goal is to find $\varphi\colon \IR^n\to \IR$ such that, for every $f\in F$, $A(f)=\varphi\big(f(x_1),\ldots,f(x_n)\big)$ approximates the integral ${\rm INT}_{\mu}(f)=\int_{\IR^d}f(x)\dd\mu(x)$ with respect to the absolutely continuous probability measure $\mu$ on $\IR^d$. Here, assuming absolute continuity ensures that the problem is not too easy.

As mentioned in the introduction to Chapter <ref> the optimal $\varphi$ can be chosen linear, that is, the optimal sampling operator is of the form

\begin{equation}\label{eq:cubature}
Q_{\Pn,a}\colon F\to \IR,\quad f\mapsto\sum_{i=1}^{n}a_i f(x_i)=\int_{\IR^d}f(x)\dd\nu_{\Pn,a}(x),
\end{equation}

with $\nu_{\Pn,a}$ as in (<ref>). This is a cubature rule with points $\Pn=\{x_1,\ldots,x_n\}$ and weights $a=(a_1,\ldots,a_n)\in \IR^n$. Note that we mean in fact $\Pn=(x_1,\ldots,x_n)$ to be able to associate the weights to the points but out of habit use the set notation which should not cause confusion. Then the worst-case error over the unit ball $F_0$ of $F$ is

\[
e(F,\intmu, Q_{\Pn,a})
=\sup_{f\in F_0}\Big|\int_{\IR^d} f(x) \dd \mu(x)-\int_{\IR^d} f(x) \dd \nu_{\Pn,a}(x)\Big|,
\]

and can be seen as a distance between the measures $\mu$ and $\nu_{\Pn,a}$. If we consider the special case $F=\lip$, the space of Lipschitz functions $f\colon \IR^d\to\IR$, equipped with the seminorm

\[
:=\sup_{\substack{x,y\in\IR^d\\x\neq y}}\frac{|f(x)-f(y)|}{\|x-y\|_2},
\]

then the Kantorovich-Rubinstein duality theorem (<cit.>) yields that, for any $\nu_{\Pn,a}$ as in (<ref>),

\begin{equation} \label{eq:lip-wce}
\sup_{|f|_{\lip}\le 1} \Big|\int f(x)\dd\mu(x) - \int_{\IR^d} f(x) \dd \nu_{\Pn,a}(x)\Big|
\end{equation}

This means that the worst-case error over Lipschitz functions with seminorm at most one can be expressed as the $W_1$-distance between the measure $\mu$ according to which we want to integrate and the discrete measure $\nu_{\Pn,a}$ representing the algorithm $Q_{\Pn,a}$.

It seems worth noting that the metric $W_1$ is also called the earth mover's distance for the following reason. If one imagines the density of $\mu$ to be a distribution of dirt, which one wishes to collect into heaps of size $a_i$ located at points $x_i$, and the work needed for transporting dirt is proportional to the distance it is moved, then the least amount of work is exactly the right-hand side of (<ref>).

Optimal weights. By means of the expression of the minimal distance $W_1=\mathcal{T}_1$ in (<ref>) one can deduce that the normalized weights minimizing the worst-case error over the unit ball of the seminormed space $\lip$ are given as in (<ref>) by the $\mu$-content of the Voronoi cells. This also holds more generally as we now explain.

Equality (<ref>) extends to the Hölder classes $C^{s}(\IR^d),0<s<1$, with seminorm $|\cdot|_{C^{s}(\IR^d)}$ defined in (<ref>). It can be deduced for example from the more general Theorem 5 in Gruber <cit.> that

\begin{equation} \label{eq:hoelder-wce}
\inf_{a_1,\ldots,a_n\in\IR}\sup_{|f|_{C^{s}(\IR^d)}\le 1} \Big|\int f(x)\dd\mu(x) - \sum_{i=1}^{n}a_i f(x_i)\Big|
\end{equation}

where the optimal weights are again as in (<ref>). This holds true for $s=1$ if $C^s(\IR^d)$ is replaced by $\lip$. For convenience we provide a proof in Appendix <ref>.

Strictly speaking, since we take the supremum over a set of seminorm at most one and not over the unit ball of a normed space, we are not in the setting considered before. However, the space $C^s(\IR^d)$ can be equipped by the norm $\|\cdot\|_{\infty}+|\cdot|_{C^s(\IR^d)}$, see the line below (<ref>), and one can proceed analogously for $\lip$. As the seminorm is bounded by the norm thus defined, one can get an upper bound for the radius of information of $\Pn$ for integration in these spaces.

More can be said if $\mu$ has bounded support $D\subset \IR^d$. Then the space of Lipschitz functions $f\colon D\to \IR$ will be denoted by $\lipd$ and becomes a normed space when equipped with the norm $\|\cdot\|_{\lipd}$ which is the restriction of $\|\cdot\|_{\lip}$. For $\lipd$ and the Hölder spaces $C^s(D)$ defined in Section <ref> we have the following known result.

Let $s\in (0,1)$ and $\mu$ be a probability measure supported on a bounded set $D\subset \IR^d$. Then, for any point set $\Pn=\{x_1,\ldots,x_n\}\subset D$,

\[
\inf_{a_1,\ldots,a_n\in \IR}\sup_{\|f\|_{C^s(D)}\le 1} \Big|\int_{\IR^d} f(x)\dd\mu(x) - \sum_{i=1}^{n}a_i f(x_i)\Big|
\asymp D_{\mu,\Pn,s},
\]

where the implicit constants depend only on $D$ and the weights given in (<ref>) attain the bound. The statement remains true for $s=1$ if $C^s(D)$ is replaced by $\lipd$.

Since linear algorithms are optimal for this integration problem this proposition implies that the radius of information given by the point set $\Pn$ satisfies

\[
\asymp D_{\mu,\Pn,s},
\]

which extends Theorem <ref> for these spaces. An analogous result holds for $\lipd$.

Proposition <ref> provides us with (near-)optimal weights and the cubature rule

\begin{equation} \label{eq:opt-cubature}
\end{equation}

which is asymptotically optimal in the sense of

\[
\chg{ e(C^s(D),\intmu,Q_{\Pn,\mu})
\le C\, r\big(C^s(D),\intmu,\Pn\big), }
\]

where the constant $C$ is independent of $\Pn$.

In general, it is a question of interest to compute (near-)optimal weights for general point sets and in most cases they are unknown. It would be interesting to have an analogon of Proposition <ref> for other classes such as Sobolev spaces, see also Question <ref> and  Remark <ref> below.

Before we turn to the case of equal weights, we show that, under minor assumptions, normalized weights cannot be much worse than general real weights. Since we were not able to locate a proof of this known fact, we provide one in Appendix <ref>.

Let $\mu$ be a probability measure supported on a set $D\subset \IR^d$ and let $F$ be a normed space of functions with $F\hookrightarrow C_b(D)$. Suppose that the constant function $\bfone_D$ belongs to $F$ (and thus all constant functions). If $Q_{\Pn,a}$ is a cubature rule as in (<ref>), then the normalized weights $a_i^*=a_i/\sum_{i=1}^{n}a_i, i=1,\ldots,n,$ satisfy

\[
\sup_{\|f\|_F\le 1} \Big|\intmu(f)-\sum_{i=1}^{n}a_i^* f(x_i)\Big|
\le (1+C\|\bfone_D\|_F) \sup_{\|f\|_F\le 1} \Big|\intmu(f)-\sum_{i=1}^{n}a_i f(x_i)\Big|.
\]

The assumptions on the function space $F$ are satisfied for all function spaces considered until now if the set $D$ is bounded. This provides some justification for studying equal weights $a_1=\cdots=a_n=1/n$.

In the case of reproducing kernel Hilbert spaces, one can compute optimal weights explicitly by solving a linear system, see, e.g., <cit.>. For example, this can be done for the Sobolev spaces $W^s_2(\Omega)$, where a kernel can be derived from  Novak, M. Ullrich, Woźniakowski and Zhang <cit.>, see also Section 2.3 in <cit.>. However, there does not seem to be a convenient geometric expression of near-optimal weights.

In the following, we will discuss equal-weight rules in Hölder spaces and discover that these are in fact asymptotically optimal, provided the dimension is large enough. This motivates the study of discrepancy in the upcoming Chapter <ref>.

Equal weights.
Define, for $\Pn=\{x_1,\ldots,x_n\}\subset \IR^d$, the equal-weight cubature rule

\begin{equation} \label{eq:qmc}
\end{equation}

Thus we allow only the reconstruction map $\varphi\colon \IR^n\to\IR$ with $\varphi(y)=\frac{1}{n}\sum_{i=1}^{n}y_i$ and we may interpret the worst-case error of $Q_{\Pn}$, which is

\[
= \sup_{f\in F_0}\Big| \frac{1}{n}\sum_{i=1}^{n}f(x_i)-\int_{\IR^d} f(x)\dd\mu(x)\Big|,
\]

as a measure of the quality of information given by sampling at $\Pn$.

At first sight, it seems that by restricting to equal weights much flexibility is lost and only special kinds of point sets may yield good equal-weight rules. This is true, for example, if one requires exact integration on subspaces as in the case of spherical designs, surveyed e.g. by Brauchart and Grabner in <cit.>.

However, if we are interested in asymptotically optimal equal-weight rules with an error allowed to exceed the minimal error

\[
\chg{r(F,\intmu,n)}
=\inf_{\#\Pn= n}r(F,\intmu,\Pn)
\]

by a proportional amount, then in some cases typical information is asymptotically optimal. As in Section <ref>, we use for each $n\in\IN$ the random point set $\pnran:=\{X_1,\ldots,X_n\}$ with random points $X_1,\ldots,X_n$ drawn independently and uniformly according to the probability measure $\mu$ on $\IR^d$.

Given random information, the corresponding random equal-weight rule associating to each $f$ the random number $\frac{1}{n}\sum_{i=1}^{n}f(X_i)$ is the prototypical example of a Monte Carlo method, whereas the algorithm in (<ref>) using the deterministic points above is often called a quasi-Monte Carlo method.
Monte Carlo methods are very popular among practioners in fields such as physics or mathematical finance where high-dimensional integrals have to be evaluated and common cubature rules based on polynomial interpolation become computationally expensive or numerically unstable. In a moment, we shall give some intuition why it is so effective in these situations. We refer to <cit.> (see also the survey <cit.>) for further information.

The law of large numbers states that, almost surely,

\[
\frac{1}{n}\sum_{i=1}^{n}f(X_i)\to \IE f(X_1)=\int_{\IR^d}f(x)\dd\mu(x) \quad \text{as }n\to\infty
\]

provided that $f(X_1)$ is integrable. Further, the central limit theorem implies that the fluctuations around this limit are asymptotically of order $n^{-1/2}$, that is, we have the convergence in distribution

\[
\sqrt{n}\,\Big(\frac{1}{n}\sum_{i=1}^{n}f(X_i) - \int_{\IR^d}f(x)\dd\mu(x) \Big)
\to \mathcal{N}\big(0,{\rm Var}_{\mu}(f)\big)\quad \text{as }n\to\infty,
\]

to a centered Gaussian with variance ${\rm Var}_{\mu}(f)=\IE f(X_1)^2 -\big(\IE f(X_1)\big)^2$ provided that $f(X_1)$ is square-integrable.

Thus we make an error on individual functions which is of the dimension- but also smoothness-independent rate $n^{-1/2}$. For obtaining a bound on the worst-case error over a function class, one can employ empirical process theory or entropy estimates, see, e.g., van der Vaart and Wellner <cit.>. However, this necessarily increases the error, if only by a factor.

In high dimensions the rate $n^{-1/2}$ can be optimal for functions of low effective smoothness $s/d$. For example, it follows from Theorem <ref> and (<ref>) (see also Proposition <ref> for $s\in(0,1)$) that for the Hölder spaces $C^{s}(D)$, where $D\subset \IR^d$ is a bounded convex set and $s>0$, the $n$-th minimal radius of information satisfies

\[
r\big(C^s(D),{\rm INT},n\big)\asymp n^{-s/d},
\]

where integration is with respect to the Lebesgue measure. In fact, using the Monte Carlo method above one can achieve this optimal rate if $s/d<1/2$ at least on the unit cube as the following discussion shows.

Among others, Kloeckner <cit.> studied the related topic of (Wasserstein) distances between a measure $\mu$ and its empirical measure $\mu_n:=\frac{1}{n}\sum_{i=1}^{n}\delta_{X_i}$ which corresponds to the Monte Carlo method. Theorem 1.4 in <cit.> shows that, see also related work by Fournier and Guillin <cit.> and van der Vaart and Wellner <cit.>, for any $s\ge 1$ and any probability measure $\mu$ on $[0,1]^d$,

\[
\IE \sup_{\|f\|_{C^{s}([0,1]^d)}\le 1}\Big|\frac{1}{n}\sum_{i=1}^{n}f(X_i)-\int_{[0,1]^d} f(x)\dd\mu(x)\Big|
\lesssim
\begin{cases}
n^{-s/d},& \text{if }s<d/2,\\
n^{-1/2}\log n,& \text{if }s=d/2,\\
n^{-1/2},& \text{if }s>d/2.\\
\end{cases}
\]

Note that here for $s\in\IN$, in contrast to our definition, the space $C^s$ consists of functions whose derivatives of order $s-1$ are Lipschitz continuous and is normed slightly differently.  This means that in the low smoothness regime $s/d<1/2$ the Monte Carlo method achieves on average the optimal rate $n^{-s/d}$. At the threshold $s/d=1/2$ an additional logarithm comes into play and for higher smoothness we arrive at the standard Monte Carlo rate of $n^{-1/2}$ which cannot be improved in general.

The special case of Lipschitz functions ($s=1$) leads to the case distinction into $d\ge 3$, where we have the optimal rate, $d=2$, where we loose a logarithm, and $d=1$, where we have the rate $n^{-1/2}$. Since Lipschitz functions are related to Wasserstein distance $W_1$, this case received particular attention, see, e.g., Weed and Bach <cit.> for some references on recent progress.

It is no coincidence that also in the related field of optimal matching, where one tries to find a bijection between two random point sets minimizing a sum of distances, the two-dimensional case is especially interesting, see for example <cit.>. There, the author calls the worst-case error of such a Monte Carlo method a discrepancy as it measures the distance between the uniform measure and its associated empirical measure. This is related to but different from the discrepancy we will study in the following Chapter <ref>.

It is a curious phenomenon that we have a threshold as above. According to Bobkov and Ledoux <cit.>, who investigated optimal matchings in one dimension, this is connected to the fact that periodic functions of smoothness $s>1/2$ can be expanded into absolutely convergent Fourier series, which is no longer true for $s=1/2$.

CHAPTER: ISOTROPIC DISCREPANCY OF LATTICE POINT SETS

In this final chapter we will consider the isotropic discrepancy, a quantity related to the radius of information for certain integration problems, where we restrict to equal-weight cubature algorithms using information either at specific point sets or random ones. As motivated in Chapter <ref>, the findings here complement the study of the radius of (random) standard information in Chapter <ref>. More precisely, we study the isotropic discrepancy of a special type of structured point sets, called lattice point sets, and show that in dimension $d \ge 2$ they do not attain the optimal behaviour exhibited by random constructions.

After a rather general introduction, we present in Section <ref> the results obtained together with F. Pillichshammer in the publications <cit.> and <cit.>. The subsequent Sections <ref> and <ref> contain the ideas behind the proofs and Section <ref> ends this chapter with open questions and opportunities for subsequent work.

§ INTRODUCTION AND MOTIVATION

We feel that the motivation for the study of istropic discrepancy, which is a special kind of discrepancy related to convex sets, benefits from a more general perspective. Thus, consider a measure space $(D,\Sigma,\mu)$ with $\mu(D)=1$ and a set system $\cA\subset\Sigma$ containing $D$ as well as the empty set. Then, for any point set $\Pn=\{x_1,\ldots,x_n\}\subset D$, the corresponding equal-weight algorithm $Q_{\Pn}\colon f\mapsto \frac{1}{n}\sum_{i=1}^{n}f(x_i)$ as in (<ref>) incurs an error on the indicator function $\bfone_A\colon D\to\IR$ which can be bounded via

\begin{equation} \label{eq:disc-ineq}
\Big|\frac{1}{n}\sum_{i=1}^{n}\bfone_A(x_i)-\int_D \bfone_A(x)\dd\mu(x)\Big|
\le D_{\cA}(\Pn),\quad A\in\cA,
\end{equation}

\begin{equation} \label{eq:disc-def}
:=\sup_{A\in\cA} \Big|\frac{\#(A\cap \Pn)}{n} - \mu(A)\Big|
\end{equation}

is the discrepancy of the point set $\Pn$ with respect to the system $\cA$ (and the measure $\mu$ which is omitted in the notation).

Analytically, the discrepancy $D_{\cA}(\Pn)$ quantifies the uniform error made by the algorithm $Q_{\Pn}$ on the set of characteristic functions belonging to $\cA$, and geometrically it compares the maximal deviation between the fraction of points of $\Pn$ belonging to such a set and its $\mu$-volume. There is a whole theory related to this notion of irregularity of distribution, see, e.g., the books by Beck and Chen <cit.>, Drmota and Tichy <cit.>, and Kuipers and Niederreiter <cit.>.

In the following, we would like to construct a space of functions built from indicator functions such that the discrepancy $D_{\cA}(\Pn)$ is equal to the quality of $Q_{\Pn}$ for this space. For this purpose, we follow Pausinger and Svane <cit.> and start with the class of simple functions

\begin{equation} \label{eq:simple}
\Sigma(\cA)
:=\Big\{\sum_{j=1}^{m}a_j \bfone_{A_j}\colon m\in\IN \text{ and }a_j\in \IR, A_j\in \cA \text{ for all }j=1,\ldots,m,\Big\}.
\end{equation}

The complexity of a simple function $f\in\Sigma(\cA)$ is captured by the sum of its coefficients, minimized over all representations, i.e.,

\[
:=\inf\Big\{\sum_{j=1}^{m}|a_j|\colon f=a_0\bfone_{D}+\sum_{j=1}^{m}a_j \bfone_{A_j} \text{ with }m, a_j \text{ and } A_j \text{ as in \eqref{eq:simple}}\Big\}
\]

which is called the $\cA$-variation of $f$.  Note that the constant part does not contribute.

By direct calculation, we can extend (<ref>) to simple functions and obtain

\begin{equation} \label{eq:kh}
\Big| \frac{1}{n}\sum_{i=1}^{n}f(x_i)-\int_D f(x)\dd\mu(x)\Big|
\le D_{\cA}(\Pn) V_{\cA}(f),\quad f\in\Sigma(\cA).
\end{equation}

It is important to note that this bound decomposes into a part depending only on the point set and another depending only on the function. For this reason one may call (<ref>) a Koksma-Hlawka inequality in the spirit of a theorem of the same name, for which we refer to e.g. <cit.>.

To extend (<ref>) further, we use uniform limits of simple functions to find a suitable function space containing $\Sigma(\cA)$. Let $f\colon D\to\IR$ be a measurable function such that there exists a sequence of simple functions $(f_n)_{n\in\IN}\subset \Sigma(\cA)$ converging uniformly to $f$. Then define the $\cA$-variation of $f$ by

\[
:=\inf\big\{\liminf_{n\to\infty} V_{\cA}(f_n)\colon f_n\in\Sigma(\cA), f_n\to f\text{ uniformly}\big\}.
\]

If we denote by $V(\cA)$ the space of all functions with finite $\cA$-variation, then it defines a seminorm on it which is zero for the constant functions.  We obtain

\begin{equation} \label{eq:disc-wce}
\sup_{V_{\cA}(f)\le 1}
\Big| \frac{1}{n}\sum_{i=1}^{n}f(x_i)-\int_D f(x)\dd\mu(x)\Big|
\end{equation}

where the upper bound follows from (<ref>) and for the lower bound a sequence $(A_n)_{n\in\IN}\subset \cA$ with $V_{\cA}(\bfone_{A_n})\to D_{\cA}(\Pn)$ works.

The identity (<ref>) states that the worst-case error of any equal-weight algorithm based on a point set over the functions with $\cA$-variation at most one is equal to the discrepancy with respect to $\cA$. This should be compared with (<ref>) relating the worst-case error of a cubature rule on functions with $|f|_{\lip}\le 1$ with the Wasserstein distance. Admittedly, the set $\{f\in V(\cA)\colon V_{\cA}(f)\le 1\}$ may seem less intuitive, as it is constructed by completing simple functions in the uniform norm. Thus, we will be more concrete and specialize to the case which interests us in this chapter.

Let now $D=[0,1)^d$ be equipped with the Lebesgue measure $\vol$ and consider the set system $\cA=\cK$, the class of convex sets contained in $[0,1)^d$. Then we call

\begin{equation} \label{eq:iso-def}
:= \sup_{K\in\cK} \Big|\frac{\#(K\cap \Pn)}{n} - \vol(K)\Big|
\end{equation}

the isotropic discrepancy of the point set $\Pn=\{x_1,\ldots,x_n\}$. It is also denoted by $J_n(\Pn)$ instead, which is the notation used in <cit.>. Its definition dates back to Hlawka <cit.> and its name was coined by Zaremba <cit.> who apparently based it on the isotropy, that is the rotation invariance, of the family of convex sets. This is in contrast to the family $\mathcal{A}$ of boxes with sides parallel to the coordinate axes used for estimating integration errors in anisotropic function spaces of dominating mixed smoothness.

The relation (<ref>) expresses the isotropic discrepancy as a worst-case error of the corresponding equal-weight or quasi-Monte Carlo rule. In this sense, it measures the quality of the information given by a point set for a specific integration problem. It can be deduced from <cit.> that the twice continuously differentiable functions $C^2( (0,1)^d)$ are continuously embedded into the space $V_{\cK}$ if it is equipped with the norm $\|\cdot\|_{\infty}+V_{\cK}(\cdot)$. Additionally, the class $\cK$ encompasses many other set systems used for studying worst-case errors, as for example $\mathcal{A}$ which is related to Hardy-Krause variation and worst-case errors in spaces of mixed smoothness. Therefore, it bounds the integration error of equal-weight rules in related function spaces.

Concerning further applications, Aistleitner, Brauchart and Dick <cit.> used an area-preserving map $\Phi\colon [0,1)^2\to \IS^2$ to relate the isotropic discrepancy to the spherical cap discrepancy, where we equip $\IS^2$ with its normalized rotation invariant measure $\sigma^{(2)}$ and consider the system $\cC$ of all spherical caps

\[
{\rm Cap}(x,t)
:= \{y\in \mathbb{S}^{2}\colon \langle x, y\rangle \ge t\},\quad x\in\mathbb{S}^{2}, t\in [-1,1],
\]

that is, intersections of the sphere with half-spaces. Through elaborate computations, they proved in <cit.> an upper bound for the spherical cap discrepancy of the mapped point set in terms of the isotropic discrepancy of the original point set $\Pn\subset [0,1)^2$, which is of the form

\begin{equation} \label{eq:iso-sphere}
\le 11\, D_{\cK}(\Pn).
\end{equation}

This was then applied to Fibonacci lattice points and certain digital nets, which are both classes of point sets with low discrepancy with respect to $\mathcal{A}$. Discussing their results, they stated on p. 1001 in <cit.>:

“Whether $(0,m,2)$-nets and/or Fibonacci lattices achieve the optimal rate of convergence for the isotropic discrepancy is an open question.”

This served as our original motivation to study the isotropic discrepancy of more general lattice point sets as introduced below. In the above question, the optimal rate is meant to be the rate of decay of the minimal isotropic discrepancy given by

\begin{equation} \label{eq:iso-min}
:=\inf_{\#\Pn= n}D_{\cK}(\Pn),
\end{equation}

where the infimum is over all point sets $\Pn\subset [0,1)^d$ with $n$ points. In <cit.> Schmidt proved the lower bound

\begin{equation} \label{eq:iso-lower}
\gtrsim n^{-2/(d+1)}
\end{equation}

using a now famous technique. This bound is attained up to a power of a logarithm as shown by Stute <cit.> for $d\ge 3$ and Beck <cit.> for $d=2$. The proofs rely on the probabilistic method and thus one does not know of an explicit point set achieving this upper bound. Interestingly enough, the proof of Stute shows that i.i.d. random points with density absolutely continuous to the Lebesgue measure satisfy this bound and are thus optimal up to a logarithmic factor. Note that this cannot hold for $d=2$ as the central limit theorem yields a rate of at best $n^{-1/2}$, see Chapter <ref>.

We investigate the isotropic discrepancy of lattice-point sets, defined as follows.

Let $d\in\IN, d\ge 2,$ and let

\[
L=\Big\{\sum_{i=1}^{d}k_i b_i\colon k_i\in\ZZ\text{ for }i=1,\dots,d\Big\}
\]

be a $d$-dimensional lattice spanned by linearly independent basis vectors $b_1,\ldots,b_d\in \IR^d$. If the lattice $L$ contains $\ZZ^d$, it is called an integration lattice and generates the lattice point set $\cP(L):=L\cap [0,1)^d$.

The Fibonacci lattice point set is a special case which can be generated by a single vector and thus is of rank one, see, e.g., <cit.>. To define it, let $F_1=F_2=1$ and $F_{m}=F_{m-1}+F_{m-2}$ for $m> 2$ be the Fibonacci numbers. Then the Fibonacci lattice point set with $F_n$ points is given by

\[
\mathcal{F}_n
=\Big\{\Big(\frac{i}{F_n},\Big\{\frac{iF_{n-1}}{F_n}\Big\}\Big),\quad i=0,\dots,F_{n}-1\Big\},
\]

where $\{\cdot\}\in [0,1)$ is the fractional part. For an illustration of $\mathcal{F}_8$ with $F_8=21$ points see Figure <ref> in Section <ref> below.

Lattice point sets are used in numerical integration for constructing good equal weight rules, see, e.g., <cit.> as well as Sloan and Joe <cit.>. In particular, the Fibonacci lattice point set achieves the best order for discrepancy with respect to $\mathcal{A}$. It also has optimal dispersion, which measures the size of the largest empty axis-parallel box in the cube, see Breneis and Hinrichs <cit.> as well as Lachmann and Wiart <cit.>. Let us mention that also for the dispersion uniform random points are the best point sets known in certain (high) dimensions, see, e.g., Litvak and Livshyts <cit.>.

However, the results presented in the next section will show that the special structure of lattice point sets compared to random points is a disadvantage with respect to isotropic discrepancy.

The Voronoi cells of a lattice point set are of equal volume, at least when it is considered on the torus $\TT^d\simeq [0,1)^d$. Therefore, equal weights are optimal for the integration of (periodic) Hölder and Lipschitz functions as Proposition <ref> shows. This justifies considering only equal weights for the integration of functions from $V_{\cK}$ when using lattice point sets.

§ DISCUSSION OF RESULTS

Among the results we present here are a lower bound on the isotropic discrepancy of lattice point sets (Theorem <ref>), a characterization of their isotropic discrepancy in terms of the spectral test of the underlying lattice (Theorem <ref>) and an equivalence for the radius of information of lattice point sets for $L_q$-approximation, $1\le q\le\infty$, in the Sobolev spaces $W^s_p([0,1)^d)$ (Theorem <ref>).

In <cit.> we derived a lower bound on the isotropic discrepancy of lattice-point sets. We present a corrected version as follows, see Remark <ref>.

Let $\cP(L)$ be an $n$-element lattice point set in $[0,1)^d$. Then

\[
D_{\cK}\big( \cP(L)\big)
\ge \min\Big\{\frac{1}{2\sqrt{d}+1},\frac{c_d}{n^{1/d}}\Big\},
\]

\[
c_d:=\frac{\sqrt{\pi}}{2\sqrt{d}+1} \left(\Gamma\left(\frac{d}{2}+1\right)\right)^{-1/d}.
\]

If additionally $\sigma(L)\leq 1/2$, then $c_d$ may be replaced by $c_d'=c \left(\Gamma\left(\frac{d}{2}+1\right)\right)^{-1/d}$ for some $c>0$ that is independent of $d$.

Stirling's formula for the Gamma function $\Gamma(x)=\int_0^{\infty}t^{x-1}{\rm e}^{-t}\dd t, x>0$, see (<ref>), implies

\[
c_d^{-1}\sqrt{\frac{\pi\,{\rm e}}{2}}\frac{1}{d}\to 1 \quad \text{as }d\to\infty.
\]

Theorem <ref> shows that the isotropic discrepancy of lattice point sets decays slower than the minimal isotropic discrepancy (<ref>) and answers the question from <cit.> mentioned near the end of the introduction to this chapter in the negative. Therefore, the upper bound of <cit.> on the spherical discrepancy of mapped Fibonacci lattice points, which is of order $n^{-1/2}$ cannot be improved. We remark that Larcher <cit.> has shown the lower bound of order $n^{-1/d}$ already for the class of lattice point sets of rank one by using a different approach than ours. In dimension $d\ge 3$, the lower bound of Theorem <ref> implies together with the discussion on the minimal isotropic discrepancy that random information prevails over information given by lattice point sets.

We obtained the lower bound in Theorem <ref> using a characterization of the isotropic discrepancy of $\cP(L)$ in terms of the spectral test $\sigma(L)$ of the lattice given as follows.

The spectral test of a $d$-dimensional lattice $L$ is given by

\[
\sigma(L):=\frac{1}{\min\big\{\|h\|_2\colon h \in L^{\bot}\setminus\{0\}\big\}},
\]

where the dual lattice is given by

\[
L^{\bot}:=\left\{h \in \IR^d\colon \langle h, x \rangle \in \ZZ \text{ for all } x \in L\right\}.
\]

We present the corrected version of Theorem 2 in <cit.>, see again Remark <ref>.

Let $\cP(L)$ be an $n$-element lattice point set in $[0,1)^d$. Then

\[
\frac{\sigma(L)}{\sqrt{d}+\sigma(L)}
\le D_{\cK}\big(\mathcal{P}(L)\big)
\leq d \, 2^{2(d+1)} \sigma(L).
\]

If $\sigma(L)\le 1/2$, then the lower bound can be replaced by $c\,\sigma(L)$,  where $c>0$ does not depend on the dimension $d$.

To give some background, let us mention that the spectral test originated as a means to evaluate the randomness of linear congruential pseudorandom number generators, see Knuth <cit.> and <cit.>. It is a well known numerical quantity to assess the coarseness of (integration) lattices and admits a convenient geometric interpretation which is developed in Section <ref>, see also <cit.>.

Consider $n=m^d$ for some $m\in\IN$. Then the lattice point set generated by the scaled integer lattice $(1/m)\ZZ^d$ contains $n$ points. Its dual is given by $m\ZZ^d$ and thus $\sigma\big( (1/m)\ZZ^d\big)=\|(m,0,\dots)\|_2=n^{-1/d}$. Its isotropic discrepancy appears to be unknown.

Let $n=m^{d-1}$ for some $m\in\IN$. Then the lattice point set generated by $L=\ZZ\times(1/m)\ZZ^{d-1}$ has $n$ points and is contained in the hyperplane $\{0\}\times\IR^{d-1}$. Its dual is $L^{\bot}=\ZZ\times m\ZZ^{d-1}$ and $\sigma(L)=\|(1,0,\dots,0)\|_2=1$. Its isotropic discrepancy is one.

If $\sigma(L)>1/2$, then the lattice point set $\cP(L)$ is concentrated on a few hyperplanes, whereas the case $\sigma(L)\le 1/2$ corresponds to a more evenly distributed $\cP(L)$.  We have the following lower bound on the spectral test of an $n$-element lattice point set, which together with Theorem <ref> implies Theorem <ref>.

Let $\cP(L)$ be an $n$-element lattice point set in $[0,1)^d$. Then

\[
\sigma(L) \ge \frac{\sqrt{\pi}}{2} \left(\Gamma\left(\frac{d}{2}+1\right)\right)^{-1/d} \frac{1}{n^{1/d}}.
\]

We did not find a proof of this result in the literature and thus provide a proof in Section <ref> using Minkowski's theorem which is commonly used for bounding the length of the shortest vector in a lattice.

In Proposition <ref> the rate $n^{-1/d}$ can be achieved by rank-one lattices when $n$ is prime, see Dick, Larcher, Pillichshammer and Woźniakowski <cit.> who bound a figure of merit equivalent, up to constants in $d$, to the inverse of the spectral test.

Theorem <ref> and Theorem <ref> are the corrected versions of <cit.> respectively. The upper bound in the latter has been already repaired by <cit.>; details are discussed in Remark <ref> in Section <ref>. Recently, we discovered also an error in the lower bound of <cit.> which affects also <cit.> without the restriction of $\sigma(L)\le 1/2$, see Remark <ref> in Section <ref>.

The characterization in Theorem <ref> is true for more general point sets of the form $(L+a)\cap [0,1)^d$ for some $a\in\IR^d$ which contain $n$ points, but one has to adjust the constants. This follows from the fact that by volume comparison the volume of the fundamental domain is roughly the inverse of the number of points.

Since, in dimension two, the minimal spherical cap discrepancy and isotropic discrepancy are of order $n^{-3/4}$ and $n^{-2/3}$ up to logarithmic factors, respectively, the bound of <cit.> stated in (<ref>) cannot be used to prove that the mapped Fibonacci lattice point set has optimal spherical discrepancy as the numerics suggest. However, it may be used to improve on the current rate of $n^{-1/2}$ for the best known deterministic constructions, see also Etayo <cit.> for such a sequence of point sets apart from the mapped Fibonacci lattice point set. Note that the upper bound on the minimal spherical cap discrepancy was obtained by Beck using the Probabilistic method, more precisely, jittered sampling, see, e.g., <cit.>. See also the author's master thesis <cit.> for more information on spherical discrepancy.

The following application of Theorem <ref> characterizes the radius of information given by a lattice point set with respect to the problems of approximation and integration of Sobolev functions on the cube.

Let $1\le p,q\le \infty$ and $s\in\IN$ as in (<ref>). For every lattice point set $\mathcal{P}(L)$ in $[0,1)^d$ it holds that

\[
r\big(W^{s}_p([0,1)^{d})\hookrightarrow L_q([0,1)^d),\mathcal{P}(L)\big)\,
\asymp \,\sigma(L)^{s-d(1/p-1/q)_+}.
\]

Here, the asymptotic notation conceals constants independent of the integration lattice $L$.

Note that the Sobolev space $W^s_p\big([0,1)^d\big)$ is defined via restriction, see (<ref>), and an analogous result holds for the space defined on $(0,1)^d$. Theorem <ref> is a consequence of Theorem <ref> applied to the Sobolev space $W^s_p([0,1)^d)$ and the following equivalence, which may be interesting on its own.

For every lattice point set $\mathcal{P}(L)$ in $[0,1)^d$ and every $0<\gamma \le \infty$, we have

\[
\sigma(L)
\lesssim_{d,\gamma} \bigl\|\dist\bigl(\cdot,\mathcal{P}(L)\bigr)\bigr\|_{L_{\gamma}([0,1)^d)}
\lesssim_d \sigma(L).
\]

The proof and thus the proof of Theorem <ref> will be given in Appendix <ref>. The distortion of sets arising from lattices has been also studied in the context of lattice quantizers, see, e.g., Conway and Sloane <cit.> as well as <cit.>.

Given a sequence of lattice point sets, we can interpret Theorem <ref> as follows.

A sequence of lattice point sets $\big(\cP(L_k)\big)_{k\in\IN}$ is asymptotically optimal for the $L_q$-approximation of Sobolev functions from $W^s_p([0,1)^d)$ if and only if the spectral test behaves optimally, i.e.,

\[
r\big(W^{s}_p([0,1)^{d})\hookrightarrow L_q([0,1)^d),\mathcal{P}(L_{k})\big)
\asymp r\big(W^{s}_p([0,1)^{d})\hookrightarrow L_q([0,1)^d),n_k\big)
\]

if and only if

\[
\quad\sigma(L_{n_k})\asymp n_k^{-1/d},
\]

where $n_k:=\#\cP(L_k)$.

By Theorem <ref> one can replace the spectral test by isotropic discrepancy in Theorem <ref> and Corollary <ref>. The latter shows that lattice point sets with small spectral test may attain the optimal rates for the integration problem in Sobolev spaces but fail to attain the optimal rate for the isotropic discrepancy. Perhaps, this may be deduced from the function spaces $W^s_p([0,1)^d)$ and $V(\cK)$ themselves.

§ HYPERPLANE COVERINGS AND LOWER BOUNDS

We will give more details on the geometric interpretation of the spectral test $\sigma(L)$ of a $d$-dimensional integration lattice $L\subset \IR^d$ and then use it to obtain lower bounds.

[black] (0,0) rectangle (1,1);
ıin 0,...,20
+(ı/21,ı*13/21-floor(ı*13/21)) circle (1/(50));

(0,0) rectangle (1,1);
ıin 1,...,9
[shorten >=-3cm, shorten <=-3cm,black] (ı*1/65,ı*8/65)–(ı*64/65,0);

[black] (0,0) rectangle (1,1);
ıin 0,...,20
+(ı/21,ı*13/21-floor(ı*13/21)) circle (1/(50));
[->,black,opacity=.8,thick] (4/65+3*8/65,4*8/65-3*1/65)–(3*1/65+3*8/65,3*8/65-3*1/65);

(0,0) rectangle (1,1);
ıin 1,...,5
[shorten >=-3cm, shorten <=-3cm, black] (ı*2/21,ı*5/21)–(ı*5/21,ı*2/21);

[black] (0,0) rectangle (1,1);
ıin 0,...,20
+(ı/21,ı*13/21-floor(ı*13/21)) circle (1/(50));
[->,black, thick,opacity=.8] (3*7/42,3*7/42)–(27.5/42,27.5/42);

[<->, black, opacity=.8,thick] ((18.5/42,9.5/42) –(25.5/42,16.5/42);

[anchor=north, black] at (25/42,14/42) $\sigma(L)$;

(-8.5,-8.5) rectangle (8.5,8.5);

ıin -10,...,10
ȷin -10,...,10
[black!30] (ı,ȷ) circle (.2);

ıin -5,...,5
ȷin -5,...,5
[black] ((ı*2+ȷ*3),(-ı*5+ȷ*3)) circle (0.4);
[white] (0,0) circle (.25);

(-8.5,-8.5) rectangle (8.5,8.5);

ıin -10,...,10
ȷin -10,...,10
[black!30] (ı,ȷ) circle (.2);

ıin -5,...,5
ȷin -5,...,5
[black] ((ı*2+ȷ*3),(-ı*5+ȷ*3)) circle (0.4);
[white] (0,0) circle (.25);

[black!80] (-1,-8) circle (.25);
[->,black!80,opacity=.8, thick] (-0.1,-0.3)–(-0.9,-7.7);

(-8.5,-8.5) rectangle (8.5,8.5);

ıin -10,...,10
ȷin -10,...,10
[black!30] (ı,ȷ) circle (.2);

ıin -5,...,5
ȷin -5,...,5
[black] ((ı*2+ȷ*3),(-ı*5+ȷ*3)) circle (0.4);
[white] (0,0) circle (.25);

[black!70] (3,3) circle (.25);
[->,black,opacity=.8,thick] (0.3,0.3)–(2.7,2.7);

The first row depicts a Fibonacci lattice point set $\cP(L)\subset [0,1)^d$ together with two different hyperplane coverings, whose distance is marked by an arrow. Its length is inverse to the vector in the dual lattice $L^{\bot}$, shown in the second row, which generates the hyperplane covering. The lattice in grey depicts $\ZZ^d\supset L$.

Following the presentation in Hellekalek <cit.>, we call a family $\cH$ of parallel hyperplanes a covering of $L$ if $L\subset \bigcup_{H\in\cH} H$ and every $H\in\cH$ contains some lattice point of $L$. Then the distance between any two adjacent hyperplanes in $\cH$ is equal to some number $d(\cH)\ge 0$. In fact, every primitive vector $x$ in the dual $L^{\bot}$ gives rise to a covering of $L$ by parallel hyperplanes all orthogonal to $x$. The distance between adjacent hyperplanes in this covering is exactly $\|x\|_2^{-1}$. The spectral test is equal to the supremum $\sup_{\cH}d(\cH)$ over all coverings of $L$ by parallel hyperplanes, which is attained by the covering of hyperplanes $\cH^*=\cH^*(L)$ for which all hyperplanes are orthogonal to the shortest vector in the dual lattice $L^{\bot}$. See Figure <ref> for an illustration. Let us note that here a lattice vector is called primitive if it is non-zero and the line connecting it to the origin does not contain another lattice vector.

In the following, we will only consider the covering $\cH^*$ and use it to explain the idea behind the lower bound on the isotropic discrepancy, Theorem <ref>, which follows from the lower bound in Theorem <ref> together with Proposition <ref>. Detailed proofs can be found in Appendix <ref>. The proof of the lower bound of Theorem <ref> is divided into two cases depending on whether we suppose $\sigma(L)\le 1/2$ or not.

In the case without any assumption on $\sigma(L)$ we will find a convex set which has no volume and contains some fraction of the points. This is achieved by intersecting $[0,1)^d$ with a hyperplane $H\in\cH^*$ containing sufficiently many points. The existence of such a hyperplane will be a consequence of the pigeonhole principle and the fact that not too many hyperplanes of $\cH^*$ have a non-empty intersection with the unit cube as they are separated by a distance of at least $\sigma(L)$.

The proof of <cit.> contains a flawed estimate of the number of hyperplanes from $\cH^*$ intersecting $[0,1)^d$. There, the upper bound $\lfloor \sqrt{d}/\sigma(L)\rfloor$ was claimed but there can be in fact as many as $\lceil \sqrt{d}/\sigma(L)\rceil \le \sqrt{d}/\sigma(L)+1$. The correction performed in this thesis gives a slightly worse bound but retains the asymptotic behaviour. Here, for any $a\in\IR$, $\lceil a\rceil$ is the smallest integer not smaller than $a$.

The lower bound with the assumption $\sigma(L)\le 1/2$ relies on a recent result due to König and Rudelson <cit.> who have shown the following.

If an affine subspace has distance less than $1/2$ to the center of the unit cube, then the volume of their intersection is at least a positive constant only depending on the codimension of the subspace.

We apply this to the continuum of parallel hyperplanes between two adjacent hyperplanes from $\cH^*$ whose convex hull contains the center of the cube. In this way, we get a lower bound on the volume of the cube intersected with the interior of this convex hull, which contains no points of $\cP(L)$, and thus also a lower bound on the isotropic discrepancy.

§ SHORT LATTICE VECTORS AND AN UPPER BOUND

For the proof of the upper bound of Theorem <ref> we have to show that for any convex set $K\subset [0,1)^d$ the fraction of points of $\cP(L)$ contained in $K$ is not too far from its volume. For this purpose, we rely on the lattice structure to form a partition into cells of volume $1/n$ containing exactly one point. Then the discrepancy of the set $K$ depends only on cells or points near the boundary of $K$.

That kind of argument appears throughout the discrepancy literature, even though sometimes superficially (especially in high dimensions). In particular, this applies to jittered or stratified sampling where in each cell a point is uniformly distributed and which can be used to derive upper bounds on the discrepancy with respect to various set systems, see, e.g., Chapter 3 in Matoušek's book <cit.> or <cit.>. In equation (3) in the latter, an estimate on the number of intersecting cells was given, however with a hidden constant. Confer also Drmota and Tichy <cit.> for another presentation. In <cit.>, Brandolini, Chen, Colzani, Gigante and Travaglini extend this method to metric measure spaces, a key hypothesis being a bound on the measure of the neighbourhood of the boundary of the involved sets. Similar to Corollary 8.3 there, we shall derive such a bound for convex sets and give an explicit constant (see Corollary <ref>). This discussion motivates a more detailed description of the proof technique of the upper bound of Theorem <ref>; remaining proofs may be found in Appendix <ref>.

Consider a tiling of $\IR^d$ by disjoint translations of the following set.

Let $L$ be a $d$-dimensional lattice with basis $b_1,\dots,b_d$. Then the fundamental domain or cell with respect to this basis is given by

\begin{equation} \label{eq:fundamental}
\fP:=\Big\{\sum_{i=1}^{d}\lambda_i b_i\colon 0\le \lambda_i <1\Big\}.
\end{equation}

Its definition implies that for every $x\in L$ the set $\fP_x:=\fP+x$, which is a shifted fundamental domain, contains no other point of $L$ besides $x$. Also, the sets $\fP_x$ and $\fP_y$ are disjoint for $x\neq y$ both in $L$. We have the disjoint union
\IR^d
=\bigcup_{x\in L}\fP_x

The volume of $\fP$ and thus any such cell is independent of the chosen basis and called the determinant $\det(L)$ of $L$. A peculiar property of $L$ being an integration lattice is that $\det(L)=1/n$, where $n=\#\cP(L)$.

For an arbitrary convex set $K\subset [0,1)^d$, its signed discrepancy

\[
:=\frac{\#(\cP(L)\cap K)}{n} - \vol(K)
\]

can be decomposed into the contributions made by each cell, that is,

\begin{equation} \label{eq:decomposition}
=\frac{1}{n}\sum_{x\in L}\Big(\bfone_K(x) -n \, \vol(K\cap \fP_x)\Big).
\end{equation}

If a cell is completely contained in $K$, then it does not contribute to the sum as it contains exactly one point of $\cP(L)$ and its intersection with $K$ has exactly volume $1/n$. Also a cell not intersecting $K$ does not contribute, since then the corresponding lattice point is not in $K$ and the volume of $K$ intersected with the cell is zero.

In order to estimate the right-hand side of (<ref>), consider the union of cells inside of $K$ and of those intersecting $K$, that is, define

\[
\Uin=\bigcup_{\substack{x\in L:\\ \fP_x\subset K}} \fP_x\quad 	\text{and}\quad
\Uout=\bigcup_{\substack{x\in L:\\ \fP_x\cap K\neq \emptyset}} \fP_x.
\]

Then we have the inclusions $\Uin\subset K \subset \Uout$.

We get a lower bound by ignoring lattice points not belonging to $\Uin$ and thus

\[
\ge \frac{1}{n}\sum_{x\in L\cap \Uin}\big(\bfone_K(x) - n\,\vol(\fP_x)\big)- \vol(K\setminus \Uin)
=\vol(K\setminus \Uin).
\]

Note that $\vol(\fP_x)=\frac{1}{n}$ for all $x\in L$. Similarly, we get an upper bound by adding lattice points whose cells intersect $K$ and thus

\[
\le \frac{1}{n}\sum_{x\in L\cap \Uout}\big(\bfone_{\Uout}(x) - n\,\vol(\fP_x)\big)+ \vol(\Uout\setminus K)
=\vol(\Uout\setminus K).
\]

Taken together, they imply for the absolute value of the signed discrepancy, the discrepancy of $K$, that

\[
\le \max\{\vol(K\setminus \Uin),\vol(\Uout\setminus K)\}.
\]

Therefore, the discrepancy is bounded in terms of the cells intersecting the boundary of $K$. In the following, we will obtain an upper bound of the volumes in the maximum by the diameter of the cell $\fP$ and bound the latter in terms of the spectral test. Taking the supremum over all convex $K\subset [0,1)^d$ then proves the upper bound of Theorem <ref>.

The sets $K\setminus \Uin$ and $\Uout \setminus K$ are contained in $K_{\dia}^-$ and in $K_{\dia}^+$, respectively, where, for any $\varrho\in \IR$,

\[
K_{\rho}^-:=\{x\in K\colon \dist(x,K^C)\le \rho\}\quad\text{and}\quad K_{\rho}^+:=\{x\in K^C \colon  \dist(x,K)\le \rho\}
\]

are the inner and the outer $\rho$-neighborhood, respectively. Thus, we have the bound

\[
\le \max\big\{\vol\big(K_{\dia}^-\big),\vol\big(K_{\dia}^+\big)\big\},
\]

which is more effective if the diameter of the cells is small.

We continue with the help of the following lemma.

For any $\rho\in [0,1]$ we have $\max\{\vol(K_{\rho}^+),\vol(K_{\rho}^-)\}\le 2^{d+3}\rho$.

The proof of this bound on the volume of a neighborhood of a convex set will be provided in Appendix <ref>. It relies on Steiner's formula which expresses, for every $\rho> 0$, the volume of the Minkowski sum $K+\rho \IB_2=\{x\in\IR^d\colon \dist(x,K)< \rho\}$ of $K$ with a ball of radius $\rho>0$ as a polynomial in $\rho$. For the proof of Lemma <ref> one needs suitable bounds on its coefficients.

We shall apply Lemma <ref> for $\rho=\dia$, where $\fP$ is the fundamental domain of a suitable basis $b_1,\ldots,b_d$ of $L$ consisting of short vectors such that the diameter is close to smallest possible. We will argue later why we can assume that $\dia \le 1$.

To find such a basis of short vectors, we use the LLL-lattice basis reduction algorithm, which was originally derived by Lenstra, Lenstra and Lovász in <cit.> to factorize polynomials but then received widespread attention in many other fields. For more information we refer to Galbraith <cit.>. The LLL-algorithm computes an LLL-reduced basis given as follows.

A basis $b_1,\ldots,b_d$ of a lattice $L$ is called LLL-reduced (with parameter $\delta=3/4$) if

* $|\mu_{i,j}|\le \frac{1}{2}$ for $1\le j\le i\le d$,

* $\|b_i^*\|_2^2\ge (\frac{3}{4}-\mu_{i,i-1}^2)\|b_i^*\|_2^2$ for $2\le i\le d$,

\[
b_1^*=b_1, \quad b_i^*=b_i-\sum_{j=1}^{i-1}\mu_{i,j}b_j^*\text{ for }i=2,\dots,d\quad \text{with }\mu_{i,j}:=\langle b_i, b_j^*\rangle/\|b_j^*\|_2^2
\]

is the Gram-Schmidt orthogonalization of $b_1,\ldots,b_d$.

Then we have the following lemma for the corresponding fundamental cell $\fP$ via Definition <ref>.

The diameter of a fundamental domain $\fP$ of a $d$-dimensional lattice $L$ with respect to an LLL-reduced basis $b_1,\ldots,b_d$ as in Definition <ref> is bounded by

\[
\dia\le d\,2^{d-1}\sigma(L)
\]

Inserting this into Lemma <ref> completes the proof of the upper bound of Theorem <ref>. It remains to justify why it is sufficient to consider the case $\dia\le 1$. This is because in any case the isotropic discrepancy is at most one and thus we can assume that $\sigma(L) \le d^{-1} \, 2^{-2(d+1)}$, since else the upper bound is trivial. By Lemma <ref> this translates to

\[
\dia\le d\, 2^{d-1}\sigma(L)
\le 2^{-d-3}<1.
\]

We note the following corollary of Lemma <ref> giving a bound on the neighbourhood of the boundary of a convex set.

Let $K\subset [0,1)^d$ be non-empty and convex. Then, for any $\rho\in [0,1]$ we have

\[
\vol\big(\{x\in\mathbb{R}^d \colon  \dist(x,\partial K)\le \rho\}\big)\le 2^{d+4}\rho.
\]

As explained in <cit.>, the proof of <cit.> contained an erroneous version of Lemma <ref> in <cit.>, where the argument used in the proof of <cit.> was incorrectly extended to higher dimensions, although the asymptotic result itself remains valid with adjusted constants in $d$.

The dependence of the upper bound of Lemma <ref>, and thus Corollary <ref>, on the dimension $d$ can be improved to be sub-exponential in $d$. Essentially, it is of order of magnitude ${\rm e}^{c d^{2/3}}$ for $c=\frac{3}{2}(2\pi)^{1/3}$. A proof is given in Appendix <ref>.

§ OPEN QUESTIONS

The first question arises canonically.

Can the unit cube be replaced by a more general set in Theorem <ref>?

Thinking of the geometry behind, it appears that the cube $[0,1)^d$ can be replaced by any convex set. It would be interesting how <cit.> may be extended to more general convex sets. This is somewhat related to the famous hyperplane conjecture, see, e.g., the book of Brazitikos, Giannopoulos, Valettas and Vritsiou <cit.>.

The second question is about the constants involved.

What is the correct dependence on $d$ in Theorem <ref>?

The exponential upper bound is essentially due to volume arguments involved and we do not know if it can be improved or other methods have to be employed.

In the introduction to this chapter we related the isotropic discrepancy to a worst-case error in a function space of functions of bounded $\cK$-variation denoted by $V(\cK)$ and into which $C^2( (0,1)^d)$ is embedded. This is already a partial answer to the following question.

Can the function space $(V(\cK),\|\cdot\|_{V(\cK)})$ be characterized in terms of smoothness?

Note that $V(\cK)$ contains indicator functions of convex sets. In general, relating discrepancies to worst-case errors of cubature rules is of much interest and may lead to a better understanding of the best possible behaviour of $n$-point sets. For $L_2$-averaged discrepancy there is a connection to reproducing kernel Hilbert spaces, see, e.g., <cit.>. On the sphere, this becomes a beautiful connection to a sum of distances, which is known from <cit.> as Stolarsky's invariance principle, see also Brauchart and Dick <cit.>.

CHAPTER: LIST OF SYMBOLS

[CO]List of symbols
[CE]List of symbols
tocchapterList of symbols
We list here frequently occuring notation. For basic notation see the end of Chapter <ref>.

§.§ Sets

$\overline{\Omega},\partial\Omega$     closure/boundary of a set $\Omega\subset\IR^d$

$\diam(\Omega)$     diameter of $\Omega$, equal to $\sup_{x,y\in\Omega}\|x-y\|_2$

$\dist(x,A)$     distance of $x$ to $A$, equal to $\inf_{y\in A}\|x-y\|_2$

$\vol(A)$     $d$-dimensional Lebesgue measure of $A$

$A+B$     Minkowski sum of sets $A,B\subset\IR^d$, see Def. <ref> (p. def:minkowski)

$\bfone_A$     indicator function of a set $A$

$f|_A$     restriction of a function $f$ to $A$

§.§ Linear and standard information

$e(S\colon F\to G, A)$     worst-case error of $A$, see eq. (<ref>) (p. eq:wce)

$r(S\colon F\to G, N_n)$     radius of the information map $N_n$, see Def. <ref> (p. def:radius)

$r(S\colon F\to G, \Lambda,n)$     $n$-th minimal radius of information, see Def. <ref> (p. def:minimal-radius)

$\lall=F'$     space of continuous linear functionals (p. loc:lall)

$c_n(S\colon F\to G)$     $n$-th Gelfand number of $S$, see Def. <ref> (p. def:gelfand-number)

$c_n(K)$     $n$-th Gelfand width of $K$, see eq. (<ref>) (p. eq:gelfand-width)

$G_{n,m}$     Gaussian random matrix, see Def. <ref> (p. def:lin-ran)

$\mathcal{G}_{m,m-n}$     Grassmannian (p. def:lin-ran)

$\enran$     a random subspace of codimension $n$, see Def. <ref> (p. def:lin-ran)

$\delta_x$     Delta functional with $\delta_x(f)=f(x)$ (p. eq:info-std)

$\lstd$     function evaluations (p. eq:info-std)

$\pnran$     a random point set with $n$ points, see Def. <ref> (p. def:std-ran)

$\intmu,{\rm INT}$     integration functional (p. loc:int)

§.§ Function spaces

$F\hookrightarrow G$     continuous embedding $\id\colon F\to G$ (p. loc:embedding)

$C_b(D)$     bounded continuous functions on $D$ (p. loc:cb)

$L_q(D,\mu)$     $q$-integrable functions on $(D,\mu)$ (p. eq:lqnorm)

$A^{\alpha}_q(\TT^d)$     function space defined via Fourier coefficients, see Def. <ref> (p. def:aaq)

$W^s_p(D)$     Sobolev functions on $D$, see Def. <ref> (p. def:sobolev)

$C^s(D)$     Hölder continuous functions on $D$ (p. eq:semi-norm-hoelder)

${\rm Lip}(D)$     Lipschitz continuous functions on $D$ (p. eq:lip-wce)

$B^s_{p\tau}(D)$     Besov space on $D$, see Appendix <ref> (p. loc:bandf)

$F^s_{p\tau}(D)$     Triebel-Lizorkin space on $D$, see Appendix <ref> (p. loc:bandf)

§.§ Notation for Chapter 3

$\rad(K,E)$     radius of the intersection $K\cap E$, see eq. (<ref>) (p. eq:radius-def)

$\crn(K)$     $n$-th random Gelfand width of $K$, see eq. (<ref>) (p. eq:crn-def)

$\elz$     ellipsoid with semiaxes given by $\sigma$, see eq. (<ref>) (p. eq:ellipsoid)

$\elp$     $\ell_p$-ellipsoid with semiaxes given by $\sigma$, see Def. <ref> (p. def:elp)

$D_{\sigma}$     diagonal operator (p. fig:ellipsoids)

$\|\cdot\|_{p,\sigma}$     (quasi-)norm with unit ball $\elp$, see eq. (<ref>) (p. eq:psigma-norm)

$\|\cdot\|_{p,q}$     Lorentz (quasi-)norm, see Def. <ref>  (p. def:lorentz)

$\decay\big(\rad(\elp,n)\big)$     rate of polynomial decay of minimal radii  (p. loc:decay-det)

$\decay\big(\rad(\elp,\enran)\big)$     rate of polynomial decay of the random radii (p. loc:decay-ran)

$M^*(K)$     mean width of $K$, see eq. (<ref>) (p. eq:mean-width)

$\Delta_p$     $\ell_p$-minimization, see eq. (<ref>) (p. eq:ellp-min)

$\delta_s(N_n)$     restricted isometry constant of order $s$ of $N_n$ (p. eq:rip)

§.§ Notation for Chapter 4

$h_{\Pn,\Omega}$     covering radius of $\Pn$ in $\Omega$, see eq. (<ref>) (p. eq:covering-rad)

$C(x,\xi,r,\theta)$     cone, see Definition <ref> (p. def:cone-condition)

$B(x,\varrho),Q(x,\varrho)$     ball/cube with center $x$ and radius $\varrho$, see eq. (<ref>) (p. eq:cubes-balls)

$Q_{\Pn}(x)$      good cube centered at $x$ with radius $r_{\Pn}(x)$, see Def. <ref> (p. def:small-cube)

$D_{\mu,\Pn,\gamma}$      distortion, see eq. <ref> (p. eq:distortion)

$T_{\Pn}$     optimal quantizer, see eq. <ref> (p. eq:opt-quant)

$C(x_i,\Pn)$     Voronoi cell of $x_i\in \Pn$, see eq. <ref> (p. eq:opt-quant)

§.§ Notation for Chapter 5

$\nu_{\Pn,a}$     discrete measure on $\Pn$ with weights $a$, see eq. (<ref>) (p. eq:discrete)

$Q_{\Pn,a}$     cubature rule with points $\Pn$ and weights $a$, see eq. (<ref>) (p. eq:cubature)

$Q_{\Pn,\mu}$     optimal cubature rule for $\lipd$, see eq. (<ref>) (p. eq:opt-cubature)

$Q_{\Pn}$     equal-weight cubature rule, see eq. (<ref>) (p. eq:qmc)

§.§ Notation for Chapter 6

$D_{\cA}(\Pn)$     discrepancy of $\Pn$ with respect to $\cA$, see eq. (<ref>) (p. eq:disc-def)

$\cK$     class of convex sets contained in $[0,1)^d$ (p. eq:iso-def)

$\mathcal{A}$     class of axis-parallel boxes contained in $[0,1)^d$ (p. eq:iso-def)

$D_{\cK}(\Pn)$     isotropic discrepancy of $\Pn$, see eq. (<ref>) (p. eq:iso-def)

$V(\cK)$     functions with finite $\cK$-variation (p. eq:iso-def)

$D_{\cK}(n)$     $n$-th minimal isotropic discrepancy, see eq. (<ref>) (p. eq:iso-min)

$\cP(L)$     lattice point set generated by $L$, see Def. <ref> (p. def:lattice)

$\sigma(L)$     spectral test of $L$, see Def. <ref> (p. def:spectral-dual)

$L^{\bot}$     dual lattice of $L$, see Def. <ref> (p. def:spectral-dual)

$\cH^*$     hyperplane covering of maximal distance (p. loc:chstar)

$\fP,\fP_x$     (translated) fundamental cell, see Def. <ref> (p. def:fundamental)

$\det(L)$     determinant of $L$ or volume of $\fP$ (p. loc:det)

CHAPTER: ADDITIONAL MATERIAL FOR CHAPTER 3

§ GELFAND NUMBERS OF DIAGONAL OPERATORS

In what follows, we collect useful knowledge about the Gelfand numbers of diagonal operators. At the end of this section we will state and prove Corollary <ref> from which the expression in (<ref>) on the rate of polynomial decay of the minimal radius for an $\ell_p$-ellipsoid with polynomial semiaxes is deduced.

Let $0< p,q\le \infty$ and $\sigma=(\sigma_{j})_{j\in\IN}$ with $\sigma_{1}\ge \sigma_{2}\ge \cdots \ge 0$. To this sequence we associate the diagonal operator

\[
\quad x=(x_{j})_{j\in\IN}\mapsto (\sigma_{j}x_{j})_{j\in\IN},
\]

which, for any $m\in\IN$, can be considered as an operator from $\ell_p^m$ to $\ell_q^m$. Recall that

\begin{equation}\label{eq:radiusgelfand}
\rad(\elp,n)
= c_{n+1}(D_{\sigma}\colon \ell_{p}^{m}\to\ell_{2}^{m})\quad\text{for all }0\le n< m,
\end{equation}

and an analogous result holds if 2 is replaced by $q$ and we measure the radius in $\|\cdot\|_q$.  Although we will need only the case $q=2$, we state the following result in a more general form.

Let $0< q \le p\le \infty$ and $\sigma_{1}\ge \sigma_{2}\ge \cdots\ge 0$. Then, for any $1\le n\le m$, we have

\[
\]

where $\frac{1}{r}=\frac{1}{q}-\frac{1}{p}$ if $q<p$ and $r=\infty$ if $q=p$.

A proof can be found in <cit.> for the case $q\ge 1$ but is in fact also valid if $q<1$. In addition to Proposition <ref>, we have for all $0< p,q\le \infty$ that

\[
c_{1}(D_{\sigma}\colon \ell_{p}^{m}\to\ell_{q}^{m})
= \|D_{\sigma}\colon \ell_{p}^{m}\to\ell_{q}^{m}\|
= \Big(\sum_{j=1}^{m}\sigma_{j}^{r}\Big)^{1/r},
\]

where $\frac{1}{r}=(\frac{1}{q}-\frac{1}{p})_{+}$. This shows that $\|\sigma\|_{r}<\infty$ is necessary to ensure that the operators $D_{\sigma}\colon \ell_{p}^{m}\to\ell_{q}^{m}, m\in\IN,$ are uniformly bounded and explains the condition $\lambda>(\frac{1}{2}-\frac{1}{p})_+$ in Section <ref>.

All of the above extends to the infinite-dimensional case in a canonical way and we now state an equivalence between the Lorentz quasi-norm of an infinite sequence $\sigma$ and the Gelfand numbers of the corresponding diagonal operators. It is taken from Buchmann <cit.> and one implication can be extracted from Linde <cit.>. The technique behind makes use of well-known results on the Gelfand numbers of the identity operator from $\ell_p$ to $\ell_q$ by, to name a few, Garnaev and Gluskin <cit.>, Gluskin <cit.>, Ismagilov <cit.> and Kashin <cit.>.

Let $1\le p,q\le \infty$ and $r>0$ with $\frac{1}{r}>(\frac{1}{q}-\frac{1}{p})_{+}$ as well as $0< t\le\infty$. Then

\[
\sigma\in\ell_{r,t}
\quad\Leftrightarrow\quad \big(c_{n}(D_{\sigma}\colon \ell_{p}\to\ell_{q})\big)_{n\in\IN}\in \ell_{u,t},
\]

* if $1\le q\le p\le\infty$, then $\frac{1}{u}=\frac{1}{r}+\frac{1}{p}-\frac{1}{q}$,

* if $1\le p<q\le 2$, then $\frac{1}{u}=
\begin{cases}
\frac{p^*}{2r}&\text{if }\frac{1}{r}<\frac{1}{p^*}\frac{1/p-1/q}{1/p-1/2},\\
\frac{1}{r}	+\frac{1}{p}-\frac{1}{q}&\text{if }\frac{1}{r}>\frac{1}{p^*}\frac{1/p-1/q}{1/p-1/2},
\end{cases}$

* if $1\le p<2<q\le \infty$, then $\frac{1}{u}=
\begin{cases}
\frac{p^*}{2r}&\text{if }\frac{1}{r}<\frac{1}{p^*},\\
\frac{1}{r}	+\frac{1}{p}-\frac{1}{q}&\text{if }\frac{1}{r}>\frac{1}{p^*},
\end{cases}$

* if $2\le p<q\le\infty$, then $\frac{1}{u}=\frac{1}{r} $.

By means of equality (<ref>), the above Propositions <ref> and <ref> apply to the minimal radius for $\ell_p$-ellipsoids. Note that in the latter proposition some cases are missing; for example, if $q=2$, there is a gap for $\frac{1}{r}=\frac{1}{p^*}$. In this case, we can deduce the following corollary from Theorem <ref>.

For all $n\in\IN$,

\[
c_n(D_{\sigma}\colon \ell_p\to\ell_2)
\lesssim
\begin{cases}
n^{-1/2}\sup\limits_{k\le j\le \infty}\sigma_{j}\sqrt{\log(j)+1} &\text{if }p=1,\\
\sqrt{p^*}n^{-1/2} \Big(\sum\limits_{j=k}^{\infty}\sigma_{j}^{p^{*}}\Big)^{1/p^{*}} &\text{if }1< p\le \infty,
\end{cases}
\]

where $k\asymp \frac{n}{p^*}$ for $p>1$, while $k\asymp n$ for $p=1$. In particular, $c_{n}(D_{\sigma}\colon \ell_{p}\to\ell_{2})\in \ell_{2,\infty}$ if $1<p\le \infty$ and $\sigma\in \ell_{p^*}$.

We use (<ref>) to state Theorem <ref> for Gelfand numbers. Then, for each $m\in\IN$, let $D_{\sigma}^m$ be the restriction of the operator $D_{\sigma}$ to the first $m$ coordinates. This gives

\[
c_n(D_{\sigma}\colon \ell_p^m\to\ell_q^m)
=c_n(D_{\sigma}^m\colon \ell_p\to\ell_q),
\]

and further, by continuity and Hölder's inequality,

\[
\big|c_n(D_{\sigma}^m\colon \ell_p\to\ell_q)-c_n(D_{\sigma}\colon \ell_{p}\to\ell_{q})\big|
\le \Big(\sum_{j=m+1}^{\infty}\sigma_j^s\Big)^{1/s},
\]

with $\frac{1}{s}=(\frac{1}{2}-\frac{1}{p})_+$. Letting $m\to\infty$ for each $n\in\IN$ completes the proof.

Let us note that bounding the Gelfand numbers of operators into $\ell_2$ via $M^*$-estimates has been done before, e.g., in <cit.>.

As a corollary to Proposition <ref> we obtain the following result on the order of decay of the minimal radius of $\ell_p$-ellipsoids with polynomially decaying semiaxes. For $p\ge 2$ it also follows from Proposition <ref> which shows that $\rad(\elp,n) \lesssim n^{-\lambda+1/2-1/p}$ for all $m>n$ with a matching lower bound for $m$, say, larger than $2n$.

Let $1\le p\le \infty$. If $\sigma_j=j^{-\lambda}$, $j\in\IN$, for some $\lambda>(\frac{1}{2}-\frac{1}{p})_+$, then

\begin{equation*}
\decay\big(\rad(\elp,n)\big)
=	\begin{cases}
\lambda\cdot\frac{p^{*}}{2}&\text{if } 1\le p<2 \text{ and }\lambda<\frac{1}{p^{*}},\\
\lambda+\frac{1}{p}-\frac{1}{2}&\text{otherwise.}
\end{cases}
\end{equation*}

We only prove the first case since the other case does not require additional ideas. To show that $\decay\big(\rad(\elp,n)\big)\ge \lambda p^*/2$, it is sufficient by (<ref>) to find $C>0$ such that, for all $\varrho<\lambda p^*/2$ large enough,

\begin{equation}\label{eq:decay}
:=c_{n}(D_{\sigma}\colon \ell_{p}^{m}\to\ell_{q}^{m})
\le C n^{-\varrho}\quad \text{for all }m\in\IN \text{ and }1\le n\le m.
\end{equation}

This is satisfied if the sequence of Gelfand numbers $c_{n}(D_{\sigma}\colon \ell_{p}\to\ell_{q})\geq c_{n,m}$ ($n\in\IN$) belongs to $\ell_{u,\infty}$ with $u=1/\varrho$. By Proposition <ref>, this holds if $\sigma\in \ell_{r,\infty}$ with a certain $r>1/\lambda$, which is true by assumption.

For the other inequality we assume that (<ref>) holds for some $\varrho>\lambda p^*/2$. Choosing $m$ large enough compared to $n$, see the proof of Corollary <ref>, we deduce from (<ref>) that for some $\varrho>\lambda p^*/2$ and every $n\in\IN$,

\begin{equation}\label{eq:decay-inf}
:=c_{n}(D_{\sigma}\colon \ell_{p}\to\ell_{q})
\le 2C n^{-\varrho}.
\end{equation}

For every $r< 1/\lambda$ and $0<t<\infty$, it follows from $\sigma\not\in \ell_{r,t}$ and Proposition <ref> that

\[
\sum_{n=1}^{\infty}\frac{1}{n}c_{n}^t n^{tp^*/2r}=\infty,
\]

which implies $c_n n^{p^*/2r}\log^{2/t} n\to \infty$, contradicting (<ref>).

§ PROOFS FOR THE CONVEX CASE

In this section we complete the proof ideas for Sections <ref> and <ref>, in particular the upper bound of Theorem <ref> and the lower bound of Proposition <ref>.

We start with the proof of Proposition <ref> on the mean width of a rounded $\ell_p$-ellipsoid which is then used to derive Theorem <ref>. The following elementary estimate for $\ell_q$-norms of structured Gaussian random vectors will be useful.

Let $k\in\IN$ and $1\le q<\infty$. If $b=(b_{j})_{j=1}^k\in\IR^k$ and $X=(b_j g_j)_{j=1}^k$ with independent standard Gaussian random variables $g_1,\dots,g_k$, then

\[
\gamma_{1}\|b\|_{q}
\le \IE \|X\|_{q}
\le \gamma_{q}\|b\|_{q},
\quad \text{where }\quad
\gamma_{q}
\asymp \sqrt{q}.
\]

\[
\IE	\|X\|_{\infty}
\asymp \sup_{1\le j\le k}b_{j}^{*}\sqrt{\log(j)+1},
\]

where $(b_j^*)_{j=1}^k$ is the non-increasing rearrangement of $(|b_j|)_{j=1}^k$ (see Definition <ref>).

For $1\le q<\infty$ the upper bound follows from Jensen's inequality and the lower bound follows from $\|\IE X'\|_{q}\le \IE\|X'\|_{q}=\IE\|X\|_{q}$, where $X'=(|b_j g_j|)_{j=1}^k$. The asymptotics for $q=\infty$ are taken from van Handel <cit.>.

Fix $m\in\IN$, $0\le k< m$ and $\varrho>0$. We shall use the representation (<ref>), which translates to

\[
=\frac{1}{c_m}\IE\sup_{t\in\elp\cap\varrho\IBo_2^m}\sum_{j=1}^{m}t_j g_j,
\]

where $c_m\asymp \sqrt{m}$. In order to bound the supremum, fix some $x\in\IR^{m}$ and $y\in \elp \cap \varrho\IBo_{2}^{m}$. Then it follows from Hölder's inequality that, for every $0\leq k < m$,

\[
\langle x,y\rangle
\le \sum_{j=1}^{k}|x_{j}y_{j}|+\sum_{j=k+1}^{m}|x_{j}y_{j}|
\le \varrho\Big(\sum_{j=1}^{k}x_{j}^{2}\Big)^{1/2}+\Big(\sum_{j=k+1}^{m}\sigma_{j}^{p^{*}}|x_{j}|^{p^{*}}\Big)^{1/p^{*}},
\]

where the first, and consequently the third, sum is empty if $k=0$.
Combining this estimate with Lemma <ref>, we obtain that if $p>1$,

\begin{align*}
\IE\sup_{y\in \elp \cap \varrho\IBo_{2}^{m}}\sum_{j=1}^{m}y_{j}g_{j}
\le \varrho\, a_{k}+\gamma_{p^{*}}\Big(\sum_{j=k+1}^{m}\sigma_{j}^{p^{*}}\Big)^{1/p^{*}},
\end{align*}

where we used that $a_k=\IE\Big(\sum_{j=1}^{k}g_i^2\Big)^{1/2}$, see (<ref>). By the previously stated asympotics for $a_{k}$ and for $\gamma_{p^{*}}$ in Lemma <ref>, we obtain the statement for $p>1$.

If $p=1$, then we deduce from Lemma <ref> that, for some suitable $C>0$,

\[
\IE\,\sup_{y\in \elp\cap \varrho\IBo_{2}^{m}} \sum_{j=1}^{m}y_jg_{j}
\le \varrho\sqrt{k}+C\sup_{k+1\leq j \leq m}\sigma_{j}\sqrt{\log(j)+1}.
\]

This completes the proof.

For any $\varrho>0$, it follows from Gordon's $M^*$-estimate (Proposition <ref>) applied to the convex body $\elp\cap \varrho \IBo_2^m$ that, with probability as claimed, a random subspace $\enran$ of codimension $n$ satisfies

\[
\rad(\elp\cap\varrho \IBo_{2}^{m}, \enran)
=\sup_{x\in \elp \cap \varrho \IBo_{2}^{m}\cap \enran}\|x\|_{2}
\le 2\frac{a_{m}}{a_{n}}M^{*}(\elp\cap\varrho \IBo_{2}^{m}).
\]

We start with the case $p>1$. Inserting the bound obtained in Proposition <ref>, we obtain a constant $C>0$ such that, for any $0\le k< m$ and $1\leq n< m$,

\[
\rad(\elp\cap\varrho \IBo_{2}^{m}, \enran)
\le C \frac{\sqrt{p^*}}{\sqrt{n}}\Big(\varrho\sqrt{k}+\Big(\sum_{j=k+1}^{m}\sigma_{j}^{p^{*}}\Big)^{1/p^{*}}\Big).
\]

In accordance with relation (<ref>), we seek to choose $\varrho$ suitably small and $k$ large such that this radius is bounded by $\varrho$.

First, let $\frac{n}{p^*}>4C^2$. Setting $\varrho:=\frac{1}{\sqrt{k}}\Big(\sum_{j=k+1}^{m}\sigma_{j}^{p^{*}}\Big)^{1/p^{*}}$ with $k:=c\frac{n}{p^*}$, where the constant $c>0$ is chosen (sufficiently small) such that $k\in \IN$ with $1\le k<m$ and

\[
\rad(\elp\cap\varrho \IBo_{2}^{m}, \enran)
\]

and so in particular that

\[
\rad(\elp, \enran)
\]

for all $m\in \IN$ and $1\le n <m$. Noting that

\[
\varrho
\lesssim \frac{\sqrt{p^*}}{\sqrt{n}}\Big(\sum_{j=k+1}^{m}\sigma_{j}^{p^{*}}\Big)^{1/p^{*}},
\]

proves the result for $p>1$ in this case. If $\frac{n}{p^*}\le 4C^2$, then let $k=0$ and let $\varrho>0$ be large enough such that $\elp\subset \varrho \IBo_2^m$ and thus

\[
\rad(\elp,\enran)
\le C\frac{\sqrt{p^*}}{\sqrt{n}}\Big(\sum_{j=1}^{m}\sigma_{j}^{p^{*}}\Big)^{1/p^{*}}.
\]

In both cases, $k+1\asymp \frac{n}{p^*}$. The proof for $p=1$ is carried out analogously.

Next, we prove the general version of the lower bound in Proposition <ref>.

By Lemma <ref>, with probability at least $1-\varepsilon$, we find $x\in \IR^m$ with

\[
x_1^2 \ge 1-\frac{n}{\varepsilon m},\quad
\|x\|_2=1,\quad\text{and}\quad
G_{n,m} x=0.
\]

We estimate

\[
\Big(\sum_{j=1}^{m}\frac{|x_j|^p}{\sigma_j^p}\Big)^{1/p}
\le \frac{1}{\sigma_1}+ \Big(\sum_{j=2}^{m}\frac{|x_j|^p}{\sigma_j^p}\Big)^{1/p}
\le \frac{1}{\sigma_1}+ \frac{1}{\sigma_m}\Big(\sum_{j=2}^{m}|x_j|^p\Big)^{1/p}
\]

and by means of Hölder's inequality, we obtain

\[
\frac{1}{\sigma_m}\Big(\sum_{j=2}^{m}|x_j|^p\Big)^{1/p}
\le \frac{m^{1/p-1/2}}{\sigma_m}\Big(\sum_{j=2}^{m}x_j^2\Big)^{1/2}
= \frac{m^{1/p-1/2}}{\sigma_m}\big(1-x_1^2\big)^{1/2}.
\]

Since $1-x_1^2\le \frac{n}{\varepsilon m}$, we have

\[
\Big(\sum_{j=1}^{m}\frac{|x_j|^p}{\sigma_j^p}\Big)^{1/p}
\le \frac{1}{\sigma_1}+1
\]

if $n\le \varepsilon m^{2p^*}\sigma_m^2$. In this case, we can normalize such that $\tilde{x}:=x/(1+\frac{1}{\sigma_1})$ satisfies

\[
\tilde{x}\in \elp,\quad
G_{n,m} \tilde{x}=0,\quad\text{and}\quad
\|\tilde{x}\|_2=\frac{\sigma_1}{1+\sigma_1},
\]

which completes the proof.

§ PROOFS FOR THE NON-CONVEX CASE

We continue with the results leading to the proof of Theorem <ref>. It is a special case of Theorem <ref> from Section <ref>. The proof relies on Lemma <ref> which is proven first.

Approximating every $x\in\elp$ by the $s$-sparse vector consisting of its $s$ largest entries we obtain

\[
\sigma_s(x)_q
\le\Big(\sum_{j=s+1}^{m}(x_j^*)^q\Big)^{1/q},
\]

where $(x_j^*)_{j=1}^m$ is the non-increasing rearrangement as in Definition <ref>. If $q=\infty$, then take the maximum norm instead and analogously for $p$ in the following. Recall that in this thesis we set $a/\infty=0$ for every $a\in\IR$.

Using that $x\in\elp$, we can write

\[
\ge \sum_{j=1}^{m}\frac{|x_j|^p}{\sigma_{j}^p}
= \sum_{j=1}^{m}\frac{(x_j^*)^p}{\sigma_{\pi(j)}^p}
\ge \sum_{j=1}^{k}\frac{(x_k^*)^p}{\sigma_{\pi(j)}^p},
\]

for any $1\leq k \leq m$, where $\pi:\{1,\ldots,m\}\to\{1,\ldots,m\}$ is a suitable permutation. Thus,

\[
\le \Big(\sum_{j=1}^{k}\frac{1}{\sigma_{\pi(j)}^p}\Big)^{-1}
\le \Big(\sum_{j=1}^{k}\frac{1}{\sigma_{j}^p}\Big)^{-1}
\asymp k^{-\lambda p-1},
\]

where the notation $\asymp$ (and $\lesssim$ below) means in this proof that the implicit constants do not depend on $k,s$ or $m\ge 2s$ but may depend on $p,q$ and $\lambda$.  Inserting this bound above yields

\[
\sigma_s(x)_q
\lesssim\Big(\sum_{k=s+1}^{m}k^{-\lambda q-q/p}\Big)^{1/q}
\asymp s^{-\lambda+1/q-1/p}
\]

as $\lambda>(1/q-1/p)_+$.

The lower bound is achieved by a vector on the boundary of $\elp$ having its support on the first $2s$ coordinates which are all equal to

\[
\Big(\sum_{i=1}^{2s}\sigma_i^{-p}\Big)^{-1/p}
\asymp s^{-\lambda-1/p}.
\]

Let $m\in\IN$, $1\le n<m$, $N_n:=n^{-1/2}G_{n,m}$ and set $r=\min\{1,q\}$. By Proposition <ref>, see also Remark <ref>,

\begin{equation} \label{eq:radq-upper}
\rad_q(\elp,\ker G_{n,m})
\le 2^{(1/q-1)_+} \sup_{x\in \elp}\|x-\Delta_r(N_n x)\|_q,
\end{equation}

where we specified $\varphi(y)=\Delta_r(n^{-1/2}y)=$ arg min $\|z\|_r$ subject to $N_n z=n^{-1/2}y$ for $y=G_{n,m} x$.

We follow the proof of <cit.> in order to obtain an upper bound. To this end, let $D\in (0,\infty)$ be large enough such that

\[
D/2>{\rm e} \quad\text{and}\quad \frac{D/2}{1+\log(D/2)}>C_1,
\]

where $C_1\in(0,\infty)$ is the constant from Proposition <ref> with $\delta=1/3$. Also choose $s\ge 1$ as the largest integer smaller than $ n/D\log({\rm e}m/n)$ such that

\[
\frac{n}{2D\log({\rm e}m/n)}
\le s
< \frac{n}{D\log({\rm e}m/n)}.
\]

Then, if $n\ge D\log({\rm e}m/n)$ it holds that $n>C_1 (2s)\log({\rm e}m/2s)$. This can be seen as follows. Put $t=2s$ such that $t/n<2/D<1/{\rm e}$. As the function $x\mapsto x\log(x)$ is decreasing on $[0,1/{\rm e}]$, we obtain

\[
n\ge\frac{D}{2}t \log({\rm e}m/n)
= \frac{D}{2}t \log({\rm e}m/t)
+ \frac{D}{2}n (t/n) \log({\rm e}t/n)
> \frac{D}{2}t \log({\rm e}m/t)
-n \log(D/2)
\]

and therefore

\[
n\ge\frac{D/2}{1+\log(D/2)}t\log({\rm e}m/t)
>C_1\,t\log({\rm e}m/t).
\]

Then, by Proposition <ref> the matrix $N_n$ satisfies $\delta_{2s}(N_n)\le \delta$ with probability at least $1-2\exp(-C_2 n)$. Assume from now on that $N_n$ is replaced by a realization satisfying this.

Let $x\in\elp$ be arbitrary. Then $v:=x-\Delta_r(N_n x)$ belongs to the kernel and we will apply the restricted isometry property to a decomposition of $v$ in order to bound $\|v\|_q$. Decompose the set $\{1,\dots,m\}$ into disjoint sets $S_1,\dots,S_M$ which are of size $s$, except for possibly $S_M$, such that $|v_i|\ge |v_j|$ for all $i\in S_{k-1}$ and $j\in S_k$, where $k\ge 2$. Write $v=\sum_{k=1}^{M}v_{S_k}$, where $v_{S_k}$ is a vector whose coordinates coincide with $v_i$ if $i\in S_k$ and with zero else. Then $r\le 2$ and Hölder's inequality imply

\begin{equation} \label{eq:v-hoelder}
\|v_{S_k}\|_2\le s^{1/2-1/r}\|v_{S_{k-1}}\|_r,\quad k=2,\dots,M,
\end{equation}

which will be used a few lines below. Together with Hölder's inequality we deduce from the lower bound in the definition (<ref>) of the restricted isometry property for the $s$-sparse (and also $2s$-sparse) vector $v_{S_k}$ that

\[
\|v\|_q^r
\le \Big\| \sum_{k=1}^{M} v_{S_k}\Big\|_q^r
\le \sum_{k=1}^{M} \|v_{S_k}\|_q^r
\le  \sum_{k=1}^{M}(s^{1/q-1/2}\|v_{S_k}\|_2)^r
\le \Big(\frac{s^{1/q-1/2}}{\sqrt{1-\delta}}\Big)^r \sum_{k=1}^{M}\|N_nv_{S_k}\|_2^r.
\]

Since $v\in \ker N_n$, it holds that $N_n v_{S_1}=-\sum_{k=2}^{M}N_n v_{S_k}$ and further, since $r\le 2$,

\[
\|N_n v_{S_1}\|_2^r
=\Big\|\sum_{k=2}^{M}N_n v_{S_k}\Big\|_2^r
=\Big(\sum_{k=2}^{M}\|N_n v_{S_k}\|_2^2\Big)^{r/2}
\le \sum_{k=2}^{M}\|N_n v_{S_k}\|_2^r.
\]

Thus, we can continue our estimate with

\[
\|v\|_q^r
\le 2 \Big(\frac{s^{1/q-1/2}}{\sqrt{1-\delta}}\Big)^r \sum_{k=2}^{M}\|N_nv_{S_k}\|_2^r.
\]

Applying now the upper bound in the restricted isometry property of (<ref>) yields that

\[
\|v\|_q^r
\le 2 \Big(\frac{\sqrt{1+\delta}}{\sqrt{1-\delta}}s^{1/q-1/2}\Big)^r \sum_{k=2}^{M}\|v_{S_k}\|_2^r.
\]

Using the inequality (<ref>) and that $\delta=1/3$ yields

\[
\|v\|_q
\le 2^{1/r+1/2} s^{1/q-1/r}\Big(\sum_{k=1}^{M}\|v_{S_k}\|_r^r\Big)^{1/r}
= 2^{1/r+1/2}s^{1/q-1/r}\|v\|_r
\]

and inserting now for $s$ yields for some constant $C>0$ depending on $r$ and $C_1$ that

\[
\|v\|_q\le C \,\Big(\frac{\log({\rm e}m/n)}{n}\Big)^{1/r-1/q} \|v\|_r.
\]

After inserting for $v=x-\Delta_r(N_n x)$, we can apply Proposition <ref> to get a bound in terms of the error of best $s$-term approximation of $x$. Then taking the supremum shows that there exists a constant $C>0$, depending on $p,q$ and $C_1$, such that

\[
\sup_{x\in \elp }\|x-\Delta_r(N_n x)\|_q
\le C\, \Big(\frac{\log({\rm e}m/n)}{n}\Big)^{1/r-1/q}\sup_{x\in \elp }\sigma_s(x)_r.
\]

Until now we considered a specific realization of $N_n$ and therefore this holds with probability at least $1-2\exp(-C_2 n)$ for the random matrix $N_n$.

With Lemma <ref> the proof of Theorem <ref> is complete if we can show that $s\le m/2$. Indeed, since the function $n\mapsto n/\log({\rm e}m/n)$ is increasing for $1\le n\le m$, we have $s\le m/D < m/2{\rm e}$.

CHAPTER: ADDITIONAL MATERIAL FOR CHAPTER 4

We provide the proofs for the statements claimed in Chapter <ref> and in particular follow the ideas given in Sections <ref> and <ref> to complete the proof of Theorem <ref> and its extension, Theorem <ref>.

First, in Section <ref>, we provide the proofs for the asymptotics of the optimal distortion (<ref>) and for Example <ref>.

In Section <ref> we continue with technical preparations regarding the approximation of Sobolev functions by polynomials (Lemma <ref>) and their extension from bounded Lipschitz domains to the whole space (Lemma <ref>). We also give a proof of the known fact that a bounded convex domain has Lipschitz boundary (Lemma <ref>).

Section <ref> contains the proof of Theorem <ref> for the case $q\ge p$. As a preparation for the upper bound, Lemma <ref> is deduced from <cit.> and the fact that the interior cone condition is preserved by the closure (Lemma <ref>) is proven. The lower bound relies on finding a suitable large hole which is provided by Lemma <ref>.

In Section <ref> we give the proof of Theorem <ref> for the case $q<p$. For this, we commence by proving the local cone condition (Lemma <ref>) and the error bound of moving least squares applied to a cube (Lemma <ref>). Afterwards, Lemmas <ref> and <ref> justify the Definition <ref> of the smallest good cube. Then the existence of an efficient covering (Proposition <ref>) and of a hole of proportional size in every smallest good cube (Lemma <ref>) are proven. With these preparations at hand the proof of the upper and lower bound in the case $q<p$ is given.

Finally, in Section <ref> we prove the extension, Theorem <ref>, of our results to more general function spaces. There, we shall also provide a definition of Besov and Triebel-Lizorkin spaces.

In this appendix we will make use of the asymptotic notations $\lesssim,\gtrsim,\asymp$ as given in Definition <ref>. Additionally, whenever an arbitrary but fixed function $f$ occurs, the implicit constants will not depend on it.

§ PROOFS FOR SECTION 4.2

Let us prove the asymptotics for the optimal points on a bounded set $\Omega\subset\IR^d$.

Let $n\in\IN$ and $\Pn=\{x_1,\dots,x_n\}\subset\IR^d$. Since

\begin{equation} \label{eq:dist-norms}
\|\dist(\cdot,\Pn)\|_{L_{\infty}(\Omega)}\ge \vol(\Omega)^{1/\gamma}\|\dist(\cdot,\Pn)\|_{L_{\gamma}(\Omega)}\text{ for every }0<\gamma<\infty,
\end{equation}

it suffices to prove the upper bound for $\gamma=\infty$ and the lower bound for $0<\gamma<\infty$.

For the upper bound we construct an $\varepsilon$-net, with $\varepsilon>0$ to be fixed later, by iteratively selecting $y_1\in\Omega$, $y_2\in\Omega\setminus B(y_1,\varepsilon)$ and $y_{k+1}\in\Omega$ not contained in $\bigcup_{j=1}^k B(y_j,\varepsilon)$ until the process stops after finitely many steps. Then we are left with $N$ balls $B(y_1,\varepsilon),\dots,B(y_N,\varepsilon)$ which cover $\Omega$ and the balls $B(y_1,\varepsilon/2),\dots,B(y_N,\varepsilon/2)$ are disjoint.

If $\varepsilon<1$, we have the volume estimate

\[
\vol\big(\Omega+B(0,1/2)\big)
\ge \vol\Big(\bigcup_{j=1}^N B(y_j,\varepsilon/2)\Big)
= N (\varepsilon/2)^d \vol(\IB_2^d).
\]

We refer to Definition <ref> in Appendix <ref> for the sum of sets.

If we choose, for sufficiently large $n$,

\[
\varepsilon=2\,\vol(\IB_2^d)^{-1/d}\vol\big(\Omega+B(0,1/2)\big)^{1/d}n^{-1/d},
\]

it follows that $N\le n$ and therefore $P_N=\{y_1,\dots,y_N\}$ has at most $n$ points and every point of $\Omega$ is not more than $\varepsilon$ from the nearest point of $P_N$. This proves the upper bound. For completeness, adding arbitrary points ensures that $\#P_N=n$.

For the proof of the lower bound, let $0<\gamma<\infty$ and fix

\[
\delta=\big(\vol(\Omega)/2\,\vol(\IB_2^d)\big)^{1/d} n^{-1/d}\quad \text{ such that }\quad n\,\vol\big(B(0,\delta)\big)= \vol(\Omega)/2.
\]

Then for any $\Pn=\{x_1,\dots,x_n\}\subset \IR^d$ the set

\[
\Omega_{\Pn}:=\Omega\setminus \bigcup_{i=1}^n B(x_i,\delta)
\]

has volume at least $\vol(\Omega)/2$ and $\dist(x,\Pn)^{\gamma}\ge \delta^{\gamma}$ for each $x\in \Omega_{\Pn}$. Integrating over $\Omega_{\Pn}$ yields

\[
\|\dist(\cdot,\Pn)\|_{L_{\gamma}(\Omega)}^{\gamma}
\ge \int_{\Omega_{\Pn}}\dist(x,\Pn)^{\gamma}\dd x
\gtrsim n^{-\gamma/d},
\]

concluding the proof.

Next, we provide the proof for the claimed necessary condition in Example <ref> for the optimality of a sequence of point sets.

Assume that for each $n$ the ball $B_n:=B(y_n,r_n)$ with $y_n\in\Omega$ and $r_n>0$ does not contain any points of $\Pn$ and that the points of $\Pn$ cover $\Omega\setminus B_n$ nicely, i.e., the covering radius of $\Pn$ in $\Omega\setminus B_n$ is of order $n^{-1/d}$. Then we have

\[
\int_{\Omega}\dist(x,\Pn)^{\gamma}~{\rm d}x \,\ls\, n^{-\gamma/d}+r_n^{\gamma+d}\quad \text{for all }0<\gamma<\infty.
\]

Rearranging, this means that if $r_n\lesssim n^{-1/d+1/(\gamma+d)}$, then $\|\dist(\cdot,\Pn)\|_{L_{\gamma}(\Omega)}\lesssim n^{-1/d}$ for the sequence $(\Pn)_{n\in\IN}$.

To show that this condition is also necessary, note that $\dist(x,\Pn) \ge r_n/2$ for every $x\in\Omega \cap B(y_n,r_n/2)$ and $n\in\IN$. The interior cone condition satisfied by $\Omega$ implies that there is a constant $c>0$ depending only on $\Omega$ such that $\vol\big(\Omega \cap B(y_n,r_n/2)\big)\ge c\, r_n$, and thus

\[
\int_{\Omega}\dist(x,\Pn)^{\gamma}~{\rm d}x \,\gs\, r_n^{\gamma+d}.
\]

Letting $1\le q<p \le \infty$ and $\gamma$ as above, we obtain from Corollary <ref> that $(\Pn)_{n\in\IN}$ is asymptotically optimal for $L_q$-approximation on $W_p^s(\Omega)$ if and only if condition (<ref>), that is,

\begin{equation*}
r_n\ls n^{-1/d+1/(\gamma+d)}
\end{equation*}

is satisfied.

§ APPROXIMATION AND EXTENSION OF SOBOLEV FUNCTIONS

In the following, let $\Omega\subset \IR^d$ be a domain as well as $1\le p\le \infty$ and $s\in\IN$ as in (<ref>). Recall from Definition <ref> that the Sobolev norm of a function $f\in W^s_p(\Omega)$ is given by

\[
\|f\|_{W^s_p(\Omega)}=\Big(\sum_{|\alpha|\leq s} \|D^{\alpha}f\|_{L_p(\Omega)}^p\Big)^{1/p},
\]

where the sum is over all multi-indices $ \alpha\in \mathbb{N}_0^d $ with sum of entries $ |\alpha|=\alpha_1+\ldots+\alpha_d $ at most $s$.  The seminorm

\begin{equation} \label{eq:sob-seminorm}
|f|_{W^s_p(\Omega)}:= \Big(\sum_{|\alpha|= s} \|D^{\alpha}f\|_{L_p(\Omega)}^p\Big)^{1/p}
\end{equation}

is zero on polynomials of degree at most $s-1$ and will be used to bound the error by polynomial approximation.

Variants of the following result about optimal polynomial approximation on cubes are well known, see, e.g., the references provided in <cit.>. The proof given here is not adapted from <cit.>, where we stated it originally, but from the similar <cit.>.

For any $1\le p\le \infty$ and $s\in \IN$ as in (<ref>), there is a constant $\cpoly>0$ such that the following holds.  For any $0< \varrho \le 1$, any cube $Q(x,\varrho)$ with center $x\in\IR^d$ and radius $ \varrho $, and any $f\in W^s_p(\IR^d)$, there is a polynomial $\pi$ of degree at most $s$ such that

\[
\sup_{x\in Q(x,\varrho)}\vert(f - \pi)(x)\vert \le \cpoly \,  \varrho ^{s-d/p} \vert f \vert_{W_p^s(Q(x,\varrho))}.
\]

We use an affine map $T$ from $Q=Q(x,\varrho)$ to the reference cube $Q_0=Q(0,1)$ with $T(y)=\varrho^{-1}(y-x)$ for every $y\in Q$. Applied to the function $f\circ T^{-1}\colon Q_0\to\IR$, the generalized Poincaré inequality from <cit.> implies that there exists a constant $c_1>0$ independent of $f$ and $Q$ such that we find a polynomial $\pi$ of degree at most $s-1$ with

\begin{equation}\label{eq:poincare}
\|f\circ T^{-1} - \pi\|_{W^s_p(Q_0)}
\, \le \, c_1\, |f\circ T^{-1}|_{W^s_p(Q_0)}.
\end{equation}

A change of variables, together with the chain rule and integration by substitution, gives another constant $c_2> 0$ such that

\begin{equation}\label{eq:cov}
|f\circ T^{-1}|_{W^s_p(Q_0)}
\, \le \, c_2\,\varrho^{s-d/p}\,|f|_{W^s_p(Q)}.
\end{equation}

The continuous embedding of $W^s_p(Q_0)$ into $C_b(Q_0)$, see the introduction to Chapter <ref>, yields $c_3>0$ with

\[
\Vert f - \pi' \Vert_{L_\infty(Q)}
\,=\, \|f\circ T^{-1} - \pi \|_{L_{\infty}(Q_0)}
\,\le\,c_3\,\|f\circ T^{-1} - \pi \|_{W^s_p(Q_0)},
\]

where $\pi'=\pi\circ T$ is again a polynomial of degree at most $s-1$.  Combining this with the estimates (<ref>) and (<ref>) yields

\[
\Vert f - \pi' \Vert_{L_\infty(Q)}
\,\le\,\cpoly\,\varrho^{s-d/p}|f|_{W^s_p(Q)},
\]

where $\cpoly:=c_1\,c_2\,c_3$ is independent of $f$ and $Q$. The continuity of $f-\pi'$ concludes the proof.

The reason that Lemma <ref> is stated for functions defined on the whole space $\IR^d$ is that we can extend the functions from $W^s_p(\Omega)$ to $W^s_p(\IR^d)$, when $\Omega$ is a bounded convex domain, which is the content of well-known Sobolev extension theorems. See, e.g., the historical comments in <cit.>. To state a version suitable for our needs, we introduce the notion of a bounded Lipschitz domain, which is a popular regularity condition under which Sobolev embedding and extension theorems hold. The following definition was used in <cit.> and taken from <cit.>.

A bounded Lipschitz domain $\Omega$ is a domain with the following property. There are points $x_1,\ldots,x_N\in\partial\Omega$ on the boundary and radii $r_1,\ldots,r_N>0$ such that $\partial\Omega$ is covered by the balls $B(x_1,r_1),\ldots,B(x_N,r_N)$ and

\[