biased_bit_cost_vulnerability_initial_segment
For 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 equals 1 - p * c, the vulnerability biased_bit_vulnerability p (two_point_mask c) equals 1 - p * c, and for any function q : ℤ → ℝ satisfying (∀ s, 0 ≤ q s), HasSum q 1, and Summable (fun s : ℤ => |(s : ℝ)| * q s), the vulnerability satisfies biased_bit_vulnerability p q ≥ 1 - p * (∑' s : ℤ, |(s : ℝ)| * q s).
Statement
theorem biased_bit_cost_vulnerability_initial_segment (p c : ℝ) (hp : 1 / 2 < p) (hp1 : p < 1) (hc0 : 0 ≤ c) (hc : c ≤ 1 - p) : biased_bit_optimal_vulnerability p c = 1 - p * c ∧ biased_bit_vulnerability p (two_point_mask c) = 1 - p * c ∧ (∀ (q : ℤ → ℝ), (∀ s, 0 ≤ q s) → HasSum q 1 → Summable (fun s : ℤ => |(s : ℝ)| * q s) → biased_bit_vulnerability p q ≥ 1 - p * (∑' s : ℤ, |(s : ℝ)| * q s))
- Formalizes
- arXiv:2611.16066, Theorem 5.5
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- 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…
- biased_bit_optimal_vulnerabilityFor real numbers p and c, biased_bit_optimal_vulnerability p c is the real infimum (sInf) of biased_bit_vulnerability p q over all…
- two_point_mask_momentFor any real number c satisfying 0 ≤ c and c ≤ 1, the sum ∑' s : ℤ, |(s : ℝ)| * two_point_mask c s equals c.
- two_point_mask_vulnerabilityFor 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.
- biased_bit_vulnerability_ge_one_sub_mul_momentFor 1/2 < p < 1 and any probability distribution q on ℤ with finite absolute first moment, the one-guess vulnerability satisfies V_p(q) ≥…
Read back from the Lean
For all real numbers $p$ and $c$, assuming $1/2 < p < 1$, $0 \le c$, and $c \le 1 - p$, three statements hold simultaneously:
1. The optimal biased bit vulnerability at $(p, c)$ equals $1 - p c$ (biased_bit_optimal_vulnerability p c = 1 - p * c).
2. The biased bit vulnerability of the two-point mask at $c$ equals $1 - p c$ (biased_bit_vulnerability p (two_point_mask c) = 1 - p * c).
3. For every distribution $q : \mathbb{Z} \to \mathbb{R}$, if $q(s) \ge 0$ for all $s \in \mathbb{Z}$, the sum of $q$ is $1$ (HasSum q 1), and the first absolute moment series $\sum_{s \in \mathbb{Z}} |s| q(s)$ is summable, then the biased bit vulnerability of $q$ is at least $1 - p \sum_{s \in \mathbb{Z}} |s| q(s)$. (Note that $c$ does not appear in this third conjunct, though it is in scope.)
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 theorem establishes the initial segment of the cost-vulnerability frontier for a biased bit, showing that for 1/2 < p < 1 and 0 ≤ c ≤ 1 - p, the optimal vulnerability equals 1 - p * c and is achieved by a two-point mask. The proof shows that 1 - p * c is the minimum (least element) of achievable vulnerabilities under the cost budget c: the two-point mask provides a feasible witness achieving exactly 1 - p * c, while a general lower bound on vulnerability establishes that no valid distribution with mean absolute cost at most c can achieve lower vulnerability. Since 1 - p * c is the least element of the admissible vulnerabilities, their infimum equals 1 - p * c.
The parameter c satisfies c ≤ 1, and two_point_mask c is a non-negative function supported on {0, 1} that sums to 1.
From c ≤ 1 - p and p > 1/2, linear arithmetic gives c ≤ 1. By definition, two_point_mask c takes value 1 - c at s = 0, value c at s = 1, and 0 elsewhere. Hence any integer outside {0, 1} evaluates to 0. Since 0 ≤ c ≤ 1, the values 1 - c, c, and 0 are all non-negative. Because the function is supported on the finite set {0, 1}, its infinite sum exists and equals the finite sum (1 - c) + c = 1 by hasSum_sum_of_ne_finset_zero.
uses
Finset.mem_insert,Finset.mem_singleton,not_or,hasSum_sum_of_ne_finset_zerohave hc1 : c ≤ 1 := by linarith have h_supp : ∀ s ∉ ({0, 1} : Finset ℤ), two_point_mask c s = 0 := by intro s hs simp only [Finset.mem_insert, Finset.mem_singleton, not_or] at hs unfold two_point_mask simp [hs.1, hs.2] have h_nonneg : ∀ s, 0 ≤ two_point_mask c s := by intro s unfold two_point_mask split_ifs <;> linarith have h_hasSum : HasSum (two_point_mask c) 1 := by have h : HasSum (two_point_mask c) (∑ x ∈ ({0, 1} : Finset ℤ), two_point_mask c x) := hasSum_sum_of_ne_finset_zero h_supp have h_sum : ∑ x ∈ ({0, 1} : Finset ℤ), two_point_mask c x = 1 := by simp [two_point_mask] rwa [h_sum] at h
The first absolute moment series ∑' s : ℤ, |s| * two_point_mask c s is summable and bounded by c.
Multiplying the support condition by |s| shows that |s| * two_point_mask c s = 0 for all s ∉ {0, 1}, using mul_zero. As a function vanishing outside a finite set, it is summable by summable_of_ne_finset_zero. Finally, two_point_mask_moment shows that the sum of this moment series is exactly c, so it is ≤ c.
uses
mul_zero,summable_of_ne_finset_zero,two_point_mask_momenthave h_supp_mom : ∀ s ∉ ({0, 1} : Finset ℤ), |(s : ℝ)| * two_point_mask c s = 0 := by intro s hs rw [h_supp s hs, mul_zero] have h_mom_summable : Summable (fun s : ℤ => |(s : ℝ)| * two_point_mask c s) := summable_of_ne_finset_zero h_supp_mom have h_mom_le : (∑' s : ℤ, |(s : ℝ)| * two_point_mask c s) ≤ c := by rw [two_point_mask_moment c hc0 hc1]
The vulnerability of two_point_mask c equals 1 - p * c.
This equality is asserted directly by the helper lemma two_point_mask_vulnerability, using the assumptions 1/2 < p < 1, 0 ≤ c, and c ≤ 1 - p.
uses
two_point_mask_vulnerabilityhave h_val : biased_bit_vulnerability p (two_point_mask c) = 1 - p * c := two_point_mask_vulnerability p c hp hp1 hc0 hcThe optimal vulnerability biased_bit_optimal_vulnerability p c equals 1 - p * c.
The optimal vulnerability is defined as the infimum of vulnerabilities over all distributions q satisfying the non-negativity, total mass 1, and cost constraint ≤ c. By IsLeast.csInf_eq, it suffices to prove that 1 - p * c is the least element of this set. The distribution two_point_mask c is feasible and achieves value 1 - p * c, establishing that 1 - p * c belongs to the set. Conversely, for any feasible distribution q, biased_bit_vulnerability_ge_one_sub_mul_moment shows its vulnerability is at least 1 - p * ∑' s, |s| * q s; since p > 0 and the moment is at most c, multiplying by p preserves the inequality via mul_le_mul_of_nonneg_left, yielding vulnerability ≥ 1 - p * c. Thus 1 - p * c is a lower bound.
uses
IsLeast.csInf_eq,biased_bit_vulnerability_ge_one_sub_mul_moment,mul_le_mul_of_nonneg_lefthave h_opt : biased_bit_optimal_vulnerability p c = 1 - p * c := by unfold biased_bit_optimal_vulnerability apply IsLeast.csInf_eq constructor · exact ⟨two_point_mask c, h_nonneg, h_hasSum, h_mom_summable, h_mom_le, h_val⟩ · rintro v ⟨q, hq0, hq1, hqm, hqc, rfl⟩ have hge := biased_bit_vulnerability_ge_one_sub_mul_moment p hp hp1 q hq0 hq1 hqm have hp_pos : 0 < p := by linarith have h_pc : p * (∑' s : ℤ, |(s : ℝ)| * q s) ≤ p * c := mul_le_mul_of_nonneg_left hqc hp_pos.le linarith
The three conjunctions in the theorem statement all hold.
The final step packages the results into the required conjunction: the optimal vulnerability equals 1 - p * c, the two-point mask achieves 1 - p * c, and any valid distribution q satisfies the general lower bound, supplied directly by biased_bit_vulnerability_ge_one_sub_mul_moment.
uses
biased_bit_vulnerability_ge_one_sub_mul_momentexact ⟨h_opt, h_val, fun q hq0 hq1 hqm => biased_bit_vulnerability_ge_one_sub_mul_moment p hp hp1 q hq0 hq1 hqm⟩
Finset.mem_insert- An element x belongs to the insertion insert a s if and only if x = a or x ∈ s.
Finset.mem_singleton- An element x belongs to the singleton set {a} if and only if x = a.
not_or- The negation of a disjunction ¬(P ∨ Q) is equivalent to the conjunction of the negations ¬P ∧ ¬Q.
hasSum_sum_of_ne_finset_zero- If a function vanishes outside a finite set s, its infinite sum exists and equals the finite sum over s.
mul_zero- Multiplying any element by zero on the right yields zero.
summable_of_ne_finset_zero- A function that vanishes outside a finite set is summable.
two_point_mask_moment- For 0 ≤ c ≤ 1, the first absolute moment ∑' s : ℤ, |s| * two_point_mask c s equals c.
two_point_mask_vulnerability- For 1/2 < p < 1, 0 ≤ c, and c ≤ 1 - p, the vulnerability of two_point_mask c is 1 - p * c.
IsLeast.csInf_eq- If an element is the least element of a set, then the infimum of the set equals that element.
biased_bit_vulnerability_ge_one_sub_mul_moment- For any 1/2 < p < 1 and any valid probability distribution q on ℤ with summable first absolute moment, its vulnerability is at least 1 - p * ∑' s : ℤ, |s| * q s.
mul_le_mul_of_nonneg_left- Multiplying an inequality b ≤ c on the left by a non-negative element a preserves the inequality: a * b ≤ a * c.
- In Lean, verifying that a distribution supported on a two-element set sums to 1 and has a summable first moment requires explicit topological summation lemmas (hasSum_sum_of_ne_finset_zero and summable_of_ne_finset_zero), whereas on paper this is treated as an immediate finite sum.
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.
/-- Theorem 5.5: Initial segment of the biased-bit cost-vulnerability frontier. -/theorem biased_bit_cost_vulnerability_initial_segment (p c : ℝ) (hp : 1 / 2 < p) (hp1 : p < 1) (hc0 : 0 ≤ c) (hc : c ≤ 1 - p) : biased_bit_optimal_vulnerability p c = 1 - p * c ∧ biased_bit_vulnerability p (two_point_mask c) = 1 - p * c ∧ (∀ (q : ℤ → ℝ), (∀ s, 0 ≤ q s) → HasSum q 1 → Summable (fun s : ℤ => |(s : ℝ)| * q s) → biased_bit_vulnerability p q ≥ 1 - p * (∑' s : ℤ, |(s : ℝ)| * q s)) := by have hc1 : c ≤ 1 := by linarith have h_supp : ∀ s ∉ ({0, 1} : Finset ℤ), two_point_mask c s = 0 := by intro s hs simp only [Finset.mem_insert, Finset.mem_singleton, not_or] at hs unfold two_point_mask simp [hs.1, hs.2] have h_nonneg : ∀ s, 0 ≤ two_point_mask c s := by intro s unfold two_point_mask split_ifs <;> linarith have h_hasSum : HasSum (two_point_mask c) 1 := by have h : HasSum (two_point_mask c) (∑ x ∈ ({0, 1} : Finset ℤ), two_point_mask c x) := hasSum_sum_of_ne_finset_zero h_supp have h_sum : ∑ x ∈ ({0, 1} : Finset ℤ), two_point_mask c x = 1 := by simp [two_point_mask] rwa [h_sum] at h have h_supp_mom : ∀ s ∉ ({0, 1} : Finset ℤ), |(s : ℝ)| * two_point_mask c s = 0 := by intro s hs rw [h_supp s hs, mul_zero] have h_mom_summable : Summable (fun s : ℤ => |(s : ℝ)| * two_point_mask c s) := summable_of_ne_finset_zero h_supp_mom have h_mom_le : (∑' s : ℤ, |(s : ℝ)| * two_point_mask c s) ≤ c := by rw [two_point_mask_moment c hc0 hc1] have h_val : biased_bit_vulnerability p (two_point_mask c) = 1 - p * c := two_point_mask_vulnerability p c hp hp1 hc0 hc have h_opt : biased_bit_optimal_vulnerability p c = 1 - p * c := by unfold biased_bit_optimal_vulnerability apply IsLeast.csInf_eq constructor · exact ⟨two_point_mask c, h_nonneg, h_hasSum, h_mom_summable, h_mom_le, h_val⟩ · rintro v ⟨q, hq0, hq1, hqm, hqc, rfl⟩ have hge := biased_bit_vulnerability_ge_one_sub_mul_moment p hp hp1 q hq0 hq1 hqm have hp_pos : 0 < p := by linarith have h_pc : p * (∑' s : ℤ, |(s : ℝ)| * q s) ≤ p * c := mul_le_mul_of_nonneg_left hqc hp_pos.le linarith exact ⟨h_opt, h_val, fun q hq0 hq1 hqm => biased_bit_vulnerability_ge_one_sub_mul_moment p hp hp1 q hq0 hq1 hqm⟩