poset_key_bound
def
For a partial order P on Fin n and rank i, KEY(P) is the supremum over all compatible solutions s = (L, e, U) of the crucial comparisons weight a_s + b_s.
Statement
noncomputable def poset_key_bound {n : ℕ} (P : PartialOrder (Fin n)) (i : ℕ) : ℕ
- Defined in
- arXiv:2610.18740 Section 5, line 622
- Verified
- 23 Oct 2026
- Axioms
- none listed
- Built on 2
- is_compatible_solutionA triple (L, e, U) is a compatible solution for a partial order P on Fin n and rank i if L, {e}, and U partition Fin n with |L| = i - 1,…
- crucial_weightGiven a partial order P on Fin n and a solution with lower set L and selected element e, the crucial comparisons weight is a_s + b_s,…
Read back from the Lean
For a natural number n, a partial order P on Fin n, and a natural number i, poset_key_bound P i is the supremum (in ℕ) of the set of natural numbers w for which there exist subsets L, U ⊆ Fin n and an element e ∈ Fin n such that (L, e, U) is a compatible solution for P and i, and w equals the crucial weight of (P, L, e).
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 KEY lower bound KEY(P) is the maximum crucial comparisons weight over all compatible solutions. -/ noncomputable def poset_key_bound {n : ℕ} (P : PartialOrder (Fin n)) (i : ℕ) : ℕ := open scoped Classical in sSup { w : ℕ | ∃ L e U, is_compatible_solution P i L e U ∧ w = crucial_weight P L e }