Selecting the 7th Smallest of 16 Elements Takes Exactly 28 Comparisons
Abstract
Let Vi(n) denote the minimum worst-case number of comparisons needed to find the i-th smallest of n distinct elements. We construct algorithms showing V7(16)≤28 and V8(16)≤29, improving the previously reported upper bounds of 30 and 31. Together with known lower bounds, these results establish V7(16)=28 and leave V8(16)∈{28,29}. For 17 elements, we establish V5(17)=27 and improve the upper bounds for ranks 6 through 9 to 29, 30, 31, and 31, respectively. Every new upper bound has an explicit decision-graph certificate verified by a static checker developed independently of the search. We also derive a lower bound for selection from a partially ordered state by combining the Fussenegger-Gabow weight with its order-reversed counterpart. All new upper bounds and this lower bound are formally verified in Lean 4. For V8(16), we show that a lower bound based solely on the total number of decision-tree leaves cannot establish V8(16)≥29. The algorithms were found using fixed-budget search, information-guided comparison ordering, and proof-number search. Proof-number search was decisive in finding the 28-comparison algorithm; in our experiments, refuting a comparison budget remained substantially more expensive than finding an algorithm within it.
Related
- Selecting the Best Few with Human Evaluators: Adaptively Combining Ratings and Pairwise Comparisons
- Structure-preserving operator splitting for 2.5D ideal MHD with an entropy-stable DGSEM and exactly divergence-free compatible finite elements
- Certified Alpha Capacity: Statistical Arbitrage When Learning Takes Time
- There may be many ways to be an herbivorous fish, but it usually takes a lot of guts.
- The Winner Takes It All
BibTeX
@misc{cremer2026selecting,
title = {{Selecting the 7th Smallest of 16 Elements Takes Exactly 28 Comparisons}},
author = {Jonathan Cremer},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.18740},
eprint = {2610.18740},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.18740},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Selecting the 7th Smallest of 16 Elements Takes Exactly 28 Comparisons
AU - Jonathan Cremer
PY - 2026
DA - 2026/10/13
PB - arXiv
DO - 10.48550/arxiv.2610.18740
UR - https://arxiv.org/abs/2610.18740
AB - Let V_i(n) denote the minimum worst-case number of comparisons needed to find the i-th smallest of n distinct elements. We construct algorithms showing V_7(16)≤28 and V_8(16)≤29, improving the previously reported upper bounds of 30 and 31. Together with known lower bounds, these results establish V_7(16)=28 and leave V_8(16)∈{28,29}. For 17 elements, we establish V_5(17)=27 and improve the upper bounds for ranks 6 through 9 to 29, 30, 31, and 31, respectively. Every new upper bound has an explicit decision-graph certificate verified by a static checker developed independently of the search. We also derive a lower bound for selection from a partially ordered state by combining the Fussenegger-Gabow weight with its order-reversed counterpart. All new upper bounds and this lower bound are formally verified in Lean 4. For V_8(16), we show that a lower bound based solely on the total number of decision-tree leaves cannot establish V_8(16)≥29. The algorithms were found using fixed-budget search, information-guided comparison ordering, and proof-number search. Proof-number search was decisive in finding the 28-comparison algorithm; in our experiments, refuting a comparison budget remained substantially more expensive than finding an algorithm within it.
ER -