# Is every finitely-presentable group a finite colimit of copies of $F_2$?

Let $$F_n$$ be the free group on $$n$$ generators. Of course, every finitely-presentable group $$G$$ is a finite colimit of copies of $$F_n$$, where $$n$$ is allowed to vary. But is $$G$$ a finite colimit of copies of $$F_2$$?

Of course, because $$F_{2n}$$ is a finite coproduct of copies of $$F_2$$, we have that any finitely-presentable group $$G$$ is a finite colimit of finite colimits of copies of $$F_2$$ -- a "2-fold" finite colimit of copies of $$F_2$$. But I'm curious about the 1-fold case.

To make the question a bit more concrete, let's unwind what it means to be a finite colimit of copies of $$F_2$$:

Let $$G$$ be a group. Then $$G$$ is a finite colimit of copies of copies of $$F_2$$ if and only if $$G$$ admits a presentation of the following description:

• There are $$2n$$ generators coming in pairs $$x_1,y_1, \dots x_n, y_n$$;

• There is a finite set of generating relations, each of the form $$w(x_i,y_i)=v(x_j,y_j)$$, where $$w,v$$ are group words and $$1 \leq i \leq j \leq n$$.

So for example, $$x_1y_1^2x_1^{-1} = y_2^{-1}x_2$$ is a permissible generating relation (with $$i=1,j=2$$) but $$x_1 x_2 = x_3$$ is not a permissible generating relation because only 2 different subscripts are allowed to appear in a permissible generating relation. So my question is:

Question: Let $$G$$ be a finitely-presented group.

• Is $$G$$ a finite colimit of copies of $$F_2$$?

• Equivalently, does $$G$$ admit a presentation of the above form?

Edit:

The form of the presentation can be constrained even further, to look like this:

• There is a finite set of generating relations, coming in pairs each of the form $$x_i = w(x_j,y_j)$$, $$y_i=v(x_j,y_j)$$, where $$w,v$$ are group words and $$1 \leq i, j \leq n$$.

Other variations are possible too; I'm not sure what the most convenient description to work with might be.

• Here is how to present your illegal relation $x_1 x_2 x_3 = 1$ in a legal way. That group has $2n$-presentation $\langle x_1, y_1, x_2, y_2, x_3, y_3 \mid x_1 x_2 x_3, y_1, y_2, y_3 \rangle$. To make $x_1 x_2 x_3$ into a legal relation, introduce $x_4,y_4, x_5, y_5$, and relations $x_1 = x_4, x_2 = y_4$, $x_5 = x_4 y_4$, $x_3 = y_3$; then the legal presentation is $$\langle x_1, \cdots, y_5 \mid x_1 = x_4, x_2 = y_4, x_3 = y_3, y_1 = y_2 = y_3 = 1, x_4 y_4 = x_5\rangle.$$ This seems to lead to the algorithm in Pace Nielsen's answer. – Mike Miller May 27 at 20:56
• @MikeMiller Thanks for pointing that out! (And yes, that was exactly what motivated the solution I produced.) – Pace Nielsen May 27 at 21:01

I believe the answer is yes. Assume, by way of contradiction, that some finitely presented group cannot be so expressed. Then we can choose such a group $$G$$ where for any generating set of the form $$x_1,y_1, x_2,y_2,\ldots, x_n,y_n$$ the number of non-permissible relations needed to define $$G$$ (together with some finite number of permissible relations) is minimized; say those non-permissible relations are $$w_1=1, w_2=1,\ldots, w_m=1$$. Write $$w_1=z_1z_2\cdots z_p$$ where each $$z_j\in \{x_1^{\pm 1},y_1^{\pm 1},\ldots, x_n^{\pm 1},y_n^{\pm 1}\}$$, where we may also assume that $$p$$ has been minimized. Note that since $$w_1=1$$ is not permissible, we must have $$p\geq 3$$.

Add new generators $$x_{n+1},y_{n+1},x_{n+2},y_{n+2}$$. The relations $$x_{n+1}=z_{p}$$, $$y_{n+1}=z_{p-1}$$, $$x_{n+2}y_{n+2}=1$$ are permissible. The relation $$x_{n+2}y_{n+1}x_{n+1}=1$$ is also permissible (since it is equivalent to $$x_{n+2}=x_{n+1}^{-1}y_{n+1}^{-1}$$). Asserting these relations still gives us the same group (since our new relations merely tell us how to write the new generators in terms of the old ones). The relation $$w_1=1$$ is equivalent to $$z_1z_2\cdots z_{p-2}y_{n+2}=1$$, but it is now shorter, a contradiction.

• Ah, you solved my notational problem (this may be standard). I incorporated it as well to make my answer more readable. – R. van Dobben de Bruyn May 27 at 21:19
• Thanks! Incidentally, I think this algorithm generalizes to show that for any variety (in the sense of universal algebra) with all operations of arity $\leq n$, any finitely-presented algebra is a finite colimit of copies of the free algebra on $n$ generators. I wonder if this is known and written somewhere... – Tim Campion May 27 at 21:20
• If only you did not unecessarily say "proof by contradiction", you would have an algorithm in your hands for converting any presentation to a permissible one. – Andrej Bauer May 28 at 6:12
• @TimCampion Semigroups are even easier. Suppose you have a relation $x_1 x_2 \cdots x_m = y_1 y_2 \cdots y_n$. Create new elements $z_1,z_2,\ldots, z_{m-1}$ and $w_1,w_2,\ldots, w_{n-1}$ and add the relations $z_1=x_1x_2$, $z_2=z_1x_3$, $z_3=z_2x_4$, and so forth up to $z_{m-1}=z_{m-2}x_m$. Do the something similar for the $w$'s. This defines the $z$ and $w$ variables in terms of previous generators. Finally, asserting $z_{m-1}=w_{n-1}$ gives the original relation. – Pace Nielsen Sep 3 at 18:51
• @TimCampion The word problem for groups is not decidable. In particular, one cannot tell whether a group word is trivial (i.e., equal to $1$). But, given any finite presentation, the algorithm can still easily be made effective. Rather than working by contradiction, one instead just reduces word lengths (ala what Andrej Bauer said earlier). – Pace Nielsen Sep 3 at 18:59

Here's a pretty direct way to do this. Choose any presentation by generators $$x_1,\ldots,x_n$$ and relations $$r_1,\ldots,r_m$$; say $$r_i = z_{i,1} \cdots z_{i,k}$$ for $$z_{i,1},\ldots,z_{i,k} \in \{x_1^{\pm 1}, \ldots, x_n^{\pm 1}\}$$. Firstly, we may assume all $$r_i$$ have length $$k = 3$$: the new variables $$x_{i,j} = z_{i,1} \cdots z_{i,j}$$ for $$0 \leq j \leq k$$ are subject only to the relations \begin{align*} x_{i,0} = e = x_{i,k}, & & & & & & x_{i,j} = x_{i,j-1}z_{i,j} & & (1 \leq j \leq k). \end{align*} If $$k < 3$$, we can eliminate the variable $$z_{i,1}$$ at the expense of replacing all $$z_{i,1}^{\pm 1}$$ by $$z_{i,2}^{\mp 1}$$ (if $$k = 2$$) or $$e$$ (if $$k = 1$$) in the other relations, so we may assume all $$r_i$$ have length exactly $$3$$. Then introduce new variables $$x_{n+1},\ldots,x_{n+m}$$ as well as variables $$y_1,\ldots,y_{n+m}$$, subject to the relations \begin{align*} x_{n+i} &= z_{i,1},& & 1 \leq i \leq m,\\ y_i &= e & & 1 \leq i \leq n,\\ y_{n+i} &= z_{i,2}, & & 1 \leq i \leq m,\\ x_{n+i}y_{n+i} &= z_{i,3}^{-1}, & & 1 \leq i \leq m,\\ \end{align*} This gives a presentation of the desired form. $$\square$$

• Thanks! It's interesting to see this from a more top-down perspective. – Tim Campion May 27 at 21:21

Ok, I think the above answers have pointed the way to a proof of the obvious generalization:

Theorem: Consider a variety $$V$$ (in the sense of universal algebra) generated by operations of arity bounded by some $$N \in \mathbb N$$, and let $$\mathcal C$$ be the category of $$V$$-algebras and homomorphisms. Let $$F$$ be the free algebra on $$N$$ generators. Then every finitely-presented $$A \in \mathcal C$$ is a finite colimit of copies of $$F$$.

Proof: By using dummy variables, we may assume that every basic operation in $$V$$ is of arity exactly $$N$$. As described in the case of groups in the Question, we are looking for a presentation of $$A$$ by generators $$(x_{11}, \dots, x_{1N},\dots, x_{n1}, \dots, x_{nN})$$ modulo "permissible" relations $$w(x_{i 1}, \dots x_{i N}) = v(x_{j 1},\dots, x_{j N})$$, were $$w, v$$ are (possibly composite) operations in the variety $$V$$.

As in Pace Nielsen's answer, it will suffice to show that if $$w(x_{11},\dots, x_{nN}) = v(x_{11},\dots,x_{nN})$$ is a non-permissible relation, we can, after adding more variables $$(x_{n+1,1},\dots, x_{n+1,N})$$, replace it with relations using only shorter words (in the sense that the total number of basic operations of which each word is composed is smaller -- the base case is a word $$x_{ij}$$ composed of no operations; note that a relation $$x_{ij} = x_{kl}$$ is permissible) and a relation of the form $$f(x_{n+1,1},\dots, x_{n+1,N}) = v(x_{11},\dots, x_{nN})$$.

To this end, we may write $$w(x_{11},\dots, x_{nN}) = f(w_1(x_{11},\dots,x_{nN}), \dots, w_N(x_{11},\dots,x_{nN}))$$ where $$f$$ is a basic operation and the $$w_i$$'s are shorter words. We impose the relations $$x_{n+1,i} = w_i(x_{11},\dots,x_{nN})$$ (which use only shorter words) along with the relation $$f(x_{n+1,1},\dots, x_{n+1,N}) = v(x_{11},\dots, x_{nN})$$, as desired.

• I think the argument generalizes, with basically just notational changes, to the case of a many-sorted variety with finitely many sorts (such as the 2-sorted variety of (ring, module) pairs -- showing that any such pair which is finitely presentable is a finite colimit of copies of $\mathbb Z[x,y]$ acting on itself). – Tim Campion Sep 4 at 15:19