Some Thoughts on Lattice Class1

- 有商就有格 -

——我的油腻数学

这次的思考来源于格密码课程第一个作业的第一题：

讨论 $l_p$ 下的Minkowski定理。

首先我们回顾一下Minkowski定理的内容：

设 $L$ 是 $\mathbb{R}^n$ 中的一个格子，$\det(L)$ 是 $L$ 的行列式，$B$ 是 $\mathbb{R}^n$ 中一个对称、凸、包含原点的集合。如果 $\text{vol}(B) > 2^n \cdot \det(L)$，则 $B$ 中至少存在一个非零的格点。

Minkowski定理的原始版本与证明

$\text{Blichfeldt's Theorem}\rightarrow \text{Minkowski's Convex Body Theorem} \rightarrow \text{Minkowski's First Theorem}$

Blichfeldt’s Theorem ：

对任意满秩格 $\Lambda \subseteq \mathbb{R}^n$，和一个（可测）集 $S \subseteq \mathbb{R}^n$，如果 $\text{vol}(S) > \det(\Lambda)$，则 $\exists\ z_1\neq z_2 \in S$ 使得 $z_1 - z_2 \in \Lambda$。

证明思路：每一个格子都可以拆分成一个格基本体阵列，我们将这些格基本体都平移到原点叠起来，那么体积大于 $\det(\Lambda)$ 的集合 $S$ 就必然有两个点同时落在叠加后格基本体内的同一个位置，这两个点差的就恰好是格中的向量。

z₂

z₁

z

→v

1. Init State 2. Fold 3. Stick 4. Return 5. Get It

证明：设 $B$ 是 $\Lambda$ 的一个基。随着 $x$ 在 $\Lambda$ 中变化，集合 $x + \mathcal{P}(B) := \{x+y | y \in \mathcal{P}(B)\}$ 形成了 $\mathbb{R}^n$ 的一个划分。现在定义 $S_x = S \cap (x + \mathcal{P}(B))$。由于 $S = \bigcup_{x \in \Lambda} S_x$，我们得出 $\text{vol}(S) = \sum_{x \in \Lambda} \text{vol}(S_x)$。我们定义 $S_x' = S_x - x$。那么 $S_x' \subseteq \mathcal{P}(B)$ 并且 $\text{vol}(S_x') = \text{vol}(S_x)$，我们得到：

$\text{vol}(S) = \sum_{x \in \Lambda} \text{vol}(S_x) = \sum_{x \in \Lambda} \text{vol}(S_x') > \text{vol}(\mathcal{P}(B)).$

因此，必须存在一些 $x, y \in \Lambda$，$x \neq y$，使得 $S_x' \cap S_y' \neq \emptyset$。设 $z$ 是 $S_x' \cap S_y'$ 中的一个点。那么 $z + x$ 在 $S_x$ 中，$z + y$ 在 $S_y$ 中，并且 $(z + x) - (z + y) = x - y$ 在 $\Lambda$ 中，证明完成。$\square$

备注：

1. 上述定理对于任何可测集 $S$ 都成立，不要求 $S$ 是凸的或者对称的。
2. 这是一个非常一般的结果，它不依赖于任何特定的范数或者距离函数。它仅仅依赖于集合的体积和格子的行列式。

Minkowski’s Convex Body Theorem ：

设 $\Lambda$ 是 $\mathbb{R}^n$ 中的一个满秩格，$B$ 是 $\mathbb{R}^n$ 中一个中心对称凸集合$S$。若 $\text{vol}(S) > 2^n \cdot \det(\Lambda)$，则 $S$ 中至少存在一个非零的格点。

定义回顾：

• 集合 $S$ 是中心对称的（centrally-symmetric），如果对于任意 $x \in S$，都有 $-x \in S$；
• 集合 $S$ 是凸的（convex），如果对于任意 $x, y \in S$ 和任意 $\lambda \in [0,1]$，都有 $\lambda x + (1-\lambda)y \in S$。

证明思路：Blichfeldt 定理只是构造出了一个格向量，那么我们再什么条件下可以进一步得到一个具体的格点呢？Minkowski’s Convex Body Theorem 就是给出了一个充分条件：当集合 $S$ 是中心对称且凸的，并且体积足够大时，我们就可以保证存在一个非零的格点。我们来还原一下这个思维过程：

0

S

Ŝ

z₁

z₂

2z₁

2z₂

-2z₂

z₁ - z₂

1. Init State 1. S → Ŝ 2. Blichfeldt 3. Usage of Symmetry 4. Usage of Convexity

• Blichfeldt: $\exists\ z_1\neq z_2 \in S$ s.t. $z_1 - z_2 \in \Lambda$;
• We want: $z_1 - z_2 \in S$;
• Make it simple: Convexity: $z_1 - z_2 = 2 \cdot \dfrac{z_1 + z_2}{2} - z_1 - z_2$;
• Symmetry: $-z_1, -z_2 \in S$.
• Combine them together: Minkowski Convex Body condition

证明：
定义 $\hat{S} = \frac{1}{2}S = \{x \mid 2x \in S\}$。则

$\text{vol}(\hat{S}) = 2^{-n}\text{vol}(S) > \det(\Lambda).$

根据 Blichfeldt 定理，存在两点 $z_1, z_2 \in \hat{S}$ 使得 $z_1 - z_2 \in \Lambda$ 是一个非零格点。

根据 $\hat{S}$ 的定义，我们有 $2z_1 \in S$ 且 $2z_2 \in S$。

由于 $S$ 是中心对称的，由 $2z_2 \in S$ 可得 $-2z_2 \in S$。

最后，由于 $S$ 是凸的，连接 $2z_1$ 和 $-2z_2$ 的线段完全包含在 $S$ 中，特别地，中点也在 $S$ 中：

$\frac{2z_1 + (-2z_2)}{2} = z_1 - z_2 \in S.$

因此，$z_1 - z_2$ 就是 $S$ 中的一个非零格点。$\square$

备注：

1. 这个定理中的常数 $2^n$ 是紧的（tight），不能改进。例如对于立方体 $[-1,1]^n$，其体积为 $2^n$，内部不含非零整数点。
2. 如果去掉"中心对称"或"凸"任一条件，定理不再成立。
3. Minkowski’s Convex Body Theorem 也是范数选择无关的。

Minkowski’s First Theorem ：

对任意$n$秩满秩格 $\Lambda$，有：

$\lambda_1(\Lambda) \leq \sqrt{n} \cdot \det(\Lambda)^{1/n}$

定义回顾：

• （开）球 $B(0,r) = \{x \in \mathbb{R}^n \mid \|x\| < r\}$ 是一个中心对称凸体，它的体积为 $\text{vol}(B(0,r)) = \dfrac{\pi^{n/2}}{\Gamma(n/2 + 1)} r^n$。它对应的闭球为 $\overline{B}(0, r)$。
• $\lambda_1(\Lambda)$ 是格 $\Lambda$ 中的最短非零向量的长度，即：
  $\lambda_1(\Lambda) = \inf\{r\mid \dim(\text{span}(\Lambda\cap B(0,r))) \geqslant 1\} = \inf\{\|v\|\mid 0 \neq v \in \Lambda\}$

证明思路：我们选了一个特殊的中心对称凸体：球，将这个特殊的中心对称凸体代入 Minkowski’s Convex Body Theorem 即得这个结论。

证明：
由 $\lambda_1(\Lambda)$ 的最小性，可知不存在 $v \in \Lambda \setminus \{0\}$ 使得 $\|v\| < \lambda_1(\Lambda)$。因此，开球 $B(0, \lambda_1(\Lambda))$ 中没有非零格点。根据 Minkowski’s Convex Body Theorem，如果 $\text{vol}(B(0, \lambda_1(\Lambda))) > 2^n \cdot \det(\Lambda)$，则 $B(0, \lambda_1(\Lambda))$ 中至少存在一个非零的格点，这与 $\lambda_1(\Lambda)$ 的定义矛盾。因此，我们必须有：

$\text{vol}(B(0, \lambda_1(\Lambda))) \leqslant 2^n \cdot \det(\Lambda)$

由于 $B(0, r)$ 的体积为 $\text{vol}(B(0, r)) = \frac{\pi^{n/2}}{\Gamma(n/2 + 1)} r^n$，我们可以将上述不等式改写为：

$\frac{\pi^{n/2}}{\Gamma(n/2 + 1)} \lambda_1(\Lambda)^n \leqslant 2^n \cdot \det(\Lambda)$

从而得到：

$\lambda_1(\Lambda) \leqslant \left( \frac{2^n \cdot \det(\Lambda) \cdot \Gamma(n/2 + 1)}{\pi^{n/2}} \right)^{1/n} = \dfrac{2}{\sqrt{\pi}}\Gamma(n/2+1)^{\frac{1}{n}}\cdot\det(\Lambda)^{\frac{1}{n}}$

当 $n$ 足够大时，由 Stirling 公式，$\Gamma(n/2 + 1)\approx \sqrt{\pi n}\left(\dfrac{n}{2e}\right)^{\frac{n}{2}}$，即：

$\lambda_1(\Lambda)\leqslant \dfrac{2}{\sqrt{\pi}}\cdot\pi^{\frac{1}{2n}}n^{\frac{1}{2n}}\cdot\sqrt{\dfrac{n}{2e}}\cdot \det(\Lambda)^{\frac{1}{n}}\approx \sqrt{\dfrac{2n}{\pi e}}\cdot \left(1 + \dfrac{\ln n}{2n}\right)\cdot \det(\Lambda)^{\frac{1}{n}}$

这里原定理的证明采用的是球 $B(0, r)$ 的内接正方体进行估计，其体积正好是 $\left(\dfrac{2r}{\sqrt{n}}\right)^n$，这样估计下来严格有：

$\lambda_1(\Lambda) \leq \sqrt{n} \cdot \det(\Lambda)^{1/n}$

注意：事实上这里的界并不是很紧，这是因为，当我们换一个角度来看待 Minkowski 第一定理时，我们发现，Minkowski第一定理所说的其实是：当我们考虑在每个格点处放置一个半径 $r$ 的球体时，当我们不要求这些球体重叠的条件下，这样的 $r$ 最大是多少？ 上述定理得到的就是 $r = \dfrac{\lambda_1(\Lambda)}{2}$。但是后来 Hermite 告诉我们，在考虑允许区域互相重叠的情况下，可以进一步将这个上界降低。更进一步地，我们会考虑这样的一个常量：

Hermite常量：

$\gamma_n = \sup\limits_{\Lambda}\dfrac{\lambda_1(\Lambda)^2}{\det(\Lambda)^{\frac{2}{n}}}$

0

v

λ₁

R

0. Init State 1. R < λ₁/2 2. R = λ₁/2 3. Overlap!

接下来我们将视角从一维抬高到 $n$ 维。对于一个向量空间，我们处理它的一个基本手段是考虑这个空间附有的二次型的正交基，这组正交基就会乖乖地张成整个空间。额，在这里这个情形下就是：

Gram-Schmidt 正交化
对 $n$ 个线性无关的向量 $b_1$, $b_2$, $\cdots$, $b_n$，定义它们的 Gram-Schmidt 正交化（正交基）为一组正交的向量 $\tilde{b}_1$, $\tilde{b}_2$, $\cdots$, $\tilde{b}_n$，且满足：

$\tilde{b}_i = b_i - \sum\limits_{j=1}^{i-1}\mu_{i, j}\tilde{b}_j$

其中 $\mu_{i, j} = \dfrac{\langle b_i, \tilde{b}_j \rangle}{\langle \tilde{b}_j, \tilde{b}_j \rangle}$
即，$\tilde{b}_i$ 恰为 $b_i$ 相对于 $\tilde{b}_1$, $\cdots$, $\tilde{b}_{i-1}$ 的正交成分。

0

b₁

b₂

b₃

b̃₁

b̃₂

b̃₃

Span(b̃₁)

Span(b̃₁, b̃₂)

0. Init Basis 1. Fix 1st Dim 2. Ortho 2nd Dim 3. Ortho 3rd Dim

$$\text{linear independent vectors } b_1, b_2, b_3$$

$$ \tilde{b}_1 = b_1 $$

$$ \tilde{b}_2 = b_2 - \mu_{2,1}\tilde{b}_1 \quad \left( \mu_{2,1} = \frac{\langle b_2, \tilde{b}_1 \rangle}{\langle \tilde{b}_1, \tilde{b}_1 \rangle} \right) $$

$$ \tilde{b}_3 = b_3 - \mu_{3, 1}\tilde{b}_1 - \mu_{3, 2}\tilde{b}_2 $$

将整个 Gram-Schmidt 写成矩阵的形式就是：

$\begin{pmatrix} \tilde{b}_1 \\ \tilde{b}_2 \\ \vdots \\ \tilde{b}_n \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 & \cdots & 0 \\ -\mu_{2,1} & 1 & 0 & \cdots & 0 \\ -\mu_{3,1} & -\mu_{3,2} & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ -\mu_{n,1} & -\mu_{n,2} & -\mu_{n,3} & \cdots & 1 \end{pmatrix} \cdot \begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_n \end{pmatrix}$

以及：

$\begin{pmatrix}b_1 \\ b_2 \\ \vdots \\ b_n \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 & \cdots & 0 \\ \mu_{2,1} & 1 & 0 & \cdots & 0 \\ \mu_{3,1} & \mu_{3,2} & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ \mu_{n,1} & \mu_{n,2} & \mu_{n,3} & \cdots & 1 \end{pmatrix} \cdot \begin{pmatrix}\tilde{b}_1 \\ \tilde{b}_2 \\ \vdots \\ \tilde{b}_n \end{pmatrix}$

写成方程的形式就是：

$\begin{cases} \tilde{b}_1 = b_1 \\ \tilde{b}_2 = b_2 - \mu_{2,1}\tilde{b}_1 \\ \tilde{b}_3 = b_3 - \mu_{3,1}\tilde{b}_1 - \mu_{3,2}\tilde{b}_2 \\ \vdots \\ \tilde{b}_n = b_n - \mu_{n,1}\tilde{b}_1 - \mu_{n,2}\tilde{b}_2 - \cdots - \mu_{n, n-1}\tilde{b}_{n-1} \end{cases}$

以及：

$\begin{cases} b_1 = \tilde{b}_1 \\ b_2 = \tilde{b}_2 + \mu_{2,1}\tilde{b}_1 \\ b_3 = \tilde{b}_3 + \mu_{3,1}\tilde{b}_1 + \mu_{3,2}\tilde{b}_2 \\ \vdots \\ b_n = \tilde{b}_n + \mu_{n,1}\tilde{b}_1 + \mu_{n,2}\tilde{b}_2 + \cdots + \mu_{n, n-1}\tilde{b}_{n-1} \end{cases}$

Minkowski’s Second Theorem

对任意$n$秩满秩格 $\Lambda$，有：

$\left(\prod\limits_{i=1}^n\lambda_i(\Lambda)\right)^{\frac{1}{n}} \leq \sqrt{n} \cdot \det(\Lambda)^{1/n}$

证明思路：选取恰好达到 $\lambda_1(\Lambda)$, $\lambda_2(\Lambda)$, $\cdots$, $\lambda_n(\Lambda)$ 的线性无关的格向量 $b_1$, $b_2$, $\cdots$, $b_n$，这时它们是倾斜的，我们并不好处理，但是我们可以对它们作 Gram-Schmidt 正交化。这时我们就获得了一个长方体，且这个长方体的体积恰好为 $\det(\Lambda)$（Gram-Schmidt正交化不改变体积）。如果我们想要使用 Minkowski Convex Body Theorem，那么就需要构造一个不包含任何非零格点的中心对称凸体。最极端的情形就是每一个 $b_i$ 都是相互垂直的，这样每一个 Gram-Schmidt 正交基就恰好都是 $\tilde{b}_i = b_i$。So，我们对于每一个方向上限制它最大为 $\lambda_i(\Lambda)$ 即可，进一步根据中心对称凸体，我们选取一个最常见的结构：椭球体 就行了。

证明：
设 $x_1, \dots, x_n \in \Lambda$ 为达到连续极小值的线性无关向量，即 $\|x_i\| = \lambda_i(\Lambda)$。
设 $\tilde{x}_1, \dots, \tilde{x}_n$ 为它们的 Gram-Schmidt 正交化。

考虑以 $\tilde{x}_1, \dots, \tilde{x}_n$ 为轴，且对应长度为 $\lambda_1, \dots, \lambda_n$ 的开椭球体：

$T = \left\{ y \in \mathbb{R}^n \;\middle|\; \sum_{i=1}^n \left( \frac{\langle y, \tilde{x}_i \rangle}{\|\tilde{x}_i\| \cdot \lambda_i} \right)^2 < 1 \right\}$

我们断言 $T$ 不包含任何非零格点。
事实上，任取非零向量 $y \in \Lambda$，并设 $1 \leq k \leq n$ 为使得 $\|y\| \geqslant \lambda_k(\Lambda)$ 的最大整数。
必定有 $y \in \text{span}(\tilde{x}_1, \dots, \tilde{x}_k) = \text{span}(x_1, \dots, x_k)$，因为否则的话，$x_1, \dots, x_k, y$ 将是 $k+1$ 个长度小于 $\lambda_{k+1}(\Lambda)$ 的线性无关向量。现在，

$\sum_{i=1}^n \left( \frac{\langle y, \tilde{x}_i \rangle}{\|\tilde{x}_i\| \cdot \lambda_i} \right)^2 = \sum_{i=1}^k \left( \frac{\langle y, \tilde{x}_i \rangle}{\|\tilde{x}_i\| \cdot \lambda_i} \right)^2 \geqslant \frac{1}{\lambda_k^2} \sum_{i=1}^k \left( \frac{\langle y, \tilde{x}_i \rangle}{\|\tilde{x}_i\|} \right)^2 = \frac{\|y\|^2}{\lambda_k^2} \geqslant 1$

因此，$y \notin T$。根据 Minkowski’s convex body theorem，$\text{vol}(T) \leq 2^n \det \Lambda$。但另一方面，

$\text{vol}(T) = \left( \prod_{i=1}^n \lambda_i \right) \text{vol}(\mathbf{B}(0, 1)) \geqslant \left( \prod_{i=1}^n \lambda_i \right) \left( \frac{2}{\sqrt{n}} \right)^n$

结合这两个界限，我们得到

$\left( \prod_{i=1}^n \lambda_i \right)^{1/n} \leq \sqrt{n} (\det \Lambda)^{1/n}$

注：事实上，Minkowski 第二定理具有与 Minkowski 第一定理类似的几何意义：我们考虑在每个格点处放置一个椭球，当我们不要求这些椭球体重叠的条件下，这样的椭球最大是多少？ 下面我们展示了一个简单的演进过程。

λ₁

λ₂

λ₃

r₁

r₂

r₃

0. 正交标架阵列 1. 3D 球均匀膨胀 2. 锁定 r₁ 旋转膨胀 3. 锁定 r₁, r₂ 完全膨胀

0. 正交标架与格点： 我们选取 Gram-Schmidt 正交化后的方向作为我们的坐标标架（虚线）。Minkowski 定理的核心在于：我们要在这个正交空间中膨胀出一个不包含原点以外格点的最大凸体，从而受限于体积约束。

1. 3D 球均匀膨胀（触碰 $\lambda_1$）： 凸体在三个正交标架方向均匀生长（此时表现为完美的 3D 球体）。当半径 $r_1$ 达到 $\lambda_1/2$ 时，它在第一个方向触碰到了最短非零向量。此时，我们必须冻结标架 $r_1$ 的生长。

2. 锁定 $r_1$ 旋转膨胀（触碰 $\lambda_2$）： 第一个维度被锁定。凸体只能在剩余的正交二维子空间（$r_2$-$r_3$ 平面）继续均匀膨胀，此时形状演变为旋转椭球体。直到 $r_2$ 达到 $\lambda_2/2$ 时触碰格点，标架 $r_2$ 也被冻结。

3. 锁定 $r_1, r_2$ 完全膨胀（触碰 $\lambda_3$）： 前两个维度均已锁定。凸体只能沿最后一条标架 $r_3$ 独自拉伸。当拉伸至 $\lambda_3/2$ 时触碰最后一个独立格点，停止生长。此时我们获得了一个拥有最大非空体积的完全不对称 3D 椭球，其体积直接导出了定理的不等式极值！

$$\Lambda\subset\mathbb{R}^n$$

$$r_1 = r_2 = r_3 = \frac{\lambda_1}{2}$$

$$r_1 = \frac{\lambda_1}{2},\; r_2 = r_3 = \frac{\lambda_2}{2}$$

$$\text{Vol}(T) = \frac{\lambda_1}{2} \cdot \frac{\lambda_2}{2} \cdot \frac{\lambda_3}{2}\cdot \text{Vol}(B(0, 1)) \leqslant \det(\Lambda)$$

$l_p$ 范数下的 Minkowski 定理

啊，其实基于上面的一大堆讨论，我们对于 Minkowski 在 $l_p$ 下的讨论就今生计算下述不等式：

• 对 Minkowski 第一定理：$\lambda_1(\Lambda)\leqslant \dfrac{2}{\text{Vol}(B_p(0, 1))^{\frac{1}{n}}}\cdot\det(\Lambda)^{\frac{1}{n}}$
• 对 Minkowski 第二定理：$\left(\prod\limits_{i=1}^n\lambda_i(\Lambda)\right)^{\frac{1}{n}} \leqslant \dfrac{2}{\text{Vol}(B_p(0, 1))^{\frac{1}{n}}}\cdot\det(\Lambda)^{\frac{1}{n}}$

其中 $B_p(0, 1)$ 指的就是 $l_p$ 范数下的以圆点为圆心，半径为 $1$ 的球：

$B_p^n = \left\{ (x_1, \dots, x_n) \in \mathbb{R}^n : \sum_{i=1}^n |x_i|^p \leq 1 \right\}$

现在的首要任务就变成了对于 $l_p$ 范数的球体的体积进行计算：

$V_n(p) = \int_{B_p^n} dx_1 dx_2 \dots dx_n = 2^n \int_{x_i \geq 0, \sum x_i^p \leq 1} dx_1 \dots dx_n$

为了消除指数 $p$，我们令 $u_i = x_i^p$。则 $x_i = u_i^{1/p}$，其导数为 $dx_i = \frac{1}{p} u_i^{\frac{1}{p}-1} du_i$。
变换后的积分区域变为单纯形 $S = \{ (u_1, \dots, u_n) : u_i \geq 0, \sum u_i \leq 1 \}$。

此时体积公式变为：

$\begin{aligned} V_n(p) &= 2^n \int_S \left( \frac{1}{p} u_1^{\frac{1}{p}-1} \right) \left( \frac{1}{p} u_2^{\frac{1}{p}-1} \right) \dots \left( \frac{1}{p} u_n^{\frac{1}{p}-1} \right) du_1 \dots du_n \\ &= \frac{2^n}{p^n} \int_S u_1^{\frac{1}{p}-1} u_2^{\frac{1}{p}-1} \dots u_n^{\frac{1}{p}-1} du_1 \dots du_n \end{aligned}$

这里需要用到一个著名的刘维尔积分公式（Liouville’s Extension of Dirichlet Integral），这个公式使用了数学归纳法结合了Beta函数和Gamma函数的关系：

$I_n = \int \dots \int_{S_n} u_1^{\alpha_1-1} u_2^{\alpha_2-1} \dots u_n^{\alpha_n-1} du_1 \dots du_n = \frac{\prod\limits_{i=1}^n \Gamma(\alpha_i)}{\Gamma(1 + \sum\limits_{i=1}^n \alpha_i)}$

其中 $S_n = \{ (u_1, \dots, u_n) : u_i \geq 0, \sum\limits_{i=1}^n u_i \leq 1 \}$。

在这里，即对所有 $i$ 都有 $\alpha_i = \frac{1}{p}$。代入公式，则有：

$\int_S u_1^{\frac{1}{p}-1} \dots u_n^{\frac{1}{p}-1} du_1 \dots du_n = \frac{\Gamma(1/p)^n}{\Gamma(1 + n/p)}$

从而我们带入得到体积的计算公式：

$V_n(p) = \frac{2^n}{p^n} \cdot \frac{\Gamma(1/p)^n}{\Gamma(1 + n/p)}$

利用 Gamma 函数的基本性质 $x\Gamma(x) = \Gamma(x+1)$，可得，$\left(1/p\right)^n \Gamma(1/p)^n = \Gamma(1 + 1/p)^n$。于是最终我们得到：

$V_n(p) = \frac{\left[ 2 \Gamma\left( 1 + 1/p \right) \right]^n}{\Gamma\left( 1 + n/p \right)}$

带入两个定理即得：

• 对 Minkowski 第一定理：$\lambda_1(\Lambda)\leqslant \dfrac{\Gamma\left( 1 + n/p \right)^{\frac{1}{n}}}{\Gamma\left( 1 + 1/p \right)}\cdot\det(\Lambda)^{\frac{1}{n}}$
• 对 Minkowski 第二定理：$\left(\prod\limits_{i=1}^n\lambda_i(\Lambda)\right)^{\frac{1}{n}} \leqslant \dfrac{\Gamma\left( 1 + n/p \right)^{\frac{1}{n}}}{\Gamma\left( 1 + 1/p \right)}\cdot\det(\Lambda)^{\frac{1}{n}}$

真棒，记：

$C_p(n) = \frac{\Gamma\left( 1 + n/p \right)^{\frac{1}{n}}}{\Gamma\left( 1 + 1/p \right)}$

下面对这个参数进行估计。
注意到当 $n$ 比较大时，根据 Stirling 公式（$\Gamma(x + 1) \sim \sqrt{2\pi x} \left(\frac{x}{e}\right)^x$），我们有：

$\Gamma\left( 1 + \frac{n}{p} \right)^{\frac{1}{n}} \sim \left[ \sqrt{2\pi \frac{n}{p}} \left( \frac{n}{pe} \right)^{\frac{n}{p}} \right]^{\frac{1}{n}} = \left( 2\pi \frac{n}{p} \right)^{\frac{1}{2n}} \left( \frac{n}{pe} \right)^{\frac{1}{p}}$

当 $n \to \infty$ 时，前面的项 $\left( 2\pi \dfrac{n}{p} \right)^{\frac{1}{2n}} \to 1$。因此，分子的渐进主导项仅仅是：$\left( \dfrac{n}{pe} \right)^{\frac{1}{p}}$。
从而我们得到最终的估计为：

$C_p(n) \sim \frac{1}{\Gamma(1 + 1/p)} \left( \frac{n}{pe} \right)^{\frac{1}{p}}$

代入一些典型范数：

• $l_1$ 范数 ($p=1$)：$C_1(n) \sim \dfrac{n}{e}$。界限随维度呈线性增长。
• $l_2$ 范数 ($p=2$)：$C_2(n) \sim \dfrac{2}{\sqrt{\pi}} \left(\dfrac{n}{2e}\right)^{\frac{1}{2}} = \sqrt{\dfrac{2n}{\pi e}}$。界限随维度呈平方根增长。
• $l_\infty$ 范数 ($p \to \infty$)：$C_\infty(n) \sim 1 \cdot 1 = 1$。界限是一个常数。

当然，在 $l_p$ 空间下，也有：

$\text{Vol}(\text{（椭）球体}) \geqslant \text{Vol}(\text{内接（长）正方体})$

的观察。且正方体的体积：

$\text{Vol}([-n^{\frac{1}{p}}, n^{\frac{1}{p}}]) = \dfrac{2^n}{n^{\frac{n}{p}}}$

就有：

• 对 Minkowski 第一定理：$\lambda_1(\Lambda)\leqslant n^{\frac{1}{p}}\cdot\det(\Lambda)^{\frac{1}{n}}$
• 对 Minkowski 第二定理：$\left(\prod\limits_{i=1}^n\lambda_i(\Lambda)\right)^{\frac{1}{n}} \leqslant n^{\frac{1}{p}}\cdot\det(\Lambda)^{\frac{1}{n}}$

Minkowski 第二定理与投影格

Minkowski 第二定理的证明中，我们事实上可以注意到一个事实：

$y\in \text{span}(\tilde{b}_1, \cdots, \tilde{b}_i) \iff y\in \text{span}(b_1, \cdots, b_i)$

转移定理（Transference 定理/Banaszczyk 定理）

LLL 算法

BKZ 算法

Minkowski定理的简单推广

根据作业启发，对相应理论进行了粗略的探索。

基于余元公式的简单推广

对于 Gamma 函数来说，我们有一个很有趣且常用的公式，称为余元公式：

$\Gamma(1/p)\cdot \Gamma(1 - 1/p) = \dfrac{\pi}{\sin(\pi/p)}$

其中 $p > 1$。

下面我们设 $\dfrac{1}{p} + \dfrac{1}{q} = 1$，其中 $p > 1$，$q > 1$，注意到 $V_n(p) = \dfrac{2^n}{p^n}\cdot\dfrac{\Gamma(1/p)^n}{\Gamma(1+n/p)}$，同时带入 $p$ 和 $q$，然后相乘，就有：

$\begin{aligned} V_n(p)^{\frac{1}{n}}\cdot V_n(q)^{\frac{1}{n}} &= \dfrac{4\cdot \Gamma(1/p)\cdot\Gamma(1/q)}{pq}\cdot \dfrac{1}{\Gamma(1+n/p)^{\frac{1}{n}}\cdot\Gamma(1+n/q)^{\frac{1}{n}}}\\ &=\dfrac{4\pi}{pq\sin(\pi/p)} \cdot \dfrac{1}{\Gamma(1+n/p)^{\frac{1}{n}}\cdot\Gamma(1+n/q)^{\frac{1}{n}}}\\ &= \dfrac{4\pi e}{p^{\frac{1}{q}}q^{\frac{1}{p}}\sin(\pi/p)} \end{aligned}$

分别根据 $l_p$ 和 $l_q$ 范数下的 Minkowski 第一定理，相乘得到：

$\lambda_1^{(p)}(\Lambda) \cdot \lambda_1^{(q)}(\Lambda) \lesssim \dfrac{n\sin(\pi/p)}{\pi e} \cdot p^{\frac{1}{q}} q^{\frac{1}{p}} \cdot \det(\Lambda)^{\frac{2}{n}}$

基于极体的简单推广

我们注意到，Minkowski Convex Body Theorem 对于（有界闭合内部非空的）形状 $S$ 的要求主要是（1）凸（2）中心对称，而当我们去证明 Minkowski 第一第二定理时，我们将其特化成了（椭）球体，如果我们回过头来，只是考虑这样的一个内部非空的有界闭合中心对称凸体 $S\subset \mathbb{R}$。同时设 $\Lambda\subset \mathbb{R}^n$ 为一个满秩格。

这里会想到极体主要是因为想到了对偶格。凸分析中自然有极体的概念可以使用。