AFTD Auto-Formalizing Theoretical Domains

biased_bit_initial_segment_optimizer_unique

theoremverifiedformalization

For any bias parameter p with 1 / 2 < p and p < 1, and any budget c with 0 < c and c ≤ 1 - p, if q is a function from ℤ to ℝ satisfying (∀ s, 0 ≤ q s), HasSum q 1, Summable (fun s : ℤ => |(s : ℝ)| * q s), (∑' s : ℤ, |(s : ℝ)| * q s) ≤ c, and biased_bit_vulnerability p q = biased_bit_optimal_vulnerability p c, then q = two_point_mask c.

Statement

theorem biased_bit_initial_segment_optimizer_unique
    (p : ℝ) (hp : 1 / 2 < p) (hp1 : p < 1)
    (c : ℝ) (hc0 : 0 < c) (hc : c ≤ 1 - p)
    (q : ℤ → ℝ) (hq_nonneg : ∀ s, 0 ≤ q s) (hq_sum : HasSum q 1)
    (hq_mom : Summable (fun s : ℤ => |(s : ℝ)| * q s))
    (hq_cost : (∑' s : ℤ, |(s : ℝ)| * q s) ≤ c)
    (hq_opt : biased_bit_vulnerability p q = biased_bit_optimal_vulnerability p c) :
    q = two_point_mask c
Formalizes
arXiv:2611.16066 Thm 5.5
Verified
16 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • 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_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.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • 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 any real numbers p and c satisfying 1 / 2 < p < 1, 0 < c, and c ≤ 1 - p, and for any function q : ℤ → ℝ such that: 1. q s ≥ 0 for all s : ℤ, 2. the sum of q over ℤ converges to 1 (HasSum q 1), 3. the series ∑ s : ℤ, |(s : ℝ)| * q s is summable, 4. ∑' s : ℤ, |(s : ℝ)| * q s ≤ c, and 5. biased_bit_vulnerability p q = biased_bit_optimal_vulnerability p c, then q is equal to the two-point mask two_point_mask c (the function mapping 0 to 1 - c, 1 to c, and all other integers to 0).

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

To prove that any optimal noise distribution q on the initial segment (0, 1 - p] equals two_point_mask c, the proof underestimates the vulnerability by replacing the pointwise maximum max(p * q(s), (1 - p) * q(s - 1)) with a test function choosing p * q(s) for nonpositive s and (1 - p) * q(s - 1) for positive s. Since q achieves the optimal vulnerability 1 - p * c, the resulting lower bound holds with equality and forces the cost to exhaust the budget c. Analyzing the slack in this bound reveals that both the mass on negative integers and the excess weight ∑_{s ≠ 0} (|s| - 1) q(s) must vanish, confining the support of q to {0, 1}. The normalization and cost constraints then uniquely determine q(0) = 1 - c and q(1) = c, matching two_point_mask c.

  1. The distribution q, its shift, and its restrictions to various index sets (nonpositive, positive, strictly negative, nonnegative, nonzero, shifted positive) are all summable.

    From 1 / 2 < p < 1, we note p > 0 and 1 - p ≥ 0. The assumption HasSum q 1 implies q is summable, and shifting indices by 1 preserves summability. Since q ≥ 0, restricting q or its shift to any subset of ℤ yields a non-negative function bounded pointwise by q (or its shift), and hence is summable by comparison (Summable.of_nonneg_of_le).

    lines 10–50

    uses Summable.of_nonneg_of_le

      have hp0 : 0 < p := by linarith
      have h1p : 0 ≤ 1 - p := by linarith
      have hq : Summable q := hq_sum.summable
      have hqshift : Summable (fun s : ℤ => q (s - 1)) :=
        hq.comp_injective (fun a b hab => by simpa using hab)
      have hqm : Summable (fun s : ℤ => if s ≤ 0 then q s else 0) := by
        apply Summable.of_nonneg_of_le (fun s => ?_) (fun s => ?_) hq
        · split_ifs <;> simp [hq_nonneg]
        · split_ifs with h
          · exact le_rfl
          · exact hq_nonneg s
      have hqpos : Summable (fun s : ℤ => if 0 < s then q s else 0) := by
        apply Summable.of_nonneg_of_le (fun s => ?_) (fun s => ?_) hq
        · split_ifs <;> simp [hq_nonneg]
        · split_ifs with h
          · exact le_rfl
          · exact hq_nonneg s
      have hqneg : Summable (fun s : ℤ => if s < 0 then q s else 0) := by
        apply Summable.of_nonneg_of_le (fun s => ?_) (fun s => ?_) hq
        · split_ifs <;> simp [hq_nonneg]
        · split_ifs with h
          · exact le_rfl
          · exact hq_nonneg s
      have hqge : Summable (fun s : ℤ => if 0 ≤ s then q s else 0) := by
        apply Summable.of_nonneg_of_le (fun s => ?_) (fun s => ?_) hq
        · split_ifs <;> simp [hq_nonneg]
        · split_ifs with h
          · exact le_rfl
          · exact hq_nonneg s
      have hqnz : Summable (fun s : ℤ => if s ≠ 0 then q s else 0) := by
        apply Summable.of_nonneg_of_le (fun s => ?_) (fun s => ?_) hq
        · split_ifs <;> simp [hq_nonneg]
        · split_ifs with h
          · exact le_rfl
          · exact hq_nonneg s
      have hqsh : Summable (fun s : ℤ => if 0 < s then q (s - 1) else 0) := by
        apply Summable.of_nonneg_of_le (fun s => ?_) (fun s => ?_) hqshift
        · split_ifs <;> simp [hq_nonneg]
        · split_ifs with h
          · exact le_rfl
          · exact hq_nonneg (s - 1)
  2. The total mass of q on non-zero integers decomposes into the sum over positive and negative integers, and is bounded above by the first absolute moment ∑ |s| q(s).

    We partition the total mass ∑ q(s) = 1 into positive and nonpositive parts, and into strictly negative and nonnegative parts. Shifting indices via Equiv.tsum_eq with Equiv.subRight equates ∑_{s > 0} q(s - 1) with ∑_{s ≥ 0} q(s). Trichotomy (lt_trichotomy) decomposes the sum over s ≠ 0 into positive and negative parts. Finally, since |s| ≥ 1 for all integers s ≠ 0 (Int.one_le_abs), multiplying by q(s) ≥ 0 (mul_le_mul_of_nonneg_right) and comparing terms (Summable.tsum_le_tsum) yields ∑_{s ≠ 0} q(s) ≤ ∑ |s| q(s).

    lines 51–97

    uses Equiv.tsum_eq, Equiv.subRight, lt_trichotomy, Summable.tsum_le_tsum, Int.one_le_abs, mul_le_mul_of_nonneg_right

      have hqm_split : (∑' s : ℤ, if s ≤ 0 then q s else 0) = 1 - ∑' s : ℤ, (if 0 < s then q s else 0) := by
        have heq : (fun s : ℤ => (if s ≤ 0 then q s else 0) + (if 0 < s then q s else 0)) = q := by
          funext s
          by_cases h : s ≤ 0
          · simp [h, not_lt.mpr h]
          · simp [h, not_le.mp h]
        have h := hqm.tsum_add hqpos
        rw [heq, hq_sum.tsum_eq] at h
        linarith
      have hqge_split : (∑' s : ℤ, if 0 ≤ s then q s else 0) = 1 - ∑' s : ℤ, (if s < 0 then q s else 0) := by
        have heq : (fun s : ℤ => (if 0 ≤ s then q s else 0) + (if s < 0 then q s else 0)) = q := by
          funext s
          by_cases h : 0 ≤ s
          · simp [h, not_lt.mpr h]
          · simp [h, not_le.mp h]
        have h := hqge.tsum_add hqneg
        rw [heq, hq_sum.tsum_eq] at h
        linarith
      have hqsh_eq : (∑' s : ℤ, if 0 < s then q (s - 1) else 0) = (∑' s : ℤ, if 0 ≤ s then q s else 0) := by
        have h := Equiv.tsum_eq (Equiv.subRight (1:ℤ)) (fun t : ℤ => if 0 ≤ t then q t else 0)
        rw [← h]
        congr 1
        funext s
        simp only [Equiv.subRight_apply]
        by_cases hs : 0 < s
        · rw [if_pos hs, if_pos (show (0:ℤ) ≤ s - 1 from by omega)]
        · rw [if_neg hs, if_neg (show ¬ (0:ℤ) ≤ s - 1 from by omega)]
      have hqnz_split : (∑' s : ℤ, if s ≠ 0 then q s else 0)
          = (∑' s : ℤ, if 0 < s then q s else 0) + (∑' s : ℤ, if s < 0 then q s else 0) := by
        rw [← hqpos.tsum_add hqneg]
        congr 1
        funext s
        rcases lt_trichotomy s 0 with h | h | h
        · rw [if_neg (not_lt.mpr (le_of_lt h)), if_pos h, if_pos (ne_of_lt h)]; ring
        · subst h; simp
        · rw [if_pos h, if_neg (not_lt.mpr (le_of_lt h)), if_pos (ne_of_gt h)]; ring
      have hqnz_le : (∑' s : ℤ, if s ≠ 0 then q s else 0) ≤ (∑' s : ℤ, |(s:ℝ)| * q s) := by
        apply Summable.tsum_le_tsum (fun s => ?_) hqnz hq_mom
        by_cases h : s = 0
        · subst h; simp
        · rw [if_pos h]
          have h1 : (1:ℝ) ≤ |(s:ℝ)| := by
            rw [← Int.cast_abs]
            have := Int.one_le_abs h
            exact_mod_cast this
          calc q s = 1 * q s := by ring
            _ ≤ |(s:ℝ)| * q s := mul_le_mul_of_nonneg_right h1 (hq_nonneg s)
  3. The vulnerability of q is bounded below by p (1 - ∑_{s > 0} q(s)) + (1 - p) (1 - ∑_{s < 0} q(s)), which is in turn at least 1 - p ∑ |s| q(s).

    We define a test function g(s) taking p * q(s) when s ≤ 0 and (1 - p) * q(s - 1) when s > 0. Pointwise g(s) ≤ max(p * q(s), (1 - p) * q(s - 1)) by le_max_left and le_max_right, so ∑ g(s) ≤ vulnerability(p, q) by Summable.tsum_le_tsum. Factoring out p and 1 - p (tsum_mul_left) and substituting our sum decompositions yields ∑ g(s) = p (1 - ∑_{s > 0} q(s)) + (1 - p) (1 - ∑_{s < 0} q(s)). Since p > 1 / 2 and ∑_{s ≠ 0} q(s) ≤ ∑ |s| q(s), non-linear arithmetic establishes that this quantity is at least 1 - p ∑ |s| q(s).

    lines 98–132

    uses Summable.tsum_le_tsum, le_max_left, le_max_right, tsum_mul_left, tsum_nonneg

      have hpt : (fun s : ℤ => if s ≤ 0 then p * q s else (1 - p) * q (s - 1))
          = (fun s : ℤ => p * (if s ≤ 0 then q s else 0) + (1 - p) * (if 0 < s then q (s - 1) else 0)) := by
        funext s
        by_cases h : s ≤ 0
        · rw [if_pos h, if_pos h, if_neg (not_lt.mpr h)]; ring
        · rw [if_neg h, if_neg h, if_pos (not_le.mp h)]; ring
      have hsumm_g : Summable (fun s : ℤ => if s ≤ 0 then p * q s else (1 - p) * q (s - 1)) := by
        rw [hpt]
        exact (hqm.mul_left p).add (hqsh.mul_left (1 - p))
      have hsumm_max : Summable (fun s : ℤ => max (p * q s) ((1 - p) * q (s - 1))) := by
        have hrhs : Summable (fun s : ℤ => p * q s + (1 - p) * q (s - 1)) :=
          (hq.mul_left p).add (hqshift.mul_left (1 - p))
        apply Summable.of_nonneg_of_le (fun s => ?_) (fun s => ?_) hrhs
        · have ha : 0 ≤ p * q s := mul_nonneg hp0.le (hq_nonneg s)
          exact le_trans ha (le_max_left _ _)
        · have ha : 0 ≤ p * q s := mul_nonneg hp0.le (hq_nonneg s)
          have hb : 0 ≤ (1 - p) * q (s - 1) := mul_nonneg h1p (hq_nonneg (s - 1))
          exact max_le (le_add_of_nonneg_right hb) (le_add_of_nonneg_left ha)
      have h_g_max : (∑' s : ℤ, if s ≤ 0 then p * q s else (1 - p) * q (s - 1))
          ≤ ∑' s : ℤ, max (p * q s) ((1 - p) * q (s - 1)) := by
        apply Summable.tsum_le_tsum (fun s => ?_) hsumm_g hsumm_max
        by_cases h : s ≤ 0
        · rw [if_pos h]; exact le_max_left _ _
        · rw [if_neg h]; exact le_max_right _ _
      have h_tsum_g : (∑' s : ℤ, if s ≤ 0 then p * q s else (1 - p) * q (s - 1))
          = p * (∑' s : ℤ, if s ≤ 0 then q s else 0) + (1 - p) * (∑' s : ℤ, if 0 < s then q (s - 1) else 0) := by
        rw [hpt, (hqm.mul_left p).tsum_add (hqsh.mul_left (1 - p)), tsum_mul_left, tsum_mul_left]
      have h_g_value : (∑' s : ℤ, if s ≤ 0 then p * q s else (1 - p) * q (s - 1))
          = p * (1 - ∑' s : ℤ, (if 0 < s then q s else 0)) + (1 - p) * (1 - ∑' s : ℤ, (if s < 0 then q s else 0)) := by
        rw [h_tsum_g, hqm_split, hqsh_eq, hqge_split]
      have hPn0 : 0 ≤ (∑' s : ℤ, (if s < 0 then q s else 0)) :=
        tsum_nonneg (fun s => by split_ifs <;> simp [hq_nonneg])
      have hkey : (1 - p * (∑' s : ℤ, |(s:ℝ)| * q s))
          ≤ p * (1 - ∑' s : ℤ, (if 0 < s then q s else 0)) + (1 - p) * (1 - ∑' s : ℤ, (if s < 0 then q s else 0)) := by
        nlinarith [hqnz_split, hqnz_le, hPn0, hp, hp1]
  4. The cost ∑ |s| q(s) must equal the budget c, and the lower bound from the test function holds with equality: p (1 - ∑_{s > 0} q(s)) + (1 - p) (1 - ∑_{s < 0} q(s)) = 1 - p ∑ |s| q(s).

    By biased_bit_cost_vulnerability_initial_segment, the optimal vulnerability on the initial segment is 1 - p * c. Since q achieves this optimum and satisfies ∑ |s| q(s) ≤ c, the chain 1 - p * c ≤ 1 - p ∑ |s| q(s) ≤ ∑ g(s) ≤ vulnerability(p, q) = 1 - p * c collapses to equality at every step. Because p > 0, cancelling p (mul_left_cancel₀) yields ∑ |s| q(s) = c, and the lower bound inequality holds with equality.

    lines 133–149

    uses biased_bit_cost_vulnerability_initial_segment, mul_left_cancel₀

      have h_opt_val : biased_bit_optimal_vulnerability p c = 1 - p * c :=
        (biased_bit_cost_vulnerability_initial_segment p c hp hp1 hc0.le hc).1
      have h_vuln_eq : biased_bit_vulnerability p q = 1 - p * c := by
        rw [hq_opt, h_opt_val]
      have h_vuln_def : biased_bit_vulnerability p q = ∑' s : ℤ, max (p * q s) ((1 - p) * q (s - 1)) := rfl
      have h_chain_le : 1 - p * c ≤ 1 - p * (∑' s : ℤ, |(s : ℝ)| * q s) := by
        nlinarith [hq_cost, hp0]
      have h_chain_eq : 1 - p * (∑' s : ℤ, |(s : ℝ)| * q s) = 1 - p * c := by
        linarith [h_chain_le, hkey, h_g_value, h_g_max, h_vuln_def, h_vuln_eq]
      have h_p_mul : p * (∑' s : ℤ, |(s : ℝ)| * q s) = p * c := by
        linarith [h_chain_eq]
      have h_cost_eq : (∑' s : ℤ, |(s : ℝ)| * q s) = c :=
        mul_left_cancel₀ hp0.ne' h_p_mul
      have h_mid_eq : p * (1 - ∑' s : ℤ, (if 0 < s then q s else 0)) + (1 - p) * (1 - ∑' s : ℤ, (if s < 0 then q s else 0))
          = 1 - p * (∑' s : ℤ, |(s : ℝ)| * q s) := by
        linarith [hkey, h_g_value, h_g_max, h_vuln_def, h_vuln_eq, h_chain_eq]
      have h2p : 0 < 2 * p - 1 := by linarith
  5. The total mass on negative integers is zero (∑_{s < 0} q(s) = 0), and the first absolute moment equals the mass on non-zero integers (∑ |s| q(s) = ∑_{s ≠ 0} q(s)).

    Rearranging algebraically, the difference between the two sides of the equality from the previous step factors as p (∑ |s| q(s) - ∑_{s ≠ 0} q(s)) + (2 * p - 1) ∑_{s < 0} q(s) = 0. Both summands are non-negative because p > 0, ∑_{s ≠ 0} q(s) ≤ ∑ |s| q(s), and 2 * p - 1 > 0 with q ≥ 0. A sum of two non-negative terms being zero forces both summands to vanish, yielding ∑_{s < 0} q(s) = 0 and ∑ |s| q(s) = ∑_{s ≠ 0} q(s).

    lines 150–167

      have h_diff : (p * (1 - ∑' s : ℤ, (if 0 < s then q s else 0)) + (1 - p) * (1 - ∑' s : ℤ, (if s < 0 then q s else 0))) - (1 - p * (∑' s : ℤ, |(s : ℝ)| * q s))
          = p * ((∑' s : ℤ, |(s : ℝ)| * q s) - ((∑' s : ℤ, (if 0 < s then q s else 0)) + (∑' s : ℤ, (if s < 0 then q s else 0)))) + (2 * p - 1) * (∑' s : ℤ, (if s < 0 then q s else 0)) := by ring
      rw [h_mid_eq] at h_diff
      have h_zero : p * ((∑' s : ℤ, |(s : ℝ)| * q s) - ((∑' s : ℤ, (if 0 < s then q s else 0)) + (∑' s : ℤ, (if s < 0 then q s else 0)))) + (2 * p - 1) * (∑' s : ℤ, (if s < 0 then q s else 0)) = 0 := by
        linarith
      have h_le_C : (∑' s : ℤ, (if 0 < s then q s else 0)) + (∑' s : ℤ, (if s < 0 then q s else 0)) ≤ (∑' s : ℤ, |(s : ℝ)| * q s) := by
        rw [← hqnz_split]
        exact hqnz_le
      have h1_nonneg : 0 ≤ p * ((∑' s : ℤ, |(s : ℝ)| * q s) - ((∑' s : ℤ, (if 0 < s then q s else 0)) + (∑' s : ℤ, (if s < 0 then q s else 0)))) := by
        nlinarith
      have h2_nonneg : 0 ≤ (2 * p - 1) * (∑' s : ℤ, (if s < 0 then q s else 0)) := by
        nlinarith [hPn0]
      have h_Pneg_zero : (∑' s : ℤ, (if s < 0 then q s else 0)) = 0 := by
        nlinarith
      have h_C_eq_sum : (∑' s : ℤ, |(s : ℝ)| * q s) = (∑' s : ℤ, (if 0 < s then q s else 0)) + (∑' s : ℤ, (if s < 0 then q s else 0)) := by
        nlinarith
      have h_C_eq_nz : (∑' s : ℤ, |(s : ℝ)| * q s) = (∑' s : ℤ, if s ≠ 0 then q s else 0) := by
        rw [hqnz_split, h_C_eq_sum]
  6. The support of q is contained in {0, 1}, meaning q(s) = 0 for all s ∉ {0, 1}.

    Since q ≥ 0 and ∑_{s < 0} q(s) = 0, hasSum_zero_iff_of_nonneg implies q(s) = 0 for all s < 0. Furthermore, the function f(s) = |s| * q(s) - (if s ≠ 0 then q(s) else 0) is pointwise non-negative and sums to zero (sub_self), so f = 0 identically by hasSum_zero_iff_of_nonneg. For s ≥ 2, this means (s - 1) * q(s) = 0 via abs_of_pos; since s - 1 > 0, we have q(s) = 0. Trichotomy (lt_trichotomy) shows any integer outside {0, 1} is either negative or at least 2, so q(s) = 0 everywhere outside {0, 1}.

    lines 168–228

    uses hasSum_zero_iff_of_nonneg, sub_self, abs_of_pos, lt_trichotomy

      have h_neg : ∀ s < 0, q s = 0 := by
        have h_nonneg_neg : ∀ s : ℤ, 0 ≤ (if s < 0 then q s else 0) := by
          intro s; split_ifs <;> simp [hq_nonneg]
        have h_zero_fun : (fun s : ℤ => if s < 0 then q s else 0) = 0 := by
          have h_has : HasSum (fun s : ℤ => if s < 0 then q s else 0) 0 := by
            have h_sum := hqneg.hasSum
            rwa [h_Pneg_zero] at h_sum
          exact (hasSum_zero_iff_of_nonneg h_nonneg_neg).mp h_has
        intro s hs
        have h_app := congr_fun h_zero_fun s
        simp only [Pi.zero_apply] at h_app
        rw [if_pos hs] at h_app
        exact h_app
      have h_ge2 : ∀ s ≥ 2, q s = 0 := by
        have hf_nonneg : ∀ s : ℤ, 0 ≤ |(s : ℝ)| * q s - (if s ≠ 0 then q s else 0) := by
          intro s
          by_cases hs : s = 0
          · subst hs; simp
          · rw [if_pos hs]
            have h1 : (1 : ℝ) ≤ |(s : ℝ)| := by
              rw [← Int.cast_abs]
              have := Int.one_le_abs hs
              exact_mod_cast this
            have : q s ≤ |(s : ℝ)| * q s := by
              calc q s = 1 * q s := by ring
                _ ≤ |(s : ℝ)| * q s := mul_le_mul_of_nonneg_right h1 (hq_nonneg s)
            linarith
        have hf_summable : Summable (fun s : ℤ => |(s : ℝ)| * q s - (if s ≠ 0 then q s else 0)) :=
          hq_mom.sub hqnz
        have hf_tsum : (∑' s : ℤ, (|(s : ℝ)| * q s - (if s ≠ 0 then q s else 0))) = 0 := by
          rw [hq_mom.tsum_sub hqnz, h_C_eq_nz, sub_self]
        have hf_zero : (fun s : ℤ => |(s : ℝ)| * q s - (if s ≠ 0 then q s else 0)) = 0 := by
          have h_has : HasSum (fun s : ℤ => |(s : ℝ)| * q s - (if s ≠ 0 then q s else 0)) 0 := by
            have h_sum := hf_summable.hasSum
            rwa [hf_tsum] at h_sum
          exact (hasSum_zero_iff_of_nonneg hf_nonneg).mp h_has
        intro s hs
        have h_app := congr_fun hf_zero s
        simp only [Pi.zero_apply] at h_app
        have hs_ne : s ≠ 0 := by omega
        rw [if_pos hs_ne] at h_app
        have hs_abs : |(s : ℝ)| = (s : ℝ) := by
          rw [abs_of_pos]
          exact_mod_cast (by omega : 0 < s)
        rw [hs_abs] at h_app
        have h_mul : ((s : ℝ) - 1) * q s = 0 := by
          linarith [h_app]
        have hs_sub_pos : 0 < (s : ℝ) - 1 := by
          have : (2 : ℝ) ≤ (s : ℝ) := by exact_mod_cast hs
          linarith
        cases mul_eq_zero.mp h_mul with
        | inl h => linarith
        | inr h => exact h
      have h_supp : ∀ s ∉ ({0, 1} : Finset ℤ), q s = 0 := by
        intro s hs
        simp only [Finset.mem_insert, Finset.mem_singleton, not_or] at hs
        rcases lt_trichotomy s 0 with h | rfl | h
        · exact h_neg s h
        · exact False.elim (hs.1 rfl)
        · have : 2 ≤ s := by omega
          exact h_ge2 s this
  7. The probabilities at 0 and 1 are uniquely determined: q(1) = c, q(0) = 1 - c, and q = two_point_mask c.

    Because q vanishes outside {0, 1}, its infinite sums reduce to finite sums over {0, 1} via tsum_eq_sum. The cost equation ∑ |s| q(s) = c simplifies to q(1) = c, and the total probability equation ∑ q(s) = 1 simplifies to q(0) + q(1) = 1, giving q(0) = 1 - c. Comparing q(s) pointwise with two_point_mask c on the cases s = 0, s = 1, and s ∉ {0, 1} completes the proof.

    lines 229–255

    uses tsum_eq_sum

      have h_supp_mom : ∀ s ∉ ({0, 1} : Finset ℤ), |(s : ℝ)| * q s = 0 := by
        intro s hs
        rw [h_supp s hs, mul_zero]
      have h_tsum_mom : (∑' s : ℤ, |(s : ℝ)| * q s) = ∑ s ∈ ({0, 1} : Finset ℤ), |(s : ℝ)| * q s :=
        tsum_eq_sum h_supp_mom
      have h_mom_val : (∑ s ∈ ({0, 1} : Finset ℤ), |(s : ℝ)| * q s) = q 1 := by
        simp
      have h_q1 : q 1 = c := by
        linarith [h_cost_eq, h_tsum_mom, h_mom_val]
      have h_tsum_q : (∑' s : ℤ, q s) = ∑ s ∈ ({0, 1} : Finset ℤ), q s :=
        tsum_eq_sum h_supp
      have h_sum_val : (∑ s ∈ ({0, 1} : Finset ℤ), q s) = q 0 + q 1 := by
        simp
      have h_q0 : q 0 = 1 - c := by
        have h1 : (∑' s : ℤ, q s) = 1 := hq_sum.tsum_eq
        linarith [h1, h_tsum_q, h_sum_val, h_q1]
      funext s
      unfold two_point_mask
      by_cases hs0 : s = 0
      · subst hs0
        simp [h_q0]
      · by_cases hs1 : s = 1
        · subst hs1
          simp [hs0, h_q1]
        · have hs_not : s ∉ ({0, 1} : Finset ℤ) := by
            simp [hs0, hs1]
          simp [hs0, hs1, h_supp s hs_not]
Summable.of_nonneg_of_le
If a function g is pointwise non-negative and bounded above by a summable function f, then g is summable.
Equiv.tsum_eq
Reindexing an infinite sum by an equivalence (bijection) preserves the sum.
Equiv.subRight
The bijection on an additive group given by subtracting a fixed element from the right: x ↦ x - a.
lt_trichotomy
For any two elements in a linear order, exactly one of a < b, a = b, or b < a holds.
Summable.tsum_le_tsum
If f ≤ g pointwise and both functions are summable, then the infinite sum of f is at most the infinite sum of g.
Int.one_le_abs
Every non-zero integer has absolute value at least 1.
mul_le_mul_of_nonneg_right
Multiplying an inequality by a non-negative number on the right preserves the inequality.
le_max_left
Any element is less than or equal to the maximum of itself and another element.
le_max_right
Any element is less than or equal to the maximum of another element and itself.
tsum_mul_left
A constant factor can be factored out of an infinite sum.
tsum_nonneg
The infinite sum of a pointwise non-negative function is non-negative.
biased_bit_cost_vulnerability_initial_segment
On the initial segment c ∈ [0, 1 - p], the optimal vulnerability is 1 - p * c, achieved by the two-point mask.
mul_left_cancel₀
A non-zero factor can be cancelled from the left of a multiplication equality.
hasSum_zero_iff_of_nonneg
For a non-negative function, its infinite sum is zero if and only if the function is identically zero.
sub_self
Subtracting an element from itself yields zero.
abs_of_pos
The absolute value of a strictly positive element equals itself.
tsum_eq_sum
If a function vanishes outside a finite set s, its infinite sum equals the finite sum over s.

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

/-- On the initial segment (0, 1 - p], any optimal additive integer mask is unique and equals two_point_mask c. -/theorem biased_bit_initial_segment_optimizer_unique    (p : ℝ) (hp : 1 / 2 < p) (hp1 : p < 1)    (c : ℝ) (hc0 : 0 < c) (hc : c ≤ 1 - p)    (q : ℤ → ℝ) (hq_nonneg : ∀ s, 0 ≤ q s) (hq_sum : HasSum q 1)    (hq_mom : Summable (fun s : ℤ => |(s : ℝ)| * q s))    (hq_cost : (∑' s : ℤ, |(s : ℝ)| * q s) ≤ c)    (hq_opt : biased_bit_vulnerability p q = biased_bit_optimal_vulnerability p c) :    q = two_point_mask c := by  have hp0 : 0 < p := by linarith  have h1p : 0 ≤ 1 - p := by linarith  have hq : Summable q := hq_sum.summable  have hqshift : Summable (fun s : ℤ => q (s - 1)) :=    hq.comp_injective (fun a b hab => by simpa using hab)  have hqm : Summable (fun s : ℤ => if s ≤ 0 then q s else 0) := by    apply Summable.of_nonneg_of_le (fun s => ?_) (fun s => ?_) hq    · split_ifs <;> simp [hq_nonneg]    · split_ifs with h      · exact le_rfl      · exact hq_nonneg s  have hqpos : Summable (fun s : ℤ => if 0 < s then q s else 0) := by    apply Summable.of_nonneg_of_le (fun s => ?_) (fun s => ?_) hq    · split_ifs <;> simp [hq_nonneg]    · split_ifs with h      · exact le_rfl      · exact hq_nonneg s  have hqneg : Summable (fun s : ℤ => if s < 0 then q s else 0) := by    apply Summable.of_nonneg_of_le (fun s => ?_) (fun s => ?_) hq    · split_ifs <;> simp [hq_nonneg]    · split_ifs with h      · exact le_rfl      · exact hq_nonneg s  have hqge : Summable (fun s : ℤ => if 0 ≤ s then q s else 0) := by    apply Summable.of_nonneg_of_le (fun s => ?_) (fun s => ?_) hq    · split_ifs <;> simp [hq_nonneg]    · split_ifs with h      · exact le_rfl      · exact hq_nonneg s  have hqnz : Summable (fun s : ℤ => if s ≠ 0 then q s else 0) := by    apply Summable.of_nonneg_of_le (fun s => ?_) (fun s => ?_) hq    · split_ifs <;> simp [hq_nonneg]    · split_ifs with h      · exact le_rfl      · exact hq_nonneg s  have hqsh : Summable (fun s : ℤ => if 0 < s then q (s - 1) else 0) := by    apply Summable.of_nonneg_of_le (fun s => ?_) (fun s => ?_) hqshift    · split_ifs <;> simp [hq_nonneg]    · split_ifs with h      · exact le_rfl      · exact hq_nonneg (s - 1)  have hqm_split : (∑' s : ℤ, if s ≤ 0 then q s else 0) = 1 - ∑' s : ℤ, (if 0 < s then q s else 0) := by    have heq : (fun s : ℤ => (if s ≤ 0 then q s else 0) + (if 0 < s then q s else 0)) = q := by      funext s      by_cases h : s ≤ 0      · simp [h, not_lt.mpr h]      · simp [h, not_le.mp h]    have h := hqm.tsum_add hqpos    rw [heq, hq_sum.tsum_eq] at h    linarith  have hqge_split : (∑' s : ℤ, if 0 ≤ s then q s else 0) = 1 - ∑' s : ℤ, (if s < 0 then q s else 0) := by    have heq : (fun s : ℤ => (if 0 ≤ s then q s else 0) + (if s < 0 then q s else 0)) = q := by      funext s      by_cases h : 0 ≤ s      · simp [h, not_lt.mpr h]      · simp [h, not_le.mp h]    have h := hqge.tsum_add hqneg    rw [heq, hq_sum.tsum_eq] at h    linarith  have hqsh_eq : (∑' s : ℤ, if 0 < s then q (s - 1) else 0) = (∑' s : ℤ, if 0 ≤ s then q s else 0) := by    have h := Equiv.tsum_eq (Equiv.subRight (1:ℤ)) (fun t : ℤ => if 0 ≤ t then q t else 0)    rw [← h]    congr 1    funext s    simp only [Equiv.subRight_apply]    by_cases hs : 0 < s    · rw [if_pos hs, if_pos (show (0:ℤ) ≤ s - 1 from by omega)]    · rw [if_neg hs, if_neg (show ¬ (0:ℤ) ≤ s - 1 from by omega)]  have hqnz_split : (∑' s : ℤ, if s ≠ 0 then q s else 0)      = (∑' s : ℤ, if 0 < s then q s else 0) + (∑' s : ℤ, if s < 0 then q s else 0) := by    rw [← hqpos.tsum_add hqneg]    congr 1    funext s    rcases lt_trichotomy s 0 with h | h | h    · rw [if_neg (not_lt.mpr (le_of_lt h)), if_pos h, if_pos (ne_of_lt h)]; ring    · subst h; simp    · rw [if_pos h, if_neg (not_lt.mpr (le_of_lt h)), if_pos (ne_of_gt h)]; ring  have hqnz_le : (∑' s : ℤ, if s ≠ 0 then q s else 0) ≤ (∑' s : ℤ, |(s:ℝ)| * q s) := by    apply Summable.tsum_le_tsum (fun s => ?_) hqnz hq_mom    by_cases h : s = 0    · subst h; simp    · rw [if_pos h]      have h1 : (1:ℝ) ≤ |(s:ℝ)| := by        rw [← Int.cast_abs]        have := Int.one_le_abs h        exact_mod_cast this      calc q s = 1 * q s := by ring        _ ≤ |(s:ℝ)| * q s := mul_le_mul_of_nonneg_right h1 (hq_nonneg s)  have hpt : (fun s : ℤ => if s ≤ 0 then p * q s else (1 - p) * q (s - 1))      = (fun s : ℤ => p * (if s ≤ 0 then q s else 0) + (1 - p) * (if 0 < s then q (s - 1) else 0)) := by    funext s    by_cases h : s ≤ 0    · rw [if_pos h, if_pos h, if_neg (not_lt.mpr h)]; ring    · rw [if_neg h, if_neg h, if_pos (not_le.mp h)]; ring  have hsumm_g : Summable (fun s : ℤ => if s ≤ 0 then p * q s else (1 - p) * q (s - 1)) := by    rw [hpt]    exact (hqm.mul_left p).add (hqsh.mul_left (1 - p))  have hsumm_max : Summable (fun s : ℤ => max (p * q s) ((1 - p) * q (s - 1))) := by    have hrhs : Summable (fun s : ℤ => p * q s + (1 - p) * q (s - 1)) :=      (hq.mul_left p).add (hqshift.mul_left (1 - p))    apply Summable.of_nonneg_of_le (fun s => ?_) (fun s => ?_) hrhs    · have ha : 0 ≤ p * q s := mul_nonneg hp0.le (hq_nonneg s)      exact le_trans ha (le_max_left _ _)    · have ha : 0 ≤ p * q s := mul_nonneg hp0.le (hq_nonneg s)      have hb : 0 ≤ (1 - p) * q (s - 1) := mul_nonneg h1p (hq_nonneg (s - 1))      exact max_le (le_add_of_nonneg_right hb) (le_add_of_nonneg_left ha)  have h_g_max : (∑' s : ℤ, if s ≤ 0 then p * q s else (1 - p) * q (s - 1))      ≤ ∑' s : ℤ, max (p * q s) ((1 - p) * q (s - 1)) := by    apply Summable.tsum_le_tsum (fun s => ?_) hsumm_g hsumm_max    by_cases h : s ≤ 0    · rw [if_pos h]; exact le_max_left _ _    · rw [if_neg h]; exact le_max_right _ _  have h_tsum_g : (∑' s : ℤ, if s ≤ 0 then p * q s else (1 - p) * q (s - 1))      = p * (∑' s : ℤ, if s ≤ 0 then q s else 0) + (1 - p) * (∑' s : ℤ, if 0 < s then q (s - 1) else 0) := by    rw [hpt, (hqm.mul_left p).tsum_add (hqsh.mul_left (1 - p)), tsum_mul_left, tsum_mul_left]  have h_g_value : (∑' s : ℤ, if s ≤ 0 then p * q s else (1 - p) * q (s - 1))      = p * (1 - ∑' s : ℤ, (if 0 < s then q s else 0)) + (1 - p) * (1 - ∑' s : ℤ, (if s < 0 then q s else 0)) := by    rw [h_tsum_g, hqm_split, hqsh_eq, hqge_split]  have hPn0 : 0 ≤ (∑' s : ℤ, (if s < 0 then q s else 0)) :=    tsum_nonneg (fun s => by split_ifs <;> simp [hq_nonneg])  have hkey : (1 - p * (∑' s : ℤ, |(s:ℝ)| * q s))      ≤ p * (1 - ∑' s : ℤ, (if 0 < s then q s else 0)) + (1 - p) * (1 - ∑' s : ℤ, (if s < 0 then q s else 0)) := by    nlinarith [hqnz_split, hqnz_le, hPn0, hp, hp1]  have h_opt_val : biased_bit_optimal_vulnerability p c = 1 - p * c :=    (biased_bit_cost_vulnerability_initial_segment p c hp hp1 hc0.le hc).1  have h_vuln_eq : biased_bit_vulnerability p q = 1 - p * c := by    rw [hq_opt, h_opt_val]  have h_vuln_def : biased_bit_vulnerability p q = ∑' s : ℤ, max (p * q s) ((1 - p) * q (s - 1)) := rfl  have h_chain_le : 1 - p * c ≤ 1 - p * (∑' s : ℤ, |(s : ℝ)| * q s) := by    nlinarith [hq_cost, hp0]  have h_chain_eq : 1 - p * (∑' s : ℤ, |(s : ℝ)| * q s) = 1 - p * c := by    linarith [h_chain_le, hkey, h_g_value, h_g_max, h_vuln_def, h_vuln_eq]  have h_p_mul : p * (∑' s : ℤ, |(s : ℝ)| * q s) = p * c := by    linarith [h_chain_eq]  have h_cost_eq : (∑' s : ℤ, |(s : ℝ)| * q s) = c :=    mul_left_cancel₀ hp0.ne' h_p_mul  have h_mid_eq : p * (1 - ∑' s : ℤ, (if 0 < s then q s else 0)) + (1 - p) * (1 - ∑' s : ℤ, (if s < 0 then q s else 0))      = 1 - p * (∑' s : ℤ, |(s : ℝ)| * q s) := by    linarith [hkey, h_g_value, h_g_max, h_vuln_def, h_vuln_eq, h_chain_eq]  have h2p : 0 < 2 * p - 1 := by linarith  have h_diff : (p * (1 - ∑' s : ℤ, (if 0 < s then q s else 0)) + (1 - p) * (1 - ∑' s : ℤ, (if s < 0 then q s else 0))) - (1 - p * (∑' s : ℤ, |(s : ℝ)| * q s))      = p * ((∑' s : ℤ, |(s : ℝ)| * q s) - ((∑' s : ℤ, (if 0 < s then q s else 0)) + (∑' s : ℤ, (if s < 0 then q s else 0)))) + (2 * p - 1) * (∑' s : ℤ, (if s < 0 then q s else 0)) := by ring  rw [h_mid_eq] at h_diff  have h_zero : p * ((∑' s : ℤ, |(s : ℝ)| * q s) - ((∑' s : ℤ, (if 0 < s then q s else 0)) + (∑' s : ℤ, (if s < 0 then q s else 0)))) + (2 * p - 1) * (∑' s : ℤ, (if s < 0 then q s else 0)) = 0 := by    linarith  have h_le_C : (∑' s : ℤ, (if 0 < s then q s else 0)) + (∑' s : ℤ, (if s < 0 then q s else 0)) ≤ (∑' s : ℤ, |(s : ℝ)| * q s) := by    rw [← hqnz_split]    exact hqnz_le  have h1_nonneg : 0 ≤ p * ((∑' s : ℤ, |(s : ℝ)| * q s) - ((∑' s : ℤ, (if 0 < s then q s else 0)) + (∑' s : ℤ, (if s < 0 then q s else 0)))) := by    nlinarith  have h2_nonneg : 0 ≤ (2 * p - 1) * (∑' s : ℤ, (if s < 0 then q s else 0)) := by    nlinarith [hPn0]  have h_Pneg_zero : (∑' s : ℤ, (if s < 0 then q s else 0)) = 0 := by    nlinarith  have h_C_eq_sum : (∑' s : ℤ, |(s : ℝ)| * q s) = (∑' s : ℤ, (if 0 < s then q s else 0)) + (∑' s : ℤ, (if s < 0 then q s else 0)) := by    nlinarith  have h_C_eq_nz : (∑' s : ℤ, |(s : ℝ)| * q s) = (∑' s : ℤ, if s ≠ 0 then q s else 0) := by    rw [hqnz_split, h_C_eq_sum]  have h_neg : ∀ s < 0, q s = 0 := by    have h_nonneg_neg : ∀ s : ℤ, 0 ≤ (if s < 0 then q s else 0) := by      intro s; split_ifs <;> simp [hq_nonneg]    have h_zero_fun : (fun s : ℤ => if s < 0 then q s else 0) = 0 := by      have h_has : HasSum (fun s : ℤ => if s < 0 then q s else 0) 0 := by        have h_sum := hqneg.hasSum        rwa [h_Pneg_zero] at h_sum      exact (hasSum_zero_iff_of_nonneg h_nonneg_neg).mp h_has    intro s hs    have h_app := congr_fun h_zero_fun s    simp only [Pi.zero_apply] at h_app    rw [if_pos hs] at h_app    exact h_app  have h_ge2 : ∀ s ≥ 2, q s = 0 := by    have hf_nonneg : ∀ s : ℤ, 0 ≤ |(s : ℝ)| * q s - (if s ≠ 0 then q s else 0) := by      intro s      by_cases hs : s = 0      · subst hs; simp      · rw [if_pos hs]        have h1 : (1 : ℝ) ≤ |(s : ℝ)| := by          rw [← Int.cast_abs]          have := Int.one_le_abs hs          exact_mod_cast this        have : q s ≤ |(s : ℝ)| * q s := by          calc q s = 1 * q s := by ring            _ ≤ |(s : ℝ)| * q s := mul_le_mul_of_nonneg_right h1 (hq_nonneg s)        linarith    have hf_summable : Summable (fun s : ℤ => |(s : ℝ)| * q s - (if s ≠ 0 then q s else 0)) :=      hq_mom.sub hqnz    have hf_tsum : (∑' s : ℤ, (|(s : ℝ)| * q s - (if s ≠ 0 then q s else 0))) = 0 := by      rw [hq_mom.tsum_sub hqnz, h_C_eq_nz, sub_self]    have hf_zero : (fun s : ℤ => |(s : ℝ)| * q s - (if s ≠ 0 then q s else 0)) = 0 := by      have h_has : HasSum (fun s : ℤ => |(s : ℝ)| * q s - (if s ≠ 0 then q s else 0)) 0 := by        have h_sum := hf_summable.hasSum        rwa [hf_tsum] at h_sum      exact (hasSum_zero_iff_of_nonneg hf_nonneg).mp h_has    intro s hs    have h_app := congr_fun hf_zero s    simp only [Pi.zero_apply] at h_app    have hs_ne : s ≠ 0 := by omega    rw [if_pos hs_ne] at h_app    have hs_abs : |(s : ℝ)| = (s : ℝ) := by      rw [abs_of_pos]      exact_mod_cast (by omega : 0 < s)    rw [hs_abs] at h_app    have h_mul : ((s : ℝ) - 1) * q s = 0 := by      linarith [h_app]    have hs_sub_pos : 0 < (s : ℝ) - 1 := by      have : (2 : ℝ) ≤ (s : ℝ) := by exact_mod_cast hs      linarith    cases mul_eq_zero.mp h_mul with    | inl h => linarith    | inr h => exact h  have h_supp : ∀ s ∉ ({0, 1} : Finset ℤ), q s = 0 := by    intro s hs    simp only [Finset.mem_insert, Finset.mem_singleton, not_or] at hs    rcases lt_trichotomy s 0 with h | rfl | h    · exact h_neg s h    · exact False.elim (hs.1 rfl)    · have : 2 ≤ s := by omega      exact h_ge2 s this  have h_supp_mom : ∀ s ∉ ({0, 1} : Finset ℤ), |(s : ℝ)| * q s = 0 := by    intro s hs    rw [h_supp s hs, mul_zero]  have h_tsum_mom : (∑' s : ℤ, |(s : ℝ)| * q s) = ∑ s ∈ ({0, 1} : Finset ℤ), |(s : ℝ)| * q s :=    tsum_eq_sum h_supp_mom  have h_mom_val : (∑ s ∈ ({0, 1} : Finset ℤ), |(s : ℝ)| * q s) = q 1 := by    simp  have h_q1 : q 1 = c := by    linarith [h_cost_eq, h_tsum_mom, h_mom_val]  have h_tsum_q : (∑' s : ℤ, q s) = ∑ s ∈ ({0, 1} : Finset ℤ), q s :=    tsum_eq_sum h_supp  have h_sum_val : (∑ s ∈ ({0, 1} : Finset ℤ), q s) = q 0 + q 1 := by    simp  have h_q0 : q 0 = 1 - c := by    have h1 : (∑' s : ℤ, q s) = 1 := hq_sum.tsum_eq    linarith [h1, h_tsum_q, h_sum_val, h_q1]  funext s  unfold two_point_mask  by_cases hs0 : s = 0  · subst hs0    simp [h_q0]  · by_cases hs1 : s = 1    · subst hs1      simp [hs0, h_q1]    · have hs_not : s ∉ ({0, 1} : Finset ℤ) := by        simp [hs0, hs1]      simp [hs0, hs1, h_supp s hs_not]
See it in the graphDiscuss this resultChallenge it