What is a good introduction to quantities such as the norm of a lattice and of short vectors in the context of lattice reduction?

273 Views Asked by At

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.