AFTD Auto-Formalizing Theoretical Domains

two_point_mask_vulnerability

theoremverified

For real numbers p and c satisfying 1 / 2 < p, p < 1, 0 ≤ c, and c ≤ 1 - p, biased_bit_vulnerability p (two_point_mask c) = 1 - p * c.

Statement

theorem two_point_mask_vulnerability (p c : ℝ) (hp : 1 / 2 < p) (hp1 : p < 1) (hc0 : 0 ≤ c) (hc : c ≤ 1 - p) : biased_bit_vulnerability p (two_point_mask c) = 1 - p * c
Source
arXiv:2611.16066, Theorem 5.5
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • two_point_maskGiven a real parameter c, two_point_mask c is the function from ℤ to ℝ mapping 0 to 1 - c, 1 to c, and all other integers to 0.
  • 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…
Used by 1

Read back from the Lean

For all real numbers $p$ and $c$, if $1/2 < p$, $p < 1$, $0 \le c$, and $c \le 1 - p$, then biased_bit_vulnerability p (two_point_mask c) = 1 - p * c.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The definition of biased bit vulnerability expresses the vulnerability as an infinite series of maximum terms over all integers s. Because the two-point mask is supported only on {0, 1}, the summand vanishes outside s ∈ {0, 1, 2}, reducing the infinite series to a sum of three terms. Under the assumptions 1 / 2 < p < 1, 0 ≤ c, and c ≤ 1 - p, each of the three maximums is evaluated directly; in particular, the middle term simplifies to (1 - p) * (1 - c) because (1 - p) * (1 - c) - p * c = 1 - p - c ≥ 0. Summing these three simplified values yields the final result 1 - p * c.

  1. The summand max (p * two_point_mask c s) ((1 - p) * two_point_mask c (s - 1)) vanishes for all integers s ∉ {0, 1, 2}.

    If an integer s is outside {0, 1, 2}, then s ≠ 0 and s ≠ 1, so the two-point mask evaluates to two_point_mask c s = 0. Likewise, s - 1 ≠ 0 and s - 1 ≠ 1, so two_point_mask c (s - 1) = 0. Both products in the maximum are therefore zero, giving max 0 0 = 0.

    lines 4–13

    uses Finset.mem_insert, Finset.mem_singleton, not_or, mul_zero, max_self

      have hsupp : ∀ s : ℤ, s ∉ ({0, 1, 2} : Finset ℤ) →
          max (p * two_point_mask c s) ((1 - p) * two_point_mask c (s - 1)) = 0 := by
        intro s hs
        simp only [Finset.mem_insert, Finset.mem_singleton, not_or] at hs
        obtain ⟨h0, h1, h2⟩ := hs
        have hq0 : two_point_mask c s = 0 := by
          simp [two_point_mask, h0, h1]
        have hq1 : two_point_mask c (s - 1) = 0 := by
          simp [two_point_mask, show s - 1 ≠ 0 by omega, show s - 1 ≠ 1 by omega]
        rw [hq0, hq1, mul_zero, mul_zero, max_self]
  2. The vulnerability reduces to the finite sum of three explicit terms: max (p * (1 - c)) 0 + max (p * c) ((1 - p) * (1 - c)) + max 0 ((1 - p) * c).

    Unfolding the definition of biased bit vulnerability expresses it as an infinite series over ℤ. Because all terms outside {0, 1, 2} vanish, tsum_eq_sum reduces this series to the finite sum over s ∈ {0, 1, 2}. Evaluating the piecewise definition of two_point_mask at s = 0, 1, 2 produces the three terms.

    lines 14–17

    uses tsum_eq_sum

      unfold biased_bit_vulnerability
      rw [tsum_eq_sum hsupp]
      simp only [two_point_mask]
      norm_num
  3. The three maximum terms simplify to p * (1 - c), (1 - p) * (1 - c), and (1 - p) * c, respectively.

    Since p < 1, we have 1 - p > 0. For the first term, p > 0 and 1 - c ≥ p > 0 ensure p * (1 - c) ≥ 0, so the maximum with 0 is p * (1 - c). For the middle term, the difference (1 - p) * (1 - c) - p * c equals 1 - p - c, which is non-negative because c ≤ 1 - p; thus (1 - p) * (1 - c) dominates p * c, resolving the maximum to (1 - p) * (1 - c). For the third term, both 1 - p and c are non-negative, so their product is non-negative, resolving max 0 ((1 - p) * c) to (1 - p) * c.

    lines 19–25

    uses max_eq_left, max_eq_right, mul_nonneg, le_of_lt

      have h1p : (0:ℝ) < 1 - p := by linarith
      have hmax1 : max (p * (1 - c)) 0 = p * (1 - c) := by
        rw [max_eq_left]; nlinarith
      have hmax2 : max (p * c) ((1 - p) * (1 - c)) = (1 - p) * (1 - c) := by
        rw [max_eq_right]; nlinarith
      have hmax3 : max 0 ((1 - p) * c) = (1 - p) * c :=
        max_eq_right (mul_nonneg (le_of_lt h1p) hc0)
  4. The vulnerability of the two-point mask equals 1 - p * c.

    Substituting the three evaluated maximums into the sum yields p * (1 - c) + (1 - p) * (1 - c) + (1 - p) * c. Expanding and combining terms algebraically simplifies this expression to 1 - p * c.

    lines 26–27

      rw [hmax1, hmax2, hmax3]
      ring
Finset.mem_insert
An element belongs to `insert b s` if and only if it equals `b` or belongs to `s`.
Finset.mem_singleton
An element belongs to the singleton set `{a}` if and only if it equals `a`.
not_or
The negation of a disjunction ¬(p ∨ q) is equivalent to ¬p ∧ ¬q (De Morgan's law).
mul_zero
Multiplying any element by zero yields zero: a * 0 = 0.
max_self
The maximum of any element with itself is that element: max a a = a.
tsum_eq_sum
An infinite sum equals the finite sum over a finite set s if every term outside s is zero.
max_eq_left
If b ≤ a, then max a b = a.
max_eq_right
If a ≤ b, then max a b = b.
mul_nonneg
The product of two non-negative numbers is non-negative.
le_of_lt
A strict inequality a < b implies the weak inequality a ≤ b.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- The vulnerability of the two-point mask equals 1 - p * c for 0 ≤ c ≤ 1 - p. -/theorem two_point_mask_vulnerability (p c : ℝ) (hp : 1 / 2 < p) (hp1 : p < 1) (hc0 : 0 ≤ c) (hc : c ≤ 1 - p) : biased_bit_vulnerability p (two_point_mask c) = 1 - p * c := by  -- Only the terms s = 0, 1, 2 of the sum are nonzero.  have hsupp : ∀ s : ℤ, s ∉ ({0, 1, 2} : Finset ℤ) →      max (p * two_point_mask c s) ((1 - p) * two_point_mask c (s - 1)) = 0 := by    intro s hs    simp only [Finset.mem_insert, Finset.mem_singleton, not_or] at hs    obtain ⟨h0, h1, h2⟩ := hs    have hq0 : two_point_mask c s = 0 := by      simp [two_point_mask, h0, h1]    have hq1 : two_point_mask c (s - 1) = 0 := by      simp [two_point_mask, show s - 1 ≠ 0 by omega, show s - 1 ≠ 1 by omega]    rw [hq0, hq1, mul_zero, mul_zero, max_self]  unfold biased_bit_vulnerability  rw [tsum_eq_sum hsupp]  simp only [two_point_mask]  norm_num  -- The middle term is dominated: (1 - p) * (1 - c) - p * c = 1 - p - c ≥ 0.  have h1p : (0:ℝ) < 1 - p := by linarith  have hmax1 : max (p * (1 - c)) 0 = p * (1 - c) := by    rw [max_eq_left]; nlinarith  have hmax2 : max (p * c) ((1 - p) * (1 - c)) = (1 - p) * (1 - c) := by    rw [max_eq_right]; nlinarith  have hmax3 : max 0 ((1 - p) * c) = (1 - p) * c :=    max_eq_right (mul_nonneg (le_of_lt h1p) hc0)  rw [hmax1, hmax2, hmax3]  ring
See it in the graphDiscuss this resultChallenge it