AFTD Auto-Formalizing Theoretical Domains

signed_coordinate_dist

def

The dictator distance delta(f) of a function f on the Boolean cube is the minimum normalized Hamming distance from f to any signed coordinate indicator x ↦ if x i = b then 1 else 0.

Statement

open scoped BigOperators in
noncomputable def signed_coordinate_dist (n : ℕ) (f : (Fin n → Bool) → ℝ) : ℝ
Defined in
arXiv:2611.00868, Section 2, Eq. (10)
Verified
04 Nov 2026
Axioms
none listed
Used by 1
  • signed_coordinate_dist_selfFor every positive integer n, coordinate i : Fin n, and boolean value b, the dictator distance of the signed coordinate indicator x ↦ if x…

Read back from the Lean

For a natural number n and a function f : (Fin n → Bool) → ℝ, signed_coordinate_dist n f is defined as the infimum over all indices i : Fin n and booleans b : Bool of the normalized sum: (1 / 2^n) * ∑_{x : Fin n → Bool} (1 if f(x) ≠ (if x(i) = b then 1 else 0) else 0). In other words, it is the infimum over all coordinate directions i and signs b of the fraction of inputs x ∈ {0, 1}^n at which f(x) does not equal the indicator of the event x_i = b.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

open scoped BigOperators in
/-- Minimum normalized Hamming distance from f to any signed coordinate indicator. -/
noncomputable def signed_coordinate_dist (n : ℕ) (f : (Fin n → Bool) → ℝ) : ℝ := ⨅ (i : Fin n) (b : Bool),
    (1 / (2 : ℝ) ^ n) * ∑ x : Fin n → Bool, if f x ≠ (if x i = b then 1 else 0) then 1 else 0
See it in the graphDiscuss this resultChallenge it