Sorting networks on 14 inputs need 50 comparators
Abstract
Let S(N) be the least number of comparators in a sorting network on N inputs. Its value is known for N ≤ 13, and for 14 inputs it was known that 49 ≤ S(14) ≤ 51. We prove S(14) ≥ 50, so S(14) is 50 or 51; as a consequence, S(16) ≥ 59. The proof uses S(13) = 45 to restrict the paths of the largest and the smallest value in a sorting network on 14 inputs with 49 comparators. After a computation, these restrictions leave a few thousand possible prefixes of such a network, up to symmetry. A computer search shows that none of them can be completed to such a network. The search uses Harder's Huffman bound (arXiv:2012.04400) and the weighted two-value bound from our proof of S(13) = 45; several of our programs are modifications of Harder's code. A separately written program checks the certificates, and S(14) ≥ 50 is also derived in Lean 4 from bounds certified outside Lean; part of the derivation runs as compiled code.
In plain words
Some sorting methods compare pairs of numbers on a schedule fixed in advance, swapping each pair that is out of order. Each compare-and-swap is a comparator, and such methods are called sorting networks. Because the schedule never depends on the numbers, they suit parallel sorting. In 1962 Bose and Nelson asked how few comparators such a network needs. For 14 numbers the smallest network known has 51 comparators, and this paper proves with computer searches that at least 50 are needed, so the minimum is 50 or 51.
Formal statement and axioms
Each main result as stated in Lean, copied verbatim from the published package, with the axioms that the proof rests on. Lean v4.35.0-rc3, Mathlib c55e6e786f49. The package.
Sortnet.S14.S14_ge_50_N
S(14) ≥ 50: with compiled code
theorem Sortnet.S14.S14_ge_50_N :
Sortnet.S14.coreTableC.Valid →
(∀ i ∈ Sortnet.S14.Wed.done, (Sortnet.S14.Wed.TLf i).Valid) →
Sortnet.S14.S14StatementDefinitions used in the statement
def S14Statement : Prop := ∀ net : Network 14, net.Sorts → 50 ≤ net.lengthstructure Comparator (n : Nat) where
i : Fin n
j : Fin n
lt : i < j
deriving DecidableEqdef Comparator.apply {n : Nat} (c : Comparator n) (v : Fin n → Nat) : Fin n → Nat :=
fun k => if k = c.i then min (v c.i) (v c.j) else if k = c.j then max (v c.i) (v c.j) else v kabbrev Network (n : Nat) := List (Comparator n)def Network.eval {n : Nat} (net : Network n) (v : Fin n → Nat) : Fin n → Nat :=
net.foldl (fun w c => c.apply w) vdef Network.Sorts {n : Nat} (net : Network n) : Prop :=
∀ v : Fin n → Nat, ∀ a b : Fin n, a ≤ b → net.eval v a ≤ net.eval v bdef bitSet (n K : ℕ) : Set (Vec n) := {v | Nat.testBit K (code v) = true}structure Table where
cnt : ℕ
ent : ℕ → ℕ × ℕ × ℕdef Table.Valid (T : Table) : Prop :=
∀ i < T.cnt, ((T.ent i).1 = 10 ∨ (T.ent i).1 = 11) → LB (bitSet (T.ent i).1 (T.ent i).2.1) (T.ent i).2.2Source: Zenodo record 23632985, lean_s14_tools.tar.gz/lean_s14/assembly_n/S14AssemblyN.lean:37-40.
Axioms, as Lean reports them: propext, Classical.choice, Quot.sound and 43,100 more, for example Sortnet.certOK_harder11._native.native_decide.ax_1_1, Sortnet.S14.CSD.n_V2164_10._native.native_decide.ax_1_1 and Sortnet.S14.CSD.n_V2202_12._native.native_decide.ax_1_1. Each of these 43,100 axioms comes from a check that runs as compiled code (native_decide). The full report is recorded in zenodo:23632985/lean_s14_tools.tar.gz/lean_s14/assembly_n/assembly_out.txt:6-43108.