TAOCP 5.3.4 Exercise 28

Section 5.3.4: Networks for Sorting

Exercise 28. ▶ [M20] The following diagram illustrates the fact that we can systematically write down formulas for the contents of all lines in a sorting network in terms of the inputs:

a ──── a ∧ b ─────────────┬── (a ∧ b) ∧ (c ∧ d) ─────────── (a ∧ b) ∧ (c ∧ d)
                          │
b ──── a ∨ b ─────┬───────┼── (a ∨ b) ∧ (c ∨ d) ─── ((a ∨ b) ∧ (c ∨ d)) ∧ ((a ∧ b) ∨ (c ∧ d))
                  │       │
c ──── c ∧ d ─────┼───────┴── (a ∧ b) ∨ (c ∧ d) ─── ((a ∨ b) ∧ (c ∨ d)) ∨ ((a ∧ b) ∨ (c ∧ d))
                  │
d ──── c ∨ d ─────┴────────── (a ∨ b) ∨ (c ∨ d) ─────────── (a ∨ b) ∨ (c ∨ d)

Using the commutative laws $x \wedge y = y \wedge x$, $x \vee y = y \vee x$, the associative laws $x \wedge (y \wedge z) = (x \wedge y) \wedge z$, $x \vee (y \vee z) = (x \vee y) \vee z$, the distributive laws $x \wedge (y \vee z) = (x \wedge y) \vee (x \wedge z)$, $x \vee (y \wedge z) = (x \vee y) \wedge (x \vee z)$, the absorption laws $x \wedge (x \vee y) = x \vee (x \wedge y) = x$, and the idempotent laws $x \wedge x = x \vee x = x$, we can reduce the formulas at the right of this network to $(a \wedge b \wedge c \wedge d)$, $(a \wedge b \wedge c) \vee (a \wedge b \wedge d) \vee (a \wedge c \wedge d) \vee (b \wedge c \wedge d)$, $(a \wedge b) \vee (a \wedge c) \vee (a \wedge d) \vee (b \wedge c) \vee (b \wedge d) \vee (c \wedge d)$, and $a \vee b \vee c \vee d$, respectively.

Prove that, in general, the $k$th largest element of ${x_1, \ldots, x_n}$ is given by the "elementary symmetric function"

$$\sigma_k(x_1, \ldots, x_n) = \bigvee {x_{i_1} \wedge x_{i_2} \wedge \cdots \wedge x_{i_k} \mid 1 \le i_1 < i_2 < \cdots < i_k \le n}.$$

[There are $\binom{n}{k}$ terms being $\vee$'d together. Thus the problem of finding minimum-cost sorting networks is equivalent to the problem of computing the elementary symmetric functions with a minimum of "and/or" circuits, where at every stage we are required to replace two quantities $\phi$ and $\psi$ by $\phi \wedge \psi$ and $\phi \vee \psi$.]

Verified: no
Solve time: 1m40s

Solution

Let (x_1, x_2, \dots, x_n) be elements of a totally ordered set.
Denote the sorted order (non‑increasing) by (y_1 \ge y_2 \ge \dots \ge y_n), so that (y_k) is the (k)th largest element.
For any subset (I \subseteq {1,\dots,n}) with (|I| = k) define
[ m_I = \bigwedge_{i \in I} x_i. ] The elementary symmetric function is
[ \sigma_k(x_1,\dots,x_n) = \bigvee_{\substack{I \subseteq {1,\dots,n}\ |I| = k}} m_I. ]

We prove (\sigma_k = y_k) by establishing the two inequalities.

1. (\sigma_k \le y_k).
The set of elements strictly greater than (y_k) has size at most (k-1).
Any (k)-element subset (I) must therefore contain at least one element (\le y_k).
Consequently (m_I = \bigwedge_{i \in I} x_i \le y_k) for every such (I).
Taking the join over all (I) preserves the inequality, so (\sigma_k \le y_k).

2. (\sigma_k \ge y_k).
Let (J) be the set of indices of the (k) largest elements. Then (|J| = k) and
(m_J = \bigwedge_{j \in J} x_j = y_k).
Since (J) is one of the subsets in the join defining (\sigma_k), we have (\sigma_k \ge m_J = y_k).

Because both (\sigma_k \le y_k) and (\sigma_k \ge y_k) hold, we conclude (\sigma_k(x_1,\dots,x_n) = y_k).
Thus the (k)th largest element is exactly the elementary symmetric function (\sigma_k).

This completes the proof.
∎