wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Find Orders of A and B
        
(Message started by: william wu on Feb 25^th, 2004, 1:48pm)

Title: Find Orders of A and B
Post by william wu on Feb 25^th, 2004, 1:48pm

I have a group G containing elements a and b such that

a⁷ = e
aba^-1 = b²
b [ne] e

Find the orders of a and b.

Title: Re: Find Orders of A and B
Post by Eigenray on Feb 25^th, 2004, 4:25pm

:: [hide]Since a⁷=e, the order of a is either 1 or 7.

Case 1: order of a is 1. Then a=e, and aba^-1 = b = b², so b = e as well.

Case 7: order of a is 7.
Claim: a^kba^-k = b^{2^k}.
Proof: Induction on k: a^k+1ba^-k-1 = a^k(aba^-1)a^-k = a^kb²a^-k = (a^kba^-k)² = (b^{2^k})² = b^{2^(k+1)}.
Now: b = ebe = a⁷ba^-7 = b¹²⁸
b¹²⁷ = 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).[/hide] ::

Title: Re: Find Orders of A and B
Post by Barukh on Feb 26^th, 2004, 8:52am

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. a³ = b² = (ab)² = 1.
2. a³ = b² = (ab)³ = 1.
3. ab² = b³a; ba³ = a²b.

Title: Re: Find Orders of A and B
Post by Eigenray on Feb 26^th, 2004, 3:56pm

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] S₃.

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.

Title: Re: Find Orders of A and B
Post by william wu on Mar 1^st, 2004, 10:11pm

Oops. I forgot to mention that b [ne] e. Sorry about that. But anyways you got the answer, nice job :)

Title: Re: Find Orders of A and B
Post by Barukh on Mar 7^th, 2004, 3:43am

on 02/26/04 at 15:56:24, Eigenray wrote:

3. I don't really know a good method for doing these in general.

Given:ab² = b³a (1) ba³ = a²b (2)
Using (1):
a²b⁴a^-2 = a(ab²)b²a^-2 = a(b³a)b²a^-2 = ab³(ab²)a^-2 = ab³(b³a)a^-2 = ab⁶a^-1 = b⁹ (3)
(the last identity is because ab²a^-1 = b³). Using (2) and (3):a²b⁴a^-2 = b^-1(a²b⁴a^-2)b = (b^-1a²b)b⁴(b^-1a^-2b) = a³b⁴a^-3, which implies:
ab⁴ = b⁴a (4)
Using (1) and (4): ab⁴ = b⁴a = b(b³a) = bab²,
which implies ba = ab² = b³a, so b² = 1. Then, (1) becomes a = b³a, and finally b = 1. Similarly, a = 1, and |G| = 1.

Title: Re: Find Orders of A and B
Post by ecoist on Dec 27^th, 2006, 11:22am

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 A₄.

Try coset enumeration on the group with generators and defining relations a^-1bab=b^-1aba=1.