diff --git a/disctospec.tex b/disctospec.tex index 46662ce3fd7f4ec564818be6b2ea92e2e78e17b6..5d9fda7857406470dd69f53a1ae95ac6dc34aaeb 100644 --- a/disctospec.tex +++ b/disctospec.tex @@ -8,7 +8,7 @@ \title{Blah Blah Blah} \author{ - Jop Bri\"{e}t \and Shravas Rao + Shravas Rao } \date{\today} @@ -78,15 +78,15 @@ \begin{document} -\title{Notes on hypergraph versions of Conlon--Zhao} -\maketitle +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 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 Conlon 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 might reuse a lot of the definitions from my paper with Jop without stating them fully. In particular, let the definition of Cayley hypergraphs by the same, but let $\mathbf{g} = (0, g, g^2, \ldots, g^{t-1})$ and $q = \mathbf{1}$ be fixed 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}. +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\|_{t, \ldots, 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})|\] +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} @@ -103,14 +103,60 @@ where $R = \{z \in \mathbb{C} : \mathcal{R}(z) \geq 0\}$ is the set of all numbe 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. +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 $\epsilon$ for some constant $\epsilon$ depending on $\lambda$. For completeness, we will state a more general form of the Expander Mixing Lemma below. + +\begin{lem} +Let $f \in \R^{\Gamma}$, let $A_g$ be the adjacency tensor of the hypergraph $\cay^{(t)}(\Gamma, g)$. +Then for every $\lambda$, there exists an $\eps$ such that if +\[ +\left\|\sum_{g \in \Gamma} f(g)A_g\right\|_{t, \ldots, t} \leq \lambda, +\] +then +\[ +\left\|\sum_{g \in \Gamma} f(g)A_g\right\|_{\infty, \ldots, \infty} \leq \lambda|\Gamma|. +\] +\end{lem} +\begin{proof} +Let $T_1, \ldots, T_t$ be the sets obtained by applying Lemma~\ref{lem:disctoinfty} to $\sum_{g \in \Gamma} A_g$. +Then, +\begin{align*} +\left\|\sum_{g \in \Gamma} f(g)A_g\right\|_{\infty, \ldots, \infty} &\leq \sum_{g \in \Gamma} f(g)A_g(1_{T_1}, \ldots, 1_{T_t}) \\ +&\leq C\left\|\sum_{g \in \Gamma} f(g)A_g\right\|_{t, \ldots, t}\|1_{T_1}\|_t\cdots\|1_{T_t}\}_t \\ +&\leq C\lambda |\Gamma| +\end{align*} +as desired. +\end{proof} + +We attempt to prove the converse, stated below. -\snote{This is misleading!} \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)$. +Let $f \in \R^{\Gamma}$, let $A_g$ be the adjacency tensor of the hypergraph $\cay^{(t)}(\Gamma, g)$. +Then for every $\lambda$, there exists an $\eps$ such that if +\[ +\left\|\sum_{g \in \Gamma} f(g)A_g\right\|_{\infty, \ldots, \infty} \leq \eps|\Gamma|. +\] +then +\[ +\left\|\sum_{g \in \Gamma} f(g)A_g\right\|_{t, \ldots, t} \leq \lambda, +\] \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. +As a corollary, we see that small discrepancy implies small spectral expansion. + +\begin{cor} +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{cor} +\begin{proof} +If for all $T_1, \ldots, T_t \subseteq \Gamma$ it holds that +\[ +|A_H(1_{T_1}, \ldots, 1_{T_t})-A_K(1_{T_1}, \ldots, 1_{T_t})| \leq \epsilon |\Gamma|, +\] +it follows by Lemma~\ref{lem:disctoinfty} that +$\|A_H-A_K\|_{\infty, \ldots, \infty} \leq \pi^t \epsilon |\Gamma|$. +Finally, by Lemma~\ref{lem:disctospec} it follows that $\|A_H-A_K\|_{t, \ldots, t} \leq \lambda$. +\end{proof} + +To prove Lemma~\ref{lem:disctospec}, 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 @@ -123,16 +169,119 @@ where $\Delta_{h}$ is the multiplicative derivative \] \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} +The generalized von Neumann inequality can be thought of as an analogue of H\"{o}lder's inequality, in which the upper bound involves the Gower's norm of some function. +In the proof of Lemma~\ref{lem:disctospec}, we will explain how to choose $f$ and $\{a_{ij}\}$ so that the left-hand side of Equation~\eqref{eq:genvn} is equal to $\sum_{g \in \Gamma} f(g)A_g(x_1, \ldots, x_t)$ for vectors $x_i$. \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$ 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 \rightarrow \mathbb{C}$, +Let $\{a_{ij}\} \in (\F_p^n)^{t \times t}$ be so that $a_{ij} = 0$ for all $i = j$, and non-zero otherwise. +Let $f: (\F_p^n) \rightarrow \R$ be a function, and $g_i :(\F_p^n) \rightarrow \R$ for each $1 \leq i \leq t$ such that $|g_i| \leq 1$ for all $i$. +For all distinct $i_1, i_2 \in [t]$, +\begin{multline}\label{eq:genvn} +\left| \mathbb{E}_{z_1, \ldots, z_t \in \F_p^n} \left[f(z_1 + \cdots+z_t) \prod_{i=1}^t g_i(a_{i1} z_1+ \ldots + a_{it} z_t))\right]\right| +\leq \\ +\|f\|_{U^{3}}\mathbb{E}_{z \in \F_p^n}[g_{i_1}(z)^2]^{1/2}\mathbb{E}_{z \in \F_p^n}[g_{i_2}(z)^2]^{1/2} +%\mathbb{E}_{z \in \F_p^n}[g_3(z)^4]^{1/4} +\end{multline} +\end{lem} + +We note that this version of the generalized von Neumann inequality is slightly tighter than the usual version. +Rather than bounding in terms of $\max_{z \in \F_p^n} g_i(z)$, we bound in terms of the $2$nd moments. +For completeness, we include the proof below. + +\begin{proof}[Proof of Lemma~\ref{lem:genvn}] +Without loss of generality, assume that $i_1 = 1$ and $i_2 = 2$. +If this is not the case, one can exchange $g_{1}$ and $g_2$ with $g_{i_1}$ and $g_{i_2}$ and the first and second rows of $a$ with the $i_1$st and $i_2$nd rows of $a$, and the same with the columns of $a$. +Note that by the assumptions of the lemma, \[ -|\mathbb{E}_{z_1, \ldots, z_m \in \mathbb{F}_p^n} \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}. +\mathbb{E}_{z_1, \ldots, z_t \in \F_p^n}[g_i(a_{i1} z_1+ \ldots + a_{it} z_t))^2]^{1/2} = \mathbb{E}_{z \in \F_p^n}[g_i(z)^2]^{1/2} \] -\end{lem} +for all $i$. +By the above, the fact that $g_1$ does not depend on $z_1$, and the Cauchy-Schwarz inequality, the right-hand side of Eq.~\eqref{eq:genvn} is bounded above by +\begin{align*} +\mathbb{E}&_{z_2, \ldots, z_t \in \F_p^n} \left[g_1(a_{12} z_2+ \cdots + a_{1t} z_t)) \mathbb{E}_{z_1 \in \F_p^n}\left[f(z_1 + \cdots+z_t) \prod_{i=2}^t g_i(a_{i1} z_1+ \cdots + a_{it} z_t))\right]\right] +\leq \\ +&\mathbb{E}_{z_2, \ldots, z_t \in \F_p^n} \left[\mathbb{E}_{z_1 \in \F_p^n}\left[f(z_1 + \cdots+z_t) \prod_{i=2}^t g_i(a_{i1} z_1+ \cdots + a_{it} z_t))\right]^2\right]^{1/2}\mathbb{E}_{z \in \F_p^n} \left[g_1(z)^2\right]^{1/2}. +\end{align*} +Note that +\begin{align*} +\mathbb{E}_{z_1 \in \F_p^n}&\left[f(z_1 + z_2 + z_3) \prod_{i=2}^t g_i(a_{i1} z_1+ \cdots + a_{it} z_t)\right]^2 \nonumber +\\ +&= \mathbb{E}_{z_1 \in \F_p^n}\left[f(z_1 + \cdots+z_t) \prod_{i=2}^t g_i(a_{i1} z_1+ \cdots)\right] +\mathbb{E}_{z_1' \in \F_p^n}\left[f(z_1' + z_2 + \cdots+z_t) \prod_{i=2}^t g_i(a_{i1} z_1'+ \cdots)\right] \\ +&= \mathbb{E}_{z_1, h_1 \in \F_p^n}\left[\Delta_{h_1} \left(f(z_1 + \cdots+z_t) \prod_{i=2}^t g_i(a_{i1} z_1+ \cdots + a_{it} z_t)\right)\right]. +\end{align*} + +Applying Cauchy-Schwarz again, we get an upper bound of + +\begin{multline*} +\mathbb{E}_{z_1, h_1, z_3, z_4, \ldots \in \F_p^n} \left[\mathbb{E}_{z_2 \in \F_p^n}\left[\Delta_{h_1} \left(f(z_1 + \cdots+z_t) \prod_{i=3}^t g_i(a_{i1} z_1+ \cdots + a_{it} z_t)\right) +\right]^2\right]^{1/2} \\ +\mathbb{E}_{z_1, h, z_3, z_4, \ldots \in \F_p^n}\left[g_2(a_{21} z_1+ a_{23} z_3+a_{24}z_a+\cdots)^2g_2(a_{21} (z_1+h_1)+ a_{23} z_3+a_{24}z_a+\cdots)^2\right]^{1/2}. +\end{multline*} + +Note that +\begin{align*} +\mathbb{E}&_{z_1, h, z_3, z_4, \ldots\in \F_p^n}\left[g_2(a_{21} z_1+ a_{23} z_3+a_{24}z_a+\cdots)^2g_2(a_{21} (z_1+h_1)+ a_{23} z_3+a_{24}z_a+\cdots)^2\right] = \\ +&= \mathbb{E}_{z_3, z_4, \ldots\in \F_p^n}\left[\mathbb{E}_{z_1}\left[g_2(a_{21} z_1+ a_{23} z_3+a_{24}z_a+\cdots)^2\right]\mathbb{E}_{z_1'}\left[g_2(a_{21} z_1'+ a_{23} z_3+a_{24}z_a+\cdots)^2\right]\right] \\ +&= \mathbb{E}_{z}\left[g_2(z)^2\right]^2. +\end{align*} + +The rest of the proof follows by the usual generalized von Neumann inequality. + +%Then, +%\begin{multline*} +%\mathbb{E}_{z_2 \in \F_p^n}\left[\Delta_{h_1} f(z_1 + z_2+z_3) g_3(a_{31} z_1+ a_{32} z_2)g_3(a_{31} (z_1+h_1)+ a_{32} z_2)\right]^2 = \\ +%\mathbb{E}_{z_2, h_2 \in \F_p^n}\left[\Delta_{h_1, h_2} f(z_1 + \cdots + z_t) \prod_{s \in \{0, 1\}^2} g_3(a_{31} (z_1+s_1h_1)+ a_{32}(z_2+s_2h_2))\right]^2 +%\end{multline*} +%One more application of Cauchy-Schwarz gives +%\begin{multline*} +%\mathbb{E}_{z_1, h_1, z_2, h_2 \in \F_p^n}\left[\mathbb{E}_{z_3}\left[\Delta_{h_1, h_2} f(z_1 + \cdots + z_t)\right]^2\right]^{1/2} +%\mathbb{E}_{z_1, h_1, z_2, h_2 \in \F_p^n}\left[\prod_{s \in \{0, 1\}^2} g_3(a_{31} (z_1+s_1h_1)+ a_{32}(z_2+s_2h_2))^2\right]^{1/2}. +%\end{multline*} +%We have +%\[ +%\mathbb{E}_{z_1, h_1, z_2, h_2 \in \F_p^n}\left[\mathbb{E}_{z_3}\left[\Delta_{h_1, h_2} f(z_1 + \cdots + z_t)\right]^2\right] = \|f\|_{U^{3}}^{8}, +%\] +%and +%\begin{align*} +%\mathbb{E}&_{z_1, h_1, z_2, h_2 \in \F_p^n}\left[\prod_{s \in \{0, 1\}^2} g_3(a_{31} (z_1+s_1h_1)+ a_{32}(z_2+s_2h_2))^2\right]\\ +%&= \mathbb{E}_{z_1, z_1'}\left[\mathbb{E}_{z_2}\left[g_3(a_{31} z_1 + a_{32}z_2)^2g_i(a_{31} z_1' + a_{32}z_2)^2\right]\mathbb{E}_{z_2'}\left[g_3(a_{31} z_1 + a_{32}z_2')^2g_i(a_{31} z_1' + a_{32}z_2')^2\right]\right] \\ +%&= \mathbb{E}_{z_1, z_1'}\left[\mathbb{E}_{z_2}\left[g_3(a_{31} z_1 + a_{32}z_2)^2g_3(a_{31} z_1' + a_{32}z_2)^2\right]^2\right] \\ +%&\leq \mathbb{E}_{z_2}\left[\mathbb{E}_{z_1}\left[g_3(a_{31} z_1 + a_{32}z_2)^4\right]\mathbb{E}_{z_1'}\left[g_3(a_{31} z_1' + a_{32}z_2)^4\right]\right] \\ +%&= \mathbb{E}_{z}[g_3(z)^4]^2, +%\end{align*} +%as desired, where the inequality follows from Cauchy-Schwarz. +%\end{proof} +% +%We also prove the following claim that will be used to further upper bound the bound in Lemma~\ref{lem:genvn}. +% +%\begin{claim}\label{claim:expbound} +%Let $X \in \R$ be a random variable taking on positive values. +%Then, +%\[ +%\mathbb{E}[X^2]\mathbb{E}[X^4]^{1/4} \leq \mathbb{E}[X^3]. +%\] +%\end{claim} +%\begin{proof} +%Note that for a random variable $Z$ taking on positive values, +%\[ +%\frac{\mathbb{E}[Z^x]}{\mathbb{E}[Z]^x} +%\] +%increases as $x$ increases, when $x$ is positive. +%This follows from normalizing so that $\mathbb{E}[Z] = 1$, and using Jensen's inequality. +%Then if $Z = X^4$, +%\[ +%\frac{\mathbb{E}[Z^{1/2}]}{\mathbb{E}[Z]^{1/2}} \leq \frac{\mathbb{E}[Z^{3/4}]}{\mathbb{E}[Z]^{3/4}}, +%\] +%which implies that +%\[ +%\mathbb{E}[Z^{1/2}]\mathbb{E}[Z]^{1/4} \leq \mathbb{E}[Z^{3/4}], +%\] +%as desired. +\end{proof} -For certain groups $\Gamma$, a lower bound on the Gowers norm of a function $f$ implies certain structural properties of the function. To do this, we define the notion of a non-classical polynomial. +For certain groups $\Gamma$, a lower bound on the Gowers norm of a function $f$ implies certain structural properties of the function. +Before stating the exact result, we define the notion of a non-classical polynomial. \begin{define} A non-classical polynomial of degree $< d$ is a function $f: \mathbb{F}^n \rightarrow G$ where $G$ is an additive group, if for all $h_1, \ldots, h_{d+1}, x \in \mathbb{F}^n$, the following holds. @@ -166,53 +315,141 @@ Let $\delta > 0$ and $s \geq 0$. Then there exists an $\epsilon = \epsilon_{\de Given the structure of non-classical polynomials that take on values in $\mathbb{T}$ described above, we have the following lemma. \begin{lem}\label{lem:decomp} -Let $P: \mathbb{F}_p^n \rightarrow \mathbb{T}$ be a non-classical polynomial of degree $d < p$. Then there exist non-classical polynomials $P_0, \ldots, P_{d}: \mathbb{F}_p^n \rightarrow \mathbb{T}$ of degree $d$ such that +Let $P: \mathbb{F}_p^n \rightarrow \mathbb{T}$ be a non-classical polynomial of degree $d < p$. Then there exist non-classical polynomials $P_0, \ldots, P_{d}$ such that \[ -\sum_{j=0}^d P_j(x+jy) = P(y) +\sum_{j=0}^d P_i(x+jy) = P(y) \] for all vectors $x, y \in \mathbb{F}_p^n$. \end{lem} \snote{This is the lemma to change if we want to make our statement more general, I think} \begin{proof} -Decompose $P$ into a sum of linear forms as in Lemma~\ref{lem:classtonon}. For each $T_i$, we show that there exist $\alpha^i_0, \ldots, \alpha^i_{d}$ such that +Decompose $P$ into a sum of linear forms as in Lemma~\ref{lem:classtonon}. For each $T_i$, we show that there exist $\alpha_0, \ldots, \alpha_{d}$ such that \begin{equation} -\sum_{j=0}^d \alpha^i_j T_i(x+jy, \ldots, x+jy) = T_i(y, \ldots, y).\label{eq:need} +\sum_{j=0}^d \alpha_j T_i(x+jy, \ldots, x+jy) = T_i(y, \ldots, y).\label{eq:need} \end{equation} -We can then construct $P_j$ satisfying the lemma as follows. -\[ -P_j(x) = \sum_{i=0}^d \alpha_j^i T_i(x). -\] +This is enough to construct the $P_i$ desired. Because $T_i$ is an $i$-linear form, we can rewrite the left-hand side of~\eqref{eq:need} as \[ -\sum_{j=0}^d \sum_{s \in \{0, 1\}^i} \alpha^i_j T_i((1-s_1)x+js_1y, \ldots, (1-s_i)x+js_iy) = -\sum_{j=0}^d \sum_{s \in \{0, 1\}^i} \alpha^i_j j^{|s|}T_i((1-s_1)x+s_1y, \ldots, (1-s_i)x+s_iy) +\sum_{j=0}^d \sum_{s \in \{0, 1\}^i} \alpha_j T_i((1-s_1)x+js_1y, \ldots, (1-s_i)x+js_iy) = +\sum_{j=0}^d \sum_{s \in \{0, 1\}^i} \alpha_j j^{|s|}T_i((1-s_1)x+s_1y, \ldots, (1-s_i)x+s_iy) \] where $|s|$ denotes the Hamming weight of $s$. Then~\eqref{eq:need} holds if for all $0 \leq k < i$, \[ -\sum_{j=0}^d \alpha^i_j j^{k} = 0 +\sum_{j=0}^d \alpha_j j^{k} = 0 \] and \[ -\sum_{j=0}^d \alpha^i_j j^{i} = 1. +\sum_{j=0}^d \alpha_j j^{i} = 1. \] -This is a system of linear equations whose coefficients come from the first $i+1$ rows of a $(d+1) \times (d+1)$ Vandermonde matrix. Because $d < p$, the determinant of such a matrix is non-zero and thus the matrix is invertible and $\alpha^i_j$ exist as desired. +This is a system of linear equations whose coefficients come from the first $i+1$ rows of a $(d+1) \times (d+1)$ Vandermonde matrix. Because $d < p$, the determinant of such a matrix is non-zero and thus the matrix is invertible and $\alpha_j$ exist as desired. \end{proof} +Finally, we will use the following result of Carlen, Loss, and Lieb~\cite{Carlen:2006}. + +\begin{thm}[Multi-linear Riesz--Thorin Interpolation Theorem]\label{thm:mlrt} +Let~$T$ be a~$k$-linear form on~$\R^n$. +Let~$C: [0,1]^k\to \R_+$ be the function defined by +\[ +C(\tfrac{1}{p_1},\dots,\tfrac{1}{p_k}) = \|T\|_{p_1, \ldots, p_k}, +\] +for any~$p_i\in [1,\infty]$. +Then, $\ln C$ is a convex function on~$[0,1]^k$. +\end{thm} + +We are now ready to prove Lemma~\ref{lem:disctospec}. + \begin{proof}[Proof of Lemma~\ref{lem:disctospec}] -We prove the contrapositive. Assume that $\cay^{(t)}(\Gamma, q, S')$ does not have spectral expansion $\lambda$, that is that there exist vectors $x_1, \ldots, x_t$ such that $\|x_i\|_{\ell_t} = 1$ for all $i$, but $(A_H-A_K)(x_1, \ldots, x_t) \geq \lambda$. Let $1_{H, K} = \frac{1_{S'}}{|S'|}-\frac{1_{S}}{|S|}$. Then +We prove the converse, and thus start with the assumption that +\[ +\left\|\sum_{g \in \Gamma} f(g)A_g(x_1, \ldots, x_t) \right\|_{t, \ldots, t} > \lambda. +\] +Next we relate the value on the left-hand side to the Gowers norm of the vector $|\Gamma|^2f$. +%where $1_{H, K} = \frac{|\Gamma|^2}{|S'|}1_{S'}-\frac{|\Gamma|^2}{|S|}1_{S}$. +Let $x_1, \ldots, x_t$ be any set of vectors such that $\|x_i\|_{\infty} \leq 1$ for all $i$. +Then \begin{equation} -(A_H-A_K)(x_1, \ldots, x_t) = \frac{|\Gamma|^2}{t!} \sum_{\sigma \in S_t} \mathbb{E}_{u, g}[x_1(ug^{\sigma(1)-1})x_2(ug^{\sigma(2)-1})\cdots x_t(ug^{\sigma(t)-1})1_{H, K}(g)]. \label{eq:unravel} +\sum_{g \in \Gamma} f(g)A_g(x_1, \ldots, x_t) = \mathbb{E}_{u, g}[x_1(u)x_2(u+g)\cdots x_t(u+(t-1)g)(|\Gamma|^2f)]. \label{eq:unravel} \end{equation} - By the Lemma~\ref{lem:genvn},~\eqref{eq:unravel} is bounded above by $\Gamma|^2\|1_{H, K}\|_{U^t}$. By the inverse Gowers theorem, there exists a polynomial $P$ of degree $t-1$ such that $\mathbb{E}_{h}[e(P(g)) 1_{H, K}] \geq \epsilon$ for some $\epsilon$, that depends on $\lambda/|\Gamma|^2$. \snote{This is really bad} - By Lemma~\ref{lem:decomp}, there exist $P_0, \ldots, P_{t-1}$ such that \[e(P_0(x))e(P_1(x+y))\cdots e(P_{t-1}(x+(t-1)y)) = e(P(y)),\] and therefore \[\mathbb{E}_{u, g}[e(P_0(u))e(P_1(ug))\cdots e(P_{t-1}(ug^{t-1})) 1_{H, K}] = \mathbb{E}_{h}[e(P(g)) 1_{H, K}] \geq \epsilon,\] +%For $z \in (\F_p^n)^m$, let $f(z) = 1_{H, K}(z)$. +%Additionally, l +Let $a_{ij} = i-j$ for all $i$ and $j$, and $g_i = x_i$ for all $i$. +Then the right-hand side of Eq.~\eqref{eq:unravel} can be rewritten as +\[ +\mathbb{E}_{z_1, \ldots, z_t} \left[(|\Gamma|^2f(z_1+\cdots+z_t)) \prod_{i=1}^t g_i(a_{i1} z_1 + \cdots + a_{it} z_t)\right]. +\] +%From now on, let $t = 3$. +By Lemma~\ref{lem:genvn}, the right-hand side of Eq.~\eqref{eq:unravel} is bounded above by +\[ +\|(|\Gamma|^2f)\|_{U^t}\mathbb{E}[g_{i_1}^2]^{1/2}\mathbb{E}[g_{i_2}^2]^{1/2} = \left\|(|\Gamma|f)\right\|_{U^t}\|x_{i_1}\|_2\|x_{i_2}\|_2 +\] +for all distinct $i_1, i_2 \in [t]$, and thus +\[ +\left\|\sum_{g \in \Gamma} f(g)A_g(x_1, \ldots, x_t)\right\|_{\mathbf{p}} \leq \left\|(|\Gamma|f)\right\|_{U^t} +\] +where $\mathbf{p}$ is any vector whose coordinates are all $\infty$ except $\mathbf{p}_{i_1} = \mathbf{p}_{i_2} = 2$. +By Theorem~\ref{thm:mlrt}, it follows that +\[ +\left\|\sum_{g \in \Gamma} f(g)A_g(x_1, \ldots, x_t)\right\|_{t, \ldots, t} \leq \left\|(|\Gamma|f)\right\|_{U^t}. +\] + +Note that by our assumption, there exist $x_1, \ldots, x_t$ such that $\|x_i\|_{t} = 1$ for all $i$ and such that +\[ +\sum_{g \in \Gamma} f(g)A_g(x_1, \ldots, x_t) \geq \lambda, +\] and thus $\lambda$ is also a lower bound on $\left\|(|\Gamma|f)\right\|_{U^t}$. + +By the inverse Gowers theorem, there exists a polynomial $P$ of degree $t-1$ such that +\[\mathbb{E}_{h}[e(P(h)) (|\Gamma|f(h))] \geq \epsilon\] for some $\epsilon$. By Lemma~\ref{lem:decomp}, there exist $P_0, \ldots, P_{t-1}$ such that \[e(P_0(x))e(P_1(x+y))\cdots e(P_{t-1}(x+(t-1)y)) = e(P(y)),\] and therefore +\begin{multline*} +\mathbb{E}_{z_1, \ldots, z_t} \left[|\Gamma|f(z_1+\cdots+z_t) \prod_{i=1}^t e\left(P_{i-1}\left(\sum_{j=1}^t (i-j)z_j\right)\right)\right] = \\ +\mathbb{E} _{z_1, \ldots, z_t}\left[|\Gamma|f(z_1+\cdots+z_t) e(P(z_1+\cdots+z_t))\right] \geq \epsilon, +\end{multline*} and \[ -(A_H-A_K)(e(P_0), \ldots, e(P_{t-1})) \geq \frac{\epsilon|\Gamma|^2}{t!}. +\sum_{g \in \Gamma} f(g)A_g(e(P_0), \ldots, e(P_{t-1})) \geq \eps|\Gamma|. \] -Because the coordinates of $e(P_i)$ are bounded above in absolute value by $1$ for all $i$, by Lemma~\ref{lem:disctoinfty}, this implies that $H$ has discrepancy at least $\epsilon|\Gamma|/(t!\pi^t)$ with respect to $K$. +Because the coordinates of $e(P_i)$ are bounded above in absolute value by $1$ for all $i$, +this implies that $\left\|\sum_{g \in \Gamma} f(g)A_g\right\|_{\infty, \ldots, \infty} \geq \eps\|\Gamma\|$ as desired. +%by Lemma~\ref{lem:disctoinfty}, this implies that $H$ has discrepancy at least $\epsilon/\pi^t$ with respect to $K$. \end{proof} +We can use Lemma~\ref{lem:disctospec} along with Theorem 1.1 of~\cite{BG17} to an improvement over Theorem 4.1 in~\cite{BR16}, for certain types of random tensors. +We first state the following tail bound that's implicit in~\cite{BR16}. + +\begin{lem}\label{lem:exptotail} +Let $(X, \|\cdot\|)$ be a Banach space and let $A_1, \ldots, A_k \in X$. +Then there exist constants $C$ and $c$ depending on the Banach space such that +\[ +\Pr\left[\left\|\eps_1A_1+\cdots+\eps_kA_k\right\| \geq u\sqrt{k}\right] \leq C\exp(-cu^2/\sigma^2) +\] +where $\eps_1, \ldots, \eps_k$ are random Rademacher random variables, and $\mathbb{E}\left[\left\|\eps_1A_1+\cdots+\eps_kA_k\right\|\right] \leq C\sigma\sqrt{k}$. +\end{lem} + +\begin{cor} +Let $\Gamma = \mathbb{F}_p^n$, $A_1, \ldots, A_k$ be independent and identically distributed random $t$-tensors so that each $A_i = \cay^{(t)}(\mathbb{F}_p^n, q, s)$ for each $s \in \mathbb{F}_p^n$. +Then there exists a constant $C_{p, t}$ that depends on $p$ and $t$ such that, +\[ +\Pr\left[\left\|\eps_1A_1+\cdots+\eps_kA_k\right\|_{t, \ldots, t} \geq \frac{u \lambda \sqrt{k}}{\eps|\Gamma|}\right] +\leq +C_{p, t}\exp(-cu^2/\sigma^2), +\] +where $\sigma = {|\Gamma|t}\sqrt{|\Gamma|^{1-\frac{1}{\lceil t/2 \rceil}}\log(|\Gamma|)}$ +\end{cor} +\begin{proof} +Using the usual symmetrization trick (see Lemma 4.1 in~\cite{BR16}), it is enough to give an upper bound on +\[ +\mathbb{E}\left[\left\|\eps_1A_1+\cdots+\eps_kA_k\right\|_{t, \ldots, t}\right], +\] +where $\eps_1, \ldots, \eps_k$ are random Rademacher random variables. +By Theorem 1.1 from~\cite{BG17}, we have that +\begin{equation}\label{eq:gausswidth} +\mathbb{E}\left[\left\|\eps_1A_1+\cdots+\eps_kA_k\right\|_{\infty, \ldots, \infty}\right] +\leq +C{|\Gamma|t}\sqrt{k|\Gamma|^{1-\frac{1}{\lceil t/2 \rceil}}\log(|\Gamma|)}. +\end{equation} +Choose an aribtrary $\lambda$, and let $\eps$ be the corresponding constant from Lemma~\ref{lem:disctospec}. +The statement of the Corollary follows from Eq.~\eqref{eq:gausswidth}, Lemma~\ref{lem:disctospec} and Lemma~\ref{lem:exptotail}. +\end{proof} \bibliographystyle{alphaabbrv} \bibliography{disctospec.bib}