v_selection_16_8_le_28_iff_exists_tree
The worst-case comparison complexity of selecting the 8th smallest element among 16 elements is at most 28 (that is, V_8(16) ≤ 28) if and only if there exists a comparison decision tree on 16 elements of depth at most 28 that correctly selects rank 7.
Statement
theorem v_selection_16_8_le_28_iff_exists_tree :
v_selection 16 8 ≤ 28 ↔ ∃ T : ComparisonTree 16, comparison_tree_selects_rank T (7 : Fin 16) ∧ comparison_tree_depth T ≤ 28- Source
- arXiv:2610.18740 Sec. 2, Selecting the 7th Smallest of 16 Elements Takes Exactly 28 Comparisons
- Verified
- 08 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- v_selection_le_iffFor any positive rank i ≤ n and bound d, the worst-case comparison complexity V_i(n) is at most d if and only if there exists a comparison…
- v_selectionThe minimum number of pairwise comparisons V_i(n) needed in the worst case by a deterministic comparison algorithm (decision tree) to find…
- comparison_tree_selects_rankA comparison decision tree T on n elements (T : ComparisonTree n) correctly selects the element of rank r : Fin n if for every permutation…
- comparison_tree_depthThe depth of a comparison decision tree is the maximum number of comparisons along any branch from the root to a leaf.
- ComparisonTreeA binary comparison decision tree on n elements whose internal nodes perform pairwise comparisons and whose leaves return an element index.
Read back from the Lean
The declaration asserts an equivalence (if and only if):
The comparison selection complexity v_selection 16 8 is at most 28 if and only if there exists a comparison tree T on 16 elements such that T selects rank 7 (i.e., (7 : Fin 16), the 8th element under 0-indexing) and the depth of T is at most 28.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The theorem establishes that the comparison complexity V_8(16) is at most 28 if and only if there exists a depth-bounded comparison tree for selecting rank 7 among 16 elements. It applies the general characterization lemma `v_selection_le_iff` with parameters n = 16, i = 8, and d = 28. The validity conditions 0 < 8 and 8 ≤ 16 are discharged automatically by linear arithmetic.
V_8(16) ≤ 28 if and only if there exists a comparison decision tree on 16 elements of depth at most 28 that correctly selects rank 7.
This equivalence is an immediate specialization of `v_selection_le_iff` with n = 16, i = 8, and d = 28. The two side conditions required by the lemma, 0 < 8 and 8 ≤ 16, are verified by linear integer arithmetic via `omega`.
uses
v_selection_le_iffv_selection 16 8 ≤ 28 ↔ ∃ T : ComparisonTree 16, comparison_tree_selects_rank T (7 : Fin 16) ∧ comparison_tree_depth T ≤ 28 := v_selection_le_iff 16 8 28 (by omega) (by omega)
v_selection_le_iff- For any positive integers n, i, and bound d with 0 < i ≤ n, the selection complexity V_i(n) is at most d if and only if there is a comparison decision tree on n elements of depth at most d that correctly selects rank i - 1.
- Rank indexing in `ComparisonTree 16` is 0-based (`Fin 16`), so selecting rank 7 corresponds to finding the 8th smallest element ($8 - 1 = 7$), matching the 1-based index parameter $i = 8$ in `v_selection 16 8`.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- V_8(16) ≤ 28 if and only if there exists a correct comparison decision tree of depth ≤ 28 for rank 7 on 16 elements. -/theorem v_selection_16_8_le_28_iff_exists_tree : v_selection 16 8 ≤ 28 ↔ ∃ T : ComparisonTree 16, comparison_tree_selects_rank T (7 : Fin 16) ∧ comparison_tree_depth T ≤ 28 := v_selection_le_iff 16 8 28 (by omega) (by omega)