§1.2 (1.5): source coding and strong converse
OpenQAlgorithms.Papers.Independent.Intakenext100.P07.classical_source_codingLet be a probability law on a finite nonempty alphabet . A code consists of an encoder into an alphabet of symbols and a decoder, and its error is the probability of recovering the wrong source symbol. Logs are binary, and is Shannon entropy. Introductory smooth max-entropy minimizes the order- Rényi entropy over normalized probability laws within variational distance .
For iid finite source law τ and a fixed error in (0,1), any rate R>H(τ) admits codes for all sufficiently large n; rates below H(τ) have failure probability tending to one. Cardinalities must be rounded to integers rather than using Fin(2^(nR)) for arbitrary real R).
This result records the source’s operational or structural relation, with the stated endpoint and attainment clauses retained.
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P07
noncomputable section
open Filter
open scoped BigOperators Matrix ComplexConjugate ComplexOrder Matrix.Norms.L2Operator Topology
namespace QAlgorithms.Papers.Independent.Intakenext100.P07
attribute [local instance] Classical.propDecidable Classical.decEq
variable {I J A B C D X Y Z : Type*}
variable [Fintype I] [DecidableEq I] [Fintype J] [DecidableEq J]
variable [Fintype A] [DecidableEq A] [Fintype B] [DecidableEq B]
variable [Fintype C] [DecidableEq C] [Fintype D] [DecidableEq D]
variable [Fintype X] [DecidableEq X] [Fintype Y] [DecidableEq Y]
variable [Fintype Z] [DecidableEq Z]
/-- NODE paper:1504.00233#1.shannon
§1.2 (1.5): source coding and strong converse, arXiv:1504.00233v5, PDF p.13. -/
theorem classical_source_coding [Nonempty X] (p : X → ℝ) (hp : paperProbability p) (R : ℝ) (hR : 0 ≤ R) :
(paperShannon p < R → ∀ e : ℝ, 0 < e → e < 1 → ∃ N : ℕ, ∀ n ≥ N,
∃ c : paperSourceCode (Fin n → X) (codeCardinality n R), paperCodeError (iidLaw p n) c ≤ e) ∧
(R < paperShannon p → ∀ codes : (n : ℕ) → paperSourceCode (Fin n → X) (codeCardinality n R),
Tendsto (fun n => paperCodeError (iidLaw p n) (codes n)) atTop (nhds 1)) := by sorry
end QAlgorithms.Papers.Independent.Intakenext100.P07
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
Let be a finite nonempty type, with decidable equality, let satisfy and , and let . Define , with the scalar logarithm taking value at , define on , and put . A code with messages consists of arbitrary functions and , with error . The assertion is that, if , then for every there is a natural number such that for every natural some such code has error at most ; and, if , then for every family of such codes, one for each natural , their errors converge to as . No conclusion is imposed by either implication when . The definitions include , where is a singleton, the empty product is , and .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.