# Stability of Homomorphisms, Coverings and Cocycles I:
Equivalence

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.

This paper is motivated by recent developments in group stability, high
dimensional expansion, local testability of error correcting codes and
topological property testing. In Part I, we formulate and motivate three
stability problems:

  * •

_Homomorphism stability_ : Are almost homomorphisms close to homomorphisms?

  * •

_Covering stability_ : Are almost coverings of a cell complex close to genuine
coverings of it?

  * •

_Cocycle stability_ : Are $1$-cochains whose coboundary is small close to
$1$-cocycles?

We then prove that these three problems are equivalent.

In Part II of this paper [CL_part2], we present examples of stable (and
unstable) complexes, discuss various applications of our new perspective, and
provide a plethora of open problems and further research directions. In
another companion paper [CL_stability_Random_complexes], we study the
stability rates of random simplicial complexes in the Linial–Meshulam model.

##  1\. Introduction

Property testing, a deep and popular area of theoretical computer science, is
the study of algorithmic local to global phenomena. A property tester is a
randomized algorithm which aims to infer global properties of an object by
applying a few random local checks on it (see Section 2). Property testing
plays a major role in some of the most celebrated results in theoretical
computer science. These include the PCP theorem [PCP_thm, dinur2007pcp,
radhakrishnan2007dinur], good locally testable codes [LTC_DELLM,
dinur2022good, LTC_Panteleev_Kalachev], and the recent complexity theoretic
refutation of Connes’ embedding problem [MIPRE].

Classically, functional properties were studied, such as linearity [BLR] and
being a low-degree polynomial [BFL91], as well as properties of graphs such as
$k$-colorability [Alon_Kriv_k-colorability]. In recent years, group theorists
began studying whether being a permutation solution to a system of group
equations is a testable property (cf. [GlebskyRivera, ArzhantsevaPaunescu,
becker2022testability, becker_Mosheiff_Luobtzky2022testability]). For example,
given a pair of almost commuting permutations, are they close to a commuting
pair? By associating between systems of group equations and group
presentations, this problem can be framed as an instance of homomorphism
testing. Namely, in the spirit of Ulam’s stability problem [Ulam], this is the
study of whether an approximate group homomorphism is close to a genuine one.
This framework generalizes the linearity test of [BLR], as well as the local
testability of error correcting codes (cf. [LTC_DELLM]), as we discuss in
Section 3.1.

Even more recently, Dinur–Meshulam [Dinur-Meshulam] initiated the study of
topological property testing. In their paper, they study whether being a
topological covering is a testable property. Namely, are near coverings of a
given complex close to actual coverings of it? Furthermore, they relate this
problem to the first cohomology of the underlying complex, and a new high
dimensional expansion parameter of it.

In this paper, we give an alternative setup for testing coverings, and
consequently a different cohomological viewpoint from the one used in [Dinur-
Meshulam].111We describe the difference in Section 4.4. In our setup, the
parameter acquired by the cohomological viewpoint is equivalent to the
covering testing parameter (as oppose to [Dinur-Meshulam] in which they only
bound one another). Moreover, both the cohomological and covering parameters
are related to the homomorphism testing parameter of the fundamental group of
the underlying complex. We intentionally chose to view these stability
problems through the property testing lens. One can present these problems in
a purely algebraic manner, but we believe property testing perspective is
important for future applications, as well as to understand better the
mechanisms involved. At the end of this paper, we discuss a slight
generalization of our framework, in which our main Theorems 1.1,1.2 and 1.3
still hold.

The second part of this paper [CL_part2] provides several elementary examples
of stable complexes, namely complexes where the local perspective implies a
global structure – almost coverings of it are close to genuine coverings, and
thus almost cocycles are close to cocycles and almost homomorphisms of its
fundamental group are close to actual homomorphisms of the group. In addition,
large cosystols of a complex are related to property (T) of its fundamental
group. Furthermore, a family of bounded $2$-dimensional coboundary expanders
with $\mathbb{F}_{2}$ coefficients is provided, resolving a special case of a
problem due to Gromov. Lastly, we discuss several potential avenues of
enquiry, including novel ways to tackle (but, not yet solve) the _existance of
non-sofic groups_ problem (See Problem 3.6).

Let us now define our objects of study. As oppose to the body of the paper,
here we give a concise presentation of the notions of interest — homomorphism
stability, covering stability and cocycle stability — in a purely algebraic
manner, with no additional motivation. For a more thorough and motivational
presentation of these notions, see Sections 3, 4 and 5. In the rest of this
section, $\rho\colon\mathbb{R}_{\geq 0}\to\mathbb{R}_{\geq 0}$ is a _rate
function_ (Definition 2.1), namely it is non-decreasing and satisfies
$\rho(\varepsilon)\xrightarrow{\varepsilon\to 0}0$.

### Homomrphism stability

Let $\Gamma\cong\langle S|R\rangle$ be a _finite_ group presentation, i.e.,
$S$ and $R$ are finite sets. Let ${\rm Sym}(n)$ be the symmetric group acting
on $[n]=\\{1,...,n\\}$. Every map $f\colon S\to{\rm Sym}(n)$ uniquely extends
to a homomorphism from the free group $f\colon\mathcal{F}(S)\to{\rm Sym}(n)$.
This homomorphism factors through $\Gamma$ if and only if for every $r\in R$
we have $f(r)={\rm Id}$. Hence, our local measurement for being a homomorphism
would be how much is this condition violated. Namely, the _homomorphism local
defect_ of $f$ is

${\rm def}_{hom}(f)=\operatorname*{\mathbb{P}}_{\begin{subarray}{c}i\in[n]\\\
r\in R\end{subarray}}[f(r).i\neq i]\leq\varepsilon,$

where the probability is the uniform one.222Other probability distributions
over $R$ can and should be discussed, though in this paper we focus on the
uniform one. For more on that, see Section 3.1, Section 7 and the second part
of this paper [CL_part2]. 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

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

This allows us to measure the distance between maps $f\colon S\to{\rm Sym}(n)$
and $g\colon S\to{\rm Sym}(N)$ as the expected value of the distances between
their evaluation points,333Again, there are reasons to take other
distributions over $S$ that are not the uniform one. See Section 7 and the
second part of this paper [CL_part2] for more on that. i.e.,

(1.1) $d_{h}(f,g)=\operatorname*{\mathbb{E}}_{s\in S}[d_{h}(f(s),g(s))].$

The _homomorphism global defect_ of $f$ is its distance to the closest genuine
homomorphism, namely

${\rm Def}_{hom}(f)=\inf\\{d_{h}(f,\varphi)\mid N\geq n,\ \varphi\colon
S\to{\rm Sym}(N),\ {\rm def}_{hom}(\varphi)=0\\}.$

The presentation $\langle S|R\rangle$ is said to be _$\rho$ -homomorphism
stable_ if ${\rm Def}_{hom}(f)\leq\rho({\rm def}_{hom}(f))$ for every map
$f\colon S\to{\rm Sym}(n)$.

### Covering stability

Recall that a _polygonal complex_ is a $2$-dimensional cell complex whose
$2$-cells are polygons. The most popular example is that of $2$-dimensional
simplicial complexes, in which the pasted polygons are all triangles. Another
popular example is that of $2$-dimensional cube complexes (cf.
[sageev1995ends]), in which all pasted polygons are quadrilaterals. In our
setup, polygons are not of any unique or bounded length.

A combinatorial map $f\colon\mathcal{Y}\to\mathcal{X}$ between two complexes
is a function that maps $i$-cells of $\mathcal{Y}$ to $i$-cells of
$\mathcal{X}$ in an incident preserving manner. Hence, by defining the map on
$G(\mathcal{Y})$, the underlying graph of $\mathcal{Y}$, there is at most one
way of extending it to all paths in $G(\mathcal{Y})$, and thus to extend it to
the polygons of $\mathcal{Y}$. A combinatorial map $f$ from a graph
$\mathcal{G}$ to a complex $\mathcal{X}$ is a _genuine covering_ , if one can
add polygons to $\mathcal{G}$ and extend $f$ accordingly so that $f$ becomes a
topological covering.

Assume $f$ was already a covering of the underlying graph of $\mathcal{X}$. By
the path lifting property of topological coverings (See Proposition 1.30, page
60, in [Hatcher_Alg_Top]), for every closed path $\pi$ in $G(\mathcal{X})$
which originates at a vertex $x\in V(\mathcal{X})$, and for every vertex
$x^{\prime}$ in the fiber $f^{-1}(x)\subseteq V(\mathcal{G})$, one can lift
$\pi$ to a path $\pi^{\prime}$ in $\mathcal{G}$ which originates at
$x^{\prime}$ and satisfies $f(\pi^{\prime})=\pi$. Even if the original path
$\pi$ was closed, the lifted path $\pi^{\prime}$ may be either open or closed.
Now, $f$ is a genuine covering if and only if for every polygon $\pi$ in
$\mathcal{X}$ and every $x^{\prime}\in f^{-1}(x)$ the lifted path
$\pi^{\prime}$ is closed. Hence, we can define the _covering local defect_ of
$f$ to be

${\rm
def}_{cover}(f)=\operatorname*{\mathbb{P}}_{\begin{subarray}{c}\pi\in\overrightarrow{P}(\mathcal{X})\\\
x^{\prime}\in
f^{-1}(x)\end{subarray}}\mathopen{}\mathclose{{}\left[\textrm{The\ lift\ of}\
\pi\ \textrm{to\ }x^{\prime}\textrm{\ is\ open}}\right],$

where $\overrightarrow{P}(\mathcal{X})$ is the set of oriented polygons in
$\mathcal{X}$.

There is a natural measure of distance between graphs, which is called the
(normalized) _edit distance_. In Section 4.1 we provide a rigorous definition
(4.1), but in essence it measures how many edges need to be
changed/deleted/added to move from the smaller graph to the larger one. This
metric can also be defined on the category of $\mathcal{X}$-labeled graphs,
namely graphs $\mathcal{Y}$ with a fixed combinatorial map into $\mathcal{X}$.
Thus, the _covering global defect_ ${\rm Def}_{cover}(f)$ of
$f\colon\mathcal{Y}\to\mathcal{X}$ would be its normalized edit distance to
the closest genuine covering $\varphi\colon\mathcal{Z}\to\mathcal{X}$ in the
category of $\mathcal{X}$-labeled graphs. The complex $\mathcal{X}$ is _$\rho$
-covering stable_ if ${\rm Def}_{cover}(f)\leq\rho({\rm def}_{cover}(f))$ for
every such $f$.

### Cocycle stability

Let $\mathcal{X}$ be a polygonal complex. An anti-symmetric map from
$\overrightarrow{E}(\mathcal{X})$, the oriented edges of $\mathcal{X}$, to
${\rm Sym}(n)$ is called a _$1$ -cochain with permutation coefficients_. In a
similar manner to combinatorial maps, these $1$-cochains extend in a unique
way to paths in the underlying graph $G(\mathcal{X})$. A $1$-cochain $\alpha$
is said to be a _$1$ -cocycle_, if for every (oriented) polygon $\pi$ we have
$\alpha(\pi)={\rm Id}$. Hence, we can define the _cocycle local defect_ of
$\alpha$ to be

${\rm
def}_{cocyc}(\alpha)=\operatorname*{\mathbb{P}}_{\begin{subarray}{c}i\in[n]\\\
\pi\in\overrightarrow{P}(\mathcal{X})\end{subarray}}[\alpha(\pi).i\neq i].$

We already defined in (1.1) a measure of distance between maps from a fixed
set to (potentially varying) permutation groups. Therefore, we have a measure
of distance between $1$-cochains. Then, the _cocycle global defect_ ${\rm
Def}_{cocyc}(\alpha)$ is the distance of $\alpha$ to the closest $1$-cocycle.
As before, $\mathcal{X}$ is _$\rho$ -cocycle stable_ if ${\rm
Def}_{cover}(\alpha)\leq\rho({\rm def}_{cover}(\alpha))$ for every $1$-cochain
$\alpha$.

### Our results

Given a polygonal complex $\mathcal{X}$ together with a base point
$*\in\mathcal{X}$, the _fundamental group_ $\pi_{1}(\mathcal{X},*)$ is the
collection of loops based at $*$ up to homotopy equivalence. Furthermore, if
$*$ is chosen to be a vertex of the underlying graph $G(\mathcal{X})$, then by
retracting any spanning tree of $G(\mathcal{X})$ we acquire a presentation of
$\pi_{1}(\mathcal{X},*)$ (See Definition 6.5). On the other hand, for any
group presentation $\Gamma=\langle S|R\rangle$, one can construct its
_presentation complex_ $\mathcal{X}_{\langle S|R\rangle}$, whose fundamental
group is isomorphic to $\Gamma$ (See Definition 6.4). The main goal (of this
part) of the paper is to prove the following equivalences.

######  Theorem 1.1.

Let $\mathcal{X}$ be a connected polygonal complex. Then, the following are
equivalent:

  * •

$\mathcal{X}$ is $\rho$-cocycle stable.

  * •

$\mathcal{X}$ is $\rho$-covering stable.

Note that the rate $\rho$ is the same in both.

######  Theorem 1.2.

Let $\Gamma\cong\langle S|R\rangle$ be a group presentation with
$|S|,|R|<\infty$. Let $\mathcal{X}_{\langle S|R\rangle}$ be the presentation
complex associated with $\langle S|R\rangle$. Then, the following are
equivalent:

  * •

$\mathcal{X}_{\langle S|R\rangle}$ is $\rho$-cocycle stable.

  * •

$\langle S|R\rangle$ is $\rho$-homomorphism stable.

Again, $\rho$ is the exact same rate.

######  Theorem 1.3.

Let $\mathcal{X}$ be a connected polygonal complex, and $*$ a vertex of
$\mathcal{X}$. Let $T$ be a spanning tree of $G(\mathcal{X})$, and let
$\pi_{1}(\mathcal{X},*)\cong\langle S|R\rangle$ be the presentation of the
fundamental group of $\mathcal{X}$ associated with retracting $T$ to the
basepoint $*$. Then

  1. (1)

If $\langle S|R\rangle$ is $\rho$-homomorphism stable, then $\mathcal{X}$ is
$\rho$-cocycle stable.

  2. (2)

If $\mathcal{X}$ is $\rho$-cocycle stable, then $\langle S|R\rangle$ is
$\mathopen{}\mathclose{{}\left(|\overrightarrow{E}(\mathcal{X})|\cdot\rho}\right)$-homomorphism
stable, where $|\overrightarrow{E}(\mathcal{X})|$ is the number of edges in
$\mathcal{X}$.

Though not as tight as Theorems 1.1 and 1.2, Theorem 1.3 still implies a
qualitative equivalence, and in many contexts – see for example the discussion
in Section 3.2 – it is enough.

Our notion of homomorphism stability is usually called _flexible pointwise
stability in permutations_ in the literature (cf. [BeckerLubotzky]), and it is
a thoroughly studied topic. Hence, using clause $(1)$ of Theorem 1.3, there
are _off the shelf_ examples of complexes with known stability rates. For
example, by [levit_lazarovich2019surface], triangulations of compact surfaces
of genus $g\geq 2$ are $\rho$-stable with rate
$\rho(\varepsilon)=\Theta(-\varepsilon\log\varepsilon)$. While, by
[BeckerMosheiff], when $g=1$ the surface is $\rho$-stable with $\rho$ being
$\Omega(\sqrt{\varepsilon})$ and $O(\varepsilon^{\frac{1}{4}})$. In the second
part of this paper [CL_part2], we provide elementary examples of complexes
with linear stability rate.

######  Remark 1.4.

As oppose to Theorem 1.1, Theorems 1.2 and 1.3 can be framed in much greater
generality than presented here. Our proof method applies to any metric
coefficient group — not only permutations equipped with the Hamming metric. We
thus relate flexible Hilbert–Schmidt stability [HadwinShulman,
BeckerLubotzky], Frobenius norm stability [DGLT, LubotzkyOppenheim] and so on
to a stability criterion for cocycles. See Corollary 6.6.

Part I of the paper is organized as follows: In Section 2 we define all
property testing related notions. In Section 3 we define and motivate
homomorphism stability of group presentations. In Section 4 we define and
motivate covering stability of polygonal complexes. In Section 5 we define and
motivate cocycle stability of polygonal complexes. The motivational parts of
Sections 3, 4 and 5 are more involved, and can be skipped by the non-expert or
first time reader. Section 6 is devoted to the proofs of Theorems 1.1,1.2 and
1.3. In Section 7 we provide a generalization of our framework, in which
Theorems 1.1,1.2 and 1.3 still hold.

### Acknowledgements

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\. Property testing

The goal of a property tester is to decide whether a given function satisfies
a specific property by querying it at a few random evaluation points. Such a
tester cannot decide with certainty that the function satisfies the property,
since it may require reading all the values of the function. Hence, a property
tester is good given that it satisfies the following: As the rejection
probability of the test gets smaller, the closer the function in hand is to
another function which has the property. We now make this paragraph precise.
For a thorough introduction to the theory, see [Goldreich].

Let ${\mathfrak{D}}$ and ${\mathfrak{R}}$ be collections of finite sets. Let
${\mathfrak{F}}$ be the collection of functions whose domain is from
${\mathfrak{D}}$ and range is from ${\mathfrak{R}}$, namely

${\mathfrak{F}}=\\{f\colon D\to R\mid
D\in{\mathfrak{D}},R\in{\mathfrak{R}}\\}.$

Let $f_{1}\colon D_{1}\to R_{1}$ and $f_{2}\colon D_{2}\to R_{2}$ be two
functions from ${\mathfrak{F}}$. The _Hamming distance with errors_ between
them is defined as follows:

(2.1) $d_{H}(f_{1},f_{2})=|D_{2}\setminus D_{1}|+|D_{1}\setminus
D_{2}|+|\\{x\in D_{1}\cap D_{2}\mid f_{1}(x)\neq f_{2}(x)\\}|.$

When $D_{1}=D_{2}$, this notion agrees with the usual Hamming distance between
functions. If for every $f\colon D\to R$ and $x\notin D$ we define
$f(x)={\mathfrak{error}}$, and we assume that ${\mathfrak{error}}\notin
R^{\prime}$ for any $R^{\prime}\in{\mathfrak{R}}$, then we can equivalently
define

$d_{H}(f_{1},f_{2})=|\\{x\in D_{1}\cup D_{2}\mid f_{1}(x)\neq f_{2}(x)\\}|,$

which is the usual way the Hamming distance is defined. Though the Hamming
distance with errors is a good metric, it outputs natural numbers and cannot
tend to zero without being zero. Hence, we usually normalize it in some way.
The most common normalization is the following, which we call the _normalized
Hamming distance with errors_ :

(2.2) $d_{h}(f_{1},f_{2})=\frac{d_{H}(f_{1},f_{2})}{|D_{1}\cup
D_{2}|}=\operatorname*{\mathbb{P}}_{x\in D_{1}\cup D_{2}}[f_{1}(x)\neq
f_{2}(x)],$

where $\operatorname*{\mathbb{P}}_{x\in A}$ is the uniform probability on $A$.
As we further discuss in Section 7, and specifically in Claim 7.1, in certain
cases other probability distributions are more natural. But, we stick to the
uniform distribution for most of Part I of the paper.

Let ${\mathfrak{P}}$ be a subset of ${\mathfrak{F}}$. We think of
${\mathfrak{P}}$ as the collection of functions in ${\mathfrak{F}}$ that
satisfy a certain property. The ${\mathfrak{P}}$-_global defect_ of a function
$f\in{\mathfrak{F}}$ is

${\rm
Def}_{\mathfrak{P}}(f)=\inf\\{d_{h}(f,\varphi)\mid\varphi\in{\mathfrak{P}}\\}.$

A _tester_ for ${\mathfrak{P}}$ is a randomized algorithm $\mathcal{T}$ that
receives as input a black box version444The way $\mathcal{T}$ interacts with
$f$ is by sending to it an evaluation point $x\in D$ and receiving back the
value $f(x)\in R.$ of a function $f\colon D\to R$ in ${\mathfrak{F}}$ and
needs to decide whether $f\in{\mathfrak{P}}$. The way it operates is as
follows:

  * •

Sampling phase: $\mathcal{T}$ randomly chooses an evaluation point $x_{1}\in
D$ and sends it to $f$. The function $f$ answers with $f(x_{1})$. According to
this value, $\mathcal{T}$ either asks for another evaluation point $x_{2}\in
D$ (which may depend on $f(x_{1})$), or moves to the next phase. $\mathcal{T}$
is allowed to repeat this process for at most $q$ rounds, where $q$ is
independent of $f$.555In certain contexts, and for some applications, $q$ may
be allowed to grow with $f$. Mainly, to make the stability rate $\rho$ (See
Definition 2.2) better using parallel repetition (cf. [Raz_Parallel_Rep_paper,
Raz_parallel_rep_survey]), or when $f$ is encoding an exponentially larger
function in a succinct way (cf. [BFL91]). Actually, this flexibility is
crucial for the applications of efficient stability mentioned in Section 6.4
of [CL_part2].  The maximum number of sampled points $q$ is called _the query
complexity of $\mathcal{T}$_.666The term _locality_ is also commonly used for
$q$ (cf. [LTC_DELLM]).

  * •

Decision phase: According to the outputs $f(x_{1}),...,f(x_{q})$, the tester
$\mathcal{T}$ decides whether to accept (namely, it decides that
$f\in{\mathfrak{P}}$) or reject (namely, it decides that
$f\notin{\mathfrak{P}}$).

The _${\mathfrak{P}}$ -local defect_ of a function $f\in{\mathfrak{F}}$ is its
rejection probability in $\mathcal{T}$, namely

(2.3) ${\rm def}_{\mathfrak{P}}(f)=\operatorname*{\mathbb{P}}[\mathcal{T}\
\textrm{rejects}\ f],$

where the probability runs over all possible sampling phases.

######  Definition 2.1.

A non-decreasing function $\rho\colon\mathbb{R}_{\geq 0}\to\mathbb{R}_{\geq
0}$ satisfying $\rho(\varepsilon)\xrightarrow{\varepsilon\to 0}0$ will be
called a _rate function_.

######  Definition 2.2.

The tester $\mathcal{T}$ is _complete_ if

$\forall f\in{\mathfrak{F}}\ \colon\ \ {\rm def}_{\mathfrak{P}}(f)=0\iff
f\in{\mathfrak{P}}.$

Namely, functions that satisfy the property are always accepted, and all other
functions are rejected with some positive probability.

Let $\rho$ be a rate function as in Definition 2.1. The tester $\mathcal{T}$
is said to be $\rho$-_stable_ 777This notion is also called _$\rho$
-robustness_ and _$\rho$ -soundness_ in the literature., if

$\forall f\in{\mathfrak{F}}\ \colon\ \ {\rm
Def}_{\mathfrak{P}}(f)\leq\rho({\rm def}_{\mathfrak{P}}(f)).$

##  3\. Homomorphism stability of group presentations

In 1940, Ulam raised the following problem:

######  Problem 3.1 (Ulam’s homomorphism stability problem [Ulam]).

Given an almost homomorphism between two groups, is it close to a genuine
homomorphism between them?

There are many (non-equivalent) ways to formulate Ulam’s problem (cf.
[Kazhdan, BOT, glebsky2023asymptotic, GowersHatami, BLT, DGLT, BC22]). In this
section we study a finite group presentations variant of it.888 Our notion of
homomorphism stability is usually referred to in the literature as _pointwise
flexible stability in permutations_ (see [BeckerLubotzky]).

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 (as defined in (2.2)) is

(3.1)
$d_{h}(\sigma,\tau)=1-\frac{|\\{i\in[n]\mid\sigma(i)=\tau(i)\\}|}{N}=\operatorname*{\mathbb{P}}_{i\in[N]}[\sigma(i)\neq\tau(i)].$

Let $\Gamma\cong\langle S|R\rangle$ be a finite group presentation, and
$\mathcal{F}(S)$ the free group with basis $S$. Let $f\colon S\to{\rm Sym}(n)$
be a function. By the universal property of free groups, $f$ has a unique
extension to a homomorphism from $\mathcal{F}(S)$ to ${\rm Sym}(n)$, which we
denote by $f$ as well. This $f$ factors through $\Gamma$ if and only if for
every $r\in R$ we have $f(r)={\rm Id}.$ Hence, the collection of functions
$f\colon S\to{\rm Sym}(n)$ that induce a homomorphism from $\Gamma$ is

$\textrm{Hom}(\Gamma,{\rm Sym})=\\{f\colon S\to{\rm Sym}(n)\mid
n\in\mathbb{N},\ \forall r\in R\colon f(r)={\rm Id}\\}.$

This suggests the following tester for deciding whether $f\colon S\to{\rm
Sym}(n)$ induces a homomorphism from $\Gamma$:

Algorithm 1 Homomorphism tester

Input: $f\colon S\to{\rm Sym}(n)$.
Output: Accept or Reject.

1: Pick $r\in R$ unifromly at random.

2: Pick $i\in[n]$ uniformly at random.

3: If $f(r).i=i$, then return Accept.

4: Otherwise, return Reject.

######  Remark 3.2.

Instead of sampling $r\in R$ uniformly at random in Algorithm 1, one can use
any fully supported probability measure on $R$. This slight generalization is
important to the discussion in Section 3.1, and is described in Section 7.
Other than these sections, we would not need this generalized version.
Furthermore, it is natural in some instances to measure the Hamming distance
in a weighted way by choosing a non-unifrom distribution on $S$ (See Section 7
and [CVY_efficient, evra2016bounded]). But again, we will use only the uniform
measure for the Hamming distances in this part of the paper.

To fit Algorithm 1 to the setup of Section 2, we need the input function $f$
to be in the form $f\colon S\times[n]\to[n]$ with the extra condition that
$f(s,\cdot)\colon[n]\to[n]$ is a permutation for every $s\in S$. Namely,

$\begin{split}&{\mathfrak{F}}=\\{f\colon S\times[n]\to[n]\mid
n\in\mathbb{N},\forall s\in S\colon f(s,\cdot)\in{\rm Sym}(n)\\},\\\
&{\mathfrak{P}}=\textrm{Hom}(\Gamma,{\rm Sym}),\\\ &\forall
f_{1},f_{2}\in{\mathfrak{F}}\ \colon\ \
d_{h}(f_{1},f_{2})=\operatorname*{\mathbb{E}}_{s\in
S}[d_{h}(f_{1}(s,\cdot),f_{2}(s,\cdot))].\end{split}$

Hence, the _homomorphism local defect_ of $f\colon S\to{\rm Sym}(n)$, which is
the rejection probability in the above test, is

${\rm def}_{hom}(f)=\operatorname*{\mathbb{E}}_{r\in R}[d_{h}(f(r),{\rm
Id})].$

Moreover, the _homomorphism global defect_ of $f\colon S\to{\rm Sym}(n)$,
which is its distance to the collection $\textrm{Hom}(\Gamma,{\rm Sym})$, is

${\rm Def}_{hom}(f)=d_{h}(f,\textrm{Hom}(\Gamma,{\rm
Sym}))=\inf\\{d_{h}(f,\varphi)\mid\varphi\in\textrm{Hom}(\Gamma,{\rm
Sym})\\}.$

######  Definition 3.3.

Let $\rho$ be a rate function, as in Definition 2.1. A finite presentation
$\Gamma\cong\langle S|R\rangle$ is said to be _ $\rho$-homomorphism stable_ if
for every $f\colon S\to{\rm Sym}(n)$, we have

${\rm Def}_{hom}(f)\leq\rho({\rm def}_{hom}(f)).$

The goal of the following Sections, 3.1 and 3.2, is to motivate the notion of
$\rho$-homomorphism stability.

###  3.1. Locally testable codes

In this section, we relate homomorphism stability to the well studied topic of
_locally testable codes_.

The classical example of a homomorphism tester is the Blum–Luby–Rubinfeld
(BLR) linearity test [BLR]. In it, the input is a function
$f\colon\mathbb{F}_{2}^{n}\to\mathbb{F}_{2}$, where $\mathbb{F}_{2}=\\{0,1\\}$
is the field with two elements, and the goal is to decide whether $f$ is
linear. To that end, two points $x,y\in\mathbb{F}_{2}^{n}$ are sampled
uniformly at random, and $f$ is evaluated at three points $x,y$ and $x+y$. The
tester accepts if and only if $f(x)+f(y)=f(x+y)$. This test is $\rho$-stable
for the identity rate function $\rho(\varepsilon)=\varepsilon$ (See Section
1.6 in [odonnell2021analysis] for a proof).

The BLR linearity test is a special case of Algorithm 1. To see that, note
that $\mathbb{F}_{2}\cong{\rm Sym}(2)$. Moreover,
$\mathbb{F}_{2}^{n}\cong\langle\\{s_{x}\\}_{x\in\mathbb{F}_{2}^{n}}\mid\\{s_{x}\cdot
s_{y}\cdot s_{x+y}^{-1}\\}_{x,y\in\mathbb{F}_{2}^{n}}\rangle$, which is the
multiplication table presentation of $\mathbb{F}_{2}^{n}$. So, the linearity
test is Algorithm 1 under the restriction that the range of $f$ is ${\rm
Sym}(2)$ and not any ${\rm Sym}(N)$. In [BC22], it is proved that the
multiplication table presentation of any finite group is $\rho$-homomorphism
stable with linear rate $\rho(\varepsilon)=3000\varepsilon$. This generalizes
[BLR], though with worse parameters.

A _linear binary error correcting code_ – or just _code_ from now on – is a
linear subspace of a finite vector space over $\mathbb{F}_{2}$. E.g., the
Hadamard code is the subspace of linear functions from $\mathbb{F}_{2}^{n}$ to
$\mathbb{F}_{2}$, out of all functions from $\mathbb{F}_{2}^{n}$ to
$\mathbb{F}_{2}$. The linearity test is a complete and $\rho$-stable tester,
in the sense of Definition 2.2, for checking whether a given function is a
Hadamard code word. Moreover, its query complexity (which was defined in the
Sampling phase of the tester in Section • ‣ 2) is $3$. Codes that have a
tester which is complete, $\rho$-stable and with constant query complexity,
are called _locally testable_.

Every matrix $A\in M_{m\times n}(\mathbb{F}_{2})$ defines the code ${\rm
Ker}(A)\subseteq\mathbb{F}_{2}^{n}$.999Such matrices are usually called
_parity-check matrices_. Together with a probability distribution $\mu$ over
$[m]$, it also defines a tester:

Algorithm 2 Matrix tester

Input: A column vector $v\in\mathbb{F}_{2}^{n}$.
Output: Accept or Reject.

1: Sample $i\in[m]$ according to $\mu$.

2: Let $R_{i}(A)$ be the $i^{\rm th}$ row of $A$. Then, if $R_{i}(A)\cdot
v=0$, return Accept.

3: Otherwise, return Reject.

Algorithm 2 is complete given that $\mu$ is fully supported. If each row of
$A$ contains at most $q$ non-zero entries, for some universal constant $q$,
then this tester has bounded query complexity.101010Codes with a parity matrix
whose rows are of bounded weight are known in the literature as LDPC codes
(cf. [Gallager_LDPC, Sipser_Spielman_exp_codes]). So, the main obstacle is to
choose $A$ such that the tester is $\rho$-stable for some desired rate
function $\rho$.111111Every code would be $\rho$-stable for some $\rho$. The
goal is to find codes with a sufficiently good rate of local testabillity.
See, e.g., our choice of parameters in the efficient stability section in Part
II of this paper [CL_part2].  Algorithm 2 is clearly a generalization of the
BLR linearity test. Furthermore, every tester for a linear locally testable
code can be assumed to be in this form [ben2003some]. But, the matrix tester
is a special case of Algorithm 1:121212As mentioned in Remark 3.2, in
Algorithm 1 we chose a relation uniformly at random. To mimic Algorithm 2, we
need to generalize the homomorphism tester so it may sample a relation
according to some distribution other than the uniform one. The code
$\textrm{Ker}(A)$ can be viewed as the collection of homomorphism inducing
maps from $S=\\{x_{j}\\}_{j\in[n]}$ to ${\rm Sym}(2)\cong\mathbb{F}_{2}$. The
relations in this case are $R=\mathopen{}\mathclose{{}\left\\{\prod
x_{j}^{A_{ij}}}\right\\}_{i\in[m]}$, where the product is always ordered by
the index. This demonstrates how general Algorithm 1 is: It encapsulates local
testability of error correcting codes as a _special case_. This viewpoint on
Algorithm 1 raises fascinating new problems which we further discuss in the
open problem section of the second part of this paper [CL_part2] (see also
[CVY_efficient]).

###  3.2. Group soficity

In this section, we relate homomorphism stability to the well studied notion
of _sofic groups_. As oppose to the general philosophy of this paper, in this
section the exact rate $\rho$ is not important. Namely, homomorphism stability
is seen as a qualitative and not quantitative property. This viewpoint is of
interest when the finitely presented group $\Gamma\cong\langle S|R\rangle$ is
infinite.

######  Fact 3.4 (Glebsky-Rivera [GlebskyRivera]).

Let $\langle S|R\rangle,\langle S^{\prime}|R^{\prime}\rangle$ be two finite
presentations of the same group $\Gamma$. Assume $\langle S|R\rangle$ is
$\rho$-homomorphism stable for some rate function $\rho$. Then $\langle
S^{\prime}|R^{\prime}\rangle$ is $(C\cdot\rho)$-homomorphism stable for some
constant $C\in\mathbb{R}_{>0}$ that depends only on the two presentations.

Hence, we say that a group $\Gamma$ is _homomorphism stable_ if it has some
finite presentation $\Gamma\cong\langle S|R\rangle$ which is
$\rho$-homomorphism stable for some rate function $\rho$. Namely, by
disregarding the exact rate $\rho$, homomorphism stability may be viewed as a
group property and not a presentation specific property.

######  Definition 3.5.

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

${\rm def}_{hom}(f_{n})\xrightarrow{n\to\infty}0,$

and for every $w\notin\langle\langle R\rangle\rangle$,131313$\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 3.6 (Gromov [Gromov_sofic], Weiss [Weiss_Sofic]).

Are there non-sofic groups?

The following is an easy to prove, yet quite insightful, observation.

######  Proposition 3.7 (Glebsky-Rivera [GlebskyRivera]).

If $\Gamma$ is homomorphism stable and sofic, then it is residually finite.

Soficity is a _group approximation_ property. There are other well studied
group approximation properties, such as hyperlinearity, property MF and
$L^{p}$-approximations (cf. [Cap_Lup_Sofic_Hyperlinear_book, DGLT]). The only
known examples of non-approximable groups were constructed using the
(analogous) observation of Proposition 3.7 (See [DGLT, LubotzkyOppenheim]).
Though more sophisticated methods for constructing non-sofic groups were
recently suggested (cf. [BowenBurton, dogon2023flexible]), they still require
the proof of homomorphism stability of certain groups.141414There are also
suggested methods for constructing non-sofic groups that do not use
homomorphism stability, at least not in such a direct manner. E.g.,
transforming the answer reduction part of the compression theorem in [MIPRE]
into a linear constraint system game (cf. [slofstra_2019]) would imply the
existence of a non-sofic group. Problem 3.6 is still a major open problem,
with many suggested tackling angles. We chose to emphasize its relation to
homomorphism stability. We further discuss group soficity in Part II of this
paper [CL_part2], and even suggest a new paradigm for potentially resolving
Problem 3.6 in the positive.

##  4\. Covering stability of polygonal complexes

Let us move now to another stability problem.

###  4.1. Graphs a la Bass–Serre

######  Definition 4.1.

A graph (a la Bass–Serre, see [Trees_Serre, KOLODNER2021595]) $\mathcal{X}$
consists of the following data:

  1. (1)

A set $V=V(\mathcal{X})$ of vertices.

  2. (2)

A set $\overrightarrow{E}=\overrightarrow{E}(\mathcal{X})$ of directed edges,
together with functions $\tau,\iota\colon\overrightarrow{E}\to V$ and an
involution $\overline{\ \ {}^{\ {}^{\
}}}\colon\overrightarrow{E}\to\overrightarrow{E}$ satisfying

$\forall e\in\overrightarrow{E}\ \colon\ \ \tau(\overline{e})=\iota(e).$

The function $\tau$ is the terminal point (or end point) function, the
function $\iota$ is the initial point (or origin point) function and
$\overline{\ \ {}^{\ {}^{\ }}}$ is the reverse edge function. Namely, an edge
$e$ can be visualized as $x\xrightarrow{e}y$, where $x=\iota(e)$ and
$y=\tau(e)$. Moreover, we have $y\xrightarrow{\bar{e}}x$.

######  Remark 4.2.

Note the following:

  * •

A graph (a la Bass-Serre) is essentially an undirected multi-graph. To make
this statement precise, define $[e]=\\{e,\bar{e}\\}$ and
$E(\mathcal{X})=\\{[e]\mid e\in\overrightarrow{E}(\mathcal{X})\\}$. Then
$(V(\mathcal{X}),E(\mathcal{X}))$ is a multi-graph where the endopints of
$[e]\in E(\mathcal{X})$ are $\iota(e)$ and $\tau(e)$.

Furthermore, multi-graphs can be viewed as $1$-dimensional CW complexes (cf.
[Hatcher_Alg_Top]) by defining $V(\mathcal{X})$ to be the $0$-dimensional
cells, $E(\mathcal{X})$ to be the $1$-dimensional cells, and with gluing maps
induced by $\tau$ and $\iota$. Hence, we can view graphs a la Bass-Serre as
topological spaces.

  * •

We may abuse notation and write $xy$ for the edge $x\xrightarrow{e}y$, though
there may be several edges with the exact same origin and endpoint.

######  Definition 4.3.

A _path_ $\pi$ in a graph $\mathcal{X}$ is a sequence of edges
$e_{1}...e_{\ell}$ such that each $e_{i}\in\overrightarrow{E}$ and for every
$1\leq i\leq\ell-1$, we have $\tau(e_{i})=\iota(e_{i+1})$. By denoting
$x_{i}:=\tau(e_{i})\in V$ and $x_{0}:=\iota(e_{1})\in V$, we can graphically
represent the path $\pi$ by

$x_{0}\xrightarrow{e_{1}}x_{1}\xrightarrow{e_{2}}...\xrightarrow{e_{\ell}}x_{\ell}.$

The integer $\ell(\pi)=\ell$ is the _length_ of the path. The path $\pi$ is
_non-backtracking_ (or reduced) if $e_{i+1}\neq\bar{e}_{i}$ for every $1\leq
i\leq\ell-1$. For a path $\pi$, its _inverse_ or _reverse orientation_ is

$\bar{\pi}=x_{\ell}\xrightarrow{\bar{e}_{\ell}}...\xrightarrow{\bar{e}_{1}}x_{0}.$

The path $\pi$ is _closed_ if $x_{0}=x_{\ell}$, and _open_ otherwise. When
$\pi$ is closed, it has $\ell$ shifts $e_{k}...e_{\ell}e_{1}...e_{k-1}$ and
$\ell$ inverses $\bar{e}_{k-1}...\bar{e}_{1}\bar{e}_{\ell}...\bar{e}_{k}$
which are also closed paths in $\mathcal{X}$. We call all these shifts and
inverses the _orientations_ of $\pi$, and denote the collection of all of them
by $[\pi]$. The path $\pi$ is _cyclically reduced_ if all its orientations are
non-backtracking.

######  Definition 4.4 (Combinatorial maps between graphs).

A _combinatorial map_ $f\colon\mathcal{Y}\to\mathcal{X}$ between two graphs is
a function that maps vertices of $\mathcal{Y}$ to vertices of $\mathcal{X}$
and edges of $\mathcal{Y}$ to edges of $\mathcal{X}$, and is compatible with
the structural data of the graph. Namely, it preserves initial points,
terminal points and edge flips:

$\forall e\in\overrightarrow{E}(\mathcal{Y})\ \colon\ \
\tau_{\mathcal{X}}(f(e))=f(\tau_{\mathcal{Y}}(e)),\
\iota_{\mathcal{X}}(f(e))=f(\iota_{\mathcal{Y}}(e)),\
f(\overline{e})=\overline{f(e)}.$

######  Remark 4.5.

Given a combinatorial map $f\colon\mathcal{Y}\to\mathcal{X}$, we can extend it
to paths in $\mathcal{Y}$. Namely, if $\pi=e_{1}...e_{\ell}$ is a path in
$\mathcal{Y}$, then $f(\pi)=f(e_{1})...f(e_{\ell})$ is a path in
$\mathcal{X}$. Moreover, combinatorial maps induce a continuous map between
the graphs as topological spaces.

Recall that a continuous function $f\colon\mathcal{Y}\to\mathcal{X}$ between
two topological spaces is a (topological) _covering_ if for every point
$x\in\mathcal{X}$ there is an open neighborhood $U$ of $x$ such that
$f^{-1}(U)$ is a disjoint union of open sets, each of which homeomorphic to
$U$ via $f$. If $\mathcal{X}$ is (path) connected, then the _degree_ of the
covering, which is the cardinality of $|f^{-1}(x)|$ for any of the points
$x\in\mathcal{X}$, is well defined (cf. Chapter 1.3 in [Hatcher_Alg_Top]).
When $|f^{-1}(x)|=n<\infty$, we say that $f$ is a degree $n$ covering, or just
$n$-covering.

######  Definition 4.6.

A combinatorial map $f\colon\mathcal{Y}\to\mathcal{X}$ between graphs is a
(combinatorial) _covering_ if it is a topological covering.

######  Remark 4.7.

Graph coverings151515Graph coverings are sometimes called _graph liftings_ in
the literature. This notion is a bit confusing because of the path lifting and
homotopy lifting lemmas (which are used for example in the proof sketch of
Fact 4.13). Hence, we stick with coverings for these objects. is an intensely
studied object. They were used both as a random model for graphs
[Linial_Amit2002random, amit2001random, MSS_Ramanujan,
Puder_expander_coverings] and as a building block in a recent construction of
good locally testable codes and good quantum codes [LTC_Panteleev_Kalachev].

######  Fact 4.8.

Let $\mathcal{X}$ and $\mathcal{Y}$ be finite graphs. Let
$f\colon\mathcal{Y}\to\mathcal{X}$ be a combinatorial map between them. Then,
$f$ is a covering if and only if for every vertex $y\in V(\mathcal{Y})$, the
star of $y$ is mapped bijectively to the star of $f(y)$. Namely, if
$E_{y}(\mathcal{Y})=\\{e\in\overrightarrow{E}(\mathcal{Y})\mid\tau(e)=y\\}$,
then $f|_{E_{y}(\mathcal{Y})}$ is a bijection onto $E_{f(y)}(\mathcal{X})$.

A combinatorial map between graphs $f\colon\mathcal{A}\to\mathcal{X}$ is said
to be an _embedding_ if it is a set theoretic injection. A _subgraph_ of
$\mathcal{X}$ is the image of some embedding into it. The _edit distance_
between a graph $\mathcal{X}$ and a subgraph of it $\mathcal{A}$ is

$d_{Edit}(\mathcal{X},\mathcal{A})=|E(\mathcal{X})|-|E(\mathcal{A})|,$

namely, this is the number of edges needed to be deleted to move from
$\mathcal{X}$ to $\mathcal{A}$. Given two graphs $\mathcal{X}$ and
$\mathcal{Z}$, not necessarily embedded in one another, we can define the edit
distance between them using the largest graph $\mathcal{A}$ which embeds into
both $\mathcal{X}$ and $\mathcal{Z}$.161616The _largest_ in this case is
according to the number of edges. The _edit distance_ between $\mathcal{X}$
and $\mathcal{Z}$ would be the maximum between their distances to
$\mathcal{A}$. Namely,

(4.1)
$d_{Edit}(\mathcal{X},\mathcal{Z})=\max(d_{Edit}(\mathcal{X},\mathcal{A}),d_{Edit}(\mathcal{Z},\mathcal{A}))=\max(|E(\mathcal{X})|,|E(\mathcal{Z})|)-|E(\mathcal{A})|.$

The normalized version of the edit distance will be

(4.2)
$d_{edit}(\mathcal{X},\mathcal{Z})=1-\frac{|E(\mathcal{A})|}{\max(|E(\mathcal{X})|,|E(\mathcal{Z})|)}.$

######  Remark 4.9.

There is an encoding of graphs for which the edit distance (4.1) agrees with
the Hamming distance (2.1) (and similarly for the normalized versions): The
vertex set $V(\mathcal{X})$ will always be $\\{1,...,|V(\mathcal{X})|\\}$. The
edge set $E(\mathcal{X})$ will always be $\\{1,...,|E(\mathcal{X})|\\}$. Then,
the function $\iota\times\tau\colon E(\mathcal{X})\to V(\mathcal{X})\times
V(\mathcal{X})$, which outputs for each edge its origin and terminus, encodes
the graph (note that we essentially chose an orientation for every edge
$[e]=\\{e,\bar{e}\\}$). There are many encodings of the same graph (one can
permute $V(\mathcal{X})$ and $E(\mathcal{X})$ arbitrarily, as well as choose
different orientations of the edges). Hence, the edit distance between two
graphs is the Hamming distance between the two most compatible encodings of
them.

One may argue that we did not choose the most natural encoding of graphs. A
multi-graph can be encoded by its adjacency matrix (see (5.3)), and the
resulting edit distance will be slightly different — it would be the sum of
$d_{Edit}(\mathcal{X},\mathcal{A})$ and $d_{Edit}(\mathcal{Z},\mathcal{A})$
instead of their maximum as in (4.1). But, up to a factor of $2$, they are the
same.

Given a graph $\mathcal{X}$, an _$\mathcal{X}$ -labeled_ graph is a graph
$\mathcal{Y}$ with a combinatorial map
$\Phi_{\mathcal{Y}}\colon\mathcal{Y}\to\mathcal{X}$ which we call _the
labeling_. A morphism between $\mathcal{X}$-labeled graphs is a combinatorial
map $f\colon\mathcal{Y}\to\mathcal{Z}$ that commutes with the labelings,
namely $\Phi_{\mathcal{Y}}=\Phi_{\mathcal{Z}}\circ f$. Embeddings and
subgraphs of $\mathcal{X}$-labeled graphs can be defined in an analogous way
to before, and hence the edit distance is defined on this category.171717Note
that by choosing a weighting system $w$ on the edges of $\mathcal{X}$, we get
a weighted edit distance on $\mathcal{X}$-labeled graphs by paying
$w(\Phi(e))$ when changing $e$. This is shortly discussed in Section 7.

###  4.2. Polygonal complexes

As mentioned above, graphs are $1$-dimensional CW complexes. We now wish to
add $2$-dimensional cells to the mixture in a combinatorial way that will
allow us to study them through a property testing lens.

######  Definition 4.10.

A _polygonal complex_ $\mathcal{X}$ is a graph with extra data: A set
$\overrightarrow{P}=\overrightarrow{P}(\mathcal{X})$ of cyclically reduced
closed paths in $\mathcal{X}$. The elements of $\overrightarrow{P}$ are called
(oriented) _polygons_. Similar to the way we always include both $e$ and
$\bar{e}$ as edges in $\overrightarrow{E}(\mathcal{X})$, we assume that all
the orientations of a polygon must be in $\overrightarrow{P}$. Namely, if
$\pi=e_{1}...e_{\ell}\in\overrightarrow{P}$, then

$\forall 1\leq k\leq\ell\ \colon\ \
e_{k}...e_{\ell}e_{1}...e_{k-1}\in\overrightarrow{P}\quad\textrm{and}\quad\bar{e}_{k-1}...\bar{e}_{1}\bar{e}_{\ell}...\bar{e}_{k}\in\overrightarrow{P}.$

We denote the set of un-oriented polygons by
$P(\mathcal{X})=\\{[\pi]\mid\pi\in\overrightarrow{P}(\mathcal{X})\\}$.

For visual examples of polygons see Figure 4.1. As oppose to edges, where
there may be multiple edges with the same origin and end point, we assume that
there are no two polygons with the same pasted path. Namely, a polygon is
uniquely defined by its closed path boundary.

$\pi_{1}$$e_{0}$$e_{1}$$e_{2}$$e_{3}$$e_{4}$$\pi_{2}$$e^{\prime}_{1}$$e^{\prime}_{2}$$e^{\prime}_{3}$$e^{\prime}_{4}$$e^{\prime}_{5}$$s_{1}$$s_{2}$$s_{3}$

0em0em

Figure 4.1. Examples of polygons. $\pi_{1}=e_{1}e_{2}e_{3}e_{4}$ is a length
$4$ polygon. We can also construct length $5$ polygons of the form
$\pi=e_{1}e_{2}e_{0}e_{3}e_{4}$ or
$\pi^{\prime}=e_{1}e_{2}\bar{e_{0}}e_{3}e_{4}$.
$\pi_{2}=e^{\prime}_{1}e^{\prime}_{2}e^{\prime}_{3}e^{\prime}_{4}e^{\prime}_{5}$
is a length $5$ polygon. Lastly, every word of length $\ell$ in the free group
on $\\{s_{1},s_{2},s_{3}\\}$ defines a length $\ell$ polygon on the bouquet of
circles.

######  Remark 4.11.

Note the following:

  * •

Polygonal complexes are graphs with added data. To be able to distinguish
between the graph structure and the whole complex $\mathcal{X}$, we denote by
$G(\mathcal{X})$ the _underlying graph_ of $\mathcal{X}$.

  * •

Polygonal complexes are $2$-dimensional CW complexes (hence, topological
spaces): Their $1$-skeleton is induced by the underlying graph
$G(\mathcal{X})$. For the $2$-dimensional cells, we paste a disc for every un-
oriented polygon $[\pi]$, with the gluing map being according to some
representative $\pi$. We therefore use the standard notation for
$i$-dimensional cells of a CW complex when suitable:

(4.3) $\mathcal{X}(0)=V(\mathcal{X})\ ,\quad\mathcal{X}(1)=E(\mathcal{X})\
,\quad\mathcal{X}(2)=P(\mathcal{X}),$

and

(4.4) $\overrightarrow{\mathcal{X}}(1)=\overrightarrow{E}(\mathcal{X})\
,\quad\overrightarrow{\mathcal{X}}(2)=\overrightarrow{P}(\mathcal{X})$

for the oriented versions.

######  Definition 4.12.

Let $\mathcal{X},\mathcal{Y}$ be two polygonal complexs. A combinatorial map
$f\colon G(\mathcal{Y})\to G(\mathcal{X})$ is called a _combinatorial map
between polygonal complexes_ , if for every
$\pi\in\overrightarrow{P}(\mathcal{Y})$, we have
$f(\pi)\in\overrightarrow{P}(\mathcal{X})$.

The notions of embeddings, subcomplexes and coverings generalize to the
polygonal complex setup in the natural way.

###  4.3. Almost covers

Let $\mathcal{G}$ be a graph and $\mathcal{X}$ a _finite_ polygonal complex.
Let $f\colon\mathcal{G}\to G(\mathcal{X})$ be a _finite_ covering. Let
$\pi=x\xrightarrow{e_{1}}x_{1}\xrightarrow{e_{2}}...\xrightarrow{e_{\ell-1}}x_{\ell-1}\xrightarrow{e_{\ell}}x$
be a polygon in $\mathcal{X}$. By the path lifting property of covering maps
(See Proposition 1.30, page 60, in [Hatcher_Alg_Top]), for every
$x^{\prime}\in f^{-1}(x)$ there exists a unique path $\pi^{\prime}$ in
$\mathcal{G}$ that begins at $x^{\prime}$ and satisfies $f(\pi^{\prime})=\pi$.
The lifted path $\pi^{\prime}$ may be closed or open.

######  Fact 4.13.

Let $f\colon\mathcal{G}\to G(\mathcal{X})$ be a finite covering. Then, all the
lifts of all the polygons in $\overrightarrow{P}(\mathcal{X})$ are closed if
and only if polygons can be added to $\mathcal{G}$ such that $f$ becomes a
covering map of $\mathcal{X}$ (namely, $\mathcal{G}$ is the $1$-skeleton of a
covering of $\mathcal{X}$ via $f$).

###### Proof idea.

This is essentially the correspondence between (conjugation orbits of)
subgroups of the fundamental group $\pi_{1}(\mathcal{X},*)$ and (connected)
coverings of $\mathcal{X}$ (See Theorem 1.38, page 67, in [Hatcher_Alg_Top]).
∎

We call a function $f\colon\mathcal{G}\to G(\mathcal{X})$ that can be
completed to a covering of $\mathcal{X}$ (as in Fact 4.13) a _genuine
covering_ of $\mathcal{X}$. This suggests the following tester for whether a
graph covering $f\colon\mathcal{G}\to G(\mathcal{X})$ is a genuine covering of
$\mathcal{X}$:181818In Algorithm 3 we sample a polygon uniformly at random.
One could have sampled a polygon using a different distribution. More on that
in Section 7.

Algorithm 3 Covering tester

Input: $f:\mathcal{G}\rightarrow G(\mathcal{X}),$ a finite covering of the
$1$-skeleton of $\mathcal{X}$.
Output: Accept or Reject.

1: Pick $[\pi]\in P(\mathcal{X})$ uniformly at random. Then, pick a
representative $\pi$ of $[\pi]$ uniformly at random.

2: Let $x$ be the starting vertex of $\pi$. Pick $x^{\prime}\in f^{-1}(x)$
uniformly at random.

3: If the lift $\pi^{\prime}$ of $\pi$ to $x^{\prime}$ is a closed path in
$\mathcal{G}$, return Accept.

4: Otherwise, return Reject.

Algorithm 3 may be fitted to the setup of Section 2 using an extension of the
encoding system suggested in Remark 4.9. In this case:

  * •

${\mathfrak{F}}$ is the collection of all graph coverings
$f\colon\mathcal{G}\to G(\mathcal{X})$;

  * •

${\mathfrak{P}}$ is the collection of all genuine coverings of $\mathcal{X}$;

  * •

Given $f_{1}\colon\mathcal{G}_{1}\to G(\mathcal{X})$ and
$f_{2}\colon\mathcal{G}_{2}\to G(\mathcal{X})$, the normalized Hamming
distance (2.2) between them is the normalized edit distance (4.2) between them
as $G(\mathcal{X})$-labeled graphs. Hence, the _covering global defect_ of $f$
is the normalized distance of $\mathcal{G}$ to the closest genuine covering of
$\mathcal{X}$ in the category of $G(\mathcal{X})$-labeled graphs. Namely,

${\rm
Def}_{cover}(f)=\inf\mathopen{}\mathclose{{}\left\\{d_{edit}(\mathcal{G},G(\mathcal{Y}))\middle|\varphi\colon\mathcal{Y}\xrightarrow{{\rm
covering}}\mathcal{X}}\right\\}.$

  * •

As before, the _covering local defect_ of $f$ is the rejection probability in
the covering tester (Algorithm 3), namely

${\rm def}_{cover}(f)=\operatorname*{\mathbb{P}}_{\begin{subarray}{c}[\pi]\in
P(\mathcal{X})\\\ x^{\prime}\in
f^{-1}(x)\end{subarray}}\mathopen{}\mathclose{{}\left[\textrm{The\ lift\ of}\
\pi\ \textrm{to\ }x^{\prime}\textrm{\ is\ open}}\right].$

######  Definition 4.14.

Let $\rho$ be a rate function, as in Definition 2.1. A polygonal complex is
_$\rho$ -covering stable_ if for every graph $\mathcal{G}$ and covering map
$f\colon\mathcal{G}\to G(\mathcal{X})$, we have

${\rm Def}_{cover}(f)\leq\rho({\rm def}_{cover}(f)).$

In the next section, we discuss our motivation to study $\rho$-covering
stability, as well as the difference between our covering tester (Algorithm 3)
and the Dinur–Meshulam one (Algorithm 4).

###  4.4. The Dinur–Meshulam framework

In [quantum_soundness_tensor_codes], Ji–Natarajan–Vidick–Wright–Yuen proved a
homomorphism stability result, in unitaries, that has a very good trade-off
between presentation length and stability rate of the studied groups (see
[CVY_efficient]). In an ongoing project [BCLV_subgroup_tests], we try to prove
a permutation analogue of their result. Covering stability, as in Definition
4.14, arises naturally in our proof strategy. In [Dinur-Meshulam],
Dinur–Meshulam studied a similar problem. The main difference between the
Dinur–Meshulam setup and ours is that they think of the degree parameter $n$
as a constant. Namely, in their alternative to Algorithm 3, instead of
sampling a polygon $[\pi=x\to...\to x]$ and a starting position from
$x^{\prime}\in f^{-1}(x)$, they only sample a polygon. Then, they check that
its lift to every vertex in the fiber $f^{-1}(x)$ is closed.

Algorithm 4 Dinur-Meshulam covering tester

Input: $f:\mathcal{G}\rightarrow G(\mathcal{X}),$ a finite covering of the
$1$-skeleton of $\mathcal{X}$.
Output: Accept or Reject.

1: Pick $[\pi]\in P(\mathcal{X})$ uniformly at random.

2: Let $x$ be the starting vertex of some uniformly chosen representative
$\pi$ of $[\pi]$.

3: If for every $x^{\prime}\in f^{-1}(x)$ the lift $\pi^{\prime}$ of $\pi$ to
$x^{\prime}$ is a closed path in $\mathcal{G}$, return Accept.

4: Otherwise, return Reject.

In Section 6.1, we give a one to one correspondence between $1$-cochains of a
polygonal complex $\mathcal{X}$ and coverings of its $1$-skeleton. To
encapsulate the Dinur–Meshulam Algorithm, one can use this equivalence and the
notations of Section 5, but with a different metric on ${\rm Sym}(n)$. They
use the discrete distance

$\forall\sigma,\tau\in{\rm Sym}(n)\ \colon\ \
d_{D}(\sigma,\tau)=\begin{cases}1&\sigma\neq\tau,\\\
0&\sigma=\tau,\end{cases}$

while we are using the normalized Hamming distance on ${\rm Sym}(n)$. This
change may seem minor, but it allows one to prove beautiful results in their
setup (See Theorem 1.2 in [dikstein2023coboundary]) that seem very difficult
to prove in our setting. The motivation to insist on our setting is coming
from the fact that it can lead to a solution to Problem 3.6. For more details,
see the open problem section of Part II of this paper [CL_part2].

There is another strengthening of Algorithm 3 which is perpendicular to the
Dinur–Meshulam one. Instead of sampling a single polygon with a single
starting position (as done in Algorithm 3), one can sample for every polygon
$[\pi=x\to...\to x]\in P(\mathcal{X})$ a uniformly random starting position
$x^{\prime}_{\pi}\in f^{-1}(x)$. Then, the tester checks for each polygon and
sampled starting position whether the lift of $\pi$ to $x^{\prime}_{\pi}$ is
closed or not. Namely:

Algorithm 5 $L^{\infty}$ covering tester

Input: $f:\mathcal{G}\rightarrow G(\mathcal{X}),$ a finite covering of the
$1$-skeleton of $\mathcal{X}$.
Output: Accept or Reject.

1: For every $[\pi]\in P(\mathcal{X})$ let $x_{\pi}$ be the starting vertex of
a uniformly chosen representative $\pi$ of $[\pi]$.

2: Sample for every $[\pi]\in P(\mathcal{X})$ a lift $x^{\prime}_{\pi}\in
f^{-1}(x_{\pi})$.

3: If for every $\pi$ and sampled $x^{\prime}_{\pi}$, the lift $\pi^{\prime}$
of $\pi$ to $x^{\prime}_{\pi}$ is closed in $\mathcal{G}$, return Accept.

4: Otherwise, return Reject.

When thinking of the complex $\mathcal{X}$ as a constant, this tester is
essentially equivalent to Algorithm 3. To encapsulate the difference between
Algorithm 5 and Algorithm 3, one can replace the expectations over polygons in
our analysis with a maximum over polygons. The same change can be done to
Algorithms 1 and 6, and we call these _the $L^{\infty}$-analogues_ of the
testers.

##  5\. Cocycle stability of polygonal complexes

In this section, we define the last stability problem of interest (for this
paper).

###  5.1. Non-commutative cohomology

Let $\mathcal{X}$ be a polygonal complex. Recall our notation
$\overrightarrow{\mathcal{X}}(i)$ for the oriented $i$-cells of $\mathcal{X}$
and $\mathcal{X}(i)$ for the unoriented versions, which were defined in (4.3)
and (4.4). Moreover, for $i=1$ or $2$, recall that $\bar{c}$ is the reverse
orientation of the cell $c\in\overrightarrow{\mathcal{X}}(i)$. Let $\Gamma$ be
a non trivial 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}\\}.$

Since we did not define orientations on vertices, there are no anti-
symmetricity conditions on $0$-cochains. Also, for every $2$-cochain
$\alpha\colon\overrightarrow{P}(\mathcal{X})\to\Gamma$ and an orientation
$\pi$ of a polygon $[\pi]$, we assume that $\alpha(\pi)$ is conjugate to
$\alpha(\pi^{\prime})$, where $\pi^{\prime}$ is a shift of $\pi$.

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}).$

######  Remark 5.1.

Every map from $\overrightarrow{E}(\mathcal{X})$ to a group $\Gamma$ can be
extended to paths in $G(\mathcal{X})$ in the natural way: For
$\pi=x_{0}\xrightarrow{e_{1}}...\xrightarrow{e_{\ell}}x_{\ell}$, we let
$\alpha(\pi)=\alpha(e_{1})...\alpha(e_{\ell})$. Note that $\delta\alpha(\pi)$
is exactly $\alpha(\pi)$ in the extended sense, but restricted to the polygons
of $\mathcal{X}$.

Next, we prove _exactness_ , namely, that for $\alpha\in
C^{0}(\mathcal{X},\Gamma)$, $\delta^{2}\alpha$ is the constant identity
function. For a polygon
$\pi=x_{0}\xrightarrow{e_{1}}x_{1}\xrightarrow{e_{2}}...\xrightarrow{e_{\ell}}x_{\ell}=x_{0}$,
we have

$\delta^{2}\alpha(\pi)=\delta\alpha(e_{1})...\delta\alpha(e_{\ell})=\alpha(x_{0})^{-1}\alpha(x_{1})\alpha(x_{1})^{-1}\alpha(x_{2})...\alpha(x_{\ell-1})^{-1}\alpha(x_{\ell})=\alpha(x_{0})^{-1}\alpha(x_{\ell})={\rm
Id}.$

For any two $i$-cochains with $\Gamma$ coefficients $\alpha$ and $\beta$, the
_distance_ between them is

(5.1)
$d(\alpha,\beta)=\operatorname*{\mathbb{E}}_{[x]\in\mathcal{X}(i)}\operatorname*{\mathbb{E}}_{x\in[x]}[d(\alpha(x),\beta(x))].$

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

(5.2)
$\lVert\alpha\rVert=\operatorname*{\mathbb{E}}_{[x]\in\mathcal{X}(i)}\operatorname*{\mathbb{E}}_{x\in[x]}[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\Gamma$ 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},\Gamma)$ 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.

###  5.2. Cohomology with permutation coefficients

Though all the cohomological definitions we listed were defined for a general
group $\Gamma$, in this paper we focus on the case where $\Gamma$ is a finite
permutation group equipped with the normalized Hamming distance (3.1).202020As
mentioned in Section 4.4, to get the Dinur–Meshulam framework you replace the
Hamming metric with the discrete metric. Moreover, since the normalized
Hamming distance (with errors) 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))\ ,\quad Z^{i}(\mathcal{X},{\rm
Sym})=\bigsqcup_{n=2}^{\infty}Z^{i}(\mathcal{X},{\rm Sym}(n))\ ,$

and

$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 (5.1), and thus also a norm on it as in
equation (5.2).

As the title of the section suggests, we now devise a tester for deciding
whether a given $i$-cochain with permutaition coeffcients is an $i$-cocycle.
Note that, by definition, $\alpha$ is a cocycle if and only if
$\|\delta\alpha\|=0$. How robust is this property? Namely, if $\delta\alpha$
has a small norm, does it imply that $\alpha$ is close to a cocycle? The
following tester assumes exactly that:

Algorithm 6 $i$-cocycle tester, for $i=0$ or $1$

Input: $\alpha\colon\overrightarrow{\mathcal{X}}(i)\to{\rm Sym}(n)$ an
$i$-cochain.
Output: Accept or Reject.

1: Pick an un-oriented $i$-cell $[\pi]\in\mathcal{X}(i+1)$ uniformly at
random. Then, pick a representative $\pi$ of $[\pi]$ uniformly at random.

2: Pick an index $i\in\\{1,...,n\\}$ uniformly at random.

3: If $\delta\alpha(\pi).i=i$, then return Accept.

4: Otherwise, return Reject.

Algorithm 6 can be framed in the setup of Section 2 in a similar way to
Algorithm 1. Namely, the input function is of the form
$\alpha\colon\mathcal{X}(i)\times[n]\to[n]$ with the restriction that for
every $i$-cell $e$, $\alpha(e,\cdot)\colon[n]\to[n]$ is a permutation. Hence:

  * •

${\mathfrak{F}}$ is the $i$-cochains $C^{i}(\mathcal{X},{\rm Sym})$;

  * •

${\mathfrak{P}}$ is the $i$-cocycles $Z^{i}(\mathcal{X},{\rm Sym})$;

  * •

The normalized Hamming distance between two $i$-cochains $\alpha,\beta\in
C^{i}(\mathcal{X},{\rm Sym})$ is

$d_{h}(\alpha,\beta)=\operatorname*{\mathbb{E}}_{[e]\in\mathcal{X}(i)}[d_{h}(\alpha(e),\beta(e))].$

Hence, the _cocycle global defect_ of $\alpha$ is

$\begin{split}{\rm Def}_{cocyc}(\alpha)&=d_{h}(\alpha,Z^{i}(\mathcal{X},{\rm
Sym}))\\\ &=\inf\\{d_{h}(\alpha,\varphi)\mid N\in\mathbb{N},\
\varphi\colon\mathcal{X}(i)\to{\rm Sym}(N),\
\|\delta\varphi\|=0\\}.\end{split}$

  * •

The rejection probability of $\alpha$ in the cocycle tester is, by design,
$\|\delta\alpha\|$. Hence, the _cocycle local defect_ of $\alpha$ is

${\rm def}_{cocyc}(\alpha)=||\delta\alpha||.$

######  Remark 5.2.

Our notations are suggestive of the $i=1$ case, since this case is our main
interest.

######  Definition 5.3.

Let $\rho$ be a rate function, as in Definition 2.1. A polygonal complex is
said to be _$\rho$ -cocycle stable in the $i^{\rm th}$ dimension_ (where $i=0$
or $1$) if for every $i$-cochain $\alpha$ we have

$d_{h}(\alpha,Z^{i}(\mathcal{X},{\rm Sym}))\leq\rho(\|\delta\alpha\|).$

The following subsections are motivational. First, in Section 5.3 we study
cocycle stability in the $0^{\rm th}$ dimension, and prove it is related to
the spectral gap of the underlying graph. This hints at a Cheeger-type
inequality. Following the hint, in Section 5.4 we define an appropriate notion
of a Cheeger constant, and compare it with the classical Cheeger constant.
Finally, in Section 5.5 we discuss coboundary expansion to motivate
generalizations of it to our setup. This generalization will be further
studied in Part II of this paper [CL_part2], and in the companion paper
[CL_stability_Random_complexes].

###  5.3. Cocycle stability in the $0^{\rm th}$ dimension

Cocycle stability in the $0^{\rm th}$ dimension depends only on the underlying
graph of the complex. For every finite graph $\mathcal{X}$ there is an
associated adjacency matrix $M_{\mathcal{X}}\colon V(\mathcal{X})\times
V(\mathcal{X})\to\mathbb{C}$ that satisfies

(5.3)
$M_{\mathcal{X}}(x,y)=|\\{e\in\overrightarrow{E}(\mathcal{X})\mid\iota(e)=x,\tau(e)=y\\}|.$

Because of the reverse edge function, this matrix is symmetric. Assuming the
graph is $k$-regular, the eigenvalues of this matrix are

$k=\lambda_{1}\geq\lambda_{2}\geq...\geq\lambda_{|V(\mathcal{X})|}\geq-k.$

The normalized spectral gap of a $k$-regular graph $\mathcal{X}$ is

$\gamma(\mathcal{X})=\frac{k-\lambda_{2}}{k}.$

######  Lemma 5.4 ($L^{2}$-Poincare-type inequality).

Let $\mathcal{X}$ be a finite regular graph. Let $\mathbb{H}$ be a Hilbert
space. Let $f\colon V(\mathcal{X})\to\mathbb{H}$ be any function. Then

$\operatorname*{\mathbb{E}}_{xy\in\overrightarrow{E}(\mathcal{X})}[\|f(x)-f(y)\|^{2}]\geq\gamma(\mathcal{X})\cdot\operatorname*{\mathbb{E}}_{x,y\in
V(\mathcal{X})}[\|f(x)-f(y)\|^{2}].$

###### Proof.

See Theorem 13.9 in [Hoory_Linial_Wigderson] for a proof sketch, and Section
1.3 in [de_la_Salle_spectral_gap] for a complete proof. ∎

######  Proposition 5.5.

Every finite connected regular graph $\mathcal{X}$ is $\rho$-cocycle stable in
the $0^{\rm th}$ dimension, with

$\rho(\varepsilon)=\frac{\varepsilon}{\gamma(\mathcal{X})}.$

###### Proof.

First of all, since $\mathcal{X}$ is connected, all $0$-cocycles are
$0$-coboundaries, namely constant functions. This is because ${\rm
Id}=\delta\alpha(xy)=\alpha(x)^{-1}\alpha(y)$ implies $\alpha(x)=\alpha(y)$
along every edge.

Now, let $\alpha\colon V(\mathcal{X})\to{\rm Sym}(n)$ be a $0$-cochain. The
group ${\rm Sym}(n)$ embeds naturally into $U(n)$, the $n\times n$ unitary
matrices, as permutation matrices. Moreover, for two permutations
$\sigma,\tau\in{\rm Sym}(n)$, we have

$d_{h}(\sigma,\tau)=\frac{1}{2}\|\sigma-\tau\|_{HS}^{2},$

where on the right hand side we think of $\sigma$ and $\tau$ as the associated
permutation matrices, and

(5.4) $\forall A\in M_{n}(\mathbb{C})\ \colon\ \
\|A\|_{HS}^{2}=\frac{\textrm{tr}(A^{*}A)}{n}=\frac{\sum_{i,j=1}^{n}|A_{ij}|^{2}}{n}$

is the normalized Hilbert–Schmidt norm, which is induced by an inner product
on $M_{n}(\mathbb{C})$ that makes it a Hilbert space. Hence, by Lemma 5.4,

$\begin{split}\|\delta\alpha\|&=\operatorname*{\mathbb{E}}_{xy\in\overrightarrow{E}(\mathcal{X})}[d_{h}(\delta\alpha(xy),{\rm
Id})]\\\
&=\operatorname*{\mathbb{E}}_{xy\in\overrightarrow{E}(\mathcal{X})}[d_{h}(\alpha(x)^{-1}\alpha(y),{\rm
Id})]\\\
&=\operatorname*{\mathbb{E}}_{xy\in\overrightarrow{E}(\mathcal{X})}[d_{h}(\alpha(y),\alpha(x)]\\\
&=\frac{1}{2}\operatorname*{\mathbb{E}}_{xy\in\overrightarrow{E}(\mathcal{X})}[\|\alpha(y)-\alpha(x)\|_{HS}^{2}]\\\
&\geq\frac{\gamma(\mathcal{X})}{2}\operatorname*{\mathbb{E}}_{x,y\in
V(\mathcal{X})}[\|\alpha(y)-\alpha(x)\|_{HS}^{2}]\\\
&=\gamma(\mathcal{X})\operatorname*{\mathbb{E}}_{x,y\in
V(\mathcal{X})}[d_{h}(\alpha(y),\alpha(x))]\\\
&\geq\gamma(\mathcal{X})\min_{x\in
V(\mathcal{X})}\underbrace{\operatorname*{\mathbb{E}}_{y\in
V(\mathcal{X})}[d_{h}(\alpha(y),\alpha(x))]}_{d_{h}(\alpha,\alpha(x))}\\\
&\geq\gamma(\mathcal{X})d_{h}(\alpha,Z^{0}(\mathcal{X},{\rm
Sym})),\end{split}$

proving the claim. ∎

###  5.4. Cheeger constants and (high dimensional) expansion

As was probably evident to an observant reader, Proposition 5.5 is a type of
_Cheeger inequality_. To make this statement precise, we need a suitable
notion of a Cheeger constant.

######  Definition 5.6.

The $i^{\rm th}$ _cocycle Cheeger constant_ of a complex $\mathcal{X}$ with
$\Gamma$ coefficients, where $i=0$ or $1$, is

(5.5)
$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

(5.6)
$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_.

When taking permutation coefficients, these notions genralize the classical
Cheeger constant for graphs when $i=0$, as explained in Remark 5.7. Moreover,
when $i=1$ and $\Gamma=\mathbb{F}_{2}$, these notions are closely related to
Gromov’s topological overlapping property [gromov2010singularities,
DKW_cosystolic_exp_implies_overlap]. As we aim to develop further study of
cocycle stability in permutations, we suggest in [CL_part2] a generalization
of the search for bounded coboundary expanders.

######  Remark 5.7.

Let $\mathcal{X}$ be a finite connected $k$-regular graph. The _classical
Cheeger constant_ of $\mathcal{X}$ is

$h(\mathcal{X})=\min\mathopen{}\mathclose{{}\left\\{\frac{|E(A,\bar{A})|}{\min(|A|,|\bar{A}|)}\
\middle|\ \emptyset\neq A\subsetneq V(\mathcal{X})}\right\\},$

where $E(A,\bar{A})$ is the set of edges with one endpoint in $A$ and the
other in its complement $\bar{A}$. Note that if $\alpha\colon
V(\mathcal{X})\to\\{0,1\\}$ is the characteristic function of $A$, and we
identify $\\{0,1\\}$ with ${\rm Sym}(2)$ (as we did in Section 3.1), then
$\frac{|E(A,\bar{A})|}{|E(\mathcal{X})|}=\|\delta\alpha\|$. Moreover, the
$0$-cocycles with ${\rm Sym}(2)$ coefficients are exactly the characteristic
functions of $V(\mathcal{X})$ and $\emptyset$, which we denote by ${\bf 1}$
and ${\bf 0}$ for the moment. Now, $d_{h}(\alpha,{\bf
0})=\|\alpha\|=\frac{|A|}{|V(\mathcal{X})|}$ and $d_{h}(\alpha,{\bf
1})=1-\|\alpha\|=\frac{|\bar{A}|}{|V(\mathcal{X})|}$. It can be verified that
the closest constant function to $\alpha$ is either ${\bf 0}$ or ${\bf 1}$,
even if we allow to range over all constant functions into ${\rm Sym}(n)$.
Hence, $d_{h}(\alpha,Z^{0}(\mathcal{X},{\rm
Sym}))=\frac{\min(|A|,|\bar{A}|)}{|V(\mathcal{X})|}$. All in all,

(5.7)
$\begin{split}h(\mathcal{X})&=\min\mathopen{}\mathclose{{}\left\\{\frac{|E(A,\bar{A})|}{\min(|A|,|\bar{A}|)}\
\middle|\ \emptyset\neq A\subsetneq V(\mathcal{X})}\right\\}\\\
&=\frac{|E(\mathcal{X})|}{|V(\mathcal{X})|}\cdot\min\mathopen{}\mathclose{{}\left\\{\frac{\nicefrac{{|E(A,\bar{A})|}}{{|E(\mathcal{X})|}}}{\nicefrac{{\min(|A|,|\bar{A}|)}}{{|V(\mathcal{X})|}}}\
\middle|\ \emptyset\neq A\subsetneq V(\mathcal{X})}\right\\}\\\
&=\frac{k}{2}\cdot\min\mathopen{}\mathclose{{}\left\\{\frac{\|\delta\alpha\|}{d_{h}(\alpha,Z^{0}(\mathcal{X},{\rm
Sym}))}\ \middle|\ \alpha\in C^{0}(\mathcal{X},{\rm
Sym}(2)),\|\delta\alpha\|\neq 0}\right\\}\\\
&=\frac{k}{2}h_{0}(\mathcal{X},\mathbb{F}_{2})\\\
&\geq\frac{k}{2}h_{0}(\mathcal{X},{\rm Sym}).\end{split}$

Namely, the classical Cheeger constant is (up to a factor of
$\nicefrac{{k}}{{2}}$) the $0^{\rm th}$ cocycle Cheeger constant with
$\mathbb{F}_{2}\cong{\rm Sym}(2)$ coefficients, which upper bounds the cocycle
Cheeger constant with permutation coefficients. By the proof of Proposition
5.5,

(5.8) $h_{0}(\mathcal{X},{\rm Sym})\geq\gamma(\mathcal{X}).$

Combining (5.7) and (5.8), we derive the lower bound in the Cheeger
inequalities [ALON_Milman_Cheeger_1, Alon_Cheeger_2, Dodziuk_Cheeger] (See
also Proposition 4.2.5 in [lubotzky1994discrete]). Moreover, since the Cheeger
inequalities deduce an upper bound on $h(\mathcal{X})$ as a function of the
spectral gap, together with (5.7) we can deduce that also
$h_{0}(\mathcal{X},{\rm Sym})$ is upper bounded by the same bound.

######  Corollary 5.8 (Generalized Cheeger inequalities in the $0^{\rm th}$
dimension).

Let $\mathcal{X}$ be a $k$-regular connected graph. Then,

$\gamma(\mathcal{X})\leq h_{0}(\mathcal{X},{\rm
Sym})\leq\sqrt{8\gamma(\mathcal{X})}.$

###  5.5. Coboundary expansion

In the beginning of the proof of Proposition 5.5, we deduced the following:

######  Fact 5.9.

The $0^{\rm th}$ cohomology of $\mathcal{X}$ with $\Gamma$ coefficients
vanishes if and only if $G(\mathcal{X})$ is connected.

Hence, when we restricted the discussion in Proposition 5.5 and Remark 5.7 to
the connected graph case, we forced the vanishing of the $0^{\rm th}$
cohomology. In that case, as proved in Remark 5.7, the cocycle Cheeger
constant with $\mathbb{F}_{2}$ coefficients is the same as the classical
Cheeger constant. But, for disconnected graphs they differ, and the natural
analogue is the coboundary Cheeger constant. The following is a
straightforward observation:

######  Fact 5.10.

Let $\mathcal{X}$ be a polygonal complex. Then:

  * •

If $h^{B}_{i}(\mathcal{X},\Gamma)>0$, then, in particular, the $i^{\rm th}$
cohomology of $\mathcal{X}$ with $\Gamma$ coefficients vanishes.

  * •

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)$.

The first observation in Fact 5.10 (for $\mathbb{F}_{2}$ coefficients) was a
key ingredient in Linial–Meshulam’s work on cohomology vanishing of random
simplicial complexes [linial_meshulam2006homological]. In a companion paper to
this one [CL_stability_Random_complexes], we discuss it further, and suggest
to study phase transition of the vanishing of the $1^{\rm st}$ cohomology with
permutation coefficients. But, what does it mean for the $1^{\rm st}$
cohomology with permutation coefficients to vanish? The analysis in Section 6
provides a characterization:

######  Fact 5.11.

Let $\mathcal{X}$ be a connected polygonal complex. Then, the $1^{\rm st}$
cohomology of $\mathcal{X}$ with permutation coefficients vanishes if and only
if the fundamental group $\pi_{1}(\mathcal{X},*)$ has no proper finite index
subgroups. Equivalently, $\widehat{\pi_{1}(\mathcal{X},*)}=1$, i.e., the
profinite completion of the fundamental group is trivial.

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. The motivation to study coboundary expansion over
$\mathbb{F}_{2}$ arised from the notion of topological overlapping
[gromov2010singularities], but it also found applications in property testing
[kaufman2014high]. As mentioned before, we further discuss these notions, as
well as topological overlapping, in Part II [CL_part2] and in
[CL_stability_Random_complexes], where we will also illustrate further the
importance of coboundary expansion with permutation coefficients.

##  6\. Proving equivalences

###  6.1. Covering stability is equivalent to cocycle stability

In this (sub) section, we prove Theorem 1.1. Namely, we show that
$\rho$-cocycle stability and $\rho$-covering stability of a polygonal complex
$\mathcal{X}$ are the same. We actually define a one to one correspondence
between $1$-cochains of $\mathcal{X}$ with ${\rm Sym}$ coefficients (up to
some equivalence relation) and coverings of the $1$-skeleton of $\mathcal{X}$
(up to isomorphism). Under this correspondence, $1$-cocycles are mapped to
genuine coverings. Moreover, the global defects are in correspondence. Lastly,
the testers translate to one another under this correspondence, which in turn
preserves the local defect. This idea of encoding graph coverings using
$1$-cochains is classical (cf. [Hatcher_Alg_Top, Linial_Amit2002random,
amit2001random]), and was specifically used in Dinur–Meshulam [Dinur-Meshulam]
in a similar way.

To make the claims from the previous paragraph precise, we need the following
action of $0$-cochains of $\mathcal{X}$ with ${\rm Sym}(n)$ coefficients on
$1$-cochains of $\mathcal{X}$ with ${\rm Sym}(n)$ coefficients:

(6.1) $\forall\alpha\colon\overrightarrow{E}(\mathcal{X})\to{\rm Sym}(n),\
\beta\colon V(\mathcal{X})\to{\rm Sym}(n)\ \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 $\beta.\alpha(\pi)=\beta(x)^{-1}\alpha(\pi)\beta(x)$. In particular,
$\|\delta(\beta.\alpha)\|=\|\delta\alpha\|$, and hence the action preserves
$1$-cocycles.

######  Claim 6.1.

Let $\mathcal{X}$ be a polygonal complex. There is a one to one correspondence
between coverings of $G(\mathcal{X})$ and orbits of $1$-cochains of
$\mathcal{X}$ with permutation coefficients under the action described in
(6.1).

###### Proof.

We first associate with every $1$-cochain
$\alpha\colon\overrightarrow{E}(\mathcal{X})\to{\rm Sym}(n)$ a corresponding
covering $f\colon\mathcal{G}\to G(\mathcal{X})$ as follows:

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

By Fact 4.8, $f$ is a covering.212121Note that the permutation $\alpha(e)$
tells us how the fiber over the terminal point $y$ is mapped to the fiber over
the origin point $x$ and not the other way around. This is because of our
choice of left actions.

On the other hand, if $f\colon\mathcal{G}\to G(\mathcal{X})$ is a degree $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)$. Here we did not have any
choice in the labeling. Now, define $\alpha(e).i$ to be the second coordinate
of $\iota(e,i)$. Note that a different choice of labeling for the fibers
$f^{-1}(x)$ would give rise to another $1$-cochain in the same orbit of the
action of the $0$-cochains. This proves the correspondence. ∎

The encoding in Claim 6.1 allows us to analyze the lifted path $\pi^{\prime}$
used in Algorithm 3. Recall that for every path
$x\xrightarrow{e_{1}}...\xrightarrow{e_{\ell}}y$ in $\mathcal{X}$ and every
$x^{\prime}\in f^{-1}(x)$, there exists a unique path $\pi^{\prime}$ in
$\mathcal{G}$ that starts at $x^{\prime}$ and satisfies $f(\pi^{\prime})=\pi$.
By choosing a $1$-cochain $\alpha$ that corresponds to the covering $f$, we
have chosen a label $(x,i)$ for $x^{\prime}$. To lift
$x\xrightarrow{e_{1}}x_{1}$, we need to find the index $j$ such that
$(x,i)\xrightarrow{(e_{1},j)}(x_{1},j)$. By our construction,
$i=\alpha(e_{1}).j$, which implies
$j=\alpha(e_{1})^{-1}.i=\alpha(\bar{e}_{1}).i$. Therefore, by induction, the
lifted path $\pi^{\prime}$ is of the form

$\begin{split}\pi^{\prime}=&(x,i)\xrightarrow{(e_{1},\alpha(\bar{e}_{1}).i)}(x_{1},\alpha(\bar{e}_{1}).i)\xrightarrow{(e_{2},\alpha(\bar{e}_{2})\circ\alpha(\bar{e}_{1}).i)}(x_{2},\alpha(\bar{e}_{2})\circ\alpha(\bar{e}_{1}).i)\to\dots\\\
&\dots\xrightarrow{(e_{\ell},\alpha(\bar{e}_{\ell})\circ...\circ\alpha(\bar{e}_{1}).i)}(y,\alpha(\bar{e}_{\ell})\circ...\circ\alpha(\bar{e}_{1}).i).\end{split}$

Note that
$\alpha(\bar{e}_{\ell})\circ...\circ\alpha(\bar{e}_{1})=\delta\alpha(\pi)^{-1}$.
Hence, the lifted path of a polygon $\pi$ to $x^{\prime}=(x,i)$ is closed if
and only if $\delta\alpha(\pi)^{-1}.i=i$ (which is if and only if
$\delta\alpha(\pi).i=i$). Therefore, the testers Algorithm 6 and Algorithm 3
are the same when encoding coverings as $1$-cochains. In particular, the
covering $f$ is genuine if and only if $\delta\alpha(\pi)={\rm Id}$ for every
polygon $\pi\in\overrightarrow{P}(\mathcal{X})$, which is the same as saying
$\delta\alpha={\rm Id}$.

######  Corollary 6.2.

Let $\mathcal{X}$ be a polygonal complex. The local defects of Algorithms 3
and 6 are preserved under the corresponednce of Claim 6.1. In particular,
orbits of $1$-cocycles of $\mathcal{X}$ are in one to one correspondence with
isomorphism classes of genuine coverings of $\mathcal{X}$.

######  Claim 6.3.

Let $\mathcal{X}$ be a polygonal complex. The global defects of Algorithms 3
and 6 are preserved under the corresponednce of Claim 6.1.

###### Proof.

Let $\alpha\colon\overrightarrow{E}(\mathcal{X})\to{\rm Sym}(n)$ and
$\beta\colon\overrightarrow{E}(\mathcal{X})\to{\rm Sym}(N)$ be two
$1$-cochains, where $N\geq n$. Let $f\colon\mathcal{G}\to G(\mathcal{X})$ and
$\varphi\colon\mathcal{Y}\to G(\mathcal{X})$ be the coverings associated with
$\alpha$ and $\beta$ respectively, as defined in the proof of Claim 6.1. Then,
we can define a mutual $G(\mathcal{X})$-labeled subgraph $\mathcal{A}$ of
$\mathcal{G}$ and $\mathcal{Y}$ as follows: Its vertices are

$V(\mathcal{A})=V(\mathcal{G})=V(\mathcal{X})\times[n].$

Its edges are

$\overrightarrow{E}(\mathcal{A})=\overrightarrow{E}(\mathcal{G})\cap\overrightarrow{E}(\mathcal{Y})=\\{(e,i)\mid\iota_{\mathcal{G}}(e,i)=\iota_{\mathcal{Y}}(e,i)\\}=\\{(e,i)\mid\alpha(e).i=\beta(e).i\\}.$

Therefore, we found a $G(\mathcal{X})$-labeled subgraph of $\mathcal{G}$ and
$\mathcal{Y}$ with

$|\overrightarrow{E}(\mathcal{A})|=|\\{(e,i)\mid
e\in\overrightarrow{E}(\mathcal{X}),\ i\in[N],\
\alpha(e).i=\beta(e).i\\}|=|\overrightarrow{E}(\mathcal{X})|\cdot N\cdot
d_{h}(\alpha,\beta).$

Hence, recalling the definition of the normalized edit distance (4.2),

(6.2) $d_{edit}(\mathcal{G},\mathcal{Y})\leq
1-\frac{|\overrightarrow{E}(\mathcal{A})|}{|\overrightarrow{E}(\mathcal{Y})|}=d_{h}(\alpha,\beta).$

On the other hand, let $f\colon\mathcal{G}\to G(\mathcal{X})$ be an
$n$-covering and $\varphi\colon\mathcal{Y}\to G(\mathcal{X})$ be an
$N$-covering, where $N\geq n$. If $a\colon\mathcal{A}\to G(\mathcal{X})$ is
the largest $G(\mathcal{X})$-labeled graph that embeds in both, then we can
think of $V(\mathcal{A})\subseteq V(\mathcal{G})\cap V(\mathcal{Y})$. For
every $x\in V(\mathcal{X})$, if $|a^{-1}(x)|=k_{x}\leq n$ then we can label
its vertices as $\\{(x,i)\\}_{i=1}^{k_{x}}$. Further, label the vertices of
$f^{-1}(x)\setminus a^{-1}(x)$ by $\\{(x,i)\\}_{i=k_{x}+1}^{n}$ and the
vertices of $\varphi^{-1}(x)\setminus a^{-1}(x)$ by
$\\{(x,i)\\}_{i=k_{x}+1}^{N}$. Note that we essentially chose an arbitrary
embedding of $V(\mathcal{G})\setminus V(\mathcal{A})$ into
$V(\mathcal{Y})\setminus V(\mathcal{A})$. By this choice of labeling, we get
$\overrightarrow{E}(\mathcal{A})\subseteq\overrightarrow{E}(\mathcal{G})\cap\overrightarrow{E}(\mathcal{Y})$.
But $\mathcal{A}$ was the largest $G(\mathcal{X})$-labeled embedding into
$\mathcal{G}$ and $\mathcal{Y}$, which implies
$\overrightarrow{E}(\mathcal{A})=\overrightarrow{E}(\mathcal{G})\cap\overrightarrow{E}(\mathcal{Y})$.
Let $\alpha$ and $\beta$ be the $1$-cochain encodings of $f$ and $\varphi$
respectively, defined by our choice of labelings (as done in the proof of
Claim 6.1). By definition,

$\begin{split}\overrightarrow{E}(\mathcal{G})\cap\overrightarrow{E}(\mathcal{Y})&=\\{(e,i)\mid
e\in\mathcal{X},\ i\in[N],\
\iota_{\mathcal{G}}(e,i)=\iota_{\mathcal{Y}}(e,i)\\}\\\ &=\\{(e,i)\mid
e\in\mathcal{X},\ i\in[N],\ \alpha(e).i=\beta(e).i\\}.\end{split}$

Therefore,

(6.3)
$d_{h}(\alpha,\beta)=\operatorname*{\mathbb{P}}_{e\in\overrightarrow{E}(\mathcal{X}),i\in[N]}[\alpha(e).i=\beta(e).i]=\frac{|\overrightarrow{E}(\mathcal{G})\cap\overrightarrow{E}(\mathcal{Y})|}{|\overrightarrow{E}(\mathcal{Y})|}=d_{edit}(\mathcal{G},\mathcal{Y}).$

Thus, if $\varphi\colon\mathcal{Y}\to\mathcal{X}$ is the closest genuine cover
to $f\colon\mathcal{G}\to G(\mathcal{X})$, then there is an encoding of them
where the normalized Hamming distance is the same as the normalized edit
distance. Together with (6.2), this proves that the global defects are
preserved under this correspondence. ∎

By combining Claim 6.1, Corollary 6.2 and Claim 6.3, Theorem 1.1 is proven.

###  6.2. Homomorphism stability is equivalent to cocycle stability

In this section we prove Theorems 1.2 and 1.3. Like in the previous section,
there is a classical correspondence between presentations and polygonal
complexes. One direction, from presentations to complexes, is via the
_presentation complex_ of the group (cf. Corollary 1.28, page 52, in
[Hatcher_Alg_Top]). The other direction, from complexes to presentaions, is
via the presentation of the fundamental group associated with the reatraction
of a spanning tree. We now recall these constructions in detail.

######  Definition 6.4.

Given a presentation $\Gamma=\langle S|R\rangle$, one can define the
presentation complex $\mathcal{X}_{\langle S|R\rangle}$ to be 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)$. Note that since there is only
one vertex, this is a closed path regardless of $r$.

###### Proof of Theorem 1.2.

Every function $f\colon S\to{\rm Sym}(n)$ can be extended to a $1$-cochain
$\alpha_{f}$ on $\mathcal{X}_{\langle S|R\rangle}$ in an antisymmetric way.
Namely, $\alpha_{f}(e(s))=f(s),\alpha_{f}(\overline{e(s)})=f(s)^{-1}$.
Furthermore, for $r=s_{1}^{\varepsilon_{1}}\cdot...\cdot
s_{\ell}^{\varepsilon_{\ell}}\in R$ we get

$\delta\alpha_{f}(\pi(r))=\prod_{i=1}^{\ell}\alpha_{f}(e(s_{i}))^{\varepsilon_{i}}=\prod_{i=1}^{\ell}f(s_{i})^{\varepsilon_{i}}=f(r).$

Hence

$\begin{split}{\rm
def}_{cocyc}(\alpha_{f})&=\operatorname*{\mathbb{E}}_{[\pi]\in
P(\mathcal{X}_{\langle S|R\rangle})}[d_{h}(\delta\alpha_{f}(\pi),{\rm Id})]\\\
&=\operatorname*{\mathbb{E}}_{r\in R}[d_{h}(\delta\alpha_{f}(\pi(r)),{\rm
Id})]\\\ &=\operatorname*{\mathbb{E}}_{r\in R}[d_{h}(f(r),{\rm Id})]\\\ &={\rm
def}_{hom}(f).\end{split}$

In particular, this correspondence $f\leftrightarrow\alpha_{f}$ associates the
homomorphisms $\textrm{Hom}(\Gamma,{\rm Sym})$ with the cocycles
$Z^{1}(\mathcal{X}_{\langle S|R\rangle},{\rm Sym})$.

Let $\varphi\colon S\to{\rm Sym}(N)$ be another function, and let
$\alpha_{\varphi}$ be the associated $1$-cochain on $\mathcal{X}_{\langle
S|R\rangle}$. Then,

$\begin{split}d_{h}(\alpha_{f},\alpha_{\varphi})&=\operatorname*{\mathbb{E}}_{e\in\overrightarrow{E}(\mathcal{X}_{\langle
S|R\rangle})}[d_{h}(\alpha_{f}(e),\alpha_{\varphi}(e))]\\\
&=\operatorname*{\mathbb{E}}_{s\in
S}[d_{h}(\alpha_{f}(e(s)),\alpha_{\varphi}(e(s)))]\\\
&=\operatorname*{\mathbb{E}}_{s\in S}[d_{h}(f(s),\varphi(s))]\\\
&=d_{h}(f,\varphi).\end{split}$

Therefore, the global defects are preserved. ∎

We now recall the presentation of the fundamental group associated with the
retraction of a tree. This presentation can be attained by van Kampen’s
Theorem (See Chapter 1.2 in [Hatcher_Alg_Top]).

######  Definition 6.5.

Let $\mathcal{X}$ be a connected polygonal complex. Choose a base point $*\in
V(\mathcal{X})$ and a spanning tree $T$ in $\mathcal{X}$. There is a standard
presentation $\langle S|R\rangle$ of the fundamental group
$\pi_{1}(\mathcal{X},*)$ with respect to $T$. For the generator set $S$, we
choose a representative $e$ out of every unoriented edge $\\{e,\bar{e}\\}\in
E(\mathcal{X})$ which is outside of the spanning tree $T$. For relations, we
take a single representative $\pi$ from each unoriented polygon $[\pi]\in
P(\mathcal{X})$. Now, the way we interpret $\pi$ as a word in $S$ is by
replacing each $\bar{e}$ for which $e\in S$ by $e^{-1}$, and by deleting every
edge $e\in T$.

###### Proof of Theorem 1.3.

Let $\alpha\colon\overrightarrow{E}(\mathcal{X})\to{\rm Sym}(n)$ be a
$1$-cochain of $\mathcal{X}$. We now define a $0$-cochain $\beta$ which
depends on $\alpha,*$ and $T$: For every vertex $y\in V(\mathcal{X})$, let
$\pi_{y}$ be the unique path in $T$ from $y$ to the base point $*$. Define
$\beta\in C^{0}(\mathcal{X},{\rm Sym})$ by

$\beta(y)=\alpha(\pi_{y}).$

Let $y\xrightarrow{e}z\in T$ be an edge in the spanning tree oriented towards
the basepoint $*$ (namely, the path between $*$ and $y$ in $T$ passes through
$z$). Hence, $\pi_{y}=e\pi_{z}$. Therefore

$\begin{split}\beta.\alpha(e)&=\beta(y)^{-1}\alpha(e)\beta(z)\\\
&=\alpha(\pi_{y})^{-1}\alpha(e)\alpha(\pi_{z})\\\
&=\alpha(e\pi_{z})^{-1}\alpha(e\pi_{z})\\\ &={\rm Id}.\end{split}$

Since the action of the $0$-cochains on the $1$-cochains does not effect the
local or global defects of the $1$-cochain, we can assume the $\alpha$ we were
given was already $\beta.\alpha$. Namely, it is the identity for every $e$ in
the tree. Then, running the homomorphism tester (Algorithm 1) on
$\alpha|_{S}\colon S\to{\rm Sym}(n)$ is the same as running the $1$-cocycle
tester (Algorithm 6) on $\alpha$. Thus,

(6.4) ${\rm def}_{hom}(\alpha|_{S})={\rm def}_{cocyc}(\alpha).$

But, the global defects may be different. If $f\colon S\to{\rm Sym}(N)$ is the
closest homomorphism to $\alpha|_{S}$, then we can extend $f$ to be the
identity on the tree $T$ and it becomes a $1$-cocycle of $\mathcal{X}$.
Furthermore

$\begin{split}d_{h}(f,\alpha|_{S})&=\operatorname*{\mathbb{E}}_{e\notin
T}[d_{h}(f(e),\alpha(e))]\\\
&=\frac{|E(\mathcal{X})|}{|E(\mathcal{X})|-|T|}\operatorname*{\mathbb{E}}_{e\in\overrightarrow{E}(\mathcal{X})}[d_{h}(f(e),\alpha(e))]\\\
&\geq d_{h}(f,\alpha).\end{split}$

Hence, ${\rm Def}_{hom}(\alpha|_{S})\geq{\rm Def}_{cocyc}(\alpha)$. Together
with (6.4), this proves clause $(1)$ of the Theorem.

For clause $(2)$ we apply a naive operation, which would seem very wasteful at
first glance. In Remark 6.8, we show that clause $(2)$ is essentially tight,
and thus this process is optimal for the worst case scenarios.

Let $\varphi\colon\overrightarrow{E}(\mathcal{X})\to{\rm Sym}(N)$ be the
closest cocycle to $\alpha$. Even though $\alpha$ is trivial on $T$, and thus
$\alpha|_{S}$ is in the potential homomorphisms from $\pi_{1}(\mathcal{X},*)$
to ${\rm Sym}(n)$, $\varphi$ is not necessarily trivial on $T$. To amend this,
we will apply on $\varphi$ a similar operation to the one we applied on
$\alpha$ in the beginning of this proof. Namely, there is a $0$-cochain
$\beta^{\prime}\colon V(\mathcal{X})\to{\rm Sym}(N)$ such that
$\beta^{\prime}.\varphi$ is trivial on $T$. How far can
$\beta^{\prime}.\varphi|_{S}$ be from $\alpha|_{S}$? Recall that
$\beta^{\prime}.\varphi|_{S}(y\xrightarrow{e}z)=\varphi(\pi_{y})^{-1}\varphi(e)\varphi(\pi_{z})$.
On the other hand,
$\alpha|_{S}(y\xrightarrow{e}z)=\alpha(e)=\alpha(\pi_{y})^{-1}\alpha(e)\alpha(\pi_{z})$,
since $\alpha$ is trivial in the tree. Let
$\pi_{y}=y\xrightarrow{e_{1}}...\xrightarrow{e_{k}}*$ and
$\pi_{z}=z\xrightarrow{e^{\prime}_{1}}...\xrightarrow{e^{\prime}_{m}}*$ be the
paths along the tree. Then,

$\begin{split}d_{h}(\alpha|_{S}(e),\beta^{\prime}.\varphi|_{S}(e))&=d_{h}(\alpha(\pi_{y})^{-1}\alpha(e)\alpha(\pi_{z}),\varphi(\pi_{y})^{-1}\varphi(e)\varphi(\pi_{z}))\\\
&=d_{h}(\alpha(\bar{e}_{k})...\alpha(\bar{e}_{1})\alpha(e)\alpha(e^{\prime}_{1})...\alpha(e^{\prime}_{m}),\varphi(\bar{e}_{k})...\varphi(\bar{e}_{1})\varphi(e)\varphi(e^{\prime}_{1})...\varphi(e^{\prime}_{m}))\\\
&\leq
d_{h}(\alpha(e),\varphi(e))+\sum_{i=1}^{k}d_{h}(\alpha(e_{i}),\varphi(e_{i}))+\sum_{j=1}^{m}d_{h}(\alpha(e^{\prime}_{j}),\varphi(e^{\prime}_{j}))\\\
&=(\diamond).\end{split}$

Note that in the last sum, no oriented edge in
$\overrightarrow{E}(\mathcal{X})$ appears more than once. Hence,

$\begin{split}(\diamond)\leq\sum_{e\in\overrightarrow{E}(\mathcal{X})}d_{h}(\alpha(e),\varphi(e))=|\overrightarrow{E}(\mathcal{X})|d_{h}(\alpha,\varphi).\end{split}$

Therefore,

$\begin{split}d_{h}(\alpha|_{S},\beta^{\prime}.\varphi|_{S})&=\operatorname*{\mathbb{E}}_{e\notin
T}[d_{h}(\alpha|_{S}(e),\beta^{\prime}.\varphi|_{S}(e))]\\\
&\leq\operatorname*{\mathbb{E}}_{e\notin
T}\mathopen{}\mathclose{{}\left[|\overrightarrow{E}(\mathcal{X})|d_{h}(\alpha,\varphi)}\right]\\\
&=|\overrightarrow{E}(\mathcal{X})|d_{h}(\alpha,\varphi),\end{split}$

which finishes the proof. ∎

######  Corollary 6.6.

Note that the proofs of Theorems 1.2 and 1.3 apply in a much more general
setup. We could have defined homomorphism stability with $(G,d)$-coefficients:
Let $\Gamma\cong\langle S|R\rangle$ be a finite presentation. Let $f\colon
S\to G$ be a function, which extends to a homomorphism from $\mathcal{F}_{S}$.
By letting

${\rm def}_{hom,G}(f)=\operatorname*{\mathbb{E}}_{r\in R}[d(f(r),{\rm
Id}_{G})]$

and

${\rm
Def}_{hom,G}(f)=\min\mathopen{}\mathclose{{}\left\\{\operatorname*{\mathbb{E}}_{s\in
S}[d(f(s),\varphi(s))]\ \middle|\ \varphi\in Hom(\Gamma,G)}\right\\},$

we can define that $\langle S|R\rangle$ is $\rho$-homomorphism stable with
$(G,d)$-coefficients whenever

${\rm Def}_{hom,G}(f)\leq\rho({\rm def}_{hom,G}(f)).$

The proofs of Theorems 1.2 and 1.3 show that this condition is equivalent to
cocycle stability in the first dimension with $(G,d)$-coefficients. Since
variants of this type are extensively studied — Hilbert–Schmidt stablity
[HadwinShulman, BeckerLubotzky], Frobenius stability [DGLT, LubotzkyOppenheim]
and so on — our framework may allow one to tackle them as well.

In Part II of this paper, we prove the following fact:

######  Fact 6.7 ([CL_part2]).

Let $\mathcal{X}$ be the _complete complex_ on $d$ vertices. Namely, it has a
vertex set $[d]$, an edge set $\\{ij\mid i\neq j\in[d]\\}$ and a triangle set
$\\{ijk\mid i\neq j\neq k\in[d]\\}$. Then $\mathcal{X}$ is $\rho$-cocycle
stable with $\rho(\varepsilon)=\varepsilon$.

######  Remark 6.8.

We now show that the bound in clause $(2)$ of Theorem 1.3 is, up to a factor
of $12$, tight. Let us consider the complete complex $\mathcal{X}$ as in Fact
6.7. Choose the spanning tree $T$ to be the path $1\to 2\to 3\to...\to d$.
Recall that $S=\overrightarrow{E}(\mathcal{X})\setminus T$, and let
$\alpha\colon S\to\mathbb{F}_{2}\cong{\rm Sym}(2)$ be the following:

$\forall i\xrightarrow{e}j\notin T\ \colon\ \
\alpha(e)=\begin{cases}1&i\leq\nicefrac{{d}}{{2}},j>\nicefrac{{d}}{{2}},\\\
1&j\leq\nicefrac{{d}}{{2}},i>\nicefrac{{d}}{{2}},\\\
0&\textrm{otherwise}.\end{cases}$

Note that if we extend $\alpha$ to be trivial on $T$, it is almost the
characteristic function of the cut of $\mathcal{X}$ separating
$\\{1,...,\lfloor\nicefrac{{d}}{{2}}\rfloor\\}$ and the rest of $[d]$, except
$\alpha(\lfloor\nicefrac{{d}}{{2}}\rfloor\to\lfloor\nicefrac{{d}}{{2}}\rfloor+1)=0$
and not $1$ (since this edge is part of $T$). It can be checked that the only
triangles that are violated by $\alpha$ are those which contain the edge
$\lfloor\nicefrac{{d}}{{2}}\rfloor\to\lfloor\nicefrac{{d}}{{2}}\rfloor+1$, and
there are $d-2$ of them. Hence, ${\rm def}_{cocyc}(\alpha)={\rm
def}_{hom}(\alpha)=\frac{d-2}{\binom{d}{3}}=\frac{6}{d(d-1)}.$ On the other
hand, since $\pi_{1}(\mathcal{X},*)=1$, there only homomorphisms from $S$ to
${\rm Sym}(n)$ are the constant identity ones, and clearly the closest one is
the one into ${\rm Sym}(2)\cong\mathbb{F}_{2}$ which is the constant $0$
function. Therefore,

${\rm Def}_{hom}(\alpha)=\operatorname*{\mathbb{E}}_{ij\notin
T}[\alpha(ij)=1]=\frac{\lfloor\nicefrac{{d}}{{2}}\rfloor\lceil\nicefrac{{d}}{{2}}\rceil-1}{\binom{d-1}{2}-d+1}\approx\frac{1}{2}.$

All in all,

$\frac{{\rm Def}_{hom}(\alpha)}{{\rm
def}_{hom}(\alpha)}\approx\frac{\frac{1}{2}}{\frac{6}{d(d-1)}}=\frac{|\overrightarrow{E}(\mathcal{X})|}{12},$

which, together with Fact 6.7, proves that the cocycle stability rate of
$\mathcal{X}$ is at least $\frac{|\overrightarrow{E}(\mathcal{X})|}{12}$
better than the homomorphism stability of the presentation of
$\pi_{1}(\mathcal{X},*)$ obtained by retracting $T$.

This example is a bit weak, since there are better spanning trees that will
yield a better (though, still quite a bad) deterioration parameter. We wonder
whether there is a complex such that all of its spanning trees produce
presentations with homomorphism stability rate deteriorating by
$\Omega(|\overrightarrow{E}(\mathcal{X})|)$ compared to the cocycle stability
rate.

##  7\. Alternative distributions

Since we presented the property testing framework in a very general fashion in
Section 2, it was not natural to discuss various normalization and weighting
systems other than the uniform ones. But, for other problems (cf. [CL_part2]),
there is a natural way of extending the definitions to include weights.

Given a polygonal complex $\mathcal{X}$, we can provide with it probability
distributions $\mu_{i}$ on $\mathcal{X}(i)$. Then, the distance between the
cochains $\alpha\colon\overrightarrow{\mathcal{X}}(i)\to{\rm Sym}(n)$ and
$\varphi\colon\overrightarrow{\mathcal{X}}(i)\to{\rm Sym}(N)$ would be

(7.1)
$d_{h}(\alpha,\varphi)=\operatorname*{\mathbb{E}}_{[x]\sim\mu_{i}}[d_{h}(\alpha(x),\varphi(x))].$

Note that (5.1) is a special case of (7.1) by choosing $\mu_{i}$ to be the
uniform distributions on the un-oriented cells. Furthermore, the edit distance
between $\mathcal{X}$-labeled graphs can be weighted according to $\mu_{1}$.
The sampling procedure of a polygon in Algorithms 3 and 6 (with $i=1$) can be
taken to be according to $\mu_{2}$. The correspondence of Theorem 1.1 which
was proved in Section 6.1 is still valid in this generalized setup, as long as
the weights on the complex $\mathcal{X}$ are fixed.

Similarly, one can associate a measure $\mu_{S}$ on $S$ and $\mu_{R}$ on $R$.
Then, define the distance between $f\colon S\to{\rm Sym}(n)$ and
$\varphi\colon S\to{\rm Sym}(N)$ in a similar fashion to (7.1),

$d_{h}(f,\varphi)=\operatorname*{\mathbb{E}}_{s\sim\mu_{S}}[d_{h}(f(s),\varphi(s))].$

Furthermore, we can sample the relation in Algorithm 1 according to $\mu_{R}$.
In this generalized framework, Theorem 1.2 can be proved as in Section 6.2 by
associating with $X_{\langle S|R\rangle}$ the measures $\mu_{1}=\mu_{S}$ on
its edges and $\mu_{2}=\mu_{R}$ on its polygons. There is a weighted version
of Theorem 1.3 as well, but we omit it from this discussion.

Though this generalized form does not imply any relation between the
$\mu_{i}$’s, there is a natural choice which behaves well when perturbations
are applied to the studied object. Let us focus on cocycle stability, which we
now know is equivalent to the others under the appropriate corresondences of
Theorems 1.1,1.2 and 1.3. For an edge $e$ and a polygon
$\pi=e_{1}...e_{\ell}$, the occurrence number of $e$ in $\pi$ is

$OC(e\prec\pi)=|\\{i\in\\{1,...,\ell\\}\mid[e_{i}]=[e]\\}|.$

Note that the occurence number is independent of the chosen orientation of the
polygon or edge. Given a distribution $\mu_{2}$ on un-oriented polygons of
$\mathcal{X}$, let us define the following weighting system on edges

$\begin{split}\forall[e]\in E(\mathcal{X})\ \colon\ \
w([e])&=\operatorname*{\mathbb{E}}_{[\pi]\sim\mu_{2}}\mathopen{}\mathclose{{}\left[OC(e\prec\pi)}\right].\end{split}$

Namely, the weight of $[e]$ is the expected number of times it appears in a
polygon sampled according to $\mu_{2}$. Then, let

(7.2) $\begin{split}\forall[e]\in E(\mathcal{X})\ \colon\ \
\mu_{1}([e])&=\frac{w([e])}{\sum_{[e^{\prime}]\in
E(\mathcal{X})}w(e^{\prime})}.\end{split}$

The reason this weighting system is natural is that it behaves well under
small perturbations, as the following claim shows.

######  Claim 7.1.

Let $\mathcal{X}$ be a polygonal complex, let $\mu_{2}$ be some distribution
on its polygons, and let $L$ be the maximal length of a polygon in
$\mathcal{X}$. Choose $\mu_{1}$ to be the distribution from (7.2). Let
$\alpha\colon\overrightarrow{E}(\mathcal{X})\to{\rm Sym}(n)$ and
$\varphi\colon\overrightarrow{E}(\mathcal{X})\to{\rm Sym}(N)$ be two
$1$-cochains. Then,

$d_{h}(\delta\alpha,\delta\varphi)\leq\operatorname*{\mathbb{E}}_{[\pi]\sim\mu_{2}}[\ell(\pi)]\cdot
d_{h}(\alpha,\varphi)\leq L\cdot d_{h}(\alpha,\varphi).$

In particular, if two cochains are close, then their local defects are also
close.

###### Proof.

Let us calculate,

$\begin{split}d_{h}(\delta\alpha,\delta\varphi)&=\operatorname*{\mathbb{E}}_{[e_{1}...e_{\ell}]\sim\mu_{2}}[d_{h}(\delta\alpha(e_{1}...e_{\ell}),\delta\varphi(e_{1}...e_{\ell}))]\\\
&=\operatorname*{\mathbb{E}}_{[e_{1}...e_{\ell}]\sim\mu_{2}}[d_{h}(\alpha(e_{1})...\alpha(e_{\ell}),\varphi(e_{1})...\varphi(e_{\ell}))]\\\
&\leq\operatorname*{\mathbb{E}}_{[e_{1}...e_{\ell}]\sim\mu_{2}}\mathopen{}\mathclose{{}\left[\sum_{j=1}^{\ell}d_{h}(\alpha(e_{j}),\varphi(e_{j}))}\right]\\\
&=\operatorname*{\mathbb{E}}_{[\pi]\sim\mu_{2}}\mathopen{}\mathclose{{}\left[\sum_{[e]\in
E(\mathcal{X})}OC(e\prec\pi)d_{h}(\alpha(e),\varphi(e))}\right]\\\
&=\sum_{[e]\in
E(\mathcal{X})}\underbrace{\operatorname*{\mathbb{E}}_{[\pi]\sim\mu_{2}}\mathopen{}\mathclose{{}\left[OC(e\prec\pi)}\right]}_{w([e])}d_{h}(\alpha(e),\varphi(e))\\\
&=\mathopen{}\mathclose{{}\left(\sum_{[e^{\prime}]\in
E(\mathcal{X})}w(e^{\prime})}\right)\mathopen{}\mathclose{{}\left(\sum_{[e]\in
E(\mathcal{X})}\mu_{1}([e])d_{h}(\alpha(e),\varphi(e))}\right)\end{split}$

Now, on the one hand,

$\sum_{[e]\in
E(\mathcal{X})}\mu_{1}([e])d_{h}(\alpha(e),\varphi(e))=\operatorname*{\mathbb{E}}_{[e]\sim\mu_{1}}[d_{h}(\alpha(e),\varphi(e))]=d_{h}(\alpha,\varphi).$

On the other hand,

$\sum_{[e^{\prime}]\in
E(\mathcal{X})}w(e^{\prime})=\operatorname*{\mathbb{E}}_{[\pi]\sim\mu_{2}}\mathopen{}\mathclose{{}\left[\sum_{[e^{\prime}]\in
E(\mathcal{X})}OC(e\prec\pi)}\right]=\operatorname*{\mathbb{E}}_{[\pi]\sim\mu_{2}}[\ell(\pi)]\leq
L,$

where $\ell(\pi)$ is the length of the polygon $\pi$, defined in Definition
4.3. This finishes the proof. ∎

## References