comparison_tree_selects_rank_exists
For 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.
Statement
theorem comparison_tree_selects_rank_exists {n : ℕ} (r : Fin n) : ∃ T : ComparisonTree n, comparison_tree_selects_rank T r- Source
- step towards v_selection_16_8_lower_bound
- Verified
- 19 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - ComparisonTreeA binary comparison decision tree on n elements whose internal nodes perform pairwise comparisons and whose leaves return an element index.
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- Used by 1
- 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…
The proof, explained
We construct an oblivious comparison decision tree that performs every pairwise comparison between elements of Fin n in sequence, recording the boolean outcomes in an accumulated matrix. At each leaf, a selection rule counts how many elements are smaller than each element according to the observed comparison table and outputs the unique element preceded by exactly r.val elements. When evaluated on any permutation σ, the accumulated table is the complete comparison matrix of σ, and the rank of σ⁻¹(r) under σ is precisely r, ensuring the tree correctly outputs the element of rank r.
Every pair of elements p = (i, j) belongs to the list of all pairs.
Decomposing p into (i, j), both coordinates belong to List.finRange n. Since comparison_tree_selects_rank_exists_all_pairs_list is defined as the Cartesian product of List.finRange n with itself, the pair belongs to the list.
uses
comparison_tree_selects_rank_exists_all_pairs_listrcases p with ⟨i, j⟩ simp [comparison_tree_selects_rank_exists_all_pairs_list]
Evaluating the decision tree constructed from query list L and accumulated matrix M on an input vector v equals applying the choice function to the matrix folded over L.
By induction on L. When L is empty, the tree is a leaf returning choose M, matching the base foldl. For a list (i, j) :: tail, the tree branches on whether v i < v j; in each branch, entry (i, j) is set to the observed boolean outcome and the induction hypothesis equates subtree evaluation to the fold over the tail.
uses
comparison_tree_selects_rank_exists_build,comparison_tree_evalinduction L generalizing M with | nil => simp [comparison_tree_selects_rank_exists_build, comparison_tree_eval] | cons head tail ih => rcases head with ⟨i, j⟩ simp [comparison_tree_selects_rank_exists_build, comparison_tree_eval] split_ifs with h · rw [ih] have : decide (v i < v j) = true := by simp [h] rw [this] · rw [ih] have : decide (v i < v j) = false := by simp [h] rw [this]
Folding comparison updates over list L produces a matrix whose entry at (i, j) is decide (v i < v j) if (i, j) ∈ L, and M i j otherwise.
By induction on L. In the empty list case, (i, j) ∉ [] and the matrix is unchanged. For a step with head (x, y) and tail, the induction hypothesis applies to the tail: if (i, j) ∈ tail, the entry is already decide (v i < v j). If (i, j) ∉ tail, the entry comes from the update at (x, y), giving decide (v i < v j) when (i, j) = (x, y) and M i j otherwise.
uses
List.foldl_cons,List.mem_cons,comparison_tree_selects_rank_exists_update_matrixinduction L generalizing M with | nil => simp | cons head tail ih => rcases head with ⟨x, y⟩ simp only [List.foldl_cons, ih, List.mem_cons] by_cases h : (i, j) ∈ tail · simp [h] · simp [h] dsimp [comparison_tree_selects_rank_exists_update_matrix] split_ifs with h2 · rcases h2 with ⟨rfl, rfl⟩ simp · simp
When L contains every pair of indices, folding comparison updates over L yields the complete comparison matrix (i, j) ↦ decide (v i < v j).
By function extensionality on (i, j), the folded matrix entry rewrites via comparison_tree_selects_rank_exists_foldl_update_matrix to a conditional check on (i, j) ∈ L. Since every pair belongs to L by assumption, the entry simplifies to decide (v i < v j).
uses
comparison_tree_selects_rank_exists_foldl_update_matrixext i j rw [comparison_tree_selects_rank_exists_foldl_update_matrix] simp [hL (i, j)]
For any permutation σ of Fin n and element a, the number of elements with smaller image under σ is (σ a).val.
The set of elements b with σ b < σ a is the image under the embedding σ⁻¹ of the initial interval Finset.Iio (σ a). Embeddings preserve cardinality (Finset.card_map) and the interval of elements strictly below σ a has cardinality (σ a).val (Fin.card_Iio).
uses
Finset.card_map,Fin.card_Iiohave h1 : Finset.filter (fun b => σ b < σ a) Finset.univ = (Finset.Iio (σ a)).map σ.symm.toEmbedding := by ext x simp rw [h1, Finset.card_map, Fin.card_Iio]
Counting elements smaller than a in the boolean comparison matrix of σ equals (σ a).val.
By definition, comparison_tree_selects_rank_exists_count_smaller counts elements b where decide (σ b < σ a) = true. This is equivalent to σ b < σ a, so the count equals the cardinality of the filtered set from comparison_tree_selects_rank_exists_card_filter_perm_lt, which is (σ a).val.
uses
comparison_tree_selects_rank_exists_count_smaller,comparison_tree_selects_rank_exists_card_filter_perm_ltdsimp [comparison_tree_selects_rank_exists_count_smaller] have h : (Finset.filter (fun b => decide (σ b < σ a) = true) Finset.univ) = (Finset.filter (fun b => σ b < σ a) Finset.univ) := by ext b simp rw [h] exact comparison_tree_selects_rank_exists_card_filter_perm_lt σ a
Applying σ to the element selected by choose_rank r on σ's comparison matrix produces r.
The selection function choose_rank r checks for an element with count r.val. The element a = σ⁻¹(r) is a valid witness since its count is (σ(σ⁻¹(r))).val = r.val. Given this witness, Classical.choose selects an element with count r.val, and by injectivity of Fin.val (Fin.ext), σ applied to that chosen element equals r.
uses
comparison_tree_selects_rank_exists_choose_rank,comparison_tree_selects_rank_exists_count_smaller_perm,dif_pos,Classical.choose_spec,Fin.extdsimp [comparison_tree_selects_rank_exists_choose_rank] have h : ∃ a : Fin n, comparison_tree_selects_rank_exists_count_smaller (fun b a => decide (σ b < σ a)) a = r.val := by use σ.symm r rw [comparison_tree_selects_rank_exists_count_smaller_perm] simp rw [dif_pos h] have ha : comparison_tree_selects_rank_exists_count_smaller (fun b a => decide (σ b < σ a)) (Classical.choose h) = r.val := Classical.choose_spec h rw [comparison_tree_selects_rank_exists_count_smaller_perm] at ha exact Fin.ext ha
We construct the candidate decision tree T that queries all pairs and fix an arbitrary permutation σ of Fin n.
We instantiate the leaf selector with comparison_tree_selects_rank_exists_choose_rank r and build tree T by querying all pairs in comparison_tree_selects_rank_exists_all_pairs_list n starting from an initial all-false matrix. We then fix an arbitrary permutation σ.
let choose := comparison_tree_selects_rank_exists_choose_rank r let T := comparison_tree_selects_rank_exists_build choose (comparison_tree_selects_rank_exists_all_pairs_list n) (fun _ _ => false) use T intro σ dsimp [T, choose]
Evaluating T on σ correctly selects the element of rank r.
Evaluating T on σ rewrites via comparison_tree_selects_rank_exists_build_eval to running the leaf selector on the matrix folded over all pairs. Because every pair is in the list, this fold yields the complete comparison matrix of σ (comparison_tree_selects_rank_exists_foldl_update_matrix_all). Finally, comparison_tree_selects_rank_exists_choose_rank_spec guarantees that σ of the selected element equals r.
uses
comparison_tree_selects_rank_exists_build_eval,comparison_tree_selects_rank_exists_foldl_update_matrix_all,comparison_tree_selects_rank_exists_mem_all_pairs_list,comparison_tree_selects_rank_exists_choose_rank_specrw [comparison_tree_selects_rank_exists_build_eval] rw [comparison_tree_selects_rank_exists_foldl_update_matrix_all (⇑σ) (comparison_tree_selects_rank_exists_all_pairs_list n) comparison_tree_selects_rank_exists_mem_all_pairs_list] exact comparison_tree_selects_rank_exists_choose_rank_spec r σ
Classical.choose_spec- The witness produced by Classical.choose satisfies the existential predicate.
Fin.card_Iio- The number of elements in Fin n strictly less than b is equal to the numerical value of b.
Fin.ext- Two elements of Fin n are equal if and only if their underlying natural number values are equal.
Finset.card_map- The cardinality of a finite set is preserved under mapping by an embedding.
List.foldl_cons- Folding a function over a cons list equals folding over the tail starting from the function applied to the initial accumulator and the head element.
List.mem_cons- An element belongs to a non-empty list if and only if it equals the head or belongs to the tail.
comparison_tree_eval- Evaluates a comparison decision tree on an input vector v by following the branches dictated by the comparisons until reaching a leaf.
comparison_tree_selects_rank_exists_all_pairs_list- The list of all pairs in Fin n × Fin n, defined as the Cartesian product of List.finRange n with itself.
comparison_tree_selects_rank_exists_build- Recursively builds a comparison decision tree that queries each pair in a list in order, updating an accumulated boolean matrix at each branch until reaching leaves.
comparison_tree_selects_rank_exists_build_eval- Evaluating the tree built from a query list on an input vector v applies the choice function to the matrix accumulated by folding comparison updates over the list.
comparison_tree_selects_rank_exists_card_filter_perm_lt- For any permutation σ of Fin n and element a, exactly (σ a).val elements have a strictly smaller image under σ.
comparison_tree_selects_rank_exists_choose_rank- Selects an element whose count of smaller elements in matrix M is r.val if one exists, defaulting to r otherwise.
comparison_tree_selects_rank_exists_choose_rank_spec- Applying the permutation σ to the element chosen by choose_rank from the comparison matrix of σ yields the target rank r.
comparison_tree_selects_rank_exists_count_smaller- The number of elements b in Fin n for which M b a is true in a boolean comparison matrix M.
comparison_tree_selects_rank_exists_count_smaller_perm- Counting the elements smaller than a in the boolean comparison matrix of a permutation σ returns (σ a).val.
comparison_tree_selects_rank_exists_foldl_update_matrix- Folding comparison updates over a list L yields a matrix whose entry at (i, j) is decide (v i < v j) if (i, j) ∈ L, and M i j otherwise.
comparison_tree_selects_rank_exists_foldl_update_matrix_all- When L contains every pair of indices, folding comparison updates over L yields the complete comparison matrix (i, j) ↦ decide (v i < v j).
comparison_tree_selects_rank_exists_mem_all_pairs_list- Every pair of indices in Fin n × Fin n is an element of the list of all pairs.
comparison_tree_selects_rank_exists_update_matrix- Updates a boolean matrix by setting the entry at (i, j) to a given boolean while leaving all other entries unchanged.
dif_pos- A dependent if-then-else expression evaluates to its 'then' branch when the condition is proven.
- The proof constructs an oblivious decision tree that systematically queries all n² pairs (including self-comparisons and redundant pairs) to build the complete comparison matrix before selecting the rank; it is designed to establish existence straightforwardly rather than optimize tree depth.
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.
def comparison_tree_selects_rank_exists_all_pairs_list (n : ℕ) : List (Fin n × Fin n) := (List.finRange n).product (List.finRange n)lemma comparison_tree_selects_rank_exists_mem_all_pairs_list {n : ℕ} (p : Fin n × Fin n) : p ∈ comparison_tree_selects_rank_exists_all_pairs_list n := by rcases p with ⟨i, j⟩ simp [comparison_tree_selects_rank_exists_all_pairs_list]def comparison_tree_selects_rank_exists_update_matrix {n : ℕ} (M : Fin n → Fin n → Bool) (i j : Fin n) (b : Bool) : Fin n → Fin n → Bool := fun x y => if x = i ∧ y = j then b else M x ydef comparison_tree_selects_rank_exists_build {n : ℕ} (choose : (Fin n → Fin n → Bool) → Fin n) : List (Fin n × Fin n) → (Fin n → Fin n → Bool) → ComparisonTree n | [], M => ComparisonTree.leaf (choose M) | (i, j) :: rest, M => ComparisonTree.branch i j (comparison_tree_selects_rank_exists_build choose rest (comparison_tree_selects_rank_exists_update_matrix M i j true)) (comparison_tree_selects_rank_exists_build choose rest (comparison_tree_selects_rank_exists_update_matrix M i j false))theorem comparison_tree_selects_rank_exists_build_eval {n : ℕ} {α : Type*} [LinearOrder α] (v : Fin n → α) (choose : (Fin n → Fin n → Bool) → Fin n) (L : List (Fin n × Fin n)) (M : Fin n → Fin n → Bool) : comparison_tree_eval v (comparison_tree_selects_rank_exists_build choose L M) = choose (L.foldl (fun m p => comparison_tree_selects_rank_exists_update_matrix m p.1 p.2 (decide (v p.1 < v p.2))) M) := by induction L generalizing M with | nil => simp [comparison_tree_selects_rank_exists_build, comparison_tree_eval] | cons head tail ih => rcases head with ⟨i, j⟩ simp [comparison_tree_selects_rank_exists_build, comparison_tree_eval] split_ifs with h · rw [ih] have : decide (v i < v j) = true := by simp [h] rw [this] · rw [ih] have : decide (v i < v j) = false := by simp [h] rw [this]lemma comparison_tree_selects_rank_exists_foldl_update_matrix {n : ℕ} {α : Type*} [LinearOrder α] (v : Fin n → α) (L : List (Fin n × Fin n)) (M : Fin n → Fin n → Bool) (i j : Fin n) : (L.foldl (fun m p => comparison_tree_selects_rank_exists_update_matrix m p.1 p.2 (decide (v p.1 < v p.2))) M) i j = if (i, j) ∈ L then decide (v i < v j) else M i j := by induction L generalizing M with | nil => simp | cons head tail ih => rcases head with ⟨x, y⟩ simp only [List.foldl_cons, ih, List.mem_cons] by_cases h : (i, j) ∈ tail · simp [h] · simp [h] dsimp [comparison_tree_selects_rank_exists_update_matrix] split_ifs with h2 · rcases h2 with ⟨rfl, rfl⟩ simp · simplemma comparison_tree_selects_rank_exists_foldl_update_matrix_all {n : ℕ} {α : Type*} [LinearOrder α] (v : Fin n → α) (L : List (Fin n × Fin n)) (hL : ∀ p, p ∈ L) (M : Fin n → Fin n → Bool) : (L.foldl (fun m p => comparison_tree_selects_rank_exists_update_matrix m p.1 p.2 (decide (v p.1 < v p.2))) M) = fun i j => decide (v i < v j) := by ext i j rw [comparison_tree_selects_rank_exists_foldl_update_matrix] simp [hL (i, j)]def comparison_tree_selects_rank_exists_count_smaller {n : ℕ} (M : Fin n → Fin n → Bool) (a : Fin n) : ℕ := (Finset.filter (fun b => M b a = true) Finset.univ).cardlemma comparison_tree_selects_rank_exists_card_filter_perm_lt {n : ℕ} (σ : Equiv.Perm (Fin n)) (a : Fin n) : (Finset.filter (fun b => σ b < σ a) Finset.univ).card = (σ a).val := by have h1 : Finset.filter (fun b => σ b < σ a) Finset.univ = (Finset.Iio (σ a)).map σ.symm.toEmbedding := by ext x simp rw [h1, Finset.card_map, Fin.card_Iio]lemma comparison_tree_selects_rank_exists_count_smaller_perm {n : ℕ} (σ : Equiv.Perm (Fin n)) (a : Fin n) : comparison_tree_selects_rank_exists_count_smaller (fun b a => decide (σ b < σ a)) a = (σ a).val := by dsimp [comparison_tree_selects_rank_exists_count_smaller] have h : (Finset.filter (fun b => decide (σ b < σ a) = true) Finset.univ) = (Finset.filter (fun b => σ b < σ a) Finset.univ) := by ext b simp rw [h] exact comparison_tree_selects_rank_exists_card_filter_perm_lt σ anoncomputable def comparison_tree_selects_rank_exists_choose_rank {n : ℕ} (r : Fin n) (M : Fin n → Fin n → Bool) : Fin n := if h : ∃ a : Fin n, comparison_tree_selects_rank_exists_count_smaller M a = r.val then Classical.choose h else rlemma comparison_tree_selects_rank_exists_choose_rank_spec {n : ℕ} (r : Fin n) (σ : Equiv.Perm (Fin n)) : σ (comparison_tree_selects_rank_exists_choose_rank r (fun b a => decide (σ b < σ a))) = r := by dsimp [comparison_tree_selects_rank_exists_choose_rank] have h : ∃ a : Fin n, comparison_tree_selects_rank_exists_count_smaller (fun b a => decide (σ b < σ a)) a = r.val := by use σ.symm r rw [comparison_tree_selects_rank_exists_count_smaller_perm] simp rw [dif_pos h] have ha : comparison_tree_selects_rank_exists_count_smaller (fun b a => decide (σ b < σ a)) (Classical.choose h) = r.val := Classical.choose_spec h rw [comparison_tree_selects_rank_exists_count_smaller_perm] at ha exact Fin.ext ha/-- Every rank-selection problem is solvable by some comparison decision tree, so the set of depths used in `comparison_selection_complexity` is nonempty. -/theorem comparison_tree_selects_rank_exists {n : ℕ} (r : Fin n) : ∃ T : ComparisonTree n, comparison_tree_selects_rank T r := by let choose := comparison_tree_selects_rank_exists_choose_rank r let T := comparison_tree_selects_rank_exists_build choose (comparison_tree_selects_rank_exists_all_pairs_list n) (fun _ _ => false) use T intro σ dsimp [T, choose] rw [comparison_tree_selects_rank_exists_build_eval] rw [comparison_tree_selects_rank_exists_foldl_update_matrix_all (⇑σ) (comparison_tree_selects_rank_exists_all_pairs_list n) comparison_tree_selects_rank_exists_mem_all_pairs_list] exact comparison_tree_selects_rank_exists_choose_rank_spec r σ