cp's mathem-o-blog

In order to define a free product with amalgamation $A \ast_C B$ you need to define $A,B,C$ and embeddings of $C$ into $A$ and $B$. Alternatively, instead of $C$ you can use a homomorphism $\phi: A \rightarrow B$ and its inverse. A third option is to pick subgroups $D \subset A$ and $E \subset B$ and give an isomorphism between them.

All three of these options require you to define some groups and some morphisms. You can define a group nicely by giving a presentation but defining maps usually takes a few lines. So, I’d like a quicker way of describing the kinds of maps we need here.

Let’s take the third option. If we have generating sets so that $D = \langle X \rangle$ and $E = \langle Y \rangle$, then if we can write each of the elements of $X$ as words in $Y^*$ then that defines the required isomorphism completely. After you’ve done that, the generating set $Y$ might as well just be those words.

So how about this as a presentation for an FPA?

\[ \langle  a_1, a_2, \dots  | R_A \rangle [  x_1 = y_1, x_2 = y_2, \dots  ] \langle b_1, b_2, \dots  | R_B \rangle \]

The bits in angle brackets are presentations of $A$ and $B$. The $x_i$ are words from $A$ and generate $D$, and the $y_i$ are words from $B$ and generate $E$.

Because this is all on one line and delimited adequately, you can chain things together and use brackets and all that, like this contrived example:

\[ \left ( \langle a,b \rangle [ b =c ] \langle c,d | cd = dc \rangle \right ) [ a=e ] \langle e,f \rangle \]

For HNN extensions, you just need to say what the original group is, what the extending letter is, and what the identified subgroups are. So how about something like:

\[ \langle g_1, g_2, \dots | R_G \rangle [ t | x_1 = y_1, x_2 = y_2, \dots ] \]

Apart from the different kinds of brackets being hard to distinguish visually, what have I missed?

Not completely sure about this, but here we go: I will show that an ordered, plane recursive tree is $E_n$-computable, $n \geq 3$, if each vertex has its number of children bounded by an $E_n$ function. So this rules out trees which grow sideways a lot quicker than they grow in height, but it has to be a lot quicker. Infinite trees are $E_3$ (maybe) continued »

In order to prove the fgoagog thing we need to be able to do computations on trees at a low level of the Grzegorczyk hierarchy, so it doesn’t mess up the complexity of the whole group computation. I will give a model of finite trees that lies in $E_3$, the same level as Cannonito/Gatterdam’s standard index for the free group.¹

Lists and finite trees are $E_3$ continued »

1. this post has been sitting as a draft since the beginning of May because I wanted to make some nice tree pictures, but I’d rather just publish it now. So, the trees section is copied out of my notes and might not make sense [↩]

So I read a bit about categories after Peter Hines came up to talk to us.

Categories

A category $C$ is a collection of objects $obj(C)$ (or just Obj), a collection of arrows (or morphisms) $hom(C)$ (or just Hom), and an arrow composition operation $\circ$ such that there is an identity arrow for each object.

An arrow has a single source object and a single target object, and is written $A \overset{f}{\rightarrow} B$. Computable categories continued »

I’m going to write up a result I think I’ve proved, which follows on from Gatterdam’s thesis. He showed that if a group is $E_n$ computable, then doing a free product with amalgamation or any number of HNN extensions to it results in a group which is at worst $E_{n+1}$ computable. What I’m going to say is that the fundamental group of a graph of $E_n$ groups is at most $E_{n+1}$ computable. This isn’t unreasonable, because a fgoagog¹ represents a load of HNN extensions and amalgamated products.

The tactic will be to follow Gatterdam’s method for amalgamated products – if we can find an algorithm which solves the word problem of the fgoagog (decides if a word on the generators is equivalent to the identity) in $E_{n+1}$ time, then the whole group is $E_{n+1}$ computable as a quotient of the free group by the set of trivial words.

I will define an admissible form for words from the fgoagog, which is an alternating series of edge letters and words from the vertex groups, such that the edge letters make up a cycle starting and ending at the base vertex. Once we have a word in admissible form, we can reduce it by swapping the image of an edge group in one vertex with its counterpart in the vertex at the other end, and eventually a trivial word will end up as just a word on the base vertex, which is an $E_n$ decision.

Clearly the process of putting a word in admissible form involves knowing something about the shape of the graph, so we need to make some $E_n$ computable functions which can represent the graph and compute paths between vertices. That’s a tiny bit interesting on its own, so I’ll spend my next post talking about that. It will need some pretty pictures of trees though, which is why I’ve put off writing it for so long.

1. ‘fgoagog’ is short for ‘fundamental group of a graph of groups’, because I can’t be doing with writing that out once every three minutes [↩]

I've started a collection of interesting non-pregroup-related papers on Mendeley. At the moment this includes a formal system which makes the diagrams in Euclid's proofs a part of the formal reasoning, and "How to explain zero-knowledge protocols to your children"

Right, so I’ve written about computable groups and the Grzegorczyk hierarchy previously. Now it’s time to join the two together so we can talk about the computational complexity of certain groups.

$E_n$ computable groups

Let $G$ be a group with an admissible index $i$ and corresponding multiplication function $m$. If $i(G)$ is $E_n$ decidable¹ and $m$ is $E_n$ computable, then $G$ is said to be $E_n$ computable.

We can also add the characteristic function² of a particular set to the primitive functions in the Grzegorczyk hierarchy to make some arguments about group computability easier. If we have $c_A$, the characteristic function of the set $A$, to our hierarchy, then we say a function (or group) is $E_n(A)$ computable³ if it can be obtained from composition and bounded recursion on $E_n$ functions and $c_A$.

Groups and the Grzegorczyk Hierarchy continued »

1. there is an $E_n$ computable function which returns $1$ on numbers which are indices of elements of $G$, and $0$ otherwise [↩]
2. $c_A$ such that $c_A(x) = 1$ if $x \in A$, and $0$ otherwise [↩]
3. or “$E_n$ computable relative to $A$” [↩]

This is Rabin’s definition of computable groups. There’s a slightly different version by Mal’cev but I haven’t read it and Rabin seems the most popular from my perspective.

Computable functions and sets

Very quickly: the primitive recursive functions are the class of functions that starts with the same primitives as the Grzegorczyk hierarchy, closed under composition and unbounded recursion. The recursive functions are the primitive recursive functions also closed under minimalisation, the operation which gives you the least $n$ such that some $P(n)=1$¹ . Because those all sound like fairly possible things to do, recursive functions are also called (effectively) computable functions.

For any subset $S \subseteq \mathbb{N}$ of the natural numbers, one can define a characteristic function $c_S(n)$, which takes the value $c_S(x)=1$ when $x \in S$, and $0$ otherwise. A set $S$ is said to be recursive if its characteristic function $c_S$ is recursive.

Computable Groups continued »

1. “the least x such that P(x) holds” is written $(\mu x)[P(x)]$ [↩]

I think this is the last Vast Branch of Mathematics I need to include before heading right into Rimlinger, but who knows? The Bass-Serre theory of fundamental groups of graphs of groups (fgoagogs!) is a very appealing way of representing constructions like free products with amalgamation and HNN extensions, where you create bigger groups by identifying subgroups of ones you’ve already got. Or the other way round; FPAs and HNN extensions are the building blocks of Bass-Serre theory. Whatever.

Serre’s Graphs and Trees continued »

Now to the other end of the subject, computational complexity. The two ends aren’t going to meet in the middle, but the Grzegorczyk Hierarchy is so simple it should be at the start by natural justice, and it’s good to have in mind as a pleasant ending point while getting lost in pregroup theory.

If you want to ask yourself whether a problem is computable or not, you have to define what you mean by ‘computable’. It’s left as an exercise for the reader, basically. So the popular thinking is that effectively computable functions and recursive functions are the same thing – that is, every computable function should be recursive.

Furthermore, a slightly smaller class of functions, the primitive recursive functions, contains pretty much everything anyone’s interested in, and leaves out horror shows like the Ackermann function.

The idea is that you can start with a few really simple initial functions: zero; successor; projection, and the operations of composition and recursion, and end up with pretty much every function on the natural numbers that anyone’s ever thought up.¹

A primitive recursive function is one which can be defined by finitely many compositions and recursions on the initial functions. A generally recursive function can be defined using unbounded minimisation as well, but remember that we’re deliberately ignoring those.

The Grzegorczyk Hierarchy continued »

1. before this was claimed and people tried to think of things that weren’t included in this class, anyway [↩]