# Tuesday July 7th

Definition
: A *character* of an abelian group is a function $\gamma: G\to S^1$ such that $\gamma(a+b) = \gamma(a)\gamma(b)$.

Example
: For $G = \ZZ/n\ZZ$, for each $0\leq k \leq n-1$ there is a character $\gamma(x) = e(xk/n)$

We can always multiply two characters together pointwise to get a new character.

Definition
: The set of characters of $G$ is denoted $G\dual$, which is a group.

For any two groups $G, H$ with characters $\gamma_1, \gamma_2$, we can form the new character $\gamma_1 \tensor \gamma_2(a_1, a_2) = \gamma_1(a_1)\gamma_2(a_2)$.
The map $(\gamma_1, \gamma_2) \mapsto \gamma_1\tensor \gamma_2$ yields an isomorphism $G_1\dual \oplus G_2\dual \cong \qty{G_1\oplus G_2}\dual$.

Thus we can extend characters from cyclic groups to get characters on all finite abelian groups.

Proposition
: We have formulae
\begin{align*}
{1\over \abs G} \sum_{a\in G} \gamma(a) = \one{\gamma = \iota} \\
{1\over \abs G} \sum_{\gamma \in G\dual} \gamma(a) = \one{1 = 0} \\
.\end{align*}

Definition
: For $f:G\to \CC$ and $\gamma\in G\dual$, the Fourier coefficient of $f$ at $\gamma$ is
\begin{align*}
\hat f(\gamma) \definedas {1\over \abs G} \sum_{a\in G} f(a) \bar{\gamma(a)}
.\end{align*}

Theorem
:   Let $f, g: G\to \CC$ be functions on a finite abelian group $G$, then
\begin{align*}
f(a) = \sum_{\gamma \in G\dual} \hat f(\gamma) \gamma(a) \qtext{Inversion}\\
{1\over \abs G} \sum_{a\in G} f(a) \bar{g(a)} = \sum_{\gamma \in G\dual} \hat f(\gamma) \bar{\hat g(\gamma)}  \qtext{Parseval's} \\
{1\over \abs G} \sum_{a\in G} \abs{f(a)}^2 = \sum_{\gamma\in G\dual} \abs{\hat f(\gamma)}^2 \qtext{Plancherel} 
.\end{align*}

> Characters form a basis of functions, convenient because they respect the arithmetic structure, useful for counting solutions to equations using analytic functions.

Partition regularity problem:
Partition $\NN$ into $\disjoint_{i=1}^r C_i$ (colors), can we solve $x+y=z$ with $x,y,z\in C_j$ for some fixed $j$?

Hindman:
Can $xy=p$ with $x+y=s$ be solved with $x,y,p,s\in C_j$?
Open, thought to be hard.

Given $A\subseteq \FF_p$, can we find $xy, x+y\in A$? 
Yes if $\abs{A} \geq 100\sqrt{p}$.

Let $S = \theset{x^2 \suchthat x\in \FF_p}$ and define its indicator function $\one_S(y)$, then taking its Fourier transform yields
\begin{align*}
\hat \one_S(k) = {1\over p} \sum_{y\in \FF_p} \one_S(y) e(-ky/p)
= {1\over p} \sum_{s\in S} e(-ks / p)
.\end{align*}

The nonzero squares are the roots of $x^{p-1\over 2} - 1$, of which there are $p-1\over 2$.
Adding in $x=0$ yields $\abs{S} = {p+1\over 2}$.
Thus $\hat \ind_S(0) = {\abs S \over p} = {p+1\over 2p}$, and
\begin{align*}
\abs{\hat \one_S(r)}^2 
&= {1\over p} \sum_{s_1, s_2} e\qty{-r(s_1 - s_2) \over p}  \\
&= {1\over p} \sum_{u, v} e\qty{-r(u^2 - v^2) \over p} \\ 
&= {1\over p} \sum_{u, v} e\qty{-r(u+v)(u-v) \over p} \quad s = u+v,~ d = u-v \\
&= {1\over p^2} \sum_{s, d} e\qty{-rsd \over p}  \\
&=
\begin{cases}
1 & d = 0 \text{ or } s = 0 \\
0 & \text{else}
\end{cases} \\
&= {1\over p^2} \sum_{s} 1 = {1\over p}
.\end{align*}

Note that we've overcounted since each square has two square roots, so we need to divide this by 4.
See notes for more details.

We now want to prove that if $A\subseteq \FF_p$ is sufficiently large, then $A$ contains a sum and a product.

If $x+y=a$ and $xy=b$, then $f(t) = t^2 - at + b = (t-x)(t-y)$ since the constant coefficient is the product of the roots and the $t$ coefficient is the sum of the roots.
Thus we check if $f(t)$ with $a, b\in A$ factors, which happens exactly when the discriminant $a^2 - 4b$ is a square.
So we now count $\sum_{a, b} \one_S(a^2 - 4b)$ where $S$ is still the set of squares.

We now attempt to use the orthogonality relations to detect solutions, so we apply Fourier inversion:
\begin{align*}
f(r) = \sum_k \hat f(k) e(kr/p)
.\end{align*}

Thus we obtain
\begin{align*}
\sum_{a, b\in A} \sum_k \one_S(k) e\qty{k(a^2-4b) \over p}
.\end{align*}

We split off into two cases, whether or not $k=0$.
For $k=0$, we saw that the Fourier coefficient was ${p+1} \over 2p$, and the total contribution is ${p+1 \over 2p} \abs{A}^2$.

For $k\neq 0$, we have an estimate
\begin{align*}
\sim \sum_{k\neq 0} \abs{ \hat \one_S(k)} \sum_{a, b\in A} e\qty{k(a^2-4ab) \over p} \\
\sim \sum_{k\neq 0} {1\over \sqrt{p}} \sum_{a, b\in A} e\qty{k(a^2-4ab) \over p} \\
.\end{align*}

To estimate the remaining double sum, we use Cauchy-Schwarz.
This can be split up as 
\begin{align*}
\abs{ \sum_{a\in A} \sum_{b\in B} e(ka^2/p) e^{-bk/p} } 
\leq 
\abs{\sum_{a\in A} e\qty{ka^2 \over p} } \abs{ \sum_{b\in A} e\qty{-bk\over p} } \\ 
=  \abs{\hat f_A(k)}   \abs{ \hat{\one_A}(k) }
.\end{align*}

where $f_A(r) = \one_P$ where $P = \theset{r=a^2 \suchthat a\in A}$


Thus
\begin{align*}
{1\over \sqrt p} \sum_{k\neq 0} \abs{\hat f_A(k)} \abs{\hat \one_A(k)} 
\leq {1\over \sqrt p} \qty{\sum_k \abs{\hat f_A(k) }^2 }^{1\over 2}  \qty{\sum_k \abs{\hat \one_A(k)}^2 }^{1\over 2}
\qtext{by Plancherel}
.\end{align*}

The first term is around $2\abs{A} \over p$, and the second term is about ${p+1 \over 2p} \abs{A}^2$.