\chapter{Bonus: Fourier analysis}
\label{ch:fourier}
Now that we've worked hard to define abstract inner product spaces,
I want to give an (optional) application:
how to set up Fourier analysis correctly, using this language.

For fun, I also prove a form of Arrow's Impossibility Theorem
using binary Fourier analysis.

In what follows, we let $\TT = \RR/\ZZ$ denote the ``circle group'',
thought of as the additive group of ``real numbers modulo $1$''.
There is a canonical map $e \colon \TT \to \CC$ sending $\TT$ to the
complex unit circle, given by
\[ e(\theta) = \exp(2\pi i \theta). \]

\section{Synopsis}
Suppose we have a domain $Z$ and are interested in functions $f \colon Z \to \CC$.
Naturally, the set of such functions form a complex vector space.
We like to equip the set of such functions
with a positive definite \emph{inner product}.
% usually something like $\left< f,g \right> = \EE_{x \in Z} f(x) \ol{g(x)}$.
%which makes the set of such functions into a normed vector space.
%(Here $\EE$ is an ``average'', which is a finite sum if $|Z| < \infty$
%but otherwise is usually an integral.)
%In particular, $\left< f,f\right>$ is the average of $|f(x)|^2$;
%and thus gives a positive definite inner form.

The idea of Fourier analysis is to then select an \emph{orthonormal basis}
for this set of functions, say $(e_\xi)_{\xi}$,
which we call the \vocab{characters};
the indexing $\xi$ are called \vocab{frequencies}.
In that case, since we have a basis, every function $f \colon Z \to \CC$
becomes a sum
\[ f(x) = \sum_{\xi} \wh f(\xi) e_\xi \]
where $\wh f(\xi)$ are complex coefficients of the basis;
appropriately we call $\wh f$ the \vocab{Fourier coefficients}.
The variable $x \in Z$ is referred to as the \vocab{physical} variable.
This is generally good because the characters are deliberately chosen
to be nice ``symmetric'' functions,
like sine or cosine waves or other periodic functions.
Thus we decompose an arbitrarily complicated function into a sum of nice ones.

\section{A reminder on Hilbert spaces}
For convenience, we record a few facts about orthonormal bases.
\begin{proposition}
	[Facts about orthonormal bases]
	\label{prop:orthonormal}
	Let $V$ be a complex Hilbert space
	with inner form $\left< -,-\right>$
	and suppose $x = \sum_\xi a_\xi e_\xi$ and $y = \sum_\xi b_\xi e_\xi$
	where $e_\xi$ are an orthonormal basis.
	Then
	\begin{align*}
		\left< x,x \right> &= \sum_\xi |a_\xi|^2 \\
		a_\xi &= \left< x, e_\xi \right> \\
		\left< x,y \right> &= \sum_\xi a_\xi \ol{b_\xi}.
	\end{align*}
\end{proposition}
\begin{exercise}
	Prove all of these.
	(You don't need any of the preceding section,
	it's only there to motivate the notation with lots of scary $\xi$'s.)
\end{exercise}

In what follows,
most of the examples will be of finite-dimensional inner product spaces
(which are thus Hilbert spaces),
but the example of ``square-integrable functions''
will actually be an infinite dimensional example.
Fortunately, as I alluded to earlier,
this is no cause for alarm
and you can mostly close your eyes and not worry about infinity.

\section{Common examples}
\subsection{Binary Fourier analysis on $\{\pm1\}^n$}
Let $Z = \{\pm 1\}^n$ for some positive integer $n$,
so we are considering functions $f(x_1, \dots, x_n)$ accepting binary values.
Then the functions $Z \to \CC$ form a $2^n$-dimensional vector space $\CC^Z$,
and we endow it with the inner form
\[ \left< f,g \right> = \frac{1}{2^n} \sum_{x \in Z} f(x) \ol{g(x)}. \]
In particular,
\[ \left< f,f \right>
	= \frac{1}{2^n} \sum_{x \in Z} \left\lvert f(x) \right\rvert^2 \]
is the average of the squares;
this establishes also that $\left< -,-\right>$ is positive definite.

In that case, the \vocab{multilinear polynomials} form a basis of $\CC^Z$,
that is the polynomials
\[ \chi_S(x_1, \dots, x_n) = \prod_{s \in S} x_s. \]
\begin{exercise}
	Show that they're actually orthonormal under $\left< -,-\right>$.
	This proves they form a basis, since there are $2^n$ of them.
\end{exercise}
Thus our frequency set is actually the subsets $S \subseteq \{1, \dots, n\}$.
Thus, we have a decomposition
\[ f = \sum_{S \subseteq \{1, \dots, n\}} \wh f(S) \chi_S. \]
\begin{example}
	[An example of binary Fourier analysis]
	Let $n = 2$.
	Then binary functions $\{ \pm 1\}^2 \to \CC$ have a basis
	given by the four polynomials
	\[ 1, \quad x_1, \quad x_2, \quad x_1x_2. \]
	For example, consider the function $f$
	which is $1$ at $(1,1)$ and $0$ elsewhere.
	Then we can put
	\[ f(x_1, x_2) = \frac{x_1+1}{2} \cdot \frac{x_2+1}{2}
		= \frac14 \left( 1 + x_1 + x_2 + x_1x_2 \right). \]
	So the Fourier coefficients are $\wh f(S) = \frac 14$
	for each of the four $S$'s.
\end{example}
This notion is useful in particular for
binary functions $f \colon \{\pm1\}^n \to \{\pm1\}$;
for these functions (and products thereof),
we always have $\left< f,f \right> = 1$.

It is worth noting that the frequency $\varnothing$ plays a special role:
\begin{exercise}
	Show that
	\[ \wh f(\varnothing) = \frac{1}{|Z|} \sum_{x \in Z} f(x). \]
\end{exercise}

\subsection{Fourier analysis on finite groups $Z$}
This time, suppose we have a finite abelian group $Z$,
and consider functions $Z \to \CC$;
this is a $|Z|$-dimensional vector space.
The inner product is the same as before:
\[ \left< f,g \right> = \frac{1}{|Z|} \sum_{x \in Z} f(x) \ol{g(x)}. \]

To proceed, we'll need to be able to multiply two elements of $Z$.
This is a bit of a nuisance since it actually won't really
matter what map I pick, so I'll move briskly;
feel free to skip most or all of the remaining paragraph.
\begin{definition}
We select a \emph{symmetric non-degenerate bilinear form}
\[ \cdot \colon Z \times Z \to \TT \]
satisfying the following properties:
\begin{itemize}
	\ii $\xi \cdot (x_1 + x_2) = \xi \cdot x_1 + \xi \cdot x_2$
	and $(\xi_1 + \xi_2) \cdot x = \xi_1 \cdot x + \xi_2 \cdot x$
	(this is the word ``bilinear'')
	\ii $\cdot$ is symmetric,
	\ii For any $\xi \neq 0$, there is an $x$ with $\xi \cdot x \neq 0$
	(this is the word ``nondegenerate'').
\end{itemize}
\end{definition}
\begin{example}
	[The form on $\Zc n$]
	If $Z = \Zc n$ then $\xi \cdot x = (\xi x)/n$ satisfies the above.
\end{example}
In general, it turns out finite abelian groups
decompose as the sum of cyclic groups (see \Cref{sec:FTFGAG}),
which makes it relatively easy to find such a $\cdot$;
but as I said the choice won't matter, so let's move on.

Now for the fun part: defining the characters.
\begin{proposition}
	[$e_\xi$ are orthonormal]
	For each $\xi \in Z$ we define the character
	\[ e_\xi(x) = e(\xi \cdot x). \]
	The $|Z|$ characters form an orthonormal basis of the
	space of functions $Z \to \CC$.
\end{proposition}
\begin{proof}
	I recommend skipping this one, but it is:
	\begin{align*}
		\left< e_{\xi}, e_{\xi'} \right>
		&= \frac{1}{|Z|} \sum_{x \in Z} e(\xi \cdot x) \ol{e(\xi' \cdot x)} \\
		&= \frac{1}{|Z|} \sum_{x \in Z} e(\xi \cdot x) e(-\xi' \cdot x) \\
		&= \frac{1}{|Z|} \sum_{x \in Z} e\left( (\xi-\xi') \cdot x \right).
	\end{align*}
\end{proof}

In this way, the set of frequencies is also $Z$,
but the $\xi \in Z$ play very different roles from the ``physical'' $x \in Z$.
Here is an example which might be enlightening.
\begin{example}
	[Cube roots of unity filter]
	Suppose $Z = \Zc3$, with the inner form given by $\xi \cdot x = (\xi x)/3$.
	Let $\omega = \exp(\frac 23 \pi i)$ be a primitive cube root of unity.
	Note that
	\[ e_\xi(x) = \begin{cases}
			1 & \xi = 0 \\
			\omega^x & \xi = 1 \\
			\omega^{2x} & \xi = 2.
		\end{cases} \]
	Then given $f \colon Z \to \CC$ with $f(0) = a$, $f(1) = b$, $f(2) = c$,
	we obtain
	\[ 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}.  \]
	In this way we derive that the transforms are
	\begin{align*}
		\wh f(0) &= \frac{a+b+c}{3} \\
		\wh f(1) &= \frac{a+\omega^2 b+ \omega c}{3} \\
		\wh f(2) &= \frac{a+\omega b+\omega^2c}{3}.
	\end{align*}
\end{example}
\begin{exercise}
	Show that in analogy to $\wh f(\varnothing)$
	for binary Fourier analysis, we now have
	\[ \wh f(0) = \frac{1}{|Z|} \sum_{x \in Z} f(x). \]
\end{exercise}
Olympiad contestants may recognize the previous example
as a ``roots of unity filter'', which is exactly the point.
For concreteness, suppose one wants to compute
\[ \binom{1000}{0} + \binom{1000}{3} + \dots + \binom{1000}{999}. \]
In that case, we can consider the function
\[ w \colon \ZZ/3 \to \CC. \]
such that $w(0) = 1$ but $w(1) = w(2) = 0$.
By abuse of notation we will also think of $w$
as a function $w \colon \ZZ \surjto \ZZ/3 \to \CC$.
Then the sum in question is
\begin{align*}
	\sum_n \binom{1000}{n} w(n)
	&= \sum_n \binom{1000}{n} \sum_{k=0,1,2} \wh w(k) \omega^{kn} \\
	&= \sum_{k=0,1,2} \wh w(k) \sum_n \binom{1000}{n} \omega^{kn} \\
	&= \sum_{k=0,1,2} \wh w(k) (1+\omega^k)^{1000}.
\end{align*}
In our situation, we have $\wh w(0) = \wh w(1) = \wh w(2) = \frac13$,
and we have evaluated the desired sum.
More generally, we can take any periodic weight $w$
and use Fourier analysis in order to interchange the order of summation.

\begin{example}
	[Binary Fourier analysis]
	Suppose $Z = \{\pm 1\}^n$, viewed as an abelian group
	under pointwise multiplication
	hence isomorphic to $(\ZZ/2\ZZ)^{\oplus n}$.
	Assume we pick the dot product defined by
	\[  \xi \cdot x \defeq \half \sum_i \frac{\xi_i-1}{2} \cdot \frac{x_i-1}{2} \]
	where $\xi = (\xi_1, \dots, \xi_n)$ and $x = (x_1, \dots, x_n)$.

	We claim this coincides with the first example we gave.
	Indeed, let $S \subseteq \{1, \dots, n\}$
	and let $\xi \in \{\pm1\}^n$ which is $-1$ at positions in $S$,
	and $+1$ at positions not in $S$.
	Then the character $\chi_S$ from the previous example
	coincides with the character $e_\xi$ in the new notation.
	In particular, $\wh f(S) = \wh f(\xi)$.

	Thus Fourier analysis on a finite group $Z$ subsumes
	binary Fourier analysis.
\end{example}

\subsection{Fourier series for functions $L^2([-\pi, \pi])$}
This is the most famous one, and hence the one you've heard of.
\begin{definition}
	The space $L^2([-\pi, \pi])$ consists of all functions
	$f \colon [-\pi, \pi] \to \CC$ such that
	the integral
	$\int_{[-\pi, \pi]} \left\lvert f(x) \right\rvert^2 \; dx$
	exists and is finite,
	modulo the relation that a function which is zero ``almost everywhere''
	is considered to equal zero.\footnote{We won't define this, yet,
		as it won't matter to us for now.
		But we will elaborate more on this in the parts on measure theory.

		There is one point at which this is relevant.
		Often we require that the function $f$ satisfies $f(-\pi) = f(\pi)$,
		so that $f$ becomes a periodic function,
		and we can think of it as $f \colon \TT \to \CC$.
		This makes no essential difference
		since we merely change the value at one point.}

	It is made into an inner product space according to
	\[ \left< f,g \right>
		= \frac{1}{2\pi} \int_{[-\pi, \pi]} f(x) \ol{g(x)} \; dx. \]
\end{definition}
It turns out (we won't prove) that this is an
(infinite-dimensional) Hilbert space!

Now, the beauty of Fourier analysis is that
\textbf{this space has a great basis}:
\begin{theorem}
	[The classical Fourier basis]
	For each integer $n$, define
	\[ e_n(x) = \exp(inx). \]
	Then $e_n$ form an orthonormal basis
	of the Hilbert space $L^2([-\pi, \pi])$.
\end{theorem}
Thus this time the frequency set $\ZZ$ is infinite, and we have
\[ f(x) = \sum_n \wh f(n) \exp(inx)
	\quad\text{almost everywhere} \]
for coefficients $\wh f(n)$
with $\sum_n \left\lvert \wh f(n) \right\rvert^2 < \infty$.
Since the frequency set is indexed by $\ZZ$,
we call this a \vocab{Fourier series}
to reflect the fact that the index is $n \in \ZZ$.
\begin{exercise}
	Show once again
	\[ \wh f(0) = \frac{1}{2\pi} \int_{[-\pi, \pi]} f(x) \; dx. \]
\end{exercise}

\section{Summary, and another teaser}
We summarize our various flavors of Fourier analysis in the following table.
\[
	\begin{array}{llll}
		\hline
		\text{Type} & \text{Physical var} & \text{Frequency var}
			& \text{Basis functions} \\ \hline
		\text{Binary} & \{\pm1\}^n
			& \text{Subsets } S \subseteq \left\{ 1, \dots, n \right\}
			& \prod_{s \in S} x_s \\
		\text{Finite group} & Z & \xi \in Z, \text{ choice of } \cdot
			& e(\xi \cdot x) \\
		\text{Fourier series} & \TT \text{ or } [-\pi, \pi] & n \in \ZZ
			& \exp(inx) \\
		\text{Discrete} & \Zc n
			& \xi \in \Zc n
			& e(\xi x / n) \\
	\end{array}
\]
I snuck in a fourth row with $Z  = \Zc n$,
but it's a special case of the second row, so no cause for alarm.

Alluding to the future, I want to hint at how \Cref{ch:pontryagin} starts.
Each one of these is really a statement
about how functions from $G \to \CC$
can be expressed in terms of functions $\wh G \to \CC$,
for some ``dual'' $\wh G$.
In that sense, we could rewrite the above table as:
\[
	\begin{array}{llll}
		\hline
		\text{Name} & \text{Domain }G & \text{Dual }\wh G
			& \text{Characters} \\ \hline
		\text{Binary} & \{\pm1\}^n
			& S \subseteq \left\{ 1, \dots, n \right\}
			& \prod_{s \in S} x_s \\
		\text{Finite group} & Z
			& \xi \in \wh Z \cong Z & e(\xi \cdot x) \\
		\text{Fourier series} & \TT \cong [-\pi, \pi]  & n \in \ZZ
			& \exp(inx) \\
		\text{Discrete} & \ZZ/n\ZZ & \xi \in \ZZ/n\ZZ
			& e(\xi x / n) \\
	\end{array}
\]
It will turn out that in general
we can say something about many different domains $G$,
once we know what it means to integrate a measure.
This is the so-called \emph{Pontryagin duality};
and it is discussed as a follow-up bonus in \Cref{ch:pontryagin}.

\section{Parseval and friends}
Here is a fun section in which you get to learn a lot of big names quickly.
Basically, we can take each of the three results
from \Cref{prop:orthonormal},
translate it into the context of our Fourier analysis
(for which we have an orthonormal basis of the Hilbert space),
and get a big-name result.

\begin{corollary}
	[Parseval theorem]
	Let $f \colon Z \to \CC$, where $Z$ is a finite abelian group.
	Then \[ \sum_\xi |\wh f(\xi)|^2 = \frac{1}{|Z|} \sum_{x \in Z} |f(x)|^2. \]
	Similarly, if $f \colon [-\pi, \pi] \to \CC$ is square-integrable then
	its Fourier series satisfies
	\[ \sum_n |\wh f(n)|^2 = \frac{1}{2\pi} \int_{[-\pi, \pi]} |f(x)|^2 \; dx. \]
\end{corollary}
\begin{proof}
Recall that $\left< f,f\right>$ is equal to the
square sum of the coefficients.
\end{proof}

\begin{corollary}
	[Fourier inversion formula]
	Let $f \colon Z \to \CC$, where $Z$ is a finite abelian group.
	Then \[ \wh f(\xi) = \frac{1}{|Z|} \sum_{x \in Z} f(x) \ol{e_\xi(x)}. \]
	Similarly, if $f \colon [-\pi, \pi] \to \CC$ is square-integrable then
	its Fourier series is given by
	\[ \wh f(n) = \frac{1}{2\pi} \int_{[-\pi, \pi]} f(x) \exp(-inx) \; dx. \]
\end{corollary}
\begin{proof}
Recall that in an orthonormal basis $(e_\xi)_\xi$,
the coefficient of $e_\xi$ in $f$ is $\left< f, e_\xi\right>$.
\end{proof}
\begin{ques}
	What happens when $\xi = 0$ above?
\end{ques}

\begin{corollary}
	[Plancherel theorem]
	Let $f \colon Z \to \CC$, where $Z$ is a finite abelian group.
	Then \[ \left< f,g \right> = \sum_{\xi \in Z} \wh f(\xi) \ol{\wh g(\xi)}. \]
	Similarly, if $f \colon [-\pi, \pi] \to \CC$ is square-integrable then
	\[ \left< f,g \right> = \sum_n \wh f(n) \ol{\wh g(n)}. \]
\end{corollary}
\begin{ques}
	Prove this one in one line (like before).
\end{ques}

\section{Application: Basel problem}
One cute application about Fourier analysis on $L^2([-\pi, \pi])$
is that you can get some otherwise hard-to-compute sums,
as long as you are willing to use a little calculus.

Here is the classical one:
\begin{theorem}
	[Basel problem]
	We have
	\[ \sum_{n \ge 1} \frac{1}{n^2} = \frac{\pi^2}{6}. \]
\end{theorem}
The proof is to consider the identity function $f(x) = x$,
which is certainly square-integrable.
Then by Parseval, we have
\[
	\sum_{n \in \ZZ} \left\lvert \wh f(n) \right\rvert^2
	= \left< f,f\right>
	= \frac{1}{2\pi} \int_{[-\pi, \pi]} \left\lvert f(x) \right\rvert^2 \; dx.
\]
A calculus computation gives
\[  \frac{1}{2\pi} \int_{[-\pi, \pi]} x^2 \; dx = \frac{\pi^2}{3}. \]
On the other hand, we will now compute all Fourier coefficients.
We have already that
\[ \wh f(0) = \frac{1}{2\pi} \int_{[-\pi, \pi]} f(x) \; dx
	= \frac{1}{2\pi} \int_{[-\pi, \pi]} x \; dx = 0. \]
For $n \neq 0$, we have by definition
(or ``Fourier inversion formula'', if you want to use big words)
the formula
\begin{align*}
	\wh f(n) &= \left< f, \exp(inx) \right> \\
	&= \frac{1}{2\pi} \int_{[-\pi, \pi]} x \cdot \ol{\exp(inx)} \; dx \\
	&= \frac{1}{2\pi} \int_{[-\pi, \pi]} x \exp(-inx) \; dx.
\end{align*}
The anti-derivative is equal to
$\frac{1}{n^2} \exp(-inx) (1+inx)$,
which thus with some more calculation gives that
\[ \wh f(n) = \frac{(-1)^n}{n} i. \]
So
\[ \sum_n \left\lvert \wh f(n) \right\rvert^2
	= 2 \sum_{n \ge 1} \frac{1}{n^2} \]
implying the result.

\section{Application: Arrow's Impossibility Theorem}
As an application of binary Fourier analysis,
we now prove a form of
\href{https://en.wikipedia.org/wiki/Arrow's_impossibility_theorem}{Arrow's theorem}.

Consider $n$ voters voting among $3$ candidates $A$, $B$, $C$.
Each voter specifies a tuple $v_i = (x_i, y_i, z_i) \in \{\pm1\}^3$ as follows:
\begin{itemize}
	\ii $x_i = 1$ if person $i$ ranks $A$ ahead of $B$, and $x_i = -1$ otherwise.
	\ii $y_i = 1$ if person $i$ ranks $B$ ahead of $C$, and $y_i = -1$ otherwise.
	\ii $z_i = 1$ if person $i$ ranks $C$ ahead of $A$, and $z_i = -1$ otherwise.
\end{itemize}
Tacitly, we only consider $3! = 6$ possibilities for $v_i$:
we forbid ``paradoxical'' votes of the form $x_i = y_i = z_i$
by assuming that people's votes are consistent
(meaning the preferences are transitive).


For brevity, let $x_\bullet = (x_1, \dots, x_n)$
and define $y_\bullet$ and $z_\bullet$ similarly.
Then, we can consider a voting mechanism
\begin{align*}
	f \colon \{\pm1\}^n &\to \{\pm1\} \\
	g \colon \{\pm1\}^n &\to \{\pm1\} \\
	h \colon \{\pm1\}^n &\to \{\pm1\}
\end{align*}
such that
\begin{itemize}
	\ii $f(x_\bullet)$ is the global preference of $A$ vs.\ $B$,
	\ii $g(y_\bullet)$ is the global preference of $B$ vs.\ $C$,
	\ii and $h(z_\bullet)$ is the global preference of $C$ vs.\ $A$.
\end{itemize}
We'd like to avoid situations where the global preference
$(f(x_\bullet), g(y_\bullet), h(z_\bullet))$ is itself paradoxical.

Let $\EE f$ denote the average value of $f$ across all $2^n$ inputs.
Define $\EE g$ and $\EE h$ similarly.
We'll add an assumption that $\EE f = \EE g = \EE h = 0$,
which provides symmetry
(and e.g.\ excludes the possibility that $f$, $g$, $h$
are constant functions which ignore voter input).
With that we will prove the following result:
\begin{theorem}
	[Arrow Impossibility Theorem]
	Assume that $(f,g,h)$ always avoids paradoxical outcomes,
	and assume $\EE f = \EE g = \EE h = 0$.
	Then $(f,g,h)$ is either a dictatorship or anti-dictatorship:
	there exists a ``dictator'' $k$ such that
	\[ f(x_\bullet) = \pm x_k, \qquad g(y_\bullet) = \pm y_k,
		\qquad h(z_\bullet) = \pm z_k \]
	where all three signs coincide.
\end{theorem}
Unlike the usual Arrow theorem, we do \emph{not} assume
that $f(+1, \dots, +1) = +1$ (hence possibility of anti-dictatorship).

\begin{proof}
	Suppose the voters each randomly select one of the $3!=6$
	possible consistent votes.
	In \Cref{prob:arrow_lemma} it is shown
	that the exact probability of a paradoxical outcome
	for any functions $f$, $g$, $h$ is given exactly by
	\[ \frac14 + \frac14 \sum_{S \subseteq \{1, \dots, n\}}
		\left( -\frac13 \right)^{\left\lvert S \right\rvert}
		\left( \wh f(S) \wh g(S) + \wh g(S) \wh h(S) + \wh h(S) \wh f(S) \right).
		\]
	Assume that this probability (of a paradoxical outcome) equals $0$.
	Then, we derive
	\[ 1 = \sum_{S \subseteq \{1, \dots, n\}}
		-\left( -\frac13 \right)^{\left\lvert S \right\rvert}
		\left( \wh f(S) \wh g(S) + \wh g(S) \wh h(S) + \wh h(S) \wh f(S) \right). \]
	But now we can just use weak inequalities.
	We have $\wh f(\varnothing) = \EE f = 0$ and similarly for $\wh g$ and $\wh h$,
	so we restrict attention to $|S| \ge 1$.
	We then combine the famous inequality $|ab+bc+ca| \le a^2+b^2+c^2$
	(which is true across all real numbers) to deduce that
	\begin{align*}
		1 &= \sum_{S \subseteq \{1, \dots, n\}}
		-\left( -\frac13 \right)^{\left\lvert S \right\rvert}
		\left( \wh f(S) \wh g(S) + \wh g(S) \wh h(S) + \wh h(S) \wh f(S) \right) \\
		&\le \sum_{S \subseteq \{1, \dots, n\}}
		\left( \frac13 \right)^{\left\lvert S \right\rvert}
		\left( \wh f(S)^2 + \wh g(S)^2 + \wh h(S)^2 \right) \\
		&\le \sum_{S \subseteq \{1, \dots, n\}} \left( \frac13 \right)^1
		\left( \wh f(S)^2 + \wh g(S)^2 + \wh h(S)^2 \right) \\
		&= \frac13 (1+1+1) = 1.
	\end{align*}
	with the last step by Parseval.
	So all inequalities must be sharp, and in particular $\wh f$, $\wh g$, $\wh h$
	are supported on one-element sets, i.e.\ they are linear in inputs.
	As $f$, $g$, $h$ are $\pm 1$ valued, each $f$, $g$, $h$ is itself
	either a dictator or anti-dictator function.
	Since $(f,g,h)$ is always consistent, this implies the final result.
\end{proof}


\section{\problemhead}

\begin{problem}
	[For calculus fans]
	Prove that
	\[ \sum_{n \ge 1} \frac{1}{n^4} = \frac{\pi^4}{90}. \]
	\begin{hint}
		Use Parseval again, but this time on $f(x) = x^2$.
	\end{hint}
\end{problem}

\begin{problem}
	\onechili
	\label{prob:arrow_lemma}
	Let $f,g,h \colon \{\pm1\}^n \to \{\pm1\}$
	be any three functions.
	For each $i$, we randomly select $(x_i, y_i, z_i) \in \{\pm1\}^3$
	subject to the constraint that not all are equal
	(hence, choosing among $2^3-2=6$ possibilities).
	Prove that the probability that
	\[ f(x_1, \dots, x_n) = g(y_1, \dots, y_n) = h(z_1, \dots, z_n) \]
	is given by the formula
	\[ \frac14 + \frac14 \sum_{S \subseteq \{1, \dots, n\}}
		\left( -\frac13 \right)^{\left\lvert S \right\rvert}
		\left( \wh f(S) \wh g(S) + \wh g(S) \wh h(S) + \wh h(S) \wh f(S) \right)
		\]
	\begin{hint}
		Define the Boolean function $D \colon \{\pm 1\}^3 \to \RR$ by
		$D(a,b,c) = ab+bc+ca$.
		Write out the value of $D(a,b,c)$ for each $(a,b,c)$.
		Then, evaluate its expected value.
	\end{hint}
	\begin{sol}
	Define the Boolean function $D \colon \{\pm 1\}^3 \to \RR$ by
	\[ D(a,b,c) = ab + bc + ca
		= \begin{cases}
			3 & a,b,c \text{ all equal} \\
			-1 & a,b,c \text{ not all equal}.
		\end{cases}.
	\]
	Thus paradoxical outcomes arise when
	$D(f(x_\bullet), g(y_\bullet), h(z_\bullet)) = 3$.
	Now, we compute that for randomly selected
	$x_\bullet$, $y_\bullet$, $z_\bullet$ that
	\begin{align*}
		\EE D(f(x_\bullet), g(y_\bullet), h(z_\bullet))
		&= \EE \sum_S \sum_T
			\left( \wh f(S) \wh g(T) + \wh g(S) \wh h(T) + \wh h(S) \wh f(T) \right)
			\left( \chi_S(x_\bullet)\chi_T(y_\bullet) \right) \\
		&= \sum_S \sum_T
			\left( \wh f(S) \wh g(T) + \wh g(S) \wh h(T) + \wh h(S) \wh f(T) \right)
			\EE\left( \chi_S(x_\bullet)\chi_T(y_\bullet) \right).
	\end{align*}
	Now we observe that:
	\begin{itemize}
		\ii If $S \neq T$, then $\EE \chi_S(x_\bullet) \chi_T(y_\bullet) = 0$,
		since if say $s \in S$, $s \notin T$ then $x_s$ affects
		the parity of the product with 50\% either way,
		and is independent of any other variables in the product.
		\ii On the other hand, suppose $S = T$.
		Then
		\[ \chi_S(x_\bullet) \chi_T(y_\bullet)
			= \prod_{s \in S} x_sy_s. \]
		Note that $x_sy_s$ is equal to $1$ with probability $\frac13$
		and $-1$ with probability $\frac23$
		(since $(x_s, y_s, z_s)$ is uniform from $3!=6$ choices,
		which we can enumerate).
		From this an inductive calculation on $|S|$ gives that
		\[
			\prod_{s \in S} x_sy_s
			=
			\begin{cases}
				+1 & \text{ with probability } \half(1+(-1/3)^{|S|}) \\
				-1 & \text{ with probability } \half(1-(-1/3)^{|S|}).
			\end{cases}
		\]
		Thus
		\[ \EE \left( \prod_{s \in S} x_sy_s \right) = \left( -\frac13 \right)^{|S|}.  \]
	\end{itemize}
	Piecing this altogether, we now have that
	\[
		\EE D(f(x_\bullet), g(y_\bullet), h(z_\bullet))
		=
		\sum_S \left( \wh f(S) \wh g(S) + \wh g(S) \wh h(S) + \wh h(S) \wh f(S) \right)
		\left( -\frac13 \right)^{|S|}.
	\]
	Then, we obtain that
	\begin{align*}
		&\EE \frac14 \left( 1 + D(f(x_\bullet), g(y_\bullet), h(z_\bullet)) \right) \\
		=& \frac14 + \frac14\sum_S
		\left( \wh f(S) \wh g(S) + \wh g(S) \wh h(S) + \wh h(S) \wh f(S) \right)
		\left( -\frac13 \right)^{|S|}.
	\end{align*}
	Comparing this with the definition of $D$ gives the desired result.
	\end{sol}
\end{problem}
