AFTD Auto-Formalizing Theoretical Domains

not_fair_binomial_anticoncentration_bound

theoremverifiedoriginal

The statement fair_binomial_anticoncentration_bound is false: The statement is false for small α. Take n = 2, α = 1/10, and X the identity on the binomial space Bin(2, 1/2). The interval |X - 1| ≤ (1/10)√2 contains the integer 1, whose binomial probability is C(2,1)/2^2 = 1/2. But the claimed right-hand side is 2e(1/10)/π < 1/5, since e < 3 and π > 3. Thus 1/2 ≤ 2e/(10π) fails.

Statement

open MeasureTheory ProbabilityTheory
open scoped unitInterval
theorem not_fair_binomial_anticoncentration_bound : ¬ (∀ {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ]
    (n : ℕ) (hn : 1 ≤ n) (X : Ω → ℕ)
    (hX : HasLaw X (binomial n ⟨1/2, by norm_num⟩) μ)
    (α : ℝ) (hα_pos : 0 < α), μ.real {ω | |(X ω : ℝ) - (n : ℝ) / 2| ≤ α * Real.sqrt (n : ℝ)} ≤
      2 * Real.exp 1 * α / Real.pi)
Related work
refutes `fair_binomial_anticoncentration_bound`
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

The proof refutes the claimed anticoncentration bound by constructing an explicit counterexample with n = 2, α = 1/10, and a fair coin p = 1/2. On the binomial space Bin(2, 1/2), the interval |X - 1| ≤ (1/10)√2 contains only the single integer 1, whose probability is C(2, 1)/2² = 1/2. However, using the estimates e < 3 and π > 3, the claimed upper bound 2e(1/10)/π is strictly less than 1/5. This forces 1/2 ≤ 1/5, a contradiction.

  1. The parameter p = 1/2 belongs to the unit interval; assuming the anticoncentration bound, we set up a candidate counterexample with n = 2 on Ω = ULift ℕ with pushforward measure μ and random variable X = ULift.down.

    In both the theorem statement (line 5) and the construction (line 9), `norm_num` verifies that 1/2 ∈ [0, 1]. We proceed by contradiction, introducing the universal anticoncentration bound (`h`). Because the theorem quantifies over sample spaces `Ω` in an arbitrary universe `Type*`, we define the probability space on `ULift ℕ` with pushforward measure `μ = (binomial 2 p).map ULift.up` and set `X = ULift.down`.

    lines 5–11

        (hX : HasLaw X (binomial n ⟨1/2, by norm_num⟩) μ)
        (α : ℝ) (hα_pos : 0 < α), μ.real {ω | |(X ω : ℝ) - (n : ℝ) / 2| ≤ α * Real.sqrt (n : ℝ)} ≤
          2 * Real.exp 1 * α / Real.pi) := by
      intro h
      let p : unitInterval := ⟨1/2, by norm_num⟩
      let μ : Measure (ULift ℕ) := (binomial 2 p).map ULift.up
      let X : ULift ℕ → ℕ := ULift.down
  2. The random variable X has law Bin(2, 1/2) with respect to the measure μ.

    By definition of `HasLaw`, we check that `X = ULift.down` is almost everywhere measurable (using `measurable_down.aemeasurable`) and that the pushforward measure `X# μ` equals `Bin(2, 1/2)`. Because `μ` is the pushforward under `ULift.up`, their composition `ULift.down ∘ ULift.up` is the identity map, so `Measure.map_map` and `Measure.map_id` show `X# μ = Bin(2, 1/2)`.

    lines 12–19

    uses measurable_down, Measure.map_map, measurable_up, Measure.map_id

      have hX : HasLaw X (binomial 2 p) μ := by
        dsimp [X, μ]
        refine ⟨?_, ?_⟩
        · exact measurable_down.aemeasurable
        · rw [Measure.map_map measurable_down measurable_up]
          convert Measure.map_id (μ := binomial 2 p) using 2
          funext x
          rfl
  3. Specialising the universal bound to n = 2, α = 1/10, and X yields μ({ω | |X(ω) - 1| ≤ (1/10)√2}) ≤ 2e(1/10)/π.

    We instantiate the universal hypothesis `h` with `Ω = ULift ℕ`, measure `μ`, `n = 2` (satisfying `1 ≤ 2`), random variable `X`, distribution witness `hX`, and `α = 1/10 > 0`. Simplifying numerical expressions `2 / 2 = 1` and `√2` yields the inequality `h'`.

    lines 20–21

      have h' := h (Ω := ULift ℕ) (μ := μ) 2 (by norm_num) X hX (1/10) (by norm_num)
      norm_num at h'
  4. The probability under μ translates to the binomial measure of the set {x ∈ ℕ | |x - 1| ≤ (1/10)√2}.

    The set `{x : ℕ | |x - 1| ≤ (1/10)√2}` is measurable by the `measurability` tactic. Using the fact that `X` has law `Bin(2, 1/2)`, rewriting along `hX.measureReal_eq` expresses the probability of the preimage under `X` directly as the binomial probability of this set in `ℕ`.

    lines 22–24

      have hmeas : MeasurableSet {x : ℕ | |(x : ℝ) - 1| ≤ (1/10 : ℝ) * Real.sqrt (2 : ℝ)} := by
        measurability
      rw [hX.measureReal_eq (p := fun x => |(x : ℝ) - 1| ≤ (1/10 : ℝ) * Real.sqrt (2 : ℝ)) hmeas] at h'
  5. The set {x ∈ ℕ | |x - 1| ≤ (1/10)√2} is exactly the singleton {1}.

    We show both inclusions for the set of natural numbers. For the forward direction, if `|ω - 1| ≤ (1/10)√2`, since `√2 < 2` (via `Real.sqrt_lt'`), we have `|ω - 1| < (1/10) * 2 < 1`. Unfolding the absolute value with `abs_lt.mp` yields `-1 < ω - 1 < 1`, which means `ω ∈ (0, 2)`. Because `ω` is a natural number, `0 < ω < 2` forces `ω = 1`. For the reverse direction, setting `ω = 1` gives `|1 - 1| = 0 ≤ (1/10)√2`, which holds immediately.

    lines 25–50

    uses Set.mem_setOf_eq, Set.mem_singleton_iff, Real.sqrt_lt', Real.sqrt_nonneg, Set.mem_Ioo, abs_lt.mp

      have hset : ({x : ℕ | |(x : ℝ) - 1| ≤ (1/10 : ℝ) * Real.sqrt (2 : ℝ)}) = {1} := by
        ext ω
        constructor
        · intro hmem
          simp only [Set.mem_setOf_eq, Set.mem_singleton_iff] at hmem ⊢
          have hsqrt : Real.sqrt (2 : ℝ) < 2 := by
            rw [Real.sqrt_lt' (by norm_num : (0:ℝ) < 2)]
            norm_num
          have hlt : |(ω : ℝ) - 1| < 1 := by
            calc |(ω : ℝ) - 1| ≤ (1/10 : ℝ) * Real.sqrt 2 := hmem
              _ < (1/10 : ℝ) * 2 := by nlinarith [Real.sqrt_nonneg (2:ℝ)]
              _ < 1 := by norm_num
          have hrange : (ω : ℝ) ∈ Set.Ioo 0 2 := by
            rw [Set.mem_Ioo]
            constructor
            · have := (abs_lt.mp hlt).1
              linarith
            · have := (abs_lt.mp hlt).2
              linarith
          have hωlt : ω < 2 := by exact_mod_cast hrange.2
          have hωpos : 0 < ω := by exact_mod_cast hrange.1
          omega
        · intro hmem
          simp only [Set.mem_setOf_eq, Set.mem_singleton_iff] at hmem ⊢
          subst ω
          norm_num
  6. The binomial probability of {1} evaluates to 1/2, simplifying the inequality to 1/2 ≤ 2e(1/10)/π.

    Substituting `{1}` into `h'` and applying `ProbabilityTheory.binomial_real_singleton` evaluates the probability to `C(2, 1) * (1/2)^1 * (1 - 1/2)^1 = 2 * (1/2) * (1/2) = 1/2`. This reduces the inequality to `1/2 ≤ 2e(1/10)/π`.

    lines 51–53

    uses ProbabilityTheory.binomial_real_singleton

      rw [hset] at h'
      rw [ProbabilityTheory.binomial_real_singleton] at h'
      norm_num at h'
  7. The right-hand side is strictly less than 1/5, contradicting 1/2 ≤ 2e(1/10)/π.

    Using `e < 2.7182818286 < 3` from `Real.exp_one_lt_d9` and `π > 3` from `Real.pi_gt_three`, clearing the positive denominator `π > 0` (`Real.pi_pos`) via `div_lt_iff₀` shows `2e(1/10)/π < 1/5`. Since `1/2 ≤ 2e(1/10)/π < 1/5` implies `1/2 < 1/5`, `linarith` derives a contradiction.

    lines 54–61

    uses Real.exp_one_lt_d9, Real.pi_pos, div_lt_iff₀, Real.pi_gt_three

      have hexp3 : Real.exp 1 < 3 := by
        calc Real.exp 1 < 2.7182818286 := Real.exp_one_lt_d9
          _ < 3 := by norm_num
      have hden : (0 : ℝ) < Real.pi := Real.pi_pos
      have hb : 2 * Real.exp 1 * (1/10) / Real.pi < 1/5 := by
        rw [div_lt_iff₀ hden]
        nlinarith [Real.pi_gt_three]
      linarith
Measure.map_map
The pushforward of a pushforward measure along two measurable maps is the pushforward along their composition: g# (f# μ) = (g ∘ f)# μ.
measurable_down
The projection map `ULift.down : ULift α → α` is measurable.
measurable_up
The lifting map `ULift.up : α → ULift α` is measurable.
Measure.map_id
The pushforward of any measure under the identity map is the measure itself.
Set.mem_setOf_eq
An element belongs to a set comprehension {x | P(x)} if and only if P(x) holds.
Set.mem_singleton_iff
An element belongs to the singleton {b} if and only if it equals b.
Real.sqrt_lt'
For positive y > 0, √x < y if and only if x < y².
Real.sqrt_nonneg
The square root of any real number is non-negative: 0 ≤ √x.
Set.mem_Ioo
An element belongs to the open interval (a, b) if and only if a < x and x < b.
abs_lt.mp
If |a| < b, then -b < a and a < b.
ProbabilityTheory.binomial_real_singleton
The binomial distribution Bin(n, p) assigns to the singleton {k} the probability C(n, k) p^k (1 - p)^(n - k).
Real.exp_one_lt_d9
Euler's number e = exp(1) is strictly less than 2.7182818286.
Real.pi_pos
The circle constant π is strictly positive: 0 < π.
div_lt_iff₀
For a positive divisor c > 0, b / c < a if and only if b < a * c.
Real.pi_gt_three
The circle constant π is strictly greater than 3.

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

open MeasureTheory ProbabilityTheoryopen scoped unitIntervaltheorem not_fair_binomial_anticoncentration_bound : ¬ (∀ {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ]    (n : ℕ) (hn : 1 ≤ n) (X : Ω → ℕ)    (hX : HasLaw X (binomial n ⟨1/2, by norm_num⟩) μ)    (α : ℝ) (hα_pos : 0 < α), μ.real {ω | |(X ω : ℝ) - (n : ℝ) / 2| ≤ α * Real.sqrt (n : ℝ)} ≤      2 * Real.exp 1 * α / Real.pi) := by  intro h  let p : unitInterval := ⟨1/2, by norm_num⟩  let μ : Measure (ULift ℕ) := (binomial 2 p).map ULift.up  let X : ULift ℕ → ℕ := ULift.down  have hX : HasLaw X (binomial 2 p) μ := by    dsimp [X, μ]    refine ⟨?_, ?_⟩    · exact measurable_down.aemeasurable    · rw [Measure.map_map measurable_down measurable_up]      convert Measure.map_id (μ := binomial 2 p) using 2      funext x      rfl  have h' := h (Ω := ULift ℕ) (μ := μ) 2 (by norm_num) X hX (1/10) (by norm_num)  norm_num at h'  have hmeas : MeasurableSet {x : ℕ | |(x : ℝ) - 1| ≤ (1/10 : ℝ) * Real.sqrt (2 : ℝ)} := by    measurability  rw [hX.measureReal_eq (p := fun x => |(x : ℝ) - 1| ≤ (1/10 : ℝ) * Real.sqrt (2 : ℝ)) hmeas] at h'  have hset : ({x : ℕ | |(x : ℝ) - 1| ≤ (1/10 : ℝ) * Real.sqrt (2 : ℝ)}) = {1} := by    ext ω    constructor    · intro hmem      simp only [Set.mem_setOf_eq, Set.mem_singleton_iff] at hmem ⊢      have hsqrt : Real.sqrt (2 : ℝ) < 2 := by        rw [Real.sqrt_lt' (by norm_num : (0:ℝ) < 2)]        norm_num      have hlt : |(ω : ℝ) - 1| < 1 := by        calc |(ω : ℝ) - 1| ≤ (1/10 : ℝ) * Real.sqrt 2 := hmem          _ < (1/10 : ℝ) * 2 := by nlinarith [Real.sqrt_nonneg (2:ℝ)]          _ < 1 := by norm_num      have hrange : (ω : ℝ) ∈ Set.Ioo 0 2 := by        rw [Set.mem_Ioo]        constructor        · have := (abs_lt.mp hlt).1          linarith        · have := (abs_lt.mp hlt).2          linarith      have hωlt : ω < 2 := by exact_mod_cast hrange.2      have hωpos : 0 < ω := by exact_mod_cast hrange.1      omega    · intro hmem      simp only [Set.mem_setOf_eq, Set.mem_singleton_iff] at hmem ⊢      subst ω      norm_num  rw [hset] at h'  rw [ProbabilityTheory.binomial_real_singleton] at h'  norm_num at h'  have hexp3 : Real.exp 1 < 3 := by    calc Real.exp 1 < 2.7182818286 := Real.exp_one_lt_d9      _ < 3 := by norm_num  have hden : (0 : ℝ) < Real.pi := Real.pi_pos  have hb : 2 * Real.exp 1 * (1/10) / Real.pi < 1/5 := by    rw [div_lt_iff₀ hden]    nlinarith [Real.pi_gt_three]  linarith
See it in the graphDiscuss this resultChallenge it