• 유한체 $$\mathbb F_q$$ 위에서 작동한다.

• 동차 선형 점화 수열 $$s_n$$이 주어지면 해당 수열을 생성하는 $k$차 동차 선형 점화식을 반환하는 알고리즘이다.

• 시간 복잡도는 $$\mathcal O (N^2)$$이다.

• 주어진 수열을 순회하며 연산한다.

본 글에서 다루는 알고리즘은 원래 BMA와는 약간 다르다. DP에서 활용할 수 있는 형태의 점화식 계수 수열을 반환하는 것을 목표로 하기에 계수의 부호 등 일부는 원래 BMA의 그것과 정반대이고, 계수 다항식이 아니라 수열을 사용한다. 원래 BMA의 방식을 정확히 알고 싶다면 다른 문서를 참고하길 바란다.

각 단계 $$n; (n=0,1,2,\cdots)$$마다 $n$까지의 최적 선형 점화식 계수 수열 $C_n={c_i^{n}}$과 그 길이인 $$L_n$$이 존재한다. $c_1^n, c_2^n,\cdots,c_{L_n}^n$이 최종적으로 구한 선형 점화식의 계수가 될 것이다.

$$c_0^0=-1,$$ 모든 $n\neq 0$에 대해 $$c_n^0=0, ; L_0 = 0$$으로 설정한다.

이를 이용해 $$s_n$$을 예측한다. 예측값 $$\hat s_n=\displaystyle\sum_{i=1}^{L_n}c_i^ns_{n-i}$$이다.

오차 $d_n$을 계산한다. $d_n = s_n - \hat s_n$이다.

만약 $d_n = 0$이라면 $C_n$이 $s_n$을 완벽히 예측한 것이다. 점화식을 수정할 필요가 없으므로 $C_{n+1} = C_n, L_{n+1} = L_n$으로 설정하고 다음 $n$으로 넘어간다.

$d_n \neq 0$이라면 $C_n$을 수정해야 한다. 이를 위해 새로운 변수 $m$을 사용해야 한다.

$m$은 이전에 오류가 발생했던 인덱스, 즉 $d_m \neq 0$이며 $n - m$이 최소인 수이다.

$m$을 사용해 $C_{n+1}$을 새롭게 설정한다.

해당 식은 $$c_i^{n+1} = c_i^n - \displaystyle\frac{d_n}{d_m}c^m_{i-n+m}$$이다.

어떻게 새로 만든 $C_{n+1}$이 올바르다고 보장할 수 있을까? $C_{n+1}$은 $$L_{n+1} \leq N \leq n$$인 모든 $N$에 대해 $$s_N = \displaystyle\sum^{L_{n+1}}{i=1}{c_i^{n+1}s{N-i}}$$를 만족해야 할 것이다.

$$\displaystyle\sum^{L_{n+1}}{i=1}{c^{n+1}_is{N-i}}=\displaystyle\sum^{L_{n+1}}{i=1}{c^n_is{N-i}}-\displaystyle\frac{d_n}{d_m}\displaystyle\sum^{L_{n+1}}{i=1}c^m{i-n+m}s_{N-i}=s_N-\displaystyle\frac{d_n}{d_m}\displaystyle\sum^{L_{n+1}}{i=1}c^m{i-n+m}s_{N-i}$$

$n<0,L_m< n$에서 $c^m_n=0$이므로

$$\displaystyle\sum^{L_{n+1}}{i=1}c^m{i-n+m}s_{N-i}=\displaystyle\sum^{L_{n+1}}{i=n-m}c^m{i-n+m}s_{N-i}=\displaystyle\sum^{L_m+n-m}{i=n-m}{c^m{i-n+m}s_{N-i}}=\displaystyle\sum^{L_m}{j=0}{c^m_js{N-j-n+m}}$$

그러므로 $$L_{n+1} \leq N \leq n - 1$$인 $N$에 대해

$$\displaystyle\sum^{L_m}{j=0}{c^m_js{N-j-n+m}}=\displaystyle\sum^{L_m}{j=1}{c^m_js{N-j-n+m}}-s_{N-n+m}=s_{N-n+m}-s_{N-n+m}=0$$이므로 $$s_N = \displaystyle\sum^{L_{n+1}}{i=1}{c_i^{n+1}s{N-i}}$$

$$N = n$$에 대해

$$\displaystyle\sum^{L_{n+1}}{i=1}{c^{n+1}_is{N-i}}=\displaystyle\sum^{L_{n+1}}{i=1}{c^n_is{N-i}}-\displaystyle\frac{d_n}{d_m}\displaystyle\sum^{L_{n+1}}{i=1}c^m{i-n+m}s_{N-i}=\hat s_n - (s_n - \hat s_n ) \displaystyle \frac{1}{d_m}\displaystyle\sum^{L_{n+1}}{i=1}c^m{i-n+m}s_{N-i}$$

$$\displaystyle\sum^{L_{n+1}}{i=1}c^m{i-n+m}s_{N-i}=\displaystyle\sum^{L_{n+1}}{i=n-m}c^m{i-n+m}s_{N-i}=\displaystyle\sum^{L_m+n-m}{i=n-m}{c^m{i-n+m}s_{N-i}}=\displaystyle\sum^{L_m}{j=0}{c^m_js{m-j}}=\hat s_m - s_m = -d_m$$

$$\therefore \displaystyle\sum^{L_{n+1}}{i=1}{c^{n+1}_is{N-i}}=\hat s_n + s_n - \hat s_n = s_n$$

따라서 $$L_{n+1} \leq N \leq n$$인 모든 $N$에 대해

$$s_N = \displaystyle\sum^{L_{n+1}}{i=1}{c_i^{n+1}s{N-i}}$$이 성립하므로 $$C_{n+1}$$은 적절하다.

이때 $2L_n\leq$ (수열의 항 수)를 만족해야 하는데, 그 이유는 $C_n$이 적합한지 확인하기 위해서는 $L_n$개의 검산 항이 필요하기 때문에 초기항 $L_n$개와 검산 항 $L_n$개, 총 $2L_n$개를 더해야 하기 때문이다.

$$L_{n+1}=n + 1 - L_n$$으로 나타낼 수 있는데, 이 또한 증명해 보자.

$c_i^{n+1}=c_i^n - \displaystyle\frac{d_n}{d_m}c^m_{i-n+m}$이므로

$L_{n+1}=\max{L_n, n-m+L_m}$이다.

$m$의 초기값은 $-1$, $L_m$의 초기값은 $0$으로 설정했을 때 처음 오류가 발생한 $n$에 대해 $L_{n+1}=\max{0, n+1}=n+1=n+1-L_n$

$m$에서 $L_{m+1}=m+1-L_m$이 성립할 때, $L_{n+1}=\max{L_n,n-m+L_m}=\max{L_n,n+1-L_{m+1}}=\max{L_n,n+1-L_n}$

$(n+1-L_n)-L_n=n+1-2L_n\geq1>0$ $\therefore \max{L_n, n+1-L_n}=n+1-L_n,;L_{n+1}=n+1-L_n$

수학적 귀납법에 의해 모든 $n=0,1,\cdots$에 대해 $L_{n+1}=n+1-L_n$

이를 코드화시켜 보자.

모든 $C, L, d$를 저장하면 공간 복잡도가 지나치게 커지므로 필요한 $C_m, L_n, d_m$과 $m$만 저장한다. $C_m$은 $B,$ $L_n$은 $L,$ $d_m$은 $w$라고 하자.

입력은 수열 $s$와 유한체의 크기 $\mathrm{mod}$면 충분하다.

def berl(S, mod = 998244353):
    N = len(S)
    M = -1
    C = [0] * (N + 1)
    C[0] = -1
    B = [0] * (N + 1)
    L = 0
    d = 0
    w = 1
    for i in range(N):
        d = S[i]
        for j in range(1, L + 1):
            d = (d - C[j] * S[i - j]) % mod
        if d != 0:
            tmp = C[:]
            for j in range(i - M, N + 1):
                C[j] = (C[j] - d * pow(w, -1, mod) * B[j - i + M]) % mod
            if 2 * L <= i:
                L = i + 1 - L
                M = i
                B = tmp
                w = d
    return C[1:L+1]

위의 코드를 필요에 따라 적절히 수정하여 사용하면 된다.

만일 함수 $$f$$가 구간 $$(-\infin , \infin)$$에서 르베그 적분 가능하면 $$\displaystyle\lim_{\omega\rarr \infin}\int^\infin_{-\infin}{f(t)e^{-i\omega t}}dt=0$$임이 성립한다.

이를 지배 수렴 정리를 사용하여 증명할 수 있다.

지배 수렴 정리는 집합 $$E$$에서 가측 함수열 $${f_n}$$과 적분 가능한 함수 $$g$$가 있을 때 $$a. e.,|f_k(x)|\leq g(x),,(k=1, 2, 3,\cdots)$$를 만족한다고 할 때, $${f_n}$$이 $$a.e.$$ 함수 $$f$$에 수렴하면 $$\displaystyle\int_E{f}=\int_E\lim_{n\rarr\infin}{f_n}=\lim_{n\rarr\infin}\int_E{f_n}$$가 성립한다는 정리이다.

우선 오일러 공식 $$e^{ix}=\cos x +i\sin x$$에 따라 $$\displaystyle\int^\infin_{-\infin}{f(t)e^{-i\omega t}}dx=\int_{-\infin}^\infin{f(t)\cos \omega t dt}-i\int_{-\infin}^\infin{f(t)\sin \omega t dt}$$

또한 복소수의 크기는 실수부$$^2+$$허수부$^2$이므로 복소지수함수 $$e^{ix}$$의 크기 $$|e^{ix}|$$는 $$x$$에 관계없이 $$1$$이다.

따라서 $$\left|e^{-i\omega t}f(t)\right|=\left|f(t)\right|$$가 성립한다.

함수열 $$g_n(x):=\displaystyle\int^\infin_{-\infin}{f(t)e^{-int}dt}$$라 하면 $$\left|g_n(x)\right|\leq \displaystyle\int^\infin_{-\infin}{\left|f(t)\right|dt}$$이고, 따라서 지배 수렴 정리가 성립한다.

그러므로 지배 수렴 정리에 따라 $$\displaystyle\lim_{\omega\rarr \infin}\int^\infin_{-\infin}{f(t)e^{-i\omega t}}dt=\int^\infin_{-\infin}{f(t)\lim_{\omega\rarr \infin}{e^{-i\omega t}}dt}$$이 성립한다.

여기서 $$\displaystyle\lim_{\omega\rarr\infin}{e^{-i\omega t}}$$를 구하기 위해서는 약수렴(weak convergence)의 개념을 알아야 한다. 어떤 수열 $$x_n$$과 힐베르트 공간 위의 $$y$$에 대해 $$\displaystyle\lim_{n\rarr\infin}{\left<x_n,y\right>=\left<x,y\right>}$$를 만족하면 $$x_n$$이 $$x$$로 약수렴한다고 한다.

정규직교로 구성된 수열 $$e_n$$이 있다고 하자. 정규직교로 구성된 수열은 내적 $$\left< e_n, e_m\right>=\delta_{nm}$$을 만족하는 수열이다. $$\delta_{nm}$$은 $$n=m$$일 때 $$1$$이고 $$n\ne m$$일 때 $$0$$인 함수이다. $$e^{inx}$$는 가장 대표적인 정규직교 함수열이다.

이 수열 $$e_n$$은 베셀 부등식에 따라서 힐베르트 공간 위의 $$x$$에 대해 $$\displaystyle\sum_{n=1}^{\infin}{\left|\left<e_n, x\right>\right|^2}\leq|x|^2$$을 만족한다. $$x$$와 $$y$$의 내적이 둘 사이의 유사도를 의미함을 생각하면 당연할 것이다.

수열의 급수가 수렴하면 수열의 극한이 $$0$$으로 수렴한다. 따라서 힐베르트 공간 위의 모든 $$x$$에 대하여 $$\displaystyle\lim_{n\rarr \infin}\left<e_n, x\right>=0$$이다. 즉 $$\displaystyle\lim_{n\rarr\infin}{e_n}$$은 힐베르트 공간 위의 모든 $$x$$에 대해 직교한다.

이는 $$n\rarr\infin$$에서 $$\left<e_n, e_n\right>=|e_n|=0$$이라는 말이고, 이를 만족하는 $$e_n$$은 영벡터밖에 없다. 즉 $$\displaystyle\lim_{n\rarr\infin}e_n=0$$이다. 따라서 $$\displaystyle\lim_{n\rarr\infin}e^{inx}=0$$이다.

위의 식에서 $$\displaystyle\lim_{\omega\rarr \infin}\int^\infin_{-\infin}{f(t)e^{-i\omega t}}dt=\int^\infin_{-\infin}{f(t)\lim_{\omega\rarr \infin}{e^{-i\omega t}}dt}$$인데 $$\displaystyle\lim_{\omega\rarr\infin}{e^{-i\omega t}}=0$$이므로

$$\displaystyle\lim_{\omega\rarr \infin}\int^\infin_{-\infin}{f(t)e^{-i\omega t}}dt=0$$이다.

이를 통해 푸리에 계수의 수렴성을 보장할 수 있다.

• 확률공간의 점들의 집합 $$\Omega$$는 표본공간이라고 한다.
• 확률공간의 가측집합 $$S\in \mathcal{F}$$는 사건이라고 한다.
• 사건 $$S$$의 측도 $$P(S)$$는 확률이라고 한다.

$$\displaystyle\int_E{f}=\int_E\lim_{n\rarr\infin}{f_n}=\lim_{n\rarr\infin}\int_E{f_n}$$

그러나 균등수렴은 아주 강한 조건이기에 만족하지 못하는 경우가 많다.

르베그 적분은 이보다 훨씬 약한 조건 하에서도 극한과 적분의 교환이 성립하는데, 그 조건들을 정리해 놓은 것을 르베그 적분의 수렴 정리라고 한다.

단조 수렴 정리, 지배 수렴 정리가 있다.

단조 수렴 정리는 측도 공간 $$(E, \mathcal{M}, \mu)$$ 위의 집합 $$E$$에서 음이 아닌 가측 함수열 $${f_n}$$이 단조 증가열이며 $$a.e.$$ 함수 $$f$$에 수렴할 때 $$\displaystyle\int_E{f}=\int_E\lim_{n\rarr\infin}{f_n}=\lim_{n\rarr\infin}\int_E{f_n}$$가 성립한다는 정리이다.

간단하게 증명해보자.

$$f=\displaystyle\lim_{n\rarr \infin}{f_n}$$이므로 $$\displaystyle\int_Ef=\int_E\lim_{n\rarr \infin}f_n$$이다.

임의의 $$n\in\N$$에 대해 $$f_n\leq f$$이므로 $$\displaystyle\int_E{f_n}\leq\int_E{f}$$이 성립한다. 따라서 $$\displaystyle\lim_{n\rarr \infin}\int_Ef_n\leq\int_E{f}$$가 성립한다.

$$\forall x\in E:s(x)\leq f(x)$$인 단순함수 $$s(x)$$를 생각하자. 임의의 $$n\in \N$$에 대해서 $$A_n={x\in E:s(x)\leq f_n(x)}\in \mathcal{M}$$ 라고 하면 $$A_1\sube A_2\sube\cdots$$이며, $$\displaystyle\lim_{n\rarr\infin}{A_n}=E$$이다.

또한 임의의 $$n\in\N$$에 대하여 $$\displaystyle\int_{A_n} s\leq\int_{A_n} f_n \leq \int_E f_n$$이다.

$$n\rarr \infin$$에서 $$\displaystyle\int_E{s}\leq \lim_{n\rarr\infin}\int_E{f_n}$$이고

르베그 적분의 정의에 따라 $$\displaystyle\int_E{f}\leq \lim_{n\rarr\infin}\int_E{f_n}$$이다.

$$,$$ $$\displaystyle\lim_{n\rarr \infin}\int_Ef_n\leq\displaystyle\int_E{f}\leq \lim_{n\rarr\infin}\int_E{f_n}$$이므로

$$\displaystyle\lim_{n\rarr \infin}\int_Ef_n=\int_Ef$$

$$\therefore\displaystyle\int_Ef=\int_E\lim_{n\rarr \infin}f_n=\displaystyle\lim_{n\rarr \infin}\int_Ef_n$$

$$,$$

$$,$$

지배 수렴 정리는 집합 $$E$$에서 가측 함수열 $${f_n}$$과 적분 가능한 함수 $$g$$가 있을 때 $$a. e.,|f_k(x)|\leq g(x),,(k=1, 2, 3,\cdots)$$를 만족한다고 할 때, $${f_n}$$이 $$a.e.$$ 함수 $$f$$에 수렴하면 $$\displaystyle\int_E{f}=\int_E\lim_{n\rarr\infin}{f_n}=\lim_{n\rarr\infin}\int_E{f_n}$$가 성립한다는 정리이다.

리만 적분은 유계함수 $$f$$가 $$a. e.$$ 연속일 때 가능한 반면, 르베그 적분은 그렇지 않아도 가능하다.

리만 적분 가능한 함수 $$f$$에 수렴하는 함수열 $${f_n}$$이 존재할 때, $${f_n}$$이 리만 적분 가능하려면 $${f_n}$$이 $$f$$에 균등수렴해야 한다.

집합 $$X$$ 위에서 함수열 $${f_n}$$이 함수 $$f$$에 균등수렴한다는 것은 수식으로 다음과 같이 나타낼 수 있다. $$\forall \epsilon >0,,\exist N\in\N\quad s.t., n\geq N \Rarr \displaystyle\sup_{x\in X}|f_n(x)-f(x)|<\epsilon$$ 함수열 $${f_n}$$이 리만 적분 가능한 함수 $$f$$에 균등수렴한다면 또한 극한과 적분의 교환이 성립한다. 즉,

$$\displaystyle\int_E{f}=\int_E\lim_{n\rarr\infin}{f_n}=\lim_{n\rarr\infin}\int_E{f_n}$$

그러나 균등수렴은 아주 강한 조건이기에 만족하지 못하는 경우가 많다.

르베그 적분은 이보다 훨씬 약한 조건 하에서도 극한과 적분의 교환이 성립하는데, 그 조건들을 정리해 놓은 것을 르베그 적분의 수렴 정리라고 한다.

단조 수렴 정리, 지배 수렴 정리가 있다.

중요한 내용이므로 다음 시간에 따로 다루도록 하겠다.

지시 함수 $$1_A(x)$$는 $$1_A(x)=\begin{cases} 1\quad x\in A\ 0 \quad x \notin A \end{cases}$$로 정의되는 함수이다.

집합 $$S$$ 위의 단순 함수 $$\phi$$는 치역이 유한한 함수이며, 가측 함수이다. 단순 함수는 지시 함수들의 유한합으로 나타낼 수 있을 것이다. 즉, $$\phi=\displaystyle\sum_{i}a_i1_{S_i}$$로 나타낼 수 있다.

이를 측도 $$\mu$$에 대해 르베그 적분한 결과를 $$\displaystyle\int_S{\phi(x)}d\mu=\sum_i{a_i\mu(S_i)}$$로 정의한다.

일반적인 가측 함수 $$f(x)$$의 적분은 이 단순 함수의 적분을 이용한다. 한마디로, 극한을 취하면 단순 함수로 모든 함수를 근사할 수 있을 것이란 아이디어이다.

이때 음이 아닌 가측 함수의 적분만 생각해 주면 되는데, 음의 값을 갖는 가측 함수의 경우에는 음이 아닌 가측 함수의 적분에 마이너스를 곱한 것으로 생각할 수 있기 때문이다.

음이 아닌 가측 함수 $$f$$에 대해 $$0\leq\phi_1(x)\leq\phi_2(x)\leq\cdots\leq f(x)$$를 만족하는 증가하는 함수열 $${\phi_n}$$을 생각할 수 있다.

함수열은 말 그대로 각 항이 함수인 수열을 말한다.

단순 함수열 $${\phi_n}$$은 끝내 $$f(x)$$에 수렴할 것이고, 즉 $$\sup{\phi_n}=f$$가 될 것이다. 이에 따라 집합 $$S$$ 위에서 정의된 함수 $$f$$의 측도 $$\mu$$에 대한 르베그 적분은 $$\displaystyle\int_S{f}d\mu=\sup\left{\int_S{\phi},d\mu,|,0\leq\phi\leq f,,, \phi는,,단순,,함수\right}$$로 정의된다.

가측 집합 $$S$$ 위의 유계 함수 $$f$$의 르베그 적분 가능성은 $$\displaystyle\int_S{f}d\mu<\infin$$로 판단한다.

“연속함수 $$f(x)$$에 대해 $$[a, b]$$를 점점 더 작은 구간 $$(x_i, x_{i+1})$$로 나누는 것은 $$(x_i, x_{i+1})$$에서 $$f(x)$$의 하한과 상한인 $$\underline{f}$$와 $$\overline{f}$$의 차를 점점 더 작게 만드는 것이 명백하고 그렇기에 $$S=\displaystyle\sum_{i}{f(\xi_i)\Delta x_i}$$의 극한이 존재한다. 그러나 불연속함수에 대해서도 같은 경우가 될 이유가 없다. 이를 해결하려면 $$[a, b]$$를 나누는 것이 아니라 $$[a, b]$$에서 하한과 상한이 경계가 되는 구간 $$[\underline{f}, \overline{f}]$$를 분할해야 하는 것이 분명하다.”

르베그 적분의 아이디어는 이와 같다. 기존에 $$x$$축을 분할했던 리만 적분과 달리 $$y$$축을 분할하는 것이다. 이 개념을 식으로 나타내면 다음과 같다. $$\displaystyle\lim_{n\rarr\infin}{\sum_{k=1}^n}\left{\inf (Y_k) \times \mu(X_k)\right}$$ $$Y_k$$는 $$n$$개로 분할된 $$y$$축의 각 소구간을 의미하고, $$X_k={x,|,f(x)\in Y_k}$$이다.

개념적으로 이해하면 이와 같고, 다음 시간에는 단순 함수의 상한으로 르베그 적분을 정의하는 방법을 알아볼 것이다.

집합 $$\Omega$$의 부분집합들을 원소로 하는 집합 $$B$$가 아래 조건을 만족할 때 $$B$$를 $$\sigma$$-대수라고 정의한다.

• $$\varnothing \in B$$
• $$E\in B \Rarr E^c\in B$$
• $$E_1, E_2, \cdots\in B \Rarr \displaystyle\bigcup_{i=1}^{\infin}{E_i}\in B$$

집합 $$\Omega$$, $$\Omega$$의 부분집합을 원소로 하는 $$\sigma$$-대수 $$B$$, 집합함수 $$\mu:S\in B\rarr [0, \infin )$$가 존재할 때 다음 조건을 만족하는 $$\mu$$를 측도라 하고, $$(\Omega, B, \mu)$$를 측도 공간이라 한다.

• $$\mu(\varnothing)=0$$
• 만일 $$E_i,(,i=1, 2, \cdots)$$가 서로소인 가측 집합이라면, $$\mu\left(\displaystyle\bigcup_{i=1}^{\infin}{E_i}\right)=\displaystyle\sum_{i=1}^{\infin}{\mu\left( E_i\right)}$$가 성립한다.

측도공간 $$(X, \mathcal{M}, \mu)$$와 $$A, B\in\mathcal{M}$$에 대하여 다음이 성립한다.

• $$A \sube B \Rarr \mu(A) \leq \mu(B)$$
• $$A\sube B, ,\mu(A)<\infin$$면 $$\mu(B-A)=\mu(B)-\mu(A)$$

르베그 측도 역시 르베그 외측도 $$\lambda^:\mathcal{P}(\R)\rarr \left[0,\infin \right)$$가 존재하며, 그 식은 다음과 같다. $$\displaystyle\lambda^(S)=\inf \left{ \sum_{i=1}^{\infin} |b_i-a_i|:a_i, b_i\in\R, S\subseteq \bigcup_{i=1}^{\infin}[a_i, b_i]\right}$$

집합 $$S$$를 포함하는 닫힌구간들의 길이의 합의 하한이다.

르베그 가측 집합은 다음 조건을 만족시키는 집합 $$S\sube \R$$을 말한다.

• $$\forall ,T\sube \R \quad\lambda^(T)=\lambda^(T\cap S) +\lambda^*(T-S)$$

르베그 가측 집합에서의 르베그 외측도 $$\lambda^$$를 *르베그 측도** $$\lambda$$로 정의한다.

르베그 가측 집합을 정의역으로 갖는 함수는 (르베그) 가측 함수라고 부른다.

한 점 집합 $${a}$$의 르베그 측도 $$L$$을 구해보자. 임의의 양수 $$\epsilon$$에 대해 $${a}\sub[a-\epsilon, a+\epsilon]$$이 성립한다.

$$[a-\epsilon, a+\epsilon]$$의 르베그 측도는 $$2\epsilon$$이고, 따라서 $$0\leq L< 2\epsilon$$이다. 엡실론 논법에 의하여 $$L=0$$이 된다. 즉 어떤 한 점 집합의 르베그 측도는 $$0$$이다.

이를 이용해 열린구간의 르베그 측도도 알 수 있다.

$$[a, b]={a}+(a,b)+{b}$$로 나타낼 수 있고, 따라서 르베그 측도를 $$\mu$$라 할 때 $$\mu([a, b])=\mu({a})+\mu((a,b))+\mu({b})$$이며, 위의 정리에 따라 $$b-a=\mu((a, b))$$이다.

이를 활용해 마침내 르베그 적분을 정의할 수 있다.

각 소구간에서 대푯값 $$\xi_i$$를 하나씩 뽑아서 수열 $$\xi={\xi_1,\xi_2, \cdots,\xi_n}$$을 만들 수가 있으며, 이를 표집수열이라고 한다.

구간 $$[a, b]$$에서 정의된 함수 $$f$$에 대해 $$S(f, P, \xi)=\displaystyle\sum_{i=1}^{n}f(\xi_i)\Delta x_i$$로 정의하며, 이를 분할 $$P$$와 표집수열 $$\xi$$에 의한 함수 $$f$$의 리만합이라고 읽는다.

$$\sup {\Delta x_i ,| ,i=1, 2, \cdots, n}$$을 $$|P|$$로 쓰고 $$P$$의 노름이라고 읽는다.

$$,$$ $$|P|\rarr 0$$에서 $$\xi_i\rarr \displaystyle\frac{x_i+x_{i-1}}{2}$$이라면 함수 $$f$$가 구간 $$[a, b]$$에서 리만 적분 가능하다고 말하며 $$\displaystyle\sum_{i=1}^{\infin}{f(\xi_i)\Delta x_i}$$는 실수 $$J$$에 수렴한다. 이때 $$J$$를 $$[a, b]$$에서의 리만 적분이라고 부른다.

이를 $$\displaystyle\int_a^bf(x)dx=J$$로 나타낸다.

리만 적분의 장점은 사각형의 합으로 나타내는 것으로 직관적으로 이해할 수 있다는 것이다. 그러나 단점도 있다. 유계함수 $$f$$가 리만 적분 가능할 필요충분조건은 거의 어디서나(almost everywhere, $$a. e.$$) 연속인 것인데, 그렇지 않은 함수들도 있기 때문이다. 가령 디리클레 함수 $$1_{\mathbb{Q}}(x)=\begin{cases}1 \quad x\in \mathbb{Q}\ 0 \quad x \notin \mathbb{Q} \end{cases}$$는 모든 점에서 불연속이다.

조건 $$p$$가 집합 $$S$$의 거의 어디서나(almost everywhere, $$a.e.$$) 성립한다는 것은 특정 가산 부분 집합을 제외한 모든 집합의 모든 원소에 대해서 $$p$$가 성립한다는 것을 말한다.

이를 해결하기 위해 르베그 측도를 기반으로 한 르베그 적분이 나오게 된다.

특정 영역의 넓이를 측정하고 싶다고 할 때, 영역을 포함하는 단위 사각형들의 넓이의 합의 하한이 조르당 외측도이고, 영역에 포함되는 단위 사각형들의 넓이의 합의 상한이 조르당 내측도이다.

하한은 $$\inf$$으로 나타내며, 인파이멈(infimum)이라고 읽는다. 하한을 알기 위해선 하계에 대해 알아야 하는데, 집합 $$S$$의 하계는 $${M,|,M\leq s\quad \forall s \in S}$$로 정의되며, 하계의 최댓값이 하한이다.

상한은 $$\sup$$으로 나타내며, 슈프리멈(supremum)이라고 읽는다. 상한은 마찬가지로 상계의 최솟값으로 정의된다. 집합 $$S$$의 상계는 $${m,|,m\geq s\quad \forall s \in S}$$로 정의될 것이다.

$$\quad$$ 상한과 하한이 최댓값, 최솟값 대신 쓰이는 이유는 $$(0, 1)$$같은 경우에 최댓값이나 최솟값은 없지만 상한과 하한은 각각 $$0$$과 $$1$$로 존재하기 때문이다.

조르당 외측도와 내측도는 이렇게 개념적으로 이해하면 된다. 수식은 쓰기 귀찮으니 위키백과 문서를 참고하는 게 좋다.

https://ko.wikipedia.org/wiki/%EC%A1%B0%EB%A5%B4%EB%8B%B9_%EC%B8%A1%EB%8F%84

유클리드 공간 $$\R^n$$ 위의 유계 집합 $$E\subseteq \R^n$$에서 조르당 외측도$$(\mu_J^)$$와 조르당 내측도$$(\mu _{J})$$가 서로 같을 때, 집합 $$E$$를 조르당 가측 집합이라고 한다. 즉 조르당 가측 집합 $$E$$에서 조르당 측도 $$\mu_J(E)=\mu_J^(E)=\mu_{J}(E)$$이다.

유클리드 공간 $$\R^n$$은 실수 집합 $$\R$$의 곱집합이다. 즉 우리가 아는 $$n$$개의 축이 있는 $$n$$차원 개념이 유클리드 공간이다.

유계란 유한한 영역을 가지는 것을 의미한다. 상계를 가지고 있으면 위로 유계, 하계를 가지고 있으면 아래로 유계라고 표현하며, 둘 모두 가지고 있는 집합을 유계 집합이라고 부른다.

조르당 측도는 유한 가법성이 성립한다. 어떤 함수 $$f(x)$$가 $$f(a+b)=f(a)+f(b)$$를 만족할 때 $$f(x)$$에서 가법성이 성립한다고 한다. 조르당 측도에서 유한 가법성이 성립한다는 것은 유한 개의 집합 $$S_1, S_2, \cdots, S_n$$ 에 대해서 $$\mu_J(\displaystyle\bigcup_{i=1}^{n}{S_i})=\sum_{i=1}^{n}{\mu_J(S_i)}$$가 성립한다는 것이다.

조르당 측도는 가산무한집합에 대해서는 가법성이 성립하지 않기 때문에, 가산 가법성이 성립하는 새로운 측도인 르베그 측도가 발명되게 된다.

!!주의!! 푸리에 변환을 거의 이해하지 못한 사람의 발버둥입니다. 전혀 정확하지 않습니다. 오류가 매우 많습니다. 남들한테 보여주려고 업로드한 글이 아닙니다.

1. 조지프 푸리에 : 내가 열역학 좀 해보는데 여기서 주기적 신호를 삼각함수들의 합으로 분리해서 나타내면 편리할 것 같은데?

   이것이 성립하는 이유는 $$\sin nx$$와 $$\cos nx$$가 각각 직교 기저이기 때문이다. 이것이 무슨 말인고 하니 $$\displaystyle\int ^b _a \sin mx \times \cos nxdx=0, \displaystyle\int ^b _a \cos mx \times \cos nxdx=0, \displaystyle\int ^b _a \sin mx \times \sin nxdx=0$$이 성립한다는 것이다. (단 2, 3번 식은 $$m\not= n$$일 때 성립한다.)

   삼각함수의 합 공식에 따라 삼각함수의 곱을 합으로 나타냄으로써 증명할 수 있다. 주기가 다른 삼각함수들의 합의 최소 주기는 주기들의 최소공배수이다.

   따라서 어떤 주기함수 $$f(x)$$를 $$\sin , \cos$$들의 합으로 나타낼 수 있다.

2. 푸리에 급수식 이쯤와서 푸리에 급수식을 보자면 다음과 같다. $f(x)=\displaystyle \sum_{k=0}^{\infin}({a_k\sin kx +b_k \cos kx})$ $$\sin kx$$는 주기가 $$2\pi$$의 $$\displaystyle\frac{1}{k}$$배인 정현파이다. 그렇다면 $$a_n, b_n$$의 정체만 안다면 푸리에 급수식을 파악할 수 있을 것이다.

   $$a_n, b_n$$은 각 $$\sin$$파와 $$\cos$$파가 $$f(x)$$에 얼마나 들어가 있는지를 판단하는 기호이다. 따라서 $$a_k:=\displaystyle\frac{<f(x),\sin kx>}{||\sin ^2kx||}=\frac{2}{T}\int ^T _0{f(x) \sin kx dx}$$, $$b_k:=\displaystyle\frac{<f(x),\cos kx>}{||\cos ^2kx||}=\frac{2}{T}\int ^T _0{f(x) \cos kx dx}$$ $$||\sin^2kx||, ||\cos^2kx||$$는 내적 구간에서 여러 주기에 걸쳐 반복되는 $$\sin, \cos$$으로 인한 노이즈를 없애는 정규화를 위한 상수이다. 계산할 시 $$k$$에 관계없이 $$\displaystyle\frac{2}{T}$$가 나온다.

3. 복소지수함수를 이용한 표현 $$e^{ix}=\cos x +i\sin x$$임을 모두가 알 것이다. 따라서 $$e^{-ix}=\cos x - i\sin x$$ 두 식을 정리하면 $$\cos x=\displaystyle\frac{e^{ix}+e^{-ix}}{2}, \sin x=\displaystyle\frac{e^{ix}-e^{-ix}}{2i}$$ 푸리에 급수식에 대입하면 $f(x)=\displaystyle\sum_{k=0}^{\infin}{a_k\displaystyle\frac{e^{ikx}-e^{-ikx}}{2i}+b_k\displaystyle\frac{e^{ikx}+e^{-ikx}}{2}}$ $$\displaystyle=\sum^\infin_{k=0}{\frac{e^{ikx}(a_k-ib_k)+e^{-ikx}(a_k+ib_k)}{2}}$$ $$a_n=\displaystyle\frac{2}{T}\int ^T 0{f(x) \sin kx dx}=\frac{1}{i}\cdot\frac{1}{T}\int^T_0{f(x)(e^{ikx}-ie^{-ikx})dx}$$ $$ia_n=\displaystyle\frac{1}{T}\int^T_0{f(x)(e^{ikx}-e^{-ikx})dx}$$ 똑같은 방법으로 $$b_n=\displaystyle\frac{1}{T}\int^T_0{f(x)(e^{ikx}+e^{-ikx})dx}$$ 즉 $$ia_n=-ia{-n}, b_n=b_{-n}$$ $$f(x)\displaystyle=\sum^\infin_{k=0}{\frac{e^{ikx}(-ia_k+b_k)+e^{-ikx}(ia_k+b_k)}{2}}$$ $$=\displaystyle\sum^\infin_{k=-\infin}{\frac{b_k-ia_k}{2}e^{ikx}}$$

   보기 편하게 $$C_k=\displaystyle\frac{b_k-ia_k}{2}=\frac{1}{T}\int^T_0f(t)(\cos kt - i\sin kt)dt=\frac{1}{T}\int^T_0f(t)e^{-ikt}dt$$로 바꾸면 $$f(x)=\displaystyle\sum^\infin_{n=-\infin}C_ne^{inx}$$ 우리가 원하는 주파수대는 정수 주파수대이므로 $$\omega =\displaystyle\frac{2\pi}{T}$$를 지수에 곱해 정수 주파수로 변경해주면

$$f(x)=\displaystyle\sum^\infin_{n=-\infin}C_ne^{in\omega x}$$ $$(\displaystyle C_n=\frac{1}{T}\int^T_0f(t)e^{-in\omega t}dt)$$

이것으로 모든 주기함수들을 가장 깔끔한 형태로 표현할 수 있는 식이 완성됐다.

4. 푸리에 변환의 유도 여기서 주기를 $$\infin$$로 보내 비주기 신호 역시 주파수 대역으로 분해하는 것이 푸리에 변환이다. $$\displaystyle\lim_{T\rarr \infin}{C_n}=\lim_{T\rarr \infin}\frac{1}{T}\int^\infin_{-\infin}f(t)e^{-i2\pi ft}dt$$ $$h(x)=\displaystyle\sum^\infin_{n=-\infin}C_ne^{in\omega x}=\displaystyle\sum^\infin_{n=-\infin}(\lim_{T\rarr \infin}\frac{1}{T}\int^\infin_{-\infin}h(t)e^{-in\omega t}dt)e^{in\omega x}$$ $$H(f):=\displaystyle\int^\infin_{-\infin}h(t)e^{-i2\pi ft}dt$$로 하면

   $$h(t)=\displaystyle\lim_{T\rarr \infin}\sum^\infin_{n=-\infin}{\frac{1}{T}H(f)e^{i2\pi ft}}$$ $$=\displaystyle\lim_{f\rarr 0}\sum^\infin_{n=-\infin}{fH(f)e^{i2\pi ft}}$$ $$\displaystyle =\int^\infin_{-\infin}H(f)e^{i2\pi ft}df$$

이산 시스템에서는 $a_n*b_n=\displaystyle\sum_{i=0}^{n}{a_ib_{n-i}}$로 표현된다.

간단히 말해서 양쪽 끝에서부터 두 함수를 교차해서 곱한 것들을 더한다는 것이다.

어, 그런데 이런 꼴을 어디서 본 적이 있었으니...

$H(f)=\displaystyle\int_{-\infin}^{+\infin}{h(t)e^{-iwt}dt}$ 푸리에 변환식에서 저런 꼴을 본 적이 있을 것이다.

놀랍게도 푸리에 변환한 후의 곱셈 뒤 역변환은 합성곱과 똑같으니... 이를 증명해보자.

푸리에 변환식 안에 합성곱을 넣어서...

$\displaystyle\int_{-\infin}^{+\infin}{}{\displaystyle\int_{-\infin}^{+\infin}{f(\lambda)g(t-\lambda)d\lambda } e^{-iwt}dt}=\displaystyle\int_{-\infin}^{+\infin}{f(\lambda) {\displaystyle\int_{-\infin}^{+\infin}{g(t-\lambda)e^{-iwt}dt}}d\lambda}$

밖으로 빼내준 뒤 치환하고...

$=\displaystyle\int_{-\infin}^{+\infin}{f(\lambda) {\displaystyle\int_{-\infin}^{+\infin}{g(m)e^{-iw(m+\lambda)}dm}}d\lambda}=\displaystyle\int_{-\infin}^{+\infin}{f(\lambda)e^{-iw\lambda}d\lambda \displaystyle\int_{-\infin}^{+\infin}{g(m)e^{-iwm}dm}}$

$=F(w)\times G(w)$

지수를 분리시켜주면 푸리에 변환식의 곱 꼴이 된다.

이산 푸리에 변환 역시 마찬가지로 할 수 있다.

합성곱으로 할 수 있는 건 매우 많다ㅡ우선 곱셈을 합성곱을 이용하여 빠르게 할 수 있다. 곱하는 수들을 값 표기법으로 나타낸 수열로 보는 것이다. $213\times 123$을 $[3, 1, 2]$와 $[3, 2, 1]$로 나타낼 수 있을 것이다. 이 때 $x=10$이다. 이 수열 둘을 합성곱한 뒤 $x=10$을 대입해준다면 간단히 두 수의 곱을 $O(N\log N)$만에 할 수 있을 것이다.

합의 경우의 수 역시 합성곱으로 구할 수 있다. $[1, 2, 3], [0, 4, 8]$에 대해 양쪽에서 하나씩 골라 더하여 만들 수 있는 수는 $1,5, 9, 2, 6, 10, 3, 7, 11$이 있을 것이다. $[1, 2, 3]$을 $[0, 1, 1, 1, 0, ...]$처럼, $[0, 4, 8]$을 $[1, 0, 0, 0, 1, 0, 0, 0, 1,...]$처럼 나타내보자. 둘을 합성곱하면 $[0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, ...]$이 됨을 알 수 있다. 이 때 이 값이 $1$인 경우의 인덱스가 $1, 5, 9, 2, 6, 10, 3, 7, 11$임을 알 수 있다!

FFT에서 1의 거듭제곱근 $w$를 사용하는데, $n$번 제곱할 때마다 한 번씩 $1$로 돌아오는 주기성을 가지고 있기 때문이다. 이와 비슷한 성질을 가지는 개념이 원시근이다.

따라서 소수 $p=a\times 2^b+1$의 원시근 $w$에 대해 $w^{\frac{p-1}{n}}≡1(\mod p)$임을 이용하여 FFT를 돌릴 수 있다. (단, $n≤2^b$여야 한다.)

대표적인 $p$로 $998,244,353$이 있다. 원시근은 $3$이다.

!!주의!! 푸리에 변환을 거의 이해하지 못한 사람의 발버둥입니다. 전혀 정확하지 않습니다. 오류가 매우 많습니다. 남들한테 보여주려고 업로드한 글이 아닙니다.

1. 푸리에 급수 $f(x)=\displaystyle\sum_{k=0}^{\infin}{\frac{<f(x), \cos kx>}{||\cos kx||^2}\cos kx+\frac{<f(x), \sin kx>}{||\sin kx||^2}\sin kx}$ $<⋅, ⋅>$는 함수의 내적으로, $\int_{a}^{b}{f(x)\times g(x)dx}$로 나타낸다. 내적은 곧 유사도를 말하기도 한다. 위끝과 아래끝은 나타내지 않는데, 아마도 푸리에 급수에서는 한 주기, 푸리에 변환에서는 $+\infin$부터 $-\infin$인 것 같다. ∥⋅∥는 노름(norm)이다. $||v||:=|v\cdot v|$로 정의된다.

진동수 $\frac{k}{2\pi}$인 사인파와 코사인파의 성분의 합으로 $f(x)$를 나타낸다. 즉 기저가 되는 사인파와 코사인파의 진동수를 $k$와 함께 증가시켜가며 내적을 해서 각 진동수에 대한 성분을 원래 파형에서 추출한 뒤, 이들의 합으로 원함수를 풀어서 나타낸 것이 푸리에 급수이다.

달리 표현하면 $f(x)=\displaystyle\sum_{k=-\infin}^{\infin}{c_ke^{ikx}}$이다. 여기서 $c_k$는 진동수 $k$ 성분이 얼마나 들어있는지, 즉 진폭이 얼마인지를 나타낸다. $e^{ikx}$는 직교 기저이기 때문에 $e^{ikx}$들 간 $\cos \theta$ 값이 0이므로 내적이 0이고, 따라서 진동수들 간 간섭이 없다.

이를 달리 표현했을 때 $f(x)=\frac{1}{2\pi}\displaystyle\sum_{k=-\infin}^{\infin}{<f(x), \psi _k> \psi _k}$이다. $2\pi$는 정규화를 위한 숫자이다. 정규화란 벡터를 단위벡터로 바꾸는 것이다. 수식으로 나타내면 $\frac{\overrightarrow v}{|v|}$이다. $\psi _k$는 $e^{ikx}$를 나타낸 것이다. $<f(x), \psi _k>$는 $c_k$에 대응한다.

2. 푸리에 변환 이렇게 푸리에 급수를 이용하여 어떤 성분이 포함되어 있는지를 알 수 있다. 그러나 각 성분의 진동수에 따라서 원함수의 한 주기에서도 나타나는 횟수가 다르므로 정확한 진폭의 측정에 영향을 줄 수가 있다. 그렇기에 주기 $T$를 $\infin$로 보내서 모든 성분이 한 번만 나타나게 한다. 이렇게 하면 진동수가 진폭 측정에 영향을 미치지 않으므로 각 진동수에 대한 크기를 정확하게 알아낼 수 있다.

지금까지의 정보를 바탕으로 푸리에 변환식을 살펴보자. $F(x)=\int_{-\infin}^{+\infin}{f(t)e^{-i2\pi xt}}dx$ 인테그랄을 계산하는 것은 내적이다. 푸리에 급수에서 한 주기씩 계산하는 인테그랄의 범위를 무한대로 보내는 것이 주기를 무한대로 보낸 것을 의미한다. $e^{-2\pi xt}$는 오일러 공식에 따라 사인함수와 코사인함수를 묶어서 표현한 것이다. 사인/코사인의 주기가 $\frac{1}{x}$이므로 진동수가 $x$인 경우를 의미한다. 즉 진동수가 $x$일 때 진동수가 똑같이 $x$인 $\sin, \cos$에 대하여 내적을 해 유사도를 구함으로써 $f(x)$에 진동수 $x$인 성분이 얼마나 포함되어 있는지를 구하는 것이다.

3. 이산 푸리에 변환 하지만 푸리에 변환은 적분이 사용되기 때문에 연속적인 데이터에만 적용할 수 있다. 컴퓨터가 다루는 데이터는 모두 이산적이므로 이산 푸리에 변환을 사용해야 한다. 이산 푸리에 변환도 그냥 푸리에 변환과 본질은 똑같다. 다만 인테그랄이 시그마로 바뀌었을 뿐이다.

$F_k=\displaystyle\sum_{j=0}^{N-1}{f_je^{\frac{i2\pi jk}{N}}}$

데이터의 점들 간의 내적을 대체제로 사용하는 것이다.

. .. ...

그런데, DFT가 시간 대역을 주파수로 바꿔주기만 하는 것이라면 무슨 의미가 있을까?

행렬곱은 곱해줄 행과 열 간의 내적과 같다. DFT와 근본이 같은 것이다. 그렇기에 DFT를 행렬곱으로 나타낼 수 있는데, 이를 '푸리에 행렬'이라고 부르기도 한다.

DFT의 식을 $w=e^{-i\frac{2\pi}{N}}$를 이용해 간단히 풀어보면 $X[i]=x[0]w^0+x[1]w^i+x[2]w^{2i}+...+x[N-1]w^{i(n-1)}$이다. 이를 행렬로 나타낸다면

$\begin{bmatrix}X_i\ \end{bmatrix}=\begin{bmatrix}1&w^i&w^{2i}&...&w^{i(n-1)}\ \end{bmatrix}\begin{bmatrix}x_0 \ x_1\ x_2 \ ...\x_{N-1} \end{bmatrix}$ 이다.

이 행렬은 $N\times N$의 크기일 것이므로, 행렬곱을 위해 곱셈을 $N^2$번 해야 한다. DFT로 시간 대역 데이터를 주파수 대역으로 변환하는 것은 $O(N^2)$의 시간복잡도를 가짐을 알 수 있다.

4. 고속 푸리에 변환 $O(N^2)$... 불만족스러운 시간복잡도이다. 이를 빠르게 하기 위해서 FFT가 개발되었다. 가장 많이 알려진 쿨리-튜키 알고리즘을 바탕으로 서술하겠다.

다항식을 표현하기 위한 대표적인 방법으로는 계수 표기법(Coefficient Representation)과 값 표기법(Value Representation)이 있다.

계수 표기법은 아주 간단하다. n차다항식의 계수 $n+1$개를 수열로 나타내주는 것이다. $3x^2+2x+1$은 $[1,2,3]$ 따위로 나타내면 된다.

값 표기법은 이보다는 조금 복잡하지만, 어렵지 않다. n차다항식에는 상수항을 포함해서 $n+1$개의 항이 있을 것이다. 따라서 $n+1$개의 지나는 점의 좌표를 알아낸다면 함수를 특정할 수 있다. 이를 라그랑주 보간법이라고 한다. 이 라그랑주 보간법에서 착안하여 n차다항식을 $n+1$개의 순서쌍들로 표현하는 방식이 값 표기법이다. $(x-1)^2$의 경우 $[(1, 0),(0,1),(2,1)]$로 나타낼 수 있을 것이다.

만약 우리가 $C(x)=A(x)\times B(x)$를 계산하고 싶다고 하자. 계수 표기법으로 할 경우 당연히 $O(N^2)$의 시간복잡도가 될 것이다. 만약 값 표기법으로 한다면 어떨까?

마찬가지로 $x_0,x_1,x_2,x_3,...,x_{n}$에 대해 $n+1$번의 곱셈을 해줘야 하므로 $O(N^2)$이다. 하지만 이를 $O(N\log N)$으로 줄일 수 있는 방법이 있다.

알다시피, 홀수차함수는 기함수이고 짝수차함수는 우함수이다. 기함수와 우함수는 그 특성상 $x_i$의 값을 구하면 $-x_i$의 값도 구할 수 있다. 그리고 계수 표기법으로 된 다항식은 홀수차함수와 짝수차함수로 나누기 아주 쉽다.

이렇게 나눠진 다항식은 $P(x)=P_e(x^2)+xP_o(x^2)$처럼 나타내면 될 것이다.

그런데, 각각의 $P_e$와 $P_o$에 대해서도 짝수차와 홀수차로 분할할 수 있을 것이다.(분할 정복)

이걸 계속 반복한다... 그러면 최종적으로 $\log N$번 분할하게 될 것이다. 분할해서 나온 결과들은 계속해서 $±$의 관계이므로 곱해서 취합하고, 다시 취합하고, 다시 취합하면 된다.

그런데, 분할한 부분을 곱해가며 취합하는 과정에서 계속해서 $±$ 쌍을 만들기 위해 음의 제곱근이 유도되는 부분이 있다. 이를 어떻게 해야할까? 앞서 나온 $w=e^{-i\frac{2\pi}{N}}$를 다시 살펴보자.

오일러 공식에 따라 $e^{-2\pi i}=1$이다. 즉 $w^n=1$이다. 이런 숫자를 1의 거듭제곱근(Root of unity)이라고 부르며, $n$제곱을 하면 1로 돌아오는 주기성을 가지고 있다.

이런 성질 덕분에 행렬에 $w$를 넣는다면 중간에 어떤 연산을 거치든 최종적으로 return할 때 1로 돌아오게 된다.

FFT의 역변환인 IFFT같은 경우에는 $e^{i\theta}$에 의한 회전 방향이 반대이므로 $w$ 대신 $w^{-1}$을 사용하고, 데이터 길이가 $N$임을 감안해 $N$으로 나눠줘서 할 수 있다.

자, 이제 충분히 만족스러운 $O(NlogN)$ 안에 FFT와 IFFT 모두를 할 수 있게 되었다. 그렇다면 공간복잡도는 어떨까? 통상적인 방법을 사용한다면 다항식을 분할할 때마다 배열을 재지정해야 하므로 메모리 사용량이 상당히 클 것이다.

만약 처음부터 배열이 $[0, 4, 2, 6, 1, 5, 3, 7]$처럼 정렬되어 있다면 굳이 배열을 재지정하지 않고 재사용할 수 있을 것이다. 이 때 정렬되는 인덱스는 이진수의 역순 배열이다. $(100\rightarrow 001)$

이 방법으로 공간복잡도 역시 만족스럽게 줄일 수 있다.

...물론 복소수 연산을 해야 한다는 크나큰 문제가 남아있다.

가장 간단하고 직관적이고 비효율적인 재귀 코드

import cmath

def fft(x, inv=False):
    N = len(x)
    if N <= 1:
        return x
    even = fft([x[i] for i in range(0, N, 2)])
    odd = fft([x[i] for i in range(1, N, 2)])
    T = [cmath.exp(complex(0, (2 if inv else -2) * cmath.pi * k / N)) * odd[k] for k in range(N // 2)] # odd에 x값, 즉 w^k를 곱해준다.
    rst = [even[k] + T[k] for k in range(N // 2)] + [even[k] - T[k] for k in range(N // 2)]
    if inv:
        rst = [round((i/N).real) for i in rst] # IFFT의 경우 N으로 나눈다.
    return rst

모든 자연수 $N$에 대하여 $N^2>N^2-N$이므로 $\frac{1}{N^2}<\frac{1}{N^2-N}$이다.

$\displaystyle\sum_{n=2}^{\infin}{\frac{1}{n^2-n}}=\displaystyle\sum_{n=2}^{\infin}{\frac{1}{n(n-1)}}=\displaystyle\sum_{n=2}^{\infin}{(\frac{1}{n-1}-\frac{1}{n})}=1$이므로 $0<\displaystyle\sum_{n=2}^{\infin}{\frac{1}{n^2}}\leq1,$ 즉 $1<\displaystyle\sum_{n=1}^{\infin}{\frac{1}{n^2}}\leq2$이다.

$\displaystyle\sum_{n=2}^{N}{\frac{1}{n^2}}$은 $N$이 증가함에 따라 같이 증가하는 단조 증가 수열이고, 그 범위가 정해졌으므로 $\displaystyle\sum_{n=2}^{\infin}{\frac{1}{n^2}}$은 수렴한다.

테일러 급수 $f(x)=\displaystyle\sum_{n=0}^{\infin}{\frac{f^{(n)}(a)}{n!}{(x-a)^n}}$에 따라서

$\sin(x)=x-\frac{x^3}{3!}+\frac{x^5}{5!}+...$이다.

$p=n\pi$ ($n$은 자연수) 라고 하고 $\sin(x)$에 $p$를 대입해보면 $0=p-\frac{p^3}{3!}+...$

양변을 $p$로 나누면 $0=1-\frac{p^2}{3!}+...$ $t=p^2$이라고 한다면 $0=1-\frac{t}{3!}+...$

위 $t$에 대한 방정식의 해를 $t_1, t_2, t_3, ...$으로 뒀을 때

$\displaystyle\sum_{n=1}^{\infin}{\frac{1}{t_n}}=\frac{t_2t_3t_4...+t_1t_3t_4+...}{t_1t_2t_3t_4...}$인데, 비에트의 정리(근과 계수와의 관계)에 따라서 $n$차방정식의 해 중 $k$개를 선택해서 곱한 것의 총합은 $(-1)^k\frac{a_{n-k}}{a_n}$ $(a_n$은 $n$차항의 계수$)$이므로 $k$에 $n-1$과 $n$을 각각 대입해서 나누면 $\frac{a_1}{a_0}=\frac{1}{3!}=\frac{1}{6}$이 나오고, 이는 주어진 급수의 합이다.

한편, $\displaystyle\sum_{n=1}^{\infin}{\frac{1}{t_n}}=\displaystyle\sum_{n=1}^{\infin}{\frac{1}{n^2\pi^2}}=\frac{1}{6}$이므로 $\displaystyle\sum_{n=1}^{\infin}{\frac{1}{n^2}}=\frac{\pi^2}{6}$