1の冪根による振り分けの公式

同義語：roots of unity filter formula

概要

前提知識: 二項係数を余りで分けた和, 複素数, de Moivreの定理, 等比数列

この記事で考えること

二項係数を余りで分けた和では、二項定理に $1,\omega,\omega^2$（$\omega=\frac{-1+\sqrt3\,i}2$）を代入して平均をとると、添字が 3 の倍数の二項係数だけが取り出せることを見た。この方法は二項係数に限らない。次の数え上げの問題にも使える。

和が 3 の倍数になる部分集合を数える

$\{1,2,3,4\}$ の部分集合（空集合も含めて $2^4=16$ 個）のうち、要素の和が 3 の倍数であるものを数える。全部書き出すと
$$ \emptyset,\quad\{3\},\quad\{1,2\},\quad\{2,4\},\quad\{1,2,3\},\quad\{2,3,4\} $$
の 6 個である（和はそれぞれ $0,3,3,6,6,9$）。$16$ の 3 分の 1 は $5.33\ldots$ なので、ちょうど 3 等分にはなっていない。

$\{1,\dots,9\}$ の部分集合（$512$ 個）になると、書き出すのは大変である。この記事では、$1$ の $n$ 乗根を使って、多項式の係数を「添字を $n$ で割った余り」で振り分ける公式を示し、このような数え上げに使う。数え上げを多項式の係数に置き換える考え方は母関数：数列を関数として扱うでも使い、部分集合の個数の数え方そのものは場合の数の数え方の体系で扱う。

問い	答えるボックス
3 乗根の $1,\omega,\omega^2$ に当たるものは、一般の $n$ では何か	def-rff-zeta
なぜ平均をとると係数が振り分けられるのか	lem-rff-sum
一般の多項式で、余りが $r$ の係数の和をどう取り出すか	thm-rff-filter
どんな $1$ の $n$ 乗根でもよいのか	ex-rff-nonprimitive
部分集合の和の問題にどう使うか	ex-rff-subsets-small-formula、ex-rff-subsets-nine

以下、整数 $k,r$ と正の整数 $n$ について、$k-r$ が $n$ で割り切れることを $k\equiv r\pmod n$ と書く（合同式と余りの世界）。$n$ が $k$ を割り切ることを $n\mid k$ と書く。

1 の $n$ 乗根

1 の $n$ 乗根と原始 $n$ 乗根

$n$ を正の整数とする。$z^n=1$ を満たす複素数 $z$ を $1$ の $n$ 乗根という。$z^k=1$ となる最小の正の整数 $k$ が $n$ であるとき、$z$ を $1$ の原始 $n$ 乗根という。特に
$$ \zeta_n:=\cos\frac{2\pi}n+i\sin\frac{2\pi}n $$
とおく。de Moivreの定理により $\zeta_n^t=\cos\frac{2\pi t}n+i\sin\frac{2\pi t}n$（$t$ は整数）であり、$\zeta_n^n=\cos2\pi+i\sin2\pi=1$ である。

小さい $n$ の 1 の冪根

$n=2$：$\zeta_2=\cos\pi+i\sin\pi=-1$。1 の 2 乗根は $1,-1$ で、原始 2 乗根は $-1$。
$n=3$：$\zeta_3=\cos\frac{2\pi}3+i\sin\frac{2\pi}3=\frac{-1+\sqrt3\,i}2=\omega$。
$n=4$：$\zeta_4=\cos\frac\pi2+i\sin\frac\pi2=i$。1 の 4 乗根は $1,i,-1,-i$ である。$i$ と $-i$ は原始 4 乗根だが、$-1$ は $(-1)^2=1$ なので原始 4 乗根ではない（原始 2 乗根である）。
$n=6$：$\zeta_6=\cos\frac\pi3+i\sin\frac\pi3=\frac{1+\sqrt3\,i}2$。$\zeta_6^2=\omega$、$\zeta_6^3=-1$ である。

原始 $n$ 乗根の冪が 1 になる条件

$\zeta$ を $1$ の原始 $n$ 乗根とする。整数 $k$ について、$\zeta^k=1$ であることと $n\mid k$ であることは同値である。さらに $\zeta_n$ は $1$ の原始 $n$ 乗根である。

余りに帰着する

段 1（$n\mid k$ なら $\zeta^k=1$）：$k=nm$（$m$ は整数）なら $\zeta^k=(\zeta^n)^m=1^m=1$ である。$\zeta\ne0$ なので $m<0$ でも負の冪は意味をもつ。
段 2（$\zeta^k=1$ なら $n\mid k$）：$k$ を $n$ で割って $k=nm+s$（$0\le s< n$）とする。段 1 と同じく $\zeta^{nm}=1$ なので $\zeta^k=\zeta^{nm}\zeta^s=\zeta^s$ である。$\zeta^k=1$ なら $\zeta^s=1$ である。もし $0< s< n$ なら、$\zeta^s=1$ となる $n$ より小さい正の整数 $s$ があることになり、「最小の正の整数が $n$」に反する。よって $s=0$、すなわち $n\mid k$ である。
段 3（$\zeta_n$ は原始 $n$ 乗根）：$\zeta_n^n=1$ である。$0< t< n$ なら偏角 $\frac{2\pi t}n$ は $0$ と $2\pi$ の間にあるので $\zeta_n^t=\cos\frac{2\pi t}n+i\sin\frac{2\pi t}n\ne1$ である。よって $\zeta_n^k=1$ となる最小の正の $k$ は $n$ である。$\square$

$m$ と互いに素な整数 $a$ の冪を $m$ で割った余りにも同じ形の性質（$a^k\equiv1\pmod m$ となるのは $k$ が $a$ の位数の倍数のときに限る）があり、冪の余りの周期と元の位数で扱う。

原始 $n$ 乗根の冪は 1 の $n$ 乗根をすべて与える

$\zeta$ を $1$ の原始 $n$ 乗根とすると、$\zeta^0,\zeta^1,\dots,\zeta^{n-1}$ は相異なり、$1$ の $n$ 乗根はちょうどこの $n$ 個である。

差の冪を見る

段 1（相異なる）：$0\le s< t\le n-1$ で $\zeta^s=\zeta^t$ とすると、両辺を $\zeta^s$ で割って $\zeta^{t-s}=1$ である。prop-rff-power-one により $n\mid t-s$ だが、$0< t-s< n$ なので矛盾する。
段 2（すべて）：$(\zeta^t)^n=(\zeta^n)^t=1$ なので、どの $\zeta^t$ も $1$ の $n$ 乗根である。一方、$n$ 次方程式 $z^n-1=0$ の解は高々 $n$ 個である（因数定理により、解が 1 つ見つかるごとに 1 次式で割れて次数が 1 下がる）。段 1 の $n$ 個で解はすべてである。$\square$

冪の和の補題

二項係数を余りで分けた和の「ふるい」$\frac13(1+\omega^k+\omega^{2k})$ を、一般の $n$ に広げる。

1 の $n$ 乗根の冪の和

$\zeta$ を $1$ の原始 $n$ 乗根とする。整数 $k$ について
$$ \frac1n\sum_{t=0}^{n-1}\zeta^{tk}=\begin{cases}1&(n\mid k)\\ 0&(n\nmid k)\end{cases} $$
である。

等比数列の和

$q:=\zeta^k$ とおくと、$\zeta^{tk}=q^t$ なので、和は初項 $1$、公比 $q$ の等比数列の $n$ 項の和 $1+q+\cdots+q^{n-1}$ である。
段 1（$n\mid k$ のとき）：prop-rff-power-one により $q=\zeta^k=1$ なので、和は $1$ を $n$ 個足した $n$ であり、$n$ で割ると $1$ である。
段 2（$n\nmid k$ のとき）：prop-rff-power-one により $q\ne1$ なので、等比数列の和の公式により和は $\dfrac{q^n-1}{q-1}$ である。ここで $q^n=\zeta^{kn}=(\zeta^n)^k=1$ なので、分子は $0$ であり、和は $0$ である。$\square$

証明で使った $\zeta$ の性質は「$\zeta^n=1$」と「$n\nmid k$ なら $\zeta^k\ne1$」の 2 つだけである。どちらかが欠けると補題は成り立たない（ex-rff-nonprimitive、ex-rff-not-root）。

補題を $n=4$ で確かめる

$\zeta=i$、$n=4$ とする。$i^0,i^1,i^2,i^3=1,i,-1,-i$ である。

$k=1$：$\frac14(1+i-1-i)=0$。
$k=2$：$i^{2t}=(-1)^t$ なので $\frac14(1-1+1-1)=0$。
$k=3$：$i^{3t}$ は $1,-i,-1,i$ なので $\frac14(1-i-1+i)=0$。
$k=4$：$i^{4t}=1$ なので $\frac14(1+1+1+1)=1$。

n = 6 のとき、k が 6 の倍数でなければ点は正多角形の頂点を均等にめぐり、平均は原点になる
図 1 は $n=6$、$\zeta=\zeta_6$ で、$t=0,\dots,5$ の $\zeta^{tk}$ を描いたものである。$k=1$ では正 6 角形の頂点、$k=2$ では正三角形の頂点をそれぞれ 2 回ずつ、$k=3$ では $\pm1$ を 3 回ずつめぐり、どれも平均（重心）は原点である。$k=6$ では 6 点がすべて $1$ に重なり、平均は $1$ である。
同じ「平均すると $0$ になる」計算を和の代わりに積分で行うと三角関数の直交性になり、三角関数の直交性（高校数学）で扱う。

主定理：振り分けの公式

1 の冪根による振り分けの公式

$f(x)=\sum_{k=0}^Ma_kx^k$ を複素数係数の多項式とし、$\zeta$ を $1$ の原始 $n$ 乗根（たとえば $\zeta=\zeta_n$）とする。整数 $r$ について、$k\equiv r\pmod n$ を満たす係数の和は
$$ \sum_{\substack{0\le k\le M\\ k\equiv r\ (\mathrm{mod}\ n)}}a_k=\frac1n\sum_{t=0}^{n-1}\zeta^{-tr}f(\zeta^t) $$
で与えられる。さらに、複素数 $x$ について $\displaystyle\sum_{k\equiv r}a_kx^k=\frac1n\sum_{t=0}^{n-1}\zeta^{-tr}f(\zeta^tx)$ が成り立つ。

和の順序を入れ替える

方針：右辺を展開し、lem-rff-sum のふるいを $k-r$ に使う。2 つ目の式を示せば、$x=1$ として 1 つ目の式を得る。
段 1（展開）：$f(\zeta^tx)=\sum_{k=0}^Ma_k\zeta^{tk}x^k$ なので
$$ \frac1n\sum_{t=0}^{n-1}\zeta^{-tr}f(\zeta^tx)=\frac1n\sum_{t=0}^{n-1}\sum_{k=0}^Ma_kx^k\zeta^{tk}\zeta^{-tr}=\frac1n\sum_{t=0}^{n-1}\sum_{k=0}^Ma_kx^k\zeta^{t(k-r)} $$
である。
段 2（和の順序の入れ替え）：有限個の和なので、$t$ と $k$ の和の順序を入れ替えてよい。
$$ =\sum_{k=0}^Ma_kx^k\cdot\Bigl(\frac1n\sum_{t=0}^{n-1}\zeta^{t(k-r)}\Bigr). $$
段 3（ふるい）：lem-rff-sum を整数 $k-r$ に使うと、括弧の中は $n\mid k-r$、すなわち $k\equiv r\pmod n$ のとき $1$、それ以外は $0$ である。よって右辺は $k\equiv r\pmod n$ の項 $a_kx^k$ だけの和である。$\square$

$r=0$ のときは、$\frac1n\bigl(f(1)+f(\zeta)+\cdots+f(\zeta^{n-1})\bigr)$、つまり「$1$ の $n$ 乗根での $f$ の値の平均」が、$n$ の倍数番目の係数の和になる（cor-rff-all-roots により $\zeta^0,\dots,\zeta^{n-1}$ は $1$ の $n$ 乗根の全体である）。$r\ne0$ のときの因子 $\zeta^{-tr}$ は、ずらし $x^{-r}f(x)$ の $n$ の倍数番目を取り出すことにあたる。

公式で $n=2,3$ に戻る

$n=2$、$\zeta=-1$、$r=0$：$\frac12\bigl(f(1)+f(-1)\bigr)$ が偶数番目の係数の和である。$f(x)=(1+x)^N$ なら $\frac12(2^N+0)=2^{N-1}$（$N\ge1$）。
$n=3$、$\zeta=\omega$：$\frac13\bigl(f(1)+\omega^{-r}f(\omega)+\omega^{-2r}f(\omega^2)\bigr)$ で、$f(x)=(1+x)^N$ とすれば二項係数を余りで分けた和の 3 つおきの公式の 1 つ目の形になる。

部分集合を公式で数える（{1, 2, 3, 4}）

$F(x):=(1+x)(1+x^2)(1+x^3)(1+x^4)$ を展開すると、$x^s$ の係数は「要素の和が $s$ の $\{1,2,3,4\}$ の部分集合」の個数である（各 $j$ について、入れないなら $1$、入れるなら $x^j$ を選んで掛けるから）。thm-rff-filter で $n=3$、$\zeta=\omega$ とする。

$F(1)=2^4=16$。
$F(\omega)$：$\omega^3=1$、$\omega^4=\omega$ なので $F(\omega)=(1+\omega)(1+\omega^2)(1+1)(1+\omega)$。$(1+\omega)(1+\omega^2)=1+\omega+\omega^2+\omega^3=0+1=1$ なので $F(\omega)=2(1+\omega)=2\cdot(-\omega^2)$。同様に $F(\omega^2)=2(1+\omega^2)=2\cdot(-\omega)$。
余り $0$：$\frac13\bigl(16-2\omega^2-2\omega\bigr)=\frac13(16+2)=6$。
余り $1$：$\omega^{-1}F(\omega)=\omega^{-1}\cdot(-2\omega^2)=-2\omega$、$\omega^{-2}F(\omega^2)=\omega^{-2}\cdot(-2\omega)=-2\omega^{-1}=-2\omega^2$ なので、$\frac13\bigl(16-2\omega-2\omega^2\bigr)=\frac13(16+2)=6$。
余り $2$：$\omega^{-2}F(\omega)=\omega^{-2}\cdot(-2\omega^2)=-2$、$\omega^{-4}F(\omega^2)=\omega^{-4}\cdot(-2\omega)=-2\omega^{-3}=-2$ なので、$\frac13(16-2-2)=4$。
余り $0$ は 6 個で、ex-rff-subsets-small の書き出しと一致する。$6+6+4=16$ である。

部分集合を公式で数える（{1, …, 9}）

$\{1,2,\dots,9\}$ の部分集合のうち、要素の和が 3 の倍数であるものの個数を求める。$F(x):=\prod_{j=1}^9(1+x^j)$ とすると、求める個数は $\frac13\bigl(F(1)+F(\omega)+F(\omega^2)\bigr)$ である。$F(1)=2^9=512$。$j=1,\dots,9$ を 3 で割った余りは $1,2,0$ がそれぞれ 3 回ずつなので、$\omega^j$ は $\omega,\omega^2,1$ がそれぞれ 3 回ずつ現れ、
$$ F(\omega)=\bigl((1+\omega)(1+\omega^2)(1+1)\bigr)^3=(1\cdot2)^3=8 $$
である。同様に $F(\omega^2)=8$ である。よって個数は $\frac{512+8+8}3=176$ である。余りが $1$ の個数は $\frac13\bigl(512+8\omega^{-1}+8\omega^{-2}\bigr)=\frac13(512+8\omega^2+8\omega)=\frac{512-8}3=168$、余り $2$ も同じく $168$ である。

部分集合の要素の和を 3 で割った余りの分布。どちらもほぼ 3 等分だが、少しずれる
図 2 は 2 つの例の分布である。どちらも、部分集合の個数の 3 分の 1 である $\frac{2^4}3=5.33\ldots$ と $\frac{2^9}3=170.66\ldots$（破線）の近くにあるが、ちょうど 3 等分ではない。ずれは $F(\omega)$ と $F(\omega^2)$ から来る。

二項係数の一般の式

二項係数を余りで分けた和の 3 つおき・4 つおきの式は、次の一般の式の特別な場合である。

二項係数の振り分けの一般式

$N\ge0$、$n\ge1$、整数 $r$ について（$0^0=1$ とする）
$$ \sum_{\substack{0\le k\le N\\ k\equiv r\ (\mathrm{mod}\ n)}}\binom Nk=\frac1n\sum_{t=0}^{n-1}\Bigl(2\cos\frac{\pi t}n\Bigr)^N\cos\frac{\pi t(N-2r)}n $$
である。

半分の角で因数分解する

段 1（半分の角）：$\zeta=\zeta_n$、$\theta_t:=\frac{\pi t}n$、$w_t:=\cos\theta_t+i\sin\theta_t$ とおく。de Moivre の定理により $w_t^2=\cos2\theta_t+i\sin2\theta_t=\zeta^t$、$w_t^{-1}=\cos\theta_t-i\sin\theta_t$ である。よって
$$ 1+\zeta^t=w_t\bigl(w_t^{-1}+w_t\bigr)=w_t\cdot2\cos\theta_t $$
である。
段 2（各項）：thm-rff-filter を $f(x)=(1+x)^N$ に使う。$\zeta^{-tr}=w_t^{-2r}$ なので、$t$ 番目の項は
$$ \zeta^{-tr}(1+\zeta^t)^N=w_t^{-2r}\,w_t^N(2\cos\theta_t)^N=(2\cos\theta_t)^N\bigl(\cos(N-2r)\theta_t+i\sin(N-2r)\theta_t\bigr) $$
である。
段 3（実部）：左辺の和は二項係数の和なので実数である。両辺の実部をとって主張の式を得る。$\square$

一般式を確かめる（$N=6$, $n=6$, $r=0$）

左辺は $\binom60+\binom66=2$ である。右辺の各項 $\bigl(2\cos\frac{\pi t}6\bigr)^6\cos\pi t$ は
$$ t=0:\ 64,\quad t=1:\ (\sqrt3)^6\cdot(-1)=-27,\quad t=2:\ 1^6\cdot1=1,\quad t=3:\ 0^6\cdot(-1)=0,\quad t=4:\ (-1)^6\cdot1=1,\quad t=5:\ (-\sqrt3)^6\cdot(-1)=-27 $$
で、和は $64-27+1+0+1-27=12$、$6$ で割って $2$ となり一致する。

$n=3$ の場合に戻る

$n=3$ では、$t=1$ の項が $\bigl(2\cos\frac\pi3\bigr)^N\cos\frac{(N-2r)\pi}3=\cos\frac{(N-2r)\pi}3$、$t=2$ の項が $(-1)^N\cos\frac{2(N-2r)\pi}3$ である。$m:=N-2r$ とおくと $(-1)^N=(-1)^m$ で、$(-1)^m\cos\frac{2m\pi}3=\cos\bigl(\frac{2m\pi}3+m\pi\bigr)=\cos\bigl(2m\pi-\frac{m\pi}3\bigr)=\cos\frac{m\pi}3$ となる。よって一般式は $\frac13\bigl(2^N+2\cos\frac{(N-2r)\pi}3\bigr)$ になり、二項係数を余りで分けた和の 3 つおきの式と一致する。

例と反例

外した仮定	崩れる結論	ボックス
$\zeta$ が原始 $n$ 乗根（$n\nmid k$ なら $\zeta^k\ne1$）	冪の和の平均が「$n\mid k$ なら $1$、そうでなければ $0$」	ex-rff-nonprimitive
$\zeta^n=1$	同上	ex-rff-not-root

反例：原始的でない 1 の冪根では振り分けられない

$n=4$ で、$\zeta_4=i$ の代わりに $-1$（これも $1$ の 4 乗根だが原始 4 乗根ではない）を使う。$\frac14\sum_{t=0}^3(-1)^{tk}$ は、$k$ が偶数なら $\frac14(1+1+1+1)=1$、奇数なら $\frac14(1-1+1-1)=0$ である。たとえば $k=2$ では $4\nmid2$ なのに平均が $1$ になり、lem-rff-sum の結論が破れる。$-1$ の冪は $1,-1$ の 2 つの値しかとらず、$1$ の 4 乗根の全体を尽くさないからである。仮定「$n\nmid k$ なら $\zeta^k\ne1$」（$\zeta$ が原始 $n$ 乗根であること）を外すと、振り分けの公式は $4$ つおきではなく $2$ つおきの和を返してしまう。$\binom N0+\binom N4+\binom N8+\cdots$ を求めるには、虚数の $\pm i$ が必要である。

反例：1 の冪根でない数では振り分けられない

$n=3$ で $\zeta=2$ とする。$2^k\ne1$（$k\ne0$）なので「$3\nmid k$ なら $\zeta^k\ne1$」は満たすが、$2^3=8\ne1$ で $\zeta^n=1$ を満たさない。$k=1$ では $\frac13(1+2+4)=\frac73\ne0$ となり、lem-rff-sum の結論が破れる。証明の段 2 で使った $q^n=1$ が成り立たないからである。

数学オリンピックの問題から

1995 年第 6 問：和が $p$ の倍数になる部分集合

ex-rff-subsets-nine と同じ「部分集合の和を余りで数える」問題で、個数が $p$ 元に限られている。

国際数学オリンピック（1995 年）第 6 問

$p$ を奇素数とする。$\{1,2,\dots,2p\}$ の $p$ 個の要素からなる部分集合 $A$ のうち、要素の和が $p$ で割り切れるものはいくつあるか。
出典：国際数学オリンピック（1995 年）第 6 問（第 2 日第 3 問、Oly95）。和訳は本記事による。

$p=3$ で数えてみる

$p=3$ では、$\{1,\dots,6\}$ の 3 元部分集合 $\binom63=20$ 個のうち、和が 3 の倍数のものは
$$ \{1,2,3\},\ \{1,2,6\},\ \{1,3,5\},\ \{1,5,6\},\ \{2,3,4\},\ \{2,4,6\},\ \{3,4,5\},\ \{4,5,6\} $$
の 8 個である（和は $6,9,9,12,9,12,12,15$）。答の式 $\frac1p\bigl(\binom{2p}p-2\bigr)+2$ は $p=3$ で $\frac{20-2}3+2=8$、$p=5$ で $\frac{252-2}5+2=52$ である。

高校数学で解く

方針：前半 $H_1:=\{1,\dots,p\}$ の中だけを 1 つずつずらす操作で、集合を $p$ 個ずつの組に分け、各組にちょうど 1 個の答があることを示す。後半を $H_2:=\{p+1,\dots,2p\}$ とする。
段 1（$H_1$ と $H_2$）：$H_1$ の和は $\frac{p(p+1)}2$、$H_2$ の和は $p\cdot p+\frac{p(p+1)}2$ である。$p$ は奇数なので $\frac{p+1}2$ は整数であり、どちらの和も $p$ の倍数である。
段 2（それ以外の集合）：$A$ を $H_1,H_2$ 以外の $p$ 元部分集合とし、$j:=(A\cap H_1\text{ の要素の個数})$ とおく。$j=0$ なら $A\subset H_2$ で要素が $p$ 個なので $A=H_2$、$j=p$ なら $A=H_1$ となるから、$0< j< p$ である。
段 3（ずらす操作）：$A\cap H_1$ の要素だけを $H_1$ の中で $1\to2\to\cdots\to p\to1$ と 1 つずつ進め、$A\cap H_2$ はそのままにした集合を $TA$ とする。$TA$ も $p$ 元部分集合で、$TA\cap H_1$ の個数は $j$ のままである。和の変化を見ると、$a< p$ の要素は $1$ 増え、$p\to1$ の要素は $p-1$ 減るが、$-(p-1)=-p+1$ なので $p$ で割った余りでは $+1$ と同じである。よって $TA$ の和は、$A$ の和に $j$ を足したものと $p$ を法として合同である。
段 4（$p$ 個の組）：$A,TA,T^2A,\dots,T^{p-1}A$ の和は、$A$ の和を $s$ として、$p$ を法として $s,s+j,s+2j,\dots,s+(p-1)j$ である。$0\le a< b\le p-1$ で $s+aj\equiv s+bj$ なら $p\mid(b-a)j$ であり、$p$ は素数で $0< j< p$ なので $p\mid b-a$ となるが、$0< b-a< p$ なので矛盾する。したがってこの $p$ 個の和は $p$ で割った余りがすべて異なり、ちょうど 1 つだけが $p$ の倍数である。和が異なるので、この $p$ 個の集合も相異なる。また $H_1$ の要素を $p$ 回進めると元に戻るので $T^pA=A$ である。
段 5（数える）：$T^pA=A$ なので、$B=T^aA$ なら $B,TB,\dots,T^{p-1}B$ は $A,TA,\dots,T^{p-1}A$ を並べ替えたものである。したがって $H_1,H_2$ 以外の $\binom{2p}p-2$ 個の集合は、段 4 の $p$ 個ずつの組に重なりなく分かれ、各組にちょうど 1 個の答がある。$H_1,H_2$ を加えて、答は
$$ \frac1p\Bigl(\binom{2p}p-2\Bigr)+2 $$
である。$\square$

大学数学で見ると

2 変数の多項式 $F(x,y):=\prod_{j=1}^{2p}(1+xy^j)$ を展開すると、$x^py^s$ の係数は「$p$ 元部分集合で和が $s$ のもの」の個数である。$y$ について thm-rff-filter を使う（$x$ は文字のまま。証明は係数ごとに同じように通る）。$\zeta=\zeta_p$ とし、$[x^p]G$ で $G$ の $x^p$ の係数を表すと、求める個数は $\frac1p\sum_{t=0}^{p-1}[x^p]F(x,\zeta^t)$ である。

$t=0$：$F(x,1)=(1+x)^{2p}$ で、$x^p$ の係数は $\binom{2p}p$。
$t\ne0$：$p\nmid t$ なので、$j=1,\dots,2p$ について $tj$ を $p$ で割った余りは $0,\dots,p-1$ をちょうど 2 回ずつとる。よって $F(x,\zeta^t)=\bigl(\prod_{m=0}^{p-1}(1+x\zeta^m)\bigr)^2$ である。cor-rff-all-roots により $\zeta^0,\zeta^1,\dots,\zeta^{p-1}$ は $z^p-1=0$ の $p$ 個の相異なる解である。因数定理により、$z^p-1$ は $z-\zeta^0$ で割り切れ、その商は残りの解 $\zeta^1,\dots,\zeta^{p-1}$ でも $0$ になる（$\zeta^m-\zeta^0\ne0$ なので）から、続けて $z-\zeta^1$ でも割り切れる。これをくり返すと $z^p-1$ は $\prod_{m=0}^{p-1}(z-\zeta^m)$ で割り切れる。両辺はどちらも $p$ 次で最高次の係数が $1$ なので、商は $1$ であり、$z^p-1=\prod_{m=0}^{p-1}(z-\zeta^m)$ である（因数定理は剰余の定理と因数定理で扱う）。ここに$z=-\frac1x$（$x\ne0$）を代入して両辺に $(-x)^p$ を掛けると、左辺は $(-x)^p\bigl((-\frac1x)^p-1\bigr)=1-(-x)^p=1+x^p$（$p$ が奇数なので $(-x)^p=-x^p$）、右辺は $\prod_m(-x)\bigl(-\frac1x-\zeta^m\bigr)=\prod_m(1+x\zeta^m)$ となる。両辺は多項式で、$0$ でないすべての $x$ で等しいので、多項式として $1+x^p=\prod_m(1+x\zeta^m)$ である。したがって $F(x,\zeta^t)=(1+x^p)^2$ で、$x^p$ の係数は $2$ である。
個数は $\frac1p\bigl(\binom{2p}p+2(p-1)\bigr)$ で、高校数学の答と一致する。2 つの解き方は表裏である。高校の解法は群 $\mathbb{Z}/p\mathbb{Z}$ が操作 $T$ で集合に作用するときの「軌道」への分割であり、大学の見方は $\mathbb{Z}/p\mathbb{Z}$ の指標（巡回群の指標と直交関係）による振り分けである。$t\ne0$ の $p-1$ 個の項がすべて $2$ なのは、$T$ で動かない集合 $H_1,H_2$ の 2 個だけが寄与することの表れである。

さらに先へ

ふるい $\frac1n\sum_t\zeta^{tk}$ は、群 $\mathbb{Z}/n\mathbb{Z}$ の指標の直交関係の最も簡単な場合である（巡回群の指標と直交関係）。
「$1$ の $n$ 乗根での値」から「余りごとの係数の和」を取り出す操作は、離散 Fourier 変換の反転公式そのものである（離散Fourier変換と反転公式）。
同じ証明は、$f$ が冪級数で $|x|$ が収束半径より小さいときも、絶対収束する級数の和の入れ替えで通る（本記事では詳細を省く）。