Talk:Presentation of a group

From formulasearchengine
Jump to navigation Jump to search

Template:Maths rating

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)

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:

Then can be embedded into:

The relators and allow all generators except and to be eliminated by Tieze transformations in such a way that if is recursively presented so is .

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:

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:

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)

a particular presentation

I'm looking for info on the following presentation: which is a lot like the Heisenberg group, except that the second relation is not there: . 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 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 is a presentation. Here S is a set (of characters) and R is a subset of (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 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 . The relation 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 (talkcontribs) 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 (talkcontribs) 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)