有限傅立葉(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) 求 和 時的 。)
解答 · 答案
,所以 ,而 時 。
快速檢查
(為甚麼對每個 , 都有 個解?)
解答 · 答案
非零平方恰有兩個根 ,因為 為奇數;非平方沒有根,零有唯一根零。它們分別是 、 和 。
快速檢查
(如果 在 上是平凡特徵標,第一個證明中的哪一步失效?)
解答 · 答案
不存在滿足 的 ,所以抵消論證無法開始。事實上它在整個域上的和是 而不是零。