not_fair_binomial_anticoncentration_bound
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.
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`.
(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
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)`.
uses
measurable_down,Measure.map_map,measurable_up,Measure.map_idhave 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
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'`.
have h' := h (Ω := ULift ℕ) (μ := μ) 2 (by norm_num) X hX (1/10) (by norm_num) norm_num at h'
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 `ℕ`.
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'
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.
uses
Set.mem_setOf_eq,Set.mem_singleton_iff,Real.sqrt_lt',Real.sqrt_nonneg,Set.mem_Ioo,abs_lt.mphave 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
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)/π`.
uses
ProbabilityTheory.binomial_real_singletonrw [hset] at h' rw [ProbabilityTheory.binomial_real_singleton] at h' norm_num at h'
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.
uses
Real.exp_one_lt_d9,Real.pi_pos,div_lt_iff₀,Real.pi_gt_threehave 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.
- In the theorem statement (line 5), `by norm_num` is an embedded tactic proof certifying that 1/2 belongs to the unit interval [0, 1].
- The universal quantification over `Ω : Type*` requires constructing the counterexample on the universe-lifted space `ULift ℕ` rather than `ℕ` directly, and taking the random variable `X` to be `ULift.down`.
- On line 23, the `measurability` tactic automatically proves that the event subset `{x : ℕ | |x - 1| ≤ (1/10)√2}` is measurable.
- On line 46, the `omega` tactic automatically deduces `ω = 1` from the bounds `0 < ω` and `ω < 2` for a natural number `ω`.
- On lines 60–61, `nlinarith` and `linarith` handle the arithmetic combining `e < 3` and `π > 3` to conclude `1/2 ≤ 2e/(10π) < 1/5`, deriving `False`.
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.
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