Minkowski's second theorem

In mathematics, Minkowski's second theorem is a result in the geometry of numbers about the values taken by a norm on a lattice and the volume of its fundamental cell.

Setting

Let $K$ be a closed convex centrally symmetric body of positive finite volume in $n$ -dimensional Euclidean space $ℝ n$ . The gauge[1] or distance[2][3] Minkowski functional $g$ attached to $K$ is defined by

g(x)=\inf \left\{\lambda \in \mathbb {R} :x\in \lambda K\right\}.

Conversely, given a norm $g$ on $ℝ n$ we define $K$ to be

{\textstyle K=\left\{x\in \mathbb {R} ^{n}:g(x)\leq 1\right\}.}

Let $Γ$ be a lattice in $ℝ n$ . The successive minima of $K$ or $g$ on $Γ$ are defined by setting the $k$ th successive minimum $λ k$ to be the infimum of the numbers $λ$ such that $λK$ contains $k$ linearly-independent vectors of $Γ$ . We have $0 < λ 1 \leq λ 2 \leq ... \leq λ n < \infty$ .

Statement

The successive minima satisfy[4][5][6]

{\frac {2^{n}}{n!}}\operatorname {vol} \left(\mathbb {R} ^{n}/\Gamma \right)\leq \lambda _{1}\lambda _{2}\cdots \lambda _{n}\operatorname {vol} (K)\leq 2^{n}\operatorname {vol} \left(\mathbb {R} ^{n}/\Gamma \right).

Proof

A basis of linearly independent lattice vectors $b 1, b 2, ... b n$ can be defined by $g(b j) = λ j$ .

The lower bound is proved by considering the convex polytope $2n$ with vertices at $\pmb j / λ j$ , which has an interior enclosed by $K$ and a volume which is $2 n /n!λ 1 λ 2 ...λ n$ times an integer multiple of a primitive cell of the lattice (as seen by scaling the polytope by $λ j$ along each basis vector to obtain $2 n$ $n$ -simplices with lattice point vectors).

To prove the upper bound, consider functions $f j (x)$ sending points $x$ in ${\textstyle K}$ to the centroid of the subset of points in ${\textstyle K}$ that can be written as ${\textstyle x+\sum _{i=1}^{j-1}a_{i}b_{i}}$ for some real numbers ${\textstyle a_{i}}$ . Then the coordinate transform ${\textstyle x'=h(x)=\sum _{i=1}^{n}(\lambda _{i}-\lambda _{i-1})f_{i}(x)/2}$ has a Jacobian determinant ${\textstyle J=\lambda _{1}\lambda _{2}\ldots \lambda _{n}/2^{n}}$ . If ${\textstyle p}$ and ${\textstyle q}$ are in the interior of ${\textstyle K}$ and ${\textstyle p-q=\sum _{i=1}^{k}a_{i}b_{i}}$ (with ${\textstyle a_{k}\neq 0}$ ) then ${\textstyle (h(p)-h(q))=\sum _{i=0}^{k}c_{i}b_{i}\in \lambda _{k}K}$ with ${\textstyle c_{k}=\lambda _{k}a_{k}/2}$ , where the inclusion in ${\textstyle \lambda _{k}K}$ (specifically the interior of ${\textstyle \lambda _{k}K}$ ) is due to convexity and symmetry. But lattice points in the interior of ${\textstyle \lambda _{k}K}$ are, by definition of ${\textstyle \lambda _{k}}$ , always expressible as a linear combination of ${\textstyle b_{1},b_{2},\ldots b_{k-1}}$ , so any two distinct points of ${\textstyle K'=h(K)=\lbrace x'|h(x)=x'\rbrace }$ cannot be separated by a lattice vector. Therefore, ${\textstyle K'}$ must be enclosed in a primitive cell of the lattice (which has volume ${\textstyle {\text{vol}}(\mathbb {R} ^{n}/\Gamma )}$ ) , and consequently ${\textstyle {\text{vol}}(K)/J={\text{vol}}(K')\leq {\text{vol}}(\mathbb {R} ^{n}/\Gamma )}$ .

gollark: `_Whatever` is quite ugly.

gollark: Evidently, C needs better extension mechanisms.

gollark: I'm not sure how you could consider that syntax okay.

gollark: This is why ALL are to utilize zig.

gollark: ```c#include <sys/socket.h>#include <sys/types.h> #include <netinet/in.h>#include <stdio.h>#include <string.h>#include <sys/select.h>#include <fcntl.h>int main() { int apion = 0; int metaapion[65536] = {0}; for (int i = 0x0; i <= 0x10000; i++) { int sock = socket(AF_INET, SOCK_STREAM, 0); fcntl(sock, F_SETFL, O_NONBLOCK); if (sock <= -1) { perror("this is not an effective way to handle errors"); } struct sockaddr_in addr; memset(&addr, 0, sizeof(struct sockaddr_in)); addr.sin_family = AF_INET; addr.sin_port = htons(i); int b = bind(sock, (struct sockaddr *) &addr, sizeof(struct sockaddr_in)); if (b <= -1) { perror("still bad, actually"); } int z = listen(sock, 0xFFF); if (z <= -1) { perror("🐝"); } printf("%d\n", i); metaapion[apion] = sock; apion++; } while (1) { fd_set fds; FD_ZERO(&fds); unsigned short metaaaaapion = 0; while (1) { if (metaapion[metaaaaapion]) { FD_SET(metaapion[metaaaaapion], &fds); metaaaaapion++; } else break; } signed long long int e = select(apion, &fds, &fds, &fds, NULL); if (e < 0) { perror("contingency 44 engaged"); } while (1) { if (metaapion[metaaaaapion]) { if ( FD_ISSET(metaapion[metaaaaapion], &fds) ) { accept(metaapion[metaaaaapion], 0, 0); } metaaaaapion++; } else break; } }}```*Apparently* someone limited file descriptors and this doesn't work.

References

Siegel (1989) p.6
Cassels (1957) p.154
Cassels (1971) p.103
Cassels (1957) p.156
Cassels (1971) p.203
Siegel (1989) p.57

Cassels, J. W. S. (1957). An introduction to Diophantine approximation. Cambridge Tracts in Mathematics and Mathematical Physics. 45. Cambridge University Press. Zbl 0077.04801.
Cassels, J. W. S. (1997). An Introduction to the Geometry of Numbers. Classics in Mathematics (Reprint of 1971 ed.). Springer-Verlag. ISBN 978-3-540-61788-4.
Nathanson, Melvyn B. (1996). Additive Number Theory: Inverse Problems and the Geometry of Sumsets. Graduate Texts in Mathematics. 165. Springer-Verlag. pp. 180–185. ISBN 0-387-94655-1. Zbl 0859.11003.
Schmidt, Wolfgang M. (1996). Diophantine approximations and Diophantine equations. Lecture Notes in Mathematics. 1467 (2nd ed.). Springer-Verlag. p. 6. ISBN 3-540-54058-X. Zbl 0754.11020.
Siegel, Carl Ludwig (1989). Komaravolu S. Chandrasekharan (ed.). Lectures on the Geometry of Numbers. Springer-Verlag. ISBN 3-540-50629-2. Zbl 0691.10021.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Siegel (1989) p.6

[2] Cassels (1957) p.154

[3] Cassels (1971) p.103

[4] Cassels (1957) p.156

[5] Cassels (1971) p.203

[6] Siegel (1989) p.57