Lemma 2 (42)
ProvedQAlgorithms.Papers.Independent.Advance50.P28.heavy_atom_lower_boundAll logarithms are natural and is the full distance. Let be a normalized law on a finite nonempty alphabet , and let be the uniform law on symbols. For a map , write for its pushforward. Every deterministic satisfies
The non-strict heavy-atom threshold is essential; the result supplies an operational finite converse without assuming the invalid unrestricted intermediate inequality (43).
import Definitions.Def_QAlgorithms_Papers_Independent_Advance50_P28
noncomputable section
open MeasureTheory Filter
open scoped BigOperators ENNReal Topology
namespace QAlgorithms.Papers.Independent.Advance50.P28
open QAlgorithms.Papers.Independent.Information100.P56 (IsLaw)
attribute [local instance] Classical.propDecidable Classical.decEq
/-- Hayashi, PDF p.8, Lemma 2, (42): the heavy-atom threshold includes equality. -/
theorem heavy_atom_lower_bound {A : Type*} [Fintype A] [Nonempty A]
{M : ℕ} (hM : 0 < M) (P : A → ℝ) (hP : IsLaw P) (f : A → Fin M) :
(∑ a, if 2 / (M : ℝ) ≤ P a then P a else 0) ≤ extractionError P f := by sorry
end QAlgorithms.Papers.Independent.Advance50.P28
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
For any finite nonempty type , positive natural number , probability law , and function , the assertion is
Here being a probability law means for every and . Atoms whose mass equals are included. The function is arbitrary; it need not be onto. If no atom meets the threshold, the left-hand side is .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.