Classical fixed-error strong converse
OpenQAlgorithms.Papers.Independent.Support50.P38.theorem3Let be finite nonempty alphabets, a probability law on , and a stochastic channel. All logarithms and entropies are in bits. Write for the memoryless product laws, , and . Let be the minimum message alphabet cardinality of an ordinary visible stochastic encoder and decoder, with independent private randomness and -average block total variation at most . For every fixed ,
This is a strong converse lower bound; it does not assert achievability or existence of a limit.
import Definitions.Def_QAlgorithms_Papers_Independent_Support50_P38
noncomputable section
namespace QAlgorithms.Papers.Independent.Support50.P38
open scoped BigOperators Matrix ComplexConjugate
open Filter
open QAlgorithms.Papers.Independent.Information100.P56 (IsLaw)
open QAlgorithms.Papers.Independent.Frontier30.P12 (IsStochastic)
open QAlgorithms.Papers.Independent.Information100.P27 (shannon labelInformation)
attribute [local instance] Classical.propDecidable
/-- Theorem 3, PDF p.3: fixed-error strong converse without common randomness.
The liminf is retained; no equality or existence of a limit is asserted. -/
theorem theorem3 {A B : Type} [Fintype A] [Fintype B] [Nonempty A] [Nonempty B]
(p : A → ℝ) (w : A → B → ℝ) (hp : IsLaw p) (hw : IsStochastic w)
(error : ℝ) (he : 0 < error) (he1 : error < 1) :
sourceInformationBits p w ≤ Filter.liminf (sizeRate p w error) atTop := by sorry
end QAlgorithms.Papers.Independent.Support50.P38
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
Let be finite nonempty types, let be nonnegative with , let have nonnegative rows each summing to , and let . Write , , and . For each positive block length , let be the least positive message count admitting stochastic encoders and stochastic decoders , with , such that
The assertion is
The minimum is formally the natural-number infimum, which returns if its defining set is empty, and the total real logarithm satisfies ; under the stated hypotheses an exact code can be obtained by transmitting the input word, so the defining sets are nonempty. Zero entries of and are permitted.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.