Theorem II.20: For R≥0,delta>0,n≥n0(a,d,delta), constant-composition code with |M|≥2^(n(R+delta)) has e≥(1/2)2^(−nEsp(R,P)(1+delta)).
OpenQAlgorithms.Papers.Independent.Renew46.P43.spherePackingCodeBoundFix finite input and output sizes and . A single threshold applies to every normalized channel, every type and every constant-composition code of that type at nonnegative . Define . The code error is maximum message error and an infinite exponent gives zero on the right.
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.20, PDF pp.35-36: positive rate slack, maximum error, and one
threshold uniform over channels, types and nonnegative R at fixed a,d,delta. -/
theorem spherePackingCodeBound (a d : ℕ) (ha : 0 < a) (hd : 0 < d)
(delta : ℝ) (hdelta : 0 < delta) :
∃ n0 : ℕ, ∀ (W : FiniteChannel a (fullAlgebra d hd)) (n : ℕ), 0 < n → n0 ≤ n →
∀ (P : PMF (Fin a)) (R : ℝ) (c : FiniteCode W n),
0 ≤ R → c.Composition P → (c.messages : ℝ) ≥ exp2 (n * (R + delta)) →
c.error ≥ (1/2) * divergenceTail n
(ENNReal.ofReal (1 + delta) * sphereExponent 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 real , there exists a natural number such that, simultaneously for every channel with letters and -dimensional density matrix outputs, every natural with , every input probability distribution , every real , and every length code , if every codeword has exactly occurrences of each letter and its message count satisfies , then
A code has a positive number of messages, arbitrary input words , and positive semidefinite measurement matrices summing to the identity; its error is
The output system has a single block, so its block restrictions are vacuous. The quantity in the bound is
where ranges over channels with the same alphabet and output dimension, with , and equals unless , and otherwise equals . Matrix functions use continuous functional calculus and the total real logarithm. Empty infima are , while and for finite ; thus an infinite exponent gives the lower bound . The exact composition assumption may be unsatisfiable for a given . The threshold depends only on , preceding all choices of .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.