> < ^ From:

> < ^ Subject:

Leonard continues in his e-mail message of 1994/07/27I 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) )$.

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.

Steve

> < [top]