1
$\begingroup$

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"...).

?

  • 0
    @Alf: Actually, no. I believe that the zero-divisor tag is meant for something else. Qiaochu removed it (and rightfully I might add) and left only the [set-theory] tag. Had it been me seeing the question first, I might have left it only with [zero-divisor] instead and let someone else deal with the problem. Perhaps a meta thread is in order for this...2011-07-13

2 Answers 2

5

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.

  • 0
    Thanks. I'll have some things to look up and learn about. Happily, there's no law against learning for old folks. :-)2011-07-13
4

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).