These are notes of a talk on a theorem of Abért–Nikolov: Let \(\Gamma\) be a finitely generated group and let \((\Gamma_n)\) be a chain of finite index subgroups. Assume that the action of \(\Gamma\) on the boundary \(\partial T\) of the coset tree of \((\Gamma_n)\) is essentially free. Then the rank gradient of \(\Gamma\) with respect to the chain \((\Gamma_n)\) equals the cost of the action of \(\Gamma\) on \(\partial T\).

The coset tree

Let \(\Gamma\) be a countable, discrete group and let \(\Gamma = \Gamma_0 \ge \Gamma_1 \ge \Gamma_2 \ge \cdots\) be a chain of finite index subgroups. For the moment we do not make any further assumptions on the chain \((\Gamma_n)\). So the subgroups \(\Gamma_n\) must neither be normal, nor are they required to have trivial total intersection.

Definition: The (right) coset tree \(T\) of \((\Gamma, (\Gamma_i))\) has vertex set \(\coprod_{n \ge 0} \Gamma_n \backslash \Gamma\) and an edge from \(\Gamma_ng\) to \(\Gamma_{m}h\) if and only if \(m = n+1\) and \(\Gamma_mh \subset \Gamma_ng\).

Not that \(T\) has the canonical root \(\Gamma_0\), so that the \(n\)-th level vertex set is just \(\Gamma_n \backslash \Gamma\), and each node in \(\Gamma_n \backslash \Gamma\) has precisely \([\Gamma_n \colon \Gamma_{n+1}]\) children.

A typical coset tree.

Definition: The boundary \(\partial T\) of the coset tree \(T\) consits of all infinite rays starting at the root \(\Gamma_0\).

Thus in mathematical terms we have \(\partial T = \underset{\leftarrow}{\lim} \Gamma_n \backslash \Gamma\) and this description makes sense not only in the category of sets but also in the category of topological spaces and of measure spaces. Each \(\Gamma_n \backslash \Gamma\) carries the discrete topology and the uniform probability measure. Thus as a space, \(\partial T\) is compact, totally disconneted and Hausdorff. It has a basis of the topology given by shadows where a shadow \(\mathrm{sh}(\Gamma_n g)\) consists of all rays going through the vertex \(\Gamma_n g\). The Borel probability measure \(\mu\) on \(\partial T\) is determined by the values \(\mu (\mathrm{sh}(\Gamma_n g)) = \frac{1}{[\Gamma : \Gamma_n]}\). The group \(\Gamma\) permutes the cosets in \(\Gamma_n \backslash \Gamma\) by right multiplication preserving the child–parent relation. Thus \(\Gamma\) acts on \(T\) from the right by tree automorphisms and we obtain an induced probability measure preserving right action of \(\Gamma\) on \(\partial T\) by homeomorphisms.

Lemma: The action of \( \Gamma\) on \(\partial T \) is ergodic.

Proof: If the chain stabilizes, the boundary is finite and the action is transitive so that the assertion is clear. Otherwise, Kuratowski’s theorem says that \(\partial T\) is Borel-isomorphic to the unit interval with Lebesgue measure so that Lebesgue’s theorem applies: any measurable \(A \subseteq \partial T\) is almost everywhere dense. In particular, if \(\mu(A) > 0\), then for all \(\varepsilon > 0\) there is some \(\Gamma_n g_0\) with
\[ \mu (\mathrm{sh}(\Gamma_n g_0) \cap A) > (1 – \varepsilon) \mathrm{sh}(\Gamma_n g_0). \]
If \(A\) is moreover \(\Gamma\)-invariant, then the same must hold for all \(\Gamma_n g\). Adding up all these inequalities gives
\[ \mu(A) = \sum_{\Gamma_n g \,\in\, \Gamma_n \backslash \Gamma} \mu(\mathrm{sh}(\Gamma_n g) \cap A) > 1 – \varepsilon, \]
which implies \(\mu(A) = 1\).

Lemma : Suppose each \(\Gamma_n\) is normal in \(\Gamma\) and that the total intersection \(\bigcap_{n \ge 0} \Gamma_n\) is trivial. Then the action of \( \Gamma\) on \(\partial T \) is free.

Proof: Given any nontrivial \(g \in \Gamma\) there is \(n > 0\) such that \(g \notin \Gamma_n\). Since \(\Gamma_n\) is a normal subgroup of \(\Gamma\), the element \(g\) permutes the set \(\Gamma_n \backslash \Gamma\) without fixed points. Thus \(g\) moves all rays in \(\partial T\).

In view of this lemma the following concept is a natural generalization of the common assumptions on a chain \((\Gamma_n)\) given in the Lemma.

Definition: A chain \((\Gamma_n)\) of subgroups of \(\Gamma\) is called Farber if the action of \( \Gamma\) on \(\partial T \) is essentially free.

Here, as usual, « essentially free » means the set of points in \(\partial T\) with nontrivial stabilizer has measure zero.

Cost and groupoid cost

Cost

Let \((X, \mu)\) be a standard Borel space and let \( \Gamma \) act on \( X \) preserving a probability measure, with finitely many ergodic components. « Lying in the same orbit » defines an equivalence relation \(E\) on \(X\). So \(E\) is a measurable subset of \(X \times X\) which we can picture as (the edge set of) a directed graph. Reflexivity, symmetry and transitivity say that the connected components of \(E\) are complete as directed gaphs: each vertex carries a loop and any two distinct vertices in the same component are joined by precisely two edges, one in each direction. Since \(\Gamma\) is countable, so are the complete directed graphs given by each component.

Apparently, we can reconstruct \(E\) if we only know which pairs of points in \(X\) are connected by some finite path along edges in \(E\), regardless of their direction. This information, in turn, is captured by any measurable subset \(S \subset E\) with the property that two points \(x,y \in X\) are joined by an edge in \(E\) if and only if there is a path between \(x\) and \(y\) along edges in \(S\).

Definition:

1. A measurable subset \(S \subseteq E\) is called a subgraph of \(E\).
2. The \(k\)-th power \(S^k\) of a subgraph \(S \subseteq E\) is defined by requiring \((x,y) \in S^k\) if and only if there is an undirected path from \(x\) to \(y\) in \(S\) of length \(l\) with \(0 \le l \le k\).
3. We say that a subgraph \(S \subseteq E\) spans \(E\) if \(E = \bigcup_{k \ge 0} S^k\). In this case we write \(E = \langle S \rangle\).

Note that \(S^0\) is the set of loop edges in \(X\), regardless of what \(S\) is: each point \(x \in X\) is joined to itself by the empty path of length zero. The rules of the game are to find spanning subgraphs \(S\) of \(E\) which are as « small » as possible. It makes sense to quantify « small » by the average number of edges starting in a vertex of \(S\). The next definition makes this idea precise.

Definition: The edge measure \(e(S)\) of a subgraph \(S \subseteq E\) is given by
\[ e(S) = \int_X \deg_S(x) \,\mathrm{d} \mu(x) \quad \text{where} \quad \deg_S(x) = |\{y \in X \colon (x,y) \in S \}|. \]

Note that \(e(S)\) can be infinite. The largest lower bound of the edge measures of spanning subgraphs of \(E\) can be thought of measuring how much effort we must invest to generate the graph and thus the equivalence relation \(E\) which the action of \( \Gamma \) on \( X \) defines.

Definition: The cost of the action of \( \Gamma \) on \( X \) is given by
\[ \mathrm{cost}(X, \Gamma) = \mathrm{cost} E = \inf_{\langle S \rangle = E} e(S). \]

As an example, say \(\Gamma\) is finitely generated by \(g_1, \ldots, g_n\). Then
\[ S = \bigcup_{i=1}^n \{ (x, xg_i) \colon x \in X \} \]
clearly defines a spanning subgraph of \(E\). So we always have
\[ \mathrm{cost}(X, \Gamma) \le d(\Gamma) \]
where \(d(\Gamma)\) is the minimal number of generators of \(\Gamma\), also known as the rank of \(\Gamma\). Note that if the action of \( \Gamma \) on \( X \) is essentially free, almost every connected component of this subgraph \(S\) looks like the Cayley graph of \(\Gamma\) with respect to the generators \(g_1, \ldots, g_n\) but with no distinguished base point whatsoever.

The idea comes to mind that one can improve upon a spanning subgraph \(S\) as above by picking a maximal tree in each component. The problem is that depending on \(\Gamma\) there might be no measurable such choice which already hints at cost being quite a delicate invariant of the action. Let us mention that the cost of an action immediately yields an invariant for the group \(\Gamma\).

Definition: We define \(\mathrm{cost} \Gamma\) as the infimum of the numbers \(\mathrm{cost}(X, \Gamma)\) running over all essentially free, ergodic, probability measure preserving actions of \(\Gamma\) on a standard Borel space \((X, \mu)\).

Groupoid cost

In addition to examining (sub-)graphs, meaning measurable subsets of \(X \times X\), it is useful to also study graphings by which we mean any measurable subset \(M \subseteq X \times \Gamma\). We find it convenient to picture an element \((x,g) \in X \times \Gamma\) as an « arrow » in \(X\) pointing from \(x\) to \(xg\). Note that (almost all) these arrows are determined by their initial and final point if and only if the action of \(\Gamma\) on \( X \) is (essentially) free. We can sort the arrows in the subset \(M\) either by initial point or by direction: either by the \(X\)- or by the \(\Gamma\)-coordinate. So interchangeably we think of \(M\) as a family of subsets
\[ M_g = \{ x \in X \colon (x, g) \in M \} \subseteq X\]
parametrized by group elements \(g \in \Gamma\), or as a family of subsets
\[ M_x = \{ g \in \Gamma \colon (x, g) \in M \} \subseteq \Gamma\]
parametrized by points \(x \in X\). Guided by what we did above, we define the \(k\)-th power \(M^k\) of \(M\) by all the arrows we obtain by composing up to \(k\) arrows from \(M\) regardless of their direction. In more mathematical terms this means \((x,g) \in M^k\) if and only if there is \(0 \le l \le k\) and a decomposition \(g = g_1 \cdots g_l\) in \(\Gamma\) such that for all \(0 \le i \le l-1 \) either
\[ (x g_1 \cdots g_i, g_{i+1}) \in M \quad \text{or} \quad (x g_1 \cdots g_{i+1}, g_{i+1}^{-1}) \in M. \]
Note that \(M^0 = X \times \{ 1 \}\), regardless of what \(M\) is.

Definition: We say that a graphing \(M \subset X \times \Gamma\) spans \(X \times \Gamma\) if we have \(X \times \Gamma = \bigcup_{k \ge 0} M^k\). In this case we write \(\langle M \rangle = X \times \Gamma\).

Let \(e\) be the measure on \(X \times \Gamma\) given by the product of \(\mu\) and the counting measure on \(\Gamma\).

Definition: The groupoid cost of the action of \(\Gamma\) on \( X \) is given by
\[ \mathrm{gcost}(X, \Gamma) = \inf_{\langle M \rangle = X \times \Gamma} e(M). \]

To explain the terminology, we observe that the set \(X \times \Gamma\) has a groupoid structure: two arrows \((x_1, g_1), (x_2, g_2) \in X \times \Gamma\) can be composed if and only if \(x_1 g_1 = x_2\), meaning the first arrow points to the initial point of the second, and in that case their composition is \((x_1, g_1 g_2)\). So a graphing spans \(X \times \Gamma\) if and only if it generates \(X \times \Gamma\) as groupoid.

Proposition: We have
\[ \mathrm{gcost}(X, \Gamma) \ge \mathrm{cost}(X, \Gamma) \]
with equality if the action is essentially free.

Proof: A graphing \(M \subseteq X \times \Gamma\) defines a subgraph \(\Phi(M) \subseteq E\) of the orbit relation \(E \subseteq X \times X\) by setting
\[ \Phi(M) = \{ (x, xg) \colon (x,g) \in M \}. \]
Clearly \(\Phi(M^k) = \Phi(M)^k\) so that \(\Phi\) preserves the spanning property. We have \(\deg_{\Phi(M)} (x) \le |M^x|\) with equality almost everywhere if the action of \(\Gamma\) on \( X \) is essentially free. Integrating over \(X\) gives the inequality. To obtain equality for essentially free actions one still has to show that each spanning subgraph can be obtained from a spanning graphing via \(\Phi\); we skip this argument which needs some technical care but no unusual ideas.

Rank gradient and cost of the coset tree boundary

Let us now assume that \(\Gamma\) is finitely generated so that there is an epimorphism \(\varphi \colon F_k \rightarrow \Gamma\) from the free group on a finite number \(k\) of letters. If \(\Lambda \subseteq \Gamma\) is a subgroup of finite index, then by the Schreier theorem \(\varphi^{-1}(\Lambda)\) is likewise free. It has index \([\Gamma \colon \Lambda]\) in \(F_k\) so that an Euler characteristic argument reveals that the rank \(l\) of \(\varphi^{-1}(\Lambda)\) is given by \(l-1 = [\Gamma \colon \Lambda](k-1)\). For the ranks \(d(\Gamma_n)\) of the groups in our chain \((\Gamma_n)\) this means that the numbers
\[ \frac{d(\Gamma_n) -1}{[\Gamma \colon \Gamma_n]} \]
form a monotone non-increasing sequence of positive numbers.

Definition: The rank gradient of \(\Gamma\) with respect to \((\Gamma_n)\) is given by
\[ \mathrm{rg}(\Gamma, (\Gamma_n)) = \lim_{n \rightarrow \infty} \frac{d(\Gamma_n) – 1}{[\Gamma \colon \Gamma_n]}. \]

This notion is due to Lackenby and here is its dynamic interpretation.

Theorem (Abért–Nikolov, 2012): For any chain \((\Gamma_n)\) we have
\[ \mathrm{gcost}(\partial T, \Gamma) = \mathrm{rg}(\Gamma, (\Gamma_n)) + 1. \]

Before we come to the proof let us combine this theorem with the proposition.

Corollary: For any Farber chain \((\Gamma_n)\) we have
\[ \mathrm{cost}(\partial T, \Gamma) = \mathrm{rg}(\Gamma, (\Gamma_n)) + 1. \]

Proof of Theorem: We first show \(\mathrm{gcost}(\partial T, \Gamma) \le \mathrm{rg}(\Gamma, (\Gamma_n)) + 1\). For all \(\varepsilon > 0\) we find some \(n\) with \(\frac{d(\Gamma_n) -1}{[\Gamma \colon \Gamma_n]} \le \mathrm{rg}(\Gamma, (\Gamma_n)) + \varepsilon\). Thus the integer
\[ d = \lfloor(\mathrm{rg}(\Gamma, (\Gamma_n)) + \varepsilon)[\Gamma \colon \Gamma_n]\rfloor + 1 \]
gives an upper bound for \(d(\Gamma_n)\). Say \(\Gamma_n\) is generated by \(g_1, \ldots, g_d\) and let \(1 = \gamma_1, \ldots, \gamma_{[\Gamma \colon \Gamma_n]}\) be a system of representatives for \(\Gamma_n \backslash \Gamma\). We define a graphing \(M \subseteq \partial T \times \Gamma\) by setting
\[
M_g = \mathrm{sh}(\Gamma_n) \text{if } g = g_i \text{ for some } i \ge 1 \text{ or } g = \gamma_i \text{ for some } i > 1
\]
and \( M_g = \emptyset \) otherwise. We claim that \(\langle M \rangle = \partial T \times \Gamma\). Indeed, let \((x, g) \in \partial T \times \Gamma\) and let \(\gamma_a\) and \(\gamma_b\) be the representatives from the list for which \(x \in \mathrm{sh}(\Gamma_n \gamma_a)\) and \(\gamma_a g \gamma_b^{-1} \in \Gamma_n\). Hence we can write \(g\) as a word of the form \(\gamma_a^{-1} g^{\pm 1}_{i_1} \cdots g^{\pm 1}_{i_k} \gamma_b\). With respect to this factorization of \(g\) one easily verifies the criterion to conclude \((x,g) \in M^{k+2}\) proving the claim. By definition \(M_g\) equals \(\mathrm{sh}(\Gamma_n)\) for precisely \(d + [\Gamma \colon \Gamma_n] – 1\) elements in \(\Gamma\) and is empty otherwise. Hence the graphing \(M\) has measure
\[ e(M) = \frac{d + [\Gamma \colon \Gamma_n] – 1}{[\Gamma \colon \Gamma_n]}. \]
It follows that
\[ \mathrm{gcost}(\partial T, \Gamma) \le \frac{d-1}{[\Gamma \colon \Gamma_n]} + 1 \le \mathrm{rg}(\Gamma, (\Gamma_n)) + 1 + \varepsilon. \]

The reverse inequality \(\mathrm{gcost}(\partial T, \Gamma) \ge \mathrm{rg}(\Gamma, (\Gamma_n)) + 1\) is somewhat harder. Given \(\varepsilon 0\), there exists a graphing \(M\) which spans \(\partial T \times \Gamma\) and has measure \(e(M) \le \mathrm{gcost}(\partial T, \Gamma) + \frac{\varepsilon}{2}\). The first thing to do now is to construct yet another graphing \(N \subseteq \partial T \times \Gamma\) which is close to \(M\) in the sense that \(e(N \triangle M) \le \frac{\varepsilon}{2}\) and has the convenient property that each \(N_g\) is a finite union of shadows which is nonempty only for finitely many \(g \in \Gamma\). Since the shadows form a countable basis of the topology of \(\partial T\), it is conceivable that such a « finite approximation » to \(M\) exists. So we shall allow ourselves to skip the precise technical construction. Since \(N\) is made up from only finitely many shadows altogether, there exists a large enough \(n\) such that each \(N_g\) is in fact a finite union of level-\(n\) shadows of the form \(\mathrm{sh}(\Gamma_n h)\).

We define a finite, directed, labeled graph \(G\) as follows. The vertex set is \(V = \Gamma_n \backslash \Gamma\) and for each \(g \in \Gamma\) we connect \(w \in V\) with \(wg \in V\) by an edge of label \(g\) if and only if \(\mathrm{sh}(w) \subseteq N_g\). The graph \(G\) has the canonical base point \(v = \Gamma_n \in V\). This data clearly defines a homomorphism of groups
\[
\begin{array}{cc}
\varphi \colon \pi_1(G,v) & \longrightarrow \Gamma \\
l = (e_1, \ldots, e_k) & \longmapsto \mathrm{label}(e_1)^{\pm 1} \cdots \mathrm{label}(e_k)^{\pm 1}
\end{array}
\]
which multiplies the labels along a loop of edges, inverting the label whenever we travel through an edge in reverse direction. We claim that the image of the homomorphism \(\varphi\) is precisely \(\Gamma_n\). Indeed, for each \(l \in \pi_1(G,v)\) we have \(v \varphi(l) = v\) by the construction of the graph \(G\). Thus \(\varphi(l) \in \mathrm{Stab}(v) = \Gamma_n\). Let \(h \in \Gamma_n\) be any element and pick some ray \(x \in \mathrm{sh}(v)\). Since \(N\) spans \(\partial T \times \Gamma\), there is a factorization \(h = g_1 \cdots g_k\) with \(g_i \in \Gamma\) such that for all \(0 \le i \le k-1\) either
\[ (x g_1 \cdots g_i, g_{i+1}) \in N \quad \text{or} \quad (x g_1 \cdots g_{i+1}, g_{i+1}^{-1}) \in N. \]
For \(0 \le i \le k\) let \(w_i \in V = \Gamma_n \backslash \Gamma\) be the level-\(n\) vertex in the coset tree \(T\) through which the ray \(x \gamma_1 \cdots \gamma_i\) passes. Then we have \(w_0 = w_k = v\) and for each \(0 \le i \le k-1\) either \(w_i\) is connected to \(w_{i+1}\) by an edge in \(G\) with label \(g_{i+1}\) or \(w_{i+1}\) is connected to \(w_i\) by an edge of label \(g_{i+1}^{-1}\). Hence these edges form a loop \(l\) with \(\varphi(l) = h\) proving the claim.

Thus \(\Gamma_n\) is a quotient group of \(\pi_1(G,v)\). The latter group is free of rank \(1 – \chi(G)\) where \(\chi(G)\) is the Euler characterisitc of the graph \(G\). Note that
\[ \textstyle e(N) = \sum_{g \in \Gamma} \ \sum_{\mathrm{sh}(\Gamma_n h) \subseteq N_g} \frac{1}{[\Gamma \colon \Gamma_n]} \]
so that \(e(N) [\Gamma \colon \Gamma_n]\) is the number of edges in \(G\) while the number of vertices in \(G\) is of course \([\Gamma \colon \Gamma_n]\). Putting pieces together we obtain
\[ d(\Gamma_n) \le d(\pi_1(G,v)) = 1 + e(N)[\Gamma \colon \Gamma_n] -[\Gamma \colon \Gamma_n]. \]
By subadditivity of the measure \(e\) applied to \(N \subseteq M \cup (N \triangle M)\) we conclude
\[ \textstyle \mathrm{rg}(\Gamma, (\Gamma_i)) \le \frac{d(\Gamma_n) – 1}{[\Gamma \colon \Gamma_n]} = e(N) – 1 < \mathrm{gcost}(\partial T, \Gamma) + \varepsilon – 1. \]

References

• Miklós Abért, Nikolay Nikolov, Rank gradient, cost of groups and the rank versus Heegaard genus, J. Eur. Math. Soc.