# Lattices and shortest vector

• Jun 25th 2013, 08:22 AM
Zoeh
Lattices and shortest vector
In my book about Lattice basis reduction I found the following:

Gaussian Heuristic: for $\displaystyle r$ big enough, there are approximately $\displaystyle$v_m r^m /vol(L)$$lattice points in \displaystyle L$$ of norm $\displaystyle$\le r$$, where \displaystyle v_m$$ denotes the volume of the m-dimensional unit ball.

Corollary: for a lattice $\displaystyle$L$$of rank \displaystyle m$$ the shortest nonzero lattice vector has norm at most approximately $\displaystyle$vol(L)^{1/m}$$. Then they give this example: Given \displaystyle \alpha, \beta, \gamma \in \mathbb{R}$$, and $\displaystyle$X$$> \displaystyle 0$$ with $\displaystyle$X$$large. Small values for the linear form \displaystyle f(x,y,z)=\alpha x + \beta y + \gamma z$$ with $\displaystyle$x,y,z \in \mathbb{Z}$$corresponds to lattices \displaystyle \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0\\ C\alpha & C\beta & C\gamma \end{pmatrix} How large should \displaystyle C$$ be taken to compute $\displaystyle$x,y,z \in \mathbb{Z}$$with \displaystyle max(\mid x \mid,\mid y \mid,\mid z \mid) \le X$$ and $\displaystyle$\mid \alpha x + \beta y + \gamma z \mid$$minimal? Their answer is: The Gaussian heuristic with \displaystyle C=X^3$$ expects solutions of size approximately $\displaystyle$X$$, with \displaystyle \mid \alpha x + \beta y + \gamma z \mid$$ approximately $\displaystyle$X^{-2}$$. How do they come up with \displaystyle C=X^3$$ ?

Using the above Corallary I have that the shortest nonzero lattice vector has norm at most approximately $\displaystyle$vol(L)^{1/m} = \mid determinant(L) \mid ^{1/3}=(C\gamma)^{1/3}

Then since $\displaystyle$max(\mid x \mid,\mid y \mid,\mid z \mid) \le X$$we have that the norm of \displaystyle (\alpha x, \beta y, \gamma z) \le \sqrt(\alpha^2 + \beta^2 + \gamma^2) X. So \displaystyle (C\gamma)^{1/3} \le \sqrt(\alpha^2 + \beta^2 + \gamma^2) X and thus \displaystyle C$$ is approximately $\displaystyle$X^3?

Am I doing this right? I hope someone can explain where the$\displaystyle$C is coming from.

Thank you!