Exact sizes of small single-output median networks

Result

Let M(n) denote the minimum number of comparators in an n-channel comparator network that places the median of any input vector on a single designated output channel, with the choice of output channel unconstrained. For even n, let M_lower(n) denote the minimum size required to isolate the lower median (the n/2-th smallest element).

The exact sizes are:

• M(7) = 13. The lower bound M(7) >= 13 is certified via an unsatisfiability proof at size 12.
• M_lower(6) = 10. The lower bound M_lower(6) >= 10 is certified via an unsatisfiability proof at size 9.
• M(3) = 3 and M(5) = 7 are re-certified.
• For n = 10, the single-output median size satisfies M(10) <= 23.

Setting and definitions

A comparator network on n channels consists of a sequence of comparators [i, j] with 0 <= i < j < n. Under the standard 0-1 sorting principle, correctness on all real inputs is equivalent to correctness on the domain {0, 1}^n of 2^n Boolean input vectors.

A network computes the single-output median if there exists an output channel c such that for every x in {0, 1}^n, channel c evaluates to 1 if and only if the Hamming weight wt(x) >= ceil((n + 1) / 2) for odd n, or wt(x) >= n / 2 + 1 for the strict upper median (respectively wt(x) >= n / 2 for the lower median when n is even).

Candidate networks are constrained to normal form:

• Lexicographic minimality under channel relabelling.
• Knuth untangling and commutation symmetries.
• Minimality conditions: every channel is active in at least one comparator, and cone constraints enforce functional dependency on the relevant inputs.
• Size padding: repeating the last comparator allows the search for networks of size at most s to be formulated as a search for networks of size exactly s.

Method

Non-existence of networks below minimal sizes was established through propositional satisfiability (SAT) encodings enforcing the normal form, channel reachability, and correctness over all 2^n Boolean inputs:

1. Lower bounds:

• For n = 7 at size 12, the SAT instance was proven UNSAT. The proof of unsatisfiability was validated by two independent drat-trim passes.
• For n = 6 (lower median) at size 9, the SAT instance was proven UNSAT and verified by drat-trim.

1. Upper bounds and candidate replay:

• For n = 7, witness MED-01 of size 13 was synthesized and replayed across all 128 Boolean inputs in {0, 1}^7, verifying median output on the designated channel.
• For n = 6, witness MED-03 of size 10 was synthesized and replayed across all Boolean inputs in {0, 1}^6.
• Structural soundness of the normal-form reduction for optimal networks was derived independently.

All synthesis logs, candidate witnesses, and verification runs are preserved in lanes/median-11/BANK-CANDIDATES.md, VERIFY.md, and box frontier/median/.

Discussion

Dobbelaere listed size 13 for n = 7 without proof, marking only n = 9 as proven optimal (attributed to Smith 1996). Whether the selection-network tables in Knuth TAOCP 5.3.4 record these exact sizes is unverified in the register.

A definitional discrepancy in prior tables was resolved: Dobbelaere's 22-comparator entry for n = 10 represents a two-output network where channels 4 and 5 jointly contain the 5th and 6th smallest elements as an unordered set. Neither channel carries a single median value on its own. Replay verification confirms that the single-output 10-channel median network requires additional comparators, establishing the upper bound M(10) <= 23.

Attribution and prior art

Prior art: Dobbelaere’s table lists 13 for n = 7 (unproven) and marks n = 9 as optimal (Smith 1996); Knuth TAOCP 5.3.4 remains unverified. Furthermore, a replay check confirmed Dobbelaere’s 22-comparator n = 10 network is a two-output design, correcting the single-output bound for n = 10 to 23 comparators rather than 22. Sources: Dobbelaere, median networks table

Register references

• Register entry: MF-189
• Receipt artifacts: lanes/median-11/BANK-CANDIDATES.md (witnesses MED-01, MED-03), VERIFY.md, box frontier/median/
• Prior art references: Dobbelaere median network tables; Smith (1996); Knuth TAOCP Section 5.3.4 (unverified status)

Every artifact named above is bundled in, or hashed by, this paper's evidence pack below.

Evidence pack

Everything needed to check this entry against its receipts: the register text, a manifest with a SHA-256 hash for every named receipt, and 2 of 2 receipt files bundled (16 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.

Download evidence.zip

Related in this programme

• MF-190
  Exact B2 circuit size and machine-checkable certificate for 5-input MOD3,1
• MF-184
  Non-existence of 18-vector Kochen-Specker sets in dimension 6
• MF-195
  Nonexistence of 19-vector Kochen-Specker sets in C^6 and the lower bound m_6 ≥ 20
• MF-199
  Nonexistence of 20-vector Kochen-Specker sets in C^6 and minimality of m_6 = 21