Theorem IV.10: For W,P and lambda,delta,eta>0, all n≥n0 admit m−1≤2^(n(H(P)−I(P;W)+3delta)) disjoint codebooks Ci, each (n,lambda) code of size≥2
OpenQAlgorithms.Papers.Independent.Renew46.P43.codePartitionLet be a finite classical-input channel, a law on , and . Uniformly in at fixed alphabet and output dimension, all sufficiently large admit disjoint codebooks , each with an actual collective maximum-error decoder of error at most . The choice is allowed.
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 IV.10, PDF p.53: disjoint large codebooks, each carrying an actual
maximum-error decoder. Zero codebooks are allowed, as needed when eta>1. -/
theorem codePartition (a : ℕ) (ha : 0 < a) (A : IntrinsicSystem)
(lambda delta eta : ℝ) (hlambda : 0 < lambda) (hdelta : 0 < delta) (heta : 0 < eta) :
∃ n0 : ℕ, 0 < n0 ∧ ∀ (W : FiniteChannel a A) (P : PMF (Fin a)) (n : ℕ), n0 ≤ n →
∃ k : ℕ, ∃ c : Fin k → FiniteCode W n,
(k : ℝ) ≤ exp2 (n * (pmfEntropy P - W.information P + 3 * delta)) ∧
(∀ i, (c i).error ≤ lambda ∧ Function.Injective (c i).word ∧
((c i).codebook.card : ℝ) ≥ exp2 (n * (W.information P - 2 * delta))) ∧
(∀ i j, i ≠ j → Disjoint (c i).codebook (c j).codebook) ∧
(∑ w ∈ (Finset.univ.filter fun w : Fin n → Fin a => ∀ i, w ∉ (c i).codebook),
∏ t, (P (w t)).toReal) < eta := 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 positive integer , every intrinsic system with positive dimension and block label , and every three positive reals , there exists a positive integer such that, simultaneously for every channel , every probability mass function on the input letters, and every natural number , there exist a natural number and codes for satisfying
Each is positive semidefinite of trace and satisfies whenever . Writing , the quantities in this bound are
where , , using continuous functional calculus and . Each code has positive message count , an injective encoding , and positive semidefinite measurement matrices summing to the identity; their entries vanish between output words whose -labels differ at any coordinate. Its error and codebook satisfy
The sets are pairwise disjoint, and the uncovered words have strictly less than product probability:
There is no upper restriction on , and no constant-composition requirement on these codebooks. The number is allowed to be ; in that case the conditions on individual codes and disjointness are vacuous and the uncovered probability is , so the last inequality requires .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.