AFTD Auto-Formalizing Theoretical Domains

sum_rankings_of_nonempty

lemmaverified

For nonempty S, a sum over rankings of S splits as a sum over the top alternative a and the rankings of S minus a.

Statement

lemma sum_rankings_of_nonempty (S : Finset ℕ) (hS : S.Nonempty) (f : List ℕ → ℝ) :
    ∑ l ∈ rankings_of S, f l = ∑ a ∈ S, ∑ t ∈ rankings_of (S.erase a), f (a :: t)
Source
step towards plackett_luce_geometric_entropy_linear (Preference Elicitation as Average-Case Sorting, AAAI 2021, Sec. 5 conjecture (entropy O(m) for every phi in (0,1)))
Verified
06 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • rankings_ofThe rankings of a finite set S of alternatives: all orderings of S as duplicate-free lists.
  • rankings_of_eq_biUnionFor nonempty S, the rankings of S are obtained by choosing a top alternative a in S and then a ranking of S minus a.
Used by 2
  • sum_plackett_luce_probWith positive weights, the Plackett-Luce probabilities of the rankings of S sum to 1.
  • plackett_luce_entropy_eqChain rule: the Plackett-Luce entropy on S equals the entropy of the first choice plus the expected Plackett-Luce entropy of the remaining…

Lean source view module on GitHub

lemma sum_rankings_of_nonempty (S : Finset ℕ) (hS : S.Nonempty) (f : List ℕ → ℝ) :    ∑ l ∈ rankings_of S, f l = ∑ a ∈ S, ∑ t ∈ rankings_of (S.erase a), f (a :: t) := by  rw [rankings_of_eq_biUnion S hS, Finset.sum_biUnion]  · refine Finset.sum_congr rfl fun a _ => ?_    rw [Finset.sum_image]    intro x _ y _ h; exact List.cons_injective h  · intro a _ b _ hab    simp only [Function.onFun]    rw [Finset.disjoint_left]    intro l h1 h2    simp only [Finset.mem_image] at h1 h2    obtain ⟨t1, -, rfl⟩ := h1    obtain ⟨t2, -, h⟩ := h2    exact hab (List.cons.inj h).1.symm
See it in the graphDiscuss this resultChallenge it