基向量太多的格基约简

Question

假设我有一个n-dimensional格的基，L\subseteq\mathbb{Z}^n和B有n向量。现在我取另一个v\in \mathbb{Z}^n\setminus L，定义一个新的格L'=L+\mathbb{Z}v。向量集B':=B\cup\{v\}生成L'，但是由于L'是n-dimensional，它的秩最多是n，所以B'太大了。因此，必须有其他一些基础来生成L'。我们如何从B'中产生这样的结果呢？

我隐约记得读到微信能做到这一点，但我不知道怎么做。有人能指点参考或提供快速的论据/证据吗？

Answer 1

写一个答案，所以这不是没有答案，虽然在评论中提到了HNF。

Hermite范式是将生成集约为一个基的标准方法。这意味着它是计算格上的几个运算的标准方法(例如，这些运算很容易用基向量表示)。

• L+L' (您的示例是特例)，或
• L\cap L' (这不太明显，需要二重性)。

请参阅这些笔记的易格问题。

你的评论

看起来有效地计算Hermite范式是非常重要的.

这是(某种程度上)正确的，但非琐碎并不是“难”的。我从笔记中引用

不难找到一种算法来计算只执行多项式数运算的矩阵的HNF。然而，由于中间计算中的数字很容易得到很大的数目，因此对该问题的天真解决可能会导致超多项式运行时间。

链接注释包括HNF实现的伪代码，即多项式运行时间(通过确保中间值保持有界)。它也许比微光要复杂一些，但实际上并不是太多--这两种算法我都希望一个高年级/高年级的本科生能够在没有太多努力的情况下实现。

当然，你可以花费更多的精力来获得更实际有效的东西。请参阅Pernet和Stein的这篇论文。由于Stein是Sage CAS的创始人，我认为这与Sage所实施的相当接近，至少在2011年前后是如此。这个算法也许是你心目中的“非平凡”算法。但是另一方面，LLL的高效实现同样也具有非平凡性(几年前，我听说LLL同时是多项式时间，而且可能很难在大型格上运行，例如维数1k+)。

值得一提的是，似乎有一些工作使用LLL作为子例程计算HNFs，例如，请参见这。