Separating a lattice simplex from a lattice polytope

Question

Let $P\subset\mathbb{R}^n$ be a convex lattice polytope.

Do there always exist a lattice simplex $\Delta\subset P$ and an affine hyperplane $H\subset\mathbb{R}^n$ separating $\Delta$ from the convex hull of the integer points of $P\setminus \Delta$?

This is equivalent to say that there exist a degree one polynomial $h:\mathbb{R}^n\rightarrow\mathbb{R}$ that is positive on all the integer points of $\Delta$ and negative on all the integer points of $P\setminus \Delta$.

Answer 1

This is possible and here is how to do this. We will use an inductive argument, assume that the statement holds for polytops of dimension $<n$ and prove it for dimension $n$.

Take any vertex $v$ of the $n$ dimensional polytop $P$ and denote by $v_1,\ldots, v_m$ all the end-points of all the edges of $P$ starting at $v$. Let $P'$ be the convex hull of $v,v_1,\ldots, v_m$. Let $P''$ be the convex hull of all the integer points in $P'$ except $v$. Clearly, $P''$ doesn't contain $v$.

Now, take any face of $P''$ that is "visible from $v$", i.e. you can connect it with $v$ by a straight segment that doesn't intersect $P''$ in its interior point (if $P''$ is degenerate and has dimension $n-1$, we take the whole $P''$ as such a face). Denote by $H$ the hyperplane that contains this face. It follows from the construction, that $H$ intersects only whose edges of $P$ that are adjacent to $v$.

Now let's cut $P$ along $H$ and take the part that contains $v$, and call it $Q$. Denote by $F$ the face of $Q$ that lies in $H$. All its vertices lie on the edges of $P$ adjacent to $v$. It is easy to see that $Q$ has a structure of a cone over $F$ with vertex $v$. By construction, integer points in $Q$ is the union of those in $F$ with $v$. Next, apply to $F$ the inductive step and cut a simplex out of it by a certain hyperplane $H'$ (of dimension $n-2$) contained in $H$. To finish, rotate a tiny bit $H$ around $H'$. This is the hyperplane we were looking for.