# Separating a lattice simplex from a lattice polytope

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$$.

• Yes, it is convex. – F_L Sep 9 '20 at 13:53
• Just to double check, a "lattice simplex" means a simplex with integer vertices, that doesn't contain integer points apart from the vertices? I.e., you don't assume that its volume is $\frac{1}{n!}$ (otherwise the statement would not hold). – Dmitri Panov Sep 9 '20 at 15:40
• @DmitriPanov: Usually a lattice simplex just means a simplex whose vertices are integral (lattice points). They might be empty or not. – Sam Hopkins Sep 9 '20 at 16:01
• I'm not sure if there's a standard term for simplices unimodularly equivalent to the standard simplex (these would be the ones with volume $1/n!$). – Sam Hopkins Sep 9 '20 at 16:05
• Yes, "lattice simplex" means a simplex with integer vertices, that does not contain integer points apart from the vertices. – F_L Sep 10 '20 at 8:21

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 $$ 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.
• ah, sorry, I misread the definition of $P''$ – Fedor Petrov Sep 9 '20 at 17:47