Improved bound with entropy-minimum attainment
OpenQAlgorithms.Papers.Independent.Support50.P38.remark16Let be finite nonempty alphabets, a probability law on , and a stochastic channel. All logarithms and entropies are in bits. Write for the memoryless product laws, , and . Assume and . If is the infimum of the message entropy of exact ordinary visible codes, there exists one attaining that infimum and satisfying
The bound refines the finite intermediate alphabet required for an entropy-optimal exact code.
import Definitions.Def_QAlgorithms_Papers_Independent_Support50_P38
noncomputable section
namespace QAlgorithms.Papers.Independent.Support50.P38
open scoped BigOperators Matrix ComplexConjugate
open Filter
open QAlgorithms.Papers.Independent.Information100.P56 (IsLaw)
open QAlgorithms.Papers.Independent.Frontier30.P12 (IsStochastic)
open QAlgorithms.Papers.Independent.Information100.P27 (shannon labelInformation)
attribute [local instance] Classical.propDecidable
/-- Remark 16, PDF p.8: the improved finite alphabet bound still attains the entropy
minimum; C and D here are cardinalities, each at least two. -/
theorem remark16 {A B : Type} [Fintype A] [Fintype B] [Nonempty A] [Nonempty B]
(ha : 2 ≤ Fintype.card A) (hb : 2 ≤ Fintype.card B)
(p : A → ℝ) (w : A → B → ℝ) (hp : IsLaw p) (hw : IsStochastic w) :
∃ c : DistributionCompressionCode A B 1, c.Exact w ∧
shannon (c.messageLaw p) = exactEntropy p w 1 ∧
c.size ≤ Fintype.card A * Fintype.card B - Fintype.card A + 1 := by sorry
end QAlgorithms.Papers.Independent.Support50.P38
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
Let be finite nonempty types with and , let be nonnegative with total mass , and let have nonnegative rows each summing to . There exists a length-one compression code with positive message count , encoder probability distributions , and decoder probability distributions , for , satisfying for every . Its induced message distribution has Shannon entropy equal to the real infimum of that entropy over all exact length-one codes, and its size satisfies
The subtraction is natural-number subtraction, truncated at zero, though the cardinality hypotheses ensure . Individual source or channel probabilities may be zero, and the exactness condition still quantifies over all input and output words.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.