1 Introduction
Let
${\mathcal{M}}$
be a compact metric space with a fixed metric
$\unicode[STIX]{x1D703}$
and a finite non-negative Borel measure
$\unicode[STIX]{x1D707}$
, normalized by
$\unicode[STIX]{x1D707}({\mathcal{M}})=1$
. For any metric
$\unicode[STIX]{x1D70C}$
on
${\mathcal{M}}$
and any
$N$
-point subset (distribution)
${\mathcal{D}}_{N}\subset {\mathcal{M}}$
, we put
$$\begin{eqnarray}\unicode[STIX]{x1D70C}[{\mathcal{D}}_{N}]=\mathop{\sum }_{x_{1},x_{2}\in {\mathcal{D}}_{N}}\unicode[STIX]{x1D70C}(x_{1},x_{2}),\end{eqnarray}$$
and denote by
$\langle \unicode[STIX]{x1D70C}\rangle$
the average value of the metric
$\unicode[STIX]{x1D70C}$
, given by
$$\begin{eqnarray}\langle \unicode[STIX]{x1D70C}\rangle =\iint _{{\mathcal{M}}\times {\mathcal{M}}}\unicode[STIX]{x1D70C}(y_{1},y_{2})\,d\unicode[STIX]{x1D707}(y_{1})\,d\unicode[STIX]{x1D707}(y_{2}).\end{eqnarray}$$
We write
$B_{r}(y)=\{x:\unicode[STIX]{x1D703}(x,y)<r\}$
,
$r\in T$
,
$y\in {\mathcal{M}}$
, for the ball of radius
$r$
centred at
$y$
and of volume
$\unicode[STIX]{x1D707}(B_{r}(y))$
. Here
$T=\{r:r=\unicode[STIX]{x1D703}(y_{1},y_{2}),y_{1},y_{2}\in {\mathcal{M}}\}$
is the set of radii,
$T\subset [0,L]$
, where
$L=\sup \{r=\unicode[STIX]{x1D703}(y_{1},y_{2}):y_{1},y_{2}\in {\mathcal{M}}\}$
is the diameter of
${\mathcal{M}}$
in the original metric
$\unicode[STIX]{x1D703}$
.
The local discrepancy of a distribution
${\mathcal{D}}_{N}$
is defined by
$$\begin{eqnarray}\displaystyle \unicode[STIX]{x1D6EC}[B_{r}(y),{\mathcal{D}}_{N}] & = & \displaystyle \#(B_{r}(y)\cap {\mathcal{D}}_{N})-N\unicode[STIX]{x1D707}(B_{r}(y))\nonumber\\ \displaystyle & = & \displaystyle \mathop{\sum }_{x\in {\mathcal{D}}_{N}}\unicode[STIX]{x1D6EC}(B_{r}(y),x),\end{eqnarray}$$
where
$$\begin{eqnarray}\unicode[STIX]{x1D6EC}(B_{r}(y),x)=\unicode[STIX]{x1D712}(B_{r}(y),x)-\unicode[STIX]{x1D707}(B_{r}(y)),\end{eqnarray}$$
and
$\unicode[STIX]{x1D712}({\mathcal{E}},x)$
is the characteristic function of a subset
${\mathcal{E}}\subset {\mathcal{M}}$
.
The quadratic discrepancy is defined by
$$\begin{eqnarray}\unicode[STIX]{x1D706}_{r}[{\mathcal{D}}_{N}]=\int _{{\mathcal{M}}}\unicode[STIX]{x1D6EC}[B_{r}(y),{\mathcal{D}}_{N}]^{2}\,d\unicode[STIX]{x1D707}(y).\end{eqnarray}$$
This formula can be written as
$$\begin{eqnarray}\unicode[STIX]{x1D706}_{r}[{\mathcal{D}}_{N}]=\mathop{\sum }_{y_{1},y_{2}\in {\mathcal{D}}_{N}}\unicode[STIX]{x1D706}_{r}(y_{1},y_{2}),\end{eqnarray}$$
where
$$\begin{eqnarray}\unicode[STIX]{x1D706}_{r}(y_{1},y_{2})=\int _{{\mathcal{M}}}\unicode[STIX]{x1D6EC}(B_{r}(y),y_{1})\unicode[STIX]{x1D6EC}(B_{r}(y),y_{2})\,d\unicode[STIX]{x1D707}(y).\end{eqnarray}$$
Let
$\unicode[STIX]{x1D709}$
be a non-negative measure on the set
$T$
of radii. We put
$$\begin{eqnarray}\unicode[STIX]{x1D706}[\unicode[STIX]{x1D709},{\mathcal{D}}_{N}]=\int _{T}\unicode[STIX]{x1D706}_{r}[{\mathcal{D}}_{N}]\,d\unicode[STIX]{x1D709}(r)=\mathop{\sum }_{y_{1},y_{2}\in {\mathcal{D}}_{N}}\unicode[STIX]{x1D706}(\unicode[STIX]{x1D709},y_{1},y_{2}),\end{eqnarray}$$
where
$$\begin{eqnarray}\unicode[STIX]{x1D706}(\unicode[STIX]{x1D709},y_{1},y_{2})=\int _{T}\unicode[STIX]{x1D706}_{r}(y_{1},y_{2})\,d\unicode[STIX]{x1D709}(r).\end{eqnarray}$$
It is clear that the integrals (1.8) and (1.9) converge if the measure
$\unicode[STIX]{x1D709}$
is finite, while for special spaces
${\mathcal{M}}$
, these integrals converge for much more general measures
$\unicode[STIX]{x1D709}$
; see [Reference Skriganov12].
The quantity
$\unicode[STIX]{x1D706}[\unicode[STIX]{x1D709},{\mathcal{D}}_{N}]^{1/2}$
is known as the
$L_{2}$
-discrepancy of a distribution
${\mathcal{D}}_{N}$
in balls
$B_{r}(y)$
,
$r\in T$
,
$y\in {\mathcal{M}}$
, with respect to the measures
$\unicode[STIX]{x1D707}$
and
$\unicode[STIX]{x1D709}$
. In the present paper it is more convenient to deal with the quadratic discrepancy
$\unicode[STIX]{x1D706}[\unicode[STIX]{x1D709},{\mathcal{D}}_{N}]$
.
We introduce the extremal quantities
$$\begin{eqnarray}\displaystyle \unicode[STIX]{x1D70C}_{N} & = & \displaystyle \sup _{{\mathcal{D}}_{N}}\unicode[STIX]{x1D70C}[{\mathcal{D}}_{N}],\end{eqnarray}$$
$$\begin{eqnarray}\displaystyle \unicode[STIX]{x1D706}_{N}(\unicode[STIX]{x1D709}) & = & \displaystyle \inf _{{\mathcal{D}}_{N}}\unicode[STIX]{x1D706}[\unicode[STIX]{x1D709},{\mathcal{D}}_{N}],\end{eqnarray}$$
with the supremum and infimum taken over all
$N$
-point distributions
${\mathcal{D}}_{N}\subset {\mathcal{M}}$
.
The study of the quantities (1.10) and (1.11) falls within the subjects of the geometry of distances and discrepancy theory; see [Reference Alexander, Beck, Chen, Toth, Goodman and O’Rourke2, Reference Beck and Chen5].
In the present paper, we shall deduce non-trivial bounds for the quantities (1.10) and (1.11) under very general conditions on spaces
${\mathcal{M}}$
, metrics
$\unicode[STIX]{x1D70C}$
and measures
$\unicode[STIX]{x1D707}$
and
$\unicode[STIX]{x1D709}$
. It is convenient to introduce the concept of
$d$
-rectifiable spaces, enabling us to compare the metric and measure on
${\mathcal{M}}$
with the Euclidean metric and Lebesgue measure on
$\mathbb{R}^{d}$
. The concept of rectifiability is well known in geometric measure theory; see [Reference Mattila10]. Here, this terminology is adapted for our purposes.
Recall that a map
$f:{\mathcal{O}}\subset \mathbb{R}^{d}\rightarrow {\mathcal{M}}$
is Lipschitz if
$$\begin{eqnarray}\unicode[STIX]{x1D703}(f(Z_{1}),f(Z_{2}))\leqslant c\Vert Z_{1}-Z_{2}\Vert ,\quad Z_{1},Z_{2}\in {\mathcal{O}},\end{eqnarray}$$
with a positive constant
$c$
, and the smallest such constant is called the Lipschitz constant of
$f$
and denoted by
$\operatorname{Lip}(f)$
. Here
$\Vert \,\cdot \,\Vert$
denotes the Euclidean metric in
$\mathbb{R}^{d}$
.
Definition 1.1. A compact metric space
${\mathcal{M}}$
with a metric
$\unicode[STIX]{x1D703}$
and a measure
$\unicode[STIX]{x1D707}$
is called
$d$
-rectifiable if there exist a measure
$\unicode[STIX]{x1D708}$
on the
$d$
-dimensional unit cube
$I^{d}=[0,1]^{d}$
that is absolutely continuous with respect to the
$d$
-dimensional Lebesgue measure on
$I^{d}$
, a measurable subset
${\mathcal{O}}\subset I^{d}$
, and an injective Lipschitz map
$f:{\mathcal{O}}\rightarrow {\mathcal{M}}$
, such that:
-
(i)
$\unicode[STIX]{x1D707}({\mathcal{M}}\setminus f({\mathcal{O}}))=0$
; and -
(ii)
$\unicode[STIX]{x1D707}({\mathcal{E}})=\unicode[STIX]{x1D708}(f^{-1}({\mathcal{E}}\cap f({\mathcal{O}})))$
for any
$\unicode[STIX]{x1D707}$
-measurable subset
${\mathcal{E}}\subset {\mathcal{M}}$
.
Since the map
$f$
is injective, we can write
$$\begin{eqnarray}\unicode[STIX]{x1D708}({\mathcal{K}}\cap {\mathcal{O}})=\unicode[STIX]{x1D707}(f({\mathcal{K}}\cap {\mathcal{O}}))\end{eqnarray}$$
for any measurable subset
${\mathcal{K}}\subset I^{d}$
. We can also assume that the measure
$\unicode[STIX]{x1D708}$
is concentrated on
${\mathcal{O}}$
and
$\unicode[STIX]{x1D708}({\mathcal{O}})=\unicode[STIX]{x1D707}(f({\mathcal{O}}))=\unicode[STIX]{x1D707}({\mathcal{M}})=1$
.
Remark 1.1. Simple examples of
$d$
-rectifiable spaces can be easily given. Any smooth (or piece-wise smooth) compact
$d$
-dimensional manifold is
$d$
-rectifiable if in the local coordinates the metric satisfies (1.12), and the measure is absolutely continuous with respect to the
$d$
-dimensional Lebesgue measure. Particularly, any compact
$d$
-dimensional Riemannian manifold with the geodesic metric
$\unicode[STIX]{x1D703}$
and the Riemannian measure
$\unicode[STIX]{x1D707}$
is
$d$
-rectifiable. In this case, it is known that condition (1.12) holds; see [Reference Helgason8, Ch. I, Proposition 9.10]. On the other hand, the condition on the Riemannian measure is obvious because the metric tensor is continuous. We refer the reader to [Reference Mattila10] for many more exotic examples of rectifiable spaces.
In the present paper we shall prove the following theorem.
Theorem 1.1. Suppose that a compact metric space
${\mathcal{M}}$
, with a metric
$\unicode[STIX]{x1D703}$
and a measure
$\unicode[STIX]{x1D707}$
, is
$d$
-rectifiable. Then the following hold.
-
(i) If a metric
$\unicode[STIX]{x1D70C}$
on
${\mathcal{M}}$
satisfies the inequality with a constant
$$\begin{eqnarray}\unicode[STIX]{x1D70C}(x_{1},x_{2})\leqslant c_{0}\unicode[STIX]{x1D703}(x_{1},x_{2}),\end{eqnarray}$$
$c_{0}>0$
, then for each
$N$
, we have (1.14)
$$\begin{eqnarray}\unicode[STIX]{x1D70C}_{N}\geqslant \langle \unicode[STIX]{x1D70C}\rangle N^{2}-d2^{d-1}\operatorname{Lip}(f)c_{0}N^{1-1/d}.\end{eqnarray}$$
-
(ii) If a measure
$\unicode[STIX]{x1D709}$
on the set
$T$
of radii satisfies the condition with a constant
$$\begin{eqnarray}\unicode[STIX]{x1D709}([a,b))\leqslant c_{0}(\unicode[STIX]{x1D709})|a-b|,\quad a\leqslant b\text{ and }a,b\in T,\end{eqnarray}$$
$c_{0}(\unicode[STIX]{x1D709})>0$
, then for each
$N$
, we have (1.15)
$$\begin{eqnarray}\unicode[STIX]{x1D706}_{N}(\unicode[STIX]{x1D709})\leqslant d2^{d-3}\operatorname{Lip}(f)c_{0}(\unicode[STIX]{x1D709})N^{1-1/d}.\end{eqnarray}$$
Here
$\operatorname{Lip}(f)$
is the Lipschitz constant of the map
$f$
in the definition of
$d$
-rectifiability of the space
${\mathcal{M}}$
.
Under such general assumptions one cannot expect that the bounds (1.14) and (1.15) are best possible. One can give examples of
$d$
-dimensional manifolds and metrics where the bounds (1.14) and (1.15) can be improved. Consider, for example, the
$d$
-dimensional unit spheres
$S^{d}=\{x\in \mathbb{R}^{d+1}:\Vert x\Vert =1\}$
with the geodesic (great circle) metric
$\unicode[STIX]{x1D703}$
and the standard Lebesgue measure
$\unicode[STIX]{x1D707}$
on
$S^{d}$
. In this case, we have
$$\begin{eqnarray}\unicode[STIX]{x1D703}_{N}=\langle \unicode[STIX]{x1D703}\rangle N^{2}-\unicode[STIX]{x1D700}_{N},\qquad \langle \unicode[STIX]{x1D703}\rangle =\unicode[STIX]{x1D70B}/2,\end{eqnarray}$$
where
$\unicode[STIX]{x1D700}_{N}=0$
for even
$N$
and
$\unicode[STIX]{x1D700}_{N}\leqslant \unicode[STIX]{x1D70B}/2$
for odd
$N$
, see [Reference Bilyk, Dai and Matzke6, Reference Skriganov12].
However, there are other examples where the order of the bounds (1.14) and (1.15) turns out to be sharp. Instead of the geodesic metric
$\unicode[STIX]{x1D703}$
, we can consider the chordal metric
$\unicode[STIX]{x1D70F}$
, given by
$\unicode[STIX]{x1D70F}(x_{1},x_{2})=2\sin {\textstyle \frac{1}{2}}\unicode[STIX]{x1D703}(x_{1},x_{2})$
on
$S^{d}$
. In this case, we have the two-sided bounds
$$\begin{eqnarray}\langle \unicode[STIX]{x1D70F}\rangle N^{2}-\mathit{CN}^{1-1/d}<\unicode[STIX]{x1D70F}_{N}<\langle \unicode[STIX]{x1D70F}\rangle N^{2}-\mathit{cN}^{1-1/d}\end{eqnarray}$$
and
$$\begin{eqnarray}C_{1}N^{1-1/d}>\unicode[STIX]{x1D706}_{N}(\unicode[STIX]{x1D709}^{\natural })>c_{1}N^{1-1/d},\end{eqnarray}$$
with constants independent of
$N$
and the measure
$d\unicode[STIX]{x1D709}^{\natural }(r)=\sin r\,dr$
on the set of radii. The left-hand bounds in (1.17) and (1.18) were proved by Alexander [Reference Alexander1] and Stolarsky [Reference Stolarsky13]. The right-hand bounds in (1.17) and (1.18) were proved by Beck [Reference Beck4]; the proof involves Fourier analysis on
$\mathbb{R}^{d+1}$
.
The quantities
$\unicode[STIX]{x1D70F}_{N}$
and
$\unicode[STIX]{x1D706}_{N}(\unicode[STIX]{x1D709}^{\natural })$
in the bounds (1.17) and (1.18) are not independent, and are related by the following identity. For any
$N$
-point subset
${\mathcal{D}}_{N}\subset S^{d}$
, we have
$$\begin{eqnarray}\unicode[STIX]{x1D6FC}(S^{d})\unicode[STIX]{x1D706}[\unicode[STIX]{x1D709}^{\natural },{\mathcal{D}}_{N}]+\unicode[STIX]{x1D70F}[{\mathcal{D}}_{N}]=\langle \unicode[STIX]{x1D70F}\rangle N^{2},\end{eqnarray}$$
where
$\unicode[STIX]{x1D6FC}(S^{d})>0$
is a constant independent of
${\mathcal{D}}_{N}$
. Particularly, for any
$N$
, we have
$$\begin{eqnarray}\unicode[STIX]{x1D6FC}(S^{d})\unicode[STIX]{x1D706}_{N}(\unicode[STIX]{x1D709}^{\natural })+\unicode[STIX]{x1D70F}_{N}=\langle \unicode[STIX]{x1D70F}\rangle N^{2},\end{eqnarray}$$
and any bound for one of the quantities
$\unicode[STIX]{x1D70C}_{N}$
or
$\unicode[STIX]{x1D706}_{N}(\unicode[STIX]{x1D709}^{\natural })$
implies a bound for the other one.
The identity (1.19) was established by Stolarsky [Reference Stolarsky13] and is known in the literature as Stolarsky’s invariance principle. The original proof in [Reference Stolarsky13] was rather difficult. It was simplified in [Reference Bilyk, Dai and Matzke6, Reference Brauchart and Dick7].
Spheres as homogeneous spaces
$S^{d}=\text{SO}(d+1)/\text{SO}(d)$
are the simplest examples of compact Riemannian symmetric spaces of rank one (two-point homogeneous spaces). All such spaces are known. Besides the spheres there are the real, complex, and quaternionic projective spaces and the octonionic projective plane; see, for example, [Reference Helgason8].
By Theorem 1.1 the bounds (1.14) and (1.15) hold for all such spaces. It turns out that the two-sided bounds of type (1.16) and (1.17) also hold for all these spaces and some classes of metrics on them. The invariance principle (1.19) can also be generalized to projective spaces. These results are intimately related to the geometry of projective spaces and Fourier analysis on homogeneous space. A proof and detailed discussion of these results are given in our paper [Reference Skriganov12].
In the present paper we use elementary methods going back to papers by Alexander [Reference Alexander1] and Stolarsky [Reference Stolarsky13]. Despite the simplicity, these methods turn out to be rather efficient.
In §2, we introduce a class of symmetric difference metrics on metric spaces and give a generalization of Stolarsky’s invariance principle to distance-invariant metric spaces (Theorem 2.1).
In §3, we give a probabilistic version of the invariance principle for arbitrary compact metric spaces (Theorem 3.1). With the help of this probabilistic invariance principle, we obtain the basic bounds for the quantities (1.10) and (1.11) in terms of equal-measure partitions of a metric space (Theorem 3.2).
In §4, we state our result on equal-measure partitions of
$d$
-rectifiable compact metric spaces into parts of small average diameter (Theorem 4.1). Relying on this result and Theorem 3.2, we complete the proof of Theorem 1.1.
In §5, we describe an explicit construction of equal measure partitions of
$d$
-rectifiable compact metric spaces into parts of small average diameter and prove Theorem 4.1.
2 The invariance principle for distance-invariant spaces
On an arbitrary compact metric space
${\mathcal{M}}$
, we introduce metrics associated with the fixed metric
$\unicode[STIX]{x1D703}$
and measure
$\unicode[STIX]{x1D707}$
by writing
$$\begin{eqnarray}\unicode[STIX]{x1D703}^{\unicode[STIX]{x1D6E5}}(\unicode[STIX]{x1D709},y_{1},y_{2})=\int _{T}\unicode[STIX]{x1D703}_{r}^{\unicode[STIX]{x1D6E5}}(y_{1},y_{2})\,d\unicode[STIX]{x1D709}(r),\end{eqnarray}$$
where
$$\begin{eqnarray}\unicode[STIX]{x1D703}_{r}^{\unicode[STIX]{x1D6E5}}(y_{1},y_{2})={\textstyle \frac{1}{2}}\unicode[STIX]{x1D707}(B_{r}(y_{1})\unicode[STIX]{x1D6E5}B_{r}(y_{2})).\end{eqnarray}$$
Here
$$\begin{eqnarray}B_{r}(y_{1})\unicode[STIX]{x1D6E5}B_{r}(y_{2})=(B_{r}(y_{1})\cup B_{r}(y_{2}))\setminus (B_{r}(y_{1})\cap B_{r}(y_{2}))\end{eqnarray}$$
denotes the symmetric difference of the balls
$B_{r}(y_{1})$
and
$B_{r}(y_{2})$
. Hence
$$\begin{eqnarray}\displaystyle \unicode[STIX]{x1D703}_{r}^{\unicode[STIX]{x1D6E5}}(y_{1},y_{2}) & = & \displaystyle \frac{1}{2}\int _{{\mathcal{M}}}\unicode[STIX]{x1D712}(B_{r}(y_{1})\unicode[STIX]{x1D6E5}B_{r}(y_{2}),y)\,d\unicode[STIX]{x1D707}(y)\nonumber\\ \displaystyle & = & \displaystyle \frac{1}{2}\int _{{\mathcal{M}}}\big(\unicode[STIX]{x1D712}(B_{r}(y_{1}),y)+\unicode[STIX]{x1D712}(B_{r}(y_{2}),y)\nonumber\\ \displaystyle & & \displaystyle -\,2\unicode[STIX]{x1D712}(B_{r}(y_{1}),y)\unicode[STIX]{x1D712}(B_{r}(y_{2}),y)\big)\,d\unicode[STIX]{x1D707}(y)\nonumber\\ \displaystyle & = & \displaystyle \frac{1}{2}\int _{{\mathcal{M}}}|\unicode[STIX]{x1D712}(B_{r}(y_{1}),y)-\unicode[STIX]{x1D712}(B_{r}(y_{2}),y)|\,d\unicode[STIX]{x1D707}(y).\end{eqnarray}$$
For the average values of the metrics
$\unicode[STIX]{x1D703}^{\unicode[STIX]{x1D6E5}}(\unicode[STIX]{x1D709})$
and
$\unicode[STIX]{x1D703}_{r}^{\unicode[STIX]{x1D6E5}}$
, we obtain
$$\begin{eqnarray}\displaystyle \langle \unicode[STIX]{x1D703}^{\unicode[STIX]{x1D6E5}}(\unicode[STIX]{x1D709})\rangle & = & \displaystyle \int _{T}\langle \unicode[STIX]{x1D703}_{r}^{\unicode[STIX]{x1D6E5}}\rangle \,d\unicode[STIX]{x1D709}(r),\end{eqnarray}$$
$$\begin{eqnarray}\displaystyle \langle \unicode[STIX]{x1D703}_{r}^{\unicode[STIX]{x1D6E5}}\rangle & = & \displaystyle \iint _{{\mathcal{M}}\times {\mathcal{M}}}\unicode[STIX]{x1D703}_{r}^{\unicode[STIX]{x1D6E5}}(y_{1},y_{2})\,d\unicode[STIX]{x1D707}(y_{1})\,d\unicode[STIX]{x1D707}(y_{2})\nonumber\\ \displaystyle & = & \displaystyle \int _{{\mathcal{M}}}\big(\unicode[STIX]{x1D707}(B_{r}(y))-\unicode[STIX]{x1D707}(B_{r}(y))^{2}\big)\,d\unicode[STIX]{x1D707}(y),\end{eqnarray}$$
where we have made use of the useful formula
$$\begin{eqnarray}\unicode[STIX]{x1D712}(B_{r}(y),x)=\unicode[STIX]{x1D712}(B_{r}(x),y)=\unicode[STIX]{x1D712}(r-\unicode[STIX]{x1D703}(x,y));\end{eqnarray}$$
here
$\unicode[STIX]{x1D712}(t)$
,
$t\in \mathbb{R}$
, is the characteristic function of the half-axis
$[0,\infty )$
. The formula (2.7) holds in view of the symmetry of metric
$\unicode[STIX]{x1D703}$
.
It is clear that the integrals (2.1) and (2.6) converge if the measure
$\unicode[STIX]{x1D709}$
is finite while for special spaces
${\mathcal{M}}$
, these integrals converge for much more general measures
$\unicode[STIX]{x1D709}$
; see [Reference Skriganov12, Lemma 2.1].
Lemma 2.1. We have
$$\begin{eqnarray}\unicode[STIX]{x1D703}^{\unicode[STIX]{x1D6E5}}(\unicode[STIX]{x1D709},y_{1},y_{2})=\frac{1}{2}\int _{{\mathcal{M}}}|\unicode[STIX]{x1D70E}(\unicode[STIX]{x1D703}(y_{1},y))-\unicode[STIX]{x1D70E}(\unicode[STIX]{x1D703}(y_{2},y))|\,d\unicode[STIX]{x1D707}(y),\end{eqnarray}$$
where
$$\begin{eqnarray}\unicode[STIX]{x1D70E}(r)=\unicode[STIX]{x1D709}([r,L])=\int _{r}^{L}d\unicode[STIX]{x1D709}(t),\quad r\in T,\end{eqnarray}$$
and
$L=\sup \{r:r\in T\}$
is the diameter of
${\mathcal{M}}$
.
Proof. For brevity, we write
$\unicode[STIX]{x1D703}(y_{1},y)=\unicode[STIX]{x1D703}_{1}$
and
$\unicode[STIX]{x1D703}(y_{2},y)=\unicode[STIX]{x1D703}_{2}$
. Using (2.1), (2.4) and (2.7), we obtain
$$\begin{eqnarray}\displaystyle & & \displaystyle \unicode[STIX]{x1D703}^{\unicode[STIX]{x1D6E5}}(\unicode[STIX]{x1D709},y_{1},y_{2})\nonumber\\ \displaystyle & & \displaystyle \quad =\frac{1}{2}\int _{{\mathcal{M}}}\biggl(\int _{T}(\unicode[STIX]{x1D712}(r-\unicode[STIX]{x1D703}_{1})+\unicode[STIX]{x1D712}(r-\unicode[STIX]{x1D703}_{2})-2\unicode[STIX]{x1D712}(r-\unicode[STIX]{x1D703}_{1})\unicode[STIX]{x1D712}(r-\unicode[STIX]{x1D703}_{2}))\,d\unicode[STIX]{x1D709}(r)\biggr)\,d\unicode[STIX]{x1D707}(y)\nonumber\\ \displaystyle & & \displaystyle \quad =\frac{1}{2}\int _{{\mathcal{M}}}(\unicode[STIX]{x1D70E}(\unicode[STIX]{x1D703}_{1})+\unicode[STIX]{x1D70E}(\unicode[STIX]{x1D703}_{2})-2\unicode[STIX]{x1D70E}(\max \{\unicode[STIX]{x1D703}_{1},\unicode[STIX]{x1D703}_{2}\}))\,d\unicode[STIX]{x1D707}(y).\end{eqnarray}$$
Since
$\unicode[STIX]{x1D70E}$
is a non-increasing function, we have
$$\begin{eqnarray}\displaystyle 2\unicode[STIX]{x1D70E}(\max \{\unicode[STIX]{x1D703}_{1},\unicode[STIX]{x1D703}_{2}\}) & = & \displaystyle 2\min \{\unicode[STIX]{x1D70E}(\unicode[STIX]{x1D703}_{1}),\unicode[STIX]{x1D70E}(\unicode[STIX]{x1D703}_{2})\}\nonumber\\ \displaystyle & = & \displaystyle \unicode[STIX]{x1D70E}(\unicode[STIX]{x1D703}_{1})+\unicode[STIX]{x1D70E}(\unicode[STIX]{x1D703}_{2})-|\unicode[STIX]{x1D70E}(\unicode[STIX]{x1D703}_{1})-\unicode[STIX]{x1D70E}(\unicode[STIX]{x1D703}_{2})|.\end{eqnarray}$$
Remark 2.1. Using (2.8), we can calculate the metric
$\unicode[STIX]{x1D703}^{\unicode[STIX]{x1D6E5}}(\unicode[STIX]{x1D709})$
explicitly for special spaces
${\mathcal{M}}$
and measures
$\unicode[STIX]{x1D709}$
. For example, in the case of spheres
$S^{d}$
and the special measure
$d\unicode[STIX]{x1D709}^{\natural }(r)=\sin r\,dr$
, one can easily find that the metric
$\unicode[STIX]{x1D703}^{\unicode[STIX]{x1D6E5}}(\unicode[STIX]{x1D709}^{\natural })$
is proportional to the chordal metric
$\unicode[STIX]{x1D70F}$
, see [Reference Bilyk, Dai and Matzke6]. For projective spaces and the specific measure
$\unicode[STIX]{x1D709}^{\natural }$
, the metric
$\unicode[STIX]{x1D703}^{\unicode[STIX]{x1D6E5}}(\unicode[STIX]{x1D709}^{\natural })$
is proportional to the Fubini–Study metric, see [Reference Skriganov12].
We next compare the metrics
$\unicode[STIX]{x1D703}$
and
$\unicode[STIX]{x1D703}^{\unicode[STIX]{x1D6E5}}(\unicode[STIX]{x1D709})$
on general metric spaces. Note that using geometric features of spheres and projective spaces, the following result can be improved; see [Reference Skriganov12, Lemma 2.1].
Lemma 2.2. If the measure
$\unicode[STIX]{x1D709}$
satisfies the condition
$$\begin{eqnarray}\unicode[STIX]{x1D709}([a,b))\leqslant c_{0}(\unicode[STIX]{x1D709})|a-b|,\quad a\leqslant b\text{ and }a,b\in T,\end{eqnarray}$$
with a constant
$c_{0}(\unicode[STIX]{x1D709})>0$
, then we have the inequality
$$\begin{eqnarray}\unicode[STIX]{x1D703}^{\unicode[STIX]{x1D6E5}}(\unicode[STIX]{x1D709},y_{1},y_{2})\leqslant {\textstyle \frac{1}{2}}c_{0}(\unicode[STIX]{x1D709})\unicode[STIX]{x1D703}(y_{1},y_{2}).\end{eqnarray}$$
Proof. We use the same notation as in the proof of Lemma 2.1. Suppose first that
$\unicode[STIX]{x1D703}_{1}\leqslant \unicode[STIX]{x1D703}_{2}$
. Using (2.9), (2.12) and the triangle inequality for the metric
$\unicode[STIX]{x1D703}$
, we obtain
$$\begin{eqnarray}\displaystyle |\unicode[STIX]{x1D70E}(\unicode[STIX]{x1D703}_{1})-\unicode[STIX]{x1D70E}(\unicode[STIX]{x1D703}_{2})| & = & \displaystyle \unicode[STIX]{x1D709}([\unicode[STIX]{x1D703}_{1},L])-\unicode[STIX]{x1D709}([\unicode[STIX]{x1D703}_{2},L])=\unicode[STIX]{x1D709}([\unicode[STIX]{x1D703}_{1},\unicode[STIX]{x1D703}_{2}))\leqslant c_{0}(\unicode[STIX]{x1D703}_{2}-\unicode[STIX]{x1D703}_{1})\nonumber\\ \displaystyle & = & \displaystyle c_{0}(\unicode[STIX]{x1D703}(y_{2},y_{1})-\unicode[STIX]{x1D703}(y_{1},y))\leqslant c_{0}(\unicode[STIX]{x1D709})\unicode[STIX]{x1D703}(y_{1},y_{2}).\end{eqnarray}$$
A similar inequality holds if
$\unicode[STIX]{x1D703}_{1}>\unicode[STIX]{x1D703}_{2}$
. Substituting (2.14) into (2.8), we obtain (2.13).◻
Consider the kernel (1.7). Substituting (1.4) into (1.7), we obtain
$$\begin{eqnarray}\displaystyle \unicode[STIX]{x1D706}_{r}(y_{1},y_{2}) & = & \displaystyle \int _{{\mathcal{M}}}\big(\unicode[STIX]{x1D712}(B_{r}(y),y_{1})\unicode[STIX]{x1D712}(B_{r}(y),y_{2})-\unicode[STIX]{x1D707}(B_{r}(y))\unicode[STIX]{x1D712}(B_{r}(y),y_{1})\nonumber\\ \displaystyle & & \displaystyle -\unicode[STIX]{x1D707}(B_{r}(y))\unicode[STIX]{x1D712}(B_{r}(y),y_{2})+\unicode[STIX]{x1D707}(B_{r}(y))^{2}\big)\,d\unicode[STIX]{x1D707}(y).\end{eqnarray}$$
Comparing (2.4) and (2.15), we see that
$$\begin{eqnarray}\unicode[STIX]{x1D706}_{r}(y_{1},y_{2})+\unicode[STIX]{x1D703}_{r}^{\unicode[STIX]{x1D6E5}}(y_{1},y_{2})=A_{r}^{(0)}+A_{r}^{(1)}(y_{1})+A_{r}^{(1)}(y_{2}),\end{eqnarray}$$
where
$$\begin{eqnarray}A_{r}^{(0)}=\int _{{\mathcal{M}}}(B_{r}(y))^{2}\,d\unicode[STIX]{x1D707}(y)\end{eqnarray}$$
and
$$\begin{eqnarray}\displaystyle A_{r}^{(1)}(x) & = & \displaystyle \int _{{\mathcal{M}}}\biggl(\frac{1}{2}\unicode[STIX]{x1D712}(B_{r}(x),y)-\unicode[STIX]{x1D707}(B_{r}(y))\unicode[STIX]{x1D712}(B_{r}(y),x)\biggr)d\unicode[STIX]{x1D707}(y)\nonumber\\ \displaystyle & = & \displaystyle \frac{1}{2}\unicode[STIX]{x1D707}(B_{r}(x))-\int _{{\mathcal{M}}}\unicode[STIX]{x1D707}(B_{r}(y))\unicode[STIX]{x1D712}(B_{r}(y),x)\,d\unicode[STIX]{x1D707}(y)\nonumber\\ \displaystyle & = & \displaystyle \frac{1}{2}\unicode[STIX]{x1D707}(B_{r}(x))-\int _{{\mathcal{M}}}\unicode[STIX]{x1D707}(B_{r}(y))\unicode[STIX]{x1D712}(B_{r}(x),y)\,d\unicode[STIX]{x1D707}(y),\end{eqnarray}$$
here we have used the formula (2.7).
Let us consider these formulas in the following special case. A metric space
${\mathcal{M}}$
is called distance-invariant if, for each
$r\in T$
, the volume of ball
$\unicode[STIX]{x1D707}(B_{r}(y))$
is independent of
$y\in {\mathcal{M}}$
; see [Reference Levenshtein, Pless and Huffman9]. The typical examples of distance-invariant spaces are (finite or infinite) homogeneous spaces
${\mathcal{M}}=G/H$
, where
$G$
is a compact group,
$H{\vartriangleleft}G$
is a closed subgroup, while
$\unicode[STIX]{x1D703}$
and
$\unicode[STIX]{x1D707}$
are respectively
$G$
-invariant metric and measure on
${\mathcal{M}}$
.
Numerous examples of distance-invariant spaces are known in algebraic combinatorics as distance-regular graphs and metric association schemes (on finite or infinite sets). Such spaces satisfy the stronger condition that the volume of intersection
$\unicode[STIX]{x1D707}(B_{r_{1}}(y_{1})\cap B_{r_{2}}(y_{2}))$
of any two balls
$B_{r_{1}}(y_{1})$
and
$B_{r_{2}}(y_{2})$
depends only on
$r_{1},r_{2}$
and
$r_{3}=\unicode[STIX]{x1D703}(y_{1},y_{2})$
; see [Reference Barg and Skriganov3, Reference Levenshtein, Pless and Huffman9].
For distance-invariant spaces, the integrals in (2.17) and (2.18) can be easily calculated, and we arrive at the following result.
Theorem 2.1. Let a compact metric space
${\mathcal{M}}$
with a metric
$\unicode[STIX]{x1D703}$
and a measure
$\unicode[STIX]{x1D707}$
be distance-invariant. Then
$$\begin{eqnarray}\unicode[STIX]{x1D706}_{r}(y_{1},y_{2})+\unicode[STIX]{x1D703}_{r}^{\unicode[STIX]{x1D6E5}}(y_{1},y_{2})=\langle \unicode[STIX]{x1D703}_{r}^{\unicode[STIX]{x1D6E5}}\rangle\end{eqnarray}$$
and
$$\begin{eqnarray}\unicode[STIX]{x1D706}(\unicode[STIX]{x1D709},y_{1},y_{2})+\unicode[STIX]{x1D703}^{\unicode[STIX]{x1D6E5}}(\unicode[STIX]{x1D709},y_{1},y_{2})=\langle \unicode[STIX]{x1D703}^{\unicode[STIX]{x1D6E5}}(\unicode[STIX]{x1D709})\rangle .\end{eqnarray}$$
Furthermore, if
$\unicode[STIX]{x1D703}^{\unicode[STIX]{x1D6E5}}[\unicode[STIX]{x1D709},{\mathcal{D}}_{N}]$
and
$\unicode[STIX]{x1D703}_{N}^{\unicode[STIX]{x1D6E5}}(\unicode[STIX]{x1D709})$
denote respectively the characteristics (1.1) and (1.10) with the metric
$\unicode[STIX]{x1D70C}=\unicode[STIX]{x1D703}^{\unicode[STIX]{x1D6E5}}(\unicode[STIX]{x1D709})$
, then
$$\begin{eqnarray}\unicode[STIX]{x1D706}[\unicode[STIX]{x1D709},{\mathcal{D}}_{N}]+\unicode[STIX]{x1D703}^{\unicode[STIX]{x1D6E5}}[\unicode[STIX]{x1D709},{\mathcal{D}}_{N}]=\langle \unicode[STIX]{x1D703}^{\unicode[STIX]{x1D6E5}}(\unicode[STIX]{x1D709})\rangle N^{2}\end{eqnarray}$$
and
$$\begin{eqnarray}\unicode[STIX]{x1D706}_{N}(\unicode[STIX]{x1D709})+\unicode[STIX]{x1D703}_{N}^{\unicode[STIX]{x1D6E5}}(\unicode[STIX]{x1D709})=\langle \unicode[STIX]{x1D703}^{\unicode[STIX]{x1D6E5}}(\unicode[STIX]{x1D709})\rangle N^{2}.\end{eqnarray}$$
Here
$r\in T$
and
${\mathcal{D}}_{N}\subset {\mathcal{M}}$
is an arbitrary
$N$
-point subset. The equalities (2.21) and (2.22) hold for any non-negative measure
$\unicode[STIX]{x1D709}$
such that the integrals (1.8), (1.9), (2.1) and (2.5) converge.
Proof. For brevity, we write
$v_{r}=\unicode[STIX]{x1D707}(B_{r}(y))$
. By definition,
$v_{r}$
is a constant independent of
$y\in {\mathcal{M}}$
, and (2.17) and (2.18) take the form
$$\begin{eqnarray}A_{r}^{(0)}=v_{r}^{2}\quad \text{and}\quad A_{r}^{(1)}(x)={\textstyle \frac{1}{2}}v_{r}-v_{r}^{2}.\end{eqnarray}$$
Hence the right-hand side of (2.16) is equal to
$v_{r}-v_{r}^{2}$
. On the other hand, the average value (2.6) is also equal to
$v_{r}-v_{r}^{2}$
. This establishes (2.19). Integrating (2.19) over
$r\in T$
with respect to the measure
$\unicode[STIX]{x1D709}$
, we obtain (2.20). Summing (2.20) over
$y_{1},y_{2}\in {\mathcal{D}}_{N}$
, we obtain (2.21), and using (1.10) and (1.11), we obtain (2.22).◻
Theorem 2.1 is a generalization of the invariance principle to arbitrary compact distance-invariant spaces. For spheres
$S^{d}$
, the relation (2.21) implies Stolarsky’s invariance principle (1.19), since in this case the metrics
$\unicode[STIX]{x1D703}^{\unicode[STIX]{x1D6E5}}(\unicode[STIX]{x1D709}^{\natural })$
and
$\unicode[STIX]{x1D70F}$
are proportional as mentioned earlier in Remark 2.1. Theorem 2.1 probably provides the most adequate explanation of the invariance principles.
3 Equal-measure partitions and the probabilistic invariance principle
Is it possible to generalize invariance principles to arbitrary compact metric spaces? At first glance the answer should be negative. Nevertheless, a probabilistic generalization of such relations turns out to be possible.
First of all, we introduce some definitions and notation. We consider an arbitrary compact metric space
${\mathcal{M}}$
with a fixed metric
$\unicode[STIX]{x1D703}$
and a normalized measure
$\unicode[STIX]{x1D707}$
. Consider a partition
${\mathcal{R}}_{N}=\{V_{i}\}_{1}^{N}$
of
${\mathcal{M}}$
into
$N$
measurable subsets
$V_{i}\subset {\mathcal{M}}$
, with
$$\begin{eqnarray}\unicode[STIX]{x1D707}\biggl({\mathcal{M}}\bigg\backslash\mathop{\bigcup }_{i=1}^{N}V_{i}\biggr)=0,\qquad \unicode[STIX]{x1D707}(V_{i}\cap V_{j})=0,\quad i\neq j.\end{eqnarray}$$
We write
$\operatorname{diam}(V,\unicode[STIX]{x1D70C})=\sup \{\unicode[STIX]{x1D70C}(y_{1},y_{2}):y_{1},y_{2}\in V\}$
for the diameter of a subset
$V\subset {\mathcal{M}}$
with respect to a metric
$\unicode[STIX]{x1D70C}$
on
${\mathcal{M}}$
. For the partition (3.1), we introduce the average diameter
$$\begin{eqnarray}\operatorname{Diam}_{1}({\mathcal{R}}_{N},\unicode[STIX]{x1D70C})=\frac{1}{N}\mathop{\sum }_{i=1}^{N}\operatorname{diam}(V_{i},\unicode[STIX]{x1D70C})\end{eqnarray}$$
and the maximum diameter
$$\begin{eqnarray}\operatorname{Diam}_{\infty }({\mathcal{R}}_{N},\unicode[STIX]{x1D70C})=\max _{1\leqslant i\leqslant N}\operatorname{diam}(V_{i},\unicode[STIX]{x1D70C}).\end{eqnarray}$$
It is clear that
$$\begin{eqnarray}\operatorname{Diam}_{1}({\mathcal{R}}_{N},\unicode[STIX]{x1D70C})\leqslant \operatorname{Diam}_{\infty }({\mathcal{R}}_{N},\unicode[STIX]{x1D70C}),\end{eqnarray}$$
and that for two metrics
$\unicode[STIX]{x1D70C}_{1}$
and
$\unicode[STIX]{x1D70C}$
,
$$\begin{eqnarray}\left\{\begin{array}{@{}l@{}}\operatorname{Diam}_{1}({\mathcal{R}}_{N},\unicode[STIX]{x1D70C}_{1})\leqslant c_{0}\operatorname{Diam}_{1}({\mathcal{R}}_{N},\unicode[STIX]{x1D70C}),\\ \operatorname{Diam}_{\infty }({\mathcal{R}}_{N},\unicode[STIX]{x1D70C}_{1})\leqslant c_{0}\operatorname{Diam}_{\infty }({\mathcal{R}}_{N},\unicode[STIX]{x1D70C}),\end{array}\right.\end{eqnarray}$$
if
$\unicode[STIX]{x1D70C}_{1}(x,y)\leqslant c_{0}\unicode[STIX]{x1D70C}(x,y)$
for every
$x,y\in {\mathcal{M}}$
.
A partition
${\mathcal{R}}_{N}=\{V_{i}\}_{1}^{N}$
is an equal-measure partition if all the subsets
$V_{i}$
have equal measure
$\unicode[STIX]{x1D707}(V_{i})=N^{-1}$
,
$1\leqslant i\leqslant N$
.
Suppose that an equal-measure partition
${\mathcal{R}}_{N}=\{V_{i}\}_{1}^{N}$
of the space
${\mathcal{M}}$
is given. Introduce the probability space
$$\begin{eqnarray}\unicode[STIX]{x1D6FA}_{N}=\mathop{\prod }_{i=1}^{N}V_{i}=\{X_{N}=(x_{1},\ldots ,x_{N}):x_{i}\in V_{i},1\leqslant i\leqslant N\},\end{eqnarray}$$
with a probability measure
$$\begin{eqnarray}\unicode[STIX]{x1D714}_{N}=\mathop{\prod }_{i=1}^{N}\widetilde{\unicode[STIX]{x1D707}}_{i},\end{eqnarray}$$
where
$\widetilde{\unicode[STIX]{x1D707}}_{i}=N\unicode[STIX]{x1D707}|_{V_{i}}$
. Here
$\unicode[STIX]{x1D707}|_{V_{i}}$
denotes the restriction of the measure
$\unicode[STIX]{x1D707}$
to a subset
$V_{i}\subset {\mathcal{M}}$
. We next write
$\mathbb{E}_{N}F[\,\cdot \,]$
for the expectation of a random variable
$F[X_{N}]$
,
$X_{N}\in \unicode[STIX]{x1D6FA}_{N}$
, and thus
$$\begin{eqnarray}\displaystyle \mathbb{E}_{N}F[\,\cdot \,] & = & \displaystyle \int _{\unicode[STIX]{x1D6FA}_{N}}F[X_{N}]\,d\unicode[STIX]{x1D714}_{N}\nonumber\\ \displaystyle & = & \displaystyle N^{N}\int \!\cdots \!\int _{V_{1}\times \cdots \times V_{N}}F(x_{1},\ldots ,x_{N})\,d\unicode[STIX]{x1D707}(x_{1})\cdots d\unicode[STIX]{x1D707}(x_{N}).\end{eqnarray}$$
Note that in the second equality, we have used the assumption that the subsets
$V_{i}$
are of equal measure.
Lemma 3.1. Let
$F^{(1)}[X_{N}]$
and
$F^{(2)}[X_{N}]$
,
$X_{N}=(x_{1},\ldots ,x_{N})\in \unicode[STIX]{x1D6FA}_{N}$
, be random variables given by
$$\begin{eqnarray}F^{(1)}[X_{N}]=\mathop{\sum }_{i}f(x_{i})\quad \text{and}\quad F^{(2)}[X_{N}]=\mathop{\sum }_{i\neq j}f(x_{i},x_{j}),\end{eqnarray}$$
where
$f(y)$
and
$f(y_{1},y_{2})$
are integrable functions on
${\mathcal{M}}$
and
${\mathcal{M}}\times {\mathcal{M}}$
respectively. Then
$$\begin{eqnarray}\mathbb{E}_{N}F^{(1)}[\,\cdot \,]=N\int _{{\mathcal{M}}}f(y)\,d\unicode[STIX]{x1D707}(y)\end{eqnarray}$$
and
$$\begin{eqnarray}\displaystyle \mathbb{E}_{N}F^{(2)}[\,\cdot \,] & = & \displaystyle N^{2}\iint _{{\mathcal{M}}\times {\mathcal{M}}}f(y_{1},y_{2})\,d\unicode[STIX]{x1D707}(y_{1})\,d\unicode[STIX]{x1D707}(y_{2})\nonumber\\ \displaystyle & & \displaystyle -N^{2}\mathop{\sum }_{i=1}^{N}\iint _{V_{i}\times V_{i}}f(y_{1},y_{2})\,d\unicode[STIX]{x1D707}(y_{1})\,d\unicode[STIX]{x1D707}(y_{2}).\end{eqnarray}$$
Proof. Substituting the left equality in (3.8) into (3.7), we obtain
$$\begin{eqnarray}\mathbb{E}_{N}F^{(1)}[\,\cdot \,]=N\mathop{\sum }_{i}\int _{V_{i}}f(y)\,d\unicode[STIX]{x1D707}(y)=N\int _{{\mathcal{M}}}f(y)\,d\unicode[STIX]{x1D707}(y).\end{eqnarray}$$
This proves (3.9).
Substituting the right equality in (3.8) into (3.7), we obtain
$$\begin{eqnarray}\displaystyle \mathbb{E}_{N}F^{(2)}[\,\cdot \,] & = & \displaystyle N^{2}\mathop{\sum }_{i\neq j}\iint _{V_{i}\times V_{j}}f(y_{1},y_{2})\,d\unicode[STIX]{x1D707}(y_{1})\,d\unicode[STIX]{x1D707}(y_{2})\nonumber\\ \displaystyle & = & \displaystyle N^{2}\mathop{\sum }_{i,j}\iint _{V_{i}\times V_{j}}f(y_{1},y_{2})\,d\unicode[STIX]{x1D707}(y_{1})\,d\unicode[STIX]{x1D707}(y_{2})\nonumber\\ \displaystyle & & \displaystyle -\,N^{2}\mathop{\sum }_{i}\iint _{V_{i}\times V_{i}}f(y_{1},y_{2})\,d\unicode[STIX]{x1D707}(y_{1})\,d\unicode[STIX]{x1D707}(y_{2})\nonumber\\ \displaystyle & = & \displaystyle N^{2}\iint _{{\mathcal{M}}\times {\mathcal{M}}}f(y_{1},y_{2})\,d\unicode[STIX]{x1D707}(y_{1})\,d\unicode[STIX]{x1D707}(y_{2})\nonumber\\ \displaystyle & & \displaystyle -\,N^{2}\mathop{\sum }_{i}\iint _{V_{i}\times V_{i}}f(y_{1},y_{2})\,d\unicode[STIX]{x1D707}(y_{1})\,d\unicode[STIX]{x1D707}(y_{2}).\nonumber\end{eqnarray}$$
This proves (3.10). ◻
Elements
$X_{N}=(x_{1},\ldots ,x_{N})\in \unicode[STIX]{x1D6FA}_{N}$
can be thought of as specific
$N$
-point distributions in the space
${\mathcal{M}}$
, and the corresponding sums of distances and discrepancies for
${\mathcal{D}}_{N}=X_{N}=\{x_{1},\ldots ,x_{N}\}\in \unicode[STIX]{x1D6FA}_{N}$
can be thought of as random variables on the probability space
$\unicode[STIX]{x1D6FA}_{N}$
. We put
$$\begin{eqnarray}\displaystyle \unicode[STIX]{x1D70C}[X_{N}] & = & \displaystyle \mathop{\sum }_{i\neq j}\unicode[STIX]{x1D70C}(x_{i},x_{j}),\end{eqnarray}$$
$$\begin{eqnarray}\displaystyle \unicode[STIX]{x1D703}_{r}^{\unicode[STIX]{x1D6E5}}[X_{N}] & = & \displaystyle \mathop{\sum }_{i\neq j}\unicode[STIX]{x1D703}_{r}^{\unicode[STIX]{x1D6E5}}(x_{i},x_{j}),\end{eqnarray}$$
$$\begin{eqnarray}\displaystyle \unicode[STIX]{x1D703}^{\unicode[STIX]{x1D6E5}}[\unicode[STIX]{x1D709},X_{N}] & = & \displaystyle \mathop{\sum }_{i\neq j}\unicode[STIX]{x1D703}^{\unicode[STIX]{x1D6E5}}(\unicode[STIX]{x1D709},x_{i},x_{j}),\end{eqnarray}$$
and
$$\begin{eqnarray}\displaystyle \unicode[STIX]{x1D706}_{r}[X_{N}] & = & \displaystyle \mathop{\sum }_{i}\unicode[STIX]{x1D706}_{r}(x_{i},x_{i})+\mathop{\sum }_{i\neq j}\unicode[STIX]{x1D706}_{r}(x_{i},x_{j}),\end{eqnarray}$$
$$\begin{eqnarray}\displaystyle \unicode[STIX]{x1D706}[\unicode[STIX]{x1D709},X_{N}] & = & \displaystyle \mathop{\sum }_{i}\unicode[STIX]{x1D706}(\unicode[STIX]{x1D709},x_{i},x_{i})+\mathop{\sum }_{i\neq j}\unicode[STIX]{x1D706}(\unicode[STIX]{x1D709},x_{i},x_{j}).\end{eqnarray}$$
The probabilistic invariance principle can be stated as follows.
Theorem 3.1. Let
${\mathcal{R}}_{N}$
be an equal-measure partition of a compact metric space
${\mathcal{M}}$
. Then the expectations of the random variables (3.12)–(3.15) on the probability space
$\unicode[STIX]{x1D6FA}_{N}$
satisfy the relations
$$\begin{eqnarray}\mathbb{E}_{N}\unicode[STIX]{x1D706}_{r}[\,\cdot \,]+\mathbb{E}_{N}\unicode[STIX]{x1D703}_{r}^{\unicode[STIX]{x1D6E5}}[\,\cdot \,]=\langle \unicode[STIX]{x1D703}_{r}^{\unicode[STIX]{x1D6E5}}\rangle N^{2}\end{eqnarray}$$
and
$$\begin{eqnarray}\mathbb{E}_{N}\unicode[STIX]{x1D706}[\unicode[STIX]{x1D709},\cdot \,]+\mathbb{E}_{N}\unicode[STIX]{x1D703}^{\unicode[STIX]{x1D6E5}}[\unicode[STIX]{x1D709},\cdot \,]=\langle \unicode[STIX]{x1D703}^{\unicode[STIX]{x1D6E5}}(\unicode[STIX]{x1D709})\rangle N^{2}.\end{eqnarray}$$
Proof. Using (2.16) with
$(y_{1},y_{2})=(x_{i},x_{j})$
and, summing over
$x_{i},x_{j}\in X_{N}$
, we obtain
$$\begin{eqnarray}\unicode[STIX]{x1D706}_{r}[X_{N}]+\unicode[STIX]{x1D703}_{r}^{\unicode[STIX]{x1D6E5}}[X_{N}]=N^{2}A_{r}^{(0)}+2NA_{r}^{(1)}[X_{N}],\end{eqnarray}$$
where
$$\begin{eqnarray}A_{r}^{(1)}[X_{N}]=\mathop{\sum }_{i}A_{r}^{(1)}(x_{i}).\end{eqnarray}$$
We next calculate the expectation
$\mathbb{E}_{N}$
of both sides in (3.18). Combining (3.9) with (2.17), (2.18) and (2.6), we find that
$$\begin{eqnarray}\displaystyle & & \displaystyle \mathbb{E}_{N}\unicode[STIX]{x1D706}_{r}[\,\cdot \,]+\mathbb{E}_{N}\unicode[STIX]{x1D703}_{r}^{\unicode[STIX]{x1D6E5}}[\,\cdot \,]\nonumber\\ \displaystyle & & \displaystyle \quad =N^{2}A_{r}^{(0)}+2\mathbb{E}_{N}A_{r}^{(1)}[\,\cdot \,]=N^{2}A_{r}^{(0)}+2N^{2}\int _{{\mathcal{M}}}A_{r}^{(1)}(y)\,d\unicode[STIX]{x1D707}(y)\nonumber\\ \displaystyle & & \displaystyle \quad =N^{2}\int _{{\mathcal{M}}}\unicode[STIX]{x1D707}(B_{r}(y))^{2}\,d\unicode[STIX]{x1D707}(y)+N^{2}\int _{{\mathcal{M}}}\unicode[STIX]{x1D707}(B_{r}(y))\,d\unicode[STIX]{x1D707}(y)\nonumber\\ \displaystyle & & \displaystyle \qquad -\,2N^{2}\int _{{\mathcal{M}}}(B_{r}(y))^{2}\,d\unicode[STIX]{x1D707}(y)\nonumber\\ \displaystyle & & \displaystyle \quad =N^{2}\int _{{\mathcal{M}}}\big(\unicode[STIX]{x1D707}(B_{r}(y))-\unicode[STIX]{x1D707}(B_{r}(y))^{2}\big)\,d\unicode[STIX]{x1D707}(y)=\langle \unicode[STIX]{x1D703}_{r}^{\unicode[STIX]{x1D6E5}}\rangle N^{2}.\nonumber\end{eqnarray}$$
This establishes (3.16).
Integrating (3.16) over
$r\in T$
with respect to the measure
$\unicode[STIX]{x1D709}$
, we obtain (3.17).◻
We wish to evaluate the expectation (3.7) of the random variable (3.11) for an arbitrary metric
$\unicode[STIX]{x1D70C}$
.
Lemma 3.2. For any equal-measure partition
${\mathcal{R}}_{N}$
of the space
${\mathcal{M}}$
and any arbitrary metric
$\unicode[STIX]{x1D70C}$
on
${\mathcal{M}}$
, we have
$$\begin{eqnarray}\mathbb{E}_{N}\unicode[STIX]{x1D70C}[\,\cdot \,]\geqslant \langle \unicode[STIX]{x1D70C}\rangle N^{2}-\operatorname{Diam}_{1}({\mathcal{R}}_{N},\unicode[STIX]{x1D70C})N\geqslant \langle \unicode[STIX]{x1D70C}\rangle N^{2}-\operatorname{Diam}_{\infty }({\mathcal{R}}_{N},\unicode[STIX]{x1D70C})N.\end{eqnarray}$$
Proof. Applying (3.10) to the random variable (3.11), we obtain
$$\begin{eqnarray}\mathbb{E}_{N}\unicode[STIX]{x1D70C}[\,\cdot \,]=\langle \unicode[STIX]{x1D70C}\rangle N^{2}-Q_{N}(\unicode[STIX]{x1D70C})N^{2},\end{eqnarray}$$
where
$$\begin{eqnarray}\displaystyle Q_{N}(\unicode[STIX]{x1D70C}) & = & \displaystyle \mathop{\sum }_{i}\iint _{V_{i}\times V_{i}}\unicode[STIX]{x1D70C}(y_{1},y_{2})\,d\unicode[STIX]{x1D707}(y_{1})\,d\unicode[STIX]{x1D707}(y_{2})\leqslant N^{-2}\mathop{\sum }_{i}\operatorname{diam}(V_{i},\unicode[STIX]{x1D70C})\nonumber\\ \displaystyle & = & \displaystyle \operatorname{Diam}_{1}({\mathcal{R}}_{N},\unicode[STIX]{x1D70C})N^{-1}\leqslant \operatorname{Diam}_{\infty }({\mathcal{R}}_{N},\unicode[STIX]{x1D70C})N^{-1},\nonumber\end{eqnarray}$$
and (3.19) follows. ◻
Distributions
$X_{N}\in \unicode[STIX]{x1D6FA}_{N}$
form a subset in the set of all
$N$
-point distributions
${\mathcal{D}}_{N}\subset {\mathcal{M}}$
. Hence
$$\begin{eqnarray}\unicode[STIX]{x1D70C}_{N}\geqslant \mathbb{E}_{N}\unicode[STIX]{x1D70C}[\,\cdot \,]\quad \text{and}\quad \unicode[STIX]{x1D706}_{N}(\unicode[STIX]{x1D709})\leqslant \mathbb{E}_{N}\unicode[STIX]{x1D706}[\unicode[STIX]{x1D709},\cdot \,].\end{eqnarray}$$
Using these inequalities together with Lemma 3.2 and Theorem 3.1, we arrive at the following basic bounds.
Theorem 3.2. Let
${\mathcal{R}}_{N}$
be an equal-measure partition of a compact metric space
${\mathcal{M}}$
with a metric
$\unicode[STIX]{x1D703}$
and a measure
$\unicode[STIX]{x1D707}$
. Then the following hold.
-
(i) If a metric
$\unicode[STIX]{x1D70C}$
on
${\mathcal{M}}$
satisfies the inequality (3.21)with a constant
$$\begin{eqnarray}\unicode[STIX]{x1D70C}(x_{1},x_{2})\leqslant c_{0}\unicode[STIX]{x1D703}(x_{1},x_{2})\end{eqnarray}$$
$c_{0}>0$
, then (3.22)
$$\begin{eqnarray}\displaystyle \unicode[STIX]{x1D70C}_{N} & {\geqslant} & \displaystyle \langle \unicode[STIX]{x1D70C}\rangle N^{2}-c_{0}\operatorname{Diam}_{1}({\mathcal{R}}_{N},\unicode[STIX]{x1D703})N\nonumber\\ \displaystyle & {\geqslant} & \displaystyle \langle \unicode[STIX]{x1D70C}\rangle N^{2}-c_{0}\operatorname{Diam}_{\infty }({\mathcal{R}}_{N},\unicode[STIX]{x1D703})N.\end{eqnarray}$$
-
(ii) If the metric
$\unicode[STIX]{x1D703}^{\unicode[STIX]{x1D6E5}}(\unicode[STIX]{x1D709})$
satisfies the inequality (3.23)with a constant
$$\begin{eqnarray}\unicode[STIX]{x1D703}^{\unicode[STIX]{x1D6E5}}(\unicode[STIX]{x1D709},x_{1},x_{2})\leqslant c_{0}\unicode[STIX]{x1D703}(x_{1},x_{2})\end{eqnarray}$$
$c_{0}>0$
, then (3.24)and
$$\begin{eqnarray}\displaystyle \unicode[STIX]{x1D703}_{N}^{\unicode[STIX]{x1D6E5}}(\unicode[STIX]{x1D709}) & {\geqslant} & \displaystyle \langle \unicode[STIX]{x1D703}^{\unicode[STIX]{x1D6E5}}(\unicode[STIX]{x1D709})\rangle N^{2}-c_{0}\operatorname{Diam}_{1}({\mathcal{R}}_{N},\unicode[STIX]{x1D703})N\nonumber\\ \displaystyle & {\geqslant} & \displaystyle \langle \unicode[STIX]{x1D703}^{\unicode[STIX]{x1D6E5}}(\unicode[STIX]{x1D709})\rangle N^{2}-c_{0}\operatorname{Diam}_{\infty }({\mathcal{R}}_{N},\unicode[STIX]{x1D703})N\end{eqnarray}$$
(3.25)
$$\begin{eqnarray}\unicode[STIX]{x1D706}_{N}(\unicode[STIX]{x1D709})\leqslant c_{0}\operatorname{Diam}_{1}({\mathcal{R}}_{N},\unicode[STIX]{x1D703})N\leqslant c_{0}\operatorname{Diam}_{\infty }({\mathcal{R}}_{N},\unicode[STIX]{x1D703})N.\end{eqnarray}$$
Proof. Comparing the left-hand inequality in (3.20) with (3.19) and using (3.5), we obtain (3.22). The bound (3.24) coincides with (3.22) written for the metric
$\unicode[STIX]{x1D703}^{\unicode[STIX]{x1D6E5}}(\unicode[STIX]{x1D709})$
. The invariance principle (3.17) together with (3.20) gives
$$\begin{eqnarray}\unicode[STIX]{x1D706}_{N}(\unicode[STIX]{x1D709})\leqslant \langle \unicode[STIX]{x1D703}^{\unicode[STIX]{x1D6E5}}(\unicode[STIX]{x1D709})\rangle N^{2}-\unicode[STIX]{x1D703}_{N}^{\unicode[STIX]{x1D6E5}}(\unicode[STIX]{x1D709}).\end{eqnarray}$$
4 Equal-measure partitions of small average diameter
In the next section we shall prove the following general result.
Theorem 4.1. Suppose that a compact metric space
${\mathcal{M}}$
, with a metric
$\unicode[STIX]{x1D703}$
and a measure
$\unicode[STIX]{x1D707}$
, is
$d$
-rectifiable. Then for each
$N$
, there exists an equal-measure partition
${\mathcal{R}}_{N}$
of the space
${\mathcal{M}}$
such that
$$\begin{eqnarray}\operatorname{Diam}_{1}({\mathcal{R}}_{N},\unicode[STIX]{x1D703})\leqslant d2^{d-1}\operatorname{Lip}(f)N^{-1/d},\end{eqnarray}$$
where
$\operatorname{Lip}(f)$
is the Lipschitz constant of the map
$f$
in the definition of
$d$
-rectifiability of the space
${\mathcal{M}}$
.
Comparing Theorems 3.2 and 4.1, we arrive immediately at the following result.
Theorem 4.2. Suppose that a compact metric space
${\mathcal{M}}$
, with a metric
$\unicode[STIX]{x1D703}$
and a measure
$\unicode[STIX]{x1D707}$
, is
$d$
-rectifiable. Write
$C=d2^{d-1}\operatorname{Lip}(f)$
. Then the following hold.
-
(i) If a metric
$\unicode[STIX]{x1D70C}$
on
${\mathcal{M}}$
satisfies the inequality (4.2)with a constant
$$\begin{eqnarray}\unicode[STIX]{x1D70C}(x_{1},x_{2})\leqslant c_{0}\unicode[STIX]{x1D703}(x_{1},x_{2})\end{eqnarray}$$
$c_{0}>0$
, then (4.3)
$$\begin{eqnarray}\unicode[STIX]{x1D70C}_{N}\geqslant \langle \unicode[STIX]{x1D70C}\rangle N^{2}-c_{0}\mathit{CN}^{1-1/d}.\end{eqnarray}$$
-
(ii) If the metric
$\unicode[STIX]{x1D703}^{\unicode[STIX]{x1D6E5}}(\unicode[STIX]{x1D709})$
satisfies the inequality (4.4)with a constant
$$\begin{eqnarray}\unicode[STIX]{x1D703}^{\unicode[STIX]{x1D6E5}}(\unicode[STIX]{x1D709},x_{1},x_{2})\leqslant c_{0}\unicode[STIX]{x1D703}(x_{1},x_{2})\end{eqnarray}$$
$c_{0}>0$
, then (4.5)and
$$\begin{eqnarray}\unicode[STIX]{x1D703}_{N}^{\unicode[STIX]{x1D6E5}}(\unicode[STIX]{x1D709})\geqslant \langle \unicode[STIX]{x1D703}^{\unicode[STIX]{x1D6E5}}(\unicode[STIX]{x1D709})\rangle N^{2}-c_{0}\mathit{CN}^{1-1/d}\end{eqnarray}$$
(4.6)
$$\begin{eqnarray}\unicode[STIX]{x1D706}_{N}(\unicode[STIX]{x1D709})\leqslant c_{0}\mathit{CN}^{1-1/d}.\end{eqnarray}$$
Remark 4.1. Notice that all the statements of Theorem 4.1 hold for an arbitrary compact
$d$
-dimensional Riemannian manifold with the geodesic metric
$\unicode[STIX]{x1D703}$
and the Riemannian measure
$\unicode[STIX]{x1D707}$
, since such manifolds are
$d$
-rectifiable; see Remark 1.1. Applications of Theorem 4.1 to compact Riemannian symmetric spaces of rank one (two-point homogeneous spaces) are considered in our paper [Reference Skriganov12] .
Theorem 1.1 is a direct corollary of Theorem 4.2.
Proof of Theorem 1.1.
The statement (i) is a paraphrase of the statement (i) of Theorem 4.1. On the other hand, by Lemma 2.2, the inequality (4.4) is satisfied, and (4.6) implies (1.15). ◻
For spheres
$S^{d}$
, equal-measure partitions
${\mathcal{R}}_{N}$
can be constructed to satisfy
$$\begin{eqnarray}\operatorname{Diam}_{\infty }({\mathcal{R}}_{N},\unicode[STIX]{x1D703})\leqslant c(d)N^{-1/d},\end{eqnarray}$$
with a constant
$c(d)$
independent of
$N$
. The bound (4.7) has been used in many papers on point distributions on spheres
$S^{d}$
, see, for example, [Reference Alexander1, Reference Beck4, Reference Beck and Chen5, Reference Rakhmanov, Saff and Zhou11]. Its detailed proof can be found in [Reference Rakhmanov, Saff and Zhou11].
This last paper [Reference Rakhmanov, Saff and Zhou11] is the first in the literature that describes and quantifies the equal-area partitioning of the sphere with small diameter. It is clear that the bound (4.7) is stronger than (4.1); cf. (3.4). However, the construction of equal-measure partitions
${\mathcal{R}}_{N}$
satisfying (4.7) depends significantly on the geometry of spheres
$S^{d}$
as smooth submanifolds in
$\mathbb{R}^{d+1}$
, while the bound (4.1) holds for arbitrary compact
$d$
-rectifiable metric spaces. Furthermore, the bound (4.1) is not very sensitive to variation of metric and measure on a given space
${\mathcal{M}}$
. In any case, the bound (4.1) suffices to prove Theorem 1.1.
5 Construction of equal-measure partitions of small average diameter
The proof of Theorem 4.1 relies on three auxiliary results. Lemma 5.1 is trivial but uses at each stage our inductive construction. Our construction of partitions is described in Lemma 5.2 for a special case of a measure concentrated on the
$d$
-dimensional unit cube. The bound (4.1) for such equal measure partitions of the unit cube is given in Lemma 5.3. Once these partitions of the unit cube are constructed, the proof of Theorem 4.1 can be easily completed in view of Definition 1.1.
Let
$\unicode[STIX]{x1D708}_{0}$
be a finite non-negative measure on the unit interval
$I\,=\,[0,1]$
. Suppose that the measure
$\unicode[STIX]{x1D708}_{0}$
is continuous, i.e. it does not have a discrete component. Then the distribution function
$\unicode[STIX]{x1D711}(z)=\unicode[STIX]{x1D708}_{0}([0,z])$
,
$z\in I$
, is continuous, non-decreasing, and satisfies
$\unicode[STIX]{x1D711}(0)=0$
and
$\unicode[STIX]{x1D711}(1)=\unicode[STIX]{x1D708}_{0}(I)$
. Furthermore, there is a one-to-one correspondence between functions with such properties and finite continuous measures on
$I$
.
Since the graph of
$\unicode[STIX]{x1D711}$
can have horizontal parts, we define the inverse function
$\unicode[STIX]{x1D711}^{-1}$
by
$$\begin{eqnarray}\unicode[STIX]{x1D711}^{-1}(t)=\sup \{z:\unicode[STIX]{x1D711}(z)=t\},\quad t\in [0,\unicode[STIX]{x1D708}_{0}(I)].\end{eqnarray}$$
Let
$1\leqslant i\leqslant k$
be integers and
$$\begin{eqnarray}n=\mathop{\sum }_{i=1}^{k}n(i)\end{eqnarray}$$
be an arbitrary representation of
$n$
as a sum of
$k$
terms
$n(i)\geqslant 0$
. Define points
$\unicode[STIX]{x1D706}(0)=0<\unicode[STIX]{x1D706}(1)\leqslant \cdots \leqslant \unicode[STIX]{x1D706}(k)=1$
by
$$\begin{eqnarray}\unicode[STIX]{x1D706}(j)=\unicode[STIX]{x1D711}^{-1}\biggl(n^{-1}\mathop{\sum }_{i=1}^{j}n(i)\unicode[STIX]{x1D708}_{0}(I)\biggr),\quad 1\leqslant j\leqslant k,\end{eqnarray}$$
and consider the intervals
$\unicode[STIX]{x1D6E5}(j)=[\unicode[STIX]{x1D706}(j-1),\unicode[STIX]{x1D706}(j)]\subset I$
,
$1\leqslant j\leqslant k$
, of length
$\ell (j)=\unicode[STIX]{x1D706}(j)-\unicode[STIX]{x1D706}(j-1)$
. The following statement is obvious.
Lemma 5.1. The intervals
$\unicode[STIX]{x1D6E5}(j)$
,
$1\leqslant j\leqslant k$
, form a partition of the unit interval
$I$
,
$$\begin{eqnarray}I=\mathop{\bigcup }_{j=1}^{k}\unicode[STIX]{x1D6E5}(j),\qquad \mathop{\sum }_{j=1}^{k}\ell (j)=1,\qquad \unicode[STIX]{x1D708}_{0}(\unicode[STIX]{x1D6E5}(j_{1})\cap \unicode[STIX]{x1D6E5}(j_{2}))=0,\quad j_{1}\neq j_{2},\end{eqnarray}$$
and
$$\begin{eqnarray}\unicode[STIX]{x1D708}_{0}(\unicode[STIX]{x1D6E5}(j))=\frac{n(j)}{n}\unicode[STIX]{x1D708}_{0}(I).\end{eqnarray}$$
If the measure
$\unicode[STIX]{x1D708}_{0}\equiv 0$
identically, then for any
$n\geqslant 1$
and any representation (5.2), the partition given in Lemma 5.1 takes the form
$$\begin{eqnarray}\unicode[STIX]{x1D6E5}(1)=[0,1],\qquad \unicode[STIX]{x1D6E5}(j)=[1,1]=\{1\},\quad 2\leqslant j\leqslant k.\end{eqnarray}$$
We agree that the partition (5.6) takes place also for
$\unicode[STIX]{x1D708}_{0}\equiv 0$
and
$n=0$
.
We now wish to extend Lemma 5.1 to the
$d$
-dimensional unit cube
$I^{d}=[0,1]^{d}$
. Let
$N\geqslant 1$
be an integer, and let
$k=\lceil N^{1/d}\rceil$
, the smallest integer not less than
$N^{1/d}$
, so that
$N\leqslant k^{d}$
. Let
$$\begin{eqnarray}N=\mathop{\sum }_{i_{1},\ldots ,i_{d}=1}^{k}N(i_{1},\ldots ,i_{d})\end{eqnarray}$$
be an arbitrary representation of
$N$
as a sum of terms
$N(i_{1},\ldots ,i_{d})$
equal to
$0$
or
$1$
. Introduce the non-negative integers
$$\begin{eqnarray}N(i_{1},\ldots ,i_{q})=\mathop{\sum }_{i_{q+1},\ldots ,i_{d}=1}^{k}N(i_{1},\ldots ,i_{d}),\quad 1\leqslant q<d.\end{eqnarray}$$
These integers satisfy the relations
$$\begin{eqnarray}N(i_{1},\ldots ,i_{q})=\mathop{\sum }_{i_{q+1}=1}^{k}N(i_{1},\ldots ,i_{q+1}),\quad 1\leqslant q<d,\end{eqnarray}$$
and
$$\begin{eqnarray}N=\mathop{\sum }_{i_{1}=1}^{k}N(i_{1}).\end{eqnarray}$$
Let
$\unicode[STIX]{x1D708}$
be a finite non-negative measure on
$I^{d}$
with a continuous distribution function
$$\begin{eqnarray}\unicode[STIX]{x1D711}(Z)=\unicode[STIX]{x1D708}([0,z_{1}]\times \cdots \times [0,z_{d}]),\qquad Z=(z_{1},\ldots ,z_{d})\in I^{d}.\end{eqnarray}$$
Lemma 5.2. For any representation of an integer
$N$
as a sum (5.7), there exists a sequence of
$d$
partitions
${\mathcal{P}}(q)$
,
$q=1,\ldots ,d$
, of the unit cube
$I^{d}$
into rectangular boxes of the form
$$\begin{eqnarray}\unicode[STIX]{x1D6F1}(i_{1},\ldots ,i_{q})=\mathop{\prod }_{j=1}^{q}\unicode[STIX]{x1D6E5}(i_{1},\ldots ,i_{j})\times [0,1]^{d-q},\quad 1\leqslant i_{j}\leqslant k,\quad 1\leqslant j\leqslant q,\end{eqnarray}$$
where
$\unicode[STIX]{x1D6E5}(i_{1},\ldots ,i_{j})\subset I$
are intervals of length
$\ell (i_{1},\ldots ,i_{j})$
, such that the following hold.
-
(i) If the indices
$i_{1},\ldots ,i_{j-1}$
are fixed, then the intervals
$\unicode[STIX]{x1D6E5}(i_{1},\ldots ,i_{j-1},i_{j})$
,
$i_{j}=1,\ldots ,k$
, form a partition of
$I$
, and (5.13)
$$\begin{eqnarray}\mathop{\sum }_{i_{j}=1}^{k}\ell (i_{1},\ldots ,i_{j-1},i_{j})=1.\end{eqnarray}$$
-
(ii) The measures of the rectangular boxes (5.12) satisfy
(5.14)
$$\begin{eqnarray}\unicode[STIX]{x1D708}(\unicode[STIX]{x1D6F1}(i_{1},\ldots ,i_{q}))=\frac{N(i_{1},\ldots ,i_{q})}{N}\unicode[STIX]{x1D708}(I^{d}).\end{eqnarray}$$
Proof. We shall construct the sequence of partitions
${\mathcal{P}}(q)$
,
$q=1,\ldots ,d$
, by induction on
$q$
.
At the first stage, we define the partition
${\mathcal{P}}(1)$
as follows. Consider the one-dimensional distribution function
$$\begin{eqnarray}\unicode[STIX]{x1D711}(z_{1})=\unicode[STIX]{x1D708}([0,z_{1}])\times [0,1]^{d-1} )=\unicode[STIX]{x1D708}_{0}([0,z_{1}]),\quad z_{1}\in I,\end{eqnarray}$$
where
$\unicode[STIX]{x1D708}_{0}$
is the corresponding measure on
$I$
,
$\unicode[STIX]{x1D708}_{0}(I)=\unicode[STIX]{x1D708}(I^{d})$
. Putting
$n=N$
,
$n(i_{1})=N(i_{1})$
in (5.2) with
$i=i_{1}$
, and applying Lemma 5.1 with the function (5.15), we obtain a partition of
$I$
into intervals
$\unicode[STIX]{x1D6E5}(i_{1})$
of length
$l(i_{1})$
,
$i_{1}=1,\ldots ,d$
, with
$$\begin{eqnarray}\mathop{\sum }_{i_{1}=1}^{k}\ell (i_{1})=1.\end{eqnarray}$$
Let
$\unicode[STIX]{x1D6F1}(i_{1})=\unicode[STIX]{x1D6E5}(i_{1})\times [0,1]^{d-1}\subset I^{d}$
. Then
$$\begin{eqnarray}\unicode[STIX]{x1D708}(\unicode[STIX]{x1D6F1}(i_{1}))=\unicode[STIX]{x1D708}_{0}(\unicode[STIX]{x1D6E5}(i_{1}))=\frac{N(i_{1})}{N}\unicode[STIX]{x1D708}(I^{d}).\end{eqnarray}$$
The partition
${\mathcal{P}}(1)$
is now constructed.
Assume now that the partition
${\mathcal{P}}(q)$
is constructed already for some
$q$
,
$1\leqslant q<d$
. Then we define the partition
${\mathcal{P}}(q+1)$
as follows. For each rectangular box of the form (5.12), we consider the one-dimensional distribution function
$$\begin{eqnarray}\displaystyle \unicode[STIX]{x1D711}(i_{1},\ldots ,i_{q},z_{q+1}) & = & \displaystyle \unicode[STIX]{x1D708}\biggl(\mathop{\prod }_{j=1}^{q}\unicode[STIX]{x1D6E5}(i_{1},\ldots ,i_{j})\times [0,z_{q+1}]\times [0,1]^{d-q-1}\biggr)\nonumber\\ \displaystyle & = & \displaystyle \unicode[STIX]{x1D708}_{0}^{(i_{1},\ldots ,i_{q})}([0,z_{q+1}]),\quad z_{q+1}\in I,\end{eqnarray}$$
where
$\unicode[STIX]{x1D708}_{0}^{(i_{1},\ldots ,i_{q})}$
is the corresponding measure on
$I$
, and
$$\begin{eqnarray}\unicode[STIX]{x1D708}_{0}^{(i_{1},\ldots ,i_{q})}(I)=\unicode[STIX]{x1D708}(\unicode[STIX]{x1D6F1}(i_{1},\ldots ,i_{q}))=\frac{N(i_{1},\ldots ,i_{q})}{N}\unicode[STIX]{x1D708}(I^{d}).\end{eqnarray}$$
Putting
$n=N(i_{1},\ldots ,i_{q})$
,
$n(i_{q+1})=N(i_{1},\ldots ,i_{q},i_{q+1})$
in (5.2) with
$i=i_{q+1}$
, and applying Lemma 5.1 with the function (5.16), we obtain a partition of
$I$
into intervals
$\unicode[STIX]{x1D6E5}(i_{1},\ldots ,i_{q},i_{q+1})$
,
$1\leqslant i_{q+1}\leqslant k$
, of length
$\ell (i_{1},\ldots ,i_{q},i_{q+1})$
such that
$$\begin{eqnarray}\mathop{\sum }_{i_{q+1}=1}^{k}\ell (i_{1},\ldots ,i_{q},i_{q+1})=1.\end{eqnarray}$$
Let
$$\begin{eqnarray}\unicode[STIX]{x1D6F1}(i_{1},\ldots ,i_{q+1})=\mathop{\prod }_{j=1}^{q+1}\unicode[STIX]{x1D6E5}(i_{1},\ldots ,i_{j})\times [0,1]^{d-q-1}.\end{eqnarray}$$
For these rectangular boxes, we have
$$\begin{eqnarray}\unicode[STIX]{x1D708}(\unicode[STIX]{x1D6F1}(i_{1},\ldots ,i_{q+1}))=\frac{N(i_{1},\ldots ,i_{q+1})}{N}\unicode[STIX]{x1D708}(I^{d}).\end{eqnarray}$$
Indeed, if
$N(i_{1},\ldots ,i_{q})\geqslant 1$
, then in view of (5.17), we have
$$\begin{eqnarray}\displaystyle \unicode[STIX]{x1D708}(\unicode[STIX]{x1D6F1}(i_{1},\ldots ,i_{q+1})) & = & \displaystyle \frac{N(i_{1},\ldots ,i_{q+1})}{N(i_{1},\ldots ,i_{q})}\unicode[STIX]{x1D708}(\unicode[STIX]{x1D6F1}(i_{1},\ldots ,i_{q}))\nonumber\\ \displaystyle & = & \displaystyle \frac{N(i_{1},\ldots ,i_{q+1})}{N}\unicode[STIX]{x1D708}(I^{d}).\nonumber\end{eqnarray}$$
If
$N(i_{1},\ldots ,i_{q})=0$
, then
$\unicode[STIX]{x1D708}(\unicode[STIX]{x1D6F1}(i_{1},\ldots ,i_{q}))=0$
, and the intervals
$\unicode[STIX]{x1D6E5}(i_{1},\ldots ,i_{q},i_{q+1})$
,
$1\leqslant i_{q+1}\leqslant k$
, are defined by (5.6). Hence
$\unicode[STIX]{x1D708}(\unicode[STIX]{x1D6F1}(i_{1},\ldots ,i_{q+1}))=0$
and (5.19) holds also. The partition
${\mathcal{P}}(q+1)$
is now constructed.◻
Consider the partition
${\mathcal{P}}(d)$
constructed in Lemma 5.2. We have
$$\begin{eqnarray}\unicode[STIX]{x1D708}(\unicode[STIX]{x1D6F1}(i_{i},\ldots ,i_{d}))=\frac{N(i_{1},\ldots ,i_{d})}{N}\unicode[STIX]{x1D708}(I^{d}),\end{eqnarray}$$
where, by definition, the terms
$N(i_{1},\ldots ,i_{d})$
are equal to
$0$
or
$1$
, and the number of terms such that
$N(i_{1},\ldots ,i_{d})=1$
is equal to
$N$
; see (5.7).
Introduce the partition
$$\begin{eqnarray}{\mathcal{P}}_{N}=\{\unicode[STIX]{x1D6F1}(\unicode[STIX]{x1D6FC}),\unicode[STIX]{x1D6FC}\in {\mathcal{A}}\}\end{eqnarray}$$
of the unit cube, where
$$\begin{eqnarray}{\mathcal{A}}=\{\unicode[STIX]{x1D6FC}=(i_{1},\ldots ,i_{d}):N(i_{1},\ldots ,i_{d})=1\},\quad \#{\mathcal{A}}=N.\end{eqnarray}$$
We write
$$\begin{eqnarray}\operatorname{Diam}_{1}({\mathcal{P}}_{N})=\frac{1}{N}\mathop{\sum }_{\unicode[STIX]{x1D6FC}\in {\mathcal{A}}}\operatorname{diam}(\unicode[STIX]{x1D6F1}(\unicode[STIX]{x1D6FC}),\Vert \,\cdot \,\Vert )\end{eqnarray}$$
for the average diameter of the partition
${\mathcal{P}}_{N}$
with respect to the Euclidean metric.
Lemma 5.3. The partition
${\mathcal{P}}_{N}=\{\unicode[STIX]{x1D6F1}(\unicode[STIX]{x1D6FC}),\unicode[STIX]{x1D6FC}\in {\mathcal{A}}\}$
is an equal-measure partition, so that
$$\begin{eqnarray}\unicode[STIX]{x1D708}(\unicode[STIX]{x1D6F1}(\unicode[STIX]{x1D6FC}))=N^{-1}\unicode[STIX]{x1D708}(I^{d}),\quad \unicode[STIX]{x1D6FC}\in {\mathcal{A}}.\end{eqnarray}$$
Furthermore,
$$\begin{eqnarray}\operatorname{Diam}_{1}({\mathcal{P}}_{N})<d2^{d-1}N^{-1/d}.\end{eqnarray}$$
Proof. Note that (5.23) follows from (5.20) and the definition (5.21).
On the other hand, the Euclidean diameter of a rectangular box
$\unicode[STIX]{x1D6F1}(i_{1},\ldots ,i_{d})$
does not exceed the sum of lengths of its sides. In other words,
$$\begin{eqnarray}\operatorname{diam}(\unicode[STIX]{x1D6F1}(i_{1},\ldots ,i_{d}),\Vert \,\cdot \,\Vert )\leqslant \ell (i_{1})+\ell (i_{1},i_{2})+\cdots +\ell (i_{1},\ldots ,i_{d}),\end{eqnarray}$$
where
$\ell (i_{1},\ldots ,i_{j})$
,
$1\leqslant j\leqslant d$
, are the lengths of the interval
$\unicode[STIX]{x1D6E5}(i_{1},\ldots ,i_{j})$
; see (5.12). Using (5.25), (5.22) and (5.13), we obtain
$$\begin{eqnarray}\displaystyle N\operatorname{Diam}_{1}({\mathcal{P}}_{N}) & {\leqslant} & \displaystyle \mathop{\sum }_{i_{1},\ldots ,i_{d}=1}^{k}\!\!\operatorname{diam}(\unicode[STIX]{x1D6F1}(i_{1},\ldots ,i_{d}),\Vert \,\cdot \,\Vert )\leqslant \mathop{\sum }_{j=1}^{d}\,\mathop{\sum }_{i_{1},\ldots ,i_{d}=1}^{k}\!\!\ell (i_{1},\ldots ,i_{j})\nonumber\\ \displaystyle & = & \displaystyle \mathop{\sum }_{j=1}^{d}k^{d-j}\mathop{\sum }_{i_{1},\ldots ,i_{j=1}}^{k}\ell (i_{1},\ldots ,i_{j})=\mathop{\sum }_{j=1}^{d}k^{d-1}=dk^{d-1}.\nonumber\end{eqnarray}$$
Since
$k=\lceil N^{1/d}\rceil$
and
$k<N^{1/d}+1$
, we have
$$\begin{eqnarray}N\operatorname{Diam}_{1}({\mathcal{P}}_{N})<d(N^{1/d}+1)^{d-1}=d(1+N^{-1/d})^{d-1}N^{1-1/d}\leqslant d2^{d-1}N^{1-1/d},\end{eqnarray}$$
and (5.24) follows. ◻
Proof of Theorem 4.1.
Let
${\mathcal{M}}$
be a
$d$
-rectifiable space. Without loss of generality, we can assume in Definition 1.1 that the measure
$\unicode[STIX]{x1D708}$
is concentrated on the subset
${\mathcal{O}}\subset I^{d}$
and that both measures
$\unicode[STIX]{x1D707}$
and
$\unicode[STIX]{x1D708}$
are normalized so that
$\unicode[STIX]{x1D707}({\mathcal{M}})=1$
and
$\unicode[STIX]{x1D708}({\mathcal{O}})=1$
.
Since the measure
$\unicode[STIX]{x1D708}$
is absolutely continuous with respect to Lebesgue measure on
$I^{d}$
, its distribution function (5.11) is continuous, so Lemmas 5.2 and 5.3 can be applied.
For the measure
$\unicode[STIX]{x1D708}$
, we consider the equal-measure partition
${\mathcal{P}}_{N}$
of the unit cube
$I^{d}$
given in Lemma 5.3. Consider the collection of subsets
$$\begin{eqnarray}{\mathcal{R}}_{N}=\{V(\unicode[STIX]{x1D6FC}),\unicode[STIX]{x1D6FC}\in {\mathcal{A}}\},\qquad V(\unicode[STIX]{x1D6FC})=f(\unicode[STIX]{x1D6F1}(\unicode[STIX]{x1D6FC})\cap {\mathcal{O}}),\end{eqnarray}$$
in the space
${\mathcal{M}}$
. Using (1.13), we obtain
$$\begin{eqnarray}\unicode[STIX]{x1D707}(V(\unicode[STIX]{x1D6FC}))=\unicode[STIX]{x1D708}(\unicode[STIX]{x1D6F1}(\unicode[STIX]{x1D6FC})\cap {\mathcal{O}})=\unicode[STIX]{x1D708}(\unicode[STIX]{x1D6F1}(\unicode[STIX]{x1D6FC}))=N^{-1},\end{eqnarray}$$
since the measure
$\unicode[STIX]{x1D708}$
is concentrated on
${\mathcal{O}}$
. By definition, the map
$f:{\mathcal{O}}\rightarrow {\mathcal{M}}$
is an injection. Hence
$$\begin{eqnarray}\unicode[STIX]{x1D707}(V(\unicode[STIX]{x1D6FC}_{1})\cap V(\unicode[STIX]{x1D6FC}_{2}))=\unicode[STIX]{x1D708}(\unicode[STIX]{x1D6F1}(\unicode[STIX]{x1D6FC}_{1})\cap \unicode[STIX]{x1D6F1}(\unicode[STIX]{x1D6FC}_{2})\cap {\mathcal{O}})=0,\quad \unicode[STIX]{x1D6FC}_{1}\neq \unicode[STIX]{x1D6FC}_{2}.\end{eqnarray}$$
Thus the collection of subsets (5.26) is an equal-measure partition of
${\mathcal{M}}$
. By definition, the map
$f:{\mathcal{O}}\rightarrow {\mathcal{M}}$
is also a Lipschitz map. Therefore
$$\begin{eqnarray}\operatorname{diam}(V(\unicode[STIX]{x1D6FC}),\unicode[STIX]{x1D703})\leqslant \operatorname{Lip}(f)\operatorname{diam}(\unicode[STIX]{x1D6F1}(\unicode[STIX]{x1D6FC})\cap {\mathcal{O}},\Vert \,\cdot \,\Vert )\leqslant \operatorname{Lip}(f)\operatorname{diam}(\unicode[STIX]{x1D6F1}(\unicode[STIX]{x1D6FC}),\Vert \,\cdot \,\Vert ).\end{eqnarray}$$
In view of (3.2) and (5.22), we have
$$\begin{eqnarray}\operatorname{Diam}_{1}({\mathcal{R}}_{N},\unicode[STIX]{x1D703})\leqslant \operatorname{Lip}(f)\operatorname{Diam}_{1}({\mathcal{P}}_{N}).\end{eqnarray}$$
Substituting (5.24) into (5.27), we obtain the desired bound (4.1). ◻
