exists_map_decision_rule
For any nonempty finite alphabet Fin m, prior p, and mask q on ℤ, there exists a decision rule g : ℤ → Fin m that attains the pointwise supremum p(g(s)) * q(s - g(s)) = ⨆ x, p(x) * q(s - x) for every integer observation s.
Statement
lemma exists_map_decision_rule (m : ℕ) [NeZero m] (p : Fin m → ℝ) (q : ℤ → ℝ) : ∃ g : ℤ → Fin m, ∀ s : ℤ, p (g s) * q (s - g s) = ⨆ x : Fin m, p x * q (s - x)- 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- Used by 1
- additive_noise_map_rule_and_bayes_vulnerabilityFor a secret with distribution p on Fin m and independent additive noise Y with distribution q on ℤ, the optimal average one-guess success…
Read back from the Lean
Given a natural number $m$ with $m \neq 0$ (via [NeZero m]), a function $p : \text{Fin } m \to \mathbb{R}$, and a function $q : \mathbb{Z} \to \mathbb{R}$, there exists a function $g : \mathbb{Z} \to \text{Fin } m$ such that for every integer $s : \mathbb{Z}$, the value $p(g(s)) \cdot q(s - g(s))$ equals the supremum (over $x : \text{Fin } m$) of $p(x) \cdot q(s - x)$, where $g(s)$ and $x$ are coerced from $\text{Fin } m$ to $\mathbb{Z}$.
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
/-- Existence of a MAP decision rule achieving the pointwise maximum. -/ lemma exists_map_decision_rule (m : ℕ) [NeZero m] (p : Fin m → ℝ) (q : ℤ → ℝ) : ∃ g : ℤ → Fin m, ∀ s : ℤ, p (g s) * q (s - g s) = ⨆ x : Fin m, p x * q (s - x) := by have h (s : ℤ) : ∃ x : Fin m, p x * q (s - x) = ⨆ x : Fin m, p x * q (s - x) := exists_eq_ciSup_of_finite choose g hg using h exact ⟨g, hg⟩