| -< the near miss of .0 >-
with(group);
grouporder(permgroup(10, {
a = [[10,1],[2,3],[4,5],[6,7],[8,9]],
b = [[1,2],[3,4],[5,6],[7,8],[9,10]],
c = [[10,1],[2,9],[3,4],[5,8],[6,7]],
d = [[10,1],[2,9],[3,8],[4,7],[5,6]] } ));
MAPLE tells me this group has order 7200. To see that the
Coxeter constraints hold, draw the vertices in a circle, and link them
by (undirected) edges labeled a,b,c or d. Checking the interactions
between each pair of labels is enlightening in discovering the approach
I've used to devise this group.
Regards,
Andrew.
|
| (1) Lightning tour of Coxeter graphs, including an example
I haven't any documentation on the subject, but this is my guess at
the theory.
The Coxeter graph for a group is a neat way of describing the
group, based on a set of generators which are involutions (ie order 2)
and have relatively little interaction. It is specifically oriented
towards finding permutation representations of abstract groups.
So for instance, a Coxeter graph could be:
0-----0-----0-----0
A model for this is S5:
s1 = (12)
s2 = (23)
s3 = (34)
s4 = (45)
Note that if |i-j| <> 1, then si.sj = sj.si. If |i-j| = 1, on the
other hand, then si.sj will have order 3. <s1,s2,s3,s4> = S5. The trickiest
thing to check is that the representation of the abstract group is faithful.
If one knows the order of the abstract group, then it is sufficient that the
perm group has the same order.
I seem to recall that even the Monster group (the largest sporadic
finite simple group) has a stunningly tiny Coxeter graph which consists of
sixteen points, arranged in a Y, with each leg of the Y having the same length.
And that is enough to define the group!
(2) A different kind of graph structure.
Suppose that we have a Coxeter graph, C, for some group G. And we
want to build a permutation representation of G inside Sn. For any involution
si, we can draw a graph Di on n vertices. vk will connect to vl in Di iff si
swaps them. Each vertex will have degree 1 or 2 in Di, since si is an
involution. So Di is a union of graphs each of the form K1 or K2 (complete
graphs on one or two vertices).
Interesting things happen when we superimpose Di & Dj to form a
multi-graph Eij. Suppose that si.sj has order x > 1. Eij will be composed of
components, selected from the following menu:
C(2x) The cyclic graph on 2x vertices
Lx The linear graph on x vertices (cyclic graph lacking 1 edge)
B2 Two points, linked by 2 edges
K1
Notes:
(1) There will be at least one component from one of the top two
categories in the menu.
(2) In any component, the edges will be alternately labelled i & j.
Two edges with the same label cannot be incident to the same vertex.
This conceptual machinery is quite powerful already:
Lemma:
If the Coxeter graph C is connected, and if no edge on it is labelled
with an even number, then in any permutation representation of G, there will
be a number m such that each Di has size m (ie: contains exactly m edges).
Proof:
Limpid :-).
In all that follows we'll assume that the preconditions of this lemma
hold. So all Di have the same size.
(3) H3
5
0-----0-----0
We are told that the group has 120 elements.
Suppose that n = 5. Then m = 1 or 2, since 2m =< n. If m = 2,
then each si is even, and we can at best create 60 elements. So m = 1.
But you can't create L5 or C10 with only 2*1 = 2 edges! So n > 5.
Suppose that n = 6. m = 1, 2 or 3. m = 1 is too small and m = 3 is
too big, to permit the construction of L5 in E12. So m = 2, and D12 is
1 2 1 2
x-----x-----x-----x-----x x
(using "x" for vertices to distinguish this graph from Coxeter graph.)
The only way that this can be extended to s3, whilst doing *something*
to the lonely 6th vertex (else we just have S5 again) is:
1/3 2 1 2 3
x-----x-----x-----x-----x-----x
(1/3 denotes double edge.)
This corresponds to:
s1 = [[1,2],[3,4]],
s2 = [[2,3],[4,5]],
s3 = [[1,2],[5,6]].
and doughty MAPLE tells us there are only 60 elements, so forget it.
We have presumably stumbled across have of PS(2,5), which we know lives in S6.
So, now let's look at n = 7. m = 2 or 3, as above. If m = 2, then
it's hopeless, while m = 3 forces D12 to be:
1 2 1 2 1/2
x-----x-----x-----x-----x x-----x
This extends only to:
1 2/3 1 2 1/2/3
x-----x-----x-----x-----x x-----x
| |
+-----------------+
3
which gives us the desired result: 120 elements.
(4) H4.
5
0-----0-----0-----0
We have to be smarter here.
Try n = 10. m = 1,2,3,4 or 5. m = 1 is too small to exhibit an L5.
But where next?
Lemma:
Given E12, and p such that s1.sp & s2.sp have order 2, we construct the
graph F12p by extending E12 through adding edges lablled p. Take a component
z of E12. One of the following holds:
(1) no vertex of z is incident with any edge labelled p
(2) every vertex of z is adjacent with another vertex of z,
via an edge labelled p. z has even order.
(3) there is a component z', such that every vertex of z is
adjacent to one vertex in z'. z & z' are IM as subgraphs of E12.
Proof:
The force is with me. Feel the truth.
So what possibilities are there for E12?
(i) C10 alone, m = 5
(ii) 2*L5, m = 4
(iii) L5, 2*B2, K1, m = 4
(iv) L5, B2, 3*K1, m = 3
(v) L5, 5*K1, m = 2
Let's save (i) till last. Otherwise, take p = 4, & z to be L5.
(ii) case (1) no: m = 4
(2) no: L5 has odd order
(3) no: bijection involves 5 edges labelled 4, but m = 4
(iii)->(v) cases (2) & (3) not possible, as above. So case (1), so no edges
labelled 4 hit L5, so m =< 2, so only (v) has a glimmer of hope. Using 4*K1,
build 2 K2 labelled 4:
1 2 1 2 4 4
x-----x-----x-----x-----x x-----x x-----x x
Now the edges labelled 3. One must affect the lonesome vertex, and
must be incident at least with each edge labelled 2 or 4. Too much work, not
possible.
Now return to (i). Take z = C10, and p = 4. case(2) is the only
solution. If 4 links vi & v(i+j), where j is odd, then 4 links v(i+1) &
v(i+j+1), & so on, all the way round. This is not possible while each vertex
has only one incidence with an edge labelled 4. So 4 links v(i) & v(i+j),
where j is even. Drawing the diagram will convince you that the only
solution is:
s1 = [[1,2],[3,4],[5,6],[7,8],[9,0]]
s2 = [[0,1],[2,3],[4,5],[6,7],[8,9]]
s4 = [[0,1],[2,9],[3,8],[4,7],[5,6]]
or some rotation of it. Now consider E23. Since m = 5, it must be C6, 2*B2
Similarly for E24. This together with the commuting of s3 with s1, forces
s3 = [[0,1],[6,7],[2,9],[3,4],[5,8]]
MAPLE tells us this has only order 7200 as a group, so n = 10 is
impossible. Next for n = 11...
regards,
Andrew
|
| (1) Completely different theory -the right one
Suppose that I have a group G, and that I am lucky enough not
only to have a presentation in terms of generators and relators, but
also to have a permutation representation of G (not necessarily faithful for
the moment).
I can then construct an edge-decorated multigraph, U, which shows the
actions of the generators upon the elements permuted. What will this
graph look like?
Well, first of all, each component of U is entirely independent of all
the others. So, let's examine one such component (orbit). It is going to
be the Schreier diagram, V, for G with respect to some subgroup H of G. The
order of the orbit will be simply the index G:H. [See note 1018ish for
what these diagrams are all about.]
Now comes the question of faith. For simplicity, let's say that
we just have a single component for the moment. Then I have a homomorphism,
@, from G to J, the AM group of V, defined by:
@(g) sends Hx to Hxg for all x,g in G.
@(g) is well-defined for all g, so @ is well-defined. The object of
interest is the kernel of @, that is:
g such that Hx = Hxg for all x in G, i.e.
g such that xgx' lies in H, for all x in G. (' denotes inverse)
ie.: ker(@) is the intersection, /\ of all the conjugates of H.
In particular, if H is normal in G, then ker(@) = H itself. A
permutation representation is faithful iff ker(@) = 1, so the only normal
subgroup which gives a faithful representation is the trivial H = 1. Non-
normal subgroups are therefore a much better choice if we're looking for
faithful permutation representations.
But we are not restricted to taking just one orbit. We can have
as many subgroups H_i as we choice, let K_i = /\ xH_ix' over x.
Then the perm rep is faithful iff:
/\K_i = 1.
The degree of the permutation representation induced is:
sum [G:H_i]
Now to find a faithful permutation representation of smallest degree
for a given group G is a question of recreational interest :-).
(2) H3
We know that H3 = S2 x A5
(This is the first time I've ever encountered "naturally" a group
of order 120 which wasn't S5 :-)
Take H_1 = S2 x A4
H_2 = {1} x A5
Now, conjugates are always easy to calculate in An or Sn...
So K_1 = S2 x {1}
K_2 = {1} x {A5}
And /\K_i = {1} x {1}, so this perm rep is faithful.
The degree of the perm rep = [G:H_1] + [G:H_2] = 5 + 2 = 7
H_1 & H_2 are maximal proper subgroups of G. There is a subgroup of
index 6, S2 x D5, but this is not faithful, since it contains a central
element (as does H_1.) So 7 is the best we can do.
A final point is that the non-identity element of K_1 is found to
be (s1.s2.s3)^5. This is an important pointer for the more difficult H4
below.
(3) H4
Trickier, but let's build towards the solution from what we know.
We have a subgroup H_1 such that J_1 is a perm group of degree 10
and order 7200. Since we are told that H4 has order 14400, this means that
|K_1| = 2. This means that H_1 contains a single non-identity element that
is central in H4.
H_4 has a normal subgroup, N, of order 2. The non-identity element
of N, k, is central to H_4. If H_1 does *not* contain k, we could create a
subgroup H' by adjoining k to H_1. H_1 has index 10 in H_4; H' would have
index 5 in H4. However, there is no Schreier diagram that can be built for H'
which adheres to the Hoffman diagram constraints for s1,s2,s3,s4, as a little
experimentation will convince you. Therefore H' cannot exist, and k is now
recognized to be the central element lying in H_1 and hence K_1. It seemed
likely.
What is k in terms of the generators? For H3, (s1.s2.s3)^5 was a
critical element, so we can explore l = (s1.s2.s3.s4) for H4. Its image in
J_1 is (1 9 5 7 3)(2 8 10), which has order 15, so if l^15 is not 1, then
it must be k. MAPLE reports that grouporder(pres(subgrel(l,H4))) is 30, so
k = (s1.s2.s3.s4)^15.
(4) Tasks still to do (but not by me :-)
So we set H_2 to be the largest subgroup of G which excludes k. Only
then will K_2 exclude k, and will we have a faithful representation. Exactly
what this is, I haven't computed. One cute candidate would be a subgroup of
order 225, index 64. If such a subgroup existed, it could certainly not
include k.
Once we know the order of H_2, we can determine whether a faithful
representation of smaller degree could possibly exist. For instance, K_2
might be trivial, in which case we could dispense with H_1!
The point is this: the original poster suspected that since H3 had
a neat perm rep, so might H4. H3 had a neat perm rep because it was a
direct product, and so we could get a faithful perm rep as a direct sum.
H4 is not a direct product (I think) and so we can't get away with the same
trick.
Regards,
Andrew.
|
| J_1 has a normal subgroup of index 2, M, namely those which are
even permutations, and those which are odd. Moreover, any even
element of J_1 fixes setwise {1,3,5,7,9}. Furthermoreover, each even
element of J_1 acts as an even perm on {1,3,5,7,9}. But M must have order
3600, so in fact M is IM to A5 x A5.
We can define an AM, �, on A5 x A5, by �(x,y) = (y,x). This is
sufficient to specify J_1 as < M, a | a� = 1, ma = a�(m) for all m in M >.
We have a faithful perm rep of degree 130. Can we improve on it?
So we are interested in subgroups of G of order > 14400/130 = 110+, not
containing k. This means we are interested in subgroups of J_1 of order >=
111, since only such groups could be the image under the HM with kernel <k>
of a group that does not contain k. This means we want to track subgroups of
M of order >= 56.
A subgroup of a Cartesian product, XxY, is contained within some
smallest Cartesian product, AxB, which is a subgroup of XxY. Let's first find
out what those subgroups AxB could be.
I claim that A5 has no proper subgroups of order > 12. This is
because any subgroup induces a HM from A5 to a permutation group on the
cosets, and the kernel of the HM is a normal subgroup of A5, hence is either
1 or A5. So the subgroup is either A5 or has index >= 5.
For instance, A5 has no subgroup of order 15, so G has no subgroup
of order 225, as we wondered yesterday. etc, etc.
Regards,
Andrew
|
| In the previous reply, I picked out the subgroups of the form
XxY of A5xA5 which could be relevant. What others subgroups of A5 could
there be, which are *not* of that form?
Well, there's not many. If S is a subgroup of XxY, then say it is
*spanning* if for all x in X there exists y in Y such that (x,y) lies in S,
and similarly for all y in Y, there exists x in X ditto. So every subgroup
of XxY spans *some* unique group X'xY'.
A spaanning subgroup of XxY will have a certain number of elements of
the form (1,y). The elements y form a subgroup of Y, Y". But moreover Y"
is normal in Y. Why?
Given y" in Y", for each y in Y, by spanningness, there is an x such
that (x,y) is in S. Then (x,y)^(-1).(1,y").(x,y) = (1,y^(-1).y".y). But
this has x component 1, so the y component lies in Y". So Y" is normal.
Similarly X" is normal in X.
Also, [X:X"] = [Y:Y"]. [Question: are X/X" & Y/Y" IM?].
Now, from the previous reply, we know all the possible groups which
could be spanned. Firstly, there are those which have X or Y (wlog, say Y)
IM to A5. A5 is simple, so Y" = A5 or 1. In the first case, the subgroup
of XxA5 isn't proper. In the second case, [Y:Y"] = 60 => X = A5, X" = 1.
So we have a subgroup order 60 of A5xA5. Elements take the form (x,f(x)),
where x runs through A5, and f is any AM of A5.
Suppose that neither X nor Y is A5, then |XxY| =< 144. Any proper
subgroup, S, must have index a square number in XxY. So |S| =< 36, which
are too small to be interesting to us.
Regards,
Andrew.
|