Lemma 21.8.241C54729DBFD

Proof. (1) Let $P$ be the convex hull of a finite set $S\subset M$, and discard points of $S$ one at a time as long as some point lies in the convex hull of the others; this does not change $P$. If only one point remains, $P$ is that point, it is the only face, and all assertions hold. Otherwise, for a remaining point $s$, lemma 21.2.3(1) gives $x\in N_{\mathbb R}$ with $\langle s,x\rangle <\langle s',x\rangle $ for all $s'$ in the convex hull of $S\setminus \{ s\} $. Every point of $P$ is a convex combination $\lambda s+(1-\lambda )s''$ with $s''$ in that hull, so $\langle \cdot ,x\rangle $ attains its minimum on $P$ only at $s$, and $\{ s\} $ is a vertex. Conversely, let $Q$ be any face, the set where $\langle \cdot ,x'\rangle $ is minimal for some $x'\in N_{\mathbb R}$, and write a point $m\in Q$ as a convex combination of points of $S$: all points with positive coefficient minimize $\langle \cdot ,x'\rangle $, hence lie in $Q$. Thus $Q$ is the convex hull of the points of $S$ it contains. Applied to a vertex $\{ v\} $, this shows $v\in S$. Hence the vertices are exactly the remaining points of $S$, and in particular lattice points. Every face is the convex hull of the vertices it contains, so there are only finitely many faces.

Let $\{ v\} $ be a vertex, the set where some $\langle \cdot ,x\rangle $ is minimal on $P$. Then $v$ is not of the form $(1-t)a+tb$ with $a\neq b$ in $P$ and $0<t<1$: the values $\langle a,x\rangle $ and $\langle b,x\rangle $ are at least $\langle v,x\rangle $, and their weighted mean equals it, so $a$ and $b$ would also be minimum points, that is, $a=b=v$. An edge is the convex hull of the finitely many vertices it contains, which lie on a line, so it is the segment between the two outermost ones; a vertex in the edge is not an interior point of the segment, hence it is an endpoint.

(2) We first show that every boundary point $b$ of $P$ lies in a facet. By lemma 21.2.3(2), $b$ lies in a face $Q$ where some $x\neq 0$ is minimal; this face is proper, since $\langle \cdot ,x\rangle $ is not constant on the full-dimensional set $P$. Suppose that $Q$ has dimension $d<n-1$, and let $c$ be the minimum of $\langle \cdot ,x\rangle $ on $P$. The linear functionals vanishing on the directions of $Q$ form a space of dimension $n-d\geq 2$, which contains $x$; choose $y$ in it, independent of $x$, and put $x_ s=x+sy$. On $Q$ the functional $\langle \cdot ,y\rangle $ is constant, say equal to $c'$, and for each vertex $w\notin Q$ consider the gap $g_ w(s)=\langle w,x_ s\rangle -(c+sc')=(\langle w,x\rangle -c)+s(\langle w,y\rangle -c')$, which is positive at $s=0$. Some vertex $w\notin Q$ has $\langle w,y\rangle \neq c'$, since otherwise $y$ would be constant on $P$ and hence zero; replacing $y$ by $-y$ if necessary, we may assume that $\langle w,y\rangle <c'$ for some such $w$. Let $s_*>0$ be the first value of $s>0$ at which some gap vanishes. Then $x_{s_*}\neq 0$ by independence, all vertices of $Q$ and at least one vertex $w\notin Q$ minimize $\langle \cdot ,x_{s_*}\rangle $ on the vertices, and hence, by (1), on $P$. The new face contains $Q$ and $w$, and $w$ does not lie in the affine span of $Q$, because $\langle \cdot ,x\rangle $ equals $c$ on that span and is larger at $w$. So the dimension of the face has increased, and after finitely many steps we reach a facet containing $b$.

A facet $\rho $ contains $n$ affinely independent vertices, which are lattice points by (1). The linear functionals vanishing on the differences of these points form a line, which is defined by linear equations with integral coefficients in the coordinates of bases of $M$ and $N$; Gaussian elimination over $\mathbb Q$ produces a nonzero rational solution, and clearing denominators gives a nonzero vector of $N$ on the line. Since $\rho $ is a face, some $x\neq 0$ attains its minimum on $P$ exactly on $\rho $; this $x$ lies on the line, and we let $u_\rho $ be the primitive vector of $N$ that is a positive multiple of $x$, which exists and is unique by the observation following definition 21.8.1. Then $a_\rho =-\langle v,u_\rho \rangle $, for any vertex $v\in \rho $, is an integer, $\ell _\rho \geq 0$ on $P$, and $\rho =\{ m\in P:\ell _\rho (m)=0\} $.

Next we show that $P$ is the intersection of the half-spaces $\{ \ell _\rho \geq 0\} $. Let $q\notin P$ and let $p$ be an interior point of $P$. The set of $s\in [0,1]$ with $p+s(q-p)\in P$ is an interval $[0,s_0]$ with $s_0<1$, and $b=p+s_0(q-p)$ is a boundary point of $P$, hence lies in some facet $\rho $. The affine function $s\mapsto \ell _\rho (p+s(q-p))$ is positive at $s=0$, because the nonconstant affine function $\ell _\rho $, which is nonnegative on $P$, cannot attain its minimum at the interior point $p$. It vanishes at $s_0<1$, so $\ell _\rho (q)<0$.

For irredundancy, let $b$ be a point of the relative interior of a facet $\rho $, which exists by lemma 21.2.3(4). If $\ell _{\rho '}(b)=0$ for another facet $\rho '$, then $\ell _{\rho '}$, which is nonnegative on $\rho $, vanishes on $\rho $ by the observation preceding the lemma. Then $u_{\rho '}$ is constant on $\rho $, whose differences span a hyperplane, so $u_{\rho '}$ lies on the line of $u_\rho $, and $u_{\rho '}=\pm u_\rho $, because both vectors are primitive. If $u_{\rho '}=-u_\rho $, then $\ell _{\rho '}=-\ell _\rho $, since both vanish on $\rho $; as both are nonnegative on $P$, $\ell _\rho $ would vanish on $P$, which is impossible at an interior point. Hence $\ell _{\rho '}=\ell _\rho $ and $\rho '=\rho $. Thus all other facet functions are positive at $b$, and a point near $b$ on the side where $\ell _\rho <0$ violates only the inequality of $\rho $.

(3) If $m\in P$ and $v\in \rho $, then $\langle m-v,u_\rho \rangle =\ell _\rho (m)\geq 0$; hence $\operatorname {cone}(P-v)\subset C_ v$. Conversely, if $y\in C_ v$, then $v+sy\in P$ for all small $s>0$, because the inequalities of the facets containing $v$ hold along this half-line and the finitely many other facet functions are positive at $v$; hence $y\in \operatorname {cone}(P-v)$. The cone $C_ v$ contains no line: if $y\neq 0$ and $\pm y\in C_ v$, then $v\pm sy\in P$ for small $s>0$, and $v$ would be the midpoint of two points of $P$, which is impossible for a vertex. Let $u$ be the sum of the normals $u_\rho $ of the facets containing $v$. If $y\in C_ v$ and $\langle y,u\rangle =0$, then $\langle y,u_\rho \rangle =0$ for all these facets, so $-y\in C_ v$ and $y=0$. Consequently, the slice $\Sigma =\{ y\in C_ v:\langle y,u\rangle =1\} $ is bounded (otherwise a limit of normalized unbounded points would give a nonzero $y\in C_ v$ with $\langle y,u\rangle =0$), and $C_ v=\operatorname {cone}(\Sigma )$.

Call a point $y\in \Sigma $ basic if the normals $u_\rho $ of the facets $\rho \ni v$ with $\langle y,u_\rho \rangle =0$ span a space of dimension $n-1$. Every point $y\in \Sigma $ is a convex combination of basic points. Indeed, if the active normals of $y$, together with $u$, span a space of dimension less than $n$, choose $d\neq 0$ annihilated by all of them. For small $|s|$ the points $y+sd$ remain in $\Sigma $, and since $\Sigma $ is bounded there are maximal $s_\pm >0$ with $y\pm s_\pm d\in \Sigma $. At $y\pm s_\pm d$ some new facet function $\langle \cdot ,u_{\rho '}\rangle $ vanishes, and $\langle d,u_{\rho '}\rangle \neq 0$, so $u_{\rho '}$ is not in the span of the previous active normals and $u$. Thus $y$ is a convex combination of two points with a larger span of active normals and $u$. Induction on the codimension of this span therefore proves the claim, because a point $y\in \Sigma $ whose active normals together with $u$ span $N_{\mathbb R}$ is basic: its active normals annihilate $y\neq 0$, so they span a space of dimension at most $n-1$, and at least $n-1$, since adding $u$ raises the dimension by at most one.

Next, $y\in \Sigma $ is basic if and only if $\mathbb R_{\geq 0}y$ is an extreme ray. If $y$ is basic, its active normals annihilate exactly the line $\mathbb Ry$; if $y=y_1+y_2$ with $y_1,y_2\in C_ v$, then for each active normal both pairings $\langle y_ k,u_\rho \rangle $ are nonnegative with sum zero, hence zero, so $y_1,y_2\in \mathbb Ry\cap C_ v=\mathbb R_{\geq 0}y$. Conversely, if $\mathbb R_{\geq 0}y$ is extreme, write $y$ as a convex combination of basic points; extremality forces each of them to lie on the ray, hence to equal $y$. Therefore $C_ v$ is generated by its extreme rays.

It remains to identify the extreme rays with the edges at $v$. If $y\in \Sigma $ is basic, the set $\{ m\in P:\ell _\rho (m)=0\text{ for the active facets of }y\} $ is a face, namely the set where the sum of the corresponding functionals $\langle \cdot ,u_\rho \rangle $ is minimal; it contains $v+sy$ for small $s>0$ and is contained in $v+(C_ v\cap (\mathbb Ry))=v+\mathbb R_{\geq 0}y$. Hence it is an edge at $v$ with direction $y$. Conversely, let $E$ be an edge at $v$ with direction $y$, so $y\in C_ v$. If $y=y_1+y_2$ with $y_1,y_2\in C_ v$, then for small $s>0$ the point $v+sy\in E$ is the midpoint of $v+2sy_1$ and $v+2sy_2$, which lie in $P$. Since $E$ is the set where some linear functional is minimal on $P$, both points lie in $E\subset v+\mathbb R_{\geq 0}y$, and so $y_1,y_2\in \mathbb R_{\geq 0}y$. Thus the ray of $y$ is extreme.

(4) Let $P$ be smooth and $v$ a vertex. By (3), $C_ v=\operatorname {cone}(e_1,\ldots ,e_ n)$. Let $e_1^*,\ldots ,e_ n^*\in N$ be the dual basis, so that $C_ v=\{ y:\langle y,e_ i^*\rangle \geq 0\text{ for all }i\} $. If $\rho $ is a facet containing $v$, then $u_\rho \geq 0$ on $C_ v$, so $u_\rho =\sum _ ic_ ie_ i^*$ with $c_ i=\langle e_ i,u_\rho \rangle \geq 0$. The set $\rho -v$ lies in $C_ v\cap u_\rho ^\perp =\operatorname {cone}\{ e_ i:c_ i=0\} $ and spans a space of dimension $n-1$, so exactly one coefficient $c_ i$ is positive. Since $u_\rho $ and $e_ i^*$ are primitive, $u_\rho =e_ i^*$. Distinct facets have distinct normals, because a facet is the set where its normal is minimal; so at most $n$ facets contain $v$. If some $e_ i^*$ were not the normal of a facet through $v$, the vector $-e_ i$ would satisfy all the inequalities defining $C_ v$, although $-e_ i\notin \operatorname {cone}(e_1,\ldots ,e_ n)$. Hence exactly $n$ facets contain $v$, and numbering them suitably, $u_ i=e_ i^*$. For $m\in P$ this gives $m-v=\sum _ i\langle m-v,u_ i\rangle e_ i=\sum _ i\ell _ i(m)e_ i$, because $\ell _ i(v)=0$. Finally, the edge in direction $e_ i$ is a segment $[v,v']$ with $v'$ a lattice point, so $v'-v=ke_ i$ for a positive integer $k$, and $v+e_ i\in [v,v']\subset P$. In dimension zero there are no facets and no edges, and the assertions are empty. $\square$