\documentclass[psamsfonts]{amsart}
\usepackage{amssymb,amsfonts}
\usepackage[all,arc]{xy}
\usepackage{enumerate}
\usepackage{mathrsfs}

%theoremstyle{plain} --- default
\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{quest}[thm]{Question}

\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\newtheorem{defns}[thm]{Definitions}
\newtheorem{con}[thm]{Construction}
\newtheorem{exmp}[thm]{Example}
\newtheorem{exmps}[thm]{Examples}
\newtheorem{notn}[thm]{Notation}
\newtheorem{notns}[thm]{Notations}
\newtheorem{addm}[thm]{Addendum}
\newtheorem{exer}[thm]{Exercise}

\theoremstyle{remark}
\newtheorem{rem}[thm]{Remark}
\newtheorem{rems}[thm]{Remarks}
\newtheorem{fact}[thm]{Fact}
\newtheorem{claim}[thm]{Claim}
\newtheorem{sch}[thm]{Scholium}

\makeatletter
\let\c@equation\c@thm
\makeatother
\numberwithin{equation}{section}

\bibliographystyle{plain}

\title{Quasirandomness and Gowers' Theorem}

\author{Qian Zhang}

\begin{document}

\maketitle
\begin{center}
August 16, 2007
\end{center}

\begin{abstract}
``Quasirandomness'' will be described and the Quasirandomness
Theorem will be used to prove Gowers' Theorem. This article assumes some familiarity with linear algebra and elementary probability theory.
\end{abstract}

\tableofcontents{}

\section{Lindsey's Lemma: An Illustration of quasirandomness}

\begin{defn}
$A$ is a Hadamard matrix of size $n$ if it is an $n \times n$ matrix with
each entry (a$_{\text{ij}}$) either +1 or -1. Moreover, its rows
are orthogonal, i.e. any two distinct row vectors have inner product 0.
\end{defn}

\begin{rem} \label{col_orthog}
If $A$ is an $n\times n$ matrix with orthogonal rows, then $AA^{T}=nI$,
so $(\frac{1}{\sqrt{n}}A)(\frac{1}{\sqrt{n}}A)^{T}=I\Leftrightarrow(\frac{1}{\sqrt{n}}A)^{T}=(\frac{1}{\sqrt{n}}A)^{-1}\Leftrightarrow A^{T}A=nI$,
so the columns of $A$ are also orthogonal, and $(\frac{1}{\sqrt{n}}A)^T(\frac{1}{\sqrt{n}}A)=I$.
\end{rem}

\begin{notn}
$\vec{1}$ denotes the column vector that has $1$ as every component.
\end{notn}

\begin{rem} \label{sum_matrix}
For any matrix $A$, $\vec{1}^{T}A\vec{1}$ is the sum of the entries of $A$.
\footnote{$\vec{1}$ selects columns of $A$ and sums their corresponding components.
$\vec{1}^{T}$ selects rows of A, selecting and adding together certain
component sums. Replacing the ith component of $\vec{1}$ with a 0
would deselect the ith column of $A$ and replacing the ith component
of $\vec{1}^{T}$ with 0 would deselect the ith row of $A$.}
\end{rem}

\begin{fact}\label{tranpose_rule}
$\left\Vert\vec{x}\right\Vert^2 = \vec{x}^T\vec{x}. \mbox{ Hence}, \left\Vert A\vec{x}\right\Vert^2 = (A\vec{x})^T(A\vec{x}) = \vec{x}^TA^TA\vec{x}.$
\end{fact}

\begin{defn} \label{incidence_vec}Given a matrix $A$ and a submatrix $T$ of $A$, let $X$ be the
set of rows of $T$ and let $Y$ be the set of columns of $T$. $\vec{x}$ is an \textbf{incidence vector}
of $X$ if for all components $x_i$ of $\vec{x}$, $x_{i}=1$ if the ith
row vector of $A$ is a row vector of $T$ and $x_{i}=0$ otherwise.
$\vec{y}$ is an incidence vector of $Y$ if for all components $y_i$ of $\vec{y}$,
$y_{i}=1$ if the ith column vector of $A$ is a column vector of $T$ and $y_{i}=0$ otherwise.
\end{defn}

\begin{lem}
(Lindsey's Lemma) If A = (a$_{\text{ij}}$) is an n$\times$n Hadamard matrix
and T is a k$\times$l-submatrix, then $|\sum_{(i,j)\in T}a_{ij}|\leq\sqrt{kln}$
\end{lem}

\begin{proof}
Let $X$ be the set of rows of $T$ and let $Y$ be the set of columns
of $T$. Note that $|X|=k$ and $|Y|=l$. Let $\overrightarrow{x}$
be the incidence vector of $X$ and let $\vec{y}$ be the incidence
vector of $Y$.

The sum of all entries of $T$ is $\sum_{(i,j)\in T}a_{ij}$, which is $\vec{x}^{T}A\vec{y}$ (recall \ref{sum_matrix}),
so $\left|\vec{x}^{T}A\vec{y}\right|=\left|\sum_{(i,j)\in T}a_{ij}\right|$.
By the Cauchy-Schwarz inequality, $\left|\vec{x}^{T}A\vec{y}\right|\leq\left\Vert \vec{x}\right\Vert \left\Vert A\vec{y}\right\Vert $.
\begin{center}
By \ref{col_orthog} and \ref{tranpose_rule}, $\left\Vert \frac{1}{\sqrt{n}}A\vec{y}\right\Vert = \vec{y}^{T}(\frac{1}{\sqrt{n}}A)^{T}(\frac{1}{\sqrt{n}}A)\vec{y}=\vec{y}^{T}\vec{y}=\left\Vert \vec{y}\right\Vert$\\
$\left\Vert A\vec{y}\right\Vert = \left\Vert \sqrt{n}(\frac{1}{\sqrt{n}}A\vec{y})\right\Vert =\sqrt{n}\left\Vert \frac{1}{\sqrt{n}}A\vec{y}\right\Vert =\sqrt{n}\left\Vert \vec{y}\right\Vert$
\end{center}
Substituting for $\left\Vert A\vec{y}\right\Vert$ in the Cauchy-Schwarz inequality and noting that $\left\Vert \vec{x}\right\Vert =\sqrt{k}$ and
$\left\Vert \vec{y}\right\Vert =\sqrt{l}$, $\left|\vec{x}^{T}A\vec{y}\right|\leq\left\Vert \vec{x}\right\Vert (\sqrt{n}\left\Vert \vec{y}\right\Vert )=\sqrt{kln}$.
\end{proof}

\subsection{How Lindsey's Lemma is a Quasirandomness result}

The following corollary illustrates how Lindsey's Lemma is a {}``quasirandomness''
result. It says that if T is a sufficiently large submatrix, then
the number of +1's and the number of -1's in T are about equal.

\begin{cor}\label{Lind Cor}
Let T be a k$\times$l submatrix of an n$\times$n Hadamard matrix $A$. If $kl\geq100n$,
then the number of +1's and the number of -1's each occupy at least
45\% and at most 55\% of the cells of T.
\end{cor}

\begin{proof}
Let x be the number of +1's in $T$ and let y be the number of -1's
in $T$. Suppose $kl\geq100n$. We want to show that $(0.45)kl\leq x\leq(0.55)kl$
and $(0.45)kl\leq y\leq(0.55)kl$.

By Lindsey's Lemma, $|\sum_{(i,j)\in T}a_{ij}|\leq\sqrt{kln}$.
Note that $x-y=\sum_{(i,j)\in T}a_{ij}$, so $\left|\sum_{(i,j)\in T}a_{ij}\right|=\left|x-y\right|\leq\sqrt{kln}$.
We know that $k>0$ and $l>0$, so $kl>0$.
\[\frac{\left|x-y\right|}{kl}\leq\sqrt{\frac{kln}{(kl)^{2}}}=\sqrt{\frac{n}{kl}}\leq\sqrt{\frac{n}{100n}}=\frac{1}{10}\]
where the last inequality holds because $kl\geq100n$. Since all entries
of T are either +1 or -1, the sum of the number of +1's and the number
of -1's is the number of entries in T, so $x+y=kl$, hence $y=kl-x$.
Substituting in for y,

\begin{eqnarray*}
\frac{|x-(kl-x)|}{kl} & \leq& \frac{1}{10} \\
\frac{-kl}{10} &\leq & 2x-kl \leq \frac{kl}{10} \\
\frac{9 kl}{20} &\leq& x \leq \frac{11kl}{20}\\
\frac{9 kl}{20} &\leq& kl-x \leq \frac{11kl}{20}\\
\frac{9 kl}{20} &\leq& y \leq \frac{11kl}{20}   \end{eqnarray*}
\end{proof}

\begin{defn}
A \textbf{random matrix} is a matrix whose entries are randomly assigned
values. Entries' assignments are independent of each other.
\end{defn}

To see how Corollary \ref{Lind Cor} shows Hadamard matrix $A$ to be like a random matrix but
not a random matrix, consider a random $n \times n$ matrix $B$ whose entries
are assigned either +1 or -1 with probability $p$ and $1-p$ respectively. Consider $U$, a $k \times l$ submatrix of
$B$. $U$ has $kl$ entries, and $w$, the number of entries of the
$kl$ entries that are +1, would be a random variable.

Considering $U$'s entries' assignments independent trials that result in either
success or failure and calling the occurrence of +1 a {}``success,''
$P(w=s)$ is the probability of $s$ successes in $kl$ independent
trials, which is the product of the probability of a particular sequence
of $s$ successes, $p^{s}(1-p)^{kl-s}$, and the number of such sequences,
$\left({kl\atop s}\right)$, so $P(w=s)=\left({kl\atop s}\right)p^{s}(1-p)^{kl-s}$.
In other words, $w$ has a binomial probability distribution. Hence,
$w$ has expected value $klp$. If each entry has equal probability
of being assigned +1 or -1, $p=\frac{1}{2}$ so $\mathrm{E}(w)=kl(\frac{1}{2})$.
Note that $w$ can take values far from $\mathrm{E}(w)$, since $P(w=s)$
shows $w$ has nonzero probability of being any integer $s$ where
$0\leq s\leq kl$.

Now consider $n \times n$ Hadamard matrix $A$, its $k \times l$ submatrix $T$,
and $x$, the number of +1's in $T$. Corollary \ref{Lind Cor} shows that $x$
must take values close to $\mathrm{E}(w)$.
\footnote{In this paragraph, +1 and -1 are assumed to occur in each cell with equal probability, so that $\mathrm{E}(w)$ is $kl(\frac{1}{2}).$}
More precisely, if $kl\geq100n$, $x$ must
be within 5\% of $\mathrm{E}(w)$. $x$ is like random $w$ in that we can expect $x$ to take values close to the expected value of $w$.
However, $x$ is not random because it $\mathit{must}$ be within
5\% of $\mathrm{E}(w)$, while random $w$ can take values farther from $\mathrm{E}(w)$,
any value ranging from $0$ to $kl$.
\footnote{If $kl\geq100n$, $x$ must be within 5\% of $\mathrm{E}(w)$.
$100$ was used in the hypothesis of \ref{Lind Cor} for the sake of concreteness.
Any arbitrary constant $c$ could have replaced $100$, so that $kl\geq cn$. So long as $c>1$,
$x$ is more limited than $w$ in the values it can take.}

The above argument is symmetrical: It can be used to compare $y$,
the number of -1's in $T$, and $z$, the number of -1's in $U$.
In deriving $P(w=s)$, we called the occurrence of +1 a {}``success.''
We could have arbitrarily called the occurrence of -1 a {}``success.''
Then $P(z=s)=\left({kl\atop s}\right)p^{s}(1-p)$, $\mathrm{E}(z)=kl(\frac{1}{2})$
if $p=\frac{1}{2}$, and $y$ would be like random $z$, but not random, in the
same way that $x$ would be like random $w$, but not random.

In short, $n\times n$ Hadamard matrix $A$ is "quasirandom" because it is like a random matrix $B$, but not itself a random matrix. Characteristics ($x$ and $y$) of $k \times l$ $T$,
a sufficiently large \footnote{$kl>n$} submatrix of $A$, are similar to characteristics ($w$ and $z$) of $k \times l$ $U$, a submatrix of
$B$. $A$ is like, but not, a random matrix $B$ because submatrices
of $A$ have properties similar to, but not the same as, submatrices
of $B$.

\section{The Quasirandomness Theorem}

\begin{defn}
A $\mathbf{graph}$ $G=(V,E)$ is a pair of sets. Elements of $V$
are called vertices and elements of $E$ are called edges. $E$ consists
of distinct, unordered pairs of vertices such that no vertex forms an edge with
itself: $\forall v\in V, E\subset V\times V\setminus\{v,v\}$. $v_{1},v_{2}\in V$
are $\mathbf{adjacent}$ when $\{v_{1},v_{2}\}\in E$, denoted $v_{1}\sim v_{2}$.
The \textbf{degree} of a vertex is the number of vertices with which
it forms an edge.
\end{defn}

\begin{rem}
Vertices can be visualized as points and an edge can be visualized
as a line segment connecting two points.
\end{rem}

\begin{defn}\label{density}
Consider a graph $G=(V,E)$ and let $n$ denote $G$'s maximum number
of possible edges, i.e. the number of edges there would be if every
vertex were connected with every other vertex, so that $n=\left(\begin{array}{c}
\left|V\right|\\
2\end{array}\right)$. $\left|E\right|$ is the number of edges in the graph. The $\mathbf{density}$
$p$ of $G$ is $\frac{\left|E\right|}{n}$.
\end{defn}

\begin{defn}
A \textbf{bipartite graph} $\Gamma(L,R,E)$ is a graph consisting
of two sets of vertices $L$ and $R$ such that an edge can only exist
between a vertex in $L$ and a vertex in $R$. Call $L$ the "left
set" and $R$ the "right set."
\end{defn}

\begin{notn}
Given two sets of vertices $V_{1}$ and $V_{2}$, $E(V_{1},V_{2})$
denotes the set of edges between vertices in $V_{1}$ and vertices
in $V_{2}$. $\left|E(V_{1},V_{2})\right|$ denotes the number of
elements in $E(V_{1},V_{2})$.
\end{notn}

\begin{defn}
Consider a bipartite graph $\Gamma(L,R,E)$ such that $\left\vert L\right\vert=k$ and $\left\vert R\right\vert=l$. Label the
vertices in L with distinct consecutive natural numbers including 1 and do the same for vertices in R. An \textbf{adjacency matrix} $(a_{ij})$ of $\Gamma$ is a $k \times l$ matrix such that

\[a_{ij}=\left\{ \begin{array}{cc}
1 & \mbox{if } i\sim j, \mbox{where } i\in L \mbox{ and } j\in R\\
0 & \mbox{otherwise}\end{array}\right.\]
\end{defn}

\begin{rem}\label{possemidef}
Let $A$ be a k x l adjacency matrix. $(A^{T}A)^{T}=A^{T}(A^{T})^{T}=A^{T}A$.
Since $A^{T}A$ is symmetric, it has $l$ real eigenvalues, denoted
$\lambda_{1},\,...,\,\lambda_{l}$ in decreasing order. $A^{T}A$
is \textbf{positive semidefinite} because $\forall x\in\mathbb{R}^{l},x^{T}A^{T}Ax=\left\Vert Ax\right\Vert ^{2}\geq0$.
Since $A^{T}A$ is positive semidefinite, its eigenvalues are nonnegative.
\end{rem}

\begin{defn}
A \textbf{biregular bipartite graph} $\Gamma(L,R,E)$ is a bipartite
graph where every vertex in $L$ has the same degree $s_{r}$ and
every vertex in $R$ has the same degree $s_{c}$.
\end{defn}

\begin{rem}\label{lsr=ksc}
$\left|E\right|=\left|L\right|s_{r}=\left|R\right|s_{c}$.
\end{rem}

\begin{fact}
(Rayleigh Principle)\label{RayP} Let $n\times n$ symmetric matrix $A$ have eigenvalues $\lambda_1,...,\lambda_n$ in decreasing order. Define the Rayleigh quotient $R_{A}(x)=\frac{\vec{x}^{T}A\vec{x}}{\vec{x}^T\vec{x}}$. Then $\lambda_{1}=\underset{\vec{x}\in\mathbb{R}^{n},\vec{x}\neq\vec{0}}{max}R_{A}(x)$.
\end{fact}

\begin{lem}\label{largest eigenvalue}
Let $\Gamma(L,R,E)$ be a biregular bipartite graph with $\left|L\right|=k$ and $\left|R\right|=l$.
Let each vertex in $L$ have degree $s_{r}$ and let each vertex in $R$ have degree $s_{c}$.
Let A be the $k \times l$ adjacency matrix of $\Gamma$, and let $\lambda_{1}$ be the largest eigenvalue of $A^{T}A$.
Then $\lambda_{1}=s_{r}s_{c}$.
\end{lem}

\begin{proof}
Let $\vec{r_{1}},...,\vec{r_{k}}$ be the row vectors of $A$. Recall that $A$ has only $1$ or $0$ for entries and that each
$\vec{r_{i}}$ contains $s_r$ 1's, so dotting $\vec{r_{i}}$ with some vector adds together $s_r$ components of that vector.
\[\frac{\left\Vert A\vec{1}_{l\times1}\right\Vert^2}{\left\Vert \vec{1}_{l\times1}\right\Vert^2} =
\frac{\left\Vert (\vec{r}_{1}\cdot\vec{1}_{l\times1},...,\vec{r}_{k}\cdot\vec{1}_{l\times1})\right\Vert^2}{l}=
\frac{\left\Vert (s_r,...,s_r)_{1\times k}\right\Vert^2}{l} = \frac{ks_r^2}{l} = (\frac{ks_r}{l})s_r=s_cs_r\]
where the last equality follows from \ref{lsr=ksc}.

We have that $\frac{\left\Vert A\vec{x}\right\Vert^2}{\left\Vert \vec{x}\right\Vert^2}=s_cs_r$ when $\vec{x}=\vec{1}_{l\times l}$.
If we could show that $\forall\vec{x}\in\mathbb{R}^l,\frac{\left\Vert A\vec{x}\right\Vert^2}{\left\Vert \vec{x}\right\Vert^2}\leq s_cs_r$,
then we would have that $\frac{\left\Vert A\vec{x}\right\Vert^2}{\left\Vert \vec{x}\right\Vert^2}$ reaches its upper bound $s_cs_r$,
so its max must be $s_cs_r$, and by \ref{RayP} and \ref{tranpose_rule},

\begin{equation*}\lambda_{1}= \underset{\vec{x}\in\mathbb{R}^{l},\vec{x}\neq\vec{0}}{max}\frac{\vec{x}^{T}A^{T}A\vec{x}}{\vec{x}^T\vec{x}}
=\underset{\vec{x}\in\mathbb{R}^{l},\vec{x}\neq\vec{0}}{max}\frac{\left\Vert A\vec{x}\right\Vert^2}{\left\Vert \vec{x}\right\Vert^2}=s_cs_r
\end{equation*}

\noindent It remains to show that $\forall\vec{x}\in\mathbb{R}^l,\frac{\left\Vert A\vec{x}\right\Vert^2}{\left\Vert \vec{x}\right\Vert^2}\leq s_cs_r$.

Let $x_1,...x_l$ denote the components of $\vec{x}$. $A\vec{x}=(\vec{r}_1\cdot\vec{x},...,\vec{r}_k\cdot\vec{x})^T$, so
\begin{equation}
\label{normAx}\left\Vert A\vec{x}\right\Vert^2=\underset{i=1}{\overset{k}{\sum}}(\vec{r}_i\cdot\vec{x})^2
\end{equation}

$\vec{r}_i\cdot\vec{x}$ is the sum of $s_r$ components of $\vec{x}$. Let $x_{i1},...,x_{is_r}$ be the $s_r$ components of $\vec{x}$ that $\vec{r}_i$ selects to sum. Then $\vec{r}_i\cdot\vec{x}=\underset{j=1}{\overset{s_r}{\sum}}x_{ij}$.

\[\vec{r}_i\cdot\vec{x}=\underset{j=1}{\overset{s_r}{\sum}}x_{ij}
=(x_{i1},...,x_{is_r})\cdot\vec{1}_{s_r\times1}\leq\left\Vert \vec{1}_{s_r\times1}\right\Vert\left\Vert (x_{i1},...,x_{is_r})\right\Vert
=\sqrt{s_r}\sqrt{\underset{j=1}{\overset{s_r}{\sum}}(x_{ij})^2}\]

\noindent where the inequality follows from the Cauchy-Schwarz Inequality, so we have that
$(\vec{r}_i\cdot\vec{x})^2\leq s_r\underset{j=1}{\overset{s_r}{\sum}}(x_{ij})^2$. Substituting into \ref{normAx},
\begin{equation}
\label{bdNormAx}\left\Vert A\vec{x}\right\Vert^2\leq s_r\underset{i=1}{\overset{k}{\sum}}\underset{j=1}{\overset{s_r}{\sum}}(x_{ij})^2
\end{equation}

Observe that the first summation cycles through all the row vectors and, for each row vector $\vec{r}_i$,
the second summation cycles through the components of $\vec{x}$ chosen by $\vec{r_i}$. Recall that $A$ has $s_c$ 1's in every column,
so in multiplying $A$ and $\vec{x}$, every component of $\vec{x}$ is selected by exactly $s_c$ row vectors. Hence,

\[\underset{i=1}{\overset{k}{\sum}}\underset{j=1}{\overset{s_r}{\sum}}(x_{ij})^2
=s_c\underset{i=1}{\overset{l}{\sum}}(x_i)^2
=s_c\left\Vert\vec{x}\right\Vert^2\]

Substituting into \ref{bdNormAx}, $\left\Vert A\vec{x}\right\Vert^2\leq s_rs_c\left\Vert \vec{x}\right\Vert^2$, so $\forall\vec{x}\in\mathbb{R}^l,\frac{\left\Vert A\vec{x}\right\Vert^2}{\left\Vert \vec{x}\right\Vert^2}\leq s_cs_r$.
\end{proof}

\begin{cor}\label{1eigenveclambda1}
Under the assumptions of \ref{largest eigenvalue}, $\vec{1}_{l\times l}$ is an eigenvector of $A^TA$ corresponding to eigenvalue $\lambda_1$.
\end{cor}

\begin{proof}
Each entry of $A\vec{1}_{l\times1}$ is the sum of a row of $A,$ which is $s_{r}$, so $A\vec{1}_{l\times1}=s_{r}\vec{1}_{k\times1}$. Similarly,
$A^{T}\vec{1}_{k\times1}=s_{c}\vec{1}_{l\times1}$. Hence, $A^{T}A\vec{1}_{l\times1}=A^{T}(s_{r}\vec{1}_{k\times1})=s_{r}(A^{T}\vec{1}_{k\times1})
=s_{r}s_{c}\vec{1}_{l\times1}=\lambda_{1}\vec{1}_{l}$, where the last equality follows by \ref{largest eigenvalue}. We have that
$A^{T}A\vec{1}_{l\times1}=\lambda_{1}\vec{1}_{l\times1}$, so $\vec{1}_{l\times1}$
is an eigenvector of $A^{T}A$ corresponding to eigenvalue $\lambda_{1}$.
\end{proof}

\begin{notn}
$J$ denotes a matrix with $1$ for every entry.
\end{notn}

\begin{thm}
(Quasirandomness Theorem) \label{QT} Suppose $\Gamma(L,R,E)$ is
a biregular bipartite graph with $\left|L\right|=k$ and $\left|R\right|=l$. Let the degree of every vertex in $L$ be $s_r$ and the degree of every vertex in $R$ be $s_c$. Let $X\subseteq L$ and $Z\subseteq R$, let $p$ be the density of
$\Gamma$, let A be the $k\times l$ adjacency matrix of $\Gamma$, and
let $\lambda_{i}$ be the i$^{th}$ eigenvalue of $A^{T}A$ in decreasing
order. Then

\[\left|\left|E(X,Z)\right|-p\left|X\right|\left|Z\right|\right|\leq\sqrt{\lambda_{2}\left|X\right|\left|Z\right|}\]
\end{thm}

\begin{proof}
Let $\vec{x}$ be the incidence vector of $X$ and let $\vec{z}$ be the incidence vector of $Z$.
\footnote{Consider the submatrix of $A$ that is the adjacency matrix of $\Gamma(X,Z,E(X,Z))$. Call this submatrix $B$. In this sentence, $X$ refers to the set of rows of $B$ and $Z$ refers to the set of columns of $B$, so \ref{incidence_vec} applies.}
$\left|E(X,Z)\right|=\vec{x}^{T}A\vec{z}$. Consider the subgraph
$\Gamma(X,Z,E(X,Z))$. If all vertices in $X$ were connected with
all vertices in $Z$, the number of edges in the subgraph would be
$\left|X\right|\left|Z\right|=\vec{x}^{T}J_{k\times l}\vec{z}$.

\begin{eqnarray*}
\left|\left|E(X,Z)\right|-p\left|X\right|\left|Z\right|\right|&=&\left|\vec{x}^{T}A\vec{z}-p(\vec{x}^{T}J_{k\times l}\vec{z})\right|
=\left|\vec{x}^{T}(A-pJ_{k\times l})\vec{z}\right|\\
&\leq&\left\Vert \vec{x}^{T}\right\Vert \left\Vert (A-pJ_{k\times l})\vec{z}\right\Vert
=\sqrt{\left|X\right|}\left\Vert (A-pJ_{k\times l})\vec{z}\right\Vert
\end{eqnarray*}

\noindent where the inequality follows by the Cauchy-Schwarz inequality. It
remains to show that $\left\Vert (A-pJ_{k\times l})\vec{z}\right\Vert \leq\sqrt{\lambda_{2}\left|Z\right|}$
i.e. $\left\Vert (A-pJ_{k\times l})\vec{z}\right\Vert ^{2}\leq\lambda_{2}\left|Z\right|=\lambda_{2}\left\Vert \vec{z}\right\Vert ^{2}$.

\begin{eqnarray*}
\left\Vert (A-pJ_{k\times l})\vec{z}\right\Vert ^{2}&=&\vec{z}^{T}(A-pJ_{k\times l})^{T}(A-pJ_{k\times l})\vec{z}\\
&=&\vec{z}^{T}(A^{T}-pJ_{k\times l}^{T})(A-pJ_{k\times l})\vec{z}\\
&=&\vec{z}^{T}(A^{T}A-pA^{T}J_{k\times l}-pJ_{k\times l}^{T}A+p^{2}J_{k\times l}^{T}J_{k\times l})\vec{z}
\end{eqnarray*}

\noindent We will simplify $A^{T}A-pA^{T}J_{k\times l}-pJ_{k\times l}^{T}A+p^{2}J_{k\times l}^{T}J_{k\times l}$ term-by-term.

$(\mbox{Simplifying } J_{k\times l}^{T}A)$ $\Gamma$ is biregular: Every vertex in $R$ is connected to $s_c$ vertices in $L$,
so $s_c=\frac{\left|E\right|}{l}$, and every vertex in $L$ is connected to $s_r$ vertices in $R$, so $s_r=\frac{\left|E\right|}{k}$. Put another way,
the entries of each column of $A$ sum to $s_c$ and the entries of each row of $A$ sum to $s_{r}$. $p=\frac{\left|E\right|}{kl}$, so:

\[s_{c}=\frac{\left|E\right|}{l}=\frac{\frac{\left|E\right|}{kl}(kl)}{l}=\frac{pkl}{l}=pk\]
\[s_r=\frac{\left|E\right|}{k}=\frac{\frac{\left|E\right|}{kl}(kl)}{k}=\frac{pkl}{k}=pl\]

\noindent Notice that each entry of $J_{k\times l}^{T}A$ is $s_c$, which is $pk$, so $J_{k\times l}^{T}A=pkJ_{l\times l}$.

$(\mbox{Simplifying } A^{T}J_{k\times l})$ $A^{T}J_{k\times l}=(J_{k\times l}^{T}A)^{T}=(pkJ_{l\times l})^{T}=pkJ_{l\times l}$, where the last equality
holds because $J_{l\times l}$ is symmetric.

$(\mbox{Simplifying } J_{k\times l}^{T}J_{k\times l})$ Each entry of $J_{k\times l}^{T}J_{k\times l}$ is the sum of a column of $J_{k\times l}$, which is $k$,
so $J_{k\times l}^{T}J_{k\times l}=kJ_{l\times l}$.

Substituting in for $J_{k\times l}^{T}A$, $A^{T}J_{k\times l}$, and $J_{k\times l}^{T}J_{k\times l}$:

\begin{eqnarray*}A^{T}A-pA^{T}J_{k\times l}-pJ_{k\times l}^{T}A+p^{2}J_{k\times l}^{T}J_{k\times l}&=&
A^{T}A-p(pkJ_{l\times l})-p(pkJ_{l\times l})+p^{2}(kJ_{l\times l})\\
&=&A^{T}A-p^{2}kJ_{l\times l}\equiv M
\end{eqnarray*}

By \ref{1eigenveclambda1}, $\vec{1}$ is an eigenvector of $A^TA$ to eigenvalue $\lambda_{1}=s_{r}s_{c}=(pk)(pl)=p^{2}kl$.
Since $J_{l\times l}\vec{1}=l\vec{1}$, $(p^{2}kJ_{l\times l})\vec{1}=p^{2}k(J_{l\times l}\vec{1})
=p^{2}k(l\vec{1})=(p^{2}kl)\vec{1}=\lambda_{1}\vec{1}$.

\[M\vec{1}=A^{T}A\vec{1}-p^{2}kJ_{l\times l}\vec{1}=
\lambda_{1}\vec{1}-\lambda_{1}\vec{1}=\vec{0}=0\vec{1}\]

\noindent so $\vec{1}$ is an eigenvector of $M$ corresponding to eigenvalue
$0$.

$M=A^{T}A-p^{2}kJ_{l\times l}=(A^{T}A)^{T}-(p^{2}kJ_{l\times l})^{T}=(A^{T}A-p^{2}kJ_{l\times l})^{T}=M^{T}$.
Since $M$ is a symmetric matrix, by the Spectral Theorem \ref{spec}, there exists
an orthogonal eigenbasis (\ref{eigenbasis}) to M. Let $\vec{e}_{i}$ be a vector in this
orthogonal eigenbasis, so $M\vec{e}_{i}=u_{i}\vec{e}_{i}$, where
$u_{i}\in\mathbb{R}$ is an eigenvalue of $M$ and $u_i$'s (aside from $u_1$) are indexed in decreasing order. Let $\vec{e}_{1}\equiv\vec{1}_{l}$,
so $u_{1}=0$. Since the $\vec{e}_{i}$ are orthogonal,
$\vec{1}$ is orthogonal to $\vec{e}_{i},\, i\geq2$. Notice that for $i\geq2$,
each entry of $J_{l\times l}\vec{e}_{i}$ is $\vec{1}\cdot\vec{e}_{i}=0$,
so $J_{l\times l}\vec{e}_{i}=\vec{0}$. Hence, for $i\geq2$,
$M\vec{e}_{i}=(A^{T}A-p^{2}kJ_{l\times l})\vec{e}_{i}=A^{T}A\vec{e}_{i}-p^{2}k(J_{l\times l}\vec{e}_{i})=A^{T}A\vec{e}_{i}$.
For $i\geq 2$, $u_{i}\vec{e}_{i}=M\vec{e}_{i}=A^{T}A\vec{e}_{i}=\lambda_{i}\vec{e}_{i}$
so $u_{i}=\lambda_{i}$ for $i\geq2$.

This implies that the largest eigenvalue of $M$ is $\lambda_{2}$, NOT $\lambda_{1}$: Since $\lambda_{i}$'s
are ordered by size and no $u_{i}=\lambda_{1}$ for $i\geq2$ and
$u_{1}=0$, which is not generally equal to $\lambda_{1}=s_{r}s_{c}\geq0$,
no $u_{i}$ ever is $\lambda_{1}$. The next largest value that
a $u_{i}$ can be is $\lambda_{2}$. (In particular, the largest eigenvalue of $M$ is $u_{2}=\lambda_{2}$.)

By \ref{RayP}, the largest eigenvalue of $M$ is $max_{\vec{z}}\frac{\vec{z}^{T}M\vec{z}}{\vec{z}^{T}\vec{z}}$.
$\frac{\vec{z}^{T}M\vec{z}}{\vec{z}^{T}\vec{z}}\leq max_{\vec{z}}\frac{\vec{z}^{T}M\vec{z}}{\vec{z}^{T}\vec{z}}=\lambda_{2}\Rightarrow\vec{z}^{T}M\vec{z}\leq\lambda_{2}\vec{z}^{T}\vec{z}$,
and $\vec{z}^{T}\vec{z}=\vec{z}\vec{z}=\left\Vert z\right\Vert ^{2}$,
so $\vec{z}^{T}M\vec{z}\leq\lambda_{2}\left\Vert z\right\Vert ^{2}$.
Recall,
\begin{eqnarray*}
\left\Vert (A-pJ_{k\times l})\vec{z}\right\Vert ^{2}&=&\vec{z}^{T}(A-pJ_{k\times l})^{T}(A-pJ_{k\times l})\vec{z}\\
&=&\vec{z}^{T}(A^{T}A-pA^{T}J_{k\times l}-pJ_{k\times l}^{T}A+p^{2}J_{k\times l}^{T}J_{k\times l})\vec{z}\\
&=&\vec{z}^{T}M\vec{z}\\
&\leq&\lambda_{2}\left\Vert z\right\Vert ^{2}
\end{eqnarray*}
which is what we needed to finish the proof.
\end{proof}

The smaller $\lambda_{2}$ is, the closer $\left|E(X,Z)\right|$
is to $p\left|X\right|\left|Z\right|$, so the closer $\frac{\left|E(X,Z)\right|}{\left|X\right|\left|Z\right|}$
is to $\frac{p\left|X\right|\left|Z\right|}{\left|X\right|\left|Z\right|}=p$.
Notice that $\frac{\left|E(X,Z)\right|}{\left|X\right|\left|Z\right|}$
is the density of the bipartite subgraph formed by $X$ and $Z$, $\Gamma(X\subseteq L,Z\subseteq R,E(X,Z))$. Hence,
the Quasirandomness Theorem says that the density of $\Gamma(X,Z,E(X,Z))$ is approximately the density of
the larger graph $\Gamma(L,R,E)$.

\begin{cor}\label{QTcor}
Under the same hypotheses as Theorem \ref{QT}, if $p^{2}\left|X\right|\left|Z\right|>\lambda_{2}$,
then $\left|E(X,Z)\right|>0$.
\end{cor}

\begin{proof}

\begin{eqnarray*}
p^{2}\left|X\right|\left|Z\right|>\lambda_{2}&\Leftrightarrow& p^{2}\left(\left|X\right|\left|Z\right|\right)^{2}>\lambda_{2}\left|X\right|\left|Z\right|\\
&\Leftrightarrow& p\left|X\right|\left|Z\right|>\sqrt{\lambda_{2}\left|X\right|\left|Z\right|}\\
&\Leftrightarrow& p\left|X\right|\left|Z\right|-\sqrt{\lambda_{2}\left|X\right|\left|Z\right|}>0
\end{eqnarray*}

\noindent By \ref{QT},

\begin{eqnarray*}
\left|\left|E(X,Z)\right|-p\left|X\right|\left|Z\right|\right|\leq\sqrt{\lambda_{2}\left|X\right|\left|Z\right|}
&\Rightarrow& -\sqrt{\lambda_{2}\left|X\right|\left|Z\right|}\leq\left|E(X,Z)\right|-p\left|X\right|\left|Z\right|\\
&\Leftrightarrow& p\left|X\right|\left|Z\right|-\sqrt{\lambda_{2}\left|X\right|\left|Z\right|}\leq\left|E(X,Z)\right|
\end{eqnarray*}

\noindent Combining the above results,

\noindent $0 < p\left|X\right|\left|Z\right|-\sqrt{\lambda_{2}\left|X\right|\left|Z\right|}\leq\left|E(X,Z)\right|\Rightarrow0<\left|E(X,Z)\right|$
\end{proof}

\subsection{How the Quasirandomness Theorem is a quasirandomness result.}

\begin{defn}
A \textbf{random graph} is a graph whose every pair of vertices is randomly assigned an edge. Pairs' assignments are independent of each other.
\end{defn}

\begin{rem}
A \textbf{random bipartite graph} is a random graph such that any two vertices in the same set have probability $0$ of forming an edge.
\end{rem}

Consider a random situation. Let $G(L',R',E')$ be a random bipartite graph with $\left\vert L'\right\vert=k$ and
$\left\vert R'\right\vert = l$, and
let each pair $\left\{l,r\right\}$, $l\in L'$ and $r\in R'$, have probability $p$ of being an edge.
Let $X'\subseteq L'$ and let $Z'\subseteq R'$. Consider the subgraph $g(X',Z',E(X',Z'))$.
The number of pairs of vertices of $g$ that can form edges is $\left|X'\right|\left|Z'\right|$.

Considering the designation of edge a ``success,''
$\left\vert E(X',Z')\right\vert$, the number of ``successes'' in $\left\vert X'\right\vert\left\vert Z'\right\vert$
independent trials, would follow a binomial distribution: $P(\left\vert E(X',Z')\right\vert=s)
=\left({\left|X'\right|\left|Z'\right|\atop s}\right)p^{s}(1-p)^{\left|X'\right|\left|Z'\right|-s}$.
$\left\vert E(X',Z')\right\vert$ would have expected value $p\left|X'\right|\left|Z'\right|$, so the density of $g$,
$\frac{\left\vert E(X',Z')\right\vert}{\left\vert X'\right\vert\left\vert\ Z'\right\vert}$, would have expected value
$\frac{p\left|X'\right|\left|Z'\right|}{\left|X'\right|\left|Z'\right|}=p$.
By the same argument, $P(\left\vert E'\right\vert=s)
=\left({\left|L'\right|\left|R'\right|\atop s}\right)p^{s}(1-p)^{\left|L'\right|\left|R'\right|-s}$,
the expected value of $\left\vert E'\right\vert$ would be $p\left|L'\right|\left|R'\right|$, so the density of $G$,
$\frac{E(L',R')}{\left\vert L'\right\vert\left\vert\ R'\right\vert}$, would have expected value $p$. The
density of $G$ and the density of $g$ have the same expected value, but there is no guarantee that the densities be within
some range of each other. The probability that the densities are wildly different, say a density of 0 and a density of 1, is nonzero.

Now consider biregular bipartite graph $\Gamma(L,R,E)$ described in the hypotheses of \ref{QT}.
The Quasirandomness Theorem says that the density of subgraph $\Gamma(X\subseteq L,Z\subseteq R,E(X,Z))$ must be within some range
\footnote{The range is controlled by $\lambda_2$ and the sizes of X and Z, and could be less than 1. The larger X and Z are and the smaller $\lambda_2$
is, the closer the density of the subgraph is to the density of the larger graph.}
of the density of $\Gamma(L,R,E)$, so in this sense one can expect the density of $\Gamma(X,Z,E(X,Z))$ to be approximately the density of $\Gamma(L,R,E)$. Similarly, one can expect the density of $G$ to be approximately the density of $g$ (in the sense that their expected values are the same). However, unlike the density of $\Gamma(L,R,E)$ and the density of $\Gamma(X,Z,E(X,Z))$, the density of $G$ and the density of $g$ are not necessarily within some range (other than 1) of each other.

$\Gamma(L,R,E)$ is a quasirandom graph because it is like, but not, a random graph $G(L',R',E')$. One can expect sufficiently large
\footnote{$\sqrt{\frac{\lambda_2}{\left\vert X\right\vert\left\vert Z\right\vert}}<1$}
subgraphs of $\Gamma(L,R,E)$ to have densities similar to, yet different from, densities of subgraphs of a random graph.

\section{Gowers theorem}

\begin{defn}
If $F$ is a field and $V$ is a vector space over $F$, then $\mathbf{GL(V)}$ is the group of nonsingular linear transformations from $V$ to $V$ under composition.
\end{defn}

\begin{defn}
If $d$ is a positive integer, then the \textbf{general linear group} $\mathbf{GL_{d}(F)}$ is the group of invertible $d\times d$ matrices with entries from $F$ under matrix multiplication.
\end{defn}

\begin{defn}
For a group $G$ and an integer $d\geq1$, a \textbf{d-dimensional representation of G over F}
is a homomorphic map $\varphi:\, G\rightarrow GL(V)\cong GL_{d}(F)$, where $V$
is a d-dimensional vector space ($V\cong F^{d}$) and $F$ is
a field. The \textbf{degree} of \textbf{$\varphi$} is $d$.
\end{defn}

\begin{rem}
To clarify, $\varphi:\, G\rightarrow GL(V)\cong GL_{d}(\mathbb{R})$ is a \textbf{representation of $G$ over $\mathbb{R}$}.
$\varphi$ maps elements of $G$ to invertible mappings from $\mathbb{R}^{d}$ to $\mathbb{R}^{d}$. Such mappings correspond to $d\times d$ invertible matrices with entries from $\mathbb{R}$.
\end{rem}

\begin{defn}
$\varphi:\, G\rightarrow GL(V)$ is a \textbf{trivial
representation} if it maps every element of $G$ to the identity transformation.
\end{defn}

\begin{thm}\label{GT}
(Gowers' Theorem - GT) Let $G$ be a group of order $\left|G\right|$
and let $m$ be the minimum degree of nontrivial representations of
G over the reals. If $X,Y,Z\subseteq G$ and $\left|X\right|\left|Y\right|\left|Z\right|\geq\frac{\left|G\right|^{3}}{m}$,
then $\exists\, x\in X,\, y\in Y,\, z\in Z\, s.t.\, xy=z$.
\end{thm}

\begin{cor}
\ref{GT} would still be true if its conclusion were replaced by $XYZ=G$
\end{cor}

\begin{proof}
Take $X,Y,Z\subseteq G$ such that $\left|X\right|\left|Y\right|\left|Z\right|\geq\frac{\left|G\right|^{3}}{m}$.\\
$XYZ=G$ means $\forall x\in X,\, y\in Y,\, z\in Z,\,\exists g\in G\, s.t.\, xyz=g$
and $\forall g\in G,\,\exists x\in X,\, y\in Y,\, z\in Z,\, s.t.\, xyz=g$.
The first statement holds by closure of $G$, so it remains to show
the second statement. Take $g\in G$. Let $Z'=gZ^{-1}$. By closure
of $G$, $Z'\in G$. Since $\left|Z'\right|=\left|Z\right|$, $\left|X\right|\left|Y\right|\left|Z'\right|\geq\frac{\left|G\right|^{3}}{m}$.
By \ref{GT}, $\exists\, x\in X,\, y\in Y,\, z'\in Z'\, s.t.\, xy=z'\Leftrightarrow xy(z'^{-1})=z'(z'^{-1})=1\Leftrightarrow xy(z'^{-1}g)=g\Leftrightarrow xyz=g.$
\end{proof}

\subsection{Translating Gowers Theorem: Proving $m_2\geq m$ Proves Gowers' Theorem}
$\,$\\

\noindent \textbf{Variables in this subsection refer to those defined in the context of $\Gamma(G_1,G_2,E)$}:
$\,$\\

To prove \ref{GT}, we take a graph theoretic view of
it. Let $G$ be a group. Let $\Gamma(G_{1},G_{2},E)$ be a bipartite graph with two sets
of vertices $G_{1}$ and $G_{2}$, which are copies of $G$. Let there be an edge between $g_1\in G_{1}$ and $g_2\in G_{2}$ only if $\exists y\in Y\subseteq G \,s.t.\, g_{1}y=g_{2}$, let $A$ be the $\left\vert G\right\vert\times\left\vert G\right\vert$ adjacency matrix of $\Gamma$, let $\lambda_2$ be the second largest eigenvalue of $A^TA$, let $p$ be the density of $\Gamma$, let $X\subseteq G_{1}$, and let $Z\subseteq G_{2}$.

\ref{GT} says that, for sufficiently large $X$ and $Z$, there
is at least one edge between a member of $X$ and a member of $Z$,
i.e. $\left|E(X,Z)\right|>0$. Curiously, which particular vertices
are chosen to constitute $X$ and $Z$ is irrelevant to guaranteeing
an edge between them. Rather, the sizes of $X$ and $Z$ are all that
matter.

In this graph theoretic view of Gowers' Theorem, the hypotheses of
the Quasirandomness Thrm hold.
\footnote{\ref{biregular} shows that $\Gamma$ is biregular}
If $p^{2}\left|X\right|\left|Z\right|>\lambda_{2}$
were to also hold, then by \ref{QTcor}, $\left|E(X,Z)\right|>0$, proving
Gowers' Theorem. To translate proving GT into proving
some other statement, we use the following results:

\begin{notn}
$g_1$ denotes any element of $G_1$ and $g_2$ denotes any element of $G_2$.
\end{notn}

\begin{lem}\label{biregular}
The degree of every vertex of $\Gamma(G_{1},G_{2},E)$ is $\left|Y\right|$
\end{lem}

\begin{proof}
We will show that every vertex in $G_1$ has degree $\left|Y\right|$ and every vertex in $G_2$ has degree $\left|Y\right|$, so every vertex of $\Gamma$ has degree $\left|Y\right|$.

Claim: Every $g_1$ has degree $\left|Y\right|$. Since $G$ is a group, by closure,
$\forall g_{1}\in G_{1}=G$ and $y\in Y\subseteq G,\, g_{1}y\in G=G_{2}$ so $g_{1}y=g_2$.
For each $g_1$, multiplication with each $y$ yields $\left|Y\right|$ distinct products in $G_2$.
Since $g_1$ and $g_2$ form an edge iff $\exists y\in Y \,s.t.\, g_{1}y=g_{2}$, $g_1$ can form no other edges, so the degree of every $g_1$ is $\left|Y\right|$.

Claim: Every $g_2$ has degree $\left|Y\right|$, i.e. every $g_2$ has $\left|Y\right|$ preimages in $G_1$: $\forall y\in Y, \exists \mbox{ unique } g_1\in G_1 \mbox{ s.t. } g_1y=g_2$. Take $y\in Y\subseteq G$. Since $G$ is a group, $y^{-1}\in G$. Take $g_2\in G_2=G$. By closure, $g_2y^{-1}\in G=G_1$ so $g_1=g_2y^{-1}$.
\end{proof}

\begin{cor}\label{EisGY}
$\left\vert E \right\vert=\left\vert G \right\vert\left\vert Y \right\vert$
\end{cor}

\begin{proof}
Every $g_1\in G_1$ forms $\left\vert Y\right\vert$ edges, and there are $\left\vert G\right\vert$ $g_1$'s, so $\left\vert E\right\vert=\left\vert G\right\vert\left\vert Y\right\vert$
\end{proof}

\begin{fact}\label{TrA}
If $A$ is an $n \times n$ real matrix with eigenvalues $\lambda_1,...,\lambda_n$, then
$Tr(A)=\underset{i=1}{\overset{n}{\sum}}\lambda_i$
\end{fact}

\begin{notn}
$\lambda_i$ denotes one of the $\left\vert G\right\vert$ eigenvalues of $A^TA$: $\left\{\lambda_1,...,\lambda_{\left\vert G\right\vert}\right\}$, listed in decreasing order. $m_i$ denotes the multiplicity of $\lambda_i$.
\end{notn}

\begin{cor}\label{lambda2ineql}
$\lambda_{2}<\frac{Tr(A^{T}A)}{m_{2}}$
\end{cor}

\begin{proof}
By \ref{TrA},
$Tr(A^TA)=\underset{i=1}{\overset{\left\vert G\right\vert}{\sum}}\lambda_i=\lambda_1 + m_2\lambda_2 + ... > m_2\lambda_2$, where the last inequality follows from $A^TA$ having nonnegative eigenvalues (by \ref{possemidef}) and from $\lambda_1>0$
\footnote{By \ref{largest eigenvalue}, $\lambda_1=s_rs_c$. Recall that $s_r$ is the sum of each row of $A$ and $s_c$ is the sum of each column of $A$. Here, we assume that $\Gamma$ is a nontrivial graph, i.e. it actually has edges, so $s_r>0$ and $s_c>0$. Hence, $\lambda_1>0$.}.
\end{proof}

\begin{lem}\label{TrATAisE}
$Tr(A^{T}A)=\left|E\right|$
\end{lem}

\begin{proof}
Let $\vec{c_1},...,\vec{c_{\left\vert G\right\vert}}$ be the column vectors of $A$ and let $c_{ij}$ denote a component of $\vec{c_j}$.

\[Tr(A^TA)=\underset{j=1}{\overset{\left\vert G\right\vert}{\sum}}\vec{c_j}\cdot\vec{c_j}
=\underset{j=1}{\overset{\left\vert G\right\vert}{\sum}}(\underset{i=1}{\overset{\left\vert G\right\vert}{\sum}}c_{ij}^2)
=\underset{j=1}{\overset{\left\vert G\right\vert}{\sum}}(\underset{i=1}{\overset{\left\vert G\right\vert}{\sum}}c_{ij})\]

The last equality follows because entries of $A$ are either $0$ or $1$, so $c_{ij}^2=c_{ij}$. The double summation adds all the entries of $A$,
hence counts the number of edges of $\Gamma(G_1,G_2,E)$.

In more detail: The second summation gives the degree of a particular $g_2$. The first summation cycles through all vertices in $G_2$. Hence, the double summation counts all the edges that vertices in $G_2$ are members of, so it counts all the edges of $\Gamma$.
\end{proof}

\begin{cor}\label{lambda2bd}
$\lambda_{2}<\frac{\left|G\right|\left|Y\right|}{m_{2}}$
\end{cor}

\begin{proof}
$\lambda_{2}<\frac{Tr(A^{T}A)}{m_{2}}=\frac{\left|E\right|}{m_{2}}=\frac{\left|G\right|\left|Y\right|}{m_{2}}$.
The first inequality holds by \ref{lambda2ineql}, the second equality
holds by \ref{TrATAisE}, and the third equality holds by \ref{EisGY}.
\end{proof}

\begin{rem}\label{p}
$p=\frac{\left|G\right|\left|Y\right|}{\left|G\right|\left|G\right|}=\frac{\left|Y\right|}{\left|G\right|}$,
where the first equality follows from \ref{EisGY} and \ref{density}.
\end{rem}

\begin{prop}
To prove Gowers' Theorem, it remains to show that $m_2\geq m$.
\end{prop}

\begin{proof}
>From \ref{lambda2bd}, we have that $\lambda_{2}<\frac{\left|G\right|\left|Y\right|}{m_{2}}$.
If we could show that $\frac{\left|G\right|\left|Y\right|}{m_{2}}\leq p^{2}\left|X\right|\left|Z\right|$,
then $\lambda_{2}<p^{2}\left|X\right|\left|Z\right|$, fulfilling
the hypotheses of \ref{QTcor} and reaching the conclusion of Gowers'
Theorem \footnote{its graph theoretic interpretation: $\left\vert E(X,Z)\right\vert>0$}. In other words, to prove GT, it remains to prove $\frac{\left|G\right|\left|Y\right|}{m_{2}}\leq p^{2}\left|X\right|\left|Z\right|$.

$\frac{\left|G\right|\left|Y\right|}{m_{2}}\leq p^{2}\left|X\right|\left|Z\right|\Leftrightarrow\frac{\left|G\right|\left|Y\right|}{m_{2}}\leq\left(\frac{\left|Y\right|}{\left|G\right|}\right)^{2}\left|X\right|\left|Z\right|\Leftrightarrow\frac{\left|G\right|^{3}}{m_{2}}\leq\left|X\right|\left|Y\right|\left|Z\right|$,
where the first iff follows from \ref{p}. To prove GT it remains to prove $\frac{\left|G\right|^{3}}{m_{2}}\leq\left|X\right|\left|Y\right|\left|Z\right|$.

Given GT's hypothesis
$\left|X\right|\left|Y\right|\left|Z\right|\geq\frac{\left|G\right|^{3}}{m}$,
if we could show $m_{2}\geq m$, then $\left|X\right|\left|Y\right|\left|Z\right|\geq\frac{\left|G\right|^{3}}{m_{2}}$.
Hence, to prove GT it remains to prove $m_{2}\geq m$.
\end{proof}

\subsection{Proving $m_2\geq m$}
$\,$\\

Recall that $m_{2}$ is the multiplicity of $\lambda_2$ and $m$ is the minimum degree
of nontrivial representations of $G$ over $\mathbb{R}$ i.e. the smallest dimension of a real vector space in which $G$ has nontrivial representation. To show that $m_{2}\geq m$, we will need some preliminary definitions and
results.

\begin{defn}
Let $V$ be a d-dimensional vector space. $U\subseteq V$ is \textbf{invariant} under $\varphi: G \rightarrow GL(V)$ if for all $g\in G$, $U$ is invariant under $\varphi(g)$, i.e. $\forall u\in U, g\in G, \varphi(g)u\in U$. Every mapping that $\varphi$ associates with an element of $G$ maps $U$ to $U$.
\end{defn}

\begin{defn}\label{eigenspace}
If $\lambda\in F$ and $A$ is an n x n matrix over $F$, then
the \textbf{eigenspace to eigenvalue $\lambda$} is $U_{\lambda}=\left\{ \vec{x}\in F^{n}\, s.t.\, A\vec{x}=\lambda\vec{x}\right\} $.
A member of the eigenspace is called an \textbf{eigenvector}
corresponding to $\lambda$.
\end{defn}

\begin{lem}\label{commuteinvariant}
If $AB=BA$, then every eigenspace of $A$ is invariant under $B$.
\end{lem}

\begin{proof}
Let $U_{\lambda}$ be an eigenspace of $A$. We want to show that
$\forall\vec{x}\in U_{\lambda},\, B\vec{x}\in U_{\lambda}$. Since
$\vec{x}\in U_{\lambda},\, A\vec{x}=\lambda\vec{x}$, so $AB\vec{x}=BA\vec{x}=B(\lambda\vec{x})=\lambda B\vec{x}$.
\end{proof}

\begin{defn} \label{eigenbasis}
An \textbf{eigenbasis} of a matrix $A$ is a set of eigenvectors of
$A$ that forms a basis for the domain of the linear transformation
corresponding to $A$.
\end{defn}

\begin{thm}\label{spec}
(Spectral Theorem) Every real symmetric matrix has an orthogonal eigenbasis.
\end{thm}

\begin{notn}
Given mapping $f: A\rightarrow B$ and $C\subseteq A$, $f|_{C}$ denotes the mapping that is the same as f, except with domain restricted to $C$. Hom(A,B) denotes the set of homomorphisms from A to B.
\end{notn}

\begin{prop}
Let $A=A^{T}$ be a real $d \times d$ matrix, and let $G$ be a group.
Let $m=\min \{ s: \exists \phi \in \mbox{nontrivial } Hom(G,GL_{s}(\mathbb{R}))\}$, i.e. m is the minimum degree of nontrivial representations of G over the reals. Let $\varphi \in Hom(G, GL_{d}(\mathbb{R}))$ be nontrivial. Suppose that $A$ commutes with all
matrices in $GL_{d}(\mathbb{R})$. Then there is an eigenvalue of $A$ with multiplicity at least $m$.
\end{prop}

\begin{proof}
By \ref{spec}, we can choose a particular eigenbasis of $A$.
Call this basis $\mathcal{B}_{A}=\left\{\vec{e_1},...,\vec{e_d}\right\}$. Since $\varphi$ is nontrivial, we can
pick $g_{0} \in G$, such that $\varphi(g_{0})$ is not the identity matrix.  Let $\psi: \mathbb{R}^{d}\rightarrow \mathbb{R}^{d}$ be
the unique linear map whose transformation matrix with respect to $\mathcal{B}_{A}$ is $\varphi(g_{0})$. Since $\varphi(g_{0})$ is not the identity
matrix, $\psi$ is not the identity map on $\mathbb{R}^{d}$.

Since $A$ commutes with every element of $GL_{d}(\mathbb{R})$, by \ref{commuteinvariant},
for every $g\in G$ and every eigenspace $U_\lambda$ of A, $U_\lambda$ is invariant under $\varphi(g)$.
Hence, $\varphi|_{U_\lambda}: g \mapsto \varphi(g)|_{U_\lambda}$ is
$\varphi|_{U_\lambda}: G \rightarrow GL({U_\lambda})$, a $dim(U_\lambda)$-dimensional representation of $G$.

In particular, $A$ commutes with $\varphi(g_{0})$, so by \ref{commuteinvariant},
$\psi$ sends each eigenspace of $A$ to itself. $\psi$ cannot act as the identity on
every $U_{\lambda}$, because if it did, then $\forall \vec{v} \in \mathbb{R}^{d}$, $\vec{v}=\sum_{i=1}^{d}\alpha_{i}\vec{e_{i}}$
where $\alpha_{i}\in\mathbb{R}$, and

\[ \psi(\vec{v})=\psi(\sum_{i=1}^{d}\alpha_{i}\vec{e_{i}})=\sum_{i=1}^{d}\alpha_{i}\psi(\vec{e_{i}})=\sum_{i=1}^{d}\alpha_{i}\vec{e_{i}}=\vec{v}
\]

\noindent so $\psi$ would act as the identity on $\mathbb{R}^{d}$, which is contrary to the choice of
$\psi$.

We've shown by contradiction that there must be an eigenspace $U_{\lambda'}$ of $A$ such that $\psi: U_{\lambda'} \rightarrow U_{\lambda'}$ is
not the identity map. Because $\psi|_{U_\lambda'}$ is not the identity map, $\varphi(g_{0})|_{U_{\lambda'}}$ is not the identity matrix,
so $\varphi|_{U_\lambda'}: G \rightarrow GL(U_{\lambda'})$ is a nontrivial representation of $G$.

By definition, $m$ is the minimum degree of nontrivial representations of $G$, so the degree of $\varphi|_{U_\lambda'}$
(which is the dimension of $U_\lambda'$) is at least $m$. Since $A$ is symmetric, the dimension of $U_{\lambda'}$
is the multipliticy of $\lambda'$, so the multiplicity of $\lambda'$ is at least $m$.
\end{proof}

\begin{defn}
$\sigma:\, V\rightarrow V$ is a \textbf{permutation} on set $V$
if it is a bijection.
\end{defn}

\begin{defn}
Consider a graph $G=(V,E)$. A graph automorphism is a mapping $\sigma:V\rightarrow V$
that preserves adjacency, i.e. $\forall i,j\in V,\, i\sim j\Leftrightarrow\sigma(i)\sim\sigma(j)$
\end{defn}

\begin{rem}
A graph automorphism for a bipartite graph $\Gamma(V_{1},V_{2},E)$ consists of permutations $\sigma_{1}:V_{1}\rightarrow V_{1}$
and $\sigma_{2}:V_{2}\rightarrow V_{2}$ s.t. $\forall v_{1}\in V_{1}$ and $v_{2} \in V_{2}$, $v_{1}\sim v_{2}\Leftrightarrow \sigma_{1}(v_{1})\sim \sigma_{2}(v_{2})$.
\end{rem}

\begin{defn}
$P(\sigma)$ is a \textbf{permutation matrix} of permutation
$\sigma$ if

\[ P(\sigma)_{ij}= \left\{ \begin{array}{ll}
         1 & \mbox{if $\sigma(i)=j$}\\
         0 & \mbox{otherwise}.\end{array} \right.\]
\end{defn}

\begin{lem}\label{graphauto_commute}
Let $\Gamma(V_{1},V_{2},E)$ be a biregular bipartite graph, let $A$ be its adjacency matrix, let $\sigma_{1}$ be a permutation of $V_{1}$, and let $\sigma_{2}$ be a permutation of $V_2$. Then $\sigma_{1}$ and $\sigma_{2}$ constitute a bipartite graph
automorphism iff $P(\sigma_{1})A=AP(\sigma_{2})$
\end{lem}

\begin{proof}
The claim is that
\[\forall i\in V_{1},\, j\in V_{2},\, i\sim j\Leftrightarrow\sigma_{1}(i)\sim\sigma_{2}(j)\Longleftrightarrow P(\sigma_{1})A=AP(\sigma_{2})\]
We will translate the right-hand side into some other statement.

By definition, $P(\sigma_{1})A=AP(\sigma_{2})\Leftrightarrow\forall i,j,\,\left[P(\sigma_{1})A\right]_{ij}=\left[AP(\sigma_{2})\right]_{ij}$.

For all $i,j$, $\left[AP(\sigma_{2})\right]_{ij}=\sum_{l=1}^{L} A_{il}P(\sigma_{2})_{lj}$. Notice that cells of A and cells of P only take values 1 or 0, so terms of the sum are either 1 or 0. The summation is equivalent to
summing only the terms that are 1. For a term to be 1, $A_{il}$ and
$P(\sigma_{2})_{lj}$ must both be 1. By definition, $A_{il}=1$ iff $i\sim l$,
and $P(\sigma_{2})_{lj}=1$ iff $\sigma_{2}(l)=j$.  Hence, $A_{il}P(\sigma_{2})_{lj}=1$ iff $i\sim l$ and $\sigma_{2}(l)=j$, so

\[\underset{l=1}{\overset{L}{\sum}}A_{il}P(\sigma_{2})_{lj}=\underset{l\, s.t.\, i\sim l=\sigma_{2}^{-1}(j)}{\sum}A_{il}P(\sigma_{2})_{lj}.\]

\noindent Multiple $l$'s can be adjacent to $i$, but since $\sigma_{2}$ is
one-to-one, only one $l$ can equal $\sigma_{2}^{-1}(j)$, so

\[\left[AP(\sigma_{2})\right]_{ij}=\underset{l\, s.t.\, i\sim l=\sigma_{2}^{-1}(j)}{\sum}A_{il}P(\sigma_{2})_{lj}=\left\{ \begin{array}{cc}
1 & if\, i\sim\sigma_{2}^{-1}(j)\\
0 & \textrm{otherwise}\end{array}\right.\]\\

For all i,j,$\left[P(\sigma_{1})A\right]_{ij}=\underset{k=1}{\overset{K}{\sum}}P(\sigma_{1})_{ik}A_{kj}$.
The terms of this sum are either 1 or 0, so the sum is equivalent
to summing only the terms that are 1. For a term to be 1, $P(\sigma_{1})_{ik}$ and $A_{kj}$ must both be 1.
By definition, $P(\sigma_{1})_{ik}=1$ iff $\sigma_{1}(i)=k$,
and $A_{kj}=1$ iff $k\sim j$. Hence, $P(\sigma_{1})_{ik}A_{kj}=1$ iff $\sigma_{1}(i)=k$ and $k\sim j$, so \[\underset{k=1}{\overset{K}{\sum}}P(\sigma_{1})_{ik}A_{kj}=\underset{k\, s.t.\,\sigma_{1}(i)=k\sim j}{\sum}P(\sigma_{1})_{ik}A_{kj}\].

\noindent Multiple $k$ could be adjacent to $j$, but since $\sigma_{1}$ is
one-to-one, only one $k=\sigma_{1}(i)$. Hence, the summation can
have only one term that is 1, so \[\left[P(\sigma_{1})A\right]_{ij}=\underset{k\, s.t.\sigma_{1}(i)=k\sim j}{\sum}P(\sigma_{1})_{ik}A_{kj}=\left\{ \begin{array}{cc}
1 & if\,\sigma_{1}(i)\sim j\\
0 & \textrm{otherwise}\end{array}\right.\]\\

For all i,j $\left[P(\sigma_{1})A\right]_{ij}=\left[AP(\sigma_{2})\right]_{ij}$ iff
the cells are both 1 or both 0 iff $\left(\sigma_{1}(i)\sim j\,\mathrm{and}\, i\sim\sigma_{2}^{-1}(j)\right)$
or $\left(\neg(\sigma_{1}(i)\sim j)\,\mathrm{and}\, \neg(i\sim\sigma_{2}^{-1}(j))\right)$.
Hence, $\sigma_{1}(i)\sim j$ is equivalent to $i\sim\sigma_{2}^{-1}(j)$.

To summarize, $P(\sigma_{1})A=AP(\sigma_{2})$ means $\forall i,j,\,\sigma_{1}(i)\sim j$ iff $i\sim\sigma_{2}^{-1}(j)$, so the lemma says: \[\forall i\in V_{1},\, j\in V_{2},\, i\sim j \Leftrightarrow \sigma_{1}(i)\sim\sigma_{2}(j)\Longleftrightarrow\forall i\in V_{1},\, j\in V_{2},\,\sigma_{1}(i)\sim j \Leftrightarrow i\sim\sigma_{2}^{-1}(j)\]\\

$\left(\Rightarrow\right)$Suppose \begin{equation}\label{1}i\in V_{1}, j\in V_{2}, i\sim j \Leftrightarrow \sigma_{1}(i)\sim\sigma_{2}(j).\end{equation}
We want to show $\sigma_{1}(i)\sim j \Leftrightarrow i\sim\sigma_{2}^{-1}(j)$.

\begin{equation}\sigma_{1}(i)\sim j\Leftrightarrow\sigma_{1}(i)\sim\sigma_{2}(\sigma_{2}^{-1}(j))\Leftrightarrow i\sim\sigma_{2}^{-1}(j)\end{equation}\noindent where the last equivalence comes from the $\Leftarrow$ direction of \ref{1}\\

$\left(\Leftarrow\right)$Suppose \begin{equation}\label{2}i\in V_{1}, j\in V_{2},\,\sigma_{1}(i)\sim j\Leftrightarrow i\sim\sigma_{2}^{-1}(j)\end{equation}

We want to show $i\sim j\Leftrightarrow\sigma_{1}(i)\sim\sigma_{2}(j)$.

\begin{equation}i\sim j\Leftrightarrow i\sim\sigma_{2}^{-1}(\sigma_{2}(j))\Leftrightarrow\sigma_{1}(i)\sim\sigma_{2}(j)\end{equation} where the last equivalence comes from the $\Leftarrow$ of \ref{2}
\end{proof}

\begin{claim}\label{PT=P-1}
Let $\sigma$ be a permutation and let $P$ be its $n\times n$ permutation matrix. $P^{T}=P^{-1}$.
\end{claim}

\begin{proof}
The claim is that $PP^T=P^TP=I_{n\times n}$.

Recall that $P(\sigma)_{ij}$ is $1$ if $\sigma(i)=j$ and is $0$ otherwise. Since $\sigma$ is a function, every row vector of $P$ has only one entry that is $1$. Since $\sigma$ is bijective, every column vector of $P$ has only one entry that is $1$. No two row vectors can have same the same component be $1$, because if there were two such row vectors, there would be a column vector with more than one 1-entry, contradicting that every column vector has only one 1-entry. Similarly, no two column vectors can have the same component be $1$. Hence, every pair of distinct row vectors of $P$ is orthogonal and every pair of distinct column vectors of $P$ is orthogonal.

Let the rows of P be $\vec{r_1},...,\vec{r_n}$. $(PP^T)_{ii}=\vec{r_i}\cdot\vec{r_i}=\underset{j=1}{\overset{n}{\sum}}r_{ij}=1$, since every row vector has only one entry that is $1$. For $i\neq j$, $(PP^T)_{ij}=\vec{r_i}\cdot\vec{r_j}=0$ since row vectors are orthogonal. Hence, $PP^T=I$.

Let the columns of P be $\vec{c_1},...,\vec{c_n}$. $(P^TP)_{ii}=\vec{c_i}\cdot\vec{c_i}=\underset{j=1}{\overset{n}{\sum}}c_{ij}=1$, since every column vector has only one entry that is $1$. For $i\neq j$, $(PP^T)_{ij}=\vec{c_i}\cdot\vec{c_j}=0$, since column vectors are orthogonal. Hence, $P^TP=I$.
\end{proof}

\begin{cor}\label{PcommutesAT}
Under the assumptions of \ref{graphauto_commute}, $P(\sigma_2)A^T=A^TP(\sigma_1)$ by \ref{graphauto_commute} and \ref{PT=P-1}
\end{cor}

\begin{lem}\label{Pcommutes}
Let $\Gamma(V_1,V_2,E)$ be a bipartite graph with adjacency matrix $A$. Let $\sigma_{1}$ be a permutation on $V_1$ and let $\sigma_{2}$ be a permutation on $V_2$. Let $\sigma_1$ and $\sigma_2$ constitute a graph automorphism. Then
$P(\sigma_{2})$ commutes with $A^{T}A$.
\end{lem}

\begin{proof}
\begin{eqnarray*}
P(\sigma_{2})^{-1}A^{T}AP(\sigma_{2})&=&P(\sigma_{2})^{T}A^{T}(I_{k\times k})AP(\sigma_{2})\\
&=&P(\sigma_{2})^{T}A^{T}(P(\sigma_{1})P(\sigma_{1})^{-1})AP(\sigma_{2})\\
&=&P(\sigma_{2})^{T}A^{T}(P(\sigma_{1})P(\sigma_{1})^{T})AP(\sigma_{2})\\
&=&(P(\sigma_{2})^{T}A^{T}P(\sigma_{1}))(P(\sigma_{1})^{T}AP(\sigma_{2}))\\
&=&(P(\sigma_{2})^{-1}A^{T}P(\sigma_{1}))(P(\sigma_{1})^{-1}AP(\sigma_{2}))=A^{T}A
\end{eqnarray*}

\noindent The last equivalence follows from \ref{graphauto_commute} and \ref{PcommutesAT}. We have $P(\sigma_{2})^{-1}A^{T}AP(\sigma_{2})=A^{T}A$, so $A^{T}AP(\sigma_{2})=P(\sigma_{2})A^{T}A$.
\end{proof}

Now consider the particular bipartite graph $\Gamma(G_1,G_2,E)$ involved in the proof
of Gowers' Theorem. $A$ is its adjacency matrix, which
is a $\left|G\right|$x$\left|G\right|$ real matrix, so $A^{T}A$
is a $\left|G\right|$x$\left|G\right|$ real matrix. Let $\lambda_{2}$
be the second largest eigenvalue of $A^{T}A$. Let $\sigma_{1}$ be a permutation of $G_1$, let $\sigma_{2}$ be a permutation of $G_2$ and let $\sigma_1$ and $\sigma_2$ constitute a graph automorphism. Let $\varphi:\, g\mapsto P(\sigma_{2})$
be a nontrivial representation of $G$, i.e. let $\varphi$ map some
$g$ to a $P(\sigma_{2})'$ that is not the identity matrix. Let $\psi$ be the linear transformation corresponding to this $P(\sigma_2)'$.
Using an argument similar to that in the proof of Proposition 3.27,
we will show that $m_{2}\geq m$.

\begin{rem}
Recall \ref{eigenspace}. $U_{\lambda_{2}}(A^{T}A)\equiv\left\{ \vec{x}\in\mathbb{R}^{\left|G\right|}\, s.t.\, A^{T}A\vec{x}=\lambda_{2}\vec{x}\right\} $
\end{rem}

\begin{prop}\label{m2geqm}
$m_{2}\geq m$
\end{prop}

\begin{proof}
$P(\sigma_{2})'$ is not the identity matrix, so $\psi$ does not act as the identity on $\mathbb{\mathbb{R}}^{\left|G\right|}$.
Suppose we could show that $\psi$ does not act as the identity on $U_{\lambda_{2}}(A^{T}A)$.

Then $P(\sigma_{2})'|_{U_{\lambda_{2}}(ATA)}$ would not be the identity matrix. Hence, $\varphi|_{U_{\lambda_{2}}(ATA)}:G\rightarrow P(\sigma_{2})|_{U_{\lambda_{2}}(ATA)}$ would be a nontrivial representation of $G$, so its degree would
be at least the minimum degree of a nontrivial representation of G i.e. $m$.

By \ref{Pcommutes}, each $P(\sigma_{2})$ commutes with $A^{T}A$,
so by \ref{commuteinvariant}, $U_{\lambda_{2}}(A^{T}A)$ is invariant under every $P(\sigma_{2})$,
so $P(\sigma_{2})|_{U_{\lambda_{2}}(ATA)}=GL(U_{\lambda_{2}}(A^TA))$,
so $\varphi|_{U_{\lambda_{2}}(ATA)}:G\rightarrow GL(U_{\lambda_{2}}(A^TA))$.
The dimension of $U_{\lambda_{2}}(A^TA)$ is the degree of $\varphi|_{U_{\lambda_{2}}(A^TA)}$, which we already showed is at least $m$.
Since $A^TA$ is symmetric, $m_2=dim(U_{\lambda_{2}}(ATA))$, which is at least $m$, so $m_2\geq m$.

It remains to show that $\psi$ does not act as the identity on $U_{\lambda_{2}}(A^{T}A)$. The only way a $\psi$ that is not the identity transformation can act as the identity on $U_{\lambda_{2}}(A^{T}A)$ is if each vector in $U_{\lambda_{2}}(A^{T}A)$
has identical components, i.e. is a multiple of $\vec{1}$. By \ref{1eigenveclambda1},
$A^{T}A\vec{1}=\lambda_{1}\vec{1}\neq\lambda_{2}\vec{1}$, so for
$c\in\mathbb{R}$, $A^{T}A(c\vec{1})\neq\lambda_{2}(c\vec{1})$ so
no multiple of $\vec{1}$ is in $U_{\lambda_{2}}(A^{T}A)$, so $\psi$
cannot act as the identity on $U_{\lambda_{2}}(A^{T}A)$.
\end{proof}

\ref{m2geqm} finishes the proof of Gowers' Theorem.


\begin{center}
\textbf{Acknowledgements}
\end{center}

Thanks to my mentors Irine Peng and Marius Beceanu for their help.

\begin{thebibliography}{9}

\bibitem{Babai}
L. Babai. Class Notes: Discrete Math - First 4 Weeks. http://people.cs.uchicago.edu/~laci/REU07/.

\bibitem{Dummit and Foote}
Dummit and Foote. 
Abstract Algebra 3rd edition. 
John Wiley and Sons Inc. 2004.

\bibitem{May}
J. A. Rice.
Mathematical Statistics and Data Analysis.
Duxbury Press. 2006.

\end{thebibliography}

\end{document}

