Equivalence of the two global compression questions
OpenQAlgorithms.Papers.Independent.Support50.P38.question4_equivalenceConsider the following assertions over every pair of finite nonempty alphabets, every input law , and every stochastic channel , with base-two information . Assertion states that for each , the minimum ordinary code size satisfies . Assertion states that for every , , and all sufficiently large positive , there is a single ordinary code with average block error at most and
The typical set uses the count tolerance for each letter . Then
This equivalence concerns universal affirmative answers; it does not assert either open assertion.
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 /-- PDF p.3, paragraph following (10): equivalence of affirmative answers to the two GLOBAL questions. Neither open assertion is promoted to an unconditional theorem. -/ theorem question4_equivalence : QuestionFour ↔ QuestionFourPrime := by sorry end QAlgorithms.Papers.Independent.Support50.P38 end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
The following two assertions are equivalent. In both assertions, let and for arbitrary positive integers , let satisfy and , and let satisfy and for every . Write , , and . For length , write , , and . A compression code consists of a positive integer , an encoder , and a decoder , where each and is a nonnegative probability distribution; its output is , and its average error is . Let be the infimum in of the code sizes with . The first assertion is that for every ,
The second assertion is that for every , every slack , and every width , there is a natural-number threshold such that for every with , there exists such a code satisfying , , and, for every obeying
also . The code in the second assertion may depend on ; neither assertion imposes a shared-randomness resource. The alphabets may be singletons, probabilities may vanish, and the displayed typicality condition has zero tolerance at letters with probability or .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.