Over Christmas I typed up my Bass-Serre / Grzegorczyk stuff in quite a lot of detail and fairly rigorously. It’s far too much to put up here as blog posts, so here’s a link to the PDF.

The big theorem I prove says that the fundamental group of a graph of $E_n$-computable groups is $E_{n+1}$-computable. But are there cases when the fgoagog stays at $E_n$, and can we pin down what conditions cause it to move up to $E_{n+1}$? I’ve found a couple of examples which begin to answer those questions.

Corollary 1 says that if the edge groups are finitely generated then you don’t go up a level, while Corollary 2 gives an example of a graph with infinitely generated edge groups that does go up a level.

Little Facts

1. The $n$^th prime $p_n\approx n\log n$.
2. $\exp (x,y):=x^y\in E_3$.
3. The Gödel encoding of a word of length $n$ on an alphabet $X$ is $\le p_n^{J(n,n)}$, an $E_3$ function.

Theorem 6.7 (from the paper)

Suppose we have $G={\pi }_1(\mathbf{G},\mathrm{\Gamma },T,v_0)$, where $\mathrm{\Gamma }$ is finite. Suppose all the $G_i\in \mathbf{G}$ are finitely generated $E_n$-computable groups, $n\ge 3$. Assume all the identified subgroups are $E_n$-decidable, and all the isomorphisms ${\varphi }_e$ are $E_n$-computable. Then $G$ is $E_{n+1}$-computable.

Corollary 1

Same assumptions as the Theorem 6.7, but also assume that the edge groups are finitely generated. So each edge homomorphism ${\varphi }_{e_{ij}}$ sends a finitely generated subgroup $E_{ij}\le G_i$ to another finitely generated subgroup $E_{ji}\le G_j$. Suppose everything is $E_n$-computable.

Then $G={\pi }_1(\mathbf{G},\mathrm{\Gamma },T,v_0)$ is $E_n$-computable.

Proof

In the algorithm from Theorem 6.7, the potential for unbounded recursion comes from applying the edge homomorphisms repeatedly. We will show that the result of applying the edge homomorphisms repeatedly is bounded by an $E_3$ function.

Let $w$ be a word on $G$ of length $n$. An upper bound on the number of syllables in $w$ is $n$, so let’s say there are $n$ applications of edge homomorphisms.

A homomorphism ${\varphi }_{e_{ij}}$ rewrites generators $x\in X_i$ as words ${\varphi }_{e_{ij}}(x)\in X_j^{\ast }$. As $G-i$ is finitely generated, there is a word ${\varphi }_{e_{ij}}(x)$ of maximum, finite length $k_{ij}$. So a word $w_i\in E_{ij}$ of length $m$ is rewritten to a word $w_j\in E_j$ of length at most $k_{ij}m$.

Because the graph is finite, we can find a greatest $k\in \{k_{ij}\}$. So after reducing all the syllables (assuming that can be done for the input word), the resulting word in $G_0$ has length at most $k^{n}n=L$.

Hence the index of the resulting word is bounded by

$$p_{k^{n}n}^{J(k^{n}n,k^{n}n)},$$

an $E_3$ function, by Fact 2. So recursion on the edge homomorphisms is bounded by an $E_n$ function, and so $G$ is $E_n$-computable.

$◻$

Corollary 2

We will construct a graph of $E_3$-computable groups whose fundamental group is $E_4$-computable.

Let $\mathbf{G}=\{G_0,G_1\}$ be two copies of the free group on two generators, so $G_0=⟨x,y⟩$ and $G_1=⟨a,b⟩$. The graph has a single edge $e$ from $v_0$ to $v_1$, so $\mathrm{\Gamma }=T=(\{v_0,v_1\},\{e,\overline{e}\})$.

Let $E_{01}=⟨\{x^{-n}y{x}^n,n\in \mathbb{N}\}⟩$, $E_{10}=⟨\{a^{-n}b{a}^n,n\in \mathbb{N}\}⟩$. So the edge groups are infinitely generated.

Define

$$\begin{array}{rl}{\varphi }_e(x^{-2n}y{x}^{2n})& =a^{(-2n)!}b{a}^{(2n)!},\\ \\ {\varphi }_{\overline{e}}(a^{-2n-1}b{a}^{2n+1})& =x^{-(2n)!-1}y{x}^{(2n)!+1}.\end{array}$$

Then $G={\pi }_1(\mathbf{G},\mathrm{\Gamma },T,v_0)$ is $E_4$-computable.

Proof

First of all, the homomorphisms are $E_3$-computable because words of the form $a^{-n}b{a}^n$ can be recognised by an $E_3$ function. Hence all the ingredients of the graph of groups are $E_3$-computable.

A word of the form

$$e{a}^{-1}{e}^{-1}\dots x^{-1}e{a}^{-1}{e}^{-1}{x}^{-n}y{x}^{n}ea{e}^{-1}x\dots ea{e}^{-1}$$

will be reduced to a word on $G_0$ whose length is proportional to ${\mathrm{fact}}^{(m)}(n)$, where $m$ is the number of syllables. As $m$ depends on the input, this length can only be computed by unbounded recursion on an $E_3$ function, so is only $E_4$-computable.

Therefore, $G$ is $E_4$-computable. $◻$

Edmund Harris mentioned on Twitter that a Slinky can make a very good model of a Klein bottle. Elin Roberts asked for an explanation, and I was curious too, so I did a bit of rummaging and found my old Slinky. ((it isn’t a real slinky, but what’s the generic name for them? Something like ‘coiled metal extend-o-toy’?))

Once I’d worked out what to do, I recorded a video explaining it:

Today I gave a talk to the department’s Postgrad Forum about Turing completeness, and universal computers. I couldn’t be bothered fiddling with Beamer to create a PDF slideshow, and I wanted to include some Youtube videos in my talk, so I made up my “slides” in HTML with a bit of CSS so it looks nice. MathJax provided LaTeX support for the maths I needed to write. The end result is a long page that I scrolled down as I talked. It seemed to work as well as a proper slideshow would’ve.

Here’s the page, which doesn’t make much sense without the talking to go along with it, and here’s the CSS file I made, in case anyone else fancies doing the same thing.

As part of one of the many jobs I’m doing at the moment for Newcastle University, I’ve written a web-based maths exam system which runs entirely in the browser, with no plugins, and is SCORM compatible. It uses the excellent MathJax for displaying mathematics; there’s a load of clever programming to allow fully randomised, algebraic answers to questions; and exams are written in a fairly easy-to-understand plaintext format.

Here’s an example of an exam written using Numbas, and here’s the file which generated it. The exam should run in modern Firefoxes, Safaris and Chromes, and IEs 8 and 9. Press the ‘Reveal’ button at the top of the page to see the answers to the questions.

We’re still clearing up exactly who owns the copyright to all this and under what terms it can be distributed, so I can’t provide much more material than this, but someone came to visit us yesterday (to give Bill Foster an award for pioneering e-assessment!) and he said that we should be a lot more public with what we’re doing, so that’s what I’m doing.

I’ve been annoying Nathan with these all week.

Why is $D_6$ better for the environment than $Z_6?$ Because it doesn’t commute.

Which bit of Jessop’s does René Descartes like best? The Konica section.

What goes well with a curry and can compute any recursive function? NAND bread.

A colleague claims to know the secret recipe for authentic Coca-Cola. How does he proves this to you without revealing the recipe? With a zero-knowledge protocola.

In the Music Hall of Fame, which guided visit takes you from James Brown up to George Clinton in the quickest time, but is best enjoyed while under the influence? The add-joint funk-tour.

So I was just making my dad’s birthday card. I felt it would benefit from some typography, so I got out a sheet of letter transfers I bought a while ago.

Something immediately leapt out at me: where are all the Es? As anyone who was a bit obsessed with cryptography when they were young knows, the most common letter in English is E, by a long way, and there are hardly any Qs, Xs or Zs. This fact has helped us (and our enemies) win wars.

So, here’s a graph of the relative letter frequencies on the sheet compared to the frequencies in the English corpus (from Simon Singh’s site):

There are about half as many Es as there should be and loads more Qs, Xs and Zs than I will ever use. Now, the sheet’s quite small, so a statistician would do a hypothesis test to see if there is a significant difference between the sheet and the corpus, but I’m not one of those so I’m going to stop here, outraged at WH Smith’s lack of rigour.

I suppose if they’d only put one Z in people would worry about a situation in which they needed to use two Zs, while it isn’t as immediately apparent that there aren’t enough Es to make use of the whole sheet.

The upshot is, I think my dad’s card is going to have to have somebody sleeping in a queue for a xylophone quorum, in order to get the most out of this sheet. My hands are tied by Statistics.

PS It isn’t all bad though – there are twice as many 1s as any of the other non-zero digits, so it at least makes a nod to Benford’s Law.

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\to 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=⟨X⟩$ and $E=⟨Y⟩$, then if we can write each of the elements of $X$ as words in $Y^{\ast }$ 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?

$$⟨a_1,a_2,\dots |R_A⟩[x_1=y_1,x_2=y_2,\dots ]⟨b_1,b_2,\dots |R_B⟩$$

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:

$$(⟨a,b⟩[b=c]⟨c,d|cd=dc⟩)[a=e]⟨e,f⟩$$

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:

$$⟨g_1,g_2,\dots |R_G⟩[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?