1の冪根で数を振り分ける
概要
1 の冪根で数を振り分ける方法（roots of unity filter）は、多項式 $f(x)=\sum_k a_kx^k$ の係数のうち $k\equiv r\pmod n$ のものの和を、$1$ の原始 $n$ 乗根 $\zeta$ を使って $\frac1n\sum_{t=0}^{n-1}\zeta^{-tr}f(\zeta^t)$ として取り出す技法である。根拠は、$\zeta^{tk}$ の $t$ についての平均が $n\mid k$ なら $1$、そうでなければ $0$ になることである。$x=\pm1$ で偶数番目、$\omega$ で 3 つおき、$\pm i$ で 4 つおきの二項係数の和が求まる。この記事は、二項係数の和、一般の公式、巡回群の指標と直交関係、離散 Fourier 変換の反転公式の 4 本への案内である。
前提知識: 複素数, 二項定理, de Moivreの定理
1 の冪根で数を振り分ける
二項定理 $(1+x)^N=\sum_{k=0}^N\binom Nkx^k$ に $x=1$ と $x=-1$ を代入して足すと、奇数番目の二項係数が打ち消し合い、偶数番目だけが残る。$-1$ の代わりに、3 乗して $1$ になる虚数 $\omega$ を使うと、3 つおきの二項係数の和も取り出せる。この「$1$ の冪根での値の平均をとって、係数を添字の余りで振り分ける」方法を、1 の冪根による振り分け（1 の冪根フィルター、roots of unity filter）という。
この記事は、この方法を高校の計算から大学の概念（群の指標、離散 Fourier 変換）まで 4 本の記事でたどるための案内である。まず主題の定義と、代表的な計算を見る。
$n$ を正の整数とする。$z^n=1$ を満たす複素数 $z$ を $1$ の $n$ 乗根といい、$z^k=1$ となる最小の正の整数 $k$ が $n$ であるものを $1$ の原始 $n$ 乗根という。たとえば
$$
\zeta_n:=\cos\frac{2\pi}n+i\sin\frac{2\pi}n
$$
は $1$ の原始 $n$ 乗根である（このことは 1の冪根による振り分けの公式 で示す）。多項式 $f(x)=\sum_{k=0}^Ma_kx^k$ と整数 $r$ について、$k-r$ が $n$ で割り切れる（$k\equiv r\pmod n$）係数 $a_k$ だけを足した和を、余りが $r$ の係数の和という。
振り分けの公式は、$\zeta$ を $1$ の原始 $n$ 乗根とするとき
$$
\sum_{k\equiv r\ (\mathrm{mod}\ n)}a_k=\frac1n\sum_{t=0}^{n-1}\zeta^{-tr}f(\zeta^t)
$$
が成り立つ、というものである。$r=0$ なら右辺は $f(1),f(\zeta),\dots,f(\zeta^{n-1})$ の平均である。証明は 1の冪根による振り分けの公式 で行う。根拠は、$\zeta^{tk}$（$t=0,\dots,n-1$）の平均が $n\mid k$ なら $1$、そうでなければ $0$ になることである。
$n=2$ では $\zeta_2=-1$ である。$f(x)=(1+x)^6$ とすると $f(1)=2^6=64$、$f(-1)=0$ なので、
$$
\text{偶数番目の和}=\frac{f(1)+f(-1)}2=32,\qquad \text{奇数番目の和}=\frac{f(1)-f(-1)}2=32
$$
である。二項係数 $1,6,15,20,15,6,1$ を直接足すと、偶数番目は $1+15+15+1=32$、奇数番目は $6+20+6=32$ で一致する。
$n=3$ では $\zeta_3=\omega=\frac{-1+\sqrt3\,i}2$ で、$\omega^3=1$、$1+\omega+\omega^2=0$ である。$f(x)=(1+x)^6$ とすると、$1+\omega=-\omega^2$、$1+\omega^2=-\omega$ から
$$
f(\omega)=(-\omega^2)^6=\omega^{12}=1,\qquad f(\omega^2)=(-\omega)^6=\omega^6=1
$$
である。よって余りが $0$ の係数の和は
$$
\binom60+\binom63+\binom66=\frac{f(1)+f(\omega)+f(\omega^2)}3=\frac{64+1+1}3=22
$$
で、直接足した $1+20+1=22$ と一致する。
$n=4$ では $\zeta_4=i$ である。$f(x)=(1+x)^8$ とすると、$(1+i)^2=2i$ から $f(i)=(2i)^4=16$、同様に $(1-i)^2=-2i$ から $f(-i)=(-2i)^4=16$、また $f(-1)=0$ である。よって
$$
\binom80+\binom84+\binom88=\frac{256+16+0+16}4=72
$$
で、直接足した $1+70+1=72$ と一致する。$-1$ の冪は $\pm1$ しかとらないので、係数によらず成り立つ式としては、実数 $\pm1$ の代入だけでは 4 つおきには分けられず、虚数 $\pm i$ が必要になる（3 つおきの場合の詳しい説明は 二項係数を余りで分けた和 にある）。
図1：1 の 3 乗根と 1 の 4 乗根は正多角形の頂点で、その平均（重心）は原点である
図 1 は $1$ の 3 乗根 $1,\omega,\omega^2$ と、$1$ の 4 乗根 $1,i,-1,-i$ である。どちらも単位円に内接する正多角形の頂点で、重心は原点にある。このため $1+\omega+\omega^2=0$、$1+i+(-1)+(-i)=0$ となり、これが「$n$ の倍数でない番号の係数が平均で消える」理由である。
高校の計算と大学の概念
| 高校の計算 | 大学の概念 | 記事 |
|---|---|---|
| $x=\pm1$ を代入して足すと偶数番目だけが残る | $n=2$ の振り分け | 二項係数を余りで分けた和 |
| $x=1,\omega,\omega^2$ を代入して 3 つおきの和を出す | $n=3$ の振り分けと $\omega^3=1$ | 二項係数を余りで分けた和 |
| $1+\omega^k+\omega^{2k}$ は $3\mid k$ なら $3$、それ以外は $0$ | $1$ の $n$ 乗根の冪の和（等比数列の和） | 1の冪根による振り分けの公式 |
| 部分集合の和が $3$ の倍数になる個数を数える | 多項式 $\prod_j(1+x^j)$ の係数の振り分け | 1の冪根による振り分けの公式 |
| $\omega^{k+l}=\omega^k\omega^l$（余りの足し算が掛け算になる） | 巡回群 $\mathbb{Z}/n\mathbb{Z}$ の指標 | 巡回群の指標と直交関係 |
| 平均をとると余りが $r$ のものだけが残る | 指標の直交関係 | 巡回群の指標と直交関係 |
| $1$ の $n$ 乗根での値から係数を戻す | 離散 Fourier 変換の反転公式 | 離散Fourier変換と反転公式 |
| 多項式の積を $x^n=1$ として計算する | 巡回畳み込みと巡回行列 | 離散Fourier変換と反転公式 |
読む順番
- 二項係数を余りで分けた和：二項定理に $x=\pm1$、$x=1,\omega,\omega^2$、$x=\pm1,\pm i$ を代入して、偶数番目・3 つおき・4 つおきの二項係数の和を求める。$\omega$ の性質から一行ずつ証明し、3 つおきの和と $2^N/3$ のずれが周期 6 でくり返すことも見る。
- 1の冪根による振り分けの公式：一般の $n$ で、$1$ の原始 $n$ 乗根による振り分けの公式を証明する。部分集合の和の数え上げに使い、数学オリンピックの問題（国際数学オリンピック（1995 年）第 6 問）も扱う。原始的でない $1$ の冪根では振り分けられないことも示す。
- 巡回群の指標と直交関係：$k\mapsto\zeta^{tk}$ が「余りの足し算を掛け算に写す」ことを取り出して、巡回群 $\mathbb{Z}/n\mathbb{Z}$ の指標を定義し、指標がちょうど $n$ 個あることと直交関係を証明する。振り分けの公式が直交関係の特別な場合であることを見る。
- 離散Fourier変換と反転公式：長さ $n$ の数列の離散 Fourier 変換を定義し、反転公式と Parseval の等式を証明する。振り分けの公式は反転公式そのものであること、畳み込みが積に変わることを見て、巡回的な連立方程式（国際数学オリンピック（1963 年）第 4 問）に使う。
1 だけ読めば高校の計算の根拠が分かる。2 は 3・4 の前提である。4 は 3 の指標の言葉を使うので、3 のあとに 4 を読む。
疑問から記事を探すときは、次の表を使うとよい。疑問 答えのある記事 $\binom N0+\binom N3+\binom N6+\cdots$ はいくつか 二項係数を余りで分けた和 なぜ $\omega$ のような虚数を代入するのか 二項係数を余りで分けた和、1の冪根による振り分けの公式 3 つおきではなく、一般に $n$ つおきならどうするか 1の冪根による振り分けの公式 $1$ の $4$ 乗根なら $-1$ を使ってもよいか 1の冪根による振り分けの公式 要素の和が $p$ の倍数になる部分集合はいくつあるか 1の冪根による振り分けの公式 なぜ平均をとると、ある余りのものだけが残るのか 巡回群の指標と直交関係 $1$ の冪根での値だけから多項式の係数を戻せるか 離散Fourier変換と反転公式 輪になった連立方程式を見通しよく解けるか 離散Fourier変換と反転公式
関連する話題
- $\mathbb{Z}/n\mathbb{Z}$（$n$ で割った余りの世界）の足し算は、合同式と余りの世界 で詳しく扱う。
- 二項係数の恒等式は 二項定理と組合せの恒等式 にまとまっている。偶数番目と奇数番目の和の計算は、そこでも $x=\pm1$ の代入として現れる。
- 多項式に数を代入して係数についての情報を取り出す考え方は、母関数：数列を関数として扱う でも使う。
- 振り分けの公式を $n\to\infty$ の極限で見ると、三角関数の直交性と Fourier 級数になる（三角関数の直交性（高校数学））。
- 大学向けの説明は、指標については 指標(有限アーベル群)、離散 Fourier 変換については 離散Fourier変換 にある。
関連項目
- 前提: 複素数, 二項定理, de Moivreの定理
- 前に読む: 複素数の掛け算は回転と拡大, 二項定理と組合せの恒等式
- 次に読む（各論）: 二項係数を余りで分けた和, 1の冪根による振り分けの公式, 巡回群の指標と直交関係, 離散Fourier変換と反転公式
- 関連（高校数学）: 合同式と余りの世界, 母関数：数列を関数として扱う, 三角関数の直交性（高校数学）
- 比較: 1の冪根
- 発展: 指標(有限アーベル群), 離散Fourier変換, Fourier級数, 高速Fourier変換
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
