| Title: | Mathematics at DEC |
| Moderator: | RUSURE::EDP |
| Created: | Mon Feb 03 1986 |
| Last Modified: | Fri Jun 06 1997 |
| Last Successful Update: | Fri Jun 06 1997 |
| Number of topics: | 2083 |
| Total number of notes: | 14613 |
Suppose we have a (non-commutative) group with two generators (a and b),
such that for any element x in the group, x^5 = I (the identity element).
How many elements can be in the group?
For example, here are a few distinct elements in the largest such group:
I,
a^i, b^i (i = 1,2,3,4)
a^i b^j, b^i, a^j (i,j = 1,2,3,4)
a^i b^j a^k, b^i a^j b^k (i,j,k = 1,2,3,4)
a^i b^j a^k b^l, b^i a^j b^k a^l (i,j,k,l = 1,2,3,4)
But note that ababab is not distinct from the above, since
a b a b a b = b^4 a^4 b^4 a^4
[ To see this, multiply each side by abab on the right:
(a b a b a b) (a b a b) = (b^4 a^4 b^4 a^4) (a b a b)
(a b)^5 = b^4 a^4 b^4 b a b
I = b^4 a^4 a b
I = b^4 b = I
These steps are easily reversed. ]
I believe that there may be an infinite number of elements in the group,
but can't prove it.
The next two pages discuss x^n = I for n = 2 and 3.
For n = 4 or 6, it's also known that the number of elements is finite.
If the relation were x^2 = I, then there are at most 4 elements in the group,
(I, a, b, and ab), as the following multiplication table shows. Note that:
b a = a^2 (b a) b^2 = a (a b)^2 b = a b
Y
X*Y | I a b ab
-----+-------------------
I | I a b ab
X a | a I ab b
b | b ab I a
ab | ab b a I
If the relation were x^3 = I, we'd have the following 27 elements:
(inverses are adjacent to each other).
a aa b bb ab bbaa ba baba
aab bba aba bab abb baa aaba aabba
abaa abbaa abba aabaa babb abbab bbab bbaab
bbaaba bbabaa I
BTW, these can all be formed by:
a^i b^j (bbaaba)^k (i,j,k = 0,1,2)
You can double-check that the above list is complete by forming the
table (as was done for x^2 = I), or you can check that:
(a^i b^j (bbaaba)^k) * (a^x b^y (bbaaba)^z)
= a^i b^j a^x (bbaaba)^k b^y (bbaaba)^z
( since 'a' and 'bbaaba' commute )
= a^i a^x b^j (bbaaba)^(j*x) (bbaaba)^k b^y (bbaaba)^z
( since 'ba' = 'a b (bbaaba)', )
( and 'a' and 'bbaaba' still commute )
= a^(i+x) b^(j+y) (bbaaba)^(j*x+k+z)
( since 'b' and 'bbaaba' commute )
And so we have closure of the product.
| T.R | Title | User | Personal Name | Date | Lines |
|---|---|---|---|---|---|
| 918.1 | HPSTEK::XIA | Tue Aug 16 1988 15:26 | 8 | ||
re .0
I do not believe that there can be infinite elements in that group.
Of course, I cannot prove that. However, I will give you my
intuition... I believe there is a maximum length for the string
containing the symbol a's and b's, and beyond that length the string
will contain a 5 repetition of a substring. This maximum length
is huge but nevertheless fininte. Of course, I may be wrong....
Eugene
| |||||
| 918.2 | BEING::POSTPISCHIL | Always mount a scratch monkey. | Tue Aug 16 1988 17:38 | 10 | |
Re .1:
There's a proof by Gilbert in topic 203 that three characters can be
used to make an arbitrarily long string without two adjacent
repetitions. Let those three "characters" be "a", "ab", and "abb" and
you can construct an arbitrarily long string without five adjacent
repetitions of any substring.
-- edp
| |||||
| 918.3 | Wondering | POOL::HALLYB | The smart money was on Goliath | Wed Aug 17 1988 18:30 | 16 |
Peter, can you construct a table of known maximum-group-sizes?
N |N|
- ----
2 4
3 27
4 ?
5 TBD
6 ?
etc.
Can anybody find an element that is not one of the ones Peter listed?
I can write, say, b^3 a^2 b^2 a b, but that may or may not simplify
like Peters "ababab" example.
John
| |||||
| 918.4 | random semi-relevant comments | HERON::BUCHANAN | and the world it runnes on wheeles | Wed Aug 24 1988 07:01 | 46 |
This is hard, and quite possibly unsolved. I seem to remember that these things are called Burnside groups, B(m,r), where each element satisfies X^m = 1, and there are r generators for the group. We're talking about B(5,2). When I was small, (ie a student), I think I read about it in Marshall Hall's tome. It detailed the proofs for m = 3, and gave a sketch of m = 4 and 6, and spoke of other m as unsolved. Since the kind of mechanisms that were being used for 3,4,6 are inductive, it's not necessarily the case that showing B(5,2) is finite is much easier than showing B(5,r) is finite for all r. Now group theory has moved on since then. In particular, there are a lot of computer tools available for exploring group presentations, and I'm sure in CAYLEY there will be something there which could be used to tackle *specifically* B(5,2). Does anyone have experience of this computer algebra tool? I don't. One blind alley that I thought of this morning is as follows. B(3,2), the group with 27 elements, is IM to a certain group of matrices. Take the set of 3 by 3 matrices over the field with 3 elements. Take the subset consisting of those matrices A(i,j) with i < j => A(i,j) = 0 i = j => A(i,j) = 1 ie the lower diagonal matrices with unity in the main diagonal. This set is a group, and each non-identity element has order three (to see this, regard each element as a sum of matrices D(k) which are empty everywhere except the k'th diagonal. (let the main diagonal be the 0'th)). There are exactly 27 matrices in this group. Can we generalize? Let's take p prime, and look at d by d matrices over the field F(p), where d =< p. The lower diagonal matrices with unity in the 0'th diagonal form a group, where each element satisfies X^p = 1. Bingo! But there's a catch: how many generators are there? Examining the 1'st diagonal, it's clear that d-1 generators at least will be necessary in order to span all the possible values that can be loaded in there. (If we quotient out the normal subgroup of those guys which are zero in the 1'st diagonal, then we're left with the group (Cp)^(d-1)). So for two generators, we'd need d = 3, which is boringly small, and I can't believe that B(5,2) is as teeny as 125. Finally, I seem to recall that B(3,r) has order 3^(2^r - 1), proved by building B(3,r) from B(3,r-1) and another generator. | |||||