\newtheorem*{conj*}{Conjecture}

\theoremstyle{remark}

\newtheorem*{note}{Note}

\newtheorem{define}[thm]{Definition}

\newtheorem*{define*}{Definition}

\newcommand{\weakdivider}{\noindent\dotfill}

\newcommand{\divider}{\hrule}

\newcommand\numberthis{\addtocounter{equation}{1}\tag{\theequation}}

\newcommand{\eps}{\varepsilon}

\DeclareMathOperator{\Tr}{Tr}

  \newcommand{\R}{\mathbb{R}} % reals

  \newcommand{\C}{\mathbb{C}} % complex numbers

  \newcommand{\N}{\mathbb{N}} % natural numbers

  \newcommand{\Z}{\mathbb{Z}} % integers

  \newcommand{\F}{\mathbb{F}} % field

  \newcommand{\K}{\mathbb K} % field

  \newcommand{\T}{\mathbb T} % circle

  \newcommand{\pmset}[1]{\{-1,1\}^{#1}} % hypercube in +-1 basis

  \newcommand{\bset}[1]{\{0,1\}^{#1}} % hypercube

  \newcommand{\sphere}[1]{S^{#1-1}} % real unit sphere of dimension #1

  \newcommand{\ball}[1]{B_{#1}} % real unit ball of dimension $1

  \newcommand{\Orth}[1]{O(\R^{#1})} % orthogonal group

  \DeclareMathOperator{\im}{im} % image

  \DeclareMathOperator{\vspan}{Span} % kernel

  \newcommand{\1}{\mathbf{1}}

  \DeclareMathOperator{\Cball}{\mathcal C}

  \DeclareMathOperator{\cay}{Cay} 

  \DeclareMathOperator{\sol}{Sol} 

\newenvironment{enumerate*}%

  {\vspace{-2ex} \begin{enumerate} %

     \setlength{\itemsep}{-1ex} \setlength{\parsep}{0pt}}%

  {\end{enumerate}}

\newenvironment{itemize*}%

  {\vspace{-2ex} \begin{itemize} %

     \setlength{\itemsep}{-1ex} \setlength{\parsep}{0pt}}%

  {\end{itemize}}

\newenvironment{description*}%

  {\vspace{-2ex} \begin{description} %

     \setlength{\itemsep}{-1ex} \setlength{\parsep}{0pt}}%

  {\end{description}}

\begin{document}

We attempt to prove that small discrepancy implies small spectral expansion for Cayley hypergraphs over certain types of abelian groups.  In the case of regular graphs, this is known to hold for Cayley graphs over any group by a result of Conlan and Zhao, but does not hold for general graphs~\cite{Conlon:2016}.

We start by giving definitions.  Because these are just my personal notes, I will let the definition of Cayley hypergraphs be the exact same as that in my paper with Jop, except we let $\mathbf{g} = (0, g, g^2, \ldots, g^{t-1})$ and $q = \mathbf{1}$ for now.  In particular, $K = \cay^{(t)}(\Gamma, q, S)$ is a $t$-uniform Cayley hypergraph with edges induced by the set $S \subseteq \Gamma$, and we let $A_K$ be the corresponding adjacency tensor.  Given a Cayley hypergraph $K$, we say that a sub-hypergraph of $K$, $H = \cay^{(t)}(\Gamma, q, S')$ for some $S' \subseteq S$ has spectral expansion $\lambda$ with respect to $K$ if \[\lambda \geq \|A_H-A_K\|_{\ell_t, \ldots, \ell_t}.\]  We say that $H$ has discrepancy $\epsilon$ with respect to $K$ if for all $T_1, \ldots, T_t \subseteq \Gamma$, \[|A_H(1_{T_1}, \ldots, 1_{T_t})-A_K(1_{T_1}, \ldots, 1_{T_t})| \leq \epsilon |\Gamma|.\]  We can lower bound discrepancy in terms of the $\ell_{\infty}, \ldots, \ell_{\infty}$-norm of $A_H-A_K$ as stated in the following Lemma (the upper bound is trivial).  The proof follows almost exactly that of the same fact for matrices in Lemma 2.1 in~\cite{Conlon:2016}.

\begin{lem}\label{lem:disctoinfty}

If $A$ is an $n \times \cdots \times n$ $t$-linear form, there exist $T_1, \ldots, T_t \subseteq [n]$ such that \[\|A\|_{\ell_{\infty}, \ldots, \ell_{\infty}} \leq \pi^t|A(1_{T_1}, \ldots, 1_{T_t})|\]

\end{lem}

\begin{proof}

Let $\mathbb{D}$ be the set of complex numbers with absolute value $1$.  Recall that for all $z \in \mathbb{C}$ and a uniformly random unit complex vector $w$ that

\[

z = \pi \mathbb{E}_{w \in \mathbb{D}} [1_R(z \overline{w}) |z| w],

\]

where $R = \{z \in \mathbb{C} : \mathcal{R}(z) \geq 0\}$ is the set of all numbers with non-negative real part, and $1_R$ is the corresponding indicator function.  For a vector $x \in \mathbb{C}^{n}$, let $x'$ be the random vector defined by $x'_i = 1_R(x_i \overline{w})|x_i|$ where $w$ is again a uniformly random unit complex vector $w$.  Then we have

\begin{align}

\|A\|_{\ell_{\infty}, \ldots, \ell_{\infty}} &= \sup_{x[1], \ldots, x[t] \in \mathbb{D}^n} \sum_{i_1, \ldots, i_t \in [n]^t} A_{i_1, \ldots, i_t} x[1]_{i_1}\ldots x[t]_{i_t} \nonumber \\

&= \sup_{x[1], \ldots, x[t] \in \mathbb{D}^n} \left| \pi^t \mathbb{E}_{w_1, \ldots, w_t \in \mathbb{D}} \sum_{i_1, \ldots, i_t \in [n]^t} A_{i_1, \ldots, i_t} x'[1]_{i_1}\ldots x'[t]_{i_t} w_1 \ldots w_t \right| \nonumber \\

&\leq \pi^t \mathbb{E}_{w_1, \ldots, w_t \in \mathbb{D}} \sup_{x[1], \ldots, x[t] \in \mathbb{D}^n} \left| \sum_{i_1, \ldots, i_t \in [n]^t} A_{i_1, \ldots, i_t} x'[1]_{i_1}\ldots x'[t]_{i_t} \right|. \label{eq:reduce}

\end{align}

By convexity,~\eqref{eq:reduce} is maximized when $x'[j] \in \{0, 1\}^n$ for all $j$, or in other words, is an indicator vector.  Letting $T_j = \{i : x'[j]_{i} = 1\}$ proves the lemma.

\end{proof}

By a straightforward generalization of the Expander Mixing Lemma, it follows that if a Cayley hypergraph has spectral expansion $\lambda$, then it also has discrepancy $\lambda$.  We attempt to prove the converse, stated below.

\begin{lem}\label{lem:disctospec}

Let $\Gamma = F_p^n$. For $t \leq p$ and every $\lambda$ there exists an $\epsilon$ such that if a Cayley $t$-uniform hypergraph $H = \cay^{(t)}(\Gamma, q, S')$ has discrepancy $\epsilon$ with respect to $K = \cay^{(t)}(\Gamma, q, S)$, then it also has spectral expansion $\lambda$ with respect to $K = \cay^{(t)}(\Gamma, q, S)$.

\end{lem}

To prove this we use the generalized von Neumann inequality and the inverse Gowers theorem, which we state below.  We first state the definition of the Gowers norm.

\begin{define}

Given a function $f: \Gamma \rightarrow \mathbb{C}$, its Gowers uniformity norm is defined by

\[

\|f\|_{U^d} = [\mathbb{E}_{h_1, \ldots, h_d, x \in G} \Delta_{h_1}\cdots\Delta_{h_d} f(x)]^{1/2^d}

\]

where $\Delta_{h}$ is the multiplicative derivative

\[

\Delta_h f(x) = f(x+h)\overline{f(x)}.

\]

\end{define}

The following lemma relates the Gowers norm to \snote{not sure how to describe this}.  We state the form given in~\cite{Bhatt:2016}

\begin{lem}[Generalized von Neumann inequality]\label{lem:genvn}

Let $(\mathcal L_1, \ldots, \mathcal L_{t+1})$ be a collection of affine-linear forms $\mathcal L_i: (\mathbb{F}_p^n)^m \rightarrow \mathbb{F}_p^n)^m$ for some prime $p$ such that no form is a multiple of another.  Then for $f_1, \ldots, f_{t+1}: \mathbb{F}_p^n)^m \rightarrow \mathbb{C}$,

\[

|\mathbb{E}_{z_1, \ldots, z_m \in \mathbb{F}_p^n)^m} \prod_{i=1}^{t+1} f_i(\mathcal L_i(z_1, \ldots, z_m))| \leq \min_{1 \leq i \leq t+1} \|f_i\|_{U^t}.

\]