Direct stationary memoryless cq channel coding
OpenQAlgorithms.Papers.Independent.Intakethird100.P05.cq_coding_directLet be a finite alphabet, let be density operators on a finite-dimensional complex Hilbert space , and let be a probability law on . Put and , where uses natural logarithms and . For every real there is a single sequence of codes with distinct words in , and positive decoder effects summing to at most identity, such that
Here the channel output for is and is the error averaged over uniform messages, including the decoder's failure outcome. Rates are nats per use and . This is the direct coding result for the chosen law .
Formalization Note Positive lengths are indexed by . The liminf bound is expressed equivalently by eventual rate bounds for every .
import Definitions.Def_QAlgorithms_Papers_Independent_Intakethird100_P05
noncomputable section
namespace QAlgorithms.Papers.Independent.Intakethird100.P05
open scoped Matrix ComplexConjugate ComplexOrder BigOperators
open Filter Topology QAlgorithms
open QAlgorithms.Papers.Independent.Information100.P60 (Mat copies)
open QAlgorithms.Papers.Independent.Information100.P07 (positiveProjection)
open QAlgorithms.Papers.Independent.Dependency50.P28 (tr pinch typeI accept)
open QAlgorithms.Papers.Independent.Claimed50.P45 (pinchedTest)
open QAlgorithms.Papers.Independent.Information100.P58 (Distribution)
open QAlgorithms.Papers.Independent.Information100.P27 (average)
open QAlgorithms.Papers.Independent.Dependency50.P07 (wordProb)
open QAlgorithms.Papers.Independent.Dependency50.P35 (directSum)
open QAlgorithms.Papers.Independent.Renew46.P44 (wordOutput)
attribute [local instance] Classical.propDecidable Classical.decEq
variable {X I : Type} [Fintype X] [DecidableEq X] [Fintype I] [DecidableEq I]
/-- PDF p.5, (24)–(25), using the operational definitions on pp.1–2:
for every a < I(p), a SINGLE sequence of positive-length codes has vanishing
uniform-message average error and liminf rate at least a. The eventual lower
bounds for every positive eps express precisely liminf >= a without a real
conditional-infimum default. No converse or maximum-message error is asserted. -/
theorem cq_coding_direct (W : DensityOutputChannel X I) (p : Distribution X)
(a : ℝ) (ha : a < channelInformationNats W p) :
∃ C : ∀ k : ℕ, DistinctWordCode (Fin (k + 1) → X) (Fin (k + 1) → I),
(∀ eps : ℝ, 0 < eps → ∀ᶠ k : ℕ in atTop,
a - eps ≤ Real.log ((C k).size : ℝ) / ((k + 1 : ℕ) : ℝ)) ∧
Tendsto (fun k : ℕ => uniformMessageError (wordOutput W.state (n := k + 1)) (C k))
atTop (𝓝 0) := by sorry
end QAlgorithms.Papers.Independent.Intakethird100.P05
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
For finite index types with decidable equality, let assign to every a complex positive semidefinite matrix on with trace , and let satisfy . Put , define , where is applied by continuous functional calculus and is the natural logarithm, and set . For every real , there exists a sequence of codes , indexed by all natural numbers , with the following properties. Writing , each code has a positive integer size , an injective assignment , and positive semidefinite decoding matrices on satisfying . Define the output matrix of a word by . Then, for every real , eventually for all ,
and the uniform message error tends to as . The sequence starts at block length ; is not required to be positive. The probability and density hypotheses exclude empty or .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.