Conference rusure::math

     Is it correct to respond instantly that there are at least
     lcm(5, 3, 2) = 30 elements?  And that the number of elements
     is a multiple of 30?
     
     Dan

    We can immediately remove b from the relations, since
    
    	(abc)^-1 = c�  =>  abc = c^-2  =>  b = a^-1 c^-3
    
    So we have G = < a,c | a^5 = (c�a)^-3 = c� >
    
    Or: G = < a,c | a^5 = c�, c^8 = (ca)^-3  >
    
    Unfortunately, this hasn't yet helped me solve the puzzle.

    This may be helpful.  I've found a non-trivial subgroup of G.
    It is:
    
	H = < a,c | a^5 = c�, c^8 = (ca)^-3, a = c^37, c^61 = I >
    
    
    
    Why 37?  Why 61?  Beats me.  Here's how I found this.  I set a = c^m,
    where m is some unknown variable, and the relations of G yielded:
    
    	 5*m-2             3*m+11                gcd(5*m-2,3*m+11)
    	c      = I,  and  c       = I;  hence,  c                  = I.
    
    Now, the gcd is usually 1, which makes for a trivial subgroup (a = c = I).
    But a computer search suggested that if m = 61*k+37, then the gcd is 61!
    Now where does that lead?

     Sixty-one?? Sixty-one??
     
     My first thought on seeing that was, "Yeah, right.  Why
     don't you try checking your arithmetic next time?" Then I
     decided I'd have to show how to do a problem like this. :-)
     
     First I decided to find the simplest possible such group. 
     If the problem had stated there was only one group
     satisfying those conditions, then that would be all that was
     needed.  Here it was left open how many possible groups
     there were, so I wanted a simple solution to see if it would
     show anything about the general case.
     
     Now, the easiest way to have a^5 = b^3 is to have some other
     element x such that a^5 = b^3 = x^15 where a = x^3 and b = x^5.
     It's not necessary that G contain a cube root of a or a
     fifth root of b; that's just a simplifying assumption.  Here
     we are given a^5 = b^3 = c^2 and the least common multiple
     is lcm(5,3,2) = 30 so assume an element y such that a = y^6,
     b = y^10, c = y^15, and a^5 = b^3 = c^2 = y^30.  Now all of
     these are equal to (abc)^-1 = (y^6 y^10 y^15)^-1 = y^-31.
     Then y^30 = y^-31 gives y^61 = e (the identity element of
     the group).  So this gives as one possible answer the group
     G = Z/61Z = the set {0,1,2,...,60} under the operation of
     addition modulo 61, with a = 6, b = 10, c = 15.  To check
     this, a^5 = aaaaa = 6+6+6+6+6 = 30, b^3 = 10+10+10 = 30,
     c^2 = 15+15 = 30, (abc)^-1 = -(6 + 10 + 15) = -31 = 30
     (modulo 61), and finally {a,b,c} generates the group because
     abc^-1 = 6 + 10 - 15 = 1 generates the group.
     
     So I guess 61 isn't an arithmetic error after all. :-)
     
     I tried then to put some restrictions on the possible
     solutions.  Maybe the group with 61 elements [there is only
     one up to isomorphism because 61 is prime] is not the only
     answer, but perhaps all solutions are cyclic (i.e., the
     integers modulo n under addition modulo n, for some n) or
     commutative.  I tried to prove that all of the solutions
     were commutative first, by showing that ab = ba, ac = ca,
     and bc = cb (this is sufficient since a,b, and c generate
     the group, i.e., any element is a finite multiple of
     (signed) integral powers of a, b, and c).  So far I have
     gotten that abc = cab = bca (all are equal to a^-5 = b^-3 =
     c^-2).
     
     For now I will leave it that one possible answer to .0 is
     the group has 61 elements, but I haven't shown yet that that
     is the only solution.
     
     Dan

                            -< yes, 61 divides |G| >-
Re: .3, Peter:

>    This may be helpful.  I've found a non-trivial subgroup of G.
>	H = < a,c | a^5 = c�, c^8 = (ca)^-3, a = c^37, c^61 = I >
>    Why 37?  Why 61?  Beats me.  Here's how I found this.  I set a = c^m,
>    where m is some unknown variable, and the relations of G yielded:
>    	 5*m-2             3*m+11                gcd(5*m-2,3*m+11)
>   	c      = I,  and  c       = I;  hence,  c                  = I.
>    Now, the gcd is usually 1, which makes for a trivial subgroup (a = c = I).
>    But a computer search suggested that if m = 61*k+37, then the gcd is 61!
>    Now where does that lead?

	This is interesting, particularly the numbers which crop up, but 
there's a small mistake in it, I think.

	We don't *know* that there is *any* m such that a = c^m.   So if we
postulate that a = c^m, then essentially, we're adding an extra relation to
the right hand side.   By adding a relation, we don't get a *subgroup* of
G.   It's not like adding a restriction to a set, and thereby getting a
smaller set.

	When a group appears in a presentation, it is a quotient group, F/F',
where F is the free group on the left hand side (here a, b & c), and F' is
the normal subgroup generated by the strings on the right hand side (here 
a^5c^-2, b�c^-2, & c�(abc) ).

	So if we add an extra relator to the right hand side (here ac^-37)
then we get a new subgroup, F", normal in F.   F' is a subgroup of F", and 
is normal in F, so F' is normal in F".   Therefore H = F/F" is isomorphic to 
(F/F')/(F"/F') = G / (F"/F').   So H is a homomorphic image of G, not a 
subgroup.   The *kernel* of the homomorphism has index 61.

	Thus there exists a normal subgroup, K, of G, index 61.   Moreover,
K contains the cyclic subgroup < ac^-37 >, and all of its conjugates.

	I'd no idea that such a normal subgroup existed!   I'd approached
the problem from a completely different tack.


Re: .4, Dan:

>     First I decided to find the simplest possible such group. 
>     If the problem had stated there was only one group
>     satisfying those conditions, then that would be all that was
>     needed.  Here it was left open how many possible groups
>     there were, so I wanted a simple solution to see if it would
>     show anything about the general case.

	A group presentation has only one solution, namely the quotient
group defined above.   The 'other solutions' that you're talking about
are homomorphic images of the solution.   Exploring them, as you've been
doing, can still lead to useful results about the real solution.

Andrew. 

    I didn't see anything in .0 that said that they had to be
    different...;-)
    
--  Barry    

     re .5
     
>>           A group presentation has only one solution, namely the quotient
>>   group defined above.
     
     I thought that was the case, but I also thought that all of
     the generators were necessary, yet here it is possible to
     write one as a product of powers of the other two.  So I
     thought perhaps this wasn't a standard presentation.  In
     fact, in the solution I gave any one of a, b, or c generates
     the entire group.  Also, since Z/61Z is a solution and you
     say there is only one solution, why did you reply as if
     Z/61Z was not that one solution but merely a homomorphic
     image of it?
     
     Dan

     .6 went in as I was writing .7 and expresses the same
     question about the "independence" of the generators,
     although much more bluntly. Why isn't "one" the answer to
     how many elements does G have?  It satisfies the
     constraints.
     
     Dan

>	Why isn't "one" the answer to
>     how many elements does G have?  It satisfies the
>     constraints.

	This is just a question of definitions.   No big deal.   We're all
familiar with something like this:

	S = { x | x real, x� rational }

	This is a set, defined to be the set of all x satisfying the 
constraints on the right.

	S' = { x | x real, x� rational, x > 0 }

	S' is also a set, with an additional constraint, and so S' is a subset
of S.

	In a group presentation, the notation is deceptively similar, but the
semantics are definitely different.   Most important: there are no 
'constraints':  the chaps on the right are relations.

	G = < a | >

	This is a group, with one generator, and no relations.   This is called
the free group on one generator, and is isomorphic to Z.   Note that G is 
well-defined by this:  we don't accept the trivial group as an answer to this
presentation, because there is no way that the element a, for instance, can be
rewritten as 1.   

	If I lob in an additional relation:

	G' = < a | a^5 = 1 >

then the group that I get is a quotient G/F, where F is the normal subgroup of
G generated by a^5.   G' is obviously isomorphic to C5, and there is just no
way that C5 is a subgroup of Z.

	Another way to say the same thing is: by adding a relation, one maps
G to a homomorphic image G', with kernel generated by the relation.

Andrew

>    	 5*m-2             3*m+11                gcd(5*m-2,3*m+11)
>   	c      = I,  and  c       = I;  hence,  c                  = I.
>    Why 61?

	5 * 11 - (-2) * 3 = 61.  That's why.

re .5

> By adding a relation, we don't get a *subgroup* of G.   It's not like
> adding a restriction to a set, and thereby getting a smaller set.
> [...] H is a homomorphic image of G, not a subgroup.   [...]

Thanks.

	Why don't I put in the next stage?   It's not *quite* complete,
as you'll see.   This is a second draft of .11, because the first draft
included too much detail, and was unmanageable.

Summary:

Peter showed:	a normal subgroup, K, with [G:K] = 61
There's also:   a normal subgroup, H, with [G:H] = 60
and further:    |H| divides 122.
Defining E to be a certain other normal subgroup:

G/E is IM to A5 x C61

What I don't know:  is E trivial, or is it IM to C2?


(1) a normal subgroup H of index 60.

	The equations: a^5 = b� = c� = (abc)^-1 = 1 are satisfied by the
assignment to various elements of the alternating group on five symbols,
A5.

	a -> (12345)
	b -> (142)
	c -> (23)(45)

	So, there's a normal subgroup, H, with [G:H] = 60.


(2) |H| divides 122

	This is a lot tougher.

	Let d = (abc)^-1.   Then d commutes with a, b & c.   It is central
and so in particular D, the cyclic group generated by d, is normal in G.   
D is contained within H.   Therefore:

	G/D = < a, b, c | a^5 = b� = c� = abc = 1>

	The first question is this: is H bigger than D?   To solve this, the
best way is to use a Cayley diagram of G/D.   This means that we have a graph, 
with one vertex for each element Dx of G/D, and one directed edge labelled
a leading from each vertex Dx to vertex Dxa.   Similarly, one directed edge 
labelled b, from Dx to Dxb, and one edge labelled c from Dx to Dxc.

	You build up the graph iteratively, by adding one vertex at a time,
putting in the known edges, and identifying two vertices when some walk of
value 1 can be made between them.   When you can draw no more edges, then
you stop and the group is complete.

	The cute thing about this group is that the Cayley diagram is planar,
and that we can take advantage of this.

	Lemma: (Not proved here) If 1/p + 1/q + 1/r > 1, then the group, 
< a, b, c | a^p = b^q = c^r = abc = 1> is finite and has order 2s, where:
1/s = 1/p + 1/q + 1/r - 1.   The Cayley diagram is then a tesselation of the
sphere.

	If 1/p + 1/q + 1/r =< 1, the group is infinite.   If equality holds, 
the Cayley diagram is a tesselation of the Euclidean plane, otherwise it is a 
tesselation of the hyperbolic plane.

	In fact, the Cayley diagram for G/D can be drawn on an icosahedron.
It's fun to see how.   Start by trisecting the edges, and putting a vertex
on each trisection point (=> 2 * 30 = 60 vertices, check).

	The graph has 60 vertices, so H = D, and thus G/D is IM to A5.   For
confirmation, note that the AM group of the Cayley diagram is the same as
the symmetry group of the icosahedron which is, guess what, A5.

	Now suppose that I've got some closed walk around the graph that 
satisfies the following properties:
	(1) value of the walk (composition of edge labels) is 1.
	(2) each edge appears twice in the walk, once in each direction.
	(3) for each face, the edges appear in cyclic order, although not
necessarily consecutively, in the walk.

	Then I allege that I can take the value of the walk to be equally
the composition of the values of a little closed walk round each face, which
is d.   Since there are 122 faces (include those with 2 edges, cc^-1), I have:
	d^122 = 1.

	I've missed out several steps here, for conciseness, and it is not
trivial to find such a closed walk.   If you are curious, explore the
following, with a diagram (or a painted icosahedron :-)

	Let e(x) = b�c.x.c~b~cc~b~cc~b~. (~ denotes inversion)
	Let g(y) = e(a^2.e(y).a^3.a~^5)
	Now examine the closed walk z = (ag(1))^5.a~^5.
	How could you combine two copies of z, to solve the problem?

	Finally, since H = D = <d>, |H| divides 122.

(3) G/E is IM to A5 x C61

	|H| is 1, 2, 61 or 122.   But we know that 61 divides G.   So only the
latter two cases are possible.

	case (a) |H| = 122
	Then	 |K| = 60*122/61 = 120
	HK/H is IM to K/E, where E is the intersection of H and K.
	G/E is IM to K/E x H/E which is IM to A5 x C61

	case (b) |H| = 61
	Then     |K| = 60*61/61  = 60
	G is IM to K x H which is IM to A5 x C61
	(and if you define E as above, then G/E IM to A5 x C61 still holds).


	Ea = ( (12345), t^12)
	Eb = ( (142),   t^20)
	Ec = ( (23)(45),t^30)
	Ed = ( 1,       t^-1)

	E = { 1, d^61 }


(4)	The only question left is: what is d^61?

	My guess is that it is 1.   For suppose not.   Then |K| = 120, and
it has a normal subgroup, E, of order 2 such that K/E is IM to A5.   I don't
think that any such K exists, except for A5 x C2.   But this leads to a
contradiction.

	Any ideas, anyone (and thanks for struggling through this far).

Andrew.

     re .2
     
>>    So we have G = < a,c | a^5 = (c�a)^-3 = c� >
>>    
>>    Or: G = < a,c | a^5 = c�, c^8 = (ca)^-3  >
     
     How do you go from the top line to the bottom?  It seems to
     me that to do that you had to assume that a and c commute.
     
     re .11
     
>>     Let d = (abc)^-1.  Then d commutes with a, b & c.
     
     I don't see why that must be true.
     
     Dan

     re .12
     
     Never mind.  Using my own result in .4 that abc = cab = bca,
     it is easy to show that if d = (abc)^-1 then ad = da, bd = db,
     and cd = dc.  Then using that result one can prove the step
     in reply .2, that (c^3 a)^-3 = c^2 ==> c^8 = (ca)^-3.
     
     Dan

>>     Let d = (abc)^-1.  Then d commutes with a, b & c.

	         5    5
	a d = a a  = a  a = d a

	         3    3
	b d = b b  = b  b = d b

	         2    2
	c d = c c  = c  c = d c

	Final step.

	Remember, we have normal subgroup H such that G/H == C61.
	Now whether the order of the group is 3660 or 7320, Sylow tells
us that there is exactly one Sylow-61-subgroup, L.   L is therefore normal.
So:
	G = H x L

	The significance of this is that H == G/L, which gives us a 
presentation for H, for the first time.   L is generated by c^4, so (using 
Peter's representation of G):

	H = < a,c | a^5 = c�, (ca)� = 1, c^4 = 1 >

	Now to find what this group is, we draw the Cayley diagram.   In
fact, most of our work is already done.   H/E == G/K, and we already have
drawn the Schreier diagram for G mod K.   This is the painted icosahedron,
with pentagons (a^5 = 1), ovals (c� = 1), and hexagons ((ca)� = 1).   To
determine the feasibility of |H| = 120, we need to view each, i, of the 60
vertices painted on the icosahedron as a pair of vertices {i+, i-}.   Now,
we label (again!) each edge of the graph as + or -, depending on whether
the action of the edge on the invertices takes (i+, i-) to the outvertices 
(i+, i-) or (i-, i+).

	Now, for |H| to be 120, the following must apply:

	(i) each pentagon contains an odd number of - labels
	(ii) each oval contains an odd number of - labels
	(iii) each hexagon contains an even number of - labels

	This in fact is easily accomplished, so |H| = 120.   Note that
H is not IM to A5 x C2, because G cannot have C2 as a homomorphic image.
C2 is the only non-trivial normal subgroup of H.

	Thus, G = H x C61, H has order 120 and composition series [A5, C2],
and |G| = 7320.

Andrew.

	I realized that the pentagonal/hexagonal tesselation of the sphere is a
familiar one.   A (soccer) football is frequently made up of such leather
patches stitched together in the necessary way, because it approximates well a
sphere.   Even plastic moulded footballs often have a black pentagonal pattern
on them echoing the leather version. 

Andrew.

     re .11
     
>>	(1) a normal subgroup H of index 60.
>>
>>     The equations: a^5 = b� = c� = (abc)^-1 = 1 are satisfied by the
>>     assignment to various elements of the alternating group on five symbols,
>>     A5.
>>
>>             a -> (12345)
>>             b -> (142)
>>             c -> (23)(45)
>>
>>             So, there's a normal subgroup, H, with [G:H] = 60.
     
	How would one solve a presentation like this,
	a^5 = b^3 = c^2 = (abc)^-1 = identity, or the equivalent
	(given the solution for b in terms of a and c) version
	a^5 = c^2 = (ca)^3 = identity?

	Did you just guess at the alternating group on five
	symbols?  Is there some systematic way of solving these?
        
        I don't even see how to tell if the result will be
        infinite, or if the result will have one element, in the
        general case.

	Dan

>      <<< Note 1089.17 by AITG::DERAMO "Daniel V. {AITG,ZFC}:: D'Eramo" >>>
>
>     re .11
>
>	How would one solve a presentation like this:
	X = < a,b,c | a^5 = b^3 = c^2 = (abc) = I> ?
>	Did you just guess at the alternating group on five symbols?

	I built the Cayley diagram.   Looking at it as a picture, it *must*
be something to do with icosahedra, which have symmetry group A5.   Also,
there are 60 nodes in the Cayley diagram, so the group has 60 elements.
Pretty strong circumstantial evidence, and it's a minute's work to figure
how to map a,b,c on to things so that (abc) = I.

	Another approach, the automorphism group of the Cayley diagram will 
contain X, since each generator acts as an automorphism of the diagram.   That 
AM group contains A5, by looking at the painting on the icosahedron.   It is a 
little work to show that the AM group *is* X.  Then you have the result.

>	Is there some systematic way of solving these?

	The system to explore the group is to build the Cayley diagram.
It's a real shame that we are limited to a text medium here, because the
diagrams are very pretty.   The critical point is that the construction *is*
systematic.   It is an algorithm.   It is not guaranteed to terminate, because
(a) there's no general way you know beforehand whether you're dealing with an
infinite group or not (b) the word problem for groups is in general
undecidable.

	But, if the algorithm terminates, then you know that you've got
a finite group.   You keep adding edges to new nodes, *only* identifying two 
nodes, if you discover that some relation unifies them.   If all the nodes 
have an in-edge and an out-edge for each generator, then you're finished.

	Let me give an example: S3.

	< a, b | a� = b� = (ab)� = 1 >

	Start with a node N1.
	Build edge & node: label edge a, leads from N1 to N2.
	Build edge & node: label edge a, leads from N2 to N3.
	Build edge & node: label edge a, leads from N3 to N4.
	Identify: N1 & N4, using a�=1.
	Build edge & node: label edge b, leads from N1 to N5.
	Build edge & node: label edge b, leads from N5 to N6.
	Identify: N1 & N6, using b�=1.
	Build edge & node: label edge a, leads from N5 to N7.
	Build edge & node: label edge a, leads from N7 to N8.
	Build edge & node: label edge a, leads from N8 to N9.
	Identify: N5 & N9, using a�=1.
	Build edge & node: label edge b, leads from N7 to N10.
	Identify: N10 & ..., using (ab)� = 1.
	... (I'm sure you can finish it off.)

	That's very dry, and doesn't really do justice to the speed with
which you can draw these diagrams out, but does suggest that it may be a
process automatisable by computer (which is true).

>       I don't even see how to tell if the result will be
>       infinite, or if the result will have one element, in the
>       general case.

	If you see some repeating structure, then it may be obvious that the
group is on a locomotive to infinity, and never coming back.   For instance

	< a | > just keeps on going.

	or there are groups related to the one I previously discussed which
form tesselations of the Euclidean or hyperbolic planes.   If there's a
regularity to the growth, then you can show that the group is infinite.   If
it's just a mess, and you can't get an analytic handle on it, then there's
no way that the algorithm can tell you "well, here's a billion nodes: it
certainly must be infinite."   That's undecidability, but not relevant here.

Slobotny,
Andrew.

     Thanks.  I did work out the S3 example, and that was simple. 
     I still have a number of nodes on the A5 problem still to be
     expanded, though.
     
     Why must every node have both an in and an out edge for
     every generator?  Why isn't just an out edge for every
     generator enough?  Wouldn't that imply that the diagram is
     complete (and so imply the former condition)?
     
     Dan
    

>     I still have a number of nodes on the A5 problem still to be
>     expanded, though.
 
	This is where scaling up into thinking about cycles and tilings
is useful, but one has to be careful to be rigorous.
    
>     Why must every node have both an in and an out edge for
>     every generator?  Why isn't just an out edge for every
>     generator enough?  Wouldn't that imply that the diagram is
>     complete (and so imply the former condition)?
    
	Yeah, in the context of finite graphs, my statement is redundant.
For infinite graphs you need to check both in order to have completeness.
(Think about < a | > again.)


Cheers,
Andrew.

        Some tools make this kind of problem easier than others...
        
        Dan
        
gap> f3 := FreeGroup( "a", "b", "c" );
Group( a, b, c )
gap> G := f3 / [
> 	(f3.1^5)/(f3.2^3),
> 	(f3.1^5)/(f3.3^2),
> 	(f3.1^5)*(f3.1 * f3.2 * f3.3)
> ];
Group( a, b, c )
gap> Size(G);
7320

	QED. :-)  A little more...

gap> a := G.1;
a
gap> b := G.2;
b
gap> c := G.3;
c
gap> Index(G, Subgroup(G, [a]));
12
gap> Index(G, Subgroup(G, [b]));
20
gap> Index(G, Subgroup(G, [c]));
30
gap> Order(G, a);
610
gap> Order(G, b);
366
gap> Order(G, c);
244

    Hey cool...
    
    Andrew.