two_point_mask_vulnerability
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
- biased_bit_cost_vulnerability_initial_segmentFor real numbers p and c satisfying 1 / 2 < p, p < 1, 0 ≤ c, and c ≤ 1 - p, the optimal vulnerability biased_bit_optimal_vulnerability p c…
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.
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.
uses
Finset.mem_insert,Finset.mem_singleton,not_or,mul_zero,max_selfhave 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]
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.
uses
tsum_eq_sumunfold biased_bit_vulnerability rw [tsum_eq_sum hsupp] simp only [two_point_mask] norm_num
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.
uses
max_eq_left,max_eq_right,mul_nonneg,le_of_lthave 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)
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.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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