Short vectors

We would like to talk about finding a short vector in a lattice. Thus we need a notion of shortness.

Definition 2.1   The infinity norm of a vector, $x$, with coordinates $x_i$ is:

$$\Vert x\Vert _\infty:=$$max$$(\vert x_i\vert)$$.$$$$

Definition 2.2   The L$_2$ norm of a vector, $x$, with coordinates $x_i$ is:

$$\Vert x\Vert _{\text{L}_2}=\Vert x\Vert _2:=(\sum x_i^2)^{1/2}\text{.}$$

Whenever we write $\Vert x\Vert$, we implicitly mean $\Vert x\Vert _2$. In order to move between these notions, we need the following:

Exercise 2.3  

$$\Vert x\Vert _\infty\leq\Vert x\Vert _2\leq n^{1/2}\Vert x\Vert _\infty$$.$$$$

Definition 2.4   Let $\mathbf{\omega_n}$ denote the volume of the unit ball in $\mathbb{R}^n$.

The factorial function is extended to all complex numbers except the negative integers by the Gamma function defined by

$$\Gamma(z) = \int_0^{\infty} t^{z-1}\mathrm{e}^{-t} dt.$$

This function is related to factorials (including the factorial of half-integers as defined above) by the identity $x! =\Gamma(x+1)$. Stirling's formula holds for positive real values $x\to\infty$:

$$\Gamma(x+1) \sim (x/\mathrm{e})^x\sqrt{2\pi x}.$$

The Gamma function satisfies the identity $\Gamma(z+1)=z\Gamma(z)$ and $\Gamma(3/2)=(1/2)!=\sqrt{\pi}/2$.

Check out ``Eric Weisstein's world of mathematics'' about the amazing world of the Gamma function at http://mathworld.wolfram.com/GammaFunction.html.

Applying Minkowski's theorem to spheres and cubes centered around the origin gives the following two theorems:

Theorem 2.5   Let $L$ be a lattice, and let $\Delta=\vert\det(L)\vert$ be the volume of a fundamental parallelepiped. Then there exists a nonzero element $x\in L$ such that

$$\Vert x\Vert\leq \frac{2}{\omega_n^{1/n}}\Delta^{1/n}$$.$$$$

Note that the right-hand side is asymptotically $c\sqrt{n}\Delta^{1/n}$, where $c=\sqrt{2/\pi\mathrm{e}}$.

Theorem 2.6   With the notation as in the previous theorem, there exists a nonzero element $x\in L$ such that $\Vert x\Vert _\infty\leq \Delta^{1/n}$.

Theorem 2.7   If $\{{\mathbf{b}}_1,\dots, {\mathbf{b}}_n\}$ is a Lovasz-reduced basis, then

• (a)  $\Vert{\mathbf{b}}_1\Vert \leq 2^{(n-1)/2}$min$(L)$
• (b)  $\Vert{\mathbf{b}}_1\Vert \leq 2^{n(n-1)/4}\Delta^{1/n}$
• (c)  $\Vert{\mathbf{b}}_1\Vert\cdots\Vert{\mathbf{b}}_n\Vert \leq 2^{n(n-1)/4}\Delta$.

This theorem follows from the following lemma and the defining properties of Lovasz reduced bases.

Lemma 2.8   If $({\mathbf{b}}_1,\cdots {\mathbf{b}}_n)$ is a Lovasz reduced basis, then $\Vert{\mathbf{b}}_i\Vert \leq 2^{(i-1)/2}\Vert{\mathbf{b}}_i^*\Vert$.

Remark 2.9   $\Delta$ can be defined for a lattice not of full rank, since the fundamental parallelpiped has an $n$-dimensional volume even if it resides in ${\mathbb{R}}^m$ for some $m\ge n$. Recall that $\Delta=\sqrt{\det G({\mathbf{b}}_1,\dots,{\mathbf{b}}_n)}$, where $G$ is the Gram matrix (see handout, section on Euclidean spaces).