AFTD Auto-Formalizing Theoretical Domains

decision_rule_success_prob_le_vulnerability

lemmaverified

For any nonempty alphabet Fin m, nonnegative prior p, probability distribution q on ℤ, and decision rule g : ℤ → Fin m, the success probability of g is at most the posterior Bayes vulnerability.

Statement

lemma decision_rule_success_prob_le_vulnerability (m : ℕ) [NeZero m] (p : Fin m → ℝ) (q : ℤ → ℝ) (hp_nonneg : ∀ x, 0 ≤ p x) (hq_nonneg : ∀ s, 0 ≤ q s) (hq_sum : HasSum q 1) (g : ℤ → Fin m) : additive_noise_success_prob m p q g ≤ additive_noise_bayes_vulnerability m p q
Source
arXiv:2611.16066 Proposition 3.1 -- Optimal Additive Integer Masks for One-Guess Vulnerability under an Absolute-Moment Budget
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • additive_noise_success_probThe average one-guess success probability of a decision rule g : ℤ → Fin m for a secret with prior p on Fin m under additive noise with…
  • additive_noise_bayes_vulnerabilityThe Bayes vulnerability V(X | S) of a secret X on Fin m with prior p observed under additive noise S = X + Y with integer mask…
Used by 1

Read back from the Lean

For any positive natural number $m$ (with NeZero m), functions $p : \text{Fin } m \to \mathbb{R}$ and $q : \mathbb{Z} \to \mathbb{R}$, and function $g : \mathbb{Z} \to \text{Fin } m$, if $p(x) \ge 0$ for all $x \in \text{Fin } m$, $q(s) \ge 0$ for all $s \in \mathbb{Z}$, and the infinite sum of $q$ over $\mathbb{Z}$ converges to $1$ (HasSum q 1), then the additive noise success probability with decision rule $g$ is less than or equal to the additive noise Bayes vulnerability: $$\text{additive\_noise\_success\_prob } m\ p\ q\ g \le \text{additive\_noise\_bayes\_vulnerability } m\ p\ q$$

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

Lean source view module on GitHub

/-- Every decision rule has success probability bounded by the Bayes vulnerability. -/
lemma decision_rule_success_prob_le_vulnerability (m : ℕ) [NeZero m] (p : Fin m → ℝ) (q : ℤ → ℝ) (hp_nonneg : ∀ x, 0 ≤ p x) (hq_nonneg : ∀ s, 0 ≤ q s) (hq_sum : HasSum q 1) (g : ℤ → Fin m) : additive_noise_success_prob m p q g ≤ additive_noise_bayes_vulnerability m p q := by
  unfold additive_noise_success_prob additive_noise_bayes_vulnerability
  have hqsumm : ∀ c : ℤ, Summable (fun s : ℤ => q (s - c)) := by
    intro c
    have h := Summable.comp_injective hq_sum.summable (i := fun s : ℤ => s - c)
      (fun a b hab => by simpa using hab)
    exact h
  have hfinsumm : Summable (fun s : ℤ => ∑ x : Fin m, p x * q (s - ↑x)) := by
    refine summable_sum (fun x _ => ?_)
    exact Summable.mul_left _ (hqsumm x)
  have hb_nonneg : ∀ s, 0 ≤ ⨆ x : Fin m, p x * q (s - ↑x) := by
    intro s
    exact le_trans (mul_nonneg (hp_nonneg default) (hq_nonneg (s - ↑(default : Fin m))))
      (Finite.le_ciSup (fun x : Fin m => p x * q (s - ↑x)) default)
  have hsup_le_sum : ∀ s, (⨆ x : Fin m, p x * q (s - ↑x)) ≤ ∑ x : Fin m, p x * q (s - ↑x) := by
    intro s
    refine ciSup_le (fun x => ?_)
    simpa using Finset.single_le_sum (f := fun x : Fin m => p x * q (s - ↑x))
      (fun i _ => mul_nonneg (hp_nonneg i) (hq_nonneg _)) (Finset.mem_univ x)
  have hsup_summ : Summable (fun s : ℤ => ⨆ x : Fin m, p x * q (s - ↑x)) :=
    Summable.of_nonneg_of_le hb_nonneg hsup_le_sum hfinsumm
  have hg_summ : Summable (fun s : ℤ => p (g s) * q (s - ↑(g s))) :=
    Summable.of_nonneg_of_le (fun s => mul_nonneg (hp_nonneg _) (hq_nonneg _))
      (fun s => Finite.le_ciSup (fun x : Fin m => p x * q (s - ↑x)) (g s)) hsup_summ
  exact Summable.tsum_le_tsum
    (fun s => Finite.le_ciSup (fun x : Fin m => p x * q (s - ↑x)) (g s)) hg_summ hsup_summ
See it in the graphDiscuss this resultChallenge it