Editing Minkowski's theorem (section)

==Applications==

===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  <math display="inline">L</math> be a lattice. Then there is a <math display="inline">x \in L \setminus \{0\}</math> with <math display="inline">  \|x\|_{\infty} \leq \left|\det(L)\right|^{1/n}</math>. In particular, by the standard comparison between  <math display="inline">l_2</math> and <math display="inline">l_{\infty}</math> norms, <math display="inline"> \|x\|_2 \leq \sqrt{n}\, \left|\det(L)\right|^{1/n}</math>.
{{math proof | proof = Let <math display="inline">l = \min \{ \|x\|_{\infty} : x \in L \setminus \{0\} \}</math>, and set  <math display="inline">C = \{ y : \|y\|_{\infty} < l \}</math>. Then <math display="inline"> \text{vol}(C) = (2l)^n</math>. If <math display="inline">(2l)^n > 2^n |d(L)|</math>, then <math display="inline">C</math> contains a non-zero lattice point, which is a contradiction. Thus <math display="inline">  l \leq | d(L)|^{1/n}</math>. Q.E.D.}}
'''Remarks:'''

* The constant in the  <math display="inline">L^2</math> bound can be improved, for instance by taking the open ball of radius <math display="inline"> < l</math> as <math display="inline">C</math> 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 <math display="inline">(1,0), (0,n)</math>. But it cannot be further improved in the sense that there exists a global constant <math>c</math> such that there exists an <math>n</math>-dimensional lattice <math>L</math> satisfying <math>\| x\|_2 \geq c {\sqrt{n}}\cdot \left|\det(L)\right|^{1/n}</math>for all <math>x \in L \setminus \{0\}</math>. Furthermore, such lattice can be self-dual. <ref>{{Cite book |last1=Milnor |first1=John |last2=Husemoller |first2=Dale |date=1973 |title=Symmetric Bilinear Forms |url=http://dx.doi.org/10.1007/978-3-642-88330-9 |pages=46 |doi=10.1007/978-3-642-88330-9|isbn=978-3-642-88332-3 }}</ref>
* Even though Minkowski's theorem guarantees a short lattice vector within a certain magnitude bound, finding this vector is in general [[Lattice problem#Shortest vector problem (SVP)|a hard computational problem]]. Finding the vector within a factor guaranteed by Minkowski's bound is [https://cseweb.ucsd.edu/classes/sp07/cse206a/lec8.pdf referred to as Minkowski's Vector Problem (MVP), and it is known that approximation SVP reduces to it] using [[Dual lattice#Transference theorems|transference properties of the dual lattice.]] The computational problem is also sometimes referred to as HermiteSVP.<ref name="Nguyen 2009 pp. 19–69">{{cite book | last=Nguyen | first=Phong Q. | chapter=Hermite's Constant and Lattice Algorithms | title=The LLL Algorithm | series=Information Security and Cryptography | publisher=Springer Berlin Heidelberg | publication-place=Berlin, Heidelberg | year=2009 | isbn=978-3-642-02294-4 | issn=1619-7100 | doi=10.1007/978-3-642-02295-1_2 | pages=19–69}}</ref>
* The [[Lenstra–Lenstra–Lovász lattice basis reduction algorithm|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 <math display="inline"> \delta </math>-LLL reduced basis <math display="inline"> b_1, \ldots, b_n </math> for <math display="inline"> L </math> has the property that <math display="inline"> \|b_1\| \leq \left(\frac{1}{ \delta - .25}\right)^{\frac{n-1}{4}} \det(L)^{1/n} </math>; see these [http://cseweb.ucsd.edu/classes/sp14/cse206A-a/lec5.pdf lecture notes of Micciancio] for more on this. As explained in,<ref name="Nguyen 2009 pp. 19–69"/> 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 number|prime]] with <math display="inline">p \equiv 1 \mod 4</math> can be written as a sum of two [[square number|squares]].

{{math proof | proof = Since <math display="inline">4 \,|\, p - 1</math> and <math display="infline">a</math> is a [[quadratic residue]] modulo a prime <math display="inline">p</math> if and only if <math display="infline"> a^{\frac{p-1}{2}} = 1~(\text{mod}~p)</math> (Euler's Criterion) there is a square root of <math display="inline">-1</math> in <math display="inline">\Z / p\Z</math>; choose one and call one representative in <math display="inline">\Z</math> for it <math display="inline">j</math>. Consider the lattice <math display="inline">L</math> defined by the vectors <math display="inline">(1, j), (0,p)</math>, and let <math display="inline">B</math> denote the associated [[matrix (mathematics)|matrix]]. The determinant of this lattice is <math display="inline">p</math>, whence Minkowski's bound tells us that there is a nonzero <math display="inline">x = (x_1, x_2) \in \mathbb{Z}^2</math> with <math display="inline">0 < \|Bx\|_2^2 < 2p</math>. We have <math display="inline">\|Bx\|^2 = \|(x_1, jx_1 + px_2)\|^2 = x_1^2 + (jx_1 + px_2)^2</math> and we define the integers <math display="inline">a = x_1, b = (jx_1 + px_2)</math>. Minkowski's bound tells us that <math display="inline">0 < a^2 + b^2 < 2p</math>, and simple [[modular arithmetic]] shows that <math display="inline">a^2 + b^2 = x_1^2 + (jx_1 + px_2)^2 = 0 \mod p</math>, and thus we conclude that <math display="inline">a^2 + b^2 = p</math>. Q.E.D.}}

Additionally, the lattice perspective gives a computationally efficient approach to Fermat's theorem on sums of squares:
{{Collapse top|title= Algorithm}} First, recall that finding any nonzero vector with norm less than <math display="inline">2p</math> in <math display="inline">L</math>, the lattice of the proof, gives a decomposition of <math display="inline">p</math> as a sum of two squares. Such vectors can be found efficiently, for instance using [[Lenstra–Lenstra–Lovász lattice basis reduction algorithm|LLL-algorithm]]. In particular, if <math display="inline">b_1, b_2</math> is a <math display="inline"> 3/4 </math>-LLL reduced basis, then, by the property that <math display="inline">\|b_1\| \leq (\frac{1}{\delta - .25})^{\frac{n-1}{4}} \text{det}(B)^{1/n}</math>, <math display="inline">\|b_1\|^2 \leq \sqrt{2} p < 2p</math>. Thus, by running the LLL-lattice basis reduction algorithm with <math display="inline"> \delta = 3/4 </math>, we obtain a decomposition of <math display="inline">p</math> as a sum of squares. Note that because every vector in <math display="inline">L</math> has norm squared a multiple of <math display="inline">p</math>, the vector returned by the LLL-algorithm in this case is in fact a shortest vector.
{{Collapse bottom}}

====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 approximation theorem|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]] {{math|''K''}} contains an [[integral ideal]] of [[field norm|norm]] not exceeding a certain bound, depending on {{math|''K''}}, called [[Minkowski's bound]]: the finiteness of the [[Class number (number theory)|class number]] of an algebraic number field follows immediately.