Two resource lower bounds for passive-feedback simulation
OpenQAlgorithms.Papers.Independent.Support50.P38.theorem11Let 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 . Fix . There are , depending only on the fixed source and error, such that for every , , and every code of block error at most whose independent seed has an arbitrary law on values and whose output word is determined by seed and message, both bounds hold for that same code:
The second bound constrains combined resources, and becomes a lower bound on randomness alone only after fixing the communication rate.
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 11, PDF pp.5–6: both lower bounds hold for the SAME feedback code, even
for nonuniform independent seed laws. The positive exponential signs are those in the
printed theorem; the opposite sign in the final proof line on p.6 is a source typo. -/
theorem theorem11 {A B : Type} [Fintype A] [Fintype B] [DecidableEq B]
[Nonempty A] [Nonempty B] (p : A → ℝ) (w : A → B → ℝ)
(hp : IsLaw p) (hw : IsStochastic w) (error : ℝ) (he : 0 < error) (he1 : error < 1) :
∃ k : ℝ, 0 < k ∧ ∃ threshold : ℕ, ∀ n ≥ threshold, 0 < n →
∀ c : SharedCode A B n, c.PassiveFeedback → sourceAverageBlockError p w c.output ≤ error →
n * sourceInformationBits p w - k * Real.sqrt n ≤ Real.logb 2 (c.size : ℝ) ∧
n * shannon (sourceOutputMarginal p w) - k * Real.sqrt n ≤
Real.logb 2 ((c.seeds : ℝ) * c.size) := 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, with decidable equality on , let be a nonnegative distribution of total mass , let have nonnegative rows each summing to , and fix . Define , , and . There exist and a natural-number threshold such that for every with , the following holds for every shared code with positive message and seed counts , any seed distribution of total mass , encoder distributions , and decoder distributions : if there are words with , and its output satisfies
then both
The seed law need not be uniform and may assign zero mass to some seeds; the second inequality uses the number of seeds, not their entropy. The constants may depend on the fixed , and singleton alphabets and vanishing probabilities are permitted.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.