HNF 基是格的最差基嗎？
我正在研究晶格問題和解決它們的一些方法。我讀過一些書，其中提到 Babai 的查找最近向量問題 (CVP) 的算法在格的“壞”基礎上無法成功。
這就引出了一個問題：格的最差基礎是什麼？
HNF 基礎是在格中找到 CVP 的最差基礎嗎？
算法是否成功解決例如 CVP 取決於基礎的質量，例如，可以根據基礎向量的範數之和來衡量基礎的質量。因此，您的問題可以解釋為：HNF 是否為您提供了質量最差的晶格的基礎？
答案必須是否定的。假設格子所在的 wlog $ \mathbb{Z}^n $ , 而 HNF 基的基向量的範數之和為 $ M $ . 現在很明顯，只有有限多個格子的基數小於這個質量度量 $ M $ ，因為我們可以列舉所有可能的此類基礎。另一方面，每個格子的基數是無限多的，因此必然有一個質量更差的基。這完全取決於你如何定義“質量”，但對於大多數明智的定義，沒有“最差質量”——你總是可以得到更差的基礎。
更具體地說，給定一個基矩陣 $ B $ , 你可以得到另一個基 $ B’ = U \cdot B $ 乘以 $ B $ 任何單模矩陣 $ U $ . 通過採取 $ U $ 有大量的條目， $ B’ $ 可能會比基礎更差 $ B $ .
由於 Babai，CVP 有兩種算法。最近平面算法和舍入算法。前者，首先應用 LLL。因此獨立於輸入基礎，算法將輸出相同的向量。所以你的說法是不正確的（因為這個算法不依賴於基礎的表示）。
後一種算法，是八佰的捨入算法。實際上，在這種情況下，輸出取決於輸入基礎。
你的問題是，如果我用 HNF 矩陣來輸入算法，如果我使用更好的基礎，輸出會最差嗎？一般來說沒有。
要看到這一點，假設您有一個滿秩整數格和一個基，它們形成一個對角矩陣，對角線條目中有正整數。該矩陣是 HNF，因此基是 HNF 基。但是，舍入算法解決了 CVP 問題，因為基是正交的（這是練習 18.2.5）。因此，您的主張再次似乎不正確。也許，在特定的格中，基於 HNF 的 CVP 提供了不好的結果。但是，你必須更具體。