§1.2: exact lossless memory
ProvedQAlgorithms.Papers.Independent.Intakenext100.P07.lossless_memoryLet 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 .
The minimum fixed binary memory for zero-error source compression is ceil(log2 |supp ρ_X|).
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.lossless
§1.2: exact lossless memory, arXiv:1504.00233v5, PDF p.12. -/
theorem lossless_memory [Nonempty X] (p : X → ℝ) (hp : paperProbability p) :
let k := Nat.ceil (Real.logb 2 ((Finset.univ.filter (fun x => 0 < p x)).card:ℝ))
(∃ c : paperSourceCode X (2^k), ∀ x, 0 < p x → c.decode (c.encode x) = x) ∧
∀ m : ℕ, (∃ c : paperSourceCode X (2^m), ∀ x, 0 < p x → c.decode (c.encode x) = x) → k ≤ m := 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 for every and . Define and , where the ceiling is taken in the natural numbers. There exist functions and such that whenever . Moreover, for every natural number , if such functions exist with messages, then . No reconstruction condition is imposed on symbols of probability zero. The hypotheses ensure ; the statement includes and , for which the message set has one element.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.