I try to avoid long-winded but precise notation when possible and use more standard notation. But we do need to be careful!
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:
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:
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:
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:
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.
/
#