additive_noise_map_rule_and_bayes_vulnerability
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₀.
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.
uses
decision_rule_success_prob_le_vulnerability,exists_map_decision_rulehave 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, ?_⟩
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`.
uses
tsum_congr· intro g hg unfold additive_noise_success_prob additive_noise_bayes_vulnerability exact tsum_congr hg
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`.
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)
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.
uses
le_antisymm,ciSup_le,le_ciSup,Set.finite_rangehave 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
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.
uses
constant_decision_rule_success_probrw [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
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.
/-- 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