signed_coordinate_dist_self
For every positive integer n, coordinate i : Fin n, and boolean value b, the dictator distance of the signed coordinate indicator x ↦ if x i = b then 1 else 0 is 0.
Statement
lemma signed_coordinate_dist_self (n : ℕ) (hn : 0 < n) (i : Fin n) (b : Bool) : signed_coordinate_dist n (fun x ↦ if x i = b then 1 else 0) = 0
- Source
- arXiv:2611.00868, Section 2, Eq. (10)
- Verified
- 05 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- signed_coordinate_distThe dictator distance delta(f) of a function f on the Boolean cube is the minimum normalized Hamming distance from f to any signed…
Read back from the Lean
For any natural number $n$, any hypothesis $hn : 0 < n$, any index $i \in \mathrm{Fin}\ n$, and any boolean $b : \mathrm{Bool}$, the signed coordinate distance (signed_coordinate_dist n) of the indicator function $(x \mapsto \text{if } x(i) = b \text{ then } 1 \text{ else } 0)$ is equal to $0$.
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 dictator distance of a function is the infimum over all coordinates i' and signs b' of its average distance to the signed dictator x ↦ [x(i') = b']. For the signed coordinate indicator x ↦ [x(i) = b], every term in this distance is a sum of nonnegative indicators, so 0 is a lower bound. Choosing the matching coordinate i' = i and sign b' = b makes the dictator identical to the function, yielding an exact distance of 0 and showing that the infimum is 0.
The index type Fin n is nonempty, and the goal unfolds to a double infimum.
Since n > 0, the element 0 : Fin n exists, so Fin n is nonempty, ensuring that indexed infima over Fin n are well-defined. Unfolding `signed_coordinate_dist` expresses the distance as the double infimum over coordinate i' and sign b' of the average Hamming distance to the dictator function.
haveI : Nonempty (Fin n) := ⟨⟨0, hn⟩⟩ unfold signed_coordinate_distEvery distance term between the two indicators is nonnegative. automation
The factor 1 / 2^n is positive, and each term in the sum is an indicator taking value 0 or 1. Case splitting on the if-then-else conditions (`split_ifs`) and numerical simplification (`norm_num`) verify that every term is nonnegative. Summing over Fin n → Bool preserves nonnegativity by `Finset.sum_nonneg`, and multiplying by the positive prefactor preserves nonnegativity by `mul_nonneg`.
uses
mul_nonneg,Finset.sum_nonneghave hterm : ∀ (i' : Fin n) (b' : Bool), 0 ≤ (1 / (2 : ℝ) ^ n) * ∑ x : Fin n → Bool, if (if x i = b then (1:ℝ) else 0) ≠ (if x i' = b' then 1 else 0) then 1 else 0 := by intro i' b' apply mul_nonneg (by positivity) apply Finset.sum_nonneg intro x _ split_ifs <;> norm_num
For the coordinate i, the infimum over signs b' is 0. automation
By `ciInf_eq_of_forall_ge_of_forall_gt_exists_lt`, an infimum is 0 if 0 is a lower bound and every w > 0 strictly exceeds some term. Lower-boundedness holds by the nonnegativity established in the previous step. For any w > 0, choosing the witness b' = b compares the indicator function to itself, making all difference terms vanish; the sum evaluates to 0, which is strictly less than w.
uses
ciInf_eq_of_forall_ge_of_forall_gt_exists_lthave hinner : (⨅ b' : Bool, (1 / (2 : ℝ) ^ n) * ∑ x : Fin n → Bool, if (if x i = b then (1:ℝ) else 0) ≠ (if x i = b' then 1 else 0) then 1 else 0) = 0 := by refine ciInf_eq_of_forall_ge_of_forall_gt_exists_lt (fun b' => hterm i b') ?_ intro w hw exact ⟨b, by simp [hw]⟩
The outer infimum over all coordinates i' is 0, concluding the proof.
Applying `ciInf_eq_of_forall_ge_of_forall_gt_exists_lt` again, 0 is a lower bound for each coordinate i' by `le_ciInf` and the nonnegativity lemma `hterm`. For any w > 0, choosing coordinate i gives an inner infimum of 0 by `hinner`, which is strictly less than w.
uses
ciInf_eq_of_forall_ge_of_forall_gt_exists_lt,le_ciInfrefine ciInf_eq_of_forall_ge_of_forall_gt_exists_lt ?_ ?_ · intro i' exact le_ciInf (fun b' => hterm i' b') · intro w hw exact ⟨i, by rw [hinner]; exact hw⟩
mul_nonneg- The product of two nonnegative numbers is nonnegative.
Finset.sum_nonneg- A sum of nonnegative terms over a finite set is nonnegative.
ciInf_eq_of_forall_ge_of_forall_gt_exists_lt- In a conditionally complete lattice, an infimum ⨅ x, f x equals b if b is a lower bound for f and any value w > b strictly exceeds f(x) for some x.
le_ciInf- In a conditionally complete lattice, if c is a lower bound for every element of a nonempty family f, then c ≤ ⨅ x, f x.
- When b' = b in line 21, `simp` automatically evaluates each indicator difference to 0 and simplifies the entire average to 0 < w.
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: dictator distance of a signed coordinate indicator is zero. -/lemma signed_coordinate_dist_self (n : ℕ) (hn : 0 < n) (i : Fin n) (b : Bool) : signed_coordinate_dist n (fun x ↦ if x i = b then 1 else 0) = 0 := by haveI : Nonempty (Fin n) := ⟨⟨0, hn⟩⟩ unfold signed_coordinate_dist have hterm : ∀ (i' : Fin n) (b' : Bool), 0 ≤ (1 / (2 : ℝ) ^ n) * ∑ x : Fin n → Bool, if (if x i = b then (1:ℝ) else 0) ≠ (if x i' = b' then 1 else 0) then 1 else 0 := by intro i' b' apply mul_nonneg (by positivity) apply Finset.sum_nonneg intro x _ split_ifs <;> norm_num have hinner : (⨅ b' : Bool, (1 / (2 : ℝ) ^ n) * ∑ x : Fin n → Bool, if (if x i = b then (1:ℝ) else 0) ≠ (if x i = b' then 1 else 0) then 1 else 0) = 0 := by refine ciInf_eq_of_forall_ge_of_forall_gt_exists_lt (fun b' => hterm i b') ?_ intro w hw exact ⟨b, by simp [hw]⟩ refine ciInf_eq_of_forall_ge_of_forall_gt_exists_lt ?_ ?_ · intro i' exact le_ciInf (fun b' => hterm i' b') · intro w hw exact ⟨i, by rw [hinner]; exact hw⟩