有限傅里叶(Fourier)变换由加法相位构成;乘法特征标则记录有限域中的乘法。二者的相互作用出乎意料地严格:一个非平凡乘法特征标变换为其共轭,再乘以一个高斯(Gauss)和。这个事实可以把有限域计数问题化为简短的傅里叶计算。
令 为奇素数,。写 ,其中 是某个剩余类的任意整数代表。对 ,使用未归一化的加法变换
定义 1.12.1
(乘法特征标与高斯和)
乘法特征标是同态 ,并通过 延拓。若它在 上不恒等于一,就称为非平凡特征标。它的高斯和是
由于乘法群有限,每个非零特征标值都是单位根,模为一;特别地,对 有 。
定理 1.12.2
(特征标变换为其共轭)
对非平凡乘法特征标 及每个 ,
当 时,两边都使用 。这个公式给出高斯和的模,一般不能确定其复相位。
证明
(对加法频率作缩放)
非平凡性提供 ,使 。乘以 置换非零剩余类,所以
因此该和为零。这证明了 时的 (2)。当 时,代换 。由于 ,
有限傅里叶正交性在这个归一化下给出帕塞瓦尔(Parseval)公式:
零频率项为零,其余 项的模都为 。因此 。
证明透视
加法和乘法各自发挥不同作用
是关于 的加法特征标,而 在非零剩余类上是乘法性的。关键一步是把 乘以 ,把一者转成另一者: 之所以是固定 的 双射,只因 可逆;把 从和中提出,则用到乘法性与 。
非平凡性恰好只用一次,就在 :那里代换不可用,变换化为单纯的特征标和。模的计算最后靠计数收尾:帕塞瓦尔公式固定总能量 , 的公式去掉一项,而由于 ,其余 项的模都等于 。若 项不为零,能量就不会平均分配,也推不出 这个值。
例题 1.12.3
(五元域上的四次特征标)
在 中,元素 生成整个群:它的逐次幂是 。定义 ;乘法性迫使 、、。令 ,
这里用到 、 及 。由于 、,
与 (2) 的预测一致。同一定理给出 ,因为 。
常见错误
(在变换中漏掉共轭)
很容易写成 。对上面的四次特征标,这会给出 ;但代换 给出 。只有当 为实数时,例如下面的二次特征标,两者才一致。
二次特征标与相位约束
定义 1.12.4
(二次特征标)
令 ;对 ,若 是 中的平方则令 ,否则令其为 。
这是非平凡乘法特征标:取 的生成元 ,平方恰好是 的偶数次幂,因此 。此外,
因为 。有限域傅里叶变换章节构造过素域生成元。
定理 1.12.5
(二次高斯和的平方被确定)
令 ,则
因此,当 时, 是 之一;当 时,它是 之一。这个论证不选择符号。
证明
(取共轭并将 a 换成负 a)
由于 为实值,
第一个定理给出 ,而 。因此 ,证明 (4)。由 (3) 得到两种情形。
例题 1.12.6
(三个元素的域)
对 ,、,直接计算得到
这里 ,确实有 。直接计算在这个例子中选出了符号;仅靠 (4) 不能为所有素数选择符号。
反例模式
平凡特征标的变换不同
令 ()且 。那么 ,而 。因此 (2) 在零点失效,高斯和的模为 而不是 。非平凡性是必要的。
对二次方程计数
定理 1.12.7
(有限域圆上的点数)
对 ,令 为满足 的有序对 的个数。那么
证明
(用加法正交性强制方程成立)
对任意 , 在 时为一,否则为零。因此记 ,有
显然 。对每个剩余类 ,方程 有 个解,包括 。若 ,先对 求和,得到
常数部分 ()由加法正交性消失,对实值二次特征标可应用 (2)。因此,对每个非零 ,。代入 (6) 后剩下 。最后的和在 时为 ,在 时为 ,证明 (5)。
例如,当 时,(5) 给出 ,而两个非零 都满足 。当 时,,每个非零 都有 。被计数的是普通整数个数;方程本身则在 中。
例题 1.12.8
(直接验证 的计数)
这时 ,所以 (5) 预测 ,而 时 。 中的平方是 (来自 )、(来自 )、(来自 )和 (来自 )。
对 ,和为 的平方对是 、 和 ,因为 ;剩下的第一分量 需要第二分量 ,而 不是平方。按根数计算得 个有序对。对边界情形 ,若有 的解,就会有 ,但 不是平方,所以只剩 ,。两个值都与 (5) 一致。
常见错误
(把 当作一)
正是约定 ,才使 对每个 都数出 的根数,包括只有唯一根 的 。若令 ,那里就会数出两个根;而且 会变成 而不是 ,(2) 在 的情形也会失效。
练习
快速检查
(为什么非平凡乘法特征标在 上求和为零?)
解答 · 答案
选择使 的 。乘以 置换该域,因此和等于自身的 倍,只能为零。
快速检查
(对 ,求 、 和 。(4) 是否确定 的符号?)
解答 · 答案
、、。方程 (4) 留下 两种可能。
快速检查
(对 ,利用 (5) 求 和 时的 。)
解答 · 答案
,所以 ,而 时 。
快速检查
(为什么对每个 , 都有 个解?)
解答 · 答案
非零平方恰有两个根 ,因为 为奇数;非平方没有根,零有唯一根零。它们分别是 、 和 。
快速检查
(如果 在 上是平凡特征标,第一个证明中的哪一步失效?)
解答 · 答案
不存在满足 的 ,所以抵消论证无法开始。事实上它在整个域上的和是 而不是零。