1 の冪根の和と離散 Fourier 変換

$n$ を $q - 1$ の約数、$\alpha \in \mathbb{F}_q$ を位数 $n$ の元とする。

1. 整数 $s$ について、$\sum_{j=0}^{n-1}\alpha^{js}$ は $n \mid s$ のとき $n \cdot 1$、そうでないとき $0$ である。$n \cdot 1$ は $\mathbb{F}_q$ で $0$ でない。
2. $f = \sum_{l=0}^{n-1} f_l x^l \in \mathbb{F}_q[x]$ に対し $c_j = f(\alpha^j)$、$c(x) = \sum_{j=0}^{n-1}c_j x^j$ とおくと、すべての整数 $i$ について $c(\alpha^{i}) = n\, f_{l}$（$l$ は $0 \le l \le n-1$、$l \equiv -i \pmod n$ で定まる添字）である。