格的壞基礎範例（LLL 的最壞情況）
概括。給定一些維度 $ n $ （說 $ n=50 $ ), 是否可以明確地描述一個格 $ L $ 和一個基礎 $ B $ 的 $ L $ 這樣 $$ \frac{ | LLL(B)_1 | }{ \lambda_1(L) } > 1.02^n $$ 在哪裡 $ LLL(B)_1 $ 是 LLL 約簡基的第一個向量 $ B $ （為了 $ \delta=1 $ 說）？常數 1.02 是 Nguyen-Stehlé 在“平均 LLL”中給出的值。或者至少，我如何（確定地）產生這樣的基礎 $ B $ ?
我試圖了解如何（確定地）產生一個格子 $ L \subset \mathbb R^n $ 和一個“糟糕的基礎” $ L $ ，在任何給定的維度上，比如說 $ n=50 $ . 通過“壞基礎” $ (b_1, …, b_n) $ ，我的意思是當我們對它應用 LLL 算法時（比如 $ \delta = 1 $ ) 然後我們得到一個基礎 $ (v_1, …, v_n) $ 這樣 $ | v_1 | $ 是“盡可能”從 $ \lambda_1(L) $ . 上限 $ | v_1 | \leq (\delta - 1/4)^{-(n-1)/2} \lambda_1(L) $ 通常不鋒利，我們通常有 $ | v_1 | \leq 1.02^n \lambda_1(L) $ .
我對可以描述的明確範例感興趣 $ b_i $ 很容易（或明確定義一個單模矩陣 $ U $ 這將給出糟糕的基礎 $ B $ 從“良好的基礎” $ G $ , 可用於計算 $ \lambda_1(L) $ ）。我看到有時可以使用 $ B = HNF(G) $ ，但它可能並不總是能得到一個糟糕的基礎，因此它並不明確（對我來說也不是很清楚……）。
我終於找到了答案！N. Gama 的論文（第 36 頁）對此進行了解釋，可在此處獲得。我複制其行構成基礎的矩陣 $ B $ 一個格子的上界 $$ | LLL(B)_1 | \leq (4/3)^{(n-2)/2} \lambda_1(L) $$ 實際上對所有人來說都很緊（尖銳） $ n $ . （注意指數 $ n-2 $ 並不是 $ n-1 $ ).
在哪裡 $ \gamma_2 = \sqrt{ 4/3 } $ 是 Hermite 在第 2 維的常數。注意右邊的三角矩陣是 Gram-Schmidt 係數的矩陣，非對角線項都是 $ 1/2 $ 這是 LLL 約簡基定義中允許的最大值。
