フーリエ解析の問題

添字は $\mathbb{Z}/16\mathbb{Z}$ の元とみなし、$x$ を周期 $16$ の数列に拡張して考える。

1. $|X_k{|}^2$ を自己相関の DFT として表す。 $x_n$ は実数なので
$$|X_k{|}^2=X_k\overline{X_k}=\sum _{n=0}^{15}\sum _{m=0}^{15}{x}_n{x}_m{\omega }^{-(n-m)k}.$$
$d=n-m(\mathrm{mod}16)$ でまとめると
$$|X_k{|}^2=\sum _{d=0}^{15}{r}_d{\omega }^{-dk},r_d=\sum _{m=0}^{15}{x}_{m+d}{x}_m$$
となる（巡回自己相関）。すなわち $Y_k=|X_k{|}^2$ は数列 $r=(r_d)$ の離散フーリエ変換である。

2. パーセバルの等式。 長さ $N$ の数列 $a$ とその DFT $A_k={\sum }_n{a}_n{\omega }^{-nk}$ に対し、${\sum }_{k=0}^{N-1}{\omega }^{-jk}=N[j\equiv 0]$ より
$$\sum _{k=0}^{N-1}|A_k{|}^2=N\sum _{n=0}^{N-1}|a_n{|}^2$$
が成り立つ。これを $a=r$, $A=Y$ に用いると
$$S=\sum _{k=0}^{15}|X_k{|}^4=\sum _{k=0}^{15}|Y_k{|}^2=16\sum _{d=0}^{15}{r}_d^2.$$

3. $r_d$ の計算。 $x$ は $\{0,1,2,3\}$ の指示関数なので、$r_d$ は集合 $\{0,1,2,3\}$ と $\{0,1,2,3\}-d(\mathrm{mod}16)$ の共通部分の要素数である。$4+3<16$ なので巡回による重なりは生じず
$$r_0=4,r_{\pm 1}=3,r_{\pm 2}=2,r_{\pm 3}=1,$$
それ以外の $d$（$d=4,5,\dots ,12$）では $r_d=0$ である（$r_{-d}$ は $r_{16-d}$ のこと）。よって
$$\sum _{d=0}^{15}{r}_d^2=4^2+2(3^2+2^2+1^2)=16+2\cdot 14=44.$$

4. 結論。
$$S=16\times 44=704.$$

（検算）$k=0$ のとき $X_0=4$ で $|X_0{|}^4=256$。$k\ne 0$ では $|X_k{|}^2=\frac{{\sin }^2(\pi k/4)}{{\sin }^2(\pi k/16)}$ であり、$k=4,8,12$ で $0$、偶数 $k=2,6,10,14$ の寄与の和は $96$、奇数 $k$ の寄与の和は $352$ と数値的に確かめられ、合計 $256+96+352=704$ と一致する。

$|X_k{|}^2$ は $x$ の円状自己相関 $r_m={\sum }_n{x}_n{x}_{n+m}$（添字は mod 16）の離散フーリエ変換であり、$|X_k{|}^4=|{\sum }_m{r}_m{\omega }^{-mk}{|}^2$ である。パーセバルの等式より ${\sum }_{k=0}^{15}|X_k{|}^4=16{\sum }_{m=0}^{15}{r}_m^2$。

$x$ は $n=0,1,2,3$ のみ 1 で、長さ 16 に対して台の幅 4 は十分小さいので巻き込みは起きない。よって $r_m=4-|m|$ $(|m|\le 3)$、それ以外は 0（$m$ は $-3,\dots ,3$ に対応）。すなわち $r_0=4,r_{\pm 1}=3,r_{\pm 2}=2,r_{\pm 3}=1$。

$\sum r_m^2=16+2(9+4+1)=16+28=44$。したがって $S=16\cdot 44=704$。

検算: $|X_k{|}^2={\left(\frac{\sin (\pi k/4)}{\sin (\pi k/16)}\right)}^2$。$k=0$ で $16^2=256$ が $|X_0{|}^4$ に寄与する。$|X_k{|}^2$ の総和は ${\sum }_k|X_k{|}^2=16\cdot 4=64$（パーセバル）で整合している。また $|X_k{|}^2=4+6\cos (\theta )+4\cos (2\theta )+2\cos (3\theta )$ ($\theta =2\pi k/16$) を 2 乗して 16 点で和をとると、定数項 $16+2(9+4+1)=44$ に 16 を掛けた 704 が得られ、一致する。