单位根的正交性

单位根的正交性

模块 5：数论变换 (NTT) — 有限域中的快速傅里叶变换

由本原 $k$ 次单位根生成的全体 $k$ 次单位根的幂之和，其结果要么是零，要么是 $k$。我们称这一性质为单位根的正交性，它将在下一章中被直接应用。

我们首先通过具体示例来说明这一性质，以便读者熟悉它，然后再给出一般性的证明。

单位根的幂之和

考虑由本原 $k$ 次单位根 $\omega$ 生成的所有 $k$ 次单位根：

$$1, \omega, \omega^2, \dots, \omega^{k-1}$$

如果我们对这个列表中的每个元素都取 $m$ 次幂，就会得到另一个列表：

$$1^m, \omega^m, (\omega^2)^m, \dots, (\omega^{k-1})^m$$

本章的目标是展示对这个新列表中的所有元素求和会发生什么。换句话说，我们希望计算对任意 $m$ 值，以下求和 $s$ 的结果：

$$s = 1^m + \omega^m + (\omega^2)^m + \dots + (\omega^{k-1})^m$$

以 $\mathbb{F}_{17}$ 中的 4 次单位根为例（实际上，任何包含本原 4 次单位根的域均可）。对于一个本原根 $\omega$，这些根是：

$$1, \omega^1, \omega^2, \omega^3,$$

或者，利用此例中 $\omega^2 \equiv -1$ 的关系，它们也可以表示为：

$$1, \omega, -1, -\omega$$

让我们将这些元素提升到某个指数 $m$，例如取 $m=3$：

$$1^3, \omega^3, (-1)^3, (-\omega)^3$$

注意到 $(-1)^3 = -1$ 且 $(-\omega)^3 = -\omega^3$，我们可以简化部分元素。

于是，同样的列表可改写为：

$$1, \omega^3, -1, -\omega^3$$

这些元素之和为零，因为：

$$1 + \omega^3 + (-1) + (-\omega^3) = 0$$

再举一例。我们再次从 $\mathbb{F}_{17}$ 中的 4 次单位根出发，但这次将每个元素提升到 8 次幂。

得到以下元素：

$$1^8, \omega^8, (-1)^8, (-\omega)^8$$

由于 8 是偶数，因此 $(-1)^8 = 1$ 且 $(-\omega)^8 = \omega^8$。

同时，请记住对于 4 次单位根，有 $\omega^4 = 1$。因此，$\omega^8 = (\omega^4)^2 = 1^2 = 1$。

于是，我们的列表简化为：

$$1^8=1, \omega^8=1, 1^8=1, \omega^8=1$$

所有元素之和为：

$$s = 1 + 1 + 1 + 1 = 4$$

在上述示例中，当 $m$ 不是 $k$ 的倍数时（$k=4, m=3$），总和为零；而当 $m$ 是 $k$ 的倍数时（$k=4, m=8$），总和为 $k$。这一结论在一般情况下也是成立的。

我们将陈述并证明以下两点：

1. 如果幂指数 $m$ 不是 $k$ 的倍数，则总和为零。
2. 反之，如果 $m$ 是 $k$ 的倍数，则总和为 $k$。

在进行一般性证明之前，让我们再看一个例子。

$\mathbb{F}_{17}$ 中的 8 次单位根

考虑 $\mathbb{F}_{17}$ 中的 8 次单位根。它们可以写成：

$$1, \omega, \omega^2, \omega^3, -1, -\omega, -\omega^2, -\omega^3,$$

这里我们利用了对于本原 8 次单位根 $\omega$ 有 $\omega^4 \equiv -1$ 的性质。

如果我们将此列表中的每个元素提升到某个不是 8 的倍数的幂 $m$ 然后求和，结果为零。否则，如果 $m$ 是 8 的倍数，则总和为 8。

新列表由下式给出：

$$1^m, \omega^m, (\omega^2)^m, (\omega^3)^m, (-1)^m, (-\omega)^m, (-\omega^2)^m, (-\omega^3)^m$$

下面我们来分析可能的情况。

情况 1：$m$ 不是 8 的倍数

考虑 $m=2$ 的情况。列表为：

$$1^2, \omega^2, (\omega^2)^2, (\omega^3)^2, (-1)^2, (-\omega)^2, (-\omega^2)^2, (-\omega^3)^2$$

它可以改写为：

$$1, \omega^2, \omega^4, \omega^6, 1, \omega^2, \omega^4, \omega^6$$

利用 $\omega^4 \equiv -1$ 这一事实，列表变为：

$$1, \omega^2, -1, -\omega^2, 1, \omega^2, -1, -\omega^2$$

对这些元素求和，我们得到：

$$ \begin{aligned} s &= 1 + \omega^2 + (-1) + (-\omega^2) + 1 + \omega^2 + (-1) + (-\omega^2) \ &= (1 - 1) + (\omega^2 - \omega^2) + (1 - 1) + (\omega^2 - \omega^2) \ &= 0 \end{aligned} $$

练习：证明当 $m=3$ 和 $m=4$ 时，总和也为零。

情况 2：$m$ 是 8 的倍数

考虑 $m=16$ 的情况。我们得到的新列表为：

$$1^{16}, \omega^{16}, (\omega^2)^{16}, (\omega^3)^{16}, (-1)^{16}, (-\omega)^{16}, (-\omega^2)^{16}, (-\omega^3)^{16},$$

或者：

$$1, \omega^{16}, \omega^{32}, \omega^{48}, 1, \omega^{16}, \omega^{32}, \omega^{48}$$

同时我们有：

$$ \begin{aligned} \omega^{16} &= (\omega^8)^2 \ \omega^{32} &= (\omega^8)^4 \ \omega^{48} &= (\omega^8)^6 \end{aligned} $$

由于我们知道对于任何本原 8 次单位根，都有 $\omega^8 \equiv 1$，因此该列表实际上是：

$$1, 1^2, 1^4, 1^6, 1, 1^2, 1^4, 1^6$$

所有项的总和为 8。

$k$ 次单位根的幂之和

现在，让我们一般性地证明前面通过示例所展示的结论。

定理。考虑由本原 $k$ 次单位根 $\omega$ 生成的所有 $k$ 次单位根。这些 $k$ 次单位根的幂之和满足：

1. 如果幂指数不是 $k$ 的倍数，则总和为零；
2. 如果幂指数是 $k$ 的倍数，则总和为 $k$。

下面，我们将分别证明这两种情况。

情况 (1)：证明当指数不是 $k$ 的倍数时总和为零

考虑所有 $k$ 次单位根，每个都提升到不是 $k$ 的倍数的幂 $m$：

$$(\omega^0)^m, (\omega^1)^m, (\omega^2)^m, \dots, (\omega^{k-1})^m$$

我们希望计算总和：

$$s = (\omega^0)^m + (\omega^1)^m + (\omega^2)^m + \dots + (\omega^{k-1})^m$$

这个总和可以写成：

$$s = \sum_{i=0}^{k-1} (\omega^i)^m$$

利用 $(\omega^i)^m = (\omega^m)^i$ 这一事实，我们可以将总和重写为：

$$s = \sum_{i=0}^{k-1} (\omega^m)^i$$

上式是一个等比级数，即同一元素的连续幂之和：

$$s = (\omega^m)^0 + (\omega^m)^1 + (\omega^m)^2 + \dots + (\omega^m)^{k-1}$$

这种形式的等比级数满足：

$$s = (\omega^m)^0 + (\omega^m)^1 + (\omega^m)^2 + \dots + (\omega^m)^{k-1} = \frac{(\omega^m)^k - 1}{\omega^m - 1}$$

要证明这个分式等于零，我们必须先说明分母不为零，然后证明分子等于零。

这里，$m$ 不是 $k$ 的倍数这个条件至关重要。回顾本原 $k$ 次单位根的定义：它是一个满足 $\omega^k \equiv 1$，但对于所有满足 $0 \leq r < k$ 的整数 $r$，都有 $\omega^r \neq 1$ 的元素 $\omega$。

因此，对于本原 $k$ 次单位根 $\omega$，只有 $\omega^k$ 的幂才等于 1，例如 $(\omega^k)^0, (\omega^k)^1, (\omega^k)^2$ 等等。

• 原文链接： rareskills.io/post/ortho...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～