TAOCP 5.3.4 Exercise 49

Section 5.3.4: Networks for Sorting

Exercise 49. [M23] Show that, in the notation of exercise 48, $(x \wedge y) \wedge z = x \wedge (y \wedge z)$ and $(x \vee y) \vee z = x \vee (y \vee z)$; however $(x \vee y) \wedge z$ is not always equal to $(x \wedge z) \vee (y \wedge z)$, and $(x \wedge y) \vee (x \wedge z) \vee (y \wedge z)$ does not always equal the middle $m$ elements of $x \uplus y \uplus z$. Find a correct formula, in terms of $x$, $y$, $z$ and the $\wedge$ and $\vee$ operations, for those middle elements.

Verified: no
Solve time: 6m04s

Solution

We work in the setting of Exercise 48: (x,y,z) are multisets of (m) numbers. For two such multisets (a,b),
(a\wedge b) is the multiset of the (m) smallest elements of (a\uplus b), and (a\vee b) is the multiset of the (m) largest elements.
The relation (a\ll b) means (a\wedge b = a) (equivalently, every element of (a) is (\le) every element of (b)).

Associativity of (\wedge) and (\vee)

We prove ((x\wedge y)\wedge z = x\wedge(y\wedge z)); the proof for (\vee) is symmetric (replace every number by its negative).

Let (U = x\uplus y\uplus z) (size (3m)). By definition, ((x\wedge y)\wedge z) is the (m) smallest elements of ((x\wedge y)\uplus z).
Observe that (x\wedge y) consists exactly of the (m) smallest elements of (x\uplus y). Any element of ((x\uplus y)\setminus(x\wedge y)) is (\ge) every element of (x\wedge y).
The multiset (V = (x\wedge y)\uplus z) has size (2m) and is a submultiset of (U). We claim that the (m) smallest elements of (U) are precisely the (m) smallest elements of (V).
Indeed, if some (x_0\in U\setminus V) were among the (m) smallest of (U), then (x_0) would belong to ((x\uplus y)\setminus(x\wedge y)); hence (x_0\ge \max(x\wedge y)). But (V) contains all (m) elements of (x\wedge y) and all (m) elements of (z), so it contains at least (m) elements (\le \max(x\wedge y)\le x_0). This contradicts (x_0) being one of the (m) smallest of (U). Therefore the (m) smallest of (U) lie entirely in (V) and equal the (m) smallest of (V).
Consequently ((x\wedge y)\wedge z = \min_m(U) = x\wedge(y\wedge z)). By the same reasoning (or by negating all numbers) we obtain ((x\vee y)\vee z = x\vee(y\vee z)).

Failure of the distributive-like identities

Take (m=2) and define
[ x = {0,10},\qquad y = {5,15},\qquad z = {5,10}. ]

• First identity:
  (x\vee y = {10,15}), so ((x\vee y)\wedge z = \min_2({10,15,5,10}) = {5,10}).
  (x\wedge z = \min_2({0,10,5,10}) = {0,5}),
  (y\wedge z = \min_2({5,15,5,10}) = {5,5}),
  ((x\wedge z)\vee(y\wedge z) = \max_2({0,5,5,5}) = {5,5}).
  Since ({5,10}\neq{5,5}), we have ((x\vee y)\wedge z \neq (x\wedge z)\vee(y\wedge z)).

• Second identity:
  (x\wedge y = {0,5},; x\wedge z = {0,5},; y\wedge z = {5,5}). Their (\vee) (i.e. the (2) largest of the union) is ({5,5}).
  The full union (x\uplus y\uplus z = {0,5,5,10,10,15}); its middle two elements (ranks (3) and (4)) are ({5,10}).
  Thus ((x\wedge y)\vee(x\wedge z)\vee(y\wedge z) \neq \text{middle }m\text{ elements}).

A correct formula for the middle (m) elements

Let (A = x\wedge y) and (B = x\vee y). Then (A\ll B) and (x\uplus y = A\uplus B).
The total multiset is (T = A\uplus B\uplus z) (size (3m)).
The (m) smallest elements of (T) are (A\wedge z = x\wedge y\wedge z).
The (m) largest elements of (T) are (B\vee z = x\vee y\vee z).
The remaining (m) elements (the middle (m)) are exactly the (m) largest elements of the (2m) smallest elements of (T).

The (2m) smallest elements of (T) are obtained by removing the (m) largest ((B\vee z)) from (T). Since (B\vee z\subseteq B\uplus z), this leaves
[ A \uplus \bigl((B\uplus z)\setminus(B\vee z)\bigr) = A \uplus (B\wedge z). ] Hence the middle (m) elements are the (m) largest of (A\uplus(B\wedge z)), i.e.
[ A \vee (B\wedge z) = (x\wedge y) \vee \bigl((x\vee y)\wedge z\bigr). ]

By symmetry, any permutation of (x,y,z) in this expression also yields the correct middle (m) elements.

[ \boxed{(x \wedge y) \vee \bigl((x \vee y) \wedge z\bigr)} ] ∎