Table of Contents

• Basics
  • Lattice
    • Determinant
    • Successive Minima
    • Minkowski's Theorem
  • Computational Problems
    • Same Lattice Problems

In complexity theory, we say a problem is hard if it it hard for the worst-case instance; while in cryptography, a problem is deemed hard only if it is hard for the average-case instance (i.e., for all but a negligible fraction of instances).

Basics

Lattice

Definition of a Lattice

Let ${\mathbb{R}}^m$ be the $m$-dimensional Euclidean (inner product) space. A lattice in ${\mathbb{R}}^m$ is the set

$$\mathcal{L}(b_1,...,b_n)=\{\sum _{i=1}^n{z}_i{b}_i\mid z_i\in \mathbb{Z}\}$$

of all integer linear combinations of the basis vectors $b_1,...,b_n$, where $n\le m$ is the rank of the lattice, and $m$ is the dimension of the lattice.

Domain of Lattice and Vector Space

Note that the vector (Euclidean) space is defined over field $\mathbb{R}$, but the lattice itself is defined over the integers $\mathbb{Z}$. I think this is a fundamental difference between lattice and general subspace. Because lattice is discrete, it is only restricted to "integer span" of the basis vectors, whereas subspace is defined over the entire field $\mathbb{R}$ and can take arbitrary linear combinations of the basis vectors, which makes it continuous.

Representation of a Lattice

There are many different ways to represent a lattice, depending on the choice of basis vectors. For example, in 2-dimensional space ${\mathbb{R}}^2$, a lattice can have different bases that generate the same set of points.

One Basis	Another Basis

Where the left image shows a lattice generated by basis,

$$b_1=\left(\begin{array}{c}1\\ 2\end{array}\right),b_2=\left(\begin{array}{c}1\\ -1\end{array}\right)$$

and the right image shows a lattice generated by another basis,

$$b_1^{\prime }=b_1+b_2=\left(\begin{array}{c}2\\ 1\end{array}\right),b_2^{\prime }=2b_1+b_2=\left(\begin{array}{c}3\\ 3\end{array}\right)$$

We see that, the (intersection) points of the two lattices coincide, meaning that both bases generate the same set of lattice points in ${\mathbb{R}}^2$.

Why do different bases generate the same lattice?

One question here : is there any relationships between these bases that generate the same lattice? The answer is yes, if they are related by a unimodular transformation, i.e., an integer matrix with determinant $\pm 1$. That is,

$$B^{\prime }=UB,\text{where }U\in {\mathbb{Z}}^{n\times n}\text{ and }det(U)=\pm 1.$$

---

We have already noticed that a lattice is defined over the integers $\mathbb{Z}$ which is discrete, whereas the Euclidean space is defined over the field $\mathbb{R}$ which is continuous. Recall that in linear algebra, the $\text{span}(B)$ is independent of the choice of basis $B$, meaning that any basis that generates the same subspace will have the same span. For lattices, different bases can also generate the same lattice.

Fact 1.1 - Span of Lattice Bases

If $B$ and $B^{\prime }$ generate the same lattice, then $\text{span}(B)=\text{span}(B^{\prime })$.

Proof

To show $\text{span}(B)=\text{span}(B^{\prime })$, we need to prove two inclusions:

1. $\text{span}(B^{\prime })\subseteq \text{span}(B)$
2. $\text{span}(B)\subseteq \text{span}(B^{\prime })$

---

Regarding (1), since $B^{\prime }=BU$ where $U$ is invertible, basis $B^{\prime }$ is a linear combination of the columns of $B$, meaning that any linear combination of the columns of $B^{\prime }$ can also be expressed as a linear combination of the columns of $B$. Therefore, $\text{span}(B^{\prime })\subseteq \text{span}(B)$.

Regarding (2), since $B=B^{\prime }{U}^{-1}$ where $U$ is invertible, basis $B$ is a linear combination of the columns of $B^{\prime }$, meaning that any linear combination of the columns of $B$ can also be expressed as a linear combination of the columns of $B^{\prime }$. Therefore, $\text{span}(B)\subseteq \text{span}(B^{\prime })$.

Completing the proof.

Clearly, we see :

1. In this case, lattice $\mathcal{L}(B)$ and vector space $\text{span}(B)$ are closely related, but they are not the same. The lattice consists of discrete points, while the vector space contains all linear combinations of the basis vectors with real coefficients .

2. Any set of $n$ linearly independent vectors from lattice $\mathcal{L}(B)$ forms a basis for vector space $\text{span}(B)$. But this set does not necessarily generate the entire lattice $\mathcal{L}(B)$.

   For example, two vectors from a lattice $\mathrm{\Lambda }=\mathcal{L}(b_1,b_2)$,

   $$\begin{gathered} b_1^{\prime }=b_1+b_1=[2,1{]}^{\mathrm{\top }} \\ {b}_2^{\prime }=b_1-b_2=[0,3{]}^{\mathrm{\top }} \end{gathered}$$

   are independent, they are surely able to form a basis for vector space $\text{span}(b_1,b_2)=\mathcal{span}(\mathrm{\Lambda })$. But they cannot generate the lattice $\mathrm{\Lambda }$ since $b_1=\frac{1}{2}(b_1^{\prime }+b_2^{\prime })$, not an integer combination of $b_1^{\prime }$ and $b_2^{\prime }$.

NOTE

So what is the characteristic of vectors that can form a lattice basis? How to remove the non-integer linear combinations from consideration?

Fact 1.2 - Valid Lattice Basis

Given a lattice $\mathcal{L}(B)$ with basis $B=[b_1,...,b_n]$, and $n$ linearly independent lattice vectors,

$$B^{\prime }=[b_1^{\prime },...,b_n^{\prime }],b_i^{\prime }\in \mathcal{L}(B)$$

We define

$$\mathcal{P}(B^{\prime })=\{\sum _{i=1}^n{x}_i{b}_i^{\prime }:0\le x_i<1\}$$

as the half-open parallelepiped generated by the basis $B^{\prime }$. Note that the coefficients $x_i$ are restricted to the interval $[0,1)$, which ensures that each point in $\mathcal{P}(B^{\prime })$ is uniquely represented. Then $B^{\prime }$ is a lattice basis if and only if $\mathcal{P}(B^{\prime })$ does not contain any lattice vector (points) other than the zero vector (origin point).

NOTE

If $B^{\prime }$ is not a lattice basis for $\mathcal{L}(B)$, i.e., $\mathcal{L}(B^{\prime })\ne \mathcal{L}(B)$. Since it is still linearly independent, so it also generates a lattice $\mathcal{L}(B^{\prime })$ which is different from $\mathcal{L}(B)$. But, what is the relationship between $\mathcal{L}(B)$ and $\mathcal{L}(B^{\prime })$?

Fact 1.3 - Sublattice

Sublattice is an natural concept after half-open parallelepiped, if there are lattice points from $\mathcal{L}(B)$ in the half-open parallelepiped, which implies a inclusion relationship :

$$\mathcal{L}(B^{\prime })\subseteq \mathcal{L}(B).$$

If $\mathcal{L}(B^{\prime })⊊\mathcal{L}(B)$, then we call $\mathcal{L}(B^{\prime })$ a proper sublattice of $\mathcal{L}(B)$.

NOTE

As we know the lattice basis vector is defined over $\mathbb{R}$. For the convenience of computation, we often consider lattice basis vectors over $\mathbb{Z}$, i.e., integer lattice basis vectors.

Fact 1.4 - Lattice as a Subgroup

It is obvious that a lattice $\mathcal{L}(B)$ has property of addition closure and contains the zero vector, i.e.,

$$\mathbf{0}\in \mathcal{L}(B),\text{and}\mathrm{\forall }u,v\in \mathcal{L}(B),u+v\in \mathcal{L}(B).$$

Moreover, for any $u\in \mathcal{L}(B)$, its additive inverse $-u$ is also in $\mathcal{L}(B)$. Therefore, a lattice $\mathcal{L}(B)$ forms a subgroup of the additive group $({\mathbb{R}}^n,+)$.

Determinant

Definition of Determinant of a Lattice

The determinant of a lattice $\mathcal{L}(B)$, denoted as $det(\mathcal{L}(B))$, geometrically is the volume of the fundamental parallelepiped generated by the basis $B$, i.e.,

$$det(\mathcal{L}(B))=\text{Vol}(\mathcal{P}(B)).$$

Furthermore, the determinant of a lattice is independent of the choice of basis. That is, if $B$ and $B^{\prime }$ are two different bases of the same lattice $\mathcal{L}(B)$, $\mathcal{L}(B)=\mathcal{L}(B^{\prime })$, then

$$det(\mathcal{L}(B))=det(\mathcal{L}(B^{\prime })).$$

Intuitively, the determinant is the shaded area of the fundamental parallelepiped generated by the basis $B$ shown in the figures above.

A natural question is how to compute the determinant of a lattice given one basis? There are two solutions for this.

Gram-Schmidt Process

The natural way is to :

1. compute the orthogonal basis $B^{\ast }=(b_1^{\ast },...,b_n^{\ast })$ corresponding to the given basis $B=(b_1,...,b_n)$ using the Gram-Schmidt process.
2. take the product of the norms of the orthogonal basis vectors to obtain the determinant:$$det(\mathcal{L}(B))=\prod _{i=1}^n\parallel b_i^{\ast }\parallel ,$$where $b_i^{\ast }$ are the Gram-Schmidt orthogonalized vectors of the basis $B$.

Take the figure 1.1 as an example, after applying the Gram-Schmidt process to the basis vectors, we obtain :

$$\begin{array}{rl}{b}_1^{\ast }& =b_1\\ b_2^{\ast }& =b_2-\frac{⟨b_2,b_1^{\ast }⟩}{⟨b_1^{\ast },b_1^{\ast }⟩}{b}_1^{\ast }\end{array}$$

where $⟨b_1^{\ast },b_2^{\ast }⟩=0$. Even though the "shaded" area is a parallelogram, after being orthogonalized, it is a rectangle with area equal to the product of two orthogonal edges which corresponds to the product of the norms of the orthogonalized vectors.

---

NOTE

By Gram-Schmidt orthogonalization, we can obtain a orthogonal basis $B^{\ast }$ from any given basis $B$, if $B$ is a lattice basis, i.e., $B\in \mathcal{L}(B)$. It is obvious that some orthogonal basis vector $b_i^{\ast }$ might not be in the lattice space anymore, i.e., $b^{\ast }\notin \mathcal{L}(B)$, since the coefficients $\frac{⟨b_i,b_j^{\ast }⟩}{⟨b_j^{\ast },b_j^{\ast }⟩}$ might not be an integer.

We see that $B^{\ast }=(b_1^{\ast },b_2^{\ast })$ is not a lattice basis since one point from $\mathcal{L}(B)$ does lie in $\mathcal{L}(B^{\ast })$, which implies that $\mathcal{L}(B^{\ast })\ne \mathcal{L}(B)$.

Determinant of Lattice Basis Matrix

In linear algebra, we know that, if $B=(b_1,...,b_n)$ is a basis of $\text{span}(B)$, then the determinant of the matrix formed by the basis vectors is equal to the product of the norms of the Gram-Schmidt orthogonalized vectors and a sign factor:

$$det(B)=(-1{)}^{\sigma }\cdot \prod _{i=1}^n\parallel b_i^{\ast }\parallel$$

If $B$ is a lattice basis, then the determinant of the lattice $\mathcal{L}(B)$ is equal to the absolute value of the determinant of the basis matrix:

$$det(\mathcal{L}(B))=\prod _{i=1}^n\parallel b_i^{\ast }\parallel =|det(B)|=\sqrt{B^{T}B}$$

This is an alternative way to compute the determinant of a lattice given its basis, instead of computing every orthogonal vectors sequentially.

Successive Minima

Let $\mathcal{L}(B)$ be a lattice generated by the basis $B$ with rank $n$. The $i$-th successive minimum ${\lambda }_i(\mathcal{L}(B))$ is defined as:

$${\lambda }_i(\mathcal{L}(B))=inf\{r>0:\dim (\text{span}(\mathcal{L}(B)\cap B(0,r)))\ge i\}$$

Intuitively, the $i$-th successive minimum represents the smallest radius of a ball centered at the origin that contains at least $i$ linearly independent lattice vectors.

More specially, when $i=1$, the first successive minimum ${\lambda }_1(\mathcal{L}(B))$ corresponds to the length of the shortest non-zero lattice vector in $\mathcal{L}(B)$ :

$${\lambda }_1(\mathcal{L}(B))=min\{\parallel v\parallel :v\in \mathcal{L}(B)\setminus \{0\}\}$$

NOTE

The successive minima ${\lambda }_i(\mathcal{L}(B))$ is independent of the choice of the lattice basis $B$, but the orthogonal basis obtained from Gram-Schmidt orthogonalization does have a relationship with the first successive minimum ${\lambda }_1(\mathcal{L}(B))$.

Fact 1.5 - First Successive Minimum as an Upper Norm Bound of Lattice Basis

Let $B$ a lattice basis, and let $B^{\ast }$ be the corresponding Gram-Schmidt orthogonalized basis. Then, the first successive minimum ${\lambda }_1(\mathcal{L}(B))$ provides an upper bound for the norms of the vectors in $B^{\ast }$:

$${\text{min}}_j\parallel b_j^{\ast }\parallel \le {\lambda }_1(\mathcal{L}(B)),\mathrm{\forall }i=1,...,n$$

Proof

For simplicity, we only consider a basis of a two-dimensional lattice, i.e., $B=(b_1,b_2)$. The Gram-Schmidt orthogonalized basis is $B^{\ast }=(b_1^{\ast },b_2^{\ast })$. By definition, we have:

$$b_1^{\ast }=b_1,b_2^{\ast }=b_2-\frac{⟨b_2,b_1^{\ast }⟩}{\parallel b_1^{\ast }{\parallel }^2}{b}_1^{\ast }$$

---

Suppose any non-zero lattice vector $v=c_1{b}_1+c_2{b}_2$ where $c_1,c_2\in \mathbb{Z}$. Since $\text{span}(b_1^{\ast },b_2^{\ast })=\text{span}(b_1,b_2)$, any lattice vector can also be expressed as a linear combination of the Gram-Schmidt orthogonalized basis vectors:

$$\begin{array}{rl}v& =c_1{b}_1^{\ast }+c_2\cdot (b_2^{\ast }+\frac{⟨b_2,b_1^{\ast }⟩}{\parallel b_1^{\ast }{\parallel }^2}{b}_1^{\ast })\\ & =(c_1+c_2\frac{⟨b_2,b_1^{\ast }⟩}{\parallel b_1^{\ast }{\parallel }^2})b_1^{\ast }+c_2{b}_2^{\ast }\end{array}$$

Two cases involved:

(a) If $c_2\ne 0$, $v$'s component perpendicular to orthogonal basis vector $b_1^{\ast }$ is given by:

$$v_{\perp b_1^{\ast }}=c_2{b}_2^{\ast }$$

thus we have $\parallel v\parallel \ge \parallel v_{\perp b_1^{\ast }}\parallel =|c_2|\parallel b_2^{\ast }\parallel \ge \parallel b_2^{\ast }\parallel$.

(b) If $c_2=0$, $v$ is parallel to $b_1^{\ast }$, thus we have $\parallel v\parallel \ge \parallel v_{\perp b_2^{\ast }}\parallel =|c_1|\parallel b_1^{\ast }\parallel \ge \parallel b_1^{\ast }\parallel$.

This implies for any non-zero lattice vector $v$, we have:

$$\parallel v\parallel \ge b_1^{\ast }\text{ or }\parallel v\parallel \ge b_2^{\ast }$$

which is equivalent with

$$\parallel v\parallel \ge \underset{j}{min}\parallel b_j^{\ast }\parallel$$

---

More specially, for the first successive minimum ${\lambda }_1(\mathcal{L}(B))$ which is the smallest non-zero lattice vector norm, we have:

$${\lambda }_1(\mathcal{L}(B))\ge {\text{min}}_j\parallel b_j^{\ast }\parallel$$

Minkowski's Theorem

Blichfeldt's Theorem

Let $\mathrm{\Lambda }$ be a lattice, and let $S\subset \text{span}(\mathrm{\Lambda })$ be a measurable set with volume $\text{vol}(S)>det(\mathrm{\Lambda })$. Then, there exist two distinct points $x,y\in S$ such that $x-y\in \mathrm{\Lambda }$.

Proof

Let $\mathrm{\Lambda }=2\mathbb{Z}$ be the lattice of even integers on x-axis, and $\mathcal{P}(\mathrm{\Lambda })=[0,2)$ is a fundamental parallelepiped of the lattice (with only one basis vector $2$). Consider a measurable set $S=[0,3)\subseteq \text{span}(\mathrm{\Lambda })=\mathbb{R}$, which ensures $\text{vol}(S)=3>det(\mathrm{\Lambda })=2$, then we need to show that exists $x,y\in [0,3)$ such that $x-y\in \mathrm{\Lambda }$.

---

Note that lattice $\mathrm{\Lambda }$ is a set of discrete even points on x-axis, and $S$ is real interval on x-axis. A few facts on this :

1. The entire vector space $\mathbb{R}=\text{span}(\mathrm{\Lambda })$ is partitioned into disjoint translates of the fundamental parallelepiped $\mathcal{P}(\mathrm{\Lambda })$, i.e., $\mathrm{\Lambda }+\mathcal{P}(\mathrm{\Lambda })=\mathbb{R}$ :

   $$\begin{array}{rl}\mathbb{R}=\text{span}(\mathrm{\Lambda })& =\bigcup _{x\in \mathrm{\Lambda }}(x+\mathcal{P}(\mathrm{\Lambda }))\\ & =[0,2)\cup [2,4)\cup [4,6)\cup \dots \end{array}$$

2. The projections on these disjoint translates of the fundamental parallelepiped cover the entire set $S$. That is,

   $$S=\bigcup _{x\in \mathrm{\Lambda }}(S\cap (x+\mathcal{P}(\mathrm{\Lambda })))$$

   In our example, $S=S_0+S_2=[0,2)+[2,3)$.

3. $\text{vol}(S)>det(\mathrm{\Lambda })$ ensures that there exist at least two points in $S$ that differ by a lattice vector, we can use the pigeonhole principle to guarantee this. In our example,

   $$\text{vol}(S)=\text{vol}(S_0)+\text{vol}(S_2)=2+1=3>det(\mathrm{\Lambda })=2$$

   Therefore, there must exist two points $x\in S_0$ and $y\in S_2$ such that $x-y\in \mathrm{\Lambda }$. For instance, $x=0.5\in S_0$ and $y=2.5\in S_2$, then $x-y=-2\in \mathrm{\Lambda }$.

Convex Body Theorem

For any lattice $\mathrm{\Lambda }$ of rank $n$ and any convex set $S\subset \text{span}(\mathrm{\Lambda })$ symmetric about the origin, if $\text{vol}(S)>2^{n}det(\mathrm{\Lambda })$, then $S$ contains a non-zero lattice point of $\mathrm{\Lambda }$.

Proof

Consider another set $S^{\prime }=\{x\in {\mathbb{R}}^n\mid 2x\in S\}$, whose volume :

$$\text{vol}(S^{\prime })=\frac{1}{2^n}\text{vol}(S)$$

Since $\text{vol}(S)>2^{n}det(\mathrm{\Lambda })$, it follows that

$$\text{vol}(S^{\prime })=\frac{1}{2^n}\text{vol}(S)>det(\mathrm{\Lambda })$$

By Blichfeldt's Theorem, there exist two distinct points $x,y\in S^{\prime }$ such that $x-y\in \mathrm{\Lambda }$. Since $S^{\prime }$ is a scaled version of $S$, we have $2x,2y\in S$. Since $S$ is symmetric, then $-2x,-2y\in S$, and since $S$ is also convex, so the mid-point $\frac{2x+(-2y)}{2}=x-y\in S$. Therefore, $S$ contains a non-zero lattice point of $\mathrm{\Lambda }$.

By observing the figure above, we can see that :

1. The symmetric convex $S=\mathcal{B}(0,\sqrt{n}det(\mathrm{\Lambda }{)}^{1/n})$ be a balll of radius $\sqrt{n}det(\mathrm{\Lambda }{)}^{1/n}$ centered at the origin.
2. $\text{vol}(S)>2^{n}det(\mathrm{\Lambda })$ always holds because it contains an $n$-dimensional hypercube with edges of length $2det(\mathrm{\Lambda }{)}^{1/n}$. So $\text{vol}(S)$ always exceeds $(2det(\mathrm{\Lambda }{)}^{1/n}{)}^n=2^{n}det(\mathrm{\Lambda })$.
3. By Minkowski's theorem there exists a non-zero lattice point in $S$, that is $v\in \mathcal{L}(B)\setminus \{0\}$, and $\parallel v\parallel <\sqrt{n}det(\mathrm{\Lambda }{)}^{1/n}$. Therefore, the shortest nonzero lattice has length :$${\lambda }_1(\mathrm{\Lambda })\le \parallel v\parallel <\sqrt{n}det(\mathrm{\Lambda }{)}^{1/n}$$

By now, we have established an upper bound on the length of the shortest nonzero lattice vector in terms of the determinant of the lattice and the dimension.

Minkowski's Second Theorem

For any rank $n$ lattice $\mathcal{L}(B)$, the successive minima (in the $l_2$ norm) ${\lambda }_1,...,{\lambda }_n$ satisfy :

$$(\prod _i^n{\lambda }_i{)}^{1/n}<\sqrt{n}det(\mathcal{L}(B){)}^{1/n}$$

Proof Logic

The equivalence of the goal is :

$$\prod _i^n{\lambda }_i<(\sqrt{n}{)}^{n}det(\mathcal{L}(B))$$

we will prove it by contradiction. We assume that

$$\prod _i^n{\lambda }_i\ge (\sqrt{n}{)}^{n}det(\mathcal{L}(B))$$

then we need to find a contradiction after some inductions.

---

As shown in above figure, for simplicity we consider $n=2$, a lattice $\mathrm{\Lambda }=\mathcal{L}(B)$ with basis $B=(b_1,b_2)$ where $\parallel b_1\parallel \le \parallel b_2\parallel$, and successive minima ${\lambda }_1=\parallel b_1\parallel ,{\lambda }_2=\parallel b_2\parallel$.

Let $S\subseteq \text{span}(\mathcal{L}(B))$ be an open (real) circle with unit radius in the real space of $\text{span}(\mathrm{\Lambda })$. Define a transformation that scale the horizontal axis of circle $S$ by a factor ${\lambda }_1$, and the vertical axis by a factor ${\lambda }_2$. Then we obtain an ellipse $T(S)$:

$$T((x,y))=({\lambda }_{1}x,{\lambda }_{2}y),(x,y)\in S$$

If we can find a non-zero lattice point whose length is less than ${\lambda }_2=\parallel b_2\parallel$ inside the ellipse $T(S)$, then it would contradict the definition of successive minima. This is the key idea behind our proof.

---

It is clear that their volumn is scaled by the product of the scaling factors along each axis:

$$\text{vol}(T(S))={\lambda }_1\cdot {\lambda }_2\cdot \text{vol}(S)$$

(In 2D, the volume corresponds to the area of the ellipse, $\text{vol}(T(S))=\pi {\lambda }_1{\lambda }_2$ and $\text{vol}(S)=\pi$). By our assumption, ${\lambda }_1\cdot {\lambda }_2\ge (\sqrt{2}{)}^{2}det(\mathcal{L}(B))=2det(\mathcal{L}(B))$, and $\text{vol}(S)=\pi >2$, we have:

$$\text{vol}(T(S))>(2\text{vol}(S))\cdot det(\mathcal{L}(B))>2^{2}det(\mathcal{L}(B))$$

Since the ellipse $T(S)$ is convex and symmetric with respect to the origin, all conditions of Minkowski's convex body theorem are satisfied, by Minkowski's convex body theorem, the ellipse $T(S)$ must contain a non-zero lattice point of $\mathcal{L}(B)$. For example, the point $ts\in T(S)$ is a lattice point, and it is scaled by $T$ from point $s\in S$.

---

Let $s=(x,y)$, then $ts=({\lambda }_{1}x,{\lambda }_{2}y)$, then we have :

$$|\parallel ts{\parallel }^2=\parallel ({\lambda }_{1}x,{\lambda }_{2}y){\parallel }^2=({\lambda }_{1}x{)}^2+({\lambda }_{2}y{)}^2$$

By successive minima, ${\lambda }_1\le {\lambda }_2$ and the length of $s$ is at most 1 (since $s$ lies on the unit circle), we have :

$$\parallel ts{\parallel }^2=({\lambda }_{1}x{)}^2+({\lambda }_{2}y{)}^2\le {\lambda }_2^2(x^2+y^2)<{\lambda }_2^2$$

Thus $\parallel ts\parallel <{\lambda }_2$ breaks the successive minima condition, leading to a contradiction.

Computational Problems

Minkowski's bound is asymptotically tight in worst case.

That means for some lattice, the actual ${\lambda }_1$ is propotional to the Minkowski's bound by some factor $0<c<1$:

$${\lambda }_1\approx c\cdot \sqrt{n}det(\mathcal{L}{)}^{1/n}$$

In this case, when $n$ grows, the Minkowski's bound also grows, and the actual ${\lambda }_1$ grows proportionally, but by a smaller factor $c$. But the ratio between the actual ${\lambda }_1$ and the Minkowski's bound remains unchanged.

Same Lattice Problems

The problem of finding a lattice vector of length ${\lambda }_1$ is known as the Shortest Vector Problem (SVP).

Given a lattice vector $t$, finding a nonzero lattice vector such that $\parallel v-t\parallel$ is minimized is known as the Closest Vector Problem (CVP).

Approximate SVP

Given a basis $B\in {\mathbb{Z}}^{m\times n}$, find a nonzero lattice vector $Bx$ where $x\in {\mathbb{Z}}^n\setminus \{0\}$, such that $\parallel Bx\parallel \le \gamma \cdot \parallel By\parallel$ for any other nonzero lattice vector $By$.

Approximate CVP

Given a basis $B\in {\mathbb{Z}}^{m\times n}$ and a target vector $t\in {\mathbb{R}}^m$, find a lattice vector $Bx$ where $x\in {\mathbb{Z}}^n$, such that $\parallel Bx-t\parallel \le \gamma \cdot \parallel By-t\parallel$ for any other lattice vector $By$.