Group Cryptography II: Key Transport Protocols

Our previous post described one of Gilbert Baumslag’s contributions to group-theoretic cryptography; this, our final post, describes a second. It is based on a talk given at Cornell by Delaram Kahrobaei on 5/5/2015.  Gilbert was Delaram’s PhD advisor.  Here they are in 2004 on the day she defended.

Delaram and Gilbert

In our previous post we described RSA, which is a way for two parties, Alice and Bob, to establish a common private key which they can used for encrypted communication, from published information without having to meet to exchange keys in advance. Diffie-Hellman public key exchange, published by Diffie and Hellman in their 1976 paper, is alternative method. A prime p\approx 10^{300} and a generator g of \mathbb{Z}_p^* are published. Alice and Bob each choose some secret a,b \in \mathbb{Z}, respectively. Alice sends Bob g^a \mod p, and Bob sends Alice g^b \mod p (publicly). The shared secret key is then K=g^{ab}=(g^a)^b=(g^b)^a, which both Alice and Bob can compute given their information.

The security of this method lies in the difficulty of the following problem: given g, p, g^a \mod p, and g^b \mod p, compute g^{ab} \mod p. One might try to solve this problem by solving for a. Doing so amounts to taking a discrete logarithm, which is considered computationally difficult.

Inspired by the Diffie-Hellman method, Baumslag et al. introduced a key transport protocol that uses a non-abelian group as its platform in their 2006 paper “Designing key transport protocols using combinatorial group theory”. Let G be a finitely presented, non-abelian group with two subgroups A, B\le G such that [a,b]=1 for all a \in A and b \in B. Necessary conditions for the security of the protocol are that these subgroups are such that (1) it is difficult to determine when an arbitrary element g\in G is contained in A or B, and (2) |A| and |B| are large.

To employ the protocol Alice and Bob agree on A,B\le G beforehand. If Alice wants to send a key w\in G to Bob, Alice randomly chooses a_1,a_2\in A and Bob randomly chooses b_1,b_2\in B. The transfer is as follows:

  1. Alice sends a_1 w a_2 to Bob.
  2. Bob sends b_1 (a_1w a_2)b_2=a_1b_1wb_2a_2 to Alice.
  3. Alice sends a_1^{-1}(a_1b_1wb_2a_2) a_2^{-1}=b_1wb_2 to Bob.
  4. Bob computes b_1^{-1}(b_1wb_2)b_2^{-1}=w.

Once the key has been exchanged, messages can be sent using an encryption scheme as described in the previous post.

Some proposed platforms for the key exchange protocol include the groups Aut(F_n), SL_4(\mathbb{Z}), and the surface braid group.

Advertisements
Posted in Uncategorized | Leave a comment

Group Cryptography I: a public key cryptography system using the modular group

0. Original Source

This post is based on

Baumslag, Fine, & Xu, A proposed public key cryptosystem using the modular group, Combinatorial group theory, discrete groups, and number theory, 35–43, Contemp. Math., 421, Amer. Math. Soc., Providence, RI, 2006

The book containing this article is available electronically (requires library subscription).

1. Basics of Public Key Cryptography

Public key cryptography is a method to allow a party to receive encrypted messages without having to exchange keys privately first. Internet commerce platforms are a common application of public key cryptography systems. When a user places an order over the internet, the user needs to send the order and payment information secretly to the vendor without meeting the vendor in person to exchange encryption keys. To achienve this, the vendor makes an encryption method publicly available but keeps the decryption method secret. In the following, we will examine how to design such a system and will look at a specific example.

The idea is simple.  If Bob wishes to receive encrypted messages, he publishes an encryption function f whose inverse is difficult to discover without extra information that Bob has. That way if Alice is sending her message x as f(x), Bob simply applies the inverse function f^{-1} to decrypt the message.

The RSA algorithm is a celebrated example of a public key cryptography system. The following is based on the RSA Wikipedia page.

How Alice sends Bob a secret integer s using RSA:

  • Bob chooses two distinct primes p,q and computes n=pq such that s<nEuler’s totient function \phi(m) calculates the number of units in the ring \mathbb{Z}/m\mathbb{Z} and is a multiplicative function. So Bob can readily compute \phi(n) = \phi(p)\phi(q) = (p-1)(q-1).
  • Bob chooses an integer e such that 1<e<\phi(n) and (e,\phi(n))=1 and lets d = e^{-1} \text{ mod }\phi(n).
  • To encrypt: Bob keeps d a secret and publishes n and e. For n sufficiently large, we know of no fast algorithms that can calculate \phi(n) without knowledge of how to factor n.
  • Alice reads n and e and sends Bob c\equiv s^e \text{ mod } n.
  • As we prove below, Bob can retrieve s as s\equiv c^d \text{ mod } n.

The integers e and n published by Bob together specify the encryption function f: \mathbb{Z}/n\mathbb{Z} \to \mathbb{Z}/n\mathbb{Z} by f(s+n\mathbb{Z}) = s^e + n\mathbb{Z}.  We claim that the decryption function is f^{-1}(s+n\mathbb{Z}) = s^d + n\mathbb{Z}:

Proposition.   The functions f and f^{-1} are inverses. In other words, s^{de} \equiv s \text{ mod n}.

Proof. If s\equiv 0\text{ mod }{p} or s \equiv 0 \mod q, then the result is immediate. If not, by the Chinese remainder theorem, it suffices to check that s\equiv s^{ed}\text{ mod } {p} and s\equiv s^{ed}\text{ mod }{q}. We know that ed-1 is divisible by \phi(pq), so ed-1 = h(p-1)(q-1) for some h. Therefore, s^{ed} \equiv s^{ed-1}s \equiv s^{h(p-1)(q-1)}s \mod p. Since s^{p-1}\equiv 1\text{ mod }{p} by Fermat’s Little Theorem,  we have s^{h(p-1)(q-1)}s\equiv 1^{h(q-1)}s\text{ mod }{p}. The proof for the mod q case is similar.

The key s needs to be less than n since everything is calculated modulo n. In practice, n will large so as to enable relatively long keys and to ensure that it is difficult to factor into a product of primes. Having shared s using RSA, Alice and Bob will then use a system such as AES (“Advanced Encryption Standard”)  to exchange messages with s serving as the key. It partitions the message into 128 bit blocks and performs a succession of permutations and substitutions on each block in a manner dictated by the key.

2. The modular group and its properties

Our cryptosystem will use the modular group: \textup{PSL}_2(\mathbb{Z}) \ \equiv \ \textup{SL}_2(\mathbb{Z}) / \langle \pm I_2 \rangle.

Key properties of this group include:

  • It is finitely presented (see below) and can be faithfully represented in \textup{SL}_2(\mathbb{R}).
  • There is an algorithm that translates between the representations of the elements of this group as words on the generators of this  presentation and matrices.
  • Given a subgroup or a “nice” (a Schreier transversal—see Section 3 below) set of coset representatives for a subgroup, solving the membership problem for that subgroup is relatively easy.

The modular group admits two particularly nice presentations:

\textup{PSL}_2(\mathbb{Z})\cong \langle{x,y|x^2=y^3=1}\rangle = \langle{a,t|a^2=(at)^3=1}\rangle,

where x = \begin{bmatrix} 0 & 1 \\ -1 & 0 \end{bmatrix}, y = \begin{bmatrix} 0 & 1 \\ -1 & -1 \end{bmatrix}, a = \begin{bmatrix} 0 & 1 \\ -1 & 0 \end{bmatrix}, t = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}, and t=xy.

The group \textup{PSL}_2(\mathbb{Z}) can be realized as a free product \mathbb{Z}_2*\mathbb{Z}_3 from the first presentation, so elements can be expressed as word in x,y in a canonical form. Moreover, there is an efficient algorithm so that one can rewrite any matrix in \textup{PSL}_2(\mathbb{Z}) in such a form:

  • Let T = \pm\begin{bmatrix}\alpha & \beta \\ \gamma &\delta \end{bmatrix}
  • One can see that:
    aT = \pm \begin{bmatrix}\gamma & \delta \\ {-\alpha} & {-\beta}\end{bmatrix} = \pm \begin{bmatrix} {-\delta} & {-\gamma} \\ \alpha & \beta \end{bmatrix} \qquad t^kT = \pm\begin{bmatrix}{\alpha+k\gamma} & {\beta+k\delta} \\ \gamma & \delta \end{bmatrix}.
  • By the euclidean algorithm, there exists some string:
    t^{k_1}at^{k_2}\cdots t^{k_n}a^\epsilon T = \pm\begin{bmatrix}\mu & \nu \\ 0 & \eta\end{bmatrix}.

The following example, we see how a 2×2 integer matrix can be transformed into an upper triangular matrix using only left multiplication by some word in a,t:

t^{-2}\begin{bmatrix} {8} & 4 \\ 3 & 1\end{bmatrix} = \begin{bmatrix}2 & 2\\ 3 & 1 \end{bmatrix} \to at^{-2}\begin{bmatrix} 8 & 4 \\ 3 & 1 \end{bmatrix} = \begin{bmatrix} 3 & 1 \\ {-2} & {-2} \end{bmatrix}
\to tat^{-2} \begin{bmatrix} 8 & 4 \\ 3 & 1\end{bmatrix} =\begin{bmatrix} 1 & {-1} \\ {-2} & {-2}\end{bmatrix} \to at^{-2}atat^{-2} = \begin{bmatrix} {-1} & 1 \\ 0 & 4\end{bmatrix}.

In the special case where the initial matrix is in \textup{SL}_2(\mathbb{Z}), we know that \mu\eta = 1, so the resulting matrix has the form \pm \begin{bmatrix}1 &\rho \\ 0 & 1\end{bmatrix} =t^\rho in \textup{PSL}_2(\mathbb{Z}). Hence a and t generate \textup{PSL}_2(\mathbb{Z}).

Another fact we will exploit is that every torsion free subgroup of the free product \textup{PSL}_2(\mathbb{Z})\cong\mathbb{Z}_2*\mathbb{Z}_3 is free.

3. The Reidemeister-Schreier rewriting process

Definition.  Let F be a finitely generated free group and H\le F. Let R be a right transversal of H in F—that is, F is the disjoint union of the cosets Hr, where r \in R. We say that R is a Schreier transversal if whenever w = x_1x_2\ldots x_n is a reduced word of length n on the generators of F and w \in R, then x_1\ldots x_{n-1}\in R.

Lemma. If F is free and H\le F, then H has a Schreier transversal in F.

Proposition (Reidemeister 1932 & Schreier 1927). Every finite index subgroup in a finitely presented group G has a finite presentation which can be explicitly described in terms of a Schreier transversal.

See Combinatorial Group Theory by Lyndon and  Schupp pp. 102-3 for details.

Proposition (Reidemeister Schreier Rewriting). Suppose R is a Schreier transversal for a finite rank free subgroup H of \textup{PSL}_2(\mathbb{Z}). Use R to get free generators W_1,\ldots,W_k for H. Given R, there is a method to express a word w on the generators a,t of \textup{PSL}_2(\mathbb{Z}) as a reduced (and so unique) product of the W_i.

4. Using \textup{PSL}_2(\mathbb{Z}) to make a “public key system”

Baumslag, Fine, & Xu’s innovation is a suggestion for an alternative to AES in the scheme set out in Section 1. They rely on RSA or similar to exchange keys, which in this case is a triple of integers (m,q,t).

Here is a naive way one might use G := \textup{PSL}_2(\mathbb{Z}) to transmit a message written in a plaintext alphabet A with some published assignment \alpha_i\mapsto W_i of letters in the alphabet.

  • Bob chooses and publishes a free subgroup H of G and a set of free generators W_1,\ldots,W_k such that |A|<k. He also publishes an injective map A \to \{ W_1, \ldots, W_k \}.
    assigning the letters in the alphabet to the free generators of H.
  • Alice converts her plaintext message to a string of matrices using the published map A \to \{ W_1, \ldots, W_k \}. Then she multiplies these matrices together to get a single matrix, which she sends to Bob.
  • To decode the message, Bob uses the preceding algorithm to factor the matrix in terms of generators a,t and then uses Reidemeister-Schreier rewriting to get a factorization into the W_i.

Baumslag, Fine, & Xu explain that Yamamura tried a similar encryption scheme, but it was found to be insecure by Grigoriev & Ponomarenko and by Steinwandt. It turns out that techniques using the geometric action of \textup{SL}_2(\mathbb{Z}) on the upper half plane can be exploited to find H. See: A.Yamamura, Public Key cryptosystems using the modular groups, Lecture Notes in Comput. Sci. 1431, 1998, pp. 203-216 for more information.

For a potentially stronger system, Baumslag, Fine, & Xu propose using multiple free subgroups of \textup{PSL}_2(\mathbb{Z}):

  • Bob publishes a collection \{H_i\} of finitely generated free subgroups of \textup{PSL}_2(\mathbb{Z}) with free generating sets W_{i,1}, \ldots W_{i, k_i}. (With overwhelming probability, j randomly chosen integral matrices in \textup{PSL}_2(\mathbb{Z}) generate a free subgroup of rank j, so Bob can choose putative lists of free generators for H_i at random and then verify freeness by checking for torsion freeness, which can done using Stallings folds.) Assume each k_i is much larger than the size k of the plaintext alphabet. This is so that a_j \mapsto W_{i, q+j} for j=1, \ldots, k is an injective map from A = \{a_1, \ldots, a_k \}.)
  • Bob has a Schreier transversal for each H_i, and so can retrieve Schreier generators for H_i.
  • Bob publicly shares these Schreier generators, but keeps the Schreier transversal secret.
  • The integer m specifies the subgroup H_m, and t specifies the lengths of the blocks into which Alice is to partition the plaintext strings, before encoding each block.
  • Alice sends each length-t block as a matrix T made by mapping letter-by-letter to corresponding matrix W_{m, j}, and then multiplying together these matrices.
  • Alice then chooses a “noise” matrix R\in \textup{PSL}_2(\mathbb{Z}). Then she sends the message encrypted as as list of matrices: T_1RT_1,T_2RT_2,\ldots,T_sRT_s. She must choose R in such a way that there is no cancellation between it and its neighbors in the decoding process which we describe next.
  • To decode the message, Bob factors each T_iRT_i into a product of the matrix W_{m, j}, working from left to right by using the Reidemeister-Schreier algorithm. He halts after finding the first t of them (an attacker will not know to stop at this point).

Baumslag, Fine & Xu give a fully worked out example of an encoded and decoded message.

There are methods to calculate transversals from Schreier generators, so just publishing Schreier generators for the desired subgroup does not necessarily make the message secure. Baumslag, Fine, & Xu said it was unknown to them how fast this calculation is.

Posted in Uncategorized | 1 Comment

Direct decompositions of finitely generated torsion-free nilpotent groups

This post is about two talks given by Gretchen Ostheimer given at Cornell on 04/21/2015 in the Berstein Seminar and in the Topology and Geometric Group Theory Seminar. The main class of groups we discuss here are finitely generated torsion-free nilpotent groups, which were introduced in our previous two posts.

Ostheimer classes of groups

Roughly speaking, polycyclic groups represent the cut off point in this hierarchy beyond which Dehn’s problems (the word, conjugacy, and isomorphism problems) become undecidable.  Finitely generated nilpotent groups, being polycyclic, are an interesting class of groups for the development of algorithms.

This post concerns direct decompositions, which we now define.

Definition. Let G be any group.

  • We say that G is directly indecomposable if whenever G = A \times B for subgroups A and B of G, then either A or B is trivial.
  • Let A_1, \dots, A_n be a finite collection of subgroups of G such that each A_i is directly indecomposable and G = A_1 \times \dots \times A_n. We call this a direct decomposition of G.

The following theorem due to Krull, Schmidt, and Remak states that, under certain conditions, direct decompositions are unique up to permutation and isomorphism.

Theorem.  Let G be a group that satisfies both the ascending and descending chain conditions on normal subgroups, then it is uniquely directly decomposable, i.e. suppose that G = A_1 \times \dots \times A_n and G = B_1 \times \dots \times B_m are two direct decompositions of G, then n=m and, possibly after reordering, we have A_i \cong B_i for every i.

Finitely generated abelian groups are an important class of groups for which unique direct decompositions exist:  their structure theorem describes all possible isomorphism classes in terms of a finite number of nonnegative integers (the rank and the invariant factors). Direct decompositions are only unique up to isomorphism. This is obvious when we look at \mathbb{Z}^2. Up to isomorphism, its only nontrivial direct decomposition is \mathbb{Z} \times \mathbb{Z}, but every choice of a basis for \mathbb{Z}^2 gives us a different decomposition.

Finitely generated torsion-free nilpotent groups are not necessarily uniquely directly decomposable, however, as illustrated by the following theorem due to Baumslag.

Theorem. For any m,n > 1 there exists a finitely generated torsion-free nilpotent group G with two direct decompositions

G \;=\; G_1 \times G_2 \times \dots \times G_m \; = \; H_1 \times H_2 \times \dots \times H_n

such that G_i \not\cong H_j for all i and j.

Even though a finitely generated torsion-free nilpotent group is not necessarily uniquely directly decomposable, we can embed it in a larger group (called its rational closure) that has the property. As we will see below, it is constructed by adjoining roots.

Definition. A group G is rational if for every g \in G and m > 0 there exists h \in G such that g = h^m.

More informally, rational groups are groups that contain all their roots. Finitely generated torsion-free nilpotent groups are not necessarily rational, but roots in these groups are unique if they exist. This property allows us to prove the following result.

Theorem. Let G be a finitely generated torsion-free nilpotent group. Then there exists a group \overline{G} such that

  1. G embeds into \overline{G}.
  2. \overline{G} is rational and its roots are unique.
  3. For every h \in \overline{G}, there exists m > 0 such that h^m \in G.

The group \overline{G} is unique up to isomorphism. We call it the rational closure of G. In some sense, it is the smallest rational group into which G embeds. Note that \overline{G} inherits the uniqueness of its roots from G.

As an example, consider the group of integers \mathbb{Z}. It is not rational because there is no square root of 1, which would be 1/2. The rational closure in this case is \mathbb{Q}, which is not a finitely generated group. We observe this behavior in general: the rational closure of a finitely generated group (if it exists) is not necessarily finitely generated.

There is an easy way to construct rational closures using matrices. For any ring R and any \alpha \in R, let \mathrm{Tr}_\alpha(n,R) be the set of all n \times n matices with entries in R of the form

\left( \begin{array}{ccccc} \alpha & * & * & \cdots & * \\ 0 & \alpha & * & \cdots & * \\ 0 & 0 & \alpha & \cdots & * \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & \alpha \end{array} \right).

There exist two maps \log: \mathrm{Tr}_1(n,\mathbb{Q}) \rightarrow \mathrm{Tr}_0(n,\mathbb{Q}) and \exp: \mathrm{Tr}_0(n,\mathbb{Q}) \rightarrow \mathrm{Tr}_1(n,\mathbb{Q}) defined as follows: we can write any element of $latex \mathrm{Tr}_1(n,\mathbb{Q})$  as A = I + U where U \in \mathrm{Tr}_0(n,\mathbb{Q}), and then \log(A) = U - \frac{1}{2} U^2 + \frac{1}{3} U^3 - \dots. For any U \in \mathrm{Tr}_0(n,\mathbb{Q}), we define \exp(U) = I + U + \frac{1}{2!}U^2 + \dots. Both infinite sums are actually  finite since U^n = 0.

Let G be a finitely generated torsion–free nilpotent group. Then G embeds into \mathrm{Tr}_1(n,\mathbb{Z}). If we denote by L the linear subspace of \mathrm{Tr}_0(n,\mathbb{Q}) generated by the set \{ \log(g) : g \in G \}, then \overline{G} = \exp(L). The space \mathrm{Tr}_0(n,\mathbb{Q} is actually a Lie algebra. This extra structure is intrinsically connected to the construction of the rational closure, as illustrated by the following proposition.

Proposition. Let H_1 and H_2 be subsets of \mathrm{Tr}_1(n,\mathbb{Z}) and M_i = \log(H_i) for i = 1,2. Then

  1. H_1 is a rational subgroup of \mathrm{Tr}_1(n,\mathbb{Z}) if and only if M_1 is a Lie subalgebra of \mathrm{Tr}_0(n,\mathbb{Q}).
  2. H_1 and H_2 commute if and only if M_1 and M_2 commute.

As mentioned earlier, rational closures of finitely generated torsion-free nilpotent groups have the unique direct decomposition property. This is surprising in light of the fact that the they original groups did not have this property (as illustrated by Baumslag’s theorem). The following observation might provide some clarification: it is easy to prove that the rational closure of a direct product is isomorphic to the direct product of the rational closures of the factors. That being said, we have

\overline{G} \;=\; \overline{G}_1 \times \overline{G}_2 \times \dots \times \overline{G}_m \; = \; \overline{H}_1 \times \overline{H}_2 \times \dots \times \overline{H}_n.

The factors in these decompositions might not be directly indecomposable (even though the original factors were). Once we decompose them, we will have uniqueness up to permutation and isomorphism.

These are some of the techniques which go into the main result of Baumslag, Miller and Ostheimer in a forthcoming article:

Theorem. There is an algorithm to decide if a given finite generated torsion-free nilpotent group is directly decomposable.

Constructing such an algorithm is challenging because there is no uniqueness of direct decompositions for this class of groups. Without going further into the details of the proof, we make some remarks:

  • finitely generated torsion-free nilpotent groups form a nice class from a computational point of view. There are a lot of algorithm available, e.g. to transform presentations into ones with appropriate properties, to construct intersections of subgroups, etc.
  • the proof uses the existence of algorithms to decompose Lie subalgebras of \mathrm{Tr}_0(n,\mathbb{Q}).
Posted in Uncategorized | Leave a comment

Algorithmic properties of nilpotent and residually torsion-free nilpotent groups

The theme of this post is the word, conjugacy and isomorphism problems in nilpotent and residually torsion-free nilpotent (RTFN) groups.

Definition 0 (lower central series). For group G, define \gamma_1(G)= G and \gamma_{i+1}(G) = [\gamma_{i}(G), G]. The lower central series is

\displaystyle \gamma_1(G) \trianglerighteq \gamma_2(G) \trianglerighteq \cdots,

Definition 1 (nilpotent, RTFN). A group {G} is said to be nilpotent if its lower central series terminates in the trivial group after finitely many steps, i.e. {\gamma_{c+1}(G) = \{1\}} for some {c}. In this case we say the minimal such {c} is the nilpotency class of {G} . We say a group {G} is residually nilpotent if for every {1 \neq g \in G} there exists some normal subgroup {N} not containing {g} and such that {G/N} is nilpotent; if in addition we can always choose N to have torsion-free quotient {G/N}, we say that {G} is residually torsion-free nilpotent (RTFN).  An equivalent definition of residual nilpotence is that

\displaystyle \bigcap_{i=1}^\infty \gamma_i(G) = \{1\},

that is, the intersection of all terms of the lower central series is trivial. Clearly every nilpotent group is residually nilpotent.

An important family of nilpotent groups are the discrete Heisenberg groups. Examples of RTFN groups include free groups (Magnus), right-angled Artin groups (Duchamp and Krob) and the hydra groups (Baumslag and Mikhailov).

The word, conjugacy and isomorphism problems are all solvable for finitely generated nilpotent groups. According to Baumslag, being able to solve the isomorphism problem means that one may think of finitely generated nilpotent groups as completely known. Here is a proof of the solvability of the word problem that is geometric in flavor. First we need the following

Definition 2 (isoperimetric function, Dehn function).   Let {G = \langle S|R \rangle} be finitely presented. We say that a monotone non-decreasing function {f: \mathbb{N} \rightarrow [0,\infty)} is an isoperimetric function if whenever {w \in F(S)} is equal to 1,

\displaystyle \mathrm{Area}(w) \leq f(|w|),

where {|w|} is the length of the word {w} with respect to {S}, and {\mathrm{Area}(w)} is the minimal number of 2-cells in the van Kampen diagram (for the given presentation) with boundary labeled by {w}. The Dehn function for the given presentation is

\displaystyle \mathrm{Dehn}(n) = \max\{\mathrm{Area}(w): w=1 \text{ in } G, |w| \leq n\}.

As is clear in the definition, the Dehn function is an isoperimetric function.

We only care about the asymptotics of the Dehn function, so we consider the equivalence class of functions up to positive scaling. That is, let {f,g:\mathbb{N} \rightarrow [0,\infty)}. Then we say {f \preceq g} if there is {C > 0} such that for all x,

\displaystyle f(x) \leq Cg(Cx)+ Cx + C

Consequently we say {f \sim g} if {f \preceq g} and {g \preceq f} and it is easy to check that {\sim} is an equivalence relation.

The relationship between the Dehn function and the solvability of the word problem is given by:

Theorem 2.  A group {G = \langle S | R \rangle} has solvable word problem if and only if the Dehn function for the group is a recursively computable function.

A sketch of the proof in one direction is that given a word {w} on {S}, we can compute \mathrm{Dehn}(|w|) which gives an upper bound on the number of 2-cells necessary to build a van Kampen diagram for w. We can attempt to construct a van Kampen diagram with w as the boundary label. If we cannot build such a diagram with fewer than \mathrm{Dehn}(|w|) 2-cells, then w was not trivial. Otherwise, we will succeed in constructing a van Kampen diagram, starting from just the boundary loop labelled by w.  Therefore this is a solution to the word problem.

That nilpotent groups have a solvable word problem is therefore a corollary of the following theorem:

Theorem 3 (Gersten, Holt, Riley). Finitely generated nilpotent groups have polynomial isoperimetric functions. In particular, if {G} is finitely generated and nilpotent of class {c}then \textup{Dehn}(n) \preceq n^{c+1}.

Since polynomials are effectively computable, it follows that nilpotent groups have solvable word problem. \Box

Mal’cev was the first to prove that nilpotent groups have solvable word problem. He gave a more algebraic proof. He defined the so-called Mal’cev coordinates (or Mal’cev basis) for a nilpotent group, and this idea was used to prove that the conjugacy and isomorphism problem are solvable (by Blackburn, and Grunewald & Segal respectively). We will not prove these results here.

Using the solvability of the word problem for nilpotent groups we can conclude:

Theorem 4. The word problem is solvable for finitely presented residually nilpotent groups.

Proof: Let {w} be a word on the generators/relations of {G}, a residually nilpotent group, and let {\gamma(G)_i}, {i\geq 1} denote the elements of the lower central series of {G}. By assumption of residual nilpotence each factor group {G/G_i} is finitely presented nilpotent. One can construct an algorithm to solve the word problem as follows:

  1. For each {i \geq 1} rewrite the word {w} on the generators of {G/\gamma_i(G)}.
  2. Each {G/\gamma_i(G)} is nilpotent (of class {i-1}), so run the previously established algorithm to deduce whether {w} is trivial in {G/\gamma_i(G)}.
  3. If {w} is not trivial in {G/\gamma_i(G)} it cannot be trivial in {G}, and the algorithm halts. If w is trivial in {G/\gamma_i(G)}, then increment {i} by 1 and repeat the above steps.

This algorithm eventually halts for any {w} non-trivial, as w survives in some quotient of large enough nilpotency class. The case when the input word is trivial can be handled easily since the list of trivial words is recursively enumerable. Therefore one can run algorithms for both cases in parallel and consequently the word problem for finitely presented residually nilpotent groups is solvable. \Box

Even though the solvability of the word problem carries over from nilpotent to residually nilpotent groups, this is not the case for the conjugacy or isomorphism problem as we show now. In the case of the conjugacy problem this means that there exist two words that are conjugate in {G/\gamma_i(G)} for all{i} but not in {G}.

Theorem 5 (Baumslag, Miller). The conjugacy and isomorphism problems are not solvable for RTFN groups (and hence for residually nilpotent groups and residually finite groups).

Their proof tackles both problems at the same time. The outline is as follows.

  • Show that there is a group having unsolvable word problem, all of whose defining relations are commutators.
  • Use a modified version of the Adyan-Rabin construction to build a family of groups {H_w}, indexed by words {w \in H}, such that {H_w} is free abelian iff {w =_H 1}.
  • Transform the family H_w via a word-conjugacy transform into a family {G_w} with unsolvable conjugacy problem whenever {w \neq_H 1} and show the resulting family is RTFN.
  • Finally, show that if {w =_H 1} then the {G_w} is isomorphic to G_1, so the class {G_w} has unsolvable isomorphism problem and each {G_w} ({w \neq_H 1)} has unsolvable conjugacy problem.

They restrict to RTFN groups in order to avoid torsion relations. This is necessary both for the modified Adyan-Rabin construction and to ensure that the groups {G_w} end up being RTFN. The first step in this outline is to show

Lemma 6. There exists a finitely presented, torsion-free group {H} with unsolvable word problem having a presentation in which all the relators are commutators.

The proof is both cute and short, so we provide it here.

Proof: Let {A = \langle a_1,\ldots,a_n | r_1,\ldots,r_m \rangle} be a group with unsolvable word problem. Consider two copies of the free group F_a = \langle a_1 \dots a_n \rangle and F_b = \langle b_1 \dots b_n \rangle,  and the subgroup {S} of {F_a * F_b} generated by {\{a_1b_1,\ldots,a_nb_n, r_1(a_1, \dots, a_n),\ldots,r_m(a_1, \dots, a_n)\}}. Then {w (a_1, \dots, a_n)\in S} iff {w =_A 1}. Now form the HNN-extension {H} of {F_a * F_b} where the stable letter {p} commutes with {S}, i.e. we take the trivial isomorphism from {S} to itself. Then {p^{-1}w (a_1, \dots, a_n)p = w (a_1, \dots, a_n)} iff {w (a_1, \dots, a_n) \in S} so the word problem for {H} is unsolvable. \Box

Notice that {H} can be presented as,

\displaystyle H = \langle a_1,\ldots,a_n,b_1,\ldots,b_n,p |[p,a_ib_i], [p,r_j(a)] \rangle.

Next Bausmlag & Miller modify the Adyan-Rabin construction to transfer the complexity of the word problem in {H} to the complexity of the isomorphism problem for the family {\{H_w\}_{w \in H}}. We skip writing out all the relations and instead refer to the paper but note that all relations lie in the first derived subgroup.

Lemma 7. Let {H} be a finitely presented group with {n} generators such that the relations are all commutators. For any word {w} in the generators of {H} we can construct the group {H_w} that satisfies the following:

    1. if {w \neq_H 1} then {H} embeds into {H_w} via the inclusion map.
    2. the abelianization of {H_w/[H_w,H_w]} is free abelian.
    3. the normal closure of {w} in {H_w} is {[H_w,H_w]} and so if {w =_H 1} then {H_w} is free abelian on {n+3} generators.

Further, if {H} has unsolvable word problem, then the isomorphism problem for the family {H_w} is unsolvable.

The last assertion follows from the fact that {H_w} is free abelian on {n+3} generators iff {w =_H 1}, so a solution to the isomorphism problem in the family H_w would provide a solution to the word problem in H. The “only if” part of this fact is obtained by using B. and C. of the lemma.

Next we perform the so-called word-conjugacy transform to the groups {H_w}, to produce a new family, G_w. This transform, denoted by {\omega}, is a transformation invented by Miller in his thesis to prove unsolvability of certain algorithmic problems. Its basic property is that the complexity of the word problem in {H} is reflected in the complexity of the conjugacy problem in {\omega(H)}. The transform acts by introducing new generators and relations that only involve conjugation. We note that the word-conjugacy transform preserves the complexity of the isomorphism problem between the families {\{H_w\}} and {\{G_w\}}.

Considering {H_w} from before, one feature of {G_w = \omega(H_w)} is that it is the split extension of two free groups, {F} and {T}, with {T} acting trivially on {F/[F,F]}. The trivial action is ensured by the fact that we started with a group {H} having only commutation relations, and preserved this by only introducing new relations that were commutator-like (i.e. lie in the derived subgroup). Appealing to the lemma that follows, we see that the groups {G_w} are all RTFN.

Lemma 8. If a group {G} is the semidirect product of two RTFN groups {C} and {D}, with {D} acting trivially on {C/[C,C]}, then {G} is RTFN.

Finally the proof is finished by showing that if {w =_H 1} then {G_w}  is isomorphic to {G_1} and this group has solvable conjugacy problem. If {w \neq_H 1} then {G_w} has unsolvable conjugacy problem. This last part is not too technical, but it is lengthy, so we skip it here. It relies on properties of HNN-extensions and lemmas by Britton and Collins.

Baumslag comments that the solvability of the isomorphism problem for nilpotent groups means that they are essentially known. It is therefore perhaps surprising, given the fact that residually nilpotent groups are approximable by nilpotent groups,  that residually nilpotent groups are, in Baumslag’s sense, not essentially known.

Posted in Uncategorized | Leave a comment

Parafree Groups

Today’s post is about groups which have the same nilpotent quotients as free groups. There are many natural questions about how different these groups can be from the free group. This provides a kind of testing ground for how well equivalence of nilpotent quotients might be expected to preserve group properties.

This post is based on the following references:

Baumslag, Parafree Groups, in Infinite groups: geometric, combinatorial and dynamical aspects, 1-14, Progr. Math., 248, Birkhauser, Basel, 2005

Baumslag, Musings on Magnus, The mathematical legacy of Wilhelm Magnus: groups, geometry and special functions (Brooklyn, NY, 1992), 99–106, Contemp. Math., 169, Amer. Math. Soc., Providence, RI, 1994

Definition 0. The lower central series for a group G is defined recursively as \gamma_1(G) = G, \gamma_i(G) = [\gamma_{i-1}(G), G].

Recall that nilpotent groups are those for which \gamma_i(G) = 1 for some finite i.

To any group we can associate a lower central sequence, which is the (ordered) set of quotients G/ \gamma_i(G). The kth element of the lower central sequence is nilpotent of class k. Furthermore, every map from G \to Q where Q is nilpotent of class k will factor through the group G/G^{(k+1)}, as this factor group only imposes the relations (and their consequences) necessary to make G nilpotent of class k.

We might ask how well the lower central sequence captures properties of a group. If G and H are nilpotent groups and have the same lower central sequence, then, in particular, they are isomorphic groups: because nilpotent groups appear as elements of their lower central sequences, the properties of nilpotent groups are completely described by the properties of elements of their lower central sequence.

We can’t expect to get full information about our group if there are elements which no nilpotent quotients can see. (That is, if there are non-trivial elements in \cap_{i=1}^{\infty}\gamma_i(G).)  Consider, for example, when G a perfect group. Then \gamma_2(G) = [G,G] = G and so G/\gamma_i(G) = \{1\} for all i. Therefore a perfect group has the same set of quotients as the trivial group. Taking nilpotent quotients  has thrown out all of our group elements.

In what follows, we will restrict our attention to groups that are residually nilpotent.

Definition 1. A group G is residually nilpotent if \cap_{i \in \mathbb{N}} \gamma_i(N) = \{1\}.

Definition 2. A group G is residually nilpotent if for every g \neq 1 there is some nilpotent quotient of G which does not trivialize g.

By the facts about the lower central sequence above, these two definitions are equivalent. These are precisely the groups in which all non-trivial elements eventually appear in the lower central sequence.

Proposition 1. The free group F_2 = \langle a, b \rangle is residually nilpotent.

Proof: Let R be the the ring of formal powers series on the non-commuting indeterminants x and y with rational coefficients. Every element of R can be written as r= r_0 + r_1 + \dots where r_i is the sum of all degree i terms. There is a map F_2 \to R which sends a \to 1+ x and b \to 1 + y. These elements are units in R with inverses given by (1 -x + x^2 -x^3+...) and (1 -y + y^2 -y^3+...). The elements (1+x) and (1+y) freely  generate a subgroup of rank 2 amoung the units of R. Conveniently, we can put a metric on the units of R which is given by d(1+ r_n + r_{n+1}+ \dots,1) = 1/n where n is the degree of the first non-zero term r_n. It is an easy induction argument to show that if f \in \gamma_k(F) that the image is f = 1 + \phi and \phi_1 = \phi_2= \dots =\phi_{k-1} = 0. This implies that the intersection of \gamma_i(G) over all i is just the identity. \Box

Now that we have a little more comfort with residually nilpotent groups, we can return to the question of how much we can say about groups which have the same lower central sequences. Free groups are a natural beginning, and the following question of Hannah Neumann is the starting point for this study:

Question 1. Are the free groups characterised by their lower central sequence? That is, if $latexG$ is a finitely generated group with the same lower central sequence as the free group F, then is G a free group?

Definition 3. A group G is parafree if it is residually nilpotent and if there is some free group F such that G / \gamma_i(G) = F/\gamma_i(F) for every i.

The parafree groups are those for which nilpotent quotients are enough to approximate the group, but for which nilpotent quotients aren’t enough to distinguish the group from a free group. Clearly free groups are an example, but there are others too. The first non-free example was the following, discovered by Baumslag.

Proposition 2. The group G = \langle a, b ,c | a = [c, a][c, b] \rangle is a non-free parafree group.

We’ll show that this group has the same lower central sequence as \langle b,c \rangle, but first we’ll need to recall a definition and a lemma:

Definition 4. The element g \in G is called non-generating if it is contained in the intersection of all maximal subgroups of G. Equivalently, if g ever appears in a presentation as a generator for G, it can be removed from the generating set, without changing the group. The set of all non-generating elements for G is actually a subgroup of G, called the Frattini subgroup.

Lemma 1. In the nilpotent group G, the Frattini subgroup contains the derived subgroup \gamma_2(G) = G^{(1)}.

Proof that G is free. Clearly

\langle a \gamma_k,~ b \gamma_k, ~ c \gamma_k \rangle = \langle a^{-1}C\gamma_k, ~ b\gamma_k, ~ c\gamma_k, ~ C\gamma_k ~|~ C\gamma_k=[c,C(a^{-1}C)^{-1}][c,b]\gamma_k\rangle,

where the equality is via a Tietze transformation and C is shorthand for [c,a][c,b].  By the lemma above, since we are in a nilpotent group, we can remove [c, a][c,b]\gamma_k from the generating set. This also removes the relator. Therefore the set a^{-1}[c, a][c, b] \gamma_k, b\gamma_k, c\gamma_k is a generating set for the free rank 3 nilpotent group of nilpotence class k. There is a map from F_3 / F_3^{(k)} \to F_2 / F_2^{(k)} which just kills the first generator.  This means that trivializing a^{-1}[c, a][c, b]\gamma_k(G) maps us to the free rank 2 nilpotent group of class k. On the other hand, G/ \gamma_k(G) is the freest nilpotent group of class k which satisfies that a^{-1}[c, a][c, b] =1. Therefore these two groups are isomorphic.

If G was a free group, it would be the group F_2, as its nilpotent quotients have rank 2. However, notice that we can express G as an HNN extension with stable letter b.

\langle a, c, b | c^b = c[a,c]a\rangle

By the method of Magnus, this implies that there is a short exact sequence

N \hookrightarrow G \to \mathbb{Z}

where N is the group \langle a_i, c_i | c_{i+1} = a_i[c_i,a_i]\rangle, and a_i = a^{b^{i}},~~ c_i = c^{b^{i}}. From the abelianization, we see that if G was free that the element a had to be trivial in G. However from this decomposition, we have that the element a= a_0 maps non-trivially into G\Box

(The hardest part of proving that a group is parafree seems to almost always be proving residual nilpotence, which we skip here.)

Definition 5. The rank of a parafree group G is defined to be the minimum number of generators of the abelianization G/G^{(1)}. In other words, a parafree group has the same set of nilpotent quotients as some free group F. The rank of G is defined to be the rank of F.

For example, the group above has rank 2.

Proposition 3. If G is an infinite, rank-1 parafree group, then it is isomorphic to \mathbb{Z}.

Proof. Indeed, this follows from the fact that the lower central sequence stabilized immediately. By the residual nilpotence of G, if all non-trivial elements of G had to remain non-trivial in some element of the lower central sequence, then in fact the map G \to G/G^{(1)} couldn’t have any kernel, so it was an isomorphism, and G/G^{(1)} was by assumption isomorphic to \mathbb{Z}\Box

Magnus proved that a rank n parafree group which can be generated with an n element set is in fact a free group. This result was later generalized by Bridson and Reid, who showed that if a parafree group has rank r\geq 2 that there is some r element subset of its generating set that generates F_r as a subgroup of G.

The following is an important tool for finding parafree groups:

Theorem 1 (Stallings). If h: A \to B is a homomorphism which induces an isomorphism on the abelianizations (ie H_1(A) and H_1(B) are isomorphic), then if H_2(A) surjects onto H_2(B) then for all i, A/ \gamma_i(A) \cong B/\gamma_i(B). In particular, this implies that if there is a homomorphism F_n \to G that induces an isomorphism on their abelianizations, and G has trivial second homology, then if G is residually nilpotent, it is parafree.

The second homology of a group G, H_2(G; \mathbb{Z}), which is often just abbreviated to H_2(G), is the second homology of an Eilenberg-Maclane space for G. Another interpretation of the second homology of a group comes from the Hopf isomorphism, which says that H_2(F/R) = R \cap [F,F] / [R,F] where F is a free group, and is a normal subgroup. We can see clearly from this equation that free groups have trivial second homology. It’s also easy to see that this holds in our example above. Indeed, the index sum of the a must be zero to intersect with [F,F] and this happens exactly when the index sum of the relator r is equal to zero, so we can express it as an element of [F,R]. Therefore Stallings’ Theorem provides another proof for our example being parafree (once residual nilpotence is verified).

Next we consider some properties of free groups that also hold amoung parafree groups:

Theorem 2. If G is a (para)free group, then G embeds into the units of a power series ring over \mathbb{Z}.

Theorem 3. If G is a (para)free group, then G embeds into a (para)free group of rank 2.

Theorem 4 (Bridson and Reid). If G is a (para)free group, then every finitely generated normal subgroup of G has finite index.

The following is a property of free groups which is conjectured to hold for parafree groups:

Conjecture 1 (Baumslag’s Parafree Conjecture). If G is a finitely generated parafree group, then  H_2(G; \mathbb{Z}) = 0, that is, the second homology of an Eilenberg-Maclane space for G will be trivial.

This conjecture is related to a  number of topological questions. It is related to the length of 3-manifold groups, that is, the ordinal at which the lower central series of a 3-manifold grous stabilizes. It is also related to Whitehead’s Asphericity Conjecture, that every connected subcomplex of a 2 dimensional aspherical CW complex is also aspherical (it has contractible universal covering space).

Although this conjecture has not been resolved, Bridson and Reid have recently shown that having the same set of nilpotent quotients does not imply having the same second homology. They have constructed an example of two finitely presented residually torsion free nilpotent groups with the same set of quotients for which one has finitely generated second homology and the other has infinitely generated second homology.

Of course, not all properties of free groups hold in the case of free groups. For example,

Theorem 5 (Baumslag). Parafree groups are not classified by their rank. In particular, there are continuum many parafree groups.

Similarly, there are many properties of free groups for which it is not yet known whether or not they hold amoung all parafree groups.

Open Questions:

  • Are parafree groups linear?
  • Are parafree groups hyperbolic?
  • Suppose that G is a finitely generated, residually finite group with the same finite images as a free group. Is G parafree?
Posted in Uncategorized | Leave a comment

More about wreath products and finiteness

In this post, we continue to talk about wreath products. First we will prove part 3 of the theorem stated in our previous post, and use it to show that being finitely presented is undecidable, and then we quickly introduce finiteness properties (FP_n and F_n) discussed from the previous Berstein blog, and talk about how wreath products behave with respect to those (the answer uncovers no surprises).

The material in this post is based on the three papers “Wreath products and finitely presented groups” by Baumslag, “On the absence of cohomological finiteness in wreath products” by Baumslag, Bridson and Gruenberg, and “Embedding wreath-like products in finitely presented groups. I” by Baumslag.

Recall the theorem we started proving last time:

Theorem. Let G and H be groups and W = G \wr H. Then,

  1. W is finitely generated if and only if both G and H are finitely generated.
  2. If W is finitely generated, then W is recursively presentable if and only if G and H are recursively presentable and if G \neq 1, then either H has solvable word problem or G is abelian.
  3. W is finitely presented if and only if G and H are finitely presented and either G = 1 or H is finite.

Proof of part 3.
Clearly, if G is the trivial group and H is finitely presented, W = H is finitely presented.

If \langle X \mid R \rangle is a finite presentation for G and H is finite, with presentation H = \langle Y \mid S \rangle, the presentation W = \langle X \cup Y \mid R \cup S \cup \{[x_1, x_2^w] \mid x_1, x_2 \in X, w \in V^-\}\rangle (where V^- is the set of non-identity elements in H) from the previous post is a finite presentation for W.

If W = K \rtimes H, where K = \bigoplus_{h \in H}h^{-1}Gh, is finitely presented, then G and H are finitely generated, and adding relations setting all the (finitely many) generators of G to 1 gives us a finite presentation for H (we can do this since K is a normal subgroup, and hence, the normal closure of these new relations is contained in K).

By Lemma 1. below (which is the content of the theorem), either H is finite, or G is trivial. If G is trivial, it is obviously finitely presented. If H is finite, K has finite index in W, and hence is finitely presented, and since K is the direct sum of finitely many copies of G, G is finitely presented.

Lemma 1. If G \neq 1 and H is infinite, then W = G \wr H is not finitely presented.
To prove this, we will use a generalization of the wreath product: instead making all the different conjugacy classes h^{-1}Gh commute, we only want a few of them to commute.

Lemma 2. Let G and H be groups, H infinite and S \subseteq H finite. Let T be the relation T = \{(s_1h, s_2h) \mid s_1, s_2 \in S, h \in H\}. Then there is a group G \wr^S H (this notation is not standard) generated by G and H such that

  1. h_1^{-1}Gh_1 \cap h_2^{-1}Gh_2 = \{1\} for h_1, h_2 \in H, h_1 \neq h_2,
  2. h_1^{-1}Gh_1 and h_2^{-1}Gh_2 commute if and only if (h_1, h_2) \in T and h_1 \neq h_2.

The actual construction of this group is a bit technical (see G. Baumslag, “Wreath products and finitely presented groups”), so we leave it out.

Lemma 3. There is an h_0 \in H such that [G, h_0^{-1}Gh_0] \neq 1 (in G \wr^S H).

With this, we can finish the proof of Lemma 1.

Proof of Lemma 1.
Assume that W is finitely presented, so we can find presentations \langle X \mid R\rangle and \langle Y \mid S \rangle for G and H with X and Y finite. As in the previous post, W = \langle X \cup Y \mid R \cup S \cup \{[x_1, x_2^w] \mid x_1, x_2 \in X, w \in V^-\}\rangle, where V^- is the set of all words on Y that do not reduce to the identity in H.

According to a theorem by B.H. Neumann, we can find a presentation W = \langle X \cup Y \mid \hat R \rangle, where \hat R \subseteq R \cup S \cup \{[x_1, x_2^w] \mid x_1, x_2 \in X, w \in V^-\} is finite. Now, \hat R \cap \{[x_1, x_2^w] \mid x_1, x_2 \in X, w \in V^- = \{[x_{i_1},x_{j_1}^{w_1}], \ldots, [x_{i_n},x_{j_n}^{w_n}]\} is a finite (possibly empty) set, and let S = \{w_1, \ldots, w_n\} and W_0 = G\wr^SH.

Then, W_0 satisfies every relation in W. But by Lemma 2, there is an h_0 \neq 1 in W such that [G,h_0^{-1}Gh_0] \neq 1 in W_0, while [G,h_0^{-1}Gh_0] = 1 in W (so there are relations in W that let us reduce every element in [G,h_0^{-1}Gh_0] to the identity), a contradiction.

This gives a proof that being finitely presented is undecidable:

Corollary. There is no algorithm that decides if a given recursively presentable group is finitely presented or not.

Proof.
Assume that there was such an algorithm. Then, we could decide if a finitely presented group G is trivial: form W = G \wr \mathbb{Z} (which is recursively presentable by part 2 of the theorem, since \mathbb{Z} has solvable word problem), and check whether it’s finitely presented. But we saw long ago that there is no algorithm for deciding if a finitely presented group is trivial.

Now, we move on to some other finiteness properties. See the previous Berstein seminar blog (mainly here and here) for a more thorough discussion of them. A (geometric) generalization of the finiteness properties of being finitely generated or finitely presented is given by considering Eilenber–Maclane spaces:

Definition. An Eilenberg–Maclane space for a group G is a connected CW-complex X with fundamental group G and all other homotopy groups trivial.

Definition. A group is of type F_n if it has an Eilenberg–Maclane space with finite n-skeleton.

Being of type F_1 is equivalent to being finitely generated, and being of type F_2 is equivalent to being finitely presented.

A similar (but algebraic) notion of finiteness is:

Definition. A group G is of type FP_n if there is a projective resolution P_n \to P_{n-1} \to \dotsb \to P_1 \to P_0 \to \mathbb{Z} \to 0 where P_k are finitely generated \mathbb{Z} G-modules.

The question then is, how do these two measures of the finiteness of a group compare to each others? Part of the answer is:

Proposition. Every group of type F_n is of type FP_n.

For the other part, R. Bieri and R. Strebel, proved in 1980 that every group of type finitely generated, metabelian group of type FP_2 is of type F_2 (that is, is finitely presented) (“Valuations and finitely presented metabelian groups.”).

However, in 1996, M. Bestvina and N. Brady (“Morse theory and finiteness properties of groups.”) found groups that were of type FP_2 but not F_2. Their counterexamples use Morse theory for cubical complexes, and it is known that many more familiar algebraic constructions (like HNN extensions and free products with amalgamation for example), cannot produce counterexamples (groups of type FP_2 that are not of type F_2). The following theorem (very similar to the theorem we’ve spent most of these last two posts proving) has as a corollary that wreath products will also not produce counterexamples.

Theorem. G \wr H, with G \neq 1, is of type FP_2, if and only if H is finite and G is of type FP_2.

Corollary. If G \wr H (with G \neq 1) is of type FP_2, but not F_2, then G is of type FP_2 but not F_2.

Proof.
By the above theorem, G is of type FP_2, and by part 3 of the main theorem, if G was finitely presented, G \wr H would be, too.

Posted in Uncategorized | Leave a comment

Wreath products and finiteness

In this post and the next, we consider the wreath product of two groups (in a previous post,  we saw that the wreath product \mathbb{Z} \wr \mathbb{Z} was not finitely presented) and see some of how it relates to finiteness properties and decidability. In particular, we will see exactly when a wreath product is finitely presented, finitely generated and FP_2 (which was discussed in the previous Berstein blog), and as corollary show that it is impossible to decide whether a (recursively presentable) group is finitely presented or not.

The material in this post is based on the paper “Embedding wreath-like products in finitely presented groups. I” by Gilbert Baumslag.

We give two characterisations, which are easily seen to be equivalent, each of which sheds some light on what the wreath product is.

Definition. Let G and H be groups. The (restricted) wreath product G \wr H is a group W such that:

  1. W is generated by G and H,
  2. the subgroup K generated by all conjugates h^{-1}G h for h \in H is the direct sum \bigoplus_{h \in H}h^{-1} G h.

Definition. Let G and H be groups, and for each h \in H, let G_h be an isomorphic copy of G, and K = \bigoplus_{h \in H}G_h. Let H act on K by h \cdot g_{h_0} = g_{h_0h^{-1}}. Then we define the wreath product G \wr H to be the semidirect product K \rtimes H.

A third characterisation of the wreath product is by a presentation:

Lemma. If G = \langle X \mid R \rangle, H = \langle Y \mid S \rangle, and we let V be the set of all words on Y, and V^- be the set of all words on Y that do not reduce to the identity (in H), then:

  1. G \wr H = \langle X \cup Y \mid R \cup S \cup \{[x_1, x_2^w] \mid x_1, x_2 \in X, w \in V\}\rangle, if G is abelian,
  2. G \wr H = \langle X \cup Y \mid R \cup S \cup \{[x_1, x_2^w] \mid x_1, x_2 \in X, w \in V^-\}\rangle, if G is not abelian.

Of course, the second presentation works even if G is abelian, the reason we want to separate them is part 2 of the following theorem describing how the wreath product interacts with different degrees of finiteness.

Theorem. Let G and H be groups and W = G \wr H. Then,

  1. W is finitely generated if and only if both G and H are finitely generated.
  2. If W is finitely generated, then W is recursively presentable if and only if G and H are recursively presentable and if G \neq 1, then either H has solvable word problem or G is abelian.
  3. W is finitely presented if and only if G and H are finitely presented and either G = 1 or H is finite.

We will prove parts 1 and 2 in this post, and leave part 3 for the next post.

Proof of part 1.
If G and H are finitely generated, by X and Y, respectively, then since W is generated by X \cup Y it follows that W is also finitely generated.

On the other hand, if W is finitely generated, and G is generated by X and H by Y, then W is generated by X' \cup Y', with X' \subseteq X, Y' \subseteq Y finite.

Since W = K \rtimes H, there is a surjection \phi : W \to H that is the identity on H, so Y' = \phi(Y') is a finite generating set for H.

Finally, since X' \cup Y' generate W, for any g \in G, we have g = x_1y_1\dotsb x_ny_n, where x_i \in X' and y_i \in Y'. Since the different conjugacy classes commute, this reduces to a product using only elements of X', so X' generates G.

For part 2, we need a lemma about recursively presentable groups, similar to a theorem by B.H. Neumann about finitely presented groups.

Lemma. If Q is a recursively presentable group and P \le Q is finitely generated subgroup, then for any finite generating set X for P, there is a presentation \langle X \mid R \rangle of P where R is a recursively enumerable set.

Proof
We can write Q = F/R, where F is a free group (on a possibly countable set of generators), and R a recursively enumerable subset of F. The elements of P form a recursively enumerable set S, and hence, the set of relations, S \cap R is recursively enumerable.

Proof of part 2.
Let G = \langle X\mid R\rangle and H = \langle Y\mid S\rangle be recursive presentations of G and H. By part 1 of the Theorem and the lemma, we can assume that X and Y are finite.

The set V of all words on Y is clearly recursively enumerable, so if G is abelian, \langle X \cup Y \mid R \cup S \cup \{[x_1, x_2^w] \mid x_1, x_2 \in X, w \in V\}\rangle is a recursive presentation for W.

Further, if H has solvable word problem, the set V^- of all non-identity words on Y is recursively enumerable since for each word in V, we can check if a word w equals the identity in H or not. So \langle X \cup Y \mid R \cup S \cup \{[x_1, x_2^w] \mid x_1, x_2 \in X, w \in V\}\rangle is a recursive presentation of W.

On the other hand, if W is recursively presentable, by the lemma, we can find presentations G = \langle X\mid R\rangle and H = \langle Y\mid S\rangle with X and Y finite and R and S recursively enumerable, so G and H are recursively presentable. Again, by the lemma, we can find find a recursive presentation W = \langle X \cup Y \mid Z\rangle. We will assume that G is not abelian, and use this to solve the word problem in H.

There are x_1, x_2 \in G with [x_1, x_2] \neq 1. Let Z^+ be the normal closure of Z in W. Z^+ is recursively enumerable, and does not contain [x_1, x_2] since x_1 and x_2 do not commute, but does contain [x_1,x_2^w] for every word w on Y which does not reduce to the identity in W. Now, let C = \{[x_1,x_2^w] \mid w \in V\}. It is recursively enumerable, so C \cap Z^+ is recursively enumerable, and the element [x_1, x_2^w] begin with x_1^{-1} w^{-1}x_2^{-1} for w which does not reduce to the identity in W (and hence H). So by generating the elements of C \cap Z^+ and reading off the part between x_1^{-1} and x_2^{-1}, we get a way to recursively enumerate the elements of H that do not equal the identity. Since we can generate all identity words in H from S, this solves the word problem in H.

Posted in Uncategorized | Leave a comment