Covering of spheres by spherical caps and worst-case error for equal weight cubature in Sobolev spaces

Johann S. Brauchart, Josef Dick, E. B. Saff, Ian H. Sloan, Yu Guang Wang, Robert S. Womersley

Introduction

In numerical analysis and approximation theory, the problem of distributing points on a sphere is fundamental. Whether one is placing weather stations to calculate global temperature averages or designing sensors for signal processing, the goal is to ensure the points are "well-spread." This paper establishes a rigorous mathematical bridge between two historically distinct ways of measuring this quality: the geometric property of "covering" and the analytic property of "integration error."

The authors demonstrate that point sets optimized for numerical integration—specifically Quasi-Monte Carlo (QMC) designs—naturally possess optimal covering properties. This means that if a set of points is good at integrating functions within a certain smoothness class, it is guaranteed to leave no large "holes" on the spherical surface.

The Dual Nature of Point Set Quality

To evaluate a set of points $X_N = \{x_1, \dots, x_N\}$ on a $d$-dimensional sphere $\mathbb{S}^d$, researchers typically look at two metrics:

  1. Geometric (Covering Radius): The covering radius $\rho(X_N)$ measures the size of the largest "hole" on the sphere. Formally, it is the maximum distance from any point on the sphere to the nearest point in $X_N$. A small covering radius indicates that the points are well-distributed geometrically.
  2. Analytic (Worst-Case Error): The worst-case error (WCE) measures how poorly a point set approximates an integral. For a given class of functions—usually a Sobolev space $W_p^s$ characterized by smoothness $s$ and norm $p$—the WCE is the maximum error of the equal-weight cubature rule over all functions in the unit ball of that space.

While a connection between these two concepts was known for specific Hilbert space settings ($p=2$), this paper provides a generalized theory for $L_p$-based Sobolev spaces, filling a significant gap in the literature.

Methodology: The "Fooling Function" and Bessel Kernels

The core of the paper’s proof relies on the construction of a "fooling function." To show that a small WCE implies a small covering radius, the authors hypothesize the existence of a large hole on the sphere. They then construct a localized "bump" function supported entirely within that hole. Because the function is zero at all points in $X_N$, the cubature rule (the weighted sum) yields zero. However, the true integral of this bump function is positive. If the WCE is small, this discrepancy must be small, which mathematically forces the hole (and thus the covering radius) to be small.

To formalize this across different Sobolev spaces, the authors utilize:

  • Bessel Kernels: These serve as the fundamental building blocks for Sobolev spaces on the sphere, allowing the authors to represent the WCE in a manageable form.
  • Bernstein-type Inequalities: The authors derive a new inequality for Bessel kernels that incorporates the mesh ratio (a measure of point set uniformity). This allows for the transfer of properties between different levels of function smoothness.
  • Spherical Harmonics: The proofs leverage the decomposition of functions into spherical harmonics, the spherical analogue of Fourier series, to handle the underlying geometry of $\mathbb{S}^d$.

Key Insights and Results

The Analytic-Geometric Bound

The paper’s primary result is encapsulated in Theorem 1.2, which provides the fundamental bound: $$\rho(X_N) \leq c_{s,d} [wce]^{1/(s+d/q)}$$ This inequality quantifies exactly how the covering radius $\rho$ shrinks as the worst-case error decreases. For the case where $p=1$, the authors deduce that QMC design sequences achieve the optimal covering order of $N^{-1/d}$.

Stability Across Function Spaces

A highly practical finding is the stability of point sets across different Sobolev spaces. The authors prove that a QMC design sequence for a space $W_p^s$ is also a design sequence for any space with the same smoothness but a larger $p'$. This suggests that a single "good" point set can be robustly applied to a variety of integration problems, even if the exact smoothness or norm of the target function is not perfectly known.

The Role of Quasi-Uniformity

The research highlights that "quasi-uniform" point sets—those where points are relatively evenly spaced and not clumped together—allow for much stronger transfers of properties between different levels of smoothness. While some results are general, the assumption of quasi-uniformity (a bounded mesh ratio) is shown to be a powerful tool in ensuring that high-smoothness designs remain effective for lower-smoothness functions.

Conclusion and Future Directions

This work solidifies the link between geometry and analysis on the sphere, proving that good integration implies good coverage. While the bounds are close to optimal, particularly when the smoothness $s$ is near $d/p$, future work may involve sharpening these constants for broader parameter ranges. Additionally, the authors suggest that the techniques developed here—specifically the Bernstein inequalities for kernels—could be extended to other compact Riemannian manifolds, potentially broadening the impact of these findings to more complex geometric domains.

Summary updated

Abstract

We prove that the covering radius of an $N$-point subset $X_N$ of the unit sphere $S^d \subset R^{d+1}$ is bounded above by a power of the worst-case error for equal weight cubature $\frac{1}{N}\sum_{\mathbf{x} \in X_N}f(\mathbf{x}) \approx \int_{S^d} f \, \mathrm{d} σ_d$ for functions in the Sobolev space $\mathbb{W}_p^s(S^d)$, where $σ_d$ denotes normalized area measure on $S^d.$ These bounds are close to optimal when $s$ is close to $d/p$. Our study of the worst-case error along with results of Brandolini et al. motivate the definition of Quasi-Monte Carlo (QMC) design sequences for $\mathbb{W}_p^s(S^d)$, which have previously been introduced only in the Hilbert space setting $p=2$. We say that a sequence $(X_N)$ of $N$-point configurations is a QMC-design sequence for $\mathbb{W}_p^s(S^d)$ with $s > d/p$ provided the worst-case equal weight cubature error for $X_N$ has order $N^{-s/d}$ as $N \to \infty$, a property that holds, in particular, for a sequence of spherical $t$-designs in which each design has order $t^d$ points. For the case $p = 1$, we deduce that any QMC-design sequence $(X_N)$ for $\mathbb{W}_1^s(S^d)$ with $s > d$ has the optimal covering property; i.e., the covering radius of $X_N$ has order $N^{-1/d}$ as $N \to \infty$. A significant portion of our effort is devoted to the formulation of the worst-case error in terms of a Bessel kernel, and showing that this kernel satisfies a Bernstein type inequality involving the mesh ratio of $X_N$. As a consequence we prove that any QMC-design sequence for $\mathbb{W}_p^s(S^d)$ is also a QMC-design sequence for $\mathbb{W}_{p^\prime}^s(S^d)$ for all $1 \leq p < p^\prime \leq \infty$ and, furthermore, if $(X_N)$ is a quasi-uniform QMC-design sequence for $\mathbb{W}_p^s(S^d)$, then it is also a QMC-design sequence for $\mathbb{W}_p^{s^\prime}(S^d)$ for all $s > s^\prime > d/p$.
BibTeX
@article{brauchart2015covering,
  author = {Johann S. Brauchart and Josef Dick and E. B. Saff and Ian H. Sloan and Yu Guang Wang and Robert S. Womersley},
  title = {{Covering of spheres by spherical caps and worst-case error for equal weight cubature in Sobolev spaces}},
  journal = {Journal of Mathematical Analysis and Applications},
  year = {2015},
  doi = {10.1016/j.jmaa.2015.05.079},
}
Figure