AFTD Auto-Formalizing Theoretical Domains

min_avg_pairwise_hamming_dist_density_one_sixteenth_n_eq_four

theoremverified

For $n = 4$, every subset $F \subseteq (\mathrm{Fin}\ 4 \to \mathrm{Bool})$ of cardinality $2^{4-4} = 1$ attains average pairwise Hamming distance $(4-4)/2 = 0$ and is a $0$-dimensional subcube is_subcube (4 - 4) F.

Statement

theorem min_avg_pairwise_hamming_dist_density_one_sixteenth_n_eq_four
    (F : Finset (Fin 4 → Bool)) (hF : F.card = 2 ^ (4 - 4)) :
    avg_pairwise_hamming_dist F = (4 - 4 : ℝ) / 2 ∧ is_subcube (4 - 4) F
Source
arXiv:2610.40486 Sec. 3
Verified
31 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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…
  • is_subcubeFor an implicit dimension $n$, a dimension $d : \mathbb{N}$, and a finite subset…

Read back from the Lean

For every finite set F of Boolean functions on 4 coordinates (F : Finset (Fin 4 → Bool)) whose cardinality is 2^(4 - 4) (which equals 1): 1. The average pairwise Hamming distance of F equals (4 - 4 : ℝ) / 2 (which equals 0). 2. F is a (4 - 4)-dimensional subcube (i.e., a 0-dimensional subcube).

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

Since F has cardinality 2^(4 - 4) = 1, it must be a singleton {c}. The average pairwise Hamming distance of a singleton is 0 because the only pair is (c, c), whose Hamming distance is zero. Furthermore, {c} is a 0-dimensional subcube obtained by fixing all coordinates (the full set Finset.univ) to agree with c.

  1. F is a singleton {c} for some boolean vector c : Fin 4 → Bool.

    The hypothesis hF states that |F| = 2^(4 - 4) = 1. By Finset.card_eq_one.mp, any finite set of cardinality 1 is a singleton {c}. We substitute F = {c} throughout the goal.

    lines 5–6

    uses Finset.card_eq_one.mp

      obtain ⟨c, hFc⟩ := Finset.card_eq_one.mp (by norm_num at hF; exact hF)
      subst hFc
  2. The average pairwise Hamming distance of {c} is (4 - 4) / 2 = 0.

    We split the goal into the two conjuncts. Unfolding the definition of avg_pairwise_hamming_dist on {c} yields the sum of Hamming distances over all pairs in {c} divided by |{c}|². The only pair is (c, c), whose Hamming distance is 0 by hammingDist_self. The expression evaluates to 0 / 1 = 0, matching (4 - 4) / 2.

    lines 7–9

    uses hammingDist_self

      constructor
      · unfold avg_pairwise_hamming_dist
        simp [hammingDist_self]
  3. {c} is a 0-dimensional subcube.

    By definition, a subset of (Fin 4 → Bool) is a subcube of dimension d if there is a coordinate subset S with |S| + d = 4 and a center point such that the subset consists of all vectors agreeing with the center on S. Here the dimension is 4 - 4 = 0, so we fix all coordinates by taking S = Finset.univ and the center point c. The dimension condition |Finset.univ| + 0 = 4 holds since Fin 4 has 4 elements. Finally, by set extensionality and function extensionality (funext_iff), a vector x equals c if and only if x i = c i for all i ∈ Finset.univ.

    lines 10–13

    uses funext_iff

      · refine ⟨Finset.univ, c, ?_, ?_⟩
        · simp
        · ext x
          simp [funext_iff]
Finset.card_eq_one.mp
A finite set has cardinality 1 if and only if it is a singleton {a} for some element a.
hammingDist_self
The Hamming distance between any element and itself is zero.
funext_iff
Two functions are equal if and only if they agree on all inputs.

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 density 1/16 minimum average Hamming distance conjecture holds for n = 4. -/theorem min_avg_pairwise_hamming_dist_density_one_sixteenth_n_eq_four    (F : Finset (Fin 4 → Bool)) (hF : F.card = 2 ^ (4 - 4)) :    avg_pairwise_hamming_dist F = (4 - 4 : ℝ) / 2 ∧ is_subcube (4 - 4) F := by  obtain ⟨c, hFc⟩ := Finset.card_eq_one.mp (by norm_num at hF; exact hF)  subst hFc  constructor  · unfold avg_pairwise_hamming_dist    simp [hammingDist_self]  · refine ⟨Finset.univ, c, ?_, ?_⟩    · simp    · ext x      simp [funext_iff]
See it in the graphDiscuss this resultChallenge it