7
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ Yes, it is convex. $\endgroup$
    – Puzzled
    Commented Sep 9, 2020 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$ Commented Sep 9, 2020 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$ Commented Sep 9, 2020 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$ Commented Sep 9, 2020 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$
    – Puzzled
    Commented Sep 10, 2020 at 8:21

1 Answer 1

8
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ ah, sorry, I misread the definition of $P''$ $\endgroup$ Commented Sep 9, 2020 at 17:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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