AFTD Auto-Formalizing Theoretical Domains

ose_hamming_flip

theoremverified

A Boolean tuple and the tuple obtained by flipping one coordinate have Hamming distance one.

Statement

theorem ose_hamming_flip (n : ℕ) (x : Fin n → Bool) (i : Fin n) :
    hammingDist x (Function.update x i (!(x i))) = 1
Source
arXiv:2611.08546, Section 6.1; Boolean-cube distortion argument
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 2

Lean source view module on GitHub

theorem ose_hamming_flip (n : ℕ) (x : Fin n → Bool) (i : Fin n) :
    hammingDist x (Function.update x i (!(x i))) = 1 := by
  classical
  have hset : (Finset.univ.filter fun j : Fin n => x j ≠ Function.update x i (!(x i)) j) = {i} := by
    ext j
    by_cases h : j = i
    · subst j
      cases hxi : x i <;> simp [Function.update, hxi]
    · simp [Function.update, h]
  simp [hammingDist, hset]
See it in the graphDiscuss this resultChallenge it