I wrote in my e-mail message of 1994/07/28

...about computing a representative that takes x to y...

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) )$.

Steve Linton answered in his e-mail message of 1994/07/28

This is only so if the action is on points. Suppose that we consider
a permutation group of small degree acting on a large orbit of sets
or tuples, or a matrix group of small degree acting on vectors or
subspaces. Then the time for a multiplication is much less than n.

For the operation on tuples you use a stabilizer chain. That is you
first find a representative r_1 that moves x[1] to y[1]. In the
stabilizer of x[1] you then look for a representative r_2 that
moves x[2] to y[2]^(r_1^-1). Then the product r_2 r_1 takes x[1] to
y[1] and x[2] to y[2]. Iterate and serve.

Ignoring the time to compute a stabilizer chain this has cost $O( n l )$,
where l is the number of points in the tuples. The running time for
Leonard's method depends on the length of the orbit that G makes on the
tuples, but in the worst case the length could be $O( n ^ l )$ and the
average running time would be $O( n ^ (l/2) )$.

For the operation on sets you use backtrack. It is not so easy to
estimate the running time for this backtrack. But Leonard's method
has again a pretty bad worst case estimate.

Of course the general comment is true. My analysis was only valid under
the assumption that the operation is one of a permutation group on
points. If the length of the orbit is not bound by n or the time
to compute one image is not constant, Leonard's method will probably
be superior. However, as the above shows, for some other operations
one can do even better, if one is willing to compute a stabilizer chain.

Martin.

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