AFTD Auto-Formalizing Theoretical Domains

v_selection_16_8_le_28_iff_exists_tree

theoremverified

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.

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

    line 3

    uses v_selection_le_iff

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

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

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