单位根的 k/2 次幂等于 1 或 -1

本文讨论了将k次单位根 ω 提高到 k/2 次方的问题,结果只能是1或-1。文章给出了证明,当指数为偶数时,结果为1;当指数为奇数时,结果为-1。这种性质可以用于优化多项式在单位根上的求值计算,通过因式分解尽可能多地提取出 x^(k/2) 项,从而简化计算。

偶数的 任何 -th 单位根的 次方将导致 1 或 -1。

这不应与看起来相似的概念混淆,即 或 单位根 和 互为加法逆元。

让我们以本原 8 次单位根为例,生成器(本原 8 次单位根):

作为给读者的练习,我们建议取 6 次单位根,将每个元素升到 3 次方 (),看看结果是 。

查看上面的评估,我们看到一个模式,即插入 的偶数次单位根的计算结果为 1,而插入 的奇数次单位根的计算结果为 -1。对此的证明在附录中。同时,让我们提出本章的中心论点:

任何 k-th 单位根升到 次方,其中 为偶数,结果为 1 或 -1。具体来说,设 为本原 -th 单位根,并设所讨论的单位根为 。如果 为偶数, 将计算为 1,如果 为奇数,则 将计算为 -1。

这个论断的一个副作用是,如果在一个单位根上进行评估,那么具有 次方的多项式中的项几乎可以免费评估。

假设例如我们有一个多项式 ,我们想在 8 个点上评估。现在假设我们将这 8 个点设置为 8 次单位根。通常,我们必须循环遍历 并评估 每个点。但是,我们实际上不需要对每个评估点进行指数运算——我们只需检查单位根的幂是偶数还是奇数!

事实上,我们可以完全跳过这个过程。让我们将 视为长度为 8 的数组。我们可以根据数组索引是偶数还是奇数返回 1 或 -1,并完全忽略指数。换句话说, 将计算为

如果多项式的系数不是 1,例如 ,则评估仅取决于我们是否在偶数或奇数索引上:

但是,对于不是 形式的多项式呢?可以对多项式进行因式分解,以引入尽可能多的 项。例如,考虑多项式

只有 项是 形式的。但是,假设我们将多项式分解如下:

这个多项式更容易评估,因为我们提前知道 项何时计算为 1 或 -1。

但是,我们还没有一个很好的技巧来处理 的较低幂。这将是后面章节的主题。

总结

将 -th 单位根 升到 次方,如果 为偶数,则结果为 1,如果 为奇数,则结果为 -1。如果我们在 -th 单位根上评估一个多项式,则幂为 的项可以通过简单地知道我们正在评估的单位根是偶数次幂还是奇数次幂来自动计算。因此,最好对多项式进行因式分解,以便我们最大化 项的数量。

附录 — 证明对于偶数,如果 为偶数,则 为 1,如果 为奇数,则 为 -1

和 互为加法逆元。由于 且 , 必须是 的加法逆元,因此 。

现在我们取 (即 -1)并将其升到

请注意, 只能是 1 或 -1。具体来说,如果 是偶数,则 ,如果是奇数,则 。因此,如果 是偶数,则我们的表达式的结果为 1,如果是奇数,则结果为 -1。

我们的表达式可以重写为:

$$(-1)^m = \begin{cases}
1, & \text{if } m \text{ is even} \\
-1, & \text{if } m \text{ is odd}
\end{cases}$$

由于表达式的代数恒等式没有改变,我们仍然可以说如果 是偶数,则 ,如果是奇数,则 。

因此,我们证明了原始语句,即当 为偶数时 ,当 为奇数时为 。

  • 原文链接: rareskills.io/post/roots...
  • 登链社区 AI 助手,为大家转译优秀英文文章,如有翻译不通的地方,还请包涵~
点赞 0
收藏 0
分享
本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论
RareSkills
RareSkills
https://www.rareskills.io/