> < ^ Date: Thu, 28 Jul 1994 15:50:00 +0200
> < ^ From: Steve Linton <sal@dcs.st-and.ac.uk >
> < ^ Subject: Re: StabChain
Leonard continues in his e-mail message of 1994/07/27

I suggest the following default strategy for calculating


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

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

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.

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

I suggest using Leonard's method for all actions except 'OnPoints'.
For OnPoints the long-term advantage of computing and remembering a
Schreier tree for an entire orbit makes it worthwhile doing so.


> < [top]