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$
1
  • $\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$
    – user99666
    Commented Nov 20, 2013 at 12:17

1 Answer 1

0
$\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$
1
  • $\begingroup$ The author appears to have made it accessible online. $\endgroup$
    – user99666
    Commented Apr 20, 2014 at 7:12

You must log in to answer this question.