장 14 보너스: 푸리에 해석

지금까지 공들여 추상적인 내적 공간을 정의했으니, 이제 (선택적인) 응용 하나를 소개하고자 합니다. 바로 이 언어를 사용하여 푸리에 해석을 올바르게 세우는 방법입니다.

재미 삼아 이진 푸리에 해석을 사용하여 애로의 불가능성 정리의 한 형태도 증명합니다.

이하에서 $\mathbb{T}=\mathbb{R}/\mathbb{Z}$ 는 “원군”을 나타내며, 이를 “ $1$ 을 법으로 하는 실수”의 덧셈군으로 생각합니다. $\mathbb{T}$ 를 복소 단위원으로 보내는 표준적인 사상 $e\colon\mathbb{T}\to\mathbb{C}$ 가 있으며, 이는 다음과 같이 주어집니다.

e(\theta)=\exp(2\pi i\theta).

14.1 개요

정의역 $Z$ 가 있고 함수 $f\colon Z\to\mathbb{C}$ 에 관심이 있다고 합시다. 자연스럽게 이러한 함수들의 집합은 복소 벡터 공간을 이룹니다. 우리는 이러한 함수들의 집합에 양의 정부호 내적을 부여하고자 합니다.

푸리에 해석의 아이디어는 그다음 이 함수들의 집합에 대해 정규직교 기저를 하나 택하는 것입니다. 이를 $(e_{\xi})_{\xi}$ 라 하고 지표라고 부르며, 첨자 $\xi$ 는 진동수라고 부릅니다. 이 경우 기저가 있으므로 모든 함수 $f\colon Z\to\mathbb{C}$ 는 다음과 같은 합이 됩니다.

f(x)=\sum_{\xi}\widehat{f}(\xi)e_{\xi}

여기서 $\widehat{f}(\xi)$ 는 기저의 복소 계수이며, 이에 걸맞게 $\widehat{f}$ 를 푸리에 계수라고 부릅니다. 변수 $x\in Z$ 는 물리 변수라고 합니다. 이 방식이 대체로 좋은 이유는 지표가 사인파나 코사인파 또는 다른 주기 함수처럼 좋은 “대칭적” 함수가 되도록 의도적으로 선택되기 때문입니다. 따라서 우리는 아무리 복잡한 함수라도 좋은 함수들의 합으로 분해합니다.

14.2 힐베르트 공간에 대한 복습

편의를 위해 정규직교 기저에 관한 몇 가지 사실을 기록해 둡니다.

명제 14.2.1 (정규직교 기저에 관한 사실).

$V$ 를 내적 형식 $\left<-,-\right>$ 을 갖는 복소 힐베르트 공간이라 하고, $e_{\xi}$ 가 정규직교 기저일 때 $x=\sum_{\xi}a_{\xi}e_{\xi}$ 이고 $y=\sum_{\xi}b_{\xi}e_{\xi}$ 라고 합시다. 그러면

	$\displaystyle\left<x,x\right>$	$\displaystyle=\sum_{\xi}\|a_{\xi}\|^{2}$
	$\displaystyle a_{\xi}$	$\displaystyle=\left<x,e_{\xi}\right>$
	$\displaystyle\left<x,y\right>$	$\displaystyle=\sum_{\xi}a_{\xi}\overline{b_{\xi}}.$

연습문제 14.2.2.

이들을 모두 증명하십시오. (앞 절의 내용은 전혀 필요하지 않으며, 앞 절은 무시무시한 $\xi$ 들이 잔뜩 등장하는 표기법의 동기를 부여하기 위해 있을 뿐입니다.)

이하에서 대부분의 예는 유한 차원 내적 공간(따라서 힐베르트 공간)이지만, “제곱 적분 가능 함수”의 예는 실제로 무한 차원의 예가 됩니다. 다행히도 앞서 암시했듯이 이는 걱정할 일이 아니며, 대체로 눈을 감고 무한에 대해 신경 쓰지 않아도 됩니다.

14.3 흔한 예

14.3.1 $\{\pm 1\}^{n}$ 위의 이진 푸리에 해석

어떤 양의 정수 $n$ 에 대해 $Z=\{\pm 1\}^{n}$ 이라 하면, 이진 값을 받는 함수 $f(x_{1},\dots,x_{n})$ 을 고려하는 것이 됩니다. 그러면 함수 $Z\to\mathbb{C}$ 들은 $2^{n}$ 차원 벡터 공간 $\mathbb{C}^{Z}$ 를 이루며, 여기에 다음 내적 형식을 부여합니다.

\left<f,g\right>=\frac{1}{2^{n}}\sum_{x\in Z}f(x)\overline{g(x)}.

특히,

\left<f,f\right>=\frac{1}{2^{n}}\sum_{x\in Z}\left\lvert f(x)\right\rvert^{2}

는 제곱의 평균이며, 이로써 $\left<-,-\right>$ 이 양의 정부호임도 확인됩니다.

이 경우 다중선형 다항식들이 $\mathbb{C}^{Z}$ 의 기저를 이룹니다. 즉, 다음 다항식들입니다.

\chi_{S}(x_{1},\dots,x_{n})=\prod_{s\in S}x_{s}.

연습문제 14.3.1.

이들이 실제로 $\left<-,-\right>$ 에 대해 정규직교임을 보이십시오. 이들은 $2^{n}$ 개이므로, 이로써 기저를 이룬다는 것이 증명됩니다.

따라서 우리의 진동수 집합은 실제로 부분집합 $S\subseteq\{1,\dots,n\}$ 들입니다. 따라서 다음과 같은 분해를 얻습니다.

f=\sum_{S\subseteq\{1,\dots,n\}}\widehat{f}(S)\chi_{S}.

예제 14.3.2 (이진 푸리에 해석의 예).

$n=2$ 라고 합시다. 그러면 이진 함수 $\{\pm 1\}^{2}\to\mathbb{C}$ 들은 다음 네 다항식으로 주어지는 기저를 갖습니다.

1,\quad x_{1},\quad x_{2},\quad x_{1}x_{2}.

예를 들어, $(1,1)$ 에서 $1$ 이고 그 외에서는 $0$ 인 함수 $f$ 를 생각해 봅시다. 그러면 다음과 같이 놓을 수 있습니다.

f(x_{1},x_{2})=\frac{x_{1}+1}{2}\cdot\frac{x_{2}+1}{2}=\frac{1}{4}\left(1+x_{1% }+x_{2}+x_{1}x_{2}\right).

따라서 네 개의 $S$ 각각에 대하여 푸리에 계수는 $\widehat{f}(S)=\frac{1}{4}$ 입니다.

이 개념은 특히 이진 함수 $f\colon\{\pm 1\}^{n}\to\{\pm 1\}$ 에 유용합니다. 이러한 함수(및 이들의 곱)에 대해서는 항상 $\left<f,f\right>=1$ 이 성립합니다.

진동수 $\varnothing$ 이 특별한 역할을 한다는 점은 주목할 만합니다:

연습문제 14.3.3.

다음을 보이십시오.

\widehat{f}(\varnothing)=\frac{1}{|Z|}\sum_{x\in Z}f(x).

14.3.2 유한군 $Z$ 위의 푸리에 해석

이번에는 유한 아벨 군 $Z$ 가 주어졌다고 하고, 함수 $Z\to\mathbb{C}$ 들을 생각합시다. 이것은 $|Z|$ 차원 벡터 공간입니다. 내적은 이전과 같습니다:

\left<f,g\right>=\frac{1}{|Z|}\sum_{x\in Z}f(x)\overline{g(x)}.

계속하려면 $Z$ 의 두 원소를 곱할 수 있어야 합니다. 실제로는 어떤 사상을 고르든 별로 중요하지 않아서 이 부분은 다소 번거로우므로, 빠르게 넘어가겠습니다. 남은 문단의 대부분 또는 전부를 건너뛰어도 좋습니다.

정의 14.3.4.

우리는 대칭 비퇴화 쌍선형 형식

\cdot\colon Z\times Z\to\mathbb{T}

을 다음 성질들을 만족하도록 선택합니다:

•

$\xi\cdot(x_{1}+x_{2})=\xi\cdot x_{1}+\xi\cdot x_{2}$ 이고 $(\xi_{1}+\xi_{2})\cdot x=\xi_{1}\cdot x+\xi_{2}\cdot x$ 입니다(이것이 “쌍선형”이라는 말의 의미입니다)
•

$\cdot$ 은 대칭입니다,
•

임의의 $\xi\neq 0$ 에 대하여 $\xi\cdot x\neq 0$ 인 $x$ 가 존재합니다(이것이 “비퇴화”라는 말의 의미입니다).

예제 14.3.5 ( $\mathbb{Z}/n\mathbb{Z}$ 위의 형식).

$Z=\mathbb{Z}/n\mathbb{Z}$ 이면 $\xi\cdot x=(\xi x)/n$ 은 위의 성질들을 만족합니다.

일반적으로 유한 아벨 군은 순환군들의 합으로 분해된다는 사실이 알려져 있으며(절 18.1 참고), 이 덕분에 그러한 $\cdot$ 을 비교적 쉽게 찾을 수 있습니다. 그러나 앞서 말했듯이 그 선택은 중요하지 않으므로 넘어갑시다.

이제 재미있는 부분인 지표의 정의로 넘어갑니다.

명제 14.3.6 ( $e_{\xi}$ 는 정규직교입니다).

각 $\xi\in Z$ 에 대하여 지표를 다음과 같이 정의합니다

e_{\xi}(x)=e(\xi\cdot x).

$|Z|$ 개의 지표는 함수 $Z\to\mathbb{C}$ 들의 공간의 정규직교 기저를 이룹니다.

증명.

이 증명은 건너뛰기를 권장하지만, 다음과 같습니다:

	$\displaystyle\left<e_{\xi},e_{\xi^{\prime}}\right>$	$\displaystyle=\frac{1}{\|Z\|}\sum_{x\in Z}e(\xi\cdot x)\overline{e(\xi^{\prime}% \cdot x)}$
		$\displaystyle=\frac{1}{\|Z\|}\sum_{x\in Z}e(\xi\cdot x)e(-\xi^{\prime}\cdot x)$
		$\displaystyle=\frac{1}{\|Z\|}\sum_{x\in Z}e\left((\xi-\xi^{\prime})\cdot x\right).$

∎

이와 같이 진동수의 집합 역시 $Z$ 이지만, $\xi\in Z$ 는 “물리적인” $x\in Z$ 와는 매우 다른 역할을 합니다. 이해에 도움이 될 만한 예를 하나 들겠습니다.

예제 14.3.7 (세제곱 단위근 필터).

$Z=\mathbb{Z}/3\mathbb{Z}$ 이고 내적 형식이 $\xi\cdot x=(\xi x)/3$ 으로 주어진다고 합시다. $\omega=\exp(\frac{2}{3}\pi i)$ 를 원시 세제곱 단위근이라고 합시다. 다음에 주목하십시오.

e_{\xi}(x)=\begin{cases}1&\xi=0\\ \omega^{x}&\xi=1\\ \omega^{2x}&\xi=2.\end{cases}

그러면 $f(0)=a$ , $f(1)=b$ , $f(2)=c$ 인 $f\colon Z\to\mathbb{C}$ 가 주어졌을 때, 다음을 얻습니다

f(x)=\frac{a+b+c}{3}\cdot 1+\frac{a+\omega^{2}b+\omega c}{3}\cdot\omega^{x}+% \frac{a+\omega b+\omega^{2}c}{3}\cdot\omega^{2x}.

이와 같이 하여 변환이 다음과 같음을 유도합니다

	$\displaystyle\widehat{f}(0)$	$\displaystyle=\frac{a+b+c}{3}$
	$\displaystyle\widehat{f}(1)$	$\displaystyle=\frac{a+\omega^{2}b+\omega c}{3}$
	$\displaystyle\widehat{f}(2)$	$\displaystyle=\frac{a+\omega b+\omega^{2}c}{3}.$

연습문제 14.3.8.

이진 푸리에 해석에서의 $\widehat{f}(\varnothing)$ 과 유사하게, 이제 다음이 성립함을 보이십시오.

\widehat{f}(0)=\frac{1}{|Z|}\sum_{x\in Z}f(x).

올림피아드 참가자라면 앞의 예제가 “단위근 필터”임을 알아볼 수 있을 텐데, 바로 그것이 요점입니다. 구체적으로, 다음을 계산하고 싶다고 합시다.

\binom{1000}{0}+\binom{1000}{3}+\dots+\binom{1000}{999}.

이 경우 다음 함수를 생각할 수 있습니다.

w\colon\mathbb{Z}/3\to\mathbb{C}.

이 함수는 $w(0)=1$ 이지만 $w(1)=w(2)=0$ 을 만족합니다. 표기 남용으로 $w$ 를 함수 $w\colon\mathbb{Z}\twoheadrightarrow\mathbb{Z}/3\to\mathbb{C}$ 로도 생각하겠습니다. 그러면 문제의 합은 다음과 같습니다.

	$\displaystyle\sum_{n}\binom{1000}{n}w(n)$	$\displaystyle=\sum_{n}\binom{1000}{n}\sum_{k=0,1,2}\widehat{w}(k)\omega^{kn}$
		$\displaystyle=\sum_{k=0,1,2}\widehat{w}(k)\sum_{n}\binom{1000}{n}\omega^{kn}$
		$\displaystyle=\sum_{k=0,1,2}\widehat{w}(k)(1+\omega^{k})^{1000}.$

우리 상황에서는 $\widehat{w}(0)=\widehat{w}(1)=\widehat{w}(2)=\frac{1}{3}$ 이며, 이로써 원하는 합을 계산하였습니다. 더 일반적으로, 임의의 주기적 가중치 $w$ 를 택하고 푸리에 해석을 사용하여 합의 순서를 바꿀 수 있습니다.

예제 14.3.9 (이진 푸리에 해석).

$Z=\{\pm 1\}^{n}$ 이라 하고, 이를 점별 곱셈에 대한 아벨 군으로 보아 $(\mathbb{Z}/2\mathbb{Z})^{\oplus n}$ 과 동형이라고 합시다. 다음과 같이 정의된 점곱을 택한다고 가정합시다.

\xi\cdot x\coloneqq\frac{1}{2}\sum_{i}\frac{\xi_{i}-1}{2}\cdot\frac{x_{i}-1}{2}

여기서 $\xi=(\xi_{1},\dots,\xi_{n})$ 이고 $x=(x_{1},\dots,x_{n})$ 입니다.

이것이 우리가 처음 제시한 예와 일치한다고 주장합니다. 실제로, $S\subseteq\{1,\dots,n\}$ 이라 하고, $\xi\in\{\pm 1\}^{n}$ 을 $S$ 에 속하는 위치에서는 $-1$ , $S$ 에 속하지 않는 위치에서는 $+1$ 인 원소라고 합시다. 그러면 앞의 예의 지표 $\chi_{S}$ 는 새 표기법의 지표 $e_{\xi}$ 와 일치합니다. 특히 $\widehat{f}(S)=\widehat{f}(\xi)$ 입니다.

따라서 유한군 $Z$ 위의 푸리에 해석은 이진 푸리에 해석을 포함합니다.

14.3.3 $L^{2}([-\pi,\pi])$ 함수에 대한 푸리에 급수

이것이 가장 유명한 것이며, 따라서 여러분도 들어 보셨을 것입니다.

정의 14.3.10.

공간 $L^{2}([-\pi,\pi])$ 는 적분 $\int_{[-\pi,\pi]}\left\lvert f(x)\right\rvert^{2}\;dx$ 가 존재하고 유한한 모든 함수 $f\colon[-\pi,\pi]\to\mathbb{C}$ 로 이루어지며, “거의 모든 곳”에서 0인 함수는 0과 같다고 간주하는 관계로 나눈 것입니다.¹¹1지금 당장은 중요하지 않으므로 아직 이것을 정의하지 않겠습니다. 하지만 측도론 부분에서 이에 대해 더 자세히 설명하겠습니다. 이것이 관련되는 지점이 하나 있습니다. 흔히 함수 $f$ 가 $f(-\pi)=f(\pi)$ 를 만족하도록 요구하는데, 그러면 $f$ 는 주기 함수가 되고 이를 $f\colon\mathbb{T}\to\mathbb{C}$ 로 생각할 수 있습니다. 한 점에서의 값만 바꾸는 것이므로 본질적인 차이는 없습니다.

이 공간은 다음에 따라 내적 공간이 됩니다.

\left<f,g\right>=\frac{1}{2\pi}\int_{[-\pi,\pi]}f(x)\overline{g(x)}\;dx.

(증명하지는 않겠지만) 이것은 (무한차원) 힐베르트 공간임이 밝혀집니다!

이제 푸리에 해석의 아름다움은 이 공간이 훌륭한 기저를 가진다는 데 있습니다.

정리 14.3.11 (고전적 푸리에 기저).

각 정수 $n$ 에 대하여 다음과 같이 정의합니다.

e_{n}(x)=\exp(inx).

그러면 $e_{n}$ 은 힐베르트 공간 $L^{2}([-\pi,\pi])$ 의 정규직교 기저를 이룹니다.

따라서 이번에는 진동수 집합 $\mathbb{Z}$ 가 무한하며, 다음이 성립합니다.

f(x)=\sum_{n}\widehat{f}(n)\exp(inx)\quad\text{거의 모든 곳}

여기서 계수 $\widehat{f}(n)$ 은 $\sum_{n}\left\lvert\widehat{f}(n)\right\rvert^{2}<\infty$ 를 만족합니다. 진동수 집합의 첨자가 $\mathbb{Z}$ 이므로, 첨자가 $n\in\mathbb{Z}$ 라는 사실을 반영하여 이것을 푸리에 급수라고 부릅니다.

연습문제 14.3.12.

다시 한번 보이십시오.

\widehat{f}(0)=\frac{1}{2\pi}\int_{[-\pi,\pi]}f(x)\;dx.

14.4 요약, 그리고 또 하나의 예고

여러 가지 형태의 푸리에 해석을 다음 표에 요약합니다.

\begin{array}[]{llll}\hline\cr\text{종류}&\text{물리 변수}&\text{진동수 변수}&\text{기저 함수% }\\ \hline\cr\text{이진}&\{\pm 1\}^{n}&\text{부분집합}S\subseteq\left\{1,\dots,n\right\}% &\prod_{s\in S}x_{s}\\ \text{유한군}&Z&\xi\in Z,\text{선택}\cdot&e(\xi\cdot x)\\ \text{푸리에 급수}&\mathbb{T}\text{또는}[-\pi,\pi]&n\in\mathbb{Z}&\exp(inx)\\ \text{이산}&\mathbb{Z}/n\mathbb{Z}&\xi\in\mathbb{Z}/n\mathbb{Z}&e(\xi x/n)\\ \end{array}

$Z=\mathbb{Z}/n\mathbb{Z}$ 인 넷째 행을 슬쩍 끼워 넣었지만, 이것은 둘째 행의 특수한 경우이므로 걱정할 필요는 없습니다.

앞으로의 내용을 암시하자면, 장 39이 어떻게 시작하는지 귀띔해 드리고 싶습니다. 이들 각각은 실제로 어떤 “쌍대” $\widehat{G}$ 에 대하여 $G\to\mathbb{C}$ 함수들을 $\widehat{G}\to\mathbb{C}$ 함수들로 어떻게 표현할 수 있는지에 관한 명제입니다. 그런 의미에서 위의 표를 다음과 같이 다시 쓸 수 있습니다.

\begin{array}[]{llll}\hline\cr\text{이름}&\text{정의역}G&\text{쌍대}\widehat{G}&\text% {지표}\\ \hline\cr\text{이진}&\{\pm 1\}^{n}&S\subseteq\left\{1,\dots,n\right\}&\prod_{s% \in S}x_{s}\\ \text{유한군}&Z&\xi\in\widehat{Z}\cong Z&e(\xi\cdot x)\\ \text{푸리에 급수}&\mathbb{T}\cong[-\pi,\pi]&n\in\mathbb{Z}&\exp(inx)\\ \text{이산}&\mathbb{Z}/n\mathbb{Z}&\xi\in\mathbb{Z}/n\mathbb{Z}&e(\xi x/n)\\ \end{array}

측도를 적분한다는 것이 무엇을 의미하는지 알고 나면, 일반적으로 여러 다양한 정의역 $G$ 에 대해 무언가를 말할 수 있음이 밝혀질 것입니다. 이것이 이른바 폰트랴긴 쌍대성이며, 장 39에서 후속 보너스로 다룹니다.

14.5 파르세발과 그 친구들

이 절은 유명한 이름을 한꺼번에 많이 익힐 수 있는 재미있는 절입니다. 기본적으로 명제 14.2.1의 세 결과를 하나씩 우리의 푸리에 해석의 맥락(여기서는 힐베르트 공간의 정규직교 기저가 주어져 있습니다)으로 옮기면, 유명한 이름이 붙은 결과를 각각 얻을 수 있습니다.

따름정리 14.5.1 (파르세발 정리).

$Z$ 가 유한 아벨 군이고 $f\colon Z\to\mathbb{C}$ 라고 합시다. 그러면

\sum_{\xi}|\widehat{f}(\xi)|^{2}=\frac{1}{|Z|}\sum_{x\in Z}|f(x)|^{2}.

마찬가지로, $f\colon[-\pi,\pi]\to\mathbb{C}$ 가 제곱적분가능하면 그 푸리에 급수는 다음을 만족합니다

\sum_{n}|\widehat{f}(n)|^{2}=\frac{1}{2\pi}\int_{[-\pi,\pi]}|f(x)|^{2}\;dx.

증명.

$\left<f,f\right>$ 는 계수들의 제곱합과 같다는 것을 상기하십시오. ∎

따름정리 14.5.2 (푸리에 역변환 공식).

$Z$ 가 유한 아벨 군이고 $f\colon Z\to\mathbb{C}$ 라고 합시다. 그러면

\widehat{f}(\xi)=\frac{1}{|Z|}\sum_{x\in Z}f(x)\overline{e_{\xi}(x)}.

마찬가지로, $f\colon[-\pi,\pi]\to\mathbb{C}$ 가 제곱적분가능하면 그 푸리에 급수는 다음과 같이 주어집니다

\widehat{f}(n)=\frac{1}{2\pi}\int_{[-\pi,\pi]}f(x)\exp(-inx)\;dx.

증명.

정규직교 기저 $(e_{\xi})_{\xi}$ 에서 $f$ 의 $e_{\xi}$ 계수는 $\left<f,e_{\xi}\right>$ 라는 것을 상기하십시오. ∎

질문 14.5.3.

위에서 $\xi=0$ 이면 어떻게 됩니까?

따름정리 14.5.4 (플랑슈렐 정리).

$Z$ 가 유한 아벨 군이고 $f\colon Z\to\mathbb{C}$ 라고 합시다. 그러면

\left<f,g\right>=\sum_{\xi\in Z}\widehat{f}(\xi)\overline{\widehat{g}(\xi)}.

마찬가지로, $f\colon[-\pi,\pi]\to\mathbb{C}$ 가 제곱적분가능하면 다음이 성립합니다

\left<f,g\right>=\sum_{n}\widehat{f}(n)\overline{\widehat{g}(n)}.

질문 14.5.5.

(앞에서처럼) 이것을 한 줄로 증명하십시오.

14.6 응용: 바젤 문제

$L^{2}([-\pi,\pi])$ 위의 푸리에 해석의 귀여운 응용 하나는, 미적분학을 조금 사용할 의향만 있다면 다른 방법으로는 계산하기 어려운 몇몇 합을 구할 수 있다는 것입니다.

다음은 고전적인 예입니다.

정리 14.6.1 (바젤 문제).

다음이 성립합니다

\sum_{n\geq 1}\frac{1}{n^{2}}=\frac{\pi^{2}}{6}.

증명은 항등함수 $f(x)=x$ 를 생각하는 것인데, 이 함수는 분명히 제곱적분가능합니다. 그러면 파르세발 정리에 의해 다음을 얻습니다

\sum_{n\in\mathbb{Z}}\left\lvert\widehat{f}(n)\right\rvert^{2}=\left<f,f\right% >=\frac{1}{2\pi}\int_{[-\pi,\pi]}\left\lvert f(x)\right\rvert^{2}\;dx.

미적분학 계산을 하면 다음을 얻습니다.

\frac{1}{2\pi}\int_{[-\pi,\pi]}x^{2}\;dx=\frac{\pi^{2}}{3}.

한편, 이제 모든 푸리에 계수를 계산하겠습니다. 이미 다음을 알고 있습니다

\widehat{f}(0)=\frac{1}{2\pi}\int_{[-\pi,\pi]}f(x)\;dx=\frac{1}{2\pi}\int_{[-% \pi,\pi]}x\;dx=0.

$n\neq 0$ 에 대하여, 정의에 의해(거창한 말을 쓰고 싶다면 “푸리에 역변환 공식”에 의해) 다음 공식을 얻습니다

	$\displaystyle\widehat{f}(n)$	$\displaystyle=\left<f,\exp(inx)\right>$
		$\displaystyle=\frac{1}{2\pi}\int_{[-\pi,\pi]}x\cdot\overline{\exp(inx)}\;dx$
		$\displaystyle=\frac{1}{2\pi}\int_{[-\pi,\pi]}x\exp(-inx)\;dx.$

원시함수는 $\frac{1}{n^{2}}\exp(-inx)(1+inx)$ 와 같으므로, 계산을 조금 더 하면 다음을 얻습니다

\widehat{f}(n)=\frac{(-1)^{n}}{n}i.

따라서

\sum_{n}\left\lvert\widehat{f}(n)\right\rvert^{2}=2\sum_{n\geq 1}\frac{1}{n^{2}}

이므로 결과가 따라 나옵니다.

14.7 응용: 애로의 불가능성 정리

이진 푸리에 해석의 응용으로서, 이제 애로의 정리의 한 형태를 증명하겠습니다.

$n$ 명의 투표자가 $3$ 명의 후보 $A$ , $B$ , $C$ 중에서 투표한다고 생각해 봅시다. 각 투표자는 다음과 같이 순서쌍 $v_{i}=(x_{i},y_{i},z_{i})\in\{\pm 1\}^{3}$ 을 정합니다.

•

사람 $i$ 가 $A$ 를 $B$ 보다 높은 순위에 두면 $x_{i}=1$ 이고, 그렇지 않으면 $x_{i}=-1$ 입니다.
•

사람 $i$ 가 $B$ 를 $C$ 보다 높은 순위에 두면 $y_{i}=1$ 이고, 그렇지 않으면 $y_{i}=-1$ 입니다.
•

사람 $i$ 가 $C$ 를 $A$ 보다 높은 순위에 두면 $z_{i}=1$ 이고, 그렇지 않으면 $z_{i}=-1$ 입니다.

암묵적으로, 우리는 $v_{i}$ 에 대해 $3!=6$ 가지 가능성만 고려합니다. 즉, 사람들의 투표가 일관적이라고(선호가 추이적이라는 뜻입니다) 가정함으로써 $x_{i}=y_{i}=z_{i}$ 꼴의 “역설적인” 투표를 배제합니다.

간결하게 쓰기 위해 $x_{\bullet}=(x_{1},\dots,x_{n})$ 이라 두고, $y_{\bullet}$ 와 $z_{\bullet}$ 도 마찬가지로 정의합시다. 그러면 다음과 같은 투표 메커니즘을 생각할 수 있습니다.

	$\displaystyle f\colon\{\pm 1\}^{n}$	$\displaystyle\to\{\pm 1\}$
	$\displaystyle g\colon\{\pm 1\}^{n}$	$\displaystyle\to\{\pm 1\}$
	$\displaystyle h\colon\{\pm 1\}^{n}$	$\displaystyle\to\{\pm 1\}$

이 메커니즘은 다음을 만족합니다.

•

$f(x_{\bullet})$ 는 $A$ 대 $B$ 에 대한 전체 선호이고,
•

$g(y_{\bullet})$ 는 $B$ 대 $C$ 에 대한 전체 선호이며,
•

$h(z_{\bullet})$ 는 $C$ 대 $A$ 에 대한 전체 선호입니다.

우리는 전체 선호 $(f(x_{\bullet}),g(y_{\bullet}),h(z_{\bullet}))$ 자체가 역설적인 상황을 피하고자 합니다.

$\mathbb{E}f$ 를 $2^{n}$ 개의 모든 입력에 대한 $f$ 의 평균값이라고 합시다. $\mathbb{E}g$ 와 $\mathbb{E}h$ 도 마찬가지로 정의합니다. 여기에 $\mathbb{E}f=\mathbb{E}g=\mathbb{E}h=0$ 이라는 가정을 추가하는데, 이 가정은 대칭성을 제공합니다(그리고 예를 들어 $f$ , $g$ , $h$ 가 투표자의 입력을 무시하는 상수 함수일 가능성을 배제합니다). 이를 바탕으로 다음 결과를 증명하겠습니다.

정리 14.7.1 (애로(Arrow)의 불가능성 정리).

$(f,g,h)$ 가 항상 역설적인 결과를 피한다고 가정하고, $\mathbb{E}f=\mathbb{E}g=\mathbb{E}h=0$ 이라고 가정합니다. 그러면 $(f,g,h)$ 는 독재이거나 반독재입니다. 즉, 다음을 만족하는 “독재자” $k$ 가 존재합니다.

f(x_{\bullet})=\pm x_{k},\qquad g(y_{\bullet})=\pm y_{k},\qquad h(z_{\bullet})% =\pm z_{k}

여기서 세 부호는 모두 일치합니다.

일반적인 애로(Arrow)의 정리와 달리, 여기서는 $f(+1,\dots,+1)=+1$ 이라고 가정하지 않습니다(그래서 반독재의 가능성이 있습니다).

증명.

투표자들이 각자 $3!=6$ 가지의 가능한 일관적인 투표 중 하나를 무작위로 선택한다고 가정합시다. 문제 14B에서는 임의의 함수 $f$ , $g$ , $h$ 에 대해 역설적인 결과가 나올 정확한 확률이 정확히 다음과 같이 주어짐을 보입니다.

\frac{1}{4}+\frac{1}{4}\sum_{S\subseteq\{1,\dots,n\}}\left(-\frac{1}{3}\right)% ^{\left\lvert S\right\rvert}\left(\widehat{f}(S)\widehat{g}(S)+\widehat{g}(S)% \widehat{h}(S)+\widehat{h}(S)\widehat{f}(S)\right).

이 (역설적인 결과가 나올) 확률이 $0$ 이라고 가정합시다. 그러면 다음을 유도할 수 있습니다.

1=\sum_{S\subseteq\{1,\dots,n\}}-\left(-\frac{1}{3}\right)^{\left\lvert S% \right\rvert}\left(\widehat{f}(S)\widehat{g}(S)+\widehat{g}(S)\widehat{h}(S)+% \widehat{h}(S)\widehat{f}(S)\right).

그런데 이제는 약한 부등식만 사용하면 됩니다. $\widehat{f}(\varnothing)=\mathbb{E}f=0$ 이고 $\widehat{g}$ 와 $\widehat{h}$ 에 대해서도 마찬가지이므로, $|S|\geq 1$ 인 경우에만 주목하면 됩니다. 그런 다음 (모든 실수에 대해 성립하는) 유명한 부등식 $|ab+bc+ca|\leq a^{2}+b^{2}+c^{2}$ 을 결합하여 다음을 이끌어냅니다.

	$\displaystyle 1$	$\displaystyle=\sum_{S\subseteq\{1,\dots,n\}}-\left(-\frac{1}{3}\right)^{\left% \lvert S\right\rvert}\left(\widehat{f}(S)\widehat{g}(S)+\widehat{g}(S)\widehat% {h}(S)+\widehat{h}(S)\widehat{f}(S)\right)$
		$\displaystyle\leq\sum_{S\subseteq\{1,\dots,n\}}\left(\frac{1}{3}\right)^{\left% \lvert S\right\rvert}\left(\widehat{f}(S)^{2}+\widehat{g}(S)^{2}+\widehat{h}(S% )^{2}\right)$
		$\displaystyle\leq\sum_{S\subseteq\{1,\dots,n\}}\left(\frac{1}{3}\right)^{1}% \left(\widehat{f}(S)^{2}+\widehat{g}(S)^{2}+\widehat{h}(S)^{2}\right)$
		$\displaystyle=\frac{1}{3}(1+1+1)=1.$

마지막 단계에서는 파스발 항등식을 사용했습니다. 따라서 모든 부등식에서 등호가 성립해야 하며, 특히 $\widehat{f}$ , $\widehat{g}$ , $\widehat{h}$ 는 원소가 하나인 집합 위에서만 0이 아닌 값을 가집니다. 즉, 이들은 입력에 대해 선형입니다. $f$ , $g$ , $h$ 는 $\pm 1$ 값을 가지므로, 각각의 $f$ , $g$ , $h$ 는 그 자체로 독재자 함수이거나 반독재자 함수입니다. $(f,g,h)$ 는 항상 일관적이므로, 이로부터 최종 결과가 따라 나옵니다. ∎

14.8 생각해 볼 만한 조금 더 어려운 문제

문제 14A (미적분학 애호가를 위하여).

다음을 증명하십시오.

\sum_{n\geq 1}\frac{1}{n^{4}}=\frac{\pi^{4}}{90}.

힌트. 다시 파스발 항등식을 사용하되, 이번에는 $f(x)=x^{2}$ 에 적용하십시오.

문제 14B.

^†^†margin:

$f,g,h\colon\{\pm 1\}^{n}\to\{\pm 1\}$ 를 임의의 세 함수라고 합시다. 각 $i$ 에 대해, 모두가 같지는 않다는 제약 조건 아래에서 $(x_{i},y_{i},z_{i})\in\{\pm 1\}^{3}$ 를 무작위로 선택합니다(따라서 $2^{3}-2=6$ 가지 가능성 중에서 선택합니다). 다음이 성립할 확률이

f(x_{1},\dots,x_{n})=g(y_{1},\dots,y_{n})=h(z_{1},\dots,z_{n})

다음 공식으로 주어짐을 증명하십시오.

\frac{1}{4}+\frac{1}{4}\sum_{S\subseteq\{1,\dots,n\}}\left(-\frac{1}{3}\right)% ^{\left\lvert S\right\rvert}\left(\widehat{f}(S)\widehat{g}(S)+\widehat{g}(S)% \widehat{h}(S)+\widehat{h}(S)\widehat{f}(S)\right)

힌트. 불 함수 $D\colon\{\pm 1\}^{3}\to\mathbb{R}$ 를 $D(a,b,c)=ab+bc+ca$ 로 정의합시다. 각 $(a,b,c)$ 에 대해 $D(a,b,c)$ 의 값을 적어 보십시오. 그런 다음 그 기댓값을 계산하십시오.

풀이. 불 함수 $D\colon\{\pm 1\}^{3}\to\mathbb{R}$ 를 다음과 같이 정의합시다.

$D(a,b,c)=ab+bc+ca=\begin{cases}3&a,b,c\text{모두 같음}\\ -1&a,b,c\text{모두 같지는 않음}.\end{cases}.$

따라서 역설적인 결과는 $D(f(x_{\bullet}),g(y_{\bullet}),h(z_{\bullet}))=3$ 일 때 발생합니다. 이제 무작위로 선택된 $x_{\bullet}$ , $y_{\bullet}$ , $z_{\bullet}$ 에 대해 다음을 계산합니다.

$\displaystyle\mathbb{E}D(f(x_{\bullet}),g(y_{\bullet}),h(z_{\bullet}))$ $\displaystyle=\mathbb{E}\sum_{S}\sum_{T}\left(\widehat{f}(S)\widehat{g}(T)+% \widehat{g}(S)\widehat{h}(T)+\widehat{h}(S)\widehat{f}(T)\right)\left(\chi_{S}% (x_{\bullet})\chi_{T}(y_{\bullet})\right)$

$\displaystyle=\sum_{S}\sum_{T}\left(\widehat{f}(S)\widehat{g}(T)+\widehat{g}(S% )\widehat{h}(T)+\widehat{h}(S)\widehat{f}(T)\right)\mathbb{E}\left(\chi_{S}(x_% {\bullet})\chi_{T}(y_{\bullet})\right).$

이제 다음을 관찰합니다.

•

$S\neq T$ 이면 $\mathbb{E}\chi_{S}(x_{\bullet})\chi_{T}(y_{\bullet})=0$ 입니다. 예를 들어 $s\in S$ , $s\notin T$ 라고 하면, $x_{s}$ 에 따라 곱의 홀짝성은 각각 50%의 확률로 어느 쪽이든 되며, $x_{s}$ 는 곱에 있는 다른 어떤 변수와도 독립이기 때문입니다.

•

반면 $S=T$ 라고 가정합시다. 그러면 다음이 성립합니다.

$\chi_{S}(x_{\bullet})\chi_{T}(y_{\bullet})=\prod_{s\in S}x_{s}y_{s}.$

$x_{s}y_{s}$ 는 확률 $\frac{1}{3}$ 로 $1$ 이고 확률 $\frac{2}{3}$ 로 $-1$ 임에 유의하십시오( $(x_{s},y_{s},z_{s})$ 는 $3!=6$ 가지 경우 중에서 균등하게 선택되며, 이 경우들은 직접 나열해 볼 수 있기 때문입니다). 이로부터 $|S|$ 에 대한 귀납적 계산을 하면 다음을 얻습니다.

$\prod_{s\in S}x_{s}y_{s}=\begin{cases}+1&\text{확률}\frac{1}{2}(1+(-1/3)^{|S|})% \\ -1&\text{확률}\frac{1}{2}(1-(-1/3)^{|S|}).\end{cases}$

따라서 다음이 성립합니다.

$\mathbb{E}\left(\prod_{s\in S}x_{s}y_{s}\right)=\left(-\frac{1}{3}\right)^{|S|}.$

이 모든 것을 종합하면, 이제 다음을 얻습니다.

$\mathbb{E}D(f(x_{\bullet}),g(y_{\bullet}),h(z_{\bullet}))=\sum_{S}\left(% \widehat{f}(S)\widehat{g}(S)+\widehat{g}(S)\widehat{h}(S)+\widehat{h}(S)% \widehat{f}(S)\right)\left(-\frac{1}{3}\right)^{|S|}.$

그러면 다음을 얻습니다.

$\displaystyle\mathbb{E}\frac{1}{4}\left(1+D(f(x_{\bullet}),g(y_{\bullet}),h(z_% {\bullet}))\right)$

$\displaystyle=$ $\displaystyle\frac{1}{4}+\frac{1}{4}\sum_{S}\left(\widehat{f}(S)\widehat{g}(S)% +\widehat{g}(S)\widehat{h}(S)+\widehat{h}(S)\widehat{f}(S)\right)\left(-\frac{% 1}{3}\right)^{|S|}.$

이를 $D$ 의 정의와 비교하면 원하는 결과를 얻습니다.

	$\displaystyle\left<e_{\xi},e_{\xi^{\prime}}\right>$	$\displaystyle=\frac{1}{\|Z\|}\sum_{x\in Z}e(\xi\cdot x)\overline{e(\xi^{\prime}% \cdot x)}$
		$\displaystyle=\frac{1}{\|Z\|}\sum_{x\in Z}e(\xi\cdot x)e(-\xi^{\prime}\cdot x)$
		$\displaystyle=\frac{1}{\|Z\|}\sum_{x\in Z}e\left((\xi-\xi^{\prime})\cdot x\right).$

	$\displaystyle\mathbb{E}D(f(x_{\bullet}),g(y_{\bullet}),h(z_{\bullet}))$	$\displaystyle=\mathbb{E}\sum_{S}\sum_{T}\left(\widehat{f}(S)\widehat{g}(T)+% \widehat{g}(S)\widehat{h}(T)+\widehat{h}(S)\widehat{f}(T)\right)\left(\chi_{S}% (x_{\bullet})\chi_{T}(y_{\bullet})\right)$
		$\displaystyle=\sum_{S}\sum_{T}\left(\widehat{f}(S)\widehat{g}(T)+\widehat{g}(S% )\widehat{h}(T)+\widehat{h}(S)\widehat{f}(T)\right)\mathbb{E}\left(\chi_{S}(x_% {\bullet})\chi_{T}(y_{\bullet})\right).$

		$\displaystyle\mathbb{E}\frac{1}{4}\left(1+D(f(x_{\bullet}),g(y_{\bullet}),h(z_% {\bullet}))\right)$
	$\displaystyle=$	$\displaystyle\frac{1}{4}+\frac{1}{4}\sum_{S}\left(\widehat{f}(S)\widehat{g}(S)% +\widehat{g}(S)\widehat{h}(S)+\widehat{h}(S)\widehat{f}(S)\right)\left(-\frac{% 1}{3}\right)^{\|S\|}.$

장 14 보너스: 푸리에 해석

14.1 개요

14.2 힐베르트 공간에 대한 복습

명제 14.2.1 (정규직교 기저에 관한 사실).

연습문제 14.2.2.

14.3 흔한 예

14.3.1 {±1}n 위의 이진 푸리에 해석

연습문제 14.3.1.

예제 14.3.2 (이진 푸리에 해석의 예).

연습문제 14.3.3.

14.3.2 유한군 Z 위의 푸리에 해석

정의 14.3.4.

예제 14.3.5 (ℤ/nℤ 위의 형식).

명제 14.3.6 (eξ는 정규직교입니다).

증명.

예제 14.3.7 (세제곱 단위근 필터).

연습문제 14.3.8.

예제 14.3.9 (이진 푸리에 해석).

14.3.3 L2([−π,π]) 함수에 대한 푸리에 급수

정의 14.3.10.

정리 14.3.11 (고전적 푸리에 기저).

연습문제 14.3.12.

14.4 요약, 그리고 또 하나의 예고

14.5 파르세발과 그 친구들

따름정리 14.5.1 (파르세발 정리).

증명.

따름정리 14.5.2 (푸리에 역변환 공식).

증명.

질문 14.5.3.

따름정리 14.5.4 (플랑슈렐 정리).

질문 14.5.5.

14.6 응용: 바젤 문제

정리 14.6.1 (바젤 문제).

14.7 응용: 애로의 불가능성 정리

정리 14.7.1 (애로(Arrow)의 불가능성 정리).

증명.

14.8 생각해 볼 만한 조금 더 어려운 문제

문제 14A (미적분학 애호가를 위하여).

문제 14B.

14.3.1 $\{\pm 1\}^{n}$ 위의 이진 푸리에 해석

14.3.2 유한군 $Z$ 위의 푸리에 해석

예제 14.3.5 ( $\mathbb{Z}/n\mathbb{Z}$ 위의 형식).

명제 14.3.6 ( $e_{\xi}$ 는 정규직교입니다).

14.3.3 $L^{2}([-\pi,\pi])$ 함수에 대한 푸리에 급수