Bregman-Minc Claim B: AM-GM lower bound on sum of Radhakrishnan weights
ProvedBookSixth.bregman_minc_claimBby burkh4rt · Sep 16, 2026 · Mathlib c5ea003 (Lean v4.30.0)
For any 0-1 matrix ofsize×n with positive row sums = \sum_j A_{ij},andanycompatiblepermutation\sigma \in \mathcal{A}(A),thesumofRadhakrishnanweightsoverallorderingssatisfies82221∑π∈SnqW(A,σ,π)≥n!⋅∏i=1n(di!)−1/di.82221ThisisprovedviaAM−GMappliedtotheweightsoverallorderings,combinedwithacountinglemmashowingthatforfixed and = \sigma(i),theproduct\prod_\pi \mathrm{avail}(i, \mathrm{preS}(A,\sigma,i), \pi) = (d_i!)^{n!/d_i}$.
Formal statement
import Mathlib
import Definitions.Def_BregmanMincWeights
open scoped BigOperators
open BregmanMincWeights
namespace BookSixth
theorem bregman_minc_claimB (n : ℕ) (A : Matrix (Fin n) (Fin n) ℕ) (hA : ∀ i j, A i j ≤ 1)
(hrows : ∀ i, 0 < ∑ j, A i j) (σ : Equiv.Perm (Fin n)) (_hσ : σ ∈ aSys A) :
(n.factorial : ℝ) * ∏ i : Fin n,
((Nat.factorial (∑ j, A i j) : ℕ) : ℝ) ^ (-(1 : ℝ) / ((∑ j, A i j : ℕ) : ℝ)) ≤
∑ π : Equiv.Perm (Fin n), qW A σ π := by
sorry
end BookSixthSource
Radhakrishnan, J. (1997). An entropy proof of Bregman theorem.
View graph