[r-t] Coset labeling

[Simon Gay]

Maybe this suggestion is too obvious, but if I remember my undergraduate group theory correctly:

The coset containing r is Gr. So r and s are in the same coset if and only if their cosets are the same: Gr = Gs.

Gr = Gs if and only if s * inverse(r) is in G.

If you don't mind having a table of size |G|, then you can just use some kind of hash table to represent the membership function for G, and look up s*inverse(r) in it.

If you know what G is in some other way (e.g. as in your example, G is S_(n-1)) then you can easily test whethe s*inverse(r) has the correct fixed bell. Or for A_(n-1) you can test the fixed bell and compute the parity of the row.

Simon



On 20/11/2011 00:30, Richard Smith wrote:


A quick question for the more mathematically-minded people
on the list.  If G is a subgroup of the extent on n bells
(S_n), and a and b are two rows, what is a good algorithm
for determining whether a and b are in the same right coset
of G?

My current strategy is to use the lexicographically least
one row from each coset Gr as its label and then compare
labels.  In pseudo-code, we have a function:

   function label(r) {
     var x = back_rounds  // the maximum element of S_n
     foreach g in G {
       x = min( x, g*r )
     }
     return x
   }

and then test whether label(a) = label(b).

For the sake of argument, let's assume a row multiplication,
a row comparison, and a row inversion all take 1 unit of
time.  (That's a fairly good assumption.)  So the comparison
of two labels costs 2|G|.

In most practical cases, it's possible to hand-craft a label
function that's *much* quicker.  If G is S_{n-1}, locate the
fixed bell and then fill the other bells in in order.  If
it's A_{n-1}, do similarly and if necessary swap a pair to
get the correct parity.  If it's S_m x S_n, find the
position of the bells in the smaller cycle, reorder them if
necessary and fix them, then drop the other bells in in
order.

In each of these, we've replaced an O(|G|) algorithm with
one that's O(1), and in doing so achieves a vast performance
increase for things like G = S_3 x S_7 where |G| = 30240.
But is it possible to write a general coset labelling
algorithm that's O(1)?

I'm not willing to accept a lookup table with n! entries,
mapping each element of S_n to a coset label.  But I may
(just) be willing to accept a table with |G| entries.

Any thoughts?

RAS

_______________________________________________
ringing-theory mailing list
ringing-theory at bellringers.net<mailto:ringing-theory at bellringers.net>
http://bellringers.net/mailman/listinfo/ringing-theory_bellringers.net




--------------------------------------------------------------------
Dr Simon Gay                    School of Computing Science
Senior Lecturer in              Sir Alwyn Williams Building
Computing Science               University of Glasgow
                                Glasgow G12 8QQ, UK
Phone: +44 141 330 6035
Fax:   +44 141 330 4913
Email: simon at dcs.gla.ac.uk<mailto:simon at dcs.gla.ac.uk>
Web:   www.dcs.gla.ac.uk/~simon<http://www.dcs.gla.ac.uk/~simon>
Skype: SimonJGay
--------------------------------------------------------------------



________________________________
The University of Glasgow, charity number SC004401