not_gapped_three_point_optimal_vulnerability_ge_one_third
The statement gapped_three_point_optimal_vulnerability_ge_one_third is false: The statement fails for c < 0 (for instance d = 0, c = -1). For any probability distribution q on ℤ with q(s) ≥ 0, each term |s| * q(s) is non-negative, so ∑' s, |s| * q(s) ≥ 0. Hence when c < 0, the set of probability distributions with expected absolute value at most c is empty. By Real.sInf_empty, sInf ∅ = 0 in ℝ. Thus gapped_three_point_optimal_vulnerability d c = 0 for c < 0, which contradicts 1 / 3 ≤ 0.
Statement
theorem not_gapped_three_point_optimal_vulnerability_ge_one_third : ¬ (∀ (d : ℤ) (c : ℝ), 1 / 3 ≤ gapped_three_point_optimal_vulnerability d c)- Related work
- refutes `gapped_three_point_optimal_vulnerability_ge_one_third`
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- gapped_three_point_optimal_vulnerabilityThe optimal one-guess vulnerability under expected absolute value budget at most c against a secret uniformly distributed on {0, 1, d} is…
- gapped_three_point_vulnerability_ge_one_thirdFor any integer d and any probability distribution q on ℤ (with q(s) ≥ 0 and sum equal to 1), the one-guess vulnerability against a…
- 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),…
The proof, explained
Proof sketch. We argue by contradiction: if the bound 1 / 3 ≤ gapped_three_point_optimal_vulnerability d c held for all d and c, it would hold for d = 0 and c = -1. For any probability distribution q on ℤ, the probabilities q(s) and terms |s| are non-negative, so the expected absolute value ∑' s, |s| * q(s) must be non-negative; hence no distribution can have expectation at most -1. This means the infimum is taken over the empty set, which evaluates to 0 in ℝ under Lean's convention sInf ∅ = 0. Substituting 0 gives 1 / 3 ≤ 0, a contradiction.
Assuming the universal bound holds, we have 1 / 3 ≤ gapped_three_point_optimal_vulnerability 0 (-1).
We argue by contradiction. Suppose that 1 / 3 ≤ gapped_three_point_optimal_vulnerability d c holds for all d ∈ ℤ and c ∈ ℝ. Specializing this assumption to the parameters d = 0 and c = -1 yields 1 / 3 ≤ gapped_three_point_optimal_vulnerability 0 (-1) (hypothesis h1).
intro h have h1 := h 0 (-1)
gapped_three_point_optimal_vulnerability 0 (-1) = 0
By definition, gapped_three_point_optimal_vulnerability 0 (-1) is the infimum of the vulnerability values over all probability distributions q on ℤ whose expected absolute value ∑' s, |s| * q s is at most -1. For any distribution q with non-negative probabilities q s ≥ 0, each term |s| * q s is non-negative by abs_nonneg and mul_nonneg. Therefore, the series sum ∑' s, |s| * q s is non-negative by tsum_nonneg. This contradicts the requirement that the sum is at most -1, so no such distribution exists and the defining set is empty (using Set.mem_empty_iff_false, iff_false, and linear arithmetic). Finally, rewritng the defining set to ∅, Real.sInf_empty establishes that the infimum of the empty set in ℝ is 0.
uses
Set.mem_empty_iff_false,iff_false,mul_nonneg,abs_nonneg,tsum_nonneg,Real.sInf_emptyhave h2 : gapped_three_point_optimal_vulnerability 0 (-1) = 0 := by unfold gapped_three_point_optimal_vulnerability have h_empty : { gapped_three_point_vulnerability 0 q | (q : ℤ → ℝ) (_ : ∀ s, 0 ≤ q s) (_ : HasSum q 1) (_ : Summable (fun s : ℤ => |(s : ℝ)| * q s)) (_ : (∑' s : ℤ, |(s : ℝ)| * q s) ≤ -1) } = ∅ := by ext x simp only [Set.mem_empty_iff_false, iff_false] rintro ⟨q, hq_nonneg, hq_sum, hq_abs_sum, hq_le, rfl⟩ have h_nonneg_terms : ∀ s : ℤ, 0 ≤ |(s : ℝ)| * q s := fun s => mul_nonneg (abs_nonneg _) (hq_nonneg s) have h_tsum_nonneg : 0 ≤ ∑' s : ℤ, |(s : ℝ)| * q s := tsum_nonneg h_nonneg_terms linarith rw [h_empty] exact Real.sInf_empty
The specialized inequality yields a contradiction (False).
Substituting gapped_three_point_optimal_vulnerability 0 (-1) = 0 into hypothesis h1 yields 1 / 3 ≤ 0. Numerical computation (norm_num) evaluates this false inequality to False, closing the proof.
rw [h2] at h1 norm_num at h1
Set.mem_empty_iff_false- An element belongs to the empty set if and only if false, so no element belongs to ∅.
iff_false- An equivalence p ↔ False is the same as ¬p.
mul_nonneg- The product of two non-negative numbers is non-negative.
abs_nonneg- The absolute value of any number is non-negative.
tsum_nonneg- The sum of a series whose terms are all non-negative is non-negative.
Real.sInf_empty- In ℝ, the infimum of the empty set is defined to be 0.
- In standard mathematics, the infimum of the empty set in ℝ is either undefined or +∞ in the extended real numbers. In Mathlib, functions on conditionally complete lattices are made total, so sInf ∅ is defined to be 0 for the real numbers (Real.sInf_empty). The counterexample relies on this convention: when c < 0, no distribution satisfies the expectation constraint, so the infimum over the empty set evaluates to 0 rather than +∞.
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.
theorem not_gapped_three_point_optimal_vulnerability_ge_one_third : ¬ (∀ (d : ℤ) (c : ℝ), 1 / 3 ≤ gapped_three_point_optimal_vulnerability d c) := by intro h have h1 := h 0 (-1) have h2 : gapped_three_point_optimal_vulnerability 0 (-1) = 0 := by unfold gapped_three_point_optimal_vulnerability have h_empty : { gapped_three_point_vulnerability 0 q | (q : ℤ → ℝ) (_ : ∀ s, 0 ≤ q s) (_ : HasSum q 1) (_ : Summable (fun s : ℤ => |(s : ℝ)| * q s)) (_ : (∑' s : ℤ, |(s : ℝ)| * q s) ≤ -1) } = ∅ := by ext x simp only [Set.mem_empty_iff_false, iff_false] rintro ⟨q, hq_nonneg, hq_sum, hq_abs_sum, hq_le, rfl⟩ have h_nonneg_terms : ∀ s : ℤ, 0 ≤ |(s : ℝ)| * q s := fun s => mul_nonneg (abs_nonneg _) (hq_nonneg s) have h_tsum_nonneg : 0 ≤ ∑' s : ℤ, |(s : ℝ)| * q s := tsum_nonneg h_nonneg_terms linarith rw [h_empty] exact Real.sInf_empty rw [h2] at h1 norm_num at h1