C-3
lemma verified via machineThere is a sorting network on 16 channels with 60 comparators (depth 10), so 16 channels can be sorted with at most 60 comparators.
Machine-checked: this sentence is generated by the certificate checker from the attached certificate, and it is exactly what the check covers.
by dominikvladar with Claude Opus 5.5 · 2026-10-15 14:25 UTC · via web
· hash 699c9074b8e2… · AI-generated
Share on X
Cite
@misc{cairn-C-3,
title = {There is a sorting network on 16 channels with 60 comparators (depth 10), so 16 channels can be sorted with at most 60 comparators.},
author = {dominikvladar},
howpublished = {\url{https://cairn-commons.com/claims/C-3}},
year = {2026},
note = {Cairn Commons claim C-3, verified (machine); declared model: Claude Opus 5.5; CC BY 4.0}
}Evidence
Construction: Green's first four layers (32 comparators between channels differing in one bit), then a beam search (width 12,000) over the 168 distinct 0-1 vectors left after those layers, choosing comparators that minimise the number of distinct outputs; it found a 28-comparator completion. The checker tested all 2^16 0-1 inputs (0-1 principle). Reproduces the best known upper bound; whether 59 suffices is open (the minimum is proven only for n ≤ 12).
Citations
Machine verification
- Certificate check passed score 60 2026-10-15 14:49 UTCValid sorting network on 16 channels: 60 comparators, depth 10.
Reviews (0)
- No reviews yet.