\[
\def\grz#1{\mathcal{E}^{#1}}
\]

I try to avoid long-winded but precise notation when possible and use more standard notation. But we do need to be careful!

- $f(x_1,\dots,x_n)$: Application of the function $f$ to the arguments $x_1, \dots, x_n$. Or arguments could be a vector $\mathbf{x}$, so $f(\mathbf{x})$ means the same thing.
- $\langle\text{new notation}\rangle \equiv \langle\text{alternate notation}\rangle := \langle\text{expression in old notation}\rangle$.
*Iteration*: $f^{(n)}(x)$ is $f$ composed with itself $n-1$ times.

Functions with domain and range $\mathbb{N}$. ($0$ is a natural number. I'm not a Roman.)

Start with these three (classes of) *primitive* functions:

*Zero*: $z() := 0.$*Successor*: $s(x) := x+1.$*Projection*: for every $n \gt 0$ and $1 \leq i \leq n$ there's a projection function $P_n^i(x_1, \dots, x_n) := x_i$ which picks out the $i$^{th}argument.

There are two operations available to create new functions from the primitives.

Given an $n$-ary function $f$ and $m$-ary functions $g_1, \dots, g_n$, $C$ constructs a new function $h$, the composition of $f$ and the $g$s:

\[ h(\mathbf{x}) = f(g_1(\mathbf{x}), \dots, g_n(\mathbf{x})) := C(f,g_1,\dots,g_n)(\mathbf{x}). \]

When $f$ is unary, we might as well write:

\[ f \circ g(\mathbf{x}) \equiv f(g(\mathbf{x})) := C(f,g)(\mathbf{x}). \]

A function $h$ is constructed by *recursion* from functions $f$ and $g$ if

\begin{align} h(\mathbf{x},0) &:= f(\mathbf{x}), \\ h(\mathbf{x},n+1) &:= g(n,h(\mathbf{x},n),\mathbf{x}). \end{align}

We can also write $h = R(f,g)$.

Make a function which adds any constant $k$ by composing the successor $k$ times:

\[ x+n := s^{(n)}(x). \]

Addition of variables can be defined recursively from the successor function:

\begin{align} x+0 &:= x \equiv P^1_1(x), \\ x+(y+1) \equiv (x+y)+1 &:= s(x+y). \end{align}

Similarly, multiplication is repeated addition:

\begin{align} x \cdot 0 &:= 0, \\ x \cdot (y+1) &:= (x \cdot y) + x. \end{align}

We want to classify functions by how quickly they grow.

Could count recursions, but often recursion can give you a "smaller" function.

Instead, count *unbounded* recursions.

A function $f$ is *bounded* by another function $h$ if, for all $\mathbf{x}$, $f(\mathbf{x}) \lt h(\mathbf{x})$.

A class of functions $\mathcal{C}$ is *closed under bounded recursion* if, whenever $f,g,h$ belong to $\mathcal{C}$ and $R(f,g)$ is bounded by $h$, then $R(f,g)$ also belongs to $\mathcal{C}$.

If there is no $h$ that bounds $R(f,g)$, then $R(f,g)$ is said to be obtained by an *unbounded recursion on $f$ and $g$*.

The *Grzegorczyk hierarchy* is an infinite nested hierarchy of classes $\grz{n}$ of functions which are closed under finite composition and bounded recursion.

$\grz{0}$ consists of just the primitive functions and whatever you can get from finitely many compositions and bounded recursion.

$\grz{n+1}$ is the smallest class which:

- contains all of $\grz{n}$;
- contains every function obtained by a single unbounded recursion on $\grz{n}$ functions;
- is closed under finite composition and bounded recursion.

Say a function is *$\grz{n}$-computable* iff it belongs to $\grz{n}$. Similarly, a set is said to be *$\grz{n}$-decidable* iff its characteristic function $\chi_S$ is $\grz{n}$-computable.

The aim is to find definitions of functions which put them at the lowest possible level of the hierarchy

Every $\grz{0}$-computable function $f(x_1,\dots,x_n)$ is bounded by some function of the form $x_i+k$, for some integers $k$ and $i$, $1 \leq i \leq n$.

Every $\grz{1}$-computable function is bounded by a linear combination of its arguments:

\[ f(x_1, \dots, x_n) \leq a_0 + a_1 \cdot x_1 + a_2 \cdot x_2 + \dots + a_n \cdot x_n. \]

Every $\grz{2}$-computable function is bounded by a polynomial.

$\grz{3}$ is equivalent to the complexity class elementary.

We'll need to work with lists of numbers.

Encode a list of integers as a single integer using *Gödel encoding*.

An *$n$-tuple* is a sequence of $n$ integers $x_0, \dots, x_{n-1}$.

The Gödel encoding of an $n$-tuple is:

\[ \mathbf{x} \equiv [x_0, \dots, x_{n-1}] := \prod_{i \lt n} p_i^{x_i+1}. \]

Functions to deal with lists all belong to $\grz{3}$.

Serre defines a graph as a set of vertices $V$ and a set of directed edges $E = E^+ \cup E^-$, with two associated maps.

First, \[ e \mapsto (\iota(e), \tau(e)) \]

associates each edge with its start and end vertices.

Secondly, \[ e \mapsto \bar{e} \]

is an involution on the edges.

A *path* in a graph is a sequence of edges $(e_1,e_2, \dots, e_n)$ such that $\tau(e_i) = \iota(e_{i+1})$, $1 \leq i \lt n$. A path is *reduced* if it doesn't contain its inverse.

A *circuit* is a path which starts and ends at the same vertex.

A path is *reduced* if no edge is followed by its inverse.

A tree $T = (V,E)$ is a connected, non-empty graph with no reduced circuits.

A *rooted* tree has a vertex $v_0$ chosen to be at the 'top' and called the *root*.

In an *ordered* tree, the set of children of each vertex is ordered, so there is a least, or *leftmost* child, and the others are on the right.

An *ordered recursive tree* is a rooted, ordered tree obtained by a recursive process which begins with the root and adds vertices below existing ones, in effect enumerating the edges.

In an ordered recursive tree, every edge can be given a label equal to that of its bottom vertex.

A finite ordered recursive tree can be entirely described by a *depth-first walk*.

Finally, the thing we're here for!

A group $G$ is *$\grz{n}$-computable* if there exist $\grz{n}$-computable functions which represent its structure entirely:

- $i: G \to \mathbb{N}$ is an injection of $G$ onto an $\grz{n}$-decidable subset of $\mathbb{N}$ (an
*index*function); - $m: i(G) \times i(G) \to i(G)$ computes the product of two group elements, i.e.: \[ m(i(g_1), i(g_2)) = i(g_1g_2), \forall g_1,g_2 \in G;\]
- $j: i(G) \to i(G)$ computes the inverse of any element of $G$.

The *standard index* for a group presentation encodes generators as numbers, and words as lists of those numbers. Multiplication is done by concatenating lists, then finding the word with smallest encoding which is equivalent in the group.

Let $G = \langle X | R \rangle$ be a presentation of a group.

The *HNN extension* of $G$, with respect to an isomorphism $\phi: H \to K$ which identifies two subgroups $H$ and $K$, has presentation:

\[ G_\phi = \left\langle X,t \: \Big| \: R, tht^{-1} = \phi(h), \forall h \in H \right\rangle. \]

The *free product with amalgamation* of two groups $G_1 = \langle X_1 | R_1 \rangle$ and $G_2 = \langle X_2 | R_2 \rangle$, with respect to an isomorphism $\phi: H_1 \to H_2$ which identifies subgroups from each group, has presentation:

\[ G_1 \underset{\phi}{\ast} G_2 = \left \langle X_1,X_2 \: \Big| \: R_1,R_2, h=\phi(h), \forall h \in H_1 \right\rangle. \]

Cannonito and Gatterdam showed that HNN extensions and FPAs move one level up the Grzegorczyk hierarchy:

- When $G$ and $\phi$ are $\grz{n}$-computable, the HNN extension $G_\phi$ is $\grz{n+1}$-computable.
- If $G_1$ and $G_2$ are $\grz{n}$-computable, $H_1$ and $H_2$ are $\grz{n}$-decidable subgroups of $G_1$ and $G_2$, and $\phi: H_1 \to H_2$ is $\grz{n}$-computable, $G_1 \underset{\phi}{\ast} G_2$ is $\grz{n+1}$-computable.

The *fundamental group of a graph of groups* (fgoagog!) generalises group extensions.

Let $\Gamma = (V,E)$ be a connected graph.

Associate with each vertex $v$ a *vertex group* $G_v$. Call the set of all vertex groups $\mathbf{G}$.

To each edge $e$ associate two isomorphic *edge groups* $A_e \leq G_{\iota(e)}$ and $B_e \leq G_{\tau(e)}$, with $A_e = B_{\bar e}$, and an isomorphism $\phi_e: A_e \to B_e$.

$(\mathbf{G},\Gamma)$ is called a *graph of groups*.

Let $T$ be a spanning tree of $\Gamma$, with a root vertex $v_0$.

The *fundamental group* of $(\mathbf{G},\Gamma)$ with respect to $T$ is the group $\pi_1(\mathbf{G},\Gamma,T,v_0) = \langle X | R \rangle$, with:

\[ X = \left( \bigcup_{v \in V} X_v \right) \cup \left( \bigcup_{e \in E} \{e\} \right), \]

\[ R = \left( \bigcup_{v \in V}R_v \right) \cup \{e^{-1}ae = \phi_e(a), \forall a \in A_e, \forall e \in E\} \cup \{ e^{-1} = \bar{e}, \forall e \in E\} \cup \{ e = 1, \forall e \in T \}.\]

If all the $G_v$ and $\phi_v$, and the tree $T$, are $\grz{n}$-computable, and all the edge groups are $\grz{n}$-decidable, then the fgoagog $\pi_1(\mathbf{G},\Gamma,T,v_0)$ is $\grz{n+1}$-computable.

My blog is at checkmyworking.com

There's a video of this talk, with the words I spoke while pointing at the words on the slides, on my YouTube channel.

/

#