Weighted information implies the joint security criterion
ProvedQAlgorithms.Papers.Independent.Intakenext100.P77.weighted_information_securityLet be a finite transcript alphabet, let with be joint probabilities of passing and transcript , and let be the information in that transcript. For every threshold ,
In particular, for , , and , if , then
The exponential threshold is positive even when the weighted information is zero. The probabilities are not normalized conditional on passing.
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P77
noncomputable section
namespace QAlgorithms.Papers.Independent.Intakenext100.P77
open scoped BigOperators ComplexConjugate ComplexOrder
open QAlgorithms
-- The repair instruction authorizes imports of pinned accepted definitions.
-- These are definitions only; no imported paper theorem is used here.
open QAlgorithms.Papers.Independent.Dependency50.P47 (Law)
open QAlgorithms.Papers.Independent.Information100.P04 (Measurement)
open QAlgorithms.Papers.Independent.Information100.P27 (shannon)
open QAlgorithms.Papers.Independent.Information100.P39 (pushLaw)
open QAlgorithms.Papers.Independent.Support50.P16 (trivialMeasurement)
attribute [local instance] Classical.propDecidable Classical.decEq
/-- Appendix N, PDF pp.28--29, Eqs.(45),(46): Markov's bound for subnormalized
pass weights and its positive exponential-threshold specialization. No sqrt(W)
threshold is used at W=0. -/
theorem weighted_information_security {T : Type} [Fintype T]
(p : PassWeights T) (info : T → ℝ) (hi : ∀ t, 0 ≤ info t) :
(∀ a : ℝ, 0 < a →
luckyProbability p info a * a ≤ ∑ t, p.weight t * info t) ∧
∀ (alpha beta : ℝ), 0 < beta → ∀ n : ℕ,
(∑ t, p.weight t * info t) ≤ Real.exp (2 * (alpha - beta * n)) →
luckyProbability p info (Real.exp (alpha - beta * n)) ≤
Real.exp (alpha - beta * n) := by sorry
end QAlgorithms.Papers.Independent.Intakenext100.P77
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
Let be any finite type, let weights satisfy for every and , and let satisfy for every . Define , so equality with the threshold is included. Then both of the following hold:
and, for every with and every ,
There is no sign restriction on , is included, and neither total weight one nor nonemptiness of is required; for empty , all the finite sums are zero.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.