v_selection_three_two_upper_bound
The 2nd smallest (the median) of 3 distinct elements can be found using at most 3 pairwise comparisons, that is, V_2(3) ≤ 3.
Statement
theorem v_selection_three_two_upper_bound : v_selection 3 2 ≤ 3- Source
- step towards v_selection_16_8_upper_bound
- Verified
- 19 Oct 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_depthThe depth of a comparison decision tree is the maximum number of comparisons along any branch from the root to a leaf.
- 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_evalGiven an assignment v : Fin n → α of values in a linearly ordered type α, evaluate a comparison tree: on a leaf leaf ans, return the index…
- ComparisonTreeA binary comparison decision tree on n elements whose internal nodes perform pairwise comparisons and whose leaves return an element index.
The proof, explained
To show that the 2nd smallest of 3 distinct elements can be found in at most 3 comparisons (V_2(3) ≤ 3), the proof exhibits an explicit comparison tree T of depth at most 3. It computationally verifies that T outputs the median for every permutation of 3 inputs. Since the selection complexity V_2(3) is defined as the infimum of depths among all trees selecting the median, the existence of T establishes the upper bound of 3.
An explicit comparison tree T on 3 elements has depth at most 3.
A comparison tree T on elements {0, 1, 2} is defined: it first compares elements 0 and 1, and then branches to compare either {1, 2} or {0, 2} depending on the outcome, taking at most 3 comparisons along any path. Lean's `decide` tactic computes `comparison_tree_depth T` and checks that it is at most 3.
let T : ComparisonTree 3 := .branch 0 1 (.branch 1 2 (.leaf 1) (.branch 0 2 (.leaf 2) (.leaf 0))) (.branch 0 2 (.leaf 0) (.branch 1 2 (.leaf 2) (.leaf 1))) have hd : comparison_tree_depth T ≤ 3 := by decide
The tree T correctly selects the element of rank 1 (the median) under all permutations of 3 elements.
Unfolding `comparison_tree_selects_rank` gives the condition that for every permutation σ ∈ S₃, applying σ to the index returned by evaluating T on the ordering σ produces rank 1 (the 2nd smallest element, 0-indexed). Since S₃ has only 3! = 6 permutations, `decide` verifies this property by exhaustive evaluation.
have hT : comparison_tree_selects_rank T (⟨1, by norm_num⟩ : Fin 3) := by unfold comparison_tree_selects_rank decide
The problem reduces to showing that the infimum of depths of trees selecting rank 1 is at most 3.
Unfolding `v_selection 3 2` yields an `if`-statement conditioned on `0 < 2 ∧ 2 ≤ 3`. Because this condition is satisfied, `dif_pos` reduces the expression to `comparison_selection_complexity` for rank 2 - 1 = 1, which unfolds to the infimum of depths of all comparison trees on 3 elements that select rank 1.
uses
dif_posunfold v_selection rw [dif_pos (show 0 < 2 ∧ 2 ≤ 3 by norm_num)] unfold comparison_selection_complexity
The selection complexity of the median of 3 elements is at most 3 (V_2(3) ≤ 3).
The tree T and the proof hT of its correctness show that its depth belongs to the set of valid tree depths. By `Nat.sInf_le`, the infimum of this set is bounded above by `comparison_tree_depth T`. Transitivity of inequality (`le_trans`) with the depth bound `hd ≤ 3` completes the proof.
uses
le_trans,Nat.sInf_leexact le_trans (Nat.sInf_le ⟨T, hT, rfl⟩) hd
dif_pos- In a dependent if-then-else expression `if h : c then t else e`, if the condition `c` holds (`hc : c`), the expression reduces to `t hc`.
le_trans- The order relation ≤ is transitive: if `a ≤ b` and `b ≤ c`, then `a ≤ c`.
Nat.sInf_le- If an element `m` belongs to a set of natural numbers `s`, then the infimum (minimum) `sInf s` is at most `m`.
- The function `v_selection` uses 1-based indexing for ranks (here `i = 2`), but converts this internally to 0-based indexing (`Fin 3` with value `2 - 1 = 1`).
- The depth bound (`hd`) and permutation correctness (`hT`) are proved via Lean's `decide` tactic, which evaluates depth by finite arithmetic and verifies median selection by exhaustively checking all 3! = 6 permutations in S₃.
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.
/-- Median of three in three comparisons: a nontrivial positive witness that `v_selection` is attained, complementing the n = 1 leaf and the negative n = 2 example already in the graph. -/theorem v_selection_three_two_upper_bound : v_selection 3 2 ≤ 3 := by let T : ComparisonTree 3 := .branch 0 1 (.branch 1 2 (.leaf 1) (.branch 0 2 (.leaf 2) (.leaf 0))) (.branch 0 2 (.leaf 0) (.branch 1 2 (.leaf 2) (.leaf 1))) have hd : comparison_tree_depth T ≤ 3 := by decide have hT : comparison_tree_selects_rank T (⟨1, by norm_num⟩ : Fin 3) := by unfold comparison_tree_selects_rank decide unfold v_selection rw [dif_pos (show 0 < 2 ∧ 2 ≤ 3 by norm_num)] unfold comparison_selection_complexity exact le_trans (Nat.sInf_le ⟨T, hT, rfl⟩) hd