Leonard Soicher writes in his e-mail message of 1994/07/26

Why does Gap feel it is necessary to compute a stabilizer chain for G in
order to compute RepresentativeOperation(G,1,pt) ?

I just looked at the code. Superficially it appears to be the result of
a mixture of stupidity and laziness. In truth however, I used the most
stupid and wastefull method I could think of, to see how long it would go
undetected ;-).

Leonard continues in his e-mail message of 1994/07/27

I suggest the following default strategy for calculating

RepresentativeOperation(G,x,y,action);

The idea is to build up two partial Schreier trees Tx, Ty (w.r.t.
G.generators), rooted at x and y, respectively. One alternately
adds nodes to Tx and Ty until they have a node z, say, in common (if
one of the trees is completed and there is no such node then return
false). Given such a z, one uses Tx,Ty in the usual way to
get elements gx,gy such that z=action(x,gx)=action(y,gy),
and so the required element taking x to y is gx/gy.

If x and y are in the same G-orbit, then this approach should be
much faster than computing an orbit for x until y is found, and
much much faster than trying to compute a StabChain if the action is
OnPoints.

It is not clear to me that this is indeed a win. Let us assume that the
group operates transitively on $n$ points and that it has only a small
number $k$ of generators.

Then computing the entire orbit an the corresponding Schreier tree takes
time $O( n k )$. Your method on the other hand would usually take time
$O( n^(1/2) k )$ (the worst case is of course also $O( n k )$.

However, I think that in most cases the total time will anyhow be
dominated by the time it takes to multiply together the representative.
Namely, under favourable conditions the pathlength from $x$ to $y$ in
this tree will be $O( log(n) )$, so the cost of computing the
representative is $O( n log(n) )$.

So your method would not be faster unless $k >> log(n)$. This is only
theory of course, and I haven't yet investigated this in practice. It
might well be that the constant for the orbit computation is so much
higher that the constant for the representative computation (most of
which is multiplying permutations, and this is done in the kernel), that
your method is still practically better.

However, there is even a practical argument against your method. Namely
assume that a user makes multiple calls to 'RepresentativeOperation',
maybe with fixed 'x' but varying 'y'. With the straightforward orbit
computation one could compute the orbit once and then remember it, so
that subsequent calls to 'RepresentativeOperation' do not have to
recompute it. With your method it is not clear how to do this, so that
the total time for all tree computations never exceeds $O( n k )$.

Martin.

-- .- .-. - .. -.  .-.. --- ...- . ...  .- -. -. .. -.- .-
Martin Sch"onert,   Martin.Schoenert@Math.RWTH-Aachen.DE,   +49 241 804551
Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany