Misplaced Pages

Minkowski's second theorem

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
(Redirected from Successive minima)

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 R. The gauge or distance Minkowski functional g attached to K is defined by g ( x ) = inf { λ ∈ R : x ∈ λ K } . {\displaystyle g(x)=\inf \left\{\lambda \in \mathbb {R} :x\in \lambda K\right\}.}

Conversely, given a norm g on R we define K to be K = { x ∈ R n : g ( x ) ≤ 1 } . {\displaystyle K=\left\{x\in \mathbb {R} ^{n}:g(x)\leq 1\right\}.}

Let Γ be a lattice in R. 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 ≤ λ2 ≤ ... ≤ λn < ∞.

Statement

The successive minima satisfy 2 n n ! vol ⁡ ( R n / Γ ) ≤ λ 1 λ 2 ⋯ λ n vol ⁡ ( K ) ≤ 2 n vol ⁡ ( R n / Γ ) . {\displaystyle {\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 b1, b2, ..., bn can be defined by g(bj) = λj.

The lower bound is proved by considering the convex polytope 2n with vertices at ±bj/ λj, which has an interior enclosed by K and a volume which is 2/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-simplices with lattice point vectors).

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

References

  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
Categories: