漸近線的具體證據λ1(Λ⊥(A))λ1(Λ⊥(A))lambda_1(Lambda^perp(A))?
最近的電子印刷紙聲稱綁定 $ \lambda_1(\Lambda^\perp(\mathbf{A})) $ 為了 $ \mathbf{A}\in\mathbb{Z}^{n\times m} $ ，一個均勻隨機矩陣，由 $ O(1) $ ，具體由 $ 4 $ . 這有應用解決 $ \mathsf{SIS}_{n,m,q,4} $ 在 $ \mathsf{P} $ .
我不是這方面的專家，但在我看來，這與普遍的想法相矛盾 $ \lambda_1(\Lambda^\perp(\mathbf{A})) = \Omega(\sqrt{n\log q}) $ （例如，參見本文的第 2.4.2 節）。
由於進入最近的論文的細節可能不是這個論壇的主題，我感興趣的是另一個問題——為漸近線收集了哪些具體/實驗證據 $ \lambda_1(\Lambda^\perp(\mathbf{A})) $ ? 研究這樣的數據將是一種簡單的方法來獲得我們是否處於 $ O(1) $ 政權或 $ \Omega(\sqrt{n\log q}) $ 一，我曾假設有人有這些方面的文件，但實際上不記得自己看過任何文件。
論文第 3 頁底部的第一個不等式是錯誤的。例如，康威和湯普森證明了“自對偶”的存在 $ n $ 維晶格 $ L $ （IE， $ L^* = L $ ） 在哪裡 $ \lambda_1(L) = \lambda_1(L^*) = \Omega(\sqrt{n}) $ ， 因此 $ \eta_{2^{-n}}(L) = O(1) $ 但 $ \tilde{bl}(L) \geq \lambda_1(L) = \Omega(\sqrt{n}) $ .
Conway 和 Thompson 的結果的陳述和證明可以在https://www.springer.com/us/book/9783642883323中找到定理 9.5 。
獨立於算法聲明，我確實對定理 2 有嚴重的懷疑。這裡有一個反駁（使用標準技術）由 Yang Yu 和 Wessel van Woerden 編造的：
假設 $ q $ 是素數，並假設 2-範數中的最小距離確實有界 $ b=O(1) $ . 最多有 $ Binom[m,b] \cdot (2b+1)^b = poly(m) $ 元素 x 在 $ \mathbb Z^m \setminus {0} $ 和 $ ||x||^2_2 \leq b $ . 但是每個這樣的向量都只有機率 $ q^{-n} $ 在隨機性上成為晶格的一部分 $ A $ . 通過聯合界限，這意味著任何這樣的向量是格的一部分的機率超過隨機性 $ A $ 最多是 $ poly(m) \cdot q^{-n} $ 除非 m 本身是指數的，否則可以忽略不計 $ n $ .