Capacity from the spread of column entropies
OpenQAlgorithms.Papers.Independent.Support50.P15.proposition13Let be a normalized discrete memoryless channel with nonempty input alphabet and finite output cardinality . Capacity is measured in nats as the supremum of single-letter mutual information over finite-support input laws. Put , , and . Then
If the fixed-dimensional asymmetry statement of Conjecture 12 holds, also . Finite input alphabets have attained column extrema; supremal and infimal entropies give the same statement for arbitrary nonempty discrete input, without an unmentioned finiteness assumption. This supplies a capacity lower bound from column entropy spread alone.
import Definitions.Def_QAlgorithms_Papers_Independent_Support50_P15
noncomputable section
attribute [local instance] Classical.propDecidable
open scoped Matrix ComplexConjugate ENNReal Matrix.Norms.L2Operator
open Filter MeasureTheory
namespace QAlgorithms.Papers.Independent.Support50.P15
open QAlgorithms.Papers.Independent.Information100.P56 (entropy)
/-- Proposition 13, PDF p.15. Arbitrary nonempty discrete input; finite output; capacity in nats.
Supremal/infimal column entropies allow nonattained extrema. -/
theorem proposition13 {X : Type*} [Nonempty X] {d : ℕ} (hd : 2 ≤ d) (c : FiniteOutputChannel X d) :
let lo := sInf (Set.range (fun x => shannonEntropyNats (c.prob x)))
let hi := sSup (Set.range (fun x => shannonEntropyNats (c.prob x)))
redundancyBound d (hi - lo) ≤ finiteOutputCapacityNats c ∧
(asymmetryConjecture d → tightBound d (-(hi - lo) / 2) ≤ (finiteOutputCapacityNats c : EReal)) := by sorry
end QAlgorithms.Papers.Independent.Support50.P15
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
Let be any nonempty type, with no finiteness assumption, let be a natural number, and let a channel assign to each numbers , , with . Using natural logarithms and , define , , and . Define its capacity by the real supremum
The allowed contributes no feasible probability vector. Put and . For and , define
where , if , if , and otherwise; an empty infimum is . Then . In addition, if for every , then , with this second inequality interpreted in the extended reals.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.