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

  • $\begingroup$ By "lattice path", do you mean that only one coordinate changes at each step? $\endgroup$ 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
    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$ 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
    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$ May 16, 2017 at 0:01


Your Answer

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