Simple universal bounds for Chebyshev-type quadratures (Q619071)

Given an integer \(k\geq 1\) and a measure \(\sigma\) on \(\mathbb R\) with finite first \(k\) moments, a quadrature formula of algebraic degree at least \(k\) is a set of nodes \(\{ x_{i}\}_{i=1}^n\subset \mathbb R\) and weights \(\{m_{i}\}_{i=1}^{n}\subset\mathbb R_{+}\) such that \[ \int x^{j}d\sigma(x)=\sum_{i=1}^n m_{i}x_{i}^j \] for all integer \(0\leq j\leq k\). The degree is exactly \(k\) if equality does not hold when \(j=k+1\). In this paper a probability measure \(\sigma\) is considered only and the formula has all weights equal to \(1/n\). Therefore, the formula takes the form \[ \int x^j d\sigma(x)= \frac{1}{n}\sum_{i=1}^n x_i^j \quad \text{for all } 0\leq j\leq k, \tag{1} \] where the nodes \((x_{i})_{i=1}^{n}\) need not to be distinct. Such formulas are called Chebyshev-type quadrature formulas. For a probability measure \(\sigma\) on \(\mathbb R\) and an integer \(k\geq 1\), \(n_{\sigma}^0(k)\) defines the minimal number of nodes \(n\) required in a Chebyshev-type quadrature (1) of algebraic degree at least \(k\), or \(\infty\) if no such quadrature exists. Define \(n_{\sigma}(k)\) to be the minimal integer such that for any \(n\geq n_{\sigma}(k)\) there exists a Chebyshev-type quadrature (1) of algebraic degree at least \(k\) having exactly \(n\) nodes, or \(\infty\) if no such integer exists. The author gives an upper bound on \(n_{\sigma}(k)\) which is given in terms of simple properties of \(\sigma\), requiring only an estimate on \(\sigma\)'s inverse modulus of continuity. While the bound is particularly simple for absolutely continuous measures with bounded densities, it extends also to singular measures and even to purely atomic measures, provided that some control over the size of the atoms is known. A lower bound on \(n_{\sigma}^{0}(k)\) is given which only requires estimates on the \((k-1)\)th and \(k\)th moments of \(\sigma\). Corresponding examples illustrate the sharpeness of these bounds. In particular, it is found that for a measure \(\sigma\) supported on \([0,1]\) with essentially bounded density, \(n_{\sigma}(k)\) may increase at most exponentially with \(k\), and this rate of growth is attained for some \(\sigma\). The concept of random Chebyshev-type quadratures is introduced, where nodes are chosen by taking independent samples from \(\sigma\). The author explains how this concept provides another way to upper bound \(n_{\sigma}^{0}(k)\) and \(n_{\sigma}(k)\) and he proposes the challenge of analyzing its performance. A preliminary result in this direction is proved for the uniform measure on the cube. Finally, the author applies these bounds to the construction of point sets on the sphere and the cylinder which form local approximate Chebyshev-type quadratures. The paper concludes with a list of open questions.