## Hot answers tagged presentations-of-groups

16

Not only these subgroups are finitely presented, they are all finite free products of cyclic groups; most of them (for sufficiently large $n$) are actually free of finite rank (once congruence subgroup contains no elements of order 2 and 3). For instance, you can easily check that $\Gamma(n)$ is torsion-free for all $n\ge 2$ by looking at traces for $n\ge 3$ ...

11

An algorithm for computing the hyperbolic "thinness" constant $\delta$ is described in the paper:
Epstein, David B. A.; Holt, Derek F
Computation in word-hyperbolic groups.
Internat. J. Algebra Comput. 11 (2001), no. 4, 467–487.
and I did implement it. It works OK on reasonably straightforward examples like surface groups, hyperbolic triangle groups, etc, ...

11

It is still an open problem to find a short and simple way to derive a finite presentation for the mapping class group. The book by Farb and Margalit (in the recent preliminary version 4.00) gives a clear sketch of the known derivations, which are rather long and complicated. For the details one must consult the original papers cited in the book. There are ...

10

This problem is undecidable. If it were not, you could use it to construct an algorithm for testing if a given f.p. group is trivial or not, which is well known to be undecidable:
Input: f.p. group G
Test if G is residually solvable.
If it is not, output "non-trivial".
If it is, find the abelianization of G.
If the abelianization is trivial, output ...

9

Finitely generated torsion-free nilpotent groups are polycyclic. Therefore, their cohomological dimension equals their Hirsch length.This is a result of Gruenberg. One can find it in Gruenberg's book 'Cohomological topics in group theory' in section 8.8 or in Robert Bieri's Book on 'homological dimension of discrete groups' as Th. 7.14.
On the other hand, ...

8

At the risk of being subjective (and possibly even argumentative), I feel like I should offer an answer to the implicit question, answered piquantly by Derek Holt:
'a large proportion of researchers in Geometric Group Theory appear to be interested only in the existence of algorithms and their complexity, rather than in actually using them to do ...

8

I think Lee's and Steve's comments pretty much answer this question. Let me try to summarize, and clear up a couple of misconceptions that seem to be lurking. For convenience, I'll denote your group by $G$.
The map $G\to F_2\times F_2$.
Actually, I don't think the map $G\to F_2\times F_2$ that you describe is an injection. The images of $x$ and $z$ ...

7

As the authors explain in the 2010-04-22 version of their text, an explicit presentation was first obtained by Harer, using the method developed by Hatcher and Thurston. The latter defined a 2-dimensional simply connected polyhedral complex on which Mod(S) acts :
cocompactly (i.e. finitely many orbits of 0,1, and 2 faces)
with explicitly finitely presented ...

7

This discussion: http://www.math.niu.edu/~rusin/known-math/95/rubik seems to culminate in a presentation (due to Dan Hoey). I did not read it carefully, I must admit. The presentation is quite complicated. For the 2x2x2 group there is this:
http://cubezzz.dyndns.org/drupal/?q=node/view/177

6

You probably already noticed that, but $B_{p,q}$ is the fundamental group of
$$
X_n/(S_p \times S_q)
$$
where $X_n$ is the configuration space of $n$ points in the complex plane. Ths may help to guess some facts about these groups.
So far I know these group are usually called "mixed braid groups" in the litterature, though this name is sometimes used for ...

5

Yes. In fact, slightly more is true: the simple homotopy type of the presentation 2-complex is preserved under Nielsen transformations. For a proof of this fact, see
Micheal N. Dyer and Allan J. Sieradski, Trees of homotopy types of two-dimensional CW-complexes. I., Comment. Math. Helv. 48 (1973), 31–44. MR0377905

5

If I understand your presentation correctly, you have determined that $\Gamma(4)$ is a free group on $5$ generators. This is not surprising. The modular curve $X(4)$ is $\mathbb P^1$ with six cusps and no elliptic points, so its fundamental group is the free group on $5$ generators. You appear to have found one set of $5$ generators. There is nothing wrong ...

4

In fact, we can describe your group $G$ quite explicitly.
The presentation has the property that each generator appears in exactly two relators. Therefore, the corresponding presentation complex $X$ is locally a surface everywhere except at the unique vertex. In particular, $X$ is homeomorphic to a surface $S$ with some number of points identified.
To ...

4

There are some other types of groups for which this type of algorithm would work. The easiest examples are abelian groups. For example, with the free abelian group of rank $2$, $\langle x,y, \mid xy=yx \rangle$, if you systematically make the substitutions $y^ax^b \mapsto x^ay^b$ with $a,b = \pm 1$, together with free reductions, then you can transform any ...

4

The following answer will only be about decidability results or, more often, undecidability results. Of course, if you have a particular group in mind, it may be that something positive can be said. I will leave others to talk about practical algorithms.
Let $G=\langle X\mid R \rangle$ be a finitely presented group, $S$ a finite subset and $H=\langle ...

4

Polycyclic groups are certainly of type $FP_\infty$ since the integral group ring $\mathbb{Z}G$ is Noetherian (http://plms.oxfordjournals.org/content/s3-4/1/419) and so every finitely generated module over it has a resolution by finitely generated projective modules.
I believe it remains an open question as to whether the only groups $G$ with the property ...

4

Suppose that $K\subset {\mathbb R}$ and that your subgroup $\Gamma$ on $PSL(2,K)$ is discrete (as a subgroup of $PSL(2,{\mathbb R})$. Then there is an algorithm for computing Dirichlet fundamental domain for $\Gamma$, which is due to Troe Jorgensen: See e.g. here for the description of the algorithm. I think, Igor Rivin even implemented this algorithm (he ...

4

It is not clear whether the set of finite residually solvable group presentations is even recursively enumerable. Unlike for the word or triviality problem where there exists an algorithm which says "yes" iff the answer is "yes", I do not think there exists such an algorithm in this case. But I do not think anybody proved that the algorithm does not exist. ...

4

One such result that springs to mind is that, if the finite group $G$ has a presentation with $r$ generators and $s$ relations, then the Schur Multiplier $M(G) = H_2(G)$ of $G$ can be generated by at most $s-r$ elements. So in particular $s \ge r$. (Of course you can prove that more directly - a finitely presented group with $s<r$ has infinite ...

3

Yes, of course, here are a few examples:
Finite Coxeter groups (see any book on Coxeter groups), they are given by their presentations.
Finite simple groups, see http://pages.uoregon.edu/kantor/PAPERS/GKKL2.pdf and references there.

3

Let me try a preliminary answer to see if I've understood what you're after.
You have, let's say, 1000 web pages, each containing some outbound links. You might define a 1000x1000 matrix D by
$$
D_{ij} = \mbox{number of links in common between the }i\mbox{th and }j\mbox{th pages}.
$$
Then you want to extract from $D$ a single number, the 'level of ...

2

The result by Guralnick, Kantor, Kassabov and Lubotzky (which is mentioned already in Mark Sapir's answer) is one of the most striking results in finite group theory of the last decade, in my opinion. It shows that there is a uniform bound on the length of the presentation for (probably all) nonabelian finite simple groups. This is much stronger than what ...

1

The Baumslag-Solitar groups $B(1,n)$ for $n\ge 2$ can be ordered, even with a total order.
Indeed, all orderings have been classified in this case, see C. Rivas: On spaces of Conradian group orderings.
Here is one way to obtain an ordering for $B(1,n)$. Start with an exact sequence
$$
0 \rightarrow \mathbb{Z}\rightarrow BS(1,n) \rightarrow ...

1

Here is an idea of an example (just for a start). Take the finite group $A_n$ (it is hyperbolic). It has a short presentation, see this paper. The total size of relations is something like $\log |A_n|$. I am sure the $\delta$ for that presentation is about $\log |A_n|$ also. A Dehn presentation of $A_n$ should require about $|A_n|$ relators.
Actually one ...

1

One approach is to represent your data as a graph, and use a network diagram tool to draw it. Variant 1: nodes are websites, weighted edges represent number of common links. Variant 2: a bipartite graph with nodes being either web sites or links, and unweighted edges indicating "web site A contains link B." The magic google phrase to find examples related to ...

Only top voted, non community-wiki answers of a minimum length are eligible