AFTD Auto-Formalizing Theoretical Domains

additive_noise_map_rule_and_bayes_vulnerability

theoremverifiedformalization

For a secret with distribution p on Fin m and independent additive noise Y with distribution q on ℤ, the optimal average one-guess success probability for observation S = X + Y is V(X | S) = ∑_{s ∈ ℤ} max_x p(x) q(s - x), which upper bounds any decision rule g, is attained by any decision rule satisfying the MAP rule p(g(s)) q(s - g(s)) = ⨆ x, p(x) q(s - x) (at least one of which exists), and satisfies V(X | S) ≥ V(X) = max_x p(x).

Statement

theorem additive_noise_map_rule_and_bayes_vulnerability (m : ℕ) [NeZero m] (p : Fin m → ℝ) (q : ℤ → ℝ)
    (hp_nonneg : ∀ x, 0 ≤ p x) (hp_sum : ∑ x, p x = 1)
    (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) ∧
    (∀ g : ℤ → Fin m, (∀ s : ℤ, p (g s) * q (s - g s) = ⨆ x : Fin m, p x * q (s - x)) →
      additive_noise_success_prob m p q g = additive_noise_bayes_vulnerability m p q) ∧
    (∃ g : ℤ → Fin m, ∀ s : ℤ, p (g s) * q (s - g s) = ⨆ x : Fin m, p x * q (s - x)) ∧
    prior_bayes_vulnerability m p ≤ additive_noise_bayes_vulnerability m p q
Formalizes
arXiv:2611.16066 Proposition 3.1 -- Optimal Additive Integer Masks for One-Guess Vulnerability under an Absolute-Moment Budget
Verified
16 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • prior_bayes_vulnerabilityThe prior Bayes vulnerability V(X) of a secret X taking values in Fin m with probability mass function p is the supremum of p x over all x…
  • 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…
  • 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…
  • constant_decision_rule_success_probFor any secret distribution p on Fin m and probability distribution q on ℤ with sum 1, the constant decision rule guessing x₀ for all…
  • exists_map_decision_ruleFor any nonempty finite alphabet Fin m, prior p, and mask q on ℤ, there exists a decision rule g : ℤ → Fin m that attains the pointwise…
  • decision_rule_success_prob_le_vulnerabilityFor any nonempty alphabet Fin m, nonnegative prior p, probability distribution q on ℤ, and decision rule g : ℤ → Fin m, the success…

Read back from the Lean

Let $m$ be a non-zero natural number ($m \neq 0$). Let $p : \text{Fin } m \to \mathbb{R}$ be a probability distribution on $\text{Fin } m$ (satisfying $0 \le p(x)$ for all $x$ and $\sum_{x} p(x) = 1$), and let $q : \mathbb{Z} \to \mathbb{R}$ be a probability distribution on $\mathbb{Z}$ (satisfying $0 \le q(s)$ for all $s$ and having sum $\sum_{s \in \mathbb{Z}} q(s) = 1$). Then the following four statements hold simultaneously: 1. For every decision rule $g : \mathbb{Z} \to \text{Fin } m$, the success probability under additive noise additive_noise_success_prob m p q g is less than or equal to the additive noise Bayes vulnerability additive_noise_bayes_vulnerability m p q. 2. For every decision rule $g : \mathbb{Z} \to \text{Fin } m$, if $g$ satisfies the maximum a posteriori (MAP) condition—namely, for all $s \in \mathbb{Z}$, $p(g(s)) \cdot q(s - g(s)) = \sup_{x \in \text{Fin } m} (p(x) \cdot q(s - x))$—then the success probability under $g$ achieves the additive noise Bayes vulnerability (additive_noise_success_prob m p q g = additive_noise_bayes_vulnerability m p q). 3. There exists a decision rule $g : \mathbb{Z} \to \text{Fin } m$ that satisfies the MAP condition for all $s \in \mathbb{Z}$ (i.e., $p(g(s)) \cdot q(s - g(s)) = \sup_{x \in \text{Fin } m} (p(x) \cdot q(s - x))$). 4. The prior Bayes vulnerability prior_bayes_vulnerability m p is less than or equal to the additive noise Bayes vulnerability 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.

The proof, explained

The theorem establishes four properties: the Bayes vulnerability is an upper bound on the success probability of any decision rule, and a MAP decision rule exists, both by prior lemmas. Any MAP decision rule attains the Bayes vulnerability bound because its success probability and the Bayes vulnerability have termwise identical series representations. Finally, the prior Bayes vulnerability equals the maximum prior probability p(x₀), which is bounded above by the posterior Bayes vulnerability by testing the constant decision rule that always predicts x₀.

  1. Any decision rule achieves success probability at most the Bayes vulnerability, and a MAP decision rule exists; this reduces the theorem to the two remaining claims.

    We invoke `decision_rule_success_prob_le_vulnerability` to establish that for any decision rule g, the success probability under additive noise is bounded above by the Bayes vulnerability ∑_{s ∈ ℤ} ⨆ x, p(x) q(s - x). Using this bound and the existence of a MAP decision rule from `exists_map_decision_rule`, the 4-part conjunction reduces to verifying two remaining properties: that any MAP rule achieves the Bayes vulnerability, and that the Bayes vulnerability is bounded below by the prior vulnerability.

    lines 10–12

    uses decision_rule_success_prob_le_vulnerability, exists_map_decision_rule

      have h1 : ∀ g : ℤ → Fin m, additive_noise_success_prob m p q g ≤ additive_noise_bayes_vulnerability m p q :=
        fun g => decision_rule_success_prob_le_vulnerability m p q hp_nonneg hq_nonneg hq_sum g
      refine ⟨h1, ?_, exists_map_decision_rule m p q, ?_⟩
  2. Any decision rule satisfying the MAP condition achieves the Bayes vulnerability.

    Let g be any decision rule satisfying the MAP rule condition p(g(s)) q(s - g(s)) = ⨆ x, p(x) q(s - x) for every observation s. Unfolding the definitions of `additive_noise_success_prob` and `additive_noise_bayes_vulnerability`, both quantities are infinite series over s ∈ ℤ. Because the summands are identical for each s by assumption, the two series sums are equal by `tsum_congr`.

    lines 13–15

    uses tsum_congr

      · intro g hg
        unfold additive_noise_success_prob additive_noise_bayes_vulnerability
        exact tsum_congr hg
  3. There exists a secret state x₀ that maximizes the prior probability distribution p.

    Since the secret alphabet Fin m is nonempty (from m ≠ 0) and finite, the probability function p attains its maximum on the universal finset by `Finset.exists_max_image`. We let x₀ be this maximizing element, so that p(x) ≤ p(x₀) for all x ∈ Fin m by `Finset.mem_univ`.

    lines 16–17

    uses Finset.exists_max_image, Finset.univ_nonempty, Finset.mem_univ

      · obtain ⟨x₀, -, hx₀'⟩ := Finset.exists_max_image (Finset.univ : Finset (Fin m)) p Finset.univ_nonempty
        have hx₀ : ∀ x, p x ≤ p x₀ := fun x => hx₀' x (Finset.mem_univ x)
  4. The prior Bayes vulnerability equals the maximal prior probability p(x₀).

    By definition, the prior Bayes vulnerability is ⨆ x, p(x). To prove this supremum equals p(x₀), we use `le_antisymm`: the upper bound ⨆ x, p(x) ≤ p(x₀) holds by `ciSup_le` because p(x) ≤ p(x₀) for all x; the lower bound p(x₀) ≤ ⨆ x, p(x) holds by `le_ciSup` because the range of p on the finite domain Fin m is finite (`Set.finite_range`) and hence bounded above.

    lines 18–25

    uses le_antisymm, ciSup_le, le_ciSup, Set.finite_range

        have hsup : prior_bayes_vulnerability m p = p x₀ := by
          unfold prior_bayes_vulnerability
          apply le_antisymm
          · apply ciSup_le
            intro x
            exact hx₀ x
          · apply le_ciSup
            exact (Set.finite_range p).bddAbove
  5. The prior Bayes vulnerability is at most the Bayes vulnerability under additive noise.

    Rewriting the prior vulnerability as p(x₀), we consider the constant decision rule that predicts x₀ for every observation s. By `constant_decision_rule_success_prob`, the success probability of this constant rule is exactly p(x₀). Since every decision rule has success probability bounded above by the Bayes vulnerability, this yields p(x₀) ≤ additive_noise_bayes_vulnerability.

    lines 26–28

    uses constant_decision_rule_success_prob

        rw [hsup]
        have hconst := h1 (fun _ => x₀)
        rwa [constant_decision_rule_success_prob m p q hq_sum x₀] at hconst
decision_rule_success_prob_le_vulnerability
For any decision rule g, the success probability under additive noise is bounded above by the Bayes vulnerability.
exists_map_decision_rule
There exists a decision rule satisfying the MAP condition for every observation.
tsum_congr
If two functions are pointwise equal, their infinite sums are equal.
Finset.exists_max_image
A function on a nonempty finite set attains its maximum value at some element.
Finset.univ_nonempty
The universal finset of a nonempty finite type is nonempty.
Finset.mem_univ
Every element of a finite type belongs to its universal finset.
le_antisymm
In a partial order, if a ≤ b and b ≤ a, then a = b.
ciSup_le
If every element f(x) is bounded above by c, then ⨆ x, f(x) ≤ c.
le_ciSup
If the range of f is bounded above, then f(c) ≤ ⨆ x, f(x) for each c.
Set.finite_range
The range of a function defined on a finite domain is finite.
constant_decision_rule_success_prob
The success probability of a constant decision rule predicting x₀ is p(x₀).

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

/-- MAP rule optimality and Bayes vulnerability bound under additive integer noise (Proposition 3.1). -/theorem additive_noise_map_rule_and_bayes_vulnerability (m : ℕ) [NeZero m] (p : Fin m → ℝ) (q : ℤ → ℝ)    (hp_nonneg : ∀ x, 0 ≤ p x) (hp_sum : ∑ x, p x = 1)    (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) ∧    (∀ g : ℤ → Fin m, (∀ s : ℤ, p (g s) * q (s - g s) = ⨆ x : Fin m, p x * q (s - x)) →      additive_noise_success_prob m p q g = additive_noise_bayes_vulnerability m p q) ∧    (∃ g : ℤ → Fin m, ∀ s : ℤ, p (g s) * q (s - g s) = ⨆ x : Fin m, p x * q (s - x)) ∧    prior_bayes_vulnerability m p ≤ additive_noise_bayes_vulnerability m p q := by  have h1 : ∀ g : ℤ → Fin m, additive_noise_success_prob m p q g ≤ additive_noise_bayes_vulnerability m p q :=    fun g => decision_rule_success_prob_le_vulnerability m p q hp_nonneg hq_nonneg hq_sum g  refine ⟨h1, ?_, exists_map_decision_rule m p q, ?_⟩  · intro g hg    unfold additive_noise_success_prob additive_noise_bayes_vulnerability    exact tsum_congr hg  · obtain ⟨x₀, -, hx₀'⟩ := Finset.exists_max_image (Finset.univ : Finset (Fin m)) p Finset.univ_nonempty    have hx₀ : ∀ x, p x ≤ p x₀ := fun x => hx₀' x (Finset.mem_univ x)    have hsup : prior_bayes_vulnerability m p = p x₀ := by      unfold prior_bayes_vulnerability      apply le_antisymm      · apply ciSup_le        intro x        exact hx₀ x      · apply le_ciSup        exact (Set.finite_range p).bddAbove    rw [hsup]    have hconst := h1 (fun _ => x₀)    rwa [constant_decision_rule_success_prob m p q hq_sum x₀] at hconst
See it in the graphDiscuss this resultChallenge it