장 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}$ 라 하고 지표(characters)라고 부릅니다. 첨수 $\xi$ 는 진동수(frequencies)라고 부릅니다. 이 경우 기저가 있으므로, 모든 함수 $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>$ 을 갖는 복소 힐베르트 공간이라 하고, $x=\sum_{\xi}a_{\xi}e_{\xi}$ , $y=\sum_{\xi}b_{\xi}e_{\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이 어떻게 시작하는지 힌트를 드리고 싶습니다. 이들 각각은 실제로 $G\to\mathbb{C}$ 의 함수들이 어떤 ”쌍대” $\widehat{G}$ 에 대한 함수 $\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 Parseval과 그 친구들

여기서는 많은 유명한 이름들을 빠르게 배울 수 있는 재미있는 절입니다. 기본적으로 명제 14.2.1의 세 가지 결과 각각을 우리의 푸리에 해석 맥락(여기서는 힐베르트 공간의 정규직교 기저를 가지고 있습니다)으로 옮겨서 유명한 결과를 얻을 수 있습니다.

따름정리 14.5.1 (Parseval 정리).

$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 (Plancherel 정리).

$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$ 를 고려하는 것입니다. 그러면 Parseval에 의해 다음을 얻습니다

\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 응용: Arrow의 불가능성 정리

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

$3$ 명의 후보 $A$ , $B$ , $C$ 중에서 투표하는 $n$ 명의 유권자를 고려합시다. 각 유권자는 다음과 같이 튜플 $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 (애로 불가능성 정리).

$(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}

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

보통의 애로 정리와 달리, 우리는 $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}$ 는 단일 원소 집합에서만 지지되어야 합니다. 즉, 입력에 대해 선형입니다. $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%의 확률로 영향을 미치며, 곱 안의 다른 변수들과 독립적이기 때문입니다.

•

반면, $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 Parseval과 그 친구들

따름정리 14.5.1 (Parseval 정리).

증명.

따름정리 14.5.2 (푸리에 반전 공식).

증명.

질문 14.5.3.

따름정리 14.5.4 (Plancherel 정리).

질문 14.5.5.

14.6 응용: 바젤 문제

정리 14.6.1 (바젤 문제).

14.7 응용: Arrow의 불가능성 정리

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

증명.

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])$ 에 대한 푸리에 급수