離散フーリエ変換の応用

　$x = (0,1,\cdots,n-1)^\intercal$ とする。 $\mathcal{F}$ を離散フーリエ変換とすれば、パーセバルの等式などにより、 $$ \sum_{k=0}^{n-1}\left|\sum_{j=0}^{n-1}j\xi^{jk}\right|^2 = \sum_{k=0}^{n-1}\left| (\mathcal{F}x)_k\right|^2 = \sum_{k=0}^{n-1}n\left| x_k\right|^2 = \sum_{k=0}^{n-1}n\left| k\right|^2 = \frac{n^2(n-1)(2n-1)}{6} $$

　和 $\displaystyle \sum_{k=1}^{n-1} \csc^4 \left( \frac{k\pi}{n} \right)$ を求めるために、$\cot \left( \frac{k\pi}{n} \right)$ を根に持つ多項式を構成する。 ド・モアブルの定理より、$(\cos \theta + \mathrm{i} \sin \theta)^n = \cos(n\theta) + \mathrm{i} \sin(n\theta)$ である。この虚部を取り出すと、 \[ \sin(n\theta) = \sum_{j: \text{odd}} \binom{n}{j} \cos^{n-j}\theta \cdot (\mathrm{i} \sin \theta)^{j-1} \cdot \sin \theta = \sin^n \theta \sum_{m=0}^{\lfloor \frac{n-1}{2} \rfloor} \binom{n}{2m+1} (-1)^m \cot^{n-2m-1} \theta \] となる。$1 \le k \le n-1$ に対して $\theta = \frac{k\pi}{n}$ とおくと $\sin(n\theta) = 0$ かつ $\sin \theta \neq 0$ であるから、 $z_k = \cot \left( \frac{k\pi}{n} \right)$ は次の $(n-1)$ 次方程式の根である。 \[ P(z) = \binom{n}{1} z^{n-1} - \binom{n}{3} z^{n-3} + \binom{n}{5} z^{n-5} - \dots = 0 \] 両辺を $n$ で割り、係数を整理すると、 \[ z^{n-1} - \frac{(n-1)(n-2)}{6} z^{n-3} + \frac{(n-1)(n-2)(n-3)(n-4)}{120} z^{n-5} - \dots = 0 \] を得る。解と係数の関係より、根の $2$ 乗和および $4$ 乗和を計算する。 $e_1 = \sum z_k^2$、 $e_2 = \sum_{i < j} z_i^2 z_j^2$ とおくと、上式の $z$ の奇数次の項が $0$ であることから $\sum z_k = 0$ であり、 \[ \sum_{k=1}^{n-1} z_k^2 = -2 \times \left( - \frac{(n-1)(n-2)}{6} \right) = \frac{(n-1)(n-2)}{3} \] 同様に、根の $4$ 乗和は $\sum z_k^4 = (\sum z_k^2)^2 - 2 \sum z_i^2 z_j^2$ として求められる。$x_k = z_k^2$ とおき、$x_k$ を根に持つ方程式の係数から、 \[ \sum_{k=1}^{n-1} z_k^4 = \left( \frac{(n-1)(n-2)}{3} \right)^2 - 2 \cdot \frac{(n-1)(n-2)(n-3)(n-4)}{30} = \frac{(n-1)(n-2)(n^2+3n-13)}{45} \] となる。

　関係 $\csc^2 \theta = 1 + \cot^2 \theta$ を用いると、$\csc^4 \theta = (1 + \cot^2 \theta)^2 = 1 + 2\cot^2 \theta + \cot^4 \theta$ である。 したがって、求める和は \[ \sum_{k=1}^{n-1} \csc^4 \left( \frac{k\pi}{n} \right) = \sum_{k=1}^{n-1} 1 + 2\sum_{k=1}^{n-1} z_k^2 + \sum_{k=1}^{n-1} z_k^4 \] \[ = (n-1) + \frac{2(n-1)(n-2)}{3} + \frac{(n-1)(n-2)(n^2+3n-13)}{45} \] これを整理すると、 \[ = \frac{n-1}{45} \left[ 45 + 30(n-2) + (n-2)(n^2+3n-13) \right] = \frac{(n^2-1)(n^2+11)}{45} = \frac{n^4 + 10n^2 - 11}{45} \] となる。$\square$

　正整数 $n$ に対して、次の和を考える。この和を二通りの方法で計算することにより証明する。 後述する補題より、この和の値は具体的に書き下すことができるから、以降は離散フーリエ変換によって変形していく。 \[ S(n) = \sum_{k=0}^{n-1} \left( \sum_{j=0}^{n-1} j \cdot (k-j) - nj \left\lfloor \frac{k-j}{n} \right\rfloor \right)^2 = \frac{n^3(n-1)(23n^3-67n^2+73n-17)}{360} \] 写像 $\rho_n:\mathbb{Z}\longrightarrow\{0,1,\dots,n-1\}$ を $n$ で割った余りを返す関数とする。 このとき、$$j \cdot (k-j) - nj \left\lfloor \frac{k-j}{n} \right\rfloor = j\left(\left(k-j\right) - n\left\lfloor \frac{k-j}{n} \right\rfloor\right) = j \rho_n(k-j)$$ である。 ベクトル \(x=(x_0,\dots,x_{n-1})\) を \(x_j=j\) と定める。 この際、添え字は $n$ を法として扱う。 内側の和を \(\displaystyle c_k=(x\ast x)_k=\sum_{j=0}^{n-1}x_j x_{k-j}\)と書けば、 求める和は \[ S(n)=\sum_{k=0}^{n-1}c_k^2 \] である。 ここで $\mathcal {F}$ を離散フーリエ変換とすれば、$\mathcal{F}c = \mathcal{F}x \odot \mathcal{F}x$ が成り立つ。パーセバルの等式などから、 $$\sum_{k=0}^{n-1}|c_k|^2 = \frac{1}{n}\sum_{k=0}^{n-1}|(\mathcal{F}c)_k|^2 = \frac{1}{n}\sum_{k=0}^{n-1}|(\mathcal{F}x)_k|^4$$ である。これより、$\mathcal{F}x$ を計算すればよい。

　離散フーリエ変換は \(\displaystyle (\mathcal{F}v)_k=\sum_{j=0}^{n-1} v_j \xi^{jk}\) （\(\xi=e^{2\pi\mathrm{i}/n}\)）であったから、ベクトル \(x\) に対して \(\displaystyle (\mathcal{F}x)_k=\sum_{j=0}^{n-1} j\xi^{jk}\) を計算する。 \(k=0\) のとき、 \((\displaystyle \mathcal{F}x)_0=\sum_{j=0}^{n-1}j=\dfrac{n(n-1)}{2}\) である。 \(k\ne0\) のとき \(r=\xi^k\) は \(r^n=1\) かつ \(r\ne1\) を満たすので、 \[ \sum_{j=0}^{n-1} j r^j=\frac{r-(n)r^n+(n-1)r^{n+1}}{(1-r)^2} \] に \(r^n=1,\ r^{n+1}=r\) を代入すると \[ \sum_{j=0}^{n-1} j r^j=\frac{n(r-1)}{(1-r)^2}=-\frac{n}{1-r}. \] よって \[ (\mathcal{F}x)_k= \begin{cases} \dfrac{n(n-1)}{2}, & k=0,\\[6pt] -\dfrac{n}{1-\xi^k}, & 1\le k\le n-1 \end{cases} \]

　いま、\(k\ne0\) に対し \(|1-\xi^k|^2=4\sin^2\!\bigl(\dfrac{\pi k}{n}\bigr)\) であるから \[ |(\mathcal{F}x)_k|^4 = \begin{cases} \dfrac{n^4(n-1)^4}{16}, & k=0,\\[6pt] \dfrac{n^4}{16}\csc^4\!\bigl(\dfrac{\pi k}{n}\bigr), & 1\le k\le n-1 \end{cases} \] を得る。これより、 \[ S(n)=\sum_{k=0}^{n-1}c_k^2=\frac{1}{n}\sum_{k=0}^{n-1} |(\mathcal{F}x)_k|^4 =\frac{n^3}{16}\Bigl((n-1)^4+\sum_{k=1}^{n-1}\csc^4\!\bigl(\tfrac{\pi k}{n}\bigr)\Bigr) \] が成り立つ。 ここで、後述の計算 \[ S(n) = \frac{n^3(n-1)(23n^3-67n^2+73n-17)}{360} \] を用いれば、\[ \sum_{k=1}^{n-1} \csc^4\left(\frac{k\pi}{n}\right) = \frac{n^4 + 10n^2 - 11}{45} \] を得る。

　内側の和 $c_k$ は\[c_k = \sum_{j=0}^{n-1} j \cdot \rho_n(k-j)\] であった。 $c_k$ を具体的に計算する。$\rho_n(k-j)$ は $j$ が $0$ から $n-1$ まで動くとき、$\{0, 1, \dots, n-1\}$ の値を一度ずつ異なる順序で取る。具体的には、$j \le k$ のとき $\rho_n(k-j) = k-j$ となり、$j > k$ のとき $\rho_n(k-j) = k-j+n$ となる。 これを用いて $c_k$ を分解すると、 \[c_k = \sum_{j=0}^{k} j(k-j) + \sum_{j=k+1}^{n-1} j(k-j+n) = \sum_{j=0}^{n-1} j(k-j) + n \sum_{j=k+1}^{n-1} j\] となる。それぞれの総和を計算して整理すると、次の結果を得る。 $$c_k = \frac{n}{6} (n^2 - 1 - 3k^2 + 3nk - 6k)$$ 求める値は $\displaystyle S(n) = \sum_{k=0}^{n-1} c_k^2$ であった。 \[S(n) = \frac{n^2}{36} \sum_{k=0}^{n-1} \left( 3k^2 - 3(n-2)k - (n^2-1) \right)^2\] この総和を計算するために、$k, k^2, k^3, k^4$ の和の公式を用いて計算をすると、 $$S(n) = \frac{n^3(n-1)(23n^3-67n^2+73n-17)}{360}$$ が得られる。$\square$