# Virtually free groups are stable in permutations

Nir Lazarovich  and  Arie Levit

###### Abstract.

We prove that finitely generated virtually free groups are stable in
permutations. As an application, we show that almost-periodic almost-
automorphisms of labelled graphs are close to periodic automorphisms.

NL is supported by the Israel Science Foundation (grant No. 1562/19) and the
German-Israeli Foundation for Scientific Research and Development.

##  1\. Introduction

A finitely generated group $G$ is called stable in permutations (in short
P-stable) if every almost action of $G$ on a finite set is close to an honest
action (see §2 for definitions). For the ubiquitous class of sofic groups, the
property of P-stability can be seen as a stronger form of residual finiteness
[1]. Our main result is:

######  Theorem A.

Every finitely generated virtually free group is P-stable.

It is trivially true that free groups are P-stable. But while residual
finiteness is preserved under passing to finite index subgroups (or rather to
any subgroup), this fact is not clear in general for P-stability.

To the best of our knowledge Theorem A gives the first examples of P-stable
groups which are not free products of P-stable amenable groups. Note that
while fundamental groups of closed orientable surfaces are known to be
flexibly P-stable [3], it is not clear if these groups are P-stable in the
strict sense.

As a special case of Theorem A we answer the following question of Lubotzky.

######  Corollary 1.1.

The modular group $\mathrm{SL}_{2}(\mathbb{Z})$ is P-stable.

Interestingly P-stability is not, generally speaking, preserved under direct
products — for example, the groups $F_{2}\times\mathbb{Z}$ are not P-stable
[2]. This phenomenon is to be contrasted with the fact that the product groups
$F_{2}\times(\mathbb{Z}/n\mathbb{Z})$ are P-stable for all $n\in\mathbb{N}$,
as follows from Theorem A. As a consequence of the P-stability of these groups
we are able to deduce:

######  Corollary B.

Fix some $d,n\in\mathbb{N}$. Let $F_{d}$ be the free group of rank $d$ and
$\mathcal{G}_{d}$ be the family of finite labelled Schreier graphs of $F_{d}$.
Then for every graph $\Gamma\in\mathcal{G}_{d}$ and every $\delta$-almost
automorphism $\alpha$ of $\Gamma$ of $\delta$-almost order $n$, there is a
graph $\Gamma^{\prime}\in\mathcal{G}_{d}$ on the same vertex set as $\Gamma$
and $O(\delta)$-close to $\Gamma$ and an automorphism $\alpha^{\prime}$ of
$\Gamma^{\prime}$ which is $O(\delta)$-close to $\alpha$ and has order $n$.

More details and a precise statement of Corollary B can be found in §8 below.

### Stable epimorphisms

Stallings theorem on ends of groups [5, 6] implies that a finitely generated
group $G$ is virtually free if and only if $G$ is isomorphic to the
fundamental group $\pi_{1}(\mathcal{G},T)$ of a finite graph of groups
$\mathcal{G}$ with finite vertex groups with respect to some maximal spanning
tree $T$ (see §3 for the definition of $\pi_{1}(\mathcal{G},T)$).

Naturally associated to the graph of groups $\mathcal{G}$ and the maximal
spanning tree $T$ there is another group $\overline{\pi}_{1}(\mathcal{G},T)$
admitting a quotient map
$\overline{\pi}_{1}(\mathcal{G},T)\to\pi_{1}(\mathcal{G},T)$. This group is
isomorphic to the free product of the vertex groups of $\mathcal{G}$ with the
topological fundamental group of the underlying graph of $\mathcal{G}$. As
finite groups are P-stable [1] it follows immediately that the group
$\overline{\pi}_{1}(\mathcal{G},T)$ is P-stable.

Motivated by this, we introduce a relative notion of P-stable epimorphisms,
see Definition 2.1. In particular, a finitely generated group $G$ is P-stable
in the usual sense if and only if the natural epimorphism from the free group
in the generators of $G$ onto the group $G$ is P-stable. Theorem A is thereby
reduced to the following statement, to which the major part of this work is
dedicated.

######  Theorem 1.2.

The epimorphism $\overline{\pi}_{1}(\mathcal{G},T)\to\pi_{1}(\mathcal{G},T)$
is P-stable.

A detailed outline of the proof of Theorem 1.2 can be found in §3 below, after
the necessary definitions and notations are set in place.

##  2\. P-stable epimorphisms

Let $X$ be a finite set. Consider the normalized Hamming distance $d_{X}$ on
the symmetric group $\operatorname{Sym}(X)$ given by

$d_{X}(\sigma_{1},\sigma_{2})=\frac{1}{|X|}|\\{x\in
X\>:\>\sigma_{1}(x)\neq\sigma_{2}(x)\\}|$

for all pairs $\sigma_{1},\sigma_{2}\in\operatorname{Sym}(X)$. Note that the
metric $d_{X}$ is bi-invariant.

Let $\overline{G}$ be a group with finite generating set $S$. Define a metric
$d_{X,S}$ on the set $\mathrm{Hom}(\overline{G},\operatorname{Sym}(X))$ of all
group homomorphisms $\rho:\overline{G}\to\operatorname{Sym}(X)$ by

$d_{X,S}(\rho,\rho^{\prime})=\sum_{s\in S}d_{X}(\rho(s),\rho(s^{\prime}))$

for each pair
$\rho,\rho^{\prime}\in\mathrm{Hom}(\overline{G},\operatorname{Sym}(X))$.

Let $N\lhd\overline{G}$ be a normal subgroup normally generated by some finite
subset $R\subset\overline{G}$. Denote $G=\overline{G}/N$. We say that an
action $\rho:\overline{G}\to\operatorname{Sym}(X)$ is a _$\delta$ -almost
$G$-action_ if

$\sum_{r\in R}d_{X}(\rho(r),\operatorname{id})<\delta.$

This terminology is justified by the observation that $\rho$ is an honest
$G$-action if and only if it is a $\delta$-almost $G$-action with respect to
$\delta=0$. Note that strictly speaking this notion depends on fixing the
normal generating set $R$.

######  Definition 2.1.

The epimorphism $\phi:\overline{G}\to G$ is _P-stable_ if for every
$\varepsilon>0$ there is a $\delta>0$ such that for every $\delta$-almost
$G$-action $\rho:\overline{G}\to\operatorname{Sym}(X)$ there is a $G$-action
$\rho^{\prime}:G\to\operatorname{Sym}(X)$ with
$d_{X,S}(\rho,\rho^{\prime}\circ\phi)<\varepsilon$.

######  Lemma 2.2.

The P-stability of the epimorphism $\phi:\overline{G}\to G$ is a well-defined
notion (i.e. it is independent of the choices of the finite sets $S$ and $R$).

###### Proof.

It is easy to see that if $S_{1}$ and $S_{2}$ are two finite generating sets
for the group $G$ then the resulting metrics $d_{X,S_{1}}$ and $d_{X,S_{2}}$
on the set $\mathrm{Hom}(\overline{G},\operatorname{Sym}(X))$ are bi-Lipschitz
equivalent. A similar argument, taking into account the bi-invariance of the
normalized Hamming metric $d_{X}$, shows that if $R_{1}$ and $R_{2}$ are two
finite normal generating sets for the subgroup $N\lhd\overline{G}$ then there
is a constant $C=C(R_{1},C_{2})>1$ such that

$C^{-1}\sum_{r\in R_{2}}d_{X}(\rho(r),\operatorname{id})\leq\sum_{r\in
R_{1}}d_{X}(\rho(r),\operatorname{id})\leq C\sum_{r\in
R_{2}}d_{X}(\rho(r),\operatorname{id}).$

The conclusion follows from these observations. ∎

Let $H$ be any group admitting a finite generating set $S$ and $F(S)$ be the
free group in the generators $S$. Observe that the natural homomorphism
$F(S)\to H$ is P-stable if and only if the group $H$ is $P$-stable in the
usual sense.

######  Remark 2.3.

Every split epimorphism is P-stable.

The following follows immediately from Definition 2.1.

######  Lemma 2.4.

Let
$\overline{\overline{G}}\overset{\phi}{\twoheadrightarrow}\overline{G}\overset{\psi}{\twoheadrightarrow}G$
be a sequence of epimorphisms with normally finitely generated kernels. If
$\phi$ and $\psi$ are P-stable then $\psi\circ\phi$ is P-stable.

We have occasion to use Lemma 2.4 only in the following special form: if the
group $\overline{G}$ is $P$-stable and $\phi:\overline{G}\twoheadrightarrow G$
is a $P$-stable epimorphism then the group $G$ is $P$-stable.

######  Remark 2.5.

It seems an interesting problem to look for other non-trivial instances of
P-stable epimorphisms.

##  3\. The fundamental group of a graphs of groups

We recall the definition of the fundamental group of a graph of groups and in
particular list its defining relations. This is followed by a detailed sketch
of proof for our Theorem A a well as for the “relative” Theorem 1.2. Lastly we
introduce some useful asymptotic notations.

### Graphs of groups

We use Serre’s notation for graphs [4]. In this notation, a graph $\Gamma$
consists of a set of vertices $V(\Gamma)$ and a set of edges $E(\Gamma)$. Each
edge $e\in E(\Gamma)$ has an origin $o(e)\in V(\Gamma)$ and a terminus
$t(e)\in V(\Gamma)$. Moreover each edge $e\in E(\Gamma)$ admits a distinct
opposite edge $\bar{e}\in E(\Gamma)$ that satisfies $\bar{\bar{e}}=e$,
$o(\bar{e})=t(e)$ and $t(\bar{e})=o(e)$. Every pair of “oriented” edges
$\\{e,\bar{e}\\}\subset E(\Gamma)$ represents a single “geometric” edge. An
orientation of the graph $\Gamma$ is a subset $\vec{E}(\Gamma)\subset
E(\Gamma)$ containing exactly a single edge from each pair $\\{e,\bar{e}\\}$.

######  Definition 3.1.

A _graph of groups_ $\mathcal{G}$ is

$\mathcal{G}=(\Gamma,\\{G_{v}\\}_{v\in V(\Gamma)},\\{G_{e}\\}_{e\in
E(\Gamma)},\\{i_{e}:G_{e}\to G_{t(e)}\\}_{e\in E(\Gamma)})$

where $\Gamma$ is a connected graph, $G_{v}$ is a vertex group for all $v\in
V(\Gamma)$, $G_{e}$ is an edge group for all edges $e\in E(\Gamma)$ with
$G_{e}=G_{\bar{e}}$ and $\iota_{e}:G_{e}\to G_{t(e)}$ are injective
homomorphisms.

Let $\mathcal{G}$ be a graph of groups. Fix an orientation $\vec{E}(\Gamma)$
and a maximal spanning tree $T\subset\Gamma$. Consider the group
$\overline{\pi}_{1}(\mathcal{G},T)$ defined as the free product

$\overline{\pi}_{1}(\mathcal{G},T)=*_{v\in
V(\Gamma)}G_{v}*F(\\{s_{e}\\}_{e\in\vec{E}(\Gamma)})$

where $F(\cdot)$ denotes the free group over the given basis. It will be
convenient to consider the following generating set

$S_{\mathcal{G}}=\bigcup_{v\in
V(\Gamma)}G_{v}\cup\\{s_{e}\\}_{e\in\vec{E}(\Gamma)}.$

######  Definition 3.2.

The _fundamental group_ $\pi_{1}(G,T)$ of the graph of groups $\mathcal{G}$
with respect to the subtree $T$ is the quotient of the free product
$\overline{\pi}_{1}(\mathcal{G},T)$ by the normal subgroup generated by the
relations

$R_{\mathcal{G}}=\begin{cases}s_{e}=1&\forall e\in\vec{E}(T),\\\
s_{e}^{-1}i_{e}(g_{e})s_{e}=i_{\bar{e}}(g_{e})&\forall
e\in\vec{E}(\Gamma),g_{e}\in G_{e}.\end{cases}$

######  Remark 3.3.

The fundamental group $\pi_{1}(\mathcal{G},T)$ as well as the group
$\overline{\pi}_{1}(\mathcal{G},T)$ are independent of the choice of maximal
spanning tree $T$ up to isomorphism [4, I.§5].

For the remainder of the paper we will assume that $\mathcal{G}$ is a finite
graph of groups, with finite vertex groups. In particular $S_{\mathcal{G}}$ is
a finite generating set for the group $\overline{\pi}_{1}(\mathcal{G},T)$.

### Outline of the proof and of the paper

Note that the group $\overline{\pi}_{1}(\mathcal{G},T)$ is a free product of
finite groups and of a free group. As such $\overline{\pi}_{1}(\mathcal{G},T)$
is easily seen to be P-stable [1]. In light of Lemma 2.4 and the remarks
following it, our main result Theorem A follows immediately from Theorem 1.2
of the introduction. In other words it suffices to show that the epimorphism
$\overline{\pi}_{1}(\mathcal{G},T)\to\pi_{1}(\mathcal{G},T)$ is P-stable.

Towards this goal consider some $\delta$-almost
$\pi_{1}(\mathcal{G},T)$-action
$\rho:\overline{\pi}_{1}(\mathcal{G},T)\to\operatorname{Sym}(X)$. In
particular $\rho$ restricts to actions of the finite vertex groups $G_{v}$.
For $\rho$ to factorize through the fundamental group $\pi_{1}(\mathcal{G},T)$
it is necessary that for every edge $e\in\vec{E}(\Gamma)$ the two actions
$\rho\circ i_{e}$ and $\rho\circ i_{\bar{e}}$ of the edge group $G_{e}$ are
isomorphic.

It is clear that the isomorphism type of an action of a finite group on a
finite set is characterized by the number of occurrences of each of its
finitely many transitive action types. In §4, we show how to represent this
data using a vector in some canonical $\mathbb{Z}$-module associated to the
group. The restriction maps $\rho|_{G_{v}}\mapsto(\rho\circ i_{e})|_{G_{e}}$
define a $\mathbb{Z}$-linear map $\mathbf{d}_{\mathcal{G}}$ between the
respective $\mathbb{Z}$-modules. The above mentioned condition (that the two
actions $\rho\circ i_{e}$ and $\rho\circ i_{\bar{e}}$ of the edge group
$G_{e}$ are isomorphic) can be described as the kernel of this
$\mathbb{Z}$-linear map $\mathbf{d}_{\mathcal{G}}$. Lastly, the fact that
$\rho$ is a $\delta$-almost action of $\pi_{1}(\mathcal{G},T)$ translates to
having a small image under the map $\mathbf{d}_{\mathcal{G}}$.

In §5, we show that “$\mathbb{Z}$-linear maps are stable” in the following
sense: an exact $\mathbb{Z}$-solution to a linear system of equations and
inequalities can be found nearby a $\delta$-almost solution. This is applied
to the linear map $\mathbf{d}_{\mathcal{G}}$. An exact $\mathbb{Z}$-solution
represents an isomorphism type of an action of
$\overline{\pi}_{1}(\mathcal{G},T)$ on a finite set of the same size as $X$,
which is statistically close to $\rho$ and admits refinements to well-defined
isomorphism types of actions of the edge groups.

Finally, in §6 we show how given a $\delta$-almost action $\rho$, and a nearby
exact $\mathbb{Z}$-solution to the corresponding linear system of equations,
one can find a nearby action $\rho^{\prime}$ factoring via
$\pi_{1}(\mathcal{G},T)$.

We will make repeated use of the finiteness of vertex and edge groups via:

######  Observation 3.4.

Let $G$ be a finite group. If $G$ acts on a finite set $X$ and $Y\subset X$
then there exists a $G$-invariant subset $Y^{\prime}\subseteq Y$ such that
$|X-Y^{\prime}|\leq|G||X-Y|$.

### Notations

We will need to consider inequalities involving quantities depending on the
graph of groups $\mathcal{G}$ in question (such as the number of vertices or
edges, the sizes of the vertex groups $G_{v}$, etc.). To avoid cumbersome
formulas it would be convenient to introduce the following asymptotic
notation.

We write $A\prec_{\bullet}B$ if there exists a constant $c=c(\bullet)$ such
that $A\leq cB$. We omit the subscript when it is clear from the context.

##  4\. Set of actions on finite sets

Let $G$ be any group. Let $\operatorname{Acts}(G)$ denote the set of all
actions of the group $G$ on finite sets considered up to isomorphism.
Similarly let $\operatorname{Trans}(G)$ be the set of transtive actions of $G$
on finite sets considered up to isomorphism.

Every action $\rho:G\to\operatorname{Sym}(X)$ on some finite set $X$ can be
decomposed into a disjoint union of its finitely many orbits
$O_{1},\ldots,O_{n}\subseteq X$. The restriction
$\rho\upharpoonright_{O_{i}}:G\to\operatorname{Sym}(O_{i})$ of $\rho$ to each
orbit $O_{i}$ is transitive for all $i=1,\ldots,n$. The isomorphism class of
the action $\rho$ is determined by counting the isomorphism classes of its
restricted actions $\rho\upharpoonright_{O_{i}}$ with multiplicity.

This observation enables us to identify the set of actions
$\operatorname{Acts}(G)$ with a non-negative cone in the free
$\mathbb{Z}$-module $\Lambda_{G}$ with basis $\operatorname{Trans}(G)$, namely

$\Lambda_{G}=\bigoplus_{\rho\in\operatorname{Trans}(G)}\mathbb{Z}\rho.$

More precisely, given an action $\rho\in\operatorname{Acts}(G)$ we define

$\rho^{\sharp}=\sum_{O\in G\backslash
X}\rho\upharpoonright_{O}\in\Lambda_{G}.$

The correspondence $\rho\mapsto\rho^{\sharp}$ is injective and its image
$\operatorname{Acts}(G)^{\sharp}$ in $\Lambda_{G}$ is the non-negative cone

$\Lambda_{G}^{+}:=\\{(\lambda_{\rho})_{\rho\in\operatorname{Trans}(G)}\>:\>\lambda_{\rho}\geq
0\\}.$

We observe that the correspondence $\rho\to\rho^{\sharp}$ is additive in the
following sense: any two actions $\rho_{1},\rho_{2}\in\operatorname{Acts}(G)$
with $\rho_{i}:G\to\operatorname{Sym}(X_{i})$ for $i\in\\{1,2\\}$ satisfy

$(\rho_{1}\coprod\rho_{2})^{\sharp}=\rho_{1}^{\sharp}+\rho_{2}^{\sharp}$

where $\rho_{1}\coprod\rho_{2}:G\to\operatorname{Sym}(X_{1}\coprod X_{2})$ is
the disjoint union of $\rho_{1}$ and $\rho_{2}$.

We find it convenient to introduce a norm $\|\cdot\|_{G}$ on the
$\mathbb{Z}$-module $\Lambda_{G}$ by

$\|\lambda\|_{G}=\sum_{\begin{subarray}{c}\rho\in\operatorname{Trans}(G)\\\
\rho:G\to\operatorname{Sym}(X_{\rho})\end{subarray}}|\lambda_{\rho}|\cdot|X_{\rho}|\quad\quad\forall\lambda=(\lambda_{\rho})\in\Lambda_{G}.$

This norm is chosen in such a way that every action
$\rho\in\operatorname{Acts}(G)$ with $\rho:G\to\operatorname{Sym}(X)$
satisfies $\|\rho^{\sharp}\|_{G}=|X|$.

#### Pullback on set of actions.

Let $H$ be any group admitting a homomorphism $i:H\to G$. There is a pullback
map $i^{*}$ on the corresponding sets of isomorphism classes of actions on
finite sets is given by

$i^{*}:\operatorname{Acts}(G)\to\operatorname{Acts}(H),\quad
i^{*}\rho=\rho\circ i\quad\forall\rho\in\operatorname{Acts}(G).$

Allowing for a slight abuse of notation, we also let $i^{*}$ denote the
resulting $\mathbb{Z}$-linear map $i^{*}:\Lambda_{G}\to\Lambda_{H}$ defined in
terms of the basis by

$i^{*}(\rho^{\sharp})=(\rho\circ
i)^{\sharp}\quad\rho\in\operatorname{Trans}(G).$

######  Observation 4.1.

Let $\phi:H\to\operatorname{Sym}(X)$ be a group action such that
$\phi^{\sharp}=i^{*}(\lambda)$ for some $\lambda\in\Lambda_{G}$. Then there
exists a group action $\rho:G\to\operatorname{Sym}(X)$ satisfying
$\rho^{\sharp}=\lambda$ and $\rho\circ i=\phi$.

### Set of actions for a graph of groups.

We extend notions introduced above to the setting of graphs of groups. Recall
that

$\mathcal{G}=(\Gamma,\\{G_{v}\\}_{v\in V(\Gamma)},\\{G_{e}\\}_{e\in
E(\Gamma)},\\{i_{e}:G_{e}\to G_{t(e)}\\}_{e\in E(\Gamma)})$

is a finite graph of groups with finite vertex groups. We define the
$\mathbb{Z}$-modules

$\Lambda_{V}=\bigoplus_{v\in
V(\Gamma)}\Lambda_{G_{v}}\quad\text{and}\quad\Lambda_{E}=\bigoplus_{e\in\vec{E}(\Gamma)}\Lambda_{G_{e}}$

and the respective positive cones

$\Lambda_{V}^{+}=\bigoplus_{v\in
V(\Gamma)}\Lambda_{G_{v}}^{+}\quad\text{and}\quad\Lambda_{E}^{+}=\bigoplus_{e\in\vec{E}(\Gamma)}\Lambda_{G_{e}}^{+}.$

It will be convenient to consider the $\mathbb{Z}$-modules with the norms

$\|\cdot\|_{V}=\frac{1}{|V(\Gamma)|}\sum_{v\in
V(\Gamma)}\|\cdot\|_{G_{v}},\quad\|\cdot\|_{E}=\frac{1}{|\vec{E}(\Gamma)|}\sum_{e\in\vec{E}(\Gamma)}\|\cdot\|_{G_{e}}$

where $\|\cdot\|_{G_{v}}$ and $\|\cdot\|_{G_{e}}$ are the norms defined on the
$\mathbb{Z}$-modules $\Lambda_{G_{v}}$ and $\Lambda_{G_{e}}$ as above.

Let $\mathbf{d}_{\mathcal{G}}:\Lambda_{V}\to\Lambda_{E}$ be the
$\mathbb{Z}$-linear map defined on each direct summand $\Lambda_{G_{v}}$ of
the $\mathbb{Z}$-module $\Lambda_{V}$ by

$(\mathbf{d}_{\mathcal{G}})|_{{\Lambda_{G_{v}}}}=\sum_{e:t(e)=v}i_{e}^{*}-\sum_{e:o(e)=v}i^{*}_{\bar{e}}.$

In other words, the image of the vector
$\lambda=(\lambda_{v})_{v}\in\Lambda_{V}$ under the $\mathbb{Z}$-linear map
$\mathbf{d}_{\mathcal{G}}$ in each coordinate $e\in\vec{E}(\Gamma)$ is given
by

$(\mathbf{d}_{\mathcal{G}}(\lambda))_{e}=i^{*}_{e}(\lambda_{t(e)})-i^{*}_{\bar{e}}(\lambda_{o(e)}).$

### Actions of the group $\overline{\pi}_{1}(\mathcal{G},T)$ on finite sets

Let $X$ be a fixed finite set. Given an action
$\rho:\overline{\pi}_{1}(\mathcal{G},T)\to\operatorname{Sym}(X)$ we denote
(abusing our previous notations)

$\rho^{\sharp}\in\Lambda_{V},\quad(\rho^{\sharp})_{v}=(\rho|_{G_{v}})^{\sharp}\quad\forall
v\in V.$

Note that $\|\rho^{\sharp}\|_{V}=|X|$. Moreover the vector $\rho^{\sharp}$
depends only on the restrictions of the action $\rho$ to the vertex groups
$G_{v}$’s but not to the free factor $F(\\{s_{e}\\})$.

######  Proposition 4.2.

If the action $\rho:\overline{\pi}_{1}(\mathcal{G},T)\to\operatorname{Sym}(X)$
factors through $\pi_{1}(\mathcal{G},T)$ then
$\rho^{\sharp}\in\ker\mathbf{d}_{\mathcal{G}}$.

###### Proof.

The $\Lambda_{G_{e}}$-coordinate of the image of the vector $\rho^{\sharp}$
under the $\mathbb{Z}$-linear map $\mathbf{d}_{\mathcal{G}}$ for any fixed
oriented edge $e\in\vec{E}(\Gamma)$ is given by

$(\mathbf{d}_{\mathcal{G}}(\rho^{\sharp}))_{e}=i^{*}_{e}((\rho|_{G_{t(e)}})^{\sharp})-i^{*}_{\bar{e}}((\rho|_{G_{o(e)}})^{\sharp})=(\rho\circ
i_{e})^{\sharp}-(\rho\circ i_{\bar{e}})^{\sharp}\in\Lambda_{G_{e}}.$

The two actions $\rho\circ i_{e}$ and $\rho\circ i_{\bar{e}}$ of the edge
group $G_{e}$ on the finite set $X$ are conjugate via the permutation
$\rho(s_{e})$. Therefore $(\rho\circ i_{e})^{\sharp}=(\rho\circ
i_{\bar{e}})^{\sharp}$ so that the $\Lambda_{G_{e}}$-coordinate in question
vanishes. This concludes the proof as the oriented edge $e\in\vec{E}(\Gamma)$
was arbitrary. ∎

We remark that the converse of Proposition 4.2 is also true, in the sense that
if a vector $\lambda\in\Lambda_{V}^{+}$ is in $\ker\mathbf{d}_{\mathcal{G}}$
then there exists a finite set $Y$ with $\|\lambda\|_{V}=|Y|$ and some action
$\rho:\pi_{1}(\mathcal{G},T)\to\operatorname{Sym}(Y)$ such that
$\rho^{\sharp}=\lambda$. We will need a much sharper version of this fact
proved in Proposition 6.1 below.

######  Proposition 4.3.

Let $\rho:\overline{\pi}_{1}(\mathcal{G},T)\to\operatorname{Sym}(X)$ be an
action. If $\rho$ is a $\delta$-almost $\pi_{1}(\mathcal{G},T)$-action then

$\|\mathbf{d}_{\mathcal{G}}(\rho^{\sharp})\|_{E}\prec_{\mathcal{G}}\delta\|\rho^{\sharp}\|_{V}.$

###### Proof.

Fix an oriented edge $e\in\vec{E}(\Gamma)$ with $t(e)=u$ and $o(e)=v$. For
each group element $g\in G_{e}$ consider the subset

$X_{g}=\\{x\in
X\>:\>\rho(s_{e}^{-1}i_{e}(g)s_{e})(x)=\rho(i_{\bar{e}}(g))(x)\\}.$

The assumption that $\rho$ is a $\delta$-almost
$\pi_{1}(\mathcal{G},T)$-action implies that $|X_{g}|\geq(1-\delta)|X|$.
Denote $X_{e}=\bigcap_{g\in G_{e}}X_{g}$ so that
$|X_{e}|\geq(1-\delta|G_{e}|)|X|$ and

$\rho(s_{e}^{-1}i_{e}(g)s_{e})(x)=\rho(i_{\bar{e}}(g))(x)\quad\forall x\in
X_{e},g\in G_{e}.$

According to Observation 3.4 there is some $i_{\bar{e}}(G_{e})$-invariant
subset $Y_{e}\subset X_{e}$ satisfying $|Y_{e}|\geq(1-\delta|G_{e}|^{2})|X|$.
Note that the set $\rho(s_{e})(Y_{e})$ is $i_{e}(G_{e})$-invariant. Moreover,
the two actions $(\rho\circ i_{e})\upharpoonright_{\rho(s_{e})(Y_{e})}$ and
$(\rho\circ i_{\bar{e}})\upharpoonright_{Y_{e}}$ of the group $G_{e}$ are
isomorphic (via conjugation by the permutation $\rho(s_{e})$).

To simplify our notations let $\rho_{u}=\rho|_{G_{u}}$ and
$\rho_{v}=\rho|_{G_{v}}$ for the remainder of this proof. The previous
paragraph implies that

$((\rho_{u}\circ
i_{e})\upharpoonright_{\rho(s_{e})(Y_{e})})^{\sharp}=((\rho_{v}\circ
i_{\bar{e}})\upharpoonright_{Y_{e}})^{\sharp}.$

The norm of the coordinate of the vector
$\mathbf{d}_{\mathcal{G}}(\rho^{\sharp})$ corresponding to the edge $e$ is
given by

$\displaystyle\begin{split}\|(\mathbf{d}_{\mathcal{G}}(\rho^{\sharp})_{e}\|_{G_{e}}&=\|i_{e}^{*}(\rho_{u}^{\sharp})-i_{\bar{e}}^{*}(\rho_{v}^{\sharp})\|_{G_{e}}\\\
&=\|((\rho_{u}\circ
i_{e})\upharpoonright_{\rho(s_{e})(Y_{e})})^{\sharp}+((\rho_{u}\circ
i_{e})\upharpoonright_{X\setminus\rho(s_{e})(Y_{e})})^{\sharp}\\\
&\quad\quad\quad\quad-((\rho_{v}\circ
i_{\bar{e}})\upharpoonright_{Y_{e}})^{\sharp}-((\rho_{v}\circ
i_{\bar{e}})\upharpoonright_{X\setminus Y_{e}})^{\sharp}\|_{G_{e}}\\\
&\leq\|i_{e}^{*}(\rho_{u}\upharpoonright_{X-\rho(s_{e})(Y_{e})})^{\sharp})\|_{G_{e}}+\|i^{*}_{\bar{e}}(\rho_{v}\upharpoonright_{X-Y_{e}})^{\sharp})\|_{G_{e}}\\\
&=|X-s_{e}(Y_{e})|+|X-Y_{e}|\leq 2\delta|G_{e}|^{2}|X|.\end{split}$

Averaging the above estimate over all oriented edges $e\in\vec{E}(\Gamma)$
gives

$\|\mathbf{d}_{\mathcal{G}}(\rho^{\sharp})\|_{E}\leq
c\delta|X|=c\delta\|\rho^{\sharp}\|_{V}$

with respect to the constant $c=2\max_{e\in\vec{E}(\Gamma)}|G_{e}|^{2}$. This
constant depends only on the graph of groups $\mathcal{G}$. ∎

##  5\. Linear algebra and cones

This section is, formally speaking, independent of the rest of the paper. Its
goal is to show that “$\mathbb{Z}$-linear maps are stable”, in the sense that
an approximate solution to a system of linear equations and inequalities must
be close to an exact $\mathbb{Z}$-solution (see Lemma 5.3 below for a precise
statement).

Let $\Lambda_{1}$ and $\Lambda_{2}$ be a pair of finitely generated free
$\mathbb{Z}$-modules. Let $\mathbf{d}:\Lambda_{1}\to\Lambda_{2}$ be a
$\mathbb{Z}$-linear map.

Let $V_{i}=\Lambda_{i}\otimes\mathbb{R}$ be the $\mathbb{R}$-vector spaces
obtained by extending scalars from $\Lambda_{i}$ and $\|\cdot\|_{i}$ be norms
on $V_{i}$ for $i=1,2$. By abuse of notation, we continue using
$\mathbf{d}:V_{1}\to V_{2}$ to denote the $\mathbb{R}$-linear extension of
$\mathbf{d}:\Lambda_{1}\to\Lambda_{2}$. We will make essential use of the fact
that $\mathbf{d}:V_{1}\to V_{2}$ is defined over $\mathbb{Q}$. Denote
$K=\ker\mathbf{d}$ so that $K$ is a $\mathbb{Q}$-subspace of the
$\mathbb{R}$-vector space $V_{1}$.

Assume that $C\subset V_{1}$ is a closed positive cone defined by finitely
many inequalities over $\mathbb{Q}$ and satisfying
$\operatorname{Span}(C)=V_{1}$. Denote $\Lambda_{1}^{+}=C\cap\Lambda_{1}$ so
that the subset $\Lambda_{1}^{+}$ is closed under addition.

######  Lemma 5.1.

For all $v\in C$ there exists $v^{\prime\prime}\in C\cap K$ such that
$\|v-v^{\prime\prime}\|_{1}\prec\|\mathbf{d}v\|_{2}$.

We point out that the intersection $C\cap K$ is non-empty for it contains the
zero vector $0\in V_{1}$. Lemma 5.1 does not require the assumption that the
subspace $K$, the linear map $\mathbf{d}$ and the positive cone $C$ are all
defined over $\mathbb{Q}$. We do need however the assumption that $C$ is
defined by finitely many inequalities.

###### Proof of Lemma 5.1.

We argue by induction on the $\mathbb{R}$-dimension of $V_{1}$. The base case
where $\dim_{\mathbb{R}}V_{1}=0$ is trivial.

Consider the $\mathbb{R}$-subspace $\mathbf{d}(V_{1})$ of the
$\mathbb{R}$-vector space equipped with two different norms, namely the
restriction of norm $\|\cdot\|_{2}$ coming from $V_{2}$, and the quotient norm
$\|\cdot\|^{\prime}_{1}$ defined by

$\|\mathbf{d}v\|_{1}^{\prime}:=\inf_{w\in K}\|v-w\|_{1}\quad\forall v\in
V_{1}.$

Since any two norms on a finite dimensional $\mathbb{R}$-vector space are bi-
Lipschitz equivalent, there is some constant $c>0$ such that
$\|\mathbf{d}v\|_{1}^{\prime}\leq c\|\mathbf{d}v\|_{2}$ for all $v\in V_{1}$.

Fix some vector $v\in C$. The infimum appearing in the definition of the
quotient norm $\|\mathbf{d}v\|_{1}^{\prime}$ is attained at some vector $w\in
K$, hence

$\|\mathbf{d}v\|^{\prime}_{1}=\|v-w\|_{1}\leq c\|\mathbf{d}v\|_{2}.$

If $w\in C$, then we are done by choosing $v^{\prime}=w\in C\cap K$.
Otherwise, let $u$ be the closest point to $w$ along the closed segment
$[v,w]\subseteq V_{1}$ and belonging to the closed cone $C$. Then clearly

$\|v-u\|_{1}\leq\|v-w\|_{1}=\|\mathbf{d}v\|^{\prime}_{1}\leq
c\|\mathbf{d}v\|_{2}\quad\text{and}\quad\|\mathbf{d}u\|_{2}\leq\|\mathbf{d}v\|_{2}.$

Since the point $u$ lies on the boundary of the positive cone $C$, it belongs
to some proper face $D\subset C$ spanning a $\mathbb{Q}$-subspace
$U_{1}=\operatorname{Span}_{\mathbb{R}}(D)\subset V_{1}$ of strictly lower
dimension. By the induction hypothesis there exists some constant $c_{D}$,
such that for $u\in D$ there exists a point $v^{\prime}\in D\cap K$ with
$\|u-v^{\prime}\|_{1}\leq c_{D}\|\mathbf{d}u\|_{2}$. Hence,

$\|v-v^{\prime}\|_{1}\leq\|v-u\|_{1}+\|u-v^{\prime}\|_{1}\leq(c+c_{D})\|\mathbf{d}v\|_{2}\leq
c_{1}\|\mathbf{d}v\|_{2}$

where $c_{1}=c+\max_{D\subset C}c_{D}$ and the maximum is taken over the
finite set of proper faces of the positive cone $C$. ∎

Recall that $K$ denotes the kernel of the linear map $\mathbf{d}$ regarded as
a $\mathbb{Q}$-subspace of the $\mathbb{R}$-vector space $V_{1}$.

######  Lemma 5.2.

There are constants $c_{1},A>0$ such that if $v\in C$ then there is a vector
$\lambda\in\Lambda^{+}\cap K$ satisfying $\|v-\lambda\|_{1}\leq
c_{1}\|\mathbf{d}v\|_{2}+A$.

###### Proof.

Let $v\in C$ be any vector. By Lemma 5.1 there exists a vector
$v^{\prime\prime}\in C\cap K$ such that $\|v-v^{\prime\prime}\|_{1}\leq
c_{1}\|\mathbf{d}v\|_{2}$ for some constant $c_{1}>0$ independent of $v$.

Note that $C\cap K$ is a positive cone defined over $\mathbb{Q}$. Let
$U=\operatorname{Span}_{\mathbb{R}}(C\cap K)\subseteq V_{1}$ so that $C\cap U$
is a closed cone with a non-empty interior in the vector subspace $U$. Denote
$B_{A}=\\{w\in V_{1}\>:\>\|w\|_{1}\leq A\\}$. Therefore $C\cap U\cap B_{A}$
contains in its interior a ball in $U$ of an arbitrary large radius, provided
the radius $A>0$ is sufficiently large. Since $\Lambda\cap U$ is a lattice in
the $\mathbb{R}$-vector space $U$, the set $C\cap U\cap B_{A}$ surjects onto
$U/(U\cap\Lambda)$ for all $A>0$ sufficiently large. Fix any sufficiently
large such $A>0$.

Since $v^{\prime\prime}\in C\cap K$ the translated set $v^{\prime\prime}+C\cap
U\cap B_{A}\subset C\cap K$ also surjects onto $U/(U\cap\Lambda)$. In
particular this set admits a point $\lambda\in\Lambda\cap C\cap
K=\Lambda^{+}\cap K$. We conclude that
$\|v-\lambda\|_{1}\leq\|v-v^{\prime\prime}\|_{1}+\|v^{\prime\prime}-\lambda\|_{1}\leq
c_{1}\|\mathbf{d}v\|_{2}+A$ as required. ∎

######  Lemma 5.3.

For any vector $\lambda\in\Lambda^{+}$ there is another vector
$\lambda^{\prime}\in\Lambda^{+}\cap K$ satisfying
$\|\lambda-\lambda^{\prime}\|_{1}\prec\|\mathbf{d}\lambda\|_{2}$ and
$\|\lambda^{\prime}\|_{1}\leq\|\lambda\|_{1}$.

###### Proof.

Let the vector $\lambda\in\Lambda^{+}$ be fixed. If $\lambda\in
K=\ker\mathbf{d}$ then there is nothing to prove, for we may simply take
$\lambda^{\prime}=\lambda\in\Lambda^{+}\cap K$. Assume therefore that
$\lambda\notin K$.

Since the linear map $\mathbf{d}$ is defined over $\mathbb{Q}$ there is a
constant $M>0$ such that $\|\mathbf{d}\lambda\|_{2}\geq M$ for every vector
$\lambda\in\Lambda\setminus K$. Denote

$\theta=\frac{c_{1}\|\mathbf{d}\lambda\|_{2}+A}{\|\lambda\|_{1}}$

where the constants $c_{1}$ and $A$ are as in Lemma 5.2.

If $\theta\geq 1$ then we may take $\lambda^{\prime}=0$. This vector
$\lambda^{\prime}$ satisfies $0=\|\lambda^{\prime}\|_{1}\leq\|\lambda\|_{1}$
and

$\|\lambda-\lambda^{\prime}\|_{1}\leq\theta\|\lambda\|_{2}=c_{1}\|\mathbf{d}\lambda\|_{2}+A\leq(c_{1}+\frac{A}{M})\|\mathbf{d}\lambda\|_{2}$

as desired (the constants $c_{1},A$ and $M$ are all independent of $\lambda$).

Finally assume that $0<\theta<1$. Apply Lemma 5.2 to the vector
$v=(1-\theta)\lambda$. This gives a new vector
$\lambda^{\prime}\in\Lambda^{+}\cap K$ with

$\|v-\lambda^{\prime}\|_{1}\leq c_{1}\|\mathbf{d}v\|_{2}+A\leq
c_{1}\|\mathbf{d}\lambda\|_{2}+A.$

Therefore

$\|\lambda^{\prime}\|_{1}\leq\|v\|_{1}+\|v-\lambda^{\prime}\|_{1}\leq(1-\theta)\|\lambda\|_{1}+c_{1}\|\mathbf{d}\lambda\|_{2}+A=\|\lambda\|_{1}.$

This verifies the second condition. As for the first condition, we have

$\|\lambda-\lambda^{\prime}\|_{1}\leq\|\lambda-v\|_{1}+\|v-\lambda^{\prime}\|_{1}\leq\theta\|\lambda\|_{1}+c_{1}\|\mathbf{d}\lambda\|_{2}+A\leq
2c_{1}\|\mathbf{d}\lambda\|_{2}+2A\leq 2(c_{1}+A/M)\|\mathbf{d}\lambda\|_{2}.$

This concludes the proof, noting as above that the constants $c_{1},A$ and $M$
are all independent of the vector $\lambda$. ∎

##  6\. From linear algebra back to actions

We show that any $\delta$-almost $\pi_{1}(\mathcal{G},T)$-action $\rho$ whose
isomorphism type $\rho^{\sharp}$ is compatible with some
$\pi_{1}(\mathcal{G},T)$-action, can be corrected to such an action. More
precisely, we establish the following result, using without further mention
all the notations introduced in §2, §3 and §4.

######  Proposition 6.1.

Let $\rho:\overline{\pi}_{1}(\mathcal{G},T)\to\operatorname{Sym}(X)$ be a
$\delta$-almost $\pi_{1}(\mathcal{G},T)$-action with $\lambda=\rho^{\sharp}$.
Let $\lambda^{\prime}\in\Lambda_{V}^{+}$ be any vector with
$\|\lambda^{\prime}\|_{V}=\|\lambda\|_{V}$. If

  1. (a)

$\lambda^{\prime}\in\ker\mathbf{d}_{\mathcal{G}}$ and

  2. (b)

$\|\lambda-\lambda^{\prime}\|_{V}\leq\delta\|\lambda\|_{V}$

then there is a group action
$\rho^{\prime}:\pi_{1}(\mathcal{G},T)\to\operatorname{Sym}(X)$ satisfying

  1. (i)

$\lambda^{\prime}=(\rho^{\prime})^{\sharp}$ and

  2. (ii)

$d_{X,S_{\mathcal{G}}}(\rho,\rho^{\prime})\prec_{\mathcal{G}}\delta$.

We precede the proof of Proposition 6.1 with an analogous statement in the
simpler context of a single group homomorphism.

######  Lemma 6.2.

Let $i:H\to G$ be a homomorphism of finite groups. Let
$\phi:H\to\operatorname{Sym}(X)$ and $\rho:G\to\operatorname{Sym}(X)$ be a
pair of group actions. Denote $\lambda=\rho^{\sharp}$. If
$\lambda^{\prime}\in\Lambda_{G}^{+}$ and $\delta>0$ are such that

  1. (a)

$d_{X,H}(\rho\circ i,\phi)\leq\delta$,

  2. (b)

$i^{*}(\lambda^{\prime})=\phi^{\sharp}$, and

  3. (c)

$\|\lambda-\lambda^{\prime}\|_{G}\leq\delta\|\lambda\|_{G}$

then there exists a group action $\rho^{\prime}:G\to\operatorname{Sym}(X)$
satisfying

  1. (i)

$\rho^{\prime}\circ i=\phi$,

  2. (ii)

$\lambda^{\prime}=(\rho^{\prime})^{\sharp}$, and

  3. (iii)

$d_{X,G}(\rho,\rho^{\prime})\prec_{G,H}\delta$.

Note that the “small” action $\phi$ of the group $H$ is not being changed,
rather the “large” action $\rho$ is being replaced with a new action
$\rho^{\prime}$ compatible with $\phi$.

###### Proof of Lemma 6.2.

We combine Assumption (a) and Observation 3.4 applied with respect to the
finite group $H$ in order to find a $\phi(H)$-invariant subset $X_{0}\subset
X$ satisfying $\phi\upharpoonright_{X_{0}}=(\rho\circ
i)\upharpoonright_{X_{0}}$ and $|X_{0}|\geq(1-\delta|H|)|X|$. By applying
Observation 3.4 a second time with respect to the finite group $G$, we find a
$\rho(G)$-invariant subset $X_{1}\subset X_{0}$ satisfying
$|X_{1}|\geq(1-\delta|H||G|)|X|$.

Consider the vector
$\lambda_{1}=(\rho\upharpoonright_{X_{1}})^{\sharp}\in\Lambda_{G}^{+}$. Let
$\mu_{1}\in\Lambda_{G}^{+}$ be the component-wise minimum of the two vectors
$\lambda^{\prime}$ and $\lambda_{1}$, i.e $\mu_{1}$ is the vector given by

$(\mu_{1})_{\chi}=\min\\{(\lambda^{\prime})_{\chi},(\lambda_{1})_{\chi}\\}\quad\forall\chi\in\operatorname{Trans}(G).$

The previous paragraph implies that
$\|\lambda-\lambda_{1}\|_{G}\leq\delta|H||G||X|$. Therefore Assumption (c)
gives

$\displaystyle\max\\{\|\lambda^{\prime}-\mu_{1}\|_{G},\|\lambda_{1}-\mu_{1}\|_{G}\\}$
$\displaystyle\leq\|\lambda^{\prime}-\lambda_{1}\|_{G}\leq\|\lambda^{\prime}-\lambda\|_{G}+\|\lambda-\lambda_{1}\|_{G}$
$\displaystyle\leq\delta|X|+\delta|H||G||X|=\delta(1+|H||G|)|X|.$

Let $Y_{1}\subset X_{1}$ be any $\rho(G)$-invariant subset satisfying
$\mu_{1}=(\rho\upharpoonright_{Y_{1}})^{\sharp}$. Write
$\mu_{2}=\lambda^{\prime}-\mu_{1}\in\Lambda_{G}^{+}$ and $Y_{2}=X\setminus
Y_{1}$ so that $\lambda^{\prime}=\mu_{1}+\mu_{2}$ and $X=Y_{1}\coprod Y_{2}$.
It will not be the case in general that $(\rho\upharpoonright Y_{2})^{\sharp}$
coincides with $\mu_{2}$. However $|Y_{2}|=\|\mu_{2}\|_{G}$ and in particular
the size of the subset $Y_{2}$ is bounded by

$|Y_{2}|=\|\mu_{2}\|_{G}\leq\delta(1+|H||G|)|X|.$

We define a new action $\rho^{\prime}:G\to\operatorname{Sym}(X)$ as follows.
To begin with, the restriction of $\rho^{\prime}$ to the $\rho(G)$-invariant
subset $Y_{1}$ coincides with $\rho$, namely
$\rho^{\prime}\upharpoonright_{Y_{1}}=\rho\upharpoonright_{Y_{1}}$. As
$i^{*}(\lambda^{\prime})=\phi^{\sharp}$ by Assumption (b) and as
$i^{*}(\mu_{1})=(\phi\upharpoonright_{Y_{1}})^{\sharp}$ by the choice of the
subset $Y_{1}$ we have
$i^{*}(\mu_{2})=(\phi\upharpoonright_{Y_{2}})^{\sharp}$. It remains to define
the action $\rho^{\prime}$ on the $\rho(G)$-invariant complement
$Y_{2}=X\setminus Y_{1}$. Taking into account Observation 4.1 we let
$\rho^{\prime}\upharpoonright_{Y_{2}}$ be an arbitrary action satisfying
$(\rho^{\prime}\circ\iota)\upharpoonright_{Y_{2}}=\phi\upharpoonright_{Y_{2}}$
and $(\rho^{\prime}\upharpoonright_{Y_{2}})^{\sharp}=\mu_{2}$. This completes
the definition of the new action $\rho^{\prime}$.

Statements (i) and (ii) of the Lemma hold true since $\rho^{\prime}\circ
i=\phi$ and

$\rho^{\prime\sharp}=(\rho^{\prime}\upharpoonright_{Y_{1}})^{\sharp}+(\rho^{\prime}\upharpoonright_{Y_{2}})^{\sharp}=\mu_{1}+\mu_{2}=\lambda^{\prime}.$

To verify Statement (iii) we compute

$\displaystyle\begin{split}d_{X}(\rho(g),\rho^{\prime}(g))&=\frac{|Y_{1}|}{|X|}d_{Y_{1}}(\rho(g)\upharpoonright_{Y_{1}},\rho^{\prime}(g)\upharpoonright_{Y_{1}})+\frac{|Y_{2}|}{|X|}d_{Y_{2}}(\rho(g)\upharpoonright_{Y_{2}},\rho^{\prime}(g)\upharpoonright_{Y_{2}})\\\
&\leq\frac{|Y_{2}|}{|X|}\leq(1+|H||G|)\delta\leq 2|H||G|\delta\end{split}$

for all elements $g\in G$. Therefore $d_{X,G}(\rho,\rho^{\prime})\leq
2|H||G|^{2}\delta$ as required. ∎

We are now in a position to prove the main result of §6.

###### Proof of Proposition 6.1.

We define the new action
$\rho^{\prime}:\pi_{1}(\mathcal{G},T)\to\operatorname{Sym}(X)$ of the
fundamental group $\pi_{1}(\mathcal{G},T)$ by specifying it on the finite
generating set $S_{\mathcal{G}}$. This is done in two steps: first we define
$\rho^{\prime}$ on the vertex groups $G_{v}$ and then on the generators of the
form $s_{e}$.

#### Step 1. Defining $\rho^{\prime}$ on $G_{v}$ for all $v\in V(\Gamma)$.

Fix an arbitrary base vertex $v_{0}$ in $V(\Gamma)$. We define the vertex
group actions $\rho^{\prime}|_{G_{v}}$ by induction on the distance in the
spanning tree $T$ of the vertex $v$ from the base vertex $v_{0}$ such that:

  1. (1)

$(\rho^{\prime}|_{G_{v}})^{\sharp}=\lambda^{\prime}_{v}$,

  2. (2)

$d_{X,G_{v}}(\rho|_{G_{v}},\rho^{\prime}|_{G_{v}})\prec\delta$ and

  3. (3)

$\rho|_{G_{t(e)}}\circ i_{e}=\rho|_{G_{o(e)}}\circ i_{\bar{e}}$ for the unique
edge $e\in E(T)$ such that $t(e)=v$ and the unique path in the tree $T$ from
$v_{0}$ to $v$ passes through $o(e)$.

_Base of the induction._ We apply Lemma 6.2 with the following data: the group
$G$ is the vertex group $G_{v_{0}}$, the group $H$ and the homomorphism
$i:H\to G$ are trivial and the vector $\lambda^{\prime}\in\Lambda_{G}^{+}$ is
the coordinate $\lambda^{\prime}_{v_{0}}\in\Lambda_{G_{v_{0}}}^{+}$. This
results in a new action $\rho^{\prime}|_{G_{v_{0}}}$ of the base vertex group
$G_{v_{0}}$ satisfying
$d_{X,G_{v_{0}}}(\rho|_{G_{v_{0}}},\rho^{\prime}|_{G_{v_{0}}})\prec\delta$ and
$(\rho^{\prime}|_{G_{v_{0}}})^{\sharp}=\lambda^{\prime}_{v_{0}}$.

_Induction step._ Let $v\in V(\Gamma)$ be a vertex of distance
$n\in\mathbb{N}$ from the base vertex $v_{0}$ in the tree $T$ and $e\in E(T)$
be the unique edge such that $t(e)=v$ and $o(e)$ is distance $n-1$ from the
base vertex $v_{0}$. Denote $u=o(e)$. By the induction hypothesis the vertex
group action $\rho^{\prime}|_{G_{u}}$ has been defined and satisfies
$(\rho^{\prime}|_{G_{u}})^{\sharp}=\lambda^{\prime}_{u}$.

We apply Lemma 6.2 with the following data: the group $G$ is the vertex group
$G_{v}$, the group $H$ is the edge group $G_{e}$, the homomorphism $i:H\to G$
is the map $i_{e}$, the action $\phi$ of the group $H$ is
$(\rho^{\prime}|_{G_{u}})\circ i_{\bar{e}}$, the action $\rho$ of the group
$G$ is $\rho|_{G_{v}}$ and lastly the vector
$\lambda^{\prime}\in\Lambda_{G}^{+}$ is the coordinate
$\lambda^{\prime}_{v}\in\Lambda_{G_{v}}^{+}$.

We proceed to verify the assumptions of Lemma 6.2. The induction hypothesis
combined with the assumption that
$\lambda^{\prime}\in\ker\mathbf{d}_{\mathcal{G}}$ imply

$i^{*}(\lambda^{\prime}_{v})=i_{e}^{*}(\lambda^{\prime}_{v})=i^{*}_{\bar{e}}(\lambda^{\prime}_{u})=i^{*}_{\bar{e}}((\rho^{\prime}|_{G_{u}})^{\sharp})=(\rho^{\prime}\circ
i_{\bar{e}})^{\sharp}=\phi^{\sharp}.$

By the triangle inequality the two actions $\rho\circ i$ and $\phi$ of the
edge group $G_{e}$ satisfy

$\displaystyle\begin{split}d_{X,G_{e}}(\rho\circ
i,\phi)&=d_{X,G_{e}}(\rho\circ i_{e},\rho^{\prime}\circ i_{\bar{e}})\\\ &\leq
d_{X,G_{e}}(\rho\circ i_{e},\rho(s_{e})\cdot(\rho\circ i_{e}))\\\
&\quad+d_{X,G_{e}}(\rho(s_{e})\cdot(\rho\circ
i_{e}),\rho(s_{e})\cdot(\rho\circ i_{e})\cdot\rho(s_{e})^{-1})\\\
&\quad+d_{X,G_{e}}(\rho(s_{e})\cdot(\rho\circ
i_{e})\cdot\rho(s_{e})^{-1},\rho\circ i_{\bar{e}})\\\
&\quad+d_{X,G_{e}}(\rho\circ i_{\bar{e}},\rho^{\prime}\circ
i_{\bar{e}}).\end{split}$

The normalized Hamming metric $d_{X}$ is bi-invariant so that the first and
second summands are both less than
$d_{X,G_{e}}(\rho(s_{e}),\operatorname{id})<\delta$. The third summand is also
less than $\delta$ as $\rho$ is a $\delta$-almost
$\pi_{1}(\mathcal{G},T)$-action and taking into account the corresponding
relation in $R_{\mathcal{G}}$. Lastly, the fourth summand satisfies
$d_{X,G_{e}}(\rho\circ i_{\bar{e}},\rho^{\prime}\circ i_{\bar{e}})\prec\delta$
by the induction hypothesis. We conclude that

$\displaystyle d_{X,G_{e}}(\rho\circ i,\phi)\prec\delta.$

Having verified all of the assumptions for Lemma 6.2, we get a new action
$\rho^{\prime}|_{G_{v}}$ of the vertex group $G_{v}$ such that
$\rho^{\prime}\circ i_{e}=\rho^{\prime}\circ i_{\bar{e}}$ on the edge group
$G_{e}$, $d_{X,G_{v}}(\rho|_{G_{v}},\rho^{\prime}|_{G_{v}})\prec\delta$ and
$(\rho^{\prime}|_{G_{v}})^{\sharp}=\lambda^{\prime}_{v}$. This completes the
step of the induction.

_Proceed with the induction until the new action $\rho^{\prime}$ is defined on
all vertex groups._

#### Step 2. Defining $\rho^{\prime}$ on the generators $s_{e}$ for all
$e\in\vec{E}(\Gamma)$

Let $e\in\vec{E}(\Gamma)$ be a directed edge with $o(e)=u$ and $t(e)=v$.

_Assume that $e\in E(T)$._ Define $\rho^{\prime}(s_{e})=\operatorname{id}$.
Recall that the action $\rho^{\prime}$ of the edge group $G_{e}$ satisfies
$\rho^{\prime}\circ i_{e}=\rho^{\prime}\circ i_{\bar{e}}$ by Step 1. Therefore

$\rho^{\prime}(i_{e}(g_{e})s_{e})(x)=\rho^{\prime}(s_{e}i_{\bar{e}}(g_{e}))(x)$

for all points $x\in X$ and all elements $g_{e}\in G_{e}$. Moreover, since
$\rho$ is a $\delta$-almost $\pi_{1}(\mathcal{G},T)$-action we have
$d_{X}(\rho(s_{e}),\rho^{\prime}(s_{e}))\leq\delta$.

_Assume that $e\in E(\Gamma)\setminus E(T)$._ According to Observation 3.4
there exists a $\rho^{\prime}|_{i_{e}(G_{e})}$-invariant subset
$X_{e}\subseteq X$, such that $|X-X_{e}|\prec\delta|X|$ and the following
conditions are satisfied for all points $x\in X_{e}$ and all elements
$g_{e}\in G_{e}$

$\displaystyle\begin{split}\rho(i_{e}(g_{e})s_{e})(x)&=\rho(s_{e}i_{\bar{e}}(g_{e}))(x),\\\
\rho(i_{\bar{e}}(g_{e}))(x)&=\rho^{\prime}(i_{\bar{e}}(g_{e}))(x),\\\
\rho(i_{e}(g_{e}))(\rho(s_{e})x)&=\rho^{\prime}(i_{e}(g_{e}))(\rho(s_{e})x).\end{split}$

Define the restriction $\rho^{\prime}(s_{e})\upharpoonright|_{X_{e}}$ of the
new action to be the same as $\rho(s_{e})\upharpoonright_{X_{e}}$. The above
conditions imply that the permutation $\rho^{\prime}(s_{e})$ satisfies

$\rho^{\prime}(i_{e}(g_{e})s_{e})(x)=\rho^{\prime}(s_{e}i_{\bar{e}}(g_{e}))(x)$

for all points $x\in X_{e}$ and all edge group elements $g_{e}\in G_{e}$.

It remains to define the permutation $\rho^{\prime}(s_{e})$ on the complement
$X-X_{e}$ and verify the above relation for all points $x\in X-X_{e}$. The two
actions $\rho^{\prime}\circ i_{e}$ and $\rho^{\prime}\circ i_{\bar{e}}$ of the
edge group $G$ are conjugate as
$\lambda^{\prime}\in\ker\mathbf{d}_{\mathcal{G}}$ and
$\rho^{\prime\sharp}=\lambda^{\prime}$. Since the permutation $\rho(s_{e})$
conjugates $(\rho^{\prime}\circ i_{e})\upharpoonright_{X_{e}}$ to
$(\rho^{\prime}\circ i_{\bar{e}})\upharpoonright_{\rho(s_{e})X_{e}}$, we know
that their complements must be conjugate as well. Define the restriction
$\rho^{\prime}(s_{e})\upharpoonright_{X\setminus X_{e}}$ to be an arbitrary
bijection from $X\setminus X_{e}$ to $X\setminus\rho(s_{e})X_{e}$ implementing
this isomorphism of actions. Note that
$d_{X}(\rho(s_{e}),\rho^{\prime}(s_{e}))\prec\delta$. This concludes the
definition of the permutation $\rho^{\prime}(s_{e})$ for this particular
oriented edge $e$.

#### A bound on $d_{X,S_{\mathcal{G}}}(\rho,\rho^{\prime})$.

The $\pi_{1}(\mathcal{G},T)$-action $\rho^{\prime}$ has been constructed in
Steps 1 and 2. It was specified in terms of the finite generating set
$S_{\mathcal{G}}$ while making sure that the defining relations
$R_{\mathcal{G}}$ of the fundamental group $\pi_{1}(\mathcal{G},T)$ hold true.
It follows from the construction that $\rho^{\prime\sharp}=\lambda^{\prime}$.
To conclude the proof it remains to bound the normalized Hamming distance
$d_{X,S_{\mathcal{G}}}(\rho,\rho^{\prime})$. Namely

$\displaystyle\begin{split}d_{X,S_{\mathcal{G}}}(\rho,\rho^{\prime})&=\sum_{\sigma\in
S_{\mathcal{G}}}d_{X}(\rho(\sigma),\rho^{\prime}(\sigma))\\\ &=\sum_{v\in
V(G)}\sum_{g\in G_{v}}d_{X}(\rho(g),\rho^{\prime}(g))\\\
&\quad\quad+\sum_{e\in E(T)}d_{X}(\rho(s_{e}),\rho^{\prime}(s_{e}))\\\
&\quad\quad+\sum_{e\in E(\Gamma)\setminus
E(T)}d_{X}(\rho(s_{e}),\rho^{\prime}(s_{e}))\\\ &\prec\delta\end{split}$

as required. ∎

##  7\. Proof of the main theorem

We are ready to show that the epimorphism
$\overline{\pi}_{1}(\mathcal{G},T)\to\pi_{1}(\mathcal{G},T)$ is P-stable.

###### Proof of Theorem 1.2.

Let $X$ be a finite set admitting a $\delta$-almost
$\pi_{1}(\mathcal{G},T)$-action
$\rho:\overline{\pi}_{1}(\mathcal{G},T)\to\operatorname{Sym}(X)$. Denote
$\lambda=\rho^{\sharp}$. We know by Proposition 4.3 that

(7.1)
$\|\mathbf{d}_{\mathcal{G}}(\lambda)\|_{E}\prec_{\mathcal{G}}\delta\|\lambda\|_{V}$

Lemma 5.3 allows us to find a vector
$\lambda^{\prime\prime}\in\Lambda_{V}^{+}\cap\ker\mathbf{d}_{\mathcal{G}}$
such that

$\|\lambda^{\prime\prime}-\lambda\|_{V}\prec\delta\|\lambda\|_{V}\quad\text{and}\quad\|\lambda^{\prime\prime}\|_{V}\leq\|\lambda\|_{V}.$

We will make an auxiliary use of the action of the fundamental group
$\pi_{1}(\mathcal{G},T)$ on a singleton. Denote this action by $s$. By
Proposition 4.2 we know that $s^{\sharp}\in\ker\mathbf{d}_{\mathcal{G}}$.
Moreover $\|s^{\sharp}\|_{V}=1$. Let

$\lambda^{\prime}=\lambda^{\prime\prime}+(\|\lambda\|_{V}-\|\lambda^{\prime\prime}\|_{V})s^{\sharp}.$

It is clear that $\lambda^{\prime}\in\ker\mathbf{d}_{\mathcal{G}}$,
$\|\lambda^{\prime}\|_{V}=\|\lambda\|_{V}=\|\rho^{\sharp}\|_{V}=|X|$ and

$\|\lambda^{\prime}-\lambda\|_{V}\leq\|\lambda-\lambda^{\prime\prime}\|_{V}+\|\lambda^{\prime}-\lambda^{\prime\prime}\|_{V}\prec\delta|X|.$

To conclude the proof we apply Proposition 6.1 and obtain the desired action
$\rho^{\prime}:\pi_{1}(\mathcal{G},T)\to\operatorname{Sym}(X)$ satisfying
$(\rho^{\prime})^{\sharp}=\lambda^{\prime}$ and
$d_{X,S_{\mathcal{G}}}(\rho,\rho^{\prime})\prec\delta$. ∎

######  Remark 7.1.

It follows from the proof that one can take $\delta\prec\epsilon$ for the
P-stability of $\pi_{1}(\mathcal{G},T)$.

The derivation of Theorem A from the above Theorem 1.2 is immediate and has
been discussed in §3.

##  8\. Graph automorphisms of finite order

Fix some $d\in\mathbb{N}$ and let $F_{d}=F(s_{1},\ldots,s_{d})$ be the free
group of rank $d$.

A finite Schreier graph $A$ of the group $F_{d}$ is a finite directed graph
edge-labelled by the generators $s_{1},\ldots,s_{d}$ such that every vertex
has exactly one incoming and one outgoing edge of each label. We indicate the
labelling of the directed edges $E(A)$ using a function
$c=c_{A}:E(A)\to\\{s_{1},\ldots,s_{d}\\}$.

A _weak $\delta$-almost-automorphism_ $\alpha$ of the Schreier graph $A$ is a
pair of bijections $\alpha:V(A)\to V(A)$ and $\alpha:E(A)\to E(A)$ (we use the
same letter for both by abuse of notation) such that for all directed edges
$e\in\vec{E}(A)$ except for a subset of size $\delta|E(A)|$ we have

$c(\alpha(e))=c(e),\;o(\alpha(e))=\alpha(o(e))\quad\text{and}\quad
t(\alpha(e))=\alpha(t(e)).$

A _$\delta$ -almost-automorphism_ $\alpha$ is a weak $\delta$-almost-
automorphism that moreover satisfies the first two conditions, namely
$c(\alpha(e))=c(e)$ and $o(\alpha(e))=\alpha(o(e))$, for all directed edges
$e\in E(A)$.

######  Observation 8.1.

Let $\alpha$ be a weak $\delta$-almost-automorphism of the finite Schreier
graph $A$. Up to changing $\alpha$ on at most $O(\delta|E(A)|)$ edges we can
make $\alpha$ into a $\delta$-almost-automorphism.

Fix some integer $n\in\mathbb{N}$.

######  Definition 8.2.

A (weak) $\delta$-almost-automorphism $\alpha$ has _$\delta$ -almost order
$n$_ if the condition $\alpha^{n}(v)=v$ holds true for all $v\in V(A)$ except
for a subset of size $\delta|V(A)|$.

Given an action $\rho:F_{d}*\left<a\right>\to\operatorname{Sym}(X)$ on some
finite set $X$ we denote by $A_{\rho}$ the Schreier graph of the restricted
action $\rho:F_{d}\to\operatorname{Sym}(X)$. Let $\alpha_{\rho}$ denote the
bijection on the vertices of the Schreier graph $A_{\rho}$ defined by
$\alpha_{\rho}=\rho(a)$. Moreover, by abuse of notation, let $\alpha_{\rho}$
denote the bijection of the directed edges of $A_{\rho}$ defined for every
$e\in E(A)$ by $\alpha_{\rho}(e)=e^{\prime}$ where $e^{\prime}$ is the unique
edge satisfying $c(e)=c(e^{\prime})$ and $o(e^{\prime})=o(\alpha_{\rho}(e))$.

######  Observation 8.3.

If $\rho:F_{d}*\left<a\right>\to\operatorname{Sym}(X)$ is a $\delta$-almost
$(F_{d}\times\mathbb{Z})$-action (resp. $\delta$-almost
$(F_{d}\times(\mathbb{Z}/n\mathbb{Z}))$-action) on some finite set $X$ then
$\alpha_{\rho}$ is a $\delta$-almost-automorphism of the Schreier graph
$A_{\rho}$ (resp. of $\delta$-almost-order $n$).

Vice versa, if $A$ is a finite Schreier graph of the group $F_{d}$ and
$\alpha$ is $\delta$-almost-automorphism (resp. of $\delta$-almost-order $n$)
of the free group $F_{d}$ then there exists a $\delta$-almost
$(F_{d}\times\mathbb{Z})$-action (resp. $\delta$-almost
$(F_{d}\times(\mathbb{Z}/n\mathbb{Z}))$-action)
$\rho:F_{d}*\left<a\right>\to\operatorname{Sym}(X)$ such that $A=A_{\rho}$ and
$\alpha=\alpha_{\rho}$.

Theorem A applied to the virtually free group
$F_{d}\times(\mathbb{Z}/n\mathbb{Z})$ and combined with the above observations
immediately gives the following corollary.

######  Corollary 8.4.

Let $A$ be a finite Schreier graph of the free group $F_{d}$ and let $\alpha$
be a weak $\delta$-almost automorphism of $\delta$-almost order $n$. Then
there exists a Schreier graph $A^{\prime}$ of the group $F_{d}$ with
$V(A)=V(A^{\prime})$, and an automorphism $\alpha^{\prime}$ of $A^{\prime}$ of
order $n$ such that the graphs $A$ and $A^{\prime}$ differ on at most
$O(\delta|E|)$ edges, and the automorphisms $\alpha$ and $\alpha^{\prime}$
differ on at most $O(\delta|V|)$ vertices.∎

Note that Corollary 8.4 is false without requiring that $\alpha$ has
$\delta$-almost order $n$ since $F_{d}\times\mathbb{Z}$ is non P-stable by
[2].

We end this paper with the following related question.

######  Question 8.5.

Is the conclusion of Corollary 8.4 true in the setting of general $d$-regular
graphs and graph automorphisms (rather than Schreier graphs of $F_{d}$)?

## References

  * [1] Lev Glebsky and Luis Manuel Rivera.  Almost solutions of equations in permutations.  Taiwanese Journal of Mathematics, 13(2A):493–500, 2009.
  * [2] Adrian Ioana.  Stability for product groups and property ($\tau$).  Journal of Functional Analysis, 279(9):108729, 2020.
  * [3] Nir Lazarovich, Arie Levit, and Yair Minsky.  Surface groups are flexibly stable.  arXiv preprint arXiv:1901.07182, 2019.
  * [4] Jean-Pierre Serre.  Arbres, Amalgames, $\mathrm{SL}_{2}$. 1977\.
  * [5] John Stallings.  On torsion-free groups with infinitely many ends.  Annals of Mathematics, pages 312–334, 1968.
  * [6] John Stallings.  Group theory and three-dimensional manifolds.  Yale University Press, 1972.


[a]Sijbrand de Jong

# Giant Radio Array for Neutrino Detection (GRAND)

the GRAND Collaboration

###### Abstract

GRAND is a newly proposed series of radio arrays with a combined area of
200,000 km2, to be deployed in mountainous areas. Its primary goal is to
measure cosmic ultra-high-energy tau-neutrinos ($E>1$ EeV), through the
interaction of these neutrinos in rock and the decay of the tau-lepton in the
atmosphere. This decay creates an air shower, whose properties can be inferred
from the radio signal it creates. The huge area of GRAND makes it the most
sensitive instrument proposed to date, ensured to measure neutrinos in all
reasonable models of cosmic ray production and propagation. At the same time,
GRAND will be a very versatile observatory with enormous exposure to ultra-
high-energy cosmic rays and photons.

This talk covers the scientific motivation, as well as the staged approach
required in the R&D stages to get to a final design that will make the
construction, deployment and operation of this vast detector affordable.

Figure 1:  Overview of the GRAND ultra-high-energy neutrino detection scheme.

##  1 Introduction

GRAND is a planned Giant Radio Array for Neutrino Detection [1]. The principle
of the GRAND observatory layout is shown in Fig. 1. It should be large enough
to detect ultra-high-energy cosmic neutrinos, with an energy above an EeV or
so, for all standard theory scenarios. This turns out to require a 200 000 km2
array. This is huge and too big to be realised in one go today. Therefore a
staged approach is followed, where at present a 300 antenna GRAND Proto300
array is being realised and a more than 10 000 km2 array would be the logical
next step.

##  2 Ultra-high-energy neutrino production and detection

Ultra-high-energy cosmic neutrinos are assumed from two sources. They can come
directly from the sources of ultra-high-energy (UHE) cosmic rays, where in the
interactions of cosmic rays also pions and thereby neutrinos are being
produced. IceCube probably detected such neutrinos in the PeV energy range
[2]. Or these neutrinos can come from interactions of UHE cosmic rays with the
cosmic photon background from CMB and other sources, where also pions can be
produced, thus creating neutrinos. The neutrinos that are produced are of the
muon and electron type and oscillation to tau neutrinos will cause as many tau
neutrinos as any of the other two types to reach the Earth. The yield of
cosmogenic UHE neutrinos can be estimated knowing the UHE cosmic ray spectrum,
but e.g. the unknown composition, source distribution, etc. give appreciable
uncertainty. Extrapolating the IceCube spectrum [3] may give an indication of
the expected UHE neutrino yield from sources, but is rather uncertain due to
the galactic to extra-galactic transition in the spectrum.

The detection principle is that UHE neutrinos develop a sizable cross section
with ordinary matter. Therefore at energies in the EeV region there is a
sizable probability that a neutrino interacts in a few kilometres of Earth. At
these energies neutrinos basically never penetrate the full Earth and it is no
longer the volume of the target that determines the yield, but the surface
with a few km thickness. The strategy then is to look for neutrinos that
interact with mountains or are Earth skimming. On a charged current
interaction either an electron, muon or tau emerges. On the right hand side of
Fig. 1 the interactions for each type of neutrino with a mountain are
illustrated. Electrons will quickly get stuck, producing an electromagnetic
shower, with a small probability of a signal escaping the Earth. Muons will
escape, but do not leave much signal density in the Earth or atmosphere and
are therefore hard to detect. Taus on the other hand, due to their limited,
but finite lifetime will mostly leave the mountain and decay in the atmosphere
in about 50 km or so, where an air shower develops. The aim is to detect these
air showers using their radio signal. Since the atmosphere is transparent for
this radio frequency radiation, the shower can be observed also at many km
after it died out. The radio detection has to be optimised for horizontal
showers, which is a challenge, but has been demonstrated as possible in
principle [4].

##  3 GRAND as multi-messenger observatory

Aside from the primary goal of UHE neutrino detection, for both particle
physics and astrophysics measurements, a huge radio detector will also cover
many other science goals, such as the detection of UHE photons and cosmic
rays, making it a true multi-messenger observatory. This is illustrated on the
right hand side in Fig. 2 Of course this also gives a background to the
neutrinos, but the distinction is not so difficult, e.g. using the direction,
where no photons or cosmic rays are expected from lines of sight with many km
of Earth. GRAND will also offer opportunities for the detection and
measurement of fast radio bursts and giant radio pulses, as well as a
measurement of the epoch of re-ionisation, as illustrated in the diagram on
the left in Fig. 2, but this will not be covered in this presentation.

Figure 2:  GRAND as versatile observatory and its multi-messenger
capabilities. The physics and astronomy topics that will be covered are listed
in the diagram on the left. The sources and propagation of the various
messengers that can be detected by GRAND are illustrated in the picture on the
right hand side.

##  4 GRAND predicted performance

Figure 3:  Estimated flux sensitivities for GRAND and limits and sensitivity
of other present and future observatories for UHE neutrinos on the left and
UHE photons in the middle. On the right the relative exposure for UHE cosmic
rays for GRAND compared to those of the Pierre Auger and Telescope Array
Observatories. Figures from [1] with references to data and predictions
mentioned therein.

An end-to-end simulation and reconstruction pipeline has been set up, with the
development of efficient semi-analytical methods for the modelling of radio
emissions [5]. Dedicated reconstruction methods for very inclined air-showers
are also being developed, with promising results in terms of angular
resolution ($\sim 0.1^{\circ}$) and on the composition estimator [6]. From
this, the required size of the array with a 1 km detector station spacing has
been determined to be about 200 000 km2 for a certain detection of UHE
cosmogenic neutrinos over the full range of the standard theoretical models
[1]. This is illustrated in Fig. 3 on the left, where the predicted GRAND
performance is plotted with several existing limits and sensitivity of other
future observatories. In case of no detection, something extraordinary is
going on and we would have to completely rethink our view of the UHE particle
universe, this would be the scientific jack pot. From the simulation also the
sensitivity to UHE photons is illustrated in the middle plot of Fig. 3, where
also for UHE photons detection is expected for most reasonable scenarios.
GRAND will also collect a very large sample of UHE cosmic rays, which is
illustrated on the right hand side of Fig. 3, where more than an order of
magnitude more events are expected to be detected by GRAND than are recorded
with the present Pierre Auger and Telescope Array Observatories.

##  5 GRAND sites

Figure 4:  Exposure map for 1 GRAND site.

But there is also astrophysics reason to distribute this area in a number of
sites. Due to the sensitivity to horizontal showers, at any one time a
circular wedge of the universe is viewed. Although from one site, integrated
over time, Fig. 4, covering all or most of the sky at any time will give much
more opportunity for observation of transients about 80% of the sky is
observed as shown in that are also observed by other instruments. Therefore,
to be able to optimally contribute to multi-messenger astronomy, it makes
sense to have of the order of ten detector sites distributed around the world.
One of such sites should therefore be about 10 000 to 20 000 km2 and on its
own has already a large enough exposure to deliver a very exciting science
programme from the moment the first site starts collecting data, while the
other sites are still being realised. A detector array of 200 000 km2, three
times the size of the Czech Republic, will be very hard to realise in one
location for reasons of available suitable land surface area, technical
realisation and maintenance, and for political reasons.

##  6 GRAND roadmap

Figure 5:  GRAND road map.

The staged approach allows the ultimate goal of 200 000 km2 to be attained in
steps and leads to a staged approach, where one 10 000–20 000 km2 array can be
deployed after the other. For such a huge array to be feasible, the detection
not only needs to work well, which has been demonstrated [7], but it also
needs to be financially viable, easy to deploy and extremely reliable. In
addition, it needs to provide its own trigger, which has been demonstrated to
be possible [8], but for which the purity needs to be improved. For these
reasons the GRAND roadmap in Fig. 5 starts with a series of smaller scale
prototypes. As a first step GRANDProto35 has demonstrated the principle on a
small array of 35 detector stations in on a site in China with the
specification compatible with a large array. Currently, GRANDProto300, a 300
detector station array on 300 km2, is being produced, where for the first time
in this roadmap steps are taken towards making the detector stations cheaper,
easier to deploy and more reliable. GRANDProto300 is also a main vehicle to
research self-triggering strategies.

##  7 GRANDProto300 progress

Figure 6:  Prototype station for the GRANDProto300 detector station.

Figure 7:  Low Noise front-end Amplifier prototype.

The radio detection station in GRANDProto300, a prototype shown in Fig. 7 are
autonomously operated. They have to create their own power and communicate
through a wireless connection. The station consists of the receiver antenna
mounted on a 3.5 m pole, where at half height also the wireless communication
antenna is mounted. The pole is supported by a box that holds the solar panel
for power harvesting and inside a battery to store and distribute power for
24/7 functioning and the electronics for digitising, analysing, triggering and
communicating to the central DAQ system. Underneath the box is an area that
can be filled with sand and rocks on location to mechanically stabilise the
structure, also in strong wind. The design is optimised for maintenance and
modification of the set-up at the cost of the price. The final design needs to
be even much cheaper and more robust, but should then not need servicing.

The detection frequency range of choice is 50-200 MHz. A significant amount of
work has been invested into an antenna design that is optimised for the
detection of horizontal showers. The current design uses a butterfly shape in
three polarisation direction: Two two-arm antennas for the horizontal and a
single-arm for the vertical polarisation.

The arms are relative small for the frequency range, which

Figure 8:  GRANDProto300 digitiser.

was necessary to get a good impedance match to the low noise amplifier over
the full frequency range and it also helps for mechanical stability. Combined
with the long pole on which the antenna is mounted it reduces ground
reflections for horizontal showers and the influence of the rest of the
mechanical structure at the foot of the pole.

The electronics consists of a low noise amplifier, see Fig. 7, AC connected
directly to the antenna at the top of the pole. In the electronics box the
signal is frequency filtered, amplified and digitised with 500 Mega samples of
14 bits per second, see Fig. 8 for the digitiser board. An integrated FPGA and
CPU chip analyses the signal, provides a station trigger and gathers
housekeeping information, e.g. for calibration. Prototype versions are in hand
and are being tested (Figs. 7 and 8). The final board is ready for production.
Station trigger information is sent to a central DAQ station that combines the
information in a level 2 trigger, which determines if the station information
is read by the central DAQ. After the level 2 trigger, the data processing is
centralised.

##  8 Outlook

GRAND is a huge detector that has been designed to have a no-loose theorem for
UHE neutrino observation, if they cannot be observed by GRAND, some new
(astro)physics must be going on. But GRAND is a much more versatile next
generation tool, also being able to detect UHE photons and cosmic rays and
capable of doing exciting radio astronomy. GRAND is to be realised in a step-
by-step approach and a road map towards its construction has been established.
The next step on this road map is the construction of a 300 detector station
prototype, GRANDProto300, which is well underway. In this step the focus is on
the self-triggering, which can be developed and tested with cosmic ray events.
The step after GRANDProto300 still poses large challenges, such as making the
detector stations much cheaper, much easier to deploy and much more robust,
all at the same time. The GRAND collaboration is making good steps forward,
but will need to grow considerably to be able to achieve its goals. Therefore,
more help from new collaborators looking for exciting challenges and a grand
goal is much welcomed.

## References

  * [1] GRAND Collaboration, The Giant Radio Array for Neutrino Detection (GRAND): Science and Design, Sci.China Phys.Mech.Astron. 63 (2020) 1, https://arxiv.org/pdf/1810.09994.
  * [2] IceCube, Fermi-LAT, MAGIC, AGILE, ASAS-SN, HAWC, H.E.S.S, INTEGRAL, Kanata, Kiso, Kapteyn, Liverpool telescope, Subaru, Swift/NuSTAR, VERITAS, VLA/17B-403 teams, Multimessenger observations of a flaring blazar coincident with high- energy neutrino IceCube-170922A, Science, 361 (2018) eaat1378, https://arxiv.org/pdf/1807.08816.
  * [3] IceCube Collaboration, The IceCube high-energy starting event sample: Description and flux characterization with 7.5 years of data, https://arxiv.org/pdf/2011.03545;
Joeran Stettner for the IceCube Collaboration, Measurement of the Diffuse
Astrophysical Muon-Neutrino Spectrum with Ten Years of IceCube Data,
Proceedings of the 36th International Cosmic Ray Conference (ICRC 2019), PoS-
ICRC2019-1017, https://arxiv.org/pdf/1908.09551.

  * [4] The Pierre Auger Collaboration, Observation of inclined EeV air showers with the radio detector of the Pierre Auger Observatory, JCAP 10 (2018) 026.
  * [5] M. Tueros, A. Zilles, Synthesis of radio signals from extensive air showers using previously computed microscopic simulations, https://arxiv.org/pdf/2008.06454; A. Zilles, et al., Radio Morphing: towards a fast computation of the radio signal from air showers, Astropart. Phys., 114 (2020) 10, https://arxiv.org/pdf/1811.01750.
  * [6] V. Decoene, Sources and detection of high energy cosmic events, PhD thesis, Sorbonne University, 6 November 2020, https://hal.archives-ouvertes.fr/tel-02991529.
  * [7] S.J. de Jong for the Pierre Auger Collaboration, The Radio detection of inclined showers at the Pierre Auger Observatory, These proceedings.
  * [8] J. Kelley for the Pierre Auger Collaboration, Data acquisition, triggering, and filtering at the Auger Engineering Radio Array, Nucl. Instrum. Meth. A725 (2013) 133, The Pierre Auger Collaboration, https://arxiv.org/pdf/1205.2104; Results of a self-triggered prototype system at the Pierre Auger Observatory for radio-detection of air showers induced by cosmic rays, JINST 7 (2012) P11023, https://arxiv.org/pdf/1211.0572.