biased_bit_vulnerability_eq_excess_sum
lemmaverifiedformalization
For any bias p ∈ ℝ and any probability distribution q on ℤ (with q(s) ≥ 0 for all s and HasSum q 1), the one-guess vulnerability V_p(q) equals p + ∑_{s ∈ ℤ} max(0, (1 - p) q(s - 1) - p q(s)).
Statement
lemma biased_bit_vulnerability_eq_excess_sum (p : ℝ) (q : ℤ → ℝ)
(hq_nonneg : ∀ s, 0 ≤ q s) (hq_sum : HasSum q 1) :
biased_bit_vulnerability p q = p + ∑' s : ℤ, max 0 ((1 - p) * q (s - 1) - p * q s)- Formalizes
- arXiv:2611.16066, line 200
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- biased_bit_vulnerabilityThe one-guess vulnerability V_p(q) of an additive integer mask with distribution q against a secret bit with bias p ∈ (1/2, 1) is the…
Read back from the Lean
For every real number $p$ and function $q : ℤ → ℝ$, if $q(s) ≥ 0$ for all $s \in ℤ$ and the sum of $q(s)$ over $s \in ℤ$ converges to $1$ (i.e., HasSum q 1), then biased_bit_vulnerability p q equals $p + \sum_{s \in ℤ} \max(0, (1 - p) q(s - 1) - p q(s))$ (where the sum is evaluated using Lean's tsum).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Excess representation of the one-guess vulnerability V_p(q) for an additive mask on a biased bit. -/ lemma biased_bit_vulnerability_eq_excess_sum (p : ℝ) (q : ℤ → ℝ) (hq_nonneg : ∀ s, 0 ≤ q s) (hq_sum : HasSum q 1) : biased_bit_vulnerability p q = p + ∑' s : ℤ, max 0 ((1 - p) * q (s - 1) - p * q s) := by unfold biased_bit_vulnerability have hshift : HasSum (fun s : ℤ => q (s - 1)) 1 := by have h := (Equiv.hasSum_iff (f := q) (e := Equiv.subRight (1 : ℤ))).2 hq_sum simpa [Function.comp_def, Equiv.subRight] using h have hpbase : HasSum (fun s : ℤ => p * q s) p := by simpa using HasSum.mul_left p hq_sum have hpshift : HasSum (fun s : ℤ => (1 - p) * q (s - 1)) (1 - p) := by simpa using HasSum.mul_left (1 - p) hshift have hA : HasSum (fun s : ℤ => (1 - p) * q (s - 1) - p * q s) ((1 - p) - p) := by simpa using hpshift.sub hpbase have hg : Summable (fun s : ℤ => max 0 ((1 - p) * q (s - 1) - p * q s)) := by apply Summable.of_nonneg_of_le · intro s exact le_max_left 0 _ · intro s exact max_le (abs_nonneg _) (le_abs_self _) · exact Summable.abs hA.summable calc ∑' s : ℤ, max (p * q s) ((1 - p) * q (s - 1)) = ∑' s : ℤ, (p * q s + max 0 ((1 - p) * q (s - 1) - p * q s)) := by apply tsum_congr intro s rw [add_max] ring_nf _ = (∑' s : ℤ, p * q s) + ∑' s : ℤ, max 0 ((1 - p) * q (s - 1) - p * q s) := by rw [Summable.tsum_add hpbase.summable hg] _ = p + ∑' s : ℤ, max 0 ((1 - p) * q (s - 1) - p * q s) := by rw [hpbase.tsum_eq]