Theorem II.18: For empirical P and R<I(P;W), codes have |M|≥(n+1)^(d−ad)2^(nR), e≤8(n+1)^(ad)2^(−nEg(R,P)), if n≥n0(a,d,P).
OpenQAlgorithms.Papers.Independent.Renew46.P43.constantCompositionCodingFix a finite stationary channel with input alphabet size and output dimension . Let be a realizable length- empirical law, and . Here , where and . For fixed , one threshold works for every channel , every realizable positive length , and every .
This is the source result with its stated operational or information-theoretic domain.
import Definitions.Def_QAlgorithms_Papers_Independent_Renew46_P43
noncomputable section
namespace QAlgorithms.Papers.Independent.Renew46.P43
open scoped BigOperators Matrix ComplexConjugate ComplexOrder ENNReal Matrix.Norms.L2Operator
open Filter MeasureTheory
open QAlgorithms.Papers.Independent.Information100.P08 (IsPure)
open QAlgorithms.Papers.Independent.Information100.P06 (Below)
open QAlgorithms.Papers.Independent.Information100.P60 (copies relativeBits)
open QAlgorithms.Papers.Independent.Dependency50.P19 (count both)
open QAlgorithms.Papers.Independent.Information100.P22 (coherentInformation)
attribute [local instance] Classical.propDecidable Classical.decEq
open QAlgorithms.Papers.Independent.Claimed50.P40 (InBlocks)
attribute [local instance] QAlgorithms.Papers.Independent.Renew46.P43.matrixMeasurableSpace
/-- Theorem II.18, PDF pp.34-35: retain the negative polynomial prefactor and
factor 8. The printed n0(a,d,P) precedes the channel W, block length and rate R.
The proof's small-error transition caveat is recorded without weakening this
fully pinned theorem. -/
theorem constantCompositionCoding {a d : ℕ} (ha : 0 < a) (hd : 0 < d)
(P : PMF (Fin a)) :
∃ n0 : ℕ, ∀ (W : FiniteChannel a (fullAlgebra d hd)) (n : ℕ), 0 < n → n0 ≤ n →
(∃ w : Fin n → Fin a, ∀ x, empiricalWeight w x = (P x).toReal) →
∀ R : ℝ, R < W.information P →
∃ c : FiniteCode W n, c.Composition P ∧
(c.messages : ℝ) ≥ (n+1 : ℝ)^((d : ℤ) - (a : ℤ)*d) * exp2 (n * R) ∧
c.error ≤ 8 * (n+1 : ℝ)^(a*d) * divergenceTail n (greedyExponent W R P) := by sorry
end QAlgorithms.Papers.Independent.Renew46.P43
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
For every pair of positive natural numbers and every probability mass function on the alphabet , there exists a natural number such that the following holds uniformly for every channel assigning a positive semidefinite complex matrix of trace to each alphabet symbol , every positive natural number , and every real , provided there exists a length- word in which each symbol occurs exactly times. Here , where , , with defined by continuous functional calculus. There then exists a code with a positive number of messages, an encoding word of length for each message , and positive semidefinite decoding matrices on whose sum is the identity, such that every has empirical frequencies and
The error is precisely ; the outcome is an additional decoding outcome. The tail function is and for finite . Its argument is
All matrices in these infima are . For density matrices , when ; otherwise it is , with the matrix functions interpreted by the functional calculus in the code. These suprema and infima take values in , so an empty infimum is . No positivity assumption is imposed on every , and need not be nonnegative. The exact-composition premise can fail—for example, if some is not an integer—in which case the implication asserts no code existence for that .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.