coordinate_indicator_is_balanced
For every positive integer n, coordinate i : Fin n, and boolean value b, the signed coordinate indicator x ↦ if x i = b then 1 else 0 is a balanced Boolean indicator.
Statement
lemma coordinate_indicator_is_balanced (n : ℕ) (hn : 0 < n) (i : Fin n) (b : Bool) : is_balanced_indicator n (fun x ↦ if x i = b then 1 else 0)
- Source
- arXiv:2611.00868, Section 1
- Verified
- 05 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- is_balanced_indicatorA real-valued function f on the n-dimensional Boolean cube is a balanced Boolean indicator if f takes values in {0, 1} and its uniform…
Read back from the Lean
For any natural number $n$ satisfying $0 < n$, any coordinate index $i : \text{Fin } n$, and any boolean value $b : \text{Bool}$, the indicator function $x \mapsto (\text{if } x(i) = b \text{ then } 1 \text{ else } 0)$ from $(\text{Fin } n \to \text{Bool})$ to $\mathbb{R}$ is a balanced indicator function (is_balanced_indicator).
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 indicator function of the event x_i = b takes values in {0, 1} by definition. To show that its average is 1/2, the domain {0, 1}^n is factored into {0, 1} × {0, 1}^(n - 1) by isolating the i-th coordinate. Under this product decomposition, the indicator depends only on the i-th bit, so the sum over all inputs evaluates to 1 * 2^(n - 1) = 2^(n - 1). Because n > 0, dividing this sum by 2^n yields 1/2, proving that the indicator is balanced.
Unfold the definition of a balanced Boolean indicator and split into two obligations: verifying the range is {0, 1} and verifying the mean is 1/2.
We unfold `is_balanced_indicator`, which requires that the function takes values in {0, 1} and that (1 / 2^n) ∑ x, f(x) = 1/2. We split this conjunction into two independent goals.
dsimp [is_balanced_indicator] refine ⟨?_, ?_⟩
The indicator function takes values in {0, 1} for every input x.
For any input x : Fin n → Bool, we consider cases on whether x i = b. If x i = b, the indicator evaluates to 1, satisfying 1 = 1. If x i ≠ b, it evaluates to 0, satisfying 0 = 0.
· intro x split_ifs · right; rfl · left; rfl
The sum of the indicator over all 2^n inputs equals 2^(n - 1).
We isolate coordinate i using the equivalence `Equiv.piSplitAt`, which identifies Fin n → Bool with Bool × ({j // j ≠ i} → Bool). The indicator factors through this bijection as checking whether the first component equals b. By `Fintype.sum_equiv`, we transfer the sum across this equivalence, and by `Fintype.sum_prod_type`, we express it as an iterated sum. Swapping the sums using `Finset.sum_comm`, the inner sum over Bool evaluates to 1 because exactly one boolean value equals b. Summing 1 over the 2^(n - 1) configurations of the remaining coordinates yields 2^(n - 1).
uses
Equiv.piSplitAt,Fintype.sum_equiv,Fintype.sum_prod_type,Finset.sum_comm· have h_sum : (∑ x : Fin n → Bool, (if x i = b then (1 : ℝ) else 0)) = (2 : ℝ) ^ (n - 1) := by let e := Equiv.piSplitAt i (fun _ => Bool) have h_eq : ∀ x, (if x i = b then (1 : ℝ) else 0) = (fun p : Bool × ({ j // j ≠ i } → Bool) ↦ if p.1 = b then (1 : ℝ) else 0) (e x) := by intro x rfl rw [Fintype.sum_equiv e (fun x => if x i = b then (1 : ℝ) else 0) (fun p => if p.1 = b then (1 : ℝ) else 0) h_eq] rw [Fintype.sum_prod_type] rw [Finset.sum_comm] simp
The average value of the indicator is 1/2.
We substitute the sum 2^(n - 1) into the expression (1 / 2^n) * ∑ x, f(x). Since n > 0, we have n ≠ 0 by `ne_of_gt`, so by `Nat.exists_eq_succ_of_ne_zero` we write n = k + 1. Rewriting 2^(k + 1) as 2^k * 2 using `pow_succ`, the factor of 2^k cancels, simplifying (1 / 2^(k + 1)) * 2^k to 1/2.
uses
Nat.exists_eq_succ_of_ne_zero,ne_of_gt,pow_succrw [h_sum] obtain ⟨k, rfl⟩ := Nat.exists_eq_succ_of_ne_zero (ne_of_gt hn) simp [pow_succ]
Equiv.piSplitAt- Decomposes a function space `(j : α) → β j` into the Cartesian product of the value at coordinate `i` and the restriction of the function to all coordinates `j ≠ i`.
Fintype.sum_equiv- The sum of a function over a finite type is preserved when re-indexed along a bijection to another finite type.
Fintype.sum_prod_type- A sum over the Cartesian product of two finite types is equal to the iterated sum over each type.
Finset.sum_comm- The order of summation in a finite double sum can be exchanged.
Nat.exists_eq_succ_of_ne_zero- Every non-zero natural number is the successor of some natural number (n = k + 1).
ne_of_gt- If b < a, then a ≠ b.
pow_succ- In any monoid, a^(n + 1) = a^n * a.
- In line 20, `simp` automatically evaluates the inner sum over `Bool` (which has two elements, exactly one equaling `b`) to 1 and computes the sum of 1 over the function type of the remaining n - 1 coordinates, using the fact that its cardinality is 2^(n - 1).
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.
/-- Sanity lemma: signed coordinate indicators are balanced Boolean indicators. -/lemma coordinate_indicator_is_balanced (n : ℕ) (hn : 0 < n) (i : Fin n) (b : Bool) : is_balanced_indicator n (fun x ↦ if x i = b then 1 else 0) := by dsimp [is_balanced_indicator] refine ⟨?_, ?_⟩ · intro x split_ifs · right; rfl · left; rfl · have h_sum : (∑ x : Fin n → Bool, (if x i = b then (1 : ℝ) else 0)) = (2 : ℝ) ^ (n - 1) := by let e := Equiv.piSplitAt i (fun _ => Bool) have h_eq : ∀ x, (if x i = b then (1 : ℝ) else 0) = (fun p : Bool × ({ j // j ≠ i } → Bool) ↦ if p.1 = b then (1 : ℝ) else 0) (e x) := by intro x rfl rw [Fintype.sum_equiv e (fun x => if x i = b then (1 : ℝ) else 0) (fun p => if p.1 = b then (1 : ℝ) else 0) h_eq] rw [Fintype.sum_prod_type] rw [Finset.sum_comm] simp rw [h_sum] obtain ⟨k, rfl⟩ := Nat.exists_eq_succ_of_ne_zero (ne_of_gt hn) simp [pow_succ]