cube_dist
def
The normalized Hamming distance between two functions f, g : {0, 1}^n → {0, ..., k} is the fraction of points in {0, 1}^n where f and g disagree.
Statement
noncomputable def cube_dist {n k : ℕ} (f g : CubeFunc n k) : ℝ
- Defined in
- arXiv:2611.02374, Def. 2.4
- Verified
- 06 Nov 2026
- Axioms
- none listed
- Built on 1
- CubeFuncThe type of functions from the n-dimensional Boolean hypercube {0, 1}^n into {0, 1, ..., k}, represented by Fin (k + 1).
- Used by 1
- is_far_from_submodularA function f is ε-far from submodular if its normalized Hamming distance to every submodular function g with the same domain and codomain…
Read back from the Lean
The definition cube_dist takes implicit natural numbers n and k, and two functions f and g of type CubeFunc n k (functions from Fin n → Bool to Fin (k + 1)), and evaluates to the real number given by the cardinality of the finset of all x : Fin n → Bool for which f x ≠ g x, divided by 2^n (as a real number). This represents the fractional/normalized Hamming distance between f and g on the Boolean hypercube.
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
/-- The normalized Hamming distance between two functions on the Boolean hypercube. -/ noncomputable def cube_dist {n k : ℕ} (f g : CubeFunc n k) : ℝ := ((Finset.filter (fun x => f x ≠ g x) Finset.univ).card : ℝ) / (2 ^ n : ℝ)