14
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Mike Miller May 27 at 20:56
  • 1
    $\begingroup$ @MikeMiller Thanks for pointing that out! (And yes, that was exactly what motivated the solution I produced.) $\endgroup$ – Pace Nielsen May 27 at 21:01
10
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Ah, you solved my notational problem (this may be standard). I incorporated it as well to make my answer more readable. $\endgroup$ – R. van Dobben de Bruyn May 27 at 21:19
  • $\begingroup$ 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... $\endgroup$ – Tim Campion May 27 at 21:20
  • 1
    $\begingroup$ 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. $\endgroup$ – Andrej Bauer May 28 at 6:12
  • 1
    $\begingroup$ @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. $\endgroup$ – Pace Nielsen Sep 3 at 18:51
  • 1
    $\begingroup$ @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). $\endgroup$ – Pace Nielsen Sep 3 at 18:59
9
$\begingroup$

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$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks! It's interesting to see this from a more top-down perspective. $\endgroup$ – Tim Campion May 27 at 21:21
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Tim Campion Sep 4 at 15:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.