Optimal exact code with bounded intermediate alphabet
OpenQAlgorithms.Papers.Independent.Support50.P38.theorem15Let 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 . Put and , and let be the infimum of encoder-message entropy over exact ordinary visible codes for . There exists such a code attaining the infimum and obeying
This supplies both optimality attainment and a finite intermediate-alphabet bound.
Source correction. The printed bound is . At it is zero, although a normalized code needs one symbol. The corrected bound changes only that singleton corner.
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
/-- Theorem 15, PDF p.8: attainment of minimum encoder entropy with bounded cardinality.
SOURCE CORRECTION: printed CD-1 is replaced by max(1,CD-1), since C=D=1 requires one
normalized message symbol. Every nonsingleton printed bound is retained. -/
theorem theorem15 {A B : Type} [Fintype A] [Fintype B] [Nonempty A] [Nonempty 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 ≤ max 1 (Fintype.card A * Fintype.card B - 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, let satisfy and , and let satisfy and for every . There exists a length-one compression code with positive message count , encoder probability distributions , and decoder probability distributions , for , such that
Its message distribution attains the infimum of over all length-one codes satisfying this exactness condition, and
The subtraction in the bound is natural-number subtraction, truncated at zero. Singleton alphabets are allowed, so when the bound is ; no strict positivity is assumed for individual source or channel probabilities, and exactness applies even to source letters of probability zero.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.