Talk:Presentation of a group

Notation

I believe it is more common to write the presentation of a group G = (S|T) rather than G = (S;T), thoughts? - siroxo 06:11, Jun 6, 2004 (UTC)

I have seen lots of notations including: (S|T), (S;T), <S:T>, <S;T> and <S|T>. A brief but unrepresentative survey:

• Magnuss, Karrrass and Solitar, 'Combinatorial Group Theory': <S;T>
• Lyndon and Schupp, 'Combinatorial Group Theory': (S;T)
• Ian Macdonald, 'The theory of groups': gp{S;T}
• Boone, Canninito and Lyndon (Eds), 'Word Problems': this is a collection of paper at a combinatorial group theory conference. It contains all these notations: (S|T), {S|T}, <S;T>, {S;T}, and gp(S;T), maybe more - I havn't checked all 650 pages!

I have no idea which is the most common notation, although I am pretty sure (S|T) is not the most common. I tend to default to the M-K-S notation <S;T>, probably because that it the textbook I used when I was learning combinatorial group theory. I get the impression that this and the L-S notation (S;T) are the most common among people who work on algoithmic problems in group theory, but, of course, other group theorists use presentations too! Personally but I am not too bothered as I tend to adapt to the environment, but it does seem to worry some people.

• Should there be a wikipedia standard? how do you go about making one?
• Maybe it is worth mentioning that the notation for a presentation is not generally agreed upon.

Bernard Hurley 10:38, 27 September 2006 (UTC)

Previous survey was of publications I own, but they are all a bit out of date. Quick, but unscientific, survey of 50 papers from last four years:

<S|T> 92%

(S|T) 4%

{S;T} 2%

<S;T> 2%

So it looks like <S|T> is the de facto standard now.

Bernard Hurley 09:13, 28 September 2006 (UTC)

I've noted these variant formats for notating a presentation, in a small subsection of the § Definition. It would be good to find a source for the history of their usage and current (relative) standardisation. yoyo (talk) 09:38, 28 March 2018 (UTC)

Undecidability

Given two presentations, the problem of determining if they give the same group is undecidable, in the Godelian sense. Viz there is no algorithm or Turing machine that can systematically explore presentations and determine whether they specify the same group in a finite amount of time (in general -- in any particular case, you just might be able to work it out). This is isomorphic to the halting problem. Do we have an article on this?

(There is an intuitive way to look at this: for any given presentation, you can try to write out every possible string that it generates; the problem is one of trying to compare all possible strings to determine if the same set was generated. Finitely-presented groups are kind-of-like context-free grammars, so one has a similar problem there: do two different grammars generate the same set of sentences? The CFG article does briefly review the undecidability problem.) linas 14:30, 25 July 2006 (UTC)

Changing my mind: split out recursively enumerated groups (again)

Hmm, considering that recursively presented groups now take up more than half of the "formal definition" section, and the rest of the statements to be included will be considerably more complicated if we really want to take non-finitely generated recursively presented groups into account, I think it should be split again into a separate articles.

Statements that need to go in:

• a recursively presented finitely generated group has a recursive subpresentation for all of its presentations. (Which is what makes the definition make sense, really.) No longer true if "finitely generated" dropped.
• Higman's Embedding theorem, and characterisation of recursively presented groups. No longer true. (As a totally tangential remark, you can actually read all of this backwards, and define computability using Higman's Embedding theorem, using nothing but group theory. I haven't seen it fleshed out, but think if someone else has, that might make for an interesting remark/potential future article.)
• Characterisation of groups with solvable world problem. Again, only the finitely generated case works, as far as I know.

Given all this, we really need a section for recursively enumerated finitely generated groups (in fact, if only there were a handier term, we'd probably have a separate article).

Is there anything interesting to say about non-f.g. recursively enumerated groups, other than "oh, all those nice things? No longer work."

Is it true that general recursively enumerated groups are just recursively generated subgroups of finitely generated recursively enumerated groups? As the free group on a countable set of generators is a r.e. subgroup of a finitely presented group, and we can just pull over the relators, so that would work.

In all, too much for a subsection of "formal definition", and, to me, it looks like it's enough for a (short) article: the main reason is most readers of this article just won't be looking for that information, and might not be able to understand it.

Does anyone disagree?

RandomP 23:56, 25 September 2006 (UTC)

Why not make a new section on recursively presented groups, seperate from the first formal definitions section? CMummert 01:02, 26 September 2006 (UTC)

I'm not sure I follow all you are saying (It's 1.30.am here in the UK and I should really be asleep!). However its worth pointing out that the HNN embedding into a 2-generator group works as follows: Let:

$C=<c_{1},c_{2},\dots \ ;s_{1},s_{2},......>$

Then $C\$ can be embedded into:

$G=<a,b,t,c_{1},c_{2},\dots \ ;t^{-1}at=b,t^{-1}b^{-1}ab^{1}t=c_{1}a^{-1}ba^{1},t^{-1}b^{-2}ab^{2}t=c_{2}a^{-2}ba^{2},\dots \ s_{1},s_{2},\dots >$

The relators $t^{-1}at=b\$ and $t^{-1}b^{-i}ab^{i}t=c_{i}a^{-i}ba^{i}\ (i\geq 1)$ allow all generators except $a\$ and $t\$ to be eliminated by Tieze transformations in such a way that if $C\$ is recursively presented so is $G\$.

Actually infinitely generated recursively presented groups are used quite extensively in combinatorial group theory. For instance in the standard proof of the Boone-Higman theorem (that a f.p. group has solvable word problem if and only if it can be embedded in a simple subgroup of a finitely presented group) the simple group is an infinitely generated recursively presented group.

Bernard Hurley 01:08, 26 September 2006 (UTC)

I am awake enough to see what you are getting at concerning the "three statements".

• Regarding the first statement, I am not quite sure what you mean by a subpresentation - i will have to think about it.
• Regarding the second statement, Higman's embedding theorem still works for infinitely generated recursively presented groups.
• Regarding the third statement. Which characterization did you have in mind? The Boone-Higman theorem was originaly proved for finitely presented groups, but the proof works for finitely generated recursively presented groups. The standard proof does not work for inifinitely generated groups, which is not to say it might not turn out to be true. The same is true for the other characterisations I know of.

You ask: Is it true that general recursively enumerated groups are just recursively generated subgroups of finitely generated recursively enumerated groups?

The answer is "yes", but it is not for the reason you seem to be suggesting. If we wish to exhibit an inifinitely generated group G=<X| R> as a subgroup of a finitely generated group, we can't simple map the generators X to the generators of a countably generated free subgroup of a free group and use the images of the relators R as new relators. The normal subgroup generated by the image of the relators may include words in X that are not equal to 1 in G. A proof is required that this will not happen for the subgroup you have chosen. The proof of the HNN embedding into a two generator group shows that there is a subgroup of <a,t|> for which this will work, namely the group with (free) generating set:

$b=t^{-1}at\$

$c_{i}=t^{-1}b^{-i}ab^{i}tz^{-i}b^{-1}a^{i}\ (i=1,2,\dots \ )$

This generating set obviously is r.e.

Whether this is too much for a section on formal definition, depends on what the reader needs the definition for. If s/he wants to undertand the statement of the Boone-Higman theorem, then s/he does not need the definition for infintely generated groups, but if s/he wants to understand the proof if the Boone-Higman theorem then s/he certainly does need it.

Perhaps the definition for inifinitley generated groups needs a separate section. The definitions are "conceptually" the same, its just that you have to get the logic right, which is a bit fiddly.

Bernard Hurley 12:42, 26 September 2006 (UTC)

Ah. In order:

• A subrepresentation of $<S|R>$ is a representation $<S'|R'>$ with $S'\subset S$, $R'\subset R$ that ends up representing the same group.
• "The answer is "yes", but it is not for the reason you seem to be suggesting." - er, that was the reason I was suggesting. I wasn't providing a proof.
• The fiddliness is certainly there (and considerable), but what about the advantages?

Sorry if I'm going off on a total tangent, but if this weren't an encyclopedia, but a "teach mathematics to space aliens who've never heard about it before, and thus don't care about your carbon-based traditions" project, I'd try to find the proofs to set up things like this:

• (Start with groups)
• Define f.g. r.p. groups to be finitely generated subgroups of f.p. groups
• (Use that to define what "computable" means)
• Define countably generated recursively presented groups to be recursively generated (equivalently, recursively enumerated) subgroups of f.g. r.p. groups (equivalently, of f.p. groups).

That would appear to me to be a way to present the material without requiring computability theory from the start.

Do you have a nice example of a non-recursively enumerated presentation (that does not have a re subpresentation) of a recursively presented group?

This all seems a lot of material to me, so I'll have a go at splitting it up into an extra section later. If it's too long, we can always reconsider a separate article.

RandomP 13:07, 26 September 2006 (UTC)

The § Definition section was much too complex for first-time readers, so I've split out the info on finitely and recursively presented groups into two separate sections. The resulting smaller definition should now be easier for newcomers to read and gain a basic understanding from. yoyo (talk) 13:22, 28 March 2018 (UTC)

a particular presentation

I'm looking for info on the following presentation: $<x,y|z=xyx^{-1}y^{-1},zx=xz>$ which is a lot like the Heisenberg group, except that the second relation is not there: $zy\neq yz$. I have in hand the matrix representations for this group (including an inf-dimensional one) but wanted to know if this thing has a name, is studied in general, etc. Thanks linas 17:31, 11 March 2007 (UTC)

Math rating

Just a place to sign edits to the math rating.Dan Hoey 19:36, 11 March 2007 (UTC) Then I noticed it belongs in the comment.Dan Hoey 19:39, 11 March 2007 (UTC) But since this section is here, I changed the comment to reference this section. This also removes the indication that I assigned the grade, which I didn't.-- Dan Hoey 15:45, 14 March 2007 (UTC)

Does a presentation uniquely determine a group?

I am no expert on this subject and am trying to make sense of it by reading the article. The presentation $\langle a\mid a^{4}=e\rangle$ clearly describes the cyclic group of order 4. However, the cyclic group of order 2 is also subject to these restrictions. How do we "know" which group is meant by the above presentation? Surely the presentation must define a unique group, as the article states that a presentation is one method of defining a group. Kidburla (talk) 00:27, 16 April 2008 (UTC)

A presentation uniquely specifies a group. I don't have a reference at hand, but I can get one, if you like. Here is the idea: suppose that $\langle S\mid R\rangle$ is a presentation. Here S is a set (of characters) and R is a subset of $(S\cup S^{-1})^{*}$ (the set of finite length words in S and their formal inverses). Let F(S) be the free group generated by S and let N(R) be the smallest normal subgroup of F(S) which contains the set R. Then the group with presentation $\langle S\mid R\rangle$ is defined to be F(S)/N(R).

Now to address your question: we know which group is meant by the presentation because N(R) is unique. More directly: it is true that the group of order two satisfies all of the relations of the group of order four. However, there is an additional relation satisfied, namely $a^{2}=1$. The relation $a^{2}=1$ is not satisfied by the generator of the group of order four. I hope this helps. best, Sam nead (talk) 08:26, 16 April 2008 (UTC)

Coxeter presentation of S5

Maybe I'm doing something wrong, but if I define a group (of permutations) S by the following four generators:

s1 := (1,2)(3,4)(5,6), s2 := (1,5)(2,4)(3,6),

s3 := (1,2)(3,5)(4,6), s4 := (1,4)(2,5)(3,6),

then they are clearly different, of order two, and they satisfy:

s3 * s1 == s1 * s3, s2 * s4 == s4 * s2,

s1 * s2 * s1 == s2 * s1 * s2, s2 * s3 * s2 == s3 * s2 * s3,

s3 * s4 * s3 == s4 * s3 * s4, s1 * s4 * s1 == s4 * s1 * s4,

particularly, s1 * s2, s2 * s3, s3 * s4 and s4 * s1 are of order 3.

However, S is not a S5 group but merely a S4 group with only 24 elements?!

IMO, the problem is here that for the generators as above we have:

s1 * s2 * s1 == s3 * s4 * s3 and s1 * s4 * s1 == s2 * s3 * s2,

whereas in S5 we would have:

(1, 2)(2, 3)(1, 2) <> (3, 4)(4, 5)(3, 4) and (1, 2)(4, 1)(1, 2) <> (2, 3)(3, 4)(2, 3).

Unfortunately, the presentation for S5 as in the table nowhere requires that:

s1 * s2 * s1 must be different from s3 * s4 * s3, as well as that

s1 * s4 * s1 must be different from s2 * s3 * s2. —Preceding unsigned comment added by IvoP (talk • contribs) 12:16, 1 April 2009 (UTC)

Hopefully the presentation for S5 mentions that s4*s1 should have order 2, not order 3. <a,b,c,d:aa,bb,cc,dd,(ab)^3,(bc)^3,(cd)^3,(da)^3,(ac)^2,(bd)^2> is an infinite group (that has S4 as a quotient). It has derived series: 2, 3, 2^4, Z^3, .... On the other hand, S5 = <a,b,c,d:aa,bb,cc,dd,(ab)^3,(bc)^3,(cd)^3,(ac)^2,(ad)^2,(bd)^2>. JackSchmidt (talk) 12:51, 1 April 2009 (UTC)

Sorry, my mistake, I have wrongly assumed that (s[i]*s[i+1])^3=id should cyclically wrap also for i=n=4, i+1=1.

However, the condition s[1]*s[n]=s[n]*s[1], or equivalently (s[1]*s[n])^2=id applies instead since |n-1|>1 (n=4).

—Preceding unsigned comment added by IvoP (talk • contribs) 14:48, 1 April 2009 (UTC)

Wikipedia naming conventions

Shouldn't this article be called "Presentation (mathematics)" or "Presentation (group theory)" by the usual Wikipedia naming conventions? — Preceding unsigned comment added by 207.241.137.116 (talk) 02:00, 15 January 2012 (UTC)

No: the parenthetical disambiguation is not used except when required for disambiguation. A natural title, as is used here and would generally be the term used in the references, is preferred. See Wikipedia:Naming_conventions#Precision and disambiguation. — Quondum^☏✎ 18:48, 15 January 2012 (UTC)

Stupid question.

OK, dumb question: normally, in defining a group in terms of generators, one talks about the set of all finite but unbounded strings of group elements (the Kleene star of these). Sometimes, one can take the limit and consider the set of infinitely-long strings of group elements. The question: in the latter case, when such a limit is possible, is the result, by necessity, always a topological group? Or are there completions that are not? linas (talk) 21:16, 28 August 2012 (UTC)

Oh silly me, never mind. The definition of topological groups requires the group action to be continuous, and clearly, one can imagine completions where the action would not be continuous. Hmm. New question: can anything be said, in general, about the completions of groups to an infinite number of products? (other than the obvious ones e.g. finite groups, or the completeness of reals under addition, etc.) linas (talk) 21:35, 28 August 2012 (UTC)

Just checking that it is clear: infinite strings of generators are not the same as infinite products. (You can't concatenate infinite strings in a reasonable way. So you don't get a group this way.) Instead, infinite strings of generators should be thought of as infinite paths in the Cayley graph of the group. If you are very careful about how you do things (ie use geodesic rays in the Cayley graph, based at the identity) and you are lucky with your group (ie it is Gromov hyperbolic) then the set of rays (up to an equivalence relation) forms a boundary/space at infinity for the group in a natural _geometric_ way. The geometry of the group and its boundary then informs the algebra of the original group. As an easy example - the trivial group has no points at infinity. The infinite cyclic group ZZ has two points at infinity. Any other finitely generated free group has a Cantor set at infinity. best,Sam nead (talk) 19:03, 29 August 2012 (UTC)

Assessment comment

The comment(s) below were originally left at Talk:Presentation of a group/Comments, and are posted here for posterity. Following several discussions in past years, these subpages are now deprecated. The comments may be irrelevant or outdated; if so, please feel free to remove this section.

See Math rating section.

Last edited at 23:07, 19 April 2007 (UTC). Substituted at 02:30, 5 May 2016 (UTC)

Relators and relations

The lead describes R as the set of relations, whereas § Definition describes R as the set of relators. These usages are not quite consistent with each other, and may thus be confusing. Any one relation can be expressed as set membership of some word, or equivalently as an equation of some word to the group identity. I've often seen relations used in formal definitions, but relators in shorthand forms, which is equivalent to dropping " = 1" from each relation expressed as such an equation. The Definition section currently includes the following text:

It is a common practice to write relators in the form x = y where x and y are words on S. What this means is that y⁻¹x ∈ R. This has the intuitive meaning that the images of x and y are supposed to be equal in the quotient group …

Note that the equations mentioned here are not to the group identity, so one might add: "… or that the images of y⁻¹x and 1 are supposed to be equal in the quotient group … " to the last statement just quoted – if that would help. So how could we reduce potential confusion?

Also, in set theory and analysis, a relation on S is defined as a subset of S × S. But here, we have several equations, each of which is regarded as one "relation", so that R becomes a set of "relations" rather than an analytic relation. Do we have one "relation", or many?

Perhaps the clearest way forward would be to note that:

1. Any relation on S is, by definition, a subset of S × S, which we can express
2. as a list of pairs of words on S, e.g. R = {(x,y), (a,z), … , (w,u)};
3. or sometimes as a list of equations between words on S, e.g. R = {x=y, a=z, … , w=u};
4. or (equivalently to the previous) as equations between some words (the relators) on S to the group identity, e.g. R = {y⁻¹x=1, z⁻¹a=1, … , u⁻¹w=1};
5. or (shorthand for the last) as a list of the relators, e.g. =R = {y⁻¹x, z⁻¹a, … , u⁻¹w}.

Would this be any better than we have now? Or somehow worse? yoyo (talk) 12:41, 28 March 2018 (UTC)

I think I see what you mean in the first paragraph and it's likely true that the article should be written more coherently. On the other hand I don't think the changes that you suggest would make the article clearer.

In particular there seems to be a misunderstanding: a relation in the context of group presentations is not at all the same as a set-theoretic relation: it merely represents a dependency between formal variables. To make formal sense of the group determined by these variables (the generators) and these relations between them one then needs to appeal to either combinatorial or group-theoretic machinery, which yields a set-theoretic equivalence relation by which we then mod out the free object (either the language or the free group) to get our actual group. (The article uses only the second construction as far as I can tell.) jraimbau (talk) 07:32, 29 March 2018 (UTC)

⟨x,y | g^n = 1 ∀g⟩

The other day I saw a group "presentation" of the following form: $\langle x,y\,|\,g^{n}=1\;\forall g\rangle$
The idea being that this was a group with 2 generators, with the only relation being that *every* element to the power of n is equal to the identity.

This article doesn't discuss these types of presentations.
I guess you would call this a finitely generated but infinitely related presentation.
That is, there are just two generators, x and y, but the relations are actually the infinite set:
$1^{n}=1,\,x^{n}=1,\,y^{n}=1,\,(xx)^{n}=1,\,(xy)^{n}=1,\,(yx)^{n}=1,\,(yy)^{n}=1,\,\ldots$
ranging over every word made of x and y (and their inverses).

Perhaps the article should address these types of presentations? --AndreRD (talk) 13:32, 13 May 2019 (UTC)

See Burnside problem. A link to this page would be a good idea. jraimbau (talk) 09:15, 14 May 2019 (UTC)