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

  • $\begingroup$ Yes, it is convex. $\endgroup$ – F_L Sep 9 '20 at 13:53
  • $\begingroup$ 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). $\endgroup$ – Dmitri Panov Sep 9 '20 at 15:40
  • $\begingroup$ @DmitriPanov: Usually a lattice simplex just means a simplex whose vertices are integral (lattice points). They might be empty or not. $\endgroup$ – Sam Hopkins Sep 9 '20 at 16:01
  • $\begingroup$ 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!$). $\endgroup$ – Sam Hopkins Sep 9 '20 at 16:05
  • 1
    $\begingroup$ Yes, "lattice simplex" means a simplex with integer vertices, that does not contain integer points apart from the vertices. $\endgroup$ – 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 $<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.

  • $\begingroup$ ah, sorry, I misread the definition of $P''$ $\endgroup$ – Fedor Petrov Sep 9 '20 at 17:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.