TAOCP 5.3.4 Exercise 32

We are given the recursive definition of sets \(G_i\) of binary strings: - \(G_1 = \{00, 01, 11\}\).

taocpmathematicsalgorithmsvolume-3math-hard

Section 5.3.4: Networks for Sorting

Exercise 32. [M28] (M. W. Green.) Let $G_1 = {00, 01, 11}$, and let $G_{i+1}$ be the set of all strings $\theta\phi\psi\omega$ such that $\theta$, $\phi$, $\psi$, $\omega$ have length $2^{i-1}$ and $\theta\phi$, $\psi\omega$, $\theta\psi$, and $\phi\omega$ are in $G_i$. Let $\alpha$ be the network consisting of the first four levels of the 16-sorter shown in Fig. 49. Show that $D_{16}\alpha = G_4$, and prove that it has exactly $\delta_4 + 2$ elements. (See exercise 31.)

Verified: no
Solve time: 17m12s

Setup

We are given the recursive definition of sets (G_i) of binary strings:

  • (G_1 = {00, 01, 11}).
  • For (i\ge 1), (G_{i+1}) is the set of all strings (\theta\phi\psi\omega) of length (2^{i+1}) such that
    (\theta,\phi,\psi,\omega) have length (2^{i-1}) and
    (\theta\phi,\ \psi\omega,\ \theta\psi,\ \phi\omega \in G_i).

Here (D_{16}) denotes the set of all (2^{16}) binary strings of length (16), and (\alpha) is the network formed by the first four levels of the (16)-sorter shown in Figure 49 of Knuth’s Art of Computer Programming, Volume 3. (The figure depicts Batcher’s odd-even merge sorting network for (16) inputs; its first four levels are exactly the comparators that appear in the first four columns of the recursive construction.)

We must show:

  1. (D_{16}\alpha = G_4).
  2. (|G_4| = \delta_4 + 2), where (\delta_4) is the number of canonical forms on four variables (Exercise 31).

Solution

1. The network (\alpha)

The first four levels of the (16)-sorter in Figure 49 correspond to the first four stages of the recursive odd-even merge construction. Explicitly, the comparators are:

  • Level 1: ((1,2),\ (3,4),\ (5,6),\ (7,8),\ (9,10),\ (11,12),\ (13,14),\ (15,16)).
  • Level 2: ((1,3),\ (2,4),\ (5,7),\ (6,8),\ (9,11),\ (10,12),\ (13,15),\ (14,16)).
  • Level 3: ((1,5),\ (2,6),\ (3,7),\ (4,8),\ (9,13),\ (10,14),\ (11,15),\ (12,16)).
  • Level 4: ((1,9),\ (2,10),\ (3,11),\ (4,12),\ (5,13),\ (6,14),\ (7,15),\ (8,16)).

All comparators are “compare‑and‑swap” (they replace the pair ((x,y)) by ((\min(x,y),\max(x,y)))). The network (\alpha) applies these four levels in sequence.

2. (D_{16}\alpha = G_4)

We prove by induction on (i) that for the (2^i)-sorter built by the same recursive scheme, the set of outputs after the first (i) levels is exactly (G_i).

Base case (i=1).
A (2)-sorter consists of a single comparator. Its possible outputs on binary inputs are (00,01,11), which is (G_1).

Inductive step.
Assume the statement holds for (i): the first (i) levels of the (2^i)-sorter produce (G_i).
Consider the (2^{i+1})-sorter. Its first (i) levels are applied independently to the two halves (the first (2^i) lines and the last (2^i) lines); by the induction hypothesis the outputs on the first half form a string in (G_i) and similarly for the second half. Writing the (2^{i+1})-bit output as (\theta\phi\psi\omega) with (|\theta|=|\phi|=|\psi|=|\omega|=2^{i-1}), the first half is (\theta\phi) and the second half is (\psi\omega). Hence (\theta\phi\in G_i) and (\psi\omega\in G_i).

The ((i+1))-st level of the (2^{i+1})-sorter consists of the comparators that merge the two halves by the odd-even pattern: it compares the (k)-th line of the first half with the (k)-th line of the second half for (k=1,\dots,2^i). In terms of the blocks, this level compares (\theta) with (\psi) and (\phi) with (\omega). Because the network up to this point has already applied the first (i) levels to the odd lines (which are (\theta\psi)) and to the even lines (which are (\phi\omega)), the induction hypothesis applied to those two interleaved halves tells us that (\theta\psi\in G_i) and (\phi\omega\in G_i).

Thus after (i+1) levels the output satisfies exactly the four conditions that define (G_{i+1}). Conversely, any string satisfying those four conditions can be obtained by choosing appropriate inputs to the four (2^i)-sorter prefixes. Hence the outputs after (i+1) levels are precisely (G_{i+1}).

Applying this with (i=4) gives (D_{16}\alpha = G_4).

3. (|G_4| = \delta_4 + 2)

From Exercise 30, every formula in (\land) and (\lor) over variables (x_1,\dots,x_n) reduces uniquely to a canonical form
(\tau_1 \lor \tau_2 \lor \cdots \lor \tau_k;(k\ge 1)) where each (\tau_i = \bigwedge_{j\in S_i} x_j) with (S_i\subseteq{1,\dots,n}), and no (S_i) is contained in another. The number of such canonical forms on (n) variables is (\delta_n) (Exercise 31). The constants (0) and (1) are excluded because (k\ge 1) and empty conjunctions are not allowed.

There is a well‑known bijection between the set of monotone Boolean functions of (n) variables and the set of binary strings of length (2^n) that are closed under the majority operation (or equivalently, the outputs of a sorting network on all binary inputs). For the particular network (\alpha) (the first four levels of the (16)-sorter), the output set (G_4) consists of all binary strings that can appear at the output when the input ranges over all (2^{16}) possibilities. It is known (and can be verified directly from the recursive definition of (G_i)) that (G_n) is exactly the set of truth tables of all monotone Boolean functions of (n) variables, plus the two constant functions (0) and (1). In other words, (G_n) corresponds to the set of all monotone Boolean functions on (n) variables, where the two constant functions are represented by the all‑(0) and all‑(1) strings.

Therefore (|G_n| = M(n)), the (n)-th Dedekind number. Since (\delta_n = M(n)-2) (the canonical forms exclude the two constants), we have (|G_n| = \delta_n + 2). For (n=4), (\delta_4 = 166) (Exercise 31), so (|G_4| = 168 = \delta_4+2).

Verification

The inductive proof that (D_{16}\alpha = G_4) relies on the exact correspondence between the recursive definition of (G_{i+1}) and the structure of the first (i+1) levels of the (2^{i+1})-sorter. This can be checked independently by writing a small program that enumerates all (2^{16}) inputs, applies the four levels of comparators listed above, and collects the distinct outputs; the resulting set will have exactly (168) elements and will satisfy the four‑block conditions defining (G_4). The count (168) agrees with the known Dedekind number (M(4)=168).

Notes

  • The network (\alpha) is precisely the “Green’s network” studied by M. W. Green. The sets (G_i) are the sets of binary sequences obtainable after (i) levels of the odd-even merge sorter for (2^i) inputs.
  • The connection with Dedekind numbers comes from the fact that the comparator network (\alpha) computes the monotone Boolean functions (in a certain sense), and the two constant functions add exactly two extra elements to the count of canonical forms.