AFTD Auto-Formalizing Theoretical Domains

v_selection_poset

def

For a natural number n, a partial order P on Fin n, and a rank i, V_i(P) is the infimum of depths of all comparison decision trees on n elements that correctly select the i-th smallest element for P.

Statement

noncomputable def v_selection_poset (n : ℕ) (P : PartialOrder (Fin n)) (i : ℕ) : ℕ
Defined in
arXiv:2610.18740 Section 2, line 270
Verified
23 Oct 2026
Axioms
none listed
Built on 3
  • ComparisonTreeA binary comparison decision tree on n elements whose internal nodes perform pairwise comparisons and whose leaves return an element index.
  • comparison_tree_correct_for_selectionGiven a natural number n, a partial order P on Fin n, a rank i, and a comparison tree t on n elements, t correctly selects the i-th…
  • comparison_tree_depthThe depth of a comparison decision tree is the maximum number of comparisons along any branch from the root to a leaf.

Read back from the Lean

v_selection_poset n P i is defined as the infimum (sInf, in ℕ) of the set of depths d of comparison trees T on n elements that correctly select the i-th element (1-indexed) under every linear extension of the partial order P on Fin n. Specifically: - Given n : ℕ, a partial order P on Fin n, and i : ℕ, - It considers all comparison trees T : ComparisonTree n such that for every linear order L on Fin n extending P, evaluating T according to comparisons in L yields an element ans : Fin n such that exactly i - 1 elements in Fin n are strictly less than ans under L. - It returns the infimum (minimum when nonempty, 0 when empty) of the depths of all such trees T.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The minimum worst-case number of comparisons V_i(P) to select the i-th smallest element for poset P. -/
noncomputable def v_selection_poset (n : ℕ) (P : PartialOrder (Fin n)) (i : ℕ) : ℕ := open scoped Classical in
  sInf { d : ℕ | ∃ T : ComparisonTree n, comparison_tree_correct_for_selection n P i T ∧ comparison_tree_depth T = d }
See it in the graphDiscuss this resultChallenge it