7
$\begingroup$

Given a non-zero vector $\boldsymbol{v}$ composed of integers, imagine the set of all non-zero integer vectors $\boldsymbol{u}$, such that $\boldsymbol{u} \cdot \boldsymbol{v} = 0$, i.e., the integer vectors orthogonal the original vector. The set $S = \{\boldsymbol{u} : \boldsymbol{u} \cdot \boldsymbol{v} = 0\}$ seems to form a $dim(\boldsymbol{v})-1$ dimensional lattice. Specifically, it's clear that for any two elements of $S$, their linear combination is also in $S$. However, because S is a subset of the lattice of all integer vectors, it's also a lattice. It there a name for this lattice? Additionally, how can it's basis vectors be computed?

$\endgroup$
  • $\begingroup$ This is a good question, I ran into it yesterday and found your post looking for the answer online. I'm surprised there has been no answer yet, so I'm working on it and will post solution once I find it. $\endgroup$ – Florian Bourse Sep 11 '15 at 8:49
1
$\begingroup$

I know that is an old question and already have a beautiful answer given by Florian Bourse, but I am adding the following just for future references.

That lattice has a name: it is called orthogonal lattice. In general, we define it regarding a set of vectors $a_1, ..., a_d \in \mathbb{Z}^n$ as follows:

$$L^\bot := \left\{ u\in \mathbb{Z}^n : \langle a_i, u \rangle = 0 \text{ for } 1 \le i \le d \right\}.$$

Or equivalently we define the lattice $L$ generated by the integer linear combinations of $a_i$'s and $L^\bot$ is then the lattice whose vectors are orthogonal to all the vectors of $L$.

Your case is just a particular one where $d=1$. And you are right about the dimension, it is $n - d$.

There are a lot of other known properties of these lattices (for instance, $\det(L^\bot) \le \det(L)$ and $(L^\bot)^\bot = span(L)\cap\mathbb{Z}^n$).

Section 2 of Merkle-Hellman Revisited: A Cryptanalysis of the Qu-Vanstone by Phong Nguyen and Jacques Stern present some discussion about this type of lattice and a polynomial-time algorithm to compute a LLL-reduced basis to them, which I've implemented in SAGE and published in this Github repository.

$\endgroup$
  • 1
    $\begingroup$ Very nice! Thanks for the reference. $\endgroup$ – Jeremy Jan 4 at 18:02
6
$\begingroup$

I don't know if this lattice has a name, however it is easy to compute a basis given $\mathbf{v}$ by recurrence:

Suppose the gcd of all coordinates of $\mathbf{v}$ is 1 or else divide by it.

Let $\mathbf{v}=(v_1,...,v_n)$.

If $n=2$, then your basis is just $(v_2,-v_1)$

If $n > 2$:
Set the first vector of your basis to be $\mathbf{b}_1=(-v_n*a_1,-v_n*a_2,...,-v_n*a_{n-1},gcd(v_1,...v_{n-1}))$, where the $a_i$ come from Bézout's Identity and can be easily calculated using the extended Euclidean algorithm.
Then complete your basis using the same algorithm with $\mathbf{v}=(v_1,...v_{n-1})$.

This yields a basis of the lattice orthogonal to $\mathbf{v}$ and not a sublattice.
Indeed, all integer vector $\mathbf{u}$ orthogonal to $\mathbf{v}$ have last coordinate which is a multiple of $gcd(v_1,...,v_{n-1})$.
$\sum_{i=1..n} u_i v_i = 0$ implies $u_n v_n = -\sum_{i=1..n-1}u_i v_i$ so $gcd(v_1,...v_{n-1})$ divides $u_n v_n$ and is coprime with $v_n$.

$\endgroup$
  • $\begingroup$ Hi, unless I am mistaking, this algorithm does not produce a full lattice of vectors orthogonal to v. As an example, take v = (125, -75, 45, -27). Then this procedure yields three basis vectors (27, 27, -27, 5), (45, 90, 25, 0), (3, 5, 0, 0). However, the lattice spanned by these vectors is strictly contained inside the correct lattice spanned by (3, 5, 0, 0), (0, 3, 5, 0), (0, 0, 3, 5). $\endgroup$ – Anton Oct 26 '18 at 17:54
  • 1
    $\begingroup$ It works if you don't forget to include the step: Suppose the gcd of all coordinates of v is 1 or else divide by it. Even during the induction step $\endgroup$ – Florian Bourse Nov 12 '18 at 18:08
  • $\begingroup$ thanks, you are absolutely right! $\endgroup$ – Anton Nov 17 '18 at 20:45

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.