2008-07-09

The Zero-One Principle

Continuing my treatment of comparator networks, I've experimenting with the discovery of minimal sorting networks using evolutionary programming, about which I plan to write in the future. One of the things needed for that is a means of quickly evaluating if a given network actually sorts all sequences of a given length or not. There is a very powerful theoretical result, called the zero-one principle that aids in identifying sorting networks from general comparator networks. It says:

(The zero-one principle): A comparator network N of width n sorts all sequences of length m if it sorts all 2n binary sequences of length n.

The proof is not difficult, and is a good showcase for the equational reasoning I'm so fond of. First, some definitions.

Given an ordered set (A, ≤), the minimum of elements a, a′A is the unique element aa′ such that:

```a↓a′ ≤ a ∧ a↓a′ ≤ a′
```

Dually, the maximum of a, a′A is the unique element aa′ such that:

```a ≤ a↑a′ ∧ a′ ≤ a↑a′
```

A monotonic function from ordered set (A, ≤) to ordered set (B, ⊑) is a function that preserves orderings, that is:

```⟨∀a, a′ ∈ A : a ≤ a′ : f.a ⊑ f.a′⟩
```

With that, I can prove the first

Lemma: monotonic functions preserve minima (dually, maxima)

Let f be monotonic on A. Then ∀a, a′A, by definition of minimum:

```   a↓a′ ≤ a ∧ a↓a′ ≤ a′
⇒ { monotonicity of f }
f.(a↓a′) ≤ f.a ∧ f.(a↓a′) ≤ f.a′
≡ {definition of ↓ }
f.(a↓a′) = f.a ↓ f.a′
```

And dually for maxima.

Recall that an comparator box is a function (xy) = (xy, xy). Applied to a sequences, a comparator [ij] with 0 ≤ ij < n sorts elements i and j of [l0, l1,… ln-1] into [l0,… li-1, lilj, li+1,… lj-1, lilj, lj+1,… ln-1]. A comparator network N is a sequence of such boxes, and as a sequence, it has a monoidal structure under composition. For a function f : AB, the pointwise extension map f : AnBn maps a sequence [l0, l1,… ln-1]∈An to the sequence [f.l0, f.l1,… f.ln-1]∈Bn. Hence, the following

Lemma: comparator networks commute with the pointwise extension of monotonic functions

Let f be monotonic on A. By induction on the structure of N, we have for the base case a single comparator box [ij]:

```   ([i ↕ j] ∘ map f).l
= { defn. pointwise extension }
[i ↕ j].[f.l0, f.l1,… f.ln-1]
= { defn. comparator box }
[f.l0,… f.li-1, f.li ↓ f.lj, f.li+1,… f.lj-1, f.li ↑ f.lj, f.lj+1,… f.ln-1]
= { lemma }
[f.l0,… f.li-1, f.(li↓lj), f.li+1,… f.lj-1, f.(li↑lj), f.lj+1,… f.ln-1]
= { defn. pointwise extension }
map f.[l0,… li-1, li↓lj, li+1,… lj-1, li↑lj, lj+1,… ln-1]
= { defn. comparator box }
(map f ∘ [i ↕ j]).l
```

For the inductive case, a comparator network N can be decomposed as the composition of comparator networks NL and NR, such that:

```   N ∘ map f
= { compositionality of network }
(NL ∘ NR) ∘ map f
= { associtativity of composition, base case }
NL ∘ (map f ∘ NR)
= { associtativity of composition, base case }
map f ∘ (NL ∘ NR)
= { compositionality of network }
map f ∘ N
```

Now I can prove the

Theorem: The zero-one principle as stated above is valid.

Suppose there is a sequence lAn that is not sorted by N, that is, for m = N.l there is an 0 ≤ k < n-1 such that mkmk+1. For all cA, define f : A → {0, 1} as f.c = 1 if mkc, and f.c = 0 otherwise. Now f is monotonic:

```   f.c ≤ f.c′
⇐ { range of f }
f.c = 0 ∨ f.c′ = 1
≡ { defn. f }
mk ≰ c ∧ mk ≤ c′
≡
mk ≤ c ⇒ mk ≤ c′
⇐ { transitivity ≤ }
c ≤ c′
```

Furthermore, f.mk = 1 and f.mk+1 = 0 which means that (map f ∘ N).l is unsorted. But since f is monotonic, by the second Lemma, (N ∘ map f).l is unsorted too. In other words, if there's a sequence over An that N doesn't sort, then there is a sequence over 2n that N doesn't sort either; by contrapositive the theorem follows.

In the next post I'll show how this translates in an efficient test for comparator networks.