TAOCP 4.6.3 Exercise 19
Let the multiplicity of an element $x$ in a multiset $A$ be denoted by $m_A(x)$.
Section 4.6.3: Evaluation of Powers
Exercise 19. [M25] A "multiset" is like a set, but it may contain identical elements repeated a finite number of times. If $A$ and $B$ are multisets, we define new multisets $A \uplus B$, $A \cup B$, and $A \cap B$ in the following way: An element occurring exactly $a$ times in $A$ and $b$ times in $B$ occurs exactly $a + b$ times in $A \uplus B$, exactly $\max(a, b)$ times in $A \cup B$, and exactly $\min(a, b)$ times in $A \cap B$. (A "set" is a multiset that contains no elements more than once; if $A$ and $B$ are sets, so are $A \uplus B$, $A \cup B$, and $A \cap B$, and the definitions given in this exercise agree with the customary definitions of set union and intersection.)
a) The prime factorization of a positive integer $n$ is a multiset $N$ whose elements are primes, where $\prod_{p \in N} p = n$. The fact that every positive integer can be uniquely factored into primes gives us a one-to-one correspondence between the positive integers and the finite multisets of prime numbers; for example, if $n = 2^2 \cdot 3^3 \cdot 17$, the corresponding multiset is $N = {2, 2, 3, 3, 3, 17}$. If $M$ and $N$ are the multisets corresponding respectively to $m$ and $n$, what multisets correspond to $\gcd(m, n)$, $\text{lcm}(m, n)$, and $mn$?
b) Every monic polynomial $f(z)$ over the complex numbers corresponds in a natural way to the multiset $F$ of its "roots"; we have $f(z) = \prod_{\zeta \in F}(z - \zeta)$. If $f(z)$ and $g(z)$ are the polynomials corresponding to the finite multisets $F$ and $G$ of complex numbers, what polynomials correspond to $F \uplus G$, $F \cup G$, and $F \cap G$?
c) Find as many interesting identities as you can that hold between multisets, with respect to the three operations $\uplus$, $\cup$, $\cap$.
Verified: yes
Solve time: 7m04s
Solution
Let the multiplicity of an element $x$ in a multiset $A$ be denoted by $m_A(x)$. By definition,
$$ m_{A\uplus B}(x)=m_A(x)+m_B(x), $$
$$ m_{A\cup B}(x)=\max\bigl(m_A(x),m_B(x)\bigr), $$
$$ m_{A\cap B}(x)=\min\bigl(m_A(x),m_B(x)\bigr). $$
All parts of the exercise reduce to these multiplicity formulas.
a)
Let
$$ m=\prod_p p^{\alpha_p}, \qquad n=\prod_p p^{\beta_p}, $$
and let $M,N$ be the corresponding multisets of prime factors. Then $m_M(p)=\alpha_p$ and $m_N(p)=\beta_p$.
The prime factorization formulas
$$ \gcd(m,n)=\prod_p p^{\min(\alpha_p,\beta_p)}, $$
$$ \operatorname{lcm}(m,n)=\prod_p p^{\max(\alpha_p,\beta_p)}, $$
$$ mn=\prod_p p^{\alpha_p+\beta_p} $$
show that the corresponding multisets are obtained by taking multiplicities $\min(\alpha_p,\beta_p)$, $\max(\alpha_p,\beta_p)$, and $\alpha_p+\beta_p$, respectively.
Hence:
$$ \boxed{\gcd(m,n)\longleftrightarrow M\cap N,} $$
$$ \boxed{\operatorname{lcm}(m,n)\longleftrightarrow M\cup N,} $$
$$ \boxed{mn\longleftrightarrow M\uplus N.} $$
b)
Let
$$ f(z)=\prod_{\zeta\in F}(z-\zeta), \qquad g(z)=\prod_{\zeta\in G}(z-\zeta), $$
where multiplicities in $F$ and $G$ are root multiplicities.
If $\zeta$ occurs with multiplicities $a$ and $b$ in $F$ and $G$, then it occurs with multiplicities
$$ a+b,\qquad \max(a,b),\qquad \min(a,b) $$
in $F\uplus G$, $F\cup G$, and $F\cap G$, respectively.
Therefore the polynomial corresponding to $F\uplus G$ is
$$ \prod_\zeta (z-\zeta)^{a+b} = \left(\prod_\zeta (z-\zeta)^a\right) \left(\prod_\zeta (z-\zeta)^b\right) =f(z)g(z). $$
Thus
$$ \boxed{F\uplus G \longleftrightarrow f(z)g(z).} $$
For $F\cap G$, the root $\zeta$ has multiplicity $\min(a,b)$. This is precisely the multiplicity of $\zeta$ in the greatest common divisor of $f$ and $g$. Taking the monic gcd,
$$ \boxed{F\cap G \longleftrightarrow \gcd(f,g).} $$
For $F\cup G$, the root $\zeta$ has multiplicity $\max(a,b)$. Since
$$ \max(a,b)=a+b-\min(a,b), $$
the corresponding polynomial is
$$ \frac{f(z)g(z)}{\gcd(f,g)}. $$
Equivalently, it is the monic least common multiple of $f$ and $g$. Hence
$$ \boxed{ F\cup G \longleftrightarrow \operatorname{lcm}(f,g) = \frac{f(z)g(z)}{\gcd(f,g)}. } $$
c)
Every identity can be verified by comparing multiplicities. Since multiplicities are nonnegative integers and the operations correspond to addition, maximum, and minimum, the resulting algebra closely parallels ordinary set theory.
The following identities hold for all multisets $A,B,C$.
Commutativity:
$$ A\uplus B=B\uplus A, $$
$$ A\cup B=B\cup A, $$
$$ A\cap B=B\cap A. $$
Associativity:
$$ (A\uplus B)\uplus C=A\uplus(B\uplus C), $$
$$ (A\cup B)\cup C=A\cup(B\cup C), $$
$$ (A\cap B)\cap C=A\cap(B\cap C). $$
Idempotence:
$$ A\cup A=A, $$
$$ A\cap A=A. $$
Distributive laws:
$$ A\cup(B\cap C) = (A\cup B)\cap(A\cup C), $$
$$ A\cap(B\cup C) = (A\cap B)\cup(A\cap C). $$
Absorption laws:
$$ A\cup(A\cap B)=A, $$
$$ A\cap(A\cup B)=A. $$
Relations involving $\uplus$:
$$ A\cap(B\uplus C) = (A\cap B)\uplus(A\cap C) $$
is false in general, but
$$ (A\uplus B)\cap(A\uplus C) = A\uplus(B\cap C) $$
is true, because
$$ \min(a+b,a+c)=a+\min(b,c). $$
Similarly,
$$ (A\uplus B)\cup(A\uplus C) = A\uplus(B\cup C), $$
because
$$ \max(a+b,a+c)=a+\max(b,c). $$
A particularly useful identity is
$$ (A\cup B)\uplus(A\cap B)=A\uplus B, $$
since for every multiplicity pair $(a,b)$,
$$ \max(a,b)+\min(a,b)=a+b. $$
Part (a) then yields the classical number-theoretic identity
$$ \gcd(m,n),\operatorname{lcm}(m,n)=mn. $$
Another consequence is
$$ (A\cup B)\cap C = (A\cap C)\cup(B\cap C), $$
and
$$ (A\cap B)\cup C = (A\cup C)\cap(B\cup C). $$
These examples illustrate that the algebra of multisets is governed by the arithmetic identities satisfied by the functions $\min$, $\max$, and addition on multiplicities.
$$ \boxed{ \begin{aligned} \gcd(m,n)&\leftrightarrow M\cap N,\ \operatorname{lcm}(m,n)&\leftrightarrow M\cup N,\ mn&\leftrightarrow M\uplus N; \end{aligned} \qquad \begin{aligned} F\uplus G&\leftrightarrow fg,\ F\cap G&\leftrightarrow \gcd(f,g),\ F\cup G&\leftrightarrow \operatorname{lcm}(f,g). \end{aligned} } $$
∎