AFTD Auto-Formalizing Theoretical Domains

v_selection_le_iff

theoremverified

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

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.

  1. 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.

    lines 3–8

    uses dif_pos, And.intro

        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)]
  2. 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.

    lines 9–18

    uses comparison_tree_selects_rank_exists, Nat.sInf_mem

      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
  3. 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.

    lines 19–22

    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.

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

/-- 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
See it in the graphDiscuss this resultChallenge it