[seqfan] Re: Prime signature of 1, and second signature

[David Wilson]

Ok...

Clearly the prime signature of n is a collection of the exponents in the 
prime factorization of n.

Wikipedia says that is the "multiset" of exponents in the prime 
factorization of n, MathWorld that it is the "sorted list" of exponents 
in the prime factorization of n. It must be clear that in either case, 
we are talking about a finite collection of positive integers. The 
former definition is precise, since a multiset is a precisely defined 
mathematical object. The latter definition is vague, since "list" does 
not have a context-independent mathematical definition, however, if we 
agree that "sorted list" actually means "nondecreasing sequence," the 
definition becomes precise.

It turns out that there is a natural bijection between finite multisets 
and finite nondecreasing sequence over the same (ordered) domain (in 
this case the positive integers). You just write the multiset in 
canonical form with nondecreasing elements, and map it to the 
nondecreasing sequence of identical elements:

     {} <=> ()
     {3,7,7} <=> (3,7,7)
     {1,1,2,2,3} <=> (1,1,2,2,3)

So while it is indeed true that a sorted list (nondecreasing sequence) 
and a multiset are not the same thing, there is a one-to-one 
correspondence between them, so you can treat them as the same thing. 
They both model the same type of collection, an unordered collection 
with repeated elements.

The prime signature of 1 cannot be {1} because that would imply 1 = p^1 
for some prime, which is not true.

Also, the prime signature of 1 cannot be {0} because a prime signature 
is a collection of positive integers, and 0 is not a positive integer. 
But suppose you ignore that constraint and allow the prime signature of 
1 to be {0} because 1 = p^0. Then I would counter that the prime 
signature of 1 is {0,0} because 1 = p^0*q^0, and also {0,0,0} and indeed 
any {0^n}. Likewise the prime signature of 48 could be {0^n,1,4} for any 
n. This destroys the uniqueness, and hence the value, of the prime 
signature.

Since 1 does have a prime factorization, the empty prime factorization, 
this would imply that it should have a prime signature, which would the 
empty prime signature, to wit, the empty multiset {} or the empty sorted 
list () of positive integers.

It really doesn't matter whether you model a prime signature as a 
multiset or (equivalently) as a nondecreasing sequence, or in what order 
you write the exponents, or whether you enclose it in braces or parens, 
as long as you understand that it is an unordered list of positive 
integers with repeated elements.

As long as you understand why

     (1,2,3,2,1) = {1,1,2,2,3}

you'll be OK.

On 6/11/2012 11:13 AM, Matthew Vandermast wrote:
> Thanks. In a paper by Jean-Louis Nicolas in the 1987 book Ramanujan Revisited ("On Highly Composite Numbers"), Nicolas refers to the least integers of each prime signature as "w.n.i.e." (with nonincreasing exponent) integers.  I wonder if the phrase "prime signature" had been coined by then.  It's a nice phrase, anyway.
>
> The earliest written definition of prime signature of which I am personally aware was written for the MathWorld site in (I think) 2006. I'd really appreciate seeing references to earlier ones, if anyone knows of any.
>
> For what it's worth, MathWorld defines the prime signature of  n>1 as a "sorted list of nonzero exponents."  I.e., *not* the multiset itself, but a list that *signifies* that multiset.  MathWorld also chose 1 to signify the empty multiset, whereas I think 0 would have been a better choice, and a more OEIS-traditional choice, too.
>
> I don't want to base too much on MathWorld's prime signature page (as great as that site usually is). But what I'm respectfully wondering at the moment is:  Is it possible that, from early on, there were variant understandings of what prime signature meant?  Perhaps some people understood the prime signature to be the multiset itself, and others understood it to be something (a list of exponents, when n>  1) that *signified* that multiset?
>
> Take this familiar OEIS comment (found under A008966 and dozens of other sequences; originally written by Neil unless I'm mistaken):
>
>
> a(n) depends only on prime signature of n (cf. A025487). So a(24) = a(375) since 24=2^3*3 and 375=3*5^3 both have prime signature (3,1).
>
> I believe that parentheses are usually used for a list, and brackets are usually used for a set or multiset. Again, having the prime signature not be the multiset itself is fine with me. I also think the "depends only on" phrase is probably justifiable even if the prime signature is a list, rather than a multiset that that list signifies. To me, "a(n) depends only on prime signature of n" seems an essentially OK way of expressing the idea: "If you know the prime signature of n, you know a(n) with certainty."
>
> I'm not usually as fond of splitting semantic hairs as I may seem in some earlier paragraphs.  I just think it would be nice for the OEIS to have a way to "signify" the prime signature of as many n as possible - and that this is even more key for the second signature. "Kludge" is a fun word for the conventional 0s denoting the absence of other suitable a(n)s, but I still like it that the OEIS usually tries to have a(n) for as many n as possible.  And again, for anyone who may have missed my response to Marc LeBrun's comments: In any case, I'll be submitting the second signature of non-squarefree numbers so people can find that if they look for it. But I suspect that the complete version would be helpful, too.
>
> Regards,
> Matt  Vandermast
>