基於格的密碼學中的 Minkowski 定理
我正在學習基本的基於格的密碼學。在O. Regev 給出的課程中，第 7 頁，有權利要求 1 和推論 2（閔可夫斯基第一定理），我都很難理解。
- 在權利要求1中，半徑為r的球的體積如何 $ vol(B(0,r)) \ge \left( \frac {2r}{\sqrt{n}} \right)^n $ ? （具體來說，球如何包含邊長的超立方體 $ \frac{2r}{\sqrt{n}} $ ) ?
- 在推論 2（閔可夫斯基第一定理）中，對於任何滿秩格 $ \Lambda $ n 級， $ \lambda_1(\Lambda) \le \sqrt{n} (<det \ \Lambda)^{\frac{1}{n}} $ . 如何證明這個定理？
試著畫一個“超立方體” $ \mathbb{R}^2 $ （即正方形）和 $ \mathbb{R}^3 $ （即一個規則立方體），都以原點為中心並且邊長等於 $ \frac{2r}{\sqrt n} $ …
由於它們以原點為中心，因此每一邊都從 $ -\frac{r}{\sqrt n} $ 至 $ \frac{r}{\sqrt n} $ （在其軸上）。
現在，屬於超立方體的離原點最遠的點正是角的點，並且所有角與原點的距離相同。由於球體是對稱的，如果一個角屬於一個球體，那麼所有的角都屬於這個球體，因此整個超立方體都包含在球體中。
原點到拐角的距離 $ c := \left(\frac{r}{\sqrt n }, \frac{r}{\sqrt n }, \cdots, \frac{r}{\sqrt n}\right) \in \mathbb{R}^n $ 是（誰）給的
$$ ||c|| = \sqrt{\left(\frac{r}{\sqrt n}\right)^2 + \cdots + \left(\frac{r}{\sqrt n}\right)^2} = \sqrt{n \cdot \left(\frac{r}{\sqrt n}\right)^2} = r $$ 現在，請注意，根據定義，超球面 $ B(0, r) $ 包含距離內的所有點 $ r $ 因此，它包含角，然後是整個 $ n $ 維超立方體。
由於這個超立方體包含在 $ B(0, r) $ , 它的體積不能大於 $ B(0, r) $ ，並且我們知道超立方體的體積是其邊長的乘積，在這種情況下， $ \prod_{i=1}^n \frac{2r}{\sqrt n} = \left( \frac{2r}{\sqrt n} \right) ^n $ .
所以，最後， $ Vol(B(0, r)) \ge \left( \frac{2r}{\sqrt n} \right)^n $ .
對於推論 2，你只需要使用 $ r = \lambda_1 $ 在上面的公式中。那麼，我們得到
$$ \left( \frac{2\lambda_1}{\sqrt n} \right)^n \le Vol(B(0, \lambda_1)) $$ 並且因為 $ B(0, \lambda_1) $ 沒有非零格點（根據定義 $ \lambda_1 $ )，它的體積不能大於 $ 2^n \det(\Lambda) $ （通過定理 9 的反證），那麼我們得到
$$ Vol(B(0, \lambda_1)) \le 2^n \det(\Lambda) $$
在本節中，我們將討論為什麼立方體的邊長是 $ \frac{2r}{\sqrt{n}} $ n維
我們首先解釋 3 維情況，然後將其擴展到 n 維。
讓我們取邊長的立方 $ a $ 刻在一個半徑的球上 $ r $ 如下所示：
現在，立方體的主對角線長度為 $ \sqrt{3}a $ .
立方體主對角線的長度是半徑為r的球的直徑
$ \Rightarrow \sqrt{3}a=2r $ .
所以， $ a=\frac{2r}{\sqrt{3}} $ 形式為 $ \frac{2r}{\sqrt{n}} $ 為了 $ n=3 $
所以，結果成立 $ n=3 $ . 現在，對於 n 維情況，請參閱Math.SE 上的這個問題。
從上面的文章：
立方體的主對角線長度為 $ \sqrt{n}a $ 在哪裡 $ a $ 是立方體每一邊的長度。
同樣，立方體主對角線的長度是半徑球的直徑 $ r $
$ \Rightarrow \sqrt{n}a= 2r $
所以， $ a=\frac{2r}{\sqrt{n}} $ 這是定理給出的值。
