AFTD Auto-Formalizing Theoretical Domains

biased_bit_cost_vulnerability_initial_segment

theoremverifiedformalization

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.

  1. 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.

    lines 3–18

    uses Finset.mem_insert, Finset.mem_singleton, not_or, hasSum_sum_of_ne_finset_zero

      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
  2. 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.

    lines 19–25

    uses mul_zero, summable_of_ne_finset_zero, two_point_mask_moment

      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]
  3. 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.

    lines 26–27

    uses two_point_mask_vulnerability

      have h_val : biased_bit_vulnerability p (two_point_mask c) = 1 - p * c :=
        two_point_mask_vulnerability p c hp hp1 hc0 hc
  4. The 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.

    lines 28–38

    uses IsLeast.csInf_eq, biased_bit_vulnerability_ge_one_sub_mul_moment, mul_le_mul_of_nonneg_left

      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
  5. 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.

    line 39

    uses biased_bit_vulnerability_ge_one_sub_mul_moment

      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⟩
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.

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

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