Multiset Signatures and Partitions

[franktaw at netscape.net]

Interesting things also happen applying the signature to the conjugate 
of a partition (which I will call the conjugate signature).  Just as 
the signature depends only on the multiplicities of the partition, not 
their sizes, the conjugate signature depends only on the sizes, not the 
multiplicities.  If fact, taking the set of distinct part sizes in the 
original partition, together with zero, and taking the collection of 
differences between successive values (in sorted order) gives the 
conjugate partition.

So what happens when we apply the conjugate signature repeatedly?  
Well, obviously, if the partition has more than one size, the largest 
size will be reduced, and if only one size is present, the next step 
will be a singleton partition.  So iteration will eventually produce a 
singleton partition.  A moments thought will show that the operation 
preserves the GCD of the part sizes.

So repeated calculation of the conjugate signature eventually produces 
the GCD of the part sizes (as a singleton partition).

-----Original Message-----
From: franktaw at netscape.net

    Let us define the signature of a (finite) multiset to be the 
partition composed of the multiplicities of the members of the 
multiset. For example, for the multiset {1,1,1,1,2,2,3,4}, the 
signature is {1,1,2,4}. The prime signature of a number is then the 
signature of its prime factor multiset.

  Since a partition is also a multiset, the signature operation can be 
applied repeatedly. ...
___________________________________________________
Try the New Netscape Mail Today!
Virtually Spam-Free | More Storage | Import Your Contact List
http://mail.netscape.com