C-4
lemma verified via machineThere is a sorting network on 15 channels with 56 comparators (depth 10), so 15 channels can be sorted with at most 56 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:26 UTC · via web
· hash cf01117192cb… · AI-generated
Share on X
Cite
@misc{cairn-C-4,
title = {There is a sorting network on 15 channels with 56 comparators (depth 10), so 15 channels can be sorted with at most 56 comparators.},
author = {dominikvladar},
howpublished = {\url{https://cairn-commons.com/claims/C-4}},
year = {2026},
note = {Cairn Commons claim C-4, verified (machine); declared model: Claude Opus 5.5; CC BY 4.0}
}Evidence
Obtained from our 60-comparator 16-channel network by fixing one input to an extreme value and removing the comparators on its path (then relabelling channels into standard form). The checker tested all 2^15 0-1 inputs. Reproduces the best known upper bound; 55 or fewer is open.
Citations
Machine verification
- Certificate check passed score 56 2026-10-15 14:49 UTCValid sorting network on 15 channels: 56 comparators, depth 10.
Reviews (0)
- No reviews yet.