AFTD Auto-Formalizing Theoretical Domains

signed_coordinate_dist_self

theoremverified

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.

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

    lines 4–5

      haveI : Nonempty (Fin n) := ⟨⟨0, hn⟩⟩
      unfold signed_coordinate_dist
  2. Every 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`.

    lines 6–14

    uses mul_nonneg, Finset.sum_nonneg

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

    lines 15–21

    uses ciInf_eq_of_forall_ge_of_forall_gt_exists_lt

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

    lines 22–26

    uses ciInf_eq_of_forall_ge_of_forall_gt_exists_lt, le_ciInf

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

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: 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⟩
See it in the graphDiscuss this resultChallenge it