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:


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


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

⟨∀a, a′A : aa′ : 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:

⇒ { monotonicity of f }
   f.(aa′) ≤ f.a ∧ f.(aa′) ≤ f.a′
≡ {definition of ↓ }
   f.(aa′) = 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]:

   ([ij] ∘ map f).l
= { defn. pointwise extension }
   [ij].[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.(lilj), f.li+1,… f.lj-1, f.(lilj), f.lj+1,… f.ln-1]
= { defn. pointwise extension }
   map f.[l0,… li-1, lilj, li+1,… lj-1, lilj, lj+1,… ln-1]
= { defn. comparator box }
  (map f ∘ [ij]).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 }
⇐ { transitivity ≤ }

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.


Jim Apple said...

I'm sure you already know about Much Ado About Two.

Matías Giovannini said...

No I didn't! Thank you so much for the link.