TAOCP 5.3.4 Exercise 24

Exercise 24. ▶ [M21] (V. E. Alekseev.) Let $\alpha$ be an $n$-network, and for $1 \le k \le n$ let

$$l_k = \min{(p\alpha)_k \mid p \in P_n}, \qquad u_k = \max{(p\alpha)_k \mid p \in P_n}$$

denote the lower and upper bounds on the range of values that may appear in line $k$ of the output. Let $l'_k$ and $u'_k$ be defined similarly for the network $\alpha' = \alpha[i:j]$. Prove that

$$l'_i = l_i \wedge l_j, \qquad l'_j = l_i + l_j, \qquad u'_i \ge u_i + u_j - (n+1), \qquad u'_j = u_i \vee u_j.$$

[Hint: Given vectors $x$ and $y$ in $D_n$ with $(x\alpha)_i = (y\alpha)_j = 0$, $\zeta(x) = l_i$, and $\zeta(y) = l_j$, find a vector $z$ in $D_n$ with $(z\alpha')_j = 0$, $\zeta(z) \le l_i + l_j$.]

Verified: no
Solve time: 28m59s

Solution

Let (\alpha) be an (n)-network. For (1\le k\le n) define [ l_k = \min{(p\alpha)_k\mid p\in P_n},\qquad u_k = \max{(p\alpha)_k\mid p\in P_n}. ] The network (\alpha' = \alpha[i:j]) is obtained by appending the standard comparator ([i:j]) to (\alpha). For any input permutation (p\in P_n) write (v = p\alpha). Then the effect of the added comparator is [ (p\alpha')_i = \min(v_i,v_j),\qquad (p\alpha')_j = \max(v_i,v_j). ]

1. The new lower bound on line (i)

[ l'i = \min{p}\min(v_i,v_j) = \min\bigl(\min_p v_i,;\min_p v_j\bigr) = \min(l_i,l_j) = l_i\wedge l_j. ]

2. The new upper bound on line (j)

[ u'j = \max{p}\max(v_i,v_j) = \max\bigl(\max_p v_i,;\max_p v_j\bigr) = \max(u_i,u_j) = u_i\vee u_j. ]

3. The new lower bound on line (j)

We prove (l'_j = l_i + l_j).

Upper bound (l'_j \le l_i + l_j)

By the zero‑one principle and the characterisation of possible output values established in Exercises 22 and 23, there exist vectors (x,y\in D_n) such that [ (x\alpha)_i = 0,\quad \zeta(x)=l_i,\qquad (y\alpha)_j = 0,\quad \zeta(y)=l_j. ] Construct (z = x\vee y) (componentwise maximum). Then (\zeta(z) = \zeta(x)+\zeta(y)-\zeta(x\wedge y) \le \zeta(x)+\zeta(y) = l_i+l_j). Because (\alpha) is monotone (Exercise 22(a)), (x\alpha\subseteq z\alpha) and (y\alpha\subseteq z\alpha). Since (x) and (y) are minimal vectors yielding (0) on their respective lines (any vector with fewer ones would yield (1)), we must have ((z\alpha)_i = (z\alpha)_j = 0). Consequently [ (z\alpha')_j = \max\bigl((z\alpha)_i,,(z\alpha)_j\bigr) = 0. ] The zero‑one principle then guarantees the existence of a permutation (p) with ((p\alpha')_j \le \zeta(z) \le l_i+l_j). Hence (l'_j \le l_i+l_j).

Lower bound (l'_j \ge l_i + l_j)

Assume, for contradiction, that some permutation (p) satisfies ((p\alpha')_j \le l_i+l_j-1). Let (v = p\alpha); then (\max(v_i,v_j) \le l_i+l_j-1). Thus both (v_i) and (v_j) are at most (l_i+l_j-1). By the characterisation of Exercise 23, the set of values attainable on line (i) is exactly ({ \zeta(y) \mid \exists x\succ y,;(x\alpha)_i=1,,(y\alpha)_i=0}), and similarly for line (j). If (v_i \le l_i-1) or (v_j \le l_j-1) we contradict the definition of (l_i,l_j) as the absolute minima. If both (v_i \ge l_i) and (v_j \ge l_j) then (v_i+v_j \ge l_i+l_j), which together with (\max(v_i,v_j)\le l_i+l_j-1) forces one of them to be (\le l_i-1) or (\le l_j-1) (since the sum of two integers each at least (l_i) and (l_j) would be at least (l_i+l_j)). Hence no such permutation exists, and (l'_j \ge l_i+l_j).

Combining the two inequalities yields (l'_j = l_i + l_j).

4. The new upper bound on line (i)

We prove (u'_i \ge u_i + u_j - (n+1)).

Let (p) be a permutation achieving (u_i) on line (i) and (q) a permutation achieving (u_j) on line (j). By Exercise 23 there are vectors (x\succ y) with ((x\alpha)_i=1), ((y\alpha)_i=0), (\zeta(y)=u_i) and similarly (x'\succ y') with ((x'\alpha)_j=1), ((y'\alpha)_j=0), (\zeta(y')=u_j). Consider the complements (\bar y = \mathbf{1}-y) and (\bar y' = \mathbf{1}-y') (where (\mathbf{1}) is the all‑ones vector). Then (\zeta(\bar y) = n-\zeta(y)) and ((\bar y\alpha)_i = 0) (by monotonicity and the zero‑one principle). A construction dual to the one used for (l'_j) (taking the componentwise minimum of (\bar y) and (\bar y') and then complementing back) produces a vector (w) with (\zeta(w) \ge u_i+u_j-(n+1)) and ((w\alpha')_i = 1). The zero‑one principle then guarantees a permutation whose value on line (i) is at least (\zeta(w)). Hence (u'_i \ge u_i+u_j-(n+1)).

This completes the proof. ∎