Abstract
We study here the error of numerical integration on metric measure spaces adapted to a decomposition of the space into disjoint subsets. We consider both the error for a single given function, and the worst case error for all functions in a given class of potentials. The main tools are the classical Marcinkiewicz–Zygmund inequality and ad hoc definitions of function spaces on metric measure spaces. The same techniques are used to prove the existence of point distributions in metric measure spaces with small \(L^p\) discrepancy with respect to certain classes of subsets, for example, metric balls.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
The starting point of this research is a simplified version of Lemma 5 in [15] which gives an upper bound of higher norms of the discrepancy of a random set of points in the unit square \([0,1]^2\), treated as a torus. Let \(N=M^2\) and consider a random set of N points \(\mathcal P\) as follows: Split the unit square into N small squares \(\{S_j\}_{j=1}^N\) of area \(N^{-1}\) in the usual way. In each small square \(S_j\) there is a random point \(x_j\), uniformly distributed in the small square, independently of the distribution of all the other random points in the other small squares.
Suppose that \(\mathcal B\) is a convex set in \([0,1]^2\). Let \(\mathcal J\) denote the set af all values of j for which the small squares \(S_j\) intersect the boundary \(\partial \mathcal B\) of \(\mathcal B\). Then it is easy to see that the cardinality of \(\mathcal J\), \(|\mathcal J|\), is O(M). For each \(j\in \mathcal J\), write
and let \(\eta _j=\xi _j-\mathbb E\xi _j\). Then, \(|\eta _j|\leqslant 1\) and \(\mathbb E\eta _j=0\). Furthermore if we define the discrepancy as
then
We now want to estimate \(\mathbb E(|D[\mathcal P,\mathcal B]|^p)\) from above, where p is an even positive integer. Note first that
and so
The random variables \(\eta _j\), where \(j\in \mathcal J\), are independent because the distributions of the random points are independent of each other. If one of \(j_1,\ldots , j_p\), say \(j_i\), is different from all the others, then
It follows that the only non-zero contribution to the sum (2) comes from those terms where each of \(j_1,\ldots ,j_p\) appears more than once. It can be shown that the major contribution comes when they appear in pairs, and there are
such pairs. Bounding each of such terms \(\mathbb E(\eta _{j_1}\ldots \eta _{j_p})\) trivially by 1, we obtain the estimate
This result is the first step towards the proof of the existence of point sets with small \(L^p\) discrepancy with respect to, say, all discs in the square. Indeed, let B(x, r) be the ball centered in the point x and with radius r. Then, an application of the above estimate to the sets B(x, r) gives
and Fubini’s theorem immediately implies the existence of an N-point set \(\mathcal P\) such that
By the monotonicity of the \(L^p\) norms, one obtains these estimates for all \(p<+\infty \).
This argument can be easily extended to a very general setting. In some sense, all that one needs for the argument to work is
-
1.
a partition of the ambient space into N parts with the same measure and similar diameter (the analog of the “small squares” in the previous argument);
-
2.
a collection of sets with uniformly regular boundary, in such a way that the cardinality of the collection of indices \(\mathcal J\) can be controlled uniformly in terms of the diameter of the “small squares.”
We will therefore be able to replace the unit square with a compact Riemannian manifold, or more generally, with metric measure spaces \(\mathcal M\) having finite measure and with the property that for any integer N the space can be partitioned as required in point 1 above. By a recent result [19] this property holds under very general hypotheses.
In fact, we can replace the characteristic function of the set \(\mathcal B\) with more general functions, so that our results are actually results on numerical integration. Consider the integral
of a function \(f\left( x\right) \) over the metric measure space \(\mathcal {M}\) with finite measure \(\mathrm{d}x\) and distance between two points x and y denoted with \(|x-y|\), and the Riemann sums
where \(\left\{ x_{j}\right\} _{j=1}^{N}\) are nodes in \(\mathcal {M}\) and \(\left\{ \omega _{j}\right\} _{j=1}^{N}\) are given weights. We are interested in the rate of decay of the error
as \(N\rightarrow +\infty \). This decay depends on the smoothness of the function \(f\left( x\right) \), the weights \(\left\{ \omega _{j}\right\} _{j=1}^{N}\) and the distribution of the nodes \(\left\{ x_{j}\right\} _{j=1}^{N}\) in \(\mathcal {M}\). For references on this problem when the metric space is a torus, a sphere, or more generally a compact Riemannian manifold, see, for example, [7,8,9,10,11,12,13, 23,24,25,26,27, 31]. For some results related to metric measure spaces, see [33, 47, 48].
Here we proceed as in the situation described before for the study of the discrepancy, and partition \(\mathcal {M}\) into N disjoint measurable sets \(\mathcal {X}_{1},\ldots ,\mathcal {X}_{N}\) with positive measure, set \(\omega _{j}=\left| \mathcal {X}_{j}\right| \), where \(\left| \cdot \right| \) denotes the measure, and consider random choices of points \(x_{j}\in \mathcal {X}_{j}\).
To fix the notation we write \(\varvec{\omega }=\left( \omega _{1} ,\ldots ,\omega _{N}\right) \), \(\mathbf {x}=\left( x_{1},\ldots ,x_{N}\right) \), \(\mathbf {X}=\mathcal {X}_{1}\times \cdots \times \mathcal {X}_{N}\), \(\mathrm{d}\mathbf {x}=\frac{\mathrm{d}x_{1}}{\omega _{1}}\times \cdots \times \frac{\mathrm{d}x_{N}}{\omega _{N}}, \) and consider the probability space \(\left( \mathbf {X} ,\mathrm{d}\mathbf {x}\right) \). We also write the error as
Notice the analogy with the discrepancy (1). There will be however an important difference: In order to measure the smoothness of our functions we will use suitable Besov spaces or potential spaces adapted to this more general context and obtain estimates of \(\mathcal {E}_{\mathbf {x},{\omega }}\left( f\right) \) for functions in such spaces. The previous combinatorial argument, however, works only when the integrability exponent p is an even integer, whereas in this case in order to obtain sharp results, we need estimates that work for generic values of p. The main idea is to replace such combinatorial argument with a generalization of the classical Khintchine inequality for sums of random variables, due to Marcinkiewicz and Zygmund [34, 35]. It says that for every \(1\leqslant p <+\infty \) and for every sequence of independent random variables \(\{f_j\}_{j=1}^N\)
For the case of discrepancy, this immediately gives
We will see that one such argument can be also used to deduce estimates on the error in numerical integration. In particular, we will study two types of problems. In the first case we will focus on the worst case numerical integration error, which determines how bad the error of a given fixed quadrature rule can be when applied to all integrands whose norm has an upper bound. The function space that we will consider for this type of problem is a space of potentials: We will say that \(f\in \mathbb H^\varPhi _p(\mathcal M)\) for \(1\leqslant p\leqslant \infty \) and a suitable kernel \(\varPhi (x,y)\) defined on \(\mathcal M\times \mathcal M\) (see Sect. 2 for the precise definition) if there is a \(g\in \mathbb L^p(\mathcal M)\) such that
and its norm is \(\Vert f\Vert _{\mathbb H^{\varPhi }_p(\mathcal M)}=\inf _g\Vert g\Vert _{\mathbb L^p(\mathcal M)}\), where the infimum is taken over all g(x) which give the potential f(x). Observe that when \(\mathcal M\) is the Euclidean space \(\mathbb R^d\) and \(\varPhi (x,y)=|x-y|^{\alpha -d}\), \(0<\alpha <d\) is the Riesz kernel, then for \(1<p<\infty \) the potential space \(\mathbb H^{\varPhi }_p(\mathcal M)\) coincides with the homogeneous fractional Sobolev space \(\dot{\mathbb H}^\alpha _p(\mathbb R^d)\). The (non-homogeneous) fractional Sobolev space \({\mathbb H}^\alpha _p(\mathbb R^d)\) can be obtained similarly, via the Bessel kernel. Also, when \(\mathcal M\) is a compact Riemannian manifold, the Sobolev space \(\mathbb H^\alpha _p(\mathcal M)\) can be defined as a potential space via the Bessel kernel, see Example 6.5 here or [7] for details on this. We will show here the following
Theorem I
Let \(\mathcal {M}\) be a metric measure space with the property that there exist d and c such that for every \(y\in \mathcal {M}\) and \(r>0\),
Assume also that \(\mathcal {M}\) can be decomposed into a finite disjoint union of sets in the form \(\mathcal {M=X}_{1}\cup \cdots \cup \mathcal {X}_{N}\), with \(\omega _{j}=\left| \mathcal {X}_{j}\right| \approx N^{-1}\) and \(\delta _{j}={\text {diam}}\left( \mathcal {X}_{j}\right) \approx N^{-1/d}\). Assume that for some \(0<\alpha <d\)
Finally, assume that \(1<p\leqslant +\infty \), \(1/p+1/q=1\), and \(d/p<\alpha <d\). Then
The first observation is that the Bessel kernel on a compact Riemannian manifold satisfies the hypotheses required by this theorem. In fact, the particular case given by the case \(\mathcal M\) a compact Riemannian manifold, \(\varPhi \) the Bessel kernel, \(\alpha <d/2+1\), and \(p=2\) had been proved in [7, Theorem 2.7] (see also [13, Theorem 24] for the case of the sphere).
We also show that under rather natural hypotheses on the space \(\mathcal M\) and on the kernel \(\varPhi \), the estimates from above hold from below as well.
Theorem II
Let \(\mathcal {M}\) be a metric measure space with the property that there exist H, K, and d such that for every \(y\in \mathcal {M} \) and \(0<r<r_{0}\),
Assume also that \(\mathcal {M}\) can be decomposed into a finite disjoint union of sets in the form \(\mathcal {M=X}_{1}\cup \cdots \cup \mathcal {X}_{N}\), with \(\omega _{j}=\left| \mathcal {X}_{j}\right| \approx N^{-1}\) and \(\delta _{j}={\text {diam}}\left( \mathcal {X}_{j}\right) \approx N^{-1/d} \). Suppose that there exists \(0<\alpha <d\), such that for any \(j=1,\ldots ,N\) and any \(z\in \mathcal {X}_{j}\), and for any y such that \({\text {dist}}\left( y,\mathcal {X}_{j}\right) \geqslant 2\delta _{j}\),
Suppose also that for any \(y\in M\), the function \(x\mapsto \varPhi \left( x,y\right) \) is continuous in \(x\ne y\). Finally, assume that \(1<p\leqslant +\infty \), \(1/p+1/q=1\), and \(d/p<\alpha <d\). Then
Once again, it should be observed that the Bessel kernel on a compact Riemannian manifold satisfies the hypotheses in the above theorem, and that the particular case given by the case where \(\mathcal M\) is the sphere, \(\varPhi \) the Bessel kernel, and \(p=2\) is contained in [13, Theorems 24 and 25].
In order to understand the two above results it could be useful to recall the following result [7, Theorem 2.16]: Let \(\mathcal M\) be a compact Riemannian manifold. For every \(1\leqslant p\leqslant \infty \) and \(\alpha >d/p\) there exists \(c>0\) such that for every distribution of points \(\mathbf x=\{x_j\}_{j=1}^N\) and weights \(\mathbf \omega =\{\omega _j\}_{j=1}^N\), one has
In other words, the worst case error for any quadrature rule cannot have a better decay than \(N^{-\alpha /d}\). Thus, Theorem I says that a random choice of points \(x_j\in \mathcal X_j\), \(j=1,\ldots ,N\), gives the best possible decay for the worst case error in \(\mathbb H^\alpha _p(\mathcal M)\) when \(d/2<\alpha <d/2+1\), while Theorem II says that when \(\alpha \geqslant d/2+1\) the stratification strategy does not lead, on average, to quadrature rules with the desired decay \(N^{-\alpha /d}\) of the worst case error in \(\mathbb H^\alpha _p(\mathcal M)\).
By the above-mentioned result in [19] on the partitioning of \(\mathcal M\) into N regions of equal measure and small diameter, under the hypotheses on \(\mathcal M\) contained in Theorem II (see Sect. 5), the above Theorems I and II apply with equal weights, that is \(\omega _j=|\mathcal M|/N\) for all \(j=1,\ldots ,N\). In [11] and [13] a sequence of point configurations on the sphere that gives the best possible decay \(N^{-\alpha /d}\) for the worst case error in the equal weight case has been called a Quasi Monte Carlo (QMC) design sequence for \(\mathbb H^\alpha _p(\mathcal M)\).
We would like to emphasize that all the cited results in [7] and [13] are based on Hilbert space techniques (\(p=2\)), while we were able to obtain \(\mathbb L^p\) integrability results thanks to the Marcinkiewicz–Zygmund inequality. Moreover, we work in the more general setting of metric measure spaces, and some of the results are new even in the particular case of compact Riemannian manifolds.
Concerning the non-Hilbert space setting, we mention here that when \(\mathcal M\) is the d-dimensional sphere, \(1\le p\le +\infty \), and \(\alpha >d/p\), the existence of QMC design sequences for \(\mathbb H^\alpha _p(\mathcal M)\) has been proved with different techniques in [11].
So far, we have considered the worst case error in numerical integration, that is the error for a whole class of functions. The second type of estimate that will be discussed here concerns the numerical integration error for a given fixed function. In particular, we will consider functions in the homogeneous Hajłasz–Besov space \(\dot{\mathbb B}^\alpha _{p,\infty }(\mathcal M)\), as defined in [30]. For details on these spaces, see §3. Here we should mention that when \(0<\alpha <1\), the spaces \(\mathbb H^{\varPhi }_{p}(\mathcal M)\) as in Theorem I are embedded into \(\dot{\mathbb B}^\alpha _{p,\infty }(\mathcal M)\), and that when \(\mathcal M\) is the Euclidean space \(\mathbb R^d\) and \(0<\alpha <1\) then the spaces \(\dot{\mathbb B}^\alpha _{p,\infty }(\mathcal M)\) coincide with the classical homogeneous Besov spaces defined via Littlewood–Paley decomposition. The main result in this context is the following
Theorem III
Assume that a metric measure space \(\mathcal {M}\) can be decomposed into a finite disjoint union of sets in the form \(\mathcal {M=X} _{1}\cup \cdots \cup \mathcal {X}_{N}\), with measure \(0<\left| \mathcal {X} _{j}\right| =\omega _{j}\approx N^{-1}\) and \(0<{\text {diam}}\left( \mathcal {X}_{j}\right) \approx {N^{-1/d}}\). Then for every \(1\leqslant p\leqslant 2\) there is a constant c such that
and for every \(2\leqslant p<+\infty \) there is a constant c such that
Of course, here a random choice of points \(x_j\in \mathcal X_j\), \(j=1,\ldots ,N\) gives better estimates than those obtained in Theorem I (and better than \(N^{-\alpha /d}\)). This is natural, since in this case we are looking for point distributions which give a small error for a given integrand f, whereas in the situation described by Theorem I we were looking for point distributions which give a small error for all integrands in our space at the same time.
Theorem III and its sharpness will be discussed in Sect. 7.
We believe that our effort in the search for the minimal properties that guarantee the validity of certain results in discrepancy theory and numerical integration can be of some help towards a deeper understanding of these results, even in the classical cases. In fact, to the best of our knowledge, the above Theorems I, II, and III are new even when applied to a general compact Riemannian manifold. There has recently been some interest in this type of problems in spaces as general as those considered here, or even more. See for example [33, 39, 43,44,45] for discrepancy and numerical integration on metric spaces and [47, 48] for analysis on fractals.
The plan of the paper is the following. In Sects. 2 and 3 we introduce the appropriate Sobolev-type spaces, and we recall a few results on how these spaces relate to each other. These matters are not completely new, but can be of some help for the unfamiliar reader. In Sect. 4 we introduce in some detail the Marcinkiewicz–Zygmund inequality. In Sect. 5 we recall the above-mentioned result in [19] concerning the partitioning of a metric measure space into regions of equal measure and small diameter. In Sects. 6 and 7 we give all the details on our results on numerical integration, with examples. Finally, Sect. 8 contains our results on the \(L^p\) (and \(L^\infty \)) discrepancy that generalize (3) and (5).
2 Sobolev Spaces and Potentials on Measure Spaces
Our estimates on the worst case error described in Theorems I and II require a definition of Sobolev spaces via potentials. For a classical approach to potentials, see, for example, [46].
Definition 2.1
Let \(\mathcal {M}\) be a measure space, let \(1\leqslant p,q\leqslant +\infty \) with \(1/p+1/q=1,\) and let \(\varPhi \left( x,y\right) \) be a measurable kernel on \(\mathcal {M}\times \mathcal {M}\). Assume that for every x,
Then every function g(x) in \(\mathbb {L}^{p}\left( \mathcal {M}\right) \) has a pointwise well defined potential
The space \(\mathbb {H}_{p}^{\varPhi }\left( \mathcal {M}\right) \) is the space of all potentials of functions in \(\mathbb {L}^{p}\left( \mathcal {M}\right) \), with norm
The infimum is taken over all g(x) which give the potential f(x).
Observe that this definition does not even require a metric. Potentials can also be defined under weaker assumptions on the kernel, but the above assumptions guarantee that these potentials are defined pointwise everywhere, and this will be necessary in the sequel. In particular, when \(\mathcal {M}\) is the Euclidean space \(\mathbb {R}^{d}\) and \(\varPhi \left( x,y\right) =\left| x-y\right| ^{\alpha -d}\) with \(0<\alpha <d\) is the Riesz kernel, then \(\mathbb {H}_{p}^{\varPhi }\left( \mathcal {M}\right) \) is the homogeneous fractional Sobolev space \(\dot{\mathbb {H}}_{p}^{\alpha }\left( \mathbb {R}^{d}\right) \). However, the cases \(p=1\) and \(p=+\infty \) require some extra care. For interesting examples of generalized potential spaces, see, for example, [29].
3 Besov and Triebel–Lizorkin Spaces on Metric Measure Spaces
Our estimates in Theorem III require a definition of Sobolev spaces, more appropriately Besov or Triebel–Lizorkin spaces, via upper gradients. Let \(\mathcal {M}\) be a metric measure space, that is, a metric space equipped with a positive Borel measure. With a small abuse of notation we denote by \(\left| \mathcal {X}\right| \) the measure of a measurable set \(\mathcal {X}\) and by \(\left| x-y\right| \) the distance between two points x and y. We will often denote with B(x, r) the open balls \(\{y\in \mathcal M:|x-y|<r\}\) with center x and radius r. Simple examples are Riemannian manifolds, or not necessarily smooth surfaces in a Euclidean space with the inherited measure and distance. In [22] Hajłasz has given a purely metric definition of a Sobolev space: A measurable function f(x) is in the Sobolev space \(\mathbb {W}_{p}^{1}\left( \mathcal {M}\right) \), \(1\leqslant p\leqslant +\infty \), if there exists a non-negative function \(g\left( x\right) \) in \(\mathbb {L}^{p}\left( \mathcal {M}\right) \) such that for almost every \(x,y\in \mathcal {M}\),
For example, it is proved in [22] that in Euclidean spaces one can choose as an upper gradient g(x) a suitable multiple of the Hardy–Littlewood maximal function of the gradient \(\nabla f\left( x\right) \).
The following is a natural generalization of upper gradient and associated Sobolev space.
Definition 3.1
Let \(\mathcal {M}\) be a metric measure space and \(\varphi \left( t\right) \) a non-negative increasing function in \(t\geqslant 0\). A measurable non-negative function \(g\left( x\right) \) is a \(\varphi \)-gradient of a measurable function \(f\left( x\right) \) if there exists a set \(\mathcal {N} \) with measure zero such that for all x and y in \(\mathcal {M{\setminus }N}\),
Definition 3.2
A measurable function f(x) is in the Hajłasz–Sobolev space \(\dot{\mathbb {M}}_{p}^{\varphi }\left( \mathcal {M}\right) ,\)\(0<p\leqslant +\infty \), if it has a \(\varphi \)-gradient in \(L^{p}\left( \mathcal {M}\right) \). We set
The infimum is taken over all \(\varphi \)-gradients \(g\left( x\right) \) of \(f\left( x\right) \).
In [22] Hajłasz proved that when \(\varphi (t)=t\), \(1<p\le +\infty \) and \({\mathcal M}=\mathbb R^d\), then this space coincides with the classical homogeneous Sobolev space \(\dot{\mathbb H}^{1}_p\left( \mathbb R^d\right) \). The above definition has been extended by Koskela et al. [30] who have defined Besov and Triebel–Lizorkin spaces on a general metric measure space. In particular they proved that, when \(\varphi (t)=t^\alpha \) with \(0<\alpha <1\) and \({\mathcal M}=\mathbb R^d\), then the space \(\dot{\mathbb {M}}_{p}^{\varphi }\left( \mathcal {M}\right) \) is larger than the classical fractional Sobolev space, and it coincides with the homogeneous Triebel–Lizorkin space \(\dot{\mathbb F}^{\alpha }_{p,\infty }\left( \mathbb R^d\right) \).
What follows is in the spirit of the definitions of Besov and Triebel–Lizorkin spaces in [30]. In order to define these spaces one needs to introduce families of gradients localized at different scales.
Definition 3.3
Let \(\mathcal {M}\) be a metric measure space and \(\varphi \left( t\right) \) a non-negative increasing function in \(t\geqslant 0\). Let \(n_{0}=\log _{2}\left( {\text {diam}}\left( \mathcal {M}\right) \right) \), possibly infinity. A sequence of non-negative measurable functions \(\left\{ g_{n}\left( x\right) \right\} _{-n_{0} }^{+\infty }\) is a \(\varphi \)-gradient for a measurable function \(f\left( x\right) \) if there exists a set \(\mathcal {N}\) with measure zero such that for all x and y in \(\mathcal {M{\setminus }N}\) with \(\left| x-y\right| \leqslant 2^{-n}\),
Definition 3.4
A measurable function f(x) is in the Hajłasz–Triebel–Lizorkin space \(\dot{\mathbb {F}} _{p,q}^{\varphi }\left( \mathcal {M}\right) ,\)\(0<p<+\infty \) and \(0<q\leqslant +\infty \), if f(x) has a \(\varphi \)-gradient \(\left\{ g_{n}\left( x\right) \right\} \) with
The infimum of the above expression taken over all \(\varphi \)-gradients defines the semi-norm \(\left\| f\right\| _{\dot{\mathbb {F}}_{p,q}^{\varphi }\left( \mathcal {M}\right) }\).
Definition 3.5
A measurable function f(x) is in the Hajłasz–Besov space \(\dot{\mathbb {B}}_{p,q}^{\varphi }\left( \mathcal {M}\right) \), \(0<p\leqslant +\infty \) and \(0<q\leqslant +\infty \), if f(x) has a \(\varphi \)-gradient \(\left\{ g_{n}\left( x\right) \right\} \) with
The infimum of the above expression taken over all \(\varphi \)-gradients defines the semi-norm \(\left\| f\right\| _{\dot{\mathbb {B}}_{p,q}^{\varphi }\left( \mathcal {M}\right) }\).
Observe that the above spaces are homogeneous, and constant functions have semi-norms equal to zero. Also observe that when \(q=+\infty \) and \(\varphi (t)\) is doubling, that is \(\varphi (2t)\le c\varphi (t)\), then the space \(\dot{\mathbb {F}}_{p,\infty }^{\varphi }\left( \mathcal {M}\right) \) coincides with the previously defined Hajłasz–Sobolev space \(\dot{\mathbb {M}}_{p}^{\varphi }\left( \mathcal {M}\right) \). It suffices to define \(g\left( x\right) =\sup \left\{ g_{n}\left( x\right) \right\} \). In particular, the straightforward generalization of a Hajłasz–Sobolev space is a Hajłasz–Triebel–Lizorkin space.
When \(\varphi \left( t\right) =t^{\alpha }\) the above definition is nothing but the definition of Hajłasz–Besov and Hajłasz–Triebel–Lizorkin given in [30]. To be precise, the definition of \(\varphi \)-gradient in [30] requires
only for x and y with \(2^{-n-1}\leqslant \left| x-y\right| \leqslant 2^{-n}\). On the other hand, if one defines
then
for x and y with \(\left| x-y\right| \leqslant 2^{-n}\), and the semi-norms defined via \(\left\{ g_{n}\left( x\right) \right\} \) and \(\left\{ G_{n}\left( x\right) \right\} \) are equivalent. In the same paper, it is proved that when \(\mathcal {M}\) is the Euclidean space \(\mathbb {R}^{d}\) and \(\varphi \left( t\right) =t^{\alpha }\) with \(0<\alpha <1\), then the spaces \(\dot{\mathbb {B}}_{p,q}^{\varphi }\left( \mathcal {M}\right) \) and \(\dot{\mathbb {F}}_{p,q}^{\varphi }\left( \mathcal {M}\right) \) coincide with the classical Besov and Triebel–Lizorkin spaces defined via a Littlewood–Paley decomposition. See, for example, [3] for the relevant definitions.
The lemma below gives an example of a function in the spaces \(\dot{\mathbb {B}} _{p,q}^{\varphi }\left( \mathcal {M}\right) \) and \(\dot{\mathbb {F}}_{p,q}^{\varphi } \left( \mathcal {M}\right) \).
Definition 3.6
For every subset \(\mathcal {B}\) in \(\mathcal {M}\), define
For example, if \(\mathcal {M}\) is a d-dimensional Riemannian manifold and \(\mathcal {B}\) is a bounded open set with regular boundary, then \(\psi _{\mathcal {B}}\left( t\right) \approx t\), while if \(\psi _{\mathcal {B} }\left( t\right) \approx t^{\beta }\), then the boundary has Minkowski fractal dimension \(d-\beta \).
Proposition 3.7
Let \(\mathcal {B}\) be an arbitrary subset of \(\mathcal {M}\). Then
In particular, if \(\varphi \left( t\right) =t^{\alpha }\) and \(\psi _{\mathcal {B}}\left( t\right) \leqslant ct^{\beta }\), then \(\chi _{\mathcal {B}}\in \dot{\mathbb {F}}_{p,\infty }^{\varphi }\left( \mathcal {M}\right) \) for \(p\alpha <\beta \) and \(\chi _{\mathcal {B}}\in \dot{\mathbb {B}}_{p,\infty }^{\varphi } \left( \mathcal {M}\right) \) for \(p\alpha \leqslant \beta \).
Proof
It suffices to observe that a \(\varphi \)-gradient for the characteristic function \(\chi _{\mathcal {B}}\left( x\right) \) is given by
Of course, there are other possible choices for the \(\varphi \)-gradient of \(\chi _{\mathcal B}\left( x\right) \), for example,
\(\square \)
The following is an immediate consequence of the definitions.
Proposition 3.8
-
(i)
If \(q_{1}\leqslant q_{2}\) and \(\varphi _{1}\left( t\right) \leqslant \varphi _{2}\left( t\right) \), then
$$\begin{aligned} \dot{\mathbb {B}}_{p,q_{1}}^{\varphi _{1}}\left( \mathcal {M}\right) \subseteq \dot{\mathbb {B}}_{p,q_{2}}^{\varphi _{2}}\left( \mathcal {M}\right) \quad \text{ and }\quad \dot{\mathbb {F}}_{p,q_{1}}^{\varphi _{1}}\left( \mathcal {M}\right) \subseteq \dot{\mathbb {F}}_{p,q_{2}}^{\varphi _{2}}\left( \mathcal {M}\right) . \end{aligned}$$ -
(ii)
For every \(\varphi \left( t\right) \) and \(0<p\leqslant +\infty \),
$$\begin{aligned} \dot{\mathbb {B}}_{p,p}^{\varphi }\left( \mathcal {M}\right) ={ \dot{\mathbb {F}}_{p,p}^{\varphi }} \left( \mathcal {M}\right) \quad \text{ and }\quad \dot{\mathbb {F}}_{p,\infty }^{\varphi }\left( \mathcal {M}\right) \subseteq \dot{\mathbb {B}}_{p,\infty }^{\varphi }\left( \mathcal {M}\right) . \end{aligned}$$In particular, for fixed p and \(\varphi \left( t\right) \), the largest space in the scale of Hajłasz–Besov and Hajłasz–Triebel–Lizorkin spaces is \(\dot{\mathbb {B}} _{p,\infty }^{\varphi }\left( \mathcal {M}\right) \).
In the Euclidean spaces it is well known that the homogeneous potential spaces \(\dot{\mathbb {H}}_{p}^{\alpha }\left( \mathbb {R}^{d}\right) \) defined via the Riesz potentials coincide with the homogeneous Triebel–Lizorkin spaces \(\dot{\mathbb {F}} _{p,2}^{\alpha }\left( \mathbb {R}^{d}\right) \) defined via the Littlewood–Paley decomposition [3, 18]. We do not know under which assumptions on \(\varPhi \left( x,y\right) \) and \(\varphi \left( t\right) \) and \(\mathcal {M}\) the equality \(\mathbb {H}_{p}^{\varPhi }\left( \mathcal {M}\right) =\dot{\mathbb {F}} _{p,2}^{\varphi }\left( \mathcal {M}\right) \) holds. Anyhow, the following proposition guarantees a weaker embedding.
Proposition 3.9
Assume that \(\psi \left( t\right) \) is an increasing function on \(0\leqslant t<+\infty \) with \(\psi \left( 0\right) =0\), and define for \(\varepsilon >0\)
Also assume that \(\varPhi \left( x,y\right) \) is a kernel on \(\mathcal {M}\times \mathcal {M}\) with the property that for some \( C>0\)
Define the potential
Finally, define the Hardy–Littlewood maximal operator
Then,
Proof
By the hypotheses on the kernel,
The dyadic decomposition
gives
Similarly,
Finally, the dyadic decomposition
gives
\(\square \)
Corollary 3.10
With the notation of the above proposition, if \(1<p\leqslant +\infty \), then the potential space \(\mathbb {H}_{p}^{\varPhi }\left( \mathcal {M}\right) \) can be continuously embedded into \( \dot{\mathbb {F}}_{p,\infty }^{\varphi }\left( \mathcal {M}\right) \).
Proof
It suffices to recall that, due to the extra 3 in the definition of \(Mg\left( x\right) \), this maximal operator \(Mg\left( x\right) \) is bounded on \(\mathbb {L}^{p}\left( \mathcal {M}\right) \) for all \(1<p\leqslant +\infty \), even when the measure on the metric space is non-doubling. See [37]. \(\square \)
Example 3.11
If \(\varphi \left( t\right) =t^{\alpha }\) with \(0<\alpha <\varepsilon \), then
Thus, if
and if \(1<p\leqslant +\infty \) then the potential space \(\mathbb {H}_{p}^{\varPhi }\left( \mathcal {M}\right) \) can be continuously embedded into \( \dot{\mathbb {F}}_{p,\infty }^{\varphi }\left( \mathcal {M}\right) \) with \(\varphi (t)=t^\alpha \).
4 The Marcinkiewicz–Zygmund Inequality
The main ingredient in what follows is the Marcinkiewicz–Zygmund inequality for sums of independent random variables.
As is well known, the variance of the sum of independent random variables is the sum of the variances. For every sequence of independent random variables \(f_{j}\),
In fact, there is a similar result with the second moment replaced by other moments and with the equality replaced by two inequalities.
Theorem 4.1
(Marcinkiewicz–Zygmund) For every \(1\leqslant p<+\infty \), there exist positive constants \(A\left( p\right) \) and \(B\left( p\right) \) such that for every sequence \(\{f_{j}\}\) of independent random variables,
The Marcinkiewicz–Zygmund inequality is a generalization of the classical inequality of Khintchine for sums of random variables with Rademacher distribution that take values \(\pm 1\) with probability 1 / 2. For a proof, see [34] and [35], or [17].
In what follows, special attention will be paid to the constants, and \(A\left( p\right) \) and \(B\left( p\right) \) will denote the best constants in the Marcinkiewicz–Zygmund inequality. If \(\overline{A}\left( p\right) \) and \(\overline{B}\left( p\right) \) are the corresponding best constants for the Khintchine inequality, then it can be proved that
see, for example, [17]. In particular there is a positive constant c such that \(c\leqslant \overline{A}(p)\leqslant 1\), while \(\overline{B}\left( p\right) =1\) for \(1\leqslant p\leqslant 2\) and \(\overline{B}(p)=\sqrt{2}\left( \varGamma \left( ({p+1})/{2}\right) / \sqrt{\pi }\right) ^{1/p}\) for \(2\leqslant p<+\infty \); see [14] and [21].
We remark that the Marcinkiewicz–Zygmund inequality can also be extended to infinite sums of independent random variables.
From now on we will assume that \(\mathcal {M}\) is a measure space of finite measure which can be expressed as a finite union \(\mathcal {X}_{1}\cup \cdots \cup \mathcal {X}_{N}\) of disjoint sets \(\mathcal {X}_{1},\ldots ,\mathcal {X}_{N}\) with measures \(0<\left| \mathcal {X}_{j}\right| =\omega _{j}<+\infty \).
As indicated earlier, we write \(\varvec{\omega }=\left( \omega _{1} ,\ldots ,\omega _{N}\right) \), \(\mathbf {x}=\left( x_{1},\ldots ,x_{N}\right) \), \(\mathbf {X}=\mathcal {X}_{1}\times \cdots \times \mathcal {X}_{N}\) and
The error incurred in a quadrature rule with sampling points \(\mathbf {x}=\left( x_{1},\ldots ,x_{N}\right) \) and weights \(\varvec{\omega }=\left( \omega _{1},\ldots ,\omega _{N}\right) \) is the functional
The above Marcinkiewicz–Zygmund inequality has an immediate corollary that allows us to control the norm of this error.
Corollary 4.2
Let \(1\leqslant p<+\infty \). For every measurable function \(f\left( x\right) \) on \(\mathcal {M}\),
Proof
It suffices to apply the Marcinkiewicz–Zygmund inequality to the independent random variables
and observe that
and
\(\square \)
5 Diameter Bounded Equal Measure Partition of Metric Measure Spaces
In some of the results that follow we shall assume that a metric measure space \(\mathcal {M}\) can be decomposed into a finite disjoint union of sets in the form \(\mathcal {M=X}_{1}\cup \cdots \cup \mathcal {X}_{N}\), with \(\omega _{j}=\left| \mathcal {X}_{j}\right| \approx N^{-1}\) and \(\delta _{j}={\text {diam}}\left( \mathcal {X}_{j}\right) \approx N^{-1/d}\). In fact, under appropriate assumptions, Gigante and Leopardi in [19] proved the following more precise result.
Theorem 5.1
Let \(\mathcal {M}\) be a connected metric measure space with finite measure with the property that there exist positive constants d, H and K such that for every \(y\in \mathcal {M}\) and \(0<r<{\text {diam}} (\mathcal {M})\),
Then, there exist two constants \(c_{1}\) and \(c_{2}\), such that for every sufficiently large N there exists a partition \(\mathcal {M}=\mathcal {X} _{1}\cup \cdots \cup \mathcal {X}_{N}\) and points \(y_{j}\in \mathcal {X}_{j}\) with \(\left| \mathcal {X}_{j}\right| = \left| \mathcal {M} \right| /N\) and
For example, the theorem applies to all compact Riemannian manifolds. An algorithmic construction in the particular case of the 2-dimensional sphere that pays attention to the size of the constant \(c_2\) is contained in [38] (see also [32] for the extension to higher dimensions).
6 Numerical Integration in Potential Spaces
In this section we shall study the functional \(\mathcal {E}_{\mathbf {x,\omega } }\) on the potential space \(\mathbb {H}_{p}^{\varPhi }\left( \mathcal {M}\right) \). Let
be the norm of this functional, also termed worst case error, and the following lemma gives an explicit formula for it.
Lemma 6.1
Assume that a measure space \(\mathcal {M}\) can be decomposed into a finite disjoint union of sets in the form \(\mathcal {M=X}_{1}\cup \cdots \cup \mathcal {X}_{N}\), with measure \(\left| \mathcal {X} _{j}\right| =\omega _{j}>0\). Assume also that \(1\leqslant p\leqslant +\infty \), \(1\leqslant q\leqslant +\infty \), \(1/p+1/q=1\), and that for every x,
Finally, assume that
Then the functional \(\mathcal {E}_{\mathbf {x,\omega }}\) is well defined and continuous on \(H_{p}^{\varPhi }\left( \mathcal {M}\right) \), and its norm is
Proof
For simplicity assume that \(q<+\infty \), the case \(q=+\infty \) being similar. Let
be the potential of a function g(x) in \(\mathbb {L}^{p}\left( \mathcal {M} \right) \). Since
\(f\left( x\right) \) is pointwise well defined. Since
it follows from Fubini’s theorem that \(f\left( x\right) \) is integrable, and
This implies that \(\mathcal {E}_{\mathbf {x,\omega }}\left( f\right) \) is well defined. Moreover,
Taking the infimum as \(g\left( y\right) \) varies among all possible functions in \(\mathbb {L}^{p}\left( \mathcal {M}\right) \) with potential \(f\left( x\right) \), one obtains
Conversely, using the standard argument for \(L^p-L^q\) duality, set
and
Then
This implies that
\(\square \)
Theorem 6.2
Assume that a measure space \(\mathcal {M}\) can be decomposed into a finite disjoint union of sets in the form \(\mathcal {M=X}_{1}\cup \cdots \cup \mathcal {X}_{N}\), with measure \(\left| \mathcal {X} _{j}\right| =\omega _{j}>0\). Assume also that \(1\leqslant p\leqslant +\infty \), \(1\leqslant q\leqslant +\infty \), \(1/p+1/q=1\), and that for every x,
Finally, assume that
Define
and
Then for every \(1\leqslant p\leqslant +\infty \),
and for every \(1<p\leqslant +\infty \),
In particular, there exist choices of nodes \(\left\{ x_{j}\right\} \) with the property that for every function \(f\left( x\right) \) in the potential space \(\mathbb {H}_{p}^{\varPhi }\left( \mathcal {M}\right) \),
The constants \(A\left( q\right) \) and \(B\left( q\right) \) are the best constants in the Marcinkiewicz–Zygmund inequality. The constants \(\varGamma \left( \varPhi \right) \) and \(\varDelta \left( \varPhi \right) \) are related to the smoothness of the kernel \(\varPhi \left( x,y\right) \). These last constants could be estimated in terms of Sobolev norms. However, in the applications, the estimates in terms of Sobolev norms are not always optimal, and it is more convenient to keep the above complicated expressions. Finally, since \(B\left( q\right) \rightarrow +\infty \) as \(p\rightarrow 1+\), the interest of the estimate (7) is when \(p\rightarrow 1+\).
Proof
By Lemma 6.1 and the triangle inequality,
where we have used the fact that for a function depending only on \(x_j\), integration on \(\mathbf X\) coincides with integration on \(\mathcal X_j\). This gives the proof with \(\varGamma \left( \varPhi \right) \). The proof with \(\varDelta \left( \varPhi \right) \) is similar, with the crucial difference that we replace the triangle inequality with the Marcinkiewicz–Zygmund inequality. Indeed, by Corollary 4.2,
The proof for the lower bound is similar. \(\square \)
The following corollary is a slightly generalized version of Theorem I in the Introduction.
Corollary 6.3
Let \(\mathcal {M}\) be a metric measure space with the property that there exist d and c such that for every \(y\in \mathcal {M}\) and \(r>0\),
Assume also that \(\mathcal {M}\) can be decomposed into a finite disjoint union of sets in the form \(\mathcal {M=X}_{1}\cup \cdots \cup \mathcal {X}_{N}\), with \(\omega _{j}=\left| \mathcal {X}_{j}\right| \approx N^{-1}\) and \(\delta _{j}={\text {diam}}\left( \mathcal {X}_{j}\right) \approx N^{-1/d}\). Assume that for some \(\varepsilon >0\) and \(0<\alpha <d\),
for every x and y, and
if \(\left| x-y\right| \geqslant 2\left| x-z\right| \). Finally, assume that \(1<p\leqslant +\infty \), \(1/p+1/q=1\) and \(d/p<\alpha <d\). Then
Proof
The assumption \(\alpha >d/p\) ensures that the kernel \(\varPhi \left( x,y\right) \) is q integrable and satisfies the hypotheses of Theorem 6.2. It then suffices to estimate
If \({\text {dist}}\left( y,\mathcal {X}_{j}\right) \leqslant 2\delta _{j}\), then for every \(x_{j}\) in \(\mathcal {X}_{j}\),
If \({\text {dist}}\left( y,\mathcal {X}_{j}\right) \geqslant 2\delta _{j}\), then
Hence
Under the assumption that \({\text {diam}}\left( \mathcal {X}_{j}\right) \approx N^{-1/d}\), there is only a bounded number of \(\mathcal {X}_{j}\) with \({\text {dist}}\left( y,\mathcal {X}_{j}\right) \leqslant 2{\text {diam}}\left( \mathcal {X}_{j}\right) \). Hence
Moreover,
Hence
\(\square \)
The following result shows that under some natural assumptions on the kernel, the mean value estimate in the above corollary is essentially sharp, and is a slightly generalized version of Theorem II in the Introduction.
Corollary 6.4
Let \(\mathcal {M}\) be a metric measure space with the property that there exist H, K and d such that for every \(y\in \mathcal {M} \) and \(0<r<r_{0}\),
Assume also that \(\mathcal {M}\) can be decomposed into a finite disjoint union of sets in the form \(\mathcal {M=X}_{1}\cup \cdots \cup \mathcal {X}_{N}\), with \(\omega _{j}=\left| \mathcal {X}_{j}\right| \approx N^{-1}\) and \(\delta _{j}={\text {diam}}\left( \mathcal {X}_{j}\right) \approx N^{-1/d} \). Suppose that there exists \(0<\alpha <d\) and \(\varepsilon >0\), such that for any \(j=1,\ldots ,N\) and any \(z\in \mathcal {X}_{j}\), and for any y such that \({\text {dist}}\left( y,\mathcal {X}_{j}\right) \geqslant 2\delta _{j}\),
Suppose also that for any \(y\in M\), the function \(x\mapsto \varPhi \left( x,y\right) \) is continuous in \(x\ne y\). Finally, assume that \(1<p\leqslant +\infty \), \(1/p+1/q=1\) and \(d/p<\alpha <d\). Then
Proof
It follows from Lemma 6.1 that
By Corollary 4.2, this is bounded from below by
By the continuity of \(z_{j}\rightarrow \varPhi (z_{j},y)\), there exists a point \(x_{j}^{*}\), depending on y, such that
Thus
For any two positive sequences \(\left\{ \alpha _{j}\right\} \) and \(\left\{ \beta _{j}\right\} \) we clearly have
Thus if \(v_{j}\) is a point of the closure of \(\mathcal {X}_{j}\) that minimizes the distance from y,
The desired result now follows from the estimates
Indeed,
If \(\lambda \geqslant \left( 2K/H\right) ^{1/d}\), then for every center y and \(r<r_{0}/\lambda \),
This gives
\(\square \)
Example 6.5
Let \(\mathcal {M}\) be a d-dimensional compact Riemannian manifold. Let \(\left\{ \lambda ^{2}\right\} \) and \(\left\{ \varphi _{\lambda }(x)\right\} \) be the eigenvalues and a complete orthonormal system of eigenfunctions of the Laplace Beltrami operator \(\varDelta \), respectively. Every tempered distribution on \(\mathcal {M}\) has Fourier transform and series
The Bessel kernel \(B^{\alpha }(x,y)\), \(-\infty<\alpha <+\infty \), is a distribution defined by the expansion
A distribution f(x) is the Bessel potential of a distribution g(x) if
Bessel potentials of functions in \(\mathbb {L}^{p}\left( \mathcal {M}\right) \) define the fractional Sobolev space \(\mathbb {H}_{p}^{\alpha }\left( \mathcal {M}\right) \). If \(0<\alpha <d\), then the Bessel kernel satisfies the estimates
See [7, Lemmas 2.5 and 2.6]. In particular, Corollary 6.3 applies with \(\varPhi (x,y)=B^{\alpha }(x,y)\) and \(\varepsilon =1\). Indeed, using the Hadamard parametrix for the wave equation, see, for example, [6], one can prove a more precise result: there is a smooth positive function \(C\left( y\right) \) and positive constants \(\eta \) and c such that
with
It then follows that Corollary 6.4 applies also. See [13, Theorems 24 and 25] for the case of the sphere.
7 Numerical Integration in Besov Spaces
The techniques of the previous section can also be used to study the error in numerical integration from a different perspective. So far we have considered the worst case error
whereas now we will estimate the error
for a given \(f\in \dot{\mathbb {B}}_{p,\infty }^{\varphi } \left( \mathcal {M}\right) \). The following is a slightly generalized version of Theorem III in the Introduction.
Theorem 7.1
Assume that a metric measure space \(\mathcal {M}\) can be decomposed into a finite disjoint union of sets in the form \(\mathcal {M=X} _{1}\cup \cdots \cup \mathcal {X}_{N}\), with measure \(0<\left| \mathcal {X} _{j}\right| =\omega _{j}<+\infty \) and \(0<{\text {diam}}\left( \mathcal {X}_{j}\right) =\delta _{j}<+\infty \). Also let \(\varphi \left( t\right) \) be a non-negative increasing function in \(t\geqslant 0\), and let \(\dot{\mathbb {B}}_{p,\infty }^{\varphi }\left( \mathcal {M}\right) \) be the associated Besov space. Then for every \(1\leqslant p\leqslant +\infty \),
Furthermore, if \(1\leqslant p\leqslant 2\), then
and if \(2\leqslant p<+\infty \), then
Observe that the estimate (9) is of some interest only for large p. Indeed, if \(1\leqslant p\leqslant 2\), then (10) is better than (9), and if \(2\leqslant p<+\infty \) and \(B\left( p\right) \leqslant \left| \mathcal {M}\right| ^{1/2} \left( \sup \left\{ \omega _{j}^{1/2}\right\} \right) ^{-1}\), then (11) is better than (9).
In order to prove Theorem 7.1, we need a Poincaré type inequality for functions in Hajłasz–Besov spaces.
Lemma 7.2
Let \(1\leqslant p\leqslant +\infty \), let \(\mathcal {M}\) be a metric measure space, and let \(\left\{ g_{n}\left( x\right) \right\} \) be a \(\varphi \)-gradient for an integrable function \(f\left( x\right) \). Let \(\mathcal {X}\) be a measurable subset of \(\mathcal {M}\) with \(\omega =\left| \mathcal {X}\right| >0\) and \({\text {diam}}\left( \mathcal {X} \right) \leqslant 2^{-n}\), and let
Then
Proof
For almost every x and y with \(\left| x-y\right| \leqslant 2^{-n} \), we have
Then, by Hölder’s inequality, we obtain
\(\square \)
Proof of Theorem 7.1
Let \(f\in \dot{\mathbb {B}}_{p,\infty }^{\varphi }\left( \mathcal {M}\right) \), and let \(\left\{ g_{n}\left( x\right) \right\} \) be a \(\varphi \)-gradient for \(f\left( x\right) \). Choose n such that \(2^{-n-1}<\sup \delta _{j}\leqslant 2^{-n}\). Then by Lemma 7.2, we have
The proofs of (10) and (11) are similar. Indeed, by Corollary 4.2, we have
Choose n such that \(2^{-n-1}<\sup \delta _{j}\leqslant 2^{-n}\), and assume that \(1\leqslant p\leqslant 2\). By Lemma 7.2, we obtain
Similarly, if \(2\leqslant p<+\infty \), then Hölder’s inequality with indices \(p/\left( p-2\right) \) and p / 2 yields
\(\square \)
Corollary 7.3
Assume that a metric measure space \(\mathcal {M}\) can be decomposed into a finite disjoint union of sets in the form \(\mathcal {M=X}_{1}\cup \cdots \cup \mathcal {X}_{N}\), with \(\omega _{j}=\left| \mathcal {X}_{j}\right| \approx N^{-1}\) and \({\text {diam}}\left( \mathcal {X}_{j}\right) \approx N^{-1/d}\) for a suitable positive constant d. Then for every \(1\leqslant p<+\infty \) and every \(0<\varepsilon <1\), there exists a constant c with the following property. For every function \(f\left( x\right) \) in the Besov space \(\dot{\mathbb {B}}_{p,\infty }^{\varphi }\left( \mathcal {M}\right) \), \(\varphi \left( t\right) =t^{\alpha }\) and \(\alpha >0\), with probability greater than \(1-\varepsilon \), a random choice of points \(\left\{ x_{j}\right\} \) in \(\left\{ \mathcal {X}_{j}\right\} \) gives
Proof
This follows from Theorem 7.1 via Chebyshev’s inequality. \(\square \)
The following example shows that Theorem 7.1 is essentially sharp.
Example 7.4
As in Theorem 5.1, let \(\mathcal {M}\) be a metric measure space of finite measure with the property that there exist positive constants H, K, d, such that for every \(y\in \mathcal {M}\) and \(0<r<{\text {diam}} \left( \mathcal {M}\right) \),
For every N, the space \(\mathcal {M}\) can be decomposed into a finite disjoint union of sets in the form \(\mathcal {M}=\mathcal {X}_{1}\cup \cdots \cup \mathcal {X}_{N}\), with \(\omega _{j}=\left| \mathcal {X}_{j}\right| \approx N^{-1}\) and \(\delta _{j}={\text {diam}}\left( \mathcal {X} _{j}\right) \approx N^{-1/d}\). Moreover every \(\mathcal {X}_{j}\) contains a ball \(B\left( w_{j},r_{j}\right) \) of center \(w_{j}\) and radius \(r_{j}\approx \delta _{j}\). It is possible to prove that each ball \(B\left( w_{j},r_{j}\right) \) contains two disjoint balls \(B\left( y_{j},\varepsilon r_{j}\right) \) and \(B\left( z_{j},\varepsilon r_{j}\right) \), with \(\varepsilon =6^{-1}\left( 2K/H\right) ^{-1/d}\). Fix \(1\leqslant j\leqslant N\) and define
with \(\vartheta _{j}\) such that f has mean 0. Observe that \(0<\vartheta _{j}<C\) independent of N. Also note that there exist constants A and B independent of N such that
and
If \(\varphi \left( t\right) =t^{\alpha }\) with \(d/p<\alpha \leqslant 1\), and if \(w_{j}\) is the above defined point in \(\mathcal {X}_{j}\), then the function
is a \(\varphi \)-gradient of \(f\left( x\right) \). Indeed, if \(x\in \mathcal {X}_{j}\) and \(\left| x-y\right| \leqslant 2\delta _{j}\), then
while for \(x\in \mathcal {X}_{j}\) and \(\left| x-y\right| >2\delta _{j} \),
In particular,
Moreover, since f(x) has mean zero and it is supported in \(\mathcal {X}_{j}\),
Finally,
This shows that Theorem 7.1 with \(1\leqslant p\leqslant 2\) is sharp.
In order to show that the theorem is essentially sharp also for \(2<p\leqslant +\infty \), let \(f_{j}\left( x\right) \) as before and define
If \(\varphi \left( t\right) =t^{\alpha }\), then a \(\varphi \)-gradient of \(f\left( x\right) \) is given by
Indeed, if \(x,y\in \mathcal {X}_{j}\), then
If \(x\in \mathcal {X}_{i}\) and \(y\in \mathcal {X}_{j}\), with \(i\ne j\) and \(\left| x-y\right| \leqslant N^{-1/d}\), then
If \(\left| x-y\right| \geqslant N^{-1/d}\), then
This gives
Moreover, the Marcinkiewicz–Zygmund inequality gives for \(2<p<+\infty \),
Finally,
In particular, this estimate shows that Theorem 7.1 with \(2<p<+\infty \) is sharp.
When \(p=+\infty \) let \(f\left( x\right) \) and \(\left\{ y_{j}\right\} \) as before, so that \(f\left( y_{j}\right) =1\). Then
In particular, this estimate shows that Theorem 7.1 with \(p=+\infty \) is sharp.
8 Discrepancy
The following result on the expected value of the pth power of the discrepancy of a random set of points with respect to a fixed given set in a measure space extends a result in [15, Lemma 5]. The result in the latter paper concerns the case of a compact convex set in the d-dimensional unit cube, and the proof is based on the combinatorial argument described in the Introduction, which in our case is replaced by the Marcinkiewicz–Zygmund inequality.
Theorem 8.1
Assume that a metric measure space \(\mathcal {M}\) is decomposed into a finite disjoint union of sets in the form \(\mathcal {M=X} _{1}\cup \cdots \cup \mathcal {X}_{N}\), and call \(\omega _{j}=\left| \mathcal {X}_{j}\right| \) and \(\delta _{j}={\text {diam}}\left( \mathcal {X}_{j}\right) \). Let \(\mathcal {B}\) be a measurable subset of \(\mathcal {M},\) and let
If \(\mathcal {J}\) is the set of indices j such that \(\mathcal {X}_{j}\) intersects both \(\mathcal {B}\) and its complement, then the following hold:
-
(i)
For every choice of points \(\left\{ x_{j}\right\} \) in \(\left\{ \mathcal {X}_{j}\right\} ,\)
$$\begin{aligned} \left| {\displaystyle \sum _{j=1}^{N}} \omega _{j}\chi _{\mathcal {B}}\left( x_{j}\right) -\left| \mathcal {B}\right| \right| \le \psi _{\mathcal {B}}\left( \sup _{j\in \mathcal {J}}\left\{ \delta _{j}\right\} \right) . \end{aligned}$$ -
(ii)
For every \(1\leqslant p<+\infty ,\)
$$\begin{aligned} \left\{ {\displaystyle \int _{\mathbf {X}}} \left| {\displaystyle \sum _{j=1}^{N}} \omega _{j}\chi _{\mathcal {B}}\left( x_{j}\right) -\left| \mathcal {B}\right| \right| ^{p}{\mathrm{d}\mathbf {x}}\right\} ^{1/p} \le B\left( p\right) \sqrt{\sup _{j\in \mathcal {J}}\left\{ \omega _{j}\right\} \psi _{\mathcal {B}}\left( \sup _{j\in \mathcal {J}}\left\{ \delta _{j}\right\} \right) }. \end{aligned}$$
Observe that the right hand side in (ii) is better than the one in (i) when
Also observe that
For a sufficiently refined decomposition \(\{\mathcal X_j\}\) of the space, one should expect \(\sup _{j\in \mathcal {J}}\left\{ \omega _{j}\right\} \) to be much smaller than \(\psi _{\mathcal {B}}\left( \sup _{j\in \mathcal {J}}\left\{ \delta _{j}\right\} \right) \). Hence, for a fixed value of p, estimate (ii) is in general better than (i) as \(N\rightarrow +\infty \). On the other hand, recall that \(B\left( p\right) \rightarrow +\infty \) as \(p\rightarrow +\infty \), hence, for a fixed decomposition of \(\mathcal M\), estimate (i) wins for sufficiently large values of p.
Proof
The proof of (i) is elementary. For every choice of \(x_{j} \in \mathcal {X}_{j}\) one has
If \(\mathcal {X}_{j}\subseteq \mathcal {B}\) or if \(\mathcal {B}\cap \mathcal {X} _{j}=\emptyset \) then \(\omega _{j}\chi _{\mathcal {B}\cap \mathcal {X}_{j}}\left( x_{j}\right) -\left| \mathcal {B}\cap \mathcal {X}_{j}\right| =0\). Moreover, for every j,
Then, by the triangle inequality,
The proof of (ii) is similar, with the crucial difference that we replace the triangle inequality with the Marcinkiewicz–Zygmund inequality (Corollary 4.2),
\(\square \)
Theorems like the above are the main building block for the proof of the existence of point distributions with small \(L^p\) discrepancy with respect to given collections of subsets. A very general result of this type is the following.
Corollary 8.2
Assume that a metric measure space \(\mathcal {M}\) can be decomposed into a finite disjoint union of sets in the form \(\mathcal {M=X}_{1}\cup \cdots \cup \mathcal {X}_{N}\), with \(\omega _{j}=\left| \mathcal {X}_{j}\right| \approx N^{-1}\) and \(\delta _j={\text {diam}}\left( \mathcal {X}_{j}\right) \approx N^{-1/d}\). Let \({\mathbb {G}}\) be a collection of measurable subsets of \(\mathcal {M}\) with the property that there exist positive constants c and \(\beta \) such that for all sets \(\mathcal {G}\in {\mathbb {G}}\)
Then for any finite positive measure \(\mu \) on any sigma algebra on \({\mathbb {G}}\), and for every \(1\leqslant p<+\infty \) there exists a constant C and a choice of points \(\left\{ x_{j}\right\} \) in \(\left\{ \mathcal {X}_{j}\right\} \) such that
Proof
By point (ii) of Theorem 8.1,
This implies that there exists an \(\mathbf x\in \mathbf X\) such that the thesis of the theorem holds. \(\square \)
We emphasize that under the hypotheses of Corollary 5.1 the required decomposition exists, and it is always possible to take all \(\omega _j\) equal to \(|\mathcal M|N^{-1}\). The corollary has several possible applications. We now examine a few particular cases, starting with the isotropic discrepancy (the discrepancy with respect to convex sets) in the unit cube \([0,1]^{d}\). For interesting phenomena concerning stratified sampling in the unit cube, see [16].
Corollary 8.3
Let \(1\leqslant p<+\infty \), and let \(\mu \) be a finite positive measure on a sigma algebra on the collection \({\mathcal {K}}^{d}_{u}\) of all convex sets of the unit cube \([0,1]^{d}.\) For any integer N there exists a distribution of points \(\{x_{j}\}_{j=1}^{N}\) in \([0,1]^{d}\) such that
Proof
It suffices to show that Corollary 8.2 applies with \(\beta =1\). First of all, the unit cube can be decomposed into a finite disjoint union of sets in the form \(\mathcal {M=X}_{1}\cup \cdots \cup \mathcal {X}_{N}\), with \(\omega _{j}=\left| \mathcal {X}_{j}\right| = N^{-1}\) and \(\delta _j={\text {diam}}\left( \mathcal {X}_{j}\right) \approx N^{-1/d}\). See, for example, Theorem 5.1. It then suffices to observe that for all convex sets K the uniform estimate \(\psi _{K}(t)\leqslant 4dt\) holds. Indeed, by the coarea formula
where for \(u>0\) we define \(K_u=\{x\in K:{\mathrm {dist}}(x,\partial K)\geqslant u\}\) and for \(u<0\) we define \(K_u=\{x\in [0,1]^d:{\mathrm {dist}}(x, K)\leqslant |u|\}\), and \(|\cdot |_{d-1}\) is the \((d-1)\)-dimensional Hausdorff measure. It is a well known property of convex sets that all sets \(K_u\) are convex (see e.g. [42, Chap. 3]. By the Archimedean property of monotonicity with respect to inclusion of the measure of the boundary of convex sets (see [5, Property 5, page 52]), from \(K_u\subset [0,1]^d\) it follows \(|\partial K_u|_{d-1}\leqslant |\partial [0,1]^d|_{d-1}=2d.\)\(\square \)
As an explicit example of measure, one could consider any finite measure supported on the translated, rotated and dilated copies of a fixed convex set. Hence, this result includes and extends well known results on the \(L^{p}\) discrepancy with respect to discs, or other collections of sets with “reasonable” shapes (see, for example, [15, Theorem 2D]). It is interesting to observe that if one replaces the above \(L^p\) norm with a supremum in \(K\in \mathcal {K}^{d}_{u}\), then the above result fails. Indeed, Schmidt (see [41]) proved that for any N point distribution in the unit cube there exists a convex set with discrepancy of order \(N^{-2/(d+1)}\).
It is perhaps worth mentioning some results about measures on the space of convex sets. It is well known that the set of non-empty convex compact subsets of \({\mathbb {R}}^{d},\) let us call it \(\mathcal {K}^{d},\) can be made into a metric space by introducing the Hausdorff distance
A large class of sigma finite Borel measures on \(\mathcal {K}^{d},\) which are positive on open sets of \(\mathcal {K}^{d}\) and are invariant under rigid motions, has been recently constructed by Hoffmann [28]. Just to give a rough idea, let \(\{K_{n}\}_{n=1} ^{+\infty }\) be an enumeration of all polytopes of \({\mathbb {R}}^{d}\) with vertices in rational points, and let \(\sum _{n=1}^{+\infty }\alpha _{n}<+\infty \) be a convergent series with positive terms. Then one can define the measure
where \(\delta _{K_{n}}\) is the Dirac delta centered at \(K_{n}\). This measure is supported on rational polytopes, but is positive on open sets since these rational polytopes are dense. A suitable clever modification can be made invariant under rigid motions. Nevertheless, it can be shown that there are more isometries of the space \(\mathcal {K}^{d}\) than those coming from rigid motions of \(\mathbb {R}^{d}\), and in fact it has been showed by Bandt and Baraki (see [2]) that for \(d>1\) there are no non-trivial sigma finite measures on \(\mathcal {K}^{d},\) that are invariant with respect to all isometries of the whole space \(\mathcal {K}^{d}\). Hence it seems that there is no “natural” measure on \(\mathcal {K}^{d}\).
Similar results hold in compact Riemannian manifolds. For the sake of simplicity, we state here a result on the \(L^p\) discrepancy associated to geodesic balls.
Corollary 8.4
Let \(\mathcal M\) be a compact Riemannian manifold with injectivity radius \(r_0\), and let \(0<r_1<r_0\). Denote by B(x, r) the geodesic ball centered at the point \(x\in \mathcal M\) with radius r. Then for any \(1\leqslant p<+\infty \), for any finite positive measure \(\mu \) on \(\mathcal M\times (0,r_1 )\), and for any integer N, there exists a distribution of points \(\{x_{j}\}_{j=1}^{N}\) in \(\mathcal M\) such that
Proof
As before, it suffices to show that Corollary 8.2 applies with \(\beta =1\). Indeed, \(\mathcal M\) can be decomposed into a finite disjoint union of sets in the form \(\mathcal {M=X}_{1}\cup \cdots \cup \mathcal {X}_{N}\), with \(\omega _{j}=\left| \mathcal {X}_{j}\right| =|\mathcal M| N^{-1}\) and \(\delta _j={\text {diam}}\left( \mathcal {X}_{j}\right) \approx N^{-1/d}\). See, for example, Theorem 5.1. Moreover, there exists a positive constant c such that for every geodesic ball B(x, r) with \(r<r_1\) and every \(t>0\) one has \( \psi _{B(x,r)}\left( t\right) \leqslant ct \). It clearly suffices to prove this for all \(0<t\leqslant (r_0-r_1)/2.\) Indeed, by the triangle inequality,
If \(s\leqslant 0\) then we set \(B(x,s)=\emptyset \). Finally, if \(r<r_1\) and \(t<(r_0-r_1)/2\), the exponential map diffeomorphically maps the annulus \(\overline{B}(x,r+t){\setminus }B(x,r-t)\) into the tangent space in x, and by a uniform bound on the Jacobian of the exponential map, its measure is bounded above by \(c((r+t)^d-\max \{0,r-t\}^d)\leqslant ct \). \(\square \)
We have already mentioned that the above results fail in general when one replaces the \(L^p\) norm with a supremum. Nevertheless, an extra hypothesis concerning the complexity of the collection of sets \(\mathbb G\) allows to obtain the same upper bound in the supremum case too, up to a logarithmic transgression.
Theorem 8.5
Let \(\mathcal {M}\) be a metric measure space with finite measure with the property that there exist positive constants d and \(c_{1}\), such that for every sufficiently large N there exists a partition \(\mathcal {M}=\mathcal {X} _{1}\cup \cdots \cup \mathcal {X}_{N}\) with \(\left| \mathcal {X}_{j}\right| = \left| \mathcal {M} \right| N^{-1}\) and \( {\mathrm {diam}}\left( \mathcal {X}_{j}\right) \leqslant c_{1}N^{-1/d}. \) Let \({\mathbb {G}}\) be a collection of measurable subsets of \(\mathcal {M}\) with the following two properties:
-
(i)
There exist positive constants \(c_2\) and \(\beta \) such that for all sets \(\mathcal {G}\in {\mathbb {G}}\)
$$\begin{aligned} \psi _{\mathcal {G}}\left( t\right) =\left| \left\{ x\in {\mathcal {G} }:{\text {dist}}\left\{ x,\mathcal {M}{\setminus }{\mathcal {G}}\right\} \leqslant t\right\} \right| +\left| \left\{ x\in \mathcal {M} {\setminus }{\mathcal {G}}:{\text {dist}}\left\{ x,{\mathcal {G}}\right\} \leqslant t\right\} \right| \leqslant c_2t^{\beta }. \end{aligned}$$ -
(ii)
There exist positive constants \(c_3\) and \(\gamma \) such that for all integers N and for all distributions \(\mathcal P\) of N points in \(\mathcal M\) there are at most \(c_3N^\gamma \) equivalence classes in \(\mathbb G\), where \(\mathcal G, \mathcal G'\) in \(\mathbb G\) are defined to be equivalent if \(\mathcal P\cap \mathcal G=\mathcal P\cap \mathcal G'\).
Then for any integer N there exists a distribution of points \(\{z_{j}\}_{j=1}^{N}\) such that
A few words on the above condition (ii) are perhaps necessary. We say that \(\mathbb G\) shatters a finite subset \(\mathcal P\) of N points of \(\mathcal M\) if there are exactly \(2^N\) distinct intersections of sets of \(\mathbb G\) with \(\mathcal P\). The Vapnik–Chervonenkis dimension, or VC dimension, of \(\mathbb G\) is the supremum of the sizes of all finite subsets of \(\mathcal M\) that are shattered by \(\mathbb G\). By Sauer lemma (see [40]), condition (ii) coincides with asking that the collection \(\mathbb G\) has finite VC dimension. For example, the collection of convex sets in \(\mathbb R^d\) has infinite VC dimension. Indeed a set of N points on a circle can be easily shattered with convex sets. On the other hand, the collection of balls in \(\mathbb R^d\) has VC dimension \(d+1\) (see [36, Chap. 5] for an account on this subject).
The proof that we present here follows closely the lines of the classic result for discs in the unit square, as one can find in Matoušek’s book [36].
Proof
Let \(M=N^{q}\), where q is a positive integer that will be fixed later. Consider two partitions of \(\mathcal M\) as in the hypothesis. The first is composed by the N sets \(\mathcal X_1,\ldots ,\mathcal X_N\), and the second is composed by the M sets \(\mathcal Y_1,\ldots ,\mathcal Y_M\). For any \(j=1,\ldots ,N\), define \(I_j=\{i=1,\ldots ,M:\mathcal Y_i\cap \mathcal X_j\ne \emptyset \}\) and, for all \(i\in I_j\) define
Fix a point \(y_{j,i}\) in any of the sets \(\mathcal {Y}_{j,i}\). Clearly \(\{\mathcal {Y}_{j,i}\}_{i\in I_j}\) forms a partition of \(\mathcal X_j\) and \(\mathcal {Y}_{j,i}\subset \{x\in \mathcal M:|x-y_{i,j}|<c_1M^{-1/d}\}\).
For each \(j=1,\ldots , N\), let us pick one point \(q_j\) among all the points \(y_{j,i}\) with \(i\in I_j\). This point \(q_j\) is chosen randomly with probability \({\mathbb P}[q_j=y_{j,i}]=N|\mathcal Y_{j,i}|/|\mathcal M|\), the choices being independent for distinct values of j. The discrepancy of the point distribution \(\{q_j\}_{j=1}^N\) with respect to a given \(\mathcal G\in \mathbb G\) can be estimated as follows
The second term in the above sum is deterministic and can be treated easily. By Theorem 8.1 (i) it is bounded above by
It is therefore sufficient to take \(q\geqslant d/\beta \) to obtain an estimate better than what is needed.
The other term is of a probabilistic nature. We only need to consider the values of j for which \(\mathcal X_j\) intersects both \(\mathcal G\) and \(\mathcal M\). Call this set \(\mathcal J\) and its cardinality m. Since
we have \(m\leqslant c_1^\beta c_2 N^{1-\beta /d}/|\mathcal M|\). Let us now set
and call \(F_j\) the random variable \( \chi _{\mathcal G} \left( q_{j}\right) - k_j. \) Thus we have
The variables \(F_j\) are mutually independent, and \(F_j\) takes the value \(1-k_j\) with probability \(k_j\), and \(-k_j\) with probability \(1-k_j\). Therefore for every \(\varDelta >0\) we have
(see, for example, [1, Corollary A.1.7]). Let us fix a constant \(C>0\). Then we have showed that
Finally, if \(\mathbb F\subset \mathbb G\) contains one representative for each equivalence class, then
if C is large enough. The theorem follows. \(\square \)
The next Corollary shows one possible application of the above theorem.
Corollary 8.6
Let \(\mathcal M\) be a d-dimensional compact Riemannian manifold isometrically embedded in \(\mathbb R^D\), and call \(B^D(x,r)=\{y\in \mathbb R^D:\Vert y-x\Vert <r\}\) the Euclidean D-dimensional ball of center x and radius r. Then there exist positive constants \(r_0\) and C such that for any integer N there exists a distribution of points \(\{z_{j}\}_{j=1}^{N}\in \mathcal M\) such that
Notice that, by the Nash embedding theorem, every Riemannian manifold can be isometrically embedded into some Euclidean space. In particular, if one takes as \(\mathcal M\) the d-dimensional unit sphere in \(\mathbb R^{d+1}\), then the sets \(B^{d+1}(x,r)\cap \mathcal M\) of the above corollary coincide with the usual spherical caps, and one recovers Beck’s estimate for the spherical cap discrepancy (see [4, Theorem 24D]).
Proof
It is enough to show that the collection of subsets of the form \(B^D(x,r)\cap \mathcal M\) satisfies the two hypotheses of Theorem 8.5. By compactness, there exists a positive number \(r_0\) such that for all \(0<r\leqslant r_0\) and for all \(x\in \mathcal M\), the set \(\mathcal N=\{y\in \mathcal M:\Vert x-y\Vert =r\}\) is a hypersurface of \(\mathcal M\) with uniformly bounded \((d-1)\)-dimensional volume. Furthermore, the measure of the set of points of \(\mathcal M\) with geodesic distance from \(\mathcal N\) less than or equal to t is bounded above by
where \(\mathrm{d}n\) is the \((d-1)\)-dimensional volume form on \(\mathcal N\) and f(s, n) is the (uniformly bounded) Jacobian of the exponential map of the normal bundle on \(\mathcal N\) in \(\mathcal M\) (see [20] for the details). Thus
and the first hypothesis of Theorem 8.5 holds with \(\beta =1\). Finally, as we mention before, balls in \(\mathbb R^D\) satisfy the second hypotheses of the same theorem with \(\gamma =D+1\) ([36, Chap. 5]). \(\square \)
References
Alon, N., Spencer, J.H.: The Probabilistic Method. Wiley-Interscience Series in Discrete Mathematics and Optimization, 3rd edn. Wiley, Hoboken (2008)
Bandt, C., Baraki, G.: Metrically invariant measures on locally homogeneous spaces and hyperspaces. Pac. J. Math. 121, 13–28 (1986)
Bergh, J., Löfström, J.: Interpolation Spaces. Springer, Berlin (1976)
Beck, J., Chen, W.W.L.: Irregularities of Distribution. Cambridge University Press, Cambridge (1987)
Bonnesen, T., Fenchel, W.: Theory of Convex Bodies. Translated from the German and edited by L. Boron, C. Christenson and B. Smith. BCS Associates (1987)
Brandolini, L., Colzani, L.: Decay of Fourier transforms and summability of eigenfunction expansions. Ann. Sc. Norm. Super. Pisa Cl. Sci. 29, 611–638 (2000)
Brandolini, L., Choirat, C., Colzani, L., Gigante, G., Seri, R., Travaglini, G.: Quadrature rules and distribution of points on manifolds. Ann. Sc. Norm. Super. Pisa Cl. Sci. 13, 889–923 (2014)
Brandolini, L., Chen, W.W.L., Gigante, G., Travaglini, G.: Discrepancy for randomized Riemann sums. Proc. Am. Math. Soc. 137, 3187–3196 (2009)
Brandolini, L., Colzani, L., Gigante, G., Travaglini, G.: On the Koksma–Hlawka inequality. J. Complex. 29, 158–172 (2013)
Brauchart, J.S., Dick, J.: A characterization of Sobolev spaces on the sphere and an extension of Stolarsky’s invariance principle to arbitrary smoothness. Constr. Approx. 38, 397–445 (2013)
Brauchart, J.S., Dick, J., Saff, E.B., Sloan, I.H., Wang, Y.G., Womersley, R.S.: Covering of spheres by spherical caps and worst-case error for equal weight cubature in Sobolev spaces. J. Math. Anal. Appl. 431, 782–811 (2015)
Brauchart, J.S., Hesse, K.: Numerical integration over spheres of arbitrary dimension. Constr. Approx. 25, 41–71 (2007)
Brauchart, J.S., Saff, E.B., Sloan, I.H., Womersley, R.S.: QMC design: optimal order quasi Monte Carlo integration schemes on the sphere. Math. Comput. 83, 2821–2851 (2014)
Burkholder, D.: Sharp inequalities for martingales and stochastic integrals. Astérisque 157–158, 75–94 (1988)
Chen, W.W.L.: On irregularities of distribution. III. J. Aust. Math. Soc. 60, 228–244 (1996)
Chen, W.W.L., Travaglini, G.: Deterministic and probabilistic discrepancies. Ark. Mat. 47, 273–293 (2009)
Chow, Y.S., Teicher, H.: Probability Theory. Independence, Interchangeability, Martingales. Springer, Berlin (1988)
Frazier, M., Jawerth, B., Weiss, G.: Littlewood-Paley theory and the study of function spaces. CBMS Regional Conference Series in Mathematics, 79. Published for the Conference Board of the Mathematical Sciences, Washington, DC, by the American Mathematical Society, Providence, RI (1991)
Gigante, G., Leopardi, P.: Diameter bounded equal measure partitions of Ahlfors regular metric measure spaces. Discret. Comput. Geom. 57, 419–430 (2017)
Heintze, E., Karcher, H.: A general comparison theorem with applications to volume estimates for submanifolds. Ann. Sci. Ecole Norm. Sup. (4) 11, 451–470 (1978)
Haagerup, U.: The best constant in the Khintchine inequality. Studia Math. 70, 231–283 (1981)
Hajłasz, P.: Sobolev spaces on an arbitrary metric space. Potential Anal. 5, 403–415 (1996)
Hesse, K.: A lower bound for the worst-case cubature error on spheres of arbitrary dimension. Numer. Math. 103, 413–433 (2006)
Hesse, K., Mhaskar, H.M., Sloan, I.H.: Quadrature in Besov spaces on the Euclidean sphere. J. Complex. 23, 528–552 (2007)
Hesse, K., Sloan, I.H.: Worst-case errors in a Sobolev space setting for cubature over the sphere \(S^{2}\). Bull. Aust. Math. Soc. 71, 81–105 (2005)
Hesse, K., Sloan, I.H.: Optimal lower bounds for cubature error on the sphere \(S^{2}\). J. Complex. 21, 790–803 (2005)
Hesse, K., Sloan, I.H.: Cubature over the sphere \(S^{2}\) in Sobolev spaces of arbitrary order. J. Approx. Theory 141, 118–133 (2006)
Hoffmann, L.M.: Measures on the space of convex bodies. Adv. Geom. 10, 477–486 (2010)
Hu, J., Zähle, M.: Generalized Bessel and Riesz potentials on metric measure spaces. Potential Anal. 30, 315–340 (2009)
Koskela, P., Yang, D., Zhou, Y.: Pointwise characterization of Besov and Triebel Lizorkin spaces and quasiconformal mappings. Adv. Math. 226, 3579–3621 (2011)
Kushpel, A.: Optimal cubature formulas on compact homogeneous manifolds. J. Funct. Anal. 257, 1621–1629 (2009)
Leopardi, P.: Diameter bounds for equal area partitions of the unit sphere. Electron. Trans. Numer. Anal. 35, 1–16 (2009)
Maggioni, M., Mhaskar, H.N.: Diffusion polynomial frames on metric measure spaces. Appl. Comput. Harmon. Anal. 24, 329–353 (2008)
Marcinkiewicz, J., Zygmund, A.: Sur les fonctions indépendantes. Fund. Math. 29, 60–90 (1937)
Marcinkiewicz, J., Zygmund, A.: Quelques théorèmes sur les fonctions indépendantes. Studia Math. 7, 104–120 (1938)
Matoušek, J.: Geometric discrepancy. An illustrated guide. Revised paperback reprint of the 1999 original. Algorithms and Combinatorics, 18. Springe, Berlin (2010)
Nazarov, F., Treil, S., Volberg, A.: Weak type estimates and Cotlar inequalities for Calderón-Zygmund operators on nonhomogeneous spaces. Int. Math. Res. Not. 9, 463–487 (1998)
Rakhmanov, E.A., Saff, E.B., Zhou, Y.M.: Minimal discrete energy on the sphere. Math. Res. Lett. 1(6), 647–662 (1994)
Reznikov, A., Saff, E.B.: The covering radius of randomly distributed points on a manifold. Int. Math. Res. Not. IMRN 19, 6065–6094 (2016)
Sauer, N.: On the density of families of sets. J. Comb. Theory Ser. A 13, 145–147 (1972)
Schmidt, W.M.: Irregularities of distribution IX. Acta Arith. 27, 385–396 (1975)
Schneider, R.: Convex Bodies: The Brunn–Minkowski Theory, Second Expanded Edition (Encyclopedia of Mathematics and its Applications). Cambridge University Press, Cambridge (2014)
Skriganov, M.M.: Point distributions in compact metric spaces. Mathematika 63, 1152–1171 (2017)
Skriganov, M.M.: Point distributions in compact metric spaces, II. arXiv:1701.04007
Skriganov, M.M.: Point distribution in compact metric spaces, III. Two-point homogeneous spaces. arXiv:1701.04545
Stein, E.M.: Singular Integrals and Differentiability Properties of Functions. Princeton University Press, Princeton (1970)
Strichartz, R.S.: Analysis on fractals. Not. Am. Math. Soc. 46(10), 1199–1208 (1999)
Strichartz, R.S., Usher, M.: Splines on fractals. Math. Proc. Camb. Philos. Soc. 129(2), 331–360 (2000)
Acknowledgements
The authors wish to thank Dmitriy Bilyk for several conversations concerning the results on discrepancy contained in this paper.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Brandolini, L., Chen, W.W.L., Colzani, L. et al. Discrepancy and Numerical Integration on Metric Measure Spaces. J Geom Anal 29, 328–369 (2019). https://doi.org/10.1007/s12220-018-9993-6
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12220-018-9993-6