Author |
Topic: Find Orders of A and B (Read 834 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Find Orders of A and B
« on: Feb 25th, 2004, 1:48pm » |
 Quote  Modify
|
I have a group G containing elements a and b such that
a7 = e
aba-1 = b2
b [ne] e
Find the orders of a and b.
|
| « Last Edit: Mar 1st, 2004, 10:12pm by william wu » |
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Find Orders of A and B
« Reply #1 on: Feb 25th, 2004, 4:25pm » |
Quote Modify
|
:: Since a7=e, the order of a is either 1 or 7.
Case 1: order of a is 1. Then a=e, and aba-1 = b = b2, so b = e as well.
Case 7: order of a is 7.
Claim: akba-k = b2^k.
Proof: Induction on k: ak+1ba-k-1 = ak(aba-1)a-k = akb2a-k = (akba-k)2 = (b2^k)2 = b2^(k+1).
Now: b = ebe = a7ba-7 = b128
b127 = 1
Since 127 is prime, the order of b is therefore either 1 or 127.
Thus the possibilities for order of (a,b) are (1,1), (7,1), and (7,127). ::
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Find Orders of A and B
« Reply #2 on: Feb 26th, 2004, 8:52am » |
Quote Modify
|
A few follow-ups. In each case, it is needed to determine the order of the group G generated by two elements a, b subject to the following relations:
1. a3 = b2 = (ab)2 = 1.
2. a3 = b2 = (ab)3 = 1.
3. ab2 = b3a; ba3 = a2b.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Find Orders of A and B
« Reply #3 on: Feb 26th, 2004, 3:56pm » |
Quote Modify
|
1. a has order 3, b has order 2.
bb = abab, so b = aba, and ba = a-1b = aab.
Also ab = (ab)-1 = b-1a-1 = baa.
It's easy to see that with these relations, the set G = {1, a, aa, b, ab, ba} is closed under multiplication, and that it contains 6 distinct elements. In fact G [approx] S3.
2. |G| is at least 12, but that's all I know so far.
3. I don't really know a good method for doing these in general.
|
|
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Find Orders of A and B
« Reply #4 on: Mar 1st, 2004, 10:11pm » |
Quote Modify
|
Oops. I forgot to mention that b [ne] e. Sorry about that. But anyways you got the answer, nice job 
|
| « Last Edit: Mar 1st, 2004, 10:12pm by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Find Orders of A and B
« Reply #5 on: Mar 7th, 2004, 3:43am » |
Quote Modify
|
on Feb 26th, 2004, 3:56pm, Eigenray wrote:| 3. I don't really know a good method for doing these in general. |
|
Given:ab2 = b3a (1) ba3 = a2b (2)
Using (1):
a2b4a-2 = a(ab2)b2a-2 = a(b3a)b2a-2 = ab3(ab2)a-2 = ab3(b3a)a-2 = ab6a-1 = b9 (3)
(the last identity is because ab2a-1 = b3). Using (2) and (3):a2b4a-2 = b-1(a2b4a-2)b = (b-1a2b)b4(b-1a-2b) = a3b4a-3, which implies:
ab4 = b4a (4)
Using (1) and (4): ab4 = b4a = b(b3a) = bab2,
which implies ba = ab2 = b3a, so b2 = 1. Then, (1) becomes a = b3a, and finally b = 1. Similarly, a = 1, and |G| = 1.
|
|
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Find Orders of A and B
« Reply #6 on: Dec 27th, 2006, 11:22am » |
Quote Modify
|
Eigenray wrote:
Quote:| 3. I don't really know a good method for doing these in general. |
|
There is a process that does more, called Todd-Coxeter-Sims Coset enumeration, that constructs a permutation representation for the largest group generated by given elements and defining relations. The process (along with a ton of other goodies) is available free online in software called GAP.
Sometimes, this process can be carried out by hand. We compute the cosets of the subgroup generated by a for Barukh's problem 2.
a a a b b a b a b a b
1 1 1 1 1 1 1 1 _____1 (Sorry about the underline. Couldn't get the last "1" to line up.)
The first row above lists the relations. The second row lists how each element acts on the cosets of <a>, with 1 representing the right coset <a>. Since a is in <a>, a fixes this coset. Since each relation equals the identity of the whole group, the second row indicates that bb and ababab fixes 1. Now we begin filling in blank spaces with new numbers consistently, that is, if a sends x to y somewhere among the tables, it must do the same everywhere in the tables. If a generator sends an x to y one place in the table and generator sends x to z somewhere else in the table, then we have discovered that coset y equals coset z and we replace all occurences of z with y. Once all gaps in the table are filled with no inconsistencies, we have a permutation representation for the group generated by the generators and given defining relations. Continuing, we fill in a gap with 2 everywhere we can and start a new row. We get
a a a b b a b a b a b
1 1 1 1 1 2 1 1 1 2 2 1
2 2 2 1 2 2 2 1 1 2
Fill in another gap:
a a a b b a b a b a b
1 1 1 1 1 2 1 1 1 2 3 2 1
2 3 2 2 1 2 2 3 2 1 1 2
3 3 3 3 3 __________3
Fill in another gap:
a a a b b a b a b a b
1 1 1 1 1 2 1 1 1 2 3 4 2 1
2 3 4 2 2 1 2 2 3 4 2 1 1 2
3 4 2 3 3 4 3 3 4 3 4 3 4 3
4 2 3 4 4 3 4 4 2 1 1 2 3 4
Done! The element a is represented by the permutation (234) and that for b is (12)(34). Since <a> is represented faithfully, it follows that Barukh's problem 2 has order 12 and is isomorphic to A4.
Try coset enumeration on the group with generators and defining relations a-1bab=b-1aba=1.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print