Intrinsic Volumes and Gaussian Polytopes:

The Missing Piece of the Jigsaw

Imre Bárány and Christoph Thäle

Received: June 25, 2016 Revised: July 7, 2017

Communicated by Friedrich Götze

Abstract. The intrinsic volumes of Gaussian polytopes are considered. A lower variance bound for these quantities is proved, showing that, under suitable normalization, the variances converge to strictly positive limits. The implications of this missing piece of the jigsaw in the theory of Gaussian polytopes are discussed.

2010 Mathematics Subject Classification: Primary 60D05; Secondary 52A22. Keywords and Phrases: Gaussian polytopes, random polytopes, stochastic geometry, variance lower bound.

1 Introduction and results

Fix a space dimension d ∈ ℕ and denote by γ_{d} the standard Gaussian measure on ℝ^{d} with density φ_{d} equal to

φ_{d}(x) := (2π)^{− \frac{d}{2}} exp ( − \frac{∥x∥^{2}}{2} ) ,  x ∈ ℝ^{d} .  (1)

Given n ≥ d + 1 let X_{1}, …, X_{n} be independent random points that are distributed on ℝ^{d} according to the probability measure γ_{d}. The random convex hull

K_{n} := [X_{1}, …, X_{n}]

of these points is a Gaussian polytope. These random polytopes are central objects considered in stochastic geometry and are also of importance in convex geometric analysis or coding theory. For example, Gluskin [8] has used Gaussian polytopes in his analysis of the diameter of the Minkowski compactum and Gaussian polytopes also arise as lower-dimensional shadows of randomly rotated high-dimensional regular simplices as shown by Baryshnikov and Vitale [4]. We refer to the survey article of Reitzner [12] for further background information and references.

We denote for ℓ ∈ {0, …, d} by V_{ℓ}(K_{n}) the ℓth intrinsic volume of K_{n}, that is,

V_{ℓ}(K_{n}) = \binom{d}{ℓ}\frac{κ_{d}}{κ_{ℓ}κ_{d−ℓ}} ∫_{𝔾(d,ℓ)} vol_{ℓ}(K_{n}|L) ν_{ℓ}(dL) .

Here, 𝔾(d, ℓ) is the Grassmannian of ℓ-dimensional linear subspaces of ℝ^{d} supplied with the unique Haar probability measure ν_{ℓ} and vol_{ℓ}(K_{n}|L) stands for the ℓ-dimensional Lebesgue measure of the orthogonal projection K_{n}|L of K_{n} onto L measured within the subspace L. Moreover, for j ∈ ℕ, κ_{j} := π^{j/2} Γ(1 + \frac{j}{2})^{−1} denotes the volume of the j-dimensional unit ball. The intrinsic volumes are of outstanding importance in convex geometry, since according to a classical theorem of Hadwiger they form a basis of the vector space of all continuous and rigid-motion invariant real-valued valuations on convex sets, cf. [14]. For example, V_{d}(K_{n}) = vol_{d}(K_{n}) is the volume, 2V_{d−1}(K_{n}) coincides with the surface area and \frac{2κ_{d−1}}{dκ_{d}} V_{1}(K_{n}) corresponds to the mean width of K_{n}.

It is well known from the work of Affentranger [1] that the expectation E[V_{ℓ}(K_{n})] of V_{ℓ}(K_{n}) satisfies

lim_{n→∞}(log n)^{− \frac{ℓ}{2}} E[V_{ℓ}(K_{n})] = \binom{d}{ℓ}\frac{κ_{d}}{κ_{d−ℓ}} .

More recently, the asymptotic behaviour of the variance Var[V_{ℓ}(K_{n})] of V_{ℓ}(K_{n}) has moved into the focus of attention. Using the classical Efron-Stein jackknife inequality Hug and Reitzner [10] have obtained a first upper bound of the form Var[V_{ℓ}(K_{n})] ≤ c_{d}(log n)^{\frac{ℓ−3}{2}} with a constant c_{d} ∈ (0, ∞) only depending on the space dimension d (but not on ℓ). In a remarkable paper of Calka and Yukich [7] the precise variance asymptotic was derived, showing thereby that the upper bound from [10] does not have the right order of magnitude. In fact, [7, Theorem 1.5] says that

lim_{n→∞}(log n)^{\frac{d+3}{2} −ℓ} Var[V_{ℓ}(K_{n})] = c_{d,ℓ} ,  (2)

with constants c_{d,ℓ} ∈ [0, ∞) only depending on d and on ℓ. However, using their methods the authors of [7] were not able to exclude the possibility that c_{d,ℓ} = 0. The aim of the present paper is to fill this gap and to show that, in fact, c_{d,ℓ} > 0. This answers a question raised at several places in the literature, see [3, Section 14], the comment after [7, Theorem 1.5] or [9, Remark 3.6]. Our result reads as follows:

Theorem 1. Let ℓ ∈ {1, …, d} and let K_{n} be a Gaussian polytope. Then there exists a constant v_{d,ℓ} ∈ (0, ∞) only depending on d and on ℓ such that

Var[V_{ℓ}(K_{n})] ≥ v_{d,ℓ} (log n)^{− \frac{d+3}{2} +ℓ} ,

whenever n is sufficiently large.

In particular, Theorem 1 in conjunction with (2) shows that the limit

lim_{n→∞}(log n)^{\frac{d+3}{2} −ℓ} Var[V_{ℓ}(K_{n})] = c_{d,ℓ}

exists and takes a strictly positive and finite value.

Remark 2. (i) Let us first comment on the boundary case ℓ = 0 in Theorem 1. Since V_{0}(K) = 1_{{K≠∅}} for any convex set K ⊂ ℝ^{d}, we have that V_{0}(K_{n}) = 1 with probability one and hence Var[V_{0}(K_{n})] = 0.

(ii) Since V_{d}(K_{n}) is the volume of the Gaussian polytope K_{n}, the case ℓ = d is already covered by Theorem 6.1 in [3], which ensures that v_{d,d} ∈ (0, ∞). Our proof comprises this situation as a special case.

A random polytope model closely related to K_{n} can be described as follows. For each n ∈ ℕ let η_{n} be a Poisson point process on ℝ^{d} with intensity measure nγ_{d}. The convex hull of the points of η_{n} will be denoted by Π_{n} and is called the Gaussian Poisson polytope. Following the coupling construction in the proof of [3, Lemma 7.1] one easily sees that expectation and variance asymptotic for Π_{n} are literally the same as for K_{n}. Moreover, the strict positivity of the constants v_{d,ℓ} in Theorem 1 implies that (log n)^{\frac{d+3}{2} −ℓ}Var[V_{ℓ}(Π_{n})] converges to a positive and finite limit. We summarize the missing piece in the proof of this result in the following corollary:

Corollary 3. Let ℓ ∈ {1, …, d} and let Π_{n} be the Gaussian Poisson polytope. Then there exists a constant v_{d,ℓ} ∈ (0, ∞) only depending on d and on ℓ such that

Var[V_{ℓ}(Π_{n})] ≥ v_{d,ℓ} (log n)^{ℓ− \frac{d+3}{2}} ,

whenever n is sufficiently large.

The result of Theorem 1 and Corollary 3 can be regarded as the missing piece of the jigsaw in the theory of Gaussian polytopes. Let us mention some of the implications that are now immediate:

- Central limit theorems. As explained in [3, 7], the positivity of the limiting variance is the only missing piece in the proof of the central limit theorem for the normalized intrinsic volumes of Π_{n}. The result follows by the methods developed in [3, 6, 7]. Moreover, a de-Poissonization argument similar to that in [3] leads to the corresponding result for K_{n}; we omit the details.

- Concentration inequalities. As explained in the recent work [9], the positivity of the limiting variance is the only missing ingredient in the proof of a concentration inequality for V_{ℓ}(Π_{n}). The precise form of such an inequality can now be determined from [9, Theorem 3.1]: For any ℓ ∈ {1, …, d} one can find a constant c ∈ (0, ∞) only depending on d and on ℓ such that

P(|V_{ℓ}(Π_{n}) − E[V_{ℓ}(Π_{n})]| ≥ y \sqrt{Var[V_{ℓ}(Π_{n})]} )

≤ 2 exp ( − \frac{1}{4} min \{\frac{y^{2}}{2^{2d+ℓ+5}} , c (log n)^{\frac{d−1}{4(2d+ℓ+5)}} y^{\frac{1}{2d+ℓ+5}} \})

for all y ≥ 0 and sufficiently large n.

- Marcinkiewicz-Zygmund-type strong laws of large numbers. The concentration inequality for V_{ℓ}(Π_{n}) mentioned in the previous paragraph can directly be used to derive Marcinkiewicz-Zygmund-type strong laws of large numbers along the lines of the proof of [9, Theorem 1.3]: For any ℓ ∈ \{1, …, d\} and p > 1 − \frac{d+3}{ℓ} one has that

\frac{V_{ℓ}(Π_{n}) − E[V_{ℓ}(Π_{n})]}{(log n)^{p \frac{ℓ}{2}}} ⟶ 0

with probability one, as n → ∞. Using the monotonicity of intrinsic volumes and a simple coupling argument, one easily verifies that the same result also holds with Π_{n} replaced by K_{n}. In that form, this refines the ordinary strong law of large numbers from [10, Corollary 1.2], which corresponds to the special case p = 1.

- Moderate deviations. Moderate deviations for the volume and the face numbers of the Gaussian Poisson polytopes Π_{n} have also been investigated in [9]. Again, the only missing piece for the extension of these results to the intrinsic volumes is the positivity of the limiting variances; we omit the details.

Remark 4. Let λ > 0 be an arbitrary real number, let η_{λ} be a Poisson point process on ℝ^{d} with intensity measure λγ_{d} and denote by Π_{λ} the random convex hull induced by η_{λ}. Using the monotonicity of intrinsic volumes and a simple coupling argument, one easily verifies that the result of Corollary 3 continues to hold with Π_{n} and log n replaced by Π_{λ} and log λ, respectively. The same comment applies to the central limit theorem, the concentration inequalities, the Marcinkiewicz-Zygmund-type strong laws of large numbers and to the moderate deviations mentioned above.

The rest of this paper is structured as follows. In Section 2 we recall the essential steps of a geometric construction from [3] and proof some auxiliary results that are needed in the proof of Theorem 1. The latter is the content of the final Section 3.

2 Preparations

2.1 Notation

The symbols ∥ · ∥ and ⟨ · , · ⟩ are used for the Euclidean norm and scalar product in ℝ^{d}, respectively. Moreover, for a set B ⊂ ℝ^{d} we write [B] for the convex hull of B. We denote the d-dimensional unit ball by 𝔹^{d} := {x ∈ ℝ^{d} : ∥x∥ ≤ 1} and write 𝕊^{d−1} := {x ∈ ℝ^{d} : ∥x∥ = 1} for the corresponding unit sphere. The normalized surface measure on 𝕊^{d−1} is denoted by ν_{𝕊^{d−1}}. Further, for a point z ∈ ℝ^{d} \{0} and α ∈ [0, π/2] we write C(z, α) for the closed circular cone whose axis is the halfline {tz : t ≥ 0} and whose angle is α. More formally, if ∢(z, x) stands for the ordinary angle between z and another point x ∈ ℝ^{d}, C(z, α) is given by C(z, α) := {x ∈ ℝ^{d} : ∢(x, z) ≤ α}. Our underlying probability space is (Ω, A, P) and we implicitly assume that it is rich enough to carry all the random objects we consider in this paper. By E[ ·] we denote expectation (integration) with respect to P and Var[ ·] stands for the variance of the argument random variable. The indicator function of an event A ∈ A is denoted by 1_{A}. For two sequences (a_{n} : n ∈ ℕ) and (b_{n} : n ∈ ℕ) we write a_{n} ≪ b_{n} (or a_{n} ≫ b_{n}) if we can find a constant c ∈ (0, ∞) not depending on n and an index n_{0} ∈ ℕ such that a_{n} ≤ c b_{n} (or a_{n} ≥ c b_{n}) for all n ≥ n_{0}. Finally, a_{n} ≈ b_{n} means that a_{n} ≪ b_{n} ≪ a_{n}. In this paper constants are denoted by c_{1}, c_{2}, … It is implicitly assumed that these constants are finite and strictly positive, and only depend on the space dimension d, unless otherwise stated.

2.2 A geometric construction

In this section we recall a geometric construction as well as some of the results already obtained [3] that we use below. We define

r = r(n) := \sqrt{2 log n − log log n} , n ∈ ℕ ,

and denote by 𝕊(r) := {x ∈ ℝ^{d} : ∥x∥ = r} the centred sphere of radius r. By y_{1}, …, y_{m} ∈ 𝕊(r) we denote a maximal system of points such that ∥y_{i} − y_{j}∥ ≥ 2c_{1} for some sufficiently large c_{1}. A simple volume comparison argument provides an estimate for the size of such a set, see [3, Claim 5.1]:

Lemma 5. One has that m ≈ (log n)^{\frac{d−1}{2}} .

For each i ∈ {1, …, m} define y_{i}^{0} := (1+r^{−2})y_{i} and notice that ∥y_{i}−y_{i}^{0}∥ = r^{−1}. Let further for i ∈ {1, …, m}, H_{i} := {x ∈ ℝ^{d} : ⟨x, y_{i}⟩ = r} be the tangent hyperplane of 𝕊(r) at y_{i} and fix a regular simplex in H_{i} whose vertices y_{i}^{1}, …, y_{i}^{d} are chosen from the (d − 2)-dimensional sphere 𝕊^{d−2}(y_{i}, \sqrt{2}) of radius \sqrt{2} in H_{i} centred at y_{i}. (Thus 𝕊(r) = 𝕊(0, r) but we keep the simpler notation for 𝕊(r).) The simplex Δ_{i} := [y_{i}^{0}, y_{i}^{1}, …, y_{i}^{d}] is the convex hull of y_{i}^{0} and the points y_{i}^{1}, …, y_{i}^{d} ∈ H_{i}, see Figure 1. It is not difficult to estimate the volume V_{d}(Δ_{i}) and the Gaussian measure γ_{d}(Δ_{i}) of these simplices, see [3, Claim 5.2]:

𝕊(r) H_{i}  y_{i−1}  y_{i}  y_{i+1} y_{i}^{1}  y_{i}^{2} y_{i}^{0} Δ_{i}

Figure 1: Construction of the simplices Δ_{i}.

Lemma 6. For each i ∈ \{1, …, m\} one has that V_{d}(Δ_{i}) ≈ (log n)^{− \frac{1}{2}} and γ_{d}(Δ_{i}) ≈ n^{−1}.

For each i ∈ {1, …, m} and j ∈ {0, …, d} we let Δ_{i}^{j} be a homothetic copy of Δ_{i} with y_{i}^{j} being the centre of the homothety and the factor being a sufficiently small number c_{2}, that is, Δ_{i}^{j} := y_{i}^{j} + c_{2}(Δ_{i} − y_{i}^{j}). Let D_{i} be the the cone D_{i} := pos({y_{i}^{j} − y_{i}^{0} : j ∈ {1, …, d}}), where we write pos( ·) for the positive hull of the argument set. This is the internal cone at vertex y_{i}^{0} of the simplex Δ_{i}, which has a simple structure because its base is a (d − 1)-dimensional regular simplex and the opposite vertex y_{i}^{0} is at height r^{−1} over this base exactly above its centre. In particular, one can check easily that

C(y_{i} − y_{i}^{0}, arctan \frac{\sqrt{2} r}{d − 1}) ⊂ D_{i} ⊂ C(y_{i} − y_{i}^{0}, arctan \sqrt{2} r) .  (3)

Since each Δ_{i}^{j} is only a homothetic copy of Δ_{i} with a scaling factor not depending on n, the following holds by construction:

Lemma 7. For each i ∈ {1, …, m} and j ∈ {0, …, d} one has that V_{d}(Δ_{i}^{j}) ≈ (log n)^{− \frac{1}{2}} and γ_{d}(Δ_{i}^{j}) ≈ n^{−1}.

For each i ∈ {1, …, m} and j ∈ {0, …, d} let z_{i}^{j} be an arbitrary point in Δ_{i}^{j} and define the cone C_{i} := pos({z_{i}^{j} − z_{i}^{0} : j ∈ {1, …, d}}). We recall the following fact about these cones from [3, Lemma 5.4], which ensures a certain independence property used below:

Lemma 8. One can choose the constant c_{1} in the above construction sufficiently large and c_{2} sufficiently small such that for each i ∈ {1, …, m} the translated cone z_{i}^{0} + C_{i} contains all simplices Δ_{k} with k ∈ {1, …, m} \ {i}.

Observe further that the simplices [z_{i}^{0}, …, z_{i}^{d}] and Δ_{i} are very close to each other if the factor of homothety c_{2} is small enough. So relations (3) imply that

C_{i}^{1} := C(y_{i} − z_{i}^{0}, arctan \frac{r}{d − 1}) ⊂ C_{i} ⊂ C(y_{i} − z_{i}^{0}, arctan 2r) =: C_{i}^{2} . (4)

Δ_{i} Δ_{i}^{0} Δ_{i}^{1}  Δ_{i}^{2} z_{i}^{0} z_{i}^{1}  z_{i}^{2} H_{i}^{1} H_{i}^{2}  ^{z_{i}^{0} z_{i}^{1}  z_{i}^{2} Δ_{i} No points here  No points here}

Figure 2: The simplices Δ_{i}^{j}, the points z_{i}^{j} and the half-spaces H_{i}^{j} (left). Illustration of the events A_{i} (right).

Next, for i ∈ {1, …, m} and j ∈ {1, …, d} we denote by H_{i}^{j} the half-space containing Δ_{i}^{k} for all k ∈ {0, …, d} \ {0, j}, not containing Δ_{i}^{0} and Δ_{i}^{j}, and such that the hyperplane bounding H_{i}^{j} touches all the simplices Δ_{i}^{0}, …, Δ_{i}^{d} except for Δ_{i}^{j}, see Figure 2 (left). We are now in the position to define for each i ∈ {1, …, m} the event A_{i} ∈ A that precisely one point from the random sample X_{1}, …, X_{n} is contained in each simplex of the form Δ_{i}^{j} and no further point from X_{1}, …, X_{n} is contained in H_{i}^{+} ∪ H_{i}^{1} ∪ … ∪ H_{i}^{d}, see Figure 2 (right). Here, H_{i}^{+} is the half-space bounded by H_{i} not containing the origin. The following probability estimate is taken from [3, Lemma 6.2]:

Lemma 9. There exists a constant c_{3} ∈ (0, 1) such that P(A_{i}) ≥ c_{3} for all i ∈ {1, …, m}.

The facts summarized so far have been used in [3] to prove a lower variance bound for the volume V_{d}(K_{n}) of K_{n}. Since we are interested in all intrinsic volumes V_{1}(K_{n}), …, V_{d}(K_{n}), a refinement is necessary to obtain such bounds. In fact, we now follow and adapt the method already applied in [2, 5, 11] to handle the more general situation.

2.3 The effect of local perturbations

Let z ∈ 𝕊^{d−1} and G be a measurable subset of 𝔾(d, ℓ) for some ℓ ∈ {0, …, d}. The angle ∢(z, G) between z and G is defined as min{∢(z, x) : x ∈ L, L ∈ G}, where ∢(z, x) = arccos \frac{⟨x,z⟩}{∥x∥} is the ordinary angle between z and x. We observe the following geometric fact, see also [2, Lemma 1]:

Lemma 10. Let z ∈ 𝕊^{d−1} and ℓ ∈ {1, …, d}. One can find a constant c_{4} ∈ (0, ∞) only depending on d and on ℓ such that

ν_{ℓ}({L ∈ 𝔾(d, ℓ) : ∢(z, L) ≤ a}) ≫ a^{d−ℓ}

for all 0 < a < c_{4}.

Proof. For M ∈ 𝔾(d, ℓ − 1) we denote by 𝔾(M, ℓ) the relative Grassmannian of ℓ-dimensional linear subspaces of ℝ^{d} containing M. This space is supplied with a unique Haar probability measure ν_{ℓ}^{M}, see Chapter 7.1 in [13]. Similarly, we let 𝔾(z^{⊥}, ℓ − 1) be the relative Grassmannian of (ℓ − 1)-dimensional linear subspaces of ℝ^{d} that are contained in the hyperplane z^{⊥} orthogonal to 1-dimensional linear subspace spanned by z. The unique Haar probability measure on 𝔾(z^{⊥}, ℓ − 1) is denoted by ν_{ℓ−1}^{z^{⊥}}. For M ∈ 𝔾(z^{⊥}, ℓ − 1) let u ∈ 𝕊^{d−1} ∩ M^{⊥} be such that ∢(z, u) ≤ a. It is clear that the ℓ-dimensional linear subspace span(M, u) spanned by M and u is contained in the set {L ∈ 𝔾(d, ℓ) : ∢(z, L) ≤ a} we are interested in. Formally, using Fubini’s theorem for flag spaces (see [13, Theorem 7.1.1]) in the second step we write

ν_{ℓ}({L ∈ 𝔾(d, ℓ) : ∢(z, L) ≤ a})

= ∫_{𝔾(d,ℓ)} 1_{{∢(z,L)≤a}} ν_{ℓ}(dL)
= ∫_{𝔾(d,ℓ−1)} ∫_{𝔾(M,ℓ)} 1_{{∢(z,L)≤a}} ν_{ℓ}^{M}(dL)ν_{ℓ−1}(dM)
≥ ∫_{𝔾(z^{⊥},ℓ−1)} ∫_{𝔾(M,ℓ)} 1_{{∢(z,L)≤a}} ν_{ℓ}^{M}(dL)ν_{ℓ−1}^{z^{⊥}}(dM)
≥ ∫_{𝔾(z^{⊥},ℓ−1)} ∫_{𝕊^{d−1}∩M^{⊥}} 1_{{∢(z,u)≤a}} ν_{𝕊^{d−1}∩M^{⊥}}(du)ν_{ℓ−1}^{z^{⊥}}(dM)

= ∫_{𝔾(z^{⊥},ℓ−1)} ν_{𝕊^{d−1}∩M^{⊥}}({u ∈ 𝕊^{d−1} ∩ M^{⊥} : ∢(z, u) ≤ a}) ν_{ℓ−1}^{z^{⊥}}(dM) .

Since M^{⊥} has dimension d − ℓ + 1, the set of points u ∈ 𝕊^{d−1} ∩ M^{⊥} with ∢(z, u) ≤ a forms a spherical cap in the (d−ℓ)-dimensional subsphere 𝕊^{d−1}∩M^{⊥} of 𝕊^{d−1}. It has radius of order a and volume of order a^{d−ℓ}, where by volume we mean here the normalized (d − ℓ)-dimensional Hausdorff measure ν_{𝕊^{d−1}∩M^{⊥}} on 𝕊^{d−1} ∩ M^{⊥}. Hence, for sufficiently small a, we have

ν_{𝕊^{d−1}∩M^{⊥}}({u ∈ 𝕊^{d−1} ∩ M^{⊥} : ∢(z, u) ≤ a}) ≫ a^{d−ℓ}

and, since ν_{ℓ−1}^{z^{⊥}} is a probability measure, also

ν_{ℓ}({L ∈ 𝔾(d, ℓ) : ∢(z, L) ≤ a}) ≫ a^{d−ℓ} .

The proof is complete.

For i ∈ {1, …, m} put F_{i} := [z_{i}^{1}, …, z_{i}^{d}] and define

Ṽ_{ℓ}(z; F_{i}) := \binom{d}{ℓ}\frac{κ_{d}}{κ_{ℓ}κ_{d−ℓ}} ∫_{𝔾(d,ℓ)} 1_{\{L∩C_{i}^{2}≠∅\}} vol_{ℓ}([z, F_{i}]|L) ν_{ℓ}(dL) , z ∈ Δ_{i}^{0} .

The next lemma provides a lower bound for the variance of these local functionals.

Lemma 11. Fix ℓ ∈ {1, …, d}, let i ∈ {1, …, m} and let Z_{i} be a point chosen with respect to the normalized Gaussian measure restricted to Δ_{i}^{0}. Then

Var_{i}[Ṽ_{ℓ}(Z_{i}; F_{i})] ≫ (log n)^{−(d−ℓ+1)} ,

where the notation Var_{i}[ ·] refers to the variance that is taken with respect to Z_{i} ∈ Δ_{i}^{0}.

Proof. Denote by w_{i} the centre of the facet of Δ_{i}^{0} opposite to the vertex y_{i}^{0}, and define the points w_{i}^{1} := \frac{2}{3}y_{i}^{0} + \frac{1}{3}w_{i} and w_{i}^{2} := \frac{1}{3}y_{i}^{0} + \frac{2}{3}w_{i}. Furthermore, the regions R_{i}^{1}, R_{i}^{2} ⊂ Δ_{i}^{0} are given by R_{i}^{1} := (w_{i}^{1} − C_{i}^{2}) ∩ Δ_{i}^{0} and R_{i}^{2} := (w_{i}^{2} + C_{i}^{2}) ∩ Δ_{i}^{0}. It is crucial to observe that one can find a constant c_{7} only depending on d such that V_{d}(R_{i}^{k}) ≥ c_{7}V_{d}(Δ_{i}^{0}) for k = 1 and k = 2. This follows from (4). Together with the first part of Lemma 7 and the fact that the Gaussian density (1) satisfies

φ_{d}(x) ≈ \frac{\sqrt{log n}}{n} for all x ∈ ℝ^{d} with r ≤ ∥x∥ ≤ r + \frac{1}{r} ,

we see that the Gaussian measure of R_{i}^{k} is

γ_{d}(R_{i}^{k}) ≈ n^{−1} ,  k ∈ {1, 2} .  (5)

Next, fix some L ∈ 𝔾(d, ℓ) that intersects the interior of the polar of the cone C_{i}^{2}. This condition means that L has an orthonormal basis e_{1}, …, e_{ℓ} such that the hyperplane H_{i,0} := {x ∈ ℝ^{d} : ⟨x, e_{1}⟩ = ⟨w_{i}^{2}, e_{1}⟩} has only one point (namely the origin) in common with C_{i}^{2}. Let H_{i,0}^{+} be the half-space bounded by H_{i,0} not containing the origin. Finally, let us define the set G_{i} := H_{i,0}^{+} ∩(w_{i}^{1} +C_{i}^{2}) ⊂ Δ_{i}^{0}. We choose points Z_{i}^{1} ∈ R_{i}^{1} and Z_{i}^{2} ∈ R_{i}^{2}. The whole construction is illustrated in Figure 3 where L appears translated by w_{i}^{2} (not affecting the vol_{ℓ}(G_{i}|L)). Observe now that R_{i}^{1} and R_{i}^{2} are separated by the hyperplane H_{i,0}. Consequently, we have that Z_{i}^{2} ∈ [Z_{i}^{1}, F_{i}], which implies the inclusion [Z_{i}^{2}, F_{i}] ⊂ [Z_{i}^{1}, F_{i}]. In addition, G_{i} ⊂ H_{i,0}^{+} and R_{i}^{2} ∩ H_{i,0}^{+} = {w_{i}^{2}}, which yields G_{i} ∩ [Z_{i}^{2}, F_{i}] = {w_{i}^{2}}. Finally, we observe that the hyperplane parallel to H_{i,0} separates R_{i}^{1} and G_{i}, whence G_{i} ⊆ [Z_{i}^{1}, F_{i}]. The construction also shows V_{d}(G_{i}) ≈ r^{−1} = (log n)^{− \frac{1}{2}} and implies that

vol_{ℓ}(G_{i}|L) ≫ (log n)^{− \frac{1}{2}} .  (6)

As result, we arrive at the estimate

vol_{ℓ}([Z_{i}^{1}, F_{i}]|L) − vol_{ℓ}([Z_{i}^{2}, F_{i}]|L) ≥ vol_{ℓ}(G_{i}|L) .

z_{i}^{1}  z_{i}^{2} F_{i} = [z_{i}^{1}, z_{i}^{2}] L + w_{i}^{2} w_{i} w_{i}^{2} w_{i}^{1} y_{i}^{0} Z_{i}^{1}Z_{i}^{2} R_{i}^{2}R_{i}^{1} G_{i}  H_{i,0}  Δ_{i}^{0}

Figure 3: Construction in the proof of Lemma 11.

Hence,

Ṽ_{ℓ}(Z_{i}^{1}; F_{i}) − Ṽ_{ℓ}(Z_{i}^{2}; F_{i})

= \binom{d}{ℓ}\frac{κ_{d}}{κ_{ℓ}κ_{d−ℓ}} ∫_{𝔾(d,ℓ)} 1_{\{L∩C_{i}^{2}≠∅\}} (vol_{ℓ}([Z_{i}^{1}, F_{i}]|L) − vol_{ℓ}([Z_{i}^{2}, F_{i}]|L)) ν_{ℓ}(dL)

≥ \binom{d}{ℓ}\frac{κ_{d}}{κ_{ℓ}κ_{d−ℓ}} ∫_{𝔾(d,ℓ)} 1_{\{L∩C_{i}^{2}≠∅\}} vol_{ℓ}(G_{i}|L) ν_{ℓ}(dL)

≫ (log n)^{− \frac{1}{2}} ν_{ℓ}(\{L ∈ 𝔾(d, ℓ) : L ∩ C_{i}^{2} ≠ ∅\})

≫ (log n)^{− \frac{1}{2}} (log n)^{− \frac{d−ℓ}{2}}

= (log n)^{− \frac{d−ℓ+1}{2}} ,

where we used (6), the definition of C_{i}^{2}, and Lemma 10. Note that the latter can indeed be applied with a = 1/ log n, since 1/ log n < c_{4} for sufficiently large n. Selecting now Z_{i}^{k}, k ∈ {1, 2}, independently at random according to the normalized Gaussian measure restricted to Δ_{i}^{0} (i.e., Z_{i}^{1} and Z_{i}^{2} are independent copies of Z_{i}), we conclude that

Var[Ṽ_{ℓ}(Z_{i}; F_{i})] = \frac{1}{2}E[(Ṽ_{ℓ}(Z_{i}^{1}; F_{i}) − Ṽ_{ℓ}(Z_{i}^{2}; F_{i}))^{2}]

≥ \frac{1}{2}E[(Ṽ_{ℓ}(Z_{i}^{1}; F_{i}) − Ṽ_{ℓ}(Z_{i}^{2}; F_{i}))^{2} 1_{R_{i}^{1}}(Z_{i}^{1})1_{R_{i}^{2}}(Z_{i}^{2})]

≫ (log n)^{−(d−ℓ+1)} P(Z_{i}^{1} ∈ R_{i}^{1}, Z_{i}^{2} ∈ R_{i}^{2}) .

To obtain a lower bound for P(Z_{i}^{1} ∈ R_{i}^{1}, Z_{i}^{2} ∈ R_{i}^{2}) we recall (5) and combine this with the second assertion of Lemma 7 as well as with the independence of the random points Z_{i}^{1} and Z_{i}^{2}. This implies that

P(Z_{i}^{1} ∈ R_{i}^{1}, Z_{i}^{2} ∈ R_{i}^{2}) = ∏_{k=1}^{2} P(Z_{i}^{k} ∈ R_{i}^{1}) = ∏_{k=1}^{2} \frac{γ_{d}(R_{i}^{k})}{γ_{d}(Δ_{i}^{0})} ≥ c_{8}^{2}

with a constant c_{8} ∈ (0, ∞) only depending on d. Hence,

Var[Ṽ_{ℓ}(Z; F_{i})] ≫ (log n)^{−(d−ℓ+1)} ,

completing thereby the proof of the lemma.

3 Proof of Theorem 1

Recall the geometric construction and its properties from the previous section and denote by F ⊂ A the σ-field generated by the random points X_{1}, …, X_{n}, except those in the simplices Δ_{i}^{0} for which 1_{A_{i}} = 1, i ∈ {1, …, m}. The conditional variance formula implies that

Var[V_{ℓ}(K_{n})] = E[Var[V_{ℓ}(K_{n})|F]] + Var[E[V_{ℓ}(K_{n})|F]]
≥ E[Var[V_{ℓ}(K_{n})|F]] .

Now, conditioned on F, suppose that 1_{A_{i}} = 1, write Z_{i} for the (unique) random point in Δ_{i}^{0} and denote by F_{i} the convex hull of the random points in Δ_{i}^{j} with j ∈ {1, …, d}. We notice that if 1_{A_{i}} = 1 for each i ∈ I in a subset I ⊂ {1, …, m}, then (Ṽ_{ℓ}(Z_{i}; F_{i}) : i ∈ I) is a family of independent random variables as a consequence of the result of Lemma 8. This independence property implies that

Var[V_{ℓ}(K_{n})|F] = ∑_{{i=1 \atop 1_{A_{i}} =1}}^{m} Var_{i}[V_{ℓ}(K_{n})] = ∑_{{i=1 \atop 1_{A_{i}} =1}}^{m} Var_{i}[Ṽ_{ℓ}(Z_{i}; F_{i})] ,

where, as in the previous section, the notation Var_{i}[ ·] refers to the variance that is taken only with respect to the point Z_{i} ∈ Δ_{i}^{0} and we only sum over those i ∈ {1, …, m} with the property that 1_{A_{i}} = 1. These variances can be controlled by means of Lemma 11, which implies that

Var[V_{ℓ}(K_{n})|F] ≫ (log n)^{−(d−ℓ+1)} ∑_{i=1}^{m} 1_{A_{i}} .

Taking expectations and finally applying Lemma 9 as well as Lemma 5, we arrive at

Var[V_{ℓ}(K_{n})] ≫ (log n)^{−(d−ℓ+1)} ∑_{i=1}^{m} P(A_{i})
≫ (log n)^{−(d−ℓ+1)} × (log n)^{\frac{d−1}{2}}
= (log n)^{ℓ− \frac{d+3}{2}} .

This completes the argument and the proof of Theorem 1. □

Acknowledgement

Both authors were partially supported by ERC Advanced Grant 267165 (DIS-CONV), and the first author by the Hungarian NKFIH grants 111827 and 116769. We are grateful to Julian Grote (Bochum) for insights concerning the concentration inequality for V_{ℓ}(Π_{n}). We would also like to thank the referee for his/her stimulating comments and suggestions.

References

[1] F. Affentranger (1991). The convex hull of random points with spherically symmetric distributions. Rend. Sem. Mat. Univ. Politec. Torino 49, 459– 383.

[2] I. Bárány, F. Fodor and V. Vigh (2010). Intrinsic volumes of inscribed random polytopes in smooth convex bodies. Adv. in Appl. Probab. 42, 605–619.

[3] I. Bárány and V.H. Vu (2007). Central limit theorems for Gaussian polytopes. Ann. Probab. 35, 1593–1621.

[4] Y.M. Baryshnikov and R.A. Vitale (1994). Regular simplices and Gaussian samples. Discrete Comput. Geom. 11, 141–147.

[5] K.J. Böröczky, F. Fodor, M. Reitzner and V. Vigh (2009). Mean width of random polytopes in a reasonably smooth convex body. J. Multivariate Anal. 100, 2287–2295.

[6] P. Calka, T. Schreiber and J.E. Yukich (2015). Brownian limits, local limits and variance asymptotics for convex hulls in the unit ball. Ann. Probab. 41, 50–108.

[7] P. Calka and J.E. Yukich (2015). Variance asymptotics and scaling limits for Gaussian polytopes. Probab. Theory Related Fields 163, 259–301.

[8] E.D. Gluskin (1981): The diameter of the Minkowski compactum is roughly equal to n. Funct. Anal. Appl. 15, 57–58.

[9] J. Grote and C. Thäle (2016). Gaussian polytopes: a cumulant-based approach. arXiv: 1602.06148.

[10] D. Hug and M. Reitzner (2005). Gaussian polytopes: variances and limit theorems. Adv. in Appl. Probab. 37, 297–320.

[11] M. Reitzner (2005). Central limit theorems for random polytopes. Probab. Theory Related Fields 133, 483–507.

[12] M. Reitzner (2010). Random polytopes. In: W.S. Kendall and I. Molchanov (Eds.), New Perspectives in Stochastic Geometry, Oxford University Press.

[13] R. Schneider, W. Weil (2008). Stochastic and Integral Geometry. Probability and its Applications (New York). Springer-Verlag, Berlin.

[14] R. Schneider (2014). Convex Bodies – The Brunn-Minkowski Theory. 2nd expanded edition, Cambridge University Press.

Imre Bárány

Rényi Institute

of Mathematics

Hungarian Academy

of Sciences

H-1364 Budapest, Hungary barany@renyi.hu and University College London Department of Mathematics London WC1E 6BT England

Christoph Thäle

Ruhr University Bochum Faculty of Mathematics D-44780 Bochum, Germany christoph.thaele@rub.de 1336

Documenta Mathematica 22 (2017)