§1.2 (1.6)–(1.7): one-shot compression sandwich
OpenQAlgorithms.Papers.Independent.Intakenext100.P07.one_shot_compression_sandwichLet 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 .
Let p be a finite probability source and 0<epsilon<1. For every 0<delta<epsilon, a code exists whenever log2 m is at least the variation-smoothed order-1/2 entropy at epsilon-delta plus log2(1/delta). Every epsilon-error code obeys the converse lower bound. The least positive feasible alphabet size m*(epsilon) exists and obeys the displayed sandwich.
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.smoothcompression
Equations (1.6)-(1.7), PDF pp.13-14. The plan's rounding concern is discharged by an explicit power-of-two candidate:
m=2^ceil(H+log(1/d)). The minimum over all alphabet sizes is at most this candidate;
no power-of-two restriction is imposed on the optimum. Independent moderation pending. -/
theorem one_shot_compression_sandwich [Nonempty X] (p : X → ℝ) (hp : paperProbability p)
(e : ℝ) (he : 0 < e) (he1 : e < 1) :
(∀ d : ℝ, 0 < d → d < e → ∀ m : ℕ, 0 < m →
introSmoothMax p (e-d)+Real.logb 2 (1/d) ≤ Real.logb 2 m →
∃ c : paperSourceCode X m, paperCodeError p c ≤ e) ∧
(∀ m : ℕ, 0 < m → ∀ c : paperSourceCode X m, paperCodeError p c ≤ e → introSmoothMax p e ≤ Real.logb 2 m) ∧
(0 < optimalCardinality p e ∧ ∃ c : paperSourceCode X (optimalCardinality p e), paperCodeError p c ≤ e) ∧
introSmoothMax p e ≤ Real.logb 2 (optimalCardinality p e) ∧
Real.logb 2 (optimalCardinality p e) ≤ sInf {v : ℝ | ∃ d : ℝ, 0 < d ∧ d < e ∧
v = (Nat.ceil (introSmoothMax p (e-d)+Real.logb 2 (1/d)):ℝ)} := 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 nonempty finite type with decidable equality, let satisfy for every and , and let . For a real radius , write
where the infimum is taken in , with its total infimum convention. A code of cardinality consists of functions and , and its error is . Let be the natural-number infimum of the positive cardinalities admitting a code of error at most , with value if that set is empty. The assertion is the conjunction of the following claims: for every real with and every natural number , the inequality implies that a code of cardinality and error at most exists; every code of positive cardinality and error at most satisfies ; and a code of exactly that cardinality and error at most exists; and
In the last expression, the ceiling is the least natural number at least the displayed real number, so it is when that number is nonpositive, and its result is then regarded as a real number before taking the infimum.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.