2
$\begingroup$

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

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ (probably better to use a name other than "dual lattice" which usually means something else . . .) $\endgroup$
    – Noam D. Elkies
    Commented Mar 30, 2019 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$
    – Joe Silverman
    Commented Mar 30, 2019 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$
    – Stanley Yao Xiao
    Commented Apr 1, 2019 at 11:47
  • $\begingroup$ What is the Browning reference? $\endgroup$
    – Will Jagy
    Commented Apr 1, 2019 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
    Commented Apr 14, 2019 at 2:29

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
2

You must log in to answer this question.

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