gapped_three_point_vulnerability_ge_one_third
For any integer d and any probability distribution q on ℤ (with q(s) ≥ 0 and sum equal to 1), the one-guess vulnerability against a uniform secret on {0, 1, d} is at least 1/3.
Statement
theorem gapped_three_point_vulnerability_ge_one_third (d : ℤ) (q : ℤ → ℝ) (hq_nonneg : ∀ s, 0 ≤ q s) (hq_sum : HasSum q 1) : 1 / 3 ≤ gapped_three_point_vulnerability d q- Source
- arXiv:2611.16066, Proposition 3.1
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- gapped_three_point_vulnerabilityThe one-guess vulnerability of an additive integer mask q against a secret uniformly distributed on {0, 1, d} is (1/3) ∑_{s ∈ ℤ} max(q(s),…
- Used by 1
- not_gapped_three_point_optimal_vulnerability_ge_one_thirdThe statement
gapped_three_point_optimal_vulnerability_ge_one_thirdis false: The statement fails for c < 0 (for instance d = 0, c =…
- not_gapped_three_point_optimal_vulnerability_ge_one_thirdThe statement
Read back from the Lean
For any integer $d$ and any function $q : \mathbb{Z} \to \mathbb{R}$, if $q(s) \ge 0$ for all $s \in \mathbb{Z}$ and the sum of $q$ over $\mathbb{Z}$ converges to $1$ ($\operatorname{HasSum} q\ 1$), then $1/3 \le \operatorname{gapped\_three\_point\_vulnerability}(d, 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 proof establishes that the one-guess vulnerability is at least $1/3$ by showing that the infinite sum of the optimal guess probabilities $\max(q(s), q(s - 1), q(s - d))$ is at least $1$. Pointwise, $q(s)$ is bounded above by this maximum, and because both $q$ and the maximum are summable, summing over all $s \in \mathbb{Z}$ preserves the inequality. Since $q$ is a probability distribution summing to $1$, the sum of the maxima is at least $1$, which implies that the vulnerability—defined as $1/3$ of this sum—is at least $1/3$.
The shifted distributions $s \mapsto q(s - 1)$ and $s \mapsto q(s - d)$, as well as their sum $s \mapsto q(s) + q(s - 1) + q(s - d)$, are summable over $\mathbb{Z}$.
Since $q$ has sum $1$, it is summable. Shifting the index by subtracting $1$ or $d$ is a bijection on $\mathbb{Z}$ (via Equiv.subRight), so Equiv.summable_iff implies the shifted sequences are also summable. The pointwise sum of three summable functions is summable.
uses
Equiv.summable_iff,Equiv.subRighthave hq : Summable q := hq_sum.summable have hq1 : Summable (fun s => q (s - 1)) := (Equiv.summable_iff (Equiv.subRight 1)).2 hq have hqd : Summable (fun s => q (s - d)) := (Equiv.summable_iff (Equiv.subRight d)).2 hq have hsum : Summable (fun s => q s + q (s - 1) + q (s - d)) := (hq.add hq1).add hqd
The pointwise maximum $s \mapsto \max(q(s), \max(q(s - 1), q(s - d)))$ is summable over $\mathbb{Z}$.
By the comparison test (Summable.of_nonneg_of_le), it suffices to show that the maximum is non-negative and bounded above by $q(s) + q(s - 1) + q(s - d)$. Non-negativity holds by le_trans and le_max_left because $0 \le q(s) \le \max(q(s), \dots)$. The upper bound holds via max_le because each individual term $q(s)$, $q(s - 1)$, and $q(s - d)$ is non-negative and therefore bounded above by their sum.
uses
Summable.of_nonneg_of_le,le_trans,le_max_left,max_lehave h_max_summable : Summable (fun s => max (q s) (max (q (s - 1)) (q (s - d)))) := by refine Summable.of_nonneg_of_le (fun s => ?_) (fun s => ?_) hsum · exact le_trans (hq_nonneg s) (le_max_left (q s) _) · refine max_le (by linarith [hq_nonneg (s - 1), hq_nonneg (s - d)]) ?_ exact max_le (by linarith [hq_nonneg s, hq_nonneg (s - d)]) (by linarith [hq_nonneg s, hq_nonneg (s - 1)])
The infinite sum of the pointwise maximum is at least $1$.
For every $s$, $q(s) \le \max(q(s), \max(q(s - 1), q(s - d)))$ by le_max_left. Because both $q$ and the maximum are summable, summing this inequality over all $s \in \mathbb{Z}$ preserves the inequality (Summable.tsum_le_tsum). Since the sum of $q$ is $1$, this gives $1 \le \sum_{s \in \mathbb{Z}} \max(q(s), \max(q(s - 1), q(s - d)))$.
uses
le_max_left,Summable.tsum_le_tsumhave h_le : ∀ s, q s ≤ max (q s) (max (q (s - 1)) (q (s - d))) := fun s => le_max_left (q s) _ have h_tsum_le := Summable.tsum_le_tsum h_le hq h_max_summable rw [hq_sum.tsum_eq] at h_tsum_le
The one-guess vulnerability against a uniform secret on $\{0, 1, d\}$ is at least $1/3$.
Unfolding the definition of gapped_three_point_vulnerability as $(1/3) \sum_{s \in \mathbb{Z}} \max(q(s), \max(q(s - 1), q(s - d)))$, multiplying both sides of the inequality $1 \le \sum_{s \in \mathbb{Z}} \dots$ by $1/3$ gives the desired lower bound.
unfold gapped_three_point_vulnerability nlinarith
Equiv.summable_iff- Precomposing a function with an equivalence (bijection) of the index set preserves summability: $\sum f(e(x))$ converges if and only if $\sum f(y)$ converges.
Equiv.subRight- Right subtraction by a fixed element $c$ (the map $x \mapsto x - c$) is a bijection on any additive group.
Summable.of_nonneg_of_le- Comparison test: if $0 \le g(x) \le f(x)$ for all $x$ and $\sum f(x)$ converges, then $\sum g(x)$ converges.
le_trans- Transitivity of inequality: if $a \le b$ and $b \le c$, then $a \le c$.
le_max_left- A value is bounded by its maximum with another value: $a \le \max(a, b)$.
max_le- If both $a \le c$ and $b \le c$, then $\max(a, b) \le c$.
Summable.tsum_le_tsum- Pointwise inequality preserves infinite sums: if $f(x) \le g(x)$ for all $x$ and both series converge, then $\sum f(x) \le \sum g(x)$.
- On paper, the summability of the pointwise maximum is often taken for granted for probability distributions; Lean requires establishing it formally by bounding the maximum by the sum of three shifted distributions.
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.
/-- Vulnerability against uniform secret on {0, 1, d} is at least the prior baseline 1/3 -/theorem gapped_three_point_vulnerability_ge_one_third (d : ℤ) (q : ℤ → ℝ) (hq_nonneg : ∀ s, 0 ≤ q s) (hq_sum : HasSum q 1) : 1 / 3 ≤ gapped_three_point_vulnerability d q := by have hq : Summable q := hq_sum.summable have hq1 : Summable (fun s => q (s - 1)) := (Equiv.summable_iff (Equiv.subRight 1)).2 hq have hqd : Summable (fun s => q (s - d)) := (Equiv.summable_iff (Equiv.subRight d)).2 hq have hsum : Summable (fun s => q s + q (s - 1) + q (s - d)) := (hq.add hq1).add hqd have h_max_summable : Summable (fun s => max (q s) (max (q (s - 1)) (q (s - d)))) := by refine Summable.of_nonneg_of_le (fun s => ?_) (fun s => ?_) hsum · exact le_trans (hq_nonneg s) (le_max_left (q s) _) · refine max_le (by linarith [hq_nonneg (s - 1), hq_nonneg (s - d)]) ?_ exact max_le (by linarith [hq_nonneg s, hq_nonneg (s - d)]) (by linarith [hq_nonneg s, hq_nonneg (s - 1)]) have h_le : ∀ s, q s ≤ max (q s) (max (q (s - 1)) (q (s - d))) := fun s => le_max_left (q s) _ have h_tsum_le := Summable.tsum_le_tsum h_le hq h_max_summable rw [hq_sum.tsum_eq] at h_tsum_le unfold gapped_three_point_vulnerability nlinarith