1
$\begingroup$

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!

$\endgroup$
3
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ 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? $\endgroup$ – Hilder Vitor Lima Pereira Aug 22 at 21:10
  • $\begingroup$ Yes you are right $\endgroup$ – Ievgeni Aug 22 at 21:40
  • $\begingroup$ 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$? $\endgroup$ – asd Aug 24 at 7:56
  • $\begingroup$ How do you do this? remember $\mathbb{Z}$ is not a field. $\endgroup$ – Ievgeni Aug 24 at 12:34
  • $\begingroup$ you solve over $\mathbb{R}$ and check if the solution you obtain is in $\mathbb{Z}$. $\endgroup$ – asd Aug 24 at 13:07
1
$\begingroup$

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

| improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.