Saturday, October 12, 2019

Multiset division and remainder

The operations of division and remainder, so familar to us because of their use with the natural numbers, can be generalized to multisets. Numerous familiar concepts can be generalized and better understood through the use of multisets, which are relatively underused in the current situation. The first thing one realizes is that we can use this to divide and get the remainder of the prime factorization multiset of a number. So for example with 8 we can divide its factorization by 2 to get 2, and a remainder of 2 which is actually how we compute roots anyways to get $2\sqrt{2}$. So this means that nth-roots are actually based upon dividing a multiset, though it was never taught to me that way and I don't think its that common to describe it like that. Here is some clojure code that deals with the general case of dividing multisets.
(defn multiset-division
  [coll divisor]

  (Multiset.
   (into
    {}
    (for [elem (support coll)
          :let [n (multiplicity coll elem)]
          :when (<= divisor n)]
      [elem (quot n divisor)]))))

(defn multiset-remainder
  [coll divisor]

  (Multiset.
   (into
    {}
    (for [elem (support coll)
          :let [n (multiplicity coll elem)]
          :when (not (zero? (mod n divisor)))]
      [elem (mod n divisor)]))))

1 comment:

  1. yes, and division of an addition multiset of a number is ordinary division. So division of a exponentiation multiset of a number must be inverse tetration.

    ReplyDelete