フーリエ解析の問題

添字は $\mathrm{mod}8$ で考える（$x_{n+8}=x_n$）。

手順 1: $|X_k{|}^2$ を自己相関の DFT として表す。

自己相関を
$$r_m=\sum _{n=0}^7{x}_{n+m}\overline{x_n}(m\in \mathbb{Z}/8\mathbb{Z})$$
と定める。これは $x$ と ${\tilde{x}}_n=\overline{x_{-n}}$ の巡回畳み込み $r=x\ast \tilde{x}$ であり、$\tilde{x}$ の DFT は $\overline{X_k}$ である。巡回畳み込みの DFT は DFT の積になるので
$$R_k=\sum _{m=0}^7{r}_m{\omega }^{-mk}=X_k\overline{X_k}=|X_k{|}^2.$$

手順 2: パーセバルの等式を $r$ に使う。

離散パーセバルの等式 ${\sum }_k|R_k{|}^2=N{\sum }_m|r_m{|}^2$ より
$$\sum _{k=0}^7|X_k{|}^4=\sum _{k=0}^7|R_k{|}^2=8\sum _{m=0}^7|r_m{|}^2.$$

手順 3: 自己相関を計算する。

$x$ が $0$ でないのは $n=0,1,2$ だけで、ずれが $8$ を一周して重なることはない。
- $r_0=1^2+2^2+1^2=6$
- $r_1=x_1{x}_0+x_2{x}_1=2\cdot 1+1\cdot 2=4$、同様に $r_{-1}=r_7=4$
- $r_2=x_2{x}_0=1$、同様に $r_{-2}=r_6=1$
- そのほかの $m$（$m=3,4,5$）では $r_m=0$

よって
$$\sum _m|r_m{|}^2=6^2+2\cdot 4^2+2\cdot 1^2=36+32+2=70.$$

手順 4: 結論。
$$\sum _{k=0}^7|X_k{|}^4=8\times 70=560.$$

（検算: $X_k=1+2{\omega }^{-k}+{\omega }^{-2k}={\omega }^{-k}(2+2\cos \frac{\pi k}{4})$ より $|X_k|=4{\cos }^2\frac{\pi k}{8}$。$k=0,\dots ,7$ で $|X_k{|}^4$ を足すと $256\cdot \frac{35}{16}=560$ となり一致する。）

$x$ の生成多項式は $1+2z+z^2=(1+z{)}^2$ なので、$z={\omega }^{-k}=e^{-i{\theta }_k}$（${\theta }_k=2\pi k/8$）として $X_k=(1+z{)}^2$ である。よって $|X_k{|}^4=|1+z{|}^8$。$|1+e^{-i\theta }{|}^2=2+2\cos \theta$ より $|X_k{|}^4=(2+2\cos {\theta }_k{)}^4=16(1+\cos {\theta }_k{)}^4$。\n\n展開すると $(1+c{)}^4=1+4c+6c^2+4c^3+c^4$（$c=\cos {\theta }_k$）。$m=1,2,3,4$ について ${\sum }_{k=0}^7\cos (m{\theta }_k)$ は $m=4$ のとき $\sum (-1{)}^k=0$ など、$8\nmid m$ ならすべて $0$（$m\le 4<8$）。${\cos }^2\theta =\frac{1+\cos 2\theta }{2}$、${\cos }^4\theta =\frac{3+4\cos 2\theta +\cos 4\theta }{8}$ より、${\sum }_{k}c=0$、${\sum }_k{c}^3=0$、${\sum }_k{c}^2=8\cdot \frac{1}{2}=4$、${\sum }_k{c}^4=8\cdot \frac{3}{8}=3$。\n\n${\sum }_k(1+c{)}^4=8+6\cdot 4+3=35$。したがって ${\sum }_k|X_k{|}^4=16\cdot 35=560$。\n\n別解（検算）: パーセバルの定理より ${\sum }_k|X_k{|}^4=N{\sum }_m|r_m{|}^2$（$r$ は巡回自己相関）。$x$ の台の長さは 3 で巡回の折り返しは起きないので $r_0=1+4+1=6$、$r_{\pm 1}=2+2=4$、$r_{\pm 2}=1$。$\sum |r_m{|}^2=36+16+16+1+1=70$、$8\cdot 70=560$。一致する。