2
$\begingroup$

Given two lattices $L_1$ and $L_2$ represented by bases $B_1$ and $B_2$, is there an efficient algorithm to compute $L_1\cap L_2$?

I can show, I think, that if $\gcd(\det(B_1),\det(B_2))=1$, then $B_1adj(B_1)B_2$ generates $L_1\cap L_2$, but I'm interested in lattices whose volumes have greater GCDs.

A follow-up question is if there is an efficient algorithm to represent the intersection of $L_1$ and $L_2+v$ for some $v\notin L_1,L_2$.

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
2
$\begingroup$

The answer to both questions is yes, and they both follow immediately by the link in the comments (even though the fact that the second follows from the link was not mentioned).

The trick is that lattice duality interchanges sums and intersections, e.g.

$$(L_0+L_1)^* = L_0^*\cap L_1^*$$

There are some conditions on this I believe, and I've written an answer on here somewhere on precisely this topic ~2 years ago (I saw it within the last day here, but don't want to hunt for a link currently).

You combine this with the fact that we have a very efficient representation of $L_0 + L_1$. In particular, you can

  1. Concatenate their bases, then
  2. Compute the Hermite Normal Form (HNF) of the resulting generating set

to get a basis for $L_0 + L_1$. By duality, this can also be used to get a basis for the intersection.

What about $L_0 \cap (v+L_1)$? Just view $L_1' = v + L_1$ as another lattice, use the HNF to compute its basis, then use the duality trick to compute the basis of the intersection, e.g. it immediately follows from this general technique.

It's worth mentioning that things get trickier if you cannot view $v + L_1$ as a lattice, for example if it is not discrete. You can see this in 1D with the "lattice" $\mathbb{Z} + \pi\mathbb{Z}$. Provided things like the relevant sums and intersections result in lattices (which will always happen if you require that $q\mathbb{Z}^n\subseteq L, L'\subseteq \mathbb{Z}^n$, perhaps for large $q$) you're fine though.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Thanks, I'm not sure about the second point though, since $L+v$ is not a lattice (for example it does not contain $0$). I played around with the dual of it and couldn't find a nice representation. Is there some way to make it look enough like a lattice that this works? $\endgroup$
    – Sam Jaques
    Sep 23 at 3:40
  • $\begingroup$ I'm pretty sure you can view it as a lattice embedded in one-dimensional higher space. This is similar to how an affine space can be viewed as a linear space in one dimension higher, and conceptually similar to Kannen's embedding to reduce CVP to SVP. The main annoyance with these types of things is that the embedding is highly non-unique, and (e.g. when practically trying to apply things like Kannen's) you'll get different performance depending on which particular embedding (for Kannen's, parameterized by which scaling factor) $\endgroup$
    – Mark
    Sep 23 at 5:12
  • $\begingroup$ Concretely, I'm suggesting that you view $L + v$ as a $n$-dimensional "slice" of an $n+1$ dimensional lattice. These also typically behave well with duality (it is typically called the "projection slice" theorem, but I am mostly seeing references to this for lattices where one projects/slices through linear subspaces, while your setting would be an affine subspace. Maybe that kills the whole idea.) $\endgroup$
    – Mark
    Sep 23 at 5:34
  • $\begingroup$ How much are those notes reliable? cseweb.ucsd.edu//classes/wi10/cse206a/lec1.pdf Other lattices can be obtained from (page 1) there conflicting two base definition; $B \in \mathbb{R}^{k\times n}$ and $B \in \mathbb{R}^{n\times k}$ $\endgroup$
    – kelalaka
    Sep 24 at 9:08
  • 1
    $\begingroup$ they are reliable. That is likely a symptom of there being two conflicting notations for lattices, namely as the image of $x\mapsto Bx$ and the image of $x^t\mapsto x^t B$ ("column notation" vs "row notation"), so it is easy to mix up the order of the two, as in row notation you have rank $k$ dimension $n$ lattice having basis $B\in\mathbb{R}^{n\times k}$, and in column notation you have it in $\mathbb{R}^{k\times n}$. $\endgroup$
    – Mark
    Sep 24 at 20:52

Your Answer

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

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