5 Expansion in the hypercube graph

5.1 The graph and its spectrum

Definition 5.1 Rerandomizing one coordinate

✓

For \(u \in \mathbb {F}_q^m\), an index \(i \in \{ 1,\dots ,m\} \), and \(x \in \mathbb {F}_q\), let

\[ \operatorname {rerand}_i(u,x) = u + x e_i. \]

This is the move obtained by rerandomizing the \(i\)-th coordinate of \(u\) by a uniform additive shift. In Lean, the same edge distribution is represented as the push-forward of the uniform distribution on triples \((u,i,x)\) by the map that replaces the \(i\)-th coordinate by \(x\); since \(x\) is uniform, this is the same distribution as the additive-shift presentation. The corresponding weight-sum identity identifies this push-forward distribution with the explicit edge coefficient used in the matrix proof.

Definition 5.2 Hypercube graph

✓

The hypercube graph \(C=(V,E)\) has vertex set \(V=\mathbb {F}_q^m\), and an edge between \(u\) and \(v\) whenever they differ in at most one coordinate. A random edge \((u,v) \sim C\) is sampled by drawing \(u \sim \mathbb {F}_q^m\), \(i \in \{ 1,\dots ,m\} \), and \(x \in \mathbb {F}_q\) uniformly and then setting \(v=\operatorname {rerand}_i(u,x)\).

Definition 5.3 Adjacency matrix and Laplacian

✓

Let \(M=q^m\). The normalized adjacency matrix of \(C\) is

\[ K = \mathbb {E}_{(u,v)\sim C} \lvert u \rangle \langle v \rvert , \]

and the Laplacian is

\[ L = \frac{1}{M}I-K. \]

Lemma 5.4 Laplacian rewrite

✓

The Laplacian can be written as

\[ L = \frac12 \mathbb {E}_{(u,v)\sim C} (\lvert u \rangle -\lvert v \rangle )(\langle u \rvert -\langle v \rvert ). \]

Proof ▶

The two vertex marginals of a random edge are uniform on \(\mathbb {F}_q^m\). Expanding the right-hand side yields \((1/M)I-K\).

Lemma 5.5 Average of a nontrivial additive character

✓

For \(\beta \in \mathbb {F}_q\),

\[ \mathbb {E}_{x \sim \mathbb {F}_q} \omega ^{\operatorname {tr}(\beta x)} = \begin{cases} 1 & \text{if } \beta =0, \\ 0 & \text{if } \beta \ne 0. \end{cases} \]

Proof ▶

If \(\beta =0\) the character is constant. If \(\beta \ne 0\), the map \(x \mapsto \beta x\) permutes \(\mathbb {F}_q\), so the average is the average of a nontrivial additive character, which vanishes.

Lemma 5.6 Orthogonality of finite-field characters

✓

For \(\alpha ,\beta \in \mathbb {F}_q^m\),

\[ \frac{1}{q^m}\sum _{u \in \mathbb {F}_q^m} \omega ^{\operatorname {tr}(u\cdot (\beta -\alpha ))} = \begin{cases} 1 & \text{if } \alpha =\beta , \\ 0 & \text{if } \alpha \ne \beta . \end{cases} \]

Proof ▶

This is Lemma 3.3 applied to \(v=\beta -\alpha \).

Lemma 5.7 Eigenvectors of the hypercube graph

✓

For each \(\alpha \in \mathbb {F}_q^m\), define

\[ \lvert \varphi _\alpha \rangle = \frac{1}{M^{1/2}} \cdot \sum _{u \in \mathbb {F}_q^m} \omega ^{\operatorname {tr}(u\cdot \alpha )} \lvert u \rangle . \]

Then the following two statements hold.

The \(\lvert \varphi _\alpha \rangle \)’s form an orthonormal basis of \(\mathbb {C}^V\).
For each \(\alpha \in \mathbb {F}_q^m\), \(\lvert \varphi _\alpha \rangle \) is an eigenvector for \(K\) with eigenvalue \(\frac{1}{M} \cdot \frac{m-|\alpha |}{m}\), where \(|\alpha |\) is the number of nonzero coordinates of \(\alpha \).

Proof ▶

First we prove 1. For \(\alpha ,\beta \in \mathbb {F}_q^m\),

\[ \langle \varphi _\alpha \mid \varphi _\beta \rangle = \frac{1}{M} \sum _{u \in \mathbb {F}_q^m} \omega ^{\operatorname {tr}(u\cdot (\beta -\alpha ))} = \begin{cases} 1 & \text{if } \alpha =\beta , \\ 0 & \text{if } \alpha \ne \beta , \end{cases} \]

by Lemma 5.6. Thus the \(\lvert \varphi _\alpha \rangle \) form an orthonormal basis of \(\mathbb {C}^V\).

Next we prove 2. For \(\alpha \in \mathbb {F}_q^m\),

\begin{equation} \begin{aligned} K \cdot \lvert \varphi _\alpha \rangle & = \left(\mathbb {E}_{(u,v)\sim C} \lvert u \rangle \langle v \rvert \right) \cdot \left(\frac{1}{M^{1/2}} \cdot \sum _{u \in \mathbb {F}_q^m} \omega ^{\operatorname {tr}(u\cdot \alpha )} \lvert u \rangle \right) \\ & = \frac{1}{M^{1/2}} \cdot \mathbb {E}_{(u,v)\sim C} \omega ^{\operatorname {tr}(v\cdot \alpha )} \lvert u \rangle . \end{aligned} \label{eq:eigenvector-calculation} \end{equation}

By the edge-sampling rule from Definition 5.2, we may write \(v=u+x e_i\), where \(i\) is uniformly random in \(\{ 1,\dots ,m\} \) and \(x\) is uniformly random in \(\mathbb {F}_q\). Therefore

\[ \eqref{eq:eigenvector-calculation} = \frac{1}{M^{1/2}} \cdot \mathbb {E}_{u,i,x} \omega ^{\operatorname {tr}((u+x e_i)\cdot \alpha )} \lvert u \rangle = \left(\mathbb {E}_{i,x}\omega ^{\operatorname {tr}(x\alpha _i)}\right) \cdot \frac{1}{M^{1/2}} \cdot \mathbb {E}_u \omega ^{\operatorname {tr}(u\cdot \alpha )} \lvert u \rangle = \frac{1}{M}\left(\mathbb {E}_{i,x}\omega ^{\operatorname {tr}(x\alpha _i)}\right) \cdot \lvert \varphi _\alpha \rangle . \]

Hence \(\lvert \varphi _\alpha \rangle \) is an eigenvector of \(K\) with eigenvalue

\[ \frac{1}{M} \cdot \mathbb {E}_i \left[\mathbb {E}_x \omega ^{\operatorname {tr}(x\alpha _i)}\right] = \frac{1}{M} \cdot \mathbb {E}_i \left[\mathbf{1}\! \left[[\right]\alpha _i=0]\right] = \frac{1}{M} \cdot \frac{m-|\alpha |}{m}, \]

by Lemma 5.5.

Lemma 5.8 Spectral gap of the Laplacian

✓

If \(\lambda _1 \le \lambda _2 \le \cdots \le \lambda _{q^m}\) are the eigenvalues of \(L\), then

\[ \lambda _1=0, \qquad \lambda _2 = \frac{1}{m q^m}. \]

Proof ▶

Lemma 5.7 identifies the two largest eigenvalues of \(K\), hence the two smallest eigenvalues of \(L=(1/q^m)I-K\).

5.2 Local and global variance

Definition 5.9 Local and global variance

✓

Let \(\lvert \psi \rangle \in \mathcal H_{\mathrm A} \otimes \mathcal H_{\mathrm B}\) and let \(0 \le A^u \le I\) be an operator for each \(u \in \mathbb {F}_q^m\). The local variance is

\[ \mathbf{Var}_{\mathrm{local}}(A,\psi ) = \frac12 \mathbb {E}_{(u,v)\sim C} \langle \psi \rvert (A^u-A^v)^2 \otimes I \lvert \psi \rangle , \]

and the global variance is

\[ \mathbf{Var}_{\mathrm{global}}(A,\psi ) = \frac12 \mathbb {E}_{u,v\sim \mathbb {F}_q^m} \langle \psi \rvert (A^u-A^v)^2 \otimes I \lvert \psi \rangle . \]

Lemma 5.10 Local variance as a Laplacian form

✓

Define

\[ A_{\mathrm{comb}} = \sum _{u \in \mathbb {F}_q^m} \lvert u \rangle \otimes A^u \otimes I. \]

Then

\[ \operatorname{Tr}(A_{\mathrm{comb}}^\dagger (L \otimes \lvert \psi \rangle \langle \psi \rvert ) A_{\mathrm{comb}}) = \mathbf{Var}_{\mathrm{local}}(A,\psi ). \]

Proof ▶

For \(u,v \in \mathbb {F}_q^m\),

\begin{equation} \begin{aligned} ((\langle u \rvert -\langle v \rvert ) \otimes \langle \psi \rvert ) \cdot A_{\mathrm{comb}} & = ((\langle u \rvert -\langle v \rvert ) \otimes \langle \psi \rvert ) \cdot \sum _{w \in \mathbb {F}_q^m} \lvert w \rangle \otimes A^w \otimes I \\ & = \langle \psi \rvert \cdot ((A^u-A^v)\otimes I). \end{aligned} \label{eq:edge-difference-action} \end{equation}

Therefore

\[ A_{\mathrm{comb}}^\dagger (L \otimes \lvert \psi \rangle \langle \psi \rvert ) A_{\mathrm{comb}} = \frac12 \mathbb {E}_{(u,v)\sim C} A_{\mathrm{comb}}^\dagger \bigl((\lvert u \rangle -\lvert v \rangle )(\langle u \rvert -\langle v \rvert ) \otimes \lvert \psi \rangle \langle \psi \rvert \bigr) A_{\mathrm{comb}} \]

by Lemma 5.4, and hence

\[ A_{\mathrm{comb}}^\dagger (L \otimes \lvert \psi \rangle \langle \psi \rvert ) A_{\mathrm{comb}} = \frac12 \mathbb {E}_{(u,v)\sim C} ((A^u-A^v)\otimes I)\lvert \psi \rangle \langle \psi \rvert ((A^u-A^v)\otimes I) \]

by 8. Taking the trace gives

\[ \operatorname{Tr}(A_{\mathrm{comb}}^\dagger (L \otimes \lvert \psi \rangle \langle \psi \rvert ) A_{\mathrm{comb}}) = \frac12 \mathbb {E}_{(u,v)\sim C} \langle \psi \rvert (A^u-A^v)^2 \otimes I \lvert \psi \rangle = \mathbf{Var}_{\mathrm{local}}(A,\psi ). \]

Lemma 5.11 Global variance as the orthogonal Fourier mass

✓

Write

\[ A_{\mathrm{comb}} = \lvert \varphi _0 \rangle \otimes A_0 + \lvert \varphi _\perp \rangle \otimes A_\perp , \]

where \(\lvert \varphi _\perp \rangle \) is orthogonal to \(\lvert \varphi _0 \rangle \). Then

\[ \frac{1}{q^m}\operatorname{Tr}((\langle \varphi _\perp \rvert \otimes A_\perp )(I\otimes \lvert \psi \rangle \langle \psi \rvert )(\lvert \varphi _\perp \rangle \otimes A_\perp )) = \mathbf{Var}_{\mathrm{global}}(A,\psi ). \]

Proof ▶

We first compute

\[ A_0 = (\langle \varphi _0 \rvert \otimes I)\cdot A_{\mathrm{comb}} = \left(\frac{1}{M^{1/2}} \cdot \sum _{u \in \mathbb {F}_q^m} \langle u \rvert \right) \otimes I \cdot \left(\sum _{u \in \mathbb {F}_q^m} \lvert u \rangle \otimes A^u \otimes I\right) = \frac{1}{M^{1/2}} \cdot \sum _{u \in \mathbb {F}_q^m} A^u \otimes I. \]

Writing \(A_{\mathrm{avg}}=\mathbb {E}_u A^u\), it follows that

\[ \lvert \varphi _0 \rangle \otimes A_0 = \sum _{u \in \mathbb {F}_q^m} \lvert u \rangle \otimes A_{\mathrm{avg}} \otimes I, \qquad \lvert \varphi _\perp \rangle \otimes A_\perp = \sum _{u \in \mathbb {F}_q^m} \lvert u \rangle \otimes (A^u-A_{\mathrm{avg}}) \otimes I. \]

Hence

\begin{equation} \frac{1}{M} \cdot \operatorname{Tr}((\langle \varphi _\perp \rvert \otimes A_\perp )(I\otimes \lvert \psi \rangle \langle \psi \rvert )(\lvert \varphi _\perp \rangle \otimes A_\perp )) = \mathbb {E}_{u \sim \mathbb {F}_q^m} \langle \psi \rvert (A^u-A_{\mathrm{avg}})^2 \otimes I \lvert \psi \rangle . \label{eq:just-took-trace} \end{equation}

Moreover,

\[ \mathbb {E}_{u \sim \mathbb {F}_q^m}(A^u-A_{\mathrm{avg}})^2 = \mathbb {E}_{u \sim \mathbb {F}_q^m}\bigl((A^u)^2-(A_{\mathrm{avg}})^2\bigr) = \frac12 \mathbb {E}_{u,v \sim \mathbb {F}_q^m} (A^u-A^v)^2. \]

Substituting this identity into 9 yields

\[ \frac{1}{M} \cdot \operatorname{Tr}((\langle \varphi _\perp \rvert \otimes A_\perp )(I\otimes \lvert \psi \rangle \langle \psi \rvert )(\lvert \varphi _\perp \rangle \otimes A_\perp )) = \frac12 \mathbb {E}_{u,v \sim \mathbb {F}_q^m} \langle \psi \rvert (A^u-A^v)^2 \otimes I \lvert \psi \rangle = \mathbf{Var}_{\mathrm{global}}(A,\psi ). \]

Lemma 5.12 Local-to-global inequality

✓

For every family \(\{ A^u\} \),

\[ \mathbf{Var}_{\mathrm{global}}(A,\psi ) \le m\, \mathbf{Var}_{\mathrm{local}}(A,\psi ). \]

Proof ▶

\begin{equation} \begin{aligned} A_{\mathrm{comb}}^\dagger (L \otimes \lvert \psi \rangle \langle \psi \rvert ) A_{\mathrm{comb}} & = (\langle \varphi _0 \rvert \otimes A_0+\langle \varphi _\perp \rvert \otimes A_\perp )(L \otimes \lvert \psi \rangle \langle \psi \rvert )(\lvert \varphi _0 \rangle \otimes A_0+\lvert \varphi _\perp \rangle \otimes A_\perp ) \\ & = (\langle \varphi _\perp \rvert \otimes A_\perp )(L \otimes \lvert \psi \rangle \langle \psi \rvert )(\lvert \varphi _\perp \rangle \otimes A_\perp ) \\ & = \langle \varphi _\perp \rvert L\lvert \varphi _\perp \rangle \cdot A_\perp \lvert \psi \rangle \langle \psi \rvert A_\perp . \end{aligned} \label{eq:used-0-eigenvector} \end{equation}

The second step uses that \(\lvert \varphi _0 \rangle \) is a \(0\)-eigenvector of \(L\). Since \(\lvert \varphi _\perp \rangle \) is orthogonal to \(\lvert \varphi _0 \rangle \), Lemma 5.8 gives

\[ \langle \varphi _\perp \rvert L\lvert \varphi _\perp \rangle \ge \frac{1}{mM} \cdot \langle \varphi _\perp \mid \varphi _\perp \rangle . \]

Therefore

\[ \mathbf{Var}_{\mathrm{local}}(A,\psi ) = \operatorname{Tr}(A_{\mathrm{comb}}^\dagger (L \otimes \lvert \psi \rangle \langle \psi \rvert ) A_{\mathrm{comb}}) = \langle \varphi _\perp \rvert L\lvert \varphi _\perp \rangle \cdot \operatorname{Tr}(A_\perp \lvert \psi \rangle \langle \psi \rvert A_\perp ) \]

by Lemma 5.10 and 10, so

\[ \mathbf{Var}_{\mathrm{local}}(A,\psi ) \ge \frac{1}{mM} \cdot \operatorname{Tr}((\langle \varphi _\perp \rvert \otimes A_\perp )(I\otimes \lvert \psi \rangle \langle \psi \rvert )(\lvert \varphi _\perp \rangle \otimes A_\perp )) = \frac{1}{m}\mathbf{Var}_{\mathrm{global}}(A,\psi ), \]

where the last step is Lemma 5.11. Rearranging gives the claim.