1
$\begingroup$

I am trying to make sense of different notations used in measuring lattices, in particular before and after a basis reduction. In particular, I am trying to get bounds and estimates for the size of the shortest and of all the basis vectors after lattice reduction, not only in the usual L2-norm $||\vec{x}|| = (\Sigma x_i^2)^{1/2}$, but also in the supremum (L$\infty$) and in the railroad (L1) norm. I have some elementary questions and possible misunderstandings which might be best clarified by a good introductory text.

I think I have seen a statement of bounds for LLL inall of these norms in a slide from some talk. But am not sure where, and would additionally be interested in some kind of motivation or reasoning (which doesn't have to be a full-fledged proof).

I am currently also a bit confused by having seen (or misunderstood?) the determinant of a lattice (basis) that occurs in such formulas for both tight bounds and heuristic estimates defined in two different ways, as either the matrix-determinant of any basis $\mathbb{b} = \{ \vec{b}_i \}$ of the lattice, or as the square root of the matrix-determinant of $\mathbb{b^{T}b}$. I wonder if there are common situations (e.g. basis vectors forming a triangular matrix...?) where these are identical, but if so, then I don't quite see it myself. Is there a common convention for the determinant of a lattice?

Another source of confusion to me is that some bounds are based on the (usually unknown) shortest vector (often called $\lambda_1$) of a lattice, whilst others state what seems to be very similar bounds based on the determinant of the lattice. I understand that there the Gaussian heuristic links these two, at least approximately. But which of these actually gives a tight bound rather than something based on a heuristic?

What would be a good, and ideally comprehensive source for this topic? Unfortunately, I'm bringing the additional burden of a somewhat selective interest in maths. Basically, I can do simple quantum mechanical calculations, but I cannot talk about it with a mathematician without a translator.

$\endgroup$
  • $\begingroup$ Should I have created a tag lattice-basis-reduction or lattice-reduction? My first thought is that I should have, but stackexchange told me to wait until I have more reputation points. $\endgroup$ – pyramids Nov 20 '13 at 12:17
1
$\begingroup$

A very nice introductory survey to lattice reduction is

F. Eisenbrand, Integer Programming and algorithmic geometry of numbers, Chapter 14 in: 50 years of integer programming 1958-2008 (M. Juenger et al., eds.), Springer, Berlin 2010.

$\endgroup$
  • $\begingroup$ The author appears to have made it accessible online. $\endgroup$ – pyramids Apr 20 '14 at 7:12

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.