# Polytopes and $C^1$-convex bodies

Karim Adiprasito, José Alejandro Samper

► To cite this version:

Karim Adiprasito, José Alejandro Samper. Polytopes and $C^1$-convex bodies. 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014), 2014, Chicago, United States. pp.277-288, 10.46298/dmtcs.2399 . hal-01207607

HAL Id: hal-01207607

https://inria.hal.science/hal-01207607

Submitted on 1 Oct 2015

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# The Lower Bound Theorem for polytopes
that approximate $C^1$-convex bodies

Karim Adiprasito<fnref n="1" />* and José Alejandro Samper<fnref n="2" />†

**Abstract.** The face numbers of simplicial polytopes that approximate $C^1$-convex bodies in the Hausdorff metric is studied. Several structural results about the skeleta of such polytopes are studied and used to derive a lower bound theorem for this class of polytopes. This partially resolves a conjecture made by Kalai in 1994: if a sequence ${P_n}_{n=0}^\infty$ of simplicial polytopes converges to a $C^1$-convex body in the Hausdorff distance, then the entries of the *g*-vector of $P_n$ converge to infinity.

**Résumé.** Nous étudions les nombres de faces de polytopes simpliciaux qui se rapprochent de $C^1$-corps convexes dans la métrique Hausdorff. Plusieurs résultats structurels sur le skelet de ces polytopes sont recherchés et utilisés pour calculer un théorème limite inférieure de cette classe de polytopes. Cela résolut partiellement une conjecture formulée par Kalai en 1994: si une suite $(P_n)_{n=0}^\infty$ de polytopes simpliciaux converge vers une $C^1$-corps convexe dans la distance Hausdorff, puis les entrées du *g*-vecteur de $P_n$ convergent vers l'infini.

**Keywords:** Geometric Combinatorics, *f*-vector theory, Polytopes, Approximation theory, Lower bound theorem, convex bodies

## 1 Introduction

The *g*-theorem was conjectured by McMullen (1971) and is one of the most celebrated theorems in the theory of convex polytopes. Billera and Lee (1980) proved the sufficiency, and Stanley (1980) proved the necessity of McMullen's conditions. It gives a complete characterization of the set of *f*-vectors of simplicial polytopes that makes it easy to verify computationally whether an integer vector is the *f*-vector of a simplicial polytope. To accomplish this, one transforms the *f*-vector into the *g*-vector, a certain vector with fewer entries that contains the same information as the *f*-vector.

The necessity part of the proof of this remarkable theorem uses heavy algebraic machinery: in one form or another, it invokes a Hard Lefschetz Theorem, either for the toric variety associated with a rational simplicial polytope (cf. Stanley (1980)), or for McMullen's weight algebra (cf. McMullen (1993)). In

<footnote n="1">¹Institut des Hautes Études Scientifiques, Bures-sur-Yvette, France</footnote>

<footnote n="2">²University of Washington, Seattle, USA</footnote>

<footnote>*Email: adiprasito@ihes.fr. K. Adiprasito has been supported by an EPDI postdoctoral fellowship and by the Romanian NASR, CNCS — UEFISCDI, project PN-II-ID-PCE-2011-3-0533.</footnote>

<footnote>†Email: samper@math.washington.edu. Jose Samper's research is partially supported by a graduate fellowship from NSF Grant DMS-1069298</footnote>
short, the known proofs of the *g*-theorem do not seem to be using a particular geometric realization of the polytope (apart from requiring that the realization be rational). Intuitively, metric properties coming from a specific embedding of a polytope are obstructions to getting certain shapes of *f*-vectors.

We will study a particular effect of geometry on the *f*-vector: if a polytope is close to a convex body whose boundary is sufficiently smooth, then the shape of the *g*-vector, and hence also of the *f*-vector is subject to additional constraints stronger than the ones of the general *g*-theorem. In particular, we resolve a part of a conjecture of Kalai (1994) asserting that any polytope that is a good approximation of a $C^1$-convex body is far away from being extremal for any of the inequalities of the *g*-theorem.

**Conjecture 1.1 (Kalai (1994))** Let $M$ be a $C^1$-convex body and let $\{P_n\}_{n=1}^\infty$ be a sequence of convex simplicial polytopes that converges to $M$ in the Hausdorff metric. Then

$$
(i) \lim_{n \to \infty} g_k(P_n) = \infty \text{ for } k = 1, 2, \dots, \lfloor \frac{d}{2} \rfloor, \text{ and}
$$

$$
(ii) \lim_{n \to \infty} (g_k(P_n) - \partial^{k+1} g_{k+1}(P_n)) = \infty \text{ for } k = 1, 2, \dots, \lfloor \frac{d}{2} \rfloor.
$$

We will prove part (i) of Kalai’s conjecture whenever $2k < d$. We furthermore announce a solution to the case $2k = d$, which requires a different method; the details of this proof, however, are too complicated to be included here.

2 Preliminaries

2.1 Polytopes and discrete geometry

A *polytope* P is the convex hull of finitely many points in a Euclidean space; equivalently it is a bounded intersection of finitely many closed half-spaces. A *face* of a polytope P is the intersection of a supporting hyperplane of P with P. The *dimension* of a face is the dimension of its affine span. Assume that P is *d*-dimensional. The *f-vector* of P is the vector $f_P := (f_{-1}, f_0, f_1, \dots, f_{d-1})$ where $f_i$ is the number of *i*-dimensional faces of P. A *simplex* is the convex hull of a set of affinely independent points, and a *k*-dimensional simplex has $k+1$ vertices. A polytope P is *simplicial* if all proper faces of P are simplices. We denote the set of proper faces of P by $\partial P$ and call it the *boundary* of P.

A (geometric) simplicial complex $\Delta$ is a finite family of simplices such that (i) if $F$ is in $\Delta$ and $G$ is a face of $F$, then $G$ is also in $\Delta$, and (ii) for any two elements $F$ and $H$ of $\Delta$, $F \cap H$ is a face of both $F$ and $H$. Note that a polytope $P$ is simplicial if and only if the boundary of $P$ is a simplicial complex. The elements of a simplicial complex are also called *faces* and the *dimension* of a simplicial complex is the maximal dimension of a face. As in the case of polytopes we may define the *f-vector* of $\Delta$, $f_\Delta := (f_{-1}, f_0, \dots, f_{d-1})$, to be the vector such that $f_i$ is the number of faces of dimension $i$. When working with a simplicial complex $\Delta$, one sometimes needs to consider the set of faces of $\Delta$ of dimension at most $i$ for some fixed $i$. This subcomplex of $\Delta$ is called the *$i$-th skeleton* of $\Delta$ and is denoted by $\Delta^{(i)}$. The set of 0-dimensional faces is denoted by $V(\Delta)$ and is called the set of *vertices* of $\Delta$.

The *link* of a face *F* of *Δ*, denoted by link<sub>Δ</sub>(*F*), or short *link*(*F*), is the set of all faces *G* of *Δ*, such that *F* ∩ *G* = ∅ and *G* is contained in a face that contains *F*. It is straightforward (see Ziegler (1995)) that for every face *F* of a polytope *P* the link of *F* in the boundary of *P* is combinatorially isomorphic to the boundary of some polytope. The link of a vertex is sometimes called a *vertex figure*.

From now on $P$ denotes a simplicial polytope and slightly abusing notation, we write $f_P$ for $f_{\partial P}$.
The $f$-polynomial of $P$ is the generating function of the $f$-vector, given by the polynomial $f_P(x) =$
$\sum_{j=0}^{d} f_{j-1}x^j$. Sometimes it is convenient to consider the $h$-polyomial, $h_P(x) := (1-x)^d f_P(\frac{x}{1-x})$. The $h$-vector $(h_0, h_1, \dots, h_d)$ of $P$ is the vector of coefficients of the $h$-polynomial, that is, $h_P(x) = \sum_{i=0}^{d} h_i x^i$. Knowing the $h$-vector is equivalent to knowing the $f$-vector. The Dehn-Sommerville relations (see Klee (1964)) assert that $h_i = h_{d-i}$, and so for a simplicial polytope $P$ the first half of the entries of the $f$-vector $P$ determine the entire $f$-vector of $P$.

The celebrated classification by Stanley (1980) and Billera and Lee (1980) of the $f$-vectors of simplicial polytopes is known as the $g$-theorem and is usually stated in terms of the $g$-vector $(g_0, g_1, \dots, g_{\lfloor \frac{d}{2} \rfloor})$, where $g_0 := h_0 = 1$ and $g_i = h_i - h_{i-1}$ for $1 \le i \le \lfloor \frac{d}{2} \rfloor$. To state this theorem define two operators, denoted by $<^k>$ and $\partial^k$, that act on the set of positive integers and output non-negative integers. For any $n, k > 0$ there exist unique $i > 0$ and $a_k > a_{k-1} > \dots > a_i \ge i > 0$ such that

$$n = \binom{a_k}{k} + \binom{a_{k-1}}{k-1} + \dots + \binom{a_i}{i}. \qquad (1)$$

Using (1) we can define the following two operations:

$$\partial^k(n) := \binom{a_k - 1}{k - 1} + \binom{a_{k-1} - 1}{(k-1) - 1} + \dots + \binom{a_i - 1}{i - 1},$$

$$n^{<k>} := \binom{a_k + 1}{k + 1} + \binom{a_{k-1} + 1}{(k-1) + 1} + \dots + \binom{a_i + 1}{i + 1}.$$

**Theorem 2.1 (g-theorem)** An integer vector $(g_0, g_1, \dots, g_{\lfloor \frac{d}{2} \rfloor})$ is the $g$-vector of a simplicial $d$-polytope if and only if the following holds:

(i) $g_0 = 1$ and $g_k \ge 0$ for $1 \le k \le \lfloor \frac{d}{2} \rfloor$.

(ii) $g_k^{<k>} \ge g_{k+1}$ for $1 \le k \le \lfloor \frac{d}{2} \rfloor - 1$.

Condition (ii) can equivalently be replaced by: $g_k \ge \partial^{k+1} g_{k+1}$ for $1 \le k \le \lfloor \frac{d}{2} \rfloor - 1$. The extremal polytopes which achieve some of the lower bounds in (i) are well studied and understood. This is a part of the generalized lower bound conjecture that was recently settled by Murai and Nevo (2013). On the other hand, not much is known about the polytopes achieving some of the upper bounds, except that if a polytope $P$ is $s$-neighbourly then all inequalities in (ii) for $k \le s - 1$ occur as equalities.

The description of polytopes with $g_k = 0$ for some $k$ is given in terms of triangulations. A triangulation of a polytope $P$ is a simplicial complex $\Sigma$ such that the set of vertices of $\Sigma$ coincides with the set of vertices of $P$ and such that the union of the simplices of $\Sigma$ is $P$. A simplicial polytope $P$ is said to be $r$-stacked if there exists a triangulation $\Sigma$ of $P$ such that $\Sigma^{(d-1-r)} = P^{(d-1-r)}$. The following result was known as the generalized lower bound theorem of McMullen and Walkup (1971).

**Theorem 2.2 (Murai and Nevo (2013))** Let $P$ be a simplicial $d$-polytope and $2 \le k \le \lfloor \frac{d}{2} \rfloor$. The following are equivalent:

(i) $g_k(P) = 0$,

(ii) $P$ is $(k-1)$-stacked.
For a simplicial $d$-polytope $P$ with boundary complex $\Delta$, consider the set of simplices

$$ \Delta(k) := \{ F \subseteq V(\Delta) : |F| = d+1, F^{(k)} \subseteq \Delta^{(k)} \}. $$

Murai and Nevo (2013) showed that if $g_k(P) = 0$, then $\Delta(d-1-k)$ is a triangulation of $P$; it the followed from a combination of results of McMullen (2004) and Bagchi and Datta (2011) that if $g_k(P) = 0$ then $\Delta(d-1-k)$ is a unique $(k-1)$-stacked triangulation of $P$.

The $f$-vector of a simplicial polytope can be expressed in terms of the $f$-vectors of vertex links. To state this result, define the short $h$-vector of $\Delta$ to be the vector $\tilde{h} := (\tilde{h}_0, \tilde{h}_1, \dots, \tilde{h}_{d-1})$, where

$$ \tilde{h}_i = \sum_{v \in V(\Delta)} h_i(\text{link}(v)). \qquad (2) $$

It is a lemma of McMullen (1970) that

$$ \tilde{h}_{j-1} := jh_j + (d+1-j)h_{j-1} \quad \text{for all } 1 \le j \le d. \qquad (3) $$

Similarly, we can define the short $g$-vector $\tilde{g} = (\tilde{g}_0, \tilde{g}_1, \dots, \tilde{g}_{d-1})$ by $\tilde{g}_0 := \tilde{h}_0$ and $\tilde{g}_i := \tilde{h}_i - \tilde{h}_{i-1}$ for $i = 1, 2, \dots, d-1$. We then have

$$ \tilde{g}_i = \sum_{v \in V(\Delta)} g_i(\text{link}(v)). \qquad (4) $$

## 2.2 Convex bodies and the Hausdorff metric

A more general class of convex sets in $\mathbb{R}^d$ that contains all $d$-polytopes is the family of convex bodies. A convex body $K$ in $\mathbb{R}^d$ is a convex compact subset of $\mathbb{R}^d$ with non-empty interior. The typical example of a convex body is the euclidean closed ball. A convex body $K$ is said to be of type $C^k$ if its topological boundary $\partial K$ is locally the graph of a $C^k$-function. Alternatively, $K$ is a convex $C^k$-embedding of the closed ball $B_1(0)$. All our results will hold for bodies of class $C^1$ and we will call them $C^1$-convex bodies. Notice that standard balls fall into the class of $C^1$-convex bodies, while polytopes are not in this class.

For a point $x \in \mathbb{R}^d$ and $A \subset \mathbb{R}^d$ define $d(x, A) := \inf_{a \in A} |x - a|$ to be the distance from $x$ to $A$ in the usual Euclidean metric. Based on this definition of the distance between a point and a set we can define a metric on the space of compact subsets of $\mathbb{R}^d$. Let $A, B$ be two bounded subsets of $\mathbb{R}^d$. Define the Hausdorff distance between $A$ and $B$ by:

$$ \delta^H(A, B) := \max \left\{ \sup_{a \in A} d(a, B), \sup_{b \in B} d(b, A) \right\}. $$

It is easy to verify that $\delta^H$ defines a metric on the space of compact subsets of $\mathbb{R}^d$ that restricts to a metric on the space of convex bodies in $\mathbb{R}^d$.

# 3 Simplices and $C^1$-convex bodies

We will use some technical results about 1-skeleta of polytopes that approximate $C^1$-convex bodies.
<figure><img src="image_2.png" /><figcaption>Fig. 1: The boundary of a simplex that contains $x$ is far from $\partial M$</figcaption></figure>

**Lemma 3.1** Let $M \subseteq \mathbb{R}^d$ be a $C^1$-convex body and let $x$ be a point in the interior of $M$. Let $A$ be the family of all $d$-simplices that contain $x$. Then

$$ \Psi(x) := \inf_{\Gamma \in A} \sup_{z \in \Gamma^{(1)}} d(z, \partial M) > 0. \qquad (5) $$

**Proof Sketch:** Assume without loss of generality that $x = 0$. Consider the set $A'$ of all $d \times (d+1)$ matrices such that each column vector belongs to $M$ and $0$ is a convex combination of columns. This is a closed and bounded subset of the space of $d \times (d+1)$ matrices, hence it is compact with respect to the standard topology. Now consider the map $\varphi: A' \to \mathbb{R}$ that maps a matrix $M$ with column vectors $v_1, \dots, v_{d+1}$ to $\max_{i \neq j} \sup_{\lambda \in [0,1]} d(\lambda v_i + (1-\lambda)v_j, \partial M)$. As the map $\varphi$ is continuous, it attains a minimum in $A'$. This minimum, denote it by $m$, is strictly positive: indeed if we consider the convex hull $P$ of the columns of a matrix $X$ with $\varphi(X) = m$, then $\varphi(X) = 0$ would imply that $P^{(1)} \subseteq \partial M$. This, however, is impossible, since $P$ is not completely contained in $\partial M$ (it contains $0$) and $\partial M$ is $C^1$ (vertices of $P$ would be singularities of $\partial M$).

Furthermore, notice that if $\Gamma$ is a $d$-simplex that contains $0$ and has vertices $v_1, \dots, v_{d+1}$, and if $Y$ is a matrix with columns $v_1, v_2, \dots, v_{d+1}$, then $Y \in A'$ and $\varphi(Y) = \sup_{z \in \Gamma^{(1)}} d(z, \partial M)$. Thus by the previous paragraph we obtain that $\sup_{z \in \Gamma^{(1)}} d(z, \partial M) \geq \varphi(X) > 0$. It follows the infimum over all the $d$-simplices that contain $0$ is bounded below by $\varphi(X) > 0$ as desired. $\square$

We now note that $\Psi(x)$ restricted to the interior of $M$ is a continuous function: if $x$ and $y$ are close enough then the family of simplices that contain $x$ is close to the family of simplices that contain $y$.

**Corollary 3.2** If $M$ is a $C^1$-convex body and $C$ is a compact subset of the interior of $M$, then

$$ \inf_{x \in C} \Psi(x) > 0. \qquad (6) $$

For $\epsilon > 0$ let

$$ M_{\epsilon} := \{x \in M \mid \inf_{z \in \partial M} |z - x| \geq \epsilon\}. $$

It is easy to show that $M_{\epsilon}$ is a convex body contained in the interior of $M$ whenever $\epsilon$ is sufficiently small. We use these bodies to show that if $P$ is sufficiently close to a $C^1$-convex body $M$, then $P^{(1)}$ is close to $\partial M$.
<figure><img src="image_3.png" /><figcaption>Fig. 2: We can slightly shrink M and get a body contained in P</figcaption></figure>

**Lemma 3.3** Let $M \subseteq \mathbb{R}^d$ be a $C^1$-convex body. For every $\epsilon > 0$ there is a $\delta > 0$ such that if $P \subseteq M$ is a polytope with $\delta^H(P, M) < \delta$ then

$$ \sup_{x \in P^{(1)}} d(x, \partial M) \le \epsilon. \qquad (7) $$

**Proof:** Assume without loss of generality that 0 is in the interior of M. It follows from the definitions that if $\delta^H(M, P) < \epsilon$ then $M_\epsilon \subseteq P$. Also, each y in the interior of M belongs to $M_t$ for every sufficiently small t. Now consider the map $h : [0, 1] \to [0, 1]$ defined by $t \mapsto \sup\{x | xM \subseteq M_t\}$. It is easy to see that h is continuous, decreasing, and $h(0) = 1$. By definition of h, we have that if $\delta^H(M, P) < t$ then $h(t)M \subseteq P$. Now take a $t < 1$ such that $|x - tx| < \epsilon$ for every $x \in \partial M$; such a t exists by our assumption that M is bounded. Letting $\delta = h^{-1}(t)$ yields the result: indeed if $\delta^H(P, M) < \delta$ then $tM \subseteq P \subseteq M$, and so $P^{(1)} \subseteq M \setminus \int(tM)$. Let $x \in P^{(1)}$ and let $f(x)$ be the intersection of the ray from 0 to x with $\partial M$. Then x lies in the segment $[tf(x), f(x)]$, hence $|x - f(x)| < |f(x) - tf(x)| < \epsilon$, and the supremum over the $x \in P^{(1)}$ is at most $\epsilon$. $\square$

The following lemma provides a relationship between simplices whose 1-skeleton is contained in the boundary of a polytope and good approximations of a convex body.

**Lemma 3.4** Let M be a $C^1$-convex body. For every $\epsilon > 0$ there exists $\delta > 0$ such that if P is a polytope with $\delta^H(P, M) \le \delta$ and $\Gamma \subseteq M$ is a simplex with $\Gamma^{(1)} \subseteq P^{(1)}$, then $\Gamma \subset M \setminus M_\epsilon$.

**Proof:** As $M_\epsilon$ is a compact set contained in the interior of M, there is $\epsilon' > 0$ such that if $\Sigma$ is a $d$-simplex that intersects $M_\epsilon$ then $\sup_{x \in \Sigma^{(1)}} d(x, \partial M) \ge \inf_{x \in M_\epsilon} \Psi(x) > \epsilon'$. On the other hand, there is $\delta > 0$, such that if $\delta^H(P, M) < \delta$, then $\sup_{x \in P^{(1)}} d(x, \partial M) \le \epsilon'$. It follows that $\sup_{x \in \Gamma^{(1)}} d(x, \partial M) \le \epsilon'$, which implies that $\Gamma$ does not intersect $M_\epsilon$. $\square$

# 4 Short $g$-vectors and local properties of good approximations

Here we prove part (i) of Kalai's conjecture for the case when $2k < d$. In particular, we show that if P is close enough to M and $g_k(P)$ is small, then there is a simplex $\Gamma$ whose 1-skeleton is contained in the 1-skeleton of P and such that $\Gamma$ intersects $M_\epsilon$ for a certain $\epsilon$ that depends only on $g_k$. This contradicts Lemma 3.4.
**Lemma 4.1** Let $g \ge 0$ be an integer and let $d, k$ be positive integers with $2k < d$. There exists a constant $C := C(g, d, k)$ such that if $P$ is a simplicial $d$-polytope with $g_k(P) \le g$ then all but $C$ vertices of $P$ have $(k-1)$-stacked links.

**Proof:** We mimic a trick of Swartz (2008). We have:

$$ 
\begin{align*}
\tilde{g}_k &= \tilde{h}_k - \tilde{h}_{k-1} \\
&= ((k+1)h_{k+1} + (d-k)h_k) - (kh_k + (d+1-k)h_{k-1}) \\
&= (k+1)g_{k+1} + (d+1-k)g_k \\
&\le (k+1)g_k^{<k>} + (d+1-k)g_k \\
&\le (k+1)g_k^{<k>} + (d+1-k)g.
\end{align*}
$$

Here the second step follows from equation (3), the fourth step is a consequence of the $g$-theorem and the last step follows from the monotonicity of the operator $^{<k>}$.

Define $C(g, d, k) := (k+1)g^{<k>} + (d+1-k)g$. Note that (8) implies that $C \ge \sum_{v \in V(P)} g_k(\text{link}(v))$. Since all vertex links of a simplicial polytope are isomorphic to boundaries of polytopes, the $g$-theorem implies that all the summands in this sum are nonnegative. Hence at most $C$ of them are positive. Then by Theorem 2.2 almost all links are $(k-1)$-stacked, as desired. $\square$

From now on $P$ is a simplicial polytope with the boundary complex of $P$ denoted by $\Delta$. If the number of vertices of $P$ is large and $g_k$ is small, we use the generalized lower bound theorem to triangulate many links and produce a large family of simplices whose 1-skeleton is contained in the 1-skeleton of $P$. For a vertex $v$ of $P$, we let $\Delta_v := \text{link}(v)$ to make the notation cleaner. The previous lemma along with Theorem 2.2 implies that if $g_k(P) < c$, then for most vertices of $P$, $\Delta_v(d-2-k)$ gives a triangulation of $\Delta_v$ (that is, $\Delta_v(d-2-k)$ is a simplicial complex homeomorphic to a ball, whose boundary is $\Delta_v$.

Let $V_k(P)$ be the set of vertices $v$ of $P$ such that $g_k(\Delta_v) = 0$. Now consider the following collection (i)

$$ \Delta'(k) = \{ \Gamma \mid \Gamma \text{ is a face of } v \ast \Delta_v(d-2-k) \text{ for } v \in V_k(P) \}. \quad (8) $$

Here $v \ast L$ denotes the cone over a $(d-1)$-dimensional simplicial complex $L$ with apex $v$. Denote by $|\Delta'(k)|$ the union of all the simplices in $\Delta'(k)$. Then $|\Delta'(k)|$ is a subset of $P$. We will show that if $P$ has enough vertices, $g_k(P) < g$, and $P$ is contained in a $C^1$-convex body $M$, then there is a compact subset $C$ contained in the interior of $M$ that depends only on $g$ and $M$, and such that $|\Delta'(k)| \cap C \ne \emptyset$.

For this we need a “separation theorem” for a finite set of points inside a $C^1$-convex body. For an affine hyperplane $H$ and a normal vector direction, let $H^+$ be the strictly positive side of $H$ and $H^-$ the weakly negative side of $H$. We say that a hyperplane is generic with respect to a finite set of points $B$ if it does not contain the affine span of any subset of $B$.

**Theorem 4.2** Let $M$ be a $C^1$-convex body and let $c > 0$ be a positive integer. There exists $\epsilon > 0$ such that for every $A \subseteq M$ with $|A| < c$ and every finite set of points $B$, there is a hyperplane $H$ generic with respect to $A \cup B$, such that $A \subseteq H^+$ and

$$ \sup_{x \in \partial M \cap H^{-}} d(x, M \cap H) \ge \epsilon. \quad (9) $$
<figure><img src="image_4.png" /><figcaption>**Fig. 3:** Any set of $k$ points is far away from some piece of the boundary</figcaption></figure>

**Proof:** Let $\mathcal{P}$ be the family of polytopes that have at most $c$ vertices and are contained in $M$. We claim that there exists $\epsilon > 0$ such that $\delta^H(P, M) > 2\epsilon$ for all $P \in \mathcal{P}$. Consider the set $\mathcal{A}(M, c)$ of all $n \times c$ matrices all of whose column vectors lie in $M$. The set $\mathcal{A}(M, c)$ is compact. Let $\text{Conv}$ be the map from $\mathcal{A}(M, c)$ to the space of bounded subsets of $\mathbb{R}^d$ that maps $X$ to the convex hull of the column vectors of $X$. This map is continuous, so the map $\varphi : \mathcal{A}(M, c) \to \mathbb{R}$ given by $\varphi(X) = \sup_{x \in \partial M} d(x, \text{Conv}(X))$ is continuous as well, and by compactness it achieves a minimum value $m$. Let $X$ be such that $f(X) = m$. This value $m$ is not $0$ since $\partial M$ is not contained in $\text{Conv}(X)$. Let $\epsilon = \frac{m}{4}$.

We claim that $\epsilon$ a a suitable number. Let $A$ be a set of at most $c$ points of $M$ and let $Y \in \mathcal{A}(M, c)$ be such that $\text{Conv}(Y)$ is the convex hull of the points of $A$. There exists a point $x \in \partial M$ and a point $y \in \text{Conv}(Y)$ such that $|x - z| \ge |x - y| \ge 2\epsilon$ for every $z \in \text{Conv}(Y)$. Let $\tilde{H}$ an affine hyperplane orthogonal to the line between $x$ and $y$ that passes through $\frac{x+y}{2}$. Perturb slightly the normal vector of this affine hyperplane to obtain a generic hyperplane $H$ that passes through $\frac{x+y}{2}$. If the perturbation is small enough then $H$ is a suitable hyperplane.

$\square$

We now use Theorem 4.2 to find a 'big' region of $M$ that only contains vertices of $V_k(P)$ and study properties of $\Delta'(k)$ restricted to the vertices contained in this region. More precisely we have the following result.

**Theorem 4.3** Let $M$ be a $C^1$-convex body in $\mathbb{R}^d$ and let $g > 0$ be an integer. There exists $\epsilon > 0$ such that for every simplicial polytope $P \subset M$ with $g_k(P) \le g$, there exists a hyperplane satisfying the inequality $\sup_{x \in \partial M \cap H^{-}} d(x, M \cap H) \ge \epsilon$ and such that $H \cap P = H \cap |\Delta'(k)|$.

**Proof:** Let $P \subset M$ be a simplicial polytope such that $g_k(P) \le g$ and let $c := C(g, d, k)$. Let $\epsilon$ be the real number given by Theorem 4.2 with the constant $c$ and let $H$ be a hyperplane obtained from Theorem 4.2 when $A = V(P) - V_k(P)$ and $B = V(P)$. Since $|\Delta'(k)| \subseteq P$ it suffices to show that $P \cap H \subseteq |\Delta'(k)| \cap H$. Since $H$ is generic it contains none of the faces of $P$ nor faces of any of the simplices of $\Delta'(k)$. Now pick a generic point $x$ in $P \cap H$, that is, a point that is not contained in a face of dimension at most $d-1$. Then pick a generic line $\ell$ that passes through $x$ and is contained in $H$. By generic we mean that $\ell$ intersects no $d$-simplex of $\Delta'(k)$ of dimension at most $d-2$.

<footnote>(i) It can be shown using results of Bagchi and Datta (2011), that $\Delta'(k)$ is a simplicial complex, but this is not necessary in the following arguments.</footnote>
<figure><img src="image_5.png" /><figcaption>Fig. 4: Take $H$ far from the complement of $V_k(P)$</figcaption></figure>

We claim that $|\Delta'(k)| \cap \ell = P \cap \ell$. To establish this, note that $\ell \cap P$ is a closed line segment and admits a continuous parametrization $\gamma : [0, 1] \to \ell \cap P$. Assume that there is $x \in P \cap H$ that is not in $|\Delta'(k)|$. Let $s = \inf\{t \in [0, 1] \mid \gamma(t) \notin |\Delta'(k)|\}$. The set $|\Delta'(k)|$ is a compact set, and so $\gamma(s) \in |\Delta'(k)|$ as long as $\ell \cap |\Delta'(k)|$ is not empty. The set $P \cap H$ is not empty, hence $\gamma(0)$ is in a facet of $P$ and this facet has one vertex in $V_k(P)$, as it must have a vertex $v$ in $H^-$. This facet belongs to a simplex of $v \ast \Delta_v(d-k)$, and so $\gamma(s) \in |\Delta'(k)|$. Now $\gamma(s)$ is in $\ell$ so it belongs to the (relative) interior of a $d$- or $(d-1)$-simplex of $\Delta'(k)$. The former is not possible because then $x$ would be in the interior of $|\Delta'(k)|$, hence it would be in the interior of $|\Delta'(k)| \cap \ell$. In the latter case we will show that $\gamma(s)$ is in the interior of $|\Delta'(k)|$ unless it is in $\Delta$. The reason for this is the following: let $\Gamma$ be a $(d-1)$-simplex of $\Delta'(k)$ that contains $\gamma(s)$. Then $\Gamma$ contains a vertex $v \in H^-$ such that $\Gamma$ is in $v \ast \Delta_v(d-2-k)$. Thus $x \in v \ast \Sigma = \Gamma$ where $\Sigma$ is a ridge of $\Delta_v(d-r)$. The ridge $\Sigma$ is contained in exactly two facets $F_1, F_2$ of $\Delta_v(d-2-k)$ unless it is on the boundary of $P$. In the first case we obtain that $\gamma(s)$ is in the interior of $v \ast F_1 \cup v \ast F_2$, thus it is also in the interior of $|\Delta'(k)|$. In the second case $\gamma(s) \in \Delta$ hence $s=1$, which is impossible since $s$ is an infimum. It follows that $\ell \cap P \subseteq \ell \cap |\Delta'(k)|$, so in particular $x \in |\Delta'(k)| \cap H$. Now the set of generic points of $P \cap H$ is dense in $P \cap H$ and is contained in $|\Delta'(k)| \cap H$. Thus taking closure of the set of generic points yields the result. $\square$

We are ready to prove the main result of the paper.

**Theorem 4.4 (Adiprasito and Samper (2014))** Part (i) of Conjecture 1.1 holds whenever $2k < d$.

**Proof:** Assume that $\{P_n\}_{n=1}^\infty$ is a sequence of polytopes that converges to $M$ and such that $g_k(P_n) \le g$ for all $n$. Let $\epsilon$ be given by Theorem 4.3. If $n$ is sufficiently large then $P_n$ contains $M_\epsilon$ in its interior. For any such $n$ let $H_n$ be a hyperplane given by Theorem 4.3. Notice that there is at least one $x \in H_n \cap M_\epsilon \subseteq H_n \cap P_n = H_n \cap |\Delta'(k)(P_n)|$. It follows that there is a simplex $\Gamma$ in $|\Delta'(k)(P_n)|$ that intersects $M_\epsilon$. This however contradicts Lemma 3.4, as $\Gamma^{(1)} \subseteq P^{(1)}$. $\square$

# 5 The case $2k = d$

If $k$ equals $\frac{d}{2}$, then our method of the proof for Theorem 4.4 breaks down: the $k$-th entry of the short $\tilde{g}$-vector of any $2k$-polytope equals 0. Nevertheless, the theorem holds for $k = \frac{d}{2}$:

**Theorem 5.1 (Adiprasito and Samper (2014))** Part (i) of Conjecture 1.1 holds whenever $2k \le d$.
The main tool is an extension of the theorem of Murai–Nevo: we provide several quantitative forms of their generalized lower bound theorem, among them the following result.

**Theorem 5.2 (Adiprasito and Samper (2014))** Let $M$ denote an arbitrary $C^1$-convex body in $\mathbb{R}^{2k}$, and let $c$ denote any non-negative integer. Then, there are $\epsilon, \delta > 0$ such that for every polytope $P$ with $(1-\epsilon)M \subset P \subset M$ and $g_k(P) \le c$, there exists a hyperplane $H$ such that

(i) $\sup_{x \in \partial M \cap H^{-}} d(x, M \cap H) \ge \delta > 0,$

(ii) there is a simplicial complex $\Gamma$ such that $P \cap H^{-} = \Gamma \cap H^{-}$, and

(iii) $\Gamma^{(d-1-k)} \cap H^{-} = P^{(d-1-k)} \cap H^{-}$.

One can derive Theorem 5.1 from Theorem 5.2 in a way analogous to how we derived Theorem 4.4 from Lemma 3.1. However, the vanishing of $\tilde{g}_k$ makes it unfeasible to construct the complex $\Gamma$ by constructing it in every link. Instead, we use a careful generalization of the methods of Murai and Nevo (2013): As a candidate for $\Gamma$, we still consider the complex $\Delta(k) = \{F : F^{(k)} \subset \Delta^{(k)}\}$, where $\Delta = \partial P$. This complex clearly satisfies property (iii) (regardless of the hyperplane $H$ chosen). Proving (i) and (ii), however, is considerably harder; to prove these claims, we consider $(2k-1)$-dimensional disks $D$ in the boundary $\partial P$ of $P$ cut out by halfspaces $H^+$. Associated to this pair $(\partial P, D)$ is a (Cohen–Macaulay) Stanley–Reisner module $\mathfrak{M}(\partial P, D) := I_D/I_{\partial P}$. We then use the crystallization principle of Green (1998) to show that, for a suitable choice of $H$ satisfying (i), the module $\mathfrak{M}(\Gamma, \Gamma|_D)$ (where $\Gamma|_D := \{F : F^{(k)} \subset D^{(k)}\}$) is Cohen-Macaulay of dimension $2k$, thereby establishing also (ii).

## Acknowledgements

We thank Isabella Novik and Ed Swartz for many helpful discussions and suggestions. We also want to thank Federico Castillo, Steven Klee and Isabella Novik for proofreading earlier versions of this manuscript.

## References

K. A. Adiprasito and J. A. Samper. The quantitative lower bound theorem. in preparation, June 2014.

B. Bagchi and B. Datta. On stellated spheres, shellable balls, lower bounds and a combinatorial criterion for tightness. *ArXiv e-prints*, Feb. 2011.

L. J. Billera and C. W. Lee. Sufficiency of McMullen's conditions for $f$-vectors of simplicial polytopes. *Bull. Amer. Math. Soc. (N.S.)*, 2(1):181–185, 1980. ISSN 0273-0979. doi: 10.1090/S0273-0979-1980-14712-6. URL http://dx.doi.org/10.1090/S0273-0979-1980-14712-6.

M. L. Green. Generic initial ideals. In J. Elias, J. Giral, R. Miró-Roig, and S. Zarzuela, editors, *Six Lectures on Commutative Algebra*, Progress in Mathematics, pages 119–186. Birkhäuser Basel, 1998. ISBN 978-3-0346-0328-7. doi: 10.1007/978-3-0346-0329-4_2. URL http://dx.doi.org/10.1007/978-3-0346-0329-4_2.
G. Kalai. Some aspects of the combinatorial theory of convex polytopes. In *Polytopes: abstract, convex and computational* (Scarborough, ON, 1993), volume 440 of *NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci.*, pages 205–229. Kluwer Acad. Publ., Dordrecht, 1994.

V. Klee. A combinatorial analogue of Poincaré's duality theorem. *Canad. J. Math.*, 16:517–531, 1964. ISSN 0008-414X.

P. McMullen. The maximum numbers of faces of a convex polytope. *Mathematika*, 17(02):179–184, 1970.

P. McMullen. The numbers of faces of simplicial polytopes. *Israel J. Math.*, 9:559–570, 1971. ISSN 0021-2172.

P. McMullen. On simple polytopes. *Invent. Math.*, 113(2):419–444, 1993. ISSN 0020-9910. doi: 10.1007/BF01244313. URL http://dx.doi.org/10.1007/BF01244313.

P. McMullen. Triangulations of simplicial polytopes. *Beiträge Algebra Geom.*, 45(1):37–46, 2004. ISSN 0138-4821.

P. McMullen and D. W. Walkup. A generalized lower-bound conjecture for simplicial polytopes. *Mathe-matika*, 18:264–273, 1971. ISSN 0025-5793.

S. Murai and E. Nevo. On the generalized lower bound conjecture for polytopes and spheres. *Acta Math.*, 210(1):185–202, 2013. ISSN 0001-5962. doi: 10.1007/s11511-013-0093-y. URL http://dx.doi.org/10.1007/s11511-013-0093-y.

R. P. Stanley. The number of faces of a simplicial convex polytope. *Adv. in Math.*, 35(3):236–238, 1980. ISSN 0001-8708. doi: 10.1016/0001-8708(80)90050-X. URL http://dx.doi.org/10.1016/0001-8708(80)90050-X.

E. Swartz. Topological finiteness for edge-vertex enumeration. *Adv. Math.*, 219(5):1722–1728, 2008. ISSN 0001-8708. doi: 10.1016/j.aim.2008.07.010. URL http://dx.doi.org/offcampus.lib.washington.edu/10.1016/j.aim.2008.07.010.

G. M. Ziegler. *Lectures on polytopes*, volume 152 of *Graduate Texts in Mathematics*. Springer-Verlag, New York, 1995. ISBN 0-387-94365-X. doi: 10.1007/978-1-4613-8431-1. URL http://dx.doi.org/10.1007/978-1-4613-8431-1.