Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I remember asking about this in some Norwegian Usenet group many many years back, and as I recall (although I may be just imagining it) a mathematician at the University of Oslo gave me a good summary. But I have forgotten it all!

Background: during my student days at Heriot Watt U. (Edinburgh) I wrote dissertation about combination of uncertain evidence by means of a model called Dempster-Shafer. With this method one had to update products of the elements of multisets (by this I mean that an element could be present any number of times), where it was necessary to support both that an element was removed, and that it was added. Addition of x to a set meant just multiplying the product by x, but removal was trickier: when x was zero one could not just divide the product by x!

So, for each set I maintained a pair (P, Z) where P was the product of the elements if possible or else 1, and Z the count of zeroes in the set. It was practical to allow a negative number of occurrences of a number in a set. And then the computer implementation of updates of these pairs (when sets were updated) corresponded directly (identical to) the computer implementation of of multiplication and division of complex numbers in polar form, i.e. (P1,Z1) "times" (P2,Z2) = (P1*P2, Z1+Z2), where the main trick is that the set {0} has product (1,1).

I find it difficult to write in the math notation required by this site. To be concrete, trying to formalize things a little by defining count of an element in a multiset, and then product of set, I couldn't get nice formula result for x raised to expression with multi-character name function. So I gave up on that, and tried simple textual formulas.

But even those proved too challenging for me here (and now I can appreciate the formula editor in Word!), I'm sorry. Also, sorry about the tags. I tried "multi-set" and "pair" but they don't exist, and I don't have rating to create new tags. I was unable to find good synonyms -- so, formulas lacking and tags lacking!

But hopefully the above description gives the gist of it: updates of sets (element added or removed) corresponded to updates of pairs, and the product, if defined, is trivially deduced from the pair. I wonder what those pair beasts are called and what the common notation is. And e.g. if there is any way to cut down on the complexity of results of addition and subtraction (I can't see any way, apparently addition and subtraction produce ugly ugly things not even deserving of name "beast"...).

?

share|improve this question
    
I don't really understand what you mean by "product." Could you give a simple example with explicit sets? –  Qiaochu Yuan Jul 13 '11 at 3:14
    
I am not 100% sure that [set-theory] is relevant. –  Asaf Karagila Jul 13 '11 at 4:27
    
@Asaf: Agreed. It looks like probability and statistics to me... –  Zhen Lin Jul 13 '11 at 6:38
1  
Qiaochu: I'll have to invent a notation for the sets, first. Let e.g. S1={3,3,5} denote a multiset where 3 occurs twice and 5 occurs once. The product is 3*3*5=45. When the set is updated by adding 0 forming S2={3,3,5,0} the product is 0. The pair for this set is (45,1), which implies product 0. Update yet again to remove one count of 0, yielding S3={3,3,5}, corresponds to updating the pair to (45,0), which yields product 45. Doing that again yields a set which I don't know how to express, but with pair (45,-1) and undefined product. Now remove the sets and the (P,Z) pairs live on their own. –  Alf P. Steinbach Jul 13 '11 at 11:28
    
@Asaf: "set-theory" was tag I found closest in meaning to "multiset". –  Alf P. Steinbach Jul 13 '11 at 11:38
show 3 more comments

2 Answers 2

Do you have other arithmetic operations defined on the pairs $(P,Z)$? As far as I can tell, what you have defined so far is just a pair $(P,Z)$ where $P$ takes values in the non-zero reals ($P\in \mathbb{R}\setminus{0}$) and $Z$ takes values in the reals (or the integers?) with a binary operation $(P_1,Z_1) \cdot (P_2,Z_2) = (P_1 \times P_2, Z_1 + Z_2)$.

In terms of abstract algebra, you have that $P$ is in the multiplicative group of non-zero reals, and $Z$ is in the additive group of either real numbers or integers. And what you have constructed, as the pair $(P,Z)$, is the group direct product of the two groups.

To define the process of evaluating $(P,Z)$ to the "product", assuming that $Z$ takes value in the integers, you can actually embed $(P,Z)$ into the formal Laurent series over the reals, by sending $(P,Z)$ to a monomial

$$ (P,Z)\mapsto P x^Z $$

which you can then formally evaluate at $z = 0$. With this you can get an analogy for $Z \neq 0, 1$ to the zeroes of higher degree, and the poles, of complex analysis.


Now let's think about the underlying multiset and how it corresponds to the pair $(P,Z)$. Your collection of multisets actually form a groupoid. The elements are given by the multisets and their formal inverses, and the partial function is given by "set addition and subtraction" in the following way.

Each element of your groupoid shall be either a multiset $m$ consisting of a collection of real numbers (or integers), or a formal inverse of a multiset (which we can denote as $m^{-1}$). The partial function is defined as follows: given $m$ and $n$ multisets, $m\times n$ is the multiset union of $m$ and $n$. Given $m^{-1}$ and $n^{-1}$ inverse multisets, $m^{-1}\times n^{-1} = (m\times n)^{-1}$ is the inverse of the multiset union of their corresponding multisets. If $m$ is a multiset and $n^{-1}$ is a multiset inverse, $m\times n^{-1}$ is only defined if $n$ is a multiset subset of $m$, and the output is $m$ with the elements of $n$ removed. Similarly we can defined $m^{-1}\times n$.

The mapping from the multiset notation to the $(P,Z)$ notation then corresponds to a groupoid homomorphism.

share|improve this answer
    
Of course, the mapping from the multiset notation to the $(P,Z)$ notation is not a monomorphism (i.e. you lose some information). The key is that if the information you only care about is the "product", that operation can be factored through this homomorphism, and so it is enough to keep track of the "pair" notation and not the full multiset notation. –  Willie Wong Jul 13 '11 at 14:03
    
Well, the practically useful operations are multiplication and division. In the question I'm asking about e.g. addition, can it be usefully defined? The pairs would be meaningless if they didn't have connection to sets (where set addition corresponds directly to pair multiplication), and mapping to real numbers. I don't have the background to understand either the words or the notation in your mapping pair -> number, but the idea is simple enough and I wish I'd thought of that! I think mapping numbers to pairs can't be simplified that much, since 0 maps to (1,1) as opposed to general (x,0)? –  Alf P. Steinbach Jul 13 '11 at 14:09
    
Yes, addition can be usefully defined, but not in the form you have written as pairs. You can extend $(P,Z)$ to the formal Laurent series I wrote about above. And as the formal Laurent series form a ring, you can do all the usual arithmetic operations, except for "division by zero"... but that is not a problem, since the "zero" element in the Laurent series expression corresponds to the $(0,0)$ element of the $(P,Z)$ notation, which you expressedly disallow. –  Willie Wong Jul 13 '11 at 14:19
    
"m×n−1 is only defined if n is a multiset subset of m, and the output is m with the elements of n removed" I think this must be wrong, or else you're talking about multisets where an element can't occur a negative number of times (have negative "multiplicity", oh how I love these words! :-) )? –  Alf P. Steinbach Jul 13 '11 at 14:19
    
Lifting back to the $(P,Z)$ notation, what you have is that you have addition while keeping track of the number of zeros. That is, if $Z_1 = Z_2$, then $(P_1,Z_1)+(P_2,Z_2) = (P_1 + P_2, Z_1)$. But if $Z_1 \neq Z_2$, you just leave it as the symbol $(P_1,Z_1)+(P_2,Z_2)$ without simplifying. Kinda like how you can add an subtract polynomials. (Indeed, you should think of this whole exercise as treating $0$ as the symbol $x$ in the usual notation for a polynomials....) –  Willie Wong Jul 13 '11 at 14:22
show 2 more comments

Generally, suppose you are working with multisets over a commutative monoid, i.e. a set with a commutative and associative product operation and identity element $1$. Apparently you desire to annotate each multiset with its product, so that, after insertions or deletions, the product can be efficiently updated by a single operation (vs. multiplying together a possibly very large number of elements contained in the multiset). For insertions, to update the product one simply multiplies the product by the inserted element. But this is a noninvertible operation for noncancellable elements (e.g. a $0$ such that $\rm\:0\cdot x = 0)\:.\:$ Thus, to efficiently support deletions, such noncancellable elements must be maintained separately from the product, in their own distinguished multiset.

Thus one may simply collapse all of the cancellable elements of a multiset into their product, and leave the noncancellable elements in multiset representation. So, generally, it suffices to represent the multiset by a triple containing (1) the submultiset of noncancellable elements; (2) the submultiset of cancellable elements; and (3) the product of the submultiset of cancellable elements.

To compute the product of all elements of the multiset one multiplies the cached product of all cancellable elements by the on-the-fly computed product of all of the noncancellable elements. This is a significant optimization when cancellable elements occur much more frequently than noncancellable elements (such as your example when $0$ is the only noncancellable element). One could also cache the entire product and invalidate it when a deletion occurs.

Note that one cannot eliminate the submultiset of cancellable elements from the triple if one desires it to be easily computable, since generally it cannot "decoded" from their product, or it may be computationally expensive to do so (e.g. factorization of integers).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.