hypercube_rel_dist
def
The relative Hamming distance between two functions f and g from the hypercube Fin n → Bool into Fin (k + 1) is the number of inputs where f and g differ divided by 2^n.
Statement
noncomputable def hypercube_rel_dist {n k : ℕ} (f g : (Fin n → Bool) → Fin (k + 1)) : ℝ
- Defined in
- arXiv:2611.02374 Def. 2.4
- Verified
- 05 Nov 2026
- Axioms
- none listed
- Used by 2
- is_eps_far_submodularA function f from Fin n → Bool to Fin (k + 1) is ε-far from submodularity if for every submodular function g from Fin n → Bool to Fin (k +…
- op_932_submodular_not_farFor any positive ε, a submodular function from Fin n → Bool to Fin (k + 1) is not ε-far from submodularity.
Read back from the Lean
hypercube_rel_dist defines a function parameterized by implicit natural numbers n and k, taking two functions f and g from (Fin n → Bool) to Fin (k + 1), and returning the real number obtained by dividing the cardinality of the set of inputs x : Fin n → Bool where f x ≠ g x (i.e., Finset.univ.filter (fun x => f x ≠ g x)) by 2 ^ n.
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
/-- Relative Hamming distance between two functions from Fin n → Bool to Fin (k + 1). -/ noncomputable def hypercube_rel_dist {n k : ℕ} (f g : (Fin n → Bool) → Fin (k + 1)) : ℝ := ((Finset.univ.filter (fun x => f x ≠ g x)).card : ℝ) / (2 ^ n : ℝ)