Lemma 3 (47)
ProvedQAlgorithms.Papers.Independent.Advance50.P28.positive_sequence_allocationprove2quantum
Let be integers. Let and be strictly positive real sequences, without normalization, such that . There is a map such that
Here . This allocation result supports the construction of finite extractors.
Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Advance50_P28
Formal statement
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 3, (47): positive, unnormalized sequences. -/
theorem positive_sequence_allocation {M N : ℕ} (hN : 0 < N) (hMN : N ≤ M)
(alpha : Fin N → ℝ) (beta : Fin M → ℝ)
(ha : ∀ i, 0 < alpha i) (hb : ∀ j, 0 < beta j)
(hmass : (∑ j, beta j) ≤ ∑ i, alpha i) :
∃ f : Fin M → Fin N,
(∑ i, max ((∑ j, if f j = i then beta j else 0) - alpha i) 0) ≤
(N : ℝ) * peak beta := by sorry
end QAlgorithms.Papers.Independent.Advance50.P28
end
Source
Tight exponential analysis of universally composable privacy amplification and its applications, arXiv:1010.1358v5, PDF p. 8, Lemma 3 (47)
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
Let be natural numbers with , and let and have strictly positive entries. If , then there exists a function such that
There is no normalization assumption on either sequence, equality of their total masses is permitted, and the function is not required to be onto.
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.