# Verify that a point is inside a lattice

I am wondering if there's a polynomial time algorithm that, given a lattice $$\Lambda$$ with basis $$\mathbf{B}$$ and a point $$x$$ in space, it tells you whether $$x$$ is in $$\Lambda$$ or not!

If you compute a base of a the dual lattice, and then check that the inner product of the point and the vector if this base are all integers: To compute this base it's $$\mathbf{B}(\mathbf{B}^{T}\mathbf{B})^{-1}$$:

https://cseweb.ucsd.edu/classes/wi12/cse206A-a/LecDual.pdf

• But if the lattice is full-rank, no vector will be perpendicular to all the basis vectors... Maybe do you mean to check if the inner products are integral? – Hilder Vitor Lima Pereira Aug 22 at 21:10
• Yes you are right – Ievgeni Aug 22 at 21:40
• Can one simply check if the solution $\alpha$ to the system $$\mathbf{B}\cdot\alpha^\top = [\mathbf{b}_1,\dots, \mathbf{b}_k]\cdot (\alpha_1,\dots,\alpha_k)^\top=\sum_{i=1}^k \alpha_i \mathbf{b}_i=\mathbf{x}$$ lies in $\mathbb{Z}^k$, i.e. if $\alpha_i\in\mathbb{Z}$ for all $i$? – asd Aug 24 at 7:56
• How do you do this? remember $\mathbb{Z}$ is not a field. – Ievgeni Aug 24 at 12:34
• you solve over $\mathbb{R}$ and check if the solution you obtain is in $\mathbb{Z}$. – asd Aug 24 at 13:07

There's a relatively simple one by using Hermite Normal Form computations. Essentially, if $$\mathbf{B} = [b_1,\dots, b_k]$$, then you check if: $$\mathsf{HNF}([b_1,\dots,b_k]) = \mathsf{HNF}([b_1,\dots,b_k, x])$$ This generalizes to the case of checking if a lattice $$\mathcal{L}(A)$$ is a sub-lattice of $$\mathcal{L}(B)$$ --- just check if $$\mathsf{HNF}(B) = \mathsf{HNF}(B\cup A)$$, where $$B \cup A$$ is the "union" of all the basis vectors.

The HNF can be used to solve a variety of "algebraic" problems on lattices, see for example section 4 of these notes. In general "algebraic" problems on lattices are easy (usually via the HNF), while "geometric" ones are hard. Ajtai has actually written a paper formulating this via an explicit conjecture (see this paper, which is an extension of his initial conjecture).