5
$\begingroup$

Let $P$ be a polytope in $\mathbb{R}^n$. Let $A_ix = b_i$ be the defining equations of its codimension $1$ faces. Is there an algorithm or some kind of criterion to decide if the lattice points inside $P$ and on its boundary have the property that any two are connected by a lattice path through $P$ (and its boundary)? It seems to me that this is a hard problem in general even for small $n$.

In the above, the lattice in question is not mentioned on purpose because I'm really looking for any kind of result. But I will certainly be happy for results concerning $\mathbb{Z}^n$.

Improve this question
$\endgroup$
5
  • $\begingroup$ By "lattice path", do you mean that only one coordinate changes at each step? $\endgroup$
    – Allen Knutson
    Commented Jan 15, 2017 at 22:29
  • $\begingroup$ For the $\mathbb{Z}^n$ a lattice path is indeed one in which only one coordinate changes at each step. For instance take in $\mathbb{R}^2$ the paralelogram with vertices $(0, 0), (5, 0), (20, 10), (15, 10)$. Then $(3, 2), (4, 2), (5, 2), (6, 2), (6, 3), (6, 4)$ is a lattice path connecting $(3, 2)$ with $(6, 4)$. $\endgroup$
    – Alex
    Commented Jan 17, 2017 at 13:11
  • 1
    $\begingroup$ It's reminding me of $\S$3 of [Diaconis-Sturmfels], statweb.stanford.edu/~cgates/PERSI/papers/sturm98.pdf . In their introduction they're looking at more complicated moves, changing 4 coordinates instead of 1. $\endgroup$
    – Allen Knutson
    Commented Jan 22, 2017 at 9:26
  • $\begingroup$ @AllenKnutson Thank you. It is indeed similar to the problem I had in mind. Strictly speaking they work with a different polynomial ring than I am but the idea is the same. Using their notation, I am trying to prove that the fiber of the map $T$ is lattice connected with respect to a (minor) modification of their lattice. Also, their result seems related to some result of Okounkov from his paper "Brunn-Minkowski inequality for multiplicities". $\endgroup$
    – Alex
    Commented Jan 23, 2017 at 16:53
  • $\begingroup$ I guess you can always assume that the lattice is $\mathbb{Z}^n$ by applying a linear transformation? $\endgroup$
    – Noah Stephens-Davidowitz
    Commented May 16, 2017 at 0:01

0

Reset to default

You must log in to answer this question.