1

I am studying mathematics of lattices and I came up with a question but I am still unable to answer it.

Given a integer lattice $\mathcal{L}(B) = \sum_{i=1}^nx_ib_i:x_i \in \mathbb{Z}$, and a point $t$ that lies in the space spun by the lattice, is it possible, in polynomial time, to check whether $t$ lies inside the fundamental parallelepiped generated by the lattice?

narger
  • 11

1 Answers1

1

Any vector $v\in\mathrm{span}(b_1,\ldots, b_n)$ is expressible as a unique linear combination of these basis vectors, so there exists unique $x\in\mathbb{R}^n$ such that $Bx=v$, that is solvable in polynomial time, by say Gaussian elimination or matrix inversion, $x=B^{-1}v$. Now we just have to check whether $0\le x_i<1$ for all $i=1,\ldots, n$, to know if $v$ is in the fundamental parallelepiped.

QED
  • 12,644
  • Thank you so much! Can this method be used to "correct" a point in space into the fundamental parallelepiped? – narger Jan 23 '23 at 09:03
  • Of course. Find $x=B^{-1}v$, and take the vector $x'$ with $x_i'=\lfloor x_i\rceil$, where $\lfloor\cdot\rceil$ is the nearest integer function. – QED Jan 23 '23 at 18:20
  • Thank you very much! Simple and clean :) – narger Jan 26 '23 at 08:30