Corollary II.19: For 0≤R≤C(W): E(R)≥Eg(R)=max_(P:R≤I(P;W))Eg(R,P).
OpenQAlgorithms.Papers.Independent.Renew46.P43.greedyReliabilityFor a finite stationary channel , define by the joint lower limit of as and . Zero error has exponent . Let and use the greedy exponents just defined. The maxima over input laws and the optimizing entropy-threshold pair are attained, as asserted in the source.
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
/-- Corollary II.19, PDF p.35: endpoints and attainment of both printed maxima
are retained; zero-error reliability values may be +infinity. -/
theorem greedyReliability {a d : ℕ} (ha : 0 < a) (hd : 0 < d)
(W : FiniteChannel a (fullAlgebra d hd)) (R : ℝ) (hR : 0 ≤ R) (hcap : R ≤ W.capacity) :
reliability W R ≥ greedyBound W R ∧
(∃ P : PMF (Fin a), R ≤ W.information P ∧ greedyBound W R = greedyExponent W R P) ∧
(∀ P : PMF (Fin a), R ≤ W.information P → ∃ L Lprime : ℝ, R ≤ Lprime - L ∧
greedyExponent W R P =
min (individualExponent W P L) ((1/2 : ℝ≥0∞) * collectiveExponent W P Lprime)) := 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 , every channel with letters and -dimensional density matrix outputs, and every real satisfying
the following three assertions hold:
there exists a probability distribution with and ; and, for every such , there exist real with and
All distributions here are on the input letters, and the quantities are defined by
The auxiliary are -dimensional density matrices. Here , , and is if , and otherwise is , with matrix functions given by continuous functional calculus and the total real logarithm. Empty extended nonnegative infima are , and empty suprema are . Finally,
along the product filter, where is the infimum of the nonnegative part of the maximum decoding error over positive length codes with messages. Such a code assigns words and has positive semidefinite measurement matrices summing to the identity; its maximum error is . The code infimum is when empty, and , , and otherwise.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.