TAOCP 5.3.4 Exercise 26

Section 5.3.4: Networks for Sorting

Exercise 26. [M24] (R. W. Floyd.) Let $\alpha$ be an $n$-network. Prove that $\alpha$ can determine the set $D_n\alpha = {x\alpha \mid x \in D_n}$ from the set $P_n\alpha = {p\alpha \mid p \in P_n}$; conversely, $P_n\alpha$ can be determined from $D_n\alpha$.

Verified: no
Solve time: 18m25s

Solution

Let (D_n = {0,1}^n) be the set of all (0)-(1) vectors of length (n), and let (P_n) be the set of all permutations of ({1,2,\dots,n}). For a vector (v \in {1,\dots,n}^n) and an integer (t) with (0 \le t \le n-1) we define its threshold vector [ v^{(t)}i = \begin{cases} 1 & \text{if } v_i > t,\ 0 & \text{otherwise}. \end{cases} ] If (v \in P_n) then (v^{(t)}) has exactly (n-t) ones, and (v^{(0)} \ge v^{(1)} \ge \cdots \ge v^{(n-1)}) is a maximal chain in the Boolean lattice (D_n); moreover (v) is uniquely determined by its thresholds because (v_i = \sum{t=0}^{n-1} v^{(t)}_i).

A comparator ([i:j]) replaces the values on lines (i) and (j) by their minimum and maximum. For any totally ordered set (S) and any threshold (t), the threshold operation (\theta_t(x) = 1) if (x>t) else (0) commutes with the comparator: [ \theta_t(\min(a,b)) = \min(\theta_t(a),\theta_t(b)),\qquad \theta_t(\max(a,b)) = \max(\theta_t(a),\theta_t(b)). ] Consequently, for any (n)-network (\alpha) and any vector (v) whose components lie in a totally ordered set, [ (v\alpha)^{(t)} = (v^{(t)})\alpha \qquad\text{for all } t. \tag{1} ] When (\alpha) acts on (D_n) it preserves the number of (1)'s (each comparator preserves the sum of the two bits), and it is a lattice homomorphism: for all (x,y \in D_n), [ (x \wedge y)\alpha = x\alpha \wedge y\alpha,\qquad (x \vee y)\alpha = x\alpha \vee y\alpha. \tag{2} ]

(D_n\alpha) from (P_n\alpha)

For any (q \in P_n\alpha) we have (q = p\alpha) for some (p \in P_n). By (1), (q^{(t)} = (p^{(t)})\alpha \in D_n\alpha). Hence [ { q^{(t)} \mid q \in P_n\alpha,; 0 \le t < n } \subseteq D_n\alpha. ] Conversely, let (y \in D_n\alpha). Then (y = x\alpha) for some (x \in D_n). Let (m = \sum_i x_i) be the number of ones in (x). Construct a permutation (p) by assigning the values (1,\dots,n-m) to the positions where (x_i=0) and the values (n-m+1,\dots,n) to the positions where (x_i=1). Then (p^{(m)} = x), and (1) gives ((p\alpha)^{(m)} = x\alpha = y). Thus (y) is a threshold of some permutation output, so [ D_n\alpha \subseteq { q^{(t)} \mid q \in P_n\alpha,; 0 \le t < n }. ] Therefore [ D_n\alpha = { q^{(t)} \mid q \in P_n\alpha,; 0 \le t < n }, ] which shows that (D_n\alpha) is completely determined by (P_n\alpha).

(P_n\alpha) from (D_n\alpha)

Define [ Q = { q \in P_n \mid q^{(t)} \in D_n\alpha \text{ for all } 0 \le t < n }. ] We already know (P_n\alpha \subseteq Q) by the argument above. To prove the reverse inclusion, let (q \in Q). For each (t) choose an arbitrary (x_t^0 \in D_n) with (x_t^0\alpha = q^{(t)}); such an (x_t^0) exists because (q^{(t)} \in D_n\alpha). We now construct a chain (x_0 \ge x_1 \ge \cdots \ge x_{n-1}) with (x_t\alpha = q^{(t)}) by induction: [ x_0 = x_0^0,\qquad x_t = x_{t-1} \wedge x_t^0 \quad (1 \le t \le n-1). ] Using the lattice homomorphism property (2) and the fact that (q^{(t-1)} \ge q^{(t)}), [ x_t\alpha = (x_{t-1} \wedge x_t^0)\alpha = x_{t-1}\alpha \wedge x_t^0\alpha = q^{(t-1)} \wedge q^{(t)} = q^{(t)}. ] Also (x_t \le x_{t-1}) by definition of meet. Since (\alpha) preserves the number of ones, each (x_t) has the same number of ones as (q^{(t)}), namely (n-t). Together with (x_t \le x_{t-1}) and the ranks differing by one, this forces (x_{t-1}) to cover (x_t) (they differ in exactly one coordinate). Hence (x_0 \ge x_1 \ge \cdots \ge x_{n-1}) is a maximal chain in (D_n).

Now define a permutation (p) by [ p_i = \sum_{t=0}^{n-1} x_{t,i}. ] Because the chain is maximal, each coordinate (p_i) is a distinct integer from (1) to (n); thus (p \in P_n). By construction, (p^{(t)} = x_t) for all (t). Applying (1) we obtain [ (p\alpha)^{(t)} = (p^{(t)})\alpha = x_t\alpha = q^{(t)} \quad\text{for all } t. ] Since a permutation is uniquely determined by its threshold vectors, (p\alpha = q). Hence (q \in P_n\alpha), and we have (Q \subseteq P_n\alpha).

Consequently [ P_n\alpha = { q \in P_n \mid q^{(t)} \in D_n\alpha \text{ for all } 0 \le t < n }, ] so (P_n\alpha) is completely determined by (D_n\alpha).

Both directions have been established: (D_n\alpha) can be computed from (P_n\alpha) and vice versa.

This completes the proof. ∎