# Relating the shortest vector of a lattice to the orthogonal complement of the lattice

By a lattice we mean sub-lattice of $$\mathbb{Z}^n \cap V$$, where $$V$$ is a subspace of $$\mathbb{R}^n$$ defined over $$\mathbb{Q}$$. We say that a lattice $$\Lambda$$ is primitive if a basis of $$\Lambda$$ can be extended to form a basis of $$\mathbb{Z}^n$$.

For a given lattice $$\Lambda$$, define its orthogonal complement $$\Lambda^\ast$$ by

$$\displaystyle \Lambda^\ast = \{\mathbf{x} \in \mathbb{Z}^n : \mathbf{x} \cdot \mathbf{y} = 0 \text{ for all } \mathbf{y} \in \Lambda\}.$$

It is known that if $$\Lambda$$ is primitive, then $$\det(\Lambda) = \det(\Lambda^\ast)$$.

Suppose that we are given a lattice $$\Lambda$$, contained in a proper subspace $$V \subset \mathbb{Q}^n$$. Suppose that we know have an explicit basis for $$\Lambda^\ast$$. Do we then have any control over the length of the shortest vector in $$\Lambda$$? Is there any way to explicitly control the length of the shortest basis vector of $$\Lambda$$ given data from $$\Lambda^\ast$$?

• (probably better to use a name other than "dual lattice" which usually means something else . . .) Mar 30 '19 at 20:28
• I changed "dual lattice" to "orthogonal complement", since as Noam said, the former has a different meaning; and indeed, when I first read this post, I blipped over the displayed equation and assumed that $\Lambda^*$ was the dual, i.e., $$\{\boldsymbol{x}\in\mathbb{Z}^n:\boldsymbol{x}\cdot\boldsymbol{y}\in\mathbb{Z} \text{ for all }\boldsymbol{y}\in\Lambda\}.$$ I hope you don't mind the edit Mar 30 '19 at 21:41
• @JoeSilverman Silverman I am aware of using the term "dual lattice" to refer to $\{\mathbf{x} \in \mathbb{Z}^n : \mathbf{x} \cdot \mathbf{y} \in \mathbb{Z}\}$, but Browning uses "dual lattice" to refer to the orthogonal complement, so I was following his convention. Apr 1 '19 at 11:47
• What is the Browning reference? Apr 1 '19 at 21:19
• Do you still assume that $\Lambda$ is primitive in your question? Otherwise for any positive integer $m$, $\Lambda$ and $m\Lambda$ (or any lattice on the subspace spanned by $\Lambda$) have the same orthogonal complement in $\mathbb Z^n$, you probably cannot have any control on the length of the shortest vectors of $\Lambda$.
– WKC
Apr 14 '19 at 2:29

This is from Cassels, Rational Quadratic Forms. On page 138, Corollary 1 says the smallest absolute value of the quadratic form is no larger than $$\left( \frac{4}{3} \right)^{(n-1)/2} \; |d|^{1/n}$$ You use the Gram determinant you have for $$d,$$ and the relevant $$n$$ is the dimension of your orthogonal lattice.
Not really a change of subject, some years ago I was answering a question and got very frustrated at correctly finding ANY basis for the orthogonal lattice to a given one. It turned out that, given a few ($$k$$) rows $$B$$ such that $$B$$ can be completed to an integer unimodular matrix, we find a square unimodular integer matrix $$W$$ (by successive elementary matrix product) such that $$BW$$ is the first few rows of an identity matrix. Then a basis is given by the $$n-k$$ right columns of $$W,$$ and one possible completion of $$B$$ to an integer unimodular matrix is just $$W^{-1}$$