// s13
S(13)
Whether sorting 13 inputs needs 44 comparators or 45 is still open.
// in plain terms
Sorting networks are fixed circuits for sorting numbers, used in hardware. For 13 inputs, nobody knows whether the best circuit needs 44 comparisons or 45; the question has been open for fifty years. We attack it with machine search against frozen, independently verified baselines, and found along the way that the accepted lower bound was never validly proven.
// 01
Problem
S(4) = 5 — solved
run the network to sort
S(13) = ?
The number of comparisons the best 13-input sorting circuit needs is unknown. The record has sat at "between 44 and 45" since the 1970s. Closing it by brute force needs over 20,000 TB of RAM, which puts the direct computation out of reach.
// 02
Protocol
Everything runs under a SHA-pinned contract: an evolution hunt for a 44-comparator witness on one track, proof engineering to make the lower-bound computation feasible on the other. Every claim is replayed by two independent verifiers, one in Python and one in Go.
| instance | result | status |
|---|---|---|
| n = 9 | 25 comparators | reproduced — 0.8 s |
| n = 11 | 35 comparators | certificate replayed bit-identically |
| n = 13 | 44 or 45 | open |
// 03
Correction to the lower bound
the honest state: 43 ≤ S(13) ≤ 45
The folklore lower bound of 44 rests on a 1972 theorem whose published proof is invalid as written: its key step is refuted by an optimal 3-sorter. The proven state of the problem is 43 ≤ S(13) ≤ 45. Juillé's 1995 45-comparator network, unimproved in thirty years, is reproduced and twice verified in our ledger.
// 04
Tracks
- +Track A. Learned and evolutionary search for a 44-comparator witness; first gate: reach 45, then beat the matched-compute baseline of 2/60 seeds.
- +Track B. Scale the lower-bound computation through a measured cost model: n = 11 in the cloud for ~$15, then the 48 GB box, then a go/no-go on n = 13 driven strictly by the numbers.
- +A separate result, publishable on its own: repair the 1972 proof.
// the thread
Status
Nothing is settled: S(13) is as open as it was in 1972. What we have is a corrected scoreboard, frozen rules, and two tracks that could each close it. The n = 13 computation may be out of reach, and the cost model will determine whether it is attempted. Repairing the 1972 proof is a result either way.
// papers
this page is the TL;DR — the papers are the full story. drafts, provided as-is.