Iterating over coset representatives.

[Michel VAN DEN BERGH]

Hi,

I have a permutation group (a Weyl group in fact) and a subgroup given by explicit generators. I would like to iterate over representatives for the cosets of this group. Is there an efficient way to do this in Sage?

I asked ChatGPT and it gave me all kinds of plausible looking commands, none of which actually existed...

Thanks!

[Martin R]

I don't know about efficient, but in the species code I use libgap.RightTransveral(group, subgroup):

    def structures(self, *labels):

        labels = _label_sets(self.parent()._arity, labels)
        n = tuple([len(U) for U in labels])
        S = _SymmetricGroup(sum(n)).young_subgroup(n)
        l = [e for l in labels for e in l]
        if self._mc == n:
            for rep in libgap.RightTransversal(S, self._dis):
                yield tuple(S(rep)._act_on_list_on_position(l))

Does this help?

Martin

[Michel VAN DEN BERGH]

On Tuesday, February 3, 2026 at 7:00:36 PM UTC+1 wrote:

I don't know about efficient, but in the species code I use libgap.RightTransveral(group, subgroup):

    def structures(self, *labels):

        labels = _label_sets(self.parent()._arity, labels)
        n = tuple([len(U) for U in labels])
        S = _SymmetricGroup(sum(n)).young_subgroup(n)
        l = [e for l in labels for e in l]
        if self._mc == n:
            for rep in libgap.RightTransversal(S, self._dis):
                yield tuple(S(rep)._act_on_list_on_position(l))

Does this help?

Martin

Some quick experimenting seems to indicate that this is exactly what I need!

Thanks a lot!

Michel

[Michel VAN DEN BERGH]

However when I turn the returned GAP representatives back into elements of the Sage group (called "weyl_group") sometimes (very rarely) I get

Traceback (most recent call last):                                                                                                                                                      
  File "/home/vdbergh/TEX/ANYA/anya/scripts/p1xp1/compute_NCCR_orbit.py", line 353, in <module>
    test4("X8")
  File "/home/vdbergh/TEX/ANYA/anya/scripts/p1xp1/compute_NCCR_orbit.py", line 341, in test4
    compute_orbit(context, col)
  File "/home/vdbergh/TEX/ANYA/anya/scripts/p1xp1/compute_NCCR_orbit.py", line 41, in compute_orbit
    w = weyl_group(w) ** -1  # left coset
        ^^^^^^^^^^^^^
  File "sage/structure/parent.pyx", line 901, in sage.structure.parent.Parent.__call__
  File "sage/structure/coerce_maps.pyx", line 164, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_
  File "sage/structure/coerce_maps.pyx", line 159, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_
  File "/home/vdbergh/sage/src/sage/groups/perm_gps/permgroup.py", line 912, in _element_constructor_
    return self.element_class(x, self, check=check)
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "sage/groups/perm_gps/permgroup_element.pyx", line 518, in sage.groups.perm_gps.permgroup_element.PermutationGroupElement.__init__
ValueError: invalid data to initialize a permutation

Anyone knows what could be the cause of this?

Best,

Michel

[Michel VAN DEN BERGH]

Some more details:

- The problem is deterministic. So it is not a problem with my computer.

- I am trying to print the offending element. Unfortunately whatever I do I always get "ValueError: invalid data to initialize a permutation". Converting the element to a string (via str, or repr) does not give an error but it does not give the full element (the string contains .... ).

Not sure what to do.

Best,

Michel

[Martin R]

could you send me code that produces the failure, so I can debug it?

Martin

[Michel VAN DEN BERGH]

On Wednesday, February 4, 2026 at 5:40:55 PM UTC+1 wrote:

could you send me code that produces the failure, so I can debug it?

That would be great!

The code is rather complex but I'll try to make a minimal example.

Best,

Michel

Martin

[Michel VAN DEN BERGH]

Below is the example extracted from my code. After a few seconds it prints

Traceback (most recent call last):

  File "/home/vdbergh/TEX/ANYA/anya/scripts/p1xp1/test_case.py", line 17, in <module>
    w = W(w)

        ^^^^
  File "sage/structure/parent.pyx", line 901, in sage.structure.parent.Parent.__call__
  File "sage/structure/coerce_maps.pyx", line 164, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_
  File "sage/structure/coerce_maps.pyx", line 159, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_
  File "/home/vdbergh/sage/src/sage/groups/perm_gps/permgroup.py", line 912, in _element_constructor_
    return self.element_class(x, self, check=check)
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "sage/groups/perm_gps/permgroup_element.pyx", line 518, in sage.groups.perm_gps.permgroup_element.PermutationGroupElement.__init__
ValueError: invalid data to initialize a permutation

from sage.all import libgap, WeylGroup

elts = ["(1,9)(3,123)(4,11)(10,17)(12,19)(18,25)(20,27)(26,33)(28,35)(34,41)(36,43)(37,44)(42,50)(45,51)(52,57)(53,58)(59,64)(60,65)(66,71)(67,72)(73,78)(79,84)(89,93)(94,98)(99,102)(103,105)(106,108)(111,114)(113,115)(121,129)(124,131)(130,137)(132,139)(138,145)(140,147)(146,153)(148,155)(154,161)(156,163)(157,164)(162,170)(165,171)(172,177)(173,178)(179,184)(180,185)(186,191)(187,192)(193,198)(199,204)(209,213)(214,218)(219,222)(223,225)(226,228)(231,234)(233,235)",
 "(1,28)(2,41)(3,159)(4,16)(7,147)(8,43)(9,129)(10,58)(11,141)(12,24)(14,139)(18,64)(19,134)(20,31)(21,131)(23,49)(26,71)(27,127)(30,55)(32,44)(34,46)(35,155)(36,47)(37,70)(38,61)(39,123)(40,51)(42,84)(45,76)(48,57)(52,82)(54,74)(56,65)(60,88)(62,72)(67,92)(68,78)(69,93)(73,96)(81,102)(86,105)(89,97)(90,108)(94,114)(99,104)(101,110)(103,107)(106,109)(112,115)(113,119)(121,148)(122,161)(124,136)(128,163)(130,178)(132,144)(138,184)(140,151)(143,169)(146,191)(150,175)(152,164)(154,166)(156,167)(157,190)(158,181)(160,171)(162,204)(165,196)(168,177)(172,202)(174,194)(176,185)(180,208)(182,192)(187,212)(188,198)(189,213)(193,216)(201,222)(206,225)(209,217)(210,228)(214,234)(219,224)(221,230)(223,227)(226,229)(232,235)(233,239)",
 "(1,131)(2,23)(4,129)(5,24)(9,124)(11,121)(13,31)(16,136)(18,37)(21,39)(25,44)(26,45)(29,47)(33,51)(34,53)(41,58)(42,60)(48,63)(50,65)(55,70)(61,76)(62,77)(68,83)(74,88)(85,97)(90,101)(95,104)(100,107)(106,111)(108,114)(112,116)(122,143)(125,144)(133,151)(138,157)(141,159)(145,164)(146,165)(149,167)(153,171)(154,173)(161,178)(162,180)(168,183)(170,185)(175,190)(181,196)(182,197)(188,203)(194,208)(205,217)(210,221)(215,224)(220,227)(226,231)(228,234)(232,236)",
 "(1,4)(2,17)(3,136)(5,19)(9,129)(10,23)(11,131)(12,24)(13,27)(16,123)(18,44)(20,31)(21,35)(26,51)(28,39)(29,43)(30,32)(34,58)(36,47)(38,40)(42,65)(46,49)(48,57)(52,63)(54,56)(55,64)(59,70)(61,71)(62,72)(66,76)(67,77)(68,78)(73,83)(74,84)(79,88)(85,93)(89,97)(90,98)(94,101)(95,102)(99,104)(100,105)(103,107)(106,114)(109,110)(112,115)(113,116)(121,124)(122,137)(125,139)(130,143)(132,144)(133,147)(138,164)(140,151)(141,155)(146,171)(148,159)(149,163)(150,152)(154,178)(156,167)(158,160)(162,185)(166,169)(168,177)(172,183)(174,176)(175,184)(179,190)(181,191)(182,192)(186,196)(187,197)(188,198)(193,203)(194,204)(199,208)(205,213)(209,217)(210,218)(214,221)(215,222)(219,224)(220,225)(223,227)(226,234)(229,230)(232,235)(233,236)",
 "(2,18)(3,19)(4,125)(5,124)(6,20)(9,24)(12,132)(14,28)(17,32)(22,36)(23,37)(33,48)(38,52)(41,55)(46,59)(50,62)(51,63)(54,67)(58,70)(65,77)(71,82)(78,87)(80,89)(84,92)(86,94)(91,99)(100,106)(105,110)(107,111)(115,117)(122,138)(123,139)(126,140)(129,144)(134,148)(137,152)(142,156)(143,157)(153,168)(158,172)(161,175)(166,179)(170,182)(171,183)(174,187)(178,190)(185,197)(191,202)(198,207)(200,209)(204,212)(206,214)(211,219)(220,226)(225,230)(227,231)(235,237)",
 "(5,13)(6,126)(7,14)(12,20)(15,22)(18,26)(19,27)(24,31)(25,33)(30,38)(32,40)(37,45)(44,51)(55,61)(59,66)(62,68)(64,71)(67,73)(70,76)(72,78)(75,80)(77,83)(81,86)(92,96)(95,100)(99,103)(102,105)(104,107)(117,118)(125,133)(127,134)(132,140)(135,142)(138,146)(139,147)(144,151)(145,153)(150,158)(152,160)(157,165)(164,171)(175,181)(179,186)(182,188)(184,191)(187,193)(190,196)(192,198)(195,200)(197,203)(201,206)(212,216)(215,220)(219,223)(222,225)(224,227)(237,238)",
 "(2,10)(3,11)(4,124)(5,12)(9,16)(13,20)(21,28)(25,32)(29,36)(30,37)(33,40)(38,45)(41,49)(46,53)(50,56)(54,60)(57,63)(64,70)(71,76)(72,77)(78,83)(84,88)(85,89)(90,94)(95,99)(100,103)(108,110)(109,111)(115,116)(122,130)(123,131)(125,132)(129,136)(133,140)(141,148)(145,152)(149,156)(150,157)(153,160)(158,165)(161,169)(166,173)(170,176)(174,180)(177,183)(184,190)(191,196)(192,197)(198,203)(204,208)(205,209)(210,214)(215,219)(220,223)(228,230)(229,231)(235,236)"]


W=WeylGroup("E8", implementation='permutation')

G = W.subgroup(elts)

for w in libgap.RightTransversal(W, G):
    w = W(w)

[Michel VAN DEN BERGH]

I managed to print the offending element with print(w.sage()). I get

[147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147, 147]

which looks wrong to me.

Michel

[Dima Pasechnik]

This is very strange code - you are attempting to change the variable of a loop inside a loop.

What do you mean to do here?

Dima
>
>
>
>
>
>
>
>

[Michel VAN DEN BERGH]

> This is very strange code - you are attempting to change the variable of a loop inside a loop.
>
> What do you mean to do here?
>

> Dima

Well that's not the point. Writing v=W(w) gives the same bug...

Best,

Michel

PS. This was just some quick test code, but this being said, I think assigning to a loop variable is fine. This does not influence the state of the iterator. A quick test confirms this.

[Michel VAN DEN BERGH]

I noticed that when I replace libgap.RightTransversal by gap.RightTransversal, the bug does not seem to occur.

So perhaps it is a bug in libgap?

Best,

Michel

[Martin R]

That's a huge example.

sage: len(libgap.RightTransversal(W, G))
138240

I think it is a gap bug, I am checking right now.

[Martin R]

I narrowed it down slightly.

https://github.com/sagemath/sage/issues/41595

[Martin R]

As a workaround, I think that explicitly converting the gap list returned by libgap.RightTransversal(W, G) into a python list helps.  I.e.,

list(libgap.RightTransversal(W, G))

Martin

On Thursday, 5 February 2026 at 11:16:52 UTC+1 Martin R wrote:

[Michel VAN DEN BERGH]

On Thursday, February 5, 2026 at 12:15:21 PM UTC+1  wrote:

As a workaround, I think that explicitly converting the gap list returned by libgap.RightTransversal(W, G) into a python list helps.  I.e.,

list(libgap.RightTransversal(W, G))

Martin

I use this initially also for G=trivial (basically I am trying to incrementally build the stabilizer of something by iterating over the cosets of a stabilizing group already found) so constructing a list  of which only a small part will be consumed is a bit inconvenient. However your issue suggests to use

for i in range(0, len(R)):

  w = W(R[i])

This seems to work perfectly!

I must say that I am mildly surprised that this works. I was guessing that the coset representatives would be found on the fly in some way.

In any case: thanks for investigating and filing the issue!

Best,

Michel

[Michel VAN DEN BERGH]

Hmm I have to retract this last post.Using 

for i in range(0, len(R)):

  w = W(R[i])

still triggers the bug.

Best,

Michel

[Dima Pasechnik]

In case you just want a permutation action of W on the cosets of G, you can avoid dealing with cosets all together.

sage: f=libgap(W).FactorCosetAction(libgap(G)).Image()
sage: f.OrbitLength(1)
138240

In fact, libgap(W).FactorCosetAction(libgap(G)) is a proper group homomorphism, so you can go back and forth between W and f.

If you explain what you wanted  to do with your coset representatives, I can say more...

Dima

[Michel VAN DEN BERGH]

Ok here is the setting. It is rather specific.

I have a group G (W(E8) in this example) and a left G equivariant equivalence relation R on it. R is not known directly,  but for any g in G and any subset S of G I can efficiently check (complexity O(1)) if g is equivalent to any element in S. I want to find representatives for G/R.

Of course this is equivalent to determining the subgroup H={h in G | h ~ 1} and a set of representatives for G/H.

So what I do is I start with H={1}, S={1} and iterate over representatives of  g of G/H. If g is not equivalent to any element in S then I add g to S.

If g is equivalent to an element s in S then h=g^-1 s ~ 1 and I replace H with the subgroup generated by H and h and repeat.

The algorithm stops when |H| |S|=|G|.  It works very efficiently, as long as G/R is not too big (even if G itself is big).

Best,

Michel

   

On Thursday, February 5, 2026 at 4:33:15 PM UTC+1  wrote:

In case you just want a permutation action of W on the cosets of G, you can avoid dealing with cosets all together.

sage: f=libgap(W).FactorCosetAction(libgap(G)).Image()
sage: f.OrbitLength(1)
138240

In fact, libgap(W).FactorCosetAction(libgap(G)) is a proper group homomorphism, so you can go back and forth between W and f.

If you explain what you wanted  to do with your coset representatives, I can say more...

Dima

[Dima Pasechnik]

On Thu, Feb 5, 2026 at 9:59 AM 'Michel VAN DEN BERGH' via sage-support
<sage-s...@googlegroups.com> wrote:
>
> Ok here is the setting. It is rather specific.
>
> I have a group G (W(E8) in this example) and a left G equivariant equivalence relation R on it. R is not known directly, but for any g in G and any subset S of G I can efficiently check (complexity O(1)) if g is equivalent to any element in S. I want to find representatives for G/R.
>
> Of course this is equivalent to determining the subgroup H={h in G | h ~ 1} and a set of representatives for G/H.
>
> So what I do is I start with H={1}, S={1} and iterate over representatives of g of G/H. If g is not equivalent to any element in S then I add g to S.
> If g is equivalent to an element s in S then h=g^-1 s ~ 1 and I replace H with the subgroup generated by H and h and repeat.
>
> The algorithm stops when |H| |S|=|G|. It works very efficiently, as long as G/R is not too big (even if G itself is big).

Would it be more efficient to start from a subgroup G_1 of G and
compute the analog of R in G_1, and the corresponding H_1, first?
Then, for G and R, you can start with H=H_1, instead of H={1}, right?

Anyway, as FactorCosetAction is pretty fast, one can re-do it once a
new h to add to H is found.
The question is how to relate points of the domain O of the
permutation group f (where
f=libgap(W).FactorCosetAction(libgap(G)).Image(),
or, in the notation of this message,
f=libgap(G).FactorCosetAction(libgap(H)).Image())

Each point of O is obtained by applying a sequence of generators of G
to 1 (i.e. to the coset {H}).
Classically, such a sequence can be obtained from the Schreier vector
(https://en.wikipedia.org/wiki/Schreier_vector). GAP itself does not
give you a ready access to a Schreier vector for an orbit,
but the GAP package orb has such a facility (
libgap.LoadPackage("orb") will load it into the Sage session,
and you need gap_packages spkg installed, or, if your Sage install
uses system-wide GAP, you need it installed there).
So you'll need to call Orb() from orb package with option ":
schreier:=true" - this is something that has to be done via
libgap.function_factory(). And then use
TraceSchreierTreeForward (see
https://docs.gap-system.org/pkg/orb/doc/chap3_mj.html#X7F927E787BA898BF)
(or TraceSchreierTreeBack) to get the words.
Or you can roll your own orbit algorithm where you'd record Schreier vector.

Does this make sense?

HTH
Dima

> --
> You received this message because you are subscribed to the Google Groups "sage-support" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-support...@googlegroups.com.
> To view this discussion visit https://groups.google.com/d/msgid/sage-support/2f5c40db-62ad-4e65-bfea-30f5e673ed39n%40googlegroups.com.

[Michel VAN DEN BERGH]

On Thursday, February 5, 2026 at 6:39:18 PM UTC+1 dwrote:

On Thu, Feb 5, 2026 at 9:59 AM 'Michel VAN DEN BERGH' via sage-support

 wrote:
>
> Ok here is the setting. It is rather specific.
>
> I have a group G (W(E8) in this example) and a left G equivariant equivalence relation R on it. R is not known directly, but for any g in G and any subset S of G I can efficiently check (complexity O(1)) if g is equivalent to any element in S. I want to find representatives for G/R.
>
> Of course this is equivalent to determining the subgroup H={h in G | h ~ 1} and a set of representatives for G/H.
>
> So what I do is I start with H={1}, S={1} and iterate over representatives of g of G/H. If g is not equivalent to any element in S then I add g to S.
> If g is equivalent to an element s in S then h=g^-1 s ~ 1 and I replace H with the subgroup generated by H and h and repeat.
>
> The algorithm stops when |H| |S|=|G|. It works very efficiently, as long as G/R is not too big (even if G itself is big).

Would it be more efficient to start from a subgroup G_1 of G and
compute the analog of R in G_1, and the corresponding H_1, first?
Then, for G and R, you can start with H=H_1, instead of H={1}, right?

Perhaps. But in the case I looked at then H becomes bigger quickly. So starting with H={1} does not seem to be a problem. 

Anyway, as FactorCosetAction is pretty fast, one can re-do it once a
new h to add to H is found.
The question is how to relate points of the domain O of the
permutation group f (where
f=libgap(W).FactorCosetAction(libgap(G)).Image(),
or, in the notation of this message,
f=libgap(G).FactorCosetAction(libgap(H)).Image())

Each point of O is obtained by applying a sequence of generators of G
to 1 (i.e. to the coset {H}).
Classically, such a sequence can be obtained from the Schreier vector
(https://en.wikipedia.org/wiki/Schreier_vector). GAP itself does not
give you a ready access to a Schreier vector for an orbit,
but the GAP package orb has such a facility (
libgap.LoadPackage("orb") will load it into the Sage session,
and you need gap_packages spkg installed, or, if your Sage install
uses system-wide GAP, you need it installed there).
So you'll need to call Orb() from orb package with option ":
schreier:=true" - this is something that has to be done via
libgap.function_factory(). And then use
TraceSchreierTreeForward (see
https://docs.gap-system.org/pkg/orb/doc/chap3_mj.html#X7F927E787BA898BF)
(or TraceSchreierTreeBack) to get the words.
Or you can roll your own orbit algorithm where you'd record Schreier vector.

Does this make sense?

I think so. Thanks in any case for the very detailed explanation. I need to study it more carefully though. In any case RightTransversal(W, H) works fine except for the bug. But I have a reasonable workaround.  I remember the cosets where the bug is triggered and once H no longer grows, I convert  RightTransversal(W, H) to a list, to pick up the few cosets that were missed because of the bug.

It is a mystery to me why list(RightTransversal(W, H)) does not suffer from the bug, but it is what it is...

Best,

Michel

 

> To unsubscribe from this group and stop receiving emails from it, send an email to.

[Martin R]

I think that this is a very serious bug, if you are unlucky, you might get wrong results without noticing.

The failure in https://github.com/sagemath/sage/issues/33072 looks somewhat similar.

Unfortunately, I have no idea how to debug it.

[Martin R]

might it make sense to ask the gap people for help?

Martin