单位根的正交性

Last updated on Apr 21, 2026

由一个本原 $k$ 次单位根生成的 $k$ 次单位根的幂之和要么是零，要么是 $k$ 。我们将这个性质称为单位根的正交性（orthogonality of roots of unity）。在下一章中，我们将直接利用这个性质。

我们首先通过示例来说明这个性质，以便读者对其有所熟悉。然后我们将在一般情况下对其进行证明。

单位根的幂之和

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

[ 1, \omega, \omega^2, ..., \omega^{k-1} ]

如果我们取这个元素列表并将每个元素求 $m$ 次幂，我们会得到另一个列表：

[ 1^m, \omega^m, (\omega^2)^m, ..., (\omega^{k-1})^m]

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

s = 1^m + \omega^m + (\omega^2)^m + ... + (\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$ 。这在一般情况下也是成立的。

我们将展示并证明以下内容：

如果幂 $m$ 不是 $k$ 的倍数，则总和为零。
否则，如果 $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$ 。

如果我们将这个列表的每个元素求 $m$ 次幂，且 $m$ 不是 $8$ 的倍数，然后对所有元素求和，结果为零。否则，如果 $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$ 次单位根的幂之和为：

零，如果幂不是 $k$ 的倍数；
$k$ ，如果幂是 $k$ 的倍数。

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

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

考虑 $k$ 次单位根，每个求 $m$ 次幂，且 $m$ 不是 $k$ 的倍数：

[ (\omega^0)^m, (\omega^1)^m, (\omega^2)^m, ..., (\omega^{k-1})^m ]

我们想要计算总和

s = (\omega^0)^m + (\omega^1)^m + (\omega^2)^m + ... + (\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 + ... + (\omega^m)^{k-1}

这种形式的几何级数满足

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

为了证明上述分数等于零，我们必须首先证明分母非零，然后证明分子等于零。

$m$ 不是 $k$ 的倍数这一事实在此至关重要。回顾本原 $k$ 次单位根的定义：它是一个元素 $\omega$ ，满足 $\omega^k \equiv 1$ ，但对于任何 $0 \leq r <k$ ， $\omega^r \neq 1$ 。

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

因为 $m$ 不是 $k$ 的倍数， $\omega^m$ 的形式不是对于任何整数 $n$ 的 $\omega^{nk}$ ，因此 $\omega^m \neq 1$ 。所以，上述分数的分母 $\omega^m-1$ 非零。

现在让我们考虑分子 $(\omega^m)^k - 1$ 。它可以写成 $(\omega^k)^m - 1$ 。

因为 $\omega$ 是一个本原 $k$ 次单位根，我们有 $\omega^k = 1$ ，分子变成

\begin{align*} (\omega^k)^m -1 &=(1)^m-1 \\ &= 1 - 1 \\ &= 0 \end{align*}

因为分子为零且分母非零，所以整个总和为零。

在下一节中，我们将研究指数 $m$ 是 $k$ 的倍数的情况。

情况 (2)：将每个元素求一个为 $k$ 的倍数的指数次幂

在本节中，我们将证明 $k$ 次单位根求 $m$ 次幂（其中 $m$ 是 $k$ 的倍数）的总和不为零，而是 $k$ 。

考虑 $k$ 次单位根

[ \omega^0, \omega^1, \omega^2, ..., \omega^{k-1} ]

让我们将此列表中的每个元素求某个幂 $m$ ：

[ (\omega^0)^m, (\omega^1)^m, (\omega^2)^m, ..., (\omega^{k-1})^m ]

因为 $(a^b)^c = (a^c)^b$ ，我们可以如下重新排列上面的每一项：

[ (\omega^m)^0, (\omega^m)^1, (\omega^m)^2, ..., (\omega^m)^{k-1} ]

现在考虑 $m$ 是 $k$ 的倍数的情况，即对于某个 $n$ ， $m=kn$ 。因此，我们的列表可以写成

[ (\omega^{nk})^0, (\omega^{nk})^1, (\omega^{nk})^2, ..., (\omega^{nk})^{k-1} ]

因为 $\omega^{nk} = (\omega^k)^n$ ，我们得到列表

[ (\omega^{k})^{0n}, (\omega^{k})^{1n}, (\omega^{k})^{2n},..., (\omega^{k})^{(k-1)n}]

利用 $\omega^k \equiv 1$ ，该列表由数字 1 的若干次幂组成：

[ (1)^{0n}, (1)^{1n}, (1)^{2n},..., (1)^{(k-1)n}]

或简写为

[1,1,1,...,1]

因为列表中有 $k$ 个元素，总和是

\underbrace{1 + 1 + 1 + \dots + 1}_{k \text{ times}} = k

结合这两个性质

表达这两个性质的一种优雅而简便的方法如下：

\sum_{i=0}^{k-1} (\omega^{i})^{m}=\begin{cases}k, & \text{if } m \text{ is a multiple of } k,\\[6pt]0, & \text{otherwise}.\end{cases}

这里的求和范围从第一项 $\omega^0$ 到最后一项 $\omega^{k-1}$ 。

两个 $k$ 次单位根列表的内积

在本节中，我们将以上面获得的关联重写为一种更适合在后续章节中使用的形式。

更准确地说，我们将把它写成

\sum_{i=0}^{k-1} (\omega^{i})^{r-s}=\begin{cases}k, & \text{if } r\equiv s \pmod{k},\\[6pt]0, & \text{otherwise}.\end{cases}

首先，让我们证明这两种形式是相同的，然后解释第二种形式的动机。

两种形式是等价的

如果 $r$ 模 $k$ 同余于 $s$ （第二种形式），那么对于某个整数 $n$ ， $r-s = nk$ 。

因此，我们说在第一种形式中被写为 $m$ 的 $r-s$ ，是 $k$ 的倍数。这与声明 $m$ 是 $k$ 的倍数是一样的。

在第二种形式中使用 $r$ 和 $s$ 的原因是我们将考虑两个向量的内积，每个向量都由单位根的幂组成。

两个单位根向量的内积

让我们考虑两个 $k$ 次单位根向量。第一个向量 $A$ 求 $r$ 次幂，形式为

A =[ (\omega^0)^r, \omega^r, (\omega^2)^r, ..., (\omega^{k-1})^r ]

第二个向量 $B$ 求负指数 $-s$ 次幂，形式为

B = [ (\omega^0)^{-s}, \omega^{-s}, (\omega^2)^{-s}, ..., (\omega^{k-1})^{-s} ]

注意：将本原 $k$ 次单位根求负数次幂不是问题。我们可以写成 $\omega^{-s} = (\omega^{-1})^s$ ，其中 $\omega^{-1}$ 是 $\omega$ 的乘法逆元。

由于 $\omega^{k} = 1$ ，将两边同时乘以 $\omega^{-1}$ 得到 $\omega^{-1} = \omega^{k-1}$ 。将两边求 $s$ 次幂，我们得到 $\omega^{-s} = \omega^{(k-1)s}$ 。

向量 $A$ 和 $B$ 的内积是

A \cdot B = (\omega^0)^r \cdot (\omega^0)^{-s} + \omega^r \cdot \omega^{-s} + ... + (\omega^{k-1})^r (\omega^{k-1})^{-s}

等价地，这可以写成

A \cdot B = (\omega^0)^{r-s} + \omega^{r-s} + ... + (\omega^{k-1})^{r-s}

用紧凑的符号表示， $A$ 和 $B$ 的内积可以写成

A \cdot B = \sum_{i=0}^{k-1} (\omega^{i})^{r-s}

因此，公式

\sum_{i=0}^{k-1} (\omega^{i})^{r-s}=\begin{cases}k, & \text{if } r\equiv s \pmod{k},\\[6pt]0, & \text{otherwise}.\end{cases}

可以理解如下：分量为 $k$ 次单位根的幂的两个向量的内积要么是 $k$ ，要么是零，这取决于指数 $r$ 和 $s$ 模 $k$ 是否同余。我们将在接下来的章节中使用这个事实。

本文是我们 ZK Book 中关于数论变换（Number Theoretic Transform）系列文章的一部分