v_selection_le_iff
For 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 decision tree on n elements of depth at most d that correctly selects the element of 0-based rank i - 1.
Statement
theorem v_selection_le_iff (n : ℕ) (i : ℕ) (d : ℕ) (h1 : 0 < i) (h2 : i ≤ n) : v_selection n i ≤ d ↔ ∃ T : ComparisonTree n, comparison_tree_selects_rank T ⟨i - 1, by omega⟩ ∧ comparison_tree_depth T ≤ d
- 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 6
- 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_selection_complexityThe worst-case comparison complexity to select the element of rank r : Fin n among n elements, defined as the infimum of the depths of all…
- comparison_tree_selects_rank_existsFor every n and every rank r : Fin n there exists a comparison decision tree on n elements that correctly selects the element of rank r.
- 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.
- Used by 1
- v_selection_16_8_le_28_iff_exists_treeThe 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…
Read back from the Lean
For all natural numbers $n$, $i$, and $d$, assuming $0 < i$ and $i \le n$, the comparison complexity of selecting the $i$-th element among $n$ elements, v_selection n i, is at most $d$ if and only if there exists a comparison tree $T$ on $n$ elements that selects the element of rank $i - 1$ (as an element of Fin n) and has depth at most $d$.
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 worst-case comparison complexity V_i(n) is defined as the infimum of depths of comparison trees that correctly select the element of rank i - 1. The theorem reduces to the fundamental property of the infimum in the natural numbers: the infimum of a set is at most d if and only if the set contains an element at most d. In the forward direction, because a correct selection tree always exists, the set of depths is nonempty, and by well-ordering its infimum is attained by an optimal tree. In the backward direction, any tree of depth at most d provides a member of the set, which immediately bounds the infimum from above.
The inequality V_i(n) ≤ d reduces to the assertion that the infimum of depths of comparison trees correctly selecting rank i - 1 is at most d.
From the assumptions 0 < i and i ≤ n, linear arithmetic implies i - 1 < n, which justifies viewing i - 1 as a valid index in Fin n. We rewrite the index to use this explicit bound. Unfolding the definitions of v_selection and comparison_selection_complexity, the rank validity condition 0 < i ∧ i ≤ n holds by hypothesis, so the conditional expression simplifies via dif_pos and And.intro to its positive branch: the infimum of the depths of all trees correctly selecting rank i - 1.
uses
dif_pos,And.introv_selection n i ≤ d ↔ ∃ T : ComparisonTree n, comparison_tree_selects_rank T ⟨i - 1, by omega⟩ ∧ comparison_tree_depth T ≤ d := by have h_lt : i - 1 < n := by omega have hr : (⟨i - 1, by omega⟩ : Fin n) = ⟨i - 1, h_lt⟩ := rfl rw [hr] unfold v_selection comparison_selection_complexity simp only [dif_pos (And.intro h1 h2)]
Forward direction: if the infimum of tree depths is at most d, there exists a correct comparison tree of depth at most d.
We split the bi-implication using constructor. Assuming the infimum of the set of depths S is at most d, we first show S is nonempty: comparison_tree_selects_rank_exists yields a correct selection tree, whose depth therefore belongs to S. Since S is a nonempty set of natural numbers, Nat.sInf_mem ensures that the infimum sInf S is an element of S. This provides a comparison tree T selecting rank i - 1 with depth equal to sInf S. Since sInf S ≤ d by assumption, T has depth at most d.
uses
comparison_tree_selects_rank_exists,Nat.sInf_memconstructor · intro h have h_nonempty : Set.Nonempty {d' | ∃ T, comparison_tree_selects_rank T ⟨i - 1, h_lt⟩ ∧ comparison_tree_depth T = d'} := by obtain ⟨T, hT⟩ := comparison_tree_selects_rank_exists ⟨i - 1, h_lt⟩ exact ⟨comparison_tree_depth T, T, hT, rfl⟩ have h_mem := Nat.sInf_mem h_nonempty rcases h_mem with ⟨T, hT1, hT2⟩ refine ⟨T, hT1, ?_⟩ rw [hT2] exact h
Backward direction: if there exists a correct comparison tree of depth at most d, then the infimum of tree depths is at most d.
Given a comparison tree T that correctly selects rank i - 1 and satisfies depth(T) ≤ d, its depth belongs to the set of depths S. By Nat.sInf_le, the infimum sInf S is at most depth(T). By transitivity of inequality (le_trans) with depth(T) ≤ d, we conclude sInf S ≤ d.
uses
Nat.sInf_le,le_trans· rintro ⟨T, hT1, hT2⟩ have h_mem : comparison_tree_depth T ∈ {d' | ∃ T', comparison_tree_selects_rank T' ⟨i - 1, h_lt⟩ ∧ comparison_tree_depth T' = d'} := ⟨T, hT1, rfl⟩ exact le_trans (Nat.sInf_le h_mem) hT2
dif_pos- A dependent if-then-else expression evaluates to its 'then' branch when the condition is true.
And.intro- From proofs of propositions a and b, constructs a proof of their conjunction a ∧ b.
comparison_tree_selects_rank_exists- For any rank r in {0, …, n - 1}, there exists at least one comparison tree correctly selecting rank r.
Nat.sInf_mem- Every nonempty set of natural numbers contains its own infimum.
Nat.sInf_le- The infimum of a set of natural numbers is less than or equal to any element belonging to the set.
le_trans- Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.
- Lines 4–6 are a formalization detail: the theorem statement uses an anonymous `by omega` to construct the `Fin n` index, so the proof proves `h_lt : i - 1 < n` explicitly and rewrites with `rfl` to provide a named hypothesis for syntactic unification in subsequent steps.
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.
/-- Worst-case comparison complexity V_i(n) ≤ d if and only if there exists a correct decision tree of depth ≤ d. -/theorem v_selection_le_iff (n : ℕ) (i : ℕ) (d : ℕ) (h1 : 0 < i) (h2 : i ≤ n) : v_selection n i ≤ d ↔ ∃ T : ComparisonTree n, comparison_tree_selects_rank T ⟨i - 1, by omega⟩ ∧ comparison_tree_depth T ≤ d := by have h_lt : i - 1 < n := by omega have hr : (⟨i - 1, by omega⟩ : Fin n) = ⟨i - 1, h_lt⟩ := rfl rw [hr] unfold v_selection comparison_selection_complexity simp only [dif_pos (And.intro h1 h2)] constructor · intro h have h_nonempty : Set.Nonempty {d' | ∃ T, comparison_tree_selects_rank T ⟨i - 1, h_lt⟩ ∧ comparison_tree_depth T = d'} := by obtain ⟨T, hT⟩ := comparison_tree_selects_rank_exists ⟨i - 1, h_lt⟩ exact ⟨comparison_tree_depth T, T, hT, rfl⟩ have h_mem := Nat.sInf_mem h_nonempty rcases h_mem with ⟨T, hT1, hT2⟩ refine ⟨T, hT1, ?_⟩ rw [hT2] exact h · rintro ⟨T, hT1, hT2⟩ have h_mem : comparison_tree_depth T ∈ {d' | ∃ T', comparison_tree_selects_rank T' ⟨i - 1, h_lt⟩ ∧ comparison_tree_depth T' = d'} := ⟨T, hT1, rfl⟩ exact le_trans (Nat.sInf_le h_mem) hT2