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 変換の反転公式と同じ仕組みである。
前提知識: 複素数, 二項定理, 複素数の掛け算は回転と拡大
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$ 乗根である（lem-ruf-sum の (1) で示す）。多項式 $f(x)=\sum_{k=0}^Ma_kx^k$ と整数 $r$ について、$k-r$ が $n$ で割り切れる（$k\equiv r\pmod n$）係数 $a_k$ だけを足した和を、余りが $r$ の係数の和という。
振り分けの公式とその証明
公式の根拠は、$\zeta^{tk}$（$t=0,\dots,n-1$）の平均が $n\mid k$ なら $1$、そうでなければ $0$ になることである。まずこれを示す。同じ主張と証明は各論の記事 1の冪根による振り分けの公式 の命題「原始 $n$ 乗根の冪が 1 になる条件」、補題「1 の $n$ 乗根の冪の和」、定理「1 の冪根による振り分けの公式」にもある。
$n$ を正の整数とする。
- $\zeta_n=\cos\frac{2\pi}n+i\sin\frac{2\pi}n$ は $1$ の原始 $n$ 乗根である。
- $\zeta$ を $1$ の原始 $n$ 乗根、$k$ を整数とすると
$$ \sum_{t=0}^{n-1}\zeta^{tk}=\begin{cases}n&(n\mid k)\\0&(n\nmid k)\end{cases} $$
が成り立つ。
- de Moivreの定理（複素数の掛け算は回転と拡大） により、正の整数 $k$ について $\zeta_n^k=\cos\frac{2\pi k}n+i\sin\frac{2\pi k}n$ である。これが $1$ になるのは $\cos\frac{2\pi k}n=1$ のとき、つまり $\frac{2\pi k}n$ が $2\pi$ の整数倍のとき、すなわち $n\mid k$ のときに限る。$n\mid k$ となる最小の正の整数 $k$ は $n$ なので、$\zeta_n$ は $1$ の原始 $n$ 乗根である。
- $w=\zeta^k$ とおくと、左辺は $1+w+w^2+\dots+w^{n-1}$ である（$\zeta\ne0$ なので $k$ が負でも $\zeta^k$ は意味をもつ）。
- $n\mid k$ のとき：$k=nm$ と書けて $w=(\zeta^n)^m=1^m=1$ なので、左辺は $1$ を $n$ 個足した $n$ である。
- $n\nmid k$ のとき：$k$ を $n$ で割って $k=nq+r$、$0< r< n$ と書く（$n$ で割り切れないので $r\ne0$）。$w=(\zeta^n)^q\zeta^r=\zeta^r$ で、$\zeta$ は原始 $n$ 乗根なので、$n$ より小さい正の $r$ について $\zeta^r\ne1$ である。よって $w\ne1$ で、等比数列の和の公式が使えて
$$ 1+w+\dots+w^{n-1}=\frac{w^n-1}{w-1} $$
である。$w^n=(\zeta^n)^k=1$ なので、分子は $0$ で、左辺は $0$ である。$\square$
$\zeta$ を $1$ の原始 $n$ 乗根、$f(x)=\sum_{k=0}^Ma_kx^k$ を多項式、$r$ を整数とする。このとき
$$
\sum_{k\equiv r\ (\mathrm{mod}\ n)}a_k=\frac1n\sum_{t=0}^{n-1}\zeta^{-tr}f(\zeta^t)
$$
が成り立つ。左辺は $0\le k\le M$ で $k\equiv r\pmod n$ となる $k$ についての和である。特に $r=0$ なら、右辺は $f(1),f(\zeta),\dots,f(\zeta^{n-1})$ の平均である。
$f(\zeta^t)=\sum_{k=0}^Ma_k\zeta^{tk}$ なので、右辺は
$$
\frac1n\sum_{t=0}^{n-1}\zeta^{-tr}\sum_{k=0}^Ma_k\zeta^{tk}=\frac1n\sum_{t=0}^{n-1}\sum_{k=0}^Ma_k\zeta^{t(k-r)}
$$
である。有限個の和なので、足す順番を入れ替えて $k$ ごとにまとめると
$$
\sum_{k=0}^Ma_k\cdot\frac1n\sum_{t=0}^{n-1}\zeta^{t(k-r)}
$$
となる。lem-ruf-sum の (2) を $k-r$ に使うと、$\frac1n\sum_t\zeta^{t(k-r)}$ は $n\mid k-r$ なら $1$、そうでなければ $0$ である。よって残るのは $k\equiv r\pmod n$ となる $a_k$ だけで、その和が左辺である。$\square$
$r=0$ のときの証明の中身は、「$n$ の倍数番目の係数は平均しても $1$ 倍のまま残り、ほかの係数は平均すると消える」ということである。$r\ne0$ のときは、$\zeta^{-tr}$ を掛けることで番号を $r$ だけずらし、余りが $r$ の係数を「$n$ の倍数番目」の位置へ動かしてから同じことをしている。
$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 の 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$ の倍数でない番号の係数が平均で消える」理由である。
条件を外すと崩れること
thm-ruf-filter では、$\zeta$ が原始 $n$ 乗根であることと、重み $\zeta^{-tr}$ を掛けることが効いている。どちらかを外すと答えが狂う。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| $\zeta$ が原始 $n$ 乗根 | $n=4$ で $\zeta=-1$、$f(x)=(1+x)^8$ とすると右辺は $128$ | 右辺が 4 つおきの和 $72$ になる |
| 重み $\zeta^{-tr}$ を掛ける | $n=3$、$r=1$、$f(x)=(1+x)^6$ で重みを省くと $22$ | 右辺が余り $1$ の係数の和 $21$ になる |
- 原始的でない $1$ の $4$ 乗根。 $\zeta=-1$ は $\zeta^4=1$ を満たすが、$\zeta^2=1$ なので原始 $4$ 乗根ではない。$f(x)=(1+x)^8$ で右辺を計算すると
$$ \frac{f(1)+f(-1)+f(1)+f(-1)}4=\frac{256+0+256+0}4=128 $$
で、これは偶数番目の和 $\binom80+\binom82+\dots+\binom88=128$ であり、4 つおきの和 $72$（ex-ruf-four）ではない。lem-ruf-sum の (2) で $k=2$ とすると、$4\nmid2$ なのに $\sum_{t=0}^3(-1)^{2t}=4\ne0$ となり、証明の「$w\ne1$」の段が崩れている。この反例は「$\zeta^n=1$ を満たせば振り分けられる」という含意を破る。 - 重みを省く。 $n=3$、$r=1$ で、余りが $1$ の二項係数の和は $\binom61+\binom64=6+15=21$ である。公式どおりに計算すると、$\omega^{-1}=\omega^2$、$\omega^{-2}=\omega$ と ex-ruf-three の $f(\omega)=f(\omega^2)=1$ から
$$ \frac{f(1)+\omega^{-1}f(\omega)+\omega^{-2}f(\omega^2)}3=\frac{64+\omega^2+\omega}3=\frac{64-1}3=21 $$
で合う。重み $\omega^{-t}$ を省くと $\frac{64+1+1}3=22$ となり、これは余りが $0$ の和である。重みは「どの余りを取り出すか」を指定している。
高校の計算と大学の概念
| 高校の計算 | 大学の概念 | 記事 |
|---|---|---|
| $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変換 にある。
関連項目
- 前提: 複素数, 二項定理, 複素数の掛け算は回転と拡大
- 前に読む: 複素数の掛け算は回転と拡大, 二項定理と組合せの恒等式
- 次に読む（各論）: 二項係数を余りで分けた和, 1の冪根による振り分けの公式, 巡回群の指標と直交関係, 離散Fourier変換と反転公式
- 関連（高校数学）: 合同式と余りの世界, 母関数：数列を関数として扱う, 三角関数の直交性（高校数学）
- 比較: 1の冪根
- 発展: 離散Fourier変換, Fourier級数, 高速Fourier変換
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
