§1.2 (1.2): classical Rényi compression direct bound
OpenQAlgorithms.Papers.Independent.Intakenext100.P07.classical_compression_directLet 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 finite probability source X, 0<ε<1, positive integer m, and some α∈[1/2,1), log2 m≥Hα(X)+α/(1−α)log2(1/ε) implies an (ε,m)-code. α=1/2 is included in the PDF interval.
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.direct
§1.2 (1.2): classical Rényi compression direct bound, arXiv:1504.00233v5, PDF p.13. -/
theorem classical_compression_direct [Nonempty X] (p : X → ℝ) (hp : paperProbability p) (e : ℝ) (he : 0 < e) (he1 : e < 1)
(m : ℕ) (hm : 0 < m) (a : ℝ) (ha : 1/2 ≤ a) (ha1 : a < 1)
(hsize : paperClassicalRenyi p a+a/(1-a)*Real.logb 2 (1/e) ≤ Real.logb 2 m) :
∃ c : paperSourceCode X m, paperCodeError p c ≤ e := 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, and let satisfy and . Let , let be a positive natural number, and let . Define
If
then there exist functions and whose error satisfies
The permitted endpoint is included.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.