AFTD Auto-Formalizing Theoretical Domains

coordinate_indicator_is_balanced

theoremverified

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.

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

    lines 4–5

      dsimp [is_balanced_indicator]
      refine ⟨?_, ?_⟩
  2. 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.

    lines 6–9

      · intro x
        split_ifs
        · right; rfl
        · left; rfl
  3. 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).

    lines 10–20

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

    lines 21–23

    uses Nat.exists_eq_succ_of_ne_zero, ne_of_gt, pow_succ

        rw [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.

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

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