Second-order achievability for a fixed pure-state ensemble
OpenQAlgorithms.Papers.Independent.Intakenext100.P76.secondOrderCodingFix a separable-output pure-state cq channel , a measurable probability law on its input alphabet, and . Let be the average output, with eigenvalue law . Assume the self-information has finite mean and finite third absolute moment. Write , , and let be the standard-normal quantile. There exist and an integer , depending on the fixed channel, law and error, such that every admits an actual finite code with average error at most and
The same lower bound holds for the supremum . This is achievability for the specified ensemble and includes .
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P76
noncomputable section
namespace QAlgorithms.Papers.Independent.Intakenext100.P76
open MeasureTheory Filter
open QAlgorithms.Papers.Independent.Information100.P63 (logTwo normalCDF normalQuantile)
open QAlgorithms.Papers.Independent.Information100.P54 (thermalEntropy)
open QAlgorithms.Papers.Independent.Dependency50.P39 (coherentCoefficient)
open QAlgorithms.Papers.Independent.Next46.P32 (PositiveKernel)
open scoped BigOperators ENNReal Topology
attribute [local instance] Classical.propDecidable
attribute [local instance] Classical.decEq
/-- PDF p.9, (5.3), with the Berry–Esseen moment convention on pp.4–5.
Constants depend on the fixed channel, law and error, and precede n. Finite
third absolute self-information moment is explicit; zero variance is included.
This is achievability for the given ensemble, with no capacity-optimality claim. -/
theorem secondOrderCoding {X : Type*} {I : Type} [MeasurableSpace X] [Countable I]
(W : X → I → ℂ) (mu : Measure X) [IsProbabilityMeasure mu]
(hnorm : ∀ x, IsUnitCoefficientVector (W x))
(hmeas : ∀ a b, Measurable (fun x => Matrix.vecMulVec (W x) (star (W x)) a b))
(p : ℕ → ℝ) (hspec : HasSpectralLaw (meanOutput W mu) p)
(hmean : Summable (fun j => p j * (-logTwo (p j))))
(hthird : Summable (fun j => p j * |logTwo (p j)| ^ 3))
(epsilon : ℝ) (he : 0 < epsilon) (he1 : epsilon < 1) :
∃ C : ℝ, 0 < C ∧ ∃ N : ℕ, 2 ≤ N ∧ ∀ n : ℕ, N ≤ n →
let R := (n : ℝ) * selfInformationMean p +
Real.sqrt ((n : ℝ) * selfInformationVariance p) * normalQuantile epsilon -
C * logTwo (n : ℝ)
HasFiniteCode (productPureCQChannel W n) epsilon R ∧
(R : EReal) ≤ logMaxCodeSize (productPureCQChannel W n) epsilon := by sorry
end QAlgorithms.Papers.Independent.Intakenext100.P76
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
Let be a measurable type, a countable type, , and a probability measure on . Assume each has summable squared moduli totaling , and every function is measurable. Let be nonnegative and summable with sum , and suppose equals , where positive-weight vectors have summable squared moduli totaling and are pairwise orthogonal under the coefficient inner product ; zero-weight vectors are unrestricted. Assume additionally that both and are summable, where and . For every , there exist and an integer such that for every , setting
there is a positive integer and a code for with and average error at most . Here , with the standard normal cumulative distribution function; a code consists of an arbitrary encoding and matrices on whose finite quadratic forms are real and nonnegative and which satisfy ; its average error is
Furthermore, , embedded in the extended reals, is at most the extended-real supremum of over all such codes with average error at most . No strictly positive variance assumption is imposed, so is included.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.