# The minimum neighborliness of a random polytope

Brett Leroux

###### Abstract

Let $\mu$ be a probability distribution on $\operatorname{\mathbb{R}}^{d}$
which assigns measure zero to every hyperplane and $S$ a set of points sampled
independently from $\mu$. What can be said about the expected combinatorial
structure of the convex hull of $S$? These polytopes are simplicial with
probability one, but not much else is known except when more restrictive
assumptions are imposed on $\mu$. In this paper we show that, with probability
close to one, the convex hull of $S$ has a high degree of neighborliness no
matter the underlying distribution $\mu$ as long as $n$ is not much bigger
than $d$. As a concrete example, our result implies that if for each $d$ in
$\mathbb{N}$ we choose a probability distribution $\mu_{d}$ on
$\operatorname{\mathbb{R}}^{d}$ which assigns measure zero to every hyperplane
and then set $P_{n}$ to be the convex hull of an i.i.d. sample of $n\leq 5d/4$
random points from $\mu_{d}$, the probability that $P_{n}$ is $k$-neighborly
approaches one as $d\to\infty$ for all $k\leq d/20$. We also give a simple
example of a family of distributions which essentially attain our lower bound
on the $k$-neighborliness of a random polytope.

##  1 Introduction

The most well-studied models of random polytopes are those where a random
polytope is defined as the convex hull of a set of independent and identically
distributed points from some probability distribution on the space
$\operatorname{\mathbb{R}}^{d}$. These objects have been studied for several
reasons. One reason is that random polytopes can sometimes give us some
insight into the possible metric or combinatorial properties of deterministic
convex polytopes with a given dimension and number of vertices. Another is
that convex polytopes have a wide range of applications in geometric
algorithms including the simplex method [7] and Wolfe’s method [20]. For many
such algorithms, the input data defines a convex polytope and it is useful to
understand combinatorial and metric properties of that polytope in order to
understand the complexity of the algorithm. Since algorithmic applications
often assume that the input data is random according to some predetermined
distribution, random polytopes are particularly relevant.

Gaussian random polytopes, i.e. random polytopes where the underlying
distribution is the standard Gaussian distribution on
$\operatorname{\mathbb{R}}^{d}$ have received much attention [3, 5, 15, 16,
21, 22]. Perhaps the main reason for this focus on Gaussian random polytopes
is that they coincide in distribution with uniform random projections of a
simplex to some lower dimensional space [6]. Another reason is that the
Gaussian distribution has many nice properties which often make calculations
simpler and behavior of combinatorial properties easier to determine. Other
commonly studied families of random polytopes are those for which the
underlying distribution is the uniform distribution on a convex body or the
boundary of a convex body. Yet another important example is _random $0/1$
polytopes_ [17] where the vertices are a random subset of the vertices of the
$d$-dimensional cube. Some papers prove results which assume only that the
underlying distribution has some property such as being log-concave [8] or
subgaussian [19].

In all of these examples, either the distribution is specified, or it
satisfies some restrictive condition such as being subgaussian. Our main
result in contrast assumes only that the distribution assigns measure zero to
every (affine) hyperplane. With this assumption only, we consider random
polytopes where the number of random points is proportional to the dimension
and the dimension approaches infinity. The main property of convex polytopes
we are interested in is $k$-neighborliness (defined in Section 1.2). One of
our main results shows that if the constant of proportionality is less than
two, then there exists some constant $\beta>0$ (depending on the constant of
proportionality), such that the probability that the random polytope is at
least $\lfloor\beta d\rfloor$-neighborly approaches one as the dimension
approaches infinity (Theorem 3).

To put this result in context, we need to review what has previously been
known about the neighborliness of random polytopes. First we collect some
notation.

###  1.1 Notation

Asymptotic notation $f(n)\sim g(n)$ means $f(n)/g(n)\to 1$ as $n\to\infty$.
For a set of points $X\subset\operatorname{\mathbb{R}}^{d}$,
$\operatorname{conv}X$ is the convex hull of $X$. Similarly,
$\operatorname{aff}X$ is the affine hull of $X$. The _binary entropy function_
is the function defined by $H(p):=-p\log_{2}p-(1-p)\log_{2}(1-p)$. We use $o$
to denote the origin in $\operatorname{\mathbb{R}}^{d}$. For a polytope $P$,
we use the notation $f_{\ell}(P)$ for the number of $\ell$-dimensional faces
of the polytope $P$. When we say that a probability distribution assigns
measure zero to every hyperplane we mean every affine hyperplane (not just
every linear hyperplane) unless otherwise specified.

###  1.2 Previous work on the neighborliness of random polytopes

######  Definition 1.

A polytope $P$ is _$k$ -neighborly_ if every subset of at most $k$ vertices is
a face of the polytope.

See [14] for an introduction to polytopes and [14, Chapter 7] for
$k$-neighborly polytopes in particular.

In addition to our results about $k$-neighborliness, we will also consider
another quantity associated to polytopes which measures how close the polytope
is to being $k$-neighborly.

######  Definition 2.

For a simplicial polytope $P\subset\operatorname{\mathbb{R}}^{d}$ with $n$
vertices and any $0\leq\ell\leq d-1$, the _$\ell$ -face density_ of $P$ is
$f_{\ell}(P)/\binom{n}{\ell+1}$.

We see that the $\ell$-face density of a polytope measures how close to being
$k$-neighborly the polytope is where $k=\ell+1$. If the $\ell$-face density is
one, then the polytope is $(\ell+1)$-neighborly. In addition to showing that a
random polytope is $k$-neighborly for a surprisingly large value of $k$, we
will show that a random polytope has $\ell$-face density close to one where
$\ell$ is even larger than $k$.

It was perhaps Gale who first speculated that random polytopes should have a
high degree of neighborliness when the dimension of the space is high [12].
More recently, it has been rigorously proven that random polytopes from
certain families of probability distributions tend to have a surprisingly high
degree of neighborliness with high probability [2, 4, 9, 10, 11, 14, 12, 19,
23, 25]. Two of these works, the paper [10] of Donoho and Tanner, and the
paper [25] of Vershik and Sporyshev are particularly relevant to this paper so
we give an overview of their results.

A _Gaussian random polytope_ is the convex hull of an i.i.d. sample of points
from the standard (mean zero and identity covariance matrix) Gaussian
distribution on $\operatorname{\mathbb{R}}^{d}$. Donoho and Tanner show in
[10] that there exists a function $\rho_{DT}(\delta)$ such that if
$\rho<\rho_{DT}(\delta)$ and $G_{n,d}$ is a Gaussian random polytope in
$\operatorname{\mathbb{R}}^{d}$ with $n$ random points with $d\geq\delta n$,
then the probability that $G_{n,d}$ is $\lfloor\rho d\rfloor$-neighborly
approaches one as $d$ approaches infinity ([10, Theorem 1]). Furthermore, they
show that if $\rho>\rho_{DT}(\delta)$, then the expected number of subsets of
the points of size $\lfloor\rho d\rfloor$ which are not faces of the polytope
approaches infinity as $d\to\infty$.

Vershik and Sporyshev establish a similar result for the $\ell$-face density.
They show that there exists a function $\rho_{VS}(\delta)$ such that if
$d=d(n)\sim\delta n$ and $\ell=\ell(n)\sim\rho d$ where
$\rho<\rho_{VS}(\delta)$, then the expected $\ell$-face density of $G_{n,d}$
approaches one as $d$ approaches infinity and that if
$\rho>\rho_{VS}(\delta)$, then the expected $\ell$-face density approaches
zero as $d$ approaches infinity [25, Theorem 1].

###  1.3 Our results

Our two main results are similar to the two results explained in the previous
section, the first due to Donoho and Tanner, and the second due to Vershik and
Sporyshev. The main difference is that our results apply to any random
polytope whose vertices are i.i.d. according to a probability distribution on
$\operatorname{\mathbb{R}}^{d}$ which assigns measure zero to every
hyperplane. This is a very weak assumption on the distribution. In particular,
it is the minimal assumption which guarantees that the random polytopes under
consideration are simplicial with probability one. Not surprisingly, because
of the generality of the distributions we consider, our result guarantees a
lower degree of neighborliness than in the case where the distribution is
Gaussian.

######  Theorem 3.

Let $\alpha<2$ and assume that $\beta>0$ satisfies $\alpha
H(\beta/\alpha)+(\alpha-\beta)(H(\frac{\alpha-1}{\alpha-\beta})-1)<0$, or
equivalently,
$\frac{\alpha^{\alpha}}{(\alpha-1)^{\alpha-1}2^{\alpha}}<\frac{\beta^{\beta}(1-\beta)^{1-\beta}}{2^{\beta}}$.
For each $d\in\mathbb{N}$, let $\mu_{d}$ be a probability distribution on
$\operatorname{\mathbb{R}}^{d}$ which assigns measure zero to every
hyperplane. Let $n:=n(d)\sim\alpha d$ and let $S_{n}$ be a set of $n$
independent and identically distributed points from $\mu_{d}$. Then for any
sequence $k:=k(d)$ with $k\sim\beta d$, the probability that
$\operatorname{conv}S_{n}$ is $k$-neighborly approaches one as $d\to\infty$.

Figure 1: $\rho_{N}^{\prime}$ (dashed) and $\rho_{D}^{\prime}$. The lower
curve shows that value of $\rho_{N}^{\prime}(\alpha)$ for each
$\alpha\in(1,2)$ which is the lower bound on the neighborliness of a random
polytope with $\sim\alpha d$ vertices. The upper curves shows the value of
$\rho_{D}^{\prime}(\alpha)$ for each $\alpha\in(1,2)$ which is the lower bound
on the $\ell$-face density.

In Theorem 3 the equation $\alpha
H(\beta/\alpha)+(\alpha-\beta)(H(\frac{\alpha-1}{\alpha-\beta})-1)=0$
implicitly determines a function which we denote $\rho_{N}^{\prime}(\alpha)$
and which is plotted in Fig. 1. By Theorem 3, the function
$\rho_{N}^{\prime}(\alpha)$ has the property that if
$\rho<\rho_{N}^{\prime}(\alpha)$, then the probability that a random polytope
in $\operatorname{\mathbb{R}}^{d}$ with $\sim\alpha d$ vertices will be at
least $\lfloor\rho d\rfloor$-neighborly approaches one as $d\to\infty$. We
have a similar result for the $\ell$-face density:

######  Theorem 4.

Let $\alpha<2$ and $0<\beta<2-\alpha$. For each $d\in\mathbb{N}$, let
$\mu_{d}$ be a probability distribution on $\operatorname{\mathbb{R}}^{d}$
which assigns measure zero to every hyperplane. Let $n:=n(d)\sim\alpha d$ and
let $S_{n}$ be a set of $n$ independent and identically distributed points
from $\mu_{d}$. Then for any sequence $\ell:=\ell(d)$ with $\ell\sim\beta d$,
the expected $\ell$-face density of $\operatorname{conv}S_{n}$ approaches one
as $d\to\infty$.

Figure 2: $\rho_{N}$ (dashed) and $\rho_{D}$. The lower curve shows that value
of $\rho_{N}(\delta)$ for each $\delta\in(1/2,1)$ which is the lower bound on
the neighborliness of a random polytope with $\sim(1/\delta)d$ vertices. The
upper curves shows the value of $\rho_{D}(\delta)$ for each $\delta\in(1/2,1)$
which is the lower bound on the $\ell$-face density.

We define the function $\rho_{D}^{\prime}(\alpha)=2-\alpha$. By Theorem 3, the
function $\rho_{D}^{\prime}(\alpha)$ has the property that if
$\rho<\rho_{D}^{\prime}(\alpha)$, then the expected $\lfloor\rho
d\rfloor$-face density of a random polytope in $\operatorname{\mathbb{R}}^{d}$
with $\sim\alpha d$ vertices approaches one as $d\to\infty$. The function
$\rho_{D}^{\prime}(\alpha)$ is also plotted in Fig. 1.

Recall that the functions $\rho_{VS}(\delta)$ and $\rho_{DT}(\delta)$
discussed in Section 1.2 are defined as functions of $\delta$ where the
dimension $d$ satisfies $d\sim\delta n$ where $n$ is the number of vertices.
In contrast, we defined the functions $\rho_{N}^{\prime}(\alpha)$ and
$\rho_{D}^{\prime}(\alpha)$ as functions of $\alpha$ where the number of
vertices $n$ satisfies $n\sim\alpha d$. Therefore in order to compare the
above the results to the results for the Gaussian case discussed in Section
1.2, we set $\delta=1/\alpha$ and define functions
$\rho_{N}(\delta):=\rho_{N}^{\prime}(1/\delta)$ and
$\rho_{D}(\delta):=\rho_{D}^{\prime}(1/\delta)$. These functions are plotted
in Fig. 2 and can be compared with the functions $\rho_{VS}(\delta)$ and
$\rho_{DT}(\delta)$ which are plotted in [10, Figure 1].

In Section 3.2 we show that the above two results are close to best possible
by constructing a family of distributions on $\operatorname{\mathbb{R}}^{d}$
which show that Theorem 3 (resp. Theorem 4) is not true if
$\rho_{N}^{\prime}(\alpha)$ (resp. $\rho_{D}^{\prime}(\alpha)$) is replaced by
a function which is strictly less than $\rho_{N}^{\prime}(\alpha)$ (resp.
$\rho_{D}^{\prime}(\alpha)$) for any $\alpha$ in the range $(1,2)$.

###  1.4 Applications

As discussed earlier, one of the main reasons to study random polytopes is to
help understand the average behavior of algorithms where the input data can be
thought of as a convex polytope. For the specific property of
$k$-neighborliness, the main application is to _compressed sensing_ , see [10]
for an explanation of the connection of $k$-neighborliness to compressed
sensing. This connection is what has motivated much of the work on the
neighborliness of random polytopes some of which was cited in Section 1.2.

###  1.5 Outline of the paper

Section 2 contains the proofs of Theorems 3 and 4. Before proving the
theorems, we explain the idea behind the proof in Section 2.1 and also in that
section we explain the main tool behind the proofs. The main tool is a
generalization of a result of Wagner and Welzl [27] which gives an upper bound
on the probability that a given point is in the convex hull of a sample of
random points.

Section 3 contains the construction of the distributions which show that
Theorems 3 and 4 are essentially best possible. In other words, we construct
distributions which produce the least neighborly polytopes over all
distributions which assign measure zero to every hyperplane. In order to prove
that the distributions we construct have the desired property, we require a
result which gives a lower bound on the probability that a given point is in
the convex hull of a sample of random points. More specifically, given a
distribution on $\operatorname{\mathbb{R}}^{d}$ and a point in
$\operatorname{\mathbb{R}}^{d}$ which is at some _depth_ (Definition 10) with
respect to the distribution, we prove a lower bound on the probability that
point is in the convex hull of a sample of random points where this
probability depends on the depth of the point (Proposition 11).

##  2 The lower bound on the neighborliness

Section 2.1 explains the main idea behind the proof of Theorems 3 and 4 and
outlines the main tool for the proof. The proof is completed in Section 2.2
after establishing some necessary lemmas.

###  2.1 An upper bound on the probability that a point is in the convex hull

Wendel’s theorem ([28],[24, Theorem 8.2.1]) is a classic result in geometric
probability which says that the probability that a set of $n$ i.i.d. random
points from a distribution on $\operatorname{\mathbb{R}}^{d}$ which is
symmetric about $o$ and which assigns measure zero to every linear hyperplane
is equal to $\frac{\sum_{i=0}^{n-d-1}\binom{n-1}{i}}{2^{n-1}}$. More recently,
Wendel’s theorem has been generalized by Wagner and Welzl in the following
way. An _absolutely continuous_ probability distribution on
$\operatorname{\mathbb{R}}^{d}$ is a probability distribution which has a
density function with respect to the Lebesgue measure on
$\operatorname{\mathbb{R}}^{d}$. A measure $\mu$ is _balanced about a point
$p$_ if every hyperplane through $p$ divides $\mu$ into two equal halves.
Wagner and Welzl showed the following

######  Theorem 5 ([27, Corollary 3.7]).

Let $\mu$ be an absolutely continuous probability measure on
$\operatorname{\mathbb{R}}^{d}$. Let $S$ be a set of $n$ independent and
identically distributed points from $\mu$. Then the probability that
$\operatorname{conv}S$ contains the origin is at most

$\frac{\sum_{i=0}^{n-d-1}\binom{n-1}{i}}{2^{n-1}}=1-\frac{\sum_{i=0}^{d-1}\binom{n-1}{i}}{2^{n-1}}.$

and this bound is attained if and only if $\mu$ is balanced about the origin.

Why is this sort of result useful for our purposes? In order to prove Theorem
3, we need to show that certain random polytopes are $k$-neighborly with
probability close to one. Therefore, we need an upper bound on the probability
that the polytope is not $k$-neighborly. By the union bound, this probability
is upper bounded by $\binom{n}{k}$ times the probability that a subset $K$ of
the vertices of size $k$ is not a face of the polytope. A standard fact about
polytopes is that $\operatorname{conv}K$ is not a face of the polytope if and
only if the affine hull of $K$ intersects the convex hull of the remaining
vertices of the polytope (Proposition 8). Therefore, letting $V$ denote the
set of vertices of the polytope, if we project $V$ to the subspace which is
orthogonal to the affine hull of $K$, then the event that
$\operatorname{conv}K$ is not a face of the polytope is equivalent to the
event that the convex hull of $V\setminus K$ contains the projection of the
affine hull of $K$ which is a point in the image space of the projection.
Theorem 5 can then be used to given an upper bound for the probability of this
event.

Rather than using Theorem 5, we will prove another version of this result
which applies not just to absolutely continuous distribution but to any
distribution which assigns measure zero to every hyperplane. We also give a
proof of this result which is very different from the proof of Theorem 5 given
in [27]. However the following result is not entirely new; it was mentioned in
[27] that such a proof works but no details were given.

######  Theorem 6.

Let $\mu$ be a probability measure on $\operatorname{\mathbb{R}}^{d}$ that
assigns measure zero to every hyperplane. Let $S$ be a set of $n$ independent
and identically distributed points from $\mu$. Then the probability that
$\operatorname{conv}S$ contains the origin is at most

$\frac{\sum_{i=0}^{n-d-1}\binom{n-1}{i}}{2^{n-1}}.$

###### Proof.

The quantity of interest is

$\mathbb{P}(o\in\operatorname{conv}(X_{1},\dotsc,X_{n})).$

Note that since $\mu$ assigns measure zero to ever hyperplane (and, in
particular, every hyperplane through the origin), the probability that some
$\ell$-flat through the origin contains more than $\ell$ points is zero. This
means that the probability that $\operatorname{conv}(X_{1},\dotsc,X_{n})$
contains the origin on its boundary is zero and so the above probability is
equal to

$p:=\mathbb{P}(o\in\operatorname{int}\operatorname{conv}(X_{1},\dotsc,X_{n})).$

Let $X_{1},\dotsc,X_{N}$ be $N$ i.i.d. points distributed according to $\mu$
where $N>n$ is some integer. Now we consider the _Gale transform_ [14, Section
5.4] of the set of points $\\{X_{1},\dotsc,X_{N}\\}$. The Gale transform of
$\\{X_{1},\dotsc,X_{N}\\}$ is a set $\bar{X}_{N}$ of $N$ points in
$\operatorname{\mathbb{R}}^{N-d-1}$ and by [14, 5.4.1] there is a one-to-one
correspondence between subsets of $\\{X_{1},\dots,X_{N}\\}$ of size $n$ which
contain the origin in their interior and subsets of $\bar{X}_{N}$ of size
$N-n$ which are faces of the polytope $\operatorname{conv}\bar{X}_{N}$. We
note that since no hyperplane through the origin contains more than $d-1$
points of $\\{X_{1},\dotsc,X_{N}\\}$ with probability one, the polytope
$\operatorname{conv}\bar{X}_{N}$ is simplicial with probability one [14,
Section 5.4].

By the Upper Bound Theorem for convex polytopes [18], and the formula for the
number of faces of each dimension of a cyclic polytope, see for example [13,
Theorem 17.3.4], the number of subsets of $\bar{X}_{N}$ of size $N-n$ which
are faces of the polytope $\operatorname{conv}\bar{X}_{N}$ is at most

$\displaystyle
C(N,n,d):=\frac{N-\delta(n-1)}{n}\sum_{j=0}^{\lfloor\frac{N-d-1}{2}\rfloor}\binom{N-1-j}{n-1}\binom{n}{N-2j+\delta}$
(1)

where $\delta=N-d-1-2\lfloor(N-d-1)/2\rfloor$. Therefore, we know that the
expected number of subsets of $\\{X_{1},\dotsc,X_{N}\\}$ of size $n$ which
contain the origin in the interior of their convex hull is at most $C(N,n,d)$,
i.e.,

$\displaystyle p\cdot\binom{N}{n}\leq C(N,n,d).$

Therefore, in order to prove the desired bound on $p$, it will suffice to show
that

$\displaystyle\lim_{N\to\infty}\frac{C(N,n,d)}{\binom{N}{n}}=\frac{\sum_{i=0}^{n-d-1}\binom{n-1}{i}}{2^{n-1}}.$
(2)

To make the calculation simpler, we will restrict our attention to values of
$N$ such that $N-d-1$ is even, i.e. the parity of $N$ is the opposite of the
parity of $d$. This means that $\delta=0$. For the terms in Eq. 1 to be non-
zero, we need $N-2j+\delta\leq n$ and so $2j\geq N+\delta-n$. Therefore, Eq. 1
equals

$\frac{N}{n}\sum_{j=\lceil\frac{N-n}{2}\rceil}^{\frac{N-d-1}{2}}\binom{N-1-j}{n-1}\binom{n}{N-2j}=\frac{N}{n}\sum_{j=\lceil\frac{N-n}{2}\rceil}^{\frac{N-d-1}{2}}\binom{N-1-j}{n-1}\bigg{(}\binom{n-1}{N-2j-1}+\binom{n-1}{N-2j}\bigg{)}$

Letting $m=(N-d-1)/2-j$ and using that
$(N-d-1)/2-\lceil\frac{N-n}{2}\rceil=\lfloor\frac{n-d-1}{2}\rfloor$, the above
is equal to

$\displaystyle\frac{N}{n}\sum_{m=0}^{\lfloor\frac{n-d-1}{2}\rfloor}\binom{N-1-(N-d-1)/2-m}{n-1}\bigg{(}\binom{n-1}{d+1+2m-1}+\binom{n-1}{d+1+2m}\bigg{)}$
$\displaystyle=\frac{N}{n}\sum_{m=0}^{\lfloor\frac{n-d-1}{2}\rfloor}\binom{N/2+(d+1)/2-1-m}{n-1}\bigg{(}\binom{n-1}{d+1+2m-1}+\binom{n-1}{d+1+2m}\bigg{)}$
$\displaystyle\stackrel{{\scriptstyle
N\to\infty}}{{\sim}}\frac{N^{n}}{n!}\frac{1}{2^{n-1}}\sum_{m=0}^{\lfloor\frac{n-d-1}{2}\rfloor}\bigg{(}\binom{n-1}{d+1+2m-1}+\binom{n-1}{d+1+2m}\bigg{)}$
$\displaystyle=\frac{N^{n}}{n!}\frac{1}{2^{n-1}}\sum_{i=0}^{n-d-1}\binom{n-1}{i}.$

Since $\binom{N}{n}\stackrel{{\scriptstyle
N\to\infty}}{{\sim}}\frac{N^{n}}{n!}$, Eq. 2 follows. ∎

###  2.2 Proofs of Theorems 3 and 4

In this section we prove Theorems 3 and 4. Before proving the theorems we need
to make rigorous the idea explained in Section 2.1. That is we first show how
Theorem 6 can be used to upper bound the probability that a subset of vertices
of a random polytope is not a face of the polytope. This bound is given in
Theorem 9. First we need a simple corollary of Theorem 6:

######  Corollary 7.

Let $\mu$ be a probability measure on $\operatorname{\mathbb{R}}^{d}$ that
assigns measure zero to every hyperplane. Let $S:=\\{X_{1},\dotsc,X_{n}\\}$ be
a set of $n$ independent and identically distributed points from $\mu$. Let
$L\subset\operatorname{\mathbb{R}}^{d}$ be some affine $\ell$-flat. Then the
probability that $L\cap\operatorname{conv}S\neq\emptyset$ is at most

$\frac{\sum_{i=0}^{n-(d-\ell)-1}\binom{n-1}{i}}{2^{n-1}}.$

###### Proof.

Note that any affine coordinate transformation of
$\operatorname{\mathbb{R}}^{d}$ preserves the fact that $\mu$ assigns measure
zero to every hyperplane. Therefore, after applying an affine coordinate
transformation to $\mu$, we may assume that $L$ is the span of the first
$\ell$ standard basis vectors in $\operatorname{\mathbb{R}}^{d}$. We can
identify $\operatorname{\mathbb{R}}^{d-\ell}$ with
$\\{0,\dotsc,0\\}\times\operatorname{\mathbb{R}}^{d-\ell}\subset\operatorname{\mathbb{R}}^{d}$.
Let $\pi_{d-\ell}$ denote the orthogonal projection onto
$\operatorname{\mathbb{R}}^{d-\ell}$.

The probability that $L\cap\operatorname{conv}S\neq\emptyset$ is equal to the
probability that $\operatorname{conv}(\tilde{X_{1}},\dotsc,\tilde{X_{n}})$
contains the origin where the $\tilde{X_{i}}$ are independent and distributed
according to the projection of $\mu$ by $\pi_{d-\ell}$. The corollary now
follows from Theorem 6. ∎

The above corollary is useful for our purposes due to the following well-known
fact:

######  Proposition 8 ([14, Exercise 3.1.1]).

Let $P$ be a polytope and $A\subset V(P)$. Then $\operatorname{conv}A$ is a
face of $P$ if and only if
$\operatorname{aff}A\cap\operatorname{conv}(V(P)\setminus A)=\emptyset$.

######  Theorem 9.

Let $\mu$ be a probability measure on $\operatorname{\mathbb{R}}^{d}$ that
assigns measure zero to every hyperplane. Let $S_{n}$ be a set of $n$
independent and identically distributed points from $\mu$. Then for any subset
$K$ of $S_{n}$ of size $k$, the probability that $\operatorname{conv}K$ is not
a face of $\operatorname{conv}S_{n}$ is at most

$\frac{\sum_{i=0}^{n-d-2}\binom{n-k-1}{i}}{2^{n-k-1}}.$

###### Proof.

Let $S_{n}:=\\{X_{1},\dotsc,X_{n}\\}$. Define

$f(x_{1},\dotsc,x_{n}):=\begin{cases}1&\text{ if
}\operatorname{conv}(x_{1},\dotsc,x_{n})\text{ is not a face of
}\operatorname{conv}S_{n}\\\ 0&\text{ otherwise}\end{cases}$

Since all the $X_{i}$ are independent and identically distributed, the
probability that $\operatorname{conv}(X_{i_{1}},\dotsc,X_{i_{k}})$ is not a
face of $\operatorname{conv}S_{n}$ is independent of the choice of subscripts.
The probability that $\operatorname{conv}(X_{n-k+1},\dotsc,X_{n})$ is not a
face of $\operatorname{conv}S_{n}$ is equal to

$\int_{\operatorname{\mathbb{R}}^{d}}\dotsc\int_{\operatorname{\mathbb{R}}^{d}}f(x_{n-k+1},\dotsc,x_{n})\mu(\mathop{}\\!\mathrm{d}x_{1})\dotsc\mu(\mathop{}\\!\mathrm{d}x_{n}).$
(3)

For any fixed choice of points $x_{n-k+1},\dotsc,x_{n}$, the inner integral

$\int_{\operatorname{\mathbb{R}}^{d}}\dotsc\int_{\operatorname{\mathbb{R}}^{d}}f(x_{n-k+1},\dotsc,x_{n})\mu(\mathop{}\\!\mathrm{d}x_{1})\dotsc\mu(\mathop{}\\!\mathrm{d}x_{n-k})$

is equal (by Proposition 8) to the probability that
$\operatorname{aff}(x_{n-k+1},\dotsc,x_{n})\cap\operatorname{conv}(S_{n}\setminus\\{x_{n-k+1},\dotsc,x_{n}\\})\neq\emptyset$.
If $\\{x_{n-k+1},\dotsc,x_{n}\\}$ are in general position, that is, they are
not contained in any affine $(k-2)$-flat, then by Corollary 7, this
probability is at most

$\frac{\sum_{i=0}^{n-d-2}\binom{n-k-1}{i}}{2^{n-k-1}}.$ (4)

Since $\mu$ assigns measure zero to every hyperplane, the measure of the set
of $\\{x_{n-k+1},\dotsc,x_{n}\\}$ which are contained in some affine
$(k-2)$-flat is zero. Therefore, Eq. 3 is the integral of a function that is
bounded by Eq. 4 except possibly on a set of measure zero, so statement of the
theorem follows. ∎

We can now prove the main results.

###### Proof of Theorem 3.

Let $S_{n}:=\\{X_{1},\dotsc,X_{n}\\}$. By Theorem 9 and the union bound, the
probability that $\operatorname{conv}S_{n}$ is not $k$-neighborly is at most

$\displaystyle\binom{n}{k}\frac{\sum_{i=0}^{n-d-2}\binom{n-k-1}{i}}{2^{n-k-1}}.$

So we just need to prove that this quantity goes to zero as $d\to\infty$. The
assumptions on $n,k,d$ imply that for $d$ sufficiently large,
$n-d-2<\frac{n-k-1}{2}$. Therefore, by the unimodality of the binomial
coefficients and using that $\binom{n}{k}\leq 2^{nH(k/n)}$, for $d$
sufficiently large,

$\displaystyle\binom{n}{k}\frac{\sum_{i=0}^{n-d-2}\binom{n-k-1}{i}}{2^{n-k-1}}$
$\displaystyle\leq\frac{\binom{n}{k}\cdot
n\cdot\binom{n-k-1}{n-d-2}}{2^{n-k-1}}$ $\displaystyle\leq
n\frac{2^{nH(k/n)}2^{(n-k-1)H((n-d-2)/(n-k-1))}}{2^{n-k-1}}$
$\displaystyle=n2^{nH(k/n)}2^{(n-k-1)\big{(}H((n-d-2)/(n-k-1))-1\big{)}}.$

Since $n\sim\alpha d$ and $k\sim\beta d$ we have that $n-d-2\sim(\alpha-1)d$
and $n-k-1\sim(\alpha-\beta)d$. So for $d$ sufficiently large, the above is at
most

$2\alpha d2^{\alpha
dH(\beta/\alpha)+(\alpha-\beta)d\big{(}H(\frac{\alpha-1}{\alpha-\beta})-1\big{)}}.$

This quantity goes to zero as $d\to\infty$ as long as $\alpha
H(\beta/\alpha)+(\alpha-\beta)(H(\frac{\alpha-1}{\alpha-\beta})-1)<0$ which is
the assumption on $\beta$. ∎

###### Proof of Theorem 4.

Let $S_{n}:=\\{X_{1},\dotsc,X_{n}\\}$. The expected $\ell$-face density of
$\operatorname{conv}S_{n}$ is equal to the probability that
$\operatorname{conv}(X_{1},\dotsc,X_{\ell+1})$ is a face of
$\operatorname{conv}S_{n}$. So we just need to show that the probability that
$\operatorname{conv}(X_{1},\dotsc,X_{\ell+1})$ is not a face of
$\operatorname{conv}S_{n}$ is $o(1)$ as $d\to\infty$. By Theorem 9, the
probability that $\operatorname{conv}(X_{1},\dotsc,X_{\ell+1})$ is not a face
of $\operatorname{conv}S_{n}$ is at most

$\frac{\sum_{i=0}^{n-d-2}\binom{n-\ell-2}{i}}{2^{n-\ell-2}}$

Since $n\sim\alpha d$ and $\ell\sim\beta d$, we know that

$\frac{n-d-2}{n-\ell-2}\sim\frac{\alpha-1}{\alpha-\beta}.$

By the assumption that $\beta<2-\alpha$, we have that
$\frac{\alpha-1}{\alpha-\beta}<1/2$. Therefore, there exists $\epsilon>0$ such
that for $d$ sufficiently large, $\frac{n-d-2}{n-\ell-2}<1/2-\epsilon$. By the
unimodality of the binomial coefficients, the fact that
$\frac{n-d-2}{n-\ell-2}<1/2-\epsilon$ implies that

$\frac{\sum_{i=0}^{n-d-2}\binom{n-\ell-2}{i}}{2^{n-\ell-2}}\leq\frac{n\binom{n-\ell-2}{n-d-2}}{2^{n-\ell-2}}$

Again using that $\binom{n}{k}\leq 2^{nH(k/n)}$, we have that for $d$
sufficiently large,

$\displaystyle\frac{\sum_{i=0}^{n-d-2}\binom{n-\ell-2}{i}}{2^{n-\ell-2}}$
$\displaystyle\leq\frac{n\binom{n-\ell-2}{n-d-2}}{2^{n-\ell-2}}$
$\displaystyle\leq\frac{n2^{(n-\ell-2)H(\frac{n-d-2}{n-\ell-2})}}{2^{n-\ell-2}}$
$\displaystyle\leq\frac{2\alpha
d2^{d(\alpha-\beta)H(1/2-\epsilon)}}{2^{d(\alpha-\beta)}}.$

And the above quantity goes to zero as $d\to\infty$ because $H(r)<1$ as long
as $r\neq 1/2$. ∎

##  3 The least neighborly distributions

As previously mentioned, we will construct a family of distributions
$\\{\mu_{d}\\}_{d\in\mathbb{N}}$ which show that Theorems 3 and 4 are in some
sense best possible. Before giving the construction, we need to establish the
following proposition, which gives the reverse of the bound given by Theorem 5
in Section 2.1.

###  3.1 A lower bound on the probability that a point is in the convex hull

######  Definition 10.

Let $\mu$ be a probability distribution on $\operatorname{\mathbb{R}}^{d}$ and
$p$ a point in $\operatorname{\mathbb{R}}^{d}$. The _depth of $p$ in $\mu$_ is
defined to be

$\min\\{\mu(H^{+})\mathrel{:}H^{+}\text{ is a closed halfspace containing
}p\\}.$

######  Proposition 11.

Let $\mu$ be an absolutely continuous probability distribution on
$\operatorname{\mathbb{R}}^{d}$. Let $S$ be a set of $n$ independent and
identically distributed points from $\mu$. Let
$p\in\operatorname{\mathbb{R}}^{d}$ be a point and assume that the depth of
$p$ in $\mu$ is greater than or equal to $a$. Then the probability that
$\operatorname{conv}S$ contains $p$ is greater than or equal to

$\displaystyle(d+1)\binom{n}{d+1}\int_{0}^{a}(y^{n-d-1}+(1-y)^{n-d-1})y^{d}\mathop{}\\!\mathrm{d}y$
$\displaystyle=\sum_{i=0}^{n-d-1}\binom{n}{i}a^{i}(1-a)^{n-i}+a^{n}\binom{n-1}{d}.$

###### Proof.

Note that it suffices to prove the statement when $p$ is the origin because
otherwise we could translate $p$ and $\mu$ to reduce to this case. Let
$p_{n,\mu}$ denote the probability that $\operatorname{conv}S$ contains the
origin, where $S$ is a set of $n$ independent and identically distributed
points from $\mu$. It is shown in [27] that there exists a function $h(y)$
(which depends only on $\mu$) such that

$p_{n,\mu}=2\binom{n}{d+1}\int_{0}^{1}y^{n-d-1}h(y)\mathop{}\\!\mathrm{d}y.$

For completeness, we give the definition of $h(y)$ from [27]: As in [27,
Section 2.2], we choose some absolutely continuous probability distribution
$\tilde{\mu}$ on $\operatorname{\mathbb{R}}^{d+1}$ such that the orthogonal
projection of $\tilde{\mu}$ to the first $d$ coordinates is the distribution
$\mu$ and we let $\tilde{\ell}$ be the $x_{d+1}$ axis in
$\operatorname{\mathbb{R}}^{d+1}$. Then as in [27, Section 1.2], we let
$\sigma$ denote a _$\tilde{\mu}$ -random oriented simplex_, i.e. a $d$-simplex
whose $d+1$ vertices are i.i.d. points from $\tilde{\mu}$ and one side of
$\sigma$ is chosen as the positive side which is denoted $H^{+}(\sigma)$.
Furthermore, we say that a directed line $\tilde{\ell}$ _enters_ an oriented
simplex $\sigma$ if it intersects the relative interior of $\sigma$ and is
directed from the positive to the negative side of $\sigma$. With this we
define

$H_{\tilde{\mu},\tilde{\ell}}:=\mathbb{P}(\tilde{\ell}\text{ enters
}\sigma\text{ and }\tilde{\mu}(H^{+}(\sigma))\leq y).$

We then define

$h(y):=h_{\tilde{\mu},\tilde{\ell}}(y):=\frac{\mathop{}\\!\mathrm{d}H_{\tilde{\mu},\tilde{\ell}}}{\mathop{}\\!\mathrm{d}y}.$

This completes the definition of $h(y)$, see [27] for more details.

Now by [27, Theorem 2.6], $h(y)=h(1-y)$ and so

$2\binom{n}{d+1}\int_{0}^{1}y^{n-d-1}h\mathop{}\\!\mathrm{d}y=2\binom{n}{d+1}\int_{0}^{1/2}(y^{n-d-1}+(1-y)^{n-d-1})h\mathop{}\\!\mathrm{d}y.$

By [27, Theorem 3.6] and the remarks following the proof of that theorem,
because of the assumption that the depth of $o$ in $\mu$ is greater than or
equal to $a$, the function $h$ satisfies $h=\frac{(d+1)}{2}\min(y,1-y)^{d}$
for $y\leq a$ and $y\geq 1-a$. Alternatively, see [26, Lemma 4.33] for a
rigorously stated proof of this claim. Therefore,

$\displaystyle p_{n,\mu}$
$\displaystyle\geq(d+1)\binom{n}{d+1}\int_{0}^{a}(y^{n-d-1}+(1-y)^{n-d-1})y^{d}\mathop{}\\!\mathrm{d}y.$

We use [1, 6.6.4] to get

$\int_{0}^{a}(1-y)^{n-d-1}y^{d}\mathop{}\\!\mathrm{d}y=\frac{(n-d-1)!d!}{n!}\sum_{i=0}^{n-d-1}\binom{n}{i}a^{i}(1-a)^{n-i}.$

And since $\int_{0}^{a}y^{n-1}\mathop{}\\!\mathrm{d}y=\frac{a^{n}}{n}$ and
$\frac{a^{n}}{n}(d+1)\binom{n}{d+1}=a^{n}\binom{n-1}{d}$,

$p_{n,\mu}\geq\sum_{i=0}^{n-d-1}\binom{n}{i}a^{i}(1-a)^{n-i}+a^{n}\binom{n-1}{d}.$

∎

We remark that a calculation similar to the one in the proof of Proposition 11
was done in [26, Theorem 4.32]. However, there is a mistake in that proof; the
summation formula they get for the integral is incorrect.

###  3.2 A family of distributions essentially attaining the lower bound

Here is the definition of the family of distributions: Let
$\epsilon_{d}:=\frac{1}{\sqrt{d}}$ (This choice is somewhat arbitrary). Let

$f(x_{1},\dotsc,x_{d}):=\frac{1}{(2\pi)^{d/2}}e^{-(1/2)(x_{1}^{2}+\cdots+x_{d}^{2})}$

be the probability density function of the standard (mean zero and identity
covariance matrix) Gaussian distribution on $\operatorname{\mathbb{R}}^{d}$.
Let $\mu_{d}$ be the distribution on $\operatorname{\mathbb{R}}^{d}$ with
density

$\big{(}1-\epsilon_{d}\big{)}f(x)+\epsilon_{d}\frac{1_{\\{\|x\|_{2}\leq\epsilon_{d}\\}}}{V_{d}}$

where $V_{d}$ is the volume of the $d$-ball with radius $\epsilon_{d}$. In
other words, $\mu_{d}$ is the combination of a Gaussian distribution having
$1-\epsilon_{d}$ of the mass (we call it the Gaussian part) and the uniform
distribution on the $d$-ball of radius $\epsilon_{d}$ (called the ball part)
having the remaining mass. Note that each distribution $\mu_{d}$ is absolutely
continuous. The following proposition shows that Theorem 4 is in some sense
best possible.

######  Proposition 12.

Let $\alpha>1$ and assume that $\beta>0$ satisfies $\beta>2-\alpha$. Let
$\\{\mu_{d}\\}_{d\in\mathbb{N}}$ be the family of probability distributions
defined at the start of this section. If for each $d\in\mathbb{N}$ we let
$n:=n(d)=\lfloor\alpha d\rfloor$ and let $S_{n}=\\{X_{1},\dotsc,X_{n}\\}$ be a
set of $n$ iid random points from $\mu_{d}$, then for any sequence
$\ell:=\ell(d)$ with $\ell\sim\beta d$, the expected $\ell$-face density of
$\operatorname{conv}S_{n}$ is $o(1)$ as $d\to\infty$.

###### Proof.

By definition, the expected $\ell$-face density of $\operatorname{conv}S_{n}$
is equal to the probability that
$\operatorname{conv}(X_{1},\dotsc,X_{\ell+1})$ is a face of
$\operatorname{conv}S_{n}$. Therefore, in order to show that the expected
$\ell$-face density is $o(1)$, it will suffice to show that the probability
that $\operatorname{conv}(X_{1},\dotsc,X_{\ell+1})$ is not a face of
$\operatorname{conv}S_{n}$ is $1-o(1)$.

First we will show that we can assume that at least one of the points
$\\{X_{i}\\}_{i\in[\ell+1]}$ is sampled from the ball part of the
distribution. Let $B$ be the event that at least one of the points
$\\{X_{i}\\}_{i\in[\ell+1]}$ is sampled from the ball part of the distribution
and $1_{B}$ the indicator function of the event $B$. Using that
$\big{(}1+x/y\big{)}^{y}<e^{x}$, we have that

$\mathbb{P}(\neg B)=\big{(}1-\epsilon_{d}\big{)}^{\ell+1}\leq
e^{-\epsilon_{d}(\ell+1)}=o(1).$

and so $\mathbb{P}(B)=1-o(1)$. This means that we ignore the case when event
$B$ is not satisfied. In particular, we have

$\displaystyle\mathbb{P}(\operatorname{conv}(X_{1},\dotsc,X_{\ell+1})\text{ is
not a face})$
$\displaystyle\geq\mathbb{P}(\operatorname{conv}(X_{1},\dotsc,X_{\ell+1})\text{
is not a face}\cap B)$

and so it suffices to show that
$\mathbb{P}(\operatorname{conv}(X_{1},\dotsc,X_{\ell+1})\text{ is not a
face}\cap B)=1-o(1)$.

Define

$f(x_{1},\dotsc,x_{\ell+1}):=\begin{cases}1&\text{ if
}\operatorname{conv}(x_{1},\dotsc,x_{\ell+1})\text{ is not a face}\\\ 0&\text{
otherwise}\end{cases}$

Then we have that

$\displaystyle\mathbb{P}(\operatorname{conv}(X_{1},\dotsc,X_{\ell+1})\text{ is
not a face}\cap B)$
$\displaystyle=\int_{\operatorname{\mathbb{R}}^{d}}\dotsc\int_{\operatorname{\mathbb{R}}^{d}}1_{B}f(x_{1},\dotsc,x_{\ell+1})\mu_{d}(\mathop{}\\!\mathrm{d}x_{n})\dotsc\mu_{d}(\mathop{}\\!\mathrm{d}x_{1}).$

Letting $B^{\prime}\subset\operatorname{\mathbb{R}}^{d(\ell+1)}$ be the set of
point sets satisfying $1_{B}=1$, we can rewrite the above as

$\displaystyle\mathbb{P}(\operatorname{conv}(X_{1},\dotsc,X_{\ell+1})\text{ is
not a face}\cap B)$
$\displaystyle=\int_{B^{\prime}}\int_{\operatorname{\mathbb{R}}^{d}}\dotsc\int_{\operatorname{\mathbb{R}}^{d}}f(x_{1},\dotsc,x_{\ell+1})\mu_{d}(\mathop{}\\!\mathrm{d}x_{n})\dotsc\mu_{d}(\mathop{}\\!\mathrm{d}x_{1}).$
(5)

For any fixed choice of points $x_{1},\dotsc,x_{\ell+1}$, the inner integral

$\displaystyle\int_{\operatorname{\mathbb{R}}^{d}}\dotsc\int_{\operatorname{\mathbb{R}}^{d}}f(x_{1},\dotsc,x_{\ell+1})\mu_{d}(\mathop{}\\!\mathrm{d}x_{n})\dotsc\mu_{d}(\mathop{}\\!\mathrm{d}x_{\ell+2})$
(6)

is equal to the probability that
$\operatorname{conv}(\\{X_{i}\\}_{i\in[\ell+2,n]})\cap L\neq\emptyset$ where
$L:=\operatorname{aff}(x_{1},\dotsc,x_{\ell+1})$. Under the assumption that
the points $x_{1},\dotsc,x_{\ell+1}$ satisfy $1_{B}=1$, we will show that this
probability is $1-o(1)$ and therefore that Eq. 6 is $1-o(1)$ for any choice of
$x_{1},\dotsc x_{\ell+1}$ such that $1_{B}=1$. Let $\pi_{L}$ be the orthogonal
projection of $\operatorname{\mathbb{R}}^{d}$ to the subspace $L^{\perp}$ of
dimension $d-\ell$ that is orthogonal to $L$. Let $\pi\mu_{d}$ denote the
measure on $L^{\perp}$ which is the projection of $\mu_{d}$. The probability
that $\operatorname{conv}(\\{X_{i}\\}_{i\in[\ell+2,n]})\cap L\neq\emptyset$ is
equal to the probability that
$\operatorname{conv}(\pi_{L}X_{\ell+2},\dotsc,\pi_{L}X_{n})$ contains $\pi L$.
Note that since at least one of the $x_{i}$, $1\leq i\leq\ell+1$ is sampled
from the ball part of the distribution, the distance from $L$ to the origin is
at most $\epsilon_{d}$. We claim that this means that the depth of $\pi L$ in
$\pi\mu_{d}$ is at least $(1-\epsilon_{d})(1/2-\epsilon_{d})$. In order to
show this, we need to show that every hyperplane in
$\pi_{L}\operatorname{\mathbb{R}}^{d}$ through $\pi L$ has at least
$(1-\epsilon_{d})(1/2-\epsilon_{d})$ of the mass of $\pi\mu_{d}$ on each side.
We will actually prove the stronger statement that every hyperplane in
$\operatorname{\mathbb{R}}^{d}$ which contains $L$ has has at least
$(1-\epsilon_{d})(1/2-\epsilon_{d})$ of the mass of $\mu_{d}$ on each side.
The Gaussian measure of halfspace determined by a hyperplane at distance less
than $\epsilon_{d}$ from the origin is greater than

$1/2-\frac{1}{\sqrt{2\pi}}\int_{0}^{\epsilon_{d}}e^{-x^{2}/2}\mathop{}\\!\mathrm{d}x\geq
1/2-\epsilon_{d}.$

And $1-\epsilon_{d}$ of the mass of $\mu_{d}$ is the standard Gaussian
measure. So the claim that the depth of $\pi L$ in $\pi\mu_{d}$ is at least
$(1-\epsilon_{d})(1/2-\epsilon_{d})\geq 1/2-2\epsilon_{d}$ follows.

Now by Proposition 11, the probability that
$\operatorname{conv}(\pi_{L}X_{\ell+2},\dotsc,\pi_{L}X_{n})$ contains $\pi L$
is at least

$(d-\ell+1)\binom{n-\ell-1}{d-\ell+1}\int_{0}^{1/2-2\epsilon_{d}}(y^{n-d-2}+(1-y)^{n-d-2})y^{d-\ell}\mathop{}\\!\mathrm{d}y.$

Using the formula in Proposition 11 along with the fact that
$\binom{n}{i}=\binom{n-1}{i-1}+\binom{n-1}{i}$ one can show that if the range
of integration is extended from $(0,1/2-\epsilon_{d})$ to $(0,1/2)$, then

$(d-\ell+1)\binom{n-\ell-1}{d-\ell+1}\int_{0}^{1/2}(y^{n-d-2}+(1-y)^{n-d-2})y^{d-\ell}\mathop{}\\!\mathrm{d}y=\frac{\sum_{i=0}^{n-d-2}\binom{n-\ell-2}{i}}{2^{n-\ell-2}}.$

Therefore, using that $\big{(}1+x/y\big{)}^{y}<e^{x}$, we have that

$\displaystyle(d-\ell+1)\binom{n-\ell-1}{d-\ell+1}\int_{0}^{1/2-2\epsilon_{d}}(y^{n-d-2}+(1-y)^{n-d-2})y^{d-\ell}\mathop{}\\!\mathrm{d}y$
$\displaystyle=\frac{\sum_{i=0}^{n-d-2}\binom{n-\ell-2}{i}}{2^{n-\ell-2}}-(d-\ell+1)\binom{n-\ell-1}{d-\ell+1}\int_{1/2-2\epsilon_{d}}^{1/2}(y^{n-d-2}+(1-y)^{n-d-2})y^{d-\ell}\mathop{}\\!\mathrm{d}y$
$\displaystyle\geq\frac{\sum_{i=0}^{n-d-2}\binom{n-\ell-2}{i}}{2^{n-\ell-2}}-2\epsilon_{d}(d-\ell+1)\binom{n-\ell-1}{d-\ell+1}\bigg{(}\frac{1}{2}+2\epsilon_{d}\bigg{)}^{n-\ell-2}$
$\displaystyle=\frac{\sum_{i=0}^{n-d-2}\binom{n-\ell-2}{i}}{2^{n-\ell-2}}-2\epsilon_{d}(d-\ell+1)\binom{n-\ell-1}{d-\ell+1}\frac{1}{2^{n-\ell-2}}\big{(}1+4\epsilon_{d}\big{)}^{n-\ell-2}$
$\displaystyle\geq\frac{\sum_{i=0}^{n-d-2}\binom{n-\ell-2}{i}}{2^{n-\ell-2}}-2\epsilon_{d}(d-\ell+1)\binom{n-\ell-1}{d-\ell+1}\frac{1}{2^{n-\ell-2}}e^{4\epsilon_{d}(n-\ell-2)}.$

First we claim that the second term above is $o(1)$. To show this, note that
since $\ell\sim\beta d$ and $n\sim\alpha d$,
$\frac{d-\ell-1}{n-\ell-2}\sim\frac{1-\beta}{\alpha-\beta}$. And by the
assumption that $\beta>2-\alpha$, we have that
$\frac{1-\beta}{\alpha-\beta}<\frac{1-\beta}{2-2\beta}=1/2$ and so there
exists $\epsilon>0$ such that for $d$ sufficiently large,
$\frac{d-\ell-1}{n-\ell-2}<1/2-\epsilon$. Now using that $\binom{n}{k}\leq
2^{nH(k/n)}$, we have that for $d$ sufficiently large,

$\displaystyle
2\epsilon_{d}(d-\ell+1)\binom{n-\ell-1}{d-\ell+1}\frac{1}{2^{n-\ell-2}}e^{4\epsilon_{d}(n-\ell-2)}$
$\displaystyle\leq
2\epsilon_{d}(d-\ell+1)\frac{2^{(n-\ell-1)H(1/2-\epsilon)}}{2^{n-\ell-2}}e^{8\sqrt{d}}$
$\displaystyle=o(1)$

because $H(1/2-\epsilon)<1$. This means that it suffices to show that
$2^{\ell+2-n}\sum_{i=0}^{n-d-2}\binom{n-\ell-2}{i}=1-o(1)$, or equivalently,
that
$2^{\ell+2-n}\sum_{i=n-d-1}^{n-\ell-2}\binom{n-\ell-2}{i}=2^{\ell+2-n}\sum_{j=0}^{d-\ell-1}\binom{n-\ell-2}{j}=o(1)$.
So by unimodality of the binomial coefficients, and again using that
$\binom{n}{k}\leq 2^{nH(k/n)}$,

$\displaystyle 2^{\ell+2-n}\sum_{j=0}^{d-\ell-1}\binom{n-\ell-2}{j}$
$\displaystyle\leq 2^{\ell+2-n}(d-\ell)\binom{n-\ell-2}{d-\ell-1}$
$\displaystyle\leq
2^{\ell+2-n}(d-\ell)2^{(n-\ell-2)H(\frac{d-\ell-1}{n-\ell-2})}$
$\displaystyle\leq 2^{\ell+2-n}(d-\ell)2^{(n-\ell-2)H(1/2-\epsilon)}.$

And the above quantity is $o(1)$ because $H(1/2-\epsilon)<1$.

This shows that Eq. 5 is the integral over $B^{\prime}$ of a function which is
uniformly bounded from below by a function which is equal to $1-o(1)$. Since
the measure of $B^{\prime}$ is equal to $\mathbb{P}(B)=1-o(1)$, this shows
that Eq. 5 is equal to $1-o(1)$ as desired. ∎

We can also prove a similar result for $k$-neighborliness of the distributions
$\mu_{d}$. (The distributions $\mu_{d}\\}_{d\in\mathbb{N}}$ in the following
proposition are the distributions defined at the beginning of this section.)

######  Proposition 13.

Let $\alpha>1$ and assume that $\beta>0$ satisfies $\alpha
H(\beta/\alpha)+(\alpha-\beta)(H(\frac{\alpha-1}{\alpha-\beta})-1)>0$, or
equivalently,
$\frac{\alpha^{\alpha}}{(\alpha-1)^{\alpha-1}2^{\alpha}}>\frac{\beta^{\beta}(1-\beta)^{1-\beta}}{2^{\beta}}$.
Let $\\{\mu_{d}\\}_{d\in\mathbb{N}}$ be the family of probability
distributions defined at the start of this section. If for each $d$ we let
$n:=n(d)=\lfloor\alpha d\rfloor$ and let $S_{n}=\\{X_{1},\dotsc,X_{n}\\}$ be a
set of $n$ iid random points from $\mu_{d}$, then for any sequence $k:=k(d)$
with $k\sim\beta d$, the expected number of subsets of $S_{n}$ of size $k$
which are not faces of $\operatorname{conv}S_{n}$ goes to infinity as
$d\to\infty$.

###### Proof.

Let $\\{\mu_{d}\\}_{d\in\mathbb{N}}$ be the distributions defined at the start
of this section.

Let $B$ be the event that at least one of the points $\\{X_{i}\\}_{i\in[k]}$
is sampled from the ball part of the distribution and $1_{B}$ the indicator
function of the event $B$. The same argument as in the proof of Proposition 12
shows that $\mathbb{P}(B)=1-o(1)$. We want to show that the expected number of
subsets of size $k$ which are not faces goes to infinity. It will suffice to
show that the expected number of subsets of size $k$ which contain at least
one point sampled from the ball part and which are not faces goes to infinity.
That is, it suffices to show that

$\binom{n}{k}\cdot\mathbb{P}(\operatorname{conv}(X_{1},\dotsc,X_{k})\text{ is
not a face}\cap B)\to\infty.$

Define

$f(x_{1},\dotsc,x_{\ell+1}):=\begin{cases}1&\text{ if
}\operatorname{conv}(x_{1},\dotsc,x_{k})\text{ is not a face}\\\ 0&\text{
otherwise}\end{cases}$

Then we have that

$\displaystyle\binom{n}{k}\mathbb{P}(\operatorname{conv}(X_{1},\dotsc,X_{\ell+1})\text{
is not a face}\cap B)$
$\displaystyle=\binom{n}{k}\int_{\operatorname{\mathbb{R}}^{d}}\dotsc\int_{\operatorname{\mathbb{R}}^{d}}1_{B}f(x_{1},\dotsc,x_{\ell+1})\mu_{d}(\mathop{}\\!\mathrm{d}x_{n})\dotsc\mu_{d}(\mathop{}\\!\mathrm{d}x_{1}).$

Letting $B^{\prime}\subset\operatorname{\mathbb{R}}^{d(\ell+1)}$ be the set of
point sets satisfying $1_{B}=1$, we can rewrite the above as

$\displaystyle\binom{n}{k}\mathbb{P}(\operatorname{conv}(X_{1},\dotsc,X_{k})\text{
is not a face}\cap B)$
$\displaystyle=\binom{n}{k}\int_{B^{\prime}}\int_{\operatorname{\mathbb{R}}^{d}}\dotsc\int_{\operatorname{\mathbb{R}}^{d}}f(x_{1},\dotsc,x_{k})\mu_{d}(\mathop{}\\!\mathrm{d}x_{n})\dotsc\mu_{d}(\mathop{}\\!\mathrm{d}x_{1}).$
(7)

For any fixed choice of points $x_{1},\dotsc,x_{k}$, the inner integral

$\displaystyle\int_{\operatorname{\mathbb{R}}^{d}}\dotsc\int_{\operatorname{\mathbb{R}}^{d}}f(x_{1},\dotsc,x_{k})\mu_{d}(\mathop{}\\!\mathrm{d}x_{n})\dotsc\mu_{d}(\mathop{}\\!\mathrm{d}x_{k+1})$
(8)

is equal to the probability that
$\operatorname{conv}(\\{X_{i}\\}_{i\in[k+1,n]})\cap L\neq\emptyset$ where
$L:=\operatorname{aff}(x_{1},\dotsc,x_{k})$.

Under the assumption that the points $x_{1},\dotsc,x_{k}$ satisfy $1_{B}=1$,
we will show that $\binom{n}{k}$ times this probability approaches infinity.
Let $\pi_{L}$ be the orthogonal projection of $\operatorname{\mathbb{R}}^{d}$
to the subspace $L^{\perp}$ of dimension $d-k+1$ that is orthogonal to $L$.
Let $\pi\mu_{d}$ denote the measure on $L^{\perp}$ which is the projection of
$\mu_{d}$. The probability that
$\operatorname{conv}(\\{X_{i}\\}_{i\in[k+1,n]})\cap L\neq\emptyset$ is equal
to the probability that
$\operatorname{conv}(\pi_{L}X_{k+1},\dotsc,\pi_{L}X_{n})$ contains $\pi L$.
Note that since at least one of the $x_{i}$, $1\leq i\leq k$ is sampled from
the ball part of the distribution, the distance from $L$ to the origin is at
most $\epsilon_{d}$. We claim that this means that the depth of $\pi L$ in
$\pi\mu_{d}$ is at least $(1-\epsilon_{d})(1/2-\epsilon_{d})$. In order to
show this, we need to show that every hyperplane in
$\pi_{L}\operatorname{\mathbb{R}}^{d}$ through $\pi L$ has at least
$(1-\epsilon_{d})(1/2-\epsilon_{d})$ of the mass of $\pi\mu_{d}$ on each side.
We will actually prove the stronger statement that every hyperplane in
$\operatorname{\mathbb{R}}^{d}$ which contains $L$ has has at least
$(1-\epsilon_{d})(1/2-\epsilon_{d})$ of the mass of $\mu_{d}$ on each side.
The Gaussian measure of halfspace determined by a hyperplane at distance less
than $\epsilon_{d}$ from the origin is greater than

$1/2-\frac{1}{\sqrt{2\pi}}\int_{0}^{\epsilon_{d}}e^{-x^{2}/2}\mathop{}\\!\mathrm{d}x\geq
1/2-\epsilon_{d}.$

And $1-\epsilon_{d}$ of the mass of $\mu_{d}$ is the standard Gaussian
measure. So the claim that the depth of $\pi L$ in $\pi\mu_{d}$ is at least
$(1-\epsilon_{d})(1/2-\epsilon_{d})\geq 1/2-2\epsilon_{d}$ follows.

Now by Proposition 11, the probability that
$\operatorname{conv}(\pi_{L}X_{k+1},\dotsc,\pi_{L}X_{n})$ contains $\pi L$ is
at least

$(d-k+2)\binom{n-k}{d-k+2}\int_{0}^{1/2-2\epsilon_{d}}(y^{n-d-2}+(1-y)^{n-d-2})y^{d-k+1}\mathop{}\\!\mathrm{d}y.$

Now using the fact that $\big{(}1+x/y\big{)}^{y}>e^{xy/(x+y)}$, and
$\binom{n}{k}=\binom{n}{n-k}$,

$\displaystyle\binom{n}{k}(d-k+2)\binom{n-k}{d-k+2}\int_{0}^{1/2-2\epsilon_{d}}(y^{n-d-2}+(1-y)^{n-d-2})y^{d-k+1}\mathop{}\\!\mathrm{d}y$
$\displaystyle\geq\binom{n}{k}(d-k+2)\binom{n-k}{d-k+2}\int_{1/2-3\epsilon_{d}}^{1/2-2\epsilon_{d}}(y^{n-d-2}+(1-y)^{n-d-2})y^{d-k+1}\mathop{}\\!\mathrm{d}y$
$\displaystyle\geq\binom{n}{k}(d-k+2)\binom{n-k}{d-k+2}\epsilon_{d}\Bigg{(}\frac{1}{2}-3\epsilon_{d}\Bigg{)}^{n-k-1}$
$\displaystyle=\binom{n}{k}(d-k+2)\epsilon_{d}\binom{n-k}{n-d-2}\frac{1}{2^{n-k-1}}\bigg{(}1-6\epsilon_{d}\bigg{)}^{n-k-1}$
$\displaystyle\geq\binom{n}{k}(d-k+2)\epsilon_{d}\binom{n-k}{n-d-2}\frac{1}{2^{n-k-1}}e^{-6\epsilon_{d}(n-k-1)/(6\epsilon_{d}+1)}.$

Now since $n\sim\alpha d$ and $k\sim\beta d$, we have that
$\frac{n-d-2}{n-k}\sim\frac{\alpha-1}{\alpha-\beta}$. And using the fact that
$\binom{n}{k}\geq(1/(n+1))2^{nH(k/n)}$, for $d$ sufficiently large the above
is lower bounded by

$\displaystyle\frac{1}{2}\cdot\frac{2^{\alpha
dH(\beta/\alpha)}2^{d(\alpha-\beta)H(\frac{\alpha-1}{\alpha-\beta})}}{2^{(\alpha-\beta)d}}\cdot\frac{(d-k+2)\epsilon_{d}e^{-6\epsilon_{d}(n-k-1)/(6\epsilon_{d}+1)}}{(n+1)(n-k+1)}$
$\displaystyle=\frac{1}{2}\cdot 2^{d\big{(}\alpha
H(\beta/\alpha)+(\alpha-\beta)(H(\frac{\alpha-1}{\alpha-\beta})-1)\big{)}}\cdot\frac{(d-k+2)\epsilon_{d}e^{-6\epsilon_{d}(n-k-1)/(6\epsilon_{d}+1)}}{(n+1)(n-k+1)}.$

And the above quantity goes to infinity as $d\to\infty$ because $\alpha
H(\beta/\alpha)+(\alpha-\beta)(H(\frac{\alpha-1}{\alpha-\beta})-1)>0$ and the
term $e^{-6\epsilon_{d}(n-k-1)/(6\epsilon_{d}+1)}$ is $\Omega(1/2^{\delta d})$
for all $\delta>0$.

We have shown that Section 3.2 is the integral over a set of measure $1-o(1)$
of a function which is uniformly bounded from below by a function which
approaches infinity as $d\to\infty$. This shows that the quantity in Section
3.2 approaches infinity. ∎

#### Acknowledgments.

Thanks to Luis Rademacher for many helpful discussions and comments. This
material is based upon work supported by the National Science Foundation under
Grants CCF-1657939, CCF-1934568 and CCF-2006994.

## References

  * [1] M. Abramowitz and I. A. Stegun, editors.  Handbook of mathematical functions with formulas, graphs, and mathematical tables.  A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York; John Wiley & Sons, Inc., New York, 1984.  Reprint of the 1972 edition, Selected Government Publications.
  * [2] R. Adamczak, A. E. Litvak, A. Pajor, and N. Tomczak-Jaegermann.  Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling.  Constr. Approx., 34(1):61–88, 2011.
  * [3] F. Affentranger and R. Schneider.  Random projections of regular simplices.  Discrete Comput. Geom., 7(3):219–226, 1992.
  * [4] I. Bárány and Z. Füredi.  On the shape of the convex hull of random points.  Probab. Theory Related Fields, 77(2):231–240, 1988.
  * [5] I. Bárány and V. Vu.  Central limit theorems for Gaussian polytopes.  Ann. Probab., 35(4):1593–1621, 2007.
  * [6] Y. M. Baryshnikov and R. A. Vitale.  Regular simplices and Gaussian samples.  Discrete Comput. Geom., 11(2):141–147, 1994.
  * [7] K.-H. Borgwardt.  The simplex method, volume 1 of Algorithms and Combinatorics: Study and Research Texts.  Springer-Verlag, Berlin, 1987.  A probabilistic analysis.
  * [8] S. Brazitikos, A. Giannopoulos, and M. Pafis.  Threshold for the expected measure of random polytopes.  Math. Ann., 2023.
  * [9] D. Donoho and J. Tanner.  Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing.  Philos. Trans. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., 367(1906):4273–4293, 2009.  With electronic supplementary materials available online.
  * [10] D. L. Donoho and J. Tanner.  Neighborliness of randomly projected simplices in high dimensions.  Proc. Natl. Acad. Sci. USA, 102(27):9452–9457, 2005.
  * [11] D. L. Donoho and J. Tanner.  Counting faces of randomly projected polytopes when the projection radically lowers dimension.  J. Amer. Math. Soc., 22(1):1–53, 2009.
  * [12] D. Gale.  Neighboring vertices on a convex polyhedron.  In Linear inequalities and related systems,, Annals of Mathematics Studies, no. 38., pages 255–263. ,, 1956.
  * [13] J. E. Goodman, J. O’Rourke, and C. D. Tóth, editors.  Handbook of discrete and computational geometry.  Discrete Mathematics and its Applications (Boca Raton). CRC Press, Boca Raton, FL, 2018.  Third edition of [ MR1730156].
  * [14] B. Grünbaum.  Convex polytopes, volume 221 of Graduate Texts in Mathematics.  Springer-Verlag, New York, second edition, 2003.  Prepared and with a preface by Volker Kaibel, Victor Klee and Günter M. Ziegler.
  * [15] D. Hug, G. O. Munsonius, and M. Reitzner.  Asymptotic mean values of Gaussian polytopes.  Beiträge Algebra Geom., 45(2):531–548, 2004.
  * [16] D. Hug and M. Reitzner.  Gaussian polytopes: variances and limit theorems.  Adv. in Appl. Probab., 37(2):297–320, 2005.
  * [17] V. Kaibel.  Low-dimensional faces of random $0/1$-polytopes.  In Integer programming and combinatorial optimization, volume 3064 of Lecture Notes in Comput. Sci., pages 401–415. Springer, Berlin, 2004.
  * [18] P. McMullen.  The maximum numbers of faces of a convex polytope.  Mathematika, 17:179–184, 1970.
  * [19] S. Mendelson, A. Pajor, and N. Tomczak-Jaegermann.  Reconstruction and subgaussian operators in asymptotic geometric analysis.  Geom. Funct. Anal., 17(4):1248–1282, 2007.
  * [20] L. Rademacher and C. Shu.  The smoothed complexity of Frank-Wolfe methods via conditioning of random matrices and polytopes.  Math. Stat. Learn., 5(3-4):273–310, 2022.
  * [21] H. Raynaud.  Sur l’enveloppe convexe des nuages de points aléatoires dans $R^{n}$. I.  J. Appl. Probability, 7:35–48, 1970.
  * [22] A. Rényi and R. Sulanke.  Über die konvexe Hülle von $n$ zufällig gewählten Punkten. II.  Z. Wahrscheinlichkeitstheorie und Verw. Gebiete, 3:138–147, 1964\.
  * [23] M. Rudelson and R. Vershynin.  Geometric approach to error-correcting codes and reconstruction of signals.  Int. Math. Res. Not., (64):4019–4041, 2005.
  * [24] R. Schneider and W. Weil.  Stochastic and integral geometry.  Probability and its Applications (New York). Springer-Verlag, Berlin, 2008\.
  * [25] A. M. Vershik and P. V. Sporyshev.  Asymptotic behavior of the number of faces of random polyhedra and the neighborliness problem.  volume 11, pages 181–201. 1992.  Selected translations.
  * [26] U. Wagner.  On $k$-sets and Applications.  PhD thesis, ETH Zürich, 2003.
  * [27] U. Wagner and E. Welzl.  A continuous analogue of the upper bound theorem.  volume 26, pages 205–219. 2001.  ACM Symposium on Computational Geometry (Hong Kong, 2000).
  * [28] J. G. Wendel.  A problem in geometric probability.  Math. Scand., 11:109–111, 1962.