# On random sections of the cube

## 1 Introduction

The principal object in this paper is the expected number of $`j`$-dimensional faces (in short, $`j`$-faces) of a random $`k`$-dimensional central section (in short, $`k`$-section) of the $`n`$-cube $`B_{\mathrm{}}^n=[1,1]^n`$ in $`\mathrm{}^n`$. We denote this number by $`f(j,k,n)`$. The normalized rotation invariant measure on the set $`G_{n,k}`$ of all $`k`$-dimensional subspaces of $`\mathrm{}^n`$ provides the probabilistic framework.

Section $`2`$ contains a calculation of the expected number of vertices of a random $`k`$\- section of the $`n`$-cube. The result is:

$$f(0,k,n)=2^k\left(\genfrac{}{}{0pt}{}{n}{k}\right)\sqrt{\frac{2k}{\pi }}_0^{\mathrm{}}e^{kt^2/2}\gamma _{nk}(tB_{\mathrm{}}^{nk})𝑑t,$$
(1)   
where $`\gamma _{nk}`$ denotes the $`(nk)`$-dimensional Gaussian probability measure.

In $`\mathrm{\S }3`$ we derive a lower bound for $`f(j,k,n)`$ for every $`1j<k<n`$. The main result is:

$$\frac{f(0,kj,n)}{f(j,k,n)}<\sqrt{\frac{2}{\pi }}\left(\frac{j(kj)}{nk+j}\right)^{1/2}_0^{\mathrm{}}e^{\frac{j(kj)}{nk+j}t^2/2}\gamma _j(tB_{\mathrm{}}^j)𝑑t.$$

The lower bound for $`f(j,k,n)`$ derived from this inequality, combined with (1), leads in some cases to asymptotically best possible results. For example, in $`\mathrm{\S }3`$ we deduce from it the following asymptotic formula, for fixed integers $`1l<m`$:

$$f(nm,nl,n)\frac{(2n)^{ml}}{(ml)!},\text{as}n\mathrm{}.$$
(2)   
The notation $`a_nb_n`$ means: $`a_n/b_n1`$ as $`n\mathrm{}`$. (2) can be interpreted as follows: the probability that a random fixed-codimensional subspace of $`\mathrm{}^n`$ intersects a fixed-codimensional face of the $`n`$-cube, tends to $`1`$ as $`n\mathrm{}`$. The formula (2) itself follows also from the work of Affentranger and Schneider. (See remark 1 of section 3 below). In , they found a formula for the expected number $`\text{E}(f_j(\mathrm{\Pi }_kB_1^n))`$ of $`j`$-faces of an orthogonal projection of an $`n`$-polytope $`P`$ onto a $`k`$-dimensional random subspace. Formula (5) of  reads as follows:

$$\text{E}(f_j(\mathrm{\Pi }_kP))=f_j(P)2\underset{s0}{}\underset{F_j(P)}{}\underset{G_{k+1+2s}(P)}{}\beta (F,G)\gamma (G,P).$$
(3)   
Here $`_j(P)`$ denotes the set of $`k`$-faces of $`P`$, and $`f_j(P)=\text{card}_j(P)`$. $`\beta (F,G)`$ denotes the internal angle (, p. 297) of the face $`G`$ at its face $`F`$, and $`\gamma (G,P)`$ — the external angle (, p. 308) of $`P`$ at its face $`G`$. It is shown in  that (3) implies that if $`0j<k`$ are fixed integers, then as $`n\mathrm{}`$,

$$\text{E}(f_j(\mathrm{\Pi }_kT^n))\frac{2^k}{\sqrt{k}}\left(\genfrac{}{}{0pt}{}{k}{j+1}\right)\beta (T^j,T^{k1})(\pi \mathrm{log}n)^{(k1)/2}.$$
(4)   
Here $`T^n`$ stands for the regular $`n`$-simplex.

In a very recent work, , Böröczky, Jr. and Henk showed that (3) implies the same asymptotic formula (4) also for $`\text{E}(f_j(\mathrm{\Pi }_kB_1^n))`$, where $`B_1^n`$ is the regular cross-polytope. In addition, they found an asymptotic formula for the internal angles $`\beta (T^j,T^{k1})`$, when $`k/j^2\mathrm{}`$. Therefore if $`j`$ is fixed, $`k`$ is much larger than $`j^2`$ and $`n`$ much larger than $`k`$, then explicit estimates for $`\text{E}(f_j(\mathrm{\Pi }_kB_1^n))`$ are available. See  for more details. Explicit asymptotic formulas for $`\text{E}(f_j(\mathrm{\Pi }_kT^n))`$, were established independently by Vershik and Sporyshev (), when $`j,k`$ are both proportional to $`n`$ and $`n\mathrm{}`$.

A simple duality argument shows that

$$\text{E}(f_j(\mathrm{\Pi }_kB_1^n))=f(kj1,k,n).$$

Choose $`j=k1`$ in (4). Applying the result for $`B_1^n`$, one has

$$f(0,k,n)=\text{E}(f_{k1}(\mathrm{\Pi }_kB_1^n))\frac{2^k}{\sqrt{k}}(\pi \mathrm{log}n)^{(k1)/2},\text{as }n\mathrm{}.$$
(5)   
The last asymptotic formula follows also from (1). In fact, if $`\{g_i\}_{i=1}^m`$ are independent $`N(0,1)`$ (that is, with mean $`0`$ and variance $`1`$) Gaussian variables then $`\gamma _m(tB_{\mathrm{}}^m)`$ coincides with the probability of the event $`\{\mathrm{max}_{1im}|g_i|t\}`$. This probabilistic interpretation allows a straightforward evaluation of the asymptotic behavior of the integral in (1), when $`k`$ is fixed and $`n\mathrm{}`$.

Formula (1) also yields information about $`f(0,k,n)`$ for $`k`$ not necessarily fixed. For example, if $`k=n1`$, then the integral in (1) can be computed and the result is:

$$f(0,n1,n)=\frac{2^nn}{\pi }\mathrm{arctan}\frac{1}{\sqrt{n1}}\frac{2^n\sqrt{n}}{\pi }.$$
(6)   
Particular values of the last formula were computed numerically in . (Table $`2`$). For the expected number of vertices of random sections of fixed co-dimension, we have the following inequality, which is a consequence of (1).

$$f(0,nd,n)\left(\genfrac{}{}{0pt}{}{n}{d}\right)2^n\left(\frac{1}{\pi }\mathrm{arctan}\frac{1}{\sqrt{nd}}\right)^d,(d1).$$

Equality holds for $`d=1`$.

To obtain a lower bound for $`f(j,k,n)`$, it turns out that it is useful to know an estimate for the Gaussian measure of a cone generated by a section of a face of a cube. In $`\mathrm{\S }3`$ we find such an estimate, by modifying K. Ball’s calculation of the maximal volume of a cube–section, based on Brascamp-Lieb’s inequality. ().

Dvoretzky’s theorem on almost Euclidean sections asserts that there exists a function $`k(\epsilon ,n)1`$, tending to infinity as $`n\mathrm{}`$ for each fixed $`\epsilon >0`$, such that if $`K`$ is an $`n`$-dimensional centrally symmetric convex body (that is, a convex compact set in $`\mathrm{}^n`$ with non-empty interior, satisfying $`K=K`$), and $`\epsilon >0`$, then for each $`1kk(\epsilon ,n)`$ there exists a $`k`$-dimensional subspace $`X`$, and a linear automorphism $`T`$ of $`X`$ for which

$$XB_2^nT(XK)(1+\epsilon )(XB_2^n),$$
(7)   
where $`B_2^n`$ denotes the Euclidean unit ball. The proof of Dvoretzky’s theorem in  shows that $`k(\epsilon ,n)c\epsilon ^2|\mathrm{log}\epsilon |^1\mathrm{log}n`$, for some absolute constant $`c>0`$. That proof determined the best possible dependence of $`k`$ on $`n`$. The dependence of $`k`$ on $`\epsilon `$ was improved by Gordon , who discovered another proof of Dvoretzky’s theorem with $`k(\epsilon ,n)c\epsilon ^2\mathrm{log}n`$. Both proofs are probabilistic; they show that not only there exist almost Euclidean sections, but actually most sections are such. More precisely, if $`X`$ is a random subspace whose dimension does not exceed $`k(\epsilon ,n)`$, then the probability that the section $`XK`$ is $`(1+\epsilon )`$-Euclidean (common terminology for expressing that (7) holds), tends to $`1`$ as $`n\mathrm{}`$. These facts motivate an investigation of the random $`f`$-vector $`\{f(j,k,n)\}_{j=0}^{k1}`$, especially since it is well known that every $`k`$-dimensional symmetric polytope that has $`2n`$ facets is affinely equivalent to a $`k`$-section of an $`n`$-cube.

## 2 Vertices

Let $`G_{n,k}`$ denote the set of $`k`$-dimensional subspaces of $`\mathrm{}^n`$. We will denote its normalized rotation invariant measure by “Prob”. Recall that this measure is related to the normalized Haar measure $`H`$ of the orthogonal group $`\mathrm{O}(n)`$ by the equality

$$\text{Prob }\{XB\}=H\{g\text{O}(n):g[e_i]_{i=1}^kB\},$$

where $`B`$ is a Borel subset of $`G_{n,k}`$ and $`[e_i]_{i=1}^k`$ is the $`k`$-dimensional subspace spanned by the first $`k`$ unit vectors in $`\mathrm{}^n`$. Fix $`XG_{n,k}`$. For each $`0jk1`$, the set of $`j`$-faces of the polytope $`XB_{\mathrm{}}^n`$ coincides with the set of intersections of $`(nk+j)`$-faces of $`B_{\mathrm{}}^n`$ with $`X`$. Every $`(nk+j)`$-face of $`B_{\mathrm{}}^n`$ has the same probability to be intersected. Therefore if one particular $`(nk+j)`$-face $`F_{nk+j}`$ is fixed, then the expected number of $`j`$-faces of the section $`XB_{\mathrm{}}^n`$ is equal to:

$$2^{kj}\left(\genfrac{}{}{0pt}{}{n}{kj}\right)\text{Prob }\{XF_{nk+j}\mathrm{}\}.$$

Let $`C(F_{nk+j})`$ denote the cone generated by $`F_{nk+j}`$:

$$C(F_{nk+j})=\underset{xF_{nk+j}}{}\{tx:t0\}.$$

Put $`C_1(F_{nk+j})=C(F_{nk+j})\mathrm{𝕊}^{n1}`$. For every subspace $`X`$,

$$XF_{nk+j}\mathrm{}(X\mathrm{𝕊}^{n1})C_1(F_{nk+j})\mathrm{}.$$

For $`n=0,1,\mathrm{}`$ we denote by $`\sigma _n`$ the normalized rotation-invariant measure on the unit-sphere $`\mathrm{𝕊}^n`$ in $`\mathrm{}^{n+1}`$. The next lemma will prove useful for dealing with intersections of subsets of the sphere with random subspaces.

###### Lemma 2.1

Let $`l,m,n`$ be positive integers satisfying $`l+mn1`$. Suppose that $`A\mathrm{𝕊}^m`$ and $`B\mathrm{𝕊}^l`$ are Borel subsets. Then for $`p=l+mn+1`$,

$$_{\mathrm{O}(n)}\sigma _p(gBA)𝑑H(g)=\sigma _l(B)\sigma _m(A).$$
(8)   
To prove the lemma one observes that for fixed $`A`$ (resp. $`B`$) the integral defines an invariant measure on $`\mathrm{𝕊}^l`$ (resp. $`\mathrm{𝕊}^m`$); the conclusion follows from that.

Lemma $`2.1`$ is now applied to $`B=X\mathrm{𝕊}^{n1}`$, which we denote by $`\mathrm{𝕊}^{k1}`$, and to $`A=C_1(F_{nk+j})`$. For $`l=k1`$ and $`m=nk+j`$ equality (8) becomes:

$$_{\mathrm{O}(n)}\sigma _j(g\mathrm{𝕊}^{k1}A)𝑑H(g)=\sigma _{nk+j}(A).$$
(9)   
We are ready to compute the expected number of vertices. The Gaussian measure in $`\mathrm{}^m`$ whose density is $`(2\pi )^{m/2}\mathrm{exp}(_1^mx_i^2/2)`$ is denoted by $`\gamma _m`$.

###### Proposition 2.2

The expected number of vertices of a random $`k`$-dimensional central section of the $`n`$-cube is given by the formula

$$f(0,k,n)=2^k\left(\genfrac{}{}{0pt}{}{n}{k}\right)\sqrt{\frac{2k}{\pi }}_0^{\mathrm{}}e^{kt^2/2}\gamma _{nk}(tB_{\mathrm{}}^{nk})𝑑t.$$

*Proof*. For each $`g\text{O}(n)`$ we have

$$g\mathrm{𝕊}^{k1}C_1(F_{nk})=(\text{span}(g\mathrm{𝕊}^{k1})C(F_{nk}))\mathrm{𝕊}^{n1}.$$

For almost every $`g`$ the intersection $`\text{span}(g\mathrm{𝕊}^{k1})C(F_{nk})`$ is either the origin itself, or else a ray emanating from the origin. Therefore the intersection $`g\mathrm{𝕊}^{k1}C_1(F_{nk})`$ is either empty or a singleton, for almost every $`g`$. Choose $`j=0`$ in (9), with $`A=C_1(F_{nk})`$. Since the measure $`\sigma _0`$ is concentrated on two points giving mass $`1/2`$ to each, we deduce from $`(9)`$ that

$$\text{Prob }\{XF_{nk}\mathrm{}\}=2\sigma _{nk}(C_1(F_{nk})).$$
(10)   
To compute the r.h.s of $`(10)`$, consider an $`(nk)`$-dimensional cube of edge-length $`1`$ inside $`\mathrm{}^{nk+1}`$, at a distance $`\sqrt{k}`$ from the origin, form the cone it generates, and compute the measure of its intersection with the sphere $`\mathrm{𝕊}^{nk}`$. Invoking polar coordinates we see that

$$\sigma _{nk}(C_1(F_{nk}))=\gamma _{nk+1}(C(F_{nk})).$$

By rotational symmetry of the Gaussian measure we may assume that $`F_{nk}`$ is specifically the set $`\{x:|x_i|1,\mathrm{\hspace{0.17em}1}ink,x_{nk+1}=\sqrt{k}\}`$. The intersection of the hyper-plane $`\{x_{nk+1}=t\}`$ with $`C(F_{nk})`$ is an $`(nk)`$-dimensional cube of edge-length $`\frac{t}{\sqrt{k}}`$. Therefore by Fubini’s theorem

$`\gamma _{nk+1}(C(F_{nk}))`$ $`={\displaystyle \frac{1}{\sqrt{2\pi }}}{\displaystyle _0^{\mathrm{}}}e^{t^2/2}\gamma _{nk}({\displaystyle \frac{t}{\sqrt{k}}}B_{\mathrm{}}^{nk})𝑑t`$   
$`=\sqrt{{\displaystyle \frac{k}{2\pi }}}{\displaystyle _0^{\mathrm{}}}e^{kt^2/2}\gamma _{nk}(tB_{\mathrm{}}^{nk})𝑑t.`$   
The last equality, together with $`(10)`$, implies the desired formula.        

The next lemma points out the precise asymptotic behavior of $`f(0,k,n)`$ when $`k`$ is fixed and $`n\mathrm{}`$, and also that of $`f(nm,nl,n)`$, when $`l,m`$ are fixed and $`n\mathrm{}`$. (To be used in $`\mathrm{\S }3`$.)

###### Lemma 2.3

Suppose that $`\{\alpha _n\}_{n=1}^{\mathrm{}}`$ is a sequence of real numbers that has a positive limit $`\alpha `$. Then as $`n\mathrm{}`$,

$$_0^{\mathrm{}}e^{\alpha _nt^2/2}\gamma _n(tB_{\mathrm{}}^n)𝑑t\mathrm{\Gamma }(\alpha )\frac{\pi ^{\alpha /2}}{\sqrt{2}}\frac{(\mathrm{log}n)^{(\alpha _n1)/2}}{n^{\alpha _n}}$$
(11)   
where $`\mathrm{\Gamma }`$ is the Gamma function.

*Proof*. Let $`F_n(t)=\text{Prob}\{\mathrm{max}_i|g_i|t\}`$, where $`g_1,\mathrm{},g_n`$ are independent $`N(0,1)`$-Gaussian variables. We have

$$\gamma _n(tB_{\mathrm{}}^n)=\left(\sqrt{\frac{2}{\pi }}_0^te^{x^2/2}𝑑x\right)^n=F_n(t).$$

For $`n>1`$, put

$$a_n=\frac{1}{\sqrt{2\mathrm{log}n}},\text{and}b_n=\sqrt{2\mathrm{log}n}\frac{\mathrm{log}(\pi \mathrm{log}n)}{2\sqrt{2\mathrm{log}n}}.$$

The well known tail approximation

$$\sqrt{\frac{2}{\pi }}_t^{\mathrm{}}e^{x^2/2}𝑑x=\sqrt{\frac{2}{\pi }}\frac{1+o(1)}{t}e^{t^2/2}\text{as}t\mathrm{},$$
(12)   
combined with a simple calculation, implies that

$$\underset{n\mathrm{}}{lim}F_n(a_nx+b_n)=\mathrm{exp}(e^x),x\mathrm{}.$$
(13)   
A change of variables gives:

$`{\displaystyle \underset{0}{\overset{\mathrm{}}{}}}e^{\alpha _nt^2/2}\gamma _n(tB_{\mathrm{}}^n)𝑑t=a_n{\displaystyle \underset{b_n/a_n}{\overset{\mathrm{}}{}}}e^{\alpha _n(a_nx+b_n)^2/2}F_n(a_nx+b_n)𝑑x`$   
$`={\displaystyle \frac{\pi ^{\alpha _n/2}}{\sqrt{2}}}{\displaystyle \frac{(\mathrm{log}n)^{(\alpha _n1)/2}}{n^{\alpha _n}}}e^{o(1)}{\displaystyle \underset{\mathrm{}}{\overset{\mathrm{}}{}}}e^{x^2o(1)}e^{\alpha _nx(1o(1))}F_n(a_nx+b_n)\chi _n(x)𝑑x.`$   
Here $`\chi _n`$ stands for the characteristic function of the interval $`[b_n/a_n,\mathrm{})`$. All four terms of the integrand in the last integral are non-negative for each $`x`$. For $`x0`$ and sufficiently large $`n`$ we have $`e^{\alpha _nx(1o(1))}<e^{\alpha x/2}`$, while the rest of the terms are majorized by $`1`$. For $`x<0`$ and sufficiently large $`n`$, we have $`F_n(a_nx+b_n)<2\mathrm{exp}(e^{|x|})`$ and $`e^{\alpha _nx(1o(1))}<e^{2\alpha |x|}`$. Thus in both cases if $`n`$ is sufficiently large, the integrand is dominated by an integrable function. By (13), the integrand converges pointwise to the function $`e^{\alpha x}\mathrm{exp}(e^x)`$; Lebesgue’s bounded convergence theorem can be applied:

$`\underset{n\mathrm{}}{lim}{\displaystyle _{b_n/a_n}}e^{x^2o(1)}e^{\alpha _nx(1o(1))}F_n(a_nx+b_n)𝑑x`$ $`={\displaystyle _{\mathrm{}}^{\mathrm{}}}e^{\alpha x}\mathrm{exp}(e^x)𝑑x`$   
$`=\mathrm{\Gamma }(\alpha ).`$   
The proof of Lemma $`2.3`$ is complete.        

Taking $`\alpha _nk`$ in Lemma 2.3 and bearing in mind Proposition $`2.2`$ re-proves the following result, which was mentioned in the introduction.

###### Corollary 2.4

For fixed $`k`$,

$$f(0,k,n)\frac{2^k}{\sqrt{k}}(\pi \mathrm{log}n)^{(k1)/2},\mathrm{as}n\mathrm{}.$$

We turn now to the case of fixed co-dimension. The next result is deduced from proposition $`2.2`$.

###### Proposition 2.5

For $`d1`$,

$$f(0,nd,n)\left(\genfrac{}{}{0pt}{}{n}{d}\right)2^n\left(\frac{1}{\pi }\mathrm{arctan}\frac{1}{\sqrt{nd}}\right)^d,(d1).$$

Equality holds for $`d=1:`$

$$f(0,n1,n)=\frac{2^nn}{\pi }\mathrm{arctan}\frac{1}{\sqrt{n1}}.$$
(14)   
*Proof*. Consider the probability measure $`d\mu (t)=2\sqrt{\frac{k}{\pi }}e^{kt^2}dt`$ on the half-line $`[0,\mathrm{})`$. Put

$$\mathrm{\Phi }(t)=\frac{2}{\sqrt{\pi }}_0^te^{x^2}𝑑x.$$

Then

$$\gamma _{nk}(tB_{\mathrm{}}^{nk})=\left(\sqrt{\frac{2}{\pi }}_0^te^{x^2/2}𝑑x\right)^{nk}=\mathrm{\Phi }^{nk}(t/\sqrt{2}).$$

Therefore

$`\sqrt{{\displaystyle \frac{2k}{\pi }}}{\displaystyle _0^{\mathrm{}}}e^{kt^2/2}\gamma _{nk}(tB_{\mathrm{}}^{nk})𝑑t`$ $`=\sqrt{{\displaystyle \frac{2k}{\pi }}}{\displaystyle _0^{\mathrm{}}}e^{kt^2/2}\mathrm{\Phi }^{nk}(t/\sqrt{2})𝑑t`$ (15)   
$`={\displaystyle _0^{\mathrm{}}}\mathrm{\Phi }^{nk}(t)𝑑\mu (t)`$   
$`\left({\displaystyle _0^{\mathrm{}}}\mathrm{\Phi }(t)𝑑\mu (t)\right)^{nk}.`$   
Elementary calculation shows that

$$_0^{\mathrm{}}e^{kt^2}\mathrm{\Phi }(t)𝑑t=\frac{1}{\sqrt{\pi k}}\mathrm{arctan}\frac{1}{\sqrt{k}}.$$

A combination of (15) with proposition $`2.2`$ gives the desired inequality, after a replacement of $`k`$ by $`nd`$. Observe that for $`k=n1`$ (that is, $`d=1`$), there is equality in the inequality of (15).        

Remarks

1. For $`n=3`$ we get from (14): $`f(0,2,3)=(24/\pi )\mathrm{arctan}\frac{1}{\sqrt{2}}4.7`$. Therefore a random $`2`$-section of the $`3`$-cube is more likely to be a parallelogram than a hexagon.

2. Bárány and Lovász proved in  that (in particular) almost every $`k`$-section of the $`n`$-cube has at least $`2^k`$ vertices. Clearly this is a precise lower bound. For $`k=n1`$, our result shows that the expected value is asymptotically $`\sqrt{n}/\pi `$ times the minimal value.

3. The asymptotic behavior of the integral

$$_0^{\mathrm{}}e^{kt^2/2}\gamma _{nk}(tB_{\mathrm{}}^{nk})𝑑t$$

for fixed $`k`$ and $`n\mathrm{}`$ was determined in  (following ), and was used to prove formula (4) of the introduction. See also . The asymptotic result is basically a corollary of the classical tail approximation of a single $`N(0,1)`$-Gaussian variable. Our approach to the proof of Lemma $`2.3`$ seems to simplify the analysis.

4. As was indicated in the introduction, we can choose $`\epsilon =\frac{c}{\sqrt{\mathrm{log}n}}`$ for some constant $`c>0`$, and then with high probability a random $`2`$-section of the cube is $`(1+\frac{c}{\sqrt{\mathrm{log}n}})`$-Euclidean. It is well known that among all centrally symmetric polygons having $`2m`$ vertices, the regular $`2m`$-gon minimizes the Banach-Mazur distance to the Euclidean disc; the minimal distance is $`(\mathrm{cos}(\pi /2m))^1`$. Consequently with high probability we have

$$(\mathrm{cos}(\pi /2m))^1<1+\frac{c}{\sqrt{\mathrm{log}n}}.$$

Hence most $`2`$-sections of the $`n`$-cube have at least $`C(\mathrm{log}n)^{1/4}`$ vertices, for some positive constant $`C`$. By Corollary $`2.2`$ (after a suitable rearrangement)

$$f(0,2,n)=2\sqrt{\pi }\text{E}(\underset{1in}{\mathrm{max}}|g_i|),$$

which is of the order of magnitude of $`\sqrt{\mathrm{log}n}`$. Summarizing these observations, we conclude: a typical $`2`$-section of the $`n`$-cube is $`(1+\frac{c}{\sqrt{\mathrm{log}n}})`$\- Euclidean, hence it cannot have too few vertices — it has at least $`C(\mathrm{log}n)^{1/4}`$ vertices with probability that tends to $`1`$ as $`n\mathrm{}`$. It does not however tend to be a regular polygon, because the expected number of its vertices is too high for that.

## 3 Other faces

We now turn to the case $`j1`$, and prove the following result.

###### Proposition 3.1

For $`j1`$, the following inequality holds.

$$\frac{f(0,kj,n)}{f(j,k,n)}<\sqrt{\frac{2}{\pi }}\left(\frac{j(kj)}{nk+j}\right)^{1/2}_0^{\mathrm{}}e^{\frac{j(kj)}{nk+j}t^2/2}\gamma _j(tB_{\mathrm{}}^j)𝑑t.$$

The starting point in the proof of Proposition $`3.1`$ is (9) of Lemma $`2.1`$. Again, we choose $`A=C_1(F_{nk+j})`$. The random variable $`g\sigma _j(g\mathrm{𝕊}^{k1}A)`$, which is defined on $`\mathrm{O}(n)`$, has values in $`[0,1]`$. Hence

$$_{\mathrm{O}(n)}\sigma _j(g\mathrm{𝕊}^{k1}A)𝑑H(g)=_0^1H\{g:\sigma _j(g\mathrm{𝕊}^{k1}A)t\}𝑑t.$$
(16)   
The integrand is non-increasing, and

$$H\{g:\sigma _j(g\mathrm{𝕊}^{k1}A)0\}=\text{Prob }\{XF_{nk+j}\mathrm{}\},$$
(17)   
because the event $`\{g\mathrm{𝕊}^{k1}A\mathrm{}\text{and}\sigma _j(g\mathrm{𝕊}^{k1}A)=0\}`$ has Haar measure zero. Therefore by (9):

$`\sigma _{nk+j}(A)`$ $`\text{Prob }\{XF_{nk+j}\mathrm{}\}sup\{t:H\{g:\sigma _j(g\mathrm{𝕊}^{k1}A)t\}>0\}`$   
$`\text{Prob }\{XF_{nk+j}\mathrm{}\}sup\{\sigma _j(g\mathrm{𝕊}^{k1}A):g\mathrm{O}(n)\}.`$   
Let

$$t_{j,k,n}=sup\{\sigma _j(g\mathrm{𝕊}^{k1}A):g\mathrm{O}(n)\}.$$

By (9), $`(15)`$ and $`(16)`$ we get

$$\text{Prob}\{XF_{nk+j}\mathrm{}\}\frac{\sigma _{nk+j}(A)}{t_{j,k,n}}.$$

Hence by (10)

$$f(j,k,n)2^{kj}\left(\genfrac{}{}{0pt}{}{n}{kj}\right)\frac{\sigma _{nk+j}(A)}{t_{j,k,n}}=\frac{\frac{1}{2}f(0,kj,n)}{t_{j,k,n}}.$$

We must bound $`t_{j,k,n}`$ from above. Since $`A`$ is contained in a half-space, a trivial bound is $`t_{j,k,n}\frac{1}{2}`$. In some cases this bound can be significantly improved. The main lemma in this section is the following.

###### Lemma 3.2

If $`1j<k<n`$, then

$$t_{j,k,n}\frac{1}{\sqrt{2\pi }}\left(\frac{j(kj)}{nk+j}\right)^{1/2}_0^{\mathrm{}}e^{\frac{j(kj)}{nk+j}t^2/2}\gamma _j(tB_{\mathrm{}}^j)𝑑t.$$

The next lemma will be used in the proof of Lemma 3.2.

###### Lemma 3.3

Given a positive number $`\tau >0`$, a $`j`$-dimensional subspace $`Y`$ of $`\mathrm{}^m`$ and a point $`y_0Y`$, the following inequality holds.

$$\gamma _j((Y\tau B_{\mathrm{}}^m)y_0)\gamma _j(\tau \sqrt{m/j}B_{\mathrm{}}^j).$$
(18)   
*Proof*. Let $`Q`$ denote the orthogonal projection onto $`Yy_0`$. As usual, $`\{e_i\}_{i=1}^m`$ are the standard unit vectors in $`\mathrm{}^m`$. Put $`u_i=Qe_i/Qe_i`$ if $`Qe_i0`$, and $`u_i=0`$ otherwise; put $`c_i=Qe_i^2`$ and $`\alpha _i=y_0,e_i`$ for $`1im`$. ($`,`$ is the standard scalar product.) Then

$`Y\tau B_{\mathrm{}}^m`$ $`=\{yY:|y,e_i|\tau i\}`$   
$`=\{yY:|yy_0,e_i+y_0,e_i|\tau i\}`$   
$`=\{yY:{\displaystyle \frac{\alpha _i\tau }{\sqrt{c_i}}}yy_0,u_i{\displaystyle \frac{\alpha _i+\tau }{\sqrt{c_i}}}\}.`$   
Therefore

$$(Y\tau B_{\mathrm{}}^m)y_0=\{xYy_0:\frac{\alpha _i\tau }{\sqrt{c_i}}x,u_i\frac{\alpha _i+\tau }{\sqrt{c_i}}\}$$

Now we can imitate K. Ball’s argument from  concerning sections of maximal volume. Instead of the Lebesgue measure, we have to consider the Gaussian measure.

In $`Yy_0`$, the identity operator can be written as $`_1^mc_iu_iu_i`$. In particular,

$$\underset{i=1}{\overset{m}{}}c_i=j,\text{and}x^2=\underset{i=1}{\overset{m}{}}c_ix,u_i^2,xYy_0.$$

Therefore the Gaussian measure in $`Yy_0`$ is equal to

$$(2\pi )^{j/2}\mathrm{exp}(\underset{i=1}{\overset{m}{}}c_ix,u_i^2/2)dx.$$

Let $`\chi _i`$ denote the characteristic function of the interval $`[\frac{\alpha _i\tau }{\sqrt{c_i}},\frac{\alpha _i+\tau }{\sqrt{c_i}}]`$. Then, by the above,

$`\gamma _j((Y\tau B_{\mathrm{}}^m)y_0)`$ $`=(2\pi )^{j/2}{\displaystyle _{Yy_0}}\left({\displaystyle \underset{i=1}{\overset{m}{}}}\chi _i(x,u_i)e^{c_ix,u_i^2/2}\right)𝑑x`$ (19)   
$`=(2\pi )^{j/2}{\displaystyle _{Yy_0}}{\displaystyle \underset{i=1}{\overset{m}{}}}(\chi _i(x,u_i)e^{x,u_i^2/2})^{c_i}dx`$   
$`(2\pi )^{j/2}{\displaystyle \underset{i=1}{\overset{m}{}}}\left({\displaystyle _{(\alpha _i\tau )/\sqrt{c_i}}^{(\alpha _i+\tau )/\sqrt{c_i}}}e^{s^2/2}𝑑s\right)^{c_i}.`$   
The last inequality is a consequence of Brascamp-Lieb’s inequality, which is stated in  as follows:

LemmaLet $`(u_i)_1^m`$ be a sequence of unit vectors in $`\mathrm{}^n`$ and $`(c_i)_1^m`$ a sequence of positive numbers so that

$$\underset{1}{\overset{m}{}}c_iu_iu_i=I_n.$$

For each $`i`$, let $`f_i:\mathrm{}[0,\mathrm{})`$ be integrable. Then

$$_\mathrm{}^n\underset{i=1}{\overset{m}{}}f_i(u_i,x)^{c_i}dx\underset{i=1}{\overset{m}{}}\left(_{\mathrm{}}f_i\right)^{c_i}.$$

The $`i`$’th integral in the product of $`(19)`$ is not larger than $`_{\tau /\sqrt{c_i}}^{\tau /\sqrt{c_i}}e^{s^2/2}𝑑s`$. Hence the last expression in $`(19)`$ is bounded above by

$$(2\pi )^{j/2}\underset{i=1}{\overset{m}{}}\left(2_0^{\tau /\sqrt{c_i}}e^{s^2/2}𝑑s\right)^{c_i},$$

which is maximized when all the $`c_i`$’s are equal. Hence

$`\gamma _j((Y\tau B_{\mathrm{}}^m)y_0)`$ $`\left(\sqrt{{\displaystyle \frac{2}{\pi }}}{\displaystyle _0^{\tau \sqrt{m/j}}}e^{s^2/2}𝑑s\right)^j`$ (20)   
$`=\gamma _j(\tau \sqrt{m/j}B_{\mathrm{}}^j).`$   
The proof of Lemma $`3.3`$ is complete.        

Proof of Lemma 3.2 For $`g\mathrm{O}(n)`$

$`\sigma _j(g\mathrm{𝕊}^{k1}A)`$ $`=\gamma _{j+1}\left(C(F_{nk+j})\text{span}(g\mathrm{𝕊}^{k1})\right)`$   
$`=\gamma _{j+1}\left(C[F_{nk+j}\text{span}(g\mathrm{𝕊}^{k1})]\right).`$   
The second equality is a consequence of the identity $`C(F_{nk+j})X=C(F_{nk+j}X)`$, which trivially holds for every subspace $`X\mathrm{}^n`$. Fix a subspace $`XG_{n,k}`$ for which the section $`XF_{nk+j}`$ is $`j`$-dimensional; almost every $`XG_{n,k}`$ has this property. Let $`C`$ denote the $`(j+1)`$-dimensional cone generated by $`XF_{nk+j}`$; put $`X_0=\text{span}C`$. By $`M`$ we denote the affine subspace spanned by $`XF_{nk+j}`$, and by $`d`$, its distance from the origin of $`X`$. The Gaussian measure of the cone $`C`$ is computed as follows. Take the unit vector $`\xi X_0`$ which is orthogonal to $`M`$, and for which $`d\xi M`$. For $`t>0`$, put $`W_t=\{xX_0:x,\xi =t\}`$. Observe that $`CW_t=(t/d)(XF_{nk+j})`$. Let $`P`$ denote the orthogonal projection from $`X_0`$ onto $`W_0`$. By Fubini’s theorem:

$`\gamma _{j+1}(C)`$ $`={\displaystyle \frac{1}{\sqrt{2\pi }}}{\displaystyle _0^{\mathrm{}}}e^{t^2/2}\gamma _j(P(CW_t))𝑑t`$ (21)   
$`={\displaystyle \frac{1}{\sqrt{2\pi }}}{\displaystyle _0^{\mathrm{}}}e^{t^2/2}\gamma _j(P(t/d)(XF_{nk+j}))𝑑t.`$   
Our task is to estimate the expression $`\gamma _j(P\tau (XF_{nk+j}))`$ for every $`\tau >0`$. We will need to discuss Gaussian measures in different subspaces. Whenever $`M`$ is an $`m`$-dimensional subspace of $`\mathrm{}^n`$ and $`qM`$, let $`\mathrm{𝔾}_{M,q}`$ denote the measure $`(2\pi )^{m/2}\mathrm{exp}(xq^2/2)dx`$. In case $`M`$ is an $`m`$-dimensional linear subspace of $`\mathrm{}^n`$ and $`q=0`$ we shall simply write $`\mathrm{𝔾}_{M,0}=\gamma _m`$. If $`T`$ is an isometry of $`\mathrm{}^n`$, then for every Borel subset $`SM`$ we have

$$\mathrm{𝔾}_{M,q}(S)=\mathrm{𝔾}_{TM,Tq}(TS).$$
(22)   
Let us momentarily assume that $`\tau =1`$. Let $`q`$ denote the nearest point of $`M`$ to the origin of $`X`$. Both $`M`$ and the range of the projection $`P`$ are $`j`$-dimensional affine subspaces of $`X_0`$. We have

$$P(XF_{nk+j})=(XF_{nk+j})q,$$

hence by (22)

$$\mathrm{𝔾}_{M,q}(XF_{nk+j})=\gamma _j(P(XF_{nk+j})).$$
(23)   
Now let $`L`$ denote the affine subspace spanned by $`F_{nk+j}`$, whose origin $`O_L`$ is taken as the center of the face $`F_{nk+j}`$. (So if $`X`$ passes through the center of $`F_{nk+j}`$, then $`q=O_L`$.) $`M`$ is also a $`j`$-dimensional affine subspace of $`L`$. By (22),

$$\mathrm{𝔾}_{M,q}(XF_{nk+j})=\mathrm{𝔾}_{M(qO_L),O_L}\left((XF_{nk+j})(qO_L)\right).$$

Applying the same argument for arbitrary $`\tau >0`$ we conclude that

$$\gamma _j(P\tau (XF_{nk+j}))=\mathrm{𝔾}_{\tau M\tau (qO_L),\tau O_L}\left(\tau (XF_{nk+j})\tau (qO_L)\right).$$
(24)   
We may think of $`\tau L`$ as $`\mathrm{}^{nk+j}`$, of $`\tau F_{nk+j}`$ as $`\tau B_{\mathrm{}}^{nk+j}`$, and of $`\tau (XF_{nk+j})`$ as an affine $`j`$-dimensional section of $`\tau B_{\mathrm{}}^{nk+j}`$. Thus for each $`t>0`$ Lemma $`3.3`$ can be used with $`\tau =t/d`$ and $`m=nk+j`$. By the definition of $`d`$, we have $`d\sqrt{kj}`$. Combining (18),(21) and $`(24)`$ we deduce that

$`\gamma _{j+1}(C)`$ $`{\displaystyle \frac{1}{\sqrt{2\pi }}}{\displaystyle _0^{\mathrm{}}}e^{t^2/2}\gamma _j\left(t\left({\displaystyle \frac{nk+j}{j(kj)}}\right)^{1/2}B_{\mathrm{}}^j\right)𝑑t`$   
$`={\displaystyle \frac{1}{\sqrt{2\pi }}}\left({\displaystyle \frac{j(kj)}{nk+j}}\right)^{1/2}{\displaystyle _0^{\mathrm{}}}\mathrm{exp}({\displaystyle \frac{j(kj)}{nk+j}}t^2/2)\gamma _j(tB_{\mathrm{}}^j)𝑑t.`$   
The proof of lemma 3.2 and thus of proposition $`3.1`$ is complete.        

By using the asymptotic formulas of section $`2`$, namely Lemma $`2.3`$ and Corollary $`2.4`$, we can now prove the following result, which shows that the lower bound for $`f(j,k,n)`$ derived from proposition $`3.1`$ is, in some cases, asymptotically best possible.

###### Corollary 3.4

For fixed integers $`1l<m`$,

$$f(nm,nl,n)\frac{(2n)^{ml}}{(ml)!}\text{as}n\mathrm{}.$$
(25)   
*Proof*. Put $`\alpha _n=(ml)(nm)/(nm+l)`$. By Proposition $`3.1`$,

$$\frac{f(0,ml,n)}{f(nm,nl,n)}<\sqrt{\frac{2\alpha _n}{\pi }}_0^{\mathrm{}}e^{\alpha _nt^2/2}\gamma _{nm}(tB_{\mathrm{}}^{nm})𝑑t.$$
(26)   
Put $`b_n=(\mathrm{log}(nm))^{(\alpha _n1)/2}/(nm)^{\alpha _n}`$ and $`c_n=(\mathrm{log}n)^{(ml1)/2}`$. Let $`d_n`$ denote the right hand side of $`(26)`$, from which we get

$$f(nm,nl,n)\frac{b_n}{c_n}>\frac{f(0,ml,n)}{c_n}\frac{b_n}{d_n}.$$

Since $`lim_n\mathrm{}\alpha _n=(ml)`$, Lemma $`2.3`$ implies that

$$\underset{n\mathrm{}}{lim}\frac{b_n}{d_n}=\frac{1}{\pi ^{(ml1)/2}\mathrm{\Gamma }(ml)\sqrt{ml}}.$$

Moreover, by Corollary $`2.4`$,

$$\underset{n\mathrm{}}{lim}\frac{f(0,ml,n)}{c_n}=\frac{2^{ml}\pi ^{(ml1)/2}}{\sqrt{ml}}.$$

Thus, the sequence $`f(nm,nl,n)\frac{b_n}{c_n}`$ is larger than a sequence that tends to $`2^{ml}/(ml)!`$ as $`n`$ tends to infinity. On the other hand we have $`f(nm,nl,n)<2^{ml}\left(\genfrac{}{}{0pt}{}{n}{ml}\right)`$, so

$$f(nm,nl,n)\frac{b_n}{c_n}<2^{ml}\left(\genfrac{}{}{0pt}{}{n}{ml}\right)\frac{b_n}{c_n},$$

and since $`b_n/c_nn^{lm}`$, the r.h.s here tends to $`2^{ml}/(ml)!`$. Consequently,

$$\underset{n\mathrm{}}{lim}f(nm,nl,n)\frac{b_n}{c_n}=\frac{2^{ml}}{(ml)!}.$$

The required asymptotic formula follows immediately. The proof of Corollary $`3.4`$ is complete.        

Remarks

1. The previous corollary implies that the number of $`(nm)`$-faces of a random $`(nl)`$-section of the $`n`$-cube tends to concentrate near the value $`2^{ml}\left(\genfrac{}{}{0pt}{}{n}{ml}\right)`$, which bounds it from above. So for example, a typical $`1`$-co-dimensional section of the $`n`$-cube will have $`2no(n)`$ facets as $`n\mathrm{}`$. This result can also be deduced from the identity (3). Indeed, by duality we have $`f(nm,nl,n)=\text{E}(f_{ml1}(\mathrm{\Pi }_{nl}(B_1^n)))`$, and replacing $`T^n`$ by $`B_1^n`$ in the proof of Theorem 2 in , (the details of this replacement appear in ; see the proof of Theorem 1.1 there) we get the previous corollary.

2. According to a remark made in , the number $`f(j,k,n)`$ is equal to the expected number of $`(kj1)`$-faces of the convex hull of $`\pm G_1,\mathrm{},\pm G_n`$, where the $`G_i`$’s are independent copies of a $`k`$-dimensional Gaussian vector. Hence, the results for $`f(0,k,n)`$ can be interpreted as results for the expected number of facets of the convex hull of $`\{\pm G_i\}_1^n`$ in $`\mathrm{}^k`$. For example, we can translate the first remark at the end of section $`2`$ to the following statement: If $`3`$ points in the plane are chosen at random, then their symmetric convex hull is more likely to be a parallelogram than a hexagon.

Acknowledgements I thank Itai Benjamini for getting me interested in the subject of this paper, and for several stimulating discussions. I also thank the referees for their useful comments.

| Yossi Lonke | Current address: |
| --- | --- |
| Institute of Mathematics | Department of Mathematics |
| The Hebrew University of Jerusalem | Case Western Reserve University |
| Jerusalem 91904, Israel | Cleveland, Ohio 44106-7058 |
|  | email: jrl16@po.cwru.edu |