Martin Rubey
2008-08-13 13:36:16 UTC
Dear Mike, Ralf, Robert, *,
I spent the last couple of days reading Adalbert Kerber's "Applied Finite Group
Actions" (Second Edition), and I understand now how things (Compose and
FunctorialCompose) could be done properly. Fortunately, it doesn't seem to be
too complicated, except for the stuff that Robert is working on anyway... I'd
like to share this with you in what follows. I hope I'm not being to terse
(don't hesitate to ask), nor too slow.
I'd like to stress that comments are very much appreciated - I was a little
disappointed that I didn't get any comments on my previous post.
I'll start with FunctorialCompose, since this is actually easier to explain.
(It is more difficult to implement though, as Robert certainly knows...)
We want to generate the isomorphism types of F#G[U] = F[G[U]], where F and U
are species (i.e., functors from finite sets/bijections to finite
sets/bijections, or if you prefer, rules that produce labelled structures given
a set of labels, that are invariant under relabelling.)
One can think of an F#G structure as an F-structure on *all* G structures. As
an example, take F=p, the species of subsets, and G=p2, the species of subsets
with 2 elements, then F#G is the species of graphs: subsets of all 2-subsets.
Taking F=p4, we obtain the species of graphs with 4 edges.
Two structures s1 and s2 are isomorphic, if there is a permutation pi, such
that F[G[pi]](s1) = s2. (Recall that a species naturally assigns to a
permutation of the labels a permutation of the structures.)
Thus, to generate orbit representatives of (F#G)[U], we have to
1) compute the action of G[pi] on G[U]
2) compute representatives of F-structures, *under this action*.
-------------------------------------------------------------------------------
The group H corresponding to the action of G[pi] on G[U] is of course a
subgroup of the symmetric group S_{G[U]} permuting the elements of G[U]. But
H is somewhat special: we have
S_{G[U]} H = H
(this is equality, not isomorphism!) In words: it's a subgroup that's
invariant under relabelling. Equivalently, if h is an element of H and the
cycletype of h is (n1,n2,...), then *all* elements of S_{G[U]} with this
cycletype are also in H.
Unfortunately, we cannot restrict ourselves to this kind of groups if we want
to be able to compute isotypes of (ordinary, i.e. "plethystic") composition,
too. Still, it would be nice to be able to take advantage of this special
group structure, whenever we can.
More precisely, for the plethystic composition, it turns out that it is
necessary to be able to compute representatives of F-structures under the
action of a Young subgroup S_n1 x S_n2 x S_n3 x..., and Young subgroups are of
course not of this type.
Note that computing isomorphism types S_n1 x S_n2 x ... can be done efficiently
(using algorithms of Knuth and Ruskey), so we really should keep this special
case. In the aldor-combinat project (iso-experiment branch), I did this by
implementing for each species a function isomorphismTypes, that take a multiset
1^n1, 2^n2, ... as input, and output structures, where we have n1 labels 1, n2
labels 2 and so on.
Similarly, I guess that the best way to accomplish 1) and 2) is to implement
for every species F two functions:
inducedAction(H: Subgroup of S_n): Subgroup of S_{F[n]}
(actually, I think it is sufficient to be able to compute inducedAction(S_n),
but being more general certainly won't hurt.)
isomorphismTypes(U: Set, H: Subgroup of S_U): Generator %
To be honest, there is one thing I do not understand yet: in what form do we
need H to be able to compute the isomorphismTypes, along the lines of Laue,
Kerber, McKay, Read, etc. I guess it is easiest to just give a set of
generators? Robert, would this be enough for you?
-------------------------------------------------------------------------------
The two most important species are k-Subsets, and set partitions.
At least for the species k-Subsets, the function isomorphismTypes can be
implemented as described in Adalbert Kerber's book Chapter 9, in particular
9.2. After all, we just need to generate orbit representatives of H\\2^U.
I'm not sure how to do Partitions (let's say, into k-parts), I must admit, but
I'd guess that it will be of similar difficulty.
Given these two, it is very easy to implement the constructors Plus, Times, and
FunctorialCompose. (Plethystic) Compose is a little trickier, it should work
very similar to the algorithm in the iso-experiment branch of aldor combinat.
We will then get all kinds of trees, graphs, relations, ...
Let's consider the times constructor, as an example. H being a subgroup of S_U,
I'll write Iso(F, H) [U] for a set of representatives of F[U] under the action
of H. We have
F G [U] = sum_{(U1, U2) in Subsets[U]} F[U1] x G[U2].
And it's straightforward to check that
Iso((F G), H) [U] = sum_{(U1, U2) in Iso(Subsets, H)[U]}
Iso(F, H|U1)[U1] x Iso(G, H|U2)[U2]:
just note that an (F G) structure is of the form
((U1, U2), f in F[U1], g in G[U2]).
Applying a permutation pi transports it to
((pi U1, pi U2), F[pi](f) in F[pi U1], G[pi](g) in G[pi U2]).
-------------------------------------------------------------------------------
I hope this is a feasible programme,
Martin
-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/
I spent the last couple of days reading Adalbert Kerber's "Applied Finite Group
Actions" (Second Edition), and I understand now how things (Compose and
FunctorialCompose) could be done properly. Fortunately, it doesn't seem to be
too complicated, except for the stuff that Robert is working on anyway... I'd
like to share this with you in what follows. I hope I'm not being to terse
(don't hesitate to ask), nor too slow.
I'd like to stress that comments are very much appreciated - I was a little
disappointed that I didn't get any comments on my previous post.
I'll start with FunctorialCompose, since this is actually easier to explain.
(It is more difficult to implement though, as Robert certainly knows...)
We want to generate the isomorphism types of F#G[U] = F[G[U]], where F and U
are species (i.e., functors from finite sets/bijections to finite
sets/bijections, or if you prefer, rules that produce labelled structures given
a set of labels, that are invariant under relabelling.)
One can think of an F#G structure as an F-structure on *all* G structures. As
an example, take F=p, the species of subsets, and G=p2, the species of subsets
with 2 elements, then F#G is the species of graphs: subsets of all 2-subsets.
Taking F=p4, we obtain the species of graphs with 4 edges.
Two structures s1 and s2 are isomorphic, if there is a permutation pi, such
that F[G[pi]](s1) = s2. (Recall that a species naturally assigns to a
permutation of the labels a permutation of the structures.)
Thus, to generate orbit representatives of (F#G)[U], we have to
1) compute the action of G[pi] on G[U]
2) compute representatives of F-structures, *under this action*.
-------------------------------------------------------------------------------
The group H corresponding to the action of G[pi] on G[U] is of course a
subgroup of the symmetric group S_{G[U]} permuting the elements of G[U]. But
H is somewhat special: we have
S_{G[U]} H = H
(this is equality, not isomorphism!) In words: it's a subgroup that's
invariant under relabelling. Equivalently, if h is an element of H and the
cycletype of h is (n1,n2,...), then *all* elements of S_{G[U]} with this
cycletype are also in H.
Unfortunately, we cannot restrict ourselves to this kind of groups if we want
to be able to compute isotypes of (ordinary, i.e. "plethystic") composition,
too. Still, it would be nice to be able to take advantage of this special
group structure, whenever we can.
More precisely, for the plethystic composition, it turns out that it is
necessary to be able to compute representatives of F-structures under the
action of a Young subgroup S_n1 x S_n2 x S_n3 x..., and Young subgroups are of
course not of this type.
Note that computing isomorphism types S_n1 x S_n2 x ... can be done efficiently
(using algorithms of Knuth and Ruskey), so we really should keep this special
case. In the aldor-combinat project (iso-experiment branch), I did this by
implementing for each species a function isomorphismTypes, that take a multiset
1^n1, 2^n2, ... as input, and output structures, where we have n1 labels 1, n2
labels 2 and so on.
Similarly, I guess that the best way to accomplish 1) and 2) is to implement
for every species F two functions:
inducedAction(H: Subgroup of S_n): Subgroup of S_{F[n]}
(actually, I think it is sufficient to be able to compute inducedAction(S_n),
but being more general certainly won't hurt.)
isomorphismTypes(U: Set, H: Subgroup of S_U): Generator %
To be honest, there is one thing I do not understand yet: in what form do we
need H to be able to compute the isomorphismTypes, along the lines of Laue,
Kerber, McKay, Read, etc. I guess it is easiest to just give a set of
generators? Robert, would this be enough for you?
-------------------------------------------------------------------------------
The two most important species are k-Subsets, and set partitions.
At least for the species k-Subsets, the function isomorphismTypes can be
implemented as described in Adalbert Kerber's book Chapter 9, in particular
9.2. After all, we just need to generate orbit representatives of H\\2^U.
I'm not sure how to do Partitions (let's say, into k-parts), I must admit, but
I'd guess that it will be of similar difficulty.
Given these two, it is very easy to implement the constructors Plus, Times, and
FunctorialCompose. (Plethystic) Compose is a little trickier, it should work
very similar to the algorithm in the iso-experiment branch of aldor combinat.
We will then get all kinds of trees, graphs, relations, ...
Let's consider the times constructor, as an example. H being a subgroup of S_U,
I'll write Iso(F, H) [U] for a set of representatives of F[U] under the action
of H. We have
F G [U] = sum_{(U1, U2) in Subsets[U]} F[U1] x G[U2].
And it's straightforward to check that
Iso((F G), H) [U] = sum_{(U1, U2) in Iso(Subsets, H)[U]}
Iso(F, H|U1)[U1] x Iso(G, H|U2)[U2]:
just note that an (F G) structure is of the form
((U1, U2), f in F[U1], g in G[U2]).
Applying a permutation pi transports it to
((pi U1, pi U2), F[pi](f) in F[pi U1], G[pi](g) in G[pi U2]).
-------------------------------------------------------------------------------
I hope this is a feasible programme,
Martin
-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/