[r-t] Coset labeling

[Richard Smith]

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