2
$\begingroup$

I consider the following setting. Let $L$ be a lattice of rank $d$ in $\mathbb{Z}^m$ ($d\leq m$). The orthogonal lattice of $L$, denoted by $L^{\perp}$, is defined as the intersection of the orthogonal to the $\mathbb{Q}$-vector space generated by $L$ with $\mathbb{Z}^m$.

My question is in the following context: if I know that the determinant of $L$ is bounded from above, say $\det(L) \leq B$ for some $B$, what can I then say about the successive minima of the lattice $L^{\perp}$?

Some papers I came across suggest that $L^{\perp}$ has a reduced basis consisting of very short vectors compared to a reduced basis of $L$, and thus one expects that $L^{\perp}$ has a reduced basis consisting of vectors with norm around $\sqrt{m-d} \det(L^{\perp})^{1/(m-d)}$. (see for instance page 36 between Theorem 1 and 2 in the paper http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.90.7518&rep=rep1&type=pdf).

Concerning this heuristic, I would like to know how strong thedge the Gaussian heuristic applies to the length of the shortest non-zero vector and not to an entire basis of reduced vectors. Is there a generalised heuristic to explain this?

$\endgroup$
  • $\begingroup$ The PDF you linked has only 16 pages but you referenced page 36. $\endgroup$ – AleksanderRas Dec 6 '18 at 10:19
  • 1
    $\begingroup$ I am referring to the page numbers in the headings of the paper. The heuristic I mention is described between Theorem 1 and 2. $\endgroup$ – Luca Notarnicola Dec 6 '18 at 10:32
  • $\begingroup$ Let $u = (1, 0, k)$ and $v = (0, 1, 0)$, where $k \in \mathbb{Z}$ is a variable. Then let $L = \{x_1 u + x_2 v : x_1, x_2 \in \mathbb{Z} \}$. We can see that the shortest vector of $L$ is $v$, however, the one of $L^\bot$ has length at least $k$, which we can make as big as we want. Thus, we can not relate the successive minima of $L$ and $L^\bot$ in general. So, the answer to your first question would probably be "nothing" (?). Don't you have a distribution or some bound to the entries of the vectors defining $L$? $\endgroup$ – Hilder Vítor Lima Pereira Dec 8 '18 at 18:49
  • $\begingroup$ And I didn't understand your second question :s $\endgroup$ – Hilder Vítor Lima Pereira Dec 8 '18 at 18:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.