# Stability of Homomorphisms, Coverings and Cocycles II:
Examples, Applications and Open problems

Michael Chapman  Michael Chapman Courant Institute of Mathematical Sciences
New York University, 251 Mercer St, New York, NY 10012, USA<EMAIL_ADDRESS>and  Alexander Lubotzky  Alexander Lubotzky Weizmann institute of Science
Rehovot, Israel<EMAIL_ADDRESS>
###### Abstract.

Coboundary expansion (with $\mathbb{F}_{2}$ coefficients), and variations on
it, have been the focus of intensive research in the last two decades. It was
used to study random complexes, property testing, and above all Gromov’s
topological overlapping property.

In part I of this paper, we extended the notion of coboundary expansion (and
its variations) to cochains with permutation coefficients, equipped with the
normalized Hamming distance. We showed that this gives a unified language for
studying covering stability of complexes, as well as stability of group
homomorphisms — a topic that drew a lot of attention in recent years.

In this part, we extend the theory to the permutation coefficients setting.
This gives some new results, even for $\mathbb{F}_{2}$ coefficients, opens
several new directions of research, and suggests a pattern to proving the
existence of non-sofic groups. Along the way, we solve the dimension $2$ case
of a problem of Gromov, exhibiting a family of bounded degree coboundary
expanders with $\mathbb{F}_{2}$ coefficients.

##  1\. Introduction

In Part I of this paper [CL_part1], we studied three stability problems — that
of group homomorphisms, coverings of polygonal complexes, and cocycles with
permutation coefficients — and proved they are all equivalent. A main
contribution of Part I was the definition of the _cocycle_ (and _coboundary_)
_Cheeger constant_ of a $2$-dimensional (polygonal) complex with coefficients
in a metric group $\Gamma$.111The commonly used definition (cf. [Dinur-
Meshulam, dikstein2023coboundary]) of _cocycle expansion_ (usually misnomed
_cosystolic expansion_) with coefficients in a general group agrees with our
definition when one assumes the group is equipped with the discrete distance
on it. Namely, every non-equal pair of elements in the coefficient group is
$1$ distance apart. Thus, our definition is a generalization of these more
classical notions. Specifically, we focused on the case where $\Gamma$ is a
permutation group equipped with the normalized Hamming distance. The current
paper further discusses this notion.

Coboundary expansion with $\mathbb{F}_{2}$ coefficients was intensively
studied in the last two decades [linial_meshulam2006homological,
gromov2010singularities, kaufman2014high, kaufman2016isoperimetric,
evra2016bounded, dikstein2023coboundary]. It was originally defined,
independently, by Linial–Meshulam [linial_meshulam2006homological] and Gromov
[gromov2010singularities]. Linial–Meshulam defined it in order to study the
cohomology of random $2$-dimensional simplicial complexes, while Gromov’s goal
was to understand topological overlapping. In a companion paper
[CL_stability_Random_complexes], the Linial–Meshulam approach is taken, to
study the cocycle and coboundary expansion of random simplicial complexes with
permutation coefficients. In this paper, we follow the developments of Gromov
[gromov2010singularities] and his followers, substituting again the
$\mathbb{F}_{2}$ coefficients with permutations.222As ${\rm
Sym}(2)\cong\mathbb{F}_{2}$, the Cheeger constants with $\mathbb{F}_{2}$
coefficients of a given complex are bounded from below by its Cheeger
constants with permutation coefficients, which provides further motivation to
study the latter. To that end, we first recall the highlights of the theory in
the $\mathbb{F}_{2}$ setup, and only then describe the permutation setup,
following with our contributions and challenges.

### Topological overlapping, Coboundary expansion, Cocycle expansion and Large
cosystols

#### The $\mathbb{F}_{2}$ coefficients setup

Let $\mathcal{X}$ be a simplicial complex of dimension $d$,
$\overrightarrow{\mathcal{X}}(i)$ the set of oriented $i$-cells,
$C^{i}(\mathcal{X},\mathbb{F}_{2})=\\{f\colon\overrightarrow{\mathcal{X}}(i)\to\mathbb{F}_{2}\\}$
the $i$-cochains of $\mathcal{X}$ with $\mathbb{F}_{2}$ coefficients, and
$\delta=\delta_{i}\colon C^{i}(\mathcal{X},\mathbb{F}_{2})\to
C^{i+1}(\mathcal{X},\mathbb{F}_{2})$ the coboundary map. Given a probability
distribution $\mu_{i}$ over $\overrightarrow{\mathcal{X}}(i)$, we can define a
notion of distance between $i$-cochains by
$d(\alpha,\beta)=\operatorname*{\mathbb{P}}_{\sigma\sim\mu_{i}}[\alpha(\sigma)\neq\beta(\sigma)],$
and thus a norm $\|\alpha\|=d(\alpha,{\bf 0})$, where ${\bf 0}$ is the
constant $0$ cochain. We assume all our simplicial complexes are given with
probability distributions $\mu_{i}$ on their oriented $i$-cells. Let
$B^{i}(\mathcal{X},\mathbb{F}_{2})=\textrm{Im}\delta_{i-1}\subseteq
C^{i}(\mathcal{X},\mathbb{F}_{2})$ be the $i$-coboundaries of $\mathcal{X}$
with $\mathbb{F}_{2}$ coefficients and
$Z^{i}(\mathcal{X},\mathbb{F}_{2})=\textrm{Ker}\delta_{i}\subseteq
C^{i}(\mathcal{X},\mathbb{F}_{2})$ the $i$-cocycles.

For $0\leq i<d$, the $i$-coboundary Cheeger constant of $\mathcal{X}$ with
$\mathbb{F}_{2}$ coefficients is

(1.1)
$h^{B}_{i}(\mathcal{X},\mathbb{F}_{2})=\inf\mathopen{}\mathclose{{}\left\\{\frac{\|\delta\alpha\|}{d(\alpha,B^{i}(\mathcal{X},\mathbb{F}_{2}))}\
\middle|\ \alpha\in C^{i}(\mathcal{X},\mathbb{F}_{2})\setminus
B^{i}(\mathcal{X},\mathbb{F}_{2})}\right\\}.$

The $i$-cocycle Cheeger constant of $\mathcal{X}$ with $\mathbb{F}_{2}$
coefficients is

(1.2)
$h_{i}(\mathcal{X},\mathbb{F}_{2})=\inf\mathopen{}\mathclose{{}\left\\{\frac{\|\delta\alpha\|}{d(\alpha,Z^{i}(\mathcal{X},\mathbb{F}_{2}))}\
\middle|\ \alpha\in C^{i}(\mathcal{X},\mathbb{F}_{2})\setminus
Z^{i}(\mathcal{X},\mathbb{F}_{2})}\right\\}.$

The $i$-cosystol of $\mathcal{X}$ with $\mathbb{F}_{2}$ coefficients is

(1.3) $CoSyst_{i}(\mathcal{X},\mathbb{F}_{2})=\inf\\{\|\alpha\|\mid\alpha\in
Z^{i}(\mathcal{X},\mathbb{F}_{2})\setminus
B^{i}(\mathcal{X},\mathbb{F}_{2})\\}.$

Gromov proved in [gromov2010singularities] that a family
$\mathfrak{X}=\\{\mathcal{X}\\}$ of (finite, locally sparse) $d$-dimensional
simplicial complexes satisfy the topological overlapping property — i.e., for
every continuous map $f\colon\mathcal{X}\to\mathbb{R}^{d}$, there exists a
point $p\in\mathbb{R}^{d}$ which is covered via $f$ by a constant fraction of
its $d$-cells333The constant fraction should be uniform on $\mathfrak{X}$,
namely independent of the specific $\mathcal{X}$. — if for every $0\leq i\leq
d-1$ there is a uniform lower bound on their $i$-coboundary Cheeger constants
with $\mathbb{F}_{2}$ coefficients. He used this implication to prove the
following:

######  Theorem 1.1 ([gromov2010singularities], see also
[linial_meshulam2006homological]).

The family of complete $d$-dimensional complexes have a uniform lower bound on
their $i$-coboundary Cheeger constants with $\mathbb{F}_{2}$ coefficients.
Thus, they satisfy the topological overlapping property.

Similarly, $d$-dimensional spherical buildings have a uniform lower bound on
their coboundary Cheeger constants with $\mathbb{F}_{2}$ coefficients (see
[LMM_2016expansion_building_like]), and therefore also satisfy the topological
overlapping property.

Having the topological overlapping property is a high dimensional version of
being a family of expander graphs. In this spirit, we use the notions of
_coboundary expander, cocycle expander_ and _toppological expander_ to
indicate that a (family of) complex(es) has a bounded from zero coboundary
Cheeger constant, cocycle Cheeger constant or satisfy the topological
overlapping property, respectively. In current terminology, Gromov’s result
says that $\mathbb{F}_{2}$-coboundary expanders are topological expanders.

For graphs, the main difficulty is finding families of bounded degree
expanders. Motivated by this analogy, Gromov posed the following problems:

######  Problem 1.2.

For $d\geq 2$, are there families of $d$-dimensional bounded degree
topological expanders?

######  Problem 1.3.

For $d\geq 2$, are there families of $d$-dimensional bounded degree
$\mathbb{F}_{2}$-coboundary expanders?

Problem 1.2 was resolved in full — first for $d=2$ in
[kaufman2016isoperimetric], and later for all dimensions in [evra2016bounded]
— without resolving Problem 1.3. This was done due to the following
generalization of Gromov’s implication from coboundary expansion to
topological overlapping:

######  Theorem 1.4 ([DKW_cosystolic_exp_implies_overlap]).

Fix $d\geq 2$, and $\mathfrak{X}=\\{\mathcal{X}\\}$ a family of (finite,
locally sparse) $d$-dimensional simplicial complexes. Assume both the cocycle
Cheeger constants $h_{i}(\mathcal{X},\mathbb{F}_{2})$ and cosystols
$CoSyst_{i}(\mathcal{X},\mathbb{F}_{2})$ of all $\mathcal{X}\in\mathfrak{X}$
in all dimensions are uniformly bounded away from zero. Then the family
$\mathfrak{X}$ satisfies the topological overlapping property.

The approach of Kaufman–Kazhdan–Lubotzky in [kaufman2016isoperimetric] and
Evra–Kaufman in [evra2016bounded] was to prove that the $d$-skeleton of
$d+1$-dimensional _Ramanujan Complexes_ (see [LSV2005ramanujan]) satisfy the
conditions of Theorem 1.4. Let us explain this approach with more details (and
in slightly greater generality): Let $\mathcal{B}$ be the Bruhat–Tits building
of a $p$-adic simple Lie group $G$ of rank $d+1$. Let $\Gamma$ be a cocompact
lattice of $G$. On the one hand,
$\mathcal{X}={}_{\Gamma}\setminus^{\mathcal{B}}$ can have a vanishing
coboundary Cheeger constant (see [lubotzky1987finite]), and thus a family of
such does not resolve Problem 1.3. On the other hand, Evra–Kaufman proved the
following:

######  Theorem 1.5 ([evra2016bounded]).

Fix $d\in\mathbb{N}$ and $G$ a $p$-adic simple Lie group of rank $d+1$. If $p$
is sufficiently large, and $\\{\Gamma\\}$ is the family of cocompact lattices
of $G$, then the $d$-skeletons of
$\mathfrak{X}=\mathopen{}\mathclose{{}\left\\{{}_{\Gamma}\setminus^{\mathcal{B}}}\right\\}$
have cocycle Cheeger constants and cosystols bounded away from zero (in all
dimensions in a uniform manner), thus satisfying the conditions of Theorem
1.4. Hence, it forms a family of topological expanders.

#### The permutation coefficients setup and our contributions

By swapping in (1.1), (1.2) and (1.3) the coefficients $\mathbb{F}_{2}$ with
${\rm Sym}=\bigsqcup{\rm Sym}(n)$ — equipped with the normalized Hamming
distance with errors (see (2.9)) — we get the notions of coboundary expansion,
cocycle expansion and large cosystols444Actually, the definition of
$CoSyst_{1}(\mathcal{X},{\rm Sym})$ requires some special care, and is not
just plugging ${\rm Sym}$ instead of $\mathbb{F}_{2}$ in the definition. See
(4.1) for the formal definition. in permutations. Since permutation groups are
non-abelian, we define these notions only in dimensions $0$ and $1$. In the
first part of this paper [CL_part1], we related the Cheeger constants with
permutations to well known problems in groups theory and combinatorial
topology, i.e., pointwise group stability and rigidity of covering spaces. The
goal of this paper is to mimic the developments made in the $\mathbb{F}_{2}$
setup for permutation coefficients. In Section 3, we follow Gromov and prove
an analogue of Theorem 1.1:

######  Theorem 1.6.

Complete complexes and spherical buildings are coboundary expanders with
permutation coefficients.

We further show in this section that every (finitely presented) group $\Gamma$
has a presentation with an arbitrarily small cocycle Cheeger constant in
permutations. In Section 4, we study cosystols with permutation coefficients.
We specifically show the following:

######  Theorem 1.7.

Let $\mathcal{X}$ be a finite polygonal complex.555A polygonal complex is a
combinatorial version of a finite $2$-dimensional CW complex. See Section 2
for a formal definition.

  1. (1)

If the fundamental group $\pi_{1}(\mathcal{X},*)$ is residually finite and
amenable, then for every $\varepsilon>0$ there is a finite covering
$\mathcal{Y}$ of $\mathcal{X}$ with $CoSyst_{1}(\mathcal{Y},{\rm
Sym})<\varepsilon$.

  2. (2)

If the fundamental group $\pi_{1}(\mathcal{X},*)$ has property $(\tau)$666See
Section 4.3 or [lubotzky1994discrete] for a definition. — in particular, if it
has Kazhdan property (T) — then, for every finite connected covering
$\mathcal{Y}$ of $\mathcal{X}$ we have $CoSyst_{1}(\mathcal{Y},{\rm
Sym})\geq\kappa,$ where $\kappa>0$ depends only on $\mathcal{X}$.

  3. (3)

By applying Garland’s method, we can (again) deduce that for every finite
connected covering $\mathcal{Y}$ of $\mathcal{X}$ we have
$CoSyst_{1}(\mathcal{Y},{\rm Sym})\geq\kappa$, where $\kappa>0$ depends only
on the local spectral expansion777See Section 4.4 or
[Dikstein_lecture_notes_trickling_down] for a formal definition. of
$\mathcal{X}$.

Note that the local spectral expansion of a simplicial complex $\mathcal{X}$
which is covered by a Bruhat–Tits building $\mathcal{B}$ of a $p$-adic Lie
group $G$ depends only on $\mathcal{B}$. Hence, the bound guaranteed by clause
$(3)$ of Theorem 1.7 is valid uniformly for all the finite quotients of
$\mathcal{B}$, and not merely to the covers of a specific quotient
$\mathcal{X}$.

Having large cosystols with permutation coefficients implies large cosystols
with $\mathbb{F}_{2}$ coefficients. Clauses $(2)$ and $(3)$ of Theorem 1.7 are
new even for $\mathbb{F}_{2}$ coefficients, and provide a new (and simple)
method for proving that the complexes used in [kaufman2016isoperimetric] and
[evra2016bounded] have large cosystols (in dimension $1$).

In Section 5, we provide a solution to Problem 1.3 for the $d=2$ case (it
remains open for $d\geq 3$). Namely, we prove that:

######  Theorem 1.8.

There exists an infinite family of bounded degree $2$-dimensional coboundary
expanders with $\mathbb{F}_{2}$ coefficients.

Though not using permutation coefficients, and thus deviating from the main
theme of this paper, we provide here this construction for two reasons: First,
no such construction can be found in the literature. Second, as discussed in
Section 6.1 —

######  Theorem 1.9.

If the family of complexes which we construct in Section 5 are cocycle
expanders in permutations, then there exist non-sofic gropus.888Actually, any
cocycle stability rate in dimension $1$ with permutation coefficients for our
construction will imply the existence of non-sofic groups. See Section 6.1.

Finding a non-sofic group is one of the most outstanding problems in group
theory. The hope is that the methods already developed for the
$\mathbb{F}_{2}$ setup [kaufman2016isoperimetric, evra2016bounded,
dikstein2023coboundary] can be translated to the permutation coefficients
setting, resolving the search for non-sofic groups. In the rest of Section 6
we discuss further open problems and suggest research directions related to
this paper.

###  1.1. Acknowledgements

Thanks to Yotam Dikstein, Shai Evra, Nati Linial, Assaf Naor, Andrei Rapinchuk
and Benjamin Weiss for useful discussions. Michael Chapman acknowledges with
gratitude the Simons Society of Fellows and is supported by a grant from the
Simons Foundation (N. 965535). Alex Lubotzky is supported by the European
Research Council (ERC) under the European Union’s Horizon 2020 (N. 882751).

##  2\. Preliminaries

We briefly recall the main definitions and relevant results from part I
[CL_part1] needed for this paper. A _polygonal complex_ $\mathcal{X}$ is a
$2$-dimensional CW complex whose $2$-cells $\mathcal{X}(2)=P(\mathcal{X})$ —
which we call _polygons_ — are pasted along cyclically reduced paths of the
_underlying graph_ ($1$-skeleton)
$G(\mathcal{X})=(\mathcal{X}(0)=V(\mathcal{X}),\mathcal{X}(1)=E(\mathcal{X}))$.
Every cyclically reduced path of length $\ell$ has $2\ell$ orientations, and
we denote by $\overrightarrow{\mathcal{X}}(2)=\overrightarrow{P}(\mathcal{X})$
the collection of $2$-cells coming with a specific orientation of their pasted
perimeter. We call $\overrightarrow{P}(\mathcal{X})$ the _oriented polygons_.
Given an oriented $i$-cell $x$, we denote by $[x]$ its un-oriented version.
Let $\Gamma$ be a group and $d\colon\Gamma\times\Gamma\to\mathbb{R}_{\geq 0}$
a bi-invariant metric on $\Gamma$. The _$i$ -cochains of $\mathcal{X}$ with
$\Gamma$ coefficients_ are the anti-symmetric assignments of elements of
$\Gamma$ to oriented $i$-cells. Namely,

$C^{i}(\mathcal{X},\Gamma)=\\{\alpha\colon\overrightarrow{\mathcal{X}}(i)\to\Gamma\mid\forall
c\in\overrightarrow{\mathcal{X}}(i)\colon\alpha(\bar{c})=\alpha(c)^{-1}\\}.$

The _coboundary maps_ are defined as follows. For a $0$-cochain $\alpha\colon
V(\mathcal{X})\to\Gamma$, its coboundary $\delta\alpha$ is the $1$-cochain

$\forall x\xrightarrow{e}y\in\overrightarrow{E}(\mathcal{X})\ \colon\ \
\delta\alpha(e)=\alpha(x)^{-1}\alpha(y).$

For a $1$-cochain $\alpha\colon\overrightarrow{E}(\mathcal{X})\to\Gamma$, its
coboundary $\delta\alpha$ is the $2$-cochain

$\forall\pi=e_{1}...e_{\ell}\in\overrightarrow{P}(\mathcal{X})\ \colon\ \
\delta\alpha(\pi)=\alpha(e_{1})...\alpha(e_{\ell}).$

We assume from now on that any polygonal complex $\mathcal{X}$ is given to us
with probability distributions $\mu_{i}$ over its oriented $i$-cells
$\overrightarrow{\mathcal{X}}(i)$. We assume $\mu_{i}$ is uniform over the
orientations of a given $i$-cell, and thus can translate between distributions
over the oriented and un-oriented cells freely. The collection of measures
$\mu_{i}$ is _descending_ if $\mu_{i}(\sigma)$ is proportional to
$\sum_{\tau\supset\sigma}\mu_{i+1}(\tau)$. For any two $i$-cochains with
$\Gamma$ coefficients $\alpha$ and $\beta$, the _distance_ between them is

(2.1)
$d(\alpha,\beta)=\operatorname*{\mathbb{E}}_{x\sim\mu_{i}}[d(\alpha(x),\beta(x))].$

Given a subset $A\subseteq C^{i}(\mathcal{X},\Gamma)$ and a cochain $\alpha\in
C^{i}(\mathcal{X},\Gamma)$, we define the distance of $\alpha$ from $A$ to be

(2.2) $d(\alpha,A)=\inf\\{d(\alpha,\varphi)\mid\varphi\in A\\}.$

The _norm_ of an $i$-cochain with $\Gamma$ coefficients $\alpha$ is its
distance to the constant identity cochain, namely

(2.3)
$\lVert\alpha\rVert=\operatorname*{\mathbb{E}}_{x\sim\mu_{i}}[d(\alpha(x),{\rm
Id})].$

An _$i$ -cocycle_ is an $i$-cochain $\alpha$ for which $\delta\alpha$ is the
constant identity function. We denote the collection of $i$-cocycles by
$Z^{i}(\mathcal{X},\Gamma)$. A $0$-cochain $\beta\colon
V(\mathcal{X})\to\Gamma$ is said to be a _$0$ -coboundary_ if it is constant.
Namely, for every $x,y\in V(\mathcal{X})$ we have $\beta(x)=\beta(y)$. A
$1$-cochain $\alpha\colon\overrightarrow{E}(\mathcal{X})\to\Gamma$ is said to
be a _$1$ -coboundary_ if it is in the image of the coboundary operator
$\delta\colon C^{0}(\mathcal{X},\Gamma)\to C^{1}(\mathcal{X},\Gamma)$. Namely,
there exists a $0$-cochain $\beta\colon V(\mathcal{X})\to{\rm Sym}(n)$ such
that for every $xy\in\overrightarrow{E}(\mathcal{X})$,
$\alpha(xy)=\delta\beta(xy)=\beta(x)^{-1}\beta(y)$. We denote by
$B^{i}(\mathcal{X},{\rm Sym})$ the collection of $i$-coboundaries of
$\mathcal{X}$. Note that, without assuming further assumptions on $\Gamma$,
the only indices for which we define $Z^{i}(\mathcal{X},\Gamma)$ and
$B^{i}(\mathcal{X},\Gamma)$ are $i=0\ \textrm{or}\ 1$. We say that the
_$i^{\rm th}$ cohomology of $\mathcal{X}$ with $\Gamma$ coefficients vanishes_
if every $i$-cocycle of $\mathcal{X}$ is an $i$-coboundary. There is a natural
action of $0$-cochains of $\mathcal{X}$ with $\Gamma$ coefficients on the
$1$-cochains:

(2.4) $\forall\alpha\colon\overrightarrow{E}(\mathcal{X})\to\Gamma,\
\beta\colon V(\mathcal{X})\to\Gamma\ \colon\ \
\beta.\alpha(x\xrightarrow{e}y)=\beta(x)^{-1}\alpha(e)\beta(y).$

Note that for every polygon
$\pi=x\xrightarrow{e_{1}}...\xrightarrow{e_{\ell}}x\in\overrightarrow{P}(\mathcal{X})$,
we have

(2.5) $\beta.\alpha(\pi)=\beta(x)^{-1}\alpha(\pi)\beta(x).$

In particular, $\|\delta(\beta.\alpha)\|=\|\delta\alpha\|,$ and hence the
action preserves $1$-cocycles. Furthermore,

$d(\alpha,B^{1}(\mathcal{X},\Gamma))=\inf\\{\|\beta.\alpha\|\mid\beta\in
C^{0}(\mathcal{X},\Gamma)\\}.$

Let $\rho\colon\mathbb{R}_{\geq 0}\to\mathbb{R}_{\geq 0}$ be a _rate function_
, namely a decreasing function satisfying
$\rho(\varepsilon)\xrightarrow{\varepsilon\to 0}0$. A polygonal complex is
said to be _$\rho$ -cocycle stable in the $i^{\rm th}$ dimension with $\Gamma$
coefficients_ if for every $i$-cochain $\alpha$ we have

(2.6) $d(\alpha,Z^{i}(\mathcal{X},\Gamma))\leq\rho(\|\delta\alpha\|).$

The $i^{\rm th}$ _cocycle Cheeger constant_ of a complex $\mathcal{X}$ with
$\Gamma$ coefficients is

(2.7)
$h_{i}(\mathcal{X},\Gamma)=\inf\mathopen{}\mathclose{{}\left\\{\frac{\|\delta\alpha\|}{d(\alpha,Z^{i}(\mathcal{X},\Gamma))}\
\middle|\ {\alpha\in C^{i}(\mathcal{X},\Gamma)},\ \|\delta\alpha\|\neq
0}\right\\}.$

Similarly, the $i^{\rm th}$ _coboundary Cheeger constant_ of a complex
$\mathcal{X}$ with $\Gamma$ coefficients is

(2.8)
$h^{B}_{i}(\mathcal{X},\Gamma)=\inf\mathopen{}\mathclose{{}\left\\{\frac{\|\delta\alpha\|}{d(\alpha,B^{i}(\mathcal{X},\Gamma))}\
\middle|\ {\alpha\in C^{i}(\mathcal{X},\Gamma)}\setminus
B^{i}(\mathcal{X},\Gamma)}\right\\}.$

When $h_{i}(\mathcal{X},{\rm Sym})>0$ we call $\mathcal{X}$ an _$i$ -cocycle
expander with $\Gamma$ coefficients_, and when $h^{B}_{i}(\mathcal{X},{\rm
Sym})>0$ we call it an _$i$ -coboundary expander with $\Gamma$ coefficients_.
Note that having a positive $i^{\rm th}$ cocycle Cheeger constant is
equivalent to having a linear cocycle stability rate in the $i^{\rm th}$
dimension. Note also that if $h^{B}_{i}(\mathcal{X},\Gamma)>0$, then in
particular the $i^{\rm th}$ cohomology of $\mathcal{X}$ with $\Gamma$
coefficients vanishes. And that if the $i^{\rm th}$ cohomology of
$\mathcal{X}$ with $\Gamma$ coefficients vanishes, then
$h^{B}_{i}(\mathcal{X},\Gamma)=h_{i}(\mathcal{X},\Gamma)$.

######  Remark 2.1.

The stability rate in the $i^{\rm th}$ dimension $\rho$ of a complex
$\mathcal{X}$ (and thus also the Cheeger constants) depends on the
distributions $\mu_{i}$ and $\mu_{i+1}$.

For a positive integer $n$, let ${\rm Sym}(n)$ be the symmetric group acting
on $[n]=\\{1,...,n\\}$. Given permutations $\sigma\in{\rm Sym}(n)$ and
$\tau\in{\rm Sym}(N)$ where $N\geq n$, the _normalized Hamming distance (with
errors)_ between them is

(2.9) $d_{h}(\sigma,\tau)=1-\frac{|\\{i\in[n]\mid\sigma(i)=\tau(i)\\}|}{N}.$

We may use the notation $\|\sigma\|$ for $d_{h}(\sigma,{\rm Id})$, as was done
in (2.3). Moreover, since the normalized Hamming distance can compare
permutations of different sizes, we will study them in a collective manner.
Let

$C^{i}(\mathcal{X},{\rm Sym})=\bigsqcup_{n=2}^{\infty}C^{i}(\mathcal{X},{\rm
Sym}(n)),\ Z^{i}(\mathcal{X},{\rm
Sym})=\bigsqcup_{n=2}^{\infty}Z^{i}(\mathcal{X},{\rm Sym}(n)),\
B^{i}(\mathcal{X},{\rm Sym})=\bigsqcup_{n=2}^{\infty}B^{i}(\mathcal{X},{\rm
Sym}(n))$

be the _$i$ -cochains with permutation coefficients_, the _$i$ -cocycles with
permutation coefficients_ and the _$i$ -coboundaries with permutation
coefficients_ respectively. Thus, $d_{h}$ defines a metric on
$C^{i}(\mathcal{X},{\rm Sym})$ as in (2.1), and thus also a norm on it as in
equation (2.3). Furthermore, the definitions of cocycle stability and Cheeger
constants extend naturally to the permutation coefficicents setup.

Let $\langle S|R\rangle$ be a group presentation with $|S|,|R|<\infty$, and
equipped with probability distributions $\mu_{S}$ and $\mu_{R}$ on the
generators and relations respectively. The _presentation complex_
$\mathcal{X}_{\langle S|R\rangle}$ is the following polygonal complex: It has
a single vertex $*$, and an edge $e(s)$ for every generator $s\in S$. Then,
for every $r=s_{1}^{\varepsilon_{1}}\cdot...\cdot
s_{\ell}^{\varepsilon_{\ell}}\in R$, we add a polygon (together with all its
orientations)
$\pi(r)=e(s_{1})^{\varepsilon_{1}}...e(s_{\ell})^{\varepsilon_{\ell}}$, where
$e(s)^{-1}=\overline{e(s)}$ and $e(s)^{1}=e(s)$. The presentation $\langle
S|R\rangle$ is _$\rho$ -homomorphism stable_ (in permutations) if
$\mathcal{X}_{\langle S|R\rangle}$ is $\rho$-cocycles stable in the $1^{\rm
st}$ dimension with permutation coefficients, where $\mu_{1}=\mu_{S}$ and
$\mu_{2}=\mu_{R}$. Later in the paper, we may refer to the _Cheeger constant
of a group presentation_. In that, we mean the cocycle Cheeger constant in
dimension $1$ with permutation coefficients of the associated presentation
complex.

A _combinatorial map_ $f\colon\mathcal{Y}\to\mathcal{X}$ between two polygonal
complexes is a function that maps $i$-cells of $\mathcal{Y}$ to $i$-cells of
$\mathcal{X}$ in an incidence preserving manner. Note that such a map extends
uniquely to (oriented) paths in $\mathcal{Y}$. A _covering_ of $\mathcal{X}$
is a combinatorial map $f\colon\mathcal{Y}\to\mathcal{X}$ which is a
topological covering (See Chapter 1.3 in [Hatcher_Alg_Top]). As long as
$\mathcal{X}$ is connected, the _degree_ of the covering is well defined and
is equal to $|f^{-1}(x)|$ for any point $x\in\mathcal{X}$. If the degree of
the covering $\mathcal{Y}$ is $n\in\mathbb{N}$, we call it an $n$-covering of
$\mathcal{X}$.

Let $\mathcal{X}$ be a connected polygonal complex. Following Claim 6.1 in
[CL_part1], there is a one to one correspondence between $n$-coverings of
$G(\mathcal{X})$ and orbits of $1$-cochains of $\mathcal{X}$ with ${\rm
Sym}(n)$ coefficients under the action described in (2.4). We recall it now.
For every $1$-cochain $\alpha\colon\overrightarrow{E}(\mathcal{X})\to{\rm
Sym}(n)$, the corresponding covering $f\colon\mathcal{G}\to G(\mathcal{X})$ is
defined to be:

$\displaystyle V(\mathcal{G})=V(\mathcal{X})\times[n];$
$\displaystyle\overrightarrow{E}(\mathcal{G})=\overrightarrow{E}(\mathcal{X})\times[n];$
(2.10) $\displaystyle\forall
x\xrightarrow{e}y\in\overrightarrow{E}(\mathcal{X}),i\in[n]\ \colon\ \ $
$\displaystyle\tau(e,i)=(y,i),\ \iota(e,i)=(x,\alpha(e).i),\
\overline{(e,i)}=(\bar{e},\alpha(e).i);$ $\displaystyle\forall x\in
V(\mathcal{X}),e\in\overrightarrow{E}(\mathcal{X}),i\in[n]\ \colon\ \ $
$\displaystyle f(x,i)=x,\quad f(e,i)=e.$

On the other hand, if $f\colon\mathcal{G}\to G(\mathcal{X})$ is an
$n$-covering, then one can construct a $1$-cochain
$\alpha\colon\overrightarrow{E}(\mathcal{X})\to{\rm Sym}(n)$ as follows: For
every $x\in V(\mathcal{X})$, $|f^{-1}(x)|=n$. Hence we can label the vertices
of $f^{-1}(x)$ by $\\{(x,i)\\}_{i=1}^{n}$. Note that for each vertex there are
$n!$ ways of choosing these labels. Now, for every
$e\in\overrightarrow{E}(\mathcal{X})$ and $e^{\prime}\in f^{-1}(e)$ define
$e^{\prime}=(e,i)$ if $\tau(e^{\prime})=(y,i)$. Then, $\alpha(e).i$ is the
second coordinate of $\iota(e,i)$. The different choices of labeling for the
fibers $f^{-1}(x)$ would give rise to different $1$-cochains in the same orbit
of the action of $0$-cochains. This correspondence sends $1$-cocyceles to
$n$-coverings of the complex $\mathcal{X}$. Futhermore, $1$-coboundaries are
in correspondence with disjoint unions of the base complex $\mathcal{X}$.
Lastly, this correspondence translates $\rho$-cocycle stability to a
topological robustness of coverings — If for a covering $\mathcal{Y}$ of the
underlying graph $G(\mathcal{X})$ most polygons in $\mathcal{X}$ lift to
closed paths in $\mathcal{Y}$, then $\mathcal{Y}$ is close (in an appropriate
metric on graphs) to (the $1$-skeleton of) a cover of $\mathcal{X}$.

##  3\. Cheeger constants with permutation coefficients of complexes and
groups

As was proved in Part I of this paper [CL_part1], homomorphism stability,
covering stability and cocycle stability are equivalent. Furthermore, the
first cocycle Cheeger constant (2.7) of a polygonal complex $\mathcal{X}$ is
positive if and only if the cocycle stability rate of $\mathcal{X}$ is linear.
This leads to two natural problems:

  1. (1)

Which polygonal complexes have a positive cocycle Cheeger constant in the
first dimension with permutation coefficients? Furthermore, can you bound the
Cheeger constant of (naturally arising) families of complexes in a uniform
manner? In Sections 3.1 and 3.2 we provide elementary proofs that complete
complexes and ${A}_{2}$ spherical buildings have cocycle Cheeger constants
which are uniformly bounded away from zero.

  2. (2)

By Fact 3.4, Theorem 1.2 and Theorem 1.3 in Part I [CL_part1], if
$\pi_{1}(\mathcal{X}_{1},*)\cong\pi_{1}(\mathcal{X}_{2},*)$ for two polygonal
complexes $\mathcal{X}_{1}$ and $\mathcal{X}_{2}$, then their stability rates
differ by a multiplicative constant. In particular,
$h_{1}(\mathcal{X}_{1},{\rm Sym})>0$ if and only if
$h_{1}(\mathcal{X}_{2},{\rm Sym})>0$. Assume the presentation complex of
$\Gamma\cong\langle S|R\rangle$ has a positive Cheeger constant. Can we bound
the Cheeger constant of all presentation complexes of $\Gamma$ uniformly? The
answer turns out to be no. In fact, never! Every group has presentations with
an asymptotically close to zero Cheeger constant, as we prove in Section 3.3.

Since homomorphism stability is a widely studied subject, there are many
examples of presentations, and thus complexes, which are $\rho$-stable for
some unspecified $\rho$.111111This is in the spirit of Section 3.2 in Part I
of this paper [CL_part1]. There are cases where meaningful bounds on $\rho$
were proven. For example, Becker–Mosheiff [BeckerMosheiff] analyzed $\rho$ for
presentations of infinite abelian groups, proving that $\rho(\varepsilon)$ is
$\Omega(\varepsilon^{\frac{1}{d}})$ and $O(\varepsilon^{\frac{1}{2^{d}}})$,
where $d$ is the infinite rank of the abelian group. Also,
Lazarovich–Levit–Minsky [levit_lazarovich2019surface] analyzed $\rho$ for
surface groups, proving that $\rho(\varepsilon)$ is
$\Theta(-\varepsilon\ln\varepsilon)$. Note that the above results imply that
the cocycle Cheeger constant of any triangulation of a compact surface which
is not a sphere is $0$. This demonstrates the discrepancy between being a
cocycle expander, and being stable for some rate $\rho$ which is not
necessarily linear. Becker–Chapman [BC22] proved that the multiplication table
presentation of a finite group yields a presentation complex with cocycle
Cheeger constant larger than $\frac{1}{3000}$, regardless of the chosen group.
And, on the other hand, there are examples of group presentations that are not
$\rho$-homomorphism stable for any rate $\rho$ (cf. [GlebskyRivera, BLT,
Ioana]).

###  3.1. The complete complex is a coboundary expander with permutation
coefficients

In this section and in Section 3.2, the distributions we use on the cells of
the complexes are the uniform ones. The proofs we provide work the same if we
choose the uniform distribution on polygons and the induced descending measure
on the edges (see Remark 3.9). We begin with a technical Lemma that appeared
in Section 6.1 of the first part of this paper [CL_part1], as part of the
proof of Theorem 1.1 there.

######  Lemma 3.1.

Let $\mathcal{X}$ be a connected polygonal complex, let $T$ be a spanning tree
in $G(\mathcal{X})$ and let $*\in V(\mathcal{X})$. Then, for every $1$-cochain
$\alpha\colon\overrightarrow{E}(\mathcal{X})\to{\rm Sym}(n)$, there is a
$0$-cochain $\beta\colon V(\mathcal{X})\to{\rm Sym}(n)$ such that
$\beta(*)={\rm Id}$ and $\beta.\alpha(e)={\rm Id}$ for every $e\in T$.

###### Proof sketch.

Recall that $\alpha$ extends to paths in $G(\mathcal{X})$. Choose
$\beta(x)=\alpha(\pi_{x\to*})$, where $\pi_{x\to*}$ is the unique non-
backtracking path in $T$ from $x$ to $*$. It is straightforward to check that
$\beta$ satisfies the desired conditions. ∎

######  Proposition 3.2.

Let $\mathcal{X}$ be the complete $2$-dimensional simplicial complex on $d+1$
vertices, namely the $2$-skeleton of the $d$-dimensional simplex, for $d\geq
2$. Then, $\mathcal{X}$ is $\rho$-cocycle stable with rate
$\rho(\varepsilon)=\frac{d-1}{d+1}\varepsilon$. Namely,
$h_{1}(\mathcal{X},{\rm Sym})\geq\frac{d+1}{d-1}>1$.

###### Proof.

Recall that the vertices of the $d$-dimesnional simplex are
$V(\mathcal{X})=\\{1,...,d+1\\}$. Further, recall that
$\overrightarrow{E}(\mathcal{X})=\\{xy\mid x\neq y\in V(\mathcal{X})\\}$ and
$\overrightarrow{P}(\mathcal{X})=\\{xyz\mid x\neq y\neq z\in
V(\mathcal{X})\\}$.121212Though slightly confusing, in the notation $x\neq
y\neq z$ we mean that all three elements are distinct from one another. Let
$\alpha\colon\overrightarrow{E}(\mathcal{X})\to{\rm Sym}(n)$ be a $1$-cochain.
For every fixed $x\in V(\mathcal{X})$, we can choose a spanning tree $T$ which
is the star centered at $x$. By Lemma 3.1, we can conjugate $\alpha$ by a
$0$-cochain $\beta_{x}$ to be trivial on $T$. Since $\delta\alpha(\Delta)$ is
conjugate to $\delta\beta_{x}.\alpha(\Delta)$ for every triangle $\Delta$, we
have

$\begin{split}\|\delta\alpha\|=\operatorname*{\mathbb{E}}_{x\neq y\neq z\in
V(\mathcal{X})}[d_{h}(\delta\alpha(xyz),{\rm
Id})]=\operatorname*{\mathbb{E}}_{x\neq y\neq z\in
V(\mathcal{X})}[d_{h}(\delta\beta_{x}.\alpha(xyz),{\rm
Id})]=(\diamondsuit).\end{split}$

Recall that
$\delta\beta_{x}.\alpha(xyz)=\beta_{x}.\alpha(xy)\beta_{x}.\alpha(yz)\beta_{x}.\alpha(zx)$.
Now, by our choice, $\beta_{x}.\alpha$ is the identity permutation on every
edge with endpoint $x$. Therefore
$\delta\beta_{x}.\alpha(xyz)=\beta_{x}.\alpha(yz)$. Moreover, if we would have
allowed $x=y$ or $x=z$, then
$\delta\beta_{x}.\alpha(xyz)=\beta_{x}.\alpha(yz)={\rm Id}$ in these cases.
Thus, by letting the expectation go over ordered triplets $xyz$ assuming only
that $y\neq z$, we have

$(\diamondsuit)=\frac{d+1}{d-1}\operatorname*{\mathbb{E}}_{x,y\neq z\in
V(\mathcal{X})}[d_{h}(\beta_{x}.\alpha(yz),{\rm
Id})]=\frac{d+1}{d-1}\operatorname*{\mathbb{E}}_{x\in
V(\mathcal{X})}[\|\beta_{x}.\alpha\|].$

All in all,

(3.1)
$\begin{split}\|\delta\alpha\|=\frac{d+1}{d-1}\operatorname*{\mathbb{E}}_{x\in
V(\mathcal{X})}[\|\beta_{x}.\alpha\|].\end{split}$

Further, the $1^{\rm st}$ cohomology of $\mathcal{X}$ vanishes, namely
$B^{1}(\mathcal{X},{\rm Sym})=Z^{1}(\mathcal{X},{\rm Sym})$ — this is because
the fundamental group of the complete complex is trivial, and by Corollary
4.1131313This result also appeared as Fact 5.11 in [CL_part1]. we deduce the
vanishing of the first cohomology. Since $d_{h}(\alpha,B^{1}(\mathcal{X},{\rm
Sym}))=\inf\\{\|\beta.\alpha\|\mid\beta\colon V(\mathcal{X})\to{\rm
Sym}(n)\\}$ for every complex $\mathcal{X}$,

(3.2) $\begin{split}d_{h}(\alpha,Z^{1}(\mathcal{X},{\rm
Sym}))&=\min\\{\|\beta.\alpha\|\mid\beta\colon V(\mathcal{X})\to{\rm
Sym}(n)\\}\\\ &\leq\operatorname*{\mathbb{E}}_{x\in
V(\mathcal{X})}[\|\beta_{x}.\alpha\|].\end{split}$

Combining (3.1) and (3.2), we get the desired rate. ∎

######  Remark 3.3.

Since the first cohomology of $\mathcal{X}$ vanishes, we also deduce that
$h_{1}^{B}(\mathcal{X},{\rm Sym})\geq\frac{d+1}{d-1}$ in this case. As
$h^{B}_{1}(\mathcal{X},\mathbb{F}_{2})\geq h_{1}^{B}(\mathcal{X},{\rm Sym})$,
we deduce the same for $\mathbb{F}_{2}$ coefficients. Compare with Proposition
2.1 of [linial_meshulam2006homological], where a lower bound of
$\nicefrac{{1}}{{40}}$ on $h^{B}_{1}(\mathcal{X},\mathbb{F}_{2})$ is given.

###  3.2. Spherical buildings of type $A_{2}$ are coboundary expanders with
permutation coefficients

######  Definition 3.4 ($A_{2}$ spherical building).

Let $\mathbb{F}_{q}$ be the finite field with $q$ elements. The vertices of
the $A_{2}$ spherical building $\mathcal{B}=\mathcal{B}(q)$ are the non-
trivial linear subspaces of $\mathbb{F}_{q}^{4}$. Two vertices of
$\mathcal{B}$ are adjacent if one is contained in the other (as sets). For
triangles, we take the clique complex of the resulting graph — namely, add a
triangle whenever we see three vertices that are all connected to one another.

######  Definition 3.5.

We say that a closed path $\pi$ in $\mathcal{X}$ can be _filled_ by polygons
$\pi_{1},...,\pi_{k}\in P(\mathcal{X})$ if one can draw a Van Kampen diagram
whose perimeter is $\pi$ and its cells are the polygons. Namely, $\pi$ is a
product of conjugates of $\pi_{1},...,\pi_{k}$ in the fundamental group of
$\mathcal{X}$. See [babson_hoffman_kahle_2011fundamental] for more about
fillings.

######  Claim 3.6.

Let $\alpha\colon\overrightarrow{E}(\mathcal{X})\to{\rm Sym}(n)$ be a
$1$-cochain. Recall the notation $\|\sigma\|=d_{h}(\sigma,{\rm Id})$ for a
permutation $\sigma$. If $\pi$ is a closed path in $\mathcal{X}$ which is
filled by $\pi_{1},...,\pi_{k}$, then
$\|\alpha(\pi)\|\leq\sum_{i=1}^{k}\|\alpha(\pi_{i})\|$.

###### Proof.

The fact $\pi$ can be filled by $\pi_{1},...,\pi_{k}$ means that it can be
written in a backtracking way as

$\pi=\sigma_{1}\pi_{1}\bar{\sigma}_{1}...\sigma_{k}\pi_{k}\bar{\sigma}_{k},$

where $\sigma_{i}$ are some paths in $G(\mathcal{X})$. Hence

$\begin{split}\|\alpha(\pi)\|&=\mathopen{}\mathclose{{}\left\|\prod_{i=1}^{k}\alpha(\sigma_{i}\pi_{i}\bar{\sigma}_{i})}\right\|\\\
&\leq\sum_{i=1}^{k}\underbrace{\|\alpha(\sigma_{i}\pi_{i}\bar{\sigma}_{i})\|}_{\|\alpha(\sigma_{i})\alpha(\pi_{i})\alpha(\bar{\sigma}_{i})\|}\\\
&=\sum_{i=1}^{k}\mathopen{}\mathclose{{}\left\|\alpha(\pi_{i})}\right\|,\end{split}$

where the second line is by the triangle inequality of the normalized Hamming
metric, and the third line is by the fact
$\alpha(\sigma_{i})^{-1}=\alpha(\bar{\sigma}_{i})$ and the conjugate
invariance of the normalized Hamming metric. ∎

We bring the following fact without a proof.

######  Fact 3.7.

Note that

  * •

The $1$-skeleton of $\mathcal{B}$ has diameter $3$.

  * •

The automorphism group of $\mathcal{B}$ acts transitively on the un-oriented
triangles of $\mathcal{B}$.

  * •

Every closed path $\pi$ of length $\leq 7$ in the $1$-skeleton
$G(\mathcal{B})$ can be filled by at most $25$ triangles.141414This bound is
not intended to be optimal, but can be deduced in a straightforward manner by
a back of the envelope calculation.

######  Proposition 3.8.

The complex $\mathcal{B}$ is $\rho$-cocycle stable for
$\rho(\varepsilon)=25\varepsilon$. Namely, $h_{1}(\mathcal{B},{\rm
Sym})\geq\frac{1}{25}$, regardless of $q$.

###### Proof.

Let $\alpha\colon\overrightarrow{E}(\mathcal{B})\to{\rm Sym}(n)$ be a
$1$-cochain. Fix a vertex $x\in\mathcal{B}$ and a spanning tree $T$ of radius
$3$ from $x$ (there exists such a tree because of the diameter condition in
Fact 3.7). For every $\eta\in\textrm{Aut}(\mathcal{B})$ we get a new base
point $\eta(x)$ and a new spanning tree $\eta(T)$. By Lemma 3.1, we can
conjugate $\alpha$ by a $0$-cochain $\beta_{\eta}$ so that it is the identity
on $\eta(T)$. As for the complete complex, the cohomology of $\mathcal{B}$
vanishes, hence

$\begin{split}d_{h}(\alpha,Z^{1}(\mathcal{B},{\rm
Sym})))&=\min\\{\|\beta.\alpha\|\mid\beta\colon V(\mathcal{X})\to{\rm
Sym}(n)\\}\\\
&\leq\min\\{\|\beta_{\eta}.\alpha\|\mid\eta\in\textrm{Aut}(\mathcal{B})\\}\\\
&\leq\operatorname*{\mathbb{E}}_{\eta\in\textrm{Aut}(\mathcal{B})}[\|\beta_{\eta}.\alpha\|].\end{split}$

Since every vertex is at most $3$ steps away from $x$ via the spanning tree
$T$, for every edge $e\in\overrightarrow{E}(\mathcal{B})$ there is a closed
path $\pi_{e}$ of length $\leq 7$ originating from $x$ which traverses $e$ as
the only edge (potentially) not in $T$. By Fact 3.7, there are triangles
$\\{\Delta^{e}_{i}\\}_{i=1}^{k_{e}}\subseteq\overrightarrow{P}(\mathcal{B})$,
where $k_{e}\leq 25$, which fill up $\pi_{e}$. Now, the action of
$\textrm{Aut}(\mathcal{B})$ on the data $e,\pi_{e}$ and $\Delta_{i}^{e}$
preserves its properties. Namely, the path $\eta(\pi_{e})$ traverses $\eta(e)$
such that it is the only edge outside of $\eta(T)$. Moreover, $\eta(\pi_{e})$
is filled by $\\{\eta(\Delta^{e}_{i})\\}_{i=1}^{k_{e}}$. Thus,

$\begin{split}\|\beta_{\eta}.\alpha(\eta(e))\|&=\|\beta_{\eta}.\alpha(\eta(\pi_{e}))\|\\\
&\leq\sum_{i=1}^{k_{e}}\|\beta_{\eta}.\alpha(\eta(\Delta^{e}_{i}))\|\\\
&=\sum_{i=1}^{k_{e}}\|\alpha(\eta(\Delta^{e}_{i}))\|,\end{split}$

where the second line is by Claim 3.6, and the third is by (2.5). Combining
our observations, we get

$\begin{split}d_{h}(\alpha,Z^{1}(\mathcal{B},{\rm
Sym})))(\alpha)&\leq\operatorname*{\mathbb{E}}_{\eta\in\textrm{Aut}(\mathcal{B})}[\|\beta_{\eta}.\alpha\|]\\\
&=\operatorname*{\mathbb{E}}_{\eta\in\textrm{Aut}(\mathcal{B})}\operatorname*{\mathbb{E}}_{e\in\overrightarrow{E}(\mathcal{B})}[\|\beta_{\eta}.\alpha(\eta(e))\|]\\\
&\leq\operatorname*{\mathbb{E}}_{\eta\in\textrm{Aut}(\mathcal{B})}\operatorname*{\mathbb{E}}_{e\in\overrightarrow{E}(\mathcal{B})}\mathopen{}\mathclose{{}\left[\sum_{i=1}^{k_{e}}\|\delta\alpha(\eta(\Delta^{e}_{i}))\|}\right]\\\
&=\operatorname*{\mathbb{E}}_{e\in\overrightarrow{E}(\mathcal{B})}\mathopen{}\mathclose{{}\left[\sum_{i=1}^{k_{e}}\mathopen{}\mathclose{{}\left(\operatorname*{\mathbb{E}}_{\eta\in\textrm{Aut}(\mathcal{B})}[\|\delta\alpha(\eta(\Delta^{e}_{i}))\|]}\right)}\right]\\\
&=(*).\end{split}$

Recall that by Fact 3.7, $\textrm{Aut}(\mathcal{B})$ acts transitively on the
triangles of $\mathcal{B}$. In particular, for a fixed triangle
$\Delta_{i}^{e}$, we have

$\operatorname*{\mathbb{E}}_{\eta\in\textrm{Aut}(\mathcal{B})}[\|\delta\alpha(\eta(\Delta^{e}_{i}))\|]=\operatorname*{\mathbb{E}}_{[\Delta]\in
P(\mathcal{B})}[\|\delta\alpha(\Delta)\|]=\|\delta\alpha\|.$

Therefore,

$\begin{split}(*)&=\operatorname*{\mathbb{E}}_{e\in\overrightarrow{E}(\mathcal{B})}\mathopen{}\mathclose{{}\left[k_{e}\cdot\|\delta\alpha\|}\right]\\\
&\leq 25\|\delta\alpha\|,\end{split}$

which finishes the proof. ∎

######  Remark 3.9.

Note that in the above proof we did not use the distribution $\mu_{1}$ on the
edges at all. We just used the fact that the distribution $\mu_{2}$ is
uniform.

######  Remark 3.10.

We focused on type $A_{2}$ spherical buildings. The approach we used is
usually referred to as the _cones method_ (cf.
[LMM_2016expansion_building_like]). This approach can be further applied to
all types of spherical buildings $\mathcal{B}$ of degree $d$ (e.g., of type
$A_{d}$), but with the stability rate degrading as $d$ increases. The recent
combinatorial methods of Dikstein–Dinur [dikstein2023coboundary], and
specifically _color restriction_ , allows to prove that the stability rate of
such spherical buildings is actually independent of $d$.151515Dikstein–Dinur
[dikstein2023coboundary] use the framework of Dinur–Meshulam [Dinur-Meshulam]
(See Section 4.2 in Part I [CL_part1]). But, the color restriction technique
can be applied in our setup, i.e., with the normalized Hamming metric
replacing the discrete distance.

Though the proofs that spherical buildings are stable may require intricate
arguments, such as the cones method and color restriction, the fact that they
are stable with good rates is quite evident. Note that spherical buildings are
only “a few steps” from being complete complexes. This is essentially the
content of Fact 3.7. Namely, they have a bounded diameter, and every triangle
of the complete complex can be filled with a bounded amount of triangles from
the building. This means that these complexes are almost as stable as the
complete complex, if we use the $L^{\infty}$-analogues (recall the discussion
at the end of Section 4.2 in Part I [CL_part1]). Since we do not use the
$L^{\infty}$-analogues but rather $L^{1}$-versions, i.e., we sample a polygon
uniformly at random in our testers (compare Algorithms 5 and 3 in Part I
[CL_part1]), proving stability requires more steps.

###  3.3. Arbitrarily small Cheeger constant of group presentations

######  Claim 3.11.

For every $\varepsilon>0$ and finitely presented group $\Gamma$, there exists
a finite presentation $\langle S|R\rangle\cong\Gamma$ such that

$h_{1}(\mathcal{X}_{\langle S|R\rangle},{\rm Sym})\leq\varepsilon,$

where $\mathcal{X}_{\langle S|R\rangle}$ is the presentation complex of
$\langle S|R\rangle$.

To prove Claim 3.11 we need the following corollary of Remark 6.7 in Part I
[CL_part1].

######  Claim 3.12.

For every $\varepsilon>0$, there is a presentation $\langle S|R\rangle$ of the
trivial group such that

$h_{1}(\mathcal{X}_{\langle S|R\rangle},{\rm Sym})\leq\varepsilon.$

###### Proof sketch.

If we take the complete complex on $d$-vertices and contract the spanning tree
$1\to 2\to...\to d$, we are left with a polygonal complex $\mathcal{X}$ with a
single vertex. The resulting complex defines a presentation of its fundamental
group, which is isomorphic to the trivial group, by taking $E(\mathcal{X})$ to
be the generating set and $P(\mathcal{X})$ to be the relations. By Remark 6.7
in [CL_part1], this presentation has $h_{1}(\mathcal{X},{\rm
Sym})\leq\frac{12}{d(d-1)}$. Hence, by choosing a large enough $d$, we are
done. ∎

###### Proof of Claim 3.11.

Let $\Gamma\cong\langle S^{\prime}|R^{\prime}\rangle$ be a finitely presented
group. By Claim 3.12, for every $\varepsilon^{\prime}>0$ there is a
presentation $\langle S^{\prime\prime}|R^{\prime\prime}\rangle\cong{\bf 1}$
with $h_{1}(\mathcal{X}_{\langle
S^{\prime\prime}|R^{\prime\prime}\rangle},{\rm Sym})\leq\varepsilon^{\prime}$.
We can choose the sets $S^{\prime},S^{\prime\prime}$ and
$R^{\prime},R^{\prime\prime}$ to be disjoint. Then, on the one hand,

$\langle S|R\rangle=\langle
S^{\prime},S^{\prime\prime}|R^{\prime},R^{\prime\prime}\rangle\cong\langle
S^{\prime}|R^{\prime}\rangle*\langle
S^{\prime\prime}|R^{\prime\prime}\rangle\cong\Gamma*{\bf 1}\cong\Gamma.$

On the other hand, every map $f\colon S^{\prime\prime}\to{\rm Sym}(n)$ can be
extended to $\hat{f}\colon S^{\prime}\cup S^{\prime\prime}\to{\rm Sym}(n)$
which is trivial on $S^{\prime}$. Now, if we choose $\mu_{2}$ and $\mu_{1}$ to
be uniform on the relations and generators, then
$\|\delta\hat{f}\|=\frac{|R^{\prime\prime}|}{|R^{\prime\prime}|+|R^{\prime}|}\|\delta
f\|$ and similarly $d_{h}(\hat{f},Z^{1}(\mathcal{X}_{\langle S|R\rangle},{\rm
Sym})))=\frac{|S^{\prime\prime}|}{|S^{\prime\prime}|+|S^{\prime}|}d_{h}(f,Z^{1}(\mathcal{X}_{\langle
S^{\prime\prime}|R^{\prime\prime}\rangle},{\rm Sym})))$. Thus,

$\begin{split}\frac{\|\delta\hat{f}\|}{d_{h}(\hat{f},Z^{1}(\mathcal{X}_{\langle
S|R\rangle},{\rm
Sym}))}&=\frac{|R^{\prime\prime}|(|S^{\prime\prime}|+|S^{\prime}|)}{|S^{\prime\prime}|(|R^{\prime\prime}|+|R^{\prime}|)}\frac{\|\delta
f\|}{d_{h}(f,Z^{1}(\mathcal{X}_{\langle
S^{\prime\prime}|R^{\prime\prime}\rangle},{\rm Sym}))}\\\
&\leq(1+|S^{\prime}|)\cdot\frac{\|\delta
f\|}{d_{h}(f,Z^{1}(\mathcal{X}_{\langle
S^{\prime\prime}|R^{\prime\prime}\rangle},{\rm Sym}))}\\\
&\leq(1+|S^{\prime}|)\varepsilon^{\prime}.\end{split}$

By choosing $\varepsilon^{\prime}=\frac{\varepsilon}{1+|S^{\prime}|}$, we
deduce the claim. ∎

##  4\. High dimensional expansion and Large cosystols

###  4.1. High dimensional expansion

For every non-trivial group $\Gamma$, the $0^{\rm th}$ cohomology of
$\mathcal{X}$ with $\Gamma$ coefficients vanishes if and only if
$G(\mathcal{X})$ is connected. What does it mean for the $1^{\rm st}$
cohomology to vanish? For permutation coefficients there is a nice
characterization. Since $1$-cocycles are in correspondence with coverings of
the base complex, and $1$-coboundaries are disjoint unions of the base
complex, having a non-coboundry $1$-cocycle is the same as having a non-
trivial finite covering of the base complex. Since there is a correspondence
between coverings of $\mathcal{X}$ and subgroups of the fundamental group
$\pi_{1}(\mathcal{X},*)$, having no non-trivial finite coverings is equivalent
to $\pi_{1}(\mathcal{X},*)$ having no proper finite-index subgroups. In
summary:

######  Corollary 4.1.

Given a polygonal complex $\mathcal{X}$, the following three conditions are
equivalent:

  1. (1)

The first cohomology of $\mathcal{X}$ with permutation coefficients vanishes.

  2. (2)

The fundamental group $\pi_{1}(\mathcal{X},*)$ has no finite index subgroups.

  3. (3)

The profinite completion of its fundamental group is trivial, nemaly
$\widehat{\pi_{1}(\mathcal{X},*)}=1$.

As oppose to the $0^{\rm th}$ dimensional case, where vanishing of the $0^{\rm
th}$ cohomology, namely connectedness, is the most basic property you would
expect from an object which presumes to _expand_ , this is not the case in
higher dimensions. Out of the various suggested high dimensional expansion
properties (cf. [lubotzky2018high]), coboundary expansion is considered a very
strong notion. These days, there are many motivations to study coboundary
expansion (cf. [kaufman2014high]), but the original motivation to study it
came — as mentioned in our introduction — from topological overlapping.
Specifically, from the fact that coboundary expansion implies topological
overlapping. Dotterrer–Kaufman–Wagner [DKW_cosystolic_exp_implies_overlap]
proved that a weakened version of coboundary expansion suffices to deduce
topological overlapping (Theorem 1.4): The simplicial complex needs to —

  1. (1)

Be a cocycle expander with $\mathbb{F}_{2}$ coefficients.

  2. (2)

Have large cosystols with $\mathbb{F}_{2}$ coefficients.

We postpone addressing condition $(1)$ with permutation coefficients for the
examples used by [kaufman2016isoperimetric, evra2016bounded] to Section 6.1.
In this section, we concentrate on condition $(2)$ with permutation
coefficients.161616In [DKW_cosystolic_exp_implies_overlap] they called the
above combination of properties _cosystolic_ expansion. We will not use this
term. Note also that in [Dinur-Meshulam, dikstein2023coboundary] cosystolic
expansion is what we call cocycle expansion, namely they do not require the
large cosystols condition. The naive generalization of the large cosystols
condition to our setup, by asking every non-coboundary cocycle to have a large
norm, cannot work: Let $\alpha\colon\overrightarrow{E}(\mathcal{X})\to{\rm
Sym}(n)$ be a non-coboundary cocycle. Note that we can define an embedding
$\omega\colon{\rm Sym}(n)\to{\rm Sym}(N)$ for any $N\geq n$, such that

$\forall\sigma\in{\rm Sym}(n),\ i>n\ \ \colon\ \ \ \omega(\sigma).i=i.$

Composing $\alpha$ with $\omega$, we get a new non-coboundary cocycle with
norm which is $\frac{n}{N}$ smaller than $||\alpha||$. Since this works for
any $N$, we cannot assume a unifrom lower bound on the norm of non-coboundary
cocycles. Note that the cocycle $\omega\circ\alpha$ correspndes to a covering
which is the disjoint union of $N-n$ copies of the underlying $\mathcal{X}$
together with the covering associated with $\alpha$. In particular, it is
disconnected. Nevertheless, the notion of large cosystols can still be saved,
by lower bounding the norms of connected non-coboundary cocycles.

######  Definition 4.2.

A $1$-cochain $\alpha\colon\overrightarrow{E}(\mathcal{X})\to{\rm Sym}(n)$ is
_connected_ if it encodes a connected covering of the underlying graph of the
base complex — namely, for every two indices $i,j\in[n]$ and every two
vertices $x,y\in V(\mathcal{X})$, there is a path $\pi$ in $\mathcal{X}$ whose
endpoints are $x$ and $y$ while $\alpha(\pi).i=j$.

######  Definition 4.3.

A complex $\mathcal{X}$ has _$\theta$ -large cosystols with permutation
coefficients_ if every non-coboundary connected cocycle
$\alpha\colon\overrightarrow{E}(\mathcal{X})\to{\rm Sym}(n)$ satisfies
$\|\alpha\|\geq\theta$. I.e., $CoSyst_{1}(\mathcal{X},{\rm Sym})\geq\theta$,
where

(4.1) $CoSyst_{1}(\mathcal{X},{\rm Sym})=\inf\\{\|\alpha\|\mid\alpha\
\textrm{is\ {connected}},\ \alpha\in Z^{1}(\mathcal{X},{\rm Sym})\setminus
B^{1}(\mathcal{X},{\rm Sym})\\}.$

Note that $CoSyst_{1}(\mathcal{X},{\rm
Sym})\geq\frac{1}{|\overrightarrow{E}(\mathcal{X})|}$. Given $\mathcal{Y}_{i}$
a family of growing coverings of $\mathcal{X}$, the quantity
$CoSyst_{1}(\mathcal{Y}_{i},{\rm Sym})$ may approach zero. An example to that
is the coverings of a cycle. More generally,

######  Proposition 4.4.

Let $\mathcal{X}$ be a finite, connected polygonal complex with
$\pi_{1}(\mathcal{X},*)$ a residually finite amenable group. Then, for every
$\varepsilon>0$, there is a covering $\mathcal{Y}$ of $\mathcal{X}$ such that
$CoSyst_{1}(\mathcal{Y},{\rm Sym})\leq\varepsilon$.

To that end, we need the following Theorem of Weiss.

######  Theorem 4.5 (Theorem 1 in [weiss2001monotileable]).

Let $\Gamma$ be a residually finite amenable group, and let $S$ be a finite
generating set of $\Gamma$. Then, for every $\varepsilon>0$, there exists a
normal subgroup $N\trianglelefteq\Gamma$ of finite index $n$ and elements
$A=\\{a_{1},...,a_{n}\\}$ such that

  1. (1)

$A$ is a transversal of $\Gamma/N$, i.e., $AN=\Gamma$.

  2. (2)

$A$ is $\varepsilon$-invariant with respect to left multiplication by $S$,
i.e.,

$|SA\setminus A|=|\\{sa\mid s\in S,a\in A,sa\notin A\\}|\leq\varepsilon|A|.$

######  Remark 4.6.

This is not the formulation of Theorem 1 spelled out in
[weiss2001monotileable], but, it is essentially what is proved therein.

Moreover, we need the following characterization of the norm of a cocycle.

######  Fact 4.7.

Let $\alpha\colon\overrightarrow{E}(\mathcal{X})\to{\rm Sym}(n)$ be a
$1$-cocycle. Let $\mathcal{Y}$ be the covering of $\mathcal{X}$ associated
with $\alpha$ as in (2.10). Let $Level(i)=\\{(x,i)\mid x\in
V(\mathcal{X})\\}\subseteq V(\mathcal{Y})$ be the $i^{\rm th}$ _level_ of
$\mathcal{Y}$, and let $\beta_{i}\colon V(\mathcal{Y})\to\\{0,1\\}$ be its
indicator function. Then

$\|\alpha\|=\operatorname*{\mathbb{E}}_{\begin{subarray}{c}e\sim\mu_{1}\\\
i\in[n]\end{subarray}}[\delta\beta_{i}(e,i)]$

Namely, $\|\alpha\|$ is the probability a sampled edge has endpoints in
different levels.171717 This is an immediate consequence of the fact that
$\delta\beta_{i}(e,i)$ indicates whether $\alpha(e).i\neq i$ or not.

###### Proof of Proposition 4.4.

Without loss of generality, we can assume $\mathcal{X}$ is a presentation
complex of some finite presentation $\Gamma\cong\langle S|R\rangle$, namely it
has a single vertex $*$. This is because, if we retract a spanning tree $T$,
the coverings of $\mathcal{X}$ are in one to one correspondence with coverings
of $\mathcal{X}/T$. Now given a finite covering $\mathcal{Y}$ of
$\mathcal{X}$, denote by $\mathcal{Y}/T$ the retraction of all the lifts of
$T$ to $\mathcal{Y}$. Every cocycle on $\mathcal{Y}/T$ can be extended to a
cocycle on $\mathcal{Y}$ by sending all the edges of the lifts of $T$ to the
identity. This operation only reduces the norm of the cocycle on $\mathcal{Y}$
compared to that on $\mathcal{Y}/T$, and thus upper bounding
$CoSyst_{1}(\mathcal{Y}/T,{\rm Sym})$ provides an upper bound for
$CoSyst_{1}(\mathcal{Y},{\rm Sym})$.181818Compare this to the proof of
Proposition 4.10, in which we need to work harder. This is because there is no
natural inequality in the reverse direction. Furthermore, we can assume
$\mu_{1}=\mu_{S}$ is uniform, otherwise we replace the soon to be chosen
$\varepsilon$ by $\frac{\varepsilon}{|S|}$ and proceed as we do.

Let $\varepsilon>0$. By assumption, $\Gamma\cong\pi_{1}(\mathcal{X},*)$ is
residually finite and amenable. By Theorem 4.5, there exists
$N\trianglelefteq\Gamma\cong\pi_{1}(\mathcal{X},*)$ a normal subgroup of index
$n<\infty$ and $A=\\{a_{1},...,a_{n}\\}$ such that $AN=\Gamma$ and
$|SA\setminus A|\leq\varepsilon|A|$. Therefore, for every $h\in\Gamma$,
$|SAh\setminus Ah|\leq\varepsilon|Ah|=\varepsilon|A|$ — namely, the right
translates of $A$ are also $\varepsilon$-invariant. Since $\Gamma$ is
residually finite, there exists a finite index subgroup $N^{\prime}\subsetneq
N$, with $[N:N^{\prime}]=k$. Choose a transversal
$B=\\{b_{1},...,b_{k}\\}\subseteq N$ of $N^{\prime}$.

The left action of $\Gamma$ on $\Gamma/N$ induces a covering $\mathcal{Y}$ of
$\mathcal{X}=\mathcal{X}_{\langle S|R\rangle}$, by letting
$V(\mathcal{Y})=A\cong\Gamma/N$ and $a_{i}\xrightarrow{s}a_{j}$ if and only if
$sa_{j}N=a_{i}N$. Similarly, the left action of $\Gamma$ on
$\Gamma/N^{\prime}$ induces a connected covering $\mathcal{Z}$ of
$\mathcal{X}$ with vertex set $A\times B\cong AB\cong\Gamma/N^{\prime}$, and
with $a_{i}b_{i^{\prime}}\xrightarrow{s}a_{j}b_{j^{\prime}}$ if and only if
$sa_{j}b_{j^{\prime}}N^{\prime}=a_{i}b_{i^{\prime}}N^{\prime}$. Since
$N^{\prime}\lneq N$, the projection to the first coordinate $A\times B\to A$
is a covering map from $\mathcal{Z}$ to $\mathcal{Y}$. Define, as in Fact 4.7,
$Level_{\mathcal{Z}}(b)=A\times\\{b\\}=\\{(a,b)\mid a\in A\\}$. This choice of
levels is the same as choosing a $1$-cocycle of $\mathcal{Y}$ that represents
the covering $\mathcal{Z}\to\mathcal{Y}$ (as in the end of Section 2). One can
also read this cocycle directly as follows: Since
$\overrightarrow{E}(\mathcal{Y})$ can be parametrized by $S\times A$, the
associated cocycle $\alpha\colon S\times A\to{\rm Sym}(B)$ is defined by
sending the pair $(s,a_{i})$ to the following permutation of $B$ — embed $B$
in $\\{a_{i}\\}\times B$; then $s$ sends $\\{a_{i}\\}\times B$ to
$\\{s^{-1}a_{i}\\}\times B$; by projecting to the second coordinate, we can
extract the permutation on $B$. Hence, the levels of $\mathcal{Z}$ with
respect to $\alpha$ are $Level_{\mathcal{Z}}(b)$.

Now, if the edge labeled by $s$ who terminates in $(a,b)\in\mathcal{Z}$ and
whose origin is at $(a^{\prime},b^{\prime})$ where $b^{\prime}\neq b$, then in
particular $sab\notin Ab$. But we know that $SAb\setminus Ab$ is of size at
most $\varepsilon|A|$, which means there are at most $\varepsilon|A||S|$ such
edges. All in all, at most $\varepsilon$ of the edges cross levels, and by
Fact 4.7, $\|\alpha\|\leq\varepsilon$ finishing the proof.

∎

Groups with property $(\tau)$ (cf. [lubotzky1994discrete]), a soft version of
Kazhdan’s property (T), stand as a contrast to amenable groups in many cases .
This is the case here as well. The main result of the rest of this section is
that the finite coverings of a complex with fundamental group having property
$(\tau)$, have a uniform lower bound on their cosystols. This gives also a new
way of deducing large cosystols in dimension $1$ with
$\mathbb{F}_{2}$-coefficients, providing an alternative to the methods used in
[kaufman2016isoperimetric, evra2016bounded], as well as simplifying any future
approach towards Problem 6.6.

###  4.2. Edge expansion of coverings implies large cosystols

######  Proposition 4.8.

Let $\mathcal{X}$ be a polygonal complex. Let $\gamma>0$. Assume that every
finite connected covering $\mathcal{Y}$ of $\mathcal{X}$ is an edge expander,
namely, $h_{0}(\mathcal{Y},\mathbb{F}_{2})\geq\gamma$ for some $\gamma>0$.
Then $CoSyst_{1}(\mathcal{X},{\rm Sym})\geq\frac{\gamma}{2}$.

###### Proof.

We begin with the setup of Fact 4.7. Let
$\alpha\colon\overrightarrow{E}(\mathcal{X})\to{\rm Sym}(n)$ be a connected
$1$-cocycle which is not a coboundary (namely, a non-coboundary connected
coycle). Let $\mathcal{Y}$ be the covering of $\mathcal{X}$ associated with
$\alpha$ as in (2.10), with the measures on cells being uniformly lifted to
$\mathcal{Y}$. Let $Level(i)=\\{(x,i)\mid x\in V(\mathcal{X})\\}\subseteq
V(\mathcal{Y})$ be the $i^{\rm th}$ _level_ of $\mathcal{Y}$, and let
$\beta_{i}\colon V(\mathcal{Y})\to\mathbb{F}_{2}$ be its indicator function.
The measure induced on $\mathcal{Y}$ is
$\mu_{j}(\sigma,i)=\frac{1}{n}\mu_{j}(\sigma)$, where $j=0,1$ or $2$,
$\sigma\in\mathcal{X}(j)$ and $i\in[n]$.

The idea of the proof is very simple: as Fact 4.7 entails, $\|\alpha\|$ is
proportional to the number of edges going between different levels. If
$\mathcal{Y}$ is an expander, there are many such edges. Let us be more
formal. We have,

$\begin{split}\gamma\leq\frac{\|\delta\beta_{i}\|}{\underbrace{d(\beta_{i},Z^{0}(\mathcal{Y},\mathbb{F}_{2}))}_{=\nicefrac{{1}}{{n}}}}=n\cdot\operatorname*{\mathbb{E}}_{(e,k)\sim\mu_{1}}[\delta\beta_{i}(e,k)]=\sum_{k=1}^{n}\operatorname*{\mathbb{E}}_{e\sim\mu_{1}}[\delta\beta_{i}(e,k)]=(\diamondsuit).\end{split}$

Now, $\delta\beta_{i}(e,k)=1$ when one of $(e,k)$’s endpoints is in $Level(i)$
and the other is not. Since the endpoints of $(e,k)$ are $(\tau(e),k)$ and
$(\iota(e),\alpha(e).k)$, the condition is $k=i$ and $\alpha(e).k\neq i$ or
$k\neq i$ and $\alpha(e).k=i$. Since every orientation of every edge is
counted that way, one may count twice those of the first kind. Therefore,

$\begin{split}(\diamondsuit)=2\operatorname*{\mathbb{E}}_{e\sim\mu_{1}}[\delta\beta_{i}(e,i)]=2\operatorname*{\mathbb{P}}_{e\sim\mu_{1}}[\alpha(e).i\neq
i].\end{split}$

On the other hand,

$\|\alpha\|=\operatorname*{\mathbb{P}}_{\begin{subarray}{c}e\sim\mu_{1}\\\
i\in[n]\end{subarray}}[\alpha(e).i\neq i].$

Thus, by taking $\operatorname*{\mathbb{E}}_{i\in[n]}$ on $(\diamondsuit)$, we
deduce $\|\alpha\|\geq\frac{\gamma}{2}$. ∎

######  Corollary 4.9.

Let $\mathcal{X}$ be a polygonal complex. Let $\gamma>0$. Assume that every
finite connected covering $\mathcal{Y}$ of $\mathcal{X}$ is an edge expander,
namely, $h_{0}(\mathcal{Y},\mathbb{F}_{2})\geq\gamma$ for some $\gamma>0$.
Then $CoSyst_{1}(\mathcal{Z},{\rm Sym})\geq\frac{\gamma}{2}$ for every
covering $\mathcal{Z}$ of $\mathcal{X}$.

###### Proof.

Since every covering of $\mathcal{Z}$ is a covering of $\mathcal{X}$, if the
conditions of Proposition 4.8 are satisfied by $\mathcal{X}$, then they are
satisfied by $\mathcal{Z}$. ∎

As we recalled in the beginning of Section 4.1, the connected coverings of
$\mathcal{X}$ are in one to one correspondence with subgroups of the
fundamental group $\pi_{1}(\mathcal{X},*)$. We will move now to show that if
$\pi_{1}(\mathcal{X},*)$ has property $(\tau)$, then all its finite coverings
are edge expanding.

###  4.3. Property $(\tau)$ and edge expansion of coverings

Let $\Gamma$ be a finitely generated group, and $S$ a finite generating set of
$\Gamma$. Let $\mu$ be a probability distribution on $S$, viewed as a an
element of the group ring $\mathbb{C}[\Gamma]$. Since every unitary
representation $\rho$ of $\Gamma$ which acts on a Hilbert space $\mathbb{H}$
can be extended to the group ring, we can define the operator $\rho(\mu)\in
B(\mathbb{H})$. Namely, $\rho(\mu)=\sum_{s\in S}\mu(s)\rho(s)$. If there
exists $\gamma>0$ such that, regardless of the chosen unitary representation
$\rho$, the spectrum of $\rho(\mu)$ is contained in
$[-1,1-\gamma]\cup\\{1\\}$, we say that $\mu$ has spectral gap $\gamma$. If
this happens, then $\Gamma$ has Kazhdan’s property (T), in which case a
spectral gap exists for any measure with a finite generating support. If the
same is true only for finite dimensional representations which factor through
finite quotients of $\Gamma$, we say that $\Gamma$ has property $(\tau)$.

######  Proposition 4.10.

Let $\mathcal{X}$ be a connected polygonal complex. If
$\pi_{1}(\mathcal{X},*)$ has $(\tau)$, then there is a
$\gamma=\gamma(\mathcal{X})>0$ such that for every connected covering
$\mathcal{Y}$ of $\mathcal{X}$ we have
$h_{0}(\mathcal{Y},\mathbb{F}_{2})\geq\gamma$.

###### Proof sketch.

This proposition depends only on the $1$-dimensional skeleton of the complex,
both in its statement and in the following proof. This is a generalization of
the well known result (cf. [lubotzky1994discrete]) that the Schreier graphs of
groups with property $(\tau)$ are expanders. This exactly corresponds to the
case where $\mathcal{X}$ is a presentation complex, namely has a single
vertex.

Assume $*$ is a vertex of $G(\mathcal{X})$. Given a spanning tree $T$ of
$G(\mathcal{X})$, we can choose for every edge
$xy\in\overrightarrow{E}(\mathcal{X})$ outside of $T$ an element in
$\pi_{1}(\mathcal{X},*)$ as follows: Walk from $*$ to $x$ in $T$. Then
traverse $xy$. Then walk from $y$ back to $*$. This is a closed path in
$G(\mathcal{X})$ which originates at $*$ and hence it is an element of the
fundamental group. Moreover, this is a generating set, and we denote it by
$S$. Take the uniform measure on $S$. By property $(\tau)$, there exists
$\gamma_{0}>0$ such that the spectral gap of the operator
$\operatorname*{\mathbb{E}}_{s\in S}[\rho(s)]$ for all finite dimensional
unitary representations of $\pi_{1}(\mathcal{X},*)$ is at least $\gamma_{0}$.

Let $\mathcal{Y}$ be a connected $n$-covering of $\mathcal{X}$. Let
$T_{1},...,T_{n}$ be the lifts of the tree $T$ to $\mathcal{Y}$. We can
retract the $T_{i}$’s in $\mathcal{Y}$ to points, resulting in a graph
$\mathcal{Z}$. Then, $\mathcal{Z}$ is a Schreier graph of
$\pi_{1}(\mathcal{X},*)$ with respect to the generating set $S$. Hence, the
adjacency operator on $\mathcal{Z}$ is of the form
$\operatorname*{\mathbb{E}}_{s\in S}[\rho(s)]$, where $\rho$ is the action of
the fundamental group on the vertices of its Schreier graph. Thus, the
adjacency operator on $\mathcal{Z}$ has a spectral gap of at least
$\gamma_{0}$. By the Cheeger inequalities, $\mathcal{Z}$ is a good edge
expander.

Now, $\mathcal{Z}$ can be a great expander while $\mathcal{Y}$ is not. As an
example, take $\mathcal{Y}=\mathcal{X}$ and note that $\mathcal{Z}$ has a
single vertex and thus is an optimal expander, while $\mathcal{X}$ may be as
bad an expander as you would like. But, this is the _only obstruction_.
Namely, since we fix $\mathcal{X}$ and look at coverings of it, there is a way
of bounding the spectral gap of the covering $\mathcal{Y}$ by those of the
retracted graph $\mathcal{Z}$ and the base graph $\mathcal{X}$ (or at least
that of the tree $T$ that we chose). To see that, note that $\mathcal{Y}$ is
essentially the replacement product of $\mathcal{Z}$ with $T$. In this
viewpoint, the trees $T_{i}$ are analogous to the clouds in the replacement
product. Hence, given any function $\beta\colon V(\mathcal{Y})\to\mathbb{C}$
which is perpendicular to the constant functions, we can average it out along
the clouds. On the averaged function the adjacency of $\mathcal{Y}$ behaves
similar to that of $\mathcal{Z}$. And on the rest, we need to use the
expansion of the tree $T$ (which again may be very poor, but it is a constant
for all the coverings). From this argument we can deduce a spectral gap, which
in turn bounds on the edge expansion by (some variant of) the Cheeger
inequalities.

Note that we totally ignored the weighting systems on the edges and vertices.
The ideas we sketched still work, but we lose even more by the required change
of weighting between $T$, $\mathcal{Z}$ and $\mathcal{Y}$. ∎

Proposition 4.10 and Corollary 4.9 prove that given a fixed complex with a
property $(\tau)$ fundamental group, the family of all its covers have a
uniform lower bound on their cosystols — with coefficients in permutations,
and hence, in particular, also for $\mathbb{F}_{2}$-coefficients. Since there
are many groups with property $(\tau)$, this provides a plethora of examples.
In particular, this applies to all finite sheeted coverings of a complex whose
fundamental group is a lattice in high rank simple Lie groups.

###  4.4. Local to Global expansion

Since the bound in Proposition 4.10 was presented in a qualitative manner — we
intentionally excluded calculations from the proof sketch we provided — we opt
for a different approach which yields quantitative results. This approach
requires one to assume more about the complex in hand than just having a
fundamental group with property $(\tau)$. It needs to be a _local spectral
expander_ , which in turn implies property (T), and thus $(\tau)$, of the
fundamental group (this is Garland’s method [garland1973p], see also
[ollivier2003spectral, ZukPropT, ballmann1997l2]). In most applications, and
specifically in the Ramanujan complexes of Lubotzky–Samuels–Vishne
[LSV2005ramanujan] which were used in [kaufman2016isoperimetric,
evra2016bounded], this condition holds. Moreover, when studying a fixed simple
$p$-adic Lie group $G$ with an associated Bruhat–Tits building $\mathcal{B}$,
this method provides a lower bound on the cosystols of all quotients of
$\mathcal{B}$ uniformly, independent of the acting lattice. To be able to
present the local spectral expansion condition, we need to recall some
spectral definitions of expansion. We follow
[Dikstein_lecture_notes_trickling_down] in our presentation — See also
Appendix A of [harsha2022note], and the original paper by Oppenheim for the
case where the distribution on highest dimensional cells is uniform
[oppenheim2018local].

Let $\mathcal{X}$ be a connected $2$-dimensional simplicial complex. Assume
$\mu_{2}$ is a fully supported distribution on the triangles of $\mathcal{X}$.
Furthermore, assume $\mu_{1}$ and $\mu_{0}$ are descendent from $\mu_{2}$, and
are fully supported. This implies in particular that the complex $\mathcal{X}$
is _pure_ : Every edge (and vertex) participate in some triangle. The link of
a cell $\sigma\in\mathcal{X}$ is the simplicial complex

$\mathcal{X}_{\sigma}=\\{\tau\in\mathcal{X}\mid\tau\cup\sigma\in\mathcal{X},\tau\cap\sigma=\emptyset\\}.$

In the two dimensional case, the only links we will focus on are vertex links,
which are graphs. The links inherit a distribution on their edges as follows:
For every vertex $\sigma$ and edge $e\in\mathcal{X}_{\sigma}$, we have
$\mu_{\sigma,1}(e)=\frac{\mu_{2}(\sigma\cup
e)}{\sum_{e^{\prime}\in\mathcal{X}_{\sigma}(1)}\mu_{2}(\sigma\cup
e^{\prime})}$. The measure on vertices of $\mathcal{X}_{\sigma}$ descends from
$\mu_{\sigma,1}$. Given a simplical complex $\mathcal{X}$, we can define an
adjacency operator $A$ on the complex valued functions on its vertices: Given
$f\colon\mathcal{X}(0)\to\mathbb{C}$,

$Af(v)=\operatorname*{\mathbb{E}}_{u\sim\mu_{v,0}}[f(u)],$

namely, we sample an edge $vu$ according to $\mu_{1}$ conditioned on the edge
containing $v$. Furthermore, we choose the following inner product on
$\mathbb{C}^{\mathcal{X}(0)}$:

$\langle
f,g\rangle=\operatorname*{\mathbb{E}}_{v\sim\mu_{0}}[\overline{f(v)}g(v)].$

The adjacency operator $A$ has the following properties:

  * •

The constant functions are eigenfunctions of it with eigenvalue $1$.

  * •

It is self adjoint with respect to the chosen inner product.

We say that $\mathcal{X}$ is a $\lambda$-spectral expander if the second
eigenvalue of $A$ is bounded by $\lambda$ from above. We say that
$\mathcal{X}$ is a $\lambda$-local spectral expander if the links
$\mathcal{X}_{v}$ are $\lambda$-spectral expanders for all $v\in
V(\mathcal{X})$.

######  Theorem 4.11 (Oppenheim’s trickling down theorem,
[Dikstein_lecture_notes_trickling_down, oppenheim2018local]).

Let $\mathcal{X}$ be a pure, connected, $2$-dimensional simplicial complex
with fully supported descendent measures on its cells. Assume also that
$\mathcal{X}$ is a $\lambda$-local spectral expander for some
$\lambda<\frac{1}{2}$ — namely, that for each vertex $v\in V(\mathcal{X})$,
the link $\mathcal{X}_{v}$ is a $\lambda$-spectral expander. Then
$\mathcal{X}$ is a $\frac{\lambda}{1-\lambda}$-spectral expander.

######  Proposition 4.12 (Weighted Cheeger inequalities: The lower bound).

If $\mathcal{X}$ is a $\lambda$-spectral expander, then
$h_{0}(\mathcal{X},\mathbb{F}_{2})\geq 1-\lambda$.

Though the proof method of Proposition 4.12 is standard, we did not find a
source which proves it in this generality, and decided to indclude it in
Appendix A for completeness.

######  Corollary 4.13.

Let $\mathcal{X}$ be a $\lambda$-local spectral expander for some
$\lambda<\frac{1}{2}$. Then, for every connected covering $\mathcal{Y}$ of
$\mathcal{X}$, we have both
$h_{0}(\mathcal{Y},\mathbb{F}_{2})\geq\frac{1-2\lambda}{1-\lambda}$, and
$CoSyst_{1}(\mathcal{Y},{\rm Sym})\geq\frac{1-2\lambda}{2-2\lambda}$.

###### Proof.

Since links are preserved by coverings, $\mathcal{Y}$ is a $\lambda$-local
spectral expander. Since $\mathcal{Y}$ is connected as well, it satisfies the
conditions of Theorem 4.11, and thus it is a
$\frac{\lambda}{1-\lambda}$-spectral expander. By Proposition 4.12, we deduce
that $h_{0}(\mathcal{Y},\mathbb{F}_{2})\geq
1-\frac{\lambda}{1-\lambda}=\frac{1-2\lambda}{1-\lambda}$. The second claim
follows now from Corollary 4.9. ∎

As mentioned in the introduction, Corollary 4.13 applies uniformly to all the
finite quotients of a Bruhat–Tits building, provided that it is a
$\lambda$-local spectral expander with $\lambda<\frac{1}{2}$ — which, by
choosing $k=0$ in Theorem 4.1 of [dikstein2023coboundary], is typically the
case. In particular, this proves the uniform lower bound on large cosystols in
[kaufman2016isoperimetric, evra2016bounded], in a different manner, at least
for dimension $1$.

##  5\. Bounded degree $2$-dimensional $\mathbb{F}_{2}$-coboundary exapnders

In this section we resolve Problem 1.3 for the special case of dimension $2$.
As oppose to Section 4, where we deduce results about $\mathbb{F}_{2}$
coefficients by using the permutation coefficients framework, here we use a
direct approach, relying heavily on the work of Evra–Kaufman
[evra2016bounded]. This section requires some expertise in the theory of
arithmetic and algebraic groups, but it is not needed for the rest of the
paper.

Let $G$ be a simple $p$-adic Lie group of rank $d\geq 3$, and let
$\mathcal{B}$ be the Bruhat–Tits building of $G$. The building $\mathcal{B}$
is a contractible, infinite, simplicial complex of dimension $d$ which has a
bounded degree — see [tits1979reductive] or Section 3.4 in
[platonov1993algebraic] for the definitions and some background. For every
cocompact lattice $\Gamma$ of $G$, the simplicial complex
$\mathcal{X}={{}_{\Gamma}}\backslash^{\mathcal{B}}$ is finite and of degree
bounded by the degree of $\mathcal{B}$ (which is independent of $\Gamma$). The
following is a corollary from the main theorem of [evra2016bounded]:

######  Theorem 5.1 (Corollary 1.12 in [evra2016bounded]).

For a large enough prime number $p$,
$h_{1}(\mathcal{X},\mathbb{F}_{2})\geq\lambda>0$.

Therefore, to prove the existence of bounded $2$-dimensional coboundary
expanders, it suffices to prove that for some $G$ as above and infinitely many
lattices $\Gamma$ of $G$, the first cohomology of
$\mathcal{X}={{}_{\Gamma}}\backslash^{\mathcal{B}}$ with $\mathbb{F}_{2}$
coefficients vanishes. Now, as $\mathcal{B}$ is contractible,
$H^{1}({{}_{\Gamma}}\backslash^{\mathcal{B}},\mathbb{F}_{2})=H^{1}(\Gamma,\mathbb{F}_{2})$.
But,
$H^{1}(\Gamma,\mathbb{F}_{2})\cong\nicefrac{{\Gamma}}{{[\Gamma,\Gamma]\Gamma^{2}}}$.
Hence:

######  Fact 5.2.

The vanishing of $H^{1}(\mathcal{X},\mathbb{F}_{2})$ is equivalent to the
claim that $\Gamma$ does not have a quotient group of order 2. Equivalently,
$\widehat{\Gamma}$ the profinite completion of $\Gamma$ does not have such a
quotient.

The rest of the section is devoted to an appropriate choice of $G$ and
infinitely many lattices without quotients of order $2$. Note that such
lattices will provide us simplicial complexes of dimension
$d=\textrm{rank}(G)$, but we care only about the $2$-skeleton of these
complexes.

Let $k$ be a number field and $\mathfrak{G}$ a $k$-algebraic group which is
simple, connected and simply connected. Let $\mathbb{A}_{k}$ be the ring of
Adeles of $k$, i.e., $\mathbb{A}_{k}=\prod^{*}_{\nu}k_{\nu}$ where $\nu$ runs
over all norms of $k$ and $k_{\nu}$ is the completion of $k$ with respect to
$\nu$. Let $\mathbb{A}_{k}^{\infty}$ (respectively $\mathbb{A}_{k}^{f}$) be
the product over all the archemedian norms (respectively non-archemedian
norms). Now, $\mathfrak{G}(k)$ is a discrete subgroup embedded diagonally in
$\mathfrak{G}(\mathbb{A}_{k})$, in fact, a lattice. By the strong
approximation theorem (SAT for short, see Section 7.4 in
[platonov1993algebraic]), if for some $\nu_{0}$, $\mathfrak{G}(k_{\nu_{0}})$
is not compact, then $\mathfrak{G}(k)\times\mathfrak{G}(k_{\nu_{0}})$ is dense
in $\mathfrak{G}(\mathbb{A}_{k})$. Equivalently, $\mathfrak{G}(k)$ is dense in
$\mathfrak{G}(\mathbb{A}_{k\setminus\\{\nu_{0}\\}})$, where
$\mathbb{A}_{k\setminus\\{\nu_{0}\\}}=\prod^{*}_{\nu\neq\nu_{0}}k_{\nu}$.

Assume from now on that $\mathfrak{G}(\mathbb{A}_{k}^{\infty})$ is compact.
Fix a non-archemedian norm $\nu_{0}$ where $\nu_{0}\not|\ 2$ — i.e., the prime
associated with $\nu_{0}$ does not lie over the rational prime $2$ — so that
$\mathfrak{G}(k_{\nu_{0}})$ is not compact. Now, for every open compact
subgroup $K$ of $\mathfrak{G}(\mathbb{A}_{k\setminus\\{\nu_{0},\infty\\}})$,
$\Gamma=\mathfrak{G}(k)\cap K$ is a dense subgroup of $K$ (by SAT), but a
discrete subgroup, in fact a lattice, in $\mathfrak{G}(k_{\nu_{0}})$. Assume
further that $\Gamma$ satisfies the congruence subgroup property (CSP for
short, see Section 9.5 in [platonov1993algebraic]). I.e., every finite index
subgroup $\Gamma_{0}$ of $\Gamma$ contains a subgroup of the form $G(K)\cap
K_{0}$, where $K_{0}$ is an open compact subgroup of $K$. Combining with SAT,
this implies that $\widehat{\Gamma}\cong K$.

######  Proposition 5.3.

With the above assumptions; if
$\mathfrak{G}(k_{2}):=\prod_{\nu|2}\mathfrak{G}(k_{\nu})$ has an open compact
subgroup $K_{2}$ with $H^{1}(K_{2},\mathbb{F}_{2})=0$, then
$\mathfrak{G}(k_{\nu_{0}})$ has infinitely many cocompact (torsion free)
lattices $\Gamma_{i}$ with $H^{1}(\Gamma_{i},\mathbb{F}_{2})=0$.

###### Proof.

In the notations above, choose $K=K_{2}\times K^{\prime}$, where $K^{\prime}$
is an open compact subgroup of
$\mathfrak{G}(\mathbb{A}_{k\setminus\\{2,\nu_{0},\infty\\}})$ of the form

$K^{\prime}=\prod_{\nu\notin\\{\infty,2,\nu_{0}\\}}K_{\nu},$

and each $K_{\nu}$ in the product is an open compact subgroup of
$\mathfrak{G}(k_{\nu})$. Let $\Gamma=\mathfrak{G}(k)\cap K$, so $\Gamma$ is a
lattice in $\mathfrak{G}(k_{\nu_{0}})$ and $\widehat{\Gamma}\cong K$.

Now, $\Gamma$ being a cocompact lattice in $\mathfrak{G}(k_{\nu_{0}})$ is
finitely generated, and thus $K$ is a finitely generated profinite group.
Hence, $\dim H^{1}(K,\mathbb{F}_{2})=\dim(\textrm{Hom}(K,\mathbb{F}_{2}))$ is
finite, i.e., for only finitely many $\nu$’s it can happen that
$H^{1}(K_{\nu},\mathbb{F}_{2})\neq 0$. Each of these $K_{\nu}$’s is a
virtually (torsion free) pro-$p$ group, where $p$ is some odd prime. Replace
$K_{\nu}$ by a deep enough finite index subgroup which is (torsion free)
pro-$p$ to ensure that $H^{1}(K_{\nu},\mathbb{F}_{2})=0$. Now
$H^{1}(K,\mathbb{F}_{2})=0$. Fixing some
$\nu^{\prime}\notin\\{\infty,2,\nu_{0}\\}$ which lies over an odd rational
prime $\ell$, choose a sequence of decreasing pro-$\ell$ subgroups
$K_{\nu^{\prime}}(i)$ of $K_{\nu^{\prime}}$ and let

$K(i)=K_{2}\times
K_{\nu^{\prime}}(i)\times\prod_{\nu\notin\\{\infty,2,\nu_{0},\nu^{\prime}\\}}K_{\nu}.$

All in all, if $\Gamma(i)=K(i)\cap\mathfrak{G}(k)$, they all satisfy
$\widehat{\Gamma(i)}=K(i)$, and their first cohomology with $\mathbb{F}_{2}$
coefficients vanishes. ∎

Let us now construct an example that satisfies all the needed
assumptions191919This example will be used again in Section 6.1. Let $D$ be a
quaternion algebra over $\mathbb{Q}$ which ramifies at $\infty$ and at some
rational prime $p_{0}\neq 2$ (cf. [vigneras1980algebres] or
[platonov1993algebraic]). Let $\tau$ be the standard involution of $D$ and
$h\colon D^{n}\times D^{n}\to D$ the canonical sesqui-linear form on $D^{n}$,
i.e.,

$h((x_{1},...,x_{n}),(y_{1},...,y_{n}))=\sum_{i=1}^{n}x_{i}\tau(y_{i}).$

Let $\mathfrak{G}$ be the algebraic group $SU(n,D,h)$, i.e., the $D$-linear
transformations preserving $h$. This is a $\mathbb{Q}$ algebraic group which
is simple, connected and simply connected, of type $C_{n}$, i.e., it is a form
of $Sp(2n)$. See the discussion in Section 5 of [DGLT] (note that there
$p_{0}=2$, but all the results are the same, till the last point), as well as
in [Ghola], and also Section 2.3 in [platonov1993algebraic]. If $p\neq
p_{0},\infty$, then $\mathfrak{G}$ splits over $\mathbb{Q}_{p}$ and
$\mathfrak{G}(\mathbb{Q}_{p})\cong Sp(2n,\mathbb{Q}_{p})$. In particular, for
$p=2$, $\mathfrak{G}(\mathbb{Q}_{2})$ contains an open compact subgroup
$K_{2}=Sp(2n,\mathbb{Z}_{2})$. For $n\geq 3$, $Sp(2n,\mathbb{Z}_{2})$ is a
perfect group.202020This follows from the well known fact that its dense
subgroup $Sp(2n,\mathbb{Z})$ is perfect. In fact, for both it can be read
directly from their Steinberg presentation. Hence, it cannot have abelian
quotients, and in particular $H^{1}(K_{2},\mathbb{F}_{2})=0$. In addition, for
every $p\neq p_{0}$, we get as before many arithmetic lattices $\Gamma$ in
$\mathfrak{G}(\mathbb{Q}_{p})$. By [rapinchuk1989congruence] and
[tomanov1989congruence] all these $\Gamma$’s satisfy the CSP. Using
Proposition 5.3 and Theorem 5.1 , we constructed an infinite families of
bounded degree cocycle expanders with vanishing first cohomology, which are in
turn $1$-coboundary expanders with $\mathbb{F}_{2}$ coefficents, resolving
Problem 1.3 in dimension $2$.

######  Remark 5.4.

  1. (1)

One can deduce the following from the proof: If $G$ is a simple Lie group with
one arithmetic lattice $\Gamma$ satisfying CSP and
$H^{1}(\Gamma,\mathbb{F}_{2})=0,$ then $G$ has infinitely many lattices with
covolume tending to infinity and vanishing first cohomology with
$\mathbb{F}_{2}$ coefficients.

  2. (2)

The previous clause should be compared with the main results of
[lubotzky1987finite], which asserts that every finitely generated not solvable
linear group and in particular the above $\Gamma$ has a sequence of finite
index subgroups $\Gamma^{j}$ with $\dim
H^{1}(\Gamma^{j},\mathbb{F}_{2})\xrightarrow{j\to\infty}\infty.$

  3. (3)

In the above — both in Proposition 5.3 and the previous two clauses — we can
replace $2$ by any fixed rational prime $\ell$.

##  6\. Open problems and suggestions for further research

###  6.1. Cocycle expansion in permutations of $p$-adic lattices implies the
existence of non-sofic groups

In this paper we are following the footsteps of the theory developed for
coboundary expansion over $\mathbb{F}_{2}$ with the goal to generalize it to
${\rm Sym}$. In Section 3, we analyzed the complete complexes and spherical
buildings. In Section 4, we studied the large cosystols condition with
permutation coefficients, and related it to property $(\tau)$ and Garland’s
method. In particular, our analysis applies to quotients of Bruhat–Tits
buildings of simple $p$-adic Lie gropus of high rank. The natural next step
would be to try to prove cocycle expansion with permutation coefficients for
such quotients. Following the foot steps of [kaufman2016isoperimetric,
evra2016bounded, dikstein2023coboundary], one may dare to suggest:

######  Conjecture 6.1.

Let $G$ be simple $p$-adic Lie group of rank $d\geq 3$, and $p\geq p(d)\gg 0$.
Then, for any lattice $\Gamma$ of $G$,

(6.1) $h_{1}({}_{\Gamma}\setminus^{\mathcal{B}},{\rm Sym})>0,$

where $\mathcal{B}$ is the Bruat–Tits building associated with $G$.

Unfortunately, we are currently not able to prove the above. Proving such a
result, even for very special cases can be very significant. Recall:

######  Definition 6.2.

A finitely presented group $\Gamma\cong\langle S|R\rangle$ is said to be
_sofic_ if there is a sequence of functions $f_{n}\colon S\to{\rm Sym}(n)$,
such that

$\forall r\in R\ \colon\ \ d_{h}(f_{n}(r),{\rm Id})\xrightarrow{n\to\infty}0,$

and for every $w\notin\langle\langle R\rangle\rangle$,212121$\langle\langle
R\rangle\rangle$ is the normal subgroup generated by $R$.

$\liminf(d_{h}(f_{n}(w),{\rm Id}))\geq\frac{1}{2}.$

######  Problem 6.3 (Gromov [Gromov_sofic], Weiss [Weiss_Sofic]).

Are there non-sofic groups?

######  Theorem 6.4.

Conjecture 6.1 implies the existence of non-sofic groups

###### Proof.

Recall that if $h_{1}({}_{\Gamma}\setminus^{\mathcal{B}},{\rm Sym})>0,$ then
$\Gamma$ is homomorphism stable with linear rate (see Theorem 1.3 in
[CL_part1]) — which is known to imply flexible stability in permutations.

Let $D$ be a quaternion algebra over $\mathbb{Q}$, which ramifies at infinity
and some rational prime $p_{0}$, as in Section 5. This time, we may take
$p_{0}=2$. Let $\Gamma_{0}$ be the lattice in $Sp(2n,\mathbb{Q}_{p})$ obtained
from such a $D$ as in Section 5, where $p\neq p_{0}$ (see [DGLT], where such
$\Gamma_{0}$ is constructed with $p_{0}=2$). As in [DGLT], by adapting
Deligne’s method to the $p$-adic numbers, $\Gamma_{0}$ has a central extension
$\tilde{\Gamma}_{0}$ with finite center and $\tilde{\Gamma}_{0}$ is not
residually finite. Now, in a paper in preparation of Gohla–Thom [Gohla_Thom]
(see also Corollary 3.4.5 in [Ghola]), they show that for $n\geq 4$, if
$\Gamma_{0}$ is flexibly stable, then $\tilde{\Gamma}_{0}$ is a non-sofic
group. ∎

We should emphasize, that what we need is much weaker than the full force of
Conjecture 6.1. First, we need it only for the group
$G=Sp(2n,\mathbb{Q}_{p})$, where $n$ is some fixed number larger than $4$, and
$p$ a fixed prime, large enough with respect to $n$ (see [Gohla_Thom]). Even
then, it suffices to prove (6.1) for a single lattice $\Gamma_{0}$ and not all
of them. Moreover, we do not need a linear homomorphism stability rate but any
rate would suffice.

Let us put our observation in perspective: The existence of non-sofic groups
is a long standing problem, and many examples of groups have been suggested as
candidates for being non-sofic. For example, finitely generated infinite
simple groups [burger2000lattices], the Burnside groups, the Higman group (cf.
Proposition 6 in Section 1.1 of [Trees_Serre]). But, as of now, these efforts
have not led to a path towards a proof [thom2018finitary,
helfgott2019soficity, kassabov2019soficity].

The work of Bowen–Burton [BowenBurton] suggested a new path. They showed that
if $SL_{n}(\mathbb{Z})$, for $n\geq 5$, is homomorphism stable then there
exists a non-sofic group. There are good reasons to believe that their
methodology can work for many high rank arithmetic groups other than
$SL_{n}(\mathbb{Z})$, including the lattices discussed in [Gohla_Thom]. The
properties of $SL_{n}(\mathbb{Z})$ used in [BowenBurton] are:

  1. (1)

The congruence subgroup property (CSP).

  2. (2)

Existence of two copies of the same non-abelian free group, one Zariski-dense
in $SL_{n}(\mathbb{Z})$, and the other Zariski-dense in a proper simple
algebraic subgroup.

  3. (3)

Super strong approximation of $SL_{n}(\mathbb{Z})$ with respect to all its
congruence subgroups.

Properties $(1)$ and $(2)$ hold for many other arithmetic groups $\Gamma$, but
$(3)$ is not yet known. An ongoing work of Alireza Salehi Golsefidi and others
aims to close this gap. Anyway, for our goal the main missing point is to show
that $\Gamma$ is homomorphism stable.

Gohla–Thom [Gohla_Thom] take a somewhat different path: Let $\Gamma_{0}$ be as
in the proof of Theorem 6.4 (or one of the lattices constructed in Section 5).
In [DGLT], the stability of homomorphisms of $\Gamma$ into the unitary group
with the Frobenius norm, which was deduced from cohomology vanishing results
of Garland [garland1973p], was used to deduce that $\tilde{\Gamma}_{0}$ is not
Frobenius approximated (which is analogous to non-soficity). By imitating this
pattern, [Gohla_Thom] prove that if $\Gamma_{0}$ is homomorphism stable in
permutations then $\tilde{\Gamma}_{0}$ is non-sofic.

Our observation here suggests a technical tool to prove the missing
homomorphism stability of this $\Gamma_{0}$: In [evra2016bounded], the
$\mathbb{F}_{2}$ analogue of Conjecture 6.1 was proved. Furthermore, the
version of Conjecture 6.1 with permutation coefficients, but with respect to
the discrete distance instead of the Hamming one, was proved in
[dikstein2023coboundary]. We hope that the techniques developed in these
papers may lead to a positive resolution of Conjecture 6.1, if not in general,
then at least for some specific cases, such as $\Gamma_{0}$, which imply the
existence of non-sofic groups.

Although we are optimistic, there are several warning signs along the way
which one should consider. First, in [BeckerLubotzky], it was shown that
property $(T)$ groups never have a strict version of homomorhpism stability.
Furthermore, in [ioana2020cohomological] it was shown that
$SL_{n}(\mathbb{Z})$, where $n\geq 3$, does not have the local lifting
property, which is another strngthening of homomorphism stability into
unitaries with the Hilbert–Schmidt norm. Lastly, in [glebsky2022extensions] it
is shown that the central extension $\tilde{\Gamma}_{0}$ above is weakly
sofic, which is, as it sounds, a weakening of the notion of a sofic group.
This means that our cnadidates for being non-sofic are actually weakly sofic!

###  6.2. Bounded expanders in permutations

The following problems are the natural generalizations of the search for
bounded coboundary and cocycle expanders with $\mathbb{F}_{2}$ coefficients
(Problem 1.3) to the permutation setup. Namely, we are looking for infinite
families of connected finite polygonal complexes
$\\{\mathcal{X}_{m}\\}_{m=1}^{\infty}$, which are uniformly bounded, namely
there is a positive integer $k$ such that the degree of every vertex in
$\mathcal{X}_{m}$ is bounded by $k$.

######  Problem 6.5 (Bounded coboundary expanders in permutations).

Is there such a family for which

$\forall m\in\mathbb{N}\ \colon\ \ h^{B}_{0}(\mathcal{X}_{m},{\rm
Sym}),h^{B}_{1}(\mathcal{X}_{m},{\rm Sym})\geq\lambda,$

for some $\lambda>0$ independent of $m$?

This is the permutation analogue of what was constructed in Section 5 for
$\mathbb{F}_{2}$. A potentially easier task is the following:

######  Problem 6.6 (Bounded cocycle expanders with large cosystols in
permutations).

Is there such a family for which

$\forall m\in\mathbb{N}\ \colon\ \ h_{0}(\mathcal{X}_{m},{\rm
Sym}),h_{1}(\mathcal{X}_{m},{\rm Sym}),CoSyst_{1}(\mathcal{X}_{m},{\rm
Sym})\geq\lambda,$

where $\lambda>0$ is independent of $m$?

Solving Problem 6.6 will be the exact Sym analogue of
[kaufman2016isoperimetric] with $\mathbb{F}_{2}$ coefficients.

###  6.3. Random models

Both random simplicial complexes and random group presentations received
significant attention in the recent two decades (cf. [Ollivier2005AJ2,
ollivier2010random, kahle2016random] and the references therein). It is
natural to ask what is the expected stability rate of a random object. It
turns out that these kinds of enquiries are closely related to Problem 6.3,
namely, finding non-sofic groups. A companion paper to this one
[CL_stability_Random_complexes] is devoted to the study of cocycle expansion
of random simplicial complexes in the Linial–Meshulam model
[linial_meshulam2006homological]. In that paper, it is proved that if the
expected cocycle Cheeger constant with permutation coefficients of a random
simplicial complex in the _mid-range_ is bounded away from zero, then there
are non-sofic hyperbolic groups. This would resolve both, the _soficity
problem_ as well as the _residual finiteness of hyperbolic groups_ problem
(cf. [kapovich2000equivalence]). This result is somewhat parallel222222The
result in [CL_stability_Random_complexes] is weaker than Dogon’s in the sense
that a better stability rate of a random complex is assumed there. But, under
these stronger assumptions, the existence of non-sofic hyperbolic groups is
deduced. to a recent work of Dogon [dogon2023flexible], where he proved that
homomorphism stability in unitaries with any rate in the mid-range will imply
the existance of non-hyperlinear groups, which are in turn non-sofic. Both
results call for further study of the stability rate of random objects. We do
suspect that a random object should not be stable in the mid-range, similar to
the way a random code is not locally testable [ben2003some].

###  6.4. Efficient Stability of finite group presentations

Short presentations of finite groups were the focus of many studies — see the
introduction of [guralnick2008presentations]. Though finding short
presentations of a given (family of) finite group(s) is a natural problem,
this search seems to be in conflict with these presentations having a
(uniformly) good stability rate. For example, the work of Ben-
Sasson–Guruswami–Kaufman–Sudan–Viderman [ben2010locally], which proves that
locally testable codes need to be _redundant_ , can be interpreted — in the
language developed further in this section — as a proof that a specific type
of short presentations of certain finite abelian groups must have a cocycle
Cheeger constant that tends to zero with their rank. On the other hand, the
most expansive presentation — the multipilication table one — has, by [BC22],
a lower bound on its Cheeger constant which is independent of the specific
group. This suggests a tradeoff between _shortness_ of a presentation and its
_stability_. It will be interesting to understand this tradeoff better.

Let us be more concrete. Recall that for every given finite group, and any
given presentation of it, its cocycle Cheeger constant in dimension $1$ with
permutation coefficients is positive. But, as was proved in Claim 3.11, one
can choose presentations with a Cheeger constant arbitrarily close to $0$.
Consider a family of finite groups $G_{i}$, given by presentations $\langle
S_{i}|R_{i}\rangle$. The goal is to relate the complexity of these
presentations and their stability rate in a uniform manner. Here, complexity
can have several interpretations: It can be taken, for example, to be
$\log|S|\cdot\sum_{r\in R}|r|$, where $|r|$ is the length of the relation $r$,
or to be the bit length of an encoding of the presentation (which can be
shorter due to the fact exponents can be written in binary and not unary).

For a first example, take the groups $\mathbb{F}_{2}^{k}$ for $k\to\infty$. On
the one hand, their multiplication table presentations, which are
exponentially more complicated than the shortest possible presentations, have
a cocycle Cheeger constant of at least $\frac{1}{3000}$ regardless of $k$. On
the other hand, the much shorter presentation on $k$ generators, where every
generator is required to be of order $2$, and every pair of generators are
required to commute, have cocycle Cheeger constants which are $O(\frac{1}{k})$
(see [kozlov2019quantitative, CVY_efficient]). Furthermore, in
[ben2010locally] it is shown that if $\mathbb{F}_{2}^{k}$ is presented as a
quotient of $\mathbb{F}_{2}^{n}$ (equipped with the above short presentation)
and one adds only $n-k$ new relations and the associated code has linear
distance, then the Cheeger constant tends to zero with $k\to\infty.$

The second natural example to study, which is completely open, is that of
finite simple groups. Clearly, studying the stability rate of various standard
presentations of the alternating and symmetric groups seem to be a natural
problem. But, we want to highlight the following case: The groups
$SL_{n}(\mathbb{F}_{p})$ (and more generally, groups of Lie type) have two
outstanding families of presentations —

  1. (1)

The Steinberg presentations: Let $e_{ij}(a)$ be the matrices with
$a\in\mathbb{F}_{p}$ in the $ij^{\rm th}$ position, and $0$ evereywhere else.
For every $i\neq j$ and $a\in\mathbb{F}_{p}$, let $U_{ij}(a)={\rm
Id}+e_{ij}(a)$. Take the $U_{ij}(a)$’s as generators, and the relations to be
$U_{ij}(a)U_{ij}(b)=U_{ij}(a+b)$ and for every $i\neq j,k\neq\ell$ and
$i\neq\ell$, $[U_{ij}(a),U_{k\ell}(b)]={\bf 1}_{j=k}U_{i\ell}(a\cdot b)$. The
complexity of this presentation is $\Omega(p)$, which is polynomial in the
size of the group — namely, an expansive presentation.

  2. (2)

The Guralnik–Kantor–Kassabov–Lubotzky presentations: Here, we do not describe
the presentations in full, but describe their complexity. There is a constant
$C$, such that regardless of $p$ and $n$, the presentations use less than $C$
generators, less than $C$ relations, and the length of the relations is at
most $C(\log n+\log p)$. See [guralnick2008presentations,
lubotzky2010presentations] for all the details. The complexity of these
presentations is logarithmic in the size of the group. Note that when one
fixes $p$ and lets $n\to\infty$, these presentations are of complexity which
is even $\log\log$ the size of the group.

In the spirit of the more understood abelian case, we conjecture the
following:

######  Conjecture 6.7.

There is a uniform lower bound on the cocycle Cheeger constant in permutations
of the Steinberg presentations, at least when fixing $n$ and tending $p$ to
$\infty$. On the contrary, the cocycle Cheeger constants in permutations of
the GKKL presentations tend to zero when either $n$ or $p$ tending to
$\infty$.

######  Remark 6.8.

Note that the length of the relations in the GKKL presentations is not
bounded. This is not natural in the viewpoint of property testing, since it
implies a non-bounded query complexity for the tester. Nevertheless, one can
study the triangulated versions of these presentations, and amend this
problem.

We now want to make the tradeoff problem between shortness and stability rate
even more concrete. To that end, recall the recent MIP*=RE breakthrough
[MIPRE] in quantum information theory, which resolved Connes’ embedding
problem (cf. [Cap_Lup_Sofic_Hyperlinear_book]). A major technical tool, which
was developed and used in this work, is a quantum soundness result on a
specific two player non-local game based on the individual degree Reed–Muller
code [quantum_soundness_tensor_codes]. As is explained in [CVY_efficient],
this quantum soundness result can be interpreted as a lower bound on the
cocycle stabilty rate of certain presentations of $\mathbb{F}_{2}^{k}$, but
with coefficients in unitaries equipped with the Hilbert–Schmidt metric rather
than in permutations equipped with the Hamming metric. Inspired by this deep
result, we suggest the following parameter setting as a challenge.

######  Problem 6.9 (Efficient stability in permutations).

Find a family of finite groups $\\{G\\}$, with presentations $G\cong\langle
S|R\rangle$, such that:

  * •

_The presentation is (somewhat) short_ :

$\begin{split}|S|,|R|&=\textrm{polylog}(|G|)\\\ \forall r\in R\
\colon|r|&=\textrm{polylog}(|G|).\end{split}$

  * •

_The stability rate is good_ : $\langle S|R\rangle$ is $\rho$-stable, and
$\rho(\varepsilon)=\textrm{polyloglog}(|G|)\cdot\varepsilon^{c}$ for some
$c>0$ independent of $|G|$.

######  Remark 6.10.

It would be more natural to ask for $\rho(\varepsilon)\leq C\varepsilon^{c}$
for two universal constants $c,C>0$. But, because of gap amplification
techniques such as parallel repetition, the $\textrm{polyloglog}(|G|)$ term is
good enough for applications.

The motivation for this parameter setting is that it allows for _randomness
generation_ in certain contexts — see the way [quantum_soundness_tensor_codes]
is used in [MIPRE]. Though Problem 6.9 is of intrinsic interest, we are
interested in it because it may help to resolve the Aldous–Lyons conjecture
regarding the existence of non-cosofic invariant random subgroups of the free
group [Aldous_Lyons_Conj] (see the preprint [BCLV_subgroup_tests]). We now
formulate a more specific version of Problem 6.9, which would be enough for
this application.

######  Problem 6.11 (Locally testable codes with permutation coefficients).

Given a matrix $A\in M_{m\times n}(\mathbb{F}_{2})$, one can define the
following presentation of $\mathbb{F}_{2}^{k}$, where $k=n-\textrm{rank}(A)$:
The set of generators is $S=\\{x_{i}\\}_{i\in[n]}$. The set of relations $R$
will contain:

  * •

_Order $2$ relations_: $\\{x_{i}^{2}\\}_{i\in[n]}$.

  * •

_Commutation relations_ : $\\{x_{i}x_{j}x_{i}^{-1}x_{j}^{-1}\\}_{i,j\in[n]}$.

  * •

_Linear relations induced by $A$_: $\mathopen{}\mathclose{{}\left\\{\prod
x_{j}^{A_{ij}}}\right\\}_{i\in[m]}$.

Now, a code $\textrm{Ker}(A)$ is $\rho$-locally testable (when tested by the
matrix tester — Algorithm 2 in Section 3.1 of [CL_part1]) if and only if it is
$\rho$-stable for the above presentation, when the range of the input
functions is restricted to ${\rm Sym}(2)$. What about the case where the
inputs are not restricted to be with range ${\rm Sym}(2)$, but any ${\rm
Sym}(n)$? Namely, what can be said about the homomorphism stability rate of
the above presentation for a given code? For the Hadamard code the resulting
presentation is essentially the multiplication table of $\mathbb{F}_{2}^{k}$,
and is thus stable but expansive. What about more _reasonably sized_ codes,
such as Reed–Muller codes? Or, the recently constructed good locally testable
codes [LTC_DELLM, LTC_Panteleev_Kalachev]?

One of our motivations to study covering stability was that, in this
framework, one can potentially translate stability results with unitary
coefficients equipped with the Hilbert–Schmidt metric to the discrete setup of
permutations with normalized Hamming metric. To that end, it would be useful
to have a Poincare-type inequality (cf. Lemma 5.4 in [CL_part1]) on the metric
space $U(n)/{\rm Sym}(n)$, with constants independent of $n$. We learened from
Assaf Naor that the metric space $M(n)/{\rm Sym}(n)$ does not have a Poincare-
type inequality on it which is independent of $n$, due to
[andoni2018snowflake]. But, the case of $U(n)/{\rm Sym}(n)$ seems to be open,
and will be sufficient for us to translate the results of
[quantum_soundness_tensor_codes] to the permutation setup.

##  Appendix A Weighted Cheeger lower bound

The following argument is very standard. It appeared in its uniformly weighted
form in Proposition 5.5 and Remark 5.7 in Part I of this paper [CL_part1],
using the $L^{2}$-Poincare inequality described in Lemma 5.4. See also
[Dodziuk_Cheeger, Alon_Cheeger_2, ALON_Milman_Cheeger_1] for the original
proofs. The main idea is to use the Reyleigh quotient definition of the second
largest eigenvalue. We add it only for completeness.

###### Proof of Proposition 4.12.

Let $\alpha\colon V(\mathcal{X})\to\mathbb{F}_{2}$ be a non-coboundary
$0$-cochain. Let $B$ be the support of $\alpha$, and let $\beta=\mu_{0}(B)$.
Define $f\colon V(\mathcal{X})\to\mathbb{R}$ as follows:

$f(v)=\begin{cases}1-\beta&v\in B,\\\ -\beta&v\notin B.\end{cases}$

Note that

$\langle f,{\bf
1}\rangle=\operatorname*{\mathbb{E}}_{v\sim\mu_{0}}[f(v)]=\mu_{0}(B)(1-\beta)-\mu_{0}(\bar{B})\beta=0,$

where $\bar{B}$ is the complement of $B$ in $V(\mathcal{X})$, and that

$\langle
f,f\rangle=\operatorname*{\mathbb{E}}_{v\sim\mu_{0}}[f(v)^{2}]=\beta(1-\beta)^{2}+(1-\beta)\beta^{2}=\beta(1-\beta).$

Hence, by the Rayleigh quotient definition of the second eigenvalue of an
operator, we have

$\langle f,Af\rangle\leq\lambda\langle f,f\rangle=\lambda\beta(1-\beta).$

On the other hand,

$\begin{split}\langle
f,Af\rangle&=\operatorname*{\mathbb{E}}_{xy\sim\mu_{1}}[f(x)f(y)]\\\
&=-2\mu_{1}(E(B,\bar{B}))\beta(1-\beta)+\mu_{1}(E(B,B))(1-\beta)^{2}+\mu_{1}(E(\bar{B},\bar{B}))\beta^{2},\end{split}$

where $E(C,D)$ is the set of oriented edges in
$\overrightarrow{\mathcal{X}}(1)$ with origin in $C$ and endpoint in $D$. Note
that by definition,
$2\mu_{1}(E(B,\bar{B}))=\mu_{1}(E(B,\bar{B}))+\mu_{1}(E(\bar{B},B))=\|\delta\alpha\|$.
Furthermore,
$d(\alpha,Z^{0}(\mathcal{X},\mathbb{F}_{2}))=\min(\beta,1-\beta)$. Now, when
sampling an edge $xy\sim\mu_{1}$, the probability $x\in B$ is $\beta$ by the
fact $\mu_{0}$ is descending from $\mu_{1}$. Hence,
$\mu_{1}(E(B,B))=\mu_{1}(B,\mathcal{X}(0))-\mu_{1}(E(B,\bar{B}))=\beta-0.5\|\delta\alpha\|$.
Similarly, $\mu_{1}(E(\bar{B},\bar{B}))=(1-\beta)-0.5\|\delta\alpha\|$. All in
all,

$\begin{split}\langle
f,Af\rangle&=-\|\delta\alpha\|\beta(1-\beta)+(\beta-0.5\|\delta\alpha\|)(1-\beta)^{2}+(1-\beta-0.5\|\delta\alpha\|)\beta^{2}\\\
&=-0.5\|\delta\alpha\|+\beta(1-\beta).\end{split}$

Combining all, we get

$0.5\|\delta\alpha\|\geq(1-\lambda)\beta(1-\beta)\geq(1-\lambda)\cdot\frac{\min(\beta,1-\beta)}{2},$

which finishes the proof by multiplying both sides of the inequality by $2$. ∎

## References