Minkowski定理

Minkowski Theorem

Minkowski Theorem 1

若多面体 \(\mathrm{S}\) 的体积 \(\operatorname{Vol}(S)>\operatorname{Vol}(P)\), 则 \(\mathrm{S}\) 中必然存在两点 \(\mathrm{x}, \mathrm{y}\) 满足 \(x \neq y, x-y \in L\)

证明：首先, 我们可以把 \(S\) 进行分割, 分割方法为 \[ S=\cup_{l \in L}((P+l) \cap S)=(P \cap S) \cap S_1 \cap \ldots S_k \]

之后把所有 \(\mathrm{S}\) 中不属于 \(P\) 的部分平移到 \(\mathrm{P}\) 中, 也就 \(S_i\) 若位于 \(P+l_i\), 则将其平移为 \(S_i-l=S_i^{\prime}\), 这样经过处理之后, \(\mathrm{S}\) 的所有部分都位于P中, 由于 \(\operatorname{Vol}(S)>\operatorname{Vol}(P)\), 所以有 \(\operatorname{Vol}(S \cap P)+\sum \operatorname{Vol}\left(S_i^{\prime}\right)>\operatorname{Vol}(P)\), 这意味着, \(S \cap P, S_i^{\prime}\) 中必然不可能两两不想交。

这就意味着, 存在 \(\mathrm{s}\) 属于 (为简单设 \(S_0=S \cap P\) ) , \(S_i^{\prime}, S_j^{\prime}(0 \leq i<j \leq k\) ) , 则意味着平移之前, \(\mathrm{S}\) 中有两点 (分别是 \(s+l_i, s+l_j\) ) 位于 \(S_i, S_j\) 中, 则令 \(x=s+l_i, y=s+l_j\), 则 \(x-y=l_i-l_j \in L, x \neq y(i \neq j)\)

闵科夫斯基格点定理: 按照上述定义, 凸体 \(S\) 关于原点中心对称, 且体积 \(\operatorname{Vol}(S)>\operatorname{Vol}(P) * 2^n\) ，则必然存在除了原点之外的格点 \(\mathrm{s}\) 满足 \(s \in L, s \in S\)

证明：考虑 \((1 / 2) S:=\{x \mid x=y / 2, y \in S\}\) ，显然其体积为 \(\operatorname{Vol}(S) / 2^n>\operatorname{Vol}(P)\) ，则根据引理，存在点 \(\mathrm{x}, \mathrm{y}\) 满足 \(x, y \in S / 2, x \neq y, x-y \in L\) 则有 \(2 x, 2 y \in S\), 根据中心对称, 有 \(-2 y \in S\), 再根据凸体性质, 取 \(=0.5\), 则有 \(0.5 *(2 x)+(1-0.5) *(2 y)=x-y \in S\)

又因为$ x-y L\(，因此\)S$中存在格中的点。

Corollary 1.1 \[ \lambda_1(\mathcal{L}) \leq \sqrt{n}(\operatorname{det} \mathcal{L})^{\frac{1}{n}} \]

Proof. We give a proof of the corollary using the following two facts:

• A ball of radius \(>\sqrt{n}(\operatorname{det} \mathcal{L})^{\frac{1}{n}}\) is convex and centrally symmetric.
• \(B\left(0, \sqrt{n}(\operatorname{det} \mathcal{L})^{\frac{1}{n}}\right) \supset\) a cube of side length \(2(\operatorname{det} \mathcal{L})^{\frac{1}{n}}\), since

\[ \operatorname{dist}((1, \ldots, 1),(0, \ldots, 0))=\sqrt{n} \text {. } \]

It follows that \[ \operatorname{vol}\left(B\left(0, \sqrt{n}(\operatorname{det} \mathcal{L})^{\frac{1}{n}}\right)\right)>2^n \operatorname{det} \mathcal{L} . \]

Remark 1.2 We could obtain a more refined inequality if we use the exact formula for \(\operatorname{vol}(B(0, R))\). Choose \(R\) such that \(\operatorname{vol}(B(0, R))=2^n \operatorname{det} \mathcal{L}\). Then \(\lambda_1(\mathcal{L}) \leq R\).

Minkowski Theorem 2
\[ \left(\prod_{i=1}^n \lambda_i(\mathcal{L})\right)^{\frac{1}{n}} \leq \sqrt{n}(\operatorname{det} \mathcal{L})^{\frac{1}{n}} \] Proof. We may assume \(\left\|\mathbf{b}_i\right\|=\lambda_i(\mathcal{L})\) for \(i=1, \ldots, n\), and consider a lattice generated by \(\mathbf{b}_1, \ldots, \mathbf{b}_n\), possibly a sublattice of \(\mathcal{L}\)​. \[ T:=\left\{\mathbf{y} \in \mathbb{R}^n: \sum_{i=1}^n\left(\frac{\left\langle\mathbf{y}, \widetilde{\mathbf{b}}_i\right\rangle}{\left\|\widetilde{\mathbf{b}}_i\right\| \lambda_i}\right)^2<1\right\} . \]

Claim: The ellipsoid \(T\) does not contain any nonzero lattice point. Let \(0 \neq \mathbf{y} \in \mathcal{L}\), and \(1 \leq k \leq n\) maximal such that \[ \lambda_{k+1}(\mathcal{L}) \not\ge \|\mathbf{y}\| \geq \lambda_k(\mathcal{L}) . \] We claim \(\mathbf{y} \in \operatorname{span}\left\{\mathbf{b}_1, \ldots, \mathbf{b}_k\right\}=\operatorname{span}\left\{\tilde{\mathbf{b}}_1, \ldots, \tilde{\mathbf{b}}_k\right\}\). If not, \(\mathbf{b}_1, \ldots, \mathbf{b}_k, \mathbf{y}\) are \(k+1\) linearly independent and their norms are less than \(\lambda_{k+1}\), a contradiction. Hence, \[ \begin{aligned} \sum_{i=1}^n\left(\frac{\left\langle\mathbf{y}, \tilde{\mathbf{b}}_i\right\rangle}{\left\|\tilde{\mathbf{b}}_i\right\| \lambda_i}\right)^2 & =\sum_{i=1}^k\left(\frac{\left\langle\mathbf{y}, \tilde{\mathbf{b}}_i\right\rangle}{\left\|\tilde{\mathbf{b}}_i\right\| \lambda_i}\right)^2 \\ & \geq \sum_{i=1}^k \frac{1}{\lambda_k^2}\left(\frac{\left\langle\mathbf{y}, \tilde{\mathbf{b}}_i\right\rangle}{\left\|\tilde{\mathbf{b}}_i\right\|}\right)^2 \\ & =\frac{\|\mathbf{y}\|^2}{\lambda_k^2} \geq 1 \end{aligned} \] so \(\mathbf{y} \notin T\), i.e., \(T\) does not contain any nonzero lattice vector. Hence, \[ 2^n \operatorname{det}(\mathcal{L}) \geq \operatorname{vol}(T)=\left(\prod_{i=1}^n \lambda_i\right) \operatorname{vol}(B(0: 1)) \geq\left(\prod_{i=1}^n \lambda_i\right)\left(\frac{2}{\sqrt{n}}\right)^n \]

So

\[ \left(\prod_{i=1}^n \lambda_i\right)^{\frac{1}{n}} \leq \sqrt{n}(\operatorname{det} \mathcal{L})^{\frac{1}{n}} \]