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$?

  • 1
    $\begingroup$ (probably better to use a name other than "dual lattice" which usually means something else . . .) $\endgroup$ Mar 30 '19 at 20:28
  • 1
    $\begingroup$ 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 $\endgroup$ Mar 30 '19 at 21:41
  • $\begingroup$ @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. $\endgroup$ Apr 1 '19 at 11:47
  • $\begingroup$ What is the Browning reference? $\endgroup$
    – Will Jagy
    Apr 1 '19 at 21:19
  • $\begingroup$ 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$. $\endgroup$
    – 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.

The translation to lattices should not change much, maybe a constant multiple.

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}$


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.