# A note on the elementary HDX construction of Kaufman-Oppenheim††thanks:
This work was done when the authors were visiting the Simons Institute for
Theory of Computing, Berkeley to participate in the summer cluster on Error-
Correcting Codes and High Dimensional Expanders 2019..

Prahladh Harsha Tata Institute of Fundamental Research, INDIA. email:
<EMAIL_ADDRESS>Research of the authors supported by the
Department of Atomic Energy, Government of India, under project no.
12-R&D-TFR-5.01-0500. Research of the first and second authors supported in
part by the Swarnajayanti and Ramanujan Fellowships respectively. Ramprasad
Saptharishi††footnotemark:

###### Abstract

In this note, we give a self-contained and elementary proof of the elementary
construction of spectral high-dimensional expanders using elementary matrices
due to Kaufman and Oppenheim [Proc. $50$th ACM Symp. on Theory of Computing
(STOC), 2018].

††footnotetext: Base version: () ,

##  1 Introduction

In the last few years, there has been a surge of activity related to high-
dimensional expanders (HDXs). Loosely speaking, high-dimensional expanders are
a high-dimensional generalization of classical graph expanders. Depending on
which definition of graph expansion is generalized, there are several
different (and unfortunately, many a time mutually inequivalent) definitions
of HDXs. For the purpose of this note, we will restrict ourselves to the
spectral definition of HDXs (see Definition 2.5). Lubotzky, Samuels and Vishne
[LSV05a, LSV05b] constructed high-dimensional analgoues of the Ramanujan
expanders of Lubotzky, Philips and Sarnak [LPS88], which they termed Ramanujan
complexes. These Ramanujan complexes have several desirable properties and
gave rise to the first construction of constant degree spectral HDXs. The
Ramanujan graphs have the nice property that they are simple to describe,
however their proof of expansion is extremely involved. The Ramanujan
complexes, on the other hand, are both non-trivial to describe as well as to
prove their high-dimensional expansion property. Subsequently Kaufman and
Oppenheim [KO18] gave an extremely elegant and elementary construction of
spectral HDXs using elementary matrices. Despite their construction being
elementary and simple, the proof of expansion, though straightforward,
requires some knowledge of some representation theory of the specific groups
involved in the construction. The purpose of this exposition is to give an
alternate elementary proof of the expansion of the Kaufman-Oppenheim HDX
construction.

The underlying graph of a HDX (even a onesided spectral HDX) is a two-sided
spectral expander. Thus, this construction has the added advantage that it
yields an elementary construction (accompanied with a simple proof) of a
standard two-sided spectral expander (though not an optimal one).

##  2 Preliminaries

We begin by recalling what a simplicial complex is.

######  Definition 2.1 (Simplicial complex).

A _simplicial complex_ $X$ over a finite set $U$ is a collection of subsets of
$U$ with the property that if $S\in X$ then any $T\subseteq S$ is also in $X$.

  * •

For all $i\geq-1$, define $X(i):=\left\\{S\in X\ :\ |S|=i+1\right\\}$ Thus, if
$X$ is non-empty, then $X(-1)=\left\\{\emptyset\right\\}$.

  * •

The elements of $X$ are called _simplices_ or _faces_. The elements of $X(0)$,
$X(1)$ and $X(2)$ are usually referred to as _vertices_ , _edges_ and
_triangles_ respectively.

  * •

The graph defined by $X(0)$ and $X(1)$ is called the _$1$ -skeleton_ of the
complex. More generally, for any $1\leq k\leq d$, the $d$-skeleton of the
complex $X$ is the sub-complex $X(-1)\cup X(0)\cup X(1)\cup\dots\cup X(k)$.

  * •

The _dimension_ of the simplicial complex $X$ defined as the largest $d$ such
that $X(d)$ (which consists of faces of size $d+1$) is non-empty.

  * •

The simplicial complex is said to be _pure_ if every face is contained in some
face in $X(d)$, where $d=\dim(X)$.

  * •

For a face $S\in X$, the _link_ of $S$, denoted by $X_{S}$, is the simplicial
complex defined as

$X_{S}:=\left\\{T\setminus S\ :\ T\in X\;,\;S\subseteq T\right\\}.\ $

Thus, a graph $G=(V,E)$ is just a simplicial complex $G$ of dimension one with
$G(0)=V$ and $G(1)=E$. We will deal with weighted pure simplicial complexes
where the weight function satisfies a certain balance condition.

######  Definition 2.2 (weighted pure simplicial complexes).

Given a $d$-dimensional pure simplicial complex $X$ and an associated weight
function $w\colon X\to\mathbb{R}_{\geq 0}$, we say the weight function is
balanced if the following two conditions are satisfied.

(2.3) $\displaystyle\sum_{\sigma\in X(d)}w(\sigma)$ $\displaystyle=1\;;$
$\displaystyle w(\sigma)$ $\displaystyle=\frac{1}{(i+2)}\sum_{\tau\in
X(i+1),\tau\supset\sigma}w(\tau),\ \text{ for all }i<d\text{ and }\sigma\in
X(i).$

A weighted simplicial complex $(X,w)$ is a pure simplical complex accompanied
with a balanced weight function $w$. If no weight function is specified, then
we work with the balanced weight function $w$ induced by the uniform
distribution on the set $X(d)$ of top faces.

For a face $S\in X$, the balanced weight function $w_{S}$ associated with the
link $X_{S}$ is the restricted weight function, suitable normalized, more
precisely $w_{S}:=w|_{X_{S}}/w(S)$.

Condition (2.3) states that the weight function can be interpreted as a family
of joint distributions $(w|_{X(-1)},\ldots,w|_{X(d)})$ where $w|_{X(i)}$ is a
probability distribution on $X(i)$. The distribution $w|_{X(d)}$ is specified
by the first condition in (2.3) while the second condition implies that the
weight distribution $w|_{x(i)}$ is the distribution on $X(i)$ obtained by
picking a random $\tau\in X(d)$ according to $w|_{X(d)}$ and then removing
$(d-i)$ elements uniformly at random.

We now recall the classical definition of what it means for a graph to be a
spectral expander.

######  Definition 2.4 (spectral expander).

Given an undirected weighted graph $G=(V,E,w)$ on $n$ vertices, let $A_{G}$ be
its normalized adjacency matrix given as follows:

$A_{G}(u,v):=\begin{cases}\frac{w(u,v)}{w(u)}&\text{if }\\{u,v\\}\in E,\\\
0&\text{otherwise.}\end{cases}$

Let $1=\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{n}\geq-1$ be the $n$
eigenvalues of $A_{G}$ with multiplicities in non-increasing order111By the
balance condition, $w$ satisfies $w(v)=\sum_{\\{u,v\\}\in E}w(u,v)$. The
matrix $A_{G}$ is self-adjoint with respect to the inner product $\left\langle
f,g\right\rangle_{w}:=\operatornamewithlimits{\mathbb{E}}_{v\sim w}[f(v)g(v)]$
since $\left\langle f,Ag\right\rangle_{w}=\left\langle
Af,g\right\rangle_{w}=\operatornamewithlimits{\mathbb{E}}_{\\{u,v\\}\sim
w}[f(u)g(v)]$. Hence, $A_{G}$ has $n$ real eigenvalues which can be obtained
using the A.2.. We denote the second largest eigenvalue of $G$ as
$\lambda(G)$.

$G$ is said to be a _$\lambda$ -spectral expander_ if
$\max\\{\lambda_{2},|\lambda_{n}|\\}\leq\lambda$.

$G$ is said to be a _$\lambda$ -onesided-spectral expander_ if
$\lambda_{2}\leq\lambda$.

This spectral definition of expanders is generalized to higher dimensional
simplicial complexes as follows.

######  Definition 2.5 ($\lambda$-spectral HDX).

A weighted simplicial complex $(X,w)$ of dimension $d\geq 1$ is said to be a
_$\lambda$ -spectral HDX_222These are sometimes also referred to as
$\lambda$-link HDXs or $\lambda$-local-expanders. if for every $-1\leq i\leq
d-2$ and $s\in X(i)$, the weighted $1$-skeleton of the link $(X_{s},w_{s})$ is
a $\lambda$-spectral expander.

A weighted simplicial complex $(X,w)$ of dimension $d\geq 1$ is said to be a
_$\lambda$ -onesided spectral HDX_ if for every $-1\leq i\leq d-2$ and $s\in
X(i)$, the weighted $1$-skeleton of the link $(X_{s},w_{s})$ is a
$\lambda$-onesided-spectral expander.

Using Garland’s technique [Gar73], Oppenheim [Opp18] showed that if the
1-skeleton all the links are connected, then a spectral gap at dimension
$(d-2)$ descends to all lower levels.

######  Descent Theorem 2.5 ([Opp18]).

Suppose $(X,w)$ is a $d$-dimensional weighted simplicial complex with the
following properties.

  * •

For all $s\in X(d-2)$, the link $(X_{s},w_{s})$ is a
$\lambda$-(onesided)-spectral expander.

  * •

The $1$-skeleton of every link is connected.

Then, $(X,w)$ is a
$\left(\frac{\lambda}{1-(d-1)\lambda}\right)$-(onesided)-spectral HDX.

Thus to prove that a given simplicial complex, it suffices to show that the
1-skeleton of all links are connected and a spectral gap at the top level. For
the sake of completeness, we give a proof of the Section 2 in Appendix A which
includes a descent theorem for the least eigenvalue as well.

##  3 Coset complexes

In this section, we construct certain special simplicial complexes based on a
group and its subgroups, that are called _coset complexes_. For a basic primer
on group theory, see Appendix B

######  Definition 3.1 (coset complex).

Let $G$ be a group and let $K_{1},\ldots,K_{d}$ be $d$ subgroups of $G$. The
coset complex $\mathcal{X}(G,\left\\{K_{1},\ldots,K_{d}\right\\})$ is a
$(d-1)$-dimensional simplicial complex defined as follows:

  * •

The _vertices_ , $\mathcal{X}(0)$, consists of cosets of $K_{1},\ldots,K_{d}$
and we shall say cosets of $K_{i}$ are of _type_ $i$.

  * •

The _maximal faces_ , $\mathcal{X}({d-1})$, consists of $d$-sets of cosets of
different types with a non-empty intersection. That is,

$\left\\{g_{1}K_{1},\ldots,g_{d}K_{d}\right\\}\in\mathcal{X}(d-1)\Longleftrightarrow
g_{1}K_{1}\cap\cdots g_{d}K_{d}\neq\emptyset.$

An equivalent way of stating this is that
$\left\\{g_{1}K_{1},\ldots,g_{d}K_{d}\right\\}\in\mathcal{X}(d-1)$ if and only
if there is some $g\in G$ such that $g_{i}K_{i}=gK_{i}$ for all $i$.

  * •

The lower dimensional faces are obtained by _down-closing_ the maximal faces.
Hence, for $0\leq r\leq d$,
$\left\\{g_{i_{1}}K_{i_{1}},\ldots,g_{i_{r}}K_{i_{r}}\right\\}\in\mathcal{X}(r-1)$
if and only if $i_{j}\neq i_{k}$ for all $j\neq k$ and

$g_{i_{1}}K_{i_{1}}\cap\cdots\cap g_{i_{r}}K_{i_{r}}\neq\emptyset.$

We shall call the set $\left\\{i_{1},\ldots,i_{r}\right\\}$ the _type_ of this
face.

  * •

The dimension of this complex is $(d-1)$.

  * •

The weight function we will use is the one induced by the uniform distribution
on the top face $\mathcal{X}(d-1)$.

A simplicial complex constructed this way is _partite_ in the sense that each
maximal face consists of vertices of distinct types.

#### Connectivity:

######  Observation 3.2.

$g_{1}K_{1}\cap g_{2}K_{2}\neq\emptyset$ if and only if $g_{1}^{-1}g_{2}\in
K_{1}K_{2}$.

###### Proof.

($\Rightarrow$) Say $x=g_{1}k_{1}=g_{2}k_{2}$ for $k_{1}\in K_{1}$ and
$k_{2}\in K_{2}$. Then $g_{1}^{-1}g_{2}=g_{1}^{-1}x\cdot
x^{-1}g_{2}=k_{1}k_{2}^{-1}\in K_{1}K_{2}$.

($\Leftarrow$) If $g_{1}^{-1}g_{2}=k_{1}k_{2}$ for $k_{1}\in K_{1}$ and
$k_{2}\in K_{2}$, then $g_{1}k_{1}=g_{2}k_{2}^{-1}\in g_{1}K_{1}\cap
g_{2}K_{2}$. ∎

######  Lemma 3.3 (Criterion for connected $1$-skeletons).

The $1$-skeleton (underlying graph) of
$\mathcal{X}(G,\left\\{K_{1},\ldots,K_{d}\right\\})$ is connected if and only
if $G=\left\langle K_{1},\ldots,K_{d}\right\rangle$.

###### Proof.

($\Leftarrow$) Since there is always an edge between $gK_{i}$ and $gK_{j}$ for
$i\neq j$, it suffices to show that $K_{1}$ is connected to $gK_{1}$ for an
arbitrary $g\in G$. Suppose, for an arbitrary element $g\in G$, we have
$g=g_{1}\ldots g_{r}$ where $g_{j}\in K_{i_{j}}$ and $i_{j}\neq i_{j+1}$ for
each $j$. We might wlog. assume that (a) $g_{1}\in K_{1}$ (otherwise set
$g=1\cdot g_{1}\cdots g_{r}$) and (b) if $r\geq 2$, then $i_{r}\neq 1$ (since
otherwise we might then have worked with $g^{\prime}=g_{1}g_{2}\ldots g_{r-1}$
as $gK_{1}=g^{\prime}g_{r}K_{1}=g^{\prime}K_{1}$).

Then, we get the following path connecting $K_{1}$ and $gK_{i_{r}}$

$K_{1}=g_{1}K_{i_{1}}\rightarrow(g_{1}g_{2})K_{i_{2}}\rightarrow(g_{1}g_{2}g_{3})K_{i_{3}}\rightarrow\ldots\rightarrow(g_{1}\cdots
g_{r})K_{i_{r}}=gK_{i_{r}}.$

Note that, due to Observation 3.2, each successive pair of cosets are
connected by an edge in the simplicial complex. Now, since $gK_{i_{r}}$ is
adjacent to $gK_{1}$ (as $i_{r}\neq 1$), we have that $K_{1}$ is connected to
$gK_{1}$.

($\Rightarrow$) For an arbitrary $g\in G$, since the $1$-skeleton is connected
we have a path

$K_{1}=g_{0}K_{i_{0}}\rightarrow g_{1}K_{i_{1}}\rightarrow\cdots\rightarrow
g_{r}K_{i_{r}}=gK_{1}.$

By Observation 3.2, for every $j=0,\ldots,r-1$, we have $g_{j}^{-1}g_{j+1}\in
K_{i_{j}}K_{i_{j+1}}\in\left\langle K_{1},\ldots,K_{d}\right\rangle$.
Therefore,

$g=(g_{0}^{-1}g_{1})\cdot(g_{1}^{-1}g_{2})\cdots(g_{r-1}^{-1}g_{r})\in\left\langle
K_{1},\ldots,K_{d}\right\rangle.\qed$

#### Structure of links of the coset complex:

For any set $S\subseteq[d]$, define the group $K_{S}:=\mathop{\bigcap}_{i\in
S}K_{i}$; let $K_{\emptyset}:=\left\langle K_{1},\ldots,K_{d}\right\rangle$.
The following lemma shows that the links of a coset complex are themselves
coset complexes.

######  Lemma 3.4.

For any $v\in\mathcal{X}(k)$ of type $S\subseteq[d]$, the link $X_{v}$ is
isomorphic to the simplicial complex defined by
$\mathcal{X}(K_{S},\left\\{K_{S}\cap K_{i}\ :\ i\notin S\right\\})$.

###### Proof.

It suffices to prove this lemma for $v\in\mathcal{X}(0)$ as links of higher
levels can be obtained by inductive applications of this case.

Observe that if $g$ is any element of $G$, then
$(g_{i_{1}}K_{i_{1}},\ldots,g_{i_{r}}K_{i_{r}})\in\mathcal{X}(r-1)$ if and
only if the tuple
$(gg_{i_{1}}K_{i_{1}},\ldots,gg_{i_{r}}K_{i_{r}})\in\mathcal{X}(r-1)$.
Therefore, the link of a coset $gK_{i}$ is isomorphic to the link of the coset
$K_{i}$. Thus, it suffices to prove the lemma for links of the type
$X_{K_{i}}$ for some $i\in[d]$.

Let $v$ be the coset $K_{1}$, without loss of generality. The _vertices_ of
the link, $X_{v}(0)$, are cosets of $K_{2},\ldots,K_{d}$ that have a non-empty
intersection with $K_{1}$. Note that any non-empty intersection
$g_{j}K_{j}\cap K_{1}$ of a cosets with $K_{1}$ is itself a coset
$\tilde{g_{j}}(K_{j}\cap K_{1})$ of the intersection subgroup $K_{j}\cap
K_{1}$ in $K_{1}$. Therefore, the vertices of the link $X_{v}(0)$ are in
bijective correspondence with cosets of $\left\\{K_{j}\cap K_{1}\ :\
j\in\left\\{2,\ldots,d\right\\}\right\\}$.

The maximal faces in $X$ that contain the coset $K_{1}$ are precisely $d$-sets
of cosets $\left\\{K_{1},g_{2}K_{2},\ldots,g_{d}K_{d}\right\\}$ with a non-
empty intersection and hence

$\emptyset\neq K_{1}\cap g_{2}K_{2}\cap\cdots\cap g_{d}K_{d}=(g_{2}K_{2}\cap
K_{1})\cap\ldots(g_{d}K_{d}\cap K_{1})=\tilde{g_{2}}(K_{2}\cap
K_{1})\cap\ldots\cap\tilde{g_{d}}(K_{d}\cap K_{1}),$

which are precisely the maximal faces of the coset complex
$\mathcal{X}\left(K_{1},\left\\{K_{j}\cap K_{1}\ :\
j\in\left\\{2,\ldots,d\right\\}\right\\}\right)$. This establishes the
isomorphism between $X_{v}$ and $\mathcal{X}\left(K_{1},\left\\{K_{j}\cap
K_{1}\ :\ j\in\left\\{2,\ldots,d\right\\}\right\\}\right)$. ∎

##  4 A concrete instantiation

The simplicial complex of Kaufman and Oppenheim [KO18] is a specific
instantiation of the above _coset complex_ construction. We will need some
notation to describe their group.

### Notation

  * •

Let $R$ denote the ring $\frac{\mathbb{F}_{p}[t]}{\left\langle
t^{s}\right\rangle}$. This is a ring whose elements can be identified with
polynomials in $\mathbb{F}_{p}[t]$ of degree less than $s$ (where addition and
multiplication are performed modulo $t^{s}$). We will think of $p$ as some
fixed prime power, $t$ a formal variable and $s$ as a growing integer.

  * •

For $1\leq i,j\leq d$ with $i\neq j$ and an element $r\in R$, we define the
$e_{i,j}(r)$ to be the $d\times d$ elementary matrix with $1$’s on the
diagonal and $r$ on the $(i,j)$-th entry.

For the sake of notational convenience, we shall abuse this notation and use
$e_{i+d,j}(r),e_{i,j+d}$ etc. to refer to $e_{i,j}(r)$ by _wrapping around_ if
necessary. For example, $e_{d,d+1}(r)$ refers to $e_{d,1}(r)$.

We are now ready to describe the groups in the construction.

$\displaystyle\text{For $i\in\left\\{1,\ldots,d\right\\}$,}\quad K_{i}$
$\displaystyle=\left\langle
e_{j,j+1}(at+b)\;:\;a,b\in\mathbb{F}_{p}\,,\,j\in[d]\setminus\left\\{i\right\\}\right\rangle.$
$\displaystyle G$ $\displaystyle=\left\langle K_{1},\ldots,K_{d}\right\rangle$

Each $K_{i}$ is generated by elementary matrices that have $1$’s on the
diagonal and an arbitrary linear polynomial in one entry of the generalised
diagonal $\left\\{(i,j)\;:\;i+1=j\bmod d\right\\}$.

It so happens that the group $G$ generated by the subgroups
$K_{1},\ldots,K_{d}$ is $\mathrm{SL}_{d}(R)$, the group of $d\times d$
matrices with entries in $R$ whose determinant is $1$ (in $R$). This is a non-
trivial fact. All we will need is the simpler fact that $|G|$ grows
exponentially with $s$ (for fixed $p$ and $d$) while the size of the groups
$K_{i}$ are functions of $p$ and $d$ (and independent of $s$). This will
follow from the sequence of observations and lemmas developed in the following
section.

###  4.1 Explicit description of the groups

The following is an easy consequence of the definition of $e_{i,j}(r)$.

######  Observation 4.1.

  * •

_Sum:_ If $i\neq j$, then $e_{i,j}(r_{1})\cdot
e_{i,j}(r_{2})=e_{i,j}(r_{1}+r_{2})$.

  * •

_Product:_ If $i\neq j$ and $k\neq\ell$, then the commutator333The commutator
of two elements $g,h$, denoted by $[g,h]$ is defined as $g^{-1}h^{-1}gh$.
(B.2) $[e_{i,j}(r_{1}),e_{k,\ell}(r_{2})]$ behaves as follows.

$[e_{i,j}(r_{1}),e_{k,\ell}(r_{2})]=\begin{cases}e_{i,\ell}(r_{1}r_{2})&\text{if
$j=k$ and $i\neq\ell$},\\\ \mathrm{id}&\text{if $j\neq k$}.\end{cases}$

Therefore, we have that

$\left[e_{i_{1},i_{2}}(r_{1}),\left[e_{i_{2},i_{3}}(r_{2}),\cdots\left[e_{i_{\ell-1},i_{\ell}}(r_{\ell-1}),e_{i_{\ell},i_{\ell+1}}(r_{\ell})\right]\cdots\right]\right]=e_{i_{1},i_{\ell+1}}(r_{1}\cdots
r_{\ell})$

and hence $e_{i,j}(r)$ can be generated for any $r\in R$. This in particular
implies that $|G|$ is at least $|p^{s}|$. On the other hand, the size of
$K_{i}$ depends only on $d,p$ and is independent of $s$. The lemma below
describes $K_{d}$; the other $K_{i}$’s are just rearrangements of rows and
columns in $K_{d}$.

######  Lemma 4.2 (Explicit description of $K_{d}$).

The group $K_{d}=\left\langle
e_{i,i+1}(at+b)\;:\;a,b\in\mathbb{F}_{p}\,,\,i\neq d\right\rangle$ consists of
matrices $A=(A_{i,j})$ of the following form:

$\displaystyle A_{i,j}=\begin{cases}0&\text{if }i>j,\\\ 1&\text{if }i=j,\\\
\text{a polynomial of degree $\leq r$}&\text{if }j-i=r.\end{cases}$

Therefore, we can obtain a crude bound of $|K_{n}|\leq p^{O(d^{3})}$. In fact,
we can generalise the above definition to define the group $\widetilde{K_{S}}$
for any $S\subseteq[d]$ as follows:

$\widetilde{K_{S}}:=\left\langle
e_{i,i+1}(at+b)\;:\;a,b\in\mathbb{F}_{p}\,,\,i\notin S\right\rangle.$

These groups can also be explicitly described.

######  Lemma 4.3 (Explicit description of $\widetilde{K_{S}}$).

For any $\emptyset\neq S\subseteq[d]$, group $\widetilde{K_{S}}$ is the set of
all $d\times d$ matrices $A=(a_{ij})$ of the form

$A_{i,j}=\begin{cases}1&\text{if }i=j,\\\ \text{a polynomial of degree $\leq
j-k$}&\text{if }j\neq k\text{ and
}\left\\{k,k+1,\ldots,j-1\right\\}_{\bmod{d}}\cap S=\emptyset,\\\
0&\text{otherwise}.\end{cases}$

###### Proof.

Any $A\in\widetilde{K_{S}}$ can be expressed as $A=B_{1}\cdots B_{m}$ where
each $B_{r}=e_{i_{r},i_{r}+1}(\ell_{r})$, for some linear polynomial
$\ell_{r}$, with $i_{r}\notin S$. Then,

$\displaystyle A_{i,j}$
$\displaystyle=\sum_{\begin{subarray}{c}i_{1},\ldots,i_{m+1}\\\
i_{1}=i\;,\;i_{m+1}=j\end{subarray}}(B_{1})_{i_{1},i_{2}}(B_{2})_{i_{2},i_{3}}\cdots(B_{m})_{i_{m},i_{m+1}}.$

From the structure of each $B_{r}$, any nonzero contribution from the RHS must
involve either $i_{r+1}=i_{r}$, or $i_{r+1}=i_{r}+1$ if $r\notin S$. This
forces that the only entries of $A$ that are nonzero, besides the diagonal,
are at $(i,j)$ with none of $\left\\{i,i+1,\ldots,j\right\\}$ in $S$.

In the case when $\left\\{i,i+1,\ldots,j\right\\}\cap S=\emptyset$, the above
argument also shows that the entry $A_{i,j}$ has degree at most $j-i$.
Furthermore, Observation 4.1 shows that $e_{i,j}(f)\in\widetilde{K_{S}}$ for
an arbitrary polynomial $f(t)$ of degree at most $j-i$. From this, we can
deduce that the structure of $\widetilde{K_{S}}$ is exactly as claimed. ∎

From the explicit structure of the groups, we have the following corollary.

######  Corollary 4.4 (Intersections of $K_{i}$’s).

For any $S\subseteq[d]$,

$\widetilde{K_{S}}=\left\langle
e_{i,i+1}(at+b)\;:\;a,b\in\mathbb{F}_{p}\,,\,i\notin
S\right\rangle=\mathop{\bigcap}_{i\in S}K_{i}=K_{S}$

In other words, the group generated by the intersection of generators equals
the group intersection.

The above corollary tells us that we can drop the tilde notation and use
$K_{S}$ for $\widetilde{K_{S}}$.

###  4.2 Connectivity of this complex

######  Lemma 4.5.

Let $S\subset[d]$ with $|S|\leq d-2$. Then,

$K_{S}=\left\langle K_{S}\cap K_{i}\;:\;i\in[d]\setminus S\right\rangle.$

###### Proof.

It is clear that $K_{S}$ is a superset of the RHS. It only remains to show
that the other containment also holds. To see this, consider an arbitrary
generator $e_{j,j+1}(r)$ of $K_{S}$. Since $j\notin S$ and $|S|\leq d-2$,
there is some $i\in[d]\setminus\left(S\cup\left\\{j\right\\}\right)$.
Therefore, $e_{j,j+1}(r)\in K_{S}\cap K_{i}$ and hence is generated by the
RHS. ∎

Combining the above lemma with Lemma 3.3 and Lemma 3.4, we have the following
corollary.

######  Corollary 4.6.

For the coset complex $\mathcal{X}(G,\left\\{K_{1},\ldots,K_{d}\right\\})$
defined by the above groups, the $1$-skeleton of every link is connected.

##  5 Spectral expansion of the complex

In this section we prove that the coset complex
$\mathcal{X}(G,\left\\{K_{1},\ldots,K_{d}\right\\})$ is a good spectral HDX.
The Section 2 states that it suffices to show that the $1$-dimensional links
of faces in $\mathcal{X}(d-3)$ are good spectral expanders.

###  5.1 Structure of $1$-dimensional links

One dimensional links of the coset complex constructed are links of
$v\in\mathcal{X}(G,\left\\{K_{1},\ldots,K_{d}\right\\})$ of size exactly
$(d-2)$ (which are elements of $\mathcal{X}(d-3)$. Any such $v$ can be written
as
$\left\\{gK_{1},\ldots,gK_{d}\right\\}\setminus\left\\{gK_{i},gK_{j}\right\\}$
for $i,j\in[d]$ with $i\neq j$ and $g\in G$. Since the link of $v$ is
isomorphic to the link of
$\left\\{K_{1},\ldots,K_{d}\right\\}\setminus\left\\{K_{i},K_{j}\right\\}$, we
might as well assume that $g=\mathrm{id}$. These happen to be of two types
depending on whether $i$ and $j$ are consecutive or not.

######  Observation 5.1.

Consider
$v=\left\\{K_{1},\ldots,K_{d}\right\\}\setminus\left\\{K_{i},K_{j}\right\\}$
where $i$ and $j$ are _not_ consecutive (i.e. $(i-j)\neq\pm 1\bmod d$). Then
the $1$-dimensional link of $v$ is a complete bipartite graph.

###### Proof.

Note that since $j\neq i+1$, we have
$[e_{i,i+1}(r_{1}),e_{j,j+1}(r_{2})]=\mathrm{id}$ by 4.1. Hence, these two
elements commute.

The link of $v$ corresponds to the coset complex
$\mathcal{X}(H,\left\\{H_{1},H_{2}\right\\})$ where

$\displaystyle H$
$\displaystyle=K_{[d]\setminus\left\\{i,j\right\\}}=\left\langle
e_{i,i+1}(at+b),e_{j,j+1}(at+b)\;:\;a,b\in\mathbb{F}_{p}\right\rangle,$
$\displaystyle H_{1}$
$\displaystyle=K_{[d]\setminus\left\\{i\right\\}}=\left\langle
e_{i,i+1}(at+b)\;:\;a,b\in\mathbb{F}_{p}\right\rangle,$ $\displaystyle H_{2}$
$\displaystyle=K_{[d]\setminus\left\\{j\right\\}}=\left\langle
e_{j,j+1}(at+b)\;:\;a,b\in\mathbb{F}_{p}\right\rangle.$

Thus, the groups $H_{1}$ and $H_{2}$ commute with each other and hence any
element of $h\in H$ can be written as $h=g_{1}\cdot g_{2}$ where $g_{1}\in
H_{1}$ and $g_{2}\in H_{2}$. 3.2 implies that the resulting graph is the
complete bipartite graph. ∎

The interesting case is when
$v=\left\\{K_{1},\ldots,K_{d}\right\\}\setminus\left\\{K_{i},K_{i+1}\right\\}$.
Without loss of generality, we may focus on the link of
$v=\left\\{K_{3},K_{4},\ldots,K_{d}\right\\}$. This corresponds to the coset
complex $\mathcal{X}(H,\left\\{H_{1},H_{2}\right\\})$ where

$\displaystyle H$ $\displaystyle=K_{3,4,\ldots,d}=\left\langle
e_{1,2}(at+b),e_{2,3}(at+b)\;:\;a,b\in\mathbb{F}_{p}\right\rangle,$
$\displaystyle H_{1}$ $\displaystyle=K_{2,3,4,\ldots,d}=\left\langle
e_{1,2}(at+b)\;:\;a,b\in\mathbb{F}_{p}\right\rangle,$ $\displaystyle H_{2}$
$\displaystyle=K_{1,3,4,\ldots,d}=\left\langle
e_{2,3}(at+b)\;:\;a,b\in\mathbb{F}_{p}\right\rangle.$

Hence, it suffices to focus on the first three rows and columns of these
matrices as the rest of them are constant. Written down explicitly,

$\displaystyle H$ $\displaystyle=\left\\{\begin{bmatrix}1&\ell_{1}&Q\\\
0&1&\ell_{2}\\\ 0&0&1\end{bmatrix}\ :\ \begin{matrix}\ell_{1},\ell_{2}\text{
are linear polynomials in $\mathbb{F}_{p}[t]$ }\\\ \text{and $Q$ is a
quadratic polynomial in $\mathbb{F}_{p}[t]$}\end{matrix}\right\\},$
$\displaystyle H_{1}$ $\displaystyle=\left\\{\begin{bmatrix}1&\ell&0\\\
0&1&0\\\ 0&0&1\end{bmatrix}\ :\ \ell\text{ is a linear polynomial in
$\mathbb{F}_{p}[t]$}\right\\},$ $\displaystyle H_{2}$
$\displaystyle=\left\\{\begin{bmatrix}1&0&0\\\ 0&1&\ell\\\ 0&0&1\end{bmatrix}\
:\ \ell\text{ is a linear polynomial in $\mathbb{F}_{p}[t]$}\right\\}.$

Therefore, each coset of $H_{1}$ and $H_{2}$ in $H$ has a unique
representative of the form

$M_{1}(\ell,Q):=\begin{bmatrix}1&0&Q\\\ 0&1&\ell\\\
0&0&1\end{bmatrix}\quad,\quad M_{2}(\ell,Q):=\begin{bmatrix}1&\ell&Q\\\
0&1&0\\\ 0&0&1\end{bmatrix}$

respectively, where $\ell$ is a linear polynomial and $Q$ is a quadratic
polynomial in $\mathbb{F}_{p}[t]$.

######  Lemma 5.2.

For linear polynomials $\ell_{1},\ell_{2}\in\mathbb{F}_{p}[t]$ and quadratic
polynomials $Q_{1},Q_{2}\in\mathbb{F}_{p}[t]$, we have that

$M_{1}(\ell_{1},Q_{1})H_{1}\cap
M_{2}(\ell_{2},Q_{2})H_{2}\neq\emptyset\quad\Longleftrightarrow\quad\ell_{1}\ell_{2}=Q_{1}-Q_{2}.$

###### Proof.

By Observation 3.2, the cosets have a non-empty intersection if and only if

$H_{1}H_{2}\ni
M_{1}(ell_{1},Q_{1})^{-1}M_{2}(\ell_{2},Q_{2})=\begin{bmatrix}1&0&-Q_{1}\\\
0&1&\ell_{1}\\\ 0&0&1\end{bmatrix}\begin{bmatrix}1&\ell_{2}&Q_{2}\\\ 0&1&0\\\
0&0&1\end{bmatrix}=\begin{bmatrix}1&\ell_{2}&Q_{2}-Q_{1}\\\ 0&1&-\ell_{1}\\\
0&0&1\end{bmatrix}$

which happens if and only if $(\ell_{2})(-\ell_{1})=Q_{2}-Q_{1}$ which is the
same as $Q_{1}-Q_{2}=\ell_{1}\ell_{2}$. ∎

Therefore, the $1$-dimensional link is the bipartite graph $A=(U,V,E)$ with
left and right vertices identified by pairs $(\ell,q)$ where $\ell$ and $Q$
are linear and quadratic polynomials in $\mathbb{F}_{p}[t]$ respectively, with
$(\ell_{1},Q_{1})\sim(\ell_{2},Q_{2})\Leftrightarrow\ell_{1}\ell_{2}=Q_{1}+Q_{2}$
(by associating $M_{1}(\ell,Q)$ with the tuple $(\ell,Q)$ on the left, and
$M_{2}(\ell,Q)$ with the tuple $(\ell,-Q)$ on the right).

Note that $A$ is an undirected, $p^{2}$-regular bipartite graph with $p^{5}$
vertices on each side. It suffices to show that $A$ is a good expander.

###  5.2 A related graph

The following graph is the “lines-points” or the “affine plane” graph used by
Reingold, Vadhan and Wigderson [RVW05] (as the _base graph_ in construction of
constant-degree expanders, using the zig-zag product). Let $\mathbb{F}_{q}$ be
a finite field. Consider the bipartite graph
$B_{q}=(U^{\prime},V^{\prime},E^{\prime})$ defined as follows:

$\displaystyle U^{\prime}=V^{\prime}$
$\displaystyle=\mathbb{F}_{q}\times\mathbb{F}_{q},$ $\displaystyle E^{\prime}$
$\displaystyle=\left\\{\left((a,b),(c,d)\right)\ :\ ac=b+d\right\\}.$

######  Lemma 5.3.

The $q$-regular bipartite graph $B_{q}$ is a $\frac{1}{\sqrt{q}}$-onesided-
spectral expander.

###### Proof.

Consider the graph $B_{q}^{2}$ restricted to the vertices in $U^{\prime}$. It
is easy to see that

$\text{\\# edges between $(a,b)$ and $(c,d)$}=\begin{cases}1&\text{if $a\neq
c$,}\\\ q&\text{if $a=c$ and $b=d$,}\\\ 0&\text{otherwise.}\end{cases}$

Therefore, the adjacency matrix of $B_{q}^{2}$ (restricted to $U^{\prime}$)
can be written (under a suitable order of listing vertices)

$qI_{q^{2}}+(J_{q}-I_{q})\otimes J_{q}\quad\text{(where $J_{q}$ is the
$q\times q$ matrix of $1s$)}.$

Hence the unnormalized second largest eigenvalue of $B_{q}^{2}$ is $q$ and
hence we have that the normalized second largest eigenvalue of $B_{q}$ is
$1/\sqrt{q}$. ∎

###  5.3 Relating the graph $B_{q}$ with $A$

Set $q=p^{3}$ so that $\mathbb{F}_{q}=\frac{\mathbb{F}_{p}[y]}{\mu(y)}$ for
some irreducible polynomial $\mu(y)$ of degree exactly $3$. Therefore, each
element in $\mathbb{F}_{q}$ is expressible as $a_{0}+a_{1}+a_{2}y^{2}$ for
some $a_{0},a_{1},a_{2}\in\mathbb{F}_{p}$. Thus, the graph
$B_{q}=(U^{\prime},V^{\prime},E^{\prime})$ defined above, for this setting of
$q=p^{3}$, is a $p^{3}$-regular bipartite graph with $p^{6}$ vertices on
either side.

Let
$U^{\prime\prime}=V^{\prime\prime}=\left\\{(a_{0}+a_{1}y,b_{0}+b_{1}y+b_{2}y^{2})\
:\ a_{0},a_{1},b_{0},b_{1},b_{2}\in\mathbb{F}_{p}\right\\}$, which is a subset
of $U^{\prime}$ and $V^{\prime}$, respectively, of size $p^{5}$ each.

######  Observation 5.4.

The induced subgraph of $B_{q}$ on $U^{\prime\prime},V^{\prime\prime}$ is
exactly the graph $A=(U,V,E)$ described earlier.

###### Proof.

Note that $((\ell_{1}(y),Q_{1}(y)),(\ell_{2}(y),Q_{2}(y)))\in E^{\prime}$ if
and only if

$\ell_{1}(y)\cdot\ell_{2}(y)=Q_{1}(y)+Q_{2}(y)\bmod{\mu(y)}.$

However, since the above equation has degree at most $2$, we have

$\ell_{1}(y)\cdot\ell_{2}(y)=Q_{1}(y)+Q_{2}(y)\quad\Leftrightarrow\quad\ell_{1}(y)\cdot\ell_{2}(y)=Q_{1}(y)+Q_{2}(y)\pmod{\mu(y)},$

and the first equation is exactly the adjacency condition of the graph $A$.
Hence, the induced subgraph of $B_{q}$ on $U^{\prime\prime},V^{\prime\prime}$
is indeed the graph $A$. ∎

Normally, induced subgraphs of expanders need not even be connected. However,
the following lemma shows that there are some instances when we may be able to
give non-trivial bounds on $\lambda$.

######  Lemma 5.5.

Suppose $X$ is a $d$-regular, undirected graph that is an induced subgraph of
a $D$-regular graph $Y$. Then,

$\lambda(X)\leq\frac{D\lambda(Y)}{d}.$

###### Proof.

The A.2 characterization of the second largest eigenvalue tells us that
$\lambda(X)=\max_{\mathbf{a}\perp\mathbf{1}_{|X|}}\frac{\mathbf{a}^{T}G\mathbf{a}}{d\cdot\mathbf{a}^{T}\mathbf{a}}$.
Consider an arbitrary $\mathbf{a}\in\mathbb{R}^{|X|}$ such that
$\mathbf{a}\perp\mathbf{1}_{|X|}=0$. Since $X$ is an induced subgraph of $Y$,
the vector $\mathbf{a}$ can be padded with zeroes to obtain a vector
$\mathbf{b}_{\mathbf{a}}\in\mathbb{R}^{|Y|}$ such that
$\mathbf{b}_{\mathbf{a}}\perp\mathbf{1}_{\left|Y\right|}$. Therefore,

$\lambda(X)=\max_{\mathbf{a}\perp\mathbf{1}_{|X|}}\frac{\mathbf{a}^{T}A_{X}\mathbf{a}}{\mathbf{a}^{T}\mathbf{a}}=\frac{D}{d}\cdot\max_{\mathbf{a}\perp\mathbf{1}_{|X|}}\frac{\mathbf{b}_{\mathbf{a}}^{T}A_{Y}\mathbf{b}_{\mathbf{a}}}{\mathbf{b}_{\mathbf{a}}^{T}\mathbf{b}_{\mathbf{a}}}\leq\frac{D}{d}\cdot\max_{\mathbf{b}\perp\mathbf{1}_{|Y|}}\frac{\mathbf{b}^{T}A_{Y}\mathbf{b}}{\mathbf{b}^{T}\mathbf{b}}=\frac{D\lambda(Y)}{d}\enspace.\qed$

######  Corollary 5.6.

The graph $A(U,V,E)$ corresponding to the $1$-dimensional links of
$\mathcal{X}(G,\left\\{K_{1},\ldots,K_{d}\right\\})$ is an onesided
$\left(\frac{1}{\sqrt{p}}\right)$-spectral expander.

###### Proof.

The graph $B_{p^{3}}$ is a bipartite, $p^{3}$-regular graph with
$\lambda(B_{p^{3}})\leq\frac{1}{p^{3/2}}$ and $A(U,V,E)$ is a $p^{2}$-regular
graph that is an induced subgraph of $B_{p^{3}}$. Hence, by Lemma 5.5,

$\lambda(A)\leq\frac{p^{3}\cdot(1/p^{3/2})}{p^{2}}=\frac{1}{\sqrt{p}}.\qed$

### The final expansion bounds

From the corollary above, we obtain the following theorem of Kaufman and
Oppenheim.

######  Theorem 5.7 ([KO18]).

For $p>(d-2)^{2}$, the $(d-1)$-dimensional coset complex
$\mathcal{X}(G,\left\\{K_{1},\ldots,K_{d}\right\\})$ is a
$\frac{1}{\sqrt{p}-(d-2)}$-onesided-spectral HDX.

###### Proof.

Follows directly from Section 2 that
$\mathcal{X}(G,\left\\{K_{1},\ldots,K_{d}\right\\})$ is a $\gamma$-(onesided)
local spectral expander for

$\gamma\leq\frac{\nicefrac{{1}}{{\sqrt{p}}}}{1-(d-2)(\nicefrac{{1}}{{\sqrt{p}}})}=\frac{1}{\sqrt{p}-(d-2)}.\qed$

##### Constructing two-sided HDXs and standard expanders graphs:

The $(d-1)$-dimensional coset complex
$\mathcal{X}(G,\left\\{K_{1},\ldots,K_{d}\right\\})$ is a not a two-sided HDX
as the 1-skeleton of the links of the faces in $\mathcal{X}(d-3)$ are
bipartite. However, if we restrict attention to the $k$-skeleton of
$\mathcal{X}$ for some $k<d-1$ then we can bound the least eigenvalue using
the descent theorem for least eigenvalue (Theorem A.4(2)). This is summarized
in the following corollary.

######  Corollary 5.8.

For $p>(d-2)^{2}$ and any $1\leq k<d$ the $k$-skeleton of the
$(d-1)$-dimensional coset complex
$\mathcal{X}(G,\left\\{K_{1},\ldots,K_{d}\right\\})$ is a
$\max\left\\{\frac{1}{\sqrt{p}-(d-2)}\;,\;\frac{1}{d-k}\right\\}$-two-sided
spectral HDX.

In particular, if we set $k=1$ in the above corollary, we get a standard
$\max\left\\{\frac{1}{\sqrt{p}-(d-2)}\;,\;\frac{1}{d-1}\right\\}$-two-sided
spectral expander. This graph is a $d$-partite graph and hence its least
eigenvalue is at most $\nicefrac{{-1}}{{(d-1)}}$, while the above argument
shows that it is least (and hence equal to) $\nicefrac{{-1}}{{(d-1)}}$.

Thus, this not only yields an elementary construction and proof of onesided-
spectral HDXs (Theorem 5.7), but also one of standard spectral expander
(Corollary 5.8).

## References

  * [Dik19] Yotam Dikstein.  _Agreement Theorems and Fourier Decomposition on High Dimensional Expanders_.  Master’s thesis, Weizmann Institute of Science, Israel, 2019.
  * [Gar73] Howard Garland.  _$p$ -adic curvature and the cohomology of discrete subgroups of $p$-adic groups_.  Ann. of Math., 97(3):375–423, 1973.  doi:10.2307/1970829.
  * [KO18] Tali Kaufman and Izhar Oppenheim.  _Construction of new local spectral high dimensional expanders_.  In _Proc. $50$th ACM Symp. on Theory of Computing (STOC)_, pages 773–786. 2018.  doi:10.1145/3188745.3188782.
  * [LPS88] Alexander Lubotzky, Ralph Phillips, and Peter Sarnak.  _Ramanujan graphs_.  Combinatorica, 8(3):261–277, 1988.  doi:10.1007/BF02126799.
  * [LSV05a] Alexander Lubotzky, Beth Samuels, and Uzi Vishne.  _Explicit constructions of Ramanujan complexes of type $\tilde{A_{d}}$_.  European J. Combin., 26(6):965––993, 2005.  doi:10.1016/j.ejc.2004.06.007.
  * [LSV05b] ———.  _Ramanujan complexes of type $\tilde{A_{d}}$_.  Israel J. Math., 149(1):267–299, 2005.  doi:10.1007/BF02772543.
  * [Opp18] Izhar Oppenheim.  _Local spectral expansion approach to high dimensional expanders part I: Descent of spectral gaps_.  Discrete Comput. Geom., 59(2):293–330, 2018.  doi:10.1007/s00454-017-9948-x.
  * [RVW05] Omer Reingold, Salil Vadhan, and Avi Wigderson.  _Entropy waves, the zig-zag graph product, and new constant-degree expanders_.  Annals of Math (2), 155(1):157–187, 2005.  (Preliminary version in 41st FOCS, 2000).  doi:10.2307/3062153.

##  Appendix A Proof of the Descent Theorem

For the sake of completeness, we present the proof of Section 2 that asserts
that proving local expansion for the maximal faces is sufficient to obtain
expansion of any link. This exposition is essentially from the lecture notes
by Dikstein [Dik19].

Let $(X,w)$ be a weighted $d$-dimensional simplicial complex. Let
$\mu_{d}=w|_{X(d)}$ be the distribution on the set $X(d)$ of $(d+1)$-sized
faces. This distribution induces distributions $\mu_{i}$ on $X(i)$ in the
natural way.

For two functions $f,g:X(0)\rightarrow\mathbb{R}$, define their _inner-
product_ $\left\langle
f,g\right\rangle_{X}=\operatornamewithlimits{\mathbb{E}}_{u\sim\mu_{0}}[f(u)g(u)]$.
We will drop the subscript $X$ if it is clear from context. Note that, by the
definition of $\mu_{1}$, sampling $u$ according to $\mu_{0}$ can be
equivalently achieved by sampling an edge $(u,v)$ according ot $\mu_{1}$ and
returning one of the points. Therefore,

(A.1) $\left\langle
f,g\right\rangle_{X}=\operatornamewithlimits{\mathbb{E}}_{u\sim\mu_{0}}[f(u)g(u)]=\operatornamewithlimits{\mathbb{E}}_{\left\\{u,v\right\\}\sim\mu_{1}}[f(u)g(u)]=\operatornamewithlimits{\mathbb{E}}_{v\sim\mu_{0}}\operatornamewithlimits{\mathbb{E}}_{u\in
X_{v}(0)}[f(u)g(u)]=\operatornamewithlimits{\mathbb{E}}_{v\sim\mu_{0}}[\left\langle
f_{v},g_{v}\right\rangle_{X_{v}}],$

where $f_{v},g_{v}:X_{v}(0)\rightarrow\mathbb{R}$, the restriction to the link
of $v$.

Define the _adjacency operator_ $A$ that, on a function
$f:X(0)\rightarrow\mathbb{R}$ on vertices returns another function $Af$ on
vertices defined via

$Af(v)=\operatornamewithlimits{\mathbb{E}}_{u\sim v}[f(u)].$

In other words, $A$ _averages_ $f$ over neighbours. Furthermore, $A$ is self-
adjoint with respect to the above inner product, i.e, $\left\langle
Af,g\right\rangle=\left\langle f,Ag\right\rangle$. Hence, it has $n$ real
eigenvalues and an orthonormal set of eigenvectors. Clearly
$A\mathbb{1}=\mathbb{1}$; the constant $1$ function is an eigenvector for this
operator (in fact, it is an eigenvector corresponding to the largest
eigenvalue 1). The remaining eigenvalues are characterized by the A.2.

######  Courant-Fischer Theorem A.2.

Let $A\in\mathbb{R}^{n\times n}$ be a $n\times n$ matrix over the reals that
is self-adjoint with respect to some inner product
$\left\langle\cdot,\cdot\right\rangle:\mathbb{R}^{n}\times\mathbb{R}^{n}\to\mathbb{R}$.
Then $A$ has $n$ real eigenvalues $\lambda_{1}\geq\cdots\geq\lambda_{n}$ which
have the following characterization.

$\lambda_{i}=\max_{V\colon\dim V=i}\min_{x\in V}\frac{\left\langle
x,Ax\right\rangle}{\left\langle x,x\right\rangle}=\min_{V\colon\dim
V=n-i+1}\max_{x\in V}\frac{\left\langle x,Ax\right\rangle}{\left\langle
x,x\right\rangle}.$

Similar to Equation A.1, we have

$\displaystyle\left\langle Af,g\right\rangle_{X}$
$\displaystyle=\operatornamewithlimits{\mathbb{E}}_{(u,w)\sim\mu_{1}}[f(u)g(w)]=\operatornamewithlimits{\mathbb{E}}_{(u,v,w)\sim\mu_{2}}[f(u)g(w)]$
$\displaystyle=\operatornamewithlimits{\mathbb{E}}_{v\sim\mu_{0}}\left[\operatornamewithlimits{\mathbb{E}}_{(u,w)\in
X_{v}(1)}[f(u)g(w)]\right]$ (A.3)
$\displaystyle=\operatornamewithlimits{\mathbb{E}}_{v\sim\mu_{0}}\left[\left\langle
A_{v}f_{v},g_{v}\right\rangle_{X_{v}}\right]$

where $A_{v}$ denotes the adjacency operator restricted to the link $X_{v}$.

With the above notation, we can now state the theorem we wish to prove. It
suffices to prove the theorem in the case of $d=3$ as we can obtain Section 2
by induction.

######  Theorem A.4.

Suppose $(X,w)$ is weighted $2$-dimensional simplicial complex. Then, we have
the following two implications:

  1. 1.

Suppose the 1-skeleton of $X$ is connected and for every vertex $v\in X(0)$,
if $\left\langle A_{v}f,f\right\rangle\leq\lambda\left\langle
f,f\right\rangle$ for all $f\colon X_{v}(0)\rightarrow\mathbb{R}$ with
$f\perp\mathbb{1}_{X_{v}}$. Then, for any $g\colon X(0)\rightarrow\mathbb{R}$
with $g\perp\mathbb{1}_{X}$, we have $\left\langle
Ag,g\right\rangle\leq\gamma\left\langle g,g\right\rangle$ where
$\gamma\leq\frac{\lambda}{1-\lambda}$.

  2. 2.

Suppose the 1-skeleton of $X$ is non-empty and for every vertex $v\in X(0)$,
if $\left\langle A_{v}f,f\right\rangle\geq\eta\left\langle f,f\right\rangle$
for all $f\colon X_{v}(0)\rightarrow\mathbb{R}$. Then, for any $g\colon
X(0)\rightarrow\mathbb{R}$, we have $\left\langle
Ag,g\right\rangle\geq\gamma\left\langle g,g\right\rangle$ where
$\gamma\geq\frac{\eta}{1-\eta}$.

Before we see a proof of this, let us see how Section 2 follows from this.

######  Descent Theorem A.4 (Section 2 restated).

Suppose $(X,w)$ is a non-empty $d$-dimensional weighted simplicial complex
with the following properties.

  * •

The $1$-skeleton of every link is connected.

  * •

For all $v\in X(d-2)$, the link $(X_{v},w_{v})$ is a
$\lambda$-(onesided)-spectral expander. I.e., there is a $\lambda>0$ such
that, for every $v\in X(d-2)$ and every $g:X_{v}(0)\rightarrow\mathbb{R}$ with
$g\perp\mathbb{1}$, we have

$\left\langle A_{v}g,g\right\rangle\leq\lambda\left\langle g,g\right\rangle.$

Then, $(X,w)$ is a $\gamma$-(onesided) local spectral expander for
$\gamma\leq\frac{\lambda}{1-(d-1)\lambda}$. That is, for any $v\in
X(-1)\cup\cdots\cup X(d-2)$ and every $g:X_{v}(0)\rightarrow\mathbb{R}$ with
$g\perp\mathbb{1}$, we have $\left\langle
A_{v}g,g\right\rangle\leq\gamma\left\langle g,g\right\rangle$.

Additionally, if we also know that there is a $\eta\in[-1,0)$ such that, for
every $v\in X(d-2)$ and every $g:X_{v}(0)\rightarrow\mathbb{R}$, we have
$\left\langle A_{v}g,g\right\rangle\geq\eta\left\langle g,g\right\rangle$.
Then, for any $v\in X(-1)\cup\cdots\cup X(d-2)$ and every
$g:X_{v}(0)\rightarrow\mathbb{R}$, we have that $X$ is a $\gamma$-(two-sided)
local spectral expander with

$\gamma\leq\max\left(\frac{\lambda}{1-(d-1)\lambda},\left|\frac{\eta}{1-(d-1)\eta}\right|\right).$

###### Proof.

For any $i\leq d-2$, let

$\lambda_{i}=\min_{v\in
X(i)}\max_{\begin{subarray}{c}g:X_{v}(0)\rightarrow\mathbb{R}\\\
g\perp\mathbb{1}\end{subarray}}\frac{\left\langle
A_{v}g,g\right\rangle}{\left\langle g,g\right\rangle},$

the smallest local expansion with respect to $X(i)$. From repeated
applications of Theorem A.4,

$\lambda_{-1}\leq\frac{\lambda_{0}}{1-\lambda_{0}}\leq\frac{\lambda_{1}/(1-\lambda_{1})}{1-(\lambda_{1}/(1-\lambda_{1}))}=\frac{\lambda_{1}}{1-2\lambda_{1}}\leq\cdots\leq\frac{\lambda_{d-2}}{1-(d-1)\lambda_{d-2}}$

which eventually completes the proof for onesided local spectral expansion.

For two-sided local spectral expansion, we would also have to show that all
local eigenvalues are bounded away from $-1$. One again, let $\eta_{i}$ be
such that

$\eta_{i}=\max_{v\in
X(i)}\min_{\begin{subarray}{c}g:X_{v}(0)\rightarrow\mathbb{R}\\\
g\perp\mathbb{1}\end{subarray}}\frac{\left\langle
A_{v}g,g\right\rangle}{\left\langle g,g\right\rangle}.$

By repeated applications of Theorem A.4 (2), we obtain

$\eta_{-1}\geq\frac{\eta_{0}}{1-\eta_{0}}\geq\frac{\eta_{1}/(1-\eta_{1})}{1-(\eta_{1}/(1-\eta_{1}))}=\frac{\eta_{1}}{1-2\eta_{1}}\geq\cdots\geq\frac{\eta_{d-2}}{1-(d-1)\eta_{d-2}}$

Together, we have that $X$ is a $\gamma$-(two-sided) local spectral expander
for

$\gamma=\max\left(\frac{\lambda}{1-(d-1)\lambda},\left|\frac{\eta}{1-(d-1)\eta}\right|\right).\qed$

###### Proof of Theorem A.4.

Let $g$ be an eigenvector that satisfies $\left\langle g,g\right\rangle=1$ and
$g\perp\mathbb{1}_{X}$ that maximises (or minimises) $\left\langle
Ag,g\right\rangle$, and $\gamma=\left\langle Ag,g\right\rangle$ be the
extremal value. In particular, $Ag=\gamma\cdot g$. From (A.3) we have
$\gamma=\left\langle
Ag,g\right\rangle=\operatornamewithlimits{\mathbb{E}}_{v}\left[\left\langle
A_{v}g_{v},g_{v}\right\rangle\right]$.

Even though $g\perp\mathbb{1}_{X}$, the _local_ component $g_{v}$ need not be
perpendicular to $\mathbb{1}_{X_{v}}$. Hence, let us write
$g_{v}=\alpha_{v}\mathbb{1}_{X_{v}}+g_{v}^{\perp}$ where
$g_{v}^{\perp}\perp\mathbb{1}_{X_{v}}$; we shall dropping the subscript from
$\mathbb{1}_{X_{v}}$ for the sake of brevity as the length of the vector will
be clear from context. Note that $\alpha_{v}=\left\langle
g_{v},\mathbb{1}\right\rangle=\operatornamewithlimits{\mathbb{E}}_{w\in
X_{v}(0)}[g_{v}]=Ag(v)$. Therefore,
$\operatornamewithlimits{\mathbb{E}}_{v}[\alpha_{v}^{2}]=\left\langle
Ag,Ag\right\rangle=\gamma^{2}$.

(A.5) $\displaystyle\gamma=\left\langle Ag,g\right\rangle$
$\displaystyle=\operatornamewithlimits{\mathbb{E}}_{v}\left[\left\langle
A_{v}g_{v},g_{v}\right\rangle\right]=\operatornamewithlimits{\mathbb{E}}_{v}\left[\alpha_{v}^{2}+\left\langle
A_{v}g_{v}^{\perp},g_{v}^{\perp}\right\rangle\right]$

We shall now focus on the proof of Theorem A.4 (1). The other direction is
exactly identical with the inequality flipped.

In the case of Theorem A.4 (1), where we are given $\left\langle
A_{v}g_{v}^{\perp},g_{v}^{\perp}\right\rangle\leq\lambda\left\langle
g_{v}^{\perp},g_{v}^{\perp}\right\rangle$ for all $v\in X(0)$, we have

$\displaystyle\gamma=\operatornamewithlimits{\mathbb{E}}_{v}\left[\alpha_{v}^{2}+\left\langle
A_{v}g_{v}^{\perp},g_{v}^{\perp}\right\rangle\right]$
$\displaystyle\leq\operatornamewithlimits{\mathbb{E}}_{v}\left[\alpha_{v}^{2}+\lambda\left\langle
g_{v}^{\perp},g_{v}^{\perp}\right\rangle\right]$
$\displaystyle=\operatornamewithlimits{\mathbb{E}}_{v}\left[(1-\lambda)\alpha_{v}^{2}+\lambda\left\langle
g_{v},g_{v}\right\rangle\right]$
$\displaystyle=(1-\lambda)\gamma^{2}+\lambda.$
$\displaystyle\implies\gamma(1-\gamma)$
$\displaystyle\leq\lambda(1-\gamma^{2})$ $\displaystyle\implies\gamma$
$\displaystyle\leq\lambda(1+\gamma)$ (connected, thus $\gamma<1$)
$\displaystyle\implies\gamma$ $\displaystyle\leq\frac{\lambda}{1-\lambda}.$

In the case of Theorem A.4 (2), where we are given $\left\langle
A_{v}g_{v}^{\perp},g_{v}^{\perp}\right\rangle\geq\eta\left\langle
g_{v}^{\perp},g_{v}^{\perp}\right\rangle$ for all $v\in X(0)$, the same
argument yields

$\displaystyle\gamma=\operatornamewithlimits{\mathbb{E}}_{v}\left[\alpha_{v}^{2}+\left\langle
A_{v}g_{v}^{\perp},g_{v}^{\perp}\right\rangle\right]$
$\displaystyle\geq\operatornamewithlimits{\mathbb{E}}_{v}\left[\alpha_{v}^{2}+\eta\left\langle
g_{v}^{\perp},g_{v}^{\perp}\right\rangle\right]=(1-\eta)\gamma^{2}+\eta$
$\displaystyle\implies\gamma$ $\displaystyle\geq\frac{\eta}{1-\eta}\qed$

##  Appendix B Primer on Group Theory

In this section, for completeness, we shall note the basic definitions and
properties of group that is used in this exposition.

######  Definition B.1 (Groups and subgroups).

A set of elements $G$ equipped with a binary operation $\star:G\times
G\rightarrow G$ is said to be a _group_ that satisfies the following
properties:

Associativity:

For all $g_{1},g_{2},g_{3}\in G$, we have $\left(g_{1}\star g_{2}\right)\star
g_{3}=g_{1}\star\left(g_{2}\star g_{3}\right)$.

Identity:

There exists an _identity_ element $\mathrm{id}\in G$ such that, for all $g\in
G$, we have $g\star\mathrm{id}=\mathrm{id}\star g=g$.

Inverses:

For every element $g\in G$, there is an element $g^{-1}\in G$ such that
$g\star g^{-1}=g^{-1}\star g=\mathrm{id}$.

Often the binary operation $\star$ is omitted and products just expressed as
concatenation of elements.

A subset $H\subseteq G$ is said to be a _subgroup_ of $G$ if $H$ the binary
operation $\star$ restricted to $H$ satisfies the above three properties
(including the fact that $h_{1}\star h_{2}\in H$ for all $h_{1},h_{2}\in H$).

Suppose $H,K$ are subgroups of $G$, would often consider the product $HK$ (or
$H\star K$) which refers to the set $\left\\{h\star k\ :\ h\in H\;,\;k\in
K\right\\}$. It is worth stressing that $HK$ _need not_ be a subgroup of $G$
and the above just refers to a set of elements that can be expressed as
(ordered) product of an element in $H$ and an element in $G$.

For an arbitrary set $S$ of $G$, we will define $\left\langle S\right\rangle$
as the smallest subgroup of $G$ that contains the set $S$. This is also
referred to as the _group generated_ by $S$.

In general, the binary operation $\star$ is order dependent. Groups where
$g_{1}\star g_{2}=g_{2}\star g_{1}$ for all $g_{1},g_{2}\in G$ is said to be a
_commutative_ or _Abelian_ group. The following notion of _commutators_ (and
_commutator subgroups_) is a way to measure _how non-commutative_ a group $G$
is.

######  Definition B.2 (Commutators).

For a pair of elements $g,h\in G$, we shall define the _commutator_ of $g,h$
(denoted by $[g,h]$) as

$[g,h]:=g^{-1}h^{-1}gh.$

The _commutator subgroup_ of $G$, denoted by $[G,G]$ is _group generated by
all commutators_. That is,

$[G,G]:=\left\langle\left\\{[g,h]\ :\ g,h\in G\right\\}\right\rangle.$

Note that if $G$ is Abelian, then $[G,G]=\left\\{\mathrm{id}\right\\}$. As
mentioned earlier, the commutator subgroup can be thought of as a way of
describing how non-Abelian a group is. In fact, the commutator subgroup of $G$
is the smallest _normal_ subgroup $H$ of $G$ such that the _quotient_ $G/H$ is
Abelian.