Help with permutation groups / gap wanted

[Martin R]

Dear permutation group / gap experts!

I would enjoy some expert help to implement the so called functorial composition of species.  The operation is easy to define even without mentioning combinatorial species, as follows:

Let Y = {1,2,...,N}

Let G: S_n x Y -> Y be a (left) action of the symmetric group S_n on Y.

Let F: S_N x X -> X be a (left) action of S_N on X.

Then we can define an action H: S_n x X -> X as follows:

For pi in S_n, let G_pi be the permutation of Y induced by the action G.  Then,

pi *_H x := G_pi *_F  x.

Currently, https://github.com/sagemath/sage/pull/40186 implements this in a very naive way.   It involves three functions:

sage.rings.lazy_species.FunctorialCompositionSpeciesElement.__init__.coefficient

(implementing the above)

sage.rings.species.PolynomialSpeciesElement.action

(used to turn a species into the corresponding action)

sage.rings.species._stabilizer_subgroups

(used to turn an action into a combinatorial species - i.e., a formal sum of stabilizer subgroups)

I would not be surprised if all three of them could be improved by applying some permutation-group-knowledge which I am lacking.  In fact, I tried to code this quickly, so it is quite likely that I even missed the most obvious things and did it completely backwards.

Best wishes,

Martin

[Dima Pasechnik]

On Sat, May 31, 2025 at 2:57 PM 'Martin R' via sage-devel
<sage-...@googlegroups.com> wrote:
>
> Dear permutation group / gap experts!
>
> I would enjoy some expert help to implement the so called functorial composition of species. The operation is easy to define even without mentioning combinatorial species, as follows:
>
> Let Y = {1,2,...,N}
>
> Let G: S_n x Y -> Y be a (left) action of the symmetric group S_n on Y.
> Let F: S_N x X -> X be a (left) action of S_N on X.
>
> Then we can define an action H: S_n x X -> X as follows:
>
> For pi in S_n, let G_pi be the permutation of Y induced by the action G. Then,
>
> pi *_H x := G_pi *_F x.

Should the last x be y? Anyhow, I am completely lost here - are X and
Y arbitrary? Or is Y a subset of X?
An example might help.

Dima

>
> Currently, https://github.com/sagemath/sage/pull/40186 implements this in a very naive way. It involves three functions:
>
> sage.rings.lazy_species.FunctorialCompositionSpeciesElement.__init__.coefficient
> (implementing the above)
> sage.rings.species.PolynomialSpeciesElement.action
> (used to turn a species into the corresponding action)
> sage.rings.species._stabilizer_subgroups
> (used to turn an action into a combinatorial species - i.e., a formal sum of stabilizer subgroups)
>
> I would not be surprised if all three of them could be improved by applying some permutation-group-knowledge which I am lacking. In fact, I tried to code this quickly, so it is quite likely that I even missed the most obvious things and did it completely backwards.
>
> Best wishes,
>
> Martin
>

> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
> To view this discussion visit https://groups.google.com/d/msgid/sage-devel/31413384-37a7-4666-8099-7e526ad03dd9n%40googlegroups.com.

[Dave Morris]

I was confused, too, but I think the point is that Y is assumed to be {1,2,...,N}.  So the action G is a homomorphism from S_n to S_N.  The action F is a homomorphism from S_N to the symmetric group on X.  We can compose these two homomorphisms to get an action of S_n on X.

To view this discussion visit https://groups.google.com/d/msgid/sage-devel/CAAWYfq0B1%3DDsnU1dEFAf%3DZbsVTDViDVjZAkYYoWL19NzFagUFA%40mail.gmail.com.

[Martin R]

> I think the point is that Y is assumed to be {1,2,...,N}.  So the action G is a homomorphism from S_n to S_N.  The action F is a homomorphism from S_N to the symmetric group on X.  We can compose these two homomorphisms to get an action of S_n on X.

Yes, that's correct.

Here is an example that can be done by hand.  Examples are easier to understand when X and Y are sets of combinatorial objects.  I replaced them with numbers above for simplicity of the definition.

Let N=4 and let n=2.  Let G be the action of S_2 on Y={(12),(21),(ab),(ba)} which switches the positions in the tuples, defined by 

(1,2) *_G (1,2) = (2,1) and 

(1,2) *_G (a,b) = (b,a).

Let F be the action of S_4 on cycles (or cyclic permutations, if you prefer) of length 4, that relabels the elements of a cycle (or, if you prefer, acting by conjugation).  That is., X={(1,2,3,4), (1,2,4,3), (1,3,2,4), (1,3,4,2), (1,4,2,3), (1,4,3,2)}, and, for example,

(2,1) *_F (1,2,3,4) = (2,1,3,4)

Then the functorial composition is an action of S_2 on the set X.  The most intuitive way to see it is to think of X as the set of cyclic permutations of Y, and S_2 acts by swapping the positions in the tuples.  For example:

(1,2) *_H ((12), (ab), (21), (ba)) = ((21), (ba), (12), (ab), so that's a fixed point, whereas

(1,2) *_H ((12), (21), (ab), (ba)) = ((21), (12), (ba), (ab) is not.

Does this help?

[Martin R]

Ideally, I would like to define this in terms of generators of associated permutation groups.  It is easy to see that it is sufficient to implement it, when F is a transitive action.  Note, however, that H is not necessarily transitive, even if F is.

To see (part of) the problem, replace the set Y in the example with a set of 2k pairs (i.e., in the example above, we have k=2), and F by the action of S_{2k} that relabels cycles.  We then obtain an action on a set with (2k-1)! elements.  (It's not hard to see that it has 2^{k-1} (k-1)! fixed points.)

A priori, the actions F and G are given as formal sums of permutation groups (i.e., the stabilizer subgroups), which is quite efficient.  In the example, F corresponds to the cyclic permutation group with generator (1,...,2k). To implement the above, I turn then into actual actions.  In particular, I actually compute the sets X and Y, and they are simply too large.

However, even optimizing the helper function _stabilizer_subgroups would be very interesting.

Best wishes,

Martin

[Martin R]

Here is one idea: perhaps I can rewrite `PolynomialSpeciesElement.action` so that it actually returns a gap action.  (it makes my brain spin every time I have to translate between species and group actions)

[Dima Pasechnik]

On Mon, Jun 2, 2025 at 3:10 AM 'Martin R' via sage-devel
<sage-...@googlegroups.com> wrote:
>
> Here is one idea: perhaps I can rewrite `PolynomialSpeciesElement.action` so that it actually returns a gap action. (it makes my brain spin every time I have to translate between species and group actions)

Indeed, you have S_n as a subgroup of S_N, because it acts on Y, with |Y|=N.
(and this is something you could have said explicitly).
Then, you have an action of S_N (on X). So all you do is you restrict
the latter action to its subgroup S_n (it could be any subgroup of
S_N, not necessarily isomorphic to S_n).
In GAP it's usual to encode actions as
https://docs.gap-system.org/doc/ref/chap41.html

HTH
Dima

> To view this discussion visit https://groups.google.com/d/msgid/sage-devel/09e510ca-e281-413a-9ab0-fd97a4735af4n%40googlegroups.com.

[Martin R]

> Indeed, you have S_n as a subgroup of S_N, because it acts on Y, with |Y|=N.
> (and this is something you could have said explicitly).

That's interesting, I never looked at functorial composition of species as restriction of group actions, but that's very promising.

I'm sorry I wasn't clear, most likely this is because I don't understand things well enough myself.

I think it matters that we want the image of S_n under the the action of G as a subgroup of S_N.

Unfortunately, I have some difficulties understanding how group actions work in gap, I just posted a question on the gap forum mailing list.

I hope that `FactorCosetAction` does exactly what I did naively in `PolynomialSpeciesElement.action`, but apparently, I do not understand `OrbitStabilizer` well enough.  Here is what I tried to get started:

gap> G := SymmetricGroup(4);
Sym( [ 1 .. 4 ] )

gap> H := Group([(1,2,3,4)]);
Group([ (1,2,3,4) ])

gap> a := FactorCosetAction(G, H);
<action epimorphism>

gap> Image(a);
Group([ (2,5,4,3), (1,4)(2,6)(3,5) ])

gap> OrbitStabilizer(G, 1, GeneratorsOfGroup(G), GeneratorsOfGroup(Image(a)));
rec( orbit := [ 1, 4, 3, 2, 5, 6 ], stabilizer := Group([ (1,2,3,4) ]) )

gap> OrbitStabilizer(G, 1, a);
rec( orbit := [ 1, 4, 2, 3 ], stabilizer := Group([ (2,4), (3,4) ]) )

I would have expected that the last two calls give the same result.  Perhaps 1 should be replaced with a coset in the second call, but I couldn't figure it out.

Martin

[Linden Disney]

I don't know if you figured this out, but I think you can do everything you want using the GAP functionality, here is your n=2, N=4 example:

gap> N := 4;
4
gap> n := 2;
2
gap> SN := SymmetricGroup(N);

Sym( [ 1 .. 4 ] )

gap> Sn := SymmetricGroup(n);
Sym( [ 1 .. 2 ] )
gap> G := GroupHomomorphismByImages(Sn, SN, [(1,2)], [(1,2)(3,4)]);
[ (1,2) ] -> [ (1,2)(3,4) ]
gap> F := OnPoints;
function( pnt, elm ) ... end
gap> H := function(pnt, g)
> return F(pnt, Image(G, g));
> end;
function( pnt, g ) ... end
gap> F((1,2,3,4), (1,2));
(1,3,4,2)
gap> H((1,2,3,4), (1,2));
(1,4,3,2)

Here I have used GroupHomomorphismByImages to define the action of Sn on N elements, but you could equally write this as a GAP action and then construct the homomorphism using the action. For the GAP links to explain these functions see 

https://docs.gap-system.org/doc/ref/chap41.html

https://docs.gap-system.org/doc/ref/chap40.html

Hope that helps,

Linden

[dmo...@deductivepress.ca]

Let's continue this discussion at PR #40186 (or someone can make a new issue).