9
$\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$
1
  • $\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$ Commented Sep 11, 2015 at 8:49

2 Answers 2

7
$\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$.

Example

Suppose we want the lattice orthogonal to $v = (125, -75, 45, -27)$.
We first look at the orthogonal of $(125,-75)$, which is the same as the lattice orthogonal to $(5,-3)$ if we simplify by $gcd(125,-75)=25$.
So our first vector is going to be $(-3,-5,0,0)$.
Now we look at the orthogonal of $(125,-75,45)$, which is the same as the orthogonal of $(25,-15,9)$, if we simplify by $gcd(125,-75,45)=5$.
Bézout's Identity gives us $2*25+3*(-15)=5$, so our new vector is $(-9*2,-9*3,5,0)=(-18,-27,5,0)$.
Finally, we arrive to our last step, Bézout's Identity gives us $1*125+1*(-75)+(-1)*45=5$, so our last vector is $(27*1,27*1,27*(-1),5)=(27,27,-27,5)$.
So our basis is formed by the three vectors : $\big((-3,-5,0,0),(-18,-27,5,0),(27,27,-27,5)\big)$

$\endgroup$
5
  • $\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
    Commented Oct 26, 2018 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$ Commented Nov 12, 2018 at 18:08
  • $\begingroup$ thanks, you are absolutely right! $\endgroup$
    – Anton
    Commented Nov 17, 2018 at 20:45
  • $\begingroup$ I don't understand this algorithm. Can you give an explicit example, like for Anton's? $\endgroup$ Commented Feb 27, 2020 at 3:38
  • $\begingroup$ I edited my answer to illustrate the algorithm working on Anton's example. Hope this helps. $\endgroup$ Commented Mar 1, 2020 at 19:15
3
$\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
  • 1
    $\begingroup$ Very nice! Thanks for the reference. $\endgroup$
    – Jeremy
    Commented Jan 4, 2019 at 18:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .