Talk:Presentation of a group

From Wikipedia, the free encyclopedia

WikiProject Mathematics
Mathematics Portal
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: B Class High Priority  Field: Algebra

Contents

[edit] 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)

[edit] 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)

[edit] 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^1t=c_1a^{-1}ba^1,t^{-1}b^{-2}ab^2t=c_2a^{-2}ba^2,\dots \ s_1,s_2,\dots >

The relators t^{-1}at=b\ and t^{-1}b^{-i}ab^it=c_ia^{-i}ba^i\ (i\ge 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^itz^{-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)

[edit] a particular presentation

I'm looking for info on the following presentation: < x,y | z = xyx − 1y − 1,zx = xz > which is a lot like the Heisenberg group, except that the second relation is not there: zy\ne 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)

[edit] 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)

[edit] 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 a2 = 1. The relation a2 = 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)