\Omega\cap B(x_i,r_i)= \Omega_i\cap B(x_i,r_i), \quad i=1,\ldots,N,
\]

where $\Omega_i$ is a suitable rotation of a special Lipschitz domain in $\mathbb{R}^d$. Here, a special Lipschitz domain in $\mathbb{R}^d$, $d\geq 2$, is the collection of all points $x=(x',x_d)$ with $x'\in\mathbb{R}^{d-1}$ such that

\[
\]

where $h\colon\mathbb{R}^{d-1}\to \IR$ is some Lipschitz function, i.e., there exists a constant $C>0$ with $|h(x')-h(y')|\leq C\|x'-y'\|_2$ for all $x',y'\in\mathbb{R}^{d-1}$.

The following extension theorem is taken from Stein <cit.>.

Let $\Omega \subset \IR^d$ be a bounded Lipschitz domain, $1\le p\le \infty$ and $s\in \IN$.  Then there is a bounded linear operator ${\rm ext}\colon W^s_p(\Omega) \to W^s_p(\IR^d)$ with ${\rm ext}(f)\vert_\Omega = f$ for all $f\in W^s_p(\Omega)$.

Note that Stein uses the notion of a minimally smooth domain which, however, entails bounded Lipschitz domains. Further, the following lemma shows that a bounded convex domain is a bounded Lipschitz domain. As we could not find a suitable proof of this intuitive fact, we provide one ourselves. A similar result may be found in Dekel and Leviatan <cit.>.

Every bounded convex domain is a bounded Lipschitz domain.

If $\Omega\subset \mathbb{R}^d$ is a bounded convex domain, we find a ball $B(x_0,r)\subset \Omega$. As $\partial\Omega$ is compact, there are points $x_1,\ldots, x_N$ such that the balls $B(x_i,r/2)$, $i\le N$, cover $\partial\Omega$.  For all $i\le N$ we show that

\begin{equation}\label{eq:Lip}
\Omega\cap B(x_i,r/2)=\Omega_i\cap B(x_i,r/2),
\end{equation}

where $\Omega_i$ is a rotation of a special Lipschitz domain in $\mathbb{R}^d$.  Applying a suitable rotation (and translation), we may assume that $x_0=0$ and that $x_i=(0,\hdots,0,a)$ for some $a\le -r$. Consider the open ball $B'=B^{d-1}(0,r)$ in $\IR^{d-1}$.  For $x'\in B'$, we define the set $A(x') = \{x_d\in\IR \colon (x',x_d)\in \Omega\} $.  Since $\Omega$ is convex and open, $A(x')$ is an open interval.  Moreover, $A(x')$ is non-empty since $0\in A(x')$.  We define $h(x')$ to be the infimum of $A(x')$.  The convexity of $\Omega$ implies that the function $h\colon B'\to \IR$ is convex.  Since every convex function on a convex domain in $\IR^{d-1}$ is Lipschitz on every compact subset of the domain, see <cit.>, the function $h$ is Lipschitz on the $d-1$-dimensional ball $B^*=B^{d-1}(0,r/2)$. This Lipschitz continuity carries over to the whole $\IR^{d-1}$ if we set $h(\lambda x')=h(x')$ for all $x' \in \partial B^*$ and $\lambda \ge 1$ (thereby redefining $h$ on $B'\setminus B^*$).  It remains to note that for every $x=(x',x_d)\in B(x_i,r/2)$ it holds that

\[
x \in \Omega
\quad\Leftrightarrow\quad
x_d \in A(x')
\quad\Leftrightarrow\quad
x_d > h(x'),
\]

proving (<ref>) for the special Lipschitz domain $\Omega_i=\{(x',x_d)\colon x_d>h(x')\}$.

Moreover, let us mention that a bounded Lipschitz domain satisfies an interior cone condition. This seems to be well known and is used for example in <cit.>, see also <cit.>. However we could not find a proof of this fact. To convince ourselves, we gave a proof of it in <cit.> which we will not repeat here.

§ THE PROOF OF THE CHARACTERIZATION IF $Q\GE P$

Let $\Omega\subset\IR^d$ be a bounded convex domain and $\Pn=\{x_1,\dots,x_n\}\subset\Omega$. Further, let the parameters $p,q,s$ be as in the statement of Theorem <ref> with $q\ge p$ and fix $ r\in (0,1]$ such that $\Omega$ contains a closed ball of radius $r$.  By Lemma <ref> the set $\Omega$ satisfies an interior cone condition as in Definition <ref> with radius $r>0$ and some angle $\theta\in (0,\pi/2)$. In the following, all constants are allowed to depend on the parameters mentioned and in particular on the domain $\Omega$ and its dimension $d$.

For the proof of the upper bound of Theorem <ref> we apply Lemma <ref> to the point set $\Pn$ and the closure $\overline{\Omega}$. To this end, we first deduce Lemma <ref> and then give a proof of the fact that the closure of a set inherits the interior cone condition.

We will show that for any point set $\Pn\subset K$ there is a subset $X\subset \Pn$ with $h_{X, K}\le 2 h_{\Pn, K}$ and separation distance $q_X\ge \frac 12 h_{\Pn,K}$. Then the condition (<ref>) is satisfied for $X$ and we can apply <cit.> to the subset $X$. We then set the functions $u_i$ for every $x_i\in \Pn \setminus X$ equal to the zero function.

Take $y_1=x_1\in \Pn$ and iteratively choose $y_i \in \Pn\setminus \bigcup_{j<i} B(y_j,h_{\Pn, K})$ until this set difference is empty. In this way, we obtain a subset $X$ of $\Pn$ which satisfies $q_X\ge \frac 12 h_{\Pn, K}$. Moreover, for any $x\in  K$, there is some $x_i\in \Pn$ with $\Vert x- x_i \Vert_2 \le h_{\Pn, K}$. Since $\Pn\setminus \bigcup_{y \in X} B(y,h_{\Pn, K})=\emptyset$, there is some $y \in X$ with $\Vert x_i - y \Vert_2 \le h_{\Pn, K}$. The triangle inequality gives $\Vert x - y\Vert_2 \le 2\, h_{\Pn, K}$ and therefore $h_{X, K}\le 2\, h_{\Pn, K}$.

The following proof ensures that the closure $\overline{\Omega}$ satisfies an interior cone condition with $r$ and $\theta$ as above.

Assume that $\Omega\subset\IR^d$ satisfies an interior cone condition with radius $r$ and angle $\theta$. For each limit point $x$ in the closure $\overline{\Omega}$ consider a sequence $(x_n)_{n\in\IN}\subset \Omega$ converging to it and let $C(x_n):=C(x_n,\xi(x_n),r,\theta)\subset \Omega$, where $n\in\IN,$ be the corresponding sequence of cones given by the interior cone condition. As the sphere is a compact metric space when equipped with the geodesic distance, the sequence $\xi(x_n)\in\IS^{d-1}$ of directions contains a convergent subsequence. Upon passing to this subsequence we may assume that $\xi(x_n)$ is convergent itself and define $\xi(x)$ to be its limit point. Then the cone $C(x):=C(x,\xi(x),r,\theta)$ is contained in $\overline{\Omega}$. To give a proof by contradiction, suppose that this does not hold, i.e., there is a point $y\in C(x)$ with positive distance from $\overline{\Omega}$. The convergence of $\xi(x_n)\to \xi(x)$ and of $x_n\to x$ implies that every point of $C(x)$ will be arbitrarily close to some point from $C(x_n)$ whenever $n$ is large enough. This is a contradiction to $y\in C(x)$ having a positive distance from $\overline{\Omega}$ and thus of every $C(x_n)$, where $n\in\IN$.

After these preparations, we prove the already known part of our main result.

Let $m>s$ be an integer and let $c_0,c_1,c_2>0$ be as in Lemma <ref>. In order to apply it to the point set $\Pn=\{x_1,\dots,x_n\}$ and $\overline{\Omega}$ we need to have $ h_{\Pn,\overline{\Omega}}\le c_1  r $. Without loss of generality we can assume that this is satisfied as the upper bound becomes trivial if this does not hold; compare with Lemma <ref> in Appendix <ref> below.

We consider the linear algorithm

\[
S_{\Pn}\colon W_p^s(\Omega) \to L_q(\Omega), \quad S_{\Pn}(f) = \chg{\sum_{i=1}^n} f(x_i) u_i,
\]

with $u_i$ provided by Lemma <ref> for the compact set $ \overline{\Omega} $.

For technical reasons we need a suitable covering of the domain by pieces of radius of order $h_{\Pn,\Omega}$. In order to find such a covering, consider the balls $B(y,h_{\Pn,\Omega})$, $y\in \Omega$.  By compactness we can extract a finite subset $I\subset \Omega$ such that the balls with $y\in I$ form a covering of $\overline{\Omega}$. Because of a well-known finite covering lemma due to G. Vitali we can select from this finite covering a subset of pairwise disjoint balls $B_i:=B(y_i,h_{\Pn,\Omega})$ such that the balls $3B_i:=B(y_i,3h_{\Pn,\Omega})$, where $i=1,\dots,N$, cover $\overline{\Omega}$.

Let $f\in W_p^s(\Omega)$ with $\Vert f \Vert_{W_p^s(\Omega)} \le 1$.  By Lemma <ref>, we can replace $f$ with its extension and assume that $f\in W_p^s(\IR^d)$ with $\Vert f \Vert_{W_p^s(\IR^d)} \le C_1$, where $C_1>0$ is independent of $f$. Fix some $i\le N$ and consider the cube $Q_i$ centered at $y_i$ with radius $(3+c_2)h_{\Pn,\Omega}$.  By Lemma <ref>, we find a polynomial $\pi_i$ of degree at most $s$ such that

\begin{equation*}
\sup_{y \in Q_i} \big\vert (f-\pi_i)(y)\big\vert \le \cpoly\, h_{\Pn,\Omega}^{s-d/p} \vert f \vert_{W_p^s(Q_i)}.
\end{equation*}

For each $y\in \Omega_i:= \Omega\cap 3B_i$, we note that $u_i(y)=0$ for $x_i\not\in Q_i$, and obtain

\begin{align}
\nonumber
\big\vert (f - S_{\Pn} f)(y) \big\vert &= \big\vert (f - \pi_i)(y) - S_{\Pn}(f-\pi_i)(y) \big\vert \\
\label{eq:polyapp}
&\le \big\vert (f- \pi_i) (y)\big\vert + \Big\vert \sum_{i=1}^n (f-\pi_i)(x_i) u_i(y) \Big\vert
\le C_2\, h_{\Pn,\Omega}^{s-d/p} \vert f \vert_{W_p^s(Q_i)},
\end{align}

where $C_2=(1+c_0) \cpoly$. In particular, this yields

\[
\Vert f - S_{\Pn}(f) \Vert_{L_\infty(\Omega)}
\le C_2\,  h_{\Pn,\Omega}^{s-d/p} \vert f \vert_{W_p^s(\IR^d)},
\]

which proves the case $q=\infty$. For $p \le q<\infty$, we use $ \Omega_i\subset Q_i $ and (<ref>) to get

\[
\Vert f - S_{\Pn}(f) \Vert_{L_q(\Omega)}^q
\le \sum_{i=1}^N \int_{\Omega_i} \big\vert \big(f - S_{\Pn}(f)\big)(y) \big\vert^q {\rm d} y
\le C_2^q\sum_{i=1}^N \, h_{\Pn,\Omega}^{sq-dq/p} \vert f \vert_{W_p^s(Q_i)}^q \vol(\Omega_i),
\]

and thus, as a continuation,

\[
\Vert f - S_{\Pn}(f) \Vert_{L_q(\Omega)}^q
\le C_3\, h_{\Pn,\Omega}^{sq-dq/p+d} \sum_{i=1}^N \vert f \vert_{W_p^s(Q_i)}^q
\le C_3\, h_{\Pn,\Omega}^{sq-dq/p+d} \Big(\sum_{i=1}^N \vert f \vert_{W_p^s(Q_i)}^p\Big)^{q/p}.
\]

It remains to bound the sum on the right-hand side by a constant. A volume argument shows that there exists $M\in\IN$ such that for all $\Pn\subset\Omega$ every $x\in \IR^d$ is contained in at most $ M\in \mathbb{N} $  of the $ N $ cubes $Q_i$. To see this, note that the balls $B_i\subset Q_i$ are disjoint and of radius $h_{\Pn,\Omega}$. Therefore,

\begin{equation}\label{eq:norms-efficient}
\sum_{i=1}^N \vert f \vert_{W_p^s(Q_i)}^p
= \sum_{\vert \alpha \vert =s} \int_{\IR^d} \Big( \vert D^\alpha f(x) \vert^p \sum_{i=1}^N  \mathbf{1}_{Q_i}(x)\Big) {\rm d} x
\le M\, \vert f \vert_{W_p^s(\IR^d)}^p
\le M C_1^p
\end{equation}

and we arrive at the desired inequality.

As described in Section <ref>, the lower bound will be proven with the help of a fooling function $f_\ast$ from the unit ball of $W_p^s(\Omega)$ which has a large $L_q$-norm and is supported in the largest hole of the point set.

Proof of the lower bound of Theorem <ref> in the case $q\ge p$.
Let $\Pn\subset\Omega$ be arbitrary and choose $ x_0\in \Omega $ such that

\begin{equation} \label{eq:large-hole}
\dist(x_0,\Pn)\ge r_0 := \min\{ r ,h_{\Pn,\Omega}/2\}.
\end{equation}

Then the ball $ B(x_0,r_0)$ does not contain any point of $ \Pn $ and is a large hole in which we can place a fooling function. However, this ball need not be contained in $\Omega$ . To remedy this, we will find a ball in the intersection $\Omega\cap B(x_0,r_0)$ with radius proportional to $r_0$. This is the content of Lemma <ref> below, for which we need the following special case of <cit.>.

Every cone $C(x,\xi,r,\theta)$ contains a closed ball of radius $c_{\theta}r$ with $c_{\theta}:=\frac{\sin \theta}{1+\sin\theta}$.

With this geometric fact we obtain the following simple but useful consequence.

Let $ \Omega\subset \mathbb{R}^d $ satisfy an interior cone condition with parameters $ r $ and $ \theta $. If $ B(x,\varrho)$ is a ball with center $ x\in\Omega $ and radius $ 0<\varrho\leq r $, there is a ball $ B(y,c_{\theta}\varrho)$ contained in $\Omega\cap B(x,\varrho)$ with $c_{\theta} $ as in Lemma <ref>.

By the interior cone condition, there is a cone with apex $x$, radius $\varrho$ and angle $\theta$ such that its interior is contained in $ \Omega\cap B(x,\varrho) $. Now Lemma <ref> completes the proof.

Returning to the proof of the lower bound of Theorem <ref>, consider again the empty ball $B(x_0,r_0)$, where $r_0$ is as in (<ref>). By Lemma <ref> we find a ball $B(y, \varrho)$ with $ \varrho := c_\theta r_0, $ which is contained in $ \Omega\cap B(x_0,r_0) $.  Now, take a smooth non-negative function $ \varphi $ supported in $ B(0,1) $ with $ \varphi(0)=1 $ and consider the function $x\mapsto f_*(x)= \varphi\big(\varrho^{-1}(x-y)\big)$, which is supported in $B(y,\varrho)$.  One can easily compute the scaling properties

\begin{equation}\label{eq:scaling-LB}
\|f_*\|_{L_q(\Omega)}\asymp \varrho^{d/q}\qquad
\text{and} \qquad 	\|f_*\|_{W^s_p(\Omega)} \ls \varrho^{-s+d/p}
\end{equation}

by taking into account that $\varrho \le 1$ and $s\ge d/p$, see also the proof of <cit.>. Here, the implicit constants are independent of $\varrho$, but depend on the choice of $\varphi$. Replacing $f_*$ by its normalization  $ f_*/\|f_*\|_{W^s_p(\Omega)}$, it satisfies

\[
\|f_*\|_{W^s_p(\Omega)}\le 1, \quad
\quad\text{and}\quad
\|f_*\|_{L_q(\Omega)} \gs h_{\Pn,\Omega}^{s-d(1/p-1/q)}.
\]

This follows after inserting for $\varrho$ in (<ref>) and noting that $\varrho=c_{\theta}\min\{ r , h_{\Pn,\Omega}/2\}$ as well as that $h_{\Pn,\Omega}$ is bounded from above. Since $f_*\ge 0$, this completes the proof also for the integration problem.
$\hfill \square$

§ THE PROOF OF  THE CHARACTERIZATION IF $Q< P$

Let $\Omega,\Pn,p,q,s,r$ and $\theta$ as in the previous section but now with $q<p$.  Before we give the proof of Theorem <ref>a, we prove the auxilary results Lemma <ref>, Lemma <ref> and Proposition <ref> from Section <ref>.

For the proof of Lemma <ref> we shall need that a full-dimensional convex set satisfies an interior cone condition. This has been stated in Lemma <ref> and is a consequence of <cit.> which, in fact, holds for more general sets, which are star-shaped with respect to a ball. Here, a set is called star-shaped with respect to a ball if the line connecting any point in this ball with any point in the set itself is fully contained in it. In particular, every convex set is star-shaped with respect to any ball inside it.

Let $x\in\Omega$ and $0<\varrho\le r$. By Lemma <ref>, the set $\Omega$ contains a cone with radius $ \varrho $, apex $x$ and angle $\theta$.  Clearly, this cone is contained in $\overline{\Omega \cap B(x, \varrho )}$, which in turn is a subset of $A(x, \varrho ):=\overline{\Omega\cap Q(x, \varrho )}$.  By Lemma <ref>, there is a closed ball of radius $c_{\theta} \varrho $ in this cone and thus in $A(x, \varrho )$.  The proof is finished if we apply Lemma <ref> to the convex set $A(x, \varrho )$ since its diameter is at most $2\varrho\sqrt{d}$ and therefore we can set $\theta'=2\arcsin(c_{\theta}/4\sqrt{d})$.

Together with Lemma <ref> from Section <ref> we can deduce the proof of the local approximation result which gave rise to the notion of a good cube.

Let $Q=Q(x,\varrho)$ for some $x\in\Omega$ and $0<\varrho\le r$. By Lemma <ref> the set $ A(x,\varrho):=\overline{\Omega \cap Q}$ satisfies an interior cone condition with radius $ \varrho '=c_\theta  \varrho $ and angle $\theta'$.

Let $m\in \IN$ be the smallest integer greater than $s$ and let $c_0,c_1>0$ be as in Lemma <ref> for the parameters $\theta'$ and $m$.  We can assume without loss of generality that $c_1<1$.  We set

\begin{equation} \label{eq:cgood}
\cgood:=c_{\theta} c_{\theta'} c_1/2,
\end{equation}

where $c_{\theta'}=\frac{\sin\theta'}{1+\sin\theta'}$ is from Lemma <ref>.  Then assumption (<ref>) implies that every ball $B(y,2\cgood  \varrho )$, $y\in \Omega\cap Q$, contains a point of $\Pn$.  By Lemma <ref> applied to $A(x,\varrho)$ every ball $ B(x,2c_{\theta'}^{-1}\cgood  \varrho ), x\in \Omega\cap Q $, contains a ball $ B(y,2\cgood  \varrho )\subset A(x,\varrho)$  and therefore a point of $\Pn\cap Q$.  We thus have

\[
h_{\Pn\cap Q,\Omega\cap Q}
=\sup_{y\in \Omega\cap Q}\dist(y,\Pn\cap Q)
\leq 2c_{\theta'}^{-1} \cgood   \varrho
= c_1  \varrho '.
\]

Thus, we may apply Lemma <ref> to the point set $\Pn\cap Q$ within the compact set $A(x,\varrho)$ and obtain bounded continuous functions $u_i\colon \Omega \cap Q \to \mathbb{R}$ for $i=1,\dots,n$ with

\[
\sum_{i=1}^n |u_i(y)|\leq c_0 \qquad\text{and}\qquad \pi(y)=\sum_{i=1}^n \pi(x) u_i(y)
\]

for all $\pi\in\mathcal{P}_m^d$ and $y\in \Omega\cap Q$, where we set $u_i=0$ for $x_i \in \Pn\setminus Q$.  For any $f\in W^s_{p}(\IR^d)$, by Lemma <ref> there is a polynomial $\pi\in \mathcal{P}_m^d$ with

\[
\sup_{y\in Q} \big\vert (f-\pi)(y)\big\vert
\,\le\, \cpoly  \varrho ^{s-d/p}|f|_{W^s_{p}(Q)}.
\]

Here, we used that $\varrho\le r\le 1$. Similar to the proof of the upper bound of Theorem <ref> in the case $q\ge p$ in Section <ref>, we get for all $y\in \Omega\cap Q$ that

\begin{align*}
\Big\vert f(y) - \sum_{i=1}^n f(x_i) u_i(y) \Big\vert
& = \Big\vert (f-\pi)(y) - \sum_{i=1}^n (f-\pi)(x_i) u_{i}(y) \Big\vert\\
& \,\le\, \big\vert (f-\pi)(y) \big\vert + c_0\, \max_{x_i\in \Pn\cap Q} \big\vert (f-\pi)(x_i) \big\vert\\
& \,\le\, (1+c_0)\cpoly\,  \varrho ^{s-d/p}|f|_{W^s_{p}(Q)},
\end{align*}

as it was to be proven.

We state and prove the following justification for $r_{\Pn}(x)\le r$ for all $x\in\Omega$, which ensures the integrity of Definition <ref>.

Let $\Pn\subset\Omega$ be a non-empty finite point set. If, for some $x\in\Omega$, we can not find $\varrho\in(0,r)$ such that (<ref>), i.e.,

\[
\sup_{y\in \Omega\cap Q(x, \varrho )} \dist(y,\Pn) \le \cgood  \varrho
\]

holds, then $\|\dist(\cdot,\Pn)\|_{L_{\gamma}(\Omega)}\ge c$ for any $0<\gamma\le \infty$ and some constant $c>0$ independent of the point set $\Pn$.

Because of (<ref>) in Appendix <ref> it is sufficient to consider finite $\gamma$. By assumption we find $y\in\Omega$ with $\dist(y,\Pn)> \cgood r/2$, that is the ball $B(y,\cgood r/2)$ is empty of $\Pn$. By Lemma <ref> we find a ball $B(z,r')$ of radius $r'=c_{\theta}\cgood r/2$ contained in $\Omega\cap B(y,\cgood r/2)$. Hence, the distance function satisfies $\dist(x,\Pn)\ge r'/2$ for all $x\in B(z,r'/2)$. Raising this inequality to the power of $\gamma$ and integrating over $\Omega$ yields the desired result.

The following lemma is used to show that $Q_{\Pn}(x)$ is a good cube for every $x\in\Omega$.

Let $x\in\Omega$. Then

\[
\sup_{y\in\Omega\cap Q(x,r_{\Pn}(x))}\dist(y,\Pn) \le \cgood\,r_{\Pn}(x).
\]

Take a sequence $(\varrho_n)_{n\in\IN}\subset (0,r)$ converging from above to $r_{\Pn}(x)$ such that $Q(x,\varrho_n)$ satisfies (<ref>), that is,

\[
\sup_{y\in \Omega\cap Q(x,\varrho_n)} \dist(y,\Pn) \le \cgood\, \varrho_n.
\]

As $Q\big(x,r_{\Pn}(x)\big)\subset Q(x,\varrho_n)$ for every $n$, taking the infimum completes the proof.

Before we come to the main part of the proof of the upper bound of Theorem <ref> in the case $q<p$, we need to validate the covering by good cubes given in Proposition <ref>. As mentioned, we will make use of a Besicovitch-type covering result in <cit.>. Remark (2) directly below it allows us to consider open cubes instead of closed ones. For convenience we rephrase the statement here.

Consider a bounded set $D$ in $\IR^d$ and for each point $x\in D$ a cube $Q\big(x,r(x)\big)$ centered at this point with some radius $r(x)>0$. Then one can choose a (possibly finite) sequence among the given cubes which is a cover of $A$, can be distributed in finitely many families, each consisting of pairwise disjoint cubes, and every point of $\IR^d$ is contained in at most a constant many cubes of the sequence. These constants depend only on the dimension.

Similar to the proof we provided in <cit.> to find a suitable covering, the idea behind the proof is to iteratively subtract from $D$ a cube of maximal size.

For each point set $\Pn$, we will apply <cit.> to the bounded convex domain $\Omega$ and the collection $Q_{\Pn}(x)$ of small good cubes. In this way, we obtain a sequence $y_1,y_2,\dots$ of points belonging to $\Omega$ such that (i), (ii) and (iii) in Proposition <ref> are satisfied with possibly infinite $N$. The proof is complete if we can show that the sequence is indeed finite. This is what we show in the following using a volume argument.

Consider the families $\cQ_j, j=1,\dots,M_1$ of pairwise disjoint cubes into which the set $Q_{\Pn}(y_i),i\in\IN,$ is distributed. We show that an arbitrary such family $\cQ_{j_0}$ is finite and thus the whole collection $Q_{\Pn}(y_i),i\in\IN$. All the cubes $Q\in \cQ_{j_0}$ are pairwise disjoint and contained in the neighborhood $\Omega_r:=\{y\in\IR^d\colon \exists x \text{ with } \|x-y\|_{\infty}\le r\}$. It is sufficient to show that there is a constant $c>0$ such that $\vol(Q)\ge c$ for all of these cubes since then

\[
\#\cQ_{j_0}\, c\le \sum_{Q\in \cQ_{j_0}}\vol(Q)\le \vol(\Omega_r)
\]

implies that the family has to be of finite cardinality and that the sequence $y_1,y_2,\dots$ is in fact finite and of length $N$ for some $N\in\IN$.

We will show that in fact that there exists $c>0$ such that $\vol\big(Q_{\Pn}(x)\big)\ge c$ for every $Q_{\Pn}(x)$ with $x\in\Omega$. For this, note that any such good cube contains at least two points of $\Pn$.  In particular, for any $x\in\Omega$,

\[
0<\frac{q_{\Pn}}{\sqrt{d}}<r_{\Pn}(x)\le r,
\]

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\}$. This gives a uniform lower bound of the form $\vol\big(Q_{\Pn}(x)\big)=\big(2\,r_{\Pn}(x)\big)^d\ge c:= (2\,q_{\Pn}/\sqrt{d})^d$.

The following proof is similar to that of <cit.>.

Let $x\in \Omega$ and $Q_{\Pn}(x)=Q\big(x,r_{\Pn}(x)\big)$. By definition, $r_{\Pn}(x)$ is the infimum over all $\varrho\in (0,r)$ such that (<ref>) holds. In particular, we find a point $y\in \Omega\cap Q(x,r_{\Pn}(x)/2)$ with $\dist(y,\Pn)\ge \cgood r_{\Pn}(x)/4$ meaning that the ball $B(y,\cgood r_{\Pn}(x)/4)\subset Q_{\Pn}(x)$ is empty of $\Pn$. By Lemma <ref> applied to $\Omega$ we obtain a ball of radius $\chole r_{\Pn}(x)$ with $\chole:=c_{\theta}c/4$ which is contained in $\Omega\cap B(y,\cgood r_{\Pn}(x)/4)$. As $\cgood<1$ (see (<ref>)), this ball is also contained in $\Omega\cap Q_{\Pn}(y)$.

Let us conclude this section with the proof of our main result.

We choose $y_i\in\Omega$, $r_i:=r_{\Pn}(y_i)$, $Q_i=Q(y_i,r_i)$ for $1\le i \le N$ as in Proposition <ref>. To get a well-defined algorithm, we will make the covering disjoint by letting

\[
\Omega_i
:=(Q_i\cap\Omega)\setminus \bigcup_{j<i} \Omega_j
\]

for all $i=1,\dots, N$. That is, $\Omega$ is the disjoint union of the sets $\Omega_i\subset Q_i$.

Then, for any $x_j\in \Pn$ and $y\in \Omega_i$, we define $u_j(y)$ according to Lemma <ref>, applied to the cube $Q_i$.  This yields bounded functions $u_j\colon \Omega\to \IR$ and a linear algorithm

\[
S_{\Pn}\colon W^s_{p}(\Omega) \to L_q(\Omega), \quad S_{\Pn}(f)=\sum_{j=1}^n f(x_j) u_j.
\]

We proceed by showing that this algorithm which uses function samples at the point set $\Pn$ satisfies the required bound on the worst-case error. To this end, let $f\in W^s_{p}(\Omega)$ with $\Vert f\Vert_{W^s_{p}(\Omega)}\le 1$.  As in the proof for the case $q\ge p$, using Lemma <ref>, we may assume that $f\in W^s_{p}(\IR^d)$ with $\|f\|_{W^s_{p}(\IR^d)}\le C$. With the help of Lemma <ref> we derive the estimate

\begin{equation*}
\Vert f - S_{\Pn}(f) \Vert_{L_q(\Omega_i)}^q
\lesssim  r_i^{(s-d/p)q+d} |f|_{W^s_{p}(Q_i)}^q,\quad i=1,\dots,N.
\end{equation*}

Using this we obtain

\[
\Vert f - S_{\Pn}(f) \Vert_{L_q(\Omega)}^q
\le \sum_{i=1}^{N} \Vert f - S_{\Pn}(f) \Vert_{L_q(\Omega_i)}^q
\lesssim \sum_{i=1}^{N} r_i^{(s-d/p)q+d} |f|_{W^s_{p}(Q_i)}^q.
\]

If $p=\infty$, we use that $|f|_{W^s_{\infty}(Q_i)}\le |f|_{W^s_{\infty}(\IR^d)}\le C$ to obtain

\[
\Vert f - S_{\Pn}(f) \Vert_{L_q(\Omega)}^q
\lesssim \sum_{i=1}^{N} r_i^{sq+d}.
\]

And if $p<\infty$, we have by means of $(s-d/p)q+d=(\gamma+d)(1-q/p)$ and Hölder's inequality that

\begin{equation*}
\Vert f - S_{\Pn}(f) \Vert_{L_q(\Omega)}^q
\ls\, \sum_{i=1}^N r_i^{(\gamma+d)(1-q/p)}|f|_{W^s_{p}(Q_i)}^q
\,\le\, \bigg(\sum_{i=1}^N r_i^{\gamma+d}\bigg)^{1-q/p}
\bigg(\sum_{i=1}^N |f|_{W^s_{p}(Q_i)}^p \bigg)^{q/p}.
\end{equation*}

Since the cubes $Q_i$ form an efficient covering, we can proceed as in (<ref>) to obtain that the second factor in the previous estimate is bounded by a constant. We will show that the first factor is bounded by $\|\dist(\cdot,\Pn)\|_{L_{\gamma}(\Omega)}^{qs}$.

To this end, let $B_i:=B(z_i,\chole r_i)\subset \Omega\cap Q_i$ be the ball of radius $\chole r_i$ given by Lemma <ref> for each $i=1,\ldots,N$. Write, for every $\gamma\in (0,\infty)$,

\begin{equation} \label{eq:first-factor}
\sum_{i=1}^N r_i^{\gamma+d}
=c \sum_{i=1}^{N} r_i^{\gamma}\vol(B_i'),
\end{equation}

where $B_i':=B(z_i,\chole r_i/2)$ is the ball of half the radius which is concentric with $B_i$ and $c>0$ depends on $d$ and $\chole$. Since $B_i$ is empty of $\Pn$, the distance function satisfies the lower bound $\dist(x,\Pn)\ge \chole r_i/2$ for every $x\in B_i'$. Therefore, integrating over $B_i'$ shows that

\begin{equation} \label{eq:dist-lower-int}
(\chole r_i/2)^{\gamma}\vol(B_i')\le \int_{B_i'}\dist(x,\Pn)^{\gamma}\dd x.
\end{equation}

Combining the estimates (<ref>) and (<ref>) yields

\[
\sum_{i=1}^N r_i^{\gamma+d}
\lesssim \sum_{i=1}^{N} \int_{B_i'}\dist(x,\Pn)^{\gamma}\dd x
\le \int_{\Omega} \Big(\dist(x,\Pn)^{\gamma}\sum_{i=1}^{N}\mathbf{1}_{Q_i}(x)\Big)\dd x.
\]

Again the efficiency of the cover $Q_i,i=1,\ldots,N$, yields the required bound. Noting that $(1-q/p)=qs/\gamma$, this completes the proof.

We give now the proof of the corresponding lower bound. For this purpose we use a fooling function supported in a disjoint subset of the holes given by Proposition <ref> together with Lemma <ref>.

To begin, choose a cover by good cubes $Q_i=Q_{\Pn}(y_i)=Q(y_i,r_i)$, where $i=1,\ldots,N$, as given by Proposition <ref>. Let, for every $i=1,\ldots,N$, the ball $B_i:=B(z_i,\chole r_i)\subset \Omega\cap Q_i$ be as in Lemma <ref>.

Then, for every $j=1,\ldots, M_1$, we collect the balls $B_i,i=1,\ldots,N$, such that $Q_i$ belongs to the family $\cQ_j$ into the family $\cB_j$. Thus, each ball $B_i, i=1,\ldots,N,$ belongs to exactly one of the families $\cB_j, j=1,\ldots,M_1$ and the families themselves are pairwise disjoint. To select a suitable family, note that since a sum over some family must be at least the average over the sums over all families, there must be an index $1\le j_0\le M_1$ with

\begin{equation} \label{eq:max-avg}
\sum_{\substack{1\le i\le N\\ B_i\in \cB_{j_0}}} r_i^{\gamma+d}
\ge \frac{1}{M_1}\sum_{j=1}^{M_1}\sum_{\substack{1\le i\le N\\ B_i\in \cB_{j}}}r_i^{\gamma+d}
\end{equation}

We shall use this bound later for estimating the norm of the fooling function we consider. Consider the disjoint balls belonging to the family $\cB_{j_0}$, each of which will contain part of the support of the fooling function. Let $I_0\subset\{1,\ldots,N\}$ be the subset of indices with $B_i\in \cB_{j_0}$.  To define the fooling function we use atomic decompositions as discussed by Triebel <cit.>, see Section <ref>.

Let $K>s$ be an integer and $Q_0=Q(0,1/2)$ be the cube of sidelength $1$ which is centered at the origin. Further, let $\psi\in C^{\infty}(\IR^d)$ be non-negative with $\mathrm{supp}\, \psi\subset Q_0$ such that $\psi(0)>0$ and $\Vert D^\alpha \psi \Vert_\infty \le 1$ for all $\alpha\in\IN_0^d$ with $|\alpha|\le K$. The exact choice of the function $\psi$ is not important for our argument. Then according to Definition 13.3 in <cit.> the function

\[
\psi_{\nu m}\colon \IR^d\to\IR,\quad \psi_{\nu m}(x)
=2^{-\nu(s-d/p)}\psi(2^{\nu}x-m),\quad x\in\IR^d,\quad\text{where }\nu\in \IN_0, \ m\in \ZZ^d,
\]

is an $(s,p)_{K,-1}$-atom supported in $Q_{\nu m}$, the cube with center $2^{-\nu}m$ and sidelength $2^{-\nu}$.

Choose, for every $i\in I_0$, a point $m_i\in \ZZ^d$ and $\nu_i\in \IN_0$ with $2^{-\nu_i}\le  \sqrt{d}\,\chole r_i\le 2^{-\nu_i+1}$ such that the dyadic cube $Q_i^*=Q_{\nu_i m_i}$ is contained in $B_i$. Define the fooling function

\[
f_*:=\sum_{i\in I_0}\lambda_i \psi_i,\quad \text{where }\lambda_i:=2^{-\nu_i \beta} \text{ with }\beta=(\gamma+d)/p,
\]

which is supported in $\Omega$ and satisfies $f_*|_{\Pn}=0$. The choice $\lambda_i$ will become clear in a moment.

To estimate $\|f_*\|_{W^s_p(\Omega)}$ from above, we use Theorem 13.8 in <cit.>, which yields a constant $C>0$ depending only on $d,s,p$ such that

\begin{equation} \label{eq:atomic}
\|f_*\|_{W^s_p(\IR^d)}^p
\le C\, \|\lambda\|_{f_{pp}}^p,\quad
\text{where }\|\lambda\|_{f_{pp}}
:=\bigg(\int_{\IR^d}\Big(\sum_{i\in I_0} |\lambda_i 2^{\nu_i d/p}\mathbf{1}_{Q_i^*}(x)|^{p}\Big)\dd x\bigg)^{1/p}.
\end{equation}

Here, the symbol $f_{pp}$ denotes a (quasi-)normed space of sequences which are indexed by $\nu\in\IN_0, m\in\ZZ^d$, see <cit.>. In the sum in (<ref>), for every $x\in\IR^d$, only one summand is not equal to zero and since $\mathrm{vol}(Q_i^*)=2^{-\nu_i d}$, we have

\[
\|f_*\|_{W^s_p(\IR^d)}^p
\lesssim \sum_{i\in I_0}\int_{\IR^d}(2^{-\nu_i})^{\beta p-d}\mathbf{1}_{Q_i^*}(x)\dd x
= \sum_{i\in I_0}(2^{-\nu_i})^{\beta p}.
\]

As $\beta p=\gamma +d$ and $2^{-\nu_i}\asymp r_i$ and $\|f_*\|_{W^s_p(\Omega)}=\|f_*\|_{W^s_p(\IR^d)}$, we arrive at

\[
\|f_*\|_{W^s_p(\Omega)}^p
\lesssim \sum_{i\in I_0} r_i^{\gamma+d}.
\]

Since the balls $B_i\in \cB_{j_0}$ containing the cubes $Q_i^*$ are pairwise disjoint, a substitution shows that

\[
\|f_*\|_{L_q(\Omega)}^q
=\sum_{i\in I_0}\int_{Q_i^*}(2^{-\nu_i})^{\beta q}\psi_i(x)^q\dd x
=\sum_{i\in I_0}(2^{-\nu_i})^{\beta q+sq-d q/p+d}\int_{Q}\psi(x)^q\dd x.
\]

Since $\gamma=s(1/q-1/p)^{-1}$ we have $\beta q+sq = \gamma +d q/p$ and thus

\[
\|f_*\|_{L_q(\Omega)}^q
\asymp\sum_{i\in I_0} r_i^{\gamma+d}.
\]

From this it follows that if we replace $f_*$ by the normalized function $f_*/\|f_*\|_{W^s_p(\Omega)}$, it satisfies

\begin{equation} \label{eq:fooling-subset}
\|f_*\|_{L_q(\Omega)}
\gtrsim \Big(\sum_{i\in I_0} r_i^{\gamma+d}\Big)^{1/q-1/p}.
\end{equation}

We now employ the bound (<ref>) for the specific choice of the family $\cB_{j_0}$ to estimate

\begin{equation} \label{eq:fooling-avg}
\sum_{i\in I_0} r_i^{\gamma+d}
\ge \frac{1}{M_1}\sum_{i=1}^{N}r_i^{\gamma+d}
\ge \frac{1}{2^dM_1}\sum_{i=1}^{N}r_i^\gamma \vol(\Omega\cap Q_i),
\end{equation}

where $Q_i$ is as above. By definition, we have $\dist(x,\Pn)\le \cgood r_i$ for every $x\in \Omega\cap Q_i$. Integrating this inequality yields

\begin{equation} \label{eq:dist-upper-int}
\int_{\Omega\cap Q_i}\dist(x,\Pn)^{\gamma}\dd x
\le \cgood^{\gamma} r_i^{\gamma} \vol(\Omega\cap Q_i),\quad i=1,\ldots,N.
\end{equation}

Thus, combining the bounds (<ref>) and (<ref>) gives

\[
\sum_{i\in I_0} r_i^{\gamma+d}
\gtrsim \sum_{i=1}^{N} \int_{\Omega\cap Q_i}\dist(x,\Pn)^{\gamma}\dd x
\ge \int_{\Omega}\dist(x,\Pn)^{\gamma}\dd x
\]

since the cubes $Q_i,i=1,\dots,N$, cover $\Omega$. Inserting this into (<ref>) yields the lower bound for the $L_q$-norm of the fooling function and thus the lower bound for the $L_q$-approximation problem. Since $f_{\ast}\ge 0$, also the lower bound for the integration problem is proven.

§ OTHER FUNCTION SPACES

In this section we give a proof of Theorem <ref>. For the convenience of the reader we will give a definition of Triebel-Lizorkin spaces and also Besov spaces on bounded Lipschitz domains. We will mostly follow <cit.>. For more details see, e.g., Triebel <cit.> or DeVore and Sharpley <cit.>.

The definition of Besov and Triebel-Lizorkin spaces. We first define the Besov space $B^s_{pq}(\IR^d)$ and the Triebel-Lizorkin space $F^s_{pq}(\IR^d)$ of real-valued functions on $\IR^d$ with the help of a suitable dyadic resolution of unity of the Fourier domain. The Fourier transform maps a function $\psi\colon \IR^d\to\IR$ belonging to $S(\IR^d)$, the Schwartz space of rapidly decreasing smooth functions, to the function $\widehat{\psi}$ defined by

\[
\widehat{\psi}(\xi)
:=(2\pi)^{-d/2}\int_{\IR^d}{\rm e}^{-i\langle x,\xi\rangle}\psi(x)\dd x,\quad \xi\in\IR^d.
\]

The inverse $F^{-1}$ of $F$ acts the same way but with $-i$ replaced by $i$.

Choose $\psi\in S(\IR^d)$ with

\[
\psi(x)=1\quad \text{if}\quad \|x\|_2\le 1\qquad \text{and}\qquad \psi(x)=0 \quad \text{if}\quad \|x\|_2\ge \frac{3}{2}.
\]

If we put $\psi_0:=\psi$ and

\[
\psi_j(x)
:=\psi(2^{-j}x)-\psi(2^{-j+1}x)\quad\text{for }x\in\IR^d \text{ and }j\in\IN,
\]

then the system $(\psi_j)_{j\in\IN_0}$ forms a dyadic resolution of unity, that is $\sum_{j=1}^{\infty}\psi_j(x)=1$ for all $x\in\IR^d$. For any tempered distribution $f\in S'(\IR^d)$ its Fourier and inverse Fourier transform may be defined and the function $F^{-1}(\psi_j \widehat{f})$ can be evaluated pointwise. Thus, the following definition makes sense.

Let $s\in\IR$ and $0<q\le\infty$. For $0<p\le \infty$ define the Besov space $B^s_{pq}(\IR^d)$ as the collection of all $f\in S'(\IR^d)$ such that

\[
\|f\|_{B^s_{pq}(\IR^d)}^{\psi}
:=\Big(\sum_{j=0}^{\infty}2^{jsq}\|F^{-1}(\psi_j \widehat{f})\|_{L_p(\IR^d)}^q\Big)^{1/q}
\]

is finite. If $q=\infty$ we modify as usual by taking the $\ell_{\infty}$-norm. For $0<p<\infty$ the Triebel-Lizorkin space $F^{s}_{pq}(\IR^d)$ is given as the collection of all $f\in S'(\IR^d)$ with finite

\[
\|f\|_{F^s_{pq}(\IR^d)}^{\psi}
:=\Big\|\Big(\sum_{j=0}^{\infty}2^{jsq}|F^{-1}(\psi_j \widehat{f})(\cdot)|^q\Big)^{1/q}\Big\|_{L_p(\IR^d)}.
\]

The expression $\|\cdot\|_{A^s_{pq}(\IR^d)}^{\psi}$, where $A$ stands for either $B$ or $F$, is a quasi-norm and becomes a norm if both $p,q\ge 1$. A different choice of $\psi$ yields an equivalent (quasi-)norm, which is why $\psi$ is omitted in the notation.

On a bounded Lipschitz domain $\Omega\subset\IR^d$ one can define the space $A^s_{pq}(\Omega)$ via restriction as in (<ref>).  By definition, the space $A^s_{pq}(\Omega)$ contains distributions but an embedding theorem shows that if $s>d/p$ we have the continuous embedding $A^s_{pq}(\Omega)\hookrightarrow C_b(\Omega)$. Further, extension of these functions onto $\IR^d$ is possible if $s>d/p$. Thus, Lemma <ref> extends to these spaces. For further information consult for example Triebel's book <cit.> and see also Rychkov <cit.> for the extension theorem.

The proof of Theorem <ref>.  Let us first note that the analogues of Corollary <ref> and Corollary <ref> immediately follow if we can extend Theorem <ref>, which is what we prove in the following.

For the space $C^s(\Omega)$ with $s\in\IN$ the extension of Theorem <ref>a is already included in Section <ref>. Namely, the upper bound is immediate from the continuous embedding $C^s(\Omega) \hookrightarrow W_\infty^s(\Omega)$. For this note that all norms on the finite-dimensional space of multi-indices are equivalent. The lower bound holds since our fooling functions $f_\ast$ for $W_\infty^s(\Omega)$ are smooth and thus contained also in $C^s(\Omega)$ with an equivalent norm.

For the remaining cases, we follow the lines of the proof of Theorem <ref> as given in the previous Sections <ref> and <ref>. We will discuss the necessary changes and refrain from copying the proof.

Let $0<p,q,\tau \le \infty$ and $s\in\IR$ with $s>d/p$. We first give the proof of the upper bound of Theorem <ref> in the remaining cases, where we replace $W^s_p(\Omega)$ by

* $C^s(\Omega)$ and $s\not\in\IN$ if $p=\infty$,

* $F^{s}_{p\tau}(\Omega)$ if $p<\infty$.

Note that it suffices to consider the case $\tau=\infty$ since we have the continuous embedding $ F^s_{p\tau_1}(\Omega)\hookrightarrow F^s_{p\tau_2}(\Omega) $ for $ \tau_1\le \tau_2 $.  Everywhere in the proof of Theorem <ref> we replace $| f |_{W_p^s(\Omega)}$ by the following (quasi-)seminorms.

In the case $p=\infty$ and $s\not\in\IN$, we use the seminorm $|f|_{C^s(\Omega)}$ as defined in (<ref>).

If $p<\infty$, we use a (quasi-)seminorm which is defined via the averaged means

\[
(d_t^{M,\Omega}f)(x) :=
t^{-d}\int_{V^M_{\Omega}(x,t)}\bigl|(\Delta_{h,\Omega}^M f)(x)\bigr|\,\text{d} h,
\]

where $M:=\lfloor s+1 \rfloor$, $\Delta_{h,\Omega}^M$ is an $M^{\rm{th}}$-order difference operator restricted to $\Omega$ and $V^M_{\Omega}(x,t)$ is the set of directions $h\in\IR^d$ of length less than $t>0$ with $x+a h\in\Omega$ for all $0\le a \le M$. More precisely,

\[
\Delta_{h,\Omega}^M(f)
\begin{cases}
\Delta_{h}^M(f)&\text{if }x+lh\in\Omega\text{ for }l=0,\ldots,M,\\
\end{cases}
\]

where, for every $x,h\in\IR^d$,

\[
\Delta_{h}^M(f)
= \Delta_{h}^{1}\Delta_{h}^{M-1}(f) \quad\text{with}\quad \Delta_{h}^{1}(f):=f(x+h)-f(x).
\]

Choosing then in the case $p<\infty$ the (quasi-)seminorm

\[
|f|_{F^s_{p\infty}(\Omega)} :=
\bigg\| \sup_{0\le t \le 1}  \frac{(d_t^{M,\Omega}f)(\cdot)}{t^s} \bigg\|_{L_p(\Omega)},
\]

it is known that then

\[
F^s_{p\infty}(\Omega)=\{f\in L_{\infty}(\Omega)\colon |f|_{F^s_{p\infty}(\Omega)}<\infty\}
\]

\|\cdot \|_{L_{\max\{p,1\}}(\Omega)}+|\cdot|_{F^s_{p\infty}(\Omega)}
being an equivalent quasi-norm, see Proposition 6 in <cit.> and set $ u=1$ as well as $r=\infty $. The same is true for $\Omega=\IR^d$.

It is readily verified that these (quasi-)seminorms have the following scaling property.  If $T\colon\IR^d\to\IR^d$ is of the form $T(y)= \varrho ^{-1} (y-x)$ with $ \varrho \le 1$ and $x\in\IR^d$ and $f\in F^s_{p\infty}(\Omega)$ or $f\in C^s(\Omega)$, then

\begin{equation}\label{eq:scaling}
|f\circ T^{-1}|_{F^s_{p\infty}(Q_0)} \le  \varrho ^{s-d/p} |f|_{F^s_{p\infty}(Q)},
\qquad
|f\circ T^{-1}|_{C^s(Q_0)} =  \varrho ^{s} |f|_{C^s(Q)},\quad  \text{respectively.}
\end{equation}

As mentioned above the extension theorem in Lemma <ref> holds without changes for the spaces $F^s_{p\tau}(\Omega)$ and $C^s(\Omega)$, where we note that $C^s(\Omega)=B^s_{\infty\infty}(\Omega)$ for $s\not\in\IN$.  If we use <cit.> (for $p<\infty$) and <cit.> (for $p=\infty$) instead of <cit.> and the scaling properties (<ref>), we see that Lemma <ref> concerning polynomial approximation on cubes remains valid under the modifications of Theorem <ref>. Thus, also Lemma <ref> defies our modifications.

To complete the proof of the upper bound in both cases $q\ge p$ and $q<p$, it only remains to note that the seminorm $|\cdot |_{F^s_{p\infty}(\Omega)}$ behaves equally well with respect to an efficient covering. Analogous to (<ref>), we have

\begin{equation}\label{eq:norms-efficient-fspace}
\sum_{i=1}^N |f|^p_{F^s_{p\infty}(Q_i)}
= \int_{\mathbb{R}^d} \left(\sup_{0\le t \le 1}  \frac{(d_t^{M,Q_i}f)(x)}{t^s}\right)^p
\sum_{i=1}^N \bfone_{Q_i}(x){\rm d}x
\le c_7 |f|^p_{F^s_{p\infty}(\mathbb{R}^d)}
\le c_8
\end{equation}

since $d_t^{M,Q_i}f(x)\le d_t^{M,\mathbb{R}^d}f(x)$ for every $x\in\mathbb{R}^d$. With these preparations at hand, we may copy the proof of the upper bound in both cases $q\ge p$ and $q<p$.

Let us now discuss the lower bound. In case of $q\ge p$ we can use the same fooling function supported in a large hole. The scaling properties (<ref>) for $C^s(\IR^d)$ require a straightforward computation, and for $F^s_{p\tau}$ they may be obtained e.g. from Proposition 2.3.1/1 in Edmunds and Triebel <cit.> and the translation-invariance of the (quasi-)seminorm.

Let us therefore consider the case $q>p$ where we used an atomic decomposition which is also valid for Besov and Triebel-Lizorkin spaces. If, for $p<\infty$, we want to replace $W^s_p$ by $F^s_{p\tau}$, we have to substitute the bound (<ref>) by

\[
\|f_*\|_{F^s_{p\tau}(\IR^d)}^p
\le C\, \|\lambda\|_{f_{p\tau}}^p,\quad
\text{where }\|\lambda\|_{f_{p\tau}}
:=\bigg(\int_{\IR^d}\Big(\sum_{i\in I_0} |\lambda_i 2^{\nu_i d/p}\mathbf{1}_{Q_i^*}(x)|^{\tau}\Big)^{p/\tau}\dd x\bigg)^{1/p}.
\]

Here, $\|\cdot\|_{f_{p\tau}}$ is another sequence quasi-norm. Otherwise the proof can remain unchanged.

In the case $q<p=\infty$, where we replace $W^s_p$ by $C^s$, we use the convention that $a/\infty=0$ for any $a\in\IR$, whence $\beta=0$ and $\lambda_i=1$ for all $i\in I_0$. In this case, the fooling function is equal to

\[
:=\sum_{i\in I_0}2^{-s\nu_i}\psi(2^{\nu_i}x-m_i).
\]

The norm of this function can be bounded as follows. If $s\in\IN$, one can use the disjoint supports of the summands to see that $\|f_{*}\|_{C^s(\IR^d)}\le \sup_{x\in\IR^d}|\psi(x)|\le 1$, and if $s\not\in\IN$ we use that Theorem 13.8 in <cit.> is also valid for Besov spaces and the bound

\[
\|f_{*}\|_{C^s(\IR^d)}
\le C\,\|\lambda\|_{b_{\infty\infty}},\quad
\text{where }\|\lambda\|_{b_{\infty\infty}}:=\max_{i\in I_0}|\lambda_i|
= 1
\]

instead of $\eqref{eq:atomic}$. Here we used that if $s\not\in\IN$, then $C^s(\IR^d)=B_{\infty\infty}^s(\IR^d)$ with equivalent norms. The remainder of the proof of the lower bound requires only obvious modifications.

Note that also Theorem <ref>b extends to the spaces since $\psi$ is non-negative. See also the discussion in Section <ref>.

CHAPTER: ADDITIONAL MATERIAL FOR CHAPTER 5

In the following, we prove equality (<ref>) between the minimal Wasserstein distance to a measure supported on a point set and the distortion, identity (<ref>) for the worst-case error for Hölder functions, the extension to the normed spaces given in Proposition <ref> and Proposition <ref> stating that weights can be assumed to be normalized.

The following proof is inspired by the one for <cit.>. Recall that $\mu$ is a Borel probability measure on $\IR^d$ absolutely continuous with respect to the Lebesgue measure and that its distortion is given by (<ref>).

For the upper bound we will exhibit an explicit transference plan between the absolutely continuous measure $\mu$ and the discrete measure $\mu_{\Pn,a}$ given by (<ref>). To this end, let $T_{\Pn}\colon \IR^d\to\IR^d$ be the quantizer from (<ref>) in Section <ref> which maps $x$ to the closest point of $\Pn$ and is of the form

\[
T_{\Pn}=\sum_{i=1}^{n}x_i \bfone_{C(x_i,\Pn)},
\]

where $C(x_i,\Pn)$ is as in (<ref>).

Define the map $G_{\Pn}\colon \IR^d\to \IR^d\times \IR^d$ by $G_{\Pn}(x)=\big(x,T_{\Pn}(x)\big)$. Then the pushforward measure $\pi_{\Pn}:=\mu\circ G_{\Pn}^{-1}$ satisfies, for any Borel sets $A,B\subset\IR^d$,

\begin{align*}
\pi_{\Pn}(A\times \IR^d)
&= \mu(x\in\IR^d\colon x\in A, T_{\Pn}(x)\in \IR^d)
\pi_{\Pn}(\IR^d\times B)
&= \mu(x\in\IR^d\colon T_{\Pn}(x)\in B)
\end{align*}

where $\nu_{\Pn}:=\sum_{i=1}^{n}\mu\big(C(x_i,\Pn)\big)\delta_{x_i}$. Thus, $\pi_{\Pn}$ has marginals $\mu$ and $\nu_{\Pn}$ and belongs to $\pi(\mu,\nu_{\Pn})$.  Then, by (<ref>), the distortion is equal to

\begin{equation*}
\int_{\IR^d} \|x-T_{\Pn}(x)\|^r \dd\mu(x)
=\int_{\IR^d} \|x-y\|^r \dd\pi_{\Pn}(x,y)
\ge T_r(\mu,\nu_{\Pn})
\ge \inf_{a_1,\ldots,a_n\in\IR} T_r(\mu,\nu_{\Pn,a}),
\end{equation*}

which completes the upper bound.

For the lower bound we note that, for every $a_1,\dots,a_n\in\IR$ and every transference plan $\pi\in\pi(\mu,\nu_{\Pn,a})$,

\begin{align*}
\int_{\IR^d\times\IR^d} \|x-y\|^r \dd\pi(x,y)
&\ge \int_{\IR^d\times \Pn} \|x-y\|^r \dd\pi(x,y)\\
&\ge \int_{\IR^d\times \Pn}\min_{i=1,\dots,n} \|x-x_i\|^r \dd\pi(x,y)
= D_{\mu,\Pn,r}
\end{align*}

Taking the infimum over all couplings and then over all weights completes the proof.

Next, we deduce the expression for the minimal worst-case error of weighted algorithms for Hölder and Lipschitz functions from the proof of Theorem 5 in <cit.>.

Let $s\in (0,1)$. For the lower bound consider the fooling function $f_{\ast}:=\dist(\cdot,\Pn)^{s}$ which vanishes on $\Pn$ and has integral $\intmu(f_{\ast})=D_{\mu,\Pn,s}$.  It is a consequence of the triangle and Hölder's inequality that $|f_{\ast}|_{C^{s}(\IR^d)}\le 1$. The method of fooling functions described in Section <ref> then establishes the lower bound.

For the upper bound we note that the infimum over all weights can be bounded from above if we insert the optimal cubature rule from (<ref>), and then

\begin{align*}
\inf_{a_1,\dots,a_n\in\IR}\sup_{|f|_{C^{s}}\le 1}\Big| \intmu(f)-\sum_{i=1}^{n}f(x_i) a_i\Big|
&\le \sup_{|f|_{C^{s}}\le 1}\Big| \intmu(f)-Q_{\Pn,\mu}(f) \Big|\\
&= \sup_{|f|_{C^{s}}\le 1}\Big| \sum_{i=1}^{n}\int_{C(x_i,\Pn)}f(x)-f(x_i)\dd \mu(x) \Big|
\end{align*}

Using the triangle inequality and that $|f|_{C^{s}(\IR^d)}\le 1$ implies $|f(x)-f(x_i)|\le \|x-x_i\|_{2}^{s}$, we see that this bounded from above by the distortion $ D_{\mu,\Pn,s} $ completing the proof of the identity for $s\in (0,1)$. The modifications necessary for $s=1$ and $\lip$ are straightforward.

Let $s\in (0,1)$. For the lower bound we again choose the fooling function $f_{\ast}:=\dist(\cdot,\Pn)^s$ which satisfies $|f_{\ast}|_{C^s(D)}\le 1$. To normalize, we divide by $1+\|f_{\ast}\|_{\infty}=1+h_{\Pn,D}^s$, which yields the lower bound

\[
\ge \frac{1}{1+h_{\Pn,D}^s}\int_{D}\dist(x,\Pn)^s\dd\mu(x),
\]

where we can replace $C^s(D)$ by $\lipd$ for $s=1$. To have a constant independent of the point set $\Pn$, and also of $s$, one can use that

\[
\le \max\{1,h_{\Pn,D}\}
\le \max\{1,\diam(D)\}.
\]

For the proof of the upper bound we use the just proven identity (<ref>) and that optimal weigths are given by (<ref>). It remains to note that the infimum over arbitrary real weights is bounded from above by the infimum over weights summing to one and that the worst-case error over functions with $|f|_{C^s(\IR^d)}\le 1$ is at least as large as the worst-case error over all functions with $\|f\|_{C^s(\IR^d)}\le 1$, and analogously for $s=1$ and $\lipd$.

Let us conclude this appendix with the following proof.

Let $f\in F$ with $\|f\|_F\le 1$ be arbitrary and $Q_{\Pn,a}$ a cubatrue rule with points $\Pn=\{x_1,\ldots,x_n\}\subset D$ and weights $a=(a_1,\ldots,a_n)$. Then the cubature rule $Q_{\Pn,a^*}$ using the normalized weights $a^*$ with $a_i^*=a_i/\sum_{i=1}^{n}a_i, i=1,\ldots,n,$ satisfies

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

The first term on the right-hand side is bounded by $e(F,\intmu,Q_{\Pn,a})$ and the second term is bounded in absolute value by

\[
\Big|\sum_{i=1}^{n} (a_i^*-a_i)f(x_i)\Big|
\le C\,\Big|1-\sum_{i=1}^{n}a_i\Big|
\le C\,\|\bfone_D\|_F\, e(F,\intmu,Q_{\Pn,a})
\]

as the normalized function $\bfone_D/\|\bfone_D\|_F$ belongs to the unit ball of $F$.

CHAPTER: ADDITIONAL MATERIAL FOR CHAPTER 6

In this appendix we provide the missing proofs for Chapter <ref>. In Section <ref> we prove the lower bound of its characterization in terms of the spectral test (Theorem <ref>) and the lower bound on the spectral test (Proposition <ref>), thus completing the proof of the lower bound in Theorem <ref>.

Section <ref> contains the proofs of Lemmas <ref> and <ref> to fill in the gaps of the proof sketch for the upper bound of Theorem <ref> given in Section <ref>. Additionally, we shall give the proof behind the asymptotics in Remark <ref>.  Finally, Section <ref> contains the proof of Proposition <ref>.

Throughout, let $L$ be a $d$-dimensional lattice and $\cP(L)=L\cap [0,1)^d$ be the corresponding lattice point set. Further, let $\cH^*$ be a hyperplane covering of $L$ as in Section <ref>, where the distance between adjacent hyperplanes is maximal and equal to the spectral test $\sigma(L)$.

§ LOWER BOUNDS

By the pigeonhole principle we find a hyperplane from $\cH^*$ which contains sufficiently many points of $\cP(L)$. Since the unit cube $[0,1)^d$ has diameter $\sqrt{d}$, it can be intersected by no more than $\sqrt{d}/\sigma(L)+1$ hyperplanes from $\cH^*$. If all of them contained strictly less than

\[
\]

points of the lattice point set $\cP(L)$, this would be a contradiction to the fact that there are at most $\sqrt{d}/\sigma(L)+1$ of them and any point of $\cP(L)$ must lie on one of these hyperplanes. Therefore, we may find at least $n_{-}$ points of $\cP(L)$ lying on some hyperplane. This implies the lower bound.

Suppose now that additionally $\sigma(L)\leq 1/2$.
In order to find a suitable pair of hyperplanes such that their convex hull contains the center $(1/2,\dots,1/2)$ of the cube $[0,1)^d$, consider the one-dimensional space orthogonal to all hyperplanes in $\cH^*$ which is spanned by some $h\in L^{\bot}$. The rays emanating from the center of the cube into the opposite directions $\pm h$ hit a hyperplane of $\cH^*$ at distance at most $\sigma(L)$ from the center of the cube. In this way, we get a pair of adjacent hyperplanes $H_1,H_2\in\cH^*$ sandwiching the center of the cube with possibly one of them containing the center. Denote the collection of all hyperplanes which lie between $H_1$ and $H_2$ by $\widetilde{\cH}$ such that the interior of the convex hull of $H_1$ and $H_2$ satisfies

\[
\widetilde{C}
={\rm int}\,{\rm conv}(H_1\cup H_2)=\bigcup_{H\in\widetilde{\cH}} H.
\]

Then $C:=\widetilde{C}\cap [0,1)^d$ does not contain any point from $\cP(L)$. Since all hyperplanes in $\widetilde{\cH}$ have distance at most $\sigma(L)\leq 1/2$ from the center, <cit.> yields a constant independent of the dimension such that

\begin{equation} \label{eq:slab-lower}
\vol(C)
\geq \sigma(L) \inf_{H\in \widetilde{\cH}} \text{vol}_{d-1}(H\cap [0,1)^d)
\ge c\, \sigma(L).
\end{equation}

Consequently, the isotropic discrepancy of $\cP(L)$ is at least $c\,\sigma(L)$.

We briefly explain how the lower bound on the isotropic discrepancy in Theorem <ref> follows. If $\sigma(L)>1/2$, then we use the fact that the function $f\colon x\mapsto x/(\sqrt{d}+x), x\ge 1/2,$ is increasing and satisfies $f(1/2)=1/(2\sqrt{d}+1)$. In the other case we apply the lower bound on the spectral test in Proposition <ref> which we prove next.

Before doing that, let us recall the content of Minkowski's fundamental theorem, which states the following:

Let $L$ be a lattice in $\IR^d$. Then any convex set in $\IR^d$ which is symmetric with respect to the origin and with volume greater than $2^d \det(L)$ contains a non-zero lattice point of $L$.

See, e.g., <cit.> in the book by Hardy and Wright.

By the definition of the spectral test we need an upper bound on the shortest vector in the dual lattice $L^{\bot}$. To this end, we will apply Minkowski's theorem to $L^{\bot}$ and the ball $r\IB_2^d$ of radius $r>0$. According to Sloan and Kachoyan <cit.> (see also <cit.>) we have $\det(L^{\bot})=n$. The volume of $r\IB_2^d$ is

\[
\vol(r\IB_2^d)
=r^d \frac{\pi^{d/2}}{\Gamma(\frac{d}{2}+1)}.
\]

Hence, by Minkowski's theorem, if

\[
r^d \frac{\pi^{d/2}}{\Gamma(\frac{d}{2}+1)} > 2^d \det(L^\bot) =2^d n,
\]

i.e., if

\[
r > \frac{2}{\sqrt{\pi}} \big(\Gamma(\frac{d}{2}+1)\big)^{1/d}  n^{1/d}=:\widetilde{r}(d,n)
\]

then $r\IB_2^d$ contains a non-zero point from $L^\bot$. In other words, $L^\bot$ contains a non-zero lattice point of length at most $\widetilde{r}(d,n)$ and therefore the length of the shortest vector of $L^{\bot}$ is at most $\widetilde{r}(d,n)$ and the spectral test at least $\widetilde{r}(d,n)^{-1}$.

§ THE UPPER BOUND FOR THE CHARACTERIZATION

In the following, we introduce useful concepts from convex geometry, see, e.g., the book of Schneider <cit.> for an introduction.

Given non-empty $A,B\subseteq \mathbb{R}^d$ we define the Minkowski addition and the Minkowski difference by

\[
A+B:=\bigcup_{b\in B} (A+b)\quad \text{and}\quad A\div B:=\bigcap_{b\in B} (A-b),\text{ respectively,}
\]

where $A\pm b=\{a\pm b\colon a\in A\}$ for every $b\in B$.

Then, for all $\rho> 0$,

\begin{align*}
K+\rho \IB_2^d&=\{x\in\mathbb{R}^d\colon \dist(x,K)<\rho\},\\
K\div\rho \IB_2^d&=\{x\in K\colon \dist\big(x,K^C\big)\ge \rho\}.
\end{align*}

We define a family of convex parallel sets by

\[
\begin{cases}
K+\rho \IB_2^d& \text{for }\rho\ge 0,\\
K\div (-\rho)\IB_2^d & \text{for } \rho < 0.
\end{cases}
\]

The largest $\rho>0$ such that $K\div \rho \IB_2^d\neq\emptyset$ is given by the inradius of $K$, which is defined by $r(K):=\sup\{\rho\ge 0\colon x+\rho \IB_2^d\subseteq K \text{ for some } x\in \mathbb{R}^d\}$. As a consequence, $\vol(K_{-r(K)})=0$ and $\rho<-r(K)$ implies $K_{\rho}=\emptyset$. For $\rho> 0$ we have $K_{\rho}=K+\rho \IB_2^d$ and $K_{-\rho}=K\div \rho \IB_2^d$. Further, $K_0=K$.

Comparing the definitions we see that for any $\rho\ge 0$

\begin{equation}\label{eq:volumedifference}
\vol(K_{\rho}^+)=\vol(K_{\rho})-\vol(K) \quad\text{and}\quad \vol(K_{\rho}^-)=\vol(K)- \vol(K_{-\rho}).
\end{equation}

We will use Steiner's formula (see, e.g., Schneider <cit.>) stating that, for every $\rho\ge 0$,

\begin{equation}\label{eq:steiner}
\vol(K+\rho \IB_2^d)=\sum_{j=0}^d \binom{d}{j}W_j(K)\rho^j,
\end{equation}

where $W_j(K)$ is the $j$-th quermassintegral of $K$. As a mixed volume, it is monotone with respect to set inclusion, i.e., it satisfies $W_j(K_1)\le W_j(K_2)$ for $j=0,\ldots, d$, whenever $K_1\subseteq K_2$ are convex bodies. Note that $W_0(K)=\vol(K)$ and $d\, W_1(K)$ is the surface area of $K$.

We shall need a result noted by Hadwiger in his book <cit.>; compare also to <cit.> by Richter and Saorín Gómez who give additional references.

The function $v(\rho):=\vol(K_{\rho})$ is differentiable on $(-r(K),\infty)$ and its derivative satisfies $v'(\rho)=d\, W_1(K_{\rho})$.

From this we derive the following inequality, which will enable us to prove Lemma <ref>.

For all $\rho\ge 0$ we have $\vol(K_{\rho}^+)\ge \vol(K_{\rho}^-).$

Using (<ref>), this inequality can be written as $v(\rho)-v(0)\ge v(0)-v(-\rho)$. Suppose first that $0<\rho\le r(K)$. Lemma <ref> and the mean value theorem yield some $\rho_1\in (0,\rho)$ and $\rho_2\in (-\rho,0)$ such that

\[
\frac{v(\rho)-v(0)}{\rho}=v'(\rho_1) \quad \text{and}\quad \frac{v(0)-v(-\rho)}{\rho}=v'(\rho_2).
\]

Since $K_{\rho_2}\subseteq K_{\rho_1}$ and the quermassintegral $W_1(\cdot)$ is monotone, we have $v'(\rho_1)\ge v'(\rho_2)$. This completes the proof in this case.

If $\rho=0$, we have equality by definition, and if $\rho>r(K)$, the monotonicity of the volume yields $v\big(r(K)\big)\le v(\rho)$, and thus from the previously established case $\rho=r(K)$ it follows that

\[
v(\rho)-v(0)\ge v\big(r(K)\big)-v(0)\ge v(0)-v\big(-r(K)\big)=v(0)-v(-\rho)
\]

since $v\big(-r(K)\big)=v(-\rho)=0$. By means of
(<ref>) this completes the proof.

If $\rho=0$, there is nothing to show and thus assume $\rho\in (0,1]$ from now on. Lemma <ref> implies that $\max\{\vol(K_{\rho}^+),\vol(K_{\rho}^-)\}= \vol(K_{\rho}^+)$ and it remains to estimate the latter. By Steiner's formula (<ref>) we have

\[
\vol(K_{\rho}^+)=\vol(K_{\rho})-\vol(K)=\sum_{j=1}^d \binom{d}{j} W_j(K) \rho^j.
\]

The monotonicity of the quermassintegrals yields

\[
\vol(K_{\rho}^+)\le \sum_{j=1}^d \binom{d}{j} W_j([0,1]^d) \rho^j
\]

with equality for $K=[0,1]^d$. According to e.g. Lotz, McCoy, Nourdin, Peccati and Tropp <cit.> it is a classical fact that for $j=0,1,\ldots, d$ the $j$-th intrinsic volume $V_j([0,1]^d)$ of the unit cube equals $\binom{d}{j}$. The relation to the quermassintegrals is given by $\binom{d}{j}W_j([0,1]^d)=\kappa_jV_{d-j}([0,1]^d),$ where $\kappa_j$ is the $j$-dimensional volume of the unit ball of $(\mathbb{R}^j,\|\cdot\|_2)$. Together with the symmetry of the binomial coefficients, this implies $W_j([0,1]^d)=\kappa_j$. Therefore, as $\rho\le 1$, we have

\[
\vol(K_{\rho}^+)\le \rho\sum_{j=1}^d \binom{d}{j}\kappa_j \rho^{j-1} \le \rho\sum_{j=1}^d\binom{d}{j}\kappa_j.
\]

Using the fact that $\kappa_j\le \kappa_5=8\pi^2/15\le 2^3$ for every $ j\in \IN$ and that $\sum_{j=0}^d \binom{d}{j}=2^d$ completes the proof of Lemma <ref>.

We finish the proof of the upper bound of Theorem <ref> with the following proof of the estimate on the diameter of a cell with respect to an LLL-reduced basis.

Let $\fP=\{\sum_{i=1}^{d} \lambda_i b_i\colon 0\le \lambda_i<1, i=1,\ldots,d\}$ be the fundamental cell with respect to an LLL-reduced basis $b_1,\ldots,b_d$ of $L$ as given by Definition <ref>. Then, from the properties of a reduced basis it can easily be deduced, see, e.g., <cit.>, that

(a) $\Vert b^{\ast}_j\Vert_2^2\leq 2^{i-j}\Vert b^{\ast}_{i}\Vert_2^2$ for $1\leq j \leq i \leq d$ and

(b) $\Vert b_i\Vert_2^2\leq 2^{d-1}\Vert b^{\ast}_i\Vert_2^2$ for $1\leq i\leq d$.

Together these estimates imply

\[
\Vert b^{\ast}_d\Vert_2\geq 2^{-(d-1)/2}\max_{1\leq i\leq d}\Vert b^{\ast}_i\Vert_2\geq 2^{-d+1}\max_{1\leq i \leq d}\Vert b\Vert_2.
\]

Using this, we bound the diameter of $\fP$ by

\[
\dia
\leq \sum_{i=1}^d \Vert b_i\Vert_2
\leq d \max_{1\leq i \leq d} \Vert b_i\Vert_2
\leq d \, 2^{d-1} \, \Vert b_d^{\ast}\Vert_2.
\]

By the Gram-Schmidt algorithm we have

\[
\Vert b_d^{\ast}\Vert_2 = \left\Vert b_d - \sum_{i=1}^{d-1} \mu_{d,j}b^{\ast}_j\right\Vert_2.
\]

That is, the length of the last vector in the Gram-Schmidt orthogonalization is the length of the projection of the vector $b_d$ onto the orthogonal complement of the subspace span$\{b^{\ast}_1,\dots,b^{\ast}_{d-1}\}=\text{span}\{b_1,...,b_{d-1}\}$ spanned by the other basis vectors. This is exactly the distance between two adjacent hyperplanes of the family of parallel hyperplanes

\[
k\, b_d+\text{span}\{b_1,...,b_{d-1}\},\quad k\in\mathbb{Z},
\]

which covers the entire lattice $L$. Therefore, since this distance cannot be larger than the spectral test, we have

\[
d\, 2^{d-1}\, \sigma(L)
\geq d\, 2^{d-1} \, \Vert b^{\ast}\Vert_2 \geq \text{diam}(\fP).
\]

This completes the proof of the upper bound of Theorem <ref>.

We give now the proof behind Remark <ref>. It was suggested by us by an anonymous reviewer when the paper <cit.> was submitted and improved our previous asymptotic estimates. The improvement of Remark <ref> can be achieved because the above upper estimate of the sum

\[
\sum_{j=1}^d\binom{d}{j}\kappa_j \quad \text{with the volumes of the unit balls } \kappa_j=  \frac{\pi^{j/2}}{\Gamma(1+j/2)}
\]

can be replaced with the following asymptotics

\begin{equation} \label{eq:subexp}
\sum_{j=1}^d {d \choose j} \frac{\pi^{j/2}}{\Gamma(1+j/2)} = {\rm e}^{\frac{3}{2}(2\pi)^{1/3}d^{2/3}+\mu(d)},
\end{equation}

where $\vert \mu(d)\vert \le c\, d^{1/3}$ for some constant $c>0$ and all $d$.

\[
a_{j}:={d \choose j} \frac{\pi^{j/2}}{\Gamma(1+j/2)} \quad \text{for } j=1,\ldots,d,
\]

it holds that $a_{j}\le a_{j+2}$ if and only if

\[
(j+1)(j+2)^{2}\le 2\pi (d-j)(d-j-1).
\]

From this one can deduce that there exists an absolute constant $C>0$ such that for each $d$ the maximal index $j_{d}$, i.e., $a_{j_{d}}=\max_{1\le j \le d}a_{j}$, satisfies $j_{d}= (2\pi)^{1/3}d^{2/3} + \mu_{0}(d)$  with $\vert \mu_{0}(d)\vert\le  C\, d^{1/3}$.

Using Stirling's formula for the Gamma function stating that

\begin{equation} \label{eq:stirling}
\Gamma(x)=\sqrt{\frac{2\pi}{x}} \left(\frac{x}{{\rm e}}\right)^x {\rm e}^{\mu_{1}(x)},\quad
\text{where }0< \mu_{1}(x) < \frac{1}{12 x}\text{ for all }x>0,
\end{equation}

and the asymptotics

\[
d(d-1)\cdots (d-j+1)=d^{j}{\rm e}^{-(j^{2}/2d)\big(1+\mu_{2}(j/d)\big)}\quad \text{for } j=1,\ldots,d,
\]

where $\mu_{2}(x)\to 0$ if $x\to 0$, we compute

\[
a_{j}=\frac{\sqrt{2}}{\pi j}\frac{d^{j}(2\pi)^{j/2}}{j^{3j/2}}{\rm e}^{3j/2-(j^{2}/2d)\big(1+\mu_{2}(j/d)\big)-\mu_{1}(j)-\mu_{1}(j/2)}\quad \text{for } j=1,\ldots,d.
\]

Inserting $j=j_{d}$ gives

\[
a_{j_{d}}={\rm e}^{\frac{3}{2}(2\pi)^{1/3}d^{2/3}+\mu_{3}(d)}
\]

with $\vert \mu_{3}(d)\vert\le C'\, d^{1/3}$ for some $C'>0$ and all $d$. Finally, using $a_{j_{d}}\le \sum_{j=1}^{d} a_{j}\le d\, a_{j_{d}}$ proves the statement.

§ PROOF OF PROPOSITION 6.13

Hölder's inequality implies

\[
\|\dist\big(\cdot,\mathcal{P}(L)\big)\|_{L_{\gamma}([0,1)^d)}\le \|\dist\big(\cdot,\mathcal{P}(L)\big)\|_{L_{\infty}([0,1)^d)},
\]

and therefore it suffices to prove the lower bound for $\gamma \in (0,\infty)$  and the upper for $\gamma=\infty$.

We start with the proof of the lower bound and let $\gamma\in (0,\infty)$ be arbitrary. Take a hyperplane covering $\cH^*$ of $L$ as in the beginning of Section <ref> with distance $\sigma(L)$ between adjacent hyperplanes. For $t\in (0,1/2)$ consider the set

\[
A_t:=\bigg\{x\in [0,1)^d \ \colon \ \dist\bigg(x,\bigcup_{H\in\cH^*}H\bigg)\ge t \, \sigma(L)\,\bigg\}.
\]

As the family $\cH^*$ covers the lattice $L$, we have $\mathcal{P}(L)\subseteq \bigcup_{H\in\cH^*}H$, and thus for $x\in A_t$ it holds that $\dist\big(x,\mathcal{P}(L)\big)\ge t\, \sigma(L)$. Taking powers and integrals on both sides yields

\[
\int_{[0,1)^d}\dist\big(x,\mathcal{P}(L)\big)^{\gamma}\,{\rm d}x\ge  t^{\gamma} \, \sigma(L)^{\gamma} \, \vol(A_t).
\]

For establishing the lower bound it suffices to find $t_d>0$ such that $\vol(A_{t_d})\ge 1/2$. To this end, we show that for some $t_d>0$ the complement $B_{t}:=[0,1)^d\backslash A_{t}$ satisfies $\vol(B_{t_d})\le 1/2$.

For any $t>0$, we first decompose the set $B_t$ into the disjoint union $B_t=\bigcup_{H\in\cH^*} S_t(H),$
where we let

\[
S_t(H):=\{x\in [0,1)^d \ \colon \ \dist(x,H)< t\, \sigma(L)\}.
\]

Consequently, we have $\vol(B_t)=\sum_{H\in\cH^*} \vol\big(S_t(H)\big)$.

For any $t>0$, at most $\sqrt{d}/\sigma(L)+2$ of the sets $S_t(H), H\in\cH^*,$ are non-empty, and thus only finitely many terms of the sum are non-zero. This is because the cube $[0,1)^d$ has diameter $\sqrt{d}$ and can therefore be intersected by no more than $\sqrt{d}/\sigma(L)$ hyperplanes contained in $\cH^*$. The volume of a set $S_t(H)$ is bounded by its width, which is at most $2t\,\sigma(L)$ times the quantity $\sup_H \vol_{d-1}(H\cap [0,1)^d)$, where the supremum is extended over all hyperplanes $H$ in $\IR^d$. Since $[0,1)^d$ is bounded, this supremum is bounded by some constant only depending on the dimension, call it $v_d$. This implies, since $H\in\cH^*$ can be arbitrary,

\[
\vol(B_t)\le (\sqrt{d}/\sigma(L)+2)\, 2t \,\sigma(L)\, v_d=\big(2\sqrt{d}+4\sigma(L)\big)\,v_d\, t.
\]

Using that $\sigma(L)\le \sqrt{d}$ we can choose $t_d=(12\sqrt{d}v_d)^{-1}$ such that $\vol(B_{t_d})\le 1/2$. This completes the proof of the lower bound.

We turn to the proof of the upper bound for which we have to find $C_d>0$ such that

\[
\|\dist\big(\cdot,\mathcal{P}(L)\big)\|_{L_{\infty}([0,1)^d)}\le C_d\,\sigma(L).
\]

If we choose

\[
r_0:=\frac{1}{2} \|\dist\big(\cdot,\mathcal{P}(L)\big)\|_{L_{\infty}([0,1)^d)},
\]

then there exists a ball $B(y,r_0)$ with center $y\in [0,1)^d$ and radius $r_0>0$ which is empty of points from $\mathcal{P}(L)$. We now use the fact that by Lemma <ref> in Section <ref> the cube $[0,1)^d$ satisfies an interior cone condition. Then Lemma <ref> implies that there exists a ball $B(z,r_0')$ contained in $ B(y,r_0)\cap [0,1)^d$ with $r_0'= u_d r_0$, where the quantity $u_d>0$ only depends on $d$.

Let $\fP$ be the fundamental parallelotope with respect to a LLL-reduced basis of $L$ (see Section <ref>) and fix $x\in L$ such that the translate $\fP_x=x+P$ contains the center $z$ of the ball. By Lemma <ref>, we have $\dia\le d\, 2^{d-1}\sigma(L)$.

Thus, if $\dia\le r_0'$, then we must have the inclusions $\fP_x\subset B(z,r_0')\subset [0,1)^d$ and consequently $x\in \mathcal{P}(L)\cap B(z,r_0')$. This is a contradiction to $B(y,r_0)\cap \cP(L)=\emptyset$. Therefore, we must have $\dia>r_0'\ge u_d r_0$ and

\[
\|\dist\big(\cdot,\mathcal{P}(L)\big)\|_{L_{\infty}([0,1)^d)}\le C_d\, \sigma(L),
\]

where $C_d:=d\,2^{d}u_d^{-1}$. This completes the proof of the upper bound of Proposition <ref>.$\hfill \qed$