AFTD Auto-Formalizing Theoretical Domains

avg_pairwise_hamming_dist_singleton

theoremverified

For any natural number $n$ and any point $c : \mathrm{Fin}\ n \to \mathrm{Bool}$, the average pairwise Hamming distance of the singleton set $\{c\} \subseteq (\mathrm{Fin}\ n \to \mathrm{Bool})$ is $0$.

Statement

theorem avg_pairwise_hamming_dist_singleton {n : ℕ} (c : Fin n → Bool) :
    avg_pairwise_hamming_dist ({c} : Finset (Fin n → Bool)) = 0
Source
folklore
Verified
31 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • avg_pairwise_hamming_distFor an implicit dimension $n$ and a finite subset $F : \mathrm{Finset} (\mathrm{Fin}\ n \to \mathrm{Bool})$, the average pairwise Hamming…

Read back from the Lean

For any natural number $n$ and any boolean vector $c : \text{Fin } n \to \text{Bool}$, the average pairwise Hamming distance of the singleton set $\{c\}$ is equal to $0$.

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

The proof, explained

By definition, the average pairwise Hamming distance of a finite set F of Boolean vectors is the sum of distances between all pairs divided by |F|². For a singleton set {c}, the double sum reduces to the distance from c to itself, which is zero by hammingDist_self, so the overall average evaluates to zero.

  1. The average pairwise Hamming distance of the singleton set {c} is 0

    Unfolding the definition of avg_pairwise_hamming_dist expands the average to the double sum over all pairs in {c} divided by |{c}|². Since {c} is a singleton, the sum reduces to the single term hammingDist c c, which evaluates to 0 by hammingDist_self. With a numerator of 0 and a denominator of 1² = 1, the entire expression simplifies to 0.

    line 4

    uses avg_pairwise_hamming_dist, hammingDist_self

      simp [avg_pairwise_hamming_dist, hammingDist_self]
avg_pairwise_hamming_dist
The average pairwise Hamming distance of a finite set F of Boolean vectors is defined as the sum of all pairwise Hamming distances divided by |F|²
hammingDist_self
The Hamming distance between any element and itself is zero (hammingDist x x = 0)

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- The average pairwise Hamming distance of a singleton in the Boolean hypercube is zero. -/theorem avg_pairwise_hamming_dist_singleton {n : ℕ} (c : Fin n → Bool) :    avg_pairwise_hamming_dist ({c} : Finset (Fin n → Bool)) = 0 := by  simp [avg_pairwise_hamming_dist, hammingDist_self]
See it in the graphDiscuss this resultChallenge it