Say we're given a parallelepiped defined by the vectors $\mathbf{x}_1,\dots,\mathbf{x}_k$ with integer entries. Is there any way to quickly determine whether it strictly contains an integer vector and if so find it?

One could of course brute force this, but if the vectors $\mathbf{x}_i$ contain $n$ bits, then this takes time that is exponential in $n$. Is there a polynomial time algorithm?

  • 1
    $\begingroup$ I think that it is enough to check $$| \det (\mathbf{x}_1, \dots , \mathbf{x}_k) | >1$$ which has polynomial time. $\endgroup$ – Crostul Jun 4 '18 at 16:45
  • $\begingroup$ What does 'strictly' mean here? You're ok with the point lying on the boundary (but not the vertices, obviously)? $\endgroup$ – peter a g Jun 4 '18 at 16:52
  • $\begingroup$ @peterag Yes, I just want to remove the vertices from consideration, which are obviously vectors with integer entries. $\endgroup$ – Sebastian Oberhoff Jun 4 '18 at 16:54
  • $\begingroup$ @Crostul What if the $\mathbf{x}_i$ don't span the entire space? $\endgroup$ – Sebastian Oberhoff Jun 4 '18 at 16:56
  • $\begingroup$ @Crostul The $2\times 1$ recatangle spanned by $\mathbf x_1=(2,0)$, $\mathbf x_2=(0,1)$ has no lattice point in its interior, but area (=det) $>1$. One would have to determine the number of interior points with a generalization of Pieck's formula - which is not that trivial in general. But due to the regular structure of parallelepipeds, it suffices to recursively count along the faces with appropriate weights. Unfortunately, this seems to take us back to exponential timing $\endgroup$ – Hagen von Eitzen Jun 4 '18 at 18:09

Your Answer

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

Browse other questions tagged or ask your own question.