# [r-t] Coset labeling

Richard Smith richard at ex-parrot.com
Mon Nov 21 17:58:17 UTC 2011

```Graham John wrote:

> I have used your approach (for example in multipart proving), but converted
> the lexicographically least label into a unique hash between 0 and !labels.

Yes, I often do this too.  I'm not sure it's feasible in
this case, though.

> Doesn't your algorithm just need to convert x into a unique hash with a
> maximum value of |G| by combining the unique hashes relating to each coset?

I'm not sure what you're suggesting.  I have N!/|G| cosets.
If I assign labels with a hash function, presumably they're
going to have to be long numbers to minimise the risk of a
hash collision.  Imagine the case of 8! cosets.  If hash is
a 32-bit number, the probability of a hash collision is
approximately:

1 - exp( - 8!.(8!-1) / (2 * 2^32) ) = 17%

Even if we use a hash value that's long enough to avoid
collisions, how do I generate the hash from a single
element?  Or do I have to traverse the coset which is
O(|G|), or even traverse it in specific order which is
probably O(|G|.ln|G|)?

So I think we have to use a label-assigning function that
guarantees uniqueness of the label.  We can do this in O(1)
with specific knowledge of the group.  E.g. if G=S_{n-1}, we
can locate the treble and use the treble position as the
index.  But that's not good in the case of an arbitrary G.

Or I need a table of size N!/|G| mapping an arbitrary member
of the group to a label, in which case I need to do an
O(|G|) traverse of the coset to find its label.  Or I need a
table of size N! mapping every row to coset.

The alternative is to avoid ever having to map from row to
label.  That's a strategy that I sometimes use, and it
involves have a big multiplication table so that I know that
if, say, we apply a 1238 place notation to a row in coset
41, we get a row in coset 72.  Again, that involves a table
of size N!/|G|.C where C is the number of place notations we
care about (which is frequently F(N), the Nth Fibonacci
number).

All of these strategies seem to involve an operation that's
slow for large groups (those with an O(|G|) step), or that
use a large amount of memory for small groups on large
numbers of bells (those with tables of size N!/|G|, or
worse).  I could have separate code paths for these two
cases, and at the moment that would probably work.  On up to
twelve bells, one or other should always be OK.  But I'd
prefer a single approach that works everywhere.

But maybe I'm missing your point.

RAS

```