Bounding the shortest vector Minkowski's theorem gives an upper bound for the length of the shortest nonzero vector. This result has applications in lattice cryptography and number theory. '''Theorem (Minkowski's bound on the shortest vector):''' Let L be a lattice. Then there is a x \in L \setminus \{0\} with \|x\|_{\infty} \leq \left|\det(L)\right|^{1/n}. In particular, by the standard comparison between l_2 and l_{\infty} norms, \|x\|_2 \leq \sqrt{n}\, \left|\det(L)\right|^{1/n}. {{math proof | proof = Let l = \min \{ \|x\|_{\infty} : x \in L \setminus \{0\} \}, and set C = \{ y : \|y\|_{\infty} . Then \text{vol}(C) = (2l)^n. If (2l)^n > 2^n |d(L)|, then C contains a non-zero lattice point, which is a contradiction. Thus l \leq | d(L)|^{1/n}. Q.E.D.}}
Remarks: • The constant in the L^2 bound can be improved, for instance by taking the open ball of radius as C in the above argument. The optimal constant is known as the
Hermite constant. • The bound given by the theorem can be very loose, as can be seen by considering the lattice generated by (1,0), (0,n). But it cannot be further improved in the sense that there exists a global constant c such that there exists an n-dimensional lattice L satisfying \| x\|_2 \geq c {\sqrt{n}}\cdot \left|\det(L)\right|^{1/n}for all x \in L \setminus \{0\}. Furthermore, such lattice can be self-dual. • Even though Minkowski's theorem guarantees a short lattice vector within a certain magnitude bound, finding this vector is in general
a hard computational problem. Finding the vector within a factor guaranteed by Minkowski's bound is referred to as Minkowski's Vector Problem (MVP), and it is known that approximation SVP reduces to it using
transference properties of the dual lattice. The computational problem is also sometimes referred to as HermiteSVP. • The
LLL-basis reduction algorithm can be seen as a weak but efficiently algorithmic version of Minkowski's bound on the shortest vector. This is because a \delta -LLL reduced basis b_1, \ldots, b_n for L has the property that \|b_1\| \leq \left(\frac{1}{ \delta - .25}\right)^{\frac{n-1}{4}} \det(L)^{1/n} ; see these lecture notes of Micciancio for more on this. As explained in, proofs of bounds on the
Hermite constant contain some of the key ideas in the LLL-reduction algorithm.
Applications to number theory Primes that are sums of two squares The difficult implication in
Fermat's theorem on sums of two squares can be proven using Minkowski's bound on the shortest vector.
Theorem: Every
prime with p \equiv 1 \mod 4 can be written as a sum of two
squares. {{math proof | proof = Since 4 \,|\, p - 1 and a is a
quadratic residue modulo a prime p if and only if a^{\frac{p-1}{2}} = 1~(\text{mod}~p) (Euler's Criterion) there is a square root of -1 in \Z / p\Z; choose one and call one representative in \Z for it j. Consider the lattice L defined by the vectors (1, j), (0,p), and let B denote the associated
matrix. The determinant of this lattice is p, whence Minkowski's bound tells us that there is a nonzero x = (x_1, x_2) \in \mathbb{Z}^2 with 0 . We have \|Bx\|^2 = \|(x_1, jx_1 + px_2)\|^2 = x_1^2 + (jx_1 + px_2)^2 and we define the integers a = x_1, b = (jx_1 + px_2). Minkowski's bound tells us that 0 , and simple
modular arithmetic shows that a^2 + b^2 = x_1^2 + (jx_1 + px_2)^2 = 0 \mod p, and thus we conclude that a^2 + b^2 = p. Q.E.D.}} Additionally, the lattice perspective gives a computationally efficient approach to Fermat's theorem on sums of squares: First, recall that finding any nonzero vector with norm less than 2p in L, the lattice of the proof, gives a decomposition of p as a sum of two squares. Such vectors can be found efficiently, for instance using
LLL-algorithm. In particular, if b_1, b_2 is a 3/4 -LLL reduced basis, then, by the property that \|b_1\| \leq (\frac{1}{\delta - .25})^{\frac{n-1}{4}} \text{det}(B)^{1/n}, \|b_1\|^2 \leq \sqrt{2} p . Thus, by running the LLL-lattice basis reduction algorithm with \delta = 3/4 , we obtain a decomposition of p as a sum of squares. Note that because every vector in L has norm squared a multiple of p, the vector returned by the LLL-algorithm in this case is in fact a shortest vector.
Lagrange's four-square theorem Minkowski's theorem is also useful to prove
Lagrange's four-square theorem, which states that every
natural number can be written as the sum of the squares of four natural numbers.
Dirichlet's theorem on simultaneous rational approximation Minkowski's theorem can be used to prove
Dirichlet's theorem on simultaneous rational approximation.
Algebraic number theory Another application of Minkowski's theorem is the result that every class in the
ideal class group of a
number field contains an
integral ideal of
norm not exceeding a certain bound, depending on , called
Minkowski's bound: the finiteness of the
class number of an algebraic number field follows immediately. ==Complexity theory==