Minkowski's theorem in lattice-based cryptography

Question

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 ?

Answer 1

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:

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.