AFTD Auto-Formalizing Theoretical Domains

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]
See it in the graphDiscuss this resultChallenge it