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 2ⁿ 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 a↓a′ such that:

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

Dually, the maximum of a, a′ ∈ A is the unique element a↑a′ 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 (x ↕ y) = (x↓y, x↑y). Applied to a sequences, a comparator [i ↕ j] with 0 ≤ i ≤ j < n sorts elements i and j of [l₀, l₁,… l_n-1] into [l₀,… l_i-1, l_i↓l_j, l_i+1,… l_j-1, l_i↑l_j, l_j+1,… l_n-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 : A → B, the pointwise extension map f : Aⁿ → Bⁿ maps a sequence [l₀, l₁,… l_n-1]∈Aⁿ to the sequence [f.l₀, f.l₁,… f.l_n-1]∈Bⁿ. 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 [i ↕ j]:

   ([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 N_L and N_R, 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 l∈Aⁿ that is not sorted by N, that is, for m = N.l there is an 0 ≤ k < n-1 such that m_k ≰ m_k+1. For all c∈A, define f : A → {0, 1} as f.c = 1 if m_k ≤ c, 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.m_k = 1 and f.m_k+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 Aⁿ that N doesn't sort, then there is a sequence over 2ⁿ 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.