AFTD Auto-Formalizing Theoretical Domains

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