Bound on the shortest non-zero vector in any full rank n-dimensional lattice $\Lambda \subseteq \mathbb{R}^n$ with respect to the $1$-norm.

cryptographyinteger-lattices

How can i prove
$$\lambda_1 \; \leq \; (n! \; det(\Lambda))^{\frac{1}{n}} \approx \frac{n \; det{(\Lambda)}^\frac{1}{n}}{e}.$$

Here $\Lambda_1$ is shortest non-zero vector. My initial thought was using Minkowski theorem (choosing $S =$ n-Ball of radius $\sqrt n \frac{\lambda_1}{n}$) and proof by contradiction (assuming $\lambda_1 \; > \; (n! \; det(\Lambda))^{\frac{1}{n}}$ and contracting with minimality of $\lambda_1$).

[Minkowski’s convex body theorem] : Let $\Lambda$ be a full dimensional lattice. If $S \subset \mathbb{R}^n$ is a symmetric convex body of volume $vol(S) > 2^n det(\Lambda)$ , then $S$ contains a non-zero lattice point.

$1-$norm for a vector $x$ : $\sum{}{}{|x_i|}$.

Best Answer

$$C_n=Vol(\{ x, \|x\|_1\le 1\})= \int_{-1}^1 Vol(\{ y, \|y\|_1\le 1-x_1\})dx_1$$ $$=\int_{-1}^1 (1-|x_1|)^{n-1}C_{n-1}dx_1=\frac{2}n C_{n-1}=\frac{2^n}{n!}$$ For all $r<\lambda_1/2$ then $ \{x, \|x\|_1\le r\}$ doesn't intersect its $\Lambda$-translates. Thus $$\det(\Lambda)\ge Vol(\{ x, \|x\|_1\le r\})=r^n\frac{2^n}{n!}$$ and hence $$\lambda_1^n\le n! \det(\Lambda)$$

Related Question