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
HTH
Dima
>
> 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
>
> On Thursday, February 5, 2026 at 6:15:17 AM UTC-6 wrote:
>
> 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
>
>
>
>
>
>
>
>
>
> On Thursday, February 5, 2026 at 12:57:16 PM UTC+1 Michel VAN DEN BERGH
wrote:
>
> 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
>
>
> On Thursday, 5 February 2026 at 11:16:52 UTC+1 Martin R wrote:
>
> That's a huge example.
>
> sage: len(libgap.RightTransversal(W, G))
> 138240
>
> I think it is a gap bug, I am checking right now.
>
>
> On Thursday, 5 February 2026 at 07:46:47 UTC+1 wrote:
>
> > 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.
>
>
>
>
> --
> 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.
> To view this discussion visit
https://groups.google.com/d/msgid/sage-support/2f5c40db-62ad-4e65-bfea-30f5e673ed39n%40googlegroups.com.
--
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 [email protected].
To view this discussion visit
https://groups.google.com/d/msgid/sage-support/6fd0d76b-b0b4-4b48-87eb-da8bbbc608d3n%40googlegroups.com.
