3
$\begingroup$

I am studying basic lattice-based cryptography. In the course given by O. Regev, on page number 7, there is Claim 1 and Corollary 2 (Minkowski's First Theorem), both of which are difficult for me to understand.

  1. In Claim 1, how the volume of a ball with a of radius r is $vol(B(0,r)) \ge \left( \frac {2r}{\sqrt{n}} \right)^n$ ? (Specifically, how does the ball contain a hypercube of side length $\frac{2r}{\sqrt{n}}$) ?
  2. In Corollary 2 (Minkowski's First Theorem), for any full-rank lattice $\Lambda$ of rank n, $\lambda_1(\Lambda) \le \sqrt{n} (<det \ \Lambda)^{\frac{1}{n}}$. How to prove this theorem ?
$\endgroup$
5
$\begingroup$

Try to draw a "hypercube" in $\mathbb{R}^2$ (i.e. a square) and in $\mathbb{R}^3$ (i.e. a regular cube), both centered at the origin and having side length equal to $\frac{2r}{\sqrt n}$...

Since they are centered at the origin, each side goes from $-\frac{r}{\sqrt n}$ to $\frac{r}{\sqrt n}$ (in its axis).

Now, the farthest points from the origin that belong to the hypercube are exactly the points of the corners and all the corners are at same distance from the origin. Since a sphere is symmetric, if one corner belongs to a sphere, all the corners belong to the sphere and, consequently, the whole hypercube is contained in the sphere.

The distance between the origin and the corner $c := \left(\frac{r}{\sqrt n }, \frac{r}{\sqrt n }, \cdots, \frac{r}{\sqrt n}\right) \in \mathbb{R}^n$ is given by

$$||c|| = \sqrt{\left(\frac{r}{\sqrt n}\right)^2 + \cdots + \left(\frac{r}{\sqrt n}\right)^2} = \sqrt{n \cdot \left(\frac{r}{\sqrt n}\right)^2} = r$$

Now, notice, by definition, the hypersphere $B(0, r)$ contains all points within distance $r$ to the origin, therefore, it contains the corners and then, the entire $n$-dimensional hypercube.

Since this hypercube is contained in $B(0, r)$, its volume cannot be greater than the volume of $B(0, r)$, and we know that the volume of a hypercube is the product of its sides' length, in this case, $\prod_{i=1}^n \frac{2r}{\sqrt n} = \left( \frac{2r}{\sqrt n} \right) ^n$.

So, finally, $Vol(B(0, r)) \ge \left( \frac{2r}{\sqrt n} \right)^n$.

To the corollary 2, you just have to use $r = \lambda_1$ in the above formula. Then, we get

$$\left( \frac{2\lambda_1}{\sqrt n} \right)^n \le Vol(B(0, \lambda_1))$$

and since $B(0, \lambda_1)$ has no nonzero lattice point (by the definition of $\lambda_1$), its volume can't be greater than $2^n \det(\Lambda)$ (by the contrapositive of theorem 9), then we get

$$Vol(B(0, \lambda_1)) \le 2^n \det(\Lambda)$$

In this section we will talk about why the cube's side length is of $\frac{2r}{\sqrt{n}}$ in n-dimension

We first explain the 3-dimensional case and later extend things to n-dimensions.
Let us take the cube of side length $a$ inscribed in a ball of radius $r$ as shown below:enter image description here

Now, the length of main diagonal of cube is $\sqrt{3}a$.
The length of the main diagonal of cube is the diameter of the Ball of radius r
$\Rightarrow \sqrt{3}a=2r$.
So, $a=\frac{2r}{\sqrt{3}}$ which is of the form $\frac{2r}{\sqrt{n}}$ for $n=3$

So, the result holds for $n=3$. Now, for the n-dimensional case see this question on Math.SE.

From the above post:

The length of the main diagonal of a cube is $\sqrt{n}a$ where $a$ is the length of each side of the cube.
Again, the length of main diagonal of cube is the diameter of the ball of radius $r$
$\Rightarrow \sqrt{n}a= 2r$
so, $a=\frac{2r}{\sqrt{n}}$ which is the value given by theorem.

$\endgroup$
  • $\begingroup$ There is no lattice point in B(0,$\lambda_1$) because $\lambda_1$ is the shortest vector contained in the 1-dimensional lattice. So, it is a vector from origin to one of the lattice point but it does not contain the lattice point. Is I am correct? $\endgroup$ – vivek Feb 9 '18 at 11:18
  • $\begingroup$ Also, I want to know why the dimension $\frac{r}{\sqrt{n}}$ is taken initially? $\endgroup$ – vivek Feb 9 '18 at 11:26
  • $\begingroup$ $ \lambda_1$ is not the shortest vector in a 1-dimensional lattice. Given any $n$-dimensional lattice $\Lambda$ ($n$ can be 1, 2, 3, 4, and so on...), $\lambda_1$ is the length of the shortest nonzero vector in $\Lambda$, that is, $\exists v \in \Lambda : 0 < ||v|| = \lambda_1$. $\endgroup$ – Hilder Vítor Lima Pereira Feb 9 '18 at 11:27
  • $\begingroup$ $B(0, \lambda_1)$ is an open ball. If it was a closed ball, it would have some lattice point with length $ \lambda_1$ in its border. If $B(0, \lambda_1)$ had some nonzero lattice point, then the length of that point would be smaller than $ \lambda_1$, which contradicts the definition of $ \lambda_1$. $\endgroup$ – Hilder Vítor Lima Pereira Feb 9 '18 at 11:28
  • $\begingroup$ The dimension is $n$, not $\frac {r}{\sqrt n}$. $\endgroup$ – Hilder Vítor Lima Pereira Feb 9 '18 at 11:30

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.