AFTD Auto-Formalizing Theoretical Domains

gapped_three_point_vulnerability_ge_one_third

theoremverified

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

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$.

  1. 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.

    lines 3–6

    uses Equiv.summable_iff, Equiv.subRight

      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
  2. 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.

    lines 7–11

    uses Summable.of_nonneg_of_le, le_trans, le_max_left, max_le

      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)])
  3. 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)))$.

    lines 12–14

    uses le_max_left, Summable.tsum_le_tsum

      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
  4. 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.

    lines 15–16

      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)$.

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

/-- 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
See it in the graphDiscuss this resultChallenge it