Editing Minkowski's theorem

{{short description|Every symmetric convex set in R^n with volume > 2^n contains a non-zero integer point}}
{{more footnotes|date=February 2017}}
[[File:Mconvexe.png|thumb|A set in {{math|{{bug workaround|ℝ}}<sup>2</sup>}} satisfying the hypotheses of Minkowski's theorem.]]

In [[mathematics]], '''Minkowski's theorem''' is the statement that every [[convex set]] in <math>\mathbb{R}^n</math> which is symmetric with respect to the origin and which has [[volume]] greater than <math>2^n</math> contains a non-zero [[integer point]] (meaning a point in <math>\Z^n</math> that is not the origin). The theorem was [[mathematical proof|proved]] by [[Hermann Minkowski]] in 1889 and became the foundation of the branch of [[number theory]] called the [[geometry of numbers]]. It can be extended from the integers to any [[Lattice (group)|lattice]] <math>L</math> and to any symmetric convex set with volume greater than <math>2^n\,d(L)</math>, where <math>d(L)</math> denotes the [[covolume]] of the lattice (the [[absolute value]] of the [[determinant]] of any of its bases).

==Formulation==
Suppose that {{math|''L''}} is a [[lattice (group)|lattice]] of [[Lattice (group)#Dividing space according to a lattice|determinant]] {{math|d(''L'')}} in the {{math|''n''}}-[[dimension (vector space)|dimensional]] [[real number|real]] [[vector space]] <math>\mathbb{R}^n</math> and {{math|''S''}} is a [[convex set|convex subset]] of <math>\mathbb{R}^n</math> that is symmetric with respect to the origin, meaning that if {{math|''x''}} is in {{math|''S''}} then {{math|−''x''}} is also in {{math|''S''}}. Minkowski's theorem states that if the volume of {{math|''S''}} is strictly greater than {{math|2<sup>''n''</sup> d(''L'')}}, then {{math|''S''}} must contain at least one lattice point other than the origin. (Since the set {{math|''S''}} is symmetric, it would then contain at least three lattice points: the origin 0 and a pair of points {{math|±&hairsp;''x''}}, where {{math|''x'' ∈ ''L'' \ 0}}.)

==Example==
The simplest example of a lattice is the [[integer lattice]] <math>\mathbb{Z}^n</math> of all points with [[integer]] coefficients; its determinant is 1. For {{math|''n'' {{=}} 2}}, the theorem claims that a convex figure in the [[Euclidean plane]] symmetric about the [[Origin (mathematics)|origin]] and with [[area]] greater than 4 encloses at least one lattice point in addition to the origin. The area bound is [[Mathematical jargon#sharp|sharp]]: if {{math|''S''}} is the interior of the square with vertices {{math|(±1, ±1)}} then {{math|''S''}} is symmetric and convex, and has area 4, but the only lattice point it contains is the origin. This example, showing that the bound of the theorem is sharp, generalizes to [[hypercube]]s in every dimension {{math|''n''}}.

==Proof==
The following argument proves Minkowski's theorem for the specific case of <math>L = \mathbb{Z}^2.</math>

'''Proof of the <math display = "inline"> \mathbb{Z}^2 </math> case:''' Consider the map
:<math>f: S \to \mathbb{R}^2/2L, \qquad (x,y) \mapsto (x \bmod 2, y \bmod 2)</math>
Intuitively, this map cuts the plane into 2 by 2 squares, then stacks the squares on top of each other. Clearly {{math|''f''&thinsp;(''S'')}} has area less than or equal to 4, because this set lies within a 2 by 2 square. Assume for a [[proof by contradiction|contradiction]] that {{math|''f''}} could be [[injective]], which means the pieces of {{math|''S''}} cut out by the squares stack up in a non-overlapping way. Because {{math|''f''}} is locally area-preserving, this non-overlapping property would make it area-preserving for all of {{math|''S''}}, so the area of {{math|''f''&thinsp;(''S'')}} would be the same as that of {{math|''S''}}, which is greater than 4. That is not the case, so the assumption must be false: {{math|''f''}} is not injective, meaning that there exist at least two distinct points {{math|''p''<sub>1</sub>, ''p''<sub>2</sub>}} in {{math|''S''}} that are mapped by {{math|''f''}} to the same point: {{math|''f''&thinsp;(''p''<sub>1</sub>) {{=}} ''f''&thinsp;(''p''<sub>2</sub>)}}.

Because of the way {{math|''f''}} was defined, the only way that {{math|''f''&thinsp;(''p''<sub>1</sub>)}} can equal {{math|''f''&thinsp;(''p''<sub>2</sub>)}} is for {{math|''p''<sub>2</sub>}}
to equal {{math|''p''<sub>1</sub> + (2''i'', 2''j'')}} for some integers {{math|''i''}} and {{math|''j''}}, not both zero.
That is, the coordinates of the two points differ by two [[parity (mathematics)|even]] integers. 
Since {{math|''S''}} is symmetric about the origin, {{math|−''p''<sub>1</sub>}} is also a point in {{math|''S''}}. Since {{math|''S''}} is convex, the line segment between {{math|−''p''<sub>1</sub>}} and {{math|''p''<sub>2</sub>}} lies entirely in {{math|''S''}}, and in particular the midpoint of that segment lies in {{math|''S''}}. In other words,
:<math>\tfrac{1}{2}\left(-p_1 + p_2\right) = \tfrac{1}{2}\left(-p_1 + p_1 + (2i, 2j)\right) = (i, j)</math>
is a point in {{math|''S''}}. This point {{math|(''i'', ''j'')}} is an integer point, and is not the origin since {{math|''i''}} and {{math|''j''}} are not both zero.
Therefore, {{math|''S''}} contains a nonzero integer point.

'''Remarks:'''  
* The argument above proves the theorem that any set of volume <math display = "inline"> >\!\det(L)</math> contains two distinct points that differ by a lattice vector. This is a special case of [[Blichfeldt's theorem]].<ref>{{cite book
 | last1 = Olds | first1 = C. D. | author1-link = Carl D. Olds
 | last2 = Lax | first2 = Anneli | author2-link = Anneli Cahn Lax
 | last3 = Davidoff | first3 = Giuliana P. | author3-link = Giuliana Davidoff 
 | contribution = Chapter 9: A new principle in the geometry of numbers
 | isbn = 0-88385-643-3
 | mr = 1817689
 | page = 120
 | publisher = Mathematical Association of America, Washington, DC
 | series = Anneli Lax New Mathematical Library
 | title = The Geometry of Numbers
 | title-link = The Geometry of Numbers
 | volume = 41
 | year = 2000}}</ref>
* The argument above highlights that the term <math display = "inline">2^n \det(L)</math> is the covolume of the lattice <math display = "inline">2L</math>.
* To obtain a proof for general lattices, it suffices to prove Minkowski's theorem only for <math display = "inline">\mathbb{Z}^n</math>; this is because every full-rank lattice can be written as <math display = "inline">B\mathbb{Z}^n</math> for some [[linear transformation]] <math display = "inline">B</math>, and the properties of being convex and symmetric about the origin are preserved by linear transformations, while the covolume of <math display = "inline">B\mathbb{Z}^n</math> is <math display = "inline">|\!\det(B)|</math> and volume of a body scales by exactly <math display = "inline">\frac{1}{\det(B)}</math> under an application of <math display = "inline">B^{-1}</math>.

==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.

==Complexity theory==

The complexity of finding the point guaranteed by Minkowski's theorem, or the closely related Blichfeldt's theorem, have been studied from the perspective of [[TFNP]] search problems. In particular, it is known that a computational analogue of [[Blichfeldt's theorem]], a [[corollary]] of the proof of Minkowski's theorem, is PPP-complete.<ref name="Cryptology ePrint Archive: Report 2018/778 2018">{{cite web | title=PPP-Completeness with Connections to Cryptography | website=Cryptology ePrint Archive: Report 2018/778 | date=2018-08-15 | url=https://eprint.iacr.org/2018/778 | access-date=2020-09-13}}</ref> It is also known that the computational analogue of Minkowski's theorem is in the class PPP, and it was [[conjecture]]d to be PPP complete.<ref name="Information Processing Letters 2019 pp. 48–52">{{cite journal | title=Reductions in PPP | journal=Information Processing Letters | volume=145 | date=2019-05-01 | issn=0020-0190 | doi=10.1016/j.ipl.2018.12.009 | pages=48–52 | url=https://www.sciencedirect.com/science/article/abs/pii/S0020019019300018 | access-date=2020-09-13| last1=Ban | first1=Frank | last2=Jain | first2=Kamal | last3=Papadimitriou | first3=Christos H. | last4=Psomas | first4=Christos-Alexandros | last5=Rubinstein | first5=Aviad | s2cid=71715876 }}</ref>

==See also==
* [[Danzer set]]
* [[Pick's theorem]]
* [[Dirichlet's unit theorem]]
* [[Minkowski's second theorem]]
* [[Ehrhart's volume conjecture]]

==References==
{{Reflist}}

==Further reading==
{{refbegin}}
*{{Cite book|
authorlink=Enrico Bombieri |first1=Enrico |last1=Bombieri |first2=Walter |last2=Gubler
|title=Heights in Diophantine Geometry
|publisher=Cambridge University Press |isbn=9780521712293 |url=https://books.google.com/books?id=3ATnwmGegvsC
|year=2006}}
*{{cite book |author-link=J. W. S. Cassels |first=J.W.S. |last=Cassels |title=An Introduction to the Geometry of Numbers |url=https://books.google.com/books?id=XyVrCQAAQBAJ |date=2012 |series=Classics in Mathematics |orig-year=1959 |publisher=Springer |isbn=978-3-642-62035-5}}
*{{cite book |author-link=John Horton Conway |author2-link=N. J. A. Sloane |first1=John |last1=Conway |first2=Neil J. A. |last2=Sloane |title=Sphere Packings, Lattices and Groups |url=https://books.google.com/books?id=5-UlBQAAQBAJ |date=29 June 2013 |publisher=Springer |isbn=978-1-4757-6568-7 |edition=3rd |orig-year=1998}}
<!-- *R. J. Gardner, ''Geometric tomography,'' Cambridge University Press, New York, 1995. Second edition: 2006. -->
*{{Cite book
  | last = Hancock |first=Harris
  | title = Development of the Minkowski Geometry of Numbers
  | orig-year = 1939 |year=2005
  | publisher = Dover Publications |isbn=9780486446400}}
*{{cite book |author-link=Edmund Hlawka |first1=Edmund |last1=Hlawka |first2=Johannes |last2=Schoißengeier |first3=Rudolf |last3=Taschner |title=Geometric and Analytic Number Theory |url=https://books.google.com/books?id=-vTuCAAAQBAJ |date=2012 |publisher=Springer |isbn=978-3-642-75306-0 |orig-year=1991}}
*{{cite book |author-link=C. G. Lekkerkerker |first=C.G. |last=Lekkerkerker |title=Geometry of Numbers |url=https://books.google.com/books?id=XZ7iBQAAQBAJ |date=2014 |publisher=Elsevier |isbn=978-1-4832-5927-7 |orig-year=1969}}
*{{cite book |author-link=Wolfgang M. Schmidt |first=Wolfgang M. |last=Schmidt |title=Diophantine Approximation |publisher=Springer |series=Lecture Notes in Mathematics |volume=785 |year=1980  |doi=10.1007/978-3-540-38645-2 |isbn=978-3-540-38645-2 }} ([1996 with minor corrections])
* [[Wolfgang M. Schmidt]].''Diophantine approximations and Diophantine equations'', Lecture Notes in Mathematics, Springer Verlag 2000.
*{{Cite book
  | last = Siegel |first=Carl Ludwig
  | author-link = Carl Ludwig Siegel
  | title = Lectures on the Geometry of Numbers
  | orig-year = 1989 |year=2013 |url=https://books.google.com/books?id=dyH4CAAAQBAJ |isbn=9783662082874
  | publisher = Springer-Verlag}}
*{{cite book |first=Rolf |last=Schneider |title=Convex Bodies: The Brunn-Minkowski Theory |url=https://archive.org/details/convexbodiesbrun0000schn |url-access=registration |date=1993 |publisher=Cambridge University Press |isbn=978-0-521-35220-8}}
{{refend}}

==External links==
*Stevenhagen, Peter. [http://websites.math.leidenuniv.nl/algebra/ant.pdf ''Number Rings''.]
*{{springer|title=Minkowski theorem|id=M/m064090|last=Malyshev|first=A.V.}}
*{{Springer|id=G/g044350|title=Geometry of numbers}} <!-- Hazewinkel -->

{{DEFAULTSORT:Minkowski's Theorem}}
[[Category:Geometry of numbers]]
[[Category:Convex analysis]]
[[Category:Theorems in number theory]]
[[Category:Articles containing proofs]]
[[Category:Hermann Minkowski]]