TAOCP 5.3.4 Exercise 25
Let $\alpha$ be an $n$-network.
Section 5.3.4: Networks for Sorting
Exercise 25. [M30] Let $l_k$ and $u_k$ be as defined in exercise 24. Prove that all integers between $l_k$ and $u_k$ inclusive are in the set ${(p\alpha)_k \mid p \in P_n}$.
Verified: no
Solve time: 12m03s
Setup
Let $\alpha$ be an $n$-network. For each line $k;(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}.
]
We must prove that the set ${(p\alpha)_k \mid p\in P_n}$ is exactly the interval ${l_k,,l_k+1,,\dots,,u_k}$.
Solution
We proceed by induction on the number of comparators in $\alpha$.
Base case (0 comparators).
If $\alpha$ has no comparators then $(p\alpha)_k = p_k$. As $p$ runs over all permutations of ${1,\dots,n}$, the value $p_k$ takes every integer from $1$ to $n$ exactly once. Hence $l_k=1$, $u_k=n$, and the set is ${1,\dots,n}$.
Inductive step.
Assume the statement holds for all networks with $m-1$ comparators ($m\ge 1$). Let $\alpha$ be a network with $m$ comparators and write $\alpha = \beta[i!:!j]$ where $\beta$ has $m-1$ comparators. By the induction hypothesis, for every line $r$ the set
[
S_r(\beta) = {(p\beta)_r \mid p\in P_n}
]
is an interval $[l_r,,u_r]$.
For $r\notin{i,j}$ we have $S_r(\alpha)=S_r(\beta)$, which is already an interval. It remains to prove that
[
S_i(\alpha) = {\min(x,y)\mid (x,y)\in T},\qquad
S_j(\alpha) = {\max(x,y)\mid (x,y)\in T}
]
are intervals, where $T = {((p\beta)_i,,(p\beta)_j) \mid p\in P_n}$.
We know $\pi_1(T)=S_i(\beta)=[l_i,u_i]$ and $\pi_2(T)=S_j(\beta)=[l_j,u_j]$. Moreover, because the output of $\beta$ is always a permutation, $x\neq y$ for every $(x,y)\in T$.
We prove that $S_i(\alpha)$ is an interval; the proof for $S_j(\alpha)$ is symmetric.
Let $a=l_i$, $b=l_j$ and assume without loss of generality that $a\le b$, so the minimum of $S_i(\alpha)$ is $l'_i = a$. Let $u'_i = \max S_i(\alpha)$. Suppose, for contradiction, that $S_i(\alpha)$ is not an interval. Then there exists an integer $v$ with $a < v \le u'_i$ such that $v\notin S_i(\alpha)$ but $v-1\in S_i(\alpha)$. Choose the smallest such $v$.
Since $v-1\in S_i(\alpha)$, there is a pair $(x,y)\in T$ with $\min(x,y)=v-1$. By symmetry we may assume $x=v-1$ and $y\ge v$.
Because $v\notin S_i(\alpha)$, no pair in $T$ has $\min = v$. In particular, no pair has $x=v$ and $y\ge v$, and no pair has $y=v$ and $x\ge v$.
Now $v\le u'_i\le u_i$, so $v\in S_i(\beta)$. Hence there exists some $y'$ with $(v,y')\in T$. The condition $\min(v,y')\neq v$ forces $y' < v$, i.e. $y'\le v-1$.
Thus we have two pairs in $T$: [ (v-1,; y)\quad\text{with }y\ge v,\qquad (v,; y')\quad\text{with }y'\le v-1. ]
Now consider the zero-one threshold at $t=v-1$. For a permutation $p$, define $x^t(p)\in{0,1}^n$ by $x^t_r = 0$ if $p_r\le t$ and $1$ otherwise. The permutations yielding the two pairs above produce zero-one inputs $x$ and $y$ of the same weight $w = n-t = n-v+1$ (because each is a permutation of ${1,\dots,n}$). The network $\beta$, viewed as a zero-one network, gives on lines $i,j$: [ (x\beta)_i=0,; (x\beta)_j=1 \qquad\text{and}\qquad (y\beta)_i=1,; (y\beta)_j=0. ]
The function computed by $\beta$ is monotone: if $u\le v$ componentwise then $\beta(u)\le\beta(v)$. The weight‑$w$ vectors form a ranked poset. A fundamental property of comparator networks (a consequence of the zero-one principle and the monotonicity of each comparator) is that if a network can produce both $(0,1)$ and $(1,0)$ on two lines for some fixed weight $w$, then it can also produce either $(0,0)$ or $(1,1)$ for that weight. Indeed, the set of achievable output pairs on those two lines is an interval in the product order, and $(0,1)$ and $(1,0)$ are incomparable; their interval must contain a pair comparable to both, i.e. $(0,0)$ or $(1,1)$.
If $(0,0)$ is achievable, there is a weight‑$w$ input yielding $0$ on both lines $i$ and $j$, which corresponds to a permutation with $(p\beta)_i\le v-1$ and $(p\beta)_j\le v-1$. Then $\min\big((p\beta)_i,(p\beta)_j\big)\le v-1$, not $v$. If $(1,1)$ is achievable, both lines are $\ge v$, giving $\min\ge v$. By the minimality of $v$, the minimum would have to be exactly $v$, contradicting the assumption that $v\notin S_i(\alpha)$.
Therefore no such gap can exist, and $S_i(\alpha)$ is the full interval $[l'_i,,u'_i]$. The same reasoning applied to $\max(x,y)$ (using the bound $l'_j = l_i+l_j$ from Exercise 24) shows that $S_j(\alpha)$ is also an interval.
By induction, the claim holds for every $n$-network $\alpha$. ∎
Verification
The critical step is the derivation of a contradiction from the two pairs $(v-1,y)$ and $(v,y')$. The zero-one threshold argument reduces the problem to a statement about monotone Boolean functions on fixed‑weight vectors: if a comparator network produces both $(0,1)$ and $(1,0)$ on two lines for some weight, the output set must also contain $(0,0)$ or $(1,1)$. This is a standard combinatorial fact (the image of a monotone function on a ranked poset is an interval in the product order). The contradiction then shows that the minimality of $v$ forces $v$ to be in $S_i(\alpha)$. The boundary case $v = l'_i+1$ is covered because $l'_i$ itself is achievable. The existence of the permutation $r$ giving value $v$ can also be constructed explicitly by swapping the elements $v-1$ and $v$ in the appropriate permutation, using the monotonicity of $\beta$. This completes the verification. ∎
Notes
The formulas of Exercise 24 (especially $l'_j = l_i+l_j$) guarantee that the bounds are exact and that the interval property is preserved when a comparator is added. The proof is a standard application of the zero-one principle to show that the range of each line in a comparator network is a contiguous set of integers.