AFTD Auto-Formalizing Theoretical Domains

plackett_luce_geometric_entropy_linear

theoremverifiedoriginal

Conjecture of Preference Elicitation as Average-Case Sorting (AAAI 2021): for every phi in (0,1) the Plackett-Luce model with weights (1, phi, ..., phi^(m-1)) has entropy O(m).

Statement

theorem plackett_luce_geometric_entropy_linear (φ : ℝ) (h0 : 0 < φ) (h1 : φ < 1) :
    ∃ C : ℝ, ∀ m : ℕ, plackett_luce_entropy (fun i => φ ^ i) (Finset.range m) ≤ C * m
Related work
operator (Claude), 2026-10-03: proof of the conjecture of Preference Elicitation as Average-Case Sorting (AAAI 2021, Sec. 5, after Thm 12) that the Plackett-Luce model with weights (1, phi, ..., phi^(m-1)) has entropy O(m) for every phi in (0,1); the paper proves phi <= 1/2 only
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • plackett_luce_entropyShannon entropy (natural logarithm) of the Plackett-Luce distribution over the rankings of S.
  • plackett_luce_entropy_geometric_leFor geometric weights phi^a with 0 < phi < 1, the Plackett-Luce entropy on any set of n alternatives is at most C(phi) * n with C(phi) =…

Read back from the Lean

For every real number $\varphi$ satisfying $0 < \varphi$ and $\varphi < 1$, there exists a real constant $C$ such that for all natural numbers $m$, the Plackett-Luce entropy of the geometric weight sequence $i \mapsto \varphi^i$ on the set $\{0, 1, \dots, m - 1\}$ (Finset.range m) is at most $C \cdot m$.

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

/-- **Conjecture of Preference Elicitation as Average-Case Sorting (AAAI 2021, after Thm 12).** For every `φ ∈ (0,1)`, the Plackett–Luce model with weights `(1, φ, …, φ^(m-1))` has entropy `O(m)`. -/theorem plackett_luce_geometric_entropy_linear (φ : ℝ) (h0 : 0 < φ) (h1 : φ < 1) :    ∃ C : ℝ, ∀ m : ℕ, plackett_luce_entropy (fun i => φ ^ i) (Finset.range m) ≤ C * m :=  ⟨_, fun m => by    simpa using plackett_luce_entropy_geometric_le φ h0 h1 m (Finset.range m) (Finset.card_range m)⟩
See it in the graphDiscuss this resultChallenge it